Версия для печати темы Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > Python: Общие вопросы > Python и участие в олимпиадах по программированию

Автор: pythonwin 12.9.2006, 09:12

albertn,  ты олимпиадник?

Автор: albertn 12.9.2006, 09:45

Цитата(Cr@$h @  12.9.2006,  09:31 ) Здорово. А что за олимпиада, кстати? (вузовская, региональная, ACM и т.п.)  ACM ICPC, NEERC, Southern Subregion IХ ЧЕТВЕРТЬФИНАЛЬНЫЕ СОРЕВНОВАНИЯ ЧЕМПИОНАТА МИРА ПО ПРОГРАММИРОВАНИЮ ЮЖНОГО - ПОВОЛЖСКОГО РЕГИОНА РОССИИ среди сборных команд высших учебных заведений состоятся в г. Саратове на базе Саратовского государственного университета им. Н.Г. Чернышевского с 9 по 13 октября 2006 г. Добавлено @ 09:56  Цитата(pythonwin @  12.9.2006,  09:12 ) albertn,  ты олимпиадник?  Если можно, то немного похвалюсь    Внутривузовские олимпиады: http://www.ncstu.ru/life/paper/2005/664/04.htm/view http://www.ncstu.ru/life/paper/2006/674/14.htm Новочеркасск: http://science.ncstu.ru/achievements/2005_09_23.htm http://science.ncstu.ru/achievements/2006_05_03olymp.htm

Автор: pythonwin 12.9.2006, 11:04

А ФИО у тебя какая?

Автор: albertn 12.9.2006, 11:22

Цитата(pythonwin @ 12.9.2006,  11:04) А ФИО у тебя какая? Помазанов С.Н.

Автор: pythonwin 12.9.2006, 11:31

Цитата(albertn @  12.9.2006,  18:22 ) Помазанов С.Н.  пропиши пожалуйста в своем профиле.  Добавлено @ 11:31  Цитата Победители и баллы 1. Помазанов Сергей, 90, ПМИ-021 2. Сугаков Михаил, 80, ПМИ-011 2. Щербаков Виктор, 80, ИС-031 2. Пивоваров Павел, 80, ИС-021 3. Козлов Илья, 60, ПМИ-011

Автор: Cr@$h 12.9.2006, 11:36

Цитата(pythonwin @  12.9.2006,  12:31 ) Победители и баллы 1. Помазанов Сергей, 90, ПМИ-021 Чувак руляет, поздравляем. ++

Автор: albertn 12.9.2006, 11:40

Цитата(pythonwin @  12.9.2006,  11:31 ) пропиши пожалуйста в своем профиле. Честно говоря я не нашел поле, где бы его адекватно можно было вставить. Цитата(Cr@$h @  12.9.2006,  11:36 ) Чувак руляет, поздравляем. ++ Спасибо PS. Вот последняя олимпиада: Код 1. С. Помазанов (ПМИ-021) — 170 баллов 2. М. Сугаков — 140 баллов 3. С.Емельяненко (БАС-031) — 120 баллов Добавлено @ 11:43  Как обычно Cr@$h и pythonwin повышают репутацию хором. Еще раз спасибо.

Автор: Cr@$h 12.9.2006, 11:50

Цитата(albertn @  12.9.2006,  12:40 ) Вот последняя олимпиада Плюс на все предыдущие распространяется    Цитата(albertn @  12.9.2006,  12:40 ) Как обычно Cr@$h и pythonwin повышают репутацию хором. Еще раз спасибо. Да. Цитата(pythonwin @  12.9.2006,  12:31 ) пропиши пожалуйста в своем профиле.  А у него самого нет  Так что можешь не писать. Цитата(albertn @  12.9.2006,  12:40 ) Честно говоря я не нашел поле, где бы его адекватно можно было вставить. Иногда под Новый Год делается подарок: можно менять подпись под аватаром. Там хоть ФИО свои пиши. А на Python там можно выступать?

Автор: pythonwin 12.9.2006, 12:09

Цитата(albertn @  12.9.2006,  18:40 ) Как обычно Cr@$h и pythonwin повышают репутацию хором. Еще раз спасибо.  Пожалуйста!  За такое дело можно и больше плюсов поставить!

Автор: Cr@$h 12.9.2006, 12:09

M Cr@$h Обсуждение выделил из темы "Преподавание Python в ВУЗах".

Автор: pythonwin 12.9.2006, 12:15

Цитата(Cr@$h @  12.9.2006,  18:50 ) Иногда под Новый Год делается подарок: можно менять подпись под аватаром. Там хоть ФИО свои пиши. Класс! я бы себе поменял бы.

Автор: Cr@$h 12.9.2006, 12:19

