2021.11 月赛题解

A-无限的路

C-Catch that cow

E-Red and black

G-World cup

H-z-sort

J-Table tennis

A.

题目：

众所周知，wy学姐心灵手巧，她最近在学习原画，立志往国风和赛博朋克风格发展。

绘画的工具是很重要哒！

于是思量再三+长期吃土后，她买了一支biulingbiuling~闪的魔法棒画笔，由于刚刚接触，wy学姐还没有领悟到其中的奥秘所在，她只会以普通画笔的方式去使用它。

wy学姐决定用它来练习画直线，于是她在平面直角坐标系中画出了如下的图形：

善于思考的wy学姐发现！她随手一画的图竟然是有点规则的！！OMG！！！

于是她决定考考你是否也发现了这个神奇美妙的规则，是否感悟到了数学的诱人的魅力和本质？

wy学姐会随机给出两个点，要求你算出连接两点的折线长度（即沿折线走的路线长度）。

Input

第一个数是正整数N（≤100）。代表数据的组数。
每组数据由四个非负整数组成x1，y1，x2，y2；所有的数都不会大于100。

Output

对于每组数据，输出两点(x1,y1),(x2,y2)之间的折线距离。注意输出结果精确到小数点后3位。

Sample Input

5 0 0 0 1 0 0 1 0 2 3 3 1 99 99 9 9 5 5 5 5

Sample Output

1.000 2.414 10.646 54985.047 0.000

思路：将斜线分为两类，一类是sqrt(x^2+(x+1)^2)，另一类为sqrt(x^2 + x^2)，再根据坐标，可以发现两点之间距离实际上是每个点到(0,0)距离的绝对值。因此只要算两个点距离原点的距离差。再根据图形，结合坐标可得出答案。

#include<iostream>

#include<math.h>

using namespace std;

int main()

{

int N, i, j, t, x, y;

double d1, d2, d3;

int a[5] = { 0 };

while (cin >> N)

{

for (i = 0; i < N; i++)

{

for(t = 0; t < 4; t++)

cin >> a[t];

d1 = d2 = d3 = 0;

x = a[0] + a[1];

y = a[2] + a[3];

for (j = 1; j < x; j++)

{

d1 += sqrt(pow(j, 2) + pow(j, 2));

}

d1 += sqrt(2) * a[0];

for (j = 1; j <= x; j++)

{

d1 += sqrt(pow(j, 2) + pow((j - 1), 2));

}

for (j = 1; j < y; j++)

{

d2 += sqrt(pow(j, 2) + pow(j, 2));

}

for (j = 1; j <= y; j++)

{

d2 += sqrt(pow(j, 2) + pow((j - 1), 2));

}

d2 += sqrt(2) * a[2];

d3 = fabs(d2 - d1);

printf("%.3lfn", d3);

}

}

return 0;

}

C.

题目：

众所周知，yh学长 is very rich，他靠着玩超级大富翁的游戏富上加富，买下了地球的半座江山（另外半座他不想要啦！）。

Of course，yh学长啥都有，这其中当然也包括养猪场。

这天，yh学长正在养猪场里跟它们一起玩，他心血来潮点了个到：“花花、茉莉、小爱、仙子……？？？仙子呢？！Where are my dear Xianzi？？？！！！”
yh学长忽然发现名为“仙子”的小粉猪不见了！Oh no！这可是他最心爱的一头猪！！！
幸好yh学长在每只猪的身上都安装了高级GPS定位导航，通过智能腕表，他可以实时知道“仙子”的位置。

yh学长从一条直线上的一个点N (0 ≤ N ≤ 100,000) 开始，“仙子”在同一直线上的一个点K (0 ≤ K ≤ 100,000) 上。

yh学长迫不及待地想把“仙子”带回来，他决定现在就出发去找它。
可是作为一个 richer ，可选择的交通方式实在是太多了，到底要用什么交通方式去找呢？
yh学长想起“仙子”最爱的两个交通工具—— 南瓜老年代步车 以及 超级无敌霹雳豪华完美小巧简易宇宙飞船。

南瓜老年代步车南瓜老年代步车——yh学长可以在一分钟内从任何一点X移动到X-1或X+1两点。
超级无敌霹雳豪华完美小巧简易宇宙飞船超级无敌霹雳豪华完美小巧简易宇宙飞船——yh学长可以在一分钟内从任何X点移动到2*X点。

已知“仙子”在离家出走一段时间后就反悔了，
十分地想念yh学长（这就是双向奔赴吗(Ｔ▽Ｔ)磕到了磕到了ヾ(◍°∇°◍)ﾉﾞ），
但它太累了，于是决定在原地不动等yh学长来找它。

请问yh学长至少需要多长时间才能把它找回来？

Input

第一行输入两个整数 N 和 K

Output

