Uva278 — Chess

PROBLEM link SUBMIT link

Prerequisite — basic knowledge of chess

Theory Difficulty: easy

Coding Difficulty: trivial

Algorithms Used: math

Solution Description:

Note — here we have assumed that n >=3 and m> =3 which is working in this case,
for others you have to handle cases separately.(example if n==1 || m==1, ans= m and n respectively for knight)

For rooks, just put them in a diagonal line:

x....
.x...
..x..
...x.

So for rooks, the answer is min(m,n).

Queens get arranged in a sort of staggered shape:

x....
..x..
....x
.x...

The answer is the same: min(m,n).

Reason — In N- Queens problem we always have solution for n>3 (we are assuming that n>3, which always be)

Knights can be arranged in a alternating grid pattern:

x.x.x   =>(n+1)/2
.x.x.   =>n/2
x.x.x
.x.x.

So, ans = ((m+1)/2)*((n+1)/2)+(m/2)*(n/2) which can be written like follows.
clearly, half will be used and other half will be left vacant, we have to look at cases of both even and odd n & m
and this works out to (m*n+1)/2 or ceil(m*n/2.0), because if both are odd then it will be upper bound.

Kings are arranged as knights, but only on alternating lines:

x.x.x
.....
x.x.x
.....

And the answer is ((m+1)/2) * ((n+1)/2).

Code C/C++

#include <cstdlib>
#include <algorithm>
#include <iostream>
#include <cmath>
using namespace std;
int main() {
    int t;
    cin>>t;
    while(t--){
        char c;
        int m,n;
        cin>>c>>m>>n;
        int ans=0;
        switch(c){
            case 'r'://rook
                ans=min(m,n);
                break;
            case 'k'://knight
                ans=ceil(m*n/2.0);
                break;
            case 'Q'://queen
                ans=min(m,n);
                break;
            case 'K'://king
                ans=ceil(m/2.0)*ceil(n/2.0);
        }
        cout<<ans<<endl;
    }
    
    return 0;
}
#happy_coding #codebrace
If you find something wrong or have any question about the solution then comment down below, you can also contact us using  contact form.