UVa : 12034 (Race)



// http://uva.onlinejudge.org/external/120/12034.html
// Runtime: 0.016s
// Tag: Dp

// @BEGIN_OF_SOURCE_CODE

#include <iostream>
#include <cstdio>
#include <algorithm>

#define LL long long

using namespace std;

LL res [1000 + 5];

void preCalc ()
{
    res [0] = 1;
    res [1] = 1;    // when n = 1, res = 1
    res [2] = 3;    // when n = 2, res = 3
    res [3] = 13;

    LL numOfZeros [1000 + 5];
    // numOfZeros [5] = number of binary numbers contain 5 zeros in a particular bit
    for ( int i = 0; i < 1005; i++ ) numOfZeros [i] = 1;

    numOfZeros [0] = 1;
    numOfZeros [1] = 4;
    numOfZeros [2] = 6;
    numOfZeros [3] = 4;

    for ( int i = 4; i <= 1000; i++ ) {
        LL val = 0;
        for ( int j = i - 1; j >= 0; j-- ) {
            val += (numOfZeros [j] * res [j]) % 10056;
            val %= 10056;
        }

        res [i] = val;

        for ( int j = i; j >= 1; j-- ) {
            numOfZeros [j] += numOfZeros [j - 1];
            numOfZeros [j] %= 10056;
        }
    }
}

int main ()
{
    preCalc();

    int testCase; scanf ("%d", &testCase);
    int cases = 0;

    while ( testCase-- ) {
            int n; scanf ("%d", &n);
            printf ("Case %d: %lld\n", ++cases, res [n]);

    }

    return 0;
}

// @END_OF_SOURCE_CODE
Advertisements

3 thoughts on “UVa : 12034 (Race)

  1. can you “Briefly” explain what you have done on this code? i mean the process of the solution. i can’t understood what is the importance of the array you have used (numofZeros). thanks in advance.

  2. ya i understand .. basically this idea is a bit complex .. let me try to make it clearer
    first of all, take an example of four horses
    how many ways, four horses can secure first place?
    count the ways in binary

    0000 -> invalid state
    0001 -> 4th horse place first, others are 2nd/3rd/4th we dont care
    0010 -> 3rd horse place first, others … we dont care
    0011 -> both 3rd and 4th horse place first
    0100 -> 2nd horse place first



    1111 -> all horses place first
    ____________________________________

    take the example, 0001 -> 4th horse place first
    we don’t know the position of other horses
    but we do know, 3 horses can end up race in 13 different ways
    we can use this value to calculate the 4 horses case

    for example,
    if a horse place first in 3 horses case
    then we can think of as, it place 2nd in 4 horses case .. because we already know which horse in first in 4 horses case

    so, we know 3 information
    1 horse can end up race in 1 ways
    2 horses can end up race in 3 ways
    3 horses can end up race in 13 ways

    int ans_for_4_horses_case = 0;

    we need to go through every possible case

    0001 -> how many ways we can solve this case?
    ans: in 13 ways …
    first 3 horses end up race in 13 ways and 4th horse place first
    ans_for_4_horses_case += 13;

    0010 -> how many ways we can solve this case?
    ans: 13 ways again
    horse1, horse2 and horse4 end up race in 13 ways .. and horse3 place 1st
    ans_for_4_horses_case += 13;

    0011 -> ans_for_4_horses_case += 3;
    0100 -> ans_for_4_horses_case += 13;
    0101 -> ans_for_4_horses_case += 3;
    0110 -> ans_for_4_horses_case += 3;
    0111 -> ans_for_4_horses_case += 1;
    1000 -> ans_for_4_horses_case += 13;
    1001 -> ans_for_4_horses_case += 3;
    1010 -> ans_for_4_horses_case += 3;
    1011 -> ans_for_4_horses_case += 1;
    1100 -> ans_for_4_horses_case += 3;
    1101 -> ans_for_4_horses_case += 1;
    1110 -> ans_for_4_horses_case += 1;
    1111 -> ans_for_4_horses_case += 1;

    print (ans_for_4_horses_case);
    75

    so, this is my basic idea .. now you can code it in your own way
    if this thing still blur to you, you can post your comment again .. thanks 🙂

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