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

Difficulty: introductory

Starter code:

Solutions:
# python3


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())
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


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)

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):
    # field1 = [[0] * i for j in range(i)]
    # field2 = [[0] * i for j in range(i)]

    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



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()


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

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)

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)
        return


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())
# n, m = map(int, input().split())
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


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

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())
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())
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):
    # soft::
    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())
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

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())
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)

n = int(input())
a = 0
b = 0
for i in range(n):
    x, y = list(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().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


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



# A
# print(int(input()) % 2)

# B
# good = ['cool', 'great', 'not bad']
# for i in range(10):
#     print(i, flush=True)
#     r = input().strip().lower()
#     for g in good:
#         if g in r:
#             print('normal')
#             return
# print('grumpy')

# C
# input()
# a = [int(x) for x in input().split()]
# while a:
#     for i in range(len(a)-1):
#         if abs(a[i] - a[i+1]) >= 2:
#             print('NO')
#             return
#     a.pop(a.index(max(a)))
# print('YES')

# D
# print(20)

# E
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

# G
# s = [ord(x) in input().strip()]


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)
        return
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

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))