Задача 1 от брой 10/2008 - Гама лъчи
Победител в първи кръг от Четиринадесетото издание на конкурса по програмиране на PC Magazine Bulgaria и Мусала Софт стана Веселин Георгиев. Той спечели принтер за етикети на Brother, осигурен от списанието и рекламни материали и грамота от Мусала Софт. Наградите бяха връчени от Тервел Няголов, главен редактор на PC Magazine Bulgaria и Пламен Цеков, Технически директор – Мусала Софт.
Задача 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 Ноември.
Място |
Име |
Град |
Общо |
Време |
1 |
Веселин Георгиев |
София |
80 |
3.53 |
2 |
Александър Георгиев |
София |
80 |
9.83 |
3 |
Борис Странджев |
София |
60 |
0.84 |
4 |
Иван Георгиев |
Плевен |
40 |
0.22 |
5 |
Петър Чакалов |
Сливен |
20 |
0.01 |
6 |
Пламен Томов |
София |
20 |
0.01 |
7 |
Станислав Узунчев |
Казанлък |
20 |
0.02 |
8 |
Антон Саров |
Русе |
20 |
0.02 |
9 |
Велислав Николов |
София |
20 |
0.02 |
10 |
Йордан Маджунков |
Плевен |
20 |
0.02 |
11 |
Красимир Георгиев |
Исперих |
20 |
0.02 |
12 |
Ивайло Бояджиев |
Кюстендил |
20 |
0.02 |
13 |
Деян Чакъров |
София |
20 |
0.02 |
14 |
Богдан Шарков |
София |
20 |
0.02 |
15 |
Васил Великов |
София |
20 |
0.02 |
16 |
Георги Ацев |
София |
20 |
0.02 |
17 |
Климент Ненов |
София |
20 |
0.02 |
18 |
Георги Йорданов |
Сливен |
20 |
0.02 |
19 |
Иван Тодоров |
Бургас |
20 |
0.02 |
20 |
Румен Христов |
Шумен |
20 |
0.03 |
21 |
Николай Хубанов |
Габрово |
20 |
0.03 |
22 |
Емануел Мартинов |
Плевен |
20 |
0.05 |
23 |
Стоян Кръстев |
София |
20 |
0.08 |
24 |
Велимир Милев |
София |
20 |
0.16 |
25 |
Калоян Радев |
Добрич |
20 |
0.19 |
26 |
Владимир Цанев |
София |
20 |
0.25 |
27 |
Христо Георгиев |
София |
20 |
0.42 |
28 |
Дамян Станчев** |
Плевен |
14 |
0.02 |
29 |
Ивайло Данколов* |
Мездра |
14 |
0.02 |
30 |
Яна Димова** |
Добрич |
14 |
0.03 |
31 |
Георги Герганов |
София |
0 |
0.00 |
32 |
Борис Белчев |
Пловдив |
0 |
0.00 |
33 |
Никола Николов |
София |
0 |
0.00 |
34 |
Ивайло Петров |
София |
0 |
0.00 |
* Точките на участника са намалени с 30%, защото решението му трябваше да бъде компилирано отново от журито.
** Точките на участника са намалени с 30%, защото програмата му чете или пише в грешен файл или от/на стандартния вход/изход.
Всички тестове, решения и логове на участниците можете да намерите тук
Тук може да прочетете анализ на задачата, изпратен от победителя в кръга - Веселин Георгиев.
За въпроси можете да ни пишете на адрес: konkurs@musala.com.
Supported by Musala Soft Ltd.
Copyright 2000-2010 by Musala Soft Ltd. All rights reserved.
|