Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | bazar.in, bazar.out | Sursă | Algoritmiada 2019 Runda PreONI |
| Autor | Alexandru Petrescu | Adăugată de |  Alexandru Petrescu •alexpetrescu |
| Timp execuţie pe test | 0.5 sec | Limită de memorie | 524288 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Bazar
In timp ce se plimba prin bazarul din Istanbul, Marcel a dat peste urmatoarea problema la departamentul care se ocupa cu schimbul de vaci.
Cerinta
Se considera un camp de iarba, un sistem de coordonate xOy si doi tauri, Ollu si Bollu, care sunt legati printr-un fir extensibil si ascutit. Ei sunt initial localizati in punctul (0, 0). Ambii se pot deplasa cu aceeasi viteza doar in Nord si Est. Atunci cand se plimba, firul care ii leaga taie iarba pe care o intampina. Ei se deplaseaza in asa fel incat sa taie cat mai multa iarba folosind firul.
Exista si N puncte unde poti pune cate o zambila. Taurii isi vor stabili traseul astfel incat sa viziteze toate zambilele puse de tine. Pentru a nu crea confuzie, trebuie sa alegi punctele unde pui zambilele astfel incat toate sa fie vizitabile, avand in vedere restrictia de mers doar in Nord si Est a taurilor. Am uitat sa precizez: Ollu si Bollu sunt cei mai destepti tauri, ei isi dau seama rapid cand incerci sa ii pacalesti. Din acest motiv, nu poti pune mai putine zambile decat numarul de maxim de zambile pe care le-ai putea pune in cea mai favorabila alegere a punctelor - altfel i-ai irita foarte tare pe Ollu si Bollu.
Pentru toate modurile corecte in care ai putea alege setul de puncte unde sa pui zambile din cele N, Bisisica (un fel de Miorita, doar ca mai incapatanata) calculeaza cantitatea de iarba pe care o vor taia taurii. La final, ea aduna toate aceste numere iar pe suma o denumeste cu numele sau. Care este restul la impartirea cu 109 + 7 a numarului ei?
Date de intrare
Fişierul de intrare bazar.in contine pe prima linie numarul N de puncte. Pe urmatoarele N linii se afla cate doua numere naturale, descriind coordonatele punctelor unde se poate afla cate o zambila.
Date de ieşire
În fişierul de ieşire bazar.out se afla restul impartirii numarului Bisisica la 109 + 7.
Restricţii
- 1 ≤ N ≤ 1.000.000
- Pentru ~5% din punctaj, N ≤ 7
- Pentru ~10% din punctaj, N ≤ 16
- Pentru ~20% din punctaj, N ≤ 1.000
- Pentru ~65% din punctaj, N ≤ 50.000
- Pentru ~80% din punctaj, N ≤ 200.000
Exemplu
| bazar.in | bazar.out |
|---|---|
| This is some text written on multiple lines. | This is another text written on multiple lines. |
Explicaţie
...
