Có một sự kiện âm nhạc được diễn ra gần khu nhà của Tèo. Vé của sự kiện được nhận bằng cách mua hoặc tham gia chuỗi trò chơi tại sự kiện.
Là một sinh viên nghèo vượt khó nên Tèo sẽ tham gia chuỗi trò chơi để săn vé tham gia sự kiện. Chuỗi trò chơi gồm hai hoạt động là checkin và giải câu đố. Mỗi người chơi được cung cấp một xâu ~s~ chỉ gồm các kí tự z
, e
, r
, o
và n
, để giải được câu đố người chơi cần sắp xếp lại xâu ~s~ để tìm được mật mã có dạng là xâu nhị phân 0
và 1
tương ứng với zero
và one
trong xâu kí tự được cung cấp.
Yêu cầu: Hãy giúp Tèo tìm mật mã để có thể săn được vé của sự kiện âm nhạc, in ra xâu mật mã có thứ tự từ điển lớn nhất.
Giả sử xâu ~s =~ zeonroe
, ta có thể sắp xếp lại thành zeroone
, mật mã tìm được là 10
.
Chú ý: xâu ~a_{1}a_{2}a_{3}...a_{n}~ có thứ tự từ điển lớn hơn xâu ~b_{1}b_{2}b_{3}...b_{n}~ khi và chỉ khi tồn tại chỉ số ~i~ sao cho:
- ~a_{i} > b_{i}~~(1 \le i \le n)~.
- Đồng thời, với mọi ~1 \le j < i~, ta luôn có ~a_{j} = b_{j}~.
Dữ liệu vào
- Một dòng duy nhất chứa xâu ~s~ (~|s| \le 10^6~) chỉ gồm các kí tự
z
,e
,r
,o
vàn
. - Dữ liệu luôn đảm bảo tồn tại cách sắp xếp xâu ~s~ thành một xâu chỉ được ghép từ
zero
vàone
, tướng ứng với0
và1
.
Dữ liệu ra
- Một dòng duy nhất chứa xâu mật mã có thứ tự từ điển lớn nhất có thể tìm được.
Ràng buộc
- Có ~30\%~ số test chỉ có các kí tự
z
,o
,r
vàe
trong xâu ~s~. - Có ~30\%~ số test chỉ có các kí tự
e
,n
vào
trong xâu ~s~. - Còn lại ~40\%~ số test không có ràng buộc gì thêm.
Ví dụ
Dữ liệu vào
nezoeoorne
Dữ liệu ra
110
Giải thích
Ta có thể sắp xếp lại thành oneonezero
, mật mã tìm được là 110
.
Bình luận