Giftcard: Execution Timed Out

Buonasera,

ho provato a risolvere il problema togliendo il minore tra i due costi da N fintanto che N non è divisibile per il maggiore. Con questo approccio prendo 70/100 per TLE nei subtask 2 e 6; a parte per il subtask 2 che posso risolvere banalmente, non riesco proprio a pensare ad una soluzione più efficiente :thinking:.
Qualcuno che mi dà un aiutino? :roll_eyes:

Qua il codice, in caso serva: https://pastebin.com/gjSm2YcQ

Il problema richiede, in fin dei conti, di risolvere la seguente equazione diofantea lineare in due variabili (a e b):

a \cdot C_1 + b \cdot C_2 = N

che ha una sua precisa risoluzione (oltre ad andare “per tentativi”).

Naturalmente Google è tuo amico se vuoi suggerimenti su come si risolve :wink:

1 Mi Piace