Google Code Jam 2019 - World Finals

Bạn không cần biết bất kỳ điều gì về luật cờ vua để giải bài này.

Có \(N\) quân vua trên một bàn cờ vô hạn, tức một lưới hai chiều, nằm tại các ô có tọa độ \((X_1,Y_1),(X_2,Y_2),\ldots,(X_N,Y_N)\). Bạn không biết \(N\) cũng như tọa độ của các quân vua, nhưng biết các điều sau:

• \(N\) ít nhất là 1 và nhiều nhất là \(N_{\max}\).
• Không tọa độ \(X\) hoặc \(Y\) nào của một quân vua có trị tuyệt đối vượt quá \(M\).
• \(N\) quân vua nằm ở \(N\) ô khác nhau.

Các quân vua muốn gặp nhau tại một ô duy nhất. Nếu chọn ô \((X,Y)\) làm nơi họp, quân vua thứ \(i\) cần số nước đi bằng giá trị lớn nhất trong hai độ chênh tuyệt đối giữa tọa độ của nó và tọa độ nơi họp:

Vì vậy, tổng số nước đi của mọi quân vua là tổng các giá trị trên với mọi \(i\). Cách cụ thể các quân vua di chuyển trên bàn cờ không liên quan tới bài toán; chỉ ô xuất phát, ô đích và số nước đi luôn tính được bằng công thức trên mới quan trọng.

Bài toán có hai giai đoạn. Trong giai đoạn đầu, bạn có thể lặp lại thao tác sau: đề xuất một nơi họp \((A,B)\), trong đó cả \(A\) và \(B\) đều thuộc đoạn \([-10M,10M]\), rồi để bộ chấm cho biết tổng số nước các quân vua cần đi tới đó:

Bạn được trao đổi với bộ chấm theo cách này nhiều nhất \(R\) lần, và được tự chọn \(A,B\) trong mỗi lần. Các quân vua không thực sự di chuyển, nên các vị trí \((X_i,Y_i)\) giữ nguyên trong mọi yêu cầu của cùng một bộ test.

Trong giai đoạn thứ hai, vai trò đảo lại: bộ chấm đưa cho bạn tọa độ một ô họp \((C,D)\), với cả \(C\) và \(D\) thuộc đoạn \([-10M,10M]\), và bạn phải trả lời tổng số nước các quân vua cần đi tới đó, giả sử chúng vẫn ở đúng các vị trí của giai đoạn đầu. Có nhiều nhất \(R\) lần trao đổi như vậy và bạn phải trả lời đúng mọi yêu cầu của bộ chấm.

Dữ liệu vào

Chương trình nhận dữ liệu từ bộ chấm theo giao thức tương tác bên dưới.

Dữ liệu ra

Chương trình gửi truy vấn và câu trả lời tới bộ chấm theo giao thức tương tác bên dưới.

Giao thức tương tác

Ban đầu, đọc một dòng chứa bốn số nguyên \(T,N_{\max},M,R\), lần lượt là số bộ test, số quân vua tối đa, trị tuyệt đối tối đa của bất kỳ tọa độ nào của một quân vua, và số yêu cầu tối đa trong mỗi giai đoạn. Các giá trị \(M\) và \(R\) là cố định và chỉ được đưa vào dữ liệu đầu vào để tiện sử dụng; xem phần Ràng buộc. Sau đó xử lý lần lượt \(T\) bộ test.

Mỗi bộ test gồm hai giai đoạn. Trong lần trao đổi thứ \(i\) của giai đoạn đầu:

• Chương trình gửi một dòng chứa hai số nguyên \(A_i\) và \(B_i\), là tọa độ \(x\) và \(y\) của một ô. Cả \(A_i\) và \(B_i\) phải thuộc đoạn \([-10M,10M]\).
• Bộ chấm trả lời một dòng chứa một số nguyên: tổng số nước các quân vua cần đi từ các vị trí chưa biết của chúng tới ô bạn vừa gửi.

Bạn được khởi tạo nhiều nhất \(R\) lần trao đổi trong giai đoạn này. Nếu thực hiện quá \(R\) lần, hoặc gửi một yêu cầu mà bộ chấm không phân tích được hay có tọa độ ngoài giới hạn, bộ chấm trả lời một dòng chỉ chứa chuỗi ERROR.

