# PBinfo #1675 – Calc – Rezolvare C++

Sursa: Codul lui Andrei
Limbaj: C++
Autor rezolvare: Darius

## Enunț

La un concurs de informatică participă 2∙N elevi împărțiți în N echipe de câte 2. Echipa poate lucra în comun la problemele propuse doar dacă au calculatoarele în rețea. Laboratorul de informatică este unul special: are 2∙N calculatoare, distribuite pe două rânduri la distanță de un metru între ele (vertical și orizontal) și N cabluri de rețea de lungime un metru. Concursul se desfășoară pe mai multe zile și nu există două zile de concurs cu aceeași configurație a rețelei.

Exemplu: pentru N=3, cei 6 elevi au fost împărțiți în 3 echipe, iar aranjarea rețelei în cele 3 zile de concurs este cea din figura de mai jos.



Administratorul laboratorului vrea să memoreze în ordine lexicografică toate configurațiile folosite în zilele de concurs. Cablul orizontal se notează prin 0, iar cel vertical prin 1. Lucrând ordonat și eficient, pentru cele trei zile el își va nota valorile: 001, 100, respectiv 111. Se observă că o reprezentare de genul 000, 010, 011, 101 nu poate fi realizată.

Cerința
Cunoscând N, să se determine:


Numărul de zile modulo 1000000007 în care se desfășoară concursul.
Configurațiile laboratorului în ziua X-1 și ziua X+1, cunoscând configurația zilei X.

Date de intrare
Fişierul de intrare calc.in conţine pe prima linie un număr natural p. Pentru toate testele de intrare, numărul p poate avea doar valoarea 1 sau valoarea 2.

Pe linia a doua vom avea numărul natural N.

Pe linia a treia se va găsi un șir de N cifre binare, fără spații între ele, reprezentând configurația corectă realizată de administrator în ziua X.

Date de ieșire
Dacă valoarea lui p este 1, se va rezolva numai punctul 1) din cerință.
În acest caz, în fişierul de ieşire calc.out se va scrie un singur număr natural Z reprezentând numărul de zile în care se desfășoară concursul pentru cele N echipe.

Dacă valoarea lui p este 2, se va rezolva numai punctul 2) din cerință. 
În acest caz, fişierul de ieşire calc.out va conține două linii. Pe prima linie se vor scrie N cifre binare, fără spații între ele, reprezentând configurația rețelei din ziua precedentă, iar pe a doua linie N cifre binare, fără spații între ele, reprezentând configurația din ziua următoare. Dacă în ziua precedentă nu există o configurație conform cerințelor problemei,  se va scrie pe prima linie valoarea -1. Dacă în ziua următoare nu există o configurație conform cerințelor problemei, se va scrie pe a doua linie valoarea -1.

Restricții și precizări

1 ≤ N ≤ 100000
Pentru rezolvarea corectă a primei cerinţe se acordă 20 de puncte, iar pentru cerința a doua se acordă 80 de puncte.

Exemplul 1
calc.in

1
3
001
calc.out

3
Exemplul 2
calc.in

2
3
001
calc.out

-1
100

## Cod sursă C++

```cpp
// Adrian Budau - 100 de puncte - Complexitate O(N)
#include <iostream>
#include <fstream>
using namespace std;
static const int kModulo = 1000 * 1000 * 1000 + 7;
int main() {
    ifstream cin("calc.in");
    ofstream cout("calc.out");
    int tip; cin >> tip;
    int N; cin >> N;
    string S; cin >> S;
    if (tip == 1) {
        int A = 1, B = 1;
        for (int i = 2; i <= N; ++i) {
            int C = (A + B) % kModulo;
            A = B; B = C;
        }
        cout << B << "\n";
        return 0;
    }
    if (N == 1) {
        cout << -1 << "\n" << -1 << "\n";
        return 0;
    }
    string prev = S, next = S;
    // predecessor
    if (S[N - 1] == '1' && S[N - 2] == '1')
        prev[N - 1] = prev[N - 2] = '0';
    else {
        int i;
        for (i = N - 2; i >= 0 && S[i] == '0'; --i);
        if (i < 0)
            prev = "-1";
        else {
            prev[i] = '0';
            for (i += 2; i < N; ++i)
                prev[i] = '1';
        }
    }
    // successor
    if (S[N - 1] == '0' && S[N - 2] == '0')
        next[N - 1] = next[N - 2] = '1';
    else {
        int i;
        for (i = N - 1; i >= 0 && S[i] == '1'; --i);
        if (i < 0)
            next = "-1";
        else {
            next[i - 1] = '1';
            next[i] = '0';
            int oldi = i;
            for (++i; i < N; ++i)
                next[i] = '0';
            if ((N - 1 - oldi) % 2 == 0)
                next[N - 1] = '1';
        }
    }
    cout << prev << "\n" << next << "\n";
}
```

## Resurse

- [Pagina originală](https://codulluiandrei.ro/rezolvari/pbinfo/1675)
- [Sursa C++](https://codulluiandrei.ro/rezolvari/pbinfo/1675/cod.cpp)
- [Sursa pe GitHub](https://raw.githubusercontent.com/codulluiandrei/pbinfo/main/pbinfo-1675/main.cpp)
- [Cursuri de informatică pentru BAC](https://codulluiandrei.ro/academia/info-curs/pachet-cpp/)