prob_147_done.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 37,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "from time import time"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 40,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0 42 15093 0.045041561126708984\n",
      "1 42 66652 0.3154754638671875\n",
      "2 42 182604 0.9883682727813721\n",
      "3 42 396782 2.2573394775390625\n",
      "4 42 748301 4.309210538864136\n",
      "5 42 1280958 7.336757183074951\n",
      "6 42 2042656 11.52486538887024\n",
      "7 42 3084852 17.13174843788147\n",
      "8 42 4462029 24.242844581604004\n",
      "9 42 6231192 33.10395812988281\n",
      "10 42 8451388 43.89130616188049\n",
      "11 42 11183250 56.85173797607422\n",
      "12 42 14488565 72.10455799102783\n",
      "13 42 18429866 89.92963767051697\n",
      "14 42 23070048 110.50300145149231\n",
      "15 42 28472008 133.96550607681274\n",
      "16 42 34698309 160.57706308364868\n",
      "17 42 41810868 190.61582255363464\n",
      "18 42 49870668 224.12399339675903\n",
      "19 42 58937494 261.29741764068604\n",
      "20 42 69069693 302.7079219818115\n",
      "21 42 80323958 348.32135009765625\n",
      "22 42 92755136 398.11518955230713\n",
      "23 42 106416060 452.56716084480286\n",
      "24 42 121357405 511.70944118499756\n",
      "25 42 137627568 575.7581295967102\n",
      "26 42 155272572 645.1484799385071\n",
      "27 42 174335994 720.4243233203888\n",
      "28 42 194858917 801.5947978496552\n",
      "29 42 216879906 888.9247958660126\n",
      "30 42 240435008 981.7169332504272\n",
      "31 42 265557776 1081.440554857254\n",
      "32 42 292279317 1187.5209467411041\n",
      "33 42 320628364 1298.8817536830902\n",
      "34 42 350631372 1417.064109802246\n",
      "35 42 382312638 1542.5900795459747\n",
      "36 42 415694445 1675.1942546367645\n",
      "37 42 450797230 1815.5541167259216\n",
      "38 42 487639776 1963.5429573059082\n",
      "39 42 526239428 2119.476708650589\n",
      "40 42 566612333 2283.1390657424927\n",
      "41 42 608773704 2455.4827601909637\n",
      "42 42 652738108 2636.158580303192\n",
      "43 42 698519778 2825.662227869034\n",
      "44 42 746132904 3024.8379702568054\n",
      "45 42 795591676 3232.723323583603\n",
      "46 42 846910284 3449.3997197151184\n",
      "846910284\n"
     ]
    }
   ],
   "source": [
    "count = 0\n",
    "t0 = time()\n",
    "for d1 in range(47):\n",
    "    for d2 in range(43):\n",
    "        dim=(d1+1,d2+1)\n",
    "        for i in range(1,1+dim[0]):\n",
    "            for j in range(1,1+dim[1]):\n",
    "                n = (dim[0]-i+1)*(dim[1]-j+1)\n",
    "                count += n\n",
    "#             print(\"hori\",i,j, count)\n",
    "\n",
    "        for up in range(1, 2*i):\n",
    "            for down in range(1, 2*j):\n",
    "                dx = up + down\n",
    "                counta = 0\n",
    "                for i2 in range(2*i):\n",
    "                    for j2 in range(2*j):\n",
    "                        if i2 %2 == j2%2 and i2+dx <= 2*i and j2+up<=2*j and j2-down>=0:\n",
    "                            counta +=1\n",
    "                count += counta\n",
    "#             print(\"diag\",up,down,count)\n",
    "    print(d1,d2, count,time()-t0)\n",
    "\n",
    "print(count)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# 846910284 correct answer"
   ]
  }
 ],
 "metadata": {
  "anaconda-cloud": {},
  "kernelspec": {
   "display_name": "Python [conda root]",
   "language": "python",
   "name": "conda-root-py"
  },
  "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.5.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}