Problème

JOI est un artisan de dango. Il existe N couleurs de dango, numérotées de 1 à N. JOI possède A_i dangos de la couleur i (pour 1 ≤ i ≤ N).

Il peut sélectionner 3 dangos pour former une brochette. Les couleurs des trois dangos (c₁, c₂, c₃) doivent respecter les conditions suiventes :

• |c₁ - c₂| ≤ 1
• |c₂ - c₃| ≤ 1
• |c₃ - c₁| ≤ 1

Autrement dit, toutes les couleurs de la brochette doivent être identiques ou adjacentes. Un même dango ne peut être utilisé que dans une seule brochette.

On doit déterminer le nombre maximal de brochettes que JOI peut produire avec les dangos dont il dispose.

Format d'entrée

N
A₁ A₂ ... Aₙ

Format de sortie

Un entier unique : le nombre maximal de brochettes réalisables.

Exemples

Exemple 1

Entrée :
3
3 1 2

Sortie :
2

Explication : On peut former 2 brochettes. La première utilise 3 dangos de couleur 1. La seconde utilise 1 dango de couleur 2 et 2 dangos de couleur 3. On ne peut pas en faire plus.

Exemple 2

Entrée :
1
99

Sortie :
33

Explication : On forme 33 brochettes avec 3 dangos de couleur 1 chacune.

Exemple 3

Entrée :
2
5 6

Sortie :
3

Explication : On peut former 3 brochettes : une avec 3 dangos de couleur 1, une avec 2 dangos de couleur 1 et 1 de couleur 2, et une avec 3 dangos de couleur 2.

Exemple 4

Entrée :
6
0 2 2 3 1 2

Sortie :
3

Exemple 5

Entrée :
1
0

Sortie :
0

Contraintes

• 1 ≤ N ≤ 200 000
• 0 ≤ A_i ≤ 10⁹
• Toutes les valeurs d'entrée sont entières.

Solution

Le problème peut être résolu par un algorithme glouton. Pour chaque couleur, on essaie d'abord de combiner les dangos restants de la couleur précédente (appelons ce reste reste) avec la couleur courante pour former une brochette complète. Ensuite, on forme autant de brochettes que possible uniquement avec la couleur courante, et on conserve le reste pour la prochaine itération.

On parcourt ainsi les couleurs de 1 à N. À chaque étape :

1. Si la somme du reste de la couleur précédente et du nombre de dangos de la couleur courante est au moins 3, on forme une brochette. On diminue alors le nombre de dangos de la couleur courante de la quantité nécessaire (3 - reste).
2. On calcule combien de brochettes complètes on peut former avec les dangos restants de la couleur courante (division entière par 3).
3. On met à jour le reste pour la prochaine étape (modulo 3).

Il faut utiliser des entiers de type long long pour éviter les dépassements.

Code C++

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<long long> stocks(n);
    for (int i = 0; i < n; ++i) {
        cin >> stocks[i];
    }

    long long skewers = 0;
    long long leftover = 0; // reste de la couleur précédente

    for (int idx = 0; idx < n; ++idx) {
        // Combinaison avec le reste de la couleur précédente
        if (leftover + stocks[idx] >= 3) {
            skewers++;
            long long needed = 3 - leftover;
            stocks[idx] -= needed;
            leftover = 0;
        }
        // Brochettes complètes avec la couleur courante
        skewers += stocks[idx] / 3;
        leftover = stocks[idx] % 3;
    }

    cout << skewers << endl;
    return 0;
}