trang chủ / đề bài / chessmatch

Trận đấu cờ

Đề bài

Mô tả

Hai đội cờ, mỗi đội có n kỳ thủ, thi đấu với nhau. Kỳ thủ thứ i của đội thứ nhất có trình độ ai, kỳ thủ thứ i của đội thứ hai có trình độ bi.

Mỗi kỳ thủ của đội thứ nhất đấu đúng một ván với một kỳ thủ của đội thứ hai và mỗi kỳ thủ của đội thứ hai cũng có đúng một đối thủ. Nói cách khác, nếu kỳ thủ i của đội thứ nhất gặp kỳ thủ pi của đội thứ hai thì [p1,p2,…,pn] là một hoán vị của 1,2,…,n.

Hai kỳ thủ có trình độ gần nhau dễ hòa, nên ban tổ chức muốn ghép cặp sao cho độ chênh lệch của trận đấu, định nghĩa là mini=1n|ai−bpi|, đạt giá trị lớn nhất có thể. Hãy tìm một cách ghép cặp như vậy.

Dữ liệu vào

  • Dòng đầu tiên chứa số nguyên t là số bộ dữ liệu.
  • Mỗi bộ dữ liệu gồm ba dòng:
    • Dòng thứ nhất chứa số nguyên n.
    • Dòng thứ hai chứa n số nguyên a1≤a2≤…≤an.
    • Dòng thứ ba chứa n số nguyên b1≤b2≤…≤bn.

Dữ liệu ra

Với mỗi bộ dữ liệu, in ra trên một dòng n số nguyên p1,p2,…,pn tạo thành một hoán vị của 1,2,…,n sao cho mini=1n|ai−bpi| lớn nhất. Nếu có nhiều đáp án, in ra đáp án bất kỳ.

Ràng buộc

  • 1≤t≤3000
  • 1≤n≤3000
  • 1≤ai,bi≤106
  • Tổng n trên mọi bộ dữ liệu không vượt quá 3000.

Ví dụ

Input Output Giải thích
4
4
1 2 3 4
1 2 3 4
2
1 100
100 101
2
1 100
50 51
5
1 1 1 1 1
3 3 3 3 3
3 4 1 2
1 2
2 1
5 4 2 3 1
Bộ 1: các cặp chênh lệch 2,2,2,2, độ chênh lệch 2 là lớn nhất. Bộ 2: ghép 1 với 100, 100 với 101 cho độ chênh lệch 1; cách còn lại cho 0. Bộ 3: ghép 1 với 51, 100 với 50 cho độ chênh lệch 50. Bộ 4: mọi cách ghép đều cho 2.
1
3
1 5 9
2 6 10
2 3 1 Các cặp (1,6),(5,10),(9,2) có chênh lệch 5,5,7, độ chênh lệch là 5.

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.402 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.6 gforth 0.7.3 gfortran 15.3.0 go 1.27.3 groovyc 5.1.3 javac 26.0.2.1 node 26.12.1 julia 1.13.2 kotlinc 2.4.21 lean 4.35.0 sbcl 2.2.9 lua 5.5.1 nim 2.2.12 fpc 3.2.2 fpc-themis 3.2.2 perl 5.42.3 php 8.5.12 pike 8.0 swipl 9.0.4 pypy3 7.3.23 python3 3.15.1 racket 8.7 ruby 4.0.8 rustc 1.99.1 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 swiftc 6.4.1 tclsh 8.6 bun 1.4.4 deno 2.9.8 v 0.5.2 zig 0.17.0