 |
Az I/S. 54. feladat (2021. május) |
I/S. 54. \(\displaystyle N\) darab gyöngyöt fűztek körbe nyakláncnak. Minden gyöngyszem vagy piros vagy kék. Egy lépésben kiválaszthatunk három szomszédos gyöngyöt és mindegyik színét az ellenkezőjére válthatjuk. Adjuk meg, hogy megoldható-e az, hogy az összes gyöngy ugyanolyan színű legyen.
Bemenet: az első sor tartalmazza az \(\displaystyle N\) számot. A következő sor tartalmaz \(\displaystyle N\) betűt, ami az egyes gyöngyszemeket írja le: P betű jelöl egy piros, K egy kék gyöngyöt. A szemeket körbe fűzték, tehát az első és utolsó gyöngyszemek szomszédok.
Kimenet: egyetlen sorba írjunk ki 1-et, ha lehetséges, -1-et ha nem lehetséges hogy minden gyöngyszem ugyanolyan színű legyen.
| Bemenet | Kimenet |
| 5 / PKPPK | 1 |
Egy lehetséges lépéssorozat: PKPPK – KPPPP – PKKPP – KKKKK.
Korlátok: \(\displaystyle 2\le N\le {10}^{5}\). Időkorlát: 0,3 mp.
Értékelés: a pontok 30%-a kapható, ha \(\displaystyle N\le 10\).
Beküldendő egy is54.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ő 2021. június 15-én LEJÁRT.
1. megoldás:
Hogyha N nem osztható 3-mal, akkor mindig van megoldás.
Hogyha N osztható 3-mal, akkor számozzuk meg a gyöngyöket egy irány mentén 1-től N-ig, és 3-as maradék alapjább osszuk őket 3 csoporta. Pontosan akkor van megoldás, ha minden csoportban ugyan annyi a kék gyöngyök paritása.
Részletes bizonyítások Tóth Bálint megoldásában:
2. megoldás:
Döntsük el hogy 1-es és 2-es gyöngyöktől kezdődő gyöngyhármasokat megcseréljük-e, innen egyértelmű a kitöltés ha kikötjük milyen színű nyakláncot szeretnénk.
Részletes leírás Horcsin Bálint megoldásában:
Statisztika:
8 dolgozat érkezett. 10 pontot kapott: Horcsin Bálint, Kovács Alex, Melján Dávid Gergő, Nagy 292 Korina, Sándor Péter, Tóth 057 Bálint. 8 pontot kapott: 1 versenyző. 4 pontot kapott: 1 versenyző.
A KöMaL 2021. májusi informatika feladatai