레이팅 미적용베시는 휴대폰에 게임을 내려받아 즐기는 것을 좋아한다. 커다란 발굽으로 작은 터치 스크린을 조작하기가 꽤 번거롭기는 하지만 말이다.
베시는 지금 하고 있는 게임에 특히 푹 빠져 있다. 게임은 \(N\)개의 양의 정수(\(2 \leq N \leq 262,144\))로 이루어진 수열로 시작하며, 각 수는 \(1 \ldots 40\) 범위에 있다. 한 번의 이동에서 베시는 값이 같은 인접한 두 수를 골라, 그보다 1 큰 값의 수 하나로 바꿀 수 있다(예를 들어 인접한 7 두 개를 8 하나로 바꿀 수 있다). 게임의 목표는 게임이 끝났을 때 수열에 존재하는 가장 큰 수의 값을 최대화하는 것이다. 베시가 최대한 높은 점수를 얻을 수 있도록 도와주자!
문제 출제: 마크 첸(Mark Chen)
문제 출제: 마크 첸(Mark Chen)
입력의 첫째 줄에 \(N\)이 주어지고, 다음 \(N\)개의 줄에 게임 시작 시의 수열을 이루는 \(N\)개의 수가 주어진다.
베시가 만들 수 있는 가장 큰 정수를 출력한다.
262144.in · 출력을 쓸 파일 262144.out4
1
1
1
23In this example shown here, Bessie first merges the second and third 1s to
obtain the sequence 1 2 2, and then she merges the 2s into a 3. Note that it is
not optimal to join the first two 1s.
riseoj 작성
출처 올림피아드 > USACO > 2015-2016 > US Open > Platinum