LEXSTR - Khôi phục xâu 1
Xem dạng PDF
Gửi bài giải
Điểm:
1,00 (OI)
Giới hạn thời gian:
1.0s
Giới hạn bộ nhớ:
256M
Tác giả:
Dạng bài
Ngôn ngữ cho phép
C, C#, C++, Go, Java, Pascal, Perl, PHP, PyPy, Python, Ruby, Rust, Scratch, Swift
Cho một xâu ~s~ dộ dài ~n~ chỉ gồm các kí tự latin in thường. Một số kí tự trong xâu ~s~ bị mờ và không thể đọc được (các kí tự bị mờ này sẽ được biểu diễn bằng kí tự ? ). Hãy tìm cách khôi phục các kí tự bị mờ trong xâu ~s~ sao cho:
- Với mỗi kí tự ~c~ từ
ađếnz, tần số của kí tự ~c~ trong xâu ~s~ đúng bằng ~f_c~. - Xâu ~s~ có thứ tự từ điển nhỏ nhất.
Lưu ý:Xâu ~x~ được gọi là có thứ tự từ điển nhỏ xâu ~y~ nếu xâu ~x~ là tiền tố của xâu ~y~ hoặc ~x_k < y_k~ (với ~k~ là vị trí ~i~ nhỏ nhất mà ~x_i \le y_i~).
Input
- Dòng đầu tiên gồm số nguyên ~n~ - độ dài xâu ~s\ (1 ≤ n ≤ 1000)~;
- Dòng thứ hai gồm một xâu độ dài ~n~, chỉ gồm các kí tự latin in thường và kí tự
?- mô tả xâu ~s~; - Dòng thứ ba gồm ~26~ số nguyên ~f_a, f_b, . . ., f_z~ - tần số của các kí tự từ
ađếnztrong xâu ~s~. Dữ liệu vào đảm bảo tổng ~26~ số nguyên này đúng bằng ~n~.
Output
- In ra xâu ~s~ sau khi được khôi phục các kí tự bị mờ. Trong trường hợp không có cách khôi phục xâu ~s~ thỏa điều kiện đề bài, hãy in ra ~-1~.
Sample
Input #1
6
y???z?
2 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1
Output #1
yaabzc
Input #2
6
yy??z?
2 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1
Output #2
-1
Input #3
11
fr??co?te?t
0 0 1 0 3 1 0 0 0 0 0 0 0 1 1 0 0 1 1 2 0 0 0 0 0 0
Output #3
freecontest
Problem source: Kc97ble - Free Contest
Bình luận
ý tưởng của mình là dùng vector lưu các cặp (pair<char,int>) để lưu mảng tần suất , tạo 1 thằng char t ='a' ở bên ngoài để t++ trong vòng lặp thì sẽ được các kí tự còn lại -Tuy nhiên mình cần cập nhập lại giá second là phải trừ đi cả số lần xuất hiện trong xâu nhập vào , nếu có thằng nào ra âm thì in ra -1 luôn -Sau đó duyệt vòng lặp của mảng kí tự với 1 thằng temp=0 để kiểm soát sự tăng của kí tự có thể thay thế , nếu kí tự nào ? thì sẽ duyệt while đến khi nào mà pair[k++].second>0 thì mới dừng , nếu k vượt ngoài 26 thì in ra -1 , còn không thì thay : a[i]=pa[i].first , đồng thời phải trừ pa[i].second đi 1 . Cứ như thế là AC .