CHAPTER 1
Problem Types 问题类型：
Dynamic Programming
Greedy
Complete Search
Flood Fill
Shortest Path
Recursive Search Techniques
Minimum Spanning Tree
Knapsack
Computational Geometry
Network Flow
Eulerian Path
Two-Dimensional Convex Hull
BigNums
Heuristic Search
Approximate Search
Ad Hoc Problems
Section 1.1
Introduction
Section 1.2
Ad Hoc Problems
`Ad hoc’ problems are those whose algorithms do not fall into standard categories with well-studied solutions. Each ad hoc problem is different; no specific or general techniques exist to solve them.
Of course, this makes the problems the `fun’ ones, since each one presents a new challenge. The solutions might require a novel data structure or an unusual set of loops or conditionals. Sometimes they require special combinations that are rare or at least rarely encountered.
Ad hoc problems usually require careful reading and usually yield to an attack that revolves around carefully sequencing the instructions given in the problem.
Ad hoc problems can still require reasonable optimizations and at least a degree of analysis that enables one to avoid loops nested five deep, for example.
More ad hoc problems appear on this web site than any other kind of problem. Always be ready for an ad hoc problem if you can not classify a problem as one of the other standard types (to be listed later).
Greedy Gift Givers
A group of NP (2 ≤ NP ≤ 10) uniquely named friends has decided to exchange gifts of money. Each of these friends might or might not give some money to some or all of the other friends (although some might be cheap and give to no one). Likewise, each friend might or might not receive money from any or all of the other friends. Your goal is to deduce how much more money each person receives than they give.
The rules for gift-giving are potentially different than you might expect. Each person goes to the bank (or any other source of money) to get a certain amount of money to give and divides this money evenly among all those to whom he or she is giving a gift. No fractional money is available, so dividing 7 among 2 friends would be 3 each for the friends with 1 left over – that 1 left over goes into the giver’s “account”. All the participants’ gift accounts start at 0 and are decreased by money given and increased by money received.
In any group of friends, some people are more giving than others (or at least may have more acquaintances) and some people have more money than others.
Given:
a group of friends, no one of whom has a name longer than 14 characters,
the money each person in the group spends on gifts, and
a (sub)list of friends to whom each person gives gifts,
determine how much money each person ends up with.
N个小朋友相互送礼物，计算每个小朋友的得失
Friday the Thirteenth
Is Friday the 13th really an unusual event?
That is, does the 13th of the month land on a Friday less often than on any other day of the week? To answer this question, write a program that will compute the frequency that the 13th of each month lands on Sunday, Monday, Tuesday, Wednesday, Thursday, Friday, and Saturday over a given period of N years. The time period to test will be from January 1, 1900 to December 31, 1900+N-1 for a given number of years, N. N is positive and will not exceed 400.
Note that the start year is NINETEEN HUNDRED, not NINETEEN NINETY.
There are few facts you need to know before you can solve this problem:
January 1, 1900 was on a Monday.
Thirty days has September, April, June, and November, all the rest have 31 except for February which has 28 except in leap years when it has 29.
Every year evenly divisible by 4 is a leap year (1992 = 4*498 so 1992 will be a leap year, but the year 1990 is not a leap year)
The rule above does not hold for century years. Century years divisible by 400 are leap years, all others are not. Thus, the century years 1700, 1800, 1900 and 2100 are not leap years, but 2000 is a leap year.
Do not use any built-in date functions in your computer language.
Don’t just precompute the answers, either, please.
黑色星期五，计算N个年份每个月的13号是星期几，然后统计出来
Broken Necklace
You have a necklace of N red, white, or blue beads (3<=N<=350) some of which are red, others blue, and others white, arranged at random. Here are two examples for n=29:
The beads considered first and second in the text that follows have been marked in the picture.
The configuration in Figure A may be represented as a string of b’s and r’s, where b represents a blue bead and r represents a red one, as follows: brbrrrbbbrrrrrbrrbbrbbbbrrrrb .
Suppose you are to break the necklace at some point, lay it out straight, and then collect beads of the same color from one end until you reach a bead of a different color, and do the same for the other end (which might not be of the same color as the beads collected before this).
Determine the point where the necklace should be broken so that the most number of beads can be collected.
项链有三个颜色 rwb，w是通配颜色，可以充当r或者b
求从一个点截断项链，头尾分别可以获得的同一颜色的珠子数量，两者相加的最大值
Section 1.3
Complete Search
brute force 暴力法
The Idea
Solving a problem using complete search is based on the ``Keep It Simple, Stupid’’ principle. The goal of solving contest problems is to write programs that work in the time allowed, whether or not there is a faster algorithm.
Complete search exploits the brute force, straight-forward, try-them-all method of finding the answer. This method should almost always be the first algorithm/solution you consider. If this works within time and space constraints, then do it: it’s easy to code and usually easy to debug. This means you’ll have more time to work on all the hard problems, where brute force doesn’t work quickly enough.
In the case of a problem with only fewer than a couple million possibilities, iterate through each one of them, and see if the answer works.
Careful, Careful
Sometimes, it’s not obvious that you use this methodology.
Milking Cows
Three farmers rise at 5 am each morning and head for the barn to milk three cows. The first farmer begins milking his cow at time 300 (measured in seconds after 5 am) and ends at time 1000. The second farmer begins at time 700 and ends at time 1200. The third farmer begins at time 1500 and ends at time 2100. The longest continuous time during which at least one farmer was milking a cow was 900 seconds (from 300 to 1200). The longest time no milking was done, between the beginning and the ending of all milking, was 300 seconds (1500 minus 1200).
Your job is to write a program that will examine a list of beginning and ending times for N (1 <= N <= 5000) farmers milking N cows and compute (in seconds):
- The longest time interval at least one cow was milked.
- The longest time interval (after milking starts) during which no cows were being milked.
农民挤奶牛,每个农民有各自的挤奶时间段
求至少有一名农民在挤奶的最长连续时间段
求没有一个农民在挤奶的最长时间间隔
Transformations
A square pattern of size N x N (1 <= N <= 10) black and white square tiles is transformed into another square pattern. Write a program that will recognize the minimum transformation that has been applied to the original pattern given the following list of possible transformations:
#1: 90 Degree Rotation: The pattern was rotated clockwise 90 degrees.
#2: 180 Degree Rotation: The pattern was rotated clockwise 180 degrees.
#3: 270 Degree Rotation: The pattern was rotated clockwise 270 degrees.
#4: Reflection: The pattern was reflected horizontally (turned into a mirror image of itself by reflecting around a vertical line in the middle of the image).
#5: Combination: The pattern was reflected horizontally and then subjected to one of the rotations (#1-#3).
#6: No Change: The original pattern was not changed.
#7: Invalid Transformation: The new pattern was not obtained by any of the above methods.
In the case that more than one transform could have been used, choose the one with the minimum number above.
从矩阵A是否可以转换到矩阵B
- 1.旋转90度
- 2.旋转180度
- 3.旋转270度
- 4.水平方向反转
- 5.先水平方向反转，然后旋转1，2，3中的角度
- 6.A B相同
- 7.无法转换
Palindromic Squares
Palindromes are numbers that read the same forwards as backwards. The number 12321 is a typical palindrome.
Given a number base B (2 <= B <= 20 base 10), print all the integers N (1 <= N <= 300 base 10) such that the square of N is palindromic when expressed in base B; also print the value of that palindromic square. Use the letters ‘A’, ‘B’, and so on to represent the digits 10, 11, and so on.
Print both the number and its square in base B.
求[1,300]之间的数字平方按照B进制是回文串的数字
Dual Palindromes
A number that reads the same from right to left as when read from left to right is called a palindrome. The number 12321 is a palindrome; the number 77778 is not. Of course, palindromes have neither leading nor trailing zeroes, so 0220 is not a palindrome.
The number 21 (base 10) is not palindrome in base 10, but the number 21 (base 10) is, in fact, a palindrome in base 2 (10101).
Write a program that reads two numbers (expressed in base 10):
N (1 <= N <= 15)
S (0 < S < 10000)
and then finds and prints (in base 10) the first N numbers strictly greater than S that are palindromic when written in two or more number bases (2 <= base <= 10).
Solutions to this problem do not require manipulating integers larger than the standard 32 bits.
求大于S的N个数，这N个数满足在[2,10]进制下，至少有两个回文串
Section 1.4
Greedy Algorithm
The Idea
The basic idea behind greedy algorithms is to build large solutions up from smaller ones. Unlike other approaches, however, greedy algorithms keep only the best solution they find as they go along. Thus, for the sample problem, to build the answer for N = 5, they find the best solution for N = 4, and then alter it to get a solution for N = 5. No other solution for N = 4 is ever considered.
Greedy algorithms are fast, generally linear to quadratic and require little extra memory. Unfortunately, they usually aren’t correct. But when they do work, they are often easy to implement and fast enough to execute.
Mixing Milk
The Merry Milk Makers company buys milk from farmers, packages it into attractive 1- and 2-Unit bottles, and then sells that milk to grocery stores so we can each start our day with delicious cereal and milk.
Since milk packaging is such a difficult business in which to make money, it is important to keep the costs as low as possible. Help Merry Milk Makers purchase the farmers’ milk in the cheapest possible manner. The MMM company has an extraordinarily talented marketing department and knows precisely how much milk they need each day to package for their customers.
The company has contracts with several farmers from whom they may purchase milk, and each farmer has a (potentially) different price at which they sell milk to the packing plant. Of course, a herd of cows can only produce so much milk each day, so the farmers already know how much milk they will have available.
Each day, Merry Milk Makers can purchase an integer number of units of milk from each farmer, a number that is always less than or equal to the farmer’s limit (and might be the entire production from that farmer, none of the production, or any integer in between).
Given:
- The Merry Milk Makers’ daily requirement of milk
- The cost per unit for milk from each farmer
- The amount of milk available from each farmer
calculate the minimum amount of money that Merry Milk Makers must spend to meet their daily need for milk.
Note: The total milk produced per day by the farmers will always be sufficient to meet the demands of the Merry Milk Makers even if the prices are high.
公司需要从农民手中买N份牛奶;每个农民有自己的出售单价和生产量;
求公司需要的最小花费
Barn Repair
It was a dark and stormy night that ripped the roof and gates off the stalls that hold Farmer John’s cows. Happily, many of the cows were on vacation, so the barn was not completely full.
The cows spend the night in stalls that are arranged adjacent to each other in a long line. Some stalls have cows in them; some do not. All stalls are the same width.
Farmer John must quickly erect new boards in front of the stalls, since the doors were lost. His new lumber supplier will supply him boards of any length he wishes, but the supplier can only deliver a small number of total boards. Farmer John wishes to minimize the total length of the boards he must purchase.
Given M (1 <= M <= 50), the maximum number of boards that can be purchased; S (1 <= S <= 200), the total number of stalls; C (1 <= C <= S) the number of cows in the stalls, and the C occupied stall numbers (1 <= stall_number <= S), calculate the minimum number of stalls that must be blocked in order to block all the stalls that have cows in them.
Print your answer as the total number of stalls blocked.
在一个夜黑风高、下着暴风雨的夜晚，farmer John的牛棚的屋顶、门都被吹飞了。所幸，许多牛都在度假，所以牛棚并没有住满。
牛棚一个挨着一个相邻排列成一行，牛就在里面过夜。一些牛棚里面有牛，而一些没有。所有的牛棚都有相同的宽度。
自从门被吹走后，farmer John必须尽快地在牛棚前建立新的木板。他的新木料供应商将会供应给他任意他想要长度的木板，但是供应商只能够提供少量的木板。Farmer John想要将木板的总长度减到最少。
给出可能买到的木板的最大数目M(1<= M<=50)，每块长度任意；牛棚的总数S(1<= S<=200); 牛棚里牛的总数C(1 <= C <=S);以及牛所在牛棚的编号stall_number(1 <= stall_number <= S),计算拦住所有有牛的牛棚所需木板的最小总长度。
输出你所计算得到的所需木板的最小总长度作为答案。
Prime Cryptarithm
牛式
Combination Lock
Wormholes
虫洞
农夫约翰爱好在周末进行高能物理实验的结果却适得其反，导致N个虫洞在农场上（2<=N<=12，n是偶数），每个在农场二维地图的一个不同点。
根据他的计算，约翰知道他的虫洞将形成 N/2 连接配对。例如，如果A和B的虫洞连接成一对，进入虫洞A的任何对象体将从虫洞B出去，朝着同一个方向，而且进入虫洞B的任何对象将同样从虫洞A出去，朝着相同的方向前进。这可能发生相当令人不快的后果。
例如，假设有两个成对的虫洞A(1，1) 和 B(3，1)，贝茜从(2，1)开始朝着 +x 方向（右）的位置移动。贝茜将进入虫洞 B（在(3,1)），从A出去（在(1,1)），然后再次进入B，困在一个无限循环中！
| . . . .
| A > B . 贝茜会穿过B，A，
+ . . . . 然后再次穿过B
农夫约翰知道他的农场里每个虫洞的确切位置。他知道贝茜总是向 +x 方向走进来，虽然他不记得贝茜的当前位置。请帮助农夫约翰计算不同的虫洞配对（情况），使贝茜可能被困在一个无限循环中，如果她从不幸的位置开始。
Ski Course Design
Farmer John has N hills on his farm (1 <= N <= 1,000), each with an integer elevation in the range 0 .. 100. In the winter, since there is abundant snow on these hills, FJ routinely operates a ski training camp.
Unfortunately, FJ has just found out about a new tax that will be assessed next year on farms used as ski training camps. Upon careful reading of the law, however, he discovers that the official definition of a ski camp requires the difference between the highest and lowest hill on his property to be strictly larger than 17. Therefore, if he shortens his tallest hills and adds mass to increase the height of his shorter hills, FJ can avoid paying the tax as long as the new difference between the highest and lowest hill is at most 17.
If it costs x^2 units of money to change the height of a hill by x units, what is the minimum amount of money FJ will need to pay? FJ can change the height of a hill only once, so the total cost for each hill is the square of the difference between its original and final height. FJ is only willing to change the height of each hill by an integer amount.
农民约翰的农场里有N座山峰(1<=N<=1000),每座山都有一个在0到100之间的整数的海拔高度。在冬天,因为山上有丰富的积雪,约翰经常开办滑雪训练营。
不幸的是,约翰刚刚得知税法在滑雪训练营方面有新变化,明年开始实施。在仔细阅读法律后,他发现如果滑雪训练营的最高和最低的山峰海拔高度差大于17就要收税。因此,如果他改变山峰的高度（使最高与最低的山峰海拔高度差不超过17）,约翰可以避免支付税收。
如果改变一座山x单位的高度成本是x^2单位,约翰最少需要付多少钱?约翰只愿意改变整数单位的高度。
Section 1.5
Search Techniques
Arithmetic Progressions
stl set 檢索
不加此条件会超时1
2
3
4if (N == 3)jbase = 1;
else if (N < 6)jbase = 4;
else if (N < 12)jbase = 12;
else { jbase = 84; }
數組 檢索
Mother’s Milk
三个杯子ABC 来回倒腾牛奶
输入三个杯子ABC的容量
初始AB杯子是空的，C杯子是满的
每次倒腾要么将杯子倒空，要么将目标杯子倒满
求A杯子保持是空的，C杯子的可能牛奶量
Section 1.6
Binary Numbers
Number Triangles
Consider the number triangle shown below. Write a program that calculates the highest sum of numbers that can be passed on a route that starts at the top and ends somewhere on the base. Each step can go either diagonally down to the left or diagonally down to the right.
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
In the sample above, the route from 7 to 3 to 8 to 7 to 5 produces the highest sum: 30.
Prime Palindromes
The number 151 is a prime palindrome because it is both a prime number and a palindrome (it is the same number when read forward as backward). Write a program that finds all prime palindromes in the range of two supplied numbers a and b (5 <= a < b <= 100,000,000); both a and b are considered to be within the range .
统计a-b之间的数 既是素数，又是回文的数
b的最大值是10的八次方 枚举会超时
先求出所有的回文组合，然后判断是不是素数
b最大时10的八次方
数字格式 abcdedcba
数字的前半部分随意组合 也就是 0-100000 之间
然后生成回文数字，判断数字是否时素数
Superprime Rib
Butchering Farmer John’s cows always yields the best prime rib. You can tell prime ribs by looking at the digits lovingly stamped across them, one by one, by FJ and the USDA. Farmer John ensures that a purchaser of his prime ribs gets really prime ribs because when sliced from the right, the numbers on the ribs continue to stay prime right down to the last rib, e.g.:
7 3 3 1
The set of ribs denoted by 7331 is prime; the three ribs 733 are prime; the two ribs 73 are prime, and, of course, the last rib, 7, is prime. The number 7331 is called a superprime of length 4.
Write a program that accepts a number N 1 <=N<=8 of ribs and prints all the superprimes of that length.
The number 1 (by itself) is not a prime number.
超级素数
n位的超级素数等于 (n-1)*10+{ 1,3,5,7,9 } 的组合中的的素数
f(n)=IsPrime(f(n-1)+{ 1,3,5,7,9 })