Untitled

// TEAM:
// Aman Bhutani,         bhutani.am@northeastern.edu
// Vladislav Manoylo,    manoylo.v@northeastern.edu
// Sophie Chun Hui Yang, yang.sophi@northeastern.edu

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


int dp[1001][1001] = {0};
int cut[1001][1001];
char dir[1001][1001];

struct pos
{
    int x;
    int y;
    pos(int a, int b): x(a), y(b) {}
};
int main()
{
    int n,m;
    cin >> n >> m;
    
    for (int i=1; i <= n; i++)
    {
        dir[i][1] = 'H';
        cut[i][1] = 1;
        dp[i][1] = i-1;
    }
        
    for (int i=1; i <= m; i++)
    {
        dir[1][i] = 'V';
        cut[1][i] = 1;
        dp[1][i] = i-1;
    }
    
    for (int i = 2; i <= n; i++)
    {
        for (int j = 2; j <= m; j++)
        {
            if (i == j)
                dp[i][j] = 0;
            else
            {
                int min = -1;
                char direct = 'N';
                int index = -1;
                //V
                for (int k = 1; k < j ; k++)
                {
                    if (min == -1 || min > dp[i][k] + dp[i][j-k] + 1 )
                    {
                        direct = 'V';
                        min = dp[i][k] + dp[i][j-k] + 1;
                        index = k;
                    }
                }

                //H
                for (int k = 1; k < i ; k++)
                {
                    if (min == -1 || min > dp[k][j] + dp[i-k][j] + 1 )
                    {
                        direct = 'H';
                        min = dp[k][j] + dp[i-k][j] + 1;
                        index = k;
                    }
                }
                dp[i][j] = min;
                cut[i][j] = index;
                dir[i][j] = direct;
            }
        }
    }
    
    stack<pos> S;
    
    S.push(pos(n,m));
    cout << dp[n][m] << endl;;

    while(!S.empty())
    {
        pos p = S.top();
        S.pop();
        if (dp[p.x][p.y]==0)
            continue;
        cout << dir[p.x][p.y] << ' ' << p.x << 'x' << p.y << " --> ";
        if (dir[p.x][p.y] == 'V')
        {
            S.push(pos(p.x, p.y - cut[p.x][p.y]));
            S.push(pos(p.x, cut[p.x][p.y]));
            
            cout << p.x << 'x' << cut[p.x][p.y] << ' ';
            cout << p.x << 'x' << p.y - cut[p.x][p.y] << endl;
        }
        else if (dir[p.x][p.y] == 'H')
        {
            S.push(pos(p.x - cut[p.x][p.y], p.y ));
            S.push(pos(cut[p.x][p.y], p.y));
            
            cout << cut[p.x][p.y] << 'x' << p.y << ' ';
            cout << p.x - cut[p.x][p.y] << 'x' << p.y << endl;
        }
        
    }
    
    return 0;
}