2019-08-08 17:34 已编辑苏州大学算法工程师

关注

Codeforces Round #501 (Div. 3)

A. Points in Segments

Description:

You are given a set of $n$ segments on the axis $O x$ , each segment has integer endpoints between $1$ and $m$ inclusive. Segments may intersect, overlap or even coincide with each other. Each segment is characterized by two integers $l_{i}$ and $r_{i}$ ( $1 \leq l_{i} \leq r_{i} \leq m$ ) — coordinates of the left and of the right endpoints.
Consider all integer points between $1$ and $m$ inclusive. Your task is to print all such points that don’t belong to any segment. The point $x$ belongs to the segment $[l; r]$ if and only if $l \leq x \leq r$ .

Input:

The first line of the input contains two integers $n$ and $m$ ( $1 \leq n, m \leq 100$ ) — the number of segments and the upper bound for coordinates.
The next $n$ lines contain two integers each $l_{i}$ and $r_{i}$ ( $1 \leq l_{i} \leq r_{i} \leq m$ ) — the endpoints of the $i$ -th segment. Segments may intersect, overlap or even coincide with each other. Note, it is possible that $l_{i} = r_{i}$ , i.e. a segment can degenerate to a point.

Output

In the first line print one integer $k$ — the number of points that don’t belong to any segment.
In the second line print exactly $k$ integers in any order — the points that don’t belong to any segment. All points you print should be distinct.
If there are no such points at all, print a single integer $0$ in the first line and either leave the second line empty or do not print it at all.

Sample Input:

3 5
2 2
1 2
5 5

Sample Output:

2
3 4

Sample Input:

1 7
1 7

Sample Output:

题目链接

给出几组区间，求不在区间内的所有点。

直接用一个数组标记记录即可。

最开始读题以为要输出所有区间，一直WA…

AC代码:

#include <bits/stdc++.h>
using namespace std;
#define mem(a,b) memset(a,b,sizeof(a))
#define pb push_back
#define mp make_pair
#define lowbit(x) (x&(-x))
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> PII;
typedef pair<double,double> PDD;
const int INF = 0x3f3f3f3f;
const int maxn = 1e5 + 5;
const int mod = 1e9 + 7;
const double eps = 1e-8;
const double pi = asin(1.0) * 2;
const double e = 2.718281828459;
bool Finish_read;
template<class T>inline void read(T &x) {
	Finish_read = 1;
	x = 0;
	int f = 1;
	char ch = getchar();
	while (!isdigit(ch)) {
		if (ch == '-') {
			f = -1;
		}
		if (ch == EOF) {
			return;
		}
		ch = getchar();
	}
	while (isdigit(ch)) {
		x = x * 10 + ch - '0';
		ch = getchar();
	}
	x *= f;
	Finish_read = 1;
};

int main(int argc, char *argv[]) {
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
	freopen("out.txt", "w", stdout);
#endif
	int n, m;
	read(n); read(m);
	vector<int> dot(m + 1, 0);
	for (int i = 0, l, r; i < n; ++i) {
		read(l); read(r);
		for (int i = l; i <= r; ++i) {
			if (!dot[i]) {
				dot[i] = 1;
			}
		}
	}
	vector<int> ans;
	for (int i = 1; i <= m; ++i) {
		if (!dot[i]) {
			ans.pb(i);
		}
	}
	printf("%d\n", int(ans.size()));
	for (auto i : ans) {
		printf("%d ", i);
	}
	printf("\n");
#ifndef ONLINE_JUDGE
    fclose(stdin);
	fclose(stdout);
	system("gedit out.txt");
#endif
    return 0;
}

B. Obtaining the String

Description:

You are given two strings $s$ and $t$ . Both strings have length $n$ and consist of lowercase Latin letters. The characters in the strings are numbered from $1$ to $n$ .
You can successively perform the following move any number of times (possibly, zero):
swap any two adjacent (neighboring) characters of $s$ (i.e. for any $i = {1, 2, \dots, n - 1}$ you can swap $s_{i}$ and $s_{i + 1})$ . You can’t apply a move to the string $t$ . The moves are applied to the string $s$ one after another.
Your task is to obtain the string $t$ from the string $s$ . Find any way to do it with at most $1 0^{4}$ such moves.
You do not have to minimize the number of moves, just find any sequence of moves of length $1 0^{4}$ or less to transform $s$ into $t$ .

