Solve with Python [100 selected past questions that beginners and intermediates should solve] (001 --004 All search: All enumeration)

1. Purpose

Solve 100 past questions that beginners and intermediates should solve in Python. The goal is to turn light blue by the time you finish solving everything.

This article is "001 --004 All Search: All Enumeration".

2. Summary

In Python, you can enumerate combinations with itertools, but I wrote it in a for statement for practice. I didn't stumble in particular.

3. Main story

001 --004 All search: All enumeration

  1. ITP1_7_B - How Many Ways? image.png

Answer

answer_list = []
while True:
    n, x = map(int, input().split())
    if n == 0 and x == 0:
        break

    count = 0
    for first in range(1, n + 1):
        for second in range(first + 1, n + 1):
            for third in range(second + 1, n + 1):
                if first + second + third == x:
                    count += 1

    answer_list.append(count)

for answer in answer_list:
    print(answer)

Since the problem statement says that there is no duplication, be careful not to duplicate the range of `first```,` `second, and thirdof the for statement. Specifically, set the start of secondto first + 1``` and the start of `` third to` `second + 1.


  1. AtCoder Beginner Contest 106 B - 105 image.png

Answer

def is_target(num):
    count = 0
    for i in range(1, num+1):
        if num % i == 0:
            count += 1
    if count == 8:
        return True
    else:
        return False

if __name__ == "__main__":
    N = int(input())
    count = 0
    for num in range(1, N+1, 2):
        count += is_target(num)

    print(count)

Create a function called `is_target``` that returns True``` and `` Falseto see if the divisor is 8. After that, check the odd numbers from 1 to N withis_target``` and add them together (True is 1 so you can add them as they are).


  1. AtCoder Beginner Contest 122 B - ATCoder image.png

Answer

target = 'ACGT'
S = input()

answer = 0
for start in range(len(S)):
    if S[start] not in target:
        continue
    count = 0
    for end in range(start, len(S)):
        if S[end] not in target:
            break
        count += 1
    
    answer = max(answer, count)

print(answer)

The substring to be extracted from the string S can be written as `S [start: end] ``` using the subscripts start``` and ```end```, so `` start For each of `` andend, check whether it is ACGT```.

When checking, the for statement of `start``` is continue``` if it is not ```ACGT```, and the for statement of ```end``` is ```ACGT Note that if it is not `` , it is` `` break```.


004. Pakencamp 2019 C-Karaoke

image.png

Answer

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

answer = 0
for song1 in range(M):
    for song2 in range(song1+1, M):
        score = 0
        for i in range(N):
            score += max(A[i][song1], A[i][song2])

        answer = max(answer, score)

print(answer)

song1Whensong2Turn the for statement about. Then, inside that, for each student (subscript i), the larger score of `` `song1and song2``` is adopted.

Recommended Posts

Solve with Python [100 selected past questions that beginners and intermediates should solve] (001 --004 All search: All enumeration)
Solve with Python [100 selected past questions that beginners and intermediates should solve] (024 --027 Depth-first search)
Solve with Python [100 selected past questions that beginners and intermediates should solve] (015 --017 Full search: Permutation full search)
Solve with Python [100 selected past questions that beginners and intermediates should solve] (010 --014 Full search: Bit full search)
Solve with Python [100 past questions that beginners and intermediates should solve] (028 --033 breadth-first search)
Solve with Python [100 selected past questions that beginners and intermediates should solve] (005 --- 009 All search: All enumeration to reduce the number of streets by devising)
Solve with Python [100 past questions that beginners and intermediates should solve] (053 --055 Dynamic programming: Others)
Solve with Python [100 selected past questions that beginners and intermediates should solve] (056 --059 Shortest path problem: Dijkstra's algorithm)
[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]
Solve with Python [100 selections of past questions that beginners and intermediates should solve] (034-038 Dynamic programming: Knapsack DP basic)
Solve with Python [100 selections of past questions that beginners and intermediates should solve] (039 --045 Dynamic programming: Knapsack DP variant)
Causal reasoning and causal search with Python (for beginners)
1st Algorithm Practical Test Solve past questions with python
2nd Algorithm Practical Test Solve past questions with python (unfinished)
Let's make an app that can search similar images with Python and Flask Part2
[For beginners in competition professionals] I tried to solve 40 AOJ "ITP I" questions with python
Solve simultaneous ordinary differential equations with Python and SymPy.
Crawling with Python and Twitter API 1-Simple search function