Advertisement
Guest User

Untitled

a guest
Mar 30th, 2017
65
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.51 KB | None | 0 0
  1. //189A : CUT RIBBON
  2.  
  3. import java.io.BufferedReader;
  4. import java.io.IOException;
  5. import java.io.InputStream;
  6. import java.io.InputStreamReader;
  7. import java.io.OutputStream;
  8. import java.io.PrintWriter;
  9. import java.util.StringTokenizer;
  10.  
  11. //Your code goes here
  12. public class Main {
  13.  
  14. static class ProblemSolver{
  15. public void solveTheProblem(InputReader in,PrintWriter out){
  16. //Take the necessary inputs
  17. int n=in.nextInt();
  18. int a=in.nextInt();
  19. int b=in.nextInt();
  20. int c=in.nextInt();
  21. int[] dp=new int[4001];
  22.  
  23. //Fill all the default entry of the dp as -1 as done in most of the cases
  24. for(int i=0;i<=n;++i)dp[i]=-1;
  25.  
  26. //Initialize the given data in the dp
  27. dp[a]=1;
  28. dp[b]=1;
  29. dp[c]=1;
  30.  
  31. //Evaluate and take the optimal of all
  32. for(int i=Math.min(a, Math.min(b, c));i<=n;++i){
  33. if(i-a>=0 && dp[i-a]!=-1)dp[i]=Math.max(dp[i-a]+1,dp[i]);
  34. if(i-b>=0 && dp[i-b]!=-1)dp[i]=Math.max(dp[i-b]+1,dp[i]);
  35. if(i-c>=0 && dp[i-c]!=-1)dp[i]=Math.max(dp[i-c]+1,dp[i]);
  36. }
  37.  
  38. //Print the result
  39. System.out.println(dp[n]);
  40.  
  41. }
  42. }
  43.  
  44. //Default template for all the codes
  45. static class InputReader {
  46. public BufferedReader reader;
  47. public StringTokenizer tokenizer;
  48.  
  49. public InputReader(InputStream stream) {
  50. reader = new BufferedReader(new InputStreamReader(stream),32768);
  51. tokenizer = null;
  52. }
  53.  
  54. public String next() {
  55. while (tokenizer == null || !tokenizer.hasMoreTokens()) {
  56. try {
  57. tokenizer = new StringTokenizer(reader.readLine());
  58. } catch (IOException e) {
  59. throw new RuntimeException(e);
  60. }
  61. }
  62. return tokenizer.nextToken();
  63. }
  64.  
  65. public int nextInt() {
  66. return Integer.parseInt(next());
  67. }
  68.  
  69. }
  70.  
  71. //Main method for all the codes
  72. public static void main(String[] args) {
  73. InputStream inputStream = System.in;
  74. OutputStream outputStream = System.out;
  75. InputReader in = new InputReader(inputStream);
  76. PrintWriter out = new PrintWriter(outputStream);
  77. ProblemSolver problemSolver = new ProblemSolver();
  78. problemSolver.solveTheProblem(in, out);
  79. out.close();
  80. }
  81.  
  82. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement