Spoj and UVa Solutions

11495 - Bubbles and Buckets

2012-06-06T03:08:00.000+05:30

Again a very simple problem, just count the no of inversions in each game instance if it's even second guy wins if it's odd the guy who starts the game (i.e. the first guy) wins.


//
//  main.cpp
//  11495 - Bubbles and Buckets
//
//  Created by Panks on 06/06/12.
//  Copyright (c) 2012 __MyCompanyName__. All rights reserved.
//

#include <iostream>
#include <cstdio>
#include <cstdlib>


unsigned long long int mergeSort(long long int arr[], long long int array_size);
unsigned long long int  _mergeSort(long long int arr[], long long int temp[], long long int left, long long int right);
unsigned long long int merge(long long int arr[], long long int temp[], long long int left, long long int mid, long long int right);

using namespace std;
int main (int argc, const char * argv[])
{
    long long int t,count, tmp;
    unsigned long long inv;
    long long int store[100000+1];
    while (scanf("%lld", &t)&&t) {
        count=0;
        tmp=t;
        while (t--) {
            scanf("%lld", &store[count]);
            count++;
        }
        inv=mergeSort(&store[0], tmp);
        if (inv%2==0) {
            cout<<"Carlos\n";
        }else{
            cout<<"Marcelo\n";
        }        
    }

    return 0;
}


unsigned long long mergeSort(long long int arr[], long long int array_size)
{
    long long int *temp = (long long int *)malloc(sizeof(long long int)*array_size);
    return _mergeSort(arr, temp, 0, array_size - 1);
}


unsigned long long _mergeSort(long long int arr[], long long int temp[], long long int left, long long int right)
{
    long long int mid;
    unsigned long long inv_count = 0;
    if (right > left)
    {

        mid = (right + left)/2;

        inv_count  = _mergeSort(arr, temp, left, mid);
        inv_count += _mergeSort(arr, temp, mid+1, right);
        
        inv_count += merge(arr, temp, left, mid+1, right);
    }
    return inv_count;
}

unsigned long long int merge(long long int arr[], long long int temp[], long long int left, long long int mid, long long int right)
{
    long long int i, j, k;
    unsigned long long int inv_count = 0;
    
    i = left; /* i is index for left subarray*/
    j = mid;  /* i is index for right subarray*/
    k = left; /* i is index for resultant merged subarray*/
    while ((i <= mid - 1) && (j <= right))
    {
        if (arr[i] <= arr[j])
        {
            temp[k++] = arr[i++];
        }
        else
        {
            temp[k++] = arr[j++];
            
            inv_count = inv_count + (mid - i);
        }
    }
    
    while (i <= mid - 1)
        temp[k++] = arr[i++];
    
    while (j <= right)
        temp[k++] = arr[j++];
    
    for (i=left; i <= right; i++)
        arr[i] = temp[i];
    
    return inv_count;
}

11462 - Age Sort

2012-06-06T03:05:00.000+05:30

Very simple problem, since the range of values is defined and is not large you can use a O(n) algo for sorting, but even inbuilt O(nlgn) would do.


//
//  main.cpp
//  11462 - Age Sort
//
//  Created by Panks on 06/06/12.
//  Copyright (c) 2012 __MyCompanyName__. All rights reserved.
//

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstdio>
using namespace std;
int main (int argc, const char * argv[])
{
    int t, tmp;
    vector<int> store;
    while (scanf("%d",&t)&&t) {
        while (t--) {
            scanf("%d", &tmp);
            store.push_back(tmp);
        }
        sort(store.begin(), store.end());
        for (int i=0; i<store.size(); i++) {
            printf("%d", store[i]);
            if (i!=store.size()-1) {
                printf(" ");
            }
        }
        printf("\n");
        store.clear();
        
    }
    return 0;
}

10810 - Ultra-QuickSort

2012-06-06T03:03:00.000+05:30

Print the no of inversions in each input. Since 'n' is large no of swaps required could be large, so make sure you are using 'unsigned long long' to store them. Though I have used them everywhere(I used find replace ;) ), but that is not required, elements can be stored in 'int'.


//
//  main.cpp
//  10810 - Ultra-QuickSort
//
//  Created by Panks on 06/06/12.
//  Copyright (c) 2012 __MyCompanyName__. All rights reserved.
//

#include <iostream>
#include <vector>
#include <cstdlib>
using namespace std;


unsigned long long int mergeSort(long long int arr[], long long int array_size);
unsigned long long int  _mergeSort(long long int arr[], long long int temp[], long long int left, long long int right);
unsigned long long int merge(long long int arr[], long long int temp[], long long int left, long long int mid, long long int right);

int main (int argc, const char * argv[])
{

    long long int t,tmp ;
    vector<long long int> store;
    cin>>t;
    while (t!=0) {
        store.clear();
        while (t--) {
            cin>>tmp;
            store.push_back(tmp);
        }
        cout<<mergeSort(&store[0], (int)store.size())<<endl;
        cin>>t;
        
    }
    
    return 0;
}







unsigned long long mergeSort(long long int arr[], long long int array_size)
{
    long long int *temp = (long long int *)malloc(sizeof(long long int)*array_size);
    return _mergeSort(arr, temp, 0, array_size - 1);
}

