Google Code Jam 2016 - Qualification Round

Một jamcoin là một chuỗi gồm \(N\ge2\) chữ số, có các tính chất sau:

• Mọi chữ số là 0 hoặc 1.
• Chữ số đầu là 1 và chữ số cuối là 1.
• Nếu diễn giải chuỗi trong bất kỳ cơ số nào từ 2 đến 10, kể cả hai đầu, số nhận được không phải số nguyên tố.

Không phải mọi chuỗi 0 và 1 đều là jamcoin. Ví dụ, 101 không phải jamcoin vì trong cơ số 2 nó có giá trị 5, là số nguyên tố. Nhưng 1001 là một jamcoin: khi diễn giải lần lượt trong các cơ số từ 2 đến 10, nó có giá trị 9, 28, 65, 126, 217, 344, 513, 730 và 1001; không số nào là nguyên tố.

Chúng tôi nghe nói có những cộng đồng dùng jamcoin làm tiền tệ. Khi gửi jamcoin cho ai đó, phép lịch sự là chứng minh jamcoin hợp lệ bằng cách kèm một ước không tầm thường của giá trị jamcoin trong mỗi cơ số từ 2 đến 10. Ước không tầm thường của số nguyên dương \(K\) là số nguyên dương khác 1 và \(K\), đồng thời chia hết \(K\). Để thuận tiện, các ước phải được viết trong cơ số 10.

Ví dụ, với jamcoin 1001 ở trên, một bộ ước không tầm thường khả dĩ cho các giá trị trong cơ số 2 đến 10 lần lượt là 3, 7, 5, 6, 31, 8, 27, 5 và 77.

Bạn có thể tạo \(J\) jamcoin khác nhau có độ dài \(N\), cùng chứng minh chúng hợp lệ không?

Dữ liệu vào

Dòng đầu chứa số bộ test \(T\). Mỗi bộ test gồm một dòng chứa hai số nguyên \(N,J\).

Dữ liệu ra

Với mỗi bộ test, in \(J+1\) dòng. Dòng đầu chỉ gồm Case #x:, trong đó x là số thứ tự bộ test (bắt đầu từ 1). Mỗi dòng trong \(J\) dòng còn lại gồm một jamcoin độ dài \(N\), theo sau bởi chín số nguyên. Số thứ \(i\) trong chín số đó (đếm từ 1) phải là một ước không tầm thường của jamcoin khi nó được diễn giải trong cơ số \(i+1\).

Mọi jamcoin phải khác nhau. Không được in cùng một jamcoin trên hai dòng khác nhau, kể cả khi dùng bộ ước khác.

Ràng buộc

• \(T=1\) (chỉ có một bộ test).
• Bảo đảm tồn tại ít nhất \(J\) jamcoin khác nhau độ dài \(N\).

Phân nhóm

• Test Set 1 (Hiển thị): \(N=16\), \(J=50\).
• Test Set 2 (Ẩn): \(N=32\), \(J=500\).

Khác thường so với một bài Code Jam, bạn đã biết chính xác nội dung từng tệp đầu vào. Chẳng hạn, tệp đầu vào của Test Set nhỏ luôn gồm đúng hai dòng:

1
16 50

Vì vậy, bạn có thể thực hiện một số tính toán trước khi thực sự tải tệp đầu vào và bắt đầu tính giờ.

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

Case #1:
100011 5 13 147 31 43 1121 73 77 629
111111 21 26 105 1302 217 1032 513 13286 10101
111001 3 88 5 1938 7 208 3 20 11

Nguồn

Google Code Jam 2016, Vòng loại, bài Coin Jam.

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

Cô cừu Bleatrix Trotter nghĩ ra một chiến lược giúp mình ngủ nhanh hơn. Trước tiên, cô chọn một số \(N\). Sau đó cô bắt đầu đọc \(N,2\times N,3\times N,\ldots\). Mỗi lần đọc một số, cô nghĩ đến tất cả chữ số trong số đó. Cô theo dõi những chữ số trong 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 đã từng nhìn thấy ít nhất một lần trong bất kỳ số nào đã đọc. Ngay khi đã thấy đủ cả mười chữ số, cô sẽ ngủ thiếp đi.

