14 Mar 2021 |
PS
AtCoder Beginner Contest 195 B번 Many Oranges
문제
https://atcoder.jp/contests/abc195/tasks/abc195_b
풀이
오렌지의 합이 총 W 킬로그램이어야 한다고 할 떄, 오렌지가 N개 필요하다고 가정한다면
AN <= 1000W <= BN 이 성립한다면 오렌지 N개를 사용해서 W 킬로그램을 정확하게 맞출 수 있을것이다.
또한 그 N의 최소, 최대값은 오렌지의 무게의 범위인 A, B 그램으로 나누면 나올것이다.
그 최소, 최대값이 AN <= 1000W <= BN의 범위에 포함이 되는지 안되는지 확인하고 포함되면 해당 최소, 최대값을 그대로 출력
범위를 벗어난다면 UNSATISFIABLE를 출력하면 정답
코드
#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/abc195/tasks/abc195_b
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
ll a, b, w;
cin >> a >> b >> w;
w *= 1000;
bool flag = true;
ll min = ceill((ld)w / b);
if (w / min < a) flag = false;
ll max = w / a;
if (w / max > b) flag = false;
if (flag)
cout << min << " " << max;
else
cout << "UNSATISFIABLE";
return 0;
}
14 Mar 2021 |
PS
AtCoder Beginner Contest 195 A번 Health M Death
문제
https://atcoder.jp/contests/abc195/tasks/abc195_a
풀이
H가 M의 배수인지 아닌지 확인하면 되는 문제
나머지가 0이면 Yes 아니면 No 출력
코드
#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/abc195/tasks/abc195_a
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
ll m,h;
cin >> m >> h;
bool isAnswer = false;
if(h % m == 0){
isAnswer = true;
}
else isAnswer = false;
if(isAnswer) cout << "Yes";
else cout << "No";
return 0;
}
05 Mar 2021 |
PS
AtCoder Beginner Contest 193 D번 Poker
문제
https://atcoder.jp/contests/abc193/tasks/abc193_d
풀이
1부터 9까지 카드뭉치가 K개가 있다.
타카하시와 아오키가 이 카드뭉치들로 포커를 친다.
양 플레이어는 4장의 카드는 오픈한 상태 한장은 히든이다.
여기서 타카하시의 승률을 계산하는 문제
히든이 양 플레이어 통틀어 2칸이 있으니 1~9까지 가능한 모든 경우를 계산하여 타카하시가 이길때마다 그 확률을 더해서 총 합을 구한다.
코드
#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/abc193/tasks/abc193_d
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
ll k;
cin >> k;
string s, t1;
cin >> s >> t1;
ll num[10] = {};
rep(i, 10) num[i] = k;
rep(i, 4) {
ll a = s[i] - '0';
ll b = t1[i] - '0';
--num[a];
--num[b];
}
vll t(10, 0), a(10, 0);
rep(k, 4) {
t[s[k] - '0']++;
a[t1[k] - '0']++;
}
ld ans = 0;
for (ll i = 1; i <= 9; i++) {
auto ti = t;
ti[i]++;
ll sc_t = 0;
for (ll l = 1; l <= 9; l++) {
sc_t += l * pow(10, ti[l]);
}
for (ll j = 1; j <= 9; j++) {
vll aj = a;
aj[j]++;
if (ti[i] + aj[i] > k) continue;
if (ti[j] + aj[j] > k) continue;
ll sc_a = 0;
for (ll l = 1; l <= 9; l++) {
sc_a += l * pow(10, aj[l]);
}
ld ch1 = num[i];
ld ch2 = num[j];
if (i == j) ch2--;
if (sc_t > sc_a) ans += ch1 / (9 * k - 8) * ch2 / (9 * k - 9);
}
}
cout << fixed;
cout.precision(10);
cout << ans;
return 0;
}
05 Mar 2021 |
PS
AtCoder Beginner Contest 193 C번 Unexpressed
문제
https://atcoder.jp/contests/abc193/tasks/abc193_c
풀이
1부터 N까지의 수 중에 a^b 로 표현할 수 없는 수는 몇개인지 찾는 문제
a^b로 표현할 수 있다는 말은 최소 a^2라고 했을때 a는 root(N)이하이다.
root N이하의 모든 수를 돌면서 모든 거듭제곱꼴을 set에 모아두고 그 사이즈만큼 N에서 뺀다.
map을 사용해도 풀 수는 있지만 수가 커지면 TLE가 발생한다.
코드
#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/abc193/tasks/abc193_c
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
ll n;
cin >> n;
unordered_set<ll> s;
for(ll a = 2; a * a <= n; a++){
ll x = a * a;
while(x <= n){
s.insert(x);
x *= a;
}
}
cout << n - s.size();
return 0;
}
05 Mar 2021 |
PS
AtCoder Beginner Contest 193 B번 Play Snuke
문제
https://atcoder.jp/contests/abc193/tasks/abc193_b
풀이
타카하시는 게임을 사고싶어한다.
N개의 가게가 있다고 할 때 각 가게까지는 타카하시가 있는 곳부터 가게까지 Ai분이 걸리고 가격은 Pi엔이며 Xi개의 물량이 있다.
1분에 1개씩 물량이 없어진다고 할 때 가장 싸게 산다면 얼마인가, 혹시 못산다면 -1를 출력
N개의 가게를 모두 돌면서 걸리는 시간보다 물량이 더 많은 가게의 가격을 비교해서 최저가를 찾으면 정답
그런 가게가 없다면 -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/abc193/tasks/abc193_b
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
ll n;
cin >> n;
vll a(n), p(n), x(n);
ll ans = INT32_MAX;
rep(i,n){
cin >> a[i] >> p[i] >> x[i];
if(x[i] > a[i]){
ans = min(ans, p[i]);
}
}
if(ans == INT32_MAX) ans = -1;
cout << ans;
return 0;
}