IOI 2001 - Ngày 2

Score là trò chơi hai người cùng di chuyển một quân cờ. Bàn cờ có \(N\) vị trí, đánh số từ \(1\) đến \(N\), và các mũi tên có hướng nối các vị trí. Mỗi vị trí thuộc sở hữu của một người chơi và có một giá trị nguyên dương; tất cả giá trị đôi một khác nhau. Quân cờ bắt đầu ở vị trí 1, điểm ban đầu của mỗi người bằng 0.

Gọi vị trí hiện tại ở đầu một lượt là \(C\). Lượt đi gồm hai bước:

1. Nếu giá trị của \(C\) lớn hơn điểm hiện tại của người sở hữu \(C\), thay điểm của người đó bằng giá trị của \(C\). Nếu không, điểm giữ nguyên. Điểm của người kia không thay đổi.
2. Người sở hữu \(C\) chọn một mũi tên đi ra từ \(C\) và chuyển quân cờ đến đầu kia của mũi tên. Một người có thể đi nhiều lượt liên tiếp.

Trò chơi kết thúc khi quân cờ trở lại vị trí 1. Người có điểm cao hơn thắng. Các mũi tên luôn bảo đảm:

• Ở mỗi vị trí đều chọn được một mũi tên đi ra.
• Từ vị trí 1 có thể đi theo các mũi tên tới mọi vị trí.
• Trò chơi chắc chắn kết thúc sau hữu hạn lượt đi.

Hãy viết chương trình chơi và thắng. Mọi ván dùng để chấm đều có chiến lược thắng cho chương trình của bạn, dù bạn có đi trước hay không. Đối thủ chơi tối ưu: một khi bạn để họ có cơ hội thắng, họ sẽ thắng.

Tương tác

Bạn là người chơi 1, đối thủ là người chơi 2. Trước tiên đọc mô tả bàn cờ từ đầu vào chuẩn:

• Dòng đầu chứa \(N\), với \(1\le N\le1000\).
• \(N\) dòng tiếp theo, mỗi dòng có \(N\) số. Số thứ \(j\) trên dòng thứ \(i\) là 1 nếu có mũi tên từ \(i\) đến \(j\), ngược lại là 0.
• Dòng tiếp theo chứa \(N\) số là chủ sở hữu các vị trí: 1 nếu thuộc bạn, 2 nếu thuộc đối thủ.
• Dòng cuối chứa \(N\) giá trị của các vị trí, đôi một khác nhau, mỗi giá trị từ \(1\) đến \(N\).

Sau đó ván chơi bắt đầu tại vị trí 1. Đến lượt bạn, in vị trí đích \(P\) của một mũi tên đi ra hợp lệ; đến lượt đối thủ, đọc vị trí đích \(P\) của họ. Luôn có \(1\le P\le N\). Thoát chương trình khi quân cờ trở về vị trí 1.

Đẩy dữ liệu sau mỗi nước đi: trong C++, dùng cout << target << endl << flush; và đọc cin >> target;; trong C, dùng printf("%d\n", target); fflush(stdout); và scanf("%d", &target);; trong Pascal, dùng Writeln(target); và Readln(target);.

Công cụ gốc

Công cụ score2 trên Linux, hoặc score2.exe trên Windows, đọc bàn cờ từ score.in theo định dạng trên, rồi in mô tả đó ra đầu ra chuẩn. Sau đó công cụ dùng chiến lược ngẫu nhiên, đọc nước đi của bạn từ đầu vào chuẩn và in nước đi của mình. Công cụ thử này không phải đối thủ tối ưu dùng khi chấm.

Chấm điểm

Có 20 bộ kiểm tra, mỗi bộ tương ứng 5 điểm. Thắng ván chơi và đáp ứng giới hạn thời gian nhận toàn bộ điểm, ngược lại nhận 0 điểm.

Trong quy trình chấm gốc, chương trình trước hết đấu với một chương trình khác với giới hạn thời gian lớn hơn giới hạn chính thức 1 giây; toàn bộ dữ liệu vào và ra được ghi lại. Sau đó chương trình được chạy lại với đầu vào từ tệp ghi đó để đo thời gian chính thức. Kết quả in ra trong hai lần phải giống nhau. Thời gian của tiến trình đối thủ không được cộng vào thời gian chương trình thí sinh.

