## 10905 - Children's Game

Moderator: Board moderators

ferrizzi
New poster
Posts: 23
Joined: Thu Mar 30, 2006 5:42 pm
Location: Brazil
I solved this problem by using digit by digit comparison. I read the input using unsigned int format, and i wrote 3 functions:
1) one to get a digit at some position
2) one to compare 2 integers (this was the more dificult)
3) I used in the main function an array, that was sorted by insertion (read a number and insert it into the array)

Regards,
[]'s
Andre

arsalan_mousavian
Experienced poster
Posts: 111
Joined: Mon Jan 09, 2006 6:19 pm
Location: Tehran, Iran
Contact:
i've got WA again and again and my program passes all the io that is given in the board , i used DP to solve the problem

Code: Select all

``````#include <iostream>
#include <cstring>
#include <queue>
#include <memory>
#include <cstdlib>
#include <math.h>
using namespace std ;
char input [50][3000] ;
char result [1000000] ;
int order [50] ;
char t [1000000] ;
int N ;

bool generateString ()
{
t [0] = NULL ;
for ( int i=0 ; i<N ; i++ )
strcat ( t , input [order [i]] ) ;
if ( strcmp ( t , result ) == 1 ) // if the t is bigger
{
strcpy ( result , t ) ;
return true ;
}
return false ;

}
int main ()
{

while ( cin >> N && N )
{
cin.get () ;
result [0] = NULL;
long long X ;
for ( int i=0 ; i<N ; i++ )
{

while (  cin.peek () == '0' || cin.peek () == '\n' ) cin.get () ;
int j ;
for (  j=0 ; cin.peek () >= '0' && cin.peek ()<= '9' ; j++ )
input [i][j] = cin.get () ;
input [i][j] = NULL ;
cin.get ();
}
for ( int i=0 ; i<N ; i++ )
order [i] = i ;
generateString () ;
bool chg ;
chg = 0 ;
while ( 1 )
{
chg = 0 ;
for ( int i=0 ; i<N && !chg; i++ )
{
if ( i == ( N-1 ) ) goto Final ;
for ( int j=(i+1) ; j<N && !chg; j++ )
{
swap ( order [i] , order [j] ) ;
if ( !generateString () )// if less
swap ( order [i] , order [j] ) ;
else // if greater
chg = 1;

}
}
if ( !chg ) goto Final ;
}
Final :
int I ;
for ( I=0 ; I<strlen ( result ) && result [I] == 0 ; I++ ); // skip leading zeros
for ( ; I<strlen ( result ) ; I++ ) cout << result [I] ;
cout << endl ;
}

}

``````
any suggestions ?
thanks in Advance . . .
Arsalan
In being unlucky I have the record.

Martin Macko
A great helper
Posts: 481
Joined: Sun Jun 19, 2005 1:18 am
Location: European Union (Slovak Republic)
arsalan_mousavian wrote:i've got WA again and again and my program passes all the io that is given in the board , i used DP to solve the problem
Are you sure you got WA and not TLE? Because your program is rather too slow...

arsalan_mousavian
Experienced poster
Posts: 111
Joined: Mon Jan 09, 2006 6:19 pm
Location: Tehran, Iran
Contact:
yeah , i am getting WA under 1 sec
In being unlucky I have the record.

Martin Macko
A great helper
Posts: 481
Joined: Sun Jun 19, 2005 1:18 am
Location: European Union (Slovak Republic)
arsalan_mousavian wrote:yeah , i am getting WA under 1 sec
You write that your solution is using DP... but it's definitely not DP what you've posted here... your algorithm looks a litle bit strange and rather slow, but actually I've not found any counter example for it, yet...

Possibly, you could try to change
your code wrote:...if ( strcmp ( t , result ) == 1 ) // if the t is bigger
to
new code wrote:...if ( strcmp ( t , result ) > 0 ) // if the t is bigger
as man strcmp says
man strcmp wrote:The strcmp() and strncmp() functions return an integer less than, equal to, or greater than zero if s1 (or the first n bytes thereof) is found, respectively, to be less than, to match, or be greater than s2.

