JOI 2025 - Tuyển chọn mùa xuân - Ngày 3

Bộ đề bài

Trở lại kỳ thi
# Bài tập Điểm Thời gian: Giới hạn bộ nhớ
1 JOI 2025 - Bitaro the Brave 3 100 (p) 2.0s 1G
2 JOI 2025 - Conference 100 (p) 2.0s 1G
3 JOI 2025 - Multi Communication 100 (p) 2.0s 128M

1. JOI 2025 - Bitaro the Brave 3

Điểm: 100 (p) Thời gian: 2.0s Bộ nhớ: 1G Input: bàn phím Output: màn hình

Người hùng Bitaro sắp thực hiện nhiệm vụ phòng thủ để bảo vệ ngôi làng khỏi quái vật. Độ khó của trận phòng thủ là một số nguyên từ \(1\) đến \(L\), được chọn khi bắt đầu nhiệm vụ. Trong trận có độ khó \(\ell\) (\(1 \le \ell \le L\)), lượng máu của mỗi quái vật gấp \(\ell\) lần lượng máu của nó ở độ khó \(1\).

Trận phòng thủ kéo dài \(T\) giây, trong đó có \(N\) quái vật xuất hiện. Các quái vật được đánh số từ \(1\) đến \(N\). Thời điểm \(t\) (\(0 \le t \le T\)) là thời điểm sau khi trận bắt đầu \(t\) giây. Quái vật \(i\) xuất hiện tại thời điểm \(S_i\) (\(0 \le S_i<T\)), có sức mạnh \(P_i\) và có lượng máu bằng \(\ell\times H_i\) khi độ khó là \(\ell\).

Trong trận, Bitaro có thể thực hiện hành động sau tùy ý nhiều lần:

  • Chọn một quái vật hiện đang xuất hiện và dành \(1\) giây để tấn công nó. Lượng máu của quái vật giảm đi \(1\). Khi máu giảm về \(0\), quái vật bị đánh bại và không thể bị tấn công thêm.

Khi thời điểm \(T\) đến, trận phòng thủ kết thúc. Gọi \(h_i\) là lượng máu của quái vật \(i\) ngay sau thời điểm \(T\). Điểm phạt của trận được tính bằng

\[ h_1P_1+h_2P_2+\cdots+h_NP_N. \]

Bitaro hoàn thành nhiệm vụ khi và chỉ khi điểm phạt không vượt quá ngưỡng \(m\) do nhiệm vụ quy định.

Hoàn thành nhiệm vụ ở độ khó càng cao thì phần thưởng càng lớn, nên Bitaro muốn biết độ khó lớn nhất mà mình có thể hoàn thành. Tuy nhiên, ngưỡng \(m\) chưa được thông báo trước. Vì vậy, Bitaro xét \(Q\) ngưỡng có thể có là \(M_1,M_2,\ldots,M_Q\).

Cho thông tin về trận phòng thủ và các ngưỡng, với mỗi ngưỡng hãy xác định có thể hoàn thành nhiệm vụ hay không và, nếu có, tìm độ khó lớn nhất mà Bitaro có thể hoàn thành.

Dữ liệu vào

  • Dòng đầu tiên chứa ba số nguyên \(N,L,T\).
  • Trong \(N\) dòng tiếp theo, dòng thứ \(i\) chứa ba số nguyên \(S_i,H_i,P_i\).
  • Dòng tiếp theo chứa số nguyên \(Q\).
  • Trong \(Q\) dòng tiếp theo, dòng thứ \(j\) chứa số nguyên \(M_j\).

Các số trên cùng một dòng được ngăn cách bởi dấu cách.

Dữ liệu ra

In \(Q\) dòng. Dòng thứ \(j\) chứa độ khó lớn nhất mà Bitaro có thể hoàn thành nhiệm vụ khi \(m=M_j\). Nếu không thể hoàn thành ở bất kỳ độ khó nào, in 0.

Ràng buộc

  • \(1 \le N \le 6000\).
  • \(1 \le L \le 10000000\).
  • \(1 \le T \le 10^{18}\).
  • \(0 \le S_i<T\) với mọi \(1 \le i \le N\).
  • \(1 \le H_i\) và \(1 \le P_i\) với mọi \(1 \le i \le N\).
  • \(H_1P_1+H_2P_2+\cdots+H_NP_N \le 10^{11}\).
  • \(1 \le Q \le 1000000\).
  • \(0 \le M_j \le 10^{18}\) với mọi \(1 \le j \le Q\).
  • \(M_1<M_2<\cdots<M_Q\).
  • Tất cả các giá trị trong dữ liệu vào đều là số nguyên.

