Bathroom Stalls

Một nhà vệ sinh có \(N+2\) buồng trên một hàng. Hai buồng ngoài cùng bên trái và bên phải bị nhân viên bảo vệ chiếm vĩnh viễn; \(N\) buồng còn lại dành cho người dùng.

Mỗi khi có người bước vào, họ cố chọn buồng xa những người khác nhất. Để tránh nhập nhằng, họ tuân theo quy tắc tất định. Với mỗi buồng trống \(S\), tính \(L_S\) và \(R_S\), lần lượt là số buồng trống nằm giữa \(S\) và buồng có người gần nhất về bên trái và bên phải. Trước hết chỉ xét những \(S\) tối đa hóa \(\min(L_S,R_S)\). Nếu chỉ có một buồng thì chọn nó; nếu còn hòa, trong số ấy chọn buồng tối đa hóa \(\max(L_S,R_S)\). Nếu vẫn còn nhiều buồng hòa nhau, chọn buồng ngoài cùng bên trái.

\(K\) người sắp lần lượt bước vào; mỗi người chọn xong trước khi người kế tiếp đến và không ai rời đi. Khi người cuối cùng chọn buồng \(S\), hai giá trị \(\max(L_S,R_S)\) và \(\min(L_S,R_S)\) bằng bao nhiêu?

Dữ liệu vào

Dòng đầu chứa số test \(T\). Tiếp theo là \(T\) dòng, mỗi dòng mô tả một test bằng hai số nguyên \(N,K\) như trên.

Dữ liệu ra

Với mỗi test, in Case #x: y z, trong đó x là số thứ tự test, y là \(\max(L_S,R_S)\) và z là \(\min(L_S,R_S)\) mà người thứ \(K\) tính cho buồng đã chọn.

Ràng buộc

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

Phân nhóm

