so103. CHU TRÌNH CƠ BẢN easy – 10test

^so103. CHU TRÌNH CƠ BẢN ^{easy – 10test}

Một khách du lịch xuất phát từ địa điểm S muốn đi thăm một số địa điểm khác rồi sau đó quay trở về S. Để tránh sự nhàm chán, ông ta muốn tìm một hành trình không qua một con đường hay một địa điểm nào quá một lần (Tất nhiên, ngoại trừ địa điểm S phải có mặt trong hành trình hai lần bởi đó là nơi bắt đầu cũng như kết thúc hành trình).

• 
  Dòng 1: Chứa hai số n, S (3  n  200).
  
• 
  Các dòng tiếp theo, mỗi dòng chứa hai số nguyên dương u, v cho ta thông tin: giữa hai địa điểm u và v có một đường đi hai chiều nối chúng.
  

• 
  Dòng 1: Ghi từ YES hay NO tuỳ theo có tồn tại hành trình thoả mãn yêu cầu của du khách hay không
  
• 
  Nếu dòng 1 ghi từ YES, dòng 2 ghi hành trình tìm được: Bắt đầu là địa điểm S, tiếp theo là danh sách các địa điểm sẽ đi qua theo đúng thứ tự trong hành trình, cuối cùng lại là địa điểm S.
  

CIRCUIT.INP	CIRCUIT.OUT
7 1 1 2 1 5 1 7 2 3 2 4 3 4 5 6 6 7	YES 1 7 6 5 1

^Euler104. CỘT CÂY SỐ^{circuit – 10test}

Một mạng lưới giao thông gồm n thành phố và m tuyến đường xa lộ hai chiều. Giữa hai thành phố bất kỳ có nhiều nhất là một xa lộ nối trực tiếp từ thành phố này tới thành phố kia. Trên mỗi xa lộ, người ta đã dựng sẵn các cột cây số để chỉ đường cho hành khách.

Để điền số km trên các cột cây số, người ta sử dụng một rô-bốt. Muốn điền đủ các cột cây số trên một tuyến đường (u, v) thì rô bốt phải thực hiện một chuyến đi từ u tới v và một chuyến đi từ v về u, cứ sau mỗi km thì dừng lại và ghi vào một mặt của một cột cây số.

Ví dụ: Để điền các cột cây số trên tuyến đường Hà Nội - Hải Phòng. Đầu tiên rô bốt xuất phát từ Hà Nội, cứ đi mỗi km thì dừng lại và điền vào cột cây số dòng "Hà Nội ... km", tất nhiên chỉ có thể điền vào mặt quay về hướng Hải Phòng bởi Rô bốt không biết được từ đó đến Hải Phòng còn bao xa. Muốn điền dòng chữ "Hải Phòng ... km" lên mặt còn lại của các cột cây số thì rô bốt phải thực hiện hành trình từ Hải Phòng trở về Hà Nội
Yêu cầu: Giả thiết rằng hệ thống giao thông đảm bảo sự đi lại giữa hai thành phố bất kỳ. Hãy tìm một hành trình của Rô bốt xuất phát từ thành phố 1, đi viết đầy đủ lên các cột cây số rồi quay trở về thành phố 1, sao cho mỗi mặt của cột cây số bất kỳ nào cũng chỉ bị viết một lần.
Dữ liệu: Vào từ file văn bản MSTONE.INP

• 
  Dòng 1: Chứa hai số n, m cách nhau một dấu cách (2  n  200)
  
• 
  m dòng tiếp theo, mỗi dòng ghi hai số u, v cách nhau một dấu cách: cho biết giữa hai thành phố u và v có một tuyến xa lộ nối chúng
  

Kết quả: Ghi ra file văn bản MSTONE.OUT

• 
  Ghi các hành trình rô bốt phải đi: Bắt đầu từ thành phố 1, tiếp theo là các thành phố đi qua theo đúng thứ tự trong hành trình, kết thúc là thành phố 1. Các số hiệu thành phố phải ghi cách nhau ít nhất một dấu cách hoặc dấu xuống dòng.
  

