fork(6) download
copy 
  1. # include <iostream>
  2. # include <cstdio>
  3. # include <algorithm>
  4.  
  5. using namespace std;
  6. int Sizes[101];
  7. int Total, A, N, Temp, Counter;
  8. int getDiff (int A, int B, int & C)
  9. {
  10.     while (A <= B)
  11. 	{
  12. 		C++;
  13. 		A += (A-1);
  14. 	}
  15. 	return A;
  16. }
  17. int Solve (int idx, int CurrentScore, int Changes)
  18. {
  19. 	//fprintf (stderr, "%d\t%d\t%d\n", idx, CurrentScore, Changes);
  20. 	if (idx == N) return Changes;
  21. 	if (CurrentScore == 1)
  22. 		return Solve (idx + 1, CurrentScore, Changes + 1);
  23. 	else if (Sizes[idx] < CurrentScore)
  24. 		return Solve (idx + 1, CurrentScore + Sizes[idx], Changes);
  25. 	else
  26. 	{
  27. 		int tChanges = 0;
  28. 		int Diff = getDiff (CurrentScore, Sizes[idx], tChanges) + Sizes[idx];
  29. 		int Min1 = Solve (idx + 1, Diff, Changes + tChanges);
  30. 		if (Sizes[idx] > CurrentScore)
  31. 			return min (Solve (idx + 1, CurrentScore, Changes+1), Min1);
  32. 		else return Min1;
  33. 	}
  34. }
  35. int main()
  36. {
  37. 	//freopen ("Input.txt", "r", stdin);
  38. 	//freopen ("Scratch.txt", "w", stdout);
  39. 	scanf ("%d", &Total);
  40. 	for (int i = 1; i <= Total; i++)
  41. 	{
  42. 		scanf ("%d%d", &A, &N);
  43. 		Temp = A;
  44. 		Counter = 0;
  45. 		//fprintf (stderr, "After Sorting\n");
  46. 		for (int j = 0; j < N; j++) scanf ("%d", &Sizes[j]);
  47. 		//fprintf (stderr, "After Sorting\n");
  48. 		sort (Sizes, Sizes + N);
  49. 		//fprintf (stderr, "After Sorting %d\n", A);
  50. 		printf ("Case #%d: %d\n", i, Solve (0, A, 0));
  51. 		//fprintf (stderr, "\n\n");
  52. 	}
  53. }
  54.  
