Sasha y la merienda

Points: 100 (partial)

Time limit: 1.0s

Memory limit: 64M

Authors:

Leonardo, FrankHG

Problem type

Allowed languages

Ada, BrainF***, C, C#, C++, Dart, Go, Java, JS, Kotlin, Pascal, Prolog, Python, Swift, VB

Al Sasha le encanta pasar tiempo en la naturaleza y, sobre todo, le encanta pasar tiempo en los bosques. El aire fresco y los hermosos sonidos hacen del bosque su lugar favorito. Sasha ha decidido pasar esta tarde en un bosque y, como es tan práctica, también ha decidido atiborrarse de comida. Su vientre puede contener $C$ ~C~ cantidad de comida.

Tendrá la oportunidad de comer diversas frutas de la naturaleza (setas, castañas, bayas, etc.) mientras camina por el bosque. Todas las frutas son mutuamente diferentes y le gustaría comer tantas frutas diferentes como sea posible, pero con la condición de que no coma en exceso. En otras palabras, el peso total de las frutas que ha comido no debe ser mayor que $C$ ~C~. Además, cuando Sasha decide comenzar a comer, intenta comer todas las frutas siguientes si es posible comerlas y no comer en exceso. En el caso de que no tenga la capacidad de comerlo, simplemente continua con la siguiente fruta sin comer esa.

Dados $N$ ~N~ enteros que representan el peso y el orden en que Sasha encuentra las frutas ,determine la cantidad máxima de frutas diferentes que puede comer Sasha si empieza a comer en el momento óptimo.

Entrada:

La primera línea de entrada contiene dos números enteros $N$ ~N~ y $C$ ~C~ $(1 \le N \le 1000, 1 \le C \le 1000000)$ .

La segunda línea contiene $N$ ~N~ números enteros $w_{i}$ ~w_{i}~ $(1 \le w_{i} \le 1000)$ ~(1 \le w_{i} \le 1000)~ que representan el peso de las frutas en el orden en que Sasha las encuentra.

Salida:

La primera y única línea de salida debe contener la máxima cantidad posible de frutas diferentes que Sasha pueda comer.

Entrada de ejemplo 1:

5 5
3 1 2 1 1

Salida de ejemplo 1:

Si Sasha decide comenzar a comer en la primera fruta, entonces habrá comido $3$ ~3~ frutas diferentes $(3, 1, 1)$ ~(3, 1, 1)~. Si comienza a comer en la segunda fruta, habrá comido $4$ ~4~ frutas $(1, 2, 1, 1)$ ~(1, 2, 1, 1)~ .

Entrada de ejemplo 2:

7 5
1 5 4 3 2 1 1

Entrada de ejemplo 2:

Entrada de ejemplo 3:

5 10
3 2 5 4 3

Salida de ejemplo 3:

Comments

1

JoJo_Cubano_13 commented on Jan. 7, 2024, 3:35 a.m.

Hola buenas, alguien podría por favor revisar mi código y explicarme que está pasando? Me están dando mal solo 3 casos y ya he probado con alrededor de 10 casos a mano y todos me han dado bien al compilarlo. Muchas gracias

1

Diego_Dario commented on July 14, 2024, 4:25 p.m.

Además, cuando Sasha decide comenzar a comer, intenta comer todas las frutas siguientes si es posible comerlas y no comer en exceso. En el caso de que no tenga la capacidad de comerlo, simplemente continua con la siguiente fruta sin comer esa.

2

angelmh commented on Sept. 17, 2023, 10:56 p.m.

Alguien me puede ayudar con casos de entrada extremos para comprobar mi código? Me da WA en 3 pruebas y no encuentro la falla.

int max = 0; int aux = 0; for (int i = 0; i < n - 1; i++) { aux = arr[i]; for (int j = i + 1; j < n; j++) { aux += arr[j]; if (aux <= c) { max = Math.max(j - i + 1, max); } } } pw.println(max);

2

Hd commented on Jan. 1, 2024, 4:02 p.m.

Hola, me pasaba lo mismo que a ti, creo q deberías leer la última oración del problema con detenimiento y analizar el primer caso de prueba para que veas tú mismo lo que pasa