Já faz um tempo desde que você matou aquela hidra , você se deliciou com a glória por anos, mas agora as pessoas estão chamando você de lavada, um tem sido. Bem, é hora de você provar que estão errados. Você já ouviu o paradeiro de outra hidra. Basta matá-lo e você receberá toda a glória que você merece.

Você chega ao arsenal para receber suas espadas, mas todas elas estão fora das espadas regulares, tudo o que resta são os setores. Um setor n dividirá o número de cabeças em uma Hydra por n, mas só poderá ser usado se o número de cabeças for divisível por n.

Mais uma vez, você escreverá um código para ajudá-lo a matar a hidra. Seu código terá como entrada o número de cabeças da hidra, começa a briga, o número de cabeças que a hidra cresce a cada turno e uma lista de n setores que você pode usar. Seu código produzirá um padrão ideal de movimentos para matar a hidra o mais rápido possível

A cada turno da luta, você pode selecionar uma única espada para usar, se após uma fatia a hidra tiver apenas uma cabeça que você ganhar, se não, ela crescerá. Você nunca pode fazer nenhum movimento, e se não houver movimentos possíveis disponíveis, você perde.

Se nenhuma solução for possível, você poderá produzir outra coisa senão uma solução, por exemplo, uma lista vazia, nada, o número zero, etc.

Isso é código-golfe, então as respostas serão pontuadas conforme a contagem de bytes, com menos sendo melhores.

Casos de teste

Aqui estão alguns casos de teste super básicos, mais casos de teste serão adicionados mediante solicitação.

24 heads, 1  heads per turn, [2,3] -> [3,3,2,3]
25 heads, 2  heads per turn, [2,3] -> No solutions
4  heads, 2  heads per turn, [2]   -> No solutions
4  heads, 3  heads per turn, [2,5] -> [2,5]
10 heads, 17 heads per turn, [2, 3, 7, 19] -> No solutions
10 heads, 6  heads per turn, [1,16] -> [1,16]
6  heads, 2  heads per turn, [2, 3, 5] -> [2, 5]
125 heads, 1  head per turn, [1, 2, 3, 127] -> [1, 1, 127]

JavaScript (ES6), 111 105 bytes

Guardado 4 bytes graças a @ThePirateBay

(h,p,a)=>{for(b={[h]:[]};c=b,b=[];)for(d in c)for(e of a){d%e?0:q=b[d/e+p]=[...c[d],e];if(d==e)return q}}

Abaixei a recursão em profundidade que estava tentando usar para os loops de largura em primeiro lugar, muito mais seguros. Produz a solução como uma matriz, se existir, é executada para sempre, se não existir. Se isso não for permitido, aqui está um que acaba por parar (na maioria dos casos, de qualquer maneira):

(h,p,a)=>{for(b={[h]:[]};c=b,b=[],c+c;)for(d in c){for(e of a){a[[,d]]||d%e?0:q=b[d/e+p]=[...c[d],e];if(d==e)return q}a[[,d]]=1}}

JavaScript, 191 190 bytes

Guardou um byte graças a Step Hen

(h,t,s)=>eval(`r=[],d=0,q=[],s.map(a=>q.push([],h));while(q.length){p=q.shift(),h=q.shift(),s.map(w=>(a=h/w)==1?d=w:!(a%1)&!r[a+=t]?r[q.push([...p,w],a),a]=1:0);d?(q=[],p).push(d):0}d?p:[]`)

f=(h,t,s)=>eval(`r=[],d=0,q=[],s.map(a=>q.push([],h));while(q.length){p=q.shift(),h=q.shift(),s.map(w=>(a=h/w)==1?d=w:!(a%1)&!r[a+=t]?r[q.push([...p,w],a),a]=1:0);d?(q=[],p).push(d):0}d?p:[]`)

console.log(`[${f(24, 1, [2,3])}]`);
console.log(`[${f(25, 2, [2,3])}]`);
console.log(`[${f(4, 2, [2])}]`);
console.log(`[${f(4, 3, [2,5])}]`);
console.log(`[${f(10, 17, [2, 3, 7, 19])}]`);
console.log(`[${f(10, 6, [1,16])}]`);
console.log(`[${f(125, 1, [1, 16])}]`);
console.log(`[${f(1024, 3, [1, 2, 137])}]`);

Python 2 , 169 195 222 bytes

+26 bytes para lidar adequadamente com a regeneração cíclica da cabeça em más escolhas de armas. (Obrigado a @ThePirateBay por apontar isso)

+27 bytes para corrigir certos casos de borda que causam erros.

