Cubic UFO

Một tàu vũ trụ ngoài hành tinh hình lập phương bí ẩn xuất hiện trên bầu trời Toronto! Trong bài này, Toronto là mặt phẳng ba chiều song song với mặt phẳng \(xz\) tại \(y=-3\) km. Con tàu là khối lập phương đặc cạnh 1 km, tâm \((0,0,0)\), với tám đỉnh \((\pm0.5,\pm0.5,\pm0.5)\) km. Nó đổ một cái bóng đáng ngại xuống mặt phẳng; chính xác hơn, bóng là phép chiếu trực giao của khối lập phương lên mặt phẳng ấy, coi Mặt Trời là một điểm ở xa vô hạn phía trên theo trục \(y\).

Quân đội chấp nhận con tàu miễn là người ngoài hành tinh đáp ứng yêu cầu hành chính: bóng phải có diện tích đủ gần \(A\) km² theo định nghĩa chính xác ở phần output. Bạn, một chuyên gia ngôn ngữ học hình học, được thuê để truyền đạt yêu cầu. Con tàu không thể đổi kích thước hay dời tâm, nhưng có thể quay tùy ý tại chỗ.

Hãy tìm một phép quay để diện tích bóng gần \(A\). Biểu diễn tư thế bằng tâm của ba mặt bất kỳ sao cho không có cặp mặt nào đối nhau.

Dữ liệu vào

Dòng đầu chứa số test \(T\). Mỗi test là một dòng chứa số hữu tỉ \(A\), diện tích bóng mong muốn tính bằng km², với đúng sáu chữ số sau dấu thập phân. Đề bảo đảm mọi \(A\) hợp lệ đều có một tư thế thỏa mãn.

Dữ liệu ra

Với mỗi test, trước hết in Case #x:, rồi in ba dòng, mỗi dòng gồm ba số hữu tỉ là tọa độ \(x,y,z\) của một tâm mặt. Có thể dùng dạng thập phân hoặc khoa học.

Kết quả được chấp nhận khi và chỉ khi đồng thời thỏa mãn:

• Khoảng cách từ mỗi điểm tới gốc nằm trong \([0.5-10^{-6},0.5+10^{-6}]\) km.
• Góc giữa mọi cặp đoạn nối gốc với hai điểm nằm trong \([\pi/2-10^{-6},\pi/2+10^{-6}]\) radian.
• Bộ chấm dựng tám đỉnh dưới dạng \(\pm p_1\pm p_2\pm p_3\) (với mỗi \(p_i\) chọn cộng \(p_i\) hoặc \(-p_i\)), chiếu chúng lên mặt phẳng \(y=-3\), lấy bao lồi, rồi yêu cầu diện tích thuộc \([A-10^{-6},A+10^{-6}]\) km².

Có thể cần in hơn sáu chữ số sau dấu thập phân để an toàn. Nếu có nhiều đáp án, có thể in bất kỳ đáp án nào.

Ràng buộc

• \(1\le T\le100\).
• Mọi \(A\) đều được bảo đảm có nghiệm.

Phân nhóm

• Test Set 1 (hiển thị): \(1.000000\le A\le1.414213\).
• Test Set 2 (ẩn): \(1.000000\le A\le1.732050\).

Đ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
1.000000
1.414213

Case #1:
0.5 0 0
0 0.5 0
0 0 0.5
Case #2:
0.3535533905932738 0.3535533905932738 0
-0.3535533905932738 0.3535533905932738 0
0 0 0.5

Nguồn

Google Code Jam 2018, Vòng loại, bài Cubic UFO.

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

Đội ngũ Code Jam vừa mua một vườn cây là một ma trận đất chưa được chuẩn bị gồm 1000 hàng và 1000 cột. Chúng tôi định trồng đủ loại cây ở đây — AVL, nhị phân, đỏ-đen, splay, v.v. — nên cần chuẩn bị một số ô bằng cách đào hố:

• Để có đủ cây dùng cho các bài toán về cây hằng năm, phải có ít nhất \(A\) ô đã được chuẩn bị.

• Để chăm sóc cây đúng cách, tập hợp tất cả các ô đã được chuẩn bị phải tạo thành một hình chữ nhật duy nhất song song với lưới, và mọi ô bên trong hình chữ nhật đó đều phải được chuẩn bị.

Các điều kiện trên cũng có nghĩa là không ô nào bên ngoài hình chữ nhật được phép đã chuẩn bị. Chúng tôi muốn khu vườn trông thật gọn gàng!

