Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <fstream>
- #include <iostream>
- using namespace std;
- int d,k,t,a[100001];
- void citeste()
- {
- ifstream f("ghiozdan.in");
- f>>d>>k>>t;
- for(int i=0;i<k;++i)
- f>>a[i];
- a[k]=d;
- f.close();
- }
- bool verif(int g,int t) /// Verifica daca poate sa ajunga la patinoar cu g paini
- {
- if(a[0]>(t+g))
- return false;
- else
- if(a[0]>g)
- t-=(a[0]-g);
- for(int i=1;i<=k;++i)
- if((a[i]-a[i-1])>(t+g))
- return false;
- else
- if((a[i]-a[i-1])>g)
- t-=((a[i]-a[i-1])-g);
- return true;
- }
- int cautbin(int lo,int hi)
- {
- int mid;
- while(lo<=hi)
- {
- mid=(lo+hi)/2;
- if(lo==hi)
- return lo;
- bool ok1=verif(mid,t),ok2=verif(mid-1,t);
- /// cout<<lo<<' '<<hi<<' '<<mid<<" ok1= "<<ok1<<" ok2= "<<ok2<<'\n';
- if(ok1&&!ok2)
- return mid;
- else
- if(ok1)
- hi=mid-1;
- else
- if(!ok2)
- lo=mid+1;
- }
- }
- int main()
- {
- citeste();
- ofstream g("ghiozdan.out");
- g<<cautbin(0,d);
- g.close();
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement