Az S. 137. feladat (2019. október)

S. 137. A Lamök bolygón összeírták egy elektronikus szótárba az univerzum összes szavát ABC-sorrendben. Sajnos a rendszert támadás érte, ezáltal nemcsak a szavak sorrendje, hanem az egyes szavakon belül a betűk sorrendje is összekeveredett. A bolygó lakói szeretnék minél hamarabb visszaállítani az eredeti szótárat, ezért a hibás szótár összes szavára meg akarják határozni, hogy minimum és maximum hányadik lehetett az eredeti szótárban. Sajnos ez túl nehéz feladatnak bizonyult számukra, ezért a te segítségedet kérik: készíts programot, amely megadja, hogy egy-egy szó legalább és legföljebb hányadik lehetett az eredeti szótárban.

A standard bemenet első sora tartalmazza a szótár szavainak \(\displaystyle N\) számát. Ezután \(\displaystyle N\) sor következik: a bemenet \(\displaystyle (i+1)\)-edik sora tartalmazza a hibás szótár \(\displaystyle i\)-edik szavát. A szavak csak az angol ABC kisbetűit tartalmazzák.

A standard kimenet \(\displaystyle N\) sort tartalmaz: az \(\displaystyle i\)-edik sorba írjuk ki, hogy a hibás szótár \(\displaystyle i\)-edik szava az eredeti szótárban minimum és maximum hányadik lehetett.

Korlátok: \(\displaystyle 1 \le N \le 10^5\), \(\displaystyle 1 \le \text{egy szó hossza} \le 20\). Időkorlát: 0,3 mp.

Értékelés: a pontok 50%-a kapható, ha \(\displaystyle N \le 10^4\).

Példa (a / jel sortörést helyettesít):

Beküldendő egy s137.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ő 2019. november 11-én LEJÁRT.

Statisztika:

12 dolgozat érkezett.
10 pontot kapott:	Horcsin Bálint, Németh Márton, Noszály Áron, Varga 256 Péter.
9 pontot kapott:	Gyimesi Péter, Mócsy Mátyás.
5 pontot kapott:	3 versenyző.
4 pontot kapott:	1 versenyző.
1 pontot kapott:	1 versenyző.
0 pontot kapott:	1 versenyző.

A KöMaL 2019. októberi informatika feladatai