Rezolvare completă PbInfo #1689 MoveDel

Se consideră două șiruri de caractere A și B, ambele șiruri având același număr de caractere.

Asupra șirurilor se aplică următorul algoritm:

  • șirul A se permută circular cu ki poziții spre stânga
  • din cele două șiruri se elimină caracterele care coincid din punct de vedere al poziției și valorilor

Algoritmul se oprește când fie ambele șiruri devin vide, fie șirurile nu mai au caractere comune. Valoarea ki pentru fiecare pas i reprezintă al i-lea număr prim din mulțimea numerelor prime.

Cerința

Dându-se N și M, să se genereze șirurile A și B, ambele având lungimea N, astfel încât numărul de repetări ale algoritmului aplicat celor două șiruri să fie M.

Date de intrare

Fișierul de intrare movedel.in conține pe prima linie valorile N și M.

Date de ieșire

În fişierul de ieşire movedel.out se vor scrie șirurile de caractere A și B de lungime N, fiecare pe câte un rând.

Restricții și precizări

  • Șirurile trebuie să conțină doar litere mici ale alfabetului englez.
  • În cazul în care algoritmul efectuează cel puțin M repetări pentru șirurile afișate, se va obține punctajul maxim pentru test. În caz contrar se vor obține [X/M*10] puncte pe test, unde X este numărul de repetări ale algoritmului (prin [X/M] se înțelege partea întreagă a numărului X/M).
  • Se garantează că există soluție pentru datele de test:

    Testul 0 1 2 3 4 5 6 7 8 9
    N 23 23 50 100 50 100 500 1000 1550 2000
    M 50 107 250 160 100 700 1500 8000 12000 16000

Exemplul 1

movedel.in

3 5

movedel.out

abc
cba

Explicație

Prima aplicare a algoritmului:

cab – după permutarea spre stânga cu 2 poziții (2 – primul număr prim), după eliminarea caracterelor comune, cele două șiruri vor fi:
ab
ba

A doua aplicare a algoritmului:
ba – după permutarea spre stânga cu 3 poziții (3 – al doilea număr prim), după eliminarea caracterelor comune, cele două șiruri devin vide, algoritmul încheindu-se.

Astfel se obțin [2/5*10]=4 puncte pentru acest test

Exemplul 2

movedel.in

5 5

movedel.out

abcde
edabc

Explicație

Pentru șirurile găsite, algoritmul se încheie după 20 de etape.
Astfel se obțin 10 puncte.

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 MoveDel:

// Adrian Budau - 100 de puncte - O(M)
#include <iostream>
#include <vector>
#include <bits/stdc++.h>

using namespace std;

static const int kMaxV = 1000 * 1000 + 7;

int main() {
    freopen("movedel.in","r",stdin);
    freopen("movedel.out","w",stdout);

    vector<bool> sieve(kMaxV, false);
    vector<int> primes;
    for (int i = 2; i < kMaxV; ++i)
        if (!sieve[i]) {
            primes.push_back(i);
            for (int j = i + i; j < kMaxV; j += i)
                sieve[j] = true;
        }
    reverse(primes.begin(), primes.end());

    int N; cin >> N;

    int covered = 0;
    vector<bool> cover(N, 0);
    int last = -1;
    int lastlast = 0;
    int now = 0;
    int iterations = 0;
    while (covered < N) {
        now = now + primes.back();
        primes.pop_back();
        now %= N;
        if (!cover[now]) {
            cover[now] = true;
            ++covered;
            lastlast = last;
            last = now;
        }
        ++iterations;
    }
    string A(N, 'b'), B(N, 'c');
    B[0] = 'a';
    A[last] = 'a';

    cerr << "I think i did " << iterations << " iterations\n";
    cerr << "With last " << last << " and last last " << lastlast << "\n";
    cout << A << "\n" << B << "\n";
}

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 #1689 MoveDel

Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #1689 MoveDel 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!