Rezolvare completă PbInfo #2153 Mirror

Numim „oglinda” numărului natural nenul a, numărul b, obţinut prin modificarea fiecărei cifre din reprezentarea sa binară, de exemplu pentru a=22(10)=10110(2) se obţine 01001(2)= 9(10)=b.

Cerința

Cunoscându-se numerele naturale N, K și cele N numere natural nenule, scrieți un program care:

  1. Transformă în baza doi termenii şirului dat obţinându-se un nou şir format din alipirea cifrelor binare. Din acest şir se vor determina și afișa, separate prin câte un spațiu, toate reprezentările în baza 10 corespunzătoare secvenţelor alăturate de exact K cifre binare, parcurse de la stânga la drepta. Dacă ultima secvenţă nu are exact K cifre binare, atunci aceasta nu se va mai lua în considerare.
  2. Să aplice K transformări asupra şirului iniţial, înlocuind la fiecare pas orice termen cu „oglinda” sa. Asupra termenilor care devin zero nu se vor mai efectua alte operații. După efectuarea celor K transformări, să se determine cea mai lungă secvență de numere care au cifra 1 pe aceeași poziție în reprezentarea lor în baza doi. Dacă sunt mai multe astfel de secvențe având lungimea maximă, se va afișa cea mai din stânga.

Date de intrare

Fișierul de intrare mirror.in conţine pe primul rând numărul C, reprezentând cerința. Pe al doilea rând se află scrise numerele naturale N și K. Pe rândul al treilea sunt cele N numere ale șirului separate prin câte un spațiu.

Date de ieșire

Dacă C=1, atunci în fişierul de ieşire mirror.out se vor scrie separate prin câte un spațiu, toate numerele cerute în enunț.
Dacă C=2, atunci în fişierul de ieşire mirror.out se va scrie pe prima linie lungimea maximă a secvenței determinate, iar pe următoarea linie separate prin spațiu, poziția primului și ultimului termen din secvență (prima poziție este 1).

Restricții și precizări

  • 1 ≤ N ≤ 100000
  • 0 ≤ K ≤ 30
  • Elementele șirului sunt mai mici decât 2000000001;
  • Pentru 30% din teste cerinţa va fi C=1.

Exemplul 1

mirror.in

1 
4 2
7 8 2 11

mirror.out

3 3 0 1 1 1

Explicație

7(10)=111(2); 8(10)=1000(2); 2(10)=10; 11(10)=1011(2);

Sirul format este: 1111000101011 și grupate câte 2 avem numerele: 11(2)=3(10); 11(2)=3(10); 00(2)=0(10); 01(2)=1(10); 01(2)=1(10); 01(2)=1(10);

Exemplul 2

mirror.in

2 
5 1
37 72 101 50 116

mirror.out

3
1 3

Explicație

După o transformare numerele în baza 2 sunt:

0 1 1 0 1 0 <-37
0 1 1 0 1 1 1 <-72
0 0 1 1 0 1 0 <-101
0 0 1 1 0 1 <-50
0 0 0 1 0 0 0 <-116

Cea mai lungă secvență este de lungime 3, fiind formată din numerele 37, 72, 101 care începe pe poziția 1 și se termină pe poziția 3. Mai există încă o astfel de secvenţa (101, 50, 116) dar se alege cea mai din stânga.

Cum e corect?

cout < "As la info"; cout << "As la info"; cout >> "As la info";

Felicitări! Poți mai mult?

Avem sute de probleme pentru tine, fiecare cu explicații ușor de înțeles.

Greșit, dar nu-i bai!

Antrenează-te cu sutele de probleme pe care ți le-am pregătit. Îți explicăm fiecare problemă în parte.

Rezolvare

Iată rezolvarea de 100 de puncte pentru problema Mirror:

// Autor: Mihai Enache
#include <iostream>
#include <fstream>
using namespace std;

const int MAX_N = 1000002;

int C, N, K;
int v[MAX_N];

int main() {
    ifstream cin("mirror.in");
    ofstream cout("mirror.out");

    cin >> C >> N >> K;
    for(int i = 1; i <= N; ++i) {
        cin >> v[i];
    }

    if(C == 1) {
        int currentValue = 0;
        int nrBits = 0;

        for(int i = 1; i <= N; ++i) {
            int maxBit = 0;
            for(int bit = 31; bit >= 0; --bit) {
                if(v[i] & (1 << bit)) {
                    maxBit = bit;
                    break;
                }
            }

            for(int bit = maxBit; bit >= 0; --bit) {
                if(v[i] & (1 << bit)) {
                    currentValue = currentValue * 2 + 1;
                }
                else {
                    currentValue = currentValue * 2;
                }

                ++nrBits;

                if(nrBits == K) {
                    cout << currentValue << " ";

                    currentValue = 0;
                    nrBits = 0;
                }
            }
        }

        cout << "
";
    }
    else {
        for(int i = 1; i <= N; ++i) {
            for(int j = 1; j <= K; ++j) {
                if(!v[i]) {
                    break;
                }

                int maxBit = 0;
                for(int bit = 31; bit >= 0; --bit) {
                    if(v[i] & (1 << bit)) {
                        maxBit = bit;
                        break;
                    }
                }

                v[i] ^= (1 << (maxBit + 1)) - 1;
            }
        }

        int startPos = -1;
        int endPos = -1;
        int maxLength = 0;

        for(int bit = 0; bit < 32; ++bit) {
            int currentLength = 0;
            for(int i = 1; i <= N; ++i) {
                if(v[i] & (1 << bit)) {
                    ++currentLength;
                }
                else {
                    currentLength = 0;
                }

                if(currentLength > maxLength || (currentLength == maxLength && i - currentLength + 1 < startPos)) {
                    maxLength = currentLength;
                    startPos = i - currentLength + 1;
                    endPos = i;
                }
            }
        }

        cout << maxLength << "
";
        cout << startPos << " " << endPos << "
";
    }

    return 0;
}

Atenție

Enunțurile afișate pe această pagină aparțin exclusiv site-ului PbInfo. Astfel, pentru ștergerea conținutului, puteți să ne contactați la adresa Adresa de email.

Rezolvarea problemei #2153 Mirror

Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #2153 Mirror de pe PbInfo.ro. Atenție: nu încurajăm copiatul codului! Totuși, credem cu tărie că analizarea unei soluții corecte este o metodă foarte ușoară de a învăța informatică, astfel că oferim sursele pentru peste 1500 de probleme de pe platforma PbInfo.ro.

Pentru rezolvări PbInfo de la peste 1500 de probleme, vă invităm să intrați pe site-ul nostru!