Codeforces Educational Round 1 (ABCDE)

2024-03-20 12:48

本文主要是介绍Codeforces Educational Round 1 (ABCDE),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

比赛链接:http://codeforces.com/contest/598

A. Tricky Sum

time limit per test:1 second

memory limit per test:256 megabytes

In this problem you are to calculate the sum of all integers from 1 to n, but you should take all powers of two with minus in the sum.

For example, for n = 4 the sum is equal to  - 1 - 2 + 3 - 4 =  - 4, because 1, 2 and 4 are 20, 21 and 22 respectively.

Calculate the answer for t values of n.

Input

The first line of the input contains a single integer t (1 ≤ t ≤ 100) — the number of values of n to be processed.

Each of next t lines contains a single integer n (1 ≤ n ≤ 109).

Output

Print the requested sum for each of t integers n given in the input.

Examples

input

2
4
1000000000

output

-4
499999998352516354

Note

The answer for the first sample is explained in the statement.

题目大意:求1到n的和,数字为2的次幂减,其余加

题目分析:分别求和然后减一下即可

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#define ll long long
using namespace std;int main() {int t;ll n;cin >> t;while (t--) {cin >> n;ll sum = (n & 1) ? (n + 1) / 2 * n : n / 2 * (n + 1);ll temp = 0;while (n) {n >>= 1;temp++;}temp--;ll sum2 = 2;while (temp) {sum2 <<= 1;temp--;}sum2 -= 1;cout << sum - (sum2 << 1) << endl;}
}

 

B. Queries on a String

time limit per test:2 seconds

memory limit per test:256 megabytes