输出一个整数——yh学长至少花多长时间才能把“仙子”找回来？

Sample Input

5 17

Sample Output

4

Hint

yh学长到达“仙子”所在地的最快方法是沿着以下路径移动：5-10-9-18-17，这需要4分钟。

思路：利用BFS算法得出最小时间。

#include<iostream>

#include<queue>

using namespace std;

int a[100005] = { 0 };

int time1[100005] = { 0 };

int flag[100005] = { 0 };

int main()

{

int n, k;

int x0, x1;

cin >> n >> k;

queue<int>q1;

q1.push(n);

time1[n] = 0;

if (n < k)

{

while (!q1.empty())

{

x0 = q1.front();

q1.pop();

for (int i = 0; i < 3; i++)

{

if (i == 0)

{

if (x0 >= 1)

{

x1 = x0 - 1;

if (x1 >= 0 && x1 <= 100005)

{

if (flag[x1] == 0)

{

q1.push(x1);

flag[x1] = 1;

time1[x1] = time1[x0] + 1;

}

if (x1 == k)

{

cout << time1[x1];

return 0;

}

}

}

}

if (i == 1)

{

x1 = x0 + 1;

if (x1 >= 0 && x1 <= 100005)

{

if (flag[x1] == 0)

{

q1.push(x1);

flag[x1] = 1;

time1[x1] = time1[x0] + 1;

}

if (x1 == k)

{

cout << time1[x1];

return 0;

}

}

}

if (i == 2)

{

x1 = x0 * 2;

if (x1 >= 0 && x1 <= 100005)

{

if (flag[x1] == 0)

{

q1.push(x1);

flag[x1] = 1;

time1[x1] = time1[x0] + 1;

}

if (x1 == k)

{

cout << time1[x1];

return 0;

}

}

}

}

}

}

else if (n >= k )

cout << abs(n - k);

return 0;

}

E.

题目：

zks会长梦见一片充满宝藏的沙滩, 它是由若干正方形的块状土地组成的一个W*H矩形区域。zks会长决定挖出这片沙滩所有的宝藏，成为传说中的宝藏男孩！！！

不幸的是，在他挖第二块地时就触发了埋藏其中的地雷，他直接被从宿舍的床上炸醒。
他恍然大悟，原来这片沙滩上的每一块地，除了宝藏，还有可能是地雷！

故事没有就这样结束，第二天，他又做了相同的梦...

编写一个程序，计算出zks会长在被炸醒前可能挖到宝藏的最大数量。

Input

输入包含多组数据. 每组数据包含两个正整数W和H.

H表示列数，W表示行数. W和H不超过20.

每块地用字符表示如下:

'.' - 宝藏
'#' - 地雷
'@' - 起点（每组数据中只有一个，下面也有宝藏!）
输入 0 0 时程序结束

Output

对于每组数据，输出一个整数，即zks会长能挖到宝藏的最大数量。

Sample Input

6 9 ....#. .....# ...... ...... ...... ...... ...... #@...# .#..#. 11 9 .#......... .#.#######. .#.#.....#. .#.#.###.#. .#.#..@#.#. .#.#####.#. .#.......#. .#########. ........... 11 6 ..#..#..#.. ..#..#..#.. ..#..#..### ..#..#..#@. ..#..#..#.. ..#..#..#.. 7 7 ..#.#.. ..#.#.. ###.### ...@... ###.### ..#.#.. ..#.#.. 0 0

Sample Output

45 59 6 13

思路：利用dfs算法，将起点的上下左右都尝试一遍，再以此用新的坐标作为新的起点进行递归，从而得出答案。

#include<iostream>

#include<queue>

using namespace std;

int W, H, i, j;

int x, y;

int sum = 0;

char map[200][200];

void dfs(int x, int y)

{

for (int i = 0; i < 4; i++)

{

if (i == 0)

{

if (y - 1 >= 1)

{

if (map[x][y - 1] == '.')

{

map[x][y - 1] = '#';

sum++;

dfs(x, y - 1);

}

}

}

if (i == 1)

{

if (y + 1 <= H)

{

if (map[x][y + 1] == '.')

{

map[x][y + 1] = '#';

sum++;

dfs(x, y + 1);

}

}

}

if (i == 2)

{

if (x - 1 >= 1)

{

if (map[x - 1][y] == '.')

{

map[x - 1][y] = '#';

sum++;

dfs(x - 1, y);

}

}

}

if (i == 3)

{

if (x + 1 <= W)

{

if (map[x + 1][y] == '.')

{

map[x + 1][y] = '#';

sum++;

dfs(x + 1, y);

}

}

}

}

}

int main()

