Google Code Jam 2019 - Round 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 Google Code Jam 2019 - Datacenter Duplex 23 1.0s 1G
2 Google Code Jam 2019 - Napkin Folding 43 3.5s 1G
3 Google Code Jam 2019 - Pancake Pyramid 22 1.0s 1G
4 Google Code Jam 2019 - Zillionim 100 3.0s 1G

1. Google Code Jam 2019 - Datacenter Duplex

Điểm: 23 Thời gian: 1.0s Bộ nhớ: 1G Input: bàn phím Output: màn hình

Đề bài

Hai công ty, Apricot Rules LLC và Banana Rocks Inc., đang dùng chung một trung tâm dữ liệu. Trung tâm dữ liệu là một ma trận gồm \(R\) hàng và \(C\) cột, mỗi ô chứa một tháp máy chủ. Mỗi tháp chứa tài sản trí tuệ thuộc về đúng một trong hai công ty.

Ban đầu, họ xây tường trên các cạnh ngăn cách những ô được giao cho hai công ty khác nhau. Nhờ đó, các ô kề nhau theo cạnh và thuộc cùng một công ty vẫn được nối với nhau. Ngoài ra, hai ô \(x\) và \(y\) được coi là liên thông nếu \(x\) được nối với một ô mà ô đó liên thông trực tiếp hoặc gián tiếp với \(y\). Theo định nghĩa này, vẫn có thể tồn tại hai ô được giao cho cùng một công ty nhưng không liên thông với nhau, và điều đó là không thể chấp nhận.

Hai công ty đồng ý xây các hành lang hẹp đi qua góc ô để nối trực tiếp hai ô kề nhau theo đường chéo. Ký hiệu \((i, j)\) là ô ở hàng \(i\), cột \(j\). Qua mỗi đỉnh chỉ được xây nhiều nhất một hành lang hẹp; nghĩa là có thể nối \((i, j)\) với \((i + 1, j + 1)\), hoặc nối \((i + 1, j)\) với \((i, j + 1)\), hoặc không nối cặp nào, nhưng không được nối cả hai cặp. Dĩ nhiên, chỉ được xây hành lang giữa hai ô được giao cho cùng một công ty.

Cho một ma trận mà mỗi ô được gắn nhãn A hoặc B tùy theo công ty sở hữu ô đó. Hãy tìm cách thêm các kết nối giữa những ô kề nhau theo đường chéo sao cho tất cả các ô A liên thông với nhau và tất cả các ô B liên thông với nhau.

Dữ liệu vào

Dòng đầu tiên chứa số lượng bộ test \(T\). Tiếp theo là \(T\) bộ test. Mỗi bộ test bắt đầu bằng một dòng chứa hai số nguyên \(R\) và \(C\), lần lượt là số hàng và số cột của ma trận biểu diễn trung tâm dữ liệu. Sau đó là \(R\) dòng, mỗi dòng chứa \(C\) ký tự. Ký tự thứ \(j\) trên dòng thứ \(i\) trong số các dòng này, \(M_{i,j}\), là A hoặc B, cho biết công ty sở hữu ô \((i, j)\).

Dữ liệu ra

Với mỗi bộ test, trước tiên hãy in một dòng có dạng Case #x: y, trong đó x là số thứ tự của bộ test (bắt đầu từ \(1\)), còn y là IMPOSSIBLE nếu không có cách chọn các kết nối theo đường chéo sao cho các ô A liên thông và các ô B liên thông, hoặc là POSSIBLE nếu tồn tại cách chọn. Sau đó, nếu đã in POSSIBLE, hãy in thêm \(R - 1\) dòng, mỗi dòng gồm \(C - 1\) ký tự. Các ký tự này phải biểu diễn một cách bố trí hợp lệ như mô tả ở trên. Ký tự thứ \(j\) trên dòng thứ \(i\) trong số các dòng đó phải là \ nếu cần nối hai ô \((i, j)\) và \((i + 1, j + 1)\), là / nếu cần nối hai ô \((i + 1, j)\) và \((i, j + 1)\), hoặc là . nếu không nối cặp nào.

Ràng buộc

  • \(1 \le T \le 100\).
  • \(2 \le C \le 100\).
  • \(M_{i,j}\) là chữ cái viết hoa A hoặc chữ cái viết hoa B với mọi \(i\) và \(j\).
  • \(M_{i,j}\) là chữ cái viết hoa A với ít nhất một cặp \(i, j\).
  • \(M_{i,j}\) là chữ cái viết hoa B với ít nhất một cặp \(i, j\).

Phân nhóm

Test Set 1 (Hiển thị)

  • \(2 \le R \le 4\).

Test Set 2 (Ẩn)

  • \(2 \le R \le 100\).

Điểm các phân nhóm

Mỗi Test Set tương ứng với một subtask trên LQDOJ. Bảng dưới đây giữ nguyên điểm chính thức của Google Code Jam và quy đổi tỷ lệ trên tổng điểm của bài.

Phân nhóm Điểm Google Code Jam Tỷ lệ điểm của bài
Test Set 1 10/23 43,48%
Test Set 2 13/23 56,52%

Ví dụ

Ví dụ 1

Input 
3
2 2
AB
BA
2 3
AAB
ABB
3 4
BBAA
BABA
BBAA
Output 
Case #1: IMPOSSIBLE
Case #2: POSSIBLE
..
Case #3: POSSIBLE
//\
.//
Giải thích

Trong Sample Case #1, cặp ô A và cặp ô B đều cần được nối với nhau, nhưng vì cả hai kết nối đều phải đi qua cùng một đỉnh nên nhiều nhất chỉ có thể tồn tại một trong hai kết nối.

Trong Sample Case #2, ngay từ dữ liệu vào, các ô đã liên thông theo đúng yêu cầu nên không cần thêm kết nối nào. Lưu ý rằng bạn có thể thêm những kết nối hợp lệ nhưng không cần thiết, vì vậy // cũng là một đáp án hợp lệ khác, còn \. là sai.

Trong Sample Case #3 cũng có nhiều lời giải, và kết quả hiển thị là một trong số đó.

Nguồn

Google Code Jam 2019, Vòng 3, bài Datacenter Duplex.

Nguồn chính thức trên Google Coding Competitions Archive, phát hành theo giấy phép Apache-2.0.

2. Google Code Jam 2019 - Napkin Folding

Điểm: 43 Thời gian: 3.5s Bộ nhớ: 1G Input: bàn phím Output: màn hình

Đề bài

Chalk đã tích cực chu du khắp thế giới cùng bạn bè và chụp ảnh tại tất cả những nơi thú vị nhất. Gần đây nhất, cậu đến châu Âu, nơi cậu tìm hiểu lịch sử của nghệ thuật gấp khăn ăn. Kể từ đó, Chalk đã sưu tầm rất nhiều loại khăn để luyện tập nghệ thuật gấp khăn.

Những chiếc khăn của Chalk có thể được biểu diễn bằng các đa giác đơn. Đa giác đơn là đa giác mà các cạnh không giao nhau, ngoại trừ hai cạnh kề nhau gặp nhau tại đỉnh chung. Mỗi đỉnh của đa giác thuộc đúng hai cạnh.

Trước khi gấp khăn, Chalk vẽ lên khăn một mẫu nếp gấp. Một mẫu nếp gấp là tập hợp gồm \(K-1\) đoạn thẳng được vẽ trên khăn. Mỗi đoạn thẳng nối hai điểm có tọa độ hữu tỉ trên biên của đa giác biểu diễn chiếc khăn và nằm hoàn toàn bên trong đa giác. Hai đoạn thẳng bất kỳ trong một mẫu nếp gấp không được chạm hoặc chồng lên nhau, ngoại trừ trường hợp chúng có chung đầu mút. Một mẫu nếp gấp gồm \(K-1\) đoạn thẳng chia chiếc khăn thành \(K\) miền đa giác. Hai điểm thuộc cùng một miền nếu tồn tại một đường liên tục nào đó (không nhất thiết là đường thẳng) nối chúng mà không giao với bất kỳ cạnh nào của đa giác hay bất kỳ đoạn thẳng nào trong mẫu nếp gấp — kể cả tại đầu mút.

Chalk chỉ quan tâm đến những mẫu nếp gấp gọn gàng. Một mẫu nếp gấp được gọi là gọn gàng nếu hai miền bất kỳ cùng kề với một đoạn nếp gấp \(F\) đều đối xứng qua \(F\). Điều này có nghĩa là khi gấp chiếc khăn theo đoạn thẳng đó, hai miền sẽ chồng khít hoàn toàn lên nhau.

Hình sau minh họa một mẫu nếp gấp gọn gàng với \(K=8\) miền.

