049 Barbar

[u-92]

 tot 70.. WA pe 1,2 si 5  

[•fireatmyself]

In primu rand tu iei WA nu TLE, dar am "masurat" citirea ta pe un Celeron la 2.40 GHz si 256 MB RAM si dureaza, pentru testul, maxim 0.14. Mai testeaza-ti solutia. Uite, incearca p'astea :

Cod:

3 3
***
IDO
***

Cod:

4 4
....
....
IDO.
....

Pentru primu test raspunsul este 0, iar pentru al doilea raspunsul este 1.

Good luck.

[u-92]

pe primul imi da 0, pe al doilea 1.. si n-am zis ca iau TLE, insa cu prima citire caracter cu caracter luam 30 si daca citeam tot sirul luam 70 de asta am zis eu ca mi se pare dubios

[•fireatmyself]

Asta chiar e dubios rau... eu am incercat sa citesc caracter cu caracter si am luat 100. Daca vrei (doar daca nu te deranjeaza), da-mi solutia ta pe mail si ma uit peste ea ([email protected]).

[u-92]

nu ma deranjeaza deloc, o s-o pun aici poate mai are cineva de postat o idee
[ am scos sursa ... ]

daca scot alea din comentariu de la citire, iau 20 (am vazut acum).. totusi cele doua chestii nu sunt echivalente?

mersi.

[•fireatmyself]

in functia bf, in loc de :

Cod:

c[++sf].x = i + dx[k];
c[sf].y = j + dy[k];

pune

Cod:

c[sf].x = i + dx[k];
c[sf++].y = j + dy[k];

prima daca cand intra in "if", variabila "sf" este 1. tu mai introduci in coada (c[1]) pozitia (0, 0) ca vecin al lui (i, j) si acest lucru nu e intodeanuna adevarat.

uite testu pe care te-am prins   :

Cod:

6 5
...I.
.....
...O.
..***
...D.

tie iti da 3, iar corect este 6.
acum iei 100    si ai grija pe viitor, ca asa ceva te poate costa mult mai mult de 30 de puncte.

[u-92]

