Google Code Jam 2019 - Round 1B

Đề bài

Odin có một số chiếc nhẫn phép thuật có khả năng tự tạo ra bản sao. Mỗi chiếc "nhẫn X ngày" cứ sau mỗi \(X\) ngày kể từ ngày nó xuất hiện lại tạo ra thêm một chiếc nhẫn X ngày. Có sáu loại nhẫn: nhẫn 1 ngày, nhẫn 2 ngày, ..., cho đến nhẫn 6 ngày.

Ví dụ, một chiếc nhẫn 3 ngày xuất hiện vào ngày 0 sẽ không làm gì cho đến ngày 3, khi nó tạo ra thêm một chiếc nhẫn 3 ngày. Sau đó, vào ngày 6, mỗi chiếc trong hai chiếc nhẫn này sẽ tạo ra thêm một chiếc nhẫn 3 ngày, và quá trình cứ tiếp tục như vậy.

Bạn biết rằng Odin không có chiếc nhẫn nào trước ngày 0. Vào ngày 0, một số chiếc nhẫn xuất hiện. Cuối ngày 0, với mỗi \(1 \le i \le 6\), Odin có \(R_i\) chiếc nhẫn \(i\) ngày. Bạn biết rằng \(0 \le R_i \le 100\) với mọi \(i\), và có ít nhất một giá trị \(R_i\) dương.

May mắn thay, bạn còn có thể sử dụng giếng tri thức bí mật. Mỗi lần sử dụng, bạn có thể biết tổng số nhẫn Odin có vào cuối một ngày cụ thể từ ngày 1 đến ngày 500, kể cả hai đầu mút. Vì ngay cả chiếc giếng cũng chỉ chứa được hữu hạn thông tin, nó sẽ trả lời theo modulo \(2^{63}\)! Ngoài ra, bạn chỉ được sử dụng giếng tối đa W lần.

Mục tiêu của bạn là xác định Odin có bao nhiêu chiếc nhẫn thuộc mỗi loại vào cuối ngày 0 — tức là tìm tất cả các giá trị \(R_i\).

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 phần Bài toán tương tác trong 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 hai số nguyên T, số lượng bộ test, và W, số lần được phép sử dụng giếng tri thức trong mỗi bộ test. 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 W + 1 lượt trao đổi với bộ chấm. Bạn có thể thực hiện tối đa W lượt trao đổi có dạng sau:

• Chương trình in một dòng chứa một số nguyên duy nhất \(D\) trong đoạn từ 1 đến 500, kể cả hai đầu mút.
• Bộ chấm trả lời bằng một dòng chứa một số nguyên duy nhất: tổng số nhẫn Odin có vào cuối ngày \(D\), theo modulo \(2^{63}\). 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.

Sau từ 0 đến W lượt trao đổi như 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 dòng chứa sáu số nguyên \(R_1\), \(R_2\), \(R_3\), \(R_4\), \(R_5\), \(R_6\), trong đó \(R_i\) biểu thị số nhẫn \(i\) ngày Odin có vào cuối ngày 0.
• Bộ chấm trả lời bằng một dòng chứa một số nguyên duy nhất: 1 nếu câu trả lời của bạn đúng, và -1 nếu câu trả lời sai (hoặc nếu bạn đã gửi một dòng sai định dạng).

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

Ràng buộc

\(1 \le \mathbf{T} \le 50\).

Phân nhóm

Test set 1 (Hiển thị)

\(\mathbf{W} = 6\).

Test set 2 (Ẩn)

\(\mathbf{W} = 2\).

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 tra cục bộ hoặc trên nền tảng của ban tổ chức. Để kiểm tra cục bộ, bạn cần chạy công cụ song song với chương trình của mình; có thể dùng trình chạy tương tác của ban tổ chức 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 ấy và xem 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 sử dụng công cụ kiểm thử được viết trong các chú thích bên trong công cụ. Bạn nên bổ sung các bộ test của riêng mình. Xin lưu ý rằng tuy công cụ kiểm thử được thiết kế để mô phỏng hệ thống chấm, nó KHÔNG phải 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 ban tổ chức.

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