Input:

The first line of the input contains one integer $n$ ( $1 \leq n \leq 50$ ) — the length of strings $s$ and $t$ .
The second line of the input contains the string $s$ consisting of $n$ lowercase Latin letters.
The third line of the input contains the string $t$ consisting of $n$ lowercase Latin letters.

Output

If it is impossible to obtain the string $t$ using moves, print “-1”.
Otherwise in the first line print one integer $k$ — the number of moves to transform $s$ to $t$ . Note that $k$ must be an integer number between $0$ and $1 0^{4}$ inclusive.
In the second line print $k$ integers $c_{j}$ ( $1 \leq c_{j} < n$ ), where $c_{j}$ means that on the $j$ -th move you swap characters $s_{c_{j}}$ and $s_{c_{j} + 1}$ .
If you do not need to apply any moves, print a single integer $0$ in the first line and either leave the second line empty or do not print it at all.

Sample Input:

6
abcdef
abdfec

Sample Output:

4
3 5 4 5

Sample Input:

4
abcd
accd

Sample Output:

-1

题目链接

求第一个字符串相邻字符如何交换可以与第二个字符串相同。

先判断两个字符串内每个字符个数是否都相同，再在第二个字符串中从后往前找两个字符串中不同的字符进行交换。

AC代码:

#include <bits/stdc++.h>
using namespace std;
#define mem(a,b) memset(a,b,sizeof(a))
#define pb push_back
#define mp make_pair
#define lowbit(x) (x&(-x))
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> PII;
typedef pair<double,double> PDD;
const int INF = 0x3f3f3f3f;
const int maxn = 1e5 + 5;
const int mod = 1e9 + 7;
const double eps = 1e-8;
const double pi = asin(1.0) * 2;
const double e = 2.718281828459;
bool Finish_read;
template<class T>inline void read(T &x) {
	Finish_read = 1;
	x = 0;
	int f = 1;
	char ch = getchar();
	while (!isdigit(ch)) {
		if (ch == '-') {
			f = -1;
		}
		if (ch == EOF) {
			return;
		}
		ch = getchar();
	}
	while (isdigit(ch)) {
		x = x * 10 + ch - '0';
		ch = getchar();
	}
	x *= f;
	Finish_read = 1;
};

int main(int argc, char *argv[]) {
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
	freopen("out.txt", "w", stdout);
#endif
	int n;
	read(n);
	string s, t;
	cin >> s >> t;
	for (int i = 0; i < 26; ++i) {
		if (count(s.begin(), s.end(), char('a' + i)) != count(t.begin(), t.end(), char('a' + i))) {
			printf("-1\n");
			return 0;
		}
	}
	vector<int> ans;
	for (int i = n - 1; i >= 0; --i) {
		if (s[i] != t[i]) {
			int index = 0;
			for (int j = i - 1; j >= 0; --j) {
				if (s[j] == t[i]) {
					index = j;
					break;
				}
			}
			for (int j = index; j < i; ++j) {
				swap(s[j], s[j + 1]);
				ans.pb(j + 1);
			}
		}
	}
	printf("%d\n", int(ans.size()));
	for (auto i : ans) {
		printf("%d ", i);
	}
	printf("\n");
#ifndef ONLINE_JUDGE
    fclose(stdin);
	fclose(stdout);
	system("gedit out.txt");
#endif
    return 0;
}

C. Songs Compression

Description:

Ivan has $n$ songs on his phone. The size of the $i$ -th song is $a_{i}$ bytes. Ivan also has a flash drive which can hold at most $m$ bytes in total. Initially, his flash drive is empty.
Ivan wants to copy all $n$ songs to the flash drive. He can compress the songs. If he compresses the $i$ -th song, the size of the $i$ -th song reduces from $a_{i}$ to $b_{i}$ bytes ( $b_{i} < a_{i}$ ).
Ivan can compress any subset of the songs (possibly empty) and copy all the songs to his flash drive if the sum of their sizes is at most $m$ . He can compress any subset of the songs (not necessarily contiguous).
Ivan wants to find the minimum number of songs he needs to compress in such a way that all his songs fit on the drive (i.e. the sum of their sizes is less than or equal to $m$ ).
If it is impossible to copy all the songs (even if Ivan compresses all the songs), print “-1”. Otherwise print the minimum number of songs Ivan needs to compress.

