1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
|
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>
typedef struct dir Dir;
#define LOG(s) fprintf(stderr, s"\n");
struct dir {
char name[32];
Dir *parent;
Dir *next_sibling;
Dir *child;
int size;
};
char buf[4096];
Dir root = {0};
int need = INT_MAX;
int to_del = INT_MAX;
int totalsize(Dir *dir) {
if (dir == NULL) return 0;
int total = dir->size;
Dir *child = dir->child;
while (child != NULL) {
total += totalsize(child);
child = child->next_sibling;
}
if (total >= need && total < to_del) to_del = total;
return total;
}
void process_ls(FILE* fp, Dir *cur) {
while (1) {
int c = fgetc(fp);
if (c == EOF) return;
ungetc(c, fp);
if (c == '$') {
return;
}
buf[0] = '\0';
fgets(buf, 4096, fp);
if (buf[0] == 'd') {
strtok(buf, " ");
char *childname = strtok(NULL, "\n");
Dir *newdir = malloc(sizeof(Dir));
strcpy(newdir->name, childname);
newdir->parent = cur;
newdir->next_sibling = cur->child;
newdir->child = NULL;
newdir->size = 0;
cur->child = newdir;
} else {
char *pos;
long fsz = strtol(buf, &pos, 10);
cur->size += fsz;
}
}
}
void process_cmd(FILE *fp, Dir **pcur) {
Dir *cur = *pcur;
char *cmd = strtok(buf + 2, " \n");
if (strcmp(cmd, "cd") == 0) {
char *param = strtok(NULL, " \n");
if (strcmp(param, "/") == 0) {
*pcur = &root;
} else if (strcmp(param, "..") == 0) {
*pcur = cur->parent;
} else {
Dir *t = cur->child;
while (t != NULL) {
if (strcmp(t->name, param) == 0) {
*pcur = t;
break;
} else {
t = t->next_sibling;
}
}
}
} else if (strcmp(cmd, "ls") == 0) {
process_ls(fp, cur);
}
}
int main() {
FILE *fp = fopen("input", "r");
Dir *cur = &root;
while (fgets(buf, 4096, fp)) {
int len = strlen(buf);
if (len <= 1) continue;
char c = buf[0];
if (c == '$') {
process_cmd(fp, &cur);
}
}
int total = totalsize(&root);
int unused = 70000000 - total;
need = 30000000 - unused;
totalsize(&root);
printf("%d\n", to_del);
}
|
