---
# System prepended metadata

title: My code list - 110 - I2P2

---

# My code list - 110 - I2P2

## *midterm 1*
:::spoiler HW2 - Gey cool~~ <font color="#FD3004">AC</font>

```c=
//HW2 - Gey cool~
#include <stdio.h>
#define LL long long int
LL n, q;
LL sum[2000001];
LL calculate_sum(LL x, LL y)
{
    if (x > y)
        return (sum[n] - sum[x - 1] + sum[y]);
    else
        return (sum[y] - sum[x - 1]);
}
int main(void)
{
    while (scanf("%lld %lld", &n, &q) != EOF)
    {
        //calculate prefix sum
        LL temp1;
        memset(sum, 0, sizeof(LL) * 2000001);
        for (int i = 0; i < n; i++)
        {
            scanf("%lld", &temp1);
            // 從1開始加, 因為index從1開始
            sum[i + 1] = temp1 + sum[i];
        }
        
        LL temp2, temp3, tempsum;
        LL biggest = 0, left = 0, right = 0;
        for (int i = 0; i < q; i++)
        {
            scanf("%lld %lld", &temp2, &temp3);
            tempsum = calculate_sum(temp2, temp3);
            if (tempsum > biggest)
            {
                left = temp2;
                right = temp3;
                biggest = tempsum;
            }
        }
        printf("Max_range: (%lld,%lld); Value: %lld\n", left, right, biggest);
    }
    return 0;
}
```
:::
:::spoiler HW2 - TA's Heartfelt <font color="#FD3004">AC</font>

```c=
// HW2 - TA's Heartfelt
// unsigned can be remove, but more clearly when added
#include <stdio.h>
int main(void)
{
    float x;
    while (~scanf("%f", &x))
    {
        unsigned int ans = *((unsigned int *)&x);
        for(int i = 31; i >= 0; i--){
            printf("%d",( ans & (1 << i) )? 1 : 0);
        }
        printf("\n");
    }
    return 0;
}
```
:::
:::spoiler HW2 - after rain - (partial judge)  <font color="#FD3004">AC</font>

```c=
//HW2 - after rain
//it is empty when id = 0 
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
typedef struct _NODE
{
    char color[10];
    struct _NODE *next;
} Node;
void insert(Node** head, char* color, int dest)
{
    Node *now = (*head), *tmp;
    //stop when reach the last element or the number we want
    for(int id = 0; now->next != NULL && id != dest; now = now->next, id++);
    tmp = (Node*)malloc(sizeof(Node));
    strcpy(tmp->color, color);
    tmp->next = now->next;
    now->next = tmp;
}

void erase1(Node** head, int dest)
{
    Node *now = (*head), *prev = NULL;
    for(int id = 0; now->next != NULL && id != dest; prev = now, now = now->next, id++);
    if(prev == NULL) return;
    prev->next = now->next;
    free(now);
}

void erase2(Node** head, char* color)
{
    Node *now = (*head), *prev = NULL;
    while(now != NULL)
    {
        if(!strcmp(now->color, color)){
            prev->next = now->next;
            free(now);
            now = prev;
        }
      	prev = now;
        now = now->next;
    }
}

void reverse(Node **head, int dest1, int dest2)
{
    Node *now = (*head), *l = NULL, *tmp = NULL;
    int id;
    for(id = 0; now->next != NULL && id != dest1; l = now, now = now->next, id++);
    while(now->next !=NULL && id < dest2){
        tmp = now->next;
        now->next = tmp->next;
        tmp->next = l->next;
        l->next = tmp;
        id++;
    }
}
////////////////////////////////////////////////////////////////////////////////////
void show(Node **head) {
    Node *now = (*head)->next;
    while(now!=NULL) {
        printf("%s ", now->color);
        now = now->next;
    }
    puts("");
}

int n;
char buf[100];
int num1, num2;
Node *head;

int main() {
    head = (Node*)malloc(sizeof(Node)); // create an empty node
    memset(head->color,'\0',sizeof(head->color));
    head->next = NULL;
    scanf("%d",&n);
    while(n--) {
        scanf("%s",buf);
        if(!strcmp(buf,"insert")) {
            scanf("%s%d",buf,&num1);
            insert(&head, buf, num1); // insert <color> <dest>
        }
        else if(!strcmp(buf,"erase1")) {
            scanf("%d",&num1);
            erase1(&head, num1); // erase1 <dest>
        }
        else if(!strcmp(buf,"erase2")) {
            scanf("%s",buf);
            erase2(&head, buf); // erase2 <color>
        }
        else if(!strcmp(buf,"reverse")) {
            scanf("%d%d",&num1,&num2);
            reverse(&head, num1, num2); // reverse <dest1> <dest2>
        }
        else if(!strcmp(buf,"show")) {
            show(&head);
        }
    }
    return 0;
}
```
:::
:::spoiler HW3 - Operation on Sequence <font color="#FD3004">AC</font>

```c=
//HW3 - Operation on Sequence
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
typedef struct _Node
{
    int num;
    struct _Node *l, *r;
}Node;

void insert(Node** head, int val1, int val2);
void erase(Node** head, int val);
void move(Node** head, int val);
void show(Node** head);

char oper[10];
int val1, val2, val;
int listLen = 1;

int main()
{
    int x, n;
    scanf("%d", &x);
    Node *head = (Node*)malloc(sizeof(Node));
    head->num = x;
    head->l = head;
    head->r = head;

    scanf("%d", &n);
    while(n--)
    {
        scanf("%s", oper);
        if(!strcmp("insert", oper)){
            scanf("%d %d", &val1, &val2);
            insert(&head, val1, val2);
        }else if(!strcmp("erase", oper)){
            scanf("%d", &val);
            erase(&head, val);
        }else if(!strcmp("move", oper)){
            scanf("%d", &val);
            move(&head, val);
        }else if(!strcmp("show", oper)){
            show(&head);
        }
    }
    return 0;
}

void insert(Node** head, int val1, int val2)
{
    Node *now = *head;
    while(val2--)
    {
        Node *tmp = (Node*)malloc(sizeof(Node));
        tmp->num = val1;
        tmp->r = now->r;
        now->r->l = tmp;
        now->r = tmp;
        tmp->l = now;
        listLen++;
        //printf("listLen = %d\n", listLen);
    }
}
void erase(Node** head, int val)
{
    Node *now = *head;
    while(val--){
        Node *tar = now->r;
        Node *tmp = tar->r;
        now->r = tmp;
        tmp->l = now;
        free(tar);
        listLen--;
    }
}
void move(Node** head, int val)
{
    Node *now = *head;
    int acc;
    if(val > 0)
        acc = val % listLen;
    else if (val < 0)
        acc = -1 * ((-1 * val) % listLen);
    while(acc != 0){
        if(acc > 0){
            now = now->r;
            acc--;
            //printf("move right 1\n");
        }else if(acc < 0){
            now = now->l;
            acc++;
            //printf("move left 1\n");
        }
    }
    *head = now;
    return;
}
void show(Node** head)
{
    Node* tmp = (*head);
    Node* end = (*head);
    while(tmp != NULL){
        printf("%d", tmp->num);
        tmp = tmp->r;
        if(tmp == end)
        {
            printf("\n");
            break;
        }
        else printf(" ");
    }
}
```
:::
:::spoiler HW3 - Uncle Huang choose Tutor(Easy version) <font color="#FD3004">AC</font>

```c=
//HW3 - Uncle Huang choose Tutor(Easy version)   

#ifndef FUNC_H_INCLUDED
#define FUNC_H_INCLUDED
#include <stdio.h>
#include <stdlib.h>

typedef struct _Node{
    int number;
    struct _Node* next;
}Node;

Node *createList(int n)
{
    Node *now = NULL;
    for(int i = 1; i <= n; i++){
        Node *tmp = (Node *)malloc(sizeof(Node));
        tmp->next = tmp;
        tmp->number = i;
        if( now != NULL ){
            tmp->next = now->next;//make sure point to head
            now->next = tmp;//point to next one
        }
        now = tmp;
    }
    now = now->next;//go back to the first element
    return now;
}

int solveJosephus(Node **head, int step)
{
    int ct = 0;
    Node *now = *head;
    while(now->next != *head){
        now = now->next;
        ct++;
    }
    ct++; //calculate there are how many elements
    now = now->next;
    
    int remain_step = 0;
    for(int i = ct; i > 1; i--){
        remain_step = (step % i);
        //remain step is corresponded to the "current student number"
        
        if( remain_step == 0 ) remain_step += i;
        remain_step --;

        while(1){
            if(remain_step == 0 && now->number != -1) break;
            if(now->number != -1) remain_step --;
            now = now->next;
        }
        now->number = -1;
    }
    
    //find which element is the remain's
    while(1){
        if(now->number != -1) return now->number;
        now = now->next;
    }
}
void freeList(Node* head)
{
    Node *now = head;
    int ct = 0;
    while(now->next != head){
        now = now->next;
        ct++;
    }
    while(ct--)
    {
        Node *tmp = now->next;
        free(now);
        now = tmp;
    }
}
#endif
```
:::
:::spoiler HW3 - typing - (partial judge)  <font color="#FD3004">AC</font>

```c=
//HW3 - Typing
#include<stdio.h>
#include<stdlib.h>
#include<string.h>

#define next ptr_to_next_node
#define prev ptr_to_prev_node
#define ch character

typedef struct _NODE
{
    char character;
    struct _NODE *ptr_to_next_node;
    struct _NODE *ptr_to_prev_node;
} Node;

Node *head, *tail, *cursor;
char buf[10];
int num;
char intype;

void insert(Node **cur, char c);
void deletion(Node **cur);
void backspace(Node **cur);
void go_left(Node **cur, int t);
void go_right(Node **cur, int t);
void go_home(Node **cur);
void go_end(Node **cur);
void show();

int main()
{
    int n;
    scanf("%d",&n);
    head = (Node*)malloc(sizeof(Node));
    head->next = head->prev = head;
    cursor = tail = head;
    while(n--)
    {
        scanf("%s",buf);
        if(!strcmp(buf,"insert"))
        {
            getchar();
            scanf("%c",&intype);
            insert(&cursor, intype); 
        }
        else if(!strcmp(buf,"deletion"))
        {
            deletion(&cursor); 
        }
        else if(!strcmp(buf,"backspace"))
        {
            backspace(&cursor); 
        }
        else if(!strcmp(buf,"go_left"))
        {
            scanf("%d", &num);
            go_left(&cursor, num); 
        }
        else if(!strcmp(buf,"go_right"))
        {
            scanf("%d", &num);
            go_right(&cursor, num); 
        }
        else if(!strcmp(buf,"go_home"))
        {
            go_home(&cursor); 
        }
        else if(!strcmp(buf,"go_end"))
        {
            go_end(&cursor); 
        }
        else if(!strcmp(buf,"show"))
        {
            show();
        }
    }
    return 0;
}
void insert(Node **cur, char c)
{
    Node *np = (Node*)malloc(sizeof(Node));
    np->ch = c;
    np->next = (*cur)->next;
    np->prev = (*cur);

    (*cur)->next->prev = np;
    (*cur)->next = np;

    if((*cur)->next->next == head)
    {
        tail = (*cur)->next;
        //head->prev = tail;
    }
}

void deletion(Node **cur)
{
    if( *cur != tail ) {
        //delete tmp
        Node *tmp = (*cur)->next;
        (*cur)->next = tmp->next;
        tmp->next->prev = (*cur);
        
        //change tail
        if( tmp == tail){
            tail = *cur;
        }
    }
}

void backspace(Node **cur)
{
    if( *cur != head ) {
      (*cur)->next->prev = (*cur)->prev;
      (*cur)->prev->next = (*cur)->next;
      (*cur) = (*cur)->prev;
    }
}

void go_left(Node **cur, int t)
{
    while(t--)
    {
        *cur = (*cur)->prev;
    }
}

void go_right(Node **cur, int t)
{
    while(t--)
    {
        *cur = (*cur)->next;
    }
}

void go_home(Node **cur)
{
    *cur = head;
}

void go_end(Node **cur)
{
    *cur = tail;
}
void show()
{
    if(head == NULL) {
        printf("\n");
        return;
    }
    Node *now = head->ptr_to_next_node;
    while(now != head)
    {
        printf("%c ", now->character);
        now = now->ptr_to_next_node;
    }
    printf("\n");
}
```
:::
:::spoiler HW4 - Crazy give head <font color="#FD3004">AC</font>

