• Revista PROGRAMAR: Já está disponível a edição #53 da revista programar. Faz já o download aqui!

BlodyGrl

[Problema] Alunos de sociologia

18 mensagens neste tópico

Os alunos da cadeira de Sociologia decidiram fazer entre eles uma experiência. Combinaram que cada um inventaria uma história sobre si próprio, a contaria aos colegas com que se relaciona melhor, e lhes contaria também todas as histórias que lhe fossem contadas. Com base nesta experiência convencionaram considerar que o grupo de uma pessoa seria o conjunto de pessoas, incluindo a própria, cuja história ficou a conhecer e que ficaram a conhecer a sua. Sabiam que, nessas condições, o grupo de uma pessoa é necessariamente o grupo de cada uma das pessoas do seu grupo. Pretendiam determinar o número de grupos com quatro ou mais pessoas e o número de pessoas fora desses grupos. Quando estavam prestes a iniciar a experiência, alguns alunos sugeriram a sua substituição por uma simulação, em computador, para vários cenários hipotéticos.

Input

Na primeira linha é dado o número de cenários a considerar. Seguem-se as descrições dos cenários. A primeira linha de cada cenário contém o número de alunos (=> 4). A seguir aparece uma linha por aluno: o primeiro número nessa linha identifica o aluno e o seguinte é o número de alunos com que se considera relacionar melhor. Os restantes números nessa linha identificam esses alunos, podendo não haver nenhum. São usados inteiros consecutivos, a partir de 1, para numerar as pessoas.

Output

Para cada cenário, terá uma linha com identificação desse caso e, na linha seguinte, dois inteiros separados por um espaço. O primeiro é o número de grupos com quatro pessoas ou mais. O segundo é o número de pessoas fora desses grupos. Qualquer um dos dois números pode ser 0.

Exemplo

Input

4

4

1 3 2 4 3

4 0

2 2 1 3

3 2 2 1

6

1 2 3 5

2 2 3 4

4 1 2

3 2 2 1

6 1 5

5 2 6 1

8

1 4 6 2 4 5

3 1 2

2 2 3 4

4 1 5

6 0

5 3 4 8 7

7 1 5

8 2 5 3

10

1 4 6 2 4 5

3 2 2 1

9 0

2 2 3 4

4 2 5 9

6 1 1

5 3 4 8 7

7 1 5

8 1 5

10 1 9

Output

Caso #1

0 4

Caso #2

1 0

Caso #3

1 2

Caso #4

2 2

Eu tenho muito mais dificuldade neste e como não queria que fossem vocês a resolve-lo (porque eu não consigo mesmo) não o queria pôr aqui mas pode ser que com a vossa ajuda eu comece a raciocinar e consiga fazer o programa por isso aqui fica ele. Quanto ao que eu já fiz é mesmo nada porque até no input tenho dificuldade porque não consigo pôr algo do género:

input=nº qualquer, len, lista de nºs com o len anterior, isto na mesma linha. Será que vocês podem começar por me ajudar aqui? (Dando dicas e não diznedo como. :P)

Agradecida. :D

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Como disse no outro tópico, gostei do problema, mas não é dificil. Já desenhaste os grafos dos exemplos de input? Deve dar para observares qualquer coisa (como é que se determina o tamanho de um grupo e quantos grupos existem).

Já vi na página da tua cadeira que já deram o que é preciso para o problema. Não estou a ver mais dicas a dar sem ser a solução propriamente dita...

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Movido para algoritmia, já que a dúvida é sobre o raciocínio e não código.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Sim, sou da FCUP. *.* Não, não resolvi. Estou a tentar o outro mas como não encontro algoritmos de Tarjan bons ando com alguns probelmas mas quanto a este também já pensei em usar a pesquisa em largura, só não sei é se vai ter pequenos problemas... Pronto, vou tentar postar o outro e fazer o mesmo que fiz a este.

Afinal sabes resolver o problema... mas o que queres dizer com "não encontro algoritmos de Tarjan bons" ? Eu costumo usar outro algoritmo que acho que é mais fácil de entender e tem a mesma eficiência. Tens a descrição aqui: http://paginas.fe.up.pt/~jpf/teach/CPAL0708/grafos4.pdf

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Porque já estive aq procurar o código na net mas não dá o resultado que deve dar. Não sei se tem algum erro ou assim mas os meus colegas dizem que devia dar outra coisa. Pois tem razão... Eu devia ter dado a matéria mas eu trabalho. Não posso ir às aulas. Além disso elas estão todas em inglês. :P

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Eu não te posso ajudar na programação porque não sei programar em python, mas eu confirmei o resultado dos 3 primeiros inputs (à mão no papel :x) hoje de manhã para conferir se a minha ideia dava.

