Елена Андреева

Советы участникам соревнований :-)

1. Состав команды

Для слаженной работы команды во время олимпиады по программированию и достижения максимально возможного результата рекомендуется формировать команду в следующем составе:

а) "Диктатор", он же капитан команды, он же генератор идей, по темпераменту - желательно сангвиник или флегматик. Решения, принимаемые капитаном во время тура, не подлежат обсуждению и выполняются немедленно. Хорошо также, если "диктатор" будет полностью осведомлен о круге задач, который близок по духу тому или иному члену команды, об их интеллектуальных способностях и скорости машинописи на языке Computer English.

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

Сгенерировав ту или иную идею, "диктатор" отдает ее на доработку наиболее подходящему для достижения этой цели "члену команды".

б) "Реализатор", он же секретарь-машинистка, он же гениальный мгновенный воплотитель своих и чужих идей, холерик по темпераменту. Главная его задача - не подпускать во время тура других членов команды к клавиатуре компьютера. Неплохо, если "реализатор" сможет сразу и без посторонней помощи запрограммировать самую легкую задачу, предоставив тем самым своим товарищам время подумать над остальными задачами. Хороший "реализатор" способен с полуслова стенографировать в терминах известного ему языка программирования бредовые идеи остальных членов команды, попутно доводя эти идеи до ума.

в) "Сомневающийся", он же главный "тестер" (не путать с тостером), лучше, если он же является главным математиком команды, по темпераметру - меланхолик. Его предназначение - внимательно изучать условие задачи, которая в данныый момент набивается и/или отлаживается "реализатором", и придумывать исчерпывающий набор тестов, на котором созданную программу необходимо проверить. Желательно, чтобы система тестов содержала все вырожденные и критические случаи, а также, чтобы ответы на предложеные тесты были "сомневающемуся" несомненно известны. Главная линия поведения "тестера" - все время сомневаться в правильности программы, созданной совместными усилиями команды, и желанть эту программу на чем нибудь "подловить". Если ему это ни разу не удастся, то можно начать сильно сомневаться в качестве самого тестера, и, следовательно, программа будет "поймана" жюри, что ведет в к негативным последствиям, а именно - к увеличению штрафного времени даже при окончательном благоприятном исходе для данной программы. На совести "сомневающегося" - также контроль педантичности следования "реализатора" формату входных и выходных данных, поскольку за "реализаторами" данное качество замечается весьма редко, да еще въедливые вопросы для жюри по поводу различных нюансов в формулировках задач (в понимании условий всегда лучше переесть, чем недоспать).

Примечание. Если к моменту изучения данного руководства команда уже была неосмотрительно сформирована и исправлять что-либо в составе участников поздно, то, в случае равномерного распределения перечисленных выше качеств среди членов команды, они могут во время тура изменять свои роли путем циклического сдвига во время перехода от решения одной задачи к другой. Например, "реализатор" отлаживает первую задачу, "диктатор" думает над второй, "сомневающийся" пишет тесты для первой, а после успешной сдачи первой задачи, бывший "диктатор" воплощает свои мысли по второй задаче на компьютере, бывший "сомневающийся" думает над третьей задачей, а освободившийся "реализатор" становится тестером по задаче номер два.

2. Подготовка к соревнованиям

Желательно, чтобы подготовка к соревнованиям проходила в течение как минимум двух-трех лет, предшествующих олимпиаде, причем без существенных перерывов, в том числе и на обед, так как спортивная форма имеет обыкновение утрачиваться. Хорошую форму позволяет поддерживать участие во Всероссийских и Международных личных и командых состязаниях для школьников и студентов по информатике, сетевых олимпиадах, межвузовских и внутривузовских командных соревнованиях по программированию. Последние можно проводить практически еженедельно (недельный перерыв между соревнованиями необходим для того, чтобы наиболее сознательные участники смогли наконец-то решить задачи, предлагавшиеся на предыдущей олимпиаде). Кроме того, чтобы необходимые для решения задач на олимпиаде алгоритмы не стали откровением во время тура, члены команды все вместе или каждый по отдельности должны знать курс высшей математики (включая линейную и не только алгебру, математический анализ, теорию вероятностей, аналитическую и неаналитическую геометрию и т.д. и т.п.), булевскую алгебру, теорию графов, курс численных методов, методы решения задач оптимального управления и исследования операций.

Неплохо также ознакомиться с теорией построения трансляторов, компьютерной геометрией, алгоритмами сортировки и поиска, классом NP-полных задач, программированием различных комбинаторных конфигураций, методом backtracking, методом ветвей и границ, динамическим программирование, а также решить проблему распознавания образов путем написания программы для собственного сканера. Логическим завершеним теоретической подготовки к соревнованиям является составление программы для игры комьпютера в преферанс с одним или двумя пользователями или какой-либо другой более сложной с точки зрения разрабоки компьютерной стратегии игры, диcассемблирование и изучение компилятора с любимого языка программирования, а также просто игра в MINESWEEPER, но не в DOOM.

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

Если же во время подготовки к соревнованиям у вашей команды возникло ощущение всемогущества или мания величия, то ни в коем случае не следует заранее обсуждать, как лучше распорядиться будущими призами. Практика показывает, что в этом случае призы достанутся вашим соперникам.

3. Стратегия и тактика повединия во время тура

Цель: создать у жюри иллюзию о решении вами как можно большего количества задач путем подгона программ под заданную систему тестов.

Средства: в достижении указанной цели все средства хороши.

1) При внимательном рассмотрении текстов "правильных" программ, решающих олимпиадные задачи, несложно убедиться, что в них довольно много общего. Поэтому, в самом начале тура "рeализатор" должен набить следующую универсальную программу, особое внимание обратив на директивы компилятора (текст программы приведен на языке TURBO-PASCAL, если вы программируете на C++, то переведите его на ваш "иностранный язык" заранее, записав дословный перевод на листе бумаги):

{$A+,B-,D+,E+,F+,G-,I+,L+,N+,O-,R+,S+,V+,X+}
{$M 65520,0,655360}
var i, j, k: integer;
procedure readdata;
var f: text;
    a: longint;
begin
  assign (f,'INPUT.TXT');
  reset (f);
  while not seekeof (f) do read (f, a);
  close (f)
end;
procedure outdata;
var g:text;
begin
  assign (g, 'OUTPUT.TXT');
  rewrite (g);
  close (g);
end;
procedure initial;
begin
end;
procedure run;
begin
end;
BEGIN
   readdata;
   initial;
   run;
   outdata;
END.

Обратите внимание, что программа получилась работающая. То есть ее можно запускать на выполнение, и при наличии в текущей директории файла INPUT.TXT (даже пустого) все должно быть в порядке. Далее необходимо скопировать эту программу столько раз, сколько задач вам предлагается на туре, называя каждый полученный файл так, как это требуется по условиям соревнований. Ну вот, теперь у вас все задачи уже решены, хотя и в первом приближении. Теперь дело за малым - постараться не испортить эти работающие программы в процессе добавления к ним новых кусков. Ведь лучшее - враг хорошего!

2) Пока "реализатор" занимается "решением" всех задач одновременно, остальные члены команды знакомятся с текстами предложенных задач и "диктатор" должен принять решение - какая задача будет программироваться первой, какая второй и кто именно этим будет заниматься. Выкрики остальных членов команды: "Я, я, я знаю как решается эта задача, да я ее за пять, две или даже одну минуту решу", должны приниматься только к сведению, а не как руководство к немедленному действию. В большинстве случаев первой должна программироваться задача, для решения которой требуется написать самую маленькую программу, и, следовательно, ошибок в которой должно быть меньше. Во вторую очередь следует заняться разработкой текста программы для очевидной и легкой (на первый взгляд) задачи, программирование которой заключается во внимательном учете всех возможных случаев, и требует некоторой техники реализации пришедших в голову идей.

3) Если вы приступили к решению задачи (сразу на компьютере или без него), внимательно прочитайте ее условие и постарайтесь правильно (!!!) понять, в чем заключается задача. Если есть хоть капля сомнения, в том числе и по форме ввода-вывода, то лучше немедленно задать вопрос жюри, а не членам своей или соседней команды. Член команды, который в данный момент не допущен до клавиатуры "диктатором", должен обязательно записывать текст программы для решаемой задачи на бумаге (столе, стуле, ладони и т.п.), даже если в голове у него уже есть готовые конструкции будущей программы. Во-первых, если вылить содержимое вашей головы на бумагу, то путем пристального взгляда вам наверняка удасться его улучшить (все улучшения также должны быть произведены в письменном виде), а, во-вторых, набивать текст программы, какой бы ясной для вас она не была, в 1,5 - 3 раза быстрее с бумаги, чем из головы.

