Google Code Jam 2015 - World Finals

“Mùa hè cuối cùng cũng đã đến: đã tới lúc nghỉ ngơi, vui chơi, ra ngoài và tận hưởng thời tiết đẹp!” Alice nói. Cô là một kiểm lâm tận tụy làm việc tại một Vườn quốc gia nổi tiếng. Vào mùa hè, nhiều gia đình tới đây cắm trại, và nhiệm vụ của Alice là bố trí chỗ cho họ.

Alice phụ trách một khu cắm trại dạng ma trận \(N\times N\); mỗi ô có chỗ cho nhiều nhất một lều. Khi sắp xếp các gia đình, cô phải tuân thủ các quy định sau:

• Chỉ các gia đình có 1, 2 hoặc 3 thành viên được vào khu cắm trại. Mỗi lều chỉ chứa người của một gia đình, và một gia đình không thể bị chia ra nhiều lều.
• Vì lý do an ninh, Alice không muốn hàng hoặc cột nào quá đông hay quá vắng: mỗi hàng và mỗi cột phải có đúng 3 người.
• Theo chính sách an toàn của vườn, mỗi hàng và mỗi cột không được có quá 2 lều.

Alice còn biết trước rằng ít nhất \(X\) gia đình ba người sẽ tới, và sẽ luôn có đủ gia đình một hoặc hai người để lấp đầy phần còn lại.

Ví dụ, các cách bố trí sau hợp lệ với \(N=3\) và \(X=0\):

1  2  0  |  3  0  0
0  1  2  |  0  1  2
2  0  1  |  0  2  1

Các cách sau không hợp lệ với \(N=3\) và \(X=1\):

1  2  0  |  0  3  0  |  1  2  0  |  1  1  1
0  1  2  |  3  0  0  |  0  2  0  |  1  1  1
2  0  1  |  0  0  0  |  2  0  1  |  1  1  1

• Cách thứ nhất không hợp lệ vì phải có ít nhất một gia đình ba người.
• Ở cách thứ hai, hàng thứ ba (và cột thứ ba) không có đúng ba người.
• Ở cách thứ ba, cột thứ hai có hơn ba người (còn hàng thứ hai có ít hơn ba người).
• Cách cuối có hơn hai lều trong một hàng hoặc cột.

Alice muốn biết có bao nhiêu cách bố trí khác nhau với \(N\) và \(X\) đã cho. Hai cách bố trí \(A\) và \(B\) khác nhau nếu có một ô chứa lều trong cách này nhưng không chứa lều trong cách kia; hoặc nếu cùng ô đó đều có lều nhưng số thành viên trong lều ở \(A\) khác ở \(B\).

Dữ liệu vào

Dòng đầu là \(T\). Mỗi test gồm \(N,X\).

Dữ liệu ra

In Case #X: Y, với \(Y\) là số cách modulo \(10^9+7\).

Ràng buộc

• \(1\le T\le200\), \(0\le X\le N\).

Phân nhóm

• Nhỏ: \(1\le N\le20\).
• Lớn: \(1\le N\le10^6\).

Đ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 2
3 1
15 0

Case #1: 2
Case #2: 24
Case #3: 738721209

0 3  |  3 0
3 0  |  0 3

Nguồn

Google Code Jam 2015, Chung kết thế giới, bài Campinatorics.

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 được yêu cầu cài đặt một thuật toán có thể coi là quan trọng nhất: tìm kiếm nhị phân. Cụ thể, bạn có một mảng đối tượng đã sắp xếp và một đối tượng mới cần chèn. Để tìm vị trí chèn, bạn có thể so sánh đối tượng mới với các đối tượng trong mảng. Mỗi phép so sánh trả về “greater”, nghĩa là đối tượng mới phải được chèn bên phải đối tượng đang xét, hoặc “less”, nghĩa là phải chèn bên trái. Để đơn giản, phép so sánh không bao giờ trả về “equal”.

Đề bảo đảm rằng nếu đối tượng mới lớn hơn một đối tượng trong mảng thì nó cũng lớn hơn mọi đối tượng nằm bên trái đối tượng ấy; tương tự, nếu nó nhỏ hơn một đối tượng thì nó cũng nhỏ hơn mọi đối tượng nằm bên phải. Nếu mảng có \(n\) phần tử, thuật toán có \(n+1\) kết quả (vị trí chèn) khả dĩ.

Trong bài này, các phép so sánh không có cùng chi phí. So sánh đối tượng mới với phần tử thứ \(i\) tốn \(a_i\), là một số nguyên từ 1 đến 9.

Trong trường hợp xấu nhất, tổng chi phí tìm kiếm nhị phân là bao nhiêu? Giả sử bạn dùng chiến lược tối ưu nhằm cực tiểu hóa tổng chi phí trong trường hợp xấu nhất.

Dữ liệu vào

Dòng đầu là \(T\). Mỗi test là chuỗi chữ số liền nhau, chữ số thứ \(i\) là \(a_i\); độ dài chuỗi là \(n\).

Dữ liệu ra

In Case #x: y, với \(y\) là chi phí tệ nhất tối ưu.

Ràng buộc

• \(1\le T\le50\); mọi chữ số từ 1 đến 9.

Phân nhóm

• Nhỏ: \(1\le n\le10^4\).
• Lớn: \(1\le n\le10^6\).

Đ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
111
1111
1111111
1111119

Case #1: 2
Case #2: 3
Case #3: 3
Case #4: 10

Nguồn

Google Code Jam 2015, Chung kết thế giới, bài Costly Binary Search.

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 đang ở trong một kho chứa rất lớn, gồm \(2^{40}\) vị trí lưu trữ xếp thành một vòng tròn.

Một chiếc xe tải có cần cẩu di chuyển dọc theo vòng tròn, lấy lên hoặc đặt xuống các thùng hàng theo một chương trình. Xe có nguồn thùng hàng không giới hạn, nên lúc nào cũng có thể đặt thêm thùng xuống.

Chương trình là một dãy các lệnh:

• b: lùi một vị trí;
• f: tiến một vị trí;
• u: lấy lên một thùng tại vị trí hiện tại;
• d: đặt xuống một thùng tại vị trí hiện tại;
• (: không làm gì;
• ): nếu vị trí hiện tại có nhiều hơn một thùng, quay lại dấu ( khớp gần nhất trong dãy lệnh và tiếp tục chương trình từ đó. Lệnh này không di chuyển xe.

Các lệnh ( và ) luôn đi thành cặp: một ( sẽ có một ) khớp với nó ở phía sau. Chương trình có nhiều nhất hai cặp như vậy; nếu có hai cặp thì chúng không lồng nhau. Vì thế chương trình thuộc đúng một trong các dạng: không có ngoặc; có một cặp; hoặc có một cặp hoàn chỉnh rồi sau đó là một cặp hoàn chỉnh khác. Các test mẫu có ví dụ cho cả ba trường hợp.

Trước khi xe bắt đầu chạy chương trình, mỗi vị trí có đúng một thùng.

Một cách bí ẩn, nếu xe lấy thùng cuối cùng khỏi một vị trí, một xe khác lập tức tới và đặt xuống 256 thùng! Tương tự, nếu xe đặt một thùng khiến vị trí đó có 257 thùng, một xe khác lập tức đi qua và lấy 256 thùng, để lại một thùng. Vì vậy, mỗi vị trí luôn có từ 1 đến 256 thùng.

Hỏi xe thực hiện tổng cộng bao nhiêu lần di chuyển tiến hoặc lùi trước khi đi tới cuối chương trình?

Dữ liệu vào

Dòng đầu là \(T\); mỗi trong \(T\) dòng sau là chương trình dài tối đa 2000.

Dữ liệu ra

In Case #X: Y, với \(Y\) là số lần xe di chuyển.

Ràng buộc

• \(1\le T\le20\), độ dài 1..2000.

Phân nhóm

• Nhỏ: tối đa một cặp ngoặc.
• Lớn: tối đa hai cặp ngoặc.

Đ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
ufffdddbbbdd
dddd(fdbu)fff
dddd(fdddddbu)f(fdddddbu)
bf

Case #1: 6
Case #2: 11
Case #3: 49
Case #4: 2

Nguồn

Google Code Jam 2015, Chung kết thế giới, bài Crane Truck.

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

Edythe là một nữ phù thủy trẻ làm trong bộ phận đảm bảo chất lượng của Merlin, Inc., một nhà máy sản xuất phép thuật. Công việc của cô là kiểm thử các phép thuật do chính Merlin phát minh. Mỗi phép cần lượng chính xác của một số nguyên liệu và biến chúng thành những lượng khác của các nguyên liệu khác. Edythe phải thi triển mỗi phép đúng một lần để xác minh rằng nó hoạt động chính xác.

Cô chỉ có thể thi triển một phép nếu có đủ lượng cần thiết của từng nguyên liệu. Nếu những phép trước đã tạo ra đúng loại nguyên liệu, Edythe bắt buộc phải dùng chúng trước. Nếu vẫn thiếu, cô được phép lấy phần còn thiếu từ kho của Merlin. Ban đầu cô không có nguyên liệu nào; cuối cùng, cô được giữ toàn bộ nguyên liệu dư đã tạo ra mà chưa dùng.

Edythe muốn kiếm càng nhiều lợi nhuận càng tốt trong thời gian học việc. Cô phải thi triển đúng một lần mỗi phép trong \(N\) phép đã cho, nhưng được chọn thứ tự tùy ý. Giả sử mọi phép hoạt động như mong đợi, thứ tự nào giúp cô có tổng giá trị lớn nhất ở cuối?

Ví dụ, kế hoạch kiểm thử có ba phép:

1. Đầu vào: vàng trị giá 7 đô-la. Đầu ra: lưu huỳnh trị giá 5 đô-la.
2. Đầu vào: không có. Đầu ra: vàng trị giá 10 đô-la và lưu huỳnh trị giá 10 đô-la.
3. Đầu vào: vàng trị giá 3 đô-la và lưu huỳnh trị giá 20 đô-la. Đầu ra: cóc trị giá 2 đô-la.

Phép thứ nhất biến vàng thành lưu huỳnh, phép thứ hai triệu hồi vàng và lưu huỳnh từ hư không, còn phép thứ ba biến vàng và lưu huỳnh thành cóc.

Nếu thi triển theo thứ tự 1, 2, 3, trước hết Edythe lấy vàng trị giá 7 đô-la từ kho cho phép #1. Sau hai phép đầu, cô có vàng trị giá 10 đô-la và lưu huỳnh trị giá 15 đô-la. Phép cuối cần vàng trị giá 3 đô-la và lưu huỳnh trị giá 20 đô-la, nên cô phải dùng toàn bộ lưu huỳnh đã tạo, vàng trị giá 3 đô-la và lấy thêm lưu huỳnh trị giá 5 đô-la từ kho. Cuối cùng cô còn nguyên liệu trị giá 9 đô-la: 7 đô-la vàng và 2 đô-la cóc.

Nhưng có kế hoạch tốt hơn. Nếu thi triển theo thứ tự 3, 1, 2, cuối cùng cô có nguyên liệu trị giá 27 đô-la: 10 đô-la vàng, 15 đô-la lưu huỳnh và 2 đô-la cóc.

Dữ liệu vào

Dòng đầu là \(T\). Mỗi test bắt đầu bằng \(N,M\), sau đó \(N\) dòng, mỗi dòng \(M\) số mô tả phép.

Dữ liệu ra

In Case #x: y, giá trị nguyên liệu cuối lớn nhất.

Ràng buộc

• \(1\le T\le100\), \(1\le N\le100\), mỗi số trong \([-100,100]\).

Phân nhóm

• Nhỏ: \(1\le M\le2\).
• Lớn: \(1\le M\le8\).

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

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

Case #1: 1
Case #2: 27

Nguồn

Google Code Jam 2015, Chung kết thế giới, bài Merlin QA.

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

Tôi có một dãy gồm \(N\) chữ số nhị phân. Tôi muốn tìm một đoạn con có đúng tỉ lệ số 0 và số 1 mong muốn; nhưng đoạn như vậy có thể không tồn tại, nên tôi chấp nhận một đoạn chỉ “khá tốt”.

Hãy tìm một đoạn con mà tỉ lệ các chữ số 1 gần phân số \(F\) đã cho nhất có thể. In chỉ số bắt đầu sớm nhất trong số các đoạn con đạt độ gần tối ưu.

Dữ liệu vào

Dòng đầu là \(T\). Mỗi test gồm \(N,F\), rồi chuỗi \(N\) ký tự 0/1.

Dữ liệu ra

In Case #x: y, với \(y\) là chỉ số bắt đầu 0-based nhỏ nhất.

Ràng buộc

• \(1\le T\le100\), \(0\le F\le1\).

Phân nhóm

• Nhỏ: \(1\le N\le1000\).
• Lớn: \(1\le N\le500000\).

Đ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
12 0.666667
001001010111
11 0.400000
10000100011
9 0.000000
111110111
5 1.000000
00000
15 0.333333
000000000011000

Case #1: 5
Case #2: 5
Case #3: 5
Case #4: 0
Case #5: 6

Nguồn

Google Code Jam 2015, Chung kết thế giới, bài Pretty Good Proportion.

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 và người bạn Pinky có kế hoạch thống trị thế giới. Nhưng trước hết, hai người phải vô hiệu hóa một vũ khí bí mật.

Vũ khí nằm trong một mê cung lối đi ngoằn ngoèo (một đồ thị) có một lối vào. Pinky sẽ ở đỉnh chứa vũ khí bí mật để vô hiệu hóa nó. Trong lúc đó, một đội an ninh ở lối vào được báo động và chạy qua đồ thị, cố tới chỗ Pinky kịp lúc để ngăn cậu ấy. Bạn sẽ làm chậm đội an ninh để Pinky có nhiều thời gian nhất có thể.

Đi qua một cạnh của đồ thị tốn một đơn vị thời gian. Ngoài ra, bạn có thể “cản trở” nhiều nhất \(K\) đỉnh. Đi qua một đỉnh bị cản tốn thêm một đơn vị thời gian. Bạn sẽ chọn một tập đỉnh bị cản sao cho làm đội an ninh chậm nhất có thể.

Đội an ninh bắt đầu ở lối vào và cố tới đỉnh vũ khí bí mật. Hỏi họ mất bao lâu để tới đó? Bạn phải quyết định tất cả các vật cản trước khi họ bắt đầu hành trình. Họ biết những đỉnh nào đã bị cản và sẽ chọn đường đi tối ưu dựa trên thông tin đó.

Cản trở chính đỉnh chứa vũ khí không có ích, vì sau khi đã bắt được Pinky thì việc đi qua đỉnh ấy không làm họ chậm thêm nữa. Ngược lại, cản trở lối vào hiển nhiên là một ý hay.

Dữ liệu vào

Dòng đầu là \(T\). Mỗi test gồm \(N,M,K\), rồi \(M\) cạnh u v với \(u<v\), không trùng; các cạnh hai chiều.

Dữ liệu ra

In Case #x: y, thời gian bảo vệ tới đích.

Ràng buộc

• \(1\le T\le100\), \(2\le N\le100\), \(1\le M\le N(N-1)/2\), \(1\le K\le N\); luôn có đường 0 tới \(N-1\).

Phân nhóm

• Nhỏ: với \(K\) đã cho, không thể tăng quá 2 so với đường ngắn nhất không cản.
• Lớn: không thêm ràng buộc.

Đ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
3 2 1
0 1
1 2
3 2 2
0 1
1 2
3 2 3
0 1
1 2
4 4 2
0 1
0 2
1 3
2 3
7 11 3
0 1
0 2
0 3
1 4
1 5
2 4
2 5
3 4
3 5
4 6
5 6

Case #1: 3
Case #2: 4
Case #3: 4
Case #4: 3
Case #5: 5

Nguồn

Google Code Jam 2015, Chung kết thế giới, bài Taking Over The World.

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