fork(1) download
  1. //package backTrack;
  2.  
  3. import java.util.Arrays;
  4. import java.util.Scanner;
  5.  
  6. /**
  7.  * Created by rajanW(683281) on 14-Mar-15.
  8.  * at 2:34 PM
  9.  * UVa 10576
  10.  * Explanation : http://o...content-available-to-author-only...a.es/board/viewtopic.php?f=25&t=4343
  11.  * Backtracking easy
  12.  */
  13. class Y2K {
  14.  
  15. static int months[];
  16. static int total;
  17. static int temp;
  18.  
  19. static void update(){
  20.  
  21. if(temp>total){
  22. // System.out.println("total="+temp);
  23. // System.out.println(Arrays.toString(months));
  24. total=temp;}
  25. }
  26.  
  27. static void solve(int s,int d,int month){
  28. //base cases
  29. if(month==13){
  30. update();return;}
  31. //if(temp<0){return;}
  32.  
  33.  
  34. //choose surplus and go ahead
  35. temp+=s;
  36. months[month]=s;
  37. if(month>6&&(months[month]+months[month-1]+months[month-2]+months[month-3]+months[month-4]>0)){months[month]=0;
  38. temp-=s;return;}
  39. // System.out.println("Month="+month+" going for surplus");
  40. solve(s, d, month + 1);
  41. months[month]=0;
  42. temp-=s;
  43.  
  44. //choose deficit and go ahead
  45. temp-=d;
  46. months[month]=-d;
  47. if(month>6&&(months[month]+months[month-1]+months[month-2]+months[month-3]+months[month-4]>0)){months[month]=0;
  48. temp+=d;return;}
  49. // System.out.println("Month="+month+" going for deficit");
  50. solve(s,d,month+1);
  51. months[month]=0;
  52. temp+=d;
  53. }
  54.  
  55. public static void main(String args[]) throws Exception{
  56. Scanner sc = new Scanner(System.in);
  57. while(sc.hasNextLine()){
  58. String sa[] = sc.nextLine().split(" ");
  59. int s = Integer.parseInt(sa[0]); int d = Integer.parseInt(sa[1]);
  60. total=0;temp=0;
  61. months = new int[13];
  62. solve(s,d,1);
  63. if(total>0){
  64. System.out.println(total);
  65. }else{
  66. System.out.println("Deficit");
  67. }
  68. }
  69. }
  70. }
  71.  
Success #stdin #stdout 0.12s 380672KB
stdin
4101497 6710350
2163550 3542387
539544 1111636
5085080 9666273
8789211 9365365
2370883 2797193
8079545 8073613
7691405 8552823
4145575 4573139
5730098 1906418
4507667 5009248
8546532 2087309
2734747 1082545
9028441 255967
5973691 5738302
2448652 8989505
2531893 75189
1186825 4612202
6794827 5587789
4953154 6271905
1585451 5584039
3657652 7324038
8393213 9664996
4238135 3865409
8288179 5055140
64388 2484585
7088246 2795846
3878391 1127272
1383239 9822994
5561296 5423184
6929042 7356931
7432120 526301
7654855 9460935
7565076 1135297
9923554 4449683
2550074 2518231
2358621 1509005
3690354 8724078
5105839 3268186
8323326 444841
2929427 3394018
8706216 8387715
2031339 17673
9840667 5100959
524144 3414579
3287862 7918316
960969 7453186
9430473 3236334
4371631 8615824
5581859 6995549
9513780 4295185
5804191 648285
9372363 4388753
7656939 2010897
2455738 6994554
2904924 5980266
6884333 5385165
5402839 1611140
9228452 1432024
4846603 7759858
8194526 9752596
7205782 650817
3887151 9155495
7771320 9152607
6148156 8258782
2553968 5869531
6517817 8178289
5083394 874511
2885408 8406532
5401087 2740334
1236952 5341146
3242664 822363
4949856 637637
2069661 8645503
8921713 4178308
6447256 6916265
7567082 9632592
8788087 6169390
5321997 3970586
2229368 9075759
4945291 3986505
4681146 7299688
8174199 1463108
2385992 9764541
5021227 3575959
1433458 7787079
1125795 6258179
6895816 4676122
5837977 6075651
2770311 8965477
8398094 7276042
6908634 9217567
5386957 8481529
2452115 5696722
7288833 3225306
7211811 7197835
4497524 2234124
6213584 4409310
4173851 5188075
8764035 8599577
stdout
5970576
3138852
Deficit
2015548
Deficit
Deficit
35592
Deficit
Deficit
32532
Deficit
Deficit
Deficit
Deficit
1412334
Deficit
Deficit
Deficit
7242228
Deficit
Deficit
Deficit
Deficit
2236356
Deficit
Deficit
Deficit
1489725
Deficit
828672
Deficit
Deficit
Deficit
Deficit
Deficit
191058
Deficit
Deficit
Deficit
Deficit
Deficit
1911006
Deficit
Deficit
Deficit
Deficit
Deficit
Deficit
509752
Deficit
Deficit
Deficit
Deficit
4872744
Deficit
Deficit
8995008
1708257
Deficit
7733392
Deficit
Deficit
Deficit
Deficit
Deficit
Deficit
Deficit
Deficit
Deficit
Deficit
1687228
2326725
Deficit
3405604
Deficit
Deficit
Deficit
15712182
8108466
4142162
5752716
8250416
Deficit
4330838
8671608
Deficit
Deficit
13318164
Deficit
Deficit
6732312
Deficit
9169540
Deficit
Deficit
83856
Deficit
10825644
Deficit
986748