infoarena

infoarena - concursuri, probleme, evaluator, articole => Arhiva de probleme => Subiect creat de: Mircea Pasoi din Noiembrie 03, 2005, 02:13:54



Titlul: 131 Geamuri
Scris de: Mircea Pasoi din Noiembrie 03, 2005, 02:13:54
Aici puteţi discuta despre problema Geamuri (http://infoarena.ro/problema/geamuri).


Titlul: 131 Geamuri
Scris de: andreit1 din Noiembrie 06, 2005, 21:21:43
Cam in ce complexitate ar trebui sa rezolv problema, tinand cont ca citirea si afisarea unui 0 pentru fiecare intrebare dureaza 0.12 secunde pe ultimul test( stiu ca timpii din monitor sunt orientativi, dar probabil se apropie de realitate)?
Sursa folosita:
Cod:

var fi,fo:text;
    i,x1,y1,x2,y2,c,n,x:word;
begin
 assign(fi,'geamuri.in'); reset(fi);
 assign(fo,'geamuri.out'); rewrite(fo);
 readln(fi,c); readln(fi,n);
 for i:=1 to n do readln(fi,x1,y1,x2,y2);
 readln(fi,n);
 for i:=1 to n do
  begin readln(fi,x); writeln(fo,0); end;
 close(fo);
end.


Titlul: 131 Geamuri
Scris de: Mircea Pasoi din Noiembrie 07, 2005, 00:14:18
Am schimbat limita la 0.2s


Titlul: 131 Geamuri
Scris de: Filip Cristian Buruiana din Noiembrie 08, 2005, 20:54:44
O(N log^2 C + M) ajunge?  :oops:  :cry:


Titlul: 131 Geamuri
Scris de: Tiberiu-Lucian Florea din Noiembrie 08, 2005, 21:46:25
Nu stiu, dar cred ca a fost data la C^2 + N + M.


Titlul: 131 Geamuri
Scris de: Filip Cristian Buruiana din Noiembrie 09, 2005, 11:36:44
Da, asa e  :-#


Titlul: 131 Geamuri
Scris de: Cosmin Negruseri din Decembrie 12, 2005, 22:36:24
Citat
Fiecare geam ce contine acel punct se va sparge
In problema nu se intelege ca tu vrei un punct inclus in ki dreptunghiuri, daca glontul i sparge geamuri atunci glontul i + 1 va sparge din geamurile ramase ... nu tot din geamurile initiale, enuntul induce in eroare pe cei ce vreau sa rezolve problema !!!!!!!!!


Titlul: 131 Geamuri
Scris de: Claudiu Guiman din Februarie 11, 2006, 10:28:55
Ce e gresit in codul asta? (poate sunt eu prost si nu-mi dau seama, dar mi se pare corect). La codu' asta iau 0 punct.
   
Cod:
#include<fstream>
#define IN_FILE  "geamuri.in"
#define OUT_FILE "geamuri.out"
std::ifstream IN;
std::ofstream OUT;
long n,m,c,a[1025][1025],b[50001];
void adaugaGeam(int x1, int y1, int x2, int y2)
{
 int i,j;
 for(i=y1; i<=y2; ++i)
    for(j=x1; j<=x2; ++j)
       {
        --b[a[i][j]];
        ++a[i][j];
        ++b[a[i][j]];
        }
 }
void citire()
{
 IN>>c;
 IN>>n;
 int i,x1,y1,x2,y2;
 for(i=1; i<=n; ++i)
    {
     IN>>x1;
     IN>>y1;
     IN>>x2;
     IN>>y2;
     adaugaGeam(x1,y1,x2,y2);
     }
 IN>>m;
 for(i=1; i<=m; i++)
     {
      IN>>x1;
      OUT<<b[x1]<<"\n";
      }
 }
int main()
{
 IN.open(IN_FILE);
 OUT.open(OUT_FILE);
  citire();
 IN.close();
 OUT.close();
 return 0;
 }


  Sa-mi spuneti daca e gresti, nu vreau sa-mi spuneti ce am gresit, o sa ma gandesc eu la asta :P


Titlul: 131 Geamuri
Scris de: Daniel Pasaila din Februarie 11, 2006, 11:15:47
Pai daca iei 0 puncte nu e clar ca e gresit? Poate doresti sa iti spunem ce ai gresit:)


Titlul: 131 Geamuri
Scris de: Claudiu Guiman din Februarie 11, 2006, 11:27:05
:mrgreen: ai dreptate... poate imi spui


Titlul: 131 Geamuri
Scris de: Tiberiu-Lucian Florea din Februarie 11, 2006, 23:56:48
Asteapta sa-ti depaneze altii codul, si o sa ajungi departe. :)


