450 - Little Black Book

All about problems in Volume 4. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

jhonny_yang
New poster
Posts: 22
Joined: Fri Jan 17, 2003 8:24 am

Post by jhonny_yang » Fri Dec 17, 2004 5:25 pm

Larry wrote: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
New poster
Posts: 11
Joined: Fri Aug 01, 2003 2:20 pm
Location: Singapore

450 [Runtime Error]

Post by willy » Thu Dec 23, 2004 5:11 pm

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
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Post by Jan » Thu Sep 15, 2005 11:23 pm

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. :)
Ami ekhono shopno dekhi...
HomePage

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Post by Jan » Thu Sep 15, 2005 11:33 pm

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.
Ami ekhono shopno dekhi...
HomePage

rmotome
New poster
Posts: 14
Joined: Mon Jan 10, 2005 12:20 pm
Location: Kitchener, Ontario, Canada

450 (Little Black Book) WA????? Look here first!!!!!!

Post by rmotome » Sun Sep 18, 2005 6:13 pm

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
New poster
Posts: 22
Joined: Thu Jun 09, 2005 1:44 am

whatz wrong with 450 help please

Post by thinker_bd » Tue Sep 27, 2005 8:19 pm

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;
}

User avatar
CodeMaker
Experienced poster
Posts: 183
Joined: Thu Nov 11, 2004 12:35 pm
Location: AIUB, Bangladesh

Post by CodeMaker » Wed Sep 28, 2005 12:26 pm

8) I know what's wrong in your code. you missed some zeros somewhere :wink:
Jalal : AIUB SPARKS

thinker_bd
New poster
Posts: 22
Joined: Thu Jun 09, 2005 1:44 am

Post by thinker_bd » Thu Sep 29, 2005 5:37 am

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];

User avatar
CodeMaker
Experienced poster
Posts: 183
Joined: Thu Nov 11, 2004 12:35 pm
Location: AIUB, Bangladesh

Post by CodeMaker » Fri Sep 30, 2005 6:35 am

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? :wink:
Jalal : AIUB SPARKS

lovemagic
Learning poster
Posts: 52
Joined: Thu Oct 02, 2003 11:38 am

limit

Post by lovemagic » Thu Dec 01, 2005 11:15 pm

total information for 3500 person is enough.
khobaib

arif_pasha
New poster
Posts: 42
Joined: Fri Jun 13, 2003 3:47 pm
Location: Dhaka , Bangladesh
Contact:

Post by arif_pasha » Tue Jan 24, 2006 6:48 pm

There are 40 dashes.. not 39

User avatar
emotional blind
A great helper
Posts: 383
Joined: Mon Oct 18, 2004 8:25 am
Location: Bangladesh
Contact:

Post by emotional blind » Wed Mar 15, 2006 7:33 am

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
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Post by Jan » Wed Mar 15, 2006 8:35 pm

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.
Ami ekhono shopno dekhi...
HomePage

User avatar
emotional blind
A great helper
Posts: 383
Joined: Mon Oct 18, 2004 8:25 am
Location: Bangladesh
Contact:

Post by emotional blind » Sat Mar 25, 2006 10:27 am

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
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Post by Jan » Sun Mar 26, 2006 7:01 pm

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.
Ami ekhono shopno dekhi...
HomePage

Post Reply

Return to “Volume 4 (400-499)”