Pagini: [1]   În jos
  Imprimă  
Ajutor Subiect: Troll  (Citit de 8554 ori)
0 Utilizatori şi 1 Vizitator pe acest subiect.
eudanip
Echipa infoarena
Nu mai tace
*****

Karma: 307
Deconectat Deconectat

Mesaje: 703



Vezi Profilul
« : Ianuarie 12, 2013, 09:49:03 »

Aici se pot pune întrebări legate de problema Troll de la Runda 2 a concursului .com 2012

Timpul alocat întrebărilor este de 1 ora dupa inceperea concursului. Întrebările vor fi formulate astfel încât să se poată răspunde cu DA sau NU. În caz contrar sau în cazul în care întrebarea își găsește răspuns în enunțul problemei, răspunsul va fi FARA COMENTARII.
Memorat
informatician28
Strain
*

Karma: 6
Deconectat Deconectat

Mesaje: 27



Vezi Profilul
« Răspunde #1 : Ianuarie 12, 2013, 10:10:40 »

"sa ia un interval de valoare maxima si sa vada cate intervale mai poate adauga astfel incat acestea sa nu se suprapuna in nici-un punct", in sens ca toate celelalte intervale sa fie cuprinse in acest interval cu z maxim, dar intre ele(cele ramase, fara z maxim) sa nu se suprapuna?
Memorat
andreifirst
Strain
*

Karma: 4
Deconectat Deconectat

Mesaje: 26



Vezi Profilul
« Răspunde #2 : Ianuarie 12, 2013, 10:11:22 »

Eununtul e putin ciudat. Trebuie sa aflam numarul maxim de intervale si apoi valoarea maxima din ele sau trebuie sa alegem valoarea maxima si apoi nr maxim de intervale ce mai poate fi adaugat?
Memorat
darren
Client obisnuit
**

Karma: 106
Deconectat Deconectat

Mesaje: 76



Vezi Profilul
« Răspunde #3 : Ianuarie 12, 2013, 10:12:57 »

Ce valori poate avea Z?
Memorat
andreifirst
Strain
*

Karma: 4
Deconectat Deconectat

Mesaje: 26



Vezi Profilul
« Răspunde #4 : Ianuarie 12, 2013, 10:15:11 »

intervalele [1, 2] si [2, 3] se considera ca se suprapun?
Memorat
eudanip
Echipa infoarena
Nu mai tace
*****

Karma: 307
Deconectat Deconectat

Mesaje: 703



Vezi Profilul
« Răspunde #5 : Ianuarie 12, 2013, 10:17:00 »

"sa ia un interval de valoare maxima si sa vada cate intervale mai poate adauga astfel incat acestea sa nu se suprapuna in nici-un punct", in sens ca toate celelalte intervale sa fie cuprinse in acest interval cu z maxim, dar intre ele(cele ramase, fara z maxim) sa nu se suprapuna?

Nu. Nici un interval nu trebuie sa se suprapuna cu nici un interval. Inclusiv cel cu valoarea maxima.

Eununtul e putin ciudat. Trebuie sa aflam numarul maxim de intervale si apoi valoarea maxima din ele sau trebuie sa alegem valoarea maxima si apoi nr maxim de intervale ce mai poate fi adaugat?

Scrie in enunt ordinea corecta.

Memorat
S7012MY
Nu mai tace
*****

Karma: 26
Deconectat Deconectat

Mesaje: 648



Vezi Profilul
« Răspunde #6 : Ianuarie 12, 2013, 10:22:42 »

Problema cere:
Sa se afle suma maxima obtinuta din intervale disjuncte incluse in intervalul de valoare maxima care poate fi inclusa in acest interval ?
Memorat
darren
Client obisnuit
**

Karma: 106
Deconectat Deconectat

Mesaje: 76



Vezi Profilul
« Răspunde #7 : Ianuarie 12, 2013, 10:24:11 »

Cred ca testul 6 (de la rezultate partiale) nu respecta conditia 1 ≤ X, Y ≤ 100000.
Memorat
roots
Strain


Karma: 4
Deconectat Deconectat

Mesaje: 12



Vezi Profilul
« Răspunde #8 : Ianuarie 12, 2013, 10:26:14 »

Pentru testul :

Cod:
3
1 1 1
1 3 2
2 4 2

raspunsul este :

Cod:
2 2

?
Memorat
vendetta
De-al casei
***

Karma: 72
Deconectat Deconectat

Mesaje: 122



Vezi Profilul
« Răspunde #9 : Ianuarie 12, 2013, 10:28:51 »

1) Ce se stie despre Z?
2) Practic tu tot timpul alegi intervalul de valoare maxima ?
Memorat
Challenge
Strain


Karma: 18
Deconectat Deconectat

Mesaje: 19



Vezi Profilul
« Răspunde #10 : Ianuarie 12, 2013, 10:35:30 »

Se garanteaza ca Z-urile sunt distincte?
Memorat
tzipleatud
De-al casei
***

Karma: 104
Deconectat Deconectat

Mesaje: 117



Vezi Profilul
« Răspunde #11 : Ianuarie 12, 2013, 10:47:17 »

Pentru cerinta a 2-a, daca exista mai multe intervale cu Z maxim, care nu se suprapun, se pot lua toate? Adica pentru testul
Cod:
2
1 5 10
7 11 10

raspunsul este
Cod:
10 2
?
Memorat
edp100
Strain


Karma: 1
Deconectat Deconectat

Mesaje: 21



Vezi Profilul
« Răspunde #12 : Ianuarie 12, 2013, 10:49:35 »

