2008 № 4 Информатика

for i : '■ to n do

read(x[i]); for i := 0 to n - 1 do begin

1 := ( (x[i + 1) - x[i) ) -u • v - (xU ! ■

x[i + 1]))/2;

if 1 > maxl then maxl :- 1 end;

write(maxl:0:4) end. Задача "Последовательность"

Дана последовательность, состоящая на 2N нату­ральных чисел. Известно, что все числа этой после­довательности можно разбить на пары таким обра­зом, что сумма чисел во всех парах будет одинако­вой. Например, числа последовательности 99, 23, 77, 1 можно разбить на пары 1 + 99 = 77 + 23.

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

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

Первая строка содержит натуральное число М — количество тестов в файле. Первая строка каждого теста содержит число 2N — количество чисел в последовательности. В каждой из последующих 2N строчек содержится целое число от 1 до 10" — эле­менты последовательности (1 < N < 50 000).

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

Ответом на тест является символ 1, если входную последовательность можно разбить на пары, произ­ведения в которых были бы одинаковыми, и 0 в противном случае. Ответ на каждый тест следует выводить в отдельной строке.

Пример

Входные данные	Выходные данные
2	0
4	1
99
23
77
1
2
1
10101

Решение

Нам необходимо научиться решать задачу для одного теста, а затем просто запустить это решение для всех М тестов.

Обозначим сумму чисел за X. Допустим, у нас есть две разных пары чисел (У, X — У) и (Z, X — Z). Произве­дения этих чисел также должны быть равны, т.е.

Перенесем Л" п левую часть:

X х (V - Z) - (Y^J - Z") - (У + Z)x (У - Z). По поставленному нами условию Y*Z. а зна­чит, мы можем разделить обе части на (Y-Z), пос­ле чего получим равенство Л ~ Z + У , т.е. У и Z об­разуют пару, что противоречит поставленному ус­ловию (пары должны быть различны).

Таким образом, мы от противного доказали, что не существует двух таких различных пар. Значит, пара должна быть всего одна. По поставленному условию нам известно, что все числа можно разбить на пары с равной суммой, а значит, нам достаточно проверить, что в тесте встречается не более двух различных чисел. Будем делать это следующим образом: заведем массив из двух элементов, в котором будем хранить встретившиеся числа. Если очередное число уже есть в массиве, то не будем предпринимать никаких дей­ствий, иначе добавим его в массив. Если количество элементов в какой-то момент стало больше двух, то следует запомнить, что ответ должен быть 0 и счи­тать оставшиеся числа массива, следя, чтобы нигде не произошло выходов за пределы .массива.

Один из вариантов такой реализации приведен ниже: var

х : array[1..2] of longint; nownum, m, n, i, j, k, с : longint; flag, bad : boolean; begin

read(m);

for k := 1 to m do begin // идем по всем тестам read(n);

nownum := 0; // пока нет встретившихся чисел bad := false;

// ничего плохого не случилось for i := 1 to n do begin read(c); flag := false; // не нашли среди имеющихся

for j := 1 to nownum do // идем по имеющимся

if x[j] = с then

flag :■= true; // нашли if not flag then begin //не нашли

inc(nownum); // увеличиваем количество встретившихся различных

if nownum > 2 then begin // больше двух

dec (nownum); // чтобы не выйти за пределы - уменьшим

bad := true

// случилось плохое - переполнились end

х[nownum] := с; // запомним, что за число встретили

end end;

if bad then writeln(O) // выводим ответ

else writeln(1) end end.

38

200В N« I Ш1<1Н)РМЛШК\

•jf

-ли ivixu гдков, 4iv iwe civ населенно, cikvoulv лито. »u kukivm "тур--"' н.кп'чит

ciuevb нл велосипеде, составляет 0.1,5 тысячи, то п j\ic-смат^ваемьт момент, т.е. на S-м "t\]V '. лапши да^ж-iu иссякнлтк Все окол»лпсь втянутыми в нее. Но оОла-д;»ет велоснпед;1Л1П 1\\\ько пят-ая ч;1сть, у ост.иьных же

■имеются iu руках ou.\eTi,i, которые некому сбытк

Задание для самостоятельной работы

1 Кчюлклуя электронную таблицу Microsoft Excel или p;U]Xil4»T.iB компьютерную программу, опреде-

п области, п которой число лкчмпч-леп пс.мкипс von" сост.пинет 1.5 ми«. чслопск. и п лкударстве. ..._...... ..^.„..„ruv^nia- колпчсспю p:,nuo .V) мл..

Литература

1. Пср-льмм ЯМ. Злннметслы...». м.мем.пнк.₁. М, Им^тельство Русаном, 1^е' '"'■

к заданиям,

опубликованным в газете "В мир информатики" № 96 ('Информатика" №20/2007)

1. Статья "Гармонические числа"

Если бы нужно оыло Bbi4itc,v>m. он:А\\1*ныс значе­ния гармонических чисел, то для этого можно было применить .«обую и.< двух функций, приведенных п статье. Но поскольку в условии требовалось получить ряд пос\еловате.\ьных глр.«оническ1с< чнсе.\. целесооб­разно для расчета очередного значения использовать

ганее вычисленное (имея в виду, что Н ^ Н _, + —):

" ' п адг ~=.рмс нач пед i

JJCJHUC -.

Здесь также целесообразно для расчета очередно­го значения использовать ранее вычисленные значе­ния. Каких именно величин — видно из следующей программы:

адг . 5смонические_ч;:с-~5 нач пел числ, знам, i

ч.'-гг. := 1 [Числитель дроби знам := 1 |Знаменатель !Выводим первую строку значений вывод не. I, числ, "/", энам нп для i qt 2 до 10

I Вычисляем числитель и знаменатель ;очередной простой дроби числ := числ * i + знам знам := знам » i

Выводим новые значения вывод нс. i, числ, "/", знам '■ S3 кон

В особенностях расчета "новых значений вел. чин Ч1«:\ и .шли разберитесь самостоятельно. И ей;. В приведенной программе есть существенный нел. CTaixiK. Какой'-

Програмл\ы npuc.va.Mi:

— Баженов Василий и Баженов Muxaiu. средняя школа села Горелом Тамбовской обл.. учитель Ши­това Л.А.;

— Ветлугин Денис, средняя школа села Татар­ское. Дальне-Константнновский р-н Нижегородской обл.. учитель Салова Т.В.;

— Деминцев Борис, средняя школа села Сердар, Республика Марий Эл. учитель Чернова Л.И.;

— Максимова Наталья, село Ни коло-Берёзовка, Республика Башкортостан. Краснокамский р-н, школа № 1. учитель Ситдикова А.Г.;

— Яценко Иван, средняя школа села Кубайка, Красноярский край, учитель Чудов Н.А.