Já falei com outro amigo de CC (o outro que referi é de Redes), e os profs andam com muita fixação no MIT. O livro deles "Introduction to algorithms" muitas vezes é dificil de seguir, mesmo em temas que eu já sabia (e eles aprofundam mais). Mas isso do inglês... na nossa área temos de dominar pelo menos a leitura :\

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Mas alguém me ajuda com aquela dúvida do Input? Já que não dá com dicas podiam p^ro este bocadinho de codigo. *.* Não queria fazer batotice mas ninguém aqui está a resolver isso. :P

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

def sociologia():
        cenarios=input()
        amigos={}
        for cenario in range(cenarios):
                alunos=input()
                for aluno in range(alunos):
                        entrada=raw_input()
                        entrada2=[int(x) for x in entrada.split()]
                        if entrada2[1]!=(len(entrada2[:1])):
                                amigos[entrada2[0]]=[entrada2[1:]]
                return amigos
sociologia()

Alguém me diz o erro disto por favor? :P

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Eu andei a ver um pouco na net e consegui fazer um programa que lê o input :x

Nota que é o meu primeiro programa em python... é muito provável que possa ser feito de forma mais simples :D

def readint(): return int(raw_input())
def readarray(foo): return map(foo, raw_input().split())

def program():
   
   ntests = readint()
   for t in range(ntests):
       n = readint()
       grafo = []
       for i in range(n):   # nao sei outra forma de inicializar o grafo com N listas vazias 
           grafo.append([])
       for i in range(n):
           linha = readarray(int)
           v = linha[0]-1   # indices de 0.. n-1
           nadj = linha[1]
           for j in range(nadj):                
               grafo[v].append( linha[j+2]-1 ) # indices de 0.. n-1
       
       for i in range(n):
           s = str(i) + ": "
           for j in grafo[i]:
               s = s + str(j) + " "
           print s
           
       
program()

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Como é que se acede aos valores de uma chave de um dicionário? Há algum comando específico? Estou farta de procurar mas acho que o meu mal é não saber procurar. :vergonha:

Tipo:

def prog():
    dic={1: [3, 2], 2: [1, 3], 3: [1]}
    lista=[]
    lista2=[]
    if lista==[]:
        lista+=dic.keys[0]
    else:
        

agora kria pôr a lista2=[3,2]

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Err BlodyGrl, aceder ao valor de uma chave num dict é a coisa mais básica em Python...

x = {1: [3,2], 0: [1,2], 3: [0,0]}
print x[1]

Mostra [3,2]. Se iterares um dict (ou seja, for i in x no exemplo anterior), o i vai ser a chave.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Sim mas eu pensei que fosse mais complicado porque eu testei mas pronto tava-me a dar marado... xD

Bem, isto está estranho porque estava a fazer um prog que se lhe desse

dic={1: [2, 3], 2: [1, 3], 3: [1]}

me desse [1,3] porque  o 1º elemento da 1ª chave (1) é 3.... E depois me passe para a chave 3 (porque foi o ultimo elemento k deste a lista) e n me de nada (nao da nada porque eu queria o que tivesse na chave 3 mas como o 1 ja la esta... se fosse 2 juntava o 2 à lista e saltava para a chave 2 e dava-me o 1º elemento que ja nao tivesse na lista) sempre assim...

Aqui está o meu estranho teste.  :cheesygrin: :dontgetit:

def prog():
    dic={1: [2, 3], 2: [1, 3], 3: [1]}
    chaves=dic.keys()
    lista=[]
    lista2=[]
    for i in range(len(dic)):
        if lista==[]:
            lista+=[chaves[i]]
        else:
            lista2+=[dic[chaves[lista[-1]]][i]]
            if dic.has_key(lista2[-1]):
                lista+=[lista2[-1]]
            return lista

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Hehe! Consegui... Quer dizer quase. xD Falta-me por o output no fim (porque ele está a dar no meio do input xD).

Se quiserem posso pôr aqui o programa.  :D Mas como há mais gente a fazer, não sei se devo. :cheesygrin:

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

A decisão é tua, eu não tenho nada contra, mas se fosse a ti só postava depois do prazo de entrega acabar :cheesygrin:

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Aleluia! Consegui!  :D Nem me acredito que andei 3 dias à volta de um programa CERTO (99%) quando a única coisa que fazia para ele trabalhar a 100% era fazer uma identação...  :wallbash:

