10346 - Peter's Smokes

All about problems in Volume 103. 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
yahoo
Learning poster
Posts: 93
Joined: Tue Apr 23, 2002 9:55 am

10346 - Peter's Smokes

Post by yahoo » Sat Aug 31, 2002 8:55 am

I can't understand why i get wrong answer in this code! Is there any typical data where my code fails. Will anybody see my code and tell me wheree i am is wrong. Thanks in advance.Here is my code:
#include <stdio.h>

main()
{
int r,n,k,cig,d,e,t;
while(1)
{
r=scanf("%d%d",&n,&k);
if(r==EOF) break;

cig=n;t=0;
while(1)
{
d=n/k;
e=cig%d;
cig=cig+d;
t=d+e;
if(t>k) n=t;
if(t<k) break;
}
printf("%d\n",cig);
}
return 0;
}
/* @END_OF_SOURCE_CODE */

wyvmak
Experienced poster
Posts: 110
Joined: Thu Dec 13, 2001 2:00 am

Post by wyvmak » Sat Aug 31, 2002 12:33 pm

at first glance, this statement is weird
e=cig%d;

cig is increasing, do you mean n?
d seems not much relate to e, do you mean k?
or maybe i've misunderstood something.

deddy one
Experienced poster
Posts: 120
Joined: Tue Nov 12, 2002 7:36 pm

Post by deddy one » Thu Nov 14, 2002 5:07 am

a simple formula like this will get you AC -- > ans = n + ((n-1) / (k-1))
:D
BTW when I use EOF , I got restrictive function , so I change it into
while (scanf ("%lld %lld ",&n,&k)==2) and it worked just fine , any comments on that ???? 8)

User avatar
Ming Han
Learning poster
Posts: 77
Joined: Thu Jun 06, 2002 7:10 pm
Location: Singapore
Contact:

Reason

Post by Ming Han » Thu Dec 26, 2002 5:44 pm

Can you explain why this works?
[cpp]ans = n + ((n-1) / (k-1)) [/cpp]

Thanks.
:: HanWorks ::

deddy one
Experienced poster
Posts: 120
Joined: Tue Nov 12, 2002 7:36 pm

Post by deddy one » Wed Jan 01, 2003 7:37 pm

well, believe it or not , but the formula was invented by
a friend of mine when we tried to solve this problem.
at first I think the formula will be

ans = n+ n/k ;
where n/k stands for the number of additional cig

but it didn't pass the sample input
:oops: , so my friend here, he
substract 1 from each element of the additional cig,
and surprisingly it worked.

hmm , what do you call it ,"beginner's" luck maybe
:wink: how about your formula ming han???
do you have another formula for this problem????

does anyone have another formula that works too??

yiuyuho
A great helper
Posts: 325
Joined: Thu Feb 21, 2002 2:00 am
Location: United States
Contact:

Strict forward

Post by yiuyuho » Thu Mar 06, 2003 6:37 am

The strict forwards algorithm for this problem will be:

input n,k;

sum = n;
while(n>=k) //possible re group and get more cigarettes
{
sum+=n/k //add the number of cigarettes possible to re-group
n = n/k+n%k
/*the butts of the re-grouped cigarettes (n/k) plus the cigarettes butts that are not re-grouped (n%k) become the new cigarettes butt numbers*/
}

print sum;
Last edited by yiuyuho on Thu Mar 06, 2003 7:39 am, edited 1 time in total.

yiuyuho
A great helper
Posts: 325
Joined: Thu Feb 21, 2002 2:00 am
Location: United States
Contact:

Post by yiuyuho » Thu Mar 06, 2003 7:38 am

The solution you found: ans = n+ (n-1)/(k-1) is actually a much better mathematical algorithm.

First let me congrat you good job on finding this. Please don't be shamed that you do something you didn't know the reason, the fact that you find that out is itself a success.
If it's not you, I will probably just use the strict forward way and never (or later, very later) discover this embedded algorithm in it. So i need to say: Thank You!

Now, to why it works (this is not perfect, any improvement or suggestion is welcomed):

Note: all 'a/b' operators refer to floor(a/b) where a,b in set positive Integer such that b>1, which is the domain of our problem.

Let's first formulate our original algorithm:
We know Peter can Smoke n, so n is the base of our sum.

now the ans is n+f(n),
where

f(n) = n/k + f(n/k + n%k) if n>=k, 0 else

this is just a recurrence from the previous algorithm (previous message)

if we expand this, we have

f(n) = n/k+ ((n/k)+(n%k))/k + (((n/k)+(n%k))/k+((n/k)+(n%k))%k)/k+...


= n/k + n/k^2 + (n%k)/k + n/k^3 + (n%k)/k/k + ((n/k)+(n%k))%k/k + ...

since (x%y)/y = 0, because 0<=x%y<y, recall a/b is refering to the floor value.

so each recurrence the '%'s go away and we have another n/k^i for each additional recurrence.

so our equation becomes:

f(n) = n/k + n/k^2 + n/k^3+ ... n/k^t

such that t = {max t | k^t <=n), because if k^(t+1) > n, then n/k^(t+1) goes to 0.

Therefore,

f(n) = Sum(n/k^i, i=1..t)
= (n/k)*Sum(1/k^i, i=0..t-1)
= (n/k)*((1/k^t - 1)/(1/k - 1)) //Geometric Sum
= (n/k)*((1-k^t)/k^t)*(k/(1-k))
= (n)*((1-k^t)/k^t)/(1-k)

now, this is the part I am not sure, but I conjecture that usder the assumptions I made (intger operation, floor, value for t),
we can let k^t = n without losing validation. (Please correct me if I am wrong and prove it if you know how)

then, it's easy:

f(n) = (n)*((1-n)/n)/(1-k) = (1-n)/(1-k) = (n-1)/(k-1)

and ans = n + f(n) = n + (n-1)/(k-1)

yiuyuho
A great helper
Posts: 325
Joined: Thu Feb 21, 2002 2:00 am
Location: United States
Contact:

Post by yiuyuho » Sun Mar 09, 2003 8:18 pm

rest = n % k
temp = n/k
what's that?

I think you should put them all in rest:

rest=n%k + n/k;

User avatar
Ming Han
Learning poster
Posts: 77
Joined: Thu Jun 06, 2002 7:10 pm
Location: Singapore
Contact:

Ans

Post by Ming Han » Mon Mar 10, 2003 12:37 pm

Just test your output using this formula:

[cpp]n + ((n-1) / (k-1)) [/cpp]
:: HanWorks ::

Hisoka
Experienced poster
Posts: 120
Joined: Wed Mar 05, 2003 10:40 am
Location: Indonesia

Post by Hisoka » Mon Mar 10, 2003 7:05 pm

I think the formula like ans=n+(n-1)/(k-1) is not exactly valid formula but it can get true for this problem because if you use int, long int or another int the number between a<ans<a+1; the result is a. so this formula cannot be simulated by math algo. But I am very appreciate because deddy and his friend can manipulate this problem with their solution :)

yiuyuho
A great helper
Posts: 325
Joined: Thu Feb 21, 2002 2:00 am
Location: United States
Contact:

Post by yiuyuho » Mon Mar 10, 2003 7:35 pm

Hisoka wrote: this formula cannot be simulated by math algo.
Why not, it there anything wrong with my deviriation above? If so, please tell me what's wrong

lendlice
New poster
Posts: 22
Joined: Thu Nov 21, 2002 10:50 am

10346 W.A

Post by lendlice » Tue Apr 08, 2003 9:24 am

I got w.a.
anyone can help me.
thanks.
[cpp]//10346
#include<stdio.h>
main()
{
int n=0,k=0,ans=0,add=0,add1=0;
scanf("%d%d",&n,&k);
add=n/k;
ans+=add;
add+=n%k;
while(add>=k)
{
add1=add;
add=add/k;
ans+=add;
add+=add1%k;
}
ans+=n;
printf("%d\n",ans);
}[/cpp]

Jalal
Learning poster
Posts: 65
Joined: Sun Jun 02, 2002 8:41 pm
Location: BANGLADESH
Contact:

Post by Jalal » Thu Apr 10, 2003 9:29 pm

No need to run a while loop in here.
try to solve in a equation.
Just in a simple equation to give the corresponding result
:wink:

junjieliang
Experienced poster
Posts: 169
Joined: Wed Oct 31, 2001 2:00 am
Location: Singapore

Post by junjieliang » Fri Apr 11, 2003 2:26 am

Is that the code you submitted? You should do something like:

Code: Select all

while (scanf("%d%d", &n, &k) == 2) {
  /* Code */
}

lendlice
New poster
Posts: 22
Joined: Thu Nov 21, 2002 10:50 am

Post by lendlice » Fri Apr 11, 2003 3:55 am

thanks
I get AC.
:P

Post Reply

Return to “Volume 103 (10300-10399)”