10 января 2017

09 января 2017

Задачи районного тура 
Всероссийской олимпиады школьников 2016 г.


26 мая 2013

Задача 5.10 (а-г).

Крылов С.С., Ушаков Д.М. «ЕГЭ информатика. Тематические тестовые задания», с.99-100, «Экзамен», Москва, 2013.

Вариант (а):
Значения двумерного массива размера  n x n задаются с помощью вложенного оператора цикла в представленном фрагменте программы (вариант на языке Pascal):

for i := 1 to n do
for k := 1 to n do
if i > k then
      A[i,k] := 1
else
      A[i,k] := 0;

Как будет зависеть от  n сумма элементов массива A после выполнения алгоритма? Напишите формулу вычисления суммы элементов массива A, в зависимости от n.

Решение:
Пусть i – номер строки, k – номер столбца.
Вычислим для наглядности значения массива A размером 5 х 5:


i   \   k
1
2
3
4
5
1
0
0
0
0
0
2
1
0
0
0
0
3
1
1
0
0
0
4
1
1
1
0
0
5
1
1
1
1
0

Очевидно, что в этом частном случае сумма элементов массива A  будет   равна 1 + 2 + 3 + 4 = 10.

В общем случае сумма элементов массива A размером  n x n  вычисляется как сумма последовательных натуральных чисел от 1 до  n – 1 по формуле    n (n – 1) / 2.


Вариант (б):
Значения двумерного массива размера  n x n задаются с помощью вложенного оператора цикла в представленном фрагменте программы (вариант на языке Pascal):

for i := 1 to n do
for k := 1 to n do
if i = k then
      A[i,k] := 1
else
      A[i,k] := -1;

Как будет зависеть от  n сумма элементов массива A после выполнения алгоритма? Напишите формулу вычисления суммы элементов массива A, в зависимости от n.

Решение:
Пусть i – номер строки, k – номер столбца.
Вычислим для наглядности значения массива A размером 5 х 5:

i   \   k
1
2
3
4
5
1
1
-1
-1
-1
-1
2
-1
1
-1
-1
-1
3
-1
-1
1
-1
-1
4
-1
-1
-1
1
-1
5
-1
-1
-1
-1
1

Из этого примера видно, что сумма элементов массива A  по каждой строчке будет  равна   2 - n, а сумма всех элементов массива A находится как  n (2 – n).
Внимание!  В книге приведен неправильный ответ:   n n2.


Вариант (в):
Значения двумерного массива размера  n x n задаются с помощью вложенного оператора цикла в представленном фрагменте программы (вариант на языке Pascal):

for i := 1 to n do
for k := 1 to n do
if i > k then
      A[i,k] := 1
else
    A[i,k] := -1;

Как будет зависеть от  n сумма элементов массива A после выполнения алгоритма? Напишите формулу вычисления суммы элементов массива A, в зависимости от n.

Решение:
Пусть i – номер строки, k – номер столбца.
Вычислим для наглядности значения массива A размером 5 х 5:

i   \   k
1
2
3
4
5
1
-1
-1
-1
-1
-1
2
1
-1
-1
-1
-1
3
1
1
-1
-1
-1
4
1
1
1
-1
-1
5
1
1
1
1
-1


Сумма элементов массива размером  n x n  вычисляется как сумма диагональных элементов и будет равна    - n.


Вариант (г):
Значения двумерного массива размера  n x n задаются с помощью вложенного оператора цикла в представленном фрагменте программы (вариант на языке Pascal):

for i := 1 to n do
for k := 1 to n do
if i > k then
      A[i,k] := i
else
      A[i,k] := -k;

Как будет зависеть от  n сумма элементов массива A после выполнения алгоритма? Напишите формулу вычисления суммы элементов массива A, в зависимости от n.

Решение:
Пусть i – номер строки, k – номер столбца.
Вычислим для наглядности значения массива A размером 5 х 5:

i   \   k
1
2
3
4
5
1
-1
-2
-3
-4
-5
2
2
-2
-3
-4
-5
3
3
3
-3
-4
-5
4
4
4
4
-4
-5
5
5
5
5
5
-5

Из этого примера видно, что сумма элементов, расположенных выше и ниже диагонали таблицы, будет равна 0.
Таким образом, сумма элементов всего массива  A  равна взятой со знаком минус сумме  последовательных натуральных чисел от 1 до  n и  определяется формулой  - n (n + 1) / 2.


17 мая 2013

Вариант задачи C4


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

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

Перед  текстом программы кратко опишите алгоритм решения.

Для каждого скопления на вход программе в первой строке подается количество измеренных скоростей звезд N.
В каждой из последующих N строк приводится значение скорости, записанное в виде целого числа, по абсолютной величине не превышающего 3000.

Вариант решения:

Program C4-astro;
{Наибольшее произведение скоростей может быть получено как произведение двух положительных или двух отрицательных скоростей, поэтому программа ищет две максимальные и две минимальные скорости из набора данных, а затем выбирает
большее из этих произведений в качестве окончательного результата}

Var min1, min2, max1, max2,  N, i, v:  longint;
       N,i: integer;
{использование типа longint важно, так как произведение достаточно больших целых чисел может выходить за пределы типа integer}

Begin
ReadLn(N);
Max1 :=  -3001;      {задаем любое число, меньшее 3000}
Min1 :=  +3001;      {задаем любое число, большее 3000}
For i  :=  1  to  N  do
   Begin
   ReadLn(v);
   if v >= max1 then
      Begin
      Max2:=max1;
      Max1:=v
      End
   Else
      if v>max2 then  Max2:=v;
   if v <= min1 then
      Begin
      Min2:=min1:
      Min1:=v
      End
   Else
      if v < min2 then Min2:=v
  End;
if max1*max2 > min1*min2 then
   WriteLn(max1*max2)
Else
    WriteLn(min1*min2)
End.