10420 - List of Conquests

[RuiFerreira]

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!

[Andrey Mokhov]

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.

[yahoo]

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] [/c]

[turuthok]

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-

[yahoo]

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]

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]

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]

i have no such prob but it gives wa.
i just count the name of the country not the name of women

[Sarmento]

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]

[Sarmento]

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

Thanks

joao

[Ghust_omega]

I hate problems like this too easy and always keep WA ,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]

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

Best regards
DM

[Ghust_omega]

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]

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

[Ghust_omega]

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 and printf("%d",strcmp("a","z")) 0 = -1 what can be the cause of WA please help me
Thanks in advance
Keep posting!!