Google Code Jam 2012 - Round 1B

Tôi có một tập hợp các số nguyên dương \(S\). Bạn có thể tìm thấy hai tập hợp con khác nhau, không rỗng, có cùng tổng hay không?

Lưu ý: Một tập hợp con là một tập hợp chỉ chứa các phần tử từ \(S\), và hai tập hợp con là khác nhau nếu chúng không có chính xác các phần tử giống nhau.

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ộ trên một dòng. Mỗi bộ test bắt đầu bằng \(N\), số lượng số nguyên dương trong \(S\). Tiếp theo là \(N\) số nguyên dương phân biệt, tất cả nằm trên cùng một dòng.

Dữ liệu ra

Đối với mỗi bộ test, trước tiên hãy in ra một dòng chứa "Case #x:", trong đó x là số thứ tự bộ test (bắt đầu từ 1).

• Nếu có hai tập hợp con khác nhau của \(S\) có cùng tổng, hãy in ra các tập hợp con này, mỗi tập hợp trên một dòng. Mỗi dòng nên chứa các số trong một tập hợp con, cách nhau bởi dấu cách.
• Nếu không thể, bạn nên in ra chuỗi "Impossible" trên một dòng duy nhất.

Nếu có nhiều cách chọn hai tập hợp con có cùng tổng, bất kỳ lựa chọn nào cũng được chấp nhận.

Ràng buộc

• Không có hai số nào trong \(S\) bằng nhau.
• \(1 \le T \le 10\).

Phân nhóm

Test set 1 (Visible Verdict)

• \(N\) chính xác bằng 20.
• Mỗi số trong \(S\) sẽ là một số nguyên dương nhỏ hơn \(10^5\).

Test set 2 (Hidden Verdict)

