CuteWisp

[C++] AtCoder Beginner Contest 187 A번 Large Digits

14 Jan 2021 | PS

AtCoder Beginner Contest 187 A번 Large Digits

문제

https://atcoder.jp/contests/abc187/tasks/abc187_a abc187_a

풀이

입력받은 두 수중 각 자릿수 합이 높은 수의 각 자릿수 합을 출력하는 문제 입력받은 두 수 A,B 는 세자리 수로 고정되어있기 때문에 각 수의 자릿수 합을 구해서 큰 수를 출력하면 정답

코드

#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/abc187/tasks/abc187_a
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    ll a,b;
    cin >> a >> b;
    ll _a = 0, _b = 0;
    while(a){
        _a += a%10;
        a/=10;
    }
    while(b){
        _b += b%10;
        b/=10; 
    }
    cout << max(_a,_b);

    return 0;
}

[C++] AtCoder Beginner Contest 186 D번 Sum of difference

13 Jan 2021 | PS

AtCoder Beginner Contest 186 D번 Sum of difference

문제

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

풀이

입력 받은 수열의 모든 pair의 차의 합을 구하는 문제

Ai - Aj 를 구한다고 할 때 j를 고정시키고 생각해보자

N = 3이며 A는 sort되어 있다고 가정해 보자. j = 2일때

  • A2 - A0
  • A2 - A1 = 2A2 - (A0 + A1) = jAj - Sj

여기서 S는 A의 누적합계이다.

j*Aj - Sj를 j= 0,1,…N 까지 반복하면 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/abc186/tasks/abc186_d
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
 
    ll n;
    cin >> n;
    vll a(n);
    for(int i = 0;i<n;i++){
        cin >> a[i];
    }
    sort(all(a));
    ll ans=0, tmp=0;
    for(int i = 1;i<n;i++){
        tmp += ((a[i]-a[i-1]) * i);
        ans += tmp;
    }
    cout << ans;
 
    return 0;
}

[C++] AtCoder Beginner Contest 186 C번 Unlucky 7

13 Jan 2021 | PS

AtCoder Beginner Contest 186 C번 Unlucky 7

문제

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

풀이

1부터 n까지의 수 중 10진수와 8진수에서 7이 존재하지 않는 수는 몇가지인지 세는 문제

n <= 10^5이기 때문에 모든 수를 돌면서 체크해도 충분히 통과가 가능하다.

코드

#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_c
string toOct(ll n){
    string s = "";
    while(n){
        s += to_string(n%8);
        n /= 8;
    }
    return s;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
 
    ll n;
    cin >> n;
    ll ans = 0;
    for(ll i = 1;i<=n;i++){
        if(to_string(i).find('7') == -1 && toOct(i).find('7') == -1)
            ans++;
    }
    cout << ans;
    
    return 0;
}

[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;
}