Phone Number-蒲公英云

Phone Number

#

Time Limit: 1000ms Memory limit: 65536K 有疑问？点这里^_^

题目描述

We know that if a phone number A is another phone number B’s prefix, B is not able to be called. For an example, A is 123 while B is 12345, after pressing 123, we call A, and not able to call B.
Given N phone numbers, your task is to find whether there exits two numbers A and B that A is B’s prefix.

输入

The input consists of several test cases.
The first line of input in each test case contains one integer N (0<N<1001), represent the number of phone numbers.
The next line contains N integers, describing the phone numbers.
The last case is followed by a line containing one zero.

输出

For each test case, if there exits a phone number that cannot be called, print “NO”, otherwise print “YES” instead.

示例输入

示例输出

NO
YES

提示

来源

2010年山东省第一届ACM大学生程序设计竞赛

示例程序

#include<iostream>  
#include<string>  
#include<stdio.h>  
#include<string.h>  
#include<stdlib.h>  
using namespace std;  
/*struct node 
{ 
    int num; 
    char name[10000]; 
}a[1010],b; 
int cmp(const void *a,const void *b) 
{ 
    return (*(struct node *)a).num>(*(struct node *)b).num?1:-1; 
}*/  
string a[1005],k;  
int b[1005];  
int main()  
{  
    int n,i,j,p,s;  
    while(scanf("%d",&n)&&n)  
    {  
        s=0;  
        for(i=0;i<n;i++)  
        /*{ 
            scanf("%s",a[i].name); 
            a[i].num=strlen(a[i].name); 
        } 
        qsort(a,n,sizeof(a[0]),cmp);*/  
            //gets(a[i]);  
            //scanf("%s",a[i]);  
        cin>>a[i];  
        for(i=0;i<n-1;i++)  
            for(j=0;j<n-1-i;j++)  
            {  
                if(a[j]>a[j+1])  
            {  
                k=a[j];  
            a[j]=a[j+1];  
            a[j+1]=k;  
            }  
            }  
            for(i=0;i<n;i++)  
                b[i]=a[i].size();  
            for(i=0;i<n-1;i++)  
            {  
                p=b[i]<b[i+1]?b[i]:b[i+1];  
                for(j=0;j<p;j++)  
                     if(a[i][j]!=a[i+1][j])  
                        break;  
                     else if(j==p-1)  
                         s=1;  
            }  
            if(s==1)  
                printf("NO\n");  
            else  
                if(s==0)  
                    printf("YES\n");  
    }  
return 0;  
}