Have you ever played Hanabi? If not, then you've got to try it out! This problem deals with a simplified version of the game.

Overall, the game has 25 types of cards (5 distinct colors and 5 distinct values). Borya is holding n cards. The game is somewhat complicated by the fact that everybody sees Borya's cards except for Borya himself. Borya knows which cards he has but he knows nothing about the order they lie in. Note that Borya can have multiple identical cards (and for each of the 25 types of cards he knows exactly how many cards of this type he has).

The aim of the other players is to achieve the state when Borya knows the color and number value of each of his cards. For that, other players can give him hints. The hints can be of two types: color hints and value hints. 

A color hint goes like that: a player names some color and points at all the cards of this color. 

Similarly goes the value hint. A player names some value and points at all the cards that contain the value.

Determine what minimum number of hints the other players should make for Borya to be certain about each card's color and value.


-----Input-----

The first line contains integer n (1 ≤ n ≤ 100) — the number of Borya's cards. The next line contains the descriptions of n cards. The description of each card consists of exactly two characters. The first character shows the color (overall this position can contain five distinct letters — R, G, B, Y, W). The second character shows the card's value (a digit from 1 to 5). Borya doesn't know exact order of the cards they lie in.


-----Output-----

Print a single integer — the minimum number of hints that the other players should make.


-----Examples-----
Input
2
G3 G3

Output
0

Input
4
G4 R4 R3 B3

Output
2

Input
5
B1 Y1 W1 G1 R1

Output
4



-----Note-----

In the first sample Borya already knows for each card that it is a green three.

In the second sample we can show all fours and all red cards.

In the third sample you need to make hints about any four colors.

Source: codeforces | Difficulty: MEDIUM_HARD
Tags: Bit manipulation

Implementation

Complete search


Solutions:
input()
p = {(1 << 'RGBYW'.index(c)) + (1 << int(k) + 4) for (c, k) in input().split()}
print(min((bin(t).count('1') for t in range(1024) if len({t & q for q in p}) == len(p))))


def main():
	p = [1]
	for i in range(1, 11):
		p.append(p[i - 1] * 2)
	hr = '12345RGBYW'
	gt = {'1': 0, '2': 1, '3': 2, '4': 3, '5': 4, 'R': 5, 'G': 6, 'B': 7, 'Y': 8, 'W': 9}

	def check(c, mask):
		tmp = gt[c]
		if mask // p[tmp] % 2 == 1:
			return True
		return False

	def count(mask):
		tmp = 0
		while mask > 0:
			tmp += mask % 2
			mask //= 2
		return tmp
	n = int(input())
	a = list(set(input().split()))
	n = len(a)
	ans = 10
	for mask in range(1023):
		f = True
		for i in range(n):
			for j in range(i + 1, n):
				if a[i] == a[j]:
					pass
				elif a[i][1] != a[j][1] and (check(a[i][1], mask) or check(a[j][1], mask)):
					pass
				elif a[i][0] != a[j][0] and (check(a[i][0], mask) or check(a[j][0], mask)):
					pass
				else:
					f = False
					break
			if not f:
				break
		if f:
			ans = min(ans, count(mask))
	print(ans)
main()


def read(mode=2):
	inputs = input().strip()
	if mode == 0:
		return inputs
	if mode == 1:
		return inputs.split()
	if mode == 2:
		return [int(x) for x in inputs.split()]

def write(s='\n'):
	if isinstance(s, list):
		s = ' '.join(map(str, s))
	s = str(s)
	print(s, end='')
import itertools
covers = itertools.product([0, 1], repeat=10)
(n,) = read()
s = read(1)
a = [0] * 25
colors = 'RGBYW'
for i in s:
	a[colors.index(i[0]) * 5 + int(i[1]) - 1] |= 1

