Миша заблудился в лесу и пытается выйти. Он составил план маршрута выхода из леса. План состоит из N прямолинейных отрезков пути. Сначала Миша идёт a1 метров на север, потом a2 метров на восток, потом a3 метров на юг, затем a4 метров на запад, затем он опять начинает повторять направления в порядке север, восток, юг, запад, то есть a5 метров он проходит на север, a6 метров на восток и т.д. Оказалось, что для того, чтобы выйти из леса из его первоначальной точки, ему нужно было пройти ровно K метров в любом из четырёх направлений, то есть первоначально Миша находится в центре квадрата со стороной 2K метров.
Введём систему координат, в которой Миша первоначально находился в центре координат, ось OX направлена на восток, ось OY направлена на север, а единица измерения равна 1 метру. Определите, в какой точке Миша выйдет из леса (впервые окажется на границе леса), если будет следовать своему плану, или в какой точке его маршрут закончится, если он не выйдет из леса.
Входные данные Первая строка входных данных содержит целое положительное число K (1 ≤ K ≤ 109) — расстояние от начального расположения Миши до четырёх сторон квадрата (границ леса). Вторая строка содержит целое положительное число N (1 ≤ N ≤ 105) — количество отрезков в плане перемещений Миши. Следующие N строк содержат по одному числу a1, a2, ..., aN (1 ≤ ai ≤ 109) — длины отрезков в плане Миши в направлениях север, восток, юг, запад и т.д.
Выходные данные Программа должна вывести два целых числа x и y — координаты точки, в которой Миша выйдет из леса (то есть маршрут Миши впервые окажется на границе леса). Если же Миша не выйдет из леса, выведите координаты точки, в которой завершится его маршрут.
Система оценки Решения, правильно работающие, когда все входные числа не превосходят 100, будут оцениваться в
Пример Ввод
Вывод
Пояснение
3 6 2 1 3 3 5 4
-2 3
На рисунке изображён первый пример из условия. Расстояние от начального расположения Миши до стороны квадрата равно 3. Маршрут Миши состоит из 6 отрезков, их длины 2, 1, 3, 3, 5, 4. Первоначальное расположение Миши (точка (0, 0)) и место, где Миша выйдет из леса (точка (-2, 3)) отмечены синими кругами. Отметим, что Миша выйдет из леса на предпоследнем отрезке намеченного пути.
2 1 1
0 1
Во втором примере из условия путь Миши состоит из одного отрезка длины 1 на сервер, а до границы леса расстояние 2, поэтому Миша закончит путь в клетке
Var a: array[0..10] of integer; i, n, k: integer; // b: array[1..4, 1..4] of integer;
begin Println(); Println(1); for i := 0 to 10 do A[i] := i + 1; PrintLn(a); Println(); for i := 1 to 10 do begin A[i] := A[i - 1]; PrintLn(a); end;
Println(); Println(2); for i := 0 to 10 do A[i] := i + 1; PrintLn(a); Println(); for i := 10 downto 0 do begin A[i] := A[10 - i]; PrintLn(a); end; end.
Четырехзначное число в расширенной записи имеет вид Известно, что первая и последняя цифры одинаковы, отсюда d=a. Сумма цифр числа равна 16, т.е. 2a+b+c=16 (1) Если число делится на 2, то оно четное, следовательно "a" может равняться 2, 4, 6, 8. (2) Нулю оно равняться не может, поскольку тогда число станет трехзначным. Если четырехзначное число делится на 11, то модуль разности между суммами цифр, стоящих на четных и нечетных местах должна делиться на 11, т.е. |(a+c)-(a+b)|= |(c-b| делится на 11. Но разность двух однозначных чисел не может превышать 9, поэтому если она делится на 11, то она должна быть равна нулю. Но тогда с=b и число имеет вид 1000a+100b+10b+a. А уравнение (1) будет выглядеть как 2a+b+b=16; 2a+2b=16; b=8-a (3) C учетом (2) можно из (3) получить 4 решения: a=2, b=6 a=4, b=4 a=6, b=2 a=8, b=0 И это породит 4 возможных кода: 2662, 4444, 6226, 8008.
a: array[0..10] of integer;
i, n, k: integer;
// b: array[1..4, 1..4] of integer;
begin
Println();
Println(1);
for i := 0 to 10 do
A[i] := i + 1;
PrintLn(a);
Println();
for i := 1 to 10 do
begin
A[i] := A[i - 1];
PrintLn(a);
end;
Println();
Println(2);
for i := 0 to 10 do
A[i] := i + 1;
PrintLn(a);
Println();
for i := 10 downto 0 do
begin
A[i] := A[10 - i];
PrintLn(a);
end;
end.
Тут вывод трасировок последних циклов
1
[1,2,3,4,5,6,7,8,9,10,11]
[1,1,3,4,5,6,7,8,9,10,11]
[1,1,1,4,5,6,7,8,9,10,11]
[1,1,1,1,5,6,7,8,9,10,11]
[1,1,1,1,1,6,7,8,9,10,11]
[1,1,1,1,1,1,7,8,9,10,11]
[1,1,1,1,1,1,1,8,9,10,11]
[1,1,1,1,1,1,1,1,9,10,11]
[1,1,1,1,1,1,1,1,1,10,11]
[1,1,1,1,1,1,1,1,1,1,11]
[1,1,1,1,1,1,1,1,1,1,1]
2
[1,2,3,4,5,6,7,8,9,10,11]
[1,2,3,4,5,6,7,8,9,10,1]
[1,2,3,4,5,6,7,8,9,2,1]
[1,2,3,4,5,6,7,8,3,2,1]
[1,2,3,4,5,6,7,4,3,2,1]
[1,2,3,4,5,6,5,4,3,2,1]
[1,2,3,4,5,6,5,4,3,2,1]
[1,2,3,4,5,6,5,4,3,2,1]
[1,2,3,4,5,6,5,4,3,2,1]
[1,2,3,4,5,6,5,4,3,2,1]
[1,2,3,4,5,6,5,4,3,2,1]
[1,2,3,4,5,6,5,4,3,2,1]