Недавно алексей устроился на работу в крупную it-компанию. ему предложили поработать над
групповым проектом. до этого у него уже было много успешных проектов, но в этот раз всё шло
не по плану.
алексей долго пытался найти причину всех неудач. в итоге он пришел к выводу, что его группа
. он считает, что i-й человек в компании характеризуется числом ai
. тогда в его
понимании, группа , если для любого целого m > 1 и любой пары разных людей
(i, j) в группе верно, что остатки от деления чисел ai и aj на m различаются.
алексей обратился со своими соображениями к руководству. они были бы рады согласиться на
реформы, но для начала хотели бы оценить все риски. алексею убедить руководство, для
этого требуется найти минимальное количество групп, на которое можно разбить
всех работников компании.
формат входных данных
в первой строке задано одно целое число n (2 6 n 6 200 000) — количество работников в компании.
во второй строке заданы n целых чисел a1, a2, . . , an (1 6 ai 6 109
) — числа, характеризующие
работников.
формат выходных данных
выведите одно число — минимальное количество групп, на которое можно
разбить всех работников компании.
примеры
стандартный ввод стандартный вывод
4
1 2 3 1
3
5
6 1 2 5 3
3
6
1 1 2 2 1 1
4
замечание
в первом примере работников можно разбить на группы первый и третий работник не могут быть в одной группе
так как остатки от деления a1 и a3 на 2 . первый и четвёртый работник не могут быть
в одной группе так как остатки от деления a1 и a4 на 7 . третий и четвёртый работник
не могут быть в одной группе так как остатки от деления a3 и a4 на 2 . таким образом,
ответ на данный тест равен 3
примеры дискр:
- энергетические уровни атома,
- сигналы светофора
- символы, слова... и т.д. и т.п.
непрерывный (он же аналоговый) - принимает бесконечное количество значений функции, амлитуда и время которого меняются непрерывно.
примеры непрерывных:
- звуковая волна,
- диаграмма изменения влажности, напряжения, и других некоторых физических величин
для преобразования непрерывного сигнала в дискретные производят дискретизацию. Процесс дискретизации сопровождается потерей информации если частота дискретизации в 2 раза меньше максимальной частоты непрерывного сигнала по теореме Найквиста... В России эту теорему называют Котельникова.
1) program Array16;
var
i:integer; // счетчик в цикле
N:integer;
a: array [1..10] of integer;
begin
writeln('Введите N (N<10)');
readln(N); // ввод размера массива
for i:=1 to N do
begin
write('a[',i,']=');
readln(A[i]); // ручной ввод значений массива
end;
writeln('Результат');
for i:=1 to N do
begin
// вычисление и вывод элементов в указанном порядке
write(' ',a[(i div 2+1)*((i) mod 2)+ n*((i+1)mod 2)-((i div 2)-1)*((i+1) mod 2)]);
end;
end.
2) Var A:array[1..100] of integer;
i,n:byte;
Begin
write('Введите n<=100: ');readln(n);
For i:=1 to n do
Begin
A[i]:=random(31);
write(A[i]:3);
End;
writeln;
For i:=1 to n div 2 do
write(A[i]:3,A[n-i+1]:3);
if n mod 2 <>0 then write(A[n div 2+1]:3);
End.