Az I. 682. feladat (2025. december)

I. 682. András széles könyvespolcán egymás mellett sorakoznak a könyvek. A legtöbb könyv András kedvenc szerzőitől van, némelyiktől jó néhány, de vannak olyan szerzők is, akiktől csak egy könyv. András könyvei egy sorban egymás mellett vannak a polcon, semmilyen szempontból nincsenek rendezve, és András nem szeretné őket átrendezni. Azért, hogy mégis jobban elkülönüljenek, kitalálta, hogy mindegyik könyv kapjon egy megfelelő színű papírkötést. Az azonos szerzőtől származó könyvek azonos színt kapjanak, de ezt a színt kaphatják még más szerzőtől származó könyvek is. De az nem fordulhat elő, hogy két egymás melletti könyv azonos színű, de nem azonos a szerzőjük. András alaposan elgondolkodott azon, hogy végül is hány különböző színű papírt kell vennie a bekötéshez, és melyikből mennyit.

Készítsünk programot i682 néven, amely a polcon sorakozó könyvek száma és a könyvek szerzői ismeretében kiszámítja, hogy legkevesebb hány színt kell használni a bekötéshez, illetve melyik színnel hány könyvet kell majd bekötni.

A program standard bemenetének első sorában a könyvek száma (\(\displaystyle 1\le N\le 500\)) szerepel. A következő sorban egy-egy szóközzel elválasztva \(\displaystyle N\) darab egész szám található: az \(\displaystyle i\)-edik szám a polcon található \(\displaystyle i\)-edik könyv \(\displaystyle s_i\) szerzőjét jelenti (\(\displaystyle {1\le s_i\le N}\)). Természetesen minden szerzőnek egyedi száma van, amely pontosan az ő könyveit jelöli.

A program a standard kimenet első sorába írja ki, hogy legalább hány színt kell használni a bekötéshez, a kimenet második sorába szóközzel elválasztva adja meg, hogy az egyes színekhez hány könyv tartozik, a kimenet harmadik sorában adja meg a könyvek egy lehetséges színezését. A program sorrendben adjon színt a könyveknek, az első könyvnek az 1-es színt, a következő eltérő színű könyvnek a 2-es színt és így tovább.

Példa:

Beküldendő egy tömörített i682.zip állományban a program forráskódja és rövid dokumentációja, amely megadja, hogy a forrásállomány melyik fejlesztői környezetben fordítható.

(10 pont)

A beküldési határidő 2026. január 15-én LEJÁRT.

A versenyzők legtöbbje – sajnos először a versenybizottság is – mohó algoritmussal oldotta meg a feladatot, vagyis sorban haladva a könyveken a könyvek közötti kapcsolatot vizsgálva az első megfelelő színt választotta egy adott könyvnek. Ez sajnos általában nem optimális, az összes lehetséges szóba jöhető színnel meg kell próbálni az adott könyvet bekötni. Így a feladat megoldása lényegesen összetettebb, mint gondoltuk.

A helyes megoldás Sümeghi Nándor budapesti versenyző munkája: i682.cpp

Amennyiben valaki szívesen foglalkozik a feladat és a saját megoldása vizsgálatával, segítségként közzéteszünk néhány bemeneti állományt és a fenti programmal kapott kimenetet: i682-be-ki.zip

Statisztika:

10 dolgozat érkezett.
10 pontot kapott:	Sümeghi Nándor .
9 pontot kapott:	Kezdődy Gréta, Krajcsovszki László, Rajtik Sándor Barnabás, Szabó Imre Bence, Tóth Marcell Domonkos.
8 pontot kapott:	1 versenyző.
Nem versenyszerű:	1 dolgozat.

A KöMaL 2025. decemberi informatika feladatai