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;
}
05 Mar 2021 |
PS
AtCoder Beginner Contest 193 A번 Discount
문제
https://atcoder.jp/contests/abc193/tasks/abc193_a
풀이
A가 B가 된다면 몇퍼센트의 할인이 적용된 것인지를 묻는 문제
100(1 - B/A) 를 출력하면 정답
물론 소수점 이하 두자리까지 정확도를 보장해야한다.
코드
#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_a
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
ll a,b;
cin >> a >> b;
ld ans = (ld)100.0 - (ld)b/a*100;
cout << fixed;
cout.precision(20);
cout << ans;
return 0;
}
05 Mar 2021 |
PS
AtCoder Beginner Contest 192 C번 Kaprekar Number
문제
https://atcoder.jp/contests/abc190/tasks/abc192_c
풀이
g1(x)는 x의 각 자리수를 내림차순으로 재배치한 것
g2(x)는 x의 각 자리수를 오름차순으로 재배치한 것
f(x) = g1(x) - g2(x)라고 한다.
a0=N이고 ai+1 = f(ai)일때 ak를 구하는 문제
f(x)를 구하고 이를 k번 반복하면 된다. k <= 10^5이고 n < 10^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/abc192/tasks/abc192_c
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
ll n,k;
cin >> n >> k;
ll a = n;
rep(i,k){
vll g;
while(a){
ll temp = a%10;
g.push_back(temp);
a /= 10;
}
sort(all(g));
ll g1 = 0, g2 = 0;
for(int j = 0;j<g.size();j++){
g1 += g[j] * pow(10,j);
}
reverse(all(g));
for(int j = 0;j<g.size();j++){
g2 += g[j] * pow(10,j);
}
a = g1 - g2;
if(a == 0) break;
}
cout << a;
return 0;
}
05 Mar 2021 |
PS
AtCoder Beginner Contest 192 B번 uNrEaDaBlE sTrInG
문제
https://atcoder.jp/contests/abc190/tasks/abc192_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/abc192/tasks/abc192_b
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
string s;
cin >> s;
bool isOk = true;
rep(i, s.length()) {
if (i % 2) {
if (s[i] < 'A' || s[i] > 'Z') {
isOk = false;
break;
}
} else {
if (s[i] < 'a' || s[i] > 'z') {
isOk = false;
break;
}
}
}
if(isOk) cout << "Yes";
else cout << "No";
return 0;
}