```c=
//HW4 - crazy give head
//debug : prefix is "int"; remember "b - plen + 1" may be less than zero!
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

char s[1010], p[1010];
int q, a, b;
int slen, plen;

int main()
{
    while (scanf("%s %s", s, p) != EOF)
    {
        slen = strlen(s);
        plen = strlen(p);
        int prefix[1010] = {0};
        int count = 0;
        for (int i = 0; i < slen - (plen - 1); i++)
        {
            if (strncmp(s + i, p, plen) == 0)
            {
                count++;
            }

            //prefix start at 1
            for (int j = i + 1; j <= i + plen; j++)
            {
                prefix[j] = count;
            }
        }

        //start to calculate the range of the require
        scanf("%d", &q);
        int tmp = 0, answer = 0, r;
        while (q--)
        {
            scanf("%d %d", &a, &b);
            
            if (b - plen + 1 < 0) r = b;
            else r = b - plen + 1;
            
            tmp = prefix[r] - prefix[a - 1];
            
            if (tmp > answer) answer = tmp;
        }
        printf("%d\n", answer);
        memset(prefix, 0, sizeof(int) * 1010);
    }
    return 0;
}
```
:::
:::spoiler HW4 - Uncle Huang Points Tutor <font color="#FD3004">AC</font>

```c=
//HW4 - Uncle Huang Points Tutor
#include <stdio.h>
#include <stdlib.h>
#define LL long long int
LL m;
LL fpw(LL x, LL y);
int main()
{
    LL x, y;
    scanf("%lld %lld %lld", &x, &y, &m);
    x = x % m;
    LL ans = fpw(x, y);
    printf("%lld\n", ans);
    return 0;
}
LL fpw(LL x, LL y)
{
    if (y == 0)
        return 1 % m;
    LL tmp = fpw(x, y / 2);
    if (y % 2 == 0)
        return tmp * tmp % m;
    else
        return (tmp * tmp % m) * x % m; 
        //tmp * tmp need to mod one time(may be too big), then available to * x
}
```
:::
:::spoiler HW4 - Restaurants in Hsinchu <font color="#FD3004">AC</font>

```c=
//12241 - Restaurants in Hsinchu 
#include<stdio.h>
#include<stdlib.h>
#define LL long long int
#define m 1000000007
LL n, ans;
typedef struct{
    LL aa, ab, ba, bb;
}matrix22;
typedef struct{
    LL aa, ba;
}matrix21;

matrix22 tmp, identity, A;
matrix21 final;
void givenum()
{
    A.aa = 1; A.ab = 1;
    A.ba = 1; A.bb = 0;
    identity.aa = 1; identity.ab = 0;
    identity.ba = 0; identity.bb = 1;
}
matrix22 mul(matrix22 x, matrix22 y)
{
    matrix22 tmp;
    tmp.aa = ((x.aa * y.aa) + (x.ab * y.ba)) % m;
    tmp.ab = ((x.aa * y.ab) + (x.ab * y.bb)) % m;
    tmp.ba = ((x.ba * y.aa) + (x.bb * y.ba)) % m;
    tmp.bb = ((x.ba * y.ab) + (x.bb * y.bb)) % m;
    return tmp;
}
matrix21 mul2(matrix22 x) 
    //因為F1 跟 F2 都是 1
    //所以得到的矩陣跟 [1
    //              1]相乘
{
    matrix21 tmp;
    tmp.aa = (x.aa + x.ab) % m;
    tmp.ba = (x.ba + x.bb) % m;
    return tmp;
}
matrix22 fpw(LL x)
{
    if(x == 0) return identity;
    matrix22 tmp = fpw(x / 2);
    tmp = mul(tmp, tmp);
    if(x % 2 == 1) tmp = mul(tmp, A);
    return tmp;
}
int main(void)
{
    givenum();
    
    while( scanf("%lld", &n)  != EOF )
    {
        if(n == 1) ans = 1;
        else if(n == 2) ans = 1;
        else{
            final = mul2( fpw(n - 2) );
            ans = final.aa;
        }
        printf("%lld\n", ans);
        ans = 0;
    }

    return 0;
}
```
:::
:::spoiler lab1 - Count 1s <font color="#FD3004">AC</font>

```c=
//HW4 12678 count 1's
#include<stdio.h>

long int total = 0;
long long int sum[1000010]={0};
void count(long long int);

int main(void)
{
    int a;
    long long int x, y;
    scanf("%d", &a);

    for ( int i = 1; i <= 1000000; i++){
        count(i);
        if ( i == 1 ){
            sum[i] = total;
        }
        else {
            sum[i] = sum[i-1] + total;
        }
        total = 0;
    }

    for ( int i = 0; i < a; i++ ){
        scanf("%lld%lld", &x, &y);
        printf("%lld\n", (sum[y]-sum[x-1]) );
    }

    return 0;
}

void count(long long int num)
{
    if ( num == 0 ){
        return;
    }
    else{
        if( num%10 == 1 ){
            total+=1;
        }
        count(num/10);
    }
}
```
:::
:::spoiler HW5 - Construct tree by inorder and preorder - (partial judge)  <font color="#FD3004">AC</font>

```c=
//HW5 - Construct tree by inorder and preorder
//be careful to reset the index of preorder
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define right ptr_to_right_node
#define left ptr_to_left_node
int n;
typedef struct _NODE
{
    int number;
    struct _NODE *ptr_to_right_node;
    struct _NODE *ptr_to_left_node;
} Node;

int idxSearch(int *arr, int start, int end, int value)
{
    int i;
    for(i = start; i <= end; i++){
        if (arr[i] == value) return i;
    }
    return -1;
}
Node *newNode(int val)
{
    Node *node = (Node*)malloc(sizeof(Node));
    node->number = val;
    node->left = node->right = NULL;
    return node;
}
Node* buildTree(int* Inorder, int* Preorder, int inorder_start, int inorder_end)
{
    static int preorder_idx = 0; // need to remember where we read preorder last time
    if ( inorder_start > inorder_end ) return NULL;

    Node *tree_node = newNode(Preorder[preorder_idx++]);

    if (preorder_idx == n) preorder_idx = 0;
    /*be careful to reset the index of preorder,
      because end with EOF, 
      you will not just have onecase*/

    if( inorder_start == inorder_end ) return tree_node;

    int inorder_idx = idxSearch(Inorder, inorder_start, inorder_end, tree_node->number);

    tree_node->left = buildTree(Inorder, Preorder, inorder_start, inorder_idx - 1);
    tree_node->right = buildTree(Inorder, Preorder, inorder_idx + 1, inorder_end);
    return tree_node; //往最下面的階層找完之後，慢慢往回連結往root的branch
    //這一行可以不寫，不過要寫==的時候
}
void showPostorder(Node* root)
{
    if (root != NULL)
    {
        showPostorder(root->left);
        showPostorder(root->right);
        printf("%d ", root->number);
    }
}
void freeTree(Node *root)
{
    if (root != NULL){
        freeTree(root->left);
        freeTree(root->right);
        free(root);
    }
}


int main(void)
{
    int id = 1;
    while( ~scanf( "%d", &n ) )
    {
        int inorder[100], preorder[100];
        for( int i = 0; i < n; i++ )
            scanf( "%d", &inorder[i] );
        for( int i = 0; i < n; i++ )
            scanf( "%d", &preorder[i] );
        Node *root = buildTree( inorder, preorder, 0, n-1 );
        printf( "testcase%d: ", id++ );
        showPostorder( root );
        printf( "\n" );
        freeTree( root );
        
    }
    return 0;
}
```
:::
:::spoiler HW5 - Species of Knuckles <font color="#FD3004">AC</font>

```c=
//HW5 - Species of Knuckles
//字母的ACSIIcode轉int記得減掉開頭的字元
//注意scanf會讀到enter
#include <stdio.h>

long long int n;
int main(void)
{
    int str[26] = {0};

    scanf("%lld", &n);
    int flag = 0;

    for (long long int i = 0; i < n; i++)
    {
        char c;
        scanf(" %c", &c); // !!!!!!!!!!要空一個不然會讀到"\n"

        int k = (int)(c - 'a'); //!!!!!注意要轉換

        if (str[k] == 0)
            str[k]++;
        else
        {
            flag = 1;
            break;
        }
    }
    if (flag == 1 || n == 1)
        printf("I'm the god of Knuckles!\n");
    else
        printf("Different makes perfect\n");

    return 0;
}
```
:::
:::spoiler HW6 - Storm Area 51 <font color="#FD3004">AC</font>

```c=
//HW6 - Storm Area 51
//using of atoi
//stop being stupid of 條件運算子!!!!!!!!!!!

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
char tmpstring[110];
char preorder[110][4];
int id = 0;
int x, y, z;

typedef struct _NODE
{
    struct _NODE *l, *r; // left and right child
    int type;            // 0:operator, 1:value, 2:variable
    char ch;             // operator or variable
    int val;             // value
} Node;

void build_tree(Node **root);
void show_inorder(Node *root);
int cal(Node *root);

int main()
{
    fgets(tmpstring, 110, stdin);
    int j = 0;
    int currentNUM = 0;
    for(int i = 0; tmpstring[i] != '\0'; i++){
        if (tmpstring[i] == ' '){
            j++;
            currentNUM = 0;
        }
     	else /*小心要加else不然空格會被存進去preorder裡面*/
        preorder[j][currentNUM++] = tmpstring[i];
    }

    Node *tree = (Node *)malloc(sizeof(Node));
    build_tree(&tree);
    show_inorder(tree);
    printf("\n");
    scanf("%d %d %d", &x, &y, &z);
    printf("%d\n", cal(tree));
    return 0;
}
void build_tree (Node** root ){
    (*root) = (Node*)malloc(sizeof(Node));
    char expr[4];
    strcpy(expr, preorder[id]);
    id++;
    if (*expr == '+' || *expr == '-' || *expr == '*' || *expr == '/'){
        (*root)->type = 0;
        (*root)->ch = *expr;
        build_tree( &(*root)->l);
        build_tree( &(*root)->r);
    }
    else if (*expr == 'x' || *expr == 'y' || *expr == 'z'){
        (*root)->type = 2;
        (*root)->ch = *expr;
        (*root)->l = (*root)->r =NULL; 
    }
    else if (*expr >= '0' && *expr <= '9'){
        (*root)->type = 1;
        (*root)->val = atoi(expr);
        (*root)->l = (*root)->r =NULL; 
    }

    return ;
}
void show_inorder( Node*root)
{
    if(root != NULL){
        show_inorder(root->l);
        if(root->type == 0) printf("%c", root->ch);
        else if(root->type == 1) printf("%d", root->val);
        else if(root->type == 2) printf("%c", root->ch);
        show_inorder(root->r);
    }
}
int cal(Node *root)
{
    if (root->type == 0){
        if (root->ch == '+') return cal(root->l) + cal(root->r);
        if (root->ch == '-') return cal(root->l) - cal(root->r);
        if (root->ch == '*') return cal(root->l) * cal(root->r);
        if (root->ch == '/') return cal(root->l) / cal(root->r);
    }
    else if(root->type == 1){
        return root->val;
    }
    else{
        if (root->ch == 'x') return x;
        if (root->ch == 'y') return y;
        if (root->ch == 'z') return z;
    }
}
```
:::
:::spoiler HW6 - Lucky Ghoul Dawn baby <font color="#FD3004">AC</font>

```c=
//HW6 - Lucky Ghoul Dawn baby
//use binary search
//TA use binary tree

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int a[2000010];
int BS(int start, int end, int target);
int main()
{
    int n, q;
    while (scanf("%d %d", &n, &q) != EOF)
    {
        for (int i = 1; i <= n; i++)
        {
            scanf("%d", &a[i]);
        }

        int p; //the input of the index
        while (q--)
        {
            scanf("%d", &p);
            int index = BS(1, n, p);
            if (index == -1)
                printf("Break your bridge!\n");
            else
                printf("%d\n", index);
        }
        memset(a, 0, sizeof(int) * (n + 1));
    }

    return 0;
}

int BS(int start, int end, int target)
{
    int mid = (start + end) / 2;
    if (target == a[mid])
        return mid;

    if (end < start)
        return -1;

    else if (target < a[mid])
        return BS(start, mid - 1, target);

    else if (target > a[mid])
        return BS(mid + 1, end, target);

}
```
:::
:::spoiler HW6 - Lucky Ghoul Dawn baby(another version) <font color="#FD3004">AC</font>

```c=
#include <stdio.h>
#include <string.h>
#include <stdlib.h>

int bridge[2000005];
int n, q;
int BS(int target);

int main()
{
    while (scanf("%d%d", &n, &q) != EOF)
    {
        for (int i = 1; i <= n; i++)
            scanf("%d", &bridge[i]);
        while(q--)
        {
            int a;
            scanf("%d", &a);
            int index = BS(a);
            if (index == 0)
                printf("Break your bridge!\n");
            else
                printf("%d\n", index);
        }
        memset(bridge, 0, sizeof(int) * (n + 1));
    }
    return 0;
}

int BS(int target)
{
    //printf("target = %d\n", target);
    int L = 1, R = n, ans = -1;
    while (L <= R)
    {
        int M = (L + R) / 2;
        //printf("L = %d//M = %d//R = %d\n", L, M, R);
        if (bridge[M] > target)
        {
            R = M - 1;
        }
        else if (bridge[M] == target)
        {
            ans = M;
            break;
        }
        else
        {
            L = M + 1;
        }
    }
    //printf("ans = %d\n", ans);
    if (ans != -1) return ans;
    else return 0;
}
```
:::
:::spoiler HW6 - Heatstroke Bamboo Rats <font color="#FD3004">AC</font>

```c=
//HW7 - Heatstroke Bamboo Rats
//difficult on delete the Node on a binary tree

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX_N 1000006
#define left left_child
#define right right_child

int n, q;
int a[MAX_N];

typedef struct _NODE
{
    int level;
    struct _NODE *left_child, *right_child;
} Node;

void build_tree(Node **now, int *arr, int l, int r);
int query_heatstroke(Node *now, int x);
void eat_rat(Node **root, int x);

int main()
{
    scanf("%d", &n);
    for (int i = 0; i < n; i++)
        scanf("%d", &a[i]);
    Node *root = NULL;
    build_tree(&root, a, 0, n - 1);
    scanf("%d", &q);
    while (q--)
    {
        int x;
        scanf("%d", &x);
        if (query_heatstroke(root, x) != 0)
        {
            puts("We might as well eat it.");
            eat_rat(&root, x);
        }
        else
            puts("No dinner tonight.");
    }
    return 0;
}
void build_tree(Node **now, int *arr, int l, int r)
{
    if (l > r)
        return;

    (*now) = (Node *)malloc(sizeof(Node));
    if (l == r) // reach the bottom, plug in the value
    {
        (*now)->level = arr[l];
        (*now)->left = (*now)->right = NULL;
    }
    else
    {
        int mid = (l + r) / 2;
        (*now)->level = arr[mid];
        build_tree(&((*now)->left), arr, l, mid - 1);
        build_tree(&((*now)->right), arr, mid + 1, r);
    }
}
int query_heatstroke(Node *now, int x)
{
    if (now == NULL)
        return 0;
    else if (now->level == x)
        return 1;
    else if (now->level > x)
        return query_heatstroke(now->left, x);
    else
        return query_heatstroke(now->right, x);
}

// seperate the delete node into : 0 child/ 1 child/ 2 children
void eat_rat(Node **root, int x)
{
    Node **cur = root;
    // set the current to our target x first
    while ((*cur)->level != x)
    {
        if ((*cur)->level > x)
            cur = &((*cur)->left);
        else
            cur = &((*cur)->right);
    }

    // if the target x has 0 child
    if ((*cur)->left == NULL && (*cur)->right == NULL)
    {
        (*cur) = NULL;
    }
    // if target x has 2 child
    // can choose pull up the smallest on right side
    //  or choose pull up the biggest on left side
    else if ((*cur)->left != NULL && (*cur)->right != NULL)
    {
        Node *big = (*cur)->right;
        while (big->left != NULL)
            big = big->left;  // find the smallest index

        int val = big->level; // val is the index to be pull up
        (*cur)->level = val;
        eat_rat(&((*cur)->right), val); // delete the old val position
    }
    // if target x has 1 child
    // just link them up
    else
    {
        if ((*cur)->left != NULL)
            (*cur) = (*cur)->left;
        else
            (*cur) = (*cur)->right;
    }
}

```
:::
:::spoiler HW7 - Construct tree by inorder and postorder <font color="#FD3004">AC</font>

```c=
//HW7 - Construct tree by inorder and postorder

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define right ptr_to_right_node
#define left ptr_to_left_node
int n, post_now, inorder[100], postorder[100];;
typedef struct _NODE
{
    int number;
    struct _NODE *ptr_to_right_node;
    struct _NODE *ptr_to_left_node;
} Node;

int idxSearch(int start, int end, int value)
{
    int i;
    for (i = start; i <= end; i++)
    {
        if (inorder[i] == value)
            return i;
    }
    return -1;
}
Node *newNode(int val)
{
    Node *node = (Node *)malloc(sizeof(Node));
    node->number = val;
    node->left = node->right = NULL;
    return node;
}
Node *buildTree(int inorder_start, int inorder_end)
{
    if (inorder_start > inorder_end) //範圍不符合了 return NULL
        return NULL;
    
    Node *tree_node = newNode(postorder[post_now--]); //new完之後先把now改成下一個post的位置方便下一個迴圈用

    if (inorder_start == inorder_end) return tree_node; //這一行可以不寫，不過可以少進兩次buildtree
   
    int inorder_idx = idxSearch(inorder_start, inorder_end, tree_node->number); //找post的值在inorder的那一個位置
    
    tree_node->right = buildTree(inorder_idx + 1, inorder_end); //in+post建立tree要從tree->right開始建立
    tree_node->left = buildTree(inorder_start, inorder_idx - 1);

    return tree_node; //往最下面的階層找完之後，慢慢往回連結往root的branch
    //這一行可以不寫，不過要寫==的時候
}
void showPreorder(Node *root)
{
    if (root != NULL)
    {
        printf("%d ", root->number);
        showPreorder(root->left);
        showPreorder(root->right);
    }
}
void freeTree(Node *root)
{
    if (root != NULL)
    {
        freeTree(root->left);
        freeTree(root->right);
        free(root);
    }
}

int main(void)
{
    int id = 1;
    while (~scanf("%d", &n))
    {
        
        for (int i = 0; i < n; i++)
            scanf("%d", &inorder[i]);
        for (int i = 0; i < n; i++)
            scanf("%d", &postorder[i]);
        
        //設定全域變數，從postorder的最後一個值開始建立樹
        post_now = n - 1; 
        
        Node *root = buildTree(0, n - 1);

        printf("testcase%d: ", id++);

        showPreorder(root);
        printf("\n");
        freeTree(root);
        memset(inorder, 0, 100);
        memset(postorder, 0, 100);
    }
    return 0;
}
```
:::
:::spoiler HW7 - Thanos' Dilemma <font color="#FD3004">AC</font>

```c=
#include<stdio.h>
#include<stdlib.h>

#define LL long long int
LL t, x, ans, m = 1000000007;
//3*3matrix
typedef struct{
    LL aa, ab, ac;
    LL ba, bb, bc;
    LL ca, cb, cc;
}matrix;
//3*1matrix
typedef struct{
    LL aa, ba, ca;
}matrix2;

matrix A, All1;
matrix2 final;

void givenum()
{
    A.aa = 1; A.ab = 2; A.ac = 1;
    A.ba = 1; A.bb = 0; A.bc = 0;
    A.ca = 0; A.cb = 1; A.cc = 0;
    All1.aa = 1; All1.ab = 0; All1.ac = 0;
    All1.ba = 0; All1.bb = 1; All1.bc = 0;
    All1.ca = 0; All1.cb = 0; All1.cc = 1;
    return;
}
matrix2 mulp(matrix x)
{
    matrix2 tmp;
    tmp.aa = ((x.aa * 13) + (x.ab * 12) + (x.ac)) % m;
    tmp.ba = ((x.ba * 13) + (x.bb * 12) + (x.bc)) % m;
    tmp.ca = ((x.ca * 13) + (x.cb * 12) + (x.cc)) % m;
    return tmp;
}
matrix mul(matrix x, matrix y)
{
    matrix z;
    z.aa = ((x.aa * y.aa) + (x.ab * y.ba) + (x.ac * y.ca)) % m;
    z.ab = ((x.aa * y.ab) + (x.ab * y.bb) + (x.ac * y.cb)) % m;
    z.ac = ((x.aa * y.ac) + (x.ab * y.bc) + (x.ac * y.cc)) % m;
    z.ba = ((x.ba * y.aa) + (x.bb * y.ba) + (x.bc * y.ca)) % m;
    z.bb = ((x.ba * y.ab) + (x.bb * y.bb) + (x.bc * y.cb)) % m;
    z.bc = ((x.ba * y.ac) + (x.bb * y.bc) + (x.bc * y.cc)) % m;
    z.ca = ((x.ca * y.aa) + (x.cb * y.ba) + (x.cc * y.ca)) % m;
    z.cb = ((x.ca * y.ab) + (x.cb * y.bb) + (x.cc * y.cb)) % m;
    z.cc = ((x.ca * y.ac) + (x.cb * y.bc) + (x.cc * y.cc)) % m;
    return z;
}
matrix fpw(LL y)
{
    if (y == 0) return All1;

    matrix tmp = fpw(y/2);

    tmp = mul(tmp, tmp);
    if (y % 2 == 1) tmp = mul(tmp, A);

    return tmp;
}
int main(void)
{
    givenum();
    scanf("%lld", &t);

    while(t--)
    {
        ans = 0;
        x = 0;
        scanf("%lld", &x);
        if(x == 0) ans = 0;
        else if(x == 1) ans = 1;
        else if(x == 2) ans = 12;
        else if(x == 3) ans = 13;
        else 
        {
            final = mulp( fpw(x - 3) );
            ans = final.aa;
        }
        printf("%lld\n", ans);
    }
    return 0;
}
```
:::
:::spoiler HW7 - Go Down Chicken <font color="#FD3004">AC</font>

```c=
// HW7 - Go Down Chicken
//小心快速冪次方爆掉了
//假如自己設定從1開始， 那助教設定的0～n要記得變1～n+1
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define LL long long int
#define DIV 1000000007
typedef struct
{
    int times; // games size
    int id;    // input sequence
    LL way;   // ways to slove the game
} Node;

Node game[1000010];
int n, q;

LL fpow(int exp);
int compare(const void *x, const void *y);
LL BS(LL x);

int main()
{
    game[0].way = -1; // 避免qsort亂掉
    while (~scanf("%d %d", &n, &q))
    {
        for (int i = 1; i <= n; i++)
        {
            scanf("%d(/`A`)/ ~I__I", &game[i].times);
            game[i].id = i;
            if (game[i].times % 2 == 1)
                game[i].way = 0;
            else
            {
                game[i].way = fpow((game[i].times / 2)); 
            }
        }

        qsort(game, n + 1, sizeof(Node), compare);
        while (q--)
        {
            LL x;
            scanf("%lld", &x);
            LL index = BS(x);
            if (index == -1) printf("Go Down Chicken 404\n");
            else printf("%lld\n", index);
        }
    }

    return 0;
}
LL fpow(int exp)
{
    if(exp == 0) return 1;
    
    LL tmp = fpow(exp / 2);

    tmp = tmp * tmp % DIV;

    if (exp % 2 == 1) tmp = tmp * 2 % DIV;

    return tmp;
}
int compare(const void *x, const void *y)
{
    long long int *p;
    long long int *q;
    //先將x, y轉換成(Node*), 得到->way之後, 再把way所屬的int值轉成地址( 亦即 & )
    p = &(((Node *)x)->way);
    q = &(((Node *)y)->way);
    return (*p - *q);
}
LL BS(LL x)
{
    LL L = 1, R = n + 1, ans = 0;
    while(L < R){
        LL M = (L + R) / 2;
        if (game[M].way >= x){
            ans = M;
            R = M;
        }
        else L = M + 1;
    }
    if (game[ans].way == x) return game[ans].id;
    else return -1;
}
```
:::
:::spoiler HW7 - too many treasures <font color="#FD3004">AC</font>