Chấm điểm

  1. \(1\) điểm: \(N \le 30\), \(Q=1\), \(M_1=0\), \(L=1\).
  2. \(3\) điểm: \(N \le 30\), \(Q=1\), \(M_1=0\).
  3. \(10\) điểm: \(N \le 30\), \(Q \le 3\).
  4. \(10\) điểm: \(Q \le 3\).
  5. \(35\) điểm: \(N \le 30\).
  6. \(8\) điểm: \(N \le 400\).
  7. \(20\) điểm: \(N \le 1800\).
  8. \(13\) điểm: Không có ràng buộc bổ sung.

Ví dụ

Ví dụ 1

Input 
2 2 10
0 9 2
8 5 1
3
0
20
40
Output 
0
1
2
Giải thích

Ở độ khó \(1\), Bitaro có thể đạt điểm phạt \(4\) bằng cách hành động như bảng dưới đây. Không thể đạt điểm phạt từ \(3\) trở xuống.

Thời điểm hoặc khoảng thời gian Sự kiện
\(0\) Quái vật \(1\) xuất hiện với \(9\) máu.
Từ \(0\) đến \(8\) Tấn công quái vật \(1\) tổng cộng \(8\) lần, làm máu của nó giảm từ \(9\) xuống \(1\).
\(8\) Quái vật \(2\) xuất hiện với \(5\) máu.
Từ \(8\) đến \(9\) Tấn công quái vật \(2\) một lần, làm máu của nó giảm từ \(5\) xuống \(4\).
Từ \(9\) đến \(10\) Tấn công quái vật \(1\) một lần, làm máu của nó giảm từ \(1\) xuống \(0\).
\(10\) Quái vật \(1\) bị đánh bại.
\(10\) Trận kết thúc. Điểm phạt là \(0\times P_1+4\times P_2=4\).

Ở độ khó \(2\), Bitaro có thể đạt điểm phạt \(26\) như sau. Không thể đạt điểm phạt từ \(25\) trở xuống.

Thời điểm hoặc khoảng thời gian Sự kiện
\(0\) Quái vật \(1\) xuất hiện với \(18\) máu.
Từ \(0\) đến \(8\) Tấn công quái vật \(1\) tổng cộng \(8\) lần, làm máu của nó giảm từ \(18\) xuống \(10\).
\(8\) Quái vật \(2\) xuất hiện với \(10\) máu.
Từ \(8\) đến \(10\) Tấn công quái vật \(1\) tổng cộng \(2\) lần, làm máu của nó giảm từ \(10\) xuống \(8\).
\(10\) Trận kết thúc. Điểm phạt là \(8\times P_1+10\times P_2=26\).

Vì \(L=2\), không thể chọn độ khó từ \(3\) trở lên. Do đó:

  • Với \(M_1=0\), không thể hoàn thành nhiệm vụ ở bất kỳ độ khó nào, nên dòng thứ nhất in \(0\).
  • Với \(M_2=20\), độ khó lớn nhất có thể hoàn thành là \(1\), nên dòng thứ hai in \(1\).
  • Với \(M_3=40\), độ khó lớn nhất có thể hoàn thành là \(2\), nên dòng thứ ba in \(2\).

Ví dụ này thỏa mãn ràng buộc của các nhóm \(3,4,5,6,7,8\).

Ví dụ 2

Input 
3 1 100000000000
60000000000 30000000000 1
30000000000 45000000000 1
10000000000 10000000000 1
1
0
Output 
0
Giải thích

Ví dụ này thỏa mãn ràng buộc của tất cả các nhóm.

Ví dụ 3

Input 
3 10000000 100000000
60000000 4 1
30000000 6 1
0 2 1
1
0
Output 
7000000
Giải thích

Ví dụ này thỏa mãn ràng buộc của các nhóm \(2,3,4,5,6,7,8\).

Ví dụ 4

Input 
5 20 100
0 3 1
20 2 2
40 1 3
60 4 4
80 2 5
11
0
50
100
150
200
250
300
350
400
450
500
Output 
6
8
10
12
13
15
16
18
19
20
20
Giải thích

Ví dụ này thỏa mãn ràng buộc của các nhóm \(5,6,7,8\).

Ví dụ 5

