Google Code Jam 2017 - Round 3

Bạn muốn \(F\) người bạn của mình chia sẻ tin tức. Bạn biết rõ ai có thể nói chuyện với ai. Có \(P\) quan hệ một chiều, mỗi quan hệ là một cặp có thứ tự \((A_i,B_i)\), nghĩa là người bạn \(A_i\) có thể nói chuyện với người bạn \(B_i\). Điều này không có nghĩa \(B_i\) có thể nói chuyện với \(A_i\), mặc dù một cặp có thứ tự khác có thể cho phép chiều ngược lại.

Với mọi cặp có thứ tự \((A_i,B_i)\) hiện có, bạn muốn \(A_i\) chuyển một tin cho \(B_i\). Mỗi tin được biểu diễn bằng một số nguyên: giá trị tuyệt đối cho biết mức độ của tin, còn dấu cho biết đó là tin tốt hay tin xấu. Số nguyên này không được bằng \(0\) (nếu không thì chẳng có tin gì), và giá trị tuyệt đối không được lớn hơn \(F^2\) (nếu không thì tin quá sức kích động). Các quan hệ khác nhau có thể mang các giá trị khác nhau.

Vì quan tâm đến cảm xúc của bạn bè, với mỗi người, tổng giá trị của tất cả tin do người đó gửi phải bằng tổng giá trị của tất cả tin người đó nhận. Nếu một người không gửi tin nào thì tổng thứ nhất được coi là \(0\); nếu người đó không nhận tin nào thì tổng thứ hai cũng được coi là \(0\).

Hãy tìm một bộ giá trị tin thỏa tất cả các quy tắc trên, hoặc xác định rằng điều đó là không thể.

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 \(F\) và \(P\): số người bạn và số cặp có thứ tự khác nhau. Tiếp theo là \(P\) dòng; dòng thứ \(i\) chứa hai số nguyên khác nhau \(A_i\) và \(B_i\), biểu thị rằng \(A_i\) có thể nói chuyện với \(B_i\). Các người bạn được đánh số từ \(1\) đến \(F\).

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\).

Nếu không có cách gán thỏa mãn, y là IMPOSSIBLE. Nếu có, y gồm \(P\) số nguyên khác \(0\), mỗi số thuộc đoạn \([-F^2,F^2]\). Số thứ \(i\) ứng với cặp có thứ tự thứ \(i\) trong dữ liệu vào và là giá trị tin mà người thứ nhất gửi cho người thứ hai. Toàn bộ các giá trị phải thỏa điều kiện cân bằng trong đề bài.

Nếu có nhiều đáp án, có thể in bất kỳ đáp án hợp lệ nào.

Ràng buộc

• \(1\le T\le100\).
• \(1\le A_i\le F\) và \(1\le B_i\le F\) với mọi \(i\).
• \(A_i\ne B_i\) với mọi \(i\); một người không tự gửi tin cho chính mình.
• \((A_i,B_i)\ne(A_j,B_j)\) với mọi \(i\ne j\); không cặp có hướng nào bị lặp trong cùng một bộ test.

Phân nhóm

Test Set 1 (Visible): \(2\le F\le4\) và \(1\le P\le12\).

Test Set 2 (Hidden): \(2\le F\le1000\) và \(1\le P\le2000\).

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

Case #1: 1 1
Case #2: IMPOSSIBLE
Case #3: -1 -1 -1
Case #4: 4 -4 -4 8
Case #5: -1 1 1

Nguồn

Google Code Jam 2017, Vòng 3, bài Good News and Bad News.

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ác nhà hóa học nghiên cứu những nguyên tố trong bảng tuần hoàn, còn tại Code Jam, chúng tôi dùng máy nghiền số tiên tiến để nghiên cứu googlement. Một googlement là một chất có thể biểu diễn bằng chuỗi nhiều nhất chín chữ số. Googlement độ dài \(L\) chỉ được chứa các chữ số thập phân từ \(0\) đến \(L\), kể cả hai đầu, và phải có ít nhất một chữ số lớn hơn \(0\). Được phép có số \(0\) ở đầu. Chẳng hạn, 103 và 001 là googlement hợp lệ độ dài \(3\); 400 không hợp lệ vì chứa chữ số \(4\) lớn hơn độ dài \(3\), còn 000 không hợp lệ vì không có chữ số nào lớn hơn \(0\).

