trang chủ / đề bài / icpc23_reg_j

Jom và Terry

Đề bài

Mô tả

Gần đây, chú chuột Terry đến sống trong một nhà máy pho mát. Ngày qua ngày, Terry đã ăn một lượng lớn pho mát mà nhà máy sản xuất. Vì sự có mặt của Terry, lượng pho mát dự trữ giảm đi đáng kể. Chú mèo Jom được giao nhiệm vụ canh giữ kho pho mát, ngăn không cho Terry lấy trộm miếng nào. Việc đầu tiên Jom làm là đặt bẫy ở tất cả những chỗ có pho mát. Điều này gây trở ngại lớn cho việc kiếm ăn của Terry.

Không bỏ cuộc, Terry nghĩ ra một kế hoạch để ăn pho mát trong kho một cách an toàn. Sau khi điều tra, Terry phát hiện trong kho có n cái bẫy. Mỗi cái bẫy có cấu trúc đặc biệt dạng một ống. Ở mỗi đầu của bẫy, Jom đặt một trong hai thứ:

  • Một miếng pho mát có khối lượng dương.
  • Một lọ keo thực phẩm đặc biệt, cho phép dính hai miếng pho mát có khối lượng x và y thành một miếng pho mát mới có khối lượng x+y. Mỗi lọ keo chỉ dùng được một lần.

Với mỗi ống, Terry gọi một đầu là "đầu vào" và đầu kia là "đầu ra". Terry có thể khéo léo di chuyển từ đầu vào tới đầu ra một cách an toàn, nhưng đi theo chiều ngược lại sẽ sập bẫy của Jom.

Ví dụ, Jom đặt n=3 bẫy như sau:

  • Bẫy 1: đầu vào có miếng pho mát khối lượng 1, đầu ra có một lọ keo.
  • Bẫy 2: đầu vào có một lọ keo, đầu ra có miếng pho mát khối lượng 2.
  • Bẫy 3: đầu vào có miếng pho mát khối lượng 4, đầu ra có miếng pho mát khối lượng 3.

Terry đã chuẩn bị một cái túi đủ lớn để đựng toàn bộ pho mát trong kho. Đầu tiên Terry đi tới bẫy p1, rồi tới bẫy p2, cứ thế cho tới bẫy pn, trong đó p1,p2,…,pn là một hoán vị của các số nguyên từ 1 đến n do Terry chọn. Khi tới bẫy i, Terry chui vào bẫy, nhặt món đồ ở đầu vào, đi qua bẫy, rồi nhặt món đồ ở đầu ra.

  • Khi nhặt được một miếng pho mát, Terry bỏ nó vào túi.
  • Khi nhặt được một lọ keo, Terry lấy 2 miếng pho mát được bỏ vào túi gần đây nhất (theo thứ tự bỏ vào), dính chúng lại bằng keo, rồi bỏ miếng pho mát mới vào lại túi. Nếu trong túi còn ít hơn hai miếng pho mát, Terry vứt lọ keo đi.

Kế hoạch gần như hoàn hảo, nhưng Terry cũng cần một phương án thoát thân nếu Jom xuất hiện. Terry tính rằng thời gian đi qua cả n bẫy rất nhanh. Tuy nhiên, khi trở về hang, vì mang túi rất nặng nên thời gian di chuyển sẽ lâu hơn nhiều. Nếu lúc đó Jom xuất hiện, theo bản năng, Terry sẽ lấy miếng pho mát được bỏ vào túi sau cùng, bỏ lại túi cùng số pho mát còn lại, và chạy thật nhanh về hang. Tất nhiên, nếu trong túi không có pho mát thì Terry không mang được gì về.

Cho mô tả các món đồ trong n bẫy, hãy giúp Terry tìm thứ tự di chuyển p1,p2,…,pn sao cho nếu phải chạy trốn Jom, khối lượng pho mát Terry mang về hang là lớn nhất có thể.

