Задачи олимпиады по программированию

Правила проведения олимпиады, условия задач и комментарии к ним, результаты олимпиады и апелляции.
Руководители: к.ф-м.н., профессор Пирогов Владислав Юрьевич, ник - Vladislav_133; к.п.н, доцент Слинкин Дмитрий Анатольевич, ник - xdsl

Модераторы: xdsl, Vladislav_133

Задачи олимпиады по программированию

Сообщение xdsl 27 мар 2014, 09:12

Здесь, 27 марта в 12.00 (10.00 Москвы), будут опубликованы задачи по программированию.

Всего подготовлено 6 задач. 2 - разминочного характера, стоимостью в 1 балл. 4 - классические олимпиадные задачи, стоимостью 6,8,8 и 10 баллов.

Предупреждение
xdsl
 
Сообщения: 1236
Зарегистрирован: 09 дек 2008, 05:16
Откуда: ВЦ ШГПИ
Полное имя: Слинкин Д.А.

Re: Задачи олимпиады по программированию

Сообщение xdsl 27 мар 2014, 11:06

Условия задач.
Уточняющий комментарий по тестам-примерам: https://shgpi.edu.ru/forum/viewtopic.php?f=107&t=1147&p=7205#p7205
Вложения
Stop8.pdf
(125.52 Кб) Скачиваний: 408
Chess10.pdf
По задаче Chess10 есть уточняющий комментарий: https://shgpi.edu.ru/forum/viewtopic.php?f=107&t=1147#p7200
(105.26 Кб) Скачиваний: 401
Queen8.pdf
(30.89 Кб) Скачиваний: 426
Cipher6.pdf
(35.09 Кб) Скачиваний: 456
FirstNext1.pdf
(33.6 Кб) Скачиваний: 493
Line1.pdf
(25.14 Кб) Скачиваний: 404
xdsl
 
Сообщения: 1236
Зарегистрирован: 09 дек 2008, 05:16
Откуда: ВЦ ШГПИ
Полное имя: Слинкин Д.А.

Re: Задачи олимпиады по программированию

Сообщение Xardas 27 мар 2014, 11:16

Можно ли, по традиции, использовать stdin и stdout вместо input.txt и output.txt?
Xardas
 
Сообщения: 45
Зарегистрирован: 12 янв 2011, 11:23
Полное имя: Шахматов Александр Александрович

Re: Задачи олимпиады по программированию

Сообщение xdsl 27 мар 2014, 11:22

Цифра в названии файла - количество баллов за задачу.
Две разминочные задачи, по 1 баллу: "Прямая"(Line1.pdf) и "На первый-второй"(FirstNext1.pdf)
Четыре более серьезных задачи: "Шифровка"(Cipher6.pdf), "Вовремя остановиться"(Stop8.pdf), "Ферзь"(Queen8.pdf) и "Шахматная задача"(Chess10.pdf)

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

Можно ли, по традиции, использовать stdin и stdout вместо input.txt и output.txt?
Можно. Обязательно об этом факте сообщите в заголовке решения задачи.
xdsl
 
Сообщения: 1236
Зарегистрирован: 09 дек 2008, 05:16
Откуда: ВЦ ШГПИ
Полное имя: Слинкин Д.А.

Re: Задачи олимпиады по программированию

Сообщение Xardas 27 мар 2014, 11:35

Шифровка писал(а):Две шифровки, в которых совпадают по порядку номера слов, но различны
номера букв в этих словах, считаются тождественными.

А значит, выводить можно только одну из них? Если да, то как будет осуществляться проверка? Комбинации ведь в таком случае могут не совпасть с эталонным решением уважаемых Организаторов.
Xardas
 
Сообщения: 45
Зарегистрирован: 12 янв 2011, 11:23
Полное имя: Шахматов Александр Александрович

Re: Задачи олимпиады по программированию

Сообщение bdm1809 27 мар 2014, 11:37

Xardas писал(а):
Шифровка писал(а):Две шифровки, в которых совпадают по порядку номера слов, но различны
номера букв в этих словах, считаются тождественными.

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

Присоединяюсь к вопросу.
bdm1809
 
Сообщения: 10
Зарегистрирован: 20 мар 2010, 14:10
Откуда: Шадринск
Полное имя: Бельков Д.М.

Re: Задачи олимпиады по программированию

Сообщение xdsl 27 мар 2014, 11:46

Автор задачи "Шифровка" сейчас на пути из вуза домой. Думаю, в течении часа он ответит на Ваши вопросы.
xdsl
 
Сообщения: 1236
Зарегистрирован: 09 дек 2008, 05:16
Откуда: ВЦ ШГПИ
Полное имя: Слинкин Д.А.

Re: Задачи олимпиады по программированию

