Atenţie! Aceasta este o versiune veche a paginii, scrisă la 2009-09-26 06:44:28.
Revizia anterioară   Revizia următoare  

 

Fişierul intrare/ieşire:color3.in, color3.outSursăLot Bistrita 2009, Baraj 1
AutorMircea Bogdan PasoiAdăugată deandrei-alphaAndrei-Bogdan Antonescu andrei-alpha
Timp execuţie pe test0.6 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Color3

Zăhărel are un set de N becuri colorate cu K culori (pentru uşurinţă vom considera culorile numerotate de la 1 la K). Fiecare bec este special, în sensul că are un comutator care îi schimbă culoarea C curentă astfel:

  • dacă C = K, culoarea devine 1
  • dacă C < K, culoarea devine C+1

Zăhărel doreşte să comute anumite becuri astfel încât toate să aibă aceeaşi culoare C. Totusi, sarcina lui nu este atât de simplă, deoarece nu poate comuta becurile direct, ci trebuie să folosească o telecomandă cu M butoane. Apăsarea unui buton afectează fiecare bec, mai exact, pentru fiecare buton i se dau N valori Ai,1 Ai,2...Ai,N cu semnificaţia că becul j este comutat de Ai,j ori când se apasă butonul i.

Cerinta

Scrieţi un program care determină în câte moduri poate folosi Zăhărel cele M butoane astfel încât toate becurile să aibă culoarea C.

Date de intrare

Fişierul de intrare color.in conţine pe prima linie numerele naturale N M K C separate prin spaţii. Următoarea linie va conţine N numere naturale separate prin spaţii reprezentând culorile iniţiale ale becurilor, în ordine de la 1 la N. Următoarele M linii vor conţine câte N numere naturale Ai,1 Ai,2...Ai,N separate prin spaţii, descriind butonul i.

La corectare se vor folosi 10 teste. Ele vor avea următoarele valori pentru N, M si K:

Test12345678910
N
M
K
13
20
47
64
64
9973
100
99
30011
150
101
666019
200
199
15485863
128
169
9699690
99
125
602329
150
150
28447459
200
175
149662546
200
200
160213270

Date de ieşire

În fişierul de ieşire color.out se va scrie pe prima linie numărul de moduri de a folosi telecomanda, astfel încât toate becurile să aibă culoarea C. Rezultatul se va afişa modulo 666013.

Restricţii si precizari

  • 1 ≤ C ≤ K
  • 0 ≤ Ai,j ≤ 109
  • Un buton de pe telecomandă poate fi apăsat de un număr de ori mai mic decât K

Exemplu

color3.incolor3.out
4 6 2 1
1 2 1 2
1 0 1 0
0 1 0 1
1 0 0 0
0 1 0 0
0 0 1 0
0 0 0 1
4

Explicaţie

Cele 4 posibilităţi sunt:
1) butonul 2
2) butoanele 4, 6
3) butoanele 1, 2, 3, 5
4) butoanele 1, 3, 4, 5, 6

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?