A NAGY FAL parkolóban N egymás mögötti parkolóhelyen N, nem feltétlenül különbözö típusú autó parkol. A típusokat 1 és M közötti egész számokkal adjuk meg. W számú munkás típusszám szerint rendezi növekvö sorrendbe az autókat az alábbi elven: Egy ún. körben minden munkás (egyszerre) kivihet egy autót a parkolóból, amit az így keletkezett legfeljebb W üres hely valamelyikére visz vissza. Lehetséges, hogy egyes körökben nem minden munkás mozgat autót. A cél a rendezettség elérése minél kevesebb körben.Írj programot, amely adott autósorrendre megad egy rendezést maximum [N/(W-1)] (azaz N/(W-1) felfelé kerekítve) lépésben. A minimálisan szükséges körök száma biz-tosan nem nagyobb ennél az értéknél.
Például legyen 10 autónk, melyek típusa 1, 2, 3 vagy 4 lehet, és legyen 4 munkásunk. Az autók eredeti sorrendje:
2 3 3 4 4 2 1 1 3 1.A minimálisan szükséges körök száma 3, az autók sorrendje az egyes körök után például a következö lehet:2 1 1 4 4 2 3 3 3 1 – az 1. kör után,Bemenet:
2 1 1 2 4 3 3 3 4 1 – a 2. kör után, és
1 1 1 2 2 3 3 3 4 4 – a 3. kör után.A CAR.IN állomány elsö sorában három egész szám van egy-egy szóközzel elválasztva: az autók száma (2 <= N <= 20000), az autótípusok száma (2 <= M <= 50) és a munkások száma (2 <= W <= M). Minden típushoz legalább 1 autó tartozik. A második sorban N egész szám van egy-egy szóközzel elválasztva: az i-edik szám az i-edik helyen álló autó típusa.Kimenet:A CAR.OUT állomány elsö sorába azt kell írni, hogy a megoldásod hány körböl (R) áll. A következö R sor az egyes köröket írja le a végrehajtásuk sorrendjében. Minden sorban az elsö egész szám (C) a mozgatandó autók száma, amelyet C számpár követ. Két egymás utáni egész szám azt írja le, hogy az autót honnan (a pár elsö tagja) hova (a pár második tagja) kell mozgatni. Több, ugyancsak R körböl álló megoldás is lehet, de közülük csak egyet kell megadni.Példa:
CAR.IN CAR.OUT 10 4 4
2 3 3 4 4 2 1 1 3 13
4 2 7 3 8 7 2 8 3
3 4 9 9 6 6 4
3 1 5 5 10 10 1Részpontszámok:
Legyen Q=[N/(W-1)] . Ha a programod által megadott R kör leírása hibás vagy a program nem jól rendez, akkor a pontszámod 0 lesz. Jó megoldás esetén a pontszámod így számolják ki a maximális pontszámból:R <= Q 100%
R = Q+1 50%
R = Q+2 20%
R >= Q+3 0%
A palindrom egy szimmetrikus karaktersorozat, azaz balról jobbra és jobbról balra olvasva azonos. Írj programot, amely egy adott karaktersorozathoz megadja a minimálisan beszúrandó karakterek számát, úgy hogy az eredmény palindrom legyen!Például 2 karakter beszúrásával az “Ab3bd” karaktersorozat palindrommá alakítható (“dAb3bAd” vagy “Adb3bdA” is lehet belöle). Kettőnél kevesebb karakter beszúrásával azonban ebből a karaktersorozatból nem állítható elő palindrom.
Bemenet:
A PALIN.IN állomány elsö sorában a bemenő karaktersorozat hossza, N (3 < = N < = 5000), a második sorban egy N hosszúságú karaktersorozat (string) van. A karaktersorozat az angol ábécé kis- és nagybetűiből, valamint számjegyekből állhat. A kis- és a nagybetűket megkülönböztetjük.Kimenet:A PALIN.OUT állomány egyetlen sorába egyetlen egész számot ( > = 0), a keresett minimális értéket kell írni.Példa:
palin.in palin.out 5
Ab3bd2
Egy űrkísérletben N tárgyat használunk, melyeket 1-töl N-ig számozunk, ahol N páratlan. Minden tárgy különböző súlyú (természetes számok), de magukat a súlyokat nem ismerjük. Minden Y súlyra igaz, hogy 1 < = Y < = N. Mediánnak nevezzük azt a tárgyat, amelyiknél ugyanannyi könnyebb, mint nehezebb tárgy van. Írj programot, amely meghatározza a mediánt! A tárgyak súlyát olyan eszközzel hasonlíthatjuk össze, amely három tárgy közül megadja a mediánt.Könyvtár:
A device nevű könyvtárból az alábbi három művelet használható:Pascal programozóknak:A device könyvtár függvényei két szöveges állományt hoznak létre MEDIAN.OUT és MEDIAN.LOG néven. A MEDIAN.OUT elsö sorában egy egész szám lesz, az, amit az Answer eljárásnak adtál át. A második sorban a Med3 hívások száma lesz. A programod és a könyvtár közötti párbeszédet a MEDIAN.LOG tartalmazza.
- GetN, egyszer kell meghívni, a programod legelején; az argumentum nélküli függvényhívás eredménye az N értéke.
- Med3, három különböző tárgy sorszámával kell hívni, függvényértéke e három sorszám közül a mediánjuk sorszáma.
- Answer, egyszer kell meghívni, a programod végén; argumentumként az N tárgy mediánjának a sorszámát kell megadnod. Ez a hívás le is állítja a programodat.
programodba írd be a következő sort:Kipróbálás:uses device;Programod kipróbálásához készíts DEVICE.IN néven olyan állományt, amely két sorból áll. Az elsőbe a tárgyak számát (N) kell írni. A második sor a tárgyak súlyát (1 és N közötti különböző egész számok) tartalmazza, ahol az i-edik érték az i-edik tárgy súlya.Könyvtár:A device nevü könyvtárból az alábbi három művelet használható:Példa:
DEVICE.IN 5
2 5 4 3 1Ez az állomány a következő esetet írja leKikötések:Ebben az esetben a helyes hívási sorrend:
Sorszám 1 2 3 4 5 Súly 2 5 4 3 1 1. GetN értéke 5.
2. Med3(1,2,3) értéke 3.
3. Med3(3,4,1) értéke 4.
4. Med3(4,2,5) értéke 4.
5. Answer(4)
- 5 < = N < = 1499 és N páratlan.
- Minden i sorszámra igaz: 1 < = i < = N.
- Minden Y súlyra igaz: 1 < = Y < = N és minden súly különböző.
- A Pascal könyvtár neve: device.tpu
- A Pascal függvények és eljárás deklarációja:
- function GetN: integer;
- function Med3(x,y,z:integer):integer;
- procedure Answer(m:integer);
- Futtatásonként a Med3 legfeljebb 7777-szer hívható.
- Programod nem olvashat és nem írhat egyetlen állományt sem.