안녕하세요. Astein 입니다.
저보다 실력이 뛰어나신 분들이 많이 계시지만, 다들 바쁘신거 같아서 키보드를 두드리게 되었네요.
조금이나마 도움이 될 수 있으면 좋겠습니다. :)

A. Minimum Scalar Product

[spoiler="풀이 보러가기..."] [문제 풀이]
제일 단순한 방법에서부터 차례대로 접근해 봅시다. 아무 생각도 하지 않고 이 문제를 접근한다면, v1의 원소를 모든 경우에 대해 Permutation을 취하고, v2도 마찬가지로 Permutation을 구해서 각각을 1:1로 매칭하는 방법이 이 문제를 풀 수 있는 제일 단순한 해법입니다. 이 경우의 시간복잡도를 구하라면 테스트 케이스 하나에 n! * n! * n 이 되겠네요. 작은 데이터 케이스의 n이 8 이하지만, 이렇게 풀면 답이 나오지 않네요... T_T
이것보다 조금 더 나은 방법으로 나아가도록 하지요. 사실 위의 알고리즘에서 v1의 원소는 Permutation을 구할 필요가 없습니다. 어차피 v2의 가능한 모든 경우를 취하면 모든 경우가 구해지기 때문이지요. 예를 들어 (a, b, c) * (d, e, f)나 (a, c, b) * (d, f, e)의 값은 같으니까요. 이렇게 개선한 알고리즘은 각각의 테스트 케이스마다 n! * n 번의 연산이 필요하고, 이러한 방법으로도 작은 데이터 케이스의 경우는 답을 구할 수 있습니다.
바로 위에서 v1의 원소는 Permutation을 구할 필요가 없다고 했으므로, v1의 원소를 임의로 변경해도 v2의 모든 경우를 살펴본다면 원래의 문제와 답이 같다고 할 수 있습니다. 따라서 v1의 원소를 오름차순으로 정렬시켜버리도록 합시다. :) 어차피 답은 같으니까요.
이제 큰 데이터 케이스의 답을 구해야 합니다. 아무런 생각이 떠오르지 않으면 단순무식하게 접근해볼까요? v1의 원소가 정렬되어 있고, 현재 상태의 v2값에 대한 스칼라 곱이 M이라고 합시다. 이 때 임의의 v2원소 두 개를 서로 변경해서 나온 스칼라 곱이 N이고, N이 M보다 작다면, v2 원소 두개를 서로 변경하는게 답을 좀 더 좋게 만든다고 볼 수 있겠지요?
그러면 N < M인 경우를 찾아보도록 합시다. 우선 v1의 원소는 정렬되어 있다고 했으므로 x1 <= x2 <= ... <= xn 가 되지요. v2의 원소가 (y1, y2, .., yi, .., yj, ... yn) 이라고 할 때, yi와 yj를 서로 바꾼 경우의 스칼라곱을 N이라고 해 봅시다.
원래의 스칼라 곱 M = x1y1 + x2y2 + ... + xiyi + ... + xjyj + ... + xnyn
좀 더 나아진 스칼라 곱 N = x1y1 + x2y2 + ... + xiyj + ... + xjyi + ... + xnyn (yi와 yj의 위치가 바뀌었습니다)
N < M 이라고 했으니 정리하면 xiyj + xjyi < xiyi + xjyj가 되고, xj = xi + k (k >= 0) 라고 볼 수 있으므로 (* 우리는 정렬했거든요) 좀 더 풀어서 표현하면 k yi < k yj 가 되겠네요. 양변의 k를 나눠주면 yi < yj가 됩니다. (k = 0이면 어떻게 하느냐!고 하실 분들이 있을지도 모르겠지만, 그 경우엔 N < M을 만족하지 못합니다. 식을 자세히 봐 주세요 :). 즉 yi < yj인 모든 경우에 바꿔주는게 답을 좋게 만든다고 할 수 있습니다.
즉 우리의 최종 목표인 v2의 배치상태는 i < j인 모든 경우에 대하여 yi < yj가 하나도 발생하지 않아야 합니다. 즉 모든 i < j에 대해 yi >= yj를 만족해야 하지요. 이 경우는 내림차순으로 정렬한 것과 같은 결과를 얻을 수 있게 됩니다. 정렬 알고리즘의 시간 복잡도는 O(N lg N)이므로 ( 비효율적으로 작성한다고 해도 O(N²⁾ ) 시간내에 충분히 Large Dataset도 솔루션을 제출할 수 있게 됩니다.
사실 이러한 문제를 많이 풀어보신 분들이라면, v1은 오름차순으로, v2는 내림차순으로 정렬해버리고 차례대로 곱해버리자!고 생각하실 수 있습니다. (그리고 이게 정답이라는건 위에서부터 증명했지요.) 하지만 한번쯤은 증명하고 넘어가는 것도 나쁘지 않겠지요 :) [/spoiler]
[spoiler="소스코드 보러가기..."]~~~ cpp

#include
#include
#include
#include
using namespace std;
int main() {
int T;
cin >> T;
int n;
for (int cn = 1; cn <= T; ++cn) {
printf("Case #%d: ", cn);
cin >> n;
vector a(n), b(n);
for (int i = 0; i < n; ++i)
cin >> a[i];
for (int i = 0; i < n; ++i)
cin >> b[i];
sort(a.begin(), a.end());
sort(b.begin(), b.end());
long long ret = 0;
for (int i = 0; i < n; ++i) {
ret += a[i] * b[n - 1 - i];
}
cout << ret << endl;
}
}

 B. Milkshakes 
    [문제 설명]
  당신은 밀크쉐이크 가게의 주인입니다. N가지의 서로 다른 맛의 밀크쉐이크를 준비할 수 있는데, 각각 '발효시킨' 경우와 '발효시키지 않은 경우'로 나눌 수 있습니다. 따라서 전체 2N 가지 종류의 밀크쉐이크가 있는 셈이지요.
  당신의 고객들은 각기 다른 취향의 소유자입니다. (물론 그중에 몇명이 같을 수도 있겠지만요.) 당신의 고객은 적어도 한 가지 이상의 당신 가게의 메뉴를 선호합니다. 하지만 '발효시킨' 밀크쉐이크의 경우는 최대 한 가지만 좋아한다고 합니다. 발효시키면 밀크쉐이크 본래의 맛을 잃어버리기 때문에 어느 누구도 두 가지 이상의 발효 밀크쉐이크를 좋아하지는 않는 것 같습니다.
  이제 당신은 밀크쉐이크 N개를 판매하고자 합니다. 따라서 아래의 세 가지 조건을 만족시키고 싶어합니다.
 - 각각의 밀크쉐이크는 전체를 발효시키거나 발효시키지 않아야 합니다. 즉 한 종류의 밀크쉐이크에 대하여 일부만 발효시켜서 팔 수는 없다는 말이지요. 
 - 당신의 고객은 적어도 한가지 이상의 밀크쉐이크를 좋아합니다.
 - 발효시키는데는 돈이 많이 들기 때문에, 당신은 가능하면 발효시키지 않고 팔고 싶습니다. (즉, 발효과정을 최소로 하고 싶습니다.)
 당신은 찾아온 고객을 단 한명도 외면할 수 없었습니다. 모든 고객을 만족시키면서 위의 세 가지 조건을 만족하는 경우를 구하는 것이 문제입니다. 만약 어떻게 하더라도 원하는 밀크쉐이크를 얻을 수 없는 고객이 있다면 "IMPOSSIBLE"을 출력하시오. 
[spoiler="풀이 보러가기..."]   [문제 풀이]
  이 문제도 하나씩 접근해 보도록 하지요. N가지의 밀크쉐이크가 있고, 각각의 밀크쉐이크는 "발효"와 "발효되지 않은"의 두 가지 상태가 존재하므로, 모든 경우를 구한다고 보면 2^N 가지의 경우가 나옵니다. 모든 경우를 가정하면서, M명의 고객들을 모두 만족할 수 있는 경우를 찾고, 그 때 발효과정을 최소로 하는 경우를 구하면 우리가 원하는 답이 되는 것이지요. 이러한 방법의 시간복잡도는 각 테스트 케이스에 대해  O(2^N * T)가 될 것입니다. [T: 고객이 선호하는 밀크쉐이크의 종류의 합을 나타냅니다. 원래 문제를 참조하세용]
  하지만 위의 알고리즘으로 Large Dataset을 구할 수는 없겠지요. 이 문제의 힌트는 "각각의 고객은 최대 한 종류의 발효된 밀크쉐이크를 좋아한다" 입니다. 이 힌트를 이용하여 문제를 풀어봅시다.
  당신에게 있어서 제일 좋은 경우는 모든 밀크쉐이크를 발효시키지 않고 소비자에게 제공하는 것입니다. 하지만 이러한 경우를 나오지 않게 하는 것은 "발효된 밀크쉐이크만 좋아하는 고객" 이 되겠지요. 우리는 이러한 소수고객들을 위해 "반드시 발효시켜야 할 밀크쉐이크의 리스트"를 구할 수 있습니다.
  이렇게 발효된 밀크쉐이크가 정해지면, 또 다른 문제점이 발생하게 되지요. 처음 상태에서는 발효되지 않은 밀크쉐이크였기 때문에 만족했던 고객들이 위의 과정에서 몇 개의 밀크쉐이크를 발효시킴으로서 "불만족"상태에 빠지게 됩니다. 만약 어떤 고객이 발효되지 않은 A 밀크쉐이크를 좋아했는데 당신이 다른 고객을 위해 A를 발효시켰다면 이 고객은 A 밀크쉐이크로는 만족할 수 없는 상태가 되는 것이지요.
  위의 과정을 반복하면서 모든 고객이 만족할 수 있는 상태를 조율해 나가는 것이 포인트입니다. 사실 말이 길었지만 간단히 알고리즘을 정리하면 세 단계로 나눌 수 있지요.
 1. 발효된 밀크쉐이크만 좋아하는 고객을 찾는다. 
 2. (1) 과정에서 K라는 밀크쉐이크를 발효했다면, 발효되지 않은 K 밀크쉐이크를 좋아하는 사람들의 "좋아하는 목록" 리스트에서, K와 관련된 정보를 삭제한다. 예를 들어, 발효되지 않은 K 밀크쉐이크와 발효된 L 밀크쉐이크를 좋아하던 사람이 있었다면, 이 사람은 다음 단계에서 발효된 밀크쉐이크만 좋아하는 고객이 되는 것이다.
 3. (1)의 과정을 반복한다. 
  음... 이렇게 풀면 시간복잡도는 아마도 하나의 테스트케이스에 대하여  O(NMT)정도가 될 것 같습니다. 저는 이러한 방법으로 Large Dataset을 구했는데, 다른 알고리즘도 많이 있을지도요 :)[/spoiler]
[spoiler="소스코드 보러가기..."]~~~ cpp

#include <iostream>
#include <cstdio>
#include <vector>
using namespace std;
vector <int> ret;
vector <int> table;
int n, m;
vector <vector <pair<int, int> > > a;
int main() {
    int T;
    cin >> T;
    for (int cn = 1; cn <= T; ++cn) {
        printf("Case #%d: ", cn);
        cin >> n;
        cin >> m;
        a.resize(m);
        for (int i = 0; i < m; ++i) {
            a[i].clear();
            int t;
            cin >> t;
            for (int j = 0; j < t; ++j) {
                int pos, st;
                cin >> pos >> st;
                a[i].push_back(make_pair(st, pos - 1));
            }
            sort(a[i].begin(), a[i].end());
        }
        ret.assign(n, 0);
        bool changed = true;
        while (changed) {
            changed = false;
            for (int i = 0; i < m; ++i) {
                if (a[i].size() == 1 && a[i][0].first == 1 && ret[a[i][0].second] == 0) {
                    ret[a[i][0].second] = 1;
                    changed = true;
                    for (int j = 0; j < m; ++j) {
                        for (int k = 0; k < a[j].size(); ++k) {
                            if (a[i][0].second == a[j][k].second && a[j][k].first == 0) {
                                swap(a[j][k], a[j][a[j].size() - 1]);
                                a[j].pop_back();
                            }
                        }
                    }
                }
            }
        }
        bool found = true;
        for (int i = 0; i < m; ++i)
            if (a[i].size() == 0) found = false;
        if (found) {
            for (int i = 0; i < n; ++i)
                printf("%d ", (ret[i] > 0));
            printf("\n");
        } else {
            printf("IMPOSSIBLE\n");
        }
    }
}

~~~[/spoiler]




 C. Numbers 
    [문제 설명]
  (3 + √5)ⁿ 의 정수부분에서 끝 세자리를 구하는 프로그램을 작성하시오. 
  예를 들어 n = 5일 경우 (3 + √5)^5 = 3935.73982...이므로 935를 출력하세요. 만약 n = 2인 경우라면 (3 + √5)^2 = 27.4164079...이므로 027을 출력하세요. (항상 3자리를 출력)
[spoiler="풀이 보러가기..."]    [문제 풀이]
  문제는 짧은데 쉽진 않네요 T_T
  단순하게 C++로 풀어서 small dataset을 제출한다면 여지없이 Incorrect를 받을 수 있는 문제였다고 들었습니다. 그 이유는 C++에서 double type이라고 해봐야 유효자리의 한계때문에 오차가 생길수 밖에 없거든요. ( Windows 계산기를 사용해서 하나씩 계산해서 테이블을 만든 다음, 제출해서 맞은 사람이 있다는 이야기는 들었습니다.)  뭐 윈도우즈 계산기를 사용하던 Mathematica나 Maple을 사용하던 답만 구하면 되는거 아니겠습니까... 라지만 Large Dataset은 이러한 것들로 구하지 좀 어렵지요 [...]
  이 문제를 풀기 위해서는 어느정도의 수학적 센스[?]가 필요한 것 같습니다. 0 < 3 - √5 < 1 라는 것을 이용해야 하거든요.
  우리가 구하는 (3 + √5)^n = A + B√5 꼴로 항상 표현이 가능합니다. 또한 (3 - √5)^n = A - B√5 로 나타낼 수 있다는 말이지요. 그리고 여기에서 두 식의 √5의 계수부인 B는 같은 값이므로, (3 + √5)^n  + (3 - √5)^n  = 2A 임을 알 수 있습니다.
  또한 저기 위에 있는 0 < 3 - √5 < 1 을 조금 더 변형시키면  0 < (3 - √5)^n < 1 이 되지요. 즉 우리가 구할 (3 + √5)^n = 2A - 0.xxx 라는 것을 알 수 있습니다. 그럼 이제 남은것은 A를 구하는 것이겠군요 [!]
  너무 자세하게 설명하면 여기에 쓸 내용이 너무 많아지므로 간단하게 결론만 쓰겠습니다. (3 + √5)^n  를 구하는 문제에서 (3 + √5)^n  = A + B√5 꼴로 표현했을때의 A를 구하면 되는 문제로 바뀌었으니까요, 여기에서 A를 구하는 것은 행렬곱셈을 사용하여 풀 수 있습니다.
                   n
R =  [ 3  5 ]   [ 1 ]   =  [A]
        [ 1  3 ]   [ 0 ]       [B]
  위의 식에서 R을 구하면 A, B를 구할수가 있게 됩니다. 왜 저렇게 되는지는 천천히 생각해 보시길 바랍니다. 이제 이렇게 행렬곱셈으로 구한다는 것을 이해하신 분들은 행렬의 n제곱을 구해야 한다는 문제에 빠지게 되는데요. 이것도 인터넷에 자료가 많이 있으니 검색의 힘을 이용해 주세요 :) 결론만 살짝 말씀드리자면 행렬의 n제곱은 O(lg n)번의 연산으로 구할 수 있게 됩니다. 또한 우리가 구하는 것은 "뒤의 세 자리" 이므로 모든 수를 가지고 있을 필요도 없구요. 
  C번 문제의 경우는 수학이 상당히 많이 필요해서 자세히 설명해드리지 못한 점 죄송하게 생각합니다. 궁금하신 사항이 있으시다면 Hanirc #icpc 채널로 오셔서 astein을 찾아주세요 [...] 일단 소스코드를 첨부합니다만 이해하기 쉬울지는 잘 모르겠네요 ㅠ_ㅠ
[/spoiler]
[spoiler="소스코드 보러가기..."]~~~ cpp

#include <cstdio>
#include <iostream>
using namespace std;
const int MOD = 1000;
struct matrix {
/*  this is 2x2 matrix 
    [ a , b ]
    [ c , d ]  */
    int a, b, c, d;
    matrix() : a(0), b(0), c(0), d(0) {}
    matrix(int _a, int _b, int _c, int _d) : a(_a), b(_b), c(_c), d(_d) {}
    matrix operator * (const matrix &T) {
        matrix ret;
        /*  [a b][T.a T.b] => [a*T.a+b*T.c a*T.b+b*T.d] *
         *  [c d][T.c T.d]    [c*T.a+d*T.d c*T.b+d*T.d] */
        ret.a = (a * T.a + b * T.c) % MOD;
        ret.b = (a * T.b + b * T.d) % MOD;
        ret.c = (c * T.a + d * T.c) % MOD;
        ret.d = (c * T.b + d * T.d) % MOD;
        return ret;
    }
    matrix pow(int n) {
        if (n == 1) return (*this);
        matrix ret(1, 0, 0, 1);
        for (int i = 30; i >= 0; --i) {
            ret = ret * ret;
            if (n & (1 << i))
                ret = ret * (*this);
        }
        return ret;
    }
};
int main() {
    int T;
    cin >> T;
    for (int cn = 1; cn <= T; ++cn) {
        int n;
        cin >> n;
        matrix ret(3, 5, 1, 3);
        ret = ret.pow(n);
        printf("Case #%d: %03d\n", cn, (2 * ret.a + 999) % MOD);
    }
}

[/spoiler]