Input 
15 10000000 1000000000000
160278118759 43084 33592
442653603914 19490 23090
824219815410 50858 89563
502303340628 56629 45080
495062829942 87342 28821
234536700105 45384 34328
396080693809 78081 50812
734374391045 40873 92012
122606844331 25451 30426
204076581972 58431 13989
495156368673 54276 41670
812963939390 27614 50228
405067019838 96324 18477
464546304875 67562 45956
528559327980 41759 15546
10
216000000000000
1728000000000000
5832000000000000
13824000000000000
27000000000000000
46656000000000000
74088000000000000
110592000000000000
157464000000000000
216000000000000000
Output 
995176
1135557
1431775
1824183
2359362
3059523
3942014
5106209
6594716
8448125
Giải thích

Ví dụ này thỏa mãn ràng buộc của các nhóm \(5,6,7,8\).

Giới hạn

Giới hạn thời gian là \(2\) giây; giới hạn bộ nhớ là \(1024\) MB.

Nguồn

Đề bài của Ủy ban Olympic Tin học Nhật Bản, JOI 2024/2025, vòng tuyển chọn mùa xuân, ngày thi thứ ba. Đề gốc và bản dịch tiếng Việt được cung cấp theo giấy phép CC BY-SA 4.0.

2. JOI 2025 - Conference

Điểm: 100 (p) Thời gian: 2.0s Bộ nhớ: 1G Input: bàn phím Output: màn hình

Chủ tịch K dự định tổ chức một chuỗi hội nghị trong \(N\) ngày. Mỗi ngày có đúng một hội nghị, được tổ chức tại một trong ba địa điểm: địa điểm chính A hoặc một trong hai địa điểm phụ B, C.

Thông tin địa điểm được cho bởi xâu \(S\) gồm các ký tự A, B, C và ?. Với ngày thứ \(i\) (\(1 \le i \le N\)):

  • Nếu ký tự thứ \(i\) của \(S\) là A, B hoặc C, hội nghị ngày đó được tổ chức tại địa điểm tương ứng.
  • Nếu ký tự thứ \(i\) là ?, địa điểm tổ chức hội nghị ngày đó chưa được quyết định.

Vì hội nghị vào ngày đầu tiên và ngày thứ \(N\) dự kiến có nhiều người tham gia, hai hội nghị này đã được ấn định tổ chức tại địa điểm A.

Chủ tịch K cần chọn một trong ba địa điểm A, B, C cho mỗi hội nghị chưa có địa điểm. Để giảm việc di chuyển, ông muốn tối thiểu hóa số chỉ số \(j\) (\(1 \le j \le N-1\)) mà địa điểm của ngày thứ \(j\) khác địa điểm của ngày thứ \(j+1\).

Ông xét \(Q\) kịch bản độc lập. Trong kịch bản thứ \(k\), trong số các hội nghị chưa có địa điểm, ông phải chọn đúng \(X_k\) hội nghị tổ chức tại A, đúng \(Y_k\) hội nghị tại B và đúng \(Z_k\) hội nghị tại C. Hãy tìm số chỉ số \(j\) nhỏ nhất có thể theo yêu cầu trên cho từng kịch bản.

Dữ liệu vào

  • Dòng đầu tiên chứa số nguyên \(N\).
  • Dòng thứ hai chứa xâu \(S\).
  • Dòng thứ ba chứa số nguyên \(Q\).
  • Trong \(Q\) dòng tiếp theo, dòng thứ \(k\) chứa ba số nguyên \(X_k,Y_k,Z_k\), ngăn cách bởi dấu cách.

Dữ liệu ra

In \(Q\) dòng. Dòng thứ \(k\) chứa số chỉ số \(j\) nhỏ nhất mà địa điểm hội nghị của ngày thứ \(j\) và ngày thứ \(j+1\) khác nhau, khi phân công các hội nghị chưa có địa điểm theo kịch bản thứ \(k\).

Ràng buộc

  • \(2 \le N \le 300000\).
  • \(S\) là xâu độ dài \(N\), chỉ gồm các ký tự A, B, C, ?.
  • Ký tự đầu tiên và ký tự thứ \(N\) của \(S\) đều là A.
  • \(1 \le Q \le 200000\).
  • \(0 \le X_k\), \(0 \le Y_k\), \(0 \le Z_k\) với mọi \(1 \le k \le Q\).
  • \(X_k+Y_k+Z_k\) bằng số ký tự ? trong \(S\) với mọi \(1 \le k \le Q\).
  • \(N,Q,X_k,Y_k,Z_k\) đều là số nguyên.

