V🇺
и еще видимо есть особый случай когда B<4
Size: a a a
2020 September 13
ЕВ
Ааа, да. Без -1
ЕВ
и еще видимо есть особый случай когда B<4
Сейчас подумаю
DB
Ребят, а можно вопрос по числам.
Пусть нам нужно максимизировать k для заданных A >= 0, B >= 0:
4a + b = k^2, a <= A, b <= B.
Рассмотрим случай B > 0
Я утверждаю, что тогда
k = floor(sqrt(4*A+B))
То есть мы подставляем максимальные a, b и если мы не получаем полный квадрат, то мы точно сможем подобрать a, b так, чтобы в сумме получить квадрат числа на единицу меньше.
Вроде, похоже на правду, так как квадрат любого числа либо 4*p, либо 4*p +1.
Может, кто-то опровергнуть такое утверждение?
Пусть нам нужно максимизировать k для заданных A >= 0, B >= 0:
4a + b = k^2, a <= A, b <= B.
Рассмотрим случай B > 0
Я утверждаю, что тогда
k = floor(sqrt(4*A+B))
То есть мы подставляем максимальные a, b и если мы не получаем полный квадрат, то мы точно сможем подобрать a, b так, чтобы в сумме получить квадрат числа на единицу меньше.
Вроде, похоже на правду, так как квадрат любого числа либо 4*p, либо 4*p +1.
Может, кто-то опровергнуть такое утверждение?
просто 4*p или 4*p+1, без квадратов
ЕВ
и еще видимо есть особый случай когда B<4
По-идее достаточно только B == 0.
При B > 0:
Если квадрат числа floor(sqrt(4A+B)) чётный, то мы его получим только с помощью А, а если нечётный, то прибавим 1 из B
При B > 0:
Если квадрат числа floor(sqrt(4A+B)) чётный, то мы его получим только с помощью А, а если нечётный, то прибавим 1 из B
ЕВ
Но нужно проверить
ЕВ
просто 4*p или 4*p+1, без квадратов
Ну да, это и имел в виду, описался...
A
Ну да, достаточно только рассмотреть B == 0
V🇺
По-идее достаточно только B == 0.
При B > 0:
Если квадрат числа floor(sqrt(4A+B)) чётный, то мы его получим только с помощью А, а если нечётный, то прибавим 1 из B
При B > 0:
Если квадрат числа floor(sqrt(4A+B)) чётный, то мы его получим только с помощью А, а если нечётный, то прибавим 1 из B
да, похоже на правду
A
если B > 0, то перебирая все возможные a и b, можно получить все возможные квадраты, которые меньше 4A+B. В случае B == 0 не все, а только четные.
ЕВ
Топ, спасибо всем👌
AS
Привет, подскажите, пожалуйста, каким образом можно найти кратчайший путь в невзвешенном графе с помощью поиска в ширину? То есть аутпут не true/false, а путь [v1, v2, v5, v6], к примеру.
MB
Для этого надо вычислить prev[v] - эта вершина, из которой мы пришли в v
MB
Ну и тогда кратчайший путь это идти по prev-ам
2020 September 14
AO
Ребят, кто может обьяснить идею этого алгоритма. Посмотрел дискасс, но ничего не понял
https://leetcode.com/problems/longest-palindrome/solution/
Моя идея была вот в чем. Т.к. нам нужно сгенерировать палиндром, мы можем посчитать количество четных символов.
Т.е. у нас может 2 ситуации. Или у нас всё четные. Или всё четные 1 нечетнае последовательность где-нибудь в центре
Вот так попытался реализовать.
https://pastebin.com/PHxA3nXh
Читаю дискасс и солюшн, вроде там написано тоже самое, а дальше происходит вот это
и я такой, эээ, что, как, зачем, почему?
Буду признателен, если кто-то сможет обьяснить. Спасибо!
https://leetcode.com/problems/longest-palindrome/solution/
Моя идея была вот в чем. Т.к. нам нужно сгенерировать палиндром, мы можем посчитать количество четных символов.
Т.е. у нас может 2 ситуации. Или у нас всё четные. Или всё четные 1 нечетнае последовательность где-нибудь в центре
Вот так попытался реализовать.
https://pastebin.com/PHxA3nXh
Читаю дискасс и солюшн, вроде там написано тоже самое, а дальше происходит вот это
ans += v / 2 * 2; и вот это if (... && v % 2 == 1) и я такой, эээ, что, как, зачем, почему?
Буду признателен, если кто-то сможет обьяснить. Спасибо!
P
Ребят, кто может обьяснить идею этого алгоритма. Посмотрел дискасс, но ничего не понял
https://leetcode.com/problems/longest-palindrome/solution/
Моя идея была вот в чем. Т.к. нам нужно сгенерировать палиндром, мы можем посчитать количество четных символов.
Т.е. у нас может 2 ситуации. Или у нас всё четные. Или всё четные 1 нечетнае последовательность где-нибудь в центре
Вот так попытался реализовать.
https://pastebin.com/PHxA3nXh
Читаю дискасс и солюшн, вроде там написано тоже самое, а дальше происходит вот это
и я такой, эээ, что, как, зачем, почему?
Буду признателен, если кто-то сможет обьяснить. Спасибо!
https://leetcode.com/problems/longest-palindrome/solution/
Моя идея была вот в чем. Т.к. нам нужно сгенерировать палиндром, мы можем посчитать количество четных символов.
Т.е. у нас может 2 ситуации. Или у нас всё четные. Или всё четные 1 нечетнае последовательность где-нибудь в центре
Вот так попытался реализовать.
https://pastebin.com/PHxA3nXh
Читаю дискасс и солюшн, вроде там написано тоже самое, а дальше происходит вот это
ans += v / 2 * 2; и вот это if (... && v % 2 == 1) и я такой, эээ, что, как, зачем, почему?
Буду признателен, если кто-то сможет обьяснить. Спасибо!
ну там просто берут чётные количество от каждого символа.
И помимо этого ещё один добавляют, если было где-то нечётное количество
И помимо этого ещё один добавляют, если было где-то нечётное количество
P
То условие только дин раз отработает
AO
ну там просто берут чётные количество от каждого символа.
И помимо этого ещё один добавляют, если было где-то нечётное количество
И помимо этого ещё один добавляют, если было где-то нечётное количество
прости, что значит
чётные количество от каждого символа ?P
ну если есть 5 символов a, и 4 символов c, то мы возьмём 4 символа а, 4 символа с, и потом добавим один символ с в середине.
AO
ну если есть 5 символов a, и 4 символов c, то мы возьмём 4 символа а, 4 символа с, и потом добавим один символ с в середине.
т.е. мы берим всё четные. А если у нас есть нечетные, который равны какое-либо количество четных + 1, мы тоже их считаем?