Not to be confused with chessboard.

 [Image] 


-----Input-----

The first line of input contains a single integer N (1 ≤ N ≤ 100) — the number of cheeses you have.

The next N lines describe the cheeses you have. Each line contains two space-separated strings: the name of the cheese and its type. The name is a string of lowercase English letters between 1 and 10 characters long. The type is either "soft" or "hard. All cheese names are distinct.


-----Output-----

Output a single number.


-----Examples-----
Input
9
brie soft
camembert soft
feta soft
goat soft
muenster soft
asiago hard
cheddar hard
gouda hard
swiss hard

Output
3

Input
6
parmesan hard
emmental hard
edam hard
colby hard
gruyere hard
asiago hard

Output
4

Source: codeforces | Difficulty: HARD


Solutions:
from math import *
n = int(input())
a = []
for i in range(n):
	a.append(input().split()[1])
x = a.count('soft')
y = a.count('hard')
if (abs(x - y) == 1 or x == y) and int(sqrt(n) + 0.5) ** 2 == n:
	print(int(sqrt(n)))
else:
	ma = max(x, y)
	t = ma * 2
	if t - 1 < n:
		print(ceil(sqrt(t)))
	else:
		print(min(ceil(sqrt(t)), ceil(sqrt(t - 1))))


from math import sqrt, ceil, floor
n = int(input())
cnt = 0
for i in range(0, n):
	(a, b) = input().split()
	if b == 'soft':
		cnt += 1
cnt = max(cnt, n - cnt)
for i in range(0, 100):
	t = i * i
	(a, b) = (int(ceil(t / 2)), int(floor(t / 2)))
	if a >= cnt and b >= n - cnt or (b >= cnt and a >= n - cnt):
		print(i)
		break


s = h = 0
number = int(input())
for x in range(number):
	lin = map(str, input().split())
	if 'soft' in lin:
		s += 1
	else:
		h += 1
if s == 0 and h == 1 or (s == 1 and h == 0):
	print(1)
	exit()
z = 1
while 1:
	l = z * z
	if l % 2 == 0:
		if l / 2 >= h and l / 2 >= s:
			print(z)
			exit()
	elif l / 2 + 1 >= h and l / 2 >= s or (l / 2 >= h and l / 2 + 1 >= s):
		print(z)
		exit()
	z += 1


n = int(input())
p = 0
q = 0
for i in range(n):
	t = input().split()[-1]
	if t == 'soft':
		p += 1
	else:
		q += 1
(s, t) = (max(p, q), min(p, q))
ans = 0
while (ans * ans + 1) // 2 < s or ans * ans // 2 < t:
	ans += 1
print(ans)


import sys
n = int(sys.stdin.readline().strip())
chs = [sys.stdin.readline().strip() for _ in range(n)]
soft = sum((ch.endswith('soft') for ch in chs))
hard = sum((ch.endswith('hard') for ch in chs))
for i in range(1, 16):
	b = i ** 2 // 2
	w = (i ** 2 + 1) // 2
	if b >= min(soft, hard) and w >= max(soft, hard):
		print(i)
		break


print((lambda x, y: sum((1 for i in range(15) if i ** 2 / 2 < x or i ** 2 + 1 >> 1 < y)))(*(lambda n, x: sorted([n - x, x]))(*(lambda n: [n, sum((input()[-4] == 'h' for i in range(n)))])(int(input())))))


(t, r) = (input, range)
n = int(t())
a = sum((t()[-4] == 'h' for i in r(n)))
(a, b) = sorted([n - a, a])
print(sum((1 for i in r(15) if i ** 2 / 2 < a or i ** 2 + 1 >> 1 < b)))


n = int(input())
a = 0
b = 0
for i in range(n):
	s = input()
	if 'soft' == s[-4:]:
		a += 1
	else:
		b += 1
