akhauriyash/Code-Regression huggingface dataset:
// IOI 2021
#include <bits/stdc++.h>
using namespace std;

#define endl '\n'
#define ends ' '
#define die(x) return cout << x << endl, 0
#define all(v) v.begin(), v.end()
#define sz(x) (int)(x.size())
#define debug(x) cerr << #x << ": " << x << endl
#define debugP(p) cerr << #p << ": {" << p.first << ", " << p.second << '}' << endl
typedef long long ll;
typedef pair<int, int> pii;
const ll INF = 1e18;
const ll MOD = 1e9 + 7;

////////////////////////////////////////////////////////////////////

const int N = 1e5 + 5;

ll DS[N], DT[N];
int n, DPS[N], DPT[N];
vector<pii> G[N];

void Dijkstra(int s, ll dis[N], int dp[N]) {
	for (int i = 1; i < N; i++) dis[i] = INF;
	dis[s] = 0;
	dp[s] = 1;
	set< pair<ll, int> > st; st.insert(make_pair(0, s));
	while (!st.empty()) {
		int v = st.begin()->second;
		st.erase(st.begin());
		for (pii e : G[v]) {
			int u = e.first, w = e.second;
			if (dis[v] + w < dis[u]) {
				st.erase(make_pair(dis[u], u));
				dis[u] = dis[v] + w;
				dp[u] = 0;
				st.insert(make_pair(dis[u], u));
			}
			if (dis[v] + w == dis[u]) dp[u] = (dp[u] + dp[v]) % MOD;
		}
	}
}
int sq(int x) { return 1LL * x * x % MOD; }

int main() {

	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	
	int m, s, t; cin >> n >> m >> s >> t;
	for (int i = 0; i < m; i++)  {
		int v, u, w; cin >> v >> u >> w;
		G[v].push_back(make_pair(u, w));
		G[u].push_back(make_pair(v, w));
	}
	Dijkstra(s, DS, DPS);
	Dijkstra(t, DT, DPT);
	int ans = 1LL * DPS[t] * DPT[s] % MOD;
	ll d = DS[t];
	for (int v = 1; v <= n; v++) 
		if (DS[v] + DT[v] == d && DS[v] == DT[v]) 
			ans = (ans - sq(1LL * DPS[v] * DPT[v] % MOD) + MOD) % MOD;
	for (int v = 1; v <= n; v++) for (pii e : G[v]) {
		int u = e.first, w = e.second;
		if (DS[v] + w + DT[u] == d && abs(DS[v] - DT[u]) < w)
			ans = (ans - sq(1LL * DPS[v] * DPT[u] % MOD) + MOD) % MOD;
	}
	cout << ans << endl;

	return 0;
}


Measured memory_bytes: 16884
#include <bits/stdc++.h>
#define XOX
using namespace std;

#define fast ios_base::sync_with_stdio(false),cin.tie(NULL)
#define int long long

#define fr first
#define se second
#define lb lower_bound 
#define ub upper_bound 
#define pb push_back
#define mpr make_pair

#define pi pair<int,int>

#define vi vector<int>

#define vpi vector< pi >

#define mi map<int,int>


#define forr(a,b) for (int i = (a); i < (b); ++i)
#define rrof(a,b) for (int i = (b)-1; i >= (a); --i)

#define sz(x) (int)x.size()
#define all(x) begin(x), end(x)

const int md = 1e9+7;
const int MX = 2e5+5;
const int INF = 1e18; 


int power_md(int a,int n)
{
 int res=1;
 while(n)
{
 if(n%2)
  res=(res%md*a%md)%md;
  a=(a%md*a%md)%md;
  n/=2;
}
res%=md;
return res;
}

int power(int a,int n)
{
 int res=1;
 while(n)
{
 if(n%2)
  res*=a;
  a=a*a;
  n/=2;
}
return res;
}

int abst(int a)
{
 return ((a<0)?(-1*a):(a));
}

class cmp_set{
public:
	bool operator() (int a, int b){
		return a > b;
	}
};

vector<string> vec_splitter(string s) {
	s += ',';
	vector<string> res;
	while(!s.empty()) {
		res.push_back(s.substr(0, s.find(',')));
		s = s.substr(s.find(',') + 1);
	}
	return res;
}
void debug_out(
vector<string> __attribute__ ((unused)) args,
__attribute__ ((unused)) int idx, 
__attribute__ ((unused)) int LINE_NUM) { cerr << endl; } 
template <typename Head, typename... Tail>
void debug_out(vector<string> args, int idx, int LINE_NUM, Head H, Tail... T) {
	if(idx > 0) cerr << ", "; else cerr << "Line(" << LINE_NUM << ") ";
	stringstream ss; ss << H;
	cerr << args[idx] << " = " << ss.str();
	debug_out(args, idx + 1, LINE_NUM, T...);
}
#ifdef XOX
#define debug(...) debug_out(vec_splitter(#__VA_ARGS__), 0, __LINE__, __VA_ARGS__)
#else
#define debug(...) 42
#endif

int32_t main()
{
    int n;
    cin>>n;
    int g=0;
    for(int i=0;i<n;i++)
    {
        int x;
        cin>>x;
        g=__gcd(g,x);
    }
    cout<<g<<"\n";
    return 0;
}

Measured memory_bytes: 256
import Foundation
#if CUDA
extension String {
    func at(i: Int) -> String {
        return String(self[self.index(self.startIndex, offsetBy: i)])
    }
    var length: Int {
        return self.count
    }
}
func getInt() -> Int {
    return Int(readLine()!)!
}
func getStrings() -> [String] {
    return readLine()!.components(separatedBy: " ")
}
func getInts() -> [Int] {
    return getStrings().map({Int($0)!})
}
#else
import Foundation
extension String: CollectionType {
    func at(i: Int) -> String {
        return String(self[self.startIndex.advancedBy(i)])
    }
    var length: Int {
        return self.characters.count
    }
    func splitToArrayOfInt() -> [Int] {
        return self.characters.flatMap({Int(String($0))})
    }
}
func getInt() -> Int {
    return Int(readLine()!)!
}
func getStrings() -> [String] {
    return readLine()!.split(" ")
}
func getInts() -> [Int] {
    return getStrings().map({Int($0)!})
}
#endif

func gcd ( x: Int, y: Int ) -> Int {
    return y == 0 ? x : gcd ( y, y: x%y )
}

func main ( ) {
    let a = getInts()
    print(a[0]/gcd(a[0], y: a[1])*a[1])

}

main()

Measured memory_bytes: 7016
#include <stdio.h>

#define N 2097152 // 2^21
#define MAXVAL 16384 // 2^14

int A[N] = {0}, B[N] = {0}, C[MAXVAL] = {0};

void countingSort(int n, int max) {
  int i;

  // count up
  for (i = 0; i < n; i++)
    C[A[i]]++;

  // calculate cumulative sum
  for (i = 1; i <= max; i++)
    C[i] += C[i - 1];

  for (i = n - 1; 0 <= i; i--) {
    B[C[A[i]]] = A[i];
    C[A[i]]--;
  }
}

