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