Google Code Jam 2019 - Round 2

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 - Contransmutation 29 1.0s 1G
2 Google Code Jam 2019 - New Elements: Part 1 22 1.5s 1G
3 Google Code Jam 2019 - New Elements: Part 2 26 1.0s 1G
4 Google Code Jam 2019 - Pottery Lottery 100 4.0s 1G

1. Google Code Jam 2019 - Contransmutation

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

Năm ngoái, chúng tôi đã nhờ bạn giúp biến đổi những kim loại đắt tiền thành chì. (Bạn không cần biết gì về bài toán trước để giải bài này.) Nhưng nhà lãnh đạo đất nước bạn vẫn tham lam và muốn có thêm chì!

Trên thế giới có \(M\) kim loại đã được biết đến; chì là kim loại số 1 trong bảng tuần hoàn của bạn. Nhà lãnh đạo đã yêu cầu bạn dùng các kim loại trong kho bạc để tạo ra nhiều chì nhất có thể.

Với mỗi kim loại (kể cả chì), bạn biết đúng một công thức cho phép phá hủy một gram kim loại đó và tạo ra một gram của mỗi kim loại trong hai kim loại khác. (Tốt nhất đừng suy nghĩ quá nhiều về định luật bảo toàn khối lượng!) Công thức của kim loại thứ \(i\) có thể tạo ra chính kim loại thứ \(i\) làm một trong các sản phẩm. Công thức không áp dụng cho phần lẻ của một gram. Bạn có thể dùng mỗi công thức bao nhiêu lần tùy thích (hoặc không dùng), miễn là có một gram nguyên liệu cần thiết.

Nếu lựa chọn tối ưu, số gram chì lớn nhất cuối cùng bạn có thể có là bao nhiêu, hay lượng đó không bị chặn? Nếu có giới hạn, vì kết quả có thể rất lớn, chỉ cần in phần dư khi chia kết quả cho số nguyên tố \(10^9+7\) (tức \(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 số nguyên \(M\), là số kim loại đã biết. Sau đó có \(M\) dòng, mỗi dòng gồm hai số nguyên \(R_{i1}\) và \(R_{i2}\); dòng thứ \(i\) (đánh số từ 1) cho biết có thể phá hủy một gram kim loại \(i\) để tạo một gram kim loại \(R_{i1}\) và một gram kim loại \(R_{i2}\). Cuối cùng là một dòng gồm \(M\) số nguyên \(G_1,G_2,…,G_M\); \(G_i\) là số gram kim loại \(i\) trong kho bạc. Chì là kim loại 1.

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). Nếu lượng chì tối đa có thể tạo ra không bị chặn, y phải là UNBOUNDED. Nếu không, y là lượng chì lớn nhất (tính bằng gram) cuối cùng có thể có, lấy modulo \(10^9+7\) (tức \(1000000007\)).

Ràng buộc

  • \(1≤ R_{i1}<R_{i2}≤ M\) với mọi \(i\).

Phân nhóm

Test Set 1 (Công khai)

  • \(1≤ T≤100\).
  • \(2≤ M≤10\).
  • \(0≤ G_i≤10\) với mọi \(i\).

Test Set 2 (Ẩn)

  • \(1≤ T≤100\).
  • \(2≤ M≤100\).
  • \(0≤ G_i≤10^9\) với mọi \(i\).

Test Set 3 (Ẩn)

  • \(1≤ T≤5\).
  • \(2≤ M≤10^5\).
  • \(0≤ G_i≤10^9\) với mọi \(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 7/29 24,14%
Test Set 2 16/29 55,17%
Test Set 3 6/29 20,69%

Ví dụ

Ví dụ 1

Input 
3
2
1 2
1 2
1 0
2
1 2
1 2
0 0
4
2 4
3 4
2 4
2 3
10 10 10 10
Output 
Case #1: UNBOUNDED
Case #2: 0
Case #3: 10
Giải thích

Trong mẫu 1, một công thức biến 1 gram chì thành 1 gram chì và 1 gram kim loại thứ hai; công thức kia biến 1 gram kim loại thứ hai thành 1 gram chì và 1 gram kim loại thứ hai. Có thể luân phiên hai công thức để tạo lượng tùy ý của cả hai kim loại.

Mẫu 2 có cùng công thức như mẫu 1, nhưng ban đầu không có kim loại nào!

Trong mẫu 3, không công thức nào giúp tạo thêm chì, nên cuối cùng không thể có nhiều chì hơn lúc đầu.

Nguồn

Google Code Jam 2019, Vòng 2, bài Contransmutation.

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 - New Elements: Part 1

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

New Elements: Part 1

Hai đoạn đầu tiên của đề bài này (không tính đoạn ghi chú này) giống hệt hai đoạn đầu tiên của bài "New Elements: Part 2". Ngoài phần đó ra, hai bài có thể được giải độc lập; bạn không cần đọc hoặc giải bài này để đọc hoặc giải bài kia.

Muriel đang trên hành trình khám phá hai nguyên tố mới mà cô đặt tên là Codium và Jamarium. Cô chưa thể phân lập chúng, nhưng muốn bắt đầu gián tiếp nghiên cứu một số tính chất quan trọng, chẳng hạn như khối lượng nguyên tử. Vì Muriel đang làm việc với duy nhất một đồng vị của Codium và duy nhất một đồng vị của Jamarium, khối lượng nguyên tử của chúng là các số nguyên dương.

Muriel đã tạo ra \(N\) phân tử khác nhau; mỗi phân tử chứa một hoặc nhiều nguyên tử Codium, một hoặc nhiều nguyên tử Jamarium và không chứa nguyên tố nào khác. Với mỗi phân tử, cô biết số nguyên tử của từng nguyên tố có trong đó. Khối lượng phân tử bằng tổng khối lượng nguyên tử của tất cả các nguyên tử cấu thành phân tử ấy.

Là bước đầu tiên để xác định chính xác khối lượng phân tử và khối lượng nguyên tử của hai nguyên tố, Muriel muốn sắp xếp các phân tử theo khối lượng phân tử tăng nghiêm ngặt. Để đánh giá độ khó của công việc này, cô muốn biết có bao nhiêu thứ tự hợp lệ nếu chỉ xét những thông tin hiện có. Một thứ tự các phân tử được coi là hợp lệ nếu tồn tại một cách chọn khối lượng nguyên tử của Codium và Jamarium sao cho khối lượng phân tử trong thứ tự đó tăng nghiêm ngặt.

Ví dụ, ta biểu diễn mỗi phân tử bằng cặp có thứ tự gồm số nguyên tử Codium và số nguyên tử Jamarium mà nó chứa. Nếu Muriel có 3 phân tử được biểu diễn bởi \((1, 1)\), \((2, 1)\) và \((1, 2)\), có hai thứ tự có thể tăng nghiêm ngặt theo khối lượng phân tử: \((1, 1), (1, 2), (2, 1)\) và \((1, 1), (2, 1), (1, 2)\). Thứ tự đầu tiên hợp lệ với mọi cách gán khối lượng nguyên tử mà Codium là nguyên tố nặng hơn, còn thứ tự thứ hai hợp lệ với mọi cách gán mà Jamarium là nguyên tố nặng hơn. Trường hợp duy nhất còn lại là Codium và Jamarium có cùng khối lượng nguyên tử; khi đó \((1, 2)\) và \((2, 1)\) có cùng khối lượng phân tử, nên không thể tạo ra một thứ tự tăng nghiêm ngặt trong trường hợp này.

Dữ liệu vào

Dòng đầu tiên chứa số lượng bộ test \(T\). Sau đó là \(T\) bộ test. Dòng đầu tiên của mỗi bộ test chứa một số nguyên \(N\), là số lượng phân tử. Mỗi dòng trong \(N\) dòng tiếp theo mô tả một phân tử khác nhau bằng hai số nguyên \(C_i\) và \(J_i\), lần lượt là số nguyên tử Codium và Jamarium trong phân tử thứ \(i\).

Dữ liệu ra

Với mỗi bộ test, in ra 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) và y là tổng số thứ tự hợp lệ theo định nghĩa ở trên.

Ràng buộc

  • \(1 \le T \le 100\).
  • \(1 \le C_i \le 10^9\) với mọi \(i\).
  • \(1 \le J_i \le 10^9\) với mọi \(i\).
  • \((C_i, J_i) \ne (C_j, J_j)\) với mọi \(i \ne j\). Mọi phân tử đều khác nhau.

Phân nhóm

Test Set 1 (Hiển thị)

  • \(2 \le N \le 6\).

Test Set 2 (Ẩn)

  • \(2 \le N \le 300\).

Đ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 8/22 36,36%
Test Set 2 14/22 63,64%

Ví dụ

Ví dụ 1

Input 
3
3
1 1
1 2
2 1
4
1 2
2 4
2 1
4 2
3
1 2
1 3
2 3
Output 
Case #1: 2
Case #2: 2
Case #3: 1
Giải thích

Bộ test mẫu số 1 đã được giải thích trong phần đề bài.

Trong bộ test mẫu số 2, hai thứ tự hợp lệ là \((1, 2), (2, 1), (2, 4), (4, 2)\) và \((2, 1), (1, 2), (4, 2), (2, 4)\). Lưu ý rằng thứ tự \((1, 2), (2, 1), (4, 2), (2, 4)\) không hợp lệ: nếu \((1, 2)\) nhẹ hơn nghiêm ngặt so với \((2, 1)\) thì \((2, 4)\), có khối lượng đúng bằng hai lần \((1, 2)\), phải nhẹ hơn nghiêm ngặt so với \((4, 2)\), có khối lượng đúng bằng hai lần \((2, 1)\).

Nguồn

Google Code Jam 2019, Vòng 2, bài New Elements: Part 1.

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 - New Elements: Part 2

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

Nguyên tố mới: Phần 2

Hai đoạn đầu tiên (không tính đoạn này) của bài toán này và bài "Nguyên tố mới: Phần 1" là giống hệt nhau. Ngoài ra, hai bài có thể được giải độc lập; bạn không cần đọc hoặc giải bài này để có thể đọc hoặc giải bài kia.

Muriel đang trên đường khám phá hai nguyên tố mới mà cô đặt tên là Codium và Jamarium. Cô vẫn chưa thể tách riêng chúng, nhưng muốn bắt đầu gián tiếp nghiên cứu một số tính chất quan trọng, chẳng hạn như khối lượng nguyên tử. Vì Muriel chỉ làm việc với một đồng vị duy nhất của Codium và một đồng vị duy nhất của Jamarium, khối lượng nguyên tử của chúng là các số nguyên dương.

Muriel đã tạo ra được \(N\) phân tử khác nhau. Mỗi phân tử chứa ít nhất một nguyên tử Codium, ít nhất một nguyên tử Jamarium và không chứa nguyên tố nào khác. Với mỗi phân tử, cô biết số nguyên tử của từng nguyên tố có trong đó. Khối lượng phân tử bằng tổng khối lượng nguyên tử của tất cả các nguyên tử mà phân tử chứa.

Bước đầu tiên, Muriel sắp xếp các phân tử theo thứ tự khối lượng phân tử tăng nghiêm ngặt. Bây giờ, cô muốn tìm các giá trị nguyên khả dĩ cho khối lượng nguyên tử của cả Codium lẫn Jamarium sao cho phù hợp với thứ tự này. Vì biết rằng có thể có nhiều cặp giá trị phù hợp, cô muốn chọn cặp làm khối lượng nguyên tử của Codium nhỏ nhất. Nếu có nhiều cặp cùng đạt khối lượng nguyên tử nhỏ nhất của Codium, cô muốn chọn cặp có khối lượng nguyên tử của Jamarium nhỏ nhất.

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. Dòng đầu tiên của mỗi bộ test chứa một số nguyên \(N\), là số lượng phân tử. Mỗi dòng trong \(N\) dòng tiếp theo mô tả một phân tử khác nhau bằng hai số nguyên \(C_i\) và \(J_i\), lần lượt biểu thị số nguyên tử Codium và Jamarium trong phân tử thứ \(i\). Các phân tử được cho theo thứ tự khối lượng phân tử tăng nghiêm ngặt.

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ự của bộ test (bắt đầu từ 1), còn y là IMPOSSIBLE (viết hoa) nếu không có cặp khối lượng nguyên tử nguyên nào làm cho khối lượng phân tử tăng nghiêm ngặt theo thứ tự đã cho. Nếu có, y phải là hai số nguyên c j, trong đó c là khối lượng nguyên tử của Codium và j là khối lượng nguyên tử của Jamarium, được chọn theo các quy tắc ở trên.

Ràng buộc

  • \(1 \le T \le 100\).
  • \(2 \le N \le 10\).
  • \((C_i, J_i) \ne (C_j, J_j)\) với mọi \(i \ne j\) (tất cả các phân tử đều khác nhau).

Phân nhóm

Test Set 1 (Công khai)

  • \(1 \le C_i \le 100\) với mọi \(i\).
  • \(1 \le J_i \le 100\) với mọi \(i\).

Test Set 2 (Ẩn)

  • \(1 \le C_i \le 10^9\) với mọi \(i\).
  • \(1 \le J_i \le 10^9\) với mọi \(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 10/26 38,46%
Test Set 2 16/26 61,54%

Ví dụ

Ví dụ 1

Input 
3
3
1 1
1 2
2 1
4
1 2
2 1
4 2
2 4
3
1 2
1 3
2 3
Output 
Case #1: 2 1
Case #2: IMPOSSIBLE
Case #3: 1 1
Giải thích

Trong test mẫu số 1, hai phân tử cuối khác nhau ở chỗ phân tử này có thêm một nguyên tử của nguyên tố này, còn phân tử kia có thêm một nguyên tử của nguyên tố kia. Vì phân tử có thêm Codium nặng hơn về tổng thể, ta kết luận Codium phải nặng hơn Jamarium. Chọn khối lượng nguyên tử của Codium và Jamarium lần lượt là 2 và 1 thì khối lượng các phân tử là \(1 \times 2 + 1 \times 1 = 3\), \(1 \times 2 + 2 \times 1 = 4\) và \(2 \times 2 + 1 \times 1 = 5\), đúng với thứ tự tăng nghiêm ngặt. Vì trong trường hợp này Codium nặng hơn Jamarium, 2 là khối lượng nguyên tử nhỏ nhất của Codium, và hiển nhiên 1 là khối lượng nguyên tử nhỏ nhất của Jamarium.

Gọi \(a\), \(b\), \(c\) và \(d\) lần lượt là khối lượng của các phân tử trong test mẫu số 2, theo thứ tự khối lượng tăng dần. Từ thành phần nguyên tử của chúng, ta có \(d = 2 \times a\) và \(c = 2 \times b\). Từ \(a < b\) suy ra \(d = 2 \times a < 2 \times b = c\), nghĩa là không có cặp giá trị khối lượng nguyên tử nào làm cho thứ tự đã cho tăng nghiêm ngặt.

Trong test mẫu số 3, lưu ý rằng các phân tử tình cờ được sắp theo thứ tự tăng nghiêm ngặt của tổng số nguyên tử. Do đó, gán khối lượng nguyên tử của cả hai nguyên tố bằng 1 sẽ làm khối lượng phân tử tăng nghiêm ngặt theo đúng thứ tự.

Nguồn

Google Code Jam 2019, Vòng 2, bài New Elements: Part 2.

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 - Pottery Lottery

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

Đề bài

Pottery Palace sắp tổ chức một cuộc xổ số với phần thưởng là những chiếc bình quý giá của nghệ sĩ Cody-Jamal. Cuộc xổ số diễn ra như sau:

  • Có 100 người tham gia xổ số. Mỗi người chơi có một số hiệu riêng biệt từ 1 đến 100 và được phát đúng một thẻ mang số hiệu đó.
  • Trên bàn có 20 chiếc bình đất sét rỗng, được đánh số từ 1 đến 20. Miệng bình hẹp, đủ rộng để bỏ một thẻ vào nhưng đủ nhỏ để người chơi không thể nhìn vào bên trong xem bình chứa gì.
  • Vào ngày thứ \(i\) của cuộc xổ số, người chơi có thẻ số \(i\) chọn một chiếc bình rồi bỏ thẻ của mình vào đó. Vì tất cả các bình đều giống hệt nhau (ngoại trừ nhãn số), mỗi người chơi sẽ chọn một bình ngẫu nhiên đều và độc lập với lựa chọn của tất cả người chơi khác.
  • Vào ngày thứ 100, sau khi người chơi số 100 đã bỏ thẻ vào bình, ban tổ chức lắc các bình để xác định số thẻ trong mỗi bình. Nếu có đúng một chiếc bình chứa ít thẻ hơn mọi chiếc bình khác thì đó là "bình chiến thắng". Sau đó, ban tổ chức đổ tất cả thẻ trong bình ấy ra, và mỗi người chơi có số hiệu ghi trên một trong các thẻ vừa được đổ ra sẽ thắng một chiếc bình! Nếu nhiều bình cùng có số thẻ ít nhất thì không ai nhận được gì.

Bạn được thuê để kiểm tra tính bảo mật của cuộc xổ số và sẽ tham gia một số lượt chạy thử. Công ty luôn gán cho bạn số 100 — tức là bạn thay thế người chơi số 100.

Bạn đã tìm ra một số cách can thiệp vào cuộc xổ số vào ban đêm, nhưng an ninh rất nghiêm ngặt nên khả năng của bạn có hạn! Cụ thể, sau mỗi ngày trong 99 ngày đầu tiên của cuộc xổ số, bạn được thực hiện đúng một trong hai hành động sau:

  • Làm giả một thẻ mang số hiệu người chơi do bạn chọn (từ 1 đến 100, kể cả hai đầu) và thêm thẻ đó vào một bình do bạn chọn. Bạn làm giả rất khéo: nếu có bình chiến thắng, mọi thẻ giả trong bình đó vẫn khiến những người chơi mang số hiệu tương ứng chiến thắng (ngoại trừ một trường hợp được nêu bên dưới).
  • Dùng một camera đặc biệt để xem số hiệu trên tất cả các thẻ trong một bình do bạn chọn.

Bạn có thể thực hiện các hành động khác nhau vào những đêm khác nhau và có thể lựa chọn một cách linh hoạt: bạn không cần quyết định trước toàn bộ các hành động.

Vào ngày thứ 100, đến lượt bạn bỏ thẻ của mình vào một bình do bạn chọn (bạn không bắt buộc phải chọn ngẫu nhiên đều). Bạn không thể thực hiện hành động nào khác trong ngày đó.

Bạn biết rằng nếu bình chiến thắng chứa nhiều hơn một thẻ của cùng một người chơi thì việc gian lận sẽ bị phát hiện rõ ràng và không ai chiến thắng. Tuy nhiên, việc những bình khác chứa nhiều hơn một thẻ của cùng một người chơi không quan trọng, vì ban tổ chức không bao giờ nhìn thấy các thẻ đó.

Mục tiêu của bạn là trở thành người chiến thắng trong ít nhất 90% số trường hợp kiểm thử.

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à một bài toán tương tác. Bạn cần bảo đảm rằng mình đã đọc phần Bài toán tương tác trong FAQ.

Ban đầu, chương trình phải đọc một dòng chứa một số nguyên \(T\), cho biết số lượng trường hợp kiểm thử. Sau đó, bạn cần xử lý \(T\) trường hợp kiểm thử.

Ở đầu mỗi trường hợp kiểm thử, bộ chấm xuất một dòng chứa một số nguyên: số hiệu của ngày hiện tại. (Bộ chấm bắt đầu ở ngày 1 và vào ngày thứ \(i\), bộ chấm in ra \(i\).) Sau khi đọc số nguyên này, chương trình phải xuất một dòng chứa hai số nguyên \(V\) và \(P\), với \(1 \le V \le 20\) và \(0 \le P \le 100\). Bộ chấm diễn giải chúng như sau:

  • Nếu \(1 \le P \le 100\), bạn bỏ một thẻ của người chơi \(P\) vào bình \(V\). Bộ chấm không xuất lại bất cứ nội dung phản hồi nào.
  • Nếu \(P = 0\), bạn kiểm tra nội dung của bình \(V\). Bộ chấm xuất một dòng gồm các số nguyên. Số nguyên đầu tiên là \(N\), số thẻ trong bình \(V\); tiếp theo là \(N\) số nguyên nữa: số hiệu người chơi trên từng thẻ, theo thứ tự không giảm.

Lưu ý rằng ở lượt 100, bạn phải bỏ thẻ của chính mình vào, nên \(P\) bắt buộc phải bằng 100.

Hãy nhớ rằng vào ngày thứ \(i\), với \(1 \le i \le 99\), bộ chấm mô phỏng hành động của người chơi thứ \(i\) như mô tả trong đề bài. Việc này xảy ra trước hành động của chính bạn trong ngày đó.

Sau khi gửi nước đi cho lượt 100, chương trình phải kết thúc nếu đó là trường hợp kiểm thử cuối cùng; nếu không, chương trình phải bắt đầu đọc dữ liệu cho trường hợp kiểm thử tiếp theo. (Lưu ý rằng bộ chấm không cho bạn biết bạn đã xử lý đúng hay sai từng trường hợp.) Bộ chấm chỉ kiểm tra xem bạn có đủ số câu trả lời đúng hay không sau khi bạn đã thử toàn bộ \(T\) trường hợp kiểm thử, vì vậy bạn không được dừng sớm! Chẳng hạn, nếu bạn trả lời đúng 225 trong 250 trường hợp đầu tiên rồi thoát hoặc cung cấp dữ liệu sai định dạng, lời giải của bạn sẽ không được coi là đúng.

Nếu chương trình xuất nội dung không hợp lệ (ví dụ: đưa ra giá trị \(P\) hoặc \(V\) không hợp lệ, hoặc cố kiểm tra một bình ở lượt 100), bộ chấm sẽ gửi một dòng chứa -1 vào luồng vào của chương trình và không gửi thêm bất cứ dữ liệu nào sau đó. Nếu chương trình tiếp tục chờ bộ chấm sau khi nhận -1, chương trình sẽ hết thời gian và nhận phán quyết Time Limit Exceeded. Bạn có trách nhiệm làm cho chương trình thoát kịp thời để nhận phán quyết Wrong Answer thay vì Time Limit Exceeded. Như thường lệ, nếu chương trình vượt quá tổng bộ nhớ cho phép hoặc gặp lỗi khi chạy, bạn sẽ nhận phán quyết tương ứng.

Phân nhóm

Test Set 1 (Hiển thị)

\(T = 250\).

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ụ kiểm thử này để kiểm thử cục bộ hoặc trên nền tảng của chúng tôi. Để kiểm thử cục bộ, bạn cần chạy công cụ song song với chương trình của mình; bạn có thể dùng trình chạy tương tác của chúng tôi cho việc đó. Để biết thêm thông tin, hãy đọc hướng dẫn trong các chú thích của tệp ấy và xem thêm phần Bài toán tương tác trong FAQ.

Hướng dẫn sử dụng công cụ kiểm thử nằm trong các chú thích bên trong công cụ. Chúng tôi khuyến khích bạn tự bổ sung các trường hợp kiểm thử. Xin lưu ý rằng mặc dù công cụ kiểm thử được thiết kế để mô phỏng hệ thống chấm, nó KHÔNG PHẢI là hệ thống chấm thật và có thể hoạt động khác. Nếu mã của bạn vượt qua công cụ kiểm thử nhưng thất bại trên bộ chấm thật, hãy kiểm tra phần Lập trình trong FAQ để bảo đảm rằng bạn đang 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.

  t = readline_int()           // đọc 250 vào t
  curr_day = readline_int()    // đọc 1 (ngày 1)
  printline 8 100 to stdout    // bỏ một thẻ của người chơi 100 vào bình 8
  flush stdout
  curr_day = readline_int()    // đọc 2 (ngày 2)
  printline 8 99 to stdout     // bỏ một thẻ của người chơi 99 vào bình 8
  flush stdout
  curr_day = readline_int()    // đọc 3 (ngày 3)
  printline 8 100 to stdout    // bỏ một thẻ của người chơi 100 vào bình 8
  flush stdout
  curr_day = readline_int()    // đọc 4 (ngày 4)
  printline 20 7 to stdout     // bỏ một thẻ của người chơi 7 vào bình 20
  flush stdout
  curr_day = readline_int()    // đọc 5 (ngày 5)
  printline 8 0 to stdout      // kiểm tra bình 8
  flush stdout
  tokens = readline_int_list() // đọc 5 2 5 99 100 100 (người chơi 2 và 5
                               //   tình cờ đã chọn bình 8)
  curr_day = readline_int()    // đọc 6 (ngày 6)
  printline 8 101 to stdout    // cố thêm một thẻ mang số hiệu người chơi không hợp lệ
  flush stdout
  curr_day = readline_int()    // đọc -1 (bộ chấm đã xác định lời giải của ta
                               //   không chính xác)
  exit                         // thoát để tránh lỗi TLE không rõ nguyên nhân

Ràng buộc

Nguồn

Google Code Jam 2019, Vòng 2, bài Pottery Lottery.

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