Цитата(Cr@$h @  12.9.2006,  12:50 ) А на Python там можно выступать? С темой не знаю что делать: если Python можно использовать на олимпиадах, то тема здесь жить сможет, если нет, то придётся в Разное перенести. Соври, что ли   Кстати, все, наверное, знакомы со стилем олимпиадных задач. Python хорошо бы для них подходил? Давал бы преимущества в скорости написания (там ведь на время и количество всё идёт в конечном счёте). Ну с произвоодительностью отдельный вопрос.

Автор: pythonwin 12.9.2006, 12:25

Цитата(Cr@$h @  12.9.2006,  19:19 ) С темой не знаю что делать: если Python можно использовать на олимпиадах, то тема здесь жить сможет, если нет, то придётся в Разное перенести. Соври, что ли smile  albertn, или просто ничего не говори!

Автор: Cr@$h 12.9.2006, 12:29

Цитата(pythonwin @  12.9.2006,  13:15 ) Класс! я бы себе поменял бы.  Тсс. Это всё серебряным шрифтом. Добавлено @ 12:34  Цитата(pythonwin @  12.9.2006,  13:25 ) albertn, или просто ничего не говори!    Я уже подкинул идею для развития в этой же теме: Цитата(Cr@$h @  12.9.2006,  13:19 ) Кстати, все, наверное, знакомы со стилем олимпиадных задач. Python хорошо бы для них подходил? Давал бы преимущества в скорости написания (там ведь на время и количество всё идёт в конечном счёте). Ну с произвоодительностью отдельный вопрос.  Просто с лаконичностью Python можно намного быстрее эти задачки решать, я считаю. К тому же функцональные языки кто-то видел в таких олимпиадах как разрешённые?

Автор: albertn 12.9.2006, 12:50

Цитата(pythonwin @ 12.9.2006,  12:25) albertn, или просто ничего не говори!  Так уж и быть, промолчу  но честно говоря хотелось-бы Кстати, раз уж зашла эта тема, то меня всегда интерисовал вопрос про применение питона к олимпиадным задачам. В классическом варианте есть входной и выходной файл. Все входные файлы четко структурированны. Но есть одна загвоздка - в нем могут встречаться как числа, так и символы, в зависимости от порядка. В классических языках программирования в этой ситуации нет проблем - открываешь как текстовый файл, а дальше что ему передаешь, то он и считывает. А как в этой ситуации поступать на питоне? Разбивать на элементы разделенные пробелом и переносами строк?  Использовать регулярные вырожения (хотя их применение будет проблемным)? Есть ли какие-либо встроенные функции, аналогичные другим языкам? Чтобы было понятней приведу какой-нить пример: Есть N массивов строк, в каждом массиве Ni cтрок. Строка заканчивается переносом строк. Структура файла такая: N N1 строка1 строка2 ... строка N1 N2 строка1 строка2 ... строка N2 ... ну и пример: Код 3 5 ыфдафыва апдукоедцуопжы ыфа фыдвадфыва фж фы ваодлуодйцу цлйдуадлыфвоадцлуоайо двоыад оцуджа вы 2 ывфд аодлыфво адфывоаж выф дадфыоваж фыва  1 овадф лывадфоывд афывафж Должен же быть какой-то более простой способ прочитать этот файл Добавлено @ 13:04  Цитата(Cr@$h @  12.9.2006,  12:19 ) Кстати, все, наверное, знакомы со стилем олимпиадных задач. Python хорошо бы для них подходил? Давал бы преимущества в скорости написания (там ведь на время и количество всё идёт в конечном счёте). Ну с произвоодительностью отдельный вопрос.  1. В скорости написания у него есть преимущество, но не большое, т.к. есть ява, с которой как я понимаю больше всего конкурирует Python, и у которой есть также от части преимущество в скорости написания. 2. По скорости выполнения он конечно будет уступать таким языкам как C/C++, но обычно в олимпиадах упор на время дается только для построения правильного алгоритма, так что должно прокатить. 3. По памяти могут быть проблемы. Честно говоря я не исследовал этот параметр, но построеные выражения обычно создают несколько списков, а не изменяют исходный. К тому-же сборщик мусора может не всегда сработать там где надо. А так все подходит

Автор: Cr@$h 12.9.2006, 13:12

M Cr@$h Тема: Python и участие в олимпиадах по программированию. Всё ликвидо теперь. Беседуем. Добавлено @ 13:23  Цитата(albertn @  12.9.2006,  13:50 ) По скорости выполнения он конечно будет уступать таким языкам как C/C++, но обычно в олимпиадах упор на время дается только для построения правильного алгоритма, так что должно прокатить. Там обычно последний тест -- как раз на скорость дают. Часто заваливает. Цитата(albertn @  12.9.2006,  13:50 ) По памяти могут быть проблемы. Честно говоря я не исследовал этот параметр, но построеные выражения обычно создают несколько списков, а не изменяют исходный. К тому-же сборщик мусора может не всегда сработать там где надо. А вот память не слышал, чтобы в тестах проверяли. А так у них там сервак стоит какой-нить. Так что здесь ещё ничего может на олимпиадах.