Chalk đã gấp thành công bộ sưu tập khăn của mình bằng các mẫu nếp gấp gọn gàng. Tuy nhiên, trong bộ sưu tập vẫn có một số chiếc khăn mà cậu chưa tìm được mẫu nếp gấp gọn gàng. Với mỗi chiếc khăn như vậy, Chalk cần bạn giúp tìm một mẫu nếp gấp gọn gàng có \(K\) miền, hoặc xác định rằng không tồn tại mẫu nào như thế.

Dữ liệu vào

Dòng đầu tiên chứa số lượng bộ test \(T\). Tiếp theo là \(T\) bộ test. Mỗi bộ test bắt đầu bằng một dòng chứa hai số nguyên \(N\) và \(K\): số đỉnh của đa giác biểu diễn chiếc khăn của Chalk và số miền cần chia chiếc khăn thành bằng một mẫu nếp gấp gọn gàng gồm \(K-1\) đoạn thẳng.

Đa giác biểu diễn chiếc khăn được cho dưới dạng danh sách \(N\) đỉnh theo thứ tự gặp được khi đi dọc chu vi đa giác theo chiều kim đồng hồ; đỉnh đầu tiên được chọn tùy ý. \(N\) dòng tiếp theo biểu diễn danh sách đó. Dòng thứ \(i\) trong số này chứa hai số nguyên \(X_i\) và \(Y_i\), cho biết điểm thứ \(i\) nằm tại tọa độ \((X_i, Y_i)\) trong mặt phẳng hai chiều.

Dữ liệu ra

Với mỗi bộ test, in một dòng có dạng Case #x: y, trong đó x là số thứ tự bộ test (bắt đầu từ \(1\)), còn y là POSSIBLE nếu có thể tạo một mẫu nếp gấp gọn gàng với \(K\) miền và là IMPOSSIBLE nếu không thể.

Nếu có thể tạo một mẫu nếp gấp gọn gàng với \(K\) miền, hãy in thêm \(K-1\) dòng liệt kê các đoạn thẳng của một mẫu nếp gấp gọn gàng với \(K\) miền, theo thứ tự bất kỳ. Mỗi dòng phải biểu diễn một đoạn thẳng khác nhau dưới dạng A_x A_y B_x B_y, trong đó \((A_x,A_y)\) và \((B_x,B_y)\) là hai đầu mút của đoạn thẳng, theo thứ tự bất kỳ. Mỗi giá trị trong \(A_x,A_y,B_x,B_y\) phải có dạng N/D, với N và D là các số nguyên dương (không có chữ số \(0\) thừa ở đầu), không có thừa số nguyên tố chung và biểu diễn số hữu tỉ \(N/D\). Không được có khoảng trắng giữa N và /, cũng như giữa / và D.

Ràng buộc

  • \(1 \le T \le 100\).
  • \(3 \le N \le 200\).
  • \(1 \le X_i \le 1000\) với mọi \(i\).
  • \(1 \le Y_i \le 1000\) với mọi \(i\).
  • \(N\) điểm được cho theo thứ tự chiều kim đồng hồ.
  • Không có hai cạnh kề nhau nào của đa giác thẳng hàng.
  • Đa giác là một đa giác đơn có diện tích dương nghiêm ngặt.
  • Hai cạnh bất kỳ không giao nhau, ngoại trừ hai cạnh kề nhau tại đầu mút chung của chúng.

Phân nhóm

Test Set 1 (Hiển thị): \(K=2\).

Test Set 2 (Ẩn): \(2 \le K \le 10\).

Điểm các phân nhóm

Mỗi Test Set tương ứng với một subtask trên LQDOJ. Bảng dưới đây giữ nguyên điểm chính thức của Google Code Jam và quy đổi tỷ lệ trên tổng điểm của bài.

Phân nhóm Điểm Google Code Jam Tỷ lệ điểm của bài
Test Set 1 4/43 9,3%
Test Set 2 39/43 90,7%

Ví dụ

Ví dụ 1

Input 
4
4 2
1 1
1 2
2 2
2 1
3 2
1 1
1 2
2 1
8 2
1 3
3 5
5 5
4 4
7 3
5 1
4 2
3 1
8 2
1 3
3 5
4 4
5 5
7 3
5 1
4 2
3 1
Output 
Case #1: POSSIBLE
1/1 2/1 2/1 1/1
Case #2: POSSIBLE
1/1 1/1 3/2 3/2
Case #3: IMPOSSIBLE
Case #4: POSSIBLE
1/1 3/1 7/1 3/1

Ví dụ 2

Input 
1
10 8
4 1
3 1
2 2
2 3
1 3
1 4
2 4
3 3
3 2
4 2
Output 
Case #1: POSSIBLE
3/1 1/1 4/1 2/1
3/1 1/1 3/1 2/1
2/1 2/1 3/1 2/1
2/1 2/1 3/1 3/1
2/1 3/1 3/1 3/1
2/1 3/1 2/1 4/1
1/1 3/1 2/1 4/1
Giải thích

Lưu ý: Ví dụ 2 không hợp lệ đối với Test Set 1. Chỉ Ví dụ 1 được kiểm tra trước khi chạy Test Set 1 (giống như cách các ví dụ thường được kiểm tra). Hơn nữa, Ví dụ 2 sẽ không được kiểm tra trước khi chạy Test Set 2.

Trong Test mẫu #1, có thể vẽ một mẫu nếp gấp gọn gàng với \(K=2\) bằng bất kỳ đường nét đứt nào trong số \(4\) đường được minh họa.

Trong Test mẫu #2, có thể vẽ một mẫu nếp gấp gọn gàng với \(K=2\) như hình minh họa.

Trong Test mẫu #3, không tồn tại mẫu nếp gấp gọn gàng nào.

Trong Test mẫu #4, có hai mẫu nếp gấp gọn gàng khả dĩ với \(K=2\), như hình minh họa.

Đối với test mẫu của Test Set 2, có thể vẽ một mẫu nếp gấp gọn gàng với \(K=8\) như hình minh họa.

Nguồn

Google Code Jam 2019, Vòng 3, bài Napkin Folding.

Nguồn chính thức trên Google Coding Competitions Archive, phát hành theo giấy phép Apache-2.0.

3. Google Code Jam 2019 - Pancake Pyramid

Điểm: 22 Thời gian: 1.0s Bộ nhớ: 1G Input: bàn phím Output: màn hình

Đề bài

Bạn vừa nấu ăn xong cho một số thực khách tại Nhà Bánh kếp Vô hạn. Có tất cả \(S\) chồng bánh kếp và bạn đã xếp chúng thành một hàng, sao cho chồng thứ \(i\) tính từ bên trái (đánh số bắt đầu từ \(1\)) có \(P_i\) chiếc bánh.

Người giám sát của bạn chuẩn bị mang các chồng bánh ra cho khách thì chợt nhận ra rằng một bức ảnh chụp chúng có thể là quảng cáo hay. Tuy nhiên, cô ấy lo rằng có thể có quá nhiều chồng bánh, nên dự định bỏ đi \(L\) chồng ngoài cùng bên trái và \(R\) chồng ngoài cùng bên phải, trong đó \(L,R\) là các số nguyên không âm thỏa mãn \(L+R\le S-3\). (Lưu ý rằng sau khi bỏ đi, vẫn còn ít nhất \(3\) chồng bánh.)

Người giám sát cũng cho rằng các chồng còn lại sẽ trông đẹp mắt nếu chúng có tính chất kim tự tháp. Một dãy \(N\) chồng có chiều cao \(H_1,H_2,\ldots,H_N\) có tính chất kim tự tháp nếu tồn tại số nguyên \(j\) (\(1\le j\le N\)) sao cho

\[H_1\le H_2\le\ldots\le H_{j-1}\le H_j\]

và

\[H_j\ge H_{j+1}\ge\ldots\ge H_{N-1}\ge H_N.\]

(Dãy này có thể trông không giống một “kim tự tháp” thông thường cho lắm — một nhóm các chồng có cùng kích thước vẫn có tính chất kim tự tháp, và một nhóm có chiều cao không giảm từ trái sang phải cũng vậy, cùng với nhiều ví dụ khác.)

Dãy còn lại sau khi người giám sát bỏ \(L\) chồng ngoài cùng bên trái và \(R\) chồng ngoài cùng bên phải có thể chưa có tính chất kim tự tháp... nhưng bạn có thể khắc phục bằng cách thêm bánh vào một hoặc nhiều chồng! Chi phí kim tự tháp hóa của một dãy là tổng số bánh ít nhất phải thêm vào các chồng để dãy có tính chất kim tự tháp.

Trong lúc người quản lý cân nhắc nên chọn \(L,R\) nào, bạn tự hỏi tổng chi phí kim tự tháp hóa trên mọi cách chọn \(L,R\) hợp lệ là bao nhiêu. Hãy tính tổng này theo modulo số nguyên tố \(10^9+7\) (\(1000000007\)).

Dữ liệu vào

Dòng đầu chứa số bộ test \(T\). Tiếp theo là \(T\) bộ test. Mỗi bộ bắt đầu bằng một dòng chứa số nguyên \(S\): số chồng bánh. Sau đó là một dòng chứa \(S\) số nguyên \(P_1,P_2,\ldots,P_S\). Số thứ \(i\) là số bánh ở chồng thứ \(i\) tính từ bên trái.

Dữ liệu ra

Với mỗi bộ test, in một dòng dạng Case #x: y, trong đó x là số thứ tự bộ test (bắt đầu từ \(1\)), còn y là tổng chi phí kim tự tháp hóa trên mọi cách chọn \(L,R\) hợp lệ, theo modulo \(10^9+7\) (\(1000000007\)).

Ràng buộc

  • \(1\le T\le100\).
  • \(1\le P_i\le10^9\) với mọi \(i\).

Phân nhóm

Test Set 1 (Hiển thị)

  • \(S=3000\) đối với tối đa \(20\) bộ test.
  • \(3\le S\le500\) đối với tất cả bộ test còn lại.

Test Set 2 (Ẩn)

  • \(S=10^6\) đối với tối đa \(1\) bộ test.
  • \(S=10^5\) đối với tối đa \(3\) bộ test.
  • \(3\le S\le10000\) đối với tất cả bộ test còn lại.

Điểm các phân nhóm

Mỗi Test Set tương ứng với một subtask trên LQDOJ. Bảng dưới đây giữ nguyên điểm chính thức của Google Code Jam và quy đổi tỷ lệ trên tổng điểm của bài.

Phân nhóm Điểm Google Code Jam Tỷ lệ điểm của bài
Test Set 1 5/22 22,73%
Test Set 2 17/22 77,27%

Ví dụ

Ví dụ 1

Dữ liệu mẫu và phần giải thích chính thức được trình bày đầy đủ ngay bên dưới.

Giải thích

Input

3
3
2 1 2
5
1 6 2 5 7
4
1000000000 1 1 1000000000

Output

Case #1: 1
Case #2: 16
Case #3: 999999991

Trong Ví dụ #1, người giám sát buộc phải chọn \(L=0,R=0\), nên đó là trường hợp duy nhất cần xét. Tối ưu là thêm một chiếc bánh vào chồng giữa. Dù dãy thu được trông phẳng, nó có tính chất kim tự tháp; thực tế mọi chỉ số đều có thể làm \(j\).

Trong Ví dụ #2, sau đây là mọi cách chọn \(L,R\), dãy còn lại và việc cần làm:

  • \(L=0,R=0\): \(H=[1,6,2,5,7]\). Thêm bốn bánh vào chồng thứ ba và một bánh vào chồng thứ tư. Ta được \([1,6,6,6,7]\), có tính chất kim tự tháp với \(j=5\).
  • \(L=0,R=1\): \(H=[1,6,2,5]\). Thêm ba bánh vào chồng thứ ba. Ta được \([1,6,5,5]\), có tính chất kim tự tháp với \(j=2\).
  • \(L=0,R=2\): \(H=[1,6,2]\). Dãy đã có tính chất kim tự tháp với \(j=2\).
  • \(L=1,R=0\): \(H=[6,2,5,7]\). Thêm bốn bánh vào chồng thứ hai và một bánh vào chồng thứ ba. Ta được \([6,6,6,7]\), có tính chất kim tự tháp với \(j=4\).
  • \(L=1,R=1\): \(H=[6,2,5]\). Thêm ba bánh vào chồng thứ hai. Ta được \([6,5,5]\), có tính chất kim tự tháp với \(j=1\).
  • \(L=2,R=0\): \(H=[2,5,7]\). Dãy đã có tính chất kim tự tháp với \(j=3\).

Vì vậy, đáp án là \((5+3+0+5+3+0)\) modulo \((10^9+7)\), bằng \(16\).

Trong Ví dụ #3, ta chỉ cần thêm bánh để tạo tính chất kim tự tháp khi \(L=0,R=0\). Tối ưu là thêm \(999999999\) bánh vào mỗi chồng thứ hai và thứ ba. (Hy vọng các thực khách đang đói!) Vì vậy đáp án là \((999999999+999999999)\) modulo \((10^9+7)\), bằng \(999999991\).

Nguồn

Google Code Jam 2019, Vòng 3, bài Pancake Pyramid.

Nguồn chính thức trên Google Coding Competitions Archive, phát hành theo giấy phép Apache-2.0.

4. Google Code Jam 2019 - Zillionim

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

Zillionim

Đề bài

Zillionim là trò chơi theo lượt cho hai người. Ban đầu, \(10^{12}\) đồng xu được xếp nối tiếp thành một hàng, đánh số từ \(1\) đến \(10^{12}\) từ trái sang phải. Mỗi lượt, người chơi phải chọn và loại bỏ \(10^{10}\) đồng xu liên tiếp. Hai đồng xu vốn không liên tiếp sẽ không trở thành liên tiếp, ngay cả khi mọi đồng xu ở giữa đã bị loại bỏ.

Đến lượt mình, người chơi thực hiện một nước hợp lệ nếu có thể, rồi tới lượt đối thủ. Người không thể thực hiện nước hợp lệ trong lượt của mình sẽ thua (và đối thủ thắng).

Vì các kỹ sư vẫn đang huấn luyện mô hình máy học chơi Zillionim, chúng tôi đã tạo một AI đơn giản chơi bằng nước đi ngẫu nhiên. AI luôn đi trước. Mỗi lượt, AI xác định mọi nước hợp lệ rồi chọn đều ngẫu nhiên một nước.

Bạn có thể đánh bại AI này... ít nhất trong phần lớn số ván không?

Dữ liệu vào

Nội dung vào được cung cấp theo giao thức mô tả dưới đây.

Dữ liệu ra

Đây là bài tương tác. Bạn cần bảo đảm đã đọc phần Bài toán tương tác trong mục Câu hỏi thường gặp.

Ban đầu, chương trình đọc một dòng chứa hai số nguyên \(T\), số bộ test, và \(W\), số ván tối thiểu cần thắng để lời giải được xem là đúng. Sau đó, bạn xử lý \(T\) bộ test, mỗi bộ là một ván Zillionim.

Mỗi bộ test được xử lý bằng các lần trao đổi với bộ chấm cho đến khi một người thắng. Trong mỗi lần trao đổi, bộ chấm trước tiên xuất một dòng chứa số nguyên \(P\), được hiểu như sau:

  • Nếu \(1 \le P \le 10^{12}-10^{10}+1\), AI đã loại bỏ các đồng xu \(P,P+1,\ldots,P+10^{10}-1\), và đến lượt bạn. Nghĩa là bạn còn ít nhất một nước hợp lệ. AI luôn đi hợp lệ.
  • Nếu \(P=-2\), nước gần nhất của bạn đã giúp bạn thắng ván hiện tại.
  • Nếu \(P=-3\), AI vừa đi và thắng ván hiện tại. Trong trường hợp này, bộ chấm không gửi nước cuối của AI.
  • Nếu \(P=-1\), thông tin cuối bạn gửi sai định dạng hoặc là nước không hợp lệ (ngoài phạm vi hoặc cố loại bỏ đồng xu không còn tồn tại), nên bạn nhận Wrong Answer vì chơi sai (xem thêm bên dưới).

Sau khi nhận \(P\) dương, bạn phải gửi một dòng chứa số nguyên dương \(Q\) (\(1 \le Q \le 10^{12}-10^{10}+1\)), biểu thị việc loại bỏ các đồng xu \(Q,Q+1,\ldots,Q+10^{10}-1\). Tất cả chúng phải chưa bị loại bỏ trong ván hiện tại.

Sau khi bộ chấm gửi -2 hoặc -3, nếu đó là ván cuối thì bộ chấm và chương trình đều kết thúc. Nếu không, bộ chấm gửi dữ liệu của lần trao đổi đầu tiên trong ván kế tiếp. Bộ chấm chỉ kiểm tra số ván thắng/thua sau khi mọi ván được xử lý đúng. Ví dụ, nếu thắng \(T-1\) ván rồi gửi dữ liệu sai trong ván cuối, bạn vẫn nhận Wrong Answer, bất kể \(W\).

