Musala Soft Logo Конкурс по програмиране на Musala Soft и PC Magazine Bulgaria PC Magazine Bulgaria Logo
  Състезателна система
Сезон 2010 - 2011
Сезон 2009 - 2010
Сезон 2008 - 2009
Сезон 2007 - 2008
Сезон 2006 - 2007
Сезон 2005 - 2006
Сезон 2004 - 2005
Сезон 2003 - 2004
Правила
Задача 1
Задача 2
Задача 3
Задача 4
Задача 5
Задача 6
Класиране
Финален кръг
Сезон 2002 - 2003
Сезон 2001 - 2002
Сезон 2000 - 2001

Задача 1 от брой 10/2003 - МОЛЕКУЛИ



Победител в първи кръг на конкурса за 2003-2004 година стана Камен Добрев. Той получи грамота, абонамент за PC Magazine Bulgaria, софтуерния продукт Fine Reader, книги.

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

Световно известният молекулярен биолог Низю Стрингьов се сблъскал със следния проблем. Той изучава свойствата на белтъчните молекули в зависимост от срещането на известни или неизвестни до момента наредени комбинации от съставки. При тези изследвания му се сторило, че свойствата много силно зависят от ...
Пълното условие на задачата (RTF Format) можете да намерите в брой 10/2003 на списание PC Magazine или да свалите от тази страница.

Коментар по условието на задача 1 (публикувано в PC Magazine):

  • Празният низ НЕ се брои за комбинация, т.е. за числата от изходния файл трябва също да е вярно, че L + F - 1 >= T; т.е. началата на първата, втората и третата комбинация от намерения низ са валидни
  • Третата известна комбинация от входния файл трябва да е "cabc" (НЕ "caba"), за да са верни и двата примерни изходни файла.

Класиране:

Място Име Град Общо
1 Камен Добрев София 100#
2 Валентин Михов Варна 100
3 Владимир Недев Варна 92
3 Стоян Йорданов София 92
5 Илиян Илиев София 84
5 Петър Милев София 84
5 Радослав Герганов София 84
8 Мартин Чилев В.Търново 76*
8 Николай Тодоров София 76
10 Тодор Арнаудов Пловдив 75
11 Славчо Иванов София 69
12 Антон Димитров Варна 68
12 Даниел Кираджиев София 68
12 Мехти Мемиш София 68
12 Тихомир Стоянов Първомайци 68
12 Чавдар Мечков София 68
17 Невен Николов Бургас 63
18 Диян Иванов София 60
19 Венцислав Почекански София 59
19 Владимир Ралев Бургас 59
19 Денчо Банков София 59*
19 Николай Милчев София 59
19 Цветомир Цонев Севлиево 59
24 Стефан Буйнов Перник 57
25 Божидар Русев София 56
25 Владимир Молотков София 56
25 Никола Арнаудов София 56
28 Иван Бобев Сливен 52
28 Йордан Гордеев В.Търново 52
30 Вангел Паронов София 51
30 Стефан Ташев Ямбол 51
32 Милен Елкин София 48
32 Мирослав Калъпов Казанлък 48
32 Нели Стефанова В.Търново 48
35 Росен Георгиев В.Търново 46
36 Велислав Николов София 44
37 Боян Бонев Пловдив 43
37 Цветан Комаров Пазарджик 43
37 Шенол Юсуф София 43
40 Ангел Владов Г.Оряховица 41
40 Станислав Асенов Казанлък 41
42 Александър Андонов Варна 40
42 Асен Илиев София 40
42 Георги Георгиев София 40
42 Деян Варчев Разград 40
42 Иван Гочев Ямбол 40
42 Кирил Минков Пловдив 40
42 Николай Цанков София 40
42 Петко Минков София 40
42 Тодор Петков София 40
42 Христо Йончев София 40
52 Ангел Джигаров Бургас 39
53 Орлин Колев София 38
54 Атанас Ковачев София 36
54 Даниела Цветанова В.Търново 36
56 Борис Даскалов София 32
56 Боян Георгиев Г.Оряховица 32
56 Георги Герганов Плевен 32
56 Георги Панайотов Варна 32
56 Йордан Зайков Пловдив 32
56 Максим Запрянов Хасково 32
56 Павел Владов Г.Оряховица 32
56 Стефан Павлов Сливен 32
64 Петър Добрев Казанлък 26
65 Антон Антонов В.Търново 24
66 Свилен Колев София 21
67 Владимир Георгиев Пазарджик 20
68 Боян Шейтанов Пловдив 17
69 Владимир Цанев София 16
69 Живко Тянков Хасково 16
71 Павел Хараламбов Бургас 11
72 Стефан Стефанов Варна 9
73 Виктор Беневски Плевен 8
74 Захари Караджов София 3*
75 Георги Костов Варна 0
75 Златко Михайлов Ямбол 0
75 Пламен Маринов София 0

