AtCoder Beginner Contest 茶diff埋め


###[C - Ubiquity](https://atcoder.jp/contests/abc178/tasks/abc178_c)

```Python3:Python3
n = int(input())
print((10**n-9**n-9**n+8**n)%(10**9+7))
```

```C++:C++
#include<iostream>
#include<vector>
#include<algorithm>
#include<iomanip>
#include<utility>
#include<iomanip>
#include<map>
#include<queue>
#include<stack>
#include<cmath>
#include<cstdio>
#include<list>
#include<set>
#include<bitset>

#define rep(i,n) for(int i=0; i<(n); i++)
#define fixed_setprecision(n) fixed << setprecision((n))
#define pai 3.1415926535897932384
#define NUM_MAX 2e18
#define NUM_MIN -1e9

using namespace std;
using ll =long long;
using P = pair<int,int>;

int main() {
    ll n;
    cin >> n;
    
    ll mod = 1e9+7;
    ll a=1, b=1, c=1;
    for(ll i=0; i<n; i++){
        a = (a * 10) % mod;
        b = (b * 9) % mod;
        c = (c * 8) % mod;
    }
    ll ans = (a-b-b+c)%mod;
    ans = (ans+mod)%mod;
    cout << ans << endl;
    
    return 0;
}
```

###[D - Wandering](https://atcoder.jp/contests/abc182/tasks/abc182_d)

```C++:C++
#include<iostream>
#include<vector>
#include<algorithm>
#include<iomanip>
#include<utility>
#include<iomanip>
#include<map>
#include<queue>
#include<stack>
#include<cmath>
#include<cstdio>
#include<list>
#include<set>
#include<bitset>

#define rep(i,n) for(int i=0; i<(n); i++)
#define fixed_setprecision(n) fixed << setprecision((n))
#define pai 3.1415926535897932384
#define NUM_MAX 2e18
#define NUM_MIN -1e9

using namespace std;
using ll =long long;
using P = pair<int,int>;

int main() {
    int n;
    cin >> n;
    
    vector<int> A(n);
    rep(i, n) cin >> A[i];
    
    ll ans = 0;
    ll b=0, s=0, max_b=0;
    for(int i=0; i<n; i++){
        b += A[i];
        max_b = max(max_b, b);
        ans = max(ans, s+max_b);
        s += b;
    }
    cout << ans << endl;
    
    return 0;
}
```

###[C - Guess The Number](https://atcoder.jp/contests/abc157/tasks/abc157_c)

```C++:C++
#include<iostream>
#include<vector>
#include<algorithm>
#include<iomanip>
#include<utility>
#include<iomanip>
#include<map>
#include<queue>
#include<stack>
#include<cmath>
#include<cstdio>
#include<list>
#include<set>
#include<bitset>

#define rep(i,n) for(int i=0; i<(n); i++)
#define fixed_setprecision(n) fixed << setprecision((n))
#define pai 3.1415926535897932384
#define NUM_MAX 2e18
#define NUM_MIN -1e9

using namespace std;
using ll =long long;
using P = pair<int,int>;

int main() {
    int n, m;
    cin >> n >> m;
    
    string ans;
    rep(i, n) ans += '0';
    
    int A[5]={-1};
    rep(i, m){
        int s, c;
        cin >> s >> c;
        s--;
        if(ans[s] == '0' || ans[s] == c+'0') ans[s] = c + '0';
        else{
            ans = "-1";
            break;
        }
        A[s]=c;
    }
    
    if(ans[0]=='0'){
        if(A[0]==-1 && ans.length()>1) ans[0]='1';
        if(A[0]==0 && ans.length()>1) ans="-1";
    }
    cout << ans << endl;
    
    return 0;
}
```

###[C - Typical Stairs](https://atcoder.jp/contests/abc129/tasks/abc129_c)

```C++:C++
#include<iostream>
#include<vector>
#include<algorithm>
#include<iomanip>
#include<utility>
#include<iomanip>
#include<map>
#include<queue>
#include<stack>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<cctype>
 
#define rep(i,n) for(int i=0; i<(n); ++i)
#define fixed_setprecision(n) fixed << setprecision((n))
#define pai 3.1415926535897932384
#define NUM_MAX 2e18
#define NUM_MIN -1e9
 
using namespace std;
using ll =long long;
using P = pair<int,int>;
template<class T> inline bool chmax(T& a, T b){ if(a<b){ a=b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b){ if(a>b){ a=b; return 1; } return 0; }
const long long INF = 1LL << 60;
 
int dp[100002];
 
int main(int argc, const char * argv[]) {
    int mod = 1e9+7;
    int N, M;
    cin >> N >> M;
 
    rep(i, N+2) dp[i] = 0;
    rep(i, M){
        int a;
        cin >> a;
        dp[a] = -1;
        if(a>0 && dp[a-1]==-1) { cout << 0 << endl; return 0; }
    }
    
    dp[0]=0;
    if(dp[1]==0) dp[1] = 1;
    if(dp[1]==-1) dp[2] = 1;
    else dp[2] = 2;
    
    for(int i=3; i<=N; i++){
        if(dp[i]==0){
            if(dp[i-1]==-1) dp[i] = dp[i-2];
            else if(dp[i-2]==-1) dp[i] = dp[i-1];
            else dp[i] = (dp[i-1] + dp[i-2]) % mod;
        }
    }
    
    cout << dp[N] << endl;
    
    return 0;
}
```

