| # | Bài tập | Điểm | Thời gian: | Giới hạn bộ nhớ |
|---|---|---|---|---|
| 1 | USACO 2017 - Don't Be Last! | 100 (p) | 4.0s | 512M |
| 2 | USACO 2017 - Hoof, Paper, Scissors | 100 (p) | 4.0s | 512M |
| 3 | USACO 2017 - Cow Tipping | 100 (p) | 4.0s | 512M |
Farmer John sở hữu \(7\) con bò sữa: Bessie, Elsie, Daisy, Gertie, Annabelle, Maggie và Henrietta. Mỗi ngày ông vắt sữa chúng và ghi chép chi tiết lượng sữa mà từng con bò cho trong mỗi lần vắt. Không có gì đáng ngạc nhiên khi Farmer John đặc biệt coi trọng những con bò cho nhiều sữa.
Vốn là những sinh vật lười biếng, đàn bò không nhất thiết muốn phải chịu trách nhiệm sản xuất quá nhiều sữa. Nếu được tự quyết định, mỗi con đều hoàn toàn hài lòng khi là con bò cho ít sữa nhất trong cả đàn. Tuy nhiên, chúng cứ nghe Farmer John nhắc đến cụm từ "từ nông trại đến bàn ăn" khi trò chuyện với những người bạn của ông. Dù không thực sự hiểu cụm từ ấy có nghĩa gì, chúng nghi rằng làm con bò cho ít sữa nhất có lẽ không phải ý hay. Thay vào đó, chúng cho rằng sẽ an toàn hơn nếu đứng ở vị trí có tổng lượng sữa ít thứ hai trong đàn. Hãy giúp đàn bò xác định con nào hiện đang giữ vị trí đáng mơ ước này.
Dòng đầu tiên chứa số nguyên \(N\) (\(1 \leq N \leq 100\)), là số mục trong nhật ký vắt sữa của Farmer John.
Mỗi dòng trong \(N\) dòng tiếp theo chứa tên của một con bò (một trong bảy tên nêu trên), theo sau là một số nguyên dương không quá \(100\), biểu thị lượng sữa con bò đó cho trong một lần vắt.
Con bò nào hoàn toàn không xuất hiện trong nhật ký được xem là đã cho \(0\) đơn vị sữa.
In trên một dòng tên của con bò có tổng lượng sữa ít thứ hai. Cụ thể hơn, gọi \(M\) là tổng lượng sữa nhỏ nhất mà một con bò bất kỳ cho được; hãy in tên con bò có tổng lượng sữa nhỏ nhất trong số tất cả những con cho nhiều hơn \(M\) đơn vị sữa. Nếu có nhiều con bò cùng giữ vị trí này, hoặc không có con bò nào giữ vị trí này (tức là mọi con bò đều có tổng lượng sữa bằng \(M\)), hãy in từ Tie. Đừng quên ký tự xuống dòng ở cuối dòng kết quả. Lưu ý rằng \(M=0\) nếu một trong bảy con bò hoàn toàn không xuất hiện trong nhật ký vắt sữa, vì con bò đó không cho đơn vị sữa nào.
Ví dụ 1
10
Bessie 1
Maggie 13
Elsie 3
Elsie 4
Henrietta 4
Gertie 12
Daisy 7
Annabelle 10
Bessie 6
Henrietta 5HenriettaTrong ví dụ này, Bessie, Elsie và Daisy cùng có tổng lượng sữa nhỏ nhất là \(7\) đơn vị. Mức sản lượng lớn hơn kế tiếp là \(9\) đơn vị, thuộc về Henrietta.
USACO 2017 January Contest, Bronze — Don't Be Last! Tác giả đề: Brian Dean.
Hẳn bạn đã từng nghe nói đến trò chơi "Oẳn tù tì" (Rock, Paper, Scissors). Đàn bò thích chơi một trò tương tự mà chúng gọi là "Móng guốc, Giấy, Kéo" (Hoof, Paper, Scissors).
Luật chơi "Móng guốc, Giấy, Kéo" rất đơn giản. Hai con bò đấu với nhau. Cả hai cùng đếm đến ba, rồi đồng thời ra một cử chỉ tượng trưng cho móng guốc, một tờ giấy hoặc một chiếc kéo. Móng guốc thắng kéo (vì móng guốc có thể đập nát kéo), kéo thắng giấy (vì kéo có thể cắt giấy), còn giấy thắng móng guốc (vì móng guốc có thể bị giấy cứa). Chẳng hạn, nếu con bò thứ nhất ra cử chỉ "móng guốc" và con thứ hai ra "giấy", con bò thứ hai sẽ thắng. Tất nhiên, hai bên cũng có thể hòa nếu cùng ra một cử chỉ.
Farmer John thích thú theo dõi hai con bò chơi một loạt \(N\) ván "Móng guốc, Giấy, Kéo" (\(1 \leq N \leq 100\)). Đáng tiếc là dù có thể thấy đàn bò ra ba loại cử chỉ khác nhau, ông không phân biệt được cử chỉ nào là "móng guốc", cử chỉ nào là "giấy" và cử chỉ nào là "kéo" (dưới con mắt thiếu kinh nghiệm của Farmer John, tất cả dường như chỉ là những biến thể của "móng guốc"...).
Vì không biết ý nghĩa của ba cử chỉ, Farmer John gán cho chúng các số \(1\), \(2\) và \(3\). Có thể cử chỉ \(1\) là "móng guốc", nhưng cũng có thể là "giấy"; ông không thể biết chắc. Dựa trên các cử chỉ mà hai con bò đã ra trong cả \(N\) ván, hãy giúp Farmer John xác định số ván lớn nhất mà con bò thứ nhất có thể đã thắng, ứng với một cách ánh xạ phù hợp từ các số sang ba cử chỉ tương ứng.
Dòng đầu tiên chứa \(N\).
Mỗi dòng trong \(N\) dòng còn lại chứa hai số nguyên (mỗi số là \(1\), \(2\) hoặc \(3\)), mô tả một ván đấu theo cách quan sát của Farmer John.
In số ván lớn nhất mà con bò thứ nhất trong hai con có thể đã thắng.
Ví dụ 1
5
1 2
2 2
1 3
1 1
3 22Một trong số nhiều cách gán phù hợp cho ví dụ này là để \(1\) biểu thị "kéo", \(2\) biểu thị "móng guốc" và \(3\) biểu thị "giấy". Cách gán này đem lại \(2\) chiến thắng cho con bò thứ nhất (ở các ván 1 3 và 3 2). Không có cách gán nào khác đem lại nhiều chiến thắng hơn.
USACO 2017 January Contest, Bronze — Hoof, Paper, Scissors. Tác giả đề: Brian Dean.
Farmer John thỉnh thoảng gặp rắc rối với những thiếu niên buồn chán đến trang trại vào ban đêm và xô ngã bò của ông. Một buổi sáng, ông tỉnh dậy và phát hiện chuyện đó lại xảy ra: \(N^2\) con bò của ông bắt đầu buổi tối bằng việc gặm cỏ theo một lưới vuông \(N \times N\) hoàn hảo (\(1 \leq N \leq 10\)), nhưng giờ đây một số con đã bị xô ngã.
May thay, Farmer John đã dùng các bộ phận từ máy kéo và xe nâng để chế tạo một cỗ máy tuyệt diệu mang tên Cow-Untipperator 3000, có thể lật cả nhóm bò lớn cùng lúc, giúp ông dựng tất cả bò đứng dậy nhanh nhất có thể. Ông có thể dùng máy lên bất kỳ "hình chữ nhật góc trên bên trái" nào trong lưới bò, tức là một lưới con hình chữ nhật chứa con bò ở góc trên bên trái. Khi đó, máy lật mọi con bò trong hình chữ nhật này, dựng những con đang ngã đứng dậy, nhưng không may cũng làm những con vốn đang đứng bị ngã! Nói cách khác, máy "đảo" trạng thái của từng con bò trong hình chữ nhật.
Farmer John nhận thấy rằng bằng cách sử dụng máy đủ nhiều lần trên một tập hợp hình chữ nhật thích hợp, cuối cùng ông có thể đưa tất cả bò trở lại trạng thái đứng đúng đắn. Hãy giúp ông xác định số lần sử dụng máy ít nhất cần thiết để làm điều đó.
Lưu ý rằng dùng máy hai lần trên cùng một hình chữ nhật là vô ích vì trạng thái của đàn bò trong hình chữ nhật đó rốt cuộc không thay đổi. Vì vậy, bạn chỉ cần xét việc dùng máy trên mỗi hình chữ nhật góc trên bên trái nhiều nhất một lần.
Dòng đầu tiên chứa số nguyên \(N\).
Mỗi dòng trong \(N\) dòng tiếp theo chứa một xâu gồm \(N\) ký tự; mỗi ký tự là 0 (biểu thị một con bò đang đứng) hoặc 1 (biểu thị một con bò bị ngã).
In số lần ít nhất Farmer John cần sử dụng Cow-Untipperator 3000 để dựng tất cả bò đứng dậy.
Ví dụ 1
3
001
111
1112Trong ví dụ này, nếu Farmer John dùng máy lên toàn bộ đàn bò (đây là một hình chữ nhật góc trên bên trái hợp lệ), trạng thái của chúng sẽ được đảo thành:
110
000
000
Khi đó, ông chỉ còn phải dùng máy lên hình chữ nhật góc trên bên trái chứa hai chữ số 1 là hoàn tất. Tổng cộng chỉ cần \(2\) lần sử dụng máy.
USACO 2017 January Contest, Bronze — Cow Tipping. Tác giả đề: Nathan Pinsker.