Blindfolded Bullseye

Đề bài

Gary có một bức tường hình vuông lớn, cao đúng \(2 \times 10^9\) nanômét và rộng \(2 \times 10^9\) nanômét. Gary đặt một tấm bia phi tiêu trên tường. Tấm bia có dạng hình tròn và bán kính nằm trong đoạn từ A đến B nanômét, kể cả hai đầu mút. Tấm bia nằm hoàn toàn trong phạm vi bức tường, nhưng có thể tiếp xúc với các cạnh tường. Khoảng cách từ tâm bia đến mỗi cạnh tường là một số nguyên nanômét.

Gary mời cô bạn Mika đến chơi một trò thú vị. Gary bịt mắt Mika và thách cô ném một phi tiêu trúng tâm bia. Để giúp cô, mỗi khi Mika ném phi tiêu vào tường, Gary sẽ cho biết phi tiêu có trúng tấm bia hay không.

Mika không biết tấm bia nằm ở đâu trên tường, nhưng vì rất giỏi ném phi tiêu, cô có thể ném chính xác đến từng nanômét. Nói cách khác, cô có thể ngắm và ném trúng chính xác bất kỳ điểm nào có khoảng cách nguyên nanômét đến mỗi cạnh tường. Ngay sau mỗi lần ném, Gary cho cô biết phi tiêu đã trúng tâm bia, trúng một phần khác của bia, hay trượt hoàn toàn và cắm vào phần tường trống.

Bạn có thể giúp Mika ném trúng tâm bia mà không dùng quá 300 phi tiêu không?

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

Ban đầu, chương trình phải đọc một dòng chứa ba số nguyên T, A và B, lần lượt biểu thị số bộ test và giá trị nhỏ nhất, lớn nhất (đều tính cả hai đầu mút) của bán kính tấm bia, theo đơn vị nanômét. (Lưu ý rằng A và B giống nhau cho mọi bộ test trong cùng một nhóm test.) Sau đó, bạn cần xử lý T bộ test.

Ta biểu diễn các điểm mà phi tiêu có thể được ngắm tới bằng các cặp \((x, y)\), trong đó \(x\) và \(y\) là các số nguyên từ \(-10^9\) đến \(10^9\), kể cả hai đầu mút. Cặp \((x, y)\) là điểm cách cạnh trái của tường \(x + 10^9\) nanômét và cách cạnh dưới của tường \(y + 10^9\) nanômét. Vì vậy, điểm \((0, 0)\) nằm chính xác tại tâm bức tường.

Với mỗi bộ test, bán kính \(R\) và tâm \((X, Y)\) của tấm bia được chọn bí mật. Các số nguyên \(R\), \(X\) và \(Y\) được bộ chấm chủ đích lựa chọn (không phải ngẫu nhiên) trong phạm vi giới hạn. Với mỗi bộ test, bạn cần thực hiện tối đa 300 lượt trao đổi với bộ chấm. Chương trình của bạn đóng vai Mika, còn chương trình chấm đóng vai Gary. Mỗi lượt gồm việc Mika chọn vị trí ném phi tiêu và Gary cung cấp thông tin về vị trí đó.

Ở lượt thứ \(i\), trước tiên chương trình in một dòng chứa hai số nguyên \(X_i\) và \(Y_i\), cả hai đều từ \(-10^9\) đến \(10^9\), kể cả hai đầu mút. Sau đó, bộ chấm trả lời bằng một dòng chứa một trong các giá trị:

• CENTER nếu \(X_i = X\) và \(Y_i = Y\).
• HIT nếu \(0 < (X - X_i)^2 + (Y - Y_i)^2 \le R^2\).
• MISS trong mọi trường hợp còn lại.

Sau khi gửi CENTER, bộ chấm sẽ chờ lượt đầu tiên của bộ test tiếp theo, nếu có.

Nếu bạn in một dòng sai định dạng hoặc chứa giá trị ngoài phạm vi, bộ chấm trả lời WRONG. Nếu đã diễn ra 300 lượt (bao gồm 300 phản hồi) mà bạn chưa nhận CENTER, hoặc nếu từng nhận WRONG, bộ chấm sẽ kết thúc toàn bộ giao tiếp, chờ chương trình của bạn kết thúc và đưa ra Wrong Answer. Ngược lại, sau khi gửi CENTER thứ T, bộ chấm kết thúc giao tiếp, chờ chương trình kết thúc và đưa ra Correct. Nếu trong lúc chờ mà chương trình vượt giới hạn thời gian hoặc bộ nhớ, phán quyết tương ứng sẽ được đưa ra. (Các phán quyết không phải thông báo gửi tới chương trình.)

Ràng buộc

• \(1 \le \mathbf{T} \le 20\).
• \(\mathbf{A} \le R \le \mathbf{B}\).
• \(-10^9 + R \le X \le 10^9 - R\).
• \(-10^9 + R \le Y \le 10^9 - R\).

Phân nhóm

Nhóm test 1 (phán quyết hiển thị)

\(\mathbf{A} = \mathbf{B} = 10^9 - 5\).

Nhóm test 2 (phán quyết hiển thị)

\(\mathbf{A} = \mathbf{B} = 10^9 - 50\).

Nhóm test 3 (phán quyết ẩn)

\(\mathbf{A} = 10^9 / 2\).
\(\mathbf{B} = 10^9\).

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 thử cục bộ hoặc trên nền tảng của chúng tôi. Để kiểm thử cục bộ, bạn cần chạy công cụ song song với mã nguồn; có thể dùng trình chạy tương tác của chúng tôi. Để biết thêm thông tin, hãy đọc hướng dẫn trong chú thích của tệp ấy và xem mục Bài toán tương tác trong phần câu hỏi thường gặp.

Hướng dẫn sử dụng công cụ nằm trong các chú thích bên trong công cụ. Chúng tôi khuyến khích bạn tự bổ sung bộ test. Xin lưu ý rằng dù được thiết kế để mô phỏng hệ thống chấm, công cụ này KHÔNG PHẢI hệ thống chấm thật và có thể hoạt động khác. Nếu mã nguồn vượt qua công cụ nhưng thất bại trên bộ chấm thật, hãy kiểm tra mục Lập trình trong phần câu hỏi thường gặp để bảo đảm bạn dùng cùng trình biên dịch với chúng tôi.

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

Trình chạy tương tác đã được thay đổi sau Vòng loại năm 2020. Hãy chắc chắn tải phiên bản mới nhất.

Ví dụ

  // Dòng sau đọc 20 vào t và 999999995 vào a và b.
  t, a, b = readline_int_list()
  // Bộ chấm bí mật chọn R = 999999995 (không còn lựa chọn khác) và X = -1,
  // Y = 3 (ở đây có quyền lựa chọn). (Nhóm test 1 thực tế
  // không nhất thiết dùng các giá trị trong ví dụ này.)
  // Ta thử ném vào góc trên trái của tường, và tấm bia
  // không phủ lên điểm đó.
  printline -1000000000 1000000000 to stdout
  flush stdout
  r = readline_string()  // đọc MISS.
  // Ta thử ném vào tâm tường. Lần này trúng tấm bia,
  // nhưng không trúng tâm bia.
  printline 0 0 to stdout
  flush stdout
  r = readline_string()  // đọc HIT.
  // Ta chọn cực kỳ may mắn và ném đúng vào tâm bia.
  printline -1 3 to stdout
  flush stdout
  r = readline_string()  // đọc CENTER.
  // Bộ chấm bắt đầu bộ test tiếp theo. Nó bí mật chọn R = 999999995
  // và X = 5, Y = 5.
  // Ta vô tình ném phi tiêu ra ngoài phạm vi cho phép.
  printline -1234567890 1234567890 to stdout
  flush stdout
  r = readline_string()  // đọc WRONG.
  exit  // thoát để tránh lỗi TLE không rõ nguyên nhân.

Nguồn

Google Code Jam 2020, Vòng 1B, bài Blindfolded Bullseye.

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 vừa nhận được món quà tuyệt vời nhất từ trước đến nay: một cây gậy Expogo. Bạn có thể đứng trên nó và dùng nó để thực hiện những cú nhảy ngày càng xa.

Hiện tại, bạn đang đứng tại điểm \((0, 0)\) trong sân sau hai chiều vô hạn và muốn đến điểm đích \((X, Y)\) có tọa độ nguyên bằng ít cú nhảy nhất có thể. Bạn phải tiếp đất chính xác tại điểm đích; chỉ nhảy qua nó là chưa đủ.

Mỗi lần dùng gậy Expogo, bạn chọn một hướng chính: bắc, nam, đông hoặc tây. Cú nhảy thứ \(i\) đưa bạn đi \(2^{i-1}\) đơn vị theo hướng đã chọn; vì vậy các cú nhảy lần lượt dài \(1, 2, 4,\ldots\) đơn vị.

Cho điểm đích \((X, Y)\), hãy xác định liệu có thể đến đó hay không; nếu có, hãy chỉ ra cách thực hiện bằng ít cú nhảy nhất có thể.

Dữ liệu vào

Dòng đầu chứa số bộ test \(T\). Tiếp theo là \(T\) bộ test, mỗi bộ gồm một dòng chứa hai số nguyên \(X\) và \(Y\), là tọa độ điểm đích.

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 thể đến đích. Nếu có thể, y phải là chuỗi gồm một hoặc nhiều ký tự N (bắc), S (nam), E (đông) hoặc W (tây), biểu diễn theo thứ tự hướng của các cú nhảy. Chuỗi phải đưa bạn đến đích sau cú nhảy cuối và phải ngắn nhất có thể.

Ràng buộc

• \((X,Y)\ne(0,0)\).

Phân nhóm

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

• \(1\le T\le80\).
• \(-4\le X\le4\).
• \(-4\le Y\le4\).

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

• \(1\le T\le100\).
• \(-100\le X\le100\).
• \(-100\le Y\le100\).

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

