Sleeping in Class

Explicación

Después de que Elsie haya hecho todas las modificaciones al arreglo de registro $A$ , el registro mostrará que Bessie duerme la misma cantidad de horas todos los días. Llamemos a ese número $\texttt{num\\_hours}$ .

Definamos también el total de horas que duerme Bessie como $\texttt{sum}$ .

Sabemos que, después de todas las modificaciones, la longitud del registro será $\texttt{sum}/\texttt{num\\_hours}$ . Como cada modificación reduce la longitud del registro en 1, la cantidad de modificaciones que hace Elsie será $N-\texttt{sum}/\texttt{num\\_hours}$ .

Como $N$ y $\texttt{sum}$ son constantes, para minimizar la expresión anterior nuestra única opción es minimizar $\texttt{num\\_hours}$ .

Para ello, recorremos los divisores de $\texttt{sum}$ como valores candidatos de $\texttt{num\\_hours}$ de menor a mayor y comprobamos si es posible reducir el registro a un arreglo con todos los elementos iguales a ese valor. En cuanto encontramos un elemento válido, imprimimos la cantidad de modificaciones necesarias y terminamos, ya que sabemos que es lo mejor que podemos hacer.

Para comprobar si un valor de $\texttt{num\\_hours}$ es válido, recorremos el registro dado y combinamos valores. Si en algún momento un valor combinado supera $\texttt{num\\_hours}$ , sabemos que $\texttt{num\\_hours}$ no es válido.

Implementación

Complejidad temporal: $\mathcal{O}(N\sqrt{\texttt{sum}})$ por cada caso de prueba.

C++JavaPython


#include <bits/stdc++.h>
using namespace std;
 
int main() {
	int test_num;
	cin >> test_num;
	for (int t = 0; t < test_num; t++) {
		int n;
		cin >> n;
		vector<int> elsie_log = vector<int>(n);
		int log_sum = 0;
		for (int &h : elsie_log) {
			cin >> h;
			log_sum += h;
		}
 
		if (log_sum == 0) {
			cout << 0 << '\n';
			continue;
		}
 
		auto valid = [&](int num_hours) {
			int curr_sum = 0;  // La cantidad actual de horas que Elsie está registrando
			for (int h : elsie_log) {
				curr_sum += h;
				if (curr_sum > num_hours) {
					return false;  // curr_sum no puede superar num_hours
				} else if (curr_sum == num_hours) {
					curr_sum = 0;
				}
			}
			return true;
		};
 
		// Probar las cantidades posibles de horas después de la modificación en orden creciente.
		bool found = false;
		int max_factor = 0;
		for (int factor = 1; factor * factor <= log_sum; factor++) {
			max_factor = factor;
			if (log_sum % factor == 0 && valid(factor)) {
				// log_sum/factor es el total de clases DESPUÉS de modificar
				cout << n - log_sum / factor << '\n';
				found = true;
				break;
			}
		}
		if (found) { continue; }
 
		for (int factor = max_factor; factor >= 1; factor--) {
			if (log_sum % factor == 0 && factor * factor != log_sum) {
				int num_hours = log_sum / factor;
				if (valid(num_hours)) {
					// log_sum/num_hours es el total de clases DESPUÉS de modificar
					cout << n - log_sum / num_hours << '\n';
					break;
				}
			}
		}
	}
}


import java.io.*;
import java.util.*;
 
public class SleepingInClass {
	private static boolean valid(int[] elsieLog, int numHours) {
		int currSum = 0;  // La cantidad actual de horas que Elsie está registrando
		for (int h : elsieLog) {
			currSum += h;
			if (currSum > numHours) {
				return false;  // currSum no puede superar numHours
			} else if (currSum == numHours) {
				currSum = 0;
			}
		}
		return true;
	}
 
	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++) {
			int n = Integer.parseInt(read.readLine());
			int[] elsieLog = new int[n];
			int logSum = 0;
			StringTokenizer logST = new StringTokenizer(read.readLine());
			for (int i = 0; i < n; i++) {
				elsieLog[i] = Integer.parseInt(logST.nextToken());
				logSum += elsieLog[i];
			}
 
			if (logSum == 0) {
				System.out.println(0);
				continue;
			}
 
			// Probar las cantidades posibles de horas después de la modificación en orden creciente.
			boolean found = false;
			int maxFactor = 0;
			for (int factor = 1; factor * factor <= logSum; factor++) {
				maxFactor = factor;
				if (logSum % factor == 0 && valid(elsieLog, factor)) {
					// logSum/factor es el total de clases DESPUÉS de modificar
					System.out.println(n - logSum / factor);
					found = true;
					break;
				}
			}
			if (found) { continue; }
 
			for (int factor = maxFactor; factor >= 1; factor--) {
				if (logSum % factor == 0 && factor * factor != logSum) {
					int numHours = logSum / factor;
					if (valid(elsieLog, numHours)) {
						// logSum/numHours es el total de clases DESPUÉS
						// de modificar
						System.out.println(n - logSum / numHours);
						break;
					}
				}
			}
		}
	}
}


def valid(elsie_log, num_hours):
	curr_sum = 0  # La cantidad actual de horas que Elsie está registrando
	for h in elsie_log:
		curr_sum += h
		if curr_sum > num_hours:
			return False  # curr_sum no puede superar num_hours
		elif curr_sum == num_hours:
			curr_sum = 0
	return True
 
 
for _ in range(int(input())):
	n = int(input())
	elsie_log = [int(i) for i in input().split()]
	assert len(elsie_log) == n
 
	log_sum = sum(elsie_log)
 
	if log_sum == 0:
		print(0)
		continue
 
	# Probar las cantidades posibles de horas después de la modificación en orden creciente.
	found = False
	max_factor = 0
	factor = 1
	while factor * factor <= log_sum:
		max_factor = factor
		if log_sum % factor == 0 and valid(elsie_log, factor):
			# log_sum/factor es el total de clases DESPUÉS de modificar
			print(n - log_sum // factor)
			found = True
			break
		factor += 1
	if found:
		continue
 
	for factor in range(max_factor, 0, -1):
		if log_sum % factor == 0 and factor * factor != log_sum:
			num_hours = log_sum // factor
			if valid(elsie_log, num_hours):
				# log_sum/num_hours es el total de clases DESPUÉS de modificar
				print(n - log_sum // num_hours)
				break