Daddy's Journey to Platinum

There are n children who want to go to a Ferris wheel, and your task is to find a gondola for each child.

Each gondola may have one or two children in it, and in addition, the total weight in a gondola may not exceed xx. You know the weight of every child.

What is the minimum number of gondolas needed for the children?

The first input line contains two integers n and x: the number of children and the maximum allowed weight.

The next line contains n integers p_1,p_2,…,p_n: the weight of each child.

Print one integer: the minimum number of gondolas.

4 10
7 2 3 9

3

• 1 <= n <= 2x1e5  
• 1 <= x <= 1e9 
• 1 <= p_i <= x

무게를 입력받아서 정렬하고, 앞쪽(left)와 뒤쪽(right) 아이의 몸무게를 합쳐서 제한무게와 비교한다.

작으면, 곤돌라 하나에 탑승시키고(left+1, right-1), 무거우면 무거운 아이 혼자 타도록 한다.(right-1)  

There are n applicants and m free apartments. Your task is to distribute the apartments so that as many applicants as possible will get an apartment.

Each applicant has a desired apartment size, and they will accept any apartment whose size is close enough to the desired size.

The first input line has three integers n, m, and k: the number of applicants, the number of apartments, and the maximum allowed difference.

The next line contains n integers a_1,a_2,…,a_n: the desired apartment size of each applicant. If the desired size of an applicant is x, he or she will accept any apartment whose size is between x−k and x+k.

The last line contains mm integers b_1,b_2,…,b_m: the size of each apartment.

Print one integer: the number of applicants who will get an apartment.

4 3 5
60 45 80 60
30 60 75

2

• 1 <= n,m <= 2x10^5
• 0 <= k <= 10^9 
• 1 <= a_i, b_i <= 10^9

아파트 크기와 원하는 크기를 입렵 받아서 작은 순서로 정렬한다.

원하는 크기와 감당할 수 있는 크기차이와 주어진 아파트의 크기를 비교해서, 가능한 방들을 출력한다.

You are given a list of n integers, and your task is to calculate the number of distinct values in the list.

The first input line has an integer n: the number of values.

The second line has n integers x_1,x_2,…,x_n 

Print one integers: the number of distinct values.

5
2 3 2 2 3

2

• 1 <= n <= 2x10^5
• 1 <= x_i <= 10^9

입력을 읽어 들여서 set에 입력하여 중복을 제거하고,  set size를 출력한다.

Your task is to place eight queens on a chessboard so that no two queens are attacking each other. As an additional challenge, each square is either free or reserved, and you can only place queens on the free squares. However, the reserved squares do not prevent queens from attacking each other.

How many possible ways are there to place the queens?

The input has eight lines, and each of them has eight characters. Each square is either free (.) or reserved (*).

Print one integer: the number of ways you can place the queens.

........
........
..*.....
........
........
.....**.
...*....
........

65

NxN보드에서 N개의 Queen을 서로 공격하지 않도록 배열하는 N-Queen 문제이다. 첫번째 열부터 퀸을 하나 배치하고, 공격 받을 수 있는 위치들을 표시하고 8번째 열에 도착하면 경우의 수를 기록한다.

There are n apples with known weights. Your task is to divide the apples into two groups so that the difference between the weights of the groups is minimal.

The first input line has an integer n: the number of apples.

The next line has n integers p_1,p_2,…,p_n: the weight of each apple.

Print one integer: the minimum difference between the weights of the groups.

5
3 2 7 4 1

1

• 1 <= n <= 20
• 1 <= p_i <= 10^9

입력받은 사과들을 양쪽에 각각 넣어보고 무게 차의 최소 값을 찾는다.

Given a string, your task is to generate all different strings that can be created using its characters.

The only input line has a string of length n. Each character is between a–z.

First print an integer k: the number of strings. Then print k lines: the strings in alphabetical order.

aabac

20
aaabc
aaacb
aabac
aabca
aacab
aacba
abaac
abaca
abcaa
acaab
acaba
acbaa
baaac
baaca
bacaa
bcaaa
caaab
caaba
cabaa
cbaaa

1 ≤ n ≤ 8

문자열을 읽어 들인다음, 정렬한다. next_permutation() 기능을 이용해서 새로운 문자열을 만들고 set<string>에 저장한다. set에 저장된 문자열 개수와 문자열들을 출력한다.

You have two coin piles containing a and b coins. On each move, you can either remove one coin from the left pile and two coins from the right pile, or two coins from the left pile and one coin from the right pile.

Your task is to efficiently find out if you can empty both the piles.

The first input line has an integer t: the number of tests.

After this, there are t lines, each of which has two integers a and b: the numbers of coins in the piles.

For each test, print "YES" if you can empty the piles and "NO" otherwise.

3
2 1
2 2
3 3

YES
NO
YES

• 1 <= t <= 10^5
• 0 <= a,b <= 10^9

두개의 입력 a, b를 이용해서 가능한 조건들을 검사한다.

먼저, 한번에 제거 가능한 숫자는 3개 이므로, 두개의 합이 3의 배수가 아니면 불가능하다. 왼쪽에서 2개 제거하는 수를 x, 오른쪽에서 2개 제거하는 수를 y로 해서 계산한다.

더할 수는 없으므로 하나라도 음수이면 불가능하다. (x < 0 || y <0)

한쪽의 입력이 다른 쪽의 2배보다 크면 불가능하다. (a > 2b || 2a < b)

두 입력의 차가 abs(a-b) = abs(x-y) 이면, 모두 없애는게 가능하므로, 이 조건까지 확인해서 결과를 출력한다.  

Your task is to calculate the number of trailing zeros in the factorial n!n!.

For example, 20!=2432902008176640000 and it has 4 trailing zeros.

The only input line has an integer n.

Print the number of trailing zeros in n!.

20

4

1 <= n <= 10^9

팩토리얼에서 뒤에 나오는 0의 갯수는 N보다 작은 수중에서 곱해지는 5나 5의 거듭제곱수들이 몇번인가와 같다. 그래서, 5로 계속 나누면서 나오는 수들을 누적해서 출력한다. 엄밀하게는 2와 2의 거듭제곱수들의 빈도수와 비교해야 한다.

Your task is to divide the numbers 1,2,…,n into two sets of equal sum.

The only input line contains an integer n.

Print "YES", if the division is possible, and "NO" otherwise.

After this, if the division is possible, print an example of how to create the sets. First, print the number of elements in the first set followed by the elements themselves in a separate line, and then, print the second set in a similar way.

Example 1.

7

Example 2.

6

Example 1.

YES
4
1 2 4 7
3
3 5 6

Example 2.

NO

1 <= n  <= 1e6

입력받은 n 이 4k 혹은 4k+3 인 경우에만 YES가 된다. ( (n+1)*n/2/2 == 0 ) n이 4k+3 형태인 경우와 4k 형태인 경우로 나누고, 4개 혹은 3개 그룹을 같도록 나누어서 출력한다.