Instructions
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);
}