Bleatrix phải bắt đầu bằng \(N\) và luôn phải đọc \((i+1)\times N\) ngay sau \(i\times N\). Ví dụ, giả sử cô chọn \(N=1692\), cô sẽ đếm như sau:

• \(N=1692\). Lúc này cô đã thấy các chữ số 1, 2, 6 và 9.
• \(2N=3384\). Lúc này cô đã thấy 1, 2, 3, 4, 6, 8 và 9.
• \(3N=5076\). Lúc này cô đã thấy đủ mười chữ số và ngủ thiếp đi.

Số cuối cùng cô đọc trước khi ngủ là gì? Nếu cô sẽ đếm mãi mãi, hãy in INSOMNIA.

Dữ liệu vào

Dòng đầu chứa số bộ test \(T\). Mỗi bộ test gồm một dòng chứa số nguyên \(N\) mà Bleatrix đã chọn.

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à số cuối cùng Bleatrix đọc trước khi ngủ theo các quy tắc trên.

Ràng buộc

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

Phân nhóm

• Test Set 1 (Hiển thị): \(0\le N\le200\).
• Test Set 2 (Ẩn): \(0\le N\le10^6\).

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

5
0
1
2
11
1692

Case #1: INSOMNIA
Case #2: 10
Case #3: 90
Case #4: 110
Case #5: 5076

Nguồn

Google Code Jam 2016, Vòng loại, bài Counting Sheep.

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

Ngày xưa, nền văn minh Fractal đã tạo ra những tác phẩm nghệ thuật gồm một hàng gạch. Họ dùng hai loại gạch: vàng (G) và chì (L).

Mỗi tác phẩm Fractal được xác định bởi hai tham số: một chuỗi gốc gồm \(K\) viên gạch và một độ phức tạp \(C\). Với một chuỗi gốc cho trước, tác phẩm ở độ phức tạp 1 chính là chuỗi gốc. Tác phẩm ở độ phức tạp \(X+1\) được tạo từ tác phẩm ở độ phức tạp \(X\) như sau:

• thay mỗi viên L bằng một bản sao của chuỗi gốc;
• thay mỗi viên G bằng \(K\) viên G.

Ví dụ, với chuỗi gốc LGL, các tác phẩm có độ phức tạp từ 1 đến 3 là:

• \(C=1\): LGL (chính là chuỗi gốc);
• \(C=2\): LGLGGGLGL;
• \(C=3\): LGLGGGLGLGGGGGGGGGLGLGGGLGL.

Hình dưới minh họa cách tạo tác phẩm độ phức tạp 2 từ tác phẩm độ phức tạp 1:

https://cdn.lqdoj.edu.vn/media/pagedown-uploads/pd_1_bf2e7cbb.png

Bạn vừa phát hiện một tác phẩm Fractal, nhưng gạch quá bẩn nên không thể biết chúng làm bằng gì. Là một nhà khảo cổ am hiểu văn hóa Fractal địa phương, bạn biết \(K\) và \(C\) nhưng không biết chuỗi gốc. Vì vàng rất thú vị, bạn muốn biết tác phẩm có ít nhất một viên G hay không. Ngân sách cho phép thuê \(S\) nghiên cứu sinh; mỗi người có thể lau một viên do bạn chọn trong số \(K^C\) viên để xem đó là G hay L.

Bạn có thể chọn trước không quá \(S\) vị trí sao cho, bất kể chuỗi gốc là gì, kết quả quan sát luôn cho phép kết luận chắc chắn tác phẩm có ít nhất một G hay không không? Nếu có, hãy cho biết cần lau những vị trí nào.

Dữ liệu vào

Dòng đầu chứa số bộ test \(T\). Mỗi bộ test gồm một dòng chứa ba số nguyên \(K\), \(C\) và \(S\).

Dữ liệu ra