Trong ví dụ trên, một kế hoạch có thể là p=[3,1,2]: túi lần lượt là [4], [4,3], [4,3,1], [4,4] (keo dính 3 và 1), [8] (keo dính 4 và 4), [8,2]. Nếu Jom xuất hiện, Terry chỉ mang về miếng pho mát khối lượng 2. Một kế hoạch tốt hơn là p=[2,3,1]: keo của bẫy 2 bị vứt đi vì túi rỗng, sau đó túi lần lượt là [2], [2,4], [2,4,3], [2,4,3,1], [2,4,4]. Khi đó Terry mang về được miếng pho mát khối lượng 4. Có thể chứng minh đây là kế hoạch tối ưu cho ví dụ này.

Dữ liệu vào

Dữ liệu vào gồm nhiều bộ dữ liệu. Mỗi bộ dữ liệu có dạng:

  • Dòng đầu tiên chứa số nguyên dương n (1≤n≤2·105): số bẫy Jom đã đặt trong kho.
  • n dòng tiếp theo, dòng thứ i chứa hai số nguyên ai và bi (0≤ai,bi≤109) mô tả hai đầu của bẫy thứ i:
    • Nếu ai>0, đầu vào của bẫy có miếng pho mát khối lượng ai.
    • Nếu ai=0, đầu vào của bẫy có một lọ keo.
    • Số bi mô tả đầu ra của bẫy theo cách tương tự.

Dữ liệu vào kết thúc bởi một dòng chứa duy nhất số 0, dòng này không phải là một bộ dữ liệu.

Dữ liệu bảo đảm tổng n của tất cả các bộ dữ liệu không vượt quá 2·105.

Dữ liệu ra

Với mỗi bộ dữ liệu, in ra n số nguyên p1,p2,…,pn là thứ tự đi qua các bẫy trong kế hoạch của Terry, sao cho nếu phải chạy trốn sau khi đi qua cả n bẫy, khối lượng pho mát Terry mang về hang là lớn nhất có thể.

Nếu có nhiều đáp án tối ưu, in ra đáp án bất kỳ.

Ràng buộc

  • 1≤n≤2·105, tổng n không vượt quá 2·105
  • 0≤ai,bi≤109

Ví dụ

Input Output Giải thích
2
2 3
1 2
2
1 1
1 0
2
2 2
0 1
3
4 4
0 0
4 4
0
2 1
1 2
2 1
1 3 2
Bộ thứ nhất: không có keo, miếng cuối cùng là đầu ra của bẫy cuối, đi theo thứ tự [2,1] được 3. Bộ thứ hai: thứ tự [1,2] dùng keo ở đầu ra bẫy 2 dính hai miếng khối lượng 1 thành miếng 2. Bộ thứ ba: thứ tự [1,2] dính hai miếng ở bẫy 1 nhưng miếng cuối chỉ nặng 1, nên thứ tự [2,1] (miếng cuối nặng 2) tốt hơn. Bộ thứ tư: đi theo thứ tự [1,3,2] (hoặc [3,1,2]), miếng cuối nặng 4+4+4=12.
3
1 0
0 0
0 0
7
0 77
5 95
27 26
97 0
0 53
0 0
0 90
0
1 3 2
2 3 7 5 1 4 6
Ví dụ bổ sung. Bộ thứ hai: chỉ miếng pho mát khối lượng 5 bị bỏ lại ở đáy túi, Terry mang về 470−5=465.

Bình luận

Không có bình luận tại thời điểm này.

gnatmake 12.2.0 a68g 3.1.2 nasm 2.16.1 as_x64 2.47 awk 1.3.4 gcc 16.2.0 dotnet 10.0.402 g++ 16.2.0 g++-themis 16.2.0 g++17 16.2.0 g++20 16.2.0 g++23 16.2.0 clang++ 22.1.8 dmd 2.113.0 dart 3.13.6 gforth 0.7.3 gfortran 15.3.0 go 1.27.3 groovyc 5.1.3 javac 26.0.2.1 node 26.12.1 julia 1.13.2 kotlinc 2.4.21 lean 4.35.0 sbcl 2.2.9 lua 5.5.1 nim 2.2.12 fpc 3.2.2 fpc-themis 3.2.2 perl 5.42.3 php 8.5.12 pike 8.0 swipl 9.0.4 pypy3 7.3.23 python3 3.15.1 racket 8.7 ruby 4.0.8 rustc 1.99.1 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 swiftc 6.4.1 tclsh 8.6 bun 1.4.4 deno 2.9.8 v 0.5.2 zig 0.17.0