Ví dụ

4
0 1 0 0
0 0 1 1
0 0 0 1
1 0 0 0
1 1 2 2
1 3 4 2
1

2
4

Nguồn

Đề gốc IOI 2001. Bảng tổng quan ngày 2.

Thuật toán mã hóa AES làm việc với các khối 128 bit. Với bản rõ \(p\) và khóa \(k\), hàm mã hóa \(E\) tạo ra bản mã \(c=E(p,k)\). Hàm giải mã \(D\) là hàm ngược tương ứng: \(D(E(p,k),k)=p\) và \(E(D(c,k),k)=c\).

Double AES dùng hai khóa độc lập \(k_1,k_2\) liên tiếp, trước tiên \(k_1\) rồi đến \(k_2\), tạo bản mã \(c_2=E(E(p,k_1),k_2)\).

Trong bài này, bạn còn được cho số nguyên \(s\). Chỉ \(4s\) bit ngoài cùng bên trái của mỗi khóa có thể khác 0; \(128-4s\) bit còn lại ở bên phải đều bằng 0. Bạn biết bản rõ \(p\), bản mã kép tương ứng \(c_2\) và số \(s\). Hãy khôi phục một cặp khóa phù hợp.

Đây là bài chỉ nộp kết quả: nộp các khóa tìm được, không nộp chương trình khôi phục khóa. Các thuật toán AES mã hóa và giải mã có trong thư viện của kỳ thi.

Dữ liệu vào

Có 10 bộ dữ liệu trong các tệp double1.in đến double10.in, được cung cấp trong tệp đính kèm double-inputs.zip. Mỗi tệp có ba dòng:

• Dòng đầu chứa \(s\), với \(1\le s\le5\).
• Dòng thứ hai chứa bản rõ \(p\).
• Dòng thứ ba chứa bản mã kép \(c_2\).

Mỗi khối được biểu diễn bằng đúng 32 chữ số thập lục phân từ 0 đến 9 và A đến F. Mọi bộ dữ liệu đều có lời giải.

Dữ liệu ra

Trên bản luyện tập này, chọn ngôn ngữ OUTPUT và nộp một tệp ZIP chứa 10 tệp kết quả ngay tại thư mục gốc của ZIP, không đặt trong thư mục con. Tên tệp kết quả được ánh xạ từ các tệp đầu vào gốc như sau:

Nội dung mỗi tệp giữ nguyên định dạng của kỳ thi gốc. Tệp ứng với đầu vào số \(I\), với \(1\le I\le10\), có ba dòng:

• Dòng đầu là #FILE double I, trong đó \(I\) là số thứ tự tệp đầu vào.
• Dòng thứ hai là khóa \(k_1\).
• Dòng thứ ba là khóa \(k_2\).

Mỗi khóa phải gồm đúng 32 chữ số thập lục phân in hoa, có các bit không liên quan bằng 0 như đã quy định, và thỏa mãn \(c_2=E(E(p,k_1),k_2)\). Nếu có nhiều cặp khóa, chỉ cần nộp một cặp.

Chẳng hạn, 01.out phải bắt đầu bằng #FILE double 1, còn 10.out bắt đầu bằng #FILE double 10. Số trong dòng #FILE là số bộ dữ liệu gốc, không thêm số 0 ở đầu như trong tên tệp ZIP.

Thư viện dùng thử

Tệp đính kèm double-aes-templates.zip cung cấp mã nguồn C/C++ tương thích với giao diện AES-128 của đề gốc, gồm aeslibc.h, aeslibc.c, chương trình gọi mẫu aestoolc.c và hướng dẫn README.md. Đây là bản cài đặt hiện đại, không phải thư viện nhị phân gốc. Sau khi giải nén, có thể biên dịch và chạy chương trình mẫu bằng:

gcc -std=c99 -O2 aestoolc.c aeslibc.c -o aestoolc
./aestoolc

