# Save The Barrels(butoaie) 0/100

**URL:** <https://forum.olinfo.it/t/save-the-barrels-butoaie-0-100/7288>\
**Category:** Aiuto\
**Created:** [23 Aprile 2022, 6:44pm UTC](https://forum.olinfo.it/t/save-the-barrels-butoaie-0-100/7288 "2022-04-23T18:44:01Z")\
**Posts on this page:** 6\
**Page:** 1

<div class="post-metadata">

**Author:** ![alenygam\_real](https://forum.olinfo.it/user_avatar/forum.olinfo.it/alenygam_real/32/1364_2.png) [@alenygam\_real](https://forum.olinfo.it/u/alenygam_real)\
**Post date:** [23 Aprile 2022, 6:44pm UTC](https://forum.olinfo.it/t/save-the-barrels-butoaie-0-100/7288/1 "2022-04-23T18:44:01Z")

</div>

Sto provando a risolvere il problema butoaie e, fino ad ora, sono arrivato ad una soluzione in cui:

- Uso la ricerca binaria per trovare una possibile soluzione
- Calcolo per ogni stanza quanti insetticidi potenti ho bisogno
- Se in quella stanza il numero di insetticidi potenti di cui ho bisogno supera la quantità di giorni trovata con la ricerca binaria, esco automaticamente essendo una soluzione impossibile da risolvere
- Altrimenti, se la quantita di insetticidi potenti necessaria è maggiore di nPotenti \* giorno, allora guardo a destra, altrimenti a sinistra.

Questo è il codice:

```auto
#include <bits/stdc++.h>

using namespace std;

int main() {
	int N, K, P, Q;
	cin >> N >> K >> P >> Q;
	vector<int> stanze(N);
	for (int i = 0; i < N; i++) {
		cin >> stanze[i];
	}

	int nPotenti = N - K;
	int nScarsi = K;
	int potenti = Q;
	int scarsi = P;
	if (scarsi > potenti) {
		swap(potenti, scarsi);
		swap(nScarsi, nPotenti);
	}

	int left = 0;
	int right = 1e7;
	while (left <= right) {
		int mid = (left + right) / 2;
		int needed = 0;
		for (int i = 0; i < N; i++) {
			if (stanze[i] <= scarsi * mid) continue;

			int duh = (stanze[i] - (scarsi * mid) + potenti - scarsi - 1) / (potenti - scarsi);
			if (duh > mid) {
				needed += nPotenti * mid + 1;
				break;
			}
			needed += duh;
		}
		if (needed <= nPotenti * mid) {
			right = mid - 1;
		} else {
			left = mid + 1;
		}
	}
	cout << right + 1 << '\n';
}

```

---

<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:** [24 Aprile 2022, 10:53am UTC](https://forum.olinfo.it/t/save-the-barrels-butoaie-0-100/7288/2 "2022-04-24T10:53:20Z")

</div>

Ciao, devi solo utilizzare long long nella bs e aumentare il limite superiore.

---

<div class="post-metadata">

**Author:** ![alenygam\_real](https://forum.olinfo.it/user_avatar/forum.olinfo.it/alenygam_real/32/1364_2.png) [@alenygam\_real](https://forum.olinfo.it/u/alenygam_real)\
**Post date:** [24 Aprile 2022, 11:18am UTC](https://forum.olinfo.it/t/save-the-barrels-butoaie-0-100/7288/3 "2022-04-24T11:18:54Z")

</div>

ho cambiato tutti gli int in long long e alzato il limite massimo a 1e18, ma ancora mi esce 0/100…

---

<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:** [24 Aprile 2022, 11:20am UTC](https://forum.olinfo.it/t/save-the-barrels-butoaie-0-100/7288/4 "2022-04-24T11:20:31Z")

</div>

ho utilizzato 1e9.

---

<div class="post-metadata">

**Author:** ![alenygam\_real](https://forum.olinfo.it/user_avatar/forum.olinfo.it/alenygam_real/32/1364_2.png) [@alenygam\_real](https://forum.olinfo.it/u/alenygam_real)\
**Post date:** [24 Aprile 2022, 11:46am UTC](https://forum.olinfo.it/t/save-the-barrels-butoaie-0-100/7288/5 "2022-04-24T11:46:18Z")

</div>

utilizzando 1e9 fa 80/100, sbagliando i primi 4 del subtask 2 😔. Credo che ci sia qualche problema con la mia ricerca binaria.

---

<div class="post-metadata">

**Author:** ![alenygam\_real](https://forum.olinfo.it/user_avatar/forum.olinfo.it/alenygam_real/32/1364_2.png) [@alenygam\_real](https://forum.olinfo.it/u/alenygam_real)\
**Post date:** [24 Aprile 2022, 11:48am UTC](https://forum.olinfo.it/t/save-the-barrels-butoaie-0-100/7288/6 "2022-04-24T11:48:17Z")

</div>

Si. Nell’ultimo if ho cambiato da \< a \<= e ora fa 100/100. Grazie mille