Codeforces Round #308 (Div 2) Editorial

Правка en2, от hsk, 2015-06-23 23:37:43

552A - Vanya and Table For each rectangle she adds ,the value of all the cells in that rectangle is increased by one. Hence it is obvious that if a rectangle of side n*m is added ,the ans increases by n*m

for each rectangle

scan(x1)

scan(y1)

scan(x2)

scan(y1)

ans=ans+(x2-x1)*(y2-y1)

Time ComplexityO(n)

552B - Vanya and Books By number of digits the question means the total number of digits.

Hence number of digits for 1=1

number of digits for 10=2

number of digits for 100=3

We need to write all numbers from 1-n We find the number of digits in n (lets call it k).

Ans=(the number of digits in all 1 digit numbers)+(number of digits in all 2 digit numbers)+...(number of digits in all k-1 digit numbers)+number of digits from 10^k to n.

As the number of p digit numbers = 9*pow(10,p-1)

for(i from 1 to k) ans=ans+i*(9*pow(10,k-1))

And finally ans=ans+(n-pow(10,k-1)+1)*k

Time ComplexityO(log(n))

552C - Vanya and Scales The problem is a simple case of recursion.We have weights of the form w^k(0<k<100). if there exists a combination of weights that forms the mass M , then

M=summation(w^k1)-summation(w*k2)

Hence M has to be of the form w*t+k (-1<=k<=1)

t also has to be of the form w*t1+k1 (-1<=k1<=1)

Hence the recursion continues . The base case is when t<w.The answer will be yes if t=w-1||t=1||t=0

Time ComplexityO(log(M))

552D - Vanya and Triangles

The problem can be solved by a simple brute force for all the points in pairs of 3.If the area of a given pair of 3 triangles is not zero , then it is a possible triangle.

for(i from 0,n-1) - for(j from i,n-1) - — for(k from j,n-1) - — — if (area (i,j,k)!=0) - — — ans++;

Time ComplexityO(n^3)

The

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en13 Английский hsk 2015-06-24 14:58:11 11
en12 Английский hsk 2015-06-23 23:59:39 0 (published)
en11 Английский hsk 2015-06-23 23:58:44 11
en10 Английский hsk 2015-06-23 23:56:40 41
en9 Английский hsk 2015-06-23 23:54:56 4
en8 Английский hsk 2015-06-23 23:54:23 198
en7 Английский hsk 2015-06-23 23:49:57 48
en6 Английский hsk 2015-06-23 23:48:05 2 Tiny change: 'rom 1 to k)\n\n- an' -> 'rom 1 to k-1)\n\n- an'
en5 Английский hsk 2015-06-23 23:47:17 3 Tiny change: ' 1 to k)\n ans=ans+' -> ' 1 to k)\n\n- ans=ans+'
en4 Английский hsk 2015-06-23 23:46:04 458
en3 Английский hsk 2015-06-23 23:41:00 345
en2 Английский hsk 2015-06-23 23:37:43 361
en1 Английский hsk 2015-06-23 23:34:36 1453 Initial revision (saved to drafts)