Daddy's Journey to Platinum

An arithmetic progression is a sequence of the form a, a+b, a+2b, ..., a+nb where n=0, 1, 2, 3, ... . For this problem, a is a non-negative integer and b is a positive integer.

Write a program that finds all arithmetic progressions of length n in the set S of bisquares. The set of bisquares is defined as the set of all integers of the form p^2 + q^2 (where p and q are non-negative integers).

TIME LIMIT: 5 secs

INPUT FORMAT
Line 1: N (3 <= N <= 25), the length of progressions for which to search
Line 2: M (1 <= M <= 250), an upper bound to limit the search to the bisquares with 0 <= p,q <= M.

If no sequence is found, a single line reading `NONE'. Otherwise, output one or more lines, each with two integers: the first element in a found sequence and the difference between consecutive elements in the same sequence. The lines should be ordered with smallest-difference sequences first and smallest starting number within those sequences first. 

There will be no more than 10,000 sequences.

5 
7

1 4
37 4
2 8
29 8
1 12
5 12
13 12
17 12
5 20
2 24

먼저, 제곱수들의 합들의 집합을 만든다. 이때, 집합의 값들을 같이 저장해두고, 검색할때 참고한다. 

검색하는 대상을 줄일 수 있는 방법을 찾는다. 일단,  a + b*n 이라고 수열을 정의한다. 

N개의 수열이 모두 집합에 있다고 하면,  a + b * (N-1) < 2 * M * M  이 된다. 여기에서 b의 범위를 축소하면,  b < 2*M*M/(N-1) 이 된다. 또, 제곱수들의 합인 집합에서 더하는 제곱수들이 커지면 집합내의 수들의 간격이 넓어진다.

3^2 + 4^2 = 25, 4^2+4^2 = 32  gap : 9 vs. 100^2 + 100^2 = 200, 100^2 + 101^2 = 221 gap: 21

그러므로, 만들어진 수  a + b * (N-1) 가 제곱수 합의 집합에 있는지 검사할 때는 큰 수들에서부터 검색하면 없는 경우를 더 빨리 찾을 수 있다.

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.

Line 1: The integer N.
Lines 2..1+N: Each line contains the elevation of a single hill.

The minimum amount FJ needs to pay to modify the elevations of his hills so the difference between largest and smallest is at most 17 units.

5 
20 
4 
1 
24 
21 

18 

가능한 높이차들 (100, 83) ~ (17,0) 안으로 모든 산들을 갈아 넣는다. 이렇게 만든 작업량중에 가장 제일 적은 것을 찾는다.

Farmer John's hobby of conducting high-energy physics experiments on weekends has backfired, causing N wormholes (2 <= N <= 12, N even) to materialize on his farm, each located at a distinct point on the 2D map of his farm (the x,y coordinates are both integers).

According to his calculations, Farmer John knows that his wormholes will form N/2 connected pairs. For example, if wormholes A and B are connected as a pair, then any object entering wormhole A will exit wormhole B moving in the same direction, and any object entering wormhole B will similarly exit from wormhole A moving in the same direction. This can have rather unpleasant consequences.

For example, suppose there are two paired wormholes A at (1,1) and B at (3,1), and that Bessie the cow starts from position (2,1) moving in the +x direction. Bessie will enter wormhole B [at (3,1)], exit from A [at (1,1)], then enter B again, and so on, getting trapped in an infinite cycle!

   | . . . .
   | A > B .      Bessie will travel to B then
   + . . . .      A then across to B again
Farmer John knows the exact location of each wormhole on his farm. He knows that Bessie the cow always walks in the +x direction, although he does not remember where Bessie is currently located.

Please help Farmer John count the number of distinct pairings of the wormholes such that Bessie could possibly get trapped in an infinite cycle if she starts from an unlucky position. FJ doesn't know which wormhole pairs with any other wormhole, so find all the possibilities (i.e., all the different ways that N wormholes could be paired such that Bessie can, in some way, get in a cycle). Note that a loop with a smaller number of wormholes might contribute a number of different sets of pairings to the total count as those wormholes that are not in the loop are paired in many different ways.

Line 1: The number of wormholes, N.
Lines 2..1+N: Each line contains two space-separated integers describing the (x,y) coordinates of a single wormhole. Each coordinate is in the range 0..1,000,000,000.

Line 1: The number of distinct pairings of wormholes such that Bessie could conceivably get stuck in a cycle walking from some starting point in the +x direction.

4 

0 0 
1 0 
1 1 
0 1

2 

각각의 홀들을 node로 하고, 두 홀들을 연결하는 웜홀을 edge로 생각해서, graph 에 cycle이 존재하는지 확인하고, 결과값을 증가시킨다.  

Farmer John's cows keep escaping from his farm and causing mischief. To try and prevent them from leaving, he purchases a fancy combination lock to keep his cows from opening the pasture gate.

Knowing that his cows are quite clever, Farmer John wants to make sure they cannot easily open the lock by simply trying many different combinations. The lock has three dials, each numbered 1..N (1 <= N <= 100), where 1 and N are adjacent since the dials are circular. There are two combinations that open the lock, one set by Farmer John, and also a "master" combination set by the lock maker.

The lock has a small tolerance for error, however, so it will open even if the numbers on the dials are each within at most 2 positions of a valid combination.

For example, if Farmer John's combination is (1,2,3) and the master combination is (4,5,6), the lock will open if its dials are set to (1,3,5) (since this is close enough to Farmer John's combination) or to (2,4,8) (since this is close enough to the master combination). Note that (1,5,6) would not open the lock, since it is not close enough to any one single combination.

Given Farmer John's combination and the master combination, please determine the number of distinct settings for the dials that will open the lock. Order matters, so the setting (1,2,3) is distinct from (3,2,1).

Line 1: The integer N.
Line 2: Three space-separated integers, specifying Farmer John's combination.
Line 3: Three space-separated integers, specifying the master combination (possibly the same as Farmer John's combination).

Line 1: The number of distinct dial settings that will open the lock.

50 
1 2 3 
5 6 7

249

입력받은 수에서 각 자리수들이 가능한 영역을 결정하고, 가능한 모든 3자리 수를 만들어서 set에 입력한다. 중복되는 조합은 set 특성에 의해서 없어지므로, set에 입력된 조합의 개수를 출력한다.

A cryptarithm is usually presented as a pencil-and-paper task in which the solver is required to substitute a digit for each of the asterisks (or, often, letters) in the manual evaluation of an arithmetic term or expression so that the consistent application of the digits results in a proper expression. A classic example is this cryptarithm, shown with its unique solution:

    SEND           9567       S->9 E->5 N->6 D->7

+ MORE       + 1085        M->1 O->0 R->8

   -------           -------

 MONEY          10652      Y->2

The following cryptarithm is a multiplication problem that can be solved by substituting digits from a specified set of N digits into the positions marked with *. Since the asterisks are generic, any digit from the input set can be used for any of the asterisks; any digit may be duplicated as many times as desired.

Consider using the set {2,3,5,7} for the cryptarithm below:

 * * *

 x * *

 -------

 * * * <-- partial product 1 -- MUST BE 3 DIGITS LONG

* * * <-- partial product 2 -- MUST BE 3 DIGITS LONG

-------

* * * *

Digits can appear only in places marked by `*'. Of course, leading zeroes are not allowed.

