450 - Little Black Book

[jhonny_yang]

Why did you write your own qsort?

Not saying it's wrong, but more chances to be wrong..

changes my qsort will solve the prob ?

[willy]

the code works perfectly on my com, can anyone tell me what is causing the runtime error?

Code: Select all

#include <stdio.h>
#include <string.h>

struct person
{
    char title[128], first[128], last[128], address[128];
    char depart[128], homep[128],workp[128], campusb[128];
};

int isblank(char *str)
{
    int i;
    
    for (i = 0; i < strlen(str);i++)
        if (str[i] != ' ')  
            return 0;
    return 1;            
}

int search(char *str, char sym, int start)
{
    int i;
    
    for (i = start; i < strlen(str); i++)
        if (str[i] == sym)
            return i;
    return -1;
}

void strbreak(char *dest, char *str, int start, int end)
{
    int i;
    
    for (i = start; i < end; i++)
        dest[i-start] = str[i];
    dest[end] = '\0';   
}

int main()
{
    int n, now, comma[30], i, j, count, total, flag, temp;
    person ppl[8192];
    char department[128], str[8192];
    
    scanf("%d\n",&n);
    now = 0;
    total = 0;
    for (i = 0; i < n; i++)
    {
        count = 0;
        while (gets(str)!=NULL) {
            if (isblank(str))
                break;
            if (count == 0)
            {
                count = 1;
                strcpy(department,str);
                continue;
            }
            comma[0] = search(str,',',0);
            for (j = 1; j < 6; j++)
                comma[j] = search(str,',',comma[j-1]+1);

            strbreak(ppl[now].title,str,0,comma[0]);
            strbreak(ppl[now].first,str,comma[0]+1,comma[1]);
            strbreak(ppl[now].last,str,comma[1]+1,comma[2]);
            strbreak(ppl[now].address,str,comma[2]+1,comma[3]);
            strbreak(ppl[now].homep,str,comma[3]+1,comma[4]);
            strbreak(ppl[now].workp,str,comma[4]+1,comma[5]);
            strbreak(ppl[now].campusb,str,comma[5]+1,strlen(str));
            strcpy(ppl[now].depart,department);
            total++;
            now++;
        }       
    }
    
    do {
        flag = 0;
        for (i = 1; i < total; i++)
        {
            for (j = 0; j < strlen(ppl[i].last); j++)
            {
                if (ppl[i].last[j] > ppl[i-1].last[j])
                    break;
                if (j >= strlen(ppl[i-1].last) || ppl[i].last[j] < ppl[i-1].last[j])
                {
                    ppl[total] = ppl[i];
                    ppl[i] = ppl[i-1];
                    ppl[i-1] = ppl[total];
                    flag = 1;
                    break;
                }
            }
        }
        
    } while (flag == 1);
    
    for (j = 0; j < total; j++)
    {
        printf("----------------------------------------\n");
        printf("%s %s %s\n",ppl[j].title,ppl[j].first,ppl[j].last);
        printf("%s\n",ppl[j].address);
        printf("Department: %s\n",ppl[j].depart);
        printf("Home Phone: %s\n",ppl[j].homep);
        printf("Work Phone: %s\n",ppl[j].workp);
        printf("Campus Box: %s\n",ppl[j].campusb);
    }
    
    return 0;
}

[Jan]

Actually it was quite a boring problem. Because it is easy but in the statement you will find no limit. I got many RTE's in this problem.

From my accepted solution I can give u the limitations.

Code: Select all

Title               25         characters
First name          25             ""
Last name           25             ""
Department          60             ""
Address             50             ""
Homephone           50             ""
Work phone          30             ""
Campus Box          30             ""
Total information   20000

Hope it helps.

[Jan]

You can find the limits in the following forum...

http://online-judge.uva.es/board/viewtopic.php?t=7156

You can use the qsort in c. But I use qsort manually.

[rmotome]

You will continue to get WA until you have the right number of dashes above every recond. Copy the dash line from the problem's output (there are 39 if I am not mistaken) paste it on your code. I had my program ACed after doing so; give this a try.

[thinker_bd]

whatz wrong with 450 help please code is given below
-------------

Code: Select all

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#define MAX 1000
struct info
{
	char t_name[MAX];
	char f_name[MAX];
	char l_name[MAX];
	char add[MAX];
	char dept[MAX];
	char h_phone[MAX];
	char w_phone[MAX];
	char cmp_box[MAX];
};

info a1[MAX];
char tmp[MAX];
char tmp2[MAX];

int cmp(const void *a,const void *b)
{
	info *p=(info *)a;
	info *q=(info *)b;
	return strcmp( p->l_name,q->l_name );
}


int main()
{
	//freopen("450.txt","r",stdin);
	int t_case;
   
	while((scanf("%d",&t_case))==1)
	{
		getchar();
		int k=0;
		while(t_case--)
		{
			gets(tmp2);
			int n2=strlen(tmp2);

							
			while(gets(tmp))
			{
			int a=strlen(tmp);
			  if(a==0) break;
		//////////title_name//////////////////////					  
				int z=0;			
				int j=0;
				while(1)
                {
				if(tmp[z]==',') break;
				
				a1[k].t_name[j]=tmp[z];				
				 j++;
				 z++; 	
				}

//////////////first_Name////////////////////////
				j=0;
				z=z+1;
				while(1)
                {
				if(tmp[z]==',') break;
				
				a1[k].f_name[j]=tmp[z];			
				 j++;
				 z++; 	
				}
////////////////last_name//////////////////////
				j=0;
				z=z+1;
				while(1)
                {
				if(tmp[z]==',') break;
				
				a1[k].l_name[j]=tmp[z];				
				 j++;
				 z++; 	
				}
/////////////////dept///////////////////////
				int z2=0;			
				int j2=0;
				while(1)
                {
				if(z2==n2) break;
				a1[k].dept[j2]=tmp2[z2];				
				 j2++;
				 z2++; 	
				}
/////////////////address////////////////
				j=0;
				z=z+1;
				while(1)
                {
				if(tmp[z]==',') break;
				
				a1[k].add[j]=tmp[z];				
				 j++;
				 z++; 	
				}
///////////////home_phone//////////////////
				j=0;
				z=z+1;
				while(1)
                {
				if(tmp[z]==',') break;
				
				a1[k].h_phone[j]=tmp[z];				
				 j++;
				 z++; 	
				}
/////////////////work_phone/////////////
				j=0;
				z=z+1;
				while(1)
                {
				if(tmp[z]==',') break;
				
				a1[k].w_phone[j]=tmp[z];				
				 j++;
				 z++; 	
				}

////////////////campus_box/////////////////
				j=0;
				z=z+1;
				while(1)
                {
				if(a==z) break;
				
				a1[k].cmp_box[j]=tmp[z];				
				 j++;
				 z++; 	
				}
/////////////////////////////////////

 			//	puts(tmp);
			k++;
			}
		}

		qsort(a1,k,sizeof(a1[0]),cmp);
	
		for(int m=0;m<k;m++)
		{
			printf("----------------------------------------\n");
			printf("%s ",a1[m].t_name);
			printf("%s ",a1[m].f_name);
			printf("%s\n",a1[m].l_name);
			
			printf("%s\n",a1[m].add);
			printf("Department: %s\n",a1[m].dept);
			printf("Home Phone: %s\n",a1[m].h_phone);
			printf("Work Phone: %s\n",a1[m].w_phone);
			printf("Campus Box: %s\n",a1[m].cmp_box);
		}
	}
 return 0;
}

[CodeMaker]

I know what's wrong in your code. you missed some zeros somewhere

[thinker_bd]

dear friend,
before submitting the 1st post i also try in following way and then
wrong answer turns into memory limit excited and WA is better that MLE
i tryed in following way

Code: Select all

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#define MAX 100
#define MAX2 10000
struct info
{
	char t_name[MAX];
	char f_name[MAX];
	char l_name[MAX];
	char add[MAX];
	char dept[MAX];
	char h_phone[MAX];
	char w_phone[MAX];
	char cmp_box[MAX];
};

info a1[MAX2];
char tmp[MAX];
char tmp2[MAX];

[CodeMaker]

sorry, i forgot to tell you not to put the zero in memory size, i m not mentioning zeros in MAX, try somewhere else. this is not about integers, this is about strings. i should now tell you that u forgot to put null values at the end of the strings. i think you know that all C string has a null at the end, did you put them?

