fork(2) download 
  1. import java.util.Scanner;
  2.  
  3. public class Main {
  4. 	private static int m;
  5. 	private static int n;
  6. 	private static int[] a;
  7. 	private static int[] b;
  8. 	private static int[] c;
  9.  
  10. 	private static int baloonsByIthPersonInXMinutes(int i, int x) {
  11. 		int fullCycleTime = a[i] * b[i] + c[i];
  12. 		int fullCyclesCount = x / fullCycleTime;
  13. 		int remainingTime = x - fullCyclesCount*fullCycleTime;
  14. 		int balloonsInRemainingTime = Math.min(b[i], remainingTime / a[i]);
  15. 		return fullCyclesCount * b[i] + balloonsInRemainingTime;
  16. 	}
  17.  
  18. 	private static int totalBaloonsInXMinutes(int x) {
  19. 		int result = 0;
  20. 		for (int i = 0; i < n; ++i) {
  21. 			result += baloonsByIthPersonInXMinutes(i, x);
  22. 		}
  23. 		return result;
  24. 	}
  25.  
  26. 	private static int findUpperBound() {
  27. 		int result = 1;
  28. 		while (totalBaloonsInXMinutes(result) < m) {
  29. 			result *= 2;
  30. 		}
  31. 		return result;
  32. 	}
  33.  
  34. 	private static int solveByBinarySearch(int lowerBound, int upperBound) {
  35. 		if (lowerBound == upperBound) return lowerBound;
  36. 		int middle = (lowerBound + upperBound) / 2;
  37. 		int middleValue = totalBaloonsInXMinutes(middle);
  38. 		if (middleValue < m)
  39. 			return solveByBinarySearch(middle + 1, upperBound);
  40. 		else
  41. 			return solveByBinarySearch(lowerBound, middle);
  42.  
  43. 	}
  44.  
  45.     public static void main(String[] args) {
  46.         Scanner in = new Scanner(System.in);
  47.         m = in.nextInt();
  48.         n = in.nextInt();
  49.         a = new int[n];
  50.         b = new int[n];
  51.         c = new int[n];
  52.         for(int i = 0; i < n; i++) {
  53.             a[i] = in.nextInt();
  54.             b[i] = in.nextInt();
  55.             c[i] = in.nextInt();
  56.         }
  57. 		int upperBound = findUpperBound();
  58. 		int result = solveByBinarySearch(upperBound / 2, upperBound);
  59.         System.out.println(result);
  60.     }
  61. }
Success #stdin #stdout 0.16s 321344KB
comments (?)
stdin 
10 3
1 2 3
3 10 3
2 4 3
stdout 
8
https://ideone.com/Wfj6H2
language:
Java (HotSpot 12)
created:
9 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!