2016. 9. 7. 00:01ㆍ알고리즘 문제풀기/문제 번역
AtCoder Regular Contest 003
링크.
A. GPA 계산(GPA計算)
링크.
B. 문제 제목
링크.
C. 어두컴컴한 귀갓길(暗闇帰り道)
링크.
타카하시 군은 밤길을 통해 학교에서 집까지 혼자서 돌아가려고 합니다.
그가 사는 곳은 직사각형 모양을 하고 있으며, 격자 모양으로 구획이 나뉘어 있습니다. 그는 동서남북 방향으로 1초에 한 칸씩 움직일 수 있습니다.
각 구획의 원래 밝은 정도가 주어지며, 경과시간 t초(출발시각은 0초)를 이용하여 “각 구획의 밝기” = (그 구역의 원래 밝은 정도) ×0.99t」로 나타낼 수 있습니다.
학교에서 자택까지 돌아가는 도중에 통과하는 경로상의 구획에 대해 “구획의 밝기”의 최소치를 그 “경로의 밝기”라고 합시다.
타카하시 군은 어둠공포증(暗所恐怖症, 암소공포증, Nyctophobia)가 있기 때문에, “경로의 밝기”가 가장 큰 경로를 선택하고 싶습니다.
그런 경로의 “밝기”를 구해주세요.
격자칸은 세로로 N칸, 가로로 M칸으로 이루어져있으며, 을 만족합니다.
주어지는 격자의 점 중 s는 학교, g는 타카하시 군의 집이며, 나머지 격자점의 값은 그 구획의 원래 밝은 정도를 나타냅니다.
예제에 대한 자세한 설명은 그림을 참고하세요.
D. 셔플 자리바꾸기(シャッフル席替え)
링크.
타카하시 군이 일하는 AtCoder사에는, 항상 한 개의 원형 테이블의 주위에 사원 전원이 앉아서 회의를 합니다.
사람마다 선호하는 자리가 있어서 항상 자리는 동일합니다만, 오늘은 자리를 바꾸기로 했습니다.
타카하시 군이 랜덤으로 두 명을 선택해서 그 두 명의 위치를 바꾸는 동작을 어떤 횟수만큼 반복한 뒤의 자리 배치가 새로운 자리배치가 됩니다.
하지만, 안타깝게도 AtCoder사에는 붙어 앉으면 회의 중에 떠들기 시작해서 미팅에 방해가 되어버리는 사람의 쌍들이 존재합니다.
타카하시 군은 성실하기 때문에, 회의가 막힘없이 진행될 수 있도록 각각의 쌍에 대해 그 두 사람이 서로 옆자리에 앉는 일이 없도록 하고 싶습니다.
자리바꾸기를 행한 뒤, 모든 쌍이 떨어져있을 확률을 구하세요.
절대오차 혹은 상대오차가 2e-3 이하일 경우 정답 처리됩니다.
사원은 N명, 떠드는 쌍의 수가 M개, 자리바꿈의 횟수가 K개라고 할 때,
AtCoder Regular Contest 004
링크.
A. 가장 먼 두 점 간의 거리 구하기(2点間距離の最大値)
링크.
평면상에 N개의 점이 있습니다.
가장 먼 두 점 사이의 거리를 구하세요.
B. 두 점 간 거리의 최대와 최소(2点間距離の最大と最小)
링크.
평면상에 0부터 N까지의 번호가 붙어있는 (N+1)개의 점이 있습니다.
또한 인 에 대해, 점 와 점 사이의 (유클리드) 거리 가 주어집니다.
이 때, 점 0과 점 N 사이의 거리로 가능한 값 중 최댓값과 최솟값을 구하세요.
C. 헤이킨치 타로 군의 우울(平均値太郎の憂鬱)
링크.
역자 주: 헤이킨치의 한자(平均値)는 ‘평균치’이며, 제목 전체는 모 라이트 노벨의 패러디.
타로 군은 1부터 N까지의 양의 정수의 평균치를 구하기로 하고, 1부터 N까지의 합계치를 N으로 나누기로 했습니다.
하지만 1부터 N까지의 합계치를 계산하는 도중, 어떤 N 이하의 양의 정수 M을 더하는 것을 깜빡해버렸고, 틀린 평균치를 산출해버렸습니다.
게다가 타로 군은 N의 값마저 잊어버렸습니다.
지금, 틀린 평균치만을 알고 있습니다(이 값은 분수 꼴의 유리수로 주어집니다). 원래의 수 N과 M이 될 수 있는 쌍들을 모두 알려주세요. 불가능한 경우 Impossible을 출력하면 됩니다.
분모 및 분자로 들어오는 수의 범위는 1 이상 이하입니다.
D. 표현의 자유(表現の自由 (Freedom of expression))
링크.
정수 N과 M이 주어질 때, 정수 N을 M개의 정수의 곱으로 나타내는 방법은 몇 가지일까요?
답을 1,000,000,007로 나눈 나머지를 답하세요.
Written with StackEdit.
'알고리즘 문제풀기 > 문제 번역' 카테고리의 다른 글
| AtCoder Regular Contest 001-002 번역 (1) | 2016.09.06 |
|---|