UVa : 11569 (Lovely Hint)


  1. lovely string must be in ascending order to achieve the requirement
  2. one character can’t be use more than 1 time. so, “HELLO” and “HELO” are same
  3. i back-tracked every possible arrangement and get the result

// http://uva.onlinejudge.org/external/115/11569.html
// Runtime : 0.020s
// Tag : back-tracking

// @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 INT_MAX 2147483647
#define INT_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 Forv(i, sz) for ( size_t i = 0; i < sz.size (); i++ )
#define Set(a, s) memset (a, s, sizeof (a))

using namespace std;

string str;
char arr [30];
int ways [30];

void bktk (int at, int pos)
{
    if ( pos == str.size () ) { ways [at]++; return; }

    For (i, pos, str.size()) {
        if ( at ) {
        	int p = (arr [at - 1] - 'A' + 1) * 5;
        	int q = (str.at (i) - 'A' + 1) * 4;
            if ( p <= q ) { arr [at] = str.at (i); bktk (at + 1, i + 1); }
        }
        else { arr [at] = str [i]; bktk (at + 1, i + 1); }
    }
    ways [at]++;
}

int main ()
{
    int testCase;
    scanf ("%d", &testCase);
    getchar ();

    while ( testCase-- ) {
        char input [1000];
        gets (input);

        str = "";
        Set (ways, 0);

        for ( int i = 0; input [i]; i++ )
            if ( isupper (input [i]) ) str += input [i];

        sort (str.begin (), str.end ());
        string :: iterator it = unique (str.begin (), str.end ());
        str.resize (it - str.begin ());

        if ( str.size() == 0 ) { printf ("0 0\n"); continue; }

        bktk (0, 0);

        for ( int i = 29; i >= 0; i-- ) {
            if ( ways [i] ) { printf ("%d %d\n", i, ways [i]); break; }
        }

    }

	return 0;
}

// @END_OF_SOURCE_CODE

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