Morris' Blog 我在摸索我存在的意義、生命的意義、內涵及價值。 沒有真正神手般的厲害，套用模式是大部分的情況。 沒那麼厲害的我存在的意義為何，襯托出神的存在？ 有時候不能怪別人不給我機會，我已經開始省思， 為什麼我沒有給別人機會的原因，而是全要靠別人。 有時候我認為我與眾不同，那是因為我做不到很多人能辦到的事情。 我聽不到、玩不起來、說得不夠明瞭、理解得不夠多， 我缺少的語文能力，就是一切一切無能的判定。 為此，我不曉得能做些對別人有幫助的事情。 我知道我自己是個不服輸的性格，但現在我不得不認輸。 我沒有能力，因此我必須認輸。 我到底來這世界作什麼？處處充滿不確定性， 而我總是無法出類拔萃，想當個一般人似乎也回不了頭了。 越強大的挑戰需要越強力的支持，而我的支持是什麼？ 最近嘗試與人談話，但都是失敗的結局，沒人能接受， 不需要言語，不需要溝通，一切所想都表達不出來。

49愛的鼓勵 6訂閱站台

You are all excellent programmers and should be good at tracing program running behaviors for debugging purposes. The following problem is to request you to verify if the program runs in the feasible ways.

A program execution with function invocation can be modeled as a control flow graph. The control flow can be identified as an intra-function flow or inter-function flow. The inter-function flows will occur at function invocation and function return. For example, if we trace the following function simpleRecFunc(x,y,z) written in the syntax of the C programming language:

1: void simpleRecFunc(int a,int b, int *v) {
2:    if (a <=2) {
3:          *v = b + 1;
4:    } else {
5:        if (a>b) 
6:          *v = *v+1 ;
7:        else 
8:          *v = *v -1 ;
9:        if (a < b + 1) { 
10:               simpleRecFunc(a-1, b, v);
11:               simpleRecFunc(a-2,*v,v);
12:       } else 
13:               simpleRecFunc(a-3,*v,v);
14:    }
15: }  
16: void main() { srandom(getpid());//set a random seed
17:   int x =random()%21;//obtain the x value between 0 and 20
18:   int y =random()%101;//obtain the y value between 0 and 100
19:   int z;
20:   simpleRecFunc(x,y,&z);
21: }

Each statement is annotated with a line number n, where n is a positive integer. After a function invocation, the return line number is n + 1. An exception is that after a function invocation at line 11, the return line number is 14. The formal parameter v in the simpleRecFunc() function is always passed in a valid integer reference, containing an integer value.

For example, if at line 2, the condition (a2) is true, the run-time flow path is 2 3 15; if the above condition is false, and at line 5, the condition (a > b) is true, the run-time path is 2 4 5 6 9 12 13. We won't trace the control flow and step into the standard library function of srandom(), getpid(), and random(), but only trace the flow into the function of simpleRecFunc(). According to the above program, we can depict a corresponding flow graph as follows:

Each node in the flow graph is labeled with the corresponding statement line number. The run-time path will be varied, due to different parameters of a, b, and v.

Given a path from node 16 to node 21, you are to determine if the path is feasible. For example, the path 16 17 18 19 20 1 2 3 15 21 is feasible. The path 16 17 18 19 20 1 2 4 5 7 8 9 12 13 1 2 3 15 21 is infeasible for we cannot find any possible integers or zero for a, b and *v to execute the above path. The path 16 17 18 19 20 1 2 4 5 7 8 9 10 1 2 3 15 21 is also infeasible because after the function invocation, the control must return to the next statement of the caller. The caller here being at line 10, the next statement line number is 11. Please note that there is no direct edge between 10 and 11 due to that we step into the function of simpleRecFunc() and the next node of 10 is 1 instead of 11. Assume the program is given enough memory to execute.

Technical Specification

1. The number of path data is N , where 0 < N1024.
2. The number of statement line numbers in an path is M, where 0 < M2¹⁶.
3. In the invocation of simpleRecFunc(x,y,z), 0x20 and 0y100