lambda n,p,w:g(n,n,p,w[::-1])[:-1]
def g(n,b,p,w,a=[]):
 if b<2:return[1]
 for x in w:
	if n%x<1and n/x+p!=n and n not in a:
	 try:
		l=[x]+g(n/x+p,n/x,p,w,[n]+a)
	 	if l and l[-1]!=0:return l
	 except:return[0]
 return[0]

Experimente online!

VB.NET (.NET 4.5), 439 + 35 (importações) = 474 bytes

Requer Imports System.Collections.Generic

Const N=Nothing
Function Z(h,r,a,Optional c=N,Optional p=N,Optional ByRef s=N)
If c Is N Then
c=New List(Of Long)
p=New List(Of Long)
End If
If s IsNot N And s?.Count<c.Count Then Return N
If p.Contains(h)Then Return N
p.Add(h)
For i=0To a.Count-1
Dim w=a(i)
If h Mod w=0Then
c.Add(w)
If h\w=1And(s Is N Or s?.Count>c.Count)Then
s=New List(Of Long)
s.AddRange(c)
End If
Z(h\w+r,r,a,c,p,s)
c.RemoveAt(c.Count-1)
End If
Next
Z=s
End Function

A função Zusa dois Int64(número de cabeças e taxa de regeneração da cabeça) e uma List(Of Int64)(Setores), e retorna um List(Of Int64) (the ordered choice of Sectors). ReturnsNothing` se não houver solução.

Assume que os setores são apresentados em ordem classificada do maior para o menor.

Os Optionalparâmetros são para as chamadas recursivas para salvar o estado. Eles rastreiam a ordem atual dos setores em uso, a ordem mais curta dos setores e o número de cabeças encontradas. Se encontrarmos o mesmo número de cabeças novamente, deve haver uma maneira mais curta de alcançá-lo.

A única ordem dos setores que importa é que preciso 1ser o último, se existir. Caso contrário, a hidra poderá crescer sem limites, porque eu poderia, a cada passo, usar o 1Setor e nunca tentar outro.

Declarei uma constante Npara representar Nothing, cortando 6 bytes cada vez que desejava usarNothing .

And/ Ornão estão em curto-circuito, portanto, uso o operador condicional nulo ( ?.) para evitar erros nulos no objeto. Em código real, eu usaria AndAlso/OrElse que faz curto-circuito.

Experimente online!

Z sem golfe para facilitar a leitura

Public Function Z(currentHeads As Long, regrowRate As Integer, weapons As ISet(Of Long), Optional currentWeapons As List(Of Long) = Nothing, Optional previousHeads As List(Of Long) = Nothing, Optional shortestWeapons As List(Of Long) = Nothing) As List(Of Long)

    ' initial call
    If currentWeapons Is Nothing Then
        currentWeapons = New List(Of Long)
        previousHeads = New List(Of Long)
    End If

    ' we've made more moves than our best so far
    If shortestWeapons IsNot Nothing AndAlso shortestWeapons.Count <= currentWeapons.Count Then
        Return Nothing
    End If

    ' exit, we've been here before
    If previousHeads.Contains(currentHeads) Then
        Return Nothing
    End If

    ' keep track of previous state to prevent duplicate paths
    previousHeads.Add(currentHeads)

    For Each w In weapons

        ' save 1 for last
        If w = 1 Then Continue For

        If currentHeads Mod w = 0 Then
            currentWeapons.Add(w)

            If currentHeads \ w = 1 Then
                If shortestWeapons Is Nothing OrElse shortestWeapons.Count > currentWeapons.Count Then
                    shortestWeapons = New List(Of Long)(currentWeapons)
                End If
            End If

            Dim answer = A(currentHeads \ w + regrowRate, regrowRate, weapons, currentWeapons, previousHeads, shortestWeapons)
            If answer IsNot Nothing Then
                If shortestWeapons Is Nothing OrElse shortestWeapons.Count > answer.Count Then
                    shortestWeapons = New List(Of Long)(answer)
                End If
            End If

            currentWeapons.RemoveAt(currentWeapons.Count - 1)
        End If
    Next

    If weapons.Contains(1) Then
        currentWeapons.Add(1)

        Dim answer = A(currentHeads \ 1 + regrowRate, regrowRate, weapons, currentWeapons, previousHeads, shortestWeapons)
        If answer IsNot Nothing Then
            If shortestWeapons Is Nothing OrElse shortestWeapons.Count > answer.Count Then
                shortestWeapons = New List(Of Long)(answer)
            End If
        End If

        currentWeapons.RemoveAt(currentWeapons.Count - 1)
    End If

    Return shortestWeapons
End Function