eolymp
bolt
Try our new interface for solving problems
Məsələlər

Любитель порядка

Любитель порядка

Zaman məhdudiyyəti 2 saniyə
Yaddaşı istafadə məhdudiyyəti 64 MiB

Франк Энштейн - очень консервативный учитель средней школы. Он хочет взять некоторых из своих учеников на экскурсию, но опасается, что некоторые из них могут стать конфликтной или влюбленной парой. Чтобы исключить такую возможность, он придумал ряд правил, которые по его мнению уменьшают вероятность двум людям образовать такую пару:

  • Разница в их росте должна превышать 40 см.

  • Они должны быть одного пола.

  • Они должны любить разные стили музыки.

  • Их любимый вид спорта - один и тот же.

Таким образом, для любых двух учеников, которых он возьмёт на экскурсию, они должны отвечать, по крайней мере, одному из вышеуказанных требований. Помогите ему найти максимальное число учеников, которые он может взять на экскурсию, учитывая информацию о них.

Giriş verilənləri

В первой строке задано число Т100 - количество тестов. Первая строка каждого теста содержит целое число N500 - количество учащихся в школе. Следующие строки описывают каждого ученика и состоят из четырех, разделенных пробелами, элементов данных:

  • Целое число h ­­- рост в см;

  • символ 'F' для женщин, или "М" для мужчин;

  • слово, описывающее предпочтительный стиль музыки;

  • слово с именем любимого вида спорта.

Каждая строка содержит не более 100 символов, и во входных данных нет пустых строк.

Çıxış verilənləri

Для каждого теста на выходе должна быть одна строка с искомым максимальным количеством учащихся, которые учитель может взять на экскурсию.

Nümunə

Giriş verilənləri #1
1
8
27 M romance programming
194 F baroque programming
67 M baroque ping-pong
51 M classicism programming
80 M classicism Paintball
35 M baroque ping-pong
39 F romance ping-pong
110 M romance Paintball
Çıxış verilənləri #1
7