---
# System prepended metadata

title: Homework 5
tags: [homework]

---

---
tags: homework
---

# Homework 5

###### tags: `linked list` `stack`

### Schedule

* Release: 12:10 PM, 2020.05.19, Wed.
* First Due: <b>12:10 PM</b>, <font color="blue"><b>2020.05.26</b></font>, Wed. (100% score)
* Second Due: 12:10 PM, 2020.06.02, Wed. (80% score)
* Extend Third Due: 12:10 PM, 2020.06.09, Wed. (60% score)
* <font color="red">Extend Date: 12:10 PM, 2020.06.16, Wed. (40% score)</font>

---

## TA information

> Contact with TAs if having any problems.

* 莊博傑 Po-Chieh Chuang / 40747019s@gapps.ntnu.edu.tw
* 林育辰 Yu-Chen Lin / 40771131h@gapps.ntnu.edu.tw

---

## Intersection of Three Linked Lists (20%)

> [name=Leetcode]

### Description

Given the heads of three singly linked-lists `a`, `b` and `c`, return the nodes at which the three lists intersect. You can return they in any order.

For example, the following three linked lists begin to intersect at node `d1` and `d2`:

```graphviz
digraph {
  rankdir=LR
  node [shape=circle]
  
  a1 -> a2
  a2 -> a3
  
  b1 -> b2
  b2 -> b3
  
  c1 -> c2
  c2 -> c3
  
  c3 -> d1
  b3 -> d1
  d1 -> d2
  d2 -> d3
  
  a3 -> d2
}
```

It is **guaranteed** that there are no cycles anywhere in the entire linked structure.

You should submit a file implement `find_intersection`, below is the content of files used in judge.

#### `list.h`

```c=!
#pragma once

struct ListNode
{
    int val;
    struct ListNode *next;
};

// Create a new node
struct ListNode *node_new(int);
// Free list
void node_free(struct ListNode *);
// Print single node's detailed info
void node_print(const struct ListNode *);
// Print vals of the list
void node_print_all(const struct ListNode *);
// Append back to front and return back
struct ListNode *node_append(struct ListNode *front, struct ListNode *back);
```

#### `list.c`

```c=!
#include <stdlib.h>
#include <assert.h>
#include <stdio.h>
#include "list.h"

struct ListNode *node_new(int val)
{
    struct ListNode *ret = malloc(sizeof(struct ListNode));
    if (!ret)
    {
        puts("Node allocation failed.");
        exit(1);
    }
    ret->val = val
    ret->next = NULL;
    return ret;
}

void node_print(const struct ListNode *node)
{
    printf("ListNode@%p { val: %d, next: %p }", node, node->val, node->next);
}

void node_print_all(const struct ListNode *node)
{
    while (node)
    {
        printf("%d ", node->val);
        node = node->next;
    }
}

struct ListNode *node_append(struct ListNode *front, struct ListNode *back)
{
    front->next = back;
    return back;
}

void node_free(struct ListNode *node)
{
    struct ListNode *prev = NULL;
    while (node)
    {
        if (prev)
            free(prev);
        prev = node;
        node = node->next;
    }
    if (prev)
        free(prev);
}

```

#### `find_intersection.h`

```c=!
#pragma once

#include "list.h"

// Return number of nodes you found, and put them into `out`. 
// `n` means that you can put at most `n` nodes into `out`,
// but in this problem you can ignore it.
int find_intersection(struct ListNode **lists, struct ListNode **out, int n);
```

#### `main.c`