Input:

The first line of the input contains two integers $n$ and $m$ ( $1 \leq n \leq 1 0^{5}, 1 \leq m \leq 1 0^{9}$ ) — the number of the songs on Ivan’s phone and the capacity of Ivan’s flash drive.
The next $n$ lines contain two integers each: the $i$ -th line contains two integers $a_{i}$ and $b_{i}$ ( $1 \leq a_{i}, b_{i} \leq 1 0^{9}$ , $a_{i} > b_{i}$ ) — the initial size of the $i$ -th song and the size of the $i$ -th song after compression.

Output

If it is impossible to compress a subset of the songs in such a way that all songs fit on the flash drive, print “-1”. Otherwise print the minimum number of the songs to compress.

Sample Input:

4 21
10 8
7 4
3 1
5 4

Sample Output:

Sample Input:

4 16
10 8
7 4
3 1
5 4

Sample Output:

-1

题目链接

每首歌有a大小，压缩后是b大小，求最少压缩几首歌可以达到要求。

按照压缩变化大小(a-b)降序排序，优先压缩变化大的歌曲，直到达到要求。

AC代码:

#include <bits/stdc++.h>
using namespace std;
#define mem(a,b) memset(a,b,sizeof(a))
#define pb push_back
#define mp make_pair
#define lowbit(x) (x&(-x))
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> PII;
typedef pair<double,double> PDD;
const int INF = 0x3f3f3f3f;
const int maxn = 1e5 + 5;
const int mod = 1e9 + 7;
const double eps = 1e-8;
const double pi = asin(1.0) * 2;
const double e = 2.718281828459;
bool Finish_read;
template<class T>inline void read(T &x) {
	Finish_read = 1;
	x = 0;
	int f = 1;
	char ch = getchar();
	while (!isdigit(ch)) {
		if (ch == '-') {
			f = -1;
		}
		if (ch == EOF) {
			return;
		}
		ch = getchar();
	}
	while (isdigit(ch)) {
		x = x * 10 + ch - '0';
		ch = getchar();
	}
	x *= f;
	Finish_read = 1;
};

int main(int argc, char *argv[]) {
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
	freopen("out.txt", "w", stdout);
#endif
	int n, m;
	read(n); read(m);
	ll sum = 0, ans = 0;
	int cnt = 0;
	vector<ll> c;
	for (int i = 0, a, b; i < n; ++i) {
		read(a); read(b);
		ans += a;
		sum += b;
		c.pb(a - b);
	}
	if (sum > m) {
		printf("-1\n");
	}
	else {
		sort(c.begin(), c.end());
		reverse(c.begin(), c.end());
		for (int i = 0; i < n && ans > m; ++i) {
			ans -= c[i];
			cnt++;
		}
		printf("%d\n", cnt);
	}
#ifndef ONLINE_JUDGE
    fclose(stdin);
	fclose(stdout);
	system("gedit out.txt");
#endif
    return 0;
}

D. Walking Between Houses

Description:

There are $n$ houses in a row. They are numbered from $1$ to $n$ in order from left to right. Initially you are in the house $1$ .
You have to perform $k$ moves to other house. In one move you go from your current house to some other house. You can’t stay where you are (i.e., in each move the new house differs from the current house). If you go from the house $x$ to the house $y$ , the total distance you walked increases by $∣ x - y ∣$ units of distance, where $∣ a ∣$ is the absolute value of $a$ . It is possible to visit the same house multiple times (but you can’t visit the same house in sequence).
Your goal is to walk exactly $s$ units of distance in total.
If it is impossible, print “NO”. Otherwise print “YES” and any of the ways to do that. Remember that you should do exactly $k$ moves.

Input:

The first line of the input contains three integers $n$ , $k$ , $s$ ( $2 \leq n \leq 1 0^{9}$ , $1 \leq k \leq 2 \cdot 1 0^{5}$ , $1 \leq s \leq 1 0^{18}$ ) — the number of houses, the number of moves and the total distance you want to walk.

Output

If you cannot perform $k$ moves with total walking distance equal to $s$ , print “NO”.
Otherwise print “YES” on the first line and then print exactly $k$ integers $h_{i}$ ( $1 \leq h_{i} \leq n$ ) on the second line, where $h_{i}$ is the house you visit on the $i$ -th move.
For each $j$ from $1$ to $k - 1$ the following condition should be satisfied: $h_{j} \neq h_{j + 1}$ . Also $h_{1} \neq 1$ should be satisfied.

