[UVa] 699 - The Falling leaves

Problem

Link: UVa 699 - The Falling leabes

hint

preorder

Code

C++

with array

#include <iostream>

bool recursion();

static constexpr const int MAX = 100;
// less stack consumption
static int pile[MAX];
static int left_bound, right_bound;
static int current_pile;

int main()
{
  int cases = 0;
  int i;

  // free sync overhead
  std::ios::sync_with_stdio(false);

  while (true)
  {
    //init
    left_bound = right_bound  = current_pile = MAX / 2;
    std::fill_n(pile, MAX, 0);

    // if the first is -1
    if (!recursion()) break;

    // output
    std::cout << "Case " << ++cases << ":\n";
    for (i = left_bound; i < right_bound; ++i)
      std::cout << pile[i] << " ";
    std::cout << pile[right_bound] << std::endl << std::endl;
  }

  return 0;
}

bool recursion()
{
  int current_value;
  std::cin >> current_value;
  if (current_value == -1) return false;

  if (current_pile < left_bound) left_bound = current_pile;
  else if (current_pile > right_bound) right_bound = current_pile;

  pile[current_pile] += current_value;

  --current_pile;
  recursion();
  current_pile += 2;
  recursion();
  --current_pile;

  return true;
}

with map

#include <iostream>
#include <map>

bool recursion();

static std::map<int, int> pile;
static int current_pile;

int main()
{
  int cases = 0;
  std::map<int, int>::const_iterator iter, iter_end;

  std::ios::sync_with_stdio(false);

  while (true)
  {
    pile.clear();
    current_pile = 0;
    if (!recursion()) break;
    std::cout << "Case " << ++cases << ":" << std::endl;
    iter = pile.cbegin(), iter_end = pile.cend();
    --iter_end;
    while (true)
      if (iter == iter_end) break;
      else std::cout << (iter++)->second << " ";
    std::cout << iter_end->second << std::endl << std::endl;
  }

  return 0;
}

bool recursion()
{
  int current_value;
  std::cin >> current_value;
  if (current_value == -1) return false;
  pile[current_pile] += current_value;

  --current_pile;
  recursion();
  current_pile += 2;
  recursion();
  --current_pile;

  return true;
}

Show Comments