Ví dụ, khi \(A=11\), mặc dù mười một ô đã chuẩn bị trong hình bên trái phía dưới tạo thành một hình chữ nhật \(3\times4\) (3 hàng và 4 cột), ô ở chính giữa hình chữ nhật vẫn chưa được chuẩn bị. Vì không phải mọi ô trong hình chữ nhật \(3\times4\) đều đã chuẩn bị, công việc trong vườn vẫn chưa hoàn tất. Tuy nhiên, chỉ cần chuẩn bị thêm ô chính giữa thì hình chữ nhật có diện tích ít nhất 11 sẽ được lấp đầy và khu vườn sẵn sàng.

Xét một ví dụ khác ở phía dưới, lần này \(A=6\). Hình ở giữa có một ô được chuẩn bị nằm ngoài hình chữ nhật \(3\times2\). Vì thế, dù hình ngoài cùng bên phải đã chuẩn bị một hình chữ nhật diện tích 6, toàn bộ tập ô đã chuẩn bị vẫn không tạo thành một hình chữ nhật do có ô thừa bên trái. Khu vườn do đó chưa sẵn sàng.

Đào đất là việc nặng nhọc đối với con người, nên chúng tôi đã mượn chú chuột Go từ đội ngũ Google Go và huấn luyện nó giúp chuẩn bị các ô. Ta có thể triển khai chuột bằng cách đưa cho nó tọa độ một ô mục tiêu trong ma trận, miễn là ô đó không nằm trên bất kỳ biên nào của ma trận. Tuy nhiên, quá trình huấn luyện chưa hoàn hảo: chuột sẽ chọn đều giả ngẫu nhiên một trong chín ô thuộc khối \(3\times3\) có tâm là ô mục tiêu, rồi chuẩn bị ô được chọn. Nếu chọn trúng một ô đã chuẩn bị, nó sẽ vô ích chuẩn bị lại ô đó.

Ta chỉ có thể triển khai chuột tối đa 1000 lần trước khi nó quá mệt để đào tiếp, nên cần tìm một chiến lược triển khai phù hợp. Sau mỗi lần triển khai, bạn sẽ được cho biết ô mà chuột thực sự chuẩn bị và có thể dùng thông tin đó trước lần triển khai tiếp theo nếu cần. Bạn không phải khai báo trước kích thước hay vị trí của hình chữ nhật.

Dữ liệu vào

Đây là một bài tương tác, nên khái niệm dữ liệu vào và dữ liệu ra khác với các bài Code Jam thông thường. Chương trình của bạn tương tác với một tiến trình riêng vừa cung cấp thông tin vừa đánh giá phản hồi. Mọi thông tin đi vào chương trình qua đầu vào chuẩn; mọi nội dung cần giao tiếp phải được gửi qua đầu ra chuẩn. Nhiều ngôn ngữ lập trình mặc định lưu đệm đầu ra, vì vậy phải bảo đảm dữ liệu thực sự được gửi đi — chẳng hạn bằng cách flush bộ đệm — trước khi dừng lại chờ phản hồi. Xem FAQ để biết ý nghĩa của việc flush bộ đệm. Mọi thứ chương trình ghi ra đầu lỗi chuẩn đều bị bỏ qua, nhưng vẫn có thể tốn bộ nhớ, nên đừng ghi tràn. Một công cụ kiểm thử cục bộ bằng Python được cung cấp ở cuối đề để hỗ trợ gỡ lỗi. Ngoài ra, phần phân tích bài Number Guessing, một bài tương tác Code Jam trước đây, có lời giải mẫu bằng mọi ngôn ngữ được hỗ trợ.

Ban đầu, chương trình đọc một dòng chứa số nguyên \(T\), là số lượng test. Sau đó chương trình xử lý lần lượt \(T\) test.

Với mỗi test, chương trình đọc một dòng chứa số nguyên \(A\), là diện tích hình chữ nhật đã chuẩn bị tối thiểu cần đạt. Sau đó chương trình thực hiện tối đa 1000 lượt trao đổi với bộ chấm.

Dữ liệu ra

Chương trình gửi các tọa độ triển khai qua đầu ra chuẩn và đọc phản hồi của bộ chấm qua đầu vào chuẩn theo giao thức dưới đây.

Giao thức tương tác

Trong mỗi lượt trao đổi, chương trình ghi ra đầu ra chuẩn một dòng gồm hai số nguyên I J: chỉ số hàng và cột của ô mà bạn muốn triển khai chuột tới. Cả hai số phải nằm trong đoạn từ 2 đến 999 và được viết ở hệ thập phân, không có số 0 ở đầu. Nếu định dạng đầu ra sai, chẳng hạn giá trị vượt phạm vi, chương trình sẽ thất bại; bộ chấm gửi một dòng -1 -1 để báo test đã thất bại rồi không gửi thêm gì vào luồng đầu vào. Nếu định dạng hợp lệ, để phản hồi lần triển khai, bộ chấm ghi một dòng gồm hai số nguyên I' J' vào luồng đầu vào và chương trình phải đọc chúng từ đầu vào chuẩn.

Nếu lần triển khai vừa rồi khiến tập ô đã chuẩn bị trở thành một hình chữ nhật có diện tích ít nhất \(A\), bạn nhận được I' = J' = 0, báo hiệu test kết thúc. Nếu chưa, I' và J' là hàng và cột của ô mà chuột thực sự chuẩn bị, thỏa mãn \(|I'-I|\le1\) và \(|J'-J|\le1\). Khi đó bạn có thể bắt đầu lượt trao đổi tiếp theo.

Nếu chương trình làm sai, chẳng hạn xuất sai định dạng hoặc giá trị vượt phạm vi, bộ chấm gửi I' = J' = -1 như đã nói ở trên rồi ngừng gửi dữ liệu. Nếu vẫn tiếp tục chờ bộ chấm sau khi đọc -1 -1, chương trình sẽ hết thời gian. Bạn có trách nhiệm kết thúc chương trình kịp lúc để nhận phán quyết thích hợp như Wrong Answer hay Runtime Error thay vì Time Limit Exceeded. Như thường lệ, nếu chương trình vượt tổng thời gian, vượt bộ nhớ hoặc gặp lỗi thực thi, bạn sẽ nhận phán quyết tương ứng.

Nếu giải xong test trong không quá 1000 lần triển khai, bạn nhận thông báo I' = J' = 0 rồi tiếp tục giải test kế tiếp. Nếu sau 1000 lượt trao đổi test vẫn chưa được giải, bộ chấm gửi I' = J' = -1 rồi ngừng gửi dữ liệu.

Không được gửi thêm thông tin cho bộ chấm sau khi đã giải xong tất cả các test. Nói cách khác, nếu chương trình tiếp tục ghi ra đầu ra chuẩn sau khi nhận I' = J' = 0 ở test cuối cùng, bạn sẽ nhận phán quyết Wrong Answer.

Trong một test cố định, các ô mà chuột chọn từ mỗi khối \(3\times3\) là giả ngẫu nhiên và độc lập với nhau, nhưng chúng được xác định bằng cùng một seed trong mọi lần chạy lại test đó. Vì vậy, một lời giải cho kết quả sai ở một test sẽ luôn sai ở test ấy trong mọi lần thử. Các test khác nhau sử dụng các seed khác nhau.

Ràng buộc

• \(1\le T\le20\).
• Mỗi test có tối đa 1000 lần triển khai.

Phân nhóm

Test Set 1 (công khai): \(A=20\).

Test Set 2 (ẩn): \(A=200\).

Ví dụ

  t = readline_int()         // reads 2 into t
  a = readline_int()         // reads 3 into a
  printline 10 10 to stdout  // sends out cell 10 10 to prepare
  flush stdout
  x, y = readline_two_int()  // reads 10 11, since cell 10 11 is prepared
  printline 10 10 to stdout  // sends out cell 10 10 again to prepare
  flush stdout
  x, y = readline_two_int()  // reads 10 10, since cell 10 10 is prepared
  printline 10 12 to stdout  // sends out cell 10 12 to prepare
  flush stdout
  x, y = readline_two_int()  // reads 10 11, since cell 10 11 is prepared again
  printline 10 10 to stdout  // sends out cell 10 10 to prepare
  flush stdout
  x, y = readline_two_int()  // reads 11 10, since cell 11 10 is prepared
  printline 11 10 to stdout  // sends out cell 11 10 to prepare
  flush stdout
  x, y = readline_two_int()  // reads 0 0; since cell 11 11 is prepared, a rectangle of size 4

  a = readline_int()         // reads 3 into a
  printline 10 10 to stdout  // sends out cell 10 10 to prepare
  x, y = readline_two_int()  // does not flush stdout; hangs on the judge

  a = readline_int()         // reads 3 into a
  printline 1 1 to stdout    // sends out cell 1 1 to prepare
  x, y = readline_two_int()  // reads -1 -1, since 1 is outside the range [2, 999]
  printline 10 10 to stdout  // sends a cell location anyway
  x, y = readline_two_int()  // hangs since the judge stops sending info to stdin

  a = readline_int()         // reads 3 into a
  printline 1 1 to stdout    // sends out cell 1 1 to prepare
  x, y = readline_two_int()  // reads -1 -1, since 1 is outside the range [2, 999]
  exit                       // receives a Wrong Answer judgment

