Google Code Jam 2012 - Round 2

Lớp học thể dục nhịp điệu bắt đầu. Huấn luyện viên nói: "Các em hãy đứng trên thảm tập sao cho mỗi người đều có đủ không gian để vung tay thoải mái mà không va trúng bất kỳ ai khác." Mọi người bắt đầu di chuyển trên thảm, cố gắng tìm vị trí thích hợp. Nhiều phút trôi qua, cuối cùng huấn luyện viên quá khó chịu nên đã nhờ bạn viết một chương trình để sắp xếp vị trí cho tất cả mọi người, hy vọng việc này sẽ nhanh hơn là để họ tự loay hoay!

Bạn được cho kích thước (chiều rộng và chiều dài) của tấm thảm nơi lớp học diễn ra. Đối với mỗi học sinh, có một khu vực hình tròn mà cô ấy cần cho riêng mình, với bán kính bằng tầm với của cánh tay. Các hình tròn này không được giao nhau, mặc dù chúng có thể tiếp xúc; và tâm của mỗi hình tròn (nơi học sinh đứng) phải nằm trên thảm. Lưu ý rằng cánh tay có thể vươn ra ngoài phạm vi tấm thảm. Bạn biết rằng có rất nhiều không gian trên thảm — diện tích của thảm ít nhất gấp năm lần tổng diện tích các hình tròn cần thiết cho tất cả mọi người trong lớp. Sẽ luôn có cách để tất cả mọi người đứng vào vị trí như yêu cầu.

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 gồm hai dòng. Dòng đầu tiên chứa ba số nguyên: \(N\), \(W\) và \(L\), lần lượt biểu thị số lượng học sinh, chiều rộng của thảm và chiều dài của thảm. Dòng thứ hai chứa \(N\) số nguyên \(r_i\), biểu thị tầm với cánh tay của học sinh thứ \(i\).

Dữ liệu ra

Đối với mỗi bộ thử nghiệm, hãy xuất một dòng chứa "Case #n: y", trong đó n là số thứ tự bộ thử nghiệm (bắt đầu từ 1) và y là một chuỗi chứa \(2N\) số, mỗi số có thể là số nguyên hoặc số thực: \(x_1, y_1, x_2, y_2\), v.v., trong đó cặp (\(x_i, y_i\)) là vị trí học sinh thứ \(i\) nên đứng (với \(0 \le x_i \le W\) và \(0 \le y_i \le L\)).

Vì có thể có nhiều cách để sắp xếp các học sinh trên thảm, bạn có thể xuất bất kỳ cách sắp xếp chính xác nào; nhưng hãy nhớ rằng bạn không được gửi tệp đầu ra có kích thước quá 200kB.

Ràng buộc

• \(1 \le T \le 50\).
• \(1 \le W, L \le 10^9\).
• \(1 \le r_i \le 10^5\).
• Diện tích thảm ít nhất gấp 5 lần tổng diện tích các hình tròn: \(5 \cdot \pi \cdot (r_1^2 + \dots + r_N^2) \le W \cdot L\).

Phân nhóm

• Tập thử nghiệm 1 (Visible): \(1 \le N \le 10\).
• Tập thử nghiệm 2 (Hidden): \(1 \le N \le 10^3\). Tổng số hình tròn trong tất cả các bộ thử nghiệm \(\le 6000\).

Đ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
2 6 6
1 1
3 320 2
4 3 2

Case #1: 0.0 0.0 6.0 6.0
Case #2: 0.0 0.0 7.0 0.0 12.0 0.0

Nguồn

Google Code Jam 2012, Vòng 2, bài Aerobics.

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 ở trên vách núi Everest. Bạn cần tìm nơi trú ẩn trước khi bị đóng băng, và trời thì tối om! Bạn phải làm gì đây?

Tin tốt là bạn đã ghi nhớ sơ đồ của ngọn núi. Nó là một lưới với một số ô không thể đi qua và các ô khác chứa các hang động nơi bạn có thể nghỉ ngơi qua đêm. Tin xấu là bạn không biết mình đang ở đâu, và vách núi quá dốc để leo lên. Tất cả những gì bạn có thể làm là di chuyển sang trái, sang phải hoặc xuống dưới.

