Google Code Jam 2017 - Qualification Round

Một nhà vệ sinh có \(N+2\) buồng nằm trên một hàng; hai buồng ngoài cùng luôn bị nhân viên bảo vệ chiếm, còn \(N\) buồng ở giữa dành cho người dùng.

Mỗi người bước vào đều cố chọn buồng xa người khác nhất theo quy tắc tất định sau. Với mỗi buồng trống \(S\), họ tính \(L_S\) và \(R_S\): số buồng trống nằm giữa \(S\) và buồng có người gần nhất tương ứng về bên trái và bên phải. Trước tiên họ chỉ xét các buồng tối đa hóa \(\min(L_S,R_S)\). Nếu chỉ còn một buồng thì chọn nó; nếu vẫn hòa, họ tối đa hóa \(\max(L_S,R_S)\); nếu vẫn còn nhiều lựa chọn, họ chọn buồng ngoài cùng bên trái.

Có \(K\) người sắp vào, từng người chọn xong trước khi người tiếp theo xuất hiện, và không ai rời đi. Khi người cuối cùng chọn buồng \(S\), hãy tìm \(\max(L_S,R_S)\) và \(\min(L_S,R_S)\).

Dữ liệu vào

Dòng đầu chứa số test \(T\). Mỗi dòng trong \(T\) dòng tiếp theo chứa hai số nguyên \(N,K\) như mô tả trên.

Dữ liệu ra

Với mỗi test, in Case #x: y z, trong đó x là số thứ tự test bắt đầu từ 1, \(y=\max(L_S,R_S)\) và \(z=\min(L_S,R_S)\) đối với buồng \(S\) mà người cuối cùng chọn.

Ràng buộc

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

Phân nhóm