ca sa vezi ce greseam.. bug`urile astea..
mersi mah, sa traiesti  

[•fireatmyself]

n-ai pentru ce
tu esti Astronomy ?

[u-92]

na ca mi s-a dezvaluit identitatea  

[•fireatmyself]

[•alex_prg]

nu ma prind de problema .... ma gandesc ca trebuie construit un graf dar nam cum sa iau R*C noduri nu ? ... ma ajuta cineva ?

[•Coty]

OK ... ignorand multe WA ca stiu ca nu prea mi-am dat interesu sa o fac din prima bine... stit de la ce pot lua SIGABRT??? ( abort parca da doar userul daca vrea altfel e sigint)

[•Marius]

OK ... ignorand multe WA ca stiu ca nu prea mi-am dat interesu sa o fac din prima bine... stit de la ce pot lua SIGABRT??? ( abort parca da doar userul daca vrea altfel e sigint)

http://infoarena.devnet.ro/forum/index.php/topic,846.0.html

Eu am depasit memoria. Cred ca si tu ai facut acelasi lucru.

[•azotlichid]

Eu primeam SIGABRT cand accesam elemente negative ale unui vector si citeam/scriam in afara zonei de memorie alocata programului.

[•Coty]

OK ... ignorand multe WA ca stiu ca nu prea mi-am dat interesu sa o fac din prima bine... stit de la ce pot lua SIGABRT??? ( abort parca da doar userul daca vrea altfel e sigint)

http://infoarena.devnet.ro/forum/index.php/topic,846.0.html

Eu am depasit memoria. Cred ca si tu ai facut acelasi lucru.

am uitat de pagina asta sorry 

Cod:

struct point
{
        long x, y, v;
};

long R, C;
char A[MAX][MAX];
long V[MAX][MAX];
long B[MAX][MAX];

point mv[4] = {{-1,0},{1,0},{0,1},{0,-1}}; // vector of moves
queue <point> D;
point I, O;
long answer=0;

singura cu dimensiune variabila este coada... deci din pricina ei sa nu imi intre??? 

[•cos_min]

nush daca ii de la asta ... da intra si in int nu trebuie folosit long

[•Coty]

din cate stiu pe compilatoarele de 32 de biti, int == long... asa cum pe alea de 64 int == long long, nu?

[•Marius]

din cate stiu pe compilatoarele de 32 de biti, int == long... asa cum pe alea de 64 int == long long, nu?

Da. Eu folosesc Visual C++ si are compilator pe 32 de biti iar int == long. Cred ca e valabil si pentru cel de 64.

am uitat de pagina asta sorry 

Mi-a fost lene sa explic din nou si ti-am dat un link.

[•Robytzza]

care e faza cu ultimul test..am vazut ca este cu -1 ..insa nu vad ce gresesc..am pus conditia daca nu poate sa ajunga la final sa afiseze -1 ..si tot iau incorect (

Gata m rezolvat 100 <:-P ,ms Marius

[•Mishu91]

Flacarile dragonilor pot trece prin zid? Adica daca am ceva de genu

Cod:

D*.

Distana pana la celula libera e 2 sau e data de distanta pana la un alt dragon?

L.E. : mi-am dat seama ca dragonii nu-s destul de puternici ca sa trimita flacari prin zid

[•stocarul]

Am si eu o problema cu testele 7 si 9.
La 7 primesc Wrong answer!, iar la 9 Killed by signal 11(SIGSEGV).
As vrea si eu cele doua teste daca se poate
stocarul [at] yahoo.com
Multumesc:)

Am pus aici si sursa:

Cod:

#include <fstream>
using namespace std;
fstream in,out;
const int dx[] = {0,0,1,-1};
const int dy[] = {1,-1,0,0};
long r,c;
long i,j,k;
long m[1001][1001];
long b[1001][1001];
long di[1000001],dj[1000001],ds[1000001];
long d=0,t;
long x,y,x1,y1;
long l,h,ma;
long suma;
char v[1001];

int nr_max(long i,long j)
  {
  long x=0;
  x=m[i][j];
  for(int k=0;k<4;k++)
    if(0<i+dx[k]<=r && 0<j+dy[k]<=c && m[i+dx[k]][j+dy[k]]>x)
      x=m[i+dx[k]][j+dy[k]];
  return x;
  }
int nr_min(long x,long y)
  {
  if(x>y) return y;
  else return x;
  }
void umple(long i,long j,long x)
  {
  for(int k=0;k<4;k++)
    if(0<i+dx[k]<=r && 0<j+dy[k]<=c && m[i+dx[k]][j+dy[k]]>=x && b[i+dx[k]][j+dy[k]]==0)
      {
      b[i+dx[k]][j+dy[k]] = 1;
      umple(i+dx[k],j+dy[k],x);
      }
  }
void goleste()
  {
  long i,j;
  for(i=1;i<=r;i++)
    for(j=1;j<=c;j++)
      b[i][j]=0;
  }

int main()
{
in.open("barbar.in",ios::in);
out.open("barbar.out",ios::out);
in>>r>>c;
in.get();
for(i=1;i<=r;i++)
  {
  in.getline(v,c+2,'\n');
  for(j=0;j<c;j++)
    {
    if(v[j]=='.') m[i][j+1]=3000000;
    else if(v[j]=='*') m[i][j+1]=-1;
    else if(v[j]=='D')
      {
      m[i][j+1]=0;
      d++;
      di[d]=i;
      dj[d]=j+1;
      }
    else if(v[j]=='I')
      {
      m[i][j+1]=3000000;
      x=i;
      y=j+1;
      }
    else
      {
      m[i][j+1]=3000000;
      x1=i;
      y1=j+1;
      }
    }
  }
in.close();
t=d;
for(i=1;i<=t;i++)
  {
  suma = m[di[i]][dj[i]]+1;
  for(j=0;j<4;j++)
    if(0<di[i]+dx[j]<=r && 0<dj[i]+dy[j]<=c && m[di[i]+dx[j]][dj[i]+dy[j]]>suma)
      {
      m[di[i]+dx[j]][dj[i]+dy[j]] = suma;
      t++;
      di[t]=di[i]+dx[j];
      dj[t]=dj[i]+dy[j];
      }
  }

h=nr_min(nr_max(x,y),nr_max(x1,y1));
k=-1;
l=0;
while(l<=h)
  {
  if(l>0 || h>0) ma=(l+h)/2;
    else ma=0;
  umple(x,y,ma);
  if(b[x1][y1]==1)
    {
    k=ma;
    l=ma+1;
    }
  else
    h=ma-1;
  goleste();
  }
out<<k<<endl;
out.close();
return 0;
}

[•Mishu91]

In conditiile in care sursele nu se fac publice sansa sa le primesti e destul de mica dar ai grija la program sa nu in vre-un ciclu infinit(o data am primit park Killed by signal 11 pt asta)

L.E. : Nu am avut destula rabdare sa urmaresc sursa, dar am un sfat: knd faci o parcurgere in latime(i se mai zice si algorimul lui lee), foloseste un sir de constante pentru directii(e mai usor de scris si de urmarit)

Cod:

const int dx[] = {-1, 1, 0, 0},
          dy[] = { 0, 0, 1,-1};

Asa se declara, iar cand vrei sa vezi toti vecinii unui element faci

Cod:

for(int k=0; k<4; k++)
{
  ivec = iact + dx[k];
  jvec = jact + dy[k];
...
}

unde iact si jact sunt indicii elementului curent(caruia vrei sai afli vecinii), iar ivec si jvec sunt indicii elementelor vecine

[•fireatmyself]

[...]
L.E. : Nu am avut destula rabdare sa urmaresc sursa, dar am un sfat: knd faci o parcurgere in latime(i se mai zice si algorimul lui lee), foloseste un sir de constante pentru directii(e mai usor de scris si de urmarit)
[...]

nu se numeste algoritmul lui Lee (cum apare gresit in unele manuale de informatica), ci Breadth-first search .

[•Mishu91]

Pai am scris k i se mai zice algoritmul lui Lee (in mod gresit, in manualele de info), n-am zis k asa se si numeste 

[•stocarul]

In conditiile in care sursele nu se fac publice sansa sa le primesti e destul de mica dar ai grija la program sa nu in vre-un ciclu infinit(o data am primit park Killed by signal 11 pt asta)

L.E. : Nu am avut destula rabdare sa urmaresc sursa, dar am un sfat: knd faci o parcurgere in latime(i se mai zice si algorimul lui lee), foloseste un sir de constante pentru directii(e mai usor de scris si de urmarit)

Cod:

const int dx[] = {-1, 1, 0, 0},
          dy[] = { 0, 0, 1,-1};

Asa se declara, iar cand vrei sa vezi toti vecinii unui element faci

Cod:

for(int k=0; k<4; k++)
{
  ivec = iact + dx[k];
  jvec = jact + dy[k];
...
}

unde iact si jact sunt indicii elementului curent(caruia vrei sai afli vecinii), iar ivec si jvec sunt indicii elementelor vecine

Multumesc mult pentru aceasta idee. Nu m-am gandit ca se poate scrie si asa, si intradevar e mult mai usor de scris algoritmul. Multumesc inca o data

p.s. Si totusi, de ce i-au doar 80 pct?