[Đội tuyển HSG9 Khoá 12] Đệ quy

Cho ba cọc \(A,B,C\) và có \(n\) chiếc đĩa đánh số từ \(1\) đến \(n\) có kích thước tương ứng là \(1\),\(2\),...,\(n\).Trạng thái ban đầu của \(n\) đều nằm ở cọc và đĩa to sẽ nằm phía dưới đĩa nhỏ hơn nó.

Yêu cầu

Hãy chuyển các đĩa từ cọc \(A\) sang cọc \(C\) sử dụng cọc \(B\) làm cọc trung gian sao cho các đĩa nhỏ luôn nằm trên đĩa to.

Input

Một dòng duy nhất chứa số nguyên dương \(n(n \leq 15)\) là số đĩa.

Output

Gồm nhiều dòng (không quá \(2^{15}\) dòng), mỗi dòng là một thao tác chuyển dạng \(X->Y\) tức là chuyển đĩa trên cùng ở cọc \(X\) đặt lên trên cùng ở cọc \(Y\) (\(X,Y \in \{A,B,C\})\).

2

A->B
A->C
B->C

Dãy số fibonanci \(f(n)\) được định nghĩa như sau:

• \(f(0)=1\)
• \(f(1)=1\)
• \(f(n)=f(n-1)+f(n-2),\forall n \geq 2\)

Cho số nguyên dương thứ \(n\), hãy tìm số fibonacci thứ \(N (N \leq 40)\)

Dữ liệu vào

Một dòng duy nhất chứa số nguyên \(N\).

Dữ liệu ra

Một dòng duy nhất chứa số nguyên \(f(n)\)

3

3

Cho hàm \(F(n)\) được định nghĩa như sau:

• \(F(0)='a'\)
• \(F(1)='b'\)
• \(F(2)='c'\)
• \(F(i) = F(i-3)+F(i-2)+F(i-1) \forall i>2\)

Cho hai số nguyên dương \(n\) và \(k\), hãy cho biết ký tự thứ \(k\) của \(F(n)\) là bao nhiêu. Biết rằng ký tự đầu tiên của \(F(n)\) được đánh số là \(1\).

Input

Dòng thứ nhất chứa hai số nguyên dương \(n\) và \(k\)

Output

Dòng thứ nhất chứa ký tự thứ \(k\) của \(F(n)\)

3 2

b

Ràng buộc

\(1 \leq k \leq |F(n)|\)

• Subtask \(1(40\% \text{số test})\): \(n\leq 10\)
• Subtask \(2(60\% \text{số test})\): \(n \leq 35\)

Cho số nguyên dương \(n(n \leq 10^9)\). Hãy in ra chữ số đầu tiên của \(N\).

Input

• Số nguyên \(N\).

Output

• Chữ số đầu tiên của \(N\).

4321

4