Приветствую, сообщество codeforces!
Недавно проходил интервью в одну локальную компанию, где мне дали задание на codility, и я был немного удивлен списком задач, которые я получил. Мне показались они сложными. Я смог решить только 1 из 3, на остальные 2 написал решения для маленьких ограничений, чтобы было хотя бы что-то.
Теперь хотел бы попросить у Вас помощи, идеи или подходы как решить эти задачи.
Задача1
1) Дано бесконечное поле на которой стоит конь (0, 0). Надо дойти до (A, B) -10^8 <= A, B <= 10^8, если невозможно возвратить -1, если количество шагов больше чем 10^8, возвратить -2
Задача2
2) Дана система счисления с основанием -2. Примеры: 011 — это будет 0 * (-2)^0 + 1 * (-2)^1 + 1 * (-2) ^ 2 = 2 0011 — это будет 0 * (-2) ^ 0 + 0 * (-2) ^ 1 + 1 * (-2) ^ 2 + 1 * (-2) ^ 3 = -4
Дан массив состоящий из 0 и 1 размером 1 < size < 10 ^ 5. Нужно возвратить массив состоящий из 0 и 1, только обозначющей отрицательное значение, полученное из изначального массива.
Примеры 11011 = 7, нужно возвратить 1001 = -7 1111 = -5, нужно возвратить 101 = 5
Здесь я сгенерировал все возвможные маски, чтобы увидеть какую-нибудь закономерность, но, к сожалению, ничего стоящего не придумал.
Заранее спасибо за вашу помощь!
UPD: длина, получившегося во второй задаче массива, должна быть минимальной
Задача 2:
если
(-2) ^ i = xто(-2) ^ i + (-2) ^ (i+1) = -x.Учитывая это можно найти все подотрезки состоящие из единиц, для каждого подотрезка приравнять к нулю единицы стоящие на четных позициях, и если длина подотрезка нечетное, то приравнять к единице элемент находящийся после последнего элемента.
Доказательство: к
(-2)^i + (-2)^(i+1) ... + (-2)^nотрицательным будет- (-2)^i - (-2)^(i+1) ... - (-2)^n, то есть(-2)^i + (-2)^(i+1) + (-2)^(i+1) + (-2)^(i+2) ... + (-2)^n + (-2)^(n+1)(так как- (-2) ^ i = (-2) ^ i + (-2) ^ (i+1)). Сократим все(-2)^i + (-2)^i + (-2)^(i+1)на0. В итоге остается то, что я описал выше.Спасибо за ответ, интересно получается. Я забыл добавить в условие, что длина полученного массива должна быть минимальной. Сорри, что сразу не написал
Нули с конца удалить можно.
100101000=100101Не думал, что в каких-либо компаниях в самом деле дают логические задачи на собеседованиях. Давно ведь известно, что они не отображают умений и навыков программирования.
Разве не наоборот?
В смысле?
Задача 1: идешь жадно в направлении нужной точки. Когда будешь находиться достаточно близко к финишу, скажем, abs(x — xf) < 10 && abs(y — yf) < 10, запускаешь бфс на поле 50х50 с центром в той клетке, где сейчас стоишь.
А не будет такого, что ответ будет разный в зависимости от того с какой точки бфс пустишь? ведь можно дойти до разных точек. мне тоже пришла в голову такая мысль, но почему-то засомневался в этом решении
Задача 1 для n, m положительных(для остальных почти тоже самое):
d[i][j] минимальное количество ходов чтобы добраться до {i, j}Вначале заполним массив d от {0, 0} до {10, 10} (bfs-ом к примеру)
Дальше допустим что
d[i][j] = min(d[i-1][j-2], d[i-2][j-1]) + 1;(тоестьmin(d[i-1][j-2], d[i-2][j-1])=min(d[i+-1][j+-2], d[i+-2][j+-1]))Учитывая это можно дойти до какой то клетки(горизонтально или вертикально) и идти от нее по диагонали вниз.
Если нам пришлось идти горизонтально то
d[0][j] = d[1][j-2] + 1иd[1][j] = d[0][j-2] + 1Для вертикального
d[i][0] = d[i-2][1] + 1иd[i][1] = d[i-2][0] + 1(я не смог доказать :), следовательно может быть неправильно )