akhauriyash/Code-Regression huggingface dataset:
/*
    Author:zeke
    
    pass System Test!
    GET AC!!
*/
#include <iostream>
#include <queue>
#include <vector>
#include <iostream>
#include <vector>
#include <string>
#include <cassert>
#include <algorithm>
#include <functional>
#include <cmath>
#include <queue>
#include <set>
#include <stack>
#include <deque>
#include <map>
#include <iomanip>
#include <utility>
#include <stack>
#include <bitset>
using ll = long long;
using ld = long double;
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define all(x) (x).begin(), (x).end()
#define rep3(var, min, max) for (ll(var) = (min); (var) < (max); ++(var))
#define repi3(var, min, max) for (ll(var) = (max)-1; (var) + 1 > (min); --(var))
#define Mp(a, b) make_pair((a), (b))
#define F first
#define S second
#define Icin(s) \
    ll(s);      \
    cin >> (s);
#define Scin(s) \
    ll(s);      \
    cin >> (s);
template <class T>
bool chmax(T &a, const T &b)
{
    if (a < b)
    {
        a = b;
        return 1;
    }
    return 0;
}
template <class T>
bool chmin(T &a, const T &b)
{
    if (b < a)
    {
        a = b;
        return 1;
    }
    return 0;
}
typedef pair<ll, ll> P;
typedef vector<ll> V;
typedef vector<V> VV;
typedef vector<P> VP;
ll mod = 1e9 + 7;
ll MOD = 1e9 + 7;
ll INF = 1e18;
long long modinv(long long a, long long m)
{
    long long b = m, u = 1, v = 0;
    while (b)
    {
        long long t = a / b;
        a -= t * b;
        swap(a, b);
        u -= t * v;
        swap(u, v);
    }
    u %= m;
    if (u < 0)
        u += m;
    return u;
}
//a,m=MOD MOD逆元
long double n;
long double dp[301][301][301];
long double cal(int i,int j,int k){
    if(dp[i][j][k]!=-1)
        return dp[i][j][k];
    if(i==0&&j==0&&k==0)
        return 0.0;
    long double res = n;
    if(i>=1)
        res += cal(i - 1, j, k) * i;
    if(j>=1)
        res += cal(i + 1, j - 1, k) * j;
    if(k>=1)
        res += cal(i, j + 1, k - 1) * k;
    res /= (i + j + k);
    return dp[i][j][k] = res;
}
int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    cin >> n;
    int l1 = 0;int l2 = 0;int l3 = 0;
    for (int i = 0; i < n;i++){
        int x;
        cin>>x;
        if(x==1)
            l1++;
        if(x==2)
            l2++;
        if(x==3)
            l3++;
    }
    for (int i = 0; i < 301;i++)
        for (int j = 0; j < 301;j++)
            for (int k = 0; k < 301;k++)
                dp[i][j][k] = -1;
    cout << setprecision(10) << cal(l1, l2, l3) << endl;
}


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

bool visit(const vector<vector<int>>& g, int v, vector<int> &order, vector<int> &color) {
  color[v] = 1;
  for (int i = 0; i < g[v].size(); i++) {
    int w = g[v][i];
    if (color[w] == 2) continue;
    if (color[w] == 1) return false;
    if (!visit(g, w, order, color)) return false;
  }
  order.push_back(v); color[v] = 2;
  return true;
}
bool topologicalSort(const vector<vector<int>>& g, vector<int>& order) {
  int n = g.size();
  vector<int> color(n);
  for (int u = 0; u < n; u++) {
    if (!color[u] && !visit(g, u, order, color)) {
      return false;
    }
  }
  reverse(order.begin(), order.end());
  return true;
}


int main(void) {
  int N, M;
  cin >> N >> M;
  int E = N - 1 + M;
  vector<vector<int>> chi(N);
  vector<vector<int>> par(N);

  int a, b;
  vector<vector<int>> es(N);
  for (int i = 0; i < E; i++) {
    cin >> a >> b;
    a--;b--;
    chi[a].push_back(b);
    par[b].push_back(a);
    es[a].push_back(b);
  }

  // vector<int> leaf;
  int root = -1;
  vector<int> depth(N, -1);
  for (int i = 0; i < N; i++) {
    if (par[i].size() == 0) {
      depth[i] = 0;
      root = i;
    }
  }

  vector<int> order;
  topologicalSort(es, order);
  for (int i = 0; i < N; i++) {
    int u = order[i];
    for (int v : es[u]) {
      depth[v] = depth[u] + 1;
    }
  }
  for (int v = 0; v < N; v++) {
    int p = -1, a = -1;
    // cerr << v << endl;
    for (int w : par[v]) {
      // cerr << w << " : " << depth[w] << endl;
      if (a < depth[w]) {
        p = w;
        a = depth[w];
      }
    }
    cout << p + 1 << endl;
  }

  return 0;
}

Measured memory_bytes: 22388
#include <iostream>
#include <string>
#include <map>

using namespace std;
#define REP(i,n) for(int i = 0; i < (int)(n); i++)
int main() {
  int N; cin>>N;
  string S; cin>>S;
  REP(i,S.length()) {
    char c = S[i];
    int pos = (c - 'A' + N) % 26 + 'A';
    S[i] = pos;
  }
  cout << S << endl;
  return 0;
}


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

int main() {
  int N,K;
  cin>>N>>K;
  vector<double> a(N+K);
  for(int i=0;i<N;i++) cin>>a[i];
  for(int i=0;i<N;i++) a[i]=a[i]/2+0.5;
  //sort(a.begin(),a.end());
  //reverse(a.begin(),a.end());
  vector<double> r(N);
  for(int i=0;i<K;i++) r[0]+=a[i];
  for(int i=0;i<N-1;i++){
    r[i+1]=r[i]-a[i]+a[K+i];
  }

  double ans=0;
  for(int i=0;i<=N-K;i++){
  //  double x=r[i]-r[i-K];
  //  cout<<x<<endl;
  double x=r[i];
//cout<<x<<endl;
    if(x>ans){
      ans=x;
    }
  }

  cout<<setprecision(20)<<ans<<endl;
  }


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

int main(){
  int a, b, c;
  vector<int> v;
  cin >> a >> b >> c;
  v.push_back(a);
  v.push_back(b);
  v.push_back(c);
  sort(v.begin(), v.end());
  
  if (v[0] + v[1] == v[2])
    cout << "Yes" << endl;
  else
    cout << "No" <<endl;
  
  return 0;
}


Measured memory_bytes: 256
def calc_divisor(x):
  res = 0
  for i in range(1,x+1):
    if x % i == 0:
      res += 1
  return res

N = int(input())
ans = 0
for i in range(1,N+1):
  if i % 2 == 1 and calc_divisor(i) == 8:
    ans += 1
print(ans)


