Background
"Joanna, would you come here a minute, please?""Yeah. I'm sorry I was late, but I was having lunch. I, uh..."
"We need to talk about your flair."
"Really? I have fifteen pieces on. I also..."
"Well, fifteen is the minimum. Okay?"
"Okay."
"Now, it's up to you whether or not you want to just do the bare minimum or... Brian, for example has 37 pieces of flair on today. And a terrific smile. :-D"
"Okay, so you want me to wear more?"
"Joanna... People can get a cheeseburger anywhere, okay? They come to Chotchkie's for the atmosphere and the attitude. That's what the flair's about. It's about fun."
"Okay, so more then, yeah?"
"Look, we want you to express yourself, okay? Now if you feel that the bare minimum is enough, then, okay... but some people choose to wear more and we encourage that, okay? You do want to express yourself, don't you?"
"Yeah."
"Okay, great, great. That's all I ask."
Problem
Joanna wants to adjust her number of flair pieces. In order to do that, this is her method of choice:
- Take the set {1, 2, …, N}.
- Give each element a sign (+ or -).
- Evaluate the expression and add the result to her current flair number.
Joanna wants her flair number to either stay the same, or increase by as little as possible. Depending on how large the result is, our protagonist might decide to quit her crappy job and apply for a considerably better position at Endava. Your task is to tell Joanna her new flair number, using the aforementioned method.
Input
A single integer, N.
Output
A single integer, Joanna's new number of flair pieces.
Constraints
- 1 ≤ N ≤ 106
- Initially, Joanna has 15 pieces of flair.
- The printer got what it deserved.
- You will receive full feedback for this problem.
Sample
| Input | Output | Explanation |
|---|---|---|
| 1 | 16 | 15 + (+1) = 16 |
| 3 | 15 | 15 + (+1+2-3) = 15 |
Let's take into consideration a few cases:
- N % 4 == 0
- In this case, we can pair up complementary values (i and n-i+1) and give them the same sign. Because N is a multiple of 22, the number of pairs is an even number (N/2 is a multiple of 21). We have reduced the problem to an even number of identical values, which can be given alternate signs, in order to add up to 0. In this case, the answer is 15.
- N % 4 == 2
- In this situation, we cannot apply the method described above, because we get one extra pair. The best we can do is assigning alternate signs from the very beginning (-1 +2 -3 +4 -5 +6, and so on). Each pair of two consecutive values gives either a +1 or a -1. Because there is an extra pair, we can choose to either have a final result of 14 (which is not valid), or 16 (which is the best we can do, considering that the sequence contains an odd quantity of odd numbers, thus it cannot evaluate to zero - an even number). In this case, the answer is 16.
- N % 4 == 3
- In this situation, we can group the first three elements in a fixed manner: +1 +2 -3 (adding up to zero). This reduces the problem to the last N-3 values. Considering that N-3 is a multiple of 4, we can apply the strategy described in the first case. The answer is 15.
- N % 4 == 1
- The same idea goes for this case: we leave the first element by itself (+1) and reduce the problem to N-1 values (which is also a multiple of four, so a zero sum can be obtained). Just like the second case, which had a lower bound of 1 for the number of extra flair pieces, the answer is 16.
Python solution (Sergiu Puscas)
1 print 15 + [0, 1, 1, 0][input()%4]
