Problem A
RGB Hydra
Languages
en
sv
This terrifying creature can have heads of three different colors. Initially, the Hydra has:
-
$R$ red heads,
-
$G$ green heads, and
-
$B$ blue heads.
Each time the hunter cuts off a head of a particular color, two new heads instantly grow back - one of each of the other two colors. For example, if the hunter cuts off a red head, then a green and a blue head will grow back immediately.
Driven by courage and ambition, the hunter not only wants to defeat the Hydra but also leave a lasting trace of the journey. To do this, the hunter wants as much red as possible to be visible on the Hydra - the goal is to maximize the number of red heads!
Before the Hydra launches its attack, the hunter has enough time to make at most $k$ moves, where each move involves cutting off a single head.
What is the maximum number of red heads the Hydra can have after at most $k$ moves?
Input
The input consists of a single line containing four integers $R$, $G$, $B$, and $k$ ($0 \leq R, G, B, k \leq 10^{18}$), where:
-
$R$ is the number of red heads,
-
$G$ is the number of green heads,
-
$B$ is the number of blue heads,
-
$k$ is the maximum number of moves the hunter can perform.
It is guaranteed that the Hydra has at least one head initially, i.e., $R + G + B \geq 1$.
(Note that the numbers $R, G, B, k$ are very large, and in languages like C++, you will need to use long long instead of int.)
Output
Print a single integer: the maximum number of red heads the Hydra can have after at most $k$ moves.
Scoring
Your solution will be tested on a set of test groups, each worth a number of points. Each test group contains a set of test cases. To get the points for a test group you need to solve all test cases in the test group.
|
Group |
Points |
Constraints |
|
$1$ |
$20$ |
$R, G, B, k \leq 10$ |
|
$2$ |
$15$ |
$k \leq R, G, B$ |
|
$3$ |
$10$ |
$R = 0$ |
|
$4$ |
$10$ |
$G = 0$ |
|
$5$ |
$10$ |
$B = 0$ |
|
$6$ |
$35$ |
No additional constraints. |
Explanation of Samples
The Hydra initially has only 1 blue head, and the hunter can make at most 1 move. The only move that can be made is to cut off the blue head, which results in 1 red head and 1 green head. No more moves can be performed, which means that 1 red head is the maximum number.
The Hydra has 4 red heads, 3 green heads, and 2 blue heads, and the hunter can make at most 1 move. The hunter can, for example, choose to cut off a green head, which results in 5 red heads, 2 green heads, and 3 blue heads. After this move, no further moves can be performed. There is no way to get more than 5 red heads, so the answer is 5.
The Hydra has 10 heads of each color. Since the hunter cannot make any moves (as $k = 0$), the number of red heads remains 10.
| Sample Input 1 | Sample Output 1 |
|---|---|
0 0 1 1 |
1 |
| Sample Input 2 | Sample Output 2 |
|---|---|
4 3 2 1 |
5 |
| Sample Input 3 | Sample Output 3 |
|---|---|
10 10 10 0 |
10 |
| Sample Input 4 | Sample Output 4 |
|---|---|
926332030620250124 57836736120250125 503852839920250126 804672315982687419 |
1731004346602937543 |