4) Рекомендации по процессу практического программирования олимпиадной задачи:

а) завершить программирование процедуры readdata ввода данных, согласно требованиям решаемой задачи;

б) в процедуре initial следует обнулить или присвоить соответствующие начальные значения всем (!!!) глобальным переменным;

в) сделать вывод результата в процедуре outdata так, как это требуется в условии задачи, это поможет дальнейшей отладке программы и не потребуется потом "простой" вывод переделывать в "правильный" (в процессе отладки имя выходного файла можно заменить на CON, тогда не придется каждый раз открывать выходной файл для просмотра результатов работы программы); в результате вы будете иметь все еще "работающюю" программу, она по-крайней мере должна компилироваться, считывать данные и выводить результат, пусть и нулевой;

г) запрограммируйте решение задачи в виде вызовов процедур и функций, которые пока следует описать в виде заглушек (мнимого или пустого действия или имитации настоящего действия, которое должна выполнять ваша программа); так вы можете отладить логику вашей программы, оставляя ее "работающей".

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

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

5) И вот, наконец, "реализатор" завершил свою работу по программированию очередной задачи (вернее думает, что завершил). Теперь главным действующим лицом становится "сомневающийся", который к этому своему звездному часу (или минуте) уже должен подготовить исчерпывающую систему тестов, которая и позволит "сомневающемуся" показать некомпетентность "реализатора". Если же данная система тестов не поставила "реализатора" в тупик и позволила ему быстро устранить все мелкие ошибки в решении задачи, то, прежде чем окончательно cоздавать exe-файл, замените следующие директивы компилятора: D-,I-,L-,R- и скорректируйте размер стека. Постарайтесь запустить полученный *.exe файл из DOS хотя бы для одного теста, чтобы убедиться в работоспособности программы не только в среде программирования, а затем еще раз перечитайте условие: а ту ли задачу вы решали? Если никакие сомнения не омрачают радостную атмосферу в вашем временном трудовом коллективе, то "диктатор" может дать команду отправить вашу программу на растерзание жюри и команда может приступить к реализации следующей программы, текст которой в идеале уже существует в письменном виде.

6) Как бороться со штрафным временем

Любую, даже самую опытную команду, может постигнуть неудача при тестировании ее программы жюри. Если тестирующая программа оказалась недовольна форматом вывода или не прошел один из первых тестов, чаще всего связаный с вырожденными случаями (например, нулями и единицами), то "диктатор" может позволить "реализатору" вернувшейся программы исправить ошибки, если они очевидны, прервав при этом решение следующей задачи. Если же не прошел один из последних тестов или превышено время тестирования, то следует усомниться в оптимальности алгоритма и даже в его правильности. В этом случае, разрешать ошибшемуся "реализатору" немедленно исправлять задачу не рекомендуется ни в коем случае: пусть сначала на бумаге разработает план изменения программы или убедится, что он это сделать не в состоянии. Недостаток работы "сомневающегося" в этом случае также очевиден. Он должен постараться дополнить свои тесты новыми, в том числе и "большими". Ситуация несколько упрощается, если ответом на любые входные данные должно быть одно из двух указанных в тексте задачи слов. Например, "correct" или "incorrect". В этом случае следует лишь добиться, чтобы ваша программа выдавала ответы всегда в одном и том же порядке при запуске ее на одной и той же последовательной системе тестов (вопрос, как это сделать, оставим открытым, чтобы описанные ниже злоупотребления не оказались на совести автора данного руководства). Тогда, если вам было указано, что неверным является ответ на тест 3, то следует изменить третий элемент в последовательности ответов на противоположный и т.д. Так как с вероятностью 1/2 вы будете выдавать правильные ответы на тесты, то из 8 тестов вам останется исправить ответы всего в четырех (в худшем случае пяти) тестах, то есть достаточно послать вашу программу жюри 5 раз и без труда заработать еще одну зачтенную задачу, хотя и с большим штрафным временем.

7) Как потратить последние 15 минут тура. Так как перед смертью все равно не надышишься, а результаты соревнований практически уже всем известы, в том числе и вашей команде, "диктатор" должен помочь всей своей команде сконцентрироваться и довести до результата одну из "не совсем правильно" решенных задач. Конечно, если это еще возможно. В этом случае команда сможет максимизировать количество полученных баллов. И наоборот, роковой ошибкой является доработка каждым из членов команды "своей задачи".

4. Как вести себя после тура

Однозначно ответить на этот вопрос невозможно. Все зависит от того, выиграли вы соревнования или проиграли.

1) Линия поведения для победителей. Во-первых, ни в коем случае нельзя зазнаваться и вообще дразнить судьбу, так как в победах на олимпиадах есть и доля случайности (рекомендуется как-нибудь отблагодарить судьбу, которая на этот раз была к вам благосклонна). Во-вторых, надо дорешать те из предложенных задач, которые все-таки не покорились вам во время тура, и тщательно проанализировать почему это произошло: не хватило времени, знаний, умений и чего-либо еще и постараться устранить недостатки в вашем коллективе до следующих соревнований. И главное, теперь требуется не терять набранную к данному туру спортивную форму (см. пункт 2 настоящего руководства).

2) Линия поведения проигравших. Если вы не выиграли данные соревнования, то, значит, неверно выполняли рекомендации п. 1-3 настоящего руководства, так что придется перечитать их еще раз и сконцентрироваться на исправлении допущенных ошибок. Кроме того, любой проигрыш всегда относителен. Возможно, есть команды, набравшие еще меньше баллов, чем вы. А может, вы сумели решить на туре задачу, подобных которой в вашей практике еще не было, тогда данные соревнования можно рассматривать как собственную победу. Но, вероятно, данные соревнования помогут вам более объективно оценить свои способности и возможности, что тоже немаловажно. Как говориться, важна не победа, а участие. Надеюсь, что данные соревнования не окажутся для вас последними, а данное руководство позволит на высоком уровне подготовиться к следующим.

Как стать чемпионом мира по программированию или разбор полетов

Эта книга написана для будущих чемпионов мира по программированию. На ее написание нас подвигли собственные неудачи в данном вопросе, и мы решили поступить по принципу; кто может - делает, кто не может - учит. Авторы были первыми, кто участвовал в чемпионате мира по программированию от Уральского государственного университета. К сожалению, мы не можем сказать о себе "мы были первыми", а всего лишь "мы были восьмыми", но мы были там, мы "нюхали порох", и очень хочется, чтобы накопленный опыт не пропал, а обогащался из года в год.

Идея книги была подсказана оргкомитетом регионального этапа чемпионата мира, который проводится АСМ -Association for Computing Machinery - с 1977 года. Только в 1996 эти соревнования докатились до Урала. Члены оргкомитета, состоявшего из москвичей и петербуржцев, выпустили некую аналогичную брошюру. Внимательно ее проанализировав, авторы определили непригодность этой брошюры для большинства команд страны в качестве руководства по подготовке. Не подлежит сомнению, что и наш опус будет полезен не каждому. Чтобы читателю было легче разобраться, для него или не для него эта книга, мы постараемся как можно чаще приводить обоснования наших утверждений или хотя бы примеры из жизни, заставившие нас думать так, как мы пишем.

Мы надеемся, что материал, изложенный в этой книге мог бы стать подспорьем многим вузам Урала и Сибири при подготовке своих команд. Серьезное отношение к такой подготовке не только принесет пользу студентам-участникам в плане изучения компьютерных наук и программирования, выработки дисциплинированности и умения действовать в команде (качество, ценность которого стали осознавать даже современные российские менеджеры), но и поможет сделать хоть какие-то шаги в устаревшей, на наш взгляд, позиции дистанцирования Москвы и Санкт-Петербурга от так называемой "периферии"-остальной части России. Одной из целей, которую мы ставили, было показать, что даже такое не слабое дело, как победа на чемпионате мира, может быть по плечу тем, кого столичные преподаватели не считают себе конкурентами.

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

Авторы также выражают глубокую личную благодарность Алексею Руфимовичу Данилину за общие ценные указания и снабжение литературой, декану математикомеханического факультета УрГУ Магазу Оразкимовичу Асанову и ректору университета Владимиру Евгеньевичу Третьякову - за всемерное содействие в подготовке команды, Хасану Салмановичу Сумгаипову, Анатолию Васильевичу Макарову и Областному комитету по делам молодежи - за поддержку, которая и сделала вообще возможной нашу поездку в Санкт-Петербург.

1. Осознание себя как команды

1.1. Вступительные общие слова

Тезис: три идеальных программиста, случайно собравшиеся в одном месте в одно и тоже время, представляют собой более слабую команду, чем та, в которой и вовсе может не быть "звезд", но которая специально тренировалась. Иллюстрацией этого утверждения может служить задача о поджаривании бифштексов. Пусть задана сковорода, на которой может быть размещено от нуля до четырех бифштексов. Каждый бифштекс в произвольный момент времени может быть положен на сковороду, удален с нее или перевернут (бифштекс имеет две стороны). Требуется поджарить шесть бифштексов за минимальное время. Бифштекс считается поджаренным, если он обжаривался в течение 15 минут с каждой стороны. Решение: жарим четыре бифштекса с одной стороны,затемдва переворачиваем, а два полуподжаренных заменяем на два сырых, затем два уже готовых убираем, два оставшихся переворачиваем и докладываем два, отложенных прежде. Итого уходит 45 минут. Этот результат недостижим, если бифштексы не будут работать как единая команда, а каждый будет стараться поджариться независимо от других. Заметим, что членам этой "команды" приходилось для получения оптимального результата проделывать не совсем "естественные" действия-уходить со сковороды недожаренными. Как ни проста эта задача, она демонстрирует важность наличия между членами команды некоторых дополнительных мотивов действий, отличающих команду от простой группы лиц. Несколько утрируя идею, ее можно выразить такой поговоркой.

Интересы сковороды важнее интересов бифштекса.

В оригинале данного труда, находящегося на www-страницах Уральского государственного университета, Санкт-Петербург и петербуржцы именуются соответственно Ленинградом и ленинградцами. По-видимому, из-за дальности расстояний до Екатеринбурга еще не дошла весть о том, что в 1991 году по результатам референдума городу было возвращено его первоначальное имя. Одновременно с возвращением своего исторического названия, совпавшим по времени с освобождением цен, Санкт-Петербург потерял все свои льготы, существовавшие во времена построения коммунизма и дававшие основания числить его столичным городом. Таким образом в настоящее время "материально-денежная" дистанция между СанктПетербургом и другими российскими городами свелась к нулю, а между СанктПетербургом и Москвой стала "дистанцией огромного размера" В связи с вышеизложенным оргкомитет и жюри посчитали возможным вернуть и в данном труде Санкт-Петербургу и его жителям их исконные исторические названия, но оставить городу красивое прилагательное "столичный" в связи с существующим в настоящее время у администрации Санкт-Петербурга намерения попросить у правительства вместо денег звания культурной столицы России.

У игрока команды постоянно возникает выбор: браться за ту или иную работу самому, поручить ее другому или вообще не выполнять эту работу в силу ее ненужности в данной ситуации. Однозначных рекомендаций для того, чтобы сделать этот выбор, мы не знаем. Один из способов облегчить себе жизнь - договориться заранее, кто какую работу будет выполнять и какая работа будет считаться ненужной. Сформулировав такие общие критерии, команда обезопасит себя от проблемы выбора во время тура. При этом возникает другая проблема. Чтобы не рассуждать и при этом не ошибаться, формальные критерии выбора должны быть установлены чрезвычайно точно и одинаково поняты всеми участниками. Если круг задач, которые предполагается решать, широк, то такие критерии едва ли могут быть записаны, и вместо них используются упрощенные критерии, оставляющие, с одной стороны, определенную свободу выбора, а с другой, дающие ответ во многих ситуациях. Проводимые тренировки позволяют игрокам накопить опыт в принятии подобных решений, в результате чего команда начинает представлять из себя единое целое. Набор правил, помогающих принимать решения по поводу своих и чужих действий, будем далее называть стратегией. Стратегия подобна таблице умножения - не решая проблемы в целом, она подсказывает ответ в простых ситуациях.

Не знаешь, что делать - вспомни стратегию. Не помнишь стратегию - полагайся на опыт.

Далее рассмотрим известные нам стратегии, выделяя у каждой плюсы, минусы и отмечая, для каких команд более всего подходит та или иная стратегия.

1.2. "Три мудреца в одном тазу..."

Сразу после старта каждый участник выбирает себе задачу, с которой в состоянии справиться, и начинает решать ее на своем листочке. Выбравший себе самую простую задачу может решать ее сразу на компьютере. Для своей задачи каждый игрок сам придумывает тесты, осуществляет отладку и сдачу. После отсылки задачи на проверку в жюри участник за компьютером меняется, освободившийся игрок выбирает себе новую задачу, и так далее.

Достоинством стратегии является то, что все простые задачи будут решены. Как показывает опыт, иногда этого бывает достаточно для победы. Далее, когда двое участников будут решать две последние простые задачи, третий игрок уже освободится и сможет обдумывать более сложную. Освободившись, к нему может подключиться второй, а при необходимости и третий участник, так что оставшееся после решения простых задач время команда может варьировать, чтобы в соответствии со своими возможностями решить еще одну или две задачи.

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

Во-первых, все три участника должны виртуозно владеть всеми стадиями программирования - от написания формальной постановки до завершающего тестирования. Во-вторых, затягивая решение своей задачи, игрок задерживает еще сразу две другие задачи, то есть каждая минута простоя (придумывание тестов, дополнительная отладка после неудачных попыток сдать задачу) умножается как минимум на три. Наконец, так как нет конкретного человека, принимающего решения о распределении работ, команда может (и часто так и бывает) попасть в цейтнот-идея о консолидации сил для "добивания" одной, последней, задачи появится слишком поздно и пропадут впустую усилия двоих игроков, решавших каждый свою задачу.

Кроме того, стратегия предполагает существенные накладные расходы при любых попытках взаимопомощи: человек, занятый (или который только что был занят) решением собственной задачи, часто не в состоянии перебороть инертность мозга и переключиться на другую задачу.

Один за всех и все за одного.

В целом, стратегия кажется разумной для трех "звезд"-игроков, каждый из которых владеет программированием во всех стадиях и дополнительно имеет хорошую математическую подготовку. Виртуозное владение техникой программирования и математическим аппаратом дадут команде большое преимущество и позволят успешно выступить, если команда обладает также высокой коммуникабельностью. Но команды, сочетающие в себе все перечисленные качества, встречаются редко.

1.3. "Столичная" система

Такое название стратегия получила потому, что была впервые в России опубликована в информационной методичке регионального этапа чемпионата мира по программированию АСМ членом жюри Е.В.Андреевой из Московского государственного университета.

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

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

Недостатком такой схемы является чрезвычайно большая ответственность, которая ложится на диктатора. На нем - стыд или слава за все принятые решения, как по решению задач, таки по распределению работ. Человек, принимающий на себя обязанности диктатора, должен быть весьма волевым, обладать большим личным опытом участия в олимпиадах. Но даже если такого человека удалось отыскать (а это не так просто), каждая его ошибка будет сокрушительным ударом по собственной команде. А ведь помимо решения задач, в том числе математических, на диктаторе лежит ответственность за оценку стоимости разработки тех или иных идей. Когда задачи, посланные в жюри, начнут возвращаться незачтенными, ему придется экстренно решать, как с ними быть - продолжать отладку сейчас или отложить, прерывать решение текущей задачи или ставить возвращенную задачу "в очередь" Помимо перечисленного, такая тактика предполагает в целом последовательное решение задач. Последовательный подход безусловно оправдан, когда речь идет о простых задачах - таких, где на разработку алгоритма уходит 10-15 минут. Эти задачи следует решать за минимальное время и затраты на организацию параллельных работ в любом виде едва ли окупятся. Однако, параллельное решение может оказаться выгодным для задач, требующих 1,5-2 человеко-часов. Данный же подход не предусматривает распараллеливания, кроме как на капитана и двух других членов.

Кадры решают все!

Итак, стратегия является весьма подходящей (возможно, близкой к идеальной) для команд, имеющих ярко выраженного опытного лидера. Как уже было отмечено выше, такие лидеры встречаются не столь часто. Попытка же использовать такую стратегию в "ровной" команде часто обречена, так как ошибки капитана сведут на нет все старания его помощников.

1.4. "Вместе весело шагать..."

Для контраста хочется привести еще пример-антипод для стратегии, где каждый решает свою задачу. Можно, наоборот, решать все задачи вместе, начиная с простых и постепенно переходя к сложным. При этом возникнет естественное ролевое распределение игроков внутри одной задачи. Участники будут последовательно выполнять этапы реализации задачи, как они себе их представляют. Нет нужды говорить, что игроки такой команды обязаны процесс программирования представлять себе одинаково.

Недостатки стратегии явно видны: потери времени при решении задач никем не контролируются и могут принимать большие размеры. Параллельная работа над разными задачами отсутствует, что снижает общее число решенных задач. Кроме того, неконтролируемые временные потери ухудшают штрафное время.

