Рассылка закрыта

При закрытии подписчики были переданы в рассылку "Обзор инструментов SEO-оптимизатора и методов продвижения" на которую и рекомендуем вам подписаться.

Вы можете найти рассылки сходной тематики в Каталоге рассылок.

←   Май 2004   →
					1	2
3	4	5	6	7	8	9
10	11	12	13	14	15	16
17	18	19	20	21	22	23
24	25	26	27	28	29	30
31

Автор

Виктор Журавлев

Статистика

1.725 подписчиков
-1 за неделю

• Выпуски
• Статистика

←   Все выпуски   →

Олимпиадные задачи и алгоритмы на C++

Информационный Канал Subscribe.Ru

---

Олимпиадные задачи и алгоритмы на C++     Здравствуйте, уважаемые подписчики. В этом выпуске две новые задачки: Манхеттен Морской бой Задача №7 "Манхеттен" (5 баллов). Входной файл: input.txt Выходной файл: output.txt Ограничение по времени: 1 сек. на тест Ограничение по памяти: 1 Mb Условие      На плоскости задано n точек. Расстояние между точками (x1, y1) и (x2, y2) будет вычислять как сумму модулей разностей их координат: r = |x1 - x2| + |y1 - y2|. Найти точку, сумма расстояний от которой до заданных n точек минимальна. Формат входного файла      В первой строке задано одно целое число n, 1 <= n <= 1000. Далее идут n строк, в каждой из которых записаны два числа, разделенные пробелом, - координаты точек. Координаты - целые числа, по модулю меньше 10000. Формат выходного файла      Вывести одну строку, содержащую два вещественных числа, разделенные пробелом. Числа выводить с 5 знаками после десятичной точки. Если существует несколько точек с минимальной суммой расстояний, то выведите любую из них. Пример входного файла (input.txt) 4 -1 1 2 0 4 4 2 5 Пример выходного файла (output.txt) 2.00000 3.14159 Задача №8 "Морской бой" (10 баллов). Входной файл: input.txt Выходной файл: output.txt Ограничение по времени: 1 сек. на тест Ограничение по памяти: 1 Mb Условие      В игру "Морской бой" играют два человека. В начале игры каждый чертит на клеточном листе бумаги свое поле - квадрат с длиной стороны 10 клеток. Строки квадрата обозначаются латинскими буквами от a до j сверху вниз, столбцы - цифрами от 0 до 9 слева направо. Затем игрок расставляет на своем поле корабли: один 4-палубный, два 3-палубных, три 2-палубных и четыре 1-палубных. Корабль - это группа соседних клеток, образующих горизонтальную или вертикальную полоску. Количество палуб корабля - это количество клеток, из которых он состоит. Корабли могут соприкасаться со сторонами поля, но не могут касаться друг друга. Игроки не показывают друг другу свои поля. Примеры полей с расставленными кораблями ('.' - пусто, '#' - палуба): №1 №2 №3 №4 0123456789 0123456789 0123456789 0123456789 a .......### a ....##.... a .#.....### a .......... b ..####.... b .......... b #......... b .......... c #......... c .##...#... c ..#.###... c .####..... d #.#..##... d ......#... d .......... d .......... e #.#....... e .#.#...... e ####...... e ##....##.. f .......... f ...#...#.. f .......... f ....#..... g ......#... g ...#...... g .#....#... g .#..#..... h ##.......# h #..#...#.# h .#....#... h .#..#..#.. i ....#..... i #......... i .......... i .......... j .......#.. j #......### j .#....##.. j ..#.#.#...      В примерах №1 и №2 корабли расставлены правильно. В примере №3 корабли расставлены неверно, потому что два однопалубных корабля (a1 и b0) касаются друг друга. В примере №4 не хватает одного 3-палубного корабля.      Первый игрок делает первый ход. Ход заключается в том, что игрок называет позицию на поле противника. Это клетка, в которую стреляет игрок. Причем по правилам он не может выстрелить в одну и ту же клетку дважды. Если эта клетка пуста, то противник говорит "мимо" и ход переходит к нему. В противном случае палуба корабля, расположенная в данной клетке, считается уничтоженной, и возможны два варианта. 1) Если все остальные палубы данного корабля были уничтожены раньше (или это 1-палубный корабль), то противник говорит "убит". 2) Если у корабля сохранилась хотя бы одна палуба, то противник говорит "ранен". В обоих случаях ход снова делает тот же игрок (т.е. он стреляет, пока не промахнется). Задача каждого игрока - уничтожить все корабли противника. Выигрывает тот, кто сделает это раньше.      Вам нужно написать программу, которая получает расстановку кораблей и список ходов игроков и проверяет, по правилам ли проходила игра. Если игроки допустили ошибки, то программа должна выдать сообщение о первой обнаруженной ошибке. Если ошибок нет, то программа должна установить, завершилась игра или нет, и, если завершилась, то выявить победителя. Формат входного файла      Первые десять строк входного файла содержат по десять символов каждая. В них задано описание поля первого игрока. В строках содержатся символы '.' (пустая клетка) и '#' (палуба корабля). Затем идет пустая строка. В следующих десяти строках аналогично задается поле второго игрока. Затем идет пустая строка. Следующая (23-я по счету) строка содержит одно целое число n, 0 <= n <= 1000 - количество сделанных ходов. Следующие n строк задают описание ходов в том порядке, в котором их делали игроки. Описание хода имеет формат "номер_игрока позиция ответ_противника". "номер_игрока" - один из символов '1' или '2'. "позиция" - два символа, первый - буква от 'a' до 'j', второй - цифра от '0' до '9'. "ответ_противника" - слово 'past' (мимо), 'killed' (убит) или 'wounded' (ранен). Формат выходного файла      В выходной файл вы должны выдать одно из следующих сообщений. "Error: first player's field is incorrect" Первый игрок неверно расставил свои корабли. "Error: second player's field is incorrect" Второй игрок неверно расставил свои корабли. "Error in move #k: the game is already finished" (Здесь и далее k нужно заменить на номер хода (нумерация с 1).) Игра уже завершена, но игрок делает ход. Напомню, что игра завершается, когда у одного из игроков уничтожены все корабли. "Error in move #k: this move must be made by another player" Ходить должен другой игрок. "Error in move #k: two shots in one place" Игрок выстрелил в клетку, в которую уже стрелял. "Error in move #k: wrong enemy's answer" Противник дал неправильный ответ. "OK: first player is winner" Первый игрок победил. "OK: second player is winner" Второй игрок победил. "OK: the game isn't finished yet" Игра еще не завершена.      Если ход содержит сразу несколько ошибок, то выдайте сообщение с меньшим номером. Пример входного файла (input.txt) .......### ..####.... #......... #.#..##... #.#....... .......... ......#... ##.......# ....#..... .......#.. ....##.... .......... .##...#... ......#... .#.#...... ...#...#.. ...#...... #..#...#.# #......... #......### 8 1 a4 wounded 1 a3 past 2 j9 past 1 b4 past 2 b1 past 1 a5 killed 1 h1 past 2 b2 wounded Пример выходного файла (output.txt) OK: the game isn't finished yet Пример входного файла (input.txt) .......### ..####.... #......... #.#..##... #.#....... .......... ......#... ##.......# ....#..... .......#.. ....##.... .......... .##...#... ......#... .#.#...... ...#...#.. ...#...... #..#...#.# #......... #......### 8 2 a0 killed 1 a3 past 2 j9 past 1 b4 past 2 b1 past 1 a5 killed 1 h1 past 2 b2 wounded Пример выходного файла (output.txt) Error in move #1: this move must be made by another player Пример входного файла (input.txt) #........# .########. ..#....#.. ####..#### .#..##..#. ##..##..## .#.#..#.#. ###....### .########. #........# .......... ..#####... .#....##.. .#...#.#.. .#..#..#.. .#..#..#.. .#.#...#.. .##....#.. ..#####... .......... 8 2 a0 killed 1 a3 past 2 j9 past 1 b4 past 2 b1 past 1 a5 killed 1 h1 past 2 b2 wounded Пример выходного файла (output.txt) Error: first player's field is incorrect Оформление, отправка и проверка решений.     На проверку принимаются решения, написанные на языке C++. Отправляйте свои письма по адресу accepted@narod.ru. Решение должно содержаться в одном файле, вложенном в ваше письмо. Для компиляции, по вашему выбору, будет использоваться программа bcc.exe (Borland C++ 3.1) или cl.exe (Microsoft Visual C++ 6.0). Размер исходного кода не должен превышать 40 Kb. Для каждой задачи отправляйте отдельное письмо. В теле письма укажите следующие данные (пример): ник (*): vasya пароль (*): a193z458w2 фамилия: Иванов имя: Василий e-mail: vasya@hotmail.com номер задачи (*): 1 компилятор (*): cl     (*) обозначены обязательные для заполнения поля. Ник и пароль вы сами придумаете при отправке своего первого письма. В последующих письмах указывайте те же самые ник и пароль. Я пока не придумал, что делать, если два человека используют один и тот же ник. Так что, старайтесь придумать его так, чтобы никто до вас его еще не придумал :-) Если вы укажите свой e-mail, то с этой проблемой будет легче разобраться. В качестве компилятора укажите bcc или cl. И, главное, не забудьте указать номер задачи!     При проверке решений, используются стандартные правила acm. Их можно найти, например, на сайте http://acm.baylor.edu. Проверка решений осуществляется на наборе тестов, недоступных участникам. Решение считается принятым, если выдало верный ответ на каждом из тестов. Программа должна считывать данные из указанного в условии входного файла и выдавать результат в указанный в условии выходной файл. Она не должна работать с другими файлами или каталогами. Входной файл нельзя открывать для записи. При доступе к входному и выходному файлу вы должны предполагать, что они находятся в текущей директории. Не используйте консольный ввод или вывод.     Решения принимаются до субботы следующей недели (15 мая 2004) включительно. В воскресенье (16 мая 2004) будут высланы результаты тестирования и авторские решения. Ведущий рассылкой: Виктор Журавлев Вопросы, пожелания, предложения пишите на мой e-mail.