Ví dụ:

MSTONE.INP	MSTONE.OUT
7 8 1 2 2 3 3 4 4 2 2 5 5 6 6 7 6 2	1 2 6 7 6 5 2 5 6 2 4 3 2 3 4 2 1

105. LỊCH SỬA CHỮA Ô TÔ^{meo nho – 10test}

Một cơ sở sửa chữa ô tô có nhận n chiếc xe để sửa. Do các nhân viên làm việc quá lười nhác nên đã đến hạn trả cho khách hàng mà vẫn chưa tiến hành sửa được chiếc xe nào. Theo hợp đồng đã ký kết từ trước, nếu bàn giao xe thứ i quá hạn ngày nào thì sẽ phải trả thêm một khoản tiền phạt là a_i.

Ông chủ cơ sở sửa chữa quyết định sa thải toàn bộ công nhân và thuê nhân công mới. Với lực lượng mới này, ông ta dự định rằng để sửa chiếc xe thứ i sẽ cần b_i ngày. Vấn đề đặt ra đối với ông là phải lập lịch sửa tuần tự các chiếc xe sao cho tổng số tiền bị phạt là ít nhất.

Yêu cầu: Hãy lập lịch sửa xe giúp cho ông chủ cơ sở sửa chữa ô tô.
Dữ liệu: Vào từ file văn bản SCHEDULE.INP

• 
  Dòng 1: Chứa số n (n  10000)
  
• 
  Dòng 2: Chứa n số nguyên dương a₁, a₂, ..., a_n (1  a_i  10000)
  
• 
  Dòng 3: Chứa n số nguyên dương b₁, b₂, ..., b_n (1  b_i  100)
  

Kết quả: Ghi ra file văn bản SCHEDULE.OUT

• 
  Dòng 1: Ghi số tiền bị phạt tối thiểu
  
• 
  Dòng 2: Ghi số hiệu các xe sẽ tiến hành sửa chữa, theo thứ tự từ xe được sửa đầu tiên đến xe sửa sau cùng
  

Ví dụ:

SCHEDULE.INP		SCHEDULE.OUT
4 1 3 4 2 3 2 3 1		44 4 2 3 1

Tiền phạt:

Xe 4: Muộn 1 (ngày) x 2 = 2

Xe 2: Muộn 3 (ngày) x 3 = 9

Xe 3: Muộn 6 (ngày) x 4 = 24

Xe 1: Muộn 9 (ngày) x 1 = 9

----------------------------

Tổng cộng = 44
Nếu sửa theo thứ tự 1, 2, 3, 4 thì:

Xe 1: Muộn 3 (ngày) x 1 = 3

Xe 2: Muộn 5 (ngày) x 3 = 15

Xe 3: Muộn 8 (ngày) x 4 = 32

Xe 4: Muộn 9 (ngày) x 2 = 18

----------------------------

Tổng cộng = 68

Каталог: Portals
Portals -> Phan Chau Trinh High School one period test no 2 Name: English : 11- time : 45 minutes Class: 11/ Code: 211 Chọn từ hoặc cụm từ thích hợp A, B, C, d để điền vào chỗ trống trong đoạn văn sau
Portals -> PHẦn I: thông tin cơ BẢn về ĐẠi hàn dân quốc và quan hệ việt nam-hàn quốc I- các vấN ĐỀ chung
Portals -> Năng suất lao động trong nông nghiệp: Vấn đề và giải pháp Giới thiệu
Portals -> LẤy ngưỜi học làm trung tâM
Portals -> BÀi tậP Ôn lưu huỳnh hợp chất lưu huỳnh khí sunfurơ so
Portals -> TỜ trình về việc ban hành mức thu phí tham gia đấu giá quyền sử dụng đất
Portals -> CỘng hòa xã HỘi chủ nghĩa việt nam độc lập – Tự do – Hạnh phúc
Portals -> GIẤY Ủy quyền tham dự Đại hội đồng Cổ đông thường niên năm 2016

tải về 438.29 Kb.

Chia sẻ với bạn bè của bạn: