대회 시작 시간이 굉장히 특이하길래(보통은 밤 11시 35분 정도에 시작하지만 이번 대회는 시작 시간이 오후 4시 5분이었다) 냉큼 참가했다.
대회 시작부터 문제를 풀었고, 30분정도 풀다가 일이 있어 그만두었다. 그리고 대회 끝나기 약 30분 정도 전에 들어와서 15분 정도 풀다 접었다.
총 1문제를 풀었는데, 결론적으로 보면 1문제, 그것도 A번에 45분을 쏟았다.
Div.2 한문제 푸는데 45분 걸리는 흑우
서론은 이쯤 하고, 풀이로 들어가자.
A. Prison Break
Problem Statement
There is a prison that can be represented as a rectangular matrix with n rows and m columns. Therefore, there are n⋅m prison cells. There are also n⋅m prisoners, one in each prison cell. Let's denote the cell in the i-th row and the j-th column as (i,j).
There's a secret tunnel in the cell (r,c), that the prisoners will use to escape! However, to avoid the risk of getting caught, they will escape at night.
Before the night, every prisoner is in his own cell. When night comes, they can start moving to adjacent cells. Formally, in one second, a prisoner located in cell (i,j) can move to cells (i−1,j) , (i+1,j) , (i,j−1) , or (i,j+1), as long as the target cell is inside the prison. They can also choose to stay in cell (i,j).
The prisoners want to know the minimum number of seconds needed so that every prisoner can arrive to cell (r,c) if they move optimally. Note that there can be any number of prisoners in the same cell at the same time.
Input
The first line contains an integer t (1≤t≤10^4), the number of test cases.
Each of the next t lines contains four space-separated integers n, m, r, c (1≤r≤n≤10^9, 1≤c≤m≤10^9).
Output
Print t lines, the answers for each test case.
풀이
모든 방 안에 죄수가 꽉 차 있고, 죄수는 움직이지 않을 수도 있으므로 문제에서 구하고자 하는 시간은 탈출구에서 가장 멀리 떨어져 있는 죄수가 탈출구로 이동하는 시간과 같다.
탈출구에서 가장 멀리 떨어져 있는 죄수는 항상 감옥의 4 꼭짓점(귀퉁이)에 있음을 알 수 있다.
따라서 4 귀퉁이에서 탈출구까지 가는 최단거리를 비교해서 가장 큰 값을 출력하면 된다.
#include<stdio.h>
int max(int a, int b){if(a>=b){return a;}else{return b;}}
int main()
{
int a,b,c,d,t;
scanf("%d",&t);
while(t--)
{
scanf("%d %d %d %d",&a,&b,&c,&d);
printf("%d\n",max(max(max(c+d-2,a-c+b-d),a-c+d-1),c-1+b-d));
}
}이걸 45분 고민했다
[00:12 Wrong Answer on pretest 1]
[00:14 Wrong Answer on pretest 2]
[00:16 Wrong Answer on pretest 2]
[00:51 Wrong Answer on pretest 2]
[01:00 Wrong Answer on pretest 1]
[01:12 Wrong Answer on pretest 2]
[01:34 Pretests passed, Accepted(9)]
이런 실수는 하지 말자.... ㅠㅠ
B번은 업솔빙 예정
'대회 후기 > Codeforces' 카테고리의 다른 글
| SIT STAR Contest 2021 practice (0) | 2021.02.08 |
|---|---|
| SIT Contest A, B, C, D Editorial (0) | 2021.02.08 |
| Codeforces Round 690 (Div.3) 후기 (0) | 2020.12.20 |
| Codeforces Round #688 (Div. 2) 후기 (0) | 2020.12.14 |
| Codeforces Round #686 (Div.3) 후기 (0) | 2020.11.25 |