Combinatoria
Zonal Informatics Olympiadindia Zonal Informatics Olympiad

Zonal Informatics Olympiadindia Zonal Informatics Olympiad P1

La publicación a continuación ha sido eliminada. Haga clic para cerrar. Esta publicación ha sido eliminada. Haga clic aquí para ver la publicación. Pi-Infinity 141 publicaciones Pi-Infinity #1 h 23 de nov. de 2025, 5:19 a. m. Y por Usted observó el cielo nocturno durante $N$ noches consecutivas. En la noche $i$, usted encontró que había exactamente $A_i$ estrellas visibles. Debido a peculiaridades del Sistema Solar, se sabe que cada estrella es visible durante un segmento continuo de noches $[L, R]$, es decir, cada estrella tiene $2$ enteros $L$ y $R$ tales que $1 \leq L \leq R \leq N$, y la estrella es visible solo en las noches $L, L+1, L+2, \dots, R$. La entrada consiste en $N$, el número de noches durante las cuales se observaron estrellas, y $A = [A_1, A_2, \dots, A_N]$, una sucesión de $N$ valores donde $A_i$ denota el número de estrellas observadas en la noche $i$. Podría haber muchas combinaciones posibles de estrellas que conduzcan al mismo número de estrellas observadas cada noche. Nos interesa el número total de estrellas únicas que se vieron a lo largo de esas $N$ noches. Sea $m$ el mínimo y $M$ el máximo número de estrellas únicas que usted podría haber observado. Su tarea es encontrar la suma $m + M$. Por ejemplo, para la entrada $N = 2$, $A = [2, 2]$, el mínimo $m$ es $2$, porque es posible que las mismas $2$ estrellas sean visibles en ambas noches, mientras que el máximo $M$ es $4$, porque es posible que $2$ estrellas sean visibles en la noche $1$ y $2$ estrellas nuevas sean visibles en la noche $2$. Por lo tanto, la respuesta es $m + M = 2 + 4 = 6$. Encuentre el valor de $m+M$ para las siguientes entradas: (a) $N = 3, A = [2, 1, 2]$ (b) $N = 6, A = [1, 2, 3, 4, 2, 1]$ (c) $N = 12, A = [4, 1, 3, 5, 2, 2, 3, 1, 5, 6, 2, 1]$ Generalización Generalización del problema- Sea $S = \{1, 2, \dots, N\}$ un conjunto discreto de $N$ puntos (noches). Se nos da una sucesión de restricciones $A = [A_1, A_2, \dots, A_N]$, donde $A_i$ especifica que el punto $i \in S$ debe estar cubierto por exactamente $A_i$ subsegmentos continuos (estrellas). Un subsegmento continuo (intervalo) está definido por dos puntos extremos $[L, R]$, donde $1 \leq L \leq R \leq N$. Un punto $i$ está cubierto por el intervalo $[L, R]$ si y solo si $L \leq i \leq R$. Buscamos encontrar un multiconjunto de tales subsegmentos continuos, $\mathcal{I} = \{[L_k, R_k]\}_{k=1}^{|\mathcal{I}|}$, tal que para cada punto $i \in S$, el número de subsegmentos en $\mathcal{I}$ que cubren a $i$ sea exactamente $A_i$. El objetivo es determinar el: Tamaño mínimo $m$: El menor número posible de subsegmentos únicos en $\mathcal{I}$ que satisface todas las restricciones. Tamaño máximo $M$: El mayor número posible de subsegmentos únicos en $\mathcal{I}$ que satisface todas las restricciones. Su tarea es encontrar la suma $m + M$. Formulación alternativa Encuentre el tamaño mínimo y máximo de una colección de intervalos $\mathcal{I}$ tal que la profundidad en cualquier punto $i$ (el número de intervalos en $\mathcal{I}$ que contienen a $i$) sea exactamente $A_i$. Esta publicación ha sido editada 7 veces. Última edición por Pi-Infinity, 23 de nov. de 2025, 9:04 a. m. Z K Y

Inicia sesión para agregar soluciones y pistas

Problemas Recomendados