Автор: Void 12.9.2006, 19:51

Цитата(albertn @  12.9.2006,  14:50 ) 1. В скорости написания у него есть преимущество, но не большое, т.к. есть ява, с которой как я понимаю больше всего конкурирует Python, и у которой есть также от части преимущество в скорости написания. Java слишком многословна в алгоритмических задачах, которые обычно предлагаются на олимпиадах. Цитата(albertn @  12.9.2006,  14:50 ) 2. По скорости выполнения он конечно будет уступать таким языкам как C/C++, но обычно в олимпиадах упор на время дается только для построения правильного алгоритма, так что должно прокатить. 3. По памяти могут быть проблемы. Честно говоря я не исследовал этот параметр, но построеные выражения обычно создают несколько списков, а не изменяют исходный. К тому-же сборщик мусора может не всегда сработать там где надо. На мой взгляд, как раз наоборот. Питон отстаёт в скорости от C++ в среднем на порядок, поэтому правильный, но не «вылизанный» алгоритм с той же асимптотикой может пролететь. А вот потребление памяти отличается не так сильно и рамки обычно задают чисто символические, так что при минимальной аккуратности в реализации выйти за них трудно. Кстати, на http://www.google.com/codejam/ Python есть в списке доступных языков.

Автор: PyS 12.9.2006, 21:07

Цитата(Void @  12.9.2006,  22:51 )  Питон отстаёт в скорости от C++ в среднем на порядок для тех кто не знает - на порядок это в 10-ть раз!

Автор: Void 12.9.2006, 21:38

Цитата(PyS @  12.9.2006,  23:07 ) для тех кто не знает - на порядок это в 10-ть раз!  У программистов — может быть ещё и в два раза  А может в e? Знаю, что в десять, и именно эту цифру имел в виду. Шустрики проводить будем? Интерпретатору байт-кода без JITа с нативно компилируемым языком не тягаться, это бессмысленно даже обсуждать. Для затравки: http://shootout.alioth.debian.org/debian/benchmark.php?test=all&lang=python&lang2=gcc (знаю, знаю, более дурацких бенчмарков, чем на этом сайте, в природе нет, но и такого широкого охвата тоже нигде не найти). Исключение: можно получить даже некоторое превосходство в программах, большую часть времени проводящих в функциях стандартной библиотеки, например, dict vs std::map или длинная арифметика Питона vs самопальная.

Автор: Cr@$h 12.9.2006, 23:15

Цитата(Void @  12.9.2006,  20:51 ) Java слишком многословна в алгоритмических задачах, которые обычно предлагаются на олимпиадах. Да, я тоже присоединяюсь к этому высказыванию. Иногда за дебрями синтаксиса можно и суть потерять. Плюс Python позволяет фнуциональный стиль, а это, батеньки, декларативное программирование, как мы все прекрасно знаем. Тут все преимущества и так понятны. Тем не менее в индустрии Java заняла прочные позиции и её синтаксис, объектная концепция пришлись весьма по вкусу программистам Цитата(Void @  12.9.2006,  20:51 ) Питон отстаёт в скорости от C++ в среднем на порядок, поэтому правильный, но не «вылизанный» алгоритм с той же асимптотикой может пролететь. В 10 раз это не сильно. Если алгоритм построен правильно и имеет сложность на O(N!), а O(N^10), то такие мелочи не повлияют на ход теста сильно, и он пройдёт успешно (про тест на олимпиадах говорю). Цитата(Void @  12.9.2006,  20:51 ) А вот потребление памяти отличается не так сильно и рамки обычно задают чисто символические, так что при минимальной аккуратности в реализации выйти за них трудно. Возможно, но в С++ её можно полностью контролировать, а Python любит копии списков плодить (уже говорили). Цитата(Void @  12.9.2006,  22:38 ) Исключение: можно получить даже некоторое превосходство в программах, большую часть времени проводящих в функциях стандартной библиотеки, например, dict vs std::map или длинная арифметика Питона vs самопальная.  Да, это факт. С другой стороны, сопосталяя с Java, в последней очень серьёзно представлены различные структуры данных. Это её козырь, без сомнений. Мы так и не выяснили: функциональные языки допускают на российских олимпиадах? И ещё один возник из этого обсуждения: разрешено ли использовать стандартные библиотеки? Я в первую очередь здесь имею в виду Java с её структурами. Или есть какие-нибудь ограничения?

Автор: Void 12.9.2006, 23:45