Тем не менее, стратегия имеет и ряд достоинств, о которых не следует забывать тем, кто разрабатывает "лучшие" стратегии. Во-первых, за время всего тура, скорее всего, будут решены все простые задачи, и при этом команда достаточно застрахована как от ошибок в определении простоты задач, таки от ошибок отдельных игроков, поскольку отдельные ошибки имеют высокую вероятность исправления другими членами команды. Во-вторых, наработка взаимопонимания, достаточного для применения такой стратегии, требует весьма малого количества тренировок. лишь бы команды была бы "спаяна" достаточно крепко. В-третьих, для формирования этой команды вообще не требуются "звезды" - асы в программировании и математике.

Логика, простота и ясность - три кита производства.

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

1.5. "Сумасшедшее (безумное) чаепитие"

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

Команда должна быть дружной и иметь высокий уровень коммуникабельности. Ничто не приносит столько бед, как прохладный психологический климат. Вместе с тем, каждый человек индивидуален, не похож на других и ему приятно, если для реализации себя, в том числе и на соревнованиях, у него есть своя ниша. Тем самым высказана мысль, что люди, объединенные в одну команду, вполне могут обладать разными талантами. Для команды нам потребуется один ярко выраженный математик, один такой же программист и один участник, в более или менее равной степени владеющий обоими ремеслами. Поясним чуть подробнее.

Математик призван видеть абстрактную суть вещей. Его стихия - обобщать, выписывать рекуррентные формулы, дифференцировать, доказывать оценки численных методов, получать функции общего члена, подсчитывать число сочетании и порядок сходимости, брать первообразные и первые интегралы, работать алгебраическими методами над геометрическими фигурами и наоборот, выполнять дополнительные построения, применять разностные схемы. Его место там, где волшебная палочка математического аппарата превращает грозное условие в послушную двухпараметрическую игрушку. Он способен сделать бесконечное число шагов за ничтожное время, написав формулу суммы ряда или ортогонализацию Грама-Шмидта. Произведения, суммы, цепные дроби, векторная алгебра, геометрические методы-да разве можно перечислить весь его арсенал.

Программист являет собой в некотором смысле противоположность математику. Он мыслит конкретно, его сырье - графы, цепи, циклы, очереди, стеки, массивы, списки, деревья, правила вывода, ветвления, потоки, файлы. Также, как и у математика, его вселенная необъятна и абстрактна, но каждая ее деталь подразумевает конкретное воплощение. Это огромная мастерская. Стоит программисту определить, какой инструмент ему нужен, и начинается сборка, и вот уже слышно веселое жужжание новорожденного механизма. Там, где математик видит нечто, ни на что не похожее, или где с его губ падает слово "тривиально", программист может найти по горло работы. Виртуоз отладки, гений трансляции-программист понимает каждое движение курсора, каждые машинный "вздох" и паузу не хуже, чем восклицания и плач партнеров. В душе каждый программист немного хакер, но он старательно скрывает в себе это качество и может даже выучить наизусть теорию матроидов, если ему скажут, что это всего лишь объекты, двойственные графам.

Наконец, третий участник команды, "мастер на все руки" или "связной," принимает на свои плечи всю тяжесть непосредственного решения задач. Несмотря на то, что могучий дуэт математика и программиста способен смести горы на своем пути, оба они могут потерять немало груза из-за крошеной дыры в рюкзаке, забыть завтрак внутри при сворачиваний палатки и т.п. Когда они разрабатывают железнодорожное полотно, для них не существуют отдельные рельсы, болты и гайки. Программист виртуозно выполнит стальную магистраль, но первые же пассажиры могут никуда не доехать, ибо на семафоре не будет предусмотрено переключение сигнала, а на станциях-открывание дверей.

Иначе говоря, творцы часто считают слишком многие вещи само собой разумеющимися, а железная болванка "Intel" не всегда способна простить им это. "Практик" кует железо, из которого потом рождаются строки кода под умелыми руками программиста, он спускает на землю написанные без разбиения на строки математические формулы, наконец, одна из самых важных его миссий-он позволяет математику не отвлекаться на "ЕРУНДУ" вроде составления тестов. И последнее: если программист в команде устанет и его мозг и пальцы перестанут действовать идеально согласованно, и еще в некоторых критических ситуациях практик способен сеть за штурвал-клавиатуру и спасти судно.

Помимо перечисленных личностей, в команде должен быть капитан - игрок, пользующийся среди друзей наибольшим доверием. Его функции, дополнительные к прямому назначению, будут описаны чуть позже. Пока отметим лишь, что желательно, чтобы капитан не был программистом, так как эта стратегия не предполагает знакомства программиста со всеми задачами, а это либо снижает компетентность решений капитана, либо требует дополнительных затрат на знакомство программиста с задачами.

После старта ближайшая цель команды - разделаться с простыми задачами. Следует однако понимать, что при том разделении труда, которое описывается, простые задачи никогда не будут решены за минимально возможное время и скорее всего найдется команда, сдавшая эти задачи раньше. Не нужно горевать об этом. Нужно побеждать общим числом задач, или даже штрафным временем, но на следующем уровне. Чтобы этого достичь, необходимо минимизировать время простоя отдельных игроков. В соответствии с этой целью программист немедленно начинает набивать общий шаблон: ввод, обработка, вывод. Он же несет обязанность немедленной отладки шаблона, так как ошибку в шаблоне придется исправлять многократно. В силу того, что применение описываемой тактики требует существенного числа тренировок, программист, как правило, будет знать искомый шаблон наизусть к началу соревнований. Еще раз подчеркнем, что, кроме специально оговоренных ниже случаев, никто не должен лезть за клавиатуру. Компьютер - дом программиста, и никого больше.

В то время, как программист занимается набором шаблона, математик и практик изучают условия задач. Цель этого изучения - обеспечить программиста и практика двумя самыми простыми задачами. Самая простая задача выдается программисту. Обычно есть сомнения, и, когда простые задачи отделены, их список с минимальными комментариями представляется практиком программисту, и тот выбирает себе самую простую задачу. Следующая по простоте задача передается практику, который на более или менее низкоуровневом псевдоязыке излагает с ходу ее решение. Пока практик и программист занимаются описанным процессом выбора двух задач, математик определяет следующую по простоте задачу и принимает решение: оста вить ее двум другим игрокам или взять себе. Нет однозначного рецепта для любой ситуации. Главное, что должен обеспечить математик своим решением - минимизацию времени простоя. К тому моменту, когда программист закончит свою задачу, практик уже составит к ней некоторые тесты. В то время, как программист далее будет тестировать свою задачу, а потом разбираться с задачей практика, практик должен иметь возможность приступить к третьей задаче. Это может быть либо никем не тронутая простая задача, либо математическая задача, разобранная математиком по косточкам, либо более сложная задача. Последняя ситуация соответствует случаю, когда простых задач не осталось, и математик собирается поменяться с практиком местами, после того как участь первых двух задач будет решена.

В общем и целом, математик должен обеспечить практику задание, не пересекающееся с собственной работой математика на момент окончания решения первой задачи. Поскольку на решение одной задачи не мобилизуются все силы команды, то на первую (самую простую) задачу может быть затрачено времени даже в полтора раза больше, чем при использовании двух предыдущих стратегий. Однако, надо отдавать себе отчет, что эта задача должна быть решена несколько быстрее, чем за час.Эта фраза имеет ввиду, что к такому времени нужно стремиться на тренировках, но нет никакого смысла убиваться по -этому часу на самих соревнованиях.

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

По-видимому, наиболее разумным будет оставить за программистом решение, будет ли он самостоятельно реализовывать данный ему алгоритм или воспользуется помощью автора. Возможно, программист решит набрать часть алгоритма самостоятельно и воспользоваться помощью товарища при наборе остальной части программы.

Итак, процесс пошел, осталось его поддерживать. Необходимость поддержания возникает не всегда, а когда решена очередная задача. Назовем такой момент точкой выбора, если до конца тура осталось более двух часов, и критической точкой, если менее 70 минут. В диапазоне 80-110 минут такая точка может быть как точкой выбора, так и критической - в зависимости от того, какие задачи остались, сколько решено и какие находятся в разработке. Решение о том, является ли точка критической или нет, должен принимать капитан.

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

Если точка является критической и освобождается один игрок, то он по решению капитана либо присоединяется к решению задачи, находящейся в разработке, либо берется за прописывание в псевдокоде задачи с ясным алгоритмом. В этот же момент может быть принято решение об использовании эвристики.

Отметим, что наряду с отсеиванием простых задач для решения в первую очередь жизненно необходимо выделять также сложные задачи, которые решать вообще не планируется. Новая задача ни при каких условиях не может быть выбрана из этого "черного списка", если хоть одна из других задач еще находится в разработке.

Если точка является критической и освободились двое участников, то капитан принимает решение либо добивать оставшуюся в разработке задачу, либо попытаться решить еще одну.

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

Описанная выше ситуация плоха по многим причинам. Во-первых, программист настроен на набивание текста, отладку, работу за компьютером, и внезапное перемещение его на роль составителя алгоритмов не способствует улучшению производительности команды. Во-вторых, программиста придется "вводить в курс дела", рассказывать ему условие и варианты решений, над которыми ведется работа, а это опять-таки потеря драгоценного времени. И в-третьих, компьютеру команды-один, и он является достаточно важным, если не важнейшим ресурсом, которым владеет команда, и поэтому простой компьютера крайне нежелателен.

В общем и целом, данная стратегия направлена на минимизацию простоя, на постоянное решение задач, имеющих реальные шансы быть завершенными до финального свистка.

Описанная стратегия, как и остальные, имеет много плюсов и минусов. Наиболее важный плюс: разделение труда не только ролевое, но и функциональное, что позволяет минимизировать простой без яркого "лидера" Наиболее важный минус: нет шансов на победу, если команда не смогла решить хотя бы одну или две задачи из списка "более сложных" Такая стратегия при решении только простых задач проигрывает по штрафному времени всегда.

Начав тренировки по данной стратегии, любая команда довольно быстро найдет оптимизирующие изменения, которые позволят более эффективно работать именно этой команде. Поэтому нет смысла далее подробно прописывать "программу" действий отдельных игроков. То, что было хорошо для первых команд УрГУ, совсем не обязательно будет приемлемо для всех остальных.

Давайте передвинемся - мне нужна чистая чашка!

Условное название стратегии выбрано из-за того, что "освободившийся" игрок поступает как типичный мартовский заяц: ищет относительно чистую чашку.

1.6. "Предохранитель"

Еще одна ролевая стратегия, являющаяся разновидностью предыдущей. В окружающем нас мире многие любят заниматься одним (и только одним) делом. Поэтому часто существенно сложнее отыскать хорошего "практика", чем математика или программиста. Предлагаемая к рассмотрению методика предлагает один из вариантов решения этой проблемы.

Рассматриваемая стратегия выделяет в команде одного математика и двух программистов. Кроме того, один из членов команды является капитаном. Сразу после старта каждый из программистов получает по простой задаче. Методы выбора простых задач могут быть различны.

Например, каждый может читать с разных концов до простой, или один садится набивать шаблон, а двое читают и т.п. Во всяком случае, эта тема достаточно подробно обсуждалась выше и ничего нового в этот момент стратегия не вносит. Далее одна задача набирается, а другая параллельно готовится. При этом математик служит как бы "центром", хозяйственной частью команды. Он занимается составлением тестов, помогает каждому из программистов в изобретении алгоритма, при необходимость проводит оценки времени, пишет решения и алгоритмы для задач на бумаге. Программисты регулярно обращаются к нему за помощью, тестами и консультациями.

Отличительная особенность поведения такой команды -смена операторов во время тура. Каждый программист ведет "свои" задачи. Такой подход имеет и плюсы, и минусы. Плюсы: облегчение загрузки программиста. Не каждый способен выдержать пять часов напряженной работы за терминалом без потери производительности, внимательности, сообразительности. А такая потеря дорого обходится: это и снижение эффективности использования компьютера, и проблемы в конце тура, когда бывает чрезвычайно важно сдать еще одну задачу. Здесь же каждый программист "предохраняет" другого, позволяет ему немного отдохнуть. Другое преимущество: локализуется ответственность за сдачу конкретной задачи. То есть математика курсе событий, он способен квалифицированно охарактеризовать ситуацию в критически момент, и в то же время за каждую задачу отвечает конкретный программист.

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

Подчеркнем, что каждому участнику здесь всегда есть чем заняться, то есть простоя как такового не происходит. Если программист не занят на машине, он составляет тесты, в том числе может помочь в составлении тестов партнеру, если необходимо "сменить рубашку"

Пусть он в связке в одной с тобой - там поймешь, кто такой.

В целом, работа происходит "попарно" - каждый программист с помощью математика сдает очередную задачу. Команда как бы состоит из четырех человек, в чем имеется тоже некоторое преимущество.

1.7. Еще немного общих слов

Повторим важную мысль, уже высказывавшуюся выше -для конкретной команды, скорее всего, ни одна из перечисленных стратегий не будет идеальной. Нужно отобрать то, что наиболее подходит для вашей команды, из каждой стратегии и составлять собственную.

Однако, неверно поступать так: на нескольких тренировках пробовать то одно, то другое. Результаты реально зависят от большого числа факторов, а не только от выбранной стратегии, и после проведения этих тренировок команда окажется не в лучшем положении, чем до них.

Терпение, плюс характер!

2. Некоторые технические детали

Помимо выработки стратегии общего поведения, есть много относительно "небольших" вопросов, возникающих при реализации любого общего подхода. Далее изложены некоторые мысли по соответствующим ситуациям.

Мелочи обходятся нам дороже потому, что мы меньше о них думаем.

2.1. Использование программы "монитор"

"Монитор" - это программа, предназначенная для просмотра текущих результатов других команд во время тура. Монитор - это спасение и головная боль тренеров и руководителей команд, с трепетом наблюдающих за его показаниями в продолжение соревнований. Однако, использование монитора участниками имеет и положительные, и отрицательные аспекты.

К положительным моментам относится помощь в распознавании простых и сложных задач. Анализ того, какие задачи пытались решать лидеры, сколько попыток сдач зафиксировано среди первой десятки по той или иной задаче, может оказать немалую помощь в выборе очередной задачи для решения. Показания монитора очень часто - верный критерий сложности задачи. В результате его просмотра команда сэкономит ресурсы, которые могли бы быть брошены на решение или исследование сложности "безнадежных" задач, правильнее определит очередность решения других задач.

Отрицательной стороной является сильный психологический шок, который испытывает человек, видя текущее положение своей команды в турнирной таблице. У команды может возникнуть стремление сделать что-то быстрее, догнать и перегнать, часто приводящее, наоборот, к снижению производительности. Угнетающее воздействие, которое производит монитор на команду тем опаснее, что его крайне трудно, если вообще возможно, смоделировать на тренировках.

Один из вариантов решения проблемы состоит в том, чтобы просматривать монитор после получения сообщения от жюри о засчитывании очередной задачи, начиная со второй. В этом случае помощь монитора при выборе очередной задачи может оказаться вполне реальной, а результаты работы команды будут, по крайней мере, не хуже при очередном просмотре по сравнению с предыдущим.

Два раза сдай - один посмотри.

Если при просмотре команда увидит себя в верхней части таблицы, то эффект также может быть двояким. С одной стороны, прилив сил, с другой, -невольное желание расслабиться, посчитать, что победа уже близка, что главное сделано.

2.2. Отсечение созданных тестов

Часто в процессе тестирования принимают участие два и более членов команды, а за клавиатурой находится только один из них. При этом часть тестов может создавать ему трудности при наборе (большой объем, сложные расчеты, необычный формат ввода) и в то же время проверять лишь один из параметров программы (скажем, запас длины массива), в котором он уверен и без того. В этом случае оператор может отсечь такие "неудобные", "невыгодные" тесты, чтобы сберечь время. Он делает это на свою ответственность. Никто не пожалеет его, когда команда в результате проиграет из-за подобной ошибки, но такой подход экономит время, тоже необходимое как воздух.

Почувствуй ответственность.

2.3. Замена оператора за терминалом

Разные люди имеют обыкновение по-разному создавать программы. Они используют различную структуру отступов, стили описания типов и генерации имен переменных. У каждого есть свой любимый метод реализации быстрой сортировки или создания двусвязного списка.

Вследствие описанного эффекта смена оператора в команде влечет наличие расходов на подстройку среды программирования и исходного текста под его вкус. Обычно не приносит хороших результатов попытка написать программу одним человеком, а отладить другим. Однако, не каждый способен интенсивно и эффективно работать в продолжение пяти часов. Резонным компромиссом кажется ведение каждой задачи одним оператором, но для разных задач операторы могут различаться.

Каждой задаче - своего оператора.

2.4. Отсечение простых и сложных задач

