Runda 5 [Hard] - Talerze

20.12.2010 - Krzysztof Piecuch
TrudnośćTrudność

 

Zadanie tygodnia

Runda 5; kategoria Hard

Limit czasowy: 2s; Limit pamięciowy: 128MB


Talerze

Czasem nieprzyjemne niespodzianki dopadają każdego. Małgosia porządkowała właśnie kuchenne szafki, gdy niechcący zbiła piękny talerz, będący od dziesięcioleci rodzinną pamiątką. Na talerzu pięknymi pozłacanymi literkami zapisane było pewne słowo, którego znaczenie zaginęło w mrokach dziejów. Teraz Małgosia przygląda się fragmentom rozbitego talerza i nie jest w stanie wyczytać z nich ani jednej literki. Jednak przypomina sobie z dziecięcych czasów dwa słowa, które można było utworzyć z kolejnych liter napisu z talerza. 

Czy pomożesz jej znaleźć najkrótszy napis, taki, który zawierałby dwa podane słowa jako swoje (niekoniecznie spójne) podciągi? Na przykład jeśli byłyby to słowa BOCZEK i SENNIK to takim słowem byłby BOCZSENNIK.

Wejście:

W pierwszej linii standardowego wejścia znajdują się dwie liczby: $ n $ oraz $ m $ ($ 1 \leq n, m \leq 10 000 $). W kolejnych dwóch wierszach znajdują się słowa. Pierwsze o długości $ n $, a drugie o długości $ m $. Oba słowa składają się jedynie z wielkich liter alfabetu angielskiego

Wyjście

Należy podać długość najkrótszego słowa z którego po skreśleniu odpowiednich liter można otrzymać oba słowa podane na wejściu.

Przykład:

Wejście:

6 6
BOCZEK
SENNIK

Wyjście:

10

Wytłumaczenie:

Szukane słowo to np. BOCZSENNIK. Żadne krótsze słowo nie zawiera obu podanych na wejściu słów jako swoich podciągów.

 

Nie możesz wysyłać i oglądać rozwiązań tego zadania ponieważ nie jesteś zalogowany. Zaloguj się lub załóż konto.
PozycjaImię i nazwiskoWynikCzasTalerze
1Przemysław Derengowski1001:45:0510
2Piotr Bejda1003:28:1510
3Kamil Dębowski1006:02:2010
4Damian Straszak1013:52:0610
5Kuba Skałecki1015:51:0710
6Adam Czapliński1053:39:0210
7Maciej Szeptuch1056:35:3310
8Wojciech Janczewski1063:18:0510
9Wiktor Kuropatwa1063:22:5810
10Maciej Kisiel1073:50:5510
11Krzysztof Pszeniczny1098:45:1510
12Arek Wróbel10114:20:1810
13Bartek Dudek10160:50:4710
14Bartosz Tarnawski10174:33:3710
15Krzysztof Trzepla10195:12:0010
16Paweł Michalak10536:36:2610
17Witold Długosz101754:46:4710
18Bartłomiej Gajewski989:50:219
19Piotr Żurkowski9580:19:409
20Krzysztof Cirocki834:39:438
21Mateusz Witkowski868:14:358
22Łukasz Hanuszczak881:22:258
23Krzysiek Kwieciński81162:58:418
24Michał Robaszyński732:14:017
25Maciej Gerus761:04:557
26Piotr Kozakowski7157:57:527
27Michał Krawczak7158:59:167
28Grzegorz Araminowicz7252:29:197
29Kamil Rychlewicz638:55:076
30Mateusz Wasylkiewicz682:57:486
31Michał Zezyk51147:40:005
32Szymon Stankiewicz414:14:094
33Jakub Sutowicz214:24:202
34Hubert Jarosz238:23:062
35Mateusz Śmiech1100:37:251
4.666665
Twoja ocena: Brak Ocena: 4.7 (3 ocen)

Copyright © 2008-2010 Wrocławski Portal Informatyczny

design: rafalpolito.com