Google Code Jam 2021 - Round 1C

Bạn đang tham gia xổ số với giải thưởng là bánh kếp dùng cả đời. Đã có \(N\) vé được bán; mỗi vé chứa một số nguyên từ \(1\) đến \(K\). Nhiều vé có thể chứa cùng một số. Bạn biết chính xác số trên mọi vé đã bán và muốn tối đa hóa xác suất thắng bằng cách mua hai vé — hai vé có thể mang cùng một số. Bạn được tự chọn số nguyên từ \(1\) đến \(K\) trên mỗi vé.

Bạn là khách hàng cuối cùng, nên sau khi bạn mua, không còn vé nào được bán. Sau đó, một số nguyên \(c\) từ \(1\) đến \(K\) được chọn đều ngẫu nhiên. Bạn thắng nếu một trong hai vé của bạn gần \(c\) nghiêm ngặt hơn mọi vé khác; hoặc nếu hai vé của bạn cách \(c\) bằng nhau và đều gần \(c\) nghiêm ngặt hơn mọi vé khác. Trong các trường hợp còn lại, bạn không thắng.

Cho các số trên \(N\) vé đã mua, xác suất thắng lớn nhất có thể đạt được khi chọn tối ưu hai vé của bạn là bao nhiêu?

Dữ liệu vào

Dòng đầu chứa số bộ dữ liệu \(T\). Mỗi bộ gồm hai dòng. Dòng đầu chứa \(N,K\): số vé đã bán và cận trên của miền số có thể chọn. Dòng thứ hai chứa \(N\) số \(P_1,P_2,\ldots,P_N\), là các số trên những vé đã mua.

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à xác suất thắng lớn nhất khi chọn vé tối ưu.

\(y\) được chấp nhận nếu sai số tuyệt đối hoặc tương đối so với đáp án đúng không quá \(10^{-6}\).

Ràng buộc

• \(1\le T\le100\).
• \(1\le N\le30\).
• \(1\le P_i\le K\) với mọi \(i\).

Phân nhóm

• Test Set 1 (Visible Verdict): \(1\le K\le30\).
• Test Set 2 (Visible Verdict): \(1\le K\le10^9\).

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

Case #1: 0.5
Case #2: 0.4
Case #3: 0.0
Case #4: 0.25

Nguồn

Google Code Jam 2021, Vòng 1C, bài Closest Pick.

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 cho số nguyên không âm ban đầu \(S\) và số nguyên không âm đích \(E\), cả hai ở dạng biểu diễn nhị phân. Mục tiêu là biến đổi \(S\) thành \(E\) bằng hai thao tác:

1. Double: nhân giá trị hiện tại với \(2\).
2. NOT: lấy phủ định theo bit của giá trị hiện tại. Biểu diễn nhị phân trước thao tác không chứa số \(0\) thừa ở đầu; mọi số \(0\) thừa sinh ra sau thao tác cũng bị bỏ. Số \(0\) duy nhất trong biểu diễn của giá trị \(0\) là số \(0\) cần thiết.

Ví dụ, Double biến \(6\) thành \(12\), \(0\) thành \(0\), \(10\) thành \(20\). NOT biến \(0\) thành \(1\), \(1\) thành \(0\), \(3=11_2\) thành \(0\), \(14=1110_2\) thành \(1\), \(10=1010_2\) thành \(5=101_2\), và \(5=101_2\) thành \(2=10_2\). Ký hiệu \(X_2\) chỉ số có biểu diễn nhị phân \(X\).

Bạn có thể dùng hai thao tác bao nhiêu lần tùy ý theo bất kỳ thứ tự nào. Ví dụ:

Hãy tìm số thao tác ít nhất để hoàn tất biến đổi, hoặc cho biết điều đó là không thể.

Dữ liệu vào

Dòng đầu chứa số bộ dữ liệu \(T\). Mỗi bộ gồm một dòng chứa hai xâu \(S,E\), là biểu diễn nhị phân của số đầu và số đích.

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\)). Nếu không thể biến \(S\) thành \(E\), \(y\) là IMPOSSIBLE; nếu có thể, \(y\) là số thao tác nhỏ nhất.

Ràng buộc

• \(1\le T\le100\).
• Mỗi ký tự của \(S\) và \(E\) là 0 hoặc 1.
• Ký tự đầu của \(S\) (tương tự của \(E\)) chỉ có thể là 0 khi xâu có độ dài \(1\).

Phân nhóm

• Test Set 1 (Visible Verdict): \(1\le|S|,|E|\le8\).
• Test Set 2 (Hidden Verdict): \(1\le|S|,|E|\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ụ

6
10001 111
1011 111
1010 1011
0 1
0 101
1101011 1101011

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

Nguồn

Google Code Jam 2021, Vòng 1C, bài Double or NOTing.

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

Năm \(2021\) đang xảy ra một điều đã hơn một thế kỷ không xuất hiện. Giống năm \(1920\) trước đó, \(2021\) là một năm gầm vang (roaring year).

Một năm biểu diễn bởi số nguyên dương \(y\) là gầm vang nếu cách viết thập phân không có số \(0\) ở đầu của \(y\) là phép nối cách viết thập phân không có số \(0\) ở đầu của ít nhất hai số nguyên dương phân biệt, liên tiếp, theo thứ tự tăng. Vì \(2021\) là phép nối của \(20\) và \(21\), nó là năm gầm vang.

Các ví dụ khác là \(12\), \(789\), \(910\), \(1234\) và \(9899100\). Năm \(2020\) không gầm vang vì danh sách duy nhất gồm ít nhất hai số dương nối thành \(2020\) là \([20,20]\), không phải các số liên tiếp.

Tương tự, \(2019\) chỉ có ba cách tách: \([20,1,9]\), \([201,9]\) và \([20,19]\). Hai danh sách đầu không gồm các số liên tiếp; danh sách cuối không tăng. Do đó \(2019\) cũng không gầm vang. Cuối cùng, \(778\) không gầm vang vì \([7,78]\) và \([77,8]\) không gồm các số liên tiếp, còn \([7,7,8]\) không gồm các số phân biệt.

Cho năm hiện tại — có thể gầm vang hoặc không — hãy tìm năm gầm vang kế tiếp.

Dữ liệu vào

Dòng đầu chứa số bộ dữ liệu \(T\). Mỗi dòng tiếp theo chứa một số nguyên \(Y\), là năm hiện tại.

Dữ liệu ra

Với mỗi bộ dữ liệu, in Case #x: z, trong đó \(x\) là số thứ tự (bắt đầu từ \(1\)), còn \(z\) là năm gầm vang đầu tiên lớn hơn nghiêm ngặt \(Y\).

Ràng buộc

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

Phân nhóm

• Test Set 1 (Visible Verdict): \(1\le Y\le10^6\).
• Test Set 2 (Hidden Verdict): \(1\le Y\le10^{18}\).

Đ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
2020
2021
68000
101

Case #1: 2021
Case #2: 2122
Case #3: 78910
Case #4: 123

Nguồn

Google Code Jam 2021, Vòng 1C, bài Roaring Years.

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