Asa facusem deque de prima data.
Citirea o fac

Cod:

scanf( "%d", &x );

Si.. TLE pe ultimele 2 teste. Nu vad ce as putea imbunatati, cu exceptia citirii.
Cum se poate face mai eficient?

Iau TLE pe ultimele doua teste pe solutia O(n). Am incercat atat implementarea C, cu citire standard si deque implementat pe vector, cat si C++, cu deque din STL.
Care ar putea fi problema? 

Desi poate parea hilar, eu unul nu folosesc RHIDE pentru ca am o senzatie de discomfort cand rulez o aplicatie facuta pt. dos si portata in linux... cu toate ca iti poti duce treaba la bun sfarsit, it's not done the *nix way.

pai rhide in linux compileaza cu gcc - compilator de linux, deci nu porteaza nimic; unde intervine dos-ul in toata treaba? 

Am rezolvat problema descompunand numerele in baza 2; astfel primesc cam 0.8 s pe testul maxim (cu unele optimizari). Am vazut ca sunt totusi rezolvari care scot 0.02 s pe testul maxim.. are cineva vreo idee?

atunci numarul de numere cu proprietatea cautata este
phi(n)=n(1-1/p1)(1-1/p2)...(1-1/pk)

te referi la functia lui Euler phi(N), care returneaza numarul de intregi mai mici ca N si primi cu N.
Problema era sa aflu cate numere mai mici ca x si prime cu n sunt..
Ideea ramane cam aceeasi, numai ca se modifica putin forma finala.

Da.. de fapt, ori cu teorema lui Pick, ori fara, ajungi la acelasi rezultat

am gasit.. greseala era la formula pentru s(i,j).
o intrebare: daca am un dreptunghi de m x n puncte laticeale, cate puncte se afla "sub" diagonala principala?

[later edit] tocmai imi dadusem si eu seama - am facut brute-force si am vazut ca pierdeam cateva din vedere. ms mult oricum, bogdan

is sigur
uite cum fac: notez cu s(i,j) numarul paralelogramelor care se incadreaza perfect intr-un dreptunghi de i x j (inclusiv dreptunghiul insusi). Astfel gasesc ca s(i,j) = ij + (i-1) + (j-1)
Apoi notez cu f(i,j) numarul locurilor in care pot translata paralelogramele care se incadreaza perfect in i x j; obtin f(i,j) = (n-i+1)*(m-j+1);
Solutia problemei devine Suma (1<=i<=n; 1<=j<=m) din ( s(i,j) * f(i,j) )
Asta verifica pentru (1,1), (1,2), (2,1), (2,2); pentru (3,2) da 58...
wtf is wrong? 

am gasit o metoda de rezolvare care mi se pare corecta (am verificat "manual" pentru (1,1), (1,2), (2,2)); totusi, iau WA pe toate testele;
pentru n=3 m=2, am gasit 58 de paralelograme; asta e raspunsul corect?

e un algoritm pentru determinarea TUTUROR drumurilor minime intre doua varfuri ale unui graf; construieste un graf partial in care orice drum intre cele doua varfuri este minim).

e un algoritm (probabil denumit impropriu) in culegerea de probleme a Doinei  H. Logofatu pentru determinarea infasurarii convexe (gasesti o descriere a lui acolo); surprinzator, pe google nu gasesti mai nimic..

cam trebuie sa folosesti principiul includerii si excluderii.. altfel nu prea vad cum poti rezolva problema

exact la asta ma refeream
inseamna ca solutia ar fi sa il factorizez pe n si pentru o intrebare de tipul "cate numere mai mici ca x si prime cu n sunt?" sa aplic includere/excludere pentru toti factorii primi obtinuti. numai ca apar s-ar putea sa apara prea multi factori primi in descompunerea lui n, si atunci aplicarea pricipiului includerii si excluderii e destul de  

cum se poate raspunde eficient la o intrebare de tipul "cate numere mai mici decat x sunt prime cu y?" (preferabil fara a-l factoriza pe y)  

intelectul tau superior cred ca va lua foc....

da...

Si evaluatoru' ce standarde trebuie sa
indeplineasca?
dati mai multe detalii.  

ma refeream la monitor, unde arata ca evaluatorul e cam obosit...

de azi (03 04 2004) de pe la ora 14
apare mesajul asteapta la rand.
cam plictisitor sa astepti atat...