min cost to go to a number using single steps or jumping to double the position.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "given a destination(a number), reach from 0 to the destination using following steps\n",
    "move one step forward or backwards from current positions at cost of step_cost\n",
    "go to 2*current number at a cost of doubling_cost\n",
    "have to find the minimum cost to reach a given destination.\n",
    "\n",
    "ex: if destination=7, step_cost=4, doubling_cost=2,\n",
    "    best way to go there is (0,1,2,4,8,7) which is 4+2+2+2+4\n",
    "    if we had gone step by step that would have been terrible to incur a cost of 28"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "4 13 2\n",
      "[[13, 0]]\n",
      "[[13, 0]]\n",
      "3\n",
      "[[6, 6], [7, 6]]\n",
      "2\n",
      "[[7, 6], [3, 8]]\n",
      "3\n",
      "[[3, 8], [3, 12], [4, 12]]\n",
      "3\n",
      "[[3, 12], [4, 12], [1, 14], [2, 14]]\n",
      "3\n",
      "[[4, 12], [1, 14], [2, 14], [1, 18], [2, 18]]\n",
      "2\n",
      "[[1, 14], [2, 14], [1, 18], [2, 18], [2, 14]]\n",
      "3\n",
      "[[2, 14], [1, 18], [2, 18], [2, 14], [0, 20], [1, 20], [0, 18]]\n",
      "2\n",
      "[[1, 18], [2, 18], [2, 14], [0, 20], [1, 20], [0, 18], [1, 16]]\n",
      "3\n",
      "[[2, 18], [2, 14], [0, 20], [1, 20], [0, 18], [1, 16], [0, 24], [1, 24], [0, 22]]\n",
      "2\n",
      "[[2, 14], [0, 20], [1, 20], [0, 18], [1, 16], [0, 24], [1, 24], [0, 22], [1, 20]]\n",
      "2\n",
      "[[0, 20], [1, 20], [0, 18], [1, 16], [0, 24], [1, 24], [0, 22], [1, 20], [1, 16]]\n",
      "1\n",
      "[[1, 20], [0, 18], [1, 16], [0, 24], [1, 24], [0, 22], [1, 20], [1, 16]]\n",
      "3\n",
      "[[0, 18], [1, 16], [0, 24], [1, 24], [0, 22], [1, 20], [1, 16], [0, 24]]\n",
      "1\n",
      "[[1, 16], [0, 24], [1, 24], [0, 22], [1, 20], [1, 16], [0, 24]]\n",
      "3\n",
      "[[0, 24], [1, 24], [0, 22], [1, 20], [1, 16], [0, 24], [0, 20]]\n",
      "1\n",
      "[[1, 24], [0, 22], [1, 20], [1, 16], [0, 24], [0, 20]]\n",
      "3\n",
      "[[0, 22], [1, 20], [1, 16], [0, 24], [0, 20], [0, 28]]\n",
      "1\n",
      "[[1, 20], [1, 16], [0, 24], [0, 20], [0, 28]]\n",
      "3\n",
      "[[1, 16], [0, 24], [0, 20], [0, 28], [0, 24]]\n",
      "3\n",
      "[[0, 24], [0, 20], [0, 28], [0, 24], [0, 20]]\n",
      "1\n",
      "[[0, 20], [0, 28], [0, 24], [0, 20]]\n",
      "1\n",
      "[[0, 28], [0, 24], [0, 20]]\n",
      "1\n",
      "[[0, 24], [0, 20]]\n",
      "1\n",
      "[[0, 20]]\n",
      "1\n",
      "18\n"
     ]
    }
   ],
   "source": [
    "step_cost,destination,doubling_cost = map(int,input().split())\n",
    "\n",
    "cases = [[destination,0]]\n",
    "print(cases)\n",
    "\n",
    "min_c = 0 #min_c is minimum cost, destination is my final dest\n",
    "while cases:\n",
    "    print(cases)\n",
    "    case = cases.pop(0)\n",
    "#     print(cases)\n",
    "    n,c = case[:]\n",
    "\n",
    "    if n==0: # we have reached the destination with cost c\n",
    "        print(1)\n",
    "        if c<min_c or min_c ==0:\n",
    "            min_c = c \n",
    "        continue\n",
    "    if n%2==0: #we are halving the distance like going from 8 to 4, doubling_cost is the cost to do it\n",
    "        print(2)\n",
    "        if c+doubling_cost<=min_c or min_c==0:\n",
    "            new = [n//2,c+doubling_cost] #if that's the case add it\n",
    "            cases.append(new)\n",
    "            #cases.insert(0,new)\n",
    "    else:\n",
    "        print(3)\n",
    "        if c+doubling_cost+step_cost<=min_c or min_c==0: #moving back or forward once and halving\n",
    "            new = [(n-1)//2,c+step_cost+doubling_cost]\n",
    "            cases.append(new)\n",
    "            new = [(n+1)//2,c+step_cost+doubling_cost]\n",
    "            cases.append(new)\n",
    "    if (n//2)*step_cost<doubling_cost: # if actually going down n//2 times step by step is better than halving it, choose that\n",
    "        new = [n-1,c+step_cost]\n",
    "        cases.append(new)\n",
    "\n",
    "print(min_c)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "8"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "pow(2,3)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "function func is wrong, as it only takes into consideration from obtaining from 2 powers, which need not be true at all."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "4 7 2\n",
      "14\n"
     ]
    }
   ],
   "source": [
    "step_cost,destination,doubling_cost = map(int,input().split())\n",
    "sc,destination,dc = step_cost,destination,doubling_cost\n",
    "def func(sc,destination,dc):\n",
    "    max2pow = pow(2,len(bin(destination))-2)\n",
    "#     print(max2pow)\n",
    "    dp = [0]*(max2pow+1)\n",
    "    dp[1] = sc\n",
    "    i = 2\n",
    "    while i<=(max2pow):\n",
    "#         print(dp)\n",
    "        dp[i] = dp[i//2]+dc\n",
    "        i*=2\n",
    "#         print(i)\n",
    "#     print(dp) \n",
    "#correct till here\n",
    "    for i in range(1,max2pow+1):\n",
    "        if dp[i]:\n",
    "            dp[i] = min(dp[i],dp[i//2]+sc*(i-i//2))\n",
    "        if not(dp[i]):\n",
    "            bin_i_len = len(bin(i))-2\n",
    "            temp_2pow = pow(2,bin_i_len)\n",
    "#             print(temp_2pow)\n",
    "            dp[i] = min(dp[temp_2pow]+sc*(temp_2pow-i),dp[temp_2pow//2]+sc*(i-temp_2pow//2))\n",
    "#             print(dp)\n",
    "        \n",
    "#     print(dp)\n",
    "    return dp[destination]\n",
    "print(func(sc,destination,dc))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "def func1(step_cost,destination,doubling_cost):\n",
    "    cases = [[destination,0]]\n",
    "#     print(cases)\n",
    "\n",
    "    min_c = 0 #min_c is minimum cost, destination is my final dest\n",
    "    while cases:\n",
    "#         print(cases)\n",
    "        case = cases.pop(0)\n",
    "    #     print(cases)\n",
    "        n,c = case[:]\n",
    "\n",
    "        if n==0: # we have reached the destination with cost c\n",
    "#             print(1)\n",
    "            if c<min_c or min_c ==0:\n",
    "                min_c = c \n",
    "            continue\n",
    "        if n%2==0: #we are halving the distance like going from 8 to 4, doubling_cost is the cost to do it\n",
    "#             print(2)\n",
    "            if c+doubling_cost<=min_c or min_c==0:\n",
    "                new = [n//2,c+doubling_cost] #if that's the case add it\n",
    "                cases.append(new)\n",
    "                #cases.insert(0,new)\n",
    "        else:\n",
    "#             print(3)\n",
    "            if c+doubling_cost+step_cost<=min_c or min_c==0: #moving back or forward once and halving\n",
    "                new = [(n-1)//2,c+step_cost+doubling_cost]\n",
    "                cases.append(new)\n",
    "                new = [(n+1)//2,c+step_cost+doubling_cost]\n",
    "                cases.append(new)\n",
    "        if (n//2)*step_cost<doubling_cost: # if actually going down n//2 times step by step is better than halving it, choose that\n",
    "            new = [n-1,c+step_cost]\n",
    "            cases.append(new)\n",
    "\n",
    "#     print(min_c)\n",
    "    return (min_c)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy.random as randomm"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "59"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "randomm.randint(1,100)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 41,
   "metadata": {},
   "outputs": [
    {
     "ename": "SyntaxError",
     "evalue": "can't assign to operator (<ipython-input-41-6546716bb67f>, line 1)",
     "output_type": "error",
     "traceback": [
      "\u001b[1;36m  File \u001b[1;32m\"<ipython-input-41-6546716bb67f>\"\u001b[1;36m, line \u001b[1;32m1\u001b[0m\n\u001b[1;33m    --NotebookApp.iopub_data_rate_limit=10000000000\u001b[0m\n\u001b[1;37m                                                   ^\u001b[0m\n\u001b[1;31mSyntaxError\u001b[0m\u001b[1;31m:\u001b[0m can't assign to operator\n"
     ]
    }
   ],
   "source": [
    "# --NotebookApp.iopub_data_rate_limit=10000000000"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "24"
      ]
     },
     "execution_count": 22,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "func(4,13,2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "18"
      ]
     },
     "execution_count": 23,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "func1(4,13,2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "375 5835\n",
      "366 4773\n",
      "351 35087\n",
      "1505 174262\n",
      "408 28952\n",
      "181 7035\n",
      "1023 8024\n",
      "647 41478\n",
      "664 87438\n",
      "1323 15084\n",
      "1162 4866\n",
      "344 27020\n",
      "913 8136\n",
      "906 29900\n",
      "751 43641\n",
      "791 4125\n",
      "1704 24335\n",
      "1140 83572\n",
      "1325 51515\n",
      "1404 154881\n",
      "830 3060\n",
      "1146 11597\n",
      "783 65575\n",
      "1249 72862\n",
      "1316 22556\n",
      "1252 68786\n",
      "738 61845\n",
      "362 15322\n",
      "1333 68169\n",
      "578 3088\n",
      "143 1004\n",
      "930 45675\n",
      "714 21515\n",
      "671 3700\n",
      "612 96330\n",
      "257 31123\n",
      "690 71844\n",
      "1168 15549\n",
      "950 153428\n",
      "525 2689\n",
      "744 24760\n",
      "249 1110\n",
      "952 11651\n",
      "979 14179\n",
      "1295 67115\n",
      "720 65040\n",
      "285 40563\n",
      "342 528\n",
      "932 14702\n",
      "502 5720\n",
      "685 1659\n",
      "706 17545\n",
      "16 605\n",
      "1649 50238\n",
      "528 40519\n",
      "600 21564\n",
      "328 98888\n",
      "632 45180\n",
      "525 71643\n",
      "376 15160\n",
      "715 2562\n",
      "1493 73729\n",
      "1253 5973\n",
      "648 25353\n",
      "93 1863\n",
      "133 276\n",
      "1014 111722\n",
      "460 1080\n",
      "625 14413\n",
      "642 8962\n",
      "701 75734\n",
      "1155 71225\n",
      "1257 43779\n",
      "187 5533\n",
      "241 6625\n",
      "766 20302\n",
      "1656 71499\n",
      "662 1745\n",
      "497 125201\n",
      "1395 16947\n",
      "456 48452\n",
      "158 798\n",
      "716 28436\n",
      "402 10911\n",
      "472 34268\n",
      "734 13994\n",
      "562 3432\n",
      "958 9146\n",
      "1070 48734\n",
      "1472 92828\n",
      "982 53189\n",
      "840 15151\n",
      "576 1227\n",
      "565 7308\n",
      "654 3265\n",
      "412 23245\n",
      "1072 129079\n",
      "920 51456\n",
      "1642 51833\n",
      "611 59651\n"
     ]
    }
   ],
   "source": [
    "count = 0\n",
    "wrong = []\n",
    "for i in range(100):\n",
    "    sc = randomm.randint(1,100)\n",
    "    dc = randomm.randint(1,100)\n",
    "    des = randomm.randint(1,10000)\n",
    "#     print([sc,des,dc,func1(sc,des,dc),func(sc,des,dc)])\n",
    "    temp1,temp2 = func1(sc,des,dc),func(sc,des,dc)\n",
    "    print(temp1,temp2)\n",
    "    if temp1!=temp2:\n",
    "        count+=1\n",
    "        wrong.append([sc,des,dc,temp1,temp2])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "100\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "[[78, 585, 7, 375, 5835],\n",
       " [3, 9639, 33, 366, 4773],\n",
       " [26, 9532, 17, 351, 35087],\n",
       " [97, 5881, 85, 1505, 174262],\n",
       " [64, 3648, 18, 408, 28952],\n",
       " [23, 1746, 6, 181, 7035],\n",
       " [20, 4444, 87, 1023, 8024],\n",
       " [51, 3291, 31, 647, 41478],\n",
       " [86, 7179, 18, 664, 87438],\n",
       " [72, 3901, 81, 1323, 15084],\n",
       " [34, 8302, 84, 1162, 4866],\n",
       " [54, 8688, 14, 344, 27020],\n",
       " [7, 7196, 89, 913, 8136],\n",
       " [43, 4775, 55, 906, 29900],\n",
       " [28, 6659, 53, 751, 43641],\n",
       " [28, 631, 85, 791, 4125],\n",
       " [86, 7925, 99, 1704, 24335],\n",
       " [64, 5389, 63, 1140, 83572],\n",
       " [40, 6936, 95, 1325, 51515],\n",
       " [96, 6589, 69, 1404, 154881],\n",
       " [45, 565, 70, 830, 3060],\n",
       " [39, 1779, 97, 1146, 11597],\n",
       " [89, 7460, 26, 783, 65575],\n",
       " [73, 9177, 68, 1249, 72862],\n",
       " [62, 1371, 98, 1316, 22556],\n",
       " [37, 6368, 97, 1252, 68786],\n",
       " [69, 3208, 42, 738, 61845],\n",
       " [68, 1247, 9, 362, 15322],\n",
       " [77, 9065, 67, 1333, 68169],\n",
       " [11, 3873, 52, 578, 3088],\n",
       " [1, 2864, 17, 143, 1004],\n",
       " [95, 8667, 35, 930, 45675],\n",
       " [61, 4442, 29, 714, 21515],\n",
       " [7, 8610, 59, 671, 3700],\n",
       " [66, 6737, 18, 612, 96330],\n",
       " [61, 7683, 1, 257, 31123],\n",
       " [67, 5163, 24, 690, 71844],\n",
       " [73, 2249, 73, 1168, 15549],\n",
       " [86, 9969, 40, 950, 153428],\n",
       " [1, 5920, 72, 525, 2689],\n",
       " [48, 1546, 56, 744, 24760],\n",
       " [12, 950, 21, 249, 1110],\n",
       " [37, 1757, 77, 952, 11651],\n",
       " [88, 1894, 49, 979, 14179],\n",
       " [38, 6460, 97, 1295, 67115],\n",
       " [60, 5173, 30, 720, 65040],\n",
       " [42, 7230, 9, 285, 40563],\n",
       " [26, 21, 93, 342, 528],\n",
       " [90, 1892, 52, 932, 14702],\n",
       " [33, 2208, 37, 502, 5720],\n",
       " [19, 1074, 69, 685, 1659],\n",
       " [38, 7746, 43, 706, 17545],\n",
       " [1, 4688, 1, 16, 605],\n",
       " [71, 8881, 96, 1649, 50238],\n",
       " [29, 9577, 25, 528, 40519],\n",
       " [12, 5844, 48, 600, 21564],\n",
       " [56, 5860, 4, 328, 98888],\n",
       " [86, 3575, 24, 632, 45180],\n",
       " [81, 7309, 3, 525, 71643],\n",
       " [44, 8532, 12, 376, 15160],\n",
       " [71, 93, 72, 715, 2562],\n",
       " [79, 3178, 94, 1493, 73729],\n",
       " [39, 3974, 98, 1253, 5973],\n",
       " [45, 8744, 36, 648, 25353],\n",
       " [15, 2169, 3, 93, 1863],\n",
       " [5, 541, 14, 133, 276],\n",
       " [61, 6373, 54, 1014, 111722],\n",
       " [33, 85, 59, 460, 1080],\n",
       " [34, 1639, 43, 625, 14413],\n",
       " [17, 8683, 46, 642, 8962],\n",
       " [94, 3294, 21, 701, 75734],\n",
       " [44, 6597, 77, 1155, 71225],\n",
       " [51, 2886, 90, 1257, 43779],\n",
       " [11, 3606, 11, 187, 5533],\n",
       " [38, 8019, 1, 241, 6625],\n",
       " [88, 737, 46, 766, 20302],\n",
       " [90, 8972, 93, 1656, 71499],\n",
       " [1, 8805, 87, 662, 1745],\n",
       " [72, 9929, 5, 497, 125201],\n",
       " [51, 3788, 99, 1395, 16947],\n",
       " [26, 5947, 25, 456, 48452],\n",
       " [20, 162, 14, 158, 798],\n",
       " [88, 8510, 28, 716, 28436],\n",
       " [93, 1140, 3, 402, 10911],\n",
       " [68, 4597, 11, 472, 34268],\n",
       " [62, 808, 54, 734, 13994],\n",
       " [26, 8079, 36, 562, 3432],\n",
       " [35, 3859, 68, 958, 9146],\n",
       " [26, 5932, 81, 1070, 48734],\n",
       " [92, 5092, 92, 1472, 92828],\n",
       " [83, 7560, 50, 982, 53189],\n",
       " [36, 8592, 55, 840, 15151],\n",
       " [93, 2057, 27, 576, 1227],\n",
       " [19, 7833, 36, 565, 7308],\n",
       " [13, 1218, 73, 654, 3265],\n",
       " [59, 8583, 9, 412, 23245],\n",
       " [99, 6896, 52, 1072, 129079],\n",
       " [36, 5503, 64, 920, 51456],\n",
       " [82, 8809, 89, 1642, 51833],\n",
       " [41, 5542, 27, 611, 59651]]"
      ]
     },
     "execution_count": 16,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "print(count)\n",
    "wrong"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "7060"
      ]
     },
     "execution_count": 12,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "70+20*(10)+97*(70)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "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.7.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}