10940 - Throwing cards away II

[newton]

dear,

should i use cerculer linklist algorithm in this problem ??


thanx

[Jan]

Yes .

[Obaida]

Some one please help me I think i have done it by simulation... But what should be done now... It's giving me WA.. But I think it will not overflow... What's wrong....

Code: Select all

#include<stdio.h>
int main()
{
	long int n,x,ans,s;
	while(scanf("%ld",&n)==1)
	{
		if(n==0)
			break;
		else
		{
			x=1;
			while(x<n)
			{
				x=x*2;
				s=x%n;
				ans=n-s;
			}
			printf("%ld\n",ans);
		}
	}
	return 0;
}

[Obaida]

[/quote]
I got WA... again & again... But where is my error...! Why this gives me WA...
[/code]

[emotional blind]

I got WA... again & again... But where is my error...! Why this gives me WA...

carefully consider the case when n=1.

[Obaida]

When n=1 then what will be the output... 1 or 0.

[emotional blind]

When n=1 then what will be the output... 1 or 0.

Given is an ordered deck of n cards numbered 1 to n

[Obaida]

I think I have it... If n==1 then output will be 1.

[emotional blind]

I think I have it... If n==1 then output will be 1.

So you got Accepted. Is it?

[Obaida]

It should be... I got Acc.. before posting...

[DD]

It should be a dynamic programming problem but how can some people solved this problem in 0.012secs

[plamplam]

This is not a dynamic programming problem @DD...this is a very interesting problem that i solved using simple mathematics.
I didn't even use recursions or functions in my code
My hint is solve 10935 before attempting this
Second hint is after you solve 10935, you can't solve this using the same method because you will get TLE, still worth a try isn't it?

Note: May be it is possible to solve this using DP or some complex algorithm, but there is always a smarter way. You only need to know the basic of programming for the simplest solution which I could find, just think for a while.

And @DD, my best for this problem is 0.032 sec, and I don't know much about code optimization. So why is it not possible to get AC in 0.012 seconds with optimizations like fread or faster I/O?

[uDebug]

Just evaluate the values upto 50. And you will get an easy sequence. If you still dont find it then I will tell you.

To solve this problem I took Jan's hint and evaluated the values from 1 through 15 (you don't need to really go all the way to 50). Though I initially started this by hand, I realized it'd be easier to do this using UVA Toolkit. If you're completely stuck like I was, then this might be a good start.

Also, here's some input / output that I found useful during testing / debugging.

Input:

Code: Select all

1
22
3333
444444	
500000	
66666	
777	
89
9999	
0

AC Output:

Code: Select all

1
12
2570
364600
475712
2260
530
50
3614

[lighted]

This is not a dynamic programming problem @DD...this is a very interesting problem that i solved using simple mathematics.
I didn't even use recursions or functions in my code
My hint is solve 10935 before attempting this
Second hint is after you solve 10935, you can't solve this using the same method because you will get TLE, still worth a try isn't it?

Note: May be it is possible to solve this using DP or some complex algorithm, but there is always a smarter way. You only need to know the basic of programming for the simplest solution which I could find, just think for a while.

And @DD, my best for this problem is 0.032 sec, and I don't know much about code optimization. So why is it not possible to get AC in 0.012 seconds with optimizations like fread or faster I/O?

I solved it with DP. It is not complex at all, very simple recurrence. My best for this problem is also 0.032.