codeforces-scrape

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

1090M.md (1256B)


      1 Source: https://codeforces.com/problemset/problem/1090/M
      2 
      3 M. The Pleasant Walk
      4 
      5 time limit per test
      6 
      7 1 second
      8 
      9 memory limit per test
     10 
     11 512 megabytes
     12 
     13 input
     14 
     15 standard input
     16 
     17 output
     18 
     19 standard output
     20 
     21 There are $n$ houses along the road where Anya lives, each one is painted in one of $k$ possible colors.
     22 
     23 Anya likes walking along this road, but she doesn't like when two adjacent houses at the road have the same color. She wants to select a long segment of the road such that no two adjacent houses have the same color.
     24 
     25 Help Anya find the longest segment with this property.
     26 
     27 Input
     28 
     29 The first line contains two integers $n$ and $k$ — the number of houses and the number of colors ($1 \le n \le 100\,000$, $1 \le k \le 100\,000$).
     30 
     31 The next line contains $n$ integers $a_1, a_2, \ldots, a_n$ — the colors of the houses along the road ($1 \le a_i \le k$).
     32 
     33 Output
     34 
     35 Output a single integer — the maximum number of houses on the road segment having no two adjacent houses of the same color.
     36 
     37 Example
     38 
     39 Input
     40 
     41 ```
     42 8 3
     43 1 2 3 3 2 1 2 2
     44 ```
     45 
     46 Output
     47 
     48 ```
     49 4
     50 ```
     51 
     52 Note
     53 
     54 In the example, the longest segment without neighboring houses of the same color is from the house 4 to the house 7. The colors of the houses are $[3, 2, 1, 2]$ and its length is 4 houses.