CuteWisp

[C++] AtCoder Beginner Contest 186 B번 Blocks on Grid

13 Jan 2021 | PS

AtCoder Beginner Contest 186 B번 Blocks on Grid

문제

https://atcoder.jp/contests/abc186/tasks/abc186_b abc186_b

풀이

H x W 만큼의 격자에 Ai,j 만큼의 블록이 쌓여있을 때 최소 몇개를 제거해야 모든 격자의 블록 높이가 동일해 지는지 묻는 문제

블록을 추가하는것이 아닌 제외만 할 수 있다는것에 유의

모든 칸을 가장 높이가 낮은 칸에 맞추면 가능하다

H,W <= 100 이기 때문에 O(n^2)으로도 충분히 해결 가능

코드

#pragma warning(disable : 4996)
#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
using namespace std;
typedef long long ll;
typedef long double ld;
typedef vector<ll> vll;
typedef pair<ll, ll> pll;
typedef pair<ld, ld> pld;
typedef tuple<ll,ll,ll> tl3;
#define FOR(a, b, c) for (int(a) = (b); (a) < (c); ++(a))
#define FORN(a, b, c) for (int(a) = (b); (a) <= (c); ++(a))
#define rep(i, n) FOR(i, 0, n)
#define repn(i, n) FORN(i, 1, n)
#define tc(t) while (t--)
// https://atcoder.jp/contests/abc186/tasks/abc186_b
ll a[101][101] ={0,};
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
 
    ll h,w;
    cin >> h >> w;
    ll low = 101 , high = -1;
    for(int i = 0;i<h;i++){
        for(int j = 0;j<w;j++){
            cin >> a[i][j];
            low = min(low, a[i][j]);
            high = max(high,a[i][j]);
        }
    }
    ll ans = 0;
    for(int i = 0;i<h;i++){
        for(int j = 0;j<w;j++){
            ans += (a[i][j] - low);
        }
    }
    cout << ans;
 
    return 0;
}

[C++] AtCoder Beginner Contest 186 A번 Brick

13 Jan 2021 | PS

AtCoder Beginner Contest 186 A번 Brick

문제

https://atcoder.jp/contests/abc186/tasks/abc186_a abc186_a

풀이

트럭이 최대 N 킬로그램을 싣고 달릴 수 있을 때 W 킬로그램만큼의 짐을 옮기려면 몇번을 옮겨야하는지 묻는 문제

N / W를 출력하면 정답

코드

#pragma warning(disable : 4996)
#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
using namespace std;
typedef long long ll;
typedef long double ld;
typedef vector<ll> vll;
typedef pair<ll, ll> pll;
typedef pair<ld, ld> pld;
typedef tuple<ll,ll,ll> tl3;
#define FOR(a, b, c) for (int(a) = (b); (a) < (c); ++(a))
#define FORN(a, b, c) for (int(a) = (b); (a) <= (c); ++(a))
#define rep(i, n) FOR(i, 0, n)
#define repn(i, n) FORN(i, 1, n)
#define tc(t) while (t--)
// https://atcoder.jp/contests/abc186/tasks/abc186_a
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
 
    ll n,w;
    cin >> n >> w;
    cout << n / w;
 
    return 0;
}

[C++] AtCoder Beginner Contest 185 C번 Duodecim Ferra

13 Jan 2021 | PS

AtCoder Beginner Contest 185 C번 Duodecim Ferra

문제

https://atcoder.jp/contests/abc185/tasks/abc185_c abc185_c

풀이

길이가 L인 막대가 있을 때 11곳을 잘라서 총 12마디를 만든다고 할 때 총 가능한 경우의 수를 구하는 문제

단순한 경우의 수 문제로 Combination(L-1, 11) 만큼의 경우의 수가 나온다.

코드

