[Educatinal Codeforces Round 173(Div.2)] - A. Coin Transformation

https://codeforces.com/contest/2043/problem/A

Educational Codeforces Round 173(Div.2) - A. Coin Transformation

문제 유형: 재귀, 분할 정복

시간 제한: 1초

메모리 제한: 256MB

 

문제

Initially, you have a coin with value n.

You can perform the following operation any number of times (possibly zero):

- transform one coin with value x, where x is greater than 3 (x>3), into two coins with value ⌊x/4⌋.

What is the maximum number of coins you can have after performing this operation any number of times?

 

n의 값을 가진 통전을 하나 가지고 있다.

다음의 연산을 몇 번이고 할 수 있다:

- 값이 x(x > 3)인 하나의 코인을 floor(x/4)값의 코인 두 개로 분할하기

이 연산을 몇 번이고 한 후에 당신이 가질 수 있는 최대의 코인 개수는?

 

입력

The first line contains one integer t (1≤t≤10^4) — the number of test cases.

Each test case consists of one line containing one integer n(1≤n≤10^18).

 

첫째 줄에 테스트 케이스 t가 주어진다.

각 테스트 케이스에는 정수 n 하나가 주어진다.

 

출력

For each test case, print one integer — the maximum number of coins you can have after performing the operation any number of times.

 

각 테스트 케이스마다, 하나의 정수 답안을 출력하시오.

 

풀이

재귀함수의 입력 수가 3 이하면, 1을 반환한다.

그게 아니라면, n/4를 재귀호출한 값에 2를 곱해서 반환한다.

 

코드

C++

#include <bits/stdc++.h>
#define ll long long
using namespace std;

ll dfs(ll n) {
  if (n <= 3)
    return 1;
  return 2 * dfs(n / 4);
}

void solve() {
  ll n;
  cin >> n;
  ll res = dfs(n);
  cout << res << "\n";
}

int main(int argc, char *argv[]) {
  int t;
  cin >> t;
  while (t--) {
    solve();
  }
  return 0;
}