This Wednesday on 18:35 I did not have anything better to do than competing in codeforces.com. I have just finished work at 18:00 and I managed to get home before the start of the competition and even to get a sandwich in between. 🙂
The first question was easy and probably that is why I was not given any points at it – I simply did not code it well – it passed the first tests and I started to read the next one. Anyhow, lesson learned, next time I will make sure not to lose points that easily.
The second question was interesting – usually the second question in codeforces.com is solved with an easy algorithm, without the usage of some advanced data structures, so my chances here are quite high. This time it was the following:
There are n cities in Bearland, numbered 1 through n. Cities are arranged in one long row. The distance between cities i and j is equal to|i - j|.
Limak is a police officer. He lives in a city a. His job is to catch criminals. It’s hard because he doesn’t know in which cities criminals are. Though, he knows that there is at most one criminal in each city.
Limak is going to use a BCD (Bear Criminal Detector). The BCD will tell Limak how many criminals there are for every distance from a citya. After that, Limak can catch a criminal in each city for which he is sure that there must be a criminal.
You know in which cities criminals are. Count the number of criminals Limak will catch, after he uses the BCD.
The first line of the input contains two integers n and a (1 ≤ a ≤ n ≤ 100) — the number of cities and the index of city where Limak lives.
The second line contains n integers t1, t2, …, tn (0 ≤ ti ≤ 1). There are ti criminals in the i-th city.
Print the number of criminals Limak will catch.
After I read twice the description and the test samples, I realized what the author wanted to say – the idea is that the bear knows always how many criminals are there in his city and for every 2 cities, distanced on the same direction from his city he knows the criminals only if the total is 0 or 2. E.g. on the picture below the bear does not know in which city (2 or 4) is the criminal, thus it simply ignores him. If there is only one city, that can be reached through a certain number of steps, the bear knows the criminals as well. E.g. if in city 6 there was a criminal, the bear would have caught it. Thus, we have in total three cases.
My algorithm was the following – I count the criminals in the city of the bear and then I split the cities into two lists – from the first to the city of the bear and from the city of the bear to the last one. I reverse the first list and I start comparing the positions. If the positions are equal, then I add the number of criminals to the result. Usually one list is longer than the other. For the positions in the longer list I have added all criminals to the result. It took me some time to find out the logic, but once I was ready and I fixed a small bug I was given full points.
Pretty much that’s all. Here comes the code from the competition (not exactly quality code, but working):
|
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 |
using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.Threading.Tasks; class problem_8june2016_02 { static void Main() { int[] int_line1 = Console.ReadLine().Split(new char[] { ' ' }).Select(int.Parse).ToArray(); int[] int_line2 = Console.ReadLine().Split(new char[] { ' ' }).Select(int.Parse).ToArray(); int int_cities = int_line1[0]; int int_capital = int_line1[1]-1; int int_result = 0; List<int> list_left = new List<int>(); List<int> list_right = new List<int>(); for (int i = 0; i < int_cities; i++) { if (i < int_capital) { list_left.Add(int_line2[i]); } if (i > int_capital) { list_right.Add(int_line2[i]); } } list_left.Reverse(); int max_len = Math.Min(list_left.Count, list_right.Count); int another_len = Math.Max(list_left.Count, list_right.Count); for (int i = 0; i < max_len; i++) { if (list_left[i]==list_right[i]) { int_result += list_left[i] * 2; } } //list_left.Reverse(); List<int> list_last = new List<int>(); if (list_left.Count>list_right.Count) { list_last = list_left; } else { list_last = list_right; } for (int i = max_len; i < another_len ; i++) { int_result += list_last[i]; } int_result += int_line2[int_capital]; Console.WriteLine(int_result); } } |
The code is in GitHub here.
Enjoy it! 😀