```c=
//HW7 - too many treasures
#include <stdio.h>
#define LL long long int
int main()
{
    LL n, q;
    scanf("%lld %lld", &n, &q);
    LL a[n + 1];
    a[0] = 0;
    LL tmp;
    for (LL i = 1; i <= n; i++)
    {
        scanf("%lld", &tmp);
        if (tmp > 0)
            a[i] = a[i - 1] + tmp;
        else
            a[i] = a[i - 1];
    }
    LL l, r, m;
    while (q--)
    {
        scanf("%lld %lld %lld", &l, &r, &m);
        printf("%lld\n", a[l + m - 1] - a[l - 1]);
    }
    return 0;
}
```
:::

## *midterm2*
:::spoiler HW8 - Heatstroke Bamboo Rats 2  <font color="#FD3004">AC</font>

```c=
//HW8 - Heatstroke Bamboo Rats 2
//difficult on delete the Node on a binary tree

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX_N 10004
#define left left_child
#define right right_child

int n, q;
int a[MAX_N];
char tmp[100];

typedef struct _NODE
{
    int level;
    struct _NODE *left_child, *right_child;
} Node;

void build_tree(Node **now, int *arr, int l, int r);
int query_heatstroke(Node *now, int x);
void eat_rat(Node **root, int x);
void buy_rat(Node **root, int x);

int main()
{
    scanf("%d", &n);
    for (int i = 0; i < n; i++)
        scanf("%d", &a[i]);
    Node *root = NULL;
    build_tree(&root, a, 0, n - 1);
    scanf("%d", &q);
    while (q--)
    {
        scanf("%s", tmp);
        if (strcmp("heatstroke", tmp) == 0)
        {
            int x;
            scanf("%d", &x);
            if (query_heatstroke(root, x) != 0)
            {
                puts("We might as well eat it.");
                eat_rat(&root, x);
            }
            else
                puts("No dinner tonight.");
        }
        else if (strcmp("buy", tmp) == 0)
        {
            int x;
            scanf("%d", &x);
            buy_rat(&root, x);
        }
    }
    return 0;
}
void build_tree(Node **now, int *arr, int l, int r)
{
    if (l > r)
        return;

    (*now) = (Node *)malloc(sizeof(Node));
    if (l == r) // reach the bottom, plug in the value
    {
        (*now)->level = arr[l];
        (*now)->left = (*now)->right = NULL;
    }
    else
    {
        int mid = (l + r) / 2;
        (*now)->level = arr[mid];
        build_tree(&((*now)->left), arr, l, mid - 1);
        build_tree(&((*now)->right), arr, mid + 1, r);
    }
}
int query_heatstroke(Node *now, int x)
{
    if (now == NULL)
        return 0;
    else if (now->level == x)
        return 1;
    else if (now->level > x)
        return query_heatstroke(now->left, x);
    else
        return query_heatstroke(now->right, x);
}

// seperate the delete node into : 0 child/ 1 child/ 2 children
void eat_rat(Node **root, int x)
{
    Node **cur = root;
    // set the current to our target x first
    while ((*cur)->level != x)
    {
        if ((*cur)->level > x)
            cur = &((*cur)->left);
        else
            cur = &((*cur)->right);
    }

    // if the target x has 0 child
    if ((*cur)->left == NULL && (*cur)->right == NULL)
    {
        (*cur) = NULL;
    }
    // if target x has 2 child
    // can choose pull up the smallest on right side
    //  or choose pull up the biggest on left side
    else if ((*cur)->left != NULL && (*cur)->right != NULL)
    {
        Node *big = (*cur)->right;
        while (big->left != NULL)
            big = big->left; // find the smallest index

        int val = big->level; // val is the index to be pull up
        (*cur)->level = val;
        eat_rat(&((*cur)->right), val); // delete the old val position
    }
    // if target x has 1 child
    // just link them up
    else
    {
        if ((*cur)->left != NULL)
            (*cur) = (*cur)->left;
        else
            (*cur) = (*cur)->right;
    }
}
void buy_rat(Node **root, int x)
{
    Node **now = root;
    while (*now != NULL)
    {
        if ((*now)->level > x)
            now = &((*now)->left);
        else
            now = &((*now)->right);
    }
    
    // 利用雙指針的性質，直接建立Node，就不用透過parent     
    (*now) = (Node *)malloc(sizeof(Node));
    (*now)->level = x;
    (*now)->left = (*now)->right = NULL;
}
```
:::
:::spoiler HW8 - Heatstroke Bamboo Rats 2 （submit type） <font color="#FD3004">AC</font>

```c=
#define left left_child
#define right right_child
void build_tree(Node **now, int *arr, int l, int r)
{
    if (l > r)
        return;

    (*now) = (Node *)malloc(sizeof(Node));
    if (l == r) // reach the bottom, plug in the value
    {
        (*now)->level = arr[l];
        (*now)->left = (*now)->right = NULL;
    }
    else
    {
        int mid = (l + r) / 2;
        (*now)->level = arr[mid];
        build_tree(&((*now)->left), arr, l, mid - 1);
        build_tree(&((*now)->right), arr, mid + 1, r);
    }
}
int query_heatstroke(Node *now, int x)
{
    if (now == NULL)
        return 0;
    else if (now->level == x)
        return 1;
    else if (now->level > x)
        return query_heatstroke(now->left, x);
    else
        return query_heatstroke(now->right, x);
}

// seperate the delete node into : 0 child/ 1 child/ 2 children
void eat_rat(Node **root, int x)
{
    Node **cur = root;
    // set the current to our target x first
    while ((*cur)->level != x)
    {
        if ((*cur)->level > x)
            cur = &((*cur)->left);
        else
            cur = &((*cur)->right);
    }

    // if the target x has 0 child
    if ((*cur)->left == NULL && (*cur)->right == NULL)
    {
        (*cur) = NULL;
    }
    // if target x has 2 child
    // can choose pull up the smallest on right side
    //  or choose pull up the biggest on left side
    else if ((*cur)->left != NULL && (*cur)->right != NULL)
    {
        Node *big = (*cur)->right;
        while (big->left != NULL)
            big = big->left; // find the smallest index

        int val = big->level; // val is the index to be pull up
        (*cur)->level = val;
        eat_rat(&((*cur)->right), val); // delete the old val position
    }
    // if target x has 1 child
    // just link them up
    else
    {
        if ((*cur)->left != NULL)
            (*cur) = (*cur)->left;
        else
            (*cur) = (*cur)->right;
    }
}
void buy_rat(Node **root, int x)
{
    Node **now = root;
    while (*now != NULL)
    {
        if ((*now)->level > x)
            now = &((*now)->left);
        else
            now = &((*now)->right);
    }
    
    // 利用雙指針的性質，直接建立Node，就不用透過parent     
    (*now) = (Node *)malloc(sizeof(Node));
    (*now)->level = x;
    (*now)->left = (*now)->right = NULL;
}
```
:::
:::spoiler HW8 - Hulk's Trouble  <font color="#FD3004">AC</font>

```c=
// HW8 - Hulk's Trouble
#include <stdio.h>
#include <stdlib.h>
#define LL long long int

LL x[100010], upper_bound, lower_bound;
int tmp;

int compare(const void *x, const void *y);
LL upperbound(LL *arr, int len, LL tar);
LL lowerbound(LL *arr, int len, LL tar);

int main()
{
    int n, q;
    scanf("%d", &n);
    for (int i = 0; i < n; i++)
    {
        scanf("%lld", &x[i]);
    }
    qsort(x, n, sizeof(x[0]), compare);

    scanf("%d", &q);
    while (q--)
    {
        scanf("%d", &tmp);
        upper_bound = upperbound(x, n, tmp);
        lower_bound = lowerbound(x, n, tmp);
        printf("%lld\n", upper_bound - lower_bound);
    }

    return 0;
}
int compare(const void *x, const void *y)
{
    LL *p, *q;
    p = ((LL *)x);
    q = ((LL *)y);
    return *p - *q;
}
LL upperbound(LL *arr, int len, LL tar)
{
    int L = 0, R = len, M;
    while (L < R)
    {
        M = (L + R) / 2;
        if (arr[M] > tar)
            R = M;
        else
            L = M + 1;
    }
    return R;
}
LL lowerbound(LL *arr, int len, LL tar)
{
    int L = 0, R = len, M;
    while (L < R)
    {
        M = (L + R) / 2;
        if (arr[M] >= tar)
            R = M;
        else
            L = M + 1;
    }
    return R;
}
```
:::
:::spoiler HW8 - minimum mean of rectangle sum  <font color="#FD3004">AC</font>

```c=
// HW8 - minimum mean of rectangle sum
#include<stdio.h>
#include<stdlib.h>
#define LL long long int
LL smallest, tmp;
int main()
{
    int n, m, elements;
    
    scanf("%d %d", &n, &m);
    elements = n * m;
    while(elements--){
        scanf("%lld", &tmp);
        if (tmp < smallest) smallest = tmp;
    }
    printf("%lld\n", smallest);
    
    return 0;
}
```
:::
:::spoiler HW9 - Break my heart  <font color="#FD3004">AC</font>

```c=
//HW9 - Break my heart
#include <iostream>
#include <set>
using namespace std;
int main()
{
    string in;
    int n;
    set<int> myset;

    cin >> n;
    while (n--)
    {
        cin >> in;
        if (in == "insert")
        {
            int tmp;
            cin >> tmp;
            myset.insert(tmp);
        }
        else if (in == "print")
        {
            int i = 0;
            for (auto it = myset.begin(); it != myset.end(); it++, i++)
            {
                cout << *it;
                if (i + 1 == myset.size())
                    cout << "\n";
                else
                    cout << " ";
            }
        }
        else if (in == "min")
        {
            if (!myset.size())
                ;
            else
            {
                auto it = myset.begin();
                cout << *it << endl;
            }
        }
        else if (in == "range_erase")
        {
            int l, r;
            cin >> l >> r;
            myset.erase(myset.lower_bound(l), myset.upper_bound(r));
        }
        else if (in == "sum")
        {
            int i = 0;
            for (auto it = myset.begin(); it != myset.end(); it++)
            {
                i += *it;
            }
            cout << i << endl;
        }
    }

    return 0;
}
```
:::
:::spoiler HW9 - Thanos' Return_cpp <font color="#FD3004">AC</font>

```c=
#include <iostream>
#include "function.h"
using namespace std;

int r, c;
long long times;
char op;
Matrix M, ans;

Matrix fast_add(Matrix mat, long long t) {
	Matrix rtn(mat.getrow(), mat.getcol());
	for(; t; t >>= 1) {
		if(t&1) rtn = rtn + mat;
		mat = mat + mat;
	}
	return rtn;
}

Matrix fast_mul(Matrix mat, long long t) {
	Matrix rtn(mat.getrow(), mat.getcol());
	for(int i = 0; i < mat.getrow(); i++)
		rtn[i][i] = 1;
	for(; t; t >>= 1) {
		if(t&1) rtn = rtn * mat;
		mat = mat * mat;
	}
	return rtn;
}

int main() {
	cin >> r >> c >> times >> op;
	M = Matrix(r, c);
	for(int i=0, tmp;i<r;i++) for(int j=0;j<c;j++) {
		cin >> tmp;
		M[i][j] = tmp % MOD;
	}
	switch (op) {
		case '+':
			ans = fast_add(M, times);
			break;
		case '*':
			ans = fast_mul(M, times);
			break;
	}
	ans.print();
	return 0;
}

```
:::
:::spoiler HW9 - Thanos' Return_h <font color="#FD3004">AC</font>

