結果

問題 No.10 ＋か×か
ユーザー alpha_virginis
提出日時 2016-11-14 00:10:56
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 1,457 bytes
コンパイル時間 1,588 ms
コンパイル使用メモリ 167,464 KB
実行使用メモリ 8,576 KB
最終ジャッジ日時 2024-11-25 22:07:41
合計ジャッジ時間 10,433 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 11 TLE * 1
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>

int n;
int total;
int xs[64];
long lower[64];
long upper[64];
std::string ans;

void dfs(std::string& str, int i, long x) {
  // fprintf(stderr, "(str, i, x) = (%s, %d, %ld)\n", str.c_str(), i, x);
  if( i == 0 ) {
    if( x == xs[0] ) {
      // fprintf(stderr, "hit\n");
      ans = std::max(ans, str);
    }
    return;
  }
  if( not ( lower[i] <= x ) ) return;
  if( not ( x <= upper[i] ) ) return;
  do {
    str[i-1] = '+';
    dfs(str, i - 1, x - xs[i]);
    str[i-1] = ' ';
  } while(false);
  do {
    if( x % xs[i] != 0 ) break;
    str[i-1] = '*';
    dfs(str, i - 1, x / xs[i]);
    str[i-1] = ' ';   
  } while(false);
}

int main() {
  scanf("%d", &n);
  scanf("%d", &total);
  for(int i = 0; i < n; ++i) {
    scanf("%d", &xs[i]);
  }

  // step 1
  lower[0] = upper[0] = xs[0];
  for(int i = 1; i < n; ++i) {
    if( xs[i] == 1 or lower[i-1] == 1 ) {
      lower[i] = lower[i-1] * xs[i];
    }
    else {
      lower[i] = lower[i-1] + xs[i];
    }
    if( xs[i] == 1 or upper[i-1] == 1 ) {
      upper[i] = upper[i-1] + xs[i];
    }
    else {
      upper[i] = upper[i-1] * xs[i];
    }
    upper[i] = std::min(upper[i], (long)1000000);
    // fprintf(stderr, "%d : (lower, upper) = (%ld, %ld)\n", i, lower[i], upper[i]);
  }

  // step 2
  std::string str;
  for(int i = 0; i < n - 1; ++i) {
    str += ' ';
  }
  ans = str;
  dfs(str, n - 1, total);
  
  // step 3
  printf("%s\n", ans.c_str());
  
  return 0;
}
0