День 1.
1. Забыл, как умножать.
Для целых чисел подойдет такой код:
int mult7(int x)
{
return (x << 3) - x;
}Мой любимый алгоритм, который возводит в степень всё, что угодно, если только понять, что в конкретной задаче есть возведение в степень.
Складывает любые объекты, для которых определена операция ‘+’. (числа, строки, списки)
int product(a, b)
{
int result = 0;
while(b)
{
if (b & 1) // b % 2 == 1
result += a;
b >>= 1;
result += result;
}
return result;
}Отмечу решение Максима (он прислал несколько):
return a / (1.0 / b); // Ловко. Никто ведь не запрещал делить.
2. Когда деревья были большими.
Компилятор borland C++ 3.1 располагает переменные в памяти подряд и вызов a[10] = 0 обнуляет i. Цикл начинается заново.
3. Угадайка.
Здесь надо было использовать двоичный поиск, который каждый раз сокращает область поиска вдвое. Тогда отдагать число можно за log(1000) < 10 вопросов.
День 2.
1. Карусель.
Решение на python:
if len(a) == len(b) and a in b*2:
print "YES"
else:
print "NOУдвоеная строка содержит все свои циклические перестановки. Достаточно сравнить длины и проверить вхождение первой строки в удвоенную вторую.
2. Дело об исчезающем прямоугольнике.
Поля в списке инициализации инициализируются в том порядке, в каком они перечислены в определении класса.
Поле _area идет раньше всех и будет обработана первой. Но _width и _height еще не инициализированы, поэтому площадь получается неверной.
3. Калькулятор.
Ясно, что в лоб посчитать не получится, поскольку 15^9783 не влезет ни в какую память.
Но можно заметить, что последняя цифра произведения зависит только от последней цифры исходного числа. Причем, эта последняя цифра повторяется.
Надо выяснить период и выписать цифры. Это можно сделать даже в уме.
Теперь составим табличку:
table int[10][4] = {{0, 0, 0 ,0}, {1 1 1 1}, {2 4 8 6}, {3 9 7 1}, {4, 6, 4, 6}, {5, 5, 5, 5}, {6, 6, 6, 6}, {7, 9, 3, 1}, {8, 4, 2, 6}, {9, 1, 9, 1}};
int result = (p == 0) ? 1 : result[e % 10][p % 4];Степенная функция определена для e > 0. Люди, которые знали, чему равно 0^0 давно покинули эту землю.
День 3.
1. Лифт.
Это решение не использует ветвления и требует только 1 машинную команду.
2. Горе от копирования.
Здесь возникает бесконечная рекурсия от того, что конструктор копирования явно вызывает operator =, а operator = неявно вызывает конструктор копирования, когда возвращает результат по значению.
Проблемы бы не возникло, если operator = возвращал бы ссылку.
Общая рекомендация: никогда не реализовывать конструктор копирования через operator =. Конструктор копирования должен работать сам по себе, а operator = иметь следущий канонический вид.
T& operator = (const T& other)
{
T tmp(other);
this->swap(tmp); // класс должен содержать метод swap, не генерирующий исключений.
return *this;
}3. Выскочка.
В задаче явно не указано, что массив нельзя менять. Те, кто предложил решение, не меняющее массив, получили дополнительные баллы.
Сперва решение, меняющее массив. Если бы не было ограничения на дополнительную память, то мы просто завели бы второй массив и отмечали в нем те числа, которые уже прошли.
Но у нас нет памяти. Значит будем отмечать на месте.
Числа имеют значения от 1 до N-1. Поэтому, если мы уже видели число, то будем менять его знак. Если встретилось отрицательное число, значит мы его уже видели:
int find_duplicate(int* array, size_t n)
{
for (size_t i = 0; i != n; ++i)
{
int marked = abs(array[i]);
if (array[i] < 0)
return marked;
else
array[marked] = -array[marked];
}
}Потом можно пройти массив еще раз и поменять все отрицательные значения обратно на положительные, создав иллюзию, что массив не менялся.
Правильное решение данной задачи – алгоритм поиска циклов Флойда (зайца и черепахи). Будем рассматривать число в ячейке, как индекс следующей ячейки.
Т.е. наш массив – это описание графа. В нашем графе точно есть цикл, это задано условием.
Ставим на старт зайца и черепаху. Заец бежит быстро, а черепаха медленно. Заяц быстро добегает до цикла и начинает бегать по кругу.
В момент, когда черепаха его догонит, нужно пристрелить зайца, чтобы не раздражал. После этого ставим на старт вторую черепашку и ждем,
пока она встретится с первой. Место встречи и есть дубликат.
int find_duplicate(int* array)
{
int start = 0;
int turtle = array[start];
int bunny = array[array[start]];
while (turtle != bunny)
{
turtle = array[turtle];
bunny = array[array[bunny]];
}
int turtle2 = start;
while (turtle2 != turtle)
{
turtle = array[turtle];
turtle2 = array[turtle2];
}
return turtle;
}
P.S. Продвинутый курс по С++ стартует уже в эту субботу: http://proglive.ru/courses/cpp2
Мы шли к этому очень долго. Мы шли к этому более года. Сегодня Центр Школа Программирования открывает новое направление – курсы программирования под мобильные устройства!
