| # | Bài tập | Điểm | Thời gian: | Giới hạn bộ nhớ |
|---|---|---|---|---|
| 1 | USACO 2018 - My Cow Ate My Homework | 100 (p) | 4.0s | 512M |
| 2 | USACO 2018 - Milk Measurement | 100 (p) | 4.0s | 512M |
| 3 | USACO 2018 - The Bovine Shuffle | 100 (p) | 4.0s | 512M |
Trong lớp lịch sử loài bò, bạn được giao một bài tập khá dài gồm \(N\) câu hỏi (\(3 \leq N \leq 100{,}000\)), mỗi câu được chấm bằng một số điểm nguyên trong khoảng \(0 \ldots 10{,}000\). Theo cách làm thường thấy, giáo viên dự định tính điểm cuối cùng bằng cách loại bỏ một câu hỏi mà bạn nhận điểm thấp nhất, rồi lấy trung bình điểm của các câu còn lại. Không may, cô bò cưng Bessie vừa ăn mất câu trả lời của bạn cho \(K\) câu hỏi đầu tiên! (\(K\) có thể nhỏ nhất là \(1\) hoặc lớn nhất là \(N-2\).)
Sau khi bạn giải thích rất nhiều, cuối cùng giáo viên cũng tin câu chuyện và đồng ý chấm phần bài tập còn lại chưa bị ăn theo cách cũ: loại bỏ câu hỏi có điểm thấp nhất (hoặc một trong các câu như vậy nếu có nhiều câu đồng hạng), rồi lấy trung bình điểm của phần còn lại.
Hãy in ra theo thứ tự tăng dần tất cả các giá trị \(K\) giúp bạn nhận được điểm cao nhất có thể theo cách chấm này.
Dòng đầu tiên chứa \(N\) và dòng tiếp theo chứa điểm của \(N\) câu hỏi trong bài tập.
In ra tất cả các giá trị \(K\) giúp bạn nhận được điểm cao nhất có thể, mỗi giá trị trên một dòng.
Ví dụ 1
5
3 1 9 2 72Nếu Bessie ăn hai câu hỏi đầu tiên, các điểm còn lại là \(9\), \(2\) và \(7\). Sau khi loại điểm nhỏ nhất và lấy trung bình, ta được điểm cuối cùng là \(8\), đây là giá trị cao nhất có thể.
USACO 2017 December Contest, Silver — My Cow Ate My Homework
Tác giả bài toán: Brian Dean.
Ban đầu, mỗi cô bò của bác nông dân John cho \(G\) gallon sữa mỗi ngày (\(1 \leq G \leq 10^9\)). Vì sản lượng sữa của một cô bò có thể thay đổi theo thời gian, bác nông dân John quyết định định kỳ đo sản lượng sữa và ghi lại trong sổ nhật ký. Các mục trong sổ có dạng như sau:
35 1234 -2
14 2345 +3
Mục đầu tiên cho biết vào ngày \(35\), sản lượng sữa của bò số \(1234\) thấp hơn \(2\) gallon so với lần đo gần nhất. Mục tiếp theo cho biết vào ngày \(14\), sản lượng sữa của bò số \(2345\) tăng \(3\) gallon so với lần đo gần nhất. Bác nông dân John chỉ có đủ thời gian để thực hiện nhiều nhất một phép đo trong mỗi ngày. Không may là bác khá thiếu ngăn nắp và không nhất thiết ghi các phép đo theo thứ tự thời gian.
Để khích lệ đàn bò, bác nông dân John tự hào trưng trên tường chuồng ảnh của cô bò đang có sản lượng sữa cao nhất (nếu nhiều cô bò cùng đạt sản lượng cao nhất, bác trưng ảnh của tất cả các cô đó). Hãy xác định số ngày mà bác nông dân John cần thay đổi bảng ảnh này.
Lưu ý rằng bác nông dân John có một đàn bò rất lớn. Vì vậy, mặc dù một số cô bò được ghi nhận trong sổ là có thay đổi sản lượng sữa, luôn có rất nhiều cô bò khác vẫn giữ nguyên sản lượng ở mức \(G\) gallon.
Dòng đầu tiên chứa số phép đo \(N\) mà bác nông dân John thực hiện (\(1 \leq N \leq 100{,}000\)), theo sau là \(G\). Mỗi dòng trong \(N\) dòng tiếp theo chứa một phép đo theo định dạng trên, gồm một ngày (một số nguyên trong khoảng \(1 \ldots 10^6\)), mã ID nguyên của một cô bò (trong khoảng \(1 \ldots 10^9\)), và mức thay đổi sản lượng sữa của cô ấy kể từ lần đo gần nhất (một số nguyên khác \(0\)). Sản lượng sữa của mỗi cô bò luôn nằm trong khoảng \(0 \ldots 10^9\).
In ra số ngày mà bác nông dân John cần điều chỉnh bảng ảnh khích lệ của mình.
Ví dụ 1
4 10
7 3 +3
4 2 -1
9 3 -1
1 1 +23USACO 2017 December Contest, Silver — Milk Measurement
Tác giả bài toán: Brian Dean.
Tin rằng những cô bò vui vẻ sẽ cho nhiều sữa hơn, bác nông dân John đã lắp một quả cầu disco khổng lồ trong chuồng và dự định dạy đàn bò của mình khiêu vũ!
Sau khi tìm hiểu các điệu nhảy phổ biến của loài bò, bác nông dân John quyết định dạy đàn bò điệu “Bovine Shuffle”. Điệu Bovine Shuffle bắt đầu với \(N\) cô bò (\(1 \leq N \leq 100{,}000\)) xếp thành một hàng theo một thứ tự nào đó, rồi thực hiện liên tiếp nhiều lần “xáo trộn”, mỗi lần có thể sắp xếp lại đàn bò. Để đàn bò dễ xác định vị trí của mình hơn, bác nông dân John đánh dấu các vị trí trong hàng từ \(1 \ldots N\): cô bò đầu hàng đứng ở vị trí \(1\), cô tiếp theo ở vị trí \(2\), và cứ thế cho đến vị trí \(N\).
Một lần xáo trộn được mô tả bởi \(N\) số \(a_1 \ldots a_N\), trong đó một cô bò ở vị trí \(i\) sẽ di chuyển đến vị trí \(a_i\) trong lần xáo trộn đó (vì vậy mỗi \(a_i\) nằm trong khoảng \(1 \ldots N\)). Mọi cô bò đều di chuyển đến vị trí mới trong lần xáo trộn. Không may, các giá trị \(a_i\) không nhất thiết phải khác nhau, nên nhiều cô bò có thể cố di chuyển đến cùng một vị trí trong một lần xáo trộn; sau đó, chúng sẽ di chuyển cùng nhau trong tất cả các lần xáo trộn còn lại.
Bác nông dân John nhận thấy rằng có một số vị trí trong hàng luôn chứa bò, bất kể thực hiện bao nhiêu lần xáo trộn. Hãy giúp bác đếm số vị trí như vậy.
Dòng đầu tiên chứa \(N\), số lượng bò. Dòng tiếp theo chứa \(N\) số nguyên \(a_1 \ldots a_N\).
In ra số vị trí sẽ luôn chứa bò, bất kể thực hiện bao nhiêu lần xáo trộn.
Ví dụ 1
4
3 2 1 33USACO 2017 December Contest, Silver — The Bovine Shuffle
Tác giả bài toán: Brian Dean.