Contar día por día
+17 puntosD ≤ 106
La idea más directa: recorrer los días uno por uno y preguntar «¿hoy le toca a Bob?». Numeramos los días desde 0
(así es más cómodo dividir). El día número dia está en la semana dia / 7 y es el día
dia % 7 de esa semana (0 es lunes, 4 es viernes, 5 y 6 son el fin de semana).
¿Qué grupo no circula? En la semana 0, el lunes es el grupo 0, el martes el 1… es decir, el grupo d. Cada
semana se corre uno, así que en la semana w el día d le toca al grupo
(w + d) % 5. El % 5 hace que después del grupo 4 vuelva el 0.
#include "placa.h"
// Grupo según el último dígito de la placa: 1,2 -> 0; 3,4 -> 1; ...; 9,0 -> 4.
const int GRUPO[10] = {4, 0, 0, 1, 1, 2, 2, 3, 3, 4};
// Subtarea 1 (D <= 10^6): revisamos los días uno por uno.
long long dias_restringidos(long long P, long long D) {
int g = GRUPO[P % 10];
long long cuenta = 0;
for (long long dia = 0; dia < D; dia++) { // dia 0 es el lunes de la semana 0
long long semana = dia / 7;
long long d = dia % 7; // 0 = lunes, ..., 4 = viernes, 5 y 6 = fin de semana
if (d < 5 && (semana + d) % 5 == g) cuenta++;
}
return cuenta;
} Con D ≤ 106 son a lo más un millón de vueltas del bucle: la computadora lo hace en un milisegundo. Pero en las otras subtareas D llega a 1018. Mueve el control y mira qué pasa:
Con 1018 días, el bucle tardaría más de 30 años. Para las demás subtareas hay que dejar de contar y pensar.