Huahua's Tech Road

花花酱 LeetCode 640. Solve the Equation

By zxi on May 10, 2019

Solve a given equation and return the value of x in the form of string “x=#value”. The equation contains only ‘+’, ‘-‘ operation, the variable x and its coefficient.

If there is no solution for the equation, return “No solution”.

If there are infinite solutions for the equation, return “Infinite solutions”.

If there is exactly one solution for the equation, we ensure that the value of x is an integer.

Example 1:

Input: "x+5-3+x=6+x-2"
Output: "x=2"

Example 2:

Input: "x=x"
Output: "Infinite solutions"

Example 3:

Input: "2x=x"
Output: "x=0"

Example 4:

Input: "2x+3x-6x=x+2"
Output: "x=-1"

Example 5:

Input: "x=x+2"
Output: "No solution"

Solution: Parse the equation

Time complexity: O(n)
Space complexity: O(1)

C++

// Author: Huahua, 0 ms, 8.5 MB

class Solution {

public:

string solveEquation(const string& equation) {

auto parse = [](string_view s) -> vector<int> {

int a{0}, b{0};

int sign = 1;

long t = 0;

bool d = false;

for (char c : s) {

if (isdigit(c)) {

d = true;

t = t * 10 + c - '0';

} else {

if (c == 'x')

a += (d ? t : 1) * sign;

else {

b += t * sign;

sign = c == '+' ? 1 : -1;

}

d = false;

t = 0;

}

b += t * sign;

return {a, b};

};

auto pos = equation.find('=');

auto l = parse(string_view(equation).substr(0, pos));

auto r = parse(string_view(equation).substr(pos + 1));

l[0] -= r[0];

l[1] -= r[1];

if (l[0] == 0)

return l[1] == 0 ? "Infinite solutions" : "No solution";

return "x=" + to_string(-l[1] / l[0]);

}

};

花花酱 LeetCode 838. Push Dominoes

By zxi on May 6, 2019

here are N dominoes in a line, and we place each domino vertically upright.

In the beginning, we simultaneously push some of the dominoes either to the left or to the right.

After each second, each domino that is falling to the left pushes the adjacent domino on the left.

Similarly, the dominoes falling to the right push their adjacent dominoes standing on the right.

When a vertical domino has dominoes falling on it from both sides, it stays still due to the balance of the forces.

For the purposes of this question, we will consider that a falling domino expends no additional force to a falling or already fallen domino.

Given a string “S” representing the initial state. S[i] = 'L', if the i-th domino has been pushed to the left; S[i] = 'R', if the i-th domino has been pushed to the right; S[i] = '.', if the i-th domino has not been pushed.

Return a string representing the final state.

Example 1:

Input: ".L.R...LR..L.."
Output: "LL.RR.LLRRLL.."

Example 2:

Input: "RR.L"
Output: "RR.L"
Explanation: The first domino expends no additional force on the second domino.

Note:

0 <= N <= 10^5
String dominoes contains only 'L‘, 'R' and '.'

Solution: Simulation

Simulate the push process, record the steps from L and R for each domino.
steps(L) == steps(R) => “.”
steps(L) < steps(R) => “L”
steps(L) > steps(R) => “R”

Time complexity: O(n)
Space complexity: O(n)

C++

// Author: Huahua, running time: 24 ms, 15.2 MB

class Solution {

public:

string pushDominoes(string D) {

const int n = static_cast<int>(D.size());

vector<int> L(n, INT_MAX), R(n, INT_MAX);

for (int i = 0; i < n; ++i)

if (D[i] == 'L') {

L[i] = 0;

for (int j = i - 1; j >= 0 && D[j] == '.'; --j)

L[j] = L[j + 1] + 1;

} else if (D[i] == 'R') {

R[i] = 0;

for (int j = i + 1; j < n && D[j] == '.'; ++j)

R[j] = R[j - 1] + 1;

}

for (int i = 0; i < n; ++i)

if (L[i] < R[i]) D[i] = 'L';

else if (L[i] > R[i]) D[i] = 'R';

return D;

}

};

花花酱 LeetCode Weekly Contest 135 (1037, 1038, 1039, 1040)

By zxi on May 4, 2019

LeetCode 1037. Valid Boomerang

Solution: Math
Time complexity: O(1)
Space complexity: O(1)

C++

class Solution {

public:

bool isBoomerang(vector<vector<int>>& points) {

if (points[0] == points[1] ||

points[1] == points[2] ||

points[0] == points[2]) return false;

int dx0 = points[0][0] - points[1][0];

int dy0 = points[0][1] - points[1][1];

int dx1 = points[0][0] - points[2][0];

int dy1 = points[0][1] - points[2][1];

return dy0 * dx1 != dy1 * dx0;

}

};

LeetCode 1038. Binary Search Tree to Greater Sum Tree

Solution: Recursion: right, root, left

Time complexity: O(n)
Space complexity: O(n)

C++

class Solution {

public:

TreeNode* bstToGst(TreeNode* root) {

int s = 0;

function<void(TreeNode*)> dfs = [&](TreeNode* n) {

if (!n) return;

dfs(n->right);

n->val = s += n->val;

dfs(n->left);

};

dfs(root);

return root;

}

};

1039. Minimum Score Triangulation of Polygon

Solution: DP

Init: dp[i][j] = 0 if 0 <= j – i <= 1
dp[i][j] := min score to triangulate A[i] ~ A[j]
dp[i][j] = min{dp[i][k] + dp[k][j] + A[i]*A[k]*A[j]), i < k < j
answer: dp[0][n – 1]

Time complexity: O(n^3)
Space complexity: O(n^2)

C++/bottom-up

class Solution {

public:

int minScoreTriangulation(vector<int>& A) {

const int n = A.size();

vector<vector<int>> dp(n, vector<int>(n));

for (int l = 3; l <= n; ++l)

for (int i = 0; i + l <= n; ++i) {

int j = i + l - 1;

dp[i][j] = INT_MAX;

for (int k = i + 1; k <= j - 1; ++k)

dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j] + A[i] * A[k] * A[j]);

}

return dp[0][n - 1];

}

};

