Színek kiválasztása#245
Miss M nemcsak szeret érdekes történeteket kitalálni programozási problémákhoz, hanem imád festeni is, különösen a harmonikus színkombinációkat, mint például a színtárcsán található kiegészítő színeket. Azonban ezúttal másképp döntött a festményéhez való színek kiválasztásában.
Miss M színtárcsát vett elő, mindegyiken különböző árnyalatokkal, amelyek (a_i+1) színből állnak, és már kiválasztott egy kezdőszínt minden tárcsán, megjelölve azt használtként. Ezután a következő algoritmust használva választja ki minden további színt:
Keressük meg a leghosszabb sorozatot a megjelöletlen színek között az összes színtárcsán; ha több is van, válasszunk bármelyiket.
Ha a sorozat hossza páratlan, vegyük a pontosan középső színt és jelöljük meg használtként.
Ha a sorozat hossza páros, vegyük az egyik középső színt és jelöljük meg használtként.
Miss M további színt szeretne választani, és azt is szeretné tudni, hogy mi lesz a megjelöletlen színek sorozatának maximális hossza, mielőtt kiválasztja a (m+n)-edik színt.
Az első sor két egész számot tartalmaz és (1 \leq n \leq 100, 1 \leq m \leq 10^{18}) — a színtárcsák száma és a színek száma, amelyeket Miss M továbbiakban szeretne kiválasztani (azaz nem számítva az egyes tárcsákon az első megjelölt színeket).
A második sor egész számot tartalmaz a_1, a_2, \dots, a_n (1 \leq a_i \leq 10^{18}).
Garantált, hogy nem több, mint az összes a_i összege.
Írjunk ki egyetlen egész számot — a megjelöletlen színek sorozatának maximális hosszát, mielőtt Miss M kiválasztja az (m+n)-edik színt.
Példa
1. példa
2. példa
3. példa
4. példa
Magyarázat a második példához: Egy színtárcsát adtak meg, amelyen szín található. Miss M már kiválasztott egy színt a tárcsáról (a képen az -es számmal jelölve). Most további színt szeretne választani. Így a tevékenységek sorozata a következő:
A megjelöletlen színek sorozatának maximális hossza . Ezért kiválasztjuk a középső színt és jelöljük meg a -es számmal.
Most és megjelöletlen színből álló sorozatok vannak; választunk bármelyiket és a sorozat közepén kiválasztunk egy színt és jelöljük meg a -as számmal.
A sorozatok közül — , , és — választjuk az -öt — ez a megjelöletlen színek sorozatának maximális hossza, mielőtt Miss M kiválasztja a -edik színt.
A problémaállítás harmadik példájának színtárcsája.
Ha a megoldás helyesen működik n=1 és a_1 \leq 100 esetén, legalább pontot ér.
Ha a megoldás helyesen működik n=1 és a_1 \leq 10^6 esetén, legalább pontot ér.
Ha a megoldás helyesen működik n=1 esetén, legalább pontot ér.