Problemas resueltos de Codeforces: Exprimidor (A. Juicer)

En Algoritmos por
agosto 26, 2016 7:26 pm

Exprimidor

límite de tiempo: 1 segundo por test
límite de memoria por test: 256 megabytes

puedes ir al problema original aquí

Kolya va hacer zumo de naranja natural. Él tiene n naranjas de tamaños a1, a2, …, an. Kolya los pondrá en la licuadora con un orden fijo, a partir de la naranja de tamaño A1, a continuación, la naranja de tamaño A2 y así sucesivamente. Para poner en la licuadora la naranja debe tener un tamaño no superior a B, por lo que si Kolya ve una naranja que es estrictamente mayor la desecha y continúa con el siguiente.

El exprimidor tiene una sección especial para recoger los residuos. Se desborda si Kolya exprime naranjas del tamaño total estrictamente mayor que d. Cuando esto sucede Kolya vacía la sección de desperdicio (incluso si no hay más naranjas) y continúa exprimiendo el jugo. ¿Cuántas veces se tiene que vaciar la sección de desperdicio?

Input
La primera línea de la entrada contiene tres enteros n, B y D (1 ≤ n ≤ 100 000, 1 ≤ b ≤ d ≤ 1 000 000) – el número de naranjas, el tamaño máximo de la naranja que cabe en la licuadora y el valor d, que determina la condición cuando la sección de residuos se debe vaciar.

La segunda línea contiene n enteros a1, a2, …, an (1 ≤ AI ≤ 1 000 000) – Los tamaños de las naranjas que figuran en el orden, Kolya va a tratar de ponerlos en la licuadora.

Output
Imprimir un entero – el número de veces que Kolya tendrá que vaciar la sección de desperdicio.

Examples:
input

output

input

output

input

output

input

output

Nota:

  • En la primera muestra, Kolya exprime el jugo de dos naranjas y vacía la sección de desperdicio después.
  • En el segundo ejemplo, el naranja no cabrá en el exprimidor de modo Kolya no tendrá ningún jugo en absoluto.

Código resuelto con C++:

 


2988 visitas