Google Code Jam 2013 - Round 1B

Kim cương đang rơi xuống từ bầu trời. Mọi người hiện đang mua các vị trí mà kim cương có thể rơi xuống, chỉ để sở hữu một viên kim cương nếu có một viên rơi vào đó. Bạn đã được chào mời một vị trí như vậy và muốn biết liệu đó có phải là một thỏa thuận tốt hay không.

Kim cương có hình dạng, bạn đoán đúng rồi đấy, hình kim cương: chúng là các hình vuông với các đỉnh \((X-1, Y)\), \((X, Y+1)\), \((X+1, Y)\) và \((X, Y-1)\) với \(X, Y\) nào đó mà chúng ta gọi là tâm của viên kim cương. Tất cả các viên kim cương luôn nằm trong mặt phẳng \(X-Y\). \(X\) là hướng ngang, \(Y\) là hướng dọc. Mặt đất ở \(Y=0\), và các tọa độ \(Y\) dương nằm trên mặt đất.

Các viên kim cương rơi từng viên một dọc theo trục \(Y\). Điều này có nghĩa là chúng bắt đầu tại \((0, Y)\) với \(Y\) rất lớn, và rơi thẳng đứng xuống, cho đến khi chúng chạm đất hoặc chạm vào một viên kim cương khác.

Khi một viên kim cương chạm đất, nó rơi cho đến khi bị chôn xuống đất tới tâm của nó, và sau đó dừng lại. Điều này có nghĩa là tất cả các viên kim cương ngừng rơi hoặc trượt nếu tâm của chúng đạt đến \(Y=0\).

Khi một viên kim cương chạm vào một viên kim cương khác, đỉnh chạm đỉnh, nó có thể bắt đầu trượt xuống, mà không xoay, theo một trong hai hướng có thể: xuống và sang trái, hoặc xuống và sang phải. Nếu không có viên kim cương nào chặn ngay lập tức ở một trong hai phía, nó sẽ trượt sang trái hoặc sang phải với xác suất bằng nhau. Nếu có một viên kim cương chặn một phía, viên kim cương đang rơi sẽ trượt sang phía còn lại cho đến khi nó bị chặn bởi một viên kim cương khác, hoặc bị chôn vùi trong đất. Nếu có các viên kim cương chặn cả đường sang trái và sang phải, viên kim cương đó sẽ dừng lại.

Hãy xem xét ví dụ trong hình. Viên kim cương đầu tiên chạm đất và dừng lại khi bị chôn một nửa, với tâm tại \((0, 0)\). Viên kim cương thứ hai có thể trượt sang trái hoặc sang phải với xác suất bằng nhau. Ở đây, nó tình cờ đi sang trái. Nó dừng lại khi bị chôn trong đất cạnh viên kim cương đầu tiên, tại \((-2, 0)\). Viên kim cương thứ ba cũng sẽ chạm vào viên đầu tiên. Sau đó, nó sẽ ngẫu nhiên trượt sang phải và dừng lại trên mặt đất, hoặc trượt sang trái, và dừng lại ở giữa và phía trên hai viên kim cương đã đặt trước đó. Nó lại tình cờ đi sang trái, nên nó dừng lại ở \((-1, 1)\). Viên kim cương thứ tư không có lựa chọn nào khác: nó sẽ trượt sang phải, và dừng lại trên mặt đất tại \((2, 0)\).

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\) dòng tiếp theo. Mỗi dòng chứa ba số nguyên: số lượng kim cương rơi \(N\), và vị trí \(X, Y\) của nơi bạn quan tâm. Lưu ý rằng nơi bạn quan tâm mua không nhất thiết phải ở trên hoặc gần mặt đất.

Dữ liệu ra

Đối với mỗi bộ test, hãy xuất một dòng chứa "Case #x: p", trong đó x là số thứ tự bộ test (bắt đầu từ 1) và p là xác suất để một trong \(N\) viên kim cương sẽ rơi sao cho tâm của nó nằm chính xác tại (\(X, Y\)). Câu trả lời sẽ được coi là đúng nếu nó nằm trong sai số tuyệt đối \(10^{-6}\) so với câu trả lời chính xác.