Measured memory_bytes: 2940
#include <stdio.h>          // printf(), getc()
#include <string.h>         // memcpy(), strstr()

#define MAX_L 100
const char NUL = '\0';

int
main(int argc, char** argv)
{
	char s[2 * MAX_L + 1];
	char p[MAX_L + 1];
	int len1, len2;
	int c;

	c = getc(stdin);
	len1 = 0;
	while (c != '\n' && c != EOF)
	{
		s[len1++] = c;
		c = getc(stdin);
	}

	c = getc(stdin);
	len2 = 0;
	while (c != '\n' && c != EOF)
	{
		p[len2++] = c;
		c = getc(stdin);
	}

	p[len2] = NUL;
	memcpy(&s[len1], s, len2 - 1);
	s[len1 + len2 - 1] = NUL;

	if (strstr(s, p) != NULL)
		printf("Yes\n");
	else
		printf("No\n");

	return 0;
}

Measured memory_bytes: 524
n = int(input())
s = input()
t = input()
count = len(s)+len(t)
flag = 1
for i in range(n):
    if s[i:]==t[:n-i]:
        c = n-i
        flag = 0
        break
if flag:
    print(count)
else:
    print(count-c)

Measured memory_bytes: 3060
#include<bits/stdc++.h>
#include<string.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pl;
#define all(a) (a).begin(),(a).end()
#define overload4(_1, _2, _3, _4, name, ...) name
#define rep1(n) for(ll i = 0;i < (n);i++)
#define rep2(i,n) for(ll i = 0;i < (n);i++)
#define rep3(i,a,b) for(ll i = (a);i < (b);i++)
#define rep4(i,a,b,c) for(ll i = (a);i < (b);i += (c))
#define rep(...) overload4(__VA_ARGS__, rep4, rep3, rep2, rep1)(__VA_ARGS__)
#define rrep1(n) for(ll i = (n)-1;i >= 0;i--)
#define rrep2(i,n) for(ll i = (n)-1;i >= 0;i--)
#define rrep3(i,a,b) for(ll i = (a)-1;i >= (b);i--)
#define rrep4(i,a,b,c) for(ll i = (a)-1;i >= (b);i -= (c))
#define rrep(...) overload4(__VA_ARGS__, rrep4, rrep3, rrep2, rrep1)(__VA_ARGS__)
#define SHOW(x) cout << #x << ": " << x << endl;
template<class T> ll sumArr(const T& a){ return accumulate(all(a), 0LL);}
template<class T> auto minArr(const T& a){ return *min_element(all(a));}
template<class T> auto maxArr(const T& a){ return *max_element(all(a));}
template<class T> void DEBUG_PRINT(T tmp){cout<<tmp<<endl;}
template<class T1,class... T2> void DEBUG_PRINT(T1 tmp,T2... tmp2){cout<<tmp<<" ";DEBUG_PRINT(tmp2...);}
ll gcd(ll a, ll b){ while(b){ ll c = b; b = a % b; a = c; } return a; }
const ll INF=1e18,MOD = 1e9+7;
const int iINF = 1e9;

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

    int n,sum;
    cin>>n;
    vector<int>a(n);
    rep(i,n)cin>>a[i];
    sum = a[0];
    rep(i,1,n)sum ^= a[i];

    rep(i,n){
        cout<<(sum ^ a[i])<<" \n"[i + 1 == n];
    }


    
    return 0;
}


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

#define int long long

signed main() {
    int n;
    cin >> n;
    int d, x;
    cin >> d >> x;
    int ans = n;
    for(int i=0; i<n; ++i) {
        int a;
        cin >> a;
        int b = a + 1;
        while(true) {
            if(b>d) break;
            ans++;
            b += a;
        }
    }
    cout << x + ans << endl;
    return 0;
}



Measured memory_bytes: 256
import sys
import math
import bisect
from collections import defaultdict, deque
from heapq import heappush, heappop


def LI(): return [int(x) for x in sys.stdin.readline().split()]


def I(): return int(sys.stdin.readline())


def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res


def IR(n):
    return [I() for i in range(n)]