{

while (cin >> H >> W)

{

if (H == 0 && W == 0)

{

continue;

}

else

{

x = y = 0;

sum = 0;

for (i = 1; i <= W; i++)

{

for (j = 1; j <= H; j++)

{

map[i][j] = ' ';

cin >> map[i][j];

if (map[i][j] == '@')

{

x = i;

y = j;

}

}

}

dfs(x, y);

cout << sum + 1 << endl;

}

}

return 0;

}

G.

题目：

协会正在举行一场对外的加时赛，在这场比赛中有n个小队，依次从1到n进行编号。

每一轮比赛后剩下小队的ID会重新按照顺序依次编号，然后按以下顺序进行比赛：第一队和第二队比，第三队和第四队比，依此类推。

可以保证在每一轮比赛中都有偶数个队。
每场比赛的获胜者晋级下一轮，失败者被淘汰出局，没有平局。

在最后一轮比赛中，只剩下两支小队，这一轮被称为决赛，获胜者被称作冠军。

大家都希望lh学长带领的小队和hz学长带领的小队进入决赛。
不幸的是，球队ID已经被确定了，lh学长和hz学长可能不会在决赛中相遇，因为如果他们足够强大，他们将在更早的阶段相遇。

请你预测一下，lh学长所在的ID为a和hz学长所在的ID为b的小队将会在哪一轮中碰面。

注意：lh学长的小队和hz学长的小队是所有小队中最强的存在！！！

Input

唯一的行包含三个整数n，a和b (2≤n≤256，1≤a，b≤n) 分别为参加比赛的小队总数，lh学长所带领的小队编号，hz学长所带领的小队编号。

可以保证，在每一轮比赛中，都有偶数个队晋级，并且a和b不相等。

Output

如果lh学长和hz学长可以在决赛中相遇，则输出唯一一行“Final!”（没有引号）

否则输出lh学长和hz学长相遇的轮数。

轮数是从1开始累计的。

Examples

Input

4 1 2

Output

1

Input

8 2 6

Output

Final!

Input

8 7 5

Output

2

Note

在第一个例子中，lh学长所在的1队和hz学长所在的2队在第1轮相遇。

在第二个例子中，lh学长所在的2队和hz学长所在的6队只可能在第3轮决赛时相遇（他们战胜了之前的所有对手）。

在第三个例子中，lh学长所在的7队和hz学长所在的5队可以在第2轮相遇（他们都在第1轮中赢得了对手）。

思路：将每一队进行编号，并模拟每一轮比赛，即将题目中学长所在的两队的对手全部淘汰，其他队伍比赛中只要随便淘汰其中一个，如果两队相遇直接输出，并在此做标记，如果最后发现没有标记，则说明两队在最终才相遇。

#include<iostream>

#include<algorithm>

using namespace std;

int t(int n)

{

int sum;

sum = 0;

while (n != 1)

{

n /= 2;

sum++;

}

return sum;

}

int main()

{

int n, a, b, i, j, x, time, flag,s;

while (cin >> n >> a >> b)

{

int c[260] = { 0 };

time = 1;

flag = 0;

x = 1;

s = 0;

for (i = 1; i <= n; i++)

c[i] = i;

for (i = 1; i <= t(n); i++)

{

s = 0;

for (j = 1; j <= n; j++)

{

x = 1;

if (c[j] > 0 && j != s)

{

while (c[j + x] == 0)

x++;

s = j + x;

if (j == a && j + x == b || j == b && j + x == a)

{

if (time != t(n))

{

cout << time << endl;

flag = 1;

return 0;

}

}

if (j == a || j == b)

c[j + x] = 0;

else if (j + x == a || j + x == b)

c[j] = 0;

else if (j != a && j != b && j + x != a && j + x != b)

c[j] = 0;

}

}

time++;

}

if (flag == 0)

cout << "Final!" << endl;

}

return 0;

}

H.

题目：

z-sort过的数组是这样的

[1,2,1,2] 和[1,1,1,1] 是z-sort过的  但是[1,2,3,4] 不是

lh学长将会给你一个数组，希望你可以帮他弄成z-sort过的，他将会奖励你他的小心心❤~~~

Input

 第一行一个整数n (1 ≤ n ≤ 1000)

第二行n 个整数 ai (1 ≤ ai ≤ 109)

代表这个数组

Output

如果可以变成z-sort过的数组，就输出数组，否则输出 "Impossible".

Examples

Input

4 1 2 2 1

Output

1 2 1 2

Input

5 1 3 2 2 5

Output

1 5 2 3 2

思路：可以通过代入法得出条件的意思是每一个偶数位上的数要大于前一个数和后一个数，所以我们要尽量保证该条件成立，则利用sort排序，将前面小的数先放在奇数位，再将较大的数一个一个放在偶数位。再用for循环判断是否满足题意，满足则输出该数组。

#include<iostream>

#include<algorithm>

using namespace std;

int main()

