Primo Progetto ASD 2014/15

Batman si annoia

Primo Progetto ASD 2014/15Batman si annoia

Batman

Giustiziere mascherato

La notte combatte ilcrimine

Il giorno insegna algoritmi

Notte tipo

I Esce dalla batcaverna (nodo 7)

I Attraversa la mappa della citta (grafo orientato)

I Torna nella sua casetta (nodo 5)

Nemici

Batman ha numerosi nemici chelo attaccano lungo il suo percorso

C’e un nemico lungo x → y se,una volta che Batman haraggiunto y , non ha modo ditornare a x .

Esempio

Batman si annoia

Ogni sera batman decide quale percorso attraversare e quindi qualegruppo di nemici dovra affrontare in quella serata.La vita rischia di diventare ripetitiva, visto che ci sono un numerolimitato di possibilita

Quanti sono idiversi insiemi dinemici che batmanpuo incontrare?

Esempio

Output=3

Esempio

Output=3

Esempio

Output=3

Esempio

Output=3

Problema

Dato il grafo della citta, il nodo di partenza e quello di arrivo,calcolare quanti sono i possibili insiemi di nemici che Batman puoincontrare.

Note

Il grafo e orientato

Il grafo non e necessariamente connesso

L’insieme vuoto e un sottoinsieme valido

Potrebbero esserci nemici irraggiungibili dalla batcaverna

I nemici non sono dati in input! Dove trovarli da soli.

Punteggio

Punteggio da 0 a 5 per ogni caso di test:

1. output sbagliato: 0 punti

2. output corretto: 5 punti

Casi semplici

Dal secondo (input1.txt) all’undicesimo caso (input 10.txt) i grafinon hanno cicli.

Note sul punteggio

Punteggio del programma

PUNTEGGIO =20∑i=1

(SCOREi × 5)

Un algoritmo che risolve i casi semplici fa almeno 30 punti.

Il programma supera il progetto (e sblocca il passaggio dell’esame)se ha PUNTEGGIO >= 30.

Note varie

Note

I Il progetto dara da 1 a 2 punti bonus allo scritto

I Conta il punteggio dell’ultimo sorgente accettato da judge

I Scadenza e Venerdı 21 Novembre alle 20:00

I Limite di 40 sottoposizioni per gruppo

I Potete provare con un dataset equivalente sulla vostramacchina (scaricate dal mio sito)

Do’s and Dont’s

Do

1. Discutere all’interno del gruppo

2. Chiedere chiarimenti sul testo

3. Chiedere opinioni su soluzioni

4. Sfruttare codice fornito nei laboratori

5. Utilizzare pseudocodice da libri o wikipedia

6. Richiedere aiuto (anche pesante) per la soluzione “minima”

7. Venire a trovarmi (Open Space 8, Povo2)

Don’t

1. Discutere con altri gruppi

2. Mettere il proprio codice su repository accessibili dal pubblico

3. Utilizzare codice scritto da altri

4. Condividere codice (!!!!!!!!!!!)