Description

假設只能使用兩種符號來組成字串，譬如 IOIOI 或 OOII，都是由 I 和 O 組成，長度分別是 5 和 4。如果給定一個這樣的字串，同時又告訴你其中只有N個符號是正確的，能否把全部可能的答案都產生出來？例如輸入的字串是 TTTFF，然後又跟你說其中只對了 4 個符號，則可能的答案應該會有下面五種： 

TTTFT
TTTTF
TTFFF
TFTFF
FTTFF
再舉一個例子，如果輸入的字串是 OXOX，而其中只有 2 個符號是對的，則可能的答案會有底下六種：
OXXO
OOOO
OOXX
XXOO
XXXX
XOOX
答案要依照一定順序列出。決定順序的規則如下：盡量讓靠右邊的符號先變，盡量讓靠左邊的符號維持不變。以上面的輸入字串 OXOX (2個符號正確)為例，答案 OXXO 會排 OOOO 前面，因為 OXXO 和原本的輸入字串 OXOX 的最左兩個符號是相同的，但是 OOOO 和原本的輸入字串 OXOX 則是左邊第二個符號就不相同，所以 OXXO 的順位高於 OOOO。同理可以去檢驗其他順序，例如答案OOXX 順位高於 XXOO，因為OOXX 最左邊的符號和原輸入 OXOX 相同，但 XXOO 最左邊的符號就已經和 OXOX 不同。
再看一個範例：假設構成的符號有P 和 Q，輸入的字串是PPP，只對 1 個符號，則答案是
PQQ
QPQ
QQP
註:這一題可以自己寫，也可以直接改程式框架，寫出 void check_bits(int cur_bit, int num_hits)。
 

Hint:

#include 
#include 
#define MAXBITS 16

char bits[3];
char input[MAXBITS+1];
char answer[MAXBITS+1];
int NBITS;

void check_bits(int cur_bit, int num_hits);
char flip(char ch);

int main(void)
{
    int nhits;

    /* Read the two symbols for the binary bits,
    e.g, OI, 01, OX, or -+, etc. */
    scanf("%2s", bits);

    /* Read the input bit string. */
    scanf("%s", input);
    NBITS = strlen(input);

    /* The answers will be stored in the array answer[] */
    answer[NBITS] = '\0';

    /* Read the number of correct bits */
    scanf("%d", &nhits);

    /* Call the recursive function check_bits
    Start from the leftmost bit. */
    check_bits(0, nhits);

    return 0;
}

/*
1.
The value of cur_bit keeps increasing as we
recursively call check_bits().
2.
If input[cur_bit] is correct, the value of num_hits
should decrease; otherwise we should keep num_hits unchanged
and check the next bit.
3.
Copy the bit from input[cur_bit] or flip the bit,
and store the result in the array answer[].
4.
If the recursive call reaches the end of the input,
it is done and we may print the answer using
    printf("%s
", answer);
*/
void check_bits(int cur_bit, int num_hits)
{
    /* YOUR CODE */

}

/*
Flip the bit. For example,
0 <--> 1
O <--> I
...
*/
char flip(char ch)
{
    return ( (ch==bits[0]) ? bits[1] : bits[0] );
}

Input

輸入資料會有三行。
第一行是兩個相連的字元，用來指出構成字串的符號是哪兩個。 (例如 "OI")
第二行是輸入的字串，假設字串長度最多不超過 16 個字元。 (例如 "IIOOIIOO")
第三行是正確的符號個數，假設正確的個數一定大於 0，且小於等於字串長度。

Output

每一行顯示一種可能的答案，結尾都要換行 (都要加 )。要注意輸出的答案的順序。列出的順序如果沒有按照題目規定，Online Judge 會判定為錯誤。

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

以範例程式為基礎，完成其中缺少的 zip 函數。這個函數的作用是將兩個 lists 合併，對應位置的元素組成一個 pair，然後產生一個新的 list 包含所有的 pairs。也就是從兩個 lists 變成一個 list of pairs。
底下的表示法，方括號 [] 代表 list，圓括弧 () 代表 pair。
譬如第一個 list 是 [1,2,3] 而第二個是 ["a","b","c"]，經過 zip 之後變成
[(1,"a"),(2,"b"),(3,"c")]。
接著如果再用第二個 list 和第一次 zip 之後的結果，再做一次 zip，結果會變成
[("a",(1,"a")),("b",(2,"b")),("c",(3,"c"))]
然後第一次 zip 和第二次 zip 得到的兩個 lists，再做第三次 zip 就變成
[((1,"a"),("a",(1,"a"))),((2,"b"),("b",(2,"b"))),((3,"c"),("c",(3,"c")))]