def check(cover):
	global a
	unknowns = [0] * 11
	for i in range(25):
		if not a[i]:
			continue
		id = -1
		if not cover[i % 5]:
			id = 5 + i // 5
		if not cover[5 + i // 5]:
			if id == -1:
				id = i % 5
			else:
				id = 10
		if id > -1:
			if unknowns[id]:
				return False
			unknowns[id] = 1
	return True
mn = 99
for i in covers:
	if check(i):
		mn = min(mn, sum(i))
print(mn)


from itertools import combinations
n = int(input())
colors = {'R': 0, 'G': 1, 'B': 2, 'Y': 3, 'W': 4}
letters = {'1': 0, '2': 1, '3': 2, '4': 3, '5': 4}
l = list(set(list(input().split())))

def checker(hint, cards):
	for i in cards:
		for j in cards:
			if i == j:
				continue
			if i[0] == j[0]:
				if i[1] not in hint and j[1] not in hint:
					return False
			elif i[1] == j[1]:
				if i[0] not in hint and j[0] not in hint:
					return False
			elif i[0] not in hint and i[1] not in hint and (j[0] not in hint) and (j[1] not in hint):
				return False
	return True
result = []
for i in l:
	if i[0] not in result:
		result.append(i[0])
	if i[1] not in result:
		result.append(i[1])
all_hints = []
for i in range(1, len(result) + 1):
	comb = combinations(result, i)
	all_hints += comb
min_hint = len(result)
if len(l) == 1:
	print(0)
else:
	for i in all_hints:
		if checker(i, l):
			min_hint = min(len(i), min_hint)
	print(min_hint)


input()
colour = dict(zip('RGBYW', range(5)))
cards = {(colour[c], ord(v) - ord('1')) for (c, v) in input().split()}
print(min((bin(cs).count('1') + bin(vs).count('1') for cs in range(1 << 5) for vs in range(1 << 5) if len({(c if cs >> c & 1 else -1, v if vs >> v & 1 else -1) for (c, v) in cards}) == len(cards))))


input()
colour = {'R': 0, 'G': 1, 'B': 2, 'Y': 3, 'W': 4}
cards = {(colour[c], ord(v) - ord('1')) for (c, v) in input().split()}

def ok(cs, vs):
	return len({(c if cs >> c & 1 else -1, v if vs >> v & 1 else -1) for (c, v) in cards}) == len(cards)
print(min((bin(cs).count('1') + bin(vs).count('1') for cs in range(1 << 5) for vs in range(1 << 5) if ok(cs, vs))))


A = {'R': 0, 'G': 1, 'B': 2, 'Y': 3, 'W': 4}

def bit_m(s):
	num = 1 << int(s[1]) - 1
	symb = 1 << A[s[0]] + 5
	return num | symb
n = int(input())
cards = list(set(input().split()))
res = [0 for i in range(len(cards))]
mask = [bit_m(cards[i]) for i in range(len(cards))]

def make_res(Q, cards):
	for i in range(len(cards)):
		if mask[i] & Q:
			res[i] |= Q

def check():
	for i in range(len(res)):
		for j in range(i + 1, len(res)):
			if res[i] == res[j]:
				return 0
	return 1
quest = [1 << i for i in range(10)]
cnt = 11
for i in range(0, 1023):
	cnt_now = 0
	res = [0 for i in range(len(cards))]
	for j in range(10):
		if 1 << j & i != 0:
			cnt_now += 1
			make_res(quest[j], cards)
	if check():
		cnt = min(cnt, cnt_now)
print(cnt)


input()
p = {(1 << 'RGBYW'.index(c)) + (1 << int(k) + 4) for (c, k) in input().split()}
mn = 20
res = 90
for i in range(1024):
	if len(p) == len(set((i & j for j in p))):
		mn = min(mn, bin(i).count('1'))
print(mn)


from itertools import *
power = lambda i: chain.from_iterable((combinations(i, r) for r in range(len(i) + 1)))
input()
cards = set(input().split())
print(min((len(s) for s in power('RGBYW12345') if len(set((str(set(s) & set(t)) for t in cards))) == len(cards))))


from collections import Counter
n = int(input())
pcards = set(input().split())
qs = 'RGBYW12345'
best = 10
for mask in range(1024):
	cnt = 0
	tmp = mask
	while tmp:
		tmp &= tmp - 1
		cnt += 1
	knows = [qs[i] for i in range(10) if mask >> i & 1]
	cards = [c for c in pcards if not c[0] in knows or not c[1] in knows]
	if not cards:
		best = min(best, cnt)
		continue
	for q in knows:
		cou = sum((1 for c in cards if q in c))
		if cou > 1:
			cnt = 100500
			break
	coun = sum((1 for c in cards if not c[0] in knows and (not c[1] in knows)))
	if coun > 1:
		cnt = 100500
	best = min(best, cnt)
print(best)


from itertools import combinations
from copy import copy

def variants(a):
	for i in range(6):
		for j in combinations(a, i):
			yield j

def main():
	input()
	cards = set(((i[0], int(i[1])) for i in input().split()))
	values = [0 for i in range(6)]
	masks = {i: 0 for i in 'RGBYW'}
	for i in cards:
		values[i[1]] += 1
		masks[i[0]] += 1
	result = float('inf')
	for i in variants('RGBYW'):
		for j in variants(list(range(1, 6))):
			c = copy(cards)
			(v, m) = (values[:], copy(masks))
			for k in copy(c):
				if k[0] in i and k[1] in j:
					v[k[1]] -= 1
					m[k[0]] -= 1
					c.remove(k)
			for l in range(11):
				for k in copy(c):
					if v[k[1]] == 1 and k[1] in j or (m[k[0]] == 1 and k[0] in i):
						v[k[1]] -= 1
						m[k[0]] -= 1
						c.remove(k)
			if len(c) <= 1:
				result = min(result, len(i) + len(j))
	print(result)
main()


from itertools import chain, combinations
from copy import deepcopy

def powerset(iterable):
	s = list(iterable)
	return chain.from_iterable((combinations(s, r) for r in range(len(s) + 1)))
n = int(input())
locations = input().split()
matrixG = [[0] * 5 for i in range(5)]
for i in locations:
	if i[0] == 'R':
		matrixG[0][int(i[1]) - 1] += 1
	elif i[0] == 'G':
		matrixG[1][int(i[1]) - 1] += 1
	elif i[0] == 'B':
		matrixG[2][int(i[1]) - 1] += 1
	elif i[0] == 'Y':
		matrixG[3][int(i[1]) - 1] += 1
	elif i[0] == 'W':
		matrixG[4][int(i[1]) - 1] += 1
for i in list(powerset(range(10))):
	matrix = deepcopy(matrixG)
	color = []
	value = []
	for j in i:
		if j <= 4:
			color.append(j)
		else:
			value.append(j)
	for v in value:
		for c in color:
			matrix[c][v - 5] = 0
		ctr = 0
		for r in range(5):
			if matrix[r][v - 5] == 0:
				ctr += 1
		if ctr == 4:
			for r in range(5):
				matrix[r][v - 5] = 0
	for c in color:
		if matrix[c].count(0) == 4:
			matrix[c] = [0] * 5
	ctr = 0
	for k in range(5):
		for j in range(5):
			if matrix[k][j] == 0:
				ctr += 1
	if ctr == 24:
		print(len(i))
		break


n = int(input())
data = set(input().split())
cards = []
lets = 'RGBYW'
ans = 10
for i in data:
	p1 = lets.find(i[0])
	p2 = int(i[1]) - 1
	cards.append(2 ** p1 + 2 ** (p2 + 5))
for i in range(1024):
	good = True
	for j in range(len(cards) - 1):
		for k in range(j + 1, len(cards)):
			if cards[j] & i == cards[k] & i:
				good = False
	if good:
		ones = 0
		now = i
		while now != 0:
			ones += now % 2
			now //= 2
		ans = min(ans, ones)
print(ans)


def check(hint, Card):
	for i in Card:
		for j in Card:
			if i == j:
				continue
			elif i[0] == j[0]:
				if i[1] not in hint and j[1] not in hint:
					return False
			elif i[1] == j[1]:
				if i[0] not in hint and j[0] not in hint:
					return False
			elif i[0] not in hint and i[1] not in hint and (j[0] not in hint) and (j[1] not in hint):
				return False
	return True
HH = 'RGBYW12345'
n = int(input())
Card = list(input().split(' '))
ans = 20
for i in range(1024):
	hint = ''
	cnt = 0
	for j in range(10):
		if 2 ** j & i > 0:
			hint += HH[j]
			cnt += 1
	if check(hint, Card):
		ans = min(ans, cnt)
print(ans)


def Checker(hint, card):
	for a in card:
		for b in card:
			if a == b:
				continue
			elif a[0] == b[0]:
				if a[1] not in hint and b[1] not in hint:
					return False
			elif a[1] == b[1]:
				if a[0] not in hint and b[0] not in hint:
					return False
			elif a[0] not in hint and a[1] not in hint and (b[0] not in hint) and (b[1] not in hint):
				return False
	return True
user_input = int(input())
user_input = input()
Card = user_input.split(' ')
possible_chars = 'RGBYW12345'
final_answer = 10
card_set = set(Card)
if len(card_set) == 1:
	print('0')
else:
	for i in range(1024):
		hint = ''
		counter = 0
		for j in range(9, -1, -1):
			if i - 2 ** j > 0:
				hint += possible_chars[j]
				i -= 2 ** j
				counter += 1
		if Checker(hint, card_set):
			final_answer = min(final_answer, counter)
	print(final_answer)


import sys
n = int(sys.stdin.readline())
cards = list(set(sys.stdin.readline().split()))
m = 10

def count_ones(n):
	cnt = 0
	while n > 0:
		if n & 1:
			cnt += 1
		n //= 2
	return cnt

def split(l, c):
	(a, b) = ([], [])
	for card in l:
		if c in card:
			a.append(card)
		else:
			b.append(card)
	return (a, b)

def is_clear(cards, h):
	cl = [cards]
	namig = 'RGBYW12345'
	for i in range(10):
		hint = h & 1 == 1
		h //= 2
		if not hint:
			continue
		cl2 = []
		for c in cl:
			(a, b) = split(c, namig[i])
			if len(a) >= 2:
				cl2.append(a)
			if len(b) >= 2:
				cl2.append(b)
		cl = cl2
	cl = [x for x in cl if len(x) >= 2]
	return len(cl) == 0
for h in range(2 ** 10):
	hints = count_ones(h)
	if is_clear(cards, h):
		m = min(m, hints)
print(m)


import itertools
input()
cards = tuple(set(str.split(input())))
n = len(cards)
if n == 1:
	print(0)
	return
symbols = 'RGBYW12345'
for l in range(1, 10):
	for comb in itertools.combinations(symbols, l):
		positions = [cards] * n
		for symbol in comb:
			for i in range(n):
				if symbol in cards[i]:
					positions[i] = tuple([c for c in positions[i] if symbol in c])
				else:
					positions[i] = tuple([c for c in positions[i] if symbol not in c])
		if sum(map(len, positions)) == n:
			print(l)
			return


n = int(input())
data = set(input().split())
temp = 'RGBYW'
c = []
res = 10
for i in data:
	p1 = temp.find(i[0])
	p2 = int(i[1]) - 1
	c.append(2 ** p1 + 2 ** (p2 + 5))
for i in range(1024):
	ok = True
	for j in range(len(c) - 1):
		for k in range(j + 1, len(c)):
			if c[j] & i == c[k] & i:
				ok = False
	if ok:
		tt = 0
		inow = i
		while inow != 0:
			tt += inow % 2
			inow //= 2
		res = min(res, tt)
print(res)


n = int(input())
colour = dict(zip('RGBYW', range(5, 10)))
cards = list({2 ** colour[c] + 2 ** (ord(v) - ord('1')) for (c, v) in input().split()})
ans = 10
n = len(cards)
if n > 1:
	for bit in range(2 ** 10):
		ok = True
		for i in range(n - 1):
			for j in range(i + 1, n):
				if cards[i] & cards[j] == 0:
					if (cards[i] | cards[j]) & bit == 0:
						ok = False
						break
				elif cards[i] != cards[j]:
					if (cards[i] ^ cards[j]) & bit == 0:
						ok = False
						break
			if not ok:
				break
		if ok:
			ans = min(bin(bit).count('1'), ans)
	print(ans)
else:
	print(0)