# PBinfo #1963 – OP – Rezolvare C++

Sursa: Codul lui Andrei
Limbaj: C++
Autor rezolvare: deivid

## Enunț

Șcuțu este un mare matematician. Într-o seară acesta a inventat operația ∆. Operația ∆ se aplică pe 2 numere naturale, astfel:


290 ∆ 345 = 290345
21 ∆ 12 = 2112
456 ∆ 0 = 4560

Mygo și Seba sunt la rândul lor foarte buni informaticieni. Aceștia au un vector A cu N elemente, numere naturale, indexate de la 1. Ei vor construi un nou vector V, acesta la rândul său indexat de la 1, ce conține fiecare valoare A[i] ∆ A[j] (1 ≤ i, j ≤ N) pe care îl vor sorta crescător.

Cerința
Acum Șcuțu le va pune celor 2 câte două întrebări:

1. Câte valori din V sunt mai mici sau egale cu X ?
2. Pentru X dat, ce valoare se află pe poziția X ?

Să se răspundă la cele 2 întrebări.

Date de intrare
Fișierul de intrare op.in conține pe prima linie numărul t, având valoarea 1 sau 2, reprezentând tipul întrebării la care se cere răspunsul. Pe a doua linie linie se află numărul N și X iar pe a treia linie se vor afla N numere naturale nenule, reprezentând valorile vectorului A.

Date de ieșire
Fișierul de ieșire op.out va conține pe prima linie numărul S, reprezentând răspunsul întrebării.

Restricții și precizări

1 ≤ N ≤ 100.000
numerele de pe a treia linie a fișierului de intrare vor fi mai mici decât 1.000.000.000
t = 1 pentru 30p

Exemplu:
op.in

1
3 23
1 2 4
op.out

5
Explicație
V = {11, 12, 14, 21, 22, 24, 41, 42, 44}. Sunt 5 numere mai mici decât 23.

op.in

2
3 6
1 2 4
op.out

24
Explicație
V = {11, 12, 14, 21, 22, 24, 41, 42, 44}. Pe poziția 6 se află numărul 24.

## Cod sursă C++

```cpp
//Popa Bogdan Ioan, Colegiul National Aurel Vlaicu Orastie, clasa a 10-a
#include <bits/stdc++.h>
#define nmax 100002
#define ll long long
using namespace std;
ifstream fin("op.in");
ofstream fout("op.out");
int n;
int a[nmax];
int i;
ll K;
int t;
bool ok;
ll unesc(int a, int b)
{
    int p = log10(b) + 1;
    ll p10 = 1;
    while(p--)
        p10 *= 10;
    return (ll)a * p10 + b;
}
ll cnt(ll val, bool &ok)
{
    int i, j;
    ll ret = 0;
    for(i = 1, j = n; i <= n; i++)
    {
        while(j >= 1 && unesc(a[i], a[j]) > val)
            j--;
        if(!j)
            return ret;
        ret += j;
        if(unesc(a[i], a[j]) == val)
            ok = 1;
    }
    return ret;
}
ll rez(ll K)
{
    ll s = unesc(a[1], a[1]), d = unesc(a[n], a[n]), m = 0, best = 0;
    bool ok;
    while(s <= d)
    {
        m = (s + d) / 2;
        ok = 0;
        ll F = cnt(m, ok);
        if(F >= K)
        {
            if(ok)
            {
                if(F == K)
                    return m;
                best = m;
            }
            d = m - 1;
        }
        else s = m + 1;
    }
    return best;
}
int main()
{
    fin >> t >> n >> K;
    for(i = 1; i <= n; i++)
        fin >> a[i];
    sort(a + 1, a + n + 1);
    if(t == 1)
        fout << cnt(K, ok) << "\n";
    else
        fout << rez(K) << "\n";
    return 0;
}
```

## Resurse

- [Pagina originală](https://codulluiandrei.ro/rezolvari/pbinfo/1963)
- [Sursa C++](https://codulluiandrei.ro/rezolvari/pbinfo/1963/cod.cpp)
- [Sursa pe GitHub](https://raw.githubusercontent.com/codulluiandrei/pbinfo/main/pbinfo-1963/main.cpp)
- [Cursuri de informatică pentru BAC](https://codulluiandrei.ro/academia/info-curs/pachet-cpp/)