[C/C++] BOJ #1011 Fly me to the Alpha Centauri

This problem is about finding the minimum number of times a warp drive needs to be activated to travel to Alpha Centauri. Though it sounds like a space exploration problem, it essentially boils down to finding the largest number 'k' where the sum 1+2+3+...+k is less than half the distance to Alpha Centauri.

Warping to Alpha Centauri

Alpha Centauri is located approximately 4.37 light-years away from Earth. Even if a spaceship travels at the speed of light, it would take 4.37 years to reach. It's the closest star system to our Sun and appears very bright when observed from Earth. Unfortunately, it's difficult to observe from above the middle latitude of Northern Hemisphere.

 

warp to Alpha Centauri

This star system is often featured in science fiction movies as a potential new home for humanity. For instance, in the movie "Passengers," the spacecraft travels to Alpha Centauri, taking over a hundred years. To achieve this, passengers are put into hibernation. (Ironically, the technology for hibernation seems more challenging than developing a faster-than-light spacecraft.) I've heard that with current technology, it's experimentally possible to send an unmanned spacecraft to Alpha Centauri within 20 years using ion propulsion.

Getting back to the problem, to solve this, we need to find the largest value of 'n' where the sum of numbers from 1 to n is less than the given distance 'd'.

\[ 1 + 2 + 3 + ... + n = \sum_{k=1}^{n} k \le d \]

The formula for the sum of numbers from 1 to n is well-known, also known as triangular numbers:

\[ \sum_{k=1}^{n} k = \frac{n(n+1)}{2} \]

Using this, we can solve the following quadratic equation:

\[ x^2 + x - 2d = 0 \]

The positive root of this equation will generally be a real number. Since the function is monotonically increasing, taking the integer part of this real number gives us the desired answer. 

I've used the quadratic formula and added a margin to the numerical value to prevent round-off errors.

 

Warp to the Alpha Centauri

Below is the source code I wrote. Please refer to it for reference only.

//----------------------------------------------------------
//    baekjoon #1011 - Fly me to the Alpha Centauri
//        - by Aubrey Choi
//        - created at 2019-09-11
//----------------------------------------------------------
#include <stdio.h>
#include <math.h>

int main()
{
    int t, x, y;
    scanf("%d", &t);
    while(t--)
    {
        scanf("%d%d",&x,&y); y-=x;
        if(y==1) { puts("1"); continue; }
        int r=(-0.9999+sqrt(1+4.0*y))/2.0;
        y-=r*(r+1);
        printf("%d\n", 2*r+(y+r)/(r+1));
    }
}