Titlul: 131 Geamuri
Scris de: ditzone din Februarie 12, 2006, 09:32:08
In primul rand sunt convins ca iei destule TLE si ar trebui sa te gandesti la o alta complexitate si in al doilea rand.. esti sigur ca raspunzi corect la intrebarile pentru K=0 ?


Titlul: Răspuns: 131 Geamuri
Scris de: Savin Tiberiu din Mai 02, 2007, 21:01:12
la primu query in exemplu zice ca ar fi un singur punct si anume: (5 4). Mie mi se pare ca si (5 3) e corect deci ar fi 2 puncte. Ce nu am inteles bine??


Titlul: Răspuns: 131 Geamuri
Scris de: Adrian Diaconu din Mai 06, 2007, 18:17:18
Pai daca tragi din (5,3) nu atingi ultimul geam, atingi doar primele 2.


Titlul: Răspuns: 131 Geamuri
Scris de: Andrei Constantinescu din Martie 16, 2013, 13:08:27
Sunt si eu curios de ceva legat de problema: ](*,)
Daca Geminski are doua variante de a trage primul glont pe care o va alege? Intreb asta deoarece Cosmin Negrusesti a spus ca dupa ce se trage primul glont, geamurile sparte de el dispar si astfel raspunsurile pentru urmatoarele gloante pot diferi in functie de ce alegere face Geminski pentru glontul cu 2 variante.

Ex. Se poate sa dispara puncte unde se sparg 4 geamuri daca alegem o varianta de la glontul 1 sau sa nu dispara daca o alegem pe cealalta.

Multumesc anticipat.

Mentionez ca am gasit rezolvarea cu Smenul lui Mars deja.

L.E.: Rezolvat!


Titlul: Răspuns: 131 Geamuri
Scris de: Mihai Ionut Enache din Iunie 20, 2013, 14:03:27
Cred ca ar trebui marita un pic limita  :). Am luat 100p doar cand am parsat, altfel iau doar 60p cu complexitate O(N+C^2+M).


Titlul: Răspuns: 131 Geamuri
Scris de: Daniel Constantin Anghel din Iunie 21, 2013, 17:00:40
Cred ca ar trebui marita un pic limita  :). Am luat 100p doar cand am parsat, altfel iau doar 60p cu complexitate O(N+C^2+M).

merge fara parsare. tu aloci prea multa memorie si de-aia iesi din timp cred.

vezi ca poti sa tii S in A, avand in vedere ca nu mai folosesti A odata ce iti creezi S.


Titlul: Răspuns: 131 Geamuri
Scris de: Mihai Ionut Enache din Iunie 23, 2013, 12:37:59
Mersi, asa este, alocam prea multa memorie si in plus parcurgeam matricea de 2 ori, in loc de o singura data. Dar la sursa asta ce este gresit: http://www.infoarena.ro/job_detail/965110?action=view-source ? Iau doar 70p desi folosesc doar matricea A si o parcurg o singura data  :-k


Titlul: Răspuns: 131 Geamuri
Scris de: Daniel Constantin Anghel din Iunie 23, 2013, 21:31:07
Mersi, asa este, alocam prea multa memorie si in plus parcurgeam matricea de 2 ori, in loc de o singura data. Dar la sursa asta ce este gresit: http://www.infoarena.ro/job_detail/965110?action=view-source ? Iau doar 70p desi folosesc doar matricea A si o parcurg o singura data  :-k

tu parcurgi coloana cu coloana.
trebuie sa parcurgi linie cu linie ca sa nu spargi cache-ul.


Titlul: Răspuns: 131 Geamuri
Scris de: Mihai Ionut Enache din Iunie 23, 2013, 23:37:00
Asa este, am luat 100p daca parcurg linie cu linie. Imi poti explica, te rog, care este diferenta?


Titlul: Răspuns: 131 Geamuri
Scris de: Daniel Constantin Anghel din Iunie 24, 2013, 12:10:13
Asa este, am luat 100p daca parcurg linie cu linie. Imi poti explica, te rog, care este diferenta?

matricile in c/c++ sunt retinute linie cu linie, iar cand pargurgi linie cu linie tu treci la elementul cu 1 poz in dreapta, dar coloana cu coloana sari vreo 1000 de elemente in cazul de fata.

cacheul e niste memorie care poate fi accesata rapid, iar tu cand accesezi un element al unui vector procesorul presupune ca o sa ai nevoie si de urmatoarele elemente si ti le baga in cache.



Titlul: Răspuns: 131 Geamuri
Scris de: Mihai Ionut Enache din Iunie 25, 2013, 11:04:07
Nu stiam. Thanks!  :peacefingers: