fork download
  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
stdin
Standard input is empty
stdout
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