VA ROG NU IMI IESE NICICUM
Ș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.
Indicații de rezolvare :
Pentru a răspunde la o întrebare de tipul 1 se va folosi o funcție cnt(X) ce va da rezultatul corespunzător. Pentru a răspunde la întrebările de tipul 2 ne vom folosi de funcția cnt pentru a căuta binar rezultatul.
Răspunsuri la întrebare
Răspuns:
Explic#include <iostream>
#include <fstream>
#include <math.h>
#include<assert.h>
using namespace std;
ifstream in("nrin.txt");
ofstream out("nrout.txt");
int cnt(int x)
{
int n=0;
if(x==0)
n=1;
else
while(x!=0)
{
x=x/10;
n++;
}
return n;
}
int delta(int a,int b)
{
int q;
q=a*pow(10,cnt(b))+b;
return q;
}
int a[1000],v[1000];
int main()
{
int n,i,j,k=1,p,x,q=0;
in>>p;
in>>n>>x;
for(i=1; i<=n; i++)
in>>a[i];
for(i=1; i<=n; i++)
{
for(j=1; j<=n; j++)
{
v[k]=delta(a[i],a[j]);
k++;
}
}
if(p==1)
{
for(i=1; i<k; i++)
if(v[i]<x)
q++;
out<<q;
}
if(p==2)
{
assert(x<k);
out<<v[x];
}
return 0;
}
ație: