| # | Bài tập | Điểm | Thời gian: | Giới hạn bộ nhớ |
|---|---|---|---|---|
| 1 | USACO 2017 - Why Did the Cow Cross the Road | 100 (p) | 4.0s | 512M |
| 2 | USACO 2017 - Why Did the Cow Cross the Road II | 100 (p) | 4.0s | 512M |
| 3 | USACO 2017 - Why Did the Cow Cross the Road III | 100 (p) | 4.0s | 512M |
Trong khi câu hỏi muôn thuở về lý do gà băng qua đường đã được cộng đồng khoa học nghiên cứu rất sâu rộng, đáng ngạc nhiên là có rất ít công trình được công bố về chủ đề liên quan: những lần bò băng qua đường. Nhận thức rõ tầm quan trọng của vấn đề này, Farmer John vô cùng phấn khởi khi một trường đại học địa phương liên hệ và nhờ ông hỗ trợ thực hiện một nghiên cứu khoa học về lý do bò băng qua đường. Ông háo hức tình nguyện giúp đỡ.
Trong khuôn khổ nghiên cứu, Farmer John được yêu cầu ghi lại số lần mỗi con bò của mình băng qua đường. Trong suốt một ngày, ông cẩn thận ghi chép vị trí của đàn bò qua một chuỗi gồm \(N\) lần quan sát. Mỗi lần quan sát ghi lại mã số của một con bò (một số nguyên trong khoảng \(1 \ldots 10\), vì Farmer John có 10 con bò), cùng với phía đường mà con bò đang đứng.
Dựa trên dữ liệu Farmer John đã ghi lại, hãy giúp ông đếm tổng số lần băng qua đường được xác nhận. Một lần băng qua đường được xác nhận khi hai lần quan sát liên tiếp đối với cùng một con bò cho thấy nó ở hai phía khác nhau của con đường.
Dòng đầu tiên chứa số lần quan sát \(N\), là một số nguyên dương không quá 100. Mỗi dòng trong \(N\) dòng tiếp theo chứa một lần quan sát, gồm mã số của một con bò, theo sau là vị trí của nó được biểu thị bằng 0 hoặc 1 (0 ứng với một phía của con đường, 1 ứng với phía còn lại).
In ra tổng số lần băng qua đường được xác nhận.
Ví dụ 1
8
3 1
3 0
6 0
2 1
4 1
3 0
4 0
3 13Trong ví dụ này, bò số 3 băng qua đường hai lần: ban đầu nó xuất hiện ở phía 1, sau đó xuất hiện ở phía 0, rồi về sau lại xuất hiện ở phía 1. Bò số 4 chắc chắn băng qua đường một lần. Bò số 2 và bò số 6 dường như không băng qua đường.
USACO 2017 February Contest, Bronze — Why Did the Cow Cross the Road. Tác giả đề: Brian Dean.
Bố cục trang trại của Farmer John khá kỳ lạ: một con đường lớn hình tròn chạy quanh rìa cánh đồng chính, nơi đàn bò của ông gặm cỏ vào ban ngày. Mỗi sáng, đàn bò băng qua con đường này để vào cánh đồng; mỗi tối, tất cả lại băng qua đường khi rời cánh đồng và trở về chuồng.
Như chúng ta đã biết, bò là loài sống theo thói quen và mỗi con đều băng qua đường theo cùng một cách mỗi ngày. Mỗi con bò đi vào cánh đồng tại một điểm khác với điểm nó đi ra, và tất cả các điểm băng qua đường đều phân biệt. Farmer John có đúng 26 con bò, được ông tùy tiện đặt tên từ A đến Z (ông cũng không biết sẽ làm gì nếu sau này có thêm con bò thứ 27...), nên có chính xác 52 điểm băng qua đường quanh con đường. Farmer John ghi lại các điểm này một cách ngắn gọn bằng cách đi một vòng theo chiều kim đồng hồ, viết tên con bò tại mỗi điểm băng qua đường, cuối cùng tạo thành một xâu 52 ký tự trong đó mỗi chữ cái xuất hiện đúng hai lần. Ông không ghi lại đâu là điểm đi vào và đâu là điểm đi ra.
Nhìn vào sơ đồ các điểm băng qua đường, Farmer John tò mò muốn biết đường đi của các cặp bò khác nhau có thể cắt nhau bao nhiêu lần trong ngày. Ông gọi một cặp bò \((a,b)\) là một cặp "giao nhau" nếu đường đi từ điểm vào đến điểm ra của bò \(a\) bắt buộc phải cắt đường đi từ điểm vào đến điểm ra của bò \(b\). Hãy giúp Farmer John đếm tổng số cặp giao nhau.
Dữ liệu vào gồm một dòng duy nhất chứa một xâu 52 ký tự in hoa. Mỗi chữ cái trong bảng chữ cái xuất hiện đúng hai lần.
In ra tổng số cặp giao nhau.
Ví dụ 1
ABCCABDDEEFFGGHHIIJJKKLLMMNNOOPPQQRRSSTTUUVVWWXXYYZZ1Trong ví dụ này, chỉ có bò A và bò B tạo thành một cặp giao nhau.
USACO 2017 February Contest, Bronze — Why Did the Cow Cross the Road II. Tác giả đề: Brian Dean.
Khi đã có tuổi, Farmer John không may ngày càng trở nên cáu kỉnh và đa nghi. Quên mất rằng sự đa dạng của loài bò đã giúp trang trại của mình phát triển thịnh vượng đến mức nào trong nhiều năm qua, gần đây ông quyết định xây một hàng rào khổng lồ bao quanh trang trại, khiến bò từ các trang trại lân cận nản lòng không muốn ghé thăm và hoàn toàn cấm bò từ một số ít trang trại lân cận đi vào. Đàn bò rất buồn trước tình cảnh này, không chỉ vì chúng không còn được thăm bạn bè mà còn vì điều đó buộc chúng phải hủy việc tham dự Olympic Vắt sữa Quốc tế, một sự kiện chúng mong chờ suốt cả năm.
Những con bò hàng xóm vẫn được phép vào trang trại của Farmer John nhận thấy quá trình này đã trở nên vất vả hơn, vì chúng chỉ có thể đi qua một cánh cổng duy nhất, nơi mỗi con phải chịu sự thẩm vấn gắt gao, thường khiến đàn bò phải xếp thành một hàng dài.
Với mỗi con trong số \(N\) con bò đến thăm trang trại, bạn được biết thời điểm nó đến cổng và khoảng thời gian nó cần để trả lời các câu hỏi nhập cảnh. Tại một thời điểm chỉ có thể thẩm vấn một con bò, vì vậy nếu nhiều con đến gần như cùng lúc, chúng nhiều khả năng phải xếp hàng chờ để được xử lý lần lượt. Chẳng hạn, nếu một con bò đến vào thời điểm 5 và trả lời câu hỏi trong 7 đơn vị thời gian, một con khác đến vào thời điểm 8 sẽ phải đợi đến thời điểm 12 mới có thể bắt đầu trả lời.
Hãy xác định thời điểm sớm nhất mà tất cả các con bò có thể vào được trang trại.
Dòng đầu tiên chứa \(N\), là một số nguyên dương không quá 100. Mỗi dòng trong \(N\) dòng tiếp theo mô tả một con bò, cho biết thời điểm nó đến và thời gian nó cần để trả lời câu hỏi; mỗi số là một số nguyên dương không quá 1.000.000.
In ra thời điểm nhỏ nhất có thể mà tất cả các con bò đã hoàn tất quá trình kiểm tra.
Ví dụ 1
3
2 1
8 3
5 715Ở đây, con bò thứ nhất đến vào thời điểm 2 và nhanh chóng được kiểm tra xong. Cổng tạm thời không hoạt động cho đến khi con bò thứ ba đến vào thời điểm 5 và bắt đầu được kiểm tra. Sau đó, con bò thứ hai đến vào thời điểm 8 và đợi đến thời điểm \(5+7=12\) mới bắt đầu trả lời câu hỏi, rồi hoàn tất tại thời điểm \(12+3=15\).
USACO 2017 February Contest, Bronze — Why Did the Cow Cross the Road III. Tác giả đề: Brian Dean.