Fişierul intrare/ieşire:teroristi.in, teroristi.outSursăONI 2010 - Baraj
AutorAndrei Grigorean, Cosmin Silvestru NegruseriAdăugată deandrei-alphaAndrei-Bogdan Antonescu andrei-alpha
Timp execuţie pe test1.1 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Teroristi

Inspiraţi de faimoasa grupare Al-Qaeda, teroriştii din oraşul Tomis s-au hotărât să saboteze Olimpiada Naţională de Informatică. Pentru a-şi pune planul în aplicare ei au răpit-o pe Miruna şi au trimis o scrisoare concurenţilor în care cer o răscumpărare foarte mare. Ca măsură de siguranţă, scrisoarea nu a fost scrisă de mână, ci a fost compusă lipind pe o foaie litere decupate dintr-un ziar. Detectivul Mirunel are un plan pentru a determina identitatea teroriştilor. Primul lucru pe care vrea să îl facă Mirunel este să demonstreze că teroriştii citesc Dilema veche. Detectivul are ultimul număr al revistei şi vrea să ştie dacă scrisoarea teroriştilor putea fi scrisă decupând litere doar din această ediţie. Din păcate sarcina este prea grea pentru Mirunel, deoarece atunci când decupează o bucată dintr-un ziar, aceasta va conţine 2 litere, câte una pe fiecare faţă. Fiecare bucată de ziar poate fi utilizată în două moduri, în funcţie de litera care va fi folosită la reconstituirea scrisorii trimise, iar acest lucru l-a încurcat de tot pe Mirunel.

Cerinta

Scrieţi un program care să determine o modalitate validă de reconstituire a scrisorii trimise de terorişti, folosind doar bucăţile de ziar decupate de Mirunel.

Date de intrare

Fişierul de intrare teroristi.in conţine pe prima linie două numere naturale N şi M, reprezentând lungimea scrisorii trimise de terorişti, respectiv numărul de bucăţi de ziar decupate. Pe a doua linie se află mesajul scrisorii sub forma unui şir de N litere mici aparţinând alfabetului englez. Fiecare din următoarele M linii conţine exact 2 caractere din alfabetul englez separate prin spaţiu, reprezentând literele înscrise pe cele două feţe ale unei bucăţi de ziar.

Date de ieşire

Fişierul de ieşire teroristi.out va conţine o singură linie pe care se va găsi un şir de N numere distincte din mulţimea {1, 2, ... M}. Pe poziţia i din şirul afişat se va afla indicele bucăţii de ziar (în ordinea în care acestea apar în fişierul de intrare) folosite pentru a reprezenta cea de a i-a literă din scrisoare.

Restricţii

  • 1 ≤ N ≤ 1 000 000
  • 1 ≤ M ≤ 1 000 000
  • Pentru 10% din teste N, M = 3
  • Pentru alte 10% din teste N, M ≤ 15
  • Pentru alte 30% din teste N, M ≤ 1000
  • Dacă există mai multe soluţii, poate fi afişată oricare dintre ele.
  • Se garantează că pe datele de test există întotdeauna soluţie.

Exemplu

teroristi.interoristi.out
6 8
miruna
b a
m i
f a
u g
f m
a g
b r
n a
5 2 7 4 8 3

Explicaţie

Se vor folosi următoarele bucăţi:
5 – f m
2 – m i
7 – b r
4 – u g
8 – n a
3 – f a

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content