Din cate inteleg intrebarea ta este: Setul de noduri pe care il aleg asa acopera toate LCA-urile nodurilor negre?
Raspunsul este da, hai sa vedem de ce.
Numim setul de LCA-uri ce trebuie gasit S
Fie un nod x care face parte din S (unul din alea care trebuie gasit). Trebuie sa demonstram ca algoritmul tau in gaseste pe x. x se afla in S, deci exista 2 noduri negre in subarbori diferiti ai lui x, pe care ii notam A1, A2. Daca A1 si A2 sunt subarbori consecutivi (nu exista un nod negru in V intre nodurile negre din A1 si nodurile negre din A2), atunci e evident ca va exista in V un nod negru din A1 langa un nod negru din A2. Daca A1 si A2 nu sunt subarbori consecutivi (exista cel putin un nod negru in V intre nodurile negre din A1 si nodurile negre din A2) atunci in V vom avea o secventa de forma (...nA1, nA1, nA1, a, b, c,...., p, nA2, nA2...)
unde nA1 = un nod negru din A1, nA2 = un nod negru din A2, a, b, c, d,...p noduri negre random, consecutive din subarbori ai lui x, care se afla intre A1 si A2. Cand faci LCA (ultimul nA1, a) o sa-l gasesti pe x. Ambele cazuri sunt satisfacute, deci x va fi gasit de algoritmul tau, no matter what.
Sper ca ai inteles dem, daca ai vreo nelamurire/am ratat ceva, da un PM sau scrie aici

N-am rezolvat inca problema, dar este un caz particular al pb. Enigma (acolo trebuind sa alcatuiesti X-ul din prefixe din cuvintele date; aici trebuie din intregul cuvant, iar aici se cere nr. minim de cuvinte, in loc de nr de moduri) deci probabil intra si trie + dinamica inainte. Vezi care dintre solutii ti se pare mai usor de implementat..

Cod:

if (i-prec>dif && prec >= A)

..tu gasesti doua prime, din care unu poate sa fie mai mic decat A in forul ala si zici la sfarsit ca daca perechea pe care ai gasit-o e mai mica decat a n-ai solutie, ceea ce e gresit. Ex, ai a = 11, b = 13...o sa iti dea -1, chiar daca ai solutie..

E probabil din cauza faptului ca vectorul ala de stringuri b nu are caracterul '\0' la sfarsit, iar cand faci fout << b[ i ] iti crapa, de-asta nu iti arata nici in editor raspunsul. Incearca sa pui la sfarsitul forului in care atribui, b[ l ][ n ] = '\0' si vezi daca iti merge.

Da, ai dreptate, mersi.

Am incercat sa abordez problema in modul urmator si sunt curios daca ar fi intrat pentru limite:

Consider initial N multimi disjuncte (fiecare multime asociata unui nod). In fiecare multime tin in "radacina" ei toate Query-urile aferente, ex: daca in multimea X aveam nodurile 6, 4 si 1, atunci tineam in X toate query-urile referitoare la 1, 4 si 6 sortate crescator dupa K (nr de elemente necesar in multime).

Sortez muchiile dupa valoare descrescator si le parcurg, una cate una, facand join de cele 2 multimi legate de muchia respectiva. De fiecare data cand fac join de 2 multimi, scot din fiecare Query-urile la care pot sa raspund si updatez in vectorul de Answer cu valoarea ultimei muchii luate, acum ca am K' = K1 + K2. Apoi fac merge pe cei 2 vectori de Query-uri, bagand vectorul rezultat in multimea rezultata. Mi s-a parut ok rezolvarea dar am crapat memoria si eram curios daca ar fi intrat o sursa pe ideea asta.

Referitor la a 9a...

In rest, nu mai am alte comentarii. Sunt curios sa vad si restul subiectelor.

Faci o impartire si o inmultire. Nu ai cum sa stii ce ordin de marime va fi rezultatul din cauza ca nu ai K si R ca valori decat din input (daca ai o data K = 5 si o data K = 1000, iti shifteaza zecimala cu 3 pozitii, adica compari 3.14159 * 1000 = 3141.59000 la a 5a zecimala). Daca iei destule zecimale nu mai are cum sa crape.

Luai pentru P1 = 1, vedeai de la coada la cap care e P2 corespunzator, apoi, te plimbai spre dreapta cu ambii pointeri (cu P1, si cu P2, dupa cum era cazul, ca sa minimizezi diferenta intre A2 si A3).

Cum ati facut sa intre precizia? Am incercat mai multe modalitati (toate cu cautare binara) pe int si pe reale, cu precizia -5, -6, dar nu mi-a intrat...

Datorita inputului de forma distante, n-ar putea sa existe 2 posibilitati de asezare a primului punct (sub axa si deasupra axei, simetric) in partea stanga? Daca da, pe care il luam?

Not sure daca e vreun algoritm de dp care sa mearga, dar poti sa faci altfel. Pentru fiecare sir imparte numerele in 3 multimi in functie de rest.

Incearca sa declari vectorii mari in afara mainului (pe heap ai mai mult decat pe stiva). Asa ar trebui sa nu mai ai KBS-uri.
BTW: "renul despre care discutam este format dintr-o locomotiva si N vagoane"...made my day.

Scuze, nu realizasem ca e a 9a...ce-i drept nu m-as mira ca la o locala sa dea subiecte aiurea.
Mi se pare mult mai simplu

Cod:

#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#define ll long long
using namespace std;

int N;
priority_queue <ll, vector <ll>, greater <ll> > Hp;
int k = 1;
ll last;

ll Aflare ()
{
	Hp.push (1);
	while (k < N)
	{
		while (Hp.top () == last) Hp.pop ();
		ll a = Hp.top ();
		Hp.pop ();
		Hp.push (2*a);
		Hp.push (3*a);
		Hp.push (5*a);
		k++;
		last = a;
	}
	return Hp.top ();
}

int main ()
{
    cin >> N;
    cout << Aflare ();
    return 0;
}

decat o solutie care tine un vector de marime 3N de struct-uri de tipul {numar, exponent la care e ridicat 2, exp la care e ridicat 3, exp la care e ridicat 5} si un indice de tipul used[50][50][50] care iti zice daca ai mai luat numarul ala pana in momentul respectiv. In plus, solutia cu heap tine un element K de maxim 3 ori (exista 3 numere din care se poate ajunge la K, mai precis K/2, K/3, K/5. Nu vei analiza unul din aceste numere decat o singura data, deci e pretty obvious). Dimensiunea heapului e maxim 3N. Daca vrei mai putin de 3N memorie (chiar nu vad sensul) bagi arbore de cautare in loc de heap si e exact la fel, daca bagi stl. Scuze pentru posturi daca le considerati inutile.

E mai greu de implementat solutia N^2 decat NlogN din cauza ca trebuie sa tii un hash/vector de booli de tipul used[ i ][j][k], unde i iti indica puterea la care e ridicat 2, j = puterea la care e ridicat 3, etc. Dupaia trebuie sa mergi cu operatia ta pana la elementul N unde te opresti (O sa ai pana la 3N elemente in vector), si e destul de stupid de bagat imo.
Mai simplu, bagi intr-un heap numarul 1. Iei o variabila k = 1, si o variabila last = 0. Cat timp k < N faci asa:
Iei elementul minim din heap. Il numim "a". Daca a = last atunci il scoti pur si simplu. Altfel, scoti a si bagi la loc in heap 2a, 3a, 5a, incrementezi k-ul si last ia valoarea a. Altfel spus:

Cod:

priority_queue <int> Hp;
int k = 1, last;

void Aflare ()
{
	Hp.push (1);
	while (k < N)
	{
		while (Hp.top () == last) Hp.pop ();
		int a = Hp.top ();
		Hp.pop ();
		Hp.push (2*a);
		Hp.push (3*a);
		Hp.push (5*a);
		k++;
		last = a;
	}
}

Raspunsul e in Hp.top () acum.

Poate sa-mi aminteasca si mie cineva cum numarai cmlsc-urile, please?

sus, la projects, add file

Am raportat problema mai demult.
Intra afisarea standard, si poti sa faci problema sa intre, dar trebuie optimizari cu operatii pe biti, ex. nu ai nevoie cand treci de la un numar la urmatorul sa construiesti complet noul numar deoarece primii biti raman la fel, asa ca poti sa bagi LSB. Vad ca inafara de mine mai sunt 2 persoane care au facut-o sa intre pe principiul asta. Daca nu vrei sa astepti pana se schimba limita, poti sa-mi dai un PM sa te ajut.

PS: N-ar strica 0.25 in plus la timp.

Cred ca mergea si cu formula, da m-am incurcat in extremele conditionate

