UVa : 574 (Sum It Up)


Title : Sum It Up

Link : http://uva.onlinejudge.org/external/5/574.html

Tricky Lines :

  1. A number can be used within a sum as many times as it appears in the list, and a single number counts as a sum.
  2. If n = 0 it signals the end of the input
  3. if there are no sums, output the line `NONE
  4. The numbers within each sum must appear in non-increasing order.
  5. all sums must be distinct; the same sum cannot appear twice

Analysis :

  1. check all possible combination, as there are only 2^12 combination possible.

Runtime : 0.020s

Solution :

// @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>
#define INT_MAX 2147483647
#define INT_MIN -2147483648
#define pi acos(-1.0)
#define N 1000000
#define LL long long
using namespace std;

int b [12 + 5];

void binary_conv (int i)
{
    memset (b, 0, sizeof (b));

    int index = 0;

    while ( i ) {
        b [index++] = i % 2;
        i /= 2;
    }

    reverse (b, b + 17);
}

int main ()
{
    int t, n;

    while ( scanf ("%d %d", &t, &n) ) {
        if ( n == 0 ) break;

        int n_arr [12 + 5];
        map <string, bool> printed_once;
        string save_sort [5000];
        int in_save = 0;

        for ( int i = 0; i < n; i++ ) scanf ("%d", &n_arr [i]);

        sort (n_arr, n_arr + n);

        int limit = 1 << n;

        printf ("Sums of %d:\n", t);
        bool none = true;

        for ( int i = limit - 1; i >= 1; i-- ) {
            binary_conv (i);
            int sum = 0;
            int plus = 0;

            for ( int j = 16; 16 - j < n; j-- )
                if ( b [j] ) { sum += n_arr [ n - (16 - j) - 1 ]; plus++; }

            string output = "";
            char token [20];

            if ( sum == t ) {
                for ( int j = 16; 16 - j < n; j-- ) {
                    if ( b [j] ) {
                        sprintf (token, "%d", n_arr [n - (16 - j) - 1]);
                        output += token;
                        if ( plus > 1 ) output += '+';
                        plus--;
                        none = false;
                    }
                }
                if ( printed_once [output] == false ) {
                    printed_once [output] = true;
                    save_sort [in_save++] = output;
                }
            }
        }

        if ( none ) printf ("NONE\n");
        else {
            sort (save_sort, save_sort + in_save);
            for ( int i = in_save - 1; i >= 0; i-- )
                cout << save_sort [i] << endl;
        }
    }

	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