urat

Urat

== include(page="template/taskheader" task_id="urat") ==

Poveste şi cerinţă...

Avem la dispoziţie $n$ scânduri de înălţimi $1, 2, 3, ..., n$. Vrem să construim un gard aşezând scândurile una lângă alta într-o ordine întâmplătoare. De exemplu, dacă $n = 3$, putem să construim gardul în $6$ moduri:
 
!problema/urat?x.PNG!
 
p<>. Pentru orice tip de gard se calculează diferenţele în valoare absolută dintre înălţimile oricăror două scânduri vecine din gard. Suma acestor diferenţe se numeşte _gradul de urâţenie_ al gardului. În exemplul anterior, pentru $n = 3$, se observă că gardurile au în $4$ cazuri gradul de urâţenie egal cu $3$ şi în $2$ cazuri au gradul de urâţenie egal cu $2$.
 
h2. Cerinţă
 
Cunoscând numărul $n$ de scânduri realizaţi un program care:
 
* calculează gradul maxim de urâţenie pe care îl poate avea un gard de $n$ scânduri;
* calculează restul modulo $543217$ al numărului de garduri cu grad maxim de urâţenie care se pot construi cu cele $n$ scânduri;
* determină un gard cu grad maxim de urâţenie format din $n$ scânduri, sub forma unei permutări de ordin $n$.

h2. Date de intrare

Fişierul de intrare $urat.in$ ...

Fişierul $urat.in$ conţine pe prima linie numărul natural $n$ reprezentând numărul de scânduri.

h2. Date de ieşire

În fişierul de ieşire $urat.out$ ...

Fişierul $urat.out$ va conţine trei linii:
 
* pe prima linie se va scrie un număr natural reprezentând gradul maxim de urâţenie al unui gard format din $n$ scânduri;
* pe a doua linie se va scrie un număr natural reprezentând restul modulo $543217$ al numărului de garduri cu grad maxim de urâţenie care se pot construi folosind cele $n$ scânduri;
* pe a treia linie se vor scrie $n$ numere naturale, oricare două consecutive separate prin câte un spaţiu, reprezentând, în ordine de la stânga spre dreapta, înălţimile scândurilor dintr-un gard cu grad maxim de urâţenie format cu cele $n$ scânduri.

h2. Restricţii

* $... ≤ ... ≤ ...$

* $1 < n &le; 500 000$
* Pentru prima cerinţă se acordă $20%$ din punctaj, pentru a doua $60%$ iar pentru a treia $20%$

h2. Exemplu

table(example). |_. urat.in |_. urat.out |
| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.
|
 
h3. Explicaţie
 
...

table(example). |_. urat.in |_. urat.out |_. Explicaţie |
| 3
| 3
4
1 3 2
| Gradul maxim de urâţenie este 3.
Există 4 tipuri de garduri cu grad maxim de urâţenie dintre cele 6 cazuri posibile - vezi figura.
Unul dintre gardurile de urâţenie maximă foloseşte, de la stânga la dreapta, scândurile (1, 3, 2) – vezi al doilea gard din figură.
|

== include(page="template/taskfooter" task_id="urat") ==

7744