Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | color3.in, color3.out | Sursă | Lot Bistrita 2009, Baraj 1 |
| Autor | Mircea Bogdan Pasoi | Adăugată de |  Andrei-Bogdan Antonescu •andrei-alpha |
| Timp execuţie pe test | 0.6 sec | Limită de memorie | 20480 kbytes |
| Scorul tău | N/A | Dificultate | N/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:
| Test | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|---|---|---|---|---|---|---|---|---|---|---|
| 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.in | color3.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
