알고리즘을 좋아하는 나

바야흐로 지금은 대해적 시대, 밀짚모자 해적단의 선장 교정이는 어린 시절 우연히 잊지 못할 한 마디를 들었다. 그것은 바로 해적 왕 골.D.상윤이 자신이 모은 모든 보물인 원피스를 위대한 항로에 놓고 왔다는 것이었다. 원피스를 가진 자는 이 세상을 가질 수 있다는 매혹적인 얘기였다.

모두들 말도 안 된다고 고개를 저었지만 교정이는 동료를 모아 원피스를 찾아 여행을 떠났다. 하늘섬을 지나 어인섬도 지나고 사황을 무너뜨린 뒤 교정이와 동료들은 결국 원피스의 위치가 적힌 결정적인 단서를 찾아냈다. 이 단서는 한 눈에 봐서는 해독이 어려웠다. 왜냐하면 여기에는 그저 알파벳 대문자들이 연속해서 적혀있었기 때문이다.

하지만 천재적인 두뇌를 가진 교정이의 동료이자 해적단의 항해사 진아는 단번에 이 단서에 어떤 특정 문자열이 여러 번 등장한다는 것을 직감했다.

이 특정 문자열이 어떤 문자열인지는 잘 알 수 없었던 진아는 자신이 생각한 모든 문자열이 이 단서에서 총 몇 번 등장하는지 알아보기로 했다. 아마도 가장 많이 등장한 문자열이 원피스의 위치를 알려줄 것이라고 생각했기 때문이다.

진아는 밀짚모자 해적단의 프로그래밍 담당인 당신에게 도움을 요청했다. 단서 전체에 진아가 원하는 문자열이 몇 번 등장하는지 알아내는 프로그램을 작성하라.

입력의 첫 줄에는 해적단이 획득한 단서의 문자열 H가 주어진다.(0 < |H| ≤ 100,000)

입력의 두 번째 줄에는 진아가 H에서 등장 횟수를 알고 싶은 문자열 N이 주어진다.(0 < |N| ≤ 10)

단, N과 H는 공백 없는 문자열로 주어지며, 모두 알파벳 대문자로 이루어져 있다.

H에서 N이 몇 번 등장하는지 출력한다.

선영이는 집 호수에 반복되는 숫자가 있는 경우에는 그 집에 사는 사람에게 불운이 찾아온다고 믿는다. 따라서, 선영이는 838호나 1004와같이 한 숫자가 두 번 이상 들어있는 집에는 절대 살지 않을 것이다.

2050년, 선영이는 한국에서 가장 돈이 많은 사람이 되었다. 그녀는 해변가에 새로운 호텔을 하나 지으려고 한다. 하지만, 투숙객에게 불운이 찾아오는 것을 피하기 위해서 반복되는 숫자가 없게 방 번호를 만드려고 한다.

정부는 선영이의 호텔 방 번호는 N보다 크거나 같고, M보다 작거나 같아야 한다는 조건을 걸고 신축 허가를 내주었다. 선영이의 새 호텔에는 방이 최대 몇 개 있을 수 있을까? (두 방이 같은 방 번호를 사용할 수 없다)

입력은 여러 개의 테스트 케이스로 이루어져 있고, 한 줄이다. 각 줄에는 문제의 설명에 나와있는 N과 M이 주어진다. (1 ≤ N ≤ M ≤ 5000)

각각의 테스트 케이스에 대해서 N보다 크거나 같고, M보다 작거나 같은 수 중에서 반복되는 숫자가 없는 것의 개수를 출력한다.

어떤 수들이 있을 때, 그 수들을 대표하는 값으로 가장 흔하게 쓰이는 것은 평균이다. 평균은 주어진 모든 수의 합을 수의 개수로 나눈 것이다. 예를 들어 10, 40, 30, 60, 30, 20, 60, 30, 40, 50의 평균은

이 된다.

평균 이외의 또 다른 대표값으로 최빈값이라는 것이 있다. 최빈값은 주어진 수들 가운데 가장 많이 나타나는 수이다. 예를 들어 10, 40, 30, 60, 30, 20, 60, 30, 40, 50 이 주어질 경우,

30 이 세 번,

40 과 60 이 각각 두 번,

10, 20, 50 이 각각 한 번씩 나오므로, 최빈값은 30 이 된다.

열 개의 자연수가 주어질 때 이들의 평균과 최빈값을 구하는 프로그램을 작성하시오.

첫째 줄부터 열 번째 줄까지 한 줄에 하나씩 자연수가 주어진다. 주어지는 자연수는 1,000 보다 작은 10 의 배수이다.

첫째 줄에는 평균을 출력하고, 둘째 줄에는 최빈값을 출력한다. 최빈값이 둘 이상일 경우 그 중 하나만 출력한다. 평균과 최빈값은 모두 자연수이다.

회의가 끝났고, 이제 악수를 하는 시간이다. 모든 사람은 직사각형 탁자 하나의 한 면에 앉아있다.

자리를 벗어나지 않고 악수를 하는 방법의 수는 총 몇 가지일까?

각 사람들은 자신의 왼쪽이나 오른쪽에 있는 사람들과 악수를 할 수 있다. (안 할 수도 있다)

첫째 줄에 회의에 참석한 사람의 수 n (1 ≤ n ≤ 10,000,000)이 주어진다.

첫째 줄에 악수를 하는 방법의 수를 출력한다. 수가 매우 커질 수 있기 때문에, 마지막 자리만 출력한다.

승택이의 아들이 생일을 맞았다. 승택이는 아들을 위해 생일 파티를 하려고 한다.

하지만 아들의 친구들을 모두 초대할 수는 없다. 아이들에게 나눠 줄 사탕이 부족하기 때문이다.

아이들은 항상 한 종류의 사탕만을 먹고 싶어한다. 게다가, 한 종류의 사탕을 최소한 K개 이상 먹어야만 행복해한다.

K가 주어지고 승택이가 현재 갖고 있는 사탕의 종류와 개수가 주어진다. 이 때, 생일파티에 올 수 있는 아이들은 최대 몇 명일까?

첫 줄에 테스트 케이스의 수 T가 주어진다. ( 1 ≤ T ≤ 100 )

각 테스트 케이스의 첫 줄엔 승택이가 갖고 있는 사탕의 종류의 수 N과 K가 주어진다. ( 1 ≤ N, K ≤ 100 )

두번째 줄엔 N개의 정수로 승택이가 각 종류의 사탕을 몇 개 갖고 있는지가 주어진다.

모든 종류에 대해, 사탕은 최소 1개 최대 100개이다.

각 테스트 케이스마다 생일파티에 최대 몇 명의 아이들이 참석할 수 있는지 하나의 정수로 출력한다.

영어에서는 어떤 글자가 다른 글자보다 많이 쓰인다. 에를 들어, 긴 글에서 약 12.31% 글자는 e이다.

어떤 글이 주어졌을 때, 가장 많이 나온 글자를 출력하는 프로그램을 작성하시오.

첫째 줄부터 글의 문장이 주어진다. 글은 최대 5000글자로 구성되어 있고, 공백, 알파벳 소문자, 엔터로만 이루어져 있다. 그리고 적어도 하나의 알파벳이 있다.

첫째 줄에 가장 많이 나온 문자를 출력한다. 여러 개일 경우에는 알파벳 순으로 앞서는 것부터 모두 공백없이 출력한다.

다음과 같은 규칙에 따라 수들을 만들려고 한다.

1. 첫 번째 수로 양의 정수가 주어진다.
2. 두 번째 수는 양의 정수 중에서 하나를 선택한다.
3. 세 번째부터 이후에 나오는 모든 수는 앞의 앞의 수에서 앞의 수를 빼서 만든다. 예를 들어, 세 번째 수는 첫 번째 수에서 두 번째 수를 뺀 것이고, 네 번째 수는 두 번째 수에서 세 번째 수를 뺀 것이다.
4. 음의 정수가 만들어지면, 이 음의 정수를 버리고 더 이상 수를 만들지 않는다.

첫 번째 수로 100이 주어질 때, 두 번째 수로 60을 선택하여 위의 규칙으로 수들을 만들면 7개의 수들 100, 60, 40, 20, 20 , 0, 20이 만들어진다. 그리고 두 번째 수로 62를 선택하여 위의 규칙으로 수들을 만들면 8개의 수들 100, 62, 38, 24, 14, 10, 4, 6이 만들어진다. 위의 예에서 알 수 있듯이, 첫 번째 수가 같더라도 두 번째 수에 따라서 만들어지는 수들의 개수가 다를 수 있다.

입력으로 첫 번째 수가 주어질 때, 이 수에서 시작하여 위의 규칙으로 만들어지는 최대 개수의 수들을 구하는 프로그램을 작성하시오. 최대 개수의 수들이 여러 개일 때, 그중 하나의 수들만 출력하면 된다.

첫 번째 수가 주어진다. 이 수는 30,000 보다 같거나 작은 양의 정수이다.

첫 번째 줄에는 입력된 첫 번째 수로 시작하여 위의 규칙에 따라 만들 수 있는 수들의 최대 개수를 출력한다.

둘째 줄에 그 최대 개수의 수들을 차례대로 출력한다. 이들 수 사이에는 빈칸을 하나씩 둔다.

체조나 다이빙 등의 경기에서 일부 심판이 자기가 좋아하는 선수에게 높은 점수를, 싫어하는 선수에게 낮은 점수를 주는 경우가 종종 있었다. 따라서 심판들이 주는 점수의 평균점수를 선수에게 주게 되면 공정하지 않은 경우가 생길 수 있다. 이를 방지하기 위하여 절사평균이나 보정평균을 사용한다. 예를 들어 심사위원 일곱 명이 다음과 같이 점수를 주었다고 하자.

