При проведении эксперимента заряженные частицы попадают на чувствительный экран, представляющий из себя матрицу размером 10 000 на 10 000 точек. При попадании каждой частицы на экран в протоколе фиксируются координаты попадания: номер ряда (целое число
Точка экрана, в которую попала хотя бы одна частица, считается светлой, точка, в которую ни одна частица не попала, — тёмной.
При анализе результатов эксперимента рассматривают группы светлых точек, расположенных в одном ряду так, что между каждыми двумя соседними светлыми точками находится ровно одна тёмная.
Вам необходимо по заданному протоколу определить максимальную длину такой группы и номер ряда, в котором эта группа встречается. Если таких рядов несколько, укажите минимально возможный номер.
Входные данные.
Первая строка входного файла содержит целое число N — общее количество частиц, попавших на экран. Каждая из следующих
В ответе запишите два целых числа: сначала максимальную длину непрерывной группы светлых точек, затем — номер ряда, в котором эта группа встречается.
Ответ:
Создадим массив из 10 000 строк, каждая из которых будет представлять из себя
Приведём решение на языке Pascal.
var
i, j, n, x, y, maxlen, maxnum, count: integer;
screen: array[1..10000] of string;
f: text;
begin
assign(f,'C:\26.txt');
reset(f);
readln(f, n);
maxlen := 0;
for i := 1 to 10000 do screen[i] := '0' * 10000;
for i := 1 to n do begin
readln(f, x, y);
screen[x][y] := '1';
end;
for i := 1 to 10000 do begin
count := 0;
for j := 1 to 10000 do begin
if j mod 2 <> 0 then begin
if (screen[i][j] = '1') and (screen[i][j + 1] = '0') then count := count + 1
else begin
if count > maxlen then begin
maxlen := count;
maxnum := i;
end;
count := 0;
end;
end;
end;
end;
writeln(maxlen, ' ', maxnum);
end.
В результате работы данного алгоритма при вводе данных из файла в условии получаем ответ — 9 995.
Ответ: 9 995.
Примечание. Путь к файлу необходимо указать согласно расположению файла на Вашем компьютере.
Приведём другое решение на языке Python.
f = open('26 (17).txt')
n = int(f.readline())
maxlen = 0
screen = [['0'] * 10001 for i in range(10001)]
for i in f:
x, y = i.split()
screen[int(x)][int(y)] = '1'
for i in range(1, 10001):
count = 0
for j in range(1, 10001):
if j % 2 != 0:
if (screen[i][j] == '1') and (screen[i][j + 1] == '0'):
count = count + 1
else:
if count > maxlen:
maxlen = count
maxnum = i
count = 0
print(maxlen, maxnum)