Imprimă pagina - 564 Rfinv

Titlul: 564 Rfinv
Scris de: Adrian Diaconu din Noiembrie 19, 2007, 00:07:40

Aici puteţi discuta despre problema Rfinv (http://infoarena.ro/problema/rfinv).

Titlul: Răspuns: 564 Rfinv
Scris de: Ionescu Vlad din Noiembrie 19, 2007, 21:58:13

Exista ceva cazuri particulare mai subtile? Am facut rezolvarea in O(n³) si iau incorect :eyebrow:

Titlul: Răspuns: 564 Rfinv
Scris de: Filip Cristian Buruiana din Noiembrie 19, 2007, 22:00:02

Ai grija sa verifica ca daca pentru o pereche (i j) nu exista nici un k pentru care distanta de la i la k + distanta de la k la j sa fie egala cu distanta de la i la j si nu ai muchie de la i la j in graful initial, atunci trebuie sa afisezi ca nu exista solutie.

Titlul: Răspuns: 564 Rfinv
Scris de: Ionescu Vlad din Noiembrie 19, 2007, 22:25:09

Pai, in solutia oficiala spune:

Citat

Pe fiecare muchie a grafului (i,j) se pune o distanta egala cu valoarea A[j] (A fiind matricea data). Se aplica apoi algoritmul Roy-Floyd pe acest graf, iar matricea distantelor obtinuta trebuie sa fie identica cu matricea distantelor data (in caz contrar neexistand solutie).

Eu asa am facut. Am mai pus si verificarea zisa de tine, dar tot incorect iau..

N-ar trebui sa ajunga doar pasii din solutia oficiala?

Titlul: Răspuns: 564 Rfinv
Scris de: Filip Cristian Buruiana din Noiembrie 19, 2007, 22:38:27

Eu am facut un pic altfel ( de fapt e acelasi lucru cu solutia oficiala dar e formulat altfel ):

* pentru fiecare pereche (i j) trebuie sa am A[ i ][ j ] <= A[ i ][ k ] + A[ k ][ j ] pentru orice k. Daca exista un k pt. care A[ i ][ k ] + A[ k ][ j ] < A[ i ][ j ] => nu am solutie
* daca exista o pereche (i j) pt. care nu exista nici un k a. i. A[ i ][ j ] = A[ i ][ k ] + A[ k ][ j ] si nu am muchie de la i la j in graf => nu am solutie

Eu am facut asa si am obtinut 100 :).

Titlul: Răspuns: 564 Rfinv
Scris de: Ionescu Vlad din Noiembrie 19, 2007, 23:44:39

Mi-a iesit pana la urma, mersi!

Titlul: Răspuns: 564 Rfinv
Scris de: Pripoae Teodor Anton din Martie 26, 2008, 22:53:48

solutia in n^4 nu intra in timp? (nici cea din articolul de solutii nu-mi intra)

Titlul: Răspuns: 564 Rfinv
Scris de: Maria Stanciu din Martie 27, 2008, 06:43:53

Intra un O(n^3) :). Ce faci tu in O(n^4)?

Titlul: Răspuns: 564 Rfinv
Scris de: Pripoae Teodor Anton din Martie 27, 2008, 11:49:28

fac exact ca in articolul de solutii

Citat

Vom sorta toate cele O(N2) distante din matrice in ordine crescatoare si vom initializa o matrice D[j]=infinit, pentru i <> j, respectiv 0, pentru i=j. Pe masura ce parcurgem sirul sortat al distantelor, vom actualiza valorile din matricea D. Sa presupunem ca am ajuns la o distanta avand valoarea x, ce reprezinta distanta minima dintre 2 noduri i si j. Daca D[j] < x sau D[j] > x si nu exista muchie in graf intre i si j, atunci nu avem solutie si ne oprim. Daca D[j] > x si exista muchie intre i si j, atunci vom pune pe aceasta muchie costul x. In continuare, va trebui sa actualizam valorile D[a] afectate de setarea valorii x pe muchia (i,j). Mai exact, pentru fiecare pereche de noduri (a,b), D[a] va fi egal cu minimul dintre valoarea actuala D[a] si min { D[a] + x + D[j], D[a][j] + x + D }.

Daca nu am intalnit nici o contradictie pe masura ce am parcurs muchiile, atunci raspunsul este "DA" ; in caz contrar, raspunsul este "NU".

am schimbat sortarea din qsort in sort din stl si acum merge in timp da imi da incorect...

puteti si voi sa puneti un test mai lung? ca nu ma prind ](*,)

Titlul: Răspuns: 564 Rfinv
Scris de: Bogdan-Alexandru Stoica din Martie 27, 2008, 13:38:44

Cod:

3
5 8
1 2
1 3
1 5
2 3
2 4
3 4
3 5
4 5
0 9 67 71 41 
98 0 165 169 139 
67 165 0 4 26 
71 169 4 0 30 
41 139 26 30 0 
6 8
1 4
1 5
2 3
2 4
3 4
3 5
4 6
5 6
0 39 9 80 6 82 
39 0 30 101 33 109 
9 30 0 71 3 79 
80 101 71 0 74 60 
6 33 3 74 0 76 
82 109 79 60 76 0 
7 16
1 2
1 4
2 4
2 5
2 6
2 7
3 4
3 5
3 6
3 7
4 5
4 6
4 7
5 6
5 7
6 7
0 28 57 56 52 62 72 
28 0 31 32 24 34 44 
57 31 0 1 7 17 27 
56 32 1 0 8 18 28 
52 24 7 8 0 10 20 
62 34 17 18 10 0 10 
72 44 27 28 20 10 0

raspunsurile sunt NU, DA, respectiv DA.

Titlul: Răspuns: 564 Rfinv
Scris de: Maria Stanciu din Martie 27, 2008, 14:56:22

Eu aveam o problema la rfinv pentru ca nu initializam matricea inainte de fiecare test si ramaneau in ea valori din testele anterioare. Vezi sa nu gresesti si tu asta :wink:

Titlul: Răspuns: 564 Rfinv
Scris de: Pripoae Teodor Anton din Martie 27, 2008, 22:51:49

mie imi da NU NU NU... tre sa mai lucrez la ea ](*,) si aia cu reinitializarea o aveam la inceput si nu imi mergea nici testu din enunt parca... dupaia am modificat si mi-a mers deci nu-i problema de la aia... da ciudat e ca am doua rezolvari (una in N^3 si una in N^4) care iau 0 puncte

LE: Cu cealalta sursa imi da NU DA DA dar iau 0 puncte :|

Cod:


for (k=0;k<nr;++k){
        xx=x[k];
        //printf("%d %d %d\n",x[k].val,x[k].i,x[k].j);
		if (d[ii[xx]][jj[xx]]>val[xx] && y[ii[xx]][jj[xx]]!=1 || d[ii[xx]][jj[xx]]<val[xx] && y[ii[xx]][jj[xx]]!=1){
           printf("NU\n");
           return;
        }
        if (d[ii[xx]][jj[xx]]>val[xx] && y[ii[xx]][jj[xx]]==1){
           d[ii[xx]][jj[xx]]=val[xx];
           for (a=0;a<n;++a)
               for (b=0;b<n;++b)
                      d[a][b]=min(d[a][b],min(d[a][ii[xx]] + val[xx] + d[jj[xx]][b], d[a][jj[xx]] + val[xx] + d[ii[xx]][b]));
        }
    }
    printf("DA\n");

asa fac... x este vectorul sortat iar d este matricea cu distantele. in val retin valoarea initiala in ii linia pe care se afla si in jj coloana

Titlul: Răspuns: 564 Rfinv
Scris de: Bogdan-Alexandru Stoica din Martie 28, 2008, 11:23:53

in principiu asa fac si eu. ai sortat perechile (i,j) din matricea initiala, crescator, dupa valoare?

Titlul: Răspuns: 564 Rfinv
Scris de: Pripoae Teodor Anton din Martie 28, 2008, 11:47:03

da... nu stiu sigur daca am implementat sort din stl bine (eu lucrez in c) da cu qsort nu intra in timp... cu asta intra dar imi da incorect

Titlul: Răspuns: 564 Rfinv
Scris de: Bogdan-Alexandru Stoica din Martie 28, 2008, 12:29:53

nu stiu ce sa zic. trimite-mi sursa ca pm.

Titlul: Răspuns: 564 Rfinv
Scris de: Petru Trimbitas din Iunie 19, 2010, 15:46:49

Ma poate ajuta cineva sa-mi spuna ce gresesc aici :

Cod:

#include <cstdio>
template <class T>
class pereche {
	public:
		int prim,ultim;

};

void rezolva() {
    pereche <int> muchii[2500];
    int i,j,k;
    int init[51][51],rez[51][51],n,m;
    scanf("%d %d",&n ,&m );
    ///<citire muchii>
    for(i=1; i<=m; i++)
        scanf("%d %d",&muchii[i].prim,&muchii[i].ultim);
    ///</citire muchii>
    for(i=1; i<=n; i++) for(j=1; j<=n; j++) scanf("%d",&rez[i][j]);//citire matr initiala
    for(i=1; i<=m; i++) {
        init[muchii[i].prim][muchii[i].ultim] = rez[muchii[i].prim][muchii[i].ultim];
        init[muchii[i].ultim][muchii[i].prim] = rez[muchii[i].prim][muchii[i].ultim];
    }
    ///<royfloyd>
    for (k = 1; k <= n; k++)
		for (i = 1; i <= n; i++)
			for (j = 1; j <= n; j++)
				if (init[i][k] && init[k][j] &&
				(init[i][j] > init[i][k] + init[k][j] || !init[i][j]) &&
				i != j)
                    init[i][j] = init[i][k] + init[k][j];
    ///</royfloyd>
    for(i=1; i<=n; i++) for(j=1; j<=n; j++)
        if(init[i][j]!=rez[i][j]) {
            printf("NU\n"); return;
        }
    printf("DA\n");

}

int main()
{
    int t,i;
    freopen("rfinv.in","r",stdin);
    freopen("rfinv.out","w",stdout);
    scanf("%d",&t);
    for(i=0; i<t; i++)
       rezolva();
    return 0;
}

Titlul: Răspuns: 564 Rfinv
Scris de: Dragos-Alin Rotaru din Iunie 19, 2010, 20:44:42

Initializeaza unde nu ai muchii in matricea init cu o valoare destul de mare (100000000), iar atunci cand faci roy-floyd fa asa :

Cod:

if (i != j && i != k && j != k)
           init[i][j] = min (init[i][j], init[i][k] + init[k][j])

Ar trebui sa mearga asa :D

Titlul: Răspuns: 564 Rfinv
Scris de: Petru Trimbitas din Iunie 19, 2010, 21:35:42

Nu merge ](*,)

Titlul: Răspuns: 564 Rfinv
Scris de: Dragos-Alin Rotaru din Iunie 19, 2010, 21:36:38

La initializare ai grija cand i == j sa pui init [ i ] [ j ] = 0 ?

Titlul: Răspuns: 564 Rfinv
Scris de: Nasturel Gabriel din Februarie 13, 2012, 10:47:16

Eu am rezolvat problema cu 2 foruri si 15 if-uri am luat maxim 100 de puncte. :banana: :banana: :banana:

Titlul: Răspuns: 564 Rfinv
Scris de: Elena Obreja din Noiembrie 11, 2013, 11:48:57

Imi poate explica, va rog, cineva care este motivul pentru care nu primesc punctaj pe sursa asta?

Cod:

#include<fstream>
using namespace std;
ifstream f("rfinv.in");
ofstream g("rfinv.out");
int t;
int n,m;
int a[51][51];
int b[51][51];
int i,j;
int x,y;
int ok;
int r;
int main()
{
    f>>t;
    for(int k=1;k<=t;k++)
    {
        ok=0;
        f>>n>>m;
        for(i=1;i<=n;i++)
         for(j=1;j<=n;j++)
          a[i][j]=b[i][j]=0;
        for(i=1;i<=m;i++)
        {
            f>>x>>y;
            a[x][y]=a[y][x]=1;
        }
        for(i=1;i<=n;i++)
        {
            for(j=1;j<=n;j++)
            {
                f>>r;
                b[i][j]=r;
            }
        }
        for(i=1;i<=n;i++)
         for(j=1;j<=n;j++)
          if((a[i][j]==0&&b[i][j]>0)||(a[i][j]>0&&b[i][j]==0))
              ok=1;
        if(ok==0)
          g<<"DA"<<"\n";
        else
          g<<"NU"<<"\n";
    }
    return 0;
}

Titlul: Răspuns: 564 Rfinv
Scris de: Trasca Andrei din Ianuarie 06, 2016, 00:41:10

