РЕШУ ЕГЭ — информатика

Задания

При проведении эксперимента заряженные частицы попадают на чувствительный экран, представляющий из себя матрицу размером 10 000 на 10 000 точек. При попадании каждой частицы на экран в протоколе фиксируются координаты попадания: номер ряда (целое число от 1 до 10 000) и номер позиции в ряду (целое число от 1 до 10 000).

Точка экрана, в которую попала хотя бы одна частица, считается светлой, точка, в которую ни одна частица не попала,  — тёмной.

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

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

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

Задание 26

Первая строка входного файла содержит целое число N  — общее количество частиц, попавших на экран. Каждая из следующих N строк содержит 2 целых числа: номер ряда и номер позиции в ряду.

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

Ответ:

Решение. Создадим массив из 10 000 строк, каждая из которых будет представлять из себя 10 000 идущих подряд нулей. Индекс массива будет являться номером ряда, а индекс позиции символа в строке будет являться номером позиции в ряду. Считаем данные из файла, присваивая в соответствующей строке соответствующему символу единицу вместо нуля. Далее с помощью строкового метода string.ToWords разобьём каждую строку в массиве с разделителем «0», таким образом получим все последовательности из светлых точек в каждом ряду. Далее последовательно пройдём по каждой найденной последовательности светлых точек и найдём последовательность с наибольшей длиной.

Приведём решение на языке 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;

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))])

№ п/п	№ задания	Ответ
1	46984	10 2786

Ключ