Skip to content

Instantly share code, notes, and snippets.

@so77id

so77id/01-circular-game.java

Last active July 6, 2021 21:51
Show Gist options
  • Save so77id/bfdc190256743b2c421032cea49fe45f to your computer and use it in GitHub Desktop.
Save so77id/bfdc190256743b2c421032cea49fe45f to your computer and use it in GitHub Desktop.
Download ZIP
Raw
01-circular-game.java
import java.io.*;
import java.math.*;
import java.security.*;
import java.text.*;
import java.util.*;
import java.util.concurrent.*;
import java.util.function.*;
import java.util.regex.*;
import java.util.stream.*;
import static java.util.stream.Collectors.joining;
import static java.util.stream.Collectors.toList;
class Result {
/*
* Complete the 'getWinner' function below.
*
* The function is expected to return an INTEGER.
* The function accepts following parameters:
* 1. INTEGER n
* 2. INTEGER k
*/
public static int getWinner(int n, int k) {
// Write your code here
Queue<Integer> q = new LinkedList<>();
for(int i = 0; i < n; i++){
q.add(i+1);
}
while(q.size() > 1) {
for(int i = 1; i<k; i++) {
int tmp = q.poll();
q.add(tmp);
}
q.poll();
}
return q.poll();
}
}
public class Solution {
public static void main(String[] args) throws IOException {
BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bufferedWriter = new BufferedWriter(new OutputStreamWriter(System.out));
int n = Integer.parseInt(bufferedReader.readLine().trim());
int k = Integer.parseInt(bufferedReader.readLine().trim());
int winner = Result.getWinner(n, k);
bufferedWriter.write(String.valueOf(winner));
bufferedWriter.newLine();
bufferedReader.close();
bufferedWriter.close();
}
}
Raw
02-el-secuestrador.java
import java.io.*;
import java.util.*;
public class Solution {
public static boolean solve(String[] revista, String[] carta){
HashMap<String, Integer> revistaMap = new HashMap<>();
for (String currentWord: revista) {
if (revistaMap.containsKey(currentWord)) {
revistaMap.put(currentWord, revistaMap.get(currentWord) + 1);
} else {
revistaMap.put(currentWord, 1);
}
}
HashMap<String, Integer> cartaMap = new HashMap<>();
for (String currentWord: carta) {
if (cartaMap.containsKey(currentWord)) {
cartaMap.put(currentWord, cartaMap.get(currentWord) + 1);
} else {
cartaMap.put(currentWord, 1);
}
}
for (String key: cartaMap.keySet()){
if (!revistaMap.containsKey(key)){
return false;
}
if (cartaMap.get(key) > revistaMap.get(key)){
return false;
}
}
return true;
}
public static final Scanner sc = new Scanner(System.in);
public static void main(String[] args) {
int T = sc.nextInt();
while(T-- >0) {
int N = sc.nextInt();
int M = sc.nextInt();
String[] revista = new String[N];
for (int i = 0; i < N; i++) {
revista[i] = sc.next();
}
String[] carta = new String[M];
for (int i = 0; i < M; i++) {
carta[i] = sc.next();
}
if (solve(revista, carta)) {
System.out.println("Si");
} else {
System.out.println("No");
}
}
}
}
Raw
03-variante-z.java
import java.io.*;
import java.util.*;
import java.util.stream.*;
import static java.util.stream.Collectors.toList;
class IndexMinPQ<Key extends Comparable<Key>> implements Iterable<Integer> {
private int maxN; // maximum number of elements on PQ
private int n; // number of elements on PQ
private int[] pq; // binary heap using 1-based indexing
private int[] qp; // inverse of pq - qp[pq[i]] = pq[qp[i]] = i
private Key[] keys; // keys[i] = priority of i
/**
* Initializes an empty indexed priority queue with indices between {@code 0}
* and {@code maxN - 1}.
* @param maxN the keys on this priority queue are index from {@code 0}
* {@code maxN - 1}
* @throws IllegalArgumentException if {@code maxN < 0}
*/
public IndexMinPQ(int maxN) {
this.maxN = maxN;
n = 0;
keys = (Key[]) new Comparable[maxN + 1]; // make this of length maxN??
pq = new int[maxN + 1];
qp = new int[maxN + 1]; // make this of length maxN??
for (int i = 0; i <= maxN; i++)
qp[i] = -1;
}
/**
* Returns true if this priority queue is empty.
*
* @return {@code true} if this priority queue is empty;
* {@code false} otherwise
*/
public boolean isEmpty() {
return n == 0;
}
/**
* Is {@code i} an index on this priority queue?
*
* @param i an index
* @return {@code true} if {@code i} is an index on this priority queue;
* {@code false} otherwise
* @throws IllegalArgumentException unless {@code 0 <= i < maxN}
*/
public boolean contains(int i) {
return qp[i] != -1;
}
/**
* Returns the number of keys on this priority queue.
*
* @return the number of keys on this priority queue
*/
public int size() {
return n;
}
/**
* Associates key with index {@code i}.
*
* @param i an index
* @param key the key to associate with index {@code i}
* @throws IllegalArgumentException unless {@code 0 <= i < maxN}
* @throws IllegalArgumentException if there already is an item associated
* with index {@code i}
*/
public void insert(int i, Key key) {
n++;
qp[i] = n;
pq[n] = i;
keys[i] = key;
swim(n);
}
/**
* Returns an index associated with a minimum key.
*
* @return an index associated with a minimum key
* @throws NoSuchElementException if this priority queue is empty
*/
public int minIndex() {
return pq[1];
}
/**
* Returns a minimum key.
*
* @return a minimum key
* @throws NoSuchElementException if this priority queue is empty
*/
public Key minKey() {
return keys[pq[1]];
}
/**
* Removes a minimum key and returns its associated index.
* @return an index associated with a minimum key
* @throws NoSuchElementException if this priority queue is empty
*/
public int delMin() {
int min = pq[1];
exch(1, n--);
sink(1);
qp[min] = -1; // delete
keys[min] = null; // to help with garbage collection
pq[n+1] = -1; // not needed
return min;
}
/**
* Returns the key associated with index {@code i}.
*
* @param i the index of the key to return
* @return the key associated with index {@code i}
* @throws IllegalArgumentException unless {@code 0 <= i < maxN}
* @throws NoSuchElementException no key is associated with index {@code i}
*/
public Key keyOf(int i) {
return keys[i];
}
/**
* Change the key associated with index {@code i} to the specified value.
*
* @param i the index of the key to change
* @param key change the key associated with index {@code i} to this key
* @throws IllegalArgumentException unless {@code 0 <= i < maxN}
* @throws NoSuchElementException no key is associated with index {@code i}
*/
public void changeKey(int i, Key key) {
keys[i] = key;
swim(qp[i]);
sink(qp[i]);
}
/**
* Change the key associated with index {@code i} to the specified value.
*
* @param i the index of the key to change
* @param key change the key associated with index {@code i} to this key
* @throws IllegalArgumentException unless {@code 0 <= i < maxN}
* @deprecated Replaced by {@code changeKey(int, Key)}.
*/
@Deprecated
public void change(int i, Key key) {
changeKey(i, key);
}
/**
* Decrease the key associated with index {@code i} to the specified value.
*
* @param i the index of the key to decrease
* @param key decrease the key associated with index {@code i} to this key
* @throws IllegalArgumentException unless {@code 0 <= i < maxN}
* @throws IllegalArgumentException if {@code key >= keyOf(i)}
* @throws NoSuchElementException no key is associated with index {@code i}
*/
public void decreaseKey(int i, Key key) {
keys[i] = key;
swim(qp[i]);
}
/**
* Increase the key associated with index {@code i} to the specified value.
*
* @param i the index of the key to increase
* @param key increase the key associated with index {@code i} to this key
* @throws IllegalArgumentException unless {@code 0 <= i < maxN}
* @throws IllegalArgumentException if {@code key <= keyOf(i)}
* @throws NoSuchElementException no key is associated with index {@code i}
*/
public void increaseKey(int i, Key key) {
keys[i] = key;
sink(qp[i]);
}
/**
* Remove the key associated with index {@code i}.
*
* @param i the index of the key to remove
* @throws IllegalArgumentException unless {@code 0 <= i < maxN}
* @throws NoSuchElementException no key is associated with index {@code i}
*/
public void delete(int i) {
int index = qp[i];
exch(index, n--);
swim(index);
sink(index);
keys[i] = null;
qp[i] = -1;
}
/***************************************************************************
* General helper functions.
***************************************************************************/
private boolean greater(int i, int j) {
return keys[pq[i]].compareTo(keys[pq[j]]) > 0;
}
private void exch(int i, int j) {
int swap = pq[i];
pq[i] = pq[j];
pq[j] = swap;
qp[pq[i]] = i;
qp[pq[j]] = j;
}
/***************************************************************************
* Heap helper functions.
***************************************************************************/
private void swim(int k) {
while (k > 1 && greater(k/2, k)) {
exch(k, k/2);
k = k/2;
}
}
private void sink(int k) {
while (2*k <= n) {
int j = 2*k;
if (j < n && greater(j, j+1)) j++;
if (!greater(k, j)) break;
exch(k, j);
k = j;
}
}
/***************************************************************************
* Iterators.
***************************************************************************/
/**
* Returns an iterator that iterates over the keys on the
* priority queue in ascending order.
* The iterator doesn't implement {@code remove()} since it's optional.
*
* @return an iterator that iterates over the keys in ascending order
*/
public Iterator<Integer> iterator() { return new HeapIterator(); }
private class HeapIterator implements Iterator<Integer> {
// create a new pq
private IndexMinPQ<Key> copy;
// add all elements to copy of heap
// takes linear time since already in heap order so no keys move
public HeapIterator() {
copy = new IndexMinPQ<Key>(pq.length - 1);
for (int i = 1; i <= n; i++)
copy.insert(pq[i], keys[pq[i]]);
}
public boolean hasNext() { return !copy.isEmpty(); }
public void remove() { throw new UnsupportedOperationException(); }
public Integer next() {
if (!hasNext()) throw new NoSuchElementException();
return copy.delMin();
}
}
}
class DirectedEdge {
private final int v;
private final int w;
private final double weight;
/**
* Initializes a directed edge from vertex {@code v} to vertex {@code w} with
* the given {@code weight}.
* @param v the tail vertex
* @param w the head vertex
* @param weight the weight of the directed edge
* @throws IllegalArgumentException if either {@code v} or {@code w}
* is a negative integer
* @throws IllegalArgumentException if {@code weight} is {@code NaN}
*/
public DirectedEdge(int v, int w, double weight) {
this.v = v;
this.w = w;
this.weight = weight;
}
/**
* Returns the tail vertex of the directed edge.
* @return the tail vertex of the directed edge
*/
public int from() {
return v;
}
/**
* Returns the head vertex of the directed edge.
* @return the head vertex of the directed edge
*/
public int to() {
return w;
}
/**
* Returns the weight of the directed edge.
* @return the weight of the directed edge
*/
public double weight() {
return weight;
}
/**
* Returns a string representation of the directed edge.
* @return a string representation of the directed edge
*/
public String toString() {
return v + "->" + w + " " + String.format("%5.2f", weight);
}
}
class Bag<Item> implements Iterable<Item> {
private Node<Item> first; // beginning of bag
private int n; // number of elements in bag
// helper linked list class
private static class Node<Item> {
private Item item;
private Node<Item> next;
}
/**
* Initializes an empty bag.
*/
public Bag() {
first = null;
n = 0;
}
/**
* Returns true if this bag is empty.
*
* @return {@code true} if this bag is empty;
* {@code false} otherwise
*/
public boolean isEmpty() {
return first == null;
}
/**
* Returns the number of items in this bag.
*
* @return the number of items in this bag
*/
public int size() {
return n;
}
/**
* Adds the item to this bag.
*
* @param item the item to add to this bag
*/
public void add(Item item) {
Node<Item> oldfirst = first;
first = new Node<Item>();
first.item = item;
first.next = oldfirst;
n++;
}
/**
* Returns an iterator that iterates over the items in this bag in arbitrary order.
*
* @return an iterator that iterates over the items in this bag in arbitrary order
*/
public Iterator<Item> iterator() {
return new LinkedIterator(first);
}
// an iterator, doesn't implement remove() since it's optional
private class LinkedIterator implements Iterator<Item> {
private Node<Item> current;
public LinkedIterator(Node<Item> first) {
current = first;
}
public boolean hasNext() { return current != null; }
public void remove() { throw new UnsupportedOperationException(); }
public Item next() {
if (!hasNext()) throw new NoSuchElementException();
Item item = current.item;
current = current.next;
return item;
}
}
}
class EdgeWeightedDigraph {
private static final String NEWLINE = System.getProperty("line.separator");
private final int V; // number of vertices in this digraph
private int E; // number of edges in this digraph
private Bag<DirectedEdge>[] adj; // adj[v] = adjacency list for vertex v
/**
* Initializes an empty edge-weighted digraph with {@code V} vertices and 0 edges.
*
* @param V the number of vertices
* @throws IllegalArgumentException if {@code V < 0}
*/
public EdgeWeightedDigraph(int V) {
this.V = V;
this.E = 0;
adj = (Bag<DirectedEdge>[]) new Bag[V];
for (int v = 0; v < V; v++)
adj[v] = new Bag<DirectedEdge>();
}
/**
* Returns the number of vertices in this edge-weighted digraph.
*
* @return the number of vertices in this edge-weighted digraph
*/
public int V() {
return V;
}
/**
* Returns the number of edges in this edge-weighted digraph.
*
* @return the number of edges in this edge-weighted digraph
*/
public int E() {
return E;
}
/**
* Adds the directed edge {@code e} to this edge-weighted digraph.
*
* @param e the edge
* @throws IllegalArgumentException unless endpoints of edge are between {@code 0}
* and {@code V-1}
*/
public void addEdge(DirectedEdge e) {
int v = e.from();
int w = e.to();
adj[v].add(e);
E++;
}
/**
* Returns the directed edges incident from vertex {@code v}.
*
* @param v the vertex
* @return the directed edges incident from vertex {@code v} as an Iterable
* @throws IllegalArgumentException unless {@code 0 <= v < V}
*/
public Iterable<DirectedEdge> adj(int v) {
return adj[v];
}
/**
* Returns all directed edges in this edge-weighted digraph.
* To iterate over the edges in this edge-weighted digraph, use foreach notation:
* {@code for (DirectedEdge e : G.edges())}.
*
* @return all edges in this edge-weighted digraph, as an iterable
*/
public Iterable<DirectedEdge> edges() {
Bag<DirectedEdge> list = new Bag<DirectedEdge>();
for (int v = 0; v < V; v++) {
for (DirectedEdge e : adj(v)) {
list.add(e);
}
}
return list;
}
/**
* Returns a string representation of this edge-weighted digraph.
*
* @return the number of vertices <em>V</em>, followed by the number of edges <em>E</em>,
* followed by the <em>V</em> adjacency lists of edges
*/
public String toString() {
StringBuilder s = new StringBuilder();
s.append(V + " " + E + NEWLINE);
for (int v = 0; v < V; v++) {
s.append(v + ": ");
for (DirectedEdge e : adj[v]) {
s.append(e + " ");
}
s.append(NEWLINE);
}
return s.toString();
}
}
class DijkstraSP {
private double[] distTo; // distTo[v] = distance of shortest s->v path
private DirectedEdge[] edgeTo; // edgeTo[v] = last edge on shortest s->v path
private IndexMinPQ<Double> pq; // priority queue of vertices
/**
* Computes a shortest-paths tree from the source vertex {@code s} to every other
* vertex in the edge-weighted digraph {@code G}.
*
* @param G the edge-weighted digraph
* @param s the source vertex
* @throws IllegalArgumentException if an edge weight is negative
* @throws IllegalArgumentException unless {@code 0 <= s < V}
*/
public DijkstraSP(EdgeWeightedDigraph G, int s) {
distTo = new double[G.V()];
edgeTo = new DirectedEdge[G.V()];
for (int v = 0; v < G.V(); v++)
distTo[v] = Double.POSITIVE_INFINITY;
distTo[s] = 0.0;
// relax vertices in order of distance from s
pq = new IndexMinPQ<Double>(G.V());
pq.insert(s, distTo[s]);
while (!pq.isEmpty()) {
int v = pq.delMin();
for (DirectedEdge e : G.adj(v))
relax(e);
}
}
// relax edge e and update pq if changed
private void relax(DirectedEdge e) {
int v = e.from(), w = e.to();
if (distTo[w] > distTo[v] + e.weight()) {
distTo[w] = distTo[v] + e.weight();
edgeTo[w] = e;
if (pq.contains(w)) pq.decreaseKey(w, distTo[w]);
else pq.insert(w, distTo[w]);
}
}
/**
* Returns the length of a shortest path from the source vertex {@code s} to vertex {@code v}.
* @param v the destination vertex
* @return the length of a shortest path from the source vertex {@code s} to vertex {@code v};
* {@code Double.POSITIVE_INFINITY} if no such path
* @throws IllegalArgumentException unless {@code 0 <= v < V}
*/
public double distTo(int v) {
return distTo[v];
}
/**
* Returns true if there is a path from the source vertex {@code s} to vertex {@code v}.
*
* @param v the destination vertex
* @return {@code true} if there is a path from the source vertex
* {@code s} to vertex {@code v}; {@code false} otherwise
* @throws IllegalArgumentException unless {@code 0 <= v < V}
*/
public boolean hasPathTo(int v) {
return distTo[v] < Double.POSITIVE_INFINITY;
}
/**
* Returns a shortest path from the source vertex {@code s} to vertex {@code v}.
*
* @param v the destination vertex
* @return a shortest path from the source vertex {@code s} to vertex {@code v}
* as an iterable of edges, and {@code null} if no such path
* @throws IllegalArgumentException unless {@code 0 <= v < V}
*/
public Iterable<DirectedEdge> pathTo(int v) {
if (!hasPathTo(v)) return null;
Stack<DirectedEdge> path = new Stack<DirectedEdge>();
for (DirectedEdge e = edgeTo[v]; e != null; e = edgeTo[e.from()]) {
path.push(e);
}
return path;
}
}
class Result {
/*
* Complete the 'calcularTiempo' function below.
*
* The function is expected to return an INTEGER.
* The function accepts following parameters:
* 1. INTEGER pN
* 2. INTEGER pM
* 3. INTEGER pC
* 4. INTEGER pV
* 5. INTEGER_ARRAY pCiudadesC
* 6. 2D_INTEGER_ARRAY pRutas
* 7. INTEGER pS
* 8. INTEGER pT
*/
public static int calcularTiempo(int pN, int pM, int pC, int pV, List<Integer> pCiudadesC, List<List<Integer>> pRutas, int pS, int pT) {
// Write your code here
EdgeWeightedDigraph G = new EdgeWeightedDigraph(pN);
for (int m=0; m<pM; m++) {
G.addEdge(new DirectedEdge(pRutas.get(m).get(0)-1, pRutas.get(m).get(1)-1, pRutas.get(m).get(2)));
G.addEdge(new DirectedEdge(pRutas.get(m).get(1)-1, pRutas.get(m).get(0)-1, pRutas.get(m).get(2)));
}
DijkstraSP SSSPs = new DijkstraSP(G, pS-1);
DijkstraSP SSSPt = new DijkstraSP(G, pT-1);
int res = -1;
for (int c=0; c<pC; c++) {
int d2 = (int) SSSPt.distTo(pCiudadesC.get(c)-1);
if (d2<=pV && SSSPs.hasPathTo(pCiudadesC.get(c)-1)) {
int d1 = (int) SSSPs.distTo(pCiudadesC.get(c)-1);
if (res<0 || d1+d2 < res) {
res = d1+d2;
}
}
}
return res;
}
}
public class Solution {
public static void main(String[] args) throws IOException {
BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bufferedWriter = new BufferedWriter(new OutputStreamWriter(System.out));
String[] firstMultipleInput = bufferedReader.readLine().replaceAll("\\s+$", "").split(" ");
int n = Integer.parseInt(firstMultipleInput[0]);
int m = Integer.parseInt(firstMultipleInput[1]);
int c = Integer.parseInt(firstMultipleInput[2]);
int v = Integer.parseInt(firstMultipleInput[3]);
List<Integer> ciudadesC = Stream.of(bufferedReader.readLine().replaceAll("\\s+$", "").split(" "))
.map(Integer::parseInt)
.collect(toList());
List<List<Integer>> rutas = new ArrayList<>();
IntStream.range(0, m).forEach(i -> {
try {
rutas.add(
Stream.of(bufferedReader.readLine().replaceAll("\\s+$", "").split(" "))
.map(Integer::parseInt)
.collect(toList())
);
} catch (IOException ex) {
throw new RuntimeException(ex);
}
});
String[] secondMultipleInput = bufferedReader.readLine().replaceAll("\\s+$", "").split(" ");
int s = Integer.parseInt(secondMultipleInput[0]);
int t = Integer.parseInt(secondMultipleInput[1]);
int tiempoMinimo = Result.calcularTiempo(n, m, c, v, ciudadesC, rutas, s, t);
bufferedWriter.write(String.valueOf(tiempoMinimo));
bufferedWriter.newLine();
bufferedReader.close();
bufferedWriter.close();
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment