Advertisement
Guest User

Untitled

a guest
Nov 24th, 2017
63
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.10 KB | None | 0 0
  1. #include <cstdio>
  2. #include <algorithm>
  3. #define MAXN 100010
  4.  
  5. using namespace std;
  6.  
  7. int prefiks[MAXN];
  8.  
  9. int szukanie(int a, int b)
  10. {
  11.     //int spr = 1;
  12.     int p = 0;
  13.     int k = b;
  14.     while(p != k)
  15.     {
  16.         spr++;
  17.         if(a < prefiks[(p + k) / 2])
  18.         {
  19.             k = (p + k) / 2 - 1;
  20.             //spr--;
  21.         }
  22.         if(a > prefiks[(p + k) / 2])
  23.         {
  24.             p = (p + k) / 2 + 1;
  25.            // spr--;
  26.         }
  27.         if(a == prefiks[(p + k) / 2])
  28.         {
  29.             printf("TAK\n");
  30.             return 0;
  31.         }
  32.         /*if(k == p + 1 && spr == 2)
  33.         {
  34.             printf("NIE\n");
  35.             return 0;
  36.         }*/
  37.  
  38.     }
  39.     printf("TAK\n");
  40.     return 0;
  41.  
  42. }
  43.  
  44. int main()
  45. {
  46.     int n, k, a, c;
  47.     int b = 0;
  48.  
  49.     scanf("%d",&n);
  50.  
  51.     for(int i = 0; i < n; i++)
  52.     {
  53.         scanf("%d",&k);
  54.         prefiks[i + 1] = prefiks[i] + k;
  55.  
  56.  
  57.     }
  58.  
  59.     c = n + 1;
  60.  
  61.     sort(prefiks, prefiks + c);
  62.  
  63.     scanf("%d",&a);
  64.  
  65.     for(int i = 0; i < a; i++)
  66.     {
  67.         scanf("%d",&k);
  68.         szukanie(k, n + 1);
  69.  
  70.     }
  71.  
  72. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement