Google Code Jam 2013 - Round 3

Đã đến lúc cho vòng chung kết Google Code Jam, và tất cả chúng ta đều muốn có mặt ở đó! Thật không may, một vài người trong chúng ta đã vô tình đến Mountain View thay vì địa điểm chính xác: London, Anh. Nhưng đừng lo lắng - chúng ta có thể bắt dịch vụ xe buýt đưa đón miễn phí của Google từ Mountain View đến London!

Dịch vụ xe buýt bao gồm \(M\) tuyến đường một chiều kết nối các cặp thành phố. Đối với mỗi tuyến đường, bạn biết nó đi từ thành phố nào đến thành phố nào, nhưng không may là bạn không biết chính xác các tuyến đường này dài bao nhiêu. Thay vào đó, với mỗi tuyến đường, bạn chỉ biết rằng độ dài của nó có thể là bất kỳ giá trị nguyên nào từ \(a_i\) đến \(b_i\), bao gồm cả hai đầu mút.

Tôi đã đi xe buýt của Google nhiều lần trước đây, vì vậy tôi đã đề xuất một lộ trình gồm các tuyến đường từ Mountain View đến London. Nhưng bạn lo lắng rằng kỹ năng tìm đường của tôi không tốt bằng bạn, và bạn muốn kiểm tra lại.

Cho lộ trình mà tôi đang đề xuất, liệu nó có thể là một con đường ngắn nhất từ Mountain View đến London không? Nếu không, ID của tuyến xe buýt đầu tiên trong lộ trình của tôi mà chắc chắn không nằm trong bất kỳ con đường ngắn nhất nào là gì (giả sử rằng tất cả các tuyến xe buýt trước đó đã được đi theo lộ trình tôi đề xuất)?

Ví dụ, giả sử chúng ta có danh sách các tuyến xe buýt sau:

ID | Start City     |  Destination City  |  Shuttle Length
---+----------------+--------------------+----------------
1  | Mountain View  |  London            |  [100, 1000]
2  | Mountain View  |  Paris             |  [500, 5000]
3  | Paris          |  London            |  [400, 600]
4  | Paris          |  Moscow            |  [500, 5000]
5  | Moscow         |  London            |  [1, 10000]

Tôi đề xuất lộ trình Mountain View -> Paris -> Moscow -> London. Con đường ngắn nhất thực sự có thể là tuyến đường trực tiếp từ Mountain View đến London, hoặc lộ trình Mountain View -> Paris -> London. Điều này có nghĩa là tuyến đường thứ hai trong lộ trình của tôi (Paris -> Moscow) là tuyến đường đầu tiên chắc chắn không phải là một phần của con đường ngắn nhất.

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 bắt đầu bằng một dòng chứa ba số nguyên dương \(N\), \(M\) và \(P\). \(N\) đại diện cho tổng số thành phố (các thành phố được đánh số từ \(1\) đến \(N\)), \(M\) đại diện cho tổng số tuyến xe buýt, và \(P\) đại diện cho số lượng tuyến xe buýt trong lộ trình của tôi từ Mountain View (thành phố số 1) đến London (thành phố số 2).

Tiếp theo là \(M\) dòng, mỗi dòng gồm bốn số nguyên \(u_i, v_i, a_i, b_i\). Mỗi dòng thể hiện rằng có một tuyến xe buýt một chiều từ thành phố \(u_i\) đến thành phố \(v_i\), và bạn biết rằng độ dài của nó có thể là bất kỳ giá trị nguyên nào từ \(a_i\) đến \(b_i\). Các tuyến đường được cấp ID từ \(1\) đến \(M\) theo đúng thứ tự trong dữ liệu vào.

Tiếp theo là một dòng gồm \(P\) số nguyên duy nhất trong phạm vi từ \(1\) đến \(M\). Những số này đại diện cho các tuyến xe buýt tôi đang đưa bạn đi, theo đúng thứ tự. Mỗi số là ID của một tuyến đường từ danh sách trước đó.

Dữ liệu ra

Đối với mỗi bộ test, hãy xuất một dòng chứa "Case #x: n", trong đó x là số thứ tự bộ test (bắt đầu từ 1) và n là ID của tuyến xe buýt đầu tiên trong lộ trình của tôi mà không thể là một phần của con đường ngắn nhất từ Mountain View đến London. Nếu không có tuyến đường nào như vậy, hãy in "Looks Good To Me".

