Problem Set 3.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\n",
    "# Программирование на языке Python для сбора и анализа данных\n",
    "*Семинары ведут: Щуров И.В., Будылин Р.Я., НИУ ВШЭ*\n",
    "\n",
    "Данный notebook является набором задач по курсу \n",
    "«Программирование на языке Python для сбора и анализа данных» \n",
    "(НИУ ВШЭ, 2014-15). Тексты задач взяты с сайта http://informatics.mccme.ru/. \n",
    "На [странице курса](http://math-info.hse.ru/s15/m) находятся другие материалы."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Домашнее задание №3\n",
    "За разные задачи можно получить разное число баллов. Максимум за ДЗ можно набрать 14 баллов. Вы можете решить больше задач, чем требуется, чтобы набрать 14 баллов, чтобы подстраховаться."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### [Задача A](http://informatics.mccme.ru/mod/statements/view3.php?id=17062&chapterid=2959) (1 балл)\n",
    "\n",
    "<div class=\"problem-statement\">\n",
    "<div class=\"legend\">\n",
    "<p>В математике функция sign(x) (знак числа) определена так: <br/>sign(x) = 1,   если x &gt; 0, <br/>sign(x) = -1, если x &lt; 0, <br/>sign(x) = 0,   если x = 0.  </p>Для данного числа x выведите значение sign(x).\n",
    "\n",
    "   </div>\n",
    "<div class=\"input-specification\">\n",
    "<div class=\"section-title\">\n",
    "     <strong>Входные данные</strong>\n",
    "    </div>\n",
    "<p>Вводится число x. </p>\n",
    "</div>\n",
    "<div class=\"output-specification\">\n",
    "<div class=\"section-title\">\n",
    "     <strong>Выходные данные</strong>\n",
    "    </div>\n",
    "<p>Выведите ответ на задачу.</p>\n",
    "</div>\n",
    "</div><div class=\"problem-statement\"><div class=\"sample-tests\"><div class=\"section-title\"><strong>Примеры</strong></div><div class=\"sample-test\"><div class=\"input\"><div class=\"title\"><strong>Входные данные</strong></div><pre class=\"content\">179\n",
    "</pre></div><div class=\"output\"><div class=\"title\"><strong>Выходные данные</strong></div><pre class=\"content\">1\n",
    "</pre></div></div></div></div>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### [Задача B](http://informatics.mccme.ru/mod/statements/view3.php?id=17062&chapterid=3504) (1 балл)\n",
    "\n",
    "<div class=\"problem-statement\">\n",
    "<div class=\"legend\">\n",
    "<p>Дано натуральное число. Требуется определить, является ли год с данным номером високосным. Если год является високосным,\n",
    "то выведите <code>YES</code>, иначе выведите <code>NO</code>.\n",
    "Напомним, что в соответствии с григорианским календарем, год является високосным, если его номер кратен 4, но не кратен 100, а также если он кратен 400.</p>\n",
    "</div>\n",
    "<div class=\"input-specification\">\n",
    "<div class=\"section-title\">\n",
    "     <strong>Входные данные</strong>\n",
    "    </div>\n",
    "<p>Вводится одно натуральное число.</p>\n",
    "</div>\n",
    "<div class=\"output-specification\">\n",
    "<div class=\"section-title\">\n",
    "     <strong>Выходные данные</strong>\n",
    "    </div>\n",
    "<p>Выведите ответ на задачу.</p>\n",
    "</div>\n",
    "</div><div class=\"problem-statement\"><div class=\"sample-tests\"><div class=\"section-title\"><strong>Примеры</strong></div><div class=\"sample-test\"><div class=\"input\"><div class=\"title\"><strong>Входные данные</strong></div><pre class=\"content\">100\n",
    "</pre></div><div class=\"output\"><div class=\"title\"><strong>Выходные данные</strong></div><pre class=\"content\">NO\n",
    "</pre></div></div></div></div>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### [Задача C](http://informatics.mccme.ru/mod/statements/view3.php?id=17062&chapterid=3505) (2 балла)\n",
    "\n",
    "<div class=\"problem-statement\">\n",
    "<div class=\"legend\">\n",
    "<p>Даны три целых числа. Найдите наибольшее из них (программа должна вывести ровно одно целое число).\n",
    "\n",
    "</p>\n",
    "<p><b>Внимание!</b> Здесь запрещено использовать функции `min`, `max` и им подобные.\n",
    "\n",
    "<p>Какое наименьшее число операторов сравнения (&gt;, &lt;, &gt;=, &lt;=) необходимо для решения этой задачи?\n",
    "\n",
    "   </p></div>\n",
    "<div class=\"input-specification\">\n",
    "<div class=\"section-title\">\n",
    "     <strong>Входные данные</strong>\n",
    "    </div>\n",
    "<p>Вводится три целых числа.</p>\n",
    "</div>\n",
    "<div class=\"output-specification\">\n",
    "<div class=\"section-title\">\n",
    "     <strong>Выходные данные</strong>\n",
    "    </div>\n",
    "<p>Выведите ответ на задачу.</p>\n",
    "</div>\n",
    "</div><div class=\"problem-statement\"><div class=\"sample-tests\"><div class=\"section-title\"><strong>Примеры</strong></div><div class=\"sample-test\"><div class=\"input\"><div class=\"title\"><strong>Входные данные</strong></div><pre class=\"content\">1\n",
    "2\n",
    "3\n",
    "</pre></div><div class=\"output\"><div class=\"title\"><strong>Выходные данные</strong></div><pre class=\"content\">3\n",
    "</pre></div></div></div></div>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### [Задача D](http://informatics.mccme.ru/mod/statements/view3.php?id=17062&chapterid=3507) (2 балла)\n",
    "\n",
    "<div class=\"problem-statement\">\n",
    "<div class=\"legend\">\n",
    "<p>Даны три целых числа. Определите, сколько среди них совпадающих. Программа должна вывести одно из чисел: 3 (если все совпадают), 2 (если два совпадает) или 0 (если все числа различны).\n",
    "\n",
    "   </p>\n",
    "   <p>**Внимание**! Здесь запрещено использовать множества (`sets`), словари и прочие продвинутые методы языка. Решение должно быть основано на операторе `if`.</p>\n",
    "   </div>\n",
    "<div class=\"input-specification\">\n",
    "<div class=\"section-title\">\n",
    "     <strong>Входные данные</strong>\n",
    "    </div>\n",
    "<p>Вводятся три целых числа.</p>\n",
    "</div>\n",
    "<div class=\"output-specification\">\n",
    "<div class=\"section-title\">\n",
    "     <strong>Выходные данные</strong>\n",
    "    </div>\n",
    "<p>Выведите ответ на задачу.</p>\n",
    "</div>\n",
    "</div><div class=\"problem-statement\"><div class=\"sample-tests\"><div class=\"section-title\"><strong>Примеры</strong></div><div class=\"sample-test\"><div class=\"input\"><div class=\"title\"><strong>Входные данные</strong></div><pre class=\"content\">1\n",
    "2\n",
    "3\n",
    "\n",
    "</pre></div><div class=\"output\"><div class=\"title\"><strong>Выходные данные</strong></div><pre class=\"content\">0\n",
    "</pre></div></div></div></div>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### [Задача E](http://informatics.mccme.ru/mod/statements/view3.php?id=17062&chapterid=3512) (3 балла)\n",
    "\n",
    "<div class=\"problem-statement\">\n",
    "<div class=\"legend\">\n",
    "<p>Шахматный ферзь ходит по диагонали, горизонтали или вертикали. Даны две различные клетки шахматной доски, определите,\n",
    "может ли ферзь попасть с первой клетки на вторую одним ходом. </p>\n",
    "</div>\n",
    "<div class=\"input-specification\">\n",
    "<div class=\"section-title\">\n",
    "     <strong>Входные данные</strong>\n",
    "    </div>\n",
    "<p>Программа получает на вход четыре числа\n",
    "от 1 до 8 каждое, задающие номер столбца и номер строки сначала для первой клетки, потом для второй клетки.</p>\n",
    "</div>\n",
    "<div class=\"output-specification\">\n",
    "<div class=\"section-title\">\n",
    "     <strong>Выходные данные</strong>\n",
    "    </div>\n",
    "<p>Программа должна вывести <code>YES</code>, если из первой клетки ходом ферзя можно попасть во вторую или <code>NO</code> в противном случае.</p>\n",
    "</div>\n",
    "</div><div class=\"problem-statement\"><div class=\"sample-tests\"><div class=\"section-title\"><strong>Примеры</strong></div><div class=\"sample-test\"><div class=\"input\"><div class=\"title\"><strong>Входные данные</strong></div><pre class=\"content\">1\n",
    "1\n",
    "2\n",
    "2\n",
    "\n",
    "</pre></div><div class=\"output\"><div class=\"title\"><strong>Выходные данные</strong></div><pre class=\"content\">YES\n",
    "</pre></div></div><div class=\"sample-test\"><div class=\"input\"><div class=\"title\"><strong>Входные данные</strong></div><pre class=\"content\">1\n",
    "1\n",
    "2\n",
    "3\n",
    "</pre></div><div class=\"output\"><div class=\"title\"><strong>Выходные данные</strong></div><pre class=\"content\">NO\n",
    "</pre></div></div></div></div>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### [Задача F](http://informatics.mccme.ru/mod/statements/view3.php?id=17062&chapterid=3517) (3 балла)\n",
    "\n",
    "<div class=\"problem-statement\">\n",
    "<div class=\"legend\">\n",
    "<p>Для данного числа n&lt;100 закончите фразу “На лугу пасется...”\n",
    "одним из возможных продолжений: “n коров”, “n корова”, “n коровы”,\n",
    "правильно склоняя слово “корова”.</p>\n",
    "</div>\n",
    "<div class=\"input-specification\">\n",
    "<div class=\"section-title\">\n",
    "     <strong>Входные данные</strong>\n",
    "    </div>\n",
    "<p>Вводится натуральное число.</p>\n",
    "</div>\n",
    "<div class=\"output-specification\">\n",
    "<div class=\"section-title\">\n",
    "     <strong>Выходные данные</strong>\n",
    "    </div>\n",
    "<p>Программа должна вывести введенное число n и одно из слов: <code>korov</code>, <code>korova</code>\n",
    "или <code>korovy</code>. Между числом и словом должен стоять ровно один пробел.</p>\n",
    "</div>\n",
    "</div><div class=\"problem-statement\"><div class=\"sample-tests\"><div class=\"section-title\"><strong>Примеры</strong></div><div class=\"sample-test\"><div class=\"input\"><div class=\"title\"><strong>Входные данные</strong></div><pre class=\"content\">1\n",
    "</pre></div><div class=\"output\"><div class=\"title\"><strong>Выходные данные</strong></div><pre class=\"content\">1 korova\n",
    "</pre></div></div><div class=\"sample-test\"><div class=\"input\"><div class=\"title\"><strong>Входные данные</strong></div><pre class=\"content\">2\n",
    "</pre></div><div class=\"output\"><div class=\"title\"><strong>Выходные данные</strong></div><pre class=\"content\">2 korovy\n",
    "</pre></div></div><div class=\"sample-test\"><div class=\"input\"><div class=\"title\"><strong>Входные данные</strong></div><pre class=\"content\">5\n",
    "</pre></div><div class=\"output\"><div class=\"title\"><strong>Выходные данные</strong></div><pre class=\"content\">5 korov\n",
    "</pre></div></div></div></div>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### [Задача G](http://informatics.mccme.ru/mod/statements/view3.php?id=17062&chapterid=3619) (2 балла)\n",
    "\n",
    "<div class=\"problem-statement\">\n",
    "<div class=\"legend\">\n",
    "<p>Даны произвольные действительные коэффициенты $a$, $b$, $c$. Решите уравнение\n",
    "$ax^2+bx+c=0$.\n",
    "\n",
    "   </p></div>\n",
    "<div class=\"input-specification\">\n",
    "<div class=\"section-title\">\n",
    "     <strong>Входные данные</strong>\n",
    "    </div>\n",
    "<p>Вводятся три действительных числа.</p>\n",
    "</div>\n",
    "<div class=\"output-specification\">\n",
    "<div class=\"section-title\">\n",
    "     <strong>Выходные данные</strong>\n",
    "    </div>\n",
    "<p>Если данное уравнение не имеет корней, выведите число 0. Если уравнение\n",
    "имеет один корень, выведите число 1, а затем этот корень. Если уравнение имеет\n",
    "два корня, выведите число 2, а затем два корня в порядке возрастания. Если уравнение\n",
    "имеет бесконечно много корней, выведите число 3.</p>\n",
    "</div>\n",
    "</div><div class=\"problem-statement\"><div class=\"sample-tests\"><div class=\"section-title\"><strong>Примеры</strong></div><div class=\"sample-test\"><div class=\"input\"><div class=\"title\"><strong>Входные данные</strong></div><pre class=\"content\">1\n",
    "-1\n",
    "-2\n",
    "</pre></div><div class=\"output\"><div class=\"title\"><strong>Выходные данные</strong></div><pre class=\"content\">2 -1 2\n",
    "</pre></div></div><div class=\"sample-test\"><div class=\"input\"><div class=\"title\"><strong>Входные данные</strong></div><pre class=\"content\">1\n",
    "2\n",
    "1\n",
    "</pre></div><div class=\"output\"><div class=\"title\"><strong>Выходные данные</strong></div><pre class=\"content\">1 -1\n",
    "</pre></div></div></div></div>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### [Задача H](http://informatics.mccme.ru/mod/statements/view3.php?id=17062&chapterid=3642) (1 балл)\n",
    "\n",
    "<div class=\"problem-statement\">\n",
    "<div class=\"legend\">\n",
    "<p>По данному целому числу N распечатайте все квадраты натуральных чисел,\n",
    "не превосходящие N, в порядке возрастания.</p>\n",
    "</div>\n",
    "<div class=\"input-specification\">\n",
    "<div class=\"section-title\">\n",
    "     <strong>Входные данные</strong>\n",
    "    </div>\n",
    "<p>Вводится натуральное число.</p>\n",
    "</div>\n",
    "<div class=\"output-specification\">\n",
    "<div class=\"section-title\">\n",
    "     <strong>Выходные данные</strong>\n",
    "    </div>\n",
    "<p>Выведите ответ на задачу.</p>\n",
    "</div>\n",
    "</div><div class=\"problem-statement\"><div class=\"sample-tests\"><div class=\"section-title\"><strong>Примеры</strong></div><div class=\"sample-test\"><div class=\"input\"><div class=\"title\"><strong>Входные данные</strong></div><pre class=\"content\">50\n",
    "</pre></div><div class=\"output\"><div class=\"title\"><strong>Выходные данные</strong></div><pre class=\"content\">1 4 9 16 25 36 49 \n",
    "</pre></div></div></div></div>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### [Задача I](http://informatics.mccme.ru/mod/statements/view3.php?id=17062&chapterid=3643) (1 балл)\n",
    "\n",
    "<div class=\"problem-statement\">\n",
    "<div class=\"legend\">\n",
    "<p>Дано целое число, не меньшее 2. Выведите его наименьший натуральный делитель, отличный от 1.</p>\n",
    "</div>\n",
    "<div class=\"input-specification\">\n",
    "<div class=\"section-title\">\n",
    "     <strong>Входные данные</strong>\n",
    "    </div>\n",
    "<p>Вводится целое положительное число.</p>\n",
    "</div>\n",
    "<div class=\"output-specification\">\n",
    "<div class=\"section-title\">\n",
    "     <strong>Выходные данные</strong>\n",
    "    </div>\n",
    "<p>Выведите ответ на задачу.</p>\n",
    "</div>\n",
    "</div><div class=\"problem-statement\"><div class=\"sample-tests\"><div class=\"section-title\"><strong>Примеры</strong></div><div class=\"sample-test\"><div class=\"input\"><div class=\"title\"><strong>Входные данные</strong></div><pre class=\"content\">15\n",
    "</pre></div><div class=\"output\"><div class=\"title\"><strong>Выходные данные</strong></div><pre class=\"content\">3\n",
    "</pre></div></div></div></div>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### [Задача J](http://informatics.mccme.ru/mod/statements/view3.php?id=17062&chapterid=3648) (2 балла)\n",
    "\n",
    "<div class=\"problem-statement\">\n",
    "<div class=\"legend\">\n",
    "<p>Вклад в банке составляет \\(x\\) рублей. Ежегодно он увеличивается на \\(p\\) процентов,\n",
    "после чего дробная часть копеек отбрасывается. Определите, через сколько лет вклад составит не менее \\(y\\) рублей.</p>\n",
    "</div>\n",
    "<div class=\"input-specification\">\n",
    "<div class=\"section-title\">\n",
    "     <strong>Входные данные</strong>\n",
    "    </div>\n",
    "<p>Программа получает на вход три натуральных числа: \\(x\\), \\(p\\), \\(y\\).</p>\n",
    "</div>\n",
    "<div class=\"output-specification\">\n",
    "<div class=\"section-title\">\n",
    "     <strong>Выходные данные</strong>\n",
    "    </div>\n",
    "<p>Программа должна вывести одно целое число.</p>\n",
    "</div>\n",
    "</div><div class=\"problem-statement\"><div class=\"sample-tests\"><div class=\"section-title\"><strong>Примеры</strong></div><div class=\"sample-test\"><div class=\"input\"><div class=\"title\"><strong>Входные данные</strong></div><pre class=\"content\">100\n",
    "10\n",
    "200\n",
    "</pre></div><div class=\"output\"><div class=\"title\"><strong>Выходные данные</strong></div><pre class=\"content\">8\n",
    "</pre></div></div></div></div>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### [Задача K](http://informatics.mccme.ru/mod/statements/view3.php?id=17062&chapterid=3660) (2 балла)\n",
    "\n",
    "<div class=\"problem-statement\">\n",
    "<div class=\"legend\">\n",
    "<p>Последовательность Фибоначчи определяется так:\n",
    "\n",
    "$$\n",
    "\\varphi_0=0, \\varphi_1=1, ..., \\varphi_{n}=\\varphi_{n-1}+\\varphi_{n-2}.\n",
    "$$\n",
    "</p>\n",
    "<p>Дано натуральное число $A$. Определите, каким по счету числом Фибоначчи оно является,\n",
    "то есть выведите такое число $n$, что \n",
    "<br/>\n",
    "$$\\varphi_n=A.$$ \n",
    "<br/>\n",
    "Если $А$ не является числом Фибоначчи,\n",
    "выведите число -1.</p>\n",
    "</div>\n",
    "<div class=\"input-specification\">\n",
    "<div class=\"section-title\">\n",
    "     <strong>Входные данные</strong>\n",
    "    </div>\n",
    "<p>Вводится натуральное число A.</p>\n",
    "</div>\n",
    "<div class=\"output-specification\">\n",
    "<div class=\"section-title\">\n",
    "     <strong>Выходные данные</strong>\n",
    "    </div>\n",
    "<p>Выведите ответ на задачу.</p>\n",
    "</div>\n",
    "</div><div class=\"problem-statement\"><div class=\"sample-tests\"><div class=\"section-title\"><strong>Примеры</strong></div><div class=\"sample-test\"><div class=\"input\"><div class=\"title\"><strong>Входные данные</strong></div><pre class=\"content\">8\n",
    "</pre></div><div class=\"output\"><div class=\"title\"><strong>Выходные данные</strong></div><pre class=\"content\">6\n",
    "</pre></div></div><div class=\"sample-test\"><div class=\"input\"><div class=\"title\"><strong>Входные данные</strong></div><pre class=\"content\">10\n",
    "</pre></div><div class=\"output\"><div class=\"title\"><strong>Выходные данные</strong></div><pre class=\"content\">-1\n",
    "</pre></div></div></div></div>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### [Задача L](http://informatics.mccme.ru/mod/statements/view3.php?id=17062&chapterid=3667) (5 балла)\n",
    "\n",
    "<div class=\"problem-statement\">\n",
    "<div class=\"legend\">\n",
    "<p>У исполнителя “Водолей” есть два сосуда, первый объемом A литров,\n",
    "второй объемом B литров, а также кран с водой. Водолей может выполнять следующие\n",
    "операции:</p>\n",
    "<ol>\n",
    "<li>Наполнить сосуд A (обозначается <code>&gt;A</code>).\n",
    "\n",
    "</li><li>Наполнить сосуд B (обозначается <code>&gt;B</code>).\n",
    "</li><li>Вылить воду из сосуда A (обозначается <code>A&gt;</code>).\n",
    "</li><li>Вылить воду из сосуда B (обозначается <code>B&gt;</code>).\n",
    "</li><li>Перелить воду из сосуда A в сосуд B (обозначается как <code>A&gt;B</code>).\n",
    "</li><li>Перелить воду из сосуда B в сосуд A (обозначается как <code>B&gt;A</code>).\n",
    "\n",
    "</li></ol>\n",
    "<p>Команда переливания из одного сосуда в другой приводят к тому, что либо первый сосуд полностью\n",
    "опустошается, либо второй сосуд полность наполняется.</p>\n",
    "</div>\n",
    "<div class=\"input-specification\">\n",
    "<div class=\"section-title\">\n",
    "     <strong>Входные данные</strong>\n",
    "    </div>\n",
    "<p>Программа получает на вход три натуральных числа A, B, N, не превосходящих 10<sup>4</sup>.</p>\n",
    "</div>\n",
    "<div class=\"output-specification\">\n",
    "<div class=\"section-title\">\n",
    "     <strong>Выходные данные</strong>\n",
    "    </div>\n",
    "<p>Необходимо вывести алгоритм действий Водолея, который позволяет получить в точности N литров\n",
    "в одном из сосудов, если же такого алгоритма не существует, то программа должна вывести текст <code>Impossible</code>.</p>\n",
    "<p>Количество операций в алгоритме не должно превышать 10<sup>5</sup>. Гарантируется,\n",
    "что если задача имеет решение, то есть решение, которое содержит не более, чем 10<sup>5</sup> операций.\n",
    "\n",
    "</p><p>Тесты к этой задаче закрытые.</p>\n",
    "</div>\n",
    "</div><div class=\"problem-statement\"><div class=\"sample-tests\"><div class=\"section-title\"><strong>Примеры</strong></div><div class=\"sample-test\"><div class=\"input\"><div class=\"title\"><strong>Входные данные</strong></div><pre class=\"content\">3\n",
    "5\n",
    "1\n",
    "</pre></div><div class=\"output\"><div class=\"title\"><strong>Выходные данные</strong></div><pre class=\"content\">&gt;A\n",
    "A&gt;B\n",
    "&gt;A\n",
    "A&gt;B\n",
    "</pre></div></div><div class=\"sample-test\"><div class=\"input\"><div class=\"title\"><strong>Входные данные</strong></div><pre class=\"content\">3\n",
    "5\n",
    "6\n",
    "</pre></div><div class=\"output\"><div class=\"title\"><strong>Выходные данные</strong></div><pre class=\"content\">Impossible\n",
    "</pre></div></div></div></div>"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language": "python",
  "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.4.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}