Skip to Content

Milk Measurement

Análisis oficial (C++ y Java) 

Explicación

Como solo hay 33 vacas y N1000N \leq 1000, podemos ordenar todas las entradas por fecha y actualizar el valor de leche de la vaca seleccionada en cada entrada.

Implementación

Complejidad temporal: O(NlogN)\mathcal{O}(N \log N), ya que la cantidad de vacas es constante.

#include <bits/stdc++.h> using namespace std; const vector<string> NAMES{"Bessie", "Elsie", "Mildred"}; const int START_AMT = 7; int main() { freopen("measurement.in", "r", stdin); int update_num; cin >> update_num; vector<tuple<int, string, int>> updates; for (int i = 0; i < update_num; i++) { int day; string cow; int change; cin >> day >> cow >> change; updates.push_back(make_tuple(day, cow, change)); } sort(updates.begin(), updates.end()); /* * Mapa que guarda la producción actual de cada vaca. * Más adelante cambiaremos los valores de producción según la entrada. */ map<string, int> outputs; for (const auto &name : NAMES) { outputs[name] = START_AMT; } vector<string> display = NAMES; // Las vacas con la mayor producción de leche. int display_changes = 0; for (const tuple<int, string, int> &u : updates) { // Cambiamos los valores de producción según la entrada. outputs[get<1>(u)] += get<2>(u); int max_output = 0; for (const auto &[_, output] : outputs) { max_output = max(max_output, output); } vector<string> new_display; for (const auto &[name, output] : outputs) { if (output == max_output) { new_display.push_back(name); } } // Actualizamos la respuesta si la ganadora vieja es distinta de la nueva. display_changes += display != new_display; display = new_display; } freopen("measurement.out", "w", stdout); cout << display_changes << endl; }
import java.io.*; import java.util.*; public class Measurement { static final String[] NAMES = new String[] {"Bessie", "Elsie", "Mildred"}; static final int START_AMT = 7; // BeginCodeSnip{Update Class} static class Update { public int day; public String cow; public int change; public Update(int day, String cow, int change) { this.day = day; this.cow = cow; this.change = change; } } // EndCodeSnip public static void main(String[] args) throws IOException { BufferedReader read = new BufferedReader(new FileReader("measurement.in")); int updateNum = Integer.parseInt(read.readLine()); Update[] updates = new Update[updateNum]; for (int i = 0; i < updateNum; i++) { StringTokenizer update = new StringTokenizer(read.readLine()); updates[i] = new Update(Integer.parseInt(update.nextToken()), update.nextToken(), Integer.parseInt(update.nextToken())); } Arrays.sort(updates, Comparator.comparingInt(u -> u.day)); /* * Mapa que guarda la producción actual de cada vaca. * Más adelante cambiaremos los valores de producción según la entrada. */ Map<String, Integer> outputs = new HashMap<>(); for (String name : NAMES) { outputs.put(name, START_AMT); } // Las vacas con la mayor producción de leche. List<String> display = Arrays.asList(NAMES); int displayChanges = 0; for (Update u : updates) { // Cambiamos los valores de producción según la entrada. outputs.put(u.cow, outputs.get(u.cow) + u.change); int maxOutput = 0; for (int o : outputs.values()) { maxOutput = Math.max(maxOutput, o); } List<String> newDisplay = new ArrayList<>(); for (Map.Entry<String, Integer> o : outputs.entrySet()) { if (o.getValue() == maxOutput) { newDisplay.add(o.getKey()); } } // Actualizamos la respuesta si la ganadora vieja es distinta de la nueva. displayChanges += !display.equals(newDisplay) ? 1 : 0; display = newDisplay; } PrintWriter written = new PrintWriter("measurement.out"); written.println(displayChanges); written.close(); } }
NAMES = ["Bessie", "Elsie", "Mildred"] START_AMT = 7 with open("measurement.in") as read: update_num = int(read.readline()) updates = [] for _ in range(update_num): day, cow, change = read.readline().split() updates.append((int(day), cow, int(change))) updates.sort() """ Mapa que guarda la producción actual de cada vaca. Más adelante cambiaremos los valores de producción según la entrada. """ outputs = {c: START_AMT for c in NAMES} display = NAMES.copy() # Las vacas con la mayor producción de leche. display_changes = 0 for u in updates: # Cambiamos los valores de producción según la entrada. outputs[u[1]] += u[2] max_output = max(outputs.values()) new_display = [name for name, o in outputs.items() if o == max_output] # Actualizamos la respuesta si la ganadora vieja es distinta de la nueva. display_changes += display != new_display display = new_display print(display_changes, file=open("measurement.out", "w"))