codeforces-scrape

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

219C.md (1106B)


      1 Source: https://codeforces.com/problemset/problem/219/C
      2 
      3 C. Color Stripe
      4 
      5 time limit per test
      6 
      7 2 seconds
      8 
      9 memory limit per test
     10 
     11 256 megabytes
     12 
     13 input
     14 
     15 stdin
     16 
     17 output
     18 
     19 stdout
     20 
     21 A colored stripe is represented by a horizontal row of *n* square cells, each cell is pained one of *k* colors. Your task is to repaint the minimum number of cells so that no two neighbouring cells are of the same color. You can use any color from 1 to *k* to repaint the cells.
     22 
     23 Input
     24 
     25 The first input line contains two integers *n* and *k* (1 ≤ *n* ≤ 5·105; 2 ≤ *k* ≤ 26). The second line contains *n* uppercase English letters. Letter "A" stands for the first color, letter "B" stands for the second color and so on. The first *k* English letters may be used. Each letter represents the color of the corresponding cell of the stripe.
     26 
     27 Output
     28 
     29 Print a single integer — the required minimum number of repaintings. In the second line print any possible variant of the repainted stripe.
     30 
     31 Examples
     32 
     33 Input
     34 
     35 ```
     36 6 3  
     37 ABBACC
     38 ```
     39 
     40 Output
     41 
     42 ```
     43 2  
     44 ABCACA
     45 ```
     46 
     47 Input
     48 
     49 ```
     50 3 2  
     51 BBB
     52 ```
     53 
     54 Output
     55 
     56 ```
     57 1  
     58 BAB
     59 ```