Google Code Jam 2016 - World Finals

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 2016 - Family Hotel 30 5.0s 1G
2 Google Code Jam 2016 - Gallery of Pillars 40 7.5s 1G
3 Google Code Jam 2016 - Integeregex 30 1.0s 1G
4 Google Code Jam 2016 - Map Reduce 50 3.0s 1G
5 Google Code Jam 2016 - Radioactive Islands 50 20.0s 1G

1. Google Code Jam 2016 - Family Hotel

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

Bạn điều hành một khách sạn có \(N\) phòng nằm dọc theo một hành lang dài, được đánh số từ 1 đến \(N\). Khách của bạn là những đại gia đình, và mỗi gia đình khi đến đều yêu cầu đúng hai phòng kề nhau. Hai phòng được coi là kề nhau nếu số phòng chênh nhau đúng 1.

Đầu ngày hôm nay, khách sạn hoàn toàn trống. Bạn dùng chiến lược đơn giản sau để xếp phòng. Mỗi khi một gia đình đến, bạn xét tất cả các cặp phòng kề nhau mà cả hai phòng đều còn trống, chọn ngẫu nhiên đều một cặp trong số đó, rồi giao hai phòng ấy cho gia đình. Các gia đình liên tục đến, mỗi lần một gia đình; nhưng ngay khi không còn cặp phòng kề nhau nào cùng trống, bạn bật biển HẾT PHÒNG và không giao thêm phòng nữa.

Với một số phòng cụ thể, xác suất để phòng đó đã có người ở vào lúc bạn bật biển HẾT PHÒNG là bao nhiêu?

Dữ liệu vào

Dòng đầu chứa số bộ test \(T\). Tiếp theo là \(T\) dòng; mỗi dòng chứa hai số: số phòng \(N\) và số hiệu phòng \(K\) mà ta quan tâm.

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), còn y là xác suất cần tìm tính theo modulo \(10^9+7\), được định nghĩa chính xác như sau.

Biểu diễn xác suất phòng \(K\) có người ở dưới dạng phân số tối giản p/q. Khi đó y phải thỏa mãn

\[yq \equiv p \pmod {10^9+7},\]

và nằm trong đoạn từ 0 đến \(10^9+6\), kể cả hai đầu. Có thể chứng minh rằng dưới các ràng buộc của bài, y luôn tồn tại và được xác định duy nhất.

Ràng buộc

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

Phân nhóm

  • Test Set 1 (Hiển thị): \(2 \le N \le 10^4\).
  • Test Set 2 (Ẩn): \(2 \le N \le 10^7\).

Đ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/30 33,33%
Test Set 2 20/30 66,67%

Ví dụ

Ví dụ 1

Input 
4
3 1
3 2
4 1
4 2
Output 
Case #1: 500000004
Case #2: 1
Case #3: 666666672
Case #4: 1
Giải thích

Trong bộ test mẫu số 3, có bốn phòng và ta cần xác suất phòng đầu tiên có người ở. Khi gia đình đầu tiên đến, có ba khả năng, mỗi khả năng có xác suất \(1/3\): họ nhận phòng 1+2, 2+3 hoặc 3+4. Ở khả năng thứ nhất, phòng đầu tiên đã có người và sẽ tiếp tục có người. Ở khả năng thứ hai, phòng đầu tiên còn trống nhưng không thể đón thêm gia đình nào, nên nó sẽ tiếp tục trống. Cuối cùng, ở khả năng thứ ba, gia đình tiếp theo chắc chắn nhận phòng 1+2, nên phòng đầu tiên sẽ có người. Vì vậy xác suất là \(2/3\), và đáp án là 666666672 vì \((666666672\times3)\bmod 1000000007=2\bmod 1000000007\).

Xác suất trong bộ test mẫu số 1 là \(1/2\); trong các bộ test mẫu số 2 và 4, xác suất là 1.

Nguồn

Google Code Jam 2016, Chung kết thế giới, bài Family Hotel.

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 2016 - Gallery of Pillars

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

Người bạn Cody-Jamal đang thực hiện tác phẩm sắp đặt nghệ thuật mới mang tên “Gallery of Pillars”. Tác phẩm sẽ được trưng bày trong một phòng triển lãm hình vuông kích thước \(N\) mét × \(N\) mét. Phòng được chia thành \(N^2\) ô vuông kích thước 1 mét × 1 mét, tạo thành ma trận \(N\times N\). Tâm chính xác của ô ở góc tây nam được gọi là điểm quan sát; người xem tác phẩm sẽ đứng tại đó. Mỗi ô còn lại chứa một cột trụ hình trụ. Mọi cột trụ có hai đáy tròn bán kính \(R\): một đáy nằm trên sàn tại tâm ô tương ứng, đáy còn lại chạm trần phòng. Người quan sát sẽ đứng tại điểm quan sát, ngắm \(N^2-1\) cột trụ và trầm trồ.

Cody-Jamal hiện đang tìm địa điểm để xem có thể chọn \(N\) lớn đến đâu. Anh cũng chưa quyết định vật liệu làm cột: có thể là bê tông hoặc ống nano carbon, nên bán kính đáy \(R\) có thể thay đổi từ 1 micromet đến gần nửa mét. Lưu ý rằng bán kính nửa mét sẽ khiến các cột kề nhau chạm nhau.

Là một nhà toán học được đào tạo bài bản, bạn nhanh chóng nhận ra có thể tồn tại những cột không thể nhìn thấy từ điểm quan sát. Cody-Jamal nhờ bạn xác định số cột nhìn thấy được với các tổ hợp \(N\) và \(R\) khác nhau. Một cách hình thức, một cột được nhìn thấy khi và chỉ khi tồn tại một đoạn thẳng từ tâm ô góc tây nam (điểm quan sát) đến một điểm bất kỳ trên biên cột đó mà không chạm hay cắt bất kỳ cột nào khác.

Dữ liệu vào

Dòng đầu chứa số bộ test \(T\). Tiếp theo là \(T\) dòng; mỗi dòng mô tả một bộ test bằng hai số nguyên \(N\) và \(R\). \(N\) là số ô vuông cạnh 1 mét theo mỗi chiều của phòng, còn \(R\) là bán kính mỗi cột tính bằng micromet. Do đó, bán kính cột tính bằng mét là \(R/10^6\).

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), còn y là số cột trong tác phẩm nhìn thấy được từ điểm quan sát.

Ràng buộc

  • \(1\le T\le100\).
  • \(1\le R<10^6/2\).

Phân nhóm

  • Test Set 1 (Hiển thị): \(2\le N\le300\).
  • Test Set 2 (Ẩn): \(2\le N\le10^9\).

Đ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/40 25%
Test Set 2 30/40 75%

Ví dụ

Ví dụ 1

Input 
4
4 100000
4 300000
3 300000
100 499999
Output 
Case #1: 9
Case #2: 7
Case #3: 5
Case #4: 3
Giải thích

Hai hình dưới minh họa hai bộ test mẫu đầu tiên (không theo đúng tỉ lệ). Người quan sát nằm ở tâm hình tròn đen. Các hình tròn khác là cột trụ; cột nhìn thấy được tô xám, cột không nhìn thấy được tô đỏ. Các đường chấm xanh biểu thị một số đường ngắm không bị chắn; các đường chấm đỏ biểu thị đường ngắm bị chắn (chuyển sang xám tại điểm đầu tiên bị chắn).

https://cdn.lqdoj.edu.vn/media/pagedown-uploads/pd_1_c1e5e233.png

https://cdn.lqdoj.edu.vn/media/pagedown-uploads/pd_1_7fb52566.png

Nguồn

Google Code Jam 2016, Chung kết thế giới, bài Gallery of Pillars.

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 2016 - Integeregex

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

Trong bài này, một biểu thức chính quy hợp lệ thuộc một trong các dạng sau. Trong các mô tả dưới đây, \(E_1,E_2,\ldots\) biểu thị các biểu thức chính quy hợp lệ (không nhất thiết khác nhau).

  • Một chữ số thập phân, tức một trong 0 1 2 3 4 5 6 7 8 9.
  • Phép nối: \(E_1E_2\).
  • Phép tuyển: (E1|E2|...|EN) với ít nhất hai biểu thức. Cặp ngoặc ngoài là bắt buộc.
  • Phép lặp: (E1)*. Cặp ngoặc ngoài là bắt buộc.

Ví dụ, 7, 23, (7)*, (45)*, (1|2|3), ((2)*|3), (1|2|3) và ((0|1))* là các biểu thức hợp lệ. Các biểu thức (7), 4|5, 4*, (1|) và (0|1)* không hợp lệ.

Ta nói biểu thức \(E\) khớp với chuỗi chữ số \(D\) khi và chỉ khi ít nhất một điều sau đúng:

  • \(E=D\).
  • \(E=E_1E_2\) và tồn tại \(D_1,D_2\) sao cho \(D=D_1D_2\), đồng thời \(E_i\) khớp với \(D_i\).
  • \(E=(E_1|E_2|\ldots|E_N)\) và ít nhất một \(E_i\) khớp với \(D\).
  • \(E=(E_1)*\) và tồn tại \(D_1,D_2,\ldots,D_N\) với một số nguyên không âm \(N\), sao cho \(D=D_1D_2\ldots D_N\) và \(E_1\) khớp với từng \(D_i\). Đặc biệt, (E1)* khớp với chuỗi rỗng.

Ví dụ, biểu thức ((1|2))*3 khớp với 3, 13, 123, 2221123 cùng nhiều chuỗi khác. Tuy nhiên, nó không khớp với 1234, 3123, 12, 33 cùng nhiều chuỗi khác.

Cho một biểu thức chính quy hợp lệ \(R\), có bao nhiêu số nguyên trong đoạn từ \(A\) đến \(B\), kể cả hai đầu, mà biểu diễn thập phân không có số 0 ở đầu của chúng khớp với \(R\)?

Dữ liệu vào

Dòng đầu chứa số bộ test \(T\). Mỗi bộ test gồm hai dòng. Dòng đầu chứa hai số nguyên dương \(A,B\), là hai đầu mút kể cả hai đầu của đoạn số nguyên cần xét. Dòng thứ hai chứa chuỗi \(R\) chỉ gồm các ký tự trong tập 0123456789()|*; \(R\) được bảo đảm là một biểu thức chính quy hợp lệ theo định nghĩa 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), còn y là số số nguyên trong đoạn \([A,B]\) được biểu thức chính quy \(R\) khớp.

Ràng buộc

  • \(1\le T\le100\).
  • \(1\le A\le B\le10^{18}\).
  • \(1\le\operatorname{length}(R)\le30\).

Phân nhóm

  • Test Set 1 (Hiển thị): \(R\) không chứa ký tự |.
  • Test Set 2 (Ẩn): Không có ràng buộc bổ sung.

Đ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 15/30 50%
Test Set 2 15/30 50%

Ví dụ

Ví dụ 1

Input 
8
1 1000
(0)*1(0)*
379009 379009
379009
1 10000
(12)*(34)*
4 5
45
1 100
((0|1))*
1 50
(01|23|45|67|23)
1 1000000000000000000
((0|1|2|3|4|5|6|7|8|9))*
1 1000
1(56|(((7|8))*9)*)
Output 
Case #1: 4
Case #2: 1
Case #3: 5
Case #4: 0
Case #5: 4
Case #6: 2
Case #7: 1000000000000000000
Case #8: 6
Giải thích

Các bộ test mẫu từ 5 đến 8 không xuất hiện trong Test Set nhỏ.

Trong bộ test 1, các số khớp trong đoạn là 1, 10, 100 và 1000. Trong bộ test 2, số khớp là 379009. Trong bộ test 3, các số khớp là 12, 34, 1212, 1234 và 3434. Bộ test 4 không có số nào khớp. Trong bộ test 5, các số khớp là 1, 10, 11 và 100. Trong bộ test 6, các số khớp là 23 và 45. Trong bộ test 7, có thể tạo mọi số trong đoạn. Trong bộ test 8, các số khớp là 1, 19, 156, 179, 189 và 199.

Nguồn

Google Code Jam 2016, Chung kết thế giới, bài Integeregex.

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 2016 - Map Reduce

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

Ben, một nhà thiết kế trò chơi điện tử tài ba, đang thiết kế các bản đồ cho trò chơi di động thực tế tăng cường sắp ra mắt. Gần đây anh tạo một bản đồ biểu diễn bằng ma trận \(R\) hàng và \(C\) cột. Bản đồ gồm các ký tự . biểu thị ô trống, các ký tự # biểu thị tường không thể đi qua, đúng một vị trí bắt đầu S và đúng một vị trí kết thúc F. Ví dụ, bản đồ có thể như sau:

