codeforces-scrape

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

954B.md (1622B)


      1 Source: https://codeforces.com/problemset/problem/954/B
      2 
      3 B. String Typing
      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 standard input
     16 
     17 output
     18 
     19 standard output
     20 
     21 You are given a string *s* consisting of *n* lowercase Latin letters. You have to type this string using your keyboard.
     22 
     23 Initially, you have an empty string. Until you type the whole string, you may perform the following operation:
     24 
     25 * add a character to the end of the string.
     26 
     27 Besides, at most once you may perform one additional operation: copy the string and append it to itself.
     28 
     29 For example, if you have to type string abcabca, you can type it in 7 operations if you type all the characters one by one. However, you can type it in 5 operations if you type the string abc first and then copy it and type the last character.
     30 
     31 If you have to type string aaaaaaaaa, the best option is to type 4 characters one by one, then copy the string, and then type the remaining character.
     32 
     33 Print the minimum number of operations you need to type the given string.
     34 
     35 Input
     36 
     37 The first line of the input containing only one integer number *n* (1 ≤ *n* ≤ 100) — the length of the string you have to type. The second line containing the string *s* consisting of *n* lowercase Latin letters.
     38 
     39 Output
     40 
     41 Print one integer number — the minimum number of operations you need to type the given string.
     42 
     43 Examples
     44 
     45 Input
     46 
     47 ```
     48 7  
     49 abcabca
     50 ```
     51 
     52 Output
     53 
     54 ```
     55 5
     56 ```
     57 
     58 Input
     59 
     60 ```
     61 8  
     62 abcdefgh
     63 ```
     64 
     65 Output
     66 
     67 ```
     68 8
     69 ```
     70 
     71 Note
     72 
     73 The first test described in the problem statement.
     74 
     75 In the second test you can only type all the characters one by one.