Dưới đây là một ví dụ về sơ đồ, với . đại diện cho một ô có thể đi qua, # đại diện cho một ô không thể đi qua, và các con số đại diện cho các hang động.

######
##...#
#..#.#
#...##
#0#..#
####1#
######

Vì trời rất tối, bạn sẽ di chuyển bằng cách tuân theo một kế hoạch, đó là một chuỗi các chỉ dẫn, mỗi chỉ dẫn yêu cầu bạn di chuyển một ô sang trái, sang phải hoặc xuống dưới. Nếu một chỉ dẫn đưa bạn đến một ô có thể đi qua hoặc một hang động, bạn sẽ thực hiện nó. Nếu nó đưa bạn đến một ô không thể đi qua, bạn sẽ phải bỏ qua nó. Dù thế nào đi nữa, bạn vẫn sẽ tiếp tục bước tiếp theo, và cứ thế, cho đến khi bạn thực hiện hết toàn bộ kế hoạch.

Để hỗ trợ việc đi xuống, bạn muốn tìm ra hai điều cho mỗi hang động C:

• Những ô nào có thể đi tới được C? Chúng ta sẽ ký hiệu tập hợp các ô này là \(S_C\), và số lượng của chúng là \(n_C\).
• Có tồn tại một kế hoạch duy nhất mà nếu thực hiện từ bất kỳ ô nào trong \(S_C\), bạn sẽ kết thúc tại hang động C không? Nếu có, chúng ta nói hang động đó là may mắn (lucky).

Lưu ý rằng bạn có thể đi ngang qua nhiều hang động trong khi thực hiện một kế hoạch. Điều quan trọng duy nhất là ô bạn kết thúc sau khi thực hiện tất cả các bước, chứ không phải các hang động bạn ghé thăm dọc đường.

Ví dụ, trong sơ đồ trên, hang động 0 là may mắn. Có 9 ô mà từ đó có thể đến được nó (bao gồm cả chính nó), và kế hoạch "sang trái-sang trái-xuống-xuống-sang trái-xuống" sẽ giúp bạn kết thúc tại hang động từ bất kỳ ô nào trong số đó.

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, bắt đầu bằng một dòng chứa các số nguyên R và C, đại diện cho số hàng và số cột của sơ đồ ngọn núi.

Tiếp theo là R dòng, mỗi dòng chứa C ký tự, mô tả sơ đồ ngọn núi. Như trong ví dụ trên, ký tự # đại diện cho ô không thể đi qua, ký tự . đại diện cho ô có thể đi qua, và các chữ số '0'-'9' đại diện cho các hang động (cũng là các ô có thể đi qua).

Dữ liệu ra

Với mỗi bộ thử nghiệm, trước tiên hãy in ra một dòng chứa "Case #x:", trong đó x là số thứ tự bộ thử nghiệm (bắt đầu từ 1). Đối với mỗi hang động C, bắt đầu từ 0 và đếm ngược lên, hãy viết một dòng "C: \(n_C\) \(L_C\)". Ở đây, C là số hiệu hang động, \(n_C\) là số lượng ô bạn có thể đi tới hang động đó, và \(L_C\) là chuỗi "Lucky" hoặc "Unlucky", như đã định nghĩa ở trên.

Ràng buộc

• Sẽ có từ 1 đến 10 hang động (bao gồm cả 1 và 10).
• Nếu có d hang động, chúng sẽ được gắn nhãn bằng các chữ số {0, 1, ..., d - 1}, và không có hai hang động nào có cùng nhãn.
• Tất cả các ô trên biên của sơ đồ ngọn núi đều không thể đi qua.
• 1 ≤ T ≤ 20.

Phân nhóm

• Test set 1 (Visible): 3 ≤ R, C ≤ 10.
• Test set 2 (Hidden): 3 ≤ R, C ≤ 60.

Đ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
7 5
#####
##0##
##1.#
##2##
#3..#
#.#.#
#####
7 6
######
##...#
#..#.#
#...##
#0#..#
####1#
######

Case #1:
0: 1 Lucky
1: 3 Lucky
2: 4 Unlucky
3: 7 Lucky
Case #2:
0: 9 Lucky
1: 11 Unlucky

Nguồn

