習題參考解答
===
習題 1
---
### Diamond
```clike=
#include <stdio.h>
int main() {
printf(" *\n");
printf(" * *\n");
printf(" * * *\n");
printf(" * * * *\n");
printf(" * * * * *\n");
printf(" * * * * * *\n");
printf(" * * * * * * *\n");
printf(" * * * * * * * *\n");
printf(" * * * * * * * * *\n");
printf("* * * * * * * * * *\n");
printf(" * * * * * * * * *\n");
printf(" * * * * * * * *\n");
printf(" * * * * * * *\n");
printf(" * * * * * *\n");
printf(" * * * * *\n");
printf(" * * * *\n");
printf(" * * *\n");
printf(" * *\n");
printf(" *\n");
return 0;
}
```
習題 2
---
### Judge Girl 50114. Simple Polygon
```clike
#include <stdio.h>
int main() {
int ax, ay, bx, by, cx, cy, dx, dy;
scanf("%d%d%d%d%d%d%d%d", &ax, &ay, &bx, &by, &cx, &cy, &dx, &dy);
int perimeter = bx - ax + by - ay + cx - bx + cy - by + cx - dx + cy - dy + dx - ax + dy - ay;
int area = (cx - ax) * (cy - ay) - (dx - ax) * (cy - dy) - (cx - bx) * (by - ay);
printf("%d\n%d\n", perimeter, area);
return 0;
}
```
### Judge Girl 50115. Depth of Water
```clike
#include <stdio.h>
int main() {
int a, b, h, c, d;
scanf("%d%d%d%d%d", &a, &b, &h, &c, &d);
printf("%d\n", a*b*h / (a*b - c*d));
return 0;
}
```
### Judge Girl 50078. Parallelogram
```clike
#include <stdio.h>
int main() {
int ax, ay, bx, by, cx, cy;
scanf("%d%d%d%d%d%d", &ax, &ay, &bx, &by, &cx, &cy);
printf("%d\n%d\n", cx + bx - ax, cy + by - ay);
printf("%d\n%d\n", cx + ax - bx, cy + ay - by);
printf("%d\n%d\n", bx + ax - cx, by + ay - cy);
return 0;
}
```
### Judge Girl 50079. Apple Pile
```clike
#include <stdio.h>
int main() {
int a, b;
scanf("%d %d", &a, &b);
printf("%d\n", (a + b)*(b - a + 1) / 2);
printf("%d\n", a + b + (b - a - 1) * 2);
return 0;
}
```
習題 3
---
### Judge Girl 50116. Play with digits
```clike
#include <stdio.h>
int main() {
int n, digits = 0, zero = 0, oddSum = 0, evenSum = 0;
while (scanf("%d", &n) == 1) {
digits++;
if (n == 0)
zero++;
if (digits % 2)
oddSum += n;
else
evenSum += n;
}
int even = (n % 2 == 0)? 1 : 0;
int divisible = !((oddSum - evenSum) % 11);
printf("%d\n%d\n%d\n%d\n", digits, even, zero, divisible);
return 0;
}
```
### Judge Girl 50117. Divide a number
```clike
#include <stdio.h>
int main() {
int k, n;
scanf("%d", &k);
int temp = 0;
int zero = 1;
while (scanf("%d", &n) == 1) {
if (temp == 0) {
if (n < k && n != 0) {
temp = n * 10;
if (zero == 0)
printf("0\n");
}
else {
printf("%d\n", n / k);
zero = 0;
temp = (n % k) * 10;
}
}
else {
temp += n;
printf("%d\n", temp / k);
zero = 0;
temp = (temp % k) * 10;
}
}
if (zero == 1)
printf("0\n");
return 0;
}
```
### Judge Girl 50080. Scan The Blocks
```clike
#include <stdio.h>
int main() {
int n;
while (scanf("%d", &n) != EOF) {
int max = -10001, min = 10001;
for (int i = 0; i < n; i++) {
int number;
if (scanf("%d", &number) == EOF) {
printf("%d\n", min);
return 0;
}
if (number < min)
min = number;
if (number > max)
max = number;
}
printf("%d\n", max);
}
return 0;
}
```
### Judge Girl 50081. Rebot Simulation
```clike
#include <stdio.h>
int main(void) {
int N, M, ins, x = 0, y = 0;
scanf("%d%d", &N, &M);
printf("%d\n%d\n", x, y);
while (scanf("%d", &ins) != EOF) {
if (ins%5 == 0)
continue;
else if (ins%5 == 1) {
if (x + ins > N - 1)
continue;
else
x += ins;
}
else if (ins%5 == 2) {
if (x - ins < 0)
continue;
else
x -= ins;
}
else if (ins%5 == 3) {
if (y + ins > M - 1)
continue;
else
y += ins;
}
else {
if (y - ins < 0)
continue;
else
y -= ins;
}
printf("%d\n%d\n", x, y);
}
return 0;
}
```
### Codeforces: Theatre Square
這題要注意的是雖然$n,m,a$的取值範圍都在$10^9$裡面(可以用int表示)，但當$a$的值很小，$n,m$的值很大，$(n/a)(m/a)$是會超過$10^9$的。
```clike
#include <stdio.h>
int main() {
int n, m, a;
scanf("%d%d%d", &n, &m, &a);
long long x = (n % a)? 1 : 0, y = (m % a)? 1 : 0;
x += n / a;
y += m / a;
printf("%lld\n", x * y);
return 0;
}
```
習題 4
---
### Judge Girl 50119. Paper, Scissors, Stone
```clike
#include <stdio.h>
int main() {
int xt, a, b, c;
scanf("%d%d%d%d", &xt, &a, &b, &c);
int yt, d, e, f;
scanf("%d%d%d%d", &yt, &d, &e, &f);
int n;
scanf("%d", &n);
for (int i = 0; i < n; i++) {
int whoWins, pairs = 0, draw = 1;
while (draw) {
int x = xt % 3, y = yt % 3;
xt = ((a * xt) + b) % c;
yt = ((d * yt) + e) % f;
pairs++;
if ((x == 0 && y == 0) || (x == 1 && y == 1) || (x == 2 && y == 2))
continue;
else if ((x == 0 && y == 2) || (x == 1 && y == 0) || (x == 2 && y == 1)) {
draw = 0;
whoWins = 0;
}
else if ((y == 0 && x == 2) || (y == 1 && x == 0) || (y == 2 && x == 1)) {
draw = 0;
whoWins = 1;
}
}
printf("%d %d\n", whoWins, pairs);
}
return 0;
}
```
### Judge Girl 50120. Consecutive 1's
```clike
#include <stdio.h>
int main() {
int n;
scanf("%d", &n);
int a[n][n];
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
scanf("%d", &a[i][j]);
int max = 0;
// row
for (int i = 0; i < n; i++) {
int current = 0;
for (int j = 0; j < n; j++) {
if (a[i][j] == 1) {
current++;
if (current > max)
max = current;
}
else
current = 0;
}
}
// column
for (int i = 0; i < n; i++) {
int current = 0;
for (int j = 0; j < n; j++) {
if (a[j][i] == 1) {
current++;
if (current > max)
max = current;
}
else
current = 0;
}
}
// diagonal
for (int i = 0; i < n; i++) {
int current = 0;
for (int j = 0; i + j < n; j++) {
if (a[j][j+i] == 1) {
current++;
if (current > max)
max = current;
}
else
current = 0;
}
current = 0;
for (int j = 0; i + j < n; j++) {
if (a[i+j][j] == 1) {
current++;
if (current > max)
max = current;
}
else
current = 0;
}
}
printf("%d\n", max) ;
return 0;
}
```
### Judge Girl 50121. Push Stones
```clike
#include <stdio.h>
int main() {
int n, m;
scanf("%d%d", &n, &m);
int map[n][m];
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
map[i][j] = 0;
int x, y, energy;
scanf("%d%d%d", &y, &x, &energy);
map[y][x] = energy;
int stones;
scanf("%d", &stones);
for (int i = 0; i < stones; i++) {
int x, y, weight;
scanf("%d%d%d", &y, &x, &weight);
map[y][x] = weight;
}
int instruction;
while (scanf("%d", &instruction) == 1) {
if (instruction == 0) {
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
printf("%d%c", map[i][j], j == m - 1? '\n' : ' ');
}
else if (instruction == 1) {
if (x < m - 1) {
int stoneX = x + 1, stoneY = y, valid = 1, cost = 0, stoneCount = 0;
while (valid) {
if (cost > energy) {
valid = 0;
break;
}
if (stoneX >= m - 1 && map[stoneY][stoneX] != 0) {
valid = 0;
break;
}
if (stoneX < m - 1 && map[stoneY][stoneX] != 0) {
if (energy - cost >= map[stoneY][stoneX]) {
cost += map[stoneY][stoneX];
stoneX++;
stoneCount++;
}
else {
valid = 0;
break;
}
}
else if (map[stoneY][stoneX] == 0)
break;
}
if (valid) {
for (int i = 0; i < stoneCount; i++) {
map[y][stoneX-i] = map[y][stoneX - i - 1];
}
energy -= cost;
map[y][x] = 0;
x++;
map[y][x] = energy;
}
}
}
else if (instruction == 2) {
if (y < n - 1) {
int stoneX = x, stoneY = y + 1, valid = 1, cost = 0, stoneCount = 0;
while (valid) {
if (cost > energy) {
valid = 0;
break;
}
if (stoneY >= n - 1 && map[stoneY][stoneX] != 0) {
valid = 0;
break;
}
if (stoneY < n - 1 && map[stoneY][stoneX] != 0) {
if (energy - cost >= map[stoneY][stoneX]) {
cost += map[stoneY][stoneX];
stoneY++;
stoneCount++;
}
else {
valid = 0;
break;
}
}
else if (map[stoneY][stoneX] == 0)
break;
}
if (valid) {
for (int i = 0; i < stoneCount; i++) {
map[stoneY - i][stoneX] = map[stoneY - i - 1][stoneX];
}
energy -= cost;
map[y][x] = 0;
y++;
map[y][x] = energy;
}
}
}
else if (instruction == 3) {
if (x > 0) {
int stoneX = x - 1, stoneY = y, valid = 1, cost = 0, stoneCount = 0;
while (valid) {
if (cost > energy) {
valid = 0;
break;
}
if (stoneX <= 0 && map[stoneY][stoneX] != 0) {
valid = 0;
break;
}
if (stoneX > 0 && map[stoneY][stoneX] != 0) {
if (energy - cost >= map[stoneY][stoneX]) {
cost += map[stoneY][stoneX];
stoneX--;
stoneCount++;
}
else {
valid = 0;
break;
}
}
else if (map[stoneY][stoneX] == 0)
break;
}
if (valid) {
for (int i = 0; i < stoneCount; i++) {
map[y][stoneX + i] = map[y][stoneX + i + 1];
}
energy -= cost;
map[y][x] = 0;
x--;
map[y][x] = energy;
}
}
}
else {
if (y > 0) {
int stoneX = x, stoneY = y - 1, valid = 1, cost = 0, stoneCount = 0;
while (valid) {
if (cost > energy) {
valid = 0;
break;
}
if (stoneY <= 0 && map[stoneY][stoneX] != 0) {
valid = 0;
break;
}
if (stoneY > 0 && map[stoneY][stoneX] != 0) {
if (energy - cost >= map[stoneY][stoneX]) {
cost += map[stoneY][stoneX];
stoneY--;
stoneCount++;
}
else {
valid = 0;
break;
}
}
else if (map[stoneY][stoneX] == 0)
break;
}
if (valid) {
for (int i = 0; i < stoneCount; i++) {
map[stoneY + i][stoneX] = map[stoneY + i + 1][stoneX];
}
energy -= cost;
map[y][x] = 0;
y--;
map[y][x] = energy;
}
}
}
}
return 0;
}
```
### Jugde Girl 50085. Tank Simulation
```clike
#include <stdio.h>
int main() {
int n, m, l, w, o;
scanf("%d%d%d%d%d ", &n, &m, &l, &w, &o);
int map[n][m];
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
map[i][j] = 0;
for (int i = 0; i < o; i++) {
int x, y;
scanf("%d%d", &x, &y);
map[y][x] = 2;
}
int x = 0, y = 0;
for (int i = 0; i < l; i++)
for (int j = 0; j < w; j++)
map[y+i][x+j] = 1;
int instruction;
while (scanf("%d", &instruction) == 1) {
if (instruction == 0) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++)
printf("%d", map[i][j]);
printf("\n");
}
continue;
}
int obstacleCount = 0;
if (instruction == 1) {
if (x + w - 1 < m - 1) {
for (int i = 0; i < l; i++)
if (map[y+i][x+w] == 2)
obstacleCount++;
if (obstacleCount <= 1) {
for (int i = 0; i < l; i++) {
map[y+i][x] = 0;
map[y+i][x+w] = 1;
}
x++;
}
}
}
else if (instruction == 2) {
if (y + l - 1 < n - 1) {
for (int i = 0; i < w; i++)
if (map[y+l][x+i] == 2)
obstacleCount++;
if (obstacleCount <= 1) {
for (int i = 0; i < w; i++) {
map[y][x+i] = 0;
map[y+l][x+i] = 1;
}
y++;
}
}
}
else if (instruction == 3) {
if (x > 0) {
for (int i = 0; i < l; i++)
if (map[y+i][x-1] == 2)
obstacleCount++;
if (obstacleCount <= 1) {
for (int i = 0; i < l; i++) {
map[y+i][x+w-1] = 0;
map[y+i][x-1] = 1;
}
x--;
}
}
}
else if (instruction == 4) {
if (y > 0) {
for (int i = 0; i < w; i++)
if (map[y-1][x+i] == 2)
obstacleCount++;
if (obstacleCount <= 1) {
for (int i = 0; i < w; i++) {
map[y+l-1][x+i] = 0;
map[y-1][x+i] = 1;
}
y--;
}
}
}
else {
if ((x + w - 1 < m - 1) && (y + l - 1 < n - 1)) {
for (int i = 1; i < l; i++)
if (map[y+i][x+w] == 2)
obstacleCount++;
for (int i = 1; i < w; i++)
if (map[y+l][x+i] == 2)
obstacleCount++;
if (map[y+l][x+w] == 2)
obstacleCount++;
if (obstacleCount <= 1) {
map[x][y] = 0;
for (int i = 0; i < w; i++) {
map[y][x+i] = 0;
map[y+l][x+i+1] = 1;
}
for (int i = 0; i < l; i++) {
map[y+i][x] = 0;
map[y+i+1][x+w] = 1;
}
x++, y++;
}
}
}
}
return 0;
}
```
習題 5
---
### Judge Girl 50086. Students and Party
```clike
#include <stdio.h>
#define k 256
#define max_n 32768
int friends[max_n][k];
int invited[max_n] = {0};
int main() {
int N, E, ID1, ID2;
scanf("%d%d", &N, &E); // read
for (int i = 0; i < max_n; i++)
for (int j = 0; j < k; j++)
friends[i][j] = -1;
while (E--) {
int x = 0; int y = 0;
scanf("%d", &ID1);
while (friends[ID1][x] != -1) // x means the nth friend of student1
x++;
scanf("%d", &friends[ID1][x]);// student2 is a friend of student1
ID2 = friends[ID1][x];
while (friends[ID2][y] != -1) // y means the nth friend of student2
y++;
friends[ID2][y] = ID1; // student1 is a friend of student2
}
int party;// party means the student who is planning for the party
while (scanf("%d", &party) == 1) {
invited[party] = 1; // party planner is attending the party as well
for (int i = 0; i < k; i++) //inviting all his friends
invited[friends[party][i]] = 1;
}
for (int i = 0; i < N; i++)
if (invited[i] == 0)
printf("%d\n", i); // print ID if the student is not invited
return 0;
}
```
### Judge Girl 50087. See-Saw
```clike
#include <stdio.h>
int main(void) {
int n, a[2048], Mleft = 0, Mright = 0, step1 = 0;
scanf("%d", &n);
for(int i = 0; i < n; i++)
scanf("%d", &a[i]);
for(int i = 1; i < n - 1; i++) {
Mleft = Mright = 0;
for(int j = 0; j < i; j++)
Mleft += a[j] * (i - j);
for(int k = i + 1; k < n; k++)
Mright += a[k] * (k - i);
if(Mleft == Mright) {
step1 = 1;
for(int l = 0 ; l < i; l++)
printf("%d ", a[l]);
printf("v ");
for(int l = i + 1; l < n - 1; l++)
printf("%d ", a[l]);
printf("%d\n", a[n-1]);
break;
}
}
if(step1 == 0) {
for(int m = 0; m < n; m++) {
int temp = a[m];
a[m] = a[n-m-1];
a[n-m-1] = temp;
for(int i = 1; i < n - 1; i++) {
Mleft = Mright = 0;
for(int j = 0; j < i; j++)
Mleft += a[j] * (i - j);
for(int k = i + 1; k < n; k++)
Mright += a[k] * (k - i);
if(Mleft == Mright) {
for(int l = 0 ; l < i; l++)
printf("%d ", a[l]);
printf("v ");
for(int l = i + 1; l < n - 1; l++)
printf("%d ", a[l]);
printf("%d\n", a[n-1]);
return 0;
}
}
}
}
}
```
### Judge Girl 50122. Knights’ Tour
```clike
#include <stdio.h>
int board[128][128];
int valid(int row, int column, int n) {
if (row > n - 1 || column > n - 1)
return 0;
else if (row < 0 || column < 0)
return 0;
else if (board[row][column] == 1)
return 0;
return 1;
}
int main() {
int dx[9] = {0, -2, -1, 1, 2, 2, 1, -1, -2}; // right : +, left : -
int dy[9] = {0, 1, 2, 2, 1, -1, -2, -2, -1}; // down : +, up : -
int n, m;
scanf("%d%d", &n, &m);
int knights[m + 1][2], output[128][128] = {0};
for (int i = 1; i <= m; i++) {
int row, column;
scanf("%d%d", &row, &column);
knights[i][0] = row, knights[i][1] = column;
board[row][column] = 1;
output[row][column] = 10000 * i;
}
int stopped[m];
for (int i = 1; i <= m; i++)
stopped[i] = 0;
int keepGoing = 1, turn = 1;
while (keepGoing) {
for (int i = 1; i <= m; i++) {
int decision = -1, pMin = 10000000;
for (int j = 1; j <= 8; j++) {
int nextRow = knights[i][0] + dx[j];
int nextColumn = knights[i][1] + dy[j];
if (!valid(nextRow, nextColumn, n))
continue;
int p = 0;
for (int k = 1; k <= 8; k++)
if (valid(nextRow + dx[k], nextColumn + dy[k], n))
p++;
if (p < pMin) {
pMin = p;
decision = j;
}
}
if (decision == -1)
stopped[i] = 1;
else {
knights[i][0] += dx[decision];
knights[i][1] += dy[decision];
board[knights[i][0]][knights[i][1]] = 1;
output[knights[i][0]][knights[i][1]] = 10000 * i + turn;
}
}
int end = 1;
for (int i = 1; i <= m; i++)
if (!stopped[i]) {
end = 0;
break;
}
if (end)
keepGoing = 0;
turn++;
}
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
printf("%d%c", output[i][j], j == n - 1? '\n' : ' ');
return 0;
}
```
### Judge Girl 50123. Magic Square
```clike
#include <stdio.h>
int grid[1000][1000];
int main() {
int n, k, r, c;
scanf("%d%d%d%d", &n, &k, &r, &c);
int back = k, backR = r, backC = c;
while (back >= 1) {
grid[backR][backC] = back;
backR = (backR + 1) % n, backC = (backC - 1 + n) % n;
back--;
}
while (k <= n * n) {
grid[r][c] = k;
int nextR = (r - 1 + n) % n, nextC = (c + 1 + n) % n;
if (grid[nextR][nextC] != 0) {
nextR = (r + 1) % n, nextC = c;
}
r = nextR, c = nextC;
k++;
}
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
printf("%d%c", grid[i][j], (j == n - 1)? '\n' : ' ');
return 0;
}
```
### Codeforces. Doors Breaking and Repairing
```math.h```已經有內建的ceiling function了~
```clike
#include <stdio.h>
#include <math.h>
int main() {
int n, x, y;
scanf("%d%d%d", &n, &x, &y);
int durability[n];
for (int i = 0; i < n; i++)
scanf("%d", &durability[i]);
double count = 0;
int destroyed = 0;
if (x <= y) {
for (int i = 0; i < n; i++) {
if (durability[i] <= x)
count++;
}
destroyed = ceil(count / 2);
}
else {
destroyed = n;
}
printf("%d\n", destroyed);
return 0;
}
```
## 習題 6
### Judge Girl 50088. Mountain Travelers
```clike
int visited[1024][1024] = {0};
int dr[8] = {0, 0, 1, -1, 1, -1, -1, 1};
int dc[8] = {1, -1, 0, 0, 1, -1, 1, -1};
int in_map(int N, int M, int r, int c) {
return r >= 0 && r <= N - 1 && c >= 0 && c <= M - 1;
}
void travel(int map[1024][1024], int N, int M, int A_r, int A_c, int B_r, int B_c, int directionA[], int directionB[]) {
visited[A_r][A_c] = visited[B_r][B_c] = 1;
int A_stop = 0, B_stop = 0, A_steps = 0, B_steps = 0;
while (!A_stop || !B_stop) {
// choose which cell the travelers should go
int A_steepest = 0, A_decision = -1, B_steepest = 0, B_decision = -1;
for (int i = 0; !A_stop && i < 8; i++) {
int new_r = A_r + dr[i], new_c = A_c + dc[i];
if (in_map(N, M, new_r, new_c)) {
if (map[new_r][new_c] - map[A_r][A_c] > A_steepest) {
A_steepest = map[new_r][new_c] - map[A_r][A_c];
A_decision = i;
}
}
}
for (int i = 0; !B_stop && i < 8; i++) {
int new_r = B_r + dr[i], new_c = B_c + dc[i];
if (in_map(N, M, new_r, new_c)) {
if (map[B_r][B_c] - map[new_r][new_c] > B_steepest) {
B_steepest = map[B_r][B_c] - map[new_r][new_c];
B_decision = i;
}
}
}
// the travelers now move into the new cell
if (!A_stop && A_decision != -1) {
directionA[A_steps] = A_decision;
A_steps++;
A_r += dr[A_decision], A_c += dc[A_decision];
}
if (!B_stop && B_decision != -1) {
directionB[B_steps] = B_decision;
B_steps++;
B_r += dr[B_decision], B_c += dc[B_decision];
}
// if the travelers can't find a suitable cell
if (A_decision == -1) A_stop = 1;
if (B_decision == -1) B_stop = 1;
// if they go into same cell
if (A_r == B_r && A_c == B_c) A_stop = B_stop = 1;
// if they go into cell that has been visited
// (note that the traveler will never go into cells that has been visited by themselves
// since the height is monotonically increasing/decreasing)
if (visited[A_r][A_c]) A_stop = 1;
if (visited[B_r][B_c]) B_stop = 1;
if (A_stop) directionA[A_steps] = -1;
if (B_stop) directionB[B_steps] = -1;
visited[A_r][A_c] = 1;
visited[B_r][B_c] = 1;
}
}
```
### Judge Girl 50124. Knights' Tour with Functions
main.c
```clike
#include <stdio.h>
#include "validMoveNum.h"
#include "nextMove.h"
int main() {
int n, m;
scanf("%d%d", &n, &m);
int visited[100][100] = {0}, output[100][100] = {0};
int knights[m + 1][2];
for (int i = 1; i <= m; i++) {
scanf("%d%d", &knights[i][0], &knights[i][1]);
visited[knights[i][0]][knights[i][1]] = 1;
output[knights[i][0]][knights[i][1]] = i * 10000;
}
int move[8][2] = {{-2, 1}, {-1, 2}, {1, 2}, {2, 1}, {2, -1}, {1, -2}, {-1, -2}, {-2, -1}};
int keepGoing = 1, turn = 1, stopped[m + 1];
for (int i = 1; i <= m; i++)
stopped[i] = 0;
while (keepGoing) {
for (int i = 1; i <= m; i++) {
if (stopped[i])
continue;
int decision = nextMove(knights[i][0], knights[i][1], n, visited);
if (decision == -1)
stopped[i] = 1;
else {
knights[i][0] += move[decision][0];
knights[i][1] += move[decision][1];
visited[knights[i][0]][knights[i][1]] = 1;
output[knights[i][0]][knights[i][1]] = 10000 * i + turn;
}
}
int end = 1;
for (int i = 1; i <= m; i++)
if (!stopped[i]) {
end = 0;
break;
}
if (end)
keepGoing = 0;
turn++;
}
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
printf("%d%c", output[i][j], j == n - 1 ? '\n' : ' ');
return 0;
}
```
validMoveNum.c
```clike
int validMoveNum(int r, int c, int n, int visited[100][100]) {
if (r < 0 || r > n - 1 || c < 0 || c > n - 1)
return -1;
if (visited[r][c])
return -1;
int move[8][2] = {{ -2, 1}, { -1, 2}, {1, 2}, {2, 1}, {2, -1}, {1, -2}, { -1, -2}, { -2, -1}};
int num = 0;
for (int i = 0; i < 8; i++) {
int nextR = r + move[i][0], nextC = c + move[i][1];
if (nextR < 0 || nextR > n - 1 || nextC < 0 || nextC > n - 1)
continue;
if (!visited[nextR][nextC])
num++;
}
return num;
}
```
nextMove.c
```clike
#include "validMoveNum.h"
int nextMove(int r, int c, int n, int visited[100][100]) {
int decision = -1, pMin = 1000000;
int move[8][2] = {{-2,1},{-1,2},{1,2},{2,1},{2,-1},{1,-2},{-1,-2},{-2,-1}};
for (int i = 0; i < 8; i++) {
int p = validMoveNum(r + move[i][0], c + move[i][1], n, visited);
if (p == -1) continue;
if (p < pMin) {
pMin = p;
decision = i;
}
}
return decision;
}
```
### Judge Girl 50125. Consecutive 1’s with Function
main.c
```clike
#include <stdio.h>
#include "findLength.h"
int main() {
int n;
scanf("%d", &n);
int array[256][256] = {0};
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
scanf("%d", &array[i][j]);
int direction[4][2] = {{1,0}, {1,1}, {0,1}, {-1,1}};
int max = 0;
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
for (int k = 0; k < 4; k++) {
int length = findLength(array, n, i, j, direction[k][0], direction[k][1]);
if (length > max)
max = length;
}
printf("%d\n", max);
return 0;
}
```
findLength.c
```clike
int findLength(int array[][256], int N, int r, int c, int dr, int dc) {
int length = 0, max = 0;
for (int i = r, j = c; i < N && j < N && i >= 0 && j >= 0; i += dr, j += dc) {
if (array[i][j] == 1) {
length++;
if (length > max) max = length;
}
else
length = 0;
}
return max;
}
```
## 習題 7
### Judge Girl 50128. Split a List
```clike
#include <stdlib.h>
void split(int A[], int *a[], int *head[], int k) {
int sizeA = 0;
while (a[sizeA] != NULL)
sizeA++;
sizeA++;
for (int i = 0; i < sizeA; i++)
a[i] = NULL;
int tail[k];
for (int i = 0; i < k; i++)
tail[i] = -1;
for (int i = 0; i < sizeA; i++) {
int remainder = A[i] % k;
if (tail[remainder] == -1)
head[remainder] = &A[i];
else
a[tail[remainder]] = &A[i];
tail[remainder] = i;
}
}
```
### Judge Girl 50129. Loops
```clike
int findLoop(int N, int *A, int index, int *B[], int *max, int *min, int visited[])
{
int start = *max = *min = A[index];
int i = index;
visited[index] = 1;
int length = 1;
while (*B[i] != start) {
i = B[i] - A;
visited[i] = 1;
if (A[i] > *max)
*max = A[i];
if (A[i] < *min)
*min = A[i];
length++;
}
return length;
}
void loops(int N, int *A, int *B[], int ans[4])
{
int visited[N];
for (int i = 0; i < N; i++)
visited[i] = 0;
int max, min;
int maxLength = 0;
int minLength = N + 1;
int maxMax, minMin;
for (int i = 0; i < N; i++)
if (visited[i] == 0) {
int length = findLoop(N, A, i, B, &max, &min, visited);
if (length > maxLength) {
maxLength = length;
maxMax = max;
} else if (length == maxLength && max > maxMax)
maxMax = max;
if (length < minLength) {
minLength = length;
minMin = min;
} else if (length == minLength && min < minMin)
minMin = min;
}
ans[0] = maxLength;
ans[1] = minLength;
ans[2] = maxMax;
ans[3] = minMin;
}
```
### Judge Girl 50090. Count Pointers
```clike
#include "count.h"
#include <stdlib.h>
#include <stdio.h>
#define MAXN 512
static int cmp_addr(const void *x, const void *y) {
int *a = *(int **) x, *b = *(int **) y;
if (a < b) return -1;
if (a == b) return 0;
return 1;
}
static int cmp_ret(const void *x, const void *y) {
int *a = (int *) x, *b = (int *) y;
if (a[1] != b[1])
return a[1] < b[1] ? -1 : 1;
return a[0] < b[0] ? -1 : 1;
}
void count(int **p[]) {
int *A[MAXN], n = 0;
for (; p[0]; p++)
A[n] = *p[0], n++;
qsort(A, n, sizeof(int*), cmp_addr);
int B[MAXN][2], m = 0;
for (int i = 0; i < n; ) {
int cnt = 0, j = i;
while (j < n && A[i] == A[j])
j++, cnt++;
B[m][0] = *A[i], B[m][1] = cnt, m++;
i = j;
}
qsort(B, m, sizeof(int)*2, cmp_ret);
for (int i = 0; i < m; i++)
printf("%d %d\n", B[i][0], B[i][1]);
}
```
### Judge Girl 50091. Two-level Table
```clike
#include <stdio.h>
#include <stdlib.h>
int **firstPtr[100];
int *secondPtr[1000000];
int ***constructTable(int A[], int B[]) {
int i = 0, j = 0, k = 0;
while (A[i] != 0) {
firstPtr[i] = &secondPtr[j];
for (int x = 0; x < A[i]; x++) {
secondPtr[j] = &B[k];
while (B[k] != 0)
k++;
k++;
j++;
}
secondPtr[j] = NULL;
j++;
i++;
}
firstPtr[i] = NULL;
return firstPtr;
}
```
Sign in with Wallet
Connect another wallet