COCI '18 Contest 4 #1 Elder

View as PDF

Submit solution

Points: 5 (partial)
Time limit: 1.0s
Memory limit: 64M

Problem type

After having watched all eight Harry Potter movies in a week, Nikola finally realized how the famous Elder Wand changes the wizard it obeys. If wizard A, whom the wand is currently obeying, is defeated by wizard B in a duel, then the wand will start obeying the wizard B.

Nikola is now wondering what would happen if 26 wizards labeled with uppercase letters of the English alphabet from A to Z began fighting in duels for the fondness of the Elder Wand. If we know the label of the wizard that the wand had obeyed before all duels and the outcomes of all N duels that were held one after another, answer the following questions:

  1. Which wizard did the wand obey after all N duels?
  2. How many different wizards did the wand obey?

Input

The first line contains an uppercase letter of the English alphabet, the label of the wizard that the wand obeyed at the beginning.

The second line contains an integer number N (1 \le N \le 100), the number of duels from the text of the task.

In the next N rows there are two different uppercase letters of the English alphabet Z1 and Z2 separated by a space, whereas the wizard with the label Z1 defeated the wizard with the label Z2 in the i^\text{th} duel.

Output

In the first line print an uppercase letter of the English alphabet, answer to the first question from the task description.

In the second line print an integer number, answer to the second question from the task description.

Scoring

Correct answer to the first question is worth 2 points and the correct answer to the second question is worth 3 points. If you do not know how to solve some part of the task, then print any value in the corresponding line.

Sample Input 1

A
3
B A
C B
D A

Sample Output 1

C
3

Explanation for Sample Output 1

Before the first duel, the Elder Wand obeyed wizard A. After the first duel, it obeyed wizard B, and after the second wizard C. The third duel didn't change anything.

Sample Input 2

N
5
D A
N B
B A
C D
F A

Sample Output 2

N
1

Sample Input 3

X
4
A X
B X
X A
D A

Sample Output 3

X
2

Comments


  • 0
    Mick  commented on Dec. 21, 2023, 3:57 a.m.

    so I got 29/50 what does AC in light green mean?


    • 0
      jakethepython  commented on Jan. 1, 2024, 8:20 p.m.

      I got the same exact score on my submission. I don't know if you had the same problem as I did but what I needed to fix was that when a previous owner gets the wand BACK after losing it, DO NOT INCREMENT the number of owners. Only add to the number of owners if someone gets the wand that has never had it before. I don't know if this helps at all, but hopefully you figure it out!


    • 0
      htoshiro  commented on Dec. 21, 2023, 11:53 a.m.

      you either only got the first question right or the second part (i assume first)


  • 0
    lilfrankster101  commented on May 17, 2023, 4:32 a.m.

    Hint: Only read if you're stuck:

    Don't forget that if a previous owner of the want defeats the current owner, you have to make sure to account for it. For example

    Lets Say A starts with the want and 3 fights:

    -B beats A

    -C beats B

    -A beats C

    A currently has the wand, and the wand has been passed around by 3 different owners. if you don't account for the fact that A has had the wand before, you output a 4 instead of a 3. In other words, A will be counted as a New owner of the wand when he's actually a previous owner.


  • 0
    Hackerman_567  commented on Dec. 21, 2022, 7:44 a.m.

    Can anyone explain to me how the third input and output works?


    • 2
      valegrete  commented on Dec. 26, 2022, 1:00 a.m. edited

      Wizard X starts with the wand and there are 4 total duels.

      Duel 1: A defeats X. Now A has the wand, and the wand has been owned by A and X.

      Duel 2: B defeats X. No change in wand status since neither B nor X owned the wand.

      Duel 3: X defeats A. Now X has the wand back, and the wand has been owned by A and X.

      Duel 4: D defeats A. No change in wand status since neither D nor A owned the wand.

      At the end of all 4 duels, X owns the wand and the wand has had two total owners: X and A.

      Therefore the output is:

      X

      2


  • 0
    seelinjd  commented on Dec. 19, 2022, 11:25 a.m.

    Hey guys and gals. I'm confused about the problem. Why is the output of sample 2 N and 1? Any input would be greatly appreciated.


    • 0
      volcano  commented on Dec. 20, 2022, 1:37 a.m.

      If wizard A, whom the wand is currently obeying, is defeated by wizard B in a duel, then the wand will start obeying the wizard B.

      This tells us that the only way to get the wand is to defeat wizard A (where wizard A has the wand).

      N
      5
      D A
      N B
      B A
      C D
      F A

      In each line, the first wizard defeats the second wizard (in this case, D defeats A, then N defeats B, and so on). Remember, since N begins with the wand, the only way for someone else to get the wand is to defeat N. Since nobody ever defeated N, nobody else ever got the wand. Therefore, the wand ends with N and is controlled by 1 wizard throughout.


      • 0
        seelinjd  commented on Dec. 20, 2022, 5:15 a.m.

        Thanks for your reply. I think I get it now.