Цитата(Cr@$h @  13.9.2006,  01:15 ) С другой стороны, сопосталяя с Java, в последней очень серьёзно представлены различные структуры данных. Например? Открываю доку и смотрю содержимое java.util.*: списки, связанные списки, множества, словари, очереди. В Питоне это всё есть, кроме связанного списка (довольно быстро изображается вручную) и словарей/множеств с гарантированным порядком элементов (тут согласен, быстро и эффективно не напишешь, а иногда нужно). Цитата(Cr@$h @  13.9.2006,  01:15 ) И ещё один возник из этого обсуждения: разрешено ли использовать стандартные библиотеки? Я в первую очередь здесь имею в виду Java с её структурами. Или есть какие-нибудь ограничения?  Есть очевидные ограничения на I/O и прочие системные функции, связанные с безопасностью, но про ограничения на алгоритмы и структуры данных не слышал ни разу. Цитата(Cr@$h @  13.9.2006,  01:15 ) Возможно, но в С++ её можно полностью контролировать, а Python любит копии списков плодить (уже говорили). Не встречался с тем, чтобы это делалось скрытно от программиста. Т.е., вызывая какую-либо функцию, обычно имеешь чёткое представление, работает она in-place или создаёт копию. Я повидал олимипдного кода на C++, написаного чудовищно неэффективно (передача std::string по значению и т.п.). Питон позволяет достичь сопоставимых результатов при существенно меньшем количестве нюансов, которые надо знать. По моему скромному опыту на ICPC, ограничения на память обычно завышены относительно разумных требований гораздо больше, чем время выполнения, так что превысить их надо постараться. Цитата(Cr@$h @  13.9.2006,  01:15 ) В 10 раз это не сильно. Если алгоритм построен правильно и имеет сложность на O(N!), а O(N^10), то такие мелочи не повлияют на ход теста сильно, и он пройдёт успешно (про тест на олимпиадах говорю). Сильно зависит от конкретной задачи. Я могу представить ситуацию, когда при идентичных алгоритмах код на C++ впишется в рамки, а на Питоне — нет.

Автор: Cr@$h 13.9.2006, 00:30

Цитата(Void @  13.9.2006,  00:45 ) В Питоне это всё есть, кроме связанного списка (довольно быстро изображается вручную) и словарей/множеств с гарантированным порядком элементов (тут согласен, быстро и эффективно не напишешь, а иногда нужно). Да, это из той же серии: иногда в библиотеках реализованы полезные вещи  Цитата(Void @  13.9.2006,  00:45 )  про ограничения на алгоритмы и структуры данных не слышал ни разу. Я имел в виду, может, хоть на java всё есть, просят самим всё руками писать, чтобы в равных условиях все были -- только язык вибирай, а дальше без готовых таких структур. Цитата(Void @  13.9.2006,  00:45 ) Питон позволяет достичь сопоставимых результатов при существенно меньшем количестве нюансов, которые надо знать. В точку. Цель не оправдывает средства (или даже наоборот тоже верно будет). Цитата(Void @  13.9.2006,  00:45 ) Цитата(Cr@$h @  13.9.2006,  01:15 ) Цитата В 10 раз это не сильно. Если алгоритм построен правильно и имеет сложность на O(N!), а O(N^10), то такие мелочи не повлияют на ход теста сильно, и он пройдёт успешно (про тест на олимпиадах говорю). Сильно зависит от конкретной задачи. Я могу представить ситуацию, когда при идентичных алгоритмах код на C++ впишется в рамки, а на Питоне — нет.  Хорошо, что там может тормозить так? Интерпретируемость? У Java в этом смысле проблем поменьше, там разработчики стараются над каждой версией оптимизировать. И если дело в этом, есть ли реализации Python для байт-кода? Типа JRuby, что ли.

Автор: Void 13.9.2006, 00:57

Цитата(Cr@$h @  13.9.2006,  02:30 ) Я имел в виду, может, хоть на java всё есть, просят самим всё руками писать, чтобы в равных условиях все были -- только язык вибирай, а дальше без готовых таких структур. Я понял, просто несколько неудачно выразился  Именно про ограничения на использование стандартных библиотек не слышал. STL использовали без ограничений, чем Java хуже. Цитата(Cr@$h @  13.9.2006,  02:30 ) Хорошо, что там может тормозить так? Интерпретируемость? У Java в этом смысле проблем поменьше, там разработчики стараются над каждой версией оптимизировать. Java может JIT-компилироваться. Питон — только интерпретируется. Цитата(Cr@$h @  13.9.2006,  02:30 ) есть ли реализации Python для байт-кода? http://www.jython.org/. Но, во-первых, в смысле языка Jython остановился на уровне CPython 2.1. Во-вторых, использование байткода JVM вместо байткода виртуальной машины Питона не означает автоматическое улучшение производительности. Питон — динамический язык, и для его эффективного исполнения нужны значительные усилия по анализу кода, выводу типов и оптимизации. Я сам Jython не использовал, так что было бы интересно, если бы кто-то просветил по поводу его быстродействия относительно CPython и Java.

