Summer FLASG Advanced | TelefonulAdvanced

This was the problem page during the contest. Access the current page here.
Time limit: 0.1s Memory limit: 64MB Input: Output:

ASG s-a săturat de telefonul lui Nokia cu butoane, așa că s-a dus la un amanet de cartier și și-a luat un Nokia nou. Fiind fan înrăit Fortnite, acesta a vrut să instaleze jocul și pe telefon. A văzut că nu este suportat jocul, însă Flaviu i-a dat un site de unde să descarce o variantă neoficială care merge și pe telefoane mai proaste. A aflat după ce a instalat aplicația că i s-a virusat telefonul și are o mulțime de litere pe ecran. Flaviu a remarcat că unele dintre aceste litere formează cuvinte, așa că i-a înmânat un dicționar xx formate din kk cuvinte pentru fiecare din cele QQ linii de pe ecran.

Cerință

Pentru cele QQ linii, să se determine dacă linia curentă se poate forma într-o secvență separată prin spații formată din cuvintele din dicționar.

Date de intrare

Pe prima linie, există numărul natural QQ.
Pentru fiecare din cele QQ interogări se află pe prima linie numerele naturale nn care reprezintă lungimea cuvântului ww (w=n|w| = n), precum și kk care reprezintă numărul de cuvinte din dicționar. Pe următoarea linie se află cuvântul ww. Pe a treia linie se află cuvintele din dicționarul xx.

Date de ieșire

Pentru fiecare din cele QQ interogări, să se afișeze DA dacă se poate forma cuvântul, și NU în caz contrar.

Restricții și precizări

  • 1Q501 \leq Q \leq 50;
  • 1n3001 \leq n \leq 300;
  • 1k1001 \leq k \leq 100;
  • 1xk201 \leq |x_k| \leq 20;
  • Atât ww, cât și xix_i, conțin doar litere mici ale alfabetului englezesc;
  • Toate cuvintele din xx sunt unice;
  • Cuvintele din dicționar pot fi refolosite într-un cuvânt.
# Punctaj Restricții
1 8 n10n \leq 10, k20k \leq 20
2 16 k50k \leq 50
3 20 k=70k = 70
4 56 Fără restricții suplimentare

Exemplul 1

stdin

1 
10 12
asgasefort
as ase gas sef se sg efort ef fort ort ga a

stdout

DA

Explicație

Următoarele secvențe pot fi formate:

a sg a se fort
a sg a sef ort
a sg as ef ort
a sg as efort
a sg ase fort
as ga se fort
as ga sef ort
as gas ef ort
as gas efort

Exemplul 2

stdin

1 
13 6
mangoicecream
man go mango ice cream icecream

stdout

DA

Explicație

Se pot genera următoarele cuvinte:

man go ice cream
man go icecream
mango ice cream
mango icecream

Exemplul 3

stdin

1
6 3
masina
ma as ina

stdout

NU

Explicație

Nu există un mod prin care poți împărți masina folosind ma, as si ina.

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