Codeforces Round #621 (Div. 1 + Div. 2) Editorial help needed

1

anyone please explain why the answer is max(2,ceil(d/y)) in the editorial
thanks in advance :slight_smile:

2

This article will help you. The question is a little modified version of this question.
Here is the article

3

Think of the question as drawing circles( of radius equal to any of the ‘favorite number’ ) , the center of your first circle is going to be (0,0) and all the circles after that will have center in the circumference of your previous circle. Since the intermediate points can be non-integer points, you can draw another circle from any point that lies on the circumference of the previous circle. The last circle will be the one whose circumference passes through (d,0).

I am talking about circles because circle is locus of all points which are at a constant distance from its center. So all the points in the circumference are points you can go to for your next step.

So to reach (d,0) in minimum number of circles you need to draw bigger circles ( of radius equal to the biggest favorite number , say M ) .

If d is present in the favorite numbers array you can reach (d,0) in one circle only.

Now if d is divisible by M, you can reach (d,0) in d/M circles, otherwise you will need d/M + 1 circles or ceil(d/M) circles . ( Try to draw the circles and check yourself )

But if M > d , then you will need exactly 2 circles . ( Try to draw the circles and check yourself. )

5 Likes
4

this is the cow one right?

i just divided into cases and solved.
if the jump is higher than the position than it will always be 2.
if multiple then pos/jump
if not multiple then pos+1/jump
because one extra jump is needed to reach the desired location.
Try to draw and visualise.
Else @jo3kerr has explained really well :slight_smile:

1 Like
6 
ll ans = INF;
loop(i,0,n)
{
	if(a[i]>x)
		ans = min(ans,2LL);
	else if(x%a[i]==0)
		ans = min(ans,x/a[i]);
	else
		ans = min(ans,x/a[i]+1);
}
std::cout<<ans<<endl;
1 Like
7

can you please explain this part??

8

my answer is exactly this

9

if the number is not multiple we will have to take two jumps sideways when we are at floor(x/a[i]) which will end up becoming x/a[i]+1 in the end.

1 Like
10

Thanks :blush:

1 Like
11

Thanks for your time bro😊