Codeforces Round #386 (Div. 2)

Codeforces Round #386 (Div. 2): http://codeforces.com/contest/746

A. Compote

a,b,c를 고르는데 1:2:4가 되도록 주어진 범위 안에서 고르면 된다.

답은 그렇게 고른 숫자들을 모두 더한 값.

준열이랑 고기 무한리필먹다가 급하게 카페와서 너무 급하게 풀었다.

난 이런 문제를 왜 1분안에 서밋하지 못할까...?ㅠ

#include <cstdio> using namespace std; int main() { int a,b,c,ans=0; scanf("%d%d%d",&a,&b,&c); for(int i=1,j=2,k=4; i<=a && j<=b && k<=c; i++,j=2*i,k=4*i) { ans=i+j+k; } printf("%d", ans); return 0; }

B. Decoding

어떤 문자열이 주어지는데, 그 문자열의 중간 문자를 택해서 새로운 문자를 만드는 것이다.

라고 잘못해석하는 바람에 초반에 엉뚱하게 짰다가 왜 output이 제대로 안나오냐며 짜증을 냈었다. ㅡ,.ㅡ;;

문제에서 주어진 입력이 위에서 말한 새로운 문자고, 출력으로는 원래의 문자열을 뱉는게 진짜 문제였다.

덕분에 안그래도 코딩도 느린놈이 시간도 더걸렸다. ㅠ 

#include <cstdio> #include <cstring> #include <string> #include <iostream> using namespace std; void f(int n, const string &s, string &ans) { if(n==0) return; if(n%2==1) { ans+=s[0]; f(n-1, s.substr(1,n),ans); } else { ans=s[0]+ans; f(n-1, s.substr(1,n),ans); } } int main() { string s,ans; int n; cin >> n >> s; f(n,s,ans); cout << ans; return 0; }

C. Tram

한방에 풀기도 했고, 쉽다고 넘어갔는데... sysfail이 떠버렸다.

그래서 고쳐봤더니.. 등호 하나 넣어줘서 틀렸었다 - _ㅠ;

사실 이런 문제 너무너무 쉬운데... 시스템 채점에서는 꼭 걸릴만한 문제인거 같긴 하다.

이런 케이스들 꼼꼼하게 잘 챙겨야 하는데 ㅠㅠㅠㅠ....

아래 소스코드는 AC받은 소스코드다.

#include <cstdio> #include <algorithm> #include <cstdlib> #include <cmath> using namespace std; int main() { int n,x1,x2,t1,t2,p,d; scanf("%d%d%d%d%d%d%d",&n,&x1,&x2,&t1,&t2,&p,&d); int human=abs(x2-x1)*t2,s=0,ans=0; if(d>0) { if(p<=x1 && x1<x2) s=x2-p; else if(x1<=p && p<=x2) s=2*(n-p)+2*p+(x2-p); else if(x1<x2 && x2<=p) s=2*(n-p)+p+x2; else if(p<=x2 && x2<x1) s=(n-p)+(n-x2); else if(x2<=p && p<=x1) s=2*(n-p)+p-x2; else if(x2<x1 && x1<=p) s=n-p+(n-x2); ans = min(s*t1, human); } else { if(p<=x1 && x1<x2) s=p+x2; else if(x1<=p && p<=x2) s=p+x2; else if(x1<x2 && x2<=p) s=p+x2; else if(p<=x2 && x2<x1) s=p+n+(n-x2); else if(x2<=p && p<x1) s=p+n+(n-x2); else if(x2<x1 && x1<=p) s=p-x2; ans = min(s*t1, human); } printf("%d", ans); return 0; }

D. Green and Black Tea

녹차 홍차문제 ㅋ

n k a b 4개의 숫자가 주어지고 a가 녹차의 수, b가 홍차의 수인데,

각각 k개 초과로 연속해서 마실 수 없다. (k잔까지 연속으로 마실 수 있음)

그래서 이게 가능하다면 가능한 경우 한가지만 문자열로 출력해주면 되는거였다. (G는 녹차, B는 홍차 ㅋㅋ)

나는 그냥 무식하게 k개씩 G와 B를 번갈아가면서 만들고,

남는 차를 그냥 다 쑤셔넣었다.

여기서 다 못 쑤셔넣으면 그냥 NO출력하게 하고,

쑤셔넣으면 그걸 답으로 출력하고... 그랬는데

일단 contest중에는 AC를 받았으나 역시나 system testing에서 WA를 받았다. ㅠㅠ

보니까 약간 실수가 있어서 살짝 바꿨떠니 계속 TLE가 떴는데,

오늘 알게된 놀라운 사실~!

g++14, g++로 채점돌리면 TLE뜨는데 g++11로 하면 1초 안으로 아슬아슬하게 (904ms) 들어와서 통과가 된다.

그리고 BOJ에서는 ios::sync_with_stdio(false); cin.tie(0);쓰고 cin, cout을 쓰면 scanf와 printf보다 눈꼽만큼 빨랐지만,

codeforces에서는 scanf, printf가 무조건 더 빠르다는 사실이 입증되었다. (cin, cout쓰면 sync와 tie를 써줘도 scanf,printf보다 느리더군)

일단 AC를 받았으므로 그 코드를 올려본다.

#include <cstdio> #include <string> #include <cstring> #include <algorithm> using namespace std; int k; string mkstr(char c, int x) { if(x==0) return ""; string ret = mkstr(c,x/2); if(x%2==1) return ret+ret+c; else return ret+ret; } void mkb(int &a, int &b, string &ans); void mka(int &a, int &b, string &ans) { //printf("A: %d %d\n", a,b); if(a>=k) { a-=k; ans+=mkstr('G',k); } else { ans+=mkstr('G',a); a=0; } if(b!=0) mkb(a,b,ans); } void mkb(int &a, int &b, string &ans) { //printf("B: %d %d\n", a,b); if(b>=k) { b-=k; ans+=mkstr('B',k); } else { ans+=mkstr('B',b); b=0; } if(a!=0) mka(a,b,ans); } int main() { int n,a1,b1,a2,b2; scanf("%d%d%d%d",&n,&k,&a1,&b1); a2=a1; b2=b1; string ans1, ans2; mka(a1,b1,ans1); mkb(a2,b2,ans2); if(a1==0 && b1==0) return 0&printf("%s", ans1.c_str()); else if(a2==0 && b2==0) return 0&printf("%s", ans2.c_str()); else { string ta,tb; ta=mkstr('G',k); tb=mkstr('B',k); if(a1) { for(int i=0; i<ans1.size(); i++) { if(ans1[i]=='B'&&(ans1[i+1]=='B'||ans1[i+1]==0)) { if(k<=a1) { ans1=ans1.substr(0,i+1)+ta+ans1.substr(i+1,ans1.size()); i+=k; a1-=k; } else { ans1=ans1.substr(0,i+1)+mkstr('G',a1)+ans1.substr(i+1,ans1.size()); i+=a1; a1=0; } } } if(a1==0) return 0&printf("%s", ans1.c_str()); } else if(b1) { for(int i=0; i<ans1.size(); i++) { if(ans1[i]=='G'&&(ans1[i+1]=='G'||ans1[i+1]==0)) { if(k<=b1) { ans1=ans1.substr(0,i+1)+tb+ans1.substr(i+1,ans1.size()); i+=k; b1-=k; } else { ans1=ans1.substr(0,i+1)+mkstr('B',b1)+ans1.substr(i+1,ans1.size()); i+=b1; b1=0; } } } if(b1==0) return 0&printf("%s", ans1.c_str()); } if(a2) { for(int i=0; i<ans2.size(); i++) { if(ans2[i]=='B'&&(ans2[i+1]=='B'||ans2[i+1]==0)) { if(k<=a2) { ans2=ans2.substr(0,i+1)+ta+ans2.substr(i+1,ans2.size()); i+=k; a2-=k; } else { ans2=ans2.substr(0,i+1)+mkstr('G',a2)+ans2.substr(i+1,ans2.size()); i+=a2; a2=0; } } } if(a2==0) return 0&printf("%s", ans2.c_str()); } else if(b2) { for(int i=0; i<ans2.size(); i++) { if(ans2[i]=='G'&&(ans2[i+1]=='G'||ans2[i+1]==0)) { if(k<=b2) { ans2=ans2.substr(0,i+1)+tb+ans2.substr(i+1,ans2.size()); i+=k; b2-=k; } else { ans2=ans2.substr(0,i+1)+mkstr('B',b2)+ans2.substr(i+1,ans2.size()); i+=b2; b2=0; } } } if(b2==0) return 0&printf("%s", ans2.c_str()); } puts("NO"); } return 0; }

쓰고나서 보니 코드가 막장인거 같다. ㅠㅠ

E. Numbers Exchange

아놔 이 문제도 다 풀었는데...

근데 콘테이후로도 아직 AC를 받지 못했다.

너무 억울한 마음에 WA난 소스코드를 올려본다.

#include <cstdio> #include <set> #include <algorithm> #include <vector> using namespace std; int v[200001], ans[200001]; set<int> odd,even; vector<int> anspos, nopos; int main() { int n, m; scanf("%d%d",&n,&m); for(int i=0; i<n; i++) { scanf("%d", &v[i]); if(v[i]%2) odd.insert(v[i]); else even.insert(v[i]); } int half=n>>1, lim = min(400000,m), cnt=0; for(int i=2; i<=lim; i+=2) { if(even.size()==half) break; if(even.count(i) == 0) { even.insert(i); cnt++; } } for(int i=1; i<=lim; i+=2) { if(odd.size()==half) break; if(odd.count(i) == 0) { odd.insert(i); cnt++; } } if(even.size()==half && odd.size()==half) { printf("%d\n", cnt); for(int i=0; i<n; i++) { if(v[i]%2==0) { if(even.count(v[i])) { even.erase(v[i]); ans[i]=v[i]; } else nopos.push_back(i); } else { if(odd.count(v[i])) { odd.erase(v[i]); ans[i]=v[i]; } else nopos.push_back(i); } } int idx=0; for(int p: odd) ans[nopos[idx++]]=p; for(int p: even) ans[nopos[idx++]]=p; for(int i=0; i<n; i++) printf("%d ", ans[i]); } else puts("-1"); return 0; }

F. Music in Car

이 문제는 보지도 못했다. 언젠가는 풀어보겠지...

G. New Roads

와 미쳤다. 오늘은 7문제나 나왔다. (시간은 30분 더주긴 했는데...)

역시나 이 문제는 아직 못봤다. 나중에 풀어봐야지 ㅋㅋ

# 최종 스코어 #

아니 근데, 나 E번 서밋하고 WA받았는데 왜 아무 표시가 안되어있는거야??

위에 스샷을 보시라~ ㅠ 분명 콘테때 E번 제출했는데... ㅠ

(저거 1번 테케부터 틀려서 그런가? ㅋㅋㅋ)

근데 저거 1번부터 틀린이유는... 문제를 잘못읽어서 ㅋㅋㅋ

나중에 제대로 읽고 푸니까 9번 테스트에서 WA

내일 다시 풀어봐야겠다. ㅋ

으앜 조교일 채점 빨리해야하는데...

저지 만들어본다고 아직까지 안했다.

후딱 하고 자야지~