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는 업솔빙 예정