Time Limit: 3000MS

Memory Limit: Unknown

64bit IO Format: %lld & %llu

[]   []   []

Description

Your chief judge is getting long in the tooth and it is getting increasingly difficult for him to read through the densely-written messages of complaints about the problems and scores. The chief judge prefers to have more and uniform spacing between the words, and you have been drafted to write a program to format lines of text accordingly.

Your task is to write a program to read a number of lines of text and format each line independently such that:

1. successive words on a formatted line are separated by exactly two blank spaces, and
2. words are NOT split between lines, and
3. width of the formatted text does not exceed a specified value.

Leading and trailing blank spaces on each given line should be ignored.

As an example:

Your chief judge is geting long in the tooth.

Have a nice day.

Your chief judge

is geting long in

the tooth.

Have a nice day.

01234567890123456789

The first input line is formatted into three (3) lines of width bounded by 20 places, and words separated by two blank spaces in each line. The second input line is formatted independently on the fourth output line.

Input 

Input to this problem starts with an integer K , K > 0 , that represents the number of messages. The number K is given on a separate line followed by a description of the K messages. The description of each message starts with a line that contains two integers. The first integer W , W20 , represents the desired width of the formatted text, and the second integer N , N > 0 , represents the number of lines in the message. A single blank space separates the two integers. The message, which consists of N lines, follows with each line consisting of a sequence of one or more words separated by blank spaces. The length of each word is less than or equal to W . That is, a word like ``supercalifragilistic-expialidocious" is only to be expected as part of the input if W35 .

Output 

For each message the output consists of one line. The line starts with the message number (the first message being ``Message 1"), followed by a ``: " (colon followed by space), as shown in the Sample Output below. This is followed by the number of lines that the formatted text would occupy.

Sample Input 

220 1Your chief judge is geting long in the tooth.30 2For each message the output consists of one line.The chief judge now prefers to have more and uniform spacing

Sample Output 

Message 1: 3Message 2: 6

/立立的代码 #include
       
         #include
        
          #include
         
           #include
          
            #include
           
             using namespace std; inline void read( int &p ) {
      char ch; int f = 1; while( ch = getchar(),(ch < '0' || ch > '9' )&& ch != '-' ); if( ch == '-' )         f = -1,p = 0; else         p = ch - '0'; while( ch = getchar(),( ch >= '0' && ch <= '9' ) )         p = p * 10 + ch - '0';     p *= f; } int last,first,s,n,m; char str[1000005]; int get(  ) {
      int i = 0; while( str[first] && str[first] != ' ' ) ++first,++i;//printf( "%s\n",str+first );     return i; } void cal(  ) {
      int temp,len = strlen( str ),c;     last = len - 1,first = 0; while( last >= 0 && str[last] == ' ' ) str[last] = 0,--last; while( str[first] && str[first] == ' ' ) ++first;     temp = c = 0; while( str[first] )     {
              temp = get(  ); if( c + temp > n )             c = temp,++s; else             c += temp; while( str[first] == ' ' ) ++first,c += 2;     } } int main(  ) {
      int Case;     scanf( "%d",&Case ); for( int i = 1; i <= Case; ++i )     {
              scanf( "%d%d\n",&n,&m );         s = 0; while( m-- )         {
                  gets( str ); ++s;             cal(  );//printf( "Message %d: %d\n",i,s );         }         printf( "Message %d: %d\n",i,s);     } //system( "pause" );     return 0; }