Mọi googlement hợp lệ có thể xuất hiện trên thế giới vào bất kỳ lúc nào, nhưng rồi sẽ phân rã tất định thành một googlement khác. Với googlement độ dài \(L\), hãy đếm số chữ số 1 trong nó (có thể bằng \(0\)) và ghi kết quả; tiếp tục đếm số chữ số 2 rồi ghi kết quả bên phải; cứ như vậy cho đến khi đếm và ghi số chữ số \(L\). Chuỗi mới tạo ra biểu diễn googlement mới và vẫn có độ dài \(L\). Thậm chí một googlement có thể phân rã thành chính nó.

Ví dụ, googlement 0414 vừa xuất hiện. Nó có một chữ số 1, không có 2, không có 3 và có hai chữ số 4, nên phân rã thành 1002. Chuỗi này có một 1, một 2, không có 3 và không có 4, nên phân rã thành 1100; sau đó lần lượt thành 2000, 0100, 1000, rồi 1000 tiếp tục phân rã thành chính nó mãi mãi.

Bạn vừa quan sát một googlement \(G\). Nó có thể vừa xuất hiện, hoặc có thể là kết quả của một hay nhiều bước phân rã. Hỏi tổng số googlement khác nhau có thể là trạng thái của nó khi mới xuất hiện trên thế giới.

Dữ liệu vào

Dòng đầu chứa số bộ test \(T\). Mỗi bộ test gồm một dòng chứa chuỗi \(G\), biểu diễn googlement quan sát được.

Dữ liệu ra

Với mỗi bộ test, in Case #x: y, trong đó x là số thứ tự bộ test, bắt đầu từ \(1\), và y là số googlement khác nhau mà googlement quan sát được có thể từng là khi mới xuất hiện.

Ràng buộc

• \(1\le T\le100\).
• Mỗi chữ số trong \(G\) nằm từ \(0\) đến \(|G|\), kể cả hai đầu.
• \(G\) chứa ít nhất một chữ số khác \(0\).

Phân nhóm

Test Set 1 (Visible): \(1\le|G|\le5\).

Test Set 2 (Hidden): \(1\le|G|\le9\).

Đ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
20
1
123

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

Nguồn

Google Code Jam 2017, Vòng 3, bài Googlements.

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 ở trên đỉnh Everest và muốn tận hưởng tất cả những đường mòn tuyệt đẹp nơi đây. Tuy nhiên, kinh nghiệm cho bạn biết rằng leo núi một mình rất nguy hiểm — bạn có thể lạc trong bóng tối. Vì vậy, bạn muốn đi vào những giờ đã định trước cùng hướng dẫn viên.

Trên núi có \(C\) trại, đánh số từ \(1\) đến \(C\), và có \(2C\) tour đi bộ đường dài một chiều, đánh số từ \(1\) đến \(2C\). Mỗi tour bắt đầu ở một trại, kết thúc ở một trại khác và không đi qua trại nào ở giữa. Everest thưa dân, công việc kinh doanh ế ẩm: có đúng hai tour khởi hành từ mỗi trại và đúng hai tour đến mỗi trại.

Mỗi tour chạy hằng ngày. Tour \(1\) và \(2\) xuất phát từ trại \(1\), tour \(3\) và \(4\) xuất phát từ trại \(2\), v.v.; tổng quát, tour \(2i-1\) và \(2i\) xuất phát từ trại \(i\). Tour thứ \(i\) kết thúc ở trại \(E_i\), khởi hành lúc giờ \(L_i\) và kéo dài đúng \(D_i\) giờ.

Hiện tại là giờ \(0\); các giờ trong ngày được đánh số từ \(0\) đến \(23\). Bạn đang ở trại \(1\) và muốn đi mỗi tour đúng một lần, cuối cùng trở lại trại \(1\). Không thể di chuyển giữa các trại bằng cách nào khác. Khi ở một trại, bạn có thể chờ bao nhiêu giờ tùy ý, kể cả \(0\), nhưng chỉ có thể bắt đầu tour đúng thời điểm nó khởi hành.

Sau khi xem lịch, bạn đã xác định chắc chắn có thể đạt mục tiêu, nhưng muốn hoàn thành nhanh nhất. Nếu chọn lộ trình tối ưu, bạn cần bao nhiêu giờ để đi hết mọi tour?

Dữ liệu vào

Dòng đầu chứa số bộ test \(T\). Mỗi bộ test bắt đầu bằng số nguyên \(C\), số trại. Tiếp theo là \(2C\) dòng. Dòng thứ \(i\), đánh số từ \(1\), mô tả tour xuất phát từ trại \(\lfloor(i+1)/2\rfloor\) và chứa ba số nguyên \(E_i,L_i,D_i\) như trên. Định dạng này bảo đảm đúng hai tour xuất phát từ mỗi trại.