Sample Input:

10 2 15

Sample Output:

YES
10 4

Sample Input:

10 9 45

Sample Output:

YES
10 1 10 1 2 1 2 1 6

Sample Input:

10 9 81

Sample Output:

YES
10 1 10 1 10 1 10 1 10

Sample Input:

10 9 82

Sample Output:

题目链接

有1~n栋房子，起始位置是1，输出进过k次移动正好移动s距离的移动过程。

最大可以移动n-1距离，从n-1遍历到1，优先移动远距离，最后用1进行剩下的移动即可。

AC代码:

#include <bits/stdc++.h>
using namespace std;
#define mem(a,b) memset(a,b,sizeof(a))
#define pb push_back
#define mp make_pair
#define lowbit(x) (x&(-x))
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> PII;
typedef pair<double,double> PDD;
const int INF = 0x3f3f3f3f;
const int maxn = 1e5 + 5;
const int mod = 1e9 + 7;
const double eps = 1e-8;
const double pi = asin(1.0) * 2;
const double e = 2.718281828459;
bool Finish_read;
template<class T>inline void read(T &x) {
	Finish_read = 0;
	x = 0;
	int f = 1;
	char ch = getchar();
	while (!isdigit(ch)) {
		if (ch == '-') {
			f = -1;
		}
		if (ch == EOF) {
			return;
		}
		ch = getchar();
	}
	while (isdigit(ch)) {
		x = x * 10 + ch - '0';
		ch = getchar();
	}
	x *= f;
	Finish_read = 1;
};

int main(int argc, char *argv[]) {
#ifndef ONLINE_JUDGE
	freopen("in.txt", "r", stdin);
	freopen("out.txt", "w", stdout);
#endif
	ll n, k, s;
	read(n); read(k); read(s);
	vector<ll> ans;
	ans.pb(1);
	if (k > s || (n - 1) * k < s) {
		printf("NO\n");
		return 0;
	}
	for (int i = n - 1; i > 0; --i) {
		while (s - i >= k - 1 && k > 0) {
			if (ans.back() + i <= n) {
				ans.pb(ans.back() + i);
				s -= i;
				k--;
			}
			else if (ans.back() - i > 0) {
				ans.pb(ans.back() - i);
				s -= i;
				k--;
			}
		}
	}
	printf("YES\n");
	for (int i = 1; i < int(ans.size()); ++i) {
		printf("%lld ", ans[i]);
	}
	printf("\n");
#ifndef ONLINE_JUDGE
	fclose(stdin);
	fclose(stdout);
	system("gedit out.txt");
#endif
    return 0;
}

E1. Stars Drawing (Easy Edition)

Description:

A star is a figure of the following type: an asterisk character ‘*’ in the center of the figure and four rays (to the left, right, top, bottom) of the same positive length. The size of a star is the length of its rays. The size of a star must be a positive number (i.e. rays of length $0$ are not allowed).
Let’s consider empty cells are denoted by ‘.’, then the following figures are stars:

The leftmost figure is a star of size $1$ , the middle figure is a star of size $2$ and the rightmost figure is a star of size $3$ . You are given a rectangular grid of size $n \times m$ consisting only of asterisks ‘*’ and periods (dots) ‘.’. Rows are numbered from $1$ to $n$ , columns are numbered from $1$ to $m$ . Your task is to draw this grid using any number of stars or find out that it is impossible. Stars can intersect, overlap or even coincide with each other. The number of stars in the output can’t exceed $n \cdot m$ . Each star should be completely inside the grid. You can use stars of same and arbitrary sizes.

In this problem, you do not need to minimize the number of stars. Just find any way to draw the given grid with at most $n \cdot m$ stars.

Input:

The first line of the input contains two integers $n$ and $m$ ( $3 \leq n, m \leq 100$ ) — the sizes of the given grid.
The next $n$ lines contains $m$ characters each, the $i$ -th line describes the $i$ -th row of the grid. It is guaranteed that grid consists of characters ‘*’ and ‘.’ only.

Output

