Năm ngoái, một liên minh nghiên cứu đã gặp một số rắc rối với một hệ cơ sở dữ liệu phân tán đôi khi làm mất một phần dữ liệu. Bạn không cần đọc hay hiểu bài toán đó để giải bài này!

Liên minh nhận thấy các hệ thống phân tán quá phức tạp, nên họ lưu \(B\) bit thông tin quan trọng trong một mảng duy nhất trên một cỗ máy tuyệt vời. Để tăng thêm một lớp bảo mật, họ khiến việc lấy thông tin thật nhanh trở nên khó khăn: người dùng phải truy vấn một vị trí bit từ \(1\) đến \(B\), rồi mới nhận được bit tại vị trí đó trong mảng đang lưu.

Đáng tiếc, cỗ máy siêu hiện đại này chịu ảnh hưởng của các dao động lượng tử ngẫu nhiên! Cụ thể, sau khi gửi mỗi truy vấn thứ \(1, 11, 21, 31, \ldots\), nhưng trước khi nhận được phản hồi, dao động lượng tử gây ra đúng một trong bốn hiệu ứng sau, mỗi hiệu ứng có xác suất như nhau:

• Với xác suất \(25\%\), mảng bị bù bit: mọi 0 trở thành 1 và ngược lại.
• Với xác suất \(25\%\), mảng bị đảo ngược thứ tự: bit đầu đổi chỗ với bit cuối, bit thứ hai đổi chỗ với bit áp chót, v.v.
• Với xác suất \(25\%\), cả hai thao tác trên (bù bit và đảo ngược thứ tự) cùng xảy ra. (Lưu ý rằng thứ tự thực hiện hai thao tác không quan trọng.)
• Với xác suất \(25\%\), mảng không thay đổi.

Ngoài ra, mỗi lần dao động xảy ra, không có bất kỳ dấu hiệu nào cho biết hiệu ứng nào đã được áp dụng. Liên minh bắt đầu lo lắng và thuê bạn lấy lại dữ liệu quý giá của họ, bất kể hiện giờ nó đang ở dạng nào! Bạn có thể tìm toàn bộ mảng sao cho câu trả lời chính xác tại đúng thời điểm bạn đưa ra câu trả lời không? Việc trả lời không được tính là một truy vấn. Chẳng hạn, nếu trả lời sau truy vấn thứ \(30\), mảng vẫn ở cùng trạng thái như trong khoảng từ sau truy vấn thứ \(21\) đến hết truy vấn thứ \(30\).

Dữ liệu vào

Nội dung vào được cung cấp theo giao thức mô tả dưới đây.

Dữ liệu ra

Đây là bài toán tương tác. Hãy chắc chắn rằng bạn đã đọc phần Bài toán tương tác trong FAQ.

Ban đầu, chương trình phải đọc một dòng chứa hai số nguyên \(T\) và \(B\), lần lượt là số lượng bộ test và số bit trong mảng. Lưu ý rằng \(B\) giống nhau ở mọi bộ test.

Sau đó, bạn cần xử lý \(T\) bộ test. Trong mỗi bộ test, bộ chấm khởi tạo một mảng \(B\) bit đã được xác định trước; mảng này có thể khác nhau giữa các bộ test và không nhất thiết được chọn ngẫu nhiên. Tiếp theo, bạn được thực hiện tối đa \(150\) truy vấn theo dạng sau:

• Chương trình in một dòng chứa một số nguyên \(P\) trong đoạn từ \(1\) đến \(B\) (kể cả hai đầu), cho biết vị trí trong mảng mà bạn muốn xem.
• Nếu số thứ tự của truy vấn vừa gửi có chữ số tận cùng là \(1\), bộ chấm chọn ngẫu nhiên đều và độc lập với mọi lần chọn khác một trong bốn khả năng đã mô tả ở trên (bù bit, đảo ngược thứ tự, vừa bù bit vừa đảo ngược thứ tự, hoặc không làm gì), rồi biến đổi mảng đang lưu tương ứng. (Lưu ý rằng điều này xảy ra ngay ở truy vấn đầu tiên.)
• Bộ chấm trả lời bằng một dòng chứa một ký tự 0 hoặc 1, là giá trị hiện được lưu tại vị trí bit \(P\); hoặc trả lời N nếu bạn in một dòng sai định dạng (ví dụ, một vị trí không hợp lệ).

