Guest User

Untitled

a guest
Nov 20th, 2017
112
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 0.85 KB | None | 0 0
  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. }
Add Comment
Please, Sign In to add comment