Google Code Jam 2021 - Round 1A

Bộ đề bài

Trở lại kỳ thi
# Bài tập Điểm Thời gian: Giới hạn bộ nhớ
1 Google Code Jam 2021 - Append Sort 26 1.0s 1G
2 Google Code Jam 2021 - Hacked Exam 39 1.0s 1G
3 Google Code Jam 2021 - Prime Time 35 1.0s 1G

1. Google Code Jam 2021 - Append Sort

Điểm: 26 Thời gian: 1.0s Bộ nhớ: 1G Input: bàn phím Output: màn hình

Ta có một danh sách các số nguyên \(X_1,X_2,\ldots,X_N\). Ta muốn chúng theo thứ tự tăng nghiêm ngặt, nhưng không được phép đổi thứ tự các phần tử, nên các thuật toán sắp xếp thông thường không dùng được.

Lựa chọn duy nhất là thay đổi các số bằng cách nối các chữ số từ \(0\) đến \(9\) vào bên phải biểu diễn thập phân của chúng. Chẳng hạn, từ số \(10\), một thao tác có thể biến nó thành \(10\mathbf0\) hoặc \(10\mathbf9\); hai thao tác có thể biến nó thành \(10\mathbf{34}\), như hình dưới.

Cho danh sách hiện tại, cần ít nhất bao nhiêu thao tác nối một chữ số để danh sách trở thành tăng nghiêm ngặt? Ví dụ, với danh sách \(100,7,10\), ta có thể dùng tổng cộng \(4\) thao tác để tạo một danh sách đã sắp xếp như hình:

Dữ liệu vào

Dòng đầu chứa số bộ dữ liệu \(T\). Mỗi bộ được mô tả trên hai dòng. Dòng đầu chứa một số nguyên \(N\), là số phần tử của danh sách. Dòng thứ hai chứa \(N\) số nguyên \(X_1,X_2,\ldots,X_N\), là các phần tử theo đúng thứ tự đã cho.

Dữ liệu ra

Với mỗi bộ dữ liệu, in Case #x: y, trong đó \(x\) là số thứ tự bộ dữ liệu (bắt đầu từ \(1\)), còn \(y\) là số thao tác nối một chữ số ít nhất cần dùng để danh sách tăng nghiêm ngặt.

Ràng buộc

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

Phân nhóm

  • Test Set 1 (Visible Verdict): \(2\le N\le3\); \(1\le X_i\le100\) với mọi \(i\).
  • Test Set 2 (Visible Verdict): \(2\le N\le100\); \(1\le X_i\le10^9\) với mọi \(i\).

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

Phân nhóm Điểm Google Code Jam Tỷ lệ điểm của bài
Test Set 1 12/26 46,15%
Test Set 2 14/26 53,85%

Ví dụ

Ví dụ 1

Input 
4
3
100 7 10
2
10 10
3
4 19 1
3
1 2 3
Output 
Case #1: 4
Case #2: 1
Case #3: 2
Case #4: 0
Giải thích
  • Bộ dữ liệu mẫu #1 là ví dụ trong đề. Như hình vẽ, có thể sắp xếp danh sách bằng \(4\) thao tác. Hai số cuối phải có ít nhất \(3\) chữ số, tổng cộng cần ít nhất \(3\) lần nối cho chúng. Nếu mọi số cuối cùng đều có đúng ba chữ số, số thứ hai sẽ lớn hơn số thứ ba vì bắt đầu bằng \(7\) thay vì \(1\); do đó không thể dùng ít hơn \(4\) thao tác.
  • Trong bộ dữ liệu mẫu #2, thứ tự phải tăng nghiêm ngặt, nên cần ít nhất một thao tác. Mọi chữ số nối hợp lệ vào số thứ hai đều được.
  • Trong bộ dữ liệu mẫu #3, dùng hai thao tác để thu được \(4,19,19\mathbf3\).
  • Trong bộ dữ liệu mẫu #4, danh sách đã tăng nghiêm ngặt nên không cần thao tác.

Nguồn

Google Code Jam 2021, Vòng 1A, bài Append Sort.

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

2. Google Code Jam 2021 - Hacked Exam

Điểm: 39 Thời gian: 1.0s Bộ nhớ: 1G Input: bàn phím Output: màn hình

Một kỳ thi có \(Q\) câu đúng/sai; đáp án đúng mỗi câu là T hoặc F. Mỗi thí sinh chọn một trong hai cho từng câu, và điểm là số câu trả lời đúng.

Đã có \(N\) thí sinh làm bài. Bạn biết câu trả lời từng câu và điểm cuối của mỗi người. Giả sử mọi chuỗi đáp án đúng phù hợp với toàn bộ điểm của các thí sinh có xác suất bằng nhau, bạn muốn tối đa hóa điểm kỳ vọng của mình. Hãy xác định điểm kỳ vọng đó và cách trả lời để đạt được nó.

