## Instructions

**Objective**

## Requirements and Specifications

**Source Code
**

#include<vector>

#include <bits/stdc++.h>

using namespace std;

// method which checks, if current player can stand in given row

static bool matches(vector<int>& row, int a) {

// if row is empty, player can stand here

if (row.empty()) {

return true;

}

// otherwise we check if sum of numbers of current player and previous player in row

// is a full square

int sum = row[row.size()-1] + a;

int sr = sqrt(sum);

return sr * sr == sum;

}

// method, which recursively builds all possible configurations

// it returns number of valid configurations which can be obtained from given state

// by adding players, starting from next

static int solveStep(vector<vector<int>> state, int next, int last) {

// if all necessary players are located in rows, we must check if obtained state is valid

if (last < next) {

bool isOk = true;

// state is valid is there are no empty rows

for (vector<int> v : state) {

// setting flag to false, if there is an empty row

if (v.empty()) {

isOk = false;

break;

}

}

// if current state is valid, returning 1, otherwise - 0

return isOk ? 1 : 0;

}

// this variable will store number of valid final states, which can be obtained from

// current one

int sum = 0;

// iterating over all rows and trying to add next player to each row

for (int i = 0; i<state.size(); i++) {

// checking if next player can be put into i-th row

if (matches(state[i], next)) {

// if player can be put here, adding it to current state

state[i].push_back(next);

// and calling this method recursively for next player

// summing up the result

sum += solveStep(state, next+1, last);

// rollbacking state by deleting added played

state[i].pop_back();

// if this state was empty, skipping further checks, since it will cause duplicating

if (state[i].empty()) {

break;

}

}

}

// returning final sum

return sum;

}

// the solution approach is straightforward:

// we recursively build all possible configurations without duplicates

static int solve(int x, int n) {

// we will store current state as 2D matrix (nested vector of ints)

vector<vector<int>> solution(x);

// calling recursive method starting with empty state and first player to place

return solveStep(solution, 1, n);

}