Coin Exchange

시간 제한1초메모리 제한2048 MB

요약
다섯 종류의 동전 개수와 제한된 횟수의 Drowned에서 Bleakmarch 전환이 주어질 때, 방향성 환율을 이용해 얻을 수 있는 Crimson 동전의 최댓값을 구한다.
난이도

어려움10점 중 8점

유형
수학, 그리디, 완전 탐색
정답자
아직 제출이 없습니다

문제

Lorenzo of Valtier is a traveling merchant navigating the fractured realms of the Five Kingdoms. Each nation mints its own unique coins using secretive forging techniques, creating a hidden economy of conversions:

Currencies

  • Aetherspire Dominion: Obsidian discs etched with celestial runes (Aetherspire Coin)
  • Bleakmarch Protectorate: Bone-white tetrahedrons that scream when heated (Bleakmarch Coin)
  • Crimson Falconate: Blood-veined square that warm before storms (Crimson Coin)
  • Drowned King’s Reach: Barnacle-encrusted hexagons that smell of brine (Drowned Coin)
  • Emberveil Syndicate: Geometric amber prisms containing frozen flames (Emberveil Coin)

Exchange Rates (Black Market, One-way Currency Exchange):

  • 33 Aetherspire →→ 11 Bleakmarch ("Three stars bow to the Pale Lord")
  • 33 Bleakmarch →→ 11 Crimson ("The Bloodied Falcon’s Toll")
  • 55 Aetherspire →→ 11 Crimson ("Stardust to Blood" smuggling route)
  • 33 Emberveil →→ 22 Drowned ("Fire drowns in black waters")
  • 33 Bleakmarch →→ 44 Emberveil ("Bleaching the Pale Mark")

Forbidden Technique: The Argentum Revenant Tome allows you to exchange 22 Drowned →→ 33 Bleakmarch ("Raising Drowned Silver") for a maximum of XX uses, after which the Pale Inquisition is triggered.

Given Lorenzo of Valtier’s initial coin stash and a limit of XX on the number of times the forbidden technique may be used, your goal is to maximize the number of Crimson Falconate coins that can be obtained using a series of exchanges. Solving this puzzle may unlock the secret behind how Lorenzo of Valtier became wealthy!

Figure 1: Echange Rates. (Coin images created by DALL·E-3)

입력

A line containing six integers: AA (Aetherspire Coin), BB (Bleakmarch Coin), CC (Crimson Coin), DD (Drowned Coin), EE (Emberveil Coin), XX (maximum use of the Forbidden Technique) satisfying 0≤A,B,C,D,E,X≤1090≤A,B,C,D,E,X≤10^9.

출력

A single integer indicating the number of maximum possible Crimson Coins that can be obtained using a series of zero or more of exchanges.

예제3

  1. 예제 1

    입력
    1 2 3 4 5 6
    
    예상 출력
    7
    
  2. 예제 2

    입력
    5 5 5 5 5 5
    
    예상 출력
    11
    
  3. 예제 3

    입력
    1000000000 0 500000000 123 456789 1000000000
    
    예상 출력
    950114243