| # | Bài tập | Điểm | Thời gian: | Giới hạn bộ nhớ |
|---|---|---|---|---|
| 1 | USACO 2015 - Cow Routing | 100 (p) | 4.0s | 512M |
| 2 | USACO 2015 - Cow Routing II | 100 (p) | 4.0s | 512M |
| 3 | USACO 2015 - It's All About the Base | 100 (p) | 4.0s | 512M |
| 4 | Thời điểm gặp mặt | 100 (p) | 1.0s | 256M |
Mệt mỏi vì thời tiết mùa đông lạnh giá ở trang trại, cô bò Bessie dự định bay đến một nơi ấm áp hơn để nghỉ dưỡng. Đáng tiếc, cô phát hiện ra rằng chỉ có một hãng hàng không, Air Bovinia, sẵn lòng bán vé cho bò, và cấu trúc của những tấm vé này lại khá phức tạp.
Air Bovinia sở hữu \(N\) máy bay (\(1 \le N \le 500\)), mỗi chiếc bay theo một "tuyến" cố định gồm hai thành phố trở lên. Chẳng hạn, một máy bay có thể bay theo tuyến bắt đầu tại thành phố 1, sau đó đến thành phố 5, tiếp theo đến thành phố 2 và cuối cùng đến thành phố 8. Không thành phố nào xuất hiện nhiều lần trên một tuyến. Nếu Bessie chọn sử dụng một tuyến, cô có thể lên máy bay tại bất kỳ thành phố nào trên tuyến rồi xuống tại bất kỳ thành phố nào nằm sau đó trên tuyến. Cô không nhất thiết phải lên tại thành phố đầu tiên hay xuống tại thành phố cuối cùng. Mỗi tuyến có một chi phí nhất định mà Bessie phải trả nếu sử dụng bất kỳ phần nào của tuyến, bất kể cô đi qua bao nhiêu thành phố trên tuyến đó.
Bessie muốn tìm cách rẻ nhất để đi từ trang trại của mình (ở thành phố \(A\)) đến điểm đến nhiệt đới (thành phố \(B\)). Vì không muốn bị rối bởi một hành trình phức tạp, cô chỉ muốn sử dụng đúng một tuyến. Hãy giúp cô xác định chi phí tối thiểu phải trả.
Dòng đầu tiên chứa \(A\), \(B\) và \(N\), cách nhau bởi dấu cách.
\(2N\) dòng tiếp theo mô tả các tuyến hiện có, mỗi tuyến bằng hai dòng. Dòng đầu tiên chứa chi phí sử dụng tuyến (một số nguyên trong đoạn \(1\ldots1000\)) và số thành phố trên tuyến (một số nguyên trong đoạn \(1\ldots500\)). Dòng thứ hai chứa danh sách các thành phố theo thứ tự trên tuyến. Mỗi thành phố được xác định bằng một số nguyên trong đoạn \(1\ldots10\,000\).
In chi phí nhỏ nhất của một tuyến duy nhất mà Bessie có thể sử dụng để đi từ thành phố \(A\) đến thành phố \(B\). Nếu không có tuyến nào như vậy, in -1.
Ví dụ 1
1 2 3
3 3
3 2 1
4 4
2 1 4 3
8 5
4 1 7 8 28Mặc dù có một phương án rẻ hơn dùng hai tuyến (dùng tuyến 2 để đi từ thành phố 1 đến thành phố 3, rồi dùng tuyến 1 để đi từ thành phố 3 đến thành phố 2), Bessie chỉ được phép dùng một tuyến duy nhất, vì vậy cô phải dùng tuyến 3 với chi phí 8.
USACO 2015 January Contest, Bronze - Cow Routing: https://usaco.org/index.php?page=viewproblem2&cpid=507
Tác giả: Richard Peng, 2015.
Mệt mỏi vì thời tiết mùa đông lạnh giá ở trang trại, cô bò Bessie dự định bay đến một nơi ấm áp hơn để nghỉ dưỡng. Đáng tiếc, cô phát hiện ra rằng chỉ có một hãng hàng không, Air Bovinia, sẵn lòng bán vé cho bò, và cấu trúc của những tấm vé này lại khá phức tạp.
Air Bovinia sở hữu \(N\) máy bay (\(1 \le N \le 500\)), mỗi chiếc bay theo một "tuyến" cố định gồm hai thành phố trở lên. Chẳng hạn, một máy bay có thể bay theo tuyến bắt đầu tại thành phố 1, sau đó đến thành phố 5, tiếp theo đến thành phố 2 và cuối cùng đến thành phố 8. Không thành phố nào xuất hiện nhiều lần trên một tuyến. Nếu Bessie chọn sử dụng một tuyến, cô có thể lên máy bay tại bất kỳ thành phố nào trên tuyến rồi xuống tại bất kỳ thành phố nào nằm sau đó trên tuyến. Cô không nhất thiết phải lên tại thành phố đầu tiên hay xuống tại thành phố cuối cùng. Mỗi tuyến có một chi phí nhất định mà Bessie phải trả nếu sử dụng bất kỳ phần nào của tuyến, bất kể cô đi qua bao nhiêu thành phố trên tuyến đó. Bessie chỉ có thể sử dụng mỗi tuyến một lần (nghĩa là cô không thể dùng một tuyến rồi sau đó lại dùng một phần khác của chính tuyến ấy).
Bessie muốn tìm cách rẻ nhất để đi từ trang trại của mình (ở thành phố \(A\)) đến điểm đến nhiệt đới (thành phố \(B\)). Vì không muốn bị rối bởi một hành trình phức tạp, cô muốn sử dụng nhiều nhất hai tuyến. Hãy giúp cô xác định chi phí tối thiểu phải trả.
Lưu ý rằng điểm khác biệt duy nhất giữa bài này và bài Bronze ngay trước đó là trong bài này Bessie có thể sử dụng tối đa hai tuyến, thay vì chỉ một tuyến như trong bài trước.
Dòng đầu tiên chứa \(A\), \(B\) và \(N\), cách nhau bởi dấu cách.
\(2N\) dòng tiếp theo mô tả các tuyến hiện có, mỗi tuyến bằng hai dòng. Dòng đầu tiên chứa chi phí sử dụng tuyến (một số nguyên trong đoạn \(1\ldots1000\)) và số thành phố trên tuyến (một số nguyên trong đoạn \(1\ldots500\)). Dòng thứ hai chứa danh sách các thành phố theo thứ tự trên tuyến. Mỗi thành phố được xác định bằng một số nguyên trong đoạn \(1\ldots10\,000\).
In chi phí nhỏ nhất của một hành trình sử dụng nhiều nhất hai tuyến mà Bessie có thể dùng để đi từ thành phố \(A\) đến thành phố \(B\). Nếu không có phương án nào như vậy, in -1.
Ví dụ 1
1 2 3
3 3
3 2 1
4 4
2 1 4 3
8 5
4 1 7 8 27Dùng tuyến 2 để đi từ thành phố 1 đến thành phố 3, rồi dùng tuyến 1 để đi từ thành phố 3 đến thành phố 2.
USACO 2015 January Contest, Bronze - Cow Routing II: https://usaco.org/index.php?page=viewproblem2&cpid=508
Tác giả: Richard Peng và Brian Dean, 2015.
Cô bò Bessie đang theo học các lớp tin học tại trường cao đẳng địa phương (hay "cow-ledge" trong trường hợp của cô), và gần đây cô rất hào hứng khi học được cách viết các số trong những hệ cơ số khác nhau.
Hãy nhớ rằng một số viết trong hệ cơ số \(B\) có các hàng chữ số lần lượt biểu diễn \(1\), \(B\), \(B^2\), \(B^3\), v.v. từ phải sang trái. Chẳng hạn, trong hệ cơ số 10 quen thuộc, các chữ số lần lượt biểu diễn hàng đơn vị, hàng chục, hàng trăm, hàng nghìn, v.v. Dãy chữ số 1234 khi được hiểu trong hệ cơ số 10 thực chất có nghĩa là \(1(1000) + 2(100) + 3(10) + 4(1)\). Cũng dãy chữ số 1234 ấy, nếu được hiểu trong hệ cơ số 5, sẽ có nghĩa là \(1(125) + 2(25) + 3(5) + 4(1)\), tổng lại bằng số 194 trong hệ cơ số 10. Bessie nhận thấy rằng khi cơ số tăng, số được biểu diễn bởi một dãy chữ số cũng tăng theo — chẳng hạn, 1234 trong hệ cơ số 7 biểu diễn một số lớn hơn 1234 trong hệ cơ số 6.
Khi viết số trong hệ cơ số \(B\), mỗi chữ số có thể nhận giá trị từ 0 đến \(B-1\). Vì vậy, chẳng hạn trong hệ cơ số 10, mỗi chữ số nằm trong đoạn \(0\ldots9\), còn trong hệ cơ số 5, mỗi chữ số nằm trong đoạn \(0\ldots4\). Hoàn toàn có thể xét các cơ số lớn hơn 10. Các nhà khoa học máy tính thường dùng hệ cơ số 16 ("thập lục phân"), trong đó các chữ cái A đến F biểu diễn các chữ số có giá trị từ 10 đến 15. Chẳng hạn, BEEF trong hệ thập lục phân tương ứng với \(11(4096) + 14(256) + 14(16) + 15\), tổng lại bằng số 48879 trong hệ cơ số 10.
Bessie bị cuốn hút bởi ý tưởng sử dụng những cơ số lớn hơn 10 rất nhiều. Cô lấy một số \(N\) và viết nó trong hai hệ cơ số khác nhau \(X\) và \(Y\), trong đó cả \(X\) lẫn \(Y\) đều thuộc đoạn \(10\ldots15\,000\). Điều thú vị là trong cả hai trường hợp, cô đều nhận được một dãy gồm 3 chữ số, và mỗi chữ số tình cờ chỉ nằm trong đoạn \(1\ldots9\). Đáng tiếc, do trí nhớ kém, giờ đây Bessie đã quên mất \(N\), \(X\) và \(Y\)! Chỉ với hai dãy 3 chữ số mà cô đã viết ra, hãy giúp cô tìm lại hai cơ số \(X\) và \(Y\) đã sử dụng.
Lưu ý rằng do \(X\) và \(Y\) có thể rất lớn, một chương trình vét cạn mọi giá trị có thể của \(X\) và \(Y\) (gần \(15\,000^2\) khả năng!) sẽ không chạy kịp giới hạn thời gian, vì vậy sẽ không nhận được trọn vẹn số điểm.
Dữ liệu vào bắt đầu bằng một số nguyên \(K\), sau đó là \(K\) dòng, mỗi dòng mô tả một bộ test riêng biệt. Mỗi bộ test gồm hai số có 3 chữ số. Số đầu tiên là số \(N\) được viết trong hệ cơ số \(X\), còn số thứ hai là \(N\) được viết trong hệ cơ số \(Y\) (\(N\), \(X\) và \(Y\) có thể khác nhau giữa các bộ test).
Kết quả phải gồm \(K\) dòng, mỗi dòng ứng với một bộ test. Trên mỗi dòng, in hai số \(X\) và \(Y\) của bộ test tương ứng, cách nhau bởi một dấu cách. Dữ liệu bảo đảm mỗi bộ test có đúng một nghiệm.
Ví dụ 1
1
419 79247 35Số 8892 khi viết trong hệ cơ số 47 là 419. Khi viết trong hệ cơ số 35, nó là 792.
USACO 2015 January Contest, Bronze - It's All About the Base: https://usaco.org/index.php?page=viewproblem2&cpid=509
Tác giả: Brian Dean, 2015.
Quý và Hân đang lên kế hoạch đi chơi với nhau. Đất nước Wibuland nơi 2 bạn đang ở có \(N\) thành phố. Thành phố của 2 bạn hiện tại là thành phố \(1\), và 2 bạn quyết định sẽ bắt xe đến thành phố \(N\) để đi chơi. Không may, vì cả Hân và Quý đang hơi nghèo, nên hai bạn phải đặt 2 chiếc grab xe máy khác nhau để đi đến điểm hẹn.
Wibuland có \(M\) con đường nối các thành phố với nhau. Với mỗi con đường \(u-v\), xe máy chỉ được phép lưu thông nếu \(u < v\), do đó sẽ không thể đi hướng ngược lại (nếu muốn về nhà thì 2 bạn phải nghĩ cách khác, như là đi bộ). 2 chiếc xe grab mà Quý và Hân đặt khi đi trên mỗi đoạn đường có thể sẽ có thời gian đi khác nhau. Ví dụ, với đoạn đường 1-2 Quý sẽ mất 10 phút để đến nơi, nhưng Hân phải mất tận 20 phút. Tuy nhiên với đoạn đường 2-3, Quý sẽ mất 30 phút trong khi Hân chỉ mất 10 phút. Vì cả hai đều không muốn người kia phải đợi mình, Quý và Hân lập ra một lộ trình cho mỗi người để khi cùng xuất phát tại thành phố \(1\), hai người sẽ đến thành phố \(N\) cùng một lúc.
Vì đang háo hức được đi chơi nên cả Quý và Hân đều không thể tập trung nghĩ cách, bạn hãy giúp 2 bạn tính thời gian ngắn nhất để cả 2 có thể đến nơi cùng một lúc.
In ra 1 dòng duy nhất là thời gian ngắn nhất để Quý và Hân đến điểm hẹn cùng lúc. Nếu không có lộ trình đi thỏa mãn, in ra "IMPOSSIBLE".
INPUT
3 3
1 3 1 2
1 2 1 2
2 3 1 2
OUTPUT
2