Problemas de Programação

If you want to see another solution for this problem, click here . In order to solve this problem, I used Prim's algorithm. While reading the edges, I store them in an adjacency list. Then, I call the Prim method, which choose the next edge to be examined according to its cost. import java.io.*; import java.util.*; import java.text.DecimalFormat; class Main  {     public static HashMap<Integer, ArrayList<Edge>> adjList;     public static Comparator<Edge> costComparator = new Comparator<Edge>() {         public int compare(Edge e1, Edge e2) {             if ((e1.cost - e2.cost) < 0) {                 return -1;             }             else if ((e1.cost - e2.cost) > 0) {                 return 1;             }                         return 0;         }     };         public static ArrayList<Points> prim(int start, int numPoints) {         Queue<Edge> queue = new PriorityQueue<Edge>(numPoints, costComparator);         Edge e = ne

In order to solve this problem, I used Kruskal's algorithm. After reading the edges, I sort them accordingly with the cost of each edge. Then, I group them with the Union-Find method. import java.io.*; import java.util.*; class Main  {     public static ArrayList<EdgeWithCost> edges;     public static int[] nodeParent;     public static int[] depth;     public static int count;         public static int root(int n) {         int currNode = n;         while (nodeParent[currNode] != currNode) {             currNode = nodeParent[currNode];         }                 return currNode;     }         public static 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;                 }             }  

If you want to see other solutions for this problem, click here and here . This solution is using Prim's algorithm. This solution is almost the same as the previous one using Prim. The difference here is that I am calculating the distance between two points inside the Prim method. Then, I do not need to have an adjacency list, and I also do not need to keep a list with the distances. import java.io.*; import java.util.*; import java.text.DecimalFormat; class Main  {     public static HashMap<Integer, Coord> map;     public static Comparator<Edge> weightCompare = new Comparator<Edge>() {         public int compare(Edge e1, Edge e2) {             if ((e1.weight - e2.weight) < 0) {                 return -1;             }             else if ((e1.weight - e2.weight) > 0) {                 return 1;             }                         return 0;         }     };         public static double prim(int start, int end, int numStones) {         Queue<Edge

If you want to see another solution for this problem, click here . This solution is using Prim 's algorithm. The initial steps are the same used in the previous solution. The difference begins after sorting the array with the distances. Here, instead of calling the union-find method to connect each stone, I prepare an adjacency list and call the Prim method. In this method, I use almost the same approach used for Dijkstra, but instead of considering the weight of my current vertex plus the weight of all the other vertexes that I have already visited, I consider only the weight of my current vertex. import java.io.*; import java.util.*; import java.text.DecimalFormat; class Main  {     public static ArrayList<Distance> distances;     public static HashMap<Integer, Coord> map;     public static HashMap<Integer, ArrayList<Edge>> adjList;     public static Comparator<Edge> weightCompare = new Comparator<Edge>() {         public int compare(Ed

This solution uses Kruskal's algorithm. First, I read the coordinate of each stone, and I map them to an index. Then, I get the distance from each node to every other node (without repetitions). Finally, with the distances sorted, I use the union-find method to connect two stones. It is important to understand that I always try to connect every two unconnected stones which has the smallest distance. Moreover, if two stones are already connected, I do not need to connect them because it would create a cycle. My condition to stop is if the stone where Freddy is has a connection with the stone where Fiona is. import java.io.*; import java.util.*; import java.text.DecimalFormat; class Main  {     public static ArrayList<Distance> distances;     public static HashMap<Integer, Coord> map;     public static int[] nodeParent;     public static int[] depth;         public static int root(int n) {         int currN = n;         while (nodeParent[currN] != currN) {     

I used Depth-First Search to solve this problem. import java.io.*; import java.util.*; class Main {     public static char[][] matrix;     public static boolean[][] visited;     public static int[] vx = {-1,-1,-1,0,0,1,1,1};     public static int[] vy = {-1,0,1,-1,1,-1,0,1};     public static int count;     public static int row;     public static int col;         public static void dfs(int currX, int currY) {         if (currX < 0 || currY < 0 || currX >= row || currY >= col || matrix[currX][currY] != '*' || visited[currX][currY]) {             return;         }                 count++;         visited[currX][currY] = true;         for (int i = 0; i < 8; i++) {             int nextX = currX+vx[i];             int nextY = currY+vy[i];             dfs(nextX, nextY);         }     }         public static void process() throws NumberFormatException, IOException {         BufferedReader br = new BufferedReader(new InputStreamReader(System.in));                 Str

For this problem, I used Dijkstra's algorithm. Moreover, I also used a matrix and an adjacency list. The first one was necessary to keep the cost (hours) to send a message from a specific city to another one. The second structure was used to keep all the reachable cities in order to avoid iterating over an entire row of the matrix to acquire this information. import java.io.*; import java.util.*; class Main  {     public static HashMap<Integer, ArrayList<Element>> adjList;     public static int[][] matrix;        public static Comparator<Element> hoursComparator = new Comparator<Element>() {         public int compare(Element e1, Element e2) {             return (int) (e1.hours - e2.hours);         }     };        public static int dijkstra(int cityStart, int cityEnd, int numCities) {         Queue<Element> queue = new PriorityQueue<Element>(numCities, hoursComparator);         Element e = new Element(cityStart, 0);         queue.add(e);

In order to solve this problem, I used Dijkstra's algorithm. Inside the Dijkstra method, I used a PriorityQueue to order the edges, which are weighted. However, once the PriorityQueue contains the data type Element, which has three variables, I had to implement a Comparator to order the queue according to the weight. import java.io.*; import java.util.*; class Main  {      public static int[][] maze;     public static int[][] addedToQueue;     public static int[] vi = {-1,1,0,0};     public static int[] vj = {0,0,-1,1};         public static Comparator<Element> priceComparator = new Comparator<Element>(){                  public int compare(Element e1, Element e2) {             return (int) (e1.price - e2.price);         }     };         public static int dijkstra(int rowStart, int colStart, int rowEnd, int colEnd, int numRows, int numCols) {         Queue<Element> queue = new PriorityQueue<Element>(numRows*numCols, priceComparator);         Elem

import java.io.*; import java.util.*; class friday {     public static int[] weekDays = new int[8];     public static int[] monthLength = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};         public static int month(int weekDay, int numDays) {         for (int i = 1; i <= numDays; i++) {             if (i == 13) {                 weekDays[weekDay] += 1;                }             weekDay++;             if (weekDay == 8) {                 weekDay = 1;             }         }                 return weekDay;     }         public static boolean isLeapYear(int year) {         boolean leapYear = false;         if (year%100 == 0) { // century             if (year%400 == 0) {                 leapYear = true;             }         }         else {             if (year%4 == 0) {                 leapYear = true;             }         }                 return leapYear;     }         public static void main (String [] args) throws IOException {         BufferedReader f = new BufferedRea

import java.io.*; import java.util.*; class gift1 {     public static void main (String [] args) throws IOException {         BufferedReader f = new BufferedReader(new FileReader("gift1.in"));                                                                                                             PrintWriter out = new PrintWriter(new BufferedWriter(new FileWriter("gift1.out")));                 int numFriends = Integer.parseInt(f.readLine());         HashMap<String, Integer> friends = new HashMap<String, Integer>();         String[] names = new String[numFriends];         for (int i = 0; i < numFriends; i++) {             String name = f.readLine();             names[i] = name;             friends.put(name, 0);         }                 for (int i = 0; i < numFriends; i++) {             String name = f.readLine();             String line = f.readLine();             StringTokenizer st = new StringTokenizer(line);             int money = Integer.p