POJ 2390 Bank Interest

解説
Hint見たらそのまま実装すればいい。

#include <iostream>
using namespace std;

int main(){
  int c;
  double n,m;
  cin >> n >> m >> c;
  while(c--) m *= 1+(n/100);
  cout << (int)m << endl;
}

POJ 2388 Who's in the Middle

解説
真ん中にいる人を求めるだけ。

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

int main(){
  int n,a;
  vector<int> v;
  cin >> n;
  for(int i = 0; i < n; i++){
    cin >> a;
    v.push_back(a);
  }
  sort(v.begin(),v.end());
  cout << v[n/2] << endl;
}

POJ 1067 取石子游戏

解説
ゲームにっき(仮) |PKU 1067 - 取石子游戏ここを見て解きました...。もう答えのようなものなので無念。

#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;

int main(){
  int a,b;
  double r = (1+sqrt(5.0))/2;
  while(cin>>a>>b){
    if(a>b) swap(a,b);
    if(floor((b-a)*r)==a) puts("0");
    else puts("1");
  }
}

POJ 3617 Best Cow Line

解説
蟻本に書いてある。が、80文字で改行とfrontとbackが同じことも考えるということを忘れていて5回ぐらいWAなりPEなり出された。

#include <iostream>
#include <cstdio>
#include <vector>

using namespace std;

int main(){
  int n,c=0;
  char a;
  vector<char> cv;
  cin >> n;
  for(int i = 0; i < n; i++){
    cin >> a;
    cv.push_back(a);
  }
  
  int l = 0, r = n-1;
  bool left;
  while(l <= r){
    c++;
    left = false;
    for(int i = 0; l + i <= r; i++){
      if(cv[l + i] < cv[r - i]){
	left = true;
	break;
      }else if(cv[l + i] > cv[r - i]){
	left = false;
	break;
      }
    }
    if(left) putchar(cv[l++]);
    else putchar(cv[r--]);
    if(c==80){
      putchar('\n');
      c = 0;
    }
  }
  putchar('\n');
}

個人的にはこのコードでどうにか通したかった...

#include <iostream>
#include <deque>
#include <string>

using namespace std;

int main(){
  int n;
  char a;
  deque<char> deq;
  string ans = "";
  cin >> n;
  for(int i = 0; i < n; i++){
    cin >> a;
    deq.push_back(a);
  }
  for(int i = 0; i < n; i++){
    if(deq.front() < deq.back()){
      ans += deq.front();
      deq.pop_front();
    }else{
      ans += deq.back();
      deq.pop_back();
    }
  }  
  cout << ans << endl;
}

deque大好き（けど解けなかった悔しい

POJ 2386 Lake Counting

解説
特になし。蟻本に書いてある。

#include <iostream>

using namespace std;

int n,m,c;
char map[102][102];

void dfs(int x, int y){
  map[x][y] = '.';
  
  for(int i = -1; i <= 1; i++){
    for(int j = -1; j <= 1; j++){
      int nx = x + i, ny = y + j;
      if(0 <= nx && nx < n && 0 <= ny && ny < m && map[nx][ny] == 'W')
	dfs(nx,ny);
    }
  }
}

int main(){
  cin >> n >> m;
  for(int i = 0; i < n; i++) cin >> map[i];
  
  for(int i = 0; i < n; i++){
    for(int j = 0; j < m; j++){
      if(map[i][j]=='W'){
	dfs(i,j);
	c++;
      }
    }
  }
  cout << c << endl;
}

POJ 2456 Aggressive cows

解説
蟻本に書いてある。

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

const int INF = 1 << 29;

int n,m,a;
vector<int> x;

bool C(int d){
  int last = 0;
  for(int i = 1; i < m; i++){
    int crt = last + 1;
    while(crt < n && x[crt] - x[last] < d) crt++;
    if(crt == n) return false;
    last = crt;
  }
  return true;
}

int main(){
  cin >> n >> m;
  for(int i = 0; i < n; i++){
    cin >> a;
    x.push_back(a);
  }
  sort(x.begin(),x.end());
  
  int l = 0, r = INF;
  
  while( r - l > 1 ){
    int mid = (r + l) / 2;
    if(C(mid)) l = mid;
    else r = mid;
  }
  
  cout << l << endl;
}

POJ 1064 Cable master

解説
蟻本に解法が載ってある。
二部探索まだまだ身についてない。

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

const int INF = 1 << 29;

int n,k;
double l[10001];

bool C(double x){
  int num = 0;
  for(int i = 0; i < n; i++) num += (int)(l[i] / x);
  return num >= k;
}

int main(){
  cin >> n >> k;
  for(int i = 0; i < n; i++) cin >> l[i];
  
  double l = 0, r = INF;
  
  for(int i = 0; i < 100; i++){
    double mid = (l + r) / 2;
    if(C(mid)) l = mid;
    else r = mid;
  }
  cout << fixed;
  cout.precision(2);
  cout << floor(r * 100) / 100 << endl;
}