Page 1 of 3

### 10164 - Number Game

Posted: 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 ### 10164

Posted: Wed Jan 08, 2003 7:15 am

### 10164

Posted: 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!!!!!!!

Posted: Wed Feb 05, 2003 11:15 am
Oh, Finally i got it.

Thanks.

Posted: 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

### 10164 - number game

Posted: 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?

Posted: Mon Aug 18, 2003 1:54 pm
never mind... got AC now... thank you

Posted: 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??

### ACCCCCCCC

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

Posted: 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?

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

### Yes, let's discuss it!

Posted: 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?

Posted: Tue May 02, 2006 9:17 pm
I used DP for this problem.
But getting TLE 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[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[N]<t)&&(i<n));i++)memo(x[i],N);
}

void dispaly(type sum,type n,type N)
{
if(n==1){ printf("%d",track[sum]); 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[N]<t)printf("No\n");
else { printf("Yes\n"); dispaly(0,N,N); }
printf("\n"); t++;
}

``````

Posted: Sun May 07, 2006 9:11 am
Hi Mr. ALU !

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!

Posted: Sat Sep 23, 2006 5:08 am
Could anybody explain me why backtracking can possibly work for this problem?