Задача D. Соревнования картингистов
Методические рекомендации по разбору предложенных олимпиадных задач
Муниципального этапа Всероссийской олимпиады школьников по информатике в 2017-2018 учебном году
Класс
Задача А. Автобусы.
| Имя входного файла: | input.txt |
| Имя выходного файла: | output.txt |
| Ограничение по времени: | 2 секунды |
| Ограничение по памяти: | 64 мегабайта |
Для заезда в детский оздоровительный лагерь организаторы решили заказать автобусы. Известно, что в лагерь собираются поехать N детей и M взрослых. Каждый автобус вмещает K человек. В каждом автобусе, в котором поедут дети, должно быть не менее двух взрослых.
Определите, удастся ли отправить в лагерь всех детей и взрослых, и если да, то какое минимальное количество автобусов требуется для этого заказать.
Формат входного файла
На вход программы поступают 3 натуральных числа, записанных через пробел - N, M и K, каждое из них не превосходит 10 000.
Формат выходного файла
Выведите количество автобусов, которые нужно заказать. Если же отправить всех в лагерь невозможно, выведите 0 (ноль).
Пример входного и выходного файлов
| Входные данные | Выходные данные |
| 10 4 7 | 2 |
| 10 4 5 | 0 |
Решение.
Алгоритм:
Во первых: нужно учесть, что К может принимать значение меньше или равное 2. В этом случае следует выводить 0, потому, что в каждый автобус мы будем вынуждены посадить взрослых (а дети так и не уедут). Теперь рассмотрим случай когда К больше двух: в том случае нужно будет ровно n/(k-2) автобусов для перевозки детей. Заметим, что если n не делится нацело на k-2, то автобусов понадобиться на один больше. Так же мы не сможем уехать если количество взрослых делённое на два меньше количества нужных автобусов для перевозки детей. Во всех остальных случаях ответом будет (m+n)/k, но если (m+n) не делится нацело на k то на один автобус больше.
|
|
|
Программа:
var a,b,c,k,n,p: integer;
begin
read(a,b,c);
if (b<2) or (c<3) then writeln(0) else
begin
k:=a div (c-2); //2
if a mod (c-2) <> 0 then inc(k);
if b div k < 2 then writeln(0) else
begin
k:=(a+b) div c;
if (a+b) mod c <> 0 then inc(k);
writeln(k);
end;
end;
end
Задача В. Лавочки
| Имя входного файла: | input.txt |
| Имя выходного файла: | output.txt |
| Ограничение по времени: | 1 секунда |
| Ограничение по памяти: | 64 мегабайта |
Лавочки в парке устроены следующим образом. Несколько одинаковых кубических гранитных блоков ставятся в ряд, а на них кладется гранитная плита (см. рисунок). Архитектор-модернист решил, что будет интереснее, если у всех лавочек расположение гранитных блоков-ножек будет разным (и не обязательно симметричным). При этом они располагаются так, чтобы плита не падала: для этого достаточно, чтобы и слева, и справа от центра плиты был хотя бы один гранитный блок или его часть (в частности, если центр плиты приходится на середину какого-нибудь блока, то и слева, и справа от центра плиты находится часть блока, и плита не падает).
|
|
|
Грабители обнаружили, что можно по одному вытаскивать гранитные блоки, находящиеся с краю (как слева, так и справа). Они хотят вытащить из-под лавочки как можно больше блоков так, чтобы она при этом не упала (передвигать оставшиеся блоки нельзя). Определите, какие блоки они должны оставить.
Формат входного файла
В первой строке входных данных содержатся два числа: L - длина лавочки и K - количество гранитных блоков-ножек. Оба числа натуральные и не превышают 10 000.
Во второй строке следуют K различных целых неотрицательных чисел, задающих положение каждой ножки. Положение ножки определяется расстоянием от левого края плиты до левого края ножки (ножка - это куб размером 1×1×1). Ножки перечислены слева направо (то есть начиная с ножки с меньшим расстоянием до левого края).
Формат выходного файла
Требуется перечислить ножки, которые грабителям нужно оставить. Для каждой ножки нужно выдать ее положение, как оно задано во входных данных. Ножки следует перечислять слева направо, в том порядке, в котором они встречаются во входных данных.
|
|
|
Примеры входных и выходных файлов
| Входные данные | Выходные данные |
| 5 2 0 2 | 2 |
| 13 4 1 4 8 11 | 4 8 |
| 14 6 1 6 8 11 12 13 | 6 8 |
Второй пример соответствует лавочке на рисунке.
Решение.
Алгоритм:
Обозначим координату (положение) i-й ножки как d i. Найдём числа left и right — номера самой правой ножки, хотя бы часть которой находится левее середины лавочки, и самой левой ножки, хотя бы часть которой находится правее середины лавочки, соответственно: left=maxi 
2d i 
L , right=mini 2 
(d i+1) 
L . Если в итогеleft=right (то есть L нечётно и 
i d i= 
2L 
), то вывести нужно одно число d left, в противном случае — сначала d left, затем d right.
Программа:
var L,k,n,i: longint;//0..10 000
a: array [0 .. 9999] of boolean;
begin
read(L,k);
for i:=1 to k do begin
read(n);
a[n]:=true;
end;
if (L mod 2 <>0) and (a[L div 2]) then begin
write(L div 2);
halt;
end ;
for i:=(L-1) div 2 downto 0 do
if a[i] then begin
write(i,' ');
break;
|
|
|
end;
for i:=l div 2 to L-1 do
if a[i] then begin
write(i);
break;
end;
end.
Задача С. Выборы
| Имя входного файла: | input.txt |
| Имя выходного файла: | output.txt |
| Ограничение по времени: | 3 секунды |
| Ограничение по памяти: | 64 мегабайта |
На выборах в Государственную думу в избирательные бюллетени внесено N партий. Электронный сканер для считывания информации с бюллетеней передает информацию о каждом бюллетене в следующем формате: если в соответствующей клетке бюллетеня стоит пометка, то сканер передает + (плюс), в противном случае он передает - (минус). Таким образом, он передает последовательность из N символов - плюсов и минусов.
Бюллетень считается действительным, если пометка есть ровно в одной клетке. Недействительные бюллетени в подсчете результатов выборов не участвуют.
Партия проходит в Государственную Думу, только если она набирает не менее 7% от общего числа действительных бюллетеней.
Требуется вывести номера (в порядке их перечисления в бюллетене) всех партий, которые проходят в Государственную Думу.
Формат входного файла
В первой строке входных данных содержатся два числа, разделенные пробелом: N - количество партий и M - количество бюллетеней. Оба числа натуральные, N <= 200, M <= 100 000.
В следующих M строках записана информация, полученная из бюллетеней. Каждая строка - последовательность из N символов + или - (без пробелов).
Гарантируется, что есть хотя бы один действительный бюллетень.
Формат выходного файла
Выведите через пробел номера партий, прошедших в Думу, в порядке возрастания. Если ни одна из партий не проходит в Думу, выводить ничего не нужно.
Примеры входных и выходных файлов
| Входные данные | Выходные данные |
| 3 4 +-- +-- -+- +-+ | 1 2 |
| 1 5 + - - - - | 1 |
Решение.
Алгоритм:
Напишем специальную функцию who, по данной строчке-бюллетеню возвращающую номер выбранного в данном бюллетене кандидата или 0 для недействительного бюллетеня (для этого достаточно один раз пройти циклом по строчке-бюллетеню, помня текущий ответ). Теперь для каждого бюллетеня вызовем функцию who от него и, если результат не равен нулю, увеличим на 1 числа K (количество действительных бюллетеней) и gwho(количество действительных голосов, отданных за партию с номером, равным результату функции who). Осталось вывести все i такие, что 100gi 
7K.
Программа:
{$h+}
var
flag:boolean;
a:array [1..10000] of longint;
s:string;
n,m,max,k,i,j:longint;
begin
readln(n,m);
max:=m;
for i:=1 to m do
begin
readln(s);
k:=0;
flag:=false;
for j:=1 to length(s) do
if s[j]='+' then
inc(k);
if k<>1 then
begin
dec(max);
flag:=true;
end;
if not flag then
for j:=1 to length(s) do
if s[j]='+' then
inc(a[j]);
end;
for i:=1 to n do
begin
if a[i]>=max*0.07 then
write(i,' ');
end;
end.
Задача D. Билет на электричку
| Имя входного файла: | input.txt |
| Имя выходного файла: | output.txt |
| Ограничение по времени: | 3 секунды |
| Ограничение по памяти: | 64 мегабайта |
В новых элитных электричках каждому пассажиру положено сидячее место. Естественно, количество сидячих мест ограничено и на всех их может не хватить. Маршрут электрички проходит через N станций, занумерованных от 0 до N-1. Когда человек хочет купить билет, он называет два числа x и y – номера станций, откуда и куда он хочет ехать. При наличии хотя бы одного сидячего места на этом участке на момент покупки ему продается билет, иначе выдается сообщение «билетов нет» и билет не продается. Ваша задача – написать программу, обслуживающую такого рода запросы в порядке их прихода.
Формат входного файла
В первой строке содержаться три числа N – количество станций (1 ≤ N ≤ 10 000), K – количество мест в электричке (1 ≤ K ≤ 1000) и M – количество запросов (1 ≤ M ≤ 50 000). В следующих M строках описаны запросы, каждый из которых состоит из двух чисел x и y (0 ≤ x < y < N).
Формат выходного файла
На каждый запрос ваша программа должна выдавать результат в виде числа 0 если билет не продается и 1 если билет был продан. Каждый результат должен быть на отдельной строке
Примеры входных и выходных файлов
| Входные данные | Выходные данные |
| 5 2 4 0 4 1 2 1 4 2 4 | 1 1 0 1 |
Решение.
Алгоритм:
Представим массив длины N в i-той ячейке которого будем хранить количество пассажиров уже купивших билет и едущих от станции i к (i+1).
Будем поддерживать для такого массива RMQ (дерево максимумов) с возможностью быстрой модификации (прибавления) на отрезке.
Теперь при обработке каждого запроса мы сначала узнаём максимум на отрезке [x; y-1], и, если он меньше К (т.е. между каждой парой станций на маршруте существует хотя бы одно свободное место), продаём билет и выполняем update(x, y-1, +1). Иначе отказываем в продаже билета.
Программа :
var
mas : array [0..10001] of longint;
n, m ,k, i, a, b, j, z :longint;
begin
readln(n, k, m);
for i := 0 to n-1 do
mas[i]:=k;
for i:=1 to m do
begin
readln(a, b);
for j := a to b-1 do
if mas[j]=0 then z:=5;
if z=5 then writeln('0')
else
begin
for j:= a to b-1 do dec(mas[j],1);
writeln('1');
end;
z:=0;
end;
end.
Задача E. Камни
| Имя входного файла: | input.txt |
| Имя выходного файла: | output.txt |
| Ограничение по времени: | 2 секунды |
| Ограничение по памяти: | 64 мегабайта |
На столе лежат N камней. За ход игрок может взять
- 1 или 2 камня, если N делится на 3;
- 1 или 3, если N при делении на 3 дает остаток один;
- 1, 2 или 3, если N при делении на 3 дает остаток два.
Каждый ход можно сделать при наличии достаточного количества камней. Проигрывает тот, кто хода сделать не может.
Формат входного файла
Вводится целое число 0 < N <= 100.
Формат выходного файла
Выведите 1 или 2 – номер игрока, который выиграет при правильной игре.
Примеры входных и выходных файлов
| Входные данные | Выходные данные |
| 3 | 2 |
| 5 | 1 |
Решение.
Алгоритм:
Пусть (F[i] = 1) если выигрывает первый и (F[i] = 2) если второй. Тогда заметим, что F[1]=1,F[2]=1 F[3] = 2. Теперь мы просто заполним наш массив F. Будем считать, что 1 это выигрышная позиция 2 проигрышная. Тогда если мы можем из теперешней позиции попасть в проигрышную, то она выигрышная, а если мы попадаем только в выигрышные, то наша позиция проигрышная. Осталось пробежаться циклом от 4 до n. И выписать условия для разной кратности 3. На самом деле, потом можно заметить, что позиции кратные 3ём проигрышные, а все остальные выигрышные.
Программа:
Program kamni;
var
n : integer;
Begin
readln(n);
if(n mod 3 = 0) then
writeln('2');
if(n mod 3 <> 0) then
writeln('1');
end.
Класс
Задача А. Ставки
| Имя входного файла: | input.txt |
| Имя выходного файла: | output.txt |
| Ограничение по времени: | 2 секунды |
| Ограничение по памяти: | 64 мегабайта |
Перед началом тараканьих бегов всем болельщикам было предложено сделать по две ставки на результаты бегов. Каждая ставка имеет вид "Таракан №Aпридет раньше, чем таракан №B".
Организаторы бегов решили выяснить, могут ли тараканы прийти в таком порядке, чтобы у каждого болельщика сыграла ровно одна ставка из двух (то есть чтобы ровно одно из двух утверждений каждого болельщика оказалось верным). Считается, что никакие два таракана не могут прийти к финишу одновременно.
Формат входного файла
В первой строке входных данных содержатся два разделенных пробелом натуральных числа: число K, не превосходящее 10, - количество тараканов и числоN, не превосходящее 100, - количество болельщиков. Все тараканы пронумерованы числами от 1 до K. Каждая из следующих N строк содержит 4 натуральных числа A, B, C, D, не превосходящих K, разделенных пробелами. Они соответствуют ставкам болельщика "Таракан №A придет раньше, чем таракан №B" и "Таракан №C придет раньше, чем таракан №D".
Формат выходного файла
Если завершить бега так, чтобы у каждого из болельщиков сыграла ровно одна из двух ставок, можно, то следует вывести номера тараканов в том порядке, в котором они окажутся в итоговой таблице результатов (сначала номер таракана, пришедшего первым, затем номер таракана, пришедшего вторым и т. д.) в одну строку через пробел. Если таких вариантов несколько, выведите любой из них.
Если требуемого результата добиться нельзя, выведите одно число 0.
Примеры входных и выходных файлов
| Входные данные | Выходные данные |
| 3 2 2 1 2 3 1 2 3 2 | 3 2 1 |
| 3 4 1 2 1 3 1 2 3 1 1 2 2 3 1 2 3 2 | 0 |
Решение.
Алгоритм:
Переберём все перестановки чисел от 1 до K — все возможные исходы бегов (порядок прихода тараканов). Для каждой перестановки за O(N) проверим, правда ли, что у каждого болельщика в таком случае сыграет ровно одна ставка. Если это действительно так, выводим текущую перестановку и завершаем работу программы. В конце программы выводим 0 (программа не завершилась раньше, следовательно, ответ не найден).
Программа :
type
Tstavka = record
a1, a2, b1, b2: longint;
end;
var
i, n, k, e, s, p, w: int64;
a: array [1..10] of int64;
st: array [1..100] of Tstavka;
go: boolean;
procedure change(x: longint);
var
i1, t: longint;
begin
for i1 := x + 1 to x + ((k - x) div 2) do
begin
t := a[i1];
a[i1] := a[k + 1 - i1 + x];
a[k + 1 - i1 + x] := t;
end;
end;
procedure next;
var
need, ch, t, i1: longint;
begin
need := 0;
for i1 := k - 1 downto 1 do
if a[i1] < a[i1 + 1] then
begin
need := i1;
break;
end;
if need = 0 then
exit;
for i1 := k downto 1 do
if a[i1] > a[need] then
begin
ch := i1;
break;
end;
t := a[need];
a[need] := a[ch];
a[ch] := t;
if e <> 1 then
change(need);
end;
begin
// assign(input,'input.txt'); reset(input);
read(k, n);
for i := 1 to n do
begin
read(st[i].a1, st[i].a2, st[i].b1);
readln(st[i].b2);
end;
if (k=1) and (st[i].a1=1) and (st[i].a2=1) and (st[i].b1=1) and (st[i].b2=1) then
begin
writeln(0);
exit;
end;
for i := 1 to k do a[i] := i; s := 1;
for i := 1 to k do s := s * i;
for e := 1 to s do
begin
go := true;
for w := 1 to n do
if ((a[st[w].a1] < a[st[w].a2]) and (a[st[w].b1] < a[st[w].b2])) or ((a[st[w].a1] > a[st[w].a2]) and (a[st[w].b1] > a[st[w].b2])) then
begin
go := false;
break;
end;
if go = true then
begin
p := 1;
while p < k do
begin
for i := 1 to k do
if a[i] = p then
begin
write(i, ' ');
inc(p);
break;
end;
end;
for i := 1 to k do
if a[i] = k then
begin
writeln(i);
exit;
end;
end;
next;
end;
writeln(0);
//close(input);
end.
Задача В. Гонки на машинах
| Имя входного файла: | input.txt |
| Имя выходного файла: | output.txt |
| Ограничение по времени: | 2 секунды |
| Ограничение по памяти: | 256 мегабайт |
Как и у каждого мальчика, у Феди есть игрушечные машинки. Однако ему повезло больше, чем обычному мальчику — все n его машинок являются радиоуправляемыми. Целыми днями он может устраивать различные автогонки и играть с друзьями.
Из всех видов гонок Федя предпочитает гонки по прямой. В данном формате соревнования трасса имеет форму прямой и является бесконечной (соревнования идут до тех пор, пока Феде это не надоест). Изначально каждая из n машинок находится на некотором расстоянии от старта — имеет фору xi метров. По команде все машинки начинают свое движение от старта, при этом каждая машинка движется во время гонки с постоянной скоростью vi метров в секунду. Все машинки движутся в одном направлении — удаляются от старта.
Недавно Феде подарили видеокамеру, и он хочет заснять яркие моменты гонки. Прежде всего Федя хочет запечатлеть первый обгон гонки, то есть первый момент времени, в который две машины находятся на одном расстоянии от старта.
Так как этого события можно ждать очень долго, Федя хочет настроить камеру на автоматическое включение во время обгона. Однако, Федя самостоятельно не может найти время, которое пройдет со времени начала гонки до времени первого обгона. Помогите Феде — напишите программу, находящую искомую величину.
Формат входных данных
В первой строке входного файла содержится единственное число n — количество машинок на трассе (2 
n 100). Каждая из следующих n строк содержит по два целых числа xi и vi — расстояние от старта (в метрах) и скорость машинки i (в метрах в секунду) соответственно (1 xi 
vi 1000).
Исходно никакие две машинки не находятся в одной точке. Гарантируется, что хотя бы один обгон во время гонки произойдет.
Формат выходных данных
В выходной файл выведите количество секунд, которое пройдет с момента старта до момента первого обгона, с точностью не менее 5 знаков после десятичной точки.
Примеры
| Входные данные | Выходные данные |
| 2 1 3 4 2 | 3.00000 |
| 2 12 20 2 21 | 10.00000 |
Пояснение для первого примера:
На рисунке точкой A обозначено место обгона.
Решение.
Алгоритм:
1)Машинка а когда-нибудь догонит машинку б, если её скорость больше, а координата меньше
2)Переберём каждую машинку с каждой и если одна машинка когда-нибудь обгонит другую(пункт 1), то посчитаем это время. Среди всех таких значений выберем минимальное. Это и будет ответом
Программа:
program gt;
var a,b:array[1..100000]of longint;
c:array[1..1000000]of real;
j,n,i,k,l:longint;
min:real;
begin
read(n);k:=0;
for i:=1 to n do
begin
read(a[i],b[i]);
end;
for i:=1 to n do
begin
for j:=1 to n do
begin
if(i<>j)and(a[i]<a[j])and(b[i]>b[j])then begin
k:=k+1;
c[k]:=(a[j]-a[i])/(b[i]-b[j]);
end;
end;
end;
min:=c[1];
for i:=2 to k do
begin
if(c[i]<min)then min:=c[i];
end;
writeln(min:1:5);
end.
Задача С. Тестирование
| Имя входного файла: | input.txt |
| Имя выходного файла: | output.txt |
| Ограничение по времени: | 2 секунды |
| Ограничение по памяти: | 64 мегабайта |
Одним из способов контроля знаний учащихся является проведение тестирований. На тестировании обычно предлагается несколько вопросов, для каждого из которых необходимо выбрать один из вариантов ответа. Для этого тестируемому выдается специальный бланк с вопросами и вариантами ответов.
Тестирования можно проводить одновременно для достаточно большого количества людей, поэтому возникает вопрос об эффективной обработке заполненных тестируемыми бланков. Во Флатландии эту проблему пытаются решить с помощью применения информационных технологий для автоматической обработки результатов тестирования.
Первым этапом является написание программы, которая бы вычисляла баллы за тест по известной информации о правильных ответах на вопросы и ответах, данных тестируемым. Ваша задача состоит в написании такой программы.
Формат входного файла
Первая строка входного файла содержит число n (1 ≤ n ≤ 100000) вопросов в тесте. Вторая строка входного файла содержит n целых чисел a1, a2, . . . , an — номера правильных вариантов ответов на каждый из вопросов. Третья строка входного файла содержит nцелых чисел b1, b2, . . . , bn — номера вариантов, выбранных тестируемым. Для чисел ai и bi верны неравенства 1 ≤ ai, bi ≤ 10.
Формат выходного файла
В выходной файл выведите число вопросов, на которые тестируемый дал правильный ответ.
Примеры входных и выходных файлов
| Входные данные | Выходные данные |
| 4 1 2 3 4 1 2 4 3 | 2 |
| 4 1 2 3 4 4 3 2 1 | 0 |
Решение.
Алгоритм:
Очень легкая задача. Считываем данные в два массива. Затем запускаем цикл до n и проверяем: если i-й элемент 1-го массива равен i-му элементу 2-го массива, то мы увеличиваем счетчик на 1.
Программа :
var
a,b:array[1..100000] of byte;
i,n, p:longint;
BEGIN
assign(input, 'input.txt');
reset(input);
assign(output, 'output.txt');
rewrite(output);
readln(n);
for i:=1 to n do
read(a[i]);
readln;
p:=0;
for i:=1 to n do begin
read(b[i]);
if a[i]=b[i] then
inc(p);
end;
writeln(p);
end.
Задача D. Соревнования картингистов
| Имя входного файла: | input.txt |
| Имя выходного файла: | output.txt |
| Ограничение по времени: | 4 секунды |
| Ограничение по памяти: | 64 мегабайта |
После очередного этапа чемпионата мира по кольцевым автогонкам на автомобилях с открытыми колёсами Формула-А гонщики собрались вместе в кафе, чтобы обсудить полученные результаты. Они вспомнили, что в молодости соревновались не на больших болидах, а на картах — спортивных автомобилях меньших размеров.
Друзья решили выяснить победителя в одной из гонок на картах. Победителем гонки являлся тот гонщик, у которого суммарное время прохождения всех кругов трассы было минимальным.
Поскольку окончательные результаты не сохранились, то каждый из n участников той гонки вспомнил и выписал результаты прохождения каждого из m кругов трассы. К сожалению, по этой информации гонщикам было сложно вычислить победителя той гонки. В связи с этим они попросили сделать это вас.
Требуется написать программу, которая вычислит победителя гонки на картах, о которой говорили гонщики.
Формат входного файла
Первая строка входного файла содержит два целых числа n и m (1 n m 100). Последующие 2 n строк описывают прохождение трассы каждым из участников. Описание прохождения трассы участником состоит из двух строк. Первая строка содержит имя участника с использованием только латинских букв (строчных и заглавных). Имена всех участников различны, строчные и заглавные буквы в именах различаются.
Вторая строка содержит m положительных целых чисел, где каждое число — это время прохождения данным участником каждого из m кругов трассы (каждое из этих чисел не превосходит 1000). Длина имени каждого участника не превышает 255.
Формат выходного файла
В выходной файл необходимо вывести имя победителя гонки на картах. Если победителей несколько, требуется вывести имя любого из них.
Примеры входных и выходных файлов
| Входные данные | Выходные данные |
| 5 3 Sumaher 2 1 1 Barikelo 2 1 2 Olonso 1 2 1 Vasya 1 1 1 Fedya 1 1 1 | Fedya |
Обращаем внимание на пробел в конце последней строки входных данных.
Решение.
Алгоритм:
Заведем отдельную строку для хранения фамилии игрока с лучшим результатом, и отдельную переменную для хранения этого результата. Затем присваиваем им результаты и фамилию 1-го гонщика, а затем считываем оставшиеся результаты и сравниваем с максимумом на данном шаге и, если требуется изменяем последний.
Программа :
var n,m,i,j,x,sum,min:longint;
s,s2:string;
begin
min:=maxlongint;
readln(n,m);
for i:=1 to n do
begin
readln(s);
sum:=0;
for j:=1 to m do
begin
read(x);
sum:=sum+x;
end;
readln;
if (sum<min) then
begin
min:=sum;
s2:=s;
end;
end;
writeln(s2);
end.
Задача Е. Дипломы
| Имя входного файла: | input.txt |
| Имя выходного файла: | output.txt |
| Ограничение по времени: | 4 секунды |
| Ограничение по памяти: | 64 мегабайта |
Когда Петя учился в школе, он часто участвовал в олимпиадах по информатике, математике и физике. Так как он был достаточно способным мальчиком и усердно учился, то на многих из этих олимпиад он получал дипломы. К окончанию школы у него накопилось n дипломов, причём, как оказалось, все они имели одинаковые размеры: w — в ширину и h — в высоту.
Сейчас Петя учится в одном из лучших российских университетов и живёт в общежитии со своими одногруппниками. Он решил украсить свою комнату, повесив на одну из стен свои дипломы за школьные олимпиады. Так как к бетонной стене прикрепить дипломы достаточно трудно, то он решил купить специальную доску из пробкового дерева, чтобы прикрепить её к стене, а к ней — дипломы. Для того чтобы эта конструкция выглядела более красиво, Петя хочет, чтобы доска была квадратной и занимала как можно меньше места на стене. Каждый диплом должен быть размещён строго в прямоугольнике размером w на h. Дипломы запрещается поворачивать на 90 градусов. Прямоугольники, соответствующие различным дипломам, не должны иметь общих внутренних точек.
Требуется написать программу, которая вычислит минимальный размер стороны доски, которая потребуется Пете для размещения всех своих дипломов.
Формат входного файла
Входной файл содержит три целых числа: w, h, n (1 w h n 109).
Формат выходного файла
В выходной файл необходимо вывести ответ на поставленную задачу.
Примеры входных и выходных файлов
| Входные данные | Выходные данные |
| 2 3 10 | 9 |
Иллюстрация к примеру:
Решение.
Алгоритм:
Из-за больших ограничений на n,w,h линейный перебор возможной длины стороны квадрата не проходит по времени, поэтому данную задачу следует решать, используя бинарный поиск по ответу. Очевидно, что размеры доски лежат в пределах от min(w,h) до n * max(w,h). За O(1) легко проверить, поместятся ли все грамоты в квадрат со стороной a (n <= (a / w) * (a / h)). Пускай мы уверены, что искомый ответ лежит в интервале от Min до Max, тогда проверим удовлетворяет ли условию квадрат со стороной Mid = (Min + Max) / 2. Если да, то Max = Mid, иначе Min = Mid+1. Выполняя эту процедуру до тех пор, пока не сойдутся Min и Max мы будем всё точнее получать возможный диапазон ответа (каждый раз область поиска уменьшается в 2 раза). Когда Min станет равно Max выведем значение Min и прекратим работу программы. Сложность такого решения: O(log(n*max(w,h))).
Программа:
function maxwh (w2, h2 :int64) :int64;
begin
if w2>h2 then maxwh:=w2 else maxwh:=h2;
end;
function maxd (w1, h1, mid1 : int64) : int64;
begin
maxd:=(mid1 div w1)*(mid1 div h1);
end;
var
w, h, n: int64;
hi, lo, mid : int64;
begin
readln(w, h, n);
hi:=maxwh(w, h)*n;
lo:=0;
while hi-lo>1 do
begin
mid:=(hi+lo) div 2;
if maxd(w, h, mid)<n then lo:=mid else hi:=mid;
end;
writeln(hi);
end
Дата добавления: 2021-12-10; просмотров: 149; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!