Aiutino ? Numerological prediction (bloomsday)

Aiuto
1

Un’aiutino per risolvere il problema (https://training.olinfo.it/#/task/ois_bloomsday/statement) entro il tempo limite?

Questo é il codice più o meno…

Probabilmente c’è qualche relazione tra i numeri che aumentano con una progressone definita non saprei…
O magari si sa ogni quanti numeri appaiono i numeri composti da nCifre+1 cifre… non so la butto li…

Dubito si possa risolvere in O(1) (almeno spero non si possa :frowning: )
Credo che invece O(N) sia fattibile (?)

In ogni caso facendolo cosi il problema é il metodo lunghezza e pow…
in quanto lunghezza dato il numero generato restituisce il numero di cifre , la “lunghezza”

pow invece , la potenza suppongo sia un for di moltiplicazioni…

cin >> K >> E >> N;

int salti = lunghezza(K);
int pos = 1;

for(;salti<N;pos++){
    salti += lunghezza(K*pow(pos,E));
}

cout << pos-1;

Oltretutto… i primi quattro output li sbaglia , mentre i restati li fa giusti se non per il tempo dove non posso dire cosa fa…

Ho provato a cambiare il metodo lunghezza in varii modi tra i quali :

int lunghezza(long long numero) return (int) log10((double) numero) + 1;

int lunghezza(long long numero){
int cifre = 0;
while (numero) {
numero/= 10;
cifre ++;
}
return cifre ;
}

e …

int lunghezza(long long x){
return (x < 10 ? 1 :
(x < 100 ? 2 :
(x < 1000 ? 3 :
(x < 10000 ? 4 :
(x < 100000 ? 5 :
(x < 1000000 ? 6 :
(x < 10000000 ? 7 :
(x < 100000000 ? 8 :
(x < 1000000000 ? 9 :
10)))))))));
}

Ma non é cosi che che va risolto…

Poi ho pensato , andando avanti posso trovare numeri lunghi tanto quanto il numero preso in precedenza , o più grandi di una cifra… quindi ho provato a modificare il metodo lunghezza anche tenendo conto di questo , ma nulla da fare :smiley:

A sto punto credo il problema sia su quel pow dei poveri e che ci sia una relazione tra la progressione dei numeri…
Aiutino plz :blush:

Cercate di “farmici arrivare” grazie :smiley:

2

Ciao,
una volta che hai trovato il numero più grande di k cifre e il numero più grande di k+1 cifre puoi anche sapere il numero complessivo di cifre che ci sono senza dover calcolare la lunghezza di ciascuno numero compreso nell’intervallo.

2 Mi Piace
3

Giusto… infatti è O(\log_{10}(N)) (circa, sono pigro per calcolare la complessità) (tralascio E e K in quanto sono piccoli).

Ti do un hint:

inizia ponendoti il problema di capire qual è il più piccolo h tale che K\cdot h^E abbia d cifre, in altre parole K\cdot h^E \geq 10^{d-1};

Hint 2: se hai mai fatto le olimpiadi di matematica forse avrai riconosciuto questo problema, che di norma è semplice poiché K=E=1…pensa a come risolvere questo sottocaso.

Con mia grande sorpresa devo dire che pow è fattibile, e ti ho anche per metà detto come.

Per chi ha già risolto:

Un modo per evitare i long double per l’ultimo test case? Ci penso da tutto il giorno, ma non mi viene in mente niente di numericamente stabile

1 Mi Piace
4

Same, con gli __int128 va in overflow, i double non hanno abbastanza precisione, solo con i long double fa 100

2 Mi Piace
5

Il problemino é che non capisco come sapere quanti numeri ci sono in quell’intervallo, in quanto il numero di numeri presenti in ogni intervallo ogni volta che il numero di cifre aumenta , cambia… :C

6

No aspe non ho capito… scusa é che oramai ho in testa la mia soluzione sbagliata quindi faccio fatica a comprendere soluzioni diverse dalla mia :smile:

7

Generalmente le padellate in testa sono un buon modo per dimenticare. Però presenta varie controindicazioni :grinning:

I numeri 1..9 hanno tutti una cifra e sono 9. Ergo, la somma sul numero delle cifre è 9. Invece abbiamo poi 10..99 e sono 90 numeri da 2 cifre. Ergo, abbiamo la somma pari ha 9 + 2\cdot 90 = 189, e così via.

La domanda è: come ottengo quel 9, 99, 999 ...?
L’osservazione fondamentale è che sono derivanti da potenze del tipo 10^d-1.

Prova a sviluppare la disuguaglianza che ti ho dato nell’hint e otterrai
h \geq \sqrt[E]{\frac{10^{d-1}}{K} } Tronca per eccesso e avrai determinato il più piccolo numero di d cifre. Il resto dovrebbe essere fuffa. Se diamo un indice ad h, del tipo h_i = \text{primo numero ad avere }i \text{ cifre} allora il numero di numeri di d cifre è h_{d+1} - h_d. E il numero di cifre totali è di conseguenza d\cdot(h_{d+1} - h_d). Continua tu.

se non riesci a leggere la formula è colpa dell’effetto blur, basta che vedi il sorgente del messaggio e lo riesci a comprendere

1 Mi Piace
8

Supponiamo di aver trovato un numero p tale che K\cdot p^E abbia d cifre, poi abbiamo trovato un numero q >p tale che K\cdot q^E abbia d cifre, puoi certo notare che è inutile calcolare il numero di cifre per ogni numero compreso tra p e q, poiché sarà sempre uguale a d. Il nostro obbiettivo è di massimizzare questa strategia e quindi scegliere p e q il più possibili distanti tra di loro. Il numero di cifre complessive sarà poi dato da (q-p+1)\cdot d. Praticamente per risolvere il probleme devi eseguire questo calcolo per ogni d\le \log_{10}(K\cdot X^E)

3 Mi Piace
9

Ragazzi scusate é che anche con le padellata non capisco…

Aluuurah :

K = 4
E = 3

4 * 1 ^ 3 = 4 (1-1+1)*1 = 1 V
4 * 2 ^ 3 = 32 (2-2 +1) *2 = 2 V
4 * 3 ^ 3 = 108 (6-3+1)*3 = 12 V
4 * 4 ^ 3 = 256
4 * 5 ^ 3 = 500
4 * 6 ^ 3 = 864
4 * 7 ^ 3 = 1372 (13-7+1)*4 V
4 * 8 ^ 3 = 2048
4 * 9 ^ 3 = 2916
4 * 10 ^ 3 = 4000
4 * 11 ^ 3 = 5324
4 * 12 ^ 3 = 6912
4 * 13 ^ 3 = 8788
4 * 14 ^ 3 = 10976 (29-14+1)*5 V

E cosi via… quindi (q-p+1)*d é la via corretta…

Ma non riesco davvero a capire come ricavarci q e p… :frowning:

supponiamo K sia 4 e E sia 3…

abbiamo questa sequenza

4 * 1 ^ 3 = 4 (1-1+1)*1 = 1 V
4 * 2 ^ 3 = 32 (2-2 +1) *2 = 2 V
4 * 3 ^ 3 = 108 (6-3+1)*3 = 12 V
4 * 4 ^ 3 = 256
4 * 5 ^ 3 = 500
4 * 6 ^ 3 = 864
4 * 7 ^ 3 = 1372 (13-7+1)*4 V

quindi partendo dall’inizio 4 la lunghezza é 1
andando avanti… trovo 32 con lunghezza diversa da 1 , quindi so di per certo che 32 é il numero piu piccolo con “lunghezza” 2 , quindi 2 sarà p, ma per trovare q , ossia il numero piu grande composto da 2 cifre… non so proprio come fare…

Ho pensato oke… andiamo a troviamo il numero piu piccolo composto da 3 cifre… ma per trovare quello non so vabeh ci ho praticamente rinunciato nonsaprei…

Help xD

10

O si fa una scansione fino a quando non ci becchiamo un numero composto da piu di d cifre?

11

Una volta che hai trovato p, si può dimostrare che p\le q<10p. Adesso bisogna trovare un modo per determinare q tale che q+1 abbia una cifra in più, in un tempo ragionevole. Hint: ricerca binaria

2 Mi Piace
12

Contro-hint: Si può risolvere anche senza ricerca binaria e avere comunque gli stessi tempi.

2 Mi Piace