# Problème 1

Located on a line are N segments, numbered from 0 to N − 1, whose positions are given in arrays A and B. For each I (0 ≤ I < N) the position of segment I is from A[I] to B[I] (inclusive). The segments are sorted by their ends, which means that B[K] ≤ B[K + 1] for K such that 0 ≤ K < N − 1.

Two segments I and J, such that I ≠ J, are overlapping if they share at least one common point. In other words, A[I] ≤ A[J] ≤ B[I] or A[J] ≤ A[I] ≤ B[J].

We say that the set of segments is non-overlapping if it contains no two overlapping segments. The goal is to find the size of a non-overlapping set containing the maximal number of segments.

For example, consider arrays A, B such that:

A = 1 B = 5
A = 3 B = 6
A = 7 B = 8
A = 9 B = 9
A = 9 B = 10
The segments are shown in the figure below.

The size of a non-overlapping set containing a maximal number of segments is 3. For example, possible sets are {0, 2, 3}, {0, 2, 4}, {1, 2, 3} or {1, 2, 4}. There is no non-overlapping set with four segments.

Write a function:

def solution(A, B)

that, given two arrays A and B consisting of N integers, returns the size of a non-overlapping set containing a maximal number of segments.

For example, given arrays A, B shown above, the function should return 3, as explained above.

Write an efficient algorithm for the following assumptions:

N is an integer within the range [0..30,000];
each element of arrays A and B is an integer within the range [0..1,000,000,000];
A[I] ≤ B[I], for each I (0 ≤ I < N);
B[K] ≤ B[K + 1], for each K (0 ≤ K < N − 1).

# Problème 2

Pour un tableau donné A de N entiers et une suite S de N entiers de l'ensemble {−1, 1}, on définit val(A, S) comme suit :

val(A, S) = |somme{ A[i]*S[i] pour i = 0..N−1 }|

(Supposons que la somme de zéro élément est égale à zéro.)

Pour un tableau A donné, on cherche une telle suite S qui minimise val(A,S).

Écrivez une fonction :

def solution(A)

qui, étant donné un tableau A de N entiers, calcule la valeur minimale de val(A,S) à partir de toutes les valeurs possibles de val(A,S) pour toutes les séquences possibles S de N entiers de l'ensemble {−1, 1}.

Par exemple, tableau donné :

A = 1
A = 5
A = 2
A = -2
votre fonction doit retourner 0, puisque pour S = [−1, 1, −1, 1], val(A, S) = 0, qui est la valeur minimale possible.

Ecrire un algorithme efficace pour les hypothèses suivantes :

N est un nombre entier dans la plage [0..20 000] ;
chaque élément du tableau A est un entier compris dans l'intervalle [−100..100].

# Problème 3

You are given N counters, initially set to 0, and you have two possible operations on them:

increase(X) − counter X is increased by 1,
max counter − all counters are set to the maximum value of any counter.
A non-empty array A of M integers is given. This array represents consecutive operations:

if A[K] = X, such that 1 ≤ X ≤ N, then operation K is increase(X),
if A[K] = N + 1 then operation K is max counter.
For example, given integer N = 5 and array A such that:

A = 3
A = 4
A = 4
A = 6
A = 1
A = 4
A = 4
the values of the counters after each consecutive operation will be:

(0, 0, 1, 0, 0)
(0, 0, 1, 1, 0)
(0, 0, 1, 2, 0)
(2, 2, 2, 2, 2)
(3, 2, 2, 2, 2)
(3, 2, 2, 3, 2)
(3, 2, 2, 4, 2)
The goal is to calculate the value of every counter after all operations.

Write a function:

def solution(N, A)

that, given an integer N and a non-empty array A consisting of M integers, returns a sequence of integers representing the values of the counters.

Result array should be returned as an array of integers.

For example, given:

A = 3
A = 4
A = 4
A = 6
A = 1
A = 4
A = 4
the function should return [3, 2, 2, 4, 2], as explained above.

Write an efficient algorithm for the following assumptions:

N and M are integers within the range [1..100,000];
each element of array A is an integer within the range [1..N + 1].

# Problème 4

Un tableau A non vide composé de N entiers est donné. Une paire d'entiers (P, Q), telle que 0 ≤ P < Q < N, est appelée une tranche du tableau A (notez que la tranche contient au moins deux éléments). La moyenne d'une tranche (P, Q) est la somme de A[P] + A[P + 1] + ... + A[Q] divisée par la longueur de la tranche. Pour être précis, la moyenne est égale à (A[P] + A[P + 1] + ... + A[Q]) / (Q − P + 1).

Par exemple, tableau A tel que :

A = 4
A = 2
A = 2
A = 5
A = 1
A = 5
A = 8
contient les exemples de tranches suivants :

tranche (1, 2), dont la moyenne est (2 + 2) / 2 = 2 ;
tranche (3, 4), dont la moyenne est (5 + 1) / 2 = 3 ;
tranche (1, 4), dont la moyenne est (2 + 2 + 5 + 1) / 4 = 2,5.
Le but est de trouver la position de départ d'une tranche dont la moyenne est minimale.

Écrivez une fonction :

classe Solution { public int solution(int[] A); }

qui, étant donné un tableau A non vide composé de N entiers, renvoie la position de départ de la tranche avec la moyenne minimale. S'il y a plus d'une tranche avec une moyenne minimale, vous devez renvoyer la plus petite position de départ d'une telle tranche.

Par exemple, étant donné le tableau A tel que :

A = 4
A = 2
A = 2
A = 5
A = 1
A = 5
A = 8
la fonction doit renvoyer 1, comme expliqué ci-dessus.

Ecrire un algorithme efficace pour les hypothèses suivantes :

N est un nombre entier dans la plage [2..100 000] ;
chaque élément du tableau A est un entier compris dans l'intervalle [−10 000..10 000].

# Problème 5

A game for one player is played on a board consisting of N consecutive squares, numbered from 0 to N − 1. There is a number written on each square. A non-empty array A of N integers contains the numbers written on the squares. Moreover, some squares can be marked during the game.

At the beginning of the game, there is a pebble on square number 0 and this is the only square on the board which is marked. The goal of the game is to move the pebble to square number N − 1.

During each turn we throw a six-sided die, with numbers from 1 to 6 on its faces, and consider the number K, which shows on the upper face after the die comes to rest. Then we move the pebble standing on square number I to square number I + K, providing that square number I + K exists. If square number I + K does not exist, we throw the die again until we obtain a valid move. Finally, we mark square number I + K.

After the game finishes (when the pebble is standing on square number N − 1), we calculate the result. The result of the game is the sum of the numbers written on all marked squares.

For example, given the following array:

A = 1 A = -2 A = 0 A = 9 A = -1 A = -2

one possible game could be as follows:

• the pebble is on square number 0, which is marked;
• we throw 3; the pebble moves from square number 0 to square number 3; we mark square number 3;
• we throw 5; the pebble does not move, since there is no square number 8 on the board;
• we throw 2; the pebble moves to square number 5; we mark this square and the game ends.

The marked squares are 0, 3 and 5, so the result of the game is 1 + 9 + (−2) = 8. This is the maximal possible result that can be achieved on this board.

Write a function:

class Solution { public int solution(int[] A); }

that, given a non-empty array A of N integers, returns the maximal result that can be achieved on the board represented by array A.

For example, given the array

A = 1 A = -2 A = 0 A = 9 A = -1 A = -2

the function should return 8, as explained above.

Write an efficient algorithm for the following assumptions:

• N is an integer within the range [2..100,000];
• each element of array A is an integer within the range [−10,000..10,000].