Ví dụ

  t, w = readline_int_list()   // Đọc 50 vào t và 6 vào w
  printline 3 to stdout        // Hỏi về ngày 3.
  flush stdout
  n = readline_int()           // Đọc 15 vào n.
  printline 1 to stdout        // Hỏi về ngày 1.
  flush stdout
  n = readline_int()           // Đọc 7 vào n.
  printline 1 1 1 3 0 0 to stdout
  flush stdout                 // Đưa ra một dự đoán dù vẫn có thể truy vấn giếng
                               // thêm tối đa bốn lần nữa.
  verdict = readline_int()     // Đọc -1 vào verdict (bộ chấm đã quyết định rằng
                               // lời giải của chúng 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 1B, bài Draupnir.

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

Vào tư thế! Charles và Delila sắp đối đầu trong trận chung kết của giải đấu kiếm Swordmaster.

Dọc theo một bức tường của đấu trường có một giá đựng \(N\) loại kiếm khác nhau; các loại kiếm được đánh số từ \(1\) đến \(N\). Với tư cách trọng tài chính, bạn sẽ chọn một cặp số nguyên \((L, R)\) (với \(1 \le L \le R \le N\)), và chỉ các loại kiếm từ loại thứ \(L\) đến loại thứ \(R\) (tính cả hai đầu) mới được sử dụng trong trận đấu.

Các loại kiếm khác nhau được sử dụng theo những cách khác nhau, và giỏi dùng một loại kiếm không nhất thiết có nghĩa là giỏi dùng một loại khác! Kỹ năng của Charles và Delila với loại kiếm thứ \(i\) lần lượt là \(C_i\) và \(D_i\). Mỗi người sẽ xem xét các loại kiếm mà bạn cho phép sử dụng, rồi chọn loại mà mình thành thạo nhất. Nếu có nhiều loại kiếm được phép mà một đấu thủ có kỹ năng ngang nhau, đồng thời mức kỹ năng đó cao hơn kỹ năng với mọi loại được phép khác, đấu thủ sẽ chọn ngẫu nhiên một trong các loại tốt ngang nhau đó. Charles và Delila có thể chọn cùng một loại kiếm; điều này không thành vấn đề vì mỗi loại đều có nhiều bản sao.

Trận đấu công bằng nếu trị tuyệt đối của hiệu giữa kỹ năng dùng loại kiếm Charles chọn và kỹ năng dùng loại kiếm Delila chọn không vượt quá \(K\). Để trận đấu luôn hấp dẫn, bạn muốn biết có bao nhiêu cặp \((L, R)\) khác nhau tạo ra một trận đấu công bằng.

Dữ liệu vào

Dòng đầu 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 \(N\) và \(K\) như trên. Hai dòng tiếp theo lần lượt chứa \(N\) số nguyên \(C_i\) biểu thị kỹ năng của Charles với từng loại kiếm và \(N\) số nguyên \(D_i\) biểu thị kỹ năng của Delila.

Dữ liệu ra

Với mỗi bộ test, in một dòng dạng Case #x: y, trong đó x là số thứ tự bộ test (bắt đầu từ \(1\)) và y là số cách chọn tạo ra một trận đấu công bằng.

Ràng buộc

• \(1 \le T \le 100\).
• \(0 \le K \le 10^5\).
• \(0 \le C_i \le 10^5\) với mọi \(i\).
• \(0 \le D_i \le 10^5\) với mọi \(i\).

Phân nhóm

Test set 1 (Hiển thị)

• \(1 \le N \le 100\).

Test set 2 (Ẩn)

• \(N = 10^5\) trong đúng \(8\) bộ test.
• \(1 \le N \le 1000\) trong tất cả các bộ test còn lại ngoài \(8\) bộ test trên.

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

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

Nguồn

Google Code Jam 2019, Vòng 1B, bài Fair Fight.

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ó rất nhiều hàng quán đường phố tuyệt vời ở Manhattan, nhưng chắc chắn nơi có đồ ăn ngon nhất chính là xe bánh crepe Code Jam!

Bạn muốn tìm chiếc xe, nhưng ngoài việc biết nó nằm tại một giao lộ nào đó, bạn không biết chính xác nó ở đâu. Bạn tin rằng mọi người từ khắp Manhattan hiện đang đi về phía giao lộ ấy, vì vậy bạn sẽ cố xác định giao lộ mà nhiều người đang đi về phía đó nhất.

