LOJ 1008 - Fibsieve's Fantabulous Birthday

In the first input, we will be given the number of test cases T . After that we will be given an input S upto T times, each of which represents the S-th second and we have to output which cell would light up by outputting the value of its column and row number separated by a single space.

If we take few examples from the chess board, for 25, its row number is 5 and 5 = √25. For 24, its row number is 5 and 5 = ⌈√24⌉. However, for 16, its column number is 4 and 4 = ⌈√16⌉. Similarly, for 15, its column number is 4 and 4 = ⌈√15⌉. So, if ⌈√S⌉ is an even number, the ceiling value of the square root of S produces the column number and if it is an odd number, it produces the row number.

For the column number of 24 it is 2 and here 2 = (closest square number to 24 ~ 24) + 1 = 25 - 24 + 1 = 2. In case of 15, its row number is 2 and 2 = (closest square number to 15 ~ 15) + 1 = 16 -15 + 1 = 2. In case of both 24 and 15, the closest square number is after them.

But in case of 17, its column number is 5 and 5 = ⌈√17⌉ although here ⌈√17⌉ produced 5 which is an odd number and again the row number is 1 = (closest square number to 17 ~ 17) = 17 - 16 = 1. Now to determine whether the closest square number to S is after or before it, we can determine by whether ⌈√S⌉² - S > ⌈√S⌉ or not. If it is lesser than it then we know that the closest square number to S is before S and if it is greater then we know that the closest square number to S is after S. If we examine the closest square number to S when it is after S, that number is actually (⌈√S⌉ - 1)². Example: for 17, (⌈√17⌉ - 1)² = (5 - 1)² = 16 and from that, 17 - 16 = 1 which is the row number of 17.

The above implementation is Accepted.

Solution in C

#include <stdio.h>
#include <math.h>

int main()
{
    int cases;
    scanf("%d", &cases);
    for (int i = 1; i <= cases; i++)
    {
        long long seconds, root, lackings, row, column;
        scanf("%lld", &seconds);
        root = ceil(sqrt(seconds * 1.0));
        lackings = root * root - seconds;
        if (lackings < root){
            row = root;
            column = lackings + 1;
        }
        else{
            column = root;
            row = seconds - (root-1) * (root-1);
        }
        if(root % 2 == 0){
            long long temp = column;
            column = row;
            row = temp;
        }
        printf("Case %d: %lld %lld\n",i, column, row);
    }

    return 0;
}

Tutorial source