Секция А. Алгоритмические задачи. Факультет радиотехники и кибернетики МФТИ. Московский физико-технический институт. Интернет-портал «Легендарный Физтех»

it2007 В этой секции предлагаются 7 задач на реализацию алгоритмов. Все задачи взяты из реальной жизни, хотя некоторые и имеют на первый взгляд сказочное условие. Для решения задач могут понадобиться не только знания и навыки, полученные в школе, но и дополнительная информация. В этом случае помогут многочисленные книги, Интернет. Не огорчайся, если сразу не сможешь решить задачу. Главное, упорство, терпение и логика мышления.

Для написания программ можно воспользоваться следующими языками программирования: Pascal, C, C++, Java. Программа должна компилироваться в одной из следующих сред:

Turbo Pascal (DOS, Windows): Turbo Pascal v7.0
С/С++ (DOS, Windows): Borland C++ v3.1
C/C++ (Linux): gcc v3.3
Java: jdk-1.5.

Участникам необходимо прислать:

исходный код программ-решений;
пояснения к программам (описание алгоритмов) вместе с доказательством (аргументированными рассуждениями в произвольной форме) корректности применения использованных алгоритмов для решения конкретных задач;
по 5 тестов для проверки работоспособности каждой программы.

Жюри будет проверять работоспособность программ, используя тесты, присланные участниками, и Оргкомитета.

На выполнения каждого теста отводится не более 2 секунд (частота ЦП — 1500МГц). Еще одно ограничение касается запрета на использование так или иначе встроенных числовых типов данных, отличных от byte / char / int / integer / longint / long и float / double / real / single.

В целях облегчения проверки просьба расположить задачи этой секции, согласно следующей структуре директорий:

/<FAMILIA>/ AUTHOR.TXT — личные данные участника,
/<FAMILIA>/SA/<AN>/<LANG>/ PROG.<LANG> — исходный текст программы (он должен быть размещен в 1 файле!),
/<FAMILIA>/SA/<AN>/DOCS/INFO.TXT — описание программы,
/<FAMILIA>/SA/<AN>/<LANG>/TESTS/IN<I>.TXT.

Здесь <FAMILIA> — фамилия участника, записанная латинскими буквами. <AN> - номер задачи (A3 — например), <LANG> — язык программирования (PAS, C, CPP, JAVA), <I> — номер теста (соответственно 0..4).

Программа должна использовать для ввода всех данных файл INPUT.TXT; для вывода — OUTPUT.TXTв директории /<FAMILIA>/SA/<AN>/<LANG>/TESTS/ .

Каждая задача оценивается в 30 баллов: аргументация алгоритма решения — 10; за тестирование: 10 — за тесты, присланные участниками (оценивается как результат выполнения программой данного теста, так и грамотность составления тестов) и 10 баллов за прохождения тестов Оргкомитета. Выполнение дополнительного задания +10 баллов.

