오늘은 뭔가 문제들이 짧아서 읽기 좋았네요 :) 특히나 LuckyNumber...

Rizvanov_de_xXx 라는 분이 챌린지에 힘입어 1등을 차지했고 페본좌님은 2위...(근데 레이팅 -10)

Easy (250 pts.)

• 문제 설명
  John은 4와 7이란 숫자를 좋아한다. 그래서 4와 7로만 이루어진 수를 Lucky Number라고 부른다.
  a이상 b이하의 수 중 Lucky Number의 갯수를 구하시오. (a, b는 1이상 10억 이하)
  [spoiler="더 보기..."] * 문제 풀이
  길이가 k인 Lucky Number는 2^k 개밖에 없습니다. 그런데 문제에서 a와 b가 10억 이하이므로 2^1 + 2^2 + ... + 2^9 개의 Lucky Number밖에 없는 셈이지요. 그래서 모든 Lucky Number를 생성한 다음에 [a, b] 범위에 포함되는지만 비교해주면 간단하게 풀 수 있습니다.
  Lucky Number를 생성하는 방법은 {4. 7}을 기본 Lucky Number라 두고, 임의의 Lucky Number를 뽑아서 * 10 + 4, * 10 + 7 연산을 하면서 생성할 수 있습니다. 그래서 b이하의 모든 Lucky number를 생성한 다음 a보다 큰 Lucky Number의 수를 세면 되는 것이지요.
  [/spoiler]

  Medium (500 pts.)

• 문제 설명
  John은 4와 7이란 숫자를 좋아한다. 그래서 4와 7로만 이루어진 수를 Lucky Number라고 부른다.
  길이가 length인 Lucky Sequence : A[0], A[1], ..., A[length - 1]은 아래와 같은 조건을 만족한다.
  조건 1) 0 <= i < length를 만족하는 모든 i에 대해서 A[i]가 numbers[j]와 같은 j가 하나 이상 존재한다.
  조건 2) 0 <= i < length - 1를 만족하는 모든 i에 대해서 A[i]의 끝자리는 A[i + 1]의 첫자리와 같다. (끝말잇기)
  vector numbers와 length가 주어졌을 때 distinct한 Lucky Sequence의 경우의 수를 1234567891로 나눈 나머지를 구하시오.
  (length는 1이상 10억 이하)
  [spoiler="더 보기..."] * 문제 풀이
  length가 매우 크기(10억) 때문에 아쉽게도 iteration으로는 해결할 수가 없습니다. 하지만 Matrix Multiplication(행렬 곱셈)을 사용하면 보다 쉽게 접근할 수가 있지요.
  우선 입력으로 받은 numbers에서 Lucky Number들을 골라냅니다. 그리고 중복되는 Lucky Number들을 지워줍니다.
  위와 같이 처리를 했다면, 어떤 Lucky Number가 있더라도 앞자리와 끝자리만 고려해도 됩니다. 474나 4774나 4474 모두 4로 시작해서 4로 끝나는 수의 의미만 가질 뿐이고, 다른 의미는 없거든요. 그러면 아래와 같은 2 by 2 Matrix를 생성합니다.
  [ 4로 시작해서 4로 끝나는 수, 4로 시작해서 7로 끝나는 수]
  A = [ 7로 시작해서 4로 끝나는 수, 7로 시작해서 7로 끝나는 수]
  우리가 구하려는 답은 A ^ (length) 를 구하여 2 by 2 matrix를 이루고 있는 각 수의 합이 됩니다. (뒤에 간단한 증명을 적어두겠습니다.) 그러면 행렬의 length 제곱을 해야 하는데 이 부분은 log(length)번으로 해결할 수 있지요. length가 짝수라면 (length / 2)의 제곱을, 홀수라면 (length / 2) ^2 * (this)를 해주면 되기 때문입니다. 큰 수의 나머지와 관련된 문제는 (B + C) % p = ((B % p) + (C % p)) % p 를 알고 있다면 쉽게 풀 수 있습니다.
  Proof:
  T[i][j][k]를 (전체 i개의 Lucky Number를 사용해서, A[0]의 첫 자리가 j이고 A[i - 1]의 마지막 자리가 k인 Sequence의 수) 라고 정의합시다.
  위에서의 행렬은 T[1][4][4]. T[1][4][7]. T[1][7][4]. T[1][7][7]을 의미한다고 보면 되지요.
  여기서 T[k][4][4]를 구한다고 가정하면, T[k][4][4] = T[k - 1][4][7] * T[1][7][4] + T[k - 1][4][4] * T[1][4][4] 라고 볼 수 있습니다. (정의를 천천히 되새겨 봅시다.)
  위와 같은 방식으로 모든 table을 채울 수가 있지요. :)
  [/spoiler]

  Hard (1000 pts.)

