|
D:= Work;
end;
Теперь определяем время и скорость первого автобуса.
if Flag then begin
T:= (MaxWeg - MinWeg)/(VMax - VMin); VVV:= -MinWeg/T + VMin;
end;
writeln(Out, T:1:4); writeln(Out, MNum[1], ' ', VVV:1:4);
Последнее усилие:
D:= 0;
for I:= 2 to N - K do begin
Work:= MDist[I] * FInt - LInt + D;
if Flag then VVV:= (Work - MinWeg)/T + VMin;
writeln(Out, MNum[I], ' ', VVV:1:4);
D:=Work;
end;
И на десерт разбор последней ошибки, которая нашлась, что очень огорчило, только при прогоне имеющихся тестов. В результате в расчет максимального и минимального пути была добавлена строка
if abs(Work)
В чем суть: когда сравниваются два числа, из которых хотя бы одно расчетное, нужно производить округление. В данном случае точность выбрана произвольно, хотя я думаю неплохо бы ее обосновать.
Задача g6_1055: Кубики (XV Всеукраинская олимпиада по информатике)
Трехмерная фигура состоит из единичных кубиков. По фигуре можно построить ее фронтальную и правую проекции. Очевидно, что по этим двум проекциям не всегда можно восстановить фигуру.
Задача
Напишите программу CUBES, которая получает на вход фронтальную и правую проекции фигуры и определяет минимальное и максимальное количество кубиков, которое можно было бы использовать для построения фигуры с заданными проекциями.
Входные данные
В первой строке входного файла CUBES.DAT находятся три числа N, M и К, которые задают размеры проекций (1 Пример входных данных
2 2 3
1 0
1 1
0 0 1
1 1 1
Выходные данные
В единственной строке выходного файла CUBES.SOL должно находиться два числа: минимальное и максимальное число кубиков, которые можно было бы использовать для построения фигуры с заданными проекциями.
Пример выходных данных
4 7
Решение g6_1055:
Сейчас я начал активные тренировки на украинских задачках. К ним прилагаются тесты, так что вы сможете проверить, насколько верно вы решили ее.
Разобьем изображения фигуры на вертикальные слои. Для нижнего слоя получим:
11 - вид спереди, 111 - вид справа.
Для минимального количества кубиков вид сверху будет выглядеть так:
100
010
001
а для максимального так:
111
111
111
Для того чтобы найти минимальное количество кубиков в слое достаточно среди количества кубиков во фронтальной и боковой проекции выбрать наибольшее. Действительно, если во фронтальной проекции лежит 4 кубика, а в боковой - 3, то мы можем выстроить 4 кубика так, что фронтальная проекция будет состоять из 4 кубиков, а боковая из 3. Если фигура имеет разрывы, то это никак не влияет на такое предположение. Пример для фронтальной проекции - 4(11101), боковой - 3(10101).
10000
00000
01100
00000
00001
Как видно, здесь фигура проецируется в 11101 и 10101. Теперь посчитаем максимум для данных проекций.
Если во фронтальной проекции на некоторой позиции стоит 1, то 1 могут быть заняты все клетки, кроме тех, которые соответствуют 0 в боковой проекции. Т.е. для одной единицы во фронтальной проекции получаем наибольшее количество блоков RB (кол-во единиц в боковой проекции), а так как у нас FB (кол-во единиц во фронтальной проекции) рядов, то максимальное кол-во блоков для слоя RB * FB. Чтобы посчитать максимальное количество блоков для всей фигуры достаточно просто сложить произведения RB на FB для всех слоев.
Технически это реализуется с помощью двух одномерных массивов, с номерами от 1 до n. В первом из них будет храниться количество элементов фронтальной и боковой проекции.
Задача g6_1056: Многоугольники (XV Всеукраинская олимпиада по информатике)
На плоскости задано такое множество из N многоугольников, что выполняются следующие условия:
1) никакие два многоугольника не имеют общих точек;
2) для каждого i-го многоугольника существует Pi многоугольников, внутри которых он находится, и N-1-Pi многоугольников, которые находятся внутри его, 0
Задача
Напишите программу POLYGON, которая для каждого многоугольника выдает количество многоугольников, внутри которых он находится.
Входные данные
Первая строка входного файла POLYGON.DAT содержит целое число N - количество многоугольников, 3
Пример входных данных
3
3 -2 1 8 9 12 1
3 7 5 6 3 7 4
4 4 3 7 7 9 3 1 2
Выходные данные
Единственная строка выходного файла POLYGON.SOL должна содержать N чисел: i-ое число строки должно быть Pi- количество многоугольников, внутри которых находится i-ый многоугольник.
Пример выходных данных
0 2 1
Решение g6_1056:
Когда я первый раз увидел эту задачу, то подумал что она геометрическая и огорчился (не люблю геометрические задачи, хуже них только задачи с графами). Но нет, нет геометрии в этой задаче.
Многоугольники не имеют общих точек. Очень важное условие.
Заведем массив, в который для каждого многоугольника запишем его крайнюю правую координату (можно записать любую другую "самую", но мы разберем случай с правой координатой). Это самая правая точка многоугольника. Естественно, что у самого большого многоугольника самая правая точка будет лежать правее самых правых точек всех остальных многоугольников. Если бы это было не так, то многоугольники имели бы точки пересечения, что противоречит условию.
Техническая реализация: Следует завести два массива, в один из которых записать координаты самых правых точек многоугольника (только координату по X, ту что отвечает за "правость"), а в другой - номера многоугольников. Затем отсортируем по убыванию массив правых координат с помощью быстрой сортировки (она есть в примерах А.Н. Никитина) вместе с элементами массива координат перемещая элементы массива номеров многоугольников. После того как массив отсортирован, заполним его элементы с правой координатой значениями, соответствующими номеру этого элемента - 1 (т.е. 0, 1, 2...). Теперь в этом массиве хранится число многоугольников, которые окружают данный многоугольник. Теперь с помощью другой процедуры быстрой сортировки отсортируем массив номеров по возрастанию, перемещая соответствующие элементы "правого" массива. Это делается для ускорения вывода, чтобы не искать каждый раз элемент в массиве заново.
Теперь просто идя по "правому" массиву от 1 до количества многоугольников выводим значения - это и есть количество окружающих многоугольников.
Задача g6_1057: Электронная почта (XIII Всеукраинская олимпиада по информатике)
Пользователь сети Интернет подписан на несколько разных списков рассылки, которые высылают ему по электронной почте сообщения на определенные темы. Для удобства пользователь создал себе набор папок, каждая из которых соответствует одной из тем. Перед тем, как читать сообщения он копирует их в соответствующую папку.
Почтовая программа, установленная на компьютере пользователя, позволяет за одну "операцию" переносить из "списка новых сообщений" в соответствующую папку:
- Одно сообщение из любого места списка
- Несколько сообщений, идущих в списке подряд, и относящихся к одной теме
Переносить можно не обязательно начиная с начала "списка новых сообщений". Пользователю необходимо перенести все новые сообщения в соответствующие им папки за наименьшее количество операций.
Пример. Пусть пользователь подписан на рассылки анекдотов, веселых историй, спортивных новостей и прогноза погоды. Пусть "список новых сообщений" при некотором вхождении в почтовую программу имел следующий вид: (Анекдоты, Спортивные новости, Прогноз погоды, Спортивные новости, Веселые истории, Веселые истории, Спортивные новости)
Список папок Список новых сообщений
1 Анекдоты 1 Анекдоты
2 Веселые истории 3 Спортивные новости
3 Спортивные новости 4 Прогноз погоды
4 Прогноз погоды 3 Спортивные новости
2 Веселые истории
2 Веселые истории
3 Спортивные новости
Переносить сообщения в папки он может следующим образом: сначала два сообщения на тему "Веселые истории". Тогда он получит следующий список: (Анекдоты, Спортивные новости, Прогноз погоды, Спортивные новости, Спортивные новости). Потом перенести сообщения о прогнозе погоды, после этого "Анекдоты", а потом, одновременно, все три сообщения о спортивных новостях. На это он потратит 4 "операции".
Задание: Напишите программу EMAIL которая будет вычислять минимальное количество "операций", с помощью которых можно перенести все новые сообщения в папки. Для удобства каждой теме присваивается номер.
Входные данные: Единственная строчка входного файла EMAIL.DAT содержит число N (0 Пример входных данных
7 1 3 4 3 2 2 3
Выходные данные В первой строке выходного файла EMAIL.SOL должно находиться минимальное число операций для данных, приведенных во входном файле.
Пример выходных данных
4
Решение g6_1057:
Несмотря на жестокий насморк я продолжаю активно тренироваться :)
Итак, мы можем переносить несколько стоящих подряд сообщений за одно действие. Это единственное, что может уменьшить общее количество операций. Этим обстоятельством можно воспользоваться сразу при вводе данных. Например, если мы встречаем сообщение на ту же тему что и предыдущее, то не записываем его в массив. Технически это реализуется с помощью цикла while, который рабоет до тех пор, пока счетчик не достигнет значения, равного количеству сообщений. Если нам встретилось сообщение, такое же, как предыдущее, то уменьшим счетчик и количество сообщений на 1 (в итоге счетчик останется неизмененным).
Теперь нам следует создать массив указателей на следующий элемент с таким же номером. Каждый элемент должен ссылаться на такой же элемент, стоящий справа от него, или содержать 0, если такого элемента справа не существует.
Теперь начинается настоящая хитрость: эта задача решается методом динамического программирования очень красиво, так красиво, что я еще никогда не видел такого красивого решения этим часто используемым способом. Заведем массив размером 200*200. Координатой по горизонтали пусть будет номер левого элемента, а по вертикали - правого. В ячейке массива будет храниться значение, сколько операций необходимо осуществить, чтобы перетащить все сообщения от левого до правого.
Как же заполнять этот массив? Логично, что для переноски одного сообщения необходима ровно одна операция, т.е. главная диагональ будет заполнена 1. Также мы знаем, что в силу особенностей ввода информации у нас не может стоять подряд два сообщения с одной тематикой, т.е. на перетаскивание двух подряд идущих сообщений нам потребуется две операции.
А вот теперь самое интересное.
Если сообщений больше чем два, то следует рассматривать все гораздо хитрее. Допустим, что оказалось так, что правое и левое сообщение имеют одну и ту же тему, тогда:
Значение массива A[l, r] (здесь A - динамически подсчитываемый массив, l и r - левая и правая границы) равно A[l + 1, r - 1] + 1, т.е. мы можем растащить все сообщения между ними и они станут рядом и вытащатся за одну операцию! Но может оказаться, что мы можем растащить A[l, r] еще быстрее. Обратим внимание на наш массив указателей на следующий аналогичный элемент NEXT. А что если между этими одинаковыми элементами есть еще такие же (т.е. NEXT[l] R)? Тогда найдем все элементы x = NEXT[x] (первоначально x = l), пока x нее станет равно r. Тогда есть два варианта: если A[l, r]
Теперь рассмотри вариант, если сообщения с номерами l и r имеют разные темы. Растаскивание такого сообщения можно представить как A[l, r] = min(A[l + 1, r], A[l, r - 1]) + 1, т.е. мы перетаскиваем соседнюю группу сообщений и, затем, отдельно сообщение, которое в эту группу не входит. Но в промежутке от l до r могут встретиться сообщения, с такой же темой как у l. Это мы можем использовать. x = NEXT[x], первоначально x = l. Условие выхода из цикла - если NEXT[x] = 0, т.е. больше таких элементов не встречается, или NEXT[x] > r, т.е. эти элементы больше не встречаются на интервале [l, r]. A[l, r] = min(A[l, r], A[l + 1, x - 1] + A[x, r]) для каждого x. Т.е. мы пытаемся из группы, например 3, 4, 2, 3, 6, 7 вытащить сначала элементы 3, 4, 2, 3, а затем, отдельно, 6 и 7.
Технически это реализуется так: сначала заполняется главная диагональ массива A[l, l] единицами, затем A[l, l + 1] = 2 (два подряд разных сообщения), а затем запускается процедура динамического подсчета с параметрами (1, 3), (2, 4), (3, 5), ..., (1, 4), т.е. сначала проходяться все интервалы длиной 3, затем 4 и т.п. Окончательным ответом будет значение в ячейке A[1, n], т.е. левая граница 1, а правая - количество сообщений.
Задача g6_1058: Автобус (XIII Всеукраинская олимпиада по информатике)
Служебный автобус совершает один рейс по установленному маршруту и в случае наличия свободных мест подбирает рабочих, которые ожидают на остановках, и отвозит их на завод. Автобус также может ждать на остановке рабочих, которые еще не пришли. Известно время прихода каждого рабочего на свою остановку и время проезда автобуса от каждой остановки до следующей. Автобус приходит на первую остановку в нулевой момент времени. Продолжительность посадки рабочих в автобус считается нулевой.
Задание: Написать программу BUS, которая определит минимальное время, за которое автобус привезет максимально возможное количество рабочих.
Входные данные: Входной текстовый файл BUS.DAT в первой строке содержит количество остановок N и количество мест в автобусе M. Каждая i-я строчка из последующих N строчек содержит целое число - время движения от остановки _ к остановке i+1 (N+1-я остановка - завод), количество рабочих K, которые придут на i-ю остановку, и время прихода каждого рабочего на эту остановку в порядке прихода (1
Пример входных данных.
3 5
1 2 0 1
1 1 2
1 4 0 2 3 4
Выходные данные: Единственная строка выходного текстового файла BUS.SOL должен содержать минимальное время, необходимое для перевозки максимального количества рабочих.
Пример выходных данных.
4
Решение g6_1058:
Мой насморк вроде бы прекратился (на спрее было написано, что надо брызгать 2 раза в каждую ноздрю 2 раза в день, а я брызгал по 6-8 раз 4-5 раз в день).
Теперь, собственно, решение. Сначала определим, что такое максимально возможное количество рабочих. Если общее количество рабочих больше вместимости автобуса, то это - объем автобуса, если же рабочих меньше чем вместимость автобуса - то это количество всех рабочих (в этом случае вместимости автобуса уместно присвоить значение, равное количеству людей).
Задачу надо решать с помощью двоичного поиска (бинарного поиска, дихотомии). А лучше с помощью двух двоичных поисков.
Когда мы считываем данные, следует определить время прихода последнего человека (т.е. то время, когда уже все люди будут на остановках) - это будет максимум в двоичном поиске. Минимум будет равен нулю. Если автобус должен задержаться перед остановкой, то он должен сделать это перед первой остановкой (действительно, если он подъедет к первой остановке, заберет людей, а потом будет ждать у второй остановки, то в это время на первую могут придти еще люди, а если ждать перед первой, то люди со второй никуда не денутся). Минимум и максимум у нас есть. Теперь берем задержку, равную x = (min + max) / 2. С помощью процедуры, которая будет описана ниже, вычисляем, сколько людей успеет придти до момента x на первую остановку, для второй остановки будет задержка, равная x + a[1], где a[1] - время следования от первой остановки до второй, для третьей задержка - x + a[1] + a[2] и т.д. Если количество севших в автобус на всех остановках больше либо равно вместимости автобуса, то надо заменить x на (min + x) / 2, если остались места в автобусе то x = (x + max) / 2. Условие выхода будет такое: если при некоторой задержке x автобус заполнен, а при задержке (x - 1) автобус не полон, то ответ x.
Теперь вторая дихотомия. Та самая, которая определяет, сколько людей успеет придти на определенную остановку до определенного момента. Здесь максимумом дихотомии будет количество людей на остановке, а минимумом - ноль. Выбираем среднего человека - если его время прихода меньше, чем задержка, то x = (x + max) / 2, если он не успеет придти, то x = (min + x) / 2. Здесь условие выхода такое: если человек успевает придти на остановку, а следующий за ним нет - то ответом будет номер человека. Отдельно нужно обрабатывать случай, если на автобус сядут все люди с остановки.
Задача g6_1059: Электронные часы (II Всероссийская командная олимпиада по информатике)
Циферблат новых электронных часов, установленных на главном здании офиса фирмы Macrohard, состоит из 4 прямоугольных панелей, каждая из которых состоит из 6 рядов по 5 лампочек в каждом. Первые две панели отображают цифры, из которых складываются часы, а следующие две - минуты. (Если сейчас меньше 10 часов, первая панель отображает 0).
К сожалению, лампочки, установленные на панелях, были произведены компанией Sveta.Net, которая известна своим принципом "раньше перегорит - больше спрос", вследствие чего на следующий день люди, проходя мимо офиса компании, видели лишь некоторое подобие цифр, поскольку некоторые лампочки больше не горели.
Петя живет в доме, стоящем прямо напротив офиса компании Macrohard. В первый день после установки часов он зарисовал у себя в блокноте, как выглядят все цифры на панелях (панели однотипные, поэтому одна и та же цифра на различных панелях выглядит одинаково). Теперь Петя хочет узнать, можно ли по текущему изображению на часах однозначно определить, сколько сейчас времени. Помогите ему!
Формат входных данных
При тестировании этой задачи в каталоге, который будет текущим, когда будет запущена Ваша программа, будет находиться два файла. Файл digits.txt содержит 6 строк по 50 символов в каждой. Он будет одинаковым для всех тестов и будет совпадать с приведенным в примере. Вы также можете найти этот файл в каталоге o:\common. Содержимое файла digits.txt задает правильное написание цифр на панелях (первый прямоугольник символов задает число 0, следующий - 1, и т. д. до 9). Не горящая лампочка обозначается символом "." (точка), а горящая - "#" (диез).
Входной файл input.txt содержит 6 строк по 20 символов в каждой - текущее изображение на часах. Первый прямоугольник задает первую панель, следующий - вторую, следующий - третью и последний - четвертую.
Формат выходных данных
Если можно точно определить время, которое сейчас отображается на часах, выведите это время в формате hh:mm. Если время нельзя определить однозначно, выведите AMBIGUITY. Если же в часах точно сломалось еще что-то, например центральный процессор, который управляет лампочками, выведите ERROR.
Примеры
digits.txt
..##.....#..##..####.#..#.####..###.####..##...##.
.#..#...##.#..#....#.#..#.#....#.......#.#..#.#..#
.#..#..#.#....#...#..#..#.###..###....#...##..#..#
.#..#....#...#.....#.####....#.#..#..#...#..#..###
.#..#....#..#......#....#.#..#.#..#..#...#..#....#
..##.....#.####.###.....#..##...##...#....##..###.
input.txt output.txt
..##..####.#..#.#### 23:45
....#....#..........
....#...#..#..#.###.
...#.....#.##......#
..#......#....#.#..#
.####..##.....#..#..
#.##.....#..##..#### ERROR
.#..#...##.#..#....#
.#.....#......#...#.
.#..#..............#
.#..#.......#......#
..##.....#.####.....
..##........##..#### AMBIGUITY
.#..#....#.#..#....#
.#............#...#.
.#..#..............#
.#..#.......#......#
..##.......####.....
Решение g6_1059: Предоставлено Андреем Станкевичем
Введем понятие "символ" как массив размера 6x5, в котором 1 соответствует горящей лампочке, а 0 - не горящей. Для двух символов A и B введем понятие их пересечения как массив C=A*B, где c[i][j] =a[i][j]*b[i][j]. Тогда верно следующее утверждение: чтобы символ A мог быть цифрой i, должно выполняться A*Di=A, где Di - символ, соответствующий каноническому написанию цифры i.
Помня также, что время лежит в диапазоне 00:00-23:59, получаем следующий алгоритм решения задачи: для каждого возможного времени проверить, может ли оно быть отображено сейчас на табло (для этого каждую цифру на табло надо сравнить с соответствующей канонической цифрой). После этого: если ровно одно время может быть отображено на табло, то это и есть ответ, если более чем одно, то ответ AMBIGUITY, в если ни одно время не подошло, то ответ ERROR.
Программа
Приведем процедуру проверки, что символ a может быть цифрой, содержащейся в символе b (в реализации для простоты не будем заменять . на 0, а # на 1, а оставим как есть):
type
tdigit = array [1..6, 1..5] of char;
function check(a, b: tdigit): boolean;
var
i, j: longint;
begin
check := false;
for i := 1 to 6 do
for j := 1 to 5 do
if (a[i][j] = '.') and (b[i][j] = '#') then
exit;
check := true;
end;
Теперь проверяем, какое время может быть на табло: часы и минуты, и выводим ответ:
for i := 0 to 23 do
begin
if can[1][i div 10] and can[2][i mod 10] then
begin
inc(ch);
hh := i;
end;
end;
cm := 0;
for i := 0 to 59 do
begin
if can[3][i div 10] and can[4][i mod 10] then
begin
inc(cm);
mm := i;
end;
end;
if (ch = 0) or (cm = 0) then
begin
writeln('ERROR');
end
else if (ch = 1) and (cm = 1) then
begin
writeln(hh div 10, hh mod 10, ':',
mm div 10, mm mod 10);
end else begin
writeln('AMBIGUITY');
end;
Задача g6_1060: Дождик (XIV Всероссийская олимпиада по информатике)
В НИИ метеорологии решили изучить процесс образования водоемов на различных рельефах местности во время дождя. Ввиду сложности реальной задачи была создана двумерная модель, в которой местность имеет только два измерения - высоту и длину. В этой модели рельеф местности можно представить как N-звенную ломаную c вершинами (x0, y0), ..., (xN, yN), где x0 yj, для любых i j. Слева в точке x0 и справа в точке xN рельеф ограничен вертикальными горами огромной высоты.
Если бы рельеф был горизонтальным, то после дождя вся местность покрылась бы слоем воды глубины H. Но поскольку рельеф - это ломаная, то вода стекает и скапливается в углублениях, образуя водоемы.
Требуется найти максимальную глубину в образовавшихся после дождя водоемах.
Входные данные
|