Magic tickets are considered the tickets in which the sum of the left digits is equal to the sum of the right digits. E.g., if you ticket is number 124016 it is a magic ticket, because 1+2+4 = 0 + 1 + 6. Knowing this, I was a bit interested in one of the problems in CodeForces. The problem is the following: 
Luba has a ticket consisting of 6 digits. In one move she can choose digit in any position and replace it with arbitrary digit. She wants to know the minimum number of digits she needs to replace in order to make the ticket lucky.
The ticket is considered lucky if the sum of first three digits equals to the sum of last three digits.
You are given a string consisting of 6 characters (all characters are digits from 0 to 9) — this string denotes Luba’s ticket. The ticket can start with the digit 0.
Print one number — the minimum possible number of digits Luba needs to replace to make the ticket lucky.
Whoever Luba is, its obvious that the problem is not as easy as it may seem. I tried to solve it with some modulo operator, trying to come up with an easy solution. However, I have underestimated the 145 tests, which were testing about 145/1000000 of the possible inputs. Thus, I have decided to follow the tag on the problem and simply to brute force it. The brute force solution is quite easy – you need to calculate the 1 million possibilities of the ticket. Then to take the magic ones out of these (function blnIsMagic in the solution). And as step 3, to compare for each magic variation how many digits are different from the current ticket (function intCompareTwo). The minimum answer is the answer of the problem.
This 3 step solution was not difficult to be implemented:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 |
using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.Threading.Tasks; class Startup { static void Main() { int intAnswer = int.MaxValue; int intCurrentAnswer = int.MaxValue; string strInput = Console.ReadLine(); for (int i = 0; i <= 999999; i++) { if (blnIsMagic(i)) { intCurrentAnswer = intCompareTwo(i, strInput); intAnswer = Math.Min(intCurrentAnswer, intAnswer); } } Console.WriteLine(intAnswer); } public static int intCompareTwo(int intA, string strInput) { string strA = intA.ToString("D6"); int intAnswer = 0; for (int i = 0; i < 6; i++) { if (strA[i]!=strInput[i]) { intAnswer++; } } return intAnswer; } public static Boolean blnIsMagic(int intInput) { string strWhole = intInput.ToString("D6"); string strLeft = strWhole.Substring(0, 3); string strRight = strWhole.Substring(3, 3); int intLeftSum = 0; int intRightSum = 0; for (int i = 0; i < 3; i++) { intLeftSum += int.Parse(strLeft[i].ToString()); intRightSum += int.Parse(strRight[i].ToString()); } return (intLeftSum==intRightSum); } } |
Cheers!