Solution UVA: 10161 - Ant on a Chessboard

 

Problem	Verdict	Lang	Time	Best	Rank	Submit Time
| discuss10161 - Ant on a Chessboard	Accepted	C++11	0.000	0.000	2978	1 mins ago

Suggest:

- I believe you can solve if i show you this hint:

26 27 28 29 30 31  6
25 24 23 22 21 32  5
10 11 12 13 20 33  4
9  8  7  14 19 34  3
2  3  6  15 18 35  2
1  4  5  16 17 36  1

1  2  3  4  5  6

Transform matrix (we only need to get first value of rows)

1
2 3 4
5 6 7 8 9
10 11 12 13 14 15 16
....

Get first value of rows

1 = a[1]
2 = a[2] + 1 
5 = a[3] + 3 = 2 + 3
10 = a[4] + 5 = 5 + 5
....

From a[k] and k, we create result

Example
8
For(ak) .. Because 10 > 8 => break and we get a[k] = 5 and k = 3
(result is a[k] -> a[k+1]-1)

For i,j <= k
5 -> 1,3 (a[k])
6 -> 2,3
7 -> 3,3
8 -> 2,3 (result) 
9 -> 1,3 (a[k+1]-1) 

10 (a[k+1])

#include<bits/stdc++.h>

using namespace std;

int a[1000111];

int n, m;

void solve(int k){

    int x= a[k]-1;

   

    if (k%2==0){

   

        for(int j=1; j<=k; j++){

            ++x;

            if (x==m){

                cout<<j<<" "<<k<<"\n";

                return;

            }

        }

   

        for(int i=k-1; i>=1; i--){

            ++x;

            if (x==m){

                cout<<k<<" "<<i<<"\n";

                return;

            }

        }

    }

    else{

       

        for(int i=1; i<=k; i++){

            ++x;

            if (x==m){

                cout<<k<<" "<<i<<"\n";

                return;

            }

        }

        for(int j=k-1; j>=1; j--){

            ++x;

            if (x==m){

                cout<<j<<" "<<k<<"\n";

                return;

            }

        }

   

    }

   

}

int main(){

    ios::sync_with_stdio(false); cin.tie(nullptr);

   

    a[1]= 1;

    for(int i=2, j=1; a[i-1] < 2*1e9; i++, j+=2)

        a[i]= a[i-1] + j, n=i;

       

    while(cin >> m){

        int i=1;

        for(i; i<=n; i++)

            if (a[i] > m) break;

        i--;

        solve(i);

    }

}