Jesteś najlepszym i najbardziej znanym bohaterem tego obszaru. Ostatnio pojawiły się pogłoski, że Hydra przebywała w pobliskim wąwozie. Uważasz, że będąc odważnym i cnotliwym bohaterem, możesz to sprawdzić dzisiaj.

Problem z hydrą polega na tym, że za każdym razem, gdy próbujesz odciąć im głowy, niektóre nowe odrastają. Na szczęście masz miecze, które mogą odciąć wiele głów jednocześnie. Ale jest haczyk, jeśli hydra ma mniej głów niż ciosy mieczem, nie będziesz w stanie zaatakować hydry. Kiedy hydra ma dokładnie zero głów, zabiłeś ją.

Istnieje również specjalny miecz o nazwie Bisector , który odetnie połowę głów Hydry, ale tylko wtedy, gdy liczba głów będzie równa. Dwusieczna nie może być w ogóle używana, gdy liczba głów jest nieparzysta. Różni się to od odcinania głowic zerowych.

Zdecydowałeś się napisać program komputerowy, aby dowiedzieć się, jak najlepiej zabić hydrę.

Zadanie

Otrzymasz jako dane wejściowe

• liczba głowic, od których zaczyna się Hydra
• liczba głów Hydry odrasta w każdej turze
• lista dostępnych do użycia mieczy (każda z nich jest dwusieczna lub tnie określoną liczbę głów w każdej turze)

Powinieneś wypisać listę ruchów, które zabiją hydrę w jak najmniejszej liczbie tur. Jeśli nie ma sposobu na zabicie hydry, musisz podać inną wartość wskazującą to (a pusta lista jest w porządku, jeśli twój język jest mocno wpisany). Jeśli istnieje wiele optymalnych sposobów na zabicie hydry, możesz wydać jeden lub wszystkie z nich.

To jest pytanie w golfa kodu, więc odpowiedzi będą oceniane w bajtach, przy czym mniej bajtów będzie lepszych.

Przypadki testowe

Więcej dostępnych na żądanie

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]

To pytanie jest uproszczoną wersją głównej mechaniki HydraSlayer . Jeśli podoba Ci się ten rodzaj układanki, polecam sprawdzić, jest całkiem fajnie. Nie mam żadnego związku z grą.

JavaScript, 230 223 bajtów

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])}]`);

Wersja bez golfa:

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:[];
}

Dwusieczny jest reprezentowany jako 0.