Ràng buộc

• \(1 \le T \le 10\).
• \(1 \le u_i, v_i \le N\).
• \(1 \le a_i \le b_i \le 1,000,000\).
• Lộ trình của tôi được đảm bảo là một lộ trình hợp lệ từ Mountain View (thành phố số 1) đến London (thành phố số 2).
• Có thể có nhiều hơn một tuyến xe buýt giữa cùng hai thành phố và có thể có tuyến xe buýt đi từ một thành phố đến chính nó. Ngoài ra, lộ trình được đề xuất có thể đi qua cùng một thành phố nhiều lần, nhưng nó sẽ không sử dụng cùng một tuyến xe buýt nhiều lần.

Phân nhóm

• Small dataset: \(2 \le N \le 20, 1 \le M \le 20, 1 \le P \le 10\).
• Large dataset: \(2 \le N \le 1000, 1 \le M \le 2000, 1 \le P \le 500\).

Đ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
4 5 3
1 2 100 1000
1 3 500 5000
3 2 400 600
3 4 500 5000
4 2 1 10000
2 4 5
3 3 2
1 3 1 1
3 2 1 1
1 2 1 2
1 2
5 6 3
1 3 1 1
4 2 1 9
1 4 1 1
3 5 2 2
5 2 2 2
3 4 1 2
1 6 2

Case #1: 4
Case #2: Looks Good To Me
Case #3: 6

Nguồn

Google Code Jam 2013, Vòng 3, bài Are We Lost Yet?.

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 đã chơi roulette trong một thời gian tại một sòng bạc địa phương. Roulette là một trò chơi sòng bạc đơn giản, trong đó nhiều người chơi đặt cược vào một hoặc nhiều số từ \(0\) đến \(36\) (bao gồm cả hai số này). Tiếp theo, một bánh xe được quay theo một hướng với một quả bóng quay theo hướng ngược lại. Bánh xe roulette chứa các số tương tự từ \(0\) đến \(36\). Một số bánh xe roulette thực tế cũng có một ô được gắn nhãn \(00\), nhưng bánh xe của chúng ta thì không. Cuối cùng, quả bóng rơi vào một trong các số. Nếu một người chơi đặt cược vào con số cụ thể đó, anh ta sẽ nhận được \(36\) lần số tiền đặt cược của mình (vì vậy lợi nhuận của lần đặt cược đó là \(35\) lần số tiền đặt cược). Tất cả các khoản đặt cược vào các con số khác đều thua.

Thật không may, may mắn đã không đứng về phía bạn và bạn đã thua suốt cả đêm. Tại một thời điểm, bạn bắt đầu tự hỏi liệu trò chơi roulette có công bằng hay không, và sau khi quan sát trò chơi thêm một chút, bạn nhận thấy một quy luật chắc chắn sẽ mang lại lợi nhuận cho sòng bạc: quả bóng luôn rơi vào một trong những con số có tổng số tiền đặt cược ít nhất! Nếu có nhiều số có cùng tổng số tiền đặt cược ít nhất, quả bóng sẽ rơi vào một trong những số đó một cách ngẫu nhiên đồng khả năng.

Tất nhiên, bạn sẽ thông báo cho các cơ quan chức năng về hành vi gian lận này, nhưng trước tiên bạn muốn gỡ lại tiền của mình bằng cách khai thác kiến thức mới tìm được. Để làm như vậy, bạn đợi cho đến khi tất cả những người chơi khác đã đặt cược xong và sau đó mới đặt cược của riêng mình. Thật không may, bạn chỉ còn lại một ngân sách hạn chế, vì vậy bạn không thể đặt cược nhiều hơn số đó. Bạn được phép đặt cược vào không hoặc nhiều số khác nhau và mỗi lần đặt cược đó có thể là bất kỳ số nguyên dương nào (có thể với số tiền khác nhau cho các số khác nhau), miễn là tổng số tiền đặt cược của bạn không vượt quá ngân sách của bạn. Lợi nhuận kỳ vọng tối đa bạn có thể kiếm được là bao nhiêu?

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 tuân theo.
Mỗi bộ test bao gồm hai dòng. Dòng đầu tiên chứa hai số nguyên: ngân sách bạn vẫn còn, \(B\), và số lượng số mà những người chơi khác đã đặt cược, \(N\). Dòng thứ hai chứa \(N\) số nguyên \(X_i\), tổng số tiền mà những người chơi khác đã đặt cược trên mỗi số khác nhau đó.

Dữ liệu ra

Đối với mỗi bộ test, hãy xuất một dòng chứa "Case #x: " theo sau là lợi nhuận kỳ vọng tối đa mà bạn kiếm được nếu bạn đặt cược một cách tối ưu. Lợi nhuận sẽ được coi là chính xác nếu nó nằm trong sai số tuyệt đối hoặc tương đối là \(10^{-6}\) so với đáp án chính xác.

Ràng buộc

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

Phân nhóm

• Phân nhóm 1 (Visible): \(1 \le B, X_i \le 1,000\).
• Phân nhóm 2 (Hidden): \(1 \le B, X_i \le 10^{12}\).

Đ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
100 1
10
34 3
5 6 7
34 4
1 1 10 10

Case #1: 0
Case #2: 2
Case #3: 0.9428571429

Nguồn

Google Code Jam 2013, Vòng 3, bài Cheaters.

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

Một vòng quay quan sát bao gồm \(N\) cabin chở khách được sắp xếp thành một vòng tròn, quay chậm rãi. Các cabin lần lượt đi qua lối vào, và khi một cabin đi qua lối vào, một người có thể bước vào cabin đó.

Trong bài toán này, các cabin nhỏ đến mức mỗi cabin chỉ có thể chở đúng một người. Vì vậy, nếu cabin đi qua lối vào đã có người, người đang đợi ở lối vào sẽ phải đợi cabin tiếp theo đến. Nếu cabin đó cũng đã có người, người đó sẽ phải đợi cabin tiếp theo nữa, và cứ thế, cho đến khi một cabin trống xuất hiện. Để đơn giản, chúng ta sẽ không xem xét việc mọi người rời khỏi cabin — hãy giả sử rằng tất cả những gì mọi người làm là bước vào cabin, và sau đó quay cùng vòng quay trong một thời gian dài tùy ý.

Chúng tôi muốn đảm bảo mọi người không thất vọng vì thời gian chờ đợi lâu, và vì vậy chúng tôi đã giới thiệu một sơ đồ giá linh hoạt: khi một người tiếp cận vòng quay, và cabin đầu tiên đi qua lối vào là cabin trống, cô ấy trả \(N\) đô la cho chuyến đi. Nếu cabin đầu tiên đã có người và cô ấy phải đợi cabin thứ hai, cô ấy trả \(N-1\) đô la cho chuyến đi. Nếu hai cabin đầu tiên đã có người và cô ấy phải đợi cabin thứ ba, cô ấy trả \(N-2\) đô la cho chuyến đi. Nói chung, nếu cô ấy phải đợi \(K\) cabin đã có người đi qua, cô ấy trả \(N-K\) đô la. Trong trường hợp xấu nhất, khi cô ấy phải đợi tất cả trừ một cabin đi qua, cô ấy sẽ chỉ trả 1 đô la.

Hãy giả sử rằng mọi người tiếp cận vòng quay của chúng ta tại các thời điểm ngẫu nhiên, vì vậy đối với mỗi người tiếp cận vòng quay, cabin đầu tiên đi qua lối vào được chọn ngẫu nhiên và độc lập. Hãy cũng giả sử rằng không ai đến vòng quay khi đã có ít nhất một người đang đợi để vào, để chúng ta không phải xử lý việc xếp hàng. Một người sẽ luôn đi cabin trống đầu tiên đi qua lối vào.

Bạn được cho số lượng cabin và những cabin nào đã có người. Chúng ta sẽ kiếm được trung bình bao nhiêu tiền cho đến khi tất cả các cabin đều có người?

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\) dòng tiếp theo. Mỗi dòng mô tả một bộ test và chỉ chứa các ký tự '.' (dấu chấm) hoặc 'X' (chữ cái X viết hoa). Số lượng ký tự trong dòng này cho bạn biết \(N\). Ký tự thứ \(i\) là 'X' khi cabin thứ \(i\) đã có người, và '.' khi nó vẫn còn trống. Các cabin được đánh số theo thứ tự chúng đi qua lối vào, vì vậy cabin thứ 1 được tiếp nối bởi cabin thứ 2, và cứ thế, bắt đầu lại từ đầu sau khi cabin cuối cùng đi qua.

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ố tiền trung bình chúng ta sẽ nhận được, tính bằng đô la. Các câu trả lời có sai số tuyệt đối hoặc tương đối không lớn hơn \(10^{-9}\) sẽ được chấp nhận.

