10940 - Throwing cards away II

All about problems in Volume 109. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

User avatar
newton
Experienced poster
Posts: 162
Joined: Thu Jul 13, 2006 7:07 am
Location: Campus Area. Dhaka.Bangladesh
Contact:

Post by newton » Mon Jul 16, 2007 2:22 pm

dear,

should i use cerculer linklist algorithm in this problem ??


thanx

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Post by Jan » Mon Jul 16, 2007 2:26 pm

Yes :D .
Ami ekhono shopno dekhi...
HomePage

Obaida
A great helper
Posts: 380
Joined: Wed Jan 16, 2008 6:51 am
Location: (BUBT) Dhaka,Bagladesh.

Crazy WA..

Post by Obaida » Sat Mar 15, 2008 7:13 am

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

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;
}
try_try_try_try_&&&_try@try.com
This may be the address of success.

Obaida
A great helper
Posts: 380
Joined: Wed Jan 16, 2008 6:51 am
Location: (BUBT) Dhaka,Bagladesh.

Still WA...

Post by Obaida » Sat Mar 15, 2008 9:27 am

[/quote]
I got WA... again & again... But where is my error...! Why this gives me WA...
[/code]
try_try_try_try_&&&_try@try.com
This may be the address of success.

User avatar
emotional blind
A great helper
Posts: 383
Joined: Mon Oct 18, 2004 8:25 am
Location: Bangladesh
Contact:

Re: Still WA...

Post by emotional blind » Sat Mar 15, 2008 8:13 pm

Obaida wrote: I got WA... again & again... But where is my error...! Why this gives me WA...
carefully consider the case when n=1.

Obaida
A great helper
Posts: 380
Joined: Wed Jan 16, 2008 6:51 am
Location: (BUBT) Dhaka,Bagladesh.

Confusion

Post by Obaida » Sun Mar 16, 2008 6:17 am

When n=1 then what will be the output... 1 or 0.
try_try_try_try_&&&_try@try.com
This may be the address of success.

User avatar
emotional blind
A great helper
Posts: 383
Joined: Mon Oct 18, 2004 8:25 am
Location: Bangladesh
Contact:

Re: Confusion

Post by emotional blind » Sun Mar 16, 2008 6:42 am

Obaida wrote: When n=1 then what will be the output... 1 or 0.
Problem Description wrote:Given is an ordered deck of n cards numbered 1 to n

Obaida
A great helper
Posts: 380
Joined: Wed Jan 16, 2008 6:51 am
Location: (BUBT) Dhaka,Bagladesh.

Oh..

Post by Obaida » Sun Mar 16, 2008 7:00 am

I think I have it... If n==1 then output will be 1.
try_try_try_try_&&&_try@try.com
This may be the address of success.

User avatar
emotional blind
A great helper
Posts: 383
Joined: Mon Oct 18, 2004 8:25 am
Location: Bangladesh
Contact:

Re: Oh..

Post by emotional blind » Sun Mar 16, 2008 8:33 am

Obaida wrote: I think I have it... If n==1 then output will be 1.
So you got Accepted. Is it?

Obaida
A great helper
Posts: 380
Joined: Wed Jan 16, 2008 6:51 am
Location: (BUBT) Dhaka,Bagladesh.

Post by Obaida » Sun Mar 16, 2008 9:37 am

It should be... I got Acc.. before posting...
try_try_try_try_&&&_try@try.com
This may be the address of success.

DD
Experienced poster
Posts: 145
Joined: Thu Aug 14, 2003 8:42 am
Location: Mountain View, California
Contact:

Re: 10940 - Throwing cards away II

Post by DD » Sun Apr 17, 2011 11:34 pm

It should be a dynamic programming problem but how can some people solved this problem in 0.012secs :o
Have you ever...
  • Wanted to work at best companies?
  • Struggled with interview problems that could be solved in 15 minutes?
  • Wished you could study real-world problems?
If so, you need to read Elements of Programming Interviews.

User avatar
plamplam
Experienced poster
Posts: 150
Joined: Fri May 06, 2011 11:37 am

Re: 10940 - Throwing cards away II

Post by plamplam » Tue Jun 07, 2011 9:03 am

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

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?
You tried your best and you failed miserably. The lesson is 'never try'. -Homer Simpson

User avatar
uDebug
A great helper
Posts: 475
Joined: Tue Jul 24, 2012 4:23 pm

Re:

Post by uDebug » Tue Feb 11, 2014 1:35 pm

Jan wrote:Just evaluate the values upto 50. And you will get an easy sequence. If you still dont find it then I will tell you. :D
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
Check input and AC output for over 7,500 problems on uDebug!

Find us on Facebook. Follow us on Twitter.

lighted
Guru
Posts: 585
Joined: Wed Jun 11, 2014 9:56 pm
Location: Kyrgyzstan, Bishkek

Re: 10940 - Throwing cards away II

Post by lighted » Thu Nov 20, 2014 7:22 pm

plamplam wrote: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 :D
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? :D

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. :)
A person who sees the good in things has good thoughts. And he who has good thoughts receives pleasure from life... Bediuzzaman

Post Reply

Return to “Volume 109 (10900-10999)”