Формат входных данных

Задача 1. Замечательные числа

ограничение по времени: 1 сек
входной файл input.txt
выходной файл output.txt

Условие задачи:
Назовем целое число N замечательным, если для него справедливо равенство (*)
N²=(N – 1)² + M², где М – целое число. Даны два целых числа А и В. Найти количество замечательных чисел из диапазона [A,B] включительно. Например, в диапазоне [1,10] таких чисел два, а именно числа 1 и 5.
Входные данные: во входном файле input.txt содержатся два целых числа А и В (1<=A<=B<=109), разделенных пробелом.
Выходные данные: в выходной файл output.txt записать количество замечательных чисел из заданного диапазона.
Пример:

input.txt	output.txt
1 10

 

Решение:
Эта задача на сокращение перебора. Если просто пробежать отрезок от А до В, то мы не успеем по времени. Значит надо сокращать перебор.
Упрощаем равенство (*), получим 2*N-1= M². В левой части этого равенства находится нечетное число, следовательно, М тоже нечетное и принадлежит отрезку от 1 до квадратного корня из числа 2*N-1. Так как максимальное значение N равно В, то правая граница отрезка, содержащего М равна квадратному корню из числа 2*1000000000-1. Увеличим ее и возьмем равную квадратному корню из числа 2*1000000000. А это число меньше 50000 и можно перебирать.

 

program zad1;

var m,a,b,n:integer;

kol:integer; input,output:text;

begin

Assign(input,'input.txt');

Reset(input);

Assign(output,'output.txt');

rewrite(output);

read(a,b);

kol:=0;

for m:=1 to trunc(sqrt(2000000000)) do {перебираем М}

if m mod 2 = 1 then {если М нечетное}

begin

n:=(m*m+1) div 2; {вычисляем N}

if (n>=a)and(n<=b) then inc(kol); {проверяем принадлежность N отрезку }

end;

writeln(kol);

close(input); close(output);

end.

 

Тесты к задаче: в архиве «Задача 1»

Задача 2. Острова

входной файл input.txt
выходной файл output.txt

Каждый элемент квадратной матрицы размеренности N x N равен нулю, либо единице. Найдите количество «островов», образованных единицами. Под «островом» понимается группа единиц (либо одна единица), со всех сторон окруженная нулями (или краями матрицы). Единицы относятся к одному «острову», если из одной из них можно перейти к другой «наступая» на единицы, расположенные в соседних клетках. Соседними являются клетки, граничащие по горизонтали или вертикали.

Входные данные

В первой строке файла input.txt записано натуральное число N не больше 100 - размер квадратной матрицы. В следующих N строках задаются элементы матрицы через пробел.

Выходные данные

В файл output.txt выведите единственное число - количество островов.

Пример

input.txt	output.txt
5 1 0 1 1 1 0 0 0 0 0 1 1 1 0 1 0 1 0 0 1 0 0 0 1 1

 

Решение задачи

Итак, это классическая задача на поиск в глубину графа. Понятно, что надо обходить матрицу и каким-то образом вычислять количество островов. Вариант решения такой: после того, как мы попадаем на остров, надо это зафиксировать увеличив переменную-результат на единицу. Чтобы второй раз не посчитать один и тот же остров, сразу после посещения необходимо его уничтожить, т.е. присвоить всем клеткам острова значение ноль.

Поскольку тест задачи не слишком мал, стоит написать процедуру уничтожения островов, назовем ее"count". Чтобы во время выполнения процедуру не "выскочить" за пределы массива, сделаем его не размером N x N, а размеров N+2 x N+2, это даст нам возможность окружить искомый массив размером N x N нулями.

const m = 102; var a:array [1..m, 1..m] of integer; i,j,n,res: integer; input,output: text; procedure count(i,j: integer); begin if a[i,j] <> 1 then exit; a[i,j]:= 0; count(i + 1, j); count(i - 1, j); count(i, j + 1); count(i, j - 1); end;begin res:= 0; assign(input,'input.txt'); reset(input); assign(output,'output.txt'); rewrite(output); read(input, n); {Заполняем массив нулями} for i:= 1 to n+2 do for j:=1 to n+2 do a[i,j]:=0; {Считываем матрицу из файла} for i:= 2 to n+1 do for j:=2 to n+1 do read(input,a[i,j]); {Обходим матрицу в поиске островов} for i:= 2 to n+1 do for j:= 2 to n+1 do if a[i,j] = 1 then begin inc(res); count(i,j); end; write(output,res); close(input); close(output); end.

Тесты к задаче: в архиве «Задача 2»

Задача 3 Клавиатура

Всем известно, что со временем клавиатура изнашивается, и клавиши на ней начинают залипать. Конечно, некоторое время такую клавиатуру еще можно использовать, но для нажатий клавиш приходиться использовать большую силу.

При изготовлении клавиатуры изначально для каждой клавиши задается количество нажатий, которое она должна выдерживать. Если знать эти величины для используемой клавиатуры, то для определенной последовательности нажатых клавиш можно определить, какие клавиши в процессе их использования сломаются, а какие – нет.

Требуется написать программу, определяющую, какие клавиши сломаются в процессе заданного варианта эксплуатации клавиатуры.

Формат входных данных

Первая строка входного файла содержит целое число n (1 ≤ n ≤ 100) – количество клавиш на клавиатуре. Вторая строка содержит n целых чисел – с1, с2, …, сn, где сi (1 ≤ сi ≤ 100000) – количество нажатий, выдерживаемых i-ой клавишей. Третья строка содержит целое число k (1 ≤ k ≤ 100000) – общее количество нажатий клавиш, и последняя строка содержит k целых чисел pj (1 ≤ pj ≤ n) – последовательность нажатых клавиш.