# 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;
}
```
:::
Sign in with Wallet
Connect another wallet