uva11495 Bubbles and Buckets

The counting inversion can be done in O(n^2) with the naive algorithm.
But it will not suffice. So we need (nlogn). Counting the inversion in merge function of merge sort is good idea too do this. while merging if second array is having small element then the elements remaning in first array all have conflict with this element so add that and thats it.
or

create binary search tree ,step by step go on inserting the elememnts, and with every node keep track of nodes that are right side of current node and
while inserting increment  the current nodes right count if inserted element falls to right (that is it is greater than current node element).and else if falls to left(that means inserted element is smaller than current node and there are right_count_of_current_node no of element greater than inserted element that are before inserted element so add that count) add right count to answer.

 Solution with first strategy:

UVA 696 How Many Knights

Easily find pattern after two,three test cases.  
But really interesting to see when either rows are 2 or columns are 2.

  

#include <algorithm>
#include <iostream>
#include <iterator>
#include <numeric>
#include <sstream>
#include <fstream>
#include <cassert>
#include <climits>
#include <cstdlib>
#include <cstring>
#include <string>
#include <cstdio>
#include <vector>
#include <bitset>
#include <cmath>
#include <queue>
#include <deque>
#include <stack>
#include <list>
#include <map>
#include <set>
using namespace std;

#define fi(i,a,b) for(int i=(int)a;i<=(int)b;i++)
#define fd(i,a,b) for(int i=(int)a;i>=(int)b;i--)
#define rep(i,n)  for(int i=0;i<n;i++)
//stl
#define sz(a) int((a).size())
#define pb push_back
#define all(c) ((c).begin(),(c).end())
#define tr(c,i) for(typeof((c).begin()) i = (c).begin(); i != (c).end(); i++)
#define present(c,x) ((c).find(x) != (c).end())
#define cpresent(c,x) (find(all(c),x) != (c).end())

typedef long long ll;
typedef pair<int,int> ii;
typedef pair<string,int> si;
typedef pair<int,ii> iii;
typedef vector<si> vsi;
typedef vector<ii> vii;
typedef vector<int> vi;
typedef vector<char> vc;
typedef vector<string> vs;
typedef map <string,vs> msvs;
typedef map <string,int> msi;
typedef map <string,string> mss;
#define INF 1000000000

int main()
{
   
        while(1)
        {
            int r,c;
            scanf("%d %d",&r,&c);
            if(r==0 && c==0)
            break;
   
            else if(r==1)
            printf("%d knights may be placed on a 1 row %d column board.\n",c,c);
           
            else if(c==1)
            printf("%d knights may be placed on a %d row 1 column board.\n",r,r);

      
            else if(r==2 || c==2)
            {
                int r1=r,c1=c;
                int mul=r*c,fb,y;
                fb=mul/4;
                y=mul%4;
                if(fb%2==0)
                {
                    printf("%d knights may be placed on a %d row %d column board.\n",fb*2+y,r,c);

                  
                }
                else
                {
                    int a2=ceil((float)fb/2);
                    printf("%d knights may be placed on a %d row %d column board.\n",a2*4,r,c);

                }
                  
              
            }
          
            else
            {
                if(c%2==0)
                {
                    printf("%d knights may be placed on a %d row %d column board.\n",(c/2)*r,r,c);
              
                }
                else
                {
                    int a1=(r/2)*c;
                    int a2=ceil((float)c/2);
                    if(r%2==0)
                    printf("%d knights may be placed on a %d row %d column board.\n",a1,r,c);
                    else
                    printf("%d knights may be placed on a %d row %d column board.\n",a1+a2,r,c);
              
                }
            }  
        }


    return 0;
}

494 Kindergarten Counting Game

Very is problem simple use gets in while loop until end of file and any character other than alphabate is delimiter

10363 Tic Tac Toe

This is easy problem but there is one catch multiple winning are allowed(as it is not mentioned in problem) , i tried both ways and got AC on commenting that condition (line : 121 in following code)

10812 Beat the Spread!

but note test case if sum=0 and differece = 0 so if d > s then continue ; (and not d>=s)

10420 List of Conquests

very easy problem
just note use of map,sort() and getchar()

573 The Snail

This is very simple problem but to avoid complications of floating point just multiply with the 100