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=3942 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 numRows = sc.nextInt();             int numCols = sc.nextInt();             int[][] matrix = new int[numRows][numCols];             for (int i = 0; i < numRows; i++) {                 String line = sc.next();                 for (int j = 0; j < numCols; j++) {                     matrix[i][j] = line.charAt(j)-'0';                 }             }             int count = 0;                     int bestCount = Integer.MAX_VALUE;               for (int j = 0; j < numCol

Link to the problem: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=666&page=show_problem&problem=4027 import java.io.*; import java.util.*; class Main {     public Deque<Character> trails;         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 seq = sc.next();             char start = seq.charAt(0);                         trails = new ArrayDeque<>();             int[] count = new int[26];             for (int i = 0; i < seq.length(); i++) {                 if (trails.peek() != null && trails.peek() == seq.charAt(i)) {                     count[seq.charAt(i)-'A']++;                     trails.poll();                     if (trails.peek() == null) {

Link to the problem: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=1734 The solution below used Floyd-Warshall 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));         int numTests = sc.nextInt();         for (int test = 0; test < numTests; test++) {             int numLocations = sc.nextInt();             int numConnections = sc.nextInt();                         int[][] matrix = new int[numLocations][numLocations];             for (int i = 0; i < numLocations; i++) {                 for (int j = 0; j < numLocations; j++) {                     matrix[i][j] = Integer.MAX_VALUE/2;                 }                 matrix[i][i] = 0;             }                         for (in

Link to the problem: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=676&page=show_problem&problem=324 The solution below used Breadth-First Search (BFS) to solve this problem. import java.io.*; import java.util.*; class Main {     public HashMap<Character, ArrayList<Info>> adjList;         public char bfs(char start, int numPlanets) {         Queue<Info> queue = new ArrayDeque<>();         queue.add(new Info(start, 0, 0));                 HashSet<Character> visited = new HashSet<>();                 double bestValue = 0;         char bestPlanet = 'Z';         while (queue.size() > 0) {             Info curr = queue.poll();             char currPlanet = curr.planet;             double currValue = curr.value;             int currDist = curr.distance;                         if (visited.contains(currPlanet) || currValue < 0) {                 continue;             }             visited.a

Link to the problem: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=676&page=show_problem&problem=370 The solution below used Floyd-Warshall to solve this problem. If you want to see another solution using Breadth-First Search, click here . import java.io.*; import java.util.*; class Main {     public ArrayList<String> mapIntToString;     public Map<String, Integer> mapStringToInt;         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());         br.readLine();         for (int test = 0; test < numTests; test++) {             if (test > 0) {                 bw.write("\n"); // blank line between outputs             }                         int index = 0;             mapInt

Link to the problem: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=676&page=show_problem&problem=370 The solution below used Breadth-First Search (BFS) to solve this problem. For every word that we visit in the BFS method, we check all the other words. If the other word differs only in one character of the current word, we add it in our queue. import java.io.*; import java.util.*; class Main {     public ArrayList<String> words;         public int bfs(String start, String end) {         Queue<Counter> queue = new ArrayDeque<>();         queue.add(new Counter(start, 0));                 HashSet<String> visited = new HashSet<>();                 while (queue.size() > 0) {             Counter curr = queue.poll();             String currS = curr.s;             int currCount = curr.count;                         if (visited.contains(currS)) {                 continue;             }             visited.a

Link to the problem: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=1517 The solution below used Backtracking to solve this problem. import java.io.*; import java.util.*; class Main {     public int s;     public int d;     public int maxSurplus;     public int[] register;         public void rec(int month, int surplus, int lastFive) {         if (month >= 5) {             if (lastFive >= 0) {                 return;             }         }         if (month == 12) {             maxSurplus = Math.max(maxSurplus, surplus);             return;         }                         register[month] = s;         rec(month+1, surplus+s, lastFive + s - (month >= 5 ? register[month-5] : 0));         register[month] = d;         rec(month+1, surplus+d, lastFive + d - (month >= 5 ? register[month-5] : 0));     }         public void process() throws NumberFormatException, IOException {         Scanner sc = n

Link to the problem: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=2933 Given a start position, the problem asks us to find the minimum total toll cost for the vehicle to reach the destination city. For this reason, the code below used Dijkstra's algorithm to find the solution. import java.io.*; import java.util.*; class Main {     public ArrayList<ArrayList<Edge>> adjList;     public int citiesServiceRoute;         public int dijkstra(int start, int end) {         Queue<Edge> queue = new PriorityQueue<>();         queue.add(new Edge(start, 0));                 HashSet<Integer> visited = new HashSet<>();                 while (queue.size() > 0) {             Edge curr = queue.poll();             int currCity = curr.city;             int currCost = curr.cost;                         if (visited.contains(currCity)) {                 continue;             }        

import java.io.*; import java.util.*; import java.text.*; import java.math.*; import java.util.regex.*; public class Solution {     public static int sizeSeqA;     public static int sizeSeqB;     public static int[] seqA;     public static int[] seqB;     public static int[][] memo;             public static int lcs(int indexA, int indexB) {         if (indexA == sizeSeqA || indexB == sizeSeqB) {             return 0;         }                    if (memo[indexA][indexB] != -1) {             return memo[indexA][indexB];         }                 int nextA = lcs(indexA+1, indexB);         int nextB = lcs(indexA, indexB+1);         int nextBoth = lcs(indexA+1, indexB+1) + ((seqA[indexA] == seqB[indexB]) ? 1 : 0);                 memo[indexA][indexB] = Math.max(nextA, Math.max(nextB, nextBoth));         return memo[indexA][indexB];     }     public static void main(String[] args) {         Scanner sc = new Scanner(System.in);                 sizeSeqA = sc.nextInt();         sizeSeqB = sc.

Link to the problem: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=3649 If you want to see another solution for this problem, click here . This solution used Prim's algorithm to solve this problem. import java.io.*; import java.util.*; class Main {     public ArrayList<ArrayList<Edge>> adjList;     public Queue<Edge> edges;         public void prim(int start, int numCities) {         Queue<Edge> queue = new PriorityQueue<>();         queue.add(new Edge(start, 0, -1));                 HashSet<Integer> visited = new HashSet<>();                 while (queue.size() > 0) {             Edge curr = queue.poll();             int currCity = curr.city;             int currCost = curr.cost;             int currParent = curr.parent;                         if (visited.contains(currCity)) {                 continue;             }             visited.add(currCity);  

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