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=3649 We want to determine a set of tunnels which has the least cost. Then, we can use a Minimum Spanning Tree to solve this problem. import java.io.*; import java.util.*; class Main {     public ArrayList<Edge> list;     public int[] nodeParent;     public int[] depth;         public int root(int n) {         while (n != nodeParent[n]) {             n = nodeParent[n];         }         return n;     }         public boolean union(int n1, int n2) {         int rootN1 = root(n1);         int rootN2 = root(n2);                 if (rootN1 != rootN2) {             if (depth[rootN1] >= depth[rootN2]) {                 nodeParent[rootN2] = nodeParent[rootN1];                 if (depth[rootN1] == depth[rootN2]) {                     depth[rootN1] += 1;                 }             }             else {                 nodeParent[rootN1]

Link to the problem: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=2931 The solution below just execute a graph traversal following the instructions on the problem statement. import java.io.*; import java.util.*; class Main {     public char[][] matrix;     public char[] instructions;     public String positions = "NLSO";     public int numRows;     public int numCols;     public int countStickers;         public void changePosition(int i, int j, char curr) {         if (matrix[i][j] == '*') {             countStickers++;         }         matrix[i][j] = curr;     }         public boolean isValidPosition(int i, int j) {         if (i < 0 || j < 0 || i >= numRows || j >= numCols || matrix[i][j] == '#') {             return false;         }         return true;     }         public void process() throws NumberFormatException, IOException {         Scanner sc = new Scan

Link to the problem: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=1956 The solution below used Floyd-Warshall to solve this problem. It is necessary to sum the values in every row to achieve the answer. 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 numMembers = sc.nextInt();         int numPaths = sc.nextInt();         while (numMembers != 0 || numPaths != 0) {             String[] names = new String[numMembers];             for (int i = 0; i < numMembers; i++) {                 names[i] = sc.next();             }                              int[][] matrix = new int[numMembers][numMembers];             for (int i = 0; i < numMembers; i++) {                 f

Link to the problem: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=668&page=show_problem&problem=813 The solution below used a mix of Topological Sorting and Backtracking to solve this problem. import java.io.*; import java.util.*; class Main  {     public HashMap<Character, ArrayList<Character>> dependents;     public ArrayList<Character> sequence;     public boolean[] considered;     public int numConsidered;     public int[] degrees;     public ArrayList<Character> zeroDegree;     public int totalLetters;     public TreeSet<String> answer;     public String[] letters;       public void rec() {         if (numConsidered == letters.length) {             StringBuilder sb = new StringBuilder();             for (int i = 0; i < sequence.size()-1; i++) {                 sb.append(sequence.get(i)+" ");             }             sb.append(sequence.get(sequence.size()-1));             answer.add(s

Link to the problem: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=2760   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++) {             String s1 = sc.next();             String s2 = sc.next();                         boolean same = true;                         if (s1.length() != s2.length()) {                 same = false;             }                         String vowels = "aeiou";             for (int i = 0; i < s1.length() && same; i++) {                 if (vowels.indexOf(s1.charAt(i)) == -1) { // it is a consonant                     if (s1.charAt(i) != s2.charAt(i)) { // if one is consona

Link to the problem: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=1190 The solution below used a Greedy approach to solve this problem. More details about this solution can be found in the code below through the comments. 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 numTeams = sc.nextInt();         int numTables = sc.nextInt();         while (numTeams != 0 || numTables != 0) {             Team[] teams = new Team[numTeams];             Table[] tables = new Table[numTables];                         for (int i = 0; i < numTeams; i++) {                 teams[i] = new Team(i, sc.nextInt());             }             for (int i = 0; i < numTables; i++) {                 tables[i] = new Ta

Link to the problem: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=535 The solution below used Bit Manipulation 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));         while (sc.hasNext()) {             int n = sc.nextInt();             int saveN = n;                        int p = 0;             int count = 0;             while (count < 4) {                 p <<= 8;                 int lastEightBits = (n&255);                 n >>= 8;                 p += lastEightBits;                 count++;             }                        bw.write(saveN+" converts to "+p+"\n");                   }                                                        

Link to the problem: https://www.hackerrank.com/challenges/lonely-integer The solution below used Bit Manipulation to solve this problem. If we do "a xor a", it result in 0. Once each number would appear twice, except for one of them, we can use this strategy. import java.io.*; import java.util.*; import java.text.*; import java.math.*; import java.util.regex.*; public class Solution {     private static int lonelyInteger(int[] a) {         int result = 0;         for (int i = 0; i < a.length; i++) {             result ^= a[i];         }         return result;     }     public static void main(String[] args) {         Scanner in = new Scanner(System.in);         int n = in.nextInt();         int[] a = new int[n];         for (int i = 0; i < n; i++) {             a[i] = in.nextInt();         }         System.out.println(lonelyInteger(a));     } }

Link to the problem: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=2531 The solution below used a technique called Sliding Window to solve this problem. import java.io.*; import java.util.*; class Main {     public void process() throws NumberFormatException, IOException {         BufferedReader br = new BufferedReader(new InputStreamReader(System.in));         BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));         int numTests = Integer.parseInt(br.readLine());         for (int test = 0; test < numTests; test++) {             String line = br.readLine();             String[] s = line.split(" ");             int n = Integer.parseInt(s[0]);             int m = Integer.parseInt(s[1]);             int k = Integer.parseInt(s[2]);                         int[] array = new int[n];             array[0] = 1;             array[1] = 2;             array[2] = 3;            

Link to the problem: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=626&page=show_problem&problem=3084 The solution below used Bit Manipulation to solve this problem. import java.io.*; import java.util.*; class Main {     public void process() throws NumberFormatException, IOException {         BufferedReader br = new BufferedReader(new InputStreamReader(System.in));         BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));         int n = Integer.parseInt(br.readLine());         while (n != 0) {             int[] v = new int[2];                         int turn = 0;             int result = n^(n-1);             if (result == 1) {                 v[turn] |= result;                 n -= 1;             }             else {                 int tmp = (n-1)&n;                 v[turn] |= tmp^n;                 n = (n-1)&n;             }                turn++;                                     while (n &g

Link to the problem: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=944 The solution below used Dynamic Programming to solve this problem. import java.io.*; import java.util.*; class Main {     public int lengthStick;     public int numCuts;     public int[] cuts;     public int[][] memo;         public int rec(int start, int end) {         if (memo[start][end] != -1) {             return memo[start][end];         }         int numPossible = 0;         for (int i = 0; i < numCuts; i++) {             if (cuts[i] > start && cuts[i] < end) {                 numPossible++;             }         }         if (numPossible == 0) {             return 0;         }                         int price = 0;         int minPrice = Integer.MAX_VALUE;         for (int i = 0; i < numCuts; i++) {             if (cuts[i] <= start || cuts[i] >= end) {                 continue;             }          

Link to the problem: https://uva.onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=2623 Some comments can be found in the code below. 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 numCharactersOnSign = sc.nextInt();             int numWords = sc.nextInt();             String[] words = new String[numWords];             for (int i = 0; i < numWords; i++) {                 words[i] = sc.next();             }                         StringBuilder sb = new StringBuilder();             for (int i = 0; i < words.length; i++) {                 int start = 0;                 for (int j = sb.length()-1; j >= Math.max(0, sb.length()-numCharacters

Link to the problem: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=3342 First, based on the total amount to pay we need to discover the total amount of watts that was consumed. Then, we can apply a Binary Search to find out how many watts each person wasted. import java.io.*; import java.util.*; class Main {     public int totalAmount;     public int diffAmounts;     public int watts;     public Info[] v;         public int calcPrice(int w) {         int consumption = 0;         int amountToPay = 0;         int index = 1;         while (index < 4 && w > 0) {             consumption = Math.min(w, (v[index].limit-v[index-1].limit));             amountToPay += consumption*v[index].price;             w -= consumption;             index++;         }         amountToPay += w*7; // how much n eed to pay                 return amountToPay;     }         public int simulate(int myWatts) {         //

Link to the problem: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=3562 The solution below used a technique called Sliding Window 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));         while (sc.hasNext()) {             int numNumbers = sc.nextInt();             int desiredMinSum = sc.nextInt();                         int sum = 0;             int pointerLeft = 0;             int minElements = Integer.MAX_VALUE;             int[] numbers = new int[numNumbers];             for (int pointerRight = 0; pointerRight < numNumbers; pointerRight++) {                 numbers[pointerRight] = sc.nextInt();                 sum += numbers[pointerRight];                 while (sum >= desire

Link to the problem: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=2267 The solution below used a Greedy approach to solve this problem. We need an array to keep the diameters of the dragon's head, and another one to keep the knights' heights. Then, we sort both arrays, and for every knight, we check if he can cut a dragon's head. In the end, we only need to see if all the heads were cut, and give the answer according to it. 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 numHeads = sc.nextInt();         int numKnights = sc.nextInt();         while (numHeads != 0 || numKnights != 0) {             int[] heads = new int[numHeads];             int[] knightsHeights = new int[numKnight