```c=
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <assert.h>
#include "list.h"
#include "find_intersection.h"

struct ListNode *build_list(struct ListNode **nodes)
{
    struct ListNode *r = NULL, *r2 = NULL;
    int n, t;
    scanf("%d", &n);
    // Empty list
    if (!n)
        return r;
    // Allocate first node
    scanf("%d", &t);
    r = nodes[t];
    // Read remain part
    r2 = r;
    for (int i = 0; i < n - 1; i++)
    {
        scanf("%d", &t);
        r2 = node_append(r2, nodes[t]);
    }
    return r;
}

int main()
{
    int n, t;
    scanf("%d", &n);
    // Process nodes
    struct ListNode **nodes = calloc(n, sizeof(struct ListNode *));
    for (size_t i = 0; i < n; i++)
    {
        scanf("%d", &t);
        nodes[i] = node_new(t);
    }
    // Create lists
    struct ListNode *lists[] = {
        build_list(nodes),
        build_list(nodes),
        build_list(nodes),
    };
    // Find intersection part
    struct ListNode *intersections[2] = {};
    int cnt = find_intersection(lists, intersections, 2);
    // Calculate answer
    int ans = 0;
    for (size_t i = 0; i < cnt; i++)
    {
        int find = 0;
        for (size_t j = 0; j < n; j++)
        {
            if (intersections[i] == nodes[j])
            {
                ans ^= nodes[j]->val;
                find = 1;
                break;
            }
        }
        assert(find);
    }
    printf("%d\n", ans);
    return 0;
}
```

### Input

Inputs follows below formats:

```
N n_0 n_1 n_2 ... n_{N-1}
A a_0 a_1 a_2 ... a_{A-1}
B b_0 b_1 b_2 ... b_{B-1}
C c_0 c_1 c_2 ... c_{C-1}
```

* $N$ is number of nodes.
* $A, B,C$ are number of nodes in lists `a`, `b`, `c`
* $a_i, b_i, c_i$ are the index of nodes for $i\text{-th}$ nodes in lists `a`, `b`, `c`.
  For example, `1` means that node is `n_1`.

#### Limits

* $N \le 100$
* $1 \le \text{Node.val} \le 10^9$

#### Subtasks

|           | Limits                            | Score |
| --------- |:--------------------------------- | -----:|
| #0        | $N = 10$, no intersection.        |  $10$ |
| #1        | $N = 10$, one intersection.       |  $30$ |
| #2        | $N = 100$, no intersection.       |  $20$ |
| #3        | $N = 100$, multiple intersection. |  $40$ |
| **Total** |                                   | $100$ |

### Output

Your implementation of `find_intersection` should return number of nodes you found, and put them into `out`. The order doesn't matter.

The standard output are xor of nodes' value, or `0` if no intersection.

### Sample Input 0

```
5 1 2 3 4 5
2 1 2
2 3 4
1 0
```

### Sample Output 0

```
0
```

### Sample Input 1

```
7 1 2 3 4 5 6 7
4 0 1 2 3
4 4 1 2 3
4 5 6 2 3
```

### Sample Output 1

```
1
```

### Hint

