Fişierul intrare/ieşire:poly2.in, poly2.outSursăONI 2012 - clasa a 10-a
AutorEugen NodeaAdăugată deSchumiDumitru Andrei Georgian Schumi
Timp execuţie pe test0.01 secLimită de memorie12288 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Poly2

Un polyomino este o figură geometrică plană compactă formată din una sau mai multe piese de domino, pătrate egale de latură 1. Două piese se consideră alăturate dacă au o latură comună.

Două Polyominouri se consideră identice dacă sunt formate din acelaşi număr de piese şi au aceeaşi configuraţie sau configuraţia unuia se poate obţine prin oglindirea celuilalt. În caz contrar cele două Polyominouri se consideră distincte.

Un polyomino poate fi rotit cu 90°, 180° şi 270°, în sens trigonometric. Prin rotaţie se obţin alte Polyominouri, nu neapărat identice cu cel inţial.

Niciunul dintre aceste Polyominouri nu este identic cu cel iniţial.
Un polyomino este convex dacă prin parcurgerea succesivă a linilor sau coloanelor nu se întâlnesc găuri.

Un polyomino este oblic convex (skew polyomino) dacă este convex şi prin parcurgerea succesivă a coloanelor de la stânga la dreapta acestea nu descresc în înălţime. Altfel spus, partea de jos a coloanei din stânga este întotdeauna mai mică sau egală ca înălţime cu partea de jos a coloanei din dreapta. În mod similar, partea de sus a coloanei din stânga este întotdeauna mai mică sau egală cu partea de sus a coloanei din dreapta.

Cerinţă

Să se determine numărul de Polyominouri oblice distincte care au perimetrul egal cu 2*N+2. Acest număr poate să fie mare, de aceea ne interesează rezultatul modulo 30103.

Date de intrare

Fişierul de intrare poly2.in conţine pe prima linie un număr natural N.

Date de ieşire

Fişierul de ieşire poly2.out conţine pe prima linie un număr natural ce reprezintă numărul de Polyominouri oblice care au perimetrul egal cu 2*N+2, număr afişat modulo 30103.

Restricţii

  • 2 ≤ N ≤ 500

Exemplu

poly2.inpoly2.out
3
5

Explicaţie

Sunt 5 Polyominouri care respectă cerinţa:

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content