Новият български мобилен оператор Безжичтел въвежда нова услуга – изпращане на SMS съобщение до двама души едновременно! От Безжичтел биха искали да предлагат услугата на цена по-ниска от цената за две отделни съобщения и за целта им е необходима вашата помощ. Мрежата на мобилния оператор се състои от N клетки (3 ≤ N ≤ 4000), като някои двойки от тях са свързани и могат да си предават съобщения. Всяка връзка има цена за изпращане на съобщение по нея, като цената е равна на енергията необходима за изпращането на съобщението. Поради особеностите на терена енергията необходима за изпращането на съобщение може да е различна за двете посоки на една връзка. Трябва да имаме предвид още, че някои предаватели са с ограничена мощност и поради това някои връзки са използваеми само в едната посока (т.е. всяка зададена връзка е еднопосочна). Броят на връзките няма да надвишава 1 000 000.
Връзките на Безжичтел са безжични, затова имат една важна особеност. Ако клетка A изпраща съобщение до клетка B с енергия К, всички клетки, които изискват енергия по-малка или равна на К, за да получат съобщение директно (без посредник) от А, също ще получат съобщението до B. Например, ако цената за изпращане на съобщение от A до B е 5, от А до C е 3, а от А до D е 8, то тогава съобщението от А до B, изпратено с енергия 5 ще бъде получено и от C, но няма да бъде получено от D. Ако, обаче, от C до E има връзка изискваща енергия 1, но няма връзка от A до E, то тогава съобщението от А до B независимо с каква енергия е изпратено, няма да бъде получено от E. Шефовете на Безжичтел биха искали да използвате тази особеност, за да минимизирате цената за изпращане на едно съобщение от една клетка, до други две клетки едновременно.
Напишете програма WIRELESS.EXE, която по зададено N, цените за изпращане на съобщение по различните връзки на Безжичтел и номерата на три клетки А, B и C, намира ней-евтината схема за изпращане на съобщение от А до B и C.
Входните данни се четат от стандартния вход и се състоят от N +1 реда. На първия ред е записано числото N, както и номерата А, B и C в този ред, разделени с по един интервал (трите номера на клетките са три различни, цели числа между 1 и N включително). На всеки от следващите N реда са записани данните за клетката със съответния номер (на първия от тези редове са данните за клетка номер 1, на втория – за клетка номер 2 и т.н.) I-тият от тези редове започва с цяло число KI (0 ≤ KI < N), задаващо броя на клетките, на които клетка номер I може да изпраща съобщение. Следват KI двойки цели числа, като всяка двойка описва една от тези KI клетки. Първото число на двойката задава номера на клетката, а второто задава цената за изпращане на съобщение от клетка I до тази клетка (цената е цяло число между 0 и 100 000 включително). Клетките на реда са подредени според цените (вторите числа) във възходящ ред. Всички числа на реда са разделени с по един интервал.
Резултатът от вашата програма трябва да бъде изведен на стандартния изход. Първият ред трябва да съдържа две числа, разделени с интервал – броя M на изпращания на съобщението във вашата схема и общата цена на изпращанията (която е сумата от цените на отделните изпращания). Следващите M реда трябва да описват изпращанията на съобщенията в хронологичен ред. Всеки ред трябва да съдържа две числа разделени с интервал – номера на клетката изпращаща съобщението и количеството енергия, което се използва. Никоя клетка не може да изпрати съобщението преди да го е получила, с изключение на клетката с номер А. След изпълнението на описаните от вас изпращания трябва и двете клетки-получатели B и C да са получили съобщението, при това общата цена на схемата трябва да е минималната възможна. В случай, че съществуват няколко такива схеми, изберете и изведете само една. Поставената задача винаги има решение.
ПРИМЕР 1Вход Изход4 1 2 3 2 3 2 3 1 4 2 1 1 0 3 2 2 4 1 2 2 1 2 2
Клетка 1 изпраща съобщението до клетка 3, която после го изпраща до клетка 2.
|
ПРИМЕР 2Вход Изход4 1 2 3 2 4 2 4 3 3 4 1 3 0 4 1 2 2 1 4 8 2 3 1 2 1
Клетка 1 изпраща съобщението до клетка 4, която после го изпраща до клетки 2 и 3 едновременно.
|
Известният професор по теория на числата Числослав Простократнов и не по-малко известният програмист Лудни Бъгски усилено спорели за това, кое е по-използваемо в съвременната приложна теория на числата – феноменалният професорски ум, или способността на компютрите да правят милиони изчисления в секунда без наличието на какъвто и да е било ум. За да решат спора си, те решили да играят следната игра (наречена по имената на двамата играчи Числудница)
Играта се играе на черна дъска, на която във всеки момент са записани две естествени числа. В началото на дъската са написани две числа, всяко от които е не по-малко от 2 и не по-голямо от 500. Двамата играчи се редуват правейки ходове с двете написани числа. Всеки ход се състои от следното. Играчът на ход избира едно от числата и го заменя с по-малко число, което е кратно на негов делител. Едно число А може да бъде заменено с друго число B (1<B<А) тогава и само тогава, когато А и B не са взаимно прости. Например числото 12 може да бъде заменено с числата 2, 3, 4, 6, 8, 9 и 10. Едновременно с тази замяна, играчът на ход трябва задължително да увеличи другото число на дъската с едно. Така възможните ходове от комбинацията (12, 6) са (2, 7), (3, 7), (4, 7) , (6, 7), (8, 7), (9, 7), (10, 7), (13, 2), (13, 3) и (13, 4),. Играта завършва тогава, когато играчът, който е на ред не може да направи валиден ход (т.е. числата на дъската са прости). Играчът, който в този момент е на ход губи играта.
Първи на ход е Бъгски, а началните числа се генерират от компютърна програма, написана от негов приятел, и затова са такива, че независимо от ходовете на проф. Простократнов, Бъгски може да спечели играта (стига да играе подходящи ходове). Затова г-н Бъгски може да напише програма, която да играе играта от негово име и винаги да печели, независимо от ходовете на проф. Простократнов. А вие? Напишете програма CRAZY.EXE, която по зададени две числа X и Y (2£X£500, 2£Y£500) играе и печели Числудница с минимален брой ходове.
Числата X и Y, както в началото, така и след всеки ход на опонента се получават в двата аргумента на подпрограмата getnum. Ходът на опонента винаги ще е валиден. Ако имате възможен ход, т.е. може да се променят X и Y в съответствие с правилата в X1 и Y1, съответно, това трябва да стане с извикване на подпрограмата setnum с аргументи X1 и Y1. Редът на числата трябва да остане непроменен (т.е. от (15, 6) валиден ход е (16, 2), но не и (2, 16)). Ако изпратените от програмата две числа са прости, т.е. печелите играта, както и ако нямате възможен ход, т.е. след поредния ви ход опонентът е достигнал до две прости числа и значи губите, setnum ще прекрати изпълнението на програмата.
Проф. Простократнов е изключително добър специалист и ако му дадете възможност, той ще ви победи. Освен това, в губеща позиция той ще играе така, че да отложи загубата си колкото може повече, независимо от вашите ходове. Иначе казано, за да победите проф. Простократнов с минимален брой ходове трябва да играете оптимално, а не да разчитате на грешка от негова страна.
Програмата ще бъде оценена с 20 тестови примера, като за всеки от тях ще получите 5 точки в случай че програмата спечели играта с минимален брой ходове, 1 точка в случай че програмата спечели играта, но не с минималния брой ходове и 0 точки в случай че програмата загуби играта или направи невалиден ход. Спечелването на играта в половината от тестовете не може да стане по друг начин освен по оптималния вачин, затова програма, която винаги печели играта, но не го прави по най-добрия начин ще спечели минимум 60 точки.
343 3 7 32
7 4 8 8
8 2 9 4
2 3 3 5
Библиотека за FreePascal (module.ppu, module.o)
procedure getnum(var X,Y: LongInt);
procedure setnum(X1,Y1: LongInt);
Инструкции: За да компилирате вашия файл crazy.pas, включете оператора uses module; в изходния текст и компилирайте с
fpc –So –O2 –XS crazy.pas
Програмата example.pas е пример за използване на тази библиотека.
Библиотека за GNU C/C++ (module.h, module.o)
void getnum(long* X, long* Y);
void setnum(long X1, long Y1);
Инструкции: За да компилирате вашия файл crazy.c или crazy.cpp, използвайте #include "module.h" в изходния текст и компилирайте с:
gcc –O2 -static crazy.c module.o -lm -o crazy.exe
gXX –O2 -static crazy.cpp module.o -lm -o crazy.exe
Програмата example.c е пример за използване на тази библиотека.
За пишещите на C/C++ в RHIDE: Непременно задайте на Options->Linker configuration стойност module.o.
Експерименти: За да тествате програмата си ще разполагате с експериментална версия на действителния модул. Тя чете началните две числа, с които искате да проверите програмата си от единствения ред на файла crazy.in. Резултатът от експеримента – дали програмата ви печели или губи – ще бъде изведе във файла crazy.out. Модулът за експерименти не винаги играе оптимално и не дава информация дали програмата ви е играла оптимално.
Задача А3. КРЪГЛА МАСА
Крал Артур често събирал рицарите си на кръглата маса, както за обсъждане на важни въпроси, така и за празнуване. Веднъж той ги поканил да отпразнуват поредната победа, но когато всички се събрали се оказало, че били доста повече от местата на масата, тъй като някои от рицарите довели и свои приятели. Крал Артур не искал да връща гости, затова наредил на слугите да намерят по-голяма маса, която да поставят на мястото на старата. Броят на гостите бил 2N, където N е естествено число ненадминаващо 2000. Крал Артур бил човек на реда и обичал всяко нещо да бъде на мястото си, затова раздал на гостите номера от 1 до 2N. Местата били означени със същите числа (в последователността в която са наредени около масата) и всеки гост трябвало да седне на мястото означено с неговия номер. Гостите можели да влизат в стаята през две врати: първата се намира между местата с номера 1 и 2N, а втората, диаметрално противоположна, се намира между местата с номера N и N +1. Пред първата врата се били подредили N от гостите, а пред втората – останалите N.
За нещастие, залата (която също била кръгла) не била достатъчно голяма. След като новата маса била инсталирана се оказало, че за да може някой гост да отиде до мястото си, трябва да вдигне всеки вече седнал, покрай когото минава. Рицарите били умни и се замислили как да организират влизането в залата, с минимален брой вдигания на вече седнали гости. Ясно било, че гостите ще влизат един по един, спазвайки реда на всяка от вратите, но може да се определи поне от коя врата да влезе следващият гост, като след влизането той тръгва в тази от двете посоки (по часовниковата стрелка или обратно на часовниковата стрелка) за да стигне до мястото си, в която ще вдигне по-малко седнали.
Задачата е да напишете програма ROUND.EXE, която по зададен ред на гостите пред всяка врата да намира минималния брой вдигания на вече седнали гости, при който всички да стигнат до местата си.
Входните данни са зададени на стандартният вход, като на първия ред е числото N. На вторият ред са зададени номерата на N гости, в реда по който са наредени пред първата врата, разделени с по интервал, а на третия – номерата на останалите N гости в реда, по който са наредени пред втората врата, също разделени с по един интервал. Гостът, чийто номер е първи в реда ще влезе първи от съответната врата.
Не единствения ред на стандартният изход програмата трябва да изведе едно число – минималния брой разминавания.
Вход: Изход:
3 3
4 5 3
6 2 1