* Adapted from [Leetcode](https://leetcode.com/problems/intersection-of-two-linked-lists/)
* If a node is at the end of list, it’s `next` will be `NULL`.
* Print `0` give you 30 pt.
* Sample 0 prints `0` because no intersection, it looks like this graph:
  ```graphviz
  digraph {
    rankdir=LR
    node [shape=circle]

    1 -> 2
    3 -> 4
    0
  }
  ```
* Sample 1 looks like this graph:
  ```graphviz
  digraph {
    rankdir=LR
    node [shape=circle]

    0 -> 1
    1 -> 2
    2 -> 3
    
    4 -> 1
    
    5 -> 6
    6 -> 2
  }
  ```
  We can find out that `1` and `2` are intersection nodes, and their values are `2` and `3`, respectively. We get the answer is `2 ^ 3 = 1`

### Problem-solving Ideas

> Announce after about 1 week

* Use an array `v` to record nodes.
* Iterate these lists, if the current node can be found in `v`, then it must be an intersection, otherwise, add it to `v`.

---

## Merge k Sorted Lists (20%)

> [name=Leetcode]

### Description

You are given an array of `k` linked-lists lists, each linked-list is sorted in ascending order.
Merge all the linked-lists into one sorted linked-list and return it.

In this problem, you should implement a function `merge` and upload your implemetation, **not** a submission contains `main` function.

Below are the content files used in judge.

#### `list.h`

```c=!
#pragma once

struct ListNode
{
    int val;
    struct ListNode *next;
};

// Create a new node
struct ListNode *node_new(int);
// Free list
void node_free(struct ListNode *);
// Print single node's detailed info
void node_print(const struct ListNode *);
// Print vals of the list
void node_print_all(const struct ListNode *);
// Append back to front and return back
struct ListNode *node_append(struct ListNode *front, struct ListNode *back);
```

#### `list.c`

```c=!
#include <stdlib.h>
#include <assert.h>
#include <stdio.h>
#include "list.h"

struct ListNode *node_new(int val)
{
    struct ListNode *ret = malloc(sizeof(struct ListNode));
    if (!ret)
    {
        puts("Node allocation failed.");
        exit(1);
    }
    ret->val = val;
    ret->next = NULL;
    return ret;
}

void node_print(const struct ListNode *node)
{
    printf("ListNode@%p { val: %d, next: %p }", node, node->val, node->next);
}

void node_print_all(const struct ListNode *node)
{
    while (node)
    {
        printf("%d ", node->val);
        node = node->next;
    }
}

struct ListNode *node_append(struct ListNode *front, struct ListNode *back)
{
    front->next = back;
    return back;
}

void node_free(struct ListNode *node)
{
    struct ListNode *prev = NULL;
    while (node)
    {
        if (prev)
            free(prev);
        prev = node;
        node = node->next;
    }
    if (prev)
        free(prev);
}

```

#### `merge.h`

```c=
#pragma once

#include "list.h"

// Merge lists, return merged head
struct ListNode *merge(struct ListNode[], int);
```

#### `main.c`

```c=
#include <stdio.h>
#include "list.h"
#include "merge.h"

struct ListNode *build_list()
{
    struct ListNode *r = NULL, *r2 = NULL;
    int n, t;
    scanf("%d", &n);
    // Allocate first node
    scanf("%d", &t);
    r = node_new(t);
    // Read remain part
    r2 = r;
    for (int i = 0; i < n - 1; i++)
    {
        scanf("%d", &t);
        r2 = node_append(r2, node_new(t));
    }
    return r;
}

int main()
{
    int k;
    scanf("%d", &k);
    // Build lists
    struct ListNode *lists[k];
    for (size_t i = 0; i < k; i++)
        lists[i] = build_list();
    // Merge & print
    struct ListNode *ans = merge(lists, k);
    node_print_all(ans);
    putchar('\n');

    return 0;
}
```

### Input

The input follows format below:

```
k
n_0 list_0
n_1 list_1
...
n_{k-1} list_{k-1}
```

* `k` is the number of list.
* For next `k` lines:
  * `n_i` is the $i\text{-th}$ list's size.
  * `list_i` is list's content, seperated by space.

#### Limits

* $k \le 100$
* $\sum|\text{list}| \le 10^4$
* $\text{Node.val} \le 10^4$

#### Subtasks

|           | Limits         | Score |
| --------- |:-------------- | -----:|
| #0        | $k=2, n=10$    |  $20$ |
| #1        | $k=2, n=100$   |  $20$ |
| #2        | $k=10, n=100$  |  $30$ |
| #3        | $k=100, n=100$ |  $30$ |
| **Total** |                | $100$ |

### Output

Return merged list.

### Sample Input 0

```
2
4 1 2 3 4
4 7 8 9 10
```

### Sample Output 0

```
1 2 3 4 7 8 9 10
```

### Hint

* Adapted from [Leetcode](https://leetcode.com/problems/merge-k-sorted-lists/)

### Problem-solving Ideas

> Announce after about 1 week

---


## Matrix Chain Multiplication (20%)

> [name=Yu-Chen Lin]

### Description
* Please implement `.h` <font color = "red"><b>function</b></font>, and the second part input and output is standard I/O, you should deal with those.

Suppose you have to evaluate an expression like $A \times B \times C \times D \times E$ where $A$, $B$, $C$, $D$, and $E$ are **matrices**. 

Since matrix multiplication is associative, the order in which multiplications are performed is arbitrary. 

However, the number of elementary **multiplications** needed strongly depends on the evaluation **order** you choose.

For example, let $A$ be a $50 \times 10$ matrix, $B$ a $10 \times 20$ matrix and $C$ a $20 \times 5$ matrix. There are two different strategies to compute $A \times B \times C$, namely $(A \times  B) \times C$ and $A \times (B \times C)$.

The first one takes $15000$ elementary multiplications, but the second one only $3500$.
> Additionally, the first case:
>   * $Q = A \times B$, and the $Q$ is a $50 \times 20$ matrice.
>   * Its multiplication: $50 \times 20 \times 10$, the $10$ is the matrice mulplication between the each element on a row of $A$ and the each element element on a column of $B$.
>   * Next, $N = Q \times C$, and the $N$ ia s $50 \times 5$ matrice.
>   * Its multiplication: $50 \times 5 \times 20$
>
> So, the elementary multiplications is $50 \times 20 \times 10 + 50 \times 5 \times 20 = 10000 + 5000 = 15000$
>
> And the second case is $Q = B \times C$, and then $N = A \times Q$, and its elementary multiplications is $10 \times 5 \times 20 + 50 \times 5 \times 10 = 1000 + 2500 = 3500$
 
Your job is to write a program that determines the **number** of elementary multiplications needed for a given evaluation strategy.

Finally, we provide the `main.c` `MatrixChain.h` `MatrixChain.c` file context, and your job is to finish the `MatrixChain.c` and submit it to NOJ.

* `MatrixChain.h`

```c=
#pragma once

#include <stdint.h>
#define MAX_ELEMENTS 10005

typedef struct matrice {
    char chr;
    int32_t row;
    int32_t col;
    struct matrice *next;
} Matrice;

//You can define the stack you own, but the name should alias to another name, e.g. stack_new, stack_covid....
typedef struct stack {
    int32_t top;
    Matrice elements[MAX_ELEMENTS];
}Stack;

//Could develop you own function to solve this problem
void push_Stack(Stack *stack, Matrice my);
void init_Stack(Stack *stack);
Matrice pop_Stack(Stack *stack);
Matrice find_element(Matrice *ptr, char chr);

//MUST complete
void solve(Matrice *Header);
```

* `main.c`

```c=
#include <stdio.h>
#include <stdint.h>
#include <stdlib.h>
#include "MatrixChain.h"

int main() {
    //Part 1 ==> store to linked-list
    //
    int32_t t = 0;
    scanf("%d\n", &t);

    Matrice *Header = NULL;
    Matrice *res = Header;

    for (int32_t i = 0 ; i < t ; i++) {
        Matrice *TEMP = (Matrice *)calloc(1, sizeof(Matrice));
        scanf("%c %d %d\n", &TEMP->chr, &TEMP->row, &TEMP->col);
        TEMP->next = NULL;

        if (Header == NULL) {
            Header = TEMP;
            res = Header;
        } else {
            res->next = TEMP;
            res = res->next;
        }
    }
    //
    //END part 1

    solve(Header);

    return 0;
}
```

* `MatrixChain.c`

```c=
//Should include the header file you need.
#include "MatrixChain.h"

//Choose, you can choose to develop you own function to deal with this problem
void push_Stack(Stack *stack, Matrice my) {
}
void init_Stack(Stack *stack) {
}
Matrice pop_Stack(Stack *stack) {
}
Matrice find_element(Matrice *ptr, char chr) {
}

//MUST
void solve(Matrice *Header) {
    //Implement this
    //
    //You MUST to deal with 
    //the input (second part) & Output on this function
}
```

### Input
Input consists of two parts: a list of matrices and a list of expressions.

<font color="red"><b>Don't deal with this part, and we would give a `Header` pointer to the beginning of a linked list.</b></font>
The first line of the input file contains one integer n ($1 \leq n \leq 26$), representing the number of matrices in the first part. The next n lines each contain one capital letter, specifying the name of the matrix, and two integers, specifying the number of rows and columns of the matrix.

We define the linked-list structure as follow:
```cpp=
typedef struct matrice {
    char chr;
    int32_t row;
    int32_t col;
    struct matrice *next;
} Matrice;
```

So, you could visit all the linked-list via the pointer `next` until the `next` pointer to `NULL`.


<font color = "blue"><b>You MUST deal with this part and output for each case.</b></font>
The second part of the input file strictly adheres to the following syntax (given in EBNF):

```
SecondPart = Line { Line } <EOF>
Line       = Expression <CR>
Expression = Matrix | "(" Expression Expression ")"
Matrix     = "A" | "B" | "C" | ... | "X" | "Y" | "Z"
```

#### Limits
* $\text{row, col} > 0,\  \text{row, col} \in \mathbb{N}$
* $\text{chr}$ all belong to uppercase, that is `A` to `Z`.
* The string ONLY contains uppercase(`A` to `Z`) and parentheses `(` `)` in the second part. And those all letter exist in the linked-list on the first part.

#### Subtasks

|           | Limits | Score |
| --------- |:------ | -----:|
| #0        |    $n \leq 5, \ \text{col} = \text{row}$, and the string only contains one kind of uppercase letter, and one or zero pair parentheses.    | $25$ |
| #1        |    $\text{col} = \text{row}$, and the string only contains uppercase and one or zero pair parentheses.    | $35$ |
| #2        |    $n \leq 10$    | $15$ |
| #3        |    Following the “limits” block conditions only.    | $25$ |
| **Total** |        | $100$ |

### Output
For each expression found in the second part of the input file, print one line containing the word `error` if evaluation of the expression leads to an error due to non-matching matrices.

Otherwise, print one line containing the number of elementary multiplications needed to evaluate the expression in the way specified by the parentheses.

### Sample Input 0
```
9            //All the information would store on linked-list
A 50 10      //
B 10 20      //
C 20 5       //
D 30 35      //
E 35 15      //
F 15 5       //
G 5 10       //
H 10 20      //
I 20 25      //
A
B
C
(AA)
(AB)
(AC)
(A(BC))
((AB)C)
(((((DE)F)G)H)I)
(D(E(F(G(HI)))))
((D(EF))((GH)I))
```

### Sample Output 0
```
0
0
0
error
10000
error
3500
15000
40500
47500
15125
```

### Hint
* We provide a diagram for the linked list in the first part. And we would give a `Header` pointer to the first element (`A`). You should visit the linked list to access the matrice information.

<!--
```mermaid
classDiagram

Header -\-> A
A -\-> B
B -\-> C
C -\-> D
D -\-> E
E -\-> F
F -\-> G
G -\-> H
H -\-> I
I -\-> NULL

class Header{
    .next
}

class A{
    .chr = A
    .row = 50
    .col = 10
    .next = addr. B
}

class B{
    .chr = B
    .row = 10
    .col = 20
    .next = addr. C
}

class C{
    .chr = C
    .row = 20
    .col = 5 
    .next = addr. D
}

class D{
    .chr = D
    .row = 30 
    .col = 35 
    .next = addr. E
}

class E{
    .chr = E
    .row = 35 
    .col = 15 
    .next = addr. F
}

class F{
    .chr = F
    .row = 15 
    .col = 5 
    .next = addr. G
}

class G{
    .chr = G
    .row = 5 
    .col = 10
    .next = addr. H
}

class H{
    .chr = H
    .row = 10 
    .col = 20
    .next = addr. I
}

class I{
    .chr = I
    .row = 20 
    .col = 25
    .next = NULL
}

class NULL{
    .val
}
```
-->
![](https://i.imgur.com/c4JRiTM.png)
* All the input string, there is not necessary to examine the parentheses validity.

### Problem-solving Ideas

> Announce after about 1 week

---

## Docchi Docchi? (20%)

> [name=Bogay]

### Description

> Tl;DR: Given a maze and actions, simulate the moves. See `input` sectino for more details.

*Nakiri Ayame* (百鬼あやめ) is a member of [Hololive](https://en.wikipedia.org/wiki/Hololive_Production#Hololive) 2nd generation. She has really a bad sense of direction. In one of her minecraft stream, she even coludn't find her house.

This leads to the birth of [Docchi Docchi Song](https://www.youtube.com/watch?v=UIAweLzHAZQ) ([English subtitled ver.](https://www.youtube.com/watch?v=qlVgC3tJoII)).

Recently, *Ayame* found that she cannot find her house again. To solve this problem, you decide to develop a program to help her to record locations.

### Input

The inputs follow the format below:

```
H W
map
actions
```

* $H$ and $W$ means the height and width of the map.
* $\text{map}$ contains $H$ lines, each line contains $W$ cahracters. `.` is grid that can walk through, and `#` can not.
* $\text{actions}$ means lines of actions, it has these choices:
  * `walk-forward`: go forward 1 grid.
  * `walk-backward`: go backward 1 grid.
  * `turn-right`: rotate the move direction 90 degree clockwise.
  * `turn-left`: rotate the move direction 90 degree counterclockwise.
  * `undo`: return to last status (i.e., location and direction).
  * `docchi`: print current location in format `x y`.

Here are some other details about the movement.

* The map's $(0, 0)$ located at top-left corner and $(H-1, W-1)$ located at bottom-right corner.
* *Ayame* starts from location $(0, 0)$ and stand toward right.
* For any invalid action, ignore it and don't record it.
  For exmaple, if the actions are:
  ```
  walk-forward
  walk-forward
  undo
  ```
  If the second walk is invalid due to encounter a unwalkable grid. The `undo` in thrid line will revert the first walk.

#### Limits

* $1 \le H,W \le 50$
* Number of actions $\le 10^4$
* Location $(0, 0)$ must be walkable.

#### Subtasks

|           | Limits             | Score |
| --------- |:------------------ | -----:|
| #0        | $H,W = 10$, no `#` |  $30$ |
| #1        | $H,W = 10$         |  $30$ |
| #3        | No other limits    |  $40$ |
| **Total** |                    | $100$ |

### Output

For each `docchi`, print the location of *Ayame*.

### Sample Input 0

```
3 3
...
...
...
walk-forward
walk-forward
docchi
```

### Sample Output 0

```
2 0
```

### Sample Input 1

```
3 3
...
.#.
...
walk-forward
turn-right
walk-forward
undo
walk-forward
docchi
```

### Sample Output 1

```
2 0
```

### Sample Input 2

```
3 3
...
...
...
walk-forward
walk-forward
walk-forward
walk-forward
walk-forward
walk-forward
walk-forward
docchi
```

### Sample Output 2

```
2 0
```

### Sample Input 3

```
3 3
...
...
...
walk-forward
docchi
walk-forward
docchi
```

### Sample Output 3

```
1 0
2 0
```

### Hint

* Use a stack to record status makes `undo` easy.
* There are 2 `c` in `docchi`.

### Problem-solving Ideas

> Announce after about 1 week

---


## Contact Status APP (20%)
> [name=Yu-Chen Lin]

### Description
* Please implement `.h` <font color = "red"><b>function</b></font>.

Now, we suffer from the distribution of some viruses and power cuts. This virus can be transmitted between humans through droplets and contact.

Then many activities become forbidden, and courses are requested to be held remotely. 


An application "Taiwan social distancing" was developed to trace the footprint of the users. Once a person is confirmed to have the virus, each user of the app will be notified whether she/he has met the confirmed case. 

The tech of the application base on the Bluetooth identification code, you could imagine that as a "business card", which be exchange each other as meet someone.

Assume that the following **structure** is adopted in the source code of the app:

```c=
typedef struct ContactStatus {
    int32_t age;
    bool isConfirmed;
    struct ContactStatus *prev;
    struct ContactStatus *next;
} s_ContactStatus;
```

A limit that meets **2** people for each and the footprint would **form a cycle** in this problem. Refer to the diagram:

![](https://i.imgur.com/BugYQWx.png)

However, users make the mistake to press the button **report random code** maybe. In a such case, the user will be marked as a confirmed case, and the user stored in the `prev` and `next` pointer would be informed.

Given one "ContactStatus" pointer, and a user age that mistaking to press the button. Your job is to write a program to **remove** such a user(Bob). Additionally, assign the `next` pointer of Bob `prev`(user) as the Bob `next`, and the `prev` pointer of Bob `next`(user) as the "Bob" `prev`.  Furthermore, the user age is **NOT** unique.

It's important that if NOT exist the **given** age, or **all** the given age its element `isConfirmed` equal to `false`,  please **ignore** the operator and **print** `System error!` ending with a newline charater. Besides, if the `Header` satisfies the "mistaking" user, you should return the `next` pointer of `Header`, if the `next` also satisfy the condition, return its `next`, otherwise, return `Header`.

For example, we have a cycle as follow:
![](https://i.imgur.com/Fqp0Ne4.jpg)

Given a pointer that directs the element `7`, and the age of the "mistaking" user is `48`.

However, we MUST remove `48` from this cycle.
![](https://i.imgur.com/93nLjvL.jpg)



Now, the `next` pointer of `2` direct to `7`, and the `prev` pointer of `7` direct to `2`, the `48` would disappear forever.


> p.s. Such linked-list is **ring** structure, like as follow:
![](https://i.imgur.com/5exGe93.png)
> The diagram origin from Prof. Chi's handout.


Finally, we provide the `main.c` `ContactStatus.h` `ContactStatus.c` file context, and your job is to **finish** the `ContactStatus.c` and submit it to NOJ.

* `main.c`
```c=
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>
#include "ContactStatus.h"

int main() {
    int32_t t = 0;
    scanf("%d", &t);

    s_ContactStatus *Header = NULL;
    s_ContactStatus *res= NULL;

    s_ContactStatus check_ans[t];

    //build RING structure
    for (int32_t i = 0 ; i < t ; i++) {
        s_ContactStatus *TEMP = (s_ContactStatus *)calloc(1, sizeof(s_ContactStatus));
        int32_t age = 0;
        char isConfirmedStr[20];
        bool isConfirmed = false;
        scanf("%d %s", &age, isConfirmedStr);

        if (strcmp(isConfirmedStr, "true") == 0) {
            isConfirmed = true;
        } else {
            isConfirmed = false;
        }

        *TEMP = (s_ContactStatus){
            .age = age,
            .isConfirmed = isConfirmed,
            .prev = res,
            .next = NULL
        };

        check_ans[i] = *TEMP;

        if (Header == NULL) {
            TEMP->prev = NULL;
            Header = TEMP;
            res = Header;
        } else {
            TEMP->prev = res;
            res->next = TEMP;
            res = TEMP;
        }
    }
    Header->prev = res;
    res->next = Header;

    //call your function to remove some element
    int32_t target = 0;
    scanf("%d", &target);
    Header = removeFromRing(target, Header);

    int32_t count = 0, reg = 0;
    bool check = true;

    //check the answer
    s_ContactStatus* pointer[2] = {Header, Header};

    do {
        printf("%d ", pointer[0]->age);
        if (pointer[0]->isConfirmed == true) {
            printf("true\n");
        } else {
            printf("false\n");
        }

        while (check_ans[count].age == target && check_ans[count].isConfirmed == true) {
            count += 1;
        }

        if (check_ans[count].age != pointer[0]->age &&
                check_ans[count].isConfirmed != pointer[0]->isConfirmed) {
            check = false;
            break;
        }
        count += 1;
        pointer[0] = pointer[0]->next;
        reg += 1;
        
    } while (pointer[0] != Header && reg < t);

    for (int32_t i = 0 ; i < reg ; i++) {
        pointer[1] = pointer[1]->prev;
    }

    if (check == false || pointer[1] != pointer[0]) {
        printf("Wrong Answer!\n");
    }

    return 0;
}
```

---

* `ContactStatus.h`
```c=
#pragma once

#include <stdint.h>
#include <stdbool.h>

typedef struct ContactStatus {
    int32_t age;
    bool isConfirmed;
    struct ContactStatus *prev;
    struct ContactStatus *next;
} s_ContactStatus;

s_ContactStatus* removeFromRing(int32_t target, s_ContactStatus* Header);
```

---

* `ContactStatus.c`

```c=
#include <stdio.h>
#include "ContactStatus.h"

s_ContactStatus* removeFromRing(int32_t target, s_ContactStatus* Header) {
    //Implement here
}
```

---

#### Subtasks
|           | Limits | Score |
| --------- |:------ | -----:|
| #0-0        | The age of the confirmed case is unique.      | $25$ |
| #0-1        | The age of the confirmed case is unique.      | $20$ |
| #0-2        | The age of the confirmed case is unique.      | $15$ |
| #1-3        |    Following the “limits” block conditions only.    | $15$ |
| #1-4        |    Following the “limits” block conditions only.    | $15$ |
| #1-5        |    Following the “limits” block conditions only.    | $10$ |
| **Total** |        | $100$ |

* In subtask 1, we divide testcases into some groups. You would receive a partial score if your submission is accepted in each group. All the groups meet the requirement for subtask 1. Account for 60 pts totally.
* In subtask 2, there are some groups of testcases that meet the requirement on subtask 2 and account for 40 pts totally.


---

### Input
<font color = "red"><b>Don't deal with the part. TA provide `main.c` </b></font>

* The 1st line of the input contains one numbers `t`. Two consecutive numbers are separated by a space. 
* The following `t` lines are the information about each `ContactStatus`. Each line contains two numbers `age` `isConfirmed`.
* Next, an integer `target` representing the age of the mistaking user.

#### Limits
* $\text{isConfirm} \in$ `true` `false`.
* $2^{31}-1 > \text{age}, \text{target} > 0$



### Output
You ONLY to print `System error!` if the condition are satisfied(like the problem description), otherwise, <font color = "red"><b>don't deal with the part. TA would check your answer in `main.c` </b></font>

* Print all the information after removing those **mistaking** users.


### Sample Input 0
```
5
48 true
2 false
17 false
91 false
7 false
48
```

### Sample Output 0
```
2 false
17 false
91 false
7 false
```

### Sample Input 1
```
5
48 true
2 false
17 false
48 false
7 false
48
```

### Sample Output 1
```
2 false
17 false
48 false
7 false
```

### Sample Input 2
```
5
19 true
2 false
17 false
34 false
7 false
48
```

### Sample Output 2
```
System error!
19 true
2 false
17 false
34 false
7 false
```

### Sample Input 3
```
5
48 true
2 false
17 false
48 true
7 false
48
```

### Sample Output 3
```
2 false
17 false
7 false
```

### Sample Input 4
```
5
48 false
2 false
17 false
48 false
7 false
48
```

### Sample Output 4
```
System error!
48 false
2 false
17 false
48 false
7 false
```

### Sample Input 5
```
15
49 true
49 true
109 true
192 true
72 false
22 true
12 true
54 true
192 false
12 false
27 false
12 true
1 true
12 true
192 true
49
```

### Sample Output 5
```
109 true
192 true
72 false
22 true
12 true
54 true
192 false
12 false
27 false
12 true
1 true
12 true
192 true
```

### Sample Input 6
```
3
100000 false
100000 true
100000 false
100000
```

### Sample Output 6
```
100000 false
100000 false
```

### Hint

* After removing those elements, the contact status still forms a cycle.
* Pay attention to the case that `Header` is removed and the `next` also be removed.
* How to examine the pointer back to the beginning of the pointer.

### Problem-solving Ideas

> Announce after about 1 week
