Cod sursa(job #2972067)

Utilizator PuskaPalfi Viktoria Tunde Puska Data 28 ianuarie 2023 17:07:05
Problema Rj Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 12.11 kb
#include <iostream>
#include <fstream>

using namespace std;

int R[102][102], J[102][102], sorR[100000], oszlopR[100000], sorJ[100000], oszlopJ[100000];

//int w[1001], v[1001];
//int d[151];
//bool prime(int x){
//    if(x==0 || x==1) return false;
//    else if(x==2) return true;
//    else if(x%2==0) return false;
//    else{
//        for(int i=3; i*i<=x; i+=2)
//            if(x%i==0) return false;
//    }
//    return true;
//}

//int n, k=0, x, d[100001], p;
//
//int kereses(int x, int n){
//    int st=1, dr=n;
//    while(st<=dr){
//        int m=(st+dr)/2;
//        if(d[m]>x) dr=m-1;
//        else st=m+1;
//    }
//    return st;
//}


int main()
{
//    int maxi, maxmax=0, n, k, db=0, mini, poz=0;
//    cin>>n;
//    for(int i=1; i<=n; i++) {
//        cin>>k;
//        if(prime(k)) v[++db]=k;
//    }
//    for(int i=db; i>=1; i--){
//        maxi=0;
//        for(int j=i+1; j<=db; j++){
//            if(v[i]<=v[j])
//                if(maxi<=w[j]) maxi=w[j];
//        }
//        w[i]=maxi+1;
//        if(maxmax<w[i]) maxmax=w[i];
//    }
//    cout<<endl<<maxmax<<endl;
//    v[poz]=-1;
//    for(int i=maxmax; i>=1; i--){
//        mini=1000000;
//        for(int j=poz+1; j<=db; j++){
//            if(mini>v[j] && maxmax==w[j] && v[j]>=v[poz]) mini=v[j], k=j;
//        }
//        cout<<v[k]<<" ";
//        poz=k;
//        maxmax--;
//    }

    ///1385
//    ifstream f("joc.in");
//    ofstream g("joc.out");
//    int n, v[151][151], s1=0, s2=s1, k;
//    f>>n;
//    for(int i=1; i<=n; i++)
//        for(int j=1; j<=n; j++)
//            f>>v[i][j];
//    for(int i=1; i<=n; i++){
//        if(i%2!=0){
//            k=1, d[k]=v[i][1];
//            for(int j=2; j<=n; j++){
//                if(v[i][j]>=d[k]) d[++k]=v[i][j];
//                else{
//                    int st=1, dr=k, poz=k+1;
//                    while(st<=dr){
//                        int m=(st+dr)/2;
//                        if(d[m]>v[i][j]) poz=m, dr=m-1;
//                        else st=m+1;
//                    }
//                    d[poz]=v[i][j];
//                }
//            }
//            s1+=k;
//        }
//        else{
//            k=1, d[k]=v[i][1];
//            for(int j=2; j<=n; j++){
//                if(v[i][j]<=d[k]) d[++k]=v[i][j];
//                else{
//                    int st=1, dr=k, poz=k+1;
//                    while(st<=dr){
//                        int m=(st+dr)/2;
//                        if(d[m]<v[i][j]) poz=m, dr=m-1;
//                        else st=m+1;
//                    }
//                    d[poz]=v[i][j];
//                }
//            }
//            s2+=k;
//        }
//    }
//    g<<s1<<" "<<s2<<endl;
//    if(s1>s2) g<<"UNU";
//    else if(s1<s2) g<<"DOI";
//    else g<<"REMIZA";


    ///#2242--100p
//    cin>>n;
//    for(int i=1; i<=n; i++){
//        cin>>x;
//        p = kereses(x, k);
//        if(d[p]<=x) k++, p=k;
//        d[p]=x;
//    }
//    cout<<n-k;

    ///508
//    int n, m, x[25001], k;
//    cin>>n;
//    for(int i=1; i<=n; i++) cin>>x[i];
//    cin>>m;
//    for(int i=1; i<=m; i++){
//        cin>>k;
//        int st=1, dr=m;
//        bool t=false;
//        while(st<=dr && !t){
//        	int l=(st+dr)/2;
//            if(x[l]==k) t=true;
//            else if(x[l]<k) st=l+1;
//            else dr=l-1;
//        }
//        if(t) cout<<1<<' ';
//        else cout<<0<<' ';
//    }

    ///
//    int n, m;
//    ifstream f("vektorok.in");
//    f>>n>>m;
//    n+=2; m+=2;
//    for(int i=3; i<=n; i++) f>>a[i][1];
//    for(int i=3; i<=m; i++) f>>a[1][i];
//
//    for(int i=1; i<=n; i++){
//        for(int j=1; j<=m; j++)
//            cout<<a[i][j]<<" ";
//        cout<<endl;
//    }
//
//    for(int i=3; i<=n; i++){
//        for(int j=3; j<=m; j++){
//            if(a[i][1]==a[1][j]){
//                a[i][j]=a[i-1][j-1]+1;
//            }
//            else{
//                a[i][j]=max(a[i-1][j], a[i][j-1]);
//            }
//        }
//    }
//
//    cout<<endl;
//    for(int i=1; i<=n; i++){
//        for(int j=1; j<=m; j++)
//            cout<<a[i][j]<<" ";
//        cout<<endl;
//    }

//    int v[a[n][m]+1], p, oszlop=3, db=0;
//    v[0]=0;
//    bool t;
//    for(int i=3; i<=n; i++){
//        t=true;
//        for(int j=i; j<=m && t; j++){
//            p=a[i][j];
//            if(a[i][1]==a[1][j]){
//                if(v[p-1]<a[i][1]){
//                    v[p]=a[i][1];
//                    oszlop=j;
//                    t=false;
//                    db=p;
//                }
//                else if(oszlop>=j){
//                    v[p-1]=a[i][1];
//                    oszlop=j;
//                    t=false;
//                    db=p;
//                }
//            }
//        }
//    }

//    int i=n, j=m, v[a[n][m]+1], p=1;
//    while(i>=3 && j>=3){
//        if(a[1][j]==a[i][1]){
//            v[p++]=a[1][j];
//            i--; j--;
//        }
//        else{
//            if(a[i-1][j]>a[i][j-1]) i--;
//            else j--;
//        }
//    }
//    for(int i=1; i<p; i++) cout<<v[i]<<" ";

//    int v[15], d[20], n=12;
//    for(int i=1; i<=n; i++) cin>>v[i];
//    int k=1;
//    d[k]=v[1];
//            for(int i=2; i<=n; i++){
//                if(v[i]>=d[k]) d[++k]=v[i];
//                else{
//                    int st=1, dr=k, poz=k+1;
//                    while(st<=dr){
//                        int m=(st+dr)/2;
//                        if(d[m]>v[i]) poz=m, dr=m-1;
//                        else st=m+1;
//                    }
//                    d[poz]=v[i];
//                }
//            }
//    for(int i=1; i<=k; i++) cout<<d[i]<<" ";

    ///egeres program
//    int n, m;
//    ifstream f("eger.in");
//    f>>n>>m;
//    for(int i=0; i<=n+1; i++) a[0][i]=a[n+1][i]=1;
//    for(int i=0; i<=m+1; i++) a[i][0]=a[i][m+1]=1;
//    for(int i=1; i<=n; i++)
//        for(int j=1; j<=m; j++)
//            f>>a[i][j];
//    a[1][1]=1;
//    for(int i=0; i<=n+1; i++){
//        for(int j=0; j<=m+1; j++)
//            cout<<a[i][j]<<" ";
//        cout<<endl;
//    }
//    cout<<endl;
//    int i=1, j=1, p=1, akt=1;
//    a[i][j]=1;
//    while(akt<=p){
//        if(a[i-1][j]==0) sor[p]=i-1, oszlop[p]=j, p++, a[i-1][j]=a[i][j]+1;
//        if(a[i][j+1]==0) sor[p]=i, oszlop[p]=j+1, p++, a[i][j+1]=a[i][j]+1;
//        if(a[i+1][j]==0) sor[p]=i+1, oszlop[p]=j, p++, a[i+1][j]=a[i][j]+1;
//        if(a[i][j-1]==0) sor[p]=i, oszlop[p]=j-1, p++, a[i][j-1]=a[i][j]+1;
//        i=sor[akt];
//        j=oszlop[akt];
//        akt++;
//    }
//    int h=a[n][m], k=n, l=m;
//    while(h!=1){
//        h--;
//        if(a[k-1][l]==h) cout<<k<<" "<<l<<endl, k--;
//        else if(a[k][l+1]==h) cout<<k<<" "<<l<<endl, l++;
//        else if(a[k+1][l]==h) cout<<k<<" "<<l<<endl, k++;
//        else if(a[k][l-1]==h) cout<<k<<" "<<l<<endl, l--;
//    }

    ///1795
//    int n, m, kezd, veg, erkx, erky, k;
//    ifstream f("gigelajungeacasa.in");
//    ofstream g("gigelajungeacasa.out");
//    f>>n>>m>>k;
//    f>>erkx>>erky;
//    f>>kezd>>veg;
//    int l, s;
//    f>>l>>s;
//    a[l][s]=-1;
//    f>>l>>s;
//    a[l][s]=-1;
//    for(int i=1; i<=k; i++){
//        f>>l>>s;
//        a[l][s]=-1;
//    }
//
//    for(int i=0; i<=n+1; i++) a[0][i]=a[n+1][i]=1;
//    for(int i=0; i<=m+1; i++) a[i][0]=a[i][m+1]=1;
//
//    int i=kezd, j=veg, p=1, akt=1;
//    bool t=true;
//    while(t){
//        if(a[i-1][j]==0) sor[p]=i-1, oszlop[p]=j, p++, a[i-1][j]=a[i][j]+1;
//        if(a[i-1][j+1]==0) sor[p]=i-1, oszlop[p]=j+1, p++, a[i-1][j+1]=a[i][j]+1;
//        if(a[i][j+1]==0) sor[p]=i, oszlop[p]=j+1, p++, a[i][j+1]=a[i][j]+1;
//        if(a[i+1][j+1]==0) sor[p]=i+1, oszlop[p]=j+1, p++, a[i+1][j+1]=a[i][j]+1;
//        if(a[i+1][j]==0) sor[p]=i+1, oszlop[p]=j, p++, a[i+1][j]=a[i][j]+1;
//        if(a[i+1][j-1]==0) sor[p]=i+1, oszlop[p]=j-1, p++, a[i+1][j-1]=a[i][j]+1;
//        if(a[i][j-1]==0) sor[p]=i, oszlop[p]=j-1, p++, a[i][j-1]=a[i][j]+1;
//        if(a[i-1][j-1]==0) sor[p]=i-1, oszlop[p]=j-1, p++, a[i-1][j-1]=a[i][j]+1;
//        i=sor[akt];
//        j=oszlop[akt];
//        akt++;
//        if(i==erkx && j==erky) t=false;
//    }
//    g<<a[erkx][erky];
//    g.close();

    ///alee -100p
//    int n, m, x, y;
//    ifstream f("alee.in");
//    ofstream g("alee.out");
//    f>>n>>m;
//    for(int i=0; i<=n+1; i++) a[0][i]=a[n+1][i]=a[i][0]=a[i][n+1]=1;
//    for(int i=1; i<=m; i++){
//        f>>x>>y;
//        a[x][y]=-1;
//    }
//    int kezd, veg, erkx, erky, i, j, akt=1, p=1;
//    f>>kezd>>veg>>erkx>>erky;
//    a[kezd][veg]=1;
//    i=kezd; j=veg;
//    bool t=true;
//    while(t){
//        if(a[i-1][j]==0) sor[p]=i-1, oszlop[p]=j, p++, a[i-1][j]=a[i][j]+1;
//        if(a[i][j+1]==0) sor[p]=i, oszlop[p]=j+1, p++, a[i][j+1]=a[i][j]+1;
//        if(a[i+1][j]==0) sor[p]=i+1, oszlop[p]=j, p++, a[i+1][j]=a[i][j]+1;
//        if(a[i][j-1]==0) sor[p]=i, oszlop[p]=j-1, p++, a[i][j-1]=a[i][j]+1;
//        i=sor[akt];
//        j=oszlop[akt];
//        akt++;
//        if(i==erkx && j==erky) t=false;
//    }
//    g<<a[erkx][erky];
//    g.close();

    ///2390-rj
    ifstream f("rj.in");
    ofstream g("rj.out");
    int n, m, xR, yR, xJ, yJ;
    char k;
    f>>n>>m;
    for(int i=0; i<=n+1; i++) R[0][i]=R[n+1][i]=J[0][i]=J[n+1][i]=1;
    for(int i=0; i<=m+1; i++) R[i][0]=R[i][m+1]=J[i][0]=J[i][m+1]=1;
    f.get(k);
    for(int i=1; i<=n; i++){
        for(int j=1; j<=m; j++){
            f.get(k);
            if(k=='X') R[i][j]=J[i][j]=-1;
            if(k==' ') R[i][j]=J[i][j]=0;
            if(k=='R') R[i][j]=1, xR=i, yR=j;
            if(k=='J') J[i][j]=1, xJ=i, yJ=j;
        }
        f.get(k);
    }

    int pR=1, pJ=1, akt=1;
    while(akt<=pR){
            ///Romeo utja
        if(R[xR-1][yR]==0) sorR[pR]=xR-1, oszlopR[pR]=yR, pR++, R[xR-1][yR]=R[xR][yR]+1;
        if(R[xR-1][yR+1]==0) sorR[pR]=xR-1, oszlopR[pR]=yR+1, pR++, R[xR-1][yR+1]=R[xR][yR]+1;
        if(R[xR][yR+1]==0) sorR[pR]=xR, oszlopR[pR]=yR+1, pR++, R[xR][yR+1]=R[xR][yR]+1;
        if(R[xR+1][yR+1]==0) sorR[pR]=xR+1, oszlopR[pR]=yR+1, pR++, R[xR+1][yR+1]=R[xR][yR]+1;
        if(R[xR+1][yR]==0) sorR[pR]=xR+1, oszlopR[pR]=yR, pR++, R[xR+1][yR]=R[xR][yR]+1;
        if(R[xR+1][yR-1]==0) sorR[pR]=xR+1, oszlopR[pR]=yR-1, pR++, R[xR+1][yR-1]=R[xR][yR]+1;
        if(R[xR][yR-1]==0) sorR[pR]=xR, oszlopR[pR]=yR-1, pR++, R[xR][yR-1]=R[xR][yR]+1;
        if(R[xR-1][yR-1]==0) sorR[pR]=xR-1, oszlopR[pR]=yR-1, pR++, R[xR-1][yR-1]=R[xR][yR]+1;
        xR=sorR[akt];
        yR=oszlopR[akt];
        akt++;
    }
    akt=1;
    while(akt<=pJ){
        ///Julia utja
        if(J[xJ-1][yJ]==0) sorJ[pJ]=xJ-1, oszlopJ[pJ]=yJ, pJ++, J[xJ-1][yJ]=J[xJ][yJ]+1;
        if(J[xJ-1][yJ+1]==0) sorJ[pJ]=xJ-1, oszlopJ[pJ]=yJ+1, pJ++, J[xJ-1][yJ+1]=J[xJ][yJ]+1;
        if(J[xJ][yJ+1]==0) sorJ[pJ]=xJ, oszlopJ[pJ]=yJ+1, pJ++, J[xJ][yJ+1]=J[xJ][yJ]+1;
        if(J[xJ+1][yJ+1]==0) sorJ[pJ]=xJ+1, oszlopJ[pJ]=yJ+1, pJ++, J[xJ+1][yJ+1]=J[xJ][yJ]+1;
        if(J[xJ+1][yJ]==0) sorJ[pJ]=xJ+1, oszlopJ[pJ]=yJ, pJ++, J[xJ+1][yJ]=J[xJ][yJ]+1;
        if(J[xJ+1][yJ-1]==0) sorJ[pJ]=xJ+1, oszlopJ[pJ]=yJ-1, pJ++, J[xJ+1][yJ-1]=J[xJ][yJ]+1;
        if(J[xJ][yJ-1]==0) sorJ[pJ]=xJ, oszlopJ[pJ]=yJ-1, pJ++, J[xJ][yJ-1]=J[xJ][yJ]+1;
        if(J[xJ-1][yJ-1]==0) sorJ[pJ]=xJ-1, oszlopJ[pJ]=yJ-1, pJ++, J[xJ-1][yJ-1]=J[xJ][yJ]+1;
        xJ=sorJ[akt];
        yJ=oszlopJ[akt];
        akt++;
    }
    int talix, taliy, t=n*m;
    for(int i=1; i<=n; i++){
        for(int j=1; j<=m; j++){
            if(R[i][j]==J[i][j])
                if(t>R[i][j] && R[i][j]>0)
                    talix=i, taliy=j, t=R[i][j];
        }
    }
//    for(int i=1; i<=n; i++){
//        for(int j=1; j<=m; j++)
//            cout<<R[i][j]<<" ";
//        cout<<endl;
//    }
//    cout<<endl;
//    for(int i=1; i<=n; i++){
//        for(int j=1; j<=m; j++)
//            cout<<J[i][j]<<" ";
//        cout<<endl;
//    }
    g<<t<<" "<<talix<<" "<<taliy;
    g.close();


    return 0;
}