[lovemagic]

total information for 3500 person is enough.

[arif_pasha]

There are 40 dashes.. not 39

[emotional blind]

I use the limits of Jan

I think my input and output format is also write

but so many time i got WA

here is my code
easier one to read

Code: Select all

#include <iostream>
#include <stdio.h>
#include <string.h>

using namespace std;

#define max 20001

struct inf{
	char dept[61];
	char title[26];
	char first[26];
	char last[26];
	char address[51];
	char home[51];
	char work[31];
	char mail[31]; 
}in[max];

void swap(int i, int j)
{
	inf p;
	p=in[i];
	in[i]=in[j];
	in[j]=p;
}

void qsort(int left, int right)
{
	int i, last;
	if(left>=right)return;
	swap(left, (left+right)/2);
	last=left;
	for(i=left+1;i<=right;i++)
		if(strcmp(in[i].last, in[left].last)<0)
			swap(++last, i);
	swap(left,last);
	qsort(left, last-1);
	qsort(last+1, right);
}

int main (void)
{
	int total=0, n, i;
	char *p;
	char buff[max], department[max], num[10];
	gets(num);
	sscanf(num,"%d",&n);
	//scanf("%d",&n);
	while(n){
		gets(department);
		//scanf("%s",&department);
		while(gets(buff)){
			if(strlen(buff)==0)break;
			strcpy(in[total].dept,department);
			p=strtok(buff,",");
			sscanf(p,"%[^,]",&in[total].title);
			p=strtok(NULL,",");
			sscanf(p,"%[^,]",&in[total].first);
			p=strtok(NULL,",");
			sscanf(p,"%[^,]",&in[total].last);
			p=strtok(NULL,",");
			sscanf(p,"%[^,]",&in[total].address);
			
			p=strtok(NULL,",");
			sscanf(p,"%[^,]",&in[total].home);
			p=strtok(NULL,",");
			sscanf(p,"%[^,]",&in[total].work);
			p=strtok(NULL,",");
			sscanf(p,"%[^\0]",&in[total].mail);
			total++;
		}
		n--;
	}	
	qsort(0, total-1);
	for(i=0;i<total;i++){
		printf("----------------------------------------\n");
		printf("%s %s %s\n",in[i].title, in[i].first, in[i].last);
		printf("%s\n",in[i].address);
		printf("Department: %s \nHome Phone: %s\nWork Phone: %s\nCampus Box: %s\n",in[i].dept,in[i].home, in[i].work, in[i].mail);
	}
	return 0;
}

so many WA..
please help now..

[Jan]

I haven't found any error. But when I replaced your input parsing part with mine, it got Accepted. That means there can be any error in your input parsing. The rest are ok.

And another thing, though I am not sure, there can be inputs like...

Input:

Code: Select all

3
English Department
Dr.,Tom,Zavis,Anystreet USA,555-2832,555-2423,823
Mrs.,Jessica,Lembeck,Center Street,555-2543,555-8584,928


Computer Science
Mr.,John,Kepler,East Pleasure,555-1432,555-2343,126
Jane,Alam,Jan,Dhaka,880-0014,876-0067,876

Output:

Code: Select all

----------------------------------------
Jane Alam Jan
Dhaka
Department: Computer Science
Home Phone: 880-0014
Work Phone: 876-0067
Campus Box: 876
----------------------------------------
Mr. John Kepler
East Pleasure
Department: Computer Science
Home Phone: 555-1432
Work Phone: 555-2343
Campus Box: 126
----------------------------------------
Mrs. Jessica Lembeck
Center Street
Department: English Department
Home Phone: 555-2543
Work Phone: 555-8584
Campus Box: 928
----------------------------------------
Dr. Tom Zavis
Anystreet USA
Department: English Department
Home Phone: 555-2832
Work Phone: 555-2423
Campus Box: 823

Your code fails for these types of inputs. I think this is the reason for your WA's.

Hope it helps.

[emotional blind]

i changed my parsing and get wrong answer
Jan now my code can handle your inputs
whats wrong now..
can you help giving your parsing part

my code

Code: Select all

#include <iostream>
#include <stdio.h>
#include <string.h>

using namespace std;

#define max 20001

