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

Trò chơi trên các đoạn

Đề bài

Mô tả

Alice và Bob chơi trò chơi sau. Alice giữ một tập S gồm các đoạn số nguyên rời nhau, ban đầu S chỉ chứa đúng một đoạn [1,n].

Mỗi lượt, Alice chọn một đoạn [l,r] trong S và yêu cầu Bob chọn một số trong đoạn đó. Bob chọn số d với l≤d≤r. Sau đó Alice xoá [l,r] khỏi S rồi thêm vào S đoạn [l,d−1] (nếu l≤d−1) và đoạn [d+1,r] (nếu d+1≤r). Trò chơi kết thúc khi S rỗng, và có thể chứng minh trò chơi luôn kéo dài đúng n lượt.

Sau khi chơi xong, Alice nhớ được toàn bộ n đoạn [l,r] mà cô đã chọn, nhưng Bob thì quên hết các số mình đã chọn. Cho danh sách các đoạn của Alice (theo thứ tự bất kỳ), hãy khôi phục với mỗi đoạn [l,r] số d mà Bob đã chọn.

Dữ liệu vào luôn tương ứng với một ván chơi hợp lệ, và có thể chứng minh cách khôi phục là duy nhất.

Dữ liệu vào

  • Dòng đầu chứa số nguyên t là số lượng bộ test.
  • Mỗi bộ test gồm dòng đầu chứa số nguyên n, sau đó là n dòng, mỗi dòng chứa hai số nguyên l và r mô tả một đoạn Alice đã chọn. Các đoạn được cho theo thứ tự tuỳ ý.

Dữ liệu ra

Với mỗi bộ test, in ra n dòng, mỗi dòng chứa ba số nguyên l, r, d nghĩa là với đoạn [l,r] của Alice thì Bob đã chọn số d. Các dòng có thể in theo thứ tự bất kỳ.

Ràng buộc

  • 1≤t≤1000
  • 1≤n≤1000
  • 1≤l≤r≤n
  • Tổng n trên tất cả các bộ test không vượt quá 1000.

Ví dụ

Input Output Giải thích
2
1
1 1
3
1 3
2 3
2 2		 1 1 1
1 3 1
2 2 2
2 3 3		 Bộ test 1: chỉ có một đoạn [1,1] nên Bob buộc phải chọn 1.
Bộ test 2: Alice chọn [1,3], Bob chọn 1, còn lại {[2,3]}; Alice chọn [2,3], Bob chọn 3, còn lại {[2,2]}; Alice chọn [2,2], Bob chọn 2.
1
5
1 5
1 2
4 5
2 2
4 4		 1 2 1
1 5 3
2 2 2
4 4 4
4 5 5		 Alice chọn [1,5], Bob chọn 3, còn lại {[1,2],[4,5]}; rồi [1,2] với d=1, [4,5] với d=5, [2,2] với d=2, [4,4] với d=4. Ở đây các dòng được in theo thứ tự tăng dần của (l,r), nhưng mọi thứ tự khác cũng được chấp nhận.

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.47 awk 1.3.4 gcc 16.2.0 dotnet 10.0.400 g++ 16.2.0 g++-themis 16.2.0 g++17 16.2.0 g++20 16.2.0 g++23 16.2.0 clang++ 22.1.8 dmd 2.113.0 dart 3.13.2 gforth 0.7.3 gfortran 12.2.0 go 1.27.0 groovyc 5.1.1 javac 25.0.4 node 26.8.1 julia 1.12.7 kotlinc 2.4.10 lean 4.33.1 sbcl 2.2.9 lua 5.4.9 nim 2.2.10 fpc 3.2.2 fpc-themis 3.2.2 perl 5.36.0 php 8.5.10 pike 8.0 swipl 9.0.4 pypy3 7.3.23 python3 3.14.7 racket 8.7 ruby 4.0.6 rustc 1.98.0 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 swiftc 6.3.3 tclsh 8.6 bun 1.4.0 deno 2.9.6 v 0.5.2 zig 0.16.0