Тексты задач городской олимпиады 9-11 классы

Задача 1. Магический квадрат

 

      Магическим квадратом называется квадрат, состоящий из NхN клеток, заполненный числами от 1 до N², каждое из которых встречается ровно один раз. При этом числа в квадрате должны обладать следующим свойством: сумма чисел, стоящих на любой горизонтали, вертикали или любой из двух главных диагоналей равна одному и тому же числу.

Требуется написать программу, которая проверяет для заданного квадрата, является ли он магическим.

Формат входных данных

Первая строка входного файла содержит число N (1 ? N ? 10²). Далее следует N строк, каждая из которых состоит из N чисел разделенных пробелами. Все числа в этих строках разные и находятся в диапазоне от 1 до N². Каждая из этих строк соответствует строке чисел квадрата, который надо проверить. Соседние числа в каждой строке разделяются ровно одним пробелом.

Формат выходных данных

В выходном файле должно быть число 1, если квадрат магический, и 0 в противном случае.

Пример входных и выходных файлов:

magic.in                             magic.out

1                                         1

1

________________________

2                                       0

1 2

4 3

________________________

3                                          1

8 1 6

3 5 7

4 9 2

Задача 2. Бег с препятствиями

      В компьютерной игре «Бег с препятствиями» нужно провести бегуна от старта до финиша, огибая препятствия. Площадку можно представить себе как сетку дорожек расположенных на квадрате [0,20]х[0,20] координатной плоскости, причем дорожки проходят только по линиям с целочисленными координатами начала и конца. Бегун может перемещаться только по этим дорожкам. Старт всегда расположен ниже финиша. Огибать препятствия он должен так: первое препятствие огибается всегда справа, второе – слева, третье – справа. Препятствий всегда три и они расположены так, что ордината первого больше ординаты старта, ордината второго больше ординаты первого, а ордината третьего больше ординаты второго и меньше ординаты финиша. Компьютерная игра устроена так, что хотя бы один путь у бегуна есть всегда.

Требуется написать программу, которая вычислит длину кратчайшего пути бегуна.

Формат входных данных

Входной файл в первой строке содержит два целых числа S_x и S_y (0 <= S_x, S_y <=20) – координаты старта для бегуна, а затем еще два целых числа F_x и F_y (0 <= F_x, F_y <=20) – координаты финиша для бегуна. А также выполняется S_y < F_y, как было сказано в условии задачи.

Далее идут три строки, описывающие все четыре препятствия парами вещественных координат x_i и y_i (0 < x_i, y_i <20), i?{1, 2, 3}.

Числа во всех строках разделены одинарными пробелами.

Формат выходных данных

Выходной файл содержит целое число, которое означает длину кратчайшего пути от старта до финиша.

Пример входных и выходных данных

runner.in                    runner.out

0 0 1 6                           13

1 1

1 3

1 5

_____________________________

1 0 1 6                                          6

0 1

2 3

0 5

Задача 3. Суперкомпьютер "Лобачевский"

      В вычислительном центре университета был установлен новый суперкомпьютер «Лобачевский». Этот суперкомпьютер состоит из N узлов, соединенных N линиями связи по топологии кольца, т.е. 1-й узел соединен со 2-м и N-м, 2-й узел с 1-м и 3-м, 3-й узел со 2-м и 4-м и т.д. Каналы связи тоже занумерованы: 1-й узел соединен со 2-м каналом №1, 2-й узел с 3-м каналом №2 и т.д. Петабайтное устройство хранения данных (попросту «винчестер») подключено только к 1-му узлу компьютера и, следовательно, любой узел отличный от 1-го может получить данные только с помощью передачи по каналам соединения, а 1-й узел получает данные мгновенно.

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

Рассылка данных организуется следующим образом: если нужно передать 2*K пакетов, то сначала передаются пакеты данных для узлов K+1 и N–K по каналам 1 и N соответственно. Через 2 сек они освобождают каналы связи, и тогда отправляются пакеты для K и N–K+1 узлов по каналам 1 и N соответственно, а по каналам 2 и N–1 передаются пакеты данных для узлов K+1 и N–K. Еще через 2 сек отправляются пакеты для K–1 и N–K+2 узлов по каналам 1 и N соответственно, по каналам 2 и N–1 передаются пакеты данных для узлов K и N–K+1, а по каналам 3 и N–2 передаются пакеты для узлов K+1 и N–K. Процесс продолжается до тех пор, пока данные не попадут в свои узлы. Затем данные обрабатываются и отправляются обратно: по 1 каналу отправляются данные из 2-го узла в 1-й, по 2-му каналу из 3-го узла во 2-й, … , по N–1 каналу из N–1 узла в N-й, по N каналу из N узла в 1-й. Во время всего этого процесса 1-й узел может выполнять вычисления самостоятельно.

Вам необходимо обработать S пакетов по 100 Мб, используя суперкомпьютер "Лобачевский".

Требуется написать программу, которая определяет балансировку нагрузки на вычислительные узлы, и определяет минимальное время, которое потребуется на вычисления. То есть, определяет оптимальным образом  какие из пакетов на каком узле вычислять и какие из пакетов пересылать по каналам связи, используя механизм рассылки данных описанный выше, тем самым определяет минимальное время выполнения вычислений.

Формат входных данных

Входной файл содержит два целых числа N (1<=N<=512)  и S (1<=S<=10 в степени 6)

Формат выходных данных

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

Пример входных и выходных данных

computer.in                     computer.out

5 4                                        4

5 6                                         5

Вы можете обсудить этот пост комментариях или в нашем чате, который находится в верхнем правом углу сайта. Если вы не знаете как общаться в чате, то скорее жмите СЮДА! Приятного Вам общения :)