[UVa] 471 - Magic Numbers

Method: Searching, String checking, Bruteforce Solved during ACM Workshop 2012 at my University.

#include <set>
#include <map>
#include <list>
#include <cmath>
#include <ctime>
#include <deque>
#include <queue>
#include <stack>
#include <cctype>
#include <cstdio>
#include <string>
#include <vector>
#include <cassert>
#include <cstdlib>
#include <cstring>
#include <sstream>
#include <iostream>
#include <algorithm>
#include <climits>
#include <clocale>


using namespace std;


typedef long long lint;

bool cmp(pair<lint,lint> a, pair<lint,lint> b) {
  
  return (a.first<b.first);
  
}


bool check(lint n) {
  
  bool ver[20];
  char buf[100];
  lint len;
  for (int i=0 ; i<=20 ; i++) ver[i]=false;
  
  sprintf(buf,"%lld",n);
  
  len = strlen(buf);
  
  if (len>10) return false;
  
  for (int i=0 ; i<len ; i++) {
 if ( ver[ buf[i]-'0' ] == true ) return false;
 else ver[ buf[i]-'0' ] = true;
  }
  return true;
}


int main( void ) {
  
  lint kase, n, i, j, numerator, x, k;
  bool first=true, dis, ver[10];
  
  vector< pair<lint,lint> > lst;
  
  scanf("%lld",&kase);
  
  while (kase--) {
 
 scanf("%lld",&n);
 
 if (n==0) continue;
 
 lst.clear();
 
 for (i=1 ; (n*i)>=0 ; i++) {
   
   numerator = n*i;
   
   x = numerator;
   
   for (k=0 ; x ; k++, x/=10) if (k>10) break; // if length of the current
   if (k>10) { break; }       // numerator exceeds 10 the loop ends
   
   if (check(i) && check(numerator)) 
  lst.push_back(make_pair(numerator,i));

 }
 
 sort(lst.begin(),lst.end(),cmp);
 
 if (!first) putchar('\n');
 first = false;
 for (i=0 ; i<lst.size() ; i++) {
   printf("%lld / %lld = %lld\n",lst[i].first,lst[i].second,n);
 }
 
  }
  
  return 0;
  
}

[C++] Bellman Ford Implementation

Bellman-Ford is a Single Source Shortest Path (SSSP) detection algorithm. I implemented this one using a new kind of approach to coding (new for me). I used a nested class implementation. The whole BFord algorithm is packed with it's data structure in an object. The edges are also implemented using an internal class in the object. I never did nested class before this. Looks awesome.

#include <cstdio>
#include <vector>

#define INF (1<<31 - 1)
#define NIL -1

using namespace std;

class bford {
  
public:
  
  class edge {
  public:
 int u, v, w;
  };
  
  int nVertex;
  int *d, *p;
  vector<edge> elist;
  
  bford( ) {
 d = new int[0];
 p = new int[0];
 elist.clear();
  }
  
  bool function( int s, int nVertex ) {
 
 d = new int[(const int)nVertex+1];
 p = new int[(const int)nVertex+1];
 
 int i, j, w, u, v;
 // init_single_source( s ) {
 for (i=0 ; i<=nVertex ; i++) {
  d[i] = INF;
  p[i] = NIL;
 }
 d[s] = 0;
 // }
 
 for (i=0 ; i<nVertex-1 ; i++) {
  for ( j=0 ; j<elist.size() ; j++) {
   // relax( elist[j].u, elist[j].v, elist[j].w ) {
   u = elist[j].u;
   v = elist[j].v;
   w = elist[j].w;
   
   if (d[v] > d[u]+w) {
    d[v] = d[u]+w;
    p[v] = u;
   }
   // }
  }
 }
 
 for (i=0 ; i<elist.size() ; i++) {
  if ( d[ elist[i].v ] > d[ elist[i].u ] + elist[i].w ) {
   return false;
  }
 }
 return true;
  }

};

int main( void ) {
  
  int i, u, v, w, nVertex, nEdge;
  
  bford grp;
  scanf("%d",&nVertex);
  
  scanf("%d",&nEdge);
  
  for (i=0 ; i<nEdge ; i++) {
 scanf("%d %d %d",&u,&v,&w);
 grp.elist.push_back(bford::edge{u,v,w});
  }
  
  printf("%s\n",(grp.function( 1, nVertex )?"True":"False"));
  
  for (i=1 ; i<=nVertex ; i++) {
 printf("%d - %d\n",i, grp.d[i]);
  }
  
  
  return 0;
  
}

