A
так и получаем 14м 16д
Size: a a a
2016 November 23
A
сложность O(Log N)
A
вот интересное решение со сложностью О(1)
A
Очень просто. Берешь любое соотношение м и д. Нпрмр 1д 29м смотришь что получается. 5*1 + 29*3 = 92
Потом смотришь что будет если прибавить одну девушку (соответственно отнять мальчика): 2д и 28м. Смотришь.
2*5 + 18*3 = 94
Смотришь некий шаг: 94 - 92 = 2. Шаг равен 2
Смотришь сколько шагов надо сделать: 122 - 92 = 30. Делишь на шаг 30/2 = 15
Нужно сделать 15 шагов
Потом смотришь что будет если прибавить одну девушку (соответственно отнять мальчика): 2д и 28м. Смотришь.
2*5 + 18*3 = 94
Смотришь некий шаг: 94 - 92 = 2. Шаг равен 2
Смотришь сколько шагов надо сделать: 122 - 92 = 30. Делишь на шаг 30/2 = 15
Нужно сделать 15 шагов
AK
Очень просто. Берешь любое соотношение м и д. Нпрмр 1д 29м смотришь что получается. 5*1 + 29*3 = 92
Потом смотришь что будет если прибавить одну девушку (соответственно отнять мальчика): 2д и 28м. Смотришь.
2*5 + 18*3 = 94
Смотришь некий шаг: 94 - 92 = 2. Шаг равен 2
Смотришь сколько шагов надо сделать: 122 - 92 = 30. Делишь на шаг 30/2 = 15
Нужно сделать 15 шагов
Потом смотришь что будет если прибавить одну девушку (соответственно отнять мальчика): 2д и 28м. Смотришь.
2*5 + 18*3 = 94
Смотришь некий шаг: 94 - 92 = 2. Шаг равен 2
Смотришь сколько шагов надо сделать: 122 - 92 = 30. Делишь на шаг 30/2 = 15
Нужно сделать 15 шагов
O(n)
AK
За единицу считает система, всё тут
A
ну почему же
1) взять 0 и 30, умножить — это О(1)
2)взять 1 и 29, умножить — это О(1)
3) 2) - 1) — О(1)
4)общая сумма - 1) — О(1)
5) 4)/3) — О(1)
и это количество шагов коснтантно сколько бы ни было большим число
получаем О(1)
1) взять 0 и 30, умножить — это О(1)
2)взять 1 и 29, умножить — это О(1)
3) 2) - 1) — О(1)
4)общая сумма - 1) — О(1)
5) 4)/3) — О(1)
и это количество шагов коснтантно сколько бы ни было большим число
получаем О(1)
AM
Очень просто. Берешь любое соотношение м и д. Нпрмр 1д 29м смотришь что получается. 5*1 + 29*3 = 92
Потом смотришь что будет если прибавить одну девушку (соответственно отнять мальчика): 2д и 28м. Смотришь.
2*5 + 18*3 = 94
Смотришь некий шаг: 94 - 92 = 2. Шаг равен 2
Смотришь сколько шагов надо сделать: 122 - 92 = 30. Делишь на шаг 30/2 = 15
Нужно сделать 15 шагов
Потом смотришь что будет если прибавить одну девушку (соответственно отнять мальчика): 2д и 28м. Смотришь.
2*5 + 18*3 = 94
Смотришь некий шаг: 94 - 92 = 2. Шаг равен 2
Смотришь сколько шагов надо сделать: 122 - 92 = 30. Делишь на шаг 30/2 = 15
Нужно сделать 15 шагов
Почему шаг не посчитать просто как разность между взымаемыми суммами?
NK
Офк так и надо)
AK
ну почему же
1) взять 0 и 30, умножить — это О(1)
2)взять 1 и 29, умножить — это О(1)
3) 2) - 1) — О(1)
4)общая сумма - 1) — О(1)
5) 4)/3) — О(1)
и это количество шагов коснтантно сколько бы ни было большим число
получаем О(1)
1) взять 0 и 30, умножить — это О(1)
2)взять 1 и 29, умножить — это О(1)
3) 2) - 1) — О(1)
4)общая сумма - 1) — О(1)
5) 4)/3) — О(1)
и это количество шагов коснтантно сколько бы ни было большим число
получаем О(1)
Почитай про О-нотацию. Ты несешь хуйню
AM
Почитай про О-нотацию. Ты несешь хуйню
Чем объясняется линейная сложность тогда?)
AK
У тебя есть n человек и сумма S. Посчитай в общем случае
AM
Я посчитал, при любом s и n получаю 4 действия, где линейная сложность?
DS
Есть задачка с олимпиады Яндекса, интересно кому ?
A
Я посчитал, при любом s и n получаю 4 действия, где линейная сложность?
вот и я о том же
GM
Есть задачка с олимпиады Яндекса, интересно кому ?
Всем интересно, но все стесняются
AK
Вах, прошу прощения, невнимательно прочитал (e.g. забил читать после второй строки), я не прав.
DS
Есть массив A
Надо вывести медианы подмасивов А[:i], где i от 1 до n
Надо вывести медианы подмасивов А[:i], где i от 1 до n
DS
Числа целые
A
интересно