#############
#S..#..##...#
###.##..#.#F#
#...##.##.###
#.#.........#
#############

Trong trò chơi của Ben, một đường đi là một dãy bước (lên, xuống, trái hoặc phải) để đi từ ô này sang ô khác mà không đi xuyên qua tường.

Ben coi một bản đồ là tốt nếu có các tính chất sau:

  • Có đường đi giữa mọi cặp ô trống (bao gồm vị trí bắt đầu và kết thúc).
  • Để bảo toàn độ vững của cấu trúc, các tường phải tiếp xúc bằng cạnh chứ không chỉ bằng góc. Trong mọi vùng \(2\times2\) của bản đồ, nếu vùng chứa đúng hai ô tường thì hai tường đó phải cùng hàng hoặc cùng cột. Nói cách khác, không có vùng \(2\times2\) nào có tường theo một trong hai cấu hình:
#.   .#
.#   #.
  • Biên bản đồ chỉ gồm tường không thể đi qua. Một ô thuộc biên nếu nó nằm ở hàng trên cùng/dưới cùng hoặc cột trái cùng/phải cùng.

Độ dài đường đi ngắn nhất là số bước ít nhất cần để đi từ vị trí bắt đầu đến vị trí kết thúc. Chẳng hạn, đường đi ngắn nhất trong ví dụ trên dài 17 bước.

Là một người làm bản đồ thông minh, Ben nhận ra bản đồ của mình quá khó đối với bạn bè. Anh muốn giảm độ khó bằng cách dỡ bỏ một số tường. Cụ thể, anh muốn biết có thể dỡ bỏ không hoặc nhiều tường sao cho đường đi ngắn nhất từ đầu đến cuối dài đúng \(D\) bước và bản đồ thu được vẫn tốt hay không. Chỉ tìm được một đường đi dài \(D\) là chưa đủ; \(D\) phải là số bước của đường đi ngắn nhất.

Ví dụ, nếu \(D=15\), ta có thể dỡ bức tường ngay bên dưới vị trí kết thúc để có một lời giải tốt:

#############
#S..#..##...#
###.##..#.#F#
#...##.##.#.#
#.#.........#
#############

Không có lời giải nếu \(D=5\).

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 ba số nguyên cách nhau bởi dấu cách \(R,C,D\): số hàng, số cột của bản đồ và số bước mong muốn của đường đi ngắn nhất sau khi có thể dỡ tường. Tiếp theo là \(R\) dòng, mỗi dòng gồm \(C\) ký tự thuộc . , #, S, F, biểu diễn bản đồ của Ben.

Bản đồ được bảo đảm là tốt theo định nghĩa trong đề.

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), còn y là POSSIBLE hoặc IMPOSSIBLE tùy theo có thể làm đường đi ngắn nhất bằng \(D\) bằng cách dỡ một số tường mà bản đồ vẫn tốt hay không. Nếu có thể, in thêm \(R\) dòng, mỗi dòng \(C\) ký tự, biểu diễn bản đồ mới. Trong đầu ra, thay các ký tự # của những tường đã dỡ (nếu có) bằng ..

Nếu có nhiều lời giải, bạn có thể in bất kỳ lời giải nào.

Ràng buộc

  • \(1\le T\le100\).
  • Mỗi bộ test chứa đúng một S và đúng một F.
  • Tệp đầu vào có kích thước không quá 3 MB.

Phân nhóm

  • Test Set 1 (Hiển thị): \(3\le R\le40\), \(3\le C\le40\), \(1\le D\le1600\).
  • Test Set 2 (Ẩn): \(3\le R\le1000\), \(3\le C\le1000\), \(1\le D\le10^6\).

Lưu ý

Đầu ra của Test Set lớn vượt giới hạn kích thước đầu ra thông thường của Code Jam, nhưng bạn vẫn có thể tải lên như bình thườ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.

Phân nhóm Điểm Google Code Jam Tỷ lệ điểm của bài
Test Set 1 20/50 40%
Test Set 2 30/50 60%

Ví dụ

Ví dụ 1

Input 
3
6 13 15
#############
#S..#..##...#
###.##..#.#F#
#...##.##.###
#.#.........#
#############
5 8 3
########
#S.....#
####...#
#F.....#
########
4 10 11
##########
#S#...#.F#
#...#...##
##########
Output 
Case #1: POSSIBLE
#############
#S..#..##...#
###.##..#.#F#
#...##.##.#.#
#.#.........#
#############
Case #2: IMPOSSIBLE
Case #3: POSSIBLE
##########
#S#...#.F#
#...#...##
##########
Giải thích

