Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

VODONCAY - Đốn Cây

Hiện tại, bài tập này đã có trên online judge chính thức của VNOI, bạn có thể truy cập ở đây: https://oj.vnoi.info/problem/vodoncay


Hùng đang làm việc trong Công ty cao su X. Công ty có rừng cao su rất rộng, với những hàng cây cao su trồng cách đều thẳng tắp. Theo định kỳ, người ta thường phải chặt hạ cả hàng cây cao su đã hết hạn khai thác để trồng thay thế bằng hàng cây mới. Hùng phát hiện ra một bài toán tin học liên quan đến vấn đề này: Một nhóm công nhân được giao nhiệm vụ chặt hạ hàng cây gồm N cây được trồng dọc theo một đường thẳng với khoảng cách cố định giữa hai cây liên tiếp. Nếu các công nhân cưa đổ một cây, họ có thể cho nó đổ về phía bên trái hoặc bên phải dọc theo hàng cây. Một cây khi đổ có thể lật đổ cây khác bị nó rơi vào và có thể làm đổ nhiều cây khác, theo hiệu ứng lan truyền domino. Sau khi khảo sát kỹ, Hùng đã mô tả được hiệu ứng lan truyền domino như sau: Giả sử các cây trên hàng cây được đánh số từ 1 đến N, từ trái qua phải và chiều cao của cây i là hi (1 <= i <= N)

  • Nếu cây i đổ về bên trái thì tất cả các cây j với i – hi < j < i cũng sẽ đổ;
  • Nếu cây i đổ về bên phải thì tất cả các cây j với i < j < i + hi cũng sẽ đổ;
  • Mỗi cây chỉ đổ một lần về bên trái hoặc bên phải.

Do đó bài toán đặt ra đối với Hùng là: Xác định số lượng nhỏ nhất các cây mà các công nhân cần cưa đổ đảm bảo hạ đổ toàn bộ hàng cây.

Yêu cầu: Giúp Hùng giải quyết bài toán đặt ra.

Dữ liệu:

  • Dòng đầu tiên ghi số nguyên dương N;
  • Dòng thứ hai chứa N số nguyên dương h1, h2, …, hn được ghi cách nhau bởi dấu cách, mỗi số không vượt quá 106.

Kết quả:

  • Dòng đầu tiên ghi số nguyên dương k là số lượng cây mà các công nhân cần cưa đổ;
  • Dòng thứ hai ghi dãy số nguyên c1, c2, …, ck trong đó |cj| (1 <= j <= k) là dãy chỉ số của các cây theo thứ tự các công nhân phải lần lượt cưa đổ, cj là số dương nếu cây cần cho đổ về bên phải và là số âm nếu cây cần cho đổ về bên trái. Nếu có nhiều cách thì chỉ cần đưa ra một cách tùy ý.

Ví dụ:

INPUT

OUTPUT

5

1 2 3 1 1

2

3 -2

Chú ý: Còn một cách đốn cây khác: Cưa hai cây 1 và 2 và đều cho đổ về bên phải.

Ràng buộc:

  • Có 40% số test ứng với 40% số điểm của bài có 1 <= N <= 10000.
  • Có 40% số test khác ứng với 40% số điểm của bài có 1 <= N <= 100000.
  • Có 20% số test còn lại ứng với 20% số điểm của bài có 1 <= N <= 4000000.


Được gửi lên bởi:VOJ Team
Ngày:2016-01-09
Thời gian chạy:1s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:Tất cả ngoại trừ: ASM64 GOSU JS-MONKEY PERL6 PYPY RUST SED
Nguồn bài:VOI 2016 bài 6

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.