# cache simulator
#  P Chongstitvatana    28 March 2022

def readtrace():
    fin = open("trx.txt","r")
    fo = open("tout.txt","w")
    trace = []
    for i in range(1,1000):
        for j in range(1,10):
            [ads,mode] = fin.readline().split()
        a = int(ads)
        if( a < 400000):      # data
            a = a // 100
        else:                   # instruction
            a = a - 400000
            a = (a // 10) + 5000
        fo.write(str(a))
        fo.write("\n")
    fin.close()
    fo.close()
    
#readtrace()
#print(10//3,10 % 3)

csize = 2000
# linesize 1 word
def direct():

    hit = 0
    total = 0
    empty = [0]*csize
    tag = [0]*csize
    
    fin = open("trx.txt","r")
    for i in range(1,100000):
        [ads,mode] = fin.readline().split()
        total += 1
        a = int(ads)
        idx = a % csize
        ta = a // csize
        if( empty[idx] == 0 ):
            empty[idx] = 1
            tag[idx] = ta
        else:
            if( tag[idx] == ta):
                hit += 1
            else:
                tag[idx] = ta    # write to this slot
                
    fin.close()
    print("total ",total," hit ",hit," hit rate ",hit/total)
    
    
# linesize 1 word
def twoway():

    csize2 = csize // 2
    hit = 0
    total = 0
    empty1 = [0]*csize2
    tag1 = [0]*csize2
    empty2 = [0]*csize2
    tag2 = [0]*csize2
    
    fin = open("trx.txt","r")
    for i in range(1,100000):
        [ads,mode] = fin.readline().split()
        total += 1
        a = int(ads)
        idx = a % csize2
        ta = a // csize2
        if( empty1[idx] == 1 and tag1[idx] == ta):
            hit += 1
            continue
        if( empty2[idx] == 1 and tag2[idx] == ta):
            hit += 1
            continue
        if( empty1[idx] == 0):
            empty1[idx] = 1
            tag1[idx] = ta
            continue
        if( empty2[idx] == 0):
            empty2[idx] = 1
            tag2[idx] = ta
            continue
        if (total % 2 == 0):    # even
            empty1[idx] = 1
            tag1[idx] = ta      # store at way1
        else:
            empty2[idx] = 1
            tag2[idx] = ta      # store at way2
        
            
    fin.close()
    print("total ",total," hit ",hit," hit rate ",hit/total)
    
direct()
twoway()