Trong phạm vi bài toán này, Manhattan là một lưới đều có các trục thẳng theo hướng la bàn và mỗi trục được giới hạn từ \(0\) đến \(Q\), kể cả hai đầu. Các đường phố theo hướng tây–đông tương ứng với các đường lưới \(y = 0, y = 1, y = 2, \ldots, y = Q\); các đường phố theo hướng nam–bắc tương ứng với các đường lưới \(x = 0, x = 1, x = 2, \ldots, x = Q\); và mọi người chỉ di chuyển dọc theo những con phố này. Những điểm mà các đường gặp nhau — chẳng hạn \((0, 0)\) và \((1, 2)\) — là các giao lộ. Khoảng cách ngắn nhất giữa hai giao lộ được đo bằng khoảng cách Manhattan, tức là tổng độ chênh lệch tuyệt đối theo phương ngang và phương dọc giữa hai cặp tọa độ.

Bạn biết vị trí của \(P\) người, tất cả đều đang đứng tại các giao lộ, cùng hướng la bàn mà mỗi người đang đi: bắc (tung độ \(y\) tăng), nam (tung độ \(y\) giảm), đông (hoành độ \(x\) tăng), hoặc tây (hoành độ \(x\) giảm). Một người được xem là đang đi về phía một giao lộ nếu hướng di chuyển hiện tại của họ nằm trên một đường đi ngắn nhất đến giao lộ đó trong lưới Manhattan. Chẳng hạn, nếu một người ở \((x_0, y_0)\) đang đi về phía bắc, thì họ đang đi về phía tất cả các giao lộ \((x, y)\) thỏa mãn \(y > y_0\).

Bạn cho rằng xe bánh crepe nằm tại giao lộ mà nhiều người đang đi về phía đó nhất. Hơn nữa, bạn tin rằng xe bánh crepe có nhiều khả năng xuất hiện ở phần phía nam và phía tây của đảo hơn. Vì thế, nếu có nhiều giao lộ như vậy, bạn sẽ chọn giao lộ có hoành độ \(x\) không âm nhỏ nhất; nếu vẫn có nhiều giao lộ có cùng hoành độ đó, bạn chọn giao lộ có tung độ \(y\) không âm nhỏ nhất trong số chúng. Bạn sẽ chọn giao lộ nào?

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ộ test bắt đầu bằng một dòng chứa hai số nguyên \(P\) và \(Q\): số người và giá trị lớn nhất có thể có của một hoành độ hoặc tung độ tại Manhattan như mô tả ở trên. Sau đó có thêm \(P\) dòng. Dòng thứ \(i\) chứa hai số nguyên \(X_i\) và \(Y_i\), là vị trí hiện tại (góc phố) của một người, và một ký tự \(D_i\), là hướng người đó đang đi. \(D_i\) là một trong các chữ cái in hoa N, S, E hoặc W, lần lượt biểu thị hướng bắc, nam, đông và tây.

Dữ liệu ra

Với mỗi bộ test, in một dòng Case #t: x y, trong đó t là số thứ tự bộ test (bắt đầu từ \(1\)), còn x và y lần lượt là hoành độ và tung độ của giao lộ mà bạn cho rằng xe bánh crepe đang ở đó.

Ràng buộc

• \(1 \le T \le 100\).
• \(1 \le P \le 500\).
• \(0 \le X_i \le Q\) với mọi \(i\).
• \(0 \le Y_i \le Q\) với mọi \(i\).
• Với mọi \(i\), nếu \(X_i = 0\) thì \(D_i \ne\) W.
• Với mọi \(i\), nếu \(Y_i = 0\) thì \(D_i \ne\) S.
• Với mọi \(i\), nếu \(X_i = Q\) thì \(D_i \ne\) E.
• Với mọi \(i\), nếu \(Y_i = Q\) thì \(D_i \ne\) N.

Phân nhóm

Test Set 1 (Công khai)

\(Q = 10\).

Test Set 2 (Ẩn)

\(Q = 10^5\).

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

3
1 10
5 5 N
4 10
2 4 N
2 6 S
1 5 E
3 5 W
8 10
0 2 S
0 3 N
0 3 N
0 4 N
0 5 S
0 5 S
0 8 S
1 5 W

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

Nguồn

Google Code Jam 2019, Vòng 1B, bài Manhattan Crepe Cart.

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