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(n))