• \(N\) chính xác bằng 500.
• Mỗi số trong \(S\) sẽ là một số nguyên dương nhỏ hơn \(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ụ

2
20 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
20 120 266 858 1243 1657 1771 2328 2490 2665 2894 3117 4210 4454 4943 5690 6170 7048 7125 9512 9600

Case #1: Possible
Case #2: Possible

Nguồn

Google Code Jam 2012, Vòng 1B, bài Equal Sums.

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

Có \(N\) thí sinh trong một chương trình truyền hình thực tế. Mỗi thí sinh được ban giám khảo cho một số điểm và nhận được bình chọn từ khán giả. Điểm số từ ban giám khảo và bình chọn từ khán giả được kết hợp để tạo thành điểm số cuối cùng cho thí sinh theo cách sau:

Gọi \(X\) là tổng điểm số mà ban giám khảo đã cho tất cả các thí sinh. Giả sử một thí sinh nhận được \(J\) điểm từ ban giám khảo và nhận được một tỉ lệ \(Y\) (từ 0 đến 1, bao gồm cả hai đầu) trong tổng số phiếu bầu của khán giả (\(Y\) có thể ví dụ là 0.3). Khi đó điểm số cuối cùng của thí sinh đó là \(J + X \times Y\). Lưu ý rằng tổng tỉ lệ bình chọn của khán giả cho tất cả các thí sinh phải bằng 1.

Thí sinh có điểm số thấp nhất sẽ bị loại.

Cho biết số điểm mà các thí sinh nhận được từ ban giám khảo, nhiệm vụ của bạn là tìm ra, đối với mỗi thí sinh, phần trăm bình chọn tối thiểu từ khán giả mà họ phải nhận được để đảm bảo không bị loại, bất kể số phiếu bầu còn lại của khán giả được phân phối như thế nào.

Nếu có nhiều thí sinh cùng có điểm số thấp nhất, sẽ không có thí sinh nào bị loại.

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, mỗi bộ trên một dòng. Mỗi dòng bắt đầu bằng một số nguyên \(N\), số lượng thí sinh, theo sau là một khoảng trắng, rồi đến \(N\) số nguyên \(s_0, s_1, \dots, s_{N-1}\), ngăn cách bởi các khoảng trắng đơn. Số nguyên \(s_i\) là điểm số được ban giám khảo chấm cho thí sinh \(i\).

Dữ liệu ra

Với mỗi bộ test, xuất ra một dòng chứa "Case #x: " theo sau là \(N\) số thực: \(m_i\). Giá trị x là số thứ tự bộ test (bắt đầu từ 1). Giá trị \(m_i\) là phần trăm bình chọn tối thiểu của khán giả cần thiết để thí sinh \(i\) chắc chắn tránh bị loại.

Các câu trả lời trong phạm vi sai số tuyệt đối hoặc tương đối \(10^{-5}\) so với đáp án đúng sẽ được chấp nhận.

Ràng buộc

• \(0 \le s_i \le 100\).
• \(s_i > 0\) cho ít nhất một giá trị \(i\). Điều này có nghĩa là ít nhất một thí sinh sẽ có điểm số từ ban giám khảo lớn hơn 0.

Phân nhóm

• Test set 1 (Visible):
• \(1 \le T \le 20\).
• \(2 \le N \le 10\).
• Test set 2 (Hidden):
• \(1 \le T \le 50\).
• \(2 \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ụ

4
2 20 10
2 10 0
4 25 25 25 25
3 24 30 21

Case #1: 33.333333 66.666667
Case #2: 0.000000 100.000000
Case #3: 25.0 25.0 25.0 25.0
Case #4: 34.666667 26.666667 38.666667

Nguồn

Google Code Jam 2012, Vòng 1B, bài Safety in 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.

Bạn đang chèo thuyền kayak qua một hệ thống hang động ngầm và đột nhiên nhận ra thủy triều đang lên và bạn bị mắc kẹt! May mắn thay, bạn có bản đồ của hệ thống hang động. Bạn bị kẹt cho đến khi thủy triều bắt đầu rút, vì vậy bạn sẽ ở đây một lúc. Trong thời gian chờ đợi, bạn muốn xác định con đường nhanh nhất để đến lối thoát ngay khi thủy triều bắt đầu rút.

Hệ thống hang động là một lưới kích thước \(N \times M\). Bản đồ của bạn gồm hai lưới số \(N \times M\): một lưới xác định chiều cao của trần hang ở mỗi ô, và một lưới xác định chiều cao của sàn hang ở mỗi ô. Sàn của hệ thống hang động có tính thẩm thấu, nghĩa là khi mực nước giảm xuống, sẽ không có nước đọng lại phía trên mực nước.

Bạn đang bị kẹt ở góc tây bắc của bản đồ. Mực nước hiện tại là \(H\) cm, và một khi nó bắt đầu giảm, nó sẽ giảm với tốc độ không đổi là 10 cm mỗi giây, xuống đến mức 0. Lối thoát nằm ở góc đông nam của bản đồ. Hiện tại nó đang bị ngập nước, nhưng nó sẽ trở nên khả dụng ngay khi thủy triều bắt đầu rút.

Tại bất kỳ thời điểm nào, bạn có thể di chuyển theo hướng bắc, nam, đông hoặc tây sang một ô liền kề với các ràng buộc sau:

• Mực nước, chiều cao sàn của ô hiện tại, và chiều cao sàn của ô liền kề đều phải thấp hơn ít nhất 50 cm so với chiều cao trần của ô liền kề. Lưu ý: điều này có nghĩa là bạn sẽ không bao giờ có thể đi vào một ô có khoảng cách giữa sàn và trần ít hơn 50 cm.
• Chiều cao sàn của ô liền kề cũng phải thấp hơn ít nhất 50 cm so với chiều cao trần của ô hiện tại.
• Bạn không bao giờ được di chuyển ra khỏi mép bản đồ.

Lưu ý rằng bạn có thể lên hoặc xuống bao nhiêu tùy thích với chiếc thuyền kayak của mình. (Bạn rất khỏe mạnh nhờ việc chèo thuyền này!) Ví dụ, bạn có thể đi từ một ô có sàn ở độ cao 10 cm sang một ô liền kề có sàn ở độ cao 9000 cm (giả sử các ràng buộc nêu trên được đáp ứng).

Các ràng buộc này được minh họa dưới đây:

• Trong hình đầu tiên, bạn không thể di chuyển sang phải vì mực nước thấp hơn chiều cao trần của ô liền kề ít hơn 50 cm.
• Trong hình thứ hai, bạn không thể di chuyển sang phải vì chiều cao sàn của ô hiện tại thấp hơn chiều cao trần của ô liền kề ít hơn 50 cm.
• Trong hình thứ ba, bạn không thể di chuyển sang phải vì chiều cao sàn của ô liền kề thấp hơn chiều cao trần của ô liền kề ít hơn 50 cm. Bạn sẽ không bao giờ có thể vào ô đó từ bất kỳ hướng nào.
• Trong hình thứ tư, bạn không thể di chuyển sang phải vì chiều cao sàn của ô liền kề thấp hơn chiều cao trần của ô hiện tại ít hơn 50 cm.

Khi di chuyển từ ô này sang ô khác, nếu có ít nhất 20 cm nước còn lại trên ô hiện tại khi bạn bắt đầu di chuyển, bạn mất 1 giây để hoàn thành việc di chuyển (bạn có thể dùng thuyền kayak). Ngược lại, bạn mất 10 giây (bạn phải kéo thuyền). Lưu ý rằng thời gian chỉ phụ thuộc vào mực nước ở ô bạn rời đi, không phải ở ô bạn đi vào.

Sẽ mất một thời gian trước khi thủy triều bắt đầu rút, và vì vậy bạn có thể dành bao nhiêu thời gian tùy thích để di chuyển trước khi nước bắt đầu hạ xuống. Điều quan trọng là bạn cần bao nhiêu thời gian kể từ thời điểm nước bắt đầu hạ cho đến khi bạn đến được lối thoát. Bạn có thể tính toán thời gian này không?

Dữ liệu vào

• Dòng đầu tiên chứa một số nguyên duy nhất, \(T\): số lượng bộ thử nghiệm.
• Tiếp theo là \(T\) bộ thử nghiệm, mỗi bộ bắt đầu bằng một dòng chứa các số nguyên \(H\), \(N\) và \(M\), đại diện cho mực nước ban đầu (cm) và kích thước bản đồ. \(2N\) dòng tiếp theo chứa chiều cao trần và sàn như sau:
  • \(N\) dòng tiếp theo, mỗi dòng chứa \(M\) số nguyên cách nhau bởi khoảng trắng. Số nguyên thứ \(j\) ở hàng thứ \(i\) đại diện cho \(C_{ij}\), chiều cao của trần nhà tính bằng cm tại vị trí lưới \((j, i)\), trong đó tọa độ \(i\) tăng dần về phía Nam, và tọa độ \(j\) tăng dần về phía Đông.
  • \(N\) dòng tiếp theo chứa \(M\) số nguyên cách nhau bởi khoảng trắng đại diện cho chiều cao của sàn, theo cùng định dạng.
• Tại vị trí bắt đầu, sẽ luôn có ít nhất 50 cm không khí giữa trần và mực nước ban đầu, và ít nhất 50 cm giữa trần và sàn.
• Vị trí lối thoát sẽ luôn có ít nhất 50 cm không khí giữa trần và sàn.
• Luôn có một đường thoát ra.

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: t", trong đó x là số thứ tự bộ thử nghiệm (bắt đầu từ 1) và t là thời gian, tính bằng giây, bắt đầu từ khi thủy triều bắt đầu rút, để bạn thoát ra khỏi hệ thống hang động. Các câu trả lời trong phạm vi sai số tuyệt đối hoặc tương đối \(10^{-6}\) so với câu trả lời đúng sẽ được chấp nhận.

Ghi chú

Có thể bạn có thể đi qua toàn bộ hệ thống hang động trước khi thủy triều bắt đầu rút. Trong trường hợp này, bạn có thể đợi ở lối thoát cho đến khi thủy triều bắt đầu rút, vì vậy câu trả lời trong trường hợp này phải là 0 (đây là trường hợp trong ví dụ thứ tư).

Ràng buộc

Phân nhóm

• Test set 1 (Visible Verdict):
  \(1 \le T \le 50\).
  \(1 \le N, M \le 10\).
  \(1 \le H \le 1000\).
  \(1 \le F_{xy} \le C_{xy} \le 1000\).

• Test set 2 (Hidden Verdict):
  \(1 \le T \le 50\).
  \(1 \le N, M \le 100\).
  \(1 \le H \le 10000\).
  \(1 \le F_{xy} \le C_{xy} \le 10000\).

Đ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
200 1 2
250 233
180 100
100 3 3
500 500 500
500 500 600
500 140 1000
10 10 10
10 10 490
10 10 10
100 3 3
500 100 500
100 100 500
500 500 500
10 10 10
10 10 10
10 10 10
100 2 2
1000 1000
1000 1000
100 900
900 100

Case #1: 11.7
Case #2: 3.0
Case #3: 18.0
Case #4: 0.0

Nguồn

Google Code Jam 2012, Vòng 1B, bài Tide Goes In, Tide Goes Out.

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