```c=
#include <iostream>
#include <cstring>
#include <iomanip>
const int MAX_N = 102;
const int MOD = 10007;

class Matrix
{
public:
	Matrix()
	{
		row = col = 0;
		memset(mat, 0, sizeof(mat));
	}
	// TODO
	Matrix(int r, int c);
	const int &getrow()
	{
		return row;
	}
	const int &getcol()
	{
		return col;
	}
	// TODO
	int *operator[](const int &x);
	const int *operator[](const int &x) const
	{
		return mat[x];
	}
	// TODO
	Matrix operator+(const Matrix &x) const;
	// TODO: be aware that this function is declared with friend!!!
	friend Matrix operator*(const Matrix &x, const Matrix &y);
	void print()
	{
		for (int i = 0; i < row; i++)
		{
			if (i == 0)
				std::cout << "/";
			else if (i == row - 1)
				std::cout << "\\";
			else
				std::cout << "|";
			for (int j = 0; j < col; j++)
			{
				std::cout << std::right << std::setw(8) << mat[i][j];
			}
			if (i == 0)
				std::cout << " \\\n";
			else if (i == row - 1)
				std::cout << " /\n";
			else
				std::cout << " |\n";
		}
	}

private:
	int mat[MAX_N][MAX_N];
	int row, col;
};
////// submit the below function
/*
const int MOD = 10007;
*/
Matrix::Matrix(int r, int c)
{
	row = r;
	col = c;
	memset(mat, 0, sizeof(mat));
}
int *Matrix::operator[](const int &x)
{
	return mat[x];
}

Matrix Matrix::operator+(const Matrix &x) const
{
	Matrix res(row, col);
	for (int i = 0; i < row; i++)
		for (int j = 0; j < col; j++)
			res[i][j] = ((mat[i][j] + x[i][j]) % MOD + MOD) % MOD;
	return res;
}

// Cus it is a friend function, doesn't below to the Class matrix
// So we don't need to write Matrix::
Matrix operator*(const Matrix &x, const Matrix &y)
{
	Matrix res(x.row, y.col);
	for (int i = 0; i < x.row; i++)
		for (int j = 0; j < y.col; j++)
			for (int k = 0; k < x.col; k++)
			{
				res[i][j] += ((x[i][k] * y[k][j]) % MOD + MOD) % MOD;
				res[i][j] = (res[i][j] % MOD + MOD) % MOD;
			}
	return res;
}

```
:::
:::spoiler HW9 - cat-toast crisis  <font color="#FD3004">AC</font>

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

int n, r; // for number of point and the distance
int x[1010], y[1010], visited[1010]; // for point matrix and visited
int single, team;// for the number of the result

int distance(int A, int B);
int dfs(int now, int parent);

int main()
{
    scanf("%d %d", &n, &r);
    for (int i = 0; i < n; i++)
    {
        scanf("%d %d", &x[i], &y[i]);
    }
    for (int i = 0; i < n; i++)
    {
        if (visited[i] == 0)
        {
            if (dfs(i, -1))
                team++;
            else
                single++;
        }
    }
    printf("%d %d\n", single, team);
    return 0;
}
int dfs(int now, int parent)
{
    int group = 0;
    visited[now] = 1;
    for (int i = 0; i < n; i++)
    {
        if (i == now)
            continue;
        else if (i == parent)
            continue;
        else if (visited[i] == 1)
            continue;
        else if (distance(now, i))// two points are in the distance of r
        {
            dfs(i, now); // do DFS
            group++;
        }
    }
    if (group != 0)
        return 1;
    else
        return 0;
}
int distance(int A, int B)
{
    if ((x[A] - x[B]) * (x[A] - x[B]) + (y[A] - y[B]) * (y[A] - y[B]) <= r * r)
        return 1;
    else
        return 0;
}
```
:::
:::spoiler BONUS - 1 - the answer to life, the universe, and everything  <font color="#FD3004">AC</font>

```c=
#include<stdio.h>
#include<stdlib.h>
#define LL long long int
LL G[100];
LL F[100];
LL input;
int main()
{
    G[0] = 1;
    G[1] = 0;
    for(int i = 2; i < 89; i++){
        G[i] = G[i - 1] + G[i - 2];
        //printf("%lld\n", G[i]);
    }

    while (~scanf("%lld", &input)){
        LL min = 1000000000000000010;
        LL tmp;
        if (input == 0 || input == 1) printf("0\n");
        else {
            for(int i = 1; i < 88; i++){
                if ((input - G[i]) % G[i + 1] == 0){
                    tmp = ( (input - G[i]) / G[i + 1] );
                    if (tmp < min) min = tmp;
                }
            }
            printf("%lld\n", min);

        }
    }
    return 0;
}

```
:::
:::spoiler HW10 - Big enough_cpp <font color="#FD3004">AC</font>

```c=
#include "12469.h"
#include<iostream>
#include<string> 
using namespace std; 
int main(){
	BigInt a, b;
    while( cin >> a >> b ){
		cout << (a+b) << '\n';
		cout << (a-b) << '\n';
	}
    return 0;
}

```
:::
:::spoiler HW10 - Big enough_h  <font color="#FD3004">AC</font>

```c=
#include <iostream>
#include <algorithm>
#include <string>
using namespace std;
#define MAX_N 1000
#define MAX_Bit 5
#define MAX 100000
class BigInt
{
public:
    long long operator[](int i) const { return m[i]; }
    long long &operator[](int i) { return m[i]; }
    BigInt()
    {
        l = 1, m[0] = 0;
        sign = 1;
    }
    friend istream &operator>>(istream &, BigInt &);
    friend ostream &operator<<(ostream &, BigInt);
    BigInt operator+(const BigInt &y);
    BigInt operator-(const BigInt &y);

private:
    long long m[MAX_N];
    int l; //長度
    int sign;
};
istream &operator>>(istream &in, BigInt &b)
{
    string ch;
    in >> ch;
    if (ch[0] == '-')
    {
        b.sign = 0;
        ch = ch.substr(1); // to move away the '-'
    }
    else
        b.sign = 1;

    reverse(ch.begin(), ch.end());
    int id = 0;
    for (int i = 0; i < ch.length(); i += MAX_Bit)
    {
        string sub = ch.substr(i, 5);
        reverse(sub.begin(), sub.end());
        b.m[id++] = stoi(sub); // turn string to int
        // cout << "cin = " << b.m[id - 1] << endl;
    }
    b.l = id;
    return in;
}
ostream &operator<<(ostream &out, BigInt b)
{
    if (!b.sign)
        cout << "-";
    /*if (b.l == 0) {
        out << "0";
        return out;
    }*/
    cout << b.m[b.l - 1];
    for (int i = b.l - 2; i >= 0; i--)
    {
        out.width(MAX_Bit);
        out.fill('0');
        out << b[i];
    }
    return out;
}
BigInt BigInt::operator+(const BigInt &y)
{
    BigInt x(*this);
    int XSIGN = 1, YSIGN = 1;
    if (!x.sign)
        XSIGN = -1;
    if (!y.sign)
        YSIGN = -1;
    int i;
    long long h = 0;
    for (i = 0; i < x.l || i < y.l || h; i++)
    {
        if (i < x.l && i < y.l)
            h += x[i] * XSIGN + y[i] * YSIGN;
        else if (i < x.l)
            h += XSIGN * x[i];
        else if (i < y.l)
        {
            h += YSIGN * y[i];
            // cout << "YSIGN = " << YSIGN << "y[i] = " << y[i] << endl;
            // cout <<"your 88\n";
        }
        x.m[i] = h % MAX;
        h /= MAX;
        //cout << "for loop minus x.m[i] = " << x.m[i] << endl;
    }
    x.l = i;

    // define x.sign
    if (x.m[x.l - 1] < 0)
        x.sign = 0;
    else
        x.sign = 1;

    // deal with the 進位
    if (!x.sign && x.l > 1)
    {
        for (int i = 0; i <= x.l - 1 - 1; i++)
        {
            if (x.m[i] > 0)
            {
                x.m[i] -= MAX;
                x.m[i + 1] += 1;
            }
            // cout << "x[i] = " << x[i] << endl;
        }
    }
    else if (x.sign && x.l > 1)
    {
        // cout << " i am positive";
        for (int i = 0; i <= x.l - 1 - 1; i++)
        {
            if (x.m[i] < 0)
            {
                // cout << "x.m[i] = " << x.m[i] << " MAX =" << MAX << endl;
                x.m[i] += MAX; 
                x.m[i + 1] -= 1;
            }
        }
    }
    for (int i = 0; i < x.l; i++)
    {
        if (x.m[i] < 0)
            x.m[i] *= -1;
        // cout << "after turn posx[i] = " << x[i] << endl;
    }
    // deal with start number is 0
    int tmpi = x.l;
    while (x.m[tmpi - 1] == 0)
    {
        x.l -= 1;
        tmpi--;
    }
    if (x.l == 1 && x.m[0] == 0)
    {
        x.sign = 1;
    }
    return x;
}
BigInt BigInt::operator-(const BigInt &y)
{
    BigInt x(*this);
    int XSIGN = 1, YSIGN = 1;
    if (!x.sign)
        XSIGN = -1;
    if (!y.sign)
        YSIGN = -1;
    int i;
    long long h = 0;
    for (i = 0; i < x.l || i < y.l || h; i++)
    {
        if (i < x.l && i < y.l)
            h += x[i] * XSIGN - y[i] * YSIGN;
        else if (i < x.l)
            h += XSIGN * x[i];
        else if (i < y.l)
        {
            h += 0 - YSIGN * y[i];
            //cout << "YSIGN = " << YSIGN << "y[i] = " << y[i] << endl;
            //cout <<"your 88\n";
        }
        x.m[i] = h % MAX;
        h /= MAX;
        //cout << "for loop minus x.m[i] = " << x.m[i] << endl;
    }
    x.l = i;

    // define x.sign
    if (x.m[x.l - 1] < 0)
        x.sign = 0;
    else
        x.sign = 1;

    // deal with the 進位
    if (!x.sign && x.l > 1)
    {
        for (int i = 0; i <= x.l - 1 - 1; i++)
        {
            if (x.m[i] > 0)
            {
                x.m[i] -= MAX;
                x.m[i + 1] += 1;
            }
            //cout << "x[i] = " << x[i] << endl;
        }
    }
    else if (x.sign && x.l > 1)
    {
        //cout << " i am positive";
        for (int i = 0; i <= x.l - 1 - 1; i++)
        {
            if (x.m[i] < 0)
            {
                //cout << "x.m[i] = " << x.m[i] << " MAX =" << MAX << endl;
                x.m[i] += MAX;
                x.m[i + 1] -= 1;
            }
        }
    }
    for (int i = 0; i < x.l; i++)
    {
        if (x.m[i] < 0)
            x.m[i] *= -1;
        //cout << "after turn posx[i] = " << x[i] << endl;
    }
    // deal with start number is 0
    int tmpi = x.l;
    while (x.m[tmpi - 1] == 0)
    {
        x.l -= 1;
        tmpi--;
    }
    if (x.l == 1 && x.m[0] == 0)
    {
        x.sign = 1;
    }
    return x;
}
```
:::
:::spoiler HW10 - Big enough（submit type）  <font color="#FD3004">AC</font>

```c=
/*#include <iostream>
#include <algorithm>
#include <string>
using namespace std;
*/
#define MAX_N 1000
#define MAX_Bit 5
#define MAX 100000