Ràng buộc

• \(1 \le T \le 100\).
• \(-10,000 \le X \le 10,000\).
• \(0 \le Y \le 10,000\).
• \(X + Y\) là số chẵn.

Phân nhóm

• Small dataset (Test set 1): \(1 \le N \le 20\).
• Large dataset (Test set 2): \(1 \le N \le 10^6\).

Đ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ụ

7
1 0 0
1 0 2
3 0 0
3 2 0
3 1 1
4 1 1
4 0 2

Case #1: 1.0
Case #2: 0.0
Case #3: 1.0
Case #4: 0.75
Case #5: 0.25
Case #6: 0.5
Case #7: 0.0

Nguồn

Google Code Jam 2013, Vòng 1B, bài Falling Diamonds.

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

Gagan vừa nhận được một email từ người bạn Jorge. Email chứa thông tin quan trọng, nhưng không may nó đã bị lỗi khi gửi: tất cả các khoảng trắng đều bị mất, và sau khi xóa các khoảng trắng, một số chữ cái đã bị thay đổi thành các chữ cái khác! Tất cả những gì Gagan có bây giờ là một chuỗi \(S\) gồm các ký tự viết thường.

Bạn biết rằng email ban đầu được tạo ra từ các từ trong từ điển được mô tả bên dưới. Bạn cũng biết rằng các chữ cái đã bị thay đổi sau khi các khoảng trắng được loại bỏ, và khoảng cách giữa các chỉ số của bất kỳ hai chữ cái bị thay đổi nào không nhỏ hơn \(5\). Ví dụ, chuỗi "code jam" có thể đã trở thành "codejam", "dodejbm", "zodejan" hoặc "cidejab", nhưng không thể là "kodezam" (vì khoảng cách giữa chỉ số của thay đổi "k" và thay đổi "z" chỉ là \(4\)).

Số lượng chữ cái tối thiểu có thể đã bị thay đổi là bao nhiêu?

Từ điển

Từ điển chứa \(W\) từ có độ dài ít nhất là \(1\) và tối đa là \(10\) ký tự viết thường và được cung cấp ở đầu tệp dữ liệu vào. Nó không phải là từ điển của bất kỳ ngôn ngữ tự nhiên nào, mặc dù nó có chứa một số từ tiếng Anh. Từ điển là giống nhau cho tất cả các bộ test trong cùng một tệp dữ liệu vào. Từ điển được đưa ra theo thứ tự tăng dần về mặt từ điển và không chứa các từ trùng lặp.

Dữ liệu vào

Dòng đầu tiên của dữ liệu vào cho biết số lượng từ trong từ điển, \(W\). Mỗi dòng trong \(W\) dòng tiếp theo chứa một chuỗi các ký tự viết thường a-z đại diện cho một từ trong từ điển.
Dòng tiếp theo 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 bao gồm một dòng duy nhất chứa một chuỗi \(S\), bao gồm các ký tự viết thường a-z.

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 chữ cái tối thiểu có thể đã bị thay đổi để tạo ra \(S\).

Ràng buộc

• \(W = 521196\).
• Mỗi từ trong từ điển chứa ít nhất 1 và tối đa 10 ký tự viết thường.
• Từ điển được sắp xếp theo thứ tự từ điển tăng dần.
• Từ điển không chứa các từ trùng lặp.
• Tổng số ký tự trong từ điển là 3323296.
• \(S\) là hợp lệ: có thể tạo ra nó bằng phương pháp mô tả ở trên.

Phân nhóm

• Test set 1 (Visible):

  • \(1 \le T \le 20\).
  • \(1 \le\) độ dài của \(S \le 50\).

  • Test set 2 (Hidden):

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

  • \(1 \le\) độ dài của \(S \le 4000\).

Đ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ụ

