Комментарии 88
Второй вопрос простой:
1) Сначала зажигаем первую веревку с обоих концов, а вторую с одного.
2) Когда первая сгорит (а это произойдет ровно через 30 минут!) зажигаем вторую веревку с другого конца. Как догорит, так и 45 минут.
1) Сначала зажигаем первую веревку с обоих концов, а вторую с одного.
2) Когда первая сгорит (а это произойдет ровно через 30 минут!) зажигаем вторую веревку с другого конца. Как догорит, так и 45 минут.
Есть другой способ
Зажигаем первую с двух сторон — она сгорит за 30 минут, затем зажигаем вторую с двух сторон и из центра, т.о. огонь будет идти в 4-х направлениях и веревка сгорит за 15 минут, а в сумме как раз 45 искомых.
Не сработает. Поджигание верёвки одновременно с концов и посередине не гарантирует, что каждая половина сгорит за одно и то же время. Первая половина может сгореть за 5 минут, а вторая за 25.
Есть ещё другой способ:
При условии, что обе веревки имеют неравномерные сгорания одинаково, то поджечь первую с обеих сторон, а вторую с обеих сторон и с точно того же места, где догорела первая. Так 30+15=45
При условии, что обе веревки имеют неравномерные сгорания одинаково, то поджечь первую с обеих сторон, а вторую с обеих сторон и с точно того же места, где догорела первая. Так 30+15=45
В комменарии автора (где-то ниже ) написано, что концы неотличимы, но, по условиям задачи, веревки одинаковые.
Но вот чего нет в условии, так это утверждения, что локальная скорость горения веревки не зависит от направления горения. Ну, это кажется очевидным, однако, если таки зависит, то нет никакой гарантии, что веревка, подожженная с двух концов, сгорит за 30 минут.
Вот тут бы и помогла идентификация концов — 30 мин можно было бы померять положив веревки «навстречу» друг други и зажечь их опять же навстречу друг другу. Как точки горения совпадут так и 30 мин. Потом опять их сдвигаем конец к началу и опять ждем совпадения точек горения. Но вот если концы таки неотличимы, я пока не понимаю, что делать.
Но вот чего нет в условии, так это утверждения, что локальная скорость горения веревки не зависит от направления горения. Ну, это кажется очевидным, однако, если таки зависит, то нет никакой гарантии, что веревка, подожженная с двух концов, сгорит за 30 минут.
Вот тут бы и помогла идентификация концов — 30 мин можно было бы померять положив веревки «навстречу» друг други и зажечь их опять же навстречу друг другу. Как точки горения совпадут так и 30 мин. Потом опять их сдвигаем конец к началу и опять ждем совпадения точек горения. Но вот если концы таки неотличимы, я пока не понимаю, что делать.
3000 бананов
В итоге получится перевезти 500 бананов, скормить верблюду 2400 и 100 останется в пустыне, если первые 500км каждые 100км провозить все что есть, возвращаясь назад.
0. 3000 бананов
100км. 2500 бананов (взял 1000 бананов с отметки 0 привез 900 бананов, взял 100 бананов, поехал на отметку 0, повторил)
200км. 2000 бананов
300км. 1700 бананов
400км. 1400 бананов
500км. 1100 бананов
Далее берем 1000 бананов и едем в конечный пункт
600км. 900 бананов
700км. 800 бананов
800км. 700 бананов
900км. 600 бананов
1000км. 500 бананов
0. 3000 бананов
100км. 2500 бананов (взял 1000 бананов с отметки 0 привез 900 бананов, взял 100 бананов, поехал на отметку 0, повторил)
200км. 2000 бананов
300км. 1700 бананов
400км. 1400 бананов
500км. 1100 бананов
Далее берем 1000 бананов и едем в конечный пункт
600км. 900 бананов
700км. 800 бананов
800км. 700 бананов
900км. 600 бананов
1000км. 500 бананов
А почему это максимум?
Ага, можно больше довезти таким способом, а именно:
1) Тащим бананы на отметку 200 км за 5 ходок, где окажется 3000-200*5=2000 бананов.
2) Тащим бананы далее на 333 км за 3 ходки до отметки 533 км, где окажется 1001 банан.
3) Тащим 1000 бананов до конца. Дистанция 467 км. Итого довозим 1000-467 = 533.
Но я все равно не уверен, что и это — максимум.
1) Тащим бананы на отметку 200 км за 5 ходок, где окажется 3000-200*5=2000 бананов.
2) Тащим бананы далее на 333 км за 3 ходки до отметки 533 км, где окажется 1001 банан.
3) Тащим 1000 бананов до конца. Дистанция 467 км. Итого довозим 1000-467 = 533.
Но я все равно не уверен, что и это — максимум.
Теоретический максимум - 666 бананов.
Нам нужно максимизировать удельную стоимость перевозки на один километр.Очевидно, за 2 ходки перевезти не получиться, поэтому рассчитаем решение пренебрегая (пока) краевым условием когда верблюду не нужно возвращаться в последний раз: будем считать, что каждый раз верблюду нужно возвращаться. Допустим х — это один банан (он же километр).
На х километров возможно перевезти только (1000-2х) бананов, при условии что нужно возвращаться. Стоимость перевозки при этом окажется 2х бананов, которые будут съедены.
Целевая функция оптимизации — это количество полезной нагрузки делить на количество съеденных бананов.
f(x)= (1000-2x)/2x -> max
Берем производную, приравниваем к нулю и находим х
Это — обычная гипербола, которая стремиться к бесконечности около нуля. Ответ — максимальная производительность при минимальном шаге. Проверим численно:
Едем на 500 километров — получаем 0 полезной нагрузки и 1000 бананов съедено
Едем на 1 километр — получаем 998 полезной нагрузки и 2 съеденных банана.
Получается, все итерационные циклы выгоднее всего делать с минимальным шагом. Допустим, наш минимальный шаг будет 1 (в случае дробного шага результат будет почти таким же — но об этом в конце)
Дальше — excel, хотя сейчас я понимаю, что можно и мысленно было:
Этап 1 — перевозим все доступные бананы за 3 ходки на 1 километр за каждый шаг.
Этап 1. Шаг 1. Перевозим все бананы на 1-ый километр. Расход — 6 бананов за три ходки. Итог — доступно 2994, все находятся на 1-ом километре.
Этап 1. Шаг 2. Перевозим все доступные бананы с 1-ого на 2-ой километр. Расход — 6 бананов. Итог — доступно 2988, все находятся на 2-ом километре.
…
Этап 2. На 167 километре у нас будет доступно 1998 бананов. С этого момента, стоимость перевозки всех бананов на следующий километр будет 4 банана.
Этап 2. Шаг 1. Перевозим все бананы с 167-ого на 168-ой километр. Расход — 4 банана, итог — доступно 1986 бананов.
…
Этап 3. На 666 километре у нас остается 1000 бананов. С этого момента вся модель перестает работать, потому что нам больше не нужно возвращаться. Это то самое краевое условие, которым мы пренебрегли. Берем все бананы и едем до конца.
Расход — 334 банана, итог — 666 бананов на 1000-ом километре.
Если бы бананы были бесконечно делимы, то с почти нулевым шагом мы бы перевезли 2/3 всех бананов как предел ряда. Точно ряд сейчас не сформулирую, но думаю ход мысли понятен.
На х километров возможно перевезти только (1000-2х) бананов, при условии что нужно возвращаться. Стоимость перевозки при этом окажется 2х бананов, которые будут съедены.
Целевая функция оптимизации — это количество полезной нагрузки делить на количество съеденных бананов.
f(x)= (1000-2x)/2x -> max
Берем производную, приравниваем к нулю и находим х
Это — обычная гипербола, которая стремиться к бесконечности около нуля. Ответ — максимальная производительность при минимальном шаге. Проверим численно:
Едем на 500 километров — получаем 0 полезной нагрузки и 1000 бананов съедено
Едем на 1 километр — получаем 998 полезной нагрузки и 2 съеденных банана.
Получается, все итерационные циклы выгоднее всего делать с минимальным шагом. Допустим, наш минимальный шаг будет 1 (в случае дробного шага результат будет почти таким же — но об этом в конце)
Дальше — excel, хотя сейчас я понимаю, что можно и мысленно было:
Этап 1 — перевозим все доступные бананы за 3 ходки на 1 километр за каждый шаг.
Этап 1. Шаг 1. Перевозим все бананы на 1-ый километр. Расход — 6 бананов за три ходки. Итог — доступно 2994, все находятся на 1-ом километре.
Этап 1. Шаг 2. Перевозим все доступные бананы с 1-ого на 2-ой километр. Расход — 6 бананов. Итог — доступно 2988, все находятся на 2-ом километре.
…
Этап 2. На 167 километре у нас будет доступно 1998 бананов. С этого момента, стоимость перевозки всех бананов на следующий километр будет 4 банана.
Этап 2. Шаг 1. Перевозим все бананы с 167-ого на 168-ой километр. Расход — 4 банана, итог — доступно 1986 бананов.
…
Этап 3. На 666 километре у нас остается 1000 бананов. С этого момента вся модель перестает работать, потому что нам больше не нужно возвращаться. Это то самое краевое условие, которым мы пренебрегли. Берем все бананы и едем до конца.
Расход — 334 банана, итог — 666 бананов на 1000-ом километре.
Если бы бананы были бесконечно делимы, то с почти нулевым шагом мы бы перевезли 2/3 всех бананов как предел ряда. Точно ряд сейчас не сформулирую, но думаю ход мысли понятен.
"На 666 километре у нас остается 1000 бананов". Почему? На 167 было было 1986. Перевоз на 1км занимает 4 банана. Тогда 986/4=246 км, то есть 1к можно доставить только до 167+246=413км
Этап 1. Шаг 1. Перевозим все бананы на 1-ый километр. Расход — 6 бананов за три ходки. Итог — доступно 2994, все находятся на 1-ом километре.
Ну, на этом шаге Вы посчитали один лишний банан, потому что, чтобы увезти все 3000 бананов на 1 км верблюд пройдет 5 км — 3 раза туда и 2 обратно.
Этап 2. На 167 километре у нас будет доступно 1998 бананов. С этого момента, стоимость перевозки всех бананов на следующий километр будет 4 банана.
На 200-м километре останется 2000 бананов, далее километр будет стоить 3 банана.
Этап 3. На 666 километре у нас остается 1000 бананов.
Это как??? 10001 банан останется на отметке 200+333=533 км. Даже если начинать с 200 км…
Итого 534/533 банана в зависимости от алгоритма верблюда. Кстати везти можно не по километру, а до точки слома модели. Т.е. первых три перехода в точку 200км, тогда от первой и второй 1000 остается 600, а от третьей 800.
Далее два перехода в точку 533 км.
Остается вопрос — нет ли точки где выгодно выбросить часть бананов. Точнее не возвращаться за ними. Имеется ввиду что мы изменим длины переходов как-то таким образом, что при последнем переходе в целевую точку, на предыдущей точке останется бананов столько же сколько стоит доставка из нее. Можно подумать что выбрав такие точки мы можем увеличить полезную загрузку.
Предположим что есть такой участок в пределах первых 200км и в точку 200км можно прийти не 3, а 2 раза. Но придя два раза, при любой загрузке невозможно получить более 1998 бананов, а у нас уже есть решение которое позволяет получить в этой точке 2000 бананов, что больше. Аналогичные рассуждения можно привести и для точки 533 км. И того максимум это 533 или 534 банана в зависимости от алгоритма верблюда, так как в точке 533 км становится важным ест ли верблюд свой банан авансом.
Далее два перехода в точку 533 км.
Остается вопрос — нет ли точки где выгодно выбросить часть бананов. Точнее не возвращаться за ними. Имеется ввиду что мы изменим длины переходов как-то таким образом, что при последнем переходе в целевую точку, на предыдущей точке останется бананов столько же сколько стоит доставка из нее. Можно подумать что выбрав такие точки мы можем увеличить полезную загрузку.
Предположим что есть такой участок в пределах первых 200км и в точку 200км можно прийти не 3, а 2 раза. Но придя два раза, при любой загрузке невозможно получить более 1998 бананов, а у нас уже есть решение которое позволяет получить в этой точке 2000 бананов, что больше. Аналогичные рассуждения можно привести и для точки 533 км. И того максимум это 533 или 534 банана в зависимости от алгоритма верблюда, так как в точке 533 км становится важным ест ли верблюд свой банан авансом.
Тут можно было получить 534 банана: не обязательно давать верблюду банан после того как он достиг километра 1000
Так-то
1) 200 км за 5 ходок = 200*5*2, верблюду надо возвращаться и его надо тоже кормить. За 200км мы теряем 2000 бананов, а не 1000.
1) 200 км за 5 ходок = 200*5*2, верблюду надо возвращаться и его надо тоже кормить. За 200км мы теряем 2000 бананов, а не 1000.
Если идти по одному километру то получається 533 банана.
Не понимаю, как так получается, потому что при таком подходе верблюд значительную часть времени будет недогруженным (как решении IgnisDeus), а жрать все равно по банану на километр, в то время как у меня получились те же 533 банана при 100% загрузке верблюда.
Хотя результаты моего первого шага совпадают с результатом 2-х первых шагов решения IgnisDeus, где верблюд тоже в конце второго шага тащил лишь 500 бананов.
Хотя результаты моего первого шага совпадают с результатом 2-х первых шагов решения IgnisDeus, где верблюд тоже в конце второго шага тащил лишь 500 бананов.
А верблюд потребляет бананы только тогда, когда ходит нагруженный? Когда ходит пустой — не потребляет?
А неважно какой именно отрезок проходить. Важно то, что пока бананов больше 2000 расход 5 бананов на километр. Больше 1000 — 3 банана на километр.
Следовательно, на первой тысяче бананов верблюд пройдёт 1000/5= 200 км. На второй тысяче — 1000/3= 333.(3) километров. После чего у него останется идти 1000 — 533 = 467 км, на которые он потратит 467 бананов. Значит останется 533 банана. Всё. По сколько именно идти в пределах этих километров значения не имеет.
Следовательно, на первой тысяче бананов верблюд пройдёт 1000/5= 200 км. На второй тысяче — 1000/3= 333.(3) километров. После чего у него останется идти 1000 — 533 = 467 км, на которые он потратит 467 бананов. Значит останется 533 банана. Всё. По сколько именно идти в пределах этих километров значения не имеет.
Этот вариант мне каженся самым простым решением. Если задасться вопросом об оптимальном расстоянии то тут важны точки излома. То есть првое перемещение должно быть 0 < X <=200. Если например перенести на 201 км. то мы потеряем на нем два банана (5 — 3) т.к. ходок на последнем километре будет 5 а могло уже быть три.
А если взять эталонную дистанцию в районе 300-400кма затем каждую следующую часть переносить на несколько меньшую дистанцию.? Верблюд все равно будет есть в процессе а значит можно будет попутно добирать бананы с чекпоинтов.
В вашем варианте верблюд будет по дороге съедать свой груз. Полностью он загружен только в начале каждого этапа, а, например, в точке 100км на первом этапе он будет нести 900 бананов.
Всё просто. Первые 200 км верблюду нужно пройти пять раз, независимо от того, будет он делать ходки по 200 или по одному километру. Следующие 333⅓ километра необходимо пройти три раза, и остаток пути — один раз. Таким образом, пройденное расстояние будет 200×5 + 333⅓×3 + (1000 — 200 — 333⅓) = 2466⅔ километра. Если за последние ⅔ км верблюду банан не дать, то в конечный пункт прибудет 534 банана.
Как донести 750 бананов
(считаем, что верблюд не потребляет бананы, не будучи нагруженным)
1. Берём 1000 бананов, каждый километр один банан съедаем, один кладём. На 500 км поворачиваем назад
2. Берём 1000 бананов, проходим 500 км (остаётся 500 бананов), раскладываем бананы ещё на 250 бананов ещё на 250 км.
3. Берём последнюю тысячу бананов, первые 750 км питаемся разложенными бананами, последние 250 съедаем, 750 доносим.
1. Берём 1000 бананов, каждый километр один банан съедаем, один кладём. На 500 км поворачиваем назад
2. Берём 1000 бананов, проходим 500 км (остаётся 500 бананов), раскладываем бананы ещё на 250 бананов ещё на 250 км.
3. Берём последнюю тысячу бананов, первые 750 км питаемся разложенными бананами, последние 250 съедаем, 750 доносим.
И даже 833 ⅓
Опять таки, по аналогии с другими решениями — пустой верблюд бананов не потребляет
1. Идём 333 ⅓ км, оставляем каждый километр по два банана (на отметке 333 ⅓ оставляем две трети банана, треть съедаем), идём назад пустые
2. Проходим 333 ⅓ на оставленных бананах (один остаётся лежать), далее раскладываем ещё на 500 км вперёд по одному банану на километр
3. Проходим 833 ⅓ на оставленных бананах, съедаем 166 ⅔ банана на оставшиеся километры, доносим 833 ⅓
1. Идём 333 ⅓ км, оставляем каждый километр по два банана (на отметке 333 ⅓ оставляем две трети банана, треть съедаем), идём назад пустые
2. Проходим 333 ⅓ на оставленных бананах (один остаётся лежать), далее раскладываем ещё на 500 км вперёд по одному банану на километр
3. Проходим 833 ⅓ на оставленных бананах, съедаем 166 ⅔ банана на оставшиеся километры, доносим 833 ⅓
С таким предположением можно и больше: двигаемся по 1 км до 333км. Получаем 2001 банан. Выкидываем 1. Движемся на км 833 (сейчас км стоит 2 банана). Получаем 1000. Движемся оставшиеся 167км. Доставляем 834 банана (последний банан верблюду не даем т.к. мы уже у цели).
А на возвращение верблюд не тратит бананы?
533/534 банана
Пока бананов больше 2000, расход идёт 5 бананов/км. Проходим 200 км.
Пока бананов больше 1000, расход идёт 3 банана/км. Проходим ещё 333 км.
Итого на точке 533 км остаётся 1001 банан и остаётся пройти 467 км.
Пока бананов больше 2000, расход идёт 5 бананов/км. Проходим 200 км.
Пока бананов больше 1000, расход идёт 3 банана/км. Проходим ещё 333 км.
Итого на точке 533 км остаётся 1001 банан и остаётся пройти 467 км.
Первая задача тоже была бы легкая, если бы было указано, что все даты (годы?) разные — тогда надо смешать годы рождения и смерти в общий список и отсортировать его по возрастанию года (не забывая, это год рождения или смерти) а потом пробежаться по списку, прибавляя или отнимая единицу от изначально нулевого счетчика в зависимости от того, что это за дата. Ответ ищется в том же проходе. Пока счетчик растет, запоминаем/передвигаем начало периода, как упадет, запоминаем период и число живых слонов. И так далее (может встретиться второй максимум)…
А вот если год смерти одного слона совпадает с годом рождения другого слона, тут непонятно, был ли момент времени, что оба слона были живы?
А вот если год смерти одного слона совпадает с годом рождения другого слона, тут непонятно, был ли момент времени, что оба слона были живы?
Задача не до конца определена как мне кажется. Но есть пример который показывает как поступать с границами периодов. Поэтому я бы решал так. В сначала пришёлся бы по всем слонам и создал бы массив год -> число слонов. Потом нашёл бы в этом массиве максимум возможно не один и представил уже в виде интервалов. Если быть уже совсем строгим то год рождения и смерти нужно исключать т.к. мы показывает в интервале период о 0101 00:00:00 и рождениеслона в этот момент невероятно.
А что такого сложного в третьей задаче? Идем по массиву, как i-й элемент оказался меньше предыдущего, так и все. Если дошли до конца, ответ — 0
P.S. Ну, можно еще после нахождения k дойти до конца, для проверки валидности входных данных…
P.S. Ну, можно еще после нахождения k дойти до конца, для проверки валидности входных данных…
думаю, что важно упомянуть о том, что решений может быть бесконечно много с периодом, равным длине массива
Предположим, 2-й элемент оказался меньше предыдущего, тогда каков будет ответ?
Наверное предполагалось что будет небольшая оптимизация. Фактически нужно сравнивать границы последовав ателье ости если сортировка нарушена то делить пополам или другим способом и брать отрезок где сортировка опять же нарушена. Пока не останется отрезок длинной два.
Вопрос 2. — Видел задачу в другом месте (хотя сам не решил)
Задача 3. — Поиск минимума? Или пары рядом стоящих чисел, когда первое больше второго.
Задача 2. За 1 проход заносим в Хэш значения квадратов элементов. А далее двойным циклом складываем квадраты элементов и проверяем наличие такого же значения в Хэше.
Задача 1. Необходимо определиться, как интерпретировать [2000,2010],[2010,2020], т.е. случай когда год смерти одного слона совпадает с годом рождения другого слона. Можно ли считать, что [2000,2020] жил ровно 1 слон, или же [2010,2010] жило 2 слона.
Предположим первое. Заводим Хэш, где год — ключ, а значение — +1 если это дата рождения, -1 если это дата смерти. Если в 1 год родилось 5 слонов, а умерло 2, тогда в хеше будет 5-2=3. Затем выгружаем все не нулевые значения Хэша в массив, сортируем его, и за 1 проход получаем решение. Сложность O(n*lon(n)) за счет сортировки.
Можно по иному пойти, выгрузить даты рождения в 1 массив, а смерти в другой массив. Отсортировать оба, и совместным прохождением по обоим массивам найти ответ. Сложность та же.
Про бананы и верблюда ещё думаю.
Задача 3. — Поиск минимума? Или пары рядом стоящих чисел, когда первое больше второго.
Задача 2. За 1 проход заносим в Хэш значения квадратов элементов. А далее двойным циклом складываем квадраты элементов и проверяем наличие такого же значения в Хэше.
Задача 1. Необходимо определиться, как интерпретировать [2000,2010],[2010,2020], т.е. случай когда год смерти одного слона совпадает с годом рождения другого слона. Можно ли считать, что [2000,2020] жил ровно 1 слон, или же [2010,2010] жило 2 слона.
Предположим первое. Заводим Хэш, где год — ключ, а значение — +1 если это дата рождения, -1 если это дата смерти. Если в 1 год родилось 5 слонов, а умерло 2, тогда в хеше будет 5-2=3. Затем выгружаем все не нулевые значения Хэша в массив, сортируем его, и за 1 проход получаем решение. Сложность O(n*lon(n)) за счет сортировки.
Можно по иному пойти, выгрузить даты рождения в 1 массив, а смерти в другой массив. Отсортировать оба, и совместным прохождением по обоим массивам найти ответ. Сложность та же.
Про бананы и верблюда ещё думаю.
Можно по иному пойти, выгрузить даты рождения в 1 массив, а смерти в другой массив. Отсортировать оба, и совместным прохождением по обоим массивам найти ответ. Сложность та же.
Если работать с массивами дат, то наглядней перевести их в множества (set в Python) и найти результирующее множество сделав пересечение множеств. Потом берем минимум и максимум из этого результирующего множества.
У меня получилось максимум всего лишь 416 бананов.
Сначала забрасываем бананы на 250-ый километр в три этапа, итого там будет 1500 бананов, половину мы потеряем, скормили прожорливому верблюду.
Затем закидываем на 416-ый километр остальные 1000 бананов, потеряв 500 бананов.
Основная цель — это найти максимальный километр, куда можно закинуть 1К бананов.
Дальше грузим всю тысячу и идем до конца, в итоге довозим всего лишь 416 бананов.
Сначала забрасываем бананы на 250-ый километр в три этапа, итого там будет 1500 бананов, половину мы потеряем, скормили прожорливому верблюду.
Затем закидываем на 416-ый километр остальные 1000 бананов, потеряв 500 бананов.
Основная цель — это найти максимальный километр, куда можно закинуть 1К бананов.
Дальше грузим всю тысячу и идем до конца, в итоге довозим всего лишь 416 бананов.
Если забрасывать бананы сразу на 250км то теряется лишние 100=(250-200)*2 банана
Хотя я чуть неправильно посчитал, на 250 у меня будет 1750.
Ну да, если на 200-ый, то мы там будем иметь там 2000 бананов.
Едем на 333 км еще, оставляем на 533-ем 333 банана, возвращаемся, берем 1К, в итоге привозим 533 банана.
По моей схеме имеем 1750 на 250-ом км.
Отвозим еще на 250 км, на 500-й 250 бананов, возвращаемся за 1К, едем в конечную точку, подбираем на 500-ом 250 бананов, в итоге получается привезем 500 бананов.
Да, получается, что на 200-ый лучше сначала.
Ну да, если на 200-ый, то мы там будем иметь там 2000 бананов.
Едем на 333 км еще, оставляем на 533-ем 333 банана, возвращаемся, берем 1К, в итоге привозим 533 банана.
По моей схеме имеем 1750 на 250-ом км.
Отвозим еще на 250 км, на 500-й 250 бананов, возвращаемся за 1К, едем в конечную точку, подбираем на 500-ом 250 бананов, в итоге получается привезем 500 бананов.
Да, получается, что на 200-ый лучше сначала.
Anti-clockwise rotated array
По-моему у вас ошибка в примерах ответа: в первом случае ответ — 4, во втором — 1 и в третьем все правильно — 0
По-моему у вас ошибка в примерах ответа: в первом случае ответ — 4, во втором — 1 и в третьем все правильно — 0
my $arr = [ 15, 18, 2, 3, 6, 12 ];
sub get_turn_count
{
my $arr = shift;
my @sorted = sort { $a <=> $b } @$arr;
my $k = 0;
while( 1 )
{
last if( join( ',', @$arr ) eq join( ',', @sorted ) );
$k++;
unshift( @$arr, pop( @$arr ) );
}
return $k
}
print get_turn_count( $arr ), " \n";
Вы правы, почему-то мысленно поворачивал по часовой, поэтому не заметил расхождения условий с примером. Исправлено.
Да, зря я поленился написать код с unit-тестами, в результате чего, чего, честно говоря, тоже «решил» задачу про поворот по часовой стрелке. Т.е. правильный ответ будет что-то типа n-i, где i — результат «моего» вчерашнего алгоритма.
P.S. Ваш код, наверное (я даже язык не могу угадать) правильный, но сильно неэффективный. Сначала сортировка массива, а потом в цикле еще и циклический сдвиг. Т.е. сложность типа O(N^2). А можно O(N).
P.S. Ваш код, наверное (я даже язык не могу угадать) правильный, но сильно неэффективный. Сначала сортировка массива, а потом в цикле еще и циклический сдвиг. Т.е. сложность типа O(N^2). А можно O(N).
Язык Perl.
Сортировка — это O(log N) один раз.
А дальше стандартные функции для работы с массивами, со списками добавление элемета в начало массива и выталкивание последнего. Не могу точно сказать какая тут сложность, но если это динамический массив, то тоже O(N) получается.
Сортировка — это O(log N) один раз.
А дальше стандартные функции для работы с массивами, со списками добавление элемета в начало массива и выталкивание последнего. Не могу точно сказать какая тут сложность, но если это динамический массив, то тоже O(N) получается.
Сортировка — это O(log N) один раз.
Сортировка O(log N)? Скорее O(N*log N). а это уже больше O(N)…
Ну, стоимость прокрутки массива, если это не плоский массив, а список, действительно может стоить фиксированное время, но уж сравнение двух массивов длиной N на равенство (в прошлый раз не заметил), опять N/2 раз, это уж точно получится O(N^2).
Хотя сортировка — это O(n log n)
А сравнение двух массивов — это O(2N), причем по сортированному не нужно было мне проходится в цикле каждый раз, можно было бы join его вычислить перед циклом, так что сложность сравнения тут O(N)
Итого O(n log n) + k * O(N)
А сравнение двух массивов — это O(2N), причем по сортированному не нужно было мне проходится в цикле каждый раз, можно было бы join его вычислить перед циклом, так что сложность сравнения тут O(N)
Итого O(n log n) + k * O(N)
Да, но в худшем случае k=N, в среднем k=N/2. А ответ ищется одним линейным проходом по массиву. Как нашли a[i-1] > a[i], так и ответ нашли (N-i, если индексация начинается с нуля). Если не нашли, ответ 0.
В задаче кажется требовался только ответ с числом в условии. Но линейный проход не обязателен можно искать делением массива пополам.
А можно на код посмотреть?
Буду рядом с компьютером напишу. А что есть подозрение что будут проблемы?
Были. Я по scientific computing специализируюсь, А тут, вроде и не поиск корня, или экстремума у выпуклой функции, поэтому и самому в голову не пришло, и в Вашем подходе, мягко говоря, засомневался.
Только после третьего вашего сообщения решил на всякий случай картинку на бумажке нарисовать и теперь на могу с Вами не согласиться. Действительно O(log N), причем независимо ни от чего. Снимаю шляпу.
P.S. А код напишите для фиксации рекорда.
Только после третьего вашего сообщения решил на всякий случай картинку на бумажке нарисовать и теперь на могу с Вами не согласиться. Действительно O(log N), причем независимо ни от чего. Снимаю шляпу.
P.S. А код напишите для фиксации рекорда.
Код я имел в виду такой. Но теперь я понимаю что Ваш вариант был правильный а мой нет. Весь вопрос как трактовать тексо возрастающая последовательность. Я могу ошибаться но кажется возрастающая и неубывающая это разные вещи. То есть возрастающая не подразумевает повторения значений. Но не сказана что последовательность возрастающая а сказано отсортирована по возрастанию. То есть она неубывающая в строгом смысле. Если значения будут повторяться (неубывающая) то вот такой массив будет проанализировать проще протым перебором при этом от начала и до конца
[5,5,5,5,5,5,5,5,5]
[5,5,5,5,5,2,5,5,5].
Я так понимаю что давая такую задачу тестирующий хочет понять какие у тестируемого будут варианты проверки и будет ли он проходить массив от начала и до конца и остановится ли на первом равестве 5 = 5 значит ротация была 0.
Хотя может быть и другой вариант например что в условии сказано что «по возрастанию» значит это буквально равных быть не может.
[5,5,5,5,5,5,5,5,5]
[5,5,5,5,5,2,5,5,5].
Я так понимаю что давая такую задачу тестирующий хочет понять какие у тестируемого будут варианты проверки и будет ли он проходить массив от начала и до конца и остановится ли на первом равестве 5 = 5 значит ротация была 0.
Хотя может быть и другой вариант например что в условии сказано что «по возрастанию» значит это буквально равных быть не может.
var array = [2,3,6,7,8,9,1]
console.log(rotatedBy(array));
function rotatedBy(array) {
var left = 0;
var right = array.length - 1;
var middle;
if (array.length <=1 || array[left] < array[right]) {
return 0;
}
while (right - left > 1 && array[left] > array[right]) {
middle = Math.floor((left + right) / 2);
if (array[left] > array[middle]) {
right = middle;
} else {
left = middle;
}
}
return array.length - right;
}
и кстати для массива [5,5,5,5,5,5,5,5] задача как бы вырождается и вариантов будет от 0 до длины массива минус один. А может быть это тест на адекватность? Если тестируемый начинает задавать тестирующему такие вопросы то он в каждой задаче будет видеть проблемы там где их нет?
Все нормально, в условии задачи сказано, что все числа разные.
Да, вы правы, вот так гораздо эффективнее:
my $arr = [ 15, 18, 2, 3, 6, 12 ];
sub get_turn_count
{
my @arr = @_;
my $min = List::Util::min( @arr );
my $k = 0;
foreach ( @arr )
{
if( $arr[ 0 ] == $min and $arr[ - 1 ] != $arr[ 0 ] )
{
last;
}
unshift( @arr, pop( @arr ) );
$k++;
}
return $k;
}
print get_turn_count( @$arr ), " \n";
По условию задачи, массив был отсортирован и потом «повернут» несколько раз. Т.к. он отсортирован, первый элемент — минимальный. Каждый поворот смещает первый элемент на 1 влево (первый раз — в конец массива). Таким образом, за один проход ищем минимальный элемент и запоминаем его позицию. Ответ n-k+1. Отдельно обрабатывается случай когда минимальный — первый элемент, значит поворотов не было (или было n).
Для поворота в другую сторону ответ k-1.
P.S. Возможно, я неправильно понял условие задачи, но мне непонятно зачем в решении поворачивать входной массив. Нам ведь не надо восстановить отсортированный? Также мое решение исходит из того, что на входе — корректные данные, т.е. это действительно отсортированный массив, который «повернули». Для восстановления исходного массива достаточно сделать еще один проход (в копию ставим элементы на нужный индекс), для проверки сортировки — тоже один с попарным сравнением с предыдущим элементом.
Для поворота в другую сторону ответ k-1.
P.S. Возможно, я неправильно понял условие задачи, но мне непонятно зачем в решении поворачивать входной массив. Нам ведь не надо восстановить отсортированный? Также мое решение исходит из того, что на входе — корректные данные, т.е. это действительно отсортированный массив, который «повернули». Для восстановления исходного массива достаточно сделать еще один проход (в копию ставим элементы на нужный индекс), для проверки сортировки — тоже один с попарным сравнением с предыдущим элементом.
Да, вы правы, переставлять элементы тут лишнее.
use List::Util ();
my $arr = [ 15, 18, 2, 3, 6, 12 ];
sub get_turn_count
{
my @arr = @_;
my $min = List::Util::min( @arr );
my $k = 0;
foreach ( 0 .. $#arr )
{
if( $arr[ $k ] == $min and $arr[ $k - 1 ] > $el )
{
last;
}
$k++;
}
return scalar( @arr ) - $k;
}
print get_turn_count( @$arr ), " \n";
У меня вопросы по шнурам:
1. То что одна половина горит 10 мин, а другая 50 мин — это конкретные условия задачи или просто как пример, на самом деле время может отличаться и оно не известно?
2 Если целиком шнур горит неравномерно, то половины горят равномерно?
3. Можно ли отличить концы шнуров, т.е. с какой стороны быстрее, а с какой медленнее сразу же, до зажигания?
1. То что одна половина горит 10 мин, а другая 50 мин — это конкретные условия задачи или просто как пример, на самом деле время может отличаться и оно не известно?
2 Если целиком шнур горит неравномерно, то половины горят равномерно?
3. Можно ли отличить концы шнуров, т.е. с какой стороны быстрее, а с какой медленнее сразу же, до зажигания?
1. Функция длины сгоревшей части шнура — монотонно возрастающая непрерывная функция, равная нулю при T=0 и равная длине шнура при T=1 час. Все.
2. Половины по длине? Нет. См. п.1
3. Нет. см. п.1
2. Половины по длине? Нет. См. п.1
3. Нет. см. п.1
1. Точное время горения половин неизвестно. Может быть 15/45, например. А могут и равномерно, я думаю.
2. Нет.
3. Нет.
2. Нет.
3. Нет.
Задачу с массивом можно решить за O(log N) бинарным поиском. Сначала берем первый элемент и средний (в одну из сторон, тут неважно), если средний больше первого, минимум в верхней части массива, если меньше, то в нижней. Продолжаем, пока длина массива не станет 2, тогда тот элемент, что меньше из двух, и будет минимальным. Индексы считаем параллельно нахождению минимума, и выдаем индекс наружу, потом если он 0, то массив не сдвинут, если не ноль, то вычитаем его из длины (так как массив сдвигался влево), получаем ответ.
Возможно, я неправильно понял алгоритм, но мне кажется он сломается на примерах {2,3,4,5,1} и {5,1,2,3,4}.
Проблема с бинарным поиском в том, что числа расположены не монотонно. Например, для {3,4,5,1,2} ряд возрастает до третьего элемента, а потом убывает.
Поправьте меня, если я ошибся.
Проблема с бинарным поиском в том, что числа расположены не монотонно. Например, для {3,4,5,1,2} ряд возрастает до третьего элемента, а потом убывает.
Поправьте меня, если я ошибся.
Задачу с верёвкой я бы решал «сложением» :)
Нужно сложить одну верёвку пополам, а вторую — вчетверо.
Когда первая верёвка полностью сгорит, пройдёт 30 минут. Когда вторая — ещё 15 минут.
Нужно сложить одну верёвку пополам, а вторую — вчетверо.
Когда первая верёвка полностью сгорит, пройдёт 30 минут. Когда вторая — ещё 15 минут.
Про бананы мне кажется можно проще объяснить, чем через функции. Пока условно предположим, что перевозим максимум на 1 км. потом возвращаемся. На первые километры тратится по 5 бананов на километр (пока не останется 2000, или потратить 1000), затем по 3 (пока не останется 1000 или снова потратить 1000) и дальше по одному.
Итого первую тысячу (5 бананов на км) мы потратим за 200 км. вторую за 333 (1 банан теряем так как его перевозка дороже его самого) ну и последнюю 1000 везем оставшиеся 467км, значит с тысячи довезем 533.
Итого первую тысячу (5 бананов на км) мы потратим за 200 км. вторую за 333 (1 банан теряем так как его перевозка дороже его самого) ну и последнюю 1000 везем оставшиеся 467км, значит с тысячи довезем 533.
Расстояния не обязательно кратны километра и нет уверенности что такой ответ действительно максимум и не даёт ключа к решению в общем случае. Например сколько будет от 3007 бананов.
сколько будет от 3007 бананов
На семь бананов при макс.загрузке 1000 проехать удастся только 1км., т.е. привезем на один банан больше (534).
нет уверенности что такой ответ действительно максимум и не даёт ключа к решению в общем случае.
Как раз дает, но если расстояния кратны километру. Если не кратны, то вопрос, как мы считаем нецелые бананы, а также как считается половина банана во рту у верблюда при расчете его грузоподъемности. По мне, такие вопросы позволяют "закопать" исходную задачу без какого-либо изменения понимания того, как думает собеседник, решивший задачу в целых числах.
Почему максимум — а потому, что каждый километр мы преодолеваем, используя наименьшую возможную стоимость километра в бананах, которая зависит от того, сколько неполных тысяч бананов у нас есть на текущий момент. При 3007 бананов их 4, и стоимость километра оказывается 7.
Целый банан не означает целого километра в одну сторону. Это мтожет быть три ходуи по 1/3 километра. Я просто мог немного подготовить данные так чтобы эти части бананов накапливались и у вашего способа получилось расхождение. Но даже не это главное. Главное что в общем методе все решается проще и точнее.
Согласен — такое объяснение сработает только в целых числах. В случае деления километров и бананов превратиться в:
Итого первую тысячу (5 бананов на км) мы потратим за 200 км. вторую за 333.(3), ну и последнюю 1000 везем оставшиеся 466.(6) км, значит с тысячи довезем 533,(3). При условии «непрерывного потребления» в конце.
Итого первую тысячу (5 бананов на км) мы потратим за 200 км. вторую за 333.(3), ну и последнюю 1000 везем оставшиеся 466.(6) км, значит с тысячи довезем 533,(3). При условии «непрерывного потребления» в конце.
Про бананы прочитал несколько неправильных решений. Почему-то многие забывают кормить верблюда на обратном пути в промежуточных ходках…
Задачу со шнурами видел слишком много раз
Верблюды
Моё решение в 444 банана, и я не знаю как больше. Отнесём 333 банана на треть пути, съев треть от тысячи на пути туда, и треть — обратно. Отнесём 444 банана на 444 км, съев 444 банана. Ещё 111 съедим на пути назад до 333 километра, там подбираем оставленые бананы, чтобы хватило добраться до дома. Берём последнюю 1000 бананов и везём на 444 километр, там подсаправляемся до упора и идём на целевую точку. Эфективность веблюда получается меньше 15% =(
Задачу со шнурами видел слишком много раз
Слоны:
создадим из данных вида [2006, 2010] записи вида 2006-тру, 2010-фолс. Отсортируем записи со всех слонов по году. Теперь пройдемся от начала до конца, создавая список. Каждому новому интервалу времени между фактами рождения/смерти слона добавляем новый элемент списка вида [ количество_слонов = запись[i].ключ? список[i-1].количество_слонов + 1: список[i-1].количество_слонов + 1;
где нулевой элемент создаётся с нулем слонов.
Потом ищем номер элемента с большим числом слонов. Он равен номеру записи с началом соответствующего интервала времени. Конец — в следующем элементе массива записей.
Задача решается за две сортировки по всем данным. Дополнительно можно оптимизировать обработку одинаковых годов, но если таких много, то быстрее создавать меньший массив из всех годов. Зависит от того, какие данные — больше чем один слон в год, или меньше. Также разумно встроить дополнительную проверку на ноль в последнем элементе списка.
где нулевой элемент создаётся с нулем слонов.
Потом ищем номер элемента с большим числом слонов. Он равен номеру записи с началом соответствующего интервала времени. Конец — в следующем элементе массива записей.
Задача решается за две сортировки по всем данным. Дополнительно можно оптимизировать обработку одинаковых годов, но если таких много, то быстрее создавать меньший массив из всех годов. Зависит от того, какие данные — больше чем один слон в год, или меньше. Также разумно встроить дополнительную проверку на ноль в последнем элементе списка.
Тройки Пифагора
есть три уравнения, которые вместе определяют пространство троек пифагора. Проверяются для двух меньших чисел. Значит ищем по наименьшему числу какие могут быть вторые, затем по двум — третье. Если не находим — берём следующее по размеру, и так до третьего с конца
...и последняя
Тут мы просто идём по массиву и сравниваем значение с предыдущим, пока неравенство не сработает. Можно идти от начала к концу и вычесть потом из длинны массива, а можно сразу идти с конца и инкрементировать счётчик оборотов, потом просто брейкануть цикл и вывести его.
В чем ошибка такого решения: habrahabr.ru/company/spice/blog/348122/#comment_10653124 (533.5 банана)?
Все верблюды накормлены. Были правда попытки зажать полбанана после работы но это уже наш менталитет. Нести бананы на треть пути сразу невыгодно ту передаются лишние бананы. Первая остановка должна быть максимум на 200 км
Да, я нашёл меньшее решение. Но я не понял почему именно столько в том решении.
Если мы предполагаем что «перевезти больше всего бананы на некоторую промежуточную базу 1, использую ровно тысячу, перевезти больше всего бананов на базу 2, используя ровно тысячу, овезти все бананы до конца» — это оптимальная стратегия, то я разобрался почему именно 534 — это максимум. Но почему эта стратегия оптимальна? Где доказательства что перевозка на одну базу а не две, или на 6, или через каждый км не будет эффективнее? Как именно формально доказать что это наиболее эффективно?
Если мы предполагаем что «перевезти больше всего бананы на некоторую промежуточную базу 1, использую ровно тысячу, перевезти больше всего бананов на базу 2, используя ровно тысячу, овезти все бананы до конца» — это оптимальная стратегия, то я разобрался почему именно 534 — это максимум. Но почему эта стратегия оптимальна? Где доказательства что перевозка на одну базу а не две, или на 6, или через каждый км не будет эффективнее? Как именно формально доказать что это наиболее эффективно?
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Выпуск#9: ITренировка — актуальные вопросы и задачи от ведущих компаний