## 10164 - Number Game

Moderator: Board moderators

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

### 10164 - Number Game

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

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

### 10164

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

### 10164

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
Oh, Finally i got it.

Thanks.

Red Scorpion
Experienced poster
Posts: 192
Joined: Sat Nov 30, 2002 5:14 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

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

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

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!

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

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

``````
Mr. Arithmetic logic Unit

serur
A great helper
Posts: 251
Joined: Thu Feb 23, 2006 11:30 pm
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!

minskcity
Experienced poster
Posts: 199
Joined: Tue May 14, 2002 10:23 am
Location: Vancouver
Could anybody explain me why backtracking can possibly work for this problem?