10420 - List of Conquests

Moderator: Board moderators

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

10420 - List of Conquests

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
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
Learning poster
Posts: 93
Joined: Tue Apr 23, 2002 9:55 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] [/c]

turuthok
Experienced poster
Posts: 193
Joined: Thu Sep 19, 2002 6:39 am
Location: Indonesia
Contact:
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
Learning poster
Posts: 93
Joined: Tue Apr 23, 2002 9:55 am
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:
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:
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:
i have no such prob but it gives wa.
i just count the name of the country not the name of women
"Everything should be made simple, but not always simpler"

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

10420 - List of Conquests

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

Sarmento
New poster
Posts: 15
Joined: Tue Apr 22, 2003 9:50 pm
Location: Lisboa, Portugal
Already solved it. I hadn't noticed that the women could have more than two names... Silly me...

Thanks

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

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

10420

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
a jhon
a Doe
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]

Dominik Michniewski
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:
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)

Ghust_omega
Experienced poster
Posts: 115
Joined: Tue Apr 06, 2004 7:04 pm
Location: Venezuela
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]
Keep posting!!

Dominik Michniewski
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:
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)

Ghust_omega
Experienced poster
Posts: 115
Joined: Tue Apr 06, 2004 7:04 pm
Location: Venezuela
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