int main() {
  int i, n, max = 0;
  const char *sp;

  scanf("%d", &n);
  for (i = 0; i < n; i++) {
    scanf("%d", &A[i]);
    if (max < A[i])
      max = A[i];
  }
  countingSort(n, max);
  for (i = 1, sp = ""; i < n + 1; i++) {
    printf("%s%d", sp, B[i]);
    sp = " ";
  }
  puts("");
  return 0;
}

Measured memory_bytes: 16972
#include <iostream>

using namespace std;

int main()
{
    string s[100000];
    int i , n ;
    int AC=0 , WA=0 , TLE=0, RE=0;
    cin>>n;
    for(i=0;i<n; i++){
        cin>>s[i];}
    for(i=0;i<n;i++){
        if(s[i]=="AC"){ AC+=1;}
        else if (s[i]=="WA"){WA+=1;}
        else if (s[i]=="TLE"){TLE+=1;}
        else if (s[i]=="RE"){RE+=1;}
        }
    cout<<"AC"<<" "<<"x"<<" "<<AC<<endl;
    cout<<"WA"<<" "<<"x"<<" "<<WA<<endl;
    cout<<"TLE"<<" "<<"x"<<" "<<TLE<<endl;
    cout<<"RE"<<" "<<"x"<<" "<<RE<<endl;

    return 0;
}


Measured memory_bytes: 6712
#include <iostream>
#include <algorithm>
#include <functional>
#include <vector>
#include <string>
#include <map>
#include <sstream>
#include <cmath>
#include <cstdio>
#include <iomanip>
#include <stdexcept>
#include <utility>
// #include <bits/stdc++.h>
#define ll long long
#define ld long double
#define rep(i,h) for(int i = 0; i < h; ++i)
#define rep1(i,h) for(int i = 0; i <= h; ++i)
#define rep2(i,n,h) for(int i = n; i < h; ++i)
#define rep3(l,n,h) for(int l = n; i <= h; ++i)
using namespace std;



int main() {
    string n;
    cin >> n;
    int k = 0;
    rep(i,n.length()) {
        int h = n[i] - '0';
        k += h;
    }
    int num = atoi(n.c_str());
    if(num % k == 0) {
        cout << "Yes";
    } else {
        cout << "No";
    }
    return 0;
}


Measured memory_bytes: 256
#include <cstdio>
#include <cmath>
#include <cstring>
#include <iostream>

#include <string>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <stack>
#include <deque>

#include <algorithm>

using namespace std;



int main(int argc, char *argv[]) {
	
	int n, m;
	cin >> n >> m;
	vector<vector<int> > vv(n + 1, vector<int> (0));
	for (int i = 0; i < m; i++) {
		int x, y, z;
		cin >> x >> y >> z;
		vv[x].push_back(y);
		vv[y].push_back(x);
	}

	int res = 0;
	vector<int> v(n + 1, 0);
	for (int i = 1; i <= n; i++) {
		if (v[i] == 0) {
			v[i] = 1;
			res++;
			queue<int> q;
			q.push(i);
			while (q.size() > 0) {
				int t = q.front();
				q.pop();
				for (auto node : vv[t])
					if (v[node] == 0) {
						q.push(node);
						v[node] = 1;
					}
			}
		}
	}
	cout << res << endl;
}



Measured memory_bytes: 6904
#include<bits/stdc++.h>
using namespace std;
int main(){
  int N; cin >> N;
  string s; cin >> s;
  if(N % 2 == 0 && s.substr(0, N/2) == s.substr(N/2, N/2)){
    cout << "Yes" << endl;
  }else{
    cout << "No" << endl;
  }
}


Measured memory_bytes: 256
import Control.Monad
import qualified Data.Vector as V

main = do
  [k, q] <- map read.words <$> getLine
  d <- V.fromList.map read.words <$> getLine
  nxm <- replicateM q $ map read.words <$> getLine
  mapM_ (print.solve k d) nxm

count :: Eq a => a -> V.Vector a -> Int
count a v = V.length $ V.elemIndices a v

solve :: Int -> V.Vector Int -> [Int] -> Int
solve k d' [n, x, m] = n - 1 - eqs - gts where
  d = V.map (`rem` m) d'
  eqs = count 0 d * quot (n-1) k + count 0 (V.take (rem (n-1) k) d)
  gts = quot alast m - quot x m
  alast = V.foldl (+) x dcnt
  (nq, nr) = quotRem (n-1) k
  cnt i | i < nr = nq + 1
        | otherwise = nq
  dcnt = V.map f $ V.indexed d
  f (i, d) = cnt i * d

Measured memory_bytes: 14716
#include <bits/stdc++.h>
#define REP(i, m, n) for(int (i) = (m); (i) < (n); ++i)
#define rep(i, n) REP(i, 0, n)
#define all(x) (x).begin(), (x).end()
using namespace std;
using Graph = vector<vector<int>>;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
typedef long long ll;
typedef pair<ll, ll> P;
const int INF = 1e9+7;
const ll LINF = 1LL<<60;

const int MAX = 510000;
const int MOD = 1000000007;

long long fac[MAX], finv[MAX], inv[MAX];

void COMinit() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (int i = 2; i < MAX; i++) {
        fac[i] = fac[i - 1] * i % MOD;
        inv[i] = MOD - inv[MOD % i] * (MOD / i) % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }
}

long long COM(int n, int k) {
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}

int main()
{
    cin.tie(0);
    ios_base::sync_with_stdio(0);
    int n, k;
    cin >> n >> k;

    COMinit();

    int r = n - k;

    for (int i = 1; i <= k; ++i) {
        cout << COM(r + 1, i) * COM(k - 1, i - 1) % MOD << endl;
    }

    return 0;
}

Measured memory_bytes: 12160
#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
#include <set>
#include <map>
#include <string>
#include <stack>
#include <queue>
#include <cmath>
#include <cstdio>
#include <istream>
#include <sstream>
#include <iomanip>
#include <iterator>
#include <climits>
using namespace std;

typedef ostringstream OSS;
typedef istringstream ISS;

typedef vector<int> VI;
typedef vector< VI > VVI;

typedef long long LL;

typedef pair<int, int> PII;
typedef vector<PII> VPII;

#define X first
#define Y second

// 1文字split 要sstream
vector<string> split(const string &str, char delim) {
	istringstream iss(str); string tmp; vector<string> res;
	while(getline(iss, tmp, delim)) res.push_back(tmp);
	return res;
}

int main(void) {
	string s;
	getline(cin, s);

	vector<string> ws = split(s, ' ');
	string max_len;
	
	map<string, int> ws_cnt;

	for (auto w : ws) {
		ws_cnt[w] = 0;
	}

	for (auto w : ws) {
		ws_cnt[w]++;
		if (max_len.size() < w.size()) {
			max_len = w;
		}
	}

	string max_cnt_str;
	int max_cnt = 0;
	for (auto m : ws_cnt) {
		if (max_cnt < m.second) {
			max_cnt = m.second;
			max_cnt_str = m.first;
		}
	}

	cout << max_cnt_str << " " << max_len << endl;
	
	return 0;
}

