Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | matrita.in, matrita.out | Sursă | Junior Challenge 2018 |
| Autor | Andrei Coman | Adăugată de |  Junior Challenge •JuniorChallenge2018 |
| 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
Matrita
Plictisit de inmultirea polinoamelor in timp liniar, de rezolvarea conjecturilor sau a altor banalitati precum “Traveling salesman problem”, Nry s-a decis sa porneasca in cautarea secretului fericirii eterne. Privind insa in jurul sau, a constatat cu stupoare ca olimpicii recurg la tehnici necurate in acest joc pentru satisfactie, de la sustrasul subtil al surselor sau al ideilor de probleme, pana la acte mult mai grave, precum insusirea locurilor la IOI sau a editiilor precedente de Junior Challenge. Dorind insa sa fie original (si sa pastreze in acelasi timp noua traditie), Nry a ajuns la urmatoarea concluzie: trebuie sa subtilizeze Matrita!
Odata ajuns in posesia elixirului magic, acesta l-a asezat intr-un colt al Beciului Olimpic (unul din cele mai sigure adaposturi, in care dusmanii pot patrunde doar prin tavanul de sticla). Insa, pentru a se asigura ca noua sa achizitie nu va disparea in mod neasteptat, acesta a decis sa formeze un sistem de aparare in modul urmator: el a privit Beciul ca o matrice patratica de latura N + 1 (liniile si coloanele sunt numerotate de la 0 la N), Matrita aflandu-se in patratul aflat pe linia 0 si coloana 0. El doreste sa plaseze mai multe capcane in patrate cu indicii liniilor si ai coloanelor cuprinsi intre 1 si N, astfel incat dreapta care uneste oricare doua capcane sa nu contina Matrita.
Nry va roaga sa raspundeti la urmatoarea intrebare: stiind numarul N, in cate moduri isi poate construi el sistemul de aparare al Matritei?
Date de intrare
Fişierul de intrare matrita.in ...
Date de ieşire
În fişierul de ieşire matrita.out ...
Restricţii
- 1 ≤ N ≤ 10.000.000
- Pentru teste in valoare 5 puncte N ≤ 10
- Pentru alte teste in valoare de 25 de puncte N ≤ 50.000
- Pentru alte teste in valoare de 30 de puncte N ≤ 750.000
- Pentru alte teste in valoare de 30 de puncte N ≤ 5.000.000
- Pentru alte teste in valoare de 10 puncte N ≤ 10.000.000
- Legenda spune ca oricine gusta din Matrita are un loc asigurat la IOI 2020
Exemplu
| matrita.in | matrita.out |
|---|---|
| This is some text written on multiple lines. | This is another text written on multiple lines. |
Explicaţie
...