Chương trình mẫu đọc từ đầu vào chuẩn một bản rõ và một khóa, mỗi khối gồm 32 chữ số thập lục phân in hoa, rồi in bản mã sau một lần mã hóa. Để mã hóa kép, gọi encrypt hai lần với hai khóa theo thứ tự \(k_1,k_2\). Chương trình mẫu chỉ minh họa cách gọi thư viện, không khôi phục khóa. Khi dùng thư viện trong chương trình của bạn, khai báo #include "aeslibc.h" và liên kết với phần cài đặt trong aeslibc.c.

Các tệp đối tượng và thư viện Pascal được mô tả trong phần giao diện gốc dưới đây chỉ thuộc môi trường kỳ thi năm 2001; chúng không nằm trong gói dùng thử hiện tại.

Thư viện gốc

Thư viện C/C++ dùng aeslibc.h và aeslibc.o, với các khai báo:

typedef char HexStr[33];
typedef unsigned char Block[16];
void hexstr2block(const HexStr hs, Block b);
void block2hexstr(const Block b, HexStr hs);
void encrypt(const Block p, const Block k, Block c);
void decrypt(const Block c, const Block k, Block p);

HexStr là chuỗi ký tự 0–9, A–F kết thúc bằng \0; Block chứa 128 bit. Hai hàm đầu chuyển đổi hai cách biểu diễn. encrypt ghi \(E(p,k)\) vào c; decrypt ghi \(D(c,k)\) vào p. Chương trình aestoolc.c minh họa cách dùng thư viện.

Thư viện FreePascal dùng aeslibp.p, aeslibp.ppu, aeslibp.o trên Linux, hoặc aeslibp.p, aeslibp.ppw, aeslibp.ow trên Windows:

type
  HexStr = String[32];
  Block = array[0..15] of Byte;
procedure HexStrToBlock(const hs: HexStr; var b: Block);
procedure BlockToHexStr(const b: Block; var hs: HexStr);
procedure Encrypt(const p, k: Block; var c: Block);
procedure Decrypt(const c, k: Block; var p: Block);

Chương trình aestoolp.pas minh họa cách dùng thư viện Pascal. Trong môi trường gốc, biên dịch bằng fpc aestoolp.pas, hoặc gcc -o aestoolc aestoolc.c aeslibc.o cho C. Trong IDE Pascal, mở tệp rồi chọn Run -> Run; trong RHIDE, mở aestoolc.c, thêm aeslibc.o ở Options -> Linker Options -> Parameter, rồi chọn Run -> Run.

Một chương trình tốt có thể khôi phục khóa trong ít hơn 10 giây cho mọi dữ liệu cho phép; đây là gợi ý của đề gốc, không phải giới hạn chạy của một bài nộp mã nguồn.

Chấm điểm

Bộ dữ liệu 1 tương ứng 1 điểm; mỗi bộ từ 2 đến 10 tương ứng 11 điểm. Tổng điểm tối đa là 100. Mỗi bộ chỉ nhận điểm nếu cặp khóa hợp lệ.

Ví dụ

1
00112233445566778899AABBCCDDEEFF
6323B4A5BC16C479ED6D94F5B58FF0C2

#FILE double 0
A0000000000000000000000000000000
70000000000000000000000000000000

Nguồn

Đề gốc IOI 2001. Bảng tổng quan ngày 2.

Một công ty công nghệ cao của Phần Lan có một nhà kho hình chữ nhật rất lớn, do một người quản lý và một công nhân phụ trách. Bốn cạnh theo thứ tự quanh kho được gọi là trái, trên, phải, dưới. Kho được chia thành các ô vuông bằng nhau; hàng được đánh số từ \(1\) từ trên xuống, cột được đánh số từ \(1\) từ trái sang phải. Lối vào nằm ở góc trên bên trái.

Các công-ten-nơ chứa thiết bị quý giá có số hiệu đôi một khác nhau, mỗi công-ten-nơ chiếm một ô. Chúng không bao giờ bị đưa ra khỏi kho; thỉnh thoảng một công-ten-nơ mới được đưa vào. Số công-ten-nơ có thể đến luôn nhỏ hơn cả số hàng và số cột của kho.

