Rezolvare completă PbInfo #2818 Inserare2

Cerința

Numim inserare a unui șir A într-un șir B introducerea, între două elemente ale șirului B, a tuturor elementelor lui A, pe poziții consecutive, în ordinea în care apar în A.

Se dau două șiruri cu n, respectiv m elemente numere întregi ordonate strict crescător, în care numerotarea elementelor începe de la 1.

Se cere să se afișeze poziția din al doilea șir începând de la care poate fi inserat primul șir, astfel încât șirul obținut să fie strict crescător. Dacă nu există o astfel de poziție, se afișează mesajul imposibil.

Date de intrare

Fișierul de intrare inserare2.in conține numere naturale din intervalul [1,106]: pe prima linie numerele m și n, iar pe fiecare dintre următoarele două linii câte un șir de m, respectiv de n numere întregi ordonate strict crescător. Numerele aflate pe aceeași linie a fișierului sunt separate prin câte un spațiu.

Date de ieșire

Fișierul de ieșire inserare2.out va conține poziția din al doilea șir începând de la care poate fi inserat primul șir, astfel încât șirul obținut să fie strict crescător. Dacă nu există o astfel de poziție, se afișează mesajul imposibil.

Restricții și precizări

  • Proiectați un algoritm eficient din punctul de vedere al spațiului de memorie utilizat și al timpului de executare.
    • se recomandă o soluție care să nu memoreze cel două șiruri în tablouri sau alte structuri de date similare.

Exemplul 1

inserare2.in

4 6
15 16 17 19
7 10 12 20 30 40

inserare2.out

4

Explicație

Se poate obține șirul 7, 10, 12, 15, 16, 17, 19, 20, 30, 40.

Exemplul 2

inserare2.in

4 6
15 16 17 19
7 14 18 20 30 40

inserare2.out

imposibil

Exemplul 3

inserare2.in

4 6
1 2 3 4
7 14 18 20 30 40

inserare2.out

imposibil

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

#include <iostream>
#include <fstream>
#include <cassert>

using namespace std;

ifstream fin("inserare2.in");
ofstream fout("inserare2.out");

int main(){
    int n , m , x, y , p , u , poz = 0;
    fin >> n >> m;
    fin >> p;
    for(int i = 2 ; i <= n ; i ++)
        fin >> x;
    u = x;
    fin >> x;
    for(int i = 2 ; i <= m ; i ++)
    {
        assert(fin >> y);
        if(x < p && u < y)
            poz = i;
        x = y;
    }
    if(poz == 0)
        fout << "imposibil
";
    else
        fout << poz << endl;
        
    fin.close();
    fout.close();
    
    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 #2818 Inserare2

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