Success #stdin #stdout 0s 2856KB
comments (?)
stdin
copy 
100
3 8
5 6 9 4 8 2 1 7
3 1
2
3 10
2 4 8 16 32 64 100 100 100 100
3 10
1 4 4 4 4 4 4 4 4 4
100 1
100
3 5
11 20 60 22 100
2 10
100 100 100 100 100 100 100 100 100 100
3 5
100 100 100 100 100
3 4
1 6 12 49
2 6
9 64 19 16 81 80
1 10
100 100 100 100 100 100 100 100 100 100
1 10
1 1 1 1 1 1 1 1 1 1
6 6
20 8 21 92 88 15
19 2
15 61
3 9
1 7 1 85 12 15 86 3 13
2 4
29 46 4 41
5 6
30 32 84 4 57 5
20 7
82 57 14 53 90 19 1
1 8
17 3 29 29 35 20 42 4
10 9
57 17 2 3 32 3 11 27 26
7 2
20 49
2 1
7
6 1
3
1 2
94 52
6 5
37 82 70 32 64
23 5
3 18 1 4 34
7 9
2 30 65 90 3 19 6 66 65
1 6
80 14 4 51 9 18
1 8
65 2 22 10 6 6 73 2
4 5
74 1 6 75 69
1 3
4 8 98
4 2
33 3
7 8
95 17 16 41 90 22 44 64
1 6
4 86 93 95 18 80
20 5
19 21 25 82 5
1 9
56 32 28 1 4 61 73 70 1
3 7
75 30 13 1 66 8 8
3 9
34 1 2 57 28 95 98 52 26
1 1
27
9 1
83
2 3
51 16 27
22 6
7 2 1 86 4 20
6 7
62 1 31 65 99 68 33
11 3
79 1 68
2 7
37 47 29 21 6 30 35
20 5
1 30 88 75 15
5 8
4 1 63 52 53 27 90 2
14 3
69 78 10
2 2
8 1
23 7
1 33 2 17 98 17 23
8 3
95 83 48
1 6
37 1 16 30 33 11
7 2
28 11
12 4
38 13 24 98
4 2
8 19
22 7
1 7 99 34 40 31 1
1 7
12 27 94 28 39 70 1
8 9
1 93 6 49 20 20 1 11 21
2 5
4 36 87 2 14
5 9
1 1 84 95 93 1 24 86 50
19 3
74 41 28
1 1
60
17 1
89
18 8
87 1 79 1 44 73 3 1
8 1
11
1 9
69 2 11 85 94 65 70 73 61
14 6
1 72 15 1 19 81
22 4
76 1 13 43
4 9
20 8 44 37 89 47 94 8 1
8 8
27 74 69 6 5 27 2 3
4 8
5 1 59 15 13 31 1 1
12 8
2 1 3 79 19 24 10 59
2 3
24 74 4
1 4
20 1 33 70
17 4
8 6 4 1
5 7
2 2 23 7 25 2 2
10 9
75 8 9 6 6 47 19 85 98
10 3
4 44 2
1 6
78 1 8 84 17 17
6 8
15 1 13 4 18 21 2 42
2 2
49 18
21 6
8 75 3 8 78 60
1 2
1 9
1 2
26 10
13 3
7 14 99
1 2
86 99
2 5
6 91 29 43 99
17 7
12 64 46 72 9 10 6
22 6
71 20 39 22 88 16
3 9
3 1 5 16 90 2 28 19 45
12 7
19 68 12 26 33 54 51
19 3
2 38 87
1 3
32 87 8
2 3
9 52 5
14 5
46 24 29 1 1
6 1
66
2 4
78 3 27 22
1 5
11 54 30 2 4
25 2
74 22
5 1
13
stdout
copy 
Case #1: 0
Case #2: 0
Case #3: 0
Case #4: 1
Case #5: 1
Case #6: 3
Case #7: 7
Case #8: 5
Case #9: 2
Case #10: 5
Case #11: 10
Case #12: 10
Case #13: 2
Case #14: 1
Case #15: 1
Case #16: 4
Case #17: 2
Case #18: 0
Case #19: 8
Case #20: 0
Case #21: 2
Case #22: 1
Case #23: 0
Case #24: 2
Case #25: 3
Case #26: 0
Case #27: 1
Case #28: 6
Case #29: 8
Case #30: 4
Case #31: 3
Case #32: 1
Case #33: 2
Case #34: 6
Case #35: 0
Case #36: 9
Case #37: 2
Case #38: 3
Case #39: 1
Case #40: 1
Case #41: 3
Case #42: 1
Case #43: 3
Case #44: 2
Case #45: 4
Case #46: 1
Case #47: 2
Case #48: 2
Case #49: 1
Case #50: 0
Case #51: 3
Case #52: 6
Case #53: 2
Case #54: 2
Case #55: 2
Case #56: 1
Case #57: 7
Case #58: 0
Case #59: 3
Case #60: 2
Case #61: 1
Case #62: 1
Case #63: 1
Case #64: 1
Case #65: 1
Case #66: 9
Case #67: 1
Case #68: 1
Case #69: 1
Case #70: 1
Case #71: 1
Case #72: 0
Case #73: 3
Case #74: 4
Case #75: 0
Case #76: 1
Case #77: 0
Case #78: 1
Case #79: 6
Case #80: 1
Case #81: 2
Case #82: 1
Case #83: 2
Case #84: 2
Case #85: 1
Case #86: 2
Case #87: 5
Case #88: 0
Case #89: 0
Case #90: 1
Case #91: 1
Case #92: 2
Case #93: 3
Case #94: 3
Case #95: 1
Case #96: 1
Case #97: 4
Case #98: 5
Case #99: 1
Case #100: 1
https://ideone.com/g5qxYd
Google Code Jam 2013 - Round 1B - Problem A - Osmos
language:
C++ (gcc 8.3)
created:
11 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!