Sau khi thực hiện bao nhiêu truy vấn tùy ý trong giới hạn \(150\) truy vấn trên, bạn phải thực hiện thêm một lượt trao đổi như sau:

• Chương trình in một dòng chứa chuỗi gồm \(B\) ký tự, mỗi ký tự là 0 hoặc 1, biểu diễn các bit hiện đang được lưu trong mảng (chúng không nhất thiết trùng với các bit ban đầu!).
• Bộ chấm trả lời bằng một dòng chứa đúng một chữ cái: Y viết hoa nếu câu trả lời đúng, và N viết hoa nếu câu trả lời sai (hoặc nếu bạn in một dòng sai định dạng). Nếu nhận được Y, hãy bắt đầu bộ test tiếp theo, hoặc ngừng gửi dữ liệu nếu không còn bộ test nào.

Sau khi gửi N vào luồng nhập của chương trình, bộ chấm sẽ không gửi thêm bất kỳ dữ liệu nào. Nếu chương trình tiếp tục chờ bộ chấm sau khi nhận N, chương trình sẽ hết thời gian và nhận kết quả Time Limit Exceeded. Bạn có trách nhiệm cho chương trình thoát kịp thời để nhận kết quả Wrong Answer thay vì Time Limit Exceeded. Tương tự như thường lệ, nếu vượt giới hạn bộ nhớ hoặc gặp lỗi thực thi, chương trình sẽ nhận kết quả tương ứng.

Ràng buộc

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

Phân nhóm

Test Set 1 (hiển thị kết quả)

\(B = 10\).

Test Set 2 (hiển thị kết quả)

\(B = 20\).

Test Set 3 (ẩn kết quả)

\(B = 100\).

Giao thức tương tác

Chương trình phải tuân thủ đầy đủ thứ tự đọc, ghi, phản hồi lỗi và yêu cầu flush được mô tả trong phần dữ liệu vào/ra và công cụ kiểm thử bên dưới.

Công cụ kiểm thử

Bạn có thể dùng công cụ kiểm thử này để kiểm thử cục bộ hoặc trên hệ thống của ban tổ chức. Để kiểm thử cục bộ, bạn cần chạy công cụ song song với chương trình của mình; có thể dùng trình chạy tương tác cho việc đó. Trình chạy tương tác đã được thay đổi sau kỳ thi năm 2019; hãy chắc chắn tải phiên bản mới nhất. Để biết thêm thông tin, hãy đọc hướng dẫn trong phần chú thích của tệp đó và tham khảo phần Bài toán tương tác trong FAQ.

Hướng dẫn sử dụng công cụ kiểm thử nằm trong các dòng chú thích bên trong công cụ. Bạn nên tự bổ sung các bộ test của riêng mình. Xin lưu ý rằng dù công cụ này được thiết kế để mô phỏng hệ thống chấm, nó KHÔNG PHẢI hệ thống chấm thật và có thể hoạt động khác. Nếu chương trình vượt qua công cụ kiểm thử nhưng thất bại trên bộ chấm thật, hãy kiểm tra phần Coding trong FAQ để bảo đảm bạn đang dùng cùng trình biên dịch với ban tổ chức.

Ví dụ

t, b = readline_int_list()      // đọc 100 vào t và 10 vào b.
// Bộ chấm bắt đầu với mảng đã định trước cho bộ test này:
// 0001101111. (Test Set 1 thật không nhất thiết dùng mảng này.)
printline 1 to stdout           // ta hỏi vị trí 1.
flush stdout
// Đây là truy vấn thứ 1, nên bộ chấm bí mật chọn ngẫu nhiên một trong
// bốn hiệu ứng. Lần này nó chọn bù bit + đảo ngược thứ tự, vì vậy
// giá trị đang lưu trở thành 0000100111.
r = readline_chr()              // đọc 0.
printline 6 to stdout           // ta hỏi vị trí 6.
flush stdout
// Đây là truy vấn thứ 2, nên không có dao động lượng tử.
r = readline_chr()              // đọc 0.
...
// Các truy vấn từ thứ ba đến thứ mười được lược bỏ trong ví dụ này.
...
printline 1 to stdout           // ta quyết định hỏi lại vị trí 1.
flush stdout
// Đây là truy vấn thứ 11, nên bộ chấm bí mật chọn một hiệu ứng; lần này
// nó đảo ngược thứ tự, vì vậy giá trị đang lưu trở thành 1110010000.
r = readline_chr()              // đọc 1.
printline 1110110000 to stdout  // ta thử trả lời. tại sao chứ?!?!
flush stdout
ok = readline_chr()             // đọc N -- ta đã mắc lỗi!
exit                            // thoát để tránh lỗi TLE không rõ nguyên nhân

