| # | Bài tập | Điểm | Thời gian: | Giới hạn bộ nhớ |
|---|---|---|---|---|
| 1 | USACO 2013 - Cow Race | 100 (p) | 4.0s | 512M |
| 2 | USACO 2013 - Breed Proximity | 100 (p) | 4.0s | 512M |
| 3 | Crush | 100 (p) | 2.0s | 512M |
Để cuối cùng giải quyết cuộc tranh cãi dai dẳng về việc ai là con bò chạy nhanh hơn, Bessie và người bạn Elsie quyết định tổ chức một cuộc đua xuyên trang trại.
Hai con bò xuất phát tại cùng một vị trí và bắt đầu chạy cùng một hướng vào cùng một thời điểm. Quá trình chạy của mỗi con bò được mô tả bởi một chuỗi các "chặng", trong mỗi chặng con bò chạy với vận tốc không đổi. Ví dụ, Bessie có thể chạy với vận tốc 5 trong 3 đơn vị thời gian, sau đó chạy với vận tốc 10 trong 6 đơn vị thời gian. Bessie và Elsie đều chạy trong cùng một tổng thời gian.
Hai con bò muốn bạn giúp đếm số lần vị trí dẫn đầu thay đổi trong cuộc đua. Một lần thay đổi vị trí dẫn đầu xảy ra tại thời điểm bò A vượt lên dẫn trước bò B, trong khi ở lần gần nhất có một con bò dẫn đầu thì đó là bò B. Ví dụ, nếu B đang dẫn đầu rồi A vượt lên trước thì đây là một lần thay đổi vị trí dẫn đầu. Nếu B đang dẫn đầu, sau đó A ngang bằng với B trong một khoảng thời gian rồi cuối cùng vượt lên trước thì điều này cũng được tính là một lần thay đổi vị trí dẫn đầu.
Dòng đầu tiên chứa hai số nguyên \(N\) và \(M\) cách nhau bởi dấu cách (\(1 \le N, M \le 1000\)).
\(N\) dòng tiếp theo, mỗi dòng chứa một trong \(N\) chặng chạy của Bessie, được mô tả bởi hai số nguyên: vận tốc của Bessie và khoảng thời gian cô chạy với vận tốc đó. Cả hai số nguyên đều nằm trong khoảng từ 1 đến 1000.
\(M\) dòng tiếp theo, mỗi dòng chứa một trong \(M\) chặng chạy của Elsie, được mô tả bởi hai số nguyên: vận tốc của Elsie và khoảng thời gian cô chạy với vận tốc đó. Cả hai số nguyên đều nằm trong khoảng từ 1 đến 1000.
In ra số lần vị trí dẫn đầu thay đổi trong cuộc đua.
Ví dụ 1
4 3
1 2
4 1
1 1
2 10
2 3
1 2
3 92Bessie chạy với vận tốc 1 trong 2 đơn vị thời gian, sau đó với vận tốc 4 trong 1 đơn vị thời gian, tiếp theo với vận tốc 1 trong 1 đơn vị thời gian và cuối cùng với vận tốc 2 trong 10 đơn vị thời gian. Elsie chạy với vận tốc 2 trong 3 đơn vị thời gian, sau đó với vận tốc 1 trong 2 đơn vị thời gian và cuối cùng với vận tốc 3 trong 9 đơn vị thời gian. Lưu ý rằng cả hai con bò đều chạy trong tổng cộng 14 đơn vị thời gian.
Elsie dẫn trước cho tới thời điểm \(t=3\), khi hai con bò gặp nhau sau khi mỗi con đã đi được tổng quãng đường 6 đơn vị, rồi chạy cùng nhau trong 1 đơn vị thời gian. Sau đó Bessie vượt lên dẫn trước trong một khoảng ngắn (lần thay đổi vị trí dẫn đầu thứ nhất), nhưng không lâu sau lại bị Elsie vượt qua (lần thay đổi vị trí dẫn đầu thứ hai). Elsie kết thúc cuộc đua ở vị trí dẫn đầu.
USACO 2013 March Contest, Bronze — Problem 1: Cow Race
Tác giả đề: Brian Dean, 2013.
\(N\) con bò của Farmer John (\(1 \le N \le 50\,000\)) đang đứng thành một hàng, mỗi con được mô tả bởi một mã giống là số nguyên.
Những con bò cùng giống có nguy cơ cãi nhau nếu đứng quá gần nhau. Cụ thể, hai con bò cùng giống được gọi là "chen chúc" nếu vị trí của chúng trong hàng chênh nhau không quá \(K\) (\(1 \le K < N\)).
Hãy tính mã giống lớn nhất của một cặp bò chen chúc.
Dòng đầu tiên chứa hai số nguyên \(N\) và \(K\), cách nhau bởi dấu cách.
\(N\) dòng tiếp theo, mỗi dòng chứa mã giống của một con bò trong hàng. Tất cả mã giống đều là số nguyên trong khoảng từ 0 đến \(1\,000\,000\).
In ra mã giống lớn nhất của một cặp bò chen chúc, hoặc \(-1\) nếu không có cặp bò chen chúc nào.
Ví dụ 1
6 3
7
3
4
2
3
44Có 6 con bò đứng thành một hàng, với các mã giống 7, 3, 4, 2, 3 và 4. Hai con bò có mã giống bằng nhau được coi là chen chúc nếu vị trí của chúng chênh nhau không quá 3.
Cặp bò có mã giống 3 chen chúc, và cặp bò có mã giống 4 cũng vậy.
USACO 2013 March Contest, Bronze — Problem 2: Breed Proximity
Tác giả đề: Brian Dean, 2013.
Lớp ITK19 có \(n\) học sinh nam, mỗi học sinh nam này đều crush đúng một trong ba bạn nữ: Oanh Trúc, Hương An và Tuyết Ny. Hoàng Hải từng khai thác hết thông tin crush-ship của từng bạn nam trong \(n\) bạn này và ghi chép hết chúng vào một cuốn sổ tay. Thật không may, Hải vừa đánh mất cuốn sổ của mình và rất tiếc nuối các thông tin quý giá mà mình đã dày công sưu tầm. Anh ấy chỉ còn nhớ đúng \(m\) thông tin: mỗi thông tin có dạng S u v hoặc D u v, trong đó, S u v đồng nghĩa với việc học sinh \(u\) và học sinh \(v\) cùng crush chung một người, còn D u v thể hiện rằng \(u\) và \(v\) crush hai người khác nhau.
Hải cho bạn biết \(m\) thông tin đó và nhờ bạn lập trình tính toán giúp có bao nhiêu trạng thái crush-ship thỏa mãn các ràng buộc mà anh đã nêu ra. Hãy giúp Hải nhé!
S u v hoặc D u v thể hiện một ràng buộc tương ứng.Test 1
4 2
S 1 2
D 1 318Có \(6\) trạng thái hợp lệ cho ba học sinh đầu (T tượng trưng cho Oanh Trúc, A tượng trưng cho Hương An và N tượng trưng cho Tuyết Ny): TTA, TTN, AAT, AAN, NNT và NNA. Ở mỗi trạng thái trong \(6\) trạng thái trên lại có \(3\) cách chọn crush cho học sinh thứ tư, vì vậy tổng số trạng thái thỏa mãn là \(6\cdot 3=18\).