Illuminazione di sala testcase 43-44-45

Aiuto
1

Ho provato a risolvere il problema luci/illuminazione di sala e nonostante il mio programma sia molto semplice e abbia ottenuto 70 punti, negli ultimi tre subtask mi va fuori tempo limite. A qualcuno succede la stessa cosa?

2

Non c’è bisogno di fare alcun tipo di iterazione, ma solo una dimostrazione matematica.
Se una luce X parte da accesa, cosa succede se la accendo e la spengo un numero pari di volte? E un numero dispari?
E quali bottoni accendono la luce X?
E quali luci vengono accese da un numero pari di interruttori?
:wink:

3

Si, a questo ci ero arrivato. Forse mi sono spiegato male: credo ci sia proprio un problema nel compilare quei 3 testcase

4

Ne dubito, altrimenti nessuno avrebbe 100 :stuck_out_tongue:
Posta il codice, magari fai delle iterazioni o dei calcoli in piĂą (il problema si risolve anche in una riga volendo).

5 
int spegni(int N, int M, int K) {
	int a=4;
	int b=1;
	for(int i=2; i<=N; i++) {
		if(i==a) {
			b++;
			a=sqrt(a);
			a=a+1;
			a=pow(a,2);
		}
	}
	return N-b;
}
6

Per sapere il numero di quadrati perfetti in [1,N] è proprio necessario un ciclo?

1 ≤ a2 ≤ N ⇒ ???

7

Grazie mille sono riuscito a risolvere il problema!

8

Dimostrazione/ ragionamento dal punto di vista matematico?

9

Dimostrazione per trovare il numero di quadrati perfetti o del perchè si usano i quadrati perfetti?

1 Mi Piace
10

Del perché, dove è il collegamento a quello che chiede il problema?

11

Prova a pensare al numero di divisori di ogni numero. Nel problema sappiamo che rimarranno accese tutte le luci che hanno un numero pari di divisori e si spegneranno tutte quelle che ne hanno un numero dispari.
Cerchiamo ora di trovare quali numeri hanno un numero dispari di divisori.

Il numero di divisori di un numero si può ottenere dalla sua fattorizzazione in numeri primi moltiplicando gli esponenti più uno di ognuno dei fattori tra loro:

N = p1^e1 * p2^e2 * ... * pn^en
d(N) = (e1 + 1) * (e2 + 1) * ... * (en + 1)

Sapendo questo, possiamo provare a ottenere un numero che abbia un numero dispari di divisori. Affinchè il numero di divisori, indicato con d(N), sia dispari, tutti i numeri che vengono moltiplicati tra loro per ottenerlo devono essere dispari. Quindi, se ogni (ei + 1) deve essere dispari, tutti gli esponenti devono essere pari.

Un numero che nella sua fattorizzazione ha solo esponenti pari è un quadrato perfetto, infatti se:

N = p1^(2*e1) * p2^(2*e2) * ... * pn^(2*en)

allora

N = (p1^e1 * p2^e2 * ... * pn^en) ^ 2

Quindi i problema si riduce a trovare tutti i numeri nell’intervallo specificato che non sono quadrati perfetti, ovvero N meno il numero di quadrati perfetti, ovvero N - sqrt(N)

Dario

1 Mi Piace