上述的操作已經寫在範例程式中，只要將 zip 正確寫出，就能產生上述的執行結果。

範例程式:

#include 
#include 
#include 
#include 


/* incomplete struct Atom */
struct Atom;

/* a pair of atom */
typedef struct Pair {
    struct Atom *left;
    struct Atom *right;
} Pair;

/* a list of atoms */
typedef struct List {
    struct Atom *data;
    struct List *next;
} List;

/* an atom can be a string, an int, a pair of atoms, or a list */
typedef struct Atom {
    char str[21];
    int val;
    Pair *pair;
    List *lst;
    int dtype; /* 0 for string, 1 for int, 2 for pair, 3 for list*/
} Atom;



/* functions for creating an atom */
Atom* atom_str(char *str);
Atom* atom_val(int val);

Atom* copy_atom(Atom *aptr);
void print_atom(Atom *aptr);
void free_atom(Atom *atpr);

/* convert an atom to a single-atom list */
List* atom_to_list(Atom *a);

/* this function is important */
/* useful for creating a new copy of an existing list */
List* cons(Atom *a, List *b);

void print_list(List *lptr);
void free_list(List *lptr);
int length(List *lptr);
List* read_list_helper(List *l, int n);
List* read_list(void);

Atom* head(List *lptr);
List* tail(List *lptr);

List* zip(List *lptr1, List *lptr2);
Pair* unzip(List *lptr);

List* take(int n, List *l);
List* drop(int n, List *l);

Pair* pair_list(List *lptr1, List *lptr2);
Pair* split_at(int n, List *l);

void print_pair(Pair* p);
void free_pair(Pair* p);

int main(void)
{
    List *s1, *s2, *s3;
    int N, i;

    s1 = read_list();
    s2 = read_list();
    s3 = NULL;

    scanf("%d", &N);
    for (i=0; istr[0] = '\0';
    } else {
        strncpy(aptr->str, str, 20);
    }
    aptr->val = 0;
    aptr->pair = NULL;
    aptr->lst = NULL;
    aptr->dtype = 0;
    return aptr;
}

/* Given a value, create a new atom */
Atom* atom_val(int val)
{
    Atom *aptr = (Atom*) malloc(sizeof(Atom));
    aptr->str[0] = '\0';
    aptr->val = val;
    aptr->pair = NULL;
    aptr->lst = NULL;
    aptr->dtype = 1;
    return aptr;
}


Atom* copy_atom(Atom *aptr)
{
    Atom *aptr_new;

    aptr_new = (Atom*) malloc(sizeof(Atom));

    if (aptr_new==NULL) return NULL;
    if (aptr==NULL) return NULL;

    aptr_new->dtype = aptr->dtype;

    if (aptr->dtype == 0) {
        strncpy(aptr_new->str, aptr->str, 20);
    } else if (aptr->dtype == 1) {
        aptr_new->val = aptr->val;
    } else if (aptr->dtype == 2) {
        if (aptr->pair == NULL) {
            aptr_new->pair = NULL;
        } else {
            aptr_new->pair = (Pair *) malloc(sizeof(Pair));
            aptr_new->pair->left = copy_atom(aptr->pair->left);
            aptr_new->pair->right = copy_atom(aptr->pair->right);
        }
    } else if (aptr->dtype == 3) {
        if (aptr->lst==NULL) {
            aptr_new->lst = NULL;
        } else {
            aptr_new->lst = cons(head(aptr->lst), tail(aptr->lst));
        }
    }
    return aptr_new;
}

void print_atom(Atom *aptr)
{
    if (aptr==NULL) {
        printf("Empty");
        return;
    }
    switch (aptr->dtype) {
    case 0:
        printf("\"%s\"", aptr->str);
        break;
    case 1:
        printf("%d", aptr->val);
        break;
    case 2:
        print_pair(aptr->pair);
        break;
    case 3:
        print_list(aptr->lst);
        break;
    default:
        printf("Undefined.");
    }

}
/* Given an atom, create a list containing the atom. */
List* atom_to_list(Atom *a)
{
    List *b;
    b = (List*) malloc(sizeof(List));
    b->next = NULL;
    b->data = copy_atom(a);
    return b;
}

