## 10346 - Peter's Smokes

Moderator: Board moderators

yahoo
Learning poster
Posts: 93
Joined: Tue Apr 23, 2002 9:55 am

### 10346 - Peter's Smokes

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
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
a simple formula like this will get you AC -- > ans = n + ((n-1) / (k-1))

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

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

### Reason

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

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:
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:
rest = n % k
temp = n/k
what's that?

I think you should put them all in rest:

rest=n%k + n/k;

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

### Ans

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

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

Jalal
Learning poster
Posts: 65
Joined: Sun Jun 02, 2002 8:41 pm
Contact:
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

junjieliang
Experienced poster
Posts: 169
Joined: Wed Oct 31, 2001 2:00 am
Location: Singapore
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
thanks
I get AC.