Történelemvizsga

Az informatikában sok probléma foglalja magában valamilyen érték maximalizálását bizonyos megszorítások mellett.

Vegyünk például egy történelemvizsgát, amelynek során a diákoknak kronológiai sorrendbe kell rakniuk néhány történelmi eseményt. Azok a diákok, akik az összes eseményt helyesen rakják sorba, maximális pontszámot kapnak. Hogyan adjunk azonban részpontszámot azoknak a diákoknak, akik egy vagy több eseményt hibásan sorolnak be?

Íme néhány lehetőség a részpontszámok adására:

1. 1 pont jár minden olyan eseményre, amelynek a sorszáma megegyezik a helyes sorszámmal.
2. 1 pont jár minden eseményre a leghosszabb olyan (nem feltétlenül összefüggő) eseménysorozatban, amelyben az események egymáshoz viszonyítva helyes sorrendben szerepelnek.

Ha például négy esemény helyes sorrendje 1 2 3 4, akkor az 1 3 2 4 sorrend 2 pontot ér az első módszer szerint (az 1-es és 4-es események sorszáma helyes), és 3 pontot ér a második módszer szerint (az 1 2 4 és az 1 3 4 eseménysorozat is egymáshoz viszonyítva helyes sorrendben tartalmazza az eseményeket).

Ebben a feladatban egy olyan programot kell írnod, amely ilyen jellegű feleleteket pontoz a második módszer szerint.

Legyen adott n esemény: 1, 2, …, n! Ha ismerjük ezen események c₁, c₂, …, c_n helyes kronológiai sorrendjét, ahol 1 ≤ c_i ≤ n az i-edik esemény sorszáma a helyes kronológiai sorrendben, valamint ismerjük egy diák által adott r₁, r₂, …, r_n sorrendet, ahol 1 ≤ r_i ≤ n az i-edik eseménynek a diák által megadott sorszáma, határozd meg a diák válaszában a leghosszabb olyan (nem feltétlenül összefüggő) eseménysorozat hosszát, amelyben az események egymáshoz viszonyítva helyes kronológiai sorrendben szereplnek!

A bemenet specifikációja

A bemenet első sora egyetlen n egész számot tartalmaz, amely az események számát adja meg (2 ≤ n ≤ 20). A második sor n egész számból áll, amelyek n esemény helyes kronológiai sorrendjét írják le. A további sorok mindegyikében szintén n egész szám szerepel, amelyek az n esemény egy-egy diák által megadott kronológiai sorrendjét reprezentálják. Ezen sorok mindegyike n számot tartalmaz az [1, …, n] intervallumból, és minden szám pontosan egyszer fordul elő mindegyik sorban. Az egy sorban szereplő számokat egy vagy több szóköz választja el egymástól.

A kimenet specifikációja

A diákok által megadott mindegyik eseménysorrendre az adott sorrendre járó pontszámot kell a kimenetre írni, soronként egyet-egyet.

1. példa bemenet

1. 4
2. 4 2 3 1
3. 1 3 2 4
4. 3 2 1 4
5. 2 3 4 1

letöltés szöveges állományként

Az 1. példa bemenethez tartozó kimenet

1. 1
2. 2
3. 3

letöltés szöveges állományként

2. példa bemenet

1. 10
2. 3 1 2 4 9 5 10 6 8 7
3. 1 2 3 4 5 6 7 8 9 10
4. 4 7 2 3 10 6 9 1 5 8
5. 3 1 2 4 9 5 10 6 8 7
6. 2 10 1 3 8 4 9 5 7 6

letöltés szöveges állományként

A 2. példa bemenethez tartozó kimenet

1. 6
2. 5
3. 10
4. 9

letöltés szöveges állományként