C++/top-down

class Solution {

public:

int minScoreTriangulation(vector<int>& A) {

const int n = A.size();

vector<vector<int>> dp(n, vector<int>(n, INT_MAX));

function<int(int, int)> solve = [&](int i, int j) {

if (j - i <= 1) return 0;

if (dp[i][j] != INT_MAX) return dp[i][j];

dp[i][j] = INT_MAX;

for (int k = i + 1; k <= j - 1; ++k)

dp[i][j] = min(dp[i][j],

solve(i, k) + solve(k, j) + A[i] * A[k] * A[j]);

return dp[i][j];

};

return solve(0, n - 1);

}

};

Python

"Author: Huahua"

from functools import lru_cache

class Solution:

def minScoreTriangulation(self, A: List[int]) -> int:

@lru_cache(None)

def dp(i, j):

return 0 if j - i <= 1 else min(dp(i, k) + dp(k, j) + A[i] * A[k] * A[j] for k in range(i + 1, j))

return dp(0, len(A) - 1)

1040. Moving Stones Until Consecutive II

Solution: Sliding Window

Time complexity: O(nlogn)
Space complexity: O(1)

C++

class Solution {

public:

vector<int> numMovesStonesII(vector<int>& stones) {

const int n = static_cast<int>(stones.size());

sort(begin(stones), end(stones));

int max_steps = max(stones[n - 1] - stones[1] - n + 2,

stones[n - 2] - stones[0] - n + 2);

int min_steps = INT_MAX;

int i = 0;

for (int j = 0; j < n; ++j) {

while (stones[j] - stones[i] >= n) ++i;

if (j - i + 1 == n - 1 && stones[j] - stones[i] == n - 2)

min_steps = min(min_steps, 2);

else

min_steps = min(min_steps, n - (j - i + 1));

}

return {min_steps, max_steps};

}

};

花花酱 LeetCode 851. Loud and Rich

By zxi on May 4, 2019

In a group of N people (labelled 0, 1, 2, ..., N-1), each person has different amounts of money, and different levels of quietness.

For convenience, we’ll call the person with label x, simply “person x“.

We’ll say that richer[i] = [x, y] if person x definitely has more money than person y. Note that richer may only be a subset of valid observations.