Để kết thúc giai đoạn đầu và chuyển sang giai đoạn thứ hai, gửi một dòng chứa chuỗi READY, không phân biệt chữ hoa chữ thường. Bộ chấm sẽ đáp lại bằng yêu cầu đầu tiên của giai đoạn thứ hai.

Trong lần trao đổi thứ \(i\) của giai đoạn thứ hai:

• Bộ chấm gửi một dòng chứa hai số nguyên \(C_i\) và \(D_i\), là tọa độ \(x\) và \(y\) của một ô. Mỗi giá trị đều thuộc đoạn \([-10M,10M]\).
• Chương trình phải trả lời một dòng chứa một số nguyên: tổng số nước các quân vua cần đi tới ô đã cho.

Bộ chấm bảo đảm gửi ít nhất 1 và nhiều nhất \(R\) yêu cầu như vậy. Nếu câu trả lời sai hoặc không thể phân tích, bộ chấm trả về ERROR như trên. Nếu bạn trả lời đúng tất cả các yêu cầu, bộ chấm gửi một dòng chỉ chứa DONE; lúc đó chương trình phải bắt đầu bộ test tiếp theo, hoặc kết thúc không lỗi nếu đã xử lý đủ \(T\) bộ test.

Sau khi gửi một dòng ERROR, bộ chấm không gửi thêm bất kỳ đầu ra nào. Nếu chương trình tiếp tục chờ bộ chấm sau khi nhận ERROR, chương trình sẽ hết thời gian và nhận Time Limit Exceeded. Bạn có trách nhiệm cho chương trình thoát kịp thời để nhận Wrong Answer thay vì Time Limit Exceeded. Nếu chương trình gặp lỗi chạy, nó sẽ nhận phán quyết tương ứng.

Số lượng và vị trí các quân vua, cũng như số lượng và vị trí các yêu cầu mà bộ chấm sẽ gửi trong các giai đoạn thứ hai, đều được chọn trước khi bất kỳ lần trao đổi nào diễn ra.

Ràng buộc

• \(1\le T\le 15\).
• \(M=10^6\).
• \(-M\le X_i\le M\) với mọi \(i\).
• \(-M\le Y_i\le M\) với mọi \(i\).
• Các cặp \((X_i,Y_i)\) đôi một khác nhau.
• \(-10M\le C_i\le 10M\) với mọi \(i\).
• \(-10M\le D_i\le 10M\) với mọi \(i\).
• \(R=1000\).

Phân nhóm

• Test Set 1 (hiển thị): \(N_{\max}=1\).
• Test Set 2 (ẩn): \(N_{\max}=10\).

Công cụ kiểm thử

Bạn có thể dùng công cụ kiểm thử đi kèm để chạy cục bộ hoặc trên nền tảng chính thức. Khi chạy cục bộ, cần chạy công cụ song song với chương trình của bạn; có thể dùng interactive runner. Hãy đọc hướng dẫn trong phần bình luận của tệp đó và phần Bài tương tác trong FAQ.

Hướng dẫn riêng của công cụ cũng nằm trong các bình luận bên trong công cụ. Bạn nên bổ sung các bộ test của mình. Dù công cụ đượ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ụ nhưng không vượt qua 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 chính thức.

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

Ví dụ

  // Suppose that the judge has decided that in the first test case, the king
  // is at the coordinates (1, -2), and the requests will be (5, -1) and
  // (7, 7).
  t, nmax, m, r = readline_int_list()   // Reads 10 1 1000000 1000
  // Our solution decides (for whatever reason) to check (3, 3) first.
  printline 3 3 to stdout
  flush stdout
  result = readline_int()               // Reads 5
  // Our solution now decides (for whatever reason) to check (2, 0).
  printline 2 0 to stdout
  flush stdout
  result = readline_int()               // Reads 2
  // Our solution concludes that the king is at (3, -2), which is consistent
  // with the observed information so far, but unfortunately not correct.
  // Our solution moves on to the request phase.
  printline READY to stdout
  request_line = readline()             // Reads 5 -1
  printline 2 to stdout                 // Wrong answer!
  request_line = readline()             // Reads ERROR
  exit                                  // exits to avoid an ambiguous TLE error

Nguồn

Google Code Jam 2019, Chung kết thế giới, bài Board Meeting.

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

