3382 - Good kg of Flauta Bread 3382 - Buen kilo de Pan Flauta 3382 - Good kg of Flauta Bread

Statistics Sub: 170 | AC: 58 | AC%: 34,12 | Score: 2,35
Created by Torneo Argentino de Programación ACM-ICPC 2015 - Melanie Sclar
Added by fidels (2015-10-12)
Limits
Total Time: 5000 MS | Test Time: 1000 MS |Memory: 256 MB | Output: 64 MB | Size: 16 KB
Enabled languages
Available in

Description

The company Flauta wants to introduce a new package containing one kg of bread (which curiously shall be sliced bread). As part of the package design team, you have been tasked with designing a nutritional pyramid in accordance to the company's requirements. The nutritional pyramid will be represented by a triangular grid of side L, which is an equilateral triangle divided in unitary triangles (i.e. equilateral triangles of side one) by drawing lines parallel to the sides of the bigger triangle. For example, in the following figure you can see triangular grids for L = 4, 5 and 6.


There are K different types of food to be shown on the nutritional pyramid, and each of them will be represented by a horizontal section of the grid. A horizontal section is that part of the pyramid that lies between two lines parallel to the base of the grid, drawn in such a way that they only touch the unitary triangles at their borders, without crossing them. In the following figure three valid horizontal sections can be seen shaded in a grid with L = 5.


It is important for the K sections in which the nutritional pyramid is divided to be easily seen, and for this reason each of them should be composed of many unitary triangles. However, because the size of the grid is fixed there is a limited number of unitary triangles to distribute among all K sections. To make sure that no section is left disproportionately small, you have been asked to find out the maximum number of unitary triangles that can make up the smallest section of the pyramid, if the sections are chosen optimally.

For example, in the following figure three different ways to divide a grid of side L = 5 in K = 3 are represented.


The grid on the left has two sections with 9 unitary triangles each, having the other section 7 unitary triangles. In the central grid, the sections have 12, 9 and 4 unitary triangles, whereas in the grid on the right they have 16, 8 and 1. Of these three choices, the best one is then represented by the grid on the left, for it has 7 unitary triangles in its smallest section, while the central grid has 4 unitary triangles and the grid on the right has only 1 such triangle. In fact, the choice of sections represented in the grid on the left of the figure is optimal, as there is no other possible choice of K = 3 horizontal sections in which the smallest of them has more than 7 unitary triangles.
La empresa de pan Flauta quiere sacar a la venta un nuevo envase que contiene un kilo de pan (curiosamente, no se trata de pan flauta sino de pan lactal). Como parte del equipo de diseño de envases, les encargaron diseñar una pirámide nutricional acorde a los requerimientos de la empresa. La pirámide nutricional será representada por una grilla triangular de lado L, que es un triángulo equilátero dividido en triángulos unitarios (o sea, triángulos equiláteros de lado uno) trazando paralelas a los lados del triángulo mayor. Por ejemplo, en la siguiente figura se ven grillas para L = 4, 5 y 6.


Se sabe que hay K tipos de alimentos distintos para mostrar en la pirámide nutricional, cada uno de los cuales será representado por una sección horizontal de la misma. Una sección horizontal es la porción de la pirámide que queda entre dos rectas paralelas a la base de la grilla, trazadas de manera tal que sólo toquen triángulos unitarios en sus bordes, sin atravesarlos. En el gráfico a continuación se pueden ver sombreadas tres secciones horizontales válidas de una grilla con L = 5.


Es importante que las K secciones en que quede dividida la pirámide se puedan ver bien, y para ello es necesario que cada una esté conformada por muchos triángulos unitarios. Sin embargo, como el tamaño de la grilla está fijo, hay una cantidad limitada de triángulos unitarios para repartir entre las K secciones. Para asegurarse de que ninguna sección quede desproporcionadamente pequeña, les han pedido que averigüen cuál es la máxima cantidad de triángulos unitarios que pueden conformar la sección más pequeña, si se eligen las secciones óptimamente.

Por ejemplo, a continuación se muestran tres formas distintas de dividir una grilla de lado L = 5 en K = 3 secciones.