unsigned long long _mergeSort(long long int arr[], long long int temp[], long long int left, long long int right)
{
    long long int mid;
    unsigned long long inv_count = 0;
    if (right > left)
    {

        mid = (right + left)/2;

        inv_count  = _mergeSort(arr, temp, left, mid);
        inv_count += _mergeSort(arr, temp, mid+1, right);
        
        inv_count += merge(arr, temp, left, mid+1, right);
    }
    return inv_count;
}


unsigned long long int merge(long long int arr[], long long int temp[], long long int left, long long int mid, long long int right)
{
    long long int i, j, k;
    unsigned long long int inv_count = 0;
    
    i = left; /* i is index for left subarray*/
    j = mid;  /* i is index for right subarray*/
    k = left; /* i is index for resultant merged subarray*/
    while ((i <= mid - 1) && (j <= right))
    {
        if (arr[i] <= arr[j])
        {
            temp[k++] = arr[i++];
        }
        else
        {
            temp[k++] = arr[j++];
            
            inv_count = inv_count + (mid - i);
        }
    }
    

    while (i <= mid - 1)
        temp[k++] = arr[i++];
    

    while (j <= right)
        temp[k++] = arr[j++];
    
    for (i=left; i <= right; i++)
        arr[i] = temp[i];
    
    return inv_count;
}

612 - DNA Sorting

2012-06-06T02:58:00.000+05:30

Sort according to no. of inversions in array and print them back.


//
//  main.cpp
//  512 - DNA Sorting
//
//  Created by Panks on 05/06/12.
//  Copyright (c) 2012 __MyCompanyName__. All rights reserved.
//

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <map>
#include <cstdlib>
using namespace std;


int inv(string str);

int main (int argc, const char * argv[])
{
    int t,n ,m;
    string tmp;
    vector<pair<int, int> > store;
    vector<string> dna;
    cin>>t;
    while (t--) {
        store.clear();
        cin>>n>>m;
        while (m--) {
            cin>>tmp;
            dna.push_back(tmp);
            store.push_back(pair<int, int> (inv(tmp), (int)dna.size()-1));
        }

        sort(store.begin(), store.end());
        for (int i=0; i<store.size(); i++) {
            cout<<dna[store[i].second]<<endl;
        }
        
        if (t) {
            cout<<endl;
        }
    }
    return 0;
}

int inv(string str){
    int result=0;
    for (int i=0; i<str.size()-1; i++) {
        for (int j=i+1; j<str.size(); j++) {
            if (str[i]>str[j]) {
                result++;
            }
        }
    }
    return result;
}

299 - Train Swapping

2012-06-06T02:56:00.000+05:30

Just count the no. of inversion in array, using mergesort.


//
//  main.cpp
//  299 - Train Swapping
//
//  Created by Panks on 05/06/12.
//  Copyright (c) 2012 __MyCompanyName__. All rights reserved.
//

#include <iostream>
#include <vector>
#include <cstdlib>
using namespace std;
int mergeSort(int arr[], int array_size);
int  _mergeSort(int arr[], int temp[], int left, int right);
int merge(int arr[], int temp[], int left, int mid, int right);


int main (int argc, const char * argv[])
{
    int t,l,tmp,inv ;
    vector<int> store;
    cin>>t;
    while (t--) {
        inv=0;
        cin>>l;
        while (l--) {
            cin>>tmp;
            store.push_back(tmp);
        }
        inv=mergeSort(&store[0], (int)store.size());
        cout<<"Optimal train swapping takes "<<inv<<" swaps.\n";
        store.clear();
    }
    
    return 0;
}


int mergeSort(int arr[], int array_size)
{
    int *temp = (int *)malloc(sizeof(int)*array_size);
    return _mergeSort(arr, temp, 0, array_size - 1);
}

int _mergeSort(int arr[], int temp[], int left, int right)
{
    int mid, inv_count = 0;
    if (right > left)
    {

        mid = (right + left)/2;

        inv_count  = _mergeSort(arr, temp, left, mid);
        inv_count += _mergeSort(arr, temp, mid+1, right);
        
        inv_count += merge(arr, temp, left, mid+1, right);
    }
    return inv_count;
}

int merge(int arr[], int temp[], int left, int mid, int right)
{
    int i, j, k;
    int inv_count = 0;
    
    i = left; 
    j = mid;  
    k = left; 
    while ((i <= mid - 1) && (j <= right))
    {
        if (arr[i] <= arr[j])
        {
            temp[k++] = arr[i++];
        }
        else
        {
            temp[k++] = arr[j++];
            
            inv_count = inv_count + (mid - i);
        }
    }
    
    while (i <= mid - 1)
        temp[k++] = arr[i++];
    
    while (j <= right)
        temp[k++] = arr[j++];
    
    for (i=left; i <= right; i++)
        arr[i] = temp[i];
    
    return inv_count;
}

146 - ID Codes

2012-06-05T00:35:00.000+05:30


//
//  main.cpp
//  146 - ID Codes
//
//  Created by Panks on 31/05/12.
//  Copyright (c) 2012 __MyCompanyName__. All rights reserved.
//

#include <iostream>
#include <algorithm>
using namespace std;
int main (int argc, const char * argv[])
{
    string input, next;
    cin>>input;
    while (input.compare("#")) {
        next=input;
        next_permutation(input.begin(), input.end());
        if (!lexicographical_compare(input.begin(), input.end(), next.begin(), next.end())) {
            if (input.compare(next)) {
                cout<<input<<endl;
            }
            else{
                cout<<"No Successor"<<endl;
            }
        }else{
            cout<<"No Successor"<<endl;
        }
        cin>>input;
    }
    return 0;
}

11340 - Newspaper

2012-06-05T00:32:00.000+05:30


//
//  main.cpp
//  11340 - Newspaper
//
//  Created by Panks on 31/05/12.
//  Copyright (c) 2012 __MyCompanyName__. All rights reserved.
//

#include <iostream>
#include <map>
#include <cstdio>
using namespace std;
int main (int argc, const char * argv[])
{
    int t,in;
    double answer;
    char letter;
    int vals;
    string line;
    map<char, int> values; 
    cin>>t;
    while (t--) {
        
        answer=0;
        cin>>in;
        while (in--) {
            cin>>letter>>vals;
            values.insert(pair<char, int>(letter, vals));
        }
        cin>>in;
        getchar();
        while (in--) {
            getline(cin, line);
            for (int i=0; i<line.size() ; i++) {
                if (values[line[i]]) {
                    answer+=values[line[i]];
                }
            }
        }
        answer/=100;
        printf("%.2f$\n", answer);
        values.clear();
    }
    return 0;
}

10258 - Contest Scoreboard

2012-06-05T00:27:00.000+05:30

Remember, there is penalty of only '20' when it is Incorrect (I), and the penalty for a particular problem for a particular contentment is considered only if he/she submits the correct solution for it, and after that no penalty is accounted for that particular problem for that contestant.

and you can do better by making a better comparison function.


//
//  main.cpp
//  10258 - Contest Scoreboard
//
//  Created by Panks on 31/05/12.
//  Copyright (c) 2012 __MyCompanyName__. All rights reserved.
//

#include <iostream>
#include <algorithm>
#include <vector>
#include <sstream>
#include <cstdio>
using namespace std;

struct info {
    int id;
    int problems[12];
    int penalty[12];
    int tsolved;
    int time;
};

bool cmp(info a, info b);
bool cmp(info a, info b){
    if (a.tsolved<b.tsolved) {
        return false;
    }else if(a.tsolved>b.tsolved){
        return true;
    }else{
        if (a.penalty[11]<b.penalty[11]) {
            return true;
        }else if(a.penalty[11]>b.penalty[11]){
            return false;
        }else{
            return (a.id-b.id)<0;
        }
    }

}


int main (int argc, const char * argv[])
{
    vector<info> store;
    int t,contestant,problem,time;
    string L;
    string input;
    stringstream ss;
    cin>>t;
    getchar();
    info data;
    data.id=0; fill_n(data.problems,12, 0); 
    fill_n(data.penalty,12, 0); data.time=0, data.tsolved=0;;
    getchar();
    while (t--) {
        getline(cin,input);
        store.resize(101);
        fill_n(store.begin(), 101, data);
        
        while (input!="") {
            ss.str(input);
            ss>>contestant; ss>>problem; ss>>time; ss>>L;
            if (!L.compare("C")) {
                store[contestant].id=contestant;
                if (store[contestant].problems[problem]==0) {
                    store[contestant].problems[problem]=1;
                    store[contestant].penalty[problem]+=time;
                }
            }else if (!L.compare("I")) {
                store[contestant].id=contestant;
                if (store[contestant].problems[problem]==0) {
                    store[contestant].penalty[problem]+=20;
                }
            }else{                
                store[contestant].id=contestant;
            }
            getline(cin, input);
            ss.clear();
        }
        
        for (int i=0; i<store.size(); i++) {
            for (int j=0; j<10; j++) {
                if (store[i].problems[j]) {
                    store[i].tsolved++;
                    store[i].penalty[11]+=store[i].penalty[j];
                }
            }
            
        }
        
        sort(store.begin(), store.end(), cmp);
        for (int i=0; i<store.size(); i++) {
            if (store[i].id==0) {
                continue;
            }
            cout<<store[i].id<<" "<<store[i].tsolved<<" "<<store[i].penalty[11]<<endl;
        }
        
        if (t!=0) {
            cout<<endl;
        }
        store.clear();
        ss.clear();
        
    }
    return 0;
}

482 - Permutation Arrays

2012-06-03T03:09:00.000+05:30


//
//  main.cpp
//  482 - Permutation Arrays
//
//  Created by Panks on 30/05/12.
//  Copyright (c) 2012 __MyCompanyName__. All rights reserved.
//

#include <iostream>
#include <vector>
#include <string>
#include <sstream>
#include <cstdlib>
#include <cstdio>
#include <algorithm>
using namespace std;
int main (int argc, const char * argv[])
{
    int t, count=0;
    string line1, line2;
    int index;
    string value;
    vector<pair<int, string> > store;
    cin>>t;
    getchar();
    while (t--) {
        getchar();
        count++;
        getline(cin, line1);
        getline(cin, line2);
        stringstream ss1(line1), ss2(line2);
        while (ss1>>index) {
            ss2>>value;
            store.push_back(pair<int, string>(index, value));
        }
        sort(store.begin(), store.end());
        if (count>1) {
            cout<<endl;
        }
        for (int i=0; i<store.size(); i++) {
            cout<<store[i].second<<endl;
        } 
        
        store.clear();
    }
    return 0;
}

11498 - Division of Nlogonia

2012-06-02T22:24:00.002+05:30



