結果

問題 No.10 ＋か×か
コンテスト
ユーザー 久我山菜々
提出日時 2018-09-30 21:39:34
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 1,854 bytes
コンパイル時間 800 ms
コンパイル使用メモリ 98,912 KB
最終ジャッジ日時 2025-01-06 14:13:19
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 5 WA * 5 TLE * 2
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp:11:11: warning: use of ‘auto’ in parameter declaration only available with ‘-std=c++20’ or ‘-fconcepts’
   11 | int count(auto const& map, auto const& as, int depth) {
      |           ^~~~
main.cpp:11:28: warning: use of ‘auto’ in parameter declaration only available with ‘-std=c++20’ or ‘-fconcepts’
   11 | int count(auto const& map, auto const& as, int depth) {
      |                            ^~~~
main.cpp:23:12: warning: use of ‘auto’ in parameter declaration only available with ‘-std=c++20’ or ‘-fconcepts’
   23 | void solve(auto& map, auto const& as, int max_depth, int depth, int total, int current) {
      |            ^~~~
main.cpp:23:23: warning: use of ‘auto’ in parameter declaration only available with ‘-std=c++20’ or ‘-fconcepts’
   23 | void solve(auto& map, auto const& as, int max_depth, int depth, int total, int current) {
      |                       ^~~~

ソースコード

diff # 

#include<iostream>
#include<vector>
#include<map>
#include<algorithm>
#include<cmath>
#include<queue>
#include<numeric>

static int const INF{100000000};

int count(auto const& map, auto const& as, int depth) {
  int ans{as[0]};
  for(int i{}; i < depth; ++i) {
    if(map[i] == 1) {
      ans += as[i + 1];
    } else {
      ans *= as[i + 1];
    }
  }
  return ans;
}

void solve(auto& map, auto const& as, int max_depth, int depth, int total, int current) {
  if(depth == max_depth) {
    if(total == current) return;
    for(int i{max_depth - 1}; i >= 0; --i) {
      if(map[i] == 1) {
        solve(map, as, max_depth, i, total, count(map, as, i));
        return;
      }
      map[i] = 0;
    }
    throw "never come";
  }
  if(map[depth] == 0) {
    map[depth] = 1;
    if(total >= current + as[depth + 1]) {
      solve(map, as, max_depth, depth + 1, total, current + as[depth + 1]);
    } else {
      solve(map, as, max_depth, depth, total, current);
    }
  } else if(map[depth] == 1) {
    map[depth] = 2;
    if(total >= current * as[depth + 1]) {
      solve(map, as, max_depth, depth + 1, total, current * as[depth + 1]);
    } else {
      solve(map, as, max_depth, depth, total, current);
    }
  } else {
    map[depth] = 0;
    if(map[depth - 1] == 1) {
      solve(map, as, max_depth, depth - 1, total, current - as[depth]);
    } else if(map[depth - 2] == 2)  {
      solve(map, as, max_depth, depth - 1, total, current / as[depth]);
    }
  }
}

int main(int, char**) {
  int n;
  std::cin >> n;
  int total;
  std::cin >> total;
  std::vector<int> as(n);
  for(int i{}; i < n; ++i) {
    std::cin >> as[i];
  }

  std::vector<int> map(n - 1, 0);
  // 0: unknown, 1: plus, 2: mul

  solve(map, as, n - 1, 0, total, as[0]);

  for(auto e: map) {
    std::cout << (e == 1 ? '+' : '*');
  }
  std::cout << std::endl;

  return 0;
}
0