Codeforces Round 690 (Div.3)

A. Favorite Sequence

---

일반적으로, 가장 왼쪽 요소는 모든 홀수 위치에 배치하고 가장 오른쪽 요소는 모든 짝수 위치에 배치한 후 왼쪽 포인터는 앞으로, 오른쪽 포인터는 하나씩 뒤로 이동

#include <iostream>
using namespace std;

void solve() {
  int n;
  cin>>n;
  int arr[300];
  for(int i=0;i<n;i++) cin>>arr[i];

  int ans[300];
  int left=0, right=n-1;
  for(int i=0;i<n;i++) {
    if(i%2==0) ans[i]=arr[left++];
    else ans[i]=arr[right--];
  }
  
  for(int i=0;i<n;i++) cout<<i<<' ';
  cout<<endl;
}

int main() {
  int t;
  cin>>t;
  while(t-- > 0) {
    solve();
  }
  return 0;
}

---

B. Last Year’s Substring

입력된 문자열 $s$에서 부분 문자열 $t$를 지워 “2020”을 만들어지는지 확인하는 문제이다.

문자열 $t$의 길이는 반드시 $n-4$이어야 한다. (“2020”의 길이는 4이기 때문)

그렇다면 문자열 $s$에서 부분 문자열 $t$를 지웠을 때 얻을 수 있는 문자열은 다음과 같다.

• $s[1], s[2],s[3],s[4]$
• $s[1],s[2],s[3],s[n]$
• $s[1],s[2],s[n-1],s[n]$
• $s[1], s[n-2],s[n-1],s[n]$
• $s[n-3],s[n-2],s[n-1],s[n]$ ```cpp #include using namespace std;

void solve() { int n; cin»n; string s; cin»s;

for(int i=0;i<=4;i++) { if(s.substr(0,i) + s.substr(n-4+i, 4-i) == “2020”) { cout«“YES”«endl; return; } } cout«“NO”«endl; return; }

int main() { int t; cin»t; while(t– >0) { solve(); } return 0; }

---

## C. Unique Number

중복되지 않은 각 자리의 숫자의 합이 입력된 $x$를 만들 수 있으면서 가장 작은 수를 출력하는 문제

먼저, 문제에 대한 답은 0이 포함되서는 안된다. 단지 숫자를 늘리기만 하기 때문이다.

그리고 가능한 최소길이를 가져야 하고 길이가 같은 경우 가장 작은 수가 정답이기 때문에 첫 번째 숫자로 먼저 비교한 후 두 번째 숫자를 추가하여 비교해야 한다. 이때 비교하게 될 숫자는 정렬된 순서로 해야 한다.
```cpp
#include <iostream>
#include <vector>
#define endl '\n'
using namespace std;

void solve() {
  int x;
  cin>>x;
  vector<int> ans;
  int sum=0, last=9;
  while(sum < x && last > 0) { // 큰 수부터 넣어서 가능한 수 찾기
    ans.push_back(min(x-sum, last));
    sum+=last;
    last--;
  }

  if(sum<x) {
    cout<<-1<<endl;
  }
  else {
    reverse(ans.begin(),ans,end());
    for(int i=0;i<ans.size();i++)
      cout<<ans[i];
      cout<<endl;
  }
  return;
}

int main() {
  int t;
  cin>>t;
  while(t-- >0) {
    solve();
  }
  return 0;
}

---

D. Add to Neighbour and Remove

먼저, $k$를 실행한 횟수라 하자. 그리고 $s$를 배열 $a$안 숫자들의 합이라 하자.

$k$번의 실행을 한 후 모든 요소들은 같은 값을 가진 배열이 되어야 한다.

그런데, 모두 같은 값이 가능한 숫자는 $\frac{s}{n-k}$이다.

예를 들어 $a$배열 [1, 2, 2, 1]이 있을 때, $s$는 6이다.

따라서 $f(k)=\frac{s}{n-k}$라 할 때, $f(1)=2,f(2)=3,f(3)=6$이 가능한 숫자이다.

이제 $a$배열을 가지고 확인해보자.

먼저, $k=1$일 때이다.

• $a_1+a_2>2$이므로 불가능

다음 $k=2$일 때이다.

• $a_1+a_2=3, a_3+a4=3$이므로 가능하다.

따라서 답은 $n-k$인 2이다.

#include <iostream>
#include <vector>
using namespace std;

typedef long long ll;

void solve() {
  int n;
  cin>>n;
  vector<ll> a(n);
  ll sum=0;
  for(int i=0;i<n;i++) {
    ll x;
    cin>>x;
    a[i]=x;
    sum+=x;
  }

  for(int i=n;i>=1;i--) {
    if(sum%i==0) {
      ll needSum=sum/i // s/(n-k)
      ll curSum=0;
      book ok=true;
      for(int j=0;j<n;j++) { // a1부터 필요한 합이 가능한가
        curSum+=a[j];
        if(curSum>needSum) { // 합이 넘어가면 불가능
          ok=false;
          break;
        }
        else if(curSum==needSum) { // 같으면 다음 인덱스부터 확인
          curSum=0;
        }
      }

      if(ok) {
        cout<<n-i<<endl;
        return;
      }
    }
  }
  return;
}

int main() {
  int t;
  cin>>t;
  while(t-- >0) {
    solve();
  }
  return 0;
}