//  main.cpp
//  11498 - Division of Nlogonia
//
//  Created by Panks on 29/05/12.
//  Copyright (c) 2012 __MyCompanyName__. All rights reserved.
//

#include <iostream>
using namespace std;
int main (int argc, const char * argv[])
{
    int k,n,m;
    int x,y;
    cin>>k;
    while (k!=0) {
        cin>>n>>m;
        while (k--) {
            cin>>x>>y;
            if (x==n||y==m) {
                cout<<"divisa\n";
                continue;
            }else{
                if (x<n) {
                    if (y<m) {
                        cout<<"SO\n";
                    }else{
                        cout<<"NO\n";
                    }
                    
                }else{
                    
                    if (y<m) {
                        cout<<"SE\n";
                    }else{
                        cout<<"NE\n";
                    }
                    
                }
            }
        }
        cin>>k;
    }
        
    return 0;
}

11340 - Newspaper

2012-06-02T22:16:00.002+05:30


//
//  main.cpp
//  11340 - Newspaper
//
//  Created by Panks on 31/05/12.
//  Copyright (c) 2012 __MyCompanyName__. All rights reserved.
//

#include <iostream>
#include <map>
#include <cstdio>
using namespace std;
int main (int argc, const char * argv[])
{

    int t,in;
    double answer;
    char letter;
    int vals;
    string line;
    map<char, int> values; 
    
    cin>>t;
    while (t--) {
        
        answer=0;
        cin>>in;
        while (in--) {
            cin>>letter>>vals;
            values.insert(pair<char, int>(letter, vals));
        }
        cin>>in;
        getchar();
        while (in--) {
            getline(cin, line);
            for (int i=0; i<line.size() ; i++) {
                if (values[line[i]]) {
                    answer+=values[line[i]];
                }
            }
        }
        answer/=100;
        printf("%.2f$\n", answer);
        
        values.clear();
        
    }
    return 0;
}

11150 - Cola

2012-06-02T21:48:00.002+05:30

Just scribe a little on paper, you would get it. ;)


//
//  main.cpp
//  11150 - Cola
//
//  Created by Panks on 29/05/12.
//  Copyright (c) 2012 __MyCompanyName__. All rights reserved.
//

#include <iostream>
using namespace std;
int main (int argc, const char * argv[])
{

    int a, tmp;
    while (cin>>a) {
        if (a==1||a==0) {
            cout<<a<<endl;
            continue;
        }
        tmp=a;
        a=a+a/2;
        a=a-a%3;
        cout<<tmp+(a/3)<<endl;
    }
    return 0;
}

11044 - Searching for Nessy

2012-06-02T21:47:00.002+05:30


//
//  main.cpp
//  11044 - Searching for Nessy
//
//  Created by Panks on 29/05/12.
//  Copyright (c) 2012 __MyCompanyName__. All rights reserved.
//

#include <iostream>
using namespace std;
int main (int argc, const char * argv[])
{

    int t;
    double a,b, froma, fromb;
    int ifroma, ifromb;
    cin>>t;
    while (t--) {
        cin>>a>>b;
        a-=2;
        b-=2;
        froma=a/3.0;
        fromb=b/3.0;
        
        if (froma-(int)froma!=0) {
            ifroma=(int)froma+1;
        }else{
            ifroma=(int)froma;
        }
        
        
        if (fromb-(int)fromb!=0) {
            ifromb=(int)fromb+1;
        }else{
            ifromb=(int)fromb;
        }
        
        cout<<ifroma*ifromb<<endl;
    }
    return 0;
}

10921 - Find the Telephone

2012-06-02T21:46:00.002+05:30


//
//  main.cpp
//  10921 - Find the Telephone
//
//  Created by Panks on 28/05/12.
//  Copyright (c) 2012 __MyCompanyName__. All rights reserved.
//

#include <iostream>
#include <algorithm>
using namespace std;


void doit(char a);
string *str=new string[8];
using namespace std;
int main (int argc, const char * argv[])
{
    
    str[0]="ABC", str[1]="DEF", str[2]="GHI", str[3]="JKL", str[4]="MNO", str[5]="PQRS", str[6]="TUV", str[7]="WXYZ";
    string input;
    while (getline(cin, input)){
        for_each(input.begin(), input.end(), doit);
        cout<<endl;
    }
    return 0;
}


void doit(char a){
    bool done=false;
    for (int i=0; i<8; i++) {
        if (count(str[i].begin(), str[i].end(), a)) {
            cout<<i+2;
            done=true;
        }
    }
    
    if (!done) {
        cout<<a;
    }
}

10812 - Beat the Spread!

2012-06-02T21:44:00.002+05:30


//
//  main.cpp
//  Problem D: Beat the Spread!
//  Created by Panks on 28/05/12.
//  Copyright (c) 2012 __MyCompanyName__. All rights reserved.
//

#include <iostream>
using namespace std;
int main (int argc, const char * argv[])
{

    int t, a, b;
    cin>>t;
    while (t--) {
        cin>>a>>b;
        if(a>=b&&a>=0&&b>=0&&((a+b)%2==0))
        {
            int c=(a+b)/2;
            cout<<c<<" "<<a-c<<endl;
            
        }else{
            cout<<"impossible\n";
        }
    }
    return 0;
}

10683 - The decadary watch

2012-06-02T21:42:00.002+05:30


//
//  main.cpp
//  10683 - The decadary watch
//  Created by Panks on 28/05/12.
//  Copyright (c) 2012 __MyCompanyName__. All rights reserved.
//

