UVa: 10025 (The ? 1 ? 2 ? … ? n = k problem)



// http://uva.onlinejudge.org/external/100/10025.html
// Runtime: 0.012s
// Tag: gotcha, math

//============================================================================
// Name        : UVa_10025.cpp
// Author      : Shahab
// Version     :
// Copyright   : Your copyright notice
// Description : Hello World in C++, Ansi-style
//============================================================================

#include <iostream>
#include <cstdio>
#include <cmath>
#define LL long long
using namespace std;

int main() {
	int testCase;
	scanf ("%d", &testCase);
	bool blank = false;

	while ( testCase-- ) {
		LL k;
		cin >> k;

		k = k < 0 ? k * -1: k;

		LL n = (LL) sqrt (k * 2);

		if ( k % 2 == 1 )
		{
			LL res = (n * (n + 1)) / 2;
			while ( res < k || res % 2 == 0 ) {
				n++;
				res = (n * (n + 1)) / 2;
			}
		}
		else
		{
			LL res = (n * (n + 1)) / 2;
			while ( res < k || res % 2 == 1 ) {
				n++;
				res = (n * (n + 1)) / 2;
			}
		}

		if ( blank ) printf ("\n"); blank = true;
		n = k == 0 ? 3 : n;
		cout << n << endl;
	}
	return 0;
}

One thought on “UVa: 10025 (The ? 1 ? 2 ? … ? n = k problem)

  1. Input:
    10
    0
    1
    -1
    2
    -2
    1000000000
    -1000000000
    325685965
    231254125
    -96585457
    Output:
    3
    
    1
    
    1
    
    3
    
    3
    
    44723
    
    44723
    
    25522
    
    21506
    
    13901
    

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s