{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# [Chef and Strings](https://www.codechef.com/JULY20B/problems/CHEFSTR1)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Having already mastered cooking, Chef has now decided to learn how to play the guitar. Often while trying to play a song, Chef has to skip several strings to reach the string he has to pluck. Eg. he may have to pluck the 1st string and then the 6th string. This is easy in guitars with only 6 strings; However, Chef is playing a guitar with 106 strings. In order to simplify his task, Chef wants you to write a program that will tell him the total number of strings he has to skip while playing his favourite song.\n",
    "\n",
    "![fig1](https://codechef_shared.s3.amazonaws.com/download/Images/JULY20/CHEFSTR1/CHEFSTR1.png)\n",
    "\n",
    "This is how guitar strings are numbered (In ascending order from right to left). Eg. to switch from string 1 to 6, Chef would have to skip 4 strings (2,3,4,5).\n",
    "\n",
    "***Input:***\\\n",
    "First line will contain T, number of testcases. Then the testcases follow.\\\n",
    "The first line of each test case contains N, the number of times Chef has to pluck a string\\\n",
    "The second line of each test case contains N space separated integers - S1, S2, …, SN, where Si is the number of the ith string Chef has to pluck.\\\n",
    "***Output:***\\\n",
    "For each testcase, output the total number of strings Chef has to skip over while playing his favourite song.\n",
    "\n",
    "***Constraints***\\\n",
    "1≤T≤10\\\n",
    "2≤N≤105\\\n",
    "1≤Si≤106\\\n",
    "For each valid i, Si≠Si+1\\\n",
    "Subtasks\\\n",
    "30 points : for each valid i, Si<Si+1\\\n",
    "70 points : No additional constraints\\\n",
    "***Sample Input:***\\\n",
    "2\\\n",
    "6\\\n",
    "1 6 11 6 10 11\\\n",
    "4\\\n",
    "1 3 5 7\\\n",
    "***Sample Output:***\\\n",
    "15\\\n",
    "3\\\n",
    "***Explanation:***\\\n",
    "***Test Case 1***\n",
    "\n",
    "Chef skips 4 strings (2,3,4,5) to move from 1 to 6\\\n",
    "Chef skips 4 strings (7,8,9,10) to move from 6 to 11\\\n",
    "Chef skips 4 strings (10,9,8,7) to move from 11 to 6\\\n",
    "Chef skips 3 strings (7,8,9) to move from 6 to 10\\\n",
    "Chef skips 0 strings to move from 10 to 11\\\n",
    "Therefore, the answer is 4+4+4+3+0=15\n",
    "\n",
    "***Test Case 2***\n",
    "\n",
    "Chef skips 1 string to move from 1 to 3\\\n",
    "Chef skips 1 string to move from 3 to 5\\\n",
    "Chef skips 1 string to move from 5 to 7\\\n",
    "Therefore, the answer is 1+1+1=3"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stdin",
     "output_type": "stream",
     "text": [
      " 1\n",
      " 6\n",
      " 1 6 11 6 10 11\n"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "15\n"
     ]
    }
   ],
   "source": [
    "for _ in range(int(input())):\n",
    "    n=int(input())\n",
    "    a=list(map(int,input().split()))\n",
    "    c=0\n",
    "    for i in range(1,n):\n",
    "        c+=abs(a[i]-a[i-1])-1\n",
    "    print(c)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# [Chef and Card Game](https://www.codechef.com/JULY20B/problems/CRDGAME)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Chef is playing a card game with his friend Morty Smith.\n",
    "\n",
    "The rules of the game are as follows:\n",
    "\n",
    "There are two piles of cards, pile A and pile B, each with N cards in it. Pile A belongs to Chef and pile B belongs to Morty.\\\n",
    "Each card has one positive integer on it\\\n",
    "The ‘power’ of a card is defined as the sum of digits of the integer on that card\\\n",
    "The game consists of N rounds\\\n",
    "In each round, both players simultaneously draw one card each from the top of their piles and the player who draws the card with higher power wins this round and gets a point. If the powers of both players' cards are equal then they get 1 point each.\n",
    "The winner of the game is the player who has more points at the end of N rounds. If both players have equal number of points then the game ends in a draw.\n",
    "The game is now over and Chef has told Morty to find the winner. Unfortunately, this task is too complex for him. Help Morty find the winner.\n",
    "\n",
    "***Input:***\\\n",
    "First line will contain T, number of testcases.\\\n",
    "The first line of each test case will contain N, the number of rounds played.\\\n",
    "The ith of the next N lines of each test case will contain Ai and Bi, the number on the card drawn by Chef and Morty respectively in round i.\\\n",
    "***Output:***\\\n",
    "For each test case, output two space separated integers on a new line:\\\n",
    "Output\n",
    "\n",
    "0 if Chef wins,\\\n",
    "1 if Morty wins,\\\n",
    "2 if it is a draw\\,\n",
    "followed by the number of points the winner had.\\\n",
    "(If it is a draw then output either player’s points).\\\n",
    "***Constraints***\\\n",
    "1≤T≤1000\\\n",
    "1≤N≤100\\\n",
    "1≤Ai,Bi≤109\\\n",
    "Subtasks\\\n",
    "100 points : No additional constraints\\\n",
    "***Sample Input:***\\\n",
    "2\\\n",
    "3\\\n",
    "10 4\\\n",
    "8 12\\\n",
    "7 6\\\n",
    "2\\\n",
    "5 10\\\n",
    "3 4\\\n",
    "***Sample Output:***\\\n",
    "0 2\\\n",
    "2 1\\\n",
    "***Explanation:***\\\n",
    "***Test Case 1:***\n",
    "\n",
    "***Round 1:***\n",
    "\n",
    "Chef’s card has power 1+0 = 1,\\\n",
    "Morty’s card has power 4.\\\n",
    "Therefore, Morty wins the round.\n",
    "\n",
    "***Round 2:***\n",
    "\n",
    "Chef’s card has power 8,\\\n",
    "Morty’s card has power 1+2 = 3.\\\n",
    "Therefore, Chef wins the round.\n",
    "\n",
    "***Round 3:***\n",
    "\n",
    "Chef’s card has power 7,\\\n",
    "Morty’s card has power 6.\\\n",
    "Therefore, Chef wins the round.\n",
    "\n",
    "Therefore, Chef wins the game with 2 points (Morty has 1 point).\n",
    "\n",
    "***Test Case 2:***\n",
    "\n",
    "***Round 1:***\n",
    "\n",
    "Chef’s card has power 5,\\\n",
    "Morty’s card has power 1+0=1.\\\n",
    "Therefore, Chef wins the round.\n",
    "\n",
    "***Round 2:***\n",
    "\n",
    "Chef’s card has power 3,\\\n",
    "Morty’s card has power 4.\\\n",
    "Therefore, Morty wins the round.\n",
    "\n",
    "Therefore, the game ends in a draw and both players have 1 point each."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [],
   "source": [
    "def digit_sum(n):\n",
    "    sum_n=0\n",
    "    while n>0:\n",
    "        r=n%10\n",
    "        sum_n+=r\n",
    "        n//=10\n",
    "    return sum_n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "9"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "digit_sum(324)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "name": "stdin",
     "output_type": "stream",
     "text": [
      " 2\n",
      " 3\n",
      " 10 4\n",
      " 8 12\n",
      " 7 6\n"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0 2\n"
     ]
    },
    {
     "name": "stdin",
     "output_type": "stream",
     "text": [
      " 2\n",
      " 5 10\n",
      " 3 4\n"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "2 1\n"
     ]
    }
   ],
   "source": [
    "for _ in range(int(input())):\n",
    "    c1=0\n",
    "    c2=0\n",
    "    for i in range(int(input())):\n",
    "        n1,n2=input().split()\n",
    "        if digit_sum(int(n1))>digit_sum(int(n2)):\n",
    "            c1+=1\n",
    "        elif digit_sum(int(n1))<digit_sum(int(n2)):\n",
    "            c2+=1\n",
    "        else:\n",
    "            c1+=1\n",
    "            c2+=1\n",
    "    if c1>c2:\n",
    "        print('0',c1)\n",
    "    elif c1<c2:\n",
    "        print('1',c2)\n",
    "    else:\n",
    "        print('2',c1)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Missing a Point"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "name": "stdin",
     "output_type": "stream",
     "text": [
      " 1\n",
      " 2\n",
      " 1 1\n",
      " 1 2\n",
      " 4 6\n",
      " 2 1\n",
      " 9 6\n",
      " 9 3\n",
      " 4 3\n"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "2 2\n"
     ]
    }
   ],
   "source": [
    "for _ in range(int(input())):\n",
    "    n=int(input())\n",
    "    l1=[]\n",
    "    l2=[]\n",
    "    for i in range(4*n-1):\n",
    "        n1,n2=input().split()\n",
    "        if n1 in l1:\n",
    "            l1.remove(n1)\n",
    "        else:\n",
    "            l1.append(n1)\n",
    "        if n2 in l2:\n",
    "            l2.remove(n2)\n",
    "        else:\n",
    "            l2.append(n2)\n",
    "    print(l1[0],l2[0])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "name": "stdin",
     "output_type": "stream",
     "text": [
      " 1\n",
      " 2\n",
      " 1 1\n",
      " 1 2\n",
      " 4 6\n",
      " 2 1\n",
      " 9 6\n",
      " 9 3\n",
      " 4 3\n"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "2 2 \n"
     ]
    }
   ],
   "source": [
    "from functools import reduce\n",
    "for _ in range(int(input())):\n",
    "    n=int(input())\n",
    "    l1=[]\n",
    "    l2=[]\n",
    "    for i in range(4*n-1):\n",
    "        m,n=map(int,input().split())\n",
    "        l1.append(m) \n",
    "        l2.append(n)\n",
    "    print(reduce(lambda x, y: x ^ y,l1),reduce(lambda x, y: x ^ y,l2))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# [Doctor Chef](https://www.codechef.com/JULY20B/problems/DRCHEF)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "name": "stdin",
     "output_type": "stream",
     "text": [
      " 1\n",
      " 5 1\n",
      " 40 30 20 10 50\n"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "49\n",
      "47\n",
      "43\n",
      "35\n",
      "19\n",
      "10\n"
     ]
    }
   ],
   "source": [
    "for _ in range(int(input())):\n",
    "    n1,n2=map(int,input().split())\n",
    "    a=list(map(int,input().split()))\n",
    "    c=len(a)\n",
    "    m=max(a)\n",
    "    if (m-n2)>0:\n",
    "        m-=n2\n",
    "        n2*=2\n",
    "        while m>0:\n",
    "            c+=1\n",
    "            print(m)\n",
    "            if (m-n2)>0:\n",
    "                m-=n2\n",
    "                n2*=2\n",
    "            else:\n",
    "                break\n",
    "        print(c)\n",
    "    else:\n",
    "        print(c)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "10"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "c"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<div class=\"LI-profile-badge\"  data-version=\"v1\" data-size=\"medium\" data-locale=\"en_US\" data-type=\"horizontal\" data-theme=\"dark\" data-vanity=\"keshavsingh4522\"><a class=\"LI-simple-link\" href='https://in.linkedin.com/in/keshavsingh4522?trk=profile-badge'>Keshav Singh</a></div>"
   ]
  },
  {
   "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.8.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}