Line 1:N, the number of digits that will be used

Line 2:N space separated non-zero digits with which to solve the cryptarithm

A single line with the total number of solutions. Here is the one and only solution for the sample input:

5

2 3 4 6 8

1

입력받은 수들을 set에 정리하고, 임의로 3자리수, 2자리수를 만들어서 계산을 했다. 그래서, 나오는 수들이 모두 집합에 있는지 확인해서, 있으면 (aaa, bb)를 기록해서 출력한다.

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.

Line 1: M, S, and C (space separated)
Lines 2-C+1: Each line contains one integer, the number of an occupied stall.

A single line with one integer that represents the total number of stalls blocked.

4 50 18 
3 
4 
6 
8 
14 
15 
16 
17 
21 
25 
26 
27 
30 
31 
40 
41 
42 
43

25

소들을 순서대로 정렬한다. 제일 처음과 제일 마지막 소를 다 가릴 수 있는 긴 보드에서 시작한다. 각 소들 사이에 간격들을 계산해서 정렬한다. 가장 넓은 간격부터 긴 보드에서 제거해나가서 필요한 보드를 완성한다 

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.

Line 1: Two integers, N and M.
The first value, N, (0 <= N <= 2,000,000) is the amount of milk that Merry Milk Makers wants per day.
The second, M, (0 <= M <= 5,000) is the number of farmers that they may buy from.
Lines 2 through M+1: The next M lines each contain two integers: Pi and Ai.
Pi (0 <= Pi <= 1,000) is price in cents that farmer i charges.
Ai (0 <= Ai <= 2,000,000) is the amount of milk that farmer i can sell to Merry Milk Makers per day.

A single line with a single integer that is the minimum cost that Merry Milk Makers must pay for one day's milk.

100 5 
5 20 
9 40 
3 10 
8 80 
6 30

630

farmer unit price 를 기준으로 정렬해서, 가격이 낮은 순으로 최대한 사들이여서 필요한 양을 맞추도록 한다.

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.

A single line with space separated integers N and S.

N lines, each with a base 10 number that is palindromic when expressed in at least two of the bases 2..10. The numbers should be listed in order from smallest to largest.

3 25

26
27
28

숫자 N과 S를 읽어서, S보다 큰 수중에서 이진법~십진법으로 바꿨을때 palindrome 이 두번 이상되는 N개의 수를 작은 순서대로 출력하는 문제이다. S에서 시작되는 루프를 돌리면서, 이진법~10진법으로 변환해서 palindrome 이 되는 경우가 2번 되면, 그 숫자를 결과 목록에 추가하고, 결과 목록이 N개가 되면 출력한다. 

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.

A single line with B, the base (specified in base 10).

Lines with two integers represented in base B. The first integer is the number whose square is palindromic; the second integer is the square itself. NOTE WELL THAT BOTH INTEGERS ARE IN BASE B!

10

1 1
2 4
3 9
11 121
22 484
26 676
101 10201
111 12321
121 14641
202 40804
212 44944
264 69696

십진수 (1<= N <= 300) 중에서 N^2 이 이진수부터 20진수(2<=B <=20)  중에 주어진 진법으로 변환했을때 Palindrome 이 되는 모든 수를 찾아서 출력하는 것이다. N 에 대해서 루프를 돌면서, N^2 를 주어진 진법으로 바꿔서, palindrome 인지 확인하고 해당하는 idx=N을 결과값 목록에 넣어둔다. 출력하면서, N, N^2 주어진 진법으로 변환해서 출력한다.