1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
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
#include <climits>
#include <cstring>
#include <iostream>
#include <numeric>
#include <vector>

using namespace std;

typedef unsigned long UINT;
typedef signed long SINT;
typedef unsigned long long UINT64;
typedef signed long long SINT64;

[[maybe_unused]] constexpr SINT MAX_SINT = LONG_MAX;
[[maybe_unused]] constexpr UINT MAX_UINT = ULONG_MAX;
[[maybe_unused]] constexpr SINT MAX_SINT64 = LLONG_MAX;
[[maybe_unused]] constexpr UINT MAX_UINT64 = ULLONG_MAX;

// TODO optimize queue
// - vector with pre-reserved size will be okay as it has double-ended access
// - no need to remove queue elems, just skip them
// - mark area under ananlysis (unless it's done already) to avoid repetitive
//   queue items

// Benchmark
#ifdef LOCAL
#include "../benchmark.h"
#define BENCH_START bench_time_start();
#define BENCH_M_START(comment) bench_meth_start(comment);
#define BENCH_M_END bench_meth_end();
#else
#define BENCH_START
#define BENCH_M_START(comment)
#define BENCH_M_END
#endif

/** Redirect stdin to provide input with Qt Creator */
void reopenInput(int argc, char** argv) {
#ifdef LOCAL
	if (argc > 1) {
		auto inFile = argv[1];
		cerr << "Reopening stdin to: " << inFile << endl;
		auto success = freopen(inFile, "r", stdin);
		if (!success) {
			cerr << "Error when opening file!" << endl;
			cerr << std::strerror(errno) << endl;
		}
	}
#endif
}

/* -------------------------------------------------------------------------- */
/* -------------------------------------------------------------------------- */
/* -------------------------------------------------------------------------- */

enum Direction {XAsc, YAsc, XDesc, YDesc};

struct Area {
	UINT time = MAX_UINT;
	bool danger;
};

typedef pair<UINT,UINT> Move;

#define AREA(row,col) map[row][col]

static Area map[2000][2000];
static vector<Move> moves;

static UINT hikers_count;
static UINT rows, columns, danger_count;

void buildMap()
{
	BENCH_M_START("buildMap")
	char row[2000];
	danger_count = 0;

	for (UINT i = 0; i < rows; i++) {
		cin >> row;
		for (UINT j = 0; j < columns; j++) {
			bool danger = row[j] == 'X';
			AREA(i, j).danger = danger;
			if (danger) danger_count++;
		}
	}
	BENCH_M_END
}

void printMap()
{
	for (UINT i = 0; i < rows; i++) {
		for (UINT j = 0; j < columns; j++) {
			auto& a = AREA(i, j);
			char c;
			if (a.danger) {
				c = 'X';
			} else if (a.time == MAX_UINT) {
				c = '.';
			} else {
				c = '0' + a.time % 10;
			}
			cerr << c;
		}
		cerr << endl;
	}
}

void go(const UINT row, const UINT col, const UINT time)
{
	auto& a = AREA(row, col);
	if (!a.danger && a.time > time) {
		a.time = time;
		moves.push_back(Move(row, col));
	}
}

/**
 * @brief findPath
 *
 * It can be easily proven that the less moves, the better time will be,
 * no matter what hiker's speed is.
 *
 * Hence:
 * - all hikers will share the best path, no need to re-calculate every time
 * - the preferred strategy is FIFO queue with trying moves towards top first
 */
void findPath(UINT& ascensions, UINT& descensions)
{
	if (danger_count < rows && danger_count < columns) {
		// A path without descensions must exist.
		ascensions = rows + columns - 2;
		descensions = 0;
		return;
	}

	BENCH_M_START("findPath")

	moves.reserve(rows*columns);
	go(0, 0, 0);

	for(UINT i = 0; i < moves.size(); i++) {
		Move& m = moves[i];
		auto row = m.first;
		auto col = m.second;
		auto time = AREA(row, col).time;

		// try other moves
		if (row < rows - 1)
			go(row+1, col, time + 1);
		if (col < columns - 1)
			go(row, col+1, time + 1);
		if (row > 0)
			go(row-1, col, time + 1);
		if (col > 0)
			go(row, col-1, time + 1);

//		TODO avoid even trying going straight back
//		if (m.dir != XAsc)
//		if (m.dir != XDesc)
//		if (m.dir != YAsc)
//		if (m.dir != YDesc)
	}

#ifdef VERBOSE
	cerr << "Resolved map:" << endl;
	printMap();
#endif

	UINT total_length = AREA(rows-1, columns-1).time;
	descensions = (total_length + 2 - rows - columns) / 2;
	ascensions = total_length - descensions;
	cerr << "Hikers will ascend " << ascensions << " times "
		 << "and descend " << descensions << " times." << endl;
	BENCH_M_END
}

/// Moves times speed can gives 64-bit number, hence UINT64 is used here.
void solve(UINT64 ascensions, UINT64 descensions)
{
	UINT64 best_time = MAX_UINT64;
	UINT best_count = 0;

	for (UINT hiker = 1; hiker <= hikers_count; hiker++) {
		UINT64 time_asc, time_desc;
		cin >> time_asc >> time_desc;
		UINT64 time = ascensions * time_asc + descensions * time_desc;

		if (time < best_time) {
			best_time = time;
			best_count = 1;
		} else if (time == best_time) {
			best_count++;
		}

#ifdef VERBOSE
		cerr << endl << "Hiker " << hiker << " has time " << time;
		if (time == best_time && best_count == 1) {
			cerr << ", it's a new record!";
		} else if (time == best_time) {
			cerr << ", he is one of the best (" << best_count << ")!";
		}
#endif
	}
	cerr << endl << flush;

	cout << best_time << " " << best_count << endl << flush;
}

int main(int argc, char** argv)
{
	BENCH_START
	std::ios_base::sync_with_stdio(false);
	reopenInput(argc, argv);

	cin >> rows >> columns >> hikers_count;
	buildMap();

#ifdef VERBOSE
	printMap();
#endif

	cerr << "Map size: "
		 << rows << "x" << columns << " (rows x columns)" << endl;

	cerr << "There are " << danger_count << " danger zones on the map." << endl;

	UINT descensions, ascensions;
	findPath(ascensions, descensions);

	solve(ascensions, descensions);
	return 0;
}