Sto cercando di svolgere questo problema ma sto trovando molte più diffcolta di quante me ne aspettassi:
Io penso di aver trovato una buona soluzione nel caso in cui i i numeri sono tutti diversi tra di loro:
- Li ordino
-Verifico quanto risulta il prodotto tra il più piccolo ed il più grande:
Se è maggiore di k significa che il mio valore piu grande è inutile(perche se supera la soglia con il
valore mininmo la supera con tutti i valori)
Se è uguale tolgo il primo ed aumento di uno il numero di soluzioni
se è minore di k allora tolgo soloil primo senza aumentare le soluzioni
ho capito che ci sono 2 errori:
1 quanto trovo che il prodotto è uguale a k non va sempre bene togliere il primo perche nel caso in cui ho per esempio
2 2 10 10 con k=20 e n=4
con il mio algoritmo da come risultato 2 e non 4
2 che è molto simile al primo lo posso trovare nel secondo caso d’esempio ossia n=3 k=9
e come valori 3 3 3 io cosi trovo solo 2 soluzioni e non 3
ma la cosa che non capisco è se effittivamente nei subtask provati c’è solo un caso dove i valori sono tutti differenti oppure se sbaglio qualcosa anche in quel caso, perche nel caso in cui i valori sono tutti differenti non si presenta nessuno degli errori che ho detto prima
il codice: https://pastebin.com/EZWySLxT
