Grade 12 · Baccalaureate exam reviewCitește în română

File: the longest run of terms with the same parity

Original: Fișier — cea mai lungă secvență de termeni cu aceeași paritate

O(n)C++1763 lines2 examplesuses date.in / date.out

The idea

The task (exam part III.3 style): the file date.in holds a sequence of at most 10^6 natural numbers with at most 9 digits. A parity run is a run of consecutive terms that all have the same parity. Print the maximum length of a parity run and the number of parity runs that have this length and cannot be extended. Efficiency: we read the numbers one by one and keep only the parity of the previous term and the length of the current run; when the parity changes, the current run has ended and we compare it with the maximum. No array is used, so memory is constant.

Original description (Romanian)

Cerința (tip subiectul III.3): fișierul date.in conține un șir de cel mult 10^6 numere naturale de cel mult 9 cifre. O secvență paritară este o secvență de termeni consecutivi care au toți aceeași paritate. Afișați lungimea maximă a unei secvențe paritare și numărul de secvențe paritare care au această lungime și nu pot fi prelungite. Eficiența: citim numerele pe rând și ținem doar paritatea termenului anterior și lungimea secvenței curente; la schimbarea parității secvența curentă s-a încheiat și o comparăm cu maximul. Nu folosim niciun tablou, deci memoria este constantă.

Complexity
O(n) timp, O(1) memorie
Grade
Grade 12 (Clasa a XII-a)

Examples

Example 1

Input (date.in)

3 5 8 2 4 7 9 11 6

Expected output

3 2
Example 2

Input (date.in)

10

Expected output

1 1

The code

Comments are in Romanian, as in the original collection. Edit freely: you can reset at any time.

fisier-secventa-aceeasi-paritate.cpp
/*
 * Titlu: Fișier — cea mai lungă secvență de termeni cu aceeași paritate
 * Clasa: 12
 * Capitol: Recapitulare pentru bacalaureat
 * Descriere: Cerința (tip subiectul III.3): fișierul date.in conține un șir de cel
 *            mult 10^6 numere naturale de cel mult 9 cifre. O secvență paritară
 *            este o secvență de termeni consecutivi care au toți aceeași paritate.
 *            Afișați lungimea maximă a unei secvențe paritare și numărul de
 *            secvențe paritare care au această lungime și nu pot fi prelungite.
 *            Eficiența: citim numerele pe rând și ținem doar paritatea
 *            termenului anterior și lungimea secvenței curente; la schimbarea
 *            parității secvența curentă s-a încheiat și o comparăm cu maximul.
 *            Nu folosim niciun tablou, deci memoria este constantă.
 * Complexitate: O(n) timp, O(1) memorie
 *
 * Exemplu
 * Intrare: 3 5 8 2 4 7 9 11 6
 * Ieșire: 3 2
 *
 * Exemplu
 * Intrare: 10
 * Ieșire: 1 1
 */
#include <fstream>
#include <iostream>
using namespace std;

int main()
{
    ifstream fin("date.in");
    long long x;
    int paritateAnt = -1, lung = 0, lungMax = 0, cate = 0;
    while (fin >> x)
    {
        int p = x % 2;
        if (p == paritateAnt)
            lung++;
        else
        {
            // s-a încheiat secvența anterioară (dacă exista una)
            if (lung > lungMax)
            {
                lungMax = lung;
                cate = 1;
            }
            else if (lung == lungMax && lung > 0)
                cate++;
            lung = 1;
            paritateAnt = p;
        }
    }
    // ultima secvență se încheie la sfârșitul fișierului
    if (lung > lungMax)
    {
        lungMax = lung;
        cate = 1;
    }
    else if (lung == lungMax && lung > 0)
        cate++;
    cout << lungMax << ' ' << cate << '\n';
    return 0;
}

Runs on a real g++ (C++17, -O2) through Compiler Explorer. Keep runs short; there's a time limit.