вопрос с форума ФРТК (Хоров Евгений [194.85.82.139], 27.11.2006 00:36:56) #
Респект :) начал делать задания, и возник вопрос, можно пользоваться Code::Blocks? А не Borland C++ v3.11? \\ champion ОТВЕТ: Вы можете использовать любую среду для написание решений секции А. Но присланные решения будут компилироваться при помощи соответствующий программ именно перечисленных сред. Если ни в одной из сред программа не будет откомпилирована (либо будет работать некорректно) соответственно за тесты вы получите 0. Так что все же постарайтесь сами проверить корректность программ в соответствующей среды.
Можно использовать тип String? (Лёвин Сергей [85.237.32.116], 12.01.2007 23:07:58) #
Скажите, можно ли использовать в программах тип String (массив символов).
Используемые языки (??? [213.219.212.86], 17.01.2007 23:25:07) #
Скажите, почему нельзя использовать Borland Delphi в режиме консоли?! Чем он хуже других? И почему все пишут на C++ :(
тип String использовать можно (Евгений Хоров [194.85.82.139], 26.01.2007 19:03:17) #
ограничения на численные типы
Ограничение на языки (секция А) связано с тем, (Евгений Хоров [194.85.82.139], 26.01.2007 19:05:24) #
что программа компилируется у нас. А значит надо установить все вохможные компиляторы
лол (Программист [217.67.117.64], 01.02.2007 22:42:08) #
можно пользоваться Code::Blocks? А не Borland C++ v3.11? - интересно как можно заменить компилятор текстовым редактором. Ответ еще более жжот: "Если ни в одной из сред программа не будет откомпилированна" - то есть опять таки программы компилируются средами, а не компиляторами =). Далее:"Скажите, можно ли использовать в программах тип String (массив символов)." - интересно о чем это вообще? ни в одном из языков строка, а тем более класс(а не тип) не является массивом символов =). Смотрим далее: "На выполнения каждого теста отводится не более 2 секунд (частота ЦП — 1500МГц)". Браво! быстродействие процессора охарактеризовали частотой, не гигафлопами в секунду или просто конкретной моделью, а Герцами =)))) Но больше всего меня насмешил способ оценки задач =), за то что программа правильно работает - треть баллов, а две трети за то понравится она или нет не пойми кому.Гагага =)). А если проверяющие, грубо говоря, понимают в программировании меньше сдающего задание(что судя по всему весьма вероятно) то они могут ему баллов и не поставить. Браво!!
Программисту (Хоров Евгений [194.85.82.139], 02.02.2007 13:33:34) #
Очень хотелось бы познакомиться "программистом" - он поймет, о ком я (ICQ 218-20-восемь)
Используемые языки (Вероника [82.209.216.102], 02.02.2007 21:32:37) #
А Free Pascal использовать можно?
прочитайте первый пост (Евгений Хоров [194.85.82.139], 09.02.2007 00:34:20) #
на этой странице
Вопрос о задаче А2 (Вероника [82.209.216.198], 12.02.2007 21:38:03) #
Вопрос о задаче А2. Может ли чиновник потребовать подпись не своего непосредственного подчиненного,а подчиненного своего подчиненного? Не прямого, то есть.
Ответ Веронике (Хоров Евгений [194.85.82.139], 12.02.2007 23:43:18) #
На этот вопрос (задавали вы же судя по имени и ip) уже прозвучал на http://forum.fizteh.ru/rt/m_9o8d/m_9vru.html Поскольку (к сожалению, или к счастью) на вопросы уполномочен отвечать только один человек, сомневаюсь, что здесь ответ будет другой. :)
проверка (Дима [83.174.213.32], 13.02.2007 16:00:23) #
Проверка решений на тестах жюри будет проходить в автоматическом или ручном режимах?
проверка (Евгений Хоров [194.85.82.139], 13.02.2007 20:14:59) #
В автоматическом режиме проверяются все тесты. Плюс просматриваются исходники, тесты и объяснения
Описание алгоритма (Дима [195.22.108.2], 13.02.2007 20:29:55) #
Можно ли описание алгоритма присылать в формате rtf, а не txt?
Оценка (Дима [195.22.108.2], 13.02.2007 21:13:00) #
Будут ли два решения, отличающиеся разной эффективностью по времени выполнения (в асимптотическом пределе) при прочих равных условиях оцениваться одним баллом?
присылайте лучшее решение (Евгений Хоров [194.85.82.139], 14.02.2007 14:28:29) #
эффективность учитываться будет
Оценка (Дима [83.174.209.61], 14.02.2007 19:38:31) #
В таком случае какой вариант будет лучше: более эффективное решение, но без доказательства или менее эффективное, но с полным доказательством?
Официально: без комментариев (Евгений Хоров [194.85.82.139], 14.02.2007 23:48:54) #
неофициально: я бы прислал лучшее и постарался аргументировать что мой алгоритм работает и работает корректно
Еще раз: Описание алгоритма (Дима [83.174.208.30], 15.02.2007 19:44:26) #
Можно ли описание алгоритма присылать в формате rtf, а не txt?
про формат описания (Евгений Хоров [194.85.82.139], 15.02.2007 22:35:31) #
Вообще в правилах /<FAMILIA>/SA/<AN>/DOCS/INFO.TXT — описание программы. Вы считаете необходимым использование rtf? (Это вопрос непринципиальный, поэтому можно только укажите это в INFO.TXT, файл следует назвать INFO.RTF)
Delphi (cSKA [213.135.131.158], 18.02.2007 20:35:16) #
Я может тугодум, но всё таки не панял почему нельзя использовать Delphi. Прошу объяснить (жедательно "на пальцах"). Заранее спасибо. :)
Microsoft Visual C++ (Алексеев Сергей [195.162.44.28], 18.02.2007 22:35:09) #
Почему среди списка компиляторов нет Microsoft Visual C++?! BC - это же не разумно. Программы работают дольше, весят больше, компилятор ругается постоянно... constant range out of 64 kb... да и все люди пишут именно на MSVC, а не на BC. Может организаторы всё-таки изменят список компиляторов? =)
Delphi (Евгений Хоров [194.85.82.139], 18.02.2007 22:38:41) #
Касается только секции А. Вы должны прислать исходный текст программ. Компилировать его будем мы здесь. Следовательно нам надо иметь компиляторы. Поскольку кол-во разлиных языков и их версий велико, мы ограничились несколькими. Delphi в их число не вошло. Почему сы не включили Delphi? Исходили из того что они с Паскалем очень похожи (синтаксисом). Паскаль изучается в школе. Кроме того для решения данных задач не требуются возможности Delphi (Графический интерфейс, мощные библиотеки и т д)
Delphi (cSKA [213.135.131.227], 19.02.2007 19:32:10) #
Для решения задач из делфи не требуется его "графический интерфейс" а его удобство в использовании и его размер памяти. На ряду с C++ и Delphi Pascal ничтожен!
Давайте обсуждать вещи связанные непосредственно с турниром (Евгений Хоров [194.85.82.139], 19.02.2007 23:51:55) #
Паскаль имеет малую функциональность. Тем не менее он идеально подходит для обучения. В том числе чтобы научиться писать ЭФФЕКТИВНЫЕ программы.
Секция А (Master [195.161.25.21], 22.02.2007 13:46:37) #
какой путь указывать к входным и выходным файлам, если пишешь на паскале
пути (Евгений Хоров [194.85.82.139], 22.02.2007 13:54:30) #
http://forum.fizteh.ru/rt/m_9o8d/m_9xda/m_9xed.html
Тесты (Иван [217.24.117.195], 24.02.2007 12:52:11) #
Как делать тесты? Например в А0, делать тесты для короткой последовательности, или для длинной. И в короткой есть несколько вариантов
программа передач (Роберт Хасанов [89.20.115.212], 27.02.2007 02:07:33) #
Я написал решение этой задачи на Free Pascal'е.Решение, я считаю, правильное, но при проверке на Турбо Паскале, мне не хватает памяти отводимой для структурных переменных, и компиляция не проходит.Что в этом случае делать?
память (Евгений Хоров [194.85.82.139], 27.02.2007 16:27:50) #
попробуйте усовершенствовать алгоритм