Assignment 1/Assignment__1.ipynb

{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "name": "Assignment_#1.ipynb",
      "provenance": [],
      "authorship_tag": "ABX9TyNeccMoJUc5l9M+J7i1VRvM",
      "include_colab_link": true
    },
    "kernelspec": {
      "name": "python3",
      "display_name": "Python 3"
    }
  },
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "view-in-github",
        "colab_type": "text"
      },
      "source": [
        "<a href=\"https://colab.research.google.com/github/18520918/CS114.L11.KHCL/blob/master/Assignment%201/Assignment__1.ipynb\" target=\"_parent\"><img src=\"https://colab.research.google.com/assets/colab-badge.svg\" alt=\"Open In Colab\"/></a>"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "8oAe5eb24P64"
      },
      "source": [
        "#**ONLINE GAME**.<br>\n",
        "Khi làm việc với yêu cầu tìm kiếm, chúng ta có thể sử dụng thuật toán tìm kiếm nhị phân. Tuy nhiên thuật toán tìm kiếm nhị phân chỉ có thể chạy trên cấu trúc dữ liệu mảng và mảng đó phải được sắp xếp thứ tự. Việc sắp xếp thường có độ phức tạp khá cao, điển hình là trong trường hợp sau đây:\n",
        "\n",
        "Giả định công ty NaViGame đang duy trì một hệ thống server rất lớn đáp ứng cho hàng chục triệu acccount của các game thủ. Hệ thông server này duy trì một danh sách các game thủ đang online cho phép nhà quản trị có thể kiểm tra xem một game thủ bất kỳ nào đó có đang online hay không. Hãy giúp công ty NaViGame xây dựng module kiểm tra game thủ online này.\n",
        "\n",
        "**INPUT**<br>\n",
        ">Mỗi dòng của input chứa hai con số a và b. Số a có giá trị là 1 hoặc 2 đại diện cho hai tình huống là có game thủ đăng nhập vào hệ thống và người quản trị vừa nhập một yêu cầu kiểm tra. Số b là mã số của game thủ trong tình huống đó (giá trị b không quá 1 tỷ).\n",
        "\n",
        "**Ví dụ như dòng**: 1 565481 cho biết game thủ với mã số 465481 vừa mới đăng nhập vào hệ thống\n",
        "\n",
        "**dòng**: 2 87126 cho biết người quản trị muốn kiểm tra xem game thủ với mã số 87126 có đang online trong hệ thống hay không.\n",
        "\n",
        "Input sẽ kết thúc bằng dòng chỉ chứa một số 0.\n",
        "\n",
        "**OUTPUT**<br>\n",
        ">Ứng với mỗi yêu cầu kiểm tra của nhà quản trị xuất ra trên một dòng giá trị 0 nếu game thủ đó không online. Nếu game thủ đang online, xuất ra 1\n",
        "\n",
        "**VÍ DỤ**:<br>\n",
        "\n",
        "|Input|Output|\n",
        "|---|---|\n",
        "|1 1 |0 |\n",
        "|1 2 | 1|\n",
        "|1 3|  |\n",
        "|2 4|  |\n",
        "|2 1|  |\n",
        "|1 5|  |\n",
        "|0|  |\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "E6be-NGWNVWZ",
        "outputId": "56e08a63-7b8c-47e5-e33d-a2671aa5afb5",
        "colab": {
          "base_uri": "https://localhost:8080/"
        }
      },
      "source": [
        "online = dict()\n",
        "ans = []\n",
        "while True:\n",
        "  s = input().split()\n",
        "  if s[0] == '1':\n",
        "    online[s[1]] = \"\"\n",
        "    #print(online)\n",
        "  elif s[0] == '2' and s[1] not in online.keys():\n",
        "      ans.append(0)\n",
        "  elif s[0] == '2' and s[1] in online.keys():\n",
        "      ans.append(1)\n",
        "  else:\n",
        "    break\n",
        "for i in range(len(ans)):\n",
        "  print(ans[i])"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "1 2\n",
            "2 3\n",
            "1 44\n",
            "1 5\n",
            "2 5\n",
            "2 1\n",
            "2 2\n",
            "1 3\n",
            "0\n",
            "0\n",
            "1\n",
            "0\n",
            "1\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "Nkj2MkpRNloE"
      },
      "source": [
        "**Bình luận**: Với mỗi lần nhập có dạng \"a b\" thì khi a = 1 thì sẽ thêm vào từ điển có sẵn giá trị b tương ứng, khi a = 2 thì sẽ kiểm tra giá trị b có tồn tại trong tử điển hay không."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "DOnfX-eNa5KM"
      },
      "source": [
        "# **ONLINE GAME 2**\n",
        "\n",
        "Nếu bạn có thể chèn thêm giá trị vào cây nhị phân thì chắc hẳn bạn cũng có thể xóa giá trị ra khỏi cây chứ nhỉ?\n",
        "\n",
        "Giả định công ty NaViGame đang duy trì một hệ thống server rất lớn đáp ứng cho hàng chục triệu acccount của các game thủ. Hệ thông server này duy trì một danh sách các game thủ đang online cho phép nhà quản trị có thể kiểm tra xem một game thủ bất kỳ nào đó có đang online hay không. Hãy giúp công ty NaViGame xây dựng module kiểm tra game thủ online này.\n",
        "\n",
        "**INPUT**<br>\n",
        ">Mỗi dòng của input chứa hai con số a và b. Số a có giá trị là 1 hoặc 2 hoặc 3 đại diện cho các tình huống là có game thủ đăng nhập vào hệ thống, có game thủ đăng xuất khỏi hệ thống và người quản trị vừa nhập một yêu cầu kiểm tra. Số b là mã số của game thủ trong tình huống đó (giá trị b không quá 1 tỷ).\n",
        "\n",
        "**Ví dụ như**<br>\n",
        "\n",
        "Dòng: 1 565481 cho biết game thủ với mã số 465481 vừa mới đăng nhập vào hệ thống\n",
        "\n",
        "Dòng: 2 87126 cho biết người quản trị muốn kiểm tra xem game thủ với mã số 87126 có đang online trong hệ thống hay không.\n",
        "\n",
        "Dòng: 3 48769 cho biết là game thủ có mã số 48769 vừa đăng xuất khỏi hệ thống.\n",
        "\n",
        "Input sẽ kết thúc bằng dòng chỉ chứa một số 0.\n",
        "\n",
        "**OUTPUT**<br>\n",
        ">Ứng với mỗi yêu cầu kiểm tra của nhà quản trị xuất ra trên một dòng giá trị 0 nếu game thủ đó không online. Nếu game thủ đang online, xuất ra 1\n",
        "\n",
        "**VÍ DỤ**<br>\n",
        "\n",
        "|INPUT|OUTPUT|\n",
        "|--|--|\n",
        "|1 1| 1|\n",
        "|1 3|0|\n",
        "|1 2| |\n",
        "|1 4| |\n",
        "|2 1| |\n",
        "|1 1| |\n",
        "|3 1| |\n",
        "|2 1| |\n",
        "|0 | |\n",
        "\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "sGwf8fJ4bj5Y",
        "outputId": "7f1f2628-2b76-4291-cbd0-549025decf6d",
        "colab": {
          "base_uri": "https://localhost:8080/"
        }
      },
      "source": [
        "online = dict()\n",
        "ans = []\n",
        "while True:\n",
        "  s = input().split()\n",
        "  if s[0] == '1':\n",
        "    online[s[1]] = \"\"\n",
        "    #print(online)\n",
        "  elif s[0] == '2' and s[1] not in online.keys():\n",
        "    ans.append(0)\n",
        "  elif s[0] == '2' and s[1] in online.keys():\n",
        "    ans.append(1)\n",
        "  elif s[0] == '3' and s[1] in online.keys():\n",
        "    del online[s[1]]\n",
        "  elif s[0] == '3' and s[1] not in online.keys():\n",
        "    continue\n",
        "  else:\n",
        "    break\n",
        "for i in range(len(ans)):\n",
        "  print(ans[i])"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "1 1\n",
            "1 3\n",
            "1 2\n",
            "1 4\n",
            "2 1\n",
            "1 1\n",
            "3 1\n",
            "2 1\n",
            "0\n",
            "1\n",
            "0\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "ejpY1iiVbxVf"
      },
      "source": [
        "**Bình luận**: Tương tự bài 1, ở bài này thì thêm biến c để xoá người chơi ra khỏi từ điển."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "8HzGSgDpbzNU"
      },
      "source": [
        "# **Print mảng 2D**\n",
        "\n",
        "Bình đang làm bài tập mảng 2 chiều nâng rất rất cao. Bình cần xuất mảng ra màn hình để quan sát. Tuy nhiên do các số nguyên trong mảng độ dài khác nhau nên khi xuất ra nhìn rất lộn xộn, không biết được số nào ở cột nào. Bạn hãy viết giúp Bình hàm xuất mảng một cách ngay ngắn.\n",
        "\n",
        "**INPUT**\n",
        ">Dòng đầu tiên chứa hai số r và c là số dòng và số cột của mảng, mỗi số không quá 1000.\n",
        ">r dòng tiếp theo, mỗi dòng chứa c số nguyên. Đây là các phần tử trong mảng 2 chiều\n",
        "\n",
        "**OUTPUT**\n",
        ">Mảng 2 chiều được canh lề phải ở các cột. Tức là chữ số cuối cùng của các cột được viết thẳng hàng với nhau. Các chỗ trống được lấp đầy bằng ký tự khoảng trắng\n",
        "\n",
        "Lưu ý là đê đảm bảo chính xác ở cuối mỗi dòng của ma trận chỉ được xuất ký tự xuống dòng, không được xuất khoảng trắng thừa.\n",
        "\n",
        "**VÍ DỤ**<br>\n",
        "\n",
        "|INPUT|OUTPUT|\n",
        "|--|--|\n",
        "|3 3|593795850 925527 97481109|\n",
        "|593795850 925527 97481109|     8190   9258     2323|\n",
        "|8190 9258 2323| -8328541  62240 70544569|\n",
        "|-8328541 62240 70544569| |\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "iEgPUqHEcWyO",
        "outputId": "eb36a928-42be-4e40-b593-4786fa89304c",
        "colab": {
          "base_uri": "https://localhost:8080/"
        }
      },
      "source": [
        "r,c = map(int,input().split())\n",
        "l = []\n",
        "for i in range(r):\n",
        "  l.append(list(map(int,input().split())))\n",
        "\n",
        "\n",
        "for i in range(r):\n",
        "  for j in range(c):\n",
        "    l[i][j] = str(l[i][j])\n",
        "\n",
        "max = []\n",
        "  \n",
        "for j in range(c):\n",
        "  max.append(0)\n",
        "  for i in range(r):\n",
        "    if len(l[i][j]) >= max[j]:\n",
        "      max[j] = len(l[i][j])\n",
        "    else:\n",
        "      max[j] = max[j]\n",
        "for i in range(r):\n",
        "  for j in range(c):   \n",
        "    for m in range(max[j]-len(l[i][j])):\n",
        "      print(\" \", end = \"\")\n",
        "    print(l[i][j],end = ' ')\n",
        "  print(\"\")"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "3 3\n",
            "593795850 925527 97481109\n",
            "8190 9258 2323\n",
            "-8328541 62240 70544569\n",
            "593795850 925527 97481109 \n",
            "     8190   9258     2323 \n",
            " -8328541  62240 70544569 \n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "HmX2H4_ockHf"
      },
      "source": [
        "**Bình luận**: Ở bài toán này cần tìm độ dài kí tự dài nhất ở mỗi cột để thêm số lượng khoảng trắng phù hợp."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "Tj1ku0qfcnHv"
      },
      "source": [
        "# **Chuỗi con Palindrome**\n",
        "Chuỗi Palindrome là chuỗi khi đọc từ trái sang phải hoặc phải sang trái đều giống nhau. Chẳng hạn, aba, bbaabb, abcddcba là các chuỗi palindrome, trong khi mca, tiu không phải. Nhập vào một chuỗi, hãy giúp Bình đếm số chuỗi con palindrome trong chuỗi vừa nhập. Biết chuỗi con là chuỗi có thể được tạo thành bởi một số kí tự liên tiếp từ chuỗi nhập vào. Ví dụ: ab, bcd, ej là chuỗi con của abcdejk, trong khi acde không phải.\n",
        "\n",
        "**INPUT**\n",
        ">Một chuỗi chỉ bao gồm các kí tự thường với độ dài chuỗi bé hơn 1000.\n",
        "\n",
        "**OUTPUT**\n",
        "> Số lượng chuỗi Palindrome có trong chuỗi nhập vào\n",
        "\n",
        "|INPUT|OUTPUT|\n",
        "|--|--|\n",
        "|aba|4|\n",
        "|abba|6|\n",
        "\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "XAk55YvDcyU9",
        "outputId": "d4a114be-4e2b-48dd-f4a6-6963c66c9601",
        "colab": {
          "base_uri": "https://localhost:8080/"
        }
      },
      "source": [
        "n = input()\n",
        "\n",
        "count = 0\n",
        "for i in range(len(n)):\n",
        "  for j in range(i+1,len(n)+1):\n",
        "    temp = n[i:j]\n",
        "    if temp == temp[::-1]:\n",
        "      count += 1\n",
        "\n",
        "print(count)"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "abba\n",
            "6\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "Q11l22vNc_84"
      },
      "source": [
        "**Bình luận**: Ở bài toán này, cần kiểm tra dãy kí tự liên tục để tính số lượng chuỗi con đối xứng."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "QHlIN4VkdE3I"
      },
      "source": [
        "# **Dãy số nguyên**\n",
        "\n",
        "Tất cả các số nguyên dương được viết trên một dòng liên tiếp nhau tạo thành một dãy số có dạng \"123456789101112131415...\".\n",
        "Nhiệm vụ của bạn là in ra chữ số thứ n trong dãy đó (chỉ số đầu tiên là 1).\n",
        "\n",
        "**INPUT:**\n",
        "> Dòng đầu tiên là một số nguyên n $(1≤n≤1000)$ — vị trí chữ số cần in.\n",
        "\n",
        "**OUTPUT:**\n",
        "> In ra màn hình chữ số ở vị trí n trong dãy.\n",
        "\n",
        "**VÍ DỤ:**\n",
        "\n",
        "|INPUT|OUTPUT|\n",
        "|--|--|\n",
        "|3|3|\n",
        "|11|0|"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "c55pMyCqdlmI",
        "outputId": "3adeb182-c03c-464a-82b5-91f8f610234e",
        "colab": {
          "base_uri": "https://localhost:8080/"
        }
      },
      "source": [
        "n = int(input())\n",
        "s = \"\"\n",
        "for i in range(1,n+1):\n",
        "  s = s + str(i)\n",
        "\n",
        "print(s[n-1])"
      ],
      "execution_count": null,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "11\n",
            "0\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "67abs890ou6F"
      },
      "source": [
        "**Bình luận**: Ở bài toán này là thao tác biến số thành dãy chuỗi liên tiếp để tìm vị trí tương ứng."
      ]
    }
  ]
}