Friday, February 1, 2019

Compute the Hypotenuse

  • Problem Description

    Valentin participates in a show called "Shockers". The rules are quite easy: jury selects one letter which Valentin doesn't know. He should make a small speech, but every time he pronounces a word that contains the selected letter, he receives an electric shock. He can make guesses which letter is selected, but for each incorrect guess he receives an electric shock too. The show ends when Valentin guesses the selected letter correctly.

    Valentin can't keep in mind everything, so he could guess the selected letter much later than it can be uniquely determined and get excessive electric shocks. Excessive electric shocks are those which Valentin got after the moment the selected letter can be uniquely determined. You should find out the number of excessive electric shocks.

    Input
    The first line contains a single integer n (1<=n<=105) the number of actions Valentin did.

    The next n lines contain descriptions of his actions, each line contains description of one action. Each action can be of one of three types:

    Valentin pronounced some word and didn't get an electric shock. This action is described by the string ". w" (without quotes), in which "." is a dot (ASCII-code 46), and w is the word that Valentin said.
    Valentin pronounced some word and got an electric shock. This action is described by the string "! w" (without quotes), in which "!" is an exclamation mark (ASCII-code 33), and w is the word that Valentin said.
    Valentin made a guess about the selected letter. This action is described by the string "? s" (without quotes), in which "?" is a question mark (ASCII-code 63), and s is the guess a lowercase English letter.
    All words consist only of lowercase English letters. The total length of all words does not exceed 105.

    It is guaranteed that last action is a guess about the selected letter. Also, it is guaranteed that Valentin didn't make correct guesses about the selected letter before the last action. Moreover, it's guaranteed that if Valentin got an electric shock after pronouncing some word, then it contains the selected letter; and also if Valentin didn't get an electric shock after pronouncing some word, then it does not contain the selected letter.

    Output
    Output a single integer the number of electric shocks that Valentin could have avoided if he had told the selected letter just after it became uniquely determined.
    Include a main program that reads the lengths of the shorter sides of a right triangle from the user, uses your function to compute the length of the hypotenuse, and displays the result.

    Refer sample input and output for formatting specification.

    All float values are displayed correct to 2 decimal places.

    All text in bold corresponds to input and the rest corresponds to output
  • CODING ARENA
  • times = int(input())
    s= set()
    n= set()
    net= set()
    ans=0
    for i in range(times-1):
        temp=input().split(" ")
        if(len(net)==1 or len(n)==25):
            if(temp[0]=='!' or temp[0]=='?'):
                ans+=1
            continue
        if temp[0]=='.':
            for j in temp[1]:
                n.add(j)
        elif temp[0]=='!':
            m=set()
            if len(s)!= 0:
                for k in s:
                    if k in temp[1]:
                        m.add(k)
            else :
                for k in temp[1]:
                    m.add(k)
            for k in s:
                if k not in m:
                    n.add(k)
            for k in temp[1]:
                if k not in m:
                    n.add(k)
            s=m
        elif temp[0]=='?':
            if temp[1] in s :
                s.remove(temp[1])
                n.add(temp[1])
            else:
                n.add(temp[1])
        net=s-n
    print(ans)
  • Test Case 1

    Input (stdin)
    5
    
    ! abc
    
    . ad
    
    . b
    
    ! cd
    
    ? c
    
    
    Expected Output
    1
  • Test Case 2

    Input (stdin)
    8
    
    ! hello
    
    ! codeforces
    
    ? c
    
    . o
    
    ? d
    
    ? h
    
    . l
    
    ? e
    
    
    Expected Output
    2

No comments:

Post a Comment