贝壳找房2021届校招算法卷1
时长:120分钟 总分:100分
116浏览 0人已完成答题
题型介绍
| 题型 | 填空题 |
|---|---|
| 数量 | 4 |
1.
取模方程
给定两个非负整数
。求有多少个正整数
，满足
。如果有无穷个解输出"inf"。
输入描述：
输入样例：
7 3 输出描述：
一行一个数字或字符串表示答案。输出样例
1
。求有多少个正整数，满足。如果有无穷个解输出"inf"。
输入描述：
一行两个数字
。
。
2.
迷宫中的牛可乐
牛可乐有一个
行
列的迷宫，如果
是'#',代表第
行第
列的方格为墙壁，如果
是'.',代表第
行第
列的方格为可走方格。
行列的迷宫，如果是'#',代表第行第列的方格为墙壁，如果是'.',代表第行第列的方格为可走方格。 每一步移动在一个可走方格，可以水平的或者垂直的移动到相邻的一个可走方格中。
但是不能走出迷宫，不能走到一个墙壁方格，也不能对角线方向移动。
你可以选择任意一个起点方格和终点方格（这两个方格必须为可走方格，且可以相互到达）。
牛可乐将从你选择的起点方格用最小的步数移动到终点方格。
本题需要你最优的选择起点方格和终点方格后让牛可乐必须要移动的步数尽可能大，你需要计算这个步数的最大值。
输入描述：第一行一个整数
接下来
行，每行
个字符 代表迷宫
中至少包含2个字符‘.’
3.
音响外放
牛牛寝室有四人，他们打算用一个音响播放自己喜欢的曲子。
但是四人的喜好各不相同，他们每个人选取了自己最喜欢的n首曲子。
也就是一共有4n首曲子，第i首的长度为
。
但是他们不能容忍播放别人的曲子的时间比他们长很多，牛牛可以从这些曲子中删掉一些，使得每个人的播放总长大致相等。
牛牛想知道在每个人都至少都播放1首歌的情况下，播放最长时间和播放最短时间的差距最小是多少。
输入描述： 第一行输入一个整数n，表示每个人都选择了n首曲子。
输出样例
100
但是四人的喜好各不相同，他们每个人选取了自己最喜欢的n首曲子。
也就是一共有4n首曲子，第i首的长度为
。但是他们不能容忍播放别人的曲子的时间比他们长很多，牛牛可以从这些曲子中删掉一些，使得每个人的播放总长大致相等。
牛牛想知道在每个人都至少都播放1首歌的情况下，播放最长时间和播放最短时间的差距最小是多少。
输入描述： 第一行输入一个整数n，表示每个人都选择了n首曲子。
随后4行，每行n个整数，分别表示第每名室友喜欢的歌曲的时间长度。
对于
的数据有
对于
的数据有
输入样例：
3
240 300 360
600 200 200
300 400 500
600 600 600 输出描述：
的数据有对于
的数据有一行输出一个整数。
4.
最大公约数
我们定义任意一个序列的最大公约数为最大的能整除序列中所有数的数
例如序列
的最大公约数为
，
的最大公约数为
，表示数据组数
对于每组数据，
第一行输入一个整数
接下来一行
个整数表示序列中的数输入样例：
2
3
2 2 4
2
1 2 输出描述：
输出T个整数，若可能，则输出最少需要删除的数，若不可能，则输出-1输出样例
-1
0
例如序列
的最大公约数为，的最大公约数为 现在牛牛想知道，对于一个长度为
的序列，如果他至多能删除
个数，请问他最少需要删除多少个数才能让序列的最大公约数变为
，或者这根本是不可能的
输入描述：
第一行输入一个整数的序列，如果他至多能删除个数，请问他最少需要删除多少个数才能让序列的最大公约数变为，或者这根本是不可能的 ，表示数据组数对于每组数据，
第一行输入一个整数
接下来一行
个整数表示序列中的数输入样例：
2
3
2 2 4
2
1 2 输出描述：
输出T个整数，若可能，则输出最少需要删除的数，若不可能，则输出-1输出样例
-1
0