CSCB324

Задачи 2023

Задача 9: Индекс20
Даден е текст на английски език. Да се направи индекс, създържащ всички думи от текста, по-дълги от две букви, наредени в азбучен ред, и по колко пъти се среща всяка дума в текста. Дума е низ от латински букви с разделител интервал, нов ред, цифра или специален символ.

Вход
Данните се четат от стандартния вход

Изход
Резултатът от работата на програмата се извежда на стандартния изход.

Пример:

Вход
29.11.
The quick brown fox jumps over the lazy dog.
To 00 in the50 ye!

Изход
brown 1
dog 1
fox 1
jumps 1
lazy 1
over 1
quick 1
the 3

Задача 10: Електричество20
Трябва да подсигурите електрическото захранване в огромна зала, където ще се провежда състезание по програмиране. Съществуват два различни стандарта за електрически щепсел и контакт: A и B. Тези стандарти са несъвместими. Щепселът от стандарт A може да бъде включен само в контакт от стандарт A. Щепселът от стандарт B може да бъде включен само в контакт от стандарт B. В залата има точно един главен контакт от тип A. Щепселите на всички компютри, който ще се използват за състезанието, също са от тип A.

Разполагате с множество разклонители от следните два вида:
• Разклонител от първи вид има един щепсел от тип А и няколко гнезда от тип B.
• Разклонител от втори вид има един щепсел от тип B и няколко гнезда от тип A.

Всички разклонители са много силни и могат да издържат на огромно натоварване. Така че можете да създадете енергийна мрежа, чрез свързване на един разклонител от първия тип към главния контакт. След това няколко разклонители от втори тип към него. Към тези разклонители можете да навържете други такива от първи тип и т.н.

Вашата задача е да намерите максималния брой компютри, които могат да бъдат свързани към електрическата мрежа, използвайки на наличните разклонители.

Вход.
Първият ред на стандартния вход ще съдържа броя на тестовите примери. Първият ред на всеки тест започва с броя на разклонителите от първи тип n и тези от втори тип m. Вторият ред съдържа n числа ai – броя на гнездата за всеки от разклонителите от първи тип. Третият ред съдържа m числа bi – броя на гнездата за всеки от разклонителите от втори тип.

Ограничения.
0 ≤ n, m ≤ 100000
1 ≤ ai, bi ≤ 1000 

Изход.
За всеки тест извеждайте на отделен ред търсения брой компютри, които могат да бъдат свързани.

Примерен тест:
2
3 2
3 2 1
2 3
2 3
2 2
2 3 1

Решение на примерния тест:
5
5