10420 - List of Conquests

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

Moderator: Board moderators

RuiFerreira
New poster
Posts: 23
Joined: Mon Dec 16, 2002 8:01 pm
Location: Portugal
Contact:

10420 - List of Conquests

Post by RuiFerreira » Sat Jan 18, 2003 3:13 am

hi!
I keep geting WA in this problem...
I've got some questions..

should i count 2 womans with the same name, in the same country??

what about case? shuoud a country with difrent caps be considered a difrent country?

thanks!
Please visit my webpage!! I've got a lot of UVA statistics scripts
http://www.fe.up.pt/~ei01081/scripts/

Andrey Mokhov
Experienced poster
Posts: 128
Joined: Fri Nov 15, 2002 7:45 am
Location: Kyrgyzstan

Post by Andrey Mokhov » Sat Jan 18, 2003 6:25 am

There is no trick in the problem. I solved it straight forward and got AC in an only submission. Here are the answers for your questions:

1. You should count all the women. In fact I even don't read their names. :) Just count'em.

2. Nothing special with capitals. Use strcmp().

Good luck!
Andrey.

User avatar
yahoo
Learning poster
Posts: 93
Joined: Tue Apr 23, 2002 9:55 am

Post by yahoo » Wed Jan 22, 2003 12:33 am

Mokhov i have done just what you say but i can't understand why i got wrong answer. Will anybody kindly see my code and tell me where i am wrong or give me some input to check my code. Here is my code:

Code: Select all

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

main()
{
	char a[1000],b[1000],con[50][80],con1[50][80],tmp[10000];
	int r,i,j,k,m,z,n,num[5000],temp,flag;
	char *st;
	while(1)
	{
		if(gets(a)==NULL) break;
		n=atoi(a);

		for(i=0;i<n;i++)
		{
			gets(b);
			st=strtok(b," ");
			strcpy(con[i],st);
		}
		for(i=0;i<5000;i++)
			num[i]=1;
		z=0;flag=0;

		for(i=0;i<n;i++)
		{
			flag=0;
			for(j=i+1;j<=n;j++)
			{
				if(strcmp(con[i],con[j])==0 && strcmp(con[i],"1")!=0 && strcmp(con[j],"1")!=0)
				{
					num[z-1]++;
					strcpy(con[j],"1");
				}
				else if(flag==0  && strcmp(con[i],"1")!=0 && strcmp(con[j],"1")!=0)
					{
						flag=1;
						strcpy(con1[z++],con[i]);
					}
			}
		}

		for(j=0;j<z-1;j++)
			for(k=j+1;k<z;k++)
			{
				if(strcmp(con1[j],con1[k])>0)
				{
					strcpy(tmp,con1[j]);
					strcpy(con1[j],con1[k]);
					strcpy(con1[k],tmp);
					temp=num[j];
					num[j]=num[k];
					num[k]=temp;
				}
			}
			for(i=0;i<z;i++)
				printf("%s %d\n",con1[i],num[i]);
	}
	return 0;
}
[c] :oops: :oops: :oops: [/c]

turuthok
Experienced poster
Posts: 193
Joined: Thu Sep 19, 2002 6:39 am
Location: Indonesia
Contact:

Post by turuthok » Wed Jan 22, 2003 10:20 pm

Hello, ... first of all ... n could be up to 2000 ... I see you declared con[] to have only 50 elements there ... you will have problem strcpy-ing n items to con[].

And also, if you declare lots of bytes as you did in the beginning of your main() function, ... it would be advisable to get them all outside the function or declared them as static since we don't know how big our stack is ...

-turuthok-

User avatar
yahoo
Learning poster
Posts: 93
Joined: Tue Apr 23, 2002 9:55 am

Post by yahoo » Wed Jan 22, 2003 11:09 pm

Thank you for your reply. My problem i think is not with array size. Because when i submit i increase the array size. Here is the size that i use in my pc. After hear from you i again change my array size. But still got wrong answer. I can't understand where i am wrong. Will anyone kindly again see my code and told me where i am wrong or can give me some test inputs. Here is my corrected code:

Code: Select all

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

