Tham gia cuộc thi "Thiết kế thuật toán nén dữ liệu", các thí sinh được Ban tổ chức yêu cầu xây dựng hàm nén dữ liệu và trả lời truy vấn như sau:

• Hàm nén dữ liệu: string zip(string x), trong đó:

  • ~x~ là một xâu nhị phân độ dài ~n~;

  • hàm cần trả về một xâu nhị phân ~y~ là xâu ~x~ sau khi nén;

• Hàm trả lời truy vấn: vector<int> answer(int n, string y), trong đó:

  • ~y~ là kết quả sau khi nén xâu ~x~ và ~n~ là độ dài xâu ~x~;

  • hàm cần trả về một dãy ~r~ có độ dài ~n~, trong đó ~r[i]~ (~0 \le i < n~) là số lượng số ~1~ nhiều nhất có thể khi chọn một xâu con gồm ~i+1~ ký tự liên tiếp của ~x~;

  • Kết quả trả về được chấp nhận nếu mọi phần tử chênh lệch không quá ~5\%~ với kết quả đúng, cụ thể, gọi ~s~ là dãy kết quả đúng thì ~\frac{|s[i]-r[i]|}{s[i]}\le 5\%~;

Input

Thí sinh cần cài đặt hai hàm đã nêu trong chương trình và cần phải khai báo thư viện bằng dòng lệnh #include "apziplib.h" ở đầu chương trình. Ngoài ra, thí sinh được phép khai báo thêm thư viện, xây dựng các hàm, sử dụng biến toàn cục khác nếu cần.

Lưu ý rằng, hàm zip và answer sẽ được gọi ở các tiến trình độc lập. Vì vậy, nếu hàm zip có sử dụng và lưu trữ dữ liệu vào các biến toàn cục, các dữ liệu này sẽ không tồn tại khi hàm answer được thực thi.

Scoring

Có tất cả ~5~ subtask. Với mỗi subtask, gọi ~Q~ là yêu cầu mức độ nén, với mỗi test trong subtask, cách tính phần trăm số điểm như sau:

• Thí sinh sẽ nhận được ~0\%~ số điểm nếu:

  • chạy sinh lỗi;

  • tương tác sai quy cách;

  • chạy quá thời gian;

  • kết quả trả về của hàm answer không được chấp nhận;

• Ngược lại, gọi ~TS~ là độ dài xâu ~y~ mà thí sinh nén từ xâu ~x~, khi đó phần trăm số điểm của test là:

  • ~0\%~ nếu ~TS>3\times Q~;

  • ~100\%~ nếu ~TS\le Q~;

  • ~100\%\times\frac{3\times Q-TS}{2\times Q}~ nếu ~Q<TS\le 3\times Q~;</p>

Với mỗi subtask, gọi ~e~ là phần trăm số điểm nhỏ nhất của một test mà thí sinh đạt được trong các test thuộc subtask, ~score~ là điểm của subtask, khi đó, điểm cho subtask được tính bằng ~e\times score~.