Save the Barrels(butoaie) tutti i subtask 2 sbagliati

#1

Seguendo lo spoiler di TheScrasse che considera:

Usare K insetticidi di potenza P e N - K insetticidi di potenza Q è equivalente a usarne N di potenza Q e K di potenza P - Q

Ho fatto questa soluzione ma sbaglia tutti i subtask2 e anche alcuni degli altri subtask:

#include <bits/stdc++.h>

using namespace std;

ifstream in("input.txt");
ofstream out("output.txt");

void soluzione(long long rooms[], long long tot, long long num1, long long num2, long long ucc1, long long ucc2)
{
	long long max = 0;
	for(int i = 0; i<tot; ++i)
	{
		in >> rooms[i];
		if((rooms[i]/ucc1) > max) max = rooms[i]/ucc1;
	}
	long long day;
	long long min = 0;
	long long app;
	bool trovato = false;
	while(!trovato)
	{
		long long rim = 0;
		day = (min + max)/2;
		for(int i = 0; i<tot; ++i)
		{
			app = rooms[i] - day*ucc1;
			if(app < 0) app = 0;
			rim += app/ucc2;
			if(app%ucc2 != 0) ++rim;
		}
		if(max-min < 2)
		{
			trovato = true;
		}else if((rim-(day*num2))>0)
		{
			min = day;
		}else if((rim-(day*num2))<0)
		{
			max = day;
		}else
		{
			trovato = true;
		}
	}
	
	out << max;
}

main()
{
	long long tot,num1,num2,ucc1,ucc2;
	in >> tot >> num1 >> ucc1 >> ucc2;
	num2 = tot - num1;	
	long long rooms[tot];
	
	if(ucc1 < ucc2)
	{
		long long app;
		app = num1;
		num1 = num2;
		num2 = app;
		app = ucc1;
		ucc1 = ucc2;
		ucc2 = app;
	}
	
	soluzione(rooms, tot, tot, num1, ucc2, ucc1-ucc2);
}
#2

Io faccio un po’ fatica a leggere il codice degli altri… però intuitivamente se hai sbagliato circa la metà dei testcase potrei dirti che non hai considerato il caso in cui Q>P.

#3

Pero’ l’ho considerato…
Grazie cmq.

#4

Penso di aver trovato l’errore
Se non sbaglio il codice non risolve correttamente il testcase

4 3
4 1
0 0 0 100
1 Mi Piace
#5

Mi sembra che manchi un controllo stanza per stanza sull’uso di ucc2.
Dovresti controllare quanti giorni ti servono per portare a 0 i bachi presenti nella iesima stanza.
Se anche in una sola stanza …

2 Mi Piace
#6

Inoltre per il solito problema dei resti alzerei di un tantino max.
Ho provato la tua soluzione con questi due accorgimenti e va ( e anche piuttosto veloce).

#7

Avevo anche pensato a questa soluzione, ma non so come trattare il fatto che ci sono piu’ di uno ucc2 che si puo’ utilizzare contemporaneamente nelle stanze diverse.

#8

Si, non riesce a risolvere questo testcase

#9

Prova ad inserire nel ciclo for interno al while qualcosa tipo:

// giorni necessari per togliere tutti i bachi dalla stanza iesima
long long giorninecessari = app / ucc2;
if (app % ucc2 != 0) ++giorninecessari;
if (giorninecessari > day) {
rim = day * num2 + 1; // forza il test sotto a mettere inf=day
break; // esce dal ciclo, inutile proseguire
}

#10

Si, questo l’avevo gia’ calcolato.
Quello che ho sbagliato sarebbe stato il modo con cui verifico se quei giorni bastino per rimuovere tutti bachi.
Perche’ ho verificato se day*num2(perche’ ogni giorno posso utilizzare num2 insetticidi) sia maggiore di rim( che sono giorni che servono per rimuovere tutto il resto). Pero’ il testo dice che in una stanza va messo soltanto un insetticidio al giorno, quindi questo ragionamento sarebbe errato.
Penso di aver gia’ trovato la via giusta.
Grazie mille per l’aiuto

#11

Non mi sembra che il controllo fra rim e day*num2 sia errato anzi direi che vada fatto ma lo integrerei con l’altro:

for (int i = 0; i < tot; ++i)
{ app = rooms[i] - day * ucc1;
if (app < 0) app = 0;
if (app) {
giorninec = app / ucc2;
if (app % ucc2 != 0) ++giorninec;
if (giorninec > day) {
rim = day * num2 + 1;
break;
}
rim += app / ucc2;
if (app % ucc2 != 0) ++rim;
}
}