Google Code Jam 2014 - Round 1C

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 2014 - Enclosure 45 1.0s 1G
2 Google Code Jam 2014 - Part Elf 20 1.0s 1G
3 Google Code Jam 2014 - Reordering Train Cars 35 1.0s 1G

1. Google Code Jam 2014 - Enclosure

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

Nhiệm vụ của bạn trong bài toán này là tìm số lượng đá ít nhất cần đặt trên một lưới hình chữ nhật kích thước \(N \times M\) (\(N\) đoạn thẳng nằm ngang và \(M\) đoạn thẳng nằm dọc) để bao quanh ít nhất \(K\) điểm giao cắt. Một điểm giao cắt được coi là bị bao quanh nếu một trong hai điều kiện sau là đúng:

  1. Một viên đá được đặt tại điểm đó.
  2. Bắt đầu từ điểm đó, chúng ta không thể tìm được một đường đi dọc theo các đường lưới để đến một điểm trống trên biên của lưới mà chỉ đi qua các điểm giao cắt trống.

Ví dụ, để bao quanh 8 điểm trên lưới \(4 \times 5\), chúng ta cần ít nhất 6 viên đá. Một trong nhiều cách đặt đá hợp lệ được hiển thị bên dưới. Các điểm bị bao quanh được đánh dấu bằng chữ "x".

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\) dòng tiếp theo, mỗi dòng chứa ba số nguyên: \(N\) \(M\) \(K\).

Dữ liệu ra

Với mỗi bộ thử nghiệm, 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ố lượng đá tối thiểu cần thiết.

Ràng buộc

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

Phân nhóm

  • Small dataset: \(N \times M \le 20\).
  • Large dataset: \(N \times M \le 1000\).

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

Ví dụ

Ví dụ 1

Input 
2
4 5 8
3 5 11
Output 
Case #1: 6
Case #2: 8

Nguồn

Google Code Jam 2014, Vòng 1C, bài Enclosure.

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 2014 - Part Elf

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

Vida nói rằng cô ấy mang dòng máu Elf: ít nhất một trong những tổ tiên của cô ấy là Elf. Nhưng cô ấy không biết đó là cha mẹ (1 thế hệ trước), ông bà (2 thế hệ trước), hay một người nào đó từ nhiều thế hệ trước nữa. Hãy giúp cô ấy!

Quy tắc di truyền dòng máu Elf hoạt động như sau: Nếu một người cha/mẹ là Elf tỉ lệ A/B, và người còn lại là Elf tỉ lệ C/D, thì con của họ sẽ là Elf tỉ lệ (A/B + C/D) / 2. Ví dụ, nếu một người là Elf 0/1 (người thuần chủng) và một người là Elf 1/2 có con, đứa trẻ đó sẽ là Elf 1/4.

Vida chắc chắn về một điều: 40 thế hệ trước, cô ấy có \(2^{40}\) tổ tiên khác nhau, và mỗi người trong số họ hoặc là Elf 1/1 hoặc là Elf 0/1.

Vida nói cô ấy là Elf tỉ lệ P/Q. Hãy cho cô ấy biết số thế hệ tối thiểu trước đây có thể có một người là Elf 1/1 trong gia đình cô ấy. Nếu Vida không thể là Elf tỉ lệ P/Q, hãy thông báo rằng cô ấy đã nhầm!

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 một phân số có dạng P/Q, trong đó P và Q là các số nguyên.

Dữ liệu ra

Với mỗi bộ test, 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ố thế hệ tối thiểu trước đây có thể có một Elf 1/1 nếu cô ấy là Elf tỉ lệ P/Q. Nếu không thể, y phải là chuỗi "impossible".

Ràng buộc

  • \(1 \le \mathbf{T} \le 100\).

Phân nhóm

  • Small dataset:

    • \(1 \le \mathbf{P} < \mathbf{Q} \le 1000\).
    • P và Q không có ước chung (phân số tối giản).

    • Large dataset:

    • \(1 \le \mathbf{P} < \mathbf{Q} \le 10^{12}\).

    • P và Q có thể có ước chung (phân số không nhất thiết tối giản).

Ghi chú chung

Đúng vậy, Vida có rất nhiều tổ tiên. Nếu đó là phần phi thực tế nhất đối với bạn, hãy đọc lại phần về Elf.

Đ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 8/20 40%
Test Set 2 12/20 60%

Ví dụ

Ví dụ 1

Input 
5
1/2
3/4
1/4
2/23
123/31488
Output 
Case #1: 1
Case #2: 1
Case #3: 2
Case #4: impossible
Case #5: 8
Note

Lưu ý: Bộ test thứ năm không nằm trong giới hạn của Small dataset.

