non riesco a prendere l ultimo task dell ultimo subtask ovvero N=10^15 ho provato a testare il code con una bruteforce e infatti mi da valori esatti (per adesso ho provato a mano essendo che la bruteforce ha una complessità di O N*bitsN e quindi fare un tester non conviene molto) questo è il mio code :
#include <bits/stdc++.h>
using namespace std;
int main(){
#ifdef EVAL
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);
#endif
long long int pfx[10],npfx[10],cal[17],n,sum=0,part=0;
long long int pot[]{1,10,100,1000,10000,100000,1000000,10000000,100000000,1000000000,10000000000,100000000000,1000000000000,10000000000000,10000000000000,100000000000000};
string a;cin>>a;
n=a.size();
pfx[0]=6;pfx[1]=2;pfx[2]=5;
pfx[3]=5;pfx[4]=4;pfx[5]=5;
pfx[6]=6;pfx[7]=3;pfx[8]=7;
pfx[9]=6;cal[0]=49;
npfx[0]=6;
for(int i=1;i<10;i++)npfx[i]=npfx[i-1]+pfx[i];
for(int i=1;i<17;i++)cal[i]=cal[i-1]*10+cal[0]*pot[i];
for(int i=0;i<n-1;i++){
sum+=cal[n-i-2]*(a[i]-'0')+part*pot[n-i-1]*(a[i]-'0');
if((a[i]-'0')>0)sum+=(npfx[(a[i]-'0')-1])*pot[n-i-1];
part+=pfx[a[i]-'0'];
}
if(n!=1)sum-=pot[n-1]*6;
for(int i=1;i<n-1;i++)sum-=pot[i]*6;
cout<<sum+part*(a[n-1]-'0'+1)+npfx[(a[n-1]-'0')];
}
scusa ma per ois_ricarica intendi questo?
perche’ ci sono incongruenze su N (1 ≤ N ≤ 100000) e non c’e` nessuna logica negli input.
Credo che tu abbia sbagliato a scrivere il titolo dell’esercizio di cui stai veramente chiedendo aiuto
sto cercando di capire come dovrebbe funzionare anche se non ho capito a pieno, e da quanto ho capito ti basi sui cicli delle cifre, sulle potenze di 10 e su una prefix sum per sapere il numero delle lancette da 0 a index.
Potresti spiegarmi un attimo meglio cio’ che fai?
effettivamente non sta molto da spiegare;mi sono calcolato quanti cicli devo fare per ottenere un unità una decina ecc,ecc e poi ho usato una prefix sum per avere il calcolo totale per ogni prefisso (quante unità di energia devo usare per passare da decine a unità stessa cosa per le centinaia ecc ecc ),l unica parte che non dovrebbe essere intuitiva ; è quella dell utilizzo della variabile part , ha solo l utilità di salvare le cifre già elaborate in partenza che rimangono invariate
es:1234
parto da 1 calcolo quanti cicli ci vogliono per arrivare alla configurazione 1000? poi passo a 2 stessa domanda, ma adesso devo sapere che l uno di dietro deve essere contato nella sol poichè io non sto calcolando 200 ma sto calcolando 1200 ; gli ultimi cicli e if dove sottraggo servono solo perchè conto pure gli zeri
tipo
01
02
03
04
verranno contati nella mia sol e dopo sottratti non so se sono stato abbastanza pulito nella spiegazione;
si ho compreso, non capivo cosa facesse infatti part l’ultimo if e for al’inizio.
Avevo in mente lo pressoche’ stesso ragionamento.
pero’ non capisco perche’ ti dovrebbe dare wa quando n=10^15, nel caso provo a crearmi una simulazione e confrontare i risultati a vedere dov’e` che sbaglia, la simulazione bruteforce credo che tu possa farla in N*lenght(N)
ok ho risolto era un errore stupido :una sottrazione mancante:< e una potenza di 10 uguale ad un altra :<<<<<;l’unico problema ,faceva 80 pure con stl::pow e non capisco effettivamente perchè non funziona sto appurando la causa l unica cosa modificata da quel code al mio è l aggiunta del vettore precaricato con le potenze
