Codeforces#143

A. Team

■問題
3つの0か1がn個与えられて、1が2つ以上あるものが何個あるか求めよ。

■解法
数えるだけ

■ソース

#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
int main(void)
{
  int n;
  cin >> n;
  int ret = 0;
  for(int i = 0; i < n; i++){
    int c = 0;
    for(int j = 0; j < 3; j++){
      int a;
      cin >> a;
      if(a) c++;
    }
    if(c >= 2) ret++;
  }
  cout << ret << endl;
}

B. Magic, Wizardry and Wonders

■問題
最後の2つの値をそれを減算した値に置き換えてを繰り返し要素が1つになったときその値がdになるようなn個の要素からなる数列を出力せよ

■解法
dp[幾つ目か][必要な差はいくつか]で無理やりdpした。
奇数項 - 偶数項 = dなんて頭いいこと時間内に思いつかなかった。

■ソース

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

int n,d,l;
int use[111];

int dp[111][22222];

int solve(int i,int m){
  if(dp[i][m + 10000] >= 0){
    return dp[i][m + 10000];
  }  

  if(i == n){
    return (m == 0)?1:0;
  }

  for(int j = 1; j <= l; j++){
    if(abs(j - m) >= l * n) continue;
    if(solve(i + 1, j - m)){
      use[i] = j;
      return dp[i][m + 10000] = 1;
    }
  }
  return dp[i][m + 10000] = 0;
}

int main(void)
{
  cin >> n >> d >> l;
  memset(dp,-1,sizeof(dp));
  if(solve(0,d)){
    for(int i = 0; i < n; i++){
      cout << use[i] << ((i == n - 1)?'\n':' ');
    }
  }else{
    cout << -1 << endl;
  }
}