Разделение задач на простые и сложные необходимо, об этом говорит простая арифметика. Пусть время на решение простой задачи составляет t минут, а на решение сложной - Т минут. Если обе задачи будут последовательно решены без "холостых заходов", то на этой уйдет (t+T) минут. При этом, если команда начнете простой задачи, то ее штрафное время составит (2*t+T) минут, а если со сложной, то (t+2*T) минут. Кроме того, сложные задачи как правило приносят команде больше штрафного времени за неудачные попытки, и, если пытаться решать их на ранней стадии, то это время войдет во все последующие результаты.

Едва ли можно указать исчерпывающую методику разделения задач на простые и сложные. Попытаемся лишь выделить приемы, используемые более или менее часто.

Для решения одних задач алгоритм решения очевиден. Для решения других требуется предварительная разработка математического аппарата - вывод рекуррентных формул, дифференцирование, получение численных формул, комбинаторный подсчет, дополнительные построения и прочее. Будем называть задачи этих двух типов соответственно "программистскими" и "математическими" Как правило, олимпиадные программистские задачи проще математических - в силу того, что многие участники "руками" знакомы с используемыми структурами данных и приемами использования этих структур. Однако, несомненно, можно придумать программистскую задачу, которая требует для своего решения больше времени, чем математическая, так что это правило - не панацея.

Рассмотрим далее отдельно решение математических и программистских задач. В решении математических задач многое зависит от правильного определения темы, на которую составлена задача. По разным темам разработаны многочисленные советы, методы и приемы, собранные в обширных руководствах по математике. Отошлем по этой части читателя к изданным сборникам задач по алгебре и геометрии, математическому анализу и просто олимпиадным задачам на логику мышления.

Что касается программистских задач, то ориентиром часто может служить порядок перебора. Порядки подразделяются таким образом: факториал - экспонента - степень - куб - квадрат - n*lоg(n) - линейный - логарифм. Обычно сложнее задача, имеющая более высокий порядок перебора. Это правило также имеет исключения. Одно из наиболее очевидных-переборная задача, для решения которой годится алгоритм Форда-Беллмана, может быть реализована быстрее, чем задача, где "побеждает поиск в ширину или в глубину, но нужен ответ за n*lоg(n) в силу заданных жюри временных ограничений.

Верная организация труда - путь к победе.

2.5. Сортировка задач одного класса

Речь идет о задачах, которые "понятно как решать" после того, как условия прочитаны. То есть, видны алгоритмы решения "общего случая". Такие задачи могут, тем не менее, весьма различаться по количеству случаев особых, когда общая формула не годится.

В этой ситуации команде желательно заняться задачей, минимальной по числу особенностей. При этом важно убедиться, что условие задачи понято правильно. Небрежность, допущенная при понимании условия задачи сейчас, обойдется втридорога позже. Во-первых, команда потратит ресурсы на разработку алгоритма, решающего не ту задачу, во-вторых, потраченное время войдет в результат пропорционально общему числу решенных задач и, в-третьих, переделка задачи иногда может обойтись дороже, чем если все бросить и написать заново.

Не пренебрегайте внимательным чтением условия.

Прежде чем решать задачу, полезно познакомиться с ее условием. Д. Пойа

2.6. Способы пересдачи

Всегда неприятно, если посланная в жюри задача не была зачтена. Возникает момент выбора: "добивать" эту задачу или не отрываться от рабочего процесса решения. Точный ответ на этот вопрос неизвестен. Оценки времени для окончания работы и над той, и над другой задачей могут оказаться ошибочными.

Одним из принципов выработки своей позиции по малоисследованным вопросам является моделирование такой ситуации на тренировках. Постепенно накапливающийся опыт поможет принимать правильное решение, учитывая особенности обеих задач, состояние команды, остаток времени и другие (даже неосознанные) факторы.

Некоторую помощь может оказать так называемая "математическая культура", если команда ею обладает. В данном случае важно такое проявление этой культуры, как осознание, из чего состоит разработанный алгоритм не в плане операторов, а в плане идей, как обрабатываются данные, к какому результату это приводит и каким на самом деле должен быть ответ. Схожая ситуация возникает при попытке студента вычислить интеграл. Он приходит к преподавателю, слышит в ответ "неправильно", и в качестве объяснения получает производную - обратную операцию. То есть бывает, что показать неверность ответа просто, даже не вдаваясь в детали. Регулярно сталкиваясь с этой проблемой, студент постепенно учится проверять ответ известными ему "простыми" способами самостоятельно, а впоследствии он начинает автоматически, без принуждения понимать, почему тот или иной путь решения обречен. Это и есть проявление математической культуры.

Опыт - кузница интуиции.

2.7. Построение контрпримеров

Одним из элементов тренировок может стать практика в построении контрпримеров к собственным решениям и к решениям собратьев по команде. За тех, кто посчитает такую процедуру ненужной, контрпримеры построит жюри.

Помимо "корыстной" пользы в виде предоставления на суд жюри более надежных решений, опыт построения контрпримеров важен и для общего развития, как элемент формирования математической и логической культуры человека. Разбирая партии, контрпримеры строят теннисисты и шахматисты,

Думай заранее!

2.8. Использование эвристик

Эвристика - алгоритм, решающий часть задач из заданного класса, но не решающий (или неизвестно, решающий ли) задачу в общем виде. В умелых руках эвристика на олимпиаде может стать грозным оружием.

С одной стороны, эвристика может быть засчитана как решение задачи, так как задачи проверяются на наборах тестов. Однако, следует помнить, что жюри, возможно, рассматривало некоторые эвристики, и потому разработанный набор тестов уже приготовил западню вашей.

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

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

Отметим, что неграмотное применение эвристик неизбежно погубит команду. Ярким примером такого применения является попытка во что бы то ни стало сдать конкретную задачу с помощью эвристики. Если познания жюри достаточно обширны (а чаще всего, так оно и бывает), то один раз не прошедшая тесты эвристика будет обречена на неудачи и в дальнейшем.

В качестве рабочей поговорки по этой главе приведем фразу, высказанную преподавателем УрГУ С. В.Сизым на одном из праздников:

Знаете ли вы, что неточность попадания снаряда можно компенсировать его диаметром?

2.9. Принцип "последней минуты"

Как в футболе каждая команда стремится забить "гол престижа", так и на олимпиадах каждая команда стремится решить хотя бы одну задачу. Кроме этого принципа, существуют традиции, также не приносящие в большинстве случаев призовых очков, но удовлетворяющие чувство собственного достоинства участников.

Одной из таких традиций является сдача на последних минутах хоть какой-нибудь задачи, пусть и не прошедшей тестирования. Можно даже послать несколько версий одной задачи - вреда это уже не принесет, так как если задача не будет засчитана, то и штрафных очков за нее не начислят.

Сдавайся! (кто может)

2.10. Принцип "блицкрига"

Продолжительная оборона психологически труднее нежели азартное нападение. Из этой завалящей мудрости можно сделать забавное извлечение. Если команда достаточно сильна, можно попробовать получить значительный отрыв уже в дебюте, и тогда команду будет сложно догнать, так как соперники могут торопиться со сдачей, ошибаться при наборе исходных текстов и написании формул. Разумеется, сказанное относится лишь к соперникам, активно пользующимся программой "монитор", о которой шла речь выше. Более того, даже и эти соперники вовсе не обязаны делать какие-либо ошибки при работе. Но своим отрывом вы предоставляете им все возможности ошибиться, отработать менее тщательно, обнаружить брешь в командной дисциплине.

Один из способов получить такой отрыв заключается в следующем. В момент старта двое берут себе по простой задаче и реализуют их, каждый самостоятельно, быстро и практически без ошибок, один - сразу на компьютере, второй -сначала на бумаге, а потом (возможно, с помощью первого) - за терминалом. Все это время третий участник занимается, например, математической задачей или нарабатывает подходы к остальным задачам, в общем, создает плацдарм для дальнейшей работы. При успешной реализации такой идеи получается, что через 50 минут после старта готовы две задачи и наработки для дальнейшего решения. Если и дальше все пойдет гладко, догнать такую команду будет весьма непросто.

Однако, описанный подход содержит и большие опасности. А именно, если что-то не получается у любого из троих участников, то никто не в состоянии прийти к нему на помощь, и в результате происходит задержка, а то и срыв работы всей команды. Простои возможны как при решении первых двух задач или сразу после него, так и в дальнейшем. Чтобы применять подобную тактику, команда должна быть очень хорошо подготовлена. Хотя даже и в этом случае, риск велик. Несколько снизить риск может блестящее взаимопонимание между партнерами.