If it is impossible to draw the given grid using stars only, print “-1”.
Otherwise in the first line print one integer $k$ ( $0 \leq k \leq n \cdot m$ ) — the number of stars needed to draw the given grid. The next $k$ lines should contain three integers each — $x_{j}$ , $y_{j}$ and $s_{j}$ , where $x_{j}$ is the row index of the central star character, $y_{j}$ is the column index of the central star character and $s_{j}$ is the size of the star. Each star should be completely inside the grid.

Sample Input:

6 8
....*...
...**...
..*****.
...**...
....*...
........

Sample Output:

3
3 4 1
3 5 2
3 5 1

Sample Input:

5 5
.*...
****.
.****
..**.
.....

Sample Output:

3
2 2 1
3 3 1
3 4 1

Sample Input:

5 5
.*...
***..
.*...
.*...
.....

Sample Output:

-1

Sample Input:

3 3
*.*
.*.
*.*

Sample Output:

-1

题目链接

E1和E2两道题目只是数据范围稍有不同，做法一样。

给出一个由’*‘和’.‘组成的矩阵，有多少种由’*‘组成的’十’型图案，若这些图案可以覆盖全部’*‘字符，则输出每个’十’的中心’*‘坐标和长度，若不能全部覆盖输出’-1’。

枚举每一个’*'为’十’的中心，判断标记即可。

AC代码:

#include <bits/stdc++.h>
using namespace std;
#define mem(a,b) memset(a,b,sizeof(a))
#define pb push_back
#define mp make_pair
#define lowbit(x) (x&(-x))
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> PII;
typedef pair<double,double> PDD;
typedef pair<ll,ll> PLL;
const int INF = 0x3f3f3f3f;
const int maxn = 1e2 + 5;
const int mod = 1e9 + 7;
const double eps = 1e-8;
const double pi = asin(1.0) * 2;
const double e = 2.718281828459;
bool Finish_read;
template<class T>inline void read(T &x) {
	Finish_read = 0;
	x = 0;
	int f = 1;
	char ch = getchar();
	while (!isdigit(ch)) {
		if (ch == '-') {
			f = -1;
		}
		if (ch == EOF) {
			return;
		}
		ch = getchar();
	}
	while (isdigit(ch)) {
		x = x * 10 + ch - '0';
		ch = getchar();
	}
	x *= f;
	Finish_read = 1;
};

struct Star {
	int i, j, l;
	Star(int _i = 0, int _j = 0, int _l = 0): i(_i), j(_j), l(_l) {}
};

int n, m;
char plat[maxn][maxn];
bool flag[maxn][maxn];
bool ok;
vector<PII> bit;
vector<Star> ans;

void judge(PII x) {
	int res = 0;
	while (x.first - res - 1 >= 1 &&
			x.first + res + 1 <= n &&
			x.second - res - 1 >= 1 &&
			x.second + res + 1 <= m &&
			plat[x.first - res - 1][x.second] == '*' &&
			plat[x.first + res + 1][x.second] == '*' &&
			plat[x.first][x.second - res - 1] == '*' &&
			plat[x.first][x.second + res + 1] == '*') {
		flag[x.first - res - 1][x.second] = 1;
		flag[x.first + res + 1][x.second] = 1;
		flag[x.first][x.second - res - 1] = 1;
		flag[x.first][x.second + res + 1] = 1;
		res++;
	}
	if (res > 0) {
		flag[x.first][x.second] = 1;
		ans.pb(Star {x.first, x.second, res});
	}
}

int main(int argc, char *argv[]) {
#ifndef ONLINE_JUDGE
	freopen("in.txt", "r", stdin);
	freopen("out.txt", "w", stdout);
#endif
	cin >> n >> m;
	for (int i = 1; i <= n; ++i) {
		for (int j = 1; j <= m; ++j) {
			cin >> plat[i][j];
			if (plat[i][j] == '*') {
				bit.pb(mp(i, j));
			}
		}
	}
	mem(flag, 0);
	for (auto it : bit) {
		judge(it);
	}
	ok = 1;
	for (auto it : bit) {
		if (!flag[it.first][it.second]) {
			ok = 0;
			break;
		}
	}
	if (ok) {
		printf("%d\n", int(ans.size()));
		for (auto it : ans) {
			printf("%d %d %d\n", it.i, it.j, it.l);
		}
	}
	else {
		printf("-1\n");
	}
#ifndef ONLINE_JUDGE
	fclose(stdin);
	fclose(stdout);
	system("gedit out.txt");
#endif
    return 0;
}

