Fişierul intrare/ieşire:12perm.in, 12perm.outSursăpreONI 2006 Runda 2
AutorTiberiu-Lucian FloreaAdăugată de
Timp execuţie pe test0.1 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise | Statistici

12-Perm

Se defineste 12-permutarea A1,A2,...,AN ca fiind o permutare a numerelor 1,2,...,N astfel incat |Ai - Ai+1|<3 pentru i=1,2,...,N-1.

Cerinta

Dandu-se un numar natural N calculati numarul de 12-permutari de lungime N.

Date de Intrare

Prima linie a fisierului de intrare 12perm.in contine numarul natural N cu semnificatia de mai sus.

Date de Iesire

In fisierul 12perm.out veti afisa X numarul de 12-permutari de lungime N modulo 1048576.

Restrictii si precizari

  • 1 ≤ N ≤ 15.000.000
  • 1048576 = 220
  • Pentru 70% din teste N ≤ 5.500.000.

Exemplu

12perm.in12perm.out
412

Explicatii

Cele 12 12-permutari sunt: 1 2 3 4, 1 2 4 3, 1 3 2 4, 1 3 4 2, 2 1 3 4, 2 4 3 1, 3 1 2 4, 3 4 2 1, 4 2 1 3, 4 2 3 1, 4 3 1 2, 4 3 2 1

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content