05.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Палиндромы-3\n",
    "Вася продолжает изучать палиндромы и искать их вокруг себя в повседневной жизни, вот только нигде их не находит. Тогда он решает, что не стоит искать палиндромы, когда их можно делать! Вася задался вопросом: какое минимальное количество символов нужно приписать к строке слева или справа так, чтобы она стала палиндромом.\n",
    "##### Формат ввода:\n",
    "Строка, состоящая из строчных латинских символов, длина строки не превосходит $1000$.\n",
    "##### Формат вывода:\n",
    "Выведите минимальное количество символов, которое необходимо дописать.\n",
    "### Пример\n",
    "##### Ввод:\n",
    "---\n",
    "    bcba\n",
    "---\n",
    "##### Вывод:\n",
    "---\n",
    "    1\n",
    "---"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "bcba\n",
      "1\n"
     ]
    }
   ],
   "source": [
    "string = raw_input()\n",
    "\n",
    "i = 0\n",
    "right = string\n",
    "left = string\n",
    "\n",
    "while right[::-1] != right and left[::-1] != left: # пока ОБА слова НЕ палиндромы\n",
    "    right = string + string[:i + 1][::-1] # дописываем к введенной строке справа ее начальный срез в обратном порядке\n",
    "    left = string[::-1][:i + 1] + string  # дописываем к введенной строке слева ее хвостовой срез в обратном порядке\n",
    "    i = i + 1\n",
    "\n",
    "print i"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---\n",
    "## Записи Майя\n",
    "Вася недавно читал статью про найденные росписи Майя и угадал в приведенных в статье рисунках скобочные последовательности. Чтобы проверить свою догадку, он решил проверить их правильность.\n",
    "##### Формат ввода:\n",
    "В единственной строке входного файла дана скобочная последовательность из двух символов: '(' и ')'. Длина строки не превосходит $1000$.\n",
    "##### Формат вывода:\n",
    "Выведите YES, если скобочная последовательность является правильной, и NO в противном случае.\n",
    "### Пример\n",
    "##### Ввод:\n",
    "---\n",
    "    ()\n",
    "---\n",
    "##### Вывод:\n",
    "---\n",
    "    YES\n",
    "---"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "()\n",
      "YES\n"
     ]
    }
   ],
   "source": [
    "string = raw_input()\n",
    "\n",
    "balance = 0\n",
    "\n",
    "for character in string:\n",
    "    if character == '(':\n",
    "        balance += 1\n",
    "    elif character == ')':\n",
    "        balance -= 1\n",
    "        if balance < 0:\n",
    "            break\n",
    "            \n",
    "if balance == 0:\n",
    "    print \"YES\"\n",
    "else:\n",
    "    print \"NO\""
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---\n",
    "## Летняя подработка\n",
    "Летом Вася решил не терять времени зря и отправился работать редактором в районную газету. Но он даже не представлял, насколько неграмотны авторы, которые подают свои статьи на печать! Чтобы хоть как-то сократить объем работы, Вася решил автоматизировать процесс. Для начала он решил начать проверять правильность расстановки кавычек в текстах автоматически.\n",
    "Статьи, которые поступают Васе, содержат два типа кавычек — двойные и одинарные. Вася хочет проверить, что кавычки расставлены хотя бы корректно, на смысл их расстановки он собирается смотреть уже в ручном режиме.\n",
    "##### Формат ввода:\n",
    "Входной файл содержит текст, возможно, на нескольких строках, который состоит из латинских символов (строчных и заглавных), знаков препинания, цифр и кавычек.\n",
    "##### Формат вывода:\n",
    "Вам требуется вывести YES, если расстановка кавычек корректна, и NO в противном случае.\n",
    "### Пример\n",
    "##### Ввод:\n",
    "---\n",
    "     \"At the end of Kirils presentation he wrote\n",
    "    as a conclusion 'I hate milkshakes'  among real stuff\"\n",
    "---\n",
    "##### Вывод:\n",
    "---\n",
    "    YES\n",
    "---"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      " \"At the end of Kirils presentation he wrote as a conclusion 'I hate milkshakes'  among real stuff\"\n",
      "YES\n"
     ]
    }
   ],
   "source": [
    "string = raw_input()\n",
    "\n",
    "stack = []\n",
    "\n",
    "def valid_stack(stack):\n",
    "    if len(stack) == 4:\n",
    "        if not (stack[0] == stack[3] and stack[1] == stack[2]): # проверяем стэк на правильную расстановку кавычек\n",
    "            return False\n",
    "        stack[:] = [] # очищаем стэк, если кавычки были расставлены верно\n",
    "    return True\n",
    "\n",
    "def check_quotes(string):\n",
    "    for character in string:\n",
    "        if character == '\\\"' or character == '\\'':\n",
    "            stack.append(character) # кладем в стэк встретившуюся кавычку\n",
    "            if not valid_stack(stack):\n",
    "                return False\n",
    "    if stack: # стэк не пуст, не хватает кавычек\n",
    "        return False\n",
    "    return True\n",
    "\n",
    "if check_quotes(string):\n",
    "    print \"YES\"\n",
    "else:\n",
    "    print \"NO\""
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---\n",
    "## Закон Бенфорда\n",
    "Закон Бенфорда утверждает, что вероятность появления цифры *d* в качестве первой значащей цифры (в десятичной системе счисления) равна ![benford law](https://official.contest.yandex.ru/testsys/tex/render/XGxvZ197MTB9XGxlZnQoMSArIFxmcmFjezF9e2R9XHJpZ2h0KQ==.png) Вася хочет это проверить, и просит Вас посчитать эту функцию для его текста.\n",
    "##### Формат ввода:\n",
    "Текст, состоящий из слов из символов латинского алфавита, знаков препинания и целых положительных чисел (т.е. числа отделены от слов и друг от друга пробелами и/или знаками препинания), длиной не более $10000$ символов.\n",
    "##### Формат вывода:\n",
    "$9$ строк, по $2$ вещественных числа (с точностью $10^{-6}$) в каждой - вероятность (долю) единицы, двойки и т.д. в качестве первой значащей цифры в числе, и по закону Бенфорда.\n",
    "### Пример\n",
    "##### Ввод:\n",
    "---\n",
    "    The tallest man-made structure is Burj Khalifa, a skyscraper in Dubai that reached 829 m (2722 ft) in height on January 17, 2009. By April 7, 2008 it had been built higher than the KVLY-TV mast in North Dakota, USA. That September it officially surpassed Poland's 646 m (2120 ft) Warsaw radio mast, which stood from 1974 to 1991, to become the tallest structure ever built. Guyed lattice towers such as these masts had held the world height record since 1954.\n",
    "\n",
    "    The CN Tower in Toronto, Canada, standing at 553 m (1815 ft), was formerly the world's tallest completed freestanding structure on land. Opened in 1976, it was surpassed in height by the rising Burj Khalifa on September 12, 2007. It has the world's highest public observation deck at 446 m (1465 ft).\n",
    "---\n",
    "##### Вывод:\n",
    "---\n",
    "    0.444444 0.30103\n",
    "    0.277778 0.176091\n",
    "    0.0 0.124939\n",
    "    0.055556 0.09691\n",
    "    0.055556 0.079181\n",
    "    0.055556 0.066947\n",
    "    0.055556 0.057992\n",
    "    0.055556 0.051153\n",
    "    0.0 0.045757\n",
    "---"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "The tallest man-made structure is Burj Khalifa, a skyscraper in Dubai that reached 829 m (2722 ft) in height on January 17, 2009. By April 7, 2008 it had been built higher than the KVLY-TV mast in North Dakota, USA. That September it officially surpassed Poland's 646 m (2120 ft) Warsaw radio mast, which stood from 1974 to 1991, to become the tallest structure ever built. Guyed lattice towers such as these masts had held the world height record since 1954.  The CN Tower in Toronto, Canada, standing at 553 m (1815 ft), was formerly the world's tallest completed freestanding structure on land. Opened in 1976, it was surpassed in height by the rising Burj Khalifa on September 12, 2007. It has the world's highest public observation deck at 446 m (1465 ft).\n",
      "0.44444 0.30103\n",
      "0.27778 0.17609\n",
      "0.0 0.12494\n",
      "0.055556 0.09691\n",
      "0.055556 0.079181\n",
      "0.055556 0.066947\n",
      "0.055556 0.057992\n",
      "0.055556 0.051153\n",
      "0.0 0.045757\n"
     ]
    }
   ],
   "source": [
    "import re, math\n",
    "\n",
    "string = raw_input()\n",
    "\n",
    "digits = re.findall(\"[0-9]+\", string)\n",
    "digits = [digit[0] for digit in digits]\n",
    "total = len(digits)\n",
    "\n",
    "for character in \"123456789\":\n",
    "    print \"{:.5} {:.5}\".format(float(digits.count(character)) / total, math.log10(1 + 1.0 / int(character)))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---\n",
    "## Списывание \n",
    "Вася решил помочь своему другу Ване сдать экзамен. Поскольку разговаривать в аудитории во время экзамена строго запрещено, ребята решили использовать старый проверенный прием — азбуку Морзе. Однако, учить ее у Васи нет времени. Помогите ему и переведите текст, который он хочет передать.\n",
    "##### Формат ввода:\n",
    "Текст, который Вася хочет передать Ване. Он целиком состоит из слов, записанных строчными латинскими буквами, разделенных ровно одним пробелом.\n",
    "##### Формат вывода:\n",
    "Выведите тот же самый текст с помощью азбуки Морзе.\n",
    "### Пример\n",
    "##### Ввод:\n",
    "---\n",
    "    the space between parts of the same letter is equal to one dot\n",
    "---\n",
    "##### Вывод:\n",
    "---\n",
    "    -   ....   .     ...   .--.   .-   -.-.   .     -...   .   -   .--   .   .   -.     .--.   .-   .-.   -   ...     ---   ..-.     -   ....   .     ...   .-   --   .     .-..   .   -   -   .   .-.     ..   ...     .   --.-   ..-   .-   .-..     -   ---     ---   -.   .     -..   ---   -\n",
    "---"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "the space between parts of the same letter is equal to one dot\n",
      "-   ....   .     ...   .--.   .-   -.-.   .     -...   .   -   .--   .   .   -.     .--.   .-   .-.   -   ...     ---   ..-.     -   ....   .     ...   .-   --   .     .-..   .   -   -   .   .-.     ..   ...     .   --.-   ..-   .-   .-..     -   ---     ---   -.   .     -..   ---   -\n"
     ]
    }
   ],
   "source": [
    "string = raw_input()\n",
    "\n",
    "to_morze_map = {\n",
    "    'a': '.-',\n",
    "    'b': '-...',\n",
    "    'c': '-.-.',\n",
    "    'd': '-..',\n",
    "    'e': '.',\n",
    "    'f': '..-.',\n",
    "    'g': '--.',\n",
    "    'h': '....',\n",
    "    'i': '..',\n",
    "    'j': '.---',\n",
    "    'k': '-.-',\n",
    "    'l': '.-..',\n",
    "    'm': '--',\n",
    "    'n': '-.',\n",
    "    'o': '---',\n",
    "    'p': '.--.',\n",
    "    'q': '--.-',\n",
    "    'r': '.-.',\n",
    "    's': '...',\n",
    "    't': '-',\n",
    "    'u': '..-',\n",
    "    'v': '...-',\n",
    "    'w': '.--',\n",
    "    'x': '-..-',\n",
    "    'y': '-.--',\n",
    "    'z': '--..'\n",
    "}\n",
    "\n",
    "def to_morze(string):\n",
    "    output = \"\"\n",
    "    for character in string.lower():\n",
    "        if character == ' ':\n",
    "            output += \"  \"\n",
    "        else:\n",
    "            output += to_morze_map[character] + \"   \"\n",
    "    return output.strip()\n",
    "\n",
    "print to_morze(string)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---\n",
    "## Списывание-2\n",
    "Вася и Ваня договорились общаться во время экзамена с помощью азбуки Морзе. И если Васе вы уже помогли в предыдущей задаче, то Ваня пока остался не у дел. Помогите ему сдать экзамен на отлично!\n",
    "##### Формат ввода:\n",
    "Входной файл содержит сообщение, записанное с помощью азбуки Морзе, которое Ваня получил от Васи. Гарантируется, что закодированный текст состоит из слов, записанных строчными латинскими символами, разделенных ровно одним пробелом.\n",
    "##### Формат вывода:\n",
    "Переведите это сообщение обратно в человекочитаемый формат.\n",
    "### Пример\n",
    "##### Ввод:\n",
    "---\n",
    "    -   ....   .     ...   .--.   .-   -.-.   .     -...   .   -   .--   .   .   -.     .--.   .-   .-.   -   ...     ---   ..-.     -   ....   .     ...   .-   --   .     .-..   .   -   -   .   .-.     ..   ...     .   --.-   ..-   .-   .-..     -   ---     ---   -.   .     -..   ---   -\n",
    "---\n",
    "##### Вывод:\n",
    "---\n",
    "    the space between parts of the same letter is equal to one dot\n",
    "---"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "-   ....   .     ...   .--.   .-   -.-.   .     -...   .   -   .--   .   .   -.     .--.   .-   .-.   -   ...     ---   ..-.     -   ....   .     ...   .-   --   .     .-..   .   -   -   .   .-.     ..   ...     .   --.-   ..-   .-   .-..     -   ---     ---   -.   .     -..   ---   -\n",
      "the space between parts of the same letter is equal to one dot\n"
     ]
    }
   ],
   "source": [
    "string = raw_input()\n",
    "\n",
    "to_morze_map = {\n",
    "    'a': '.-',\n",
    "    'b': '-...',\n",
    "    'c': '-.-.',\n",
    "    'd': '-..',\n",
    "    'e': '.',\n",
    "    'f': '..-.',\n",
    "    'g': '--.',\n",
    "    'h': '....',\n",
    "    'i': '..',\n",
    "    'j': '.---',\n",
    "    'k': '-.-',\n",
    "    'l': '.-..',\n",
    "    'm': '--',\n",
    "    'n': '-.',\n",
    "    'o': '---',\n",
    "    'p': '.--.',\n",
    "    'q': '--.-',\n",
    "    'r': '.-.',\n",
    "    's': '...',\n",
    "    't': '-',\n",
    "    'u': '..-',\n",
    "    'v': '...-',\n",
    "    'w': '.--',\n",
    "    'x': '-..-',\n",
    "    'y': '-.--',\n",
    "    'z': '--..'\n",
    "}\n",
    "\n",
    "from_morze_map = {value: key for key, value in to_morze_map.items()}\n",
    "\n",
    "def from_morze(string):\n",
    "    words = string.strip().split(\"   \")\n",
    "    letters = []\n",
    "    for word in words:\n",
    "        letters.extend(word.split(\"  \"))\n",
    "    output = \"\"\n",
    "    for letter in letters:\n",
    "        if letter:\n",
    "            output += from_morze_map[letter]\n",
    "        else:\n",
    "            output += \" \"\n",
    "    return output.strip()\n",
    "            \n",
    "print from_morze(string)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---\n",
    "## Числа \n",
    "Вася уже многому научился в программировании, поэтому теперь задачи сами приходят ему в голову. В этот раз ему захотелось словами вывести число, написанное во входном файле.\n",
    "##### Формат ввода:\n",
    "Единственное неотрицательное целое число от $0$ до $2*10^9$.\n",
    "##### Формат вывода:\n",
    "Выведите то же самое число словами. Число десятков и число единиц пишутся через дефис. \"and\" между сотнями и десятками не пишется никогда.\n",
    "### Пример\n",
    "##### Ввод:\n",
    "---\n",
    "    1543\n",
    "---\n",
    "##### Вывод:\n",
    "---\n",
    "    one thousand five hundred forty-three\n",
    "---"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "90012002300\n",
      "ninety billion twelve million two thousand three hundred\n"
     ]
    }
   ],
   "source": [
    "string = raw_input()\n",
    "\n",
    "to_words_map = {\n",
    "    '0': '',\n",
    "    '1': 'one',\n",
    "    '2': 'two',\n",
    "    '3': 'three',\n",
    "    '4': 'four',\n",
    "    '5': 'five',\n",
    "    '6': 'six',\n",
    "    '7': 'seven',\n",
    "    '8': 'eight',\n",
    "    '9': 'nine',\n",
    "    '10': 'ten',\n",
    "    '11': 'eleven',\n",
    "    '12': 'twelve',\n",
    "    '13': 'thirteen',\n",
    "    '14': 'fourteen',\n",
    "    '15': 'fifteen',\n",
    "    '16': 'sixteen',\n",
    "    '17': 'seventeen',\n",
    "    '18': 'eighteen',\n",
    "    '19': 'nineteen',\n",
    "    '0*': '',\n",
    "    '2*': 'twenty',\n",
    "    '3*': 'thirty',\n",
    "    '4*': 'forty',\n",
    "    '5*': 'fifty',\n",
    "    '6*': 'sixty',\n",
    "    '7*': 'seventy',\n",
    "    '8*': 'eighty',\n",
    "    '9*': 'ninety',\n",
    "    0: '',\n",
    "    1: 'thousand',\n",
    "    2: 'million',\n",
    "    3: 'billion'\n",
    "}\n",
    "\n",
    "def spell_hundreds(string):\n",
    "    if len(string) == 3:\n",
    "        if string[0] != '0':\n",
    "            format_string = \"{} hundred {}\"\n",
    "        else:\n",
    "            format_string = \"{}{}\"\n",
    "        hundreds = to_words_map[string[0]]\n",
    "        if string[1] > '1':\n",
    "            tens = to_words_map[string[1] + '*']\n",
    "            if string[2] != '0':\n",
    "                format_string += \"-{}\"\n",
    "            else:\n",
    "                format_string += \"{}\"\n",
    "            ones = to_words_map[string[2]]\n",
    "        else:\n",
    "            format_string += \"{}\"\n",
    "            if string[1] != '0':\n",
    "                tens = to_words_map[string[1] + string[2]]\n",
    "                ones = \"\"\n",
    "            else:\n",
    "                tens = \"\"\n",
    "                ones = to_words_map[string[2]] \n",
    "        return format_string.format(hundreds, tens, ones).strip()\n",
    "    return None\n",
    "\n",
    "def spell(string):\n",
    "    string = \"0\" * ((3 - len(string) % 3) % 3) + string\n",
    "    length = len(string)\n",
    "    i = 0\n",
    "    output = \"\"\n",
    "    while i < length / 3:\n",
    "        part = string[length - 3 * (i + 1):length - 3 * i]\n",
    "        if part != \"000\":\n",
    "            output = \"{} {} {}\".format(spell_hundreds(part), to_words_map[i], output)\n",
    "        i += 1\n",
    "    return output.strip()\n",
    "        \n",
    "print spell(string)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---\n",
    "## Кортеж-2\n",
    "Помните Васины эксперименты с печатью разложения числа на простые множители? Находить числа он уже научился сам, а вот с печатью пока не справляется. А вы справитесь? В этой задаче запрещено использовать встроенное форматирование <code>tuple</code> - его необходимо воспроизвести самостоятельно.\n",
    "##### Формат ввода:\n",
    "Входная строка из не более чем $1000$ чисел, каждое в диапазоне от $-10^9$ до $10^9$.\n",
    "##### Формат вывода:\n",
    "Кортеж из этих чисел в отсортированном порядке - так, как получилось бы в результате <code>print((1,2,3))</code>.\n",
    "### Пример\n",
    "##### Ввод:\n",
    "---\n",
    "    10 5 20\n",
    "---\n",
    "##### Вывод:\n",
    "---\n",
    "    (5, 10, 20)\n",
    "---"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "  1 2 3 1 1 1 1 2  1 1 1  5\n",
      "(1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 3, 5)\n"
     ]
    }
   ],
   "source": [
    "numbers = tuple([str(number) for number in sorted([int(number) for number in raw_input().split()])])\n",
    "print \"(\" + \", \".join(numbers) + \")\""
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---\n",
    "## Словарь-2\n",
    "Кортежи не слишком интересны - элементы просто идут подряд, менять ничего нельзя... То ли дело словари! Составьте словарь и выведите его так, как его вывела бы функция <code>print</code>. В этой задаче запрещено использовать встроенное форматирование <code>dict</code> - его необходимо воспроизвести самостоятельно.\n",
    "##### Формат ввода:\n",
    "Первая строка содержит натуральное число $N ≤ 1000$. Далее идут $N$ строк, в каждой по $2$ целых числа от $-10^9$ до $10^9$, разделенных пробелом - пары ключ-значение. Все ключи уникальны.\n",
    "##### Формат вывода:\n",
    "Словарь из этих пар - так, как получилось бы в результате <code>print(1: 2, 3: 4)</code>. Для определенности, ключи выводите в порядке возрастания.\n",
    "### Пример\n",
    "##### Ввод:\n",
    "---\n",
    "    2\n",
    "    1 2\n",
    "    3 4\n",
    "---\n",
    "##### Вывод:\n",
    "---\n",
    "    {1: 2, 3: 4}\n",
    "---"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "2\n",
      "1 2\n",
      "3 4\n",
      "{1: 2, 3: 4}\n"
     ]
    }
   ],
   "source": [
    "N = int(raw_input())\n",
    "dictionary = {}\n",
    "while N > 0:\n",
    "    pair = tuple(int(i) for i in raw_input().split())\n",
    "    dictionary[pair[0]] = pair[1]\n",
    "    N -= 1\n",
    "\n",
    "pairs = [str(key) + \": \" + str(value) for key, value in dictionary.items()]\n",
    "print \"{\" + \", \".join(pairs) + \"}\""
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---\n",
    "## Война и мир\n",
    "Вася всерьез занялся обработкой текстов. Теперь он хочет по томику Войны и мира узнать, какие слова в нем — самые частотные. Его друг лингвист Петя уже подсказывает, что это будут предлоги и союзы, но Вася сомневается. Развейте его сомнения!\n",
    "##### Формат ввода:\n",
    "Входной файл содержит текст, записанный латинскими буквами, цифрами и знаками препинания. Все непробельные символы, отличные от латинских символов, следует удалить из текста перед подсчетом частот.\n",
    "##### Формат вывода:\n",
    "Для всех словоформ, приведенных к нижнему регистру, выведите число их вхождений в исходный текст, по одному в строке, в алфавитном порядке.\n",
    "### Пример\n",
    "##### Ввод:\n",
    "---\n",
    "    War and Peace is a novel by the Russian author Leo Tolstoy, first published in 1869. The work is epic in scale and is regarded as one of the most important works of world literature. It is considered as Tolstoy's finest literary achievement, along with his other major prose work, Anna Karenina.\n",
    "---\n",
    "##### Вывод:\n",
    "---\n",
    "    a 1\n",
    "    achievement 1\n",
    "    along 1\n",
    "    and 2\n",
    "    anna 1\n",
    "    as 2\n",
    "    author 1\n",
    "    by 1\n",
    "    considered 1\n",
    "    epic 1\n",
    "    finest 1\n",
    "    first 1\n",
    "    his 1\n",
    "    important 1\n",
    "    in 2\n",
    "    is 4\n",
    "    it 1\n",
    "    karenina 1\n",
    "    leo 1\n",
    "    literary 1\n",
    "    literature 1\n",
    "    major 1\n",
    "    most 1\n",
    "    novel 1\n",
    "    of 2\n",
    "    one 1\n",
    "    other 1\n",
    "    peace 1\n",
    "    prose 1\n",
    "    published 1\n",
    "    regarded 1\n",
    "    russian 1\n",
    "    scale 1\n",
    "    the 3\n",
    "    tolstoy 1\n",
    "    tolstoys 1\n",
    "    war 1\n",
    "    with 1\n",
    "    work 2\n",
    "    works 1\n",
    "    world 1\n",
    "---"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "War and Peace is a novel by the Russian author Leo Tolstoy, first published in 1869. The work is epic in scale and is regarded as one of the most important works of world literature. It is considered as Tolstoy's finest literary achievement, along with his other major prose work, Anna Karenina.\n",
      "a 1\n",
      "achievement 1\n",
      "along 1\n",
      "and 2\n",
      "anna 1\n",
      "as 2\n",
      "author 1\n",
      "by 1\n",
      "considered 1\n",
      "epic 1\n",
      "finest 1\n",
      "first 1\n",
      "his 1\n",
      "important 1\n",
      "in 2\n",
      "is 4\n",
      "it 1\n",
      "karenina 1\n",
      "leo 1\n",
      "literary 1\n",
      "literature 1\n",
      "major 1\n",
      "most 1\n",
      "novel 1\n",
      "of 2\n",
      "one 1\n",
      "other 1\n",
      "peace 1\n",
      "prose 1\n",
      "published 1\n",
      "regarded 1\n",
      "russian 1\n",
      "scale 1\n",
      "the 3\n",
      "tolstoy 1\n",
      "tolstoys 1\n",
      "war 1\n",
      "with 1\n",
      "work 2\n",
      "works 1\n",
      "world 1\n"
     ]
    }
   ],
   "source": [
    "import re\n",
    "\n",
    "string = raw_input()\n",
    "\n",
    "words = {}\n",
    "string = re.sub('[^a-zA-Z\\s]', '', string)\n",
    "\n",
    "for word in re.findall(\"[a-zA-Z']+\", string):\n",
    "    word = word.lower()\n",
    "    if word in words:\n",
    "        words[word] += 1\n",
    "    else:\n",
    "        words[word] = 1\n",
    "        \n",
    "for key in sorted(words):\n",
    "    print key, words[key]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---\n",
    "## Война и мир-2\n",
    "После решения предыдущей задачи Вася признал правоту Пети. Однако, теперь он перешел от слов к символам и хочет узнать, с какими частотами отдельные буквы встречаются в текстах.\n",
    "##### Формат ввода:\n",
    "Входной файл содержит текст, записанный латинскими буквами, цифрами и знаками препинания. Все символы, отличные от латинских символов, следует удалить из текста перед подсчетом частот.\n",
    "##### Формат вывода:\n",
    "Для всех содержащихся в тексте латинских символов, приведенных к нижнему регистру, выведите число их вхождений в исходный текст, по одному в строке, в алфавитном порядке.\n",
    "### Пример\n",
    "##### Ввод:\n",
    "---\n",
    "    War and Peace is a novel by the Russian author Leo Tolstoy, first published in 1869. The work is epic in scale and is regarded as one of the most important works of world literature. It is considered as Tolstoy's finest literary achievement, along with his other major prose work, Anna Karenina.\n",
    "---\n",
    "##### Вывод:\n",
    "---\n",
    "    a 21\n",
    "    b 2\n",
    "    c 5\n",
    "    d 8\n",
    "    e 25\n",
    "    f 4\n",
    "    g 2\n",
    "    h 9\n",
    "    i 20\n",
    "    j 1\n",
    "    k 4\n",
    "    l 10\n",
    "    m 4\n",
    "    n 16\n",
    "    o 21\n",
    "    p 5\n",
    "    r 20\n",
    "    s 20\n",
    "    t 20\n",
    "    u 4\n",
    "    v 2\n",
    "    w 6\n",
    "    y 4\n",
    "---"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "War and Peace is a novel by the Russian author Leo Tolstoy, first published in 1869. The work is epic in scale and is regarded as one of the most important works of world literature. It is considered as Tolstoy's finest literary achievement, along with his other major prose work, Anna Karenina.\n",
      "a 21\n",
      "b 2\n",
      "c 5\n",
      "d 8\n",
      "e 25\n",
      "f 4\n",
      "g 2\n",
      "h 9\n",
      "i 20\n",
      "j 1\n",
      "k 4\n",
      "l 10\n",
      "m 4\n",
      "n 16\n",
      "o 21\n",
      "p 5\n",
      "r 20\n",
      "s 20\n",
      "t 20\n",
      "u 4\n",
      "v 2\n",
      "w 6\n",
      "y 4\n"
     ]
    }
   ],
   "source": [
    "import re\n",
    "\n",
    "string = raw_input()\n",
    "letters = {}\n",
    "\n",
    "for letter in re.findall(\"[a-zA-Z]\", string):\n",
    "    letter = letter.lower()\n",
    "    if letter in letters:\n",
    "        letters[letter] += 1\n",
    "    else:\n",
    "        letters[letter] = 1\n",
    "        \n",
    "for key in sorted(letters):\n",
    "    print key, letters[key]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---\n",
    "## Пароли \n",
    "Вася хочет поменять свой пароль от электронной почты, потому что боится, что его ящик мог быть взломан. По правилам новый пароль должен удовлетворять таким ограничениям:\n",
    "* состоять из символов таблицы ASCII с кодами от $33$ до $127$;\n",
    "* быть не меньше $8$ символов и не длиннее $14$;\n",
    "* из $4$ классов символов - большие буквы, маленькие буквы, цифры, прочие символы - в пароле должны присутствовать три любых.\n",
    "\n",
    "Помогите Васе написать программу, которая проверит, что его новый пароль годится.\n",
    "##### Формат ввода:\n",
    "На входе дана одна строка - новый Васин пароль.\n",
    "##### Формат вывода:\n",
    "Выведите YES, если Васин пароль удовлетворяет требованиям, и NO в противном случае.\n",
    "### Пример\n",
    "##### Ввод:\n",
    "---\n",
    "    Vasya123\n",
    "---\n",
    "##### Вывод:\n",
    "---\n",
    "    YES\n",
    "---"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Vasya123\n",
      "YES\n"
     ]
    }
   ],
   "source": [
    "string = raw_input()\n",
    "\n",
    "def check_password(string):\n",
    "    properties = set(['a', 'A', '1', '!'])\n",
    "    if not 8 <= len(string) <= 14:\n",
    "        return False\n",
    "    for character in string:\n",
    "        if not 33 <= ord(character) <= 127:\n",
    "            return False\n",
    "        if 'a' <= character <= 'z':\n",
    "            properties.discard('a')\n",
    "        elif 'A' <= character <= 'Z':\n",
    "            properties.discard('A')\n",
    "        elif '0' <= character <= '9':\n",
    "            properties.discard('1')\n",
    "        else:\n",
    "            properties.discard('!')\n",
    "    if len(properties) > 1:\n",
    "        return False\n",
    "    return True\n",
    "\n",
    "if check_password(string):\n",
    "    print \"YES\"\n",
    "else:\n",
    "    print \"NO\""
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---\n",
    "## Война и мир-3\n",
    "В процессе работы над предыдущими задачами Вася иногда читал большие фрагменты четырехтомника Льва Николаевича Толстого. Ни для кого не секрет, что автор в этом произведении часто возвращается к нескольким проблемам. Вася хочет автоматически научиться искать такие фрагменты. Для этого он планирует сравнивать наборы слов в предложениях. Начать он решил с простейшей задачи — для двух предложений найти все их общие слова.\n",
    "##### Формат ввода:\n",
    "Первая строка входного файла содержит предложение, записанное с помощью латинских символов, цифр и знаков препинания. Вторая строка содержит аналогичное предложение. Все непробельные символы, отличные от латинских символов, следует сразу же удалить из текстов.\n",
    "##### Формат вывода:\n",
    "Выведите в алфавитном порядке, по одному в строке, в нижнем регистре, все слова, которые встречаются в обоих предложениях.\n",
    "### Пример\n",
    "##### Ввод:\n",
    "---\n",
    "    War and Peace is a novel by the Russian author Leo Tolstoy, first published in 1869. The work is epic in scale and is regarded as one of the most important works of world literature. It is considered as Tolstoy's finest literary achievement, along with his other major prose work, Anna Karenina.\n",
    "    \n",
    "    War and Peace has a large cast of characters, the majority of whom are introduced in the first book. Some are actual historical figures, such as Napoleon and Alexander I. While the scope of the novel is vast, it is centered around five aristocratic families. The plot and the interactions of the characters take place in the era surrounding the 1812 French invasion of Russia during the Napoleonic wars.\n",
    "---\n",
    "##### Вывод:\n",
    "---\n",
    "    a\n",
    "    and\n",
    "    as\n",
    "    first\n",
    "    in\n",
    "    is\n",
    "    it\n",
    "    novel\n",
    "    of\n",
    "    peace\n",
    "    the\n",
    "    war\n",
    "---"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "War and Peace is a novel by the Russian author Leo Tolstoy, first published in 1869. The work is epic in scale and is regarded as one of the most important works of world literature. It is considered as Tolstoy's finest literary achievement, along with his other major prose work, Anna Karenina.\n",
      "War and Peace has a large cast of characters, the majority of whom are introduced in the first book. Some are actual historical figures, such as Napoleon and Alexander I. While the scope of the novel is vast, it is centered around five aristocratic families. The plot and the interactions of the characters take place in the era surrounding the 1812 French invasion of Russia during the Napoleonic wars.\n",
      "a\n",
      "and\n",
      "as\n",
      "first\n",
      "in\n",
      "is\n",
      "it\n",
      "novel\n",
      "of\n",
      "peace\n",
      "the\n",
      "war\n"
     ]
    }
   ],
   "source": [
    "import re\n",
    "\n",
    "string1 = re.sub('[^a-zA-Z\\s]', '', raw_input())\n",
    "string2 = re.sub('[^a-zA-Z\\s]', '', raw_input())\n",
    "\n",
    "words1 = set([word.lower() for word in re.findall(\"[a-zA-Z']+\", string1)])\n",
    "words2 = set([word.lower() for word in re.findall(\"[a-zA-Z']+\", string2)])\n",
    "\n",
    "for word in sorted(words1.intersection(words2)):\n",
    "    print word"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---\n",
    "## Война и мир-4\n",
    "Вася привык читать тексты с экрана, но иногда форматирование текста ему очень не нравится. В частности, ему редко нравится, как текст разделен на строки. Поэтому Вася решил написать перенос самостоятельно. Он считает, что идеальная ширина текста равняется $80$ символам, поэтому если очередное слово не укладывается в эти пределы, то он его переносит на следующую строку. Помогите Васе написать такую программу.\n",
    "##### Формат ввода:\n",
    "Ровно одна строка с текстом, который надо отформатировать. Текст состоит из латинских символов, цифр и знаков препинания. Удалять символы, отличные от латинских символов, не требуется. Разбиение на слова можно получить с помощью метода <code>split</code>: <code>s.split()</code>\n",
    "##### Формат вывода:\n",
    "Выведите текст, разбитый на строки по приведенному правилу.\n",
    "### Пример\n",
    "##### Ввод:\n",
    "---\n",
    "    War and Peace is a novel by the Russian author Leo Tolstoy, first published in 1869. The work is epic in scale and is regarded as one of the most important works of world literature. It is considered as Tolstoy's finest literary achievement, along with his other major prose work, Anna Karenina.\n",
    "---\n",
    "##### Вывод:\n",
    "---\n",
    "    War and Peace is a novel by the Russian author Leo Tolstoy, first published in\n",
    "    1869. The work is epic in scale and is regarded as one of the most important\n",
    "    works of world literature. It is considered as Tolstoy's finest literary\n",
    "    achievement, along with his other major prose work, Anna Karenina.\n",
    "---"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "War and Peace is a novel by the Russian author Leo Tolstoy, first published in 1869. The work is epic in scale and is regarded as one of the most important works of world literature. It is considered as Tolstoy's finest literary achievement, along with his other major prose work, Anna Karenina.\n",
      "War and Peace is a novel by the Russian author Leo Tolstoy, first published in \n",
      "1869. The work is epic in scale and is regarded as one of the most important \n",
      "works of world literature. It is considered as Tolstoy's finest literary \n",
      "achievement, along with his other major prose work, Anna Karenina.\n"
     ]
    }
   ],
   "source": [
    "words = raw_input().split()\n",
    "\n",
    "width = 0\n",
    "\n",
    "for word in words:\n",
    "    if width + len(word) > 80:\n",
    "        width = len(word) + 1\n",
    "        print \"\\n\" + word,\n",
    "    else:\n",
    "        width += len(word) + 1\n",
    "        print word,"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---\n",
    "## Война и мир-5\n",
    "Васе так нравится текст Война и мира, что он хочет сохранить его от посторонних глаз. Для этого он хочет применить новый метод шифрования, о котором недавно услышал — заменить каждый символ на символ, сдвинутый на некоторую константу по алфавиту. Помогите ему сохранить труды Льва Николаевича!\n",
    "##### Формат ввода:\n",
    "Первая строка содержит натуральное число — параметр сдвига. Вторая строка содержит текст, состоящий из строчных латинских бука, цифр и знаков препинания. Все латинские символы требуется заменить по шифру Цезаря, а цифры и знаки препинания оставить без изменения.\n",
    "##### Формат вывода:\n",
    "Выведите зашифрованный текст.\n",
    "### Пример\n",
    "##### Ввод:\n",
    "---\n",
    "    3\n",
    "    war and peace is a novel by the russian author leo tolstoy, first published in 1869. the work is epic in scale and is regarded as one of the most important works of world literature. it is considered as tolstoy's finest literary achievement, along with his other major prose work, anna karenina.\n",
    "---\n",
    "##### Вывод:\n",
    "---\n",
    "    zdu dqg shdfh lv d qryho eb wkh uxvvldq dxwkru ohr wrovwrb, iluvw sxeolvkhg lq 1869. wkh zrun lv hslf lq vfdoh dqg lv uhjdughg dv rqh ri wkh prvw lpsruwdqw zrunv ri zruog olwhudwxuh. lw lv frqvlghuhg dv wrovwrb'v ilqhvw olwhudub dfklhyhphqw, dorqj zlwk klv rwkhu pdmru survh zrun, dqqd nduhqlqd.\n",
    "---"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "3\n",
      "war and peace is a novel by the russian author leo tolstoy, first published in 1869. the work is epic in scale and is regarded as one of the most important works of world literature. it is considered as tolstoy's finest literary achievement, along with his other major prose work, anna karenina.\n",
      "zdu dqg shdfh lv d qryho eb wkh uxvvldq dxwkru ohr wrovwrb, iluvw sxeolvkhg lq 1869. wkh zrun lv hslf lq vfdoh dqg lv uhjdughg dv rqh ri wkh prvw lpsruwdqw zrunv ri zruog olwhudwxuh. lw lv frqvlghuhg dv wrovwrb'v ilqhvw olwhudub dfklhyhphqw, dorqj zlwk klv rwkhu pdmru survh zrun, dqqd nduhqlqd.\n"
     ]
    }
   ],
   "source": [
    "N = int(raw_input())\n",
    "string = raw_input()\n",
    "\n",
    "cypher = \"\"\n",
    "\n",
    "for character in string:\n",
    "    if 'a' <= character <= 'z':\n",
    "        character = chr(ord('a') + (ord(character) - ord('a') + N) % (ord('z') - ord('a') + 1))\n",
    "    cypher += character\n",
    "    \n",
    "print cypher"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---\n",
    "## Отладка \n",
    "Вася написал решение задачи про перебор всех правильных скобочных последовательностей в лексикографическом порядке и теперь хочет его отдебажить. Вот код его решения:\n",
    "```python\n",
    "def brackets(begin, balance, length):\n",
    "  if len(begin) == length:\n",
    "    print(begin)\n",
    "    return\n",
    "  if length - len(begin) - 1 >= balance + 1:\n",
    "    brackets(begin + '(', balance + 1, length)\n",
    "  if balance > 0:\n",
    "    brackets(begin +')', balance - 1, length)\n",
    "```\n",
    "Вася хочет при входе в функцию писать, что вызвана такая-то функция с такими-то параметрами, а при выходе - что завершается работа такой-то функции с такими-то параметрами.\n",
    "И вот Вася уже собрался писать дебаговый вывод в консоль, как вспомнил, что вы умеете писать декораторы. Помогите Васе и напишите декоратор, чтобы Вася смог его применить и в других задачах для отладки своих решений.\n",
    "##### Формат ввода:\n",
    "Вам дается число $n, 0 ≤ n ≤ 9$ — количество пар скобок, для которого Вася запускает свое решение.\n",
    "##### Формат вывода:\n",
    "Выведите результат работы программы с декоратором. Формат вывода приведен в семпле.\n",
    "### Пример\n",
    "##### Ввод:\n",
    "---\n",
    "    2\n",
    "---\n",
    "##### Вывод:\n",
    "---\n",
    "    Start brackets with args ('', 0, 2) and dict {}\n",
    "    Start brackets with args ('(', 1, 2) and dict {}\n",
    "    Start brackets with args ('()', 0, 2) and dict {}\n",
    "    ()\n",
    "    Finish brackets with args ('()', 0, 2) and dict {}\n",
    "    Finish brackets with args ('(', 1, 2) and dict {}\n",
    "    Finish brackets with args ('', 0, 2) and dict {}\n",
    "---"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "6\n",
      "Start brackets with args ('', 0, 6) and dict {}\n",
      "Start brackets with args ('(', 1, 6) and dict {}\n",
      "Start brackets with args ('((', 2, 6) and dict {}\n",
      "Start brackets with args ('(((', 3, 6) and dict {}\n",
      "Start brackets with args ('((()', 2, 6) and dict {}\n",
      "Start brackets with args ('((())', 1, 6) and dict {}\n",
      "Start brackets with args ('((()))', 0, 6) and dict {}\n",
      "((()))\n",
      "Finish brackets with args ('((()))', 0, 6) and dict {}\n",
      "Finish brackets with args ('((())', 1, 6) and dict {}\n",
      "Finish brackets with args ('((()', 2, 6) and dict {}\n",
      "Finish brackets with args ('(((', 3, 6) and dict {}\n",
      "Start brackets with args ('(()', 1, 6) and dict {}\n",
      "Start brackets with args ('(()(', 2, 6) and dict {}\n",
      "Start brackets with args ('(()()', 1, 6) and dict {}\n",
      "Start brackets with args ('(()())', 0, 6) and dict {}\n",
      "(()())\n",
      "Finish brackets with args ('(()())', 0, 6) and dict {}\n",
      "Finish brackets with args ('(()()', 1, 6) and dict {}\n",
      "Finish brackets with args ('(()(', 2, 6) and dict {}\n",
      "Start brackets with args ('(())', 0, 6) and dict {}\n",
      "Start brackets with args ('(())(', 1, 6) and dict {}\n",
      "Start brackets with args ('(())()', 0, 6) and dict {}\n",
      "(())()\n",
      "Finish brackets with args ('(())()', 0, 6) and dict {}\n",
      "Finish brackets with args ('(())(', 1, 6) and dict {}\n",
      "Finish brackets with args ('(())', 0, 6) and dict {}\n",
      "Finish brackets with args ('(()', 1, 6) and dict {}\n",
      "Finish brackets with args ('((', 2, 6) and dict {}\n",
      "Start brackets with args ('()', 0, 6) and dict {}\n",
      "Start brackets with args ('()(', 1, 6) and dict {}\n",
      "Start brackets with args ('()((', 2, 6) and dict {}\n",
      "Start brackets with args ('()(()', 1, 6) and dict {}\n",
      "Start brackets with args ('()(())', 0, 6) and dict {}\n",
      "()(())\n",
      "Finish brackets with args ('()(())', 0, 6) and dict {}\n",
      "Finish brackets with args ('()(()', 1, 6) and dict {}\n",
      "Finish brackets with args ('()((', 2, 6) and dict {}\n",
      "Start brackets with args ('()()', 0, 6) and dict {}\n",
      "Start brackets with args ('()()(', 1, 6) and dict {}\n",
      "Start brackets with args ('()()()', 0, 6) and dict {}\n",
      "()()()\n",
      "Finish brackets with args ('()()()', 0, 6) and dict {}\n",
      "Finish brackets with args ('()()(', 1, 6) and dict {}\n",
      "Finish brackets with args ('()()', 0, 6) and dict {}\n",
      "Finish brackets with args ('()(', 1, 6) and dict {}\n",
      "Finish brackets with args ('()', 0, 6) and dict {}\n",
      "Finish brackets with args ('(', 1, 6) and dict {}\n",
      "Finish brackets with args ('', 0, 6) and dict {}\n"
     ]
    }
   ],
   "source": [
    "import functools\n",
    "\n",
    "def debug(_origin):\n",
    "    @functools.wraps(_origin)\n",
    "    def _wrapper(*args, **kwargs):\n",
    "        print \"Start {} with args {} and dict {}\".format(_origin.__name__, args, kwargs)\n",
    "        ret = _origin(*args, **kwargs)\n",
    "        print \"Finish {} with args {} and dict {}\".format(_origin.__name__, args, kwargs)\n",
    "        return ret\n",
    "    return _wrapper\n",
    "\n",
    "@debug\n",
    "def brackets(begin, balance, length):\n",
    "    if len(begin) == length:\n",
    "        print(begin)\n",
    "        return\n",
    "    if length - len(begin) - 1 >= balance + 1:\n",
    "        brackets(begin + '(', balance + 1, length)\n",
    "    if balance > 0:\n",
    "        brackets(begin +')', balance - 1, length)\n",
    "        \n",
    "n = int(raw_input().strip())\n",
    "\n",
    "brackets('', 0, n)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---\n",
    "## Профайлинг  \n",
    "Вася решает задачу про перебор всех перестановок длины $n$ в порядке возрастания. Делает он это очень просто — перебирает все последовательности подряд до тех пор, пока не получит последовательность, являющуюся перестановкой. К сожалению, его решение не укладывается в ограничения по времени. Вася хочет воспользоваться профайлером, чтобы узнать, выполнение какой из функций занимает так много времени.\n",
    "Вот код Васиного решения:\n",
    "```python\n",
    "def next_sequence(sequence):\n",
    "    sequence = sequence[:]\n",
    "    for i in range(1, len(sequence) + 1):\n",
    "        if sequence[-i] < len(sequence) - 1:\n",
    "            sequence[-i] += 1\n",
    "            i -= 1\n",
    "            while i > 0:\n",
    "                sequence[-i] = 0\n",
    "                i -= 1\n",
    "            return sequence\n",
    "    return None\n",
    "\n",
    "def is_permutation(sequence):\n",
    "    numbers = {}\n",
    "    for i in sequence:\n",
    "        numbers[i] = 1\n",
    "    for i in range(len(sequence)):\n",
    "        if i not in numbers or numbers[i] != 1:\n",
    "            return False\n",
    "    return True\n",
    "\n",
    "def next_permutation(permutation):\n",
    "    permutation = permutation[:]\n",
    "    while permutation is not None:\n",
    "        permutation = next_sequence(permutation)\n",
    "        if permutation is not None and is_permutation(permutation):\n",
    "            return permutation\n",
    "    return None\n",
    "\n",
    "n = int(input())\n",
    "a = list(range(n))\n",
    "while a is not None:\n",
    "    a = next_permutation(a)\n",
    "```\n",
    "Помогите Васе и напишите декоратор, который будет для каждой функции писать суммарное время ее работы.\n",
    "##### Формат ввода:\n",
    "Содержит ровно одно число $n, 0 ≤ n ≤ 6$.\n",
    "##### Формат вывода:\n",
    "Выведите результат работы профайлера. Функции перечислите именно в этом порядке, время выводите в секундах с точностью до одного знака после запятой.\n",
    "### Пример\n",
    "##### Ввод:\n",
    "---\n",
    "    8\n",
    "---\n",
    "##### Вывод:\n",
    "---\n",
    "    next_sequence 27.2\n",
    "    is_permutation 33.6\n",
    "    next_permutation 99.5\n",
    "---"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 210,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "8\n",
      "next_sequence 27.2\n",
      "is_permutation 33.6\n",
      "next_permutation 99.5\n"
     ]
    }
   ],
   "source": [
    "import time, functools\n",
    "d = {}\n",
    "\n",
    "def profiler(_origin):\n",
    "    @functools.wraps(_origin)\n",
    "    def _wrapper(*args, **kwargs):\n",
    "        start = time.clock()\n",
    "        ret = _origin(*args, **kwargs)\n",
    "        finish = time.clock()\n",
    "        if _origin.__name__ in d:\n",
    "            d[_origin.__name__] += float(finish - start)\n",
    "        else:\n",
    "            d[_origin.__name__] = 0.\n",
    "        return ret\n",
    "    return _wrapper\n",
    "\n",
    "@profiler\n",
    "def next_sequence(sequence):\n",
    "    sequence = sequence[:]\n",
    "    for i in range(1, len(sequence) + 1):\n",
    "        if sequence[-i] < len(sequence) - 1:\n",
    "            sequence[-i] += 1\n",
    "            i -= 1\n",
    "            while i > 0:\n",
    "                sequence[-i] = 0\n",
    "                i -= 1\n",
    "            return sequence\n",
    "    return None\n",
    "\n",
    "@profiler\n",
    "def is_permutation(sequence):\n",
    "    numbers = {}\n",
    "    for i in sequence:\n",
    "        numbers[i] = 1\n",
    "    for i in range(len(sequence)):\n",
    "        if i not in numbers or numbers[i] != 1:\n",
    "            return False\n",
    "    return True\n",
    "\n",
    "@profiler\n",
    "def next_permutation(permutation):\n",
    "    permutation = permutation[:]\n",
    "    while permutation is not None:\n",
    "        permutation = next_sequence(permutation)\n",
    "        if permutation is not None and is_permutation(permutation):\n",
    "            return permutation\n",
    "    return None\n",
    "\n",
    "n = int(input())\n",
    "a = list(range(n))\n",
    "while a is not None:\n",
    "    a = next_permutation(a)\n",
    "\n",
    "print \"{} {:.1f}\".format('next_sequence', d['next_sequence'])\n",
    "print \"{} {:.1f}\".format('is_permutation', d['is_permutation'])\n",
    "print \"{} {:.1f}\".format('next_permutation', d['next_permutation'])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 2",
   "language": "python",
   "name": "python2"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 2
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython2",
   "version": "2.7.11"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}