Buongiorno, gli ultimi tre casi di “Ricarica” mi vanno in timeout,mi potreste dare una mano a velocizzare il programma, vi lascio il codice di seguito grazie in anticipo:
#include <bits/stdc++.h>
using namespace std;
int main(){
ofstream out("output.txt");
ifstream in("input.txt");
long long int N,M;
in>>N>>M;
typedef pair<long long int,long long int>coppia;
vector<coppia>v(N);
for(long long int i=0;i<N;i++){
in>>v[i].first;
in>>v[i].second;
}
long long int ris;
bool A=false;
for(int i=1;i<=M && A==false;i++){
long long int cont=i,x=1;
long long int j=0;
//cout<<i<<" "<<cont<<endl;
while(x<=M && cont!=0){
if(j<N){
if(x!=v[j].first){
x++;
cont--;
}
else{
cont+=v[j].second-v[j].first+1;
x=v[j].second+1;
j++;
}
}
else{
cont-=M-v[v.size()-1].second;
x=M+1;
}
//cout<<cont<<" "<<x<<endl;
}
if(cont>0){
ris=i;
A=true;
}
}
out<<ris;
}
Ho capito la tua idea e ho provato a fare una soluzione ma va ancora in timeout:
#include <bits/stdc++.h>
using namespace std;
int main(){
ofstream out("output.txt");
ifstream in("input.txt");
long long int N,M;
in>>N>>M;
typedef pair<long long int,long long int>coppia;
vector<coppia>v(N);
for(long long int i=0;i<N;i++){
in>>v[i].first;
in>>v[i].second;
/*long long int n1,n2;
cin>>n1>>n2;
v.push_back(make_pair(n1,n2));*/
}
long long int ris;
bool A=false;
long long int j=1;
while(A==false){
long long int i=0;
bool B=true;
long long int cont=j,x=0;
while(i<=N && B==true && x<=M){
if(i<N){
cont-=(v[i].first-1)-x;
x=v[i].first;
if(cont<=0){
B=false;
}
else{
cont+=v[i].second-v[i].first+1;
x=v[i].second;
i++;
}
}
else{
cont-=M-v[v.size()-1].second;
x=M+1;
}
}
if(cont<=0){
B=false;
}
if(B==true){
ris=j;
A=true;
}
else{
j++;
}
}
out<<ris;
}
Ripeto che non mi è chiaro l’algoritmo e quindi più di tanto non posso dire ma vedo un while dentro un while mentre c’è sicuramente una soluzione O(N). Hai a che fare con una spezzata triangolare che sale di k quando si attraversa un intervallo j di copertura lungo k e scende di k1 quando si attraversa un intervallo scoperto lungo k1 più le eventuali parti scoperte iniziali e finali.
Grazie mille ho capito come prendere 100 ti vorrei chiedere una cosa ma solo per curiosità, ma come fai a risolvere i problemi con cosi poco tempo,mi spiego meglio in parecchi problemi vedo sempre che tra i più veloci ci sei tu vorrei sapere se usi qualche tecnica particolare perchè mi piacerebbe impararla
Purtroppo non dispongo di soluzioni particolari ma di molto tempo da dedicare a questa attività che tra l’altro mi piace parecchio, inoltre non devo prepararmi per fare competizioni. Tutto questo significa che una volta trovata una soluzione posso dedicare anche molto tempo a migliorarla, cosa che il più delle volte avviene. Infine, fra i trucchi del mestiere, esistono funzioni per velocizzare i tempi di I/O che spesso e volentieri costituiscono una porzione cospicua del tempo che viene valutato per stabilire la velocità della soluzione.
Direi che l’utilizzo di questo portale per allenamenti, cioè quello che stai già facendo, va benissimo. Comincia da quelli più facili e vai avanti, usa il forum etc. se poi arrivi ad un livello tale da voler puntare più in alto vedi Come qualificarsi per le IOI? per qualche consiglio aggiuntivo.