10905 - Children's Game

[ferrizzi]

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)

[arsalan_mousavian]

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

[Martin Macko]

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]

yeah , i am getting WA under 1 sec

[Martin Macko]

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

...if ( strcmp ( t , result ) == 1 ) // if the t is bigger

to

...if ( strcmp ( t , result ) > 0 ) // if the t is bigger

as man strcmp says

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]

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]

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

Your solution's not working for

Code: Select all

2
47107575102712769936 68510897482010786149041631210810410110497141076106261021082276567248265259910827465
0

Correct answer is:

Code: Select all

6851089748201078614904163121081041011049714107610626102108227656724826525991082746547107575102712769936

[Martin Macko]

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]

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]

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

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]

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]

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]

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]

thanks tan_Yui, I'll try to fix my code...