fork download
copy 
  1.  
  2.  
  3. //For a string of n bits x1, x2, x3, ..., Xn the adjacent bit count of the string(AdjBC(x)) is given by
  4. //
  5. //
  6. //X1*X2 + X2*X3 + X3*X4 + ... + Xn - 1 * Xn
  7. //
  8. //
  9. //which counts the number of times a 1 bit is adjacent to another 1 bit.For example :
  10. //AdjBC(011101101) = 3
  11. //AdjBC(111101101) = 4
  12. //AdjBC(010101010) = 0
  13. //
  14. //Write a program which takes as input integers n and k and returns the number of bit
  15. //strings x of n bits(out of 2ⁿ) that satisfy AdjBC(x) = k.For example, for 5 bit strings,
  16. //there are 6 ways of getting AdjBC(x) = 2 :
  17. //11100, 01110, 00111, 10111, 11101, 11011
  18. //
  19. //Input
  20. //
  21. //The first line of input contains a single integer P, (1 ≤ P ≤ 1000), which is the number
  22. //of data sets that follow.Each data set is a single line that contains the data set
  23. //number, followed by a space, followed by a decimal integer giving the number(n) of bits
  24. //in the bit strings, followed by a single space, followed by a decimal integer(k) giving
  25. //the desired adjacent bit count.The number of bits(n) will not be greater than 100 and 
  26. //the parameters n and k will be chosen so that the result will fit in a signed 32 - bit
  27. //integer.
  28. //
  29. //Output
  30. //
  31. //For each data set there is one line of output.It contains the data set number followed 
  32. //by a single space, followed by the number of n - bit strings with adjacent bit count
  33. //equal to k.
  34.  
  35. #include <stdio.h>
  36.  
  37. //data table containing all previously counted values; 
  38. unsigned int ***data;
  39. unsigned int AdjecentBitCount(int a, int b, int c);
  40.  
  41. //counts number of strings that have numberOfAdjecent number of adjecent 1s given the string lengh
  42. //assuming that previous value was lastValue
  43. unsigned int ComputeAdjecentBitCount(int lastValue, int bits, int adjecent){
  44. 	if (adjecent < 0)
  45. 		return 0;
  46. 	if (adjecent == 0){
  47. 		if (bits <= 1)
  48. 		{
  49. 			if (lastValue == 0)
  50. 				return 2;
  51. 			return 1;
  52. 		}
  53. 	}
  54. 	if (adjecent < bits){
  55. 		if (lastValue == 0){
  56. 			return AdjecentBitCount(0, bits - 1, adjecent) + AdjecentBitCount(1, bits - 1, adjecent);
  57. 		}
  58. 		return AdjecentBitCount(0, bits - 1, adjecent) + AdjecentBitCount(1, bits - 1, adjecent - 1);
  59. 	}
  60. 	if ((adjecent == bits) && (lastValue == 1))
  61. 		return 1;	
  62. 	return 0;	
  63. };
  64.  
  65. unsigned int AdjecentBitCount(int lastValue, int numberOfBits, int numberOfAdjecent){
  66. 	if (numberOfAdjecent < 0 || numberOfBits < 0)
  67. 		return 0;
  68. 	//retrieves previous result from the table
  69. 	if (data[numberOfBits][numberOfAdjecent][lastValue] == 0xFFFFFFFF)
  70. 		data[numberOfBits][numberOfAdjecent][lastValue] = ComputeAdjecentBitCount(lastValue, numberOfBits, numberOfAdjecent);
  71. 	//if there is no result in the data table, compute it and store it
  72. 	return data[numberOfBits][numberOfAdjecent][lastValue];
  73. };
  74.  
  75.  
  76. int main(){
  77.  
  78. 	//data initialization
  79. 	data = new  unsigned int**[101];
  80. 	for (int i = 0; i < 101; ++i){
  81. 		data[i] = new  unsigned int*[101];
  82. 		for (int j = 0; j < 101; ++j){
  83. 			data[i][j] = new unsigned int[2];
  84. 			data[i][j][0] = 0xFFFFFFFF;
  85. 			data[i][j][1] = 0xFFFFFFFF;
  86. 		}
  87. 	}
  88.  
  89.  
  90. 	int numberOfCases;
  91. 	int dissposable;
  92. 	int bitsNum;
  93. 	int adjecent;
  94. 	scanf("%d", &numberOfCases);
  95. 	for (int caseNum = 0; caseNum <numberOfCases; ++caseNum){
  96. 		scanf("%d %d %d", &dissposable, &bitsNum, &adjecent);
  97. 		printf("%d %u\n", caseNum + 1, AdjecentBitCount(0, bitsNum, adjecent));
  98. 	}
  99.  
  100. 	return 0;
  101. }
  102.  
  103.  
Success #stdin #stdout 0.01s 5508KB
comments (?)
stdin
copy 
10
1 5 2
2 20 8
3 30 17
4 40 24
5 50 37
6 60 52
7 70 59
8 80 73
9 90 84
10 100 90
stdout
copy 
1 6
2 63426
3 1861225
4 168212501
5 44874764
6 160916
7 22937308
8 99167
9 15476
10 23076518
https://ideone.com/npgjhB
language:
C++ 4.3.2 (gcc-4.3.2)
created:
1 year 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!