# POJ 1258-Agri-Net

POJ 1258-Agri-Net Agri-Net Time Limit: 1000MS Memory Limit: 10000K Total Submissions: 40975 Accepted: 16713 Description Farmer John has been elected mayor of his town! One of his campaign promises was to bring internet connectivity to all farms in the area. He needs your help, of course. Farmer John ordered a high speed connection for his farm and is going to share his connectivity with the other farmers. To minimize cost, he wants to lay the minimum amount of optical fiber to connect his farm to all the other farms. Given a list of how much fiber it takes to connect each pair of farms, you must find the minimum amount of fiber needed to connect them all together. Each farm must connect to some other farm such that a packet can flow from any one farm to any other farm. The distance between any two farms will not exceed 100,000. Input The input includes several cases. For each case, the first line contains the number of farms, N (3 <= N <= 100). The following lines contain the N x N conectivity matrix, where each element shows the distance from on farm to another. Logically, they are N lines of N space-separated integers. Physically, they are limited in length to 80 characters, so some lines continue onto others. Of course, the diagonal will be 0, since the distance from farm i to itself is not interesting for this problem. Output For each case, output a single integer length that is the sum of the minimum length of fiber required to connect the entire set of farms. Sample Input 4 0 4 9 21 4 0 8 17 9 8 0 16 21 17 16 0 Sample Output 28 Source USACO 102

The input includes several cases.

# POJ 2485-Highways

POJ 2485-Highways Highways Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 22907 Accepted: 10553 Description The island nation of Flatopia is perfectly flat. Unfortunately, Flatopia has no public highways. So the traffic is difficult in Flatopia. The Flatopian government is aware of this problem. They’re planning to build some highways so that it will be possible to drive between any pair of towns without leaving the highway system. Flatopian towns are numbered from 1 to N. Each highway connects exactly two towns. All highways follow straight lines. All highways can be used in both directions. Highways can freely cross each other, but a driver can only switch between highways at a town that is located at the end of both highways. The Flatopian government wants to minimize the length of the longest highway to be built. However, they want to guarantee that every town is highway-reachable from every other town. Input The first line of input is an integer T, which tells how many test cases followed. The first line of each case is an integer N (3 <= N <= 500), which is the number of villages. Then come N lines, the i-th of which contains N integers, and the j-th of these N integers is the distance (the distance should be an integer within [1, 65536]) between village i and village j. There is an empty line after each test case. Output For each test case, you should output a line contains an integer, which is the length of the longest road to be built such that all the villages are connected, and this value is minimum. Sample Input 1 3 0 990 692 990 0 179 692 179 0 Sample Output 692 Hint Huge input,scanf is recommended. Source POJ Contest,Author:Mathematica@ZSU

which is the length of the longest road to be built such that all the villages are connected, and this value is minimum.

# hihoCoder 1051-补提交卡

hihoCoder 1051-补提交卡 #1051 : 补提交卡 时间限制:2000ms 单点时限:1000ms 内存限制:256MB 描述 小Ho给自己定了一个宏伟的目标：连续100天每天坚持在hihoCoder上提交一个程序。100天过去了，小Ho查看自己的提交记录发现有N天因为贪玩忘记提交了。于是小Ho软磨硬泡、强忍着小Hi鄙视的眼神从小Hi那里要来M张”补提交卡”。每张”补提交卡”都可以补回一天的提交，将原本没有提交程序的一天变成有提交程序的一天。小Ho想知道通过利用这M张补提交卡，可以使自己的”最长连续提交天数”最多变成多少天。 输入 第一行是一个整数T(1 <= T <= 10)，代表测试数据的组数。 每个测试数据第一行是2个整数N和M(0 <= N, M <= 100)。第二行包含N个整数a1, a2, … aN(1 <= a1 < a2 < … < aN <= 100)，表示第a1, a2, … aN天小Ho没有提交程序。 输出 对于每组数据，输出通过使用补提交卡小Ho的最长连续提交天数最多变成多少。 样例输入 3 5 1 34 77 82 83 84 5 2 10 30 55 56 90 5 10 10 30 55 56 90 样例输出 76 59 100

# POJ 1019-Number Sequence

POJ 1019-Number Sequence Number Sequence Time Limit: 1000MS Memory Limit: 10000K Total Submissions: 34278 Accepted: 9835 Description A single positive integer i is given. Write a program to find the digit located in the position i in the sequence of number groups S1S2…Sk. Each group Sk consists of a sequence of positive integer numbers ranging from 1 to k, written one after another. For example, the first 80 digits of the sequence are as follows: 11212312341234512345612345671234567812345678912345678910123456789101112345678910 Input The first line of the input file contains a single integer t (1 ≤ t ≤ 10), the number of test cases, followed by one line for each test case. The line for a test case contains the single integer i (1 ≤ i ≤ 2147483647) Output There should be one output line per test case containing the digit located in the position i. Sample Input 2 8 3 Sample Output 2 2 Source Tehran 2002, First Iran Nationwide Internet Programming Contest

# hihoCoder 1043-完全背包

hihoCoder 1043-完全背包 #1043 : 完全背包 时间限制:20000ms 单点时限:1000ms 内存限制:256MB 描述 且说之前的故事里，小Hi和小Ho费劲心思终于拿到了茫茫多的奖券！而现在，终于到了小Ho领取奖励的时刻了！ 等等，这段故事为何似曾相识？这就要从平行宇宙理论说起了………总而言之，在另一个宇宙中，小Ho面临的问题发生了细微的变化！ 小Ho现在手上有M张奖券，而奖品区有N种奖品，分别标号为1到N，其中第i种奖品需要need(i)张奖券进行兑换，并且可以兑换无数次，为了使得辛苦得到的奖券不白白浪费，小Ho给每件奖品都评了分，其中第i件奖品的评分值为value(i),表示他对这件奖品的喜好值。现在他想知道，凭借他手上的这些奖券，可以换到哪些奖品，使得这些奖品的喜好值之和能够最大。 提示一： 切，不就是0~1变成了0~K么 提示二：强迫症患者总是会将状态转移方程优化一遍又一遍 提示三：同样不要忘了优化空间哦！ 输入 每个测试点（输入文件）有且仅有一组测试数据。 每组测试数据的第一行为两个正整数N和M,表示奖品的种数，以及小Ho手中的奖券数。 接下来的n行描述每一行描述一种奖品，其中第i行为两个整数need(i)和value(i)，意义如前文所述。 测试数据保证 对于100%的数据，N的值不超过500，M的值不超过10^5 对于100%的数据，need(i)不超过2*10^5, value(i)不超过10^3 输出 对于每组测试数据，输出一个整数Ans，表示小Ho可以获得的总喜好值。 样例输入 5 1000 144 990 487 436 210 673 567 58 1056 897 样例输出 5940

# POJ 2586-Y2K Accounting Bug

POJ 2586-Y2K Accounting Bug Y2K Accounting Bug Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 10647 Accepted: 5328 Description Accounting for Computer Machinists (ACM) has sufferred from the Y2K bug and lost some vital data for preparing annual report for MS Inc. All what they remember is that MS Inc. posted a surplus or a deficit each month of 1999 and each month when MS Inc. posted surplus, the amount of surplus was s and each month when MS Inc. posted deficit, the deficit was d. They do not remember which or how many months posted surplus or deficit. MS Inc., unlike other companies, posts their earnings for each consecutive 5 months during a year. ACM knows that each of these 8 postings reported a deficit but they do not know how much. The chief accountant is almost sure that MS Inc. was about to post surplus for the entire year of 1999. Almost but not quite. Write a program, which decides whether MS Inc. suffered a deficit during 1999, or if a surplus for 1999 was possible, what is the maximum amount of surplus that they can post. Input Input is a sequence of lines, each containing two positive integers s and d. Output For each line of input, output one line containing either a single integer giving the amount of surplus for the entire year, or output Deficit if it is impossible. Sample Input 59 237 375 743 200000 849694 2500000 8000000 Sample Output 116 28 300612 Deficit Source Waterloo local 2000.01.29

ACM knows that each of these 8 postings reported a deficit

1 2 3 4 5 6 7 8 9 10 11 12 s s s s d s s s s d s s //每5个月里只有1个月亏损 s s s d d s s s d d s s //每5个月里只有2个月亏损 s s d d d s s d d d s s //每5个月里只有3个月亏损 s d d d d s d d d d s d //每5个月里只有4个月亏损

# POJ 1012-Joseph

