[AUT-ACMICPC] AUT-OJ7

[Aminreza Gholami]

salam,
in hafte chon soalhaye hal nashode dar contest hafteye ghabl ra taghriban hich kas hal nakard,
contest jadid nagozashtim.(az 25 soal hal nashode (3+5+5+6+6) faghat 3 soal bad az contest hal shod!!) ke in yani kasi ghasd tamrin jeddi nadare va contest gozashtan vaght talaf kardane!!!

be nazar man bad az contest bayad hatman soalha ra hal konid,
bad az chand rooz ham javab soalha ra kasani ke hal kardand to goroh begozarand.

baraye hamahangi javab soalhaye contest 2hafteye pish ra be in tartib begozarid(tarjihan rahhal ra mail konid na code):
B -> angeh aslanian
C -> fatemeh azadi
D -> hale havayi
G -> fatemeh azadi
H -> azadeh mosavi

link contest: AUT-OJ7

--
You received this message because you are subscribed to the Google Groups "AUT-ACMICPC" group.
To post to this group, send email to aut-a...@googlegroups.com.
To unsubscribe from this group, send email to aut-acmicpc...@googlegroups.com.
For more options, visit this group at http://groups.google.com/group/aut-acmicpc?hl=en.

[Pooya Zafar]

Kheyli mamnun

[Angeh A2]

Soale B :
Soale Graph
hameye SCC ha ro be dast miarim , va node haye har kodoom ro tarkib mikonim ye joorai,
graph ye DAG mishe ...azaye ooni ke outdegree==0 dare ro chap mikonim , baraye SCC peyda kardan , Tarjan behtar az baghie ravesh haast


Soale F:
Soale DP!!!!
az tamame ja hayi ke mitoonim ta bezanim say mikonim ta bezanim ta jayi ke  dige jaye ta kardan namoone ...
vali bayaye ta kardan bayad check konim ke mishe ta zad ya na ....
{  baraye inke betoonim  ta bezanim bayad az mahale ta age be 2 sare kaghaz harekat konim ta ha dar 2 taraf dar jahate axe ham bashan }

AAVAAVVVAAV
az A ta mizanim mishe 

AVVVAAV
 az V ta mizanim mishe 
AAV
az A ta mizanim mishe 

V
ke V ham khodesh ye ta mikhad ...
kolan 4 doone ta lazem dare ... 

On Mon, May 10, 2010 at 2:46 PM, Aminreza Gholami <ami...@gmail.com> wrote:

[Angeh A2]

[Azadeh Mousavi]

too soale B,manzooretoon az SCC ,DAG va Tarjan ro nemifahmam!:D kollan age ye meghdari bishtar tozih bedin khoob mishe! mamnoon --- On Mon, 5/10/10, Angeh A2 <ange...@gmail.com> wrote:

[Azadeh Mousavi]

tozihe soale H: avval inke mishe sabet kard ke bozorgtarin mostatil , ertefa'esh be andazeye yekki az 'h[i]' hast pas agar bozorgtarin mostatile momken ro baraye har h[i] ee be dast biarim,javab taghriban be dast miad,(bayad beyne masahat haye be dast amade max begirim) avval ai va bi ro baraye har ertefa'e hi tarif mikonim, a[i]: (andise avvalin chap tarin ertefa'ee ke agar az i omin ertefa shoroo konim h[ai]< h[i] shavad)+1 b[i]: (andise avvalin rast tarin ertefa'ee ke agar az i omin ertefa shoroo konim h[ai]< h[i] shavad)-1 kafist ke a[i] va b[i] ha ra baraye har ertefa bedast biarim va masahate har mostatil ba ertefa'e h[i] mishavad: h[i]*(b[i]-a[i]+1) ,va beyne in masahat ha max begirim faghat baraye be dast avordan ai va bi ha chon 1 ≤ n ≤ 100000 agar aaddi for bezanim (O(n^2))  TL mishe va baraye in ghesmat mishe az DP estefade kard va a[i] ha va b[i] ha ro ba estefade az a[j] ha va b[j] hayi ke ghablan be dast avordim hesab konim --- On Mon, 5/10/10, Aminreza Gholami <ami...@gmail.com> wrote:

