617A.Elephant - Codeforces Programming Problem Solution Code Explained
7 May-9May, 2020
-------------------------------------
There are lots of solutions of codeforces problems you can find on the internet.
But the problem I face is that a very few explanations of those available. In
this tutorial I’m going to try to give an easy-to-understand explanation of a codeforces
problem titled “617A-Elephant”.
First up, I want you to read the problem.
----------------------------------------------------------------------
An elephant decided to visit his
friend. It turned out that the elephant's house is located at point 0 and his
friend's house is located at point x(x > 0) of the coordinate
line. In one step the elephant can move 1, 2, 3, 4 or 5 positions forward.
Determine, what is the minimum number of steps he needs to make in order to get
to his friend's house.
------------------------------------------------------------------------
Now look at the image carefully.
Does it make
sense? If doesn’t, then don’t worry. I am here for you with this tutorial.
Let’s just
imagine our elephant can hop.
At this
moment he is at point 0. He wants to go around at his friend’s house which is
located at point 10 (i.e. x = 10). Before he starts he wants to know how many
hops he needs to make to reach his friend’s house. The problem is he doesn’t
know mathematics or programming ;) . He just knows how to hop :P . Why not we programme for him. Let’s help
him out.
In one hop he can reach either position
1:
If he makes
a 5-position hop, he needs to make two hops to reach his friend’s house at
point 10.
That is 10 / 5 = 2 hops; where 10 is the target/reach
point and 5 is the number he can reach in his one hop.
If he wants to
make a 2-position hop, he needs to make five hops to reach.
10/2 = 5
hops
We would
suggest a 5-position hop. Because 2 is the minimum number of hops in which he
can get to his friend’s house. That’s the explanation of the problem.
Now read the
problem again. Hope you understand it.
Well, this
is an explanation for mankind. How do we make the solution understandable for
computer?
Now we’re
going to write a programme for it.
--
Let’s assume
his friend’s house is at some different points.
If the house
is at point 1, he needs to make a 1-position hop.
1 reach
point / 1 position hop = 1 (one hop)
That means
if he wants to reach point 1, he just needs to make a 1 position hop.
Or,
alternatively we can calculate like this-
5 is his
greatest hop position. So..
1 reach
point / 5 position hop = 0.2
We will add
1 to this result.
0.2+ 1 =
1.2; round figure 1 (one hop)
We get one
hop.
---
If the house
is at point 2…
2/ 2 position-hop
= 1 hop (one hop) minimum
Or, 2/1 position
hop= 2 hops (two hops); if he wants to take 1 position hop.
But we will take
one hop, because we need the minimum number of hops.
Or, like we
did before… dividing the point by 5.
2 point / 5
= 0.4
Add 1 to it.
0.4+ 1 =
1.4; round figure 1 (one hop) minimum
---
If at point
3..
3/3 position
hop = 1(one hop)
Or, 3/2 =
1.5; round figure 2 (two hops).
We will take
one hop as it is minimum.
Or,
alternatively,
3/5 = 0.6
0.6+1 = 1.6;
round figure 1 (one hop) minimum
--
At point 4
4/4
position-hop = 1(one hop) minimum
4/3 = 1.3; round
figure 2 (two hops)
4/2 = 2 (two
hops)
Or,
4/5 = 0.8;
0.8 + 1 =
1.08; round figure 1 (one hop) minimum
(reach
point/5) + 1 = number of hops
-
What if the
house is at point 5?
Easy answer,
isn’t it?
5/5 = 1;
minimum (5 reach point is divisible by 5 position hop)
5/4 = 1.2; round
figure 2
5/3 = 1.6; round
figure 2
5/2 = 2.5;
round figure 3
5/1 = 5;
-
Now consider
the point at 6, 7, 8, 9, 10, 12, 13, 14, 15 bla.. bla… bla…
Look, these
reach points are greater than 5 the biggest position hop. Since we want to find
the minimum number of hops, we don’t need to consider other smaller position
hop i.e., 4, 3, 2, 1. In these cases, we will recommend 5 to the elephant. So let’s
see..
6/5 = 1.2; (1.2+1=2)
2 hops
7/5 = 1.4;
(1.4+1=2) 2 hops
8/5 = 1.6; (1.6+1=2)
2 hops
9/5 = 1.8;
(1.8+1=2) 2 hops
10/5 = 2; 2
hops
11/5 = 2.2;
(2.2+1=3) 3 hops
12/5 = 2.4; (2.4+1=3)
3 hops
13/5 = 2.6;
(2.6+1=3) 3 hops
14/5 = 2.8; (2.8+1=3)
3 hops
15/5 = 3; 3
hops
-----
Well, the
elephant can make other position hops to reach these points, like-
For point 6…
6/1 =6; 6
hops
6/2 = 3; 3
hops
6/3 = 2; 2
hops
6/4 = 1.5; 2
hops
6/5 = 1.2;
(1.2+1=2) 2 hops
Here 2 hops
is the minimum. So for the simplicity we can consider only 5.
--------------------------------------------------
Let’s consider
our findings at a glance.
1/5 = 0.2; (0.2+1=1)
1 hop
2/5 = 0.4; (0.4+1=1)
1 hop
3/5 = 0.6;
(0.6+1=1) 1 hop
4/5 = 0.8; (0.8+1=1)
1 hop
5/5 = 1; 1
hop
6/5 = 1.2; (1.2+1=2)
2 hops
7/5 = 1.4;
(1.4+1=2) 2 hops
8/5 = 1.6; (1.6+1=2)
2 hops
9/5 = 1.8;
(1.8+1=2) 2 hops
10/5 = 2; 2
hops
11/5 = 2.2;
(2.2+1=3) 3 hops
12/5 = 2.4; (2.4+1=3)
3 hops
13/5 = 2.6;
(2.6+1=3) 3 hops
14/5 = 2.8; (2.8+1=3)
3 hops
15/5 = 3; 3
hops
-------------------------------------------------------
Can you
relate anything?
Yeah, when
the reach points are divisible by 5, the quotients are the minimum number of
hops.
And when not
divisible, we’ll add 1 to the quotients and find the minimum number of hops.
Now let’s
see the input, output and examples the problem gives us:
---------------------------------------------------------------------------------------------
Input
The first line of the input contains
an integer x (1 ≤ x ≤ 1 000 000) — The coordinate of the
friend's house.
Output
Print the minimum number of steps
that elephant needs to make to get from point 0 to point x.
Examples
Input 5
Output 1
-
Input 12
Output 3
Note
In the first sample the elephant
needs to make one step of length 5 to reach the point x.
In the second sample the elephant
can get to point x if he moves by 3, 5 and 4. There are other ways to
get the optimal answer but the elephant cannot reach x in less than
three moves.
--------------------------------------------------------------------------------------------------------------
Let’s write our programming code..
#include<stdio.h>
int main(){
int x;
scanf("%d", &x);
if( x%5 == 0){
printf("%d", x/5);
}else{
printf("%d", x/5+1);
}
return 0;
}
That’s all for this problem. Hope
you understand it better than before. See you!
Comments
Post a Comment