교수들은 각종 업무와 약속으로 가득 찬 복잡한 스케줄 속에서 매우 바쁘게 살아간다. P 교수는 낮잠을 자는 것을 좋아하지만 스케줄이 바쁘다 보니 낮잠을 잘 수 있는 시간이 별로 없다. 하지만 P 교수는 매일 한 번씩은 낮잠을 자고 싶어한다. 물론 그의 스케줄을 감안해서 될 수 있으면 오랫동안 낮잠을 즐길 수 있는 방법을 찾아야 한다. P 교수가 최대한 오랫동안 낮잠을 잘 수 있게 해주는 프로그램을 만들어라
- 본문의 "낮잠 오래 자기(Longest Nap)" 문제 중에서 -
블라디미르는 새하얀 피부와 날카로운 이를 가지고 있다. 나이는 600살이나 되지만, 뱀파이어인 블라디미르에게 나이는 별 의미가 없다. 블라디미르는 뱀파이어로 살아가는 데 있어서 별 다른 불편함을 느끼지 못한다. 그는 항상 야간 근무를 맡는 의사로 일하고 있는데, 훌륭하게 의사 생활을 하고 있으며, 야간 근무를 도맡아 하다 보니 동료들하고도 매우 사이 좋게 지내고 있다. 그는 파티장에서 맛을 보는 것만으로도 혈액형을 알아맞히는 쇼를 보여주곤 한다. 블라디미르는 여행을 하고 싶은데, 뱀파이어이다 보니 세 가지 문제를 극복해야만 한다.
1. 항상 관을 가지고 다녀야 하기 때문에 기차 여행 밖에는 할 수가 없다. 다행히도 워낙 오랫동안 돈을 모았기 때문에 재력이 상당하므로 항상 1등칸을 타고 다닐 수 있다.
2. 황혼에서 새벽까지만, 즉 오후 여섯 시부터 오전 여섯 시까지만 여행할 수 있다. 낮에는 기차역을 벗어날 수 없다.
3. 뭔가 먹을 것을 가지고 다녀야 한다. 하루에 피를 1리터씩 먹어야 하며, 그의 관 안에서 정오(낮 12시)에 피를 마신다.
두 도시가 주어졌을 때 최단 경로를 찾는 프로그램을 만들어서 블라디미르가 최소한의 피만 챙겨서 여행할 수 있도록 도와주자. 피를 너무 많이 가지고 다니면 사람들이 "그 피 가지고 뭘 하실 건가요?" 같은 질문을 하면서 의심할 수도 있기 때문이다.
- "황혼에서 새벽까지(From Dusk Till Dawn)" 문제 중에서 -
본문
[문제 28] 낮잠 오래 자기(Longest Nap)
PC/UVa ID: 110404/10191, 인기도: B, 성공률: 보통, 레벨: 1
교수들은 각종 업무와 약속으로 가득 찬 복잡한 스케줄 속에서 매우 바쁘게 살아간다. P 교수는 낮잠을 자는 것을 좋아하지만 스케줄이 바쁘다 보니 낮잠을 잘 수 있는 시간이 별로 없다. 하지만 P 교수는 매일 한 번씩은 낮잠을 자고 싶어한다. 물론 그의 스케줄을 감안해서 될 수 있으면 오랫동안 낮잠을 즐길 수 있는 방법을 찾아야 한다. P 교수가 최대한 오랫동안 낮잠을 잘 수 있게 해주는 프로그램을 만들어라.
입력
임의 개수의 테스트 케이스가 입력되며 각 테스트 케이스가 하루를 나타낸다. 각 테스트 케이스의 첫번째 줄에는 100 이하의 양의 정수 s가 들어있으며 이 수는 그 날 미리 잡혀있는 약속의 개수를 나타낸다. 그 다음 줄부터 s개의 줄에는 time1 time2 약속 형식으로 잡혀있는 약속이 입력되며, time1은 시작 시각, time2는 끝나는 시각을 나타낸다. 모든 시각은 hh:mm 형식으로 주어진다. 끝나는 시각은 반드시 시작 시간보다 뒤며 시작 시간과 스페이스 한 개로 구분된다.
모든 시각은 10:00 이후, 18:00 이전으로 주어진다. 따라서 결과도 반드시 이 시간 내에 있어야 한다. 즉 10:00 전에 낮잠을 잘 수 없고 18:00 넘어서까지 낮잠을 잘 수도 없다.
약속은 임의의 문자를 열거한 형태로 주어지는데 반드시 한 줄에 입력되어야 한다. 각 줄의 길이는 255 글자를 넘지 않으며 10≤hh≤18, 0≤mm<60이라고 가정할 수 있다. 하지만 약속이 어떤 정해진 순서대로 입력된다고 가정할 수 없고 파일 종료 문자가 나올 때까지 입력을 모두 읽어야 한다.
출력
각 테스트 케이스에 대해 다음과 같은 내용을 한 줄씩 출력한다.
Day #d: the longest nap starts at hh:mm and will last for [H0 hours and] M minutes.
d는 테스트 케이스 번호(1에서 시작)를, hh:mm은 낮잠을 자기 시작하는 시각을 의미한다. 낮잠 자는 시간을 표시할 때는 다음과 같은 규칙을 따른다.
1. 총 시간 X가 60분 미만이면 "X minutes"만 출력한다.
2. 총 시간 X가 60분 이상이면 "H hours and M minutes"라고 출력한다. 이때 H는 다음과 같이 결정된다.
H=X÷60(정수 나눗셈), M=X를 60으로 나눈 나머지
단수, 복수는 따지지 않는다. 즉 "1 minutes", "1 hours" 같은 식으로 출력되도록 해야 한다.
낮잠을 잘 수 있는 시간은 시작 시각과 끝나는 시각의 차로 계산한다. 즉 약속이 14:00에 끝나고 다음 약속이 14:47에 시작하면 14:47-14:00=47분 동안 낮잠을 잘 수 있다.
가장 길게 낮잠을 잘 수 있는 시간이 여러 개 있으면 그 중 가장 빨리 시작하는 것을 출력한다. 낮잠을 잘 시간이 전혀 없을 정도로 교수가 하루 종일 바쁜 경우는 없다고 가정한다.
입력 예
4
10:00 12:00 Lectures
12:00 13:00 Lunch, like always.
13:00 15:00 Boring lectures...
15:30 17:45 Reading
4
10:00 12:00 Lectures
12:00 13:00 Lunch, just lunch.
13:00 15:00 Lectures, lectures... oh, no!
16:45 17:45 Reading (to be or not to be?)
4
10:00 12:00 Lectures, as everyday.
12:00 13:00 Lunch, again!!!
13:00 15:00 Lectures, more lectures!
15:30 17:15 Reading (I love reading, but should I schedule it?)
1
12:00 13:00 I love lunch! Have you ever noticed it? :)
출력 예
Day #1: the longest nap starts at 15:00 and will last for 30 minutes.
Day #2: the longest nap starts at 15:00 and will last for 1 hours and 45 minutes.
Day #3: the longest nap starts at 17:15 and will last for 45 minutes.
Day #4: the longest nap starts at 13:00 and will last for 5 hours and 0 minutes.
[문제 28 해답] 낮잠 오래 자기(Longest Nap)
약속 시간들을 정렬한 다음, 앞에서부터 읽어 나가면서 중간에 비는 시간을 계산하여 그 최대 값을 찾으면 된다. 시간 계산을 편리하게 하기 위해, 입력 받은 시간 값을 10시 정각을 기준으로 하여 몇 분이 지났는지로 변환해서 처리했다.
/* @BEGIN_OF_SOURCE_CODE */
/* @JUDGE_ID: hoimann 10152 C "simple one" */
#include
#include
#define MAX_APPTS 100
typedef struct {
int start, end;
} appointment;
int str2time(char *hh, char *mm)
{
return (hh[1] - '0') * 60 + (mm[0] - '0') * 10 + (mm[1] - '0');
}
appointment appt[MAX_APPTS + 2];
char line[256];
void main()
{
int num_appts;
int day_number, i, j, min, nap_slot, nap_time;
appointment temp_appt;
day_number = 0;
while (scanf("%d", &num_appts) == 1) {
day_number++;
gets(line);
appt[0].start = 0;
appt[0].end = 0;
appt[num_appts + 1].start = 8 * 60;
appt[num_appts + 1].end = 8 * 60;
for (i = 1; i <= num_appts; i++) {
gets(line);
appt[i].start = str2time(line, line + 3);
appt[i].end = str2time(line + 6, line + 9);
}
for (i = 1; i < num_appts; i++) {
min = i;
for (j = i; j <= num_appts; j++)
if (appt[j].start < appt[min].start)
min = j;
temp_appt = appt[i];
appt[i] = appt[min];
appt[min] = temp_appt;
}
nap_slot = 0;
nap_time = appt[1].start - appt[0].end;
for (i = 1; i <= num_appts; i++)
if (appt[i + 1].start - appt[i].end > nap_time) {
nap_slot = i;
nap_time = appt[i + 1].start - appt[i].end;
}
printf("Day #%d: the longest nap starts at ", day_number);
printf("1%d:%02d and will last for ",
appt[nap_slot].end / 60,
appt[nap_slot].end % 60);
if (nap_time >= 60)
printf("%d hours and %d minutes.\n", nap_time / 60, nap_time % 60);
else
printf("%d minutes.\n", nap_time);
}
}
/* @END_OF_SOURCE_CODE */
[문제 89] 체스판 위의 개미(Ant on a Chessboard)
PC/UVa ID: 111201/10161, 인기도: B, 성공률: 높음, 레벨: 1
어느 날 앨리스라는 개미가 M×M 체스판에 올라갔다. 앨리스는 체스판에 있는 모든 셀을 방문하려고 한다. 그래서 판 한 쪽 구석에서 시작해서 체스판을 한 꺼풀씩 훑어나가기로 했다.
앨리스는 (1, 1)자리부터 움직이기 시작했다. 처음에는 한 칸 위로 올라간 다음, 오른쪽으로 한 칸 이동하고, 다시 한 칸 아래로 내려왔다. 그리고 나서 한 칸 오른쪽으로 움직여서 두 칸 위로 올라가고, 두 칸 왼쪽으로 움직였다. 이런 식으로 매번 한 행, 그리고 한 열씩을 더 움직였다.
예를 들어 앨리스가 25단계를 움직인 경로를 표시해보면 다음과 같다. 여기에서 각 숫자는 앨리스가 각 셀을 방문한 순서를 나타낸다.
25 24 23 22 21
10 11 12 13 20
9 8 7 14 19
2 3 6 15 18
1 4 5 16 17
앨리스는 여덟 번째 단계에서는 (2, 3) 위치에 있었고, 20번째 단계에서는 (5, 4) 위치에 있었다. 단계 수가 주어졌을 때, 체스판이 매우 커서 움직일 수 있는 위치에 제한이 없다고 할 때, 앨리스의 위치를 결정하는 프로그램을 만들어야 한다.
입력
입력 파일은 여러 줄로 구성되는데, 각 줄마다 단계 번호를 나타내는 정수 N(1≤N≤2×109)이 하나씩 입력된다. 0이 입력되면 입력이 종료된다.
출력
입력된 값에 대해 해당 단계에서의 앨리스의 위치 (x, y)를 나타내는 두 정수를 출력한다. x는 열 번호, y는 행 번호를 나타낸다. 두 정수 사이에는 스페이스가 한 개 들어간다.
입력 예 출력 예
8 2 3
20 5 4
25 1 5
0
[문제 89 해답] 체스판 위의 개미(Ant on a Chessboard)
N이 매우 크기 때문에, 1부터 차례대로 수를 배열에 넣은 뒤 검색해서 위치를 찾는 방법은 사용할 수 없다. 그렇다면 어떤 방법을 사용해야 할까? 셀을 순회하는 방식을 보고, 식으로 위치를 바로 구하는 방법을 찾아야 한다.문제에 주어진 배열을 보면, 1~4까지는 크기 2짜리 정사각형을 이루는데, 5~9까지를 추가하면 크기 3의 정사각형이 된다는 것을 알 수 있다.즉, 1~n^2까지의 n^2개의 숫자로는 크기 n짜리 정사각형을 만들 수 있는 것이다.이렇게 숫자의 크기를 보고 이 수가 어떤 크기의 정사각형의 외곽선을 이루는지를 알 수 있다. 그 외곽선에서의 정확한 위치는 직접 순회를 하거나, 모범답안에서 처럼 식으로 해결할 수 있다.
/* @BEGIN_OF_SOURCE_CODE */
/* @JUDGE_ID: 46288WZ 10161 C "non-loop calculation" */
#include
#include
void main()
{
while (1)
{
long n = 0;
/* inner_box_size : 격자에서 완전히 순회한 줄의 수 */
/* step_num : 마지막 줄에서 순회한 칸의 수 */
/* step_num_from_left : 마지막 줄에서, 왼쪽부터 센 칸의 수 */
long inner_box_size, step_num, step_num_from_left;
/* column, row : 결과로 출력할 행과 열 번호 */
/* 모서리를 지났느냐에 따라서 식이 달라진다. */
long column = 0, row = 0;
scanf("%d", &n);
if ( n == 0 ) break;
inner_box_size = (long)(sqrt(n - 1));
step_num = n - inner_box_size * inner_box_size;
step_num_from_left = step_num;
if ( inner_box_size % 2 == 0 )
step_num_from_left = inner_box_size * 2 + 2 - step_num;
if ( step_num_from_left <= inner_box_size + 1 )
{
column = step_num_from_left;
row = inner_box_size + 1;
}
else
{
column = inner_box_size + 1;
row = inner_box_size * 2 + 2 - step_num_from_left;
}
printf("%ld %ld\n", column, row);
}
}
/* @END_OF_SOURCE_CODE */
문제 해답