Bem, daqui a uma horinhas já está posto. Agora vou voltar ao outro programa mas assim até é tarde é difícil.  :(

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Tão e que tal correu?

Deixo aqui como resolvi o problema. Se alguém quiser criticar o código, agradeço :P

def readint(): return int(raw_input())
def readarray(tipo): return map(tipo, raw_input().split())

def debug(grafo, n):
    for i in range(n):
        s = str(i) + ": "
        for j in grafo[i]:
            s = s + str(j) + " "
        print s

def dfs( grafo , visited , ordem , v ):
    visited[v] = 1
    for u in grafo[v]:
        if visited[u] == 0 :
            dfs( grafo , visited , ordem , u )    
    ordem.append(v)    

def dfst( grafoT , visited , v , componente ):
    visited[v] = 1
    componente.append(v)
    for i in grafoT[v]:
        if visited[i] == 0 :
            dfst( grafoT , visited , i , componente)
    
def scc( n , grafo, grafoT ):
    visited = []
    ordem = []
    for i in range(n):
        visited.append(0)
    for i in range(n):
        if visited[i] == 0 :
            dfs( grafo , visited , ordem , i )
    
    componentes = []
    for i in range(n):
        visited[i] = 0
    ordem.reverse()
    for i in range(n):
        if visited[ ordem[i] ] == 0 :
            c = []
            dfst( grafoT , visited , ordem[i] , c )
            componentes.append( c )
    return componentes

def program():    
    ntests = readint()
    for t in range(ntests):
        n = readint()
        grafo = []
        grafoT = []
        for i in range(n):      # nao sei outra forma de inicializar o grafo com N listas vazias 
            grafo.append( [] )  # grafo representado em lista de adjancencias
            grafoT.append( [] ) # grafo com arestas invertidas
            
        for i in range(n):
            linha = readarray(int)
            v = linha[0]-1                      # indices de 0.. n-1
            for j in range(linha[1]):
                u = linha[j+2]-1
                grafo[v].append( u )            # indices de 0.. n-1
                grafoT[u].append( v );
        
        #debug(grafo,n)
        
        comp = scc(n , grafo, grafoT)
        
        ngrupos = 0
        fora = 0
        for c in comp:
            if len(c) >= 4 :    ngrupos+= 1
            else:               fora += len(c)
        
        print "Caso #%d\n%d %d" % (t+1, ngrupos , fora)
        
program()

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Pois, ao início eu ia fazer assim mas cheguei à conclusão que sou um pouco burra demais para isso. xD

Aqui fica o meu. :)

#O input é muito fácil de perceber. 
def entradas():
    cenarios=input()
    listac1=[]
    listac2=[]
    for cenario in range(cenarios):
        alunos=input()
        amigos = {}
        c1=0
        c2=0
        lista=[]
        for aluno in range(alunos):
            entrada=raw_input()
            entrada2=[int(x) for x in entrada.split()]
            if entrada2[1]==(len(entrada2[1:])-1):
                amigos[entrada2[0]]=entrada2[2:]
            else:
                return
        tarjan(amigos)     #Com a ajuda de pseudo-código e de uma amigo. 
        for i in range(len(tarjan(amigos))):
            if len(tarjan(amigos)[i])>=4:
                c1+=1
            else:
                c2+=len(tarjan(amigos)[i])
        listac1+=[c1]
        listac2+=[c2]
        c1=0
        c2=0
    for i in range(cenarios):
        print "Caso #"+str(i+1)
        print listac1[i],listac2[i]
        
def tarjan(amigos):
    dic={}
    lista=[]
    ciclos=[]
    def visit(amigo):
        if amigo in dic: return
        n=len(dic)
        dic[amigo]=n
        quant_amigos=len(lista)
        lista.append(amigo)
        for outro_amigo in amigos[amigo]:
            visit(outro_amigo)
            dic[amigo]=min(dic[amigo],dic[outro_amigo])
        if n==dic[amigo]:
            ciclo=lista[quant_amigos:]
            del lista[quant_amigos:]
            ciclos.append(ciclo)
            for i in ciclo:
                dic[i]=len(amigos)
    for amigo in amigos:
        visit(amigo)
    return ciclos

entradas()

Acho que o programa é bem simples de perceber se perceberem o Tarjan (o que acho que percebem, quem não perceber que diga.  :))

E correu muito bem xD (quer dizer, mais ou menos porque me estava a esquecer de limpar os dicionários depois do 1º for mas de resto foi MUITO simples fazê-lo. :))

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Crie uma conta ou ligue-se para comentar

Só membros podem comentar

Criar nova conta

Registe para ter uma conta na nossa comunidade. É fácil!


Registar nova conta

Entra

Já tem conta? Inicie sessão aqui.


Entrar Agora