/* create a new list and add the atom to the head */
List* cons(Atom *a, List *b)
{
    List *c;

    c = atom_to_list(a);
    if (b!=NULL) {
        c->next = cons(head(b), tail(b));
    }

    return c;
}

void print_list(List *lptr)
{
    printf("[");
    while (lptr!=NULL) {
        print_atom(lptr->data);
        if (lptr->next != NULL)
            printf(",");
        lptr = lptr->next;
    }
    printf("]");
}

int len_helper(List *lptr, int len)
{
    if (lptr==NULL) return len;
    else return len_helper(lptr->next, len+1);
}
int length(List *lptr)
{
    return len_helper(lptr, 0);
}

void free_atom(Atom *aptr)
{
    if (aptr != NULL) {
        if (aptr->dtype==2) {
            free_pair(aptr->pair);
        } else if (aptr->dtype==3) {
            free_list(aptr->lst);
        }
        free(aptr);
    }
}

void free_list(List *lptr)
{
    List *p;
    if (lptr!=NULL) {
        p = tail(lptr);
        if (head(lptr)!=NULL) {
            free_atom(head(lptr));
        }
        free_list(p);
    }
}

Atom* head(List *lptr)
{
    return lptr->data;
}

List* tail(List *lptr)
{
    return (lptr==NULL) ? NULL : lptr->next;
}

/* create a new list combining a string list and a value list
If the two input lists have different lengths, the new list will be
of the same length as the shorter one.
*/
List* zip(List *lptr1, List *lptr2)
{
    Atom a;
    List *l1, *l2;

    if ( ??? ) { // lptr1 或 lptr2 兩者有一個是 NULL
        return NULL;
    } else {
        a.pair = ???; // malloc 取得一塊 Pair 空間
        a.pair->left = ???; // 利用  copy_atom  複製 lptr1 的開頭第一個 atom
        a.pair->right = ???; // 利用  copy_atom  複製 lptr2 的開頭第一個 atom
        a.dtype = 2;
        l1 = ??? // 利用 zip 處理剩下的 lists  (提示: 用遞迴)
        l2 = cons(&a, l1); // 利用 cons 造出新的 list
        free_pair(a.pair);
        free_list(l1);
        return l2;
    }
}

void print_pair(Pair *p)
{
    printf("(");
    print_atom(p->left);
    printf(",");
    print_atom(p->right);
    printf(")");
}

void free_pair(Pair* p)
{
    if (p!=NULL) {
        free_atom(p->left);
        free_atom(p->right);
        free(p);
    }
}

Input

輸入資料會有五行。
第一行是一個整數 M1，代表第一個 list 包含的資料筆數，第二行則是 M1 筆資料，每筆用空白隔開。
第三行是一個整數 M2，代表第二個 list 包含的資料筆數，第四行則是 M2 筆資料，每筆用空白隔開。
第五行則是一個整數 N。代表執行 zip 的次數。

Output

輸出只有一行，列出經過 zip 之後的 list 內容。最後有換行。

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

• Midtern exam 2 accounts for 15% of your semester grade.
• The grade of your midterm exam 2 is computed as follows:
  Let P1 be 11001 , P2 be 11935, P3 be 13206, P4 be 13207,

Grade = Score(P1) *(4.5/4)+ Score(P2)*(4.5/5) + max { Score(P3)*(6/10), Score(P4)*(6/10) },
where Score(Pi) is the number of testcases you earned for problem Pi.

• That is, choose only one of P3 and P4 to solve!
• There are totally 15 points.

• {11001, 11935} --> {13206, 13207} 

• For problem 13206, the main objective is to test the implementation of polymorphism, inheritance and stringstream. The problem is not hard. But be aware that if you're not familiar with inheritance, it's possible to get no score among all subtask.
• For problem 13207, the main objective is to test the concept of polymorphism and optimization of your strategy. The problem is similar to practice version. But be aware that if you're not good at optimization, solving 13206 may easier for you to get All Accepted.

Input

Output

Sample Input  Download

Sample Output  Download

Tags

Discuss