Google Code Jam 2022 - Round 2

Để chào đón người tham dự một hội nghị dành cho lập trình viên trên Io, vệ tinh của Sao Mộc, ban tổ chức đã bơm rất nhiều bóng bãi biển khổng lồ. Mỗi quả bóng có hình gần giống chữ số \(1\) hoặc \(0\), bởi chúng trông hơi giống các chữ I và O. Hội nghị vừa kết thúc nên giờ phải dọn hết bóng. May thay, robot dọn bóng BALL-E đã nhận nhiệm vụ!

Hội nghị được tổ chức trên một đường thẳng ngang vô hạn, với trạm \(0\) ở giữa, các trạm \(1,2,\ldots\) ở bên phải và các trạm \(-1,-2,\ldots\) ở bên trái. Trạm \(0\) chứa kho bóng duy nhất của hội nghị. Mỗi trạm khác chứa nhiều nhất một quả bóng.

BALL-E có hai ngăn chứa, mỗi ngăn đựng được một quả bóng. Một ngăn chỉ đựng bóng hình \(1\), ngăn kia chỉ đựng bóng hình \(0\). Bóng hình \(1\) thuôn dài hơn bóng hình \(0\), nên bóng của mỗi hình không thể vừa ngăn dành cho hình kia.

Ban đầu, cả hai ngăn \(0\) và \(1\) của BALL-E đều trống, và robot xuất phát tại trạm \(0\). Robot có thể thực hiện các thao tác sau:

• Di chuyển sang trạm liền kề bên trái hoặc bên phải, tốn \(1\) đơn vị năng lượng.
• Nếu trạm hiện tại có bóng và BALL-E chưa mang bóng cùng hình, robot có thể cất bóng đó vào ngăn tương ứng, tốn \(0\) năng lượng.
• Nếu trạm hiện tại có bóng, BALL-E có thể nén để đổi bóng sang hình còn lại: bóng hình \(1\) thành hình \(0\) hoặc ngược lại. Thao tác tốn \(C\) năng lượng. BALL-E không thể đổi hình một quả bóng đã được cất trong ngăn.
• Nếu BALL-E đang ở trạm \(0\) và mang ít nhất một bóng, robot có thể gửi toàn bộ bóng trong các ngăn vào kho. Thao tác tốn \(0\) năng lượng và để cả hai ngăn trống.

Lưu ý rằng khi BALL-E tới một trạm có bóng, robot không bắt buộc phải nhặt bóng ngay, ngay cả khi ngăn tương ứng còn trống. Tương tự, khi đến trạm có kho, robot không bắt buộc phải gửi những quả bóng đang mang.

Hãy tìm số đơn vị năng lượng nhỏ nhất để BALL-E chuyển tất cả bóng vào kho, chỉ sử dụng các thao tác trên.

Dữ liệu vào

Dòng đầu chứa số bộ test \(T\). Mỗi bộ test bắt đầu bằng hai số nguyên \(N\) và \(C\): số quả bóng và số đơn vị năng lượng cần để đổi hình một quả bóng. \(N\) dòng tiếp theo mô tả vị trí (số trạm) và hình của các quả bóng. Dòng thứ \(i\) chứa hai số nguyên \(X_i,S_i\), lần lượt là vị trí và hình của quả bóng thứ \(i\).

Dữ liệu ra

Với mỗi bộ test, in một dòng theo dạng Case #x: y, trong đó \(x\) là số thứ tự bộ test, bắt đầu từ \(1\), và \(y\) là số đơn vị năng lượng nhỏ nhất cần để chuyển toàn bộ bóng vào kho như mô tả.

Ràng buộc

• \(1\le T\le100\).
• \(0\le S_i\le1\) với mọi \(i\).
• \(-10^9\le X_i\le10^9\) với mọi \(i\).
• \(0\le C\le10^9\).
• \(X_i\ne0\) với mọi \(i\).
• Mọi \(X_i\) đôi một khác nhau.

Phân nhóm

• Test Set 1 (phán quyết hiển thị): trong nhiều nhất \(15\) test, \(1\le N\le5000\); trong các test còn lại, \(1\le N\le100\).
• Test Set 2 (phán quyết ẩn): trong nhiều nhất \(15\) test, \(1\le N\le10^5\); trong các test còn lại, \(1\le N\le5000\).

Đ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.