Dữ liệu ra

Với mỗi bộ test, in Case #x: y, trong đó x là số thứ tự bộ test, bắt đầu từ \(1\), và y là số giờ nhỏ nhất để đạt mục tiêu.

Ràng buộc

• \(1\le T\le100\).
• \(1\le E_i\le C\).
• \(E_i\ne\lceil i/2\rceil\) với mọi \(i\); không tour nào bắt đầu và kết thúc cùng một trại.
• Với mỗi trại \(i\), có đúng hai chỉ số \(j\) sao cho \(E_j=i\); đúng hai tour kết thúc tại mỗi trại.
• \(0\le L_i\le23\).
• \(1\le D_i\le1000\).
• Tồn tại ít nhất một lộ trình bắt đầu và kết thúc tại trại \(1\), dùng mỗi tour đúng một lần.

Phân nhóm

Test Set 1 (Visible): \(2\le C\le15\).

Test Set 2 (Hidden): \(2\le C\le1000\).

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

Case #1: 32
Case #2: 192

Nguồn

Google Code Jam 2017, Vòng 3, bài Mountain Tour.

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

Phòng tranh danh giá Slate Modern chuyên về trào lưu nghệ thuật mới nhất: tranh thang xám tuân theo những quy tắc rất nghiêm ngặt. Mỗi bức tranh phải là một lưới \(R\) hàng và \(C\) cột. Mỗi ô được tô bằng một màu có độ sáng là số nguyên dương. Để bức tranh không quá chói mắt, độ sáng của hai ô chung một cạnh — không chỉ chung góc — không được chênh nhau quá \(D\).

Người bạn họa sĩ Cody-Jamal đang vẽ một bức tranh cho phòng tranh. Đêm qua, anh ấy có cảm hứng và tô sẵn \(N\) ô phân biệt bằng những độ sáng nguyên dương nhất định. Hôm nay bạn mới kể cho anh ấy về quy tắc của phòng tranh; giờ anh ấy muốn biết có thể điền độ sáng nguyên dương vào mọi ô còn lại để hoàn thành tranh mà không vi phạm quy tắc hay không. Nếu có thể, anh ấy muốn tổng độ sáng lớn nhất có thể để tiết kiệm sơn đen. Hãy tìm tổng đó hoặc xác định rằng công việc là không thể. Vì kết quả có thể rất lớn, chỉ cần in phần dư khi chia cho số nguyên tố \(10^9+7=1000000007\).

Dữ liệu vào

Dòng đầu chứa số bộ test \(T\). Mỗi bộ test bắt đầu bằng bốn số nguyên \(R,C,N,D\). Tiếp theo là \(N\) dòng; dòng thứ \(i\) chứa \(R_i,C_i,B_i\), cho biết ô ở hàng \(R_i\), cột \(C_i\) có độ sáng \(B_i\). Hàng và cột được đánh số từ \(1\).

Dữ liệu ra

Với mỗi bộ test, in Case #x: y, trong đó x là số thứ tự bộ test, bắt đầu từ \(1\). Nếu không thể hoàn thành tranh thì y là IMPOSSIBLE; nếu có thể thì y là tổng độ sáng lớn nhất có thể, lấy modulo \(1000000007\).

Ràng buộc

• \(1\le T\le100\).
• \(1\le N\le200\).
• \(1\le D\le10^9\).
• \(1\le R_i\le R\) và \(1\le C_i\le C\) với mọi \(i\).
• \(1\le B_i\le10^9\) với mọi \(i\). Cận trên này chỉ áp dụng cho các ô Cody-Jamal đã tô; các ô khác có thể nhận độ sáng lớn hơn \(10^9\).
• \(N<RC\); có ít nhất một ô trống.
• Với mọi \(i\ne j\), \(R_i\ne R_j\) hoặc \(C_i\ne C_j\); mọi ô cho trước đều phân biệt.

Phân nhóm

Test Set 1 (Visible): \(1\le R,C\le200\).

Test Set 2 (Hidden): \(1\le R,C\le10^9\).

Đ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 3 2 2
2 1 4
1 2 7
1 2 1 1000000000
1 2 1000000000
3 1 2 100
1 1 1
3 1 202
2 2 2 2
2 1 1
2 2 4

Case #1: 40
Case #2: 999999986
Case #3: IMPOSSIBLE
Case #4: IMPOSSIBLE

6 7 9
4 6 8

Nguồn

Google Code Jam 2017, Vòng 3, bài Slate Modern.

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