Đệ Quy #1

Dãy số Fibonacci, thường được ký hiệu là \(F(n)\), là một dãy số mà mỗi số bằng tổng của hai số đứng ngay trước nó. Dãy bắt đầu từ \(0\) và \(1\).

Cụ thể:

Cho số nguyên \(n\), hãy tính giá trị \(F(n)\).

Ví dụ 1

Input

n = 2

Output

1

Giải thích

Ví dụ 2

Input

n = 3

Output

2

Giải thích

Ví dụ 3

Input

n = 4

Output

3

Giải thích

Giới hạn

• \(0 \le n \le 30\)

Viết một hàm để đảo ngược một chuỗi. Chuỗi đầu vào được cho dưới dạng một mảng ký tự \(s\).

Bạn phải thực hiện việc đảo ngược bằng cách thay đổi trực tiếp mảng đầu vào, với độ phức tạp bộ nhớ bổ sung là \(O(1)\).

Ví dụ 1

Input

s = ["h", "e", "l", "l", "o"]

Output

["o", "l", "l", "e", "h"]

Ví dụ 2

Input

s = ["H", "a", "n", "n", "a", "h"]

Output

["h", "a", "n", "n", "a", "H"]

Giới hạn

• \(1 \le s.length \le 10^5\)
• \(s[i]\) là một ký tự ASCII có thể in được.

Trò chơi Tháp Hà Nội gồm có ba cọc, được đánh số như sau:

• Cọc \(1\) ở bên trái.
• Cọc \(2\) ở giữa.
• Cọc \(3\) ở bên phải.

Có \(n\) đĩa tròn với các kích thước khác nhau. Ban đầu, cọc bên trái chứa tất cả các đĩa, được sắp xếp theo thứ tự tăng dần về kích thước từ trên xuống dưới.

Mục tiêu là di chuyển tất cả các đĩa từ cọc bên trái sang cọc bên phải, sử dụng cọc ở giữa làm cọc trung gian.

Trong mỗi lượt, bạn được phép chọn đĩa nằm trên cùng của một cọc và chuyển nó sang một cọc khác.

Bạn không được phép đặt một đĩa lớn lên trên một đĩa nhỏ hơn.

Nhiệm vụ của bạn là tìm cách di chuyển tất cả các đĩa bằng số bước ít nhất.

Input

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

Output

Dòng đầu tiên in ra số nguyên \(k\): số bước di chuyển ít nhất.

Sau đó, in ra \(k\) dòng mô tả các bước di chuyển. Mỗi dòng chứa hai số nguyên \(a\) và \(b\), cho biết một đĩa được chuyển từ cọc \(a\) sang cọc \(b\).

Giới hạn

• \(1 \le n \le 16\)

Sample Input

2

Sample Output

3
1 2
1 3
2 3

Ta xây dựng một bảng gồm \(n\) hàng, được đánh số bắt đầu từ \(1\).

Hàng đầu tiên chỉ chứa ký tự:

0

Trong mỗi hàng tiếp theo, ta xét hàng ngay trước đó và thực hiện thay thế:

• Mỗi ký tự 0 được thay bằng 01.
• Mỗi ký tự 1 được thay bằng 10.

Ví dụ, với \(n=3\):

• Hàng thứ \(1\): 0
• Hàng thứ \(2\): 01
• Hàng thứ \(3\): 0110

Cho hai số nguyên \(n\) và \(k\), hãy xác định ký tự thứ \(k\), tính từ \(1\), trong hàng thứ \(n\).

Ví dụ 1

Input

n = 1, k = 1

Output

0

Giải thích

Hàng 1: 0

Ví dụ 2

Input

n = 2, k = 1

Output

0

Giải thích

Hàng 1: 0
Hàng 2: 01

Ví dụ 3

Input

n = 2, k = 2

Output

1

Giải thích

Hàng 1: 0
Hàng 2: 01

Giới hạn

• \(1 \le n \le 30\)
• \(1 \le k \le 2^{n-1}\)

Bạn đang leo một cầu thang gồm \(n\) bậc để lên đến đỉnh.

Trong mỗi lần di chuyển, bạn có thể bước lên \(1\) bậc hoặc \(2\) bậc.

Hãy xác định có bao nhiêu cách khác nhau để bạn có thể leo đến đỉnh cầu thang.

Ví dụ 1

Input

n = 2

Output

2

Giải thích

Có hai cách để leo đến đỉnh:

1. 1 bậc + 1 bậc
2. 2 bậc

Ví dụ 2

Input

n = 3

Output

3

Giải thích

Có ba cách để leo đến đỉnh:

1. 1 bậc + 1 bậc + 1 bậc
2. 1 bậc + 2 bậc
3. 2 bậc + 1 bậc

Giới hạn

• \(1 \le n \le 45\)

Cho một xâu, nhiệm vụ của bạn là liệt kê tất cả các xâu khác nhau có thể được tạo ra bằng cách sử dụng toàn bộ các ký tự của xâu đã cho.

Các xâu kết quả phải được sắp xếp theo thứ tự từ điển.

Input

Một dòng duy nhất chứa một xâu có độ dài \(n\).

Các ký tự trong xâu là các chữ cái tiếng Anh viết thường từ a đến z.

Output

Dòng đầu tiên in ra số nguyên \(k\): số lượng xâu khác nhau có thể được tạo ra từ xâu ban đầu.

Sau đó, in ra \(k\) dòng. Mỗi dòng chứa một xâu kết quả, theo thứ tự từ điển.

Giới hạn

• \(1 \le n \le 8\)

Sample Input

aabac

Sample Output

20
aaabc
aaacb
aabac
aabca
aacab
aacba
abaac
abaca
abcaa
acaab
acaba
acbaa
baaac
baaca
bacaa
bcaaa
caaab
caaba
cabaa
cbaaa