[HALEH H]

D.Drink,on Ice
halate ghabele pishbini:
1)tabdile hameye ab be yakh t daraje
2) tabdile hameye yakh be ab t daraje
3)tabdile m gram yakh be ab(makhlooti az ab va yakh 0 daraje)
4)tabdile m gram ab be yakh(makhlooti az ab va yakh 0 daraje)
(1)
Mw * 4.19*(0-tw)+mi*2.09*(t-ti)-mw*em+mw*2.09*t=0
T=(mi*2.09*ti+mw*4.19*tw+mw*em)/(mi*2.09+mw*2.09)
Agar t<=0 bashad:
Jerme yakh = mw+mi , Jerme ab=0
(2)
Mi*2.09*(0-ti)+mi*em+mi*4.19*t+mw*4.19(t-tw)=0
T=(mi*2.09-mi*em+mw*4.19*tw) /(mw*4.19+mi*4.19)
Agar t>=0 bashad:
Jerme yakh =0, Jerme ab=0
(3)
M=jerme meghdar yakh ab shode
Damaye ta'adol=0
Mw*4.19(0-tw)+mi*2.09(0-ti)+m*em=0
M=(mw*4.19*tw+mi*2.09*ti)/em
Agar m<=mi bashad:
Jerme yakh = mi-m, jerme ab = m+mw
(4)
M=jerme meghdar ab yakh baste
Damaye ta'adol=0

Mw*4.19(0-tw)+mi*2.09*(0-ti)-m*em=0
M=(mw*4.19*tw+mi*2.09*ti)/-em
Agar m<mw bashad :
Jerme yakh=mi+m , jerme ab=mw-m

[Angeh A2]

SCC strongly connected componenets ...( ye sub graph az ye ye directed graph ke ke u~>v baraye tamame u va v haye oon sub graph )
DAG  Directed Acyclic Graph ...
Tarjan ham ye algorithme maroof baraye peyda kardane SCC e (makhsoosan vase masale hayei mese in va directed MST va .. ke tarkib kardane node haye SCC be soorate ye node vahed matrah mishe ) faghat ba ye modified DFS

aval tamame SCC ha ro peyda mikonim ..
baraye azaye har SCC sharte
bottom(G)={v∈V|∀w∈V:(v→w)⇒(w→v)}

bargharar e...
halati ke baes mishe in shart baraye node haye ye SCC sedgh nakone va node haye tooye oon SCC bottom nabashan  ine ke yeki az node haye oon SCC (u) be ye node (v) yale dashte bashe ke v ozve SCC i ke u tooshe nabashe dar in halat tamame node haye SCCi ke node u tooshe be ye node digei vaslan ke oon node be ina vasl nist ... pas bottomn nistan ...

dar vaghe node haye tooye har SCCi ,ke hich kodoom az node haye oon  SCC  be node digei gheyr az node haye tooye oon SCC vasl nabashan mishan bottom e Graph ...

omidvaram tooneste basham khoob begam:D

[Fatemeh Azadi]

Salam

C.   Fixed Partition Contest Management:

Ba backtrack hameye assignmentaye mokhtalef baraye soalharo tolid mikonim, va baraye har kodoom agar assignmente  dorosti  bood (yani  har soal tavasote shakhsi ke bayad halesh kone ghabele hal bood) minimume majmooe zaman haye hal ro hesab mikonim va beine hameye assignmenta  minimum migirim. Baraye har halat ham tartibi minimum majmoo’e ro dare ke har nafar soalhayi ro ke bayad hal kone be tartib az oonayi  ke zamane kamtary tool mikeshan, shoroo kone.

 

G.   Genetic Code:

Ba backtrack (!!) reshteyi ba sharayete mas’ale  be toole hade aksar 5000 misazim va baraye hameye voroodiha az hamon estefade mikonim  (ke nemidoonam ghabl az code zadan az koja mishe motmaen shod ke cheghadr tool mikeshe ta ye chenin stringi ro peida kone vali beharhal age az tavabe’e stringie C estefade konim mibinim ke kheili kam tool mikeshe ! )