[PYTHON] Story of trying competitive programming 2

Why?

This is a sequel to here. I will update it from time to time, and when I reach a certain level, I will move on to the next article.

Last updated: 1/19

Standard input

How to receive the numbers given in the problem. I think it's like a method and remember it with brain death.


#If you want to receive this kind of data
1
2 3
test

#Write like this
N = int(input()) # N = 1
b,c = map(int,input().split()) # b = 2, c = 3
S = input() # S = test

#If you want to receive this kind of data

3 2
1 2
5 5
-2 8

#Write like this

N, X = map(int, input().split())
l = [list(map(int, input().split())) for _ in range(N)]

The problem I did

B - Cakes and Donuts

Code written

#I want to buy cakes and donuts and see if there is a pattern that makes a total of just $ N

N = int(input())
cake = 4
donuts = 7
ans = "No"

#If N is a multiple of the price of the cake or donut, then if you keep buying either the cake or the donut, you'll get $ N
if N % cake == 0 or N % donuts == 0:
    print('Yes')
    exit()

#If the above conditions are not met, full search
#The point is to divide the index
for i in range(N):
    #First, fix the index of the cake and change the number of donuts to check if the conditions are met.
    for j in range(N):
        if N == (i*cake + j*donuts):
            ans = "Yes"
            break
print(ans)


B - 81

Code written

#I want to find out if a given integer fits in the multiplication table

N = int(input())
ans = 'No'

#Since it is a multiplication table, range(1,10)Can be achieved by trial of
for i in range(1,10):
    for j in range(1,10):
        if N == (i*j):
            ans = 'Yes'
            break
print(ans)

N = int(input())
ans = 'No'

def calculate(x,y):
  sample = x * y
  return sample

for i in range(1,10):
  for j in range(1,10):
    result = calculate(i,j)
    if result == N:
      ans = 'Yes'
print(ans)


B - Good Distance

Code written

#How many N coordinates in the D dimension have integer distances

import math
N, X = map(int, input().split())
#Get the given coordinates
l = [list(map(int, input().split())) for _ in range(N)]
count = 0


def test(x, y):
    d = 0
    #I want to calculate the axis distance of each coordinate for the number of X dimensions ex. X=In case of 2, the following calculation is performed between the X-axis and y-axis of each coordinate.
    for i in range(X):
        #Take the coordinates from l and compare them by the number of X dimensions. For example X=If it is 2, the loop ends by calculating the X axes first and then the Y axes.
        d += abs((x[i]-y[i]))**2
    #Returns the square root of d
    return math.sqrt(d)

#Dare to start from 1
for j in range(1, N):
    # j =If 1, range(1)And t=0 can be established
    for t in range(j):
        #How to retrieve the data of the multidimensional array is as follows
        result = test(l[j], l[t])
        if result == int(result):
            count += 1
print(count)



#How to extract numerical values ​​in the case of multidimensional array Application
# ex. num_list = [[1, 2], [5, 5], [-2, 8]]When

# sample =  num_list[0] = [1,2]
# sample1 =  num_list[1] = [5, 5]
# sample[0] = 1 = num_list[0][0]
#You can take it out with the same theory below
# sample[1] = 2
# sample1[0] = 5
# sample1[1] = 5

B - Making Triangle

Code written
#How many combinations make a triangle from the given side length

#module
import itertools

N = int(input())
l = list(map(int,input().split()))
count = 0
#Sort in ascending order
l.sort()
# itertools.combinations(iterable,int)Returns the combination of the number specified in the second argument in
for i in itertools.combinations(l,3):
    #The condition of the triangle is as follows because the total of the two sides is larger than the remaining one side, and this time the size of the three sides is different.
    if i[0] + i[1] > i[2] and i[0] != i[1] != i[2]:
        count += 1
print(count)

N = int(input())
num_list = list(map(int, input().split()))
count = 0
num_list.sort()

for i in itertools.combinations(num_list, 3):
  if i[0] + i[1] > i[2] and i[0] != i[1] != i[2]:
    count += 1
print(count)

B - Some Sums

Code written

#I want to add the digits of a given number to find the sum of the numbers that meet the conditions.

N,A,B = map(int,input().split())
new_list = []
#To represent the sum of the digits of a number, just keep adding the remainder after dividing by 10.
for i in range(1,N+1):
    #Save the number to try
    index = i
    ans = 0
    #Try until 0
    while i > 0:
        #Add the remainder
        ans += i % 10
        #Divide by 10
        i = i // 10
    #If the conditions are met, add the first saved number to the list
    if A <= ans <= B:
        new_list.append(index)
#Output list total
print(sum(new_list))


B - Palindromic Numbers

Code written

#I want to know the number of integers between A and B that are palindromic numbers.

A,B = map(int,input().split())
count = 0

#Convert integers to strings, list them, and compare them in reverse order.
for i in range(A,B+1):
    sample = str(i)
    sample2 = list(reversed(str(i)))
    sample2 = ''.join(sample2)
    if sample == sample2:
        count += 1
print(count)


A - Digits Sum

Code written

N = int(input())
ans = N

#If the remainder of dividing N by 10 is 0, the answer you want is 10.
if N % 10 == 0:
    print(10)
    exit()
#Otherwise
for i in range(1,N):
    #The liver is that the sum of the integers A and B is N, which means that B= N -That it is A
    A = i
    B = N - i
    sum1 = 0
    sum2 = 0
    while A > 0:
        sum1 += A % 10
        A //= 10
    while B > 0:
        sum2 += B % 10
        B //= 10
    if ans > sum1 + sum2:
        ans = sum1 + sum2
print(ans)


#Alternative 1 Store the sum of the sums of each of A and B in a list and extract only the minimum value from it.

for i in range(1, N):
    A = i
    B = N - i
    result1 = 0
    result2 = 0
    while A > 0:
        result1 += A % 10
        A = A // 10
    while B > 0:
        result2 += B % 10
        B = B // 10
    sum = result1 + result2
    new_list.append(sum)
print(min(new_list))

#Alternative 2 From the point that when the sum of the integers A and B is N, the minimum sum of the sums of the A and B is equal to the sum of the N.

#Get numbers as strings
num = input()

ans = 0
for i in range(len(num)):
    #The integer obtained as a character string can be extracted as follows, so you can continue to add it.
    ans += int(num[i])

if ans == 1:
    print(10)
else:
    print(ans)


B - Digits

Code written

#I want to convert an integer to N-ary

#To convert an integer N to K-ary, you can pick up the remainder of N divided by K in order from the back, so you can count how many times you can do that.
N, K = map(int, input().split())
list = []
count = 0
while N > 0:
    count += 1
    #Not related to the problem, but if you need to keep a record of the remainder, keep it in the list
    list.append(str(N % K))
    N = N // K
print(count)
#The following is when you want to display the conversion result to 2, 8 and hexadecimal numbers
sample = int(''.join(list))
if K == 2:
    print(bin(sample))
elif K == 8:
    print(oct(sample))
elif K == 16:
    print(hex(sample))


Current impression

From this point on, I feel that knowledge of mathematics and knowledge of Python libraries has become necessary. The first two questions are whether or not you notice that the index is divided. It is easier to understand because it is easier to come up with this idea if you do the multiplication table first.

The third and fourth questions are so-called combination problems, but it is difficult to replace them with code.

The third question is probably the type of problem that will be a barrier for those who are not good at math or for those who are weak in competitive programming like me. The point is to handle multidimensional arrays and how to do a full search. Especially in the latter case, if you normally do it with just range (), you will get an out of index error, so I had no idea how to prevent it. At first glance, neither responded, and after three laps, I felt a little hungry.

The fourth question was to develop further and make 3C2 from the given input and search for one that meets the conditions. A library called itertools makes brute force combinations from iterable, so I used this to ask questions. The key is to remember the conditions for forming a triangle. I couldn't do it at first glance because I didn't remember.

B --From Some Sums, problems with radix. Basically, when converting N to an X-ary number, you can pick up the remainder of dividing N by X until it becomes 0. Furthermore, in the case of Python, 2, 8, and hexadecimal numbers can be converted with built-in functions, so conversion can also be done using that.

reference

Reverse, reversed lists and strings in Python The nature of integers | About n-ary notation

Recommended Posts

Story of trying competitive programming 2
Story of trying competitive programming Part 1
The story of trying to reconnect the client
The story of trying deep3d and losing
Story of trying to use tensorboard with pytorch
The story of trying Sourcetrail × macOS × VS Code
[Note] Beginning of programming
I tried competitive programming
Recruitment of programming masters
Competitive programming diary python 20201213
The story of sys.path.append ()
Competitive programming diary python 20201220
Competitive programming with python
The story of making a Line Bot that tells us the schedule of competitive programming
Competitive programming diary python
A story of trying out pyenv, virtualenv and virtualenvwrapper
The story of building Zabbix 4.4
Linear programming + hands-on of pulp
[Apache] The story of prefork
Program-level story of libscips ① (α0.0.1)
Features of programming languages [Memo]
Python Competitive Programming Site Summary
Competitive programming is what (bonus)
The popularity of programming languages
Trying normal Linux programming Part 1
Technology that supports jupyter: traitlets (story of trying to decipher)
1st month of programming learning
Input / output method of values from standard input in competitive programming, etc.
Re: Competitive Programming Life Starting from Zero Chapter 1.2 "Python of Tears"
Python3 standard input for competitive programming
The story of Python and the story of NaN
Competitive programming, coding test template: Python3
The story of participating in AtCoder
[Python] [Table of Contents Links] Python Programming
[Memo] Small story of pandas, numpy
Understanding memo of collective intelligence programming
The story of remounting the application server
Story of power approximation by Python
Learning history of programming transcendence beginners
The story of writing a program
A story of a deep learning beginner trying to classify guitars on CNN
The story of trying to push SSH_AUTH_SOCK obsolete on screen with LD_PRELOAD