CO92SUBW - EDITORIAL

editorial
, , , ,
1

Author: Trung Nguyen
Tester and Editorialist: Alei Reyes ## Problem Link
Practice

Contest

Difficulty

Easy

PREREQUISITES:

Implementation

Problem

There are some stations on the X-axis. The distance between the i-th and i+1-th station is i+1. It takes one second to move one unit of distance, also it takes one second to move from one station to the next. We want to go from point 0 to point X in the minimum time.

Explanation

Let di denote the position of the i-th station. The distance between station i and i-1 is equal to i. Therefore di = di-1 + i.

If we apply the recurrence recursively we get that di is equal to the sum of integers from 1 to i. In closed form: di = (i*(i+1))/2.

Numbers of the sequence 1 3 6 10 15 are called triangular numbers.

Note that triangular numbers increases quadratically. There are not many of them below 109, actually there are only 44720.

Chef wants to go to position X. So he can walk to station 1, then go by trains to the nearest station to X, and finally go walking the remaining distance.

Now the problem is to find the leftmost and rightmost station to the cinema, and check which one is more convenient. Is possible to binary search the answer, but since constraints are small, we can just iterate over all possible triangular numbers.

Implementation

Author’s Solution

Tester’s and Editorialist’s Solution

1 Like
2

int t = nextInt();
while(t–>0){
int n = nextInt();
int min = Integer.MAX_VALUE;
for(int i=1;i<45000;i++){
int sum = i+ Math.abs(i*(i+1)/2 -n);
min = Math.min(min,sum);
}
p.println(min);
}

4

#include<bits/stdc++.h>
using namespace std;
int main()
{
int t,j=0,x,n,f,d1,d2,g;
cin>>t;
while(j<t)
{
cin>>x;
n=(-1+sqrt(1+(8*x)))/2;

	f=((n+1)*(n+2))/2;
	
	g=(n*(n+1))/2;
	
	d1=abs(g-x);
	
	d2=abs(f-x);
	
	if(d1>d2)
	cout<<(d2+n+1)<<"\n";
	else if(d2>=d1)
	cout<<(d1+n)<<"\n";
	j++;
}
return 0;

}strong text
please check my code even though my out puts are correct its still not accepting my solution
can you pls provide me the test case where it is failing

5

Just FYI sqrt() is not computed in constant time. But still nice solution

7

It could be a overkill but We can use binary search as well to find closest stations on the left and right of the x.

3 Likes