Você é o melhor e mais famoso herói da região. Ultimamente, existem rumores de que uma Hydra está saindo em um barranco próximo. Sendo o herói corajoso e virtuoso que você é, você vai descobrir isso hoje mais tarde.

O problema com as hidras é que, toda vez que você tenta cortar a cabeça, algumas novas crescem. Felizmente para você, você tem espadas que podem cortar várias cabeças ao mesmo tempo. Mas há um problema: se a hidra tiver menos cabeças do que a espada cortada, você não poderá atacá-la. Quando a hidra tem exatamente zero cabeças, você a matou.

Há também uma espada especial chamada The Bisector que cortará metade das cabeças da Hydra, mas apenas se o número de cabeças for igual. O Bisector não pode ser utilizado quando o número de cabeças é ímpar. Isso é diferente de cortar zero cabeças.

Então você decidiu que escreverá um programa de computador para descobrir a melhor maneira de matar a hidra.

Tarefa

Você será dado como entrada

• o número de cabeças que a Hydra começa com
• o número de cabeças que a Hydra regrows a cada turno
• uma lista de espadas disponíveis para uso de cada uma (cada uma é uma bissetor ou corta um número fixo de cabeças a cada turno)

Você deve produzir uma lista de movimentos que matarão a hidra no menor número de turnos possível. Se não houver como matar a hidra, você deve gerar algum outro valor indicando isso (e a lista vazia será boa se o seu idioma for fortemente digitado). Se houver várias maneiras ótimas de matar a hidra, você poderá produzir qualquer uma delas ou todas elas.

Esta é uma questão de código-golfe, para que as respostas sejam pontuadas em bytes, com menos bytes sendo melhores.

Casos de teste

Mais disponível mediante solicitação

5 heads, 9 each turn,  [-1,-2,-5] -> [-5]
12 heads, 1 each turn, [/2,-1] -> No solution
8 heads, 2 each turn,  [-9, -1] -> [-1,-9]
3 heads, 23 each turn, [/2,-1,-26] -> [-1,-1,-26,-26,-26,-26,-26,-26,-26,-26]
16 heads, 1 each turn, [/2, 4, 2] -> [/2,-4,/2,-4]

Esta pergunta é uma versão simplificada do principal mecânico do HydraSlayer . Se você gosta desse tipo de quebra-cabeça, recomendo que seja divertido. Eu não tenho nenhuma afiliação com o jogo.

JavaScript, 230 223 bytes

f=(h,t,s)=>{m=h-Math.min(...s),d=1,q=[],s.map(a=>q.push([],h));while(q.length){p=q.shift(),h=q.shift(),s.map(w=>!(a=w?h+w:h/2)?d=w:!(a%1)&a>0&a<m&!f[a+=t]?f[q.push([...p,w],a),a]=1:0);d<1?(q=[],p).push(d):0}return d<1?p:[]}

_=_=>f=(h,t,s)=>{m=h-Math.min(...s),d=1,q=[],s.map(a=>q.push([],h));while(q.length){p=q.shift(),h=q.shift(),s.map(w=>!(a=w?h+w:h/2)?d=w:!(a%1)&a>0&a<m&!f[a+=t]?f[q.push([...p,w],a),a]=1:0);d<1?(q=[],p).push(d):0}return d<1?p:[]}

console.log(`[${_()(5, 9,  [-1,-2,-5])}]`);
console.log(`[${_()(12, 1, [0,-1])}]`);
console.log(`[${_()(8, 2,  [-9,-1])}]`);
console.log(`[${_()(1, 2,  [0,-4])}]`);
console.log(`[${_()(3, 2,  [0,-4,-1])}]`);
console.log(`[${_()(3, 4,  [0,-4,-1])}]`);
console.log(`[${_()(3, 23, [0,-1,-26])}]`);
console.log(`[${_()(16, 1, [0,-4,-2])}]`);

Versão não destruída:

f=(heads,turn,swords)=>{
  max=heads-Math.min(...swords);

  found=1;
  flags=[];
  queue=[];
  swords.map(a=>queue.push([],heads));

  while(queue.length){
    path=queue.shift();
    heads=queue.shift();

    swords.map(sword=>{
      after=sword?heads+sword:heads/2;

      if(!after){
        found=sword;
      }else if(!(after%1)&after>0&after<max&!flags[after+=turn]){
        flags[after]=1;
        queue.push([...path,sword],after);
      }
    });

    if(found<1){
      path.push(found);
      break;
    }
  }

  return found<1?path:[];
}

A bissetriz é representada como 0.