Turrón del duro P52382


Statement
 

pdf   zip

html

El cocinero de la única escuela de Villabajo de Arriba (Chef, para los amigos) se dispone a cortar los T centímetros de turrón de Alicante (el “duro”) en n trozos. El turrón ha llegado en exactamente k≤ n barras, no todas ellas del mismo tamaño. Todo el mundo sabe que el turrón duro de Villabajo de Arriba es duro de verdad: usando su motosierra de cocina, Chef sólo puede realizar cortes en las líneas de puntos que hay a cada centímetro exacto de turrón.

La intención de Chef es hacer exactamente n−k cortes adicionales para acabar obteniendo exactamente n trozos. Para ello, Chef repitirá n−k veces el siguiente proceso: buscar el trozo más grande de turrón, y cortarlo por la mitad. En concreto, cortarlo en dos trozos de tamaño t/2 si el tamaño original t es par, y en un trozo de tamaño ⌊ t/2 ⌋ y otro de tamaño ⌊ t/2 ⌋ + 1 si el tamaño original es impar. Caso de haber más de un trozo de turrón de tamaño máximo, Chef escogerá el primero (los turrones están originalmente dispuestos en fila, y cuando se corta un trozo por la mitad, los nuevos trozos ocupan el espacio del anterior).

Por ejemplo, si hay k=4 trozos originales con tamaños 4, 7, 1, 7 (en este orden) y se desean n=8 trozos. Chef realizará 4 cortes en el siguiente orden (hemos marcado en negrita el trozo que Chef cortará a continuación):

4, 7, 1, 7 
4, 3, 4, 1, 7 
4, 3, 4, 1, 3, 4 
2, 2, 3, 4, 1, 3, 4 
2, 2, 3, 2, 2, 1, 3, 4 

Escribe un programa que muestre el resultado final.

Entrada

Un número indeterminado de casos. Cada caso se da en dos líneas. La primera línea contiene los números n (trozos que se desea obtener) y k (trozos inicales). La segunda línea contiene k enteros con los tamaños de los k trozos de turrón. Se te garantiza que k ≤ n, todos los tamaños son positivos, y que la suma T de los tamaños de los trozos de turrón es mayor o igual que n.

Salida

Para cada caso, escriba una línea con n enteros separados por espacios, con los tamaños finales de los trozos de turrón.

Puntuación

  • TestA:   Entradas con no más de 10 casos donde n ≤ 10 y T ≤ 100.  20 Puntos 
  • TestB:   Entradas con no más de 10 casos con n ≤ 1000 y T ≤ 104.  20 Puntos 
  • TestC:   Entradas con no más de 10 casos con n ≤ 104 y T ≤ 106.  30 Puntos 
  • TestD:   Entradas con no más de 5 casos con n ≤ 105 y T ≤ 109.  30 Puntos 
Public test cases

  • Input

    8 4
4 7 1 7

    Output

    2 2 3 2 2 1 3 4

  • Input

    2 1
10
3 1
10
4 1
10
5 1
10
6 1
10
7 1
10

    Output

    5 5
2 3 5
2 3 2 3
2 1 2 2 3
2 1 2 2 1 2
1 1 1 2 2 1 2

  • Input

    4 2
3189317 4728378

    Output

    1594658 1594659 2364189 2364189

  • Input

    8 1
318933

    Output

    39866 39867 39866 39867 39866 39867 39867 39867
    • Information
    Author
    Omer Giménez
    Language
    Spanish
    Official solutions
    C++
    User solutions
    C++