1. Підпослідовність

Максимальна оцінка: 40 балів
Обмеження на час: 0,15 сек.
Обмеження на пам’ять: 4 MБ
Вхідний файл: subseq.in
Вихідний файл: subseq.out
Програма: subseq.*

Завдання
Створити програму для обчислення довжини найдовшої спільної підпос­лідов­ності двох послідов­ностей {x_j}^k_{j = 1} і {y_j}^l_{j = 1}.

Вхідні дані
Файл містить у вказаному порядку невід'ємні цілі числа k, x₁, x₂, …, x_k, l, y₁, y₂, …, y_l, де k + l < 16 000, а члени послідовностей менші за 65 432.

Вихідні дані
Файл має міститти лише шукану довжину найдовшої спільної підпос­лідов­ності.

Приклад

2. Сiм'я

Максимальна оцінка: 92 балів
Обмеження на час: 0,15 сек.
Обмеження на пам’ять: 4 MБ
Вхідний файл: family.in
Вихідний файл: family.out
Програма: family.*

Завдання
Створiть програму, яка визначає ступiнь родичiвства чи свояцтва.

Вхідні дані
Перші два рядки файлу мiстять по одному iменi двох рiзних персонажiв.

Усi наступні рядки файлу мають такий вигляд:

• iм'я персонажу в називному вiдмiнку;
• « - » (тире, вiддiлене прогалинами);
• одне з таких слiв: син, донька, дружина;
• iм'я персонажу в родовому вiдмiнку.

Родовий відмінок іменників в українській мові утворюють:

• у I-iй вiдмiнi замiною закiнчень -а, -я на -и, -ї;

• у II-iй вiдмiнi додаванням закiнчення -a, якщо iменник закiнчується на приголосний (врахуйте йотування пiсля й i виключення Ігоря), або змiною закiнчення -о на -а.

Вхiднi данi не мiстять iмен з III-ої вiдмiни й iмен з II вiдмiни, якi закiнчуються на м'який знак. Імена складаються з одного слова. Розрiзняються персонажi з однаковими iменами, якщо цi iмена записано рiзними за висотою лiтерами (великими чи малими). Імена мiстять не бiльше 20 лiтер. Кiлькiсть персонажiв не перевищує 30.

Вихідні дані
Файл повинен мати такий вигляд:

• iм'я з 1-го рядка family.in (закiнчення подати малими лiтерами);
• « - » (тире, вiддiлене прогалинами);
• одне з таких слiв, видiлених курсивом:
  • батько;
  • мати;
  • син;
  • донька;
  • чоловік;
  • дружина;
  • дід — батьків або материн тато;
  • баба — батькова або материна мати;
  • прадід — батько діда або баби;
  • прабаба — мати діда або баби;
  • онук — син дочки або сина;
  • онука — донька сина або дочки;
  • правнук — син онука або онучки;
  • правнучка — донька онука або онучки;
  • брат — кожен із синів щодо інших дітей тих самих батьків;
  • сестра — кожна із доньок щодо інших дітей тих самих батьків;
  • стрий — брат батька або чоловік батькової сестри;
  • стрийна — сестра батька або дружина батькового брата;
  • вуй — брат матері або чоловік материної сестри;
  • вуйна — сестра матері або дружина материного брата;
  • небіж — син брата або сестри (слова братанець і сестринець не вживати);
  • небога — донька брата або сестри (слова братаниця і сестриниця не вживати);
  • двоюрідний брат — син дядька або тітки;
  • двоюрідна сестра — дочка дядька або тітки;
  • триюрідний брат — син двоюрідних дядька або тітки;
  • триюрідна сестра — дочка двоюрідних дядька або тітки;
  • внучатий племінник — син небожа або небоги;
  • внучата племінниця — дочка небожа або небоги;
  • свекор — батько чоловіка;
  • свекруха — мати чоловіка;
  • тесть — батько дружини;
  • теща — матір дружини;
  • сват — батько або родич одного з подружжя щодо батьків або родичів іншого;
  • сваха — мати або родичка одного з подружжя щодо батьків або родичів іншого;
  • дівер — брат чоловіка;
  • діверка — дружина дівера;
  • зовиця — сестра чоловіка;
  • зять — чоловік дочки;
  • невістка — дружина сина;
  • свояк — брат дружини або чоловік сестри дружини;
  • своячка — сестра дружини або дружина брата дружини;
  • швагер — чоловік сестри;
  • братова — дружина брата
  — в даній задачі зміст понять зять, невістка звужено;
• ім'я з 2-го рядка family.in у родовому вiдмiнку, причому закiнчення треба подати малими лiтерами.

Зауваження щодо кодування літер кирилиці: використовувати кодову таблицю cp1251. Якщо є сумніви, код програми і вміст тестових файлів потрібно набрати/проглянути, використовуючи Блокнот (Notepad).