10905 - Children's Game

[DD]

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; 		
	}
}

I think your sorting is wrong since you should compare the two concatenations of two strings, say (a + b) and (b + a).

[Imti]

//Got Acc

[Garfield]

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.

Got it clearly, thnx for providing help. Like you, cell phone spy software guys, work here.

[Scarecrow]

getting TLE. someone can help me plz?

Code: Select all

AC

[Shihab]

Ac

[Frez]

good CMP function :

Code: Select all

bool CMP(string a,string b)
{
	return (a+b<b+a);
}

use it for sort function !

[mgavin2]

This problem is horribly written and doesn't include bounds on the input.

Read and process everything as strings.
The problem might talk about everything being integers, such as

In next lines there are N positive integers.

So you read and process items as int32s, then int64s...
But the problem never says the integers can't have a leading 0! LOL TRICKED YOU!

TRICKY TEST CASE:

2
01 10
0

1001

Perhaps if we keep instilling the fear of reading numbers as strings because you can't be sure that the numbers will actually be numbers even if you're told they're numbers, then every future DBA will stringize their whole database.