Daca se mai uita cineva la problema aceasta, am si eu nevoie de ajutor. Imi merge pe ambele exemple(si cel din enunt si cel de la "fireatmyself") dar iau 0 puncte. Am incercat si metoda lui Dastas, merge pe exemple, dar tot 0 puncte iau ](*,)

Cod:

#include <iostream>
#include <stdio.h>
#define infile "rfinv.in"
#define outfile "rfinv.out"
#define N 51
#define inf 100001

using namespace std;

int c[N][N],n,m,t,a[N][N];

FILE * in=fopen(infile,"r");
FILE * out=fopen(outfile,"w");

void cit()
{
    fscanf(in,"%d %d\n",&n,&m);
    int i,j;
    for(i=1;i<=n;i++)
        for(j=i+1;j<=n;j++)
        {
            a[i][j]=a[j][i]=inf;
            c[i][j]=c[j][i]=inf;
        }
    for(i=1;i<=m;i++)
    {
        int x,y;
        fscanf(in,"%d %d",&x,&y);
        a[x][y]=a[y][x]=1;
    }
    for(i=1;i<=n;i++)
        for(j=1;j<=n;j++)
        {
            fscanf(in,"%d",&c[i][j]);
            if(a[i][j])
                a[i][j]=c[i][j];
        }
}

void roy_floyd()
{
    int i,j,k;
    for(k=1;k<=n;k++)
        for(i=1;i<=n;i++)
            for(j=1;j<=n;j++)
                if(i!=j && j!=k && i!=k)
                    a[i][j]=min(a[i][j],a[i][k]+a[k][j]);
}

bool sol2()
{
    int i,j,k,sw=0;
    for(i=1;i<=n;i++)
        for(j=1;j<=n;j++)
        {
            sw=0;
            for(k=1;k<=n;k++)
                {
                    if(c[i][j]>c[i][k]+c[k][j])
                        return 0;
                    if(c[i][j]==c[i][k]+c[k][j])
                        sw=1;
                }
            if(!sw && a[i][j]==inf)
                return 0;
        }
    return 1;
}

inline void verif()
{
    int i,j;
    for(i=1;i<=n;i++)
        for(j=1;j<=n;j++)
            if(a[i][j]!=c[i][j])
            {
                fprintf(out,"NU");
                return ;
            }
    fprintf(out,"DA");
}

int main()
{
    int i;
    fscanf(in,"%d\n",&t);
    for(i=1;i<=t;i++)
    {
        cit();
        roy_floyd();
        verif();
        /*if(sol2())
            fprintf(out,"DA");
        else
            fprintf(out,"NU");*/
        fprintf(out,"\n");
    }
    return 0;
}

Sol2 este solutia lui Dastas

Titlul: Răspuns: 564 Rfinv
Scris de: George Marcus din Ianuarie 06, 2016, 12:38:31

Cod:

if(a[i][j])

Conditia nu e tot timpul adevarata?

Incearca sa eviti pe viitor conditii formulate dubios. In loc de "if (x)", pune explicit "if (x > 0)".

Titlul: Răspuns: 564 Rfinv
Scris de: Trasca Andrei din Ianuarie 06, 2016, 23:19:02

Salut! Multumesc de raspuns, nu imi dadusem seama ca initializasem matricea cu infinit. O sa incerc sa vad daca acum merge, dar observ ca sunt probleme la compilator momentan.

Titlul: Răspuns: 564 Rfinv
Scris de: Trasca Andrei din Ianuarie 12, 2016, 23:09:09

Citat din mesajul lui: George Marcus din Ianuarie 06, 2016, 12:38:31

Cod:

if(a[i][j])

Conditia nu e tot timpul adevarata?

Incearca sa eviti pe viitor conditii formulate dubios. In loc de "if (x)", pune explicit "if (x > 0)".

Se pare ca tot 0 puncte iau, chiar si cu aceasta modificare. Nu pot sa imi dau seama care este problema

Titlul: Răspuns: 564 Rfinv
Scris de: George Marcus din Ianuarie 16, 2016, 19:27:48

Cod:

if(a[i][j]!=0 || a[i][j]!=inf)

Vezi conditia asta.

Titlul: Răspuns: 564 Rfinv
Scris de: Gheoace Mircea din Iunie 28, 2016, 11:04:01

Nu știu care este problem la rezolvarea mea: Am încercat cu ideea lui Filip

