Thursday, December 11, 2014

ACM 1502. Domino Dots / Точки домино

  If we sort the domino figures by one side we will get the following set, 0/0 0/1 0/2...... 0/N, 1/1 ,1/2,....., N-1/N-1,  N-1/N,  N/N
so if the first number is M then the other number can be from M to N. The sum of numbers from 1 to K equals K*(K+1)/2. For calculating sum of numbers from M to N we need to take N*(N+1)/2 - (M-1)*M/2.  So for all the dominoes which have the first number of M we will have answer of N*(N+1)/2 - (M-1)*M/2 + (N-M+1)*M.


       FULL SOURCE CODE

No comments:

Post a Comment