2A.algo - Puzzles algorithmiques (2)#

Puzzles algorithmiques tirés de Google Code Jam et autres sites équivalents, nombres premiers, écoulement d’eau, séparation des bagarreurs, formation de binômes.

```from jyquickhelper import add_notebook_menu
```

Exercice 1 : nombres premiers#

CodeForces 483A

On propose la conjecture suivante :

Si sont premiers entre eux et si sont premiers entre eux alors sont premiers entre eux.

On veut montrer que cette conjecture est fausse. Pour cela, il faut trouver trois entiers pour lesquels l’énoncé est faux et on les cherche tels qu’il existe deux entiers :

Exercice 2 : watersheds#

Geologists sometimes divide an area of land into different regions based on where rainfall flows down to. These regions are called drainage basins.

Given an elevation map (a 2-dimensional array of altitudes), label the map such that locations in the same drainage basin have the same label, subject to the following rules.

• From each cell, water flows down to at most one of its 4 neighboring cells.

• For each cell, if none of its 4 neighboring cells has a lower altitude than the current cell’s, then the water does not flow, and the current cell is called a sink.

• Otherwise, water flows from the current cell to the neighbor with the lowest altitude.

• In case of a tie, water will choose the first direction with the lowest altitude from this list: North, West, East, South.

Every cell that drains directly or indirectly to the same sink is part of the same drainage basin. Each basin is labeled by a unique lower-case letter, in such a way that, when the rows of the map are concatenated from top to bottom, the resulting string is lexicographically smallest. (In particular, the basin of the most North-Western cell is always labeled ‘a’.)