G. HY022 - Chữ số thứ N

Bộ nhớ: 256 MiB Thời gian: 1000 ms Nhập/xuất từ luồng chuẩn
Kiểu bài: Thông thường Kiểu chấm: So sánh văn bản

Đề bài

Người ta xây dựng một số A gồm vô hạn chữ số chỉ gồm các chữ số 0, 1, 2 qua một số bước như sau:

  • Bước 0 : Gán cho chữ số đầu tiên của A a_1=0 ;
  • Bước k+1 : Giả sử ở bước k đã hình thành được m số hạng đầu của A a_1a_2\ldots a_m thì tại bước k+1 2\times m số hạng đầu của A a_1a_2\ldots a_mb_1b_2\ldots b_m mà với 1≤i≤m thì b_i=(a_i+1) mod\ 3 .

Như vậy các giai đoạn đầu hình thành số A như sau: 0 → 01 → 0112 → 01121220 → 0112122012202001 → \ldots

Yêu cầu: in ra chữ số thứ N của A\ (N≤10^{18}) .

Ví dụ N=4 thì a_N=2 ; N=8 thì a_N=0 .

Dữ liệu:

  • Gồm nhiều dòng (không quá 1000 dòng), mỗi dòng ghi một số nguyên dương N .

Kết quả:

  • Mỗi dòng ghi một kết quả tương ứng.

Ví dụ:

Dữ liệu:

4
8

Kết quả:

2
0