VOI 08 Bài 2 - Lò cò

View as PDF
Submit solution
Points: 0.08 (partial)
Time limit: 1.0s
Memory limit: 512M
Input: stdin
Output: stdout
Problem source:
VOI 2008
Problem type
Allowed languages
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

Nhảy lò cò là trò chơi dân gian của Việt Nam. Người trên hành tinh X cũng rất thích trò chơi này và họ đã cải biên trò chơi này như sau: Trên mặt phẳng vẽ ~n~ vòng tròn được đánh số từ 1 đến ~n~. Tại vòng tròn ~i~ người ta điền số nguyên dương ~a_{i}~ . Hai số trên hai vòng tròn tùy ý không nhất thiết phải khác nhau. Tiếp đến người ta vẽ các mũi tên, mỗi mũi tên hướng từ một vòng tròn đến một vòng tròn khác. Quy tắc vẽ mũi tên là: Nếu có ba số ~a_{i}~, ~a_{j}~, ~a_{k}~ thỏa mãn ~a_{k} = a_{i} + a_{j}~ thì vẽ mũi tên hướng từ vòng tròn ~i~ đến vòng tròn ~k~ và mũi tên hướng từ vòng tròn ~j~ đến vòng tròn ~k~. Người chơi chỉ được di chuyển từ một vòng tròn đến một vòng tròn khác nếu có mũi tên xuất phát từ một trong số các vòng tròn, di chyển theo cách mũi tên đã vẽ để đi đến các vòng tròn khác. Người thắng cuộc sẽ là người tìm được cách di chuyển qua nhiều vòng tròn nhất.

Ví dụ: Với 5 vòng tròn và các số trong vòng tròn là 1, 2, 8, 3, 5, trò chơi được trình bày trong hình dưới đây:

image

Khi đó có thể di chuyển được nhiều nhất qua 4 vòng tròn (tương ứng với đường di chuyển được tô đậm trên hình vẽ).

Hãy xác định xem trong trò chơi mô tả ở trên, nhiều nhất có thể di chuyển được qua bao nhiêu vòng tròn.

Input

  • Dòng đầu chứa số nguyên ~n~ ~(3 \leq n \leq 1000)~;
  • Dòng thứ hai chứa dãy số nguyên dương ~a_{1}, a_{2}, \dots, a_{n}~ ~(a_{i} \leq 10^{9}, i=1, 2,..., n)~.

Hai số liên tiếp trên một dòng được ghi cách nhau bởi dấu cách.

Output

Ghi ra số lượng vòng tròn trên đường di chuyển tìm được.

Giới hạn

  • 60% số tests ứng với 60% số điểm của bài có 3 ≤ n ≤ 100.

Sample Input

5
1 2 8 3 5

Sample Output

4

Comments

Please read the guidelines before commenting.


  • 0
    tiendat123  commented on Feb. 25, 2026, 3:09 a.m.

    ez dễ vãi


  • -5
    Tuananha12  commented on April 7, 2025, 5:26 p.m.

    This comment is hidden due to too much negative feedback. Show it anyway.


    • 0
      minhduca2k53  commented on Nov. 26, 2025, 12:25 a.m.

      Phải chịu bạn ạ


  • -7
    hieuhfgr  commented on May 6, 2024, 1:17 a.m.

    This comment is hidden due to too much negative feedback. Show it anyway.


    • -11
      sunshine262  commented on Aug. 20, 2024, 7:21 a.m.

      This comment is hidden due to too much negative feedback. Show it anyway.


  • -4
    PizzaPasta  commented on Dec. 7, 2023, 1:15 p.m. ← edited

    Bài khó ghê


  • -8
    orrigizaltaze  commented on Sept. 24, 2021, 3:31 p.m.

    This comment is hidden due to too much negative feedback. Show it anyway.


  • 5
    tamthegod  commented on May 20, 2021, 11:47 a.m.

    test hơi yếu ạ