Daddy's Journey to Platinum

In a movie festival n movies will be shown. You know the starting and ending time of each movie. What is the maximum number of movies you can watch entirely?

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

After this, there are n lines that describe the movies. Each line has two integers aa and bb: the starting and ending times of a movie.

Print one integer: the maximum number of movies.

3
3 5
4 9
5 8

2

• 1 <= n <= 2x10^5
• 1 <= a < b <= 10^9

영화가 끝나는 시간을 기준으로 정렬한다.

영화 끝나는 시간이 다음 영화 시작 시간 전에 끝나면, 볼 수 있는 영화편수를 증가시키고, 영화 끝나는 시간을 다음 영화 시간으로 갱신한다.  

You are given the arrival and leaving times of n customers in a restaurant.

What was the maximum number of customers?

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

After this, there are n lines that describe the customers. Each line has two integers a and b: the arrival and leaving times of a customer.

You may assume that all arrival and leaving times are distinct.

Print one integer: the maximum number of customers.

3
5 8
2 4
3 9

2

• 1 <= n <= 2x10^5
• 1 <= a < b <= 10^9

입력받은 시간들을 priority queue 에 저장한다.

단, 먼저 도착한 사람이 앞쪽에 나오도록 모두 음수로 만든다.

저장된 queue 의 제일 위쪽에 있는 자료를 확인해서, 도착 시간이면 +1, 떠난 시간이면 -1을 누적한다.

이렇게 누적한 손님 수중에서 가장 큰 값을 출력한다.

There are n concert tickets available, each with a certain price. Then, m customers arrive, one after another.

Each customer announces the maximum price he or she is willing to pay for a ticket, and after this, they will get a ticket with the nearest possible price such that it does not exceed the maximum price.

The first input line contains integers n and m: the number of tickets and the number of customers.

The next line contains n integers h_1,h_2,…,h_n: the price of each ticket.

The last line contains mm integers t_1,t_2,…,t_m: the maximum price for each customer.

Print, for each customer, the price that they will pay for their ticket. After this, the ticket cannot be purchased again.

5 3
5 3 7 8 5
4 8 3

If a customer cannot get any ticket, print −1.

3
8
-1

• 1 <= n,m <= 2x10^5
• 1 <= h_i, t_i <= 10^9

티켓 가격을 multiset에 저장하고, 희망 가격으로 lower_bound를 찾는다.

그 가격보다 낮은 가격이 있으면 출력하고, 없으면 -1을 출력한다.

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에 저장된 문자열 개수와 문자열들을 출력한다.