Marlin là một chú cá bị lạc mất con trai và đang cố tìm con. May mắn thay, khi đang bơi cùng hai anh em Wally và Seymour, rùa Cynthia gặp Marlin. Cynthia biết chính xác Marlin cần đi đâu và có thể chỉ đường rất tỉ mỉ. Marlin thông minh, có thể làm theo hoàn hảo, nhưng ghi nhớ một danh sách chỉ dẫn dài lại khó. Cynthia cần làm danh sách đó thật ngắn.

Marlin sống trong một ma trận \(R\) hàng và \(C\) cột. Một số ô nguy hiểm, không thể đi vào. Marlin và con trai hiện ở hai ô an toàn khác nhau; con trai Marlin không bao giờ chuyển ô.

Cynthia đưa chỉ dẫn dưới dạng một chương trình gồm danh sách lệnh, mỗi dòng là một trong năm loại:

• N: đi một ô về bắc (lên);
• S: đi một ô về nam (xuống);
• W: đi một ô về tây (trái);
• E: đi một ô về đông (phải);
• G(i): nhảy tới dòng lệnh thứ \(i\) (đánh số từ 1).

Sau khi thực hiện một trong bốn lệnh di chuyển, Marlin chuyển sang dòng kế tiếp nếu có. Nếu không còn dòng kế tiếp, Marlin chỉ đứng yên mãi mãi.

Ví dụ, với chương trình

1: N
2: E
3: G(6)
4: S
5: G(1)
6: W
7: G(4)

Marlin đi bắc (dòng 1), rồi đông (2), nhảy tới dòng 6 mà không di chuyển (3), đi tây (6), nhảy tới dòng 4 (7), đi nam (4), nhảy tới dòng 1 (5), rồi đi bắc (1), v.v.

Nếu ở bất kỳ thời điểm nào Marlin và con trai cùng ở một ô, họ sẽ đoàn tụ và Marlin ngừng làm theo mọi lệnh. Hãy tìm số dòng nhỏ nhất trong một chương trình đưa Marlin tới cùng ô với con trai mà không bao giờ vào ô nguy hiểm hay đi ra ngoài biên ma trận. Mọi lệnh G phải nhảy tới một dòng tồn tại trong chương trình.

Dữ liệu vào

Dòng đầu chứa số bộ test \(T\). Mỗi bộ test bắt đầu bằng một dòng chứa \(R,C\), số hàng và cột. Tiếp theo là \(R\) dòng, mỗi dòng là một chuỗi \(C\) ký tự. Ký tự \(A_{ij}\) ở hàng \(i\), cột \(j\) là # nếu ô nguy hiểm, M nếu đó là vị trí hiện tại của Marlin, N nếu đó là vị trí hiện tại của con trai Marlin, và . nếu là ô an toàn đang trống.

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 có chương trình thỏa điều kiện, hoặc là số lệnh nhỏ nhất của một chương trình như vậy.

Ràng buộc

• \(1\le T\le100\).
• \(A_{ij}\) là một trong #, ., M, N.
• Có đúng một cặp \((i,j)\) sao cho \(A_{ij}={}\)M và đúng một cặp sao cho \(A_{ij}={}\)N.

Phân nhóm

Test Set 1 (Visible): \(1\le R\le10\), \(1\le C\le10\).

