| # | Bài tập | Điểm | Thời gian: | Giới hạn bộ nhớ |
|---|---|---|---|---|
| 1 | USACO 2019 - Cow Poetry | 100 (p) | 4.0s | 512M |
| 2 | USACO 2019 - Sleepy Cow Sorting | 100 (p) | 4.0s | 512M |
| 3 | USACO 2019 - Shortcut | 100 (p) | 4.0s | 512M |
Farmer John không hề hay biết rằng Bessie là một người rất yêu nghệ thuật! Gần đây nhất, cô bắt đầu nghiên cứu tác phẩm của nhiều nhà thơ vĩ đại, và giờ cô muốn thử tự sáng tác thơ.
Bessie biết \(N\) từ (\(1 \leq N \leq 5000\)) và muốn sắp xếp chúng thành những bài thơ. Bessie đã xác định độ dài tính theo số âm tiết của mỗi từ, đồng thời phân chúng vào các "lớp vần". Mỗi từ chỉ vần với những từ khác thuộc cùng lớp vần.
Mỗi bài thơ của Bessie gồm \(M\) dòng (\(1 \leq M \leq 10^5\)), và mỗi dòng phải có \(K\) âm tiết (\(1 \leq K \leq 5000\)). Hơn nữa, thơ của Bessie phải tuân theo một sơ đồ gieo vần cụ thể.
Bessie muốn biết cô có thể viết bao nhiêu bài thơ khác nhau thỏa mãn các ràng buộc đã cho.
Dòng đầu tiên chứa \(N\), \(M\) và \(K\).
Mỗi dòng trong \(N\) dòng tiếp theo chứa hai số \(s_i\) (\(1 \leq s_i \leq K\)) và \(c_i\) (\(1 \leq c_i \leq N\)). Điều này cho biết Bessie biết một từ có độ dài \(s_i\) âm tiết và thuộc lớp vần \(c_i\).
\(M\) dòng cuối cùng mô tả sơ đồ gieo vần mà Bessie mong muốn, mỗi dòng chứa một chữ cái in hoa \(e_i\). Tất cả các dòng ứng với cùng một giá trị \(e_i\) phải kết thúc bằng những từ thuộc cùng một lớp vần. Các dòng có giá trị \(e_i\) khác nhau không nhất thiết phải kết thúc bằng những từ thuộc các lớp vần khác nhau.
In ra số bài thơ Bessie có thể viết thỏa mãn các ràng buộc này. Vì số này có thể rất lớn, hãy tính kết quả theo modulo \(1\,000\,000\,007\).
Ví dụ 1
3 3 10
3 1
4 1
3 2
A
B
A960Trong ví dụ này, Bessie biết ba từ. Hai từ đầu tiên vần với nhau và có độ dài lần lượt là ba âm tiết và bốn âm tiết; từ cuối cùng dài ba âm tiết và không vần với hai từ còn lại. Cô muốn viết một bài thơ ba dòng sao cho mỗi dòng có mười âm tiết và dòng đầu tiên vần với dòng cuối cùng. Có \(960\) bài thơ như vậy. Sau đây là một ví dụ về bài thơ hợp lệ (trong đó \(1\), \(2\) và \(3\) lần lượt biểu diễn từ thứ nhất, thứ hai và thứ ba): 121 123 321.
Đề bài gốc: USACO 2019 January Contest, Gold — Cow Poetry
Tác giả: Jay Leeds
Farmer John đang cố gắng sắp xếp \(N\) con bò của mình (\(1 \leq N \leq 10^5\)), được đánh số thuận tiện từ \(1 \dots N\), trước khi chúng ra đồng cỏ ăn sáng.
Hiện tại, các cô bò đang đứng thành một hàng theo thứ tự \(p_1, p_2, p_3, \dots, p_N\), còn Farmer John đứng trước cô bò \(p_1\). Ông muốn sắp xếp lại để các cô bò có thứ tự \(1, 2, 3, \dots, N\), trong đó cô bò \(1\) đứng cạnh Farmer John.
Hôm nay các cô bò hơi buồn ngủ, nên tại bất kỳ thời điểm nào, cô bò duy nhất chú ý đến chỉ dẫn của Farmer John là cô đứng ngay trước mặt ông. Trong một bước thời gian, ông có thể yêu cầu cô bò này di chuyển xuống dưới hàng \(k\) vị trí, với \(k\) bất kỳ từ \(1\) đến \(N-1\), kể cả hai đầu mút. \(k\) cô bò mà cô ấy đi qua sẽ chậm rãi tiến lên phía trước, tạo chỗ để cô ấy chen vào hàng ngay sau họ.
Ví dụ, giả sử \(N=4\) và ban đầu các cô bò đứng theo thứ tự sau:
FJ: 4, 3, 2, 1
Cô bò duy nhất đang chú ý đến FJ là cô bò \(4\). Nếu ông yêu cầu cô ấy di chuyển xuống dưới hàng \(2\) vị trí, thứ tự sau đó sẽ là:
FJ: 3, 2, 4, 1
Lúc này cô bò duy nhất đang chú ý đến FJ là cô bò \(3\), nên ở bước thời gian thứ hai ông có thể đưa ra chỉ dẫn cho cô bò \(3\), và cứ tiếp tục như vậy cho đến khi các cô bò được sắp xếp xong.
Farmer John nóng lòng hoàn thành việc sắp xếp để có thể trở về trang trại ăn sáng. Hãy giúp ông tìm một dãy chỉ dẫn sắp xếp các cô bò trong số bước thời gian tối thiểu.
Dòng đầu tiên chứa \(N\). Dòng thứ hai chứa \(N\) số nguyên cách nhau bởi dấu cách: \(p_1, p_2, p_3, \dots, p_N\), cho biết thứ tự ban đầu của các cô bò.
Dòng đầu tiên chứa một số nguyên duy nhất \(K\), là số bước thời gian tối thiểu cần thiết để sắp xếp các cô bò.
Dòng thứ hai chứa \(K\) số nguyên cách nhau bởi dấu cách, \(c_1, c_2, \dots, c_K\), mỗi số thuộc khoảng \(1 \ldots N-1\). Hơn nữa, nếu ở bước thời gian thứ \(i\), FJ yêu cầu cô bò đứng trước mặt mình di chuyển xuống dưới hàng \(c_i\) vị trí, thì sau \(K\) bước thời gian, các cô bò phải ở đúng thứ tự.
Nếu có nhiều dãy chỉ dẫn tối ưu, chương trình có thể in ra bất kỳ dãy nào trong số đó.
Ví dụ 1
4
1 2 4 33
2 2 3Đề bài gốc: USACO 2019 January Contest, Gold — Sleepy Cow Sorting
Tác giả: Dhruv Rohatgi
Mỗi tối, Farmer John rung một chiếc chuông khổng lồ để gọi các cô bò về chuồng ăn tối. Vì mong muốn đến chuồng nhanh nhất có thể, tất cả chúng đều đi theo lộ trình ngắn nhất có thể để đến đó.
Trang trại được mô tả bởi một tập gồm \(N\) cánh đồng (\(1 \leq N \leq 10\,000\)), được đánh số thuận tiện từ \(1 \ldots N\), trong đó chuồng nằm ở cánh đồng \(1\). Các cánh đồng được nối bởi một tập gồm \(M\) đường mòn hai chiều (\(N-1 \leq M \leq 50\,000\)). Mỗi đường mòn có một thời gian di chuyển tương ứng, và từ mọi cánh đồng đều có đường đi đến chuồng qua một số đường mòn.
Cánh đồng \(i\) có \(c_i\) con bò. Khi nghe tiếng chuông báo bữa tối, tất cả những con bò này đi đến chuồng theo một lộ trình có tổng thời gian nhỏ nhất. Nếu có nhiều lộ trình cùng đạt thời gian nhỏ nhất, các cô bò chọn lộ trình "nhỏ nhất theo thứ tự từ điển" (nghĩa là khi phá vỡ thế hòa giữa hai lộ trình, chúng ưu tiên lộ trình sử dụng cánh đồng có chỉ số nhỏ hơn tại vị trí đầu tiên mà hai lộ trình khác nhau; chẳng hạn, một đường đi qua các cánh đồng \(7, 3, 6, 1\) sẽ được ưu tiên hơn một đường đi qua \(7, 5, 1\), giả sử cả hai có cùng thời gian di chuyển).
Farmer John lo ngại chuồng nằm quá xa một số cánh đồng. Ông cộng thời gian di chuyển của từng con bò trên toàn bộ đàn và gọi kết quả là tổng thời gian di chuyển. Ông muốn giảm con số này nhiều nhất có thể bằng cách thêm một đường mòn "đường tắt" có thời gian di chuyển \(T\) (\(1 \leq T \leq 10\,000\)), nối từ chuồng (cánh đồng \(1\)) đến một cánh đồng khác do ông lựa chọn. Nếu một cô bò bắt gặp đường tắt khi đang đi theo lộ trình thông thường đến chuồng, cô sẽ sử dụng nó nếu nhờ đó đến chuồng nhanh hơn. Nếu không, cô bò sẽ tiếp tục đi theo lộ trình thông thường, ngay cả khi có thể sử dụng đường tắt theo cách khác để cải thiện thời gian di chuyển.
Hãy giúp Farmer John xác định mức giảm tổng thời gian di chuyển lớn nhất có thể đạt được bằng cách thêm đường tắt.
Dòng đầu tiên chứa \(N\), \(M\) và \(T\). Dòng tiếp theo chứa \(N\) số nguyên \(c_1 \ldots c_N\), mỗi số nằm trong khoảng \(0 \ldots 10\,000\). Mỗi dòng trong \(M\) dòng tiếp theo mô tả một đường mòn bằng ba số nguyên \(a\), \(b\) và \(t\), trong đó đường mòn nối hai cánh đồng \(a\), \(b\) và có thời gian di chuyển \(t\). Mọi thời gian di chuyển đều nằm trong khoảng \(1 \ldots 25\,000\).
In ra mức giảm tổng thời gian di chuyển lớn nhất mà Farmer John có thể đạt được.
Ví dụ 1
5 6 2
1 2 3 4 5
1 2 5
1 3 3
2 4 3
3 4 5
4 5 2
3 5 740Đề bài gốc: USACO 2019 January Contest, Gold — Shortcut
Tác giả: Brian Dean