Skip to main content

Codeforces Global Round 6

Codeforces Global Round 6

A. Competitive Programmer

According to the problem statement you are given some digits ( 0 - 9 ) , is it possible to make a number using all digits which is divisible by 60 ?


To make a number from the digits which is divisible by 60, we need a zero and more than one even digits and digits sum must be divisible by 3.

Code :



B. Dice Tower


According to the the picture given in the problem the sum of any two oppsite side of the dice is 7. Accept top dice , sum of all visible side pips in a dice is 21 - 7 = 14.
We can make a tower , which all visible pips is equal to n , if
n = 14 * d + 14 + pip
n = 14 * D + pip

where pip = { 1, 2, 3, 4, 5, 6 }

Code :


Labels:

Comments

Post a Comment

Popular posts from this blog

Histogram - LOJ

It's a well-known problem and the well-known solution is using a stack. I tried to solve it by segment tree( iterative version for building tree ) and got TLE. Hope I can optimize the code.  TLE CODE 
Post a Comment
Read more

Calculating 10^18th Fibonacci number by Matrix Expo Feat Spoj TSHOW2 - Fibonacci brain

Problem  :  TSHOW2 - Fibonacci brain Solution : We can easily calculate nth Fibonacci number by dynamic programming using the recurrence relation - \[ { f(x) } = \left\{ \begin{array}{ll} { f(x-1) + f(x-2) } & \mbox{if } x > 2 \\ 1 & \mbox{if } x = 2 \\ 0 & \mbox{if } x = 1 \end{array} \right. \] f[1] = 0 f[2] = 1 for i in { 3 ... n } f[i] = f[i-1] + f[i-2] But we cannot calculate Fibonacci number by dynamic programming when n is large like 10^18. We can easily calculate large 10^18 Fibonacci number by  matrix exponentiation . We can write that, \[ \begin{bmatrix} {1} & {1} \\ {1} & {0} \end{bmatrix} ^ {n} = \begin{bmatrix} { f(n+1) } & { f(n) } \\ { f(n) } & { f(n-1) } \end{bmatrix} \] n is large , using binary exponentiation we can calculate nth Fibonacci number by O(log n) complexity.    
Post a Comment
Read more