내가 한 엣코더 라운드 중에 가장 잘한 라운드다!
3솔했고, B에서 많이 뇌절했다.
B는 문제가 좀 별로인것 같다.
그리고 C번은 왤논이었는데 내가 그걸 모르고(...) 엄청 어렵게 풀었다.
풀이로 들어가자!
A. Slot
Problem Statement
You are playing the slots.
The result of a spin is represented by three uppercase English letters C1, C2, and C3. It is considered a win when all of them are the same letter.
Determine whether it is a win.
Constraints
Ci is an uppercase English letter.
Input
Input is given from Standard Input in the following format:
C1C2C3
Output
If the result is a win, print Won; otherwise, print Lost.
풀이
주어진 세개의 문자가 같은지를 판별하자.
#include<bits/stdc++.h>
int main(){
char a,b,c;
scanf("%c %c %c",&a,&b,&c);
if(a==b&&a==c&&b==c) puts("Won");
else puts("Lost");
return 0;
}
[01:21 Accepted]
B. Alchoholic
Problem Statement
Takahashi had N glasses of liquor.
The amount and alcohol percentage of the i-th liquor were Vi milliliters and Pi percent by volume, respectively.
Takahashi gets drunk when his alcohol intake exceeds X milliliters.
Which of the N liquors was he drinking when he gets drunk? If he was not drunk even after drinking all the liquors, print -1 instead.
Constraints
- All values in input are integers.
- 1≤N≤10^3
- 0≤X≤10^6
- 1≤Vi≤10^3
- 0≤Pi≤100
Input
Input is given from Standard Input in the following format:
N X
V1 P1
⋮
VN PN
Output
If Takahashi got drunk when drinking the i-th liquor, print i. If he was not drunk even after drinking all the liquors, print -1 instead.
풀이
각 주어지는 음료별로 알코올의 양을 구해서 더하면 된다.
그대로 코드를 짜고 제출하면 틀린다.
왜그럴까? 바로 실수 오차 때문이다.
실수 오차를 없엘려면 실수를 없에 버리면 된다.
따라서 알코올의 양을 100으로 나누지 않고, 즉 알코올의 양*100을 구하고 그 값을 마실수 있는 최대 알코올의 양*100과 비교해주면 된다.
실수오차 참 짜증난다:(
#include<bits/stdc++.h>
using namespace std;
int main(){
int n, x;cin >> n >> x;
int v[1000], p[1000];
for (int i = 0; i < n; ++i) cin >> v[i] >> p[i];
long long t[1000];
for (int i = 0; i < n; ++i) t[i] = v[i] * p[i];
long long ans = 0;
for (int i = 0; i < n; ++i){
ans += t[i];
if (ans > x * 100){
cout << i+1 << endl;
break;
}
}
if (ans <= x * 100) cout << -1;
}
[13:00 Wrong answer]
[15:07 Wrong answer]
[18:23 Wrong answer]
[25:29 Wrong answer]
[27:52 Wrong answer]
[30:25 Accepted]
C. Mandarine Orange
Problem Statement
There are N dishes arranged in a row in front of Takahashi. The i-th dish from the left has Ai oranges on it.
Takahashi will choose a triple of integers (l,r,x) satisfying all of the following conditions:
- 1≤l≤r≤N
- 1≤x
- for every integer I between l and r (inclusive), x≤Ai.
He will then pick up and eat x oranges from each of the l-th through r-th dishes from the left.
At most how many oranges can he eat by choosing the triple (l,r,x) to maximize this number?
Constraints
- All values in input are integers.
- 1≤N≤10^4
- 1≤Ai≤10^5
Input
Input is given from Standard Input in the following format:
N
A1 … AN
Output
Print the maximum number of oranges Takahashi can eat.
풀이
이 문제는 왜인지 모르겠지만 왤논이라고 한다,,
나는 대회 중에 진짜 이상한 방법으로 풀어서 11분만에 템플릿 미포함 1442B를 짜는 미친짓을 했다.
여러분은 이런 풀이를 하지 않았으면 한다.. ㅠㅠㅠ
내 풀이를 설명하면 머리만 아프니까 에디토리얼에 있는 간단한 풀이를 설명하도록 하겠다.
One can first fix l, then update x while increasing r one by one to find them in a total of O(N^2) time.
아 너무 쉽다
#include<bits/stdc++.h>
using namespace std;
int a[10010];
int main(){
int n;
cin >> n;
for(int i=0;i<n;i++)cin >> a[i];
int ans=0;
for(int l=0;l<n;l++){
int x=a[l];
for(int r=l;r<n;r++){
x=min(x,a[r]);
ans=max(ans,x*(r-l+1));
}
}
cout << ans;
}
<내 코드>
#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
vector<ll> f(vector<ll> &v){
ll i,j,k,l,n=v.size();
vector<ll> res(n);stack<ll> st;
for(i=0;i<n;i++){
while(!st.empty()&v[i]<=v[st.top()]) st.pop();
if(st.empty()) res[i]=-1;
else res[i] = st.top();
st.push(i);
}
return res;
}
vector<ll> g(vector<ll> &v){
ll i,j,k,l,n=v.size();vector<ll> res(n);stack<ll> st;
for(i=n-1;i>=0;i--){
while(!st.empty()&v[i]<=v[st.top()]) st.pop();
if(st.empty()) res[i]=n;
else res[i] = st.top();
st.push(i);
}
return res;
}
void solve(){
ll i,j,k,n,m,a,b,u;cin>>n;vector<ll> v(n);
for(i=0;i<n;i++) cin>>v[i];
vector<ll> l = f(v);vector<ll> r = g(v); ll ans=0;
for(i=0;i<n;i++) ans = max(ans, v[i]*(r[i]-l[i]-1));
cout<<ans;
}
int main(){
ll t;t=1;
while(t--) solve();
}
제 코드가 얼마나 더러운지 알겠나요
[41:55 Accepted]
D 굉장히 어려워 보여서 안풀었다 ㅋㅋㅋㅋ
업솔빙도 안할예정