Xâu nhị phân

Xem PDF

Điểm: 300 (p) Thời gian: 1.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

Cho tập hợp tất cả các xâu nhị phân có độ dài \(N\) được sắp xếp theo thứ tự từ điển. Ví dụ \(N = 3\) ta có tập hợp: \(000, 001, 010, 011, 100, 101, 110, 111\).

Trong tập hợp trên, ta có:

  • Xâu nhị phân \(100\): ở vị trí số \(5\).
  • Vị trí số \(7\) trong tập là xâu nhị phân: \(110\).

Yêu cầu: Với một số \(N (N \le 63)\) cho trước, hãy cho biết:

  • Xâu nhị phân \(S\) (có độ dài \(N\)) nằm ở vị trí nào của tập.
  • Vị trí thứ \(K\) (\(1 \le K \le 10^{18}\)) là xâu nhị phân nào?

Input

  • Dòng đầu chứa một số nguyên \(N\), là độ dài của các xâu nhị phân.
  • Dòng thứ hai chứa một xâu nhị phân \(S\) có độ dài bằng \(N\).
  • Dòng thứ ba chứa một số nguyên \(K\).

Output

  • Dòng đầu tiên chứa một số nguyên là vị trí của \(S\) trong tập hợp.
  • Dòng thứ hai ghi xâu nhị phân có \(N\) phần tử nằm ở vị trí thứ \(K\).

Example

Test 1

Input
3
100
7   
Output
5
110

Bình luận

Không có bình luận nào.