Dữ liệu vào

Dòng đầu chứa \(T\). Dòng đầu mỗi bộ chứa \(N,Q\). Mỗi trong \(N\) dòng tiếp theo chứa xâu \(A_i\) và số nguyên \(S_i\): câu trả lời và điểm của thí sinh \(i\). Ký tự thứ \(j\) của \(A_i\) là T hoặc F.

Dữ liệu ra

Với mỗi bộ, in Case #x: y z/w, trong đó \(y\) là một chuỗi đáp án đạt điểm kỳ vọng lớn nhất, còn \(z/w\) là điểm kỳ vọng cực đại dưới dạng phân số tối giản; \(w\) phải dương và nhỏ nhất có thể.

Ràng buộc

  • \(1\le T\le2021\); \(|A_i|=Q\); mọi ký tự là T hoặc F.
  • \(0\le S_i\le Q\); tồn tại ít nhất một chuỗi đáp án đúng phù hợp đầu vào.

Phân nhóm

  • Test Set 1 (Visible Verdict): \(1\le N\le2\), \(1\le Q\le10\).
  • Test Set 2 (Hidden Verdict): \(1\le N\le2\), \(1\le Q\le40\).
  • Test Set 3 (Hidden Verdict): \(1\le N\le3\), \(1\le Q\le120\).

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

Phân nhóm Điểm Google Code Jam Tỷ lệ điểm của bài
Test Set 1 8/39 20,51%
Test Set 2 6/39 15,39%
Test Set 3 25/39 64,1%

Ví dụ

Ví dụ 1

Input 
4
1 3
FFT 3
1 3
FFT 2
2 6
FFTTTF 2
FTFTFT 4
2 2
FF 1
TT 1
Output 
Case #1: FFT 3/1
Case #2: FFT 2/1
Case #3: FTFFFT 4/1
Case #4: TF 1/1
Note
  • Mẫu #1: điểm của FFT là \(3\), nên đáp án đúng buộc là FFT.
  • Mẫu #2: đáp án đúng là FFF, FTT hoặc TFT, mỗi chuỗi xác suất \(1/3\). Trả FFT cho kỳ vọng \((2+2+2)/3=2\).
  • Mẫu #3 còn có đáp án đạt kỳ vọng \(4\), chẳng hạn FTFTFT.
  • Mẫu #4 có một câu T, một câu F nhưng không biết thứ tự. TF/FT được \(2\) với xác suất \(1/2\), \(0\) với xác suất \(1/2\); FF/TT luôn được \(1\). Mọi chuỗi có cùng kỳ vọng nên in bất kỳ.

Mẫu bổ sung Test Set 3 (không chạy trên lời giải nộp):

Input bổ sung:

1
3 120
FFTFFFTFFFTTTTTTTFTFFFFFFTTTFTFFFTFTFFTTFTFFTFFTTTFTFTFFTFTFTTFFFFTFTFFFFTTTFTTFTTTTFFFTTFFFFFTTFFTFFTFFTTTFFFFTTFFTFTTF 55
FFFTFFTTFFFFTFTFFTFFFTTTTTTFFFTTTFTTTTFFTFTTTFTTFFTTTFTFFFFTFFTTFFTTFTTFFTFTFFTFTTFTFTFFTTTFFTFTFTTFFTFTFTFTTFFTFFFTFTFT 62
FFFTFTTFFFFFTFTFTTTTTTFFTTFTFFFTFFTTTTTTFFFTTTFFFTTFTFFFFFFTFTTFFTFTTTFTTTTFTTFFFFTFFTTFTFFTTTTTTFTFFFFFTTFFTFTFTFFTTTTT 64

Output bổ sung:

Case #1: FFFTFTTTFFFFTFTFFTFTTTTTTTFFFFTTTFTTTTFFTFTTTTTFFFTFTFTFFFFTFFTTFTFTFTTTTTFFTFFFFFFFFTTFTTTTTTFTTTTFFFFTFTFTTFTFFFFTTTFT 189154508532118369075350624633/2901503505434414233388602018

Kỳ vọng vượt \(65\), cao hơn điểm thật của mọi thí sinh. Cả tử và mẫu có thể lớn hơn \(2^{64}\); tử số ở đây vượt \(2^{97}\).

Kỳ vọng vượt \(65\), cao hơn điểm thật của mọi thí sinh. Cả tử và mẫu có thể lớn hơn \(2^{64}\); tử số ở đây vượt \(2^{97}\).

Kỳ vọng vượt \(65\), cao hơn điểm thật của mọi thí sinh. Cả tử và mẫu có thể lớn hơn \(2^{64}\); tử số ở đây vượt \(2^{97}\).

Kỳ vọng vượt \(65\), cao hơn điểm thật của mọi thí sinh. Cả tử và mẫu có thể lớn hơn \(2^{64}\); tử số ở đây vượt \(2^{97}\).

