USACO 2014 - Counting Friends

Xem PDF
Tất cả bài nộp
Các bài nộp tốt nhất
Dạng bài
Ngôn ngữ cho phép
Assembly, Awk, C, C#, C++, Clang, Cobol, D, Groovy, Haskell, JS, Java, Kotlin, Lua, Node JS, OCaml, ObjectiveC, PHP, Pascal, Perl, Prolog, Pypy, Pypy 3, Python, Ruby, Rust, Scala, Scratch, Swift
Điểm: 1600 (p) Thời gian: 4.0s Bộ nhớ: 512M Input: bàn phím Output: màn hình

\(N\) cô bò của Farmer John (\(2 \le N \le 500\)) đã tham gia mạng xã hội "MooBook".

Mỗi cô bò có một hoặc nhiều người bạn để tương tác trên MooBook. Để giải trí, Farmer John lập danh sách số lượng bạn bè của từng cô bò. Tuy nhiên, trong lúc ghi danh sách ông bị xao nhãng và vô tình ghi thừa một số, vì vậy danh sách có \(N+1\) số thay vì \(N\) số như dự định.

Hãy giúp Farmer John xác định những số nào trong danh sách có thể là số thừa bị ghi nhầm.

Dữ liệu vào

  • Dòng đầu tiên chứa số nguyên \(N\).
  • \(N+1\) dòng tiếp theo, dòng thứ \(i\) chứa số lượng bạn bè của một cô bò của FJ hoặc có thể là số thừa bị ghi nhầm.

Ràng buộc

  • \(2 \le N \le 500\).
  • Mỗi cô bò có một hoặc nhiều người bạn.

Dữ liệu ra

  • Dòng đầu tiên chứa số nguyên \(K\), là số phần tử trong danh sách của FJ có thể là số thừa. Nếu \(K=0\) thì không có số nào trong danh sách mà sau khi xóa đi sẽ tạo ra một cách kết bạn khả thi.
  • \(K\) dòng tiếp theo, mỗi dòng chứa chỉ số trong thứ tự dữ liệu vào (từ \(1\) đến \(N+1\)) của một số trong danh sách có thể là số thừa; tức là sau khi xóa số này, \(N\) số còn lại cho phép hình thành một tập quan hệ bạn bè khả thi giữa các cô bò. Các chỉ số phải được in theo thứ tự tăng dần.

Ví dụ

Ví dụ 1

Input 
4
1
2
2
1
3
Output 
3
1
4
5
Giải thích

Farmer John có \(4\) cô bò. Hai cô chỉ có \(1\) người bạn mỗi cô, hai cô có \(2\) người bạn mỗi cô và một cô có \(3\) người bạn; tất nhiên, một trong các số này là số thừa không thuộc danh sách.

Xóa số đầu tiên trong danh sách của FJ (số \(1\)) sẽ để lại danh sách \(2,2,1,3\), và danh sách này thật sự cho phép một cách kết bạn khả thi. Chẳng hạn, nếu đặt tên các cô bò là \(A\) đến \(D\), các cặp \((A,B)\), \((A,C)\), \((A,D)\) và \((B,C)\) là đủ: \(A\) có \(3\) người bạn, \(B\) và \(C\) có \(2\) người bạn, còn \(D\) có \(1\) người bạn. Tương tự, xóa số \(1\) còn lại trong danh sách của FJ cũng được, và xóa số \(3\) cũng được. Xóa một trong hai số \(2\) đều không được; có thể thấy điều này vì tổng các số còn lại là số lẻ, rõ ràng khiến việc tìm một cách kết bạn khả thi trở nên bất khả thi.

Nguồn

USACO 2014 March Contest, Gold — Counting Friends

Tác giả: Brian Dean, 2014.

Bình luận

Mới nhất
Tải bình luận...

Không có bình luận nào.

Kỳ thi: