Google Code Jam 2020 - 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 2020 - Emacs++ 35 6.5s 1G
2 Google Code Jam 2020 - Incremental House of Pancakes 19 1.0s 1G
3 Google Code Jam 2020 - Security Update 20 1.0s 1G
4 Google Code Jam 2020 - Wormhole in One 26 1.0s 1G

1. Google Code Jam 2020 - Emacs++

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

Năm 2016, tại Distributed Code Jam, chúng tôi đã giới thiệu ngôn ngữ Lisp++ dành cho những người hâm mộ Lisp thích mật độ dấu ngoặc cao hơn. Sau đây là phần nhắc lại về cú pháp của ngôn ngữ này.

Một chương trình Lisp++ là một chuỗi dấu ngoặc cân bằng. Chính xác hơn, một chương trình Lisp++ có một trong các dạng sau. (Trong đặc tả này, \(C\) biểu thị một đoạn mã chương trình nào đó — không nhất thiết là cùng một đoạn mã ở mỗi lần xuất hiện.)

  • () — đúng nghĩa chỉ gồm một dấu ngoặc mở và một dấu ngoặc đóng. Ta nói dấu ( này khớp với dấu ) này, và ngược lại.
  • (\(C\)) — một chương trình nằm bên trong một cặp dấu ngoặc bao ngoài. Ta nói dấu ( này khớp với dấu ) này, và ngược lại.
  • \(CC\) — hai chương trình (không nhất thiết giống nhau) đặt liền nhau.

Năm nay, chúng tôi hân hạnh công bố Emacs++, một trình xem văn bản dành cho Lisp++. Emacs++ hiển thị một chương trình Lisp++ có độ dài \(K\) trên một dòng dài duy nhất, cùng một con trỏ mà bạn có thể di chuyển. Con trỏ là một "con trỏ khối", luôn nằm trên một trong \(K\) ký tự của chương trình chứ không nằm giữa hai ký tự.

Tại bất kỳ thời điểm nào, bạn có thể thực hiện một trong ba thao tác sau để di chuyển con trỏ. (\(i\) là vị trí hiện tại của con trỏ, đánh số từ 1 tại vị trí ngoài cùng bên trái.)

  • Di chuyển con trỏ sang trái một ký tự (hoặc không làm gì nếu con trỏ đã ở ký tự ngoài cùng bên trái). Thao tác này mất \(L_i\) giây.
  • Di chuyển con trỏ sang phải một ký tự (hoặc không làm gì nếu con trỏ đã ở ký tự ngoài cùng bên phải). Thao tác này mất \(R_i\) giây.
  • Dịch chuyển tức thời con trỏ tới dấu ngoặc khớp (theo định nghĩa ở trên) với dấu ngoặc là ký tự thứ \(i\). Thao tác này mất \(P_i\) giây.

Chúng tôi cho rằng Emacs++ sẽ đơn giản đối với người dùng thành thạo, nhưng vẫn cần hiểu mức độ hiệu quả của nó. Ta có một chương trình Lisp++ duy nhất và danh sách \(Q\) truy vấn về chương trình đó; mỗi truy vấn gồm vị trí bắt đầu \(S_j\) và vị trí kết thúc \(E_j\). Để trả lời truy vấn thứ \(j\), bạn phải xác định khoảng thời gian nhỏ nhất có thể \(N_j\) (tính bằng giây) để đưa con trỏ từ \(S_j\) tới \(E_j\) nếu luôn đưa ra các quyết định tối ưu.

Hãy in tổng của tất cả các giá trị \(N_j\) đó.

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 mỗi bộ test chứa hai số nguyên \(K\), là độ dài chương trình Lisp++, và \(Q\), là số lượng truy vấn.

Dòng thứ hai chứa chuỗi \(P\) gồm \(K\) ký tự, mỗi ký tự là ( hoặc ), biểu diễn một chương trình Lisp++ (chuỗi dấu ngoặc cân bằng) như mô tả ở trên.

Dòng thứ ba, thứ tư và thứ năm, mỗi dòng chứa \(K\) số nguyên. Số thứ \(i\) trên các dòng này lần lượt là \(L_i\), \(R_i\) và \(P_i\) đã mô tả ở trên.

Dòng thứ sáu và thứ bảy, mỗi dòng chứa \(Q\) số nguyên. Số thứ \(j\) trên các dòng này lần lượt là \(S_j\) và \(E_j\) đã mô tả ở trên.

Dữ liệu ra

Với mỗi bộ test, in một dòng Case #x: y, trong đó x là số thứ tự bộ test (bắt đầu từ 1) và y là tổng các giá trị \(N_j\).

Ràng buộc

  • \(1 \le T \le 100\).
  • \(K = 10^5\) và \(Q = 10^5\) đối với nhiều nhất 9 bộ test.
  • \(2 \le K \le 1000\) và \(1 \le Q \le 1000\) trong tất cả trường hợp còn lại.
  • Độ dài của \(P\) bằng \(K\).
  • \(P\) là chuỗi dấu ngoặc cân bằng như mô tả ở trên.
  • \(1 \le S_j \le K\) với mọi \(j\).
  • \(1 \le E_j \le K\) với mọi \(j\).

Phân nhóm

Test Set 1 (Visible Verdict)

  • \(L_i = 1\) với mọi \(i\).
  • \(R_i = 1\) với mọi \(i\).
  • \(P_i = 1\) với mọi \(i\).

Test Set 2 (Hidden Verdict)

  • \(1 \le L_i \le 10^6\) với mọi \(i\).
  • \(1 \le R_i \le 10^6\) với mọi \(i\).
  • \(1 \le P_i \le 10^6\) 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 12/35 34,29%
Test Set 2 23/35 65,71%

Ví dụ

Ví dụ 1

Input

```sample
1

12 5
(()(((()))))
1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1
7 4 4 12 5
12 11 10 1 6
```
???+ success "Output"

Case #1: 10

??? "Giải thích"
Bộ test mẫu tuân theo giới hạn của Test Set 1, nên mọi chi phí thời gian đều bằng nhau (1 giây cho mỗi lần di chuyển).

    Thời gian ngắn nhất cho các truy vấn như sau:


    1. Di chuyển sang phải năm lần từ vị trí 7 đến 12, mất 5 giây.
    2. Dịch chuyển tức thời từ vị trí 4 đến 11, mất 1 giây.
    3. Dịch chuyển tức thời từ vị trí 4 đến 11, rồi sang trái đến 10, mất 2 giây.
    4. Dịch chuyển tức thời từ vị trí 12 đến 1, mất 1 giây.
    5. Di chuyển sang phải từ vị trí 5 đến 6, mất 1 giây.

    Vì vậy, tổng thời gian là $5+1+2+1+1=10$ giây.

Nguồn

Google Code Jam 2020, Vòng 2, bài Emacs++.

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 2020 - Incremental House of Pancakes

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

Mỗi sáng tại Nhà Bánh Kếp Tăng Dần, nhân viên nhà bếp chuẩn bị toàn bộ bánh kếp cho ngày hôm đó và xếp chúng thành hai chồng. Ban đầu, chồng bên trái có \(L\) chiếc bánh kếp và chồng bên phải có \(R\) chiếc bánh kếp.

Khách hàng của nhà hàng này có thói quen rất nhất quán: khách thứ \(i\) đến nhà hàng (đánh số từ 1) luôn gọi \(i\) chiếc bánh kếp. Khi khách thứ \(i\) gọi \(i\) chiếc, bạn lấy \(i\) chiếc từ chồng hiện còn nhiều bánh nhất (hoặc từ chồng bên trái nếu hai chồng có số bánh bằng nhau). Nếu không chồng nào có ít nhất \(i\) chiếc bánh, nhà hàng đóng cửa và khách thứ \(i\) không được phục vụ chiếc bánh nào. Bạn không bao giờ dùng bánh từ cả hai chồng để hoàn thành một đơn gọi món.

Biết số bánh kếp ban đầu trong mỗi chồng, hãy xác định có bao nhiêu khách hàng được phục vụ và mỗi chồng còn lại bao nhiêu chiếc bánh khi nhà hàng đóng cửa.

Dữ liệu vào

Dòng đầu tiên của dữ liệu vào cho biết số bộ test, \(T\). Tiếp theo là \(T\) bộ test. Mỗi bộ test gồm một dòng chứa hai số nguyên \(L\) và \(R\): lần lượt là số bánh kếp ban đầu trong chồng bên trái và chồng bên phải như mô tả ở trên.

Dữ liệu ra

Với mỗi bộ test, in một dòng có dạng Case #x: n l r, trong đó x là số thứ tự bộ test (bắt đầu từ 1), n là số khách hàng được phục vụ, còn l và r lần lượt là số bánh kếp còn lại trong chồng bên trái và bên phải khi nhà hàng đóng cửa.

Ràng buộc

  • \(1 \le T \le 1000\).

Phân nhóm

Test Set 1 (Visible Verdict):

  • \(1 \le L \le 1000\).
  • \(1 \le R \le 1000\).

Test Set 2 (Hidden Verdict):

  • \(1 \le L \le 10^{18}\).
  • \(1 \le R \le 10^{18}\).

Đ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/19 26,32%
Test Set 2 14/19 73,68%

Ví dụ

Ví dụ 1

Input 
3
1 2
2 2
8 11
Output 
Case #1: 1 1 1
Case #2: 2 1 0
Case #3: 5 0 4
Giải thích

Trong bộ test mẫu số 1, khách hàng đầu tiên nhận 1 chiếc bánh từ chồng bên phải, khiến mỗi chồng còn lại 1 chiếc. Khách hàng thứ hai muốn 2 chiếc bánh, nhưng không chồng nào có đủ cho họ, mặc dù tổng cộng vẫn còn 2 chiếc bánh.

Trong bộ test mẫu số 2, khách hàng đầu tiên nhận 1 chiếc bánh từ chồng bên trái vì hai chồng có số bánh bằng nhau. Sau đó, chồng bên trái còn 1 chiếc và chồng bên phải còn 2 chiếc. Khách hàng thứ hai muốn 2 chiếc bánh; bạn phục vụ họ bằng chồng bên phải và làm chồng này hết sạch. Khi khách hàng thứ ba đến, không chồng nào có 3 chiếc bánh, nên không có thêm đơn gọi món nào được phục vụ.

Trong bộ test mẫu số 3, khách hàng đầu tiên được phục vụ từ chồng bên phải, khiến chồng bên trái còn 8 chiếc và chồng bên phải còn 10 chiếc. Khách hàng thứ hai cũng được phục vụ từ chồng bên phải, khiến mỗi chồng còn 8 chiếc. Khách hàng thứ ba được phục vụ từ chồng bên trái, khiến chồng này còn 5 chiếc và chồng bên phải còn 8 chiếc. Sau đó, khách hàng thứ tư được phục vụ từ chồng bên phải, khiến chồng này còn 4 chiếc. Phục vụ khách hàng thứ năm làm chồng bên trái hết sạch; tiếp đó, không chồng nào còn đủ bánh để phục vụ khách hàng thứ sáu.

Nguồn

Google Code Jam 2020, Vòng 2, bài Incremental House of Pancakes.

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 2020 - Security Update

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

Security Update

Công ty Apricot Rules vừa cài đặt một bản cập nhật bảo mật quan trọng cho mạng của mình. Mạng có một máy nguồn, và mọi máy tính khác trong mạng đều kết nối với máy nguồn qua một dãy gồm một hoặc nhiều kết nối trực tiếp hai chiều.

Loại bản cập nhật này tự lan truyền: ngay khi một máy tính nhận bản cập nhật lần đầu tiên, máy đó lập tức bắt đầu truyền bản cập nhật tới tất cả các máy kết nối trực tiếp với nó. Mỗi kết nối trực tiếp có một giá trị độ trễ: số giây cần thiết để kết nối ấy truyền bản cập nhật (giống nhau theo cả hai chiều). Vì vậy, bản cập nhật không lan đến tất cả các máy ngay lập tức.