{

int n, i, j, x;

int a[1005] = { 0 };

int b[1005] = { 0 };

int flag[1005] = { 0 };

cin >> n;

for (i = 0; i < n; i++)

{

cin >> a[i];

}

sort(a, a + n);

j = 0;

for (i = 0; i < n; i+=2)

{

b[i] = a[j];

a[j] = 0;

j++;

}

j = 1;

for (i = 0; i < n; i++)

{

if (a[i] > 0)

{

b[j] = a[i];

j += 2;

}

}

x = 0;

for (i = 1; i < n; i+=2)

{

if (b[i] < b[i - 1] || b[i] < b[i + 1])

{

x = 1;

}

}

cout << endl;

if (x == 0)

{

for (i = 0; i < n; i++)

cout << b[i] << " ";

}

else

cout << "Impossible" << endl;

return 0;

}

J.

题目：

在连续几天的没日没夜后，wy学姐颤颤巍巍地翻出了一个珍藏多年的宝典，只见上面赫然写着——《凡人修仙传》！
她正在可怜兮兮地临时抱佛脚来试图提升自己目前的实力以获得最后的胜利。

事情是这样的，wy学姐本来卡在瓶颈期多年，经过前几天的修炼，隐隐有突破之势，如今金身已就，眼看神功大成，只差渡劫！
就在这时，天空一道惊雷，她落入了一个结界之中，这正是她飞升的最后一道关卡！

这个结界里有很多斗法者，而她需要与其中的优胜斗法者（即最后的胜利者）进行对决，赢则飞升。

为了渡过此劫、成功飞升，谨慎起见，她决定先打探一下对手的情况。

那些人的斗法是这样的，n个斗法者排成一队（随机），前俩名斗法者打一场，输的人 走到队伍的最后，赢的人继续与下一个斗法者对决，依次类推，直到有人能连胜k场为止。

对于这种修仙对决，自然是修炼层数越高的人能获胜啦。

正所谓知己知彼，百战不殆。
wy学姐坚信，只要能提前准确地预测出她的对手，她就能在这短暂的时间内找到越级（或许不是呢qwq）挑战胜利的办法！

你能帮她找到修练到多少层的人会获胜吗？

Input

第一行输入两个整数: n and k (2 ≤ n ≤ 500, 2 ≤ k ≤ 1012) ——n代表排队的斗法者人数，k代表要连胜的场数

第二行有 n 个整数 a1, a2, ..., an (1 ≤ ai ≤ n)——即队伍中每个人修炼神功的层数。保证每个人各不相同。

Output

输出一个整数——最后的优胜斗法者修炼到的功力层数.

Examples

Input

2 2 1 2

Output

2

Input

4 2 3 1 2 4

Output

3

Input

6 2 6 5 3 1 2 4

Output

6

Input

2 10000000000 2 1

Output

2

Note

第二个样例解释

3 和1打. 3 赢. 1 到最后面去

3 和 2打. 3 赢. 他获得两场胜利，所以他是最后的赢家

思路：将此题分为了两种情况，如果当K，即需要连胜的场数大于等于剩余人数-1，则说明需要找出队伍中最强的人。而另一种情况即为剩余人数-1大于K，则利用循环进行判断，如果在剩余人数-1小于等于K之前，有人能连胜K场，就直接输出，否则依然用第一种情况。

#include<iostream>

using namespace std;

int main()

{

long long n, k, max;

cin >> n >> k;

int a[505] = { 0 };

int i, j, f, s;

max = 0;

for (i = 0; i < n; i++)

{

cin >> a[i];

if (a[i] > max)

max = a[i];

}

if (k >= n - 1)

{

cout << max;

return 0;

}

else

{

s = 0;

f = 0;

j = 1;

int x = 0;

for (i = 1; i <= n; i++)

{

if (n - x < k)

break;

if (f == k && x == 0)

{

cout << a[x];

s = 1;

return 0;

}

else if (f == k - 1 && x != 0)

{

cout << a[x];

s = 1;

return 0;

}

if (a[x] > a[x + j])

{

f++;

j++;

}

else

{

x += j;

j = 1;

f = 0;

}

}

if (s == 0)

cout << max;

}

return 0;

}

相关知识

Hello world Python新手赛题解
ZUST 程序设计算法竞赛基础【1】题解报告
2011年ZOL主题摄影月赛四月
洛谷 P1077 摆花 题解
2023大学生技能竞赛月花艺赛项开赛
园林绿化工中理论知识题解。.doc
花店橱窗题目题解
一起定格美好瞬间，方程豹汽车11月摄影月赛邀你参赛
月度主题摄影比赛丨2024年4月摄影月赛主题“春天的号角”
光影中国网2021年第4期月赛：花卉摄影

网址: 2021.11 月赛题解 https://www.huajiangbk.com/newsview848523.html