Daddy's Journey to Platinum

자물쇠 숫자 3개를 tuple<int, int, int>로 처리하고, 숫자 사이의 차이를 abs 이용해서 계산한다. 다만, modulo 연산에서 -를 지원하지 않기 때문에 dial number - 2 ( modulo -2) 보다 큰 경우도 고려한다. 3중 루프를 O(N^3)이지만 최대 dial number 100 을 생각하면, 속도에 문제가 될 것 같지는 않다. 필요하다면, key number 에서 5x5x5 로 가능한 숫자 배열을 작성하고, 그 배열 숫자들로만 루프를 돌리면 좀 더 빨라질 것 같다. 중복 제거를 위해서 set 에 무조건 입력하고, 중복이 제거된 결과의 수만 조회 했는데, 입력하기 전에 조회를 하고 없으면 입력하도록 하는것도 방법이 될 수는 있을 것 같다. 효율성은 find를 하고 없으면 입력하는것이 조금은 더 좋을 것 같다.

Farmer John has three milking buckets of capacity A, B, and C liters. Each of the numbers A, B, and C is an integer from 1 through 20, inclusive. Initially, buckets A and B are empty while bucket C is full of milk. Sometimes, FJ pours milk from one bucket to another until the second bucket is filled or the first bucket is empty. Once begun, a pour must be completed, of course. Being thrifty, no milk may be tossed out. 

Write a program to help FJ determine what amounts of milk he can leave in bucket C when he begins with three buckets as above, pours milk among the buckets for a while, and then notes that bucket A is empty.

A single line with the three integers A, B, and C.

A single line with a sorted list of all the possible amounts of milk that can be in bucket C when 
bucket A is empty.

8 9 10

1 2 8 9 10

water jug problem 이라고 불리는 물통 사이에서 물을 옮기는 문제이다. 여기서는 물통 3개를 이용하므로, 3 water jug problem이라고 할 수 있다. 시작할때 가지고 있는 물의 양(0, 0, C)에서 물통 사이에서 한번에 옮길 수 있는 6가지 경우들을 재귀적으로 검색한다. 한번 검색한 곳은 다시 검색하지 않도록 확인해서, 검색을 종료하도록 한다. 문제 조건에 따라서 물통 A가 비어 있을때 물통 C의 양을 기록해서 출력한다.

The cows have not only created their own government but they have chosen to create their own money system. In their own rebellious way, they are curious about values of coinage. Traditionally, coins come in values like 1, 5, 10, 20 or 25, 50, and 100 units, sometimes with a 2 unit coin thrown in for good measure.
The cows want to know how many different ways it is possible to dispense a certain amount of money using various coin systems. For instance, using a system of {1, 2, 5, 10, ...} it is possible to create 18 units several different ways, including: 18x1, 9x2, 8x2+2x1, 3x5+2+1, and many others.
Write a program to compute how many ways to construct a given amount of money using supplied coinage. It is guaranteed that the total will fit into both a signed long long (C/C++) and Int64 (Free Pascal).

The number of coins in the system is V (1 <= V <= 25).
The amount money to construct is N (1 <= N <= 10,000).

Line 1: Two integers, V and N
Lines 2..: V integers that represent the available coins (no particular number of integers per line)

A single line containing the total number of ways to construct N money units using V coins.

3 10 
1 2 5

10

특정한 정수 집합으로 원하는 값을 만들어내는 경우의 수를 세는 문제로 coin change 문제이다. 

특정한 코인 값 c[i] =a 라고 하면, 원하는 값 target 를 만들 수 있는 방법은 이 코인이 없이 만들수 있는 경우의 수와 이 코인 값을 제외한 값을 만들수 있는 경우의 수의 합이 된다. 

 v(target, b) = v(target, a) + v(target-b, b) 

다만, 이 경우에는 코인의 수는 제한이 없기 때문에, 코인 값의 배수들에 해당하는 값들을 모두 확인해야 한다.

참고: subset sum problem ( link )

For many sets of consecutive integers from 1 through N (1 <= N <= 39), one can partition the set into two sets whose sums are identical. 

For example, if N=3, one can partition the set {1, 2, 3} in one way so that the sums of both subsets
are identical:

• {3} and {1,2}

This counts as a single partitioning (i.e., reversing the order counts as the same partitioning and
thus does not increase the count of partitions).
If N=7, there are four ways to partition the set {1, 2, 3, ... 7} so that each partition has the same
sum:

• {1,6,7} and {2,3,4,5}
• {2,5,7} and {1,3,4,6}
• {3,4,7} and {1,2,5,6}
• {1,2,4,7} and {3,5,6}

Given N, your program should print the number of ways a set containing the integers from 1 through N can be partitioned into two sets whose sums are identical. Print 0 if there are no such ways. 

Your program must calculate the answer, not look it up from a table.

The input file contains a single line with a single integer representing N, as above.

The output file contains a single line with a single integer that tells how many same-sum partitions can be made from the set {1, 2, ..., N}. The output file should contain 0 if there are no ways to make a same-sum partition.

7

4

{1, 2, ..., N} 인 집합을 합이 같은 2개의 집합으로 나누는 경우의 수를 구하는 문제이다. 전체의 합은 N*(N+1)/2 이고 이것을 2개의 같은 값으로 나누는 것이기 때문에 N*(N+1)/4 = k. 즉, N % 4 = 0 or -1(3) 인 경우만 가능하다. 

이 경우의 수는 조건에 맞는 모든 부분집합을 찾아서 그 수를 구할 수 있다. N = 4K 인 경우는 A = { (1, 4), (5,8), ..., (4K+1, 4K+4)}, B = { (2, 3), (6,7), ... , (4K+2, 4K+3)} 의 두 집합으로 나눈뒤 한쪽의 특정한 값을 가진 수의 조합을 다른 쪽에서 같은 값을 가진 조합으로 변경해서, 다른 집합들을 찾을 수 있다. N = 4K+3 인 경우는 A = { (1,2), (5,5), ... (4K+1, 4K+2)}, B = { (0,3), (4, 7), ... , (4K, 4K+3)}으로 초기 집합을 나눌 수 있다.

부분 집합들을 직접 찾지 않고, 아래 같은 규칙을 이용해서 경우의 수를 세는 것도 가능하다.  다만 어떤 부분 집합이 가능한지는 알 수 없다.

A(i+1, K) 의 값은 새로운 수 (i+1)이 원하는 합을 만드는데 사용한 경우< A(i+1, K-(i+1))>와 사용하지 않는 경우<A(i, K)>의 합이 된다.  A(i+1, K) = A(i, K) + A(i+1, K-(i+1))

이 값들을 구하는데,  A(0,0) = 1. (empty set), A(k, 0) = 1(empty set) 을 가지고 시작해서 완성한다.

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개위 상위 수에서 큰수를 기준으로 한다. 이렇게 마지막 행에 도착해서, 제일 큰 수를 출력한다.