Az I/S. 48. feladat (2020. november)

I/S. 48. Egy sakktáblára szeretnénk minél több vezért elhelyezni úgy, hogy egyik se üsse a másikat. Valaki már el is helyezett \(\displaystyle K\) vezért a táblára úgy, hogy egyik se üti a másikat. Adjuk meg, hogy legfeljebb hány vezért helyezhetünk még el a táblára úgy, hogy a táblán levő vezérek közül egyik se üsse a másikat.

Bemenet: az első sor tartalmazza a \(\displaystyle K\) számot. A következő \(\displaystyle K\) sor mindegyike egy \(\displaystyle x\) és egy \(\displaystyle y\) számot tartalmaz: az adott vezért az \(\displaystyle x\)-edik sor \(\displaystyle y\)-adik oszlopába tették le.

Kimenet: adjuk meg, hogy legfeljebb még hány vezért tehetünk a táblára úgy, hogy egyik se üsse a másikat.

Példa:

Korlátok: \(\displaystyle 1\le K\le 7\), \(\displaystyle 1\le x,y\le 8\). Időkorlát: 0,3 mp.

Értékelés: a pontok 50%-a kapható, ha \(\displaystyle K = 7\).

Beküldendő egy is48.zip tömörített állományban a megfelelően dokumentált és kommentezett forrásprogram, amely tartalmazza a megoldás lépéseit, valamint megadja, hogy a program melyik fejlesztői környezetben futtatható.

(10 pont)

A beküldési határidő 2020. december 15-én LEJÁRT.

Visszalépéses kereséssel megkereshető az összes olyan állapot, ami helyes, ezek közül kiválasztjuk az optimálisat.

Statisztika:

11 dolgozat érkezett.
10 pontot kapott:	Horcsin Bálint, Kovács Alex, Sándor Péter, Szakács Ábel, Varga 256 Péter.
9 pontot kapott:	Bagladi Milán Zsolt, Papp Marcell Miklós, Ürmössy Dorottya.
8 pontot kapott:	1 versenyző.
7 pontot kapott:	1 versenyző.
2 pontot kapott:	1 versenyző.

A KöMaL 2020. novemberi informatika feladatai