diamant

Time limit: 0.18s
Memory limit: 16MB
Input: diamant.in
Output: diamant.out

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 linie 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 și precizări

  • 0 < N < 21
  • 0 < M < 21
  • 231<X<231-2^{31} < X < 2^{31}

Exemplu

diamant.in

2 2 7

diamant.out

3

Explicaţie

Matricile corespunzătoare celor 3 diamante sunt:

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

Problem info

ID: 86

Editor: liviu

Author:

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

Tags:

ONI 2006 XI-XII

Log in or sign up to be able to send submissions!