trang chủ / bài tập / charmgame

Mê hoặc bởi trận đấu

Đề bài

Mô tả

Alice và Borys đang chơi một trận tennis gồm a+b game. Trong mỗi game, một người giao bóng (server) và người còn lại đỡ bóng (receiver). Hai người giao bóng luân phiên: sau game Alice giao bóng là game Borys giao bóng, và ngược lại.

Mỗi game kết thúc với chiến thắng của một trong hai người. Nếu người giao bóng thắng game đó, ta nói người đó giữ giao bóng. Nếu người đỡ bóng thắng game đó, ta nói người đó bẻ giao bóng (break).

Biết rằng kết thúc trận đấu, Alice thắng a game và Borys thắng b game. Ta không biết ai là người giao bóng game đầu tiên, cũng không biết ai thắng từng game cụ thể.

Hãy tìm tất cả các giá trị k sao cho có thể đã xảy ra đúng k break trong cả trận đấu.

Dữ liệu vào

Dòng đầu chứa số nguyên t (1t103) — số test trong file.

Mỗi dòng trong t dòng tiếp theo chứa hai số nguyên ab (0a,b105; a+b>0) — số game Alice và Borys thắng.

Dữ liệu ra

Với mỗi test in ra hai dòng.

  • Dòng đầu: số nguyên m (1ma+b+1) — số giá trị k thỏa mãn.
  • Dòng thứ hai: m số nguyên phân biệt k1<k2<<km (0kia+b) theo thứ tự tăng dần.

Ràng buộc

  • 1t103
  • 0a,b105a+b>0
  • Tổng a+b trên tất cả các test trong một file không vượt quá 2·105.

Ví dụ

Input Output Giải thích
3
2 1
1 1
0 5
4
0 1 2 3
2
0 2
2
2 3
Test 1: trận có 3 game, mọi giá trị từ 0 đến 3 break đều có thể. Test 2: trận có 2 game — hoặc cả hai đều giữ giao (0 break), hoặc cả hai cùng bị bẻ (2 break). Test 3: Alice thắng 0 game nên Borys luôn thắng; trong 5 game Borys phải giao 2 hoặc 3 game, mỗi game Borys đỡ là một break, cho 2 hoặc 3 break.
2
99999 0
0 99999
2
49999 50000
2
49999 50000
Với một người thắng toàn bộ 99999 game, số break luôn bằng số game người còn lại giao — là 49999 hoặc 50000 tùy ai giao trước.

Bình luận

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

gnatmake 12.2.0 a68g 3.1.2 nasm 2.16.1 as_x64 2.46 awk 1.3.4 gcc 16.1.0 csc 6.12.0.200 g++ 16.1.0 g++-themis 16.1.0 g++17 16.1.0 g++20 16.1.0 g++23 16.1.0 clang++ 22.1.6 dmd 2.112.0 dart 3.12.1 gforth 0.7.3 gfortran 12.2.0 go 1.26.3 groovyc 5.0.6 javac 25.0.3 node 26.2.0 kotlinc 2.3.21 sbcl 2.2.9 lua 5.4.8 nim 2.2.10 fpc 3.2.2 fpc-themis 3.2.2 perl 5.36.0 php 8.5.6 pike 8.0 pypy3 7.3.23 python3 3.14.5 racket 8.7 ruby 4.0.5 rustc 1.96.0 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 tclsh 8.6 bun 1.3.14 deno 2.8.1 v 0.5.1 zig 0.16.0