istream &operator>>(istream &in, BigInt &b)
{
    string ch;
    in >> ch;
    if (ch[0] == '-')
    {
        b.sign = 0;
        ch = ch.substr(1); // to move away the '-'
    }
    else
        b.sign = 1;

    reverse(ch.begin(), ch.end());
    int id = 0;
    for (int i = 0; i < ch.length(); i += MAX_Bit)
    {
        string sub = ch.substr(i, 5);
        reverse(sub.begin(), sub.end());
        b.m[id++] = stoi(sub); // turn string to int
        // cout << "cin = " << b.m[id - 1] << endl;
    }
    b.l = id;
    return in;
}
ostream &operator<<(ostream &out, BigInt b)
{
    if (!b.sign)
        cout << "-";
    /*if (b.l == 0) {
        out << "0";
        return out;
    }*/
    cout << b.m[b.l - 1];
    for (int i = b.l - 2; i >= 0; i--)
    {
        out.width(MAX_Bit);
        out.fill('0');
        out << b[i];
    }
    return out;
}
BigInt BigInt::operator+(const BigInt &y)
{
    BigInt x(*this);
    int XSIGN = 1, YSIGN = 1;
    if (!x.sign)
        XSIGN = -1;
    if (!y.sign)
        YSIGN = -1;
    int i;
    long long h = 0;
    for (i = 0; i < x.l || i < y.l || h; i++)
    {
        if (i < x.l && i < y.l)
            h += x[i] * XSIGN + y[i] * YSIGN;
        else if (i < x.l)
            h += XSIGN * x[i];
        else if (i < y.l)
        {
            h += YSIGN * y[i];
            // cout << "YSIGN = " << YSIGN << "y[i] = " << y[i] << endl;
            // cout <<"your 88\n";
        }
        x.m[i] = h % MAX;
        h /= MAX;
        //cout << "for loop minus x.m[i] = " << x.m[i] << endl;
    }
    x.l = i;

    // define x.sign
    if (x.m[x.l - 1] < 0)
        x.sign = 0;
    else
        x.sign = 1;

    // deal with the 進位
    if (!x.sign && x.l > 1)
    {
        for (int i = 0; i <= x.l - 1 - 1; i++)
        {
            if (x.m[i] > 0)
            {
                x.m[i] -= MAX;
                x.m[i + 1] += 1;
            }
            // cout << "x[i] = " << x[i] << endl;
        }
    }
    else if (x.sign && x.l > 1)
    {
        // cout << " i am positive";
        for (int i = 0; i <= x.l - 1 - 1; i++)
        {
            if (x.m[i] < 0)
            {
                // cout << "x.m[i] = " << x.m[i] << " MAX =" << MAX << endl;
                x.m[i] += MAX; 
                x.m[i + 1] -= 1;
            }
        }
    }
    for (int i = 0; i < x.l; i++)
    {
        if (x.m[i] < 0)
            x.m[i] *= -1;
        // cout << "after turn posx[i] = " << x[i] << endl;
    }
    // deal with start number is 0
    int tmpi = x.l;
    while (x.m[tmpi - 1] == 0)
    {
        x.l -= 1;
        tmpi--;
    }
    if (x.l == 1 && x.m[0] == 0)
    {
        x.sign = 1;
    }
    return x;
}
BigInt BigInt::operator-(const BigInt &y)
{
    BigInt x(*this);
    int XSIGN = 1, YSIGN = 1;
    if (!x.sign)
        XSIGN = -1;
    if (!y.sign)
        YSIGN = -1;
    int i;
    long long h = 0;
    for (i = 0; i < x.l || i < y.l || h; i++)
    {
        if (i < x.l && i < y.l)
            h += x[i] * XSIGN - y[i] * YSIGN;
        else if (i < x.l)
            h += XSIGN * x[i];
        else if (i < y.l)
        {
            h += 0 - YSIGN * y[i];
            //cout << "YSIGN = " << YSIGN << "y[i] = " << y[i] << endl;
            //cout <<"your 88\n";
        }
        x.m[i] = h % MAX;
        h /= MAX;
        //cout << "for loop minus x.m[i] = " << x.m[i] << endl;
    }
    x.l = i;

    // define x.sign
    if (x.m[x.l - 1] < 0)
        x.sign = 0;
    else
        x.sign = 1;

    // deal with the 進位
    if (!x.sign && x.l > 1)
    {
        for (int i = 0; i <= x.l - 1 - 1; i++)
        {
            if (x.m[i] > 0)
            {
                x.m[i] -= MAX;
                x.m[i + 1] += 1;
            }
            //cout << "x[i] = " << x[i] << endl;
        }
    }
    else if (x.sign && x.l > 1)
    {
        //cout << " i am positive";
        for (int i = 0; i <= x.l - 1 - 1; i++)
        {
            if (x.m[i] < 0)
            {
                //cout << "x.m[i] = " << x.m[i] << " MAX =" << MAX << endl;
                x.m[i] += MAX;
                x.m[i + 1] -= 1;
            }
        }
    }
    for (int i = 0; i < x.l; i++)
    {
        if (x.m[i] < 0)
            x.m[i] *= -1;
        //cout << "after turn posx[i] = " << x[i] << endl;
    }
    // deal with start number is 0
    int tmpi = x.l;
    while (x.m[tmpi - 1] == 0)
    {
        x.l -= 1;
        tmpi--;
    }
    if (x.l == 1 && x.m[0] == 0)
    {
        x.sign = 1;
    }
    return x;
}
```
:::

:::spoiler HW10 - A lot of sandwiches <font color="#FD3004">AC</font>

```c=
#include <iostream>
// abstract class
class Food
{
public:
    enum class Type
    {
        IdiotSandwich,
        NormalSandwich
    };
    friend std::ostream &operator<<(std::ostream &out, Food &d)
    {
        d.print(out);
        return out;
    }
    Type getType() { return type; }
    void setType(Type x) { type = x; }
    virtual ~Food() {}

private:
    virtual void print(std::ostream &out) {}
    Type type;
};

class IdiotSandwich : public Food
{
public:
    IdiotSandwich(int x)
    {
        setType(Type::IdiotSandwich);
        setINT(x);
    }
    void setINT(int x) { intelligence = x; }
    int getINT() { return intelligence; }

private:
    // TODO
    void print(std::ostream &out);
    int intelligence;
};

class NormalSandwich : public Food
{
public:
    NormalSandwich(std::string x)
    {
        setType(Type::NormalSandwich);
        setName(x);
    }
    void setName(std::string x) { name = x; }
    std::string getName() { return name; }

private:
    // TODO
    void print(std::ostream &out);
    std::string name;
};

class Dish
{
public:
    Dish() { food = nullptr; }
    // TODO
    ~Dish();
    Food &getFood() { return (*food); }
    const Food &getFood() const { return (*food); }
    // TODO
    friend std::istream &operator>>(std::istream &in, Dish &d);
    Food *food;
};

int n;
Dish dish;

int main()
{
    std::cin >> n;
    while (n--)
    {
        std::cin >> dish;
        std::cout << dish.getFood() << std::endl;
    }
    return 0;
}
////////submit below function////////
Dish::~Dish()
{
    delete food;
}
void IdiotSandwich::print(std::ostream &out)
{
    out << "An idiot sandwich with intelligence level " << IdiotSandwich::getINT() << " only.";
}
void NormalSandwich::print(std::ostream &out)
{
    out << NormalSandwich::getName() << ". Masterpiece of sandwiches.";
}
std::istream &operator>>(std::istream &in, Dish &d)
{
    std::string str;
    int t1;
    in >> str;
    if (d.food != nullptr)
    {
        delete d.food;
        d.food = nullptr;
    }
    if (str == "Ramsay")
    {
        in >> t1;
        d.food = new IdiotSandwich(t1);
    }
    else
        d.food = new NormalSandwich(str);
    return in;
}
////////submit the above function////////
```
:::
:::spoiler HW10 - Endgame <font color="#FD3004">AC</font>

```c=
#include <iostream>
#include <queue>
#include <utility>
using namespace std;

typedef pair<int, int> PAIR;

queue<PAIR> q;
PAIR tmpdest, tmpdist;
int n, m;
int toBeDestroyed = 0;
char map[1001][1001];
int toX[] = {1, -1, 0, 0};
int toY[] = {0, 0, 1, -1};
int bfs();
int main()
{
    cin >> n >> m;

    for(int i = 0; i < n; i ++){
        for (int j = 0; j < m; j++){
            cin >> map[i][j];

            if (map[i][j] == 'I'){
                tmpdest.first = i;
                tmpdest.second = j;
                q.push (tmpdest);
                //cout << q.front().first << q.front().second << endl;
                tmpdist.first = 0;
                tmpdist.second = 0;
                q.push (tmpdist);
                //cout << q.back().first << q.back().second << endl;
            }
            if(map[i][j] == 'T'){
                toBeDestroyed += 1;
            }
        }
    }
    //cout << "T = " << toBeDestroyed << endl; 
    cout << bfs() << endl;

    return 0;
}
int bfs()
{
    while(!q.empty()){
        PAIR now = q.front();
        //cout <<"now = ("<< now.first << " " << now.second << ")" << endl;
        q.pop();
        int dist = q.front().first;
        // cout << "dist = " << dist << endl;
        q.pop();

        //////////////////////////////////////////////////////
        // if (map[now.first][now.second] == 'C') continue; //
        //////////////////////////////////////////////////////
        // why we cannot add the above line ?               //
        // we make (O+x, O+y) be 'C' below,                 //
        //    then it will run the loop again               //
        //    but we want to do (O+x, O+y)'s four position  //
        //    so if we ignore the (O+x, O+y) with 'C'       //
        //    it will stop doing forever !!!!!!             //
        //////////////////////////////////////////////////////

        for(int i = 0; i < 4; i++){
            if (now.first + toX[i] >= m || now.second + toY[i] >= n || now.first + toX[i] < 0 || now.second + toY[i] < 0)
                continue;
            else if(map[now.first + toX[i]][now.second + toY[i]] == 'C')
                continue;
            else if(map[now.first + toX[i]][now.second + toY[i]] == 'T'){
                toBeDestroyed--;
                if (!toBeDestroyed) return dist + 1;
            }

            // we already use this position, so we define to 'C' to
            //easy to do the remaining step
            map[now.first + toX[i]][now.second + toY[i]] = 'C';
            
            //pushing the new position and the distance
            tmpdest.first = now.first + toX[i];
            tmpdest.second = now.second + toY[i];
            q.push (tmpdest);
            tmpdist.first = dist + 1;
            tmpdist.second = 0;
            q.push (tmpdist);
        }
    }
    return -1;
}
```
:::
:::spoiler HW11 - So beautiful <font color="#FD3004">AC</font>

```c=
#include <iostream>
#include <map>
#include <vector>
using namespace std;

map< int, map< char, vector<string> > > bucket;
pair<int, char> vowel(string str);

int main ()
{
    int n;
    cin >> n;
    string lyric;
    pair <int, char> key;
    while (n--){
        cin >> lyric;
        key = vowel(lyric);
        bucket[key.first][key.second].push_back(lyric);
    }
    int comp = 0, uncomp = 0, single = 0;
    for(auto i : bucket){
        single = 0;
        for(auto j : i.second){
            comp += j.second.size() / 2;
            single += j.second.size() % 2;
        }
        uncomp += single / 2;
    }
    int ANS = 0;
    if (comp >= uncomp){
        ANS += uncomp;
        ANS += (comp - uncomp) / 2;
    }
    else 
        ANS += comp;
        
    cout << ANS << endl;

    return 0;
}
pair<int, char> vowel(string str)
{
    pair<int, char> ans;
    int vow = 0;
    for(auto &i : str){
        if (i == 'a' || i == 'e' || i == 'i' || i == 'o' || i == 'u'){
            vow++;
            ans.second = i;
        }
    }
    ans.first = vow;
    return ans;
}
```
:::
:::spoiler HW11 - The power of vector <font color="#FD3004">AC</font>

```c=
#include <iostream>
#include <set>
#include <vector>
#include <string>
using namespace std;

vector<int> V;
set<pair<int, int>> record;

int NUMBER = 0;
pair<int, int> last_record;

int main ()
{
    int n;
    string input;
    int element;

    cin >> n;
    while(n--){
        cin >> input;
        if (input == "push_back"){
            cin >> element;
            V.push_back(element);
            /*last_record.first = element;
            last_record.second = ++NUMBER;*/
            record.insert({element, NUMBER + 1});
            NUMBER++;
        }
        else if(input == "pop_back" && !V.empty()){
            record.erase({V[NUMBER - 1], NUMBER});
            V.pop_back();
            NUMBER--;
        }
        else if(input == "find"){
            cin >> element;
            if ( element <= NUMBER ){
                cout << V[element - 1] << endl;
            }
        }
        else if(input == "min" && !V.empty()){
            cout << record.begin()->first << " " << record.begin()->second << endl;
        }
        else if(input == "max" && !V.empty()){
            cout << record.rbegin()->first << " " << record.rbegin()->second << endl;
        }
    }
    return 0;
}
```
:::
:::spoiler HW11 - Salary thief <font color="#FD3004">AC</font>

```c=
#include <iostream>
#include <string.h>
using namespace std;
#define MOD 1000000007
#define LL long long int
int main ()
{
    int n, x;
    cin >> n;
    while(n--){
        cin >> x;
        string str;
        cin >> str;
        int id = 0;
        for (id = 0; id < x, str.length() <= x; id++){
            //we just have to calculate the actual element below X number, 
            //after that we can just times the length to get the answer
            string right = str.substr(id + 1);
            for(int i = 0; i < str[id] - '0' - 1; i++){
                str += right;
            }
        }
        LL len = str.length();
            //carry on the "id"
        for(int i = id; i < x; i++){
            LL times = (str[i] - '0' - 1) % MOD;
            LL length_to_times = (len - (i + 1)) % MOD;
            LL temp = ( times * length_to_times + MOD) % MOD;
            len = ((len % MOD + temp % MOD) + MOD) % MOD;
            // the plus MOD above is to avoid len < 0
        }
        cout << len << endl;
    }
    return 0;
}
```
:::
:::spoiler HW11 - Nyan Cat Crisis <font color="#FD3004">AC</font>

```c=
#include <iostream>
#include <cstring>
#include <string>
using namespace std;

pair<int, int> N[500];
int visited[500];
int n, r, k;
int groupsize = 0;

int distance(int A, int B);
void dfs(int now, int parent);

int main()
{
    int t;
    cin >>t;
    while(t--)
    {
        int big = 0, small = 0;
        cin >> n >> r >> k;
        for(int i = 0; i < n; i++){
            cin >> N[i].first >> N[i].second;
        }
        for(int i = 0; i < n; i++){
            if (!visited[i]){
                groupsize = 1;
                dfs(i, -1);
                if (groupsize >= k){
                    big++;
                }
                else {
                    small++;
                }
            }
        }
        cout << small << " " << big << endl;
        memset(visited, 0, sizeof(int) * 500);
    }

    return 0;
}
int distance(int A, int B)
{
    if ((N[A].first - N[B].first) * (N[A].first - N[B].first) + (N[A].second - N[B].second) * (N[A].second - N[B].second) <= r * r)
        return 1;
    else return 0; 
}
void dfs(int now, int parent)
{
    visited[now] = 1;
    for(int i = 0; i < n; i++){
        if (i == now || i == parent || visited[i]) continue;
        else if (distance(i, now)){
            dfs(i, now);
            groupsize++;
        }
    }
}
```
:::
:::spoiler BONUS - 2 - Fix the Bug <font color="#FD3004">AC</font>

```c=
#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

long long int a[200005];
long long int rem[15][200005];

int countDigit(int x) {
    int res = 0;
    while (x != 0) {
        x /= 10;
        res++;
    }
    return res;
}

int BSleft(long long int *arr, int start, int end, int target) {
    int mid = (start + end) / 2;
    if (start == end - 1) {
        if (arr[start] == target) {
            return start;
        } else if (arr[end] == target) {
            return end;
        } else {
            return -1;
        }
    }
    if (target <= arr[mid]) {
        return BSleft(arr, start, mid, target);
    } else {
        return BSleft(arr, mid, end, target);
    }
}

int BSright(long long int *arr, int start, int end, int target) {
    int mid = (start + end) / 2;
    if (start == end - 1) {
        if (arr[end] == target) {
            return end;
        } else if (arr[start] == target) {
            return start;
        } else {
            return -1;
        }
    }
    if (target >= arr[mid]) {
        return BSright(arr, mid, end, target);
    } else {
        return BSright(arr, start, mid, target);
    }
}

int main() {
    long long int n, k;
    while (cin >> n >> k) {
        memset(a, 0, sizeof(a));
        memset(rem, 0, sizeof(rem));
        long long int res = 0;
        for (int i = 0; i < n; ++i) {
            cin >> a[i];
        }
        if (n == 1) {
            cout << 0 << endl;
            continue;
        }
        for (long long int i = 0, mul = 1; i <= 10; ++i, mul *= 10) {
            for (long long int j = 0; j < n; ++j) {
                rem[i][j] = ((a[j] % k) * (mul % k)) % k;
            }
            sort(rem[i], rem[i] + n);
        }
        for (int i = 0; i < n; ++i) {
            int digitNum = countDigit(a[i]);
            int toFind = (k - a[i] % k) % k;
            int l = BSleft(rem[digitNum], 0, n - 1, toFind);
            int r = BSright(rem[digitNum], 0, n - 1, toFind);
            if (l != -1 && r != -1) {
                res += (r - l + 1);
                long long int temp = a[i];
                for (long long int j = 0; j < digitNum; ++j) {
                    temp *= 10;
                }
                if ((temp + a[i]) % k == 0) {
                    res--;
                }
            }
        }
        cout << res << endl;
    }
    return 0;
}
```
:::
## *final*
:::spoiler HW12 - People nowadays <font color="#FD3004">AC</font>

```c=
#include <iostream>
#include <utility>
#include <set>
using namespace std;
set< pair<int, string> > person;
int main()
{
	int n;
	cin >> n;
	while(n--){
		string input;
		cin >> input;
		string name;
		int age;
		if (input == "born"){
			cin >> name >> age;
			person.insert({age, name});
		}
		else if(input == "find"){
			cin >> name >> age;
			if ( person.find({age, name}) != person.end()) cout << "YES\n";
			else cout << "NO\n";
		}
		else if (input == "kill"){
			cin >> name >> age;
			person.erase( {age, name} );
		}
		else if (input == "young"){
			cout << person.begin()->second << " " << person.begin()->first << endl;
		}
	}
	/*
	for(auto it = person.begin(); it != person.end(); it++){
		cout << "name" << " " << it->first << " " << "age" << " " << it->second <<endl;
	}
	*/
	return 0;
}
```
:::
:::spoiler HW12 - Poorgrammer <font color="#FD3004">AC</font>

```c=
#include <iostream>
#define ll long long
using namespace std;
ll n, m;
ll a[200010] = {0};
ll test_day(ll day)
{
    ll code = 0;
	int penality = 1;
	
	// the first cup for every day has no penality
	for (int i = 0; i < day; i++){
		code += a[i];
	}
	for(int i = day; i < n; i++){
		// if less than penality, the cup of coffee is useless
		if (a[i] > penality)
			code += (a[i] - penality);
		// after a cycle of "DAY", penality need to be added
		if( (i + 1) % day == 0)
			penality++;
	}
	return code;
}
int main()
{
    int t;
    cin >> t;
    while (t--)
    {
        cin >> n >> m;
        for(int i = 0; i < n; i++){
            cin >> a[i];
        }
        // use binary search!!!
        //at least one day, the most is n day
        // set R = n + 1 to let M has chance to touch n
        ll L = 1, R = n + 1, ans = -1;
        while( L < R ){
            ll M = (L + R) / 2;
            // either bigger or equal to m will be the answer
            if( test_day(M) >= m ) R = ans = M;
            else L = M + 1;
        }
        cout << ans << endl;

    }
    return 0;
}
```
:::
:::spoiler HW12 - The night's watch <font color="#FD3004">AC</font>

```c=
#include <iostream>
#include <climits>
using namespace std;
#define LL long long

LL a[5010] = {0};

LL MIN(LL x, LL y);
LL MAX(LL x, LL y);

int main()
{
	int t;
	cin >> t;
	while(t--){
		int n, m, k;
		LL ans = 0;
		cin >> n >> m >> k;
		for(int i = 0; i < n; i++){
			cin >> a[i];
		}

		if (m <= k) k = m - 1;

		// 命令i個人拿頭
		for(int i = 0; i <= k; i++){
			LL at_least = INT_MAX;
			// j代表有多少無法控制的人拿頭
			for(int j = 0; j <= m - k - 1; j++){
				// 內層max: 我們自己選當然選最大
        		// 外層min：不能控制的情況，我們找最小
				at_least = MIN( at_least, MAX(a[i + j], a[i + j + ( n - m )]) );
			}
			// 可以控制k個人，所以找最大
			ans = MAX(at_least, ans);
		}
		cout << ans << endl;
	}

	return 0;
}
LL MIN(LL x, LL y)
{
	return x < y ? x : y;
}
LL MAX(LL x, LL y)
{
	return x > y ? x : y;
}
```
:::
:::spoiler HW12 - Got flunked <font color="#FD3004">X</font>

```c=

```
:::
:::spoiler HW13 - Skate Shoes Sliding <font color="#FD3004">AC</font>

```c=
#include <iostream>
// 其實能走到的範圍就是 [-l, r]，總共有 l + r + 1 = N + 1 種可能
int l = 0, r = 0;
int main()
{
	int N;
	std::cin >> N;
	while(N--){
		char input;
		std::cin >> input;
		if (input == 'L') l++;
		else if (input == 'R') r++;
	}
	std::cout << l + r + 1 << std::endl;

	return 0;
}

```
:::
:::spoiler HW13 - Guard The Wall <font color="#FD3004">AC</font>

```c=
#include <iostream>
#include <climits>	//for INT_MAX
#include <cstring>  //for memset
using namespace std;

#define MAX(x, y) x > y ? x : y
#define MIN(x, y) x < y ? x : y

int n, q;
pair<int, int> soldier[5010];
int section[5010];
int tmpsection[5010];
int prefix[5010];

int takeout (int first_soldier);

int main()
{
	int t;
	cin >> t;
	while(t--){
		cin >> n >> q;
		for(int i = 1; i <= q; i++){
			cin >> soldier[i].first >> soldier[i].second;
			for(int j = soldier[i].first; j <= soldier[i].second; j++){
				section[j]++;
			}
		}

		int ans = 0;

		// 枚舉拿掉一個人後
		for(int i = 1; i <= q; i++){
			ans = MAX(ans, takeout(i));
		}
		cout << ans << endl;

		memset(soldier, 0, sizeof(soldier));
		memset(section, 0, sizeof(section));
		memset(prefix, 0, sizeof(prefix));
	}

	return 0;
}
int takeout (int first_soldier)
{
	int guarded = 0, reduce = INT_MAX;

	for(int i = 1; i <= n; i++){
		tmpsection[i] = section[i];
	}

	// 將第一個拿掉的人有guard的區域都-1
	for(int i = soldier[first_soldier].first; i <= soldier[first_soldier].second; i++){
		tmpsection[i]--;
	}
	for(int i = 1; i <= n; i++){
		if(tmpsection[i] > 0) guarded++;

		// 對於只有一個人guard的區域建前綴和
		if(tmpsection[i] == 1) prefix[i] = prefix[i - 1] + 1;
		else prefix[i] = prefix[i - 1];
	}

	// 枚舉再拿掉哪一個人會減少最少區域
	for(int second_soldier = 1; second_soldier <= q && second_soldier != first_soldier; second_soldier++){
		reduce = MIN(reduce, prefix[soldier[second_soldier].second] - prefix[soldier[second_soldier].first - 1]);
	}

	memset(tmpsection, 0, sizeof(tmpsection));
	return  guarded - reduce;
}

```
:::
:::spoiler HW13 - I got a perfect body <font color="#FD3004">AC</font>

```c=
#include <iostream>
#include <algorithm> //for sort
#include <cstring>	 //for memset
using namespace std;

#define LL long long

int n, p, k;
int a[300010] = {0};
LL prefix[300010] = {0};

int main()
{
	int t;
	cin >> t;
	while (t--)
	{
		int NOP = 0;
		cin >> n >> p >> k;
		for (int i = 1; i <= n; i++)
		{
			cin >> a[i];
		}
		sort(a + 1, a + 1 + n);

		prefix[1] = a[1];
		for (int i = 1; i <= n; i++)
		{
			// 買到第i個物品要付num[i] + sum[i-1] 元
			if (i < k)
				prefix[i] = prefix[i - 1] + a[i];
			// 但是如果是第 i >= k 個物品，就只要付num[i] + sum[i-k] 元
			// prefix[0] = 0
			else
			// it is better to start with i = 1, because if i start with 0, then the second
			// element is i = 1, then i - k will be less than zero for k = 2;
			// so we use the corresponding index will be better
			// or we can set another else if(i == k) to start with index zero
				prefix[i] = prefix[i - k] + a[i];
		}

		for (int i = 1; i <= n; i++)
		{
			if (p >= prefix[i])
				NOP = i;
		}

		cout << NOP << endl;
		memset(a, 0, sizeof(a));
		memset(prefix, 0, sizeof(prefix));
	}

	return 0;
}
```
:::

:::spoiler BONUS - 3 - Motto Hayaku <font color="#FD3004">AC</font>

```c=
#include <iostream>
#include <algorithm>
#define ll long long

using namespace std;
ll n,x,a,b;
ll idx, target;
ll final_idx, final_m, final_i, final_target;
ll m, tmp_m;
ll tmp_ans = 0, final_ans = 0;
ll not_zero = 0;
ll x_num = 0;
pair<ll,ll>fin[100005];
pair<ll,ll>num[100005];
pair<ll,ll>final_num[100005];
pair<ll,ll>prefix[100005];
pair<ll,ll>prefix2[100005];

