baibhavbista

Pyramid of Glasses

Jan 10th, 2018
107
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.26 KB | None | 0 0
  1. //http://codeforces.com/problemset/problem/676/B
  2. //Pyramid of Glasses
  3. #include <bits/stdc++.h>
  4. using namespace std;
  5.  
  6. int left_glass_pos(int n, const int arr[], const int h)
  7. {
  8.     int row;
  9.     for(int i = 0; i < h; ++i)
  10.     {
  11.         if(arr[i] >= n)
  12.         {
  13.             row = i;
  14.             break;
  15.         }
  16.     }
  17.     return (n + row + 1);
  18. }
  19.  
  20. void recur(float qnty_arr[], float t, int glass, const int arr[], const int h)
  21. {
  22.     //cout << "glass " << glass << ", t "
  23.     qnty_arr[glass] += t;
  24.     if(glass >= arr[h-1] - h + 1)
  25.     {
  26.     }
  27.     else{
  28.  
  29.     if(qnty_arr[glass] > 1.0)
  30.     {
  31.         float overflow = qnty_arr[glass] - 1.0;
  32.         int left_pos = left_glass_pos(glass, arr, h);
  33.         recur(qnty_arr, overflow/2, left_pos, arr, h);
  34.         recur(qnty_arr, overflow/2, left_pos+1, arr, h);
  35.         qnty_arr[glass] = 1.0;
  36.     }
  37.     }
  38. }
  39.  
  40. int main()
  41. {
  42.     int h, t;
  43.     cin >> h >> t;
  44.     int arr[h];
  45.     arr[0] = 0;
  46.     for(int i = 1; i < h; i++)
  47.         arr[i] = arr[i-1] + i + 1;
  48.  
  49.     float qnty_arr[arr[h-1]+1] = {0.0};
  50.     recur(qnty_arr, t, 0, arr, h);
  51.     int c = 0;
  52.     for(int i = 0; i <= arr[h-1]; i++)
  53.     {
  54.         if(qnty_arr[i] >= 1.0)
  55.         {
  56.             c++;
  57.         }
  58.     }
  59.     cout  << c;
  60.     return 0;
  61. }
Advertisement
Add Comment
Please, Sign In to add comment