Contest Trại hè Miền Bắc 2023 - Xâu nhị phân
Xem dạng PDF
Gửi bài giải
Điểm:
30,00 (OI)
Giới hạn thời gian:
1.0s
Giới hạn bộ nhớ:
1G
Input:
stdin
Output:
stdout
Test chính thức
Dạng bài
Ngôn ngữ cho phép
C, C++, Java, Pascal, PyPy, Python, Scratch, TEXT
Trong trường hợp đề bài hiển thị không chính xác, bạn có thể tải đề bài tại đây: Đề bài
Cho hai số nguyên dương ~n~ và ~k~. Xét các xâu nhị phân độ dài ~n~ mà không có hai bit 1 nào kề nhau, hãy tìm xâu thứ ~k~ theo thứ tự từ điển.
Input
Gồm một dòng chứa hai số nguyên dương ~n~ ~k~ (~n \le 90; k \le 10^{18}~).
Output
Nếu số lượng xâu thoả mãn bé hơn ~k~, in ra -1. Ngược lại, in ra một xâu nhị phân độ dài ~n~ không có hai bit 1 kề nhau, là xâu thứ ~k~ tính theo thứ tự từ điển.
Scoring
| Subtask | Điểm | Ràng buộc |
|---|---|---|
| 1 | ~20\%~ | ~n \le 20~ |
| 2 | ~30\%~ | ~k \le 10^5~ |
| 3 | ~50\%~ | ~n \le 90; k \le 10^{18}~ |
Sample Input 1
4 7
Sample Output 1
1001
Notes
Có ~8~ xâu nhị phân độ dài ~4~ mà không có hai bit 1 kề nhau, được liệt kê theo thứ tự từ điển là: 0000, 0001, 0010, 0100, 0101, 1000, 1001, 1010. Xâu thứ ~7~ trong dãy là 1001.
Bình luận