IATI Day 2, Junior group
Bulgarian
XVI INTERNATIONAL ADVANCED TOURNAMENT IN INFORMATICS
ПРОЛЕТНИ СЪСТЕЗАНИЯ ПО ИНФОРМАТИКА, ШУМЕН 2025
Задача C23. МОНОПОЛИ 2 1 sec. 256 MB
След като помогнахте на Deni да направи перфектната карта за игра на монопол
през 2021 г., тя отново се нуждае от вашата помощ! Припомняме, че игралната карта
за монопол се състои от 𝑁 полета (номерирани от 1 до 𝑁) и 𝑀 еднопосочни връзки
между тях. Тук 𝑀 = 𝑁 − 1. Еднопосочните връзки отговарят на следните условия –
няма връзка от поле към себе си и няма различни връзки между една и съща двойка
полета. Връзките имат свойството, че всяко поле е достъпно от поле 1.
Дефиниция: Нека имаме пермутация на числата от 1 до 𝑁. Ние наричаме
пермутацията подходящо подреждане на полетата, ако е изпълнено следното
условие – за всяка връзка от поле 𝑖 към поле 𝑗, 𝑖 трябва да бъде преди 𝑗 в
пермутацията.
Проблемът за Deni е, че тя загуби идеалната карта за игра на монопол. За
щастие нейният приятел Боби си спомня картата, но той реши да се позабавлява
с нея, преди да й каже кои са връзките. Първо, Боби казва на Deni, че подходящото
подреждане на полетата е последователността 1, 2, … , 𝑁. След това Боби ще
отговори на няколко въпроса от Deni, за да й помогне да разбере какви са
връзките между полетата. Всеки въпрос ще бъде за това доколко подходяща е
някаква пермутация на числата от 1 до 𝑁 (за повече подробности вижте раздела
„Подробности за имплементацията“). Нашата героиня иска вашата помощ, за да
измисли и приложи стратегия с възможно най-малко въпроси.
Задача
Напишете програма monopoly2, която намира неизвестните връзки с възможно
най-малко въпроси към Боби. Тя трябва да съдържа функцията find_connections,
която ще се компилира с програмата на журито (за ролята на Боби).
Подробности за имплементацията
Вашата функция find_connections трябва да има следния формат:
std::vector <std::pair <int, int> > find_connections (int N);
Тя ще бъде извикана еднократно от програмата на журито с един параметър –
брой полета. Функцията трябва да върне списък от подредени двойки, описващи
намерените връзки между полетата. Редът на наредените двойки в списъка няма
значение.
Функцията за задаване на въпроси към Боби има следния формат:
std::vector <bool> check (std::vector <int> p);
Параметърът p е пермутацията на числата от 1 до 𝑁 във въпроса. Резултатът е
булев вектор b с размер 𝑁, където 𝑏𝑖 = 1 (0 ≤ 𝑖 < 𝑁) тогава и само тогава, когато е
изпълнено едно от следните условия:
• съществува връзка от поле 𝑝𝑗 към поле 𝑝𝑖 при 𝑖 < 𝑗;
• съществува поле 𝑝𝑗 за което 𝑏𝑗 = 1 и вие може да се движите по връзките от 𝑝𝑗
до 𝑝𝑖.
Забележете, че еднозначността на стойностите следва от свойствата на
връзките.
Task C23. МОНОПОЛИ 2 iati-shu.org Page 1 of 4
IATI Day 2, Junior group
Bulgarian
XVI INTERNATIONAL ADVANCED TOURNAMENT IN INFORMATICS
ПРОЛЕТНИ СЪСТЕЗАНИЯ ПО ИНФОРМАТИКА, ШУМЕН 2025
Ако последователността не е валидна пермутация на числата от 1 до 𝑁, ще
получите Wrong answer за теста. Сложността на функцията е 𝑂(𝑁 ). Можете да
извикате тази функция най-много 108
𝑁 пъти, в противен случай ще получите Wrong
answer.
Вашата програма monopoly2 трябва да имплементира функцията find
connections. Може да съдържа и друг код, функции и глобални променливи, но не
трябва да съдържа функцията main. Освен това не трябва да четете от стандартния
вход или да печатате към стандартния изход. Вашата програма трябва да включва
заглавния файл monopoly2.h чрез инструкцията към препроцесора:
#include "monopoly2.h"
Ограничения
♣ 1 ≤ 𝑁 ≤ 1 000;
♣ 𝑀 = 𝑁 − 1.
Subtasks
Подзадача Точки Необходими
подзадачи 𝑁 Други ограничения
0 0 − − Картата от примерната
комуникация.
1 5 − ≤ 1 000
1, 2, … , 𝑁 е единственото
подходящо подреждане на
полетата.
2 6 0 ≤ 6 –
3 17 1 ≤ 1 000
1, 2, … , 𝑁 могат да бъдат получени
и чрез започване с полето 1, след
това изброяване на полетата с
директни връзки от 1, след това
изброяване на полета с
еднопосочни връзки от второто
добавено поле и т.н.
4 13 0, 2 ≤ 300 –
5 59 0 − 4 ≤ 1 000
Ако започнем от поле 1 и
следваме връзките, не можем да
използваме повече от 25 връзки.
Точките за дадена подзадача се получават само ако всички тестове за нея и
задължителните подзадачи са успешно издържани, като точките са равни на
минималния резултат от теста за нея и задължителните подзадачи, умножен
по точките на подзадачата.
Оценяване
Всеки тест получава резултат, който е дробно число между 0 и 1 включително.
Ако даден тест има положителен резултат, той се счита успешен за вашето
Task C23. МОНОПОЛИ 2 iati-shu.org Page 2 of 4
IATI Day 2, Junior group
Bulgarian
XVI INTERNATIONAL ADVANCED TOURNAMENT IN INFORMATICS
ПРОЛЕТНИ СЪСТЕЗАНИЯ ПО ИНФОРМАТИКА, ШУМЕН 2025
решение. Тестът има положителен резултат, ако успешно откриете връзките между
полетата.
Ако 𝑐𝑛𝑡 е броят на извикванията на функцията check за определен тест, тогава
резултатът от теста се изчислява по следния начин:
• За всички подзадачи: ако 𝑐𝑛𝑡 > 108
𝑁 , тогава резултатът е равен на 0.
• Подзадача 0, 1, и 2.
– Ако 𝑐𝑛𝑡 ≤ 108
𝑁 , тогава резултатът е равен на 1.
• Подзадача 3.
– Ако 𝑐𝑛𝑡 ≤ 10 000, тогава резултатът е равен на 1.
– Ако 10 000 < 𝑐𝑛𝑡 ≤ 15 000, тогава резултатът е равен на min( 1000
𝑐𝑛𝑡−9000 , 1).
– Ако 15 000 < 𝑐𝑛𝑡 ≤ 108
𝑁 ,тогава резултатът е равен на 0.1.
• Подзадача 4.
– Ако 𝑐𝑛𝑡 ≤ 50 000,тогава резултатът е равен на 1.
– Ако 50 000 < 𝑐𝑛𝑡 ≤ 200 000,тогава резултатът е равен на min( 25000
𝑐𝑛𝑡−25000 , 1).
– Ако 200 000 < 𝑐𝑛𝑡 ≤ 108
𝑁 , тогава резултатът е равен на 0.1.
• Подзадача 5.
– Ако 𝑐𝑛𝑡 ≤ 170, тогава резултатът е равен на 1.
– Ако 170 < 𝑐𝑛𝑡 ≤ 1000, тогава резултатът е равен на min((170+3000
𝑐𝑛𝑡+3000 )3000
𝑐𝑛𝑡 , 1).
– Ако 1000 < 𝑐𝑛𝑡 ≤ 20 000,тогава резултатът е равен на min((170
𝑐𝑛𝑡 )0.4, 0.5).
– Ако 20 000 < 𝑐𝑛𝑡 ≤ 108
𝑁 , тогава резултатът е равен на 0.1.
Пример за комуникация
Нека имаме следната илюстрация на карта с 5 полета и 4 връзки:1
2
3
4
5
Действия на вашата програма Отговор на журито
find_connections(5)
check({2, 3, 4, 5, 1}) return {1, 1, 1, 1, 0}
check({1, 5, 2, 3, 4}) return {0, 1, 0, 0, 0}
check({1, 4, 3, 2, 5}) return {0, 1, 1, 0, 0}
return {{1, 2}, {2, 3}, {3, 4}, {2, 5}}
Task C23. МОНОПОЛИ 2 iati-shu.org Page 3 of 4
IATI Day 2, Junior group
Bulgarian
XVI INTERNATIONAL ADVANCED TOURNAMENT IN INFORMATICS
ПРОЛЕТНИ СЪСТЕЗАНИЯ ПО ИНФОРМАТИКА, ШУМЕН 2025
Локално тестване
За локално тестване се предоставят следните файлове: monopoly2.h,
Lgrader.cpp, примерен файл monopoly2.cpp за вашата програма и файл с
картата от примерната комуникация. Когато предоставените файлове са в една и
съща папка, можете да компилирате заедно вашата програма monopoly2.cpp и
Lgrader.cpp. Това ще направи програма за проверка на коректността на вашата
функция.
Програмата ще изисква от стандартния вход следната последователност от
числа:
− на първия ред: едно цяло положително число – брой на интервалите 𝑁;
− на всеки от следващите 𝑁 − 1 реда две положителни цели числа, които описват
еднопосочни връзки.
Ако не следвате протокола за комуникация, ще получите подходящо съобщение
за грешка. В противен случай, ако програмата е успешна, ще получите съобщението
„Правилно намерени връзки.“.