행성들을 구하라

이미지 출처: commons.wikimedia.org/

Balatro는 많은 사람을 사로잡은 게임이며, Elvar도 그중 한 명이다. Elvar는 Balatro를 매우 좋아하며, 지금은 자신의 최고 기록을 경신할 가능성이 높은 게임을 진행하고 있다. Balatro의 목표는 포커 족보를 플레이해 목표 점수 $x$에 도달함으로써 블라인드를 돌파하는 것이다. 모든 포커 족보는 서로 다른 칩 수와 배수를 가진다. 그러면 포커 족보의 총점은 chips $\cdot$ multiplier로 계산된다. 예를 들어 칩이 $50$개이고 배수가 $4$이면, 그 족보로 $200$점을 얻는다. 각 블라인드가 끝난 뒤에는 조커, 타로 카드, 행성 카드를 구매하여 더 많은 점수를 얻을 수 있도록 포커 족보를 강화할 수 있다.

Elvar는 이번 게임에서 플라스마 덱이라는 특별한 덱을 사용하고 있다. 이 덱으로 플레이할 때는 칩과 배수를 곱하는 대신, 먼저 둘의 평균을 구한 다음 곱한다. 예를 들어 앞에서처럼 칩이 $50$개이고 배수가 $4$이면, 먼저 둘의 평균을 구한다. 그러면 칩은 $27$개이고 배수는 $27$이 되어, 점수는 $729$이 된다.

Elvar는 이번 Balatro 게임에서 상당히 운이 좋아 게임 초반에 친숙한 Perkeo을 손에 넣었다. 따라서 그는 Observatory을 찾기 위해 행성 카드 Neptune의 복사본을 모으기로 했다. Elvar는 항상 로열 플러시를 플레이할 수 있도록 덱을 구성했으며, 이 족보는 칩 $151$개와 $8$의 배수를 준다. 또한 Neptune 카드 하나를 사용하면 여기에 칩 $40$개와 $4$의 배수가 더해진다는 것을 알고 있다. 예를 들어 Neptune 카드 두 장을 사용하면 로열 플러시로 칩 $231$개와 $16$의 배수를 얻으며, 플라스마 덱을 적용하면 칩 $123.5$개와 $123.5$의 배수가 된다.

하지만 이제 Elvar는 조금 곤란한 상황에 놓였다. 마지막 블라인드가 끝난 뒤 Observatory를 찾을 것이라고 너무 확신한 나머지 자신의 조커를 모두 팔았다. 하지만 안타깝게도 Observatory는 어디에서도 찾을 수 없었다. 낙담한 그는 좋지 않은 상황에서도 최선을 다하려고 조커 Constellation을 구매했다. 이 조커가 좋은 이유는 각 핸드가 끝난 뒤 점수를 계산하기 전에 배수를 $1 + 0.1 \cdot$ number of planet cards used배로 만들기 때문이다. 따라서 Elvar가 Neptune 카드 $10$장을 사용하면 칩 $551$개와 $96$의 배수를 얻고, 플라스마 덱을 적용하면 칩 $323.5$개와 $323.5$의 배수가 되며, 이에 따라 $104,652.25$의 점수를 얻는다. Elvar는 Observatory를 찾지 못한 충격에서 아직 완전히 벗어나지 못했기 때문에 몇 장의 카드를 사용해야 하는지 모른다. 그가 블라인드에서 승리하기 위해 사용해야 하는 행성 카드의 최소 개수를 알아내도록 도와줄 수 있는가?

채점

그룹 | 점수 | 제한 조건

1 | 30 | $0 \leq x \leq 6320$

2 | 30 | $0 \leq x \leq 10^{24}$

3 | 40 | $0 \leq x \leq 10^{64}$

입력에는 Elvar가 블라인드에서 승리하기 위해 얻어야 하는 점수를 나타내는 하나의 양의 정수 $x$이 주어진다.

Elvar가 블라인드에서 승리하기 위해 사용해야 하는 행성 카드의 최소 개수를 출력한다.