sakhassan
Experienced poster
Posts: 105
Joined: Sat Mar 11, 2006 9:42 am
Location: cse,DU

### 10905 - Children’s Game

I have tried all the possible input.... But still getting WA... I dont know what i have missed!!!!!!!!!!!!! pls help me
#include<stdio.h>
#include<string.h>

#define MAX 200

char str[MAX][80];

char res[MAX];

void sort(int count)
{

char temp[MAX];
char a[MAX];
char b[MAX];

int i,j,k,l;
int flag ;
int len1,len2;

for(i=0;i<count;i++)
{

for(j=count-1;j>i;j--)
{
len1 = strlen(str[j-1]);
len2 = strlen(str[j]);
strcpy(a,str[j-1]);
strcpy(b,str[j]);
//flag = 1;

if(len1==len2)
{
if(strcmp(str[j],str[j-1])>0)
{
strcpy(temp,str[j]);
strcpy(str[j],str[j-1]);
strcpy(str[j-1],temp);
}
}
else
{

if(len1>len2)
{
int len;
len = len1;
len1 = len2;
len2 = len;

strcpy(temp,a);
strcpy(a,b);
strcpy(b,temp);
strcpy(str[j-1],a);
strcpy(str[j],b);

}

flag = 0;
l=0;

while(l<len2)
{
if(flag==0)
{
for(k=0;k<len1 && l<len2;k++,l++)
{
if(a[k]==b[l])
continue;
else if(a[k]>b[l])
{
flag = 1;
break;
}
else
{
flag = 2;
break;
}
}

}
else
break;

}

if(flag==1)
{

}
else if(flag==2)
{
strcpy(temp,str[j]);
strcpy(str[j],str[j-1]);
strcpy(str[j-1],temp);

}
else
{

if(k<len1 && l>=len2)
{
k--;
for(l=0;k<len1&&l<len2;l++,k++)
{
if(a[k]<=b[l])
{
strcpy(temp,str[j-1]);
strcpy(str[j-1],str[j]);
strcpy(str[j],temp);
}
}
}
}
/*
else
{
while(l<len2)
{

for(k=0;k<len1;k++)
{
if(
}
l++;
}
}*/
/*
for(k=0;k<len1;k++)
{
for(l=0;l<len2;l++)
{
if(a[k]<b[l])
{
strcpy(temp,str[j]);
strcpy(str[j],str[j-1]);
strcpy(str[j-1],temp);
flag = 0;
break;
}
//else if(a[k]>b[l])
}

if(!flag)
break;
}*/
}
/*
else
{
for(k=0;k<len2;k++)
{
for(l=0;l<len1;l++)
{
if(a[k]<b[l])
{
strcpy(temp,str[j]);
strcpy(str[j],str[j-1]);
strcpy(str[j-1],temp);
flag = 0;
break;
}
}

if(!flag)
break;
}

}*/

}
}
}

int main()
{

int n;
int i;

while(1)
{
scanf("%d",&n);
if(n==0)
break;
for(i=0;i<n;i++)
scanf("%s",str);

sort(n);

//strcpy(res,"");
for(i=0;i<n;i++)
{
//strcat(res,str);
printf("%s",str);
}

printf("\n");
//printf("%s\n",res);

}

return 0;
}

Martin Macko
A great helper
Posts: 481
Joined: Sun Jun 19, 2005 1:18 am
Location: European Union (Slovak Republic)

### Re: WA WA on 10905

sakhassan wrote:I have tried all the possible input.... But still getting WA... I dont know what i have missed!!!!!!!!!!!!! pls help me

Code: Select all

``````2
47107575102712769936 68510897482010786149041631210810410110497141076106261021082276567248265259910827465
0``````

Code: Select all

``6851089748201078614904163121081041011049714107610626102108227656724826525991082746547107575102712769936``

