Code in C Language for SOJ 1001. Alphacode

16312 ワード

Code in C Language for SOJ 1001. Alphacode
Ver 0.1(TL)
再帰的な遍歴アルゴリズムを利用する欠点は明らかである:大きな演算量(減らすことができない)、それによる超長演算時間.利点:冬は走って暖かい手の宝になることができる.

//
// main.cpp                                           
//                                                  
// Common Test Emilia                                
//                                                   
// Created by Emilia on 2016/11/8                    
// Copyright © 2016  Emilia. All rights reserved.   
//

#include
#include

int process(int len, char *in);
int cyc(int sta, int *cord, int mid);

int main(void)
{
    char input[50] = { 0 };
    int i = 0, length;
    int output;
    while (input[i] = getchar())
    {
        if (input[0] == '0')
            return 0;
        if (input[i] == '
')
        {
            length = i;
            output = process(length, input);
            printf("%d
", output);
            for (i = 0; length > 0; input[--length] = 0);
        }
        else
            i++;
    }
    return 0;
}

int process(int len, char *in)
{
    int rec[50] = { 0 };
    int re = 1, num = 0;
    for (int i = 0; i < len - 1; i++)
    {
        if (in[i] == '1' && in[i + 1] != '0')
            rec[i] = 1;
        else if (in[i] == '0')
            for (int t = i - 1;t < len - 1; t++)
                in[t] = in[t + 2];
        else if (in[i] == '2')
                if (in[i + 1] <= '6' && in[i + 1] != '0')
                    rec[i] = 1;
    }
    len = strlen(in);
    for (int t = 0; t < 50; t++)
        num += rec[t];
    for (int t = 1;t <= num;t++)
    {
        re += cyc(0, rec, t);
    }
    return re;
}

int cyc(int sta, int *cord, int mid)
{
    int num = 0;
    if (mid > 1)
    {
        mid--;
        for (int t = sta;t < 50;t++)
        {
            if (cord[t] == 1)
            {
                sta = t + 2;
                num += cyc(sta, cord, mid);
            }
        }
        return num;
    }
    else
    {
        for (int t = sta; t < 50; t++)
            num += cord[t];
        return num;
    }
}

Ver 0.2(TL)
フィボチェナ思想の後から前への再帰アルゴリズムの欠点を結びつけた:大きな繰返し演算量(減らすことができる)、それによる超長演算時間.利点:冬は走って手を温めることができるが、Ver 0.1の効果はない.

//
// main.cpp                                           
//                                                  
// Common Test Emilia                                
//                                                   
// Created by Emilia on 2016/11/8                    
// Copyright © 2016  Emilia. All rights reserved.   
//

#include
#include

int process(int len, char* in);

int main(void)
{
    char input[50] = { 0 };
    int i = 0, length;
    int output;
    while (input[i] = getchar())
    {
        if (input[0] == '0')
            return 0;
        if (input[i] == '
')
        {
            length = i;
            output = process(length, input);
            printf("%d
", output);
            for (i = 0; length > 0; input[--length] = 0);
        }
        else
            i++;
    }
    return 0;
}

int process(int len, char* in)
{
    int num = 0, lim;
    lim = (in[len - 2] - '0') * 10 + in[len - 1] - '0';
    if (len >= 2 && lim < 27)
    {
        num += process(len - 2, in);
    }
    else
        num += 0;
    if (len > 1 && in[len - 1] != '0')
    {
        num += process(len - 1, in);
    }
    else
        num += 0;
    if (len <= 1)
        num += 1;
    return num;

}

Ver 1.0(AC)
フィボチェナ思想の前から後への再帰アルゴリズムの利点を組み合わせた:Ver 0.2の繰返し演算問題(すべての演算結果を配列で格納した)を解決し、それによる高速演算.欠点:手を温める宝にはなれない.

//
// main.cpp                                           
//                                                  
// Common Test Emilia                                
//                                                   
// Created by Emilia on 2016/11/8                    
// Copyright © 2016  Emilia. All rights reserved.   
//

#include
#include

int main(void)
{
    char input[6000] = { 0 };
    int i = 0, length;
    long long result[6001] = { 1, 1 };
    while (input[i] = getchar())
    {
        if (input[0] == '0')
            return 0;
        if (input[i] == '
')
        {
            length = i;
            for (int t = 1; t < length; t++)
            {
                if (input[t - 1] == '1' || input[t - 1] == '2' && input[t] <= '6')
                {
                    result[t + 1] += result[t - 1];
                }
                if (input[t] != '0')
                {
                    result[t + 1] += result[t];
                }
            }
            printf("%lld
", result[length]);
            for (i = 1; i < 5001; i++, result[i] = 0);
            for (i = 0; length > 0; input[--length] = 0);
        }
        else
            i++;
    }
    return 0;
}

良いアルゴリズムがどれほど重要かを示します.p
SAMPLE INPUT

11111111111
1111111111111111111111
111111111111111111111111111111111
11111111111111111111111111111111111111111111
0

SAMPLE OUTPUT

Time Cost

Line 1
Ver 0.1: <1ms
Ver 0.2: <1ms
Ver 1.0: <1ms

Line 2
Ver 0.1: 21ms
Ver 0.2: 1ms
Ver 1.0: <1ms

Line 3
Ver 0.1: 2153ms
Ver 0.2: 78ms
Ver 1.0: <1ms

Line 4
Ver 0.1: 233207ms
Ver 0.2: 9042ms
Ver 1.0: <1ms

Line 5 (input: 1x50)
Ver 1.0: <1ms

Line 6 (input: 1x60)
Ver 1.0: <1ms

Line 7 (input: 1x70)
Ver 1.0: <1ms

Line 8 (input: 1x80)
Ver 1.0: <1ms

Line 9 (input: 1x90)
Ver 1.0: <1ms

Platform:
CPU: Intel(R)Core(TM)i7-4710HQ @ 2.50GHz(Turbo on)
Memory: 16G

GET送信とreturnの特性 Progate:PHP講座4を終えて