Homework 5 - HackMD

--- tags: homework --- # Homework 5 ###### tags: `linked list` `stack` ### Schedule * Release: 12:10 PM, 2020.05.19, Wed. * First Due: 12:10 PM, 2020.05.26, 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) * Extend Date: 12:10 PM, 2020.06.16, Wed. (40% score) --- ## 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` function, 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. Don't deal with this part, and we would give a `Header` pointer to the beginning of a linked list. 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`. You MUST deal with this part and output for each case. 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.  ![](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` function. 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 Don't deal with the part. TA provide `main.c` * 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, don't deal with the part. TA would check your answer in `main.c` * 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