Programozás‎ > ‎Feladatok‎ > ‎

Játék (2013)

Ádám és Éva kétszemélyes játékot játszik egy N mezőt tartalmazó játéktáblán. A játék során az első mezőről indulva, felváltva lépve, egy bábut mozgatnak a játéktáblán, ugyanarra a mezőre többször is léphetnek. Egy adott mezőről csak szomszédos mezőre lehet lépni egy lépésben. Minden mezőre rá van írva egy pontszám. Ádám kezdi a játékot. Ha Ádám az aktuális lépésében az m mezőre lép, amire p pontszám van írva, akkor összpontszáma p értékkel növelődik. Ha Éva az m mezőre lép, amire p pontszám van írva, akkor Ádám összpontszámát csökkentik p értékkel. Ádám célja, hogy a lehető legtöbb összpontot szerezze, Éva célja pedig az, hogy Ádám a lehető legkevesebb összpontot szerezzen a játék során. Az összpontszám lehet negatív is, ekkor Ádám fizet Évának a játék végén.  

Feladat

Készíts programot, amely kiszámítja, hogy mekkora az a legnagyobb összpontszám, amit Ádám biztosan meg tud szerezni K lépéses játékban, bárhogyan is lép Éva!

Bemenet

A jatek.be szöveges állomány első sorában két egész szám van egy szóközzel elválasztva, a játéktáblán lévő mezők N száma (1≤N≤500) és a játékban megteendő lépések K száma (1≤K≤2000). (Tehát mindkét játékos K lépést tesz felváltva.) A második sor pontosan N pozitív egész számot tartalmaz egy-egy szóközzel elválasztva, az m-edik szám az m sorszámú mezőn lévő pontszám értéke, legfeljebb 1000. A következő N sor írja le a mezők szomszédjait, tehát, hogy adott mezőről mely mezőkre lehet lépni közvetlenül. Az állomány m+2-edik sora az m-edik mező szomszédjait tartalmazza egy-egy szóközzel elválasztva, 0-val zárva. Minden mezőről legalább egy másik mezőre lehet lépni. Minden mezőnek önmaga is lehet szomszédja.

Kimenet

A jatek.ki szöveges állomány első és egyetlen sorába egy egész számot kell írni, a legnagyobb összpontszámot, amit Ádám meg tud szerezni K lépéses játékban, bárhogyan is lép Éva!

Példa

Bemenet  Kimenet
5 2
2 5 8 9 3
3 2 0
4 1 0
2 5 0
3 2 0
4 2 1 0		4


Tesztadatok

Címkék

A feladat forrása: NTOITV 2013, 11-13. évfolyam, döntő
Algoritmusok: dinamikus programozás