Công cụ kiểm thử

Bạn có thể dùng công cụ kiểm thử này để chạy cục bộ hoặc trên nền tảng của Google. Khi kiểm thử cục bộ, cần chạy công cụ song song với chương trình; có thể dùng interactive runner của Google cho việc đó. Hãy đọc hướng dẫn trong phần chú thích của tệp ấy và phần Interactive Problems trong FAQ để biết thêm thông tin.

Hướng dẫn sử dụng nằm trong các chú thích bên trong công cụ và bạn được khuyến khích tự bổ sung test. Lưu ý rằng công cụ chỉ nhằm mô phỏng hệ thống chấm, không phải hệ thống chấm thật và có thể hành xử khác. Nếu chương trình vượt qua công cụ nhưng thất bại trên bộ chấm thật, hãy kiểm tra phần Coding trong FAQ để bảo đảm bạn dùng cùng trình biên dịch với hệ thống.

Tải công cụ kiểm thử từ kho lưu trữ chính thức.

Nguồn

Google Code Jam 2018, Vòng loại, bài Go, Gopher!.

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

Một robot ngoài hành tinh đang đe dọa vũ trụ bằng một tia năng lượng có thể phá hủy toàn bộ tri thức về thuật toán. Chúng ta phải ngăn nó lại!

May thay, chúng ta hiểu cách robot hoạt động. Ban đầu tia có sức mạnh 1. Robot chạy một chương trình gồm một chuỗi lệnh, được thực thi lần lượt từ trái sang phải. Mỗi lệnh thuộc một trong hai loại:

• C (viết tắt của “charge”, nạp năng lượng): nhân đôi sức mạnh của tia.

• S (viết tắt của “shoot”, bắn): bắn tia và gây lượng sát thương bằng sức mạnh hiện tại của tia.

Ví dụ, nếu chương trình của robot là SCCSSC, khi chạy chương trình robot sẽ thực hiện như sau:

• Bắn tia, gây 1 sát thương.
• Nạp năng lượng, nhân đôi sức mạnh của tia thành 2.
• Nạp năng lượng, nhân đôi sức mạnh của tia thành 4.
• Bắn tia, gây 4 sát thương.
• Bắn tia, gây 4 sát thương.
• Nạp năng lượng, tăng sức mạnh của tia thành 8.

Trong trường hợp đó, chương trình gây tổng cộng 9 sát thương.

Các nhà thuật toán hàng đầu của vũ trụ đã phát triển một tấm khiên chịu được tổng sát thương tối đa là \(D\). Tuy nhiên, chương trình hiện tại của robot có thể gây nhiều sát thương hơn mức đó khi được chạy.

Tổng thống Vũ trụ tình nguyện bay vào không gian để hack chương trình trước khi robot chạy nó. Cách duy nhất Tổng thống có thể hack mà không bị robot phát hiện là đổi chỗ hai lệnh kề nhau. Chẳng hạn, Tổng thống có thể hack chương trình trên một lần bằng cách đổi lệnh thứ ba và thứ tư, tạo thành SCSCSC và giảm tổng sát thương xuống 7. Sau đó, ví dụ, Tổng thống có thể hack thêm lần nữa để được SCSSCC, giảm sát thương xuống 5, và cứ thế tiếp tục.

Để robot không nghi ngờ quá mức, Tổng thống không muốn hack quá nhiều lần. Nếu có thể làm cho chương trình gây tổng sát thương không quá \(D\), số lần hack nhỏ nhất cần dùng là bao nhiêu?

Dữ liệu vào

Dòng đầu tiên chứa số lượng test \(T\). Mỗi test tiếp theo gồm một dòng chứa số nguyên \(D\) và chuỗi \(P\): tổng sát thương tối đa tấm khiên chịu được và chương trình của robot.

Dữ liệu ra

Với mỗi test, in một dòng Case #x: y, trong đó x là số thứ tự test bắt đầu từ 1; y là số lần hack nhỏ nhất để đạt mục tiêu, hoặc IMPOSSIBLE nếu không thể.

Ràng buộc

• \(1\le T\le100\).
• \(1\le D\le10^9\).
• \(2\le |P|\le30\).
• Mỗi ký tự của \(P\) là C hoặc S.

Phân nhóm

Test Set 1 (công khai): chương trình của robot chứa không quá một ký tự C.