Với mỗi bộ test, in 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 tồn tại tập vị trí thỏa mãn, hoặc là danh sách từ 1 đến \(S\) số nguyên dương chỉ các vị trí đủ để trả lời câu hỏi. Các vị trí được đánh số từ 1 ở ngoài cùng bên trái đến \(K^C\) ở ngoài cùng bên phải. Có thể in theo thứ tự bất kỳ, nhưng các vị trí phải đôi một khác nhau.

Nếu có nhiều tập hợp hợp lệ, có thể in bất kỳ tập nào. Hãy nhớ rằng sau khi nộp một bộ Small và được chấp nhận, bạn không thể tải rồi nộp một đầu vào Small khác; FAQ của cuộc thi giải thích kỹ hơn. Lời nhắc này không xuất hiện ở các vòng sau.

Ràng buộc

• \(1\le T\le100\).
• \(1\le K\le100\).
• \(1\le C\le100\).
• \(K^C\le10^{18}\).

Phân nhóm

• Test Set 1 (Visible): \(S=K\).
• Test Set 2 (Hidden): \(1\le S\le K\).

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

5
2 3 2
1 1 1
2 1 1
2 1 2
3 2 3

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

Nguồn

Google Code Jam 2016, Vòng loại, bài Fractiles.

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

Nhà Bánh Kẹp Vô Hạn vừa giới thiệu một loại bánh mới! Một mặt bánh có khuôn mặt vui vẻ bằng vụn sô-cô-la (“mặt vui”), mặt kia không có gì (“mặt trống”).

Bạn là trưởng phục vụ đang trực và nhà bếp vừa đưa một chồng bánh để phục vụ khách. Như mọi người phục vụ bánh giỏi, bạn có thị lực tia X và biết mỗi chiếc đang ngửa mặt vui hay mặt trống. Bạn nghĩ khách sẽ vui nhất nếu khi phục vụ, mọi chiếc bánh đều ngửa mặt vui.

Bạn biết thao tác sau: cẩn thận nhấc một số chiếc ở đỉnh chồng (có thể là toàn bộ), lật cả nhóm, rồi đặt lại lên những chiếc không nhấc. Cả nhóm được lật trong một chuyển động, không lật riêng từng chiếc. Chính xác hơn, đánh số bánh \(1,2,\ldots,N\) từ trên xuống dưới và chọn \(i\) chiếc đầu. Sau khi lật, thứ tự là \(i,i-1,\ldots,2,1,i+1,\ldots,N\). Các bánh \(1\) đến \(i\) đổi mặt đang ngửa; các bánh \(i+1\) đến \(N\) giữ nguyên mặt.

Ký hiệu mặt vui là +, mặt trống là -. Với chồng --+- từ trên xuống, có thể nhấc ba chiếc đầu, lật cả nhóm rồi đặt lên chiếc thứ tư không đổi, thu được -++-. Những thao tác hợp lệ khác là lật một, hai hoặc cả bốn chiếc đầu. Không được lật hai chiếc ở giữa hay riêng chiếc cuối vì chỉ được lấy một đoạn bắt đầu từ đỉnh.

Bạn sẽ không phục vụ cho đến khi mọi bánh đều ngửa mặt vui, nhưng không muốn bánh nguội. Nếu luôn lựa chọn tối ưu, cần ít nhất bao nhiêu thao tác?

Dữ liệu vào

Dòng đầu chứa \(T\). Mỗi bộ test gồm một chuỗi \(S\); mỗi ký tự là + (ban đầu ngửa mặt vui) hoặc - (ban đầu ngửa mặt trống). Đọc từ trái sang phải tương ứng với chồng bánh từ trên xuống dưới.

Dữ liệu ra

Với mỗi bộ test, in Case #x: y, trong đó \(x\) bắt đầu từ 1 và \(y\) là số thao tác nhỏ nhất để mọi bánh ngửa mặt vui.

Ràng buộc

• \(1\le T\le100\).
• Mọi ký tự của \(S\) là + hoặc -.

Phân nhóm

• Test Set 1 (Visible): \(1\le |S|\le10\).
• Test Set 2 (Hidden): \(1\le |S|\le100\).

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

5
-
-+
+-
+++
--+-

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

Nguồn

Google Code Jam 2016, Vòng loại, bài Revenge of the Pancakes.

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