## 10346 - Peter's Smokes

Moderator: Board moderators

deddy one
Experienced poster
Posts: 120
Joined: Tue Nov 12, 2002 7:36 pm
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

btw,
nice avatar , I like Legolas too

have a nice day to y' all

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

### SOLUTION

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

Regards,
Ming Han
:: HanWorks ::

yiuyuho
A great helper
Posts: 325
Joined: Thu Feb 21, 2002 2:00 am
Location: United States
Contact:
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
Experienced poster
Posts: 147
Joined: Fri Jun 13, 2003 10:46 pm

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
New poster
Posts: 2
Joined: Thu Sep 18, 2003 6:06 am

### 10346 - WA

#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
Experienced poster
Posts: 136
Joined: Tue Apr 01, 2003 6:59 am
Location: Jakarta, Indonesia
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!!
There are 3 things one need to be successful : motivation, ability and chance. And if you're a believer, make it four : God's will.

cccc
New poster
Posts: 2
Joined: Thu Sep 18, 2003 6:06 am
thanks, I got AC

_.B._
Experienced poster
Posts: 160
Joined: Sat Feb 07, 2004 7:50 pm
Location: Venezuela
Contact:

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

Quantris
Learning poster
Posts: 80
Joined: Sat Dec 27, 2003 4:49 am
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
New poster
Posts: 43
Joined: Fri Jun 25, 2004 9:37 pm
> butts ... butts ... butt ... butts ... butt ... butts

teehee

dovier_antonio
New poster
Posts: 47
Joined: Fri Feb 18, 2005 5:00 am
Location: Havana, Cuba

### 10346 Hi !!!

code removed... thanks!
Last edited by dovier_antonio on Fri Feb 03, 2012 10:07 am, edited 1 time in total.

dovier_antonio
New poster
Posts: 47
Joined: Fri Feb 18, 2005 5:00 am
Location: Havana, Cuba

### Re: 10347 Hi !!!

code removed... thanks!
Last edited by dovier_antonio on Fri Feb 03, 2012 10:08 am, edited 1 time in total.

Raj Ariyan
Learning poster
Posts: 70
Joined: Sat Feb 05, 2005 9:38 am
Location: Gurukul

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");
Some Love Stories Live Forever ....

dovier_antonio
New poster
Posts: 47
Joined: Fri Feb 18, 2005 5:00 am
Location: Havana, Cuba

### Hi !!!!

Thanks... now i got AC!
Last edited by dovier_antonio on Fri Feb 03, 2012 10:08 am, edited 1 time in total.

dootzky
New poster
Posts: 36
Joined: Tue Apr 12, 2005 12:20 am
Contact:
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