Người hâm mộ quá khích

Đề bài

Hôm nay sẽ là ngày ấy — hôm nay sẽ là ngày bạn cuối cùng cũng chụp được một bức ảnh với chú mèo Peppurr!

Người ta vừa thông báo rằng Peppurr sẽ đi lưu diễn quanh thành phố của bạn. Thành phố có vô hạn con đường dài vô hạn chạy theo hướng bắc–nam và vô hạn con đường dài vô hạn chạy theo hướng đông–tây. Một giao lộ là bất kỳ điểm nào mà một con đường bắc–nam gặp một con đường đông–tây. Từ một giao lộ bất kỳ, giao lộ gần nhất theo mỗi trong bốn hướng (bắc, đông, nam và tây) nằm cách đúng một khu phố.

Bạn biết chính xác lộ trình mà chuyến lưu diễn của Peppurr sẽ đi qua trên các con đường đó. Mục tiêu của bạn là có mặt tại một trong các giao lộ thuộc lộ trình của Peppurr đúng lúc Peppurr ở đó, và bạn muốn làm điều này sớm nhất có thể. Đó là cách bạn sẽ chụp được ảnh với Peppurr!

Chuyến lưu diễn của Peppurr bắt đầu tại một giao lộ nằm cách giao lộ nơi bạn đang đứng X khu phố về phía đông và Y khu phố về phía bắc. Cả bạn và Peppurr đều mất đúng một phút để đi hết một khu phố và phải kết thúc mỗi phút tại một giao lộ; không ai trong hai có thể chỉ đi một phần khu phố.

Peppurr di chuyển theo một lộ trình định trước. Trong mỗi phút, bạn có thể chọn đứng yên suốt phút đó, hoặc dùng phút đó để đi một khu phố theo một trong 4 hướng (bắc, đông, nam hoặc tây). Cả bạn và Peppurr chỉ đi dọc theo các con đường.

Nếu bạn và Peppurr ở cùng một giao lộ vào cùng một thời điểm, bạn có thể chụp ảnh, kể cả tại giao lộ cuối cùng của chuyến lưu diễn. Tuy nhiên, Peppurr không thể chụp ảnh sau khi chuyến lưu diễn kết thúc, vì vậy nếu bạn đến giao lộ cuối cùng chỉ muộn hơn thời điểm kết thúc dù một phút thì bạn cũng sẽ không chụp được ảnh.

Liệu bạn có thể chụp ảnh với Peppurr không? Nếu có, bạn có thể làm được sớm nhất sau bao lâu?

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 X, Y và một chuỗi ký tự M. Điều này biểu thị rằng chuyến lưu diễn của Peppurr bắt đầu cách bạn đúng X khu phố về phía đông và Y khu phố về phía bắc. Chuỗi M là dãy các bước di chuyển mà Peppurr sẽ thực hiện. Ký tự thứ \(i\) trong M là một trong N, E, S hoặc W, tương ứng với hướng (lần lượt là bắc, đông, nam hoặc tây) mà Peppurr sẽ đi một khu phố trong phút thứ \(i\) của chuyến lưu diễn.

Dữ liệu ra

Với mỗi bộ test, 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). Nếu không có cách nào chụp ảnh với Peppurr, y là IMPOSSIBLE. Nếu không, y là số phút nhỏ nhất tính từ lúc chuyến lưu diễn bắt đầu cần để chụp được ảnh với Peppurr.

Ràng buộc

• \(1 \le T \le 100\).
• \((X, Y) \ne (0, 0)\). (Chuyến lưu diễn không bắt đầu tại cùng giao lộ với bạn.)

Phân nhóm

Test Set 1 (Phán quyết hiển thị)

• \(0 \le X \le 10\).
• \(0 \le Y \le 10\).
• \(1 \le\) độ dài của M \(\le 8\).
• Mỗi ký tự trong M là một chữ cái in hoa — N hoặc S.

Test Set 2 (Phán quyết hiển thị)

• \(0 \le X \le 1000\).
• \(0 \le Y \le 1000\).
• \(1 \le\) độ dài của M \(\le 1000\).
• Mỗi ký tự trong M là một chữ cái in hoa — N hoặc S.

Test Set 3 (Phán quyết hiển thị)

• \(0 \le X \le 1000\).
• \(0 \le Y \le 1000\).
• \(1 \le\) độ dài của M \(\le 1000\).
• Mỗi ký tự trong M là một chữ cái in hoa — N, E, S hoặc W.

Đ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
4 4 SSSS
3 0 SNSS
2 10 NSNNSN
0 1 S
2 7 SSSSSSSS

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

2
3 2 SSSW
4 0 NESW

Case #1: 4
Case #2: 4

Nguồn

Google Code Jam 2020, Vòng 1C, bài Overexcited Fan.

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

Overrandomized

Đề bài

Lưu ý: Mỗi khi đề bài nói một thứ được chọn ngẫu nhiên, điều đó có nghĩa là thứ ấy được chọn theo phân phối đều trên tất cả các khả năng hợp lệ và độc lập với mọi lựa chọn khác.

