Estás preso num
enorme labirinto em espiral! O labirinto pode ser visto como uma
grelha rectangular onde existe um único e enorme corredor em espiral
onde as várias posições do corredor (células da grelha) são numeradas
consecutivamente com números inteiros, tal como ilustrado na figura
seguinte (as linhas pretas são paredes):
Tu estás na posição nº 1 e acabas de ouvir uma voz grave e profunda anunciando a posição do labirinto onde se encontra um alçapão com a saída. Cansado como estás, pretendes encontrar a maneira mais rápida de chegar desde a posição 1 até à saída.
Por sorte, tens contigo disponíveis um conjunto de barras de dinamite que podes usar para fazer explodir algumas paredes e abrir caminho até à saída. Cada barra de dinamite serve para fazer explodir uma única parede e abrir caminho entre duas posições que dantes estavam separadas precisamente por uma parede. Podes por exemplo usar uma barra de dinamite para fazer explodir a parede entre as posições 4 e 15, entre a 13 e a 30 ou entre a 7 e a 20.
Tens de encontrar o menor caminho entre a posição 1 e a saída, sabendo que podes usar a dinamite para encurtar esse caminho. Para medir o tamanho de um caminho, considera que demoras uma unidade de tempo para te moveres para uma posição adjacente na vertical ou horizontal. Se não existir parede entre duas posições adjacentes, podes efectuar esse movimento. Caso contrário, só o podes efectuar se gastares uma barra de dinamite para explodir a parede que separa as duas posições.
Exemplificando, considera que a saída está na posição 31. Nesse caso, se tiveres exactamente uma barra de dinamite, o menor caminho tem tamanho 14. A figura seguinte ilustra uma dos possíveis caminhos com esse tamanho, passando por uma única parede dinamitada entre 13 e 32. O caminho é: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 32, 31.
Se por acaso tivesses 2 barras de dinamite, o menor caminho teria tamanho 6. Um caminho possível com esse tamanho seria o ilustrado na figura seguinte.
Com 3 barras de dinamite para usar, o menor caminho continuaria a ter tamanho 6.
Dada a posição da saída S e o número B de barras de dinamite ao teu dispor, a tua tarefa é encontrar o menor caminho entre a posição 1 e a saída S, dinamitando no máximo B paredes.
O input é constituído por uma única linha contendo dois inteiros S e B, separados por um único espaço, indicando respectivamente a posição da saída e o número de barras de dinamite que se encontram ao teu dispor.
O output deve ser constituído por uma única linha contendo um número inteiro indicando o tamanho do caminho mínimo entre a posição 1 e a saída S, dinamitando no máximo B paredes.
São garantidos os seguintes limites em todos os casos de teste que irão ser colocados ao programa:
| 2 ≤ S ≤ 100 000 000 | Posição da saída | |
| 0 ≤ B ≤ 1 000& | Número de barras de dinamite |
Para um conjunto de casos de teste valendo 10% dos pontos, o número B de barras de dinamite é zero. Para um conjunto de casos de teste valendo 60% dos pontos, S é menor do que 100 000 e B é menor que 10.
31 1
14
31 2
6