При проведении эксперимента заряженные частицы попадают на чувствительный экран, представляющий из себя матрицу размером 10 000 на 10 000 точек. При попадании каждой частицы на экран в протоколе фиксируются координаты попадания: номер ряда (целое число
Точка экрана, в которую попала хотя бы одна частица, считается светлой, точка, в которую ни одна частица не попала, — тёмной.
При анализе результатов эксперимента рассматривают группы светлых точек, расположенных в одном ряду подряд, то есть без тёмных точек между ними.
Вам необходимо по заданному протоколу определить максимальную длину такой группы и номер ряда, в котором эта группа встречается. Если таких рядов несколько, укажите минимально возможный номер.
Входные данные.
Первая строка входного файла содержит целое число N — общее количество частиц, попавших на экран. Каждая из следующих
В ответе запишите два целых числа: сначала максимальную длину непрерывной группы светлых точек, затем — номер ряда, в котором эта группа встречается.
Ответ:
Создадим массив из 10 000 строк, каждая из которых будет представлять из себя
Приведём решение на языке Pascal.
var
i, j, n, x, y, maxlen, maxnum: integer;
screen: array[1..10000] of string;
screen_str: array 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
screen_str := screen[i].ToWords('0');
for j := 1 to screen_str.Length - 1 do
if screen_str[j].Length > maxlen then begin
maxlen := screen_str[j].Length;
maxnum := i;
end;
end;
writeln(maxlen, ' ', maxnum);
end.
В результате работы данного алгоритма при вводе данных из файла в условии получаем ответ — 10 2786.
Ответ: 10 2786.
Примечание. Путь к файлу необходимо указать согласно расположению файла на Вашем компьютере.
Приведём другое решение на языке Python.
f = open('26 (11).txt')
n = int(f.readline())
a = [[0] * 10001 for j in range(10001)]
for i in range(n):
x, y = map(int, f.readline().split())
a[x][y] = 1
maxi = 0
mini = 0
for i in range(10001):
count = 0
m = 0
for j in range(10001):
if a[i][j] == 1:
count += 1
m = max(count, m)
else:
count = 0
if m > maxi:
maxi = max(maxi, m)
mini = i
print(maxi, mini)
Приведём решение Юрия Красильникова на языке Python.
a=[tuple(map(int,s.split())) for s in open('26.txt')][1:]
a=sorted(set(a)) # избавляемся от повторных попаданий и сортируем
r=[]
l=1
for i in range(1,len(a)):
if a[i][0]==a[i-1][0] and a[i][1]-a[i-1][1]==1:
l+=1 # считаем длину группы
else:
r.append( (l,a[i-1][0]) ) # длина группы и ряд, в котором она находится
l=1
r.append( (l,a[-1][0]) ) # последняя группа
la=[x[0] for x in r] # список с длинами групп
print(*r[la.index(max(la))])