Pagini: [1]   În jos
  Imprimă  
Ajutor Subiect: Move  (Citit de 2721 ori)
0 Utilizatori şi 1 Vizitator pe acest subiect.
savim
Nu mai tace
*****

Karma: 194
Deconectat Deconectat

Mesaje: 333



Vezi Profilul
« : Februarie 24, 2013, 01:28:07 »

Aici se pot pune întrebări legate de problema Move de la Runda 3 a concursului Algoritmiada 2013.

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
geniucos
Vorbaret
****

Karma: 21
Deconectat Deconectat

Mesaje: 199



Vezi Profilul
« Răspunde #1 : Februarie 24, 2013, 09:08:24 »

Cum adica "Pentru ca o operatie move(a, b) sa fie considerata valida, trebuie ca a != b"?Inseamna ca nu pot sa il mut pe 2 imediat dupa pozitia 2,adica pe 3?
Memorat
assa98
Strain
*

Karma: -19
Deconectat Deconectat

Mesaje: 33



Vezi Profilul
« Răspunde #2 : Februarie 24, 2013, 09:13:44 »

Numerele sunt intre 1 si N?
Memorat
eudanip
Echipa infoarena
Nu mai tace
*****

Karma: 307
Deconectat Deconectat

Mesaje: 695



Vezi Profilul
« Răspunde #3 : Februarie 24, 2013, 09:17:23 »

Cum adica "Pentru ca o operatie move(a, b) sa fie considerata valida, trebuie ca a != b"?Inseamna ca nu pot sa il mut pe 2 imediat dupa pozitia 2,adica pe 3?

NO COMMENT. E foarte clar.

Numerele sunt intre 1 si N?

Din moment ce se da o PERMUTARE tu ce crezi?
Memorat
Luzar_roky
Strain


Karma: -5
Deconectat Deconectat

Mesaje: 1



Vezi Profilul
« Răspunde #4 : Februarie 24, 2013, 09:48:52 »

operatiile de tip MOVE sunt incluse in limbajul c si c++ in <cmath>/<cmath.h> ?

edit: nu mai am nevoie de un raspuns
« Ultima modificare: Februarie 24, 2013, 10:01:03 de către Ilies Dragos Ionut » Memorat
geniucos
Vorbaret
****

Karma: 21
Deconectat Deconectat

Mesaje: 199



Vezi Profilul
« Răspunde #5 : Februarie 24, 2013, 18:17:42 »

Cum se facea problema asta?
Memorat
harababurel
Client obisnuit
**

Karma: 23
Deconectat Deconectat

Mesaje: 62



Vezi Profilul
« Răspunde #6 : Februarie 24, 2013, 19:20:19 »

Problema e foarte asemanatoare cu asta: http://codeforces.com/contest/270/problem/D, diferenta fiind ca aici trebuie sa afisezi si operatiile propriuzise.
Pentru ca numarul de operatii sa fie minim, incerci sa alegi un subsir cat mai lung a.i. elementele din el sa poata ramane la pozitiile lor si sa nu trebuiasca mutate (adica sa fie deja in ordine crescatoare), ceea ce coincide cu gasirea celui mai lung subsir crescator. Astfel ca numarul minim de mutari este egal cu N - L, unde L = lungimea celui mai lung subsir crescator.
Pentru a determina operatiile, se introduc intr-un vector toate valorile care nu fac parte din subsirul crescator maximal (adica valori care trebuiesc mutate de la pozitiile lor), si se parcurg in ordine crescatoare (ar trebui sa functioneze si o parcurgere in ordinea in care apar). Pentru fiecare valoare VAL, ea trebuie mutata la dreapta valorii VAL-1, astfel ca fiecare operatie este de forma "VAL VAL-1". Complexitatea finala O(N log N). Sper ca ti-am fost de ajutor!
Memorat
geniucos
Vorbaret
****

Karma: 21
Deconectat Deconectat

Mesaje: 199



Vezi Profilul
« Răspunde #7 : Februarie 24, 2013, 19:57:34 »

Multumesc pentru ajutor!Am luat 100.Totusi nu mergea sa afisezi operatiile in ce ordine vrei.Trebuiau afisate neaparat in ordine crescatoare:D
Memorat
harababurel
Client obisnuit
**

Karma: 23
Deconectat Deconectat

Mesaje: 62



Vezi Profilul
« Răspunde #8 : Februarie 24, 2013, 21:18:55 »

Da, trebuie afisate in ordinea crescatoare a valorii lor, deoarece mutarea elementului VAL in dreapta elementului VAL-1 implica automat ca elementul VAL-1 sa fie amplasat corect, si asta nu-i neaparat adevarat daca nu tii cont de ordine...
Memorat
Pagini: [1]   În sus
  Imprimă  
 
Schimbă forumul:  

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