10346 - Peter's Smokes

[yahoo]

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]

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]

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]

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

Thanks.

[deddy one]

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
how about your formula ming han???
do you have another formula for this problem????

does anyone have another formula that works too??

[yiuyuho]

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;

[yiuyuho]

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]

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]

Just test your output using this formula:

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

[Hisoka]

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]

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]

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]

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]

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

Code: Select all

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

[lendlice]

thanks
I get AC.