#
# Άσκηση: (προσδιορισμός της άσκησης με αναφορά στην ημερομηνία της διάλεξης όπου ανατέθηκε, ή με άλλη περιγραφή)
#
# Ονόματα φοιτητών: Λύση ενδεικτική από το διδάσκοντα
#
# Περιγράψτε στις επόμενες γραμμές σε ποια μεταβλητή (ή καλώντας ποια συνάρτηση)
# βρίσκει κανείς το αποτέλεσμα του προγράμματός σας.
# Αν πρόκειται για κάτι ποιο σύνθετο, περιγράψτε το επαρκώς.
#
# Η συνάρτηση που καλούμε φαίνεται στις 3 τελευταίες γραμμές
#
#
# Στείλτε το αρχείο αυτό στο email probapp@fourier.math.uoc.gr
# Ως αποστολέας θα πρέπει να φαίνεται το πλήρες σας όνομα και η αποστολή να είναι
# από το Πανεπιστημιακό σας email, αλλιώς δε θα γίνει δεκτό.
#
# Γράψτε το πρόγραμμά σας από δω και κάτω. Αν υπάρχουν συνοδευτικά αρχεία επισυνάψτε τα.
#
#


n = int(input("Δώστε το n: "))
k = n*(n-1)//2 # Πλήθος ακμών του πλήρους γραφήματος με n κορυφές


L = [] # Ποιες είναι οι κορυφές της υπ' αριθμόν i ακμής
for i in range(n):
    for j in range(i+1, n):
        L.append((i, j))


def prob_mono(i, j, k, C):     #i,j,k οι κορυφες του εκάστοτε τριγώνου σε αύξουσα σειρά
    """
    Επιστρέφει την πιθανότητα το τρίγωνο i, j, k να είναι
    μονοχρωματικό αν ισχύει ο μερικός χρωματισμός C
    """
    w1 = L.index((i,j))
    w2 = L.index((j,k))        #w1,w2,w3: οι ακμές του τριγώνου που δημιουργείται απο τα ζεύγη κορυφών
    w3 = L.index((i,k))
    p = -1                         # p: πιθανότητα να προκύψει μονοχρωματικό τρίγωνο.
    triangle = [C[w1],C[w2],C[w3]]     #triangle: περιέχει τους χρωματισμούς των ακμών του τριγώνου 
    for i in triangle:
        if triangle.count(0)==0:        # αν στο τρίγωνο όλες οι ακμές είναι χρωματισμένες
            if triangle.count(1)==3 or triangle.count(2)==3:   # αν ολες ειναι ιδιες,εχουμε πιθανότητα μονοχρωματικου τριγώνου 1
                p = 1
            else: 
                p = 0                   # αλλίως έχουμε πιθανότητα 0 
        elif triangle.count(0)==1:      #αν έχουμε μία ακμή χωρίς χρώμα
            if triangle.count(1)==2 or triangle.count(2)==2:    # αν έχουμε 2 ακμές με ίδιο χρώμα,έχουμε πιθ. 1/2.
                p = 1/2
            else:
                p = 0               #αλλιώς είναι ετερόχρωμες άρα έχουμε πιθανότητα 0.
        elif triangle.count(0)==2:    # αν έχουμε 1 χρωματισμένη ακμή,η πιθανότητα είναι 1/4
            p = 1/4
        else:
            p = 1/4             # αν δεν έχουμε καμία χρωματισμένη,τότε η πιθανότητα είναι 1/4
            break 
    return p

def mean_under_colors(C):
    """
    Υπολογίζει τη μέση τιμή του X υπό τη δέσμευση του μερικού
    χρωματισμού C
    """
    s = 0
    for i in range(n):      
        for j in range(i+1,n):
            for k in range(j+1,n):
                s += prob_mono(i, j, k, C)    
    return s

C = k*[0] # Στη λίστα C το 0 σημαίνει τυχαίο χρώμα, 1=κόκκινο, 2=μπλε
for i in range(k): # Για όλες τις ακμές i
        C1 = C[:] ; C1[i]=1 # O C1 είναι ο μερικός χρωματισμός που προκύπτει από τον C αν θέσουμε την i ακμή στο χρώμα 1
        C2 = C[:] ; C2[i]=2 # Ομοίως για τον C2
        value1 = mean_under_colors(C1) # Υπολογίζετε εδώ τη μέση τιμή υπό τον ένα και τον άλλο χρωματισμό
        value2 = mean_under_colors(C2)
        if value1 < value2:     # βρίσκουμε την μικρότερη μέση τιμή και κρατάμε τον χρωματισμό που προκύπτει απο αυτή.
            C = C1[:]
        else:
            C = C2[:]
    
# Τυπώστε πόσα μονοχρωματικά τρίγωνα έχει ο χρωματισμός που βρήκατε (και τον αριθμό 1/4 (n ανά 3) για σύγκριση)
mono = mean_under_colors(C) # εδώ C είναι πλήρως χρωματισμός και η μέση τιμή της ΤΜ είναι η τιμή της για το χρωματισμό αυτό
compare = n*(n-1)*(n-2)/24
print(f"Μέση τιμή πλήθους μονοχρωματικών τριγώνων: {compare}, τιμή που βρήκαμε {mono}")