[090812] Problem E - Crabbles

Post date: Sep 9, 2012 1:08:46 AM

Problem: http://acm.student.cs.uwaterloo.ca/~acm00/060225/E.html

Here is the solution that we discussed on the whiteboard today. In particular, it incorporates the use of bit masks, which are very important tools for a lot of problems (especially when we get into DP).

#include <iostream> #include <set> #include <algorithm> // Includes the sort function using namespace std; int main() { int N; cin >> N; // Dictionary size set<string> dictionary; for (int i=0; i < N; i++) { string s; cin >> s; sort(s.begin(), s.end()); // Sorts the letters in the string alphabetically dictionary.insert(s); // sets are automatically sorted } int M; cin >> M; // Number of hands for (int i=0; i < M; i++) { // For each hand int P; cin >> P; // Number of tiles char tiles[P]; int values[P]; for (int j=0; j < P; j++) { cin >> tiles[j] >> values[j]; // The tile and its value } int maxScore = 0; // Go through every possible word you can make for (int mask=1; mask < (1<<P); mask++) { // 1<<P is the same as 2^P string wordToCheck; int wordScore = 0; for (int k=0; k < P; k++) { // For each of the P tiles // check to see if it is a 1 in the mask. // This is nonzero (specifically, equals 1<<k) // if the kth binary digit from the right is a 1, // where k=0 is the right-most digit. if (mask & (1<<k)) { wordToCheck += tiles[k]; wordScore += values[k]; } } sort(wordToCheck.begin(), wordToCheck.end()); if (dictionary.count(wordToCheck)) { // The word is in the dictionary maxScore = max(maxScore, wordScore); } } // End for each possible word cout << maxScore << endl; } // End for each hand }