Google Code Jam 2015 - Round 2

Cha mẹ Elliot nói tiếng Pháp và tiếng Anh với cậu ở nhà. Cậu đã nghe rất nhiều từ, nhưng không phải lúc nào cũng rõ từ nào thuộc ngôn ngữ nào!

Elliot biết một câu chắc chắn là tiếng Anh, một câu chắc chắn là tiếng Pháp, và một số câu khác có thể là tiếng Anh hoặc tiếng Pháp. Nếu một từ xuất hiện trong một câu tiếng Anh, nó phải là một từ tiếng Anh. Nếu một từ xuất hiện trong một câu tiếng Pháp, nó phải là một từ tiếng Pháp.

Xét tất cả những câu Elliot đã nghe, số từ ít nhất bắt buộc phải thuộc cả tiếng Anh lẫn tiếng Pháp là bao nhiêu?

Dữ liệu vào

Dòng đầu chứa số bộ test \(T\). Mỗi bộ test bắt đầu bằng một dòng chứa số nguyên \(N\), sau đó là \(N\) dòng, mỗi dòng gồm một dãy "từ" cách nhau bởi dấu cách. Mỗi "từ" chỉ gồm các chữ thường a đến z.

Dòng đầu trong \(N\) dòng là một "câu" tiếng Anh, dòng thứ hai là một "câu" tiếng Pháp. Các dòng còn lại có thể là "câu" thuộc một trong hai ngôn ngữ. (Các "từ" và "câu" không được bảo đảm là hợp lệ trong bất kỳ ngôn ngữ thật nào.)

Dữ liệu ra

Với mỗi bộ test, in một dòng Case #x: y, trong đó \(x\) là số thứ tự bộ test (bắt đầu từ 1) và \(y\) là số từ ít nhất mà Elliot đã nghe và bắt buộc phải thuộc cả tiếng Anh lẫn tiếng Pháp.

Ràng buộc

• \(1 \le T \le 25\).
• Mỗi từ dài không quá 10 ký tự.
• Hai câu "đã biết" chứa không quá 1000 từ mỗi câu.
• Mỗi câu "chưa biết" chứa không quá 10 từ.

Phân nhóm

• Test Set 1 (Nhỏ): \(2 \le N \le 20\).
• Test Set 2 (Lớn): \(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
he loves to eat baguettes
il aime manger des baguettes
4
a b c d e
f g h i j
a b c i j
f g h d e
4
he drove into a cul de sac
elle a conduit sa voiture
il a conduit dans un cul de sac
il mange pendant que il conduit sa voiture
6
adieu joie de vivre je ne regrette rien
adieu joie de vivre je ne regrette rien
a b c d e
f g h i j
a b c i j
f g h d e

    ???+ success "Output"

        ```sample
Case #1: 1
Case #2: 4
Case #3: 3
Case #4: 8

??? "Giải thích"

    Trong Case #1, Elliot biết chắc câu đầu là tiếng Anh và câu thứ hai là tiếng Pháp nên không có gì mơ hồ; từ duy nhất bắt buộc thuộc cả hai ngôn ngữ là `baguettes`.

    Trong Case #2, hai câu cuối có thể lần lượt là: Anh-Anh, Anh-Pháp, Pháp-Anh, hoặc Pháp-Pháp. Khả năng thứ hai làm số từ chung của hai ngôn ngữ nhỏ nhất; tập đó là `d`, `e`, `i`, và `j`.

Nguồn

Google Code Jam 2015, Vòng 2, bài Bilingual.

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 là tay trống của ban nhạc rock Denise and the Integers. Chiếc trống là một hình trụ được quấn quanh bởi một lưới ô chữ nhật.

Ban nhạc sắp biểu diễn ở Mathland. Khán giả Mathland rất khó tính và đòi hỏi mỗi ô trên trống chứa một số nguyên dương; không được dùng số 0 hay số âm. Hơn nữa, mỗi số nguyên \(K\) phải kề cạnh (chung một cạnh, không chỉ chung một điểm) với đúng \(K\) ô khác cũng chứa số \(K\): ô chứa 1 phải chạm đúng một ô khác chứa 1, ô chứa 2 phải chạm đúng hai ô khác chứa 2, v.v. Ngoài điều kiện đó, một ô chạm các ô mang giá trị khác như thế nào không quan trọng.

Hai mặt tròn trên và dưới của trống không được tính là ô và không cần trang trí. Vì vậy, mỗi ô ở hàng trên cùng và dưới cùng chỉ chạm ba ô khác, còn tất cả ô ở giữa chạm bốn ô.

Ví dụ, đây là một cách trang trí hợp lệ cho hình trụ tạo bởi lưới 3 hàng, 5 cột:

https://cdn.lqdoj.edu.vn/media/pagedown-uploads/pd_1_ff258d7f.png

(Hãy hình dung hai cột khuất ở mặt sau của trống giống với ba cột đang nhìn thấy.)

Bạn muốn biết có bao nhiêu cách trang trí hợp lệ khác nhau. Hai cách trang trí là khác nhau nếu không thể xoay một cách quanh trục đối xứng của hình trụ để tạo ra cách kia. Mặt trên và mặt dưới của trống được coi là khác nhau, nên cách trang trí lưới \(3\times5\) dưới đây khác với cách phía trên:

https://cdn.lqdoj.edu.vn/media/pagedown-uploads/pd_1_c4cf1ac1.png

(Một lần nữa, hãy hình dung hai cột khuất ở mặt sau giống với ba cột đang nhìn thấy.)

Trống có \(R\) hàng và \(C\) cột. Có bao nhiêu cách trang trí hợp lệ khác nhau? Kết quả có thể rất lớn, hãy trả về số cách modulo \(10^9+7\) (1000000007).

Dữ liệu vào

Dòng đầu chứa số bộ test \(T\). Mỗi bộ test là một dòng chứa hai số nguyên \(R\) và \(C\), lần lượt là số hàng và số cột của trống.

Dữ liệu ra

Với mỗi bộ test, in một dòng Case #x: y, trong đó \(x\) là số thứ tự bộ test (bắt đầu từ 1) và \(y\) là số cách trang trí hợp lệ modulo \(10^9+7\).

Ràng buộc

• Các ô chỉ được chứa số nguyên dương và phải thỏa điều kiện kề cạnh đã nêu.

Phân nhóm

• Test Set 1 (Nhỏ): \(1 \le T \le 20\), \(2 \le R \le 6\), \(3 \le C \le 6\).
• Test Set 2 (Lớn): \(1 \le T \le 100\), \(2 \le R \le 100\), \(3 \le C \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ụ

2
2 4
3 5

    ???+ success "Output"

        ```sample
Case #1: 1
Case #2: 2

??? "Giải thích"

    Trong Case #1, lời giải duy nhất là điền số 3 vào tất cả các ô.

    Trong Case #2, hai lời giải duy nhất chính là hai cách được minh họa trong đề bài.

Nguồn

Google Code Jam 2015, Vòng 2, bài Drum Decorator.

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ể bơi trẻ em là một chiếc bể lớn có thể chứa nước để trẻ nhỏ vui chơi.

Bạn có \(N\) nguồn nước khác nhau. Nguồn thứ \(i\) cung cấp nước với lưu lượng \(R_i\) và nhiệt độ \(C_i\). Ban đầu, tất cả nguồn nước đều tắt. Mỗi nguồn chỉ có thể được bật một lần và tắt một lần; thao tác bật hoặc tắt không tốn thêm thời gian. Nhiều nguồn có thể hoạt động đồng thời.

Bể có thể chứa vô hạn nước, nhưng bạn muốn đổ vào bể chính xác thể tích \(V\) với nhiệt độ chính xác \(X\) trong thời gian ngắn nhất. Nếu bật và tắt các nguồn một cách tối ưu (không nhất thiết phải dùng mọi nguồn), cần ít nhất bao nhiêu giây?

Trong bài này, khi trộn tức thời lượng nước có thể tích \(V_0\), nhiệt độ \(X_0\) với lượng nước có thể tích \(V_1\), nhiệt độ \(X_1\), ta thu được thể tích \(V_0+V_1\) và nhiệt độ

Ví dụ, trộn 5 lít nước ở 10 độ với 10 lít nước ở 40 độ sẽ cho 15 lít nước ở 30 độ. Cũng giả sử rằng nước không tự nóng lên hay nguội đi theo thời gian, trừ khi được trộn với nước khác.

Dữ liệu vào

Dòng đầu chứa số bộ test \(T\). Mỗi bộ test bắt đầu bằng ba số cách nhau bởi dấu cách: số nguyên \(N\) và hai số thực \(V\), \(X\) như mô tả ở trên.

\(N\) dòng tiếp theo, mỗi dòng chứa hai số thực \(R_i\) và \(C_i\), lần lượt là lưu lượng và nhiệt độ của nguồn thứ \(i\). Thể tích được tính bằng lít, lưu lượng tính bằng lít mỗi giây và nhiệt độ tính bằng độ C.

Mọi số thực đều được biểu diễn chính xác với bốn chữ số sau dấu thập phân.

Dữ liệu ra

Với mỗi bộ test, in một dòng Case #x: y, trong đó \(x\) là số thứ tự bộ test (bắt đầu từ 1), còn \(y\) là số giây nhỏ nhất cần để đổ vào bể đúng thể tích và nhiệt độ yêu cầu. Nếu không thể thực hiện với dữ liệu đã cho, \(y\) phải là chuỗi IMPOSSIBLE.

\(y\) được coi là đúng nếu sai số tuyệt đối hoặc tương đối so với đáp án đúng không vượt quá \(10^{-6}\). Dấu chấm . được dùng làm dấu thập phân.

Ràng buộc

• \(1\le T\le100\).
• \(0.1\le X\le99.9\).
• \(0.1\le C_i\le99.9\).

Phân nhóm

• Tập nhỏ: \(1\le N\le2\); \(0.0001\le V\le100.0\); \(0.0001\le R_i\le100.0\).
• Tập lớn: \(1\le N\le100\); \(0.0001\le V\le10000.0\); \(0.0001\le R_i\le10000.0\).

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

6
1 10.0000 50.0000
0.2000 50.0000
2 30.0000 65.4321
0.0001 50.0000
100.0000 99.9000
2 5.0000 99.9000
30.0000 99.8999
20.0000 99.7000
2 0.0001 77.2831
0.0001 97.3911
0.0001 57.1751
2 100.0000 75.6127
70.0263 75.6127
27.0364 27.7990
4 5000.0000 75.0000
10.0000 30.0000
20.0000 50.0000
300.0000 95.0000
40.0000 2.0000

Case #1: 50.0000000
Case #2: 207221.843687375
Case #3: IMPOSSIBLE
Case #4: 0.500000000
Case #5: 1.428034895
Case #6: 18.975332068

Nguồn

Google Code Jam 2015, Vòng 2, bài Kiddie Pool.

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

Khi sử dụng Google Street View, có lẽ bạn từng nhấc nhân vật Pegman lên rồi thả xuống. Hôm nay, một người dùng tinh nghịch sẽ đặt Pegman vào một ô nào đó của lưới chữ nhật gồm các ô vuông đơn vị, có \(R\) hàng và \(C\) cột. Mỗi ô có thể trống hoặc mang một mũi tên chỉ theo một trong bốn hướng: lên, phải, xuống hoặc trái.

Khi Pegman được đặt vào một ô, nếu ô đó trống thì anh ấy đứng yên mãi mãi. Nếu ô có mũi tên, Pegman bắt đầu đi theo hướng mũi tên. Trong lúc đi, khi gặp một ô trống, anh ấy tiếp tục đi theo hướng hiện tại; khi gặp một mũi tên khác, anh ấy đổi sang hướng của mũi tên đó rồi tiếp tục đi.

Pegman có thể vui vẻ đi vòng quanh lưới mãi mãi, nhưng cũng có thể bước ra ngoài biên lưới. Bạn có thể ngăn điều đó và cứu anh ấy bằng cách đổi hướng của một hoặc nhiều mũi tên. Mỗi mũi tên chỉ được đổi sang một trong ba hướng còn lại; chỉ được đổi hướng, không được thêm hoặc xóa mũi tên.

Hãy tìm số mũi tên ít nhất cần đổi để bảo đảm Pegman không rời khỏi lưới, bất kể ban đầu anh ấy được đặt ở đâu.

Dữ liệu vào

Dòng đầu chứa số bộ test \(T\). Mỗi bộ test bắt đầu bằng hai số nguyên \(R\), \(C\) cách nhau bởi dấu cách. Sau đó là \(R\) dòng, mỗi dòng có \(C\) ký tự mô tả các ô:

• .: ô không có mũi tên;
• ^: mũi tên lên;
• >: mũi tên sang phải;
• v: mũi tên xuống;
• <: mũi tên sang trái.

Dữ liệu ra

Với mỗi bộ test, in một dòng Case #x: y, trong đó \(x\) là số thứ tự bộ test (bắt đầu từ 1), còn \(y\) là số mũi tên ít nhất phải đổi để Pegman không rời lưới, bất kể vị trí ban đầu. Nếu không thể bảo đảm điều đó dù đổi bao nhiêu mũi tên, in IMPOSSIBLE.

Ràng buộc

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

Phân nhóm

• Tập nhỏ: \(1\le R,C\le4\).
• Tập lớn: \(1\le R,C\le100\).

Đ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 1
^
^
2 2
>v
^<
3 3
...
.^.
...
1 1
.

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

Nguồn

Google Code Jam 2015, Vòng 2, bài Pegman.

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