ARC061 C - Many Formulas

Calendar Clock iconCalendar Clock icon

atcoder

Table of contents

# Problem

https://atcoder.jp/contests/arc061/tasks/arc061_a

# Time complexity

SS is the length of the string.

O(2S)O(2^S)

# Solution

// C++ 14
#include <iostream>
#include <string>
#include <vector>
#include <list>
#include <algorithm>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <unordered_map>
#include <math.h>

#define ll long long
#define Int int
#define loop(x, start, end) for(Int x = start; x < end; x++)
#define loopdown(x, start, end) for(int x = start; x > end; x--)
#define rep(n) for(int x = 0; x < n; x++)
#define span(a,x,y) a.begin()+x,a.begin()+y
#define span_all(a) a.begin(),a.end()
#define len(x) (x.size())
#define last(x) (*(x.end()-1))

using namespace std;
#include <sstream>
string S;

void input() {
  cin >> S;
}

Int dfs(string s) {
  stringstream ss(s);
  Int x = 0;
  ss >> x;
  if (s.length() == 1) return x;
  loop(n,1,s.length()) {
    string left = s.substr(0, n);
    string right = s.substr(n);
    stringstream ss2(left); Int leftNum = 0; ss2 >> leftNum;
    Int rightNum = dfs(s.substr(n));
    // i.e. 1 + 23
    //      1 + 2 + 3
    // Here '1 +' is added twice. (twice is the number of cases)
    x += leftNum * pow(2, right.length()-1) + rightNum;
  }
  return x;
}

void solve() {
  cout << dfs(S) << endl;
}

int main(void) {
  input();
  solve();
  return 0;
}

Remote freelancer. A web and mobile application enginner.
Traveling around the world based on East Asia.
I'm looking forward to your job offers from all over the world!

Offer jobs or contact me!

Comments