• Test Set 1 (Visible): \(1\le N\le1000\).
• Test Set 2 (Visible): \(1\le N\le10^6\).
• Test Set 3 (Hidden): \(1\le N\le10^{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.

Ví dụ

5
4 2
5 2
6 2
1000 1000
1000 1

Case #1: 1 0
Case #2: 1 0
Case #3: 1 1
Case #4: 0 0
Case #5: 500 499

Nguồn

Google Code Jam 2017, Vòng loại, bài Bathroom Stalls.

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

Bạn sắp tổ chức một buổi trình diễn ba phong cách thời trang trên sân khấu dạng lưới \(N\times N\). Mỗi ô hoặc trống (ký hiệu .), hoặc chứa một người mẫu loại +, x hay loại siêu thời thượng o. Mỗi + hoặc x cho 1 điểm phong cách, mỗi o cho 2 điểm, ô trống không cho điểm.

Để đạt hiệu quả nghệ thuật tối đa, cách đặt phải tuân theo:

• Nếu hai người mẫu cùng hàng hoặc cùng cột, ít nhất một người phải là +.
• Nếu hai người mẫu cùng một đường chéo, ít nhất một người phải là x.

Một cách chính xác, hai ô \((i_0,j_0)\) và \((i_1,j_1)\) cùng hàng khi \(i_0=i_1\), cùng cột khi \(j_0=j_1\), và cùng đường chéo khi \(i_0+j_0=i_1+j_1\) hoặc \(i_0-j_0=i_1-j_1\).

Ví dụ, lưới sau không hợp lệ:

...
x+o
.+.

Ở hàng giữa, cặp x và o không có ai là +. Trên đường chéo từ + ở hàng cuối tới o ở hàng giữa cũng có hai người mà không ai là x.

Ngược lại, lưới sau hợp lệ vì không hàng, cột hay đường chéo nào vi phạm:

+.x
+x+
o..

Cố vấn đã đặt trước \(M\) người mẫu theo đúng quy tắc. Bạn có thể thêm tùy ý (kể cả không thêm) bất kỳ loại nào. Không được bỏ người mẫu có sẵn, nhưng có thể nâng cấp bao nhiêu + hoặc x thành o tùy ý, miễn vẫn hợp lệ. Hãy tìm một cách đặt/thay thế hợp lệ có tổng điểm phong cách lớn nhất.

Dữ liệu vào

Dòng đầu chứa số test \(T\). Mỗi test bắt đầu bằng \(N,M\), sau đó là \(M\) dòng; dòng thứ \(i\) chứa loại +, x hoặc o và hai số \(R_i,C_i\). Hàng được đánh số từ 1 đến \(N\) từ trên xuống, cột từ 1 đến \(N\) từ trái sang phải.

Dữ liệu ra

Với mỗi test, trước tiên in Case #x: y z, trong đó x là số thứ tự test bắt đầu từ 1, y là tổng điểm của cách bố trí và z là tổng số người mẫu đã thêm hoặc thay thế. Sau đó in đúng \(z\) dòng theo định dạng input, ghi loại cuối cùng và vị trí của từng người mẫu được thêm/thay; các dòng có thể theo thứ tự bất kỳ.

Nếu có nhiều đáp án hợp lệ, có thể in bất kỳ đáp án nào.

Ràng buộc

• \(1\le T\le100\).
• \(1\le N\le100\).
• \(1\le C_i\le N\).
• \(0\le M\le N^2\).
• Không có hai người mẫu đặt sẵn trong cùng ô.
• Cách đặt ban đầu được bảo đảm hợp lệ.

Phân nhóm

• Test Set 1 (Visible): \(R_i=1\) với mọi \(i\); mọi người mẫu đặt sẵn đều ở hàng trên cùng, nhưng vẫn có thể thêm/thay trong hàng này hoặc thêm ở hàng khác.
• Test Set 2 (Hidden): \(1\le R_i\le N\); không có hạn chế thêm về hàng.

Đ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 0
1 1
o 1 1
3 4

+ 2 3
+ 2 1
x 3 1
+ 2 2

Case #1: 4 3
o 2 2
+ 2 1
x 1 1
Case #2: 2 0
Case #3: 6 2
o 2 3
x 1 2

x.
+o

...
+++
x..

.x.
++o
x..

Nguồn

Google Code Jam 2017, Vòng loại, bài Fashion Show.

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

Năm ngoái, Infinite House of Pancakes giới thiệu một loại bánh mới: một mặt có khuôn mặt vui bằng hạt sô-cô-la (“mặt vui”), mặt kia không có gì (“mặt trắng”).

Bạn là bếp trưởng trực ca. Bánh được nướng thành một hàng trên bề mặt nóng. Để tiếp tục nâng cao hiệu suất, nhà hàng cấp cho bạn một xẻng lật quá khổ, mỗi lần lật đúng \(K\) chiếc bánh liên tiếp. Trong đoạn ấy, mọi bánh đang ngửa mặt vui sẽ thành mặt trắng và ngược lại; thứ tự trái sang phải của bánh không đổi.

Bạn không thể dùng xẻng để lật ít hơn \(K\) chiếc, kể cả ở hai đầu hàng vì bề mặt nướng có gờ cao hai bên. Chẳng hạn, có thể lật \(K\) chiếc đầu tiên nhưng không thể lật chỉ \(K-1\) chiếc đầu.

Người học việc vừa dùng xẻng loại cũ để lật riêng một số bánh rồi mang xẻng ấy vào nhà vệ sinh, ngay trước lúc khách tham quan bếp. Bạn chỉ còn xẻng quá khổ và cần nhanh chóng làm mọi chiếc bánh ngửa mặt vui để khách ra về vui vẻ.

Biết trạng thái hiện tại, hãy tính số lần dùng xẻng ít nhất để tất cả bánh ngửa mặt vui, hoặc cho biết điều đó là không thể.

Dữ liệu vào

Dòng đầu chứa số test \(T\). Mỗi test gồm một dòng chứa chuỗi \(S\) và số nguyên \(K\). Chuỗi \(S\) biểu diễn hàng bánh: + là bánh ban đầu ngửa mặt vui, - là bánh ban đầu ngửa mặt trắng.

Dữ liệu ra

Với mỗi test, in Case #x: y, trong đó x là số thứ tự test bắt đầu từ 1; y là IMPOSSIBLE nếu không thể làm mọi bánh ngửa mặt vui, hoặc là số lần dùng xẻng ít nhất.

Ràng buộc

• \(1\le T\le100\).
• Mỗi ký tự của \(S\) là + hoặc -.
• \(2\le K\le |S|\).

Phân nhóm

• Test Set 1 (Visible): \(2\le |S|\le10\).
• Test Set 2 (Hidden): \(2\le |S|\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ụ

3
---+-++- 3
+++++ 4
-+-+- 4

Case #1: 3
Case #2: 0
Case #3: IMPOSSIBLE

Nguồn

Google Code Jam 2017, Vòng loại, bài Oversized Pancake Flipper.

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

Tatiana thích giữ mọi thứ thật ngăn nắp. Đồ chơi của cô được xếp từ nhỏ đến lớn, bút chì từ ngắn đến dài, còn máy tính từ cũ đến mới. Một ngày nọ, khi luyện đếm, cô nhận thấy một số số nguyên khi được viết ở hệ cơ số 10 và không có chữ số 0 ở đầu thì các chữ số của chúng được sắp theo thứ tự không giảm. Chẳng hạn, 8, 123, 555 và 224488 đều có tính chất này. Cô gọi những số như vậy là số gọn gàng (tidy number). Những số không có tính chất ấy, như 20, 321, 495 và 999990, không phải số gọn gàng.

Cô vừa đếm xong tất cả các số nguyên dương theo thứ tự tăng dần từ 1 đến \(N\). Số gọn gàng cuối cùng mà cô đã đếm là số nào?

Dữ liệu vào

Dòng đầu tiên chứa số lượng bộ test \(T\). Tiếp theo là \(T\) dòng; mỗi dòng mô tả một bộ test bằng một số nguyên \(N\), số cuối cùng Tatiana đã đếm.

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) và y là số gọn gàng cuối cùng Tatiana đã đếm.

Ràng buộc

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

Phân nhóm

• Test Set 1 (Visible): \(1 \le N \le 1000\).
• Test Set 2 (Hidden): \(1 \le N \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.

Ví dụ

4
132
1000
7
111111111111111110

Case #1: 129
Case #2: 999
Case #3: 7
Case #4: 99999999999999999

Nguồn

Google Code Jam 2017, Vòng loại, bài Tidy Numbers.

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