fork download
copy 
  1. import java.io.Writer;
  2. import java.io.BufferedWriter;
  3. import java.io.OutputStreamWriter;
  4. import java.io.OutputStream;
  5. import java.io.PrintWriter;
  6. import java.io.IOException;
  7. import java.io.InputStream;
  8. import java.math.BigInteger;
  9. import java.util.Arrays;
  10. import java.util.ArrayList;
  11. import java.util.InputMismatchException;
  12. import java.util.*;
  13. import java.io.*;
  14. import java.math.*;
  15. import java.util.concurrent.TimeUnit;
  16.  
  17. class Main{
  18.   static class pair{
  19.     int end;
  20.     long weight;
  21.     pair(int a, long b){
  22.       end=a;
  23.       weight=b;
  24.     }
  25.     public String toString(){
  26.       return "(end: "+end+" weight: "+weight+")";
  27.     }
  28.     // public int compareTo(pair p){
  29.     //   if(weight==p.weight) return Integer.compare(end, p.end);
  30.     //   return Long.compare(weight, p.weight);
  31.     // }
  32.   }
  33.  
  34.   static class edge implements Comparable<edge>{
  35.     int start, end;
  36.     long weight;
  37.     edge(int a, int b, long c){
  38.       start=a;
  39.       end=b;
  40.       weight=c;
  41.     }
  42.     public int compareTo(edge e){
  43.        return Integer.compare(start, e.start);
  44.     }
  45.   }
  46.   static void dj(ArrayList<ArrayList<pair>> graph, int start, int k, long [][] dis){
  47.  
  48.     ArrayDeque<pair> dq= new ArrayDeque<>();
  49.     dq.addLast(new pair(start, 0));
  50.     // Arrays.fill(dis[start], 0);
  51.     while(!dq.isEmpty()){
  52.       pair temp= dq.poll();
  53.       start=temp.end;
  54.       // System.out.printf("temp.end: %d\t \n", start);
  55.       if(temp.weight>dis[start][k-1])continue;
  56.       for(pair p: graph.get(start)){
  57.         int end=p.end; long weight= p.weight;
  58.         // System.out.println("start: "+start+"\tend: "+p.end);
  59.         if(dis[end][k-1]>temp.weight+weight){
  60.           dis[end][k-1]=temp.weight+weight;
  61.           dq.addFirst(new pair(end, dis[end][k-1]));
  62.           Arrays.sort(dis[end]);
  63.         }
  64.       }
  65.     }
  66.     // return dis[graph.size()-1];
  67.   }
  68.   static class ProblemSolver{
  69.     public void solveTheProblem(InputReader in,OutputWriter out, NumberTheory nt, Debug dbg){
  70.       int test=1;//in.nextInt();
  71.       while(test-- >0){
  72.         int n, m;
  73.         n=in.nextInt();
  74.         m=in.nextInt();
  75.         int k=in.nextInt();
  76.         long dis[][]= new long[n+1][k];
  77.         // for(int i=2;i<graph.size();i++) Arrays.fill(dis[i],  Long.MAX_VALUE);
  78.         for(long i[]: dis)
  79.         dis[1][0]=0;
  80.         // ArrayList<edge> graph=new ArrayList<>();
  81.         ArrayList<ArrayList<pair>> graph=new ArrayList<>();
  82.         for(int i=0;i<=n;i++) {
  83.           graph.add(new ArrayList<>());
  84.           Arrays.fill(dis[i], Long.MAX_VALUE);
  85.         }
  86.         for(int i=0;i<m;i++){
  87.           int a=in.nextInt();
  88.           int b=in.nextInt();
  89.           long c=in.nextLong();
  90.           // graph.add(new edge(a, b, c));
  91.           graph.get(a).add(new pair(b, c));
  92.         }
  93.         // Collections.sort(graph);
  94.         // for(edge e: graph){
  95.           // System.out.printf("start: %d end: %d weight: %d\t \n", e.start, e.end, e.weight);
  96.         // }
  97.          dj(graph, 1, k, dis);
  98.         for(int i=0;i<k;++i) out.print(dis[n][i]+" ");
  99.       }
  100.     }
  101.   }
  102.  
  103.   public static void main(String[] args){
  104.     int checkTimeELAPSED=0;
  105.     if(checkTimeELAPSED==0){
  106.       InputStream inputStream=System.in;
  107.       OutputStream outputStream=System.out;
  108.       Debug debug= new Debug();
  109.       InputReader in=new InputReader(inputStream);
  110.       OutputWriter out=new OutputWriter(outputStream);
  111.       NumberTheory nt= new NumberTheory();
  112.       ProblemSolver problemSolver=new ProblemSolver();
  113.       problemSolver.solveTheProblem(in,out, nt, debug);
  114.       out.flush();
  115.       out.close();
  116.     }
  117.     else{
  118.       long startTime = System.nanoTime();
  119.       InputStream inputStream=System.in;
  120.       OutputStream outputStream=System.out;
  121.       Debug debug= new Debug();
  122.       InputReader in=new InputReader(inputStream);
  123.       OutputWriter out=new OutputWriter(outputStream);
  124.       NumberTheory nt= new NumberTheory();
  125.       ProblemSolver problemSolver=new ProblemSolver();
  126.       problemSolver.solveTheProblem(in,out,nt,debug);
  127.       long endTime = System.nanoTime();
  128.       long timeElapsed = endTime - startTime;
  129.       out.println("Execution time in nanoseconds  : " + timeElapsed);
  130.   		out.println("Execution time in milliseconds : "+ timeElapsed / 1000000);
  131.       out.println("Execution time in seconds : "+ timeElapsed / 1000000000);
  132.       out.flush();
  133.       out.close();
  134.     }
  135.   }
  136.   @SuppressWarnings({"unchecked", "static-access", "all", "StaticQualifiedUsingExpression"})
  137.   static class Debug {
  138. 	//change to System.getProperty("ONLINE_JUDGE")==null; for CodeForces
  139.   	public static final boolean LOCAL = System.getProperty("user.home").toString().equals("C:\\Users\\Hp");
  140.   	private static <T> String ts(T t) {
  141.   		if(t==null) {
  142.   			return "null";
  143.   		}
  144.   		try {
  145.   			return ts((Iterable) t);
  146.   		}catch(ClassCastException e) {
  147.   			if(t instanceof int[]) {
  148.   				String s = Arrays.toString((int[]) t);
  149.   				return "{"+s.substring(1, s.length()-1)+"}";
  150.   			}else if(t instanceof long[]) {
  151.   				String s = Arrays.toString((long[]) t);
  152.   				return "{"+s.substring(1, s.length()-1)+"}";
  153.   			}else if(t instanceof char[]) {
  154.   				String s = Arrays.toString((char[]) t);
  155.   				return "{"+s.substring(1, s.length()-1)+"}";
  156.   			}else if(t instanceof double[]) {
  157.   				String s = Arrays.toString((double[]) t);
  158.   				return "{"+s.substring(1, s.length()-1)+"}";
  159.   			}else if(t instanceof boolean[]) {
  160.   				String s = Arrays.toString((boolean[]) t);
  161.   				return "{"+s.substring(1, s.length()-1)+"}";
  162.   			}
  163.   			try {
  164.   				return ts((Object[]) t);
  165.   			}catch(ClassCastException e1) {
  166.   				return t.toString();
  167.   			}
  168.   		}
  169.   	}
  170.   	private static <T> String ts(T[] arr) {
  171.   		StringBuilder ret = new StringBuilder();
  172.   		ret.append("{");
  173.   		boolean first = true;
  174.   		for(T t: arr) {
  175.   			if(!first) {
  176.   				ret.append(", ");
  177.   			}
  178.   			first = false;
  179.   			ret.append(ts(t));
  180.   		}
  181.   		ret.append("}");
  182.   		return ret.toString();
  183.   	}
  184.   	private static <T> String ts(Iterable<T> iter) {
  185.   		StringBuilder ret = new StringBuilder();
  186.   		ret.append("{");
  187.   		boolean first = true;
  188.   		for(T t: iter) {
  189.   			if(!first) {
  190.   				ret.append(", ");
  191.   			}
  192.   			first = false;
  193.   			ret.append(ts(t));
  194.   		}
  195.   		ret.append("}");
  196.   		return ret.toString();
  197.   	}
  198.   	public void dbg(Object... o) {
  199.   		if(LOCAL) {
  200.   			System.err.print("Line #"+Thread.currentThread().getStackTrace()[2].getLineNumber()+": [");
  201.   			for(int i = 0; i<o.length; i++) {
  202.   				if(i!=0) {
  203.   					System.err.print(", ");
  204.   				}
  205.   				System.err.print(ts(o[i]));
  206.   			}
  207.   			System.err.println("]");
  208.   		}
  209.   	}
  210.   }
  211.  
  212.   static class InputReader {
  213.     private boolean finished = false;
  214.  
  215.     private InputStream stream;
  216.     private byte[] buf = new byte[1024];
  217.     private int curChar;
  218.     private int numChars;
  219.     private SpaceCharFilter filter;
  220.  
  221.     public InputReader(InputStream stream) {
  222.       this.stream = stream;
  223.     }
  224.  
  225.     public int read() {
  226.       if (numChars == -1) {
  227.         throw new InputMismatchException();
  228.       }
  229.       if (curChar >= numChars) {
  230.         curChar = 0;
  231.         try {
  232.           numChars = stream.read(buf);
  233.         } catch (IOException e) {
  234.           throw new InputMismatchException();
  235.         }
  236.         if (numChars <= 0) {
  237.           return -1;
  238.         }
  239.       }
  240.       return buf[curChar++];
  241.     }
  242.  
  243.     public int peek() {
  244.       if (numChars == -1) {
  245.         return -1;
  246.       }
  247.       if (curChar >= numChars) {
  248.         curChar = 0;
  249.         try {
  250.           numChars = stream.read(buf);
  251.         } catch (IOException e) {
  252.           return -1;
  253.         }
  254.         if (numChars <= 0) {
  255.           return -1;
  256.         }
  257.       }
  258.       return buf[curChar];
  259.     }
  260.  
  261.     public int nextInt() {
  262.       int c = read();
  263.       while (isSpaceChar(c)) {
  264.         c = read();
  265.       }
  266.       int sgn = 1;
  267.       if (c == '-') {
  268.         sgn = -1;
  269.         c = read();
  270.       }
  271.       int res = 0;
  272.       do {
  273.         if (c < '0' || c > '9') {
  274.           throw new InputMismatchException();
  275.         }
  276.         res *= 10;
  277.         res += c - '0';
  278.         c = read();
  279.       } while (!isSpaceChar(c));
  280.       return res * sgn;
  281.     }
  282.  
  283.     public long nextLong() {
  284.       int c = read();
  285.       while (isSpaceChar(c)) {
  286.         c = read();
  287.       }
  288.       int sgn = 1;
  289.       if (c == '-') {
  290.         sgn = -1;
  291.         c = read();
  292.       }
  293.       long res = 0;
  294.       do {
  295.         if (c < '0' || c > '9') {
  296.           throw new InputMismatchException();
  297.         }
  298.         res *= 10;
  299.         res += c - '0';
  300.         c = read();
  301.       } while (!isSpaceChar(c));
  302.       return res * sgn;
  303.     }
  304.  
  305.     public String nextLine() {
  306.       int c = read();
  307.       while (isSpaceChar(c)) {
  308.         c = read();
  309.       }
  310.       StringBuilder res = new StringBuilder();
  311.       do {
  312.         if (Character.isValidCodePoint(c)) {
  313.           res.appendCodePoint(c);
  314.         }
  315.         c = read();
  316.       } while (!isSpaceChar(c));
  317.       return res.toString();
  318.     }
  319.  
  320.     public boolean isSpaceChar(int c) {
  321.       if (filter != null) {
  322.         return filter.isSpaceChar(c);
  323.       }
  324.       return isWhitespace(c);
  325.     }
  326.  
  327.     public static boolean isWhitespace(int c) {
  328.       return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
  329.     }
  330.  
  331.     private String readLine0() {
  332.       StringBuilder buf = new StringBuilder();
  333.       int c = read();
  334.       while (c != '\n' && c != -1) {
  335.         if (c != '\r') {
  336.           buf.appendCodePoint(c);
  337.         }
  338.         c = read();
  339.       }
  340.       return buf.toString();
  341.     }
  342.  
  343.     public String readLine() {
  344.       String s = readLine0();
  345.       while (s.trim().length() == 0) {
  346.         s = readLine0();
  347.       }
  348.       return s;
  349.     }
  350.  
  351.     public String readLine(boolean ignoreEmptyLines) {
  352.       if (ignoreEmptyLines) {
  353.         return readLine();
  354.       } else {
  355.         return readLine0();
  356.       }
  357.     }
  358.  
  359.     public BigInteger readBigInteger() {
  360.       try {
  361.         return new BigInteger(nextLine());
  362.       } catch (NumberFormatException e) {
  363.         throw new InputMismatchException();
  364.       }
  365.     }
  366.  
  367.     public char nextCharacter() {
  368.       int c = read();
  369.       while (isSpaceChar(c)) {
  370.         c = read();
  371.       }
  372.       return (char) c;
  373.     }
  374.  
  375.     public double nextDouble() {
  376.       int c = read();
  377.       while (isSpaceChar(c)) {
  378.         c = read();
  379.       }
  380.       int sgn = 1;
  381.       if (c == '-') {
  382.         sgn = -1;
  383.         c = read();
  384.       }
  385.       double res = 0;
  386.       while (!isSpaceChar(c) && c != '.') {
  387.         if (c == 'e' || c == 'E') {
  388.           return res * Math.pow(10, nextInt());
  389.         }
  390.         if (c < '0' || c > '9') {
  391.           throw new InputMismatchException();
  392.         }
  393.         res *= 10;
  394.         res += c - '0';
  395.         c = read();
  396.       }
  397.       if (c == '.') {
  398.         c = read();
  399.         double m = 1;
  400.         while (!isSpaceChar(c)) {
  401.           if (c == 'e' || c == 'E') {
  402.             return res * Math.pow(10, nextInt());
  403.           }
  404.           if (c < '0' || c > '9') {
  405.             throw new InputMismatchException();
  406.           }
  407.           m /= 10;
  408.           res += (c - '0') * m;
  409.           c = read();
  410.         }
  411.       }
  412.       return res * sgn;
  413.     }
  414.  
  415.     public boolean isExhausted() {
  416.       int value;
  417.       while (isSpaceChar(value = peek()) && value != -1) {
  418.         read();
  419.       }
  420.       return value == -1;
  421.     }
  422.  
  423.     public String next() {
  424.       return nextLine();
  425.     }
  426.  
  427.     public SpaceCharFilter getFilter() {
  428.       return filter;
  429.     }
  430.  
  431.     public void setFilter(SpaceCharFilter filter) {
  432.       this.filter = filter;
  433.     }
  434.  
  435.     public interface SpaceCharFilter {
  436.       public boolean isSpaceChar(int ch);
  437.     }
  438.     public int[] nextIntArray(int n){
  439.       int[] array=new int[n];
  440.       for(int i=0;i<n;++i)array[i]=nextInt();
  441.       return array;
  442.     }
  443.     public int[] nextSortedIntArray(int n){
  444.       int array[]=nextIntArray(n);
  445.       Arrays.sort(array);
  446.       return array;
  447.     }
  448.     public ArrayList<Integer> nextIntArrayList(int n){
  449.       ArrayList<Integer> ar= new ArrayList<>();
  450.       for(int i=0;i<n;i++)
  451.       ar.add(nextInt());
  452.       return ar;
  453.     }
  454.     public ArrayList<Long> nextLongArrayList(int n){
  455.       ArrayList<Long> ar= new ArrayList<>();
  456.       for(int i=0;i<n;i++)
  457.       ar.add(nextLong());
  458.       return ar;
  459.     }
  460.  
  461.     public int[] nextSumIntArray(int n){
  462.       int[] array=new int[n];
  463.       array[0]=nextInt();
  464.       for(int i=1;i<n;++i)array[i]=array[i-1]+nextInt();
  465.       return array;
  466.     }
  467.     public long[] nextLongArray(int n){
  468.       long[] array=new long[n];
  469.       for(int i=0;i<n;++i)array[i]=nextLong();
  470.       return array;
  471.     }
  472.     public long[] nextSumLongArray(int n){
  473.       long[] array=new long[n];
  474.       array[0]=nextInt();
  475.       for(int i=1;i<n;++i)array[i]=array[i-1]+nextInt();
  476.       return array;
  477.     }
  478.     public long[] nextSortedLongArray(int n){
  479.       long array[]=nextLongArray(n);
  480.       Arrays.sort(array);
  481.       return array;
  482.     }
  483.     public int[][] nextIntMatrix(int n,int m){
  484.       int[][] matrix=new int[n][m];
  485.       for(int i=0;i<n;++i)
  486.       for(int j=0;j<m;++j)
  487.       matrix[i][j]=nextInt();
  488.       return matrix;
  489.     }
  490.  
  491.     public int[][] nextIntMatrix(int n){
  492.       return nextIntMatrix(n,n);
  493.     }
  494.  
  495.     public long[][] nextLongMatrix(int n,int m){
  496.       long[][] matrix=new long[n][m];
  497.       for(int i=0;i<n;++i)
  498.       for(int j=0;j<m;++j)
  499.       matrix[i][j]=nextLong();
  500.       return matrix;
  501.     }
  502.  
  503.     public long[][] nextLongMatrix(int n){
  504.       return nextLongMatrix(n,n);
  505.     }
  506.  
  507.     public char[][] nextCharMatrix(int n,int m){
  508.       char[][] matrix=new char[n][m];
  509.       for(int i=0;i<n;++i)
  510.       matrix[i]=next().toCharArray();
  511.       return matrix;
  512.     }
  513.  
  514.     public char[][] nextCharMatrix(int n){
  515.       return nextCharMatrix(n,n);
  516.     }
  517.   }
  518.  
  519.   static class OutputWriter {
  520.     private final PrintWriter writer;
  521.  
  522.     public OutputWriter(OutputStream outputStream) {
  523.       writer = new PrintWriter(new BufferedWriter(new OutputStreamWriter(outputStream)));
  524.     }
  525.  
  526.     public OutputWriter(Writer writer) {
  527.       this.writer = new PrintWriter(writer);
  528.     }
  529.  
  530.     // public void print(char[] array) {
  531.     //     writer.print(array);
  532.     // }
  533.  
  534.     public void print(Object... objects) {
  535.       for (int i = 0; i < objects.length; i++) {
  536.         if (i != 0) {
  537.           writer.print(' ');
  538.         }
  539.         writer.print(objects[i]);
  540.       }
  541.     }
  542.  
  543.     public void print(int[] array) {
  544.       for (int i = 0; i < array.length; i++) {
  545.         if (i != 0) {
  546.           writer.print(' ');
  547.         }
  548.         writer.print(array[i]);
  549.       }
  550.     }
  551.  
  552.     public void print(double[] array) {
  553.       for (int i = 0; i < array.length; i++) {
  554.         if (i != 0) {
  555.           writer.print(' ');
  556.         }
  557.         writer.print(array[i]);
  558.       }
  559.     }
  560.  
  561.     public void print(long[] array) {
  562.       for (int i = 0; i < array.length; i++) {
  563.         if (i != 0) {
  564.           writer.print(' ');
  565.         }
  566.         writer.print(array[i]);
  567.       }
  568.     }
  569.  
  570.     public void print(char[] array) {
  571.       for (int i = 0; i < array.length; i++) {
  572.         if (i != 0) {
  573.           writer.print(' ');
  574.         }
  575.         writer.print(array[i]);
  576.       }
  577.     }
  578.  
  579.     public void print(String[] array) {
  580.       for (int i = 0; i < array.length; i++) {
  581.         if (i != 0) {
  582.           writer.print(' ');
  583.         }
  584.         writer.print(array[i]);
  585.       }
  586.     }
  587.  
  588.     public void print(int[][] matrix){
  589.       for(int i=0;i<matrix.length;++i){
  590.         println(matrix[i]);
  591.       }
  592.     }
  593.  
  594.     public void print(double[][] matrix){
  595.       for(int i=0;i<matrix.length;++i){
  596.         println(matrix[i]);
  597.       }
  598.     }
  599.  
  600.     public void print(long[][] matrix){
  601.       for(int i=0;i<matrix.length;++i){
  602.         println(matrix[i]);
  603.       }
  604.     }
  605.  
  606.     public void print(char[][] matrix){
  607.       for(int i=0;i<matrix.length;++i){
  608.         println(matrix[i]);
  609.       }
  610.     }
  611.  
  612.     public void print(String[][] matrix){
  613.       for(int i=0;i<matrix.length;++i){
  614.         println(matrix[i]);
  615.       }
  616.     }
  617.  
  618.     public void println(int[] array) {
  619.       print(array);
  620.       writer.println();
  621.     }
  622.  
  623.     public void println(double[] array) {
  624.       print(array);
  625.       writer.println();
  626.     }
  627.  
  628.     public void println(long[] array) {
  629.       print(array);
  630.       writer.println();
  631.     }
  632.  
  633.     // public void println(char[] array) {
  634.     //     print(array);
  635.     //     writer.println();
  636.     // }
  637.  
  638.     public void println(String[] array) {
  639.       print(array);
  640.       writer.println();
  641.     }
  642.  
  643.     public void println() {
  644.       writer.println();
  645.     }
  646.  
  647.     public void println(Object... objects) {
  648.       print(objects);
  649.       writer.println();
  650.     }
  651.  
  652.     public void print(char i) {
  653.       writer.print(i);
  654.     }
  655.  
  656.     public void println(char i) {
  657.       writer.println(i);
  658.     }
  659.  
  660.     public void println(char[] array) {
  661.       writer.println(array);
  662.     }
  663.  
  664.     public void printf(String format, Object... objects) {
  665.       writer.printf(format, objects);
  666.     }
  667.  
  668.     public void close() {
  669.       writer.close();
  670.     }
  671.  
  672.     public void flush() {
  673.       writer.flush();
  674.     }
  675.  
  676.     public void print(long i) {
  677.       writer.print(i);
  678.     }
  679.  
  680.     public void println(long i) {
  681.       writer.println(i);
  682.     }
  683.  
  684.     public void print(int i) {
  685.       writer.print(i);
  686.     }
  687.  
  688.     public void println(int i) {
  689.       writer.println(i);
  690.     }
  691.  
  692.     public void separateLines(int[] array) {
  693.       for (int i : array) {
  694.         println(i);
  695.       }
  696.     }
  697.   }
  698.   static class NumberTheory{
  699.  
  700.     /**
  701.     * Modular Arithmetic:
  702.     *  1. (a+b)%c=(a%c+b%c)%c
  703.     *  2. (a*b)%c=(a%c*b%c)%c
  704.     *  3. (a-b)%c=(a%c-b%c+c)%c
  705.     *  4. (a/b)%c=(a%c*(b^-1)%c)%c -- (b^-1 is multiplicative modulo inverse)
  706.     */
  707.     //Modular Addition
  708.     public int modularAddition(int a,int b,int MOD){
  709.       return (a%MOD+b%MOD)%MOD;
  710.     }
  711.     public long modularAddition(long a,long b,long MOD){
  712.       return (a%MOD+b%MOD)%MOD;
  713.     }
  714.     //Modular Multiplication
  715.     public int modularMultiplication(int a,int b,int MOD){
  716.       return ((a%MOD)*(b%MOD))%MOD;
  717.     }
  718.     public long modularMultiplication(long a,long b,long MOD){
  719.       return ((a%MOD)*(b%MOD))%MOD;
  720.     }
  721.     //Modular Subtraction
  722.     public int modularSubtraction(int a,int b,int MOD){
  723.       return (a%MOD-b%MOD+MOD)%MOD;
  724.     }
  725.     public long modularSubtraction(long a,long b,long MOD){
  726.       return (a%MOD-b%MOD+MOD)%MOD;
  727.     }
  728.  
  729.     /**
  730.     * Binary Exponentiation
  731.     */
  732.     public int binaryExponentiation(int x,int n){
  733.       if(n==0)return 1;
  734.       else if(n%2==0)return binaryExponentiation(x*x,n/2);
  735.       else return x*binaryExponentiation(x*x,(n-1)/2);
  736.     }
  737.     public long binaryExponentiation(long x,long n){
  738.       long result=1;
  739.       while(n>0){
  740.         if(n%2==1)result*=x;
  741.         x=x*x;
  742.         n/=2;
  743.       }
  744.       return result;
  745.     }
  746.  
  747.     /**
  748.     * Modular Exponentiation
  749.     */
  750.     public int modularExponentiation(int x,int n,int MOD){
  751.       if(n==0)return 1%MOD;
  752.       else if(n%2==0)return modularExponentiation(modularMultiplication(x,x,MOD),n/2,MOD);
  753.       else return modularMultiplication(x,modularExponentiation(modularMultiplication(x,x,MOD),(n-1)/2,MOD),MOD);
  754.     }
  755.     public long modularExponentiation(long x,long n,long MOD){
  756.       long result=1;
  757.       while(n>0){
  758.         if(n%2==1)result=modularMultiplication(result,x,MOD);
  759.         x=modularMultiplication(x,x,MOD);
  760.         n/=2;
  761.       }
  762.       return result;
  763.     }
  764.  
  765.     /**
  766.     * Factorial of a number
  767.     */
  768.     public long factorials(long n){
  769.       if(n==0)return 1;
  770.       return n*factorials(n-1);
  771.     }
  772.  
  773.     /**
  774.     * Prime factors of a number
  775.     */
  776.     public ArrayList<Integer> distinctPrimeFactors(int n){
  777.       ArrayList<Integer> factorials=new ArrayList<>();
  778.       int limit=(int)Math.sqrt(n);
  779.       if(n%2==0){
  780.         factorials.add(2);
  781.         while(n%2==0)n/=2;
  782.       }
  783.       for(int i=3;i<=limit;i+=2){
  784.         if(n%i==0){
  785.           factorials.add(i);
  786.           while(n%i==0)n/=i;
  787.         }
  788.       }
  789.       if(n>2)factorials.add(n);
  790.       return factorials;
  791.     }
  792.  
  793.     public ArrayList<Long> distinctPrimeFactors(long n){
  794.       ArrayList<Long> factorials=new ArrayList<>();
  795.       long limit=(long)Math.sqrt(n);
  796.       if(n%2==0){
  797.         factorials.add((long)2);
  798.         while(n%2==0)n/=2;
  799.       }
  800.       for(long i=3;i<=limit;i+=2){
  801.         if(n%i==0){
  802.           factorials.add(i);
  803.           while(n%i==0)n/=i;
  804.         }
  805.       }
  806.       if(n>2)factorials.add(n);
  807.       return factorials;
  808.     }
  809.  
  810.     public ArrayList<Integer> primeFactors(int n){
  811.       ArrayList<Integer> factorials=new ArrayList<>();
  812.       int limit=(int)Math.sqrt(n);
  813.       if(n%2==0){
  814.         factorials.add(2);
  815.         while(n%2==0)n/=2;
  816.       }
  817.       for(int i=3;i<=limit;i+=2){
  818.         if(n%i==0){
  819.           factorials.add(i);
  820.           while(n%i==0)n/=i;
  821.         }
  822.       }
  823.       if(n>2)factorials.add(n);
  824.       return factorials;
  825.     }
  826.  
  827.     public ArrayList<Long> primeFactors(long n){
  828.       ArrayList<Long> factorials=new ArrayList<>();
  829.       long limit=(long)Math.sqrt(n);
  830.       if(n%2==0){
  831.         factorials.add((long)2);
  832.         while(n%2==0)n/=2;
  833.       }
  834.       for(long i=3;i<=limit;i+=2){
  835.         if(n%i==0){
  836.           factorials.add(i);
  837.           while(n%i==0)n/=i;
  838.         }
  839.       }
  840.       if(n>2)factorials.add(n);
  841.       return factorials;
  842.     }
  843.  
  844.     /**
  845.     * Combination: nCr
  846.     */
  847.     //Naive version
  848.     //(n,r)=(n-1,r-1)+(n-1,r) for r!=0 or r!=n
  849.     //(n,0)=(n,n)=1
  850.     public int binomialCoefficientRecursive(int n,int k){
  851.       if(k==0 || k==n)return 1;//base case
  852.       return binomialCoefficientRecursive(n-1,k-1)+binomialCoefficientRecursive(n-1,k);//recursion
  853.     }
  854.  
  855.     //Dynamic Programming version(Uses bottom up approach to fill the table)
  856.     //Time complexity: O(n*k)
  857.     //Space complexity: O(n*k)
  858.     public long binomialCoefficientIterative(int n,int k){
  859.       long[][] C=new long[n+1][k+1];
  860.       for(int i=0;i<=n;++i){
  861.         for(int j=0;j<=Math.min(n,k);++j){
  862.           if(j==0 || j==i)C[i][j]=1;
  863.           else C[i][j]=C[i-1][j-1]+C[i-1][j];
  864.         }
  865.       }
  866.       return C[n][k];
  867.     }
  868.  
  869.     //Pascal's Triangle version(Space efficient program)
  870.     //Time complexity: O(n*k)
  871.     //Space complexity: O(k)
  872.     public long nCr(int n,int r){
  873.       int[] C=new int[r+1];
  874.       C[0]=1;//nC0=1
  875.       for(int i=1;i<=n;++i)
  876.       for(int j=Math.min(i,r);j>0;--j)
  877.       C[j]=C[j]+C[j-1];
  878.       return C[r];
  879.     }
  880.  
  881.     /**
  882.     * Catlan number:
  883.     *  - Time complexity: O(n*n)
  884.     *  - Auxiliary space: O(n)
  885.     *
  886.     *  NOTE: Time complexity could be reduced to O(n) but it is
  887.     *        possible if and only if n is small or else there is
  888.     *        a chance of getting an overflow. To decrease the time
  889.     *        complexity to O(n) just remember nCr=nCn-r
  890.     */
  891.     public long catlanNumber(int n){
  892.       long[] catlan=new long[n+1];
  893.       catlan[0]=catlan[1]=1;
  894.       for(int i=2;i<=n;++i)
  895.       for(int j=0;j<i;++j)
  896.       catlan[i]+=catlan[j]*catlan[i-1-j];
  897.  
  898.       return catlan[n];
  899.     }
  900.  
  901.     /**
  902.     * Greatest Common Divisor(GCD)
  903.     *  - It is also known as Highest Common Factor(HCF)
  904.     *  - Time complexity: log(min(a,b))
  905.     *  - Auxiliary Space: O(1)
  906.     */
  907.     public int gcd(int a,int b){
  908.       if(b==0)return a;
  909.       return gcd(b,a %b);
  910.     }
  911.  
  912.     public long gcd(long a,long b){
  913.       if(b==0)return a;
  914.       return gcd(b,a%b);
  915.     }
  916.  
  917.     /**
  918.     * Extended Euclid's Algorithm:
  919.     *  - ax+by=gcd(a,b)
  920.     *  - Time complexity:
  921.     *  -
  922.     */
  923.  
  924.  
  925.     /**
  926.     * Least Common Multiple(LCM):
  927.     *  - Time complexity: log(min(a,b))
  928.     *  - Auxiliary Space: O(1)
  929.     */
  930.     public long lcm(long a,long b){
  931.       return (a*b)/gcd(a,b);
  932.     }
  933.  
  934.   }
  935. }
  936. //
  937. //                       "8,        .m8"
  938. //                        I8Im    ,mI8"
  939. //                        ,8I""I8,mI8m
  940. //             "I8mm,    ,I8    I8 "I8,          ,m"
  941. //                "I88I88I8m ,I8"   "I8""==mm ,mI8"
  942. //        ___    ,mI8"    "8I8"      I8,  ,mI8I8"
  943. //   .,mI8I8I8I8I88,      ,m8"      ,I8I8I8I888"
  944. // "I8Im,       "I88,    ,8"      ,II8"     "88,
  945. //    `"I8,        "I8, ,8"     ,I8"         "I8,
  946. //       "I8m       "I888      ,I8"           "I8,
  947. //         "8m        "I8      88"              "I8,
  948. //          I8,        I8      88                 "I8,
  949. //           88,       I8,     "I8                 "I8
  950. //           "I8,      "I8,     "I8,                I8;.
  951. //            "I8,      "I8,      "I8        .,mmmI8888888m,.
  952. //              I8,      "I8,      I8,  .mI8I88"""". .. "I8888
  953. //              "I8,      "I8      mI8I88"". . . . . .,m8"   "8
  954. //               I8m,  __ ;I8   ,II88" . . . . .,;miI88"
  955. //               "I88I8I88I88,,I88" . . . ,mmiiI8888"
  956. //                ,I8". . ."I8I8". . . mi888888888"
  957. //              ,I8 . . . .,I88I. . .i88888888888"
  958. //             I8. . . .,mII88Ima. .i88888888888"
  959. //            ,8"..,mI88I88I88I8Imi888888888888"
  960. //            I8.,I8I"""        ""II88888888888
  961. //           ;I8I8"                  ""I8888888
  962. //           ""                         "I88888
  963. //                                        "I888
  964. //                                         "I88,
  965. //                                          "I88
  966. //                                           "88,
  967. //                                            I88,              ______   __
  968. //                           ______           "I88__        .mI88I88I88I88I88,
  969. //                      .,mI88I88I88, ,mI88,   I88"""     ,mI8". . . . "I8,..8,
  970. //                    ,I888' . . . "I88.\ "8,  I88      ,I8". . . .  / :;I8 \ 8,
  971. //                  .mI8' . . .  / .:"I8.\ 88  "88,    ,8". . .  / .;mI8I8I8,\ 8
  972. //                 ,I8'. . .  / . .:;,I8I8I888  I88   ,8". .  / .:mI8"'   "I8,:8
  973. //                ,I8'. . . / . .:;,mI8"  `"I88 I88   I8. .  / .m8"         "I8I
  974. //               ,I8 . .  / . .:;,mI8"      "I88888   88,.  / ,m8            "8'
  975. //               I8'. .  / . .;,mI8"          "II888 ,I8I8,.,I8"
  976. //               I8 . . / . .,mI8"              I8888888' """
  977. //               `I8,.  / ;,mI8"                 II888
  978. //                "I8I, /,mI8"                 __I888
  979. //                  "I8888"                   """I88
  980. //                    ""                         I88
  981. //                                               I88__
  982. //                                               I88"""
  983. //                                               I88
  984. //                                               I88
  985. //                                             __I88
  986. //                                            """I88
  987. //                                               I88
  988. //                                               I88
  989. //                                               I88__
  990. //                                               I88"""
  991. //                                               I88
  992. //                                        BITSY  ___  CHUCK
  993.  
Runtime error #stdin #stdout #stderr 0.09s 32740KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
stderr
copy 
Exception in thread "main" java.util.InputMismatchException
	at Main$InputReader.read(Main.java:227)
	at Main$InputReader.nextInt(Main.java:264)
	at Main$ProblemSolver.solveTheProblem(Main.java:73)
	at Main.main(Main.java:113)
https://ideone.com/firTh4
language:
Java (HotSpot 12)
created:
3 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!