acm竞赛小结5 BUAA Training 2013 #1_综合

上周参加了北航2013训练赛#1

挺有意思的对于初学者难度也挺适中一共一周时间所以时间相当充裕全A完了。

A - Coins

Time Limit: 2000 MS Memory Limit: 262144 KB 64bit IO Format: %I64d & %I64u

Description

One day Vasya came across three Berland coins. They didn't have any numbers that's why Vasya didn't understand how their denominations differ. He supposed that if one coin is heavier than the other one, then it should be worth more. Vasya weighed all the three pairs of coins on pan balance scales and told you the results. Find out how the deminations of the coins differ or if Vasya has a mistake in the weighting results. No two coins are equal.

Input

The input data contains the results of all the weighting, one result on each line. It is guaranteed that every coin pair was weighted exactly once. Vasya labelled the coins with letters ?A?, ?B? and ?C?. Each result is a line that appears as (letter)(> or < sign)(letter). For example, if coin "A" proved lighter than coin "B", the result of the weighting is A<B.

Output

It the results are contradictory, print Impossible. Otherwise, print without spaces the rearrangement of letters ?A?, ?B? and ?C? which represent the coins in the increasing order of their weights.

Sample Input

Input

A>B
C<B
A>C

Output

CBA

Input

A<B
B>C
C>A

Output

ACB

反正是简单题，但是一直wa，最后只好就用最笨的方法，竟然过了。。。：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
const int MaxN = 10001;
bool v[4][4]; int main(){
     int k , j , i , x , y;char a[4];memset(v,0,sizeof(v));cin >> a;x = a[0] - 64; y = a[2] - 64;if (a[1] == '>') v[x][y] = 1; else v[y][x] = 1;cin >> a;x = a[0] - 64; y = a[2] - 64;if (a[1] == '>') v[x][y] = 1; else v[y][x] = 1;cin >> a;x = a[0] - 64; y = a[2] - 64;if (a[1] == '>') v[x][y] = 1; else v[y][x] = 1;    if (v[1][2] && v[2][3] && (!v[2][1]) && (!v[3][1]) && (!v[3][2])) cout << "CBA" << endl; elseif (v[1][3] && v[3][2] && (!v[3][1]) && (!v[2][1]) && (!v[2][3])) cout << "BCA" << endl; elseif (v[2][1] && v[1][3] && (!v[1][2]) && (!v[3][2]) && (!v[3][1])) cout << "CAB" << endl; elseif (v[2][3] && v[3][1] && (!v[3][2]) && (!v[1][2]) && (!v[1][3])) cout << "ACB" << endl; elseif (v[3][1] && v[1][2] && (!v[1][3]) && (!v[2][3]) && (!v[2][1])) cout << "BAC" << endl; elseif (v[3][2] && v[2][1] && (!v[2][3]) && (!v[1][3]) && (!v[1][2])) cout << "ABC" << endl; elsecout << "Impossible" << endl;cin >> a;return 0;
}

B - Email address

Time Limit: 2000 MS Memory Limit: 262144 KB 64bit IO Format: %I64d & %I64u

Description

Sometimes one has to spell email addresses over the phone. Then one usually pronounces a dot as dot, an at sign as at. As a result, we get something like vasyaatgmaildotcom. Your task is to transform it into a proper email address (vasya@gmail.com).

It is known that a proper email address contains only such symbols as . @ and lower-case Latin letters, doesn't start with and doesn't end with a dot. Also, a proper email address doesn't start with and doesn't end with an at sign. Moreover, an email address contains exactly one such symbol as @, yet may contain any number (possible, zero) of dots.

You have to carry out a series of replacements so that the length of the result was as short as possible and it was a proper email address. If the lengths are equal, you should print the lexicographically minimal result.

Overall, two variants of replacement are possible: dot can be replaced by a dot, at can be replaced by an at.

Input

The first line contains the email address description. It is guaranteed that that is a proper email address with all the dots replaced by dot an the at signs replaced by at. The line is not empty and its length does not exceed 100 symbols.

Output

Print the shortest email address, from which the given line could be made by the described above replacements. If there are several solutions to that problem, print the lexicographically minimal one (the lexicographical comparison of the lines are implemented with an operator < in modern programming languages).

In the ASCII table the symbols go in this order: . @ ab...z

Sample Input

Input

vasyaatgmaildotcom

Output

vasya@gmail.com

Input

dotdotdotatdotdotat

Output

dot..@..at

Input

aatt

Output

a@t

水题不解释了

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
const int MaxN = 10001;
char a[1001];
char b[1001];int main(){
     int k , j , i , len;bool flag = 0;cin >> a;len = strlen(a); i = -1;while (1){
     i++;if (i == len) break;if (i > 0 && i+2 < len && a[i] == 'a' && a[i+1] == 't' && !flag){
     flag = 1;i++;cout << '@';} elseif (i > 0 && i+3 < len && a[i] == 'd' && a[i+1] == 'o' && a[i+2] == 't'){
     i += 2;cout << '.';} else cout << a[i];}cout << endl;cin >> a;return 0;
}

C - Longest Regular Bracket Sequence

Time Limit: 2000 MS Memory Limit: 262144 KB 64bit IO Format: %I64d & %I64u

Description

This is yet another problem dealing with regular bracket sequences.

We should remind you that a bracket sequence is called regular, if by inserting ?+? and ?1? into it we can get a correct mathematical expression. For example, sequences ?(())()?, ?()? and ?(()(()))? are regular, while ?)(?, ?(()? and ?(()))(? are not.

You are given a string of ?(? and ?)? characters. You are to find its longest substring that is a regular bracket sequence. You are to find the number of such substrings as well.

Input

The first line of the input file contains a non-empty string, consisting of ?(? and ?)? characters. Its length does not exceed 10⁶.

Output

Print the length of the longest substring that is a regular bracket sequence, and the number of such substrings. If there are no such substrings, write the only line containing "0 1".

Sample Input

Input

)((())))(()())

Output

6 2

Input

))(

Output

0 1

这题用栈实现

#include <iostream>
#include <stack>
#include <string.h>
using namespace std;
stack <pair<char,long long> > t;
char a[1000010];
int main()
{
         long long maxn = 0,maxnum = 1;long long n = 0;scanf("%s", a);long long aaa = strlen(a);for (long long i = 0; i < aaa; i ++){
         if (a[i] == '('){
         t.push(make_pair(a[i], n));n = 0;}else{
         if (t.empty())n = 0;else{
         long long u = t.top().second;t.pop();n += (u + 2);if (n