HƯỚNG DẪN VIÊN DU LỊCH

Ông G là một hướng dẫn viên du lịch. Công việc của ông ta là hướng dẫn một vài “tua” du lịch từ thành phố này đến thành phố khác. Trên các thành phố này, có một vài con đường hai chiều được nối giữa chúng. Mỗi cặp thành phố có đường kết nối đều có dịch vụ xe buýt chỉ chạy giữa hai thành phố này và chạy theo đường nối trực tiếp giữa chúng. Mỗi dịch vụ xe buýt đều có một giới hạn lớn nhất lượng khách mà xe buýt có thể trở được. Ông G có một tấm bản đồ chỉ các thành phố và những con đường nối giữa chúng. Ngoài ra, ông ta cũng có thông tin về mỗi dịch vụ xe buýt giữa các thành phố. Ông hiểu rằng ông không thể đưa tất cả các khách du lịch đến thành phố thăm quan trong cùng một chuyến đi. Lấy ví dụ: Về bản đồ gồm 7 thành phố, mỗi cạnh được nối giữa các thành phố biểu thị những con đường và các số viết trên mỗi cạnh cho biết cho biết giới hạn hành khách của dịch vụ xe buýt chạy trên tuyến đường đó.

Bây giờ, nếu ông G muốn đưa 99 khách du lịch từ thành phố 1 đến thành phố 7. Ông ta sẽ phải yêu cầu ít nhất là 5 chuyến đi, và lộ trình ông ta nên đi là 1 – 2 – 4 – 7.

Nhưng, Ông G. nhận thấy là thật khó để tìm ra tất cả lộ trình tốt nhất để sao cho ông ta có thể đưa tất cả khách du lịch đến thành phố thăm quan với số chuyến đi là nhỏ nhất. Do vậy mà ông ta cần sự trợ giúp của các bạn.

Dữ liệu vào: từ tệp văn bản TOURIST.INP

- Dòng đầu tiên chứa hai số nguyên N (N ≤ 1000) và R mô tả lần lượt số thành phố và số đường đi giữa các thành phố.

- R dòng tiếp theo, mỗi dòng chứa 3 số nguyên: C1, C2, P. Trong đó C1, C2 mô tả lộ trình đường đi từ thành phố C1 đến thành phố C2 và P (P > 1) là giới hạn lớn nhất có thể phục vụ của dịch vụ xe buýt giữa hai thành phố.

Các thành phố được đánh dấu bằng một số nguyên từ 1 đến N. Dòng thứ (R+1) chứa ba số nguyên S, D, T mô tả lần lượt thành phố khởi hành, thành phố cần đến và số khách du lịch được phục vụ.

Kết quả ra: ghi vào tệp văn bản TOURIST.OUT

Ghi ra số lộ trình nhỏ nhất cần phải đi qua các thành phố thỏa mãn yêu cầu đề bài.

Ví dụ:

TOURIST.INP	TOURIST.OUT
7 10 1 2 30 1 3 15 1 4 10 2 4 25 2 5 60 3 4 40 3 6 20 4 7 35 5 7 20 6 7 30 1 7 99	5

TEST - CODE

QBBUILD

Nguồn: http://www.vn.spoj.com/problems/QBBUILD

Vua Peaceful vừa khai hoang một vùng đất để lập ra nước Peace, lúc đầu chỉ có N thành phố được đánh số từ 1 đến N và không có con đường nào

Vua Peace chọn ra 4 thành phố đặc biệt để làm trung tâm kinh tế và 4 thành phố này phải được liên thông với nhau. Chi phí xây dựng các con đường không phải nhỏ vì thế mà nhà cua muốn sử dụng chi phí ít nhất để xây dựng các con đường sao cho 4 thành phố đặc biệt đó vẫn liên thông

Bạn chỉ biết chi phí ước tính để xây dựng một số con đường và bạn hãy chọn ra một số con đường để xây dựng theo ý muốn của nhà vua biết rằng luôn luôn tồn tại ít nhất một phương án xây dựng sao cho 4 thành phố đặc biệt liên thông

Dữ liệu vào: từ file QBBUILD.INP

+ Dòng đầu tiên ghi số nguyên dương N là số lượng các thành phố (4≤N≤100)

+ Dòng thứ hai ghi 4 số nguyên là số hiệu của 4 thành phố đặc biệt

+ Trong các dòng tiếp theo mỗi dòng ghi 3 số nguyên dương u, v và c với ý nghĩa muốn xây dựng một con đường hai chiều nối trực tiếp hai thành phố u và v thì chi phí là c (1≤c≤5000);

Dữ liệu ra: ghi vào file QBBUILD.OUT gồm 1 dòng duy nhất là tổng chi phí nhỏ nhất để xây dựng hệ thống đường

Ví dụ:

QBBUILD.INP	QBBUILD.OUT
5 2 3 4 1 1 2 10 1 5 1 5 2 1 1 4 1 4 3 3 3 2 2	5

 TEST - CODE - SOLUTION

ÔNG NGÂU BÀ NGÂU

Hẳn các bạn đã biết ngày "ông Ngâu bà Ngâu" hàng năm, đó là một ngày đầy mưa và nước mắt. Tuy nhiên, một ngày trước đó, nhà Trời cho phép 2 "ông bà" được đoàn tụ. Trong vũ trụ vùng thiên hà nơi ông Ngâu bà Ngâu ngự trị có N hành tinh đánh số từ 1 đến N, ông ở hành tinh Adam (có số hiệu là S) và bà ở hành tinh Eva (có số hiệu là T). Họ cần tìm đến gặp nhau.

