$ cd preparacion/editoriales/clasificatoria-2026/placa

Placa rotativa

Una restricción vehicular que cambia de día cada semana. Te contamos cómo sumar puntos subtarea por subtarea, desde contar día por día hasta una fórmula que responde al instante.

Autor: Juan Manuel Rua Echalar 100 puntos · 4 subtareas

// el problema

La historia, en corto

En Sucre hay una regla nueva: de lunes a viernes, cada día hay un grupo de autos que no puede circular. Los sábados y domingos todos circulan. El grupo de un auto depende del último dígito de su placa:

Último dígito1 o 23 o 45 o 67 u 89 o 0
Grupo01234

La primera semana (la semana 0) el lunes no circula el grupo 0, el martes el grupo 1, y así hasta el viernes, que le toca al grupo 4. Para que no le toque siempre el mismo día a los mismos, cada semana todo se corre un día: en la semana 1 el lunes le toca al grupo 1, el martes al 2, … y el viernes al 0.

Bob tiene un auto con placa P. Hay que contar en cuántos de los primeros D días no pudo usarlo. El día 1 es un lunes.

Calendario de la restricción· prueba con tu placa

Cada fila es una semana (s0 es la semana 0) y cada casilla dice qué grupo (G0 a G4) no circula ese día; el fin de semana (—) es libre. En rojo, los días en que el auto de Bob se queda en casa. Mueve D y mira cómo cambia la cuenta.

// qué hay que programar

Solo una función

En la OBI no lees la entrada ni imprimes la salida: de eso se encarga el grader, un programa que prepara la OBI. Tú escribes solo la función dias_restringidos, que recibe P y D y devuelve la respuesta. El grader la llama una vez por caso de prueba.

archivo de prueba
7 30
grader (lo pone la OBI) lee la entrada y llama a dias_restringidos(7, 30)
tu función, en placa.cpp long long dias_restringidos(long long P, long long D);
el grader escribe
4

Fíjate en el tipo: long long. D puede llegar a 1018 (un trillón), que no cabe en un int. ¿Quieres saber más del grader? Está explicado en la página de inicio de las editoriales.

// la escalera de puntos

Cuatro subtareas, cuatro ideas

Cada bloque es una subtarea, tan ancho como sus puntos. Tócalo para ir a su explicación.

Cada subtarea es una versión más fácil del problema y da puntos por sí sola. Ojo: las subtareas 2 y 3 no dependen de la 1. Puedes sacar sus 46 puntos sin haber resuelto la primera, porque cada una premia una observación distinta. La 4 junta todo.

Subtarea 1

Contar día por día

+17 puntos

D ≤ 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.

placa.cpp · subtarea 1 17 pts
#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:

¿Cuánto tarda?· límite: 1 segundo

Una computadora hace unos mil millones (109) de pasos sencillos por segundo. Contar día por día hace un paso por día; la fórmula de la subtarea 4 hace unos pocos pasos, sea cual sea D.

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.

Subtarea 2

Una restricción por semana

+22 puntos

El día D es viernes, sábado o domingo

Recuerda lo que viste en el calendario: cada semana, de lunes a viernes, pasan los cinco grupos, una vez cada uno. Si el día D es viernes, sábado o domingo, entonces la última semana ya terminó sus días hábiles. Cada semana que tocamos, completa o no, le quitó a Bob exactamente un día.

¿Cuántas semanas tocamos? Si D = 12, tocamos la semana 0 (días 1 a 7) y la semana 1 (días 8 a 14): son 2. En general es D / 7 redondeado hacia arriba, que en C++ se escribe (D + 6) / 7.

placa.cpp · subtarea 2 22 pts
#include "placa.h"

// Subtarea 2 (el día D es viernes, sábado o domingo): cada semana restringe
// a cada grupo exactamente una vez, y la última semana ya pasó su viernes.
// La respuesta es la cantidad de semanas tocadas, ceil(D / 7), sin importar la placa.
long long dias_restringidos(long long P, long long D) {
    return (D + 6) / 7;
}

