Fişierul intrare/ieşire:permbit.in, permbit.outSursăAlgoritmiada 2018 Runda PreONI
AutorEugenie Daniel PosdarascuAdăugată deandreiiiiPopa Andrei andreiiii
Timp execuţie pe test0.5 secLimită de memorie262144 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Permbit

Se dau N şiruri a câte M elemente binare, al i-lea şir fiind notat Si. Fie mulţimea permutărilor P care au proprietatea că, aplicate oricarui şir din cele date, se obţine urmatorul şir. Mai exact, permutarea P este validă dacă:
S_i_j = S_{(i+1)}_{P[j]}, \hspace{5} \forall \hspace{3} 1 \leq i < n, 1 \leq j \leq m
Se cere să se afişeze:
a) O permutare P oarecare validă
b) Permutarea mediană P (sortând lexicografic toate permutările corecte, se consideră cea care se află la mijloc, în caz că sunt două permutări la mijloc, se considera cea mai mică lexicografic)
c) Numarul de permutări P valide modulo 109 + 7.
Se garantează că există cel puţin o permutare care respectă proprietatea de mai sus.

Date de intrare

Fişierul de intrare permbit.in conţine pe prima linie numărul C, reprezentând cerinţa pe testul respectiv: 1 pentru cerinţa a), 2 pentru cerinţa b) şi 3 pentru cerinţa c).
Pe următoarea linie se află numerele N şi M, iar pe următoarele N linii câte un şir de M biţi.

Date de ieşire

În fişierul de ieşire permbit.out se afla, daca C = 3, numărul de permutări corecte modulo 1.000.000.007, iar dacă nu, o permutare, după caz, oarecare sau mediană.

Restricţii

  • 2 ≤ N, M, N * M ≤ 106
  • 10 puncte: N, M ≤ 8, 1 ≤ C ≤ 3
  • 10 puncte: N, M ≤ 300, C = 1
  • 10 puncte: N, M ≤ 300, C = 2
  • 10 puncte: N, M ≤ 300, C = 3
  • 30 puncte: N * M ≤ 106, C = 2
  • 10 de puncte: N * M ≤ 106, C = 1
  • 20 de puncte: N * M ≤ 106, C = 3

Exemplu

permbit.inpermbit.out
1
3 8
10111010
11000111
01111100
2 5 8 7 1 4 6 3
2
3 10
0000011010
0001100001
1010000100
6 9 7 8 3 10 5 2 4 1
3
3 6
001100
000011
100100
8
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?