Problemas de Programação

I used Brute Force to solve this problem. I considered only the numbers that have an exact square. Once a Quirksome Square is a number 'xyzw' where (xy+zw)^2 = xyzw, these numbers are the only possible answers.   import java.io.*; import java.util.*; class Main  {     public static void process() throws NumberFormatException, IOException {          BufferedReader br = new BufferedReader(new InputStreamReader(System.in));                String line = br.readLine();         while (line != null) {             int numDigits = Integer.parseInt(line);                        int div = 1;             for (int i = 0; i < numDigits; i+=2) {                 div *= 10;             }                        StringBuilder end = new StringBuilder();             for (int i = 0; i < numDigits; i++) {                 end.append(9);             }             int size = Integer.parseInt(end.toString());             ArrayList<Integer> quirksomeSquares = new ArrayList<Integer>(

If you want to see another solution for this problem, click here . As in the previous solution, I am using Brute Force. However, instead of using some nestled for loops, I am using recursion. The execution time for this solution was worse than for the previous one. import java.io.*; import java.util.*; class Main  {     public static int[] binsContent;     public static ArrayList<Solution> solutions;     public static int[] chosen;     public static String colorsLetters = "BGC";         public static int calc(int firstBin, int secondBin, int thirdBin) {         int sum = 0;         for (int i = 0; i < 3; i++) { // get how many bottles will be moved             if (i != firstBin) {                 sum += binsContent[i];             }         }         for (int i = 3; i < 6; i++) {             if (i%3 != secondBin) {                 sum += binsContent[i];             }         }         for (int i = 6; i < 9; i++) {             if (i%3 != thirdBin) {      

I used Brute Force to solve this problem. Here, I used some nestled for loops to find all the possible solutions. import java.io.*; import java.util.*; class Main  {     public static int[] binsContent;     public static String colorsLetters = "BGC";         public static int calc(int b, int g, int c) {         int sum = 0;         for (int i = 0; i < 3; i++) {             if (i != b) {                 sum += binsContent[i];             }         }         for (int i = 3; i < 6; i++) {             if (i%3 != g) {                 sum += binsContent[i];             }         }         for (int i = 6; i < 9; i++) {             if (i%3 != c) {                 sum += binsContent[i];             }         }                 return sum;     }         public static void process() throws NumberFormatException, IOException {           BufferedReader br = new BufferedReader(new InputStreamReader(System.in));                 String line = br.readLine();         while (line !=

I used Depth-First Search to solve this problem. After reading the matrix, I use a DFS to find all the characters 'X'. In this method, each group of 'X' receives a number, which will help get the answer in the end. Then, I mark all the '.' position as visited. And finally, I call the DFS method to find all the characters 'X' in every die. Once each group of 'X' has its own "identification number", I only need to add each ID that I found during the DFS in a structure, and then, count how many different IDs I got. PS.: For every die, it will execute the DFS method once. import java.io.*; import java.util.*; class Main  {     public static char[][] matrix;     public static int[][] matrixInt;     public static boolean[][] visited;     public static int numRows;     public static int numCols;     public static int count;     public static int[] vx = {-1,0,0,1};     public static int[] vy = {0,-1,1,0};     public static HashSet<Int

I used Depth-First Search to solve this problem. import java.io.*; import java.util.*; import java.lang.Math; class Main  {     public static int[][] matrix;     public static boolean[][] visited;     public static int count;     public static int dimension;     public static int[] vi = {-1,0,0,1};     public static int[] vj = {0,-1,1,0};         public static void dfs(int currI, int currJ, int border) {         //if (currI < 0 || currJ < 0 || currI >= dimension || currJ >= dimension || (currI != border && currJ != border && currI != dimension-border-1 && currJ != dimension-border-1) || visited[currI][currJ]) {         if (currI < 0 || currJ < 0 || currI >= dimension || currJ >= dimension || (currI != border && currJ != border) || visited[currI][currJ]) {             return;         }                 visited[currI][currJ] = true;         count += matrix[currI][currJ];         for (int i = 0; i < 4; i++) {             int nex

I used Depth-First Search to solve this problem. First, I find the character that is responsible for the contour. Then, I iterate over the borders of the matrix in order to visit all the spaces that are not completely surrounded by the contour characters. After it is done, I apply the DFS method every time I find a marking character. Moreover, I had to use BufferedWriter instead of the common System.out to print the answers because I got a "Time Limit Exceeded" when I used the second option. import java.io.*; import java.util.*; class Main  {     public static final int ROWS = 30;     public static final int COLS = 80;     public static int numCols;     public static int numRows;     public static char[][] matrix;     public static boolean[][] visited;     public static char contour;     public static char marking;     public static int[] vx = {-1,0,0,1};     public static int[] vy = {0,-1,1,0};         public static void dfs(int currX, int currY) {         if (currX &

I used Dijkstra's algorithm to solve this problem. If you want to see another solution for this problem, click here . In both solutions I used two Dijkstras. The difference between this solution and the previous one is that here I keep only the parent of each point in my queue. For every point, I keep a list of parents because if it is possible to reach a point through more than one point with the same shortest cost, I have to add all these points to my list. In the end of the first Dijkstra, I call another method responsible for iterate over the list of parents to remove the edges that belong to the shortest path from the start to the end point. Finally, I call the second Dijkstra, which will give the answer. import java.io.*; import java.util.*; class Main  {     public static HashMap<Integer, ArrayList<SimpleEdge>> adjList;     public static ArrayList<ArrayList<Integer>> parents;     public static int[] costs;        public static Comparator&

I used Dijkstra's algorithm to solve this problem. For this solution, I used the Dijkstra method twice. In the first time, all the edges that are used to find the shortest path were detected. Then, the edges found earlier were removed, and the Dijkstra method was used again to find the new shortest path, if it exists. import java.io.*; import java.util.*; class Main  {     public static HashMap<Integer, ArrayList<SimpleEdge>> adjList;     public static ArrayList<ArrayList<Integer>> edges;     public static int[] degrees;         public static Comparator<Edge> costComparator = new Comparator<Edge>() {         public int compare(Edge e1, Edge e2) {             return e1.cost-e2.cost;         }     };         public static int dijkstraShortestPath(int start, int end, int numPoints, boolean firstDijkstra) {         Queue<Edge> queue = new PriorityQueue<Edge>(numPoints, costComparator);         queue.add(new Edge(start, 0, new ArrayLi

I used Dijkstra's algorithm to solve this problem. If you want to see another solution for this problem, click here . The difference between this solution and the previous one is that in the first solution, I used only one structure that maps each floor to an array of floors & cost. Therefore, I did not have a different structure for each elevator. Then, it was necessary to apply some calculus to get the floor of a specific elevator. In the second solution, I use one structure that contains the elevator, an array of floors for each elevator, and an array of floors & cost for each one of the floors. Then, it is not necessary to apply any additional calculus to get a floor. Therefore, it reduces the time of execution.  import java.io.*; import java.util.*; class Main  {     public static int[] speedElevators;     public static ArrayList<ArrayList<ArrayList<Edge>>> graph;         public static Comparator<Edge> costComparator = new Comparator<

I used Dijkstra's algorithm to solve this problem. import java.io.*; import java.util.*; class Main  {     public static int[] speedElevators;     public static HashMap<Integer, ArrayList<Edge>> graph;         public static Comparator<Edge> costComparator = new Comparator<Edge>() {         public int compare(Edge e1, Edge e2) {             return e1.cost-e2.cost;         }     };         public static int dijkstra(int start, int dest, int numElevators) {         Queue<Edge> queue = new PriorityQueue<Edge>(100, costComparator);         for (int i = 0; i < numElevators; i++) {             queue.add(new Edge(i*100, 0));         }                 HashSet<Integer> visited = new HashSet<Integer>();                 while (queue.size() > 0) {             Edge curr = queue.poll();             int currFloor = curr.floor;             int currCost = curr.cost;                         if (visited.contains(currFloor)) {                 con