thirteen_bit, Ну просто перебрать все точки и найти ту, которая дает максимум. Если ищите среди выпуклого множества, то можно бинарным поиском искать - так быстрее, но сложнее.
floppa322, Зависит от задачи. Если у вас можно предметы использовать только по одному разу, то нельзя из только последней строки восстановить ответ. В некоторых задачах, как рюкзак без цен с повторениями, действительно, трюк с сокращением таблицы ДП не имеет недостатков.
FlashDok, Ну вот подумайте: если прямоугольник очень высокий, весь луч ни разу не отражается. его длина не зависит от высоты вообще. Если прямоугольник где-то в 2 раза ниже, чем если бы луч был от угла в угол, то луч был бы из двух сегментов. Если их выпрямить - то это будет все тот же прямой луч все той же длины. Т.е. очевино мы можем высоту менять очень в широких пределах не меняя длину.
Если все еще не верите, то в автокаде поиграйтесь с прямоугольником не меняя его длину и угол наклона.
FlashDok, а высота и не учитывается. Если вам надо именно до правой стенки длину подсчитать, то она от высоты не зависит. В более низких прямоугольниках будет просто больше отражений, но длина луча такая же.
FlashDok, где вы ее нашли и что она должна искать? Не подходит. Только первое слагаемое оставьте. Замените еостнус на синус, и если все еще не подходит.
kan3k1k3n, У вас там уже одно целое число. Если же вы хотите, чтобы в файле было "7", то читайте и пишите в текстовом режиме. Открывайте файл с "t" вместо "b" и читайте/пишите fscanf/fprintf, а не fread/fwrite.
Skodio29, да, придется только так. Любая библиотека, что вы откопаете, будет именно так и делать. И это достаточно простой код, чтобы написать его руками.
Xiran, Не влиет, конечно, но если вам нужна переносимость, то используйте, например int32_t. Так-то размер ptrdiff гарантируется быть хотя бы 17 бит, а сколько их там на другой платформе - вы знать не можете.
Скорее всего у вас там где-то Undefinded behavior. Ошибка, короче. Выложите код, чтобы его было удобно читать. Например, кажый файл в отдельный спойлер и в теге code. Или на pastebin. Качать архивы и в них ковырятся ради вас никто не будет.
Adamos, Ох, да. У вас решение за O(n^2) вместо O(n). Это называется "волновой алгоритм". Тоже из теории графов. Для уже упомянутого выше случая
в других вариантах было намного больше этажей
- ваше решение никуда не годится.
Вообще, математическая модель тут - граф. Вы можете сколько угодно отворачиваться от этого факта, но любое ваше решение в итоге будет алгоритмом на графе. Просто если теорию знать, то сразу понятно, какое решение тут хорошее, а какое - не очень. Это как, если вам дано квадратное уравнение, даже если там не x, а количество зайцев и все словами описано, то вы как его не решайте, в итоге все равно получите числа из формулы с дискриминантом.
значит, с рекурсией лучше не рисковать и развернуть ее в цикл.
Там 2 ветки, удачи ее разворачивать.
Но вообще, если, таки, составить математическую модель задачи (граф), то это стандартная задача поиска компоненты связности в графе. Решается или обходом в глубину (типа ваша рекурсия и получается, только стандартно. Понятно почему и как работает и доказано), или обходом в ширину (но это не "развернутая в цикл рекурсия". Это другой подход).
Adamos, Ну нет, граф-то строится элементарно. Он может быть несвязен и задача - найти размер компоненты связности со стартовой вершиной.
Можно граф даже не строить явно, а генерировать ребра на лету. Ну, будет у вас стек или очередь достигнутых вершин, берете оттуда вершину, получаете 2 другие и, если они не помечены - обрабатываете их. Если вершин так много, то надо пометки хранить в хеш-таблице. Но граф полезно себе передставить в любом случае.
Но вообще тут конкретная задача с конкретными ограниченями и нет никаких миллионов этажей - их 70.
