Codeforces Round #529 (Div.3)- Bài 5

Bài 5: You are given a bracket sequences $s$ consisting of $n$ opening '(' ans closing ')' brackets.
A regular bracket sequence is a bracket sequence that can be transformed into a correct arithmetic expression by inserting characters '1' and '+' between the original characters of the sequence. For example, bracket sequences "( ) ( )","( ( ) ) " are regular (the resulting expressions are "( 1 )+ ( 1 )","( (1+1)+1)", and ") (" and "(" are not.

You can change the type of some bracket $s_i$. It means that if $s_i= ' ) '$ then you can change it to '(' and vice versa.
Your task is to calculate the number of position $i$ such that if you change the type of the $i-th$ bracket, then the resulting bracket sequence becomes regular.
Input
The first line of the input contains one integer $n(1\le n\le 10^6)$- the length of the bracket sequence.
The second line of the input contains the string $s$ consisting of $n$ opening '(' and closing ')' brackets.
Output
Print one integer- the number of position $i$ such that if you change the type of the $i-th$ bracket, then the resulting bracket sequence becomes regular.

Examples

input

Copy

6
(((())

output

Copy

3

input

Copy

6
()()()

output

Copy

0

input

Copy

1
)

output

Copy

0

input

Copy

8
)))(((((

output

Copy

0

Solution:

#include <iostream>

using namespace std;

const int N = 1e6 + 6;

int n, ans;
char s[N];
int a[N], m[N];

int main() {
 cin >> n >> s + 1;
 for (int i = 1; i <= n; ++i) a[i] = a[i - 1] + (s[i] == '(') - (s[i] == ')');
 for (int i = n; i >= 1; --i) m[i] = min(i == n ? N : m[i + 1], a[i]);
 for (int i = 1; i <= n && a[i - 1] >= 0; ++i) {
  int d = ((s[i] == '(') - (s[i] == ')')) * 2;
  ans += m[i] >= d && a[n] == d;
 }
 cout << ans << endl;
 return 0;
}

Codeforces Round #529 (Div.3)- Bài 4

Bài 4: There are $n$ kids, numbered from $1$ to $n$, dancing in a circle around the Christmas tree. Let's enumerate them in a clockwise directions as $p_1,p_2,...,p_n$( all these numbers are from $1$ to $n$ and are distinct, so $p$ is a permutation). Let the next kid for a kid $p_i$ be kid $p_{i+1}$ if $i<n$ and $p_1$ otherwise. After the dance, each kid remembered two kids: the next kid( let's call him $x$) and the next kid for $x$. Each kid told you which kids he/she remembered: the kid $i$ remembered kid $a_{i,1}$ and $a_{i,2}$. However, the order of $a_{i,1}$ and $a_{i,2}$ can differ from their order in the circle.

Example: 5 kids in a circle, $p=[3,2,4,1,5]$ (or any cyclic shift). The information kids remembered is: $a_{1,1}=3,a_{1,2}=5,a_{2,1}=1,a_{2,2}=4;a_{3,1}=2,a_{3,2}=4,a_{4,1}=1,a_{4,2}=5,a_{5,1}=2,a_{5,2}=3$.
You have to restore the order of the kids in the circles using this information. If there are several answers, you may print any. It is guaranteed that at least one solution exists.
If you are Python programmer, consider using PyPy instead of Python when you submit your code.
Input
The first line of the input contains one integer $n(3\le n\le 2.10^5)$- the number of the kids.
The next $n$ lines contain $2$ integers each. The $i-th$ line contains two integers $a_{i,1}$ and $a_{i,2}(1\le a_{i,1},a_{i,2}\le n,a_{i,1}\ne a_{i,2})$- the kids the $i-th$ kid remembered, given in arbitrary order.
Output
Print $n$ integers $p_1,p_2,...,p_n$- permutation of integers from $1$ to $n$, which corresponds to the order of kids in the circle. If there are several answers, you may print any (for example, it doesn't matter which kid is the first in the circle). It is guaranteed that at least one solution exists.

Examples

input

Copy

5
3 5
1 4
2 4
1 5
2 3

output

Copy

3 2 4 1 5 

input

Copy

3
2 3
3 1
1 2

output

Copy

3 1 2 

 Solution:

#include <bits/stdc++.h>

int main() {
 int n, i, j, k, u, v;
 scanf("%d", &n);
 std::vector<int> a(n + 1);
 for (i = 1; i <= n; ++i) {
  scanf("%d%d", &u, &v);
  if (u == n || v == n) j = u ^ v ^ n;
  a[u] ^= v; a[v] ^= u;
 }
 if (j == u || j == v) j ^= a[n];
 for (i = n; n--; k = j, j = i, i = k ^ a[i]) printf("%d ", i);
}

Codeforces Round #529 (Div.3)- Bài 2

Bài 2: You are given an array $a$ consisting of $n$ integer numbers.
Let instability of the array be the following value: $\max\limits_{i=1}^{n}a_i-\min\limits_{i=1}^{n}a_i$.
You have to remove exactly one element from this array to minimize instability of the resulting $(n-1)-$ elements array. Your task is to calculate the minimum possible instability.
Input
The first line of the input contains one integer $n(2\le n\le 10^5)$- the number of elements in the array $a$.
The second line of the input contains $n$ integers $a_1,a_2,...,a_n(1\le a_i\le 10^5)$- elements of the array $a$.
Output
Print one integer- the minimum possible instability of the array if you have to remove exactly one element from the array $a$.

Examples

input

Copy

4
1 3 3 7

output

Copy

2

input

Copy

2
1 100000

output

Copy

0

Solution:

#include<bits/stdc++.h>
using namespace std;
int n,a[101000];
int main(){
 cin>>n;
 for(int i=0;i<n;i++)
  cin>>a[i];
 sort(a,a+n);
 cout<<min(a[n-1]-a[1],a[n-2]-a[0]);
}

Codeforces Round #529 (Div.3) - Bài 1

Polycarp loves ciphers. He has invented his own cipher called repeating.
Repeating cipher is used for strings. To encrypt the string $s=s_1s_2...s_m(1\le m\le 10)$, Polycarp uses the following algorithm:
+ he writes down $s_1$ ones,
+ he writes down $s_2$ twices,
+ he writes down $s_3$ three times,
+...
+ he writes down $s_m$ $m$ times.
For example, if $s="bab"$ the process is: $"b"\to "baa"\to "baabbb"$. So the encrypted $s="bab"$ is $"baabbb"$.
Given string $t$- the result of encryption of some string $s$. Your task is to decrypt it, i.e find the string $s$.
Input
The first line contains integer $n(1\le n\le 55)$- the length of the encrypted string. The second line of the input contains $t$- the result of encryption of some string $s$. It contains only lowercase Latin letters. The length of $t$ is exactly $n$.
It is guarantee that the answer to the test exists.
Output
Print such string $s$ that after encryption it equals $t$.

Examples

input

Copy

6
baabbb

output

Copy

bab

input

Copy

10
ooopppssss

output

Copy

oops

input

Copy

1
z

output

Copy

z

 Solution:

#include<bits/stdc++.h>
using namespace std;
int m;
int main(){
   int n;
   string s;
   cin>>s;
   cin>>s;
   for(int i=0;i<s.size();i+=m){
      cout<<s[i];
      m++;
   }
   return 0;
}

Codeforces Round 57- Bài 1

Bài 1: You are given a range of positive integers from $l$ to $r$

Find such a pair of integers $(x,y)$ that $l\le x,y\le r,x\ne y$ and $x$ divides $y$

If there are multiple answers, print any of them.

You are also asked to answer $T$ independent queries

T independent queries.

Input

The first line contains a single integer $T(1\le T\le 1000)$- the number of queries. T$T$1≤T— the number of queries

Each of the next $T$ lines contains two integers $l$ and $r(1\le l\le r\le 998244353)$ - inclusive borders of the range.

It is guaranteed that testset only includes queries, which have at least one suitable pair.

Output

Print $T$ lines, each line should contain the answer- two integer $x$ and $y$ such that $1\le x,y\le r,x\ne y$ and $x$ divides $y$. The answer in the $i-th$ lines should correspond to the $i-th$ query from the input

If there are multiple answers, print any of them.

Example

input

Copy

3
1 10
3 14
1 10

output

Copy

1 7
3 9
5 10

Solution:

#include<bits/stdc++.h>
using namespace std;
int main(){
    int t,l,r;
   cin>>t;
   while(t--){
    cin>>l>>r;
    cout<<l<<" "<<2*l<<'\n';
   }
   return 0;
}