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 »

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 »

Please Help me ......

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

10164

Post 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!!!!!!!
none

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

Post by Red Scorpion »

Oh, Finally i got it.

Thanks.

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

Post 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

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 »

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 »

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 »

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 »

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 »

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 »

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 »

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 »

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 »

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 »

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

Post Reply

Return to “Volume 101 (10100-10199)”