infoarena

infoarena - concursuri, probleme, evaluator, articole => Arhiva de probleme => Subiect creat de: Mircea Pasoi din Mai 23, 2005, 14:16:32



Titlul: 064 Cobai
Scris de: Mircea Pasoi din Mai 23, 2005, 14:16:32
Aici puteţi discuta despre problema Cobai (http://infoarena.ro/problema/cobai).


Titlul: 064 Cobai
Scris de: Bogdan-Cristian Tataroiu din Mai 25, 2005, 13:03:51
Am trimis exact aceeasi rezolvare, dar cu doua afisari: una cu int-uri si una cu float-uri si am obtinut 40 puncte pt cea cu int-uri si 25 puncte cu cea cu float-uri. V-as recomanda sa faceti si pentru aceasta problema un evaluator care acorda punctaj pentru un test daca diferenta absoluta intre rezultatul dat de programul evaluat si cel oficial este mai mica sau egala cu 0.01.


Titlul: 064 Cobai
Scris de: Mircea Pasoi din Mai 25, 2005, 13:58:25
Pai cam asta face verificatorul la problema asta.


Titlul: 064 Cobai
Scris de: cristi8 din Mai 25, 2005, 14:56:39
cobaiul nu ar trebui sa poata trece prin camera de unde incepe ?

..oricum, iau doar 70 si nu ma prind unde gresesc.. puteti sa-mi ziceti testul 7 de exemplu ? pe toate testele "de mana" care le-am dat a mers, zic eu, bine..


Titlul: 064 Cobai
Scris de: Bogdan-Cristian Tataroiu din Mai 25, 2005, 15:00:47
Nu poate trece prin camera de unde incepe. Scrie in enunt ca dupa ce cobaiul pleaca din camera, biologul o inchide.
PS: Scuze pentru primul post. Aveam impresia ca din cauza asta nu merge afisarea cu float-uri.


Titlul: 064 Cobai
Scris de: cristi8 din Mai 25, 2005, 15:40:28
da.. asa e.. nu vazusem...

am mai dat mai multe teste, si chiar nu gasesc gresala.. am citit si enuntul de cateva ori, si sursa ... dar nu gasesc nimic.

 [-o<  va rog, dati-mi si mie testul 7 macar

~~~~~
EDIT: gata.. am luat 100... pusesem char in loc de int la o matrice  ](*,)


Titlul: Teste
Scris de: Filip Cristian Buruiana din Iunie 15, 2005, 16:42:14
In legatura cu testele care nu merg... Tot iau 75 la asta desi am implementat-o de ceva ori si toate testele pe care le dau imi merg... Si eu am folosit matrici, dar care sunt binare (deci la mine un char este suficient).... Nu stiu ce are (inchid si camera initiala dupa primul pas)

 
                                          bubbleSORT


Titlul: MDA...
Scris de: Filip Cristian Buruiana din Iunie 15, 2005, 17:14:44
Nu merge... chiar nu merge...  :(


Titlul: Re: Teste
Scris de: Mircea Pasoi din Iunie 15, 2005, 17:15:56
Citat din mesajul lui: filipb
In legatura cu testele care nu merg... Tot iau 75 la asta desi am implementat-o de ceva ori si toate testele pe care le dau imi merg... Si eu am folosit matrici, dar care sunt binare (deci la mine un char este suficient).... Nu stiu ce are (inchid si camera initiala dupa primul pas)

  NU VREAU SA DERANJEZ PE CINEVA K INTREB AICI ( [-( ), dar altundeva nu am unde ( nu am vazut ). Pt. probema "PETRICA"... Pur si simplu e ciudat... Iau 10 puncte desi pe toate testele pe care le dau imi da raspunsul bun.... Si am dat vreo 10 teste cat mai diferite... E si mai ciudat k nu imi da raspunsul nici macar la primul test unde banuiesc ca N e destul de mic deci ar trebui sa mearga daca si mie imi merge pe toate testele pe care le dau... M-am uitat... Am facut si afisarea bine (adik am respectat tipurile care intervin)... F. CIUDAT! ( SI F ENERVANT  :cry: ). CUM AS PUTEA SA FAC SI EU ROST DE UN TEST MACAR? ( de primul test)... Daca se poate asa ceva... MS MULT ( si un topic si pt problema asta, desi e f. veche in arhiva )
 
                                          bubbleSORT


La cobai, esti sigur ca inchizi camera din care pleaca?
Cat despre petrica, exista un topic deja, doar ca e pe pagina 2 (daca ai fi dat un search pe forum l-ai fi gasit!) Testele folosite pentru evaluare nu pot fi facute publice, citeste regulile.


Titlul: Sorry
Scris de: Filip Cristian Buruiana din Iunie 15, 2005, 17:26:15
Sorry... nici nu mi-am dat seama k este si o pagina a doua...  :oops: Da... dupa ce fac initializarile, in camera cu '*' pun '+'....


Titlul: 064 Cobai
Scris de: andreit1 din Iunie 15, 2005, 20:47:43
Si eu sunt cam in aceeasi situatie. dar ma gandesc ca daca sunt cativa cu maxim inseamna ca noi suntem de vina. daca gasesti cumva greseala sa imi zici si mie ca vad ca avem acelesi punctaj.


Titlul: 064 Cobai
Scris de: andreit1 din Iulie 11, 2005, 20:03:34
Totusi ce are testul 2( de exemplu) diferit de celelalte? Am citit si recitit problema de o gramada de ori( la fel si sursa) si am incercat mai multe citiri si abordari... nu inteleg de ce iau doar 75. Camera din care incepe am inchis-o....


Titlul: teste
Scris de: vladut.forum din Iulie 14, 2005, 11:42:18
Mah, care poate sa-mi de-a si mie niste teste, si raspunsu corect... Ca nustiu de ce nu iau 100 iau numa 15... Doar fac exact cum imi zice problema... Ma duc din punctu de start cu prima directie, apoi din toate punctele noi plec pe urmatoarea directie si tot asa...


Titlul: 064 Cobai
Scris de: andreit1 din Iulie 14, 2005, 11:53:55
Eu luasem din cauza preciziei 75/100. 15 puncte e cam putin. Probabil ai gresit ceva la implementare. Ai grija ca trebuie sa faca cel putin un pas dupa fiecare schimbare de directie si vezi sa inchizi camera din care pleaca.


Titlul: 064 Cobai
Scris de: vladut.forum din Iulie 14, 2005, 12:39:47
da mah, inchid camera, si fac cel putin un pas..ca daca nu fac iau 0.. o fi oare din cauza precizei.. io fac asa cu int-urui. a=nr de casute in care poate ajunge... si b= numarul de casute albe
afisez a*100/b, apoi iau restu a*100)%b si aflu urmatoarele doua cifre


Titlul: 064 Cobai
Scris de: andreit1 din Iulie 14, 2005, 12:44:35
Eu cu fprintf(fo,"%0.2f\n",(float)bune/tot*100) am luat 75


Titlul: 064 Cobai
Scris de: Iorgulescu Calin din Iulie 19, 2005, 23:47:54
Salut!
Si eu iau tot 75/100. Rationamentul sper ca e corect, asa ca ma gandesc ca ar putea fi tot de la precizie. Eu fac tot cu printf. De curiozitate, tu cum ai facut sa nu mai fie problema de precizie?


Titlul: 064 Cobai
Scris de: Bogdan-Cristian Tataroiu din Iulie 20, 2005, 09:01:14
Eu am calculat rezultatul in doua long-uri (unul pt partea intreaga si unul pt partea fractionara):
Cod:
    long sol1 = nr * 100 / nrpos;
    long sol2 = nr * 10000 / nrpos - sol1 * 100;
    printf("%d.%02d\n", sol1, sol2);


Titlul: 064 Cobai
Scris de: Iorgulescu Calin din Iulie 20, 2005, 14:01:05
Mersi mult! Am luat 100 acum. Dar totusi de ce nu mergea cu printf? Rontujea rezultatul sau de ce? Oricum mersi de idee. =D>


Titlul: Raspuns: 064 Cobai
Scris de: Toma Radu din Iunie 11, 2006, 12:22:33
Care ar fi complexitatea la problema asta? Io am facut asa : la fiecare modificare de directie, pun intr-o coada toate pozitiile in care poate ajunge si la urmatoarea schimbare de directie expandez punctele din coada. este ceva mai rapid?


Titlul: Raspuns: 064 Cobai
Scris de: Filip Cristian Buruiana din Iunie 12, 2006, 17:52:37
O(N*M*K) este suficient. Abordarea ta e buna...


Titlul: Raspuns: 064 Cobai
Scris de: Codrea Marcel din Iunie 14, 2006, 21:58:09
da calinux,e vorba de rotunjiri
pt float s=2.999 si printf("%0.2f",s) afiseaza 3.00
si eu m-am prins cam tarziu  ](*,)


Titlul: Raspuns: 064 Cobai
Scris de: Bondane Cosmin din Februarie 07, 2007, 13:08:49
Scuzati cat va da pe testul :

Citat
5 5
*....
.....
.....
.....
.....
SEV

Ms.


Titlul: Raspuns: 064 Cobai
Scris de: Savin Tiberiu din Februarie 07, 2007, 13:12:02
mie imi da 66.66


Titlul: Răspuns: 064 Cobai
Scris de: Andrei Homorodean din Iulie 12, 2007, 09:24:33
Problema asta este una dintre cele mai interesante: iei 5 puncte daca nu afisezi nimic!   \:D/


Titlul: Răspuns: 064 Cobai
Scris de: Ionescu Robert Marius din Martie 11, 2008, 09:36:06
imi zice si mie cineva de ce pe testul de mai sus da 66.66  :?


Titlul: Răspuns: 064 Cobai
Scris de: Bozianu Ana din August 16, 2008, 19:04:23
Imi cer scuze daca spun banalitati dar consider ca e vorba de informatii utile pentru cei care ajung in situatia frustranta de a rezolva corect o problema si intampina dificultati la afisarea numerelor reale datorita preciziei.

Fie p variabila de tip double calculata corect. Sa se afiseze cu 2 zecimale fara rotunjire.

Varianta utilizata de mine :

.....
#include<math.h>
....
double p;
....
p=floor(100*p)/100;
printf("%.2lf",p);
.....


@robytzza

initial
*....
.....
.....
.....
.....
se aplica S =>
+....
*....
*....
*....
*....
se aplica E =>
+....
.****
.****
.****
.****
se aplica V =>
+....
****.
****.
****.
****.
 deci cobaiul poate sa ajunga in 16 camere din cele 24 posibile (cea din care a plecat se inchide dupa iesirea cobaiului )
Deci probabilitatea e 16/ 24 *100% = 66.(6) % care afisat cu 2 zecimale da 66.66 %


Titlul: Răspuns: 064 Cobai
Scris de: Rusu Radu din Decembrie 27, 2010, 12:18:59
Destul de ciudata treaba:
Cu precizie de 0.01 iau 75
Cu precizie de 0.001 iau 90
cu precizie de 0.000001 iau 100
Avanda in vedere ca precizia ceruta acolo e 0.01 e cam ciudat :D


Titlul: Răspuns: 064 Cobai
Scris de: Finaru Andrei Emanuel din Ianuarie 24, 2011, 19:27:53
Eu si cu 2 zecimale, si cu 6 zecimale afisate, tot 75 iau. Imi poate cineva da un test propriu mai mare ca sa-mi dau seama ce caz nu prind? De mentionat ca nu am TLE, deci programul nu cicleaza.


Titlul: Răspuns: 064 Cobai
Scris de: Simoiu Robert din Ianuarie 24, 2011, 19:35:25
Cod:
10 10
..........
.+.+..+++.
+....+.+..
.++.*....+
...+.+.+.+
......+...
.+.++.+...
....+.....
.++++.....
+..+.+.+..
NVSEV

Cod:
4.28


Titlul: Răspuns: 064 Cobai
Scris de: Finaru Andrei Emanuel din Ianuarie 24, 2011, 20:21:16
Mie imi da tot asa: 4.285714. Mersi, oricum.
LE: Mi-a iesit de suta, o greseala stupida in cod #-o


Titlul: Răspuns: 064 Cobai
Scris de: Andrei C. din Iulie 07, 2011, 16:58:08
Este special cu testul 18? Caci mie nu-mi iese de niciun fel.

L.E. Am luat 100 pana la urma, dar banuiesc ca dupa directii mai este scris ceva (doar o banuiala fiindca am trecut testul 18 doar dupa ce am facut break in momentul in care D[curenta] != N si S si V si E. Nu reuseam daca ma opream in momentul in care D[curenta]=='\0'. Citeam cu scanf("%s", D) ).


Titlul: Răspuns: 064 Cobai
Scris de: onisim necula din Iulie 19, 2012, 16:06:53
va puteti uita peste una din sursele mele sa imi spuneti si mie de ce imi da killed by signal ?


Titlul: Răspuns: 064 Cobai
Scris de: Dumitru Andrei Georgian din Iulie 20, 2012, 14:10:38
Cod:
while(a[i+dx[x]][j+dy[x]]!=-1&&i+dx[x]>=1&&i+dx[x]<=n&&j+dy[x]>=1&&j+dy[x]<=m)
Aici tu accesezi a[i + dx
  • ][j + dy
  • ] fara sa verifici daca i + dx
  • si j + dy
  • sunt intre 1 si n, respectiv intre 1 si m, ceea ce poate sa iti strice rezolvarea. Ordinea corecta a conditiilor din while este
Cod:
while(i+dx[x]>=1&&i+dx[x]<=n&&j+dy[x]>=1&&j+dy[x]<=m && a[i+dx[x]][j+dy[x]]!=-1)
Urmatoarea problema este prima linie din while unde in loc sa pui a[i + dx
  • ][j + dy
  • ] ai pus a[i + dx
  • ][j + dy[j]]. J poate merge pana la m, iar vectorul dy are doar 4 elemente => killed by signal 11.


Titlul: Răspuns: 064 Cobai
Scris de: Alexandru Valeanu din Ianuarie 22, 2013, 22:44:56
Poate sa-mi spuna si mie cineva ce gresesc:

Cod:

#include <iostream>
#include <fstream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <iomanip>

#define pp pair<int,int>
#define ox first
#define oy second

#define Nmax (1<<6)

using namespace std;

char mat[Nmax][Nmax];
char s[Nmax*Nmax];

int n, m, nr;
int xP, yP;
float total, vizitat, raspuns;

pp coada[Nmax*Nmax];
pp coada_aux[Nmax*Nmax];
pp v[Nmax*Nmax];

int LgC, LgAuxC;

void citire(){

    freopen("cobai.in", "r", stdin);

    scanf("%d %d", &n, &m);

    for(int i = 0; i < n; i++){

        scanf("%s", s);

        for(int j = 0; j < m; j++){

            mat[i][j] = s[j];

            if(s[j] == '*')
                xP = i,
                yP = j;

            if(s[j] == '.')
                total++;
        }
    }

    scanf("%s", s);

    nr = strlen(s);

    for(int i = 0; i < nr; i++)
        switch(s[i]){

            case 'N': v[i].ox = -1, v[i].oy = 0;  break;
            case 'E': v[i].ox = 0, v[i].oy = 1;   break;
            case 'S': v[i].ox = 1, v[i].oy = 0;   break;
            case 'V': v[i].ox = 0, v[i].oy = -1;  break;
        }
}

void lee(){

    int p, tr, ts;

    LgC = 1;
    coada[0].ox = xP, coada[0].oy = yP;

    for(int p = 0; p < nr; p++){

        for(int i = 0; i < LgC; i++)
            mat[coada[i].ox][coada[i].oy] = '.';

        LgAuxC = 0;

        for(int i = 0; i < LgC; i++){

            tr = coada[i].ox;
            ts = coada[i].oy;

            while(1){

                tr += v[p].ox;
                ts += v[p].oy;

                if(tr < 0 || tr >= n || ts < 0 || ts >= m)
                    break;

                if(mat[tr][ts] != '.')
                    break;

                coada_aux[LgAuxC].ox = tr;
                coada_aux[LgAuxC].oy = ts;
                LgAuxC++;

                mat[tr][ts] = '*';
            }
        }

            for(int i = 0; i < LgAuxC; i++)
                coada[i] = coada_aux[i];

            LgC = LgAuxC;
    }
}

void gaseste(){

    for(int i = 0; i < n; i++)
        for(int j = 0; j < m; j++)
            if(mat[i][j] == '*')
                vizitat++;
}

void afis(){

    ofstream g("cobai.out");

    g << setprecision(10) << vizitat*100/total << '\n';
}

int main(){

    citire();
    lee();
    gaseste();
    afis();

    return 0;
}



Titlul: Răspuns: 064 Cobai
Scris de: Vasilut Lucian din Ianuarie 25, 2013, 00:04:56
 


Cred ca la tine greseala este faptul ca nu inchizi prima pozitie
Cod:

coada[0].ox = xP, coada[0].oy = yP;

    .....
.....

        for(int i = 0; i < LgC; i++)
            mat[coada[i].ox][coada[i].oy] = '.';



tu in coada[0].ox ,coada[0].oy bagi pozitia de unde ai plecat ,iar apoi in forul ala tu pui pozitia respectiva in matrice ca fiind spatiu liber,ceea ce este incorect.

Poti face ceva de genu:

Cod:

for(int i = 0; i < LgC; i++)
            mat[coada[i].ox][coada[i].oy] = '.';
mat[xP][yP] ='+';



Cred ca acum ar trebui sa iei ceva puncte in plus .
Bafta :ok:



Titlul: Răspuns: 064 Cobai
Scris de: Alexandru Valeanu din Ianuarie 25, 2013, 21:13:26
Multumesc frumos!
Asta era problema...acum am luat 100p.  :D


Titlul: Răspuns: 064 Cobai
Scris de: Cristian Bodnar din Martie 17, 2013, 17:54:07
Imi da raspuns gresit pe primul test. Din ce am vazut, raspunsul ar trebui sa fie 00.00 ceea ce implica un numar de locuri in care s-ar putea afla la finalul traseului egal cu 0. Asta contrazice problema unde se specifica: "Dupa schimbarea unei directii cobaiul se deplaseaza cu cel putin o pozitie in acea directie".

Aveti idee care ar putea fi problema?


Titlul: Răspuns: 064 Cobai
Scris de: Daniel Constantin Anghel din Martie 19, 2013, 20:01:49
Am trimis exact aceeasi rezolvare, dar cu doua afisari: una cu int-uri si una cu float-uri si am obtinut 40 puncte pt cea cu int-uri si 25 puncte cu cea cu float-uri. V-as recomanda sa faceti si pentru aceasta problema un evaluator care acorda punctaj pentru un test daca diferenta absoluta intre rezultatul dat de programul evaluat si cel oficial este mai mica sau egala cu 0.01.

Pai cam asta face verificatorul la problema asta.
nu, nu cred ca verificatorul face asta asa cum trebuie, chiar trebuie grija sa nu aproximezi.

de exemplu
Cod:
fout<<setprecision(2)<<fixed;
fout<<(double)sol*100/rn-0.005<<"\n";
ia 100 in timp ce
Cod:
fout<<setprecision(2)<<fixed;
fout<<(double)sol*100/rn<<"\n";
ia 75

deci daca aveti 75 de puncte si nu stiti de unde e, s-ar putea sa trebuiasca sa scadeti 0,005.


Titlul: Răspuns: 064 Cobai
Scris de: Bogdan Pop din Ianuarie 19, 2014, 03:28:24
Nu reusesc sa-mi dau seama unde gresesc.
imi puteti spune unde gresesc?

Cod :


#include <fstream>
#include <queue>
#include <iomanip>
#include <string>
using namespace std;

ifstream is("cobai.in");
ofstream os("cobai.out");

int n,m,SP1,SP2;
char x[51][51];
string s;
float Rooms,PossibleRooms,Result;

queue<pair<int,int> > Q;
queue<pair<int,int> > Q2;

void Input();
void BF();

int main()
{
    Input();
    BF();
    Result = (PossibleRooms)*100/Rooms;
    os << setprecision(4) << Result;

        return 0;
}

void Input()
{
    is >> n >> m;
    for ( int i = 1; i <= n; ++i )
        for ( int j = 1; j <= m; ++j )
        {
            is >> x[j];
            if ( x[j] == '*' )
            {
                Q.push(make_pair(i,j));
                SP1 = i;
                SP2 = j;
                x[j] = '+';
            }
            if ( x[j] == '.')
                Rooms++;
        }
    is >> s;
}

void BF()
{
    int ki,kj,ip,jp;
    for ( int i = 0; i < s.size(); ++i )
    {
        if ( s == 'N' )
            ki = -1, kj = 0;
        if ( s == 'E' )
            ki = 0, kj = 1;
        if ( s == 'S' )
            ki = 1, kj = 0;
        if ( s == 'V' )
            ki = 0, kj = -1;
            int l = 0;
        PossibleRooms = 0;
        while ( !Q.empty() )
        {
            l = 0;
            ip = Q.front().first;
            jp = Q.front().second;
            if ( ip != SP1 || jp != SP2 )
            x[ip][jp] = '.';
            Q.pop();
            while ( 1 != 0 )
            {
                ip += ki;
                jp += kj;
                l = 1;
                if ( ip >= 1 && ip <= n && jp >= 1 && jp <= m && x[ip][jp] == '.' )
                {
                    Q2.push(make_pair(ip,jp));
                    x[ip][jp] = '*';

                }
                else
                    break;
            }
        }
                    while ( !Q2.empty() )
            {
                Q.push(make_pair(Q2.front().first,Q2.front().second));
                Q2.pop();
                PossibleRooms++;
            }
    }
}