Advertisement
dyamondz

Fixed points - P34682

Oct 23rd, 2018
164
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.77 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. using namespace std;
  4.  
  5. bool find_fixed(vector<int>&v, int x, int&temp){
  6.     int l = 0;
  7.     int r = v.size()-1;
  8.     while(r-l > 1){
  9.         int m = (l+r)/2;
  10.         if(v[m]+x >= m+1){
  11.             r = m;
  12.         }
  13.         else{
  14.             l = m;
  15.         }
  16.     }
  17.     if(v[l]+x == l+1){
  18.         temp = l;
  19.         return true;
  20.     }
  21.     else if(v[r]+x == r+1){
  22.         temp = r;
  23.         return true;
  24.     }
  25.     else return false;
  26. }
  27.  
  28. int main(){
  29.     int n, j=1;
  30.     while(cin>>n){
  31.         vector<int> v(n,0);
  32.         for(int i=0; i<n; ++i){
  33.             cin>>v[i];
  34.         }
  35.         int m,x;
  36.         cin>>m;
  37.         cout<<"Sequence #"<<j<<endl;
  38.         for(int i=0;i<m;++i){
  39.             cin>>x;
  40.             int temp;
  41.             if(find_fixed(v,x,temp)){
  42.                 cout<<"fixed point for "<<x<<": "<<temp+1<<endl;
  43.             }
  44.             else cout<<"no fixed point for "<<x<<endl;
  45.         }
  46.         ++j;
  47.         cout<<endl;
  48.     }
  49. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement