Google Code Jam 2012 - Qualification Round

Bạn đang xem một chương trình nơi các Googler (nhân viên của Google) nhảy múa, và sau đó mỗi vũ công được ba giám khảo cho một bộ ba điểm số. Mỗi bộ ba điểm số gồm ba điểm số nguyên từ 0 đến 10. Các giám khảo có tiêu chuẩn rất giống nhau, vì vậy sẽ là bất ngờ nếu một bộ ba điểm số có hai điểm số cách nhau 2 đơn vị. Không có bộ ba điểm số nào chứa các điểm số cách nhau quá 2 đơn vị.

Ví dụ: (8, 8, 😎 và (7, 8, 7) không bất ngờ. (6, 7, 😎 và (6, 8, 😎 là bất ngờ. (7, 6, 9) sẽ không bao giờ xảy ra.

Tổng điểm của một Googler là tổng của ba điểm số trong bộ ba điểm số của Googler đó. Kết quả tốt nhất của một Googler là điểm số lớn nhất trong bộ ba điểm số của Googler đó. Cho biết tổng điểm của mỗi Googler, cũng như số lượng bộ ba điểm số bất ngờ, số lượng tối đa các Googler có thể có kết quả tốt nhất ít nhất là p là bao nhiêu?

Ví dụ, giả sử có 6 Googler và họ có tổng điểm như sau:
29, 20, 8, 18, 18, 21. Bạn nhớ rằng có 2 bộ ba điểm số bất ngờ, và bạn muốn biết có bao nhiêu Googler có thể đạt được kết quả tốt nhất từ 8 trở lên.

Với những tổng điểm đó, và biết rằng hai trong số các bộ ba là bất ngờ, các bộ ba điểm số có thể là:

10 9 10
6 6 8 (*)
2 3 3
6 6 6
6 6 6
6 7 8 (*)

Các trường hợp được đánh dấu (*) là các trường hợp bất ngờ. Điều này cho chúng ta 3 Googler đạt được ít nhất một điểm số từ 8 trở lên. Không có chuỗi bộ ba điểm số nào cho kết quả cao hơn 3, vì vậy câu trả lời là 3.

Dữ liệu vào

Dòng đầu tiên của dữ liệu vào cho biết số lượng bộ thử nghiệm, T. T bộ thử nghiệm tiếp theo. Mỗi bộ thử nghiệm bao gồm một dòng duy nhất chứa các số nguyên cách nhau bởi dấu cách. Số nguyên đầu tiên là N, số lượng Googler, và số nguyên thứ hai là S, số lượng bộ ba điểm số bất ngờ. Số nguyên thứ ba là p, như đã mô tả ở trên. Tiếp theo là N số nguyên \(t_i\): tổng điểm của các Googler.

Dữ liệu ra

Đối với mỗi bộ thử nghiệm, hãy xuất một dòng chứa "Case #x: y", trong đó x là số thứ tự bộ thử nghiệm (bắt đầu từ 1) và y là số lượng tối đa Googler có thể có kết quả tốt nhất lớn hơn hoặc bằng p.

Ràng buộc

• \(1 \le T \le 100\).
• \(0 \le S \le N\).
• \(0 \le p \le 10\).
• \(0 \le t_i \le 30\).
• Ít nhất S giá trị của \(t_i\) sẽ nằm trong khoảng từ 2 đến 28, bao gồm cả hai đầu.

Phân nhóm

• Tập kiểm tra 1 (Visible): \(1 \le N \le 3\).
• Tập kiểm tra 2 (Hidden): \(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.

Ví dụ

4
3 1 5 15 13 11
3 0 8 23 22 21
2 1 1 8 0
6 2 8 29 20 8 18 18 21

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

Nguồn

Google Code Jam 2012, Vòng loại, bài Dancing With the Googlers.

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ống trong một mặt phẳng 2 chiều, và một trong những địa điểm yêu thích của bạn là Phòng Gương (Hall of Mirrors). Phòng Gương là một căn phòng (tất nhiên là 2 chiều) được bố trí trên một lưới ô vuông. Mỗi ô vuông trên lưới chứa một tấm gương hình vuông, không gian trống, hoặc chính bạn. Bạn có chiều rộng bằng 0 và chiều cao bằng 0, và bạn nằm ở chính giữa ô lưới của mình.

Mặc dù rất nhỏ, bạn vẫn có thể nhìn thấy hình ảnh phản chiếu của mình khi nó được phản chiếu chính xác trở lại vị trí của bạn. Ví dụ, hãy xem xét cách bố trí sau, trong đó '#' biểu thị một gương vuông lấp đầy ô của nó, '.' biểu thị không gian trống và chữ cái in hoa 'X' biểu thị bạn đang ở trung tâm của ô đó:

######
#..X.#
#.#..#
#...##
######

Nếu bạn nhìn thẳng lên trên hoặc thẳng sang bên phải, bạn sẽ có thể nhìn thấy hình ảnh phản chiếu của mình.

Thật không may, trong Phòng Gương rất nhiều sương mù, vì vậy bạn không thể nhìn xa hơn \(D\) đơn vị. Giả sử \(D=3\). Nếu bạn nhìn lên trên, hình ảnh phản chiếu của bạn sẽ cách 1 đơn vị (0.5 đến gương và 0.5 quay lại). Nếu bạn nhìn sang phải, hình ảnh phản chiếu của bạn sẽ cách 3 đơn vị (1.5 đến gương và 1.5 quay lại), và bạn sẽ có thể nhìn thấy nó. Nếu bạn nhìn xuống dưới, hình ảnh phản chiếu của bạn sẽ cách 5 đơn vị và bạn sẽ không thể nhìn thấy nó.

Điều quan trọng là phải hiểu cách ánh sáng truyền đi trong Phòng Gương. Ánh sáng truyền theo đường thẳng cho đến khi chạm vào gương. Nếu ánh sáng chạm vào bất kỳ phần nào của gương ngoại trừ góc của nó, nó sẽ được phản xạ theo cách thông thường: nó sẽ bật ra với góc phản xạ bằng góc tới. Mặt khác, nếu ánh sáng chạm vào góc của một tấm gương, tình hình sẽ phức tạp hơn. Các sơ đồ sau đây giải thích các trường hợp:

Trong các trường hợp sau, ánh sáng tiếp cận một góc và được phản xạ, làm thay đổi hướng của nó:

Trong hai trường hợp đầu tiên, ánh sáng tiếp cận hai gương liền kề tại điểm chúng gặp nhau. Ánh sáng được phản xạ theo cùng một cách như thể nó đã chạm vào giữa một tấm gương dài. Trong trường hợp thứ ba, ánh sáng tiếp cận các góc của ba gương liền kề và quay trở lại chính xác hướng mà nó đã đến.

Trong các trường hợp sau, ánh sáng tiếp cận các góc của một hoặc nhiều gương, nhưng không bật lại mà tiếp tục đi theo hướng cũ:

Điều này xảy ra khi ánh sáng đạt đến khoảng cách 0 từ góc của một tấm gương, nhưng sẽ không phải đi qua gương để tiếp tục đi theo cùng một hướng. Theo cách này, một tia sáng có thể đi qua giữa hai gương nằm chéo nhau -- thực tế là đi qua một khoảng không gian có kích thước 0. Thật may là tia sáng cũng có kích thước 0, nên nó vừa khít!

Trong trường hợp cuối cùng, ánh sáng tiếp cận góc của một tấm gương và bị triệt tiêu:

Lưu ý rằng ánh sáng dừng lại khi nó chạm vào bạn, nhưng nó phải chạm vào đúng tâm ô lưới của bạn.

Bạn có thể nhìn thấy bao nhiêu hình ảnh của chính mình?

Dữ liệu vào

Dòng đầu tiên của đầu vào cho biết số lượng bộ test, \(T\). \(T\) bộ test tiếp theo. Mỗi bộ test bắt đầu bằng một dòng chứa ba số nguyên cách nhau bởi dấu cách, \(H\), \(W\) và \(D\). \(H\) dòng tiếp theo, mỗi dòng chứa \(W\) ký tự. Các ký tự tạo thành bản đồ của Phòng Gương cho bộ test đó, như mô tả ở trên.

Dữ liệu ra

Đối với mỗi bộ test, hãy xuất một dòng chứa "Case #x: y", trong đó x là số thứ tự bộ test (bắt đầu từ 1) và y là số lượng hình ảnh phản chiếu của chính bạn mà bạn có thể nhìn thấy.

Ràng buộc

• \(1 \le T \le 100\).
• \(3 \le H, W \le 30\).
• \(1 \le D \le 50\).
• Tất cả các ký tự trong mỗi bản đồ sẽ là '#', '.', hoặc 'X'.
• Chính xác một ký tự trong mỗi bản đồ sẽ là 'X'.
• Hàng đầu tiên, hàng cuối cùng, cột đầu tiên và cột cuối cùng của mỗi bản đồ sẽ hoàn toàn chứa các ký tự '#'.

Phân nhóm

• Test set 1 (Visible): Sẽ không có quá \(2W+2H-4\) ký tự '#'.
• Test set 2 (Hidden): Hạn chế từ Small dataset không áp dụ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ụ

6
3 3 1
###
#X#
###
3 3 2
###
#X#
###
4 3 8
###
#X#
#.#
###
7 7 4
#######
#.....#
#.....#
#..X..#
#....##
#.....#
#######
5 6 3
######
#..X.#
#.#..#
#...##
######
5 6 10
######
#..X.#
#.#..#
#...##
######

Case #1: 4
Case #2: 8
Case #3: 68
Case #4: 0
Case #5: 2
Case #6: 28

Nguồn

Google Code Jam 2012, Vòng loại, bài Hall of Mirrors.

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ó bao giờ cảm thấy thất vọng với truyền hình vì cứ phải xem đi xem lại những thứ giống nhau, được "tái chế" (recycled) liên tục không? Cá nhân tôi thì không quan tâm đến truyền hình lắm, nhưng đôi khi tôi lại cảm thấy như vậy về các con số.

Giả sử một cặp số nguyên dương phân biệt \((n, m)\) được gọi là tái chế nếu bạn có thể nhận được \(m\) bằng cách chuyển một số chữ số từ cuối của \(n\) lên đầu mà không làm thay đổi thứ tự của chúng. Ví dụ, \((12345, 34512)\) là một cặp tái chế vì bạn có thể nhận được \(34512\) bằng cách chuyển \(345\) từ cuối của \(12345\) lên đầu. Lưu ý rằng \(n\) và \(m\) phải có cùng số lượng chữ số để trở thành một cặp tái chế. Cả \(n\) và \(m\) đều không được có chữ số \(0\) ở đầu.

Cho các số nguyên \(A\) và \(B\) có cùng số lượng chữ số và không có chữ số \(0\) ở đầu, có bao nhiêu cặp tái chế phân biệt \((n, m)\) thỏa mãn \(A \le n < m \le B\)?

Dữ liệu vào

Dòng đầu tiên của dữ liệu vào cho biết số lượng bộ test, \(T\). \(T\) bộ test theo sau. Mỗi bộ test gồm một dòng duy nhất chứa các số nguyên \(A\) và \(B\).

Dữ liệu ra

Với mỗi bộ test, hãy xuất một dòng chứa "Case #x: y", trong đó x là số thứ tự bộ test (bắt đầu từ 1), và y là số lượng cặp tái chế \((n, m)\) với \(A \le n < m \le B\).

Ràng buộc

• \(1 \le T \le 50\).
• \(A\) và \(B\) có cùng số lượng chữ số.

Phân nhóm

• Tập kiểm tra 1 (Visible Verdict): \(1 \le A \le B \le 1000\).
• Tập kiểm tra 2 (Hidden Verdict): \(1 \le A \le B \le 2000000\).

Đ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
1 9
10 40
100 500
1111 2222

Case #1: 0
Case #2: 3
Case #3: 156
Case #4: 287

Nguồn

Google Code Jam 2012, Vòng loại, bài Recycled 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.

Tại Google, chúng tôi đã tạo ra một ngôn ngữ tốt nhất có thể, được gọi là Googlerese. Để dịch văn bản sang Googlerese, chúng tôi lấy bất kỳ thông điệp nào và thay thế mỗi chữ cái tiếng Anh bằng một chữ cái tiếng Anh khác. Phép ánh xạ này là song ánh (tương ứng một-một và toàn ánh), có nghĩa là cùng một chữ cái đầu vào luôn được thay thế bằng cùng một chữ cái đầu ra, và các chữ cái đầu vào khác nhau luôn được thay thế bằng các chữ cái đầu ra khác nhau. Một chữ cái có thể được thay thế bằng chính nó. Các khoảng trắng được giữ nguyên.

Ví dụ (và đây là một gợi ý!), thuật toán dịch thuật tuyệt vời của chúng tôi bao gồm ba phép ánh xạ sau: 'a' -> 'y', 'o' -> 'e', và 'z' -> 'q'. Điều này có nghĩa là "a zoo" sẽ trở thành "y qee".

Googlerese dựa trên phép ánh xạ thay thế tốt nhất có thể, và chúng tôi sẽ không bao giờ thay đổi nó. Nó sẽ luôn giống nhau trong mọi trường hợp kiểm thử. Chúng tôi sẽ không tiết lộ phần còn lại của phép ánh xạ vì điều đó sẽ làm bài toán quá dễ, nhưng có một vài ví dụ dưới đây có thể giúp ích cho bạn.

Cho một đoạn văn bản bằng Googlerese, bạn có thể dịch nó ngược lại thành văn bản bình thường không?

Giải quyết bài toán này

Thông thường, các bài toán Google Code Jam có 1 bộ dữ liệu Small và 1 bộ dữ liệu Large. Bài toán này chỉ có 1 bộ dữ liệu Small. Một khi bạn giải được bộ dữ liệu Small, bạn đã hoàn thành bài toán này.

Dữ liệu vào

Dòng đầu tiên của dữ liệu vào cho biết số lượng bộ thử nghiệm, \(T\). Tiếp theo là \(T\) bộ thử nghiệm, mỗi bộ trên một dòng.

Mỗi dòng bao gồm một chuỗi \(G\) bằng Googlerese, được tạo thành từ một hoặc nhiều từ chứa các chữ cái 'a' - 'z'. Sẽ có chính xác một ký tự khoảng trắng (' ') giữa các từ liên tiếp và không có khoảng trắng ở đầu hoặc cuối mỗi dòng.

Dữ liệu ra

Với mỗi bộ thử nghiệm, hãy xuất ra một dòng chứa "Case #\(X\): \(S\)" trong đó \(X\) là số thứ tự bộ thử nghiệm và \(S\) là chuỗi mà khi chuyển sang Googlerese sẽ trở thành \(G\).

Ràng buộc

Chỉ có một tập thử nghiệm với kết quả hiển thị công khai.
\(1 \le T \le 30\).
\(G\) chứa tối đa 100 ký tự.
Không có văn bản nào được đảm bảo là tiếng Anh chuẩn.

Phân nhóm

Bài này chỉ có một tập kiểm thử với kết quả hiển thị công khai.

Đ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
ejp mysljylc kd kxveddknmc re jsicpdrysi
rbcpc ypc rtcsra dkh wyfrepkym veddknkmkrkcd
de kr kd eoya kw aej tysr re ujdr lkgc jv

Case #1: our language is impossible to understand
Case #2: there are twenty six factorial possibilities
Case #3: so it is okay if you want to just give up

Nguồn

Google Code Jam 2012, Vòng loại, bài Speaking in Tongues.

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