Dãy m-cute

Điểm: 8,00 (OI)

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

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

Đầu vào: stdin

Đầu ra: stdout

Dạng bài

Ngôn ngữ cho phép

Ada, Algol, Assembly, Awk, C, C#, C++, D, Dart, Forth, Fortran, Go, Groovy, Java, Javascript, Kotlin, Lisp, Lua, Nim, ObjC, Pascal, Perl, PHP, Pike, Python, Racket, Ruby, Rust, Scheme, Scratch, Sed, TCL, Typescript, V, Zig

Cho số nguyên dương $m$ . Một dãy số nguyên dương $x_{1}, x_{2}, \dots, x_{n}$ được gọi là $m$ -cute nếu với mọi chỉ số $i$ thỏa mãn $2 \leq i \leq n$ , ta có

$x_{i} = x_{i - 1} + x_{i - 2} + \dots + x_{1} + r_{i}$

với $r_{i}$ là một số nguyên dương nào đó thỏa $1 \leq r_{i} \leq m$ .

Cho $q$ truy vấn, mỗi truy vấn gồm ba số nguyên dương $a$ , $b$ , $m$ . Với mỗi truy vấn, hãy xác định xem có tồn tại một dãy $m$ -cute nhận $a$ là phần tử đầu tiên và $b$ là phần tử cuối cùng hay không. Nếu có, hãy đưa ra một dãy như vậy.

Có thể chứng minh rằng dưới ràng buộc của bài, nếu tồn tại dãy hợp lệ thì luôn tồn tại một dãy có không quá $50$ phần tử.

Dữ liệu vào

Dòng đầu chứa số nguyên $q$ — số truy vấn.
$q$ dòng tiếp theo, mỗi dòng chứa ba số nguyên $a$ , $b$ , $m$ mô tả một truy vấn.

Dữ liệu ra

Với mỗi truy vấn:

Nếu không tồn tại dãy $m$ -cute hợp lệ, in ra -1.
Ngược lại, in ra một số nguyên $k$ ( $1 \leq k \leq 50$ ), sau đó là $k$ số nguyên $x_{1}, x_{2}, \dots, x_{k}$ ( $1 \leq x_{i} \leq 10^{14}$ ) thỏa mãn $x_{1} = a$ , $x_{k} = b$ và dãy là $m$ -cute.

Nếu có nhiều dãy hợp lệ, in ra dãy nào cũng được.

Ràng buộc

$1 \leq q \leq 10^{3}$
$1 \leq a, b, m \leq 10^{14}$ , $a \leq b$

Ví dụ

Input	Output	Giải thích
2 5 26 2 3 9 1	4 5 7 13 26 -1	Truy vấn 1: dãy $5, 7, 13, 26$ hợp lệ vì $7 = 5 + 2$ , $13 = 7 + 5 + 1$ , $26 = 13 + 7 + 5 + 1$ — các giá trị $r_{i}$ đều nằm trong $[1, 2]$ . Đây là một đáp án; chẳng hạn $5, 6, 13, 26$ cũng được chấp nhận. Truy vấn 2: với $m = 1$ và bắt đầu từ $3$ , dãy duy nhất tuân thủ là $3, 4, 8, 16, \dots$ , không chứa $9$ .
1 1 1 100000000000000	1 1	Dãy chỉ gồm một phần tử $1$ thoả $x_{1} = a = b = 1$ .

Bình luận

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