POJ 1012-Joseph Joseph Time Limit: 1000MS Memory Limit: 10000K Total Submissions: 48397 Accepted: 18267 Description The Joseph’s problem is notoriously known. For those who are not familiar with the original problem: from among n people, numbered 1, 2, . . ., n, standing in circle every mth is going to be executed and only the life of the last remaining person will be saved. Joseph was smart enough to choose the position of the last remaining person, thus saving his life to give us the message about the incident. For example when n = 6 and m = 5 then the people will be executed in the order 5, 4, 6, 2, 3 and 1 will be saved. Suppose that there are k good guys and k bad guys. In the circle the first k are good guys and the last k bad guys. You have to determine such minimal m that all the bad guys will be executed before the first good guy. Input The input file consists of separate lines containing k. The last line in the input file contains 0. You can suppose that 0 < k < 14. Output The output file will consist of separate lines containing m corresponding to k in the input file. Sample Input 3 4 Sample Output 5 30 Source Central Europe 1995

# hihoCoder 1040-矩形判断

hihoCoder 1040-矩形判断 #1040 : 矩形判断 时间限制:1000ms 单点时限:1000ms 内存限制:256MB 描述 给出平面上4条线段，判断这4条线段是否恰好围成一个面积大于0的矩形。 输入 输入第一行是一个整数T(1<=T<=100)，代表测试数据的数量。 每组数据包含4行，每行包含4个整数x1, y1, x2, y2 (0 <= x1, y1, x2, y2 <= 100000)；其中(x1, y1), (x2,y2)代表一条线段的两个端点。 输出 每组数据输出一行YES或者NO，表示输入的4条线段是否恰好围成矩形。 样例输入 3 0 0 0 1 1 0 1 1 0 1 1 1 1 0 0 0 0 1 2 3 1 0 3 2 3 2 2 3 1 0 0 1 0 1 1 0 1 0 2 0 2 0 1 1 1 1 0 1 样例输出 YES YES NO

# hihoCoder 1038-01背包

hihoCoder 1038-01背包 #1038 : 01背包 时间限制:20000ms 单点时限:1000ms 内存限制:256MB 描述 且说上一周的故事里，小Hi和小Ho费劲心思终于拿到了茫茫多的奖券！而现在，终于到了小Ho领取奖励的时刻了！ 小Ho现在手上有M张奖券，而奖品区有N件奖品，分别标号为1到N，其中第i件奖品需要need(i)张奖券进行兑换，同时也只能兑换一次，为了使得辛苦得到的奖券不白白浪费，小Ho给每件奖品都评了分，其中第i件奖品的评分值为value(i),表示他对这件奖品的喜好值。现在他想知道，凭借他手上的这些奖券，可以换到哪些奖品，使得这些奖品的喜好值之和能够最大。 提示一：合理抽象问题、定义状态是动态规划最关键的一步 提示二：说过了减少时间消耗，我们再来看看如何减少空间消耗 输入 每个测试点（输入文件）有且仅有一组测试数据。 每组测试数据的第一行为两个正整数N和M,表示奖品的个数，以及小Ho手中的奖券数。 接下来的n行描述每一行描述一个奖品，其中第i行为两个整数need(i)和value(i)，意义如前文所述。 测试数据保证 对于100%的数据，N的值不超过500，M的值不超过10^5 对于100%的数据，need(i)不超过2*10^5, value(i)不超过10^3 输出 对于每组测试数据，输出一个整数Ans，表示小Ho可以获得的总喜好值。 样例输入 5 1000 144 990 487 436 210 673 567 58 1056 897 样例输出 2099

# POJ 1011-Sticks

POJ 1011-Sticks Sticks Time Limit: 1000MS Memory Limit: 10000K Total Submissions: 121990 Accepted: 28247 Description George took sticks of the same length and cut them randomly until all parts became at most 50 units long. Now he wants to return sticks to the original state, but he forgot how many sticks he had originally and how long they were originally. Please help him and design a program which computes the smallest possible original length of those sticks. All lengths expressed in units are integers greater than zero. Input The input contains blocks of 2 lines. The first line contains the number of sticks parts after cutting, there are at most 64 sticks. The second line contains the lengths of those parts separated by the space. The last line of the file contains zero. Output The output should contains the smallest possible length of original sticks, one per line. Sample Input 9 5 2 1 5 2 1 5 2 1 4 1 2 3 4 Sample Output 6 5 Source Central Europe 1995