Страницы

Уроки 53, 54 Олимпиадные задачи с использованием двумерных массивов

Пример 1. Имеется N домов. Если в доме i расположить пожарную часть, то поездка по вызову в дом j займет время a[i,j]+a[j,i] (i не равно j). Найти номер дома, от которого поездка в самый удаленный дом займет минимальное время.
Пусть время задано массивом а, размер которого NxN, все элементы - натуральные числа, не превышающие 1000. Будем считать a[i,i]=0.


Формат ввода:
В первой строке вводится число n
В следующих строках находятся элементы массива А построчно

Формат вывода:
Число - номер селения


Входные данные
Результат
3
0 25 36
27 0 29
35 29 0
2

Указания: 
Определим для каждого дома i максимальное время поездки в дом j, для этого найдем максимальную из сумм a[i,j]+a[j,i] в каждой i-той строке и результат занесем в таблицу В на i-тое место. 
В массиве В найдем минимальный элемент и его номер.

program pr1;
type mas=array[1..200,1..20] of integer;
var i,j,n,min,max,nmin:integer;
a:mas;
b:array[1..20] of integer;
procedure vvod;
begin
assign(input,'input.txt');
reset(input);
readln(n);
for i:=1 to n do
for j:=1 to j do
read(a[i,j]);
close(input);
end;

procedure poiskmax; {ищем максимальную сумму в каждой строке}
begin
for i:=1 to n do
begin
max:=a[i,1]+a[1,i];
for j:=2 to n do
if a[i,j]+a[j,i]>max then max:=a[i,j]+a[j,i];
b[i]:=max; {заносим значение максимальной суммы строки в одномерный массив В}
end;
end;

procedure vyvod;
begin
min:=b[1]; nmin:=1;
for i:=2 to n do {ищем минимальный элемент в массиве В и его номер}
if min>b[i] then begin min:=b[i] ; nmin:=i end;
assign(output,'output.txt');
rewrite(output);
write(nmin);
close(output);
end;

begin
vvod;
poiskmax;
vyvod;
end.




Задания

Задание 1. В соревнованиях по плаванию принимают участие n спортсменов. Соревнования состоят из трёх заплывов. Составить программу, определяющую лучший результат в каждом заплыве.

а[i, j] — результат спортсмена в заплыве;
i - номер спортсмена;
j - номер заплыва.

Указание:
Лучший результат в заплыве, т. е. наименьший из а[i,j] будем помещать в одномерный массив В, соcтоящий из трех элементов.
За основу решения задачи возьмём процедуру нахождения наименьшего из n чисел (минимальное в столбце).

Формат ввода:

В первой строке вводится число n
В следующих строках находятся элементы массива А построчно - результаты каждого спортсмена в трех заплывах


Формат вывода:
Выводится три числа - лучшие результаты в каждом заплыве

       Тесты        Посмотреть решение         


Экспериментальный раздел


1. Измените программу таким образом, чтобы можно было определить лучший результат каждого спортсмена.

2. Дополните программу так, чтобы она определяла абсолютного победителя.




Задание 2. В совет школы, состоящий из N человек, выбирают представителей из M классов, от каждого класса выдвинуто по N представителей, по одному на каждую должность в совете школы. Число проголосовавших за каждого кандидата представлено в двумерном массиве. Составить программу, которая определяет из какого класса выбрано больше всего представителей. 

m - количество классов;
n — количество должностей в совете школы;
i — номер должности;
j — номер класса;
а[i,j] — количество голосов отданных за представителя;
nom — номер победившего на выборах класса;
b — массив из количества человек каждого класса, победивших на i-тую должность




Номер класса
1
2
m
Номер должности в совете школы
1
5
10
12
4
2
2
3
7
2
3
7
8
5
11




n
8
12
6
1

Указание:
Обнулим все элементы массива В.
Находим максимальный элемент  и его номер в каждой строке.  
Увеличиваем на 1 элемент с номером победившего класса в массиве В. 
Находим максимальный элемент в таблице В, номер этого элемента - класс, который является победителем.

Формат ввода:
В первой строке вводятся числа n и  m
В следующих строках находятся элементы массива А построчно

Формат вывода:
Единственное число - номер победившего класса

     Тесты       Посмотреть решение      


Задание 3. Об абитуриентах одной специальности известно: индивидуальный шифр и баллы, полученные ими на на ЦТ по трем предметам и средний балл аттестата (по 100 бальной системе). План приёма на специальность 8 человек. Требуется определить проходной балл, список рекомендованных к зачислению и отдельно список получивших полупроходной балл (если он есть). В списки включить индивидуальный шифр абитуриента и набранную сумму баллов.

k- количество абитуриентов;
f[k] — одномерный массив, индивидуальный шифр абитуриента;
b[k,4] — двумерный массив, баллы полученные абитуриентами;

prb — проходной балл;
pprb — полупроходной балл;
sb[k] — одномерный массив, сумма баллов, полученных абитуриентом.

Указание:
При решении задачи необходимо выполнить следующие этапы:
• ввод исходных баллов (инд. шифр и баллы);
• получение суммы баллов каждого абитуриента;
• сортировка всех данных об абитуриентах по убыванию их суммы баллов;
• вычисление проходного и полупроходного (если он есть) баллов;
• вывод требуемых списков.

После сортировки списков в порядке убывания суммы баллов возможны два варианте. Если sb[8]>sb[9], то проходной балл prb=sb[8], а полупроходного балла нет. Если же sb[8]=sb[9], то проходной балл prb=sb[8]+1, а полупроходной балл pprb=sb[8].



Формат ввода:
В первой строке вводится число k

Во второй строке массив f - шифр абитуриентов
В следующих строках находятся элементы массива В построчно

Формат вывода:
построчно шифр каждого абитуриента и его сумма баллов
проходной балл
построчно шифр и сумма баллов зачисленных абитуриентов
полупроходной балл
в строку шифр абитуриентов с полупроходным баллом

     Тесты       Посмотреть решение     



Задания для самостоятельного решения

1. В двумерном массиве натуральных случайных чисел от 0 до 199 найти количество всех двухзначных чисел, у которых сумма цифр кратна 5.

2. Отсортировать в матрице столбцы по убыванию значений элементов в первой строке.

3. Двумерный массив MxN заполнить случайными числами от 1 до 9. Вывести на экран сколько раз встречается каждое число.

4. Составьте программу замены местами второго и четвертого элементов второго столбца двумерного массива размером NхN.

5. Составьте программу удаления столбца, содержащего максимальный элемент двумерного массива.