Problem diamant


O firmă produce un tip nou de diamante de formă dreptunghiulară şi de calităţi diferite. Pentru a calcula calitatea unui diamant firma împarte diamantul în N*M pătrăţele formând o matrice cu N linii numerotate de la 1 la N şi M coloane numerotate de la 1 la M. Pătrăţelul de pe linia i şi coloana j poate influenţa calitatea diamantului în felul următor (1≤i≤N, 1≤j≤M):

  • dacă pătrăţelul conţine impurităţi este marcat cu -1 şi va diminua calitatea diamantului cu i*j
  • dacă pătrăţelul este simplu este marcat cu 0 şi nu schimbă calitatea diamantului
  • dacă pătrăţelul conţine aur este marcat cu +1 şi va mări calitatea diamantului cu i*j.

Fiecare pătrăţel va fi marcat cu unul dintre cele trei numere (-1, 0, +1).

Un client bogat vrea să cumpere cât mai multe diamante diferite, de aceeaşi calitate X. Două diamante sunt diferite dacă există cel puţin un pătrăţel de pe o line i şi coloană j marcat diferit în cele două diamante.

Cerinţă

Ajutaţi firma să poată răspunde la astfel de cereri scriind un program care pentru un anumit X găseşte numărul de diamante diferite de calitate X.

Date de intrare

Pe prima linie a fişierului de intrare diamant.in sunt scrise trei numere întregi N M X separate prin câte un spaţiu reprezentând numărul de linii, numărul de coloane ale unui diamant, şi respectiv calitatea cerută.

Date de ieşire

Pe prima linie din fişierul de ieşire diamant.out se va afla numărul de diamante diferite cu calitatea cerută, modulo 10000.

Restricţii

  • 0 < N < 21
  • 0 < M < 21
  • \(-2^{31} < X < 2^{31}\)

Exemplu

diamant.in

2 2 7

diamant.out

3

Explicaţii

Matricile corespunzătoare celor 3 diamante sunt:

-1 +1     +1  0      +1 +1
+1 +1     +1 +1       0 +1

General info

ID: 86

Upload: liviu

Input: diamant.in/diamant.out

Memory limit: 16MB/1MB

Time limit: 0.18s

Author: Dan Ionut Fechete

Source: ONI 2006 XI-XII: Ziua 1, Problema 2

Submissions

Special Submissions