Fişierul intrare/ieşire:urat.in, urat.outSursăONI 2012 - clasele 11-12
AutorAdrian PanaeteAdăugată deSpiderManSimoiu Robert SpiderMan
Timp execuţie pe test0.5 secLimită de memorie67583 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Urat

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:

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.

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.

Date de intrare

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

Date de ieşire

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.

Restricţii

  • 1 < n ≤ 500 000
  • Pentru prima cerinţă se acordă 20% din punctaj, pentru a doua 60% iar pentru a treia 20%

Exemplu

urat.inurat.outExplicaţ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ă.
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content