Ajude Beth a escapar do deserto

11

Embora parecido com o outro quebra-cabeça de transporte de água , os aspectos únicos desse desafio o tornam totalmente diferente.

Beth

Beth está localizada em um oásis no meio de um deserto. Há muita água no lago, mas infelizmente existem apenas X baldes, cada um dos quais com capacidade para litros de água.

Beth pode carregar 2 baldes nas mãos, mas para sobreviver, ela deve beber exatamente 1 litro após cada quilômetro percorrido. Ela também pode deixar alguns baldes até a metade (a água não evapora).

O desafio

Descubra a fórmula e escreva a solução mais curta que funcionará para valores inteiros positivos de X e Y e calcule a distância máxima que Beth pode percorrer do oásis. É permitido mover água entre os baldes.

Exemplo

X = 3, Y = 5

  1. Beth deixa 1 balde cheio a 3 km do oásis e volta (tomando a última bebida do oásis)
  2. Beth traz outro balde cheio no ponto 3KM, tendo 12L lá agora.
  3. Beth pode avançar para o ponto 6KM e deixar um balde com 4L de água.
  4. Volte ao ponto 3KM. Ela agora tem exatamente 2 litros para voltar ao oásis.
  5. Encha as caçambas e viaje até o ponto 6KM. Ela agora tem 8 litros de água.
  6. Continue até o ponto de 15 km.

Resposta é: 15

Entrada / Saída

Você pode definir X / Y diretamente no código ou ler da entrada. O resultado pode ser colocado na variável ou na saída, o que for menor.

romaninsh
fonte
2
Isso deveria ser código de golfe? É marcado como um desafio de código.
Dennis
Sim, é código-golfe, eu adicionei a tag. Crie uma fórmula correta e expresse-a através do código.
romaninsh
1
Eu acho que vale a pena expandir no passo 1. No começo, não estava claro para mim como Beth poderia viajar 6 km com apenas 5 litros de água: ela bebe somente após cada km que viaja e, finalmente, no oásis.
Xnor
1
Você poderia dar um caso de teste, da maneira que um programa o produziria?
Pavel
Editou a pergunta para abordar os dois pontos.
romaninsh

Respostas:

2

JavaScript (ES6), 25 bytes

x=>y=>((x<3?x:3)+x)*y/2+1
x=>y=>(x<3?x+x:x+3)*y/2+1
x=>y=>(x<3?x:(x+3)/2)*y+1
x=>y=>(x<3?x:x/2+1.5)*y+1

Tudo isso calcula o mesmo valor; Não consigo pensar em uma formulação mais curta.

Quando xé menor 3, você pega o máximo de água possível e caminha o mais longe possível, o que é simples x*y+1.

Quando xé pelo menos 3, você deve começar a criar caches.

Do oásis, você pode deixar um balde cheio à distância y/2e retornar ao oásis. Você precisa de 2 baldes para fazer isso, mas isso não é útil se você tiver apenas 2 baldes, porque deseja poder encher 2 baldes quando retornar ao oásis.

No oásis, com um balde à distância y/2, você pode deixá-lo à distância ye retornar ao oásis. Você precisa de 3 baldes para fazer isso.

Do oásis, com baldes cheios em ambos ye y/2, você pode deixar um balde cheio à distância 3y/2e retornar ao oásis. Você precisa de 4 baldes para fazer isso. Você então precisa deixar um balde cheio a uma distância y/2e retornar ao oásis.

Eventualmente, você pode acabar com um balde cheio em (x-1)y/2. (Você não pode deixar um balde cheio xy/2porque não seria capaz de voltar ao oásis, pois a ida e volta é xya capacidade total dos baldes.)

Usando seus baldes restantes, você pode deixar baldes cheios em (x-3)y/2... you y/2. Nesse ponto, você simplesmente caminha o mais longe que pode, pegando seus baldes cheios à medida que avança. Quando você chega, (x-1)y/2ainda tem dois baldes cheios, o que lhe permite chegar (x+3)y/2.

O extra 1vem da peculiaridade das regras, permitindo que você ande sua última milha sem ter água. Embora o exemplo mostre que você pode deixar os baldes um pouco mais afastados do que o descrito acima, isso na verdade não ajuda a caminhar mais, pois você precisa deixar menos água ou beber a água do balde ao alcançá-lo antes de poder se mover em.

Neil
fonte