Also, we’ll say quiet[x] = q if person x has quietness q.

Now, return answer, where answer[x] = y if y is the least quiet person (that is, the person y with the smallest value of quiet[y]), among all people who definitely have equal to or more money than person x.

Example 1:

Input: richer = [[1,0],[2,1],[3,1],[3,7],[4,3],[5,3],[6,3]], quiet = [3,2,5,4,6,1,7,0]
Output: [5,5,2,5,4,5,6,7]
Explanation: 
answer[0] = 5.
Person 5 has more money than 3, which has more money than 1, which has more money than 0.
The only person who is quieter (has lower quiet[x]) is person 7, but
it isn't clear if they have more money than person 0.

answer[7] = 7.
Among all people that definitely have equal to or more money than person 7
(which could be persons 3, 4, 5, 6, or 7), the person who is the quietest (has lower quiet[x])
is person 7.

The other answers can be filled out with similar reasoning.

Note:

1 <= quiet.length = N <= 500
0 <= quiet[i] < N, all quiet[i] are different.
0 <= richer.length <= N * (N-1) / 2
0 <= richer[i][j] < N
richer[i][0] != richer[i][1]
richer[i]‘s are all different.
The observations in richer are all logically consistent.

Solution: DFS + Memoization

For person i , remember the quietest person who is richer than person i.

Time complexity: O(n^2)
Space complexity: O(n)

C++

// Author: Huahua, running time: 108 ms, 31.6 MB

class Solution {

public:

vector<int> loudAndRich(vector<vector<int>>& richer, vector<int>& quiet) {

const int n = quiet.size();

vector<vector<int>> g(n);

for (const auto& r : richer)

g[r[1]].push_back(r[0]);

vector<int> ans(n, -1);

function<void(int)> dfs = [&](int i) {

if (ans[i] != -1) return;

ans[i] = i;

for (int j : g[i]) {

dfs(j);

if (quiet[ans[j]] < quiet[ans[i]])

ans[i] = ans[j];

}

};

for (int i = 0; i < n; ++i) dfs(i);

return ans;

}

};

花花酱 8 Puzzles – Bidirectional A* vs Bidirectional BFS

By zxi on April 30, 2019

8 Puzzles # nodes expended of 1000 solvable instances

Conclusion:

Nodes expended: BiDirectional A* << A* (Manhattan) <= Bidirectional BFS < A* Hamming << BFS
Running time: BiDirectional A* < Bidirectional BFS <= A* (Manhattan) < A* Hamming << BFS

Code:

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

# Author: Huahua

from collections import deque

import heapq

import numpy as np

import random

import sys

N = 3

def Manhattan(s1, s2):

dist = 0

for i1, d in enumerate(s1):

i2 = s2.index(d)

x1 = i1 % N

y1 = i1 // N

x2 = i2 % N

y2 = i2 // N

dist += abs(x1 - x2) + abs(y1 - y2)

return dist

def Hamming(s1, s2):

return sum(x != y for x, y in zip(s1, s2))

class Node:

dirs = [0, -1, 0, 1, 0]

def __init__(self, state, parent = None, h = 0):

self.state = state

self.parent = parent

self.g = parent.g + 1 if parent else 0

self.h = h

self.f = self.g + self.h

def getMoves(self):

moves = []

index = self.state.index(0)

x = index % N

y = index // N

for i in range(4):

tx = x + Node.dirs[i]

ty = y + Node.dirs[i + 1]

if tx < 0 or ty < 0 or tx == N or ty == N:

continue

i = ty * N + tx

move = list(self.state)

move[index] = move[i]

move[i] = 0

moves.append(tuple(move))

return moves

def print(self):

print(np.reshape(self.state, (N, N)))

def __lt__(self, other):

return self.f < other.f

def AStarSearch(start_state, end_state, heuristic):

def h(s):

return heuristic(s, end_state)

q = []

s = Node(start_state, h=h(start_state))

heapq.heappush(q, s)

opened = {s.state : s.f}

closed = dict()

while q:

n = heapq.heappop(q)

if n.state == end_state:

return n, len(opened), len(closed)

if n.state in closed: continue

closed[n.state] = n.f

