10346 - Peter's Smokes

[deddy one]

for yiuyuho :

thx very much for the explanation,
to be honest I never thought about solving this
problem by straight forward algorithm,
because I always thought that this kind of
problem need a formula to solve it.

The credit for discovering the formula
should be given to my friend
Anton Supriyadi

btw,
nice avatar , I like Legolas too

have a nice day to y' all

[Ming Han]

Ok...After what has been going on in this forum for the past few months...no one still cannot clealy explain why (n + (n-1)/(k-1)) works.

I have compiled some of the points in this forum and added my own.
The full investigation report is here. (You need Microsoft Word)
http://www.chs.edu.sg/~01chs194/programs/math_3a30.doc

Please feel free to post your comments.

Regards,
Ming Han

[yiuyuho]

please elaborate more on your assumption of k^t = n, note that without strengthening that assumption, your explaination is the clone of one of the previous post.

[bugzpodder]

Hi Ming, let me point out your weaknesses in your document:

1. k!=1 -- mod 1 is not interesting. so it should be k>1
2. the geometric series assumes that you do NOT round down when doing n/k. in your question you assumed otherwise.

3. you cannot assume n=k^t, it is not necessary true.

[cccc]

#include <iostream>
using namespace std;

int main()
{
int a[100],b[100],c,i,j,k=0;
while(cin >> i >> j)
{
a[k]=i;b[k]=j;k++;
}
for(int l=0;l<k;l++)
{
c=a[l];
for(int m=a[l];m>=b[l];m)
c+=m=m/b[l];

cout << c << endl;
}

}

[Joseph Kurniawan]

n=20, k=3 :
First Peter can smoke 20 times and leaving 20 butts.
Now he can make 1 new smoke by using 3 butts:
New smoke = 20/3 = 6
Butts left = 20%6 = 2
Now Peter can smoke 6 more times, thus he has smoked 26 times
leaving 6 more butts, making the total butts 6+2=8.
New smoke = 8/3 = 2
Butts left = 8%3 = 2
Peter can smoke twice, has smoked 26+2 = 28 times and leaving
two more butts (current butts = 2+2 = 4).
New smoke = 4/3 = 1
Butts left = 4%3 = 1
Peter smoke once more and he has smoked for 29 times and
leaving 1+1 = 2 butts.
Since he needs 3 butts to make a new smoke, yet only two available
then Peter can't make anymore smoke.
So Peter smoked 29 times.
Hope this simulation helps!!

[cccc]

thanks, I got AC

[_.B._]

Great example and explanation Joseph Kurniawan!.
Keep posting!.

[Quantris]

Couldn't read the document, but this question is sort of a chestnut...

The formula I used is (kn-1)/(k-1), which is really the same as the n+... version.

The simple explanation is:
If we have n cigarettes, we have k*n butts (imagine breaking them each up into k butts at the start).

Take 1 butt out, leaving kn-1. Then, you can take (k-1) butts at a time, atttach them to the one you took out, and smoke it, leaving just the 1 butt again. so basically you burn k-1 butts each time.

Therefore (kn-1)/(k-1) (floored by integer division) is exactly how many cigarettes you can smoke.

[Andrew Neitsch]

> butts ... butts ... butt ... butts ... butt ... butts

teehee

[dovier_antonio]

code removed... thanks!

[dovier_antonio]

code removed... thanks!

[Raj Ariyan]

Hi,
First of all i think the problem number is 10347 not 10346. Well from first look of ur code i get one mistake done by u. When the output will be
-1 then u print int part. You have to print -1.000. Hope it helps. Good Luck.

just use ->
printf("-1.000\n");

[dovier_antonio]

Thanks... now i got AC!

[dootzky]

really funny.

i would normaly solve this problem with a simulation, but hence the formula is now well known, i did it with ONE LINE?! omg.

Code: Select all

void main () { long k,n; while (cin >> n >> k) cout << n+ ((n-1)/(k-1)) << endl; }

seriously, this is funny.

ofcoruse, line above this line is #include <isotream.h>, but that's not really a code, it's more of a ... tehnical stuff.

thx anyway, this one was a freebie.
greeTZ,
dootzky