UVa: 941 (Permutations)



// https://uva.onlinejudge.org/external/9/p941.pdf
// Runtime: 0.162s
// tag: permutation, recursive, math

// @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 <ctime>
#include <sstream>

#define Inf 2147483647
#define Pi acos(-1.0)
#define N 10000 + 10
#define LL long long
#define F(i, n) for( int i = (0); i < (n); i++ )
#define Fs(i, sz) for( size_t i = 0; i < sz.size (); i++ )
#define Set(a, s) memset(a, s, sizeof (a))
inline LL Power(int b, int p) { LL r = 1; for ( int i = 1; i <= p; i++ ) r *= b; return r; }

using namespace std;

LL fact(int len) {
    if (len == 0 || len == 1) return 1;
    LL ret = 1;
    for ( int i = 2; i <= len; i++ ) {
        ret *= i;
    }
    return ret;
}

string recur(string inp, int len, LL target) {
    if (len == 1) return inp;
    LL unit = fact(len - 1);
    int extractedCharPos = (int) ((target - 1) / unit);
    char extractedChar = inp [extractedCharPos];
    inp.erase(inp.begin() + extractedCharPos);
    return extractedChar + recur(inp, len - 1, target % unit == 0 ? unit : target % unit);
}

int main ()
{
    int testCases;

    scanf ("%d", &testCases);

    while (testCases--) {
        string input;
        LL target;

        cin >> input >> target;

        sort(input.begin(), input.end());

        cout << recur(input, (int) input.size(), target  + 1) << endl;

    }


    return 0;
}

// @END_OF_SOURCE_CODE

Advertisements

UVa: 11947 (Cancer or Scorpio)


Input:
2
04230004
04232004

Accepted Output:
1 01/28/0005 aquarius
2 01/28/2005 aquarius


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

#define Inf 2147483647
#define Pi acos(-1.0)
#define N 1000000
#define LL long long
#define F(i, n) for( int i = (0); i < (n); i++ )
#define Fs(i, sz) for( size_t i = 0; i < sz.size (); i++ )
#define Set(a, s) memset(a, s, sizeof (a))
inline LL Power(int b, int p) { LL r = 1; for ( int i = 1; i <= p; i++ ) r *= b; return r; }

using namespace std;

int dayInMonths [] = {31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};

bool isLeapYear(int year) {
    if (year % 400 == 0) return true;
    if (year % 100 == 0) return false;
    if (year % 4 == 0) return true;
    return false;
}


int countDays(int day, int month, int year) {

    int counter = 0;

    for ( int i = 1; i < year; i++ ) {
        counter += (isLeapYear(i) ? 366 : 365);
    }

    for ( int i = 1; i < month; i++ ) {
        counter += dayInMonths [i - 1];
    }

    counter += day;

    if (month > 2 && isLeapYear(year)) counter++;

    return counter;
}

void printZodiacSign(int date, int month) {

    struct node {
        char const *sign;
        int startMonth;
        int startDate;
        int endMonth;
        int endDate;

        node () {}

        node(char const *s, int a, int b, int c, int d) {
            this->sign = s;
            this->startMonth = a;
            this->startDate = b;
            this->endMonth = c;
            this->endDate = d;
        }
    } n [12];

    n [0] = node("aquarius", 1, 21, 2, 19);
    n [1] = node("pisces", 2, 20, 3, 20);
    n [2] = node("aries", 3, 21, 4, 20);
    n [3] = node("taurus", 4, 21, 5, 21);
    n [4] = node("gemini", 5, 22, 6, 21);
    n [5] = node("cancer", 6, 22, 7, 22);
    n [6] = node("leo", 7, 23, 8, 21);
    n [7] = node("virgo", 8, 22, 9, 23);
    n [8] = node("libra", 9, 24, 10, 23);
    n [9] = node("scorpio", 10, 24, 11, 22);
    n [10] = node("sagittarius", 11, 23, 12, 22);
    n [11] = node("capricorn", 12, 23, 1, 20);

    for ( int i = 0; i < 12; i++ ) {
        if (month == n [i].startMonth) {
            if (date >= n [i].startDate) { printf ("%s\n", n [i].sign); break; }

        } else if (month == n [i].endMonth) {
            if (date <= n [i].endDate) { printf ("%s\n", n [i].sign); break; }
        }
    }
}

void printOutput(int days) {

    int year = 1;
    int month = 1;

    while(days >= 365) {
        days -= (isLeapYear(year) ? 366 : 365);

        if (days <= 0) {
            days += (isLeapYear(year) ? 366 : 365);
            break;
        }

        year++;
    }

    if (days) {

        if (isLeapYear(year)) dayInMonths [1]++;

        while (days > dayInMonths [month - 1]) {
            days -= dayInMonths [month - 1];
            month++;
        }
    }

    printf ("%02d/%02d/%04d ", month, days, year);

    printZodiacSign(days, month);

}

