VM 08 Bài 09 - Những hình nhân nhảy múa

View as PDF

Submit solution


Points: 0.25 (partial)
Time limit: 0.38s
Memory limit: 256M
Input: stdin
Output: stdout

Problem source:
VNOI Marathon '08 - Round 12/DivBProblem Setter: Ngô Minh Ðức
Problem type
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

Những hình nhân nhảy múa là một loại mật mã bí ẩn đã xuất hiện trong một câu chuyện về thám tử Sherlock Homes. Ngày nay, người ta vẫn còn dùng loại mật mã này, nhưng các hình nhân được truyền đi bằng hình ảnh qua Internet và khó giải mã hơn. Chúng sẽ tự động biến đổi đi theo thời gian để trở nên khó nhận dạng so với mật mã ban đầu. Các hình nhân có chiều cao khác nhau, mỗi hình nhân có thể quay lên phía trên hoặc quay xuống phía dưới.

image

Để tiện lợi, ta quy ước chiều cao của mỗi hình nhân là số dương nếu quay đầu lên trên và số âm nếu quay đầu xuống dưới. Sau mỗi giây, các hình nhân sẽ biến đổi như sau. Ba hình nhân liên tiếp bất kỳ sẽ được chọn. Chiều cao của hai hình nhân ở bên trái và phải sẽ được cộng thêm một lượng bằng chiều cao kể cả dấu của hình nhân ở giữa. Sau đó, hình nhân ở giữa sẽ quay ngược đầu lại. Hình dưới đây minh họa sự biến đổi của ba hình nhân liên tiếp:

image

Biết rằng ban đầu, các hình nhân đều quay lên phía trên.

Biết dãy các hình nhân tại một thời điểm nào đó, bạn hãy xác dịnh dãy hình nhân ban đầu, hoặc thông báo dãy hình nhân không hợp lệ, nếu không tìm được dãy hình nhân ban đầu hoặc dãy hình nhân ban đầu không phải là duy nhất.

Input

  • Dòng 1: chứa số nguyên dương ~N~, là số lượng hình nhân trên dãy.
  • Dòng 2: chứa ~N~ số nguyên ~a_1, a_2, a_3, ..., a_n~. Trong đó ~|a_i|~ cho biết chiều cao của hình nhân thứ ~i~ tại một thời điểm nào đó, ~a_i > 0~ nếu hình nhân quay đầu lên trên, và ~a_i < 0~ nếu hình nhân quay đầu xuống dưới.

Các hình nhân được đánh số thứ tự từ 1 đến ~N~ từ trái sang phải.

  • ~1 \le N \le 10^5~.
  • ~1 \le |a_i| \le 5000~.

Output

Gồm một dòng duy nhất chứa:

  • Số -1 nếu không tìm được dãy hình nhân ban đầu hoặc dãy hình nhân ban đầu không phải là duy nhất.
  • Hoặc ~N~ số nguyên ~b_1, b_2, ..., b_n~ là dãy hình nhân ban đầu, với cùng kiểu mô tả như trong dữ liệu vào. ~b_1, b_2, ..., b_n~ phải là số nguyên dương, vì các hình nhân ban đầu đều quay lên trên.

Sample Input

5
2451 -1647 -244 1006 1130

Sample Output

560 244 762 885 245

Comments

Please read the guidelines before commenting.



  • 0
    JokerFav  commented on March 18, 2023, 2:35 a.m.

    cái đề sai chính tã kìa