2014
02-14

# Stock Exchange

All stock exchanges in the world have been hit very hardly by the crisis. To keep their profit, they now try to cut down all expenses. Prague Stock Exchange would like to employ new computer software to run their operations.

Will you help them to develop such a system? Your task is to detect all pairs of buyers and sellers that are able to make a deal together.

The input contains a description of several issuers. Each of them begins with a line containing an integer N, one space, and a code of the stock issuer. After the first one, there are N other lines, each representing one bid. A bid consists of an agent name, one space character, a word specifying the bid type in lowercase letters (either "buy" or "sell") another space character, and a price given as a decimal number with exactly three digits after the decimal point. All buy bids always specify the maximal price, sell bids list the minimal price for which the agent wants to sell the stocks.

Every issuer code consist of 1-10 uppercase letters ("A" – "Z"). Agent names have at least 1 and at most 20 characters and may be composed of both lowercase and uppercase letters. For one issuer, all agent names are always unique, but the same agents may post bids for several issuers. The number of bids ( N ) will never exceed 1000. No price will be higher than 10000.

The last line of the input contains the string "0 END".

The input contains a description of several issuers. Each of them begins with a line containing an integer N, one space, and a code of the stock issuer. After the first one, there are N other lines, each representing one bid. A bid consists of an agent name, one space character, a word specifying the bid type in lowercase letters (either "buy" or "sell") another space character, and a price given as a decimal number with exactly three digits after the decimal point. All buy bids always specify the maximal price, sell bids list the minimal price for which the agent wants to sell the stocks.

Every issuer code consist of 1-10 uppercase letters ("A" – "Z"). Agent names have at least 1 and at most 20 characters and may be composed of both lowercase and uppercase letters. For one issuer, all agent names are always unique, but the same agents may post bids for several issuers. The number of bids ( N ) will never exceed 1000. No price will be higher than 10000.

The last line of the input contains the string "0 END".

3 IBM
TooExpensive sell 12.000
ThisWillWork sell 10.600
4 ACM
one sell 129.999
four sell 129.888
4 CVUT
seller sell 121.110
sellertwo sell 121.111
0 END

IBM
TooExpensive: NO-ONE
ACM
one: two three
two: one four
three: one four
four: two three
CVUT
seller: iamok
toopoor: NO-ONE
sellertwo: iamok
iamok: seller sellertwo

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

int a[100005];
int main(){
int n, len, i, x;
while(~scanf("%d",&n)){
if(n==0){
puts("0");
continue;
}
scanf("%d", &a[1]);
len = 1;
for(i=2;i<=n;++i){
scanf("%d",&x);
int now = lower_bound(a+1,a+len+1, x) - a;
if(now == len+1){
a[++len] = x;
}
else{
a[now] = x;
}
}
printf("%d\n", len);
}
return 0;
}