루미 알고리즘

#1607골드RGB Hydra

PO 2025 결선코딩출제 Harry Zhang영어 원문이 문제가 어렵다면 — 배우는 순서 보기

영어 원문입니다. 원문의 수식·표를 글자로 옮겨 모양이 다를 수 있습니다. 정확한 내용은 원문 페이지에서 확인하세요. 원문 페이지 열기 (새 창)

Problem

(그림은 원문 저장소에서 볼 수 있습니다)

While hunting monsters, the brave hunter encounters a Hydra. But this was not just any Hydra - this is an RGB Hydra!

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 cut off!

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 ≤ R, G, B, k ≤ 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 ≥ 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.

GroupPointsConstraints
120R, G, B, k ≤ 10
215k ≤ R, G, B
310R = 0
410G = 0
510B = 0
635No 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.

예제

예제 1

입력
0 0 1 1
출력
1

예제 2

입력
4 3 2 1
출력
5

예제 3

입력
10 10 10 0
출력
10

예제 4

입력
926332030620250124 57836736120250125 503852839920250126 804672315982687419
출력
1731004346602937543

출처 표기

출처: Programmeringsolympiaden 2025년 결선 · 원문 페이지 · 이용 조건 CC BY-SA · LaTeX 원문을 화면용 글로 옮겼습니다(수식·표의 모양이 다를 수 있습니다). 내용은 고치지 않았습니다.

크리에이티브 커먼즈 저작자표시-동일조건변경허락.

문제 출처: 한국정보올림피아드(KOI) (CC BY-NC-SA 4.0) · International Olympiad in Informatics (IOI) (CC BY) · Centre for Education in Mathematics and Computing (CEMC), University of Waterloo (CC BY-NC 4.0) · Programmeringsolympiaden (CC BY-SA) · CSES Problem Set (Antti Laaksonen) (CC BY-NC-SA 4.0). 루미 알고리즘은 위 단체들과 관계없는 별도의 서비스이며, 자료는 원문 그대로 싣습니다. 문제마다 출처와 이용 조건을 따로 표기합니다.