[UVa] 627 - The Net

Pretty simple and somewhat forced towards the solution.
Counting number of nodes and shortest path. You have to print the path too.
It's simply BFS. The pi[ ] array comes handy to print the path.

Method: BFS (Use the pi array)

#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <queue>
#include <algorithm>

#define WHITE 0
#define GREY 1
#define BLACK 3
#define INF 0
#define NIL -1

using namespace std;

bool color[400], adj[400][400];
int d[400], p[400];
char in[100000];

bool bfs( int s, int des, int n ) {
 int u, v;
 for (u=0 ; u<=300 ; u++) {
  color[u] = WHITE;
  d[u] = INF;
  p[u] = NIL;
 }
 color[s] = GREY;
 d[s] = 0;
 p[s] = NIL;
 
 queue<int> q;
 q.push(s);
 while (!q.empty()) {
  u = q.front();
  q.pop();
  for (v=1 ; v<=n ; v++) {
   if (adj[u][v] && color[v]==WHITE) {
    color[v] = GREY;
    d[v] = d[u]+1;
    p[v] = u;
    q.push(v);
    if (v == des) {
     return true;
     
    }
   }
  }
  color[u] = BLACK;
 }
 return false;
}

void print_path(int v) {
 int i, j, pr[1000];
 for (i=v, j=0 ; i>0 ; i=p[i], j++) pr[j] = i;
 for (--j ; j>0 ; j--) printf("%d ",pr[j]);
 printf("%d\n",pr[j]);  //|Last one can't have
}    //|can't have blank space
    //|after it

int main( void ) {


 int i, j, c, n, u, v, nodes, conn;
 char *p;

 while ( scanf("%d",&nodes) == 1 ) {
  getchar(); // Back off for gets()
  
  for (i=0 ; i<=300 ; i++) { 
   for (j=0 ; j<=300 ; j++) adj[i][j] = false;
  }
  
  n = nodes;
  
  while (nodes--) {
   gets(in);
   p = strtok(in,"-,");
   sscanf(p,"%d",&i);
   p = strtok(NULL,"-,");
   while (p) {
    sscanf(p,"%d",&c);
    adj[i][c] = true; //|Connections are !bidirectional
    p = strtok(NULL,"-,");
   }
  }
  
  
  scanf("%d",&conn);
  
  printf("-----\n");
  
  for (i=1 ; i<=conn ; i++) {
   scanf("%d %d",&u, &v);
   if (bfs(u,v,n)) {
    print_path( v );
   } else {
    printf("connection impossible\n");
   }
  }
 }
}

Setup Code::Blocks Nightly on Windows

