Submission #534852

---

Source Code Expand

#include <cstdio>
#include <cmath>
#include <cstring>
#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
#include <utility>
#include <sys/time.h>

using namespace std;
typedef long long ll;

ll dp[64][64][64][2];
const ll INF = 1ll << 62;

ll solve() {
	ll N;
	cin >> N;
	int S = 1;
	for (int i = 0; ; ++i) {
		if ((1ll << i) > N) {
			S = i;
			break;
		}
	}
	for (int i = 0; i < 64; ++i) {
		for (int j = 0; j < 64; ++j) {
			for (int k = 0; k < 64; ++k) {
				dp[i][j][k][0] = INF;
				dp[i][j][k][1] = INF;
			}
		}
	}

	dp[0][0][0][0] = 0;
	for (int i = 0; i <= S; ++i) {
		for (int j = 0; j <= S; ++j) {
			for (int k = 0; k <= S; ++k) {
				if (dp[i][j][k][0] == INF && dp[i][j][k][1] == INF) continue;
				if ((N & (1L << i)) == 0) {
					dp[i + 1][j + 0][k + 0][0] = min(dp[i + 1][j + 0][k + 0][0], dp[i][j][k][0]);
					dp[i + 1][j + 0][k + 1][0] = min(dp[i + 1][j + 0][k + 1][0], dp[i][j][k][1]);
					dp[i + 1][j + 1][k + 1][0] = min(dp[i + 1][j + 1][k + 1][0], dp[i][j][k][0] + (1L << i));
					dp[i + 1][j + 1][k + 0][1] = min(dp[i + 1][j + 1][k + 0][1], dp[i][j][k][1] + (1L << i));
				} else {
					dp[i + 1][j + 0][k + 1][0] = min(dp[i + 1][j + 0][k + 1][0], dp[i][j][k][0]);
					dp[i + 1][j + 0][k + 0][1] = min(dp[i + 1][j + 0][k + 0][1], dp[i][j][k][1]);
					dp[i + 1][j + 1][k + 0][1] = min(dp[i + 1][j + 1][k + 0][1], dp[i][j][k][0] + (1L << i));
					dp[i + 1][j + 1][k + 1][1] = min(dp[i + 1][j + 1][k + 1][1], dp[i][j][k][1] + (1L << i));
				}
			}
		}
	}
	ll ans = INF;
	for (int i = 1; i <= S; ++i) {
		ans = min(ans, dp[S + 1][i][i][0]);
	}
	return ans;
}


int main() {
	int T;
	cin >> T;
	for (int i = 0; i < T; ++i) {
		cout << solve() << endl;
	}
}

Submission Info

Judge Result