Measured memory_bytes: 1208
#include <iostream>
#include <complex>
#include <sstream>
#include <string>
#include <algorithm>
#include <deque>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <vector>
#include <set>
#include <limits>
#include <cstdio>
#include <cctype>
#include <cmath>
#include <cstring>
#include <cstdlib>
#include <ctime>
using namespace std;
#define REP(i, j) for(int i = 0; i < (int)(j); ++i)
#define FOR(i, j, k) for(int i = (int)(j); i < (int)(k); ++i)
#define SORT(v) sort((v).begin(), (v).end())
#define REVERSE(v) reverse((v).begin(), (v).end())

const double EPS = 1e-8;
const double INF = 1e12;
typedef complex<double> P;
namespace std {
  bool operator < (const P& a, const P& b) {
    return real(a) != real(b) ? real(a) < real(b) : imag(a) < imag(b);
  }
}

//外積
double cross(const P& a, const P& b) {
  return imag(conj(a)*b);
}

//内積
double dot(const P& a, const P& b) {
  return real(conj(a)*b);
}

//線 (線分)
struct L : public vector<P> {
  L(const P &a, const P &b) {
    push_back(a); push_back(b);
  }
};

int ccw(P a, P b, P c) {
  b -= a; c -= a;
  if (cross(b, c) > 0)   return +1;       // counter clockwise
  if (cross(b, c) < 0)   return -1;       // clockwise
  if (dot(b, c) < 0)     return +2;       // c--a--b on line
  if (norm(b) < norm(c)) return -2;       // a--b--c on line
  return 0;
}

bool intersectSS(const L &s, const L &t) {
  return ccw(s[0],s[1],t[0])*ccw(s[0],s[1],t[1]) <= 0 &&
         ccw(t[0],t[1],s[0])*ccw(t[0],t[1],s[1]) <= 0;
}

int main() {
  int Q; cin >>Q;
  REP(q, Q){
    int x0, y0, x1, y1, x2, y2, x3, y3;
    scanf("%d %d %d %d %d %d %d %d", &x0, &y0, &x1, &y1, &x2, &y2, &x3, &y3);
    L l1 = L(P(x0, y0), P(x1, y1)), l2 = L(P(x2, y2), P(x3, y3));
    if(intersectSS(l1, l2)) cout <<1 <<endl;
    else cout <<0 <<endl;
  }
  return 0;
}

Measured memory_bytes: 1268
# AGC015A - A+...+B Problem
def main():
    n, a, b = tuple(map(int, input().rstrip().split()))
    if a > b or (n == 1 and a != b):
        print(0)
    elif n == 1 and a == b:
        print(1)
    else:
        print((n - 2) * (b - a) + 1)


if __name__ == "__main__":
    main()

Measured memory_bytes: 3060
#define ALL(v) v.begin(), v.end()
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;


int main() {

	int n;
	cin >> n;
	n = n - 1;
	vector<ll> a(n);

	ll total = 0;
	for (int i = 0; i < n; i++)
	{
		
		cin >> a[i];
		
	}

	for (int i = 0; i < n; i++)
	{
		if (i == 0) {
			total += a[i];
		}else{
			ll minz;
			minz = min(a[i - 1], a[i]);
			total += minz;
		}
	}

	total += a[n - 1];

		cout << total << endl;

}



Measured memory_bytes: 256
func readInts() -> [Int] {
    return readLine()!.split(separator: " ").map { Int($0)! }
}
let nab = readInts()
let n = nab[0]
let a = nab[1]
let b = nab[2]

if n*a<b {
  print(n*a)
} else {
  print(b)
}



Measured memory_bytes: 8136
from heapq import *
import sys
from collections import *
from itertools import *
from decimal import *
import copy
from bisect import *
import math
sys.setrecursionlimit(4100000)
def gcd(a,b):
    if(a%b==0):return(b)
    return (gcd(b,a%b))
input=lambda :sys.stdin.readline().rstrip()
N,M,K=map(int,input().split())
mod=998244353
fac=[1,1]
for i in range(2,N*2):
    fac.append(fac[-1]*i%mod)
ifac=[pow(i,mod-2,mod) for i in fac]

def comb(a,b):
    if a<b:
        return(0)
    return(fac[a]*ifac[b]*ifac[a-b]%mod)


c=0
for k in range(K+1):
    k=N-1-k
    c+=pow(M-1,k,mod)*comb(N-1,k)
    c%=mod
c*=M
c%=mod
print(c)


Measured memory_bytes: 134024
#include<iostream>
#include<algorithm>
using namespace std;

#define ll long long int

struct ST
{
	ll x1, x2;
	ll y1, y2;
	ll z1, z2;
};

ll x[100 + 10] = { 0 };
ll y[100 + 10] = { 0 };
ll z[100 + 10] = { 0 };

ll area = 0;

int main()
{
	ST fish[50 + 10];

	int n,k;

	int i, j;
	int xi, yi, zi;

	int cnt = 0;


	
	cin >> n >> k;

	for (i = 0; i < n; i++)
	{
		cin >> fish[i].x1 >> fish[i].y1 >> fish[i].z1 >> fish[i].x2 >> fish[i].y2 >> fish[i].z2;

		x[i * 2] = fish[i].x1;
		x[(i * 2) + 1] = fish[i].x2;
		y[i * 2] = fish[i].y1;
		y[(i * 2) + 1] = fish[i].y2;
		z[i * 2] = fish[i].z1;
		z[(i * 2) + 1] = fish[i].z2;
	}

	sort(x, x + (n * 2));
	sort(y, y + (n * 2));
	sort(z, z + (n * 2));

	for (xi = 0; xi < n * 2 -1; xi++)
	{
		for (yi = 0; yi < n * 2 -1; yi++)
		{
			for (zi = 0; zi < n * 2 -1; zi++)
			{
				cnt = 0;
				for (i = 0; i < n; i++)
				{
					if (fish[i].x1 > x[xi] || x[xi + 1] > fish[i].x2)
					{
						continue;
					}
					if (fish[i].y1 > y[yi] || y[yi + 1] > fish[i].y2)
					{
						continue;
					}
					if (fish[i].z1 > z[zi] || z[zi + 1] > fish[i].z2)
					{
						continue;
					}

					cnt++;
				}

				if (cnt >= k)
				{
					area += (x[xi + 1] - x[xi]) * (y[yi + 1] - y[yi]) * (z[zi + 1] - z[zi]);
				}

			}
		}
	}

	cout << area << endl;

	return 0;
}




Measured memory_bytes: 3140
#include <iostream>
#include <string>
#include <math.h>
#include <iomanip>
#include <stdio.h>
#include <algorithm>
#include <ctime>
#include <vector>
#include <set>
#include <queue>
using namespace std;

int N;
int x[10], y[10];

double dist(int i, int j)
{
    double dx = x[i] - x[j];
    double dy = y[i] - y[j];
    return pow(dx * dx + dy * dy, 0.5);
}

void solve()
{
    cin >> N;
    for (int i = 1; i <= N; i++)
        cin >> x[i] >> y[i];
    double sum = 0.0;
    vector<int> v(N);
    for (int i = 0; i < N; i++)
        v[i] = i + 1;
    do
    {
        for (int i = 0; i < N - 1; i++)
            sum += dist(v[i], v[i + 1]);
    } while (next_permutation(v.begin(), v.end()));
    int Factorial = 1;
    for (int i = 2; i <= N; i++)
        Factorial *= i;
    cout << fixed << setprecision(10) << sum / Factorial << endl;
    return;
}
int main()
{
    solve();
    return 0;
}

Measured memory_bytes: 384
//  RAKSHIT KADAM

 #include <bits/stdc++.h>
// #include <ext/pb_ds/assoc_container.hpp> 3
// #include <ext/pb_ds/tree_policy.hpp>
// using namespace __gnu_pbds;
// #define ordered_set tree< int ,  null_type ,  less<int> ,  rb_tree_tag ,  tree_order_statistics_node_update>
#warning !!!check the size of arrayss!!!
 
// NUMERIC DEFINITIONS :
    #define INF 100000000000000005
    #define inf 1000000004
    #define MOD  1000000007
    #define mod 998244353
    #define MAX 300006
    #define pi 3.1415926535897932384626433832795
#define ld long double
 #define ll long long
 #define int long long
 
 #define P(gg) for(auto rax:gg){cout<<rax<<" ";}cout<<endl;
 #define Need_for_speed(activated) ios_base :: sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL)
 #define satisfy ll t; cin>> t; while(t--)
 #define inp(n) int n;cin >> n
 #define mp make_pair
 #define pb push_back
 #define endl "\n"
 #define x first
 #define y second
 #define fore(i,a,b) for(ll i=a;i<b;i++)
 #define forci(i,n) for(ll i=0;i<n;i++)
 #define vi vector<ll>
 #define Endl endl
 #define lb lower_bound
 #define ub upper_bound
#define pii pair<ll,ll>
 
 #define input freopen("input.txt", "r", stdin),freopen("output.txt", "w", stdout)
 #define time        cerr << "\nTime elapsed: " << 1000 * clock() / CLOCKS_PER_SEC << "ms\n";
using namespace std;
 
ll gcd(ll a, ll b){if (b == 0)return a;return gcd(b, a % b);}
int power(int x, unsigned int y, unsigned int m){ if (y == 0) return 1;int p = power(x, y/2, m) % m;  p = (p * p) % m;return (y%2 == 0)? p : (x * p) % m;}
ll modInverse(int a, int m){{ return power(a, m-2, m);}}
const int maxn = 500003;
// ll fact[1000005];
//ll modIN[1000005];
//void facto()
//{
//    ll lim =1000005;fact[0]=1;
//    for(ll i=1;i<lim;i++)
//    {
//        fact[i]=(fact[i-1]*i)%MOD;
//    }
//    modIN[n]=modInverse(fact[n],MOD);
//    for(ll i=n-1;i>=1;i--)
//    {
//        modIN[i] = (modIN[i+1]*(i+1))%MOD;
//    }
//}
//ll ncr(ll a,ll b)
//{
//    ll ret = 0;
//    ret = fact[a]*(modIN[b]);
//    ret%=MOD;
//    ret*=modIN[a-b];
//    ret%=MOD;
//    return ret;
//}

void solve()
{
    ll x,k,d;cin>>x>>k>>d;
    if(x<0)x*=-1;
    

        ll req = (x+d-1)/d;
        if(k<req)
        {
            cout<<x-k*d<<endl;
        }
        else
        {
            k-=req;
            ll minn=0;
            if(k&1)
            {
                minn=abs(x-(req-1)*d);
            }
            else minn = abs(x-req*d);
            cout<<minn<<endl;
        }
   
}
signed main()
{
   Need_for_speed(activated);
  
//    satisfy
//    {
//        solve();
//    }
   
    solve();
    
    return 0;
}
//Concentrate while implementing,,,!!!
 


Measured memory_bytes: 3612
#include "bits/stdc++.h"
using namespace std;
#ifdef _DEBUG
#include "dump.hpp"
#else
#define dump(...)
#endif

//#define int long long
#define rep(i,a,b) for(int i=(a);i<(b);i++)
#define rrep(i,a,b) for(int i=(b)-1;i>=(a);i--)
#define all(c) begin(c),end(c)
const int INF = sizeof(int) == sizeof(long long) ? 0x3f3f3f3f3f3f3f3fLL : 0x3f3f3f3f;
const int MOD = (int)(1e9) + 7;
template<class T> bool chmax(T &a, const T &b) { if (a < b) { a = b; return true; } return false; }
template<class T> bool chmin(T &a, const T &b) { if (a > b) { a = b; return true; } return false; }
int Largest_Square(const vector<vector<int>> &field) {
	int H = field.size(), W = field[0].size();
	vector<vector<int>>dp(H, vector<int>(W)); // dp[i][j]=?????????(i,j)???????????????????????£?????§???????????§?????£?????¢???????????????
	rep(i, 0, H)rep(j, 0, W) dp[i][j] = (field[i][j] + 1) % 2; // ????????????????????????????????????????????????
	int ret(0);
	rep(i, 0, H)chmax(ret, dp[i][0]); rep(i, 0, W)chmax(ret, dp[0][i]);
	rep(i, 1, H)rep(j, 1, W)
		if (dp[i][j])chmax(ret, dp[i][j] = 1 + min(dp[i - 1][j], min(dp[i][j - 1], dp[i - 1][j - 1])));
	//rep(i, 0, H)rep(j, 0, W)cout << dp[i][j] << (j == W - 1 ? '\n' : ' ');
	return ret*ret;// ??????????????¢???????????§???
}
signed main() {
	cin.tie(0);
	ios::sync_with_stdio(false);

	int H, W; cin >> H >> W;
	vector<vector<int>>G(H, vector<int>(W));
	rep(i, 0, H)rep(j, 0, W)cin >> G[i][j];
	cout << Largest_Square(G) << endl;
	return 0;
}

Measured memory_bytes: 18420
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Scanner;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 *
 * @author mikit
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        Scanner in = new Scanner(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        AAddSubMul solver = new AAddSubMul();
        solver.solve(1, in, out);
        out.close();
    }

    static class AAddSubMul {
        public void solve(int testNumber, Scanner in, PrintWriter out) {
            int a = in.nextInt(), b = in.nextInt();
            out.println(Math.max(a + b, Math.max(a - b, a * b)));
        }

    }
}



Measured memory_bytes: 22224
N, X = map(int, input().split())

burgersize, pnum = [1], [1]
for i in range(N):
    burgersize.append(burgersize[-1] * 2 + 3)
    pnum.append(pnum[-1] * 2 + 1)