Người công nhân xếp chúng gần góc trên bên trái theo quy tắc sau. Khi đưa công-ten-nơ có số hiệu \(k\) vào một hàng, anh đi từ trái sang phải và tìm công-ten-nơ đầu tiên có số hiệu lớn hơn \(k\):

• Nếu không tìm thấy, đặt \(k\) ngay sau công-ten-nơ ngoài cùng bên phải của hàng.
• Nếu tìm thấy công-ten-nơ \(l\), thay \(l\) bằng \(k\), rồi đưa \(l\) vào hàng tiếp theo theo cùng quy tắc.
• Nếu hàng đang xét trống, đặt công-ten-nơ vào ô ngoài cùng bên trái.

Mỗi công-ten-nơ mới bắt đầu được đưa vào hàng đầu tiên.

Ví dụ, khi các công-ten-nơ \(3,4,9,2,5,1\) đến theo thứ tự này, cách xếp cuối cùng là:

1 4 5
2 9
3

Người quản lý hỏi: “Công-ten-nơ 5 có đến trước công-ten-nơ 4 không?” Người công nhân trả lời: “Không, điều đó không thể xảy ra.” Người quản lý bèn nghĩ rằng có thể suy ra thứ tự đến chỉ từ cách xếp. Nhưng người công nhân giải thích rằng nói chung không thể xác định duy nhất: cách xếp này cũng có thể do thứ tự \(3,2,1,4,9,5\), hoặc \(3,2,1,9,4,5\), hay 14 thứ tự khác tạo ra.

Không muốn để lộ rằng người công nhân có vẻ thông minh hơn mình, người quản lý bỏ đi. Hãy giúp ông ấy: từ cách xếp hiện tại, liệt kê tất cả thứ tự đến có thể có.

Dữ liệu vào

Đọc từ đầu vào chuẩn:

• Dòng đầu chứa \(R\), số hàng có công-ten-nơ.
• \(R\) dòng tiếp theo mô tả các hàng từ trên xuống. Mỗi dòng bắt đầu bằng \(M\), số công-ten-nơ trong hàng, rồi đến \(M\) số hiệu theo thứ tự từ trái sang phải.

Các số hiệu \(I\) thỏa mãn \(1\le I\le50\) và đôi một khác nhau. Tổng số công-ten-nơ \(N\) thỏa mãn \(1\le N\le13\).

Dữ liệu ra

In mỗi thứ tự đến có thể có trên một dòng gồm \(N\) số hiệu. Không in số lượng thứ tự ở đầu. Các dòng có thể theo bất kỳ thứ tự nào; để nhận toàn bộ điểm, mỗi thứ tự đến hợp lệ phải xuất hiện đúng một lần.

Chấm điểm

Có 25 bộ kiểm tra. Điểm gốc của mỗi bộ được tính như sau:

• Có thứ tự không thể xảy ra, hoặc không in thứ tự nào: 0 điểm.
• In tất cả thứ tự có thể có, mỗi thứ tự đúng một lần: 4 điểm.
• In ít nhất một nửa số thứ tự có thể có, mỗi thứ tự đúng một lần, nhưng chưa đủ tất cả: 2 điểm.
• Các trường hợp còn lại, tức có ít hơn một nửa số thứ tự hoặc có thứ tự bị lặp, nhưng tất cả thứ tự in ra đều hợp lệ: 1 điểm.

Ví dụ

3
3 1 4 5
2 2 9
1 3

3 2 1 4 9 5
3 2 1 9 4 5
3 4 2 1 9 5
3 2 4 1 9 5
3 2 9 1 4 5
3 9 2 1 4 5
3 4 2 9 1 5
3 4 9 2 1 5
3 2 4 9 1 5
3 2 9 4 1 5
3 9 2 4 1 5
3 4 2 9 5 1
3 4 9 2 5 1
3 2 4 9 5 1
3 2 9 4 5 1
3 9 2 4 5 1

2
2 1 2
1 3

3 1 2
1 3 2

Nguồn

Đề gốc IOI 2001. Bảng tổng quan ngày 2.