Cerința

Agentul 007 a uitat cifrul seifului în care păstra documentele, însă ştie cum poate fi aflat. Are nişte cartonaşe pe care sunt notate n numere naturale distincte din intervalul [ a,b ]. Mai are o listă cu m numere naturale distincte care reprezintă anumite poziţii din şirul ordonat crescător al numerelor de pe cartonaşe. Însumând numerele aflate pe poziţiile din listă se determină un număr natural care reprezintă cifrul seifului. Cum Agentul 007 nu a mai programat din liceu, vă roagă pe voi să găsiţi cifrul în schimbul a 100 de … puncte.

Date de intrare

Fișierul de intrare memory007.in conține pe prima linie numerele n,m,a,b, pe a doua linie n numere naturale distincte separate prin spații reprezentând numerele de pe cartonaşe, iar pe a treia linie m numere naturale distincte reprezentând poziţiile din listă.

Date de ieșire

Fișierul de ieșire memory007.out va conține pe prima linie cifrul seifului.

Restricții și precizări

1 ≤ m ≤ n ≤ 500.000
numerele de pe cartonaşe vor fi distincte şi mai mici decât 1.000.000.000
numerele din listă vor fi naturale nenule, distincte şi mai mici sau egale cu n, ordonate crescător
1 ≤ a ≤ b ≤ 1.000.000.000
n ≤ b - a ≤ 700.000

Exemplu

memory007.in

5 3 30 80
78 56 34 45 61
1 2 5

memory007.out

Explicație

Numerele de pe cartonaşe sunt 78,56,34,45,61 şi sunt din intervalul [ 30,80 ]. Ordonate crescător formează şirul 34,45,56,61,78. Numerele din listă, adică 1,2,5, ne spun că cifrul se obţine însumând numerele de pe poziţiile 1, 2 şi 5 din şirul ordonat crescător al numerelor de pe cartonaşe, adică cifrul este 34+45+78=157.

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

#include <fstream>
#include <bitset>

using namespace std;

ifstream f("memory007.in");
ofstream g("memory007.out");

bitset<700020> v ;
long n , m , a , b , i , j , nr , x ;
long long suma , r , t ;

int main()
{
    f >> n >> m >> a >> b ;
    for ( i=1 ; i<=n ; i++ )
    {
        f >> x ;
        j = x-a ;
        v[j] = 1 ;
    }
    j = 0 ;
    nr = 0 ;
    suma = 0 ;
    for ( i=1 ; i<=m ; i++)
    {
        f >> x ;
        while ( nr < x )
        {
          nr = nr + v[j] ;
          j++ ;
        }
        suma = suma + j - 1 ;
    }
    r = m ;
    t = a ;
    suma = suma + r * t ;
    g << suma ;
    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 #1906 Memory007

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

Rezolvare completă PbInfo #1906 Memory007