#include <iostream>
#include <sstream>
using namespace std;
long double mult = 10000000.0/8640000.0;
long long int secs1;
int ans;
string convertInt(int number);
string convertInt(int number)
{
    stringstream ss;    //create a stringstream
    ss << number;       //add number to the stream
    return ss.str();    //return a string with the contents of the stream
}

int main (int argc, const char * argv[])
{

    string input;
    int h1, m1, s1, c1, h2, m2, s2, c2;
    while (getline(cin, input)) {
        h1=(input[0]-'0')*10+(input[1]-'0');
        m1=(input[2]-'0')*10+(input[3]-'0');
        s1=(input[4]-'0')*10+(input[5]-'0');
        c1=(input[6]-'0')*10+(input[7]-'0');
        secs1=h1*360000+m1*6000+s1*100+c1;

        ans=secs1*mult;
        string tocheck=convertInt(ans);
        int len=7-(tocheck.size());
        while (len--) {
            cout<<'0';
        }

        cout<<ans<<endl;
    }
    return 0;
}

10420 - List of Conquests

2012-06-02T21:28:00.002+05:30


//
//  main.cpp
//  10420 - List of Conquests
//
//  Created by Panks on 28/05/12.
//  Copyright (c) 2012 __MyCompanyName__. All rights reserved.
//

#include <iostream>
#include <map>
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

map<string, int> store;
vector<string> onlyplace;
bool cmpit(pair<string, int> a);
bool cmpit(pair<string, int> a){
    return 0;
}

void printit(string place);
void printit(string place){

    cout<<place<<" "<<store[place]<<endl;
}
int main (int argc, const char * argv[])
{
    int t;
    cin>>t;
    getchar();
    while (t--) {
        string name, place;
        cin>>place;
        getchar();
        getline(cin, name);
        if (store[place]) {
            store[place]++;
        }else{
            onlyplace.push_back(place);
            store.insert(pair<string, int>(place, 100));
            store[place]++;
        }
    }

    sort(onlyplace.begin(), onlyplace.end());
    for_each(onlyplace.begin(), onlyplace.end(), printit);
    return 0;
}

10363 - Tic Tac Toe

2012-06-02T21:00:00.002+05:30


//
//  main.cpp
//  10363 - Tic Tac Toe
//
//  Created by Panks on 28/05/12.
//  Copyright (c) 2012 __MyCompanyName__. All rights reserved.
//

#include <iostream>
#include <algorithm>
#include <cstdio>
using namespace std;
int main (int argc, const char * argv[])
{
    
    // insert code here...
    int t;
    string row1, row2, row3;
    cin>>t;
    while (t--) {
        bool xwin=0;
        bool owin=0;
        getchar();
        getline(cin, row1);
        getline(cin, row2);
        getline(cin, row3);
        long int countx=0, counto=0;
        countx=count(row1.begin(), row1.end(), 'X')+count(row2.begin(), row2.end(), 'X')+count(row3.begin(), row3.end(), 'X');
        counto=count(row1.begin(), row1.end(), 'O')+count(row2.begin(), row2.end(), 'O')+count(row3.begin(), row3.end(), 'O');
        
        
        if (count(row1.begin(), row1.end(), 'X')==3||count(row2.begin(), row2.end(), 'X')==3||count(row3.begin(), row3.end(), 'X')==3) {
            xwin=true;
        }
        if ((row1[0]=='X'&&row2[0]=='X'&&row3[0]=='X') || (row1[1]=='X'&&row2[1]=='X'&&row3[1]=='X') || (row1[2]=='X'&&row2[2]=='X'&&row3[2]=='X')) {
            xwin=true;
        }
        if ((row1[2]=='X'&&row2[1]=='X'&&row3[0]=='X') || (row1[0]=='X'&&row2[1]=='X'&&row3[2]=='X')) {
            xwin=true;
        }   
        
        
        if (count(row1.begin(), row1.end(), 'O')==3||count(row2.begin(), row2.end(), 'O')==3||count(row3.begin(), row3.end(), 'O')==3) {
            owin=true;
        }
        if ((row1[0]=='O'&&row2[0]=='O'&&row3[0]=='O') || (row1[1]=='O'&&row2[1]=='O'&&row3[1]=='O') || (row1[2]=='O'&&row2[2]=='O'&&row3[2]=='O')) {
            owin=true;
        }
        if ((row1[2]=='O'&&row2[1]=='O'&&row3[0]=='O') || (row1[0]=='O'&&row2[1]=='O'&&row3[2]=='O')) {
            owin=true;
        } 
        
        
        if(countx>counto+1){
            cout<<"no\n";
        }else if (counto>countx) {
            cout<<"no\n";
        }else if(xwin==true && owin==true){
            cout<<"no\n";
        }else if(owin==true&&counto<countx){
            cout<<"no\n";
        }else if(xwin==true&&counto>=countx){
            cout<<"no\n";
        }else
            cout<<"yes\n";
    }
    return 0;
}

10281 - Average Speed

2012-06-02T20:26:00.002+05:30


//
//  main.cpp
//  10281 - Average Speed
//
//  Created by Panks on 27/05/12.
//  Copyright (c) 2012 __MyCompanyName__. All rights reserved.
//

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
double cspeed=0, tdistane=0;
int gh=0, gm=0, gs=0;
string input;


