Google Code Jam 2019 - Round 1A

Đề bài

Trong một chuyến thám hiểm ngoài Trái Đất, bạn đã tìm thấy bằng chứng về thơ ca của người ngoài hành tinh! Nhóm ngôn ngữ học của bạn xác định rằng mỗi từ trong ngôn ngữ ngoài hành tinh có trọng âm ở đúng một vị trí (một chữ cái) trong từ; phần của từ bắt đầu từ chữ cái mang trọng âm được gọi là hậu tố trọng âm. Hai từ được coi là gieo vần nếu hậu tố trọng âm của chúng giống nhau. Chẳng hạn, hai từ PROL và TARPOL gieo vần nếu chữ cái mang trọng âm trong cả hai từ là O hoặc L, nhưng chúng không gieo vần nếu các chữ cái mang trọng âm là hai chữ R, hoặc là R trong PROL và P trong TARPOL, hoặc là O trong PROL và L trong TARPOL.

Bạn đã khôi phục được danh sách \(N\) từ có thể thuộc một bài thơ ngoài hành tinh. Đáng tiếc là bạn không biết chữ cái nào mang trọng âm trong mỗi từ. Bạn tin rằng mình có thể loại bỏ không hoặc nhiều từ trong số này, gán chữ cái mang trọng âm cho các từ còn lại, rồi sắp xếp các từ đó thành từng cặp sao cho mỗi từ chỉ gieo vần với từ còn lại trong cặp của nó và không gieo vần với bất kỳ từ nào thuộc các cặp khác.

Hãy tìm số lượng từ lớn nhất có thể được sắp xếp thành các cặp theo cách này.

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 bắt đầu bằng một dòng chứa số nguyên duy nhất \(N\). Sau đó là \(N\) dòng, mỗi dòng chứa một chuỗi \(W_i\) gồm các chữ cái tiếng Anh in hoa, biểu diễn một từ riêng biệt. Lưu ý rằng cùng một từ có thể được gán trọng âm khác nhau trong các bộ test khác nhau.

Dữ liệu ra

Với mỗi bộ test, in ra một dòng theo định dạng Case #x: y, trong đó x là số thứ tự của bộ test (bắt đầu từ \(1\)) và y là kích thước của tập con lớn nhất gồm các từ thỏa mãn những tiêu chí nêu trên.

Ràng buộc

• \(1 \le T \le 100\).
• \(1 \le |W_i| \le 50\) với mọi \(i\).
• \(W_i\) chỉ gồm các chữ cái tiếng Anh in hoa với mọi \(i\).
• \(W_i \ne W_j\) với mọi \(i \ne j\) (các từ không lặp lại trong cùng một bộ test).

Phân nhóm

Test Set 1 (Hiển thị)

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

Test Set 2 (Ẩn)