Chấm điểm

  1. \(4\) điểm: \(N \le 50\) và số ký tự ? trong \(S\) không quá \(13\).
  2. \(7\) điểm: \(N \le 500\).
  3. \(13\) điểm: \(N \le 5000\), \(Q \le 10\).
  4. \(18\) điểm: \(N \le 5000\).
  5. \(12\) điểm: \(Q \le 10\).
  6. \(8\) điểm: \(S\) không chứa C và \(Z_k=0\) với mọi \(1 \le k \le Q\).
  7. \(13\) điểm: \(Z_k=0\) với mọi \(1 \le k \le Q\).
  8. \(25\) điểm: Không có ràng buộc bổ sung.

Ví dụ

Ví dụ 1

Input 
9
A??B??C?A
3
1 3 1
4 1 0
0 0 5
Output 
3
4
4
Giải thích

Trong kịch bản thứ nhất, trong \(5\) hội nghị chưa có địa điểm, cần chọn \(1\) hội nghị tại A, \(3\) hội nghị tại B và \(1\) hội nghị tại C. Chẳng hạn, có thể thu được xâu địa điểm ABBBBCCAA. Khi đó, các chỉ số \(j\) mà hai ngày liên tiếp có địa điểm khác nhau là \(1,5,7\), tổng cộng \(3\) chỉ số. Không có cách nào giảm số này xuống \(2\) hoặc ít hơn, nên dòng thứ nhất in \(3\).

Trong kịch bản thứ hai, trong \(5\) hội nghị chưa có địa điểm, cần chọn \(4\) hội nghị tại A và \(1\) hội nghị tại B. Chẳng hạn, có thể thu được xâu địa điểm AAABBACAA. Các chỉ số \(j\) cần đếm là \(3,5,6,7\), tổng cộng \(4\) chỉ số. Không có cách nào giảm số này xuống \(3\) hoặc ít hơn, nên dòng thứ hai in \(4\).

Trong kịch bản thứ ba, cả \(5\) hội nghị chưa có địa điểm đều phải được tổ chức tại C. Các chỉ số \(j\) cần đếm là \(1,3,4,8\), tổng cộng \(4\) chỉ số, nên dòng thứ ba in \(4\).

Ví dụ này thỏa mãn ràng buộc của các nhóm \(1,2,3,4,5,8\).

Ví dụ 2

Input 
12
A???A?B????A
4
0 8 0
2 6 0
7 1 0
3 5 0
Output 
4
4
2
2
Giải thích

Ví dụ này thỏa mãn ràng buộc của tất cả các nhóm.

Ví dụ 3

Input 
28
ACB??B???BCB??B????B?AAA?BBA
26
6 1 6
4 5 4
2 3 8
9 2 2
11 0 2
8 4 1
11 0 2
2 0 11
0 1 12
12 1 0
10 3 0
1 4 8
3 7 3
2 8 3
1 3 9
11 1 1
7 0 6
6 4 3
8 4 1
0 10 3
13 0 0
11 1 1
0 6 7
2 8 3
9 0 4
0 0 13
Output 
15
11
13
13
15
12
15
15
16
15
13
12
10
9
13
15
15
11
12
9
15
15
11
9
15
17
Giải thích

Ví dụ này thỏa mãn ràng buộc của các nhóm \(1,2,4,8\).

Giới hạn

Giới hạn thời gian là \(2\) giây; giới hạn bộ nhớ là \(1024\) MB.

Nguồn

Đề bài của Ủy ban Olympic Tin học Nhật Bản, JOI 2024/2025, vòng tuyển chọn mùa xuân, ngày thi thứ ba. Đề gốc và bản dịch tiếng Việt được cung cấp theo giấy phép CC BY-SA 4.0.

3. JOI 2025 - Multi Communication

Điểm: 100 (p) Thời gian: 2.0s Bộ nhớ: 128M Input: bàn phím Output: màn hình

Đây là bài chỉ nộp kết quả (output-only).

Chủ tịch K chuẩn bị một trò chơi cho những người tham gia trại huấn luyện mùa xuân. Có \(N\) người tham gia, được đánh số từ \(1\) đến \(N\). Mỗi người có một tấm bảng. Trò chơi diễn ra như sau:

  1. Chủ tịch K chọn một người làm người cha; tất cả những người còn lại là người con. Ông không thông báo cho những người tham gia ai được chọn làm người cha.
  2. Chủ tịch K viết ký tự T lên bảng của người cha và ký tự F lên bảng của tất cả những người con.
  3. Mỗi người đọc ký tự trên bảng của chính mình. Sau đó, mọi người thực hiện \(L\) lượt theo một chiến lược đã thống nhất trước.
  4. Sau \(L\) lượt, mỗi người phải trả lời số hiệu của người cha.

