After failing to qualify for the National Olympiad in Informatics because of his childish mistake, Xorin decided to build a tool that will ensure he never gets a Memory Limit Exceeded feedback ever again.
When Xorin writes a new source file, he wants to be able to type into the tool a code sequence corresponding to his declaration of variables. The tool should then interpret the sequence and output the total memory allocated for said variables.
A C variable declaration looks like TYPE VAR1,VAR2,..,VARn
, where
TYPE
is the type of the variable:char
(1 byte),short
(2 bytes),int
(4 bytes), each of them optionally preceded byunsigned
VARk
looks likeNAME
(a scalar) orNAME[DIM1][DIM2]..[DIMn]
(a N-dimensional vector). A vector needs as much memory asDIM1 * DIM2 * ... * DIMn
scalars of the same type.
int n,m
, unsigned short vec[5][100],othervec[105],randomvar
. Input
A list of C variable declarations in the format above, separated by newlines. The input ends with a newline character.Output
A list of integers separated by newlines. Thei
th integer is the amount of memory needed to store the variabled declared on the i
th line of the input Notes
- Each input line is at most 100 characters long
- Variable names cannot be empty and may only contain lowercase letters
- On each line, there are no spaces after the first letter of the first variable name
- All numbers in the output are smaller than 109
Sample
Input | Output |
---|---|
char marint,a[20] int b[2],c[1],d,e unsigned int d short a,b,c,d[2][2][2],munsigned | 21 20 4 24 |
An exercise in string splitting.
C solution (Marius Gavrilescu)
1 #include<stdio.h> 2 #include<stdlib.h> 3 #include<string.h> 4 5 char decl[105], *var[105], delim[105] = "][\n"; 6 7 int main(void){ 8 for(char c = 'a' ; c <= 'z' ; c++) // Construct the delimiter containing 9 delim[c - 'a' + 3] = c; // all letters and ], [, newline 10 11 while(!feof(stdin)){ // While we aren't done 12 fgets(decl, 105, stdin); // Read a declaration into decl 13 scanf(" "); // Trigger EOF if necessary 14 char *last_space = strrchr(decl, ' '); // Find the last space character 15 *last_space = 0; // Split the string at this char 16 char *type = decl, *vars = last_space + 1; // into the type and a string of vars 17 18 int varn = 0, sum = 0; 19 var[0] = strtok(vars, ","); // Split the string of vars into an array 20 while((var[++varn] = strtok(NULL, ","))); 21 22 for(int i = 0 ; i < varn ; i++){ // For each variable 23 int nr = 1; // nr is the dimension of the variable (number of elements) 24 char *part = strtok(var[i], delim); // Split it into parts using delim 25 while(part) { // Each part is a dimension of the vector 26 nr *= atoi(part); // Multiply nr by the dimension 27 part = strtok(NULL, delim); 28 } 29 sum += nr * 4; // int is the default type and has 4 bytes 30 } 31 32 if(strstr(type, "short")) 33 sum /= 2; 34 if(strstr(type, "char")) 35 sum /= 4; 36 printf("%d\n", sum); 37 } 38 39 return 0; 40 }
Perl solution (Marius Gavrilescu)
1 #!/usr/bin/perl 2 use v5.14; 3 use warnings; 4 5 use List::Util qw/reduce sum/; 6 7 while (<>) { 8 my ($type, $vars) = /(.*) ([^ ]+)$/; # Split the declaration into type and string of vars 9 my @vars = split ',', $vars; # Split the string of vars into an array 10 y/0-9]//cd for @vars; # Remove all characters from variables except for digits and ] 11 my $result = sum map { reduce { $a * $b } 4, split ']' } @vars; # Split each var into dimensions, multiply the dimensions together and sum the results 12 $result /= 2 if $type =~ /short/; 13 $result /= 4 if $type =~ /char/; 14 say $result; 15 }