菜单

POJ刷题计划 水题四连 1002~1005

八月 17, 2018 - 算法
POJ刷题计划 水题四连 1002~1005

POJ-1002 487-3279

题目描述

Businesses like to have memorable telephone numbers. One way to make a telephone number memorable is to have it spell a memorable word or phrase. For example, you can call the University of Waterloo by dialing the memorable TUT-GLOP. Sometimes only part of the number is used to spell a word. When you get back to your hotel tonight you can order a pizza from Gino’s by dialing 310-GINO. Another way to make a telephone number memorable is to group the digits in a memorable way. You could order your pizza from Pizza Hut by calling their “three tens” number 3-10-10-10.
The standard form of a telephone number is seven decimal digits with a hyphen between the third and fourth digits (e.g. 888-1200). The keypad of a phone supplies the mapping of letters to numbers, as follows:

A, B, and C map to 2
D, E, and F map to 3
G, H, and I map to 4
J, K, and L map to 5
M, N, and O map to 6
P, R, and S map to 7
T, U, and V map to 8
W, X, and Y map to 9

There is no mapping for Q or Z. Hyphens are not dialed, and can be added and removed as necessary. The standard form of TUT-GLOP is 888-4567, the standard form of 310-GINO is 310-4466, and the standard form of 3-10-10-10 is 310-1010.
Two telephone numbers are equivalent if they have the same standard form. (They dial the same number.)

Your company is compiling a directory of telephone numbers from local businesses. As part of the quality control process you want to check that no two (or more) businesses in the directory have the same telephone number.

Input

The input will consist of one case. The first line of the input specifies the number of telephone numbers in the directory (up to 100,000) as a positive integer alone on the line. The remaining lines list the telephone numbers in the directory, with each number alone on a line. Each telephone number consists of a string composed of decimal digits, uppercase letters (excluding Q and Z) and hyphens. Exactly seven of the characters in the string will be digits or letters.

Output

Generate a line of output for each telephone number that appears more than once in any form. The line should give the telephone number in standard form, followed by a space, followed by the number of times the telephone number appears in the directory. Arrange the output lines by telephone number in ascending lexicographical order. If there are no duplicates in the input print the line:

No duplicates.

Sample Input

12
4873279
ITS-EASY
888-4567
3-10-10-10
888-GLOP
TUT-GLOP
967-11-11
310-GINO
F101010
888-1200
-4-8-7-3-2-7-9-
487-3279

Sample Output

310-1010 2
487-3279 4
888-4567 3

题目大意

这题题干挺长的,意思倒还算明确。就是说0-9的数字可以转换成对应的字母表示,在一串数字之间可以任意的插入-,我们的任务是读入这些字符串,找到相同的意义的字符串并且归类,输出的时候按照xxxx-xxx的格式输出就好。

题目分析

乍一看是挺水的一道题,我最开始的思路是把所有的字符串读入之后放在一个结构体数组里面,结构体包括一个数组存字符串,一个数字存出现次数。读入的时候跳过所有的-,在第4个位置手动加上一个-,也就是直接读入输出格式的字符串。每输入一个字符串,让它和之前的每一个字符串匹配,如果相同,与它比较的字符串的技术+1。输入完毕之后按字符串排序,排序后遍历次数,输出所有次数大于2的情况。

本来以为这种题可以这样过的,交了一发结果tle,于是去想一些其他方法。

这里注意到一点,所有的字符串转换成数字之后只有7位,换言之,在int的范围之内,也就是说,我可以转换成int直接对比和排序,要比对字符串对比和排序高效很多。输入的时候忽略所有的-,把字母转换成对应数字,每次都令当前数字*10+当前数字,得到一个7位数。最后输出的时候要先输出4位,再输出-,最后输出最后3位,要注意的是控制格式%04d和%03d,因为可能是0开头。

代码实现


POJ-1003 Hangover

题目描述

How far can you make a stack of cards overhang a table? If you have one card, you can create a maximum overhang of half a card length. (We’re assuming that the cards must be perpendicular to the table.) With two cards you can make the top card overhang the bottom one by half a card length, and the bottom one overhang the table by a third of a card length, for a total maximum overhang of 1/2 + 1/3 = 5/6 card lengths. In general you can make n cards overhang by 1/2 + 1/3 + 1/4 + … + 1/(n + 1) card lengths, where the top card overhangs the second by 1/2, the second overhangs tha third by 1/3, the third overhangs the fourth by 1/4, etc., and the bottom card overhangs the table by 1/(n + 1). This is illustrated in the figure below.
image