void updatevalues();
void updatevalues(){
    int h=0,m=0,s=0, speed=0;
    int i=0;
    while (input[i]!=':') {
        h=h*10+input[i]-'0';
        i++;
    }
    i++;
    while (input[i]!=':') {
        m=m*10+input[i]-'0';
        i++;
    }
    i++;
    while (input[i]!=' ') {
        s=s*10+input[i]-'0';
        i++;
    }
    i++;
    while (input[i]!='\0') {
        speed=speed*10+input[i]-'0';
        i++;
    }
    double time=(h-gh)+((m-gm)/60.0)+((s-gs)/3600.0);
    double dis=time*cspeed;
    tdistane=dis+tdistane;
    cspeed=speed;
    gh=h;
    gm=m;
    gs=s;
}



int main (int argc, const char * argv[])
{

    // insert code here...
    int h=0, m=0, s=0;
    while (getline(cin, input)) {
        if (count(input.begin(), input.end(), ' ')) {
            updatevalues();
        }else{
            int i=0;
            h=0; m=0; s=0;
            while (input[i]!=':') {
                h=h*10+input[i]-'0';
                i++;
            }
            i++;
            while (input[i]!=':') {
                m=m*10+input[i]-'0';
                i++;
            }
            i++;
            while (input[i]!='\0') {
                s=s*10+input[i]-'0';
                i++;
            }
            
            double dist=((h-gh)+((m-gm)/60.0)+((s-gs)/3600.0))*cspeed;
            double totaldis=tdistane+dist;
            printf("%s %.2f km\n", &input[0], totaldis);
            
            
        }
    }

}

10141 - Request for Proposal

2012-06-02T20:12:00.002+05:30


/* ******************************************* */
// \_/\_/\_/\_/---Coded by Panks---\_/\_/\_/\_/ //
/* ******************************************* */


// **********************Headers******************

//C headers
#include<cstdio>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<cstdio>
#include<ctime>
#include<cctype>
#include<cassert>
#include<climits>
#include<cerrno>
#include<cfloat>
#include<ciso646>
#include<clocale>
#include<csetjmp>
#include<csignal>
#include<cstdarg>
#include<cstddef>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<ctime>
#include<cwchar>
#include<cwctype>

//containers
#include<vector>
#include<list>
#include<map>
#include<queue>
#include<deque>
#include<set>
#include<complex>
#include<string>
#include<stack>
#include<bitset>
#include<istream>
#include<valarray>

//IOs
#include<iostream>
#include<sstream>
#include<iomanip>
#include<fstream>
#include<exception>
#include<ios>
#include<iosfwd>
#include<ostream>
#include<iterator>
#include<stdexcept>
#include<streambuf>

//algorithm & miscellaneous
#include<algorithm>
#include<functional>
#include<numeric>
#include<utility>
#include<limits>
#include<locale>
#include<memory>
#include<new>
/* ********************************************** */


////////////////////SHORTHANDS\\\\\\\\\\\\\\\\\\\\\

#define ull unsigned long long
#define ll long long

#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define REP(i,n) FOR(i,0,n-1)

#define FORD(i,a,b) for(int i=a;i>=b;i--)
#define REPD(i,n) FOR(i,n-1,0)

#define testcase(t) int t;scanf("%d",&t);while(t--)
#define s(x) scanf("%d",&x)
#define sl(x) scanf("%lld",&x)
#define ss(x) scanf("%s",x)

#define p(x) printf("%d",x)
#define pl(x) printf("%lld",x)
#define ps(x) printf("%s",x)

#define pn(x) printf("%d\n",x)
#define pln(x) printf("%lld\n",x)
#define psn(x) printf("%s\n",x)

#define all(c) c.begin(),c.end() 
//////////////////////////\\\\\\\\\\\\\\\\\\\\\\\\\\


// ---------------Fast IO using getchar-------------- \\
// will accept values 9-digits in int and 19-digits in long long on my system


int getint(){
    int c = 'a';
    while (!(c >= '0' && c <= '9') && c != '-')
        c = getchar();
    int c2;
    if (c != '-')
        c2 = c;
    else
        c2 = '0';
    int res = 0;
    while((c2 >= '0' && c2 <= '9')){
        res = (res << 3) + (res << 1) + (c2 - '0');
        
        c2 = getchar();
    }
    return res * (c == '-' ? -1 : 1);
}
// ------------------------------------------------- \\

//------------------Actual Code--------------------- \\

using namespace std;

int main (int argc, const char * argv[])
{

    int n, p,count=0;
    string req, name, togive;
    double price, minprice;
    int met, maxmet;
    cin>>n>>p;
    while (n!=0) {
        count++;
        getchar();
        while (n--) {
            getline(cin, req);
        }
        met=maxmet=0;
        price=minprice=0;
        while (p--) {
            getline(cin, name);
            cin>>price>>met;
            if (met>maxmet) {
                maxmet=met;
                minprice=price;
                togive=name;
            }else if(met==maxmet){
                if (price<minprice) {
                    maxmet=met;
                    minprice=price;
                    togive=name;
                }
            }
                        
            getchar();
            while (met--) {
                getline(cin, req);
            }
        }
        
        if (count>1) {
            cout<<endl;
        }
        cout<<"RFP #"<<count<<endl<<togive<<endl;
        
        
        cin>>n>>p;
    }
    return 0;
}

10082 - WERTYU

2012-06-02T20:08:00.002+05:30

You can combine all the arrays in one and can do a lot better :) , I was just rushing through when I coded these.



//
//  main.cpp
//  WERTY
//
//  Created by Panks on 27/05/12.
//  Copyright (c) 2012 __MyCompanyName__. All rights reserved.
//

#include <iostream>
#include <algorithm>
#include <string>
using namespace std;



#define ull unsigned long long
#define ll long long

#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define REP(i,n) FOR(i,0,n-1)

#define FORD(i,a,b) for(int i=a;i>=b;i--)
#define REPD(i,n) FOR(i,n-1,0)

#define testcase(t) int t;scanf("%d",&t);while(t--)
#define s(x) scanf("%d",&x)
#define sl(x) scanf("%lld",&x)
#define ss(x) scanf("%s",x)

#define p(x) printf("%d",x)
#define pl(x) printf("%lld",x)
#define ps(x) printf("%s",x)

#define pn(x) printf("%d\n",x)
#define pln(x) printf("%lld\n",x)
#define psn(x) printf("%s\n",x)

#define all(c) c.begin(),c.end() 




string row1="`1234567890-=", row2="QWERTYUIOP[]\?", row3="ASDFGHJKL;'", row4="ZXCVBNM,./<";

void replaceit(char a);
void replaceit(char a){
    if (a==' ') {
        cout<<" ";
    }
    string::iterator pos;
    
    if(count(row1.begin(), row1.end(), a)){
        pos=find(all(row1), a);
        pos--;
        cout<<*pos;
    }else if(count(row2.begin(), row2.end(), a)){
        pos=find(all(row2), a);
        pos--;

        cout<<*pos;
    }else if(count(row3.begin(), row3.end(), a)){
        pos=find(all(row3), a);
        pos--;

        cout<<*pos;    
    }else if(count(row4.begin(), row4.end(), a)){
        pos=find(all(row4), a);
        pos--;
        cout<<*pos;    
    }
}

int main (int argc, const char * argv[])
{
    string input;
    while(getline(cin, input)){
        for_each(input.begin(), input.end(), replaceit);
        cout<<endl;
    }
    
}

941 - Permutations

2012-06-02T20:03:00.002+05:30



/* ******************************************* */
// \_/\_/\_/\_/---Coded by Panks---\_/\_/\_/\_/ //
/* ******************************************* */


// **********************Headers******************

//C headers
#include<cstdio>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<cstdio>
#include<ctime>
#include<cctype>
#include<cassert>
#include<climits>
#include<cerrno>
#include<cfloat>
#include<ciso646>
#include<clocale>
#include<csetjmp>
#include<csignal>
#include<cstdarg>
#include<cstddef>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<ctime>
#include<cwchar>
#include<cwctype>

//containers
#include<vector>
#include<list>
#include<map>
#include<queue>
#include<deque>
#include<set>
#include<complex>
#include<string>
#include<stack>
#include<bitset>
#include<istream>
#include<valarray>

//IOs
#include<iostream>
#include<sstream>
#include<iomanip>
#include<fstream>
#include<exception>
#include<ios>
#include<iosfwd>
#include<ostream>
#include<iterator>
#include<stdexcept>
#include<streambuf>

//algorithm & miscellaneous
#include<algorithm>
#include<functional>
#include<numeric>
#include<utility>
#include<limits>
#include<locale>
#include<memory>
#include<new>
/* ********************************************** */


////////////////////SHORTHANDS\\\\\\\\\\\\\\\\\\\\\

#define ull unsigned long long
#define ll long long

#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define REP(i,n) FOR(i,0,n-1)

#define FORD(i,a,b) for(int i=a;i>=b;i--)
#define REPD(i,n) FOR(i,n-1,0)

#define testcase(t) int t;scanf("%d",&t);while(t--)
#define s(x) scanf("%d",&x)
#define sl(x) scanf("%lld",&x)
#define ss(x) scanf("%s",x)

#define p(x) printf("%d",x)
#define pl(x) printf("%lld",x)
#define ps(x) printf("%s",x)

#define pn(x) printf("%d\n",x)
#define pln(x) printf("%lld\n",x)
#define psn(x) printf("%s\n",x)

#define all(c) c.begin(),c.end() 
//////////////////////////\\\\\\\\\\\\\\\\\\\\\\\\\\


// ---------------Fast IO using getchar-------------- \\
// will accept values 9-digits in int and 19-digits in long long on my system

int getint();
int getint(){
    int c = 'a';
    while (!(c >= '0' && c <= '9') && c != '-')
        c = getchar();
    int c2;
    if (c != '-')
        c2 = c;
    else
        c2 = '0';
    int res = 0;
    while((c2 >= '0' && c2 <= '9')){
        res = (res << 3) + (res << 1) + (c2 - '0');
        
        c2 = getchar();
    }
    return res * (c == '-' ? -1 : 1);
}
// ------------------------------------------------- \\

//------------------Actual Code--------------------- \\


using namespace std;

bool compit (char a, char b);
bool compit (char a, char b){
    return int(a)<int(b);
}

long int factorial(long int n);
long int factorial(long int n){
    int a=1;
    while (n!=1) {
        a*=n;
        n--;
    }
    return a;
}

