Задача 1 от брой 10/2008 - Гама лъчи

Победител в първи кръг от Четиринадесетото издание на конкурса по програмиране на PC Magazine Bulgaria и Мусала Софт стана Веселин Георгиев. Той спечели принтер за етикети на Brother, осигурен от списанието и рекламни материали и грамота от Мусала Софт. Наградите бяха връчени от Тервел Няголов, главен редактор на PC Magazine Bulgaria и Пламен Цеков, Технически директор – Мусала Софт.

Условие на задача 1

Задача 1 можете да намерите в брой 10/2008 на PC Magazine Bulgariа. Задачата можете да нaмерите и на този сайт в (PDF) и (DOC) формат. Изпращайте решенията си не по късно от 11 Ноември, като използвате формата за качване на решения в този сайт. 

Уточнения по условието

• За всеки тест програмата трябва да работи за не повече от 25 секунди.
• Ограничението за използваната оперативна памет е 256MB.
• В 40% от тестовите примери ще е изпълнено N<=30000.

• Ако два лъча се пресичат, потенциалът в опасната точка да се изчислява като сума от потенциала върху единия лъч (в точката, която е най-близо до другия лъч) и потенциала върху другия лъч (в точката, която е най-близо до първия).

• Подробно обяснение на примера в задачата:
  - за опасната точка с координати (2,2,1), образувана от първия и втория лъч, изчисляваме потенциала като сума от потенциалите, създавани в точката (2,2,1) от първия източник (Fi(d1)=Fi0*e^(-mu*d1)=1.0*e^(-0.3*2)=0.548811... , където d1=разстоянието между източника (0,2,1) и опасната точка) и от втория източник (Fi(d2)=Fi0*e^(-mu*d2)=1.0*e^(-0.3*sqrt(3))=0.594749..., където d2=разстоянието между източника и опасната точка). За общия потенциал в опасната точка получаваме Fi(d1)+Fi(d2)=0.548811+0.594749=1.14356 и тъй като изискваната максимална грешка в потенциала е 0.0001, и двата отговора 1.1435 и 1.1436 се считат за верни.
  - кандидатът за опасна точка с координати (4,2,1), образуван на първия и третия лъч има потенциал Fi0*e^(-mu*4) + Fi0*e^(-mu*sqrt(5)) = 0.301194+0.511288=0.812482, което е по-малко от FiMax, откъдето следва, че точката не е опасна.
  - тъй като първия и втория лъч не само са на разстояние, не по-голямо от 0.0001, но и се пресичат, то и двата потенциала, участващи в сумата, се изчисляват в една и съща точка (2,2,1). Това се отнася и до лъчите 1 и 3.

• Ако върху два лъча има опасна точка, то във всяка от проекционните равнини ще е налице явно пресичане на лъчите. Това означава, че независимо колко близко се намират два лъча в проекционната равнина, ако не се пресичат, опасна точка не може да се образува. Така условието за съществуване на опасна точка върху два лъча се надгражда до <<разстоянието между лъчите в пространството трябва да е не по-голямо от 0.0001 и проекциите им във всяка от трите проекционни равнини се пресичат>>.

• Броят на цифрите след десетичната запетая при отпечатване на потенциалите в отговора не е от значение. Важно е само абсолютната стойност на разликата между очаквания и отпечатания от участника потенциал да е не по-голяма от 0.0001. Това означава, че правилни резултати за потенциала в отговора на примерния тест са както 1.1435, така и 1.1436, 1.143560974451, 1.143599999999.

Класиране: 



Контестации и забележки можете да изпращате на konkurs@musala.com не по-късно от 21 Ноември. 

* Точките на участника са намалени с 30%, защото решението му трябваше да бъде компилирано отново от журито.

** Точките на участника са намалени с 30%, защото програмата му чете или пише в грешен файл или от/на стандартния вход/изход. 

Всички тестове, решения и логове на участниците можете да намерите тук

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