AtCoder Beginner Contest 153 - Caracal vs Monster

Caracal is fighting with a monster.
The health of the monster is H.
Caracal can attack by choosing one monster. When a monster is attacked, depending on that monster's health, the following happens:
 - If the monster's health is 1, it drops to 0.
 - If the monster's health, X, is greater than 1, that monster disappears. Then, two new monsters appear, each with the health of \lfloor X/2 \rfloor.
(\lfloor r \rfloor denotes the greatest integer not exceeding r.)
Caracal wins when the healths of all existing monsters become 0 or below.
Find the minimum number of attacks Caracal needs to make before winning.

-----Constraints-----
 - 1 \leq H \leq 10^{12}
 - All values in input are integers.

-----Input-----
Input is given from Standard Input in the following format:
H

-----Output-----
Find the minimum number of attacks Caracal needs to make before winning.

-----Sample Input-----
2

-----Sample Output-----
3

When Caracal attacks the initial monster, it disappears, and two monsters appear, each with the health of 1.
Then, Caracal can attack each of these new monsters once and win with a total of three attacks.

Source: atcoder | Difficulty: MEDIUM


Solutions:
import math
h = int(input())
print(2 ** (math.floor(math.log2(h)) + 1) - 1)


h = int(input())
H = bin(h)
k = len(H) - 2
A = 2 ** k - 1
print(A)


from math import log
h = int(input())
k = int(log(h, 2)) + 1
print(2 ** k - 1)


H = int(input())
n = len(bin(H)) - 2
print(2 ** n - 1)


H = int(input())
ans = 1
while H > 0:
	H = H // 2
	ans *= 2
print(ans - 1)


H = int(input())
I = len(bin(H)) - 3
Sn = 2 ** (I + 1) - 1
print(Sn)


n = int(input())
ans = 1
while ans <= n:
	ans *= 2
print(ans - 1)


h = int(input())
print(2 ** h.bit_length() - 1)


import math
H = int(input())
a = int(math.log(H, 2))
print(2 ** (a + 1) - 1)


import math
n = int(input())
m = int(math.log(n, 2))
print(2 ** (m + 1) - 1)


def main():
	N = 0
	H = int(input())
	ans = 0
	while True:
		H //= 2
		if H == 0:
			break
		N += 1
	for i in range(N + 1):
		ans += pow(2, i)
	print(ans)

def __starting_point():
	main()
__starting_point()


print((1 << int(input()).bit_length()) - 1)


H = int(input())
n = H.bit_length()
ans = (1 << n) - 1
print(ans)


h = int(input())
n = 0
while 2 ** n <= h:
	n += 1
print(2 ** n - 1)


a = int(input())
i = 0
k = 1
while a > 1:
	a = a // 2
	i += k
	k *= 2
print(i + k)


print(2 ** len(bin(int(input()))[2:]) - 1)


import math
h = int(input())
(a, ans) = (0, 0)
while h > 1:
	h = math.floor(h / 2)
	a += 1
for i in range(a + 1):
	ans += 2 ** i
print(ans)


n = int(input())
i = 1
while i * 2 <= n:
	i *= 2
print(i * 2 - 1)


h = int(input())
c = 0
while h > 0:
	h = h // 2
	c += 1
print(2 ** c - 1)


h = int(input())
for i in range(100):
	if 2 ** i > h:
		print(2 ** i - 1)
		return


h = input()
h = int(h)
num = 1 << h.bit_length()
print(num - 1)


H = int(input())
cnt = 0
res = 0
while H > 1:
	H = H // 2
	cnt += 1
	res += 2 ** cnt
print(res + 1)


hp = int(input())
n = 0
while hp:
	hp //= 2
	n += 1
print(2 ** n - 1)


H = int(input())

def attack(n):
	if 1 == n:
		return 1
	return 2 * attack(int(n / 2)) + 1
print(attack(H))


from sys import setrecursionlimit
setrecursionlimit(1000000)
H = int(input())

