[코드포스 Practice8] D. Team

Now it's time of Olympiads. Vanya and Egor decided to make his own team to take part in a programming Olympiad. They've been best friends ever since primary school and hopefully, that can somehow help them in teamwork.

지금은 올림피아드 시간입니다. Vanya와 Egor는 프로그래밍 올림피아드에 참가하기 위해 팀을 만들기로 결정합니다. 그들은 초등학교때부터 절친한 친구였고 희망컨데 그것이 팀워크에 어떻게든 도움이 될 수 있습니다. 

For each team Olympiad, Vanya takes his play cards with numbers. He takes only the cards containing numbers 1 and 0. The boys are very superstitious. They think that they can do well at the Olympiad if they begin with laying all the cards in a row so that:

각각의 팀 올림피아드에서 Vanya는 숫자가 있는 놀이카드를 가져갑니다. 그는 오직 0과 1이 쓰여져 있는 카드만 가져갑니다. 그 소년들은 아주 미신적입니다. 그들은 만약 그들이 모든 카드를 가로로 놓으면 올림피아드에서 잘 할 수 있다고 생각합니다. 다음과 같이 :

there wouldn't be a pair of any side-adjacent cards with zeroes in a row;
there wouldn't be a group of three consecutive cards containing numbers one.

곁에 인접한 0카드 쌍이 없어야 한다

세개가 연이은 1카드 묶음이 없어야 한다

Today Vanya brought n cards with zeroes and m cards with numbers one. The number of cards was so much that the friends do not know how to put all those cards in the described way. Help them find the required arrangement of the cards or else tell the guys that it is impossible to arrange cards in such a way.

오늘 Vanya는 n개의 0카드와 m개의 1카드를 들고왔다. 카드의 숫자는 엄청 많아서 그 친구들은 어떻게 서술된 방식으로 놓는지 모른다. 카드의 요구된 배치를 찾도록 도와줘라 또는 그 방법으로 카드를 배치하는 건 불가능하다고 애들한테 알려줘라

Input
The first line contains two integers: n (1 ≤ n ≤ 10^6) — the number of cards containing number 0; m (1 ≤ m ≤ 10^6) — the number of cards containing number 1.

첫번째 줄은 두개의 정수를 포함한다. n -- 0을 포함하는 카드의 개수; m -- 1을 포함하는 카드의 개수

Output
In a single line print the required sequence of zeroes and ones without any spaces. If such sequence is impossible to obtain, print -1.

한 줄에 0과 1의 요구된 순서를 띄우지 말고 출력해라. 만약 그런 순서를 얻기 어려울 경우 -1을 출력해라.

---

이 문제는 무난히 풀었다. 난이도가 갈수록 어려워져서 보통 한 문제 건너뛰면 다음 문제도 못 푸는 경우가 많은데 이건 건너뛰고도 풀었다! 

 

조건이 0은 연속되면 안 되고 1은 세 개 이상 연속되면 안 된다. 예제 출력을 보니 0이 더 조건이 까다로워서 0을 기준으로 1의 개수를 구하면 되겠다 싶었다. 다음으로 가능한 1의 개수 범위를 구해서 범위를 벗어나면 -1을 출력한다. 이제 최소 1의 개수는 있으니 최소 문자열 사이에 남은 1을 끼워주면 끝~~

 

로직은 짜려다 시간 아까워서 적다 말았다. 

 

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <functional>
#include <string>
 
using namespace std;
using i64 = long long;
 
int main() {
    int n, m;
    scanf("%d %d", &n, &m);
    
    int min = n-1;
    int max = (n+1)*2;
    
    if(m < min || max < m){
        printf("-1");
        return 0;
    }
    
    int all = m - min;
    
    for(int i = 0; i < 2; i++){
        if(all > 0){
            printf("1");
            all--;
        }
    }
    for(int i = 0; i < n-1; i++){
        printf("01");
        if(all > 0){
            printf("1");
            all--;
        }
    }
    printf("0");
    for(int i = 0; i < 2; i++){
        if(all > 0){
            printf("1");
            all--;
        }
    }
    
    
    return 0;
}

 

먼저 최대와 최소 1의 개수를 구한 다음, 1이 이 범위를 벗어나는지 확인한다. 

 

다음으로 남은 1의 개수를 구해 all에 저장한다. (변수명 짓는 센스 보소)

이제 반복문을 세 번 도는데 첫번째 반복문은 최소 문자열 앞에 들어갈 1을 적는 일을 하고 두번째 반복문은 0과 0사이에 1을 적는 일을 하고 마지막 반복문은 끝네 들어갈 1을 적어준다.