struct inf{
	char dept[61];
	char title[26];
	char first[26];
	char last[26];
	char address[51];
	char home[51];
	char work[31];
	char mail[31]; 
}in[max];

void swap(int i, int j)
{
	inf p;
	p=in[i];
	in[i]=in[j];
	in[j]=p;
}

void qsort(int left, int right)
{
	int i, last;
	if(left>=right)return;
	swap(left, (left+right)/2);
	last=left;
	for(i=left+1;i<=right;i++)
		if(strcmp(in[i].last, in[left].last)<0)
			swap(++last, i);
	swap(left,last);
	qsort(left, last-1);
	qsort(last+1, right);
}

int main (void)
{
	int total=0, n, i;
	char *p;
	char buff[max], department[max], num[10];
	gets(num);
	sscanf(num,"%d",&n);
	//scanf("%d",&n);
	while(n){
		gets(department);
		//scanf("%s",&department);
		if(strlen(department))
		while(gets(buff)){
			if(strlen(buff)==0)break;
			strcpy(in[total].dept,department);
			p=strtok(buff,",");
			sscanf(p,"%[^,]",&in[total].title);
			p=strtok(NULL,",");
			sscanf(p,"%[^,]",&in[total].first);
			p=strtok(NULL,",");
			sscanf(p,"%[^,]",&in[total].last);
			p=strtok(NULL,",");
			sscanf(p,"%[^,]",&in[total].address);
			
			p=strtok(NULL,",");
			sscanf(p,"%[^,]",&in[total].home);
			p=strtok(NULL,",");
			sscanf(p,"%[^,]",&in[total].work);
			p=strtok(NULL,",");
			sscanf(p,"%[^\0]",&in[total].mail);
			total++;
		}
		n--;
	}	
	qsort(0, total-1);
	for(i=0;i<total;i++){
		printf("----------------------------------------\n");
		printf("%s %s %s\n",in[i].title, in[i].first, in[i].last);
		printf("%s\n",in[i].address);
		printf("Department: %s \nHome Phone: %s\nWork Phone: %s\nCampus Box: %s\n",in[i].dept,in[i].home, in[i].work, in[i].mail);
	}
	return 0;
}

[Jan]

Here is my input parsing part...

Code: Select all

    int n,fl,m=0,total,i,p,len,j;
    char temp[1000],temp1[1000];
    
    scanf("%ld",&n);
    gets(temp1);
    for(i=0;i<n;i++)
    {
	fl=0;
	while(gets(temp))
	{
	    if(temp[0]=='\0')
		break;
	    if(fl==0)
	    {
		strcpy(temp1,temp);
		fl=1;
	    }
	    else
	    {		
		p=0;
		len=strlen(temp);
		for(j=0;j<len;j++,p++)
		{
		    if(temp[j]==',')
			break;
		    in[m].title[p]=temp[j];
		}
		in[m].title[p]='\0';
		p=0;
		for(j++;j<len;j++,p++)
		{
		    if(temp[j]==',')
			break;
		    in[m].first[p]=temp[j];
		}
		in[m].first[p]='\0';

		p=0;
		for(j++;j<len;j++,p++)
		{
		    if(temp[j]==',')
			break;
		    in[m].last[p]=temp[j];
		}
		in[m].last[p]='\0';

		p=0;
		for(j++;j<len;j++,p++)
		{
		    if(temp[j]==',')
			break;
		    in[m].address[p]=temp[j];
		}
		in[m].address[p]='\0';
		p=0;
		for(j++;j<len;j++,p++)
		{
		    if(temp[j]==',')
			break;
		    in[m].home[p]=temp[j];
		}
		in[m].home[p]='\0';
		p=0;
		for(j++;j<len;j++,p++)
		{
		    if(temp[j]==',')
			break;
		    in[m].work[p]=temp[j];
		}
		in[m].work[p]='\0';
		p=0;
		for(j++;j<len;j++,p++)
		{
		    if(temp[j]==',')
			break;
		    in[m].mail[p]=temp[j];
		}
		in[m].mail[p]='\0';
		strcpy(in[m].dept,temp1);
		m++;
	    }
	}
    }
    total=m;

I have converted it as your code... I dont know why the spacing is different here. Sorry for that.

Hope it works.