Test Set 2 (ẩn): không có ràng buộc bổ sung ngoài các ràng buộc chung.

Đ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
1 CS
2 CS
1 SS
6 SCCSSC
2 CC
3 CSCSS

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

Nguồn

Google Code Jam 2018, Vòng loại, bài Saving The Universe Again.

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

Trong phòng thí nghiệm thuật toán bí mật của Code Jam, chúng tôi dành vô số giờ vật lộn với một trong những bài toán phức tạp nhất thời đại: sắp xếp hiệu quả một danh sách số nguyên theo thứ tự không giảm. Sau khi nghiên cứu cẩn thận thuật toán bubble sort kinh điển, chúng tôi vui mừng công bố một biến thể mới.

Phép toán cơ bản của bubble sort chuẩn là xét một cặp số kề nhau và đảo cặp đó nếu số bên trái lớn hơn số bên phải. Thuật toán của chúng tôi lại xét một nhóm ba số kề nhau; nếu số ngoài cùng bên trái lớn hơn số ngoài cùng bên phải, nó đảo ngược cả nhóm. Vì đây là một kiểu “bubble sort theo bộ ba”, chúng tôi gọi tắt nó là Trouble Sort.

  TroubleSort(L): // L is a 0-indexed list of integers
    let done := false
    while not done:
      done = true
      for i := 0; i < len(L)-2; i++:
        if L[i] > L[i+2]:
          done = false
          reverse the sublist from L[i] to L[i+2], inclusive

Ví dụ, với \(L=\) 5 6 6 4 3, Trouble Sort diễn tiến như sau:

• Lượt thứ nhất:

  • Xét 5 6 6, không làm gì: 5 6 6 4 3.
  • Xét 6 6 4, nhận thấy \(6>4\), đảo bộ ba: 5 4 6 6 3.
  • Xét 6 6 3, nhận thấy \(6>3\), đảo bộ ba: 5 4 3 6 6.

• Lượt thứ hai:

  • Xét 5 4 3, nhận thấy \(5>3\), đảo bộ ba: 3 4 5 6 6.
  • Xét 4 5 6, không làm gì: 3 4 5 6 6.
  • Xét 5 6 6, không làm gì: 3 4 5 6 6.

• Sau đó, lượt thứ ba xét cả ba bộ ba mà không làm gì, nên thuật toán kết thúc.

Chúng tôi đang háo hức chuẩn bị giới thiệu Trouble Sort tại hội nghị Special Interest Group in Sorting ở Hawaii thì một thực tập sinh vừa chỉ ra vấn đề: Trouble Sort có thể không sắp xếp danh sách đúng! Chẳng hạn, hãy xét danh sách 8 9 7.

Chúng tôi cần bạn giúp nghiên cứu thêm. Cho một danh sách gồm \(N\) số nguyên, hãy xác định Trouble Sort có sắp xếp thành công danh sách theo thứ tự không giảm hay không. Nếu không, hãy tìm chỉ số — đánh số từ 0 — của lỗi sắp xếp đầu tiên sau khi thuật toán kết thúc, tức vị trí đầu tiên có giá trị lớn hơn giá trị đứng ngay sau nó trong danh sách cuối cùng.

Dữ liệu vào

Dòng đầu tiên chứa số lượng test \(T\). Mỗi test gồm hai dòng: dòng thứ nhất chứa số nguyên \(N\), là số phần tử của danh sách; dòng thứ hai chứa \(N\) số nguyên \(V_i\), là các giá trị trong danh sách.

Dữ liệu ra

Với mỗi test, in một dòng Case #x: y, trong đó x là số thứ tự test bắt đầu từ 1; y là OK nếu Trouble Sort sắp xếp danh sách đúng, hoặc là chỉ số đánh từ 0 của lỗi sắp xếp đầu tiên như mô tả ở trên.

Ràng buộc

• \(1\le T\le100\).
• \(0\le V_i\le10^9\) với mọi \(i\).

Phân nhóm

Test Set 1 (công khai): \(3\le N\le100\).

Test Set 2 (ẩn): \(3\le N\le10^5\).

Lưu ý đặc biệt

Test Set 2 có lượng dữ liệu vào lớn, nên bộ đọc không có đệm có thể khiến việc đọc chậm hơn. Ngoài ra, hãy nhớ rằng một số ngôn ngữ mặc định có bộ đệm đầu vào nhỏ.

Đ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
5
5 6 8 4 3
3
8 9 7

Case #1: OK
Case #2: 1

Nguồn

Google Code Jam 2018, Vòng loại, bài Trouble Sort.

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