Увидел тут одну любопытную задачку. В субботу пара наших студентов принимала участие в заочной олимпиаде по программированию, проводимой южноуральским госунивером. При подготовке им дали доступ к условиям задач, которые предлагались на предыдущих олимпиадах. Одна из них меня здорово заинтересовала тем, вроде-бы легко решается "в лоб", но такое решение сквозь тесты не проходит.
Условие примерно такое (точную формулировку не помню, но суть передам): В зоопарке есть N видов животных. Каждого вида - определенное количество (скажем Xi, где 1<=i<=N). На выставку хотят выбрать три зверика разных видов. Вопрос: сколько всего уникальных комбинаций звериков можно выбрать для выставки? Пример: при наличии двух львов, одного заяца, одного волка и одного медведя можно получить 7 уникальных комбинаций: лев1 заяц волк лев1 заяц медведь лев1 волк медведь лев2 заяц волк лев2 заяц медведь лев2 волк медведь заяц волк медведь На входе задачи - по числу зверей одного вида в каждой строке. На выходе - число уникальных комбинаций. А теперь самое главное. 1<=N<=100000, общее кол-во зверей также до 100000, время работы программы - не более 2 секунд. Кто первым уложится? Добавлено спустя 54 минуты 11 секунд: Совсем забыл. Вот тот-же тест, но для дос и винпррограм. По два символа на перевод строки. А то турбопаскаль или обжектпаскаль, например, хотят символы с кодами 10 и 13 в конце строки. Символ с кодом 10 концом строки не считают.
|
По мотивам международных олимпиад сляпал сегодня тестопрогонщик для произвольных задач:
http://shgpi.ru/scripts/tasks/ Удобно сверять свои результаты с верными. В IE не проверял, но, имхо, интерфейс должен работать и там. |
а какие пары получились можно на выходе сделать? _________________ Ищи баги в себе!!! |
Там пары, вернее - тройки, не считаются. Иначе по исходным условиям за 2 секунды вжизь не посчитать. |
Если есть решатель, значит задача решена??? |
Ага
Двадцать минут (с трудом вспоминая комбинаторику) на вывод формулы (листочек+ручка), десять - на программу (клава+freepascal). Плюс пять минут на перевод с freepascal на php, чтобы в решатель вставить. Последнее, понятно, необязательно на своем хостинге, где можно просто исполняемый файл запустить, а результаты выполнения - юзеру отправить. Впрочем 100000 звериков и на php за 0.3 секунды считает, так что можно с исполняемым файлом не заморачиваться. Кстати, в решатель задачки добавляю очень просто:
|
Двадцать минут!!!
У меня ушло часа три на поиск закономерностей!!! Но решение получилось красивое, всего строчек в 15. Добавлено спустя 2 часа 14 минут 57 секунд: xdsl, а есть ещё подобные задачки? |
Задачка взята отсюда: http://ipc.susu.ac.ru
Из более сложных попробуйте задачки про лабиринт и особенно волшебный лабиринт отсюда: http://shgpi.ru/f11/info/conf_olimp_2007/objavl_zao_olimp.html Если заинтересовало и все получается, то вам дорога на http://ttb.by - соревнования по спортивному программированию в индивидуальном зачете |
xdsl, код решения задачи на freepascal можно увидеть |
На паскале где-то затерялась, а на php - вот
|
Если интересно моё решение:
чтение/запись в стандартный поток ввода/вывода |
Подсобрал наши олимпиадные задачи за пару последних лет и выложил сюда: http://shgpi.edu.ru/scripts/tasks/ |
|
Вы не можете начинать темы Вы не можете отвечать на сообщения Вы не можете редактировать свои сообщения Вы не можете удалять свои сообщения Вы не можете голосовать в опросах Вы не можете вкладывать файлы Вы можете скачивать файлы |