USACO 2022 - Tests for Haybales

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: 2500 (p) Thời gian: 4.0s Bộ nhớ: 512M Input: bàn phím Output: màn hình

Những chú bò của Nông dân John đã quyết định tổ chức một cuộc thi lập trình cho những chú bò ở trang trại của Nông dân Nhoj. Để các bài toán vui nhất có thể, chúng đã dành rất nhiều thời gian nghĩ ra những bộ dữ liệu vào đầy thử thách. Riêng với một bài toán tên “Haybales”, những chú bò cần bạn giúp thiết kế các dữ liệu vào khó. Việc này đòi hỏi giải bài toán khá thú vị sau:

Có một mảng số nguyên đã sắp xếp \(x_1\le x_2\le\dotsb\le x_N\) (\(1\le N\le 10^5\)), và một số nguyên \(K\). Bạn không biết mảng hay \(K\), nhưng với mỗi chỉ số \(i\), bạn biết chỉ số lớn nhất \(j_i\) sao cho \(x_{j_i}\le x_i+K\). Đảm bảo rằng \(i\le j_i\) và \(j_1\le j_2\le\cdots\le j_N\le N\).

Từ thông tin này, những chú bò của Nông dân John cần dựng một mảng bất kỳ cùng với một số nguyên \(K\) khớp với thông tin đã cho. Kết quả dựng phải thỏa mãn \(0\le x_i\le 10^{18}\) với mọi \(i\) và \(1\le K\le 10^{18}\).

Có thể chứng minh rằng điều này luôn khả thi. Hãy giúp những chú bò của Nông dân John giải bài toán!

Dữ liệu vào

Dòng đầu chứa \(N\). Dòng tiếp theo chứa \(j_1,j_2,\ldots,j_N\).

Dữ liệu ra

In \(K\), sau đó in \(x_1,\ldots,x_N\) trên các dòng riêng biệt. Mọi kết quả hợp lệ đều được chấp nhận.

Phân nhóm

  • Với 50% số dữ liệu vào, \(N\le 5000\).
  • Với số dữ liệu vào còn lại, không có ràng buộc bổ sung.

Ví dụ

Ví dụ 1

Input 
6
2 2 4 5 6 6
Output 
6
1
6
17
22
27
32
Giải thích

Kết quả mẫu là mảng \(a=[1,6,17,22,27,32]\) với \(K=6\). \(j_1=2\) được thỏa mãn vì \(a_2=6\le 1+6=a_1+K\) nhưng \(a_3=17>1+6=a_1+K\), nên \(a_2\) là phần tử lớn nhất không vượt quá \(a_1+K\). Tương tự:

  • \(j_2=2\) được thỏa mãn vì \(a_2=6\le 6+6\) nhưng \(a_3=17>6+6\).
  • \(j_3=4\) được thỏa mãn vì \(a_4=22\le 17+6\) nhưng \(a_5=27>17+6\).
  • \(j_4=5\) được thỏa mãn vì \(a_5=27\le 22+6\) nhưng \(a_6=32>22+6\).
  • \(j_5=6\) được thỏa mãn vì \(a_6=32\le 27+6\) và \(a_6\) là phần tử cuối cùng của mảng.
  • \(j_6=6\) được thỏa mãn vì \(a_6=32\le 32+6\) và \(a_6\) là phần tử cuối cùng của mảng.

Đây không phải kết quả đúng duy nhất cho dữ liệu vào mẫu. Chẳng hạn, bạn có thể in mảng \([1,2,4,5,6,7]\) với \(K=1\).

Nguồn

USACO 2022 January Contest, Gold — Tests for Haybales: https://usaco.org/index.php?page=viewproblem2&cpid=1187

Tác giả: Danny Mittal.

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: