(SPOJ) Floresta - Solution

Link to the problem: http://br.spoj.com/problems/FLOREST2/

This problem has a pattern. We start the grid with height equals to '2'. Then, to complete the "width of a square", we need more 3 trees (our 'seq'). Every time that the height is increased by one, the amount of trees necessary to complete the width of a square is increased by two. 

We only count an arrangement if, given the number of available trees, it is possible to complete the width of a square.

We stop to consider the arrangements when the height becomes bigger than width because we already counted the next arrangements.


import java.io.*;
import java.util.*;

class solucao {
    public void process() throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
       
        int numTrees = Integer.parseInt(br.readLine());
       
        int count = 0;
        int height = 2;
        int seq = 3;
        while (seq < numTrees) {
            if ((numTrees-height)%seq == 0) {
                count++;
            }
            int width = (numTrees-height)/seq;
            if (height > width) {
                break;
            }

            height++;
            seq += 2;
        }
       
        bw.write(count+"\n");
           
        bw.flush();
        bw.close();
       
        return;
    }
   
    public static void main(String[] args) throws NumberFormatException, IOException {
        solucao m = new solucao();
        m.process();
       
        System.exit(0);
    }
}