NCPC2012F Optimal Transformation Cost＠Morris' Blog

2012-10-21 14:33:06| 人氣326| 回應0 | 上一篇 | 下一篇

NCPC2012F Optimal Transformation Cost

推薦 0 收藏 0 轉貼0 訂閱站台

Problem F

Optimal Transformation Cost

Input File: pf.in

Time Limit: 3 seconds

A mathematician, Professor Lee, is now studying a transformation scheme in Coding Theory. There are 2ⁿ n-bit binary strings S = {b_nb_n-1…b_i…b₂b₁|b_i∈ {0, 1} for 1 <= i <= n}. Two strings, can be transformed each other if and only if one is b_nb_n-1…b_k+10b_k-1b_k-2…b₁ and the other is b_nb_n-1…b_k+11b_k-1b_k-2…b₁, where i = 0, 1 and 1<= k <= n (i.e., their binary strings differ in a one-bit position only). We use x↔y to denote the transformation between two strings x and y, and use cost(x, y) to denote the cost of the transformation x↔y. To make the problem much easier, we assume the cost of each transformation is a constant c.

Professor Lee aims at finding a sequence of transformations T(S)=〈s₁↔s₂↔s₃↔…s_m-1↔s_m(=s₁)〉among S such that the following two conditions hold:

1. Every possible transformation is contained at least once by T(S).

2. The transformation cost T(S), defined by sigma(cost(s_i, s_i+1)), is as smallest as possible.

The minimum transformation cost of T(S) is called the optimal transformation cost, denoted by cost(T(S)). For example, consider S = {000, 001, 010, 011, 100, 101, 110, 111} and assume that c = 1. Then, T(S) =〈000↔001↔011↔010↔000↔100↔101↔001↔101↔111↔011↔111↔110↔010↔110↔100↔000〉and cost(T(S)) = 16. Note that T(S) may not be unique, but cost(T(S)) is unique.

Given a positive integer n and the cost of each transformation c, you task is to write a computer program to calculate the optimal cost cost(T(S))

Technical Specification

l 2 <= n <= 20

l 1 <= c <= 100

輸入說明：

The first line of the input file contains an integer, denoting the number of test cases to follow. For each test case, one line contains two integers n and c separated by a space.

輸出說明：

For each test case, output the optimal cost.

範例輸入：

23 12 1

範例輸出：

提示：

※ 測資錯誤請通知我

出處：

NCPC2012 (管理：morris1028)

這題其實就是要我們增邊尤拉環道, 求這圖的最少邊數, 我們先不理會邊的費用 c, 這個常數最後再乘就好了。

偶數的情況 : 對於每個點都有偶數條邊, 很明顯地本身就是尤拉環道, 邊的個數就是 2^n * n / 2
奇數的情況 :
我們可以從圖中畫出來, 那圖怎麼畫呢, 按照二進制裡面一個 1 數劃出, 最左邊集合是 000, 最右邊集合是111, 我們依序增加邊讓每個節點都是連接偶數條邊, 我們會發現左右會對稱, 也就是剛好是二項式的左右, 因此恰好有一半的點會增一條邊, 因此答案是 2^n * n / 2 + 2^(n-1) = 2^(n-1) * (n+1)。

#include <stdio.h>

int main() {
    int t, n, c;
    scanf("%d", &t);
    while(t--) {
        scanf("%d %d", &n, &c);
        int ans;
        if(n&1)
            ans = (1<<(n-1))*(n+1);
        else
            ans = (1<<n)*n/2;
        printf("%d\n", ans*c);
    }
    return 0;
}

我要檢舉

台長： Morris

您可能對以下文章有興趣

b113. 6. 線性系統求解

[ZJ][N*NlogN][BIT] a533. IOI2004 Day1.1.阿特米斯

[ZJ][模擬水] a349. 2. 指令解譯器

[ZJ][一年後修裝版][C++] b113. 6. 線性系統求解

人氣(326) | 回應(0)| 推薦 (0)| 收藏 (0)| 轉寄
全站分類: 不分類 | 個人分類: 資訊競賽 |
此分類下一篇:NCPC2012C Matrix
此分類上一篇:NCPC2012B Integer Partition

回應(0)