Giải thích ví dụ

  • Trong ví dụ đầu tiên, Vida có thể có một người cha/mẹ là Elf 1/1 và người còn lại là Elf 0/1. Điều đó có nghĩa là cô ấy có thể có Elf 1/1 từ 1 thế hệ trước, vì vậy đáp án là 1.
  • Trong ví dụ thứ hai, Vida có thể có một người cha/mẹ là Elf 1/1 và người còn lại là Elf 1/2. Đáp án là 1.
  • Trong ví dụ thứ ba, Vida có thể có cha mẹ là Elf 0/1 và Elf 1/2. Người cha/mẹ Elf 1/2 có thể có cha mẹ là Elf 1/1 và Elf 0/1. Điều này nghĩa là Elf 1/1 có thể xuất hiện từ 2 thế hệ trước, đáp án là 2.
  • Trong ví dụ thứ tư, không thể có tỉ lệ chính xác 2/23 nếu tất cả tổ tiên 40 thế hệ trước đều là 0/1 hoặc 1/1.

Nguồn

Google Code Jam 2014, Vòng 1C, bài Part Elf.

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 2014 - Reordering Train Cars

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

Yahya là một đứa trẻ thông minh, vì vậy tâm trí cậu luôn nảy sinh rất nhiều câu hỏi thú vị khi chơi với đồ chơi của mình. Bài toán hôm nay xuất hiện khi cha cậu mang về một bộ toa tàu đồ chơi, trong đó mỗi toa có một chữ cái tiếng Anh viết thường ở một mặt.

Khi mới nhận được món quà, cậu rất vui và bắt đầu chơi bằng cách nối các toa tàu lại với nhau mà không có mục tiêu cụ thể nào. Nhưng sau một thời gian, cậu cảm thấy chán (như thường lệ). Vì vậy, cậu quyết định định nghĩa một bài toán mới thú vị.

Bài toán là cậu hiện có \(N\) bộ toa tàu đã được nối sẵn. Cậu có thể biểu diễn mỗi bộ toa tàu đã nối này dưới dạng một chuỗi các chữ cái viết thường. Cậu muốn đếm số cách nối tất cả \(N\) bộ toa tàu này để tạo thành một đoàn tàu hợp lệ duy nhất. Một đoàn tàu được coi là hợp lệ nếu tất cả các lần xuất hiện của cùng một ký tự đều nằm cạnh nhau.

Hình trên là một cách Yahya có thể nối các bộ toa "ab", "bc" và "cd" để tạo thành một đoàn tàu hợp lệ: "ab bc cd". Nếu cậu nối chúng theo thứ tự "cd ab bc", đoàn tàu đó sẽ không hợp lệ: các ký tự "c" sẽ không nằm cạnh nhau.

Chắc chắn bạn đã nhận thấy đây không phải là một bài toán dễ giải đối với Yahya, vì vậy cậu ấy cần sự giúp đỡ của bạn! Hãy đi và giúp Yahya!

Lưu ý: các chữ cái chỉ được viết trên một mặt của toa tàu, vì vậy bạn không thể đảo ngược chúng. Ví dụ, nếu một toa tàu có chữ "ab" viết trên đó, nó không thể thay đổi thành "ba".

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. Dòng đầu tiên của mỗi bộ thử nghiệm chứa một số nguyên duy nhất \(N\), số lượng bộ toa tàu đã nối. Dòng tiếp theo chứa \(N\) chuỗi cách nhau bởi một khoảng trắng. Mỗi chuỗi đại diện cho một bộ toa tàu đã nối và chỉ bao gồm các chữ cái tiếng Anh viết thường.

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ố cách khác nhau để có được một đoàn tàu hợp lệ. Vì con số này có thể rất lớn, hãy xuất kết quả theo modulo 1,000,000,007.

Ràng buộc

  • \(1 \le T \le 100\).
  • \(1 \le\) Độ dài mỗi chuỗi toa tàu \(\le 100\).

Phân nhóm

  • Small dataset: \(1 \le N \le 10\).
  • Large dataset: \(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.

Phân nhóm Điểm Google Code Jam Tỷ lệ điểm của bài
Test Set 1 10/35 28,57%
Test Set 2 25/35 71,43%

Ví dụ

Ví dụ 1

Input 
3
3
ab bbbc cd
4
aa aa bc c
2
abc bcd
Output 
Case #1: 1
Case #2: 4
Case #3: 0
Note

Trong trường hợp đầu tiên, chỉ có một cách để tạo thành đoàn tàu hợp lệ bằng cách nối chuỗi "ab" với "bbbc" rồi đến "cd" theo thứ tự này.

Trong trường hợp thứ hai, có 4 cách khả thi. Lưu ý rằng có hai bộ toa tàu khác nhau được biểu diễn bởi chuỗi "aa", vì vậy có hai cách sắp xếp hai chuỗi này để nhóm chúng thành một bộ "aaaa". Ngoài ra, chỉ có một cách để sắp xếp bộ "bc" với "c" để thành "bcc". Sau đó, bạn có thể sắp xếp "aaaa" và "bcc" theo hai cách khác nhau. Tổng cộng có \(2 \times 2 = 4\) cách.

Trong trường hợp thứ ba, không có cách nào tạo thành đoàn tàu hợp lệ, vì nếu nối theo bất kỳ cách nào trong hai cách "abc"+"bcd" hoặc "bcd"+"abc", các chữ cái "b" và "c" sẽ không liên tiếp.

Nguồn

Google Code Jam 2014, Vòng 1C, bài Reordering Train Cars.

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