[For beginners in competition professionals] I tried to solve 40 AOJ "ITP I" questions with python

Introduction

In this article, AOJ introduced in "Guidelines for improving competition pros and AtCoder taught by Red Coder [Beginner: Let's start competition pros]" I will explain 40 questions of "Introduction To Programming I" in Python.

I myself started competitive programming with no programming experience. After reading the introductory book "Self-study programmer from the basics of the Python language to how to work", "Introduction To Programming I" I worked on //judge.u-aizu.ac.jp/onlinejudge/finder.jsp?course=ITP1). It's just an individual story, but after solving 40 questions, tea performance can be served at ** AtCoder Beginner Contest (ABC) ** held at Atcoder. I think that I will acquire the basic knowledge for competitive programming.

ITP1_1_A Hello World

ITP1_1_A


print("Hello World")

[Explanation] print outputs Hello World.

ITP1_1_B X:Cubic

ITP1_1_B


x=int(input())
print(x**3)

[Explanation] Since ʻinput ()is received as a character string, it is processed after making it a numerical value with ʻint ().

ITP1_1_C Rectangle

ITP1_1_C


a,b=map(int,input().split())
print(a*b,2*(a+b))

[Explanation] ʻinput (). Split ()can be used for 1-row / multi-column input. However, since it is received as a character string, it is processed after converting it to a numerical value withmap and ʻint. For input, refer to "Introduction to Python with AtCoder".

ITP1_1_D Watch

ITP1_1_D


S=int(input())
print(S//3600,":",(S%3600)//60,":",S%60, sep="")

[Explanation] The quotient of seconds divided by 3600 is h, the quotient of seconds divided by 3600 divided by 60 is m, and the number of seconds is 60. The remainder after dividing is s. To connect h, m, s and: with+, h, m, s must be a string. Even if a character string and a numerical value are mixed, if it is print, it can be output without any problem. For the output, refer to "Introduction to Python with AtCoder".

ITP1_2_A Small, Large, or Equal

ITP1_2_A


a,b=map(int,input().split())
if a>b:
    print("a > b")
elif a<b:
    print("a < b")
else:
    print("a == b")

[Explanation] Write as it is said.

ITP1_2_B Range

ITP1_2_B


a,b,c=map(int,input().split())
if a<b and b<c:
    print("Yes")
else:
    print("No")

[Explanation] There is no problem even if you write ʻa <b <c`.

ITP1_2_C Sorting Three Numbers

ITP1_2_C


three_numbers=list(map(int,input().split()))
three_numbers.sort()
print(*three_numbers)

[Explanation] list will appear for the first time. list is an object that contains multiple elements. "[Introduction to Python] List usage and method summary" will be helpful. If you can afford it, you should also study tuple and dict. To sort a list, you can use " list name ".sort () or sorted ("list name "). For more information on these differences, see "Differences between sort and sorted in Python for sorting lists".

ITP1_2_D Circle in a Rectangle

ITP1_2_D


W,H,x,y,r = map(int,input().split())
Flag=True
if x+r>W or x-r<0:
    Flag=False
if y+r>H or y-r<0:
    Flag=False
if Flag:
    print("Yes")
else:
    print("No")

[Explanation] Check that the circles do not protrude from the rectangle in the horizontal and vertical directions. Create a Flag and set it to False when the conditions are no longer met. If it is True to the end, the circle will fit in a rectangle, otherwise it will be either vertical or horizontal. True``False is called a bool type. "[Introduction to Python] Learn the uses and usage of Boolean!" will be helpful.

ITP1_3_A Print Many Hello World

ITP1_3_A


for i in range(1000):
    print("Hello World")

[Explanation] This is the first time that the repeated for has appeared. You can refer to this "[Introduction to Python] How to write repetitive statements using for statements".

ITP1_3_B Print Test Cases

ITP1_3_B


case_number=0
while True:
    x=int(input())
    case_number+=1
    if x==0:
        break
    print("Case {}: {}".format(case_number,x))

[Explanation] Execute until the input becomes 0 with while. For while, refer to "Loop processing by Python while statement (infinite loop, etc.)". Competitive programming often outputs Case i: result. There are several output methods in python, one of which is format. format is a string method that allows you to embed variables inside a string (only available in Python 2.6 and above). Here "[Introduction to Python] How to output the contents of variables with the format method" will be helpful.

ITP1_3_C Swapping Two Numbers

ITP1_3_C


while True:
    x,y=map(int,input().split())
    if x==0 and y==0:
        break
    if x>y:
        print(y,x)
    else:
        print(x,y)

[Explanation] Execute until the input becomes 0 0 with while. After that, check the magnitude relationship of x, y and output.

ITP1_3_D How Many Divisors?

ITP1_3_D


a,b,c=map(int,input().split())
cnt=0
for k in range(a,b+1):
    if c%k==0:
        cnt+=1
print(cnt)

[Explanation] Check one by one whether the integers from ʻa to bare divisors ofc. If it is a divisor, increase cnt` (count) by one.

ITP1_4_A A/B Problem

ITP1_4_A


a,b=map(int,input().split())
print(a//b,a%b,"{:.6f}".format(a/b))

ITP1_4_A (another solution)


a,b=map(int,input().split())
print(a//b,a%b,round((a/b),6))

[Explanation] The problem is how to handle the decimal error of ʻa / b. You can specify the decimal point digit of a number by using format. ["Mastering Python's format () method"](https://www.itbook.info/network/python20.html) will be helpful. Alternatively, you can round off to keep the decimal error within the constraints of the problem. Note that round` is not strictly rounded. For rounding, refer to "Rounding decimals and integers in Python round and Decimal.quantize".

ITP1_4_C Simple Calculator

ITP1_4_C


while True:
    a,op,b=input().split()
    a=int(a)
    b=int(b)

    if op=="?":
         break
    if op=="+":
        print(a+b)
    if op=="-":
        print(a-b)
    if op=="*":
        print(a*b)
    if op=="/":
        print(a//b)

[Explanation] Execute until ? appears with while. After that, addition, subtraction, multiplication, and division are output respectively.

ITP1_4_D Min, Max and Sum

ITP1_4_D


N=int(input())
a=list(map(int,input().split()))
print(min(a),max(a),sum(a))

[Explanation] In Python, the maximum, minimum, and total of list can be calculated by max (list name) min (list name) sum (list name), respectively.

ITP1_5_A Print a Rectangle

ITP1_5_A


while True:
    H,W= map(int,input().split())
    if H==0 and W==0:
        break
    for i in range(H):
        print("#"*W)
    print()

[Explanation] * is repeated in the character string. For example, " Hello World "* 3 becomes " Hello World Hello World Hello World ". The final print () means one line between the rectangles.

ITP1_5_B Print a Frame

ITP1_5_B


while True:
    H,W= map(int,input().split())
    if H==0 and W==0:
        break
    print("#"*W)
    for i in range(H-2):
        print("#"+"."*(W-2)+"#")
    print("#"*W)
    print()

[Explanation] Similar to the previous problem. However, the 1st and H lines are " ### ... ### ", but the 2nd to H-1 lines are " # ......... # ". Therefore, "output the first line", "output from the second line to the H-1 line (that is, the H-2 line)", and "output the H line".

ITP1_5_C Print a Chessboard

ITP1_5_C


while True:
    H,W=map(int,input().split())
    if H==0 and W==0:
         break
    for h in range(H):
        for w in range(W):
            if (h+w)%2==0:
                print("#",end="")
            else:
                print(".",end="")
        print()
    print()

[Explanation] You can write for in for. It is called a double loop. (Reference: "break from multiple loops (nested for loops) in Python") If you look closely at the check pattern you want to output, you will see a line. Notice that the sum of the number and the number of columns is # when it is even, and . when it is odd (note that in Python it counts as line 0, line 1, and so on). Output in turn on each row and start a new line in the last column. However, if you do something like print ("# "), a line break will occur after #. To avoid that, use ʻend =" "` to avoid line breaks on output.

ITP1_5_D Structured Programming

ITP1_5_D


N=int(input())
for i in range(1,N+1):
    if i%3==0 or "3" in str(i):
        print(" {}".format(i),end="")
print()

[Explanation] First, understand the meaning of the problem. It's a painful problem if you can't read the C ++ code, but since C ++ is often used in the explanation of competitive programming, it may be good to make it readable. For example, the code for a book commonly known as "Arimoto" is written in C ++. The problem this time is ** "Among the natural numbers less than or equal to n, output multiples of 3 or numbers with 3 in ascending order" **. You can easily tell that it is a multiple of 3 by looking at the remainder after dividing by 3. This time, I used ʻin` as a character string to confirm that 3 is attached. To determine whether an arbitrary character string is included, "Search a character string with Python (determine whether it contains ~, get position, count)" Will be helpful.

ITP1_6_A Reversing Numbers

ITP1_6_A


N=int(input())
a=list(map(int,input().split()))
a=a[::-1]
print(*a)

[Explanation] To reverse the order of the list, you can sort by the list type method reverse, the built-in function reversed, and the slice. This time I used slices. The reverse order of the list is "Reverse list or string in Python", but the slice is "List or character by Python slice". Partial selection / substitution of columns " will be helpful.

ITP1_6_B Finding Missing Cards

ITP1_6_B


N=int(input())
suits=["S","H","C","D"]
cards=[]
for _ in range(N):
    s,n=input().split()
    if s=="S":
        cards.append(int(n))   
    elif s=="H":
        cards.append(13+int(n))   
    elif s=="C":
        cards.append(26+int(n))
    else:
        cards.append(39+int(n))

for i in range(1,53):
    if i not in cards:
        print(suits[(i-1)//13],(i-1)%13+1)

[Explanation] Let's think about how to express the Trump mark and numbers together. Marks and numbers can be represented at the same time by representing spades from 1 to 13, hearts from 14 to 26, clovers from 27 to 39, and diamonds from 40 to 52. For example, 3 of the heart becomes 16. Then make a list of the cards you had first. After that, check if you have the numbers from 1 to 52 (that is, all 52 playing cards) one by one, and if you do not have it, output it.

[Memo] Actually, it is necessary to be careful when using ʻin for problems that require attention to the amount of calculation. For the amount of calculation, ["Summary of how to calculate the amount of calculation order! ~ Where the log comes from ~"](https://qiita.com/drken/items/872ebc3a2b5caaa4a0d0) is helpful. Find out if ʻi is in list The complexity of ʻi in listis $ O (n) $. This means that each element inlist is checked to see if ʻi is equal. There is no problem if the number of cards is about the same as playing cards, but if the number is large, the amount of calculation may be enormous, so be careful.

ITP1_6_C Official House

ITP1_6_C


N=int(input())
room=[[[0]*10 for _ in range(3)] for _ in range(4)]

for _ in range(N):
    b,f,r,v=map(int,input().split())
    room[b-1][f-1][r-1]+=v

for i in range(4):
    for j in range(3):
        for k in range(10):
            print(" {}".format(room[i][j][k]), end="")
        print()
    if i!=3:
        print("####################")

[Explanation] This problem can be solved with a multidimensional array. "How to handle multidimensional arrays in Python [for beginners]" will be helpful. Matching the output format is a bit of a challenge.

ITP1_6_D Matrix Vector Multiplication

ITP1_6_D


n,m=map(int,input().split())
A=[list(map(int,input().split())) for i in range(n)]
b=[int(input()) for i in range(m)]
for i in range(n):
    ans=0
    for j in range(m):
        ans+=A[i][j]*b[j]
    print(ans)

[Explanation] This problem can also be solved by processing with a multidimensional array. It will be a matrix calculation.

ITP1_7_A Grading

ITP1_7_A


while True:
    m,f,r=map(int,input().split())
    if m==-1 and f==-1 and r==-1:
        break
    sum=m+f
    if m==-1 or f==-1 :
        print("F")
    elif sum>=80:
        print("A")
    elif sum>=65:
        print("B")
    elif sum>=50:
        print("C")
    elif sum>=30:
        if r>=50:
            print("C")
        else:
            print("D")
    else:
        print("F")

[Explanation] Read the problem carefully and perform conditional branching.

ITP1_7_B How many ways?

ITP1_7_C


while True:
    n,x=map(int,input().split())
    if n==0 and x==0 :
        break
    cnt=0
    for i in range(1,n-1):
        for j in range(i+1,n):
            if j<x-i-j<=n:
                cnt+=1
    print(cnt)

[Explanation] This is a problem that involves a little mathematical thinking. Consider adding three numbers from the numbers up to n without duplication to make x. For example, suppose you make 9 from a number from 1 to 5. At this time, 1 + 3 + 5 and 3 + 5 + 1 are the same combination of numbers, so they are regarded as the same combination. In order not to count such combinations multiple times, we will select under the rule that "the number to be selected next is always larger than the number selected before". First select ʻi, then select a larger j. After that, if x-i-j is larger than jand less thann`, it is established as a combination.

ITP1_7_C Spreadsheet

ITP1_7_C


r,c=map(int,input().split())
sheet=[list(map(int,input().split())) for i in range(r)]
for i in range(r):
    sheet[i].append(sum(sheet[i]))
Column_sum=[0]*(c+1)
for j in range(c+1):
    for i in range(r):
        Column_sum[j]+=sheet[i][j]

for i in range(r):
    print(*sheet[i])
print(*Column_sum)

[Explanation] First, create a two-dimensional array of r * c. Find and add the sum for each row and the sum for each column. It is a problem that can be solved by combining the conventional ideas. This time, the sum of the rows is sum, and the sum of the columns is calculated by adding the number of the jth column of each row by one.

ITP1_7_D Matrix Multiplication

ITP1_7_D


n,m,l=map(int,input().split())
A=[list(map(int,input().split())) for i in range(n)]
B=[list(map(int,input().split())) for i in range(m)]

C=[]
for i in range(n):
    line=[]
    for j in range(l):
        c=0
        for k in range(m):
            c+=A[i][k]*B[k][j]
        line.append(c)
    C.append(line)

for line in C:
    print(*line)

[Explanation] A two-dimensional array is used. You need to understand and write the index.

ITP1_8_A Toggling Cases

ITP1_8_A


words=input()
print(str.swapcase(words))

[Explanation] There are several methods that can be used to convert uppercase and lowercase letters. This problem can be easily solved by using one of them, swapcase. There are other methods you should know, such as ʻupperandlower`. You may want to read "Python uppercase and lowercase conversion (upper / lower / capitalize / swapcase / title)".

ITP1_8_B Sum of Numbers

ITP1_8_B


while True:
    str_n=input()
    if str_n=="0":
        break
    list_n=list(str_n)
    ans=0
    for n in list_n:
        ans+=int(n)
    print(ans)

ITP1_8_B alternative solution


while True:
    str_n=input()
    if str_n=="0":
        break
    print(sum(list(map(int,str_n))))

[Explanation] This time, I dare to receive the numerical value as a character string. List the strings. For example, for the string " 123 ", if you uselist ("123"), it will be["1", "2", "3"]. After that, use for to extract the number of each place one by one. However, since it can be extracted as a character string, it is added after converting it to a numerical value with ʻint () . You can also write more concisely using map`, which has been used for standard input so far.

ITP1_8_C Counting Characters

ITP1_8_C


import sys
texts=sys.stdin.read()
texts=texts.lower()
cnt=[0]*26

letters=list('abcdefghijklmnopqrstuvwxyz')
for x in texts:
    i=0
    for y in letters:
        if x==y:
            cnt[i]+=1
        i+=1
for i in range(26):
    print(letters[i]+" : "+str(cnt[i]))

[Explanation] Until now, standard input has been received using ʻinput. This time, I have to read an English sentence with multiple lines and the number of lines is unknown. It is possible to combine while and ʻinput, but use the sys module sys.stdin.read. You can receive a multi-line character string as it is. For details, ["Python] Receive data from the keyboard with standard input (sys.stdin.readlines, input function)"](https://algorithm.joho.info/programming/python-sys-stdin-readline/#toc3) Please refer to. After inputting, make all lowercase letters, check the alphabet one by one in English, and count.

ITP1_8_D Ring

ITP1_8_D


s=input()
p=input()
s*=2
if s.find(p)!=-1:
    print("Yes")
else :
    print("No")

[Explanation] Consider whether you can create a certain character string from a ring-shaped character string. A ring-shaped string has no beginning and end, and you can make as long a string as you like. However, in this problem, the condition is that p is shorter than s. Therefore, it is enough to think about two laps of the ring. Create a string that corresponds to two laps of the ring, and check if you can make p there. Use the string method find to see if there is ap. find gets the position of a particular string, but returns -1 if there is no string. "Search a character string with Python (determine whether it contains ~, get position, count)" will be helpful.

ITP1_9_A Finding a Word

ITP1_9_A


import sys
word=input()
text=sys.stdin.read()
print(text.lower().split().count(word))

[Explanation] Input is done with sys.stdin.read. I will explain about text.lower (). Split (). Count (word). Use lower () to lowercase it. Use split () to separate each space into a list. It is the same as split of ʻinput (). Split ()with normal standard input. ["Split character string with Python (delimiter, line feed, regular expression, number of characters)"](https://note.nkmk.me/python-split-rsplit-splitlines-re/) will be helpful. Use thecount` method to find out how many are in the list. "[Python] Counting the number of occurrences of a specific character or character string (count)" is helpful.

ITP1_9_B Shuffle

ITP1_9_B


while True:
    cards=input()
    if cards=="-":
        break
    m=int(input())
    for i in range(m):
        sh=int(input())
        former=cards[:sh]
        later=cards[sh:]
        cards=later+former
    print(cards)

[Explanation] It can be solved using slices in the list.

ITP1_9_C Card Game

ITP1_9_C


n=int(input())
T=0
H=0
for i in range(n):
    card_t,card_h=input().split()
    if card_t==card_h:
        T+=1
        H+=1
    else:
        if card_h>card_t:
            H+=3
        else:
            T+=3
print(T,H)

[Explanation] If you use > or < in the character string, the result of comparison in dictionary order will be returned. You can use this to solve it.

ITP1_9_D Transformation

ITP1_9_D


text=input()
n=int(input())
for i in range(n):
    order=input().split()
    a,b=map(int,order[1:3])
    if order[0]=="print":
        print(text[a:b+1])
    elif order[0]=="reverse":
        re_text=text[a:b+1]
        text=text[:a]+re_text[::-1]+text[b+1:]
    else :
        text=text[:a]+order[3]+text[b+1:]

[Explanation] As before, you can solve it using slices of the list. However, you need to be a little careful when using reverse. When changing step to -1 in a slice, start and ʻendare not interpreted literally. This [question](https://stackoverflow.com/questions/41430791/python-list-error-1-step-on-1-slice) will be helpful. This time, I made a list of the range I want toreverse` and then did it in reverse order.

ITP1_10_A Distance

ITP1_10_A


x1,y1,x2,y2=map(float,input().split())
print(((x1-x2)**2+(y1-y2)**2)**0.5)

[Explanation] The route can be calculated by importing the math module and usingmath.sqrt ()or by ** 0.5.

ITP1_10_B Triangle

ITP1_10_B


import math
a,b,C=map(float,input().split())
θ=math.radians(C)
h=b*math.sin(θ)
S=(a*h)/2
c=math.sqrt(a**2+b**2-2*a*b*math.cos(θ))
L=a+b+c
print(S,L,h,sep="\n")

[Explanation] Triangular ratio uses the math module. The conversion between radians and radians is "Mutual conversion between radians and radians", and the trigonometric ratio is ["Calculate trigonometric functions with Python (sin, cos). , tan, arcsin, arccos, arctan) "" (https://note.nkmk.me/python-math-sin-cos-tan/) will be helpful. The length of c is calculated by the cosine theorem.

ITP1_10_C Standard Deviation

ITP1_10_C


while True:
    n=int(input())
    if n==0:
        break
    score=list(map(int,input().split()))
    mean=sum(score)/n
    var_sum=0
    for i in range(n):
        var_sum+=(score[i]-mean)**2
    print((var_sum/n)**0.5)

[Explanation] Statistic can be calculated using modules such as statistics, but this time it is calculated and calculated as described in the problem statement. First, calculate the average value. Find the mean square of the difference from the mean. This is distribution. If you take that route, it will be the standard deviation you find this time.

ITP1_10_D Distance II

ITP1_10_D


def Distance(X,Y,p):
    s=0
    for x,y in zip(X,Y):
        s+=abs(x-y)**p
    print(s**(1/p))

n=int(input())
X=list(map(int,input().split()))
Y=list(map(int,input().split()))

for p in range(1,4):
    Distance(X,Y,p)
print(max(abs(x-y) for x,y in zip(X,Y)))

[Explanation] Until now, we have used existing libraries, but you can also define your own functions. This time, we will define a function that outputs the distance Distance. For the definition of the function, refer to "Define / call function in Python (def, return)". Only the Chebyshev distance is calculated separately. The zip function is also useful when retrieving elements from multiple lists. "How to use Python, zip function: Get multiple list elements at once" is helpful.

Finally

When writing the commentary, I was conscious of as much information as possible that could be touched as concisely as possible. I dared to solve problems that can be solved by using multiple lists with a multidimensional array. However, I tried to keep one or two new things per question so that it wouldn't suddenly become difficult. I'm still a beginner, but I think it's an article that makes me happy when I'm just starting out with Python. After "Introduction To Programming I", "Red Coder teaches you how to improve AtCoder. I think that you should tackle the problem of full search as introduced in the guideline [Beginner: Let's start the competition pro]. While working on the full search problem, I also practiced quick solving so that I could solve the three questions A, B, and C of the ABC contest within a total of 30 minutes. I hope it will be helpful to everyone. Thank you for reading to the end.

Recommended Posts

[For beginners in competition professionals] I tried to solve 40 AOJ "ITP I" questions with python
I tried to solve the ant book beginner's edition with python
[Pandas] I tried to analyze sales data with Python [For beginners]
I tried to refer to the fun rock-paper-scissors poi for beginners with Python
I tried to solve the soma cube with python
I tried to solve the problem with Python Vol.1
I tried to solve AOJ's number theory with Python
[Python] I tried to solve 100 past questions that beginners and intermediates should solve [Part 5/22]
[Python] I tried to solve 100 past questions that beginners and intermediates should solve [Part7 / 22]
[Python] I tried to solve 100 past questions that beginners and intermediates should solve [Part 4/22]
[Python] I tried to solve 100 past questions that beginners and intermediates should solve [Part3 / 22]
[Python] I tried to solve 100 past questions that beginners and intermediates should solve [Part 1/22]
[Python] I tried to solve 100 past questions that beginners and intermediates should solve [Part 6/22]
Tohoku University 2020 First semester math exam (science) I tried to solve major questions 1 to 3 with Python
I want to solve APG4b with Python (only 4.01 and 4.04 in Chapter 4)
I tried to implement PLSA in Python
I tried to implement PLSA in Python 2
I wanted to solve ABC160 with Python
I tried to implement ADALINE in Python
I wanted to solve ABC159 in Python
I tried to implement PPO in Python
I tried to solve TSP with QAOA
I wanted to solve ABC172 with Python
[Python] I tried to explain words that are difficult for beginners to understand in an easy-to-understand manner.
How to write offline real time I tried to solve E11 with python
I tried to solve AtCoder's depth-first search (DFS) in Python (result: TLE ...)
How to write offline real time I tried to solve E12 with python
I wanted to solve NOMURA Contest 2020 with Python
I tried to integrate with Keras in TFv1.1
I tried to get CloudWatch data with Python
I tried to output LLVM IR with Python
Try to calculate RPN in Python (for beginners)
I tried to implement TOPIC MODEL in Python
I tried to automate sushi making with python
I want to solve APG4b with Python (Chapter 2)
I tried to implement selection sort in python
[Introduction for beginners] Working with MySQL in Python
I tried to implement merge sort in Python with as few lines as possible
Python / PEP8> E128 I tried to solve continuation line under-indented for visual indent
[For beginners] How to use say command in python!
I tried to implement Minesweeper on terminal with python
I tried to get started with blender python script_Part 01
I tried to touch the CSV file with Python
I tried to draw a route map with Python
I tried to implement a pseudo pachislot in Python
I tried to get started with blender python script_Part 02
I tried to implement Dragon Quest poker in Python
I was addicted to scraping with Selenium (+ Python) in 2020
I tried to implement an artificial perceptron with python
I want to work with a robot in python.
I tried to implement GA (genetic algorithm) in Python
I tried to automatically generate a password with Python3
I tried to summarize how to use pandas in python
I tried to analyze J League data with Python
[For beginners] Web scraping with Python "Access the URL in the page to get the contents"
I tried to build an environment for machine learning with Python (Mac OS X)
The 15th offline real-time I tried to solve the problem of how to write with python
I tried fp-growth with python
I tried scraping with Python
I tried gRPC with Python
I tried scraping with python