Skip to Content
CTRL K

Block Game

Análisis oficial (Java) 

Explicación

Usamos un arreglo de frecuencias para llevar la cantidad mínima de bloques necesarios para cada letra. Para cada par de palabras, contamos las ocurrencias de cada letra en ambas palabras.

Como solo podemos ver un lado del bloque a la vez, tomamos la mayor de las dos frecuencias de cada letra y la sumamos al conteo total. Por último, después de procesar todos los pares, imprimimos el arreglo de frecuencias, que representa la cantidad total de bloques necesarios para cada letra.

Implementación

Complejidad temporal: O(NS)\mathcal{O}(NS), donde SS es la longitud máxima de un string.

#include <fstream>
#include <iostream>
#include <string>
#include <vector>
 
using std::cout;
using std::endl;
using std::string;
using std::vector;
 
/**
 * @return An array of length 26, containing the frequency
 * of each character in the given string.
 */
vector<int> count_freq(string s) {
	vector<int> freq(26);
	for (char c : s) { freq[c - 'a']++; }
	return freq;
}
 
int main() {
	std::ifstream read("blocks.in");
	int n;
	read >> n;
	vector<std::pair<string, string>> words(n);
	for (auto &[w1, w2] : words) { read >> w1 >> w2; }
 
	vector<int> max_blocks(26);
	for (const auto &[w1, w2] : words) {
		vector<int> freq1 = count_freq(w1);
		vector<int> freq2 = count_freq(w2);
		for (int c = 0; c < 26; c++) { max_blocks[c] += std::max(freq1[c], freq2[c]); }
	}
 
	std::ofstream written("blocks.out");
	for (int i : max_blocks) { written << i << '\n'; }
}
import java.io.*;
import java.util.*;
 
public class Blocks {
	public static void main(String[] args) throws IOException {
		Kattio io = new Kattio("blocks");
		int n = io.nextInt();
		String[][] words = new String[n][];
		for (int i = 0; i < n; i++) { words[i] = new String[] {io.next(), io.next()}; }
 
		int[] maxBlocks = new int[26];
		for (String[] w : words) {
			int[] freq1 = countFreq(w[0]);
			int[] freq2 = countFreq(w[1]);
			for (int c = 0; c < 26; c++) {
				maxBlocks[c] += Math.max(freq1[c], freq2[c]);
			}
		}
 
		for (int i : maxBlocks) { io.println(i); }
		io.close();
	}
 
	/**
	 * @return An array of length 26, containing the frequency
	 * of each character in the given string.
	 */
	static int[] countFreq(String s) {
		int[] freq = new int[26];
		for (int i = 0; i < s.length(); i++) { freq[s.charAt(i) - 'a']++; }
		return freq;
	}
 
	// CodeSnip{Kattio}
}
from typing import List
 
 
def count_freq(s: str) -> List[int]:
	"""
	:return: An array of length 26, containing the frequency
	of each character in the given string.
	"""
	freq = [0] * 26
	for c in s:
		freq[ord(c) - ord("a")] += 1
	return freq
 
 
with open("blocks.in") as read:
	n = int(read.readline())
	words = [read.readline().split() for _ in range(n)]
 
max_blocks = [0] * 26
for w1, w2 in words:
	freq1, freq2 = count_freq(w1), count_freq(w2)
	for c in range(26):
		max_blocks[c] += max(freq1[c], freq2[c])
 
with open("blocks.out", "w") as written:
	for i in max_blocks:
		print(i, file=written)
Fundamentos