Page **1** of **3**

### 10164 - Number Game

Posted: **Thu Dec 12, 2002 7:58 am**

by **Red Scorpion**

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**

by **Red Scorpion**

Please Help me ......

### 10164

Posted: **Tue Jan 28, 2003 10:57 am**

by **newhh2002**

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**

by **Red Scorpion**

Oh, Finally i got it.

Thanks.

Posted: **Wed Feb 05, 2003 11:23 am**

by **Red Scorpion**

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**

by **titid_gede**

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**

by **titid_gede**

never mind... got AC now... thank you

Posted: **Mon Aug 01, 2005 5:33 pm**

by **I LIKE GN**

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**

by **I LIKE GN**

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**

by **Moha**

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?

### 10164 want your help

Posted: **Mon Apr 17, 2006 5:09 pm**

by **Wei-Ming Chen**

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**

by **serur**

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?

### Please help

Posted: **Tue May 02, 2006 9:17 pm**

by **TISARKER**

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[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++;
}
```

Posted: **Sun May 07, 2006 9:11 am**

by **serur**

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**

by **minskcity**

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