9
aabea
bobs
code
in
jam
oo
operation
production
system
4
codejam
cxdejax
cooperationaabea
jobsinproduction

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

Nguồn

Google Code Jam 2013, Vòng 1B, bài Garbled Email.

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

Armin đang chơi Osmos, một trò chơi giải đố dựa trên vật lý được phát triển bởi Hemisphere Games. Trong trò chơi này, anh ấy điều khiển một "mote" (hạt), di chuyển xung quanh và hấp thụ các hạt nhỏ hơn.

Trong trò chơi này, một hạt có thể hấp thụ (hoặc bị hấp thụ bởi) những thứ khác! Trò chơi trong bài toán này có ý tưởng tương tự như Osmos, nhưng không yêu cầu bạn phải từng chơi trò chơi này.

Khi hạt của Armin hấp thụ một hạt nhỏ hơn, hạt của anh ấy sẽ lớn thêm một lượng bằng kích thước của hạt nhỏ đó. Sau khi lớn hơn, anh ấy có thể hấp thụ thêm nhiều hạt hơn nữa.
Ví dụ: giả sử hạt của Armin có kích thước \(10\), và có các hạt khác với kích thước \(9, 13\) và \(19\). Ban đầu, hạt của Armin chỉ có thể hấp thụ hạt kích thước \(9\). Sau khi hấp thụ, nó sẽ có kích thước \(19\). Sau đó, nó có thể hấp thụ hạt kích thước \(13\). Khi đó, nó sẽ có kích thước \(32\). Bây giờ, hạt của Armin có thể hấp thụ hạt cuối cùng.

Lưu ý rằng hạt của Armin chỉ có thể hấp thụ một hạt khác nếu và chỉ nếu hạt đó nhỏ hơn. Nếu hạt khác có cùng kích thước, hạt của Armin không thể hấp thụ nó.

Bạn chịu trách nhiệm cho chương trình tạo ra các hạt để Armin hấp thụ. Chương trình đã tạo ra một số hạt với các kích thước khác nhau và hạt của Armin. Thật không may, với kích thước hạt của Armin và danh sách các hạt khác, có thể không có cách nào để Armin hấp thụ tất cả chúng.

Bạn muốn khắc phục điều đó. Có hai loại thao tác bạn có thể thực hiện, theo bất kỳ thứ tự nào, bất kỳ số lần nào: bạn có thể thêm một hạt có kích thước nguyên dương bất kỳ vào trò chơi, hoặc bạn có thể loại bỏ bất kỳ một hạt hiện có nào. Số lần tối thiểu bạn cần thực hiện các thao tác đó để Armin có thể hấp thụ mọi hạt khác là bao nhiêu?

Ví dụ, giả sử hạt của Armin có kích thước \(10\) và các hạt khác có kích thước \([9, 20, 25, 100]\). Trò chơi này hiện không thể giải được, nhưng bằng cách thêm một hạt kích thước \(3\) và loại bỏ hạt kích thước \(100\), bạn có thể làm cho nó giải được chỉ trong \(2\) thao tác. Đáp án ở đây là \(2\).

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 cho biết kích thước hạt của Armin, \(A\), và số lượng các hạt khác, \(N\). Dòng thứ hai chứa \(N\) kích thước của các hạt khác. Tất cả các kích thước hạt được cho sẽ là số nguyên.

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ố thao tác tối thiểu cần thiết để trò chơi có thể giải được.

Ràng buộc

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

Phân nhóm

• Tập dữ liệu 1 (Small - Visible):
  • \(1 \le A \le 100\).
  • \(1 \le\) tất cả kích thước hạt \(\le 100\).
  • \(1 \le N \le 10\).
• Tập dữ liệu 2 (Large - Hidden):
  • \(1 \le A \le 10^6\).
  • \(1 \le\) tất cả kích thước hạt \(\le 10^6\).
  • \(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
2 2
2 1
2 4
2 1 1 6
10 4
25 20 9 100
1 4
1 1 1 1

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

Nguồn

Google Code Jam 2013, Vòng 1B, bài Osmos.

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