Алгоритмы обработки


Плюсануть
Поделиться
Класснуть
Запинить


Условие задачи Прогресс
ID 38716. Радость Громозеки
Темы: Массивы    Алгоритмы обработки    "Два указателя"   

Громозека имеет последовательность целых чисел A длины N. Он сделает три среза в последовательности A и разделит ее на четыре (непустые) смежные подпоследовательности B, C, D и E. Положения срезов он выбирает произвольно. Пусть P, Q, R, S - суммы элементов в B, C, D,  E соответственно. Громозека будет счастлив, когда абсолютная разница между максимумом и минимумом между P, Q, R, S будет минимальной. Найдите минимально возможную абсолютную разницу между максимумом и минимумом между P, Q, R, S.

Входные данные
В первой строке записано целое число N  (1 <= N <= 2·105). Во второй строке записано N целых чисел Ai (1 <= Ai <= 109).

Выходные данные
Выведите на экран минимально возможную абсолютную разницу между максимумом и минимумом между P, Q, R, S.
 

Примеры
№ Входные данные Выходные данные Пояснения
1 5
3 2 4 1 2		 2 Если разделить A на B, C, D, E = (3), (2), (4), (1,2), то P = 3, Q = 2, R = 4, S = 1 + 2 = 3.
Здесь максимум и минимум среди P, Q, R, S равны 4 и 2, с абсолютной разницей 2.
Мы не можем сделать абсолютную разницу между максимумом и минимумом меньше 2, поэтому ответ - 2.
2 10
10 71 84 33 6 47 23 25 52 64		 36  
3 7
1 2 3 1000000000 4 5 6		 999999994  

ID 39382. Ты решишь это?
Темы: Одномерные массивы    Алгоритмы обработки   

Есть N частей некоторого исходного кода. Характеристики i-й части кода представлены M целыми числами Ai1, Ai2, ..., AiM . Вам даны целые числа B1, B2, ..., BM и C.
i-я часть кода правильно решает задачу тогда и только тогда, когда \( A_{i1}\cdot B_1 + A_{i2}\cdot B_2 + ...+ A_{iM}\cdot B_M +C>0\).
Среди N частей исходного кода найдите количество, которые правильно решают эту задачу.

Входные данные
В первой строке заданы три числа через пробел: N, M (1 <= N, M <= 20) и C (-100 <= C <= 100). Во второй строке задано  M чисел Bi (-100 <= Bi <= 100). Каждая из следующих N строк содержит M чисел Ai (-100 <= Aij <= 100, 1 <= i <= N, 1 <= j <= M).

Выходные данные
Выведите одно число - ответ на задачу.
 

Примеры
№ Входные данные Выходные данные
1 2 3 -10
1 2 3
3 2 1
1 2 2		 1
2 5 2 -4
-2 5
100 41
100 40
-3 0
-6 -2
18 -13		 2
3 3 3 0
100 -100 0
0 100 100
100 100 100
-100 100 100		 0

ID 29448. Роза ветров
Темы: Одномерные массивы    Алгоритмы обработки   

При выборе места строительства жилого комплекса при металлургическом комбинате необходимо учитывать "розу ветров" (следует расположить жилой комплекс так, чтобы частота ветра со стороны металлургического комбината была бы минимальной). Для этого в течении года проводилась регистрация направления ветра в районе строительства. Данные представлены в виде массива, в котором направление ветра ветра за каждый день (365) кодируется следующим образом: 
1 - северный (N),
2 - южный (S)
3 - восточный (E)
4 - западный (W)
5 - северо-западный (NW)
6 - северо - восточный (NE)
7 - юго-западный (SW)
8 - юго-восточный (SE).
Определить, как должен быть расположен жилой комплекс по отношению к комбинату

Входные данные: 
В первой строке подается 365 значений от 1 до 8 (направление ветра)

Выходные данные:
Вывести соответствующие буквы (аббревиатуру - смотри список выше), с какой стороны следует построить жилой комплекс
 
ID 37169. Игра "Жизнь". Простой вариант
Темы: Двумерные массивы    Алгоритмы обработки   

В некоторых клетках квадрата \( N\ х\ N\) живут микроорганизмы (не более одного в одной клетке). Каждую секунду происходит следующее:
– все микроорганизмы, у которых менее 2-х соседей, умирают от скуки (соседями называются микроорганизмы, живущие в клетках, имеющих общую сторону или вершину);
– все микроорганизмы, у которых более 3-х соседей, умирают от перенаселенности;
– на всех пустых клетках, у которых ровно в трех соседних клетках жили микроорганизмы, появляются новые микроорганизмы.
Все изменения происходят одновременно, то есть для каждой клетки сначала выясняется ее судьба, а затем происходят изменения сразу во всех клетках.
Требуется по данной конфигурации определить, во что она превратится через \(T\) секунд.

Входные данные: В первой строке вводятся два натуральных числа –\( N\) (\(1 \leq N \leq 10\)) и \(T\) (\(1 \leq T \leq 100\)). Далее записано \( N\) строчек по \( N\) чисел, описывающих начальную конфигурацию (0 – пустая клетка, 1 – микроорганизм). Числа в строках разделены пробелами.
Выходные данные: Требуется вывести \( N\) строк по \( N\) чисел – описание конфигурации через T секунд (в том же формате, как и во входных данных).

Примеры
№ Входные данные Выходные данные
1 3 1
1 0 1
1 0 1
1 0 1		 0 0 0
1 0 1
0 0 0
2 2 2
1 1
1 1		 1 1
1 1
3 5 10
1 0 1 1 0
0 1 0 0 0
0 0 0 1 0
0 0 0 0 0
0 1 0 1 0		 0 1 1 0 0
0 1 1 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0

