CodeForces.com is really a nice place you can learn stuff. Learning by doing is probably what man actually needs in programming. Thus, I have taken the 2. Problem of the 2. Division in CodeForces, as far as it seemed interesting to me (and doable) 🙂
The problem looked like this. Pretty much, you have a number of columns of soldiers, who are marching either with the left or with the right foot. Each soldier decides for himself. Your target is to maximize the beauty of the whole parade, by giving order just to one column to swap feet. The question is which column should you change? Or the way CF explained it:
The first line contains single integer n (1 ≤ n ≤ 105) — the number of columns.
The next n lines contain the pairs of integers li and ri (1 ≤ li, ri ≤ 500) — the number of soldiers in the i-th column which start to march from the left or the right leg respectively.
Print single integer k — the number of the column in which soldiers need to change the leg from which they start to march, or 0 if the maximum beauty is already reached.
Consider that columns are numbered from 1 to n in the order they are given in the input data.
If there are several answers, print any of them.
|
1 2 3 4 |
3 5 6 8 9 10 3 |
|
1 |
3 |
Pretty good problem, actually seeming trivial. But it is definitely not that trivial. At least, 2-3 points may break the whole story. E.g., if you are used to using List.Sum() function, this is definitely not your exercise – you would not make it within the 1 second limit of the tests and you should think of something else. If you think that you can make this problem just with one loop, well, here it is probably not the case, you still need two.
Last but not least – you need some experience playing (or watching) sports like volleyball or tennis. In those sports, always when there is a point given to one of the team, the difference in the decision of the referee to which team to give the single point is actually equal to 2. E.g. if the current result is 13:16 and player A gets a point, the result is 14:16, but if player B gets the point, the result is 13:17. It’s the same with these soldiers. If all left soldiers change legs, the difference between left and right soldiers would be the number of those soldiers, doubled – e.g. we count away the soldiers, leaving “left” soldier sum and we add them to the “right” soldiers sum. Thus, the following part of the code is actually what makes the program run below a second, without using the expensive List.Sum():
|
1 |
int_current_beauty = Math.Abs(int_total_l - 2 * lst_left[i] + 2 * lst_right[i] - int_total_r); |
The whole code is here:
|
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 |
using System; using System.Collections.Generic; using System.Linq; class cf378_2 { static void Main() { string str_read = ""; int int_better_beauty = -1; int int_current_beauty; int int_row = 0; int int_total = int.Parse(Console.ReadLine()); int int_total_l = 0; int int_total_r = 0; List<int> lst_left = new List<int>(); List<int> lst_right = new List<int>(); for (int i = 0; i < int_total; i++) { str_read = Console.ReadLine(); lst_left.Add(int.Parse(str_read.Split()[0])); lst_right.Add(int.Parse(str_read.Split()[1])); int_total_l += int.Parse(str_read.Split()[0]); int_total_r += int.Parse(str_read.Split()[1]); } int int_initial_beauty = Math.Abs(int_total_l-int_total_r); for (int i = 0; i < int_total; i++) { int_current_beauty = Math.Abs(int_total_l - 2 * lst_left[i] + 2 * lst_right[i] - int_total_r); if ((int_current_beauty>int_better_beauty) && (int_current_beauty > int_initial_beauty)) { int_better_beauty = int_current_beauty; int_row = i+1; } } Console.WriteLine(int_row); } } |
Available also in GitHub here.
Enjoy it! 🙂