Trong đội Code Jam, chúng tôi thích gửi cho nhau các pangram: những cụm từ dùng mỗi chữ cái trong bảng chữ cái tiếng Anh ít nhất một lần. Một ví dụ quen thuộc là “the quick brown fox jumps over the lazy dog”. Đôi khi pangram chứa thông tin mật — chẳng hạn CJ QUIZ: KNOW BEVY OF DP FLUX ALGORITHMS — nên chúng tôi cần giữ chúng an toàn.

Sau vài phút đọc sách mật mã học, chúng tôi biết rằng việc phân tích tích của hai số nguyên tố lớn là rất khó, nên đã thiết kế một hệ mã dựa trên điều đó. Trước tiên, chúng tôi chuẩn bị như sau:

• Chọn 26 số nguyên tố khác nhau, không số nào lớn hơn số nguyên \(N\).
• Sắp xếp các số nguyên tố theo thứ tự tăng dần; gán số nhỏ nhất cho chữ A, số nhỏ thứ hai cho B, và cứ thế.
• Mọi thành viên trong đội ghi nhớ danh sách này.

Khi muốn gửi một pangram, trước hết chúng tôi xóa mọi khoảng trắng để tạo bản rõ. Sau đó, viết tích của số nguyên tố ứng với ký tự thứ nhất và số ứng với ký tự thứ hai; tiếp theo là tích ứng với ký tự thứ hai và thứ ba; cứ thế cho tới tích ứng với hai ký tự cuối. Danh sách mới là bản mã, có ít hơn bản rõ đúng một phần tử.

Ví dụ, giả sử \(N=103\) và ta chọn 26 số nguyên tố lẻ đầu tiên vì lo rằng số chẵn quá dễ phân tích. Khi đó A \(=3\), B \(=5\), C \(=7\), D \(=11\), ..., Z \(=103\). Nếu mã hóa pangram CJ QUIZ... ở trên thì bản rõ là CJQUIZKNOWBEVYOFDPFLUXALGORITHMS. Giá trị đầu của bản mã là \(7\) (số nguyên tố của C) nhân \(31\) (số của J), bằng \(217\); giá trị kế tiếp là \(1891\), và cứ thế, kết thúc bằng \(3053\).

Bạn được cung cấp bản mã và giá trị \(N\) đã dùng, nhưng không được biết các số nguyên tố đã chọn hay cách giải mã. Hãy khôi phục bản rõ.

Dữ liệu vào

Dòng đầu chứa số bộ test \(T\). Mỗi bộ test gồm hai dòng. Dòng đầu chứa hai số nguyên \(N\) như mô tả ở trên và \(L\), độ dài danh sách bản mã. Dòng thứ hai chứa \(L\) số nguyên của bản mã.

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à chuỗi gồm \(L+1\) chữ cái tiếng Anh viết hoa: bản rõ.

Ràng buộc

• \(1\le T\le100\).
• \(25\le L\le100\).
• Bản rõ chứa mỗi chữ cái tiếng Anh ít nhất một lần.

Phân nhóm

Test Set 1 (Visible): \(101\le N\le10000\).

Test Set 2 (Hidden): \(101\le N\le10^{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
103 31
217 1891 4819 2291 2987 3811 1739 2491 4717 445 65 1079 8383 5353 901 187 649 1003 697 3239 7663 291 123 779 1007 3551 1943 2117 1679 989 3053
10000 25
3292937 175597 18779 50429 375469 1651121 2102 3722 2376497 611683 489059 2328901 3150061 829981 421301 76409 38477 291931 730241 959821 1664197 3057407 4267589 4729181 5335543

Case #1: CJQUIZKNOWBEVYOFDPFLUXALGORITHMS
Case #2: SUBDERMATOGLYPHICFJKNQVWXZ

Nguồn

Google Code Jam 2019, Vòng loại, bài Cryptopangrams.

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

Một liên hiệp nghiên cứu vừa xây dựng một hệ cơ sở dữ liệu mới cho trung tâm dữ liệu của họ. Hệ thống gồm một máy tính chủ và \(N\) máy tính worker, được đánh số từ \(0\) đến \(N-1\). Mỗi worker lưu đúng một bit thông tin — có vẻ khá lãng phí, nhưng đây là dữ liệu rất quan trọng!

Máy chủ hỗ trợ lệnh TEST_STORE <bits> như sau: máy chủ đọc chuỗi <bits> gồm đúng \(N\) bit, gửi bit thứ \(i\) cho worker thứ \(i\) lưu trữ, rồi đọc các bit từ các worker và trả chúng về cho người dùng theo đúng thứ tự ban đầu.

Trong điều kiện bình thường, TEST_STORE phải trả lại chính chuỗi đã nhận. Tuy nhiên, đúng \(B\) worker đang bị hỏng. Các worker hỏng vẫn lưu được bit được gửi tới, nhưng không trả về bit nào khi máy chủ đọc dữ liệu. Vì thế, TEST_STORE chỉ trả về \(N-B\) bit của các worker không hỏng, theo thứ tự ID tăng dần.

Ví dụ, giả sử \(N=5\) và các worker \(0\) và \(3\) bị hỏng, tức \(B=2\). Khi đó:

• TEST_STORE 01101 trả về 111;
• TEST_STORE 00110 trả về 010;
• TEST_STORE 01010 trả về 100;
• TEST_STORE 11010 cũng trả về 100.

Vì lý do bảo mật, cơ sở dữ liệu được giấu trong một hầm dưới núi nên mỗi lần gọi TEST_STORE mất rất nhiều thời gian. Hãy xác định chính xác tất cả worker bị hỏng bằng không quá \(F\) lần gọi.

Dữ liệu vào

Đây là bài tương tác. Chương trình nhận dữ liệu từ bộ chấm theo giao thức bên dưới.

Ban đầu, chương trình đọc một dòng chứa số nguyên \(T\), là số bộ test. Sau đó xử lý lần lượt \(T\) bộ test.

Ở đầu mỗi bộ test, chương trình đọc một dòng chứa ba số nguyên \(N\), \(B\) và \(F\): số worker, số worker hỏng và số truy vấn tối đa được phép gửi.

Dữ liệu ra

Chương trình gửi các truy vấn và đáp án tới bộ chấm theo giao thức tương tác bên dưới. Sau mỗi dòng xuất, phải flush bộ đệm chuẩn đầu ra.

Giao thức tương tác

Trong mỗi bộ test, chương trình được gửi tối đa \(F\) dòng truy vấn. Mỗi dòng phải là một chuỗi gồm đúng \(N\) ký tự, mỗi ký tự là 0 hoặc 1. Chuỗi này chính là đối số <bits> của một lệnh TEST_STORE.

Sau mỗi truy vấn hợp lệ, bộ chấm trả về một chuỗi dài đúng \(N-B\), gồm các bit do các worker không hỏng trả về theo thứ tự ID tăng dần. Nếu chương trình gửi quá \(F\) truy vấn, bộ chấm trả về một dòng chỉ chứa -1, chấm dứt toàn bộ giao tiếp và chờ chương trình thoát.

Khi đã xác định được các worker hỏng, chương trình kết thúc bộ test bằng cách in \(B\) số nguyên cách nhau bởi dấu cách: ID của các worker hỏng theo thứ tự tăng dần. Dòng đáp án này không được tính là một trong \(F\) truy vấn.

Nếu \(B\) số được in không đúng chính xác tập ID của các worker hỏng, bài làm nhận Wrong Answer; bộ chấm gửi -1 rồi không giao tiếp thêm. Nếu đáp án đúng, bộ chấm gửi 1, sau đó gửi dòng mở đầu bộ test kế tiếp, hoặc kết thúc nếu không còn bộ test.

Ngay khi đọc được -1, chương trình phải thoát; nếu tiếp tục chờ dữ liệu, chương trình có thể bị báo Time Limit Exceeded thay vì lỗi giao thức thực sự.

Ràng buộc

• \(1\le T\le100\).
• \(2\le N\le1024\).
• \(1\le B\le\min(15,N-1)\).

Phân nhóm

• Test Set 1: \(F=10\).
• Test Set 2: \(F=5\).

Ví dụ

  t = readline_int()             // đọc 2 vào t
  n, b, f = readline_int_list()  // đọc 5, 2, 10 vào n, b, f
  printline 01101 to stdout      // bốn truy vấn tiếp theo khớp ví dụ trong đề
  flush stdout
  response = readline_str()      // đọc 111; lúc này đã có thể suy ra đáp án
  printline 00110 to stdout      // các truy vấn còn lại chỉ để minh họa
  flush stdout
  response = readline_str()      // đọc 010
  printline 01010 to stdout
  flush stdout
  response = readline_str()      // đọc 100
  printline 11010 to stdout
  flush stdout
  response = readline_str()      // đọc 100
  printline 0 3 to stdout        // đoán đáp án mà không cần dùng đủ 10 truy vấn
  flush stdout
  verdict = readline_int()       // đọc 1: test này đúng
  n, b, f = readline_int_list()  // đọc 2, 1, 10 vào n, b, f
  printline 01 to stdout         // đây là truy vấn, không phải đáp án cuối
  flush stdout
  response = readline_str()      // đọc 1
  printline 1 to stdout          // đưa ra một dự đoán sai
  verdict = readline_str()       // đọc -1
  exit                           // thoát để tránh kết quả TLE khó hiểu

Nguồn

Google Code Jam 2019, Vòng loại, bài Dat Bae.

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

Một người vừa trúng xổ số Code Jam và chúng ta nợ họ \(N\) jamcoin! Tuy nhiên, khi chuẩn bị in một tấm séc ngoại cỡ, chúng ta gặp rắc rối: số nguyên \(N\) có ít nhất một chữ số 4, nhưng phím 4 trên bàn phím của máy in séc đã hỏng.

May thay, ta có một cách xử lý khác: gửi cho người thắng hai tấm séc có giá trị là hai số nguyên dương \(A\) và \(B\), sao cho cả \(A\) lẫn \(B\) đều không chứa chữ số 4, đồng thời \(A+B=N\). Hãy tìm bất kỳ cặp \(A,B\) nào thỏa mãn các điều kiện đó.

Dữ liệu vào

Dòng đầu tiên chứa số lượng bộ test \(T\). Tiếp theo là \(T\) bộ test; mỗi bộ test gồm một dòng chứa số nguyên \(N\).

Dữ liệu ra

Với mỗi bộ test, in một dòng có dạng Case #x: A B, trong đó x là số thứ tự bộ test, bắt đầu từ 1, còn \(A\) và \(B\) là hai số nguyên dương được mô tả ở trên.

Đề bài bảo đảm luôn tồn tại ít nhất một đáp án. 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\).
• \(N\) có ít nhất một chữ số 4.

Phân nhóm

• Test Set 1 (Visible): \(1<N<10^5\).
• Test Set 2 (Visible): \(1<N<10^9\).
• Test Set 3 (Hidden): \(1<N<10^{100}\).

Hai Test Set đầu chiếm phần lớn số điểm cần thiết để vượt qua vòng thi gốc. Test Set thứ ba chỉ có thêm 1 điểm.

Đ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
940
4444

Case #1: 2 2
Case #2: 852 88
Case #3: 667 3777

Nguồn

Google Code Jam 2019, Vòng loại, bài Foregone Solution.

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 có thể đi con đường của riêng mình

Đề bài

Bạn vừa bước vào mê cung dễ nhất thế giới. Bạn bắt đầu tại ô phía tây bắc của một lưới gồm \(N \times N\) ô vuông đơn vị và phải đi đến ô phía đông nam. Bạn chỉ có thể thực hiện hai loại bước đi: đi một đơn vị về phía đông và đi một đơn vị về phía nam. Bạn có thể đi vào bất kỳ ô nào, nhưng không được thực hiện bước đi khiến bạn ra khỏi lưới.

Bạn rất hào hứng vì sắp trở thành người đầu tiên trên thế giới giải được mê cung, nhưng rồi bạn nhìn thấy những dấu chân. Đối thủ của bạn, Labyrinth Lydia, đã giải mê cung trước bạn theo đúng các quy tắc được mô tả ở trên!

Là một người có tư duy độc lập, bạn không muốn sử dụng lại bất kỳ bước đi nào của Lydia. Cụ thể, nếu đường đi của cô ấy có một bước đi đơn vị từ một ô \(A\) nào đó sang ô kề \(B\), đường đi của bạn không được chứa bước đi từ \(A\) sang \(B\). (Tuy nhiên, trong trường hợp đó, đường đi của bạn vẫn được phép ghé qua \(A\) hoặc \(B\), miễn là bạn không đi từ \(A\) sang \(B\).) Hãy tìm một đường đi như vậy.

Trong hình minh họa sau đây, đường đi của Lydia được tô màu xanh dương và một đường đi hợp lệ có thể có của bạn được tô màu cam.

Dữ liệu vào

Dòng đầu tiên chứa số lượng bộ test \(T\). Tiếp theo là \(T\) bộ test; mỗi bộ gồm hai dòng. Dòng đầu tiên chứa một số nguyên \(N\), cho biết kích thước của mê cung như đã mô tả ở trên. Dòng thứ hai chứa chuỗi \(P\) gồm \(2N - 2\) ký tự; mỗi ký tự là chữ cái in hoa E (đi về phía đông) hoặc chữ cái in hoa S (đi về phía nam), biểu diễn đường đi hợp lệ của Lydia qua mê cung.

Dữ liệu ra

Với mỗi bộ test, hãy in một dòng có dạng Case #x: y, trong đó x là số thứ tự của bộ test (bắt đầu từ \(1\)), còn y là một chuỗi gồm \(2N - 2\) ký tự; mỗi ký tự là chữ cái in hoa E (đi về phía đông) hoặc chữ cái in hoa S (đi về phía nam), biểu diễn một đường đi hợp lệ của bạn qua mê cung và không xung đột với đường đi của Lydia như đã mô tả ở trên. Đề bài đảm bảo luôn tồn tại ít nhất một đáp án.

Ràng buộc

• \(1 \le T \le 100\).
• \(P\) chứa chính xác \(N - 1\) ký tự E và chính xác \(N - 1\) ký tự S.

Phân nhóm

Test Set 1 (Hiển thị)

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

Test Set 2 (Hiển thị)

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

Test Set 3 (Ẩn)

• Với nhiều nhất \(10\) bộ test, \(2 \le N \le 50000\).
• Với tất cả các bộ test còn lại, \(2 \le N \le 10000\).

Đ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
SE
5
EESSSESE

Case #1: ES
Case #2: SEEESSES

Nguồn

Google Code Jam 2019, Vòng loại, bài You Can Go Your Own Way.

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