Zerojudge第二屆簡單的小競賽題解
第二次舉辦簡單的小競賽，感覺有點難，但對某些人來說應該算很簡單的，有 $4$ 題流程題和 $12$ 題競賽題，競賽題有下半場和上半場。
A：簽到 (Zerojudge_f026不公開)
題目：輸出 $\text{Checked!!!}$
解法：直接輸出。
B：規則說明 (Zerojudge_f027不公開)
題目：輸入帳密，輸出帳密。
解法：輸出帳密。
1-1：Say HELLO! (Zerojudge_e412練習題)
題目：輸入姓名，輸出姓名。
解法：輸出姓名，輸入記得要讀取整行。
1-2：行不行 (Zerojudge_f028練習題)
題目：輸入姓名、分數，問行不行。
解法：輸出姓名，若分數 $≥60$，輸出 $\text{Yes}$，否則輸出 $\text{No}$。
1-3：OREOREO! (Zerojudge_e698)
題目：輸入餅乾、餅乾餡、餅乾寬、高，輸出餅乾。
解法：讀取字串，輸出餅乾。
1-4：奇怪的隕石(Zerojudge_e990)
題目：給你隕石半衰期 $T$，問過多久變 $n$ 倍。
解法：可得公式 $-T\times log_2(n)$。
1-5：S形的矩陣 (Zerojudge_f034練習題)
題目：給你 $n$，輸出 $n\times n$ 的 $S$ 形的矩陣。
解法：輸出。
1-6：Caidocraft的構造改革！(Zerojudge_f010)
題目：給你一些指令，有些要輸出，詳情請見上方連結。
解法：測資不是很大，直接循序搜索就好了，$\text{Code}$ 有點亂。
C：中場休息 (Zerojudge_f029不公開)
題目：輸出最後吃多飽。
解法：一直加直到 $\text{EOF}$。
2-1：測量速度 (Zerojudge_f030練習題)
題目：輸入姓名，$n$ 秒 $k$ 個字，輸出多快。
解法：輸出 $k/n$。
2-2：0、1 (Zerojudge_f031練習題)
題目：輸入 $0、1$，輸出 $\text{White、Black}$。
解法：判斷是 $0$ 還是 $1$。
2-3：巴尾萊鳥 (Zerojudge_f011)
題目：輸入 $n$ 次方程式、切點，求切線與 $X$ 軸交點。
解法： 斜率 $=dy/dx$，對 $n$ 次方程式微分可求得斜率，切線:$y-b=m(x-a)$，將 $(s,0)$ 代 入，$0-b=m(s-a)$，$s=-b/m+a$。 但若 $m=0$，會與 $X$ 軸平行，此時判斷 $b$ 是否等於 $0$。
2-4：奶油機器人 (Zerojudge_f012)
題目：機器人在白色平面由 $(0,0)$ 出發，所在的格子為白色時，使得格子變成黑色，並向右轉 $90$ 度，前進一格；所在的格子為黑色時，使得格子變成白色，並向左轉 $90$ 度，前進一格。
解法：由維基百科可知，在 $10000$ 多格後會 $104$ 個一循環，所以 $n$ 取 $15000$，只需存前 $15000$ 格，和循環的 $104$ 格，若大於 $15000$ 時，加上去即可。
2-5：費の數列 (Zerojudge_f032練習題)
題目：求費氏數列第 $n$ 項 $(n≤10000)$。
解法：一開始先存好，輸入時直接輸出就好了。
2-6：N項的費氏數列 (Zerojudge_f013)
題目：求 $n$ 項費氏數列的第 $k$ 項 $(k<=2^{50})$
解法：都沒人解出這題，要不然就是直接算 $33\%$，或矩陣快速冪 $67\%$，其實是要先判斷哪一種做法比較快，因為矩陣快速冪在乘的時間會用到 $n^3$，$k$ 小時就很耗時間。
我有想過用 $queue$，但都差不多快。
D：離場 (Zerojudge_f033不公開)
題目：給你一些物品，判斷有多少個。
解法：累加到 $\text{EOF}$。
我的分享就到這裡結束了，如果喜歡我的 $\text{Blog}，歡迎追蹤！
A：簽到 (Zerojudge_f026不公開)
題目：輸出 $\text{Checked!!!}$
解法：直接輸出。
#pragma GCC optimize("O3")
#include <iostream>
using namespace std;
int main() {
cout << "Checked!!!\n";
}
B：規則說明 (Zerojudge_f027不公開)
題目：輸入帳密，輸出帳密。
解法：輸出帳密。
#pragma GCC optimize("O3")
#include <iostream>
using namespace std;
int main() {
char ac[21], ps[21];
scanf ("Account:%s\n", ac);
scanf ("Password:%s", ps);
printf ("%s\n%s\nLog in\n", ac, ps);
}
1-1：Say HELLO! (Zerojudge_e412練習題)
題目：輸入姓名，輸出姓名。
解法：輸出姓名，輸入記得要讀取整行。
#pragma GCC optimize("O3")
#include <iostream>
using namespace std;
int main() {
string str;
while (getline (cin, str))
cout << "HELLO," << str << '\n';
}
1-2：行不行 (Zerojudge_f028練習題)
題目：輸入姓名、分數，問行不行。
解法：輸出姓名，若分數 $≥60$，輸出 $\text{Yes}$，否則輸出 $\text{No}$。
#pragma GCC optimize("O3")
#include <iostream>
using namespace std;
int main() {
string str;
int n;
while (cin >> str >> n)
cout << str << ':' << (n >= 60 ? "Yes\n" : "No\n");
}
1-3：OREOREO! (Zerojudge_e698)
題目：輸入餅乾、餅乾餡、餅乾寬、高，輸出餅乾。
解法：讀取字串，輸出餅乾。
#pragma GCC optimize("O3")
#include <iostream>
using namespace std;
int on, oh, ren, reh;
char o, re;
void fo() {
if (on >= ren)
for (int i = 0; i < oh; i++)
cout << string (on, o) << '\n';
else
for (int i = 0; i < oh; i++)
cout << string ( (ren - on) / 2, ' ') << string (on, o) << '\n';
}
void reo() {
if (on <= ren)
for (int i = 0; i < reh; i++)
cout << string (ren, re) << '\n';
else
for (int i = 0; i < reh; i++)
cout << string ( (on - ren) / 2, ' ') << string (ren, re) << '\n';
}
int main() {
while (cin >> on >> oh >> ren >> reh) {
cin >> o >> re;
int t;
cin >> t;
while (t--) {
string str;
cin >> str;
for (int i = 0; i < str.length(); i++) {
if (str[i] == 'O')
fo();
else
i++, reo();
}
cout << '\n';
}
}
}
1-4：奇怪的隕石(Zerojudge_e990)
題目：給你隕石半衰期 $T$，問過多久變 $n$ 倍。
解法：可得公式 $-T\times log_2(n)$。
#pragma GCC optimize("O3")
#include <iostream>
#include <cmath>
#include <iomanip>
using namespace std;
int main() {
double T, n;
while (cin >> T >> n)
cout << fixed << setprecision (3) << -T*log2 (n) << '\n';
}
1-5：S形的矩陣 (Zerojudge_f034練習題)
題目：給你 $n$，輸出 $n\times n$ 的 $S$ 形的矩陣。
解法：輸出。
#pragma GCC optimize("O3")
#include <stdio.h>
int main() {
int n;
while (~scanf ("%d", &n)) {
for (int i = 0; i < n; i++) {
if (i % 2 == 0)
for (int j = 0; j < n; j++)
printf ("%d ", i * n + j + 1);
else
for (int j = n - 1; j >= 0; j--)
printf ("%d ", i * n + j + 1);
printf ("\n");
}
printf ("\n");
}
}
1-6：Caidocraft的構造改革！(Zerojudge_f010)
題目：給你一些指令，有些要輸出，詳情請見上方連結。
解法：測資不是很大，直接循序搜索就好了，$\text{Code}$ 有點亂。
#pragma GCC optimize("O3")
#include <iostream>
#include <map>
#include <vector>
#include <sstream>
#define f first
#define s second
#define x first
#define y second
using namespace std;
int hp, sat, walk, run;
pair<int, int>At, re;
map<string, int>food;
map<string, int>monster;
vector<pair<string, int> >backpack;
map<pair<int, int>, vector<pair<string, int> > >fall;
void init() {
hp = sat = 10, At.x = At.y = re.x = re.y = walk = run = 0;
}
int find_string (vector<pair<string, int> >vec, string str) {
for (int i = 0; i < vec.size(); i++)
if (vec[i].f == str)
return i;
return -1;
}
void die() {
for (int i = 0; i < backpack.size(); i++) {
int fi = find_string (fall[At], backpack[i].f);
if (fi == -1)
fall[At].push_back (backpack[i]);
else
fall[At][fi].s += backpack[i].s;
}
At = re, hp = sat = 10;
backpack.clear();
}
void suck() {
if (fall.count (At)) {
for (int i = 0; i < fall[At].size(); i++) {
int fi = find_string (backpack, fall[At][i].f);
if (fi == -1)
backpack.push_back (fall[At][i]);
else
backpack[fi].s += fall[At][i].s;
}
fall.erase (fall.find (At));
}
}
void sleep() {
re = At;
}
void create_monster (string str, int n) {
monster[str] = n;
}
void attacked (string str) {
hp -= monster[str];
if (hp <= 0)
die();
}
void pick (string str, int n) {
int fi = find_string (backpack, str);
if (fi == -1)
backpack.push_back ({str, n});
else
backpack[fi].s += n;
}
void turn() {
if (sat <= 10)
return;
int more = sat - 10;
sat = 10;
more /= 2;
hp += more;
if (hp > 10)
hp = 10;
}
void eat (string str, int n) {
int fi = find_string (backpack, str);
backpack[fi].s -= n;
if (backpack[fi].s == 0)
backpack.erase (backpack.begin() + fi);
sat += food[str] * n;
turn();
}
void Walk (string to, int n) {
int de;
walk += n, de = walk / 50, walk %= 50;
sat -= de;
if (sat <= 0)
die();
else {
if (to == "East")
At.x += n;
else if (to == "West")
At.x -= n;
else if (to == "North")
At.y += n;
else if (to == "South")
At.y -= n;
suck();
}
}
void Run (string to, int n) {
int de;
run += n, de = run / 25, run %= 25;
sat -= de;
if (sat <= 0)
die();
else {
if (to == "East")
At.x += n;
else if (to == "West")
At.x -= n;
else if (to == "North")
At.y += n;
else if (to == "South")
At.y -= n;
suck();
}
}
void think (string strr) {
stringstream ss;
ss << strr;
string str;
ss >> str;
if (str == "Walk") {
string to;
int n;
ss >> to >> n;
Walk (to, n);
return;
}
if (str == "Run") {
string to;
int n;
ss >> to >> n;
Run (to, n);
return;
}
if (str == "Sleep") {
sleep();
return;
}
if (str == "Create") {
string name;
int n;
ss >> name >> n;
create_monster (name, n);
return;
}
if (str == "Attacked") {
string name;
ss >> name >> name;
attacked (name);
return;
}
if (str == "Pick") {
string thing, test;
int n;
ss >> thing >> n;
ss >> test;
if (! (test[0] >= '0' && test[0] <= '9')) {
int fi = find_string (backpack, thing);
if (fi == -1)
backpack.push_back ({thing, n});
else
backpack[fi].s += n;
} else {
backpack.push_back ({thing, n});
int mo = 0;
for (int i = 0; i < test.length(); i++)
mo = mo * 10 + test[i] - '0';
food[thing] = mo;
}
return;
}
if (str == "Eat") {
string fo;
int n;
ss >> fo >> n;
eat (fo, n);
return;
}
if (str == "Print") {
string dd;
ss >> dd;
if (dd == "HP")
cout << "HP:" << hp << '\n';
else if (dd == "SAT")
cout << "SAT:" << sat << '\n';
else if (dd == "At")
cout << "At:(" << At.x << ',' << At.y << ")\n";
else {
cout << "Backpack:\n";
for (int i = 0; i < backpack.size(); i++)
cout << backpack[i].f << ' ' << backpack[i].s << '\n';
}
}
}
int main() {
init();
string str;
while (getline (cin, str)) {
think (str);
}
}
C：中場休息 (Zerojudge_f029不公開)
題目：輸出最後吃多飽。
解法：一直加直到 $\text{EOF}$。
#pragma GCC optimize("O3")
#include <iostream>
using namespace std;
int main() {
int sum = 0, n;
while (cin >> n)
sum += n;
cout << sum << '\n';
}
2-1：測量速度 (Zerojudge_f030練習題)
題目：輸入姓名，$n$ 秒 $k$ 個字，輸出多快。
解法：輸出 $k/n$。
#pragma GCC optimize("O3")
#include <iostream>
#include <iomanip>
using namespace std;
int main() {
string str;
double s, k;
while (cin >> str >> s >> k)
cout << str << ':' << fixed << setprecision (3) << k / s << '\n';
}
2-2：0、1 (Zerojudge_f031練習題)
題目：輸入 $0、1$，輸出 $\text{White、Black}$。
解法：判斷是 $0$ 還是 $1$。
#pragma GCC optimize("O3")
#include <iostream>
#include <iomanip>
using namespace std;
int main() {
bool b;
while (cin >> b)
cout << (b == 0 ? "White\n" : "Black\n");
}
2-3：巴尾萊鳥 (Zerojudge_f011)
題目：輸入 $n$ 次方程式、切點，求切線與 $X$ 軸交點。
解法： 斜率 $=dy/dx$，對 $n$ 次方程式微分可求得斜率，切線:$y-b=m(x-a)$，將 $(s,0)$ 代 入，$0-b=m(s-a)$，$s=-b/m+a$。 但若 $m=0$，會與 $X$ 軸平行，此時判斷 $b$ 是否等於 $0$。
#pragma GCC optimize("O3")
#include <iostream>
#include <iomanip>
using namespace std;
double dpow (double n, int p) {
if (p == 0)
return 1;
double re = 1;
for (int i = 1; i <= p; i++)
re *= n;
return re;
}
int main() {
int t;
cin >> t;
while (t--) {
int n;
double a, b = 0, m = 0;
cin >> n;
int c[n + 1];
for (int i = 0; i <= n; i++)
cin >> c[i];
cin >> a;
for (int i = 0; i <= n; i++)
b += dpow (a, n - i) * c[i];
for (int i = 0; i < n; i++)
m += dpow (a, n - i - 1) * c[i] * (n - i);
if (m == 0 && b == 0)
cout << "It can sleep everywhere!\n";
else if (m == 0)
cout << "It cannot sleep!\n";
else
cout << '(' << fixed << setprecision (3) << -b / m + a << ",0)\n";
}
}
2-4：奶油機器人 (Zerojudge_f012)
題目：機器人在白色平面由 $(0,0)$ 出發，所在的格子為白色時，使得格子變成黑色，並向右轉 $90$ 度，前進一格；所在的格子為黑色時，使得格子變成白色，並向左轉 $90$ 度，前進一格。
解法：由維基百科可知，在 $10000$ 多格後會 $104$ 個一循環，所以 $n$ 取 $15000$，只需存前 $15000$ 格，和循環的 $104$ 格，若大於 $15000$ 時，加上去即可。
#pragma GCC optimize("O3")
#include <iostream>
#include <map>
#define x first
#define y second
using namespace std;
int dic = 0;
map<pair<int, int>, bool>color;
pair<int, int>ans[15001], at, cir[105];
void turn_go (bool bo) {
if (bo == 1)
dic = (dic + 1) % 4;
else if (dic == 0)
dic = 3;
else
dic--;
if (dic == 0)
at.y++;
else if (dic == 1)
at.x++;
else if (dic == 2)
at.y--;
else if (dic == 3)
at.x--;
}
void init() {
for (int i = 1; i <= 15000; i++) {
if (color[at] == 0) {
color[at] = 1;
turn_go (1);
ans[i] = at;
} else {
color[at] = 0;
turn_go (0);
ans[i] = at;
}
}
for (int i = 1; i <= 104; i++) {
if (color[at] == 0) {
color[at] = 1;
turn_go (1);
cir[i] = at;
} else {
color[at] = 0;
turn_go (0);
cir[i] = at;
}
}
}
int main() {
init();
long long n;
while (cin >> n) {
if (n <= 15000)
cout << '(' << ans[n].x << ',' << ans[n].y << ")\n";
else {
n -= 15000;
long long mod = n % 104, div = n / 104;
if (mod == 0)
div--, mod = 104;
cout << '(' << (long long) cir[mod].x - 2 * div << ',' << (long long) cir[mod].y - 2 * div << ")\n";
}
}
}
2-5：費の數列 (Zerojudge_f032練習題)
題目：求費氏數列第 $n$ 項 $(n≤10000)$。
解法：一開始先存好，輸入時直接輸出就好了。
#pragma GCC optimize("O3")
#include <iostream>
#include <iomanip>
using namespace std;
int main() {
int f[10001], k;
f[1] = f[2] = 1;
for (int i = 3; i <= 10000; i++)
f[i] = (f[i - 1] + f[i - 2]) % 10007;
while (cin >> k)
cout << f[k] << '\n';
}
2-6：N項的費氏數列 (Zerojudge_f013)
題目：求 $n$ 項費氏數列的第 $k$ 項 $(k<=2^{50})$
解法：都沒人解出這題，要不然就是直接算 $33\%$，或矩陣快速冪 $67\%$，其實是要先判斷哪一種做法比較快，因為矩陣快速冪在乘的時間會用到 $n^3$，$k$ 小時就很耗時間。
我有想過用 $queue$，但都差不多快。
#pragma GCC optimize("O3")
#include <iostream>
#define mod 1000000007
#define ll long long
using namespace std;
int t, n, ans[30][30], mult[30][30];
ll k;
void init() {
for (int i = 0; i < n; i++)
mult[0][i] = ans[0][i] = 1;
for (int i = 1; i < n; i++)
for (int j = 0; j < n; j++)
mult[i][j] = ans[i][j] = (i - 1 == j ? 1 : 0);
}
bool faster() {
ll zero = (k - n) * n, one, bit = 0, m = k - n - 1;
while (m)
bit += ( (m & 1) ? 2 : 1), m >>= 1;
one = n * n * n * bit;
if (zero <= one)
return 0;
return 1;
}
void solve0() {
int dp[n];
ll now = n;
for (int i = 0; i < n; i++)
dp[i] = 1;
for (ll i = n; i < k; i++) {
ll sum = (2 * now - dp[0]) % mod;
if (sum < 0)
sum += mod;
for (int j = 0; j < n - 1; j++)
dp[j] = dp[j + 1];
dp[n - 1] = now;
now = sum;
}
cout << dp[n - 1] << '\n';
}
void mult_mult() {
int arr[n][n];
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
arr[i][j] = mult[i][j];
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++) {
mult[i][j] = 0;
for (int k = 0; k < n; k++)
mult[i][j] = ( (ll) arr[i][k] * arr[k][j] + mult[i][j]) % mod;
}
}
void ans_mult() {
int arr[n][n];
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
arr[i][j] = ans[i][j];
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++) {
ans[i][j] = 0;
for (int k = 0; k < n; k++)
ans[i][j] = ( (ll) mult[i][k] * arr[k][j] + ans[i][j]) % mod;
}
}
void solve1() {
ll m = k - n - 1, sum = 0;
while (m) {
if (m & 1)
ans_mult();
mult_mult();
m >>= 1;
}
for (int i = 0; i < n; i++)
sum = (sum + ans[0][i]) % mod;
cout << sum << '\n';
}
void solve() {
cin >> n >> k;
if (k <= n) {
cout << "1\n";
return;
}
init();
if (faster() == 0)
solve0();
else
solve1();
}
int main() {
cin >> t;
while (t--)
solve();
}
D：離場 (Zerojudge_f033不公開)
題目：給你一些物品，判斷有多少個。
解法：累加到 $\text{EOF}$。
#pragma GCC optimize("O3")
#include <iostream>
#include <iomanip>
using namespace std;
int main() {
string str;
int n = 0;
while (cin >> str)
n++;
cout << n << '\n';
}
我的分享就到這裡結束了，如果喜歡我的 $\text{Blog}，歡迎追蹤！
留言
張貼留言