main()
{
  char a[1000],b[1000],con[3000][80],con1[3000][80],tmp[10000];
  int r,i,j,k,m,z,n,num[5000],temp,flag;
  char *st;
  while(1)
  {
    if(gets(a)==NULL) break;
    n=atoi(a);

    for(i=0;i<n;i++)
    {
      gets(b);
      st=strtok(b," ");
      strcpy(con[i],st);
    }
    for(i=0;i<5000;i++)
      num[i]=1;
    z=0;flag=0;

    for(i=0;i<n;i++)
    {
      flag=0;
      for(j=i+1;j<=n;j++)
      {
        if(strcmp(con[i],con[j])==0 && strcmp(con[i],"1")!=0 && strcmp(con[j],"1")!=0)
        {
          num[z-1]++;
          strcpy(con[j],"1");
        }
        else if(flag==0 && strcmp(con[i],"1")!=0 && strcmp(con[j],"1")!=0)
          {
            flag=1;
            strcpy(con1[z++],con[i]);
          }
      }
    }

    for(j=0;j<z-1;j++)
      for(k=j+1;k<z;k++)
      {
        if(strcmp(con1[j],con1[k])>0)
        {
          strcpy(tmp,con1[j]);
          strcpy(con1[j],con1[k]);
          strcpy(con1[k],tmp);
          temp=num[j];
          num[j]=num[k];
          num[k]=temp;
        }
      }
      for(i=0;i<z;i++)
        printf("%s %d\n",con1[i],num[i]);
  }
  return 0;
} 

Dominik Michniewski
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:

Post by Dominik Michniewski » Thu Jan 23, 2003 8:55 am

try to use list or vector from C++. Code is more readable and shorter :))

I solve his question using lists ... for names of country I use 100 char buffer (for each) and line of input has no more then 400 characters ;-) because in other way I've got RTE ;-)

Regards
Dominik Michniewski

turuthok
Experienced poster
Posts: 193
Joined: Thu Sep 19, 2002 6:39 am
Location: Indonesia
Contact:

Post by turuthok » Thu Jan 23, 2003 12:03 pm

Try this simple test:

=================
2
a john
a doe
=================

I'm sure your code will return "a 1" ... I don't know how you used your num[] array ... but the first index (z) is set to zero ... and when the 1st two elements are the same ... you have a (z-1) which is not a valid index.

Other than that, ... I see you use too many strcmp() ... in the real contest, the time limit is 2 seconds ... If you use strcmp() inefficiently, you could run into TLE later on ... remember that n could be up to 2000.

Last time in the contest I had a structure that contains 2 fields, the country name and the count. I was too afraid it's going to timeout if I just do linear-search, so I used some kind of hash tables for each entry.

-turuthok-

anupam
A great helper
Posts: 405
Joined: Wed Aug 28, 2002 6:45 pm
Contact:

Post by anupam » Fri Jan 24, 2003 2:08 pm

i have no such prob but it gives wa.
i just count the name of the country not the name of women :oops: :oops:
"Everything should be made simple, but not always simpler"

User avatar
Sarmento
New poster
Posts: 15
Joined: Tue Apr 22, 2003 9:50 pm
Location: Lisboa, Portugal

10420 - List of Conquests

Post by Sarmento » Wed Nov 26, 2003 10:18 pm

Why do I keep getting WA?

Thanks

Code: Select all

[c]
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int comp_chars(char * char1, char * char2){
	int ret = strcmp(char1,char2);
  	if (ret < 0)
  		ret = -1;
  	else if (ret > 0)
  		ret = 1;
  	return ret;
}

int main(){
	int n, i, j;
	char a [80], b[80];
	char s [2001][80];
	scanf("%d", &n);
	for(i=0; i < n ; i++){
		scanf("%s %s %s", s[i], a, b);
	}
	qsort(s,n,sizeof(char)*80,(void *)comp_chars);
	for(i=0; i < n; i++){
		printf("%s ", s[i]);
		for(j=i; strcmp(s[i],s[j]) == 0 && j < n; j++){
		}
		printf("%d\n", j - i);
		i = j-1;
	}
	return 0;	
}
[/c]
-----------------
Jo

User avatar
Sarmento
New poster
Posts: 15
Joined: Tue Apr 22, 2003 9:50 pm
Location: Lisboa, Portugal

