Немного о "С4"

Программы и исходники задач

Задача 1 (скачать)

Дана последовательность N целых положительных чисел. Рассматриваются все пары элементов последовательности, сумма которых делится на m=60. Среди всех таких пар нужно найти и вывести пару с максимальным произведением элементов. Если одинаковое максимальное произведение имеют несколько пар, можно вывести любую из них. Если подходящих пар в последовательности нет, нужно вывести два нуля.

Описание входных и выходных данных

В первой строке входных данных задаётся количество чисел N (2<=N<=10 000). В каждой из последующих N строк записано одно натуральное число, не превышающее 10 000

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

8

10

30

50

40

60

70

90

80

Пример выходных данных для приведённого выше примера входных данных:

50 70

Пояснение. Из данных восьми чисел можно составить четыре пары, удовлетворяющие условию: (10 50) (30 90) (50 70) (40 80) Наибольшее произведение получается в паре (50 70)

Напишите эффективную по времени и по памяти программу для решения этой задачи.

Программа считается эффективной по времени, если при одновременном увеличении количества исходных чисел N и параметра m в k раз время работы программы увеличивается не более чем в k раз.

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

Будем хранить в массиве из m элементов максимальное число, имеющее соответствующий остаток от деления на m

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

Задача 2 (скачать)

Дана последовательность N целых положительных чисел. Рассматриваются все пары элементов последовательности, находящихся на расстоянии не меньше 6 (разница в индексах элементов должна быть 6 или более). Необходимо определить количество пар, разность чисел в которых кратна 3

Описание входных и выходных данных

В первой строке входных данных задаётся количество чисел N (6<=N<=1000). В каждой из последующих N строк записано одно натуральное число, не превышающее 1000

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

8

2

6

5

4

6

7

9

8

Пример выходных данных для приведённого выше примера входных данных:

1

Пояснение. Из данных восьми чисел можно составить три пары, удовлетворяющие условию: (1 7) (1 8) (2 8) Для заданного набора чисел получаем пары (2 9) (2 8) (6 8) Разности чисел в этих парах равны 7 6 2 Одна из этих разностей кратна 3. Напишите эффективную по времени и по памяти программу для решения этой задачи. Программа считается эффективной по времени, если при одновременном увеличении количества исходных чисел N и параметра m в k раз время работы программы увеличивается не более чем в k раз.Программа считается эффективной по памяти, если память, необходимая для хранения всех переменных программы, не превышает 4 Кбайт и не увеличивается с ростом N

Для вычисления всегда используется первый элемент массива, а новое число записывается в последний. Хотя этот алгоритм работает медленнее, чем алгоритм с циклическим массивом (для каждого элемента требуется пять дополнительных присваиваний при сдвигах), основное требование эффективности здесь выполнено: при увеличении размера массива в k раз количество действий растёт не более чем в k раз. Для хранения счётчиков по остаткам можно вместо массива из трёх элементов использовать три отдельные переменные. Это делает программу чуть более громоздкой, но не влияет на эффективность.

Задача 3 (скачать)

1. Гоночная трасса состоит из двух основных дорог и нескольких переездов, позволяющих перейти с одной дороги на другую.

На всех участках, включая переезды, движение разрешено только в одну сторону, поэтому переезд возможен только с дороги A на дорогу B. Гонщик стартует в точке A₀ и должен финишировать в точке B_N. Он знает, за какое время сможет пройти каждый участок пути по каждой дороге, то есть время прохождения участков A₀A₁, A₁A₂, ..., A_N-1A_N, B₀B₁, B₁B₂, ..., B_N-1B_N. Время прохождения всех переездов A₀B₀, A₁B₁, ..., A_NB_N одинаково и известно гонщику. Необходимо определить, за какое минимальное время гонщик сможет пройти трассу.Напишите эффективную, в том числе по используемой памяти, программу для решения этой задачи. Перед текстом программы кратко опишите алгоритм решения и укажите язык программирования и его версию.

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

В первой строке задаётся количество участков трассы N. Во второй строке задаётся целое число t – время (в секундах) прохождения каждого из переездов A₀B₀, A₁B₁, …, A_NB_N. В каждой из последующих N строк записано два целых числа a_i и b_i, задающих время (в секундах) прохождения очередного участка на каждой из дорог. В первой из этих строк указывается время прохождения участков A₀A₁ и B₀B₁, во второй – A₁A₂ и B₁B₂ и т. д.

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

3

20

320 150

200 440

300 210

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

Программа должна напечатать одно целое число: минимально возможное время прохождения трассы (в секундах).

Пример выходных данных для приведённого выше примера входных данных

750

Пусть X_i – минимально возможное время движения от A₀ до A_i,

а Y_i — минимально возможное время движения от A₀ до B_i. В точку A_i можно попасть только из точки A_i-1, поэтому X_i = X_i-1 + a_i. В точку B_i можно попасть двумя способами:

• из точки B_i-1

• из точки A_i.

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

Получается, что Y_i = min(Y_i-1 + b_i, X_i + t).

Кроме того, очевидно, что X₀ = 0, Y₀ = t.

Используя эти соотношения, можно найти значения X_i и Y_i для всех i от 1 до N, не сохраняя всех значений Значение Y_N будет окончательным ответом задачи.

Задача 4 (скачать)

Произведение ab кратно 7 и не кратно 49:

• a кратно 7, но не кратно 49;

• b не кратно 7(+ симметричный случай).

Максимальное произведение дают максимальные множители. Переменные

• Max7 – максимальное число, кратное 7, но не кратное 49;

• Max – максимальное число, не кратное 7.

X=Max7*Max

Задача 5 (скачать)

Дан список результатов сдачи экзамена учащимися школ некоторого района, с указанием фамилии и имени учащегося, номера школы и итогового балла. Напишите эффективную по времени работы и по используемой памяти программу (укажите используемую версию языка программирования, например, Borland Pascal 7.0), которая определяет номера школ, имеющих наибольший средний балл, показанный выпускниками данной школы на экзамене. На вход программе в первой сроке подается количество учащихся во всех школах района N. В каждой из последующих N строк находится информация в следующем формате:<Фамилия> <Имя> <Номер школы> <Балл>

где <Фамилия> – строка, состоящая не более, чем из 20 символов без пробелов,<Имя> – строка, состоящая не более, чем из 20 символов без пробелов,<Номер школы> – число от 1 до 99,<Балл> - число от 0 до 100.Порядок следования строк – произвольный.

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

6

Иванов Сергей 7 70

Сергеев Петр 3 65

Петров Кирилл 7 68

Кириллов Егор 3 75

Егоров Николай 7 71

Николаев Иван 19 70

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

Пример вывода для приведенного выше примера ввода:

3

19

При выполнении задания следует учитывать, что значение N может быть велико (до 10 000).

Создадим два массива с индексами от 1 до 99, соответствующих номерам школ будем хранить в этих массивах :

• количество выпускников из этой школы, сдававших экзамен

• суммарный балл выпускников этой школы.

Программа читает все входные данные один раз. После считывания фамилии, имени, номера школы и балла считанное значение прибавляется к суммарному баллу для данной школы, а количество выпускников из этой школы, сдававших экзамен, увеличиваем на 1. После окончания считывания данных проходим циклом от 1 до 99 по всем школам и определяем максимальный средний балл по всем школам. Затем во втором цикле выводим номера школ, средний балл в которых равен максимальному.

Задача 6 (скачать)

На плоскости дан набор точек с целочисленными координатами. Необходимо найти треугольник наибольшей площади с вершинами в этих точках, одна из сторон которого лежит на оси OX. Напишите эффективную, в том числе по памяти, программу, которая будет решать эту задачу. Размер памяти, которую использует Ваша программа, не должен зависеть от длины переданной последовательности чисел. Укажите используемый язык программирования и его версию. В первой строке вводится одно целое положительное число – количество точек N. Каждая из следующих N строк содержит два целых числа – сначала координата х, затем координата у очередной точки.Программа должна вывести одно число – максимальную площадь треугольника, удовлетворяющего условиям задачи. Если такого треугольника не существует, программа должна вывести ноль.

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

6

0 0

2 0

0 4

3 3

5 5

-6 -6

Пример выходных данных для приведенного выше примера входных данных:

6

Нам нужно определить площадь треугольника, одно из оснований которого лежит на оси ОХ. Пусть длина этого основания равна B, а высота треугольника равна H. Тогда площадь треугольника равна S = B×H/2. Из этих рассуждений следует, что треугольник с максимальной площадью образован двумя точками на оси ОХ, которые дальше всего стоят друг от друга, и точкой, которая наиболее удалена от оси ОХ, то есть имеет максимальную координату y (по модулю).

Таким образом, нужно найти:

• xMin – минимальное значение x-координаты среди всех точек, для которых y-координата равна нулю;

• xMax – максимальное значение x-координаты среди всех точек, для которых y-координата равна нулю;

• yMax – максимальный модуль y-координаты среди всех точек.

Тогда S = (xMax – xMin)×yMax/2. Единственная сложность состоит в том, чтобы записать в переменные xMax и xMin некоторые начальные значения, которые позволят определить, что еще ни одной точки на оси ОХ не найдено.Например, можно записать в них два нуля, но как тогда различить ситуации «ни одна точка на оси ОХ не найдена» и «найдена одна точка на оси ОХ с координатой x=0»?

@akaVeta