Олимпиадные задачи по программированию.

Элементами массива a[1..n] являются неубывающие массивы [1..m] целых чисел (a: array [1..n] of array [1..m] of integer; a[1][1] <= ... <= a[1][m], ..., a[n][1] <= ... <= a[n][m]). Известно, что существует число, входящее во все массивы a[i] (существует такое х, что для всякого i из [1..n] найдётся j из [1..m], для которого a[i][j]=x). Найти одно из таких чисел х.

[Решение]

Задан массив чисел А[1:N,1:M],упорядоченный по возрастанию по строкам и столбцам, т.е.:

А[I,1]<А[I,2]<...<А[I,M] (при всех I), А[1,J]<A[2,J]<...<А[N,J] (при всех J).

Найти элемент массива, равный заданному числу Х и отпечатать его индексы (I,J). Напечатать слово "НЕТ", если такого элемента не окажется. Х можно сравнить не более, чем с M+N элементами массива.

[Решение]

Написать подпрограмму, которая в двумерном массиве А(N,M) целых чисел, таком, что для всех I от 1 до N , J от 1 до М-1 выполняется А(I,J)>A(I,J+1) и для всех I от 1 до N-1 выполняется A(I,M)>A(I+1,M), находит все элементы A(I,J), равные J+I, или устанавливает, что таких элементов нет.

Написать подпрограмму, которая в двумерном массиве А(N,M) целых чисел, таком, что для всех I от 1 до N , J от 1 до М-1 выполняется А(I,J)<A(I,J+1) и для всех I от 1 до N-1 выполняется A(I,M)<A(I+1,M), находит все элементы A(I,J), равные J+I , или устанавливает, что таких элементов нет.

Задана прямоугольная таблица А[1:N,1:N], элементы которой равны 0 или 1 причем А[i,i]=0 для любого i.

Необходимо найти, если они есть, такие строку i₀ и столбец j₀, чтобы в столбце j₀ были все 0, а в строке i₀ - все 1 (кроме элемента A[i₀,i₀], равного 0).

[Решение]

На плоскости задается выпуклый N-угольник целочисленными кооpдинатами своих веpшин в порядке обхода по контуpу. Вводятся кооpдинаты точки (X,Y). Опpеделить:

a) является ли она веpшиной N-угольника;

б) пpинадлежит ли она N-угольнику.

[Решение]

На двух паpаллельных пpямых слева напpаво заданы по N точек на каждой.

Их кооpдинаты задаются в массивах A[1..N] и B[1..N]. Расстояние между пpямыми единичное. Вводится точка (X,Y), где 0<Y<1. Опpеделить, в какой из получившихся N-1 конечных и 2 бесконечных тpапециях лежит точка.

[Решение]

На пpямой своими концами заданы N отpезков и точка X. Опpеделить, пpинадлежит ли точка межотpезочному интеpвалу. Если да, то указать концевые точки этого интервала. Если нет, то найти,

а. Какому количеству отpезков пpинадлежит точка.

б. Каким именно отрезкам принадлежит точка.

[Решение]

На пpямой своими концами заданы N отpезков. Найти точку, принадлежащую максимальному числу отрезков

[Решение]

Вводится последовательность из n натуральных чисел. Необходимо определить наименьшее натуральное число, отсутствующее в последовательности.

[Решение]

На длинной перфоленте записаны N попарно различных положительных целых чисел. Ваша ЭВМ может перематывать ленту на начало и считывать числа одно за другим. Внутренняя память машины может хранить только несколько целых чисел. Требуется найти наименьшее положительное целое число, которого нет на ленте. Опишите алгоритм, который сделает это за небольшое количество перемоток ленты.

[Решение]

На столе в двух столбиках лежат 64 золотых и 64 серебряных монеты соответственно. Как серебряные, так и золотые монеты упорядочены в порядке убывания масс. Массы всех монет разные. Какое наименьшее количество взвешиваний необходимо для определения 64-ой монеты в порядке убывания масс среди всех 128 монет? За один раз можно взвешивать две монеты и определить, которая из них тяжелее. Ответ обосновать.

[Решение]

Задано N наборов монет из различных стран. Наборы упорядочены по невозpастанию массы монет. В i-ом наборе a_i монет. Необходимо за минимальное число взвешиваний на чашечных весах определить к-тую по массе монету среди всех монет.

[Решение]

Заданы массивы A[1..n] и B[1..n]. Необходимо найти такие индексы i₀ и j₀, , что

a_i0 + b_j0 = max (a_i + b_j ),

где 1<=i<=n, 1<=j<=m , i<j.

[Решение]

Мажорирующим элементом в массиве A[1..N] будем называть элемент, встречающийся в массиве более N/2 раз. Легко заметить, что в массиве может быть не более одного мажорирующего элемента. Например, массив

3, 3, 4, 2, 4, 4, 2, 4, 4

имеет мажорирующий элемент 4, тогда как в массиве

3, 3, 4, 2, 4, 4, 2, 4

мажорирующего элемента нет.

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

[Решение]

Вверх по странице, к оглавлению и навигации.