# Black Friday (giftcard)

**URL:** <https://forum.olinfo.it/t/black-friday-giftcard/8791>\
**Category:** Aiuto\
**Created:** [12 Marzo 2024, 10:49am UTC](https://forum.olinfo.it/t/black-friday-giftcard/8791 "2024-03-12T10:49:28Z")\
**Posts on this page:** 7\
**Page:** 1

<div class="post-metadata">

**Author:** ![lollospadalaser](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/l/35a633/32.png) [@lollospadalaser](https://forum.olinfo.it/u/lollospadalaser)\
**Post date:** [12 Marzo 2024, 10:49am UTC](https://forum.olinfo.it/t/black-friday-giftcard/8791/1 "2024-03-12T10:49:28Z")

</div>

Ho risolto [questo](https://training.olinfo.it/#/task/ois_giftcard/statement) 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.

---

<div class="post-metadata">

**Author:** ![qwfwq](https://forum.olinfo.it/user_avatar/forum.olinfo.it/qwfwq/32/2974_2.png) [@qwfwq](https://forum.olinfo.it/u/qwfwq)\
**Post date:** [12 Marzo 2024, 10:06pm UTC](https://forum.olinfo.it/t/black-friday-giftcard/8791/2 "2024-03-12T22:06:00Z")

</div>

> [@lollospadalaser](#):
>
> Tuttavia questa non mi sembra la soluzione “corretta” perché per scrivere questa ho dovuto utilizzare per forza python.

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**.

---

<div class="post-metadata">

**Author:** ![lollospadalaser](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/l/35a633/32.png) [@lollospadalaser](https://forum.olinfo.it/u/lollospadalaser)\
**Post date:** [18 Marzo 2024, 4:37pm UTC](https://forum.olinfo.it/t/black-friday-giftcard/8791/3 "2024-03-18T16:37:37Z")

</div>

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.

---

<div class="post-metadata">

**Author:** ![qwfwq](https://forum.olinfo.it/user_avatar/forum.olinfo.it/qwfwq/32/2974_2.png) [@qwfwq](https://forum.olinfo.it/u/qwfwq)\
**Post date:** [18 Marzo 2024, 10:01pm UTC](https://forum.olinfo.it/t/black-friday-giftcard/8791/4 "2024-03-18T22:01:08Z")

</div>

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

Se come penso stai utilizzando l’identità:

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

```

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

```auto
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**.

---

<div class="post-metadata">

**Author:** ![lollospadalaser](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/l/35a633/32.png) [@lollospadalaser](https://forum.olinfo.it/u/lollospadalaser)\
**Post date:** [19 Marzo 2024, 2:46pm UTC](https://forum.olinfo.it/t/black-friday-giftcard/8791/5 "2024-03-19T14:46:41Z")

</div>

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?

---

<div class="post-metadata">

**Author:** ![qwfwq](https://forum.olinfo.it/user_avatar/forum.olinfo.it/qwfwq/32/2974_2.png) [@qwfwq](https://forum.olinfo.it/u/qwfwq)\
**Post date:** [21 Marzo 2024, 9:24pm UTC](https://forum.olinfo.it/t/black-friday-giftcard/8791/6 "2024-03-21T21:24:13Z")

</div>

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.

---

<div class="post-metadata">

**Author:** ![lollospadalaser](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/l/35a633/32.png) [@lollospadalaser](https://forum.olinfo.it/u/lollospadalaser)\
**Post date:** [22 Marzo 2024, 8:00am UTC](https://forum.olinfo.it/t/black-friday-giftcard/8791/7 "2024-03-22T08:00:53Z")

</div>

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

Grazie.