#2056. TRIBONACCI

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
Đưa lên bởi: Trùm CUỐI

Đề bài

Nguồn: Free Contest 7

Dãy số tribonacci được định nghĩa như sau:

  • a_0=0, a_1=0, a_2=1 ;
  • a_n = a_{n-1} + a_{n-2} + a_{n-3}, n ≥ 3 .

Các phần tử ban đầu của dãy là: 0, 0, 1, 1, 2, 4, 7, 13, 24, 44, 81, 149, 274, 504, 927, 1705, 3136, 5768,10609, 19513, 35890, 66012, 121415, 223317 , 410744, 755476,1389537, 2555757, 4700770, 8646064, …

Cho số n , tìm số tribonacci đầu tiên lớn hơn hoặc bằng n .

Dữ liệu vào:

  • Input gồm nhiều test, số lượng test không quá 100 ;
  • Mỗi test gồm một dòng chứa số nguyên n\ (0 ≤ n ≤ 10^9) .

Dữ liệu ra:

  • Với mỗi test, in ra số tribonacci tìm được.

Ví dụ:

Dữ liệu vào:
1
2
3
4
5
Dữ liệu ra:
1
2
4
4
7