You are given a string s and should process m queries. Each query is described by two 1-based indices liri and integer ki. It means that you should cyclically shift the substring s[li... riki times. The queries should be processed one after another in the order they are given.

One operation of a cyclic shift (rotation) is equivalent to moving the last character to the position of the first character and shifting all other characters one position to the right.

For example, if the string s is abacaba and the query is l1 = 3, r1 = 6, k1 = 1 then the answer is abbacaa. If after that we would process the query l2 = 1, r2 = 4, k2 = 2 then we would get the string baabcaa.

Input

The first line of the input contains the string s (1 ≤ |s| ≤ 10 000) in its initial state, where |s| stands for the length of s. It contains only lowercase English letters.

Second line contains a single integer m (1 ≤ m ≤ 300) — the number of queries.

The i-th of the next m lines contains three integers liri and ki (1 ≤ li ≤ ri ≤ |s|, 1 ≤ ki ≤ 1 000 000) — the description of the i-th query.

Output

Print the resulting string s after processing all m queries.

Examples

input

abacaba
2
3 6 1
1 4 2

output

baabcaa

Note

The sample is described in problem statement.

题目大意:一个字符串,n个操作,每次将l到r位置旋转k个单位长度,求操作后的字符串

题目分析:串长很短,旋转操作具有周期性,因此k对子串长取模即可,旋转可以通过经典的三段逆序方式来实现

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int const MAX = 10005;
char s[MAX];void reverse(char* s, int l, int r) {while (l < r) {swap(s[l++], s[r--]);}
}int main() {scanf("%s", s);int m, l, r, k;scanf("%d", &m);while (m--) {scanf("%d %d %d", &l, &r, &k);l--;r--;k %= (r - l + 1);reverse(s, r - k + 1, r);reverse(s, l, r - k);reverse(s, l, r);}printf("%s\n", s);
}

 

C. Nearest vectors

time limit per test:2 seconds

memory limit per test:256 megabytes

You are given the set of vectors on the plane, each of them starting at the origin. Your task is to find a pair of vectors with the minimal non-oriented angle between them.

Non-oriented angle is non-negative value, minimal between clockwise and counterclockwise direction angles. Non-oriented angle is always between 0 and π. For example, opposite directions vectors have angle equals to π.

Input

First line of the input contains a single integer n (2 ≤ n ≤ 100 000) — the number of vectors.

The i-th of the following n lines contains two integers xi and yi (|x|, |y| ≤ 10 000, x2 + y2 > 0) — the coordinates of the i-th vector. Vectors are numbered from 1 to n in order of appearing in the input. It is guaranteed that no two vectors in the input share the same direction (but they still can have opposite directions).

Output

Print two integer numbers a and b (a ≠ b) — a pair of indices of vectors with the minimal non-oriented angle. You can print the numbers in any order. If there are many possible answers, print any.

Examples

input

4
-1 0
0 -1
1 0
1 1

output

3 4

input

6
-1 0
0 -1
1 0
1 1
-4 -5
-4 -6

output

6 5

题目大意:平面上给n个向量(用点的坐标表示),求向量夹角最小的点的编号

题目分析:这个题除了精度毒瘤外就没什么了,极角排序后暴力即可

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
long double const PI = acos(-1.0);
int const MAX = 100005;
pair <long double, int> a[MAX];
int n, x, y;int main () {scanf("%d", &n);for (int i = 0; i < n; i++) {scanf("%d %d", &x, &y);a[i] = make_pair(atan2(y, x), i);}sort(a, a + n);long double mi = 10000.0, tmp;int ans1 = 0, ans2 = 0;for (int i = 0; i < n; i++) {tmp = a[(i + 1) % n].first - a[i].first;if (tmp < 0) {tmp += 2.0 * PI;}if (tmp < mi) {mi = tmp;ans1 = a[i].second + 1;ans2 = a[(i + 1) % n].second + 1;}}printf("%d %d\n", ans1, ans2);
}

 

D. Igor In the Museum

time limit per test:1 second

memory limit per test:256 megabytes

Igor is in the museum and he wants to see as many pictures as possible.

Museum can be represented as a rectangular field of n × m cells. Each cell is either empty or impassable. Empty cells are marked with '.', impassable cells are marked with '*'. Every two adjacent cells of different types (one empty and one impassable) are divided by a wall containing one picture.

At the beginning Igor is in some empty cell. At every moment he can move to any empty cell that share a side with the current one.

For several starting positions you should calculate the maximum number of pictures that Igor can see. Igor is able to see the picture only if he is in the cell adjacent to the wall with this picture. Igor have a lot of time, so he will examine every picture he can see.

Input

First line of the input contains three integers nm and k (3 ≤ n, m ≤ 1000, 1 ≤ k ≤ min(n·m, 100 000)) — the museum dimensions and the number of starting positions to process.

Each of the next n lines contains m symbols '.', '*' — the description of the museum. It is guaranteed that all border cells are impassable, so Igor can't go out from the museum.

Each of the last k lines contains two integers x and y (1 ≤ x ≤ n, 1 ≤ y ≤ m) — the row and the column of one of Igor's starting positions respectively. Rows are numbered from top to bottom, columns — from left to right. It is guaranteed that all starting positions are empty cells.

Output

Print k integers — the maximum number of pictures, that Igor can see if he starts in corresponding position.

Examples

input

5 6 3
******
*..*.*
******
*....*
******
2 2
2 5
4 3

output

6
4
10

input

4 4 1
****
*..*
*.**
****
3 2

output

8

题目大意:输入一个n*m的字符矩阵,k组询问,每组询问是一个点,求与该点所在的联通块直接相邻的'*'字符的数量

题目分析:DFS即可,DFS时对每个联通块标号

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
int const MAX = 1005;
int n, m, k;
char s[MAX][MAX];
bool vis[MAX][MAX];
int mp[MAX][MAX];
vector<int> ans;int dx[4] = {0, 1, 0, -1};
int dy[4] = {1, 0, -1, 0};int DFS(int id, int x, int y) {if (s[x][y] == '*') {return 1;}vis[x][y] = true;mp[x][y] = id;int num = 0;for (int i = 0; i < 4; i++) {int xx = x + dx[i];int yy = y + dy[i];if (!vis[xx][yy] && xx > 0 && yy > 0 && xx <= n && yy <= m) {num += DFS(id, xx, yy);}}return num;
}int main() {scanf("%d %d %d", &n, &m, &k);for (int i = 1; i <= n; i++) {scanf("%s", s[i] + 1);}int id = 0;for (int i = 1; i <= n; i++) {for (int j = 1; j <= m; j++) {if (s[i][j] == '.' && !vis[i][j]) {int res = DFS(id, i, j);ans.push_back(res);id++;}}}int x, y;while (k--) {scanf("%d %d", &x, &y);printf("%d\n", ans[mp[x][y]]);}
}

 

E. Chocolate Bar

time limit per test:2 seconds

memory limit per test:256 megabytes

You have a rectangular chocolate bar consisting of n × m single squares. You want to eat exactly k squares, so you may need to break the chocolate bar.

In one move you can break any single rectangular piece of chocolate in two rectangular pieces. You can break only by lines between squares: horizontally or vertically. The cost of breaking is equal to square of the break length.

For example, if you have a chocolate bar consisting of 2 × 3 unit squares then you can break it horizontally and get two 1 × 3 pieces (the cost of such breaking is 32 = 9), or you can break it vertically in two ways and get two pieces: 2 × 1 and 2 × 2 (the cost of such breaking is 22 = 4).

For several given values nm and k find the minimum total cost of breaking. You can eat exactly k squares of chocolate if after all operations of breaking there is a set of rectangular pieces of chocolate with the total size equal to k squares. The remaining n·m - ksquares are not necessarily form a single rectangular piece.

Input

The first line of the input contains a single integer t (1 ≤ t ≤ 40910) — the number of values nm and k to process.

Each of the next t lines contains three integers nm and k (1 ≤ n, m ≤ 30, 1 ≤ k ≤ min(n·m, 50)) — the dimensions of the chocolate bar and the number of squares you want to eat respectively.

Output

For each nm and k print the minimum total cost needed to break the chocolate bar, in order to make it possible to eat exactly ksquares.

Examples

input

4
2 2 1
2 2 3
2 2 2
2 2 4

output

5
5
4
0

Note

In the first query of the sample one needs to perform two breaks:

  • to split 2 × 2 bar into two pieces of 2 × 1 (cost is 22 = 4),
  • to split the resulting 2 × 1 into two 1 × 1 pieces (cost is 12 = 1).

In the second query of the sample one wants to eat 3 unit squares. One can use exactly the same strategy as in the first query of the sample.

题目大意:n*m的巧克力块,求在吃k块的情况下,最小切割代价,每次切割的代价为切割长度的平方

题目分析:数据范围很小,随便dp即可,dp[i][j][k]表示高为i,长为j的巧克力块吃k块的最小代价,暴力枚举横切和竖切的情况,以横切为例,假设在高为h的地方切一刀,会把巧克力分为h*j和(i-h)*j两块,假设当前枚举的切割后的上半部分的块数为up,下半部分则为k-up,易得转移方程dp[i][j][k] = min(dp[i][j][k], dp[h][j][up] + dp[i - h][j][k - up] + j * j,若i*j<=50,如果要吃大小为i*j的巧克力块的话是不需要额外切割的,比如样例的第四个,因此初始化时将i*j<=50的dp[i][j][i*j]设为0

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int const INF = 1e9;int dp[35][35][55];void pre() {for (int i = 0; i <= 30; i++) {for (int j = 0; j <= 30; j++) {for (int k = 0; k <= 50; k++) {dp[i][j][k] = INF;}}}for (int i = 0; i <= 30; i++) {for (int j = 0; j <= 30; j++) {dp[i][j][0] = 0;if (i * j <= 50) {dp[i][j][i * j] = 0;}}}for (int i = 1; i <= 30; i++) {for (int j = 1; j <= 30; j++) {for (int k = 1; k <= min(i * j, 50); k++) {for (int h = 1; h <= (i >> 1); h++) {for (int up = 0; up <= k; up++) {dp[i][j][k] = min(dp[i][j][k], dp[h][j][up] + dp[i - h][j][k - up] + j * j);}}for (int v = 1; v <= (j >> 1); v++) {for (int left = 0; left <= k; left++) {dp[i][j][k] = min(dp[i][j][k], dp[i][v][left] + dp[i][j - v][k - left] + i * i);}}}}}
}int main() {pre();int t, n, m, k;scanf("%d", &t);while (t--) {scanf("%d %d %d", &n, &m, &k);printf("%d\n", dp[n][m][k]);}
}

 

这篇关于Codeforces Educational Round 1 (ABCDE)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/829510

相关文章

Codeforces Round #240 (Div. 2) E分治算法探究1

Codeforces Round #240 (Div. 2) E  http://codeforces.com/contest/415/problem/E 2^n个数,每次操作将其分成2^q份,对于每一份内部的数进行翻转(逆序),每次操作完后输出操作后新序列的逆序对数。 图一:  划分子问题。 图二: 分而治之,=>  合并 。 图三: 回溯:

Codeforces Round #261 (Div. 2)小记

A  XX注意最后输出满足条件,我也不知道为什么写的这么长。 #define X first#define Y secondvector<pair<int , int> > a ;int can(pair<int , int> c){return -1000 <= c.X && c.X <= 1000&& -1000 <= c.Y && c.Y <= 1000 ;}int m

Codeforces Beta Round #47 C凸包 (最终写法)

题意慢慢看。 typedef long long LL ;int cmp(double x){if(fabs(x) < 1e-8) return 0 ;return x > 0 ? 1 : -1 ;}struct point{double x , y ;point(){}point(double _x , double _y):x(_x) , y(_y){}point op

Codeforces Round #113 (Div. 2) B 判断多边形是否在凸包内

题目点击打开链接 凸多边形A, 多边形B, 判断B是否严格在A内。  注意AB有重点 。  将A,B上的点合在一起求凸包,如果凸包上的点是B的某个点,则B肯定不在A内。 或者说B上的某点在凸包的边上则也说明B不严格在A里面。 这个处理有个巧妙的方法,只需在求凸包的时候, <=  改成< 也就是说凸包一条边上的所有点都重复点都记录在凸包里面了。 另外不能去重点。 int

Codeforces 482B 线段树

求是否存在这样的n个数; m次操作,每次操作就是三个数 l ,r,val          a[l] & a[l+1] &......&a[r] = val 就是区间l---r上的与的值为val 。 也就是意味着区间[L , R] 每个数要执行 | val 操作  最后判断  a[l] & a[l+1] &......&a[r] 是否= val import ja

Codeforces Round 971 (Div. 4) (A~G1)

A、B题太简单,不做解释 C 对于 x y 两个方向,每一个方向至少需要 x / k 向上取整的步数,取最大值。 由于 x 方向先移动,假如 x 方向需要的步数多于 y 方向的步数,那么最后 y 方向的那一步就不需要了,答案减 1 代码 #include <iostream>#include <algorithm>#include <vector>#include <string>

Codeforces#295(Div.2)A、B(模拟+BFS)

解题报告链接:点击打开链接 C. 题目链接:点击打开链接 解题思路: 对于给定的字符串,取出现次数最多的字母(可以同时有多个)。由这些字母组成长度为n的字符串,求有多少种组合。最后用数学知识即可。 完整代码: #include <algorithm>#include <iostream>#include <cstring>#include <climits>

MemSQL Start[c]UP 2.0 - Round 1A(构造)

题目链接:http://codeforces.com/problemset/problem/452/A 解题思路: 打个表暴力查找匹配。 完整代码: #include <algorithm>#include <iostream>#include <cstring>#include <complex>#include <cstdio>#include <strin

Codeforces Round #281 (Div. 2)A(构造+暴力模拟)

题目链接:http://codeforces.com/problemset/problem/493/A 解题思路: 暴力的判断,分三种情况去判断即可。注意如果之前已经被罚下场后,那么在后面的罚下情况不应该算在输出结果内。 完整代码: #include <algorithm>#include <iostream>#include <cstring>#include <co

Codeforces Round #182 (Div. 2)A(水题)

题目链接:http://codeforces.com/contest/302/problem/A 解题思路: 只要通过重新排列使区间内和为0即是1,否则是0. 完整代码: #include <algorithm>#include <iostream>#include <cstring>#include <complex>#include <cstdio>#inc