CodeupCoder's Blog

Div 3라 문제가 쉬웠고, 업솔빙 포함해서 3문제를 풀 수 있었다.

업솔빙 한 문제는 년-월-일-시간 순으로 맞은 일시를 적었고, 대회 시간 내 푼 문제는 대회시작으로부터 누적시간-분 순으로 맞은 일시를 적었다.

바로 풀이로 들어가자.

A. Favorite Sequence

Problem statement

Polycarp has a favorite sequence a[1…n] consisting of n integers. He wrote it out on the whiteboard as follows:

• he wrote the number a1 to the left side (at the beginning of the whiteboard);
• he wrote the number a2 to the right side (at the end of the whiteboard);
• then as far to the left as possible (but to the right from a1), he wrote the number a3;
• then as far to the right as possible (but to the left from a2), he wrote the number a4;
• Polycarp continued to act as well, until he wrote out the entire sequence on the whiteboard.

For example, if n=7 and a=[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 integer t (1≤t≤300) — the number of test cases in the test. Then t test cases follow.

The first line of each test case contains an integer n (1≤n≤300) — the length of the sequence written on the whiteboard.

The next line contains nn integers b1,b2,…,bn (1≤bi≤10^9) — the sequence written on the whiteboard.

Output

Output t answers to the test cases. Each answer — is a sequence a that 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 string s[1…n] of length n consisting of decimal digits. Polycarp performs the following operation with the string s no more than once (i.e. he can perform operation 0 or 1 time):

• Polycarp selects two numbers i and j (1≤i≤j≤n) and removes characters from the s string at the positions i,i+1,i+2,…,j (i.e. removes substring s[i…j]). More formally, Polycarp turns the string s into the string s1s2…si−1sj+1sj+2…sn.

For example, the string s="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 string s into a string "2020" in no more than one operation? Note that you can perform zero operations.

Input

The first line contains a positive integer t (1≤t≤1000) — number of test cases in the test. Then tt test cases follow.

The first line of each test case contains an integer n (4≤n≤200) — length of the string s. The next line contains a string s of length n consisting of decimal digits. It is allowed that the string s starts with digit 0.

Output

For each test case, output on a separate line:

• "YES" if Polycarp can turn the string ss into a string "2020" in no more than one operation (i.e. he can perform 0 or 1 operation);
• "NO" otherwise.

You may print every letter of "YES" and "NO" in any case you want (so, for example, the strings yEs, yes, Yes and YES will 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을 보고 나니 허탈했다;;

#include<stdio.h>
char x[210];
int main()
{
	int t;
	scanf("%d",&t);
	while(t--){
		int a;
		scanf("%d",&a);
		scanf("%s",x+1);
		if(x[1]=='2'&&x[2]=='0'&&x[3]=='2'&&x[4]=='0'){
        	printf("YES\n");
        }
		else if(x[1]=='2'&&x[2]=='0'&&x[3]=='2'&&x[a]=='0'){
        	printf("YES\n");
        }
		else if(x[1]=='2'&&x[2]=='0'&&x[a-1]=='2'&&x[a]=='0'){
        	printf("YES\n");
        }
		else if(x[1]=='2'&&x[a-2]=='0'&&x[a-1]=='2'&&x[a]=='0'){
        	printf("YES\n");
        }
		else if(x[a-3]=='2'&&x[a-2]=='0'&&x[a-1]=='2'&&x[a]=='0'){
        	printf("YES\n");
        }
		else printf("NO\n");
	}
}

[2020-12-15-19:58 Accepted]

C. Unique number

Problem statement

You are given a positive number x. Find the smallest positive integer number that has the sum of digits equal to x and all digits are distinct (unique).

Input

The first line contains a single positive integer t (1≤t≤50) — the number of test cases in the test. Then t test cases follow.

Each test case consists of a single integer number x (1≤x≤50).

Output

Output t answers to the test cases:

• if a positive integer number with the sum of digits equal to x and all digits are different exists, print the smallest such number;
• otherwise print -1.

풀이

if문 노가다 ㄱㄱ!! 뭐 Editorial 보니까 멋있게 수식으로 푸는 방법이 있더라...

근데 이게 노가다 하는거도 50개를 다 하기에는 손이 너무 아파서 좀 효율적인(?) 노가다를 하기 위해서 일종의 전략(?)을 짜 보았다.

일단 x가 9보다 작거나 같은 경우에는 그냥 x를 출력하자.

x가 1~9까지의 숫자로 만들 수 있는 가장 큰 수의 자릿수의 합보다 큰 경우(즉, 45보다 큰 경우)는 -1을 출력한다.

그 외의 경우를 다 노가다 치기는 힘드니까 또다시 자연수들을 묶음으로 나누어 보자.

먼저 x가 9보다 크고 17보다 작거나 같은 경우는 모두 _9 모양의 2자리 숫자로 표현해야 한다.

그다음 x가 17보다 크고 24보다 작거나 같은 경우는 모두 _89 모양의 3자리 숫자로 표현해야 한다.

이런 식으로 해 나가면 if문 단 14개(?!)로 해결 할 수 있다!!

물론 그래도 노가다는 심하다

#include <stdio.h>
int main()
{
    int t,i,x;
    scanf("%d\n",&t);
    while(t--)
    {
        scanf("%d",&x);
        if(x<=9) printf("%d\n",x);
        else
        {
            if(x>45)
            {
                printf("-1\n");
            }
            else if(x>9&&x<=17)
            {
                printf("%d9\n",x-9);
            }
            else if(x>=18&&x<=24)
            {
                printf("%d89\n",x-17);
            }
            else if(x>=25&&x<=30)
            {
                printf("%d789\n",x-24);
            }
            else if(x>=31&&x<=35)
            {
                printf("%d6789\n",x-30);
            }
            else if(x>=36&&x<=39)
            {
                printf("%d56789\n",x-35);
            }
            else if(x==40)
            {
                printf("1456789\n");
            }
            else if(x==41)
            {
                printf("2456789\n");
            }
            else if(x==42)
            {
                printf("3456789\n");
            }
            else if(x==43)
            {
                puts("13456789");
            }
            else if(x==44)
            {
                puts("23456789");
            }
            else
            {
                puts("123456789");
            }
        }
    }
    return 0;
}

[01:34 Wrong Answer on test 2]

[01:37 Accepted]

3번이 생각보다 쉬워서 좋았다.(--)

일요일 9시에 열리는 대회는 내가 일정이 있어서 풀 시간이 얼마 없다..ㅠ

그래도 괜찮은(?) 결과가 나와서 기분은 좋았지만 rating은...다.

개인적으로 B번을 시간 안에 못 풀기도 했고, C번은 내가 좋아하는 조합이론 문제가 나와서 대회가 마음에 들었다.

(참고로 내가 가장 좋아하는 문제의 종류는 조합/기하 관련 문제들이다)(물론 쉬운거)

바로 풀이로 들어가자.

A. ABC Preparation

Problem statement

Takahashi has decided to hold some number of programming contests.
Holding one contest requires one 100100-point problem, one 200200-point problem, one 300300-point problem, and one 400400-point problem.
When he has A1, A2, A3, and A4 drafts of 100-, 200-, 300-, and 400-point problems, respectively, at most how many contests can he hold?
The same draft can be used only once.

Input

Input is given from Standard Input in the following format:

A1 A2 A3 A4

Output

Print an integer representing the maximum number of contests that can be held.

풀이

어짜피 모든 배점의 문제를 다 똑같은 개수만큼 출제하는 것이기 때문에 가장 적은 개수가 있는 문제의 개수만큼만 대회를 만들 수 있다. 따라서 입력되는 값 중에서 가장 작은 값을 출력하면 된다.

#include<stdio.h>
int min(int a, int b){if(a>=b){return b;}else{return a;}}
int main()
{
    int a,b,c,d,;
    scanf("%d %d %d %d",&a,&b,&c,&d);
    printf("%d",min(a,min(b,min(c,d))));
    return 0;
}

[02:29 Accepted]

C. Duodecim Ferra

Problem statement

There is an iron bar of length L lying east-west. We will cut this bar at 11 positions to divide it into 12 bars. Here, each of the 12 resulting bars must have a positive integer length.
Find the number of ways to do this division. Two ways to do the division are considered different if and only if there is a position cut in only one of those ways.
Under the constraints of this problem, it can be proved that the answer is less than 2^63.

Input

Input is given from Standard Input in the following format:

L

Output

Print the number of ways to do the division.

풀이

길이가 L인 bar에는 자를 수 있는 곳이 L-1개 있다. 그 L-1개 중에서 11개를 선택하는 방법의 수가 정답이므로 L-1C11을 출력하면 된다.

import math
def nCr(n,r):
    f = math.factorial
    return f(n) // f(r) // f(n-r)
a = int(input())
print(nCr(a-1,11))

다름이 아니라 C로 짜니까 nCr함수에서 오류가 나는지 자꾸 WA 떠서 파이썬으로 풀었다

[67:12 Wrong Answer]

[67:26 Wrong Answer]

[73:55 Runtime Error]

[76:21 Accepted]

B는 업솔빙 예정

조금 늦게 후기를 작성한다.

이 라운드는 한국인인 djm03718님이 주최하셔서 굉장히 기대가 되었다.

시간도 한국인에 맞게 1시간 이른 10시 35분이어서 좋았다.

그래도 한문제밖에 못풀었다.

바로 풀이로 들어가도록 하겠다.

A. Cancel the trains

Problem statement

Gildong's town has a train system that has 100 trains that travel from the bottom end to the top end and 100 trains that travel from the left end to the right end. The trains starting from each side are numbered from 11 to 100, 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. The i-th train starting at the bottom end is initially at (i,0) and will be at (i,T) after T minutes, and the i-th train starting at the left end is initially at (0,i) and will be at (T,i) after T minutes. All trains arrive at their destinations after 101 minutes.

However, Gildong found that some trains scheduled to depart at a specific time, simultaneously, are very dangerous. At this time, n trains are scheduled to depart from the bottom end and mm trains are scheduled to depart from the left end. If two trains are both at (x,y) at the same time for some x and y, they will crash into each other. Therefore, he is asking you to find the minimum number 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 cases t (1≤t≤100).

Each test case contains three lines. The first line of each test case consists of two integers n and m (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 contains n integers. Each integer is a train number that is scheduled to start from the bottom end. The numbers are given in strictly increasing order, and are between 1 and 100, inclusive.

The third line of each test case contains mm integers. Each integer is a train number that is scheduled to start from the left end. The numbers are given in strictly increasing order, and are between 1 and 100, 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.

풀이

두개의 기차가 충돌하게 되는 조건은 같은 시간에 같은 위치에서 출발한 경우가 된다.

따라서 입력되는 2개의 배열에서 같은 숫자가 나오는 횟수를 출력하면 된다.

#include<stdio.h>
int main()
{
    int i,j,n,m,t,train[101],train2[101],cnt=0;
    scanf("%d\n",&t);
    while(t--)
    {
        scanf("%d %d\n",&n,&m);
        for(i=0;i<n;i++)
        {
            scanf("%d",&train[i]);
        }
        for(j=0;j<m;j++)
        {
            scanf("%d",&train2[j]);
        }
        cnt=0;
        for(i=0;i<n;i++)
        {
            for(j=0;j<m;j++)
            {
                if(train[i]==train2[j]) cnt++;
                else continue;
            }
        }
        printf("%d\n",cnt);
    }
    return 0;
}

[00:09 Pretest Passed(3)/Accepted]

한 문제만 풀었다.

B번 업솔빙 예정..

대회 시작 시간이 굉장히 특이하길래(보통은 밤 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 Div 3 후기겸 풀이를 올려보려고 한다.

사실 코포 대회는 주로 저녁 11시 35분에서 새벽 1시 35분까지 열리기 때문에(러시아에서 열리는 대회라 그렇다) 12시에 칼같이 자는 나에게는 적합한 대회가 아니다. (...)

그래도 재미삼아 A번이라도 풀기 위해 대회에 참가했다.(그리고 목표에 충실하게 A번만 풀고 빤스런했다)

그럼 본격적으로 풀이와 후기를 써본다.

A. Special Permutation

Problem Statement

You are given one integer n (n>1).

Recall that a permutation of length nn is an array consisting of nn distinct integers from 1 to n in arbitrary order. For example, [2,3,1,5,4] is a permutation of length 5, but [1,2,2] is not a permutation (2 appears twice in the array) and [1,3,4] is also not a permutation (n=3 but there is 4 in the array).

Your task is to find a permutation p of length n that there is no index i (1≤i≤n) such that pi=i(so, for all i from 1 to n the condition pi≠i should be satisfied).

You have to answer t independent test cases.

If there are several answers, you can print any. It can be proven that the answer exists for each n>1.

Input

The first line of the input contains one integer t (1≤t≤100) — the number of test cases. Then t test cases follow.

The only line of the test case contains one integer n (2≤n≤100) — the length of the permutation you have to find.

Output

For each test case, print n distinct integers p1,p2,…,pn — a permutation that there is no index i (1≤i≤n) such that pi=i (so, for all i from 1 to n the condition pi≠i should be satisfied).

If there are several answers, you can print any. It can be proven that the answer exists for each n>1.

풀이

쉽게 생각하면 쉽고, 어렵게 생각하면 어려운 문제이다.

문제를 번역하면 이렇다.

'n이 주어질 때 n의 순열 p1,p2,…,pn 중 pi≠i 인 순열을 아무거나 출력하세요'

이를 더 간단하게 바꾸면 다음과 같다.

'n이 주어질 때 n의 교란순열중 하나를 출력하세요'

따라서 n의 순열 중 기본적인 것인 1, 2, ..., n 을 한칸씩 밀려쓴 순열을 출력하면 정답이 된다.

#include <stdio.h>
int main()
{
    int t,i;
    scanf("%d\n",&t);
    while(t--)
    {
        int a;
        scanf("%d",&a);
        for(i=2;i<=a;i++)
        {
            printf("%d ",i);
        }
        printf("1 ");
    }
    return 0;
}

[00:09 Wrong Answer on test 2]

[00:09 Wrong Answer on test 1]

[00:10 Accepted]

a가 홀수일 때와 짝수일 때를 굳이 나눠서 생각하다가 1틀을 하고, 마지막에 띄어쓰기가 없어서 또 1틀을 했다.

이런데서 실수하지 말자... ㅠㅠ

B번은 간단한 구현 문제로 보인다. 업솔빙 예정.