Kỳ vọng vượt \(65\), cao hơn điểm thật của mọi thí sinh. Cả tử và mẫu có thể lớn hơn \(2^{64}\); tử số ở đây vượt \(2^{97}\).

Kỳ vọng vượt \(65\), cao hơn điểm thật của mọi thí sinh. Cả tử và mẫu có thể lớn hơn \(2^{64}\); tử số ở đây vượt \(2^{97}\).

Kỳ vọng vượt \(65\), cao hơn điểm thật của mọi thí sinh. Cả tử và mẫu có thể lớn hơn \(2^{64}\); tử số ở đây vượt \(2^{97}\).

Kỳ vọng vượt \(65\), cao hơn điểm thật của mọi thí sinh. Cả tử và mẫu có thể lớn hơn \(2^{64}\); tử số ở đây vượt \(2^{97}\).

Kỳ vọng vượt \(65\), cao hơn điểm thật của mọi thí sinh. Cả tử và mẫu có thể lớn hơn \(2^{64}\); tử số ở đây vượt \(2^{97}\).

Kỳ vọng vượt \(65\), cao hơn điểm thật của mọi thí sinh. Cả tử và mẫu có thể lớn hơn \(2^{64}\); tử số ở đây vượt \(2^{97}\).

Kỳ vọng vượt \(65\), cao hơn điểm thật của mọi thí sinh. Cả tử và mẫu có thể lớn hơn \(2^{64}\); tử số ở đây vượt \(2^{97}\).

Nguồn

Google Code Jam 2021, Vòng 1A, bài Hacked Exam.

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

3. Google Code Jam 2021 - Prime Time

Điểm: 35 Thời gian: 1.0s Bộ nhớ: 1G Input: bàn phím Output: màn hình

Bạn đang chơi một trò solitaire mới tên Prime Time. Bạn có một bộ bài, mỗi lá ghi một số nguyên tố; nhiều lá có thể ghi cùng số.

Mục tiêu là chia các lá thành hai nhóm sao cho tổng các số của nhóm thứ nhất bằng tích các số của nhóm thứ hai. Mỗi lá thuộc đúng một nhóm và mỗi nhóm phải có ít nhất một lá. Tổng hoặc tích của nhóm một lá chính là số trên lá đó.

Trong hình, nhóm trái có tổng \(25\), nhóm phải có tích \(25\), nên đây là cách chia hợp lệ. Điểm của bạn là tổng nhóm thứ nhất — cũng là tích nhóm thứ hai — hoặc bằng \(0\) nếu không thể chia. Hãy tìm điểm lớn nhất.

Dữ liệu vào

Dòng đầu chứa số bộ dữ liệu \(T\). Dòng đầu mỗi bộ chứa \(M\), số lượng số nguyên tố phân biệt. Mỗi trong \(M\) dòng tiếp theo chứa \(P_i,N_i\), nghĩa là có đúng \(N_i\) lá ghi số nguyên tố \(P_i\). Tổng số lá là \(\sum_iN_i\).

Dữ liệu ra

Với mỗi bộ dữ liệu, in Case #x: y, trong đó \(x\) là số thứ tự (bắt đầu từ \(1\)), còn \(y\) là điểm lớn nhất.

Ràng buộc

  • \(1\le T\le100\); \(1\le M\le95\) (có đúng \(95\) số nguyên tố từ \(2\) đến \(499\)).
  • \(2\le P_i\le499\); mọi \(P_i\) nguyên tố; \(P_i<P_{i+1}\).
  • \(N_i\ge1\) với mọi \(i\).

Phân nhóm

  • Test Set 1 (Visible Verdict): \(2\le\sum N_i\le10\).
  • Test Set 2 (Visible Verdict): \(2\le\sum N_i\le100\).
  • Test Set 3 (Hidden Verdict): \(2\le\sum N_i\le10^{15}\).

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

Phân nhóm Điểm Google Code Jam Tỷ lệ điểm của bài
Test Set 1 7/35 20%
Test Set 2 13/35 37,14%
Test Set 3 15/35 42,86%

Ví dụ

Ví dụ 1

Input 
4
5
2 2
3 1
5 2
7 1
11 1
1
17 2
2
2 2
3 1
1
2 7
Output 
Case #1: 25
Case #2: 17
Case #3: 0
Case #4: 8
Giải thích

Ở mẫu #1, cách chia tối ưu là \(11+2+7+3+2=5\cdot5\). Cách \(5+7+3+2+5=11\cdot2\) cũng hợp lệ nhưng điểm thấp hơn. Ở mẫu #2, các lá cùng ghi một số vẫn có thể nằm ở hai nhóm khác nhau.

Nguồn

Google Code Jam 2021, Vòng 1A, bài Prime Time.

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