Bài 36 - Giải thuật nhập môn

Dãy 0-1 là dãy vô hạn phần tử chỉ gồm các số 0 và 1 được xây dựng theo quy luật sau đây: Số đầu tiên là số 0. Nối vào dãy các số đã viết “dãy số đảo” của nó ( là dãy số có cùng chiều dài với dãy đã viết, trong đó số 0 ở dãy đã viết thành số 1 ở “dãy số đảo” và số 1 ở dãy đã viết trở thành số 0 ở “dãy số  đảo”). Như vậy sau mỗi lần nối, chiều dài của dãy tăng lên gấp đôi.
Dưới đây là 5 bước đầu tiên để hình thành dãy 0-1:
0
0 1
0 1 1 0
0 1 1 0 1 0 0 1
0 1 1 0 1 0 0 1 1 0 0 1 0 1 1 0
Nhiệm vụ:
Viết chương trình xa1xc định chữ số ở vị trí thứ N của dãy 0-1
Dữ liệu: Cho trong tập tin SEQ01.inp gồm 1 dòng duy nhất chứa 1 số nguyên  dương N duy nhất ( N<=30000)
Kết quả: Cho trong tập tin văn bản SEQ01.out, chứa 1 số nguyên duy nhất chỉ chữ số ở vị trí thứ N của dãy 0-1
Ví dụ: 
SEQ01.inp:
11
SEQ01.out:
0