Skip to Content
CTRL K

Photoshoot

Análisis oficial (C++, Java y Python) 

Explicación

Queremos maximizar la cantidad de Guernseys en posiciones pares. Mirando pares de vacas adyacentes, HH no aporta nada, GG siempre aporta uno, y GH/HG pueden aportar uno según su orientación. Solo consideramos pares adyacentes cuya primera vaca está en una posición impar para evitar solapamientos. Decimos que un par mixto GH/HG está alineado si es HG y desalineado si es GH.

Como invertir un prefijo voltea la orientación de todos los pares anteriores, podemos recorrer los pares de derecha a izquierda, llevando la cuenta de si nuestros volteos han cambiado la orientación o no.

Si un par mixto ya está alineado bajo la orientación actual, lo dejamos. En caso contrario, hay que voltearlo. Un par está desalineado exactamente cuando su Guernsey termina en una posición impar bajo la paridad actual de volteos. Cada volteo es a la vez necesario y suficiente, así que la cantidad de veces que hay que voltear pares desalineados es exactamente el número mínimo de inversiones necesarias.

Implementación

Complejidad temporal: O(N)\mathcal{O}(N)

#include <cassert>
#include <iostream>
#include <string>
 
using std::cout;
using std::endl;
using std::string;
 
int main() {
	int cow_num;
	string cows;
	std::cin >> cow_num >> cows;
	assert(cows.size() == cow_num && cow_num % 2 == 0);
 
	int flips = 0;
	for (int c = cow_num - 2; c >= 0; c -= 2) {
		string sub = cows.substr(c, 2);
		if (sub[0] == sub[1]) { continue; }
		if ((sub == "GH" && flips % 2 == 0) || (sub == "HG" && flips % 2 == 1)) {
			flips++;
		}
	}
 
	cout << flips << endl;
}
import java.io.*;
 
public class Photoshoot {
	public static void main(String[] args) throws IOException {
		BufferedReader read = new BufferedReader(new InputStreamReader(System.in));
		int cowNum = Integer.parseInt(read.readLine());
		String cows = read.readLine();
		assert cows.length() == cowNum && cowNum % 2 == 0;
		read.close();
 
		int flips = 0;
		for (int c = cowNum - 2; c >= 0; c -= 2) {
			String sub = cows.substring(c, c + 2);
			if (sub.charAt(0) == sub.charAt(1)) { continue; }
			if ((sub.equals("GH") && flips % 2 == 0) ||
			    (sub.equals("HG") && flips % 2 == 1)) {
				flips++;
			}
		}
 
		System.out.println(flips);
	}
}
cow_num = int(input())
cows = input()
assert len(cows) == cow_num and cow_num % 2 == 0
 
flips = 0
for c in range(cow_num - 2, -1, -2):
	sub = cows[c : c + 2]
	if sub[0] == sub[1]:
		continue
	if (sub == "GH" and flips % 2 == 0) or (sub == "HG" and flips % 2 == 1):
		flips += 1
 
print(flips)
Fundamentos