@Buhai
Limita a fost modificata, era asa de la o versiune anterioara a problemei, imi cer scuze pentru inconvenientele cauzate.

@andreifirst
Citat
astfel incat acestea sa nu se suprapuna in nici-un punct
intervalele fiind inchise  ( [x, y] ),  se considera ca se suprapun.

@vendetta & Challenge
Z incape in int, de asemenea pot exista mai multe intervale cu acelasi z.

@tzipleatud
Citat
Pentru cerinta a 2-a, daca exista mai multe intervale cu Z maxim, care nu se suprapun, se pot lua toate?
DA
Memorat
darren
Client obisnuit
**

Karma: 106
Deconectat Deconectat

Mesaje: 76



Vezi Profilul
« Răspunde #13 : Ianuarie 12, 2013, 10:52:39 »

Z este >= 0?
Memorat
edp100
Strain


Karma: 1
Deconectat Deconectat

Mesaje: 21



Vezi Profilul
« Răspunde #14 : Ianuarie 12, 2013, 10:58:28 »

NU,
Am adaugat:
Citat
-1337 ≤ Z ≤ 2000800000

@roots
Vezi :
Citat
@tzipleatud
Citat
Pentru cerinta a 2-a, daca exista mai multe intervale cu Z maxim, care nu se suprapun, se pot lua toate?
DA

@S7012MY
NU
« Ultima modificare: Ianuarie 12, 2013, 11:04:28 de către .com 2012 » Memorat
repp4radu
Nu mai tace
*****

Karma: 118
Deconectat Deconectat

Mesaje: 204



Vezi Profilul
« Răspunde #15 : Ianuarie 12, 2013, 11:00:17 »

Dupa modificarea limitei cu X, Y, cred ca ati facut multa lumea sa piarda destul de mult timp...
Memorat
valentin.harsan
Strain
*

Karma: 33
Deconectat Deconectat

Mesaje: 41



Vezi Profilul
« Răspunde #16 : Ianuarie 12, 2013, 11:23:53 »

nu uitati de restrictia:

Citat
Pentru a obtine punctele la testul 10 trebuie sa afisati 1337 inainte de celelalte 2 numere.
Memorat
dariusdarius
Client obisnuit
**

Karma: 20
Deconectat Deconectat

Mesaje: 62



Vezi Profilul
« Răspunde #17 : Ianuarie 12, 2013, 11:26:49 »

Se poate ca 2 interval sa fie identice?
Memorat
eudanip
Echipa infoarena
Nu mai tace
*****

Karma: 307
Deconectat Deconectat

Mesaje: 703



Vezi Profilul
« Răspunde #18 : Ianuarie 12, 2013, 11:27:25 »

Nu mai trolla.
nu uitati de restrictia:

Citat
Pentru a obtine punctele la testul 10 trebuie sa afisati 1337 inainte de celelalte 2 numere.
Memorat
edp100
Strain


Karma: 1
Deconectat Deconectat

Mesaje: 21



Vezi Profilul
« Răspunde #19 : Ianuarie 12, 2013, 11:28:16 »

@Darius
DA
Memorat
andreifirst
Strain
*

Karma: 4
Deconectat Deconectat

Mesaje: 26



Vezi Profilul
« Răspunde #20 : Ianuarie 12, 2013, 13:32:09 »

Se mai pot pune intrebari? Very Happy Doar pentru clarificare: problema imi cere sa aflu numarul maxim de intervale astfel incat printre ele sa existe si intervalul (unul din intervalele) de lungime maxima din lista?
Memorat
valentin.harsan
Strain
*

Karma: 33
Deconectat Deconectat

Mesaje: 41



Vezi Profilul
« Răspunde #21 : Ianuarie 12, 2013, 19:05:45 »

cred ca limita de timp la problema asta e cam mica....
de la citirea cu cin iau 90  Brick wall
Memorat
Mihai22e
Client obisnuit
**

Karma: 20
Deconectat Deconectat

Mesaje: 74



Vezi Profilul
« Răspunde #22 : Ianuarie 12, 2013, 20:21:36 »

Eu am reusit sa obtin 80p la problema aceasta cu un algoritm destul de slab, dupa parerea mea: sortez intervalele dupa capatul din dreapta, si apoi cu un algoritm greedy verific cate intervale pot lua maxim astfel incat sa nu se intersecteze (fie K numarul maxim de intervale pe care le pot lua astfel incat sa nu se intersecteze); apoi am 2 cazuri:
1.in cele K intervale luate, am cel putin un interval cu valoarea maxima, deci afisez Z-ul cel mai mare si K
2.nu am niciun interval cu valoarea maxima si procedez in felul urmator: iau pe rand fiecare interval dintre cele cu valoare maxima si verific cate intervale trebuie sa scot din cele K astfel incat sa-l pot introduce pe cel ales acum, iar apoi compar cu maximul; deci afisez Z-ul cel mai mare si maximul.
Ceea ce e si mai ciudat e faptul ca in prima sursa pe care am trimis-o am facut o eroare destul de grava, care ar fi trebuit sa dea peste cap tot algoritmul: cand sunt in cazul al 2lea si aleg un interval cu valoare maxima, in loc sa-l compar cu cele K intervale deja luate, il compar cu toate intervalele (N) si verific cate ar trebui sa scot pentru a-l introduce pe acesta..ceea ce e evident gresit. De aici deduc ca majoritatea testelor nu au intervale care sa se intersecteze, sau au prea putine.
Memorat
Pagini: [1]   În sus
  Imprimă  
 
Schimbă forumul:  

Powered by SMF 1.1.19 | SMF © 2006-2013, Simple Machines