Codeforces 簡單題系列 1
考慮一個不斷成長的數列：第 $1$ 回合的數列是 $S_1=[1]$，第 $n$ 回合做的事情是先把 $n$ 放進去再把剛才的數列照抄一次：$S_n = [S_{n-1}, n, S_{n-1}]$ 給你 $n$ 以及 $k$，請問第 $n$ 個數列的第 $k$ 項是多少？
不難發現前幾項是 $1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, \ldots$，所以答案就會是 $k$ 寫成二進位以後末尾 $0$ 的數量加一。實作上可以用 __builtin_ctzll() 來處理，要記得加上 ll 以免向隅。
// by tmt514
int main(void) {
long long n, k;
cin >> n >> k;
cout << 1 + __builtin_ctzll(k) << endl;
return 0;
}
有一天你寫了一個數字在黑板上，印象中你記得所有數字的總和 $\ge k$。當你離開座位一陣子了以後，卻發現你數字某些位數被擦掉改寫成 $n$ 了。請問無論如何，至少有幾個數字被擦掉了呢？$n\le 10^{100000}$、$k\le 10^9$。題目保證有解。
這題是 Greedy，你可以直接把所有 digit 排序，然後從最小的開始，依次把他改成 9，直到總和超過 $k$ 為止。
// by tmt514
int main(void) {
int k, ans = 0;
string n;
cin >> k >> n;
sort(n.begin(), n.end());
for(auto &&x: n) k -= x-'0';
for(auto &&x: n) if(k>0) { k -= '9'-x; ++ans; }
cout << ans << endl;
return 0;
}
Memory 想要從平面座標上的原點，經過一連串的指令以後回到原點。這串指令可以寫成一個字串 $s$，並且包含 L, R, U, D 四種字元分別代表向左、向右、向上、向下各走一單位距離。為了讓 Memory 能夠順利回到原點，請問至少要修改這個字串的幾個字元呢？如果無論如何都無法達成目標，請輸出 $-1$。$1\le |s|\le 10^5$。
首先我們可以知道，若字串長度是奇數鐵定無解。接著我們可以透過計算 L 和 R 的數量、計算 U 和 D 的數量來決定要修改幾個字元。
// by tmt514
int main(void) {
string s;
int LR=0, UD=0;
cin >> s;
for(auto &&x: s) {
if(x=='L' || x=='R') LR += (x=='L'?1:-1);
if(x=='U' || x=='D') UD += (x=='U'?1:-1);
}
LR = abs(LR);
UD = abs(UD);
if((LR+UD)%2) cout << -1 << endl;
else cout << (LR+UD)/2 << endl;
return 0;
}
Vasiliy 在一間療養院度過了他的假期，回來的時候幾乎忘了所有的細節了！
在療養院美一天都有早餐(breakfast)、晚餐(dinner) 以及宵夜(supper)。Vasiliy 只記得他吃過了 $b$ 餐早餐、$d$ 餐晚餐以及 $s$ 餐宵夜，但是他不記得他是在一天之中的什麼時候抵達、一天之中的什麼時候離開的。
現在給你 $b, d, s$ 的值，請問他在療養院的時候，至少錯過了幾餐？ （$0\le b, d, s\le 10^{18}$, $b+d+s\ge 1$）
本題有趣的地方在於，若 Vasiliy 沒有錯過任何一餐，那麼其敘述等價於 $\max(b, d, s) - \min(b, d, s) = 1$。所以只要找出三個數字最大的值，然後把其他兩個補足到至少該值減 $1$ 即可。
// by tmt514
int main(void) {
long long b, d, s;
cin >> b >> d >> s;
long long x = max(b, max(d, s));
long long c = max(0LL, (x-1)-b);
c += max(0LL, (x-1)-d);
c += max(0LL, (x-1)-s);
cout << c << endl;
return 0;
}