Question

#1266 C++ (indicatii la final) dau 50 de puncte

Cerința
Se dă o matrice cu n linii şi m coloane ce conţine numere naturale astfel încât parcurgând matricea pe prima linie de la stânga la dreapta, pe a doua linie de la dreapta la stânga, pe a treia linie de la stânga la drepta, ş.a.m.d., toate elementele matricei vor forma un şir strict crescător. Fiind date p numere naturale ordonate strict crescător, să se afişeze pentru fiecare numărul liniei şi coloanei unde acesta se găseşte în matrice, respectiv 0 dacă acesta nu se găseşte în matrice.
Date de intrare
Fișierul de intrare cautanrinmatrice.in conține pe prima linie numerele n şi m reprezentând dimensiunile matricei , pe următoarele n linii câte m numere aranjate conform enunţului reprezentând elementele matricei, pe următoarea linie numărul p, iar pe ultima linie cele p numere în ordine strict crescătoare ce trebuie căutate în matrice.
Date de ieșire
Fișierul de ieșire cautanrinmatrice.out va conține pe primele p linii numărul liniei şi coloanei pe care se află în matrice fiecare din cele p numere date, respectiv 0 dacă numărul nu se găseşte în matrice.
Restricții și precizări
1 ≤ n , m ≤ 1000
elementele matricei sunt numere naturale mai mici decât 2.000.000.000
1 ≤ p ≤ 1.000.000
cele p numere vor fi mai mici decât 2.000.000.000


Exemplu
cautanrinmatrice.in
3 4
2 5 11 14
29 27 23 19
32 38 44 59
3
11 24 38
cautanrinmatrice.out
1 3
0
3 2
Explicație
Numărul 11 se află în matrice pe linia 1 coloana 3, numărul 24 nu se află în matrice, iar numărul 38 se află în matrice pe linia 3, coloana 2.

INDICATII: Se formeaza un sir crescator cu elementele matricei, parcursa conform enuntului, apoi pentru fiecare dintre cele p numere date se cauta BINAR daca se afla in sirul format. In functie de pozitia gasita in sir se deduce numarul liniei si al coloanei din matrice pe care se afla respectivul numar.

Answer 1

#include <fstream>

using namespace std;
ifstream f("cautanrinmatrice.in");
ofstream g("cautanrinmatrice.out");
int i , j  , x , a[1000008] , m , n , p , li , co , d , poz , mij ;

int caut( int st , int dr )
{
    if ( st > dr ) return 0 ;
    else {
           mij = ( st + dr ) / 2 ;
           if ( a [ mij ] == x ) return mij ;
           else if ( a [ mij ] < x ) return caut ( mij + 1 , dr ) ;
                                else return caut ( st , mij - 1 ) ;

         }
}

int main()
{
    f >> n >> m ;
    d = n * m ;
    for ( i = 1 ; i <= n ; i++ )
       if ( i % 2 == 1 ) for ( j = 1 ; j <= m ; j++ ) f >> a [ ( i - 1 ) * m + j ] ;
                    else for ( j = 1 ; j <= m ; j++ ) f >> a [ i * m - j + 1 ] ;
    f >> p ;
    for ( i = 1 ; i <= p ; i++ )
    {
        f >> x;
        poz = caut(1,d) ;
        if ( poz==0 ) g << 0 << "\n" ;
              else
              {
                  if( poz%m==0 ){ li = poz / m ; co = m ; }
                           else { li = poz /m + 1 ; co = poz % m ; }
                  if( li%2==1 ) g << li << " " << co << "\n" ;
                           else g << li << " " << m - co + 1 << "\n" ;
              }
    }

    return 0 ;
}