codeforces-scrape

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

100D.md (1783B)


      1 Source: https://codeforces.com/problemset/problem/100/D
      2 
      3 D. World of Mouth
      4 
      5 time limit per test
      6 
      7 5 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 There are a lot of rumors in the media these days. One day Aida decided to find out how rumors are made.
     22 
     23 She asked *n* of her friends to help her. They all formed a circle and Aida told the person to her right a piece of news which was just a simple string. Then each person told the string to the person on his/her right. But they didn't tell the string exactly as they'd heard it. Each person made at most one of these two types of changes:
     24 
     25 * Removing one character from the end of the heard string.
     26 * Adding a character to the end of the heard string.
     27 
     28 Finally when the rumor passed exactly *n* moves (a complete cycle), Aida heard something quite different from what she expected from the person on her left. She thinks someone has cheated and made some changes other than those explained above. Now she wants you to write a Pike piece of code which gets the initial and final strings and tells Aida whether it's possible to get to the final string from the initial one, by the rules described above.
     29 
     30 Input
     31 
     32 The first line contains a single integer *n* (2 ≤ *n* ≤ 8 × 106), the number of Aida's friends. The following two lines contain a non-empty string each — initial and final strings. The lengths of strings are at most 107 and they only contain English alphabet letters.
     33 
     34 Output
     35 
     36 Write a single YES or NO. Write YES only if it's possible to get to the final string from the initial string.
     37 
     38 Examples
     39 
     40 Input
     41 
     42 ```
     43 100  
     44 Codeforces  
     45 MMIODPC
     46 ```
     47 
     48 Output
     49 
     50 ```
     51 Yes
     52 ```
     53 
     54 Input
     55 
     56 ```
     57 5  
     58 MMIOD  
     59 CF
     60 ```
     61 
     62 Output
     63 
     64 ```
     65 No
     66 ```
     67 
     68 Note
     69 
     70 The input is case-sensitive, while the output is not.