Question

Gigel a găsit un șir de n cifre minunate. A adormit cu ele în brațe și a visat m numere naturale. Nedumerit, a cerut părerea vrăjitoarei Ghiocica. Acesta i-a spus: - Gigele, ești norocos. Suma numerelor distincte visate care sunt scrise cu cifre consecutive în șirul de cifre minunate este suma pe care o vei câștiga la Loto. Nerăbdător, Gigel vă roagă să scrieți un program care să citească cele n cifre și cele m numere să să determine suma pe care o va câștiga la Loto. Date de intrare Fișierul de intrare potrivire.in conține pe prima linie numărul n; a doua linie conține șirul de n cifre. A treia linie conține numărul m, iar a patra linie conține cele m numere. Date de ieșire Fișierul de ieșire potrivire.out va conține pe prima linie numărul S, reprezentând suma pe care o va câștiga Gigel. Restricții și precizări 1 ≤ n, m ≤ 100000 pentru 50% din teste, 1 ≤ n, m ≤ 1000 cele m numere visate sunt numere naturale și au cel mult cinci cifre Exemplu potrivire.in 10 4 5 6 2 6 0 7 1 9 7 6 456 662 2607 2607 97 975 potrivire.out 3160 Explicație Numerele distincte visate care se pot scrie cu cifre consecutive din șir sunt: 456, 2607 și 97, iar suma lor este 3160. 2607 a fost visat de două ori, dar se ia în considerare o singură dată.

Answer 1

#include <iostream>

#include <fstream>

using namespace std;

ifstream f("potrivire.in");

ofstream g("potrivire.out");

int n,m,i,j,k, v[100002], vc[100000], num, suma;

int main()

{

   f >> n;

   for (i=0; i<n; ++i)

       f >> v[i];

   for (i=0; i<n; ++i)

   {

       for (j=i; j<i+5 && j<n; ++j)

       {

           num=0;

           for (k=i; k<=j; ++k)

               num=num*10+v[k];

           vc[num]=1;

       }

   }

   f >> m;

   for (i=1; i<=m; ++i)

   {

       f >> num;

       if (vc[num])

       {

           suma=suma+num;

           vc[num]=0;

       }

   }

   g << suma;

}