Các kỹ sư của Apricot Rules không biết bất kỳ giá trị độ trễ nào, nhưng họ biết tất cả chúng đều là số nguyên dương. Họ muốn bạn giúp xác định các giá trị độ trễ có thể là bao nhiêu, dựa trên những gì họ quan sát được về sự lan truyền của bản cập nhật trong một thí nghiệm gần đây.

Các kỹ sư của Apricot Rules chỉ cài đặt bản cập nhật trên máy nguồn, rồi chờ nó lan truyền khắp hệ thống cho đến khi mọi máy đều được cập nhật. Họ ghi lại một số thông tin về quá trình lan truyền. Cụ thể, với mỗi máy K không phải máy nguồn, bạn biết chính xác một trong hai điều sau:

  • Khoảng thời gian chính xác, tính bằng giây, từ lúc máy nguồn nhận bản cập nhật đến lúc K nhận bản cập nhật lần đầu tiên.
  • Số máy khác (bao gồm cả máy nguồn) nhận bản cập nhật lần đầu tiên sớm hơn K một cách nghiêm ngặt.

Lưu ý rằng nhiều máy có thể nhận bản cập nhật vào đúng cùng một thời điểm.

Bạn phải tính độ trễ theo giây cho mỗi kết nối trực tiếp giữa hai máy. Mỗi giá trị độ trễ phải là một số nguyên dương không lớn hơn \(10^6\). Tập các độ trễ bạn đưa ra phải phù hợp với toàn bộ thông tin đã biết. Đề bài bảo đảm có ít nhất một cách gán độ trễ phù hợp.

Dữ liệu vào

Dòng đầu tiên cho biết số 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 \(C\) và \(D\): lần lượt là số máy tính và số kết nối trực tiếp. Các máy được đánh số từ 1 đến \(C\), trong đó máy 1 là máy nguồn.

Dòng tiếp theo chứa \(C-1\) số nguyên \(X_2, X_3, \ldots, X_C\). Giá trị \(X_i\) dương cho biết máy \(i\) nhận bản cập nhật sau máy 1 đúng \(X_i\) giây. Giá trị \(X_i\) âm cho biết có \(-X_i\) máy khác nhận bản cập nhật sớm hơn máy \(i\) một cách nghiêm ngặt; con số này bao gồm cả máy nguồn.

Sau đó có thêm \(D\) dòng biểu diễn \(D\) kết nối trực tiếp trong mạng. Dòng thứ \(i\) chứa hai số nguyên \(U_i\) và \(V_i\), cho biết máy \(U_i\) và máy \(V_i\) kết nối trực tiếp với nhau.

Dữ liệu ra

Với mỗi bộ test, in một dòng có dạng Case #x: y1 y2 ... yD, trong đó x là số thứ tự bộ test (bắt đầu từ 1), còn \(y_i\) là một số nguyên dương không lớn hơn \(10^6\), biểu diễn độ trễ tính bằng giây được gán cho kết nối trực tiếp thứ \(i\).

Ràng buộc

  • \(1 \le T \le 100\).
  • \(2 \le C \le 100\).
  • \(C-1 \le D \le 1000\).
  • \(1 \le U_i < V_i \le C\) với mọi \(i\).
  • \((U_i,V_i) \ne (U_j,V_j)\) với mọi \(i \ne j\).
  • Mọi máy (ngoại trừ máy nguồn) đều kết nối với máy nguồn qua một dãy gồm một hoặc nhiều kết nối trực tiếp.
  • Tồn tại ít nhất một cách gán các giá trị độ trễ phù hợp với dữ liệu vào.

Phân nhóm

Test Set 1 (Phán quyết hiển thị)

\(-C < X_i < 0\) với mọi \(i\). (Bạn nhận được loại thông tin thứ hai cho tất cả các máy.)