На практике такой подход почти никогда не окупается. Накладки, ошибки, индивидуальные промахи, непонимание условий, неверный выбор первых задач, неучтенные граничные случаи-очень много всего в природе противостоит приведенной методике. Но задуматься о существовании принципа "блицкрига" стоит уже потому, что, откорректировав систему тренировок с его учетом, можно добиться улучшения взаимопонимания в команде, которое пригодится уже всегда.

Выбирай лучшее из многого - по крупицам.

2.11. Метод нисходящего проектирования

Одним из самых дорогостоящих этапов программирования является отладка. С одной стороны, потому что на ее освоение традиционно отводится мало времени (и, как следствие, по технологии отладки написано не так много литературы, как по кодированию вообще), с другой - так как временные затраты на отладку часто недооценивают и считают, что программа "почти готова", когда успешно происходит трансляция.

Следствием этой ситуации является слабость владения участниками отладочными инструментами, существенные потери времени на "почти готовую" программу и неработающая программа в момент окончания тура. Этот и несколько следующих пунктов содержат некоторые советы, помогающие сократить время на отладку. Секрет в сокращении этого времени часто кроется в самой технологии программирования.

Метод нисходящего проектирования призван сократить временные затраты на написание алгоритма и последующую отладку программы. Суть его, вкратце, заключается в следующем. Изначально в задаче выделяются некоторые "главные" подзадачи, формирующие алгоритм в целом, но не обязательно "опускающиеся" до деталей этого алгоритма. Рассмотрим в качестве примера поиск в ширину в графе. Его обычно разбивают на три подзадачи: инициализация очереди вершин, совершение очередного шага (с анализом, не пора ли закончить работу) и построение кратчайшего пути.

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

Основная идея метода нисходящего проектирования - не пытаться программировать сразу. Пошаговая детализация (программирование "сверху вниз") автоматически заставляет человека формировать понятную ему же структуру программы. После завершение трансляции (также автоматически) формируется первичный набор тестов; каждый тест отлаживает конкретную подзадачу. Аккуратное проектирование обычно приводит к тому, что программист хорошо представляет себе работу каждой конкретной подзадачи, ее входные и выходные данные, и потому в состоянии протестировать именно ее. По окончании тестирования конкретной подзадачи, можно тестировать другие подзадачи независимо(!).Эта независимость дает также возможность тестировать подзадачи по ходу реализации программы, генерируя после трансляции уже первично отлаженный код.

Наконец, упрощается и последующая отладка - при получении неверного результата программа может быть протрассирована, и проверка результата на очередном шаге сведется к пониманию, верно или неверно отработала очередная подзадача. Возможность независимой отладки подзадач сказывается и здесь, сужая область внесения возможных изменений трассируемыми подзадачами.

Помимо перечисленного метод уменьшает нагрузку на мозг, ибо человеку не приходится решать проблему "что делать" У программиста автоматически формируется задание в каждый момент времени. Метод хорош также тем, что допускает множество конкретных воплощений и сочетается с разнообразными усовершенствованиями. Некоторые усовершенствования перечислены ниже.

Перекладывание хотя бы части труда с головы на методику работы эффективно повышает возможности мозга.

2.12. Блочная отладка

В таких языках программирования, как Си и Паскаль, имеется понятие блока. Прием блочной отладки заключается в рассмотрении каждого блока как отдельной подзадачи в момент написания программы. Как правило, программисты любят создавать небольшие по объему блоки, что способствует упрощению их отладки.

Такой прием весьма дисциплинирует программиста. Чем дольше прием применяется, тем больше блоков программист способен отлаживать непосредственно при их создании. С блоков он переходит на логически связные куски программы, на подпрограммы, вспомогательные алгоритмы и т.п. Будучи уверен в "кирпичиках", из которых состоит программа, человек в дальнейшем тестирует уже "здание" в целом, не отвлекаясь на мелочи. Прием особенно эффективен в сочетании с нисходящим проектированием.

Сложность отладки пропорциональна квадрату размера блока.

2.13. Событийно управляемые системы

Многие ошибки происходят в результате некорректных операций над определенными объектами: чтения и записи за границей массива, вычисления вне допустимого диапазона значений переменной, обращения к неиспользуемому участку памяти. Одним из способов предотвращения таких ошибок служит написание событийно управляемых систем.

Сразу отметим, что сказанное не означает, что везде и всюду следует писать событийно управляемые программы. Но сама тренировка в их написании научит программиста лучше понимать и организовывать взаимодействие между объектами, в результате чего он будет допускать меньше ошибок во всех, а не только в событийно управляемых программах.

Рассмотрим программу как некий абстрактный (сказочный) мир, где живут свои герои с характерами, заданными наборами свойств (методов). Только теперь общение между героями будет происходить "цивилизованно" Вместо того, чтобы ударить по гвоздю, молоток пошлет ему сообщение "по тебе пора ударить" Это сообщение может прочитать и еще кто-нибудь, но за отсутствием полезной для себя информации проигнорирует. Гвоздь проверит, не погнут ли он, находится ли он в пределах досягаемости молотка и пошлет стене сообщение о последствиях удара. Например, это сообщение может звучать так: "В точке с координатами (х,у) будет произведен удар силой Р Н/см2" Стена примет это сообщение и отреагирует по-своему.

Явное объявление происходящего через сообщения имеет два преимущества. Вопервых, проверка возможности совершения действия над объектом поручается самому объекту (а кто, кроме самой функции знает, можно ли ее дифференцировать). Тем самым эта проверка производится там, где максимально доступна информация об объекте, то есть необходимые для этой проверки данные. Упрощается обработка некорректных ситуаций - объект вправе либо не реагировать на них, либо посылать ответное сообщение с рассказом о происшедшем. При моделировании параллельных процессов упрощается синхронизация. При осуществлении некоторого события программа получает возможность адекватно отреагировать на него, так как откликнутся только те объекты, которые сообщение заинтересует (нет опасности, что в ответ на крик лыжника о помощи сойдет лавина). Во-вторых, упрощается отслеживание происходящего в программе. Нет больше нужды копаться в конкретных операторах работы с ячейками памяти, достаточно просто выводить куда-либо в отладочном режиме посылаемые сообщения. Как правило, этой деловой переписки достаточно, чтобы установить "куда идут деньги".

Но часто разрабатываемые программы достаточно просты, и нет смысла палить из пушки по воробьям. Тем не менее, идеи событийной управляемости часто оказывают помощь и при реализации простых задач. Само понимание возможности такой работы учит программиста грамотно организовывать поведение объектов в абстрактном мире, избегая ошибок.

2.14. Граничные тесты

Многие программы отлично работают на "средних" примерах, но (увы) дают неверный результат когда один или несколько параметров задачи принимают крайние значения. К сожалению, часто не представляется возможным отследить все комбинации крайних значений всех переменных - это число бывает слишком велико. Чтобы как-то выйти из этого положения, действуют следующим образом.

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

На границе тучи ходят хмуро.

2.15. Еще раз об integer, word и long

Чтобы не допускать ошибок, связанных с преобразованием целых типов, можно воспользоваться следующим правилом: при передаче в переменную или функцию значения некоторого выражения, убедитесь, что хотя бы один аргумент имеет тип результата.

Вся процедура проверки корректности выражения состоит из двух этапов: проверки того, что вычисляемое значение находится в диапазоне результата (int*int=long, abs(int)+abs(int)=word, но int+int=long (!)), и того, что автоматическое приведение типов в выражении не приводит к искажению значения (int*int+int - может быть неверно, если первое слагаемое будет приведено к int; следует писать int*long+int. Обратите внимание, что int+int также может бытъ неверно, если транслятор сначала приведет результат к int, а потом - присвоит его.).

Используя приведенный принцип, можно застраховать себя от выполнения второго шага (возможно, использовать принцип следует несколько раз в одном выражении, например; (int+int)-long может не отработать, если (int+int) будет автоматически приведено к int).

2.16. Оператор комментария

Часто программисты недооценивают оператор комментария, что приводит к неоправданным затратам времени на отладку программы, а также к многократным пересдачам ее жюри. Происходит это потому, что человек забывает логику своей программы и в дальнейшем тратит время на то, чтобы понять, где именно происходит требуемая обработка или как именно работает тот или иной фрагмент.

Однако, еще со времен, когда не было никаких языков программирования, кроме машинных кодов, существует метод описывать, что происходит в программе, и этот метод-комментарии. Понятная программа во многом похожа на книгу-она содержит разделы, главы, параграфы. В какой-то мере пропуск строки напоминает абзац. Логично, чтобы главы и части программы-книги имели названия, а логически самостоятельные части (напоминающие, к примеру, статьи в сборнике) - аннотации.

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

