AtCoder Beginners Contest 089[A to C]

Tasks

 

A. Grouping 2 … Simply print the result of the floor result

print(int(input())//3)

 

B. Hina Arare … As I use set(), I just need to add everything in this set. And print out the result to get the unique numbers of colors.

n = input()
s = set(input().split())

print("Four" if len(s) == 4 else "Three")

 

C. March … At the first sight, I thought I used regular expression to get the matching result. but soon realized it would be too slow in this case as N is a way big. Instead I use simple dictionary to store just the numbers of person whose name starts with any character in “MARCH”. With this, the cost would be N, and it should be completed within the necessary timeframe.

from itertools import combinations

n = int(input())
names = {"M":0, "A":0, "R":0, "C":0, "H":0}
# for each input, examine if it starts with specific character.
# No need to store the actual name as this problem doesn't require full name to output
for _ in range(n):
    name = input()
    if name[0] in names.keys():
        names[name[0]] += 1

patterns = list(combinations(names.keys(), 3))

count = 0
for pattern in patterns:
    count += names[pattern[0]] * names[pattern[1]] * names[pattern[2]]

print(count)

 

AtCoder Beginners Contest 088[A to C]

Tasks

 

A. Infinite Coins … Simple print modulus result

n = int(input())
a = int(input())

print("Yes" if n%500 <= a else "No")

 

B. Card Game For Two … As the questions says “When both players take the optimal strategy to maximize their scores”, it means both player takes the biggest card on their turn. Sort the card list in descending order, and use python list slice ([::2] the last 2 means every other cards) to create the resulting card list for both users.

n = int(input())
cards = sorted(list(map(int, input().split())), reverse=True)

if n > 1:
    print(sum(cards[::2])-sum(cards[1::2]))
else:
    print(cards[0])

 

C. Takahashi’s Information … As possible number of ai is not so big, I use bruteforce for possible a1, so the cost is 100x3x3. Once a1 value is fixed, the other number can be calculated. Compare the resulting list (from the assumption) and the original list.

def is_correct(grids):
    for a1 in range(min(101, grids[0][0]+1)):
        b_list = grids[0][0] - a1, grids[0][1] - a1, grids[0][2] - a1
        a2, a3 = grids[1][0] - b_list[0], grids[2][0] - b_list[0]
        a_list = [a1, a2, a3]
        temp_grids = []
        for an in a_list:
            row = []
            for bn in b_list:
                row.append(an+bn)
            temp_grids.append(row)
        if grids == temp_grids:
            return True

    return False


grids = []
for _ in range(3):
    grids.append(list(map(int, input().split())))

print("Yes" if is_correct(grids) else "No")

 

AtCoder Beginners Contest 087[A to C]

Tasks

 

A. Buying Sweets … Simple print modulus (=changes) result

x = int(input())
a = int(input())
b = int(input())

print((x-a)%b)

 

B. Coins … This takes N^3, and it’s much costly. And obviously there is a room for improvement.

a = int(input())
b = int(input())
c = int(input())
x = int(input())

count = 0
for i in range(a+1):
    for j in range(b+1):
        for k in range(c+1):
            if 500 * i + 100 * j + 50 * k == x:
                count += 1

print(count)

 

C. Candies … Iterate index one by one, so the cost is N.

n = int(input())
rows = []
for i in range(2):
    rows.append(list(map(int, input().split())))
 
max_candies = 0
for j in range(n):
    if sum(rows[0][:j+1]) + sum(rows[1][j:]) > max_candies:
        max_candies = sum(rows[0][:j+1]) + sum(rows[1][j:])
 
print(max_candies)

 

AtCoder Beginners Contest 086[A to C]

Tasks

 

A. Product … Simple if else based on modulus

a, b = list(map(int, input().split()))

print("Even" if a*b%2==0 else "Odd")

 

B. 1 21 … Inputs can be concatenated as they are strings, and cast the result and make them integer. math.sqrt function make the integer into float. compare resulting float and integer.

from math import sqrt

a, b = input().split()
x = sqrt(int(a + b))
print("Yes" if x == int(x) else "No")

 

C. Traveling … First I tried to brute force all the path, but it will end up 4^N and it cannot be completed in time. With the below code, the cost is only N.

def can_Travel(visits):
    current_loc = (0, 0)
    current_time = 0
    for visit in visits:
        next_loc = (visit[1], visit[2])
        distance =  abs(next_loc[0] - current_loc[0]) + abs(next_loc[1] - current_loc[1])
        
        # distance is further than it can be reached
        if distance > visit[0] - current_time:
            return False
        # the distance is within the achievable range, but it cannot be done as we cannot stop
        elif (visit[0] - current_time - distance)%2 != 0:
            return False

    return True


n = int(input())
visits = []
for _ in range(n):
    visits.append(list(map(int, input().split())))

print("Yes" if can_Travel(visits) else "No")

 

AtCoder Beginners Contest 085[A to C]

Tasks

 

A. Already 2018 … String concatenation and slicing

print('2018'+input()[4:])

 

B. Kagami Mochi … I used set. As all values added into the set is unique(duplicated values will be ignored), I just need to output the numbers of the set once all input is completed.

s = set()
for _ in range(int(input())):
    s.add(input())

print(len(s))

 

C. Otoshidama … I used simple two for loops to iterate the numbers of 10,000 notes and 5,000 notes. Hence the cost is N^2.

def otoshidama(nos, amt):

    for x in range(0, amt//10000+1):
        for y in range(0, (amt-(10000*x))//5000+1):
            if 10000*x + 5000*y + 1000*(nos-x-y) == amt:
                return (x, y, nos-x-y)

    return (-1, -1, -1)

n, y = list(map(int,input().split()))

print(*otoshidama(n, y))

 

AtCoder Beginners Contest 084[A to C]

Tasks

 

A. New Year … Basic calculation only

print(-int(input())+48)

 

B. Postal Code … I used string method .split(‘-‘) to split the given string into two part, and method .isdecimal() to check if respective part is composed of only 0-9.

a, b = list(map(int, input().split()))
s = input()

sl = s.split('-')
if len(sl) != 2:
    print('No')
elif ( sl[0].isdecimal() and len(sl[0]) == a ) and ( sl[1].isdecimal() and len(sl[1]) == b):
   print('Yes')
else:
    print('No')

 

C. Special Trains … I created class for stations to store each parameters. It costs N^2 as there are two for loops, but N is only up to 500 and should not be a problem.

class station:
    def __init__(self, speed, first, interval):
        self.speed = speed
        self.first = first
        self.interval = interval


def onboard_duration(station, start_time, first=False):
    # return the arrival_time at the next_station
    if first or start_time < station.first: # starting station or the first train is not departed from the station
        return station.first + station.speed
    elif start_time % station.interval == 0:
        return start_time + station.speed
    else:
        return start_time + station.interval - (start_time % station.interval) + station.speed


stations = []
for _ in range(int(input())-1):
    stations.append(station(*list(map(int, input().split()))))

for i in range(len(stations)):
    elapsed_time = 0
    for j in range(i, len(stations)):
        if elapsed_time == 0:
            elapsed_time = onboard_duration(stations[j], elapsed_time, first=True)
        else:
            elapsed_time = onboard_duration(stations[j], elapsed_time)
    print(elapsed_time)

print('0')

 

AtCoder Beginners Contest 082 [A to C]

Tasks

 

A. Round Up The Mean … Round up using math.ceil

from math import ceil
print(ceil(sum(list(map(int, input().split())))/2))

 

B. Two Anagrams … make the ascending ordered string from s, and make the descending ordered string from t. Compare both of them. The for loop needs to have three conditions as first condition checks if s-string is shorter than t-string, the second condition checks if t-string is shorter than s-string OR the pointing character in t-string is bigger than the same index character in s-string. We cannot include s_chr < t_chr in the first condition as it will cause Error “None cannot be compared with int” if t-string is shorter than s-string.

from itertools import zip_longest

def twoAnagrams(s, t):
    s_str = ''.join(sorted(s))
    t_str = ''.join(sorted(t, reverse=True))

    if t_str.startswith(s_str):
        if len(s_str) < len(t_str):
            return True
        # this implies s and t is the same string
        else:
            return False

    # zip_longest returns None if one list is shorter than the other
    for s_chr,t_chr in zip_longest(s_str, t_str):
        if s_chr is None:
            return True
        elif t_chr is None or t_chr < s_chr:
            return False
        elif s_chr < t_chr:
            return True


s = list(input())
t = list(input())

print('Yes' if twoAnagrams(s,t) else 'No')

 

C. Good Sequence … I used collections.Counter function again. It makes this tasks very easy. Once dictionary is populated, I just need to go through all the keys and compare the key and value.

from collections import Counter

n = int(input())
a = list(map(int, input().split()))

c = Counter(a)

result = 0
for num in c.keys():
    if num < c[num]:
        result += c[num] - num
    elif num > c[num]:  # numbers of appearance is less than the number. needs to delete all
        result += c[num]

print(result)

 

AtCoder Beginners Contest 083[A to C]

Tasks

 

A. Libra … Basic if…else structure

a,b,c,d = list(map(int, input().split()))

if a+b > c+d:
    print('Left')
elif a+b == c+d:
    print('Balanced')
else:
    print('Right')

 

B. Some Sums … I used brute force as the expected N is up to 10^4. So I just iterate all the numbers from 1 to N.

a,b,c,d = list(map(int, input().split()))

if a+b > c+d:
    print('Left')
elif a+b == c+d:
    print('Balanced')
else:
    print('Right')

 

C. Multiple Gift … I used kind of brute force here as well. Multiply current number by 2, 3, 4… and check if modulus is 0 each time.

x, y = list(map(int, input().split()))

count = 1
curr_num, next_num = x, x*2
multiplier = 2
while next_num <= y:
    if next_num%curr_num == 0:
        count += 1
        multiplier = 2
        curr_num = next_num
    else:
        multiplier += 1
    next_num = curr_num * multiplier

print(count)

 

AtCoder Beginners Contest 081 [A to C]

Tasks

 

A. Placing Marbles … Count “1” in the input string

print(input().count("1"))

 

B. Shift Only … Add the result into the temporary list if the number modulo 2 is 0. In each iteration of the list, compare the length of the original list and temporary list.

n = int(input())
a = list(map(int, input().split()))

result = 0

while True:
    temp_a = []
    for num in a:
        if num%2 == 0:
            temp_a.append(num//2)
    if len(temp_a) != n:
        break
    a = temp_a
    result += 1

print(result)

 

C. Not So Diverse … In python, there is a Counter function which can create a dictionary from a list. In this case, take a list of numbers, and make a dictionary which has “number” as a key, and “times of the number appears in the list” as a value.

n = int(input())
a = list(map(int, input().split()))

result = 0

while True:
    temp_a = []
    for num in a:
        if num%2 == 0:
            temp_a.append(num//2)
    if len(temp_a) != n:
        break
    a = temp_a
    result += 1

print(result)

 

AtCoder Beginners Contest 080 [A to C]

Tasks

 

A. Parking … Simple comparison with if

n, a, b = list(map(int, input().split()))

print(a*n if b > a*n else b)

 

B. Harshard Number … Given one number, and judge if the number is Harshard Number. use modulus.

x = input()

fx = sum([int(num) for num in x])

print("Yes" if int(x)%fx == 0 else "No")

 

C. Shopping Street … Given one number, and two lists. And calculate the highest profit we can earn.

n = int(input())
f = []
for _ in range(n):
    f.append(list(map(int, input().split())))
p = []
for _ in range(n):
    p.append(list(map(int, input().split())))

result = -float("inf")

# opening schedule for my shop.
# start from 1(only open Mon.AM) to 1023(open all day)
for b in range(1, 1<<10):

    profit = 0
    # compare with other shops
    for i in range(n):

        common_opening = 0
        # compare time
        for j in range(10):

            if 1&(b>>j) and f[i][j] == 1:

                common_opening += 1
        profit += p[i][common_opening]

    result = max(result, profit)

print(result)