Автор: Cr@$h 13.9.2006, 01:16

Цитата(Void @  13.9.2006,  01:57 ) STL использовали без ограничений, чем Java хуже. Тогда full trottle! Цитата(Void @  13.9.2006,  01:57 ) Java может JIT-компилироваться. Питон — только интерпретируется. Именно это и позвроляет ей работать "чуть" быстрее.   Цитата(Void @  13.9.2006,  01:57 ) Я сам Jython не использовал, так что было бы интересно, если бы кто-то просветил по поводу его быстродействия относительно CPython и Java.  Присоединяюсь. И мне интересно. Возможно, по скорости он "прилично" быстрее Python. Конечно, мы это из разговора об олимпиадах и применению на них (быстрого/небыстрого) Python вывели. Может, подспорье будет... Цитата(Void @  13.9.2006,  01:57 ) Но, во-первых, в смысле языка Jython остановился на уровне CPython 2.1. Вот это жалко. Возможно, не прижился таки. Своя машина и так есть. Добавлено @ 01:17  Приветствую Void в обсуждении. Что так заходишь поздно? Дел, наверное, много. У тебя какое местное время было?

Автор: albertn 13.9.2006, 09:02

Мда ну и написали за время моего отсутствия! Ладно, начну по порядку. Любая задача может делиться на несколько категорий, таких как память, скорость, алгоритм и смешанные. Про память: Ну допустим есть такая простая задачка. есть 1000000 чисел от 0 до 100. Памяти разрешено 2 Мб. Уместит ли питон такой массив в том количестве памяти? На сколько я понимаю любые функции функционального программирования пораждают новые списки, что может сильно использовать память. Но в случае чего можно не полагаться на сборщик мусора, и самим отчищать использованную память. Про скорость: Основная загводзка скорости будет состоять в обработке списков, или переборе. В первом случае у питона есть встроенные функции, написанные на си, так что с этим особых проблем может и не быть, а перебор можно таким-же образом перевести в списковую структуру, и его обрабатывать. К тому-же есть множества, разрешающие использовать чуть ли бесконечное количество элементов. Про ограничения на программу: Цитата(Void @  12.9.2006,  23:45 ) Есть очевидные ограничения на I/O и прочие системные функции, связанные с безопасностью, но про ограничения на алгоритмы и структуры данных не слышал ни разу. Кроме перечисленных ограничений, могут также встречаться и алгоритмические ограничения, но это в основном на классические языки. Как например, чтобы код программы умещался в 200 символов, или программа должна быть линейной.  Есть такой классический пример - надо отсортировать массив положительных чисел, причем программа должна быть линейной. Для питона еще могли бы сделать ограничение, что нельзя пользоваться функцией sort, множествами и любыми логическими операциями. Цитата(Void @  12.9.2006,  23:45 ) Сильно зависит от конкретной задачи. Я могу представить ситуацию, когда при идентичных алгоритмах код на C++ впишется в рамки, а на Питоне — нет.  В любой олимпиаде организаторы заранее говорят, что программу можно написать на любом предоставленном языке, и она может пройти все тесты. Цитата(Cr@$h @  13.9.2006,  00:30 ) Я имел в виду, может, хоть на java всё есть, просят самим всё руками писать, чтобы в равных условиях все были -- только язык вибирай, а дальше без готовых таких структур. Бред. Если посмотреть, то даже у си есть такие библиотеки как vector и algorithm, в которых очень многое реализованно. Добавлено @ 09:07  Цитата(Cr@$h @  12.9.2006,  23:15 ) Мы так и не выяснили: функциональные языки допускают на российских олимпиадах? Возможно есть, но это олимпиады не широкого масштаба. Я несколько встречал, в которых допустимых языков было достаточно много. На ACM разрешено использовать только 3 - Pascal (Delphi), C++ (Visual C++.NET), Java. Но в финале уже убрали паскаль, т.е. оставили всего два языка. Так что надежда на появление там питона ОЧЕНЬ мала.

Автор: PyS 13.9.2006, 10:11

Цитата(albertn @  13.9.2006,  12:02 ) Ну допустим есть такая простая задачка. есть 1000000 чисел от 0 до 100. Памяти разрешено 2 Мб. Уместит ли питон такой массив в том количестве памяти? проверил на скорость: Код import profile profile.run('range(0, 10**6, 1)')          4 function calls in 0.066 CPU seconds    Ordered by: standard name    ncalls  tottime  percall  cumtime  percall filename:lineno(function)         1    0.040    0.040    0.040    0.040 (range)         1    0.000    0.000    0.000    0.000 (setprofile)         1    0.026    0.026    0.066    0.066 <string>:1(?)         0    0.000             0.000          profile:0(profiler)         1    0.000    0.000    0.066    0.066 profile:0(range(0, 10**6, 1)) Как проверить на использумую память?

