#include using namespace std; struct queue { queue* next; int p, kind; }; queue* init() { queue* q = new queue; q->next = NULL; return q; } void enq(queue* q, int p, int kind) { while (q->next != NULL) { q = q->next; } queue* t = new queue; t->next = NULL; t->p = p; t->kind = kind; q->next = t; } bool deq(queue* q, int* p, int* kind) { if (q->next == NULL) { return false; } else { *p = q->next->p; *kind = q->next->kind; queue* t = q->next; q->next = q->next->next; delete t; return true; } } int BinaryCount(int n) { int count = 0; while (n > 0) { count += n % 2; n /= 2; } return count; } int main(void) { int n; cin >> n; bool* flag = new bool[n]; for (int i = 0; i < n; ++i) { flag[i] = false; } queue* q = init(); int posi = 1, hosuu; int kind = 0; do { if (posi == n) { cout << kind << endl; return 0; } flag[posi - 1] = true; hosuu = BinaryCount(posi); if (posi - hosuu > 0 && !flag[posi - 1 - hosuu]) { enq(q, posi - hosuu, kind + 1); } if (posi + hosuu <= n && !flag[posi - 1 + hosuu]) { enq(q, posi + hosuu, kind + 1); } } while (deq(q, &posi, &kind)); cout << "-1" << endl; return 0; }