# EOJ Test Round #3 Solution

ultmaster edited 2 年，9 月前

### A. 天气猜猜看

for (int i = 0; i &lt; n; ++i) {
cin &gt;&gt; self; // for C++, use scanf("%s", self) for C
if (i &gt; 0 &amp;&amp; self != last) {
if (last == "UP") ans[i-1] = 30;
else if (last == "DOWN") ans[i-1] = 0;
start = ans[i-1];
}
if (self == "UP")
start += 0.1;
else start -= 0.1;
ans[i] = start;
last = self;
}


### B. 寻找图书馆

#### 70 分解法

int ans = 120000; // 一个很大的数
for (int i = 0; i &lt; m; ++i)
ans = min(ans, abs(x[i] - qr));
printf("%d\n", ans);


#### 100 分解法

x[m++] = -1000000; //读完图书馆位置后加一个边界，防止输出答案时r-1越界

// 使用 qsort/sort 排序（略）

int l = 0, r = m - 1; //二分
while (l &lt; r) {
int mid = (l + r) / 2;
if (x[mid] &lt; qr) l = mid + 1;
else r = mid;
}
printf("%d\n", min(abs(x[r - 1] - qr), abs(x[r] - qr)));


### C. 很大很大的数

int check(ll x) {
int res = 0;
while (x) {
int i = x % 10;
if (i == 0 || i == 1)
res++;
x /= 10;
}
return res;
}
while (check(n) != x) n--;


def solve(n, x):
ans = dfs(str(n), x, 0, True, 0, '')
if ans is None:
length = len(str(n)) - 1
while length &gt; 0:
ans = dfs('9' * length, x, 0, False, 0, '')
if ans is not None:
break
length -= 1
return int(ans)

def dfs(s, x, u, lim, siz, cur):
# Limit is True means it is still limited
# print(cur)
if siz &gt; x:
return None
if len(s) - u &lt; x - siz:
return None
if u == len(s):
if siz == x:
# print(x, u, lim, siz)
return ''
return None
start = int(s[u]) if lim else 9
ed = 0 if u == 0 else -1
for i in range(start, ed, -1):
# print(u, i)
append = 1 if 0 &lt;= i &lt;= 1 else 0
if i != start or not lim:
new_ans = dfs(s, x, u + 1, False, siz + append, cur + str(i))
if new_ans is not None:
return str(i) + new_ans
else:
new_ans = dfs(s, x, u + 1, True, siz + append, cur + str(i))
if new_ans is not None:
return str(i) + new_ans
return None


### D. 相似的句子

int judge() {
if (k1 != k2) return 0;
for (int i = 0; i &lt; k1; ++i)
if (s1[i] != s2[i]) return 0;    // use strcmp for C
return 1;
}

sort(s1, s1 + k1);    // use qsort for C
sort(s2, s2 + k2);
printf("Case %d: %s\n", kase, judge() ? "YES" : "NO");