Mỗi lượt trong bước \(3\) gồm hai giai đoạn theo thứ tự:

  • Trước hết, mỗi người xóa ký tự trên bảng của mình, viết một ký tự mới là T hoặc F, rồi đưa bảng cho chủ tịch K.
  • Sau đó, lần lượt với \(i=1,2,\ldots,N\), người \(i\) chọn một người có số hiệu \(p\) (\(1 \le p \le N\)) và báo số \(p\) cho chủ tịch K. Chủ tịch K cho người \(i\) xem bảng của người \(p\), và người \(i\) đọc ký tự trên bảng đó. Người \(i\) được phép chọn chính mình.

Mục tiêu là thống nhất trước một chiến lược sao cho, bất kể ai được chọn làm người cha, cuối cùng tất cả mọi người đều xác định đúng số hiệu người cha. Bạn muốn đạt mục tiêu với số lượt \(L\) càng nhỏ càng tốt.

Một chiến lược gồm số nguyên không âm \(L\) và các quy tắc quyết định hành động như sau:

  • Với người \(i\) (\(1 \le i \le N\)), giả sử các ký tự người đó đã đọc trước khi lượt \(t\) (\(1 \le t \le L\)) bắt đầu lần lượt là \(a_0,a_1,\ldots,a_{t-1}\). Chỉ dựa trên thông tin \((i,t,a_0,a_1,\ldots,a_{t-1})\), người đó phải quyết định cả ký tự sẽ viết lên bảng trong lượt \(t\) lẫn số hiệu người sẽ chọn để xem bảng trong lượt đó.
  • Với người \(i\), giả sử các ký tự đã đọc đến hết lượt \(L\) lần lượt là \(a_0,a_1,\ldots,a_L\). Chỉ dựa trên thông tin \((i,L,a_0,a_1,\ldots,a_L)\), người đó phải quyết định số hiệu người cha mà mình sẽ trả lời.

Ở đây, \(a_0\) là ký tự được đọc trên bảng của chính người đó trước lượt đầu tiên, còn \(a_t\) là ký tự đọc được trong lượt \(t\).

Hãy xây dựng một chiến lược đạt mục tiêu. Với từng trường hợp người cha là \(1,2,\ldots,N\), hãy xuất ký tự mà mỗi người viết lên bảng và số hiệu người mà họ chọn xem bảng ở mỗi lượt khi thực hiện cùng chiến lược đó.

Dữ liệu vào

Mỗi tệp dữ liệu vào chứa một số nguyên \(N\).

Dữ liệu ra

Xuất dữ liệu theo cấu trúc:

L
acts_1
acts_2
...
acts_N

Dòng đầu tiên chứa số nguyên không âm \(L\), là số lượt của chiến lược. Khối \(acts_s\) mô tả hành động của mọi người trong trường hợp người \(s\) là người cha. Các khối được xuất theo thứ tự \(s=1,2,\ldots,N\).

Mỗi khối \(acts_s\) có cấu trúc:

s
c_{1,1} p_{1,1} c_{1,2} p_{1,2} ... c_{1,L} p_{1,L}
c_{2,1} p_{2,1} c_{2,2} p_{2,2} ... c_{2,L} p_{2,L}
...
c_{N,1} p_{N,1} c_{N,2} p_{N,2} ... c_{N,L} p_{N,L}
  • Dòng đầu tiên của khối chứa số nguyên \(s\).
  • Trong \(N\) dòng tiếp theo, dòng thứ \(i\) mô tả hành động của người \(i\). Với mỗi lượt \(t=1,2,\ldots,L\), xuất lần lượt ký tự \(c_{i,t}\) mà người đó viết lên bảng và số hiệu \(p_{i,t}\) của người mà họ chọn xem bảng. Các giá trị trên một dòng được ngăn cách bởi dấu cách.
  • \(c_{i,t}\) phải là T hoặc F, và \(1 \le p_{i,t} \le N\).

Điều kiện hợp lệ

