#pragma once
/*
* STRICT.H
* Tool for validation of input data for the programming contest problems
* Copyright (c) Vladimir Yakovlev, 2011-2014
* http://acm.timus.ru/stricth
* Version 0.2
*
* History:
* 22.07.2011 v.0.1. first release
* 17.01.2014 v.0.2. new features added
*/
#include <stdio.h>
#include <stdarg.h>
#include <stdlib.h>
#include <string.h>
#include <string>
#include <vector>
#include <queue>
#include <map>
#include <algorithm>
#if (_WIN32 || __WIN32__)
#include <fcntl.h>
#include <io.h>
#define ON_WINDOWS
#endif
/* interface */
class Input
{
FILE* m_file;
int c;
int line;
int pos;
void setBinaryMode();
void nextChar();
void assertDigit();
void init();
void parsePattern(const char* charPattern, bool valid[256]);
public:
Input();
Input(const char* fileName);
~Input();
bool isSpace() const;
bool isWhitespace() const;
bool isEoln() const;
bool isEof() const;
void readSpace();
void readOneOrMoreSpaces();
void readEoln();
void readSpaceOrEoln();
void readEof();
int readChar();
std::string readToken();
// charPattern is a list of correct chars like "SWNE" or a range of chars like "0-9"
// or a combination of them like "-_a-zA-Z"
std::string readToken(int minLength, int maxLength, const char* charPattern);
// read whole line and advance to the beginning of the next line
std::string readLine();
std::string readLine(int minLength, int maxLength, const char* charPattern);
int readInt(int minValue, int maxValue);
long long readLong(long long minValue, long long maxValue);
unsigned long long readULong(unsigned long long minValue, unsigned long long maxValue);
double readDouble(double minValue, double maxValue, int maxDigits);
// read an array of ints separated by single spaces
std::vector<int> readIntVector(int count, int minValue, int maxValue);
// read an array of ints each in a separate lines,
// advance to the beginning of the next line
std::vector<int> readIntVectorLines(int count, int minValue, int maxValue);
void _assert(bool noerror, const char* expr);
void error(const char* fmt, ...);
private:
Input(const Input&);
Input& operator =(const Input&);
};
#undef assert
#define assert(expr) _assert((expr), #expr)
void error(const char* fmt, ...);
bool isConnected(int n, const std::vector< std::pair<int, int> >& edges);
void assertTree(const std::vector< std::pair<int, int> >& tree);
void assertConnected(int n, const std::vector< std::pair<int, int> >& edges);
void assertPrime(int p);
void assertSum(const std::vector<int>& values, long long minValue, long long maxValue);
// verifies that all values in the given vector are distinct
template<typename T>
void assertDistinct(const std::vector<T>& values);
// verifies that the sequence of values in the given vector is monotone
// in the way described by the relation:
// "<" each term is less than the following one (strictly increasing sequence)
// "<=" each term is less than or equal to the following one (nondecreasing sequence)
// ">" each term is greater than the following one (strictly decreasing sequence)
// ">=" each term is greater than or equal to the following one (nonincreasing sequence)
template<typename T>
void assertMonotone(const std::vector<T>& values, const char* relation);
/* implementation */
void Input::setBinaryMode()
{
#ifdef ON_WINDOWS
#ifdef STDIN_FILENO
int stdinFileno = STDIN_FILENO;
#else
int stdinFileno = _fileno(stdin);
#endif
if (_setmode(stdinFileno, O_BINARY) == -1)
::error("Cannot set stdin to binary mode");
#endif
}
void Input::nextChar()
{
if (isEoln())
{
line++;
pos = 1;
}
else
pos++;
c = getc(m_file);
#ifdef ON_WINDOWS
if (c == 10)
error("Unix style EOLN");
if (c == 13)
{
c = getc(m_file);
if (c != 10)
error("Character 13 without 10");
}
#else
if (c == 13)
error("Windows style EOLN");
#endif
}
void Input::assertDigit()
{
if (c >= '0' && c <= '9')
return;
if (isEof())
error("EOF instead of number");
if (isEoln())
error("EOLN instead of number");
if (isSpace())
error("SPACE instead of number");
if (c == '\t')
error("TAB instead of number");
error("'%c' instead of number", (char)c);
}
void Input::init()
{
line = 1;
pos = 0;
c = 0;
nextChar();
}
void Input::parsePattern(const char* charPattern, bool valid[256])
{
for (int b = 0; b < 256; b++)
valid[b] = false;
for (int i = 0; charPattern[i]; i++)
{
unsigned char u = (unsigned char)charPattern[i];
if (u == '-' && i > 0 && charPattern[i + 1])
{
unsigned char from = (unsigned char)charPattern[i - 1];
unsigned char to = (unsigned char)charPattern[i + 1];
if (from > to)
error("wrong pattern: '%s'", charPattern);
for (int v = from; v <= to; v++)
valid[v] = true;
}
else
{
valid[u] = true;
}
}
}
Input::Input()
{
setBinaryMode();
m_file = stdin;
init();
}
Input::Input(const char* fileName)
{
m_file = fopen(fileName, "rb");
if (!m_file)
::error("Cannot open file %s", fileName);
init();
}
Input::~Input()
{
fclose(m_file);
}
bool Input::isWhitespace() const
{
return c == ' ' || c == '\t' || c == '\n';
}
bool Input::isSpace() const
{
return c == ' ';
}
bool Input::isEoln() const
{
return c == '\n';
}
bool Input::isEof() const
{
return c == EOF;
}
void Input::readSpace()
{
if (!isSpace())
error("SPACE expected");
nextChar();
}
void Input::readOneOrMoreSpaces()
{
if (!isSpace())
error("SPACE expected");
nextChar();
while (isSpace())
nextChar();
}
void Input::readEoln()
{
if (!isEoln())
error("EOLN expected");
nextChar();
}
void Input::readSpaceOrEoln()
{
if (!isSpace() && !isEoln())
error("EOLN or SPACE expected");
nextChar();
}
void Input::readEof()
{
if (!isEof())
error("EOF expected");
}
int Input::readChar()
{
if (isEof())
error("EOF instead of char");
int oldc = c;
nextChar();
return oldc;
}
std::string Input::readToken()
{
if (isEof())
error("EOF instead of token");
if (isWhitespace())
error("whitespace instead of token");
std::string res;
while (!isWhitespace() && !isEof())
{
res += (char)c;
nextChar();
}
return res;
}
std::string Input::readToken(int minLength, int maxLength, const char* charPattern)
{
bool valid[256];
parsePattern(charPattern, valid);
if (isEof())
error("EOF instead of token");
if (isWhitespace())
error("whitespace instead of token");
std::string res;
while (!isWhitespace() && !isEof())
{
res += (char)c;
if ((int)res.length() > maxLength)
error("the length of token exceeded %d", maxLength);
if (!valid[c])
error("character '%c' does not match pattern '%s'", (char)c, charPattern);
nextChar();
}
if ((int)res.length() < minLength)
error("the length of token is less than %d", minLength);
return res;
}
std::string Input::readLine()
{
std::string res;
while (!isEoln())
{
if (isEof())
error("EOF instead of EOLN");
res += (char)c;
nextChar();
}
nextChar();
return res;
}
std::string Input::readLine(int minLength, int maxLength, const char* charPattern)
{
bool valid[256];
parsePattern(charPattern, valid);
std::string res;
while (!isEoln())
{
if (isEof())
error("EOF instead of EOLN");
res += (char)c;
if ((int)res.length() > maxLength)
error("the length of line exceeded %d", maxLength);
if (!valid[c])
error("character '%c' does not match pattern '%s'", (char)c, charPattern);
nextChar();
}
if ((int)res.length() < minLength)
error("the length of line is less than %d", minLength);
nextChar();
return res;
}
int Input::readInt(int minValue, int maxValue)
{
return (int)readLong(minValue, maxValue);
}
long long Input::readLong(long long minValue, long long maxValue)
{
bool minus = false;
long long x = 0;
if (c == '-')
{
minus = true;
nextChar();
}
assertDigit();
if (c == '0')
{
nextChar();
if (c >= '0' && c <= '9')
error("integer with leading zero");
else if (minus)
error("minus zero");
}
else
{
const long long MIN_LONG = 0x8000000000000000ll;
const long long MIN_LONG_DIV10 = MIN_LONG / 10;
const long long MIN_LONG_MOD10 = -(MIN_LONG % 10);
const long long MAX_LONG = 0x7fffffffffffffffll;
const long long MAX_LONG_DIV10 = MAX_LONG / 10;
const long long MAX_LONG_MOD10 = MAX_LONG % 10;
while (c >= '0' && c <= '9')
{
long long digit = c - '0';
if (minus)
{
if (x < MIN_LONG_DIV10 || (x == MIN_LONG_DIV10 && digit > MIN_LONG_MOD10))
error("overflow of 64-bit signed integer");
x = x * 10 - digit;
}
else
{
if (x > MAX_LONG_DIV10 || (x == MAX_LONG_DIV10 && digit > MAX_LONG_MOD10))
error("overflow of 64-bit signed integer");
x = x * 10 + digit;
}
nextChar();
}
}
if (x < minValue || x > maxValue)
error("integer %lld is out of bounds [%lld, %lld]", x, minValue, maxValue);
return x;
}
unsigned long long Input::readULong(unsigned long long minValue, unsigned long long maxValue)
{
unsigned long long x = 0;
assertDigit();
if (c == '0')
{
nextChar();
if (c >= '0' && c <= '9')
error("integer with leading zero");
}
else
{
const unsigned long long MAX_ULONG = 0xffffffffffffffffull;
const unsigned long long MAX_ULONG_DIV10 = MAX_ULONG / 10ull;
const unsigned long long MAX_ULONG_MOD10 = MAX_ULONG % 10ull;
while (c >= '0' && c <= '9')
{
unsigned long long digit = c - '0';
if (x > MAX_ULONG_DIV10 || (x == MAX_ULONG_DIV10 && digit > MAX_ULONG_MOD10))
error("overflow of 64-bit unsigned integer");
x = x * 10u + digit;
nextChar();
}
}
if (x < minValue || x > maxValue)
error("integer %llu is out of bounds [%llu, %llu]", x, minValue, maxValue);
return x;
}
double Input::readDouble(double minValue, double maxValue, int maxDigits)
{
bool minus = false;
bool wasDigit = false;
double x = 0.0;
if (c == '-')
{
minus = true;
nextChar();
}
if (c == '0')
{
nextChar();
if (c >= '0' && c <= '9')
error("double with leading zero");
wasDigit = true;
}
while (c >= '0' && c <= '9')
{
x = x * 10.0 + (c - '0');
nextChar();
wasDigit = true;
}
if (c == '.')
{
if (!wasDigit)
error("double starts with dot");
nextChar();
if (c < '0' || c > '9')
error("double ends with dot");
double y = 0.1;
for (int k = 1; c >= '0' && c <= '9'; k++)
{
if (k > maxDigits)
error("more than %d digits after decimal point", maxDigits);
x += y * (double)(c - '0');
y *= 0.1;
nextChar();
wasDigit = true;
}
}
if (!wasDigit)
assertDigit();
if (minus && x == 0.0)
error("minus zero");
if (minus)
x = -x;
if (minValue - x > 1e-10 || x - maxValue > 1e-10)
error("number %g is out of bounds [%g, %g]", x, minValue, maxValue);
return x;
}
std::vector<int> Input::readIntVector(int count, int minValue, int maxValue)
{
std::vector<int> result;
for (int i = 0; i < count; i++)
{
if (i > 0)
readSpace();
result.push_back(readInt(minValue, maxValue));
}
return result;
}
std::vector<int> Input::readIntVectorLines(int count, int minValue, int maxValue)
{
std::vector<int> result;
for (int i = 0; i < count; i++)
{
result.push_back(readInt(minValue, maxValue));
readEoln();
}
return result;
}
void Input::_assert(bool noerror, const char* expr)
{
if (!noerror)
error("condition failed: %s ", expr);
}
void Input::error(const char* fmt, ...)
{
va_list argptr;
va_start(argptr, fmt);
fprintf(stderr, "Line %d, pos %d: ", line, pos);
vfprintf(stderr, fmt, argptr);
fprintf(stderr, " ");
va_end(argptr);
exit(1);
}
void error(const char* fmt, ...)
{
va_list argptr;
va_start(argptr, fmt);
vfprintf(stderr, fmt, argptr);
fprintf(stderr, " ");
va_end(argptr);
exit(1);
}
bool isConnected(int n, const std::vector< std::pair<int, int> >& edges)
{
std::vector<bool> used(n, false);
std::vector< std::vector<int> > adj(n);
std::queue<int> q;
for (unsigned int i = 0; i < edges.size(); i++)
{
if (edges[i].first < 1 || edges[i].first > n)
error("Incorrect vertex number: %d", edges[i].first);
if (edges[i].second < 1 || edges[i].second > n)
error("Incorrect vertex number: %d", edges[i].second);
adj[edges[i].first - 1].push_back(edges[i].second - 1);
adj[edges[i].second - 1].push_back(edges[i].first - 1);
}
used[0] = true;
q.push(0);
while (!q.empty())
{
int x = q.front();
q.pop();
for (unsigned int j = 0; j < adj[x].size(); j++)
{
int y = adj[x][j];
if (!used[y])
{
used[y] = true;
q.push(y);
}
}
}
for (int u = 0; u < n; u++)
if (!used[u])
return false;
return true;
}
void assertTree(const std::vector< std::pair<int, int> >& tree)
{
if (!isConnected((int)tree.size() + 1, tree))
error("Graph is not a tree");
}
void assertConnected(int n, const std::vector< std::pair<int, int> >& edges)
{
if (!isConnected(n, edges))
error("Graph is not connected");
}
void assertPrime(int p)
{
int i;
for (i = 2; i * i <= p; i++)
if (p % i == 0) break;
if (p < 2 || i * i <= p)
error("Number is not a prime: %d", p);
}
void assertSum(const std::vector<int>& values, long long minValue, long long maxValue)
{
long long sum = 0;
for (unsigned int i = 0; i < values.size(); i++)
sum += values[i];
if (sum < minValue || sum > maxValue)
error("The sum of array %lld is out of bounds [%lld, %lld]", sum, minValue, maxValue);
}
template<typename T>
void assertDistinct(const std::vector<T>& values)
{
std::map<T, int> index;
for (unsigned int i = 0; i < values.size(); i++)
{
if (!index.insert(std::pair<T, int>(values[i], i)).second)
error("Duplicate elements at positions %d and %d", index[values[i]] + 1, i + 1);
}
}
template<typename T>
void assertMonotone(const std::vector<T>& values, const char* relation)
{
int rel = 0;
if (!strcmp(relation, "<"))
rel = 1;
else if (!strcmp(relation, "<="))
rel = 2;
else if (!strcmp(relation, ">"))
rel = 3;
else if (!strcmp(relation, ">="))
rel = 4;
else
error("Wrong relation: '%s'", relation);
for (unsigned int i = 1; i < values.size(); i++)
{
const T& x = values[i - 1];
const T& y = values[i];
if (!(rel == 1 && x < y || rel == 2 && x <= y || rel == 3 && x > y || rel == 4 && x >= y))
error("The sequence is not monotone: wrong relation at positions %d and %d", i, i + 1);
}
}