Автор: Cr@$h 13.9.2006, 12:37

Цитата(albertn @  13.9.2006,  10:02 ) Для питона еще могли бы сделать ограничение, что нельзя пользоваться функцией sort, множествами и любыми логическими операциями. Да, но раз Цитата(albertn @  13.9.2006,  10:02 ) Если посмотреть, то даже у си есть такие библиотеки как vector и algorithm, в которых очень многое реализованно. то я бы разрешал всё. Если Python помогает лучше решать олимпиадные задачи, то пускай другие языки пеняют на себя.

Автор: albertn 13.9.2006, 12:55

Кстати, я ошибся, в той программе могут быть всего 2 цикла, а все остальное линейно и без логических операций. Кому не слабо, пусть попробует выложить. Естестно на питоне, и чтоб все честно было.

Автор: Artemios 13.9.2006, 13:31

Цитата(albertn @  13.9.2006,  09:02 ) Есть такой классический пример - надо отсортировать массив положительных чисел, причем программа должна быть линейной. Для питона еще могли бы сделать ограничение, что нельзя пользоваться функцией sort, множествами и любыми логическими операциями. Цитата(albertn @  13.9.2006,  12:55 ) Кстати, я ошибся, в той программе могут быть всего 2 цикла, а все остальное линейно и без логических операций. Не понял, сам смысл сортировки же это расположение некоторого множества элементов в соответствии с некоторым порядком, определенным на элементах. А порядок - это функция, определенная для пар элементов, возвращающая логическое значение. С другой стороны, если все завязано на положительности и целых чисел, как элементов упорядочиваемого множества, так все равно, можно попытаться завязать на проверке равенства нулю в ходе ряда действий, что также есть логическая операция... Эх, старею что-то

Автор: Void 13.9.2006, 18:36

Цитата(albertn @  13.9.2006,  11:02 ) Кроме перечисленных ограничений, могут также встречаться и алгоритмические ограничения, но это в основном на классические языки. Как например, чтобы код программы умещался в 200 символов, или программа должна быть линейной.  Какой-то школьный уровень, право слово  Однако придётся поверить, что и такое встречается. Цитата(albertn @  13.9.2006,  11:02 ) В любой олимпиаде организаторы заранее говорят, что программу можно написать на любом предоставленном языке, и она может пройти все тесты. Во-первых, мы рассматриваем гипотетический случай, поскольку о реальном применении Питона на олимпиадах пока никто не сообщил. Во-вторых, на упомянутом Google Code Jam было открыто сказано, что некоторые задачи возможно нельзя будет решить на Питоне из-за ограничений по времени выполнения. Цитата(albertn @  13.9.2006,  11:02 ) На сколько я понимаю любые функции функционального программирования пораждают новые списки, что может сильно использовать память. Так кто заставляет использовать Питон, как чисто функциональный язык? Цитата(albertn @  13.9.2006,  11:02 ) Ну допустим есть такая простая задачка. есть 1000000 чисел от 0 до 100. Памяти разрешено 2 Мб. Уместит ли питон такой массив в том количестве памяти? Массив — уместит (см. модуль array). Но в ограничения не впишется, потому что только его рантайм займёт сразу после загрузки программы существенно больше памяти.

Автор: dvska 13.9.2006, 20:48

Цитата(Void @ 13.9.2006,  00:57) Я сам Jython не использовал, так что было бы интересно, если бы кто-то просветил по поводу его быстродействия относительно CPython и Java. Пробовали, тестировали. Тормоз он. К тому же мёртвенький практически...    А жаль.

Автор: albertn 14.9.2006, 13:32

Цитата(Artemios @  13.9.2006,  13:31 ) Не понял, сам смысл сортировки же это расположение некоторого множества элементов в соответствии с некоторым порядком, определенным на элементах. А порядок - это функция, определенная для пар элементов, возвращающая логическое значение. С другой стороны, если все завязано на положительности и целых чисел, как элементов упорядочиваемого множества, так все равно, можно попытаться завязать на проверке равенства нулю в ходе ряда действий, что также есть логическая операция... Эх, старею что-то smile Основной упор в задаче идет на то, чтобы отсортировать 2 числа без использования логики. Дам легкую подсказку, что сортировка несет за собой математическую основу. Мне один тип предложил такую идею, что надо сделать нулевой массив большой размерности, и забить каждое значение как индекс массива, а затем просто вывести все по порядку. Но все-же решение не рациональное, и не правильное.

Автор: Void 14.9.2006, 20:45