Công ty Banana Rocks Inc. vừa viết một dịch vụ sinh số ngẫu nhiên cao cấp trên nền tảng đám mây, được kỳ vọng sẽ trở thành tiêu chuẩn vàng mới về tính ngẫu nhiên.

Thiết kế ban đầu là một nhóm máy chủ sẽ nhận yêu cầu dưới dạng một số nguyên dương duy nhất \(M\) có không quá U chữ số thập phân, rồi trả về một số nguyên được chọn ngẫu nhiên trong đoạn từ \(1\) đến \(M\), kể cả hai đầu mút. Tuy nhiên, thay vì viết kết quả bằng các chữ số từ \(0\) đến \(9\) như thông thường, các máy chủ đã bị "ngẫu nhiên hóa quá mức". Mỗi máy chủ có một tập ngẫu nhiên gồm \(10\) chữ cái tiếng Anh in hoa đôi một khác nhau để dùng làm chữ số, cùng một ánh xạ ngẫu nhiên từ các chữ cái ấy tới các giá trị phân biệt trong khoảng từ \(0\) đến \(9\).

Mô tả chính thức của tình huống hiện tại như sau: mỗi máy chủ có một chuỗi chữ số \(D\) gồm đúng \(10\) chữ cái tiếng Anh in hoa khác nhau. Chuỗi chữ số xác định ánh xạ giữa các chữ cái và các chữ số hệ cơ số 10: ký tự thứ \(j\) tính từ trái sang của \(D\) (đánh số từ \(0\)) là chữ số hệ cơ số 10 có giá trị \(j\). Ví dụ, nếu \(D\) là CODEJAMFUN thì C biểu diễn chữ số \(0\), O biểu diễn chữ số \(1\) và N biểu diễn chữ số \(9\). Khi dùng chuỗi chữ số đó, số \(379009\) sẽ được mã hóa thành EFNCCN.

Khi nhận truy vấn thứ \(i\) với tham số nguyên \(M_i\), máy chủ:

• chọn ngẫu nhiên một số nguyên \(N_i\) trong đoạn từ \(1\) đến \(M_i\), kể cả hai đầu mút;
• viết số đó thành một chuỗi trong hệ cơ số 10 không có chữ số \(0\) ở đầu, dùng ký tự thứ \(j\) của \(D\) (đánh số từ \(0\)) làm chữ số có giá trị \(j\); và
• trả về chuỗi thu được làm phản hồi \(R_i\).

Chúng tôi đã thu thập một số dữ liệu mà chúng tôi tin rằng có thể dùng để khôi phục chuỗi chữ số bí mật \(D\) của từng máy chủ. Chúng tôi gửi \(10^4\) truy vấn đến mỗi máy chủ. Với mỗi truy vấn, chúng tôi chọn ngẫu nhiên một giá trị \(M_i\) trong đoạn từ \(1\) đến \(10^{\mathbf{U}}-1\), kể cả hai đầu mút, và nhận phản hồi \(R_i\), là một chuỗi có không quá U chữ cái tiếng Anh in hoa. Chúng tôi ghi lại các cặp \((M_i, \mathbf{R_i})\). Trong lúc chuyển các bản ghi này sang một thiết bị lưu trữ dữ liệu mới, giá trị của tất cả các số nguyên \(M_i\) trong bản ghi của một số máy chủ đã bị hỏng và không thể đọc được.

Bạn có thể giúp chúng tôi tìm chuỗi chữ số \(D\) của từng máy chủ không?

Dữ liệu vào

Dòng đầu tiên cho biết số lượng bộ test T. Sau đó là T bộ test. Mỗi bộ test chứa các bản ghi của một máy chủ và bắt đầu bằng một dòng chứa số nguyên duy nhất U, biểu thị rằng \(10^{\mathbf{U}}-1\) là cận trên (có tính cả cận) của miền mà từ đó chúng tôi chọn các số nguyên \(M_i\) để truy vấn máy chủ ấy. Tiếp theo là đúng \(10^4\) dòng. Mỗi dòng chứa một số nguyên \(Q_i\) (trong hệ cơ số 10, dùng các chữ số từ \(0\) đến \(9\) như thông thường) và một chuỗi \(R_i\), lần lượt biểu diễn truy vấn và phản hồi thứ \(i\). Nếu \(Q_i\) \(= -1\) thì số nguyên \(M_i\) được dùng cho truy vấn thứ \(i\) là không xác định. Nếu không, \(Q_i\) \(= M_i\).

Dữ liệu ra

Với mỗi bộ test, 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\)) và y là chuỗi chữ số \(D\) của máy chủ được xét trong bộ test x.

Ràng buộc

