XerimHD, Можно. Вы там где на try_counter реагируете, вставьте break. И после цикла по collision точно так же сделайте: если try_counter большой - делайте break.
1) Код не весь. Начало цикла преведено, а конец и, особенно, условие выхода из внутреннего цикла - нет.
2) В каком цикле оно виснет?
3) Что этот код должен делать по вашей задумке?
дискретность все портит.
Как в задаче о рюкзаке - вроде понятно, что надо брать самые дорогие на кг предметы, но так можно делать, только если предметы сильно меньше оставшегося места.
А в этой задаче бинпоиск (оно же дихотомия по ответу) - стандартный прием. Вместо того, чтобы считать время от количества шаров, что очень сложно, можно всего за логарифм вывернуть задачу наизнанку и считать количество шаров от времени. Это решение за O(n log n). Быстрее решения, насколько я могу судить, не существует.
Это хорошая идея, но она страдает той же проблемой: если все надувальщики отдыхают после каждого шара, и у них времена все разные, то у вас будет фактически по одному шару и считаться. Этих самых сегментов может быть очень-очень много.
mrbudson, Если выигрышный ход еще не найден, то переходим к следующему ходу. Работает в связке с циклом while несколько строчек выше. Вообще, написанно не самым очевидным способом. Это было бы лучше в виде, допустим цикла for и выхода через break.
Думайте, что происходит, если winner() вернет computer или нет.
mrbudson, Она проверяет, что функция winner() возвращает computer. Логично предположить, что это означает, что компьютер побеждает на данной конфигурации доски.
В общем случае - сложно понять. Надо или подобрать 2 точки, которые дают одинаковое значение у функции, или как-то доказать, что таких быть не может. Если функция непрерывна, то можно доказать, что она монотонна и тогда уникальность всех значений очевидна. Именно этот случай тут и происходит (найдите производную для -1
Fomkol, Файлы никак не отслеживаются. Ничего на вашем компьютере странного не происходит, и переустанавливать ничего не надо, если вы только этот скрипт каждый день не запускаете. Прекратите его запускать и все. Однако, в момент, когда вы этот скрипт запускали, разработчики Геншина видели ваши обращения к своим серверам. С их серверов вы эти данные никак не сотрете, если они их там собирают. Если вас еще не забанили, то уже вряд ли что-то сделают.
Аналогия тут: этот скрипт - это дубликат ключа к черному ходу на склад геншина. Вы когда им пользуетесь туда залезаете и запись в каком-то журнале смотрите. Если там были камеры - вы уже ничего не сделаете. Но тела никакого нет, чтобы его надо было специально прятать. Если там не было камер - то вам ничего делать не надо.
sirenko, я лишь сказал, как найти площадь пустого пространства среди заданных блоков. Как их упаковывать- это отдельная очень сложная задача. Можно предположить, что у вас не будет островов если все коробки класть так, чтобы они положенного уже как-то касались. Тогда не надо мучатся с лучами. Надо только учесть, что одна "пустая" область максимального размера будет на самом деле бесконечной внешностью: ее надо проигнорировать.
Еще, стоит полумать, вдруг в задаче можно класть блоки так, чтобы замкнутых пустот не образовывалось вообще.
sirenko, увы, при попытке описать метод нашелся косяк. Обход в ширину со сжатием координат быстрее. Это будет O(n^2).
Другой быстрый метод, действительно за n log n: построить граф из линий и обойти все ребра. Что-то вроде этого: e-maxx.ru/algo/facets
Надо построить граф, где вершины - это углы блоков, а ребра - линии между ними. Для этого точки надо отсортировать 2 раза: по x, y а потом по y, x.
Но проблема этого алгоритма, что он не обработает области с дырками, вроде пустоты в которой коробками ограниченна другая область. Это можно обойти, если добавить еще линии на граф. Из каждого левого верхнего угла пустите вверх луч, пока он не пересечет другой блок. Это можно все за n log n сделать методом сканирующей прямой снизу вверх. У вас может начаться луч или встретится нижняя грань блока. Храните лучи в балансированном дереве (set) и при границе отсекайте те лучи, которые с ней пересекаются. В c++ это легко делается через lower_bound у set, в js вам придется писать свое BST похоже.
Лучи, которые не пересеклись ни с чем, надо запомнить.
Потом, когда вы все области получили, если в ней есть ребро от блока по часовой стрелке и нет верхнего ребра блока с незакрытым лучем - это пустая область.
Еще есть метод сканирующей прямой и системы непересекающихся множеств. Работать это все будет где-то за O(n log n), но без хорошего опыта с алгоритмами вы это вряд ли напишите. Но если хотите, могу объяснить.
хм, а если в таком случае для i-го веса перебирать все N предметов ?
Не поможет. Проблема в том, что вы не знаете, какие из предметов можно брать для текущего i-ого веса - вдруг они вам очень нужны в конце будут. И просто по одной последней строке вы никак это не определите вообще. И в итоге ваше восстановление ответа может взять один предмет несколько раз, или, если этого избегать, прийти в тупик: все возможные предметы для i-ого веса уже взяты в ответ и что делать вообще непонятно.
Иногда можно прям в массиве хранить множество всех предметов, Но это уже не O(S) памяти. Возможно, это все равно меньше O(SN) для полной матрицы, но не факт.
thirteen_bit, Ну просто перебрать все точки и найти ту, которая дает максимум. Если ищите среди выпуклого множества, то можно бинарным поиском искать - так быстрее, но сложнее.
floppa322, Зависит от задачи. Если у вас можно предметы использовать только по одному разу, то нельзя из только последней строки восстановить ответ. В некоторых задачах, как рюкзак без цен с повторениями, действительно, трюк с сокращением таблицы ДП не имеет недостатков.
