In the new 2017 I have decided to take a new look at CodeForces and what do they bring us.
After all, this is one of the very few “places” in the world, where you can compete with the world class developers. Its like playing football vs. Cristiano Ronaldo and Messi in a team :).
Thus, I have resolved easily the first problem of the GoodBye 2016 competition and I started striving for number 2. There, you had the following task:
In this problem we assume the Earth to be a completely round ball and its surface a perfect sphere. The length of the equator and any meridian is considered to be exactly 40 000 kilometers. Thus, travelling from North Pole to South Pole or vice versa takes exactly 20 000 kilometers.
Limak, a polar bear, lives on the North Pole. Close to the New Year, he helps somebody with delivering packages all around the world. Instead of coordinates of places to visit, Limak got a description how he should move, assuming that he starts from the North Pole. The description consists of n parts. In the i-th part of his journey, Limak should move ti kilometers in the direction represented by a string dirithat is one of: “North“, “South“, “West“, “East“.
Limak isn’t sure whether the description is valid. You must help him to check the following conditions:
- If at any moment of time (before any of the instructions or while performing one of them) Limak is on the North Pole, he can move only to the South.
- If at any moment of time (before any of the instructions or while performing one of them) Limak is on the South Pole, he can move only to the North.
- The journey must end on the North Pole.
Check if the above conditions are satisfied and print “YES” or “NO” on a single line.
Pretty much, what I understood, was that the poor bear Limak can be given any number of kilometers, and if it reaches one of the poles, it has to go back. E.g., if the bear is given 1,000,000 kilometers it simply makes 25 rounds around the globe and does not even bear to complain about it 🙂 After all, that’s its faith 🙂 Thus, I somehow thought that the problem is a bit difficult even for a second problem, but after all, this is codeforces and the difficulty there is getting more and more difficult. Thus, I coded something like this:
|
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 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 |
using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.Threading.Tasks; class cf002 { const int intSizeLine = 20000; const int intSizeLine2 = 40000; const string SOUTH = "S"; const string NORTH = "N"; static int y; static void Main() { int n = int.Parse(Console.ReadLine()); y = 0; for (int i = 0; i < n; i++) { string strInfo = Console.ReadLine(); int intSize = int.Parse(strInfo.Split()[0]); string strDirection = strInfo.Split()[1].Substring(0, 1); if (y == 0) { y = GetY(intSize, SOUTH); } else if(y == intSizeLine) { y = GetY(intSize, NORTH); } else if (strDirection == SOUTH) { y = GetY(intSize, SOUTH); } else if (strDirection == NORTH) { y = GetY(intSize, NORTH); } } if (y==0) { Console.WriteLine("YES"); } else { Console.WriteLine("NO"); } } public static int GetY(int intValue, string strDirection) { int intResult = 0; int intLeft = 0; if (intValue >= intSizeLine2) { intValue -= (intValue / intSizeLine2) * intSizeLine2; } switch (strDirection) { case NORTH: if (y-intValue<0) { intLeft = y; intValue -= intLeft; if (intValue > intSizeLine) { intValue -= intSizeLine; intResult = GetY(intValue, NORTH); } else { intResult = intValue; } } else { intResult = y - intValue; } break; case SOUTH: if (intValue+y>intSizeLine) { intLeft = intSizeLine - y; intValue -= intLeft; if (intValue > intSizeLine) { intValue -= intSizeLine; intResult = GetY(intValue, SOUTH); } else { intResult = intSizeLine - intValue; } }else { intResult = y + intValue; } break; } return intResult; } } |
Well, as you can imagine it was wrong on at least two levels. The first level is that the poor bear does not like it when it should change automatically directions. But there was more. In my idea, if the bear was in the south pole and was given any type of task, it automatically starts moving north. E.g., if it is told to go West, it simply starts moving north. Well, it was not it. After some trial and error (and checking the solutions of some people) I found out that I was really over complicating it. The real solution looks like this:
|
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 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 |
using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.Threading.Tasks; class cf750_02 { const int intSizeLine = 20000; const string SOUTH = "S"; const string NORTH = "N"; static bool violation = false; static int y; static void Main() { int n = int.Parse(Console.ReadLine()); y = 0; for (int i = 0; i < n; i++) { string strInfo = Console.ReadLine(); int intSize = int.Parse(strInfo.Split()[0]); string strDirection = strInfo.Split()[1].Substring(0, 1); if (y == 0 && strDirection!=SOUTH) { violation = true; } if (y == intSizeLine && strDirection != NORTH) { violation = true; } if (strDirection == SOUTH) { y = GetY(intSize, SOUTH); } else if (strDirection == NORTH) { y = GetY(intSize, NORTH); } } if (y == 0 && !violation ) { Console.WriteLine("YES"); } else { Console.WriteLine("NO"); } } public static int GetY(int intValue, string strDirection) { int intResult = 0; switch (strDirection) { case NORTH: if (y - intValue < 0) { violation = true; return intResult; } else { intResult = y - intValue; } break; case SOUTH: if (intValue + y > intSizeLine) { violation = true; return intResult; } else { intResult = y + intValue; } break; } return intResult; } } |
And the only reason it looks so big, is that I actually used my first solution to build the second one. But it worked 🙂
If due to some reason, you need to see the solution in GitHub, it is here.
Enjoy it! 🙂