당신은 카드 N장과 양의 정수 K를 가지고 있고, N은 K의 배수이다. 이들을 이용해 다음과 같이 게임을 하려고 한다.
카드 N장을 일렬로 나열한다. 각각의 카드에는 1부터 9까지의 숫자 중 하나가 적혀있다.
당신은 이 N장의 카드 중 몇 장의 카드를 골라서 버릴 수 있다. 이 때, 버리는 카드의 개수는 K의 배수여야 하며, 1장도 버리지 않을 수도 있고, N장 전부 버릴 수도 있다.
위 과정을 거치면 남아있는 카드의 개수는 K의 배수이다. 이 카드들을 왼쪽에서부터 순서를 바꾸지 않고 K개씩 한 묶음으로 묶는다.
한 묶음에 포함된 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 정수형으로는 표현할 수 없는 경우가 있음에 주의한다.
cinador 3년 전 3
문제
당신은 카드 N장과 양의 정수 K를 가지고 있고, N은 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 정수형으로는 표현할 수 없는 경우가 있음에 주의한다.