UVA 12482 Short Story Competition

Maratona de Programação da SBC – ACM ICPC – 2012                                                              

                                                Problem A

                                Short Story Competition

   Machado wants to be a writer.       He has written many short stories,  book reviews,  reports of trips

he made, and a little romance.  Now Machado wants to take part in a short story competition, which

has very strict rules about the submission format.

   The  rules  of  the  competition  limit  the  number  of  total  pages,  and  specify  the  maximum  number

of characters per line, and the maximum number of lines per page.           Additionally, each word must be

written integrally in one line (ie, a word cannot be separated in two lines).  Machado wants to write a

story with as many words as possible within the rules of the contest, and needs your help.

   Given  the  maximum  number  of  characters  per  line,  the  maximum  number  of  lines  per  page,  and

the words of the short story that Machado is writing, he wants to know the minimum number of pages

that his short story will ocuppy, considering the rules of the contest.

Input

   The  first  line  of  a  test  case  contains  three  integers  N, L and  C,  which  indicate,  respectively,  the

number of words of the short story, the maximum number of lines per page and the maximum number

of  characters  per  line. Machado’s  short  story  is  innovative  and  contains  no  characters  besides  upper

and  lower  case  letters  and  blanks. The  second  line  contains  Machado’s  short  story,  consisting  of  N

words separated by exactly one blank space.

Output

   For each test case your program must output a single line containing a single integer indicating the

minimum number of pages the short story will ocuppy, considering the contest rules.

Restrictions

   • 2 ≤ N ≤ 1000

   • 1 ≤ L ≤ 30

   • 1 ≤ C ≤ 70

   • 1 ≤ length of each word  ≤ C

Example

Sample Input

14 4 20

Se mana Piedade tem casado com Quincas Borba apenas me daria uma esperanca colateral

16 3 30

No dia seguinte entrou a dizer de mim nomes feios e acabou alcunhando me Dom Casmurro

5 2 2

a de i de o

5 2 2

a e i o u

Sample output

2

1

3

3

题意：给你一篇短故事，求至少需要几页纸才能容纳这篇段故事，已知短故事有N个单词，每页能容纳L行，每行能容纳C个字符，这里要注意每个单词后有一个空格，一个单词只能在同一行。

思路：数据较小，直接定义二维数组算出每个单词的长度，然后一个个找下去即可。

#include<stdio.h>
#include<string.h>
char a[1111][77];
int b[1111];
int main()
{
  int n,l,c,sum,flag,i;
  while(scanf("%d %d %d",&n,&l,&c)!=EOF)
  {
    for(i=0;i<n;i++)
      scanf("%s",a[i]);
    for(i=0;i<n;i++)
      b[i]=strlen(a[i]);
    sum=0;
    flag=0;
    for(i=0;i<n;i++)
    {
      if(flag+b[i]<=c)
      {
        flag+=b[i];
        flag++;
      }
      else
      {
        sum++;
        flag=0;
        i--;
      }
    }
    if(flag!=0)
      sum++;
    if(sum%l==0)
      printf("%d\n",sum/l);
    else
      printf("%d\n",sum/l+1);
  }
  return 0;
}