Hello! Welcome to my blog about programming!

Graph Theory

DFS

The most useful graph algorithms are search algorithms. DFS (Depth First Search) is one of them.

While running DFS, we assign colors to the vertices (initially orange). Algorithm itself is really simple :

dfs (v):
        color[v] = gray
        for u in adj[v]:
                if color[u] == orange
                        then dfs(u)
        color[v] = dark_blue

Time complexity : O(n + m).

Hanoi Towers

Link to the problem
Link to ideone.com

def move(n, start, finish, temp):
    global count
    if n > 0:
        move(n - 1, start, temp, finish)
        print(n, start, finish)
        count += 1
        move(n - 1, temp, finish, start)
        
count = 0
n = int(input())
move(n, 1, 3, 2)
print(count)

In
3

Out
1 1 3
2 1 2
1 3 2
3 1 3
1 2 1
2 2 3
1 1 3
7

TechnoCup. First Round, C

Link to the problem

import sys

n = int(input())
c1 = 3 
c2 = 4
L = [0]*n

sys.stdout.write('? 1 2\n')
sys.stdout.flush()
sum12 = int(input())

sys.stdout.write('? 2 3\n')
sys.stdout.flush()
sum23 = int(input())

sys.stdout.write('? 1 3\n')
sys.stdout.flush()
sum13 = int(input())

L[0] = (sum13 + sum12 - sum23) // 2
L[1] = sum12 - L[0]
L[2] = sum13 - L[0]

if n == 3:
    print('!', *L)
else:
    n1 = 3
    while n1 < n:
        b = '? ' + str(c1) + ' ' + str(c2) + '\n'
        sys.stdout.write(b)
        sys.stdout.flush()
        sum34 = int(input())        
        L[n1] = sum34 - L[n1 - 1]
        n1 += 1
        c1 += 1
        c2 += 1
if n > 3:
    print('!', *L)

№ 3766. Bank System

Link

input = open('input.txt', 'r')
output = open('output.txt', 'w')

L = list(map(str, input.read().split('\n')))  
Accounts = dict()

for i in L:
    if i != '':
        st = list(i.split( ))    
        if st[0] == 'DEPOSIT':
            Accounts[st[1]] = Accounts.get(st[1], 0) + int(st[2])  
        
        elif st[0] == 'INCOME':
            for j in Accounts:
                if Accounts[j] > 0:
                    Accounts[j] = int(Accounts[j] * ((100 + int(st[1])) / 100) // 1)   
                
        elif st[0] == 'BALANCE':
            if st[1] in Accounts:
                output.write(str(int(Accounts[st[1]])) + '\n')
            else:
                output.write('ERROR\n')   
            
        elif st[0] == 'TRANSFER':
            Accounts[st[1]] = Accounts.get(st[1], 0) - int(st[3])
            Accounts[st[2]] = Accounts.get(st[2], 0) + int(st[3])      
            
        elif st[0] == 'WITHDRAW':
            Accounts[st[1]] = Accounts.get(st[1], 0) - int(st[2]) 
        
input.close()
output.close()