Moo Language

Explicación

El editorial oficial cubre un enfoque lineal, pero el cuadrático alcanza para el puntaje completo.

Este problema es bastante enrevesado. La forma de pensarlo es fijar qué queremos dejar como constante, y luego ver cómo se pueden definir las demás cosas en términos de las que ya fijamos.

En este caso, las constantes sobre las que hacemos fuerza bruta son la cantidad de verbos transitivos e intransitivos, que llamaré TVs e ITVs para abreviar. La razón intuitiva es que cada oración, sin contar las conjunciones, tiene exactamente un verbo. Así, si sabemos cuántos verbos vamos a usar, también podemos saber cuántos sustantivos, comas, etc. vamos a usar.

Los TVs y los ITVs necesitan dos y un sustantivo respectivamente, así que primero hay que comprobar si tenemos suficientes sustantivos. Si usamos una cantidad no nula de TVs, podemos usar comas para agregar sustantivos al final de una oración con TV.

También intentamos usar tantas conjunciones como sea posible; si hay $s$ oraciones, podemos usar como máximo $\left\lfloor\frac{s}{2}\right\rfloor$ conjunciones, ya que cada oración se puede unir a lo sumo una vez.

El resto es formateo; no se necesitan trucos algorítmicos.

Implementación

Complejidad temporal: $\mathcal{O}(N^2)$

C++JavaPython


#include <algorithm>
#include <iostream>
#include <map>
#include <vector>
 
using namespace std;
 
int main() {
	int test_num;
	cin >> test_num;
	for (int t = 0; t < test_num; t++) {
		int word_num, comma_num, period_num;
		cin >> word_num >> comma_num >> period_num;
		map<string, vector<string>> words{{"noun", {}},
		                                  {"transitive-verb", {}},
		                                  {"intransitive-verb", {}},
		                                  {"conjunction", {}}};
		for (int w = 0; w < word_num; w++) {
			string token, type;
			cin >> token >> type;
			words[type].push_back(token);
		}
 
		int max_size = 0;  // La mayor cantidad de palabras que podemos usar
		// Junto con cuántos TVs/ITVs producen ese tamaño máximo
		int best_tv = 0;
		int best_itv = 0;
		const vector<string> &nouns = words["noun"];  // solo un atajo
		int max_verbs = period_num + min(period_num, (int)words["conjunction"].size());
		// Probar todas las combinaciones de verbos transitivos/intransitivos
		for (int tv = 0; tv <= words["transitive-verb"].size(); tv++) {
			for (int itv = 0; itv <= words["intransitive-verb"].size(); itv++) {
				int nouns_left = nouns.size() - itv - 2 * tv;
				if (nouns_left < 0 || tv + itv > max_verbs) { break; }
 
				// Intentar usar tantas conjunciones como sea posible
				int conj_used = min((int)words["conjunction"].size(), (tv + itv) / 2);
				// Si se usó un verbo transitivo, poner sustantivos hasta que se acaben las comas
				int extra = tv > 0 ? min(comma_num, nouns_left) : 0;
				int total = 2 * itv + 3 * tv + extra + conj_used;
 
				if (total > max_size) {
					max_size = total;
					best_tv = tv;
					best_itv = itv;
				}
			}
		}
 
		// Construir todas las frases iniciales (n + itv o n + tv + n)
		int noun_at = 0;
		vector<string> phrases;
		for (int i = 0; i < best_itv; i++) {
			string itv = words["intransitive-verb"][i];
			string noun = nouns[noun_at++];
			phrases.push_back(noun + " " + itv);
		}
		for (int i = 0; i < best_tv; i++) {
			string tv = words["transitive-verb"][i];
			string noun1 = nouns[noun_at++];
			string noun2 = nouns[noun_at++];
			phrases.push_back(noun1 + " " + tv + " " + noun2);
		}
		// Agregar tantos sustantivos como sea posible al final de una oración con tv
		if (best_tv > 0) {
			string &last = phrases.back();
			for (int c = 0; c < comma_num && noun_at < nouns.size(); c++) {
				last.append(", ").append(nouns[noun_at++]);
			}
		}
 
		// Unir todas las oraciones que podamos usando conjunciones
		int phrase_at = 0;
		vector<string> sentences;
		for (string conj : words["conjunction"]) {
			if (phrase_at + 1 >= phrases.size()) { break; }
			string first = phrases[phrase_at++];
			string second = phrases[phrase_at++];
			sentences.push_back(first + " " + conj + " " + second);
		}
		sentences.insert(sentences.end(), phrases.begin() + phrase_at, phrases.end());
 
		cout << max_size << endl;
		string res = "";
		for (const string &s : sentences) { res += s + ". "; }
		if (!res.empty()) { res.pop_back(); }
		cout << res << '\n';
	}
}


import java.io.*;
import java.util.*;
 
