Codeforces Round #662 (Div. 2) ABC

from sys import stdin
def input(): return stdin.readline().rstrip()
 
for _ in range(int(input())):
    n=int(input())
    print(1+n//2)

 

A - Rainbow Dash, Fluttershy and Chess Coloring

 

 

직접 시뮬레이션 해 보면 1 - 2 - 2 - 3 - 3 - 4 - 4 - ... 순으로 답이 됨을 알 수 있다.

 

 

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <map>
using namespace std;

int n, q;
map<int,int> plank;

char oper;
int target;

int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n;
    for (int i = 0; i < n; ++i) {
        int input;
        cin >> input;
        plank[input]++;
    }

    cin >> q;
    while (q--) {
        cin >> oper >> target;
        if (oper == '+') { plank[target]++; n++; }
        else { plank[target]--; n--; }

        if (n < 8) {
            cout << "NO\n";
            continue;
        }

        bool sq = false;
        long long cnt = 0;
        for (pair<int,int> ne : plank) {
            int next = ne.second;
            if (next == 2 || next == 3) {
                cnt += 1;
            }
            else if (next > 3) {
                if (sq == false) {
                    sq = true;
                    cnt += (next - 4) / 2;
                }
                else {
                    cnt += next / 2;
                }
            }
            if (cnt >= 2 && sq) {
                break;
            }
        }

        if (cnt >= 2 && sq) {
            cout << "YES\n";
        }
        else {
            cout << "NO\n";
        }
    }

    return 0;
}

 

B - Applejack and Storages (TLE)

 

 

입력에서 plank를 크기별로 분류한다.

 

같은 길이의 판자가 네 개 이상 있다면 정사각형 모양의 창고를 지을 수 있고,

두 개 이상 있다면 직사각형 모양의 창고의 벽 중 두 변을 지을 수 있다.

 

위 과정에 사용하고 남은 판자가 둘 이상일 수 있음에 유의한다.

 

 

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;
 
int T;
long long n;
long long cake[100001];
long long res = 0;
 
long long maxCake = 0;
vector<int> modecake;
long long rest = 0;
 
int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    
    cin >> T;
    while (T--) {
        modecake.clear();
        maxCake = 0;
        rest = 0;
        res = 0;
        for (auto& next : cake) next = 0;
 
        cin >> n;
        for (int i = 0; i < n; ++i) {
            int input;
            cin >> input;
            cake[input]++;
 
            if (cake[input] > maxCake) {
                modecake.clear();
                maxCake = cake[input];
                modecake.push_back(input);
            }
            else if (cake[input] == maxCake) {
                modecake.push_back(input);
            }
        }
 
        if (n == 2) {
            cout << 0 << "\n";
            continue;
        }
 
        for (int i = 1; i <= 100000; ++i) {
            if (cake[i] < maxCake) {
                rest += cake[i];
            }
        }
 
        res = max(0, (int)modecake.size() - 1);
        res += rest / (maxCake - 1);
 
        /*
        if (modecake.size() == 1) {
            res = rest / (maxCake - 1);
        }
        else {
            res = rest;
            res += modecake.size() - 1;
        }
        */
 
        cout << res << "\n";
    }
 
    return 0;
}

 

C - Pinkie Pie Eats Patty-cakes

가장 자주 등장한 종류의 케이크를 M 이라고 하자.

M은 여러 개 존재할 수 있다. (1 2 2 3 3 이라면 종류 2, 종류 3을 M 이라고 할 수 있다.)

 

최소한 (M 의 갯수 - 1) 만큼의 거리를 둘 수 있음이 보장된다. 

 

나머지 케이크를 중앙에 끼워 넣어 거리를 더 벌릴 수 있다.

그 거리는 floor( 나머지 케이크의 수 /  한 M의 등장 횟수 ) 와 같다.