Ràng buộc

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

Phân nhóm

• Test set 1 (Visible): \(1 \le N \le 20\).
• Test set 2 (Hidden): \(1 \le N \le 200\).

Đ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
.X.
X.X.
.XX.
X..XX.
.XX..X

Case #1: 4.66666666666667
Case #2: 6.00000000000000
Case #3: 5.75000000000000
Case #4: 13.4722222222222
Case #5: 13.5277777777778

Nguồn

Google Code Jam 2013, Vòng 3, bài Observation Wheel.

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ừa mới mua một trang trại lớn và muốn xây dựng một hàng rào xung quanh nó. Đã có sẵn \(N\) cọc rào trong trang trại của bạn.

Bạn sẽ thêm các đoạn hàng rào là các đường thẳng nối các cọc rào. Thật không may, vì những lý do pháp lý, luật sư của bạn nhấn mạnh rằng bạn thực sự phải sử dụng tất cả các cọc rào, nếu không mọi chuyện sẽ trở nên tồi tệ.

Trong bài toán này, các cọc rào được biểu diễn dưới dạng các điểm trên mặt phẳng 2 chiều. Bạn muốn xây dựng hàng rào bằng cách sắp xếp các cọc rào theo một thứ tự nào đó, sau đó nối cọc thứ nhất với cọc thứ hai, thứ hai với thứ ba, và cuối cùng là cọc cuối cùng với cọc đầu tiên. Các đoạn hàng rào bạn tạo ra phải tạo thành một đa giác không tự cắt. Nghĩa là, tại mỗi cọc rào chỉ có đúng hai đoạn hàng rào nối vào, và tại mọi điểm khác có tối đa một đoạn hàng rào đi qua.

Bây giờ, điều đó khá dễ dàng, nhưng bạn cũng muốn bảo toàn thực tế là trang trại của bạn rất lớn! Sẽ không vui chút nào nếu bạn rào lại phần lớn trang trại của mình bằng các hàng rào. Vì vậy, bạn muốn tạo ra hàng rào sao cho diện tích bao quanh lớn hơn một nửa diện tích tối đa mà bạn có thể bao quanh nếu bạn được phép không sử dụng tất cả các cọc.

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. Dòng đầu tiên của mỗi bộ thử nghiệm chứa số \(N\) các cọc rào. Các cọc được đánh số từ \(0\) đến \(N - 1\). Mỗi dòng trong \(N\) dòng tiếp theo chứa hai số nguyên \(X_i\) và \(Y_i\) cách nhau bởi một khoảng trắng: tọa độ của cọc 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 #x: ", trong đó x là số thứ tự bộ thử nghiệm (bắt đầu từ 1), tiếp theo là \(N\) số nguyên phân biệt từ \(0\) đến \(N - 1\), cách nhau bởi dấu cách. Đó là số hiệu của các cọc rào, theo chiều kim đồng hồ hoặc ngược chiều kim đồng hồ, mà bạn sẽ sử dụng để xây dựng hàng rào. Lưu ý rằng cọc đầu tiên và cọc cuối cùng được nối với nhau.

Nếu có nhiều giải pháp, hãy in bất kỳ giải pháp nào trong số đó.

Ràng buộc

• Các cọc rào sẽ ở \(N\) điểm duy nhất và không cùng nằm trên một đường thẳng.

Phân nhóm

• Small dataset (Test set 1):

  • \(1 \le T \le 100\)
  • \(3 \le N \le 10\)
  • \(-100 \le X_i, Y_i \le 100\)

  • Large dataset (Test set 2):

  • \(1 \le T \le 30\)

  • \(3 \le N \le 1000\)
  • \(-50000 \le X_i, Y_i \le 50000\)

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

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

Nguồn

Google Code Jam 2013, Vòng 3, bài Rural Planning.

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