cinador   3년 전

문제

당신은 카드 N장과 양의 정수 K를 가지고 있고, N은 K의 배수이다. 이들을 이용해 다음과 같이 게임을 하려고 한다.

  1. 카드 N장을 일렬로 나열한다. 각각의 카드에는 1부터 9까지의 숫자 중 하나가 적혀있다.
  2. 당신은 이 N장의 카드 중 몇 장의 카드를 골라서 버릴 수 있다. 이 때, 버리는 카드의 개수는 K의 배수여야 하며, 1장도 버리지 않을 수도 있고, N장 전부 버릴 수도 있다.
  3. 위 과정을 거치면 남아있는 카드의 개수는 K의 배수이다. 이 카드들을 왼쪽에서부터 순서를 바꾸지 않고 K개씩 한 묶음으로 묶는다.
  4. 한 묶음에 포함된 K개의 숫자들을 K자리의 십진수로 보고, 이 K자리 수들의 합이 이 게임에서 얻을 수 있는 점수가 된다.

예를 들어, N = 9, K = 3이고, 카드에 쓰여져 있는 숫자들이 왼쪽에서부터 2, 9, 9, 7, 9, 2, 4, 5, 8 이라고 하자. 만약 카드를 하나도 버리지 않는다면 점수는 299 + 792 + 458 = 1549 이다. 반면에, 1번째, 6번째, 7번째 카드를 버린다면 남은 6장의 카드가 9, 9, 7, 9, 5, 8 이 되므로, 점수는 997 + 958 = 1955 가 된다. 단, 모든 카드를 버린다면 점수는 0이다.

양의 정수 K와 일렬로 나열된 카드 N장에 쓰여진 숫자들이 주어질 때, 적절하게 카드를 버려서 얻을 수 있는 점수의 최댓값을 구하여라.

ㅤ

입력

입력은 최대 50개의 테스트 케이스로 이루어져 있으며, 각 테스트 케이스는 다음과 같은 형식을 갖는다.

K

s1s2...sN

첫번째 줄에는 양의 정수 K가 주어진다. K는 2이상 14이하이다.

두번째 줄에는 문자열이 하나 주어진다. 문자열의 길이는 N이고, N은 K이상 200,000이하인 양의 정수이며, K의 배수이다. 또한, 이 문자열의 i번째 문자 si 는 왼쪽에서 i번째 카드에 쓰여진 숫자이고, 1부터 9까지의 숫자 중 하나이다.

입력의 마지막에는 0 하나가 주어진다. 

ㅤ

출력

각 테스트 케이스에 대해, 얻을 수 있는 점수의 최댓값을 한 줄에 하나씩 출력한다.

이 문제의 제한을 만족하는 모든 경우에서 정답이 263 미만임을 증명할 수 있다. 단, 32bit 정수형으로는 표현할 수 없는 경우가 있음에 주의한다.

iansong   3년 전

"모든 경우에서 정답이 263 미만임이 보장된다"가 더 자연스러울 것 같습니다

댓글을 작성하려면 로그인해야 합니다.