Ví dụ

4
5 0
3 0
6 0
8 0
10 1
15 1
5 10
3 0
6 0
8 0
10 1
15 1
5 1
3 0
6 0
8 0
10 1
15 1
2 0
1000000000 0
-1000000000 1

Case #1: 52
Case #2: 56
Case #3: 54
Case #4: 4000000000

Nguồn

Google Code Jam 2022, Vòng 2, bài I, O Bot.

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

Ảnh máy tính thông thường là một ma trận các pixel, trong đó mỗi pixel là một hình vuông nhỏ có một màu cụ thể. Khi vẽ những đường không hoàn toàn song song với các trục của ma trận pixel, hình vẽ sẽ xuất hiện sai lệch. Đường tròn là một ví dụ cực đoan của hiện tượng này.

Giả sử ta có một bức ảnh gồm \((2R+1)\times(2R+1)\) pixel. Các hàng và cột được đánh số từ \(-R\) đến \(R\), sao cho pixel ở tâm nằm tại hàng \(0\), cột \(0\). Ban đầu mọi pixel đều màu trắng. Có thể vẽ một đường tròn đen bán kính \(R\), tâm ở giữa ảnh, bằng giả mã sau; set_pixel_to_black(x, y) tô đen pixel tại hàng \(x\), cột \(y\).

draw_circle_perimeter(R):
  for x between -R and R, inclusive {
    y = round(sqrt(R * R - x * x))   # round to nearest integer, breaking ties towards zero
    set_pixel_to_black(x, y)
    set_pixel_to_black(x, -y)
    set_pixel_to_black(y, x)
    set_pixel_to_black(-y, x)
  }

Một số pixel có thể bị tô đen nhiều lần, nhưng thao tác này có tính lũy đẳng: gọi set_pixel_to_black trên một pixel vốn đã đen sẽ không làm thay đổi gì.

Giả mã sau vẽ một hình tròn đặc, bắt đầu từ một ảnh toàn màu trắng.

draw_circle_filled(R):
  for x between -R and R, inclusive {
    for y between -R and R, inclusive {
      if round(sqrt(x * x + y * y)) <= R:
        set_pixel_to_black(x, y)
    }
  }

Cuối cùng, giả mã sau vẽ sai một hình tròn đặc:

draw_circle_filled_wrong(R):
  for r between 0 and R, inclusive {
    draw_circle_perimeter(r)
  }

Cho \(R\), hãy tính số pixel có màu khác nhau giữa bức ảnh gọi draw_circle_filled(R) và bức ảnh gọi draw_circle_filled_wrong(R).

Dữ liệu vào

Dòng đầu chứa số bộ test \(T\). Mỗi bộ test được mô tả trên một dòng chứa số nguyên \(R\), là bán kính đường tròn cần vẽ.

Dữ liệu ra

Với mỗi bộ test, in một dòng theo dạng Case #x: y, trong đó \(x\) là số thứ tự bộ test, bắt đầu từ \(1\), và \(y\) là số pixel có màu khác nhau giữa bức ảnh tạo bởi draw_circle_filled(R) và bức ảnh tạo bởi draw_circle_filled_wrong(R).

Ràng buộc

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

Phân nhóm

• Test Set 1 (phán quyết hiển thị): \(1\le R\le100\).
• Test Set 2 (phán quyết ẩn): \(1\le R\le10^5\).

Đ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.

Ví dụ

3
2
8
50

Case #1: 4
Case #2: 24
Case #3: 812

Nguồn

Google Code Jam 2022, Vòng 2, bài Pixelated Circle.

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

Mr. Jolly dạy bóng đá cho \(N\) đứa trẻ được đánh số từ \(1\) đến \(N\). Ông thường để lại trên sân nơi thi đấu một viên kẹo cho mỗi trẻ. Khi trận đấu kết thúc, mỗi trẻ có thể lấy và ăn một viên kẹo làm phần thưởng.

Sau trận đấu, bọn trẻ đều mệt nên mỗi em muốn lấy viên kẹo gần mình nhất theo khoảng cách Euclid. Điều này có thể gây tranh giành nếu cùng một viên kẹo gần nhất với từ hai trẻ trở lên. Để tránh chuyện đó, sau trận đấu tất cả trẻ đứng yên tại chỗ, còn Mr. Jolly lần lượt gọi tên từng em. Khi được gọi, trẻ lấy viên kẹo gần mình nhất trong số những viên chưa bị lấy. Nếu có nhiều viên đồng hạng ở khoảng cách nhỏ nhất, Mr. Jolly được quyết định trẻ sẽ lấy viên nào.

Cách làm này đã hoạt động rất tốt trong một thời gian, nhưng hôm nay tai họa xảy ra: khi bày kẹo, Mr. Jolly vô tình làm rơi viên thạch việt quất ông định ăn sau khi bọn trẻ về nhà. Trên sân giờ có \(N\) trẻ và \(N+1\) viên kẹo. Các viên được đánh số từ \(1\) đến \(N+1\), trong đó viên số \(1\) là thạch việt quất của Mr. Jolly. Liệu ông có thể cứu viên thạch bằng cách gọi tên bọn trẻ theo một thứ tự sao cho thạch việt quất là viên duy nhất còn lại hay không?

Dữ liệu vào

Dòng đầu chứa số bộ test \(T\). Mỗi bộ test bắt đầu bằng một dòng chứa \(N\), số trẻ trên sân. \(N\) dòng tiếp theo mô tả vị trí của các trẻ; mỗi dòng chứa hai số nguyên \(X_i,Y_i\), là vị trí của trẻ thứ \(i\) sau trận đấu. Sau đó là \(N+1\) dòng mô tả vị trí các viên kẹo, trong đó viên đầu tiên là thạch việt quất của Mr. Jolly. Mỗi dòng chứa hai số nguyên \(X_j,Y_j\), là vị trí viên kẹo thứ \(j\).

Dữ liệu ra

Với mỗi bộ test, in một dòng theo dạng Case #x: y, trong đó \(x\) là số thứ tự bộ test, bắt đầu từ \(1\). Nếu không có cách chọn thứ tự trẻ và phá hòa để thạch việt quất không bị ăn, \(y\) là IMPOSSIBLE. Nếu cứu được viên thạch, \(y\) là POSSIBLE.

Trong trường hợp POSSIBLE, in thêm \(N\) dòng biểu diễn thứ tự các trẻ đi lấy kẹo và viên kẹo mỗi trẻ lấy. Dòng thứ \(i\) chứa hai số nguyên \(A_i,B_i\), nghĩa là trẻ \(A_i\) đi tiếp theo và lấy viên \(B_i\). Tại thời điểm đó, \(B_i\) phải là viên gần nhất hoặc đồng hạng gần nhất với trẻ \(A_i\).

Ràng buộc

• \(1\le T\le100\).
• \(-10^9\le X_i,Y_i\le10^9\) với mọi trẻ \(i\).
• \(-10^9\le X_j,Y_j\le10^9\) với mọi viên kẹo \(j\).

Phân nhóm

• Test Set 1 (phán quyết hiển thị): \(1\le N\le10\).
• Test Set 2 (phán quyết ẩn): \(1\le N\le1000\).

Đ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.

Ví dụ

4
2
-3 0
-1 0
3 0
-2 -1
-2 1
1
0 0
1 1
2 2
3
10 0
-10 0
0 0
0 5
-1 0
5 0
0 -5
2
3 4
3 4
5 7
3 4
5 7

Case #1: POSSIBLE
2 2
1 3
Case #2: IMPOSSIBLE
Case #3: POSSIBLE
3 2
2 4
1 3
Case #4: POSSIBLE
1 2
2 3

Nguồn

Google Code Jam 2022, Vòng 2, bài Saving the Jelly.

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

Để phạt tính nghịch ngợm, Dante bị nhốt trong một ngôi nhà kỳ lạ có rất nhiều phòng. Ngôi nhà là một lưới phòng \(N\times N\), trong đó \(N\) là số lẻ lớn hơn \(1\). Phòng góc trên bên trái mang số \(1\); các phòng còn lại được đánh số \(2,3,\ldots,N^2\) theo hình xoắn ốc thuận chiều kim đồng hồ. Cụ thể, việc đánh số đi dọc hàng trên cùng, rồi rẽ phải \(90\) độ mỗi khi gặp biên lưới hoặc một phòng đã được đánh số, và kết thúc tại phòng trung tâm. Vì \(N\) lẻ, ngôi nhà luôn có đúng một phòng ở chính giữa và phòng đó luôn mang số \(N^2\).