int main(){
    
    int t;
    string input="";
    long int no, fact;
    cin>>t;
    while (t--) {
        cin>>input>>no;
        sort(all(input), compit);
        int a=0;
        fact=1;
        int long factor=factorial(input.size());
        no=no%factor;
        
        if (no!=0) {
            while (fact<=no) {
                a++;
                fact=fact*a;
            }
            fact/=a;
            a--;
            
        }else{
            fact=0;
            a=0;
            
        }
        
        string ans="";
        while (a--) {
            ans+=char(int(no/fact)+48);
            no=no%fact; 
            fact/=(a+1);
        }
        ans+='0';
        
        int long diff=input.size()-ans.size();
        if (diff<0) {
            diff=0;
        }
        while (diff--) {
            ans='0'+ans;
        }
        
        
        long int len=input.size();
        int i=0;
        len--;
        string final="";
        while (len--) {
            final+=input[ans[i]-48];
            input.erase(input.begin()+ans[i]-48);
            i++;
        }
        cout<<final+input<<endl;
        
    }
    
}

739 - Soundex Indexing

2012-06-02T19:59:00.002+05:30


//
//  main.cpp
//  Soundex Indexing
//
//  Created by Panks on 24/05/12.
//  Copyright (c) 2012 __MyCompanyName__. All rights reserved.
//

#include <iostream>
using namespace std;



int getcode(char a);

int main (int argc, const char * argv[])
{

    string input;
    bool done=false;
    int i;
    string code, ans;
    cout<<"         NAME                     SOUNDEX CODE"<<endl;
    while (cin>>input) {
        done=false;
        i=0;
        code="";
        while (i<input.length()&&!done) {
            if(i>0&&(input[i]=='A'||input[i]=='E'||input[i]=='I'||input[i]=='O'||input[i]=='U'||input[i]=='Y'||input[i]=='W'||input[i]=='H'||getcode(input[i])==getcode(input[i-1]))){
                i++;
                continue;
            }
            if (code.length()==4) {
                done=true;
                continue;
            }else if(code.length()>0&&code.length()<4){
                code=code+char(getcode(input[i])+48);
                i++;
            }else{
                code=input[i];
                i++;
            }
        }
        if (code.length()!=4) {
            while (code.length()!=4) {
                code=code+'0';
            }
        }
        ans="";
        ans="         "+input;
        while (ans.length()!=34) {
            ans=ans+' ';
        }
        ans=ans+code;
        cout<<ans<<endl;
    }
    cout<<"                   END OF OUTPUT"<<endl;
    return 0;
}

int getcode(char a){
    if(a=='B'||a=='P'||a=='F'||a=='V'){
        return 1;
    }else if(a=='D'||a=='T'){
        return 3;
    }else if(a=='L'){
        return 4;
    }else if(a=='M'||a=='N'){
        return 5;
    }else if(a=='R'){
        return 6;
    }else if(a=='C'||a=='S'||a=='K'||a=='G'||a=='J'||a=='Q'||a=='X'||a=='Z'){
        return 2;
    }else{
        return -1;
    }
}

661 - Blowing Fuses

2012-06-02T19:54:00.002+05:30



//
//  main.cpp
//  Blowing Fuses
//
//  Created by Panks on 23/05/12.
//  Copyright (c) 2012 __MyCompanyName__. All rights reserved.
//

#include <iostream>
#include <vector>
using namespace std;
int main (int argc, const char * argv[])
{
    

    int n,m,c;
    int getit;
    int count=0;

    int* devpowr=new int[20];
    bool* devstat=new bool[20];
    
    cin>>n>>m>>c;
    while (n!=0) {
        count++;
        for (int i=0; i<n; i++) {
            cin>>getit;
            devpowr[i]=getit;
            devstat[i]=false;
        }
        int total=0,mtotal=0;
        int tmp;
        for (int i=1; i<=m; i++) {
            cin>>tmp;
            tmp--;
            if(devstat[tmp]==false){
                devstat[tmp]=true;
                total+=devpowr[tmp];
                mtotal=max(mtotal, total);
                if(total>c){
                    cout<<"Sequence "<<count<<"\nFuse was blown.\n\n";
                    for(int r = i + 1; r <= m; r++) {
                        cin >> tmp;}
                
                    break;
                }
            }else{
                devstat[tmp]=false;
                total-=devpowr[tmp];
            }
            
            if(i==m){
                cout<<"Sequence "<<count<<"\nFuse was not blown.\nMaximal power consumption was "<<mtotal<<" amperes.\n\n";
                break;
            }
        }
        cin>>n>>m>>c;
    }
    return 0;
}

573 - The Snail

2012-06-02T19:52:00.002+05:30



//
//  main.cpp
//  The Snail
//
//  Created by Panks on 23/05/12.
//  Copyright (c) 2012 __MyCompanyName__. All rights reserved.
//

#include <iostream>
#include <cmath>
using namespace std;
int main (int argc, const char * argv[])
{
    
    
    double h, u, d;
    int f;
    cin>>h>>u>>d>>f;
    
    while (h!=0) {
        double tmp=0;
        int count=0;
        double df=u*f/100.0;
        while (1) {
            tmp=tmp+u;
            count++;
            if(tmp>h){
                cout<<"success on day "<<count<<endl;
                break;
            }
            tmp-=d;
            if(tmp<0&&count>0){
                cout<<"failure on day "<<count<<endl;
                break;
            }
            u=u-df;
            if (u<0) {
                u=0;
            }
        }
        
        cin>>h>>u>>d>>f;
    }
    
    return 0;
}