Problemas de Programação

Link to the problem: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=646&page=show_problem&problem=1004 The solution below used Backtracking to solve this problem. import java.io.*; import java.util.*; class Main {     public String sequence;     BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));        public void rec(int index, char[] array) throws NumberFormatException, IOException {         if (index == sequence.length()) {             for (int i = 0; i < array.length; i++) {                 bw.write(array[i]);             }             bw.write("\n");             return;         }                for (int j = index; j > 0; j--) {             array[j] = array[j-1];         }         array[0] = sequence.charAt(index);         rec(index+1, array);         for (int i = 1; i <= index; i++) {             char tmp = array[i];             array[i] = array[i-1];             array[i-1] = tmp;     

Link to the problem: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=2231 The solution below used a Greedy approach to solve this problem. From the first coin, we check if the sum of the value of all the considered coins is less than the value of the next coin. If so, we add the value of the next coin to our sum. In the end, we only need to check how many coins were added to this sum. import java.io.*; import java.util.*; class Main {     public int[] coins;     public HashSet<Integer> myCoins;        public void process() throws NumberFormatException, IOException {         Scanner sc = new Scanner(System.in);         BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));         int numTests = sc.nextInt();         for (int test = 0; test < numTests; test++) {             int numCoins = sc.nextInt();             coins = new int[numCoins];             for (int i = 0; i < n

Link to the problem: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=3362 The solution below used a Greedy approach to solve this problem. The problem states that we should start matching the pairs by the most senior bachelor. Then, we can sort the array related to the bachelors' ages in a descending order. The most senior bachelor available would be linked to the most senior spinster available. Finally, if there is any bachelor that is not linked to a spinster, we present the youngest one by getting the last element in the array of bachelors. import java.io.*; import java.util.*; class Main {     public void process() throws NumberFormatException, IOException {         Scanner sc = new Scanner(System.in);         BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));         int numCase = 0;         int numBachelors = sc.nextInt();         int numSpinsters = sc.nextInt();       

Link to the problem: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=2354 The solution bellow used a Greedy approach to solve this problem. We sort the array of items in a decreasing order and, every 3 items, we sum the value of the last item (the one that would be given for free). import java.io.*; import java.util.*; class Main {     public void process() throws NumberFormatException, IOException {         Scanner sc = new Scanner(System.in);         BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));         int numTests = sc.nextInt();         for (int test = 0; test < numTests; test++) {             int numItems = sc.nextInt();             Integer[] items = new Integer[numItems];             for (int i = 0; i < numItems; i++) {                 items[i] = sc.nextInt();             }             Arrays.sort(items, Collections.reverseOrder());                         int t

Link to the problem: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=2384 The solution below used a Greedy approach to solve this problem. We sort the array related to the morning routes in ascending order, and the array related to the evening routes in descending order. Then, it is possible to have the best solution once we have the sum of the biggest value in an array and the smallest value in the other. import java.io.*; import java.util.*; class Main {     public void process() throws NumberFormatException, IOException {         Scanner sc = new Scanner(System.in);         BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));         int numBusDrivers = sc.nextInt();         int limit = sc.nextInt();         int r = sc.nextInt();         while (numBusDrivers != 0 || limit != 0 || r != 0) {             Integer[] morning = new Integer[numBusDrivers];             for (int i = 0; i

Link to the problem: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=646&page=show_problem&problem=3112 The solution below used Backtracking to solve this problem. Every time that the method rec is called, it will keep the character in the current position ( numChanges+0 ) or it will change the character by a character in the array elements ( numChanges+1 ) . import java.io.*; import java.util.*; class Main {     public int length;     public int numAllowedChanges;     public String sequence;     public char[] dna;     public char[] elements = {'A', 'C', 'G', 'T'};     public TreeSet<String> mutatedDNA;        public void rec(char[] dnaArray, int index, int numChanges) {         if (numChanges > numAllowedChanges) {             return;         }         if (index == length) {             StringBuilder sb = new StringBuilder();             for (int i = 0; i < dnaArray.length; i++) {         

Link to the problem: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=3146 The solution below declared the three data structures being considered (Queue, Stack, and Priority Queue). Then, every time that a new element was inserted in the structure, all the three of them received this element. Moreover, every time that a query was received, we checked if the element returned by the input was the same of the output of each data structure. import java.io.*; import java.util.*; class Main {     public Comparator<Integer> intComparator = new Comparator<Integer>() {         public int compare(Integer i1, Integer i2) {             return i2-i1;         }     };        public void process() throws NumberFormatException, IOException {         Scanner sc = new Scanner(System.in);         BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));         while (sc.hasNext()) {            

Link to the problem: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=1041 The solution below used the concept of Longest Common Subsequence (LCS), related to Dynamic Programming, to solve this problem. import java.io.*; import java.util.*; class Main {     public String[] s1;     public String[] s2;     public int[][] memo;        public int rec(int indexS1, int indexS2) {         if (indexS1 == s1.length || indexS2 == s2.length) {             return 0;         }                if (memo[indexS1][indexS2] != -1) {             return memo[indexS1][indexS2];         }                int jumpLeft = rec(indexS1+1, indexS2);         int jumpRight = rec(indexS1, indexS2+1);         int equal = (s1[indexS1].equals(s2[indexS2])) ? rec(indexS1+1, indexS2+1) + 1 : rec(indexS1+1, indexS2+1) + 0;                memo[indexS1][indexS2] = Math.max(jumpLeft, Math.max(jumpRight, equal));         return memo[indexS1][indexS2

Link to the problem: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=1007 The solution below used the concept of Longest Common Subsequence (LCS), related to Dynamic Programming, to solve this problem. import java.io.*; import java.util.*; class Main {     public int numTilesN1;     public int numTilesN2;     public int[] tilesN1;     public int[] tilesN2;     public int[][] memo;        public int rec(int indexN1, int indexN2) {         if (indexN1 == numTilesN1 || indexN2 == numTilesN2) {             return 0;         }                if (memo[indexN1][indexN2] != -1) {             return memo[indexN1][indexN2];         }                int jumpLeft = rec(indexN1+1, indexN2);         int jumpRight = rec(indexN1, indexN2+1);         int equal = (tilesN1[indexN1] == tilesN2[indexN2]) ? rec(indexN1+1, indexN2+1) + 1 : rec(indexN1+1, indexN2+1) + 0;                memo[indexN1][indexN2] = Math.max(jumpLeft,

Link to the problem: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=1895 The solution below used a Priority Queue to solve this problem because the best solution is always to sum the two smallest numbers. import java.io.*; import java.util.*; class Main {     public void process() throws NumberFormatException, IOException {         Scanner sc = new Scanner(System.in);         BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));         int numNumbers = sc.nextInt();         while (numNumbers != 0) {             Queue<Integer> queue = new PriorityQueue<>();             for (int i = 0; i < numNumbers; i++) {                 queue.add(sc.nextInt());             }             int lastSum = queue.poll()+queue.poll();             queue.add(lastSum);             int sumCost = lastSum;             for (int i = 2; i < numNumbers; i++) {                 lastSum = queue.poll(

Link to the problem: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=1680 The solution below is an iterative version of the previous solution. import java.io.*; import java.util.*; class Main {     public String s;     public int[][] memo;         public void process() throws NumberFormatException, IOException {         Scanner sc = new Scanner(System.in);         BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));         int numTests = sc.nextInt();         memo = new int[1024][1024];         for (int test = 0; test < numTests; test++) {             s = sc.next();             for (int i = 0; i < s.length(); i++) {                 for (int j = 0; j < s.length(); j++) {                     memo[i][j] = -1;                 }             }                         for (int d = 1; d < s.length(); d++) {                 for (int i = 0; i < s.length() -d ; i++) {          

Link to the problem: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=1680 The solution below used Dynamic Programming to solve this problem. import java.io.*; import java.util.*; class Main {     public String s;     public int[][] memo;         public int rec(int left, int right) {         if (left >= right) {             return 0;         }                 if (memo[left][right] != -1) {             return memo[left][right];         }         int min = Integer.MAX_VALUE;         min = Math.min(min, rec(left, right-1) + 1); // insert left         min = Math.min(min, rec(left+1, right) + 1); // delete left         min = Math.min(min, rec(left+1, right-1) + ((s.charAt(left) == s.charAt(right)) ? 0 : 1)); // replace                 memo[left][right] = min;         return memo[left][right];     }         public void process() throws NumberFormatException, IOException {         Scanner sc = new Scanner(Syste

Link to the problem: https://uva.onlinejudge.org /index.php?option=com_onlinejudge&Itemid=8&category=633&page=show_problem&problem=3644 The solution below used a Priority Queue to solve this problem. import java.io.*; import java.util.*; class Main {     public void process() throws NumberFormatException, IOException {         Scanner sc = new Scanner(System.in);         BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));         Queue<Data> queue = new PriorityQueue<Data>();                 String command = sc.next();         while (!command.equals("#")) {             int id = sc.nextInt();             int period = sc.nextInt();             queue.add(new Data(id, period, period));             command = sc.next();         }                 int numQueries = sc.nextInt();         for (int i = 0; i < numQueries; i++) {             Data d = queue.poll();             bw.write(d.id+"\n");             queue.add(ne

Link to the problem: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=751&page=show_problem&problem=3648 The solution below used the concept of Edit Distance, related to Dynamic Programming, to solve this problem. import java.io.*; import java.util.*; class Main {     public int s1Length;     public String s1;     public int s2Length;     public String s2;     public int[][] memo;         public int rec(int indexS1, int indexS2) {         if (indexS1 == s1Length) {             return s2Length-indexS2;         }         if (indexS2 == s2Length) {             return s1Length-indexS1;         }                 if (memo[indexS1][indexS2] != -1) {             return memo[indexS1][indexS2];         }                 int delete = rec(indexS1+1, indexS2) + 1;         int insert = rec(indexS1, indexS2+1) + 1;         int change = rec(indexS1+1, indexS2+1) + ((s1.charAt(indexS1) == s2.charAt(indexS2)) ? 0 : 1);                 memo[indexS1][inde

Link to the problem: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=751&page=show_problem&problem=1346 The solution below used the concept of Longest Common Subsequence, related to Dynamic Programming, to solve this problem. import java.io.*; import java.util.*; class Main {     public String s1;     public String s2;     public int[][] memo;         public int rec(int indexS1, int indexS2) {         if (indexS1 == s1.length() || indexS2 == s2.length()) {             return 0;         }         if (memo[indexS1][indexS2] != -1) {             return memo[indexS1][indexS2];         }                         int nextS1 = rec(indexS1+1, indexS2);         int nextS2 = rec(indexS1, indexS2+1);         int nextS1S2 = rec(indexS1+1, indexS2+1) + ((s1.charAt(indexS1) == s2.charAt(indexS2)) ? 1 : 0);                 memo[indexS1][indexS2] = Math.max(nextS1, Math.max(nextS2, nextS1S2));         return memo[indexS1][indexS2];     }         publi

Link to the problem: http://www.spoj.com/problems/EDIT/ If you want to see another solution for this problem, click here . The solution below used a Greedy approach to solve this problem. import java.io.*; import java.util.*; class Main {     public String s;         public void process() throws NumberFormatException, IOException {         BufferedReader br = new BufferedReader(new InputStreamReader(System.in));         BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));                               s = br.readLine();         while (s != null) {             int sumChanges1 = 0;             int last = (s.charAt(0) >= 'A' && s.charAt(0) <= 'Z') ? 1 : 0; // 1 -> upper , 0 -> lower             for (int i = 1; i < s.length(); i++) {                 int curr = (s.charAt(i) >= 'A' && s.charAt(i) <= 'Z') ? 1 : 0;                 if (last == curr) {                     sumChanges1++;            

Link to the problem: http://www.spoj.com/problems/EDIT/ The solution below used Dynamic Programming to solve this problem. import java.io.*; import java.util.*; class Main {     public String s;     public int[][] memo;     public int f(char c) {         return (c >= 'A' && c <= 'Z') ? 1 : 0;     }        public int rec(int index, int last) {         if (index == s.length()) {             return 0;         }             if (memo[index][last] != -1) {             return memo[index][last];         }                 // last == 0 -> last character was upper         // last == 1 -> last character was lower         int sum = 0;         sum = rec(index+1, (last+1)%2) + (last == f(s.charAt(index)) ? 1 : 0);                 memo[index][last] = sum;         return memo[index][last];     }         public void process() throws NumberFormatException, IOException {         BufferedReader br = new BufferedReader(new InputStreamReader(System.in));         Buffe

Link to the problem: http://www.spoj.com/problems/EDIST/ The solution below used a concept called Edit Distance, related to Dynamic Programming, to solve this problem. import java.io.*; import java.util.*; class Main {     public String s1;     public String s2;     public int[][] memo;         public int rec(int indexS1, int indexS2) {         if (indexS1 == s1.length()) {             return s2.length()-indexS2;         }         if (indexS2 == s2.length()) {             return s1.length()-indexS1;         }                 if (memo[indexS1][indexS2] != -1) {             return memo[indexS1][indexS2];         }                        int delete = rec(indexS1+1, indexS2)+1;         int insert = rec(indexS1, indexS2+1)+1;         int replace = rec(indexS1+1, indexS2+1)+(s1.charAt(indexS1) == s2.charAt(indexS2) ? 0 : 1);                     memo[indexS1][indexS2] = Math.min(delete, Math.min(insert, replace));         return memo[indexS1][indexS2];     }         public void process()

Link to the problem: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=1446 For every bipartite graph, we need to find out which "side" has more nodes. The solution below used a Breath-First Search (BFS) to accomplish this task.  import java.io.*; import java.util.*; class Main {     public ArrayList<ArrayList<Integer>> adjList;     public int[] state;         public int bfs(int start) {         Queue<Integer> queue = new ArrayDeque<>();         queue.add(start);         state[start] = 0;                 boolean possible = true;                 int stateZero = 0;         int stateOne = 0;         while (queue.size() > 0) {             int currPeople = queue.poll();             if (state[currPeople] == 0) {                 stateZero++;             }             else {                 stateOne++;             }                         ArrayList<Integer> reachPeople =