Codeforces Round 690 (Div.3) 후기

2020. 12. 20. 13:05

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

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

바로 풀이로 들어가자.

A. Favorite Sequence

Problem statement

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

he wrote the number $a_{1}$ to the left side (at the beginning of the whiteboard);
he wrote the number $a_{2}$ to the right side (at the end of the whiteboard);
then as far to the left as possible (but to the right from $a_{1}$ ), he wrote the number $a_{3}$ ;
then as far to the right as possible (but to the left from $a_{2}$ ), he wrote the number $a_{4}$ ;
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 $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 \leq t \leq 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 \leq n \leq 300$ ) — the length of the sequence written on the whiteboard.

The next line contains $n$ integers $b_{1}, b_{2}, \dots, b_{n}$ ( $1 \leq b_{i} \leq 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 \dots 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 $1 \leq i \leq j \leq n$ ) and removes characters from the $s$ string at the positions $i, i + 1, i + 2, \dots, j$ (i.e. removes substring $s [i \dots j]$ ). More formally, Polycarp turns the string $s$ into the string $s_{1} s_{2} \dots s_{i - 1} s_{j + 1} s_{j + 2} \dots s_{n}$

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 $1 \leq t \leq 1000$ ) — number of test cases in the test. Then $t$ test cases follow.

The first line of each test case contains an integer $n$ (4 $4 \leq n \leq 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 $s$ 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 \leq t \leq 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 \leq x \leq 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번이 생각보다 쉬워서 좋았다.(--)

저작자표시

'대회 후기 > Codeforces' 카테고리의 다른 글

SIT STAR Contest 2021 practice (0)	2021.02.08
SIT Contest A, B, C, D Editorial (0)	2021.02.08
Codeforces Round #688 (Div. 2) 후기 (0)	2020.12.14
Codeforces Round #687 (Div. 2) 후기 (2)	2020.12.01
Codeforces Round #686 (Div.3) 후기 (0)	2020.11.25

CodeupCoder's Blog