class MatriuDispersa:

    def __init__(self, nfiles=0, ncolumnes=0):
        self.nfils = nfiles
        self.ncols = ncolumnes
        self.vals = {}

    def __getitem__(self, pos):
        if 1 <= pos[0] <= self.nfils and 1 <= pos[1] <= self.ncols:
            return self.vals.get(pos, 0.0)
        else:
            raise IndexError

    def __setitem__(self, pos, valor):
        if 1 <= pos[0] <= self.nfils and 1 <= pos[1] <= self.ncols:
            if valor == 0:
                if pos in self.vals:
                    del self.vals[pos]
            else:
                self.vals[pos] = valor
        else:
            raise IndexError

    def __len__(self):
        return len(self.vals)

    def __str__(self):
        ls = []
        for f in range(1, self.nfils+1):
            lss = []
            for c in range(1, self.ncols+1):
                lss.append('%.1f' % self[f,c])
            ls.append(' '.join(lss))
        return '\n'.join(ls)

    def __add__(self, other):
        if self.nfils == other.nfils and self.ncols == other.ncols:
            suma = MatriuDispersa(self.nfils, self.ncols)
            for f in range(1, self.nfils+1):
                for c in range(1, self.ncols+1):
                    suma[f,c] = self[f,c] + other[f,c]
        else:
            suma = MatriuDispersa()
        return suma
        
    def __mul__(self, other):
        if self.ncols == other.nfils:
            mult = MatriuDispersa(self.nfils, other.ncols)
            for i in range(1, mult.nfils+1):
                for j in range(1, mult.ncols+1):
                    aux = 0.0
                    for k in range(1, self.ncols+1):
                        aux = aux + self[i,k] * other[k,j]
                    mult[i,j] = aux
        else:
            mult = MatriuDispersa()
        return mult

    def __rmul__(self, k):
        nova = MatriuDispersa(self.nfils, self.ncols)
        for i in range(1, self.nfils+1):
            for j in range(1, self.ncols+1):
                nova[i,j] = self[i,j] * k
        return nova
        
        # Implementació alternativa, tenint en compte la representació com un diccionari: 

        # nova = MatriuDispersa(self.nfils, self.ncols)
        # for pos in self.vals:
        #     nova.vals[pos] = self.vals[pos] * k
        # return nova


def identitat(dim):
    ident = MatriuDispersa(dim, dim)
    for i in range(1, dim+1):
        ident[i, i] = 1.0
    return ident