Post by Sarmento » Fri Nov 28, 2003 1:14 am

Already solved it. I hadn't noticed that the women could have more than two names... Silly me...

Thanks

joao
-----------------
Jo

User avatar
Ghust_omega
Experienced poster
Posts: 115
Joined: Tue Apr 06, 2004 7:04 pm
Location: Venezuela

10420

Post by Ghust_omega » Mon Sep 06, 2004 2:27 pm

I hate problems like this too easy and always keep WA :evil: ,anyway I count the number of a country apears I ignore the names, Here some I/O this is good??? :-?

Input:
[c]
15
Spain Donna Elvira
England Jane Doe
Spain Donna Anna
Venezuela afdas safdsf asfsafa safsdf
Alemania sevet safads
Alemania adfsadfs sdfdsfads
Austrai asdfsadffregtgwrt grddf fdgfd
a jhon
a Doe
England Madonna Lill
England woman1
Austria woman2
Venezuela Maria perez
Colombia Nohelia beta
Argentina woman2
[/c]

Ouput:
[c]
Alemania 2
Argentina 1
Austrai 1
Austria 1
Colombia 1
England 3
Spain 2
Venezuela 2
a 2
[/c]

give me some I/O or hint please help me

Dominik Michniewski
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:

Post by Dominik Michniewski » Tue Sep 07, 2004 12:05 am

you must have bug in your code. My accepted solution outputs the same results.

Best regards
DM
If you really want to get Accepted, try to think about possible, and after that - about impossible ... and you'll get, what you want ....
Born from ashes - restarting counter of problems (800+ solved problems)

User avatar
Ghust_omega
Experienced poster
Posts: 115
Joined: Tue Apr 06, 2004 7:04 pm
Location: Venezuela

Post by Ghust_omega » Wed Sep 08, 2004 12:36 pm

Thanks Dominik for you reply, here is my source code
someone that help me why WA please :(
[c]
#include <stdio.h>
#include <string.h>

int main(){
char c[2100][80];
int a[80]={0};
char s[80];
int n,n1=0,i,j,aux2,menor,bool=1;
char *t1;

/*freopen("10420.in","r",stdin);
freopen("10402.out","w",stdout); */

/*Take the number of case*/
scanf("%d\n",&n);
while(n--){
bool=1;
gets(s);
t1 = strtok(s," ");

for(i=0;i<n1;i++)
if(strcmp(c,t1) == 0){
bool=0;
a++;
break;
}
if(bool){
a[n1]=1;
strcpy(c[n1++],t1);
}
}
/*Sort the array in order alfabetic this algorithm is the selection*/
for(i=0;i<n1-1;i++){
for(j=i+1,menor=i;j<n1;j++)
if(strcmp(c[j],c[menor])==-1)
menor=j;
strcpy(t1,c);
aux2=a;
strcpy(c,c[menor]);
a=a[menor];
strcpy(c[menor],t1);
a[menor] = aux2;
}
for(i=0;i<n1;i++)
printf("%s %d\n",c,a);

return 0;
} [/c]
Thanks in advance
Keep posting!!

Dominik Michniewski
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:

Post by Dominik Michniewski » Wed Sep 08, 2004 1:41 pm

I can't test it, but I thunk that problem is here:

Code: Select all

         
if(strcmp(c[j],c[menor])==-1) 
            menor=j; 
strcmp() returns to you (like read in documentation) negative value, but not always -1
see printf("%d",strcmp("a","z"));

Best regards
DM
If you really want to get Accepted, try to think about possible, and after that - about impossible ... and you'll get, what you want ....
Born from ashes - restarting counter of problems (800+ solved problems)

User avatar
Ghust_omega
Experienced poster
Posts: 115
Joined: Tue Apr 06, 2004 7:04 pm
Location: Venezuela

Post by Ghust_omega » Thu Sep 09, 2004 9:38 am

thanks!! Domnik for you reply and your tip about strcmp i change that part of mi code by this

Code: Select all

if(strcmp(c[j],c[menor]) < 0)
            menor=j; 
and still WA :cry: and printf("%d",strcmp("a","z")) 0 = -1 what can be the cause of WA :( please help me
Thanks in advance
Keep posting!!

Post Reply

Return to “Volume 104 (10400-10499)”