• \(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
2
TARPOL
PROL
3
TARPOR
PROL
TARPRO
6
CODEJAM
JAM
HAM
NALAM
HUM
NOLOM
4
PI
HI
WI
FI

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

Nguồn

Google Code Jam 2019, Vòng 1A, bài Alien Rhyme.

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

Năm ngoái, một lũ chuột túi má phiền phức đã đến cư trú trong vườn cây ăn quả của chúng tôi. Chúng tôi đã thử đổi nghề bằng cách mở một sân golf thu nhỏ, nhưng có vẻ như lũ chuột cũng theo chúng tôi đến đây! Một lần nữa, chúng tôi cần xác định có bao nhiêu con chuột, nhưng không thể quan sát trực tiếp vì chúng kín đáo và hoạt động về đêm, trong khi chúng tôi lại thích ngủ vào ban đêm. Chúng tôi biết số chuột nằm trong khoảng từ \(1\) đến M, tính cả hai đầu.

Sân golf thu nhỏ của chúng tôi nổi tiếng vì có một cối xay gió điện tử nhỏ trên mỗi lỗ trong số 18 lỗ. Cối xay thứ \(i\) có \(2 \leq \mathbf{B}_i \leq 18\) cánh, được đánh số theo chiều kim đồng hồ từ \(0\) đến \(\mathbf{B}_i-1\). Mỗi đêm, trước khi đi ngủ, chúng tôi tắt các cối xay và đặt tất cả sao cho cánh số \(0\) hướng xuống dưới; điều này rất quan trọng để các cối xay có thể sạc đúng cách cho ngày hôm sau. Tuy nhiên, chúng tôi nhận thấy rằng khi thức dậy, các cối xay đã bị tác động. Vì sân golf thu nhỏ nằm ở một khu vực không có gió, chúng tôi cho rằng chính lũ chuột nghịch ngợm là thủ phạm!

Chúng tôi biết rằng mỗi đêm, tất cả chuột lần lượt chui ra; mỗi con chọn độc lập và ngẫu nhiên đều một trong các cối xay, rồi xoay cối đó ngược chiều kim đồng hồ một cánh. Chẳng hạn, với một cối xay có 3 cánh và cánh số 0 đang hướng xuống, con chuột đầu tiên tác động vào nó sẽ xoay để cánh số 1 hướng xuống; những con tiếp theo tác động vào cối xay đó sẽ lần lượt làm cho cánh hướng xuống mang số 2, rồi 0, rồi 1, và cứ tiếp tục như vậy.

Chúng tôi đã nghĩ ra một kế hoạch. Các cối xay được thiết kế sao cho có thể dễ dàng thay đổi số cánh (để điều chỉnh độ khó của sân), và giờ chúng tôi sẽ tận dụng điều đó! Mỗi đêm, trước khi đi ngủ, chúng tôi có thể chọn số cánh cho từng cối xay trong số 18 cối, miễn là nằm trong giới hạn đã cho; không bắt buộc mọi cối xay phải có cùng số cánh, cũng không bắt buộc phải đưa ra cùng lựa chọn vào mỗi đêm. Vào buổi sáng, chúng tôi sẽ quan sát số ghi trên cánh đang hướng xuống của từng cối xay.

Chúng tôi có N đêm để xác định \(G\), số lượng chuột. Bạn có thể giúp chúng tôi không?

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à một bài toán tương tác. Bạn cần bảo đảm rằng mình đã đọc thông tin trong phần Bài toán tương tác của mục Câu hỏi thường gặp.

Ban đầu, chương trình phải đọc một dòng chứa ba số nguyên T, N và M, lần lượt là số lượng bộ test, số đêm được phép sử dụng trong mỗi bộ test và số chuột tối đa. Sau đó, bạn cần xử lý T bộ test.

Trong mỗi bộ test, chương trình thực hiện tối đa N + 1 lượt trao đổi với bộ chấm. Bạn có thể thực hiện tối đa N lượt trao đổi có dạng sau:

• Chương trình in một dòng gồm mười tám số nguyên từ 2 đến 18, tính cả hai đầu; số thứ \(i\) biểu thị số cánh mà bạn muốn cối xay thứ \(i\) có trong đêm đó.
• Bộ chấm trả lời bằng một dòng gồm mười tám số nguyên; số thứ \(i\) biểu thị số ghi trên cánh đang hướng xuống của cối xay thứ \(i\) vào buổi sáng, sau khi lũ chuột đã nghịch phá. Nếu bạn gửi dữ liệu không hợp lệ (chẳng hạn một số nằm ngoài phạm vi hoặc một dòng sai định dạng), bộ chấm sẽ trả lời -1 thay vào đó.

Trong mỗi đêm, đối với mỗi con chuột, cối xay mà nó chọn để xoay được chọn ngẫu nhiên (giả ngẫu nhiên) và đều; lựa chọn này độc lập với mọi lựa chọn khác của bất kỳ con chuột nào (kể cả chính nó) trong bất kỳ đêm nào.

Sau khi thực hiện từ 0 đến N lượt trao đổi như mô tả ở trên, bạn phải thực hiện thêm một lượt trao đổi có dạng sau:

• Chương trình in một số nguyên: dự đoán của bạn cho \(G\), số lượng chuột.
• Bộ chấm trả lời bằng một dòng chứa duy nhất một số nguyên: 1 nếu đáp án của bạn đúng, và -1 nếu đáp án sai (hoặc nếu bạn đã cung cấp một dòng sai định dạng).

Sau khi bộ chấm gửi -1 vào luồng đầu vào của chương trình (do dữ liệu không hợp lệ hoặc đáp án không đúng), nó 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 -1, 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 để chương trình kết thúc đủ sớm nhằm nhận kết quả Wrong Answer thay vì Time Limit Exceeded. Như thường lệ, nếu chương trình dùng quá giới hạn bộ nhớ hoặc gặp lỗi khi chạy, bạn sẽ nhận kết quả tương ứng.

Ràng buộc

\(1 \leq \mathbf{T} \leq 20\).

Phân nhóm

Test set 1 (Công khai)

\(\mathbf{N} = 365\).
\(\mathbf{M} = 100\).

Test set 2 (Ẩn)

\(\mathbf{N} = 7\).
\(\mathbf{M} = 10^6\).

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 nền tảng của chúng tôi. Để 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; bạn có thể dùng trình chạy tương tác của chúng tôi cho việc đó. Để biết thêm thông tin, hãy đọc hướng dẫn trong các chú thích của tệp đó và xem thêm phần Bài toán tương tác trong mục Câu hỏi thường gặp.

Hướng dẫn dành cho công cụ kiểm thử được viết trong các chú thích bên trong công cụ. Chúng tôi khuyến khích bạn bổ sung các bộ test của riêng mình. Xin lưu ý rằng mặc dù công cụ kiểm thử được xây dựng để mô phỏng hệ thống chấm, nó KHÔNG PHẢI là 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 xem phần Lập trình trong mục Câu hỏi thường gặp để bảo đảm rằng bạn đang dùng cùng trình biên dịch với chúng tôi.

Tải công cụ kiểm thử

Ví dụ

  t, n, m = readline_int_list()   // Đọc 20 vào t, 365 vào n và 100 vào m.
  // Chọn số cánh cho đêm thứ nhất.
  printline 2 2 2 2 18 3 3 3 3 3 3 4 4 4 4 5 2 2 to stdout
  flush stdout
  // Đọc 0 0 0 0 0 0 1 2 1 0 1 2 0 0 0 0 1 0 vào res.
  res = readline_int_list()
  // Chọn số cánh cho đêm thứ hai.
  printline 2 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 2 to stdout
  flush stdout
  // Đọc 0 1 1 2 0 0 1 0 0 0 0 0 0 1 0 0 0 0 vào res.
  res = readline_int_list()
  printline 8 to stdout        // Ta đưa ra dự đoán sai dù vẫn có thể
  flush stdout                 // điều tra thêm tối đa 363 đêm nữa.
  verdict = readline_int()     // Đọc -1 vào verdict (bộ chấm đã quyết định rằng
                               //   lời giải của ta không đúng)
  exit                         // Thoát để tránh lỗi TLE không rõ nguyên nhân

Nguồn

Google Code Jam 2019, Vòng 1A, bài Golf Gophers.

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 tàu Battlestarcraft Algorithmica của chúng ta đang bị những robot dai dẳng mang tên Pylons truy đuổi trong không gian! Chúng ta vừa dịch chuyển tức thời đến một thiên hà mới để cố gắng cắt đuôi chúng. Chúng ta muốn ở lại đây càng lâu càng tốt nhằm có thêm thời gian lên kế hoạch cho bước tiếp theo... nhưng cũng không muốn bị bắt!

Thiên hà này là một lưới phẳng gồm \(R\) hàng và \(C\) cột; các hàng được đánh số từ \(1\) đến \(R\) theo thứ tự từ trên xuống dưới, còn các cột được đánh số từ \(1\) đến \(C\) theo thứ tự từ trái sang phải. Ta có thể chọn ô bắt đầu và phải tiếp tục nhảy giữa các ô cho đến khi đã thăm mỗi ô trong thiên hà đúng một lần. Nói cách khác, ta không bao giờ được thăm lại một ô, kể cả ô bắt đầu.

Ta không muốn khiến Pylons đoán bước đi tiếp theo quá dễ dàng. Mỗi khi nhảy từ ô hiện tại, ta phải chọn một ô đích không cùng hàng, cùng cột hoặc cùng đường chéo với ô hiện tại. Gọi \((i, j)\) là ô ở hàng thứ \(i\) và cột thứ \(j\); một bước nhảy từ ô hiện tại \((r, c)\) đến ô đích \((r', c')\) không hợp lệ khi và chỉ khi ít nhất một trong các điều sau đúng:

• \(r = r'\)
• \(c = c'\)
• \(r - c = r' - c'\)
• \(r + c = r' + c'\)

Bạn có thể giúp chúng ta tìm một thứ tự thăm toàn bộ \(R \times C\) ô sao cho bước đi giữa mọi cặp ô liên tiếp trong dãy đều hợp lệ không? Hay chúng ta không thể thoát khỏi Pylons?

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 hai số nguyên \(R\) và \(C\): số hàng và số cột của thiên hà này.

Dữ liệu ra

Với mỗi bộ test, in một dòng có dạng Case #x: y, trong đó y là một chuỗi chữ cái in hoa, bằng POSSIBLE hoặc IMPOSSIBLE tùy theo việc có thể thỏa mãn các điều kiện trong đề bài hay không. Sau đó, nếu có thể, in thêm \(R \times C\) dòng. Dòng thứ \(i\) trong số này biểu diễn ô thứ \(i\) mà bạn sẽ thăm (đánh số từ \(1\)), và phải chứa hai số nguyên \(r_i\) và \(c_i\): hàng và cột của ô đó. Lưu ý rằng dòng đầu tiên trong số các dòng này biểu diễn ô bắt đầu mà bạn chọn.

Ràng buộc

Phân nhóm

Test Set 1 (Hiển thị):

• \(T = 16\).
• \(2 \le R \le 5\).
• \(2 \le C \le 5\).

Test Set 2 (Ẩn):

• \(1 \le T \le 100\).
• \(2 \le R \le 20\).
• \(2 \le C \le 20\).

Đ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
2 5

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

Nguồn

Google Code Jam 2019, Vòng 1A, bài Pylons.

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