Ciao, sono giorni che cerco di risolvere blindpunch, ma il massimo che riesco ad ottenere è 0/100 con la metà dei test case giusti.
L’idea alla base del codice è che creo un multiset di struct in cui salvo la probabilità attuale di uccidere l’insetto, la probabilità iniziale e il numero di ciabatte che ho già tirato. Il set è ordinato in ordine decrescente in base alla probabilità attuale di uccidere l’insetto.
Grazie in anticipo per qualsiasi aiuto.
#include <assert.h>
#include <math.h>
#include <stdio.h>
#include <set>
#include <iostream>
// constraints
#define MAXN 200000
using namespace std;
// input data
struct insetti
{
long double attuale, iniziale, ciabatte;
bool operator< (const insetti& r) const
{
return attuale>r.attuale; //in modo da ordinare il multiset in ordine crescente
}
};
int T, N, K, i, j;
long double prob[MAXN]; //array
multiset<insetti> set_prob;
long double scegli(int K);
int main() {
// uncomment the following lines if you want to read/write from files
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
assert(1 == scanf("%d", &T));
for(i=0; i<T; i++) {
assert(2 == scanf("%d %d", &N, &K));
for(j=0; j<N; j++)
{
long double a;
insetti c;
assert(1 == scanf("%Lf", &a));
c.iniziale=a;
c.attuale=a;
c.ciabatte=0;
//cout << "attuale: " << c.attuale << " iniziale: " << c.iniziale << " ciabatte: " << c.ciabatte << endl;
set_prob.insert(c); //l'inizializzazione del set è corretta
//ordinato dal più grande al più piccolo
}
// insert your code here
long double result = scegli(K);
result = floor(result * 1000000) / 1000000; //NON TOCCARE
printf("%.6Lf\n", result);
}
return 0;
}
long double scegli(int K)
{
long double risultato=0;
while(K>0)
{
insetti max = *set_prob.begin(); //insetto con la prob attuale massima
insetti cambio = max; //insetto che uso per aggiornare il valore attuale del numero massimo
risultato+=max.attuale;
cambio.ciabatte++;
cambio.attuale=((cambio.iniziale)*pow((1-cambio.iniziale), cambio.ciabatte));
set_prob.erase(set_prob.begin()); //multiset quindi elimino solo l'elemento più grande
set_prob.insert(cambio);
K--;
}
return risultato;
}
