Respuestas-practica-entrada-CC3S2.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "aa25c6d6",
   "metadata": {},
   "source": [
    "### Respuestas de la prueba de entrada"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "abc67693",
   "metadata": {},
   "source": [
    "Irene tiene n monedas en su cartera, las monedas pueden tener diferentes valores, pero ella puede tener más de una moneda del mismo valor. Ella quiere dar todas sus monedas a sus dos hijos, de manera que la diferencia de lo que reciban sea mínima, de esa manera cualquiera de ellos estará triste. Escriba un programa que encuentre cuánto dinero recibe cada niño."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "bbcd0a8e",
   "metadata": {},
   "outputs": [],
   "source": [
    "  #include <cstdio>\n",
    "  using namespace std;\n",
    "\n",
    "  int C[101], X[1001];\n",
    "  int nMonedas;\n",
    "\n",
    "  int main() {\n",
    "    int k, dinero, halfdinero;\n",
    "\n",
    "    dinero = 0;\n",
    "    scanf(\"%d\", &nMonedas);\n",
    "    for (int i = 0; i < nMonedas; i++) {\n",
    "      scanf(\"%d\", &C[i]);\n",
    "      dinero += C[i];\n",
    "    }\n",
    "\n",
    "    halfdinero = dinero / 2;\n",
    "    X[0] = 1;\n",
    "    for (int i = 0; i < nMonedas; i++) {\n",
    "      k = C[i];\n",
    "      for (int j = halfdinero; j >= k; j--) {\n",
    "        X[j] |= X[j - k];\n",
    "      }\n",
    "    }\n",
    "\n",
    "    for (int i = halfdinero; i >= 0; i--) {\n",
    "      if (X[i] != 0) {\n",
    "        printf(\"%d %d\\n\", i, dinero - i);\n",
    "        break;\n",
    "      }\n",
    "    }\n",
    "\n",
    "    return 0;\n",
    "  }"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "476dc050",
   "metadata": {},
   "source": [
    "El rompecabezas de búsqueda de palabras (https://en.wikipedia.org/wiki/Word_search ) es un juego en el que se te da un diccionario de n palabras, junto con una matriz M, r × c que contiene solo letras mayúsculas, el objetivo es encontrar todas las palabras del diccionario en M, las palabras se pueden escribir hacia adelante o hacia atrás en cualquiera de las 8 direcciones (vertical, horizontal, diagonal). Escribe un programa que dado un diccionario y un rompecabezas, encuentre en el rompecabezas cada palabra del diccionario."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "400db081",
   "metadata": {},
   "outputs": [],
   "source": [
    "#include <iostream>\n",
    "#include <string>\n",
    "#include <vector>\n",
    "using namespace std;\n",
    "\n",
    "class TrieNode {\n",
    " public:\n",
    "  bool isWord;\n",
    "  vector<int> ref;\n",
    "\n",
    "  TrieNode(bool isWord = false) {\n",
    "    this->isWord = isWord;\n",
    "    ref = vector<int>(26, -1);\n",
    "  }\n",
    "};\n",
    "\n",
    "int n, nRows, nColumns;\n",
    "vector<string> puzzle;\n",
    "vector<TrieNode> trie;\n",
    "\n",
    "int encuentraPalabras(int, int, int, int);\n",
    "void agregaPalabra(int, string, int);\n",
    "\n",
    "int main() {\n",
    "  string word, puzzleRow;\n",
    "  int palabraEncontrada;\n",
    "\n",
    "  trie.push_back(TrieNode());\n",
    "  // Lee el diccionario y agrega palabras para probar\n",
    "  cin >> n >> nRows >> nColumns;\n",
    "  for (int i = 0; i < n; i++) {\n",
    "    cin >> word;\n",
    "    agregaPalabra(0, word, 0);\n",
    "  }\n",
    "\n",
    "  //  Lee rompecabezas de palabras\n",
    "  for (int i = 0; i < nRows; i++) {\n",
    "    cin >> puzzleRow;\n",
    "    puzzle.push_back(puzzleRow);\n",
    "  }\n",
    "\n",
    "  // Por cada letra inicia una búsqueda en las 8 direcciones\n",
    "  for (int i = 0; i < nRows; i++) {\n",
    "    for (int j = 0; j < nColumns; j++) {\n",
    "      palabraEncontrada = encuentraPalabras(i, j, -1, 0);\n",
    "      palabraEncontrada += encuentraPalabras(i, j, 0, 1);\n",
    "      palabraEncontrada += encuentraPalabras(i, j, 1, 0);\n",
    "      palabraEncontrada += encuentraPalabras(i, j, 0, -1);\n",
    "      palabraEncontrada += encuentraPalabras(i, j, -1, 1);\n",
    "      palabraEncontrada += encuentraPalabras(i, j, 1, 1);\n",
    "      palabraEncontrada += encuentraPalabras(i, j, 1, -1);\n",
    "      palabraEncontrada += encuentraPalabras(i, j, -1, -1);\n",
    "\n",
    "      // Imprime la ubicación de la letra inicial y cuántas palabras se encontraron\n",
    "      if (palabraEncontrada > 0) {\n",
    "        cout << \"(\" << i << \",\" << j << \"): \" << palabraEncontrada << \"\\n\";\n",
    "      }\n",
    "    }\n",
    "  }\n",
    "\n",
    "  return 0;\n",
    "}\n",
    "\n",
    "int encuentraPalabras(int row, int col, int dirY, int dirX) {\n",
    "  int nWords = 0;\n",
    "  int k = 0;\n",
    "\n",
    "  while (row >= 0 && row < nRows && col >= 0 && col < nColumns) {\n",
    "    int p = puzzle[row][col] - 'A';\n",
    "    if (trie[k].ref[p] != -1) {\n",
    "      k = trie[k].ref[p];\n",
    "    } else {\n",
    "      break;\n",
    "    }\n",
    "\n",
    "    if (trie[k].isWord) {\n",
    "      nWords++;\n",
    "    }\n",
    "    row += dirY;\n",
    "    col += dirX;\n",
    "  }\n",
    "\n",
    "  return nWords;\n",
    "}\n",
    "\n",
    "void agregaPalabra(int nodeId, string word, int pos) {\n",
    "  if (pos == word.length()) {\n",
    "    return;\n",
    "  }\n",
    "\n",
    "  int k = trie[nodeId].ref[word[pos] - 'A'];\n",
    "  if (k == -1) {\n",
    "    k = trie.size();\n",
    "    trie[nodeId].ref[word[pos] - 'A'] = k;\n",
    "    trie.push_back(TrieNode());\n",
    "  }\n",
    "\n",
    "  if (pos == word.length() - 1) {\n",
    "    trie[k].isWord = true;\n",
    "  }\n",
    "  \n",
    "  agregaPalabra(k, word, pos + 1);\n",
    "}"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "C++11",
   "language": "C++11",
   "name": "xcpp11"
  },
  "language_info": {
   "codemirror_mode": "text/x-c++src",
   "file_extension": ".cpp",
   "mimetype": "text/x-c++src",
   "name": "c++",
   "version": "11"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}