Install MinGW GCC Port on Windows.
1. Just go to this address [ http://sourceforge.net/projects/mingw/files/Installer/mingw-get-inst/ ]
2. Select the topmost link that looks (almost) like mingw-get-inst-XXXXXXXX

3. Download the exe you see there and execute it on your machine keeping the Internet connected. Everything else is pretty self explanatory.

Now for the nightlies of Code::Blocks.
1. Go to [ http://forums.codeblocks.org/ ]
2. Look for the section called Nightly Builds, go into it.
3. The latest nightly is the first one, click it.
4. Every nightly release has 3 links. Links to the 2 DLLs and the zip file containing the release. Download all of them (unless you've done this before and know exactly what you can ignore here).
5. Extract all of them in the same directory. If they are in folders bring them out.
6. If the extraction went well, executing codeblocks.exe won't be any problem.
7. After codeblocks.exe opens, Open this section Settings > Compiler. If you can't find it, look at the top row of options in the Code::Blocks window.
8. In the Window that opens you'll see some tabs slightly after the first options. Click on the fourth one called Toolchain Executables.
9. Look for the button called "Auto Detect". Click it. If it reports success then you're done. Otherwise click on "..." that is to the left of "Auto-Detect" and browse to the folder where you've installed MInGW.

I hope everything went well. To check if your compiler is working fine just compile a "Hello World" program. :D Any questions are welcome.

[UVa] 12032 - The Monkey and the Oiled Bamboo

A very simple problem but the conditions have to be understood very carefully.

Method: Simple, on the fly.

Initialize the value of k with the first jump (from ground to first rung)
If (jump == capacity)
    capacity decreases by 1
If (jump > current capacity)
    Check if jump == k, increase k by 1. Reset capacity to k
    Check if jump > k, set k = jump, Reset capacity to k-1
    Check if jump < k increase k by 1. Reset capacity to k

#include <stdio.h>

typedef int lint;



lint val[100000 + 10];

int main( void ) {
 
 lint n, i, k, v, kase=1, kounter;
 
 val[0]=0;
 
 scanf("%d",&kounter);
 
 while (kounter--) {
  scanf("%d",&n);
  
  for (i=1 ; i<=n ; i++) {
   scanf("%d",&val[i]);
  }
  
  k = val[1];
  v = val[1];
  
  for (i=0 ; i<n ; i++) {
   if (val[i+1]-val[i]>v) {
    if (val[i+1]-val[i]==k) {
     k++;
     v=k;
    } else if (val[i+1]-val[i]>k) {
     k=val[i+1]-val[i];
     v=k-1;
    } else {
     k++;
     v=k;
    }
   } else if (val[i+1]-val[i]==v) {
    v--;
   }
   
  }
  printf("Case %d: %d\n",kase++,k);
 
 }
 return 0;
}

How to use UVa Online Judge

Many of us have enormous interest in practicing programming using online judge sites but sometimes get stuck when it comes to using them. In this tutorial, I've tried to explain the usage of one of the most popular OJ sites, The UVa Online Judge.

Let's get started.

First of all get an account.
1. Go to http://uva.onlinejudge.org
2. On the panel situated on the left side of the page look for the link "Register"

3. Click that you'll reach a page where you have to supply some account information in order to get registered. Look carefully at the last field, put 00000 in it.

4. After you've confirmed your email address and all other formalities you can come back and Log in to your account. Do so using the panel on the left.
5. Now for a test drive, let's submit a code. First go to "Browse Problems" on the left panel slightly to the bottom.

6. Here comes a list of Categories that the problems are organized in. We will browse through the volumes of Contest Problems. These sets are organized according to Contests. We use this because after a contest finishes, we get the problems of that contest in here together easily.

7. Click the volume you desire to use, I open the last one because this set has the latest contest problems.

8. We're going to submit a code for the problem "Calculating Yuan Fen". I'm not going to explain it here since that's not what I'm trying to show you.

9. Look on the left side of the problem name, it's the code of the problem, 12414. If you submit a solution, you need this code. You can also click on the problem and use the "Submit" button inside. Since I use the Quick Submit method a lot, I'm showing you that. On the left side look for the link "Quick Submit"

10. The Quick Submit window is pretty easy to understand.
a. Put the problem code in the first field
b. Choose which language you're coding in (The language you used to write the solution)
c. Paste your code in the BIG code field or you can choose the code file itself.
d. Click on "Submit"

11. After the submission is complete you'll have to click on the "My Submissions" link on the left side to see if the solution was successfully submitted and if so, was it Accepted or not. Since I didn't post an actual working solution, I got Wrong Answer. Hope that won't be the same with you :)

That's it, the basics. Start exploring the site and examining the different sections. You'll soon find that it's an awesome experience. Solving problems using programming methods is something only a few lucky people get to enjoy. And congratulations, you're now one of them :D





UVa is not the end. There are much better (resourcefully) sites that can help you enhance your programming skills. I showed UVa because most people start here. I don't think you'll need to understand anymore to start on other sites. Only TopCoder might seem a bit tricky initially. If you need any help, comment here or contact me on Facebook. Happy Coding.

[UVa] 12414 - Calculating Yuan Fen

Method: Simulate it, nothing special. But don't handle with strings. TLE for sure then.

#include <stdio.h>

int y(char *s, int st) {
 int val[100], stor[100], v, i, j, k=0;
 for (i=0 ; s[i] ; i++) {
  v = s[i]+st-'A';
  for (j=0 ; v ; j++, v/=10) {
   stor[j] = v%10;
  }
  for (--j ; j>=0 ; j--, k++) {
   val[k] = stor[j];
   
  }
 }
 
 
 while (k>2) {
  for (i=0, j=0 ; j<k ; j++, i++) {
   val[i] = (val[j]+val[j+1])%10;
  }
  if (k==4) {
   if (val[0]==1 && val[1]==0 && val[2]==0) {
    return 100;
   }
  }
  k--;
 }
 return 0;
}

int main( void ) {
 char input[20];
 int i, found, result;
 while ( gets(input) ) {
  
  for (i=1, found=0 ; i<=10000 && found==0 ; i++) {
   result = y(input, i);
   if (result == 100) {
    found = 1;
   }
  }
  if (found == 1) {
   printf("%d\n",i-1);
  } else {
   printf(":(\n");
  }
 }
 return 0; 
}

How to install Code::Blocks Nightlies in Ubuntu

I got into a problem trying to do this. Here's the place I discussed it.
[ http://forums.codeblocks.org/index.php/topic,16342.0.html ]

This tutorial works for any version of Linux that has Ubuntu. Apparently, I did all this in Linux Mint 12 (Lisa). The only repository discussed herer is Jens'. But this guy doesn't bother updating his repo-homepage. So, I had a crashed Lisa installation trying to be smarty pants. In the end, found several scattered threads where he told how to install the nightlies (added them up myself).

Now.

1. First of all you have to add these 2 lines to your sources.list

    deb http://apt.jenslody.de/ any main
    deb-src http://apt.jenslody.de/ any main

But wait, there are some modifications for different types of versions.
    Replace main with:
                release [For the usual releases]

2. Add another line for wxWidgets to your sources.list
   
    deb http://apt.wxwidgets.org/ squeeze-wx main

3. sudo apt-get update

4. Now install using command: sudo apt-get install codeblocks codeblocks-contrib


And to upgrade to the latest Nightly when in comes out

    sudo apt-get update
    sudo apt-get remove codeblocks codeblocks-contrib
    sudo apt-get install codeblocks codeblocks-contrib

Programming Challenges [Audio Lectures]

This page has some useful resource that are based on the book "Programming Challenges" that is very popular.

[http://www.cs.sunysb.edu/~skiena/392/audio/]

Just for the note.

[UVa] 12444 - Bits & Pieces

Method: Bitmasking, Bit manipulation
Trick: Analyze the problem a bit with the given Samples.
When for a particular bit
C = 1 & D = 1, obviously both the numbers have to have 1 in that position
C = 0 & D = 1, if this case occurs for the first time make the bit in B = 1 & A = 0, otherwise B = 0 & A = 1. This ensures |B-A] Minimality & A<=B.
No other combination is possible.

/* Faith-M */

//Headers
#include <set>
#include <map>
#include <list>
#include <cmath>
#include <ctime>
#include <deque>
#include <queue>
#include <stack>
#include <cctype>
#include <cstdio>
#include <string>
#include <vector>
#include <cassert>
#include <cstdlib>
#include <cstring>
#include <sstream>
#include <iostream>
#include <algorithm>
#include <climits>
#include <clocale>
//Defines
#define pow2(i) (1<<i)
#define bit(i) (1<<i)
#define isOdd(i) (i&1)
#define isEven(i) (!(i&1))
#define isPrime(i) ((i==2) || ((i&1) && !pTest[i])) //pTest has to be the bool array's name
#define sz(i) i.size()
#define vec(type,name) vector< type > name
#define rep(i,a,b) for(int i=a ; i<=b ; i++)
#define swap(type,a,b) {type t=a; a=b; b=t;}
#define sum(a,n) ( (n*(n+1)/2) - (a-1)*a/2 )
#define iscap(i) (i>='A'&&i<='Z')
#define issmall(i) (i>='a'&&i<='z')
#define isnum(i) (i>='0'&&i<='9')
#define issymbol(i) (!(i>='a'&&i<='z') && !(i>='A'&&i<='Z') && !(i>='0'&&i<='9'))
#define mk(i,j) make_pair(i,j)
#define ERROR 1e-11
//Type Defs
typedef long long lint;
typedef unsigned long long ulint;
typedef long double ldouble;

using namespace std;

pair <lint, lint> find( lint c, lint d )
{
    lint a=0, b=0, bit_c, bit_d;
    bool fbit=true;
    int i;

    for (i=31 ; i>=0 ; i--)
    {
        if ((1<<i)&c) bit_c = 1;
        else bit_c = 0;

        if ((1<<i)&d) bit_d = 1;
        else bit_d = 0;

        if (bit_c == 1 && bit_d == 1)
        {
            a = a | (1<<i);
            b = b | (1<<i);
        } else if (bit_c == 0 && bit_d == 1)
        {
            if (fbit == true)
            {
                b = b | (1<<i);
            } else
            {
                a = a | (1<<i);
            }
            fbit = false;
        }
    }

    if ( (a&b) == c && (a|b) == d ) return make_pair(a,b);
    else return make_pair(-1,-1);

}

int main()
{
 //freopen("input.txt","r+",stdin);
 //freopen("output.txt","w+",stdout);/**/

 //    TEST CASE     //
 int kase=1, kounter=1;/**/

 lint c, d;

    scanf("%d",&kase);
    while (kase--)
    {
        cin >> c >> d;

        pair <lint, lint> res = find(c,d);

        if (res.first == -1) printf("-1\n");
        else cout << res.first << " " << res.second << endl;
    }


 return 0;
}

[UVa] 729 - The Hamming Distance Problem

Method: Bruteforce, all combinations. Permutation. Backtracking.
Trick: Finding all the results is pretty easy using any Basic Backtracking code but you have to sort them. So? Don't work with 1s work with 0s. Or just use next_permutation( ) from STL, your choice. Optimizations: Pregenerating all combinations might give you a better runtime, didn't try it.

Sample Input:

1

16 7

Sample Output:

Please find it using UVA Toolkit (www.uvatoolkit.com)

/* Faith-M */

//Headers
#include <set>
#include <map>
#include <list>
#include <cmath>
#include <ctime>
#include <deque>
#include <queue>
#include <stack>
#include <cctype>
#include <cstdio>
#include <string>
#include <vector>
#include <cassert>
#include <cstdlib>
#include <cstring>
#include <sstream>
#include <iostream>
#include <algorithm>
#include <climits>
#include <clocale>
//Defines
#define pow2(i) (1<<i)
#define bit(i) (1<<i)
#define isOdd(i) (i&1)
#define isEven(i) (!(i&1))
#define isPrime(i) ((i==2) || ((i&1) && !pTest[i])) //pTest has to be the bool array's name
#define sz(i) i.size()
#define vec(type,name) vector< type > name
#define rep(i,a,b) for(int i=a ; i<=b ; i++)
#define swap(type,a,b) {type t=a; a=b; b=t;}
#define sum(a,n) ( (n*(n+1)/2) - (a-1)*a/2 )
#define iscap(i) (i>='A'&&i<='Z')
#define issmall(i) (i>='a'&&i<='z')
#define isnum(i) (i>='0'&&i<='9')
#define issymbol(i) (!(i>='a'&&i<='z') && !(i>='A'&&i<='Z') && !(i>='0'&&i<='9'))
#define mk(i,j) make_pair(i,j)
#define ERROR 1e-11
//Type Defs
typedef long long lint;
typedef unsigned long long ulint;
typedef long double ldouble;

using namespace std;

int st[20];

void func(int n, int h, int cnt, int x)
{

    if (cnt >= h)
    {
        for (int j=1 ; j<=n ; j++)
        {
            printf("%d",st[j]);
        }
        printf("\n");


        return;
    }

    for (int i=x ; i<=n ; i++)
    {
        if (st[i] == 1)
        {
            st[i] = 0;

            func(n,h,cnt+1,i+1);

            st[i] = 1;
        }
    }

    return;
}

int main()
{
    //freopen("input.txt","r+",stdin);
    //freopen("output.txt","w+",stdout);/**/

    //    TEST CASE     //
    int kase=1, kounter=1;/**/

    int n, h;

    bool blnk = false;

    scanf("%d",&kase);

    while ( kase-- )
    {
        if (blnk) printf("\n");
        else blnk = true;

        for (int i=1 ; i<=20 ; i++)
        {
            st[i] = 1;
        }

        scanf("%d %d",&n,&h);

        func(n,n-h,0,1);
    }


    return 0;
}

[UVa] 727 - Equation

Method: Stack
Tricky case: None that comes to mind. Even though some people are saying that cases like (1+2)3 exist, they don't because my code doesn't take them into account.

Sample Input:

20

0
*
8
-
4
*
6
+
4
/
7
*
2

(
3
+
(
3
+
2
)
*
(
4
+
5
+
2
)
*
(
1
+
2
-
3
/
(
1
-
2
*
(
4
+
4
)
)
)
)
-
3
*
5

(
3
+
(
3
+
2
)
*
(
4
+
5
+
2
)
*
(
1
+
2
-
3
/
(
1
-
2
*
(
4
+
4
)
)
)
)
-
3
*
5

1
+
(
2
*
3
)
*
4

(
1
+
2
)
3

1
+
2
*
3

1
+
2
-
3

1
+
2
*
3

(
1
+
2
)
/
(
3
-
4
)

(
(
1
+
2
)
*
(
3
-
4
)
+
5
)
/
(
6
+
7
)

(
1
*
(
2
+
3
+
(
4
*
5
)
)
+
1
)

(
(
(
1
)
)
)

1

( 
1 
+ 
2 
) 
3 

(
3
/
(
2
+
5
)
+
9
*
5
-
1
/
3
)

(
)

(
3
+
2
)
*
5

(
3
+
2
)
*
5

(
3
+
2
-
4
)
*
5

(
(
3
+
2
)
-
4
)
+
9

Sample Output:

08*46*-47/2*+

332+45+2+*12+31244+*-/-*+35*-

332+45+2+*12+31244+*-/-*+35*-

123*4*+

12+3

123*+

12+3-

123*+

12+34-/

12+34-*5+67+/

123+45*+*1+

1

1

12+3

325+/95*+13/-



32+5*

32+5*

32+4-5*

32+4-9+

/* Faith-M */

//Headers
#include <set>
#include <map>
#include <list>
#include <cmath>
#include <ctime>
#include <deque>
#include <queue>
#include <stack>
#include <cctype>
#include <cstdio>
#include <string>
#include <vector>
#include <cassert>
#include <cstdlib>
#include <cstring>
#include <sstream>
#include <iostream>
#include <algorithm>
#include <climits>
#include <clocale>
//Defines
#define pow2(i) (1<<i)
#define bit(i) (1<<i)
#define isOdd(i) (i&1)
#define isEven(i) (!(i&1))
#define isPrime(i) ((i==2) || ((i&1) && !pTest[i])) //pTest has to be the bool array's name
#define sz(i) i.size()
#define vec(type,name) vector< type > name
#define rep(i,a,b) for(int i=a ; i<=b ; i++)
#define swap(type,a,b) {type t=a; a=b; b=t;}
#define sum(a,n) ( (n*(n+1)/2) - (a-1)*a/2 )
#define iscap(i) (i>='A'&&i<='Z')
#define issmall(i) (i>='a'&&i<='z')
#define isnum(i) (i>='0'&&i<='9')
#define issymbol(i) (!(i>='a'&&i<='z') && !(i>='A'&&i<='Z') && !(i>='0'&&i<='9'))
#define mk(i,j) make_pair(i,j)
#define ERROR 1e-11
//Type Defs
typedef long long lint;
typedef unsigned long long ulint;
typedef long double ldouble;

using namespace std;

int rating[1000];

string proc(string inp)
{
    int i;
    string prnt="";
    stack <char> stk;

    for (i=0 ; i<inp.size() ; i++)
    {



        if ( inp[i] == '(' ) { stk.push(inp[i]); }
        if ( inp[i] == ')' )
        {
            while (stk.top()!='(')
            {
                char ch = stk.top();
                stk.pop();
                prnt += ch;
            }
            stk.pop();

        }

        if ( inp[i]=='/' || inp[i]=='*' || inp[i]=='+' || inp[i]=='-' )
        {
            if (stk.empty() || stk.top()=='(')
            {
                stk.push(inp[i]);
            } else
            {
                while (!stk.empty() && rating[ inp[i] ] <= rating[ stk.top() ])
                {
                    char ch = stk.top();
                    stk.pop();
                    prnt += ch;
                }
                stk.push( inp[i] );
            }
        }


        if (inp[i]>='0' && inp[i]<='9')
        {
            prnt += inp[i];
        }
    }
    while (!stk.empty())
    {
        if (stk.top()=='(') {  }
        else prnt += stk.top();
        stk.pop();
    }

    return prnt;
}

char buf[100000];

int main()
{
    //freopen("input.txt","r+",stdin);
    //freopen("output.txt","w+",stdout);/**/
    //    TEST CASE     //
    int kase=1, kounter=1;/**/

    rating['/'] = 3;
    rating['*'] = 3;
    rating['-'] = 1;
    rating['+'] = 1;

    scanf("%d",&kase);
    getchar();
    gets(buf);

    while (kase--)
    {
        if (kounter++ > 1) printf("\n");


        string inp = "";
        while ( gets(buf) )
        {
            if (!strcmp(buf,"")) break;

            inp += buf;
        }

        if (inp == "") continue;
        string prnt = proc(inp);
        printf("%s\n",prnt.c_str());
    }


    return 0;
}