public class MooLanguage {
	public static void main(String[] args) throws IOException {
		BufferedReader read = new BufferedReader(new InputStreamReader(System.in));
		int testNum = Integer.parseInt(read.readLine());
		for (int t = 0; t < testNum; t++) {
			StringTokenizer initial = new StringTokenizer(read.readLine());
			int wordNum = Integer.parseInt(initial.nextToken());
			int commaNum = Integer.parseInt(initial.nextToken());
			int periodNum = Integer.parseInt(initial.nextToken());
			Map<String, List<String>> words = new HashMap<>() {
				{
					put("noun", new ArrayList<>());
					put("transitive-verb", new ArrayList<>());
					put("intransitive-verb", new ArrayList<>());
					put("conjunction", new ArrayList<>());
				}
			};
			for (int w = 0; w < wordNum; w++) {
				StringTokenizer word = new StringTokenizer(read.readLine());
				String token = word.nextToken();
				String type = word.nextToken();
				words.get(type).add(token);
			}
 
			int maxSize = 0;  // La mayor cantidad de palabras que podemos usar
			// Junto con cuántos TVs/ITVs producen ese tamaño máximo
			int bestTV = 0;
			int bestITV = 0;
			final List<String> nouns = words.get("noun");  // solo un atajo
			int maxVerbs =
			    periodNum + Math.min(periodNum, words.get("conjunction").size());
			// Probar todas las combinaciones de verbos transitivos/intransitivos
			for (int tv = 0; tv <= words.get("transitive-verb").size(); tv++) {
				for (int itv = 0; itv <= words.get("intransitive-verb").size(); itv++) {
					int nounsLeft = nouns.size() - itv - 2 * tv;
					if (nounsLeft < 0 || tv + itv > maxVerbs) { break; }
 
					// Intentar usar tantas conjunciones como sea posible
					int conjUsed =
					    Math.min(words.get("conjunction").size(), (tv + itv) / 2);
					// Si se usó un verbo transitivo, poner sustantivos hasta que se
					// acaben las comas
					int extra = tv > 0 ? Math.min(commaNum, nounsLeft) : 0;
					int total = 2 * itv + 3 * tv + extra + conjUsed;
 
					if (total > maxSize) {
						maxSize = total;
						bestTV = tv;
						bestITV = itv;
					}
				}
			}
 
			// Construir todas las frases iniciales (n + itv o n + tv + n)
			int nounAt = 0;
			List<String> phrases = new ArrayList<>();
			for (int i = 0; i < bestITV; i++) {
				String itv = words.get("intransitive-verb").get(i);
				String noun = nouns.get(nounAt++);
				phrases.add(noun + " " + itv);
			}
			for (int i = 0; i < bestTV; i++) {
				String tv = words.get("transitive-verb").get(i);
				String noun1 = nouns.get(nounAt++);
				String noun2 = nouns.get(nounAt++);
				phrases.add(noun1 + " " + tv + " " + noun2);
			}
			// Agregar tantos sustantivos como sea posible al final de una oración con tv
			if (bestTV > 0) {
				StringBuilder last = new StringBuilder(phrases.get(phrases.size() - 1));
				for (int c = 0; c < commaNum && nounAt < nouns.size(); c++) {
					last.append(", ").append(nouns.get(nounAt++));
				}
				phrases.set(phrases.size() - 1, last.toString());
			}
 
			// Unir todas las oraciones que podamos usando conjunciones
			int phraseAt = 0;
			List<String> sentences = new ArrayList<>();
			for (String conj : words.get("conjunction")) {
				if (phraseAt + 1 >= phrases.size()) { break; }
				String first = phrases.get(phraseAt++);
				String second = phrases.get(phraseAt++);
				sentences.add(first + " " + conj + " " + second);
			}
			sentences.addAll(phrases.subList(phraseAt, phrases.size()));
 
			System.out.println(maxSize);
			String res = String.join(". ", sentences);
			res += res.isEmpty() ? "" : ".";
			System.out.println(res);
		}
	}
}


for _ in range(int(input())):
	word_num, comma_num, period_num = [int(i) for i in input().split()]
	words = {
		"noun": [],
		"transitive-verb": [],
		"intransitive-verb": [],
		"conjunction": [],
	}
	for _ in range(word_num):
		token, type_ = input().split()
		words[type_].append(token)
 
	max_size = 0  # La mayor cantidad de palabras que podemos usar
	# Junto con cuántos TVs/ITVs producen ese tamaño máximo
	best_tv = 0
	best_itv = 0
	nouns = words["noun"]  # solo un atajo
	max_verbs = period_num + min(period_num, len(words["conjunction"]))
	# Probar todas las combinaciones de verbos transitivos/intransitivos
	for tv in range(len(words["transitive-verb"]) + 1):
		for itv in range(len(words["intransitive-verb"]) + 1):
			nouns_left = len(nouns) - itv - 2 * tv
			if nouns_left < 0 or tv + itv > max_verbs:
				break
 
			# Intentar usar tantas conjunciones como sea posible
			conj_used = min(len(words["conjunction"]), (tv + itv) // 2)
			# Si se usó un verbo transitivo, poner sustantivos hasta que se acaben las comas
			extra = min(comma_num, nouns_left) if tv > 0 else 0
			total = 2 * itv + 3 * tv + extra + conj_used
 
			if total > max_size:
				max_size = total
				best_tv = tv
				best_itv = itv
 
	# Construir todas las frases iniciales (n + itv o n + tv + n)
	noun_at = 0
	phrases = []
	for i in range(best_itv):
		phrases.append(nouns[noun_at] + " " + words["intransitive-verb"][i])
		noun_at += 1
	for i in range(best_tv):
		noun1, noun2 = nouns[noun_at], nouns[noun_at + 1]
		noun_at += 2
		phrases.append(noun1 + " " + words["transitive-verb"][i] + " " + noun2)
 
	# Agregar tantos sustantivos como sea posible al final de una oración con tv
	if best_tv > 0:
		last = [phrases[-1]]
		c = 0
		while c < comma_num and noun_at < len(nouns):
			last.append(", ")
			last.append(nouns[noun_at])
			noun_at += 1
			c += 1
		phrases[-1] = "".join(last)
 
	# Unir todas las oraciones que podamos usando conjunciones
	phrase_at = 0
	sentences = []
	for conj in words["conjunction"]:
		if phrase_at + 1 >= len(phrases):
			break
		first, second = phrases[phrase_at], phrases[phrase_at + 1]
		phrase_at += 2
		sentences.append(first + " " + conj + " " + second)
	sentences.extend(phrases[phrase_at:])
 
	print(max_size)
	res = ". ".join(sentences)
	res += "." if res else ""
	print(res)