def f(n):
	if n == 1:
		return 1
	else:
		return 1 + f(n // 2) * 2
print(f(H))


N = int(input())
import math
print(2 * 2 ** int(math.log2(N)) - 1)


n = int(input())
cnt = 0
i = 0
ans = 0
while n != 1:
	n //= 2
	i += 1
ans = 2 ** (i + 1) - 1
print(ans)


s = int(input())
a = 0
while s > 0:
	s = s // 2
	a += 1
print(2 ** a - 1)


import math
h = int(input())
n = int(math.log2(h)) + 1
print(2 ** n - 1)


h = int(input())
l = 0
while h > 0:
	l = 2 * l + 1
	h //= 2
print(l)


h = int(input())
hb = bin(h)[2:]
hbn = len(hb)
print(2 ** hbn - 1)


N = int(input())
NB = format(N, '0b')
K = len(NB)
print(2 ** K - 1)


x = int(input())
k = 0
while x > 0:
	x = x // 2
	k = k + 1
print(2 ** k - 1)


h = int(input())
i = 0
while 2 ** i <= h:
	i += 1
print(2 ** i - 1)


import math
print(pow(2, int(math.log(int(input()), 2) // 1) + 1) - 1)


h = int(input())
count = 0
while True:
	h = h // 2
	if h == 0:
		break
	count += 1
print(2 ** count + int(2 ** count - 1))


H = int(input())
i = len(bin(H)) - 2
print(2 ** i - 1)


H = int(input())
A = 1
while H >= A:
	A *= 2
print(A - 1)


n = int(input())
c = 0
while n != 0:
	n //= 2
	c += 1
print(2 ** c - 1)


H = int(input())
X = 1
while X <= H:
	X *= 2
print(X - 1)


h = int(input())
ct = 0
while h > 0:
	ct += 1
	h //= 2
print(2 ** ct - 1)


import math
h = int(input())
tmp = math.log2(h)
print(2 ** int(tmp + 1) - 1)


h = int(input())
ans = 1
while ans < h:
	ans = ans << 1 | 1
print(ans)


H = int(input())

def attack_num(x):
	if x == 1:
		return 1
	else:
		return 2 * attack_num(x // 2) + 1
print(attack_num(H))


h = int(input())
ans = 0
p = 0
while h:
	h //= 2
	ans += 2 ** p
	p += 1
print(ans)


H = int(input())
c = 1
ans = 1
while H > 1:
	H //= 2
	c *= 2
	ans += c
print(ans)


n = int(input())
s = str(bin(n))[2:]
l = len(s)
print(2 ** l - 1)


n = int(input())
s = 1
t = 0
while s <= n:
	s = s * 2
	t += 1
print(2 ** t - 1)


import math
h = int(input())
c = int(math.log2(h))
print(2 ** (c + 1) - 1)


h = int(input())
import math
print(pow(2, int(math.log2(h)) + 1) - 1)


print(2 ** (int(__import__('math').log2(int(input()))) + 1) - 1)


h = int(input())
count = 0
ans = 0
while h > 0:
	h //= 2
	count += 1
for i in range(count):
	ans = ans * 2 + 1
print(ans)


h = int(input())
for i in range(10 ** 12):
	if 2 ** i <= h < 2 ** (i + 1):
		ans = 2 ** (i + 1) - 1
		print(ans)
		return


H = int(input())
p = 0
while H > 0:
	H //= 2
	p += 1
print(2 ** p - 1)


import math
h = int(input())
count = 0
e = 0
while h > 0:
	count += 1 * 2 ** e
	e += 1
	if h == 1:
		h = 0
	else:
		h = int(math.floor(h / 2))
print(count)


h = int(input())
num = 0
while h > 0:
	h = h // 2
	num += 1
print(2 ** num - 1)


a = int(input())
s = str(bin(a))[2:]
print(2 ** len(s) - 1)


import math
h = int(input())
hp = h
c = 0
ans = 0
while hp > 1:
	hp = math.floor(hp / 2)
	c += 1
for i in range(0, c + 1):
	ans += 2 ** i
print(ans)


x = int(input())
v = len(bin(x)) - 2
print((1 << v) - 1)


h = int(input())
count = 0
for i in range(40):
	count += 2 ** i
	if h >= 2 ** i and h < 2 ** (i + 1):
		break
print(count)


H = int(input())
k = 1
N = 0
while H > 0:
	H = H // 2
	N += k
	k *= 2
print(N)


print(~-2 ** int(input()).bit_length())


H = int(input())
n = H.bit_length()
print(pow(2, n) - 1)


H = int(input())
now = 1
for i in range(1, 100):
	if now <= H <= now * 2 - 1:
		print(2 ** i - 1)
		break
	else:
		now *= 2


h = int(input())
cnt = 0
while h != 1:
	h //= 2
	cnt += 1
t = 1
ans = 0
for i in range(cnt + 1):
	ans += t
	t *= 2
print(ans)


H = int(input())
i = 1
while H > 1:
	H = H // 2
	i += 1
print(2 ** i - 1)


import math
H = int(input())
x = int(math.log2(H)) + 1
print((1 << x) - 1)


h = int(input())
ans = 0
for i in range(10 ** 10):
	if h == 1:
		print(2 ** (ans + 1) - 1)
		break
	else:
		h //= 2
		ans += 1


import math
h = int(input())
i = int(math.log(h, 2))
print(2 ** (i + 1) - 1)


import sys
sys.setrecursionlimit(1000000)

def rec(n):
	if n == 1:
		return 1
	return rec(n // 2) * 2 + 1
n = int(input())
print(rec(n))


def mons(hp, attack=1):
	if hp == 1:
		return attack * 2 - 1
	else:
		return mons(hp // 2, attack * 2)
print(mons(int(input())))


from math import log2
print(pow(2, int(log2(int(input()))) + 1) - 1)


H = int(input())
cnt = 0
num = 1
while H >= 1:
	H = H // 2
	cnt += num
	num = num * 2
print(cnt)


h = int(input())
d = 1
ans = 0
while h:
	ans += d
	h //= 2
	d *= 2
print(ans)


H = int(input())
n = H
k = 1
while n // 2 > 0:
	n = n // 2
	k += 1
print(2 ** k - 1)


n = int(input())
h = len(bin(n)) - 2
print(2 ** h - 1)


H = int(input())
K = 1
while not K <= H < 2 * K:
	K = 2 * K
print(2 * K - 1)


H = int(input())
print(2 ** H.bit_length() - 1)


h = int(input())

def fh(x):
	if x == 1:
		return 1
	else:
		return 2 * fh(x // 2) + 1
ans = fh(h)
print(ans)


H = int(input())

def getAns(x):
	if x <= 1:
		return 1
	return 2 * getAns(x // 2) + 1
ans = getAns(H)
print(ans)


H = int(input())

def battle(h):
	if h == 1:
		return 1
	else:
		return 2 * battle(h // 2) + 1
print(battle(H))


H = int(input())
print(2 ** len(format(H, 'b')) - 1)


import bisect
import numpy
H = int(input())
ans = 1
HP = 2
tmp = 1
while True:
	if H < HP:
		break
	else:
		tmp *= 2
		ans += tmp
		HP *= 2
print(ans)


bins = len(format(int(input()), 'b'))
print(2 ** bins - 1)


h = int(input())

def cal(x):
	if x == 1:
		return 1
	return cal(x // 2) * 2 + 1
print(cal(h))


h = int(input())
cnt = 0
while h != 1:
	cnt += 1
	h //= 2
print(2 ** (cnt + 1) - 1)


H = int(input())
s = 1
t = 0
while H > 1:
	H = H // 2
	s = s * 2
	t = t + 1
list = []
u = 1
while u <= t:
	list.append(u)
	u = u + 1
z = 0
for i in list:
	z = z + 2 ** (i - 1)
print(str(z + s))


a = int(input())
n = str(bin(a))
print(2 ** (len(n) - 2) - 1)


H = int(input())
ii = 1
while H != 1:
	ii += 1
	H = H // 2
print(2 ** ii - 1)


h = int(input())

def wa(n):
	w = 0
	for i in range(0, n + 1):
		w += 2 ** i
	return w
n = 1
cnt = -1
while n <= h:
	n = n * 2
	cnt += 1
print(wa(cnt))


h = int(input())
s = 1
while h > 1:
	h //= 2
	s += 1
print(2 ** s - 1)


import numpy as np
H = int(input())
c = 0
while H != 0:
	c += 1
	H = H // 2
print(2 ** c - 1)


h = int(input())
fix = 1
while h >= fix:
	fix *= 2
print(fix - 1)


from math import *
print(2 ** ceil(log2(int(input()) + 1)) - 1)


def f(x):
	return f(x // 2) * 2 + 1 if x > 1 else 1
print(f(int(input())))


from math import *
H = int(input())
print(2 ** (int(log2(H)) + 1) - 1)


H = int(input())
a = 0
t = 1
while H:
	H //= 2
	a += t
	t *= 2
print(a)


h = int(input())
count = 0
while h != 0:
	h //= 2
	count += 1
print(2 ** count - 1)


def myfunc(N):
	if N <= 1:
		return 1
	return 2 * myfunc(int(N / 2)) + 1

def __starting_point():
	N = int(input())
	print(myfunc(N))
__starting_point()


import math
X = int(input())
print(2 ** (int(math.log2(X)) + 1) - 1)


H = int(input())
count = 0
while H != 1:
	count += 1
	H = H >> 1
print(2 * 2 ** count - 1)


H = int(input())
from math import log
print(2 ** (int(log(H, 2)) + 1) - 1)


h = int(input())
k = 1
while k <= h:
	k *= 2
print(k - 1)


h = int(input())
binary = len(bin(h)) - 2
print(2 ** binary - 1)


H = int(input())
i = 0
while True:
	if H < 2 ** i:
		n = i
		break
	i += 1
print(2 ** n - 1)


H = int(input())
N = 0
while True:
	N += 1
	if 2 ** N > H:
		break
a = [1] * N
for i in range(N):
	if i == 0:
		a[i] = 1
	else:
		a[i] = 2 * a[i - 1] + 1
print(a[-1])


h = int(input())
dig = len(format(h, 'b'))
print(2 ** dig - 1)


H = int(input())
m = 1
while m <= H:
	m *= 2
print(m - 1)


print(pow(2, int(input()).bit_length()) - 1)


H = int(input())
L = 0
while H > 1:
	H = H // 2
	L += 1
print(2 ** (L + 1) - 1)


def solve(H: int):
	n = 1
	attack = 0
	while H > 1:
		attack += n
		H = H // 2
		n *= 2
	attack += n
	return attack

def main():
	H = int(input())
	answer = solve(H)
	print(answer)

def __starting_point():
	main()
__starting_point()


N = int(input())
cnt = 0
while N > 0:
	N //= 2
	cnt = cnt * 2 + 1
print(cnt)


H = int(input())
A = 0
ans = 0
for i in range(H):
	if 2 ** i <= H < 2 ** (i + 1):
		A = 2 ** i
		break
	else:
		continue
for j in range(i + 1):
	ans += 2 ** j
print(ans)


h = int(input())
n = len(format(h, 'b'))
print(2 ** n - 1)


h = int(input())
a = bin(h)
b = len(a) - 2
print(2 ** b - 1)


h = int(input())
ans = 0
cnt = 1
while True:
	h = h / 2 // 1
	ans += cnt
	if h == 0:
		print(ans)
		return
	cnt *= 2


h = int(input())
h_bi = bin(h)[2:]
print(2 ** len(h_bi) - 1)


n = int(input())
m = 1
while n > m:
	m *= 2
	m += 1
print(m)


H = int(input())
if H == 1:
	print(1)
	return
import math as m
n = m.floor(m.log2(H)) + 1
ans = 2 ** n - 1
print(ans)


h = int(input())
b = bin(h)
l = len(b) - 2
print(2 ** l - 1)


H = int(input())
i = 0
temp = 0
while True:
	if 2 ** i <= H and H < 2 ** (i + 1):
		temp = 2 ** i
		break
	i += 1
print(temp * 2 - 1)


h = int(input())
x = '1' * (len(bin(h)) - 2)
print(int(x, 2))


def f(h):
	if h != 1:
		return f(h // 2) * 2 + 1
	else:
		return 1
h = int(input())
print(f(h))


n = int(input())
x = bin(n)
print(2 ** (len(x) - 2) - 1)


import math
h = int(input())
l = int(math.log(h, 2))
p = 2 ** l * 2 - 1
print(p)


H = int(input())
h = 1
while H > h - 1:
	h *= 2
print(h - 1)


H = int(input())
s = bin(H)
s = s[2:]
print(2 ** len(s) - 1)


H = int(input())
count = 0
pow = 1
for _ in range(H):
	if H < pow:
		break
	count += 1
	pow *= 2
print(2 ** count - 1)


h = int(input())
res = 1
c = 1
while h > 1:
	c *= 2
	res += c
	h //= 2
print(res)


import math
H = int(input())
n = math.floor(math.log2(H))
ans = 0
for i in range(0, n + 1):
	ans += 2 ** i
print(ans)


H = int(input())
N = 1
while H:
	H //= 2
	N += N
print(N - 1)


H = int(input())
k = len(bin(H)[2:])
print(2 ** k - 1)


def divi(n):
	if n > 1:
		return 2 * divi(n // 2) + 1
	else:
		return 1
h = int(input())
print(divi(h))


H = int(input())
b = 0
while 2 ** b <= H:
	b += 1
print(2 ** b - 1)


import math
H = int(input())
print(2 ** (math.floor(math.log2(H)) + 1) - 1)


def main():
	h = int(input())
	cnt = 0
	while h > 0:
		h //= 2
		cnt += 1
	x = 0
	for i in range(cnt):
		x = x * 2 + 1
	print(x)

def __starting_point():
	main()
__starting_point()


h = int(input())
lhb = len(format(h, 'b'))
print(2 ** lhb - 1)


h = int(input())
ans = 2 ** (len(bin(h)) - 2) - 1
print(ans)


h = int(input())
sumn = 0
(i, k) = (0, 1)
while k <= h:
	sumn += k
	i += 1
	k = 2 ** i
print(sumn)


import math
h = int(input())
atk = 0
enemy = 1
while True:
	if h > 1:
		h = math.floor(int(h / 2))
		atk += enemy
		enemy *= 2
	elif h == 1:
		atk += enemy
		break
print(atk)


h = int(input())
ans = 0
e = 1
while h > 0:
	ans += e
	e *= 2
	h = h // 2
print(ans)


H = int(input())
for i in range(0, 40):
	if 2 ** i <= H < 2 ** (i + 1):
		H = 2 ** i
		break
ans = 0
for k in range(0, i + 1):
	ans += 2 ** k
print(ans)


h = int(input())
x = 1
while h > 1:
	h = h // 2
	x += 1
print(2 ** x - 1)


import math
H = int(input())
ans = 0
num = 0
while True:
	ans += 2 ** num
	if H == 1:
		print(ans)
		break
	else:
		H = math.floor(H / 2)
		num += 1


def check(n):
	if n > 1:
		return 2 * check(n // 2) + 1
	else:
		return 1
print(check(int(input())))


h = int(input())
hh = len(bin(h)) - 2
print(pow(2, hh) - 1)


H = int(input())
c = 1
while H > 0:
	c *= 2
	H //= 2
print(c - 1)


import math
h = int(input())
x = math.floor(math.log2(h)) + 1
y = 2 ** x - 1
print(y)


H = int(input())
now = 1
while now <= H:
	now *= 2
print(now - 1)


H = int(input())
cnt = 1
ans = 0
while True:
	if 2 ** cnt > H:
		cnt -= 1
		break
	elif 2 ** cnt == H:
		break
	else:
		cnt += 1
for c in range(cnt + 1):
	ans += 2 ** c
print(ans)


import sys
import copy
import math
import itertools
H = int(input())
cnt = 0
for i in range(int(math.log2(H)) + 1):
	cnt += 2 ** i
print(cnt)


H = int(input())
attackcnt = 0
monstercnt = 1

def monster(h, m, a):
	if h == 1:
		return (0, 0, a + m)
	else:
		return monster(int(h / 2), 2 * m, a + m)
(a, b, c) = monster(H, monstercnt, attackcnt)
print(c)


H = int(input())
n = 1
while H != 1:
	H //= 2
	n += 1
print(2 ** n - 1)


def N():
	return int(input())

def L():
	return list(map(int, input().split()))

def NL(n):
	return [list(map(int, input().split())) for i in range(n)]
mod = pow(10, 9) + 7
import sys
import math
import collections
n = N()
l = int(math.log2(n))
su = 0
z = 1
for i in range(l + 1):
	su += z
	z *= 2
print(su)


from sys import stdin
import math
h = int(stdin.readline())
split_times = math.ceil(math.log2(h + 1))
sum_times = sum([2 ** i for i in range(split_times)])
print(sum_times)


import math
h = int(input())
a = math.log(h, 2)
print(2 ** int(a) * 2 - 1)


print(2 ** len('{0:b}'.format(int(input()))) - 1)


import math
n = int(input())
n2 = int(math.log(n, 2))
print(2 * 2 ** n2 - 1)


a = int(input())
k = 2
while a >= k:
	k *= 2
print(k - 1)


H = int(input())
ans = 1
if H != 1:
	h = H
	for i in range(1, 40):
		if int(h / 2) >= 2:
			ans += 2 ** i
			h = int(h / 2)
		else:
			ans += 2 ** i
			break
print(ans)


import math
H = int(input())
l = math.log(H, 2)
ll = math.floor(l) + 1
ans = 2 ** ll - 1
print(ans)


h = int(input())
a = 0
while h != 0:
	h = h // 2
	a = a + 1
print(2 ** a - 1)


n = int(input())
cnt = 0
while n != 1:
	n = n // 2
	cnt += 1
ans = 1
for i in range(1, cnt + 1):
	ans = ans + 2 ** i
print(ans)


import sys
input = sys.stdin.readline

def main():
	enemy_hp = int(input())
	enemy_count = 1
	attack_count = 1
	if enemy_hp == 1:
		print(1)
		return
	else:
		while enemy_hp > 1:
			enemy_hp = int(enemy_hp / 2)
			enemy_count *= 2
			attack_count += enemy_count
	print(attack_count)

def __starting_point():
	main()
__starting_point()


N = int(input())
a = 0
d = 1
while d <= N:
	a += d
	d *= 2
print(a)


H = int(input())
n = 0
ans = 0
while True:
	if 2 ** n > H:
		break
	else:
		ans += 2 ** n
		n += 1
print(ans)


def main():
	H = int(input())
	res = 1
	ans = 1
	while H > 1:
		res *= 2
		ans += res
		H //= 2
	print(ans)

def __starting_point():
	main()
__starting_point()


h = int(input())
ans = (1 << h.bit_length()) - 1
print(ans)


H = int(input())
x = 1
while x <= H:
	x *= 2
print(x - 1)


import math
out = 2 ** int(math.log2(int(input())) + 1) - 1
print(out)


h = int(input())
h = str(format(h, 'b'))
print(2 ** len(h) - 1)


h = int(input())
m = 0
while 2 ** m <= h:
	m += 1
print(2 ** m - 1)


import math
print(2 ** math.ceil(math.log2(float(input()) + 1)) - 1)


H = int(input())
bh = len(str(bin(H))) - 2
print(2 ** bh - 1)


h = int(input())
ans = 0
t = 1
while t <= h:
	t *= 2
print(t - 1)


H = int(input())
for i in range(0, 10 ** 20 + 1):
	if 2 ** i <= H < 2 ** (i + 1):
		break
print(2 ** (i + 1) - 1)


f = lambda x: 2 * f(x // 2) + 1 if x > 1 else 1
print(f(int(input())))


H = int(input())
num = 1
sum = 0
while H != 0:
	H = H // 2
	sum += num
	num *= 2
print(sum)


def main():

	def solve(n):
		if n == 1:
			return 1
		return solve(n // 2) * 2 + 1
	H = int(input())
	print(solve(H))

def __starting_point():
	main()
__starting_point()