Презентация Разборы задач 3 - бинарный поиск и перебор онлайн

Содержание слайда: Разборы задач №3 Бинарный поиск и перебор

Содержание слайда: Содержание 3 – Как можно быстрее – codeforces 701D 10 – Осада Вальгаллы – codeforces 975C 14 – Эклеры – codeforces 991C 18 – Планирование экспедиции – codeforces 1011B 23 – Лавочки – codeforces 1042B 26 – Шляпа – codeforces 1019B

Содержание слайда: Как можно быстрее – codeforces 701D На каникулах n школьников решили сходить на экскурсию и собрались все вместе. Им необходимо преодолеть путь длиной l метров. Каждый из школьников будет идти со скоростью . Чтобы быстрее добраться до экскурсии было принято решение арендовать автобус, вместимостью человек (то есть одновременно в автобусе не может находиться более k человек) и скоростью . Чтобы никого из школьников не укачало, каждый из них хочет сесть в автобус не более одного раза. Перед вами стоит задача определить минимальное время, по истечении которого все n школьников смогут добраться до места проведения экскурсии. Считайте, что посадка и высадка пассажиров, а также разворот автобуса, происходят мгновенно и этим временем можно пренебречь.

Содержание слайда: Как можно быстрее – codeforces 701D

Содержание слайда: Как можно быстрее – codeforces 701D

Содержание слайда: Как можно быстрее – codeforces 701D Очевидно, что искомый ответ лежит в пределах от 0 до n*l. Разобьем школьников на группы по вместимости автобуса: (n+k-1)/k. Чтобы получить искомое время, мы можем использовать бинарный поиск по ответу. Если целевая функция будет возвращать истину, то мы будем сдвигать правую границу поиска, а если ложь – левую.

Содержание слайда: Как можно быстрее – codeforces 701D Рассмотрим время, которое требуется проехать на автобусе, чтобы первая группа дошла как раз за время mid. это время равно , где изначально T равно mid, posM равно 0 (в этой позиции мы будем поддерживать позицию школьников, которые еще не ехали в автобусе). Затем нужно аккуратно пересчитывать T и posM для каждой следующей группы, учитывая, что автобус должен вернуться обратно, чтобы забрать следующую группу. Если в какой-то момент стало меньше, чем l - posM, либо T стало меньше 0, нужно вернуть false. Если все группы школьников успеют добраться за время T, нужно вернуть true. Также нужно не забыть, что после того, как автобус отвезет последнюю группу школьников, возвращаться обратно ему не нужно.

Содержание слайда: Как можно быстрее – codeforces 701D bool check(double T, int n,int l,int v1,int v2,int k) { double start = 0; double t0 = 0; double left = n; if (T*v1 >= l) return true; while (left > 0) { double t = l-start+v1*(t0-T); double y=v2-v1; double x = t/y; left -= k; double busLoc = start+x*v2; start += x*v1; double timeBack = (busLoc-start)/(v2+v1); start += timeBack*v1; t0 += x+timeBack; if (t0-timeBack > T) return false; } return true; }

Содержание слайда: Золотая система счисления – codeforces 457A #include <bits/stdc++.h> using namespace std; int main() { string a,b; cin>>a>>b; int n=max(a.size(),b.size()); if(a.size()<n) a=string(n-a.size(),'0')+a; else if(b.size()<n) b=string(n-b.size(),'0')+b; int c[100002]; for( int i=0;i<n;i++){ c[i]=a[i]-b[i]; } for( int i=0;i<n-2;i++){ if(c[i]>2) { cout<<">"; return 0; } if(c[i]<-2) { cout<<"<"; return 0; } c[i+1]+=c[i]; c[i+2]+=c[i]; c[i]=0; } if(c[n-2]==0 && c[n-1]==0){ cout<<"="; return 0; } if(c[n-2]>0 || (c[n-2]==0 && c[n-1]>0)) { cout<<">"; return 0; } cout<<"<"; return 0; }

Содержание слайда: Осада Вальгаллы – codeforces 975C Ивар Бескостный — великий лидер. Он пытается захватить Каттегат, в данный момент находящийся под контролем Лагерты. Битва началась, и волны воинов Ивара гибнут одна за другой. У Ивара n воинов, он выставляет их вдоль прямой напротив главных ворот так, что i-й воин стоит сразу за (i−1)-м воином. Первый воин возглавляет атаку. Каждый атакующий воин может выдержать до стрел, прежде чем он падёт, где — сила i-го воина. Лагерта приказывает своим воинам выпустить стрел в течение i-й минуты, стрелы одна за одной поражают первого всё ещё стоящего воина. После того, как все воины Ивара падут и стрелы, находящиеся в воздухе в данный момент, пролетят, Тор бьёт по земле своим молотом и все воины Ивара получают свои силы назад и возвращаются в битву. Другими словами, если все воины умрут в минуту t, в конце этой минуты t они все встанут и будут сражаться.

