Processing algorithms

ID 38716. Gromozeka's Joy

Gromozek has a sequence of integers A of length N. It will make three slices in the  A sequence and split it into four (non-empty) contiguous subsequences B, C, D > and E. He chooses the positions of the slices arbitrarily. Let P, Q, R, S be the sums of elements in B, < code>C, D,  E respectively. Gromozeka will be happy when the absolute difference between the maximum and minimum between P, Q, R, S  minimum. Find the smallest possible absolute difference between the maximum and minimum between P, Q, R, S.

Input
The first line contains an integer N  (\(1<=N<=2 \cdot 10^5\)). The second line contains N integers Ai (\(1<=A_i<=10 ^9\)).

Imprint
Print the smallest possible absolute difference between the maximum and minimum between P, Q, R, S.
 

Examples

ID 39382. Will you solve it?

There are N parts of some source code. The characteristics of the ith part of the code are represented by M integers Ai1, Ai2< /sub>, ..., AiM . You are given integers B1, B2, ...< /font>, BM , and C.
The ith part of the code solves the problem correctly if and only if \( A_{i1}\cdot B_1 + A_{i2} \cdot B_2 + ...+ A_{iM}\cdot B_M +C>0\).
Among the N parts of the source code, find the number that correctly solve this problem.

Input
The first line contains three space-separated numbers: N, M (1 <= N, M <= 20) and C (- 100 <= C <= 100). The second line contains   M numbers Bi (-100 <= B_i <= 100). Each of the following N lines contains M numbers Ai (-100 <= A _ij <= 100, 1 <= i <= N, 1 <= j <= M).

Imprint
Print one number - the answer to the problem.
 

Examples

ID 29448. Rose of Wind

When choosing a construction site for a residential complex at a metallurgical plant, it is necessary to take into account the "wind rose"; (the residential complex should be located so that the frequency of the wind from the side of the metallurgical plant would be minimal). To do this, during the year, the wind direction was recorded in the construction area. The data is presented as an array in which the wind direction of the wind for each day (365) is encoded as follows: 
1 - northern (N),
2 - southern (S)
3 - east (E)
4 - western (W)
5 - northwest (NW)
6 - northeast (NE)
7 - southwest (SW)
8 - southeast (SE).
Determine how the residential complex should be located in relation to the plant

Input: 
The first line contains 365 values ​​from 1 to 8 (wind direction)

Imprint:
Print the corresponding letters (abbreviation - see the list above) on which side the residential complex should be built
 

ID 37169. Game "Life". Easy option

In some cells of the square \( N\ х\ N\) microorganisms live (no more than one in one cell). The following happens every second:
– all microorganisms that have less than 2 neighbors die of boredom (neighbors are microorganisms that live in cells that have a common side or top);
– all microorganisms with more than 3 neighbors die from overcrowding;
– on all empty cells, in which microorganisms lived in exactly three adjacent cells, new microorganisms appear.
All changes occur simultaneously, that is, for each cell, its fate is first clarified, and then changes occur in all cells at once.
It is required to determine from this configuration what it will turn into after \(T\) seconds.

ID 42268. Hidden map

In the deck, Gromozeka has cards on which one whole number is written. Each number in the deck occurs exactly 4 times. 
Thus, in the deck there are 4 cards with the number 1, 4 cards with the number 2, ..., 4 cards with the number N. In total, there are 4*N cards in the code.

Gromozeka shuffled those cards, then hid one of them and gave you a stack of the remaining 4*N-1 cards. The i-th card (1<= i <=4*N−1) from the stack contains an integer Ai.

Find the integer written on the card that Gromozeka hid.

Input
The program receives two lines as input. The first line contains the integer N (1 <= N <= 10⁵).  The second line contains 4*N-1 integers Ai (1 <= Ai <= 4*N−1. 1<= i <=4*N−1). For each k (1<=k<=N) there are at most 4 i indices, such that Ai=k.


Imprint
Print the answer to the problem.
 
 

Examples

ID 42271. Number of elements greater than both neighbors

You are given an array of integers. Write a program that in the given array determines the number of elements that have two neighboring elements and, at the same time, both neighboring elements are less than the given one.

First given is a number N - number of elements in the array (1 <= N <= 10000). Then, space-separated  N numbers - elements of the array. The array consists of integers.

You need to output the number of array elements that have two neighbors and are strictly greater than both of their neighbors.

Examples

5
1 2 3 4 5

0

5
2 3 2 4 3

2

ID 42324. Find and count

Given two integer sequences, each of length N: A = (A1, A 2, ..., AN) and B = (B1, B2, ..., BN).
All A elements are different. All B elements are also different.

Print the following two values.

1. The number of integers contained in both A and B appearing in the same position in the two sequences. In other words, the number of integers  i numbers such that Ai = Bi.
2. The number of integers contained in both A and B that appear at different positions in the two sequences. In other words, the number of pairs of integers  (i, j) numbers such that Ai = Bj and i ≠ j.

Examples

4
1 3 5 2
2 3 1 4

1
2

3
1 2 3
4 5 6

0
0