Recently, Valery have come across an entirely new programming language. Most of all the…
- User
Recently, Valery have come across an entirely new programming language. Most of all the language attracted him with template functions and procedures. Let us remind you that templates are tools of a language, designed to encode generic algorithms, without reference to some parameters (e.g., data types, buffer sizes, default values).
Valery decided to examine template procedures in this language in more detail. The description of a template procedure consists of the procedure name and the list of its parameter types. The generic type T parameters can be used as parameters of template procedures.
A procedure call consists of a procedure name and a list of variable parameters. Let's call a procedure suitable for this call if the following conditions are fulfilled:
- its name equals to the name of the called procedure;
- the number of its parameters equals to the number of parameters of the procedure call;
- the types of variables in the procedure call match the corresponding types of its parameters. The variable type matches the type of a parameter if the parameter has a generic type T or the type of the variable and the parameter are the same.
You are given a description of some set of template procedures. You are also given a list of variables used in the program, as well as direct procedure calls that use the described variables. For each call you need to count the number of procedures that are suitable for this call. Input
The first line contains a single integer n (1 ≤ n ≤ 1000) — the number of template procedures. The next n lines contain the description of the procedures specified in the following format:
"void procedureName (type_1, type_2, ..., type_t)" (1 ≤ t ≤ 5), where void is the keyword, procedureName is the procedure name, type_i is the type of the next parameter. Types of language parameters can be "int", "string", "double", and the keyword "T", which denotes the generic type.
The next line contains a single integer m (1 ≤ m ≤ 1000) — the number of used variables. Next m lines specify the description of the variables in the following format:
"type variableName", where type is the type of variable that can take values "int", "string", "double", variableName — the name of the variable.
The next line contains a single integer k (1 ≤ k ≤ 1000) — the number of procedure calls. Next k lines specify the procedure calls in the following format:
"procedureName (var_1, var_2, ..., var_t)" (1 ≤ t ≤ 5), where procedureName is the name of the procedure, var_i is the name of a variable.
The lines describing the variables, template procedures and their calls may contain spaces at the beginning of the line and at the end of the line, before and after the brackets and commas. Spaces may be before and after keyword void. The length of each input line does not exceed 100 characters. The names of variables and procedures are non-empty strings of lowercase English letters and numbers with lengths of not more than 10 characters. Note that this is the only condition at the names. Only the specified variables are used in procedure calls. The names of the variables are distinct. No two procedures are the same. Two procedures are the same, if they have identical names and identical ordered sets of types of their parameters.
Output
On each of k lines print a single number, where the i-th number stands for the number of suitable template procedures for the i-th call.
Examples
Input
4 void f(int,T) void f(T, T) void foo123 ( int, double, string,string ) void p(T,double) 3 int a string s double x123 5 f(a, a) f(s,a ) foo (a,s,s) f ( s ,x123) proc(a)
Output
2 1 0 1 0
Input
6 void f(string,double,int) void f(int) void f ( T ) void procedure(int,double) void f (T, double,int)
void f(string, T,T) 4 int a int x string t double val
5 f(t, a, a) f(t,val,a) f(val,a, val) solve300(val, val) f (x)Output
1 3 0 0 2
Assistant
We are given a problem: count the number of template procedures that match a given procedure call.
We need to parse inputs: n template procedures, m variable declarations, k procedure calls.
Constraints: n,m,k <= 1000, types: int, string, double, and generic T.
Procedure definitions: "void procedureName (type_1, type_2, ..., type_t)". The types can be "int", "string", "double", "T". Parameter count t is between 1 and 5 inclusive. The procedure names are strings of lowercase letters and digits, length <=10. Variable names are distinct.
Variable declarations: "type variableName". types are "int", "string", "double". No generic variables.
Procedure calls: "procedureName (var_1, var_2, ..., var_t)". t also between 1 and 5. The variable names are given; they are among the m declared variables.
We need for each call: count how many procedures (among n) have the same name as the called procedure, the same number of parameters, and for each position, either the parameter type in the procedure definition is "T", or it's exactly the same as the variable's type.
Important: The generic type T matches any variable type. But note: T is just a placeholder. There is no "T" variable; it's only in definitions.
Thus it's straightforward: parse all procedures, group by name? But we can just iterate over all procedures for each call, because n,k <= 1000, so O(n*k) up to 1e6, and each procedure has at most 5 parameters, so it's fine. But we could also index by name and param count to speed up, but not necessary.
Parsing: The input lines may have leading/trailing spaces, spaces before/after parentheses, commas. Also spaces around "void". But basically each line is a single procedure definition, variable definition, or call. We need to parse them robustly.
Let's think about the format:
Procedure definition: starts with "void" (maybe preceded by spaces), then procedureName, then '(' (maybe with spaces), then list of types separated by commas (maybe with spaces), then ')'. Each type is either "int", "string", "double", or "T". Also the list may have spaces around types.
Variable definition: type variableName. type is "int", "string", "double". Possibly spaces.
Call: procedureName '(' var_1, var_2, ..., var_t ')'. Spaces allowed.
We should parse token by token, splitting by whitespace, but also parentheses and commas are tokens. However easier: read the line, then remove leading/trailing spaces, then we can manually parse.
Given that line length <=100, we can use simple string operations.
Simplify: Use a regex? Not allowed. We'll parse by scanning.
For procedure definition: Find first word after "void"? Actually the line: maybe "void f(int,T)". After stripping spaces, it starts with "void". So we can split by spaces, but then there is "f(int,T)" with no space before '(' maybe. So better to parse with a state machine: after "void", there is the procedure name, then an open parenthesis, then a list of types separated by commas, then close parenthesis. The name might be contiguous with '('? In the example: "void f(int,T)" has space between f and '('? Actually they wrote "void f(int,T)" - there is no space after f before '('? Let's see: "void f(int,T)". Possibly it's "void f(int,T)"? Typically there would be a space before '('? In the example "void f(int,T)" it's ambiguous: they didn't show spaces. In second example: " void f ( T )". Here there are spaces between f and '(' and after '(' etc. So we need to handle both. Easiest: remove all spaces? But then types like "string" etc. But spaces inside are not part of identifiers. So we could strip all whitespace? But then "void f(int,T)" becomes "voidf(int,T)"? Actually stripping all spaces means we would remove spaces between tokens, but then the name "f" would become adjacent to "void" and to '('? Let's think: if we remove all spaces, the line becomes "voidf(int,T)" which is wrong because "void" and "f" become merged. So we cannot remove all spaces; we need to parse tokens while ignoring spaces.
We can do: read the line, then split by whitespace, parentheses, and commas? For instance, we can treat '(' and ')' and ',' as separate tokens, ignoring spaces. So we can tokenize the string: tokens are sequences of non-space characters that are either alphanumeric or parentheses/comma? But parentheses and commas are separate tokens. A simple approach: replace commas and parentheses with spaces and then split? For example, replace '(' with ' ( ', ')' with ' ) ', ',' with ' , ', then split by whitespace. That yields tokens including these symbols. Then we can parse.
For procedure definition: tokens: ["void", "procedureName", "(", type1, ",", type2, ",", ... , type_t, ")"] but note after '(' we might have type1, then maybe a comma, then type2, ... etc. So we can parse: after stripping, the first token must be "void". Next token is the procedure name. Then "(". Then subsequent tokens: we will have types and commas alternately. The last token before the closing ")" should be a type (or maybe nothing if no parameters? But t>=1 so at least one). So we can simply iterate: after "(", we read tokens until we see ")". For each token that is not a comma, it is a type. So we can collect types.
Variable declaration: tokens: [type, variableName] maybe? Actually format: "type variableName". So after stripping and splitting (no parentheses/comma), we get two tokens: type and variable name. But there could be spaces. So we can just split by whitespace and get exactly two tokens. (But note there could be extra spaces at start/end, but splitting yields tokens). So that works.
Call: "procedureName (var_1, var_2, ..., var_t)". Tokenizing with parentheses/comma: we can treat similarly: we replace '(' and ')' and ',' with spaced tokens. Then we get tokens: procedureName, "(", var1, ",", var2, ",", ... , var_t, ")". So we can parse: first token is procedure name, then "(", then we collect variable names (alternating commas) until ")".
Thus a generic tokenizer: read line, then define a list tokens = re.split(r'\s+|(?<=()|(?=))|(?<=,)', line)? Or simpler: we can manually scan.
Given the small length, we can do:
def tokenize(line): tokens = [] i = 0 n = len(line) while i < n: if line[i].isspace(): i += 1 continue if line[i] in '(),': tokens.append(line[i]) i += 1 continue # else read an identifier or type keyword: sequence of characters not whitespace and not parentheses/comma j = i while j < n and not line[j].isspace() and line[j] not in '(),': j += 1 tokens.append(line[i:j]) i = j return tokens
This will split tokens appropriately. For example "void f(int,T)" yields: ["void","f","(","int",",","T",")"].
Now for procedure definition: we need to check first token is "void". Next token is name. Then token[2] must be "(" and last token must be ")". Then between are parameters: tokens[3:-1]. But they include commas. So we can filter out commas: only take tokens that are not ','. That gives list of types. The order matters. So types = [tok for tok in tokens[3:-1] if tok != ',']
But need to ensure that tokens[3:-1] pattern includes possible empty? Not needed.
Also verify: What if there are spaces before/after void? The tokenizer skips spaces so first non-space token will be "void". Good.
Now for call: tokens: first token is procedureName, then "(", then variable names and commas, then ")". So similar: after name and "(", we take tokens from index 2 to -1, filter out commas to get variable names.
For variable: tokens = line.split() should suffice: just two tokens.
Now we need to store variables: map variable name -> actual type (int, string, double).
Store procedures: list of tuples (name, param_types list). param_types list are strings, either "int","string","double","T". We'll keep as is.
Then for each call: for each procedure with same name and same number of parameters (len(param_types) == len(call_vars)), we check for each position: either param_type == "T" or param_type == var_type. If all match, count++. Print count.
Edge Cases: The generic T matches any type; but what about if multiple T's? They are independent. That's fine.
Also ensure that variable names used in call are defined. The problem says only the specified variables are used.
Potential pitfalls: Over counting? Since procedures are distinct even if same name and param types? Actually they said "No two procedures are the same. Two procedures are the same, if they have identical names and identical ordered sets of types of their parameters." So each definition is unique, but there could be multiple procedures with same name but different parameter types (including generic T). So counting all distinct procedures that match.
Now check examples:
Example1: 4 procedures: void f(int,T) void f(T, T) void foo123 ( int, double, string,string ) void p(T,double)
Variables: int a string s double x123
Calls: f(a, a) -> variables: a is int, a int. Check procedures named f:
- f(int,T): param1 int matches a (int), param2 T matches a (any) -> OK.
- f(T,T): both T -> OK. So count=2.
f(s,a): s string, a int.
- f(int,T): param1 int vs string: not match (since param1 not T and not equal) -> fail.
- f(T,T): both T -> OK. So count=1.
foo (a,s,s) -> call name "foo"? Actually procedure name is "foo123"? call name is "foo". Not match any procedure (since no procedure named "foo") -> count 0. But also param count mismatch maybe. So 0.
f(s,x123): s string, x123 double.
- f(int,T): int vs string -> fail.
- f(T,T): both T -> OK. count=1.
proc(a): call name "proc", none -> 0.
Matches output.
Example2: 6 procedures. void f(string,double,int) void f(int) void f ( T ) void procedure(int,double) void f (T, double,int)
void f(string, T,T)Variables: int a, int x, string t, double val.
Calls: f(t, a, a) -> t string, a int, a int. Check procedures named f with 3 params:
- f(string,double,int): requires string, double, int. But second param is a int but needs double -> fails.
- f(T, double, int): first T matches string, second double vs a int fails.
- f(string, T, T): first string matches, second T matches int, third T matches int -> OK. So count=1. (Other f have 1 param or 2 params? None with 3 besides these. So 1)
f(t,val,a): t string, val double, a int. Check:
- f(string,double,int): string,double,int matches exactly -> OK.
- f(T,double,int): T matches string, double matches, int matches -> OK.
- f(string,T,T): string matches, T matches double, T matches int -> OK. All three 3-param f match. So count=3.
f(val,a,val): val double, a int, val double. Check:
- f(string,double,int): first string vs double fails.
- f(T,double,int): T matches double, second double vs a int fails.
- f(string,T,T): first string vs double fails. No match -> 0.
solve300(val,val): no procedure named solve300 -> 0.
f(x): call with 1 param x int. Check procedures named f with 1 param:
- f(int) -> exact match -> OK.
- f(T) -> T matches any -> OK. So count=2.
Output matches.
So the algorithm is correct.
Implementation details:
Read n, then for i in range(n): line = input().strip()? But we need to preserve spaces inside? Actually we want to parse spaces, but leading/trailing spaces not needed. But we must not strip all spaces because we need to tokenize correctly, but we can strip leading/trailing spaces because they are irrelevant. So line = input().strip()? In example, there are spaces before "void" so after strip they are removed. That's fine. However note that there could be spaces after the procedure name and before '(' that are not stripped because we strip only leading/trailing. But after we strip the whole line, we remove leading/trailing whitespace. That is fine. Then tokenize as described.
But wait: Example input line: " void f ( T ) " has spaces at start and end. After strip, becomes "void f ( T )". Our tokenizer will skip internal spaces. So good.
So we can strip line first to remove leading/trailing spaces, then tokenize.
But careful: There is possibility that the line has spaces only at start but also after '(' and before types? That's fine.
Now for variable declarations: line may be " int a" with leading spaces. strip, then split whitespace -> ["int","a"]. Good.
Calls: same.
We should store procedures in a list. But also perhaps index by name to avoid scanning all procedures for each call. But not needed.
However if n=1000, k=1000, scanning all for each call is 1e6, which is fine.
But also each procedure has at most 5 parameters, so comparison cheap.
Thus solution is O(nk5).
Now we should output each count on a separate line.
Edge Cases: The name of procedure can contain digits? Yes, lowercase English letters and numbers. So valid.
Be careful: The generic type is "T". Could there be a variable type "T"? No, variable types are only "int","string","double". So "T" is only used in definitions.
Parsing: In procedure definitions, type tokens could be "int", "string", "double", "T". Check they are exactly these; but input guaranteed.
Now, the tricky part: The name of the procedure could be something like "void" or "int"? Not likely but can be? They said names are non-empty strings of lowercase English letters and numbers. So they cannot be "void", which contains uppercase? Actually "void" is lowercase letters. So could a procedure be named "void"? The problem doesn't explicitly forbid that. It says "names of variables and procedures are non-empty strings of lowercase English letters and numbers". So "void" consists of lowercase letters, so it's possible. But the definition always starts with the keyword "void". That would be ambiguous: "void void(...)"? That would be a procedure named "void". Is that allowed? Possibly yes. In the parsing, the first token is "void", and the second token is the name. So if the name is "void", the second token is "void". That's fine. So we treat the first token as the keyword, not part of name.
Similarly, could a variable name be "int"? It could be, but variable declaration has type first then name. So if a variable name is "int", we have "int int"? That is "type variableName". Could be allowed. So we must parse correctly.
Now, in calls: The first token is procedure name. Could be "void"? Possibly. But that would be ambiguous with the keyword? But calls don't have "void". So it's fine.
Now, when we tokenize procedure definitions, we need to skip the initial "void". So we can simply check if tokens[0] == "void". If not, maybe the input is malformed, but it's guaranteed to follow format.
Now Implementation Steps:
-
Read n.
-
Initialize list procedures = [] (each element: (name, param_types_list)) For i in range(n): line = input().strip() tokens = tokenize(line) # as defined # tokens[0] is "void" name = tokens[1] # tokens[2] should be "(" # find the index of ")"? Actually tokens list includes ")" as last token. So we can assume last token is ")". if tokens[-1] != ")": # just in case? # but should be pass # extract types: tokens between index 2 and -1, excluding commas param_types = [] for tok in tokens[3:-1]: # Actually tokens[2] is "(", tokens[3] is first type or maybe ")" if no params? But t>=1 so at least one type. if tok != ',': param_types.append(tok) # Note: if there is space after '(' and before first type, tokenizer will treat '(' as separate, then spaces skipped, then type. So tokens[3] is the first type? Let's test: For "void f(int,T)", tokens: ["void","f","(","int",",","T",")"]. tokens[2]="(", tokens[3]="int". tokens[4]=",", tokens[5]="T", tokens[6]=")". So between index 3 and -1: indices 3,4,5 => tokens[3]="int", tokens[4]=",", tokens[5]="T". Filter out commas gives ["int","T"]. # If there is whitespace: "void f ( int , T )" tokens: ["void","f","(","int",",","T",")"] same. # So param_types = [tok for tok in tokens[3:-1] if tok != ','] # But note: What if there is a procedure with one parameter: "void f(T)". tokens: ["void","f","(","T",")"]. Then tokens[3:-1] => tokens[3] is "T", tokens[-1] is ")", so tokens[3:-1] gives only token at index 3 (since -1 exclusive) if we use tokens[3:-1]? Let's see: tokens indices: 0="void",1="f",2="(",3="T",4=")". So tokens[3:-1] includes index 3? slice 3:4 gives ["T"] (since -1 is 4? Actually -1 index is 4, but slice excludes end, so tokens[3:4] = ["T"]). So we need to include up to the token before ")", but not including ")". tokens[3:-1] works for length>1? Actually if tokens = ["void","f","(","T",")"], indices: 0,1,2,3,4. tokens[3:-1] means start=3, stop=-1=4? In Python, stop index is exclusive, -1 corresponds to index 4? Wait, -1 index refers to the last element (index 4). So tokens[3:-1] gives from index 3 up to (but not including) index -1 which is index 4? Actually slice uses negative indices: tokens[3:-1] means start=3, end=-1. In a list of length 5, -1 index is 4, so tokens[3:-1] is indices 3 only? Let's test mentally: In Python, lst = [0,1,2,3,4]; lst[3:-1] gives [3] because indices: 0,1,2,3,4; start=3 (value 3), end=-1 corresponds to index 4, so slice includes indices 3? Actually it goes up to but not including index 4, so includes index 3 only. So yes, tokens[3:-1] includes only token at index 3. That's correct. If there are two parameters: tokens length maybe 7: indices 0,1,2,3,4,5,6. -1 index is 6, slice tokens[3:6] gives indices 3,4,5 which includes types and commas. So it's fine. # However we need to be careful: tokens[3:-1] may not always start at index 3 if there are spaces? Actually the '(' token is at some index. After name token, the next token should be '(' exactly. So index 2 is '(' (if tokens[2] is '('). So types start at index 3. Good. procedures.append((name, param_types))
But note: the tokenizer may produce tokens where there could be extra spaces? Already accounted.
However what about the case: "void f ( T )" where there are spaces between name and '('? Our tokenizer: tokens: ["void","f","(","T",")"]. It's fine.
-
Read m: integer.
-
Initialize variables dict: var_type = {}. For i in range(m): line = input().strip() # split by whitespace parts = line.split() # There should be exactly two tokens: type, name. typ, name = parts[0], parts[1] var_type[name] = typ
-
Read k: integer.
-
For each call i in range(k): line = input().strip() tokens = tokenize(line) # This will include '(', ')', ',' etc. # first token is procedure name proc_name = tokens[0] # second token must be '('; but we can ignore as it's there. # collect variable names: from tokens[2:-1] (skip '(' at index1) and filter out commas # tokens: [proc_name, '(', var1, ',', var2, ',', ..., var_t, ')'] var_names = [tok for tok in tokens[2:-1] if tok != ','] # compute result: count = 0 for (p_name, param_types) in procedures: if p_name != proc_name: continue if len(param_types) != len(var_names): continue # check each position: match = True for i_param, param_type in enumerate(param_types): var_name = var_names[i_param] var_typ = var_type[var_name] # guaranteed exists if param_type != "T" and param_type != var_typ: match = False break if match: count += 1 print(count)
That's it.
Potential issues: The tokenizer might treat digits and letters correctly. Must ensure that tokenization of procedure definitions yields exactly the types as tokens without extra commas. Also in call tokenization, we should ensure that variable names are taken correctly. What if there is a call like "f()" with no parameters? But t>=1, so at least one.
Now think about tokenization: The tokenizer splits on spaces and also on characters '(', ')', ',' as separate tokens. But what about the case where there is no space between name and '('? e.g., "f(a,b)". In call, we have "procedureName (var_1,...)" maybe with or without space. Our tokenizer: The procedure name token will be "f" if there is a space before '('? If there's no space, e.g., "f(a,b)", scanning: start at 'f', it reads characters until whitespace or one of '(),'. Since '(' is in the set, it will stop before '('? Actually our tokenizer reads while not whitespace and not in '(),'. So when we see 'f', it reads letters until it sees '(' (which is in the set). At that point, it will stop and add "f" as token. Then i is at index after 'f'? Wait, we need to manage the index correctly. Let's implement properly:
We'll have a pointer i. While i < n: if char[i] is space: i++. elif char[i] in '(),': tokens.append(char[i]); i++. else: start = i; while i < n and not char[i].isspace() and char[i] not in '(),': i++ ; tokens.append(line[start:i]).
For "f(a,b)": char[0]='f' not space not special, start=0, then we increment i while condition. The next char is '(' which is in special set, so stop. So we add token "f". Then i is at '(' (since we stopped before '('? Actually we break when char[i] is in special set, but we haven't consumed it. At that moment i is still at '('? Let's simulate:
i=0, char[0]='f' -> not space, not special => start=0. Then while loop: i++ -> i=1, check char[1]='(' which is in special, so condition fails (while condition: char[i] not space and not in set). So loop ends. After loop, we add substring from start to i: line[0:1]="f". Then we continue outer loop. Now i is still 1 because we haven't advanced past the '('; but we need to process '(' next. In the next iteration, i=1, char[1]='(' is in special, so we add '(' and i++ => i=2. So correct.
So tokenization works.
Now for procedure definition "void f(int,T)": tokenized as described.
For variable definition, line.split() is easier.
Now, we need to parse the procedure definition correctly when there is no space between name and '('? That's fine.
One more nuance: The type tokens can be "int", "string", "double", "T". "string" is a type that is a word, no punctuation. Good.
Now, there is also the possibility of a procedure name containing digits; that's fine.
Now, performance wise, it's fine.
Let's write the code.
But there is a potential pitfall: The input lines may have spaces after commas before types, e.g., "void f( int , T )". Our tokenizer will produce tokens: ["void","f","(","int",",","T",")"] because after '(' we have space, but tokenizer skips spaces, then reads "int", then sees ',' (after space? Actually after int, there is a space then ','? The tokenizer will skip spaces before reading, so after reading "int", the next char is space, which is skipped, then next char is ',', which is added as a token, then space skipped, then "T", etc. So it's fine.
Now, regarding reading input: Since there can be up to 1000 lines, and each line length <=100, no memory issues.
Now, let's double-check the parsing of procedure definitions: In some definitions, there might be extra spaces between void and name, like "void f (int,T)". That yields tokens: ["void","f","(","int",",","T",")"]; after strip, leading spaces removed.
But there might be a scenario where there is a space after '(' but before first type? Already fine.
Now, what about the possibility that the procedure definition has spaces in the type list, like "void f(int, string)". That contains a comma and then a space before "string". Our tokenizer: after "int", we encounter ',' (added), then space skipped, then "string" read. So tokens: ["void","f","(","int",",","string",")"]; then param_types extracted by ignoring commas gives ["int","string"]. Good.
Now, one more edge: The procedure name could be something like "void123"? No, it's after the keyword void.
Now, we should consider that there could be a procedure named "T"? That is allowed, but then it's a name, not the generic type. In the definition of a procedure, after "void", the next token is the name, which could be "T". That would be ambiguous only for humans. But then the type list still has "T" tokens. Our parsing treats any token that is not ',' as a type when collecting param_types. But if the name was "T", it's in a different position. So no conflict.
Now, we also must ensure that we treat the generic "T" as a special type, not as a variable name. In matching, we check if param_type == "T" or param_type == var_type. That's correct.
Now, we need to be careful about case: types are exactly "int", "string", "double", "T". They are lower case except T is uppercase. Variable types are also lower case. So we compare exactly.
Now, potential edge: What if there is a variable name "T"? The variable names are lower case letters and numbers, so they can't be uppercase. So "T" is uppercase, not a variable name. So no conflict.
Now, implement tokenize as a function:
def tokenize(s): tokens = [] i = 0 n = len(s) while i < n: if s[i].isspace(): i += 1 continue if s[i] in '(),': tokens.append(s[i]) i += 1 continue j = i while j < n and not s[j].isspace() and s[j] not in '(),': j += 1 tokens.append(s[i:j]) i = j return tokens
Now, test with a few strings.
Let's quickly mentally test:
s = "void f ( int , T )" tokens: i=0: 'v' not space, not special => start=0, j goes to i=1? Actually need to step: j=i=0, while j<... condition: char not space and not in set; at j=0, 'v' ok, j=1; char[1]='o' ok... continues until j=4? Actually "void" length 4; at j=4, char[4]=' ' (space), condition fails; tokens append s[0:4]="void". i=j=4. Loop: char[4] space -> i=5. char[5]='f', not space not special, start=5, j=5->6? At j=5 'f' ok, j=6 char[6]=' ' -> fail, token "f". i=6. Next char space -> i=7. char[7]='(' special -> add '(' i=8. char[8]=' ' space -> i=9. char[9]='i' not space etc -> start=9, j moves until char[12]? Actually "int" plus maybe trailing? At char[9]='i',10='n',11='t',12=' ' -> token "int". i=12. space -> i=13. char[13]=',' special -> add ',' i=14. char[14]=' ' space -> i=15. char[15]='T' start, j=15->16? char[16]=' ' -> token "T". i=16. space -> i=17. char[17]=')' special -> add ')' i=18. End. tokens: ["void","f","(","int",",","T",")"] Good.
Now, if there is no spaces: "void f(int,T)" tokens: i=0: start=0, j increments until char[4]=' '? Actually no space: "voidf(int,T)"? Wait string is "void f(int,T)"? Actually there is a space after void: "void f(int,T)". So tokens: "void" then space, then "f" then '(' etc. Good.
But what about "void f(int,T)"? Actually there is no space between f and '('? In the original example, it's written as "void f(int,T)" without a space after f? Possibly they wrote "void f(int,T)" where after f there is no space before '('? But the tokenizer will treat it as: after "f" token, next char '(' is special, added separately. So token list: "void","f","(","int",",","T",")". Works.
Now if there were no space after void: "voidf(int,T)"? That would be invalid because the keyword "void" should be separate. But specification says lines may contain spaces at beginning and end, but doesn't guarantee there is a space between void and name? Typically there must be a space because they are separate tokens. However it's plausible that there is no space? The problem statement: "The lines describing the variables, template procedures and their calls may contain spaces at the beginning of the line and at the end of the line, before and after the brackets and commas. Spaces may be before and after keyword void." It does not say that there can't be no space between keyword void and procedure name. It only says spaces may be before and after void. But the natural reading: In the format "void procedureName (type_1, ...)" you would expect at least one space between void and name. Also they said "Spaces may be before and after keyword void." That implies there might be spaces before void (beginning) and after void (between void and name) but they don't forbid no space? However typical input will have spaces. In any case, if there is no space, the tokenizer would see "voidf" as a single token, which would be problematic. But the problem likely ensures the format has whitespace separating tokens. Because they explicitly mention spaces can be before/after brackets, commas, etc., but the tokens themselves (void, name) are separate and are separated by spaces in the specification. I think it's safe to assume there is whitespace between void and name. We'll assume input adheres to that.
But to be safe, we might parse more robustly: The line must start with "void", but after that there might be spaces. We can locate the position of "void" and then skip it, then find name, etc. But I think it's fine.
Now, memory: we store procedures as list of (name, param_types). Since n <=1000, fine.
Now, produce output.
Testing with examples should work.
But I want to double-check the parsing of the call line when there are spaces before parentheses. For example, "f ( s ,x123)" from first example output. tokens: first token "f", then "(", then "s", ",", "x123", ")" after filtering commas we get ["s","x123"].
Now, note that in call, variable names are guaranteed to exist; no need to check.
Now, complexity O(100010005)=5 million ops, trivial.
Now, implement.
Edge Cases: There might be multiple procedures with same name but different number of parameters; we filter by length.
Now, if there is a procedure with name "procedureName" and parameters ["T","double"] etc. Already handled.
Now, one more nuance: Could there be a procedure with parameter type "t"? No, types are only the specific ones.
Now, might there be a call with a variable name that is not defined? No.
Now, we must be careful about reading input lines: Because the lines may have trailing spaces, we use strip() to remove them. But what if a line contains only spaces? Not possible because each line has at least something.
Now, regarding the tokenizer: It returns tokens. For procedure definitions, we need to get param_types. However, if there are multiple commas, our filter may include any token that is not ','. That works. But what about if there is a comma that appears as part of a type? No, types are simple words.
Now, check if there could be an empty token due to consecutive delimiters? For example, "void f( )" but t>=1, so not.
But maybe "void f(,)"? Not allowed.
So fine.
Now, consider that in call, variable names could be "T"? But variable names are lower case letters and numbers; "T" is uppercase, so not.
Now, final code.
But wait: The input format: first line integer n, then n lines of procedures. Then integer m, then m lines variables. Then integer k, then k lines calls. There might be blank lines? Not mentioned. So we can read line by line with input().strip() but careful: if there is a blank line, strip() would yield empty string, but problem says there are no blank lines except maybe after integers? Typically after reading an integer using input() we get the integer line; next line is the first procedure, no blank lines. So okay.
Implementation plan in Python:
def solve(): import sys data = sys.stdin.read().splitlines() # But easier: use input() in loop. But we need to be careful about reading many lines. # We'll just use input() as it's fine. # However, we need to strip each line? We'll do line = input().strip() # However, if there are lines with only spaces, strip yields empty, but we can still parse? Not needed. # I'll implement using sys.stdin for speed? Not necessary. # But given constraints low, okay.
Better to use sys.stdin.read() to avoid overhead? But fine.
I'll write:
import sys
def tokenize(s): tokens = [] i = 0 n = len(s) while i < n: if s[i].isspace(): i += 1 continue if s[i] in '(),': tokens.append(s[i]) i += 1 continue j = i while j < n and not s[j].isspace() and s[j] not in '(),': j += 1 tokens.append(s[i:j]) i = j return tokens
def main(): input = sys.stdin.readline n_line = input() while n_line.strip() == '': n_line = input() # in case of blank lines, but unlikely n = int(n_line.strip()) procedures = [] for _ in range(n): line = input().strip() # maybe there are blank lines? Not expected but just in case: while line == '': line = input().strip() tokens = tokenize(line) # tokens[0] is 'void' name = tokens[1] # param_types param_types = [tok for tok in tokens[3:-1] if tok != ','] procedures.append((name, param_types)) m_line = input() while m_line.strip() == '': m_line = input() m = int(m_line.strip()) var_type = {} for _ in range(m): line = input().strip() while line == '': line = input().strip() typ, name = line.split() var_type[name] = typ k_line = input() while k_line.strip() == '': k_line = input() k = int(k_line.strip()) out_lines = [] for _ in range(k): line = input().strip() while line == '': line = input().strip() tokens = tokenize(line) proc_name = tokens[0] var_names = [tok for tok in tokens[2:-1] if tok != ','] count = 0 for p_name, param_types in procedures: if p_name != proc_name: continue if len(param_types) != len(var_names): continue match = True for pt, vn in zip(param_types, var_names): vt = var_type[vn] if pt != 'T' and pt != vt: match = False break if match: count += 1 out_lines.append(str(count)) sys.stdout.write('\n'.join(out_lines))
if name == 'main': main()
But need to test with example.
Test with example1:
Input as given. We'll simulate.
Let's run mental: n=4 lines: "void f(int,T)" -> tokenize: ["void","f","(","int",",","T",")"]; name="f", param_types = filter commas => ["int","T"]. "void f(T, T)" -> tokens: ["void","f","(","T",",","T",")"]; param_types: ["T","T"]. " void foo123 ( int, double, string,string ) " -> after strip: "void foo123 ( int, double, string,string )" -> tokenize: ["void","foo123","(","int",",","double",",","string",",","string",")"]; param_types: ["int","double","string","string"]. " void p(T,double)" -> strip: "void p(T,double)" -> tokenize: ["void","p","(","T",",","double",")"]; param_types: ["T","double"].
Variables: 3 lines: "int a" -> typ=int, name=a. " string s" -> strip: "string s" -> split => ["string","s"]. "double x123" -> typ=double, name=x123.
Calls: 5 lines: "f(a, a)" -> tokenize: ["f","(","a",",","a",")"] -> proc_name=f, var_names=["a","a"]. Match: count 2. " f(s,a )" -> tokenize: ["f","(","s",",","a",")"] -> var_names ["s","a"] -> count 1. "foo (a,s,s)" -> tokenize: ["foo","(","a",",","s",",","s",")"] -> proc_name="foo", var_names ["a","s","s"]; no procedure with name "foo" -> count 0. " f ( s ,x123)" -> tokenize: ["f","(","s",",","x123",")"] -> count: f with (int,T) fails, (T,T) passes -> 1. "proc(a)" -> tokenize: ["proc","(","a",")"] -> count 0.
Output matches.
Now example2: Should work.
Now, potential tricky part: The procedure name could be something like "void" where second token is "void". That would be parsed correctly: name = tokens[1] = "void". Then param_types list may include "void"? Not likely but allowed? Not type. But if name is "void", we store it, and later call with "void(...)", then it will match procedures with name "void". That's allowed. So fine.
Now, what about lines that have no spaces between name and '('? Our tokenizer still works because it splits '(' as separate token. But we rely on the tokens list having '(' at index 2. However if there is no space, tokens still are: [name, '(']? Actually after name token, the next character is '(' which becomes separate token, so tokens[1] is name, tokens[2] is '('? Let's test: "f(a,b)" for call. That's call, not definition. For definition: "void f(int,T)" no space between f and '('? tokens: after "void", space, then "f"? Actually there is space after void? But assume we have "void f(int,T)" with space after f? It says "void f(int,T)" might have space? Actually if there is no space between f and '(' then it's "void f(int,T)". But "void" and "f" separated by space, so after void we have space, then f, then '(' with no space. Then tokenizer: after reading "void", we have space, then 'f' token (since next char is 'f'), we read until '('; then add "f". Next char '(' => token '(' . So tokens[1] = "f", tokens[2] = '('. So still index 2 is '('.
Thus param_types extraction using tokens[3:-1] (skip '(') should work. Because after '(' token, the next token is either a type or ')'? But in case of no parameters? t>=1, so there will be at least a type. So tokens[3] exists. In case of one parameter: tokens = ["void","f","(","T",")"]; tokens[3] = "T", tokens[-1] = ")" so tokens[3:-1] -> ["T"]; good.
But is it always tokens[3]? What if there are spaces before '('? Example: "void f (int,T)". Here tokens: ["void","f","(","int",",","T",")"]; same. So index 2 is '('? Actually check: after name token "f", there may be a space, then '('? The tokenizer will skip spaces, so the next non-space is '('; so tokens[2] is '('.
But what about a scenario: "void f ( int , T )"? tokens: after "void", then "f", then '(' (since after f, spaces, then '('), so tokens[2] is '('.
Thus index 2 is '(' for all.
But if there were no space between void and name? That would cause tokens[0]="voidf"? Not allowed. So ignore.
Thus our parsing is consistent.
Now, one more nuance: The variable declarations: could have multiple spaces, but split works.
Now, potential error: When reading lines with input().strip(), we might strip away spaces that are needed? No, we only tokenize after stripping; spaces inside are preserved until tokenization. So fine.
Now, for calls, tokenization should work similarly.
But what about the call: "proc(a)" we did.
Now, there might be a call with spaces before commas: "f(s, a)" tokens: ["f","(","s",",","a",")"]; filter out commas yields ["s","a"].
Now, also note that variable names are distinct and used in calls. No need for extra validation.
Thus the solution seems ready.
But let's consider if there is any scenario where our tokenization fails: Suppose a variable name contains punctuation? No, only lowercase letters and numbers. So safe.
Now, what about the type "string"? It's a word, no issues.
Now, think about the possibility of a line: "void f (T,string)" where there is no space after comma? That is fine.
Now, one more thing: The tokenizer returns tokens including parentheses and commas. When we filter out commas from the slice tokens[2:-1], we must also consider that the slice might include a closing parenthesis? But we slice to -1, which excludes the last token (which is ')'), so no.
But is it possible that the token before ')' is a comma? That would indicate trailing comma, like "void f(int,)"? Not allowed because each parameter must have a type and t>=1, but they might not include trailing comma. The problem doesn't specify that extra commas are not allowed; it says the list of types separated by commas. Usually there is no trailing comma. So we can assume no trailing comma before ')'. So our filter is fine.
But what if there is a space between '(' and the first type? Our tokenizer will skip spaces, so the token after '(' is the type. So tokens[3] is that type. So our slice includes from index 3 to -1. However if there is a space between '(' and type, but also if there are no spaces, it's still same.
But wait: The tokens list may have more tokens if there are extra spaces? For example: "void f ( int , T )". tokens: index0:void,1:f,2:(,3:int,4:,,5:T,6:). So slice [3:6] = [int, ',', T]. Filter out commas => [int, T]. Good.
But what about: "void f ( )"? Not allowed due to t>=1.
Now, what about: "void f(T)" tokens: [void,f,(,T,)]; slice [3:4] = [T]; filter yields [T]; good.
Now, but consider: "void f ( T )". tokens: [void,f,(,T,)]; slice [3:4] = [T]; good.
Now, one more edge: In procedure definition, could there be a type like "int"? Yes. Could there be a type "T"? Yes.
Now, the generic T is case-sensitive: it's uppercase. So if param_type == 'T' we treat as generic.
Now, note: There could be procedure name that equals a type? e.g., "int" is a type, but variable names and procedure names are lowercase letters and numbers, so "int" is lowercase, but T is uppercase. So not conflict.
Now, implement.
Potential pitfalls: When reading integer n, m, k, there might be extra whitespace; using int(s.strip()) handles.
Now, final code as above.
But I'd like to test with a custom case: n=1, procedure: void main(T) m=1 variable: int x; k=1 call: main(x) -> count 1. Works.
Now, another: procedure: void foo(T,T) and call foo(a,b) with a int, b string -> both T -> match.
Now, test with procedure: void foo(int,int) call foo(a,b) where a int, b int -> match. call foo(a,s) where s string -> no match.
Now, test with procedure: void foo(T) and void foo(int) and call foo(a) with a int -> both match -> count 2.
Now, test with procedure: void foo(T,string) call foo(a,b) with a int, b string -> match. call foo(a,b) with a string, b string -> match (T matches string). call foo(a,b) with a double, b int -> fails because second param string != int.
Now, all good.
Now, check if there is any scenario where a procedure definition has more than 5 parameters? It says t between 1 and 5 inclusive. So fine.
Now, about reading: We used while loops to skip blank lines just in case. But better to avoid infinite loops if there are unexpected blank lines. Usually not.
We can simplify: for each group, read line and strip, but if empty, continue reading until non-empty. But input spec doesn't mention blank lines, so we could simply use input().strip() without extra loop. But I'll keep the while loops for safety.
But note: after reading n, the next n lines could have blank lines? No. So we might inadvertently skip non-blank lines if we treat empty as skip, but if a line is not empty, we read it. If some procedure line is empty (only spaces), strip yields empty; but is that allowed? Probably not. So safe.
Let's just not include while loops; just read exactly n lines. But to be robust, we can read line and if after strip it's empty, we treat it as an empty line but still count it? Not needed. I'll go with simple approach: read exactly n lines using input().strip() and trust it's non-empty.
Simplify code:
def main(): import sys input = sys.stdin.readline
n = int(input().strip()) procedures = [] for _ in range(n): line = input().strip() tokens = tokenize(line) # first token is 'void' name = tokens[1] param_types = [tok for tok in tokens[3:-1] if tok != ','] procedures.append((name, param_types)) m = int(input().strip()) var_type = {} for _ in range(m): typ, name = input().strip().split() var_type[name] = typ k = int(input().strip()) out = [] for _ in range(k): line = input().strip() tokens = tokenize(line) proc_name = tokens[0] var_names = [tok for tok in tokens[2:-1] if tok != ','] cnt = 0 for p_name, param_types in procedures: if p_name != proc_name: continue if len(param_types) != len(var_names): continue # match ok = True for pt, vn in zip(param_types, var_names): vt = var_type[vn] if pt != 'T' and pt != vt: ok = False break if ok: cnt += 1 out.append(str(cnt)) sys.stdout.write('\n'.join(out))Now, test with provided examples. Good.
But we must handle case where token list for call might have length 2? That would be if call is "f()" (no parameters). But t>=1, so not.
But could there be a call with one variable, like "f(a)"? tokens: ["f","(","a",")"]; tokens[2:-1] -> tokens[2] is "a", tokens[-1] is ")", so slice [2:-1] yields ["a"]; filter commas yields ["a"]. Good.
Now, if there are spaces: "f( a )" tokens: ["f","(","a",")"]; same.
Now, what about "f ( a )" tokens: ["f","(","a",")"]; good.
Now, but if there is a comma after last variable? Not allowed.
Now, consider if a procedure definition includes extra spaces like "void f ( T , int )". tokens: ["void","f","(","T",",","int",")"]; param_types = ["T","int"].
Now, check: token slice tokens[3:-1] is from index3 to -1: tokens indices:0=void,1=f,2=(,3=T,4=,,5=int,6=). So slice [3:6] = [T, ',', int]; filter commas -> [T,int].
Good.
Now, what about if the procedure name contains digits: "void foo1 (int)" tokens: ["void","foo1","(","int",")"]; param_types = ["int"].
Now, code should handle.
Now, think about performance: tokenization is O(len(line)) per line, fine.
Now, edge: the tokenization function might produce tokens incorrectly if there are multiple consecutive special characters. But not present.
Now, implement and test with example.
Potential bug: In procedure definition, tokens[3:-1] might include tokens that are not types if there are extra spaces? For instance, if there is a space after '(' and before first type, but tokenizer skips spaces, so the token after '(' is the type. So no extra tokens.
But if there is something like "void f ( (int) )"? Not allowed.
Now, final answer.
However, I want to consider one more subtlety: The problem says "Only the specified variables are used in procedure calls." So all var_names are known.
Now, think about the possibility of procedures with same name but different parameter counts. Our condition len(param_types)==len(var_names) ensures correct count.
Now, output is straightforward.
Now, we can also compress procedures by name to improve but not needed.
Now, one more test: n=1000, each procedure has up to 5 types, scanning for each call: 1e6 comparisons * 5 = 5e6, trivial.
Now, I'll produce final answer.
But wait: The problem statement includes "The names of variables and procedures are non-empty strings of lowercase English letters and numbers with lengths of not more than 10 characters." So names are lowercase and numbers only. "T" is uppercase, so not a name.
Now, also note: In the variable declaration, the type is either "int", "string", "double". So they are all lowercase. Generic "T" is uppercase. So case-sensitive.
Now, in matching, we compare param_type (which can be "T" uppercase) and var_type (lowercase). So equality with var_type works: if param_type == 'T' or param_type == var_type. Since var_type is lowercase, param_type being uppercase only matches if it's 'T', otherwise it would be lowercase type. So correct.
Now, we should be careful about type comparison: "int" vs "int" works.
Now, all good.
Now, produce final code.
But I'd like to check for a potential issue with the tokenization: In some languages, the string may contain a comma inside a type? Not here.
Thus final.
One more thought: In the procedure definition, after tokenization, tokens[0] should be "void". But what if there are extra spaces before void, we stripped, so first token is "void". But if the line started with spaces, we stripped, so first token is "void". Good.
But what if the line is like " void f(int)"? After strip, "void f(int)", first token "void". Good.
Now, let's also consider an edge case where the procedure name is something like "void" but there is a space after void? Actually it would be "void void (int)". Then tokens: ["void","void","(","int",")"]. So the first token is "void" (keyword), second token is "void" (name). That's okay.
Now, if we try to parse param_types: tokens[3:-1] -> tokens[3] is "int"? Let's see: tokens indices: 0="void",1="void",2="(",3="int",4=")". So tokens[3:-1] = tokens[3:4] = ["int"]; good.
Now, call: "void(a)"? That would be a call to procedure named "void" with variable a. So tokenization: tokens = ["void","(","a",")"]; proc_name = "void". That matches the procedure with name "void". Good.
Now, all fine.
Now, final answer.
But double-check tokenization of a call with multiple variables: "f(a,b,c)" tokens: ["f","(","a",",","b",",","c",")"]; var_names = [a,b,c].
Now, in param_types extraction, we used tokens[2:-1] which includes tokens from index 2 (which is '(') to last -1 exclusive. For call: tokens[2] is '('? Actually tokens[0] is name, tokens[1] is '('? Wait earlier we said tokens[1] is '('? Let's re-evaluate call tokenization: For "f(a,b)", tokenizer: reads "f" -> token; then '(' -> token; then "a" -> token; then ',' -> token; then "b" -> token; then ')' -> token. So tokens: index0="f", index1="(", index2="a", index3=",", index4="b", index5=")". So var_names should be tokens at positions that are not '(' or ')' or ','. So we need to collect from tokens[2:-1] but excluding commas. That gives indices 2,4? Actually slice [2:5] (since -1 index is 5, exclusive) gives tokens[2], tokens[3], tokens[4] -> "a", ",", "b". Filter commas yields ["a","b"]. Good.
But what about when there is a space after '('? e.g., "f( a , b )". tokens: ["f","(","a",",","b",")"]; same.
Now, what about when there is a space between name and '('? e.g., "f (a,b)". tokens: ["f","(","a",",","b",")"]; same.
Now, for call, tokens[0] is name; tokens[1] is '('; tokens[2] onward are parameters and commas. So our slice from 2 to -1 is correct.
But what about if there is a space before '('? Actually tokenizer skips spaces, so after name token, next token is '('.
Thus fine.
Now, the only possible issue: If there is a call like "f()" (no parameters) which is not allowed but if it were, tokens: ["f","(",")"]; then tokens[2:-1] yields tokens[2]? tokens indices: 0="f",1="(",2=")". slice [2:-1] -> start=2, end=-1 (index of ')' is 2? Actually tokens length 3: indices 0,1,2. -1 index is 2. So slice [2:-1] means start=2, end=2, empty. So var_names = [] which is correct for zero parameters. But since t>=1, not needed.
Now, verify procedure definition slice similarly: tokens[2] = '('; tokens[3] = first type; tokens[-1] = ')'. So tokens[3:-1] is correct for t>=1.
Now, but is it always that the '(' token is at index 2? Suppose the procedure name is "void" and there is a space after name and '('? tokens: ["void","void","(","int",")"] -> index2='(', index3='int'. So yes.
Now, consider a weird scenario: "void f ( int )" tokens: after stripping, "void f ( int )" but with spaces. Tokenizer: after "void", then "f", then '(', then "int", then ')'. So index2 = '('.
Thus all good.
Now, implement final code.
But there's a nuance: The input lines could have spaces before the keyword void? They said spaces may be before and after keyword void. So there could be spaces at the beginning of line; we strip them, so they are removed.
Now, final code is ready.
But I want to also consider using Python's re for tokenization? Not needed.
Now, test with provided examples:
Example1:
Input as exactly as given. We'll simulate.
We'll include some extra spaces. Should work.
Now, potential bug: In tokenization, we treat any character that is not space and not in '(),' as part of a token. But what if a type or name includes underscore? They said only lowercase letters and numbers, so no underscore. So fine.
Now, might there be a type like "long"? No, only int, string, double.
Now, check that the tokenizer splits correctly when there is a digit in name: e.g., "foo123". It will be one token.
Now, for variable declaration line: we used .split() which splits on any whitespace. That's fine even if there are multiple spaces.
Now, test with an additional case to ensure we handle uppercase T correctly.
Now, confirm that we treat T as generic only when it's exactly "T". Not "t". So okay.
Now, finalize.
I will provide the solution with explanation.
But in the final answer, we only need to output code.
But let's see if there are any hidden pitfalls:
-
The procedure definitions can have up to 5 parameters, but we don't need to enforce that limit.
-
The variable definitions: only types: int, string, double. So var_type is one of these.
-
In matching, we need to ensure we access var_type[vn] exists. It will.
-
There might be a procedure call to a name that doesn't exist; we will count 0.
Now, additional: Could there be a procedure with parameter type "T" that matches any variable type, but also there could be a procedure with exact type like "int". Both can match for an int variable. So we count both.
Now, check if the generic T could match also if the variable type is something else? Yes, it always matches.
Now, consider the possibility of ambiguous parsing: The tokenizer for calls might also include extra parentheses? Not present.
Now, check if there is a case where a variable name is "void"? That is lowercase "void". Since variable names are lowercase, "void" is allowed. Then a call might be "f(void)" which would be a variable named "void". That would be tokenized as: tokens: ["f","(","void",")"]; var_names = ["void"]; we then look up var_type["void"]. That's okay. So no conflict.
Now, does our parsing of procedure definitions treat "void" as keyword? Yes, we ignore first token.
Now, what if a procedure name is "int"? That's lowercase, allowed. Then a call "int(a)" would be parsed as procedure name "int". That's fine. But note that variable names also could be "int"? Since variable names are distinct and could be "int"? Possibly, but then call "int(int)" would be ambiguous? Actually no, because the first token is the procedure name, then '(' then variable name "int". So that is a valid call to procedure named "int" with variable named "int". That's okay. No conflict.
Now, note: The problem states that variable names are distinct and non-empty strings of lowercase letters and numbers. So "int" is valid variable name. So we must not confuse type names with variable names. In our matching, we only use var_type dict, which maps variable names to types. So that's fine.
Now, one more: The variable type could be "string"? Yes, which is also a type. But variable name could be "string"? Yes, possible. Then call "f(string)" would be a call with variable named "string". That's okay.
Now, all good.
Now, think about the possibility of a procedure definition with name same as a type? It's allowed. But in parsing, we treat first token as keyword, second as name. So if the name is "string", we will treat it as name. Later when we parse calls, the first token is the procedure name, so if a call is "string(x)", it refers to a procedure named "string". If there's also a variable named "string", that's fine.
Now, any other considerations? The problem might have multiple test cases? No, it's a single input.
Now, final code.
I'll write the final solution in Python.
Wait, there's a nuance: In the procedure definition, there might be a space before the opening parenthesis, and also there might be a space after the closing parenthesis? Our tokenizer would ignore spaces, but we need to ensure that the last token is ')', but there might be spaces after ')', which are ignored.
Now, consider line: "void f ( int , T ) " after strip, trailing spaces removed, becomes "void f ( int , T )". So last token is ')'.
Thus fine.
Now, I'll write final solution with tokenizer function inside.
But we must ensure that we handle possible input where there are empty lines before the integer lines? The first integer is read with input().strip() and converted. If there's a blank line before, the first call to input() will read that blank line. But problem doesn't mention blank lines. Usually not. However to be safe, we could read until we get a non-empty line for each integer. But I think it's not needed.
But I'll incorporate robust reading: After reading n_line, we could do while n_line.strip() == "": n_line = input() (but then we risk infinite loop if at EOF, but there is input). I'll add while loops to skip empty lines for the first line of each group? But simpler: just read and strip, and assume it's non-empty. I'll trust the judge.
Given it's Codeforces style problem? Might be from Codeforces. Usually there are no blank lines. So fine.
Now, code.
But I'd like to optimize by grouping procedures by name: We can create a dict: proc_by_name = {} mapping name to list of param_types. But we need to count all matching. Could just iterate over all procedures each time. But to be safe with 1000*1000, it's fine.
But if we want to be slightly more efficient, we can group:
from collections import defaultdict procedures_by_name = defaultdict(list) for name, params in procedures: procedures_by_name[name].append(params)
Then for each call, we only iterate over those with same name. That reduces scanning. But not necessary.
We'll implement grouping to be safe and maybe faster. But O(nk) is fine. However n and k up to 1000, and each procedure may have many parameters up to 5, so 10001000*5 = 5,000,000 operations, which is fine for Python.
But we should also consider the tokenization overhead. Still fine.
I'll implement with list.
But to be neat, I'll use grouping.
Let's do:
proc_dict = {} or defaultdict(list) But careful: The procedures list is initially stored as (name, param_types). We'll do:
procs_by_name = defaultdict(list) for name, param_types in procedures: procs_by_name[name].append(param_types)
Then in calls:
candidates = procs_by_name.get(proc_name, []) for param_types in candidates: if len(param_types) != len(var_names): continue then match.
This reduces iterations.
We'll do that.
Now, final code:
import sys from collections import defaultdict
def tokenize(s): tokens = [] i = 0 n = len(s) while i < n: if s[i].isspace(): i += 1 continue if s[i] in '(),': tokens.append(s[i]) i += 1 continue j = i while j < n and not s[j].isspace() and s[j] not in '(),': j += 1 tokens.append(s[i:j]) i = j return tokens
def main(): input = sys.stdin.readline
n = int(input().strip()) procs_by_name = defaultdict(list) for _ in range(n): line = input().strip() tokens = tokenize(line) name = tokens[1] param_types = [tok for tok in tokens[3:-1] if tok != ','] procs_by_name[name].append(param_types) m = int(input().strip()) var_type = {} for _ in range(m): typ, name = input().strip().split() var_type[name] = typ k = int(input().strip()) out = [] for _ in range(k): line = input().strip() tokens = tokenize(line) proc_name = tokens[0] var_names = [tok for tok in tokens[2:-1] if tok != ','] cnt = 0 for param_types in procs_by_name.get(proc_name, []): if len(param_types) != len(var_names): continue match = True for pt, vn in zip(param_types, var_names): vt = var_type[vn] if pt != 'T' and pt != vt: match = False break if match: cnt += 1 out.append(str(cnt)) sys.stdout.write('\n'.join(out))if name == "main": main()
Now, test with examples.
But wait: In procedure definition parsing, we assumed tokens[1] is name. But what if the line had extra spaces and the tokenizer produced tokens where after void there is maybe '('? That would be weird. But trust.
Now, test with example1:
n=4. Build procs_by_name: f: [[int,T], [T,T]] foo123: [[int,double,string,string]] p: [[T,double]] Then variables: a->int, s->string, x123->double. Calls: f(a,a): candidates for f: two. Both length 2. Check: first: int matches a (int), T matches -> ok; second: T,T -> ok -> cnt=2. f(s,a): int,T fails first param int vs string; T,T ok -> cnt=1. foo(a,s,s): candidates for foo -> none -> cnt=0. f(s,x123): int,T fails; T,T ok -> cnt=1. proc(a): candidates for proc -> none -> 0.
Matches.
Example2 similarly.
Now, final answer.
But before finalizing, I want to test with a custom case where procedure name appears with multiple param lists. Works.
Now, I think solution is correct.
Now, about time: tokenization loops over each character; each line length <=100, so overhead minimal.
Now, potential bug: When we parse param_types, we used tokens[3:-1] and filtered commas. But consider a procedure with one parameter: tokens = ["void","f","(","T",")"]; tokens[3:-1] = tokens[3:4] = ["T"]; filter commas -> ["T"]; ok.
But consider a procedure with multiple parameters but maybe there is a comma at the end of the slice? Not, because slice excludes the ')'.
But what if there is a comma after the last parameter before ')'? Like "void f(T,)"? Not allowed but if it were, tokens: ["void","f","(","T",",",")"]; tokens[3:-1] = tokens[3:5]? Actually tokens indices:0=void,1=f,2=(,3=T,4=,,5=). slice 3:-1 -> index 3,4 -> ["T",","] filter commas -> ["T"]; still ok, but the comma would be filtered. But there would be an extra comma that is not separating two types, so it's malformed, but it's not in input.
Thus fine.
Now, we also need to be careful about the fact that the type list could have a trailing space before ')', but tokenizer will treat ')' as separate.
Now, is there any case where the tokenizer could produce an empty token? For instance, if there are two consecutive special characters without spaces? e.g., "()", but not used.
Now, final answer.
I'll produce the final solution in code.
But wait: The problem statement includes "The lines describing the variables, template procedures and their calls may contain spaces at the beginning of the line and at the end of the line, before and after the brackets and commas. Spaces may be before and after keyword void." So we are handling that.
Now, code.
One more nuance: In the procedure definition, after void, there could be spaces, but the name could be "void"? That would be tokenized as second token "void". Then we add to dict. In calls, if there is a call to procedure "void", the tokenizer will produce first token "void". But then we have to differentiate that from a variable named "void"? No, it's a procedure name.
Now, if there is a variable named "void", and we call "f(void)", it's fine.
Now, all set.
Now, output each number on separate lines.
Now, final answer.
But I recall that in Codeforces problems, they sometimes require fast I/O. Our input reading with sys.stdin.readline should be fine for 1000 lines.
Now, I'll also consider using .split() for variable lines and tokenizer for others.
Now, final code as above.
I think that's ready.
Now, write final answer with explanation.
But the problem: The user said "Recently, Valery have come across ...". This is a problem from Codeforces, likely "Template Procedure" or something. So answer must be code.
Now, I'll produce final answer with explanation and code.
But as ChatGPT, I need to output the final answer: code only? The user said "Write a solution in python". Usually they expect the code. So I'll provide the solution code with comments.
But the instructions: "You are an AI... Provide the final answer." I'll give a thorough explanation then code.
In the response, I'll include a brief explanation of approach and then the code.
I'll also ensure the code is properly formatted.
Thus final. ```python
import sys from collections import defaultdict
def tokenize(s: str): """Split a line into tokens, treating parentheses and commas as separate tokens.""" tokens = [] i = 0 n = len(s) while i < n: if s[i].isspace(): i += 1 continue if s[i] in '(),': tokens.append(s[i]) i += 1 continue j = i while j < n and not s[j].isspace() and s[j] not in '(),': j += 1 tokens.append(s[i:j]) i = j return tokens
def main(): input = sys.stdin.readline
# ---- read template procedures ---- n = int(input().strip()) procs_by_name = defaultdict(list) # name -> list of parameter type lists for _ in range(n): line = input().strip() toks = tokenize(line) name = toks[1] # the name is the second token # parameters are between '(' and ')', commas are filtered out param_types = [t for t in toks[3:-1] if t != ','] procs_by_name[name].append(param_types) # ---- read variables ---- m = int(input().strip()) var_type = {} for _ in range(m): typ, name = input().strip().split() var_type[name] = typ # ---- process calls ---- k = int(input().strip()) out = [] for _ in range(k): line = input().strip() toks = tokenize(line) proc_name = toks[0] var_names = [t for t in toks[2:-1] if t != ','] cnt = 0 for param_types in procs_by_name.get(proc_name, []): if len(param_types) != len(var_names): continue match = True for pt, vn in zip(param_types, var_names): vt = var_type[vn] if pt != 'T' and pt != vt: match = False break if match: cnt += 1 out.append(str(cnt)) sys.stdout.write('\n'.join(out))if name == "main": main()