trang chủ / đề bài / icpc26_mb_l

Căn chỉnh đo xa lượng tử

Đề bài

Mô tả

Sâu bên trong Khu vực 2026, hai trinh sát Alice và Bob phải đồng bộ các thẻ định vị qua một cây cầu lượng tử chập chờn bằng một bộ thẻ đo xa tổng quát. Mỗi thẻ dữ liệu được xác định duy nhất bởi một dải tần s (1≤s≤S) và một hạng cộng hưởng r (1≤r≤R), được viết dưới dạng xâu s:r.

Chương trình của bạn sẽ được chạy hai lần trong mỗi test để đóng vai cả Alice lẫn Bob, qua đầu vào chuẩn (stdin) và đầu ra chuẩn (stdout):

  • Lần chạy 1 (Alice): Alice nhận N thẻ dữ liệu phân biệt. Cô giấu đúng một thẻ tùy chọn vào bộ đệm lượng tử và sắp xếp N−1 thẻ còn lại thành một dãy hoán vị cụ thể để phát đi.
  • Lần chạy 2 (Bob): Bob nhận dãy N−1 thẻ theo đúng thứ tự Alice đã phát ở lần chạy 1. Bằng cách phân tích cách sắp xếp hoán vị, Bob phải suy ra và in ra chính xác thẻ đã bị giấu.

Hai lần chạy là hai tiến trình độc lập: thông tin duy nhất Bob nhận được từ Alice là dãy N−1 thẻ theo thứ tự cô in ra.

Dữ liệu vào

Với lần chạy 1 (Alice):

  • Dòng 1 chứa xâu first.
  • Dòng 2 chứa ba số nguyên N, S, R cách nhau bởi dấu cách.
  • Dòng 3 chứa N xâu cách nhau bởi dấu cách, là N thẻ phân biệt ban đầu Alice nhận được.

Với lần chạy 2 (Bob):

  • Dòng 1 chứa xâu second.
  • Dòng 2 chứa ba số nguyên N, S, R cách nhau bởi dấu cách.
  • Dòng 3 chứa N−1 xâu cách nhau bởi dấu cách, là dãy thẻ Alice đã in ra ở lần chạy 1.

Dữ liệu ra

Với lần chạy 1 (Alice):

  • Dòng 1: in thẻ bị giấu theo định dạng s:r.
  • Dòng 2: in N−1 thẻ còn lại theo thứ tự bạn chọn, cách nhau bởi đúng một dấu cách.

Với lần chạy 2 (Bob):

  • In đúng một dòng chứa thẻ bị giấu mà Bob suy ra, theo định dạng s:r.

Một test được chấp nhận khi thẻ Bob in ra trùng với thẻ Alice đã giấu (và Alice in ra đúng N thẻ đã cho, mỗi thẻ một lần).

Ràng buộc

  • 4≤N≤13
  • 1≤S≤N−1
  • 1≤R≤2×(N−2)!+1
  • 1≤s≤S và 1≤r≤R với mọi thẻ.
  • N thẻ ban đầu đôi một phân biệt.

Ví dụ

Mỗi dòng của bảng là một lần chạy chương trình. Thẻ bị giấu và thứ tự phát đi phụ thuộc vào chiến lược của lời giải; bảng dưới đây là kết quả của một chiến lược đúng.

Input Output Giải thích
first
5 4 13
1:13 2:4 3:5 1:5 2:6
2:6
2:4 1:5 3:5 1:13
Lần chạy 1 (Alice): cô giấu thẻ 2:6 và phát đi 4 thẻ còn lại theo thứ tự 2:4 1:5 3:5 1:13. Trong đề gốc, Alice cũng giấu 2:6 nhưng phát theo thứ tự 1:13 2:4 3:5 1:5; đó là kết quả của một chiến lược khác, cũng hợp lệ nếu Bob dùng cùng chiến lược.
second
5 4 13
2:4 1:5 3:5 1:13
2:6 Lần chạy 2 (Bob) của cùng test trên: Bob nhận dãy Alice đã phát và in ra đúng thẻ bị giấu 2:6.
first
4 2 5
2:1 1:5 2:3 1:1
1:1
1:5 2:1 2:3
Lần chạy 1 (Alice) của một test khác: Alice giấu 1:1 và phát 1:5 2:1 2:3.
second
4 2 5
1:5 2:1 2:3
1:1 Lần chạy 2 (Bob) của test thứ hai: Bob suy ra thẻ bị giấu là 1:1.

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