Test Set 2 (Hidden): Với nhiều nhất 10 bộ test, \(1\le R,C\le100\); với các bộ test còn lại, \(1\le R,C\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ụ

5
2 5
N...#
....M
2 5
N#...
...#M
5 5
N..##
#.###
#...#
##.##
##..M
5 5
..N##
#.###
#...#
##.##
##..M
3 3
#M#
###
#N#

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

1: W
2: N
3: S
4: G(1)

1: W
2: N
3: W
4: G(3)

1: N
2: W
3: W
4: S
5: W
6: W
7: N

1: W
2: W
3: N
4: N
5: G(2)

1: W
2: W
3: N
4: N
5: E
6: G(1)

Nguồn

Google Code Jam 2019, Chung kết thế giới, bài Go To Considered Helpful.

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

Hai đoạn tiếp theo của đề này và Juggle Struggle: Part 2 giống hệt nhau. Ngoài phần đó, hai bài có thể giải độc lập; bạn không cần đọc hay giải bài này để đọc hoặc giải bài kia.

Là quản lý nhóm Graceful Chainsaw Jugglers, bạn quyết định làm tiết mục hấp dẫn hơn. Thay vì mỗi nghệ sĩ tự tung hứng cưa máy của mình, bạn muốn họ ghép thành cặp, mỗi cặp ném cưa máy qua lại cho nhau.

Trong tiết mục mới, \(2N\) nghệ sĩ cùng đứng trên sân khấu, được chia thành \(N\) cặp, mỗi người thuộc đúng một cặp.

Bạn cho rằng tiết mục sẽ ấn tượng hơn nếu cưa máy của các cặp khác nhau có nguy cơ va chạm. Xem sân khấu là một mặt phẳng hai chiều; đoạn thẳng nối vị trí hai nghệ sĩ trong một cặp gọi là đường tung hứng của cặp. Khi hai đường tung hứng giao nhau, ta nói cưa máy của hai cặp có nguy cơ va chạm. Vị trí không gian và cách ghép cặp tạo thành một cách bố trí. Cách bố trí là tráng lệ nếu đường tung hứng của mọi hai cặp đều giao nhau.

Sau rất nhiều suy nghĩ và thiết kế, bạn đã tìm được một cách bố trí tráng lệ và ghi vị trí cùng cách ghép cặp lên giấy. Không may, một cú ném cưa tệ đã cắt đôi tờ giấy và bạn làm mất nửa ghi các cặp.

Đồ trang trí sân khấu đã được thiết kế theo vị trí các nghệ sĩ nên không thể thay đổi. Buổi ra mắt được mong đợi chỉ còn vài giờ nữa; hãy tìm một cách bố trí tráng lệ. Cho vị trí mọi nghệ sĩ trên sân khấu hai chiều, hãy ghép họ thành các cặp sao cho bố trí tráng lệ.

Dữ liệu vào

Dòng đầu chứa số bộ test \(T\). Mỗi bộ test bắt đầu bằng số nguyên \(N\), số cặp nghệ sĩ. Tiếp theo là \(2N\) dòng; dòng thứ \(i\) chứa hai số nguyên \(X_i,Y_i\), tọa độ vị trí nghệ sĩ thứ \(i\).

Dữ liệu ra

Với mỗi bộ test, in Case #x: j1 j2 ... j(2N), biểu thị nghệ sĩ \(i\) ghép với nghệ sĩ \(j_i\) với mọi \(i\). Phải có \(j_{j_i}=i\) với mọi \(i\).

Ràng buộc

• \(-10^9\le X_i,Y_i\le10^9\) với mọi \(i\).
• Không có ba vị trí nghệ sĩ thẳng hàng; điều này cũng kéo theo không có hai người cùng vị trí.
• Luôn tồn tại ít nhất một cách ghép tạo nên bố trí tráng lệ.

Phân nhóm

Test Set 1 (Visible): \(1\le T\le100\), \(2\le N\le100\).

Test Set 2 (Hidden): \(1\le T\le10\), \(2\le N\le10^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
2
-1 -1
-1 1
1 1
1 -1
3
1 2
2 1
2 3
3 1
3 3
4 2
3
7 1
1 1
7 2
5 5
3 5
1 2

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

Nguồn

Google Code Jam 2019, Chung kết thế giới, bài Juggle Struggle: Part 1.

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

Hai đoạn tiếp theo của đề này và Juggle Struggle: Part 1 giống hệt nhau. Ngoài phần đó, hai bài có thể giải độc lập; bạn không cần đọc hay giải bài này để đọc hoặc giải bài kia.

Là quản lý nhóm Graceful Chainsaw Jugglers, bạn quyết định làm tiết mục hấp dẫn hơn. Thay vì mỗi nghệ sĩ tự tung hứng cưa máy của mình, bạn muốn họ ghép thành cặp, mỗi cặp ném cưa máy qua lại cho nhau.

Trong tiết mục mới, \(2N\) nghệ sĩ cùng đứng trên sân khấu, được chia thành \(N\) cặp, mỗi người thuộc đúng một cặp.

Bạn cho rằng tiết mục sẽ ấn tượng hơn nếu cưa máy của các cặp khác nhau có nguy cơ va chạm. Xem sân khấu là một mặt phẳng hai chiều; đoạn thẳng nối vị trí hai nghệ sĩ trong một cặp gọi là đường tung hứng của cặp. Khi hai đường tung hứng giao nhau, ta nói cưa máy của hai cặp có nguy cơ va chạm. Vị trí không gian và cách ghép cặp tạo thành một cách bố trí. Cách bố trí là tráng lệ nếu đường tung hứng của mọi hai cặp đều giao nhau. Nói cách khác, mỗi đoạn trong \(N\) đường tung hứng phải giao với cả \(N-1\) đoạn còn lại; các giao điểm không nhất thiết trùng nhau.

Sau vài sửa chữa vào phút chót, bạn có một cách bố trí mà mình cho là tráng lệ. Vì phải hoàn thành gấp, bạn muốn viết một trình kiểm tra xác định nó có thực sự tráng lệ hay không. Nếu không, đề bảo đảm có nhiều nhất 25 cặp nghệ sĩ không giao với mọi cặp khác. Trình kiểm tra phải báo danh sách tất cả những cặp đó để xem xét.

Dữ liệu vào

Dòng đầu chứa số bộ test \(T\). Mỗi bộ test bắt đầu bằng số nguyên \(N\), số cặp nghệ sĩ. Tiếp theo là \(N\) dòng; dòng thứ \(i\) chứa bốn số nguyên \(X_i,Y_i,X'_i,Y'_i\). Hai điểm \((X_i,Y_i)\) và \((X'_i,Y'_i)\) là vị trí hai nghệ sĩ của cặp thứ \(i\).

Dữ liệu ra

Với mỗi bộ test, in Case #x: y. Nếu đầu vào là một cách bố trí tráng lệ, y là MAGNIFICENT. Nếu không, y là một danh sách số nguyên tăng nghiêm ngặt; chỉ số \(i\) xuất hiện trong danh sách khi và chỉ khi đường tung hứng của cặp thứ \(i\) không giao với ít nhất một đường tung hứng khác.

Ràng buộc

• \(-10^9\le X_i,Y_i,X'_i,Y'_i\le10^9\) với mọi \(i\).
• Không có ba vị trí nghệ sĩ thẳng hàng; điều này cũng kéo theo không có hai người cùng vị trí.
• Ngoại trừ nhiều nhất 25 cặp, đường tung hứng của mọi cặp giao với cả \(N-1\) đường còn lại.
• Có thể tồn tại hoặc không tồn tại một cách ghép lại các nghệ sĩ để tạo bố trí tráng lệ; đề không đưa ra bảo đảm về điều này.

Phân nhóm

Test Set 1 (Visible): \(1\le T\le100\), \(2\le N\le100\).

Test Set 2 (Hidden): \(1\le T\le13\), \(2\le N\le10^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ụ

4
2
-1 -1 -1 1
1 1 1 -1
2
-1 -1 1 1
-1 1 1 -1
4
1 2 4 2
2 1 3 1
2 4 3 0
3 3 2 3
3
1 1 2 2
3 7 4 8
8 3 9 3

Case #1: 1 2
Case #2: MAGNIFICENT
Case #3: 1 2 4
Case #4: 1 2 3

Nguồn

Google Code Jam 2019, Chung kết thế giới, bài Juggle Struggle: Part 2.

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ó thể bạn từng nghe về Tensor Processing Unit của Google, loại chip dùng để xây dựng mạng nơ-ron. Tuy nhiên, còn một lĩnh vực nghiên cứu sâu sắc và quan trọng hơn cả học máy: sắp xếp!

Chúng tôi đang phát triển một con chip đặc biệt tên Sorting Permutation Unit, có thể áp dụng hoán vị lên mảng số nguyên rất nhanh. Một hoán vị là một thứ tự của \(n\) số nguyên dương đầu tiên \(p_1,p_2,\ldots,p_n\); áp dụng nó lên mảng \(a_1,a_2,\ldots,a_n\) sẽ cho mảng mới \(a_{p_1},a_{p_2},\ldots,a_{p_n}\). Ví dụ, áp dụng hoán vị 3 1 2 4 lên mảng 99 234 45 800 cho 45 99 234 800.

Tuy nhiên, biểu diễn hoán vị trong phần cứng rất tốn kém, nên bộ xử lý chỉ được dùng nhiều nhất \(P\) hoán vị khác nhau. Bạn phải giúp chọn các hoán vị đó.

Cho \(K\) mảng, mỗi mảng gồm \(N\) số nguyên. Trước hết, bạn chỉ định không quá \(P\) hoán vị kích thước \(N\) tùy ý. Sau đó, với mỗi mảng đầu vào, cung cấp một dãy không quá \(S\) chỉ thị; mỗi chỉ thị là một hoán vị trong tập đã khai báo. Áp dụng các chỉ thị theo đúng thứ tự phải cho một mảng được sắp không giảm. Trong mỗi dãy chỉ thị, mỗi hoán vị có thể được dùng không lần, một lần hoặc nhiều lần, và các lần dùng không nhất thiết liên tiếp.

Dữ liệu vào

Dòng đầu chứa số bộ test \(T\). Mỗi bộ test bắt đầu bằng bốn số nguyên \(P,S,K,N\): số hoán vị tối đa được phép khai báo, số chỉ thị tối đa để sắp mỗi mảng, số mảng và số phần tử trong mỗi mảng. Tiếp theo là \(K\) dòng, mỗi dòng gồm \(N\) số nguyên \(A_{i1},A_{i2},\ldots,A_{iN}\); \(A_{ij}\) là giá trị thứ \(j\) của mảng thứ \(i\).

Dữ liệu ra

Với mỗi bộ test, trước tiên in theo thứ tự:

• Một dòng Case #x:, với x là số thứ tự bộ test (bắt đầu từ 1).
• Một dòng chứa số nguyên \(P'\), với \(1\le P'\le P\): số hoán vị bạn chọn.
• \(P'\) dòng, dòng thứ \(i\) chứa \(N\) số \(p_{i1},p_{i2},\ldots,p_{iN}\) của hoán vị thứ \(i\).

Sau đó in thêm \(K\) dòng chỉ thị. Dòng thứ \(i\) bắt đầu bằng \(S'\), với \(0\le S'\le S\), rồi là \(S'\) số \(X_1,X_2,\ldots,X_{S'}\), trong đó \(1\le X_k\le P'\). \(X_k\) cho biết chỉ thị thứ \(k\) áp dụng hoán vị thứ \(X_k\) trong danh sách đã khai báo (đánh số từ 1). Dãy chỉ thị phải biến mảng đầu vào thứ \(i\) thành chính các phần tử của nó theo thứ tự không giảm.

Ràng buộc

• \(1\le T\le10\).
• \(S=450\).
• \(1\le K\le30\).
• \(2\le N\le50\).
• \(1\le A_{ij}\le1000\) với mọi \(i,j\).

Phân nhóm

Test Set 1 (Visible): \(P=20\).

Test Set 2 (Hidden): \(P=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ụ

2
20 450 4 3
10 10 11
17 4 1000
999 998 997
10 10 11
20 450 5 5
1 2 3 4 5
2 3 4 5 1
3 4 5 1 2
4 5 1 2 3
5 1 2 3 4

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

Nguồn

Google Code Jam 2019, Chung kết thế giới, bài Sorting Permutation Unit.

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

Năm 2016, người ta đã chứng minh rằng mọi số nguyên dương đều có thể viết thành tổng của không quá ba số hạng palindrome. Trong bài này, một số hạng palindrome là chuỗi chữ số không có số 0 ở đầu, biểu diễn một số nguyên dương và đọc xuôi hay ngược đều giống nhau.

Cho số nguyên dương \(S\), hãy tìm \(K\) số hạng palindrome có tổng bằng \(S\), sao cho \(K\) nhỏ nhất.

Dữ liệu vào

Dòng đầu chứa số bộ test \(T\). Mỗi dòng trong \(T\) dòng tiếp theo chứa một số nguyên dương \(S\).

Dữ liệu ra

Với mỗi bộ test, in một dòng theo một trong các dạng Case #x: A1 nếu chỉ cần một số hạng, Case #x: A1 A2 nếu cần hai số hạng, hoặc Case #x: A1 A2 A3 nếu cần ba số hạng. x là số thứ tự bộ test (bắt đầu từ 1), mỗi \(A_i\) là một số hạng palindrome như định nghĩa trên, và tổng các \(A_i\) bằng \(S\).

Ràng buộc

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

Phân nhóm

Test Set 1 (Visible): \(1\le S\le10^{10}\).

Test Set 2 (Hidden): \(1\le S\le10^{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
1
198
1234567890

Case #1: 1
Case #2: 191 7
Case #3: 672787276 94449 561686165

Nguồn

Google Code Jam 2019, Chung kết thế giới, bài Won't sum? Must now.

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