Этот блог посвящен вопросам подготовки к олимпиадам по программированию и самой технологии программирования. Используемый язык программирования предпочитаю Паскаль. С некоторых пор стала подробнее изучать Си, так что теперь могу поделиться примерами и на Си. Не все мне известно, но то, что знаю — делюсь с Вами.
Страницы
Поиск по этому блогу
вторник, 15 мая 2012 г.
Некоторые способы решения задач
| 8 | |||||||
| 7 | |||||||
| 6 | |||||||
| 5 | |||||||
| 4 | |||||||
| 3 | |||||||
| 2 | |||||||
| 1 | |||||||
| A | B | C | D | E | F | G | H |
| Белые | Черные | Ходы | ||
| Король | Король | Король ходит в любое поле на 1 клетку | ||
| Ферзь | Ферзь | Ферзь ходит в любом направлении на любое поле | ||
| Ладья | Ладья | Ладья ходит по вертикали или по горизонтали | ||
| Слон | Слон | Слон ходит по диагональным направлениям | ||
| Конь | Конь | Конь ходит «углом»: 2 прямо/назад – 1 влево/вправо или 1 прямо/назад – 2 влево/вправо | ||
| Пешка | Пешка | Пешка ходит прямо, но рубит по диагонали на 1 клетку вперед | ||
Решение: Задача на двумерный массив и последовательную проверку правильности ходов. Сложность состоит в проверке ходов для каждой фигуры и проверке правильности ходов: после черных идут белые, после белых — черные. Примерный код программы:
program project3;
var a:array[‘1′..’8′,’a’..’h’]of char;
r1,c1,r2,c2,g,r,c,f,d,h:char;
flag:boolean;
k,i,j:integer;
<белый конь>
function hodnw(r1,c1,r2,c2:char):boolean;
begin
hodnw:=true;
if ((abs(ord(r1)-ord(r2))=2)and(abs(ord(c1)-ord(c2))=1))or
((abs(ord(r1)-ord(r2))=1)and(abs(ord(c1)-ord(c2))=2))
then begin a[r2,c2]:=’n’; a[r1,c1]:=’.’;end
else hodnw:=false;
end;
<черый конь>
function hodnb(r1,c1,r2,c2:char):boolean;
begin
hodnb:=true;
if ((abs(ord(r1)-ord(r2))=2)and(abs(ord(c1)-ord(c2))=1))or
((abs(ord(r1)-ord(r2))=1)and(abs(ord(c1)-ord(c2))=2))
then begin a[r2,c2]:=’N’; a[r1,c1]:=’.’;end
else hodnb:=false;
end;
<белый король>
function hodkw(r1,c1,r2,c2:char):boolean;
begin
hodkw:=true;
if (abs(ord(r1)-ord(r2))
<черный король>
function hodkb(r1,c1,r2,c2:char):boolean;
begin
hodkb:=true;
if (abs(ord(r1)-ord(r2))
<белая ладья>
function hodrw(r1,c1,r2,c2:char):boolean;
var g,f,h,d,c,r:char;
begin
hodrw:=true;
if ((abs(ord(r1)-ord(r2))=0)and (abs(ord(c1)-ord(c2))>0))or
((abs(ord(r1)-ord(r2))>0)and (abs(ord(c1)-ord(c2))=0))
then begin
if c1=c2 then begin
if(r1 ‘.’ then hodrw:=false;
end;
if r1=r2 then begin
if(c1 ‘.’ then hodrw:=false;
end;
a[r2,c2]:=’r’; a[r1,c1]:=’.’;
end
else hodrw:=false;
end;
<черная ладья>
function hodrb(r1,c1,r2,c2:char):boolean;
var g,f,h,d,c,r:char;
begin
hodrb:=true;
if ((abs(ord(r1)-ord(r2))=0)and (abs(ord(c1)-ord(c2))>0))or
((abs(ord(r1)-ord(r2))>0)and (abs(ord(c1)-ord(c2))=0))
then begin
if c1=c2 then begin
if(r1 ‘.’ then hodrb:=false;
end;
if r1=r2 then begin
if(c1 ‘.’ then hodrb:=false;
end;
a[r2,c2]:=’R’; a[r1,c1]:=’.’;
end
else hodrb:=false;
end;
<белый слон>
function hodbw(r1,c1,r2,c2:char):boolean;
var g,f,h,d,r:char;i:integer;
begin
hodbw:=true;
if (abs(ord(r1)-ord(r2))=abs(ord(c1)-ord(c2)))
then begin
if(r1 ‘.’ then hodbw:=false;
end;
a[r2,c2]:=’b’; a[r1,c1]:=’.’;
end
else hodbw:=false;
end;
<черный слон>
function hodbb(r1,c1,r2,c2:char):boolean;
var g,f,h,d,r:char;i:integer;
begin
hodbb:=true;
if (abs(ord(r1)-ord(r2))=abs(ord(c1)-ord(c2)))
then begin
if(r1 ‘.’ then hodbb:=false;
end;
a[r2,c2]:=’B’; a[r1,c1]:=’.’;
end
else hodbb:=false;
end;
<белый ферзь>
function hodqw(r1,c1,r2,c2:char):boolean;
begin
hodqw:=hodbw(r1,c1,r2,c2)or hodrw(r1,c1,r2,c2);
a[r2,c2]:=’q’; a[r1,c1]:=’.’;
end;
<черный ферзь>
function hodqb(r1,c1,r2,c2:char):boolean;
begin
hodqb:=hodbb(r1,c1,r2,c2) or hodrb(r1,c1,r2,c2);
a[r2,c2]:=’Q’; a[r1,c1]:=’.’;
end;
<белая пешка>
function hodpw(r1,c1,r2,c2:char):boolean;
begin
hodpw:=true;
if ((ord(r2)-ord(r1)=1)and (ord(c1)-ord(c2)=0))or
((ord(r2)-ord(r1)=2)and (ord(c1)-ord(c2)=0)and(r2=’4′))or
((ord(r2)-ord(r1)=1)and (abs(ord(c1)-ord(c2))=1)and (a[r2,c2]<>’.’))
then begin a[r2,c2]:=’p’; a[r1,c1]:=’.’; end
else hodpw:=false;
end;
<черная пешка>
function hodpb(r1,c1,r2,c2:char):boolean;
begin
hodpb:=true;
if ((ord(r1)-ord(r2)=1)and (ord(c1)-ord(c2)=0))or
((ord(r1)-ord(r2)=2)and (ord(c1)-ord(c2)=0)and(r2=’5′))or
((ord(r1)-ord(r2)=1)and (abs(ord(c1)-ord(c2))=1)and (a[r2,c2]<>’.’))
then begin a[r2,c2]:=’P’; a[r1,c1]:=’.’; end
else hodpb:=false;
end;
begin
assign(input,’input.txt’);reset(input);
assign(output,’output.txt’);rewrite(output);
<заполняем массив игрового поля перед началом игры>
a[‘1′,’a’]:=’r’;
a[‘1′,’b’]:=’n’;
a[‘1′,’c’]:=’b’;
a[‘1′,’d’]:=’q’;
a[‘1′,’e’]:=’k’;
a[‘1′,’f’]:=’b’;
a[‘1′,’g’]:=’n’;
a[‘1′,’h’]:=’r’;
for c:=’a’ to ‘h’ do begin a[‘2′,c]:=’p’; a[‘7′,c]:=’P’; a[‘8’,c]:=upcase(a[‘1’,c]);end;
for r:=’3′ to ‘6’ do
for c:=’a’ to ‘h’ do a[r,c]:=’.’;
<переменная k отвечает за ход: белые k=1, черные k=-1>
k:=0;
<переменная flag отвечает за правильность хода фигуры>
flag:=true;
<считываем первый ход и определяем кто ходит первым>
readln(c1,r1,g,c2,r2);
if (a[r1,c1]=’.’) then flag:=false <пустая клетка ходить не может>
else
if (a[r1,c1] in [‘n’,’p’]) and (a[r2,c2] = ‘.’) <первым ходом может быть только конем или пешкой,
причем ее ход должен быть на пустую клетку>
then begin k:=1 ; <если первым ходят белые>
case a[r1,c1] of
‘n’:flag:=hodnw(r1,c1,r2,c2);
‘p’:flag:=hodpw(r1,c1,r2,c2);
end
end
else
if (a[r1,c1] in [‘N’,’P’] )and(a[r2,c2] = ‘.’)
then begin k:=-1 ;<если первым ходят черные>
case a[r1,c1] of
‘N’:flag:=hodNB(r1,c1,c2,r2);
‘P’:flag:=hodPB(r1,c1,c2,r2);
end
end
else flag:=false; <во всех остальных случаях ход не верен>
while flag and not eof() do begin <пока можно ходить и есть еще строки.
В этом случае окончание ввода с клавиатуры Ctrl+Z,Enter>
readln(c1,r1,g,c2,r2);
if (a[r1,c1]=’.’) then begin flag:=false;break; end;
if (k=-1)and(a[r1,c1] in [‘r’,’n’,’b’,’k’,’q’,’p’] )and (a[r2,c2] in [‘.’,’N’,’R’,’B’,’K’,’Q’,’P’])
then begin
k:=1;
case a[r1,c1] of
‘n’:flag:=hodnw(r1,c1,r2,c2);
‘p’:flag:=hodpw(r1,c1,r2,c2);
‘k’:flag:=hodkw(r1,c1,r2,c2);
‘b’:flag:=hodbw(r1,c1,r2,c2);
‘r’:flag:=hodrw(r1,c1,r2,c2);
‘q’:flag:=hodqw(r1,c1,r2,c2)
else
flag:=false;
end;
end else
if (k=1)and(a[r1,c1] in [‘R’,’N’,’B’,’K’,’Q’,’P’] ) and (a[r2,c2] in [‘.’,’n’,’r’,’b’,’k’,’q’,’p’])
then begin
k:=-1;
case a[r1,c1] of
‘N’:flag:=hodnb(r1,c1,r2,c2);
‘P’:flag:=hodpb(r1,c1,r2,c2);
‘K’:flag:=hodkb(r1,c1,r2,c2);
‘B’:flag:=hodbb(r1,c1,r2,c2);
‘R’:flag:=hodrb(r1,c1,r2,c2);
‘Q’:flag:=hodqb(r1,c1,r2,c2)
else
flag:=false;
end;
end else flag:=false;
end;
<вывод результата>
if flag then
for r:=’8′ downto ‘1’ do begin
for c:=’a’ to ‘h’ do write(a[r,c]);
writeln;
end else
write(‘No solution’);
close(output);
end.
Сложнее всего придумать для этой задачи адекватные тесты, чтобы проверялись всевозможные неверные и верные ходы.
В соревнованиях по бегу принимают участие N спортсменов (3 ≤ N ≤ 1000). Результаты забега занесены в массив по порядку номеров участников. Все результаты участников различны. Определить время (результат) бронзового призёра.
Ввод
Первая строка содержит N — количество участников забега. Следующая строка содержит результаты каждого участника забега (через пробел) в последовательности номеров участников.
Вывод
На экран выводится время (результат) бронзового призёра.
Не могу решить эту задачу (проходит 10 из 12 проверок): Задача №33
Подскажите, что надо поменять, что бы программа прошла?
Закрыт по причине того, что не по теме участниками Abyx, Suvitruf says Reinstate Monica ♦ , cheops, Arhad-the-dev, Kromster says support Monica 1 ноя ’17 в 12:28 .
Похоже, этот вопрос не соответствует тематике сайта. Те, кто голосовал за его закрытие, указывали следующую причину:
- "Вопросы с просьбами помочь с отладкой («почему этот код не работает?») должны включать желаемое поведение, конкретную проблему или ошибку и минимальный код для её воспроизведения прямо в вопросе. Вопросы без явного описания проблемы бесполезны для остальных посетителей. См. Как создать минимальный, самодостаточный и воспроизводимый пример." – Suvitruf says Reinstate Monica, cheops, Kromster says support Monica
Если вопрос можно переформулировать согласно правилам, изложенным в справке, отредактируйте его.
Привет, братишки и сестрички по коду!
Недавно наткнулся на сайт e-olimp.com. Заметил, что там проходит много крутых контестов и неплохой архив. Но ходят слухи, якобы сайт этот немного кривоват. Поэтому:
1) Прошу высказать свое мнение об этом ресурсе
2) Какие есть еще архивы задач кроме здешнего архива, тимуса и ацмп?
3) С каких тем лучше начать синему? Хочу стать красным как можно быстрее)
Надеюсь на вашу помощь, ребятулечки!
BanderLog- 5 лет назад
- 20
BanderLog
5 лет назад
20
На e-olimp сейчас как раз уже мало контестов (разве что различные спирали и т.д., но не полноценный АСМ). Но в архиве — куча старых. Система у них действительно оооооочень глючная и странная. К примеру, один и тот же код может получать разные вердикты, потому что попал на разные сервера, на которых тесты не совпадают. Или к задаче могли "забыть" подключить чекер. Есть еще банальное "если таймит, то надо послать еще раз — может быть, не повезло с сервером" — тестируют на машинах очень разной мощности.
Несколько линков на архивы можно найти здесь. Или в гугле:)
С каких тем начать/как готовиться/в чем секрет/что нужно знать — стандартные вопросы, которые поднимают едва ли не каждые две недели. Поиск по сайту тебе в помощь, теги advice, training, guide, подготовка, strategy, practice и другие аналогичные.
сейчас работает вроде только одна тестилка, но она падает почти каждый день))
Задачи там отличные, чекер ужасен. К примеру, вывод массива циклом
Получаем WA из-за пробела после последнего элемента и т.д и т.п
И повторно WA из-за отсутствия перевода на новую строку)
На самом деле к этому быстро привыкаешь, входит в привычку.
Намного хуже, если есть задача, в которой написано "если ответов несколько, выведите любой", а чекер забыли подключить, и из всех ответов на самом деле система принимает только один.
А еще бесит фраза "в первой строке указано количество тестов" и на дано ограничение на их количество.
Также частенько бывают крайне непонятные условия
Эта фраза — это уже не вина e-olimp. Что было в оригинальном условии — то и скопировали. На многих контестах в задачах не указывают ограничения на число тестов. При этом иногда организаторы могут ответить на этот вопрос, если написать клар:)
Непонятность условий — тоже вопрос к авторам контеста, с которого взяли задачу. Если читать условия на украинском, то обычно сразу видно, что их переводили транслейтом или это делал человек, для которого украинский не родной. Если на контесте русских условий не было, то и с переводом на русский примерно такая же картина. Но оригинальные условия почти всегда качественны. Разве что иногда их криво копируют:)
Ибо нефиг. Пробел — такой же символ, как и остальные. Представь, что в конце, вместо перевода строки кто-то вывел букву "а".
Да ладно. Между пробелом и символом ‘a’ все-таки есть немалая разница, и давать WA из-за лишнего пробела в конце строки — моветон. Все-таки, если в задаче требуется просто вывести несколько чисел, не грех в чекере считать по токенам — всем же лучше будет. А если автор считает, что стоит давать штрафную посылку за то, что участник, скажем, вывел n чисел через пробел, а не разделяя переводами строки, как хочет автор, то я с ним не согласен.
Люблю людей, которые хотят от авторов очень четкого условия и ограничения на входные данные, время и память, при этом злятся, когда им дали ВА за лишнй пробел. Обычно в памятках перед соревнованиями пишут, что не должно быть лишних символов, про концы строк и файла, поэтому если получил ВА из-за лишнего пробела, то угадай, кто дурак.
Обычно все возможные комбинации пробелов/endl/табов после/перед/между аутпутом проверяют на пробном туре, от греха подальше:)
Для чего даются четкие МЛи и ТЛи? Для удобства участников. Для чего даются умолчанные ограничения "не выводите ни в коем случае лишнего пробела в конце строки"? Для удобства участников?
Давая задачу на online judge, которая провисит на нем не один год, и которую решит не один человек, можно потратить на несколько минут больше, и сделать нормальный чекер (да что там делать, все сделано за вас уже, лишь возьми да прикрути). Если кому-то лень это сделать — это уже неуважение к людям, которые будут тратить свое время, решая задачу.
Имхо, если цель контеста — придираться к пробелам, то и условие задачи должно выглядеть суровее:
Например задача отсортировать числа и напечатать отсортированный массив в строку должна заканчиваться так:
вывести отсортированный массив, распечатав его числа в десятичной системе без ведущих нулей, в порядке возрастания индексов массива. Использовать символьную таблицу совместимую с ASCII, разделять числа ровно одним пробелом (код 32). В конце строки добавить символы перехода на новую строку в windows-формате, т.е. символы с кодами 13 и 10.
Смахивает на задротство, извините. %)
Да я понимаю, что все это крайности, но не понимаю, зачем об этом холиварить, если формально зачастую об этом предупреждают, и лечится это одной строкой.
Кстати, мне одному интересно зачем там контесты с ПТЗ? Причем не только старые, но и очень свежие! Мало того, что их там все равно никто не решает, так и непонятно откуда они там берутся и кто их сливает туда(ведь их нигде не публикуют и материалы дают только участникам с требованием, что они не будут их раздавать).
Что значит "зачем"? Хуже никому не станет от того, что они там есть. Возможно, кто-то когда-то что-то и порешает.
Тогда почему их нет на КФ? А насчет хуже- там довольно много школьников(в основном), которые могут испортить себе тренировку в универе. Та же примерно история, как я понимаю, с виртуальными контестами финалов на сервере снарка- туда всех подряд не пускают тоже:)
Я не знаю причин, по которым орги ПТЗ скрывают все. Есть только догадки насчет того, чего они боятся. Мне в этом смысле больше импонируют поляки, которые выкладывают материалы со всех своих соревнований, и выпустили сборник с решениями их лучших задач. Почувствуй разницу.
Испортить тренировку в универе? Да ладно, вот прям прорешают все еще в школе. Сейчас в сети число доступных контестов исчисляется тысячами, если они вдруг все это прорешают.
Или ПЗ почему-то такой особенный, что его нельзя решать? Он чем-то принципиально отличается от четвертьфиналов/полуфиналов/других сборов? Я еще понимаю — финал. Священные и неприкасаемые задачи финала, которые только для избранных. И которые нужно решать именно в режиме тренировки за неделю до финала. Потому что будь у вас хоть 400 командных тренировок до этого — без 5 тренировок конкретно на задачах финала вы свой финал сольете в одни ворота. Потому что там особенные задачи. И особенный контест. И вообще все особенное. ОК, пускай:) Шутки шутками, эти задачи можно решать на livearchive, при желании) Но это отдельный разговор.
А ПЗ чем такой особенный? Я никогда не был ни на финале, ни в ПЗ, так что объясните. Те контесты, которые доступны в сети, и которые я решал (ASC в тренировках здесь, кое-что на е-олимпе, кое-что в других местах) — вполне себе обычные контесты.
Я действительно не могу понять логику. Если человек хочет решать конкретные задачи — он почти наверняка их достанет и будет решать. Если он считает нужным не решать тот или иной контест — он его не решает. Согласен со словами Rubanenko, такая политика выглядит для меня странной, никому не будет хуже от того, что материалы будут доступны. Это все равно что задачи онсайтов ТСО хранить на закрытом сервере и давать к ним доступ только тем, кто вышел в этом году на онсайт. Или не пускать пользователей из div2 решать задачи div1 CF.
В целом мне тоже нравится больше когда все общедоступно. Но правила есть правила и их надо выполнять, наверняка какой-то смысл в них вкладывался. Например мы регулярно сталкивались когда писали контесты ПТЗ на КФ, что 1-2 не очень простые задачи мы решали еще в школе(думаю понятно, что это не на пользу тренировке) и даже не знали откуда они тогда.
ПТЗ действительно отличаются. Для нас эти сборы были на порядок сложнее всех командных контестов, что мы решали раньше. Мы сдавали в среднем 3-4 задачи, почти никогда нельзя было назвать хоть одну из них халявой и для первого раза мы остались довольны своим результатом. Те контесты, что здесь лежат довольно старые по большей части и задачи уже стали не такими оригинальными и ориентироваться на их сложность сейчас ошибочно.
Наверное понятно, что я хотел сказать, на этом свое участие в обсуждении заканчиваю.