#pragma warning(disable : 4996)
#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
using namespace std;
typedef long long ll;
typedef long double ld;
typedef vector<ll> vll;
typedef pair<ll, ll> pll;
typedef pair<ld, ld> pld;
typedef tuple<ll, ll, ll> tl3;
#define FOR(a, b, c) for (int(a) = (b); (a) < (c); ++(a))
#define FORN(a, b, c) for (int(a) = (b); (a) <= (c); ++(a))
#define rep(i, n) FOR(i, 0, n)
#define repn(i, n) FORN(i, 1, n)
#define tc(t) while (t--)
// https://atcoder.jp/contests/abc185/tasks/abc185_c
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
 
    ll l;
    cin >> l;
    ll ans = 1;
    repn(i,11) {
        ans *= (l-i);
        ans /= i;
    }
    cout << ans;
    
    return 0;
}

[C++] AtCoder Beginner Contest 185 B번 Smartphone Addiction

13 Jan 2021 | PS

AtCoder Beginner Contest 185 B번 Smartphone Addiction

문제

https://atcoder.jp/contests/abc185/tasks/abc185_b abc185_b

풀이

스마트폰의 배터리가 현재 n만큼 있고 집에 t시간에 도착한다고 한다. 그때 ai ~ bi 시간에는 카페에서 충전을 한다고 할때 집까지 배터리를 다 쓰지 않고 갈 수 있는지 여부를 확인하는 문제

ai < bi < aj < bj (i < j) 가 보장되기 때문에 순서대로 체크하면서 배터리가 0이 되는지 아닌지 체크해가면서 진행하면 된다. m <= 1000이기 때문에 O(n)으로도 충분히 해결 가능한 문제

코드

#pragma warning(disable : 4996)
#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
using namespace std;
typedef long long ll;
typedef long double ld;
typedef vector<ll> vll;
typedef pair<ll, ll> pll;
typedef pair<ld, ld> pld;
typedef tuple<ll, ll, ll> tl3;
#define FOR(a, b, c) for (int(a) = (b); (a) < (c); ++(a))
#define FORN(a, b, c) for (int(a) = (b); (a) <= (c); ++(a))
#define rep(i, n) FOR(i, 0, n)
#define repn(i, n) FORN(i, 1, n)
#define tc(t) while (t--)
// https://atcoder.jp/contests/abc185/tasks/abc185_b
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
 
    bool isOk = true;
    ll n, m, t;
    cin >> n >> m >> t;
    ll tmp = 0, maxCap = n;
    rep(i, m) {
        ll a, b;
        cin >> a >> b;
        n -= a - tmp;
        if (n < 1) {
            cout << "No";
            return 0;
        }
        n = min(n + (b - a), maxCap);
        tmp = b;
    }
    n -= t - tmp;
    if (n < 1) {
        cout << "No";
        return 0;
    } else
        cout << "Yes";
 
    return 0;
}

[C++] AtCoder Beginner Contest 185 A번 ABC Preparation

13 Jan 2021 | PS

AtCoder Beginner Contest 185 A번 ABC Preparation

문제

https://atcoder.jp/contests/abc185/tasks/abc185_a abc185_a

풀이

100, 200, 300, 400점 짜리 문제가 A1, A2, A3, A4개 있을 때 대회를 개최하려면 각 문제가 1개 있어야 한다고 한다. 그 때 총 몇번의 대회를 개최할 수 있는지 묻는 문제

입력값의 최소값을 출력하면 그 값이 대회를 개최할 수 있는 최댓값이 된다.

코드

#pragma warning(disable : 4996)
#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
using namespace std;
typedef long long ll;
typedef long double ld;
typedef vector<ll> vll;
typedef pair<ll, ll> pll;
typedef pair<ld, ld> pld;
typedef tuple<ll, ll, ll> tl3;
#define FOR(a, b, c) for (int(a) = (b); (a) < (c); ++(a))
#define FORN(a, b, c) for (int(a) = (b); (a) <= (c); ++(a))
#define rep(i, n) FOR(i, 0, n)
#define repn(i, n) FORN(i, 1, n)
#define tc(t) while (t--)
// https://atcoder.jp/contests/abc185/tasks/abc185_a
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
 
    ll a[4];
    cin >> a[0] >> a[1] >> a[2] >> a[3];
    cout << min(a[0],min(a[1],min(a[2],a[3])));
 
    return 0;
}