def count_p(level, X):
    if level == 0:
        return 1
    elif X == burgersize[level]:
        return pnum[level]
    elif X == 1:
        return 0
    elif X < (burgersize[level] - 1) // 2 + 1:
        return count_p(level - 1, X - 1)
    elif X == (burgersize[level] - 1) // 2 + 1:
        return pnum[level - 1] + 1
    elif X > (burgersize[level] - 1) // 2 + 1:
        return pnum[level - 1] + 1 + count_p(level - 1, X - (burgersize[level] - 1) // 2 - 1)
    return None

ans = count_p(N, X)
print(ans)

Measured memory_bytes: 3064
#include <bits/stdc++.h>
#include <math.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)

const int MOD = 1000000007;

const int INF_32 = 1LL << 30;
const int64_t INF_64 = 1LL << 60;

int main()
{
    int N;
    string S;
    cin >> N;
    cin >> S;

    int size = S.size();

    if (size % 2 == 1) {
        cout << "No" << endl;
        return 0;
    }

    for (int i = 0; i < size / 2; i++) {
        if (S.at(i) != S.at(i + size / 2)) {
            cout << "No" << endl;
            return 0;
        }
    }

    cout << "Yes" << endl;
}

Measured memory_bytes: 256
n, m = gets.split.map(&:to_i)
ab = []
cd = []
n.times do
  ab.push gets.split.map(&:to_i)
end
m.times do
  cd.push gets.split.map(&:to_i)
end
cps = []
ab.each_index do |i|
  min = 1000000000
  cd.each_index do |j|
    d = (ab[i].first - cd[j].first).abs + (ab[i].last - cd[j].last).abs
    if min > d
      min = d
      cps[i] = j + 1
    end
  end
end
cps.each do |cp|
  puts cp
end


Measured memory_bytes: 1788
#include <bits/stdc++.h>

#define rep2(x,fr,to) for(int x=(fr);x<(to);x++)
#define rep(x,to) for(int x=0;x<(to);x++)
#define repr(x,fr,to) for(int x=(fr);x>=(to);x--)
#define all(c) c.begin(),c.end()
#define sz(v) (int)v.size()

using namespace std;
typedef long long  ll; typedef vector<int> VI; typedef pair<int,int> pii;
typedef vector<ll> VL; const int MD = 998244353;
void dbg(){cerr<<"\n";} template <typename T,typename ...T2> void dbg(const T& fst, const T2&...rst){ cerr << fst << ": "; dbg(rst...); }


int main()
{
	cin.tie(0); ios_base::sync_with_stdio(false);
	int  n, s;
	cin >>n >>s;
	VI a(n);
	rep(i, n) cin >>a[i];
	
	VL dp(s+4); dp[0]=1;
	rep(i, n){
		VL np(s+4);
		rep(k, s+1) {
			(np[k] += dp[k] *2 )%=MD;
			if(k+a[i] <= s) (np[ k + a[i]] += dp[k]) %=MD;
		}
		swap(dp, np);
	}
	cout << dp[s] <<"\n";
	return 0;
}


Measured memory_bytes: 3680
#include<stdio.h>
#include<stdlib.h>

int main(void){
    
    int H, W, h, w, i, j, sum, min;
    int a[26][26];
    int x, y;
    
    scanf("%d",&H);
    scanf("%d",&W);
    
    for(i=1;i<=H;i++){
        for(j=1;j<=W;j++){
            scanf("%d",&a[i][j]);
        }
    }
    
    min = 100000000;
    
    for(i=1;i<=H;i++){
        for(j=1;j<=W;j++){
            sum = 0;
            for(h=1;h<=H;h++){
                for(w=1;w<=W;w++){
                   x = abs(i-h);
                   y = abs(j-w);
                   if(x<y) sum += a[h][w]*x;
                   else sum += a[h][w]*y;
                }
            }
            if(sum < min) min = sum;
        }
    }
    printf("%d\n",min);

    return 0;
    
}


Measured memory_bytes: 2100
#include <bits/stdc++.h>

using namespace std;

int main(void) {
  int H, W;
  cin >> H >> W;
  vector <string> a(H);
  for(int i = 0; i < H; i++) {
    cin >> a[i];
  }

  vector <vector <bool>> b(H);
  for(int i = 0; i < H; i++) {
    vector <bool> tmp;
    for(int j = 0; j < W; j++) {
      tmp.push_back(true);
    }
    b[i] = tmp;
  }
  
  for(int i = 0; i < H; i++) {
    bool w = false;
    for(int j = 0; j < W; j++) {
      if(a[i][j] == '#') {
	w = true;
	break;
      }
    }
    if(!w) {
      for(int k = 0; k < W; k++) {
	b[i][k] = false;
      }
    }
  }

  for(int j = 0; j < W; j++) {
    bool w = false;
    for(int i = 0; i < H; i++) {
      if(a[i][j] == '#') {
	w = true;
	break;
      }
    }
    if(!w) {
      for(int k = 0; k < H; k++) {
	b[k][j] = false;
      }
    }
  }

  for(int i = 0; i < H; i++) {
    bool foo = false;
    for(int j = 0; j < W; j++) {
      if(b[i][j]) {
	cout << a[i][j];
	foo = true;
      }
    }
    if(foo) {
      cout << endl;
    }
  }
  
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<(n);i++)
using ll=long long;

int main()
{
    ll n;
    cin>>n;
    ll ans=n+2;
    for(ll i=1;i*i<=n;i++){
        if(n%i==0){
            ll t=i+n/i-2;
            ans=min(ans,t);
        }
    }
    cout<<ans;
}

Measured memory_bytes: 3596
#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin >> n;
    int a[n];
    a[0]=-1;
    int d[n+1];
    for(int i=0;i<=n;i++) d[i]=0;
    for(int i=1;i<n;i++){
        cin >> a[i];
        d[a[i]]++;
    }
    for(int i=1;i<=n;i++){
        cout << d[i] << endl;
    }
}

Measured memory_bytes: 5192
#include <stdio.h>

#define Num 100

int main(void){

    int l, n, i, j, k = 0, min = 0, count = 0;
    int a[Num];

    scanf("%d", &l); 

    for (i = 0; i <= l-1; i++) {
        scanf("%d", &a[i]); 
    }

    for (i = 0; i <= l-1; i++) {
        min = i;
        for (j = i+1; j <= l-1; j++) {
            if(a[j] < a[min]){
                min = j;
            }
        }
        if(min != i){
            k = a[min];
            a[min] = a[i];
            a[i] = k;
            count++;
        }
    }
    
    for (i = 0; i <= l-2; i++) {
        printf("%d ", a[i]); 
    }
    printf("%d\n", a[i]);
    printf("%d\n", count);

    return 0;
}


Measured memory_bytes: 1992
#include <bits/stdc++.h>
using namespace std;
#define maxn 55
#define maxm 125005
#define int long long
#define INF 1e9 + 10
int n, X, D, ans, cnt, dp[maxm];
int w[maxn], val[maxn], pos[maxn];
int tot, V[maxn * maxn], W[maxn * maxn];

int read()
{
    int x = 0, k = 1;
    char c; c = getchar();
    while(c < '0' || c > '9') { if(c == '-') k = -1; c = getchar(); }
    while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
    return x * k;
}

struct edge
{
    int cnp, to[maxn], last[maxn], head[maxn];
    edge() { cnp = 1; }
    void add(int u, int v)
    { to[cnp] = v, last[cnp] = head[u], head[u] = cnp ++; }
}E1;

void dfs(int u)
{
    val[u] = 1;
    for(int i = E1.head[u]; i; i = E1.last[i])
    {
        int v = E1.to[i];
        dfs(v);
        w[u] += w[v]; val[u] += val[v];
    }
    cnt += val[u] * n; pos[u] = u;
}

bool cmp(int x, int y) { return val[x] * w[y] > val[y] * w[x]; }
void Get_min(int &x, int y) { x = x < y ? x : y; }

int num[60];

signed main()
{
    n = read(), X = read(), D = read();
    w[1] = read();
    for(int i = 2; i <= n; i ++)
    {
        w[i] = read(); int x = read();
        E1.add(x, i);
    }
    dfs(1);
    memset(dp,63,sizeof dp);dp[0]=0;
    for(int i = 1; i <= n; i ++)
    {
        int len = 1, lim = X/w[i];
		if(i>1) lim=min(lim,D);

		if(lim>n) num[i]=lim-n,lim=n;

        while(lim>0)
        {
            if(lim<len) len=lim;
			int ww=len*val[pos[i]],vv=len*w[pos[i]];
			for(int j = n*n*n; j>=ww; j --) Get_min(dp[j], dp[j -ww] +vv); // k件物品
            lim -= len, len <<= 1;
        }
    }

 	sort(pos + 1, pos + n + 1, cmp);
    int ans = 0;
    for(int i = 0; i <= n*n*n; i ++)
       {
        if(dp[i] > X) continue;
        int ret = i, left = X - dp[i];
        for(int j = 1; j <= n; j ++)
        {
            int tem = pos[j];
            int used = min(num[tem], left / w[tem]);

            left -= w[tem] * used;
            ret += val[tem] * used;
        }
        ans = max(ans, ret);
    }
    printf("%lld\n", ans);
    return 0;
}


Measured memory_bytes: 1280
package main
import (
  "fmt"
  "sort"
)

type AB struct {
  a int
  b int
}

type ABs []AB
func (ab ABs) Len() int {
  return len(ab)
}
func (ab ABs) Less(i, j int) bool {
  return ab[i].b < ab[j].b
}
func (ab ABs) Swap(i, j int) {
  ab[i], ab[j] = ab[j], ab[i]
}

func main() {
  var n int
  fmt.Scan(&n)
  a := make([]int, n)
  b := make([]int, n)
  for i := 0; i < n; i++ {
    fmt.Scan(&a[i], &b[i])
  }
  ab := make([]AB, n)
  for i := 0; i < n; i++ {
    ab[i] = AB{a: a[i], b: b[i]}
  }
  
  sort.Sort(ABs(ab))
  
  time := 0
  result := "Yes"
  for i := 0; i < n; i++ {
    time += ab[i].a
    if ab[i].b < time {
      result = "No"
      break
    }
  }
  fmt.Println(result)
}

Measured memory_bytes: 11008
import java.util.*;

public class Main{
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    String abcd = sc.next();
    int n = abcd.length();
    int total = 0;
    String ans = "";
    for(int i = 0; i < Math.pow(2, n - 1); i++){
      //StringBuffer sb = new StringBuffer(abcd);
      //int count = 0;
      total = Integer.parseInt(abcd.substring(0, 1));
      ans = abcd.substring(0, 1);
      for(int j = 0; j < n - 1; j++){
        if((1&i>>j) == 1){
          //sb.insert(j + 1 + count, "+");
          //count++;
          total += Integer.parseInt(abcd.substring(j + 1, j + 2));
          ans += "+" + abcd.substring(j + 1, j + 2);
        }else{
          total -= Integer.parseInt(abcd.substring(j + 1, j + 2));
           ans += "-" + abcd.substring(j + 1, j + 2);
          //sb.insert(j + 1 + count, "-");
          //count++;
        }
      }
      if(total == 7){
        break;
      }
    }
    System.out.println(ans + "=7");
  }
}

Measured memory_bytes: 21716
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define ull unsigned long long int
#define Endl endl
#define mod  1000000007
#define mkp make_pair
#define pb push_back
#define cin(n) scanf("%d",&n)
#define cout(n) printf("%d ",n)
#define sf(n) scanf("%d",&n)
#define pf(n) printf("%d ",n)
#define bitget(n) __builtin_popcountll(n)
#define maxi 500111

ll dx[] = {1,1,0,-1,-1,-1,0,1};
ll dy[] = {0,-1,-1,-1,0,1,1,1};
ll dxx[] = {1,-1,0,0};
ll dyy[] = {0,0,-1,1};
ll modexpo(ll x,ll y){if(y==0)return 1;if(y%2){ll viky=modexpo(x,y/2);
return (((x*viky)%mod)*viky)%mod;}else{ll viky=modexpo(x,y/2);return (viky*viky)%mod;
}}
ll intpoint(ll x1, ll y1, ll x2, ll y2) { return ( __gcd(abs(x1-x2),abs(y1-y2))+1); }
bool isvalid(ll x,ll y,ll n,ll m) { return (x>=0&&x<n&&y>=0&&y<m); }
// mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
// int pp = uniform_int_distribution<int>(0, kk-1)(rng);
// ---------------------///////////////---------------------------------
// ---------------------///////////////----------------------------------
// -------------/////////////////---------------------------------///////


ll dp[100011],n,k,ap[1000];

bool check(ll remain){

  if(dp[remain] != -1){
    return dp[remain];
  }

  ll ok = 1;

  for(ll i=0;i<n;i++){
    if(remain>=ap[i]){
      ok = ok&check(remain-ap[i]);
    }
  }

  dp[remain] = !ok;

  return dp[remain];

}
int main() {
    
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin>>n>>k;
    
    for(ll i = 0;i<n;i++){
      cin>>ap[i];
    }
    for(ll i=0;i<=100000;i++){
      dp[i] = -1;
    }
    if(check(k)){
      cout<<"First";
    }else{
      cout<<"Second";
    }

    return 0;
}

Measured memory_bytes: 4224
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define chmax(a, b) a = max(a, b);
#define chmin(a, b) a = min(a, b);
using namespace std;
using ll = long long;
using P = pair<int,int>;

int main() {
	string s;
	cin >> s;
	vector<int> d;
	d.push_back(0);
	int now = 0;
	rep(i, s.size()) {
		now += (s[i] == '1' ? -1 : 1);
		d.push_back(now);
	}
	int mx = 0, mn = 0;
	for(int di: d) {
		chmax(mx, di);
		chmin(mn, di);
	}
	int mxind;
	rep(i, d.size()) {
		if (d[i] == mx) {
			mxind = i;
			break;
		}
	} // smallest index
	int mnind;
	rep(i, d.size()) {
		if (d[i] == mn) {
			mnind = i;
		}
	} // largest index
	if (mxind < mnind) {
		cout << mx - mn << endl;
		return 0;
	}
	int mx2 = mn;
	rep(i, mnind) chmax(mx2, d[i]);
	int ans = 1001001001;
	rep(_, 2) {
		priority_queue<P> q;
		for(int i = mnind + 1; i < d.size(); i++) {
			q.emplace(-d[i], i);
		}
		int cnt = 0;
		int tmx = mn;
		for(int i = mnind; i < mxind; i++) {
			while(q.top().second <= i) q.pop();
			if (s[i] == '?' && -q.top().first - (cnt + 1) * 2 >= mn) {
				cnt += 1;
			}
			chmax(tmx, d[i+1] - cnt * 2);
		}
		chmin(ans, max(tmx, mx2) - mn);
		mn--;
	}
	cout << ans << endl;

	
}


Measured memory_bytes: 24228
use std::io::*;
use std::str::FromStr;

#[allow(unused_macros)]
macro_rules! scan {
  ($e:expr; $t:ty) => {
    $e.get::<$t>()
  };
  ($e:expr; $($t:ty), *) => {
    ($($e.get::<$t>(),)*)
  }
}

struct Scanner<R: BufRead> {
  reader: R,
  iter: std::vec::IntoIter<String>
}

