SGU127-Telephone directory - c++编程基础

127. Telephone directory

time limit per test: 0.5 sec.

memory limit per test: 4096 KB

CIA has decided to create a special telephone directory for its agents. The first 2 pages of the directory contain the name of the directory and instructions for agents, telephone number records begin on the third page. Each record takes exactly one line and consists of 2 parts: the phone number and the location of the phone. The phone number is 4 digits long. Phone numbers cannot start with digits 0 and 8. Each page of the telephone directory can contain not more then K lines. Phone numbers should be sorted in increasing order. For the first phone number with a new first digit, the corresponding record should be on a new page of the phone directory. You are to write a program, that calculates the minimal number P pages in the directory. For this purpose, CIA gives you the list of numbers containing N records, but since the information is confidential, without the phones locations.

Input

The first line contains a natural number K (0 < K < 255) - the maximum number of lines that one page can contain. The second line contains a natural N (0 < N < 8000) - number of phone numbers supplied. Each of following N lines contains a number consisting of 4 digits - phone numbers in any order, and it is known, that numbers in this list cannot repeat.

Output

First line should contain a natural number P - the number of pages in the telephone directory.

Sample Input

1234

5678

1345

1456

1678

1111

5555

6789

6666

5000

Sample Output

题目说一本电话本，按照一定的规则制作而成，规则是这样的：每个电话号码由4个数字组成，电话本的每一页最多包含k个数字；求这本电话本的页数。

第一行输入k，n；第二行输入n个电话号码。

#include  
#include  
#include  
#include  
#include  
#include  
#include  
#include  
#include  
#include  
#include  
#include  
#include  
using namespace std;  
int main()  
{  
    int k,n,w,sum;  
    int a[11];  
    while(scanf("%d%d",&k,&n)!=EOF)  
    {  
        sum=0;  
        memset(a,0,sizeof(a));  
        for(int i=1; i<=n; i++)  
        {  
            scanf("%d",&w);  
            a[w/1000]++;  
        }  
        for(int i=1; i<10; i++)  
        {  
            if(a[i])  
            {  
                sum++;  
                sum+=(a[i]-1)/k;  
            }  
        }  
        printf("%d\n",sum+2);  
    }  
    return 0;  
}