Каждый, кто выполнял какой-либо совместный проект, быстро уясняет себе, что написать комментарий быстрее, дешевле и проще, чем отвечать на вопросы партнера о том, что происходит там-то и там-то. Написать грамотный комментарий, помогающий, а незатуманивающий от читателя текста программы ее суть, несложно, если отнестись к этому ответственно.

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

Комментарии не увеличивают время работы программы.

2.17. Предварительное обдумывание алгоритма

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

Одним из примеров такого рода служит определение простоты числа. Можно написать программу, делящую заданное натуральное число на все, меньшие его натуральные числа. Недолгое размышление подскажет, что для проверки простоты достаточно делить на 2 и все нечетные числа. Однако, подумав еще немного, можно сообразить, что достаточно делить на 2 и все нечетные числа, не превосходящие арифметического квадратного корня из заданного числа, ибо если есть множитель, больший корня, то должен быть и множитель, меньший корня. Уже для такого небольшого числа как миллион две последние версии программы проделают 500 тысяч сравнений и 500 сравнений соответственно.

Дурная голова рукам покоя не дает.

2.18. Копирование блоков

Одним из приемов ускорения набора текста является копирование уже набранного блока кода и небольшая его последующая модификация. Но в реальной жизни в дальнейшем порой приходится корректировать один из этих блоков, и программист в этот момент обязан задать себе вопрос: как внесенное изменение отразится на других похожих блоках.

Такой вопрос предполагает, что программист в состоянии определить, где именно находятся похожие блоки и чем именно эти блоки отличаются. Если применять копирование блоков бездумно, то ответы на эти вопросы могут занять больше времени, чем хотелось бы. Поэтому:

-1. Размещайте такие блоки невдалеке друг от друга.

-2. Комментируйте отличия каждого блока от других.

Может быть, если программист не вполне уверен в своем умении быстро ответить на приведенный вопрос, ему стоит и вообще воздержаться от применения подобной практики, путем выделения общего во всех блоках в отдельную процедуру.

Умение копировать не освобождает от размышлений.

3. Тренировки

3.1. Смысл тренировок

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

Учитывая особенности соревнования, нужно подбирать и теоретический материал. Не претендуя на абсолютную истину все же заметим, что при подготовке к студенческой олимпиаде изучение программирования на машине Тьюринга или сетях Петри может принести больше пользы, чем асовое исполнение текстов на ассемблере.

Это не означает впрочем, что ассемблер изучать не нужно. Исходя из здравого смысла, можно предположить, что тренировки будут тем полезнее, чем шире будет их тематика. Может быть, человеку проще думать и действовать, он более уверен в себе, если то, что приходится изобретать на соревнованиях (и, кстати, на работе -тоже), гдето было слышано, опробовано, проверено на опыте.

Усвоенные на тренировках разнообразные идеи составляют арсенал участника для борьбы с задачами, его походный набор инструментов для изготовления программ. И чем больше этот набор, чем более совершенны его инструменты, тем качественнее будет и конечный продукт.

3.2. Частота тренировок

Личный опыт показывает, что максимальным сроком, в течение которого человек еще способен помнить, о чем шла речь, является неделя. Поэтому прежде всего следует рассмотреть возможность устраивать тренировки хотя бы раз в неделю.

Если это невозможно, то кажется разумным увеличить самостоятельную нагрузку, а также создать условия для промежуточных встреч для общения между участниками, тренерами, преподавателями и консультантами.

3.3. Элементы тренировок (в порядке убывания важности)

3.3.1. Круг тем

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

Обыденностью для участника соревнований становится задача "что делать, когда точное решение наизусть неизвестно" Жизнь и оргкомитет предлагают нам задачи, часто в чем-то необычные, неосвоенные, содержащие разнообразные препятствия на пути решения "обычными" методами. Знание нестандартных подходов, а также методов преодоления трудностей, позволит участнику справиться с этими затруднениями.

3.3.2. Математические задачи

Для повышения квалификации программиста часто весьма полезно решать именно математические задачи, в том числе, олимпиадные. Во-первых, потому что во многих стратегиях отчетливо выделена роль математика, а во-вторых, потому что применение математических методов решения может облегчить программирование (см. также выше пункт "Предварительное обдумывание алгоритма").

3.3.3. Отладка

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

3.3.4. Режим реального контроля

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

Название абзаца выбрано таким потому, что важно не только, чтобы никто не простаивал, но и чтобы задачи решались компактно по времени. То есть, все могут быть заняты полезным трудом, но если этот труд сводится к тому, что каждый очень долго решает свою задачу, то надо обдумать вопрос о реорганизации тренировочного процесса.

3.3.5. Реализация ссылочных структур

Другая крайность - прекрасное знание теории решения тех или иных задач, но большое число ошибок в реализации. Яркий пример из этой области-реализация ссылочных структур данных (например, это могут быть стеки, очереди, деки и т.п.). Многие умеют использовать эти средства (в том числе, весьма нетривиально), но при торопливой реализации легко ошибаются. Косвенная адресация ничего не простит, а транслятор не поможет - используя указатели вместо объектов, человек берет на себя смелость управлять памятью.

3.3.6. Взаимопонимание

Речь идет об отработке ситуаций, когда по тем или иным причинам нормальная работа команды невозможна. Пример-задача не сдана с десятой попытки. Возможны и другие ситуации, когда нужно объяснить партнеру, что происходит, или, наоборот, помочь, когда надо принимать решение о совместной работе над одной задачей и т.п. Короче, если отработать методы эвакуации заранее, меньше будет ущерб от пожара.

3.3.7. Общее число задач

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

3.3.8. Тай-брейк

Один из элементов работы - решение "последней" задачи. Эту задачу приходится решать в ускоренном темпе, а простой она, как правило, не бывает. Если решать последнюю задачу как все остальные задачи, то времени не хватит. Речь и идет о том, чтобы попытаться выгадать за счет отбрасывания других задач те "золотые" 30 - 40 минут, которых не хватает, чтобы закончить работу.

3.3.9. Замеры времени

Наконец, когда освоена приведенная выше техника, можно приступать к отработке быстрого командного решения задач. Но помните: вы с этим поторопитесь, если указанные выше элементы (а возможно, и многие другие, которые мы не учли) не будут осознаны участниками, и придется отрабатывать их на ходу, а это - нервы, споры и проволочки.

3.4. Роль запасного участника

Запасной игрок - это особая роль. С одной стороны, он позволяет не сорвать выступление, когда кто-то заболел, а с другой -его имя остается в тени после соревнований.

Следует особое внимание уде; 1ять работе с запасным участником (участниками), в том числе учитывая психологические аспекты их невыступления.

3.5. Спарринг-партнеры

Чтобы оценить свои силы более реально, интересно на последнем этапе тренировок (уже когда перешли к замерам времени) соревноваться с другой командой. Кроме того, с друзьями-соперниками можно обсуждать различные элементы соревновании, а идеями обмениваться. Чем больше команд тренируются вместе, тем большим числом идей они смогут поделиться друг с другом.

"Совместно"-не означает в одной комнате. Можно просто вместе ходить на лекции, общаться в коридорах, а у терминала собираться порознь.

4. Советы руководителю команды

4.1. "А счастье было так возможно..."

Нет никакого смысла горевать по поводу того, что "чуть-чуть" не успели Так будет всегда и независимо от результата. Вообще, не очень понятно, что можно обсуждать после соревнований. Во всяком случае, если задачи интересные, то тема обеспечена Когда же она надоест, можно обсудить допущенные технические ошибки и обратить внимание на пользу, которую все проделанное принесет в жизни.

4.2. Соотношение приза и груза

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

Техника, расписание тренировок, билеты, деньги - все это на совести руководителя. На вопросы, не связанные с программированием, должно уходить минимальное время.

Полезно помнить, что у участников есть родители. Своевременное и полное их информирование о настоящем и будущем сэкономит и руководителю, и участникам много нервов.

Наконец, очень хорошо, если руководитель никогда не повышает голос, всегда выслушивает любого собеседника (и если прерывает, то очень вежливо и только из-за нехватки времени) и уж совсем никогда не впадает в панику. Он, и прежде всего он, должен заразить всех уверенностью, что всегда что-то можно придумать, и демонстрировать это на деле, потому что неожиданных ситуаций в работе тренера возникает уйма.

Участники первых полуфинальных соревнований
Северо-Восточного Европейского региона
командного чемпионата мира по программированию 1996/97'гг.
от Уральского государственного университета:
Евгений Штыков - тренер;
первая команда УрГУ - Марат Бакиров,
Станислав Васильев, Александр Клепинин;
вторая команда УрГУ - Сергей Герштейн, Станислав Скорб,
Никита Шамгунов, запасной Сергей Коган