Содержание слайда: Осада Вальгаллы – codeforces 975C

Содержание слайда: Осада Вальгаллы – codeforces 975C Примеры

Содержание слайда: Осада Вальгаллы – codeforces 975C Сперва определимся с тем, какими будут совокупные силы воинов, для чего просуммируем силы i-того воина и всех предыдущих. Аналогично поступим со стрелами. Теперь мы знаем, что за i-тую минуту будет выпущено t стрел, которые убьют h воинов. Если совокупно стрел на i-той больше, чем совокупная сила всех воинов, то мы можем вернуть n - все воины умрут, а потом воскреснут. Иначе мы можем определить, сколько умерло воинов, и вернуть в качестве i-того значения разницу между числом оставшихся воинов и числом умерших воинов.

Содержание слайда: Эклеры – codeforces 991C После успешной сдачи всех зачетов Вася купил себе в подарок коробку, содержащую n сладких эклеров. Вася решил каждое утро есть некоторое одинаковое число эклеров, пока они все не закончатся. Однако сосед Васи, Петя, заметил принесенную Васей коробку и тоже решил насладиться вкусом эклеров. Теперь процесс поедания эклеров выглядит следующим образом: сначала Вася выбирает число k, одинаковое для всех дней. Затем утром он съедает k эклеров из коробки (или доедает все эклеры, если их осталось меньше k), после этого Петя вечером съедает 10% оставшихся эклеров. Если эклеры еще не закончились, то на следующий день Вася опять съедает k эклеров, а Петя — 10% от оставшихся и так далее. Если число эклеров не делится на 10, то Петя округляет «свою» долю в меньшую сторону, например, если в коробке было 97 эклеров, то Петя съест только 9 из них. В частности, если в коробке уже меньше 10 эклеров, то Петя не будет их есть вообще. Определите, какое наименьшее число k может выбрать Вася такое, что он съест не менее половины от всех n эклеров, которые были в коробке изначально. Заметьте, что число k должно быть натуральным.

Содержание слайда: Эклеры – codeforces 991C Входные данные В первой строке содержится натуральное число ) — изначальное количество эклеров. Выходные данные Вывести единственное число — наименьшее значение k, удовлетворяющее Васю.

Содержание слайда: Эклеры – codeforces 991C Очевидно, что если для некоторого k условие задачи выполняется – Вася съест более половины эклеров, то и для любого большего k условие выполнится. Тогда мы можем решить задачу с помощью бинарного поиска по ответу. Мы будем сдвигать левую границу, если данное k нас не удовлетворяет, и правую – если при данном k условие выполнится.

Содержание слайда: Эклеры – codeforces 991C bool check(long long k, long long n) { long long sum = 0; long long cur = n; while (cur > 0) { long long o = min(cur, k); sum += o; cur -= o; cur -= cur / 10; } return sum * 2 >= n; }

Содержание слайда: Планирование экспедиции – codeforces 1011B Наташа планирует экспедицию на Марс для n человек. Важная задача — обеспечить питанием каждого участника в каждый из дней экспедиции. Всего на складе доступны m суточных комплектов питания. Каждый комплект характеризуется своим типом . Каждый из участников в день должен съедать ровно один суточный комплект питания. По причине экстремальных нагрузок, каждый участник в каждый из дней экспедиции должен съедать комплект одного и того же типа. Для разных участников типы съедаемых комплектов могут как различаться, так и совпадать. Формально, для каждого участника j Наташа должна выбрать тип питания и каждый день j-й участник должен съедать комплект питания типа . Значения у разных участников могут как различаться, так и совпадать. Какой максимальной продолжительности в днях можно спланировать экспедицию, чтобы выполнить требования выше?

Содержание слайда: Планирование экспедиции – codeforces 1011B Входные данные В первой строке записаны два целых числа n и m — количество участников экспедиции и количество суточных комплектов питания на складе. Во второй строке записана последовательность целых чисел , где — тип i-го комплекта питания. Выходные данные Выведите максимальное количество дней, сколько может продолжаться экспедиция. Если невозможно спланировать экспедицию даже на один день, то выведите 0.

