UVa : 11538 (Chess Queen)


1. if row == 1 then output: column * (column – 1)

2. if the queen can attack only horizontally then output: row * column * (column – 1)

3. similarly, if the queen can attack only vertically then output: column * row * (row – 1)

4. if we do not consider diagonal attack
output = row * column * (column – 1) + column * row * (row – 1)

5. number of cells in a diagonal path will increase by time
after some time it will decrease

6. for example
minimum = min ( row, column )
maximum = max ( row, column )

number of cells in a diagonal path,
will increase from 1 to minimum
will remain same from minimum + 1 to maximum
will decrease, same as increase

7. after find out the diagonal attack, multiplied by 2, as there are 2 diagonals

8. use unsigned long long


// http://uva.onlinejudge.org/external/115/11538.html
// Rumtime: 1.384s
// Tag: math, ad-hoc

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

#include <iostream>
#include <algorithm>
#define LL unsigned long long
using namespace std;

int main() {
	LL n, m;

	while ( cin >> n >> m ) {
		if ( n == 0 && m == 0 ) break;

		LL res = 0;
		LL mini = min (m, n);
		LL maxi = max (m, n);
		LL cnt = 1;

		while ( cnt != mini ) {
			res += ((cnt - 1) * cnt);
			res += ((cnt - 1) * cnt);
			cnt++;
			maxi--;
		}


		cnt *= (cnt - 1);
		res += (maxi * cnt);

		res *= 2; // both diagonal
		res += (n * (m - 1) * m + m * (n - 1) * n); // for horizontal & vertical

		cout << res << endl;

	}
	return 0;
}
Advertisements

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