Citat din mesajul lui: Filip Cristian Buruiana din Noiembrie 19, 2007, 22:38:27

Și am mi-a rezultat asa:
# include <cstdio>
# include <cstring>
using namespace std;
FILE *f=fopen("rfinv.in","r"),*g=fopen("rfinv.out","w");
short n,m,t,i,j;
bool A[51][51],C[51][51];int B[51][51];
/*
A matrice de adiacenta in care A[j]=1 daca exista legatura intre i si j si 0 altfel
C matrice in care salvez 1 daca exista drum intre i si j sau costul dintre i si j poate fi descompus pe drumul i->k k->j
B matricea unde se afla rezultatul royfloyd din fisier
*/
bool royfloyd()
{
short i,j,k;
for(k=1;k<=n;++k)
for(i=1;i<=n;++i)
for(j=1;j<=n;++j)
            if(i!=j)
         {
if(B[j] > B[k]+B[k][j])
return 0;
            if(A[j] || B[j]==B[k]+B[k][j])
               C[j]=1;
         }
   for(i=1;i<=n;++i)
      for(j=1;j<=n;++j)
         if(i!=j)
            if(!C[j])//daca exista drum si nu nu este pe diag princ
               return 0;
   return 1;
}
template<class T>
void initMatrice(T A[][51])
{
for(i=0;i<n;++i)
memset(A,0,(n+1)*sizeof(T));
}
int main()
{
fscanf(f,"%hd",&t);
while(t--)
{
fscanf(f,"%hd %hd\n",&n,&m);
initMatrice(A);
      initMatrice(B);
      initMatrice(C);
short x,y;
for(i=0;i<m;++i)
{
fscanf(f,"%hd %hd\n",&x,&y);
A
[y]=A[y]
=1;
}
for(i=1;i<=n;++i)
         for(j=1;j<=n;++j)
            fscanf(f,"%d",B+j);
if(royfloyd())
fprintf(g,"DA\n");
else
fprintf(g,"NU\n");
}
}
Primesc mesajul Incorect

Titlul: Răspuns: 564 Rfinv
Scris de: Andronache Riccardo din Ianuarie 17, 2017, 20:00:49

Imi poate spune cineva unde gresesc de imi da testul " incorect " ? >.>
PS: Am luat multe teste cu solutia asta, daca aveti cazuri exceptate dati-mi-le.. Multumesc !

#include <bits/stdc++.h>
#define inf 1000001
using namespace std;

ifstream f("rfinv.in");
ofstream g("rfinv.out");

const int NMAX = 51;
int t, n, m, counter;
int a[NMAX][NMAX], c[NMAX][NMAX];

void citire()
{
f>>n>>m;

for(int i = 1; i<= n; i++)
for(int j =1; j <= n; j++)
{
if(i != j) a[j] = inf;
}

for(int i = 1; i <= m; i++)
{
int x, y;
f>>x>>y;
a
[y] = 1;
a[y]
= 1;
}

for(int i = 1; i <= n; i++)
for(int j = 1; j <=n; j++)
{
f>>c[j];
if(a[j] || a[j] == inf)
a[j] = c[j];
}
}

void roy_floyd()
{
int i, j, k;
for( k = 1; k <= n; k++)
for( i = 1; i <= n; i++)
for( j = 1; j <= n; j++)
if(i != j && i != k && j != k && a[j] > a[k] + a[k][j] && a[j] )
{
a[j] = a[k] + a[k][j];
counter++;
}
}

void afisare()
{
for(int i = 1; i <= n; i++)
{

for(int j = 1; j <= n; j++)
g<<a[j]<<" ";
g<<"\n";
}

}

int main()
{
f>>t;
for(int i = 1; i <= t; i++)
{
int greseli = 0;
counter = 0;
citire();
afisare();
g<<"\n";
roy_floyd();

if(counter != 0)
g<<"NU" <<"\n";
else
{
for(int i = 1; i <= n; i++)
for(int j = 1; j <= n; j++)
if(a[j] != c[j])
greseli++;
if(greseli != 0)
g<<"NU"<<"\n";
else g<<"DA"<<"\n";
}

}
return 0;
}

infoarena

infoarena - concursuri, probleme, evaluator, articole => Arhiva de probleme => Subiect creat de: Adrian Diaconu din Noiembrie 19, 2007, 00:07:40