Home » 国际竞赛 » Details

USACO 2022 February Contest, Bronze Problem 3. Blocks

Category: 国际竞赛, 计算机国际竞赛 Date: 2022年7月5日下午5:24

USACO 2022 February Contest, Bronze Problem 3. Blocks

In an effort to improve her vocabulary, Bessie the cow has obtained a set of four wooden blocks, each one a cube with a letter of the alphabet written on each of its six sides. She is learning how to spell by arranging the blocks in a row so the letters on top of the blocks spell words.

Given the letters on each of Bessie's four blocks, and a list of words she would like to spell, please determine which of words on her list she will be able to spell successfully using the blocks.

INPUT FORMAT (input arrives from the terminal / stdin):

The first line of input contains $N$ ( $1 \leq N \leq 10$ ), the number of words that Bessie would like to spell. The next four lines each contain a string with six uppercase letters, representing the letters on the six sides of one of Bessie's blocks. The next $N$ lines contain the $N$ words Bessie would like to spell. Each of these is between 1 and 4 uppercase letters long.

OUTPUT FORMAT (print output to the terminal / stdout):

For each word on Bessie's list, output YES if she is able to spell it using the blocks and NO otherwise.

SAMPLE INPUT:

6
MOOOOO
OOOOOO
ABCDEF
UVWXYZ
COW
MOO
ZOO
MOVE
CODE
FARM

SAMPLE OUTPUT:

YES
NO
YES
YES
NO
NO

In this example, Bessie can spell COW, ZOO, and MOVE. Sadly, she cannot spell MOO, since the only block with an M cannot also be used for an O. She cannot spell FARM since there is no block with a letter R. She cannot spell CODE since the C, D, and E all belong to the same block.

Problem credits: Brian Dean

USACO 2022 February Contest, Bronze Problem 3. Blocks 题解(翰林国际教育提供，仅供参考)

题解请注册或登录查看

[/hide]

(Analysis by Nick Wu)

For a fixed ordering of four blocks, there are $6^{4} = 1296$ different words that can be formed. There are $4 \times 3 \times 2 \times 1 = 24$ ways to order the four blocks, for a total of 31104 four-letter different arrangements that can be formed.

Doing the same math for one-letter, two-letter, and three-letter combinations, we can show that there are 24 one-letter arrangements, 432 two-letter arrangements, and 5184 three-letter arrangements. This is small enough that we can precompute all possible words that can be formed.

To precompute all possible words, we need to iterate over all possible orderings of blocks and letters. We can then throw all of these words into a set to make it easy to check if the word is present.

Danny Mittal's Java code picks blocks one at a time and generates letters as the blocks are fixed in place.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashSet;
import java.util.Set;
 
public class Blocks {
    static final char[][] blocks = new char[4][];
    static final Set<String> makeable = new HashSet<>();
 
    static void recur(int usedMask, String word) {
        makeable.add(word);
        for (int j = 0; j < 4; j++) {
            if ((usedMask & (1 << j)) == 0) {
                for (char letter : blocks[j]) {
                    recur(usedMask + (1 << j), word + letter);
                }
            }
        }
    }
 
    public static void main(String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(in.readLine());
        for (int j = 0; j < 4; j++) {
            blocks[j] = in.readLine().toCharArray();
        }
        recur(0, "");
        StringBuilder out = new StringBuilder();
        for (int j = 0; j < n; j++) {
            if (makeable.contains(in.readLine())) {
                out.append("YES");
            } else {
                out.append("NO");
            }
            out.append('\n');
        }
        System.out.print(out);
    }
}

My Python 3 code fixes the ordering of the blocks first and then loops over letters to generate all possible words.

def solve():
    n = int(input())
    l = [input() for _ in range(4)]
    words = set()
    for a in range(4):
        for b in range(4):
            if a in [b]:
                continue
            for c in range(4):
                if c in [a, b]:
                    continue
                for d in range(4):
                    if d in [a, b, c]:
                        continue
                    for l1 in l[a]:
                        words.add(l1)
                        for l2 in l[b]:
                            words.add(l1+l2)
                            for l3 in l[c]:
                                words.add(l1+l2+l3)
                                for l4 in l[d]:
                                    words.add(l1+l2+l3+l4)
    for _ in range(n):
        print("YES" if input() in words else "NO")
 
solve()

Note that you don't need to precompute all possible words. Benjamin Qi's C++ code tries all possible orderings of blocks and sees if a given ordering can yield the letters in order.

#include <bits/stdc++.h>
using namespace std;
 
bool solve(array<string, 4> blocks) {
	string word;
	cin >> word;
	do {
		bool ok = true;
		for(int i = 0; i < word.size(); i++) {
			if(find(blocks[i].begin(), blocks[i].end(), word[i]) == blocks[i].end()) ok = false;
		}
		if (ok) return true;
	} while (next_permutation(blocks.begin(), blocks.end()));
	return false;
}
 
int main() {
	int TC; cin >> TC;
	array<string, 4> blocks;
	for(int i = 0; i < 4; i++) cin >> blocks[i];
	sort(blocks.begin(), blocks.end());
	for(int i = 0; i < TC; i++) {
		bool b = solve(blocks);
		if (b) cout << "YES\n";
		else cout << "NO\n";
	}
}

[/hide]