Diferente intre titluri:
Concursul National de Soft Grigore Moisil, Solutii
Concursul National de Soft Grigore Moisil Lugoj 2014, Solutii
Diferente intre continut:
h1. Solutii Concursul National de Soft Grigore Moisil Lugoj 2014
h1. 'Cerc5':problema/cerc5
Pentru primul joc, este necesara determinarea subsirului crescator de lungime maxima.
Pentru al doilea joc, se urmareste in O(K) pozitia poz pe care ajunge jucatorul 1 dupa efectuarea celor K mutari. Apoi, pe o tehnica similara aplicata invers se gasesc pozitiile de start ale lui poz - 1 si poz + 1.
h1. 'Perfect2':problema/perfect2
Pentru prima cerinta este necesara determinarea minimurilor si maximelor pentru coordonata x, respectiv y.
Pentru a doua cerinta, fie DX = abs(A[1].x - A[i].x) si DY = abs(A[1].y - A[i].y). Segmentul este perfect daca niciun punct laticeal nu se afla pe segment, lucru adevarat daca si numai daca cmmdc(DX, DY) = 1.
h1. 'Android':problema/android
Problema se rezolva cu programare dinamica. Ne vom construi un tablou bidimensional cu urmatoarea semnificatie: dp[conf][i] = numarul de posibilitati de a ajunge in nodul i, avand vizitate toate nodurile corespunzatoare bitilor de 1 din conf.
dp[conf][i] = sum(dp[conf - (1 << i)][j]), astfel incat toate celelalte puncte dintre i si j sa fie deja vizitate.
Pentru 100 de puncte, este necesara o precalculare a punctelor dintre i si j. Complexitate finala O((N * M)^2^ * 2^N * M^)
h1. 'Matperm2':problema/matperm2
Se observa ca din punctul de vedere al pozitiilor, la fiecare pas va avea acelasi efect. Astfel, putem obtine matricea dupa primul set de operatii si sa o transformam intr-o permutare de lungime N * M. Rezultatul ar fi permutarea compusa de P ori. Se pot obtine 70 de puncte cu ridicare la putere in timp logaritmic. Pentru 100 de puncte este necesara observatia ca ciclurile din permutare sunt independente intre ele. Astfel, problema se poate rezolva printr-o singura parcurgere a permutarii. Complexitate finala O(N * M).
Diferente intre securitate:
Topicul de forum nu a fost schimbat.