###[C - Dice and Coin](https://atcoder.jp/contests/abc126/tasks/abc126_c)

```C++:C++
#include<iostream>
#include<vector>
#include<algorithm>
#include<iomanip>
#include<utility>
#include<iomanip>
#include<map>
#include<queue>
#include<stack>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<cctype>
 
#define rep(i,n) for(int i=0; i<(n); ++i)
#define fixed_setprecision(n) fixed << setprecision((n))
#define pai 3.1415926535897932384
#define NUM_MAX 2e18
#define NUM_MIN -1e9
 
using namespace std;
using ll =long long;
using P = pair<int,int>;
template<class T> inline bool chmax(T& a, T b){ if(a<b){ a=b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b){ if(a>b){ a=b; return 1; } return 0; }
const long long INF = 1LL << 60;
 
 
int main(int argc, const char * argv[]) {
    double N, K;
    cin >> N >> K;
    
    int cc=1;
    double sum=0;
    while(cc<=N){
        int c=cc;
        double cnt=0;
        while(c<K){
            cnt++;
            c=c*2;
        }
        sum += (1.0/N) * pow(1.0/2.0, cnt);
        cc++;
    }
    
    cout << fixed_setprecision(10) << sum << endl;
    
    return 0;
}
```

```C++:C++
#include<iostream>
#include<vector>
#include<algorithm>
#include<iomanip>
#include<utility>
#include<iomanip>
#include<map>
#include<queue>
#include<stack>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<cctype>

#define rep(i,n) for(int i=0; i<(n); ++i)
#define fixed_setprecision(n) fixed << setprecision((n))
#define pai 3.1415926535897932384
#define NUM_MAX 2e18
#define NUM_MIN -1e9

using namespace std;
using ll =long long;
using P = pair<int,int>;
template<class T> inline bool chmax(T& a, T b){ if(a<b){ a=b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b){ if(a>b){ a=b; return 1; } return 0; }
const long long INF = 1LL << 60;


int main(int argc, const char * argv[]) {
    double N, K;
    cin >> N >> K;
    
    int cc=1;
    double sum=0;
    while(cc<=N){
        int c=cc;
        double tmp=1.0/(double)N;
        while(c<K){
            tmp/=2.0;
            c=c*2;
        }
        sum+=tmp;
        cc++;
    }
    
    cout << fixed_setprecision(10) << sum << endl;
    
    return 0;
}
```

###[C - Rectangle Cutting](https://atcoder.jp/contests/abc130/tasks/abc130_c)

```C++:C++
#include<iostream>
#include<vector>
#include<algorithm>
#include<iomanip>
#include<utility>
#include<iomanip>
#include<map>
#include<queue>
#include<stack>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<cctype>

#define rep(i,n) for(int i=0; i<(n); ++i)
#define fixed_setprecision(n) fixed << setprecision((n))
#define execution_time(ti) printf("Execution Time: %.4lf sec\n", 1.0 * (clock() - ti) / CLOCKS_PER_SEC);
#define pai 3.1415926535897932384
#define NUM_MAX 2e18
#define NUM_MIN -1e9

using namespace std;
using ll =long long;
using P = pair<int,int>;
template<class T> inline bool chmax(T& a, T b){ if(a<b){ a=b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b){ if(a>b){ a=b; return 1; } return 0; }
const long long INF = 1LL << 60;

int main(int argc, const char * argv[]) {
    ll W, H, x, y;
    cin >> W >> H >> x >> y;
    cout << fixed_setprecision(10) << double(W*H)/2.0 << ' ' << (x+x==W && y+y==H? 1:0) << endl;
    
    return 0;
}
```

###[C - Anti-Division](https://atcoder.jp/contests/abc131/tasks/abc131_c)

```C++:C++
#include<iostream>
#include<vector>
#include<algorithm>
#include<iomanip>
#include<utility>
#include<iomanip>
#include<map>
#include<queue>
#include<stack>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<cctype>

#define rep(i,n) for(int i=0; i<(n); ++i)
#define fixed_setprecision(n) fixed << setprecision((n))
#define execution_time(ti) printf("Execution Time: %.4lf sec\n", 1.0 * (clock() - ti) / CLOCKS_PER_SEC);
#define pai 3.1415926535897932384
#define NUM_MAX 2e18
#define NUM_MIN -1e9

using namespace std;
using ll =long long;
using P = pair<int,int>;
template<class T> inline bool chmax(T& a, T b){ if(a<b){ a=b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b){ if(a>b){ a=b; return 1; } return 0; }
const long long INF = 1LL << 60;

ll gcd(ll c, ll d){
    if(c<d) swap(c, d);
    while(d>0){
        ll r = c%d;
        c = d;
        d = r;
    }
    return c;
}

ll anti_division(ll n, ll c, ll d){
    ll g = gcd(c, d);
    ll l = c / g * d;
    return n - n/c - n/d + n/l;
}

int main(int argc, const char * argv[]) {
    ll A, B, C, D;
    cin >> A >> B >> C >> D;
    cout << anti_division(B, C, D) - anti_division(A-1, C, D) << endl;
    
    return 0;
}
```

