ACM入门试题Problem_Set
A : 赶公交
Alfred在大学新区上学，他每个星期都要到市区学琴，因此要在每个星期六的10点钟之前赶到琴行上课，从郑大坐68路车到琴行要花整整一个小时，而68路车是每半小时一趟，整点和30分的时候会发一趟车。
这一次，Alfred起床晚了，一看表已经8点多了，匆忙收拾了一下之后，Alfred马上冲向公交站，但是，由于路况不佳，在前面的一段路上满是泥泞。路况如下：
如左图，A(x A,y A)是Alfred
现在所处的位置，B(x B,y B)是公交
站(Bus-stop)的位置，其中y>0的
区域是泥泞的地面，Alfred在泥
泞的地面上的移动速度是v1(米/
秒)，而y<0的区域是水泥地，
Alfred在水泥地上的移动速度只
有v2(米/秒)，其中v1<=v2，A在
第二象限，B在第四象限。
Alfred是一个物工院的学生，
他稍微估算了一下，剩下的时间
已经不多了，他看看表，现在离9
点整只剩下T秒了(T由题目给
出)，Alfred想知道，他如果用最
优的策略赶往公交站，今天的课
是否会迟到。
输入规格：
第一行是一个整数C，C<=10，紧接着C组数据，每组数据依次给出x A,y A,x B,y B,v1,v2和T，他们的意义如上文所述，x,y坐标的单位是米，所有坐标的绝对值<109，T是一个整数。
输出规格：
对于每组数据，输出YES或NO，表示Alfred会不会迟到。
输入样例：
3
-10.0 10.0 10.0 -10.0
5.0 5.0
6
-10.0 10.0 10.0 -10.0 5.0 5.0 5
-10.0 10.0 10.0 -10.0 5.0 3.0
8
输出样例：
YES
NO
YES
ps:三个样例中实际所需的最短时间依次是：5.66, 5.66, 7.33
出题者：黄文超
B : 逃学威龙
fish_ball无心向学，总是打逃课的主意，他确信他的期末考试绝对能够考过，但是老师可不相信他，因此老师定下了一条规矩，最后的期末成绩将由平时成绩和考试成绩组成，各占50%的分数，也就是满分100分，其中平时成绩50分，考试成绩50分。而老师为了不让同学们逃课，平时成绩将仅由出勤情况确定，每点名到一次逃课就要扣掉10分的平时成绩。
fish_ball很不满于老师这套想法，决心要将翘课进行到底，他有足够的信心和实力在期末考中得到满分，剩下的就只看平时成绩了，只要他在平时成绩中保留的分数>=10分，他这个学期就可以合格。他甚至为此充分调查了老师的点名习惯，发现如下规律：每个学期这门课程共有K个课时(K<=20)，而对于某节课老师点不点名是一个独立的事件，并且老师在某一节课点名的概率是p(0.0<=p<=1.0)，现在fish_ball想尽可能多的逃课，但是要保证他有90%以上的概率不挂掉这门课，问fish_ball这个学期最多能翘掉多少课？
输入规格：
第一行是一个整数C，C<=20，紧接着C组数据，每组数据包含一行，依次给出整数K (1<=K<=20)和p(0.0<=p<=1.0)，如题目中所描述。
输出规格：
对于每组数据，输出一个整数，表示fish_ball这学期最多能够翘掉几堂课。
输入样例：
4
4 1
4 0
20 0.5
20 0.2
输出样例：
4
4
9
出题者：黄文超
C : 烦恼的中学生
在郑大，很多学生都会找点兼职来赚点外快，Alfred也不例外，他找的兼职是家教。好了，现在Alfred的工作就是辅导一个高中生的数学。
这一天，这位高中生叫Alfred帮忙做一下作业：在二维平面内给出一个三角形的三个顶点坐标，现在的任务是求出这个三角形的垂心，也就是三角形的三条高线所在直线的交点。
当然，Alfred的数学是不错的，对于这么简单的问题，Alfred只用了半分钟就解决掉了，正当Alfred得意的时候，这位高中生却毫不吃惊地说：我们的作业一共有100条呢! Alfred听见了之后不禁倒抽了一口凉气，现在的中学生真命苦啊。
所以，打抱不平的Alfred决定要帮这位高中生的忙：利用计算机程序来批量解决这个问题，但是Alfred苦思数日却没有想出来解决办法，你们能帮他这个忙吗？
输入规格：
第一行是一个整数C(C<=100)，表示有C组测试数据，每组数据三行，每行两个浮点数分别表示三角形某个顶点的x,y坐标。所有坐标的绝对值<10000。输入保证三点不共线。
输出规格：
对于每组输入数据，输出两个浮点数xh, yh表示所给三角形垂心的纵横坐标，保留三位小数(四舍五入)。
Hint:请注意你的程序，避免输出-0.000的情况，这样系统会判错。(如果要输出一个极小的负数，如-0.000001，输出会变成-0.000，应该手动排除这种情况，确保这种时候输出0.000。)
输入样例：
3
-10 0
0 10
10 0
-10 0
10 0
0 17.321
2 10
4 -5
20 6
输出样例：
0.000 10.000
0.000 5.774
6.031 4.137
出题者：黄文超
D : Maze
There?re many buildings in ZZU, and Alfred is new here. Today, it is the first day he is at school. It?s 7:40 now, Alfred must go to the classroom at once, or he?ll be late. You know being late at the first class will make a bad impression on the teacher. Alfred is a good student, he will never make this happen, will he?
So he hurries to the buildings where the classrooms locate at. But the problem come out, he does not know the road! This make him mad, it just like a maze!
Now he turns to you, an old student at ZZU. What you should do is simple: just tell him how long the shortest path that leads him to the right classroom is. Alfred will thank you very much.
Now let?s describe the situation here. The map can be represented as a M×N
grid(2<=M<=50, 2<=N<=50). In each cell, there?s a symbol: ….?, ?X?, ?a?, ?c?, where a ….?means a the cell is reachable, an …X? represents a wall that is not reachable, and …a?means Alfred is at that place initially, …c? means the classroom.
At a single minute, Alfred can go from a reachable cell to an adjacent one (to the north, west, south or east), of course, the target cell must be also reachable. So can you tell if Alfred takes the optimal path, how many minutes does he need at least to reach the classroom?
Input Specification:
The first line consist only one integer C(C <= 10), indicates C cases follows. In each case, there are two integers M and N on the first line, as the size of the map. Then M lines follows are the given map.
Output Specification:
For each case, output a single line consist a single integer, represents at least how many minutes Alfred need to arrive at the class. If there is no path to the classroom, just print “No path”
Sample Input: 2
3 5
a....
XX.XX
c..X.
4 6
a...X.
XX.X.. cX...X
..XX.. Sample Output: 6
No path
Author：Alfred Huang
E ：生日聚会
今天是JacmY生日，他请大家吃饭，就这样，一行N个人来到了餐馆，大家吃吃喝喝，有说有笑，气氛甚欢，这时突然有人提议大家玩一个游戏，听罢规则后，就开始了游戏。
游戏规则是这样的，吃饭的N个人围坐在桌子旁，JacmY是1号，沿着顺时针方向开始编号，2、3……N，然后由JacmY随机说一个数K(1 <= K <= N)，从JacmY开始顺时针报数，“1，2……”，当有人报到K时，这个人从他的位置起来，先坐到了其他桌子，然后由下一个人重新从1开始报……就这样循环下去，每当有人报到K，这个人就离开了桌子，直到剩下这最后一个人，他非常倒霉的要接受大家的惩罚，就是罚酒一杯。JacmY有些郁闷了，K是由自己说的，万一说不好让自己受惩罚了，这个就有点不爽了，所以JacmY想请你帮忙找出哪些K会让他受罚，这样以来，JacmY就不用担心会喝太多酒了！
输入规格：
第一行一个整数T代表样例的组数
下面T行，每行一个整数N， 1 <= N<= 100；N如题目所述。
输出规格：
对于每组数据，第一行输出一个整数M，表示有M个这样的K会让JacmY 受罚，接下来一行是M个整数，代表K分别取的哪些值，这些数字间用空格隔开。
输入样例：
3
5
8
10
输出样例：
1
4
2
2 6
1
8
出题人：吴云鹏
F：奇特的图形
记得上小学奥数时，JacmY最喜欢做的题就是给一个图形，从它某一个顶点出发描这个图形，若恰通过图中每条边一次，看最后能否又回到起点。当时JacmY 只懂得拿着铅笔随便画画试试，如果成功了，就说这个图能画下来，而他判断不能画下来的标准就是费了半天功夫都画不出来，当然这么做是不对的，特别当图形变得复杂时，JacmY是试不过来的。看着可怜的JacmY，你能帮帮他吗？
输入规格：
第一行一个整数T代表样例的组数
以下T组数据中，每组第一行是N，K，(2 <= N <= 100)分别代表当前图形有N个顶点，K条边，接下来K行中，每行两个整数X，Y（ 1 <= X,Y <= N）代表顶点X和顶点Y之间有一条边。
输出规格：
如果当前图形能按照题目要求描出来，则输出“YES”（不包括引号），否则输出“NO”。
输入样例：
3
3 3
1 2
2 3
1 3
3 2
1 2
2 3
2 2
1 2
1 2
输出样例：
YES
NO
YES
出题人：吴云鹏
G: Binary String Matching
I can say: this is the simplest problem in this contest, if you missed it because the problem is in English, it will be a pity.
Given two strings A and B, whose alphabet consist only …0?and …1?. Your task is only to tell how many times does A appear as a substring of B?
For example, the text string B is …1001110110? while the pattern string A is …11?, you should output 3, because the pattern A appeared at the position 4, 5 and 8.
It?s very simple, isn?t it? I will never cheat you. So be quick, you will easily get a …Yes?! Just do it!
Input Specification:
The first line consist only one integer C(C <= 10), indicates C cases follows. In each case, there are two lines, the first line gives the string A, length (A) <= 10, and the second line gives the string B, length (B) <= 100. And it is guaranteed that B is always longer than A.
Output Specification:
For each case, output a single line consist a single integer, tells how many times do B appears as a substring of A.
Sample Input:
3
11
1001110110
101
110010010010001
1010
110100*********
Sample Output:
3
3
Author：Alfred Huang
H: Binary String Matching (Extreme)
You will soon found this problem is the same as the previous one, but I tell you, it is not so easy, because the data is extremely large, so in order to get a …Yes?, you must find an effective way to solve it, within a second. Otherwise, you?ll get a …Time Limit Exceed?. So a brute force solution is not available here, be avoid to do this.
Given two strings A and B, whose alphabet consist only …0?and …1?. Your task is only to tell how many times does A appear as a substring of B?
For example, the text string B is …1001110110? while the pattern string A is …11?, you should output 3, because the pattern A appeared at the position 4, 5 and 8.
Input Specification:
The first line consist only one integer C(C <= 10), indicates C cases follows. In each case, there are two lines, the first line gives the string A, length (A) <= 30, and the second line gives the string B, length (B) <= 10000000. And it is guaranteed that B is always longer than A.
Output Specification:
For each case, output a single line consist a single integer, tells how many times do B appears as a substring of A.
Hint: Anyway, this problem is not so difficult, try to use bit processing strategy.
Sample Input:
3
11
1001110110
101
110010010010001
1010
110100*********
Sample Output:
3
3
Author：Alfred Huang