bool cmp(pair<ll,ll>a, pair<ll,ll>b)
{
    return a.first < b.first;
}

bool cmp2(pair<ll,ll>a, pair<ll,ll>b)
{
    return a.second < b.second;
}

ll u_bound(ll val, ll l, ll r)
{
    ll left = l, right = r;
    while(left < right)
    {
        ll mid = (left + right) / 2;
        if(prefix[mid].first > val)
            right = mid;
        else
            left = mid + 1;
    }
    return right - 1;
}

int main()
{
    cin >> n >> x >> a >> b >> m;
    for(ll i=1; i<=n; i++)
    {
        cin >> num[i].first;
        final_num[i].first = num[i].first;
        num[i].second = final_num[i].second = i;
    }
    num[0].first = num[0].second = 0;
    prefix2[0].first = prefix2[0].second = 0;
    sort(num+1,num+n+1,cmp);
    sort(final_num+1,final_num+n+1,cmp);
    for(ll i=1; i<=n; i++)
    {
        if(i >= 1)
            prefix[i].first = (i - 1) * num[i].first - prefix2[i-1].first;

        prefix2[i].first= (prefix2[i-1].first + num[i].first);
        prefix[i].second = prefix2[i].second = num[i].second;
    }
    /*for(int i=1; i<=n; i++)
        cout << num[i].first << " ";
    cout << endl;
    for(int i=1; i<=n; i++)
        cout << prefix[i].first << " ";
    cout << endl;
    for(int i=1; i<=n; i++)
        cout << prefix2[i].first << " ";
    cout << endl;*/
    tmp_m = m;
    idx = u_bound(tmp_m, 1, n+1);
    target = num[idx].first;
    tmp_m -= prefix[idx].first;
    target = min(x, target + (tmp_m / idx));
    //cout << "tmp_m: " << tmp_m << " target: " << target << " idx: " << idx << endl;
    tmp_m %= idx;


    for(ll i=idx; i>=1; i--)
    {
        final_num[i].first = target;
        final_num[i].second = num[i].second;
        if(target < x)
        {
            if(tmp_m)
            {
                tmp_m--;
                final_num[i].first++;
            }
        }
    }
    for(ll i=idx+1; i<=n; i++)
    {
        final_num[i].first = num[i].first;
        final_num[i].second = num[i].second;
    }
    for(ll i=1; i<=n; i++)
        if(final_num[i].first == x)
            x_num++;

    final_ans = target * b + x_num * a;

    for(ll i=n; i>=1; i--)
    {
        m -= (x - num[i].first);
        if(m <= 0)
            break;

        tmp_m = m;
        idx = u_bound(tmp_m, 1, n+1);
        target = num[idx].first;
        tmp_m -= prefix[idx].first;
        target = min(x, target + (tmp_m / idx));

        tmp_m %= idx;
        tmp_ans = b * target + (n - i + 1) * a;

        if(tmp_ans >= final_ans)
        {
            //cout << "m: " << m << " idx: " << idx << " target: " << target << " tmp_m: " << tmp_m << " tmp_ans: " << tmp_ans << endl;
            not_zero = 1;
            final_ans = tmp_ans;
            final_i = i;
            final_idx = idx;
            final_m = tmp_m;
            final_target = target;
        }
    }
    if(not_zero)
    {
        for(ll i = final_idx; i>=1; i--)
        {
            final_num[i].first = final_target;
            final_num[i].second = num[i].second;
            if(final_m)
            {
                final_m--;
                final_num[i].first++;
            }
        }
        for(ll i = final_idx+1; i<final_i; i++)
        {
            final_num[i].first = num[i].first;
            final_num[i].second = num[i].second;
        }
        for(ll i=final_i; i<=n; i++)
        {
            final_num[i].first = x;
            final_num[i].second = num[i].second;
        }
    }
    sort(final_num+1, final_num+n+1, cmp2);
    cout << final_ans << '\n';
    for(ll i=1; i<=n; i++)
        cout << final_num[i].first << " ";
    return 0;
}
```
:::
:::spoiler HW14 - Eat candies <font color="#FD3004">AC</font>

```c=
#include <iostream>
#include <algorithm>
using namespace std;
int main()
{
    int t;
    cin >> t;
    while(t--)
    {
        int candy[3];
        for(int i = 0; i < 3; i++){
            cin >> candy[i];
        }
        sort(candy, candy + 3);
        if(candy[2] > candy[0] + candy[1]){
            cout << candy[0] + candy[1] << endl;
        }
        else {
            cout << ( candy[0] + candy[1] + candy[2] ) / 2 << endl;
        }
    }
    return 0;
}
```
:::
:::spoiler HW14 - knuckle's name <font color="#FD3004">AC</font>

```c=
#include <iostream>
#include <cstring>
#include <string>
using namespace std;

bool edge[30][30];
bool visited[30];

// dfs function
void dfs(int i);

int main()
{
    int t;
    cin >> t;
    while(t--)
    {
        int n;
        cin >> n;
        memset(edge, false, sizeof(edge));
        memset(visited, false, sizeof(visited));
        while(n--)
        {
            string str;
            cin >> str;
            for(int i = 0; i < str.length(); i++){
                if(i == 0){
                    edge[str[i] - 'a'][str[i] - 'a'] = true;
                }
                else {
                    edge[str[i] - 'a'][str[i - 1] - 'a'] = true;
                    edge[str[i - 1] - 'a'][str[i] - 'a'] = true;
                }
            }
        }
        // declare in local, remember to reset the num
        int ans = 0;
        for(int i = 0; i < 26; i++){
            if( !visited[i] && edge[i][i] ){
                dfs(i);
                ans++;
            }
        }
        cout << ans << endl;
    }
    return 0;
}
void dfs(int i)
{
    visited[i] = true;
    for(int j = 0; j < 26; j++){
        if( !visited[j] && edge[i][j] ){
            dfs(j);
        }
    }
}
```
:::
:::spoiler HW14 - Unlimited Triangle Work <font color="#FD3004">AC</font>

```c=
#include <iostream>
#include <cstring>
#include <string>
using namespace std;
#define ll long long int
ll ans[100005];
ll pre[100005];
ll answer = 0;
int main()
{
    int t;
    cin >> t;
    while(t--)
    {
        ll A, B, C, D;
        cin >> A >> B >> C >> D;

        answer = 0;
        memset(ans, 0, sizeof(ans));
        memset(pre, 0, sizeof(pre));

        for(ll i = A; i <= B; i++){ // set the range of x + y
            ll L = i + B;
            ll R = i + C + 1;
            pre[L] += 1;
            pre[R] -= 1;
        }
        for(ll i = A + B; i <= B + C + 1; i++){ // do prefix of x + y
            pre[i + 1] += pre[i];
        }
        for(ll i = A + B; i <= C + D; i++){ // do prefix of z
            pre[i + 1] += pre[i];
        }
        for(ll i = C; i <= D; i++){ //get answer for every z
            ans[i] = pre[C + D] - pre[i];
        }
        for(ll i = C; i <= D; i++){ //sum up the answer
            answer += ans[i];
        }
        cout << answer << endl;
    }
    return 0;
}
```
:::

:::spoiler QUIZ - 4 - Poorgrammer - ver2  <font color="#FD3004">AC</font>

```c=
#include <iostream>
#include <algorithm>
#define ll long long
using namespace std;
ll n, m;
ll a[200010] = {0};
bool cmp(int x, int y)
{
	return x > y;
}
ll test_day(ll day)
{
    ll code = 0;
	int penality = 1;
	
	// the first cup for every day has no penality
	for (int i = 0; i < day; i++){
		code += a[i];
	}
	for(int i = day; i < n; i++){
		// if less than penality, the cup of coffee is useless
		if (a[i] > penality)
			code += (a[i] - penality);
		// after a cycle of "DAY", penality need to be added
		if( (i + 1) % day == 0)
			penality++;
	}
	return code;
}
int main()
{
    int t;
    cin >> t;
    while (t--)
    {
        cin >> n >> m;
        for(int i = 0; i < n; i++){
            cin >> a[i];
        }
        // in version 2, the sequence of coffee isn't from big to small
		sort(a, a + n, cmp);
        // use binary search!!!
        //at least one day, the most is n day
        // set R = n + 1 to let M has chance to touch n
        ll L = 1, R = n + 1, ans = -1;
        while( L < R ){
            ll M = (L + R) / 2;
            // bigger than m will be the answer
            if( test_day(M) > m ) R = ans = M;
            else L = M + 1;
        }
        cout << ans << endl;

    }
    return 0;
}
```
:::
:::spoiler QUIZ - 4 - Guard The Wall - ver2  <font color="#FD3004">AC</font>

```c=
#include <iostream>
#include <climits>
#include <cstring>
using namespace std;
#define MAX(x, y) (x) > (y) ? (x) : (y)
#define MIN(x, y) (x) < (y) ? (x) : (y)

int n, q;

pair<int, int> soldier[305];
int section[305];
int tmpsection[305];
int prefix[305];

int takeout(int first, int second)
{
    int guarded = 0, reduce = INT_MAX;
    for(int i = 1; i <= n; i++){
        tmpsection[i] = section[i];
    }
    for(int i = soldier[first].first; i <= soldier[first].second; i++){
        tmpsection[i]--;
    }

    for(int i = soldier[second].first; i <=soldier[second].second; i++){
        tmpsection[i]--;
    }

    for(int i = 1; i <= n; i++){
        if (tmpsection[i] > 0) guarded++;

        if (tmpsection[i] == 1) prefix[i] = prefix[i - 1] + 1;
        else prefix[i] = prefix[i - 1];
    }
    /*
    cout << "first" << " " << first << "second" << " " << second << endl;
    cout << "prefix : ";
    for(int i = 1; i <= n; i++){
        cout << prefix[i] << " ";
    }
    cout << endl;
    */
    for(int i = 1; i <= q && i != first && i != second; i ++){
        reduce = MIN(reduce, prefix[soldier[i].second] - prefix[soldier[i].first - 1]);
    }
    memset(tmpsection, 0, sizeof(tmpsection));
    memset(prefix, 0, sizeof(prefix));
    return guarded - reduce;
}
int main()
{
    int t;
    cin >> t;
    while(t--){
        cin >> n >> q;
        for(int i = 1; i <= q; i++){
            cin >> soldier[i].first >> soldier[i].second;
            for(int j = soldier[i].first; j <= soldier[i].second; j++){
                section[j]++;
            }
        }

        int ans = 0;
        for(int i = 1; i < q; i++){
            for(int j = i + 1; j <= q; j++){
                //cout << "i = " << i << "j = " << j << endl;////////////
                int tmp = takeout(i, j);
                ans = MAX(ans, tmp);
            }
        }
        cout << ans << endl;
        memset(section, 0, sizeof(section));
        memset(prefix, 0, sizeof(prefix));
        memset(soldier, 0, sizeof(soldier));
    }
    return 0;
}

```
:::
:::spoiler Unlimited Triangle Work - ver2 - ver2  <font color="#FD3004">AC</font>

```c=
#include <iostream>
#include <memory.h>
#include <string>
using namespace std;
#define ll long long int
ll ans[100005];
ll pre[100005];
ll answer = 0;
int main()
{
    int t;
    cin >> t;
    while(t--)
    {
        ll A, B, C, D;
        cin >> A >> B >> C >> D;

        answer = 0;
        memset(ans, 0, sizeof(ans));
        memset(pre, 0, sizeof(pre));

        for(ll i = A; i <= B; i++){ // set the range of x + y
            ll L = i + B;
            ll R = i + C + 1;
            pre[L] += 1;
            pre[R] -= 1;
        }
        for(ll i = 1; i <100005; i++){ // do prefix of x + y
            pre[i] += pre[i - 1];
        }
        for(ll i = 1; i <100005; i++){ // do prefix of z
            pre[i] += pre[i - 1];
        }
        for(ll i = C; i <= D; i++){ //get answer for every z
            if(i % 2 == 0) ans[i] = pre[(int)(1.5 * i) - 1] - pre[i];
            else ans[i] = pre[(int)(1.5 * i)] - pre[i];
        }
        for(ll i = C; i <= D; i++){ //sum up the answer
            answer += ans[i];
        }
        cout << answer << endl;
    }
    return 0;
}

```
:::