Deci trebuie sa gasim minimul lui B(i,j) cu i+j=K, i>=1 si j>=1. Pentru orice i si j alegem, numitorul fractiei este constant, deci trebuie sa le alegem astfel incat sa minimizam numaratorul fractiei.
Astfel, deoarece K este par, putem observa ca B(K/2,K/2) ne va da minimul functiei. Deci, Daniel se va putea teleporta dintr-un punct (x,y) in (x+K/2,y+K/2) sau (x-K/2,y+K/2) sau (x+K/2,y-K/2) sau (x-K/2,y-K/2).
Daca Daniel este intr-un punct (x,y) care e la distanta manhattan D fata de origine dupa o teleportare acesta va ajunge intr-un punct (x1,y1) care e la distanta manhattan D+K sau D-K fata de origine.
Cum Daniel pleaca din origine (care e la distanta manhattan 0) oricum ar folosi teleportarile acesta va ajunge intr-un punct (x,y) cu distanta manhattan fata de origine divizibla cu K.
Cum Daniel pleaca din origine (care e la distanta manhattan 0), oricum ar folosi teleportarile, acesta va ajunge intr-un punct (x,y) cu distanta manhattan fata de origine divizibla cu K.
Pentru a ajunge in zona sigura acesta trebuie sa ajunga la un punct cu distanta manhattan egala cu L/2, deci L/2 trebuie sa fie divizibil cu K => pentru prima cerinta trebuie sa afisam toti divizorii pari al lui L/2.
Daca L/2 este impar, nu va avea divizori pari, deci raspunsul va fi -1 pentru ambele cerinte.
De exemplu, pentru un K divizor par al lui L/2, un posibil drum este (0,0) -> (1*(K/2),1*(K/2)) -> (2*(K/2),2*(K/2)) -> .. -> ((L/2K)*(K/2),(L/2K)*(K/2)).
Pentru cerina 2 trebuie sa gasim drumul de cost minim dintre toti K gasiti la cerinta 1. Pentru un K fixat costul drumului minim este (L/2K)*B(K/2,K/2), daca notam functia asta cu B' observam ca este strict descrescatoare de la 2 pana la L/2, deci minimul functiei va fi cand K este maxim, respectiv L/2.
Raspunsul pentru cerinta 2 este B(L/4,L/4). (Se poate observa usor ca minimul este cand K este maxim deoarece factorialul de la numitor creste foarte repede).
Raspunsul pentru cerinta 2 este B(L/4,L/4). (Se poate observa usor ca minimul se realizeaza cu K maxim deoarece factorialul de la numitor creste foarte repede).
h2. "Sunmihai":https://infoarena.ro/problema/sunmihai
Acesta problema se rezolva cu metoda programarii dinamice. Vom calcula dp[i][j] - costul minim pentru a avea pe ultima piesa din domino valoarea din dreapta j, trecand prin primele i domino-uri date. Vom folosi notatia: v1[i] - valoarea din stanga a celui de-al i-lea domino dat initial si v2[i] - valoarea din dreapta. Dp[ 1 ][v2[ 1 ]] este 0 pentru ca nu aplicam nicio operatie primului domino, iar dp[ 1 ][v1[ 1 ]] este maxim A (v1[i] poate fi egal cu v2[i]), pentru ca intoarcem domino-ul; restul tabloului de dinamica il vom initializa cu o valoare mare. Ajunsi la a i-a piesa putem sa abordam in urmatorul fel: vrem sa o pastram exact cum e, iar dp[i][v2[i]] va fi dp[i-1][v1[i]]; vrem sa o intoarcem, iar dp[i][v1[i]] va fi dp[i-1][v2[i]] + A (atentie cand v1[i]=v2[i]), o scoatem cu cost B, iar dp[i][j] va fi egal cu dp[i-1][j] sau adaugam o piesa cu cost C. Piesa de tip C are sens sa fie adaugata doar cand vrem sa pastram a i-a piesa si nu avem anterior o piesa de care sa o legam, adica dp[i-1][v1[i] / v2[i]] este valoarea aceea mare cu care am initializat tabloul. Putand insera o piesa cu orice valori v1 si v2, nu ne intereseaza care sunt acestea si vom insera piesa dupa o configuratie dp[i-1][j], nu conteaza cine este j (de la 1 la 100), cu dp valoarea minima. Dp[i][v2[i]] va fi dp[i-1][j] (minim) + C. Raspunsul se va afla in min(dp[n][v1[i]], dp[n][v2[i]]).
Acesta problema se rezolva cu metoda programarii dinamice. Vom calcula dp[i][j] - costul minim pentru a avea pe ultima piesa din domino valoarea din dreapta j, trecand prin primele i domino-uri date. Vom folosi notatia: v1[i] - valoarea din stanga a celui de-al i-lea domino dat initial si v2[i] - valoarea din dreapta. Dp[ 1 ][v2[ 1 ]] este 0 pentru ca nu aplicam nicio operatie primului domino, iar dp[ 1 ][v1[ 1 ]] este maxim A (v1[i] poate fi egal cu v2[i]), pentru ca intoarcem domino-ul; restul tabloului de dinamica il vom initializa cu o valoare mare. Ajunsi la a i-a piesa putem sa abordam in urmatorul fel: vrem sa o pastram exact cum e, iar dp[i][v2[i]] va fi dp[i-1][v1[i]]; vrem sa o intoarcem, iar dp[i][v1[i]] va fi dp[i-1][v2[i]] + A (atentie cand v1[i]=v2[i]), o scoatem cu cost B, iar dp[i][j] va fi egal cu dp[i-1][j] + B sau adaugam o piesa cu cost C. Piesa de tip C are sens sa fie adaugata doar cand vrem sa pastram a i-a piesa si nu avem anterior o piesa de care sa o legam, adica dp[i-1][v1[i] / v2[i]] este valoarea aceea mare cu care am initializat tabloul. Putand insera o piesa cu orice valori v1 si v2, nu ne intereseaza care sunt acestea si vom insera piesa dupa o configuratie dp[i-1][j], nu conteaza cine este j (de la 1 la 100), cu dp valoarea minima. Dp[i][v2[i]] va fi dp[i-1][j] (minim) + C. Raspunsul se va afla in min(dp[n][v1[i]], dp[n][v2[i]]).
h2. "Negot":https://infoarena.ro/problema/negot
Aceasta este o aplicatie de flux maxim, insa exista o solutie care se misca mai bine folosind cuplaj maxim in graf bipartit.
Pentru flux: vom crea un nod 0 sursa si vom crea N muchii de capacitate K. Toate muchiile de la producator la magazin au capacitate 1. Vom crea, de altfel, si un nod destinatie si M muchii de capacitate 1 de la magazine la destinatie.
Pentru flux: vom crea un nod 0 sursa si N muchii de capacitate K de la sursa la producatori. Toate muchiile de la producator la magazin au capacitate 1. Vom crea, de altfel, si un nod destinatie si M muchii de capacitate 1 de la magazine la destinatie.
Pentru cuplaj: putem "clona" un producator de K ori si fiecare clona sa o cuplam cu maxim 1 magazin. Restrictiile permit crearea efectiva a N*K noduri cu tot cu muchiile aferente, insa pentru o solutie performanta vom tine un vector de aparitii al fiecarui nod dintre cele N. Frecventa petru fiecare nod nu trebuie sa fie mai mare decat K in timp ce cuplam.
