10164 - Number Game

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

Moderator: Board moderators

Red Scorpion
Experienced poster
Posts: 192
Joined: Sat Nov 30, 2002 5:14 am

10164 - Number Game

Post by Red Scorpion » Thu Dec 12, 2002 7:58 am

Hi,

I have try to solve this problem with generate all the combination that possible (Recursive),
but i still get WA!

Can anyone tell me the other method ?

regards,
Red Scorpion 8)

Red Scorpion
Experienced poster
Posts: 192
Joined: Sat Nov 30, 2002 5:14 am

10164

Post by Red Scorpion » Wed Jan 08, 2003 7:15 am

Please Help me ......

newhh2002
New poster
Posts: 11
Joined: Sun Jan 26, 2003 4:25 pm
Contact:

10164

Post by newhh2002 » Tue Jan 28, 2003 10:57 am

would you help me about the algorithm of #10164? it might be a easy problem, but i don't know how to solve it. (my method use much memory and results in "tle" :( i wonder how those guys on the ranklist did it) thanks!!!!!!!
none

Red Scorpion
Experienced poster
Posts: 192
Joined: Sat Nov 30, 2002 5:14 am

Post by Red Scorpion » Wed Feb 05, 2003 11:15 am

Oh, Finally i got it.

Thanks.

Red Scorpion
Experienced poster
Posts: 192
Joined: Sat Nov 30, 2002 5:14 am

Post by Red Scorpion » Wed Feb 05, 2003 11:23 am

Hai ..

You just need to get a combination of number and print it.
I Use recurence, and get it in less then 1S.

Good Luck,
Red Scorpion

titid_gede
Experienced poster
Posts: 187
Joined: Wed Dec 11, 2002 2:03 pm
Location: Mount Papandayan, Garut

10164 - number game

Post by titid_gede » Mon Aug 18, 2003 1:39 pm

this problem looks easy, but i always got WA ... what is the tricky input here? if answer is Yes what we have to output, the number or the index of the number?
Kalo mau kaya, buat apa sekolah?

titid_gede
Experienced poster
Posts: 187
Joined: Wed Dec 11, 2002 2:03 pm
Location: Mount Papandayan, Garut

Post by titid_gede » Mon Aug 18, 2003 1:54 pm

never mind... got AC now... thank you
Kalo mau kaya, buat apa sekolah?

I LIKE GN
Learning poster
Posts: 57
Joined: Fri Oct 10, 2003 11:01 pm
Location: in front of PC
Contact:

Post by I LIKE GN » Mon Aug 01, 2005 5:33 pm

we to consider up to 2N-1(2*2^10-1 = 2*1024-1 = 2047) numbers
of which to choose 1000 numbers...
a terrific backtrack would get TL...
how urs is so fast!!!!!
m'i missing something??
There are two tragedies in life one is to lose your hearts' desire and another is to gain it --- GBS.

I LIKE GN
Learning poster
Posts: 57
Joined: Fri Oct 10, 2003 11:01 pm
Location: in front of PC
Contact:

ACCCCCCCC

Post by I LIKE GN » Fri Sep 16, 2005 5:43 pm

I LIKE GN wrote: a terrific backtrack would get TL...
No "a terrific backtrack" would NEVER get TL...
but a very simple "search all possibility" recursion now solves the problem
in 0.035 sec
also it needs MEMOIZATION( and MOD operation to help MEMO...)
thanks to all of uuuuu.
There are two tragedies in life one is to lose your hearts' desire and another is to gain it --- GBS.

Moha
Experienced poster
Posts: 216
Joined: Tue Aug 31, 2004 1:02 am
Location: Tehran
Contact:

Post by Moha » Wed Mar 22, 2006 11:04 pm

I have written a DP code for it. But I got TLE. Can anybody help me. Is there any faster algorithm that DP exists for this problem?

Wei-Ming Chen
Experienced poster
Posts: 122
Joined: Sun Nov 13, 2005 10:25 am
Location: Taiwan

10164 want your help

Post by Wei-Ming Chen » Mon Apr 17, 2006 5:09 pm

I got WA on this problem, can someone give me some strict I/O?
Thanks very much... :-?

By the way, I don't know when "No" happened...
Can someone tell me? Or the answer is always "Yes"? Thanks..

serur
A great helper
Posts: 251
Joined: Thu Feb 23, 2006 11:30 pm

Yes, let's discuss it!

Post by serur » Wed Apr 26, 2006 11:12 am

Hello fellows!

10164- "Number Game".
Has this:
N=2^k, k=1,2,3,4,5,6,7,8,9,10

some mysterious meaning? Has it something to do with bits=>binary representation of sets and so on? Has it any crucial meaning at all?
Last edited by serur on Sat Apr 14, 2012 3:34 pm, edited 1 time in total.

TISARKER
Learning poster
Posts: 88
Joined: Tue Oct 12, 2004 6:45 pm
Location: Bangladesh
Contact:

Please help

Post by TISARKER » Tue May 02, 2006 9:17 pm

I used DP for this problem.
But getting TLE :evil:
Can any one tell me why am i getting TLE?
Either check my code or give me prunning idea please :(

Code: Select all

#include<stdio.h>
//#include<math.h>
//#include<string.h>
#define range 1100005
#define drange 2100
#define crange 1100
#define type int

type sum[range],item[range],Total,x[drange],track[crange][crange];

type status[crange][crange],t=1;

void memo(type val,type N)
{
type k,i,j,count=Total;
for(k=0;k<Total;k++)
	{
	i=val+sum[k]; i%=N; j=item[k]+1; if(j>N)continue;
	if(status[i][j]==t)continue;
	status[i][j]=t; track[i][j]=val; if(status[0][N]==t)return;
	sum[count]=i; item[count]=j; count++;
	}
Total=count; i=val%N; j=1; if(status[i][j]==t)return ;
status[i][j]=t; track[i][j]=val; sum[Total]=i; item[Total]=j; Total++;
}

void input(type n,type N)
{
type i,j; for(i=0;i<n;i++)scanf("%d",&x[i]); Total=0;
for(i=0;((status[0][N]<t)&&(i<n));i++)memo(x[i],N);
}

void dispaly(type sum,type n,type N)
{
if(n==1){ printf("%d",track[sum][1]); return; }
type val; val=track[sum][n]; sum-=(val%N);
if(sum<0)sum+=N;
dispaly(sum,n-1,N);
printf(" %d",val);
}

void main()
{
type n,N;
//clrscr();
//freopen("E:\\input.cpp","r",stdin);
//freopen("E:\\myput.cpp","w",stdout);
while(scanf("%d",&N)==1)
	{
	if(N==0)break; n=2*N-1; input(n,N);
	if(status[0][N]<t)printf("No\n");
	else { printf("Yes\n"); dispaly(0,N,N); }
	printf("\n"); t++;
	}

Mr. Arithmetic logic Unit

serur
A great helper
Posts: 251
Joined: Thu Feb 23, 2006 11:30 pm

Post by serur » Sun May 07, 2006 9:11 am

Hi Mr. ALU :D !

Ignore my message above - divested of everything it turned out to be easy backtracking problem, and I was disappointed. How you can use DP - only to do mod N, eh?

Good luck!

minskcity
Experienced poster
Posts: 199
Joined: Tue May 14, 2002 10:23 am
Location: Vancouver

Post by minskcity » Sat Sep 23, 2006 5:08 am

Could anybody explain me why backtracking can possibly work for this problem?

Post Reply

Return to “Volume 101 (10100-10199)”