Spoj and UVa Solutions

Wednesday, June 6, 2012

11495 - Bubbles and Buckets

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

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;
}

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

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

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;
}

Tuesday, June 5, 2012

146 - ID Codes


//
//  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


//
//  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;
}