E2. Stars Drawing (Hard Edition)

Description:

In this problem, you do not need to minimize the number of stars. Just find any way to draw the given grid with at most $n \cdot m$ stars.

Input:

The first line of the input contains two integers $n$ and $m$ ( $3 \leq n, m \leq 1000$ ) — the sizes of the given grid.
The next $n$ lines contains $m$ characters each, the $i$ -th line describes the $i$ -th row of the grid. It is guaranteed that grid consists of characters ‘*’ and ‘.’ only.

Output

Sample Input:

6 8
……
……
…*.
……
……
…

Sample Output:

3
3 4 1
3 5 2
3 5 1

Sample Input:

5 5
.…
*.
.****
….
…

Sample Output:

3
2 2 1
3 3 1
3 4 1

Sample Input:

5 5
.*…
*…
.…
.…
…

Sample Output:

-1

Sample Input:

3 3
.
.*.
.

Sample Output:

-1

题目链接

同上。

AC代码:

#include <bits/stdc++.h>
using namespace std;
#define mem(a,b) memset(a,b,sizeof(a))
#define pb push_back
#define mp make_pair
#define lowbit(x) (x&(-x))
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> PII;
typedef pair<double,double> PDD;
typedef pair<ll,ll> PLL;
const int INF = 0x3f3f3f3f;
const int maxn = 1e3 + 5;
const int mod = 1e9 + 7;
const double eps = 1e-8;
const double pi = asin(1.0) * 2;
const double e = 2.718281828459;
bool Finish_read;
template<class T>inline void read(T &x) {
	Finish_read = 0;
	x = 0;
	int f = 1;
	char ch = getchar();
	while (!isdigit(ch)) {
		if (ch == '-') {
			f = -1;
		}
		if (ch == EOF) {
			return;
		}
		ch = getchar();
	}
	while (isdigit(ch)) {
		x = x * 10 + ch - '0';
		ch = getchar();
	}
	x *= f;
	Finish_read = 1;
};

struct Star {
	int i, j, l;
	Star(int _i = 0, int _j = 0, int _l = 0): i(_i), j(_j), l(_l) {}
};

int n, m;
char plat[maxn][maxn];
bool flag[maxn][maxn];
bool ok;
vector<PII> bit;
vector<Star> ans;

void judge(PII x) {
	int res = 0;
	while (x.first - res - 1 >= 1 &&
			x.first + res + 1 <= n &&
			x.second - res - 1 >= 1 &&
			x.second + res + 1 <= m &&
			plat[x.first - res - 1][x.second] == '*' &&
			plat[x.first + res + 1][x.second] == '*' &&
			plat[x.first][x.second - res - 1] == '*' &&
			plat[x.first][x.second + res + 1] == '*') {
		flag[x.first - res - 1][x.second] = 1;
		flag[x.first + res + 1][x.second] = 1;
		flag[x.first][x.second - res - 1] = 1;
		flag[x.first][x.second + res + 1] = 1;
		res++;
	}
	if (res > 0) {
		flag[x.first][x.second] = 1;
		ans.pb(Star {x.first, x.second, res});
	}
}

int main(int argc, char *argv[]) {
#ifndef ONLINE_JUDGE
	freopen("in.txt", "r", stdin);
	freopen("out.txt", "w", stdout);
#endif
	cin >> n >> m;
	for (int i = 1; i <= n; ++i) {
		for (int j = 1; j <= m; ++j) {
			cin >> plat[i][j];
			if (plat[i][j] == '*') {
				bit.pb(mp(i, j));
			}
		}
	}
	mem(flag, 0);
	for (auto it : bit) {
		judge(it);
	}
	ok = 1;
	for (auto it : bit) {
		if (!flag[it.first][it.second]) {
			ok = 0;
			break;
		}
	}
	if (ok) {
		printf("%d\n", int(ans.size()));
		for (auto it : ans) {
			printf("%d %d %d\n", it.i, it.j, it.l);
		}
	}
	else {
		printf("-1\n");
	}
#ifndef ONLINE_JUDGE
	fclose(stdin);
	fclose(stdout);
	system("gedit out.txt");
#endif
    return 0;
}