Input 

The test data begins with a positive integer N, where N is the number of path data. The subsequence N lines are the input paths, specified by a sequence of statement line numbers, each separated with one or more spaces, from the starting statement line 16 to the end statement line 21. Each input path is read up to the end of the line, for example:

16 17 18 19 20 1 2 3 15 21

Output 

If the given path is feasible according to the above control flow graph, output feasible, otherwise output infeasible.

Sample Input 

2
16 17 18 19 20 1 2 3 15 21
16 17 18 19 20 1 2 4 5 7 8 9 12 13 1 2 3 15 21

Sample Output for the Sample Input 1 

feasible 
infeasible

Sample Input 

4
16 17 18 19 20 1 2 3 15 21
16 17 18 19 20 1 2 4 5 7 8 9 12 13 1 2 3 15 21
16 17 18 19 20 1 2 4 5 7 8 9 10 1 2 3 15 21
16 17 18 19 20 1 2 4 5 6 9 12 13 1 2 3 15 14 15 21

Sample Output 

feasible 
infeasible
infeasible
feasible

---

把所有可能建造出來, 要記得 x, y, z 是有範圍的

#include <iostream>
#include <cstdio>
#include <cstdlib>
using namespace std;
char s[2122][2000];
int k = 0, st;
void simpleRecFunc(int a, int b, int *v) {
    s[k][st++] = 1, s[k][st++] = 2;
    //printf("1 2 ");
    if(a <= 2) {
        //printf("3 ");
        s[k][st++] = 3;
        *v = b+1;
    } else {
        //printf("4 5 ");
        s[k][st++] = 4, s[k][st++] = 5;
        if(a > b) {
            //printf("6 ");
            s[k][st++] = 6;
            *v = *v + 1;
        }
        else {
            //printf("7 8 ");
            s[k][st++] = 7, s[k][st++] = 8;
            *v = *v - 1;
        }
        //printf("9 ");
        s[k][st++] = 9;
        if(a < b + 1) {
            //printf("10 ");
            s[k][st++] = 10;
            simpleRecFunc(a-1, b, v);
            //printf("11 ");
            s[k][st++] = 11;
            simpleRecFunc(a-2, *v, v);
        } else {
            //printf("12 13");
            s[k][st++] = 12, s[k][st++] = 13;
            simpleRecFunc(a-3, *v, v);
            s[k][st++] = 14;
            //printf("14 ");
        }

    }
    s[k][st++] = 15;
    //printf("15 ");
}
void Build() {
    //printf("16 17 18 19 20 ");
    int i, j;
    for(i = 0; i <= 20; i++)
        for(j = 0; j <= 100; j++) {
            s[k][0] = 16, s[k][1] = 17, s[k][2] = 18, s[k][3] = 19, s[k][4] = 20;
            st = 5;
            int x = i, y = j, z = 0;
            simpleRecFunc(x, y, &z);
            //printf("21\n");
            s[k][st++] = 21;
            s[k][st++] = -1;
            k++;
        }
}
int main() {
    Build();
    int T;
    char Sa[100000];
    scanf("%d", &T);
    gets(Sa);
    while(T--) {
        gets(Sa);
        int A[1025], n = 0, tmp = 0, g = 0, i, j;
        for(i = 0; Sa[i]; i++)
            if(Sa[i] >= '0' && Sa[i] <= '9')
                g = 1, tmp = tmp * 10+ Sa[i]-'0';
            else {
                if(g) {
                    A[n++] = tmp;
                }
                tmp = 0, g = 0;
            }
        if(g) {
            A[n++] = tmp;
        }
        A[n++] = -1;
        int flag = 0;
        for(i = 0; i < k; i++) {
            for(j = 0; s[i][j] != -1; j++)
                if(s[i][j] != A[j])
                    break;
            if(s[i][j] == -1 && A[j] == -1) {
                flag = 1;
                break;
            }
        }
        puts(flag ? "feasible" : "infeasible");
    }
    return 0;
}