IOI 2001 - Ngày 1

Giả sử các trạm gốc điện thoại di động thế hệ thứ tư ở khu vực Tampere hoạt động như sau. Khu vực được chia thành các ô vuông tạo thành ma trận \(S\times S\), có hàng và cột đánh số từ \(0\) đến \(S-1\). Mỗi ô chứa một trạm gốc.

Số điện thoại đang hoạt động trong một ô có thể thay đổi vì điện thoại di chuyển, được bật hoặc được tắt. Mỗi trạm thỉnh thoảng báo độ thay đổi cùng tọa độ ô của mình cho trạm chính. Hãy xử lý các báo cáo này và trả lời tổng số điện thoại đang hoạt động trong những vùng hình chữ nhật được hỏi.

Dữ liệu vào

Mỗi dòng chứa một lệnh và các tham số nguyên theo bảng sau:

Tất cả giá trị đều hợp lệ. Đặc biệt, một cập nhật âm không làm giá trị ô trở thành âm. Chỉ số bắt đầu từ 0; chẳng hạn, với \(S=4\), có \(0\le X,Y\le3\).

Dữ liệu ra

Với mỗi lệnh 2, in một dòng chứa một số nguyên là tổng được hỏi. Không in gì cho các lệnh khác.

Ràng buộc

• \(1\le S\le1024\).
• Giá trị \(V\) của mỗi ô tại mọi thời điểm: \(0\le V\le2^{15}-1=32767\).
• Độ thay đổi: \(-2^{15}\le A\le2^{15}-1\).
• Số lệnh \(U\): \(3\le U\le60002\).
• Tổng số điện thoại trong toàn bảng không vượt quá \(2^{30}\).
• Trong 20 bộ kiểm tra, có 16 bộ với \(S\le512\).

Giới hạn bộ nhớ của kỳ thi gốc là 5 MiB; bản luyện tập này dùng 8 MiB để phù hợp với môi trường chạy hiện nay. Giới hạn thời gian vẫn là 1 giây.

Chấm điểm

Mỗi bộ kiểm tra tương ứng 5 điểm trong thang điểm gốc 100; kết quả đúng và trong giới hạn thời gian nhận toàn bộ điểm của bộ đó.

Lưu ý vào ra

Đọc từ đầu vào chuẩn và ghi ra đầu ra chuẩn. Đề gốc yêu cầu đẩy dữ liệu sau mỗi câu trả lời: với C++, có thể dùng cout << answer << endl << flush;; với C, dùng printf("%d\n", answer); fflush(stdout);. Với Pascal, đọc bằng Read(last); ... Readln; và ghi bằng Writeln(answer);. Công cụ kiểm tra trực tuyến gốc chuyển tệp đầu vào vào đầu vào chuẩn của chương trình.

Ví dụ

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

3
4

Nguồn

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

Những trò chơi Mancala với hạt và hốc là một trong các hình thức giải trí lâu đời nhất. Ioiwari là một biến thể được thiết kế riêng cho IOI. Hai người chơi dùng một bàn tròn có bảy hốc quanh mép, đánh số \(1\) đến \(7\) theo chiều kim đồng hồ. Mỗi người còn có một kho hạt riêng.

Ban đầu, 20 hạt được phân vào bảy hốc, mỗi hốc có ít nhất 2 và nhiều nhất 4 hạt; cả hai kho đều trống. Hai người đi luân phiên. Trong một lượt, người chơi chọn một hốc không rỗng, lấy tất cả hạt trong đó lên tay và để hốc ấy trống. Bắt đầu từ hốc kế tiếp, lần lượt xét các hốc theo chiều kim đồng hồ và làm như sau cho đến khi tay không còn hạt:

• Nếu trên tay còn nhiều hơn một hạt: nếu hốc đang xét đã có 5 hạt, lấy một hạt từ hốc chuyển vào kho của mình, không lấy bớt hạt trên tay; nếu không, đặt một hạt từ tay vào hốc.
• Nếu trên tay chỉ còn một hạt: nếu hốc đang xét có từ 1 đến 4 hạt, chuyển tất cả hạt trong hốc cùng hạt trên tay vào kho của mình. Nếu hốc có 0 hoặc 5 hạt, chuyển hạt trên tay vào kho của đối phương.

Trò chơi kết thúc khi sau một lượt đi, cả bảy hốc đều trống. Người có nhiều hạt trong kho hơn thắng; nếu bằng nhau thì hòa.

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

Tương tác

Chương trình của bạn là người chơi 1, đối thủ là người chơi 2. Đầu tiên, đọc một dòng gồm bảy số nguyên \(p_1,\ldots,p_7\) từ đầu vào chuẩn, là số hạt ban đầu trong các hốc. Sau đó:

