Problemas de Programação

Link to the problem:  https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=3836 Every time that a crop-growing spot that is not covered by a scarecrow is found, it is assumed that the next position will receive a scarecrow. If the crop-growing spot is in the last position, and there is no scarecrow related to this spot, it will receive a scarecrow itself. The approach used was Greedy. import java.io.*; import java.util.*; class Main {     public static void process() throws NumberFormatException, IOException {         Scanner sc = new Scanner(System.in);                  int numTests = sc.nextInt();         for (int i = 0; i < numTests; i++) {             int lengthField = sc.nextInt();             char[] field = new char[lengthField];             String line = sc.next();             for (int j = 0; j < lengthField; j++) {                 field[j] = line.charAt(j);                          

Link to the problem: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=2258 We need to iterate over all the board in order to find if there is a way to form each given word. The solution below used backtracking to solve this problem. import java.io.*; import java.util.*; class Main {     public char[][] matrix;     public boolean[][] visited;     public String word;     public boolean gotWord;     public int[] vi = {-1,-1,-1,0,0,1,1,1};     public int[] vj = {-1,0,1,-1,1,-1,0,1};     public HashMap<Integer, Integer> mapScore;         public void initMapScore() {         mapScore.put(3, 1);         mapScore.put(4, 1);         mapScore.put(5, 2);         mapScore.put(6, 3);         mapScore.put(7, 5);     }         public void rec(int currI, int currJ, int currIndexWord) {         if (currI < 0 || currJ < 0 || currI >= 4 || currJ >= 4 || visited[currI][currJ] || matrix[currI][currJ] != word.c

Link to the problem: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=620 The ball can only go to two directions, left or right. If the ball's number is even, it goes to the left, but if it is odd, the ball goes to the right. Then, we know in which node the ball is through the operations: node = node*2 and node = node*2+1 . import java.io.*; import java.util.*; class Main {     public static void process() throws NumberFormatException, IOException {         Scanner sc = new Scanner(System.in);                 int numTests = sc.nextInt();         for (int i = 0; i < numTests; i++) {             int depth = sc.nextInt();             int ball = sc.nextInt();                         int node = 1;             int newBall = ball-1;             for (int j = 0; j < depth-1; j++) {                 if (newBall%2 == 0) {                     node = node*2;                 }                 else {            

Link to the problem: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=696 While reading the telephone numbers, they are all mapped to the common notation. Then, we only need to group the telephone numbers that are exactly the same in a structure that keeps not only the number, but also how many repetitions were found. import java.io.*; import java.util.*; class Main {     public static HashMap<Character, Integer> map;         public static void initMap() {         map.put('A', 2);         map.put('B', 2);         map.put('C', 2);         map.put('D', 3);         map.put('E', 3);         map.put('F', 3);         map.put('G', 4);         map.put('H', 4);         map.put('I', 4);         map.put('J', 5);         map.put('K', 5);         map.put('L', 5);         map.put('M', 6);         map.put('N&#

Link to the problem: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=583 For every word in the entry (dictionary or scrambled words), it is kept what characters compose each word and how many times they appear. In the end, for every scrambled word, it is checked if these information matches with one or more words in the dictionary. The approach used was grouping words that have the same amount of characters. import java.io.*; import java.util.*; class Main {     public static void process() throws NumberFormatException, IOException {         Scanner sc = new Scanner(System.in);                 HashMap<HashMap<Character, Integer>, ArrayList<String>> words = new HashMap<>();                 String line = sc.next();         while (!line.equals("XXXXXX")) {             HashMap<Character, Integer> letters = new HashMap<>();             // check which letters the wor

Link to the problem: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=2597 For every position next to a trap (up, down, left, right), we need to inform the player that it is not safe to move toward. Then, the only safe solution is to come back to the previous position from where he came. The player need to find all the positions where a piece of gold is, respecting the condition above mentioned. Therefore, the solution below used Depth-First Search. import java.io.*; import java.util.*; class Main {     public static int numRows;     public static int numCols;     public static char[][] matrix;     public static boolean[][] visited;     public static int[] vi = {-1,0,0,1};     public static int[] vj = {0,-1,1,0};     public static int countGold;             public static boolean isSafe(int currI, int currJ) {         for (int i = 0; i < 4; i++) {             int nextI = currI+vi[i];             int nextJ

Link to the problem: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=1444 For each domino, it is necessary to check if one of its sides matches with one of the sides of the borders. If a match is found, that border will become the new domino. This process is repeated until the number of dominoes required be reached or until it finds out that it is not possible to find a solution. The approach used was backtracking. import java.io.*; import java.util.*; class Main {     public static int numSpaces;     public static int numPieces;     public static ArrayList<Domino> dominos;     public static int[] considered;     public static boolean gotMatch;     public static boolean gotAnswer;         public static void rec(int leftRight, int rightLeft, int spaces) {         if (spaces == 0 && leftRight == rightLeft) { // left and right side must match to have only one sequence of dominoes             got

Link to the problem: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=3702 Every time that a group of at least two same characters is found, these characters are erased, and a new string containing the remaining characters is created. This process happens until it finds out whether the string can be empty or not. Therefore, it was used backtracking. import java.io.*; import java.util.*; class Main {     public static boolean canBeEmpty;         public static void rec(String s) {         if (s.equals("")) {             canBeEmpty = true;         }         if (canBeEmpty) {             return;         }                 for (int i = 0; i < s.length(); i++) {             int countEqual = 0;             for (int j = i+1; j < s.length(); j++) {                 if (s.charAt(j) != s.charAt(i)) {                     break;                 }                 countEqual++;             }             if (

Link to the problem: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=2026 For this problem, it is only necessary to try all the possible row positions for every queen in a column. The approach used was backtracking. import java.io.*; import java.util.*; class Main {     public static int[] rows;     public static int[][] matrixAttacks;     public static int maxUnchange;     public static int unchange;     //public static int[] vi = {-1,-1,-1,0,0,1,1,1};     //public static int[] vj = {-1,0,1,-1,1,-1,0,1};         public static void rec(int row, int indexRow, int col) {         if (col == 9) {             if (unchange > maxUnchange) {                 maxUnchange = unchange;             }             return;         }         if (indexRow-unchange > 8-maxUnchange) {             return;         }                 for (int i = 1; i <= 8; i++) {             if (matrixAttacks[i][col] != 0) {             

Link to the problem: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=1846 First, I tried to use backtracking to solve this problem. Although this first solution found the correct answer, it exceeded the time limit because the maximum number of entries could be 50. Then, I tried another solution that read all the numbers as strings. The comparison is done by concatenating every two strings as string1string2 and string2string1 and checking which one was greater. import java.io.*; import java.util.*; import java.math.*; class Main {     public int compareNumbers(int n1, int n2) {         if (n1 > n2) {             return 1;         }         else if (n1 < n2) {             return -1;         }          return 0;     }         public Comparator<String> numberComparator = new Comparator<String>() {         public int compare(String s1, String s2) {             StringBuilder sb1 = new StringB

Link to the problem: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1672 In the output of this problem, we need to present a set of answers, where contradictory answers need to be in the same set. Contradictory answers are those that compose a cycle (" the answers may indicate a preference for X over Y and also for Y over X "). Therefore, the solution below is using Kosaraju's algorithm to solve this problem. Kosaraju is one of the algorithms used to find strongly connected components. import java.io.*; import java.util.*; class Main {     public HashMap<Character, ArrayList<Character>> adjListOut;     public HashMap<Character, ArrayList<Character>> adjListOutReverse;     public Deque<Character> stack;     public HashSet<Character> visited;     public HashMap<Character, Integer> identities;         public void dfsReverse(Character c, int idt) {         if (visited

Link to the problem: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=2829 First, we need to sort the entries according to the time a soldier need to complete a job. Then, the soldiers are chosen from those who need more time to complete a job to those who need less time. import java.io.*; import java.util.*; class Main {     public static void process() throws NumberFormatException, IOException {         Scanner sc = new Scanner(System.in);            int numCase = 0;         int numSoldiers = sc.nextInt();         while (numSoldiers != 0) {             Soldier[] soldiers = new Soldier[numSoldiers];             for (int i = 0; i < numSoldiers; i++) {                 int brief = sc.nextInt();                 int execTime = sc.nextInt();                 soldiers[i] = new Soldier(brief, execTime);             }             Arrays.sort(soldiers);             int sumTime = 0;             int maxTime = 0;    

Link to the problem: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=2597 For this problem, if the player reaches a position that is next to a trap, the only safe solution is to go back to the old position. Due to this fact, the solution below is using the Depth-First Search. import java.io.*; import java.util.*; class Main {     public static int numRows;     public static int numCols;     public static char[][] matrix;     public static boolean[][] visited;     public static int[] vi = {-1,0,0,1};     public static int[] vj = {0,-1,1,0};     public static int countGold;             public static boolean isSafe(int currI, int currJ) {         for (int i = 0; i < 4; i++) {             int nextI = currI+vi[i];             int nextJ = currJ+vj[i];             if (matrix[nextI][nextJ] == 'T') {                 return false;             }         }                 return true;     }         public s

Link to the problem: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=1168 Each person is associated with a structure that contains all the trees that this person heard. In the end, these structures are grouped in order to check how many different structures we have. import java.io.*; import java.util.*; class Main {     public static void process() throws NumberFormatException, IOException {         BufferedReader br = new BufferedReader(new InputStreamReader(System.in));                 int numTests = Integer.parseInt(br.readLine());         br.readLine(); // blank space         for (int i = 0; i < numTests; i++) {             if (i > 0) {                 System.out.println();             }                         String line = br.readLine();             String[] s = line.split("\\s");             int numPeople = Integer.parseInt(s[0]);             int numTrees = Integer.parseInt(s[1]);