N hành tinh được nối với nhau bởi một hệ thống cầu vồng. Hai hành tinh bất kỳ chỉ có thể không có hoặc duy nhất một cầu vồng (hai chiều) nối giữa chúng. Họ luôn đi tới mục tiêu theo con đường ngắn nhất. Họ đi với tốc độ không đổi và nhanh hơn tốc độ ánh sáng. Điểm gặp mặt của họ chỉ có thể là tại một hành tinh thứ 3 nào đó.

Yêu cầu: Hãy tìm một hành tinh sao cho ông Ngâu và bà Ngâu cùng đến đó một lúc và thời gian đến là sớm nhất. Biết rằng, hai người có thể cùng đi qua một hành tinh nếu như họ đến hành tinh đó vào những thời điểm khác nhau.

Dữ liệu vào: từ tệp văn bản NGAU.INP gồm

Dòng đầu là 4 số N M S T (N ≤ 1000, 1 ≤ S ≠ T ≤ N), M là số cầu vồng. M dòng tiếp, mỗi dòng gồm ba số I J L thể hiện có cầu vồng nối giữa hai hành tinh I, J và cầu vồng có độ dài là L (1 ≤ I ≠ J ≤ N, 0 < L ≤ 200).

Dữ liệu ra: ghi vào tệp văn bản NGAU.OUT, nếu như không tồn tại hành tinh nào thoả mãn yêu cầu thì ghi ra một dòng chữ CRY. Nếu có nhiều hành tinh thoả mãn thì ghi ra hành tinh có chỉ số nhỏ nhất.

Ví dụ:

NGAU.INP	NGAU.OUT
4 4 1 4 1 2 1 2 4 1 1 3 2 3 4 2	2

 TEST

CHUỖI ỐC

Nguồn: PreVOI

Biển Đà Nẵng được nhiều du khách biết đến như một trong những điểm nghỉ ngơi lý tưởng và được tạp chí Forbes (Mỹ) bình chọn là một trong những bãi biển đẹp nhất thế giới. Các bãi tắm có độ dốc lớn, nước trong xanh thích hợp cho những du khách muốn thưởng thức những loại hình dịch vụ giải trí nghỉ dưỡng câu cá, lướt ván, lặn, ngắm san hô…

Trong một đợt đi du lịch ở Đà Nẵng, sáng sớm DONG3D thường đi dạo dọc bờ biển và nhặt những vỏ ốc rồi xâu chúng lại thành một chuỗi. Nguyên tắc tạo chuỗi ốc của DONG3D như sau: ban đầu chuỗi ốc rỗng, không có vỏ ốc, khi gặp một vỏ ốc mới có thể lấy để xâu vào 1 trong hai đầu của chuỗi hoặc bỏ đi không lấy, cuối cùng nhận được một chuỗi vỏ ốc mà tính từ đầu đến cuối chuỗi các vỏ ốc có kích thước tăng dần và gồm càng nhiều vỏ ốc càng tốt.

Yêu cầu: cho trước dãy a₁, a₂,…,a_N là kích thước các vỏ ốc mà DONG3D lần lượt gặp khi đi dọc bờ biển, hãy tìm cách nhặt và xâu chuỗi để được nhiều vỏ ốc nhất.

Dữ liệu vào: từ tệp văn bản BEADS.INP

+ Dòng đầu tiên ghi số nguyên dương N≤10⁵

+ Dòng thứ 2 chứa N số nguyen dương a₁, a₂,…,a_N ("i:a_i≤10⁹)

Dữ liệu ra: ghi vào tệp văn bản BEADS.OUT một số nguyên duy nhất là số lượng vỏ ốc trong chuỗi tạo được.

Ví dụ:

BEADS.INP	BEADS.OUT
5 4 4 5 3 1	4

TEST - SOLUTION

QUAN HỆ HỌ HÀNG

DÂY DẪN

TÌM CHỮ SỐ

Xét biểu diễn thập phân của phân số a/b. Biểu diễn này có thể là một số thập phân hữu hạn hoặc một số thập phân vô hạn tuần hoàn. Nếu phân số có thể biểu diễn bởi một số thập phân hữu hạn, ta có thể viết thêm một dãy vô hạn các chữ số 0 vào sau chữ số cuối cùng sau dấu chấm thập phân và coi đó cũng là một số thập phân vô hạn tuần hoàn. Ví dụ:

Yêu cầu: Sau khi đánh số từ 1 trở đi, từ trái qua phải các chữ số đứng sau dấu “,” trong biểu diễn thập phân của a/b, hãy xác định chữ số thứ k.

Ví dụ:

+ Với a=100, b=8, k=2, chữ số đứng thứ 2 sau dấu thập phân của giá trị 100/8  là chữ số 0

+ Với a=99, b=140, k=12, chữ số đứng thứ 12 sau dấu chấm thập phân giá trị 99/140 là chữ số 2

Dữ liệu: Vào từ tệp văn bản DIGIT.INP gồm 1 dòng chứa 3 số nguyên dương a, b, k<= 10^18 cách nhau ít nhất một ký tự trắng.

Kết quả: Ghi ra tệp văn bản DIGIT.OUT một số nguyên duy nhất là giá trị chữ số tìm được

Ví dụ:

DIGIT.INP	DIGIT.OUT
100 8 1	5
17 3 10	6
99 140 12	2