Test Set 2 (Phán quyết ẩn)

  • \(-C < X_i \le 1000\) với mọi \(i\).
  • \(X_i \ne 0\) 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 9/20 45%
Test Set 2 11/20 55%

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

Dữ liệu vào mẫu

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

Dữ liệu ra mẫu

Case #1: 5 10 1 5
Case #2: 2020 2020 2020 2020
Case #3: 1000000 1000000

Trong test mẫu số 1, hình sau biểu diễn mạng máy tính được minh họa bởi dữ liệu ra mẫu. Máy thứ \(i\) được biểu diễn bằng hình tròn mang nhãn \(i\). Một đường nối hai hình tròn biểu diễn một kết nối trực tiếp. Số trên mỗi đường biểu diễn độ trễ của kết nối trực tiếp đó.

Trong test mẫu số 2, ba kết nối đầu tiên phải có cùng độ trễ, còn kết nối thứ tư có thể có bất kỳ độ trễ hợp lệ nào. Lưu ý rằng \(-2\), \(0\), \(1000001\) và \(3.14\) là các ví dụ về độ trễ không hợp lệ.

Trong test mẫu số 3, hãy nhớ rằng các kết nối là hai chiều, nên bản cập nhật có thể truyền từ máy 3 sang máy 2. Bất kỳ hai giá trị độ trễ hợp lệ nào cũng dùng được ở đây.

Trường hợp sau không thể xuất hiện trong Test Set 1, nhưng có thể xuất hiện trong Test Set 2:

1
6 9
10 -2 -5 15 20
1 2
1 3
2 3
2 4
2 5
3 5
3 6
4 5
5 6

Một trong các dữ liệu ra đúng là 10 12 4 15 8 3 9 7 5, như minh họa trong hình dưới đây.

Nguồn

Google Code Jam 2020, Vòng 2, bài Security Update.

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 2020 - Wormhole in One

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

Đề bài

Bạn đang tham gia một cuộc thi golf siêu không gian liên thiên hà và đã tiến vào vòng chung kết! Bạn thực sự quyết tâm giành chiến thắng, vì vậy bạn muốn chuẩn bị một chiến thuật tất thắng.

Trong golf siêu không gian, cũng như trong golf thông thường, bạn dùng gậy đánh một quả bóng, khiến bóng bay theo hướng do bạn chọn. Sân chơi là một mặt phẳng hai chiều, trên đó các điểm biểu diễn những lỗ khác nhau. Quả bóng cũng được biểu diễn bằng một điểm, và bạn được chọn vị trí xuất phát của bóng, miễn là vị trí đó không trùng với một lỗ.

Vì đây là golf siêu không gian, người chơi được phép biến một số cặp lỗ thành các lỗ sâu bằng cách liên kết chúng với nhau. Mỗi lỗ hoặc được để lại làm lỗ bình thường, hoặc được liên kết với nhiều nhất một lỗ khác (không bao giờ với chính nó). Lỗ sâu là liên kết vô hướng và có thể được đi qua theo cả hai chiều.

Do môi trường không có ma sát, khi bạn đánh bóng, bóng chuyển động thẳng theo một hướng và giữ hướng đó mãi mãi, trừ khi nó đến một lỗ; gọi lỗ đó là \(h\). Khi chạm \(h\), bóng dừng nếu \(h\) không nối với lỗ nào khác. Nếu \(h\) nối với một lỗ khác \(h'\), bóng lập tức đi ra từ \(h'\) rồi tiếp tục chuyển động theo đúng hướng trước đó.

Bạn biết vị trí của mỗi lỗ. Bạn muốn tối đa hóa số lỗ phân biệt có thể chạm bằng một cú đánh. Vì vậy, bạn muốn chọn vị trí xuất phát, hướng đánh và những cặp lỗ sẽ được liên kết thành lỗ sâu, nếu có. Bóng không được xuất phát tại cùng vị trí với một lỗ sâu. Khi bóng đi qua một lỗ sâu, cả lỗ đi vào lẫn lỗ đi ra đều được tính. Mỗi lỗ chỉ được tính một lần, kể cả khi bóng đi vào hoặc đi ra khỏi nó (hoặc cả hai) nhiều lần. Nếu bóng dừng trong một lỗ, lỗ đó cũng được tính.

