fork download
copy 
  1. import java.util.HashSet;
  2. import java.util.Set;
  3.  
  4. class Multimapa {
  5.  
  6. 	Set<Integer>[] pos;
  7. 	int size;
  8. 	int base;
  9.  
  10. 	private void initPos(int base) {
  11. 		pos = new HashSet[base];
  12.  
  13. 		for (int i = 0; i < base; i++) {
  14. 			pos[i] = new HashSet<>();
  15. 		}
  16. 	}
  17.  
  18. 	public Multimapa(int n, int base) {
  19. 		this.base = base;
  20. 		initPos(base);
  21.  
  22. 		if (n == 0) {
  23. 			pos[0].add(0);
  24. 			size = 1;
  25. 			return;
  26. 		}
  27. 		if (n < 0) {
  28. 			n = -n;
  29. 		}
  30. 		int digitPos = 0;
  31. 		while (n > 0) {
  32. 			int digit = n % base;
  33. 			pos[digit].add(digitPos);
  34.  
  35. 			n /= base;
  36. 			digitPos++;
  37. 		}
  38. 		size = digitPos;
  39. 	}
  40.  
  41. 	public static void main(String[] args) {
  42. 		// int qntNumerosInteressantes = 0;
  43. 		// for (int i = 0; i < 99999999; i++) {
  44. 		// 	if (julga(i, 10)) {
  45. 		// 		System.out.println(i + " é capicua não repetido na base " + 10);
  46. 		// 		qntNumerosInteressantes++;
  47. 		// 	}
  48. 		// }
  49.  
  50. 		// System.out.println("quantidade de números capicua e não repetidos nas base 10: " + qntNumerosInteressantes);
  51.  
  52. 		// qntNumerosInteressantes = 0;
  53. 		// for (int i = 0; i < 99999999; i++) {
  54. 		// 	if (julga(i, 16)) {
  55. 		// 		System.out.println(i + " é capicua não repetido na base " + 16);
  56. 		// 		qntNumerosInteressantes++;
  57. 		// 	}
  58. 		// }
  59.  
  60. 		// System.out.println("quantidade de números capicua e não repetidos nas base 16: " + qntNumerosInteressantes);
  61.  
  62. 		meta_julga(0xffeff, 10); // 1048319
  63. 		meta_julga(121, 10);
  64. 		meta_julga(1221, 10);
  65. 		meta_julga(12721, 10);
  66. 		meta_julga(12721, 16); // 31b1
  67. 		meta_julga(0xffeff, 16);
  68. 		meta_julga(0xffdead, 16);
  69. 		meta_julga(0101, 8);
  70. 		meta_julga(0171, 8);
  71. 		meta_julga(01267621, 8);
  72. 		meta_julga(01267421, 8);
  73.  
  74. 		meta_julga(5, 2); // 101
  75. 		meta_julga(6, 2); // 110
  76. 		meta_julga(7, 2); // 111
  77. 		meta_julga(4, 2); // 10
  78. 		meta_julga(16, 3); // 121
  79. 		meta_julga(10, 3); // 101
  80. 		meta_julga(12, 3); // 110
  81. 	}
  82.  
  83. 	private static void meta_julga(int n, int base) {
  84. 		if (julga(n, base)) {
  85. 			System.out.println(n + " é capicua não repetido na base " + base);
  86. 		} else {
  87. 			System.out.println(n + " não é capicua não repetido na base " + base);
  88. 		}
  89. 	}
  90.  
  91. 	// retorna verdade se todos os dígitos do número passado forem idênticos
  92. 	//
  93. 	// algoritmo de detecção: se, por acaso, existirem pelo menos dois dígitos com 1 ou mais posições, então é não repetido.
  94. 	// caso seja tudo zero exceto por um único dígito, então é repetido
  95. 	private static boolean ehNaoRepetido(Multimapa mm) {
  96. 		int nDigitosDistintos = 0;
  97.  
  98. 		for (int i = 0; i < mm.base; i++) {
  99. 			nDigitosDistintos += mm.pos[i].size() > 0? 1: 0;
  100. 		}
  101.  
  102. 		return nDigitosDistintos > 1;
  103. 	}
  104.  
  105. 	// retorna verdadeiro caso seja capicua
  106. 	//
  107. 	// algoritmo: verifica cada dígito; se for de tamanho `t` ímpar, então o dígito da posição `floor(t/2)` deve ser ignorado
  108. 	// para um dígito `d` na posição `p` não ignorado, é necessário existir um outro dígito `d` na posição complementar `p'`, tal que `p + p' = t - 1`
  109. 	private static boolean ehCapicua(Multimapa mm) {
  110. 		int somaSimetrica = mm.size - 1;
  111. 		int posIgnorada = mm.size % 2 == 1? mm.size/2: -1;
  112.  
  113. 		for (int d = 0; d < mm.base; d++) {
  114. 			for (Integer p: mm.pos[d]) {
  115. 				// só tenta verificar se tem o complemento se e somente se não é ignorado
  116. 				if (p != posIgnorada) {
  117. 					int posComplemento = somaSimetrica - p;
  118.  
  119. 					// se não existe o dígito na posição complementar, então não é capicua
  120. 					if (!mm.pos[d].contains(posComplemento)) {
  121. 						return false;
  122. 					}
  123. 				}
  124. 			}
  125. 		}
  126. 		return true;
  127. 	}
  128.  
  129. 	private static boolean julga(int n, int base) {
  130. 		Multimapa mm = new Multimapa(n, base);
  131.  
  132. 		if (ehNaoRepetido(mm)) {
  133. 			if (ehCapicua(mm)) {
  134. 				return true;
  135. 			}
  136. 		}
  137.  
  138. 		return false;
  139. 	}
  140. }
  141.  
Success #stdin #stdout 0.04s 4386816KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1048319 não é capicua não repetido na base 10
121 é capicuan não repetido na base 10
1221 é capicuan não repetido na base 10
12721 é capicuan não repetido na base 10
12721 não é capicua não repetido na base 16
1048319 é capicuan não repetido na base 16
16768685 não é capicua não repetido na base 16
65 é capicuan não repetido na base 8
121 é capicuan não repetido na base 8
356241 é capicuan não repetido na base 8
356113 não é capicua não repetido na base 8
5 é capicuan não repetido na base 2
6 não é capicua não repetido na base 2
7 não é capicua não repetido na base 2
4 não é capicua não repetido na base 2
16 é capicuan não repetido na base 3
10 é capicuan não repetido na base 3
12 não é capicua não repetido na base 3
https://ideone.com/lvA9a4
language:
Java (HotSpot 12)
created:
7 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!