Martin Macko
A great helper
Posts: 481
Joined: Sun Jun 19, 2005 1:18 am
Location: European Union (Slovak Republic)

### Re: WA WA on 10905

sakhassan wrote:I have tried all the possible input.... But still getting WA... I dont know what i have missed!!!!!!!!!!!!! pls help me
Btw, there is already a thread on this problem. If there is a thread on a particular problem, please, use it to post your question and do not create a new one. (see http://online-judge.uva.es/board/viewtopic.php?t=9498, http://online-judge.uva.es/board/viewtopic.php?t=9006 and http://online-judge.uva.es/board/viewtopic.php?t=8983)

sakhassan
Experienced poster
Posts: 105
Joined: Sat Mar 11, 2006 9:42 am
Location: cse,DU
thanks I have corrected the problem ... it was a silly mistake ... my array size was small.... my code works for all the input and output given in the thread..........But still I am getting WA................

sakhassan
Experienced poster
Posts: 105
Joined: Sat Mar 11, 2006 9:42 am
Location: cse,DU
#include<stdio.h>
#include<string.h>
#include<math.h>

#define MAX 150

char str[MAX][MAX];

int strcmpi(char a[MAX], char b[MAX])
{

int len,len1,len2;
int i;
char temp[MAX];

len1 = strlen(a);
len2 = strlen(b);

if(len1>len2)
len = len2;
else
len = len1;

for(i=0;i<len ;i++)
{
if(a<b)
return -1;
else if(a>b)
return 1;
}

if(abs(len1-len2)==1)
{
if(len1>len2)
{
if(a[len1-1]>b[0])
return 1;
else if(a[len1-1]<b[0])
return -1;
}
else
{

if(b[len2-1]>a[0])
return 1;
else if(b[len2-1]<a[0])
return -1;

}
}

else if(abs(len1-len2)>1)
{

if(len1>len2)
{

}

if(len1>len2)
{
strcpy(temp,&a[len1-len2]);
strcmpi(temp,b);
}
else
{
strcpy(temp,&b[len2-len1]);
strcmpi(a,temp);
}

}

return 0;

}

void sort(int count)
{

char temp[MAX];
int i,j;

for(i=0;i<count;i++)
{
for(j=count-1;j>i;j--)
{
if(strcmpi(str[j-1],str[j])<0)
{
strcpy(temp,str[j-1]);
strcpy(str[j-1],str[j]);
strcpy(str[j],temp);
}
}
}

}

int main()
{

int cases;
int i;

while(1)
{
scanf("%d",&cases);
if(cases==0)
break;
i=0;
memset(str,0,sizeof(str));
while(i<cases)
{

scanf("%s",str);
i++;
}

sort(cases);
for(i=0;i<cases;i++)
printf("%s",str);
printf("\n");

}
return 0;
}

sakhassan
Experienced poster
Posts: 105
Joined: Sat Mar 11, 2006 9:42 am
Location: cse,DU
I have modified my comparison function like this:
can any1 have any idea???
int strcmpi(char a[MAX], char b[MAX])
{

int i;
int len1,len2,len;
int flag;
char temp[MAX];

len1 = strlen(a);
len2 = strlen(b);

if(len1>len2)
len = len2;
else
len = len1;

flag = 0;

for(i=0;i<len;i++)
{
if(a>b)
{
flag = 1;
break;
//return 1;
}
else if(a<b)
{
flag = 2;
break;
//return -1;
}
else
continue;
}

if(!flag && len1!=len2)
{
if(len==len1)
{
strcpy(temp,&b[len]);
flag = strcmpi(a,temp);
}
else
{
strcpy(temp,&a[len]);
flag = strcmpi(temp,b);
}

}

//return_flag :

if(flag==1)
return 1;
else if(flag==2)
return -1;

return 0;

}

Martin Macko
A great helper
Posts: 481
Joined: Sun Jun 19, 2005 1:18 am
Location: European Union (Slovak Republic)
sakhassan wrote:I have modified my comparison function like this:
can any1 have any idea???
Your new solution (with the modified comparison function) does not work for:

Code: Select all

``````10
524247331010 7 10078 129043310 63915138 5 7106 10213109 2145 7626644593
0``````
My AC's output:

Code: Select all

``77626644593710663915138552424733101021451290433101021310910078``

jan_holmes
Experienced poster
Posts: 136
Joined: Fri Apr 15, 2005 3:47 pm
Location: Singapore
Contact:

### got WA...

I got WA with this code, I have checked all the testcases posted in the forum... please help and give me other testcases... thx...

Code: Select all

``````#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#include <math.h>
#include <string>
#include <iostream>

//WA...

using namespace std;

int max(int a,int b) {
return a>b?a:b;
}

typedef struct {
string si;
int len;
int idx;
} T;

T t[100];

int compare(const void *a,const void *b) {
T* x = (T*) a;
T* y = (T*) b;
int count1 = 0;
int count2 = 0;
int ll = max(x->len,y->len);
for (int i=0;i<ll;i++) {
if (count1 >= x->len) count1 = 0;
if (count2 >= y->len) count2 = 0;
int tmp1 = (x->si[count1])-'0';
int tmp2 = (y->si[count2])-'0';
if (tmp1 != tmp2) return y->si[count2] - x->si[count1];
count1++; count2++;
}
return x->len - y->len;
}

int cmp(const void *a,const void *b) {
T* x = (T*) a;
T* y = (T*) b;
int count1 = 0;
int count2 = 0;
int ll = max(x->len,y->len);
for (int i=0;i<ll;i++) {
if (count1 >= x->len) count1 = 0;
if (count2 >= y->len) count2 = 0;
int tmp1 = (x->si[count1])-'0';
int tmp2 = (y->si[count2])-'0';
if (tmp1 != tmp2) return y->si[count2] - x->si[count1];
count1++; count2++;
}
return y->len - x->len;
}

int main () {
int n,tt;
int count = 0;
char s[10000];
char *tokenptr;
string ret1 = "";
string ret2 = "";
while (scanf("%d",&n) != EOF) {
ret1 = "";
ret2 = "";
count = 0;
if (!n) return 0;
for(int i=0;i<n;i++) {
scanf("%s",s);
//sprintf(s,"%d",tt);
t[count].si = s;
t[count].len = strlen(s);
count++;
}
/*tokenptr = strtok(s," ");
while (tokenptr != NULL) {
//t[count].idx = count;
//strcpy(t[count].si,tokenptr);
t[count].si = tokenptr;
t[count].len = strlen(tokenptr);
count++;
tokenptr = strtok(NULL," ");
}*/
int temp = 0;
temp=count+1;
qsort(t,temp,sizeof(T),compare);
for (int i=0;i<temp;i++) {
ret1+=t[i].si;
}
qsort(t,temp,sizeof(T),cmp);
for (int i=0;i<temp;i++) {
ret2+=t[i].si;
}
if (ret1 > ret2) cout << ret1;
else cout << ret2;
printf("\n");
//cout << ret1 << "\n" << ret2;
//printf("\n");*/
//cout << ret1 << "\n";
for (int i=0;i<temp;i++) {
t[i].si = "";
}
}
return 0;
}

``````

tan_Yui
Experienced poster
Posts: 155
Joined: Sat Jul 10, 2004 12:41 am

### Re: got WA...

Hi, jan_holmes.
Your code was failed in the following case.

Code: Select all

``````5
1 120 1201 12012 120120
5
7 768 7687 76876 768768
0
``````
Correct output is :

Code: Select all

``````1201212012012012011
7768776876876876876
``````
Best regards.

jan_holmes
Experienced poster
Posts: 136
Joined: Fri Apr 15, 2005 3:47 pm
Location: Singapore
Contact:
thanks tan_Yui, I'll try to fix my code...