En la grilla de la izquierda hay dos secciones con 9 triángulos unitarios cada una, teniendo la otra sección 7 triángulos unitarios. En la grilla central, las secciones tienen 12, 9 y 4 triángulos unitarios, mientras que en la grilla de la derecha tienen 16, 8 y 1. De estas tres formas de elegir las secciones horizontales, la mejor es entonces la de la grilla de la izquierda, dado que en ella la sección más pequeña tiene 7 triángulos unitarios, mientras que en la grilla central y de la derecha las secciones más pequeñas tienen 4 y 1 triángulos unitarios, respectivamente. De hecho, la elección de las secciones representada en la grilla a la izquierda de la figura es óptima, ya que no hay ninguna otra elección posible de K = 3 secciones horizontales en la que la más pequeña de ellas tenga más de 7 triángulos unitarios.
The company Flauta wants to introduce a new package containing one kg of bread (which curiously shall be sliced bread). As part of the package design team, you have been tasked with designing a nutritional pyramid in accordance to the company's requirements. The nutritional pyramid will be represented by a triangular grid of side L, which is an equilateral triangle divided in unitary triangles (i.e. equilateral triangles of side one) by drawing lines parallel to the sides of the bigger triangle. For example, in the following figure you can see triangular grids for L = 4, 5 and 6.


There are K different types of food to be shown on the nutritional pyramid, and each of them will be represented by a horizontal section of the grid. A horizontal section is that part of the pyramid that lies between two lines parallel to the base of the grid, drawn in such a way that they only touch the unitary triangles at their borders, without crossing them. In the following figure three valid horizontal sections can be seen shaded in a grid with L = 5.


It is important for the K sections in which the nutritional pyramid is divided to be easily seen, and for this reason each of them should be composed of many unitary triangles. However, because the size of the grid is fixed there is a limited number of unitary triangles to distribute among all K sections. To make sure that no section is left disproportionately small, you have been asked to find out the maximum number of unitary triangles that can make up the smallest section of the pyramid, if the sections are chosen optimally.

For example, in the following figure three different ways to divide a grid of side L = 5 in K = 3 are represented.


The grid on the left has two sections with 9 unitary triangles each, having the other section 7 unitary triangles. In the central grid, the sections have 12, 9 and 4 unitary triangles, whereas in the grid on the right they have 16, 8 and 1. Of these three choices, the best one is then represented by the grid on the left, for it has 7 unitary triangles in its smallest section, while the central grid has 4 unitary triangles and the grid on the right has only 1 such triangle. In fact, the choice of sections represented in the grid on the left of the figure is optimal, as there is no other possible choice of K = 3 horizontal sections in which the smallest of them has more than 7 unitary triangles.

Input specification

One line containing two integers L and K, respectively representing the length of the side of the triangular grid and the number of sections in which said grid is to be divided (1 <= K <= L <= 10^6).
Una línea conteniendo dos enteros L y K, representando respectivamente la longitud del lado de la grilla triangular y la cantidad de secciones en las que se desea dividir dicha grilla (1 <= K <= L <= 10^6).
One line containing two integers L and K, respectively representing the length of the side of the triangular grid and the number of sections in which said grid is to be divided (1 <= K <= L <= 10^6).

Output specification

Print one line containing an integer representing the maximum number of unitary triangles that can make up the smallest horizontal section.
Imprimir en la salida una línea conteniendo un entero que representa la máxima cantidad de triángulos unitarios que pueden conformar la sección horizontal más pequeña.
One line containing two integers L and K, respectively representing the length of the side of the triangular grid and the number of sections in which said grid is to be divided (1 <= K <= L <= 10^6).

Sample input

5 3

Sample output

7

Hint(s)

Sample input #2
5 2

Sample output #2
9

Sample input #3
1000000 1

Sample output #3
1000000000000

Sample input #4
1000000 30000

Sample output #4
32679639
Sample input #2
5 2

Sample output #2
9

Sample input #3
1000000 1

Sample output #3
1000000000000

Sample input #4
1000000 30000

Sample output #4
32679639
Sample input #2
5 2

Sample output #2
9

Sample input #3
1000000 1

Sample output #3
1000000000000

Sample input #4
1000000 30000

Sample output #4
32679639

Recommendation

We have carefully selected several similar problems: 3675 | 1005 | 3303 | 3232 | 1608 | 3277