Google Code Jam 2016 - Round 1A

Bạn là giáo viên tại trường mẫu giáo Little Coders mới mở. Lớp có \(N\) em, mỗi em có một mã học sinh khác nhau từ 1 đến \(N\). Mỗi em có đúng một người bạn thân nhất (BFF), và bạn biết BFF của từng em. Quan hệ này không nhất thiết hai chiều: B là BFF của A không có nghĩa A là BFF của B.

Kế hoạch bài học ngày mai có một hoạt động mà người tham gia phải ngồi thành vòng tròn. Bạn muốn tạo vòng tròn lớn nhất có thể sao cho mỗi em ngồi ngay cạnh BFF của mình, ở bên trái hoặc bên phải. Những em không ở trong vòng sẽ chỉ quan sát.

Số trẻ lớn nhất có thể ngồi trong vòng là bao nhiêu?

Dữ liệu vào

Dòng đầu chứa \(T\). Mỗi bộ test gồm hai dòng. Dòng đầu là \(N\), tổng số trẻ. Dòng thứ hai chứa \(N\) số \(F_1,F_2,\ldots,F_N\), trong đó \(F_i\) là mã học sinh của BFF của em có mã \(i\).

Dữ liệu ra

Với mỗi bộ test, in Case #x: y, với \(x\) bắt đầu từ 1 và \(y\) là số trẻ lớn nhất có thể xếp thành vòng sao cho mỗi em ngồi cạnh BFF của mình.

Ràng buộc

• \(1\le T\le100\).
• \(1\le F_i\le N\) với mọi \(i\).
• \(F_i\ne i\) với mọi \(i\) (không ai là BFF của chính mình).

Phân nhóm

• Test Set 1 (Visible): \(3\le N\le10\).
• Test Set 2 (Hidden): \(3\le N\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ụ

4
4
2 3 4 1
4
3 3 4 1
4
3 3 4 3
10
7 8 10 10 9 2 9 6 3 3

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

Nguồn

Google Code Jam 2016, Vòng 1A, bài BFFs.

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 quân đội của Trung sĩ Argus tập hợp để luyện tập, họ đứng thành lưới vuông \(N\times N\), mỗi ô đúng một binh sĩ. Mỗi người có một chiều cao.

Argus muốn luôn quan sát được mọi binh sĩ. Vì thích nhìn lưới từ góc trên trái, ông yêu cầu:

• trong mỗi hàng, chiều cao tăng nghiêm ngặt từ trái sang phải;
• trong mỗi cột, chiều cao tăng nghiêm ngặt từ trên xuống dưới.

Hai binh sĩ trong cùng hàng hoặc cột không thể cao bằng nhau, nhưng nhiều binh sĩ ở các vị trí khác trong lưới vẫn có thể cùng chiều cao.

Vì đôi lúc binh sĩ luyện riêng theo hàng hoặc cột, Argus yêu cầu báo cáo gồm \(2N\) danh sách chiều cao: mỗi hàng theo thứ tự trái sang phải và mỗi cột theo thứ tự trên xuống dưới. Bạn ghi từng danh sách lên một mảnh giấy riêng. Trên đường về văn phòng, tiếng kèn lớn làm bạn giật mình đánh rơi giấy; gió cuốn mất một mảnh trước khi bạn nhặt lại. Các mảnh còn lại không theo thứ tự, và bạn cũng quên mảnh nào là hàng hay cột vì không ghi chú.

Argus sẽ bắt bạn chống đẩy hàng trăm lần nếu báo cáo thiếu. Hãy tìm danh sách bị mất.

Dữ liệu vào

Dòng đầu chứa \(T\). Mỗi bộ test gồm một dòng chứa \(N\), sau đó là \(2N-1\) dòng, mỗi dòng có \(N\) số nguyên biểu diễn các danh sách còn lại. Bảo đảm chúng là tất cả trừ một hàng hoặc cột của một lưới hợp lệ như mô tả.

Dữ liệu ra

Với mỗi bộ test, in Case #x: y, trong đó \(x\) bắt đầu từ 1 và \(y\) là \(N\) số nguyên tăng nghiêm ngặt của danh sách bị thiếu.

Ràng buộc

• \(1\le T\le50\).
• Mọi chiều cao nằm trong \([1,2500]\).
• Các số trên mỗi dòng tăng nghiêm ngặt.
• Bảo đảm tồn tại duy nhất một đáp án hợp lệ.

Phân nhóm

• Test Set 1 (Visible): \(2\le N\le10\).
• Test Set 2 (Hidden): \(2\le N\le50\).

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

1
3
1 2 3
2 3 5
3 5 6
2 3 4
1 2 3

Case #1: 3 4 6

1 2 3
2 3 4
3 5 6

1 2 3
2 3 5
3 4 6

Nguồn

Google Code Jam 2016, Vòng 1A, bài Rank and File.

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

Trong trò chơi truyền hình The Last Word, người dẫn bắt đầu một lượt bằng cách cho thí sinh xem chuỗi \(S\) gồm các chữ cái tiếng Anh in hoa. Thí sinh có một bảng trắng ban đầu trống. Người dẫn lần lượt đưa các chữ của \(S\) theo đúng thứ tự. Với chữ đầu tiên, thí sinh viết nó lên bảng; đây được tính là từ đầu tiên dù chỉ dài một chữ. Sau đó, với mỗi chữ mới, thí sinh phải viết nó vào đầu hoặc cuối từ hiện có trước khi nhận chữ tiếp theo (hoặc kết thúc trò chơi).

Ví dụ \(S=\) CAB. Sau khi viết C, có bốn chuỗi lựa chọn:

• đặt A trước C thành AC, rồi B trước AC thành BAC;
• đặt A trước C thành AC, rồi B sau AC thành ACB;
• đặt A sau C thành CA, rồi B trước CA thành BCA;
• đặt A sau C thành CA, rồi B sau CA thành CAB.

Từ sau khi dùng hết các chữ của \(S\) được gọi là last word. Thí sinh thắng nếu từ của mình đứng cuối theo thứ tự bảng chữ cái trong tất cả các last word có thể tạo. Với ví dụ trên, từ thắng là CAB, tình cờ giống chuỗi gốc. Với \(S=\) JAM, từ thắng là MJA.

Bạn là thí sinh tiếp theo và vừa được xem \(S\). Hãy tạo last word chiến thắng.

Dữ liệu vào

Dòng đầu chứa \(T\). Mỗi bộ test gồm một dòng chứa chuỗi \(S\).

Dữ liệu ra

Với mỗi bộ test, in Case #x: y, trong đó \(x\) bắt đầu từ 1 và \(y\) là last word chiến thắng.

Ràng buộc

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

Phân nhóm

• Test Set 1 (Visible): \(1\le |S|\le15\).
• Test Set 2 (Hidden): \(1\le |S|\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ụ

7
CAB
JAM
CODE
ABAAB
CABCBBABC
ABCABCABC
ZXCASDQWE

Case #1: CAB
Case #2: MJA
Case #3: OCDE
Case #4: BBAAA
Case #5: CCCABBBAB
Case #6: CCCBAABAB
Case #7: ZXCASDQWE

Nguồn

Google Code Jam 2016, Vòng 1A, bài The Last Word.

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