Сообщение Vladislav_133 27 мар 2014, 12:06

Xardas писал(а):Можно ли, по традиции, использовать stdin и stdout вместо input.txt и output.txt?

Не можно, а нужно :)
Аватара пользователя
Vladislav_133
Elite
 
Сообщения: 1386
Зарегистрирован: 13 дек 2008, 18:08
Полное имя: П.В.Ю.

Re: Задачи олимпиады по программированию

Сообщение Vladislav_133 27 мар 2014, 12:09

Xardas писал(а):
Шифровка писал(а):Две шифровки, в которых совпадают по порядку номера слов, но различны
номера букв в этих словах, считаются тождественными.

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


Да, один вариант.
Ну, проверим, вы уж не беспокойтесь :)
Аватара пользователя
Vladislav_133
Elite
 
Сообщения: 1386
Зарегистрирован: 13 дек 2008, 18:08
Полное имя: П.В.Ю.

Re: Задачи олимпиады по программированию

Сообщение xdsl 27 мар 2014, 12:09

Vladislav_133 писал(а):
Xardas писал(а):Можно ли, по традиции, использовать stdin и stdout вместо input.txt и output.txt?

Не можно, а нужно :)

Ну-у-у нельзя так категорично. Боюсь, что многие виндоуз-ориентированные программисты и слов-то таких (stdin, stdout) не знают.
xdsl
 
Сообщения: 1236
Зарегистрирован: 09 дек 2008, 05:16
Откуда: ВЦ ШГПИ
Полное имя: Слинкин Д.А.

Re: Задачи олимпиады по программированию

Сообщение Vladislav_133 27 мар 2014, 12:15

А ведь много проще работать с потоком, чем создавать файл, писать туда, потом его закрывать.
Аватара пользователя
Vladislav_133
Elite
 
Сообщения: 1386
Зарегистрирован: 13 дек 2008, 18:08
Полное имя: П.В.Ю.

Re: Задачи олимпиады по программированию

Сообщение Xardas 27 мар 2014, 12:34

Будут ли влиять на проверку пустые строки, например, в конце выходных данных?
Xardas
 
Сообщения: 45
Зарегистрирован: 12 янв 2011, 11:23
Полное имя: Шахматов Александр Александрович

Re: Задачи олимпиады по программированию

Сообщение Chess 27 мар 2014, 12:39

В задаче "Прямая" "подряд идущие точки" имеются ввиду во входных данных или и на прямой тоже?
Т.е. для входных данных
1 1
2 2
3 3
1 2
4 4
Ответ: 3
А для входных данных
1 1
3 3
2 2
1 2
4 4
Ответ: тоже 3?
Chess
 
Сообщения: 13
Зарегистрирован: 18 фев 2009, 22:17
Полное имя: Владимир

Re: Задачи олимпиады по программированию

Сообщение Vladislav_133 27 мар 2014, 13:19

Xardas писал(а):Будут ли влиять на проверку пустые строки, например, в конце выходных данных?

Ну форматы то оговорены. Но если уж вам так хочется в конце поставить пустую строку, то можете ставить - не повлияет. :)
Аватара пользователя
Vladislav_133
Elite
 
Сообщения: 1386
Зарегистрирован: 13 дек 2008, 18:08
Полное имя: П.В.Ю.

Re: Задачи олимпиады по программированию

Сообщение Vladislav_133 27 мар 2014, 13:22

Chess писал(а):В задаче "Прямая" "подряд идущие точки" имеются ввиду во входных данных или и на прямой тоже?
Т.е. для входных данных
1 1
2 2
3 3
1 2
4 4
Ответ: 3
А для входных данных
1 1
3 3
2 2
1 2
4 4
Ответ: тоже 3?


Имеется в виду, что точки, находящиеся в списке, начиная с первой находятся на одной прямой. И в вашем и моем примере их три, разумеется. На прямой же точек бесконечно много :)
Аватара пользователя
Vladislav_133
Elite
 
Сообщения: 1386
Зарегистрирован: 13 дек 2008, 18:08
Полное имя: П.В.Ю.

Re: Задачи олимпиады по программированию

Сообщение StamNS 27 мар 2014, 14:06

Я немного недопонял задачу с прямой...
1 1
3 3
2 2
1 2
4 4
9 0
5 5
Тут ответ будет 3 или 5
StamNS
 
Сообщения: 1
Зарегистрирован: 27 мар 2014, 13:59
Полное имя: Салимгараев Н И

Re: Задачи олимпиады по программированию

Сообщение Vladislav_133 27 мар 2014, 14:13

Три подряд идущих точки начиная с первой находятся на прямой, значит 3.
Аватара пользователя
Vladislav_133
Elite
 
Сообщения: 1386
Зарегистрирован: 13 дек 2008, 18:08
Полное имя: П.В.Ю.