Kết quả được coi là đúng khi và chỉ khi tồn tại một chiến lược đạt mục tiêu mà dữ liệu xuất ra chính là các hành động khi thực hiện chiến lược đó. Cụ thể, phải đồng thời thỏa mãn hai điều kiện:

  1. Với mọi người \(i\) (\(1 \le i \le N\)), mọi lượt \(t\) (\(1 \le t \le L\)) và hai ứng viên người cha khác nhau \(x,y\) (\(1 \le x,y \le N\), \(x\ne y\)): nếu dãy ký tự mà người \(i\) đã đọc trước lượt \(t\) giống nhau trong trường hợp người cha là \(x\) và trường hợp người cha là \(y\), thì hành động của người \(i\) ở lượt \(t\) cũng phải giống nhau trong hai trường hợp, tức là viết cùng ký tự và chọn cùng một người để xem bảng.
  2. Với mọi người \(i\) và hai ứng viên người cha khác nhau \(x,y\), dãy ký tự mà người \(i\) đã đọc đến hết lượt \(L\) trong trường hợp người cha là \(x\) phải khác dãy ký tự trong trường hợp người cha là \(y\).

Tệp kết quả

Chỉ nộp các tệp kết quả output_01.txt, output_02.txt, output_03.txt, lần lượt tương ứng với các tệp dữ liệu vào input_01.txt, input_02.txt, input_03.txt.

Ràng buộc

\(N\) là một trong ba giá trị \(4\), \(32\), \(48\).

Chấm điểm

Điểm của bài là tổng điểm của ba bộ dữ liệu vào. Với mỗi bộ dữ liệu, nếu kết quả sai định dạng hoặc không thỏa mãn các điều kiện hợp lệ, điểm của bộ dữ liệu đó bằng \(0\).

Nếu kết quả hợp lệ, điểm được tính theo số lượt \(L\) trong tệp kết quả tương ứng:

Nhóm Tệp dữ liệu vào \(N\) Điều kiện Điểm Điểm tối đa của nhóm
1 input_01.txt \(4\) \(4<L\) \(0\) \(16\)
1 input_01.txt \(4\) \(2<L\le4\) \(16-7\times(L-2)\) \(16\)
1 input_01.txt \(4\) \(L\le2\) \(16\) \(16\)
2 input_02.txt \(32\) \(27<L\) \(0\) \(60\)
2 input_02.txt \(32\) \(8<L\le27\) \(60-3\times(L-8)\) \(60\)
2 input_02.txt \(32\) \(L\le8\) \(60\) \(60\)
3 input_03.txt \(48\) \(9<L\) \(0\) \(24\)
3 input_03.txt \(48\) \(L\le9\) \(24\) \(24\)

Nếu điểm bằng \(0\), hệ thống chấm của kỳ thi gốc hiển thị thông báo Output isn't correct, kể cả khi nguyên nhân là số lượt quá lớn.

Ví dụ

Ví dụ 1

Input 
3
Output 
3
1
T 1 T 2 T 3
F 1 F 2 F 3
F 1 F 2 F 3
2
F 1 F 2 F 3
T 1 T 2 T 3
F 1 F 2 F 3
3
F 1 F 2 F 3
F 1 F 2 F 3
T 1 T 2 T 3
Giải thích

Kết quả này có thể được tạo ra bởi chiến lược sau:

  • Chọn \(L=3\).
  • Trong mỗi lượt \(t\) (\(1 \le t \le L\)), mỗi người viết T nếu mình là người cha và viết F nếu mình là người con. Mỗi người biết vai trò của chính mình nhờ ký tự đã đọc trên bảng lúc đầu.
  • Trong lượt \(t\), mọi người đều chọn xem bảng của người \(t\), không phụ thuộc vào các ký tự đã đọc trước đó.
  • Đến hết lượt \(3\), mỗi người đã đọc bảng của tất cả những người tham gia, kể cả chính mình, ít nhất một lần. Mỗi người trả lời số hiệu của người có ký tự T trên bảng.

Với chiến lược này, bất kể ai được chọn làm người cha, cuối cùng tất cả mọi người đều trả lời đúng. Vì vậy, kết quả trong ví dụ là hợp lệ.

Ví dụ này không thỏa mãn ràng buộc của bài và không nằm trong các bộ dữ liệu chấm, vì \(N=3\).

Nguồn

Đề bài của Ủy ban Olympic Tin học Nhật Bản, JOI 2024/2025, vòng tuyển chọn mùa xuân, ngày thi thứ ba. Đề gốc và bản dịch tiếng Việt được cung cấp theo giấy phép CC BY-SA 4.0.