Sau khi nhận -1, chương trình phải kết thúc để nhận Wrong Answer. Nếu vẫn chờ bộ chấm, chương trình sẽ hết thời gian và nhận Time Limit Exceeded. Bạn có trách nhiệm để chương trình thoát bình thường và đúng hạn, nhằm nhận Wrong Answer thay vì Runtime Error hoặc Time Limit Exceeded.

Hạt giống sinh số ngẫu nhiên được định trước (và khác nhau) cho từng ván. Vì vậy, hai bài nộp thực hiện chính xác cùng chuỗi nước trong một ván sẽ nhận chính xác cùng chuỗi nước từ AI trong ván ấy. Cách AI chơi trong một ván cũng không phụ thuộc, kể cả theo nghĩa sinh giả ngẫu nhiên, vào các nước trong những ván trước thuộc cùng bộ test.

Ràng buộc

  • \(T=500\).
  • \(-3 \le P \le 10^{12}-10^{10}+1\).
  • \(P \ne 0\).
  • \(P\) biểu thị nước đi hợp lệ hoặc thông tin hợp lệ về trạng thái ván, như giải thích ở trên.

Phân nhóm

Bộ test 1 (Hiển thị)

\(W=300\).

Bộ test 2 (Hiển thị)

\(W=475\).

Bộ test 3 (Hiển thị)

\(W=499\).

Giao thức tương tác

Chương trình phải tuân thủ đầy đủ thứ tự đọc, ghi, phản hồi lỗi và yêu cầu flush được mô tả trong phần dữ liệu vào/ra và công cụ kiểm thử bên dưới.

Công cụ kiểm thử

Bạn có thể dùng công cụ này để kiểm tra cục bộ hoặc trên nền tảng của chúng tôi. Để kiểm tra cục bộ, cần chạy công cụ song song với chương trình; có thể dùng trình chạy tương tác của chúng tôi. Hãy đọc hướng dẫn trong chú thích của tệp đó và phần Bài toán tương tác trong mục Câu hỏi thường gặp.

Hướng dẫn sử dụng nằm trong chú thích của công cụ. Chúng tôi khuyến khích bạn tự thêm ca kiểm thử. Dù nhằm mô phỏng hệ thống chấm, công cụ này KHÔNG PHẢI hệ thống chấm thật và có thể hoạt động khác. Nếu chương trình vượt qua công cụ nhưng thất bại trên bộ chấm thật, hãy xem phần Lập trình trong Câu hỏi thường gặp để bảo đảm bạn dùng cùng trình biên dịch với chúng tôi.

Tải công cụ kiểm thử

Ví dụ

Ví dụ 1

Dữ liệu mẫu và phần giải thích chính thức được trình bày đầy đủ ngay bên dưới.

Giải thích

Để đơn giản, phiên sau dùng \(50\) đồng xu thay vì \(10^{12}\), và mỗi nước loại bỏ \(10\) đồng xu liên tiếp thay vì \(10^{10}\). Ngoài ra, luật chơi không đổi.

t, w = readline_int_list()   // đọc 500 vào t và 300 vào w
p = readline_int()           // đọc 23; bắt đầu ván 1. AI lấy xu 23 đến 32.
printline 38 to stdout       // ta lấy xu 38 đến 47
flush stdout
p = readline_int()           // đọc 3. AI lấy xu 3 đến 12.
printline 13 to stdout       // ta lấy xu 13 đến 22 (nước duy nhất còn lại!)
flush stdout
p = readline_int()           // đọc -2. Ta thắng ván 1 vì AI hết nước.
p = readline_int()           // đọc 32; bắt đầu ván 2. AI lấy xu 32 đến 41.
printline 13 to stdout       // ta lấy xu 13 đến 22
flush stdout
p = readline_int()           // đọc -3. Không biết nước của AI, nhưng ta hết nước và thua ván 2.
p = readline_int()           // đọc 10; bắt đầu ván 3. AI lấy xu 10 đến 19.
printline 0 to stdout        // chọn chỉ số sai (đánh số xu bắt đầu từ 1!)
flush stdout
p = readline_int()           // đọc -1 — ta đã mắc lỗi!
exit                         // thoát để tránh lỗi TLE không rõ nguyên nhân

Nguồn

Google Code Jam 2019, Vòng 3, bài Zillionim.

Nguồn chính thức trên Google Coding Competitions Archive, phát hành theo giấy phép Apache-2.0.