#[allow(dead_code)]
impl<R: BufRead> Scanner<R> {
  fn new(reader: R) -> Scanner<R> {
    Scanner { reader, iter: vec![String::new()].into_iter() }
  }
  fn new_line(&mut self) {
    let mut line = String::new();
    self.reader.read_line(&mut line).ok();
    self.iter = line.trim().split_whitespace().map(|s| s.to_string()).collect::<Vec<String>>().into_iter();
  }
  fn get<T: FromStr>(&mut self) -> T {
    self.iter.next().unwrap().parse().ok().unwrap()
  }
  fn get_line(&mut self) -> String {
    let mut line = String::new();
    self.reader.read_line(&mut line).ok();
    line.trim().to_string()
  }
}

fn main() {
  let cin = stdin();
  let cin = cin.lock();
  let mut sc = Scanner::new(cin);
  sc.new_line();
  let m = scan!(sc; i64);
  let mut score = [0, 0];
  for _ in 0..m {
    sc.new_line();
    let (t, h) = scan!(sc; String, String);
    if t == h {
      score[0] += 1;
      score[1] += 1;
    }
    else {
      let idx = if t > h { 0 } else { 1 };
      score[idx] += 3;
    }
  }
  println!("{}", score.iter().map(|v| v.to_string()).collect::<Vec<String>>().join(" "));
}



Measured memory_bytes: 5052
#include<iostream>
#include<cstdio>
#include<iomanip>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<stack>
#include<queue>
#include<map>
#include<set>
#include<vector>
#include<time.h>
#include<sstream>
#define MINN -1e8 
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const ll INF=0x3f3f3f3f3f3f;
const int P=1e9+7;
const int MAXN=32000;
const double pi=3.1415926;
//const int MINN=-1e8;
const ll mod=1000000007;

//map<string,ll> m;
//map<ll,ll> m;

//set<ll> s;

//vector<ll> v;

//scanf("%lld",&t);
//scanf("%lld%lld",&,&);
int a[505][505],n;
void f(int l,int r,int tmp)
{
	if(l==r)return;
	int mid=(r+l)/2;
	for(int i=l;i<=mid;i++)
	{
		for(int j=mid+1;j<=r;j++)
		{
			a[i][j]=tmp;
		}
	}
	if(r!=l+1)
	{
		f(l,mid,tmp+1);
		f(mid+1,r,tmp+1);
	}
}
int main()
{
	cin>>n;
	f(1,n,1);
	for(int i=1;i<=n-1;i++)
	{
		cout<<a[i][i+1];
		for(int j=i+2;j<=n;j++)
		{
			cout<<" "<<a[i][j];
		}
		cout<<'\n';
	}
	return 0;
}
//ll n,m,t,a,x,ans,res;
//ll powmod(ll a,ll b)     //快速幂 
//{
//	ll tmp=a%mod;
//	ll ans=1;
//	while(b)
//	{
//		if(b&1)ans=ans*tmp%mod;
//		tmp=tmp*tmp%mod;
//		b>>=1;
//	}
//	return ans%mod;
//}


//bool is_prime(ll a)     //判断素数 
//{
//	if(a==2)return 1;
//	else if(a==1||a%2==0)return 0;
//	else
//	{
//		for(ll i=3;i*i<=a;++i)
//		{
//			if(a%i==0)return 0;
//		}
//	}
//	return 1;
//}



Measured memory_bytes: 1408
n,x = map(int,input().split())
ls = list(map(int,input().split()))
ls = list(map(lambda t:abs(t-x),ls))
def gcd(a,b):
    if b == 0:
        return a
    else:
        return gcd(b,a%b)
def gcdlist(l):
    a = l[0]
    for i in range(len(l)):
        a = gcd(a,l[i])
    return a
print(gcdlist(ls))

Measured memory_bytes: 63768
#include <bits/stdc++.h>
using namespace std;
 
int main(){
	string s;
	cin >> s;
  	if(s == "Sunny"){
    cout << "Cloudy" << endl; 
    return 0;
    }else if(s == "Cloudy"){
    cout << "Rainy" << endl;
    return 0;
    }else if(s == "Rainy"){
    cout << "Sunny" << endl;
    return 0;
    }
}

Measured memory_bytes: 3584
#include <bits/stdc++.h>
using namespace std;

int main() {
  int M, D;
  cin >> M >> D;
  
  int count=0;
  
  for(int i=1;i<=D;i++){
    if((i/10)>=2 && (i%10)>=2){
      if((i/10)*(i%10) <= M){
        count++;
      }
    }
  }
  
  cout << count << endl;

}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <algorithm>
#include <queue>
#include <map>
using namespace std;
long long int pow2[61] = {}; 
long long int pow3[61] = {}; 
long long int P = 1e9 + 7; 
map<long long int, long long int> dp; 
long long int ans(long long int n){
	if(dp[n] > 0){return dp[n];}
	if(n == 0){
         	return dp[0] = 1; 
 	}
	int a = upper_bound(pow2, pow2 + 61, n) - pow2; 
	long long int b = pow2[a] - n; 
	if(b == 1){
		return dp[n] = (pow3[a] + 1)/2 % P;
	}
	else{
		long long int Q = (P + pow3[a-1] + ans(n - pow2[a-1]) - ((n == pow2[a] - 2) ? 0 : ans(pow2[a] - n - 3))) % P;
		return dp[n] = Q; 
	}
}
int main() {
	pow2[0] = 1, pow3[0] = 1; 
	for(int i = 1; i <= 60; i++){
		pow2[i] = pow2[i-1] * 2; 
		pow3[i] = (pow3[i-1] * 3) % P; 
	}
	long long int N; 
	cin >> N; 
	cout << ans(N) << endl; 
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <unordered_map>
typedef long long ll;
#define rep(i,m,n) for(ll i = (m); i < (n); i++)
#define rrep(i,m,n) for(ll i = (m); i >= (n); i--)
#define print(x) cout << (x) << endl;
#define print2(x,y) cout << (x) << " " << (y) << endl;
#define printa(x,n) for(ll i = 0; i < n; i++){ cout << (x[i]) << " \n"[i == n-1];}
#define printp(x,n) for(ll i = 0; i < n; i++){ cout << "(" << x[i].first << ", " << x[i].second << ") "; } cout << endl;
#define INF (1e18)
using namespace std;
const ll MOD = 1e9 + 7;
typedef pair<ll, ll> lpair;
ll f(ll n){
    return (n*n + 4) / 8;
}

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll H,W;
    cin >> H >> W;
    char C[110][110];
    rep(i,0,H){
        rep(j,0,W){
            cin >> C[i][j];
        }
    }
    rep(i,0,H){
        rep(j,0,W){
            cout << C[i][j];
        }
        cout << endl;
        rep(j,0,W){
            cout << C[i][j];
        }
        cout << endl;
    }
}


Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
using namespace std;

int n;
int a[110], i, j, aux, mid;

void rotire(){
    rotate(a,a+1,a+n);
}