Google Code Jam 2012, Vòng 2, bài Descending in the Dark.

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 đi bộ qua một dãy núi. Trong dãy núi này, cứ mỗi km lại có một đỉnh núi và không có đỉnh nào ở giữa. Tại mỗi đỉnh núi, bạn nằm xuống nghỉ ngơi, nhìn về phía trước và thấy một trong những đỉnh phía trước là đỉnh cao nhất. Đỉnh có vẻ cao nhất đó có thể không thực sự là đỉnh cao nhất vì hai lý do: có thể có một đỉnh cao hơn bị che khuất bởi một đỉnh khác gần bạn hơn và thấp hơn; hoặc bạn có thể đang nhìn xuống, và một đỉnh ở xa có thể trông cao hơn một đỉnh ở gần.

Chính xác hơn, khi chúng ta nói rằng đỉnh \(B\) trông có vẻ cao nhất từ đỉnh \(A\), điều đó có nghĩa là:

• \(B\) nằm xa hơn \(A\) trên đường đi.
• Tất cả các đỉnh nằm giữa \(A\) và \(B\) đều nằm dưới đường thẳng nối hai đỉnh \(A\) và \(B\).
• Tất cả các đỉnh xa hơn \(B\) đều nằm dưới hoặc nằm trên đường thẳng này.

Bạn không biết chiều cao của mỗi đỉnh, nhưng bạn có trí nhớ rất tốt; bạn đã đi qua tất cả các đỉnh và nhớ được đỉnh nào trông có vẻ cao nhất từ mỗi đỉnh đó. Bạn muốn tìm một bộ chiều cao cho các đỉnh sao cho phù hợp với thông tin đó. Lưu ý rằng bạn đã nằm xuống khi nhìn, vì vậy chúng ta giả định bạn luôn nhìn từ mức mặt đất trên mỗi đỉnh.

Trong ví dụ này, đỉnh thứ tư trông có vẻ cao nhất từ đỉnh thứ nhất và thứ ba. Khi bạn nằm trên đỉnh thứ hai, bạn không thể nhìn thấy đỉnh thứ tư; đỉnh thứ ba đã che khuất nó và trông có vẻ cao nhất.

Dữ liệu vào

Dòng đầu tiên của đầ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ộ gồm hai dòng:

• Dòng đầu tiên chứa một số \(N\), số lượng đỉnh núi. Bạn bắt đầu chuyến đi tại đỉnh \(1\) và đi tiếp đến đỉnh \(N\).
• Dòng tiếp theo chứa \(N-1\) số \(x_i\). Số thứ \(i\) biểu thị chỉ số của đỉnh trông có vẻ cao nhất từ đỉnh \(i\) (lưu ý rằng đỉnh \(N\) là đỉnh cuối cùng, nên không có đỉnh nào khác để nhìn từ đó).

Dữ liệu ra

Với mỗi bộ thử nghiệm, xuất một dòng chứa "Case #n: \(y_1\) \(y_2\) ... \(y_N\)", trong đó \(n\) là số thứ tự bộ thử nghiệm (bắt đầu từ 1) và \(y_i\) là chiều cao của đỉnh thứ \(i\). Bạn có thể xuất bất kỳ giải pháp nào phù hợp với dữ liệu đầu vào, miễn là tất cả các chiều cao bạn xuất ra phải là số nguyên từ \(0\) đến \(10^9\), bao gồm cả hai đầu mút.

Nếu không có giải pháp nào khả thi, hãy xuất "Case #n: Impossible".

Ràng buộc

• \(1 \le T \le 30\).
• \(i < x_i \le N\).

Phân nhóm

• Test set 1 (Visible): \(2 \le N \le 10\).
• Test set 2 (Hidden): \(2 \le N \le 2000\).

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

Case #1: 10 10 10 10 10 2
Case #2: 10 20 40 80
Case #3: Impossible
Case #4: 5 3 6 8

Nguồn

