daily pastebin goal
41%
SHARE
TWEET

Untitled

a guest Nov 20th, 2017 65 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <cstdio>
  2. #include <queue>
  3. #include <cmath>
  4. #include <algorithm>
  5. #include <vector>
  6. using namespace std;
  7.  
  8. int depth(int a)
  9. {
  10.     int now = 3, res = 0, sum = 0;
  11.     while (sum < a)
  12.     {
  13.         res++;
  14.         for (int i = 0; i < now; i++) sum++;
  15.         now *= 3;
  16.     }
  17.     return res;
  18. }
  19.  
  20. int main()
  21. {
  22.     int hw = 100;
  23.     for (int i = 1; i <= 50; i++) { // i는 처음 쿠키의 개수
  24.         priority_queue<pair<int, int> > pq;
  25.         for (int j = 1; j <= i; j++) {
  26.             pq.push({ -(hw - i), j });
  27.         }
  28.         int cnt = 0;
  29.         while (!pq.empty()) // pq에는 (-남은경로의길이, 쿠키번호) 가 들어 있음
  30.         {
  31.             cnt++;
  32.             int move = depth(pq.size());
  33.             vector<pair<int, int>> vec;
  34.             for (int k = 0; k < move; k++) {
  35.                 auto now = pq.top(); pq.pop();
  36.                 now.first += 1;
  37.                 if (now.first != 0) vec.push_back(now);
  38.             }
  39.             for (auto v : vec) pq.push(v);
  40.         }
  41.         printf("cookie %d : move %d\n", i, cnt);
  42.     }
  43. }
RAW Paste Data
Top