Задача 4. Трапеза для героев Имя входного файла: стандартный ввод
Имя выходного файла: стандартный вывод
Ограничение по времени: 1 секунда
Ограничение по памяти: 512 мегабайт
После очередной победы над пришельцами K героев одного известного фильма собрались вместе
в кафе. Среди героев есть правши и левши. Они хотят сесть за длинным прямоугольным столом с
одной стороны этого стола так им лучше наблюдать за происходящим в кафе. Места за столом
последовательно пронумерованы, всего за столом N мест. Герои могут садиться не рядом друг с
другом. За столом могут остаться свободные (незанятые) места. Если на соседних (расположенных
последовательно друг за другом) местах по правую руку от правши оказывается левша именно в
таком порядке, то им будет неудобно есть. Грут обеспокоен такой ситуаций и хочет узнать много
ли пар героев сидят неудобно.
Форматвходныхданных
В первой строке записано целое число N (1 6N 6106) количество мест за столом.
Во второй строке записано целое число K (1 6K 63 ·105) количество героев.
Далее следуют K строк, к каждой из которых содержится информация о соответствующем герое:
номер места, и 0 если герой - правша, или 1 если герой - левша.
Гарантируется, что номера мест всех героев попарно различны.
Форматвыходныхданных
Выведите одно целое число количество пар героев, которым неудобно сидеть за столом.
Системаоценки
за каждую подзадачу начисляются только в случае, если все тесты для этой подзадачи
и необходимых подзадач успешно пройдены.
Ограничения
Подзадача K Дополнительные
ограничения
Необходимые
подзадачи
Информация о
проверке
0 0 Тесты из условия полная
1 20 1 6K 65 000 полная
2 20 1 6K 63 ·105 Количество левшей
не превосходит 100 первая ошибка
3 60 1 6K 63 ·105 1, 2 первая ошибка
lim = 11;
type
V = array[1..lim] of integer;
function FirstNegative(a: V; n: integer): integer;
var
i: integer;
begin
i := 0;
Result := 0;
repeat
i := i + 1;
if a[i] < 0 then Result := i
until (Result > 0) or (i > lim)
end;
procedure InpMass(var a: V; var n: integer; mName: string);
// Организует ввод массива
var
i, p: integer;
begin
writeln('Вводите элементы массива ' + mName + '; 7777 - конец ввода');
i := 0;
repeat
read(p);
i := i + 1;
if p <> 7777 then a[i] := p;
until (p = 7777) or (i > lim);
n := i - 1
end;
var
a, b: V;
m, n, p, q: integer;
begin
InpMass(a, m, 'A');
InpMass(b, n, 'B');
p := FirstNegative(a, m);
q := FirstNegative(b, n);
if p <= q then writeln('Номер первого отрицательного элемента в массива А: ', p)
else writeln('Номер первого отрицательного элемента в массива B: ', q)
end.
Тестовое решение:
Вводите элементы массива A; 7777 - конец ввода
37 14 -25 32 30 -29 38 27 7777
Вводите элементы массива B; 7777 - конец ввода
33 -36 23 -17 -3 -16 -33 33 -48 -39 30 7777
Номер первого отрицательного элемента в массива B: 2
// Внимание! Если программа не работает, обновите версию!
begin
Writeln('*** Исходный массив ***');
var a:=MatrRandom(5,5,-50,50);
a.Println(4); Writeln(4*a.ColCount*'-');
Writeln('*** Транспонированный массив ***');
a:=Transpose(a); a.Println(4)
end.
Пример
*** Исходный массив ***
40 -31 16 -27 -3
34 -37 0 -33 -8
-16 -44 -38 19 -22
-32 36 -22 42 -17
-31 20 36 8 9
*** Транспонированный массив ***
40 34 -16 -32 -31
-31 -37 -44 36 20
16 0 -38 -22 36
-27 -33 19 42 8
-3 -8 -22 -17 9