9.3, 9.5, 9.6, 9.8, 9.1, 5.0, 9.3

전체의 합이 61.6이 되므로 평균은 8.8이 된다. 이 평균점수는 한 심판이 다른 심판에 비하여 아주 낮은 점수인 5.0을 주어서 나온 결과로, 선수는 매우 불공정하다고 느낄 것이다.

위의 점수를 작은데서 큰 순서로 정렬하면 5.0, 9.1, 9.3, 9.3, 9.5, 9.6, 9.8 이 된다.

이때 절사평균(7, 2)는 정렬된 전체 점수 일곱 개 중 양쪽 끝에서 두 개씩을 제외하고 난 9.3, 9.3, 9.5의 평균인 9.37이 된다(소수점이하 셋째 자리에서 반올림). 또 보정평균(7, 2)는 정렬된 전체 점수 일곱 개 중 양쪽 끝에서 각각 두 개를, 남은 점수 중 가장 가까운 것으로 교체한 9.3, 9.3, 9.3, 9.3, 9.5, 9.5, 9.5의 평균으로 9.39가 된다(소수점이하 셋째 자리에서 반올림).

N개의 점수와 양쪽에서 제외하는 개수 K 값이 주어졌을 때 절사평균(N, K)와 보정평균(N, K)를 계산하는 프로그램을 작성하시오.

첫째 줄에 전체 점수의 개수 N과 제외되는 점수의 개수 K가 빈칸을 사이에 두고 주어진다. N은 3 이상 100,000 이하의 자연수이다. K는 0 이상 (N/2)-1 이하로 주어진다. 그 다음 N줄에는 각 심판의 점수가 한 줄에 하나씩 주어진다. 점수는 0 이상 10 이하의 실수로 소수점이하 첫째 자리까지 주어진다.

첫째 줄에 절사평균(N, K)를, 둘째 줄에 보정평균(N, K)를 각각 소수점이하 셋째 자리에서 반올림하여 둘째 자리까지 출력한다. 예를 들어 결과값이 9.667인 경우 9.67로, 5인 경우 5.00으로, 5.5인 경우에는 5.50으로 출력한다.

심술쟁이 해커 임준오(동탄 주민)는 오늘도 점심시간을 기다리고 있다. 준오와 친구들은 매일 복도 어딘가의 한 지점에 모여서 함께 밥을 먹으러 간다. 선린의 복도는 직선형으로 되어있고, 준오와 친구들은 이 복도 어딘가에 위치한 교실에서 종이 치기만을 기다리고 있다.

‘띵~ 디딩~ 띵디딩디딩~’

종이 울렸다! 준오와 친구들은 최대한 빨리 한 지점에서 만나야한다. 그렇지 않으면 홍수처럼 쏟아지는 학생들에 휩쓸려 제각각 급식실로 떠내려갈지도 모른다.

준오를 포함한 친구들의 교실 위치 xi와 각 학생들의 달리기 속도 vi, 그리고 홍수가 밀려오기까지 남은 시간 T가 주어진다. 과연 준오와 친구들은 함께 밥을 먹으러 갈 수 있을까?

교실은 1차원 직선 위 어딘가에 위치해있다. 학생들의 달리기 속도는 항상 일정하며, 모든 학생들이 종이 울림과 동시에 뛰어나온다. 홍수가 터지는 시점과 친구들이 만나는 시점이 일치한다면 홍수에 떠내려가기 전에 만날 수 있는 것으로 간주한다.

첫째 줄에는 준오를 포함한 친구들의 수 N과 홍수까지 남은 시간 T가 주어진다. (1 ≤ N ≤ 50,000, 1 ≤ T(초) ≤ 1,000,000,000) 남은 시간 T는 소숫점 넷째자리의 실수로 주어진다.

둘째 줄에는 N명 학생들의 위치 x1, x2, ..., xn(1 ≤ xi ≤ 1,000,000,000)가 주어진다. (자연수, 미터 단위)

셋째 줄에는 N명 학생들의 속도 v1, v2, ..., vn(1 ≤ vi ≤ 1,000,000,000)가 주어진다. (자연수, 초당 미터)

준오와 친구들이 모두 만날 수 있으면 1을, 그렇지 않으면 0을 출력한다.

두 수 a와 b가 주어졌을 때, a와 b의 최소 공배수를 구하는 프로그램을 작성하시오.

첫째 줄에 테스트 케이스의 개수 n이 주어진다. 다음 n개 줄에는 a와 b가 주어진다. a와 b사이에는 공백이 하나 이상 있다. 두 수는 백만보다 작거나 같은 자연수이다.

각 테스트 케이스에 대해서 입력으로 주어진 두 수의 최소공배수를 출력한다.