Разборы задач №3 - бинарный поиск и перебор

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

Как можно быстрее – codeforces 701D

Как можно быстрее – codeforces 701D

Как можно быстрее – codeforces 701D
Примеры

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

Как можно быстрее – codeforces 701D

Как можно быстрее – 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
using namespace std;
int main() {
string a,b;
cin>>a>>b;
int n=max(a.size(),b.size());
if(a.size()
else if(b.size()
int c[100002];
for( int i=0;i
c[i]=a[i]-b[i];
}
for( int i=0;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

Осада Вальгаллы – 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
Примеры

Эклеры – 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

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

Two's complement – 1 – informatics 750
Примеры

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

Планирование экспедиции – codeforces 1011B
int find_res1(int people, int l, int r, vector
F){
int p = 0;
if (r - l == 1)
{
for (unsigned int i = 0; i < F.size(); i++)
p += F[i] / r;
if (p >= people)
return r;
else
return l;
}
int m = (l + r)/2;
for (unsigned int i = 0; i < F.size(); i++)
p += F[i] / m;
if (p >= people) return find_res1(people, m, r, F);
else return find_res1(people, l, m, F);}

Лавочки – codeforces 1019B

Лавочки – codeforces 1042A

Лавочки – codeforces 1042A
Примеры

Лавочки – codeforces 1042A
Для максимума находим наибольшее число людей на лавочке и добавляем туда всех пришедших.
Для минимума в цикле распределяем всех пришедших по наименее занятым лавочкам.
int main(){
unsigned int n, m;
cin>>n>>m;
int *a=new int [n];
for (int i=0;i
cin>>a[i];
int max=0;
for (int i=0;i
if (a[max]
max=i;
max=a[max]+m;
while (m>0)
{
int min=0;
for (int i=0;i
{
if (a[min]>a[i])
min=i;
}
a[min]++;
m--;
}
int min=0;
for (int i=0;i
if (a[min]
min=i;
min=a[min];
cout<
return 0;
}

Шляпа – codeforces 1019B

Шляпа – codeforces 1019B

Шляпа – codeforces 1019B
Примеры

Шляпа – codeforces 1019B

Шляпа – codeforces 1019B