ID 42268. Спрятанная карта
Темы: Одномерные массивы    Алгоритмы обработки   

В колоде у Громозеки находятся карты, на которых написано по одному целому числу. Каждое число в колоде встречается ровно 4 раза. 
Таким образом, в колоде имеются 4 карты с числом 1, 4 карты с числом 2, ..., 4 карты с числом N. Всего в колоде 4*N карт.

Громозека перетасовал эти карты, а затем спрятал одну из них и дал вам стопку оставшихся 4*N-1 карт. На i-й карте (1<= i <=4*N−1) из стопки написано целое число Ai.

Найдите целое число, записанное на карте, которую спрятал Громозека.

Входные данные
Программа получает на вход две строки. Первая строка содержит целое число N (1 <= N <= 105).  Вторая строка содержит 4*N-1 целых чисел Ai (1 <= Ai <= 4*N−1. 1<= i <=4*N−1). Для каждого k (1<=k<=N) существует не более 4 индексов i, таких, что Ai=k.


Выходные данные
Выведите ответ на задачу.
 
 

Примеры
№ Входные данные Выходные данные
1 3
1 3 2 3 3 2 2 1 1 1 2		 3
2 1
1 1 1		 1
3 4
3 2 1 1 2 4 4 4 4 3 1 3 2 1 3		 2

ID 42271. Количество элементов, больших обоих соседей
Темы: Одномерные массивы    Алгоритмы обработки   

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


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

Сначала задано число N - количество элементов в массиве (1 <= N <= 10000). Далее через пробел записаны N чисел - элементы массива. Массив состоит из целых чисел.


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

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

 
Примеры
№ Входные данные Выходные данные
1 
5
1 2 3 4 5
 
0
2 
5
2 3 2 4 3
 
2

ID 42324. Найти и посчитать
Темы: Массивы    Алгоритмы обработки   

Даны две целочисленные последовательности, каждая из которых имеет длину N: A = (A1, A2, ..., AN) и B = (B1, B2, ..., BN).
Все элементы A различны. Все элементы B тоже разные.

Выведите следующие два значения.

  1. Количество целых чисел, содержащихся в обоих A и B, появляющихся в одной и той же позиции в двух последовательностях. Другими словами, количество целых i чисел такое, что Ai = Bi.
  2. Количество целых чисел, содержащихся в обоих A и B, появляющихся в разных позициях в двух последовательностях. Другими словами, количество пар целых (i, j) чисел, таких, что Ai = Bj и i ≠ j.


Входные данные
Программа получает на вход три строки. В первой строке записано одно число N (1 <= N <= 1000) - количество чисел последовательности. Во второй строке записаны числа A1, A2, ..., AN, все числа различные. В третьей строке - числа B1, B2, ..., BN , все числа различные (1 <= Ai, Bi <= 109). 

Выходные данные
Выведите в первой строке ответ на первый вопрос, во второй строке - на второй.
 
 
Примеры
№ Входные данные Выходные данные
1 
4
1 3 5 2
2 3 1 4
 
1
2
2 
3
1 2 3
4 5 6
 
0
0

ID 44509. Башни 2.0
Темы: Задача на реализацию    Структуры данных    Структуры данных    Алгоритмы обработки    Линейные алгоритмы    Алгоритмы обработки   

В компьютерной игре есть n башен, высота i-й башни равна ai метров. Определим расстояние между двумя башнями с индексами i и j как |i−j|. Разрешается прыгнуть с i-й башни на j-ю башню тогда и только тогда, когда не существует такого индекса 1 <= k <= n, такого, что расстояние от i-й до j-й башни не меньше расстояния от i-й башни до k-й башни, и k-я башня имеет большую высоту, чем j-я. Башня j достижима из башни i если существует последовательность корректных прыжков, которая начинается в i-й башне и заканчивается в j-й. Посчитайте для каждой башни количество достижимых из неё башен, включая её саму.


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

Первая строка входных данных содержит одно целое число n (1 <= n <= 500000) - количество башен.

Вторая строка входных данных содержит n чисел a1, a2, ..., an (1 <= an <= 109) - высоты башен.


Выходные данные
Выведите n чисел, i-е из которых должно быть равным количеству башен, достижимых из i-й башни.
 
Примечание

В первом примере с 1-й башни можно прыгнуть на башни 1 и 5. Любая другая башня имеет меньшую высоту, чем башня 1, поэтому туда нельзя прыгнуть (в качестве k можно выбрать 1). Множество достижимых из 1-й башни также состоит из башен 1 и 5. Со второй башни можно прыгнуть на башни 1, 2, и 5, они же являются множеством достижимых. С третьей башни можно прыгнуть на башни 2, 3, 5. Однако, башня 1 также является достижимой, поскольку можно сделать два прыжка: 3→2→1. Таким образом, получается 4 достижимые башни. С 4-й башни можно прыгнуть на башни 4 и 5, они же являются единственными достижимыми. Из 5-й башни достижима только она сама.

Во втором примере из 1-й и из 2-й башни достижимы башни 1,2,3,4,5. Из 3-й башни достижимы башни 3,4,5. Из 4-й и 5-й башни достижимы башни 4,5. Из 6-й башни достижимы башни 4,5,6. Из 7-й башни достижимы башни 4,5,6,7.

 
 
Примеры
№ Входные данные Выходные данные
1 
5
7 6 3 4 10
 
2 3 4 2 1
2 
7
1 1 1 2 2 1 1
 
5 5 3 2 2 3 4