# Решението на Камен Добрев е по-бързо от това на Валентин Михов.
* Решения получени след крайния срок, които няма да бъдат включени в общото класиране.

Също така, можете да видите пълното класиране по тестове.

Тестове:

Тестовете (ZIP Format), въз основа на които журито е формирало класирането, са достъпни за всички. Можете да ги намерите чрез съответния линк.

Коментар по решението и резултатите на участниците:

Резултатите показват, че повечето от участниците правилно са се насочили към алгоритъма на Ахо-Корасик, но не са съобразили, че за приближено решение не са необходими всички срещания на шаблони (за някои от тестовете това не може да стане в разумно време и в наличната памет). Струва си да отбележим, че използването на неофициални библиотеки е рисковано - някои от готовите библиотечни функции, реализиращи АК не работят правилно. Двама участници успяха да съберат пълния брой точки - Камен Добрев от София и Валентин Михов от Варна. Първото място беше отредено на Камен Добрев, заради по бързото му решение (Камен чете много бързо входните данни и използва статична памет за построяването на дървото).

Предлагаме Ви и алгоритмичен анализ на задача 1.

Задача 1 (Молекули) - участници (по дата и час на последното получено решение):

  1. Божидар Русев - София - 04.11.2003, 00:42
  2. Мехти Мемиш - София - 04.11.2003, 14:10
  3. Златко Михайлов - Ямбол - 06.11.2003, 12:03
  4. Александър Андонов - Варна - 10.11.2003, 14:47
  5. Николай Цанков - София - 11.11.2003, 17:52
  6. Иван Гочев - Ямбол - 12.11.2003, 11:51
  7. Владимир Георгиев - Пазарджик - 12.11.2003, 22:49
  8. Невен Николов - Бургас - 13.11.2003, 14:05
  9. Петър Добрев - Казанлък - 13.11.2003, 16:15
  10. Владимир Ралев - Бургас - 13.11.2003, 17:14
  11. Стефан Стефанов - Варна - 13.11.2003, 21:17
  12. Ангел Джигаров - Бургас - 16.11.2003, 10:36
  13. Георги Герганов - Плевен - 16.11.2003, 19:24
  14. Орлин Колев - София - 16.11.2003, 22:29
  15. Боян Шейтанов - Пловдив - 17.11.2003, 15:09
  16. Вангел Паронов - София - 17.11.2003, 18:16
  17. Цветомир Цонев - Севлиево - 17.11.2003, 19:30
  18. Пламен Маринов - София - 18.11.2003, 02:53
  19. Стефан Ташев - Ямбол - 18.11.2003, 12:20
  20. Тодор Петков - София - 18.11.2003, 12:29
  21. Деян Варчев - Разград - 18.11.2003, 12:59
  22. Стефан Буйнов - Перник - 18.11.2003, 14:21
  23. Илиян Илиев - София - 18.11.2003, 15:49
  24. Боян Георгиев - Горна Оряховица - 18.11.2003, 16:03
  25. Иван Бобев - Сливен - 18.11.2003, 19:33
  26. Даниел Кираджиев - София - 18.11.2003, 22:16
  27. Цветан Комаров - Пазарджик - 18.11.2003, 22:25
  28. Даниела Цветанова - Велико Търново - 19.11.2003, 04:47
  29. Антон Димитров - Варна - 19.11.2003, 10:23
  30. Шенол Юсуф - София - 19.11.2003, 11:20
  31. Георги Георгиев - София - 19.11.2003, 12:05
  32. Славчо Иванов - София - 19.11.2003, 13:43
  33. Станислав Асенов - Казанлък - 19.11.2003, 14:27
  34. Павел Владов - Горна Оряховица - 19.11.2003, 17:22
  35. Чавдар Мечков - София - 19.11.2003, 18:54
  36. Стефан Павлов - Сливен - 19.11.2003, 19:20
  37. Ангел Владов - Горна Оряховица - 19.11.2003, 19:31
  38. Велислав Николов - София - 19.11.2003, 21:03
  39. Радослав Герганов - София - 19.11.2003, 23:09
  40. Росен Георгиев - Велико Търново - 19.11.2003, 23:55
  41. Георги Костов - Варна - 20.11.2003, 11:43
  42. Антон Антонов - Велико Търново - 20.11.2003, 12:47
  43. Нели Стефанова - Велико Търново - 20.11.2003, 13:12
  44. Йордан Зайков - Пловдив - 20.11.2003, 13:31
  45. Тодор Арнаудов - Пловдив - 20.11.2003, 13:46
  46. Атанас Ковачев - София - 20.11.2003, 14:02
  47. Живко Тянков - Хасково - 20.11.2003, 14:04
  48. Петко Минков - София - 20.11.2003, 14:29
  49. Боян Бонев - Пловдив - 20.11.2003, 15:30
  50. Николай Милчев - София - 20.11.2003, 16:16
  51. Виктор Беневски - Плевен - 20.11.2003, 16:50
  52. Борис Даскалов - София - 20.11.2003, 17:50
  53. Венцислав Почекански - София - 20.11.2003, 19:43
  54. Петър Милев - София - 20.11.2003, 19:46
  55. Мирослав Калъпов - Казанлък - 20.11.2003, 20:06
  56. Георги Панайотов - Варна - 20.11.2003, 20:14
  57. Тихомир Стоянов - Първомайци - 20.11.2003, 20:51
  58. Владимир Недев - Варна - 20.11.2003, 21:15
  59. Милен Елкин - София - 20.11.2003, 21:25
  60. Никола Арнаудов - София - 20.11.2003, 21:33
  61. Павел Хараламбов - Бургас - 20.11.2003, 21:47
  62. Владимир Молотков - София - 20.11.2003, 22:02
  63. Стоян Йорданов - София - 20.11.2003, 22:41
  64. Максим Запрянов - Хасково - 20.11.2003, 22:44
  65. Валентин Михов - Варна - 20.11.2003, 23:31
  66. Асен Илиев - София - 20.11.2003, 23:34
  67. Владимир Цанев - София - 20.11.2003, 23:37
  68. Йордан Гордеев - Велико Търново - 20.11.2003, 23:37
  69. Свилен Колев - София - 20.11.2003, 23:39
  70. Камен Добрев - София - 20.11.2003, 23:45
  71. Николай Тодоров - София - 20.11.2003, 23:46
  72. Христо Йончев - София - 20.11.2003, 23:48
  73. Диян Иванов - София - 20.11.2003, 23:54
  74. Кирил Минков - Пловдив - 20.11.2003, 23:58
  75. Мартин Чилев - Велико Търново - 21.11.2003, 00:28 --> Закъсняло Решение
  76. Захари Караджов - София - 21.11.2003, 09:15 --> Закъсняло Решение
  77. Денчо Банков - София - 23.11.2003, 01:53 --> Закъсняло Решение

Решения на всички участници:

За да може всеки лично да се убеди защо класирането е такова и защо има X, а не Y точки, публикуваме всички изпратени решения заедно с изходните кодове на всички програми (с изключение на тези, които пожелаха сорсът им да не се публикува). За всеки участник са създадени .log файлове, които отразяват как са преминали тестовете върху програмата му. Въпросният .log файл се дава само за да добиете представа защо получавате точките, които са ви дадени, но не винаги отразява точната причина за провала на тестовете. Имайте предвид това.

Контестации:

Контестации могат да се подават от всички участници, стига да са основателни. Ще се разглеждат само претенции на участници, които са оценени неправилно в резултат от грешка на журито. Моля преди да изпратите контестация, внимателно прочетете условието на задачата за да прецените дали тя е основателна. Журито ще отговори на всички ваши въпроси, свързани с оценяването.

За въпроси можете да ни пишете на адрес: konkurs@musala.com.

Supported by Musala Soft Ltd.

Copyright 2000-2010 by Musala Soft Ltd. All rights reserved.