Translatezi sistemul de axe in centrul cercului si ai:
X = R(x1 + x2) / sqrt ((x1 + x2) ^ 2 + (y1 + y2) ^ 2)
Y = R(y1 + y2) / sqrt ((x1 + x2) ^ 2 + (y1 + y2) ^ 2)

Nu cred ca se pot gasi astea fara derivate.

*luai 70 cu 1 incorect , trist cand implementezi o dinamica in ultima ora, si te prinzi in ultimele 5 min de chestia asta...ma rog.

O proprietate:
ai 2 nr. a si b atunci a&b + a|b = a + b
1 & 1 = 1; 1 | 1 = 1; 1 + 1 = 2 (se shifteaza bitul);
1 & 0 = 0; 1 | 0 = 1; 1 + 0 = 1;
etc.
Asta se aplica pt orice biti de aceeasi importanta, deci luand separat toti bitii din cele 2 numere, practic se aplica individual operatia si o sa dea a + b (se aplica doar la 2 nr., la mai multe nu mai e asa)

Fie A = maximul, de forma a[n]a[n-1]...a[k]a[k-1]...a[1].
Cazul 1: Presupunem ca secventa de sushi maxim il contine pe A si se continua spre dreapta cu P numere (spre stanga e analog). Aceste P numere le vom numi numere considerate pentru secventa.
Fie primii biti de la a[n] la a[k+1] comuni la toate numerele considerate. (Poate sa fie nu fie niciun bit.) Aplicand si respectiv sau si adunand, raman neschimbati, deci rezultatul este acelasi cu primii biti din 2A (se shifteaza la stanga). a[n]...a[k + 1] e secventa comuna maxima a partii cele mai semnificative => exista un numar B in grupul de numere considerate de forma a[n]...a[k + 1]b[k]b[k -1]...b[1] cu b[k] != a[k]. Cum A > B => a[k]  = 1, b[k] = 0. Nu ne intereseaza primii biti de la a[n] la a[k +1], deci vom considera doar A' = 1a[k -1]a[k - 2]...a[1] si B' = 0b[k - 1]b[k - 2]...b[1]. Notam AND, rezultatul operatiei & pe grup, si OR, rezultatul operatiei | pe grup. =>  AND <= a[k -1]a[k -2]...a[1], iar OR <= 11...1 (k cifre de 1) = 1000..00 (k cifre de 0) - 1 => AND + OR  <= 1000..00 (k cifre de 0) - 1 + a[k - 1]a[k -2]...a[1], dar 2A' = 2(1000..00 (k - 1 zerouri) + a[k - 1]a[k - 2]...a[1]) = 10000..00 (k cifre de 0) + 2 * a[k - 1]a[k - 2]...a[1]. Comparam cele doua relatii:

AND + OR    ?   2A'
1000..00 (k zerouri) - 1 + a[k - 1]a[k -2]...a[1]    ?    1000...00 (k zerouri) + 2 * a[k - 1]a[k - 2]...a[1]
-1    ?    a[k - 1]a[k - 2]...a[1]
a[k - 1]a[k - 2]...a[1] >= 0, de unde => concluzia.

Alt caz ce trebuie analizat este cand secv. maxima nu include pe a. Notam numerele analog de forma X0b[1]b[2]b[3]...b[n] (a = X1a[1]a[2]...a[n]). Presupunem cazul maximal in care b[1] = b[2] =...b[n] = 1. Atunci aplicand sushi pe aceste numere se obtine X01111...110 (n de 1), in schimba 2a > (X1000...00 (n de 0) << 1 = X100...00 (n + 1 de 0)) deci > X011111...110, deci prob. e rezolvata.

LE: Am gresit ceva in demonstratie, o sa o rescriu.

LE2: Acum e corecta.

v[ i ] * 2
Am si demonstratie.

Se citesc in ordinea X1, Y1, X2, Y2?

Nici eu nu pot sa particip sambata asta. Nu ar fi rau deloc daca ati putea pune-o in alta zi   

Same here.

Testul:

Cod:

1
14:34:51,999 --> 15:44:12,999
Am gasit bug-ul.
Cand afisezi, baga g << "{" << ((int) nr) << "}";

Speaks for itself.

Puteti totusi sa va uitati peste problema asta. Stiu ca s-a luat 100 dar eu nu reusesc nicicum sa trec de 90. Chiar cred ca ar trebui marita putin limita

N-ar strica...Si eu m-am chinuit un pic. Incearca sa inversezi ordinea forurilor, sa faci dinamica invers, mie numai asa mi-a intrat.