---

---

http://subscribe.ru/ E-mail: ask@subscribe.ru

Отписаться Убрать рекламу

---

В избранное

{#template MAIN} <div id="loginForm" style="display:none;" class="subscriberu_popup"> <div class="popup_register"> {#include js_tmpl_auth_reg_tab} {#if $P.login_register_tab == 1} <form class="authentication-form" method="post" action="/MEMBERLOGIN_authen_cred"> <dl class="rg_block_options"> <dt id="js_tap_panel_auth"> <h1>Войти на сайт</h1> {* {#include js_tmpl_auth_reg_button} *} {#include js_tmpl_auth_reg_action} <hr class="logreg_line noPhones"> <div class="logreg_descr noPhones"><p>{#include js_tmpl_auth_reg_descr} </p></div> <div class="logreg_advice noPhones"> Если вы еще не с нами, то начните с <a href="#" onclick="rgNav('js_tab_reg');return false;" class="dashed" data-func="registr">регистрации</a> </div> <br><br> <a class="dashed auth-enter" href="/manage/author/"><b>Вход для авторов</b></a> </dt> </dl> </form> {#/if} {#if $P.login_register_tab == 2} <div class="rg_block_options"> <div id="js_tap_panel_auth"> <h1>Регистрация</h1> <div class="social_reg"> {* <div class="rg_description">{#include js_tmpl_soc_auth_reg_descr}</div> *} {#include js_tmpl_auth_reg_soc} <div class="rg_soc_auth_agree">{#include js_tmpl_auth_reg_agree}</div> </div> <div class="subscribe_reg"> {* <div class="rg_description"> #include js_tmpl_auth_reg_descr </div> *} {#include js_tmpl_auth_reg_action} </div> {* {#include js_tmpl_auth_reg_button} *} <div class="clr"> </div> <hr class="logreg_line noPhones"> <div class="logreg_descr noPhones">{#include js_tmpl_auth_reg_descr} {#include js_tmpl_soc_auth_reg_descr} </div> </div> </div> {#/if} </div> {* <div class="gray_bg register_shadow"></div> *} </div> {#/template MAIN} {#template js_tmpl_auth_reg_tab} <ul class="rg_nav"> <li id="js_tab_auth" class="{#if $P.login_register_tab == 1} rg_active_nav {#/if} rg_first_nav"><a onclick="rgNav('js_tab_auth');return false;" href="">Вход на сайт</a></li> <li id="js_tab_reg" class="{#if $P.login_register_tab == 2} rg_active_nav {#/if}"><a onclick="rgNav('js_tab_reg');return false;" href="">Регистрация </a></li> </ul> <span onclick="hidebo();" class="rg_closed"> </span> {#/template js_tmpl_auth_reg_tab} {#template js_tmpl_auth_reg_action} {#if $P.login_register_tab == 1} {#include js_tmpl_auth_reg_soc} {#/if} <div class="rg_forms"> <input type="hidden" id="login_register_destination" value="{$P.login_register_destination}"/> {#if $P.login_register_tab == 1} <div class="rg_for_input"> <span class="rg_text_inner">E-mail или код подписчика</span> <input id="credential_0" class="js_keydown_selector rg_input_text" data-js_submit="no" data-js_next_input_name="credential_1" name="" type="text" /> </div> <div class="rg_for_input"> <span class="rg_text_inner">Пароль</span> <input id="credential_1" class="js_keydown_selector rg_input_text" data-js_submit="yes" data-js_action="js_loginFormBut" name="" type="password" onkeyup="showAttention(this,!!window.event.shiftKey)" /> <span class="pswd_attention" id="attention_pswd"> <span class="icon_attention"></span> <span class="pswd_attention-text" id="attention-text_pswd1">Русская раскладка клавиатуры!</span> <span class="pswd_attention-text" id="attention-text_pswd2">У вас включен Caps Lock!</span> <span class="pswd_attention-text" id="attention-text_pswd3">У вас включен Caps Lock и русская раскладка клавиатуры!</span> </span> </div> <div class="rg_for_input input-alien"> <span class="chk noPhones"><input id="chk_alien" name="" type="checkbox" /></span><label for="chk_alien" class="noPhones"> Чужой компьютер</label> <a class="forgot_pass" href="/member/totalrecall">Забыли пароль?</a> </div> <div class="rg_for_input"> <em id="auth_msg" class="reg_error"></em> <input id="lf_typeauthid" value="email" type="hidden"> <input type="submit" class="button button-red logreg_submit" id="js_loginFormBut" value="Войти"> <!--</a>--> <div class="loading loading-cover" style="display: none;"><div class="loader"></div></div> </div> {#/if} {#if $P.login_register_tab == 2} <div class="rg_for_input"> <span class="rg_text_inner">E-mail</span> <input id="arfemail" class="js_keydown_selector rg_input_text" name="" type="text" data-js_submit="yes" data-js_action="js_regFormBut"/> </div> <div class="rg_for_input rg_set_lineh rg_for_input_wide"> <label class="js_tap_panel_checkbox"> <span class="chk"><input name="" id='js_tap_panel_checkbox_terms' type="checkbox" data-js_submit="yes" /></span> Я ознакомился и согласен с <a class="link_txd logreg_accLink" href="/faq/vereinbarung.html">условиями сервиса Subscribe.ru</a> </label> <br /> <label class="js_tap_panel_checkbox"> <span class="chk"><input name="" id='js_tap_panel_checkbox_personal' type="checkbox" data-js_submit="yes" /></span> Нажимая на кнопку "Готово!", я даю <a class="link_txd logreg_accLink" href="/faq/persverordnung.html">согласие на обработку персональных данных</a> </label> </div> {* <div style="float: left;position: absolute;left: 11em;"> <img src="http://www.kupivip.ru/images/vip/logo.png?1604" style="width: 86px; vertical-align: middle;display: block;"> </div> <div class="rg_for_input rg_set_lineh"> <label class="js_tap_panel_checkbox"><input name="" id="js_tap_panel_checkbox_kupivip" type="checkbox" data-js_submit="yes"> Я хочу получать новости о скидках на одежду</label> </div> *} <div class="rg_for_input"> <em id="reg_msg" class="reg_error rg_for_input_wide"></em> <em id="reg_msg2" class="reg_error rg_for_input_wide"></em> <input id="rf_typeauthid" value="email" type="hidden"> <a class="button button-red logreg_submit" id="js_regFormBut" href="#">Готово!</a> <div class="loading loading-cover" style="display: none;"><div class="loader"></div></div> </div> {#/if} </div> {#/template js_tmpl_auth_reg_action} {#template js_tmpl_auth_reg_agree} <div class="rg_for_input rg_set_lineh rg_for_input_wide"> <label class="js_tap_panel_checkbox"> <span class="chk"><input name="" id='js_tap_panel_checkbox_terms_reg' type="checkbox" data-js_submit="yes" /></span> Я ознакомился и согласен с <a class="link_txd logreg_accLink" href="/faq/vereinbarung.html">условиями сервиса Subscribe.ru</a></label> <em id="reg_msg_soc" class="reg_error rg_for_input_wide"></em> </div> {#/template js_tmpl_auth_reg_agree} {#template js_tmpl_auth_reg_button} <div class="rg_butons_socials"> {#if $P.login_register_tab == 1} <a class="rg_btn_soc rg_bs_01 js_tap_panel_selector" action="auth_email" href="#"><span><i></i>Email</span></a> <a class="rg_btn_soc rg_bs_01 js_tap_panel_selector" action="auth_openid" href="#"><span><i></i>OpenID</span></a> <a class="rg_btn_soc rg_bs_02 js_tap_panel_selector" action="auth_vkontakte" href="#"><span><i></i>Вконтакте</span></a> <a class="rg_btn_soc rg_bs_02 js_tap_panel_selector" action="auth_mailru" href="#"><span><i></i>Mail.Ru</span></a> {#/if} {#if $P.login_register_tab == 2} <a class="rg_btn_soc rg_bs_01 js_tap_panel_selector" action="reg_email" href="#"><span><i></i>Email</span></a> <a class="rg_btn_soc rg_bs_01 js_tap_panel_selector" action="reg_openid" href="#"><span><i></i>OpenID</span></a> <a class="rg_btn_soc rg_bs_02 js_tap_panel_selector" action="reg_vkontakte" href="#"><span><i></i>Вконтакте</span></a> <a class="rg_btn_soc rg_bs_02 js_tap_panel_selector" action="reg_mailru" href="#"><span><i></i>Mail.Ru</span></a> {#/if} </div> {#/template js_tmpl_auth_reg_button} {#template js_tmpl_auth_reg_descr} {#if $P.login_register_tab == 1} Для оформления подписки на выбранную рассылку, работы с интересующей вас группой или доступа в нужный вам раздел, просим авторизоваться на Subscribe.ru {#/if} {#if $P.login_register_tab == 2} Для регистрации укажите ваш e-mail адрес. Адрес должен быть действующим, на него сразу после регистрации будет отправлено письмо с инструкциями и кодом подтверждения. {#/if} {#/template js_tmpl_auth_reg_descr} {#template js_tmpl_soc_auth_reg_descr} Или зарегистрируйтесь через социальную сеть. {#/template js_tmpl_soc_auth_reg_descr} {#template js_tmpl_auth_reg_soc} <div class="rg_soc"> {#if $P.login_register_tab == 1} <a onclick="return _checkSocConfirm(event)" href="https://oauth.vk.com/authorize?client_id=3954260&scope=wall,offline,photos,groups,video,audio,email&redirect_uri={location.protocol+'//'+location.host}/member/login/vk/&response_type=code&v=5.15" class="login_register_vk_button"> <span class="login_register_vk_icon"></span> </a> {#/if} {#if $P.login_register_tab == 2} <a onclick="return _checkSocConfirm(event)" href="https://oauth.vk.com/authorize?client_id=3954260&scope=wall,offline,photos,groups,video,audio,email&redirect_uri={location.protocol+'//'+location.host}/member/join/vk&response_type=code&v=5.15" class="login_register_vk_button"> <span class="login_register_vk_icon"></span> </a> {#/if} </div> {#/template js_tmpl_auth_reg_soc}

{#template MAIN} <div id="loginForm" style="display:none;" class="subscriberu_popup"> <div class="popup_register"> {#include js_tmpl_auth_reg_tab} <dl class="rg_block_options"> <dt id="js_tap_panel_auth"> <p class="rg_description">{#include js_tmpl_auth_reg_descr}</p> <div class="clr"> </div> {#include js_tmpl_auth_reg_action} <div class="clr"> </div> </dt> </dl> </div> <!-- <div class="gray_bg register_shadow"></div> --> </div> {#/template MAIN} {#template js_tmpl_auth_reg_tab} <ul class="rg_nav"> <li id="js_tab_reg" class="rg_active_nav rg_first_nav"><a href="" onclick="return false;" >Регистрация</a></li> </ul> <span onclick="hidebo();" class="rg_closed"> </span> {#/template js_tmpl_auth_reg_tab} {#template js_tmpl_auth_reg_descr} <strong>Пожалуйста, подтвердите ваш адрес.</strong><br><br>Вам отправлено письмо для подтверждения вашего адреса {$P.register_confirm_mail}.<br>Для подтверждения адреса перейдите по ссылке из этого письма. {#/template js_tmpl_auth_reg_descr} {#template js_tmpl_auth_reg_action} <div class="rg_forms confirm_code_from_letter"> <div class="rg_for_input"> <span class="rg_inp_descr" style="width:15em;">Или введите код из письма:</span> <input type="text" value="" id="confirm_code" name="" data-js_submit="yes" data-js_action="js_confirmFormBut" class="js_keydown_selector rg_input_text_conf" > </div> <div class="rg_for_input"><label>Не пришло письмо? <b>Пожалуйста, проверьте папку Спам</b><br /> (папку для нежелательной почты).</label><br />  <a href="" onclick="ajax_recall_code();return false" >Вышлите мне письмо еще раз!</a></div> <div class="rg_for_input"> <em class="reg_error" id="confirm_msg"></em> <a href="#" class="button button-red" id="js_confirmFormBut">Готово</a> <div class="loading loading-cover" style="display: none;"><div class="loader"></div></div> <br> </div> </div> {#/template js_tmpl_auth_reg_action}