Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

NKJUMP - VOI08 Lò cò

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 ai. 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ố ai, aj, ak thỏa mãn ak = ai + aj 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:

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ẽ).

Yêu cầu

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.

Dữ liệu

  • Dòng đầu chứa số nguyên n (3 ≤ n ≤ 1000);
  • Dòng thứ hai chứa dãy số nguyên dương a1, a2, ..., an (ai ≤ 109, 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.

Kết quả

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

Ràng buộc

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

Ví dụ

Dữ liệu:
5
1 2 8 3 5

Kết qủa
4

Được gửi lên bởi:Duc
Ngày:2008-01-29
Thời gian chạy:0.217s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:Tất cả ngoại trừ: ERL GOSU JS-RHINO PERL6 PYPY RUST SED
Nguồn bài:VOI 2008

hide comments
2018-09-03 15:30:22
long long mới AC nha mn :)
2018-02-08 07:32:06
vl thật, n^3 mà result 100
2018-02-04 15:03:02
THAM KHẢO THUẬT TOÁN VÀ CODE TẠI:

http://yeulaptrinh.pw/406/nkjump-spoj/



2017-12-28 10:16:25
PD
2017-10-04 01:34:03
Code AC: http://123link.top/NKJUMP
2017-08-21 16:05:29
Kham khảo:
https://vietcodes.github.io/code/52/
2017-07-24 17:52:43
ảo quá 100 mà n^2logn -.-
2017-06-14 04:00:50
2^n cx AC
2017-06-01 14:03:17
1 đấm AC
O(nlogn) nha ^^
from Dinh Truong Lam
2017-02-15 08:55:06
14,2 có cách sửa ko mn
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.