• \(1 \le \mathbf{T} \le 10\).
• \(D\) là một chuỗi gồm đúng \(10\) chữ cái tiếng Anh in hoa khác nhau, được chọn độc lập và theo phân phối đều từ tập tất cả các chuỗi như vậy.
• Với mọi \(i\), \(M_i\) được chọn độc lập và theo phân phối đều trong đoạn từ \(1\) đến \(10^{\mathbf{U}}-1\), kể cả hai đầu mút.
• Với mọi \(i\), \(N_i\) được chọn độc lập và theo phân phối đều trong đoạn từ \(1\) đến \(M_i\), kể cả hai đầu mút.
• Với mọi \(i\), \(R_i\) là biểu diễn trong hệ cơ số 10 của \(N_i\), dùng ký tự thứ \(j\) tính từ trái sang của \(D\) (đánh số từ \(0\)) làm chữ số có giá trị \(j\).

Phân nhóm

Test Set 1 (Hiển thị kết quả chấm)

• \(Q_i\) \(= M_i\) với mọi \(i\).
• U \(= 2\).

Test Set 2 (Hiển thị kết quả chấm)

• \(Q_i\) \(= M_i\) với mọi \(i\).
• U \(= 16\).

Test Set 3 (Hiển thị kết quả chấm)

• \(Q_i\) \(= -1\) với mọi \(i\).
• U \(= 16\).

Đ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
2
20 P
-------------------------------
Đã lược bỏ 9999 dòng dữ liệu vào.
Hãy dùng nút tải xuống ở phía trên
để xem toàn bộ dữ liệu vào mẫu.
-------------------------------

Case #1: TPFOXLUSHB

Nguồn

Google Code Jam 2020, Vòng 1C, bài Overrandomized.

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

Bạn vừa đến nhận việc bếp trưởng tại Nhà Bánh kếp Vô hạn và, như thường lệ, bắt gặp một thảm họa đang diễn ra! Các đầu bếp khác đã vô tình làm ra một số chiếc bánh kếp hình tròn khổng lồ, tất cả đều có cùng kích thước. Những chiếc bánh này quá lớn để phục vụ nguyên chiếc, nên họ đã bắt đầu chặt chúng thành các miếng (trong bài này, các miếng là những hình quạt tròn). Hiện tại, bạn có \(N\) miếng; miếng thứ \(i\) là một hình quạt có góc trong (góc ở tâm) bằng \(A_i\) nanođộ (một nanođộ bằng \(10^{-9}\) độ).

Có \(D\) thực khách đang chờ món. Mỗi thực khách muốn nhận đúng một miếng có cùng kích thước với miếng của mọi thực khách khác, nhưng họ không quan tâm kích thước đó cụ thể là bao nhiêu. Tuy nhiên, có thể không thực hiện được điều này bằng các miếng hiện có, nên bạn có thể cần thực hiện một hoặc nhiều nhát cắt theo bán kính.

Một nhát cắt biến một miếng hiện có với góc trong \(X\) thành hai miếng mới có góc trong \(Y\) và \(X-Y\). Bạn có thể làm vậy với bất kỳ \(0<Y<X\) nào, và các giá trị này không nhất thiết phải là số nguyên. Bạn có thể tiếp tục cắt một hoặc cả hai miếng mới này, rồi cứ thế tiếp tục.

Bạn được phép để thừa một hoặc nhiều miếng (với kích thước bất kỳ) mà không đưa cho thực khách; bạn có thể ăn chúng sau, vì thảm họa này đang khiến bạn lỡ mất bữa sáng của chính mình!

Hãy xác định tổng số nhát cắt ít nhất cần thực hiện để đáp ứng các thực khách.

Dữ liệu vào

Dòng đầu tiên chứa số bộ test \(T\). Tiếp theo là \(T\) bộ test. Mỗi bộ bắt đầu bằng một dòng chứa hai số nguyên \(N\) và \(D\): số miếng hiện có và số thực khách. Sau đó là một dòng nữa chứa \(N\) số nguyên \(A_1,A_2,\ldots,A_N\); số thứ \(i\) biểu diễn góc trong (tính bằng nanođộ) của miếng thứ \(i\).

Dữ liệu ra

Với mỗi bộ test, in một dòng chứa Case #x: y, trong đó x là số thứ tự bộ test (bắt đầu từ \(1\)), còn y là số nhát cắt nhỏ nhất cần thực hiện như mô tả ở trên.

Ràng buộc

• \(1\le T\le100\).
• \(1\le A_i<360\times10^9\) với mọi \(i\).

Phân nhóm

Test Set 1 (Phán quyết hiển thị)

• \(1\le N\le300\).
• \(2\le D\le3\).

Test Set 2 (Phán quyết hiển thị)

• \(1\le N\le300\).
• \(2\le D\le50\).

Test Set 3 (Phán quyết ẩn)

• Với đúng \(21\) bộ test, \(9000\le N\le10000\).
• Với đúng \(T-21\) bộ test, \(1\le N\le1000\).
• \(2\le D\le50\).

Đ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
1 3
1
5 2
10 5 359999999999 123456789 10
2 3
8 4
3 2
1 2 3

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

Nguồn

Google Code Jam 2020, Vòng 1C, bài Oversized Pancake Choppers.

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