Editorial for COCI '09 Contest 1 #2 Domino


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

This task can be solved by solving the mathematical problem behind it and simply calculating the solution using that formula. However, the constraints were small enough that a more programming oriented solution exists. First note that if we take a particular domino we can turn it so that the first number on the domino is the smaller one (if they are both equal it's doesn't matter anyhow). Now we can sort all tiles by their smaller number first, and break ties using their larger number if necessary. Since each tile appears only once, this gives us a simple ordering which we can traverse. Going tile by tile and summing dots gives us the following code:

For each i from 0 to N
    For each j from i to N
        solution = solution + i + j

Comments

There are no comments at the moment.