Programozó versenyek

ACM ICPC Central European Regional Contest, Prague, 2007, 2011, Practice Session

2011. november 29. 18:45 – 2012. február 1. 0:00

Menetelő hangyák

Hangyák! Hát nem elbűvölőek? E kis rovarok ezrei masíroznak fel és alá. Jól szervezett hangyavárakat tudnak építeni. Néha azonban egy kicsit bután cselekszenek.

Képzeljük el, hogy van egy hosszú fadarab, aminek a tetején hangyák sétálgatnak! A viselkedési mintájuk nagyon egyszerű: Mindegyikük lassan araszol előre, másodpercenként 1 cm-es állandó sebességgel. Ha egy hangya találkozik egy másikkal, összeérintik az „antennáikat”, majd mindketten azonnal megfordulnak, és elindulnak az ellenkező irányba. Ha egy hangya eléri a fadarab végét, akkor leesik, és többé nincs hatással a többi hangyára.

Az ábrán mozgásban lévő hangyákra láthatunk példát a 0. másodpercben. Az 1. másodpercben az E és az A jelű hangyák találkoznak a 2-es pozícióban, és megfordulnak. Az A jelű hangya 1,5 másodperccel később találkozik a B jelűvel. Ugyanebben a pillanatban (2,5 másodperccel az indulás után) a C és D jelű hangyák is találkoznak. Mind a négyen megfordulnak. 0,5 másodperccel később (a 3. másodpercben) az E jelű hangya leesik a bal oldalon. És így tovább…

A feladatod, hogy szimuláld a hangyák mozgását. Az egyszerűség kedvéért tegyük fel, hogy a hangyák mérete 0 (még ha az ábra alapján ez nem is így tűnik).

A bemenet specifikációja

A bemenet számos tesztesetet tartalmaz. Minden teszteset egy olyan sorral kezdődik, amelyben két egész szám (L és A) szerepel egy szóközzel elválasztva. L a fadarab hossza cm-ben (1 ≤ L ≤ 999 999), A pedig a szimuláció kezdetén a fadarabon lévő hangyák száma (1 ≤ AL+1).

Ezután A sor következik, amelyek mindegyike egy pozitív egész számból (Xi), egy szóközből és egy angol nagybetűből áll. A szám (0 ≤ XiL) az i-edik hangya pozícióját adja meg, a betű pedig a kezdeti irányát: „L”, ha balra néz (a 0 felé), „R”, ha jobbra. Minden hangya különböző pozícióból indul.

A bemenetet egy olyan sor zárja, amelyben két nulla szerepel L és A helyén.

A kimenet specifikációja

Minden tesztesetre egyetlen sort kell a kimenetre írni, amely a „The last ant will fall down in T seconds.” szöveget tartalmazza, ahol T az a pontos idő, amikor az utolsó (vagy utolsó két) hangya eléri a fadarab végét. Ha lehetséges, az időt egész számként kell megadni, ha nem, akkor pontosan egy tizedesjegy kövesse a tizedespontot.

Példa bemenet

  1. 900000 1
  2. 0 R
  3. 10 1
  4. 0 L
  5. 14 5
  6. 3 L
  7. 6 L
  8. 13 L
  9. 8 R
  10. 1 R
  11. 0 0
letöltés szöveges állományként

A példa bemenethez tartozó kimenet

  1. The last ant will fall down in 900000 seconds.
  2. The last ant will fall down in 0 seconds.
  3. The last ant will fall down in 13 seconds.
letöltés szöveges állományként

(Az utolsó példa teszteset megfelel az ábrának.)

Debreceni Egyetem, Informatikai Kar, v. 2019.03.01.