Codeforces Round#739 (Div. 3)
22 Aug 2021
저번주 수요일날 참가한 div.3입니다. 처음으로 7문제 중에 4문제 풀었습니다.체감상 이번에 풀은 문제들이 저번 보다 훨씬 쉬웠습니다. A~D까지 풀었고, E,F1 건드려 보다가 끝났습니다. 다음 코포는 div 2 도전..!
A. Dislike of Threes
3으로 나눠지거나 3으로 끝나는 수를 제외한 수들에 대해서 k번째 수를 출력하는 문제였습니다. 처음부터 k번째까지 차례대로 모두 계산하여 풀었습니다.
code
//
// Created by changhyeonnam on 2021/08/18.
//
#include <iostream>
#include <cstring>
#include <string>
#include <algorithm>
#include <vector>
#include <queue>
#include <tuple>
#define endl '\n'
#define INF 1e9
#define LINF 2e15
using namespace std;
using tup = tuple<int,int,int>;
typedef long long ll;
typedef pair<int,int> pi;
typedef pair<ll,ll> pl;
vector<vector<pi>> v;
//priority_queue<pi,vector<pi>,greater<pi>> q;
//priority_queue<tup,vector<tup>,greater<tup>> edge;
int main(){
int t;
cin>>t;
while(t--){
int k;
cin>>k;
int st = 0;
while(k--){
st+=1;
while(st%3==0 || st%10==3){
st+=1;
}
}
cout<<st<<endl;
}
return 0;
}
B. Who’s Opposite?
원탁에 짝수의 사람들이 1번부터 차례대로 2k번까지 앉아 있습니다. a,b,c가 입력으로 주어지는데, a와 b는 마주보는 한 쌍이고, 나머지 c에 대응되는 번호를 출력해야 합니다. 답이 여러개가 있다면 아무거나 출력하고, 없다면 -1을 출력하는 문제였습니다.
마주보는 번호들의 차가 k(여기선 3)일때, 가장 큰수는 2k였습니다. a,b,c에 대해 2k 이하인지 비교하여 예외처리하고, c-(abs(a-b)) 혹은 c+(abs(a-b))를 범위 체크해주고 출력하여 풀었습니다.
code
//
// Created by changhyeonnam on 2021/08/18.
//
#include <iostream>
#include <cstring>
#include <string>
#include <algorithm>
#include <vector>
#include <queue>
#include <tuple>
#define endl '\n'
#define INF 1e9
#define LINF 2e15
using namespace std;
using tup = tuple<int,int,int>;
typedef long long ll;
typedef pair<int,int> pi;
typedef pair<ll,ll> pl;
vector<vector<pi>> v;
//priority_queue<pi,vector<pi>,greater<pi>> q;
//priority_queue<tup,vector<tup>,greater<tup>> edge;
int t;
int main(){
cin>>t;
while(t--){
int a,b,c;
cin>>a>>b>>c;
if(a>b)
{
int tmp = a;
a = b;
b = tmp;
}
int diff = abs(a-b);
if(diff*2<b || diff*2<c){
cout<<-1<<endl;
continue;
}
if(c-diff>0){
cout<<c-diff<<endl;
}
else if(c+diff<=diff*2){
cout<<c+diff<<endl;
}
else
cout<<-1<<endl;
}
return 0;
C. Infinity Table
아래 2차원 행렬에 대해 어떤 숫자 k가 주어졌을때, 위치를 출력하는 문제 였습니다.
1,2,5,10 을보면 1, 1+1, 1+1+3, 1+1+3+5, … 이런식으로 증가합니다. 그리고 1열에서 n번째 수라면 길이 n의 정사각형의 형태를 띱니다. 이것들을 고려하여 문제를 풀었습니다.
code
//
// Created by changhyeonnam on 2021/08/18.
//
#include <iostream>
#include <cstring>
#include <string>
#include <algorithm>
#include <vector>
#include <queue>
#include <tuple>
#define endl '\n'
#define INF 1e9
#define LINF 2e15
using namespace std;
using tup = tuple<int,int,int>;
typedef long long ll;
typedef pair<int,int> pi;
typedef pair<ll,ll> pl;
vector<vector<pi>> v;
//priority_queue<pi,vector<pi>,greater<pi>> q;
//priority_queue<tup,vector<tup>,greater<tup>> edge;
int t;
int main(){
cin>>t;
while(t--){
ll k;
cin>>k;
int nth = 1;
int tmp = 1;
while(tmp<k){
tmp+=2*nth-1;
nth+=1;
}
if(tmp>k){
nth-=1;
tmp-=(2*nth-1);
}
bool flag = false;
for(int i=1;i<=nth;i++){
if(tmp==k){
cout<<i<<" "<<nth<<endl;
flag = true;
break;
}
tmp+=1;
}
if(!flag){
for(int j=nth-1;j>=1;j--){
if(tmp==k){
cout<<nth<<" "<<j<<endl;
break;
}
tmp+=1;
}
}
}
return 0;
}
D. Make a Power of Two
1601번 바이너리 파워비숍 을 아직 못풀었는데, 이 문제에서 $2^n$에 대해 재귀적으로 계산하는 것을 배워서 이 문제에서 사용했습니다.
숫자를 지우거나 오른쪽에 숫자를 추가하여 $2^k$꼴을 만드는 문제였습니다. 투포인터를 활용해서 문제를 풀었습니다. 2의 64승부터 (넉넉하게) 시작하여 2의 0승까지 재귀적으로 호출하고, 주어진 숫자 n과 2의 k승이 몇개의 숫자가 다른지 세보고 그 개수가 가장 작을 때, 개수를 출력했습니다. 투포인터는 주어진 숫자 n과 2의 k승 중에 길이가 더 짧은 숫자를 선택했습니다.
code
//
// Created by changhyeonnam on 2021/08/18.
//
#include <iostream>
#include <cstring>
#include <string>
#include <algorithm>
#include <vector>
#include <queue>
#include <tuple>
#include <cmath>
#define endl '\n'
#define INF 1e9
#define LINF 2e15
using namespace std;
using tup = tuple<int,int,int>;
typedef long long ll;
typedef pair<int,int> pi;
typedef pair<ll,ll> pl;
vector<vector<pi>> v;
//priority_queue<pi,vector<pi>,greater<pi>> q;
//priority_queue<tup,vector<tup>,greater<tup>> edge;
int t;
int solve(string x,int msb){
if(msb<=-1)
return 100;
int count = 0;
ll tmp = pow(2,msb);
string str = to_string(tmp);
int ptr1=0,ptr2 =0;
while(ptr1<x.size()&&ptr2<str.size()){
if(str[ptr2]==x[ptr1]){
ptr2+=1;
ptr1+=1;
count +=1;
continue;
}
else{
ptr1+=1;
continue;
}
}
int rval = 0;
rval+= (x.size()-count);
if(str.size()>count)
rval+= (str.size()-count);
int count_next = solve(x,msb-1);
if(count_next<rval)
rval=count_next;
return rval;
}
int main(){
cin>>t;
while(t--){
string strx;
cin>>strx;
int ans = solve(strx,64);
cout<<ans<<endl;
}
return 0;
}