Google Code Jam 2012, Vòng 2, bài Mountain View.

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 đứng trên một gờ đá trong rừng nhiệt đới, và tình yêu duy nhất của đời bạn đang đứng trên một gờ đá tương tự ở phía bên kia của một đầm lầy đầy rắn, cá sấu và nhiều sinh vật khó chịu khác. May mắn thay, có một số dây leo treo từ vòm lá của rừng trên đầm lầy, và thậm chí may mắn hơn, bằng cách nào đó bạn đã nắm được sợi dây đầu tiên trong số này (xem các hình minh họa bên dưới). Vòm lá của rừng ở độ cao không đổi, và cả hai gờ đá đều ở cùng độ cao với vòm lá. Các dây leo chỉ đơn giản là những đoạn dây treo từ vòm lá tại các điểm nhất định, với độ dài khác nhau.

Nếu bạn là một anh hùng hư cấu, bạn sẽ chỉ việc đu dây một cách cuồng nhiệt và hò hét, tại một thời điểm nào đó buông sợi dây đang giữ, bay trong không trung một lúc, bắt lấy một sợi dây khác, đu tiếp, và sau vài lần lặp lại, bạn sẽ ôm được tình yêu duy nhất của mình trong tay. Tiếc thay, bạn không phải là anh hùng hư cấu, và nếu bạn thử làm vậy, có lẽ hò hét sẽ là phần duy nhất bạn thực hiện tốt.

Kế hoạch của bạn thận trọng hơn một chút. Bạn sẽ đu trên sợi dây đang giữ, nhưng thay vì buông tay, bạn sẽ bắt lấy một sợi dây khác. Sau đó, bạn sẽ từ từ và cẩn thận leo lên sợi dây ban đầu của mình, sao cho sợi dây mới bạn đang giữ sẽ trở nên nằm ngang - hoặc đạt đến toàn bộ chiều dài của nó, hoặc đạt đến khoảng cách giữa hai sợi dây, tùy theo giá trị nào nhỏ hơn. Sau đó, bạn sẽ nghỉ ngơi một chút và đu tiếp để lặp lại quá trình này. Lưu ý rằng bạn không nhất thiết phải bắt sợi dây đầu tiên bạn gặp khi đang đu, bạn có thể thích đu xa hơn một chút và bắt một sợi dây ở xa hơn. Bạn cũng có thể leo lên sợi dây bạn đang đu qua lại để giảm khoảng cách giữa bạn và gốc của sợi dây. Thực tế, điều này có nghĩa là bạn có thể bắt bất kỳ sợi dây nào mà sợi dây của bạn cắt qua khi đang đu. Lưu ý rằng bạn sẽ không leo xuống dây khi đang đu.

Một điều khác biệt nữa giữa bạn và bất kỳ anh hùng hư cấu nào là trước khi bắt đầu toàn bộ quy trình khá rủi ro này, bạn muốn biết liệu thực sự có thể sang được bờ bên kia của khu rừng theo cách này hay không. Và đây là câu hỏi bạn phải trả lời trong 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ộ test, \(T\). \(T\) bộ test tiếp theo. Dòng đầu tiên của mỗi bộ test chứa số lượng dây leo \(N\). \(N\) dòng mô tả các dây leo tiếp theo, mỗi dòng gồm một cặp số nguyên \(d_i\) và \(l_i\) - tương ứng là khoảng cách của dây leo so với gờ đá của bạn và chiều dài của dây leo. Dòng cuối cùng của bộ test chứa khoảng cách \(D\) đến gờ đá nơi tình yêu của bạn đang đợi. Bạn bắt đầu bằng việc nắm giữ sợi dây đầu tiê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à YES hoặc NO, cho biết liệu bạn có thể đến được với tình yêu của mình hay không, dựa trên các quy tắc trên.

Ràng buộc

• \(0 < d_i, l_i, D \le 10^9\).
• \(T \le 30\).
• \(d_i < d_{i+1}\).
• Vì bạn giữ sợi dây đầu tiên, \(d_0 \le l_0\).
• \(d_{N-1} < D\).

Phân nhóm

• Test set 1 (Visible Verdict): \(1 \le N \le 100\).
• Test set 2 (Hidden Verdict): \(1 \le N \le 10000\). Tổng số dây leo trong tất cả các bộ test không quá 60000.

Đ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
3 4
4 10
6 10
9
3
3 4
4 10
7 10
9
2
6 6
10 3
13
2
6 6
10 3
14

Case #1: YES
Case #2: NO
Case #3: YES
Case #4: NO

Nguồn

Google Code Jam 2012, Vòng 2, bài Swinging Wild.

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