Bedan Contest #01 - C - Nhảy lò cò - TLEOJ: TLE Online Judge

Bedan Contest #01 - C - Nhảy lò cò

Điểm: 1900 (thành phần)

Thời gian: 0.5s

Bộ nhớ: 256M

Input: hopping.inp

Output: hopping.out

Tác giả:

flo

Dạng bài

Ngôn ngữ cho phép

C++, ~~NASM~~, Pascal, pypy3, Python

Vì trời mưa liên tục những ngày nay nên flo chỉ có thể ở nhà mà không thể ra ngoài đường để chơi. Vì vậy flo quyết định rủ bạn bè đến nhà chơi nhảy lò cò

Trò chơi bắt đầu với một dãy gồm $n$ ô, ô ở vị trí $pos$ sẽ có số điểm là $a_{pos}$ . flo có tổng cộng $n$ lượt chơi và tại lượt thứ $i$ , cậu sẽ nhảy lên $i$ ô trong $n$ ô trên. Với mỗi bước nhảy, flo có thể nhảy đến một ô bất kì với điều kiện là vị trí ô cậu nhảy đến phải lớn hơn vị trí ô mà trước đó cậu đứng. Số điểm của mỗi lượt chơi sẽ là số nguyên dương $m$ lớn nhất thỏa mãn $P$ chia hết cho $10^m$ với $P$ là tích của số điểm của các ô mà flo nhảy lên trong lượt chơi đó.

Người chiến thắng sẽ là người có tống số điểm sau $n$ lượt chơi là cao nhất và flo muốn giành được chiến thắng. Tuy nhiên với mỗi lượt chơi, số lượng cách nhảy quá nhiều khiến cậu không biết phải làm như thế nào. Bạn hãy tính giúp flo số điểm tối đa cậu ấy có thể đạt được là bao nhiêu nhé.

Input, Output and Scoring

Input

Hai nguyên dương $n$ $(1 \le n \le 100)$ .
Dãy $a$ gồm $n$ phần tử $a_1, a_2, ..., a_n$ $(1 \le a_i \le 100)$ .

Output

In ra kết quả thỏa mãn.

Scoring

Subtask $1$ $(20\%)$ : $1 \le n \le 20$ .
Subtask $2$ $(80\%)$ : Không giới hạn gì thêm.

Example

Input

3
2 5 10

Output

Note

Tại lượt chơi $1$ , flo có thể nhảy vào ô thứ $3$ để có số điểm là $1$ .
Tại lượt chơi thứ $2$ , flo có thể nhảy vào ô thứ $1, 2$ để có số điểm là $1$ .
Tại lượt chơi thứ $3$ , flo có thể nhảy vào ô thứ $1, 2, 3$ để có số điểm là $2$ .
Tổng số điểm của các lượt chơi trên là $4$ , dễ dàng thấy đây là số điểm lớn nhất mà flo có thể đạt được.

Bình luận

Không có bình luận nào.