Problem F
Distraheret
Languages
da
en
Man er enten gift eller ugift. Kan du afgøre, om nogen, der er gift, kigger på nogen, der er ugift?
Indlæsning
Første linje af indlæsningen består af to heltal: det totale antal $N$ af folk og antallet $L$ af disse, som kigger på nogen anden. Du kan antage $0< N$ og $0\leq L\leq N$. Derpå følger $N$ linjer, en for hver person, bestående af personens navn og ægteskabsstand. Folk har forskellige navne, som består af mellem $1$ og $10$ bogstaver fra det engelske alfabet. Hvis du kender personens ægteskabsstand, står der »m« for gift og »u« ugift. Ellers står der »?«; sådan en person er dog stadig enten gift eller ugift. Derpå følger $L$ linjer på formen »Alice -> Charlie«, som betyder, at Alice kigger på Charlie. Du har fuldstændigt overblik over hvem, der kigger på hvem. Ingen kigger på sig selv, og ingen kigger på mere end én anden person.
Udskrift
Skriv 1, hvis mindst én gift person kigger på nogen ugift person. Skriv 0, hvis ingen gifte personer kigger på nogen ugift person. Hvis dette ikke kan afgøres, skriv ?.
Pointsætning
|
Gruppe |
Point |
Begrænsinger |
|
1 |
23 |
$N\leq 3$, alle folks ægteskabsstand er kendt |
|
2 |
24 |
$N \leq 3$ |
|
3 |
25 |
$N \leq 12$ |
|
4 |
28 |
$N \leq 50\, 000$ |
| Sample Input 1 | Sample Output 1 |
|---|---|
3 2 Alice m Bobbie u Charlie m Alice -> Charlie Charlie -> Bobbie |
1 |
| Sample Input 2 | Sample Output 2 |
|---|---|
3 2 Alice m Bobbie ? Charlie m Alice -> Charlie Charlie -> Bobbie |
? |
| Sample Input 3 | Sample Output 3 |
|---|---|
3 2 Alice m Bobbie m Charlie m Alice -> Charlie Charlie -> Bobbie |
0 |
