Középiskolai Matematikai és Fizikai Lapok
Informatika rovattal
Kiadja a MATFUND Alapítvány
Már regisztráltál?
Új vendég vagy?

Az I. 574. feladat (2022. november)

I. 574. Egy hosszú polcon dobozok helyezkednek el sorban egymás mellett, melyeket pozitív egész számok azonosítanak. Egy robot képes arra, hogy a polcról levegyen egy dobozt, képes arra, hogy magánál tartson egy dobozt, és képes arra, hogy a polcon egy üres helyre elhelyezze a magánál tartott dobozt. Ezenkívül a robot a polc elejétől a végéig tud mozogni előre és vissza, akár úgy is, hogy dobozt hoz magával, valamint képes arra, hogy mozgás közben egy polcon lévő dobozt egy szomszédos üres helyre toljon át. A robot rendező algoritmusa a következők szerint vezérli a robotot:

    1. Elindul a polc elejétől, és ha van olyan doboz, amely nagyobb azonosító számmal rendelkezik, mint az utána következő doboz, akkor azt leveszi a polcról.

    2. Mozog tovább a polc vége felé, miközben tartja a kivett dobozt, és minden olyan dobozt a polc eleje felé tol a szomszédos üres helyre, amely kisebb azonosító számú, mint az a doboz, amit a kezében tart.

    3. Ha talál olyan dobozt, amely nagyobb azonosító számú, mint a kezében tartott doboz, akkor azt már nem tolja a polc eleje felé, hanem az azt megelőző üres helyre leteszi a magánál tartott dobozt. Ezután visszatér a polc elejére, ahol az 1. pont szerint kezdi ismét a működését.

    4. Ha a polc elejétől indulva nem talál olyan dobozt, amely nagyobb azonosító számmal rendelkezne, mint a következő doboz, akkor abbahagyja a rendezést, mivel a dobozok az azonosító számok szerint növekvő sorrendben vannak.

Készítsünk programot, amely adott dobozok esetén megadja, hogy a robotnak hányszor kell levennie dobozt a polcról, illetve hányszor kell egy hellyel odébb tolnia dobozt!

A program a standard bemenet első sorából olvassa be a dobozok \(\displaystyle N\) számát (\(\displaystyle 2\le N\le 20\)), majd a második sorából a dobozok azonosító számát, \(\displaystyle N\) darab különböző pozitív egészet. A program a standard kimenet egyetlen sorába írja ki, hogy hányszor kellett a robotnak a rendezés során levennie egy dobozt, illetve hányszor kellett egy szomszédos helyre odébb tolnia egy dobozt.

Példák:

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

(10 pont)

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


Mintamegoldásként Szabó Imre Bence budapesti diák C++ nyelven készült munkáját (i574.cpp), Kövesi Alíz tatai tanuló Python nyelven készült megoldását (i574.py) és Horváth Milán pécsi versenyző C# nyelvű programját (i574.cs) adjuk közre.


Statisztika:

9 dolgozat érkezett.
10 pontot kapott:Bátorfi Balázs, Gyönki Dominik, Hinek Milán, Horváth Milán, Kövesi Alíz, Nagy 292 Korina, Szabó Imre Bence, Vadász Levente Márton, Zádor-Nagy Zsombor.

A KöMaL 2022. novemberi informatika feladatai