Educational Codeforces Round 96 (Div.2)

A. Number of Apartments

방이 3개, 5개, 7개짜리로 구성된 아파트에서 각각의 방의 개수를 구하는 문제

가장 간단하게, $n$이 1, 2, 4로 구성된 아파트인 경우 방의 개수가 맞지 않으므로 -1을 출력해야 한다.

방 3개를 기준으로 $[3,6,9,..]$, 5개를 1추가하면 $[5,8,11,…]$, 7개를 1추가하면 $[7,10,13,…]$의 수열을 얻을 수 있다.

즉, 위의 수열 중 1, 2, 4를 제외하고 모두 표현할 수 있으므로 다음의 경우를 생각할 수 있다.

• $n$이 3으로 나누어 떨어지는 경우, 방 3개짜리로 구성된 아파트이므로 $(n/3,0,0)$을 출력하면 된다.
• $n$을 3으로 나누어 나머지 1이 남는 경우, 방 7개 하나와 나머지 방 3개짜리 이므로, $((n-7)/3,0,1)$을 출력하면 된다.
• $n$을 3으로 나누어 나머지 2가 남는 경우, 방 5개 하나와 나머지 방 3개짜리 이므로, $((n-5)/3,1,0)$을 출력하면 된다.

#include <iostream>
#include <algorithm>
#define endl '\n'
using namespace std;

typedef long long ll;

void solve() {
  int n;
  cin>>n;
  if(n==1 || n==2 || n==4) {
    cout<<-1<<endl;
    return;
  }
  if(n%3==0) {
    cout<<(n/3)<<' '<<0<<' '<<0<<endl;
  }
  else if(n%3==1) {
    cout<<((n-7)/3)<<' '<<0<<' '<<1<<endl;
  }
  else {
    cout<<((n-5)/3)<<' '<<1<<' '<<0<<endl;
  }
  return;
}

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0); cout.tie(0);
  //freopen("input.txt","r",stdin);
  int t;
  cin>>t;
  while(t--) {
    solve();
  }
  return 0;
}

---

B. Barrels

$n$개의 배럴이 일렬로 나열되어 있고 각 배럴에 물은 $a_i$만큼 들어있다. 두 개의 배럴을 임의로 선택해 한쪽에 전부 부어 물을 합칠 수 있는데, 최대 $k$번의 시도로 배럴의 가장 많은 물의 양과 가장 적은 물의 양의 최대 차를 구하는 문제

두 배럴을 선택해 물을 옮기면 한 쪽은 무조건 0이 된다. 따라서, 가장 많은 물부터 k번째 물까지 합하면 최대 차를 구할 수 있다.

#include <iostream>
#include <vector>
#include <algorithm>
#define endl '\n'
using namespace std;

typedef long long ll;

void solve() {
  int n, k;
  cin>>n>>k;
  vector<ll> a(n);
  for(int i=0;i<n;i++) cin>>a[i];
  sort(a.begin(),a.end());
  reverse(a.begin(),a.end());
  ll sum=0;
  for(int i=0;i<=k;i++) sum+=a[i];
  cout<<sum<<endl;
  return;
}

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0); cout.tie(0);
  //freopen("input.txt","r",stdin);
  int t;
  cin>>t;
  while(t--) {
    solve();
  }
  return 0;
}

---

C. Numbers on Whiteboard

$1, 2, 3, …, n$ 까지 수열이 주어질 때, 두 수 $a, b$를 골라 수열에서 지우고 $\lceil \frac{a+b}{2} \rceil$을 수열에 추가하는 과정을 진행한다.

$n-1$번을 진행한 후에 최종적으로 남는 수의 최소값을 구하고 그 과정까지 출력하는 문제

이 문제는 그리디로 해결할 수 있다.

$n-1$번을 진행하게 되면 마지막 남는 수는 2 이상의 수 이어야 한다. 왜냐하면 마지막 수가 1이 남으려면 $n-1$번째 과정에는 1과 1이 남아야 하는데 불가능하기 때문이다.

그리고, 모든 수열에 대해 오른쪽에서 왼쪽으로 두 개의 수를 순차로 선택해서 2를 만들 수 있다.

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#define endl '\n'
using namespace std;

typedef long long ll;

void solve() {
  int n;
  cin>>n;
  cout<<2<<endl;
  int a=n,b=n-1;
  for(int i=0;i<n-1;i++) {
    cout<<a<<' '<<b<<endl;
    if((a+b)%2==1) a=(a+b)/2+1;
    else a=(a+b)/2;
    b--;
  }
  return;
}

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0); cout.tie(0);
  freopen("input.txt","r",stdin);
  int t;
  cin>>t;
  while(t--) {
    solve();
  }
  return 0;
}

---

D. String Deletion

임의의 숫자를 지우게 될 때 2개 이상의 같은 숫자끼리는 지워지는 문자열에서 비어있게 될 때까지 최대 연산의 횟수를 구하는 문제

중간에 있는 숫자를 지우게 될 때, 다음 두 가지 경우가 생긴다.

• 101에서 0을 지우게 되면서, 11이 붙어 같이 지워지는 경우
• 101에서 맨 앞 1을 지우게 되면서, 01이 되어 조건에 의해 0이 지워지는 경우

최대한 많은 연산을 하기 위해 첫번째 경우를 피해야 한다.

즉, 앞에서부터 2개 이상의 문자열을 먼저 지우고 남은 문자열을 앞에서부터 하나씩 지워가면 된다.

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#define endl '\n'
using namespace std;

typedef long long ll;
typedef pair<int,int> pii;

void solve() {
  int n;
  cin>>n;
  string s;
  cin>>s;
  queue<int> q;
  int cur=0;
  for(int i=0;i<n;i++) { // 연속되는 문자열의 위치를 저장
    if(i>0 && s[i]==s[i-1]) q.push(cur);
    if(i>0 && s[i]!=s[i-1]) cur++;
  }
  int deleted=0; // 지워진 연속된 문자열의 문자 개수
  int score=0; // 횟수
  for(int i=0;i<n;i++) {
    if(q.empty()) break;
    q.pop();
    deleted++;
    score++;
    while(!q.empty() && q.front()==i) { // 연속되는 문자열을 지우는 과정
      q.pop();
      deleted++;
    }
    deleted++;
  }
  score+=(n-deleted+1)/2; // 10의 경우 1을 지우면 그 다음 문자도 지워지므로 남은 문자열을 2로 나눈다
  cout<<score<<endl;
  return;
}

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0); cout.tie(0);
  //freopen("input.txt","r",stdin);
  int t;
  cin>>t;
  while(t--) {
    solve();
  }
  return 0;
}