• Small Dataset 1 (Test Set 1, hiển thị): \(1\le N\le1000\).
• Small Dataset 2 (Test Set 2, hiển thị): \(1\le N\le10^6\).
• Large Dataset (Test Set 3, ẩn): \(1\le N\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ụ

5
4 2
5 2
6 2
1000 1000
1000 1

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

Nguồn

Google Code Jam 2018, Vòng luyện tập, bài Bathroom Stalls.

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

Number Guessing

Đây là một bài kinh điển, được đưa vào chủ yếu để bạn làm quen với hệ thống chấm tương tác. Bộ chấm nghĩ ra một số nguyên \(P\) trong khoảng \((A,B]\), tức \(A<P\le B\). Bạn có \(N\) lượt đoán; sau mỗi lần đoán sai, bộ chấm cho biết \(P\) lớn hơn hay nhỏ hơn số vừa đoán.

Nếu gặp sự cố kỹ thuật ảnh hưởng đến việc tham gia Practice Session, hãy gửi thư ngay tới [email protected]. Ban tổ chức chỉ hỗ trợ ở mức hạn chế trong phiên nhưng sẽ phản hồi sớm nhất có thể. Với mọi phản hồi khác, họ mời thí sinh gửi suy nghĩ và đề xuất qua biểu mẫu phản hồi sau Practice Session.

Dữ liệu vào

Khác bài chuẩn, input được bộ chấm tương tác gửi dần qua đầu vào chuẩn theo giao thức dưới đây, không phải một tệp cố định biết trước.

Dữ liệu ra

Mọi thông tin chương trình muốn gửi cho bộ chấm phải được viết ra đầu ra chuẩn theo giao thức dưới đây. Nội dung ghi ra lỗi chuẩn bị bỏ qua, nhưng vẫn có thể tốn bộ nhớ và bị tính vào giới hạn bộ nhớ.

Giao thức tương tác

Ban đầu, đọc một dòng chứa số nguyên \(T\). Sau đó xử lý lần lượt \(T\) test. Với mỗi test:

1. Đọc một dòng chứa hai số nguyên \(A,B\), là cận dưới loại trừ và cận trên bao gồm.
2. Đọc một dòng chứa số nguyên \(N\), số lượt đoán tối đa.
3. Thực hiện nhiều nhất \(N\) lần trao đổi. Mỗi lần, in một dòng chứa duy nhất số nguyên \(Q\), là dự đoán, rồi flush đầu ra ngay trước khi chờ phản hồi.
4. Đọc một từ do bộ chấm trả về: CORRECT nếu \(Q=P\), TOO_SMALL nếu \(Q<P\), hoặc TOO_BIG nếu \(Q>P\). Nếu chưa đúng, có thể tiếp tục lượt trao đổi kế tiếp.

Nhiều ngôn ngữ mặc định đệm output, nên nếu không flush trước khi đọc phản hồi, cả hai tiến trình có thể cùng chờ nhau; FAQ về bài tương tác giải thích thêm về thao tác flush. Nếu output sai định dạng, dự đoán ngoài miền hoặc có lỗi tương tự, bộ chấm gửi WRONG_ANSWER rồi ngừng gửi mọi dữ liệu. Chương trình phải thoát ngay khi nhận phản hồi này; nếu tiếp tục chờ input, nó sẽ treo và cuối cùng nhận Time Limit Exceeded thay vì verdict lỗi thích hợp.

Nếu giải được test trong \(N\) lượt, bộ chấm gửi CORRECT, rồi gửi dòng \(A,B\) của test tiếp theo nếu còn. Nếu hết \(N\) lượt mà chưa giải được, bộ chấm gửi WRONG_ANSWER và dừng. Sau khi nhận CORRECT cho test cuối, không được in thêm gì; nếu vẫn tiếp tục ghi stdout, bài sẽ bị Wrong Answer.

Ràng buộc

• \(1\le T\le20\).
• \(A=0\).
• \(N=30\).

Phân nhóm

• Test Set 1 (hiển thị): \(B=30\).
• Test Set 2 (ẩn): \(B=10^9\).

Ví dụ

  t = readline_int()         // reads 3 into t
  a, b = readline_two_int()  // reads 0 into a and 30 into b; note that 0 30 is one line
  n = readline_int()         // reads 30 into n
  printline 30 to stdout     // guesses 30
  flush stdout
  string s = readline()      // because 30 > 9, reads TOO_BIG into s
  printline 5 to stdout      // guesses 5
  flush stdout
  s = readline()             // reads TOO_SMALL into s since 5 < 9
  printline 10 to stdout     // guesses 10
  flush stdout
  s = readline()             // reads TOO_BIG into s since 10 > 9
  printline 9 to stdout      // guesses 9
  flush stdout
  s = readline()             // reads CORRECT into s

  a, b = readline_two_int()  // reads 0 into a and 30 into b; note that 0 30 is one line
  n = readline_int()         // reads 30 into n
  printline 31 to stdout     // guesses 31
  flush stdout
  string s = readline()      // reads WRONG_ANSWER
  a, b = readline_two_int()  // tries to read for the third test case but hangs since
                             // judge has stopped sending info to stdin

  a, b = readline_two_int()  // reads 0 into a and 30 into b; note that 0 30 is one line
  n = readline_int()         // reads 30 into n
  printline 31 to stdout     // guesses 31
  flush stdout
  string s = readline()      // reads WRONG_ANSWER
  exit                       // receives a Wrong Answer judgment

Nguồn

Google Code Jam 2018, Vòng luyện tập, bài Number Guessing.

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

Senate Evacuation

Một đám cháy nhỏ bùng lên trong phòng thượng viện và mọi người phải sơ tán!

Mỗi thượng nghị sĩ trong phòng thuộc một trong \(N\) đảng chính trị, được đặt tên theo \(N\) chữ cái in hoa đầu tiên của bảng chữ cái tiếng Anh. Cửa thoát hiểm đủ rộng cho nhiều nhất hai người, nên mỗi bước bạn có thể đưa một hoặc hai thượng nghị sĩ ra ngoài.

Quy tắc thượng viện cho phép những người còn trong phòng bỏ phiếu cho bất kỳ dự luật nào vào bất kỳ lúc nào, kể cả giữa cuộc sơ tán. Vì vậy, sau mọi bước, không đảng nào được có đa số tuyệt đối: số người của một đảng không bao giờ được lớn hơn một nửa tổng số người còn lại.

Hãy xây dựng một kế hoạch sơ tán; thượng viện đang trông cậy vào bạn!

Dữ liệu vào

Dòng đầu chứa số test \(T\). Mỗi test gồm hai dòng. Dòng đầu chứa \(N\), số đảng. Dòng thứ hai chứa \(N\) số nguyên \(P_1,P_2,\ldots,P_N\), trong đó \(P_i\) là số thượng nghị sĩ của đảng mang chữ cái thứ \(i\).

Dữ liệu ra

Với mỗi test, in Case #x: y, trong đó x là số thứ tự test và y là kế hoạch sơ tán. Kế hoạch là danh sách chỉ dẫn cách nhau bởi dấu cách theo đúng thứ tự thực hiện; mỗi chỉ dẫn gồm một hoặc hai chữ cái, biểu diễn đảng của những người rời phòng ở bước đó.

Đề bảo đảm có ít nhất một kế hoạch hợp lệ. Nếu có nhiều kế hoạch, có thể in bất kỳ kế hoạch nào.

Ràng buộc

• \(1\le T\le50\).
• Trước khi sơ tán, không đảng nào có đa số tuyệt đối.
• \(1\le P_i\le1000\) với mọi \(i\).

Phân nhóm

• Small Dataset (Test Set 1, hiển thị): \(2\le N\le3\) và \(\sum_iP_i\le9\).
• Large Dataset (Test Set 2, ẩn): \(2\le N\le26\) và \(\sum_iP_i\le1000\).

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

Case #1: AB BA
Case #2: AA BC C BA
Case #3: C C AB
Case #4: BA BB CA

Nguồn

Google Code Jam 2018, Vòng luyện tập, bài Senate Evacuation.

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

Steed 2: Cruise Control

Annie là tài xế xe buýt với công việc rất căng thẳng. Cô thử thư giãn bằng một chuyến du thuyền Caribe nhưng chuyến đi cũng đầy áp lực, nên gần đây cô chuyển sang cưỡi ngựa.

Hôm nay Annie cưỡi ngựa về phía đông trên một con đường một chiều dài và hẹp chạy từ tây sang đông. Cô đang ở kilômét 0, đích ở kilômét \(D\); số kilômét tăng dần về phía đông.

Có \(N\) con ngựa khác cũng đi về phía đông, sẽ tiếp tục đi mãi và hiện đều nằm giữa Annie và đích. Ngựa thứ \(i\) ban đầu ở kilômét \(K_i\) và chạy với tốc độ tối đa \(S_i\) km/h.

Ngựa rất lịch sự: một con \(H_1\) không vượt lên trước con \(H_2\) vốn xuất phát phía trước nó. Nhiều ngựa có thể cùng vị trí trong bất kỳ khoảng thời gian nào và có thể coi mỗi con là một điểm. Các ngựa khác Annie chạy tốc độ tối đa, trừ khi một con nhanh \(H_1\) bắt kịp con chậm hơn \(H_2\), lúc đó \(H_1\) giảm tốc để bằng \(H_2\).

Ngựa của Annie không có tốc độ tối đa và có thể chạy ở bất kỳ tốc độ nào cô chọn, miễn không vượt ngựa khác. Để chuyến đi êm ái, Annie muốn dùng một tốc độ “cruise control” không đổi trong toàn bộ hành trình từ vị trí hiện tại tới đích. Tốc độ lớn nhất hợp lệ là bao nhiêu?

Dữ liệu vào

Dòng đầu chứa số test \(T\). Mỗi test bắt đầu bằng hai số nguyên \(D,N\), lần lượt là vị trí đích và số ngựa khác trên đường. Tiếp theo là \(N\) dòng; dòng thứ \(i\) chứa \(K_i,S_i\), vị trí ban đầu và tốc độ tối đa của ngựa thứ \(i\).

Dữ liệu ra

Với mỗi test, in Case #x: y, trong đó x là số thứ tự test và y là tốc độ không đổi lớn nhất (km/h) Annie có thể dùng mà không vượt ngựa khác. Kết quả được chấp nhận nếu sai số tuyệt đối hoặc tương đối không quá \(10^{-6}\).

Ràng buộc

• \(1\le T\le100\).
• \(0<K_i<D\le10^9\) với mọi \(i\).
• \(K_i\ne K_j\) với mọi \(i\ne j\); không hai ngựa nào xuất phát cùng vị trí.
• \(1\le S_i\le10000\).

Phân nhóm

• Small Dataset (Test Set 1, hiển thị): \(1\le N\le2\).
• Large Dataset (Test Set 2, ẩn): \(1\le N\le1000\).

Đ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
2525 1
2400 5
300 2
120 60
60 90
100 2
80 100
70 10

Case #1: 101.000000
Case #2: 100.000000
Case #3: 33.333333

Nguồn

Google Code Jam 2018, Vòng luyện tập, bài Steed 2: Cruise Control.

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