Skip to Content
CTRL K

Magazine Ad

Pista 1

Si se sabe que cierto ancho es/no es posible para formatear un anuncio, ¿qué se puede deducir de eso?

Pista 2

¿Hay forma de formatear un anuncio de un ancho dado usando a lo sumo el número máximo de líneas?

Solución

Explicación

Editorial oficial 

¿Hay forma de formatear un anuncio de un ancho dado usando a lo sumo el número máximo de líneas?

Si podemos formatear un anuncio usando a lo sumo el número máximo de líneas con ancho ww, entonces todos los anchos ≥w\geq w también funcionan. Por lo tanto, podemos hacer búsqueda binaria sobre el ancho mínimo que funciona.

Podemos partir el anuncio en palabras individuales. Guardaremos la longitud de cada palabra más un espacio o un guion (salvo la última palabra), porque los espacios y los guiones funcionan de forma similar.

Agregaremos tantas palabras como sea posible a cada línea para cada ancho, creando una línea nueva cuando nos quedamos sin espacio. Si la cantidad de líneas que usamos es menor o igual que el número máximo de líneas, entonces nuestro ancho funciona. Si alguna palabra es más larga que el ancho dado, entonces nuestro ancho no funciona.

Implementación

Complejidad temporal: O(Nlog⁡N)\mathcal{O}(N \log N)

#include <bits/stdc++.h>
using namespace std;
 
int max_lines;
vector<int> word_lengths;
string ad;
 
/** @return si el anuncio más optimizado del ancho dado cumple las restricciones */
bool width_valid(int width) {
	int lines = 0;
	int curr_width = 0;
 
	for (int word_length : word_lengths) {
		// si una palabra individual es más ancha que el anuncio, hace falta un ancho mayor
		if (word_length > width) { return false; }
 
		// si nos pasamos, hace falta una línea nueva
		if (curr_width + word_length > width) {
			lines++;
			curr_width = word_length;
		} else {
			curr_width += word_length;  // agregamos la palabra a la línea actual
		}
	}
 
	if (curr_width > 0) { lines++; }
	return lines <= max_lines;
}
 
int main() {
	cin >> max_lines;
	// ignoramos el carácter '\n' antes de getline
	cin.ignore();
	getline(cin, ad);
 
	// obtenemos los tamaños de cada palabra, incluyendo espacios y guiones finales
	word_lengths.push_back(0);
	for (char i : ad) {
		word_lengths.back()++;
		// espacios y guiones funcionan igual; empezamos palabra nueva después de agregar el carácter
		if (i == ' ' || i == '-') { word_lengths.push_back(0); }
	}
 
	/*
	 * hallamos el menor ancho que no usa más de max_lines
	 * código de búsqueda binaria: https://usaco.guide/silver/binary-search
	 */
	int lo = 0;
	int hi = (int)ad.size();
	hi++;
	while (lo < hi) {
		int mid = lo + (hi - lo) / 2;
		if (width_valid(mid)) {
			hi = mid;
		} else {
			lo = mid + 1;
		}
	}
 
	cout << lo << endl;
}
import java.io.*;
import java.util.*;
 
public class MagazineAd {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
 
		int maxLines = Integer.parseInt(st.nextToken());
		String ad = br.readLine();
 
		List<Integer> wordLengths = new ArrayList<>();
		// obtenemos los tamaños de cada palabra, incluyendo espacios y guiones finales
		wordLengths.add(0);
 
		for (char i : ad.toCharArray()) {
			wordLengths.set(wordLengths.size() - 1,
			                wordLengths.get(wordLengths.size() - 1) + 1);
 
			// espacios y guiones funcionan igual; empezamos palabra nueva después de agregar el carácter
			if (i == ' ' || i == '-') { wordLengths.add(0); }
		}
 
		/*
		 * hallamos el menor ancho que no usa más de max_lines
		 * código de búsqueda binaria: https://usaco.guide/silver/binary-search
		 */
		int lo = 0;
		int hi = ad.length() + 1;
		while (lo < hi) {
			int mid = lo + (hi - lo) / 2;
			if (widthValid(mid, wordLengths, maxLines)) {
				hi = mid;
			} else {
				lo = mid + 1;
			}
		}
 
		System.out.println(lo);
	}
 
	/** @return si el anuncio más optimizado del ancho dado cumple las restricciones */
	private static boolean widthValid(int width, List<Integer> wordLengths,
	                                  int maxLines) {
		int lines = 0;
		int currWidth = 0;
 
		for (int wordLength : wordLengths) {
			// si una palabra individual es más ancha que el anuncio, hace falta un ancho mayor
			if (wordLength > width) { return false; }
 
			// si nos pasamos, hace falta una línea nueva
			if (currWidth + wordLength > width) {
				lines++;
				currWidth = wordLength;
			} else {
				currWidth += wordLength;  // agregamos la palabra a la línea actual
			}
		}
 
		if (currWidth > 0) { lines++; }
 
		return lines <= maxLines;
	}
}
def width_valid(width, word_lengths, max_lines):
	""":return: si el anuncio más optimizado del ancho dado cumple las restricciones"""
	lines = 0
	curr_width = 0
 
	for word_length in word_lengths:
		# si una palabra individual es más ancha que el anuncio, hace falta un ancho mayor
		if word_length > width:
			return False
 
		# si nos pasamos, hace falta una línea nueva
		if curr_width + word_length > width:
			lines += 1
			curr_width = word_length
		else:
			curr_width += word_length  # agregamos la palabra a la línea actual
 
	if curr_width > 0:
		lines += 1
	return lines <= max_lines
 
 
max_lines = int(input())
ad = input()
 
# obtenemos los tamaños de cada palabra, incluyendo espacios y guiones finales
word_lengths = [0]
for char in ad:
	word_lengths[-1] += 1
	# espacios y guiones funcionan igual; empezamos una palabra nueva después de agregar un carácter
	if char == " " or char == "-":
		word_lengths.append(0)
 
# hallamos el menor ancho que no usa más de max_lines
lo = 0
hi = len(ad) + 1
while lo < hi:
	mid = lo + (hi - lo) // 2
	if width_valid(mid, word_lengths, max_lines):
		hi = mid
	else:
		lo = mid + 1
 
print(lo)
Fundamentos