trang chủ / đề bài / icpcwf22_y

Nén xâu

Đề bài

Mô tả

Hiệp hội Kế hoạch Nén Vô hạn (ICPC) vừa phát triển một chiến lược nén dữ liệu mới tuyệt vời, gọi là "Đừng lặp lại chính mình" (DRY). DRY làm việc trên một xâu ký tự: nếu xâu chứa hai lần xuất hiện liên tiếp của cùng một xâu con, nó chỉ đơn giản xoá đi một trong hai lần đó. Ví dụ, trong xâu "alfalfa seeds", nó có thể xoá một trong hai xâu con "e" trong "seeds" và một trong hai xâu con "lfa" trong "alfalfa", được kết quả "alfa seds". DRY cũng có thể tận dụng các lần xoá trước đó: chẳng hạn với xâu "seventeenth baggage", đầu tiên nó xoá chữ "e" lặp trong "seventeenth" và chữ "g" lặp trong "baggage", được "sevententh bagage", rồi xoá "ent" lặp trong "sevententh" và "ag" lặp trong "bagage", được "seventh bage".

Nếu có nhiều cách chọn xâu con lặp liên tiếp để xoá, DRY phải chọn sao cho xâu cuối cùng ngắn nhất có thể. Ví dụ, với xâu "ABBCDCABCDCD", DRY có hai lựa chọn: xoá chữ "B" lặp ở gần đầu, hoặc xoá "CD" lặp ở cuối. Nếu xoá "B", DRY sẽ xoá được tiếp "ABCDC" lặp, được "ABCDCD", rồi cuối cùng xoá "CD" ở cuối, được "ABCD". Còn nếu DRY xoá "CD" ở cuối trước, nó còn lại "ABBCDCABCD", từ đó chỉ xoá được chữ "B" lặp để được "ABCDCABCD", và từ xâu này không xoá thêm được gì nữa. Vậy lựa chọn đúng của DRY là bắt đầu bằng việc nén chữ "B" đôi, và cuối cùng thu được "ABCD".

ICPC nhận thấy DRY cho kết quả tốt nhất trên các xâu nhị phân, tức là các xâu chỉ gồm chữ số 0 và 1. Vì vậy, họ giao cho bạn cài đặt thuật toán DRY tốt nhất có thể cho xâu nhị phân. Với một xâu nhị phân cho trước, hãy in ra một xâu ngắn nhất có thể thu được bằng cách áp dụng DRY nhiều lần lên nó.

Dữ liệu vào

Một dòng duy nhất chứa một xâu khác rỗng có độ dài không quá 105, chỉ gồm các chữ số 0 và 1.

Dữ liệu ra

In ra một dòng chứa một kết quả ngắn nhất có thể của việc chạy DRY trên xâu đã cho. Nếu có nhiều kết quả ngắn nhất, in ra kết quả nào cũng được.

Ràng buộc

  • 1≤ độ dài xâu ≤105.
  • Xâu chỉ gồm các ký tự 0 và 1.

Ví dụ

Input Output Giải thích
1111 1 Xoá liên tiếp các chữ 1 lặp: 1111, 111, 11, 1.
101 101 Xâu không chứa hai xâu con giống nhau đứng liền nhau nên không xoá được gì.
10110 10 Xoá một chữ 1 trong "11" được 1010, rồi xoá một lần "10" trong "1010" được 10.

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