Esto ya no cuenta día por día: hace una división y responde al instante, aunque D sea 1018. Lo que le falta: si D cae de lunes a jueves, la última semana está cortada y quizá el día de Bob todavía no llegó.

Subtarea 3

Cuando D es lunes

+24 puntos

El día D es lunes

Si el día D es lunes, entonces D = 7w + 1: hay w = D / 7 semanas completas y, de la semana w, solo vemos su lunes.

  • Las w semanas completas aportan un día cada una: w días.
  • El lunes de la semana w no circula el grupo w % 5 (el lunes de la semana 0 es el grupo 0, el de la semana 1 el grupo 1, …). Si ese es el grupo de Bob, sumamos 1.
placa.cpp · subtarea 3 24 pts
#include "placa.h"

const int GRUPO[10] = {4, 0, 0, 1, 1, 2, 2, 3, 3, 4};

// Subtarea 3 (el día D es lunes): hay w = D / 7 semanas completas, una
// restricción por cada una. De la semana w solo vemos el lunes, y ese lunes
// no circula el grupo w % 5.
long long dias_restringidos(long long P, long long D) {
    int g = GRUPO[P % 10];
    long long w = D / 7;
    return w + (w % 5 == g ? 1 : 0);
}

Aquí ya importa la placa, y aparece la pregunta clave para el problema completo: ¿en qué día de la semana incompleta le toca a Bob?

Subtarea 4

La semana incompleta

+37 puntos

Sin restricciones adicionales

Ahora D puede caer en cualquier día. Partimos los D días en w = D / 7 semanas completas y r = D % 7 días sueltos de la semana w (su lunes, su martes, …). Las semanas completas aportan w. Falta saber si el día de Bob en la semana w cae dentro de esos r días.

En la semana w el día d le toca al grupo (w + d) % 5. Queremos el d con (w + d) % 5 == g, y despejando:

d = (g − w) mod 5 respuesta = w + (d < r ? 1 : 0)

Esta fórmula incluye a las subtareas anteriores: si el día D es viernes, sábado o domingo, r es 5, 6 o 0 y el resultado es el mismo que (D + 6) / 7; si es lunes, r = 1 y solo cuenta si d = 0, como en la subtarea 3.

placa.cpp · solución completa 100 pts
#include "placa.h"

const int GRUPO[10] = {4, 0, 0, 1, 1, 2, 2, 3, 3, 4};

// Solución completa, O(1).
// En la semana w, el grupo g no circula el día hábil d que cumple (w + d) % 5 == g,
// es decir, d = (g - w) mod 5: exactamente un día por semana.
long long dias_restringidos(long long P, long long D) {
    int g = GRUPO[P % 10];
    long long w = D / 7;  // semanas completas: una restricción cada una
    long long r = D % 7;  // días de la semana incompleta (lunes, martes, ...)
    // En C++, % puede dar negativo: sumamos 5 para dejarlo entre 0 y 4.
    long long d = ((g - w) % 5 + 5) % 5;
    return w + (d < r ? 1 : 0);  // ¿su día cae dentro de los r días que vemos?
}

Hay otro camino que también da 100: el patrón completo se repite cada 5 semanas (35 días), y en esos 35 días cada grupo pierde exactamente 5. Sumas 5 por cada bloque de 35 días y cuentas día por día solo los menos de 35 que sobran.

// para la próxima

Errores comunes

  • Usar int. D llega a 1018 y un int solo guarda hasta unos 2 × 109. Usa long long.
  • El módulo negativo de C++, como en el recuadro de arriba.
  • Olvidar que la restricción se corre. Ese código puede pasar la subtarea 2 (donde la placa no importa) y nada más.
  • Calcular mal el grupo, por ejemplo como «último dígito % 5». También pasa solo la subtarea 2, por la misma razón.
  • Olvidar el fin de semana, como si la semana tuviera 5 días.