Az I/S. 40. feladat (2019. december)

I/S. 40. Egy nap \(\displaystyle N\) matematikus moziba megy. A moziban \(\displaystyle M\) darab szék van egy sorban (1-től \(\displaystyle M\)-ig megszámozva). Mindannyian egy sorban ülnek le. Mindenki megmondja, hogy minimum melyik sorszámú székre és maximum melyik sorszámú székre hajlandó leülni. Nincs olyan szék, ahova ketten is leülhetnének. Azért, hogy kényelmesen elférjenek, megpróbálnak a lehető legtávolabb leülni egymástól. Még pontosabban: arra törekednek, hogy a két egymáshoz legközelebb ülő matematikus távolsága (a székek számának különbsége) a lehető legnagyobb legyen. Adjuk meg, hogy mekkora ez a legnagyobb távolság.

Bemenet: az első sor tartalmazza \(\displaystyle N\) és \(\displaystyle M\) értékét. A következő \(\displaystyle N\) sor mindegyike egy \(\displaystyle a_{i}, b_{i}\) számpárt tartalmaz, ami azt jelenti, hogy az \(\displaystyle i\)-edik matematikus olyan székre szeretne leülni, amelynek száma legalább \(\displaystyle a_{i}\) és legfeljebb \(\displaystyle b_{i}\). Kimenet: a program adjon meg egyetlen számot, két legközelebbi matematikus maximális távolságát.

Példa:

Korlátok: \(\displaystyle 3\le N\le {10}^{5}\), \(\displaystyle 0\le M\le {10}^{9}\). Időkorlát: 0,3 mp.

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

Beküldendő egy is40.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ő 2020. január 10-én LEJÁRT.

Statisztika:

6 dolgozat érkezett.
10 pontot kapott:	Horcsin Bálint, Mócsy Mátyás, Noszály Áron, Szente Péter.
7 pontot kapott:	1 versenyző.
6 pontot kapott:	1 versenyző.

A KöMaL 2019. decemberi informatika feladatai