Цитата(albertn @  14.9.2006,  15:32 ) Основной упор в задаче идет на то, чтобы отсортировать 2 числа без использования логики. Код def sort_two_numbers(a, b):     lesser = (a + b - abs(a - b)) / 2     bigger = a + b - lesser     return lesser, bigger Поскольку в Питоне есть длинная арифметика, для целых чисел это будет работать всегда (для действительных имеем возможную потерю точности).

Автор: Artemios 15.9.2006, 05:54

Я вроде тоже сначала примерно также подумал: Код # даны a,b c = (a+b)/2 d = abs(a-b)/2 a1 = c-d b1 = c+d Только ведь в abs используется операция сравнения

Автор: Artemios 15.9.2006, 07:00

Цитата(Artemios @  15.9.2006,  05:54 ) Только ведь в abs используется операция сравнения Сорри, слишком математически смотрел на задачу  В машинной арифметике же достаточно сбрасывать в 0 знаковый бит не в зависимости от того, какой он был изначально. Только вот как знаки, и соответственно abs, реализованы в длинной арифметике питона - пока не интересовался

Автор: albertn 15.9.2006, 12:27

Void, ну теперь то уже все готово осталось только написать полный код программы, что не составит труда. Задачка то в принципел легкая, только приходится хорошо подумать головой. PS Void, +1

Автор: Cr@$h 15.9.2006, 18:22

Цитата(Artemios @  15.9.2006,  06:54 ) Только ведь в abs используется операция сравнения  Используется в ней.. и то возможно. Если не разрешено пользоваться логическими операциями, то не значит, что нельзя использовать другие функции. Так, если посмотреть, логические операции будут использоваться в большинстве функций.   Void, руляет.

Автор: albertn 18.9.2006, 09:48

Цитата(Cr@$h @  15.9.2006,  18:22 ) Используется в ней.. и то возможно. Если не разрешено пользоваться логическими операциями, то не значит, что можно использовать другие функции. Так, если посмотреть, логические операции будут использоваться в большинстве функций. Ну я бы так не сказал. Если углубиться в этот вопрос, то на асме логической операцией считается та, которая следит за сменой флагов. Все арифметические операции, как и взятие модуля хоть и изменяют эти флаги, но не следят за их изменением.

Автор: Artemios 18.9.2006, 10:39

Цитата(albertn @  18.9.2006,  09:48 ) Ну я бы так не сказал. Если углубиться в этот вопрос, то на асме логической операцией считается та, которая следит за сменой флагов. Все арифметические операции, как и взятие модуля хоть и изменяют эти флаги, но не следят за их изменением.  Ну а если опять посмотреть математически, то любое машинное действие - есть операция над битами, то бишь реализация булевой алгебры, синоним коей алгебра логики

Автор: albertn 18.9.2006, 11:31

Цитата(Artemios @ 18.9.2006,  10:39) Ну а если опять посмотреть математически, то любое машинное действие - есть операция над битами, то бишь реализация булевой алгебры, синоним коей алгебра логики  Ну если так посмотреть, то все что у нас просисходит - это просто совокупность элементарых частиц, подчиняющихся одним и тем-же законам  А если серьезно, то как-раз арифметические операции считывают только состояние регистров и памяти, а логические операции к тому-же считывают флаги состояний. Вообще операции AND, OR, NOT ... по-сути чисто математические. А уже < > <= >= == != .. чисто логические. В принципе получается что AND, OR, NOT ... можно было-бы применять, но их прменение влечет за собой применение логических операций или функций, что в задаче не разрешено. Ну так что, никто не хочет предоставить полный вариант программы? Ладно, уж напишу. Не ругайте сильно за пузырька  Код a = [2,43,5,6,4,3,4,6,78,9,7,5,34,56,7,78,6,43,3,6,7,43,23,8,7,5,3,2,4,5,65,78,89,897,65,54,34,4,5,56,65,7,4,7,89] for i in range(len(a)):     for j in range(len(a)-1):         m = (a[j] + a[j+1])/2.0         l = abs(a[j]-m)         a[j] = int(m-l)         a[j+1] = int(m+l) print a

Автор: Artemios 18.9.2006, 11:53

Цитата(albertn @  18.9.2006,  11:31 ) Ну если так посмотреть, то все что у нас просисходит - это просто совокупность элементарых частиц, подчиняющихся одним и тем-же законам А что, процесс мышления уже формализовали?

Автор: albertn 18.9.2006, 12:01

Цитата(Artemios @  18.9.2006,  11:53 ) А что, процесс мышления уже формализовали? Пару миллионов строчек кода осталось на питоне   А про циклы ты это имел ввиду? Цитата(albertn @  13.9.2006,  12:55 ) в той программе могут быть всего 2 цикла

Автор: Artemios 18.9.2006, 12:03

Сорри, невнимательно смотрел твой код, свою глупость удалил Добавлено @ 12:07  Цитата(albertn @  18.9.2006,  11:31 )  for j in range(len(a)-1): for j in range(len(a)-i-1)