Chẳng hạn, dưới đây là cách đánh số cho các ngôi nhà có \(N=3\) và \(N=5\).

Dante bắt đầu ở phòng \(1\) và muốn tới phòng trung tâm, tức phòng \(N^2\). Trong suốt hành trình, cậu chỉ có thể đi từ phòng hiện tại sang một phòng kề cạnh có số lớn hơn. Hai phòng chỉ được xem là kề nhau nếu chung một cạnh, không phải chỉ chung một góc.

Dante biết mình có thể đi theo thứ tự số liên tiếp: đang ở phòng \(x\) thì sang \(x+1\), rồi tiếp tục như vậy. Cách đó cần đúng \(N^2-1\) bước. Nhưng Dante muốn làm theo cách riêng: cậu muốn tới phòng trung tâm trong đúng \(K\) bước, với \(K<N^2-1\).

Dante có thể đạt được điều này bằng cách dùng một hoặc nhiều đường tắt. Đường tắt là một bước đi giữa hai phòng không mang số liên tiếp.

Trong ngôi nhà \(5\times5\) ở trên:

• Từ phòng \(1\), Dante không thể sang \(17\), nhưng có thể sang \(2\) hoặc \(16\). Bước sang \(2\) không phải đường tắt vì \(1+1=2\); bước sang \(16\) là đường tắt vì \(1+1\ne16\).
• Từ phòng \(2\), có thể sang \(3\) (không phải đường tắt) hoặc \(17\) (đường tắt), nhưng không thể sang \(1\), \(16\) hay \(18\).
• Từ phòng \(24\), Dante chỉ có thể sang \(25\), và đó không phải đường tắt.
• Không thể đi ra khỏi phòng \(25\).

Xét ví dụ cụ thể trong ngôi nhà \(5\times5\) với \(K=4\). Dante có thể đi \(1\to2\), rồi \(2\to17\) bằng một đường tắt, tiếp theo \(17\to18\), và cuối cùng \(18\to25\) bằng một đường tắt khác. Hình dưới minh họa hành trình; các mũi tên đỏ là đường tắt.

Hãy giúp Dante tìm một dãy đúng \(K\) bước để tới phòng trung tâm, hoặc cho biết điều đó là không thể.

Dữ liệu vào

Dòng đầu chứa số bộ test \(T\). Mỗi bộ test gồm một dòng chứa hai số nguyên \(N,K\), trong đó \(N\) là kích thước ngôi nhà, tức số hàng và cũng là số cột, còn \(K\) là số bước chính xác Dante muốn đi từ phòng \(1\) tới phòng \(N^2\).

Dữ liệu ra

Với mỗi bộ test, in một dòng theo dạng Case #x: y, trong đó \(x\) là số thứ tự bộ test, bắt đầu từ \(1\).

Nếu không có dãy đúng \(K\) bước hợp lệ tới phòng trung tâm, \(y\) phải là IMPOSSIBLE.

Nếu có, \(y\) là số lần Dante dùng đường tắt. Vì Dante muốn kết thúc trong ít hơn \(N^2-1\) bước nên luôn phải dùng ít nhất một đường tắt. Sau đó, in thêm \(y\) dòng, mỗi dòng gồm hai số nguyên. Dòng thứ \(i\) biểu diễn lần thứ \(i\) Dante dùng đường tắt trong hành trình, tức đi từ phòng \(a_i\) sang phòng \(b_i\) sao cho \(a_i+1<b_i\).

Các dòng theo đúng thứ tự hành trình, nên \(a_i<a_{i+1}\) với mọi \(1\le i<y\).

Ràng buộc

• \(1\le T\le100\).
• \(1\le K<N^2-1\).
• \(N\bmod2\equiv1\), tức \(N\) lẻ.

Phân nhóm

• Test Set 1 (phán quyết hiển thị): \(3\le N\le9\).
• Test Set 2 (phán quyết hiển thị): \(3\le N\le39\).
• Test Set 3 (phán quyết ẩn): \(3\le N\le9999\).

Đ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.

Ví dụ

4
5 4
5 3
5 12
3 1

Case #1: 2
2 17
18 25
Case #2: IMPOSSIBLE
Case #3: 2
11 22
22 25
Case #4: IMPOSSIBLE

Nguồn

Google Code Jam 2022, Vòng 2, bài Spiraling Into Control.

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