# A
def A():
    n = I()
    print(n // 2 - 1 if n % 2 == 0 else n // 2)
    return


# B
def B():
    return


# C
def C():
    return


# D
def D():
    return


# E
def E():
    return


# F
def F():
    return


# Unittest
def resolve():
    A()
    return


# Solve
if __name__ == "__main__":
    A()


Measured memory_bytes: 38384
#include<bits/stdc++.h>
typedef long long int ll;
typedef unsigned long long int ull;
#define BIG_NUM 2000000000
#define HUGE_NUM 99999999999999999
#define MOD 1000000007
#define EPS 0.000000001
using namespace std;


#define NUM 1005

struct WORD{
	int loc;
	char ch;
};

struct Info{
	int Y,H;
};

struct Data{
	Data(int arg_Y,int arg_length,int arg_index){
		Y = arg_Y;
		length = arg_length;
		index = arg_index;
	}
	int Y,length,index;
};

int N,A,B,num_query;
map<int,char> MAP;
WORD word[NUM];
Info info[NUM];
vector<Data> V;

int get_loc(int loc){

	bool FLG;
	int left,right,mid;

	while(true){
		FLG = false;

		left = 0,right = V.size()-1,mid = (left+right)/2;

		while(left <= right){

			if(loc >= V[mid].Y && loc <= V[mid].Y+V[mid].length-1){

				loc = (loc-V[mid].Y)%(V[mid].Y-info[V[mid].index].H)+info[V[mid].index].H;
				FLG = true;
				break;

			}else if(loc > V[mid].Y){

				left = mid+1;

			}else{

				right = mid-1;
			}
			mid = (left+right)/2;
		}

		if(!FLG)break;
	}

	return loc;
}

int main(){

	scanf("%d %d %d %d",&N,&A,&B,&num_query);

	int loc;
	char buf[2];

	for(int loop = 0; loop < A; loop++){

		scanf("%d %s",&word[loop].loc,buf);
		word[loop].ch = buf[0];
	}

	for(int i = 0; i < B; i++){
		scanf("%d %d",&info[i].Y,&info[i].H);
	}
	info[B].Y = N+1;

	for(int i = 0; i < B; i++){
		if(info[i].H == 0)continue;
		V.push_back(Data(info[i].Y,info[i+1].Y-info[i].Y,i));
	}

	for(int loop = 0; loop < A; loop++){

		loc = word[loop].loc;
		MAP[get_loc(loc)] = word[loop].ch;
	}


	for(int loop = 0; loop < num_query; loop++){

		scanf("%d",&loc);

		auto at = MAP.find(loc = get_loc(loc));

		if(at == MAP.end()){

			printf("?");

		}else{

			printf("%c",MAP[loc]);
		}
	}

	printf("\n");
	return 0;
}



Measured memory_bytes: 3196
{-# OPTIONS_GHC -O2 #-}
{-# LANGUAGE BangPatterns      #-}
{-# LANGUAGE CPP               #-}
{-# LANGUAGE OverloadedStrings #-}
{-# LANGUAGE TupleSections     #-}

import           Control.Applicative
import           Control.Monad
import           Control.Monad.Primitive
import           Control.Monad.ST
import           Control.Monad.State.Strict
import           Data.Bool
import qualified Data.ByteString.Char8       as B
import qualified Data.ByteString.Unsafe      as B
import           Data.Char
import           Data.Function
import qualified Data.IntMap.Strict          as IM
import qualified Data.IntSet                 as IS
import           Data.List
import           Data.Monoid
import           Data.Ord
import           Data.Primitive.MutVar
import qualified Data.Set                    as S
import           Data.Tuple
import qualified Data.Vector                 as V
import qualified Data.Vector.Generic         as G
import qualified Data.Vector.Generic.Mutable as GM
import qualified Data.Vector.Unboxed         as U
import qualified Data.Vector.Unboxed.Mutable as UM
import           Debug.Trace
import           Foreign                     hiding (void)
import           Unsafe.Coerce

main :: IO ()
main = do
    n <- readLn
    xs <- U.unfoldrN n (B.readInt.B.dropWhile isSpace) <$> B.getLine
    ys <- U.unfoldrN n (B.readInt.B.dropWhile isSpace) <$> B.getLine
    print . maybe (-1) id $ solve n xs ys

solve :: Int -> U.Vector Int -> U.Vector Int -> Maybe Int
solve n xs ys
    | sx < sy = Nothing
    | otherwise = Just . go res0 need0 . map negate . sort $ U.toList negatives
  where
    !sx = U.sum xs
    !sy = U.sum ys
    !diffs = U.filter (/= 0) $ U.zipWith (-) ys xs
    (positives, negatives) = U.partition (> 0) diffs
    !res0 = U.length positives
    !need0 = U.sum positives

    go !res !need (x:xs)
      | need <= 0 = res
      | otherwise = go (res + 1) (need - x) xs
    go res _ _ = res

Measured memory_bytes: 9596
#include <bits/stdc++.h>
#define _GLIBCXX_DEBUG
#define rep(i,n) for(int i = 0; i < (int)(n); i++)
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define sz(x) (int)(x).size()
#define all(v) v.begin(), v.end()
using namespace std;
using ll = long long;
using P = pair<int, int>;
using vi = vector<int>;
using vc = vector<char>;
using vb = vector<bool>;
using vs = vector<string>;
using vll = vector<long long>;
using vp = vector<pair<int, int>>;
using vvi = vector<vector<int>>;
using vvc = vector<vector<char>>;
using vvll = vector<vector<long long>>;
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 (b<a) {a=b; return 1;} return 0;}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    ll n, k;
    cin >> n >> k;
    vi a(n);
    rep(i, n) cin >> a[i];
    set<int> st;
    vi ans;
    int now = 1;
    while (1) {
        now = a[now-1];
        if (st.count(now)) {
            ans.pb(now);
            break;
        } else {
            st.insert(now);
            ans.pb(now);
        }
    }
    int s = 0;
    rep(i, n) {
        if (ans[i] == ans.back()) {
            s = i;
            break;
        }
    }
    vi repeat;
    for (int i = s; i < sz(ans) - 1; ++i) {
        repeat.pb(ans[i]);
    }
    int len = sz(ans) - s - 1;
    if (k <= s) {
        cout << ans[k-1] << endl;
    } else {
        k -= s;
        k %= len;
        if (k == 0) cout << repeat.back() << endl;
        else cout << repeat[k-1] << endl;
    }
}

Measured memory_bytes: 15016
#-------------------------------------------------------------------
import sys
def p(*a):
  s=" ".join(map(str,a))
  #print(s)
  sys.stderr.write(s+"\n")
#-------------------------------------------------------------------

N, M = map(int, input().split())			# "5 7" -> ["5", "7"] -> 5, 7 => N=5,K=7

A = sorted(list( map(int, input().split()) ))	# 1 2 3 4 5 ...(ソート付き)

p("A ",A)

B=[]
for i in range(M):
	b,c = map(int, input().split())
	B.append([b,c])


p("B ",B)
B=sorted(B, key=lambda x: x[1]*-1)
p("B ",B)


a=0
for i in range(len(B)):
	b = B[i]
	for j in range(b[0]):
		
		if A[a]<b[1]: A[a]=b[1]
		a+=1
		if a>=len(A): break

	if a>=len(A): break


print(sum(A))



Measured memory_bytes: 147460
#include<bits/stdc++.h>
using namespace std;
long long a=0;
int main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    //cout.setf(ios_base::fixed,ios_base::floatfield);
    int n,m,z=0;
    cin>>n;
    bool a[101]={false};
    for(int i=0;i<n;i++){
        cin>>m;
        a[m]=true;
    }
    for(int i=0;i<101;i++){
        if(a[i]==true) z++;
    }
    cout<<z<<'\n';
    return 0;
}

Measured memory_bytes: 3624
import java.util.*;

public class Main {
	
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int d = in.nextInt();
		int n = in.nextInt();
		int s = 1;
		for(int i = 0;i < d;i ++) {
			s *= 100;
		}
		if(n == 100)n ++;
		System.out.println(s * n);
	}
}


Measured memory_bytes: 21844
import java.util.*;

public class Main {
    public static void main(String args[]) throws Exception {
        Scanner sc = new Scanner(System.in);
        String s = sc.next();
        int len = s.length();
        int[] res = new int[len];

        int i = 0;
        while(i < len) {
        	int leftR = i;
        	while(i < len && s.charAt(i) == 'R') {
        		i++;
        	}
        	int rightR = i-1;

        	int leftL = i;
        	while(i < len && s.charAt(i) == 'L') {
        		i++;
        	}
        	int rightL = i - 1;
        	int cntR = rightR - leftR + 1;
        	int cntL = rightL - leftL + 1;
        	int cnt = (cntR + cntL) / 2;
        	res[rightR] = cnt;
        	res[leftL] = cnt;
        	if((cntR + cntL) % 2 != 0) {
        		if(cntR > cntL) {
        			if((cntR-1) % 2 == 0)
        				res[rightR]++;
        			else
        				res[leftL]++;
        		} else {
        			if((cntL-1) % 2 == 0)
        				res[leftL]++;
        			else
        				res[rightR]++;
        		}
        	}
        }
        for(int j = 0; j < len; j++)
        	if(j == len - 1)
        		System.out.println(res[j]);
        	else
        		System.out.print(res[j] + " ");
    }
}


Measured memory_bytes: 42884
import itertools
lst = []
for e in range(5):
    lst.append(int(input()))
ans = 10**9
for pl in list(itertools.permutations(lst)):
    minute = 0
    for i,w in enumerate(pl):
        while True:
            if minute%10 == 0:
                minute += w 
                break
            else:
                minute += 1
    ans = min(ans, minute)
print(ans)

Measured memory_bytes: 3060
import java.io.IOException;
import java.util.Scanner;

public class Main {

	public static void main(String[] args) throws IOException {

		new Main().run();
	}

	private void run() throws IOException {
		Scanner scanner = new Scanner(System.in);

		while (true) {
			p = scanner.nextInt();
			if (p == 0)
				break;
			n = new int[6];
			for (int i = 0; i < 6; i++)
				n[i] = scanner.nextInt();
			u = new int[6];
			System.out.println(slove(p, 5));
		}
	}

	private int slove(int r, int c) {
		if (c >= 0) {
			int ans = 1 << 30;
			for (int i = 0; i < 2; i++) {
				u[c] = Math.min(n[c], r / coin[c] + i);
				ans = Math.min(ans,
						slove(Math.max(0, r - u[c] * coin[c]), c - 1) + u[c]);
			}
			return ans;
		} else {
			int ch = -p;
			for (int i = 0; i < 6; i++)
				ch += coin[i] * u[i];
			int ans = 0;
			for (int i = 5; i >= 0; i--) {
				ans += ch / coin[i];
				ch %= coin[i];
			}
			return ans;
		}
	}

	int p;
	int[] n, u;
	int[] coin = { 1, 5, 10, 50, 100, 500 };
}

Measured memory_bytes: 23036
#include <cstdio>
#include <iostream>
#include <string>

using namespace std;

int main() {
	int a, b, c, d;
	string num;
	while (cin >> num) {
		int flag = 0;
		a = num[0] - '0';
		b = num[1] - '0';
		c = num[2] - '0';
		d = num[3] - '0';
		for (int i = 0; i < 2&&!flag; i++) {
			for (int j = 0; j < 2&&!flag; j++) {
				for (int k = 0; k < 2; k++) {
					//cout << a << b << c << d;
					if (i) b = -b;
					if (j) c = -c;
					if (k) d = -d;
					if ((a + b + c + d) == 7)
					{
						cout << a;
						if (b < 0) cout << "-" << abs(b);
						else cout << "+" << b;
						if (c < 0) cout << "-" << abs(c);
						else cout << "+" << c;
						if (d < 0) cout << "-" << abs(d);
						else cout << "+" << d;
						cout << "=7" << endl;
						flag = 1;
						break;
					}
					b = abs(b);
					c = abs(c);
					d = abs(d);
				}
			}
		}
	}
	return 0;
}

Measured memory_bytes: 256
/*
 * Dictionary.c
 *
 *  Created on: 2015/02/16
 */
#include<stdio.h>
#include<string.h>

#define M 1000213

void insert(char*);
int find(char*);
int get_key(char*);
int get_keycode(char);
int get_hash_num(int,int);

char hash[M][13]={"\0"};

int main(void){
	int n;
	int i;
	char str[13],input[7];

	scanf("%d",&n);

	for(i=0;i<n;i++){
		scanf("%s %s",input,str);

		if(input[0]=='i') insert(str);

		if(input[0]=='f'){
			if(find(str)==1) printf("yes\n");
			else printf("no\n");
		}
	}

	return 0;
}

void insert(char *str){
	int i=0,hash_num,data;

	data=get_key(str);

	while(1){
		hash_num=get_hash_num(data,i);
		if(strcmp(hash[hash_num],"\0")==0){
			strcpy(hash[hash_num],str);
			break;
		}
		i++;
	}

}

int find(char *str){
	int data,hash_num,i=0;

	data=get_key(str);

	while(1){
		hash_num=get_hash_num(data,i);
		if(strcmp(hash[hash_num],"\0")==0) return 0;
		if(strcmp(hash[hash_num],str)==0) return 1;
		i++;
	}
}

int get_key(char *str){
	int data=0,cnt=0,p=1;

	while(str[cnt]!='\0'){
		data+=p*get_keycode(str[cnt]);
		p*=5;
		cnt++;
	}

	return data;
}

int get_keycode(char work){
	switch(work){
	case 'A':
		return 1;
	case 'C':
		return 2;
	case 'G':
		return 3;
	case 'T':
		return 4;
	}
}

int get_hash_num(int data,int i){
	return ((data%M)+i*(data%(M-1)+1))%M;
}



Measured memory_bytes: 15368
// ===================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// ===================================
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <vector>
#include <cmath>
#define re register
using namespace std;

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

const int N=600000+10;
const int mod=924844033;
inline int qpow(int a,int b) { int c=1;
    for (;b;b>>=1,a=1ll*a*a%mod) if (b&1) c=1ll*c*a%mod;
    return c;
}

int n;

struct edge { int v,nxt; } e[N<<1];
int head[N];
inline void addEdge(int u,int v) {
    static int c=0;
    e[++c]=(edge){v,head[u]},head[u]=c;
}

int fac[N],ifac[N];
inline void init(int n) {
    fac[0]=1;
    for (re int i=1;i<=n;++i) fac[i]=1ll*fac[i-1]*i%mod;
    ifac[n]=qpow(fac[n],mod-2);
    for (re int i=n;i;--i) ifac[i-1]=1ll*ifac[i]*i%mod;
}
inline int C(int n,int m) {
    return 1ll*fac[n]*ifac[m]%mod*ifac[n-m]%mod;
}

int cnt[N],sz[N];
inline void dfs(int u,int fa) {
    sz[u]=1;
    for (re int i=head[u];i;i=e[i].nxt) {
        int v=e[i].v; if (v==fa) continue;
        dfs(v,u),sz[u]+=sz[v],++cnt[sz[v]];
    }
    ++cnt[n-sz[u]];
}

int r[N],F[N],G[N];
inline void NTT(int* A,int n,int op) {
    for (re int i=0;i<n;++i) if (i<r[i]) swap(A[i],A[r[i]]);
    for (re int i=1;i<n;i<<=1) {
        int rot=qpow(op==1?5:554906420,(mod-1)/(i<<1));
        for (re int j=0;j<n;j+=i<<1)
            for (re int k=0,w=1;k<i;++k,w=1ll*w*rot%mod) {
                int x=A[j+k],y=1ll*w*A[j+k+i]%mod;
                A[j+k]=(x+y)%mod,A[j+k+i]=(x-y+mod)%mod;
            }
    }
    if (op==-1) { int inv=qpow(n,mod-2);
        for (re int i=0;i<n;++i) A[i]=1ll*A[i]*inv%mod;
    }
}

int main() {
    n=read();
    for (re int i=1;i<n;++i) {
        int u=read(),v=read();
        addEdge(u,v),addEdge(v,u);
    }
    dfs(1,0); init(n);
    for (re int i=1;i<=n;++i) F[i]=1ll*cnt[i]*fac[i]%mod;
    reverse(F,F+n+1);
    for (re int i=0;i<=n;++i) G[i]=ifac[i];
    int lim=1,l=0;
    for (;lim<=n<<1;lim<<=1,++l);
    for (re int i=0;i<lim;++i) r[i]=(r[i>>1]>>1)|((i&1)<<(l-1));
    NTT(F,lim,1),NTT(G,lim,1);
    for (re int i=0;i<lim;++i) F[i]=1ll*F[i]*G[i]%mod;
    NTT(F,lim,-1);
    reverse(F,F+n+1);
    for (re int i=1;i<=n;++i)
        printf("%lld\n",(1ll*n*C(n,i)%mod
                        -1ll*ifac[i]*F[i]%mod+mod)%mod);
    return 0;
}


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

using namespace std;
using ll =long long;
#define SORT(a) sort((a).begin(),(a).end())
#define rSORT(a) reverse((a).begin(),(a).end())
#define For(i, a, b)    for(int i = (a) ; i < (b) ; ++i)
#define rep(i, n)       For(i, 0, n)
#define debug(x)  cerr << #x << " = " << (x) << endl;
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
void coY() {cout <<"Yes"<<endl;}
void coN(){cout <<"No"<<endl;}
const ll INF = 1LL << 60;
const int mod = 1e9+7;
//Write From this Line

int main()
{
	int n , m ;
	cin >> n >> m ;
	vector<int> p(m) ;
	vector<string> s(m);
	rep(i,m) cin >> p[i] >> s[i] ;
	map<int,int> pro;
	int ac = 0 ;
	int wa = 0 ;
	rep(i,m){
		if(s[i] == "AC"){
			if(pro[p[i]] == -1) continue;
			wa += pro[p[i]] ;
			ac ++ ;
			pro[p[i]] = -1 ;//-1にしたらもう正解したってこと
		} else if (s[i] == "WA"){
			if(pro[p[i]] == -1) continue;
			pro[p[i]] ++ ;
		}
	}
	cout << ac << " " << wa << endl;

}


Measured memory_bytes: 10752
#include<bits/stdc++.h>
using namespace std;
#define ll long long

ll gcd(ll x, ll y){
    if(y==0){
        return x;
    }else{
        return gcd(y,x%y);
    }
}



int main(){
    int a,b,k=0;
    cin>>a>>b>>k;
    vector<int> v;
    for(int i=1;i<=min(a,b);i++){
        if(a%i==0&&b%i==0){
            v.push_back(i);
        }
    }
    cout << v[v.size()-k]<<endl;
}





Measured memory_bytes: 256
import java.util.*;
public class Main {
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		// 整数の入力
		
		// スペース区切りの整数の入力
		long a = sc.nextLong();
		long b = 1;
		long c = 2;
		long d = 1;
		long e = 1000000007;
		
		
		for(int i = 0; i < a; i++){
			b = b * 10;
			b = b % e;
			c = c * 9;
			c = c % e;
			d = d * 8;
			d = d % e;
			
		}
		long f = b - c + d;
		if(f < 0){
			System.out.println(b - c + d + e);
          //System.out.println(b);
		}else{
			System.out.println(b - c + d);
           //System.out.println(b);
		} 
		
		
	}
}

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

int A[21];
int B[21];
int C[21];

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

    for (int i = 1; i <= N; ++i) cin >> A[i];
    for (int i = 1; i <= N; ++i) cin >> B[i];
    for (int i = 1; i <= N - 1; ++i) cin >> C[i];

    int ans = 0;
    int prev = N;

    for (int i = 1; i <= N; ++i) {
        int a = A[i];
        ans += B[i];
        ans += a == prev + 1 ? C[prev] : 0;
        prev = a;
    }

    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#pragma GCC optimize("O3")
using namespace std;
#define ll long long 
#define pb push_back
//#define mp make_pair
#define fr first
#define sc second
#define MAX ((ll)(1e17+100))
#define MX ((ll)(4e9+100))
#define ARRS ((ll)(1e6+100))
#define ARS ((ll)(1e3+100))
#define HS ((ll)(233))
#define MOD ((ll)(998244353))
#define EP ((double)(1e-9))
#define PI ((double)3.141592653)
#define LG 21
using namespace std;

ll n,m;
ll a[ARRS];
ll b[ARRS];
ll f[ARRS];
string s;
vector<ll> v[ARRS];

int main(){
	ll pas=MAX;
	
	cin>>n;
	for(int a=1; a<n; a++){
		ll s=0;
		ll k=a;
		while(k){
			s+=k%10;
			k/=10;
		}
		k=n-a;
		while(k){
			s+=k%10;
			k/=10;
		}
		pas=min(pas,s);
	}
	cout<<pas;

}


Measured memory_bytes: 24832
#include <bits/stdc++.h>
using namespace std;
int main(){
    int n;
    cin >> n;
    for(float i=0;i<=50000;i++){
        if(n==int(i*1.08)){
            cout<<i<<endl;
            break;
        }
        if(i==50000||n<int(i*1.08)){
            cout << ":(" <<endl;
            break;
        }
    }
    return 0;
}

Measured memory_bytes: 3784
#include <algorithm>
#include <cmath>
#include <deque>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <set>
#include <stack>
#include <string>
#include <vector>

using namespace std;
using LLONG = long long;
const LLONG MOD = 1000000007;

int main()
{
    int N, u, v; cin >> N >> u >> v; --u; --v;
    vector<vector<int>> adList(N);
    for (int i = 0; i < N - 1; ++i)
    {
        int v1, v2; cin >> v1 >> v2; --v1; --v2;
        adList[v1].push_back(v2);
        adList[v2].push_back(v1);
    }
    // 青木君の開始位置から各頂点までの距離を計算
    const int INF = 1e6;
    vector<int> aDists(N, INF);
    aDists[v] = 0;
    deque<int> Q{ v };
    while (!Q.empty())
    {
        int t = Q.front(); Q.pop_front();
        for (const int n : adList[t])
        {
            if (aDists[n] > aDists[t] + 1)
            {
                Q.push_back(n);
                aDists[n] = aDists[t] + 1;
            }
        }
    }
    // 高橋君について，青木君より先に到達可能な頂点のうち
    // 最も遠くにある頂点を探す
    vector<int> tDists(N, INF);
    vector<bool> movableFlags(N, false);
    tDists[u] = 0;
    movableFlags[u] = true;
    Q.push_back(u);
    while (!Q.empty())
    {
        int t = Q.front(); Q.pop_front();
        for (const int n : adList[t])
        {
            int dist = tDists[t] + 1;
            // 高橋君の方が先に動くので，等距離の点にも移動できる
            if (tDists[n] > dist && aDists[n] >= dist)
            {
                Q.push_back(n);
                tDists[n] = dist;
                movableFlags[n] = true;
            }
        }
    }
    int ans = -1;
    for (int i = 0; i < N; ++i)
    {
        // 高橋君が移動可能な頂点のうち青木君から見て最も遠い頂点をｘとすると
        // ｘは袋小路であり，その一歩手前のｘで高橋君を捕まえることができる
        if (movableFlags[i])
        {
            ans = max(ans, aDists[i] - 1);
        }
    }
    cout << ans << endl;
}

Measured memory_bytes: 6656
#include <bits/stdc++.h>
using namespace std;
char a[10010];
bool c, f;
int main() {
    scanf("%s", a);
    for(int i=0; i<strlen(a); i++) {
        if(a[i]=='C') c=true;
        if(a[i]=='F'&&c==true) f=true; 
    }
    if(f==true) printf("Yes\n"); 
    else printf("No\n"); 
    return 0;
}

Measured memory_bytes: 256
const fun = (n) => {
    return Math.floor(n * (n - 1) / 2)
}

const main = (N,S) => {
    var count = {} 
    for(var i = 0;i<=N;i++) {
      	var tmp = S[i].sort().join('')
        if(tmp in count) {
            count[tmp]+=1
        }else{
            count[tmp] = 1
        }
    }
    var result = 0
  	for(item in  count) {
        result+=fun(count[item])
      }
    return result
}

const input = require('fs').readFileSync('/dev/stdin','utf8').split("\n")
const N = Number(input[0])
const S = input.slice(1).map(x => Array.from(x))
console.log(main(N,S))

Measured memory_bytes: 73352
#include<iostream>
using namespace std;
int main (void)
{
	long N;
	cin >> N;
	long long Ccases = 0;
	for (long B=1; B < N; B++)
	{
		if (N % B == 0)
			Ccases += (N / B) - 1;
		else
			Ccases += (N / B);
	}
	cout << Ccases << endl;
	return 0;
}

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

int main(){
    int k, q;
    int64_t d[5000], sum[5001];
    cin >> k >> q;
    for(int i=0;i<k;++i) cin >> d[i];
    while(q--){
        int64_t n, x, m;
        cin >> n >> x >> m;
        sum[0] = 0;
        for(int i=1;i<=k;++i) sum[i] = sum[i-1] + (d[i-1] + m - 1) % m + 1;
        int64_t ans = (n - 1) - (x % m + sum[k] * ((n - 1) / k) + sum[(n - 1) % k]) / m;
        cout << ans << endl;
    }
    return 0;
}

Measured memory_bytes: 384
#include<bits/stdc++.h>
using namespace std;
int p[100010],f[100010];
#define N 100000
int main(){
p[0]=p[1]=1;
for(int i=2;i*i<=N;i++){
for(int j=i*i;j<N;j+=i){
if(!p[j])p[j]=1;
}
}
for(int i=2;i<N;i++){
if(!p[i]&&!p[(i+1)/2]){
f[i]=f[i-1]+1;
}
else f[i]=f[i-1];
}
int n;
cin>>n;
while(n--){
int l,r;
cin>>l>>r;
cout<<f[r]-f[l-1]<<endl;

}
return 0;
}

Measured memory_bytes: 1408
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;


int main()
{
	int a,b,c,n,m,ans,sum;
	cin>>a>>b>>c>>n>>m;
	ans=a*n+b*m;
	sum=a*n+b*m;
	for(int i=1;i<=max(n,m);i++)
	{
		if(i<=min(n,m))ans=min(ans,sum-a*i-b*i+2*c*i);
		else if(n>=m)ans=min(ans,sum-a*i-b*m+2*c*i);
		else ans=min(ans,sum-a*n-b*i+2*c*i);
	}
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 256
#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N=2e5+10;
const ll INF_ll=4611686018427387903;
int n,m,now;ll tag[N<<2],seg[N<<2];
struct Interval{int l,r,x;bool operator <(const Interval&e)const{return r<e.r;}}a[N];
inline void pushdown(int o,int L,int R){
	if(tag[o]){
		int lc=o<<1,rc=(o<<1)+1;
		tag[lc]+=tag[o];tag[rc]+=tag[o];
		seg[lc]+=tag[o];seg[rc]+=tag[o];
		tag[o]=0;
	}
}
inline void update(int o,int L,int R,int l,int r,ll x){
	if(l<=L&&R<=r){tag[o]+=x;seg[o]+=x;return;}
	int M=(L+R)>>1,lc=o<<1,rc=(o<<1)+1;
	pushdown(o,L,R);
	if(l<=M)update(lc,L,M,l,r,x);
	if(r>M)update(rc,M+1,R,l,r,x);
	seg[o]=max(seg[lc],seg[rc]);
}
inline ll query(int o,int L,int R,int l,int r){
	if(l<=L&&R<=r)return seg[o];
	int M=(L+R)>>1,lc=o<<1,rc=(o<<1)+1;ll sum=-INF_ll;
	pushdown(o,L,R);
	if(l<=M)sum=max(sum,query(lc,L,M,l,r));
	if(r>M)sum=max(sum,query(rc,M+1,R,l,r));
	return sum;
}
int main(){
	scanf("%d%d",&n,&m);
	for(register int i=1;i<=m;i++)
		scanf("%d%d%d",&a[i].l,&a[i].r,&a[i].x);
	sort(a+1,a+m+1);now=1;
	for(register int i=1;i<=n;i++){
		update(1,1,n,i,i,query(1,1,n,1,i));
		while(a[now].r==i&&now<=m)update(1,1,n,a[now].l,a[now].r,a[now].x),now++;
	}
	printf("%lld\n",max(0ll,seg[1]));
	return 0;
}

Measured memory_bytes: 14592
#include <iostream>
#include <string>
#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <bitset>
#include<vector>
#include<utility>
#include<fstream>
#include<queue>
#include <iomanip>
#include<numeric>
#include<set>
#include<map>
#include<functional>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> l_l;
typedef pair<int, int> i_i;
typedef unsigned long long ull;
#define rep(i,n) for(int i=0;i<n;i++)
char ca;
const int MOD = 1000000007;
ll  c, d = 0, e, i,n, j, k, h, w, o, a[300005], b[10000] = {};
queue<ll> q;
string s;
pair<ll, ll> p[20][20];
vector<ll> v;
const int MAX = 2005;
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 >> n;
	ll ma = 0;
	rep(i, n) {
		cin >> a[i];
		ma = max(a[i], ma);
	}
	rep(i, n) {
		rep(j, 60) {
			if (a[i] & 1 )b[j]++;
			a[i] = (a[i] >> 1);
			if (a[i] == 0)break;
		}
	}
	c = 1;
	rep(i, 60) {
		c = (c * 2) % MOD;
			if (i == 0)c = 1;
		k = (b[i] * (n - b[i])) % MOD;
		d = (d + c * k) % MOD;
	//	cout << b[i] << " " << c << " " << d << "\n";
	}

	cout << d;
	return 0;
}

Measured memory_bytes: 2560
#!/usr/bin/env python3
import sys


def solve(A: int, B: int, C: int, K: int):
    ans = 0
    ans += min(A, K)
    if K >= A + B:
        ans += min(K - (A + B), C) * -1
    print(ans)
    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    A = int(next(tokens))  # type: int
    B = int(next(tokens))  # type: int
    C = int(next(tokens))  # type: int
    K = int(next(tokens))  # type: int
    solve(A, B, C, K)

if __name__ == '__main__':
    main()


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

int main() {
    int n;
    cin >> n;
    vector<int> x(n), y(n);
    rep(i,n) cin >> x[i] >> y[i];
    auto dist = [&](int i, int j) {
        double dx = x[i] - x[j];
        double dy = y[i] - y[j];
        return sqrt(dx*dx + dy*dy);
    };
    vector<int> p(n);
    rep(i,n) p[i] = i;
    double len = 0;
    int cnt = 0;
    do {
        rep(i,n-1) {
            len += dist(p[i], p[i+1]);
        }
        cnt++;
    } while (next_permutation(p.begin(), p.end()));
    double ans = len/cnt;
    printf("%.10f\n", ans);
    return 0;
}

Measured memory_bytes: 3796
//abc133_a.cpp
//Sun Jul  7 20:47:38 2019

#include <iostream>
#include <string>
#include <queue>
#include <map>
#include <unordered_map>
#include <vector>
#include <algorithm>
#include <math.h>
#include <set>
#define INTINF 2147483647
#define LLINF 9223372036854775807
using namespace std;
using ll=long long;
typedef pair<int,int> P;

int main(){
	int n,a,b;
	cin >> n >> a >> b;

	if (n*a>b){
		cout << b << endl;
	}else {
		cout << n*a << endl;
	}
}

Measured memory_bytes: 256
//kruskal tree
#include <vector>
#include <algorithm>
#include <cmath>
#include <cstdio>
using namespace std;
#define M 9999
int parent[M],a[M],b[M];
pair<double,int>node[M];
int root(int a){return parent[a]==a?a:parent[a]=root(parent[a]);}
int unite(int a,int b){
	int x=root(a),y=root(b);
	if(x==y)return 0;
	parent[x]=y;
	return 1;
}
int main(){
	int i,j,k,m,n,q;
	double x,y,z,r,t;
	for(;scanf("%d",&n),n;){
		vector<vector<double> >v(n);
		for(q=m=i=0;i<n;i++){
			scanf("%lf%lf%lf%lf",&x,&y,&z,&r);
			v[i].push_back(x),v[i].push_back(y),v[i].push_back(z),v[i].push_back(r),parent[i]=i;
			for(j=0;j<i;j++){
				for(x=k=0;k<3;k++)x+=(t=v[i][k]-v[j][k])*t;
				x=sqrt(x)-v[i][3]-v[j][3];
				if(x<=0){if(unite(i,j))q++;}
				else a[m]=i,b[m]=j,node[m].first=x,node[m++].second=m;
			}
		}
		sort(node,node+m);
		for(x=i=0;i<m&&q<n-1;i++)if(unite(a[node[i].second],b[node[i].second]))x+=node[i].first,q++;
		printf("%.3f\n",x);
	}
}

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

int main(){
  int N; cin >> N;
  set<tuple<int,int,int>> e;
  for(int i=0; i<N-1; i++){
    int a,b; cin >> a >> b;
    e.insert(make_tuple(a,b,i));
    e.insert(make_tuple(b,a,i));
  }
  
  // 頂点1から始める
  // 1につないでいる辺に1から振る
  // 振った辺の先の頂点でそれぞれ1から振る（ただし元の数字は飛ばす）
  // 振った中でmaxが最小
  int maxcolor=0;
  vector<int> ecolor(N-1,0);
  queue<pair<int,int>> q; // 頂点/色
  q.push(make_pair(1,0));
  while(!e.empty()){
    pair<int,int> v=q.front(); q.pop();
    int currentcolor=0;
    auto itr=e.lower_bound(make_tuple(v.first,0,0));
    while(get<0>(*itr)==v.first){
      currentcolor++;
      if(currentcolor==v.second) currentcolor++;
      if(maxcolor<currentcolor) maxcolor=currentcolor;
      ecolor[get<2>(*itr)]=currentcolor;
      q.push(make_pair(get<1>(*itr),currentcolor));
      e.erase(e.find(make_tuple(get<1>(*itr),get<0>(*itr),get<2>(*itr))));
      itr=e.erase(itr);
    }
  }
  cout << maxcolor << endl;
  for(int i=0; i<N-1; i++) cout << ecolor[i] << endl;
}

Measured memory_bytes: 13440
import java.util.*;
import java.util.Scanner;
import java.io.*;
import java.io.BufferedReader; 
import java.io.IOException; 
import java.io.InputStreamReader; 
import java.util.Scanner; 
import java.util.StringTokenizer;

import javax.lang.model.util.ElementScanner6; 

public class Main
{
    static class FastReader
    { 
        BufferedReader br; 
        StringTokenizer st; 

        public FastReader() 
        { 
            br = new BufferedReader(new
                    InputStreamReader(System.in)); 
        } 

        String next() 
        { 
            while (st == null || !st.hasMoreElements()) 
            { 
                try
                { 
                    st = new StringTokenizer(br.readLine()); 
                } 
                catch (IOException  e) 
                { 
                    e.printStackTrace(); 
                } 
            } 
            return st.nextToken(); 
        } 

        int nextInt() 
        { 
            return Integer.parseInt(next()); 
        } 

        long nextLong() 
        { 
            return Long.parseLong(next()); 
        } 

        double nextDouble() 
        { 
            return Double.parseDouble(next()); 
        } 

        String nextLine() 
        { 
            String str = ""; 
            try
            { 
                str = br.readLine(); 
            } 
            catch (IOException e) 
            { 
                e.printStackTrace(); 
            } 
            return str; 
        } 
    } 
    
    

    public static void main(String args[])
    {  
        FastReader in=new FastReader();
        int t=1;
        //t=in.nextInt();
        while(t-->0)
        {
 
            long x=(long)Math.abs(in.nextLong());
            long k=in.nextLong();
            long d=in.nextLong();

            long zeroth=x/d;
      

            if(zeroth>=k)
            {
                x=x-k*d;
                System.out.println(x);
            }

            else
            {
                x-=(zeroth*d);
                k-=zeroth;
                
                if(k%2==0)
                {
                  
                    System.out.println(x);
                }
                else
                {
                    x=(long)Math.abs(x-d);
                    System.out.println(x);
                }

            }
            
           
        }
    }
}


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

int main() {
  int m;
  cin >> m;
  
  if(m>=1800)
    cout << 1;
  else if(m>=1600)
    cout << 2;
  else if(m>=1400)
    cout << 3;
  else if(m>=1200)
    cout << 4;
  else if(m>=1000)
    cout << 5;
  else if(m>=800)
    cout << 6;
  else if(m>=600)
    cout << 7;
  else if(m>=400)
    cout << 8;
  
  return 0;
}

Measured memory_bytes: 3628
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
int main(){
  int n, m;
  while(cin >> n >> m, n||m){
    int k = 0, a = n;
    queue<int> players;
    for(int i = 0; i < n; ++i) players.push(i+1);
    for(int i = 1; i <= m; ++i){
      string s, t;
      cin >> s;
      if(i%3 == 0) t += "Fizz";
      if(i%5 == 0) t += "Buzz";
      if(i%3 && i%5) t = to_string(i);
      if(s == t){
        int p = players.front();
        players.pop();
        players.push(p);
      }else{
        if(players.size() > 1){
          players.pop();
        }
      }
    }
    vector<int> ans;
    while(!players.empty()){
      ans.push_back(players.front());
      players.pop();
    }
    sort(ans.begin(), ans.end());
    cout << ans[0];
    for(int i = 1; i < ans.size(); ++i) cout << " " << ans[i];
    cout << endl;
  }
  return 0;
}



Measured memory_bytes: 3272
a, b, x = list(map(int,input().split()))
if x <= a*a*b/2:
    t = float(a*b*b/(2*x))
else:
    t = float(2*b/a) - float(2*x/(a**3))
import math
ans = math.degrees(math.atan(t))
print(ans)

Measured memory_bytes: 38256
use std::io::*;
use std::str::FromStr;
 
fn read<T: FromStr>() -> Option<T> {
    let stdin = stdin();
    let s = stdin
        .bytes()
        .map(|c| c.unwrap() as char)
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .collect::<String>();
    s.parse::<T>().ok()
}
 
fn main() {
    let n: usize = read().unwrap();
    let mut a: Vec<i64> = Vec::with_capacity(n);
 
    for _i in 0..n {
        let x: i64 = read().unwrap();
        a.push(x);
    }

    
    let mut counters: Vec<i64> = Vec::with_capacity(n);
    for p in a.iter() {
        let mut x: i64 = *p;
        let mut counter: i64 = 0;
        while x % 2 == 0 {
            x = x / 2;
            counter += 1;
        }
        counters.push(counter);
    }
    let min = counters.iter().min().unwrap();
    println!("{}", min);
}


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

int main()
{
    int n;  cin >> n;
    int a[n];
    rep(i,n)  cin >> a[i];

    int t = a[0] - 1;
    int ans = 0;

    rep(i,n) {
        if (t == 1) {
            ans++;
            cout << ans << endl;
            break;
        }
        ans++;
        t = a[t] - 1;
        if (i == n-1)  cout << -1 << endl;
    }
}

Measured memory_bytes: 640
def runlength(S):
    A = []
    tmp = S[0]
    cnt = 0
    for i in range(len(S)):
        if S[i] == tmp:
            cnt += 1
        else:
            A.append(cnt)
            tmp = S[i]
            cnt = 1
    else:
        A.append(cnt)
    return A

def main():
    X = input()
    Y = runlength(X)
    if X[0] == 'T':
        Y = [0] + Y
    
    if X[-1] == 'S':
        Y += [0]

    ans = len(X)
    amari = 0
    for i in range(0,len(Y),2):
        ans -= 2 * min(amari + Y[i], Y[i+1])
        amari = max(0, amari + Y[i] - Y[i+1])

    print(ans)


if __name__ == "__main__":
    main()

Measured memory_bytes: 10108
#include <bits/stdc++.h>
using namespace std;
using lint = long long;
using VI = vector<int>;
using VVI = vector<VI>;

int main() {
  cin.tie(0); ios::sync_with_stdio(false);
  int n; cin >> n;
  VI a(n); for (int i = 0; i < n; i++) cin >> a[i];
  cout << accumulate(a.begin(), a.end(), 0) - n << '\n';
  return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <iomanip>
#include <vector>
#include <queue>
#include <set>
#include <map>

using namespace std;
typedef long long ll;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout << setprecision(10) << fixed;
    int a, b, c, d;
    cin >> a >> b >> c >> d;
    while(true){
        c -= b;
        if(c <= 0){
            cout << "Yes" << endl;
            return 0;
        }
        a -= d;
        if(a <= 0){
            cout << "No" << endl;
            return 0;
        }
    }
}

Measured memory_bytes: 3608
#include <iostream>
#include <string>
using namespace std;

struct dice{
  double _1,_2,_3,_4,_5,_6;
};

int main(){
  
  dice d;
  int sus,i;
  string dir;
 
  cin>>d._1>>d._2>>d._3>>d._4>>d._5>>d._6;
  cin>>dir;
  
  for(i=0; i<dir.size(); i++){
    
    switch(dir[i]){
    case 'N':
      sus=d._1;
      d._1=d._2;
      d._2=d._6;
      d._6=d._5;
      d._5=sus;
      break;
    case 'E':
      sus=d._1;
      d._1=d._4;
      d._4=d._6;
      d._6=d._3;
      d._3=sus;
      break;
    case 'W':
      sus=d._1;
      d._1=d._3;
      d._3=d._6;
      d._6=d._4;
      d._4=sus;
      break;
    case 'S':
      sus=d._1;
      d._1=d._5;
      d._5=d._6;
      d._6=d._2;
      d._2=sus;
      break;
    }

  }

  cout<<d._1<<endl;

}

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

using ll = long long;

const int INF = 1001001001;
const ll INF_LL = 1001001001001001001LL;

int main(void){
  int n,m; cin >> n >> m;
  vector<int> k(n);
  vector<vector<int>> a(n);
  rep(i,n){
    cin >> k[i];
    rep(j,k[i]){
      int in; cin >> in;
      a[i].push_back(in);
    }
  }

  int ans = 0;  
  rep(j,k[0]){
    int tmp = a[0][j];
    int num=0;
    for(int i = 1;i<n;i++){
      rep(h,k[i]){
	if(tmp==a[i][h]){
	  num++;
	  break;
	}
      }
    }
    if(num==n-1) ans++;
  }

  cout << ans << endl;
  
  return 0;
}


Measured memory_bytes: 3616
mod = 10**9+7
n = int(input())
a = [list(map(int, input().split())) for i in range(n)]
dp = [0]*(1 << n)
dp[0] = 1
for i in range(1, 1 << n):
    k = bin(i).count("1")
    for j in range(n):
        if i >> j & 1 and a[k-1][j]:
            dp[i] += dp[i ^ (1 << j)]
    dp[i] %= mod
print(dp[(1 << n)-1])


Measured memory_bytes: 57580