• 문제 설명
  John은 4와 7이란 숫자를 좋아한다. 그래서 4와 7로만 이루어진 수를 Lucky Number라고 부른다.
  어떤 수들은 Lucky Number의 합으로 나타낼 수 있다. integer N이 주어졌을 때, Lucky Number로 이루어져 있으며 합이 정확히 N인 vector 를 리턴하는 프로그램을 작성하시오. 만족하는 경우가 여러 가지 있을 경우, Lucky Number를 적게 쓰는 경우를 답으로 인정한다. 또한 사용한 Lucky Number의 수가 같을 경우에는 earliest lexicographically 한 답을 return 하시오.
  [spoiler="더 보기..."]

• 문제 풀이
  처음엔 단순 Back-Tracking으로 접근했다가 TLE를 해결할 수 없어서 다른 방법으로 풀었더랬죠.. (5분이 모자라서 submit을 못했지만 -.-)
  N = 999999라면 아래와 같이 만들어 질 수 있지요.
  000004
  044444
  477774

  + 477777

  999999
  제일 앞에 0이 들어갔다고 해도, 실제로는 0을 쓰지 않으니 Lucky Number라고 볼 수 있습니다. 문제를 푸는 핵심 아이디어는 m개의 수를 가지고 N을 만든다고 하면 각 자리에 i개의 0, j개의 4, k개의 7이 사용되며 i + j + k = m 을 만족한다는 것이지요. (좀 더 정확하게 말하자면 0은 1의 자리에는 하나도 사용되지 않을 것이고 자릿수가 높아질수록 점점 많이 사용될 것입니다.)
  소스코드가 길지 않으니 그냥 붙여넣도록 하겠습니다 ㅠ_ㅠ 혹시 궁금하신 부분이 있다면 댓글로 남겨주세요.

#include
#include
#include
#include
using namespace std;
vector rv, r1, r2;
struct TheLuckySum {
bool backtr(int n, int remain) {
if (n == 0) return true;
if (n < 0) return false;
for (int sum = 0; sum <= remain; ++sum) {
// non zero -> sum;

for (int i = sum; i >= 0; --i) {
int ldigit = 4 * i + 7 * (sum - i);
if (n >= ldigit && (n - ldigit) % 10 == 0) {
if (backtr((n - ldigit) / 10, sum)) {
r1.push_back(i);
r2.push_back(sum);
return true;
}
}
}
}
return false;
}
vector sum(int n) {
for (int i = 1; ; ++i) {
if (backtr(n, i)) {
rv.resize(i);
for (int j = 0; j < r1.size(); ++j) {
for (int k = 0; k < r2[j]; ++k) {
if (k < r2[j] - r1[j]) rv[k] = rv[k] * 10 + 7; else rv[k] = rv[k] * 10 + 4;
}
}
break;
}
if (n < 50 && i == 15) return rv;
}
reverse(rv.begin(), rv.end());
return rv;
}
};

[/spoiler]
<div>[이 글은 과거 홈페이지에서 이전된 글입니다. <a href="http://algospot.andromeda-express.com/zbxe/editorial/47398">원문보기</a>]</div>