Black Friday (giftcard)

Aiuto
1

Ho risolto questo problema.
quello che ho fatto è: dividere N,C1,C2 per il loro gcd, trovare due interi x e y tali che xC1 + yC2 = 1 poi ho moltiplicato x e y per N, in questo modo ho trovato un risultato corretto, il problema è che x e y devono essere maggiori o uguali a 1, però da qua diventa poi facile sistemare x e y in modo che la loro somma sia minima.

Tuttavia questa non mi sembra la soluzione “corretta” perché per scrivere questa ho dovuto utilizzare per forza python che non ha quasi limiti alla grandezza degli Int, qualcuno riuscirebbe a darmi qualche idea su quale sia il modo “corretto” per risolverlo? Per “corretto” intendo il modo in cui é stato pensato.

2

Linguaggio a parte la soluzione si ottiene, comunque, con il procedimento che hai suggerito. Ma con i seguenti constraints:

  • 2 \leqslant N < 2^{64}
  • 1 \leqslant C1, C2 \leqslant N

in C++, per risolvere il corrispondente task, ci rientri con gli unsigned long long.

3

Scusa ma non ho capito proprio il consiglio
Risolvendo xC1 + yC2 = 1 x e y potrebbero anche essere negativi, inoltre nel caso in cui 2^{63}<N < 2^{64} se x,y \neq 1 si fa in overflow.

4

Risolvendo xC1 + yC2 = 1, x e y potrebbero anche essere negativi.

Se come penso stai utilizzando l’identità:

xC1 + yC2 = g dove g = gcd(C1, C2)

allora è vero che x e y potrebbero negativi, ma Il task chiede che sia:

xC1 + yC2 = N

e c’è anche il constraint che dice testualmente:

• It is guaranteed that a solution exists.

quindi x e y devono essere interi positivi e per non incorrere nell’overflow, nel caso in questione, è utile usare unsigned long long.

1 Mi Piace
5

per trovare xC1 + yC2 = N ho prima trovato xC1 + yC2 = 1 con l’algoritmo di Euclide e poi ho moltiplicato per N x e y. In questo modo si va in overflow, l’unico altro modo che mi viene in mente è (mettiamo che C2 > C1):
calcolare xC1 + yC2 = N (mod C2) => xC1 = N mod C2 e poi risolvere.

Sarebbe questo il metodo per evitare di andare in overflow?

6

Seguendo il tuo metodo, per non finire in overflow in C++ , è opportuno utilizzare variabili unsigned long long in input/output e __int128_t per tutte le altre operazioni.

7

c’è un modo per risolvere il tutto solo con unsigned long long?

Grazie.