UVa : 10670 (Work Reduction)



// http://uva.onlinejudge.org/external/106/10670.html
// Runtime: 0.016s
// Tag: Greedy

/* 
 * File:   main.cpp
 * Author: shahab
 * Created on April 7, 2011, 11:46 PM
 */

// @BEGIN_OF_SOURCE_CODE

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <string>
#include <cctype>
#include <stack>
#include <queue>
#include <list>
#include <vector>
#include <map>
#include <sstream>
#include <cmath>
#include <bitset>
#include <utility>
#include <set>
#include <numeric>

#define INF_MAX 2147483647
#define INF_MIN -2147483647
#define pi acos(-1.0)
#define N 1000000
#define LL long long

#define For(i, a, b) for( int i = (a); i < (b); i++ )
#define Fors(i, sz) for( size_t i = 0; i < sz.size (); i++ )
#define Fore(it, x) for(typeof (x.begin()) it = x.begin(); it != x.end (); it++)
#define Set(a, s) memset(a, s, sizeof (a))
#define Read(r) freopen(r, "r", stdin)
#define Write(w) freopen(w, "w", stdout)

using namespace std;

struct agency {
    char name [20];
    int oneUnitCost;
    int makeItHalfCost;
    int netCost;
} a [100 + 10];

bool cmp (agency p, agency q)
{
    if ( p.netCost < q.netCost ) return true;
    if ( p.netCost == q.netCost && strcmp (p.name, q.name) < 0 ) return true;
    return false;
}

int main(int argc, char** argv)
{
    int testCase;
    scanf ("%d", &testCase);
    int cases = 0;

    while ( testCase-- ) {
        int n, m, l;
        scanf ("%d %d %d", &n, &m, &l); getchar ();

        For (i, 0, l) {
            char inp [100]; gets (inp);
            int j = 0;
            while ( inp [j] != ':' ) a [i].name [j] = inp [j++];
            a [i].name [j] = 0;
            j++;
            char num [20]; int k = 0;
            while ( inp [j] != ',' ) num [k++] = inp [j++];
            num [k] = 0;
            a [i].oneUnitCost = atoi (num);
            j++;
            k = 0;
            while ( inp [j] ) num [k++] = inp [j++];
            num [k] = 0;
            a [i].makeItHalfCost = atoi (num);
        }

        For (i, 0, l) {
            int tmp_n = n;
            int cost = 0;
            while ( tmp_n != m ) {
                if ( tmp_n / 2 < m ) { cost += (a [i].oneUnitCost * (tmp_n - m)); tmp_n = m; }
                else {
                    int diff = tmp_n - (tmp_n / 2);
                    if ( diff * a [i].oneUnitCost > a [i].makeItHalfCost ) cost += a [i].makeItHalfCost;
                    else cost += (diff * a [i].oneUnitCost);
                    tmp_n /= 2;
                }
            }
            a [i].netCost = cost;
        }

        sort (a, a + l, cmp);

        printf ("Case %d\n", ++cases);
        For (i, 0, l) printf ("%s %d\n", a [i].name, a [i].netCost);
    }

    return 0;
}

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