13 Jan 2021 |
PS
AtCoder Beginner Contest 185 C번 Duodecim Ferra
문제
https://atcoder.jp/contests/abc185/tasks/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;
}
13 Jan 2021 |
PS
AtCoder Beginner Contest 185 B번 Smartphone Addiction
문제
https://atcoder.jp/contests/abc185/tasks/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;
}
13 Jan 2021 |
PS
AtCoder Beginner Contest 185 A번 ABC Preparation
문제
https://atcoder.jp/contests/abc185/tasks/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;
}
03 Jan 2021 |
PS
AtCoder Beginner Contest 184 C번 Super Ryuma
문제
https://atcoder.jp/contests/abc184/tasks/abc184_c
풀이
(r1,c1)에서 (r2,c2)로 이동할 때 총 몇번의 이동으로 도착할 수 있는 지 구하는 문제
이동 할 때는 (a,b)에서 (c,d)로 이동한다고 할 때
-
(1) *a+b = c+d
-
(2) a-b = c-d
-
인 경우에만 이동할 수 있다.
(1)과 (2)를 사용하면 동일한 parity를 가진 모든 점으로 이동할 수 있다.
여기에 (3)을 추가로 사용하면 최대 3번의 이동으로 모든 점으로 이동할 수 있게 된다.
코드
#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/abc184/tasks/abc184_c
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
ll r1,c1,r2,c2;
cin >> r1 >> c1 >> r2 >> c2;
ll r = r2-r1;
ll c = c2-c1;
ll ans = 3;
if(r == 0 && c == 0) ans = 0;
else if(r == c || r == -c || abs(r) + abs(c) <= 3) ans = 1;
else if((r1 + r2 + c1 + c2)%2 == 0 || abs(r + c) <= 3 || abs(r - c) <= 3 || abs(r) + abs(c) <= 6) ans = 2;
cout << ans;
return 0;
}
03 Jan 2021 |
PS
AtCoder Beginner Contest 184 B번 Quizzes
문제
https://atcoder.jp/contests/abc184/tasks/abc184_b
풀이
n개의 퀴즈가 있고 x포인트로 시작 할 때 하나 맞출때마다 1점을 얻고 하나 틀릴때마다 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/abc184/tasks/abc184_b
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
ll n,x;
string s;
cin >> n >> x;
cin >> s;
for(ll i = 0;i<n;i++){
if(s[i] == 'x'){
if(x != 0) x--;
}
else{
x++;
}
}
cout << x;
return 0;
}