• Đến lượt mình, in số hiệu hốc không rỗng mà bạn chọn ra đầu ra chuẩn.
• Đến lượt đối thủ, đọc số hiệu hốc họ chọn từ đầu vào chuẩn.
• Kết thúc khi tất cả hốc trống sau một lượt đi.

Phải đẩy dữ liệu sau khi in nước đi. Với C++, dùng cout << mymove << endl << flush; và đọc bằng cin >> last;. Với C, dùng printf("%d\n", mymove); fflush(stdout); và scanf("%d", &last);. Với Pascal, dùng Writeln(mymove); và Readln(last);.

Công cụ gốc

Công cụ ioiwari2 trên Linux, hoặc ioiwari2.exe trên Windows, chơi tối ưu ở vai người chơi 2 từ vị trí cố định 4 3 2 4 2 3 2. Công cụ in vị trí này trước, sau đó đọc các nước đi của người chơi 1 và in nước đi của mình. Có thể chạy hai chương trình ở hai cửa sổ và chuyển các nước đi bằng tay. Công cụ gốc ghi cuộc đối thoại vào ioiwari.out.

Chấm điểm

Trong thang điểm gốc, mỗi ván thắng được 4 điểm, hòa được 2 điểm, thua được 0 điểm. Bảng tổng quan kỳ thi quy định 25 ván, tổng tối đa 100 điểm.

Bản luyện tập sử dụng 24 vị trí xuất phát còn có trong kho dữ liệu chính thức; không bổ sung một ván thứ 25 giả định. Cả 24 bộ kiểm tra có trọng số bằng nhau: thắng nhận toàn bộ điểm của bộ đó, hòa nhận một nửa, thua nhận 0. Tổng điểm được quy đổi về thang 100. Đây là điều chỉnh so với số ván và điểm tuyệt đối của kỳ thi gốc.

Ví dụ

4 3 2 4 2 3 2
3
4
7

2
5
5

Nguồn

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

Ông già Noel và các phụ tá thường trao đổi thông điệp bí mật bằng ngôn ngữ 25. Bảng chữ cái của ngôn ngữ này gồm 25 chữ cái Latin in hoa từ A đến Y, theo thứ tự thông thường; không có chữ Z.

Mỗi từ chứa đúng 25 chữ cái khác nhau. Viết từ vào bảng \(5\times5\) theo từng hàng, từ trái sang phải và từ trên xuống dưới. Một từ hợp lệ phải có các chữ cái tăng dần trên mỗi hàng và mỗi cột.

Ví dụ, từ ADJPTBEKQUCGLRVFINSWHMOXY cho bảng:

A D J P T
B E K Q U
C G L R V
F I N S W
H M O X Y

Đây là một từ hợp lệ. Ngược lại, ADJPTBEGQUCKLRVFINSWHMOXY không hợp lệ vì thứ tự tăng dần bị vi phạm ở cột thứ hai và cột thứ ba.

Ông già Noel có một từ điển gồm tất cả các từ hợp lệ, sắp xếp theo thứ tự từ điển và đánh số từ \(1\). Chẳng hạn, từ số 1 là ABCDEFGHIJKLMNOPQRSTUVWXY; từ số 2 là ABCDEFGHIJKLMNOPQRSUTVWXY, trong đó T và U đổi chỗ so với từ đầu tiên. Từ điển có không quá \(2^{31}\) từ.

Hãy xác định số thứ tự của một từ hợp lệ cho trước, hoặc tìm từ ứng với một số thứ tự cho trước.

Dữ liệu vào

Đọc từ đầu vào chuẩn hai dòng:

• Dòng đầu chứa một ký tự W hoặc N.
• Nếu ký tự đó là W, dòng thứ hai chứa một từ hợp lệ gồm 25 chữ cái.
• Nếu ký tự đó là N, dòng thứ hai chứa số thứ tự của một từ có trong từ điển.

Dữ liệu ra

In một dòng ra đầu ra chuẩn: số thứ tự của từ nếu chế độ là W, hoặc từ tương ứng nếu chế độ là N.

Chấm điểm

Có 20 bộ kiểm tra, mỗi bộ tương ứng 5 điểm trong thang điểm gốc 100. Kết quả đúng và trong giới hạn thời gian nhận toàn bộ điểm của bộ kiểm tra; ngược lại nhận 0 điểm.

Ví dụ

W
ABCDEFGHIJKLMNOPQRSUTVWXY

2

N
2

ABCDEFGHIJKLMNOPQRSUTVWXY

Nguồn

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