Educational Codeforces Round #96 (Div.2)

A. Number of Apartments

3つの部屋、5つの部屋、7つの部屋からなるアパートで、部屋ごとの個数を求める問題.
最も簡単なのは、nnnが1、2、4からなるアパートであれば、部屋の数が合わないため、-1を印刷する必要があるということです.
3部屋基準[3,6,9...][3,6,9,..][3,6,9,..], 1を5個追加すると[58,11...][5,8,11,...][5,8,11,...], 7個追加すると[7,10,13,...][7,10,13,...][7,10,13,...]得られる数列.
すなわち、上記の数列のうちの1、2、4以外の数列を表すことができるので、以下のことが考えられる.

nnを3で割ると、3部屋からなるマンション(n/3,0,0)(n/3,0,0)(n/3,0,0)が出力されます.

nnを3で割って、1つ残っていれば、7部屋と3部屋残っていれば、(n∧7)/3,0,1)(n-7)/3,0,1)(n∧7)/3,0,1)出力すればよい.

nnを3で割って残りの2が5部屋と3部屋の場合(nυ5)/3,1,0)(n-5)/3,1,0)((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

nnn個のバケツが一列に並んでいて、各バケツの水はaia iaiほどあります.2つのバケツを任意に選択し、水をすべて片側に注ぎ、最大kkk回の試みでバケツの最大水量と最小水量の最大差の問題を求めることができます.
2バレルを選んで水を移すと、1バレルは必ずゼロになります.したがって,最も多い水から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,...,n1, 2, 3, ..., n1,2,3,...,数列をnにすると、2つの数a、ba、ba、bを選択して数列から削除し、a+b 2lceilfrac{a+b}{2\rceil892 a+b΃を数列に追加します.
nⓐ-1 n-ⓐを1回行った後,最終残数の最小値を求め,プロセスの問題に出力する
この問題はグリディで解決できる.
n8218;−1 n8218;は1回行い,最後に残る数は2以上でなければならない.最後の数が1の場合、n–1 n–1、最初のプロセスは1と1でなければなりませんが、これは不可能です.
次に、各数列について、右から左の順に2つの数を選択して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つ以上の同じ数値の間の最大演算回数の問題.
中央の数値を削除すると、次の2つの状況が発生します.

1101から0を削除する、11が貼り付けられて一緒に削除すると

になる.
一番前の1を

1101から削除すると01、条件が0の場合は

となる.
できるだけ多くの演算を行うためには,第1のケースを避けなければならない.
すなわち,2つ以上の文字列を前から削除し,残りの文字列を前から1つずつ削除する.

#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;
}