Re: Задачи олимпиады по программированию

Сообщение Антон 27 мар 2014, 15:19

В задаче "прямая", во входном файле могут ли повторяться точки, и нужно ли их считать, а так же координаты только целые числа, или же нет?
Антон
 
Сообщения: 6
Зарегистрирован: 26 мар 2014, 14:34
Полное имя: Тоха_(ДАС)

Re: Задачи олимпиады по программированию

Сообщение bdm1809 27 мар 2014, 15:33

В "Шифровке": нужно ли как то реагировать на отсутствие нужного символа в ключе (key="abc", text="abd"), или текст гарантированно состоит только из тех символов, которые есть в ключе?
bdm1809
 
Сообщения: 10
Зарегистрирован: 20 мар 2010, 14:10
Откуда: Шадринск
Полное имя: Бельков Д.М.

Re: Задачи олимпиады по программированию

Сообщение Vladislav_133 27 мар 2014, 15:34

Антон писал(а):В задаче "прямая", во входном файле могут ли повторяться точки, и нужно ли их считать, а так же координаты только целые числа, или же нет?


1. Нет, предполагается, что точки разные.
2. Нет в общем случае координаты вещественные. Просто в примере приводится такая красивая прямая, делящая угол первого квадранта пополам.
Аватара пользователя
Vladislav_133
Elite
 
Сообщения: 1386
Зарегистрирован: 13 дек 2008, 18:08
Полное имя: П.В.Ю.

Re: Задачи олимпиады по программированию

Сообщение Vladislav_133 27 мар 2014, 15:35

bdm1809 писал(а):В "Шифровке": нужно ли как то реагировать на отсутствие нужного символа в ключе (key="abc", text="abd"), или текст гарантированно состоит только из тех символов, которые есть в ключе?


Если нужного символа нет, значит зашифровать не получилось. Нет результата.
Аватара пользователя
Vladislav_133
Elite
 
Сообщения: 1386
Зарегистрирован: 13 дек 2008, 18:08
Полное имя: П.В.Ю.

Re: Задачи олимпиады по программированию

Сообщение Vladislav_133 27 мар 2014, 15:38

Особенностью задач этого года является то, что мы не стали описывать в них подробную спецификацию, указывающую, как программа должна реагировать в разных граничных случаях. Причину этому, я пока обсуждать не буду. Можно обсудить такой подход в дискуссии после олимпиады.
Аватара пользователя
Vladislav_133
Elite
 
Сообщения: 1386
Зарегистрирован: 13 дек 2008, 18:08
Полное имя: П.В.Ю.

Re: Задачи олимпиады по программированию

Сообщение bdm1809 27 мар 2014, 15:49

in_place :D
bdm1809
 
Сообщения: 10
Зарегистрирован: 20 мар 2010, 14:10
Откуда: Шадринск
Полное имя: Бельков Д.М.

Re: Задачи олимпиады по программированию

Сообщение Xardas 27 мар 2014, 17:43

Шахматная задача писал(а):Решение задачи подразумевает нахождение такой
комбинации ходов, что при любом возможном ответе на первый ход белых черные
получают мат вторым ходом белых

Таким образом, во 2 строке выходных данных может быть любой ход черных?
Xardas
 
Сообщения: 45
Зарегистрирован: 12 янв 2011, 11:23
Полное имя: Шахматов Александр Александрович

Re: Задачи олимпиады по программированию

Сообщение xdsl 27 мар 2014, 18:14

Xardas писал(а):Таким образом, во 2 строке выходных данных может быть любой ход черных?
Нет, конечно. Любой возможный по шахматным правилам.
Кстати, обнаружил в последнем абзаце Chess10 неточность в своем комментарии. Вернее, тафтологию. Написано:
Например, в первом и втором примере ход черных может быть произвольным в рамках шахматных правил, а в третьем примере пешка может превратиться не только в ферзя, но и ладью.
Масло маслянное получилось, потому-что в первом примере в рамках шахматных правил король "обязан" рубить ладью, иначе ему из-под шаха не уйти. Поэтому в рамках шахматных правил в первом примере возможен только один ход.
Следовало, наверное, сказать: Например, в во всех примерах ход черных может быть произвольным в рамках шахматных правил, а в третьем примере пешка может превратиться не только в ферзя, но и ладью.

Любой из вариантов хода черных в соответствии с шахматными правилами считается верным, поэтому студенческие результаты буду прогонять через проверочную программу, которую как раз сейчас пишу.
xdsl
 
Сообщения: 1236
Зарегистрирован: 09 дек 2008, 05:16
Откуда: ВЦ ШГПИ
Полное имя: Слинкин Д.А.

След.

Вернуться в Олимпиада по программированию

Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 0