Решение заданий Яндекса - vs AI.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![](https://i.imgur.com/N3vRUw8.png)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[2, 2, 2, 2]\n",
      "0\n"
     ]
    }
   ],
   "source": [
    "N, K, t = 6, 4, 2  # всего салютов, нужно взять K штук, обязательно взять t-ый\n",
    "nums = [1, 2, 1, 2, 2, 2]\n",
    "\n",
    "# N, K, t = 5, 3, 1\n",
    "# nums = [4, 1, 5, 6, 2]\n",
    "\n",
    "N, K, t = map(int, input().split())\n",
    "nums = []\n",
    "for _ in range(N):\n",
    "\tnums.append(int(input()))\n",
    "\n",
    "taken = nums.pop(t-1)\n",
    "L = [taken]\n",
    "\n",
    "for r in range(0, 1000):\n",
    "\tfor i, n in enumerate(nums):\n",
    "\t\tif len(L) < K and abs(taken - n) == r:\n",
    "\t\t\tL.append(n)\n",
    "\t\t\tnums[i] = 10**10\n",
    "\n",
    "print(L)\n",
    "print(max(L) - min(L))\t"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![](https://i.imgur.com/1DqkvKC.png)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1\n"
     ]
    }
   ],
   "source": [
    "N = 4\n",
    "AB = [[2, 1], [2, 2], [5, 1], [1, 3]]  # при таких данных 1\n",
    "\n",
    "N = 5\n",
    "AB = [[2, 1], [2, 1], [2, 1], [2, 1], [2, 1]]  # при таких данных 3\n",
    "\n",
    "N = 1\n",
    "AB = [[273, 691]]  # при таких данных 1\n",
    "\n",
    "AB = []\n",
    "N = int(input())\n",
    "for _ in range(N):\n",
    "\ta, b = map(int, input().split())\n",
    "\tAB += [[a, b]]\n",
    "\n",
    "AB.sort(key=sum, reverse=True)\n",
    "\n",
    "sumA = sum([a for a, b in AB])\n",
    "sumB = 0\n",
    "k = 0\n",
    "for a, b in AB:\n",
    "\tif sumB <= sumA:\n",
    "\t\tsumB += a + b\n",
    "\t\tsumA -= a\n",
    "\t\tk += 1\n",
    "\n",
    "print(k)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![](https://i.imgur.com/EDrWcvS.png)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1\n"
     ]
    }
   ],
   "source": [
    "# на этих данных 1\n",
    "N, L = 2, 3 # месяцев в году, дней в неделе\n",
    "D = [4, 5]  # дней в каждом месяце\n",
    "d1, m1, y1, t1 = 1, 1, 1, 1  # день, месяц, год, день недели сегодня\n",
    "d2, m2, y2 = 3, 2, 12        # день, месяц, год затмения\n",
    "\n",
    "# на этих данных 3\n",
    "N, L = 2, 3\n",
    "D = [4, 5]\n",
    "d1, m1, y1, t1 = 1, 1, 1, 1\n",
    "d2, m2, y2 = 2, 2, 2\n",
    "\n",
    "N, L = map(int, input().split())\n",
    "D = list(map(int, input().split()))\n",
    "d1, m1, y1, t1 = map(int, input().split())\n",
    "d2, m2, y2 = map(int, input().split())\n",
    "\n",
    "days = sum(D[m1-1:] + [-d1] + D * (y2 - y1 - 1) + D[:m2] + [d2])\n",
    "print((t1 + days%L) % L + 1)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---"
   ]
  },
  {
   "cell_type": "raw",
   "metadata": {},
   "source": [
    "Новый год — это важный праздник, поэтому одного салюта мало, и Саша решил купить K штук.\n",
    "В магазине продаются N видов салюта, при этом у i-го салюта высота, на которой он взрывается,\n",
    "равна hi.\n",
    "По мнению Саши, чем больше разброс по высоте, тем хуже выглядят взрывы, поэтому он хочет,\n",
    "чтобы разность между максимальной и минимальной высотой салютов была минимальна.\n",
    "Также ему очень нравится, как взрывается салют под номером t, поэтому он его обязательно\n",
    "купит. Помогите Саше посчитать, какую минимальную разность высот он может получить.\n",
    "Формат входных данных\n",
    "В первой строке находятся три целых числа N, K, t (1 ⩽ K, t ⩽ N ⩽ 105), где N — количество\n",
    "салютов, которые есть в магазине, K — число салютов, которое нужно купить, t — номер салюта,\n",
    "который точно необходимо купить.\n",
    "В i-й из следующих N строк находится единственное число hi (1 ⩽ hi ⩽ 109) — высота, на\n",
    "которой взрывается i-й фейерверк.\n",
    "Формат выходных данных\n",
    "Выведите минимальную разность, которую можно получить.\n",
    "\n",
    "Пример входных данных №1:\n",
    "6 4 2\n",
    "1\n",
    "2\n",
    "1\n",
    "2\n",
    "2\n",
    "2\n",
    "\n",
    "При входных данных №1 должен быть вывод:\n",
    "0\n",
    "\n",
    "Пример входных данных №2:\n",
    "5 3 1\n",
    "4\n",
    "1\n",
    "5\n",
    "6\n",
    "2\n",
    "\n",
    "При входных данных №2 должен быть вывод:\n",
    "2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0\n",
      "2\n"
     ]
    }
   ],
   "source": [
    "def minimal_height_difference(N, K, t, heights):\n",
    "    # Индексация t начинается с 1, для удобства работы в Python сделаем -1\n",
    "    t_height = heights[t - 1]\n",
    "    \n",
    "    # Сортируем высоты для удобства поиска минимального диапазона\n",
    "    heights.sort()\n",
    "    \n",
    "    # Находим позицию обязательного салюта в отсортированном списке\n",
    "    t_index = heights.index(t_height)\n",
    "    \n",
    "    # Инициализируем минимальное значение разницы очень большим числом\n",
    "    min_diff = float('inf')\n",
    "    \n",
    "    # Проходим скользящим окном размером K по отсортированному списку\n",
    "    for start in range(N - K + 1):\n",
    "        end = start + K - 1\n",
    "        # Проверяем, содержит ли текущее окно обязательный салют\n",
    "        if start <= t_index <= end:\n",
    "            # Обновляем минимальное значение разницы\n",
    "            current_diff = heights[end] - heights[start]\n",
    "            min_diff = min(min_diff, current_diff)\n",
    "    \n",
    "    return min_diff\n",
    "\n",
    "# Входные данные примеров\n",
    "heights_1 = [1, 2, 1, 2, 2, 2]\n",
    "heights_2 = [4, 1, 5, 6, 2]\n",
    "\n",
    "# Вызов функции и печать результатов\n",
    "print(minimal_height_difference(6, 4, 2, heights_1))  # Ожидается вывод: 0\n",
    "print(minimal_height_difference(5, 3, 1, heights_2))  # Ожидается вывод: 2\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---"
   ]
  },
  {
   "cell_type": "raw",
   "metadata": {},
   "source": [
    "Реши задачу ниже при помощи Python.\n",
    "\n",
    "В далекой-далекой галактике в одном году N месяцев, в i-м из которых Di дней. В одной неделе\n",
    "там не 7, а целых L дней, пронумерованных от 1 до L.\n",
    "Недавно вы узнали, что в день d2 месяца m2 года y2 произошло уникальное солнечное затмение.\n",
    "Вы захотели узнать, на какой день недели пришлось затмение, однако, изучив все доступные вам\n",
    "источники, не смогли найти ответ на этот вопрос.\n",
    "Из-за этого вам самим придется вычислить этот день, основываясь на информации, которую вы\n",
    "знаете про сегодняшний день: сегодня d1-й день m1-го месяца y1-го года и t1-й день недели.\n",
    "Формат входных данных\n",
    "В первой строке ввода находятся два целых числа N и L (1 ⩽ N ⩽ 105, 1 ⩽ L ⩽ 109) — количество\n",
    "месяцев в году и количество дней в неделе соответственно.\n",
    "В следующей строке находятся N целых чисел, i-е из которых равно Di (1 ⩽ Di ⩽ 105) —\n",
    "количество дней в i-м месяце.\n",
    "В третьей строке ввода находятся 4 целых числа, разделенные пробелами: d1, m1, y1 и t1\n",
    "(1 ⩽ y1 ⩽ 105, 1 ⩽ m1 ⩽ N, 1 ⩽ d1 ⩽ Dm1, 1 ⩽ t1 ⩽ L) — день, месяц и год сегодняшнего дня,\n",
    "а также сегодняшний день недели.\n",
    "В четвертой строке ввода находятся 3 целых числа, задающих интересующую вас дату: d2, m2, y2\n",
    "(1 ⩽ y2 ⩽ 105, 1 ⩽ m2 ⩽ N, 1 ⩽ d2 ⩽ Dm2) — день, месяц и год интересного вам дня.\n",
    "Формат выходных данных\n",
    "Выведите единственное число — номер дня недели, на который пришлось затмение.\n",
    "\n",
    "Пример входных данных:\n",
    "2 3\n",
    "4 5\n",
    "1 1 1 1\n",
    "3 2 12\n",
    "\n",
    "При таких данных должен быть вывод:\n",
    "1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "3\n"
     ]
    }
   ],
   "source": [
    "def calculate_day_of_eclipse():\n",
    "    import sys\n",
    "    input = sys.stdin.read\n",
    "    data = input().split()\n",
    "    \n",
    "    index = 0\n",
    "    N, L = int(data[index]), int(data[index+1])\n",
    "    index += 2\n",
    "    \n",
    "    days_in_months = [int(data[i]) for i in range(index, index+N)]\n",
    "    index += N\n",
    "    \n",
    "    d1, m1, y1, t1 = int(data[index]), int(data[index+1]), int(data[index+2]), int(data[index+3])\n",
    "    index += 4\n",
    "    \n",
    "    d2, m2, y2 = int(data[index]), int(data[index+1]), int(data[index+2])\n",
    "    \n",
    "    # Перевести все к единому индексу начала отсчета (0-based)\n",
    "    m1 -= 1\n",
    "    m2 -= 1\n",
    "    d1 -= 1\n",
    "    d2 -= 1\n",
    "    t1 -= 1\n",
    "    \n",
    "    # Функция для подсчета дней от начала эры до конкретной даты\n",
    "    def count_days(y, m, d):\n",
    "        # Сумма дней в полных годах\n",
    "        total_days = sum(days_in_months) * y\n",
    "        # Добавляем дни полных месяцев текущего года\n",
    "        total_days += sum(days_in_months[:m])\n",
    "        # Добавляем дни текущего месяца\n",
    "        total_days += d\n",
    "        return total_days\n",
    "    \n",
    "    # Считаем количество дней с начала эры до обеих дат\n",
    "    days_from_base_to_today = count_days(y1, m1, d1)\n",
    "    days_from_base_to_eclipse = count_days(y2, m2, d2)\n",
    "    \n",
    "    # Разница в днях между двумя датами\n",
    "    days_difference = days_from_base_to_eclipse - days_from_base_to_today\n",
    "    \n",
    "    # Вычисляем день недели затмения\n",
    "    eclipse_day_of_week = (t1 + days_difference) % L\n",
    "    if eclipse_day_of_week < 0:\n",
    "        eclipse_day_of_week += L\n",
    "\n",
    "    # Возвращаем 1-based день недели\n",
    "    return eclipse_day_of_week + 1\n",
    "\n",
    "# Имитация ввода из stdin и вывода результатов\n",
    "import io\n",
    "import sys\n",
    "\n",
    "input_data = \"\"\"2 3\n",
    "4 5\n",
    "1 1 1 1\n",
    "2 2 2\"\"\"\n",
    "\n",
    "sys.stdin = io.StringIO(input_data)\n",
    "print(calculate_day_of_eclipse())\n",
    "\n",
    "# 2 3\n",
    "# 4 5\n",
    "# 1 1 1 1\n",
    "# 2 2 2\n",
    "# "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---"
   ]
  },
  {
   "cell_type": "raw",
   "metadata": {},
   "source": [
    "Реши задачу ниже при помощи Python.\n",
    "\n",
    "В одном городе проходят выборы нового мэра, всего есть два кандидата: Андрей и Борис. Город\n",
    "этот небольшой и в нем есть N районов.\n",
    "Для каждого района известно, сколько человек поддерживает Андрея и Бориса. Борис очень\n",
    "сильно желает победить, поэтому он собирается произнести в некоторых районах речь. Если в i-м\n",
    "районе Борис произносит речь, то все жители этого района голосуют за Бориса. В противном случае,\n",
    "жители, которые поддерживают Андрея, голосуют за него, а остальные избиратели расстраиваются\n",
    "и не голосуют.\n",
    "В выборах побеждает кандидат, набравший строго большее число голосов, чем его соперник.\n",
    "Само собой, Борис очень занятой человек, поэтому хочет посетить минимальное число районов\n",
    "для победы на выборах. Вы, как его помощник, должны вычислить это количество.\n",
    "Формат входных данных\n",
    "В первой строке вводится число районов N (1 ⩽ N ⩽ 2 · 105).\n",
    "В следующих N строках вводятся по два целых числа ai, bi (1 ⩽ ai, bi ⩽ 109) — количество\n",
    "кандидатов, которые поддерживают в i-м районе Андрея и Бориса соответственно.\n",
    "Формат выходных данных\n",
    "Выведите минимальное количество районов, которые должен посетить Борис, чтобы победить\n",
    "на выборах.\n",
    "\n",
    "Пример входных данных №1:\n",
    "4\n",
    "2 1\n",
    "2 2\n",
    "5 1\n",
    "1 3\n",
    "\n",
    "При входных данных №1 должен быть вывод::\n",
    "1\n",
    "\n",
    "Пример входных данных №2:\n",
    "1\n",
    "273 691\n",
    "\n",
    "При входных данных №2 должен быть вывод::\n",
    "1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0\n"
     ]
    }
   ],
   "source": [
    "n = int(input())\n",
    "andrey = 0\n",
    "boris = 0\n",
    "\n",
    "for i in range(n):\n",
    "    a, b = map(int, input().split())\n",
    "    andrey += a\n",
    "    boris += b\n",
    "\n",
    "if andrey > boris:\n",
    "    print(0)\n",
    "else:\n",
    "    print(1)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "4\n"
     ]
    }
   ],
   "source": [
    "n = int(input())\n",
    "districts = []\n",
    "for i in range(n):\n",
    "    a, b = map(int, input().split())\n",
    "    districts.append((a, b))\n",
    "\n",
    "districts.sort(key=lambda x: -x[0])\n",
    "\n",
    "total_andrey = sum(x[0] for x in districts)\n",
    "total_boris = 0\n",
    "ans = 0\n",
    "\n",
    "for i in range(n):\n",
    "    a, b = districts[i]\n",
    "    total_andrey -= a\n",
    "    total_boris += b\n",
    "    ans += 1\n",
    "    if total_boris > total_andrey:\n",
    "        break\n",
    "print(ans)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0\n"
     ]
    }
   ],
   "source": [
    "n = int(input())\n",
    "a = []\n",
    "b = []\n",
    "for i in range(n):\n",
    "    ai, bi = map(int, input().split())\n",
    "    a.append(ai)\n",
    "    b.append(bi)\n",
    "\n",
    "ans = -1\n",
    "for i in range(n):\n",
    "    if sum(b) - sum(a) >= sum(a) - b[i]:\n",
    "        ans = max(ans, i)\n",
    "\n",
    "print(ans + 1)"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.11.5"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}