Вечеринка после блокировки
Это была пустяковая проблема. Все, что вы должны заметить, это то, что он должен добавить собранные монеты в свои сбережения до дня, предшествующего окончанию блокировки.
Самый простой подход заключался в том, чтобы умножить «а» на «k-1» раз и прибавить к его собственным сбережениям, чтобы получить результат.
e.g
10 3 5
у него есть 10 монет в качестве сбережений, и его папа даст ему 3 монеты на 4 дня, поэтому (10 + 3 * 4) = 22.
Общая временная сложность составляет O (1).
Решение:
https://github.com/himmanshuuu/Editorials_Contest/blob/master/After_Lockdown_Party.cpp
Решение побега рыцаря
Эта задача представляет собой простую математическую задачу. Вам дана шахматная доска из блоков MxN и координата начальной позиции коня. Простым наблюдением вы можете видеть, что максимальное смещение коня будет +2 в любом направлении, поэтому нам просто нужно проверить, в каком направлении потребуется минимальное количество ходов, чтобы сдвинуться. Общая сложность каждого запроса будет O(1).
https://github.com/priyanshu360/Editorials/blob/master/hackerrankescapeknight.cpp
{ Размер шахматной доски n*m и начальная позиция (a, b) }
{
int влево, вправо, вверх, вниз;
left = b;
вправо = m — b + 1;
вверх = a;
вниз = n — a + 1;
int dir = min(left, min(right, min(up , вниз)));
cout‹‹floor(dir/2);
Максимальный кекс
Эта проблема была простой проблемой реализации: вам дали число n и число k, поэтому у вас есть k ходов, чтобы максимизировать число n, и мы также должны проверить, что число должно делиться на 3 после изменений.
Чтобы сделать любое число максимум, мы можем начать слева, чтобы скрыть его цифры «9» до «9» для (k — 1) ходов, но после этой итерации мы сохранили наш 1 ход на последнем ходу, мы проверим сумму цифр, и теперь мы нужно повторить итерацию слева, проверяя, какой цифрой мы можем заменить текущую цифру, чтобы сумма стала делиться на 3 { (сумма — текущая цифра + новая цифра)% 3 == 0}, и мы заменим только текущую цифру новой цифрой если (новая цифра › текущая цифра) или если такого возможного хода нет, мы заменим крайнюю правую цифру числа.
Общая сложность будет O (длина (n)).
Решение:
https://github.com/priyanshu360/Editorials/blob/master/hackerrankcupcake.cpp
n = 9888, k = 2
Шаг 1:- замените 9'8'88 на 9 -> 9988
//Теперь остался только 1 k.
Шаг 2:- сумма = 34, не делится на 3
Шаг 3:- теперь, чтобы сделать n делящимся на три, у нас есть следующие ходы
9988 -> 8988 { невозможный ход как 9 › 8 }
9988 -› 9888 { невозможный ход как 9 › 8 }
9988 -› 9978 { невозможный ход как 8 › 7 }
9988 -› 9987 { невозможный ход как 8 › 7 }< br /> Шаг 4: - Итак, как я уже сказал выше, если нет возможного хода, мы сделаем ход самой правой цифрой. 9988–›9987
Тупой номер
Легкая задача теории чисел: число будет n-квадратным, только если n-полный квадрат. Доказательство:-
n² + n² + n² …. n терминов = n² * (1 + 1 + 1….. n терминов) = n * n²
КОРЕНЬ(n*n²) = КОРЕНЬ(n) * n
Если n является идеальным квадратом n, то SQRT(n*n²) должен быть идеальным квадратом, следовательно, мы можем сказать, что n является идеальным квадратом.
Таким образом, работа сводится к нахождению числа полных квадратов между заданными l и r. Для этого есть простая формула
floor(sqrt(b)) — ceil(sqrt(a)) + 1
https://www.geeksforgeeks.org/find-number-perfect-squares-two-given-numbers/
Общая сложность будет O (log (b)), так как функция sqrt работает за время log (n).
Друг в беде — настоящий друг
Вывод первый:
Сначала мы преобразуем каждую цифру исходного числа следующим образом:
0, 1 -> пустой
2 -> 2
3 -> 3
4 -> 322
5 -> 5
6 -> 53
7 -> 7
8 -> 7222
9 -> 7332
Затем отсортируйте все цифры в порядке убывания как новое число, тогда оно и будет ответом.
Доказательство:
Мы можем заметить, что наш ответ не будет содержать цифр 4,6,8,9, потому что мы всегда можем преобразовать цифры 4,6,8,9 в большее количество цифр, как в заключении, и это делает число больше.
Тогда как мы можем убедиться, что результат будет наибольшим после этого преобразования?
Мы можем доказать следующую лемму:
Для любого положительного целого числа x, если его можно записать в виде (2!) c 2 * (3!) c 3 * ( 5!) c 5 * (7!) c 7, будет только один уникальный путь.
Предположим, что существует два способа записать x в этой форме, мы можем предположить, что эти два способа: (2!) a 2 * (3!) a 3 * (5!) a 5 * (7!) a 7 и (2!) b 2 * (3!) b 3 * (5!) b 5 * (7!) b 7.
Мы находим наибольшее i такое, что a i ≠ b i. Затем мы известно, что существует по крайней мере одно простое число, делитель которого различен двумя способами.
Но согласно основной теореме арифметики существует только одна простая факторизация каждого целого числа. Таким образом, мы получаем противоречие.
После получения результата нам не нужно беспокоиться о том, что другие числа будут больше нашего.
Временная сложность: O(n).
Решение:
https://github.com/himmmanshuuu/Editorials_Contest/blob/master/A_Friend_in_need_is_friend_indeed.cpp
Python_solutions-https://github.com/himmanshuuu/Contest_solution-Python-
