TLEoj Contest #08 - Trò chơi với đá

Điểm: 1400 (thành phần)

Thời gian: 1.0s

Bộ nhớ: 256M

Input: bàn phím

Output: màn hình

Tác giả:

nathan4690

Dạng bài

Ở thành phố XYZ, ai ai cũng đều biết tới nathan4690 với khả năng "chơi đá" thần sầu của anh khiến tất cả đều ngưỡng mộ. Tuy nhiên, riêng chỉ có bạn là không tin tưởng vào tài năng đó của nathan4690, vì vậy cậu ấy quyết định sẽ thách đấu bạn bằng một trò chơi nho nhỏ.

Trò chơi được thực hiện trên một sân đấu được chia thành $10^6$ vị trí được đánh số từ $1$ đến $10^6$ . nathan4690 có một số viên đá, cậu ấy xếp chúng vào $n$ vị trí từ $1$ đến $n$ , vị trí thứ $i$ có $a_i$ viên đá. Bạn được thực hiện không quá $10^6$ thao tác sau:

Chọn $3$ vị trí $i,j,k$ phân biệt có giá trị không quá $10^6$ sao cho vị trí $i$ và $j$ chứa ít nhất một viên đá.
Lấy hai viên đá từ hai vị trí thứ $i$ , $j$ , mỗi vị trí một viên đá, rồi chuyển chúng sang vị trí thứ $k$ .

Mục tiêu của trò chơi là chuyển hết tất cả các viên đá về một vị trí duy nhất (vị trí kết thúc không quan trọng). nathan4690 đã dễ dàng dành chiến thắng trong trò chơi này, thậm chí không cần dùng đến các vị trí lớn hơn $n$ s, còn bạn?

Input, Output và Subtasks

Input

Dòng đầu tiên chứa số nguyên dương $n$ là số lượng vị trí được đặt đá ( $4 \leq n \leq 10^5$ )
Dòng thứ hai chứa $n$ số nguyên dương $a_1, a_2, \ldots, a_n$ tương ứng là số viên đá ở vị trí thứ $1,2,\ldots,n$ ( $1 \leq a_i \leq 10^5$ )

Dữ liệu đảm bảo $a_1 + a_2 + \ldots + a_n \leq 2 \times 10^5$

Output

Dòng đầu tiên cần chứa số nguyên không âm $c$ là số lượng thao tác bạn sẽ thực hiện ( $0 \leq c \leq 10^6$ ). Lưu ý rằng bạn không cần tối thiểu hóa số thao tác bạn thực hiện.
$c$ dòng tiếp theo, mỗi dòng cần chứa $3$ số nguyên dương phân biệt $i,j,k$ là các vị trí bạn sẽ thực hiện thao tác ( $1 \leq i,j,k \leq 10^6$ )
Nếu bạn không thể dành chiến thắng trong trò chơi của nathan4690, in ra một dòng duy nhất chứa số -1

Subtasks

Subtask $1$ ( $20\%$ số điểm): $a_i \leq 2$ với mọi $i$
Subtask $2$ ( $80\%$ số điểm): Không có ràng buộc gì thêm.

Với mỗi test:

Bạn sẽ được tính $25\%$ số điểm của test đó nếu bạn sử dụng không quá $10^6$ vị trí.
Bạn sẽ được tính $100\%$ số điểm của test đó nếu bạn sử dụng không quá $n$ vị trí.

Sample

Sample Input

4
1 2 3 1

Sample output

2
1 2 3
2 4 3

Note

Ban đầu, số lượng đá ở từng chồng là: $1,2,3,1$
Ở bước 1, bạn chuyển $1$ viên từ chồng $1$ và $1$ viên từ chồng $2$ sang chồng thứ $3$ . Số lượng đá ở từng chồng lúc này là: $0,1, 5,1$
Ở bước 2, bạn chuyển $1$ viên từ chồng $2$ và $1$ viên từ chồng $4$ sang chồng thứ $3$ . Số lượng đá ở từng chồng lúc này là: $0,0, 7,0$
Bạn giành chiến thắng trò chơi vì đã đưa hết các viên đá vào chồng thứ $3$ . Bạn được $100\%$ số điểm của test vì không dùng tới bất kỳ vị trí nào lớn hơn $4$ .

Bình luận

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