• \(1\le T\le100\).
• \(-10^9\le X\le10^9\).
• \(-10^9\le Y\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ụ

2 3
-2 -3
3 0
-1 1
???+ success "Output"sample
Case #1: SEN
Case #2: NWS
Case #3: EE
Case #4: IMPOSSIBLE
```

??? "Giải thích"
    Trong trường hợp mẫu số 1, bạn có thể nhảy về nam từ $(0,0)$ đến $(0,-1)$, rồi về đông đến $(2,-1)$, rồi về bắc đến $(2,3)$.

    Không thể có lời giải hiệu quả hơn (không quá hai bước), vì cần ít nhất $2+3=5$ đơn vị khoảng cách để đến đích, còn tổng độ dài hai cú nhảy đầu chỉ là $3$.

    Trường hợp mẫu số 2 giống trường hợp mẫu số 1 nhưng phản xạ qua cả hai trục, nên đáp án thu được bằng cách phản xạ mọi hướng trong đáp án mẫu số 1.

    Trong trường hợp mẫu số 3, `EWE` không hợp lệ dù đến được đích, vì có cách dùng ít cú nhảy hơn.

    Bạn hãy tự xác định vì sao không thể đến đích trong trường hợp mẫu số 4.

Nguồn

Google Code Jam 2020, Vòng 1B, bài Expogo.

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

Join the Ranks

Đề bài

Gần đây, bạn có một bộ bài mới. Mỗi lá mang một hạng, là số nguyên từ 1 đến \(R\), và một chất, là số nguyên từ 1 đến \(S\). Với mỗi cặp hạng và chất có đúng một lá bài, nên bộ bài có tổng cộng \(R \times S\) lá. Ta ký hiệu lá bài hạng \(r\), chất \(s\) là \((r,s)\).

Vì còn mới, bộ bài được xếp từ trên xuống dưới theo chất tăng dần; nếu cùng chất thì theo hạng tăng dần. Cụ thể: \((1,1)\), \((2,1)\), ..., \((R,1)\), rồi \((1,2)\), \((2,2)\), ..., \((R,2)\), và cứ thế đến \((R,S)\). Ví dụ, với \(R=4\), \(S=2\), thứ tự ban đầu là \((1,1),(2,1),(3,1),(4,1),(1,2),(2,2),(3,2),(4,2)\).

Bạn muốn sắp xếp lại bộ bài theo hạng: đặt mọi lá cùng hạng cạnh nhau và các hạng theo thứ tự tăng dần. Bạn không quan tâm thứ tự các chất trong mỗi hạng. Chẳng hạn, với \(R=4\), \(S=2\), một thứ tự mới hợp lệ là \((1,2),(1,1),(2,1),(2,2),(3,1),(3,2),(4,2),(4,1)\).

Bạn đang học nấu ăn nên muốn sắp xếp bộ bài mà không đặt những chiếc xẻng lật xuống. Bạn quyết định chỉ dùng thao tác nhiều bước sau:

• Lấy một hoặc nhiều lá trên cùng, đặt riêng thành chồng A.
• Lấy một hoặc nhiều lá từ vị trí trên cùng mới, đặt riêng thành chồng B.
• Đặt chồng A lên bộ bài, rồi đặt chồng B lên trên bộ bài mới.

Thao tác hoán đổi phần A và B mà không ảnh hưởng các lá nằm sâu hơn trong bộ bài (nếu có).

Tiếp tục ví dụ \(R=4\), \(S=2\): nếu nước đầu chọn 3 lá cho A và 2 lá cho B, ta có:
A: \((1,1),(2,1),(3,1)\),
B: \((4,1),(1,2)\), và
Phần còn lại: \((2,2),(3,2),(4,2)\).
Sau khi đặt A lên bộ bài rồi B lên A, thứ tự mới là \((4,1),(1,2),(1,1),(2,1),(3,1),(2,2),(3,2),(4,2)\).

Cho \(R\) và \(S\), hãy tìm một dãy thao tác sắp xếp bộ bài theo hạng như trên với số thao tác ít nhất có thể.

Dữ liệu vào

Dòng đầu là số bộ test \(T\). Mỗi dòng trong \(T\) dòng tiếp theo chứa hai số nguyên \(R,S\), lần lượt là số hạng và số chất.

Dữ liệu ra

Với mỗi bộ test, in Case #x: y, trong đó x là số thứ tự bộ test (từ 1), còn y là số thao tác tối thiểu. Sau đó in thêm y dòng a_i b_i: ở thao tác thứ \(i\), lấy trước \(a_i\) lá làm A rồi lấy \(b_i\) lá tiếp theo làm B.

Ràng buộc

Phân nhóm

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

• \(T=12\).
• \(2 \le R \le 5\).
• \(2 \le S \le 7\).
• \(R \times S \le 14\).

Test Set 2 (phán quyết ẩn)

• \(1 \le T \le 100\).
• \(2 \le R \le 40\).
• \(2 \le S \le 40\).

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

Case #1: 1
2 1
Case #2: 2
3 2
2 1
Case #3: 2
2 3
2 2

Nguồn

Google Code Jam 2020, Vòng 1B, bài Join the Ranks.

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