for move in n.getMoves():

node = Node(move, n, h(move))

if move in opened and opened[move] <= node.f: continue

opened[node.state] = node.f

heapq.heappush(q, node)

return None, len(opened), len(closed)

def BFS(start_state, end_state):

q = deque()

q.append(Node(start_state))

opened = set(start_state)

closed = 0

while q:

n = q.popleft()

if n.state == end_state:

return n, len(opened), closed

closed += 1

for move in n.getMoves():

if move in opened: continue

opened.add(move)

q.append(Node(move, n))

return None, len(opened), closed

def getRootNode(n):

return getRootNode(n.parent) if n.parent else n

def BidirectionalBFS(start_state, end_state):

def constructPath(p, o):

while o:

t = o.parent

o.parent = p

p, o = o, t

return p

ns = Node(start_state)

ne = Node(end_state)

q = [deque([ns]), deque([ne])]

opened = [{start_state : ns}, {end_state: ne}]

closed = [0, 0]

while q[0]:

l = len(q[0])

while l > 0:

p = q[0].popleft()

closed[0] += 1

for move in p.getMoves():

n = Node(move, p)

if move in opened[1]:

o = opened[1][move]

if getRootNode(n).state == end_state:

o, n = n, o

n = constructPath(n, o.parent)

return n, len(opened[0]) + len(opened[1]), closed[0] + closed[1]

if move in opened[0]: continue

opened[0][move] = n

q[0].append(n)

l -= 1

q.reverse()

opened.reverse()

closed.reverse()

return None, len(opened[0]) + len(opened[1]), closed[0] + closed[1]

def print_path(n):

if not n: return

print_path(n.parent)

n.print()

def solvable(state):

inv = 0

for i in range(N*N):

for j in range(i + 1, N*N):

if all((state[i] > 0, state[j] > 0, state[i] > state[j])):

inv += 1

return inv % 2 == 0

if __name__ == '__main__':

s = [1, 2, 3, 4, 5, 6, 7, 8, 0]

e = [1, 2, 3, 4, 5, 6, 7, 8, 0]

i = 0

while True:

random.shuffle(s)

if not solvable(s): continue

n1, opened1, closed1 = AStarSearch(tuple(s), tuple(e), heuristic=Manhattan)

n2, opened2, closed2 = AStarSearch(tuple(s), tuple(e), heuristic=Hamming)

n3, opened3, closed3 = BFS(tuple(s), tuple(e))

n4, opened4, closed4 = BidirectionalBFS(tuple(s), tuple(e))

print("%d\t%d\t%d\t%d" % (closed1, closed2, closed3, closed4))

sys.stdout.flush()

# print("A*")

# print_path(n1)

# print('---------------')

# print("BFS")

# print_path(n3)

# print('---------------')

# print("Bi-BFS")

# print_path(n4)

# print('---------------')

i += 1

if i == 1000: break

C++ Version

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

178

179

180

181

182

183

184

185

186

187

188

189

190

191

192

193

194

195

196

197

198

199

200

201

202

203

204

205

206

207

208

209

210

211

212

213

214

215

216

217

218

219

220

221

222

223

224

225

226

227

228

229

230

231

232

233

234

235

236

237

238

239

240

241

242

243

244

245

246

247

248

249

250

251

252

253

254

255

256

257

258

259

260

261

262

263

264

265

266

267

268

269

270

271

272

273

274

275

276

277

278

279

280

281

282

283

284

285

286

287

288

289

290

291

292

293

294

295

296

297

298

299

300

301

302

303

304

305

306

307

308

309

310

311

312

313

314

315

316

317

318

319

320

321

322

323

324

325

#include <algorithm>

#include <array>

#include <chrono>

#include <deque>

#include <functional>

#include <iostream>

#include <memory>

#include <queue>

#include <unordered_map>

#include <unordered_set>

#include <vector>

using namespace std;

using chrono::high_resolution_clock;

constexpr int N = 3;

constexpr int dirs[] = {0, 1, 0, -1, 0};

struct Node;

typedef string State;

typedef shared_ptr<Node> NodePtr;

typedef function<int(const State& s, const State& t)> Heuristic;

