/******************************************************************************
Online C++ Compiler.
Code, Compile, Run and Debug C++ program online.
Write your code in this editor and press "Run" button to compile and execute it.
*******************************************************************************/
#include <iostream>
#include <string>
#include <cstring>
using namespace std;
class Integer
{
int m_value;
public:
Integer() {}
Integer(int val) {
m_value = val;
}
inline operator int () const {
return m_value;
}
int operator % (int val) const {
if (val == 0)
throw("Mod by zero!");
return m_value % val;
}
int operator / (int val) const {
if (val == 0)
throw("Divide by zero!");
return m_value / val;
}
inline int operator * (int val) const {
return m_value * val;
}
};
bool isNumber(char ch) {
return ch >= '0' && ch <= '9';
}
class String
{
string m_value;
public:
String() {}
String(const string& val) {
m_value = val;
}
String(const char* val) {
m_value = val;
}
String(int val) {
int _val = (val < 0) ? -val : val;
do {
m_value += (_val % 10) + '0';
_val /= 10;
}
while (_val != 0);
if (val < 0)
m_value += '-';
m_value = reverse();
}
inline operator string () const {
return m_value;
}
inline size_t length() const {
return m_value.length();
}
inline String& operator += (char ch) {
m_value += ch;
return *this;
}
void assertValid() const {
if (length() == 0)
throw("Not valid String!");
if (length() == 1 && !isNumber(m_value[0]))
throw("Not valid String");
size_t n = 0;
if (length() > 1 && m_value[0] == '-')
n = 1;
for (; n < length(); ++n)
if (!isNumber(m_value[n]))
throw("Not valid String!");
}
inline bool equalsZero() const {
assertValid();
size_t n = 0;
if (m_value[0] == '-')
n = 1;
for (; n < length(); ++n)
if (m_value[n] != '0')
return false;
return true;
}
bool isPositive() const {
return m_value[0] != '-';
}
bool operator == (const char* val) const {
size_t len = strlen(val);
if (length() != len)
return false;
for (size_t n = 0; n < length(); ++n)
if (m_value[n] != val[n])
return false;
return true;
}
inline bool operator != (const char* val) const {
return ! (*this == val);
}
inline String insert(size_t n, char ch) {
m_value.insert(n, 1, ch);
return *this;
}
String leadZero() const {
String result;
size_t n = 0;
bool pos = isPositive();
if (! pos)
n = 1;
for (; n < length() - 1; ++n)
if (m_value[n] != '0')
break;
for (; n < length(); ++n)
result += m_value[n];
if (result == "0")
return result;
if (!pos)
result.insert(0, '-');
return result;
}
String reverse() const {
String result;
if (length() != 0)
for (size_t n = length(); n > 0; --n)
result += m_value[n - 1];
return result;
}
inline char operator [] (size_t n) const {
return m_value[n];
}
String absolute() const {
String result;
size_t n = 0;
if (! isPositive())
n = 1;
for (; n < length() - 1; ++n)
if (m_value[n] != '0')
break;
for (; n < length(); ++n)
result += m_value[n];
return result;
}
bool operator < (const String& val) const {
if (equalsZero() && val.equalsZero())
return false;
if (!isPositive() && val.isPositive())
return true;
if (isPositive() && !val.isPositive())
return false;
String _this = absolute();
String _val = val.absolute();
if (_this.length() < _val.length())
return isPositive();
else if (_this.length() > _val.length())
return !isPositive();
for (size_t n = 0; n < length(); ++n)
if (_this[n] < _val[n])
return isPositive();
else if (_this[n] > _val[n])
return !isPositive();
return false;
}
inline bool operator >= (const String& val) const {
return ! (*this < val);
}
inline bool operator <= (const String& val) const {
if (equalsZero() && val.equalsZero())
return true;
if (!isPositive() && val.isPositive())
return true;
if (isPositive() && !val.isPositive())
return false;
String _this = absolute();
String _val = val.absolute();
if (_this.length() < _val.length())
return isPositive();
else if (_this.length() > _val.length())
return !isPositive();
for (size_t n = 0; n < length(); ++n)
if (_this[n] < _val[n])
return isPositive();
else if (_this[n] > _val[n])
return !isPositive();
return true;
}
bool operator == (const String& val) const {
String _this = leadZero();
String _val = val.leadZero();
if (_this.length() != _val.length())
return false;
for (size_t n = 0; n < _this.length(); ++n)
if (_this[n] != _val[n])
return false;
return true;
}
String operator + (const String& val) const {
if (equalsZero())
return val;
if (val.equalsZero())
return *this;
bool pos = isPositive();
if (pos) {
if (!val.isPositive())
return *this - val.absolute();
}
else {
if (val.isPositive())
return val - absolute();
}
String _this = absolute().reverse();
String _val = val.absolute().reverse();
while (_this.length() < _val.length())
_this += '0';
String result;
char carry = 0;
for (size_t n = 0; n < _this.length(); ++n) {
int nn;
if (n < _val.length())
nn = (_this[n] - '0') + (_val[n] - '0') + carry;
else
nn = (_this[n] - '0') + carry;
if (nn > 9) {
nn -= 10;
carry = 1;
}
else
carry = 0;
result += nn + '0';
}
if (carry == 1)
result += '1';
if (!pos)
result += '-';
return result.reverse().leadZero();
}
String operator += (const string& val) {
m_value += val;
return *this;
}
String operator - () const {
if (equalsZero())
return *this;
if (isPositive()) {
String result;
result += '-';
result += m_value;
return result;
}
return absolute();
}
String operator - (const String& val) const {
if (equalsZero())
return - val;
if (val.equalsZero())
return *this;
bool pos = isPositive();
if (pos) {
if (!val.isPositive())
return *this + val.absolute();
if (*this < val)
return - (val - *this);
}
else {
if (!val.isPositive())
return (val.absolute() - absolute());
return - (val + absolute());
}
String _this = absolute().reverse();
String _val = val.absolute().reverse();
while (_this.length() < _val.length())
_this += '0';
String result;
char carry = 0;
for (size_t n = 0; n < length(); ++n) {
int nn;
if (n < _val.length())
nn = (_this[n] - '0') - (_val[n] - '0') - carry;
else
nn = (_this[n] - '0') - carry;
if (nn < 0) {
nn += 10;
carry = 1;
}
else
carry = 0;
result += nn + '0';
}
if (!pos)
result += '-';
return result.reverse().leadZero();
}
String append(char ch) const {
string str = m_value;
str.push_back(ch);
return String(str);
}
String powerOf10(int n) const {
if (n == 0)
return *this;
if (n > 0) {
String result = *this;
for (int nn = 0; nn < n; ++nn)
result += '0';
return result;
}
else {
String result = absolute().reverse();
n = -n;
if (n >= result.length()) {
size_t nn = n - result.length();
while (nn != 0) {
result += '0';
--nn;
}
result += ".0";
}
else
result.insert(n, '.');
if (! isPositive())
result += '-';
return result.reverse();
}
}
String operator * (const String& val) const {
if (equalsZero() || val.equalsZero())
return String("0");
enum { Pos, Neg } sign = Pos;
if (isPositive()) {
if (! val.isPositive())
sign = Neg;
}
else {
if (val.isPositive())
sign = Neg;
}
String _this = absolute();
String _val = val.absolute();
size_t p10 = 0;
while (_this[_this.length() - p10 - 1] == '0') {
++p10;
}
_this = _this.substr(0, _this.length() - p10);
size_t q10 = 0;
while (_val[_val.length() - q10 - 1] == '0') {
++q10;
}
_val = _val.substr(0, _val.length() - q10);
_this = _this.reverse();
_val = _val.reverse();
String result = "0";
for (size_t n = 0; n < _val.length(); ++n) {
int x = _val[n] - '0';
for (size_t nn = 0; nn < _this.length(); ++nn) {
int y = _this[nn] - '0';
String _mult = String(x * y);
result = result + _mult.powerOf10((int) nn + (int) n);
}
}
p10 += q10;
while (p10 != 0) {
result += '0';
--p10;
}
if (sign == Neg)
result.insert(0, '-');
return result.leadZero();
}
String powerOf2() const {
if (equalsZero())
return String("1");
String _this = *this;
String result;
if (isPositive()) {
result = "1";
while (! _this.equalsZero()) {
result = result * String("2");
_this = _this - 1;
}
}
else {
result = "1";
while (! _this.equalsZero()) {
result = result / String("2");
_this = _this + 1;
}
}
return result;
}
inline String substr(size_t n, size_t len) const {
return String(m_value.substr(n, len));
}
String operator / (const String& val) const {
if (val.equalsZero())
throw("Divide by zero!");
if (val == "1")
return *this;
if (val == "-1")
return - *this;
enum { Pos, Neg } sign = Pos;
if (isPositive()) {
if (! val.isPositive())
sign = Neg;
}
else {
if (val.isPositive())
sign = Neg;
}
String _this = absolute();
String _val = val.absolute();
if (_val.length() > _this.length())
return String("0");
while (_val[_val.length() - 1] == '0' && _this[_this.length() - 1] == '0') {
_this = _this.substr(0, _this.length() - 1);
_val = _val.substr(0, _val.length() - 1);
}
String result;
if (_val == "1")
result = _this;
else {
String _subthis = _this.substr(0, _val.length());
size_t n = 0;
if (_subthis < _val) {
_subthis += _this[_val.length()];
n = 1;
}
for (; n <= _this.length() - _val.length(); ++n) {
if (_subthis < _val) {
_subthis += _this[_val.length() + n - 1];
_subthis = _subthis.leadZero();
if (_subthis == "0") {
result += '0';
continue;
}
if (_subthis < _val) {
result += '0';
continue;
}
}
if (_subthis == _val) {
_subthis = "0";
result += '1';
continue;
}
for (int x = 9; x > 0; --x) {
String _xval = _val * String(x);
if (_xval <= _subthis) {
result += (x + '0');
_subthis = _subthis - _xval;
break;
}
}
}
}
if (sign == Neg)
result.insert(0, '-');
return result.leadZero();
}
};
ostream& operator << (ostream& os, const String& str) {
return os << (string) str;
}
int main()
{
try {
Integer x(333);
Integer y(77);
cout << "x =" << x << endl;
cout << "x % y = " << x % y << endl;
cout << "x / y = " << x / y << endl;
cout << "x * y = " << x * y << endl;
String s1("11102023");
cout << "leadZero " << s1.leadZero() << endl;
cout << "reverse " << s1.reverse() << endl;
cout << "absolute " << s1.absolute() << endl;
String s2("-1557");
cout << (s1 < s2 ? "Less" : "Not less") << endl;
cout << (s1 >= s2 ? "Greater or equal" : "Less") << endl;
cout << "s1 + s2 = " << s1 + s2 << endl;
cout << "s1 - s2 = " << s1 - s2 << endl;
cout << "s1 * s2 = " << s1 * s2 << endl;
cout << "s1.powerOf10(-7) " << s1.powerOf10(-7) << endl;
//cout << "s1.powerOf2() " << s1.powerOf2() << endl; // Commented because expensive
cout << "s1 / s2 = " << s1 / s2 << endl;
#if 0
for (int n = 1; n < 100001; ++n) {
String s3(n);
for (int nn = 1; nn <= n; ++nn) {
String s4(nn);
String s5(n * nn);
cout << n << " * " << nn << " = " << s3 * s4;
if (s5 == s3 * s4)
cout << " ok" << endl;
else
throw(" incorrect!");
}
}
#endif
}
catch(const char* e) {
cerr << e << endl;
}
return 0;
}