10905 - Children's Game

All about problems in Volume 109. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

ayon
Experienced poster
Posts: 161
Joined: Tue Oct 25, 2005 8:38 pm
Location: buet, dhaka, bangladesh

Post by ayon » Tue Nov 14, 2006 4:59 pm

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
ishtiak zaman
----------------
the world is nothing but a good program, and we are all some instances of the program

User avatar
sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York

Post by sohel » Thu Nov 16, 2006 12:14 pm


output 1: 00009
output 2: 9000000009

ayon
Experienced poster
Posts: 161
Joined: Tue Oct 25, 2005 8:38 pm
Location: buet, dhaka, bangladesh

Post by ayon » Thu Nov 16, 2006 3:39 pm

he he, sohel vai, your output is wrong, if you print "output 1:", "output 2:", you will get wrong answer :wink:
ishtiak zaman
----------------
the world is nothing but a good program, and we are all some instances of the program

User avatar
sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York

Post by sohel » Thu Nov 16, 2006 11:53 pm

:)

voix
New poster
Posts: 1
Joined: Sat Dec 02, 2006 12:42 pm

10905 Help needed

Post by voix » Sat Dec 02, 2006 12:57 pm

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
Learning poster
Posts: 52
Joined: Thu Oct 02, 2003 11:38 am

Post by lovemagic » Mon Jun 18, 2007 1:12 am

can anyone tell me why my code gets WA?

Code: Select all


AC 

:D
khobaib

rushel
Learning poster
Posts: 67
Joined: Sat Jan 22, 2005 5:57 am

Post by rushel » Mon Jun 18, 2007 11:43 pm

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
Learning poster
Posts: 98
Joined: Mon May 07, 2007 8:30 am

Post by hamedv » Tue Jun 19, 2007 5:27 am

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

lovemagic
Learning poster
Posts: 52
Joined: Thu Oct 02, 2003 11:38 am

Post by lovemagic » Wed Jun 20, 2007 1:29 am

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

User avatar
cytmike
Learning poster
Posts: 95
Joined: Mon Apr 26, 2004 1:23 pm
Location: Hong Kong and United States
Contact:

Post by cytmike » Sat Dec 29, 2007 1:39 pm

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

Saul Hidalgo
New poster
Posts: 18
Joined: Wed Jan 03, 2007 2:36 am
Location: Los Teques, Venezuela

I'm having WA

Post by Saul Hidalgo » Sun Jan 27, 2008 8:46 am

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

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. :wink:

lucky16g
New poster
Posts: 8
Joined: Sun Jul 01, 2007 7:25 pm

Post by lucky16g » Wed Mar 26, 2008 11:22 am

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
New poster
Posts: 23
Joined: Wed Mar 19, 2008 12:25 pm
Location: BUET, Bangladesh
Contact:

10905 - Children’s Game - WA

Post by naffi » Thu Sep 25, 2008 4:23 am

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; 		
	}
}
Always At Your Help.

mukit
New poster
Posts: 48
Joined: Wed Nov 21, 2007 10:09 am
Location: Dhaka , Bangladesh
Contact:

Re: 10905 - Children’s Game

Post by mukit » Tue Dec 16, 2008 8:29 pm

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

Code: Select all

ok AC after changing array size 
:wink:

Shafaet_du
Experienced poster
Posts: 147
Joined: Mon Jun 07, 2010 11:43 am
Location: University Of Dhaka,Bangladesh
Contact:

Re: 10905 - Children’s Game

Post by Shafaet_du » Sun Oct 24, 2010 3:34 pm

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.

Post Reply

Return to “Volume 109 (10900-10999)”