struct Node {

Node(State s, NodePtr p = nullptr, int h = 0)

: s(s), p(p), h(h), g(p ? p->g + 1 : 0), f(this->h + g) {}

vector<State> GetNextStates() const {

vector<State> states;

int index = find(s.begin(), s.end(), '0') - s.begin();

int x = index % N;

int y = index / N;

for (int i = 0; i < 4; ++i) {

int tx = x + dirs[i];

int ty = y + dirs[i + 1];

if (tx < 0 || ty < 0 || tx == N || ty == N) continue;

int new_index = ty * N + tx;

State next(s);

next[index] = s[new_index];

next[new_index] = '0';

states.push_back(move(next));

}

return states;

}

NodePtr p;

int h;

int g;

int f;

State s;

};

bool Sovlable(const State& s) {

int inv_count = 0;

for (int i = 0; i < N * N; ++i) {

for (int j = i + 1; j < N * N; ++j) {

if (s[i] != '0' && s[j] != '0' && s[i] > s[j]) {

++inv_count;

}

return inv_count % 2 == 0;

}

NodePtr GetRoot(NodePtr n) { return n->p ? GetRoot(n->p) : n; }

NodePtr WirePath(NodePtr p, NodePtr n) {

while (n) {

NodePtr t = n->p;

n->p = p;

p = n;

n = t;

}

return p;

}

void ConstructPath(NodePtr node, vector<State>* path) {

while (node) {

path->push_back(node->s);

node = node->p;

}

reverse(path->begin(), path->end());

}

class Solver {

public:

virtual bool Solve(State start, State target, vector<State>* path,

int* opened, int* closed) = 0;

};

class BFSSolver : public Solver {

public:

bool Solve(State start, State target, vector<State>* path, int* opened,

int* closed) override {

int expended = 0;

unordered_set<string> seen;

deque<NodePtr> q{make_shared<Node>(start)};

while (!q.empty()) {

auto cur = q.front();

q.pop_front();

++expended;

if (cur->s == target) {

ConstructPath(cur, path);

*opened = seen.size();

*closed = expended;

return true;

}

for (const auto& s : cur->GetNextStates()) {

auto r = seen.insert(s);

if (!r.second) continue;

q.push_back(make_shared<Node>(s, cur));

}

return false;

}

};

class BidirectionalBFSSolver : public Solver {

public:

bool Solve(State start, State target, vector<State>* path, int* opened,

int* closed) override {

auto start_node = make_shared<Node>(start);

auto target_node = make_shared<Node>(target);

unordered_map<string, NodePtr> seen0{{start, start_node}};

unordered_map<string, NodePtr> seen1{{target, target_node}};

deque<NodePtr> q0{start_node};

deque<NodePtr> q1{target_node};

int expended = 0;

while (!q0.empty()) {

size_t size = q0.size();

while (size--) {

auto cur = q0.front();

q0.pop_front();

++expended;

for (const auto& s : cur->GetNextStates()) {

auto n = make_shared<Node>(s, cur);

auto it = seen1.find(s);

if (it != seen1.end()) {

auto p = it->second;

if (GetRoot(n)->s == target) swap(n, p);

n = WirePath(n, p->p);

ConstructPath(n, path);

*opened = seen0.size() + seen1.size();

*closed = expended;

return true;

}

if (seen0.count(s)) continue;

seen0[s] = n;

q0.push_back(n);

}

if (q1.size() < q0.size()) {

swap(q0, q1);

swap(seen0, seen1);

}

return false;

}

private:

};

struct NodeCompare : public binary_function<NodePtr, NodePtr, bool> {

bool operator()(const NodePtr& x, const NodePtr& y) const {

return x->f > y->f;

}

};

int ManhattanDistance(const State& s, const State& t) {

int h = 0;

for (int i1 = 0; i1 < N * N; ++i1) {

int i2 = t.find(s[i1]);

int x1 = i1 % N;

int y1 = i1 / N;

int x2 = i2 % N;

int y2 = i2 / N;

h += abs(x1 - x2) + abs(y1 - y2);

}

return h;

}

int HammingDistance(const State& s, const State& t) {

int h = 0;

for (size_t i = 0; i < s.size(); ++i) {

if (s[i] != t[i]) ++h;

}

return h;

}

class AStarSolver : public Solver {

public:

explicit AStarSolver(Heuristic heuristic) : heuristic_(heuristic) {}

bool Solve(State start, State target, vector<State>* path, int* opened,

int* closed) override {

unordered_map<string, NodePtr> o;

unordered_set<string> c;

priority_queue<NodePtr, vector<NodePtr>, NodeCompare> q;

q.emplace(new Node(start, nullptr, heuristic_(start, target)));

while (!q.empty()) {

auto cur = q.top();

q.pop();

if (cur->s == target) {

ConstructPath(cur, path);

*opened = o.size();

*closed = c.size();

return true;

}

if (!c.insert(cur->s).second) continue;

for (const auto& s : cur->GetNextStates()) {

auto it = o.find(s);

auto n = make_shared<Node>(s, cur, heuristic_(s, target));

if (it != o.end() && n->f >= it->second->f) continue;

o[s] = n;

q.push(n);

}

return false;

}

private:

Heuristic heuristic_;

};

class BiAStarSolver : public Solver {

public:

explicit BiAStarSolver(Heuristic heuristic) : heuristic_(heuristic) {}

bool Solve(State start, State target, vector<State>* path, int* opened,

int* closed) override {

unordered_map<string, NodePtr> o0, o1;

unordered_map<string, NodePtr> c0, c1;

priority_queue<NodePtr, vector<NodePtr>, NodeCompare> q0, q1;

q0.emplace(new Node(start, nullptr, heuristic_(start, target)));

q1.emplace(new Node(target, nullptr, heuristic_(target, start)));

bool farward = true;

while (!q0.empty()) {

auto size = q0.size();

while (size--) {

auto cur = q0.top();

q0.pop();

if (c0.count(cur->s)) continue;

c0[cur->s] = cur;

if (c1.count(cur->s)) {

auto p = c1[cur->s];

if (GetRoot(cur)->s == target) swap(cur, p);

cur = WirePath(cur, p->p);

ConstructPath(cur, path);

*opened = o0.size() + o1.size();

*closed = c0.size() + c1.size();

return true;

}

for (const auto& s : cur->GetNextStates()) {

auto it = o0.find(s);

auto n = make_shared<Node>(s, cur,

heuristic_(s, farward ? target : start));

if (it != o0.end() && n->f >= it->second->f) continue;

o0[s] = n;

q0.push(n);

}

if (q1.size() < q0.size()) {

swap(q0, q1);

swap(c0, c1);

swap(o0, o1);

farward = !farward;

}

return false;

}

private:

Heuristic heuristic_;

};

bool VerifyPath(const vector<State>& path, const State& s, const State& t) {

if (path.empty()) return false;

if (path.front() != s || path.back() != t) return false;

for (size_t i = 1; i < path.size(); ++i) {

Node n(path[i - 1]);

auto states = n.GetNextStates();

if (find(begin(states), end(states), path[i]) == end(states)) {

return false;

}

return true;

}

void StatisticsMode() {

State s{"123456780"};

State t{"123456780"};

vector<unique_ptr<Solver>> solvers;

solvers.emplace_back(new BFSSolver);

solvers.emplace_back(new AStarSolver(HammingDistance));

solvers.emplace_back(new AStarSolver(ManhattanDistance));

solvers.emplace_back(new BidirectionalBFSSolver);

solvers.emplace_back(new BiAStarSolver(ManhattanDistance));

for (int i = 0; i < 1000;) {

random_shuffle(s.begin(), s.end());

if (!Sovlable(s)) continue;

++i;

for (auto& solver : solvers) {

vector<State> path;

int opened;

int closed;

auto t0 = high_resolution_clock::now();

bool sovlable = solver->Solve(s, t, &path, &opened, &closed);

auto t1 = high_resolution_clock::now();

if (!VerifyPath(path, s, t)) {

cerr << "Invalid path!" << endl;

return;

}

auto time_span = chrono::duration_cast<chrono::duration<double>>(t1 - t0);

cout << closed << "\t" << time_span.count() * 1000 << "\t";

}

cout << endl;

}

int main() { StatisticsMode(); }