###[C - Remainder Minimization 2019](https://atcoder.jp/contests/abc133/tasks/abc133_c)

```C++:C++
#include<iostream>
#include<vector>
#include<algorithm>
#include<iomanip>
#include<utility>
#include<iomanip>
#include<map>
#include<queue>
#include<stack>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<cctype>

#define rep(i,n) for(int i=0; i<(n); ++i)
#define fixed_setprecision(n) fixed << setprecision((n))
#define execution_time(ti) printf("Execution Time: %.4lf sec\n", 1.0 * (clock() - ti) / CLOCKS_PER_SEC);
#define pai 3.1415926535897932384
#define NUM_MAX 2e18
#define NUM_MIN -1e9

using namespace std;
using ll =long long;
using P = pair<int,int>;
template<class T> inline bool chmax(T& a, T b){ if(a<b){ a=b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b){ if(a>b){ a=b; return 1; } return 0; }
const long long INF = 1LL << 60;

int main(int argc, const char * argv[]) {
    ll L, R;
    cin >> L >> R;
    
    if(R-L>=2019) { cout << 0 << endl; return 0; }
    
    ll res=INF;
    for(ll i=L; i<=min(R, L+2018); i++){
        for(ll j=i+1; j<=min(R, L+2018); j++){
            res = min(res, (i*j)%2019);
        }
    }
    cout << res << endl;

    return 0;
}
```

###[C - Green Bin](https://atcoder.jp/contests/abc137/tasks/abc137_c)

```C++:C++
#include<iostream>
#include<vector>
#include<algorithm>
#include<iomanip>
#include<utility>
#include<iomanip>
#include<map>
#include<queue>
#include<stack>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<cctype>

#define rep(i,n) for(int i=0; i<(n); ++i)
#define fixed_setprecision(n) fixed << setprecision((n))
#define execution_time(ti) printf("Execution Time: %.4lf sec\n", 1.0 * (clock() - ti) / CLOCKS_PER_SEC);
#define pai 3.1415926535897932384
#define NUM_MAX 2e18
#define NUM_MIN -1e9

using namespace std;
using ll =long long;
using P = pair<int,int>;
template<class T> inline bool chmax(T& a, T b){ if(a<b){ a=b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b){ if(a>b){ a=b; return 1; } return 0; }
const long long INF = 1LL << 60;

int main(int argc, const char * argv[]) {
    int N;
    cin >> N;
    
    map<string, ll> mp;
    rep(i, N){
        string s;
        cin >> s;
        
        sort(s.begin(), s.end());
        mp[s]++;
    }
    
    ll res=0;
    for(map<string, ll>::iterator itr=mp.begin(); itr!=mp.end(); itr++){
        res += itr->second * (itr->second-1) / 2 ;
    }
    cout << res << endl;
    
    return 0;
}
```

###[C - Buy an Integer](https://atcoder.jp/contests/abc146/tasks/abc146_c)

```C++:C++
#include<iostream>
#include<vector>
#include<algorithm>
#include<iomanip>
#include<utility>
#include<iomanip>
#include<map>
#include<queue>
#include<stack>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<cctype>

#define rep(i,n) for(int i=0; i<(n); ++i)
#define fixed_setprecision(n) fixed << setprecision((n))
#define execution_time(ti) printf("Execution Time: %.4lf sec\n", 1.0 * (clock() - ti) / CLOCKS_PER_SEC);
#define pai 3.1415926535897932384
#define NUM_MAX 2e18
#define NUM_MIN -1e9

using namespace std;
using ll =long long;
using P = pair<int,int>;
template<class T> inline bool chmax(T& a, T b){ if(a<b){ a=b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b){ if(a>b){ a=b; return 1; } return 0; }
const long long INF = 1LL << 60;

ll d(ll a) {
    ll res = 0;
    while (a) {
        ++res;
        a /= 10;
    }
    return res;
}

int main(int argc, const char * argv[]) {
    ll A, B, X;
    cin >> A >> B >> X;
    
    ll left = 0, right = 1000000001;
    while(right-left>1){
        ll mid = (left + right) / 2;
        if(A*mid + B*d(mid)>X){
            right=mid;
        }else{
            left=mid;
        }
    }
    cout << left << endl;
    
    return 0;
}
```