2016. 9. 6. 16:45ㆍ알고리즘 문제풀기/문제 번역
AtCoder Regular Contest 001
링크. 안타깝게도 실제 대회는 열리지 못했다고 한다.
A. 수능 채점(センター採点)
링크.
참고
센터 시험(センター試験) : 우리나라의 수능에 해당하는, 대학 입학 시험 전의 전국 공통 시험. 여기서는 수능으로 번역함.
타카하시 군은 수능 시험을 쳤습니다.
수능 시험의 각각의 문제는 1부터 4까지의 선택지가 있습니다. 타카하시 군은 별로 공부를 하지 않았기 때문에, 모든 문제에 대해 같은 선택지를 골랐습니다.
시험 종료 후, 수능 시험의 정답이 주어졌습니다만, 타카하시 군은 어떤 번호를 골랐는지를 잊어버리고 말았습니다. 하지만 타카하시 군은 자신의 점수가 신경쓰입니다.
타카하시 군을 위해 타카하시 군이 맞을 수 있는 문제의 갯수의 최대 및 최소를 알려주세요.
입력 예제는 입출력을 참고하세요.
첫 번째 줄에 주어지는 문자열의 길이는 100보다 작거나 같습니다. 즉, .
예제 입력 1
9
131142143예제 출력 1
4 1
예제 입력 2
4
1111예제 출력 2
4 0
B. 리모콘(リモコン)
링크.
타카하시 군은, 에어컨의 설정온도를 변경하려고 하고 있습니다. 현재 설정온도는 A도이고, 원하는 온도는 B도입니다.
에어컨의 리모콘은 한 번 버튼을 눌러서,
- 설정 온도를 1도 올리거나 내림
- 설정 온도를 5도 올리거나 내림
- 설정 온도를 10도 올리거나 내림
의 여섯 가지의 조작 중 어느 하나를 할 수 있습니다.
타카하시 군이 설정온도를 A도에서 B도로 바꾸기 위해 버튼을 최소 몇 번 눌러야 하는지 알려주세요.
예제 입력 1
7 34
예제 출력 1
5
예제 입력 2
19 28
예제 출력 2
2
C. 퍼즐 돕기(パズルのお手伝い)
링크.
타카하시 군은 퍼즐을 좋아합니다. 오늘은 8-queen 문제에 도전하려고 하고 있습니다.
8-queen 문제란, 8x8의 체스판 상에 가로, 세로, 그리고 45도 대각선 상에는 퀸이 많아야 하나 존재하도록 총 8개의 퀸을 놓는 문제입니다.
그림: 출력 1의 예. 조건을 만족하고 있습니다.
타카하시 군은 세 개의 퀸을 놓았는데, 나머지 퀸을 어떻게 배치하면 좋을까 잘 모르겠다고 합니다.
나머지 다섯 개의 퀸을 잘 배치해서 8-queen 문제를 해결해주세요.
불가능한 경우 No Answer를 출력하면 됩니다.
입출력 방법은 예제를 참고하세요.
예제 입력 1
........
........
.......Q
........
..Q.....
........
.Q......
........예제 출력 1
Q.......
....Q...
.......Q
.....Q..
..Q.....
......Q.
.Q......
...Q....예제 입력 2
.....Q..
.Q......
........
........
........
Q.......
........
........예제 출력 2
No Answer
D. 레이싱 게임(レースゲーム)
링크.
타카하시 군은 레이싱 게임을 풀려고 하고 있습니다.
레이스는 (x,y)=(start,0) 에서 시작해、(x,y)=(goal,N) 의 골인 지점을 향해 달려갑니다.
0≦k≦N인 y=k 에 대해서 코스의 왼쪽과 오른쪽 끝 점의 x좌표가 주어지고, 그것을 차례대로 이은 것이 코스입니다.
그림: 입력1에 해당합니다. 빨간 원이 시작 지점, 파란 원이 골인 지점입니다. 갈색 부분이 코스입니다.
레이스에 사용하는 차는 코스 위에서만 달릴 수 있습니다. 그리고, 순식간에 방향을 전환할 수 있으며, 차의 폭 및 길이는 무시할 수 있습니다.
타카하시 군은, 이 레이싱 게임을 공략하기 위해서 시작 지점부터 골인 지점까지의 최단 경로를 구하고 싶습니다.
입력은 다음과 같습니다.
N
start goal
l[0] r[0]
l[1] r[1]
:
:
l[N] r[N]AtCoder Regular Contest 002
링크.
B번 문제의 입력 포맷에 문제가 있었다고 한다. 지금은 고쳐졌을 것이다.
A. 윤년(うるう年)
링크.
.
B. 딱 나누어지는 날짜(割り切れる日付)
링크.
C. 커맨드 입력(コマンド入力)
링크.
타카하시 군은 친구와 격투 게임으로 대전을 하기로 했습니다.
격투 게임은 A, B, X, Y의 네 종류의 버튼을 연속으로 입력하는 커맨드에 의해 기술을 시전하며 싸우는 게임입니다.
하지만, 평소 격투 게임을 즐기지 않는 타카하시군은 커맨드를 입력하는 게 어렵고, 친구에게 이길 수 있을 것 같지가 않습니다.
여기서 남아있는 L과 R 버튼에 연속한 두 개의 버튼의 입력을 단축키로 할당해서, 커맨드의 입력을 단축하고 싶습니다.
예를 들어, 커맨드가 ABXY라면 버튼을 네 번 누를 필요가 있습니다만, L에 AB, R에 XY를 할당하는 것으로 LR을 누르는 걸로 대신하여, 버튼을 두 번만 누르는 것으로 단축할 수 있습니다.
L과 R을 사용해 입력을 최대한 짧게 했을 때 필요한 버튼의 입력 횟수를 구하세요.
D. 보드 게임(ボードゲーム)
링크.
타카하시 군은 격투 게임에서 친구에게 진 것이 분해서 참을 수가 없었고, 이번에는 자신이 이길 수 있는 게임을 제안했습니다.
제인한 게임은 일단 바둑판 위에서 마주 보고 앉아, 그림에서 왼쪽 1열이 ○의 진지, 오른쪽 1열이 X의 진지가 됩니다.
랜덤으로 놓인 ○와 X의 말을 사용하며, 두 사람은 각각 ○와 X 중 자신의 말을 선택합니다.
그림: 바둑판의 예. 좌측의 빨간 열이 ○의 진지, 우측의 파란 열이 X의 진지입니다.
말은 상대의 진지를 향해 한 칸씩 전진하고, 상대에게 밟힌 말은 사라집니다.
자신의 앞쪽 한 방향으로만 전진할 수 있으며, 대각선・옆・뒤 등의 방향으로는 움직일 수 없습니다.
그리고, 자신의 말을 밟을 수는 없습니다.
번갈아 한 번씩 자신의 말을 움직여, 상대의 말을 모두 없애거나, 상대의 진지에 자신의 말을 하나라도 놓으면 승리가 됩니다.
선행은 ○가 붙은 말을 가지고 있는 사람이지만, 최초의 수에서는 ×를 없애는 것이 불가능한 초기배치로 놓여있습니다.
또한、초기배치에 이미 어느쪽이 승리조건을 만족해있는 상태도 없습니다.
타카하시 군은 반드시 이기고 싶기 때문에 ○와 ×의 어느쪽을 선택할지 고민하고 있습니다.
타카하시 군이 이기도록, ○와 ×의 어느 쪽이 이기는지 판정해주세요.
Written with StackEdit.
'알고리즘 문제풀기 > 문제 번역' 카테고리의 다른 글
| AtCoder Regular Contest 003-004 번역 (0) | 2016.09.07 |
|---|