Dữ liệu vào

Dòng đầu cho biết 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 \(N\): tổng số lỗ. \(N\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(X_i\) và \(Y_i\), lần lượt là tọa độ X và Y của lỗ thứ \(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à số lỗ phân biệt lớn nhất có thể chạm nếu đưa ra các quyết định tối ưu như trên.

Ràng buộc

  • \(1 \le T \le 100\).
  • \(-10^9 \le X_i \le 10^9\) với mọi \(i\).
  • \(-10^9 \le Y_i \le 10^9\) với mọi \(i\).
  • \((X_i,Y_i) \ne (X_j,Y_j)\) với mọi \(i \ne j\). (Không có hai lỗ cùng tọa độ.)

Phân nhóm

Test Set 1 (phán quyết hiển thị)

\(1 \le N \le 7\).

Test Set 2 (phán quyết ẩn)

\(1 \le N \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/26 38,46%
Test Set 2 16/26 61,54%

Ví dụ

Ví dụ 1

Input 
5
2
0 0
5 5
3
0 0
5 5
5 0
5
0 0
5 5
5 0
3 2
2 4
7
0 0
1 1
2 1
3 1
8 2
11 2
14 2
1
-1000000000 1000000000
Output 
Case #1: 2
Case #2: 3
Case #3: 4
Case #4: 7
Case #5: 1
Giải thích

Trong trường hợp mẫu số 1, ta có thể nối hai lỗ bằng một lỗ sâu để chạm cả hai bằng cách đưa bóng vào một trong hai lỗ. Nếu không có lỗ sâu, bóng sẽ dừng tại lỗ đầu tiên nó chạm, nên không thể chạm nhiều hơn một lỗ.

Trong trường hợp mẫu số 2, ta có thể nối lỗ tại \((0,0)\) với lỗ tại \((5,5)\). Sau đó, chẳng hạn ta đánh bóng từ \((4.9,5)\) theo chiều ngang dương để bóng chạm \((5,5)\) trước. Bóng đi vào đó rồi đi ra từ \((0,0)\), vẫn giữ hướng ngang dương. Cuối cùng, bóng chạm \((5,0)\) và dừng (vì lỗ đó không được liên kết với lỗ sâu nào).

Trong trường hợp mẫu số 3, ta có thể nối cặp lỗ tại \((0,0)\) và \((5,0)\), đồng thời nối cặp tại \((3,2)\) và \((5,5)\). Đánh bóng từ \((4,-1)\) về phía \((5,0)\) khiến bóng lần lượt chạm \((5,0)\), \((0,0)\), \((5,5)\) và \((3,2)\).

Trong trường hợp mẫu số 4, ta có thể nối các cặp \((0,0)\)–\((1,1)\), \((2,1)\)–\((11,2)\) và \((8,2)\)–\((14,2)\). Đánh bóng từ \((-1,0)\) về phía \((0,0)\) khiến bóng lần lượt chạm: \((0,0)\), \((1,1)\), \((2,1)\), \((11,2)\), \((14,2)\), \((8,2)\), \((11,2)\), \((2,1)\) và \((3,1)\). Dù \((11,2)\) và \((2,1)\) được chạm hai lần, mỗi lỗ chỉ được tính một lần vì đề bài yêu cầu đếm các lỗ phân biệt.

Trong trường hợp mẫu số 5, chỉ có một lỗ và ta có thể đánh bóng vào đó mà không cần xét lỗ sâu. (Ta có thể chọn bất kỳ vị trí xuất phát nào, kể cả bên ngoài miền tọa độ được phép của các lỗ.)

Nguồn

Google Code Jam 2020, Vòng 2, bài Wormhole in One.

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