codeforces-scrape

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

70B.md (1996B)


      1 Source: https://codeforces.com/problemset/problem/70/B
      2 
      3 B. Text Messaging
      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 Fangy the little walrus, as all the modern walruses, loves to communicate via text messaging. One day he faced the following problem: When he sends large texts, they are split into parts each containing *n* characters (which is the size of one text message). Thus, whole sentences and words get split!
     22 
     23 Fangy did not like it, so he faced the task of breaking the text into minimal messages on his own so that no sentence were broken into pieces when it is sent and the number of text messages to be sent would be minimal. If two consecutive sentences are in different messages, the space between them can be ignored (Fangy does not write this space).
     24 
     25 The little walrus's text looks in the following manner:
     26 
     27 ```
     28 TEXT ::= SENTENCE | SENTENCE SPACE TEXT  
     29 SENTENCE ::= WORD SPACE SENTENCE | WORD END  
     30 END ::= {'.', '?', '!'}  
     31 WORD ::= LETTER | LETTER WORD  
     32 LETTER ::= {'a'..'z', 'A'..'Z'}  
     33 SPACE ::= ' '
     34 ```
     35 
     36 SPACE stands for the symbol of a space.
     37 
     38 So, how many messages did Fangy send?
     39 
     40 Input
     41 
     42 The first line contains an integer *n*, which is the size of one message (2 ≤ *n* ≤ 255). The second line contains the text. The length of the text does not exceed 104 characters. It is guaranteed that the text satisfies the above described format. Specifically, this implies that the text is not empty.
     43 
     44 Output
     45 
     46 On the first and only line print the number of text messages Fangy will need. If it is impossible to split the text, print "Impossible" without the quotes.
     47 
     48 Examples
     49 
     50 Input
     51 
     52 ```
     53 25  
     54 Hello. I am a little walrus.
     55 ```
     56 
     57 Output
     58 
     59 ```
     60 2
     61 ```
     62 
     63 Input
     64 
     65 ```
     66 2  
     67 How are you?
     68 ```
     69 
     70 Output
     71 
     72 ```
     73 Impossible
     74 ```
     75 
     76 Input
     77 
     78 ```
     79 19  
     80 Hello! Do you like fish? Why?
     81 ```
     82 
     83 Output
     84 
     85 ```
     86 3
     87 ```
     88 
     89 Note
     90 
     91 Let's take a look at the third sample. The text will be split into three messages: "Hello!", "Do you like fish?" and "Why?".