Đầu ra mẫu hiển thị một bộ đáp án cho các bộ test mẫu; có thể tồn tại những đáp án khác.

Bộ test 1 chính là ví dụ trong đề. Trong bộ test 2, chẳng hạn có thể dỡ tường để đường đi ngắn nhất dài 2 hoặc 4, nhưng không có cách làm nó dài đúng 3. Trong bộ test 3, đường đi ngắn nhất ban đầu đã dài 11 bước nên không cần giảm độ khó.

Nguồn

Google Code Jam 2016, Chung kết thế giới, bài Map Reduce.

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

5. Google Code Jam 2016 - Radioactive Islands

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

Bạn lái một chiếc thuyền từ tọa độ \((-10,A)\) đến tọa độ \((10,B)\). Tọa độ được đo bằng kilômét và thuyền di chuyển với vận tốc không đổi 1 kilômét mỗi giờ. Bạn hoàn toàn điều khiển được lộ trình của thuyền. Ta mô hình hóa thuyền như một điểm.

Trong khu vực có \(N\) hòn đảo; mỗi đảo cũng được mô hình hóa như một điểm. Đảo thứ \(i\) ở tọa độ \((0,C_i)\).

Khu vực bị nhiễm phóng xạ và bạn liên tục nhận 1 microsievert bức xạ mỗi giờ từ môi trường chung, bất kể đang ở đâu. Hơn nữa, chính các đảo cũng có phóng xạ: bạn liên tục nhận thêm bức xạ từ đảo thứ \(i\) với tốc độ \(D_i^{-2}\) microsievert mỗi giờ, trong đó \(D_i\) là khoảng cách hiện tại tính bằng kilômét từ bạn đến đảo thứ \(i\). Một cách hình thức, gọi \(D_i(t)\) là khoảng cách đến đảo thứ \(i\) theo thời gian \(t\), và \(X\) là tổng thời gian hành trình; tổng bức xạ nhận từ đảo thứ \(i\) là tích phân xác định \(\int_0^X D_i(t)^{-2}\,dt\). Bạn có thể đến gần đảo tùy ý miễn không trùng đúng tọa độ của nó.

Hãy tìm tổng liều bức xạ nhỏ nhất có thể nhận nếu chọn lộ trình tối ưu.

Dữ liệu vào

Dòng đầu chứa số bộ test \(T\). Mỗi bộ test gồm hai dòng. Dòng đầu chứa ba giá trị: số nguyên \(N\) và hai số thực \(A,B\) như mô tả trên. Dòng thứ hai chứa \(N\) số thực \(C_i\); số thứ \(i\) là tung độ của đảo thứ \(i\).

Mọi số thực đều được cho với đúng hai chữ số sau dấu thập phâ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), còn y là liều bức xạ nhỏ nhất tính bằng microsievert nhận được trong hành trình.

y được coi là đúng nếu sai số tuyệt đối hoặc tương đối không quá \(10^{-3}\) so với đáp án chính xác.

Ràng buộc

  • \(-10.00\le A\le10.00\).
  • \(-10.00\le B\le10.00\).
  • \(-10.00\le C_i\le10.00\) với mọi \(i\).
  • \(C_i\ne C_j\) với mọi \(i\ne j\).

Phân nhóm

  • Test Set 1 (Hiển thị): \(T\le20\), \(N=1\).
  • Test Set 2 (Ẩn): \(T\le50\), \(1\le N\le2\).

Đ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 25/50 50%
Test Set 2 25/50 50%

Ví dụ

Ví dụ 1

Input 
2
1 1.00 -2.00
0.00
2 0.00 0.00
3.00 -3.00
Output 
Case #1: 21.806
Case #2: 21.706
Giải thích

Hình sau biểu diễn đường đi tối ưu cho bộ test mẫu số 1. Hòn đảo được phóng to để dễ nhìn, nhưng hãy nhớ phải coi nó là một điểm.

https://cdn.lqdoj.edu.vn/media/pagedown-uploads/pd_1_4df0bb23.png

Nguồn

Google Code Jam 2016, Chung kết thế giới, bài Radioactive Islands.

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