Nguồn

Google Code Jam 2020, Vòng loại, bài ESAb ATAd.

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

Indicium trong tiếng Latinh có nghĩa là "vết" (trace). Trong bài này, chúng ta làm việc với các hình vuông Latinh và vết của ma trận.

Một hình vuông Latinh là ma trận vuông \(N\times N\), trong đó mỗi ô chứa một trong \(N\) giá trị khác nhau và không giá trị nào lặp lại trong cùng một hàng hoặc cột. Bài này chỉ xét các "hình vuông Latinh tự nhiên", tức là \(N\) giá trị được dùng là các số nguyên từ \(1\) đến \(N\).

Vết của ma trận vuông là tổng các giá trị trên đường chéo chính (từ góc trên bên trái đến góc dưới bên phải).

Cho \(N\) và \(K\), hãy tạo một hình vuông Latinh tự nhiên \(N\times N\) có vết \(K\), hoặc cho biết điều đó là không thể. Ví dụ, dưới đây là hai đáp án có thể có với \(N=3\), \(K=6\); các giá trị góp vào vết được in đậm.

**2** 1 3     **3** 1 2
3 **2** 1     1 **2** 3
1 3 **2**     2 3 **1**

Dữ liệu vào

Dòng đầu chứa số bộ test \(T\). Tiếp theo là \(T\) bộ test, mỗi bộ gồm một dòng chứa hai số nguyên \(N\) và \(K\): kích thước ma trận và vết mong muốn.

Dữ liệu ra

Với mỗi bộ test, in một dòng dạng Case #x: y, trong đó x là số thứ tự bộ test (bắt đầu từ \(1\)), còn y là IMPOSSIBLE nếu không có đáp án hoặc POSSIBLE nếu có. Trong trường hợp thứ hai, in thêm \(N\) dòng, mỗi dòng gồm \(N\) số nguyên, biểu diễn một hình vuông Latinh tự nhiên hợp lệ có vết \(K\).

Ràng buộc

• \(N \le K \le N^2\).

Phân nhóm

• Test Set 1 (phán quyết hiển thị): \(T=44\); \(2 \le N \le 5\).
• Test Set 2 (phán quyết ẩn): \(1 \le T \le 100\); \(2 \le N \le 50\).

Đ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
3 6
2 3

Case #1: POSSIBLE
2 1 3
3 2 1
1 3 2
Case #2: IMPOSSIBLE

1 2     2 1
2 1     1 2

Nguồn

Google Code Jam 2020, Vòng loại, bài Indicium.

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ài

Tóm tắt: Cho một chuỗi chữ số S, hãy chèn vào đó số lượng dấu ngoặc mở và dấu ngoặc đóng ít nhất sao cho chuỗi thu được cân bằng và mỗi chữ số \(d\) nằm bên trong đúng \(d\) cặp ngoặc khớp nhau.

Ta gọi phần lồng nhau của hai dấu ngoặc trong một chuỗi là chuỗi con nằm hoàn toàn giữa chúng. Một dấu ngoặc mở và một dấu ngoặc đóng nằm bên phải nó được gọi là khớp nhau nếu phần lồng nhau của chúng rỗng, hoặc nếu mọi dấu ngoặc trong phần lồng nhau ấy đều khớp với một dấu ngoặc khác cũng nằm trong phần đó. Độ sâu lồng nhau của một vị trí \(p\) là số cặp ngoặc khớp nhau \(m\) sao cho \(p\) nằm trong phần lồng nhau của \(m\).

