Editorial for COCI '06 Contest 5 #4 Liga

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.

Let the five numbers be $A$ ~A~, $B$ ~B~, $C$ ~C~, $D$ ~D~ and $E$ ~E~. We know that $A=B+C+D$ ~A=B+C+D~ and $E=3B+C$ ~E=3B+C~. Additionally, all numbers are integers, at least $0$ ~0~, and $A$ ~A~ is at most $100$ ~100~.

The sample data shows that cases where one or two numbers are missing can be solved. It is less obvious that cases where three numbers are missing can be solved, and even some cases where four are missing (for example, 0 ? ? ? ? or ? ? ? ? 300).

Note first that $A$ ~A~ and $D$ ~D~ can't both be unknown, except in the special case when $A=B+C=100$ ~A=B+C=100~ and $D=0$ ~D=0~. If $A$ ~A~ and $D$ ~D~ were unknown, it would be possible to increase or decrease both numbers by one, and the solution would not be unique.

With that in mind, notice that if $B$ ~B~ and $C$ ~C~ are known, then all other numbers can be calculated. The solution tries every possible pair $(B,C)$ ~(B,C)~ (each of the numbers is either fixed, or we try all values between $0$ ~0~ and $100$ ~100~), calculates the other numbers and checks if the quintuplet satisfies the conditions.

Comments

There are no comments at the moment.