codeforce 1300

COFO::1425H Huge Boxes of Animal Toys

cofo problem

COFO::1425H Huge Boxes of Animal Toys

Link : COFO::1425H

Problem

level : 1300
tag : constructive algorithms
어떻게 풀어야할까 고민을 꽤 했지만, 영역이 4개라는 점과 무한대를 이용할 수 있다는 점을 생각해내면 풀 수 있는 문제였습니다.

Point

4개의 영역에 포함된 숫자의 갯수 A, B, C, D가 주어집니다.
4개의 영역은 다음과 같습니다.
- (−∞,−1]
- (−1,0)
- (0,1)
- [1,∞)
주어진 A + B + C + D 개의 숫자 중 2개씩 선택해서 곱한 후 그 결과를 다시 네 영역 중 하나에 담습니다.
이와 같은 과정을 반복해서 숫자가 1개만 남을때까지 반복합니다.
이때 이 하나의 수가 포함될 수 있는 영역에는 Ya를, 그렇지 않은 경우 Tidak를 출력합니다.

Design

4개의 영역 모두 무한대라는 특징이 있습니다.
A , D 영역은 무한대로 큰 수를 정할 수 있다는 점이고,
B, C 영역은 무한대로 작은 수를 정할 수 있다는 점입니다.
이를 이용해서 크게 4가지 특성만 정해주면 답을 찾을 수 있습니다.
- 첫번째 박스에 오려면
  - 음수이고, -1보다 작은 수
- 두번째 박스에 오려면
  - 음수이고, -1과 0사이의 수
- 세번째 박스에 오려면
  - 양수이고, 0과 1 사이의 수
- 네번째 박스에 오려면
  - 양수이고, 1보다 큰 수
이를위해 코드에 적어두었듯이 주어진 A, B, C, D를 통해 다음 4가지의 특성을 찾을 수 있습니다.
- 결과값이 음수인가
- 결과값이 양수인가
- 결과값이 0과 1사이에 올 수 있는가
- 결과값이 1보다 클 수 있는가

Big O(time)

O(N)

Code

// https://beenpow.github.io/
#define rep(i,a,b) for(int i=(a);i<(b);i++)
#define r_rep(i,a,b) for(int i=(a);i>(b);i--)
#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
typedef long long ll;
using namespace std;

bool beMinus(int a, int b, int c, int d){return (a+b)%2 == 1;}
bool bePlus (int a, int b, int c, int d){return (a+b)%2 == 0;}
bool beSmall(int a, int b, int c, int d){return (b+c) >= 1;}
bool beLarge(int a, int b, int c, int d){return (a+d) >= 1;}

void solve(){
    int ans[4] = {0, 0, 0, 0};
    int q, w, e, r;
    cin >> q >> w >> e >> r;
    // box 1
    if(beMinus(q, w, e, r) && beLarge(q, w, e, r)) ans[0] = 1;
    
    // box 2
    if(beMinus(q, w, e, r) && beSmall(q, w, e, r)) ans[1] = 1;
    
    // box 3
    if(bePlus(q, w, e, r) && beSmall(q, w, e, r)) ans[2] = 1;
    
    // box 4
    if(bePlus(q, w, e, r) && beLarge(q, w, e, r)) ans[3] = 1;
    
    rep(i, 0, 4){
        if(ans[i] == 1) cout << "Ya ";
        else cout << "Tidak ";
    }cout << '\n';
}
int main(){
    //freopen("input.txt", "r", stdin);
    int tc; cin >> tc;
    while(tc--)
        solve();
    return 0;
}
 