Loading...
Submission
# When Author Problem Language CPU Memory
20829 2024-06-09 09:06:37 AHAMMED_99 Major Emrul & A Dream War C 138 ms 5492 kb Accepted
Test Cases
# CPU Memory Points
1 0 ms 1536 kb 1 Accepted
2 0 ms 1536 kb 1 Accepted
3 1 ms 3584 kb 1 Accepted
4 0 ms 1340 kb 1 Accepted
5 1 ms 1604 kb 1 Accepted
6 1 ms 3788 kb 1 Accepted
7 0 ms 1628 kb 1 Accepted
8 138 ms 5492 kb 1 Accepted
Source Code
  1. #include <stdio.h>
  2. #include <limits.h>
  3.  
  4. #define MAX_LEVELS 10005
  5. #define MAX_DRONES 105
  6.  
  7. int dp[MAX_DRONES][MAX_LEVELS];
  8.  
  9. int min(int a, int b) {
  10. return a < b ? a : b;
  11. }
  12.  
  13. int max(int a, int b) {
  14. return a > b ? a : b;
  15. }
  16.  
  17. int main() {
  18. int K, N;
  19. scanf("%d %d", &K, &N);
  20.  
  21. // Initialize the dp array
  22. for (int i = 0; i <= K; i++) {
  23. for (int j = 0; j <= N; j++) {
  24. dp[i][j] = INT_MAX;
  25. }
  26. }
  27.  
  28. // Base cases
  29. for (int i = 1; i <= K; i++) {
  30. dp[i][0] = 0; // No levels to test
  31. dp[i][1] = 1; // Only one level to test
  32. }
  33. for (int j = 1; j <= N; j++) {
  34. dp[1][j] = j; // With one drone, we need to test each level
  35. }
  36.  
  37. // Fill the dp table
  38. for (int i = 2; i <= K; i++) {
  39. for (int j = 2; j <= N; j++) {
  40. int low = 1, high = j, result = INT_MAX;
  41. while (low <= high) {
  42. int mid = (low + high) / 2;
  43. int broken = dp[i - 1][mid - 1]; // Drone breaks
  44. int not_broken = dp[i][j - mid]; // Drone does not break
  45. result = min(result, 1 + max(broken, not_broken));
  46.  
  47. if (broken > not_broken) {
  48. high = mid - 1;
  49. } else {
  50. low = mid + 1;
  51. }
  52. }
  53. dp[i][j] = result;
  54. }
  55. }
  56.  
  57. int result = dp[K][N];
  58. if (result == INT_MAX) {
  59. printf("Sorry, Emrul Bhai :(\n");
  60. } else {
  61. printf("%d\n", result);
  62. }
  63.  
  64. return 0;
  65. }
  66.