int digit(char c) {
    return c - 48;
}


int main ()
{
    int testCases;

    scanf ("%d", &testCases);

    int cases = 0;

    while (testCases--) {
        char input [8 + 10];
        scanf ("%s", input);

        dayInMonths [1] = 28;

        int totalNumberOfDays = countDays(digit (input [2]) * 10 + digit (input [3]),
                digit (input [0]) * 10 + digit (input [1]),
                digit (input [4]) * 1000 + digit (input [5]) * 100 + digit (input [6]) * 10 + digit (input [7]));

        printf ("%d ", ++cases);

        printOutput(totalNumberOfDays + 40 * 7);
    }

    return 0;
}

// @END_OF_SOURCE_CODE

UVa: 893 (Y3K Problem)



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

#define Inf 2147483647
#define Pi acos(-1.0)
#define N 1000000
#define LL long long
#define F(i, n) for( int i = (0); i < (n); i++ )
#define Fs(i, sz) for( size_t i = 0; i < sz.size (); i++ )
#define Set(a, s) memset(a, s, sizeof (a))
inline LL Power(int b, int p) { LL r = 1; for ( int i = 1; i <= p; i++ ) r *= b; return r; }

using namespace std;

int dayInMonths [] = {31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};

bool isLeapYear(int year) {
    if (year % 400 == 0) return true;
    if (year % 100 == 0) return false;
    if (year % 4 == 0) return true;
    return false;
}


int countDays(int day, int month, int year) {

    int counter = 0;

    for ( int i = 1; i < year; i++ ) {
        counter += (isLeapYear(i) ? 366 : 365);
    }

    for ( int i = 1; i < month; i++ ) {
        counter += dayInMonths [i - 1];
    }

    counter += day;

    if (month > 2 && isLeapYear(year)) counter++;

    return counter;
}

void printOutput(int days) {

    int year = 1;
    int month = 1;

    while(days >= 365) {
        days -= (isLeapYear(year) ? 366 : 365);

        if (days <= 0) {
            days += (isLeapYear(year) ? 366 : 365);
            break;
        }

        year++;
    }

    if (days) {

        if (isLeapYear(year)) dayInMonths [1]++;

        while (days > dayInMonths [month - 1]) {
            days -= dayInMonths [month - 1];
            month++;
        }
    }

    printf ("%d %d %d\n", days, month, year);

}

int main ()
{
    int futureDays;
    int day;
    int month;
    int year;

    while (scanf ("%d %d %d %d", &futureDays, &day, &month, &year)) {
        if ( futureDays == 0 && day == 0 && month == 0 && year == 0 ) break;

        dayInMonths [1] = 28;

        int totalNumberOfDays = countDays(day, month, year);
//        printf ("days: %d\n", totalNumberOfDays);
        totalNumberOfDays += futureDays;
        printOutput(totalNumberOfDays);
    }

    return 0;
}

// @END_OF_SOURCE_CODE

UVa : 10141 (Request for Proposal)



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

#define Inf 2147483647
#define Pi acos(-1.0)
#define N 1000000
#define LL long long
#define F(i, n) for( int i = (0); i < (n); i++ )
#define Fs(i, sz) for( size_t i = 0; i < sz.size (); i++ )
#define Set(a, s) memset(a, s, sizeof (a))
inline LL Power(int b, int p) { LL r = 1; for ( int i = 1; i <= p; i++ ) r *= b; return r; }

using namespace std;

struct node {
    char companyName [80 + 20];
    int compliance;
    int price;
    int r;
} a [10000];

bool cmp(node p, node q) {

    // greater compliance should come first
    if (p.compliance > q.compliance) return true;

    if (p.compliance == q.compliance) {
        // lower price should come first
        if (p.price < q.price) return true;
    }

    return false;
}

int main ()
{
    int n;
    int p;

    bool blank = false;

    int cases = 0;

    while ( scanf ("%d %d", &n, &p) != EOF ) {
        getchar();

        if ( n == 0 && p == 0 ) break;

        char itemName [80 + 20];

        // don't need this input data
        F(i, n) {
            gets(itemName);
        }

        double price;

        F(i, p) {
            gets(a [i].companyName);
            scanf ("%lf %d", &price, &a [i].r);

            // keeping the price integer
            a [i].price = (int) (price * 100);
            getchar();

            // keeping the compliance integer
            a [i].compliance = (a [i].r * N) / n;

            // don't need this input data
            F(j, a [i].r) {
                gets(itemName);
            }
        }

        sort(a, a + p, cmp);

        if (blank) printf ("\n");
        blank = true;

        printf ("RFP #%d\n%s\n", ++cases, a [0].companyName);
    }

    return 0;
}

