Advertisement
a53

ghiozdan

a53
Sep 25th, 2017
258
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.17 KB | None | 0 0
  1. #include <fstream>
  2. #include <iostream>
  3. using namespace std;
  4. int d,k,t,a[100001];
  5.  
  6. void citeste()
  7. {
  8. ifstream f("ghiozdan.in");
  9. f>>d>>k>>t;
  10. for(int i=0;i<k;++i)
  11. f>>a[i];
  12. a[k]=d;
  13. f.close();
  14. }
  15.  
  16. bool verif(int g,int t) /// Verifica daca poate sa ajunga la patinoar cu g paini
  17. {
  18. if(a[0]>(t+g))
  19. return false;
  20. else
  21. if(a[0]>g)
  22. t-=(a[0]-g);
  23. for(int i=1;i<=k;++i)
  24. if((a[i]-a[i-1])>(t+g))
  25. return false;
  26. else
  27. if((a[i]-a[i-1])>g)
  28. t-=((a[i]-a[i-1])-g);
  29. return true;
  30. }
  31.  
  32. int cautbin(int lo,int hi)
  33. {
  34. int mid;
  35. while(lo<=hi)
  36. {
  37. mid=(lo+hi)/2;
  38. if(lo==hi)
  39. return lo;
  40. bool ok1=verif(mid,t),ok2=verif(mid-1,t);
  41. /// cout<<lo<<' '<<hi<<' '<<mid<<" ok1= "<<ok1<<" ok2= "<<ok2<<'\n';
  42. if(ok1&&!ok2)
  43. return mid;
  44. else
  45. if(ok1)
  46. hi=mid-1;
  47. else
  48. if(!ok2)
  49. lo=mid+1;
  50. }
  51. }
  52.  
  53. int main()
  54. {
  55. citeste();
  56. ofstream g("ghiozdan.out");
  57. g<<cautbin(0,d);
  58. g.close();
  59. return 0;
  60. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement