Nagyon sok kisfiuk és lányuk van Kínában. Még egy kis fiú. És még több rizs.
Az utóbbi időben azonban egyre több síró és boldogtalan gyermek van óvodájában. Elkezdték matematikát tanulni. Különösen, eddig megtanulták számolni a nagy számokat, valamint megszorozni és osztani kettővel.
Azt gondolhatja, hogy sok a házi feladata, vagy nem szereti a matekot. Ennek azonban pont az ellenkezője igaz. Miután megszerezték ezt az új nagyhatalmat, mindennap használják. Főleg ebédnél. Mielőtt elkezdenének enni, mindenki megszámolja a rizsszemeket. 1
Amikor mindenki megszámolta a rizst, megkezdődik az ebéd második szakasza. Összehasonlítás. Ha valaki megtudja, hogy kétszer annyi szemcséje van, mint egy osztálytársának, akkor joga van előléptetni és kinevetni. Aztán sírás következik, vagy egy sérült fiú vagy lány talál valakit, akinek kétszer annyi a rizsa. A gyerekek néha kegyetlenek.
A pedagógusok tanácstalanok. Még soha nem tapasztaltak annyi sírást és kreatív káromkodást, mint amennyit az elmúlt időszakban hallottak. Természetesen a tanítási folyamat gyorsan leállt, de a gyerekeket nem lehet abból tanítani, amit már tudnak.
Ezért alternatívaként szeretnének néhány gyereknek rizst venni és tofut adni nekik. A rizst gyermekektől kell venni, hogy ne legyen két óvoda \ (x \) és \ (2x \) rizsszem. A pedagógusok rájönnek, hogy senki sem szereti a tofut 2, ezért szeretnék adni amilyen kicsi csak lehet gyermekek. Az is érdekelné őket, hogy hány gyerek veheti el a legkevesebb rizslemezt, és terjesztheti a tofut.
A feladat
\ (N \) rizs adagokat készítenek ebédre. Minden adagról megtudhat egy számot - a rizsszemek számát. Ezeket a számokat növekvő sorrendben rendezik a bemenetnél. Néhány adagot kell vennie, hogy senki ne kapjon kétszer annyi rizst, mint bárki más. Más szavakkal, nem maradhat két olyan rész, amelynek \ (x \) és \ (2x \) szemcséje van. Megpróbál a lehető legkevesebb részt eltávolítani.
Azt is megtudhatja, hogy hány adagot lehet eltávolítani a korábbi követelmények teljesítése érdekében. A két út akkor különbözik egymástól, ha van legalább egy rész, amelyet az egyik módon hagytunk, a másikban nem. Mivel ezek a módszerek nagyon sokfélék lehetnek, csak a maradékot írja be, miután elosztjuk a prímszámmal \ (1 \, 000 \, 000 \, 009 \) .
Beviteli formátum
A bemenet első sorában van egy pozitív egész szám (\ n), amely nem haladja meg az (1 \, 000 \, 000 \) értéket, jelezve a részek számát. A következő sort \ (n \) számok \ (r_i \) követik szóközökkel elválasztva, mindegyiknél \ (0). A \ (r_i \) számok a legkisebbtől a legnagyobbig vannak elrendezve.
Kimeneti formátum
Írjon két egész számot szóközzel elválasztva: a lehető legnagyobb számú rész maradjon remodulálva \ (1 \, 000 \, 000 \, 009 \), miután eltávolította a szükséges lemezeket, és azok kiválasztásának módjainak számát. A kimenetet új sor karakterrel fejezze be.
Példa
Bemenet:
Kimenet:
Nincs promóció és a lehető legkevesebb tofu, a gyerekeknek a következő részek maradnak: 1 3 4 5 5, 1 4 5 5 6, 2 2 3 5 5, 2 2 5 5 6
Ennek a szórakozásnak köszönhetően néhány órát ebédelnek is, így nem kell délután lefeküdniük
És ezt a rizst valakinek meg kell ennie
Feltöltés
A feltöltéshez be kell jelentkezned
Kérdések és vita
A forduló végén lehetősége lesz megvitatni a megoldásokat egy modellmegoldás alatt zajló vitában.