Input

The input consists of one or more test cases, followed by a line containing the number 0.00 that signals the end of the input. Each test case is a single line containing a positive floating-point number c whose value is at least 0.01 and at most 5.20; c will contain exactly three digits.

Output

For each test case, output the minimum number of cards necessary to achieve an overhang of at least c card lengths. Use the exact output format shown in the examples.

Sample Input

1.00
3.71
0.04
5.19
0.00

Sample Output

3 card(s)
61 card(s)
1 card(s)
273 card(s)

题目大意

在桌子边缘放卡片,第n张卡片可以有1/(n+1)的长度伸出桌面,给出总长度,问需要几张卡片可以到达这个长度。

题目分析

一道看起来不难实际上也不难的问题,看到discuss里有些人受到高精度的影响,我倒是没有遇见,直接上代码吧。

代码实现:

总结

普普通通的一道水题,没啥好说的,可能是给我找找自信吧(雾


POJ-1004 Financial Management

题目描述

Larry graduated this year and finally has a job. He’s making a lot of money, but somehow never seems to have enough. Larry has decided that he needs to grab hold of his financial portfolio and solve his financing problems. The first step is to figure out what’s been going on with his money. Larry has his bank account statements and wants to see how much money he has. Help Larry by writing a program to take his closing balance from each of the past twelve months and calculate his average account balance.

Input

The input will be twelve lines. Each line will contain the closing balance of his bank account for a particular month. Each number will be positive and displayed to the penny. No dollar sign will be included.

Output

The output will be a single number, the average (mean) of the closing balances for the twelve months. It will be rounded to the nearest penny, preceded immediately by a dollar sign, and followed by the end-of-line. There will be no other spaces or characters in the output.

Sample Input

100.00
489.12
12454.12
1234.10
823.05
109.20
5.27
1542.25
839.18
83.99
1295.01
1.75

Sample Output

$1581.42

题目大意

题意更加简单了,输入十二个数字求平均数,输出的时候加上$即可。

题目分析

上一题逃过了高精度的问题,这一关就没那么容易了,使用double会wa掉,成为高精度受害者(x,用float即可。

代码实现


POJ_1005 I Think I Need a Houseboat

题目描述

Fred Mapper is considering purchasing some land in Louisiana to build his house on. In the process of investigating the land, he learned that the state of Louisiana is actually shrinking by 50 square miles each year, due to erosion caused by the Mississippi River. Since Fred is hoping to live in this house the rest of his life, he needs to know if his land is going to be lost to erosion.

After doing more research, Fred has learned that the land that is being lost forms a semicircle. This semicircle is part of a circle centered at (0,0), with the line that bisects the circle being the X axis. Locations below the X axis are in the water. The semicircle has an area of 0 at the beginning of year 1. (Semicircle illustrated in the Figure.)
image

Input

The first line of input will be a positive integer indicating how many data sets will be included (N). Each of the next N lines will contain the X and Y Cartesian coordinates of the land Fred is considering. These will be floating point numbers measured in miles. The Y coordinate will be non-negative. (0,0) will not be given.

Output

For each data set, a single line of output should appear. This line should take the form of: “Property N: This property will begin eroding in year Z.” Where N is the data set (counting from 1), and Z is the first year (start from 1) this property will be within the semicircle AT THE END OF YEAR Z. Z must be an integer. After the last data set, this should print out “END OF OUTPUT.”

Sample Input

2
1.0 1.0
25.0 0.0

Sample Output

Property 1: This property will begin eroding in year 1.
Property 2: This property will begin eroding in year 20.
END OF OUTPUT.

题目大意

土地从(0,0)的位置开始以半圆的形状被侵蚀,每年面积扩大50,给出点的坐标,求出这个点什么时候被水淹没。

题目分析

这题也不算难,不过我wa了几发,一开始的想法就是求出以对应点到原点距离为半径的半圆的面积,然后面积从50一直累加上去,最后求出计数,过了样例就交了一发,但是这个做法竟然会wa,于是换成用求出的面积除以50加1,得到的结果理论上和之前一样,但是这样就神奇的过了。

代码实现

总结

怎么看都是一道水题,也不知道为什么第一种方法会wa,可能是因为eps的问题吧。

标签:, ,

发表评论

电子邮件地址不会被公开。 必填项已用*标注