Автор: Cr@$h 18.9.2006, 12:26

Цитата(albertn @  18.9.2006,  10:48 ) Ну я бы так не сказал. Если углубиться в этот вопрос, то на асме логической операцией считается та, которая следит за сменой флагов. Все арифметические операции, как и взятие модуля хоть и изменяют эти флаги, но не следят за их изменением.  Да неправильно написал я  Хотел сказать: Если не разрешено пользоваться логическими операциями, то не значит, что нельзя использовать другие функции. Цитата(Artemios @  18.9.2006,  11:39 ) Ну а если опять посмотреть математически, то любое машинное действие - есть операция над битами, то бишь реализация булевой алгебры, синоним коей алгебра логики  А уж если посмотреть на логические схемы, то там одни логиеские операции и есть практически  Цитата(albertn @  18.9.2006,  12:31 ) Вообще операции AND, OR, NOT ... по-сути чисто математические. А уже < > <= >= == != .. чисто логические. Думаю, имелось в виду, что нельзя использовать логические операции в привычном смысле слова. Цитата(Artemios @  18.9.2006,  12:53 ) А что, процесс мышления уже формализовали?  О, куда может привести разговор оп олимпиадах на Python   Ещё раз извините, что выше неправильно выразился (можно/нельзя).

Автор: Artemios 13.10.2006, 16:42

Итак, завершилась олимпиада в Саратове, в которой принимала участие команда  albertn. Ставропольские ребята заняли 10-е место и теперь в числе 10-ки пебедителей поедут на полуфинал в Питер. Не могу не похвастаться: 1,2,3 места заняли команды Саратовского гос. университета.

Автор: pythonwin 16.10.2006, 08:09

Цитата(Artemios @  13.10.2006,  23:42 ) 1,2,3 места заняли команды Саратовского гос. университета.smile Artemios, можно вопрос? в комисии по подготовке проведения олимпиады были люди которые готовили Саратовских студуентов к олимпиаде?

Автор: Artemios 16.10.2006, 10:14

Цитата(pythonwin @  16.10.2006,  08:09 ) в комисии по подготовке проведения олимпиады были люди которые готовили Саратовских студуентов к олимпиаде? Честно говоря, не знаю - не интересовался, ты лучше у albertn спроси. Если же намекаешь, что свои своим подтасовали, то вспомни, кто стал победителем на последнем чемпионате мира по программированию, проходившем далеко не в Саратове, и не в России.

Автор: pythonwin 16.10.2006, 10:59

Если же намекаешь, что свои своим подтасовали, то вспомни, кто стал победителем на последнем чемпионате мира по программированию, проходившем далеко не в Саратове, и не в России.  1) подтасовать - это врятли.  2) могли просто "правильно" подготовить, хотя если бы поймали, то позора ... 3) кто победил на чемпионате мира по программированию не знаю 4) моя практика участия в олимпиадах такова - "правильная" подготовка есть на небольших олимпиадах (районные, городские, областные), а вот выше - уже нет - ставка выше!

Автор: Artemios 16.10.2006, 11:27

Цитата(pythonwin @  16.10.2006,  10:59 ) кто победил на чемпионате мира по программированию не знаю Команда Саратовского государственного университета  Цитата(pythonwin @  16.10.2006,  10:59 ) вот выше - уже нет - ставка выше! Так был-то четвертьфинал чемпионата мира  Добавлено @ 11:31  А вообще мы отвлеклись, надо б albertn-а поздравить.

Автор: albertn 16.10.2006, 11:34

Наконец-то я приехал домой. Теперь смело могу принимать поздравления  Саратов - это действительно сильные комманды (их было 10). Их действительно готовят, причем очень серьезно. У них есть даже центр подготовки. Если посмотреть то нас никто никогда не готовил, разве что изредка мы сами себя готовили. Кстати я слегка поковырялся, и нашел тестирующую систему по олимпиадным заданиям, и нашел реализацию на питоне.

Автор: DeadLine 5.2.2007, 13:13

Питон официально не является олимпиадным языком программирования

Автор: Void 5.2.2007, 16:15

DeadLine, ты имеешь в виду, на каких-то конкретных соревнованиях? Или как ещё понимать твои слова?

Автор: pythonwin 6.2.2007, 06:56

Цитата(DeadLine @  5.2.2007,  16:13 ) Питон официально не является олимпиадным языком программирования  почему? любая школа, техникум или ВУЗ могут провести у себя "внутреннюю" олимпиаду на питоне

Автор: slav0nic 6.2.2007, 11:59

http://www.python.com.ua/forum/viewtopic.php?id=369 правда как я понял, она сейчас закончилась, но в 2007 году наверно будет

Powered by Invision Power Board (http://www.invisionboard.com)
© Invision Power Services (http://www.invisionpower.com)