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

import numpy as np

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


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


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


C = k*[0] # Στη λίστα C το 0 σημαίνει τυχαίο χρώμα, 1=κόκκινο, 2=μπλε
for i in range(k): # Για όλες τις ακμές i
        (u, v) = L[i] # u,v είναι οι κορυφές της ακμής Νο i
        diff = 0 # σε αυτή τη μεταβλητή θα υπολογίσουμε τη διαφορά της μέσης τιμής
                 # αν χρωματίσουμε την i ακμή κόκκινη (1) από να τη χρωματίσουμε μπλε (2).
                 # Δίνουμε στην i ακμή το χρώμα 1 αν diff < 0 αλλιώς το χρώμα 2.
        for w in range(n):
            if w==u or w==v:
                continue # θέλουμε το w να είναι οποιαδήποτε άλλη κορυφή από τις u, v
#                uk = ndx[u][w] # Αριθμός της ακμής u--w
#                vk = ndx[v][w] # Αριθμός της ακμής v--w
            [uu, vv, ww] = sorted([u, v, w]) # Η prob_mono θέλει τις κορυφές σε αύξουσα σειρά
            C[i] = 1
            diff += prob_mono(uu, vv, ww, C)
            C[i] = 2
            diff -= prob_mono(uu, vv, ww, C)
        if diff < 0:
            C[i] = 1
        else:
            C[i] = 2

# Τυπώστε πόσα μονοχρωματικά τρίγωνα έχει ο χρωματισμός που βρήκατε (και τον αριθμό 1/4 (n ανά 3) για σύγκριση)
mono = 0 # εδώ υπολογίζουμε πόσα μονοχρωματικά τρίγωνα έχουμε
for i in range(n):
    for j in range(i+1, n):
        for k in range(j+1, n):
            eij = ndx[i][j] # eij, ejk, eik είναι οι αριθμοί των ακμών του τριγώνου
            ejk = ndx[j][k]
            eik = ndx[i][k]
            if C[eij]==C[eik] and C[eik]==C[ejk]: # αν όλα τα χρώματα ίδια τότε αυξάνουμε το μετρητή
                mono += 1
            
compare = n*(n-1)*(n-2)/24
print(f"Μέση τιμή πλήθους μονοχρωματικών τριγώνων: {compare}, τιμή που βρήκαμε {mono}")