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

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

Post by deddy one » Fri Apr 18, 2003 7:40 am

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

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

SOLUTION

Post by Ming Han » Mon May 05, 2003 4:21 pm

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

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

Post by yiuyuho » Thu May 08, 2003 12:11 am

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

Post by bugzpodder » Sat Jun 14, 2003 9:30 pm

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

10346 - WA

Post by cccc » Thu Sep 18, 2003 6:11 am

#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

Post by Joseph Kurniawan » Thu Sep 18, 2003 7:08 am

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!! :wink: :wink: :wink:
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
Location: Lethbridge, Alberta, Canada

Post by cccc » Fri Sep 19, 2003 3:04 am

thanks, I got AC

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

Helpful.

Post by _.B._ » Wed May 19, 2004 7:37 am

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

Quantris
Learning poster
Posts: 80
Joined: Sat Dec 27, 2003 4:49 am
Location: Edmonton AB Canada

Post by Quantris » Sun Jun 27, 2004 6:23 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

Post by Andrew Neitsch » Mon Jun 28, 2004 3:00 am

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

teehee

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

10346 Hi !!!

Post by dovier_antonio » Mon Mar 14, 2005 4:52 am

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

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

Re: 10347 Hi !!!

Post by dovier_antonio » Mon Mar 14, 2005 5:40 am

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

Reply

Post by Raj Ariyan » Mon Mar 14, 2005 6:57 pm

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

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

Hi !!!!

Post by dovier_antonio » Tue Mar 15, 2005 1:00 pm

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
Location: belgrade, serbia (ex yugoslavia)
Contact:

Post by dootzky » Sun May 08, 2005 3:03 am

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

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

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

Post Reply

Return to “Volume 103 (10300-10399)”