(a, b) = (max(a, b), min(a, b))
cur1 = 1
cur2 = 0
q = 1
while cur1 < a or cur2 < b:
	q += 1
	if q % 2:
		cur1 = (q // 2 + 1) * (q // 2 + 1) + q // 2 * (q // 2)
		cur2 = (q // 2 + 1) * (q // 2) * 2
	else:
		cur1 = cur2 = q // 2 * q
print(q)


from math import sqrt
n = int(input())
(s, h) = (0, 0)
for i in range(n):
	(a, b) = input().split()
	if b == 'soft':
		s += 1
	else:
		h += 1
k = 2 * max(s, h) - 1
if s + h > k:
	k += 1
t = int(sqrt(k))
if t * t < k:
	t += 1
print(t)


def main():
	n = int(input())
	(b, w) = (0, 0)
	for x in range(n):
		s = input().split()[1]
		if s == 'soft':
			b += 1
		else:
			w += 1
	for x in range(1, 100):
		a = x ** 2
		a1 = a // 2
		a2 = a - a1
		if max(b, w) <= a2 and min(b, w) <= a1:
			print(x)
			return
main()


n = int(input())
soft = 0
hard = 0
for i in range(n):
	a = input().split(' ')
	if a[1] == 'soft':
		soft = soft + 1
	else:
		hard = hard + 1
for i in range(100):
	tmp = i * i
	l = tmp >> 1
	r = tmp - l
	if l >= soft and r >= hard:
		print(i)
		break
	if r >= soft and l >= hard:
		print(i)
		break


n = int(input().strip())
p = 0
q = 0
for i in range(n):
	(a, b) = input().strip().split()
	if b == 'soft':
		p += 1
	else:
		q += 1
t = 0
while True:
	t += 1
	black = t * t // 2
	white = (t * t + 1) // 2
	if p <= black and q <= white or (p <= white and q <= black):
		print(t)
		break


n = int(input())
(a, b) = (0, 0)
for i in range(n):
	s = [j for j in input().split()]
	if s[1] == 'soft':
		a += 1
	else:
		b += 1
for i in range(1, 100):
	if i % 2 == 0:
		k = i * i
		if k // 2 >= a and k // 2 >= b:
			print(i)
			return
	else:
		k = i * i
		k //= 2
		if k + 1 >= max(a, b) and k >= min(a, b):
			print(i)
			return


n = int(input())
a = list()
for i in range(n):
	b = input().split()[1]
	a.append(b == 'soft' if 1 else 0)
white = a.count(1)
black = a.count(0)
for sz in range(1, 100):
	bl = 0
	wh = 0
	bl2 = 0
	wh2 = 0
	if sz % 2 == 0:
		wh = sz * sz // 2
		bl = sz * sz // 2
		wh2 = wh
		bl2 = bl
	else:
		wh = sz * sz // 2 + 1
		bl = sz * sz // 2
		wh2 = sz * sz // 2
		bl2 = sz * sz // 2 + 1
	if white <= wh and black <= bl or (white <= wh2 and black <= bl2):
		print(sz)
		exit()


n = int(input())
(a, b) = (0, 0)
for _ in range(n):
	(_, s) = input().split()
	if s == 'soft':
		a += 1
	else:
		b += 1
if a < b:
	(a, b) = (b, a)
x = 0
for i in range(1, 200):
	x += 1 + (i * 2 - 1) // 4 * 2
	if a <= x and b <= i ** 2 - x:
		print(i)
		break


from math import *
t = input
n = int(t())
a = sum((t()[-4] == 'h' for i in 'i' * n))
print(ceil(max(max(n - a, a) * 2 - 1, n) ** 0.5))


n = int(input())
soft = 0
hard = 0
for i in range(n):
	(_, t) = input().split()
	if t == 'soft':
		soft += 1
	else:
		hard += 1
for i in range(1, 100):
	s1 = soft
	h1 = hard
	s2 = soft
	h2 = hard
	for j in range(i):
		for k in range(i):
			if (j + k) % 2 == 0:
				s1 -= 1
				h2 -= 1
			else:
				s2 -= 1
				h1 -= 1
	if s1 <= 0 and h1 <= 0 or (s2 <= 0 and h2 <= 0):
		print(i)
		break


n = int(input())
(a, b) = (0, 0)
for _ in range(n):
	(t, s) = input().split()
	if s == 'hard':
		a += 1
	else:
		b += 1
(a, b) = sorted([a, b])
res = int((n - 1) ** 0.5)
while True:
	s = res * res
	if s // 2 >= a and s - s // 2 >= b:
		break
	res += 1
print(res)


(a, b) = (0, 0)
n = int(input())
for i in range(n):
	(x, y) = input().split()
	if y == 'soft':
		a += 1
	else:
		b += 1
for i in range(1, 1000):
	n = i * i
	y = n // 2
	x = n - y
	if a <= x and b <= y or (a <= y and b <= x):
		print(i)
		break


a = int(input())
(s, h) = (0, 0)
for i in range(a):
	q = input()
	if q.split()[-1] == 'soft':
		s += 1
	else:
		h += 1
m = max(s, h)
q = 1
while 1:
	if (q * q + 1) // 2 >= m:
		if q * q < s + h:
			q += 1
		print(q)
		break
	q += 1


x = int(input())
arr = [0, 0]
for i in range(x):
	(cheese, typ) = input().split()
	if typ == 'soft':
		arr[0] += 1
	else:
		arr[1] += 1
test = int(max(arr[0], arr[1]))
test2 = int(min(arr[0], arr[1]))
for i in range(10000):
	cap = i * i
	capt = cap / 2
	cap = capt + cap % 2
	if cap >= test and capt >= test2:
		print(i)
		break


N = int(input())
(w, b) = (0, 0)
for n in range(N):
	(cheese, color) = input().split()
	if color == 'hard':
		b += 1
	else:
		w += 1
for k in range(1, 16):
	if b <= k ** 2 // 2 and w <= k ** 2 // 2 or (k % 2 == 1 and max(b, w) <= (k ** 2 + 1) // 2 and (b + w <= k ** 2)):
		print(k)
		break


def counts(n: int):
	if n % 2 == 0:
		return (n ** 2 // 2, n ** 2 // 2)
	return (n ** 2 // 2, n ** 2 - n ** 2 // 2)
(soft, hard) = (0, 0)
n = int(input())
for _ in range(n):
	(_, typ) = input().split()
	if typ == 'soft':
		soft += 1
	else:
		hard += 1

def solve(soft, hard):
	for k in range(1, 1000):
		(max_white, max_black) = counts(k)
		if soft <= max_white and hard <= max_black or (soft <= max_black and hard <= max_white):
			return k
print(solve(soft, hard))


n = int(input())
sf = 0
hd = 0
for _ in range(n):
	(_, t) = input().split()
	if t == 'soft':
		sf += 1
	else:
		hd += 1
for i in range(1, 20):
	if sf <= (i ** 2 + 1) // 2 and hd <= (i ** 2 + 1) // 2 and (sf + hd <= i ** 2):
		print(i)
		break


def mp():
	return map(int, input().split())
n = int(input())
s = h = 0
for i in range(n):
	if list(input().split())[1][0] == 's':
		s += 1
	else:
		h += 1
c = 0
for i in range(1, 1000):
	if i % 2 == 0:
		c += i - 1
	else:
		c += i
	if c >= s and i ** 2 - c >= h or (c >= h and i ** 2 - c >= s):
		print(i)
		break


N = int(input())
A = 0
for _ in range(N):
	if input().split()[1] == 'hard':
		A += 1
B = N - A
if A > B:
	(A, B) = (B, A)
n = 1
while not (A <= n * n // 2 and B <= n * n // 2 + n % 2):
	n += 1
print(n)


n = int(input())
x = y = 0
for i in range(n):
	(s, t) = input().split()
	if t == 'soft':
		x += 1
	else:
		y += 1
if x < y:
	(x, y) = (y, x)
for i in range(1, 200):
	if (i ** 2 + 1) // 2 >= x and i ** 2 // 2 >= y:
		print(i)
		break


n = int(input())
s = 0
h = 0
for i in range(n):
	(a, b) = input().split()
	if b == 'soft':
		s += 1
	else:
		h += 1
mx = max(s, h)
mn = min(s, h)
pq = [(1, 0), (2, 2), (5, 4), (8, 8), (13, 12), (18, 18), (25, 24), (32, 32), (41, 40), (50, 50), (61, 60), (72, 72), (85, 84), (98, 98), (113, 112)]
for i in range(len(pq)):
	if mx <= pq[i][0] and mn <= pq[i][1]:
		print(i + 1)
		break


L = input().split()
n = int(L[0])
scnt = hcnt = 0
for i in range(0, n):
	L = input().split(' ')
	if L[1] == 'soft':
		scnt += 1
	else:
		hcnt += 1
for i in range(1, 100):
	if scnt <= (i * i + 1) / 2 and hcnt <= (i * i + 1) / 2 and (scnt + hcnt <= i * i):
		print(i)
		break


N = int(input())
a = 0
for i in range(N):
	if input().split()[1] == 'hard':
		a += 1
b = N - a
if a > b:
	(a, b) = (b, a)
n = 1
while not (a <= n * n // 2 and b <= n * n // 2 + n % 2):
	n += 1
print(n)


n = int(input())
p = 0
q = 0
for i in range(n):
	(x, y) = input().split()
	if y == 'soft':
		p += 1
	else:
		q += 1
for i in range(1, 100):
	if (i * i + 1) // 2 >= p and i * i // 2 >= q or ((i * i + 1) // 2 >= q and i * i // 2 >= p):
		print(i)
		break


n = int(input())
a = 0
b = 0
for i in range(n):
	(x, y) = map(str, input().split())
	if y == 'soft':
		a += 1
	else:
		b += 1
c = max(a, b)
if a % 2 == 1 and b % 2 == 1 and (a == b):
	c = a + 1
for i in range(1000):
	kol = (i * i + 1) / 2
	if kol >= c:
		print(i)
		break


n = int(input())
s = 0
h = 0
for i in range(n):
	res = input().strip().split()[-1]
	if res == 'soft':
		s += 1
	else:
		h += 1
(b, w) = (min(s, h), max(s, h))
for k in range(n):
	if k ** 2 // 2 >= b and k ** 2 - k ** 2 // 2 >= w:
		print(k)
		exit()
print(n)


n = int(input())
h = s = 0
for i in range(n):
	if input().split(' ')[1] == 'hard':
		h += 1
	else:
		s += 1
if h < s:
	(h, s) = (s, h)
i = 1
while (i ** 2 + 1) // 2 < h or i ** 2 // 2 < s:
	i += 1
print(i)


n = int(input())
cheeses = {'soft': 0, 'hard': 0}
for i in range(n):
	(cheese, t) = input().split()
	cheeses[t] += 1
size = 1
while True:
	cells = size * size
	blacks = cells // 2
	if cells % 2:
		blacks += 1
	whites = blacks
	if blacks >= cheeses['hard'] and whites >= cheeses['soft'] and (cells >= cheeses['hard'] + cheeses['soft']):
		print(size)
		break
	size += 1


import sys
from math import ceil, floor
c = [ceil(n ** 2 / 2) for n in range(40)]
f = [floor(n ** 2 / 2) for n in range(40)]
n = int(sys.stdin.readline())
s_cnt = 0
h_cnt = 0
for _ in range(n):
	(t, h) = sys.stdin.readline().split()
	if h == 'hard':
		h_cnt += 1
	else:
		s_cnt += 1
idx = 0
a = max(s_cnt, h_cnt)
b = min(s_cnt, h_cnt)
while c[idx] < a:
	idx += 1
while f[idx] < b:
	idx += 1
print(idx)


n = int(input())
(soft, hard) = (0, 0)
for i in range(n):
	(sir, tip) = input().split()
	if tip == 'soft':
		soft += 1
	else:
		hard += 1
for k in range(100):
	a = k * k // 2
	b = k * k - a
	if soft <= a and hard <= b or (soft <= b and hard <= a):
		print(k)
		break


n = int(input())
hard = soft = 0
for i in range(n):
	cheese = input().split()
	if cheese[1] == 'hard':
		hard += 1
	else:
		soft += 1
i = 1
while True:
	if hard <= i * i // 2 and soft <= (i * i + 1) // 2 or (hard <= (i * i + 1) // 2 and soft <= i * i // 2):
		print(i)
		break
	i += 1


def main():
	n = int(input())
	(hard, soft) = (0, 0)
	while n:
		n -= 1
		if input().split()[1] == 'hard':
			hard += 1
		else:
			soft += 1
	if hard < soft:
		(hard, soft) = (soft, hard)
	assert soft <= hard
	side = 1
	while side ** 2 / 2 < soft or side ** 2 / 2 + (side & 1) < hard:
		side += 1
	print(side)
main()


n = int(input())
t = [i * i for i in range(100)]
mi = 0
for _ in range(n):
	tmp = input().split()[1]
	if tmp == 'soft':
		mi += 1
mi = min(mi, n - mi)
max = max(mi, n - mi)
if max == 1:
	print(n)
else:
	for i in range(99):
		if t[i] // 2 + t[i] % 2 < max <= t[i + 1] // 2 + t[i + 1] % 2:
			print(i + 1)
			break


N = int(input())
hard = 0
soft = 0
for _ in range(N):
	(_, tp) = input().split()
	if tp == 'hard':
		hard += 1
	else:
		soft += 1
top = max(soft, hard)
total = soft + hard
i = 1
while True:
	size = i * i
	val = size // 2
	if i % 2 != 0:
		val += 1
	if val >= top and size >= total:
		print(i)
		break
	i += 1


def solve(hard, soft):
	array = [1, 2, 5, 8, 13, 18, 25, 32, 41, 50, 61, 72, 85, 98, 113]
	numba = max(hard, soft)
	answa = 0
	for i in range(len(array)):
		if array[i] >= numba:
			answa = i + 1
			break
	if hard == soft and hard % 2 == 1:
		answa += 1
	return answa
x = int(input())
hard = 0
soft = 0
while x > 0:
	data = input().split()
	if data[1] == 'hard':
		hard += 1
	else:
		soft += 1
	x -= 1
print(solve(hard, soft))


n = int(input())
wcnt = 0
bcnt = 0
for i in range(n):
	(a, b) = input().split()
	if b == 'soft':
		bcnt = bcnt + 1
	else:
		wcnt = wcnt + 1
if wcnt > bcnt:
	t = wcnt
	wcnt = bcnt
	bcnt = t
lo = 1
hi = 100
while lo < hi:
	mid = (lo + hi) // 2
	if mid * mid // 2 < wcnt or mid * mid - mid * mid // 2 < bcnt:
		lo = mid + 1
	else:
		hi = mid
print(lo)


p = [1, 2, 5, 8, 13, 18, 25, 32, 41, 50, 61, 72, 85, 98, 113]
n = int(input())
s = h = 0
for i in range(n):
	a = input().split()[1]
	if a == 'soft':
		s += 1
	else:
		h += 1
if s > h:
	ma = s
else:
	ma = h
pp = 0
while ma > p[pp]:
	pp += 1
if s == h == p[pp] and p[pp] % 2 == 1:
	print(pp + 2)
else:
	print(pp + 1)


n = int(input())
cnt0 = 0
cnt1 = 0
for i in range(n):
	s = input().split()
	cnt0 += s[1] == 'soft'
	cnt1 += s[1] == 'hard'
for i in range(1000):
	k1 = i * i // 2
	k0 = i * i - k1
	if cnt0 <= k0 and cnt1 <= k1:
		print(i)
		break
	elif cnt0 <= k1 and cnt1 <= k0:
		print(i)
		break


n = int(input())
soft = 0
hard = 0
for i in range(n):
	(x, y) = input().split()
	if y == 'hard':
		hard += 1
	else:
		soft += 1
if hard < soft:
	(hard, soft) = (soft, hard)
for i in range(1, 100):
	x = i * (i // 2)
	if i % 2:
		x += (i + 1) // 2
	y = i * i - x
	if hard <= x and soft <= y:
		print(i)
		exit(0)


n = int(input())
black = 0
white = 0
for i in range(n):
	s = input().split()
	if s[1] == 'soft':
		black += 1
	else:
		white += 1
i = 1
while i % 2 and (black > i * i // 2 + 1 or white > i * i // 2) or (i % 2 == 0 and (black > i * i // 2 or white > i * i // 2)):
	i += 1
j = i + 0
i = 1
while i % 2 and (white > i * i // 2 + 1 or black > i * i // 2) or (i % 2 == 0 and (white > i * i // 2 or black > i * i // 2)):
	i += 1
print(min(i, j))