codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

365B.md (1182B)


      1 Source: https://codeforces.com/problemset/problem/365/B
      2 
      3 B. The Fibonacci Segment
      4 
      5 time limit per test
      6 
      7 1 second
      8 
      9 memory limit per test
     10 
     11 256 megabytes
     12 
     13 input
     14 
     15 stdin
     16 
     17 output
     18 
     19 stdout
     20 
     21 You have array *a*1, *a*2, ..., *a**n*. Segment [*l*, *r*] (1 ≤ *l* ≤ *r* ≤ *n*) is good if *a**i* = *a**i* - 1 + *a**i* - 2, for all *i* (*l* + 2 ≤ *i* ≤ *r*).
     22 
     23 Let's define *len*([*l*, *r*]) = *r* - *l* + 1, *len*([*l*, *r*]) is the length of the segment [*l*, *r*]. Segment [*l*1, *r*1], is longer than segment [*l*2, *r*2], if *len*([*l*1, *r*1]) > *len*([*l*2, *r*2]).
     24 
     25 Your task is to find a good segment of the maximum length in array *a*. Note that a segment of length 1 or 2 is always good.
     26 
     27 Input
     28 
     29 The first line contains a single integer *n* (1 ≤ *n* ≤ 105) — the number of elements in the array. The second line contains integers: *a*1, *a*2, ..., *a**n* (0 ≤ *a**i* ≤ 109).
     30 
     31 Output
     32 
     33 Print the length of the longest good segment in array *a*.
     34 
     35 Examples
     36 
     37 Input
     38 
     39 ```
     40 10  
     41 1 2 3 5 8 13 21 34 55 89
     42 ```
     43 
     44 Output
     45 
     46 ```
     47 10
     48 ```
     49 
     50 Input
     51 
     52 ```
     53 5  
     54 1 1 1 1 1
     55 ```
     56 
     57 Output
     58 
     59 ```
     60 2
     61 ```