Содержание слайда: Two's complement – 1 – informatics 750

Содержание слайда: Планирование экспедиции – codeforces 1011B Сперва определимся с тем, сколько каких комплектов нам досталось. Очевидно, что ответ не может превышать количество еды. Тогда мы можем реализовать бинарный поиск. Будем рассматривать величину , где F[i] - кол-во комплектов, l, r - нижняя и верхняя граница дней в экспедиции. В первой итерации l=0,r=m; По сути мы рассматриваем то, на людей хватит комплектов питания по группам для количества дней r. Если p<n, то сдвигаем r влево, иначе сдвигаем l вправо Если r-l=1, то то делаем то же, что и в пункте а, если p<n, то выводим в качестве ответа l, иначе - r.

Содержание слайда: Планирование экспедиции – codeforces 1011B

Содержание слайда: Лавочки – codeforces 1019B В берляндском парке есть n лавочек. Про каждую лавочку известно количество людей , которые уже сидят на i-й лавочке. Известно, что в ближайшее время в парк придут ещё m человек, каждый из которых сядет на одну из n лавочек. Пусть k — это максимальное количество человек, которые будут сидеть на одной лавочке после прихода в парк ещё m человек. Определите минимально возможную величину k и максимально возможную величину k. Считайте, что никто из посетителей парка не будет вставать с лавочек.

Содержание слайда: Лавочки – codeforces 1042A Входные данные В первой строке следует целое число — количество лавочек в парке. Во второй строке следует целое число — количество людей, которые ещё придут в парк и сядут на лавочки. В следующих n строках следует по одному целому числу — количество людей, которые изначально сидят на i-й лавочке. Выходные данные Выведите минимально возможную величину k и максимально возможную величину k, где k — это максимальное количество человек, которые будут сидеть на одной лавочке после прихода в парк ещё m человек.

Содержание слайда: Лавочки – codeforces 1042A

Содержание слайда: Лавочки – codeforces 1042A Для максимума находим наибольшее число людей на лавочке и добавляем туда всех пришедших. Для минимума в цикле распределяем всех пришедших по наименее занятым лавочкам.

Содержание слайда: Шляпа – codeforces 1019B

Содержание слайда: Шляпа – codeforces 1019B Входные данные: на вход подаётся одно целое чётное число — число участников, пришедших на клуб Имура. Вам разрешается задать не более 60 вопросов. Выходные данные: для того, чтобы узнать число i-го участника , нужно вывести «? i». После этого ваша программа на вход получит целое число — число на листочке i-го человека. Чтобы сообщить, что ответ найден, требуется вывести «! i», где i — номер любого участника из пары . Если такой пары участников не существует, выведите «! -1». После этого программа должна завершиться. Запрос на вывод ответа не входит в ограничение на 60 запросов. Не забывайте сбрасывать буфер после каждого запроса. Например, на C++ надо использовать функцию fflush(stdout), на Java вызов System.out.flush(), на Pascal flush(output) и stdout.flush() для языка Python.

Содержание слайда: Шляпа – codeforces 1019B

Содержание слайда: Шляпа – codeforces 1019B Пусть a(i) — листок на числе i-го школьника. Введем функцию . Поскольку n четно, то b(i) корректно определена. Заметим два факта: во-первых, , а во-вторых, . Задача заключается в поиске i такого, что b(i) = 0. Из второго наблюдения можно заметить, что все b(i) имеют одинаковую четность. Поэтому, посчитаем b(0), и если оно нечетно, то ответа нет, и нужно вывести  - 1 — все b(i) имеют одинаковую четность (нечетную), и ноль, как число другой четности, в b(i) не появится.

Содержание слайда: Шляпа – codeforces 1019B Иначе, пусть мы посчитали b(0), и оно оказалось равным какому-то числу x (без ограничения общности x > 0). Заметим, что . Поскольку из второго наблюдения мы помним, что все b(i) имеют одинаковую четность, и соседние отличаются не больше, чем на 2, можно воспользоваться дискретной непрерывностью. Лемма: если есть два индекса i, j со значениями b(i), b(j), то на отрезке между i и j есть все значения той же четности от min(b(i), b(j)) до max(b(i), b(j)). Действительно, поскольку соседние b изменяются не больше, чем на 2, мы не могли пропустить ни одно число той же четности. Теперь можно применить двоичный поиск с границами 0 и . Сдвиги границ будут производиться в зависимости от знака b(m). Если b(m)=0, то поиск прекращается.

Содержание слайда: Шляпа – codeforces 1019B