Ví dụ, trong các chuỗi sau, mọi chữ số đều bằng độ sâu lồng nhau tại vị trí của nó: 0((2)1), (((3))1(2)), ((((4)))), ((2))((2))(1). Ba chuỗi đầu có độ dài nhỏ nhất trong số các chuỗi chứa cùng các chữ số theo cùng thứ tự, nhưng chuỗi cuối thì không, vì ((22)1) cũng chứa các chữ số 221 và ngắn hơn.

Cho một chuỗi chữ số S, hãy tìm một chuỗi khác \(S'\), gồm các dấu ngoặc và chữ số, thỏa mãn tất cả các điều kiện sau:

• Mỗi dấu ngoặc trong \(S'\) đều khớp với một dấu ngoặc khác.
• Xóa bất kỳ và toàn bộ dấu ngoặc khỏi \(S'\) sẽ thu được S.
• Mỗi chữ số trong \(S'\) bằng độ sâu lồng nhau tại vị trí của nó.
• \(S'\) có độ dài nhỏ nhất.

Dữ liệu vào

Dòng đầu tiên chứa số lượng bộ test T. T dòng tiếp theo, mỗi dòng biểu diễn một bộ test và chỉ chứa chuỗi S.

Dữ liệu ra

Với mỗi bộ test, in một dòng có dạng Case #x: y, trong đó x là số thứ tự bộ test (bắt đầu từ 1) và y là chuỗi \(S'\) được định nghĩa ở trên.

Ràng buộc

• \(1 \le T \le 100\).
• \(1 \le \lvert S \rvert \le 100\).

Phân nhóm

• Test Set 1 (phán quyết hiển thị): Mỗi ký tự trong S là 0 hoặc 1.
• Test Set 2 (phán quyết hiển thị): Mỗi ký tự trong S là một chữ số thập phân từ 0 đến 9, kể cả hai đầu mút.

Đ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
0000
101
111000
1

Case #1: 0000
Case #2: (1)0(1)
Case #3: (111)000
Case #4: (1)

Nguồn

Google Code Jam 2020, Vòng loại, bài Nesting Depth.

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

Con của Cameron và Jamie sắp tròn 3 tuổi! Tuy giờ đây đứa trẻ đã tự lập hơn, việc sắp xếp các hoạt động cho con và những công việc thiết yếu trong gia đình vẫn là một thử thách đối với hai người.

Cameron và Jamie có một danh sách gồm \(N\) hoạt động cần thực hiện trong ngày. Mỗi hoạt động diễn ra trong một khoảng thời gian xác định. Họ cần giao mỗi hoạt động cho một trong hai người sao cho không ai phải phụ trách hai hoạt động chồng lấn nhau. Một hoạt động kết thúc tại thời điểm \(t\) không được coi là chồng lấn với một hoạt động khác bắt đầu tại thời điểm \(t\).

Ví dụ, giả sử Jamie và Cameron cần phụ trách 3 hoạt động: một hoạt động từ 18:00 đến 20:00, một hoạt động khác từ 19:00 đến 21:00 và một hoạt động nữa từ 22:00 đến 23:00. Một cách phân công là để Jamie phụ trách hoạt động từ 19:00 đến 21:00, còn Cameron phụ trách hai hoạt động kia. Một lịch hợp lệ khác là để Cameron phụ trách hoạt động từ 18:00 đến 20:00 và Jamie phụ trách hai hoạt động còn lại. Lưu ý rằng hai hoạt động đầu tiên chồng lấn trong khoảng từ 19:00 đến 20:00, vì vậy không thể giao cả hai hoạt động đó cho cùng một người.

Cho thời điểm bắt đầu và kết thúc của mỗi hoạt động, hãy tìm một lịch bất kỳ sao cho cùng một người không phải phụ trách các hoạt động chồng lấn, hoặc cho biết điều đó là không thể.

Dữ liệu vào

Dòng đầu tiên của dữ liệu vào chứa số bộ test \(T\). Tiếp theo là \(T\) bộ test. Mỗi bộ test bắt đầu bằng một dòng chứa một số nguyên \(N\), là số hoạt động cần phân công. Sau đó là \(N\) dòng nữa. Dòng thứ \(i\) trong số này (đánh số từ 1) chứa hai số nguyên \(S_i\) và \(E_i\). Hoạt động thứ \(i\) bắt đầu đúng \(S_i\) phút sau nửa đêm và kết thúc đúng \(E_i\) phút sau nửa đêm.

Dữ liệu ra

Với mỗi bộ test, in một dòng có dạng Case #x: y, trong đó x là số thứ tự bộ test (bắt đầu từ 1), còn y là IMPOSSIBLE nếu không có lịch hợp lệ theo các quy tắc trên; nếu có, y là một chuỗi gồm đúng \(N\) ký tự. Ký tự thứ \(i\) của y phải là C nếu hoạt động thứ \(i\) được giao cho Cameron trong lịch đề xuất, và là J nếu hoạt động đó được giao cho Jamie.

Nếu có nhiều lời giải, bạn có thể in ra bất kỳ lời giải nào. Thông tin về việc có nhiều lời giải sẽ không được nhắc lại một cách tường minh trong các bài còn lại của cuộc thi năm 2020.

Ràng buộc

• \(1 \le T \le 100\).
• \(0 \le S_i < E_i \le 24 \times 60\).

Phân nhóm

Test Set 1 (phản hồi kết quả đầy đủ):

• \(2 \le N \le 10\).

Test Set 2 (phản hồi kết quả đầy đủ):

• \(2 \le N \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.

Ví dụ

4
3
360 480
420 540
600 660
3
0 1440
1 3
2 4
5
99 150
1 100
100 301
2 5
150 250
2
0 720
720 1440

Case #1: CJC
Case #2: IMPOSSIBLE
Case #3: JCCJJ
Case #4: CC

Nguồn

Google Code Jam 2020, Vòng loại, bài Parenting Partnering Returns.

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

Vestigium

Vestigium có nghĩa là “vết” (trace) trong tiếng Latinh. Trong bài toán này, chúng ta làm việc với các hình vuông Latin và vết của ma trận.

Vết của một ma trận vuông là tổng các giá trị trên đường chéo chính (đường chéo chạy từ góc trên bên trái đến góc dưới bên phải).

Một ma trận vuông kích thước \(N \times N\) là một hình vuông Latin nếu mỗi ô chứa một trong \(N\) giá trị khác nhau và không có giá trị nào xuất hiện lặp lại trong cùng một hàng hoặc cùng một cột. Trong bài toán này, ta chỉ xét các “hình vuông Latin tự nhiên”, trong đó \(N\) giá trị là các số nguyên từ \(1\) đến \(N\).

Cho một ma trận chỉ chứa các số nguyên từ \(1\) đến \(N\), ta muốn tính vết của nó và kiểm tra xem nó có phải là một hình vuông Latin tự nhiên hay không. Để cung cấp thêm thông tin, thay vì chỉ cho biết ma trận có phải là một hình vuông Latin tự nhiên hay không, hãy tính số hàng và số cột có chứa các giá trị lặp lại.

Dữ liệu vào

Dòng đầu tiên của dữ liệu vào chứa số lượng bộ test \(T\). Tiếp theo là \(T\) bộ test. Mỗi bộ test bắt đầu bằng một dòng chứa một số nguyên duy nhất \(N\): kích thước của ma trận cần xét. Sau đó là \(N\) dòng; dòng thứ \(i\) trong số đó chứa \(N\) số nguyên \(M_{i,1}, M_{i,2}, \ldots, M_{i,N}\). \(M_{i,j}\) là số nguyên nằm ở hàng thứ \(i\) và cột thứ \(j\) của ma trận.

Dữ liệu ra

Với mỗi bộ test, in ra một dòng có dạng Case #x: k r c, trong đó x là số thứ tự của bộ test (bắt đầu từ \(1\)), k là vết của ma trận, r là số hàng của ma trận có chứa phần tử lặp lại và c là số cột của ma trận có chứa phần tử lặp lại.

Ràng buộc

Phân nhóm

Test Set 1 (Phán quyết hiển thị)

• \(1 \le T \le 100\).
• \(2 \le N \le 100\).
• \(1 \le M_{i,j} \le N\) với mọi \(i, j\).

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

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

Nguồn

Google Code Jam 2020, Vòng loại, bài Vestigium.

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