Daddy's Journey to Platinum

Sorting is one of the most frequently performed computational tasks. Consider the special sorting problem in which the records to be sorted have at most three different key values. This happens for instance when we sort medalists of a competition according to medal value, that is, gold medalists come first, followed by silver, and bronze medalists come last.

In this task the possible key values are the integers 1, 2 and 3. The required sorting order is non-decreasing. However, sorting has to be accomplished by a sequence of exchange operations. An exchange operation, defined by two position numbers p and q, exchanges the elements in positions p and q.

You are given a sequence of key values. Write a program that computes the minimal number of exchange operations that are necessary to make the sequence sorted.

Line 1: N (1 <= N <= 1000), the number of records to be sorted
Lines 2-N+1: A single integer from the set {1, 2, 3}

A single line containing the number of exchanges required

9 
2 
2 
1 
3 
3 
3 
2 
3 
1

4 

정렬할 입력을 저장하면서, 1, 2, 3 숫자를 기록한다. bubble sort와 비슷한 방법으로 진행한다. 2보다 뒤쪽에 있는 1들을 2와 바꾼다. 3보다 뒤에 있는 1들을 3과 바꾼다. 마지막으로 3보다 뒤에 있는 2들을 3과 바꾼다. 

Consider the set of all reduced fractions between 0 and 1 inclusive with denominators less than or equal to N.

Here is the set when N = 5:

0/1 1/5 1/4 1/3 2/5 1/2 3/5 2/3 3/4 4/5 1/1
Write a program that, given an integer N between 1 and 160 inclusive, prints the fractions in order of increasing magnitude.

One line with a single integer N.

One fraction per line, sorted in order of magnitude. 

5

0/1
1/5
1/4
1/3
2/5
1/2
3/5
2/3
3/4
4/5
1/1 

받은 N보다 작은 정수들로 정수쌍 ( i, j ) 를 만들고 첫번째 수는 0, 마지막 수는 1/1 로 해서 vector에 저장한다. 이때 두수가 서로 서로소가 아닌 경우는 제외한다. 왜냐하면 1/2 = 2/4 = 3/6 ..이 되지만, 문제에서는 1/2만 출력해야 한다. vector를 정렬하는데, (a, b) vs (c, d)의 크기 비교는 a/b vs c/d => ad/bd vs bc/bd => ad vs bc 로 비교하도록 했다.

Runaround numbers are integers with unique digits, none of which is zero (e.g., 81362) that also have an interesting property, exemplified by this demonstration:

If you start at the left digit (8 in our number) and count that number of digits to the right (wrapping back to the first digit when no digits on the right are available), you'll end up at a new digit (a number which does not end up at a new digit is not a Runaround Number). Consider: 8 1 3 6 2 which cycles through eight digits: 1 3 6 2 8 1 3 6 so the next digit is 6.
Repeat this cycle (this time for the six counts designed by the `6') and you should end on a new digit: 2 8 1 3 6 2, namely 2.
Repeat again (two digits this time): 8 1
Continue again (one digit this time): 3
One more time: 6 2 8 and you have ended up back where you started, after touching each digit once. If you don't end up back where you started after touching each digit once, your number is not a Runaround number.
Given a number M (that has anywhere from 1 through 9 digits), find and print the next runaround number higher than M, which will always fit into an unsigned long integer for the given test data.

A single line with a single integer, M

A single line containing the next runaround number higher than the input value, M.

81361

81362

입력받는 숫자는 최대 9자리가 가능하다. (중복없이 1~9) 두개의 배열을 만들어서, 유일성 검사를 하고, 문제 조건대로 각 자리수 숫자에 도착했는지 검사한다. 숫자 자리수 만큰 움직여서, 모든 자리수에 도착했으면 통과, 아니면 실패하도록 한다. 숫자 자리수 순환 시키는 것은 % 연산으로 처리한다.

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.

A single line with the number N.

The superprime ribs of length N, printed in ascending order one per line.

4

2333
2339
2393
2399
2939
3119
3137
3733
3739
3793
3797
5939
7193
7331
7333
7393

제일 왼쪽에 올 수 있는 숫자는 2/3/5/7 (한자리수 소수)만 올 수 있다. 또한 두자리수 이상의 수에서 제일 앞을 제외한 모든 자리수는 (1/3/7/9) 만이 가능하다. 이 조건을 만족하도록, 왼쪽에서부터 숫자를 만들어 출력한다.

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 .

Line 1: Two integers, a and b

The list of palindromic primes in numerical order, one per line.

5 500

5
7
11
101
131
151
181
191
313
353
373
383

자리수가 짝수인 palindrome 은 11의 배수 이므로, 자리수가 홀수인 숫자들을 만들어서 소수인지 검사한다.  다만, 소수는 2를 제외하면 모두 짝수이고, 끝자리가 0/5인 경우도 5의 배수가 된다. 또, 자리수 합이 3의 배수이면 3의 배수가 된다. 이런 몇가지 검사를 통과한 수들을 대상으로 소수검사를 시행한다.

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.

The first line contains R (1 <= R <= 1000), the number of rows. Each subsequent line contains the integers for that particular row of the triangle. All the supplied integers are non-negative and no larger than 100.

A single line containing the largest sum using the traversal specified.

5 
7 
3 8 
8 1 0 
2 7 4 4 
4 5 2 6 5

30

읽어 들인 입력들을 2차원 배열에 저장한다. 첫번째 입력부터 아래로 내려가면서 더해간다. 양쪽에서 도착할 수 있는 경우, 2개위 상위 수에서 큰수를 기준으로 한다. 이렇게 마지막 행에 도착해서, 제일 큰 수를 출력한다. 

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이 존재하는지 확인하고, 결과값을 증가시킨다.