If n is dividable by 3, you need to print 'a/3-1', 'a/3', and 'a/3+1'.
If not, the answer does not exist. Print '-1'.
#include<bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(0)
typedef long long ll;
using namespace std;
int main(){
int t;
scanf("%d",&t);
while(t--)
{
int a;
scanf("%d",&a);
if(a%3==0)
{
int k=a/3;
printf("%d %d %d\n",k-1,k,k+1);
}
else puts("-1");
}
return 0;
}
업솔빙 한 문제는 년-월-일-시간 순으로 맞은 일시를 적었고, 대회 시간 내 푼 문제는 대회시작으로부터 누적시간-분 순으로 맞은 일시를 적었다.
바로 풀이로 들어가자.
A. Favorite Sequence
Problem statement
Polycarp has a favorite sequencea[1…n]consisting ofnintegers. He wrote it out on the whiteboard as follows:
he wrote the numbera1to the left side (at the beginning of the whiteboard);
he wrote the numbera2to the right side (at the end of the whiteboard);
then as far to the left as possible (but to the right froma1), he wrote the numbera3;
then as far to the right as possible (but to the left froma2), he wrote the numbera4;
Polycarp continued to act as well, until he wrote out the entire sequence on the whiteboard.
The beginning of the result looks like this (of course, if n≥4).
For example, if n=7anda=[3,1,4,1,5,9,2], then Polycarp will write a sequence on the whiteboard[3,4,5,2,9,1,1].
You saw the sequence written on the whiteboard and now you want to restore Polycarp's favorite sequence.
Input
The first line contains a single positive integert(1≤t≤300) — the number of test cases in the test. Then ttest cases follow.
The first line of each test case contains an integern(1≤n≤300) — the length of the sequence written on the whiteboard.
The next line containsnnintegersb1,b2,…,bn(1≤bi≤10^9) — the sequence written on the whiteboard.
Output
Outputtanswers to the test cases. Each answer — is a sequenceathat Polycarp wrote out on the whiteboard.
풀이
문제를 읽으면 알 수 있듯이 처음과 마지막을 먼저 쓰고, 중간을 끝에서부터 순서대로 채워나가는 방식으로 쓴다고 하니 이를 역방향으로 적용시키면 된다. 가장 먼저 첫 element를 출력하고, 그 다음 마지막 element, 2번째, 마지막에서 2번째, ... 이런 식으로 출력을 하자. 이때 n이 홀수인지 짝수인지를 판단해서, 홀수라면 가운데 값이 있으므로 마지막에 따로 출력해 주고, 짝수라면 특이사항이 없다.
#include<stdio.h>
int main()
{
int n;
int arr[1001];
scanf("%d\n",&t);
while(t--){
scanf("%d",&n);
for(i=0;i<n;i++){
scanf("%d ",&arr[i]);
}
k = n/2;
if(n%2==0){
for(i=0;i<n/2;i++){
printf("%d %d ",arr[i],arr[n-i-1]);
}
printf("\n");
}
else{
for(i=0;i<n/2;i++){
printf("%d %d ",arr[i],arr[n-i-1]);
}
printf("%d\n",arr[n/2]);
}
}
return 0;
}
[00:08 Accepted]
B. Last Year's Substring
Problem statement
Polycarp has a strings[1…n]of lengthnconsisting of decimal digits. Polycarp performs the following operation with the stringsno more than once(i.e. he can perform operation0or1time):
Polycarp selects two numbersiandj(1≤i≤j≤n) and removes characters from thesstring at the positionsi,i+1,i+2,…,j(i.e. removes substrings[i…j]). More formally, Polycarp turns the stringsinto the strings1s2…si−1sj+1sj+2…sn.
For example, the strings="20192020" Polycarp can turn into strings:
"2020" (in this case(i,j)=(3,6)or(i,j)=(1,4));
"2019220" (in this case(i,j)=(6,6));
"020" (in this case(i,j)=(1,5));
other operations are also possible, only a few of them are listed above.
Polycarp likes the string "2020" very much, so he is wondering if it is possible to turn the stringsinto a string "2020" in no more than one operation? Note that you can perform zero operations.
Input
The first line contains a positive integert (1≤t≤1000) — number of test cases in the test. Thentttest cases follow.
The first line of each test case contains an integern(4≤n≤200) — length of the strings. The next line contains a stringsof lengthnconsisting of decimal digits. It is allowed that the stringsstarts with digit0.
Output
For each test case, output on a separate line:
"YES" if Polycarp can turn the stringssinto a string "2020" in no more than one operation (i.e. he can perform0 or1operation);
"NO" otherwise.
You may print every letter of "YES" and "NO" in any case you want (so, for example, the stringsyEs,yes,YesandYESwill all be recognized as positive answer).
풀이
문제를 요약하면 주어진 문자열 안에 '2020'이 1개, 또는 2개로 분리되어 있는지를 판별하는 문제이다. 2020이 1개로 분리되는 방법은 '2020' 한가지밖에 없다. 2개로 분리되는 방법의 수는 '2/020', '20/20', '202/0' 이렇게 3개지 경우가 있다. 하지만 이때 한번만 문자열에서 문자의 묶음을 지울 수 있으므로 '2020'이 2개로 분리되는 경우에서는 분리된 2개의 문자열이 각각 주어진 문자열의 맨 앞과 맨 뒤에 있어야 한다. 앞서 말한 조건을 단순 if문으로 모두 확인하면 된다.
이 문제는 개인적으로 어렵게 생각하면 굉장히 어려워지지만 실제로는 쉬운 문제라고 생각된다.
Editorial을 보기 전 이 문제를 가지고 정말 한참을 고민했는데도 답을 찾지 못했는데, Editorial을 보고 나니 허탈했다;;
Gildong's town has a train system that has100trains that travel from the bottom end to the top end and100trains that travel from the left end to the right end. The trains starting from each side are numbered from11to100, respectively, and all trains have the same speed. Let's take a look at the picture below.
The train system can be represented as coordinates on a 2D plane. Thei-th train starting at the bottom end is initially at(i,0)and will be at(i,T)afterTminutes, and thei-th train starting at the left end is initially at(0,i)and will be at(T,i)afterTminutes. All trains arrive at their destinations after101minutes.
However, Gildong found that some trains scheduled to depart at a specific time, simultaneously, are very dangerous. At this time,ntrains are scheduled to depart from the bottom end andmmtrains are scheduled to depart from the left end. If two trains are both at (x,y)at the same time for somexandy, they will crash into each other. Therefore, he is asking you to find theminimumnumber of trains that should be canceled to prevent all such crashes.
**문제에 오타가 있습니다. Bold로 표시한 'canceled'가 문제 지문에서는 'cancelled'로 표기되어 있습니다.**
Input
Each test contains one or more test cases. The first line contains the number of test casest(1≤t≤100).
Each test case contains three lines. The first line of each test case consists of two integersnandm(1≤n,m≤100) — the number of trains scheduled to depart from the bottom end, and the number of trains scheduled to depart from the left end, respectively.
The second line of each test case containsnintegers. Each integer is a train number that is scheduled to start from thebottomend. The numbers are given in strictly increasing order, and are between1and 100, inclusive.
The third line of each test case containsmmintegers. Each integer is a train number that is scheduled to start from theleftend. The numbers are given in strictly increasing order, and are between1and100, inclusive.
Output
For each test case, print a single integer: the minimum number of trains that should be canceled in order to prevent all crashes.
대회 시작 시간이 굉장히 특이하길래(보통은 밤 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 withnrows andmcolumns. Therefore, there aren⋅mprison cells. There are alson⋅mprisoners, one in each prison cell. Let's denote the cell in thei-th row and thej-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 integert(1≤t≤10^4), the number of test cases.
Each of the nexttlines contains four space-separated integersn,m,r,c(1≤r≤n≤10^9,1≤c≤m≤10^9).
Output
Printtlines, 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));
}
}
