Submission #337066

#	Time	Username	Problem	Language	Result	Execution time	Memory
337066		kutbilim_one	Odd-even (IZhO11_oddeven)	C++14	0 / 100	1 ms	384 KiB

oddeven

//All functions of Big Numbers
//C++
//Source: http://e...content-available-to-author-only...x.ru/algo/big_integer
//
#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <vector>
#include <string>
using namespace std;

typedef vector<int> lnum;
const int base = 1000*1000*1000;

//TheFunctions Long Numbers
void output(lnum a);
lnum init(int n);
lnum init(string s);
lnum operator+(lnum a, lnum b);
lnum operator-(lnum a, lnum b);
lnum operator*(lnum a, lnum b);
lnum operator*(lnum a, int b);
lnum operator/(lnum a, int b);
int operator%(lnum a, int b);
bool operator<(lnum a, lnum b);
bool operator>(lnum a, lnum b);
bool operator==(lnum a, lnum b);
//

lnum sqrt(lnum n){
    lnum l = init("0");
    lnum r = n;
    lnum res;

    while(l<=r){
      lnum m = (l + r)/2;
      
      if(m*m < n || m*m == n){
        res = m;
        l = m + init("1");
      }else
        r = m - init("1");
    
    }

    return res;
}            

int main(){
/*
    string a, b;
    int c;
    cin >> a >> b >> c;

    lnum n = init(a);
    lnum m = init(b);

    cout << a << " + " << b << " = "; output( n+m );

    if(n < m) cout << a << " - " << b << " = -", output( m-n );
    else cout << a << " - " << b << " = ", output( n-m );

    cout << a << " * " << b << " = "; output( n*m );
    cout << a << " * " << c << " = "; output( n*c );
    cout << a << " / " << c << " = "; output( n/c );

    if(n < m) cout << a << " < " << b;
    if(n > m) cout << a << " > " << b;
    if(n == m) cout << a << " = " << b;
*/
	string s;
	cin >> s;

	lnum n = init(s);

    if(sqrt(n*200000000) % 10000 < 5000) output(n*2 - sqrt(n*2));
    else output(n*2 - sqrt(n*2) - init("1"));

    return 0;
}


//The Functions Code
// output the Big Integer
void output(lnum a){
    printf("%d", a.empty() ? 0 : a.back());
    for(int i = (int)a.size()-2; i >= 0; --i)
        printf("%09d", a[i]);
    printf("\n");
}

//Initialization of integer to long number
lnum init(int n){
    lnum a;
    while(n > 0)a.push_back(n % base), n /= base;
    return a;
}

//Initialization of string to long number
lnum init(string s){
    lnum a;

    for(int i = (int)s.length(); i > 0; i-=9)
        if(i < 9) a.push_back( atoi( s.substr(0, i).c_str() ) );
        else a.push_back( atoi( s.substr(i-9, 9).c_str() ) );

    while(a.size() > 1 && a.back() == 0)
        a.pop_back();

    return a;
}

//The Plussing of two long numbers
lnum operator+(lnum a, lnum b){
    int carry = 0;

    for(size_t i = 0; i < max(a.size(), b.size()) || carry; ++i){
        if(i == a.size())
            a.push_back(0);
        a[i] += carry + (i < b.size() ? b[i] : 0);
        carry = a[i] >= base;
        if(carry) a[i] -= base;
    }

    return a;
}

//The Minus of two long number
lnum operator-(lnum a, lnum b){
    int carry = 0;

    for(size_t i = 0; i < a.size() || carry; ++i){
        a[i] -= carry + (i < b.size() ? b[i] : 0);
        carry = a[i] < 0;
        if(carry) a[i] += base;
    }

    while(a.size() > 1 && a.back() == 0)
        a.pop_back();

    return a;
}

//The Multiple long to int
lnum operator*(lnum a, int b){
    int carry = 0;

    for(size_t i = 0; i < a.size() || carry; ++i){
        if(i == a.size()) a.push_back(0);
        long long cur = carry + a[i] * 1ll * b;
        a[i] = int(cur % base);
        carry = int(cur / base);
    }

    while(a.size() > 1 && a.back() == 0)
        a.pop_back();

    return a;
}

//The Multiple long to long
lnum operator*(lnum a, lnum b){
    lnum c(a.size()+b.size());

    for(size_t i = 0; i < a.size(); ++i)
    for(int j = 0, carry = 0; j < (int)b.size() || carry; ++j){
        long long cur = c[i+j] + a[i] * 1ll * (j < (int)b.size() ? b[j] : 0) + carry;
        c[i+j] = int(cur % base);
        carry = int(cur / base);
    }

    while(c.size() > 1 && c.back() == 0)
        c.pop_back();

    return c;
}

//The Divisible long to int
lnum operator/(lnum a, int b){
    int carry = 0;

    for(int i = (int)a.size()-1; i >= 0; --i){
        long long cur = a[i] + carry * 1ll * base;
        a[i] = int(cur / b);
        carry = int(cur % b);
    }

    while(a.size() > 1 && a.back() == 0)
        a.pop_back();

    return a;
}

int operator%(lnum a, int b){
    int carry = 0;

    for(int i = (int)a.size()-1; i >= 0; --i){
        long long cur = a[i] + carry * 1ll * base;
        a[i] = int(cur / b);
        carry = int(cur % b);
    }
                
    return carry;
}

//The Biggest operator
bool operator>(lnum a, lnum b){
    if(a.size() > b.size()) return 1;
    if(a.size() < b.size()) return 0;

    for(int i = (int)a.size()-1; i >= 0; --i){
        if(a[i] > b[i]) return 1;
        if(a[i] < b[i]) return 0;
    }

    return 0;
}

//The Smallest operator
bool operator<(lnum a, lnum b){
    return (b > a);
}

//The Equal operator
bool operator==(lnum a, lnum b){
    return !(a < b || a > b);
}

• Subtask 1: 0 / 100