第7回JOI予選

0521(aoj) : おつり
0522(aoj) : JOIとIOI
0523(aoj) : カードゲーム
0524(aoj) : 星座探し
0525(aoj) : おせんべい
0526(aoj) : 船旅

0521

やるだけ、見るも無残なくそこーど。

#include <iostream>
int main()
{
  int n;
  while(std::cin>>n,n){
    n = 1000-n;
    int ans = 0;
    while(n>=500){
      n-=500; ans++;
    }
    while(n>=100){
      n-=100; ans++;
    }
    while(n>=50){
      n-=50; ans++;
    }
    while(n>=10){
      n-=10; ans++;
    }
    while(n>=5){
      n-=5; ans++;
    }
    ans += n;
    printf("%d\n",ans);
  }
  return 0;
}

0522

やるだけ

#include <iostream>
#include <string>
using namespace std;
int main()
{
  string str;
  while(cin>>str){
    int pos = 0;
    int joi,ioi;
    joi = ioi = 0;
    while( (pos=str.find("JOI",pos)+1) )joi++;
    pos = 0;
    while( (pos=str.find("IOI",pos)+1) )ioi++;
    
    printf("%d\n%d\n",joi,ioi);
  }
  return 0;
}

0523

やるだけ

#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;
int main()
{
  int n;
  
  while(cin>>n,n){
    vector<int> taro,hana;
    int num[201];
    memset(num,0,sizeof(num));
    
    for(int i=0; i<n; i++){
      int a; cin>>a;
      num[a]=1;
    }
    
    for(int i=1; i<=2*n; i++){
      if( num[i] )taro.push_back(i);
      else       hana.push_back(i);
    }
    
    int turn=1;
    int ba = 0;
    for(; taro.size() && hana.size();){
      if( turn ){
        vector<int>::iterator it = lower_bound(taro.begin(),taro.end(),ba);
        if( it==taro.end() )ba=0;
        else{
          ba = *it;
          taro.erase( it );
        }
        
      }else{
        vector<int>::iterator it = lower_bound(hana.begin(),hana.end(),ba);
        if( it==hana.end() )ba=0;
        else{
          ba = *it;
          hana.erase( it );
        }
      }
      turn ^= 1;
    }

    printf("%d\n%d\n",hana.size(),taro.size());
  }
  return 0;
}

0524

普通に探索するだけ

#include <iostream>
int main()
{
  int n,m;
  int seiza[200][2];
  int point[1000][2];
  while(std::cin>>n,n){
    for(int i=0; i<n; i++)
      std::cin>>seiza[i][0]>>seiza[i][1];
    std::cin>>m;
    for(int i=0; i<m; i++)
      std::cin>>point[i][0]>>point[i][1];
      
    for(int i=0; i<m; i++){
      int j;
      int dx = point[i][0] - seiza[0][0];
      int dy = point[i][1] - seiza[0][1];
      for(j=1; j<n; j++){
        int x = seiza[j][0] + dx;
        int y = seiza[j][1] + dy;
        int k;
        for(k=0; k<m; k++)
          if( point[k][0]==x && point[k][1]==y )break;
        if( k==m )break;
      }
      if( j==n ){
        printf("%d %d\n",dx,dy);
        break;
      }
    }
  }
  return 0;
}

0525

縦が最大10行なので、ビットで処理した。
このコードだと最大計算量は1024*10000*10なので最大ケースを試すと手元の環境では7secになる。
でも、AOJにsubmitすると0.5sec以内に終わった。AOJのデータセットはやさしいのかも。

#include <iostream>
#include <cstring>
using namespace std;
int main()
{
  int R,C;
  int field[10000];
  
  while(cin>>R>>C,R|C){
    memset(field,0,sizeof(field));
    for(int i=0; i<R; i++){
      for(int j=0; j<C; j++){
        int a; cin>>a;
        field[j] = (field[j]<<1) | a;
      }
    }
    
    int ans = 0;
    
    for(int k=1; k<(1<<R); k++){
      int sum = 0;
      for(int i=0; i<C; i++){
        int t1 = field[i];
        int t2 = ~field[i];
        int sum1 = 0;
        int sum2 = 0;
        for(int j=1; j<(1<<R); j<<=1){
          if( k&j ){
            sum1 += ( ((~t1)&j)==j ? 1 : 0 );
            sum2 += ( ((~t2)&j)==j ? 1 : 0 );
          }else{
            sum1 += ( (t1&j)==j ? 1 : 0 );
            sum2 += ( (t2&j)==j ? 1 : 0 );
          }
        }
        sum += max(sum1,sum2);
      }
      ans = max(ans,sum);
    }
    
    printf("%d\n",ans);
  }
  return 0;
}

0526

ダイクストラった。
優先度付きキューを使ってみた。

#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>
#include <queue>
#include <functional>
using namespace std;
int main()
{
  int n,k;
  int node[101][101];
  while(cin>>n>>k,n|k){
  
    for(int i=0; i<=n; i++)
      for(int j=0; j<=n; j++)
        node[i][j] = INT_MAX;
    
    while(k--){
      int m;
      cin>>m;
      if( m ){
        int c,d,e;
        cin>>c>>d>>e;
        node[c][d] = node[d][c] = min(node[d][c],e);
      }else{
        int a,b;
        cin>>a>>b;
        int memo[101];
        priority_queue< pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > > pq;
        for(int i=0; i<=n; i++)memo[i]=INT_MAX;
        pq.push(make_pair(0,a));
        memo[a]=0;
        while( !pq.empty() ){
          pair<int,int> pi = pq.top();
          if( pi.second == b )break;
          pq.pop();
          for(int i=1; i<=n; i++){
            if( node[pi.second][i]!=INT_MAX &&
               node[pi.second][i]+pi.first < memo[i] ){
              memo[i] = node[pi.second][i] + pi.first;
              pq.push(make_pair(memo[i],i));
            }
          }
        }
        printf("%d\n",memo[b]==INT_MAX?-1:memo[b]);
      }
    }
  }
  return 0;
}