10905 - Children's Game

[ayon]

it's not clear to me what would be the output if input integers contains leading zeros. what should be the answer for the following inputs:

Code: Select all

1
00009
2
00009 90000

[sohel]

output 1: 00009
output 2: 9000000009

[ayon]

he he, sohel vai, your output is wrong, if you print "output 1:", "output 2:", you will get wrong answer

[sohel]

[voix]

Hi,

I got AC but it was rejudged WA (time ago). I use the method of 'clever sorting' using

s1++s2 > s2++s1

as order function and using the sort function 'sort' from the C++ STL. Is this a valid method? I'm quite sure, but... I'm still getting WA. I've read all the others threads about this problem and my algorithm gives the correct output for all the inputs posted.

I don't know what to do... is the method of 'clever sorting' ok? Can anybody post tricky test cases that show the 'clever sorting' is wrong?


thanks in advance

[lovemagic]

can anyone tell me why my code gets WA?

Code: Select all

AC 

[rushel]

i think a simple bubble sort will do. i just have to take decisions between two strings which on should come before.

e.g: 1234 12349

string1: 123412349
string2: 123491234
so string2 should come before string1

[hamedv]

whit bubble sort you get TLE.
you can use qsort()

[lovemagic]

a simple bubble sort will do as N (≤ 50).

[cytmike]

Anybody now has the idea how transitivity works?
I got AC using david's method, but I really want a proof of that.

[Saul Hidalgo]

Hi! I read all the post about this problem. All the input match. And i have WA .

Here is my code:

Code: Select all

#include <iostream>
#include <string>
#include <vector>
using namespace std;
int main(){
	int taman;
	bool entro=false;
	while ((cin >> taman) && taman!=0){
		if (entro) cout << endl;
		entro=true;
		vector<string> numeros;
		string temp;
		for (int tama=0; tama<taman ; tama++){
			cin >> temp;
			numeros.push_back(temp);
		}
		while(numeros.size()>0){
			int pos=0;
			for (int i=0; i<numeros.size() ; i++){
				bool listo=false;
				int elmaspeque=numeros[pos].size();
				if (elmaspeque>numeros[i].size()) elmaspeque=numeros[i].size();
				for (int j=0; (j<numeros[i].size() || j<numeros[pos].size()) && !listo; j++){
					if (numeros[i][j%(numeros[i].size())]>numeros[pos][j%(numeros[pos].size())]){
						listo=true;
						pos=i;
					}
					else if (numeros[i][j%(numeros[i].size())]<numeros[pos][j%(numeros[pos].size())]){
						listo=true;
					}
				}

				if (!listo && numeros[i]!=numeros[pos]){
					if (numeros[i]+numeros[pos]>numeros[pos]+numeros[i]){
						pos=i;
					}
				}
			}
			cout << numeros[pos];
			numeros.erase(numeros.begin() + pos , numeros.begin() + pos +1);
			pos=0;
		}
		numeros.clear();
	}
	return 0;
}

Thanks for all.

[lucky16g]

i have try it very times
and got WA
i finally find it
in compare we cant use atoi() or atof()
becourse the lenth is too long
when i try to compare one char by one char
i got ac
hope this will help the one who got wa

[naffi]

I need help.

Code: Select all

#include<iostream>

using namespace std;
char arr[9000][9000],tmp[9000];
bool comp_function(int i,int j)
{
	int il = strlen(arr[i]);		
	int jl = strlen(arr[j]);
	if(jl >= il)
	{
		for(int x = 0, y = 0; y < jl; y++, x = (++x)%il)
		{
			if(arr[i][x] > arr[j][y])return true;			
			else if(arr[i][x] < arr[j][y])return false;
		}
		return true;
	}
	else
	{
		for(int x = 0, y = 0; x < il; x++, y = (++y)%jl)
		{
			if(arr[i][x] > arr[j][y])return true;			
			else if(arr[i][x] < arr[j][y])return false;
		}
		return true;
	}
}

main()
{
#ifndef ONLINE_JUDGE
	freopen("input.txt","r",stdin);	
	freopen("output.txt","w",stdout);
#endif
	int N,i;
	while(scanf("%d",&N) && N)
	{
		i = 0;
		while(N--)
		{
			scanf("%s",arr[i++]);			
		}
		for(int s = 1; s < i; ++s)//Bubble sort in Teach Yourself by Herb. Sch.
		{
			for(int t = i-1; t >= s; --t)
			{
				if(!comp_function(t-1,t))
				{
					strcpy(tmp,arr[t-1]);
					strcpy(arr[t-1],arr[t]);
					strcpy(arr[t],tmp);					
				}
			}
		}
		
		for(int j = 0; j < i; j++)cout<<arr[j];
		cout<<endl; 		
	}
}

[mukit]

i'm getting WA in this problem. please give some critical input-output or suggestion.

Code: Select all

ok AC after changing array size 

[Shafaet_du]

See the algorithm described by DAVID in 1st page,that will help you. and try this:

Code: Select all

2
1231231232 123 
0

output:

Code: Select all

1231231232123

you can use bubble sort,it wont give tle.