Kiểm tra kiện cỏ

Điểm: 1,00 (OI)

Giới hạn thời gian: 2.0s

Python 3 5.0s

Giới hạn bộ nhớ: 256M

Đầu vào: stdin

Đầu ra: stdout

Tác giả:

huunguyen

Dạng bài

Ngôn ngữ cho phép

C++, Go, Java, Kotlin, Pascal, Python, Scratch

Cho một mảng các số nguyên được sắp xếp không giảm $x_{1} \leq x_{2} \leq \dots \leq x_{N}$ ( $1 \leq N \leq 10^{5}$ ) và một số nguyên $K$ . Bạn không biết mảng hay $K$ , nhưng bạn biết rằng với mỗi chỉ số $i$ , $j_{i}$ là chỉ số lớn nhất sao cho $x_{j_{i}} \leq x_{i} + K$ . Đảm bảo rằng $i \leq j_{i}$ và $j_{1} \leq j_{2} \leq \dots \leq j_{N} \leq N$ .

Từ thông tin này, hãy xây dựng một mảng $x$ bất kỳ cùng với một số nguyên $K$ thỏa mãn các điều kiện trên. Cần đảm bảo $0 \leq x_{i} \leq 10^{18}$ với mọi $i$ và $1 \leq K \leq 10^{18}$ .

Có thể chứng minh rằng luôn tồn tại lời giải.

Dữ liệu vào

Dòng đầu tiên chứa số nguyên $N$ .
Dòng thứ hai chứa $j_{1}, j_{2}, \dots, j_{N}$ .

Dữ liệu ra

In $K$ trên dòng đầu tiên, sau đó in $x_{1}, x_{2}, \dots, x_{N}$ trên các dòng tiếp theo (mỗi số trên một dòng).

Mọi đáp án hợp lệ đều được chấp nhận.

Ràng buộc

$1 \leq N \leq 10^{5}$
$i \leq j_{i}$ với mọi $i$
$j_{1} \leq j_{2} \leq \dots \leq j_{N} \leq N$
Với 50% số test, $N \leq 5000$

Ví dụ

Input	Output	Giải thích
6 2 2 4 5 6 6	7 0 1 9 11 17 19	Mảng $a = [0, 1, 9, 11, 17, 19]$ với $K = 7$ . Ví dụ: $j_{1} = 2$ vì $a_{2} = 1 \leq 0 + 7$ nhưng $a_{3} = 9 > 0 + 7$ . Đáp án $a = [1, 2, 4, 5, 6, 7]$ với $K = 1$ cũng hợp lệ.

Bình luận

Không có bình luận tại thời điểm này.