Домашнее задание: написать систему спутникового наведения ракет на ВМФ потенциального противника ;).
Задача g6_1029: Палиндромы
Дана последовательность символов s1, s2, ..., sn, 1 a.
Найти количество символов, содержащихся в самом длинном палиндроме.
Формат входных данных
Входной файл INPUT.TXT содержит в первой строке целое число n. Во второй строке идет последовательность символов s1, s2, ..., sn.
Пример:
asDFr rtYUUYtr KLOPF vccv
Формат выходных данных
Выходной файл OUTPUT.TXT должен содержать количество символов, содержащихся в самом длинном палиндроме, если исходная последовательность не содержит ни одного палиндрома, файл должен содержать цифру 0 (нуль).
Пример:
8
Решение g6_1029:
Опять простая задача :(
Инициализируем максимальную длину палиндрома нулем. Читаем символ, если он не пробел, то добавляем к строке, если пробел - проверяем является ли строка палиндромом, а затем обнуляем эту строку.
Как проверять, является ли строка палиндромом? Очень просто. Заводим цикл от 1 до половины длины строки. Проверяем, если S[k] S[length(S)+1-k] - тогда строка не палиндром. Если строка оказалась палиндромом, то проверяем, если length(S) > max(максимальное кол-во букв в палиндроме), то max := length(S).
В конце просто выводим max (если палиндромов не было, то max = 0, так мы его инициализировали).
Задача g6_1030: Лошадью ходи! (DOOI)
Даны обозначения двух полей шахматной доски, на которых стоят конь и пешка. Найти минимальное количество ходов, за которые конь доберется до пешки, если последняя стоит на месте. Координаты коня и пешки задаются как натуральные числа, от левого нижнего угла шахматной доски.
Формат входных данных:
Первая строка входного файла input.txt содержит пару натуральных чисел, координаты коня; вторая - пару чисел, координаты пешки.
Формат выходных данных:
Выходной файл output.txt содержит одно число - количество ходов коня (можно и последовательные координаты этих ходов).
input.txt:
3 4
6 4
output.txt:
3
Решение g6_1030:
Задача, присланная нашими партнерами по ДООИ. Ее надо решить двум командам, но я решил, что партнеры не обидятся, если я разберу их задачу на своем сайте.
Первая идея, которая пришла мне в голову - рекурсивное решение. Идея неправильная (было установлено опытным путем - полный перебор жутко тормозная вещь). Вторая идея это нерекурсивный флуд (заливка) всего поля. Заполним всю доску кодом 255 (чтоб не путаться). От начальной позиции (присвоим этой клетке на доске значение 0) во все возможные позиции, на которые конь может переместиться за один ход, ставим 1. Затем сканируем всю доску, как только нашли значение 1 во все возможные клетки, куда конь может сходить ставим 2, но это только в том случае, если там стоит 255, т.е. конь там еще не был, иначе получится не кратчайший маршрут. Повторяем сканирование для 2, 3 и т.д. до тех пор, пока в одной из свежезаполненных клеток не напоремся на пешку. Если это произошло, то выводим значение из этой клетки - кратчайшее расстояние до позиции коня.
Теперь перейдем ко второму вопросу (можно, значит нужно). Заведем массив для хранения координат коня размерностью 64 (а вдруг долго топтаться будет). Вот теперь-то нам и пригодится рекурсия (хорошо, что я свою процедуру закомментировал, а не стер!). От конечной позиции (где стоит пешка) проверяем все возможные клетки, откуда туда мог прийти конь (на 1 меньше чем кол-во ходов итоговое). Как только найдем, занесем в элемент массива с номером, равным итоговому количеству ходов коня его координаты, затем уменьшаем счетчик, изначально равный количеству ходов коня до пешки, на 1. Запускаем рекурсивную процедуру для позиции, откуда пришел конь и т.д. В конце (когда дойдем до клеточки со значением 1 - первый ход) выводим все содержимое массива. Для примера из условия это: 5,5 7,6 6,4.
Я конечно понимаю, что рекурсия - вещь неудобоваримая, но лично я ее освоил еще в 8-ом классе, и даже написал научную работу на эту тему. Если что-то непонятно - пишите на мыло, буду пытаться объяснить :)
Задача g6_1031: Левые повороты (DOOI)
Маршрут движения автомобиля задан в виде координат вершин ломаной.
Необходимо определить количество левых поворотов (смежные участки ломаной не лежат на одной прямой). Автомобиль начинает движение с любой точки (!!!Здесь уточнение от меня - автомобиль начинает движение из первой вершины ломаной, а вот ее координаты любые!!!).
Формат входных данных:
Первая строка входного файла input.txt сомстоит из одного числа, количества звеньев ломаной; в последующих строках - пары натуральных чисел, координаты вершин ломаной.
Формат выходных данных:
Выходной файл output.txt содержит одно число - количество левых поворотов
input.txt:
4
1 1
2 2
3 2
3 3
2 3
output.txt:
2
Решение g6_1031:
Наконец-то геометрическая задача! (терпеть их не могу, если честно, но куда деваться). Звенья ломаной можно представить в виде векторов. А дальше я приведу кусок комментария Александра Николаевича Никитина:
Геометрические алгоритмы: С какой стороны вектора лежит точка?
Если vector(a) и vector(b) - вектора a и b соответственно, то:
vector(a)*vector(b) = ax*by - ay*bx = a*b*sin(beta-alfa)
ax,ay,bx,by - координаты концов векторов
a - длина вектора a
b - длина вектора b
alfa - угол альфа для вектора a
beta - угол бета для вектора b
Вывод: при общей начальной точке двух векторов их векторное произведение больше нуля, если второй вектор направлен влево от первого, и меньше нуля, если вправо.
Если известны две точки, то вектор, основанный на них можно получить вычитанием двух векторов направленных из начала координат: например, есть точка A и точка B
вектор|AB| = Вектор|B| - Вектор|A|, иным словом AB_x = Bx-Ax, AB_y= By-Ay
Таким образом, получается:
Если есть вектор |AB|, заданный координатами ax,ay,bx,by и точка px,py, то для того чтобы узнать лежит ли она слева или справа, надо узнать знак произведения:
(bx-ax)*(py-ay)-(by-ay)*(px-ax)
Итак, вроде бы все понятно (сам прочитал первый раз в жизни - раньше всегда брал готовую функцию). У нас есть два вектора 1-2 и 1-3 если 3 левее вектора 1-2, то поворот левый, иначе не левый (логично). Точно также для вектора 2-3 и точки 4 и т.д.
Задача g6_1032: Почти Крэг Туми (DOOI)
Составить программу, которая будет находить, на сколько квадратов, стороны котоых выражены натуральными числами, можно разрезать данный прямоугольник, если от него каждый раз отрезается квадрат максимально большой площади.
Формат входных данных:
Входной файл input.txt состоит из одной строки, содержащей два натуральных числа - стороны прямоугольника.
Формат выходных данных:
Выходной файл output.txt содержит одно число - количество квадратов
input.txt:
3 4
6 4
output.txt:
3
Решение g6_1032:
А вам слабо решить эту задачу с листом бумаги, ножницами, без компьютера и с завязанными глазами? А сделать тоже самое без ножниц и с компьютером?! Мне слабо.
Обозначим стороны прямоугольника за A и B. Сделаем так, чтобы A было больше B (например с помощью процедуры swap, как в задаче 1001. Теперь заведем переменную C, в которой будет храниться количество квадратиков. Будем повторять следующие действия пока одна из сторон (B) не станет равна 0:
1) B меньше чем A, следовательно надо откромсать сколько можем квадратов B*B от прямоугольника A*B. Т.е. C := C + A div B;
2) Вычислим размеры останков прямоугольника: A := A mod B (не смогли отрезать).
3) swap(A, B)!!!!!
Задача g6_1033: Прицельное метание помидор
Михаил Густокашин
В детстве у меня было развлечение - кидаться помидорами с балкона, так чтобы забрызгать прогнившими внутренностями помидор прохожих. Я тогда подметил, что на каждый кубический сантиметр помидоры (кстати, она имеет форму идеального шара) приходится квадратный метр поверхности (это объясняется тем, что помидора падает с 7-го этажа и размазывается по большой площади мелкими брызгами). Т.е. помидора объемом в 3 куб. см. забрызгает круг с центром в точке падения площадью 3 кв. м.
Я наметил несколько точек, в которые я точно попаду. В какую из этих точек надо кинуть помидору наименьшего размера, чтобы забрызгать всех прохожих?
Входные данные:
В первой строке входного файла input.txt содержится число n - количество намеченных точек, в следующих n строках - координаты этих точек с точностью до 2 знаков после запятой. В следующей строке содержится m - количество человек, в последующих m строках - координаты людей. 1
Выходные данные:
В первой строке содержаться координаты точки, в которую надо кидать помидору, а во второй - наименьший радиус r помидоры в сантиметрах.
Пример входных данных:
1
0 0
2
1 0
0.5 0.5
Пример выходных данных:
0.00 0.00
0.91
Решение g6_1033:
Эту задачу я составил сам. От начала до конца :).
Первая часть решения похожа на решение задачи #1010 - Вирусы. Здесь точно так же надо находить максимальное из расстояний от точки до каждого человека, затем среди этих расстояний выбирать наименьшее.
Дальше идет интереснее. Мы нашли наилучшее R - расстояние от точки, до самого дальнего человека. Площадь круга S = Pi * R2. В то же время объем шара V = 4/3 * Pi * r3, где r - радиус помидоры в сантиметрах. Т.к 1 куб.см. размазывается по 1 кв.м., то имеем:
R2 = 4/3 * r3;
r3 = 3/4 * R2;
Введем переменную X = 3/4 * R2.
Все было бы хорошо, но в Паскале вроде бы нет функции которая считает кубический корень. Его нам придется посчитать самим. Для этого будем использовать способ двоичного приближения (дихотомии). Минимальный возможный радиус примем равный 0, а максимальный - заведомо больше максимально возможного (например 100, потому что таких помидор не бывает :). Примем радиус помидоры за среднее арифметическое минимума и максимума. Если r3 больше X, то следует приравнять максимум r (действительно, если объем и так больше, то при большем радиусе он будет только увеличиваться), если r3 меньше X, то приравниваем минимум радиусу. Повторяем эту операцию до тех пор, пока разница между максимумом и минимумом не станет меньше 0.01 или лучше 0.005 (так надежнее). Мы нашли кубический корень с заданной точностью.
Кстати, примерно такой же метод используется при подсчете многих хитрых функций в компьютере.
Задача g6_1034: Программистика
XIV Всероссийская олимпиада по информатике. 5-11 апреля 2002г. г. Пермь.
В Перми становится популярной игра "Программистика".
Для игры требуются плоские квадратные фишки 4-х видов, представляющие собой поле 3*3 с вырезанной центральной клеткой. В остальных клетках каждой фишки записаны числа от 1 до 8. Все виды фишек показаны на рисунке. Количество фишек каждого вида не ограничено.
Игра проводится на поле размером N*N. Первоначально все клетки поля заполнены единицами.
В начале игры Магистр несколько раз случайным образом помещает произвольные фишки на игровое поле так, что фишка попадает на поле целиком, а ее центральная клетка совпадает с одной из клеток поля. После помещения очередной фишки все числа в восьми клетках игрового поля, которые перекрывает фишка, умножаются на соответствующие числа в клетках фишки, и результаты становятся новыми значениями этих клеток игрового поля.
Таким образом, после окончания процесса размещения фишек игровое поле оказывается заполненным полученными произведениями. Далее Магистр передает получившееся поле игроку, которому необходимо установить для каждой клетки поля, сколько раз Магистр в нее помещал центральные клетки фишек.
Требуется для каждого входного файла, содержащего полученное Магистром поле, сформировать соответствующий ему выходной файл, в N строках которого содержится по N чисел, показывающих, сколько раз в соответствующую клетку помещались центральные клетки фишек.
Входные данные
В каталоге C:\TESTS\4 находятся 7 входных файлов с именами game.01, game.02, :, game.07. В первой строке каждого из этих файлов записано N (3 9.
Выходные данные
Каждый выходной файл должен состоять из N строк по N разделенных пробелами чисел, показывающих для каждой клетки поля, сколько раз в нее помещались центральные клетки фишек.
Вам требуется представить на тестирование 7 выходных файлов с именами:
Р[номер участника]_4.[номер теста]
где - пятизначный номер участника, 4 - номер задачи, - двузначный номер теста задачи.
Например, у участника с номером 21111 выходной файл для теста № 3 должен называться P21111_4.03
Пример
Входной файл game.0x
5
1 2 3 1 1
8 1 140 48 7
7 6 120 1 16
1 1 15 8 3
1 1 1 1 1
Выходной файл Р21111_4.0x
0 0 0 0 0
0 1 0 0 0
0 0 0 2 0
0 0 0 0 0
0 0 0 0 0
Примечание
Результатом решения задачи являются только 7 выходных файлов, которые и необходимо представить на проверку.
Решение g6_1034:
Прошу прощения, что долго не обновлял сайт - уезжал на Всероссийскую олимпиаду :). Вернулся с 28 местом и дипломом второй степени.
Это самая простая задача на олимпиаде имеет нестандартный вид. Здесь необходимо сдать не программу, а только выходные файлы, но чтобы их сгенерировать, все-таки нужно написать программку :)
Начнем просматривать игровое поле с левого верхнего угла(на верхней левый угол может влиять только карточка с центром в (2;2)). Будем пытаться поставить на клетку (2;2) все карточки, за исключением карточки номер 1. В случае, если карточку подставить можно, увеличиваем счетчик в точке (2;2) на 1, а значения окружающих ее клеток делим на числа, написанные на соответствующем месте карточки. Как только мы не сможем подставить ни одну из карточек с номерами от 2 до 4, перейдем к карточке 1(мы не переходили к ней раньше, т.к. неизвестно . Рассмотрим поле (2;1): у первой карточки на это место приходится число 2, у всех остальных числа: 7, 5, 3. Надо заметить что никакая комбинация из перемноженных чисел 3, 5 и 7 не даст 2k, т.к. будет нечетной. Проверим, на какую степень 2 мы можем разделить значение (2;1). Соответственное количество первых карточек имеет центр в точке (2;2). Обработаем для них другие покрываемые клеточки
Теперь представим, что самой верхней левой клеткой стала клетка (2;1). Повторим для нее те же операции. Когда мы достигнем верхней левой клетки (N - 2; 1) следующей за ней будет верхняя левая клетка (2;2). Повторим эту операцию, пока не проверим все поле. Если вы обработали все правильно, то оно должно быть заполнено единичками.
Всероссийская олимпиада, в сущности не такая уж и сложная ;).
Задача g6_1035: "Мы вас упакуем!"
Михаил Густокашин
В Тольятти началась новая грандиозная рекламная акция "Мы вас упакуем!" компании g6, производящей пластиковые пакеты. В ходе акции проводится массовая бесплатная раздача новой модели пластикового пакета от g6 - GEXANIUM, выдерживающего нагрузку до 150кг, рекламу на транспорте, в радио и теле эфире, с помощью сети интернет (особенно запомнился тольяттинцам бесплатный доступ к сети с 31 декабря по 7 января по телефону 666-666 login: 666, password: 666. Стоит заметить, что наибольшей популярностью пользовался сайт g6prog.narod.ru). Но не это самое главное, а самое главное это скидки на совершенно новый пакет с подогревом, mp3-плейером, картой flash-памяти на 128 мб., голосовым управлением и прочими наворотами, который называется xMSG666. К сожалению, этот пакет не предназначен для бесплатной раздачи, но g6 объявило о серьезном снижении цен на этот пакет. Здесь компания применила хитрый маркетинговый шаг. Например:
Пусть раньше пакет стоил 100$ (компания объявила, что независимо от инфляции цена не будет больше 255$, но и бесплатно раздаваться не будет). После скидки пакет стал стоить 50$. По идее компания должна была написать "Новый xMSG666 со скидкой 50%!", вместо этого компания стала писать "Новый xMSG666 со скидкой 100%!". То есть компания стала отнимать от старой цены новую и делить на новую цену, чтобы посчитать скидку, хотя на самом деле надо отнимать от старой цены новую, и делить на старую. По такому случаю в компании был проведен банкет. Там произошла одна интересная история: пожарник - Дядя Вася - выпил немного лишнего и по ошибке вместо туалета забрел в кабинет директора, ну и, естественно, воспользовался этим помещением как туалетом. Вот смеху то было.
Конкурент фирмы g6, компания Цуцик кучерявый (занимается производством холщовых мешков и сеток, кстати, по всем вопросом по приобретению данной продукции обращайтесь по телефону в Тольятти (8482) 13-13-13 - напечатано на правах рекламы), заметила "ошибку" менеджеров g6, и подала на "пластикового монстра g6" в суд (ходят слухи, что разгадать такую хитрую комбинацию простому смертному не по силом, а значит налицо промышленный шпионаж - тут волей-неволей задумаешься о Дяде Васе). Суд принял решение - если разница в правильном и неправильном подсчете скидки менее 5%, то компания g6 может продолжить продажи, иначе - компания будет оштрафована на сумму в 10000000$. Однако, вскоре планка была снижена до 10%. Сейчас в Тольятти существует много слухов на эту тему, которые, чтобы не утомлять читателя не будут приводиться в этом кратком обзоре.
Ваша задача определить судьбу компании.
Входные данные:
В первой строке содержится начальная цена пакета, во второй - цена со скидкой.
Выходные данные:
Следует вывести слово YES, если разница в подсчете скидок не более 10% (т.е. если от конечной скидки отнять начальную получится число меньше либо равное 10), и слово NO, если разница больше 10%.
Пример 1:
input.txt:
100
99
output.txt:
YES
Пример 2:
input.txt:
250
50
output.txt:
NO
Решение g6_1035:
Да уж... При составлении этой задачи мной преследовалась цель научить желающих заниматься решением олимпиадных задач отсеву, мягко говоря, "словесного поноса" в условии.
Переформулируем задачу. Дано два числа a и b. Найдем, какую часть составляет (a - b) от а и от b, обозначим части за c1 и c2. Если (c1 - c2) > 0.1 тогда выводим NO, иначе YES.
Вроде бы стало попроще. Мораль такая: дочитывайте задачи до конца.
Задача g6_1036: Хитрющая строка. По мотивам ICL-2002
Михаил Густокашин
В моем классе учится один парень - Ариф, который часто занимается на уроках математики в общем то математикой, но не совсем той, которой надо: то он выписывает в столбик квадраты всех чисел, то все степени двойки, то таблицу умножения до 100*100, короче говоря, наш Ариф - еще тот. Недавно получил 2 за контрольную, потому что на всех предыдущих уроках занимался далеко не тем, чем надо. Однажды он придумал себе новое развлечение - стал выписывать в строку (без пробелов) четвертые степени всех простых чисел подряд. У него получилась примерно такая строка:
16816252401...
Потом ему стало интересно можно ли определить, какая цифра стоит на n-ом месте в этой строке? Формулу подобрать он не смог, да наверное ее и нету. Задача состоит в том, что несмотря на отсутствие формулы, определить, какая цифра стоит на n-ом месте.
Входные данные:
Во входном файле input.txt содержится единственное число n (0
Выходные данные:
В выходном файле output.txt содержится одна цифра, которая стоит в этой строке на n-ом месте.
Пример 1:
input.txt:
1
output.txt:
1
Пример 2:
input.txt
5
output.txt
6
Решение g6_1036:
Опять моя задачка. Тут есть два решения (которые придумал я сам) - одно из них почему-то валится на 15000, а другое молотит все подряд.
Как искать простые числа? Надо найти округленный квадратный корень из числа и искать делители только от 2 до этого корня. Если у числа есть делители, то половина из них меньше либо равна его квадратному корню.
Первое решение(которое работает до 15000, почему-то): с оцениванием длины 4 степени. Суть этого решения состоит в том, что мы оцениваем длину 4 степени числа, для этого будем извлекать корень 4 степени из степеней 10 и если число лежит например между sqrt(sqrt(106)) и sqrt(sqrt(107)), включая sqrt(sqrt(106)), то длина его 4 степени будет 6 десятичных знаков. Будем отнимать от данного числа n полученное число, а в случае если длина получившейся четвертой степени больше номера необходимого элемента, то запустим хитрую процедуру извлечения цифры из типа данных extended. Если нам необходимо извлечь первую цифру, то для этого надо вывести округленный trunc'ом результат деления нашей 4 степени на 10(кол-во цифр в ней - 1). В противном случае найдем первую цифру, умножим ее на 10(кол-во цифр - 1) и отнимем полученное число от нашей 4 степени. Теперь уменьшим общее кол-во цифр и номер запрашиваемой цифры на 1.
Второе решение(работает чуть медленнее, но зато может посчитать практически любой член этой последовательности). Здесь используется длинная арифметика, похожая на задачу 2n. Алгоритм тут точно такой же, так что опишу только те хитрости, которые надо здесь применить. Во-первых: каждое число, которое необходимо возвести в 4 степень надо разбить на 10-тичные знаки с помощью mod и div, это вроде бы несложно. Еще одна хитрость состоит в том, что элементы массива будут иметь тип byte, а переменная для временной работы и флаг переноса - типа longint. Процедура будет умножать массив на число, чтобы найти 4 степень ее необходимо запустить 4 раза(вернее один раз разбить число на 10-тичные знаки и три раза запустить процедуру).
Третье решение (by Axel): длина 4 чтепени числа log(x)/log(10) округленные вверх.
Задача g6_1037: Анаграммы
Во входном файле input.txt содержится строка длиной не более 255 символов, в которой через один или несколько пробелов следуют слова. Найти все группы анаграмм(слов, составленных из одних и тех же букв) в этой строке и вывести в файл output.txt их каждую с новой строки, все слова должны идти через пробел в порядке, в котором они встречаются в строке.
input.txt
123 321 1234 12345 123456 231 132 3241 123457
output.txt
123 321 231 132
1234 3241
Решение g6_1037:
Для каждого слова надо составить массив-паспорт из 256 элементов. Если в слове встретилась какая либо буква, то нужно увеличить на 1 элемент с номером, который соответствует ее коду. Логично, что анаграммы будут иметь одинаковые паспорта. Для решения задачи требуется аккуратно выполнить все условия, т.е. не выводить одни и те же слова по 2 раза например и т.п. Для этого удобно использовать булевский массив размером в 128 элементов(это максимальное количество слов в строке, столько же нужно массивов-паспортов), в котором будет храниться флажок, уже выведено слово или нет. Аккуратности и удачи вам!
Задача g6_1038: Система защиты (XIV Всероссийская олимпиада по информатике)
"ПермьОлимпБанк" разработал сверхнадежную систему защиты ценных бумаг. В правом верхнем углу любой бумаги должно присутствовать прямоугольное изображение в виде черно-белого рисунка. Для определения подлинности документов была создана библиотека контрольных элементов. Если документ подлинный, то в изображении на документе заданное количество раз присутствует каждый контрольный элемент из библиотеки. В библиотеке нет совпадающих элементов.
Система контроля после сканирования получает изображение в виде цифрового массива N M (N
Контрольный элемент представляется массивом размером L*L (L
Требуется для каждого входного файла сформировать соответствующий ему выходной файл, в котором записано, сколько раз каждый элемент библиотеки встречается в изображении, описанном во входном файле.
Входные данные
В каталоге С:\TESTS\6 находятся 13 входных файлов с именами CONTROL.01, CONTROL.02, ..., CONTROL.13.
В первой строке каждого из этих входных файлов записаны через пробел числа N, M, K, L.
Далее следуют по порядку К блоков, соответствующих элементам контрольного образца в библиотеке. Каждый блок состоит из L строк по L цифр (ноль или единица). После каждого блока следует пустая строка.
В последующих N строках записаны по M цифр в каждой, соответствующих изображению.
Выходные данные
Вам требуется сдать 13 выходных файлов с именами:
P"номер участника"_6."номер теста"
где "номер участника" - пятизначный номер участника, 6 - номер задачи, "номер теста" - двузначный номер теста задачи.
Например, у участника с номером 21111 выходной файл для теста из файла CONTROL.03 должен называться P21111_6.03
Каждый выходной файл должен содержать К строк.
В каждой строке содержится два числа: номер контрольного элемента из библиотеки и число его обнаружений (0 - если элемент не обнаружен).
Номер контрольного элемента из библиотеки в первой строке равен 1, во второй - 2 и т.д.
Все числа в строках должны быть разделены пробелом.
Например, изображению на рис. 1 и контрольным элементам на рис. 2 соответствуют представленные ниже входной и выходной файлы.
Входной файл CONTROL.xx
8 7 4 4
1001
1111
1001
1001
1001
1001
1001
1001
0000
0000
0000
0000
0010
1111
0010
0010
1001001
1001001
1001001
1111111
1001001
1001001
1001001
1001001
Выходной файл Pnnnnn_6.xx
1 2
2 2
3 0
4 1
Решение g6_1038:
Классная задачка! Я больше нигде не видел входных файлов по 100 мегабайт! Ну, теперь перейдем к решению.
На разборе задач после олимпиады нам рассказали, как решить эту задачу (а частично я решил ее на олимпиаде, но тормозила она жутко) - но она была последней, а я перестал воспринимать информацию после 3 задачи :), так что придется мне рассказывать свое решение, которое я придумал сразу после окончания олимпиады :(.
Каждая вертикальная строка контрольного элемента состоит из произвольного количества нулей и единиц, причем общее количество этих нулей и единиц меньше либо равно 50. Эту последовательность можно считать двоичной записью числа, однако в Borland Pascal нет чисел такой размерности (про double, extended и т.п. молчу - т.к. они тормозят и не лезут в память), однако во Free Pascal, который предлагается на олимпиаде вместе с Borland Pascal, существует целочисленный тип данных int64 и ограничение в памяти помягче - 2Гб. Free Pascal вы можете скачать на официальном сайте freepascal.org - советую качать версию win32 или под Linux(если он у вас есть), потому что go32v2 глючит еще страшнее, чем две предыдущие. Во Free есть несколько особенностей - в конце надо ставить close(output), потому что автоматически он этого не делает, ставить скобки в арифметических выражениях, а то он иногда путает порядок действий (у меня такого не было - рассказали), и еще: int64 не поддерживает операции mod и не может быть использован как счетчик в цикле.
Итак, для каждой строки вычислим уникальное число, т.е. которое однозначно определяет именно эту строку. В случае если нам встретилась единица, то прибавляем к числу 1 и при каждой новой встретившейся цифре увеличиваем число вдвое. Вертикальной строке 1111 будет соответствовать число 15, строке 0001 - число 1 и т.п. Теперь каждый шаблон представлен L числами длиной до 50 двоичных цифр.
Проведем подобную операцию для первых L строк изображения - получим до 10000 чисел, каждое из которых длиной до 50 двоичных знаков. Теперь просто начнем поиск каждого шаблона (50 последовательных чисел) в строке (10000 последовательных чисел). Это, можно сказать, поиск подстроки в строке. Для ускорения этого процесса можно использовать хеш-функции. После того, как мы проверили все шаблоны, нам необходимо спуститься на одну строку вниз. Для этого из чисел строки больших либо равных 2L вычитаем 2L, т.е. убираем первую цифру. Теперь умножим полученные числа на 2 (освободим место для нового ряда. В случае если встретилась 1, то прибавим к числу строки 1. Так будем продолжать до конца входного файла.
Хотелось бы сказать, что заметное ускорение в работе даст использование вместо типизированного файла нетипизированного, т.к. Pascal читает из нетипизированного файла намного быстрее.
Задача g6_1039: Виза (ИМ-2002 СамГУ)
Жители одного государства очень любят различные математические головоломки. Даже тот, кто желает получить въездную визу, должен решить задачу: отыскать ключевое слово. Условие задачи таково:
На листке написано несколько длинных чисел. Если сложить все цифры в каждом числе, получатся новые числа. Далее, следует сложить все цифры в каждом из вновь полученных чисел. Процесс следует продолжать до тех пор, пока в результате не останутся числа, меньшие 10. После этого все просто: числа от 0 до 9 - это номера букв в алфавите (в этом государстве алфавит состоит всего из десяти букв). Замена чисел буквами и дает ключевое слово.
Напишите программу, которая будет отыскивать ключевое слово.
Формат входного файла:
Первая строка - алфавит государства: десять букв расположенных по возрастанию порядковых номеров без пробелов.
Вторая строка - количество чисел (N
Следующие N строк - собственно исходные числа (по одному на строке, в каждом не более 255 цифр).
Формат выходного файла:
Ключевое слово
Пример:
input.txt
АГЕИКЛМОРТ
4
8267
19929
54262
000000000000
output.txt
ЛИГА
Решение g6_1039:
Первый раз до конца прочитал условие, пока печатал :). Вообще наша команда всегда отличается быстрым стартом и завалом во второй части соревнований, однако это не помешало нам занять второе место в этом году :). Задача простая. Читаем в переменную string алфавит государства. Затем перед нами встает две задачи - посчитать сумму цифр в длинном и в коротком числе. Для длинного числа все просто - складывае в одну переменную val всех символов строки (длинное число удобно загнать в строку). Если получилось числе меньше 10 - то выведем соответствующую ей букву в output. Если получилось число большее 10, то его придется разделать в цикле while. Найдем сумму цифр числа (summ := summ + A mod 10; A := A div 10) и в случае если она больше 10, то присвоим числу значение суммы. При выводе символа надо помнить, что символу в строке занумерованы 1..10, а на выход будут подаваться числа 0..9, так что логично к выходному числу прибавлять 1...
Задача g6_1040: Робот-сапер
Программа робота-сапера состоит из последовательности команд вида (a, b), где a - символ, принимающий значения W, N, O или S, что означает, соответственно, запад, север, восток или юг, а b - натуральное число, b
Требуется написать программу, которая решает эту задачу.
Ввод данных организовать из файла input.txt или с клавиатуры, а вывод - в файл output.txt или на экран.
Формат входных данных:
1-я строка: K (K
2-я строка: "a" "пробел" "b" - значения параметров 1-ой из этих команд;
3-я строка: "a" "пробел" "b" - значения параметров 2-ой из этих команд;
K+1-я строка: "a" "пробел" "b" - значения параметров K-ой из этих команд.
Формат выходных данных:
1-я строка: M - количество команд искомой последовательности;
2-я строка: "a" "пробел" "b" - значения параметров 1-ой из этих команд;
3-я строка: "a" "пробел" "b" - значения параметров 2-ой из этих команд;
M+1-я строка: "a" "пробел" "b" - значения параметров M-ой из этих команд.
Ограничение времени: 20 секунд.
Пример входных данных:
4
W 4
N 2
O 2
S 3
Пример выходных данных (соответствуют приведенным входным):
2
W 2
S 1
Решение g6_1040:
Что-то эта задачка у меня давно лежит решенная, а руки никак не дойдут разобрать. Ну что ж теперь настал и ее черед.
Во первых, надо завести массив 200*200 и закольцевать его (т.е. если вышли за левый край то переходим на правый) из элементов word или integer. Если у вас нет ограничений с памятью (например вы пишите на Free Pascal или на чем-нибудь подобном) заведите массив 400*400 и не закольцовывайте его. Такие размеры массивов объясняются тем, что в одном направлении робот может пройти не более 10 раз максимум по 20 клеток (если я правильно понял условие задачи). Заполним первоначально весь массив элементами 65536 или -1. Из точки (1; 1) начнем ползти соответственно инструкциям (N - вверх, S - вниз и т.д.) и заполнять все клетки, по которым проходит робот элементами 0.
Полностью выполнив все инструкции, мы получим лабиринт, в котором клетки, по которым можно идти - нули, а заблокированные - не нули (логично). Для поиска кратчайшего пути в лабиринте необходимо употребить алгоритм заливки (он уже употреблялся ровно 10 задач назад, в задаче Лошадью ходи!(#1030)). Здесь мы пойдем от конечной точки во все стороны тем же самым нерекурсивным флудом. Только здесь алгоритм стоит немного изменить - завести массив координат "новых клеток", т.е. тех клеток, которые добавились на этом шаге. Потом перенесем эти координаты в другой массив и будем делать еще один шаг только от них. Это то же самое что и обход графа в ширину.
Как только мы нафлудим до начальной точки, то необходимо начать распутывать всю нашу конструкцию. Находим точку, на которую можно перейти с начальной точки (которая хранит значение X - общее количество шагов), и определяем, в каком направлении надо двигаться. Двигаемся сколько можем (так чтобы координата следующей клетки в этом направлении была меньше на 1), считаем шаги. Как только придем к ситуации, что в этом направлении двигаться не можем, ищем новое доступное направление, выводим предыдущее направление и количество пройденных шагов. Вот если бы еще требовалось найти наименьшее количество команд с наименьшей длиной пути, то тогда пришлось писать перебор...
Задача g6_1041: Квадраты
Дано N квадратов на плоскости (1
Формат входных данных
В первой строке входного файла находится число N.
В последующих N строках находятся тройки чисел (x, y, a), каждая из которых описывает один квадрат следующим образом: (x,y) - координаты центра квадрата, a - длина его стороны. Все числа - целые. -30000 Формат выходных данных
В выходной файл следует вывести площадь области, покрытой данными квадратами. Округлить значение до сотых и вывести ровно два знака после десятичной точки.
Пример ввода
3
0 0 2
1 1 2
-3 1 5
Правильный вывод для примера
32.00
Решение g6_1041:
Задача с ИМ-Y2K СамГУ. Самое неинтересное решение - создать массив 60000*60000 байт, т.е. около 3,5 Гб, но, к сожалению FP не может завести такой массив, а BP/TP тем более. Если у вас есть компьютер с хотя бы полу-гигабайтом опреативной памяти можете попробывать сжать размеры массива, т.к. нам достаточно всего одного бита для квадратика. К сожалению у моего компьютера всего 256 Мб. и тормозной винчестер, так что придется думать.
Найдем координаты левого верхнего и правого нижнего углов квадратиков. Теперь сольем все координаты в разные массивы - в один X, в другой - Y. Отсортируем эти массивы по возрастанию. У нас получится 2 набора координат по 200 штук в комплекте. Поставим им в соответствие таблицу 200*200 из элементов boolean, заполненную false. Для каждого квадратика запустим процедуру, которая будет прорисовывать его хитроумную проекцию в таблицу. Она должны найти, каким номерам элементов отсортированных массивов с координатами соответствуют координаты левого верхенго и правого нижнего края. Двигаясь по X от номера левой координаты до номера правой и по Y от номера верхней до номера нижней будем присваивать этим элементам true - там находится один из квадратов или сегментов квадратов. (Пример приведен на рисунке, обратите внимание, что он не соответствует приведнным выше входным данным).
|
Такому рисунку соответствует таблица:
1 1 0 0 0
1 1 1 0 0
0 1 1 0 0
0 0 0 0 0
0 0 0 0 1
|
Теперь таблица заполнена! Осталось только посчитать площадь. Заведем цикл по всей таблице (т.е. два цикла по X и по Y). Как только нашли true, то к площади прибавляем произведение (X[I + 1] - X[I]) * (Y[J + 1] - Y[J]) ведь целочисленной координате в таблице из диапазона 1..200 соответствует целочисленное значение из -30000..30000 в отсортированном массиве координат.
Если написано слишком коряво, то напишите в гостевую книгу - переделаю.
Задача g6_1042: Треугольник (VI международная олимпиада по информатике)
Дан треугольник, составленный из чисел. Напишите программу, которая вычисляет наибольшую сумму чисел, расположенных на пути, начинающемся в верхней точке и заканчивающемся на основании треугольника.
Каждый шаг на пути может осуществляться вниз по диагонали влево или вниз по диагонали вправо.
Число строк в треугольнике от 1 до 100.
Треугольник составлен из целых чисел от 0 до 99.
Входные данные:
Первым числом во входном файле с именем INPUT.TXT является количество строка в треугольнике. Пример файла исходных данных представлен ниже.
5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
Выходные данные:
В выходной файл с именем OUTPUT.TXT записывается только наибольшая сумма в виде целого числа. Ниже приведен OUTPUT.TXT для данных выше исходных данных.
30
Пример входных данных и правильной последовательности:
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
Решение g6_1042:
Эта задача предлагалась не только на международной олимпиаде, но и на областной в Самаре, несколько лет назад.
Первое решение, которое приходит в голову - рекурсия - неправильное. Здесь есть решение проще.
Для хранения треугольника заведем массив 100*100 (из элементов word, а почему не byte вы поймете позже), часть элементов которого останутся нулевыми. Начнем анализировать треугольник, двигаясь от предпоследней строки к первой (такой тип движения избавит нас от части частных случаев). Итак, смотрим на предпоследнюю строку. У нее по диагонали снизу есть два соседа (в треугольном массиве это число которое находится на 1 клетку ниже и число, на 1 клетку ниже и правее данного) - выберем из них наибольший и прибавим к значению элемента значение наибольшего из нижних соседей. Повторяя эту операцию для каждой строки до вершины и для самой вершины, в вершине (элемент (1;1)) получим искомую сумму. Если бы мы двигались сверху вниз, то возникал бы случай для крайних элементов, у которых всего один сосед.
Вот если бы нам надо было вывести маршрут, то было бы несколько сложнее, а так задача очень проста в реализации и несложна в понимании :)
Задача g6_1043: Принцип компании (отборочный тур на Самарскую областную олимпиаду 2000 г.)
Компания
|