// @END_OF_SOURCE_CODE

UVa: 247 (Calling Circles)



// link: http://uva.onlinejudge.org/external/2/247.html
// runtime: 0.045s
// tag: SCC

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

#define Inf 2147483647
#define Pi acos(-1.0)
#define N 100
#define LL long long
#define F(i, n) for( int i = (0); i < (n); i++ )
#define Fs(i, sz) for( size_t i = 0; i < sz.size (); i++ )
#define Set(a, s) memset(a, s, sizeof (a))
inline LL Power(int b, int p) { LL r = 1; for ( int i = 1; i <= p; i++ ) r *= b; return r; }

using namespace std;

map<string, int> names;
vector<string> rNames;

int namesLen = 0;

vector <int> edges [N];
vector <int> rEdges [N];    // reversed edges
vector <int> sortedNode;

bool vis [N];

int comp [N];               // component number of a node

int cases = 0;
bool blank = false;

int n, m;

void reset ()
{
    for ( int i = 0; i < N; i++ ) {
        edges [i].clear();
        rEdges [i].clear();
    }

    sortedNode.clear();
    names.clear();
    rNames.clear();

    namesLen = 0;
    memset (vis, false, sizeof vis);
}

void dfs1 (int x)
{
    vis [x] = true;

    for ( size_t u = 0; u < edges [x].size(); u++ ) {
        if ( !vis [edges [x] [u]] )
            dfs1(edges [x] [u]);
    }

    sortedNode.push_back(x);
}

void dfs2 (int x, int c)
{
    vis [x] = false;

    comp [x] = c;

    for ( size_t u = 0; u < rEdges [x].size(); u++ ) {
        if ( vis [rEdges [x] [u]] )
            dfs2(rEdges [x] [u], c);
    }
}

void assignNumber(string s)
{
    if (!names [s]) {
        ++namesLen;
        names [s] = namesLen;
        rNames.push_back(s);
    }
}

void printOutput(int compLen)
{
    if (blank) printf ("\n");
    blank = true;

    printf ("Calling circles for data set %d:\n", ++cases);

    bool space;

    for (int i = 1; i <= compLen; i++ ) {

        space = false;

        F(j, n) {
            if (comp [j + 1] == i) {

                if (space) printf (", ");
                space = true;

                cout << rNames[j];
            }
        }

        printf ("\n");
    }
}

int main ()
{
    while (scanf ("%d %d", &n, &m)) {

        if ( n == 0 && m == 0 ) break;

        reset();

        string name1, name2;

        F(i, m) {
            cin >> name1 >> name2;

            assignNumber(name1);
            assignNumber(name2);

            edges [names [name1]].push_back(names [name2]);
            rEdges [names [name2]].push_back(names [name1]);
        }

        F(i, namesLen) {
            if (!vis [i + 1]) {
                dfs1(i + 1);
            }
        }

        int compId = 0;

        for ( int i = sortedNode.size() - 1; i >= 0; i-- ) {
            if ( vis [sortedNode [i]] )
                dfs2(sortedNode [i], ++compId);
        }

        printOutput(compId);

    }

    return 0;
}

// @END_OF_SOURCE_CODE

UVa: 12372 (Packing for Holiday)



// link: http://uva.onlinejudge.org/external/123/12372.html
// Runtime: 0.012s

#include <cstdio>

using namespace std;

int main ()
{
    int testCases;

    scanf ("%d", &testCases);

    int cases = 0;

    while ( testCases-- ) {

        int l, w, h;

        scanf ("%d %d %d", &l, &w, &h);

        printf ("Case %d: ", ++cases);

        if (l <= 20 && w <= 20 && h <= 20) printf ("good");
        else printf ("bad");

        printf ("\n");
    }


}

UVa: 11942 (Lumberjack Sequencing)



// link: http://uva.onlinejudge.org/external/119/11942.html
// Runtime: 0.009s

#include <cstdio>


using namespace std;

int main ()
{

    int testCases;

    scanf ("%d", &testCases);

    printf ("Lumberjacks:\n");

    while ( testCases-- ) {

        int lumberjack [10 + 2];

        for ( int i = 0; i < 10; i++ ) {
            scanf ("%d", &lumberjack [i]);
        }

        bool isBig = true;

        if (lumberjack [0] > lumberjack [1]) isBig = false;

        bool ordered = true;

        if (isBig) {

            for ( int i = 1; i < 10; i++ ) {
                if (lumberjack [i] < lumberjack [i - 1]) ordered = false;
            }

        } else {

            for ( int i = 1; i < 10; i++ ) {
                if (lumberjack [i] > lumberjack [i - 1]) ordered = false;
            }
        }

        if (ordered)
            printf ("Ordered\n");
        else
            printf ("Unordered\n");

    }

    return 0;
}