int main()
{
    cin>>n;
    mid=n/2;
    if(n==2) {
        cout <<-1 <<'\n';
        return 0;
    }
    for(i=0; i<n; i++)
        a[i]=i+1;

    for(i=0; i<n; i++)
    {
        rotire();
        if(n%2==0 && i>=mid)
        {
            aux=a[mid-1];
            a[mid-1]=a[mid];
            a[mid]=aux;
        }

        for(j=0; j<n-1; j++)
            cout << a[j]<<" ";
        cout<<'\n';

        if(n%2==0 && i>=mid)
        {
            aux=a[mid-1];
            a[mid-1]=a[mid];
            a[mid]=aux;
        }
    }
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define r(i,n) for(int i=0;i<n;i++)
#define int long long
using namespace std;
typedef pair<int,int>P;

bool u[10000009];

signed main(){
    int n;
    cin>>n;
    int sum=0;
    vector<int>v;
    for(int i=2;i<=10000008;i++)if(!u[i]){
        v.push_back(i);
        for(int j=i+i;j<10000008;j+=i){
            u[j]=1;
        }
    }

    r(i,v.size()){
        if(v[i]>n)break;
        if(!u[2+v[i]])sum++;
    }
    cout<<sum*2<<endl;
}


Measured memory_bytes: 21060
while True:
    H, W = map(int, input().split())
    if H == 0:
        break
    original_diagonal = H**2 + W**2

    ans_h = 200
    ans_w = 200
    ans_diagnal = 200000000

    for i in range(1, 150):
        for j in range(i+1, 150):
            new_diagonal = i**2 + j**2
            if original_diagonal > new_diagonal or (original_diagonal == new_diagonal and i <= H):
                continue
            if (new_diagonal < ans_diagnal) or (new_diagonal == ans_diagnal and i < ans_h):
                ans_h = i
                ans_w = j
                ans_diagnal = new_diagonal

    print(ans_h, ans_w)



Measured memory_bytes: 5592
N, K = map(int, input().split())
A = list(map(lambda a: int(a) - 1, input().split()))

T = [A[:]]
for _ in range(64):
    prev = T[-1]
    T.append([prev[a] for a in prev])

now = 0
for d, P in enumerate(T):
    if ((1 << d) & K) > 0:
        now = P[now]
print(now + 1)


Measured memory_bytes: 121548
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <queue>
#include <ctime>
#include <cassert>
#include <complex>
#include <string>
#include <cstring>
#include <chrono>
#include <random>
#include <queue>
#include <bitset>

using namespace std;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);

	int n;
	cin >> n;

	int a[100];
	for (int i = 0; i < n; i++) {
		cin >> a[i];
	}

	int con = 0;
	for (int i = 0; i < n - 1; i++) {
		int min = i;
		for (int j = i; j < n; j++) {
			if (a[j] < a[min]) {
				min = j;
			}
		}
		swap(a[i], a[min]);
		if (min != i) {
			con++;
		}
	}

	for (int i = 0; i < n; i++) {
		if (i)  cout << ' ';
		cout << a[i];
	}
	cout << endl;

	cout << con << endl;
}


Measured memory_bytes: 3172
#include <stdio.h>

int main()
{
	int a,b,c,i,n=0;
	
	scanf("%d %d %d",&a,&b,&c);
	
	for(i=a;i<=b;i++){
		
		if((c%i)==0){
			n++;
			
		}
		
	}
	
	printf("%d\n",n);
	
  return 0;
}

Measured memory_bytes: 596
#include <bits/stdc++.h>
using namespace std;
#define FIN ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

int main() {FIN
    
    int i = 1, n;
    while (cin >> n, n) {
        cout << "Case " << i << ": " << n << "\n";
        i++;
    }
    
    return 0;
}


Measured memory_bytes: 3164
#include <bits/stdc++.h>

#define REP(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define ALL(x) (x).begin(),(x).end()

using namespace std;

template <typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template <typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }

using ll = long long;
using ld = long double;

const int INF = 1e9;
const ld eps = 1e-9, pi = acos(-1.0);

int main() {
  cout << setprecision(12) << fixed << boolalpha;
  ll N, X;
  cin >> N >> X;
  ll sum = N;
  ll a = N - X, b = X;
  if (a < b) swap(a, b);
  while (b > 0) {
    sum += b * (a / b) * 2;
    tie(a, b) = make_pair(b, a % b);
  }
  cout << sum - a << endl;
  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;

int main(){
    int q;
    cin >> q;
    for(int qnum = 0; qnum < q; qnum++){
        string x, y;
        cin >> x;
        cin >> y;
        vector<vector<int>> memo(x.length()+1, vector<int>(y.length()+1, 0));
        for(int i = 0; i < x.length(); i++){
            for(int j = 0; j < y.length(); j++){
                if(x[i] == y[j]){
                    memo[i+1][j+1] = memo[i][j]+1;
                }else{
                    memo[i+1][j+1] = max(memo[i][j+1], memo[i+1][j]);
                }
            }
        }
        cout << memo[x.length()][y.length()] << endl;
    }
    return 0;
}


Measured memory_bytes: 6836
#include<bits/stdc++.h>
using namespace std;
int main(){
    int a,b;
    cin >> a >> b;
    int count = 1;
    int sum = 0;
    for(int i = 0;i<a;i++){
        int c;
        cin >> c;
        sum += c;
        if(b < sum){
            break;
        }
        count++;
    }
    cout << count << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define INF 1200000000

using namespace std;

typedef pair<int, int> P;
typedef long long int LL;

int main() {
    LL n;
    cin >> n;
    LL mx = -INF;
    LL p = -1;
    for (int i = 0; i < n; i++) {
        LL tmp;
        cin >> tmp;
        if (p != -1) {
            mx = max(tmp - p, mx);
            if (tmp < p) {
                p = tmp;
            }
        } else {
            p = tmp;
        }
    }

    cout << mx << endl;

    return 0;
}

Measured memory_bytes: 3104
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll INF = 1LL << 62;

int k, x;
void input() {
    cin >> k >> x;
}

void solve() {
    if(500 * k >= x) {
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }
}



int main() {
    input();
    solve();
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define REP(i,a,b) for (int i = a; i < (b); ++i)
#define all(x) (x).begin(),(x).end()
const int INF = 1000000007;
typedef long long ll;
using namespace std;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
ll gcd(ll a, ll b) { return b ? gcd(b, a%b) : a; }
int main(){
  // ios::sync_with_stdio(false);cin.tie(nullptr);
  int n;
  cin >> n;
  vector<int>v(n);
  rep(i,n)cin >> v[i];
  int now = 1;
  rep(i,n){
    if(now == v[i]){
      now++;
    }
  }
  if(now - 1){
    cout << n - now + 1<< endl;
  }
  else{
    cout << -1 << endl;
  }
  return 0;
}


Measured memory_bytes: 1024
#include<bits/stdc++.h>
#define rep(i,n) for(int i=0; i<(n); i++)
using namespace std;
using ll=long long;

int main(){
  string s;
  ll k,count=0;
  cin >> s >> k;
  rep(i,100){
    if(s[i]=='1') count++;
    if(s[i]!='1') break;
  }
  
  if(k>count){
    rep(i,100){
      if(s[i]!='1'){
       cout << s[i] << endl;
       return 0;
      }
    }
  }
  
  if(k<=count) cout << 1 << endl;
  
  return 0;
}


Measured memory_bytes: 3556