akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <utility>
#include <vector>
#include <cmath>

using namespace std;

int main ()
{
	int h, w, d, a, l, r, q;
	vector<long long> sum[90010];
	cin>>h>>w>>d;
	pair<int, int> pla[90010];
	for (int i=1; i<=h; i++)
	{
		for (int j=1; j<=w; j++)
		{
			cin>>a;
			pla[a].first=i;
			pla[a].second=j;
		}
	}
	for (int i=1; i<=d; i++)
	{
		for (int j=i; j<=h*w; j+=d)
		{
			if (j==i) sum[i].push_back(0LL);
			else sum[i].push_back((long long)sum[i][(j-i)/d-1]+abs(pla[j].first-pla[j-d].first)+abs(pla[j].second-pla[j-d].second));
		}
	}
	cin>>q;
	for (int i=0; i<q; i++)
	{
		cin>>l>>r;
		if (l%d!=0) cout<<sum[l%d][(r-l%d)/d]-sum[r%d][(l-l%d)/d]<<endl;
		else cout<<sum[d][(r-d)/d]-sum[d][(l-d)/d]<<endl;
	}
		
}


Measured memory_bytes: 6016
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce
import pprint
sys.setrecursionlimit(10 ** 9)


INF = 10 ** 13
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007


n = I()

ans = 0
for j in range(1, int(n ** 0.5) + 1):
    if not (n - j) % j and (n - j) // j > j:
        ans += (n - j) // j


print(ans)

Measured memory_bytes: 41068
// include
// ------------------------------------------------
#include <bits/stdc++.h>
#include <vector>
#include <algorithm>
#include <math.h>

using namespace std;

// func
// ------------------------------------------------
int CalcSumOfDigit(int n);      // 各桁の和を計算する。

// define
// ------------------------------------------------
#define all(a)        (a).begin(),(a).end()
#define rall(a)       (a).rbegin(),(a).rend()
#define pb            push_back
#define sz(a)         int((a).size())
#define rep(i,n)      for(int(i)=0;(i)<(n);(i)++)
#define repe(i,n)     for(int(i)=0;(i)<=(n);(i)++)
#define vsort(v)      sort((v).begin(),(v).end())
#define rvsort(v)     sort(rall((v)))
#define vi            vector<int>

const int INF = 1e9;

// code
// ------------------------------------------------
int main() {

  char c;
  cin >> c ;

  string s = "aeiou";

  bool b = false;
  rep(i,5)
  {
    if(s[i] == c)
      
      {
          b = true;
          break;
      }
  }

  if(b) cout << "vowel";
  else cout << "consonant";

  return 0;
}

// funcの実体
// ------------------------------------------------
int CalcSumOfDigit(int n)
{
  int s = 0;
  while(n)
  {
    s += n % 10;
    n = n / 10;
  }
  return s;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(void){
	int n,m;
	int box[50];
	int sum;
	cin>>n>>m;
	for(int i=0;i<n;i++)	cin>>box[i];
	sort(box,box+n,greater<int>());
	sum=0;
	for(int i=0;i<m;i++)	sum+=box[i];
	cout<<sum<<endl;
	return 0;
}

Measured memory_bytes: 256
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <vector>
#include <map>
#include <unordered_map>
#include <cmath>

using namespace std;
typedef long long ll;
#define INF int(1e9)
#define REP(i, n) for(int i = 0; i < (int)(n); i++)
#define REPR(i, n) for(int i = n - 1; i >= 0; i--)
#define REPONE(i, n) for(int i = 1; i <= (int)(n); i++)
#define EACH(i, mp) for(auto i:mp)
#define FOR(i, m, n) for(int i = m;i < n;i++)


int N;

bool is_prime(int p) {
    if (p == 1) return false;
    FOR(i, 2, p) if (p % i == 0)return false;
    return true;
}

void solve() {
    vector<int> primes;
    FOR(i, 2, 55555) {
        if (is_prime(i)) primes.push_back(i);
    }
    int count = 0;
    EACH(p, primes) {
        if (p % 5 == 1) {
            count++;
            cout << p << ' ';
        }
        if (count == N) break;
    }
}

int main() {
    cin >> N;
    solve();
    return 0;
}


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

int compstr(string a, string b) {
  int cnt=0;
  for (char c='a'; c<='z'; c++) {
    bool flg_a=false, flg_b=false;
    for (int i=0; i<a.size(); i++) {
      if (c == a[i]) flg_a=true;
    }
    for (int i=0; i<b.size(); i++) {
      if (c == b[i]) flg_b=true;
    }
    if (flg_a && flg_b) cnt++;
  }
  return cnt;
}

int main() {
  int N,ans=0;
  string S;
  cin >> N >> S;

  for (int i=1; i<N; i++) {
    string a=S.substr(0,i);
    string b=S.substr(i,N-i);
    ans = max(ans,compstr(a,b));
  }

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

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define mp make_pair
#define pb push_back
#define lb lower_bound
#define up upper_bound
#define vll vector<ll>
#define G vector<vll >
#define F first
#define S second
#define pll pair<ll,ll>
#define RFOR(i,a,b) for(int i=a;i>=b;i--)
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define endl '\n'
#define clr(a) memset(a,0,sizeof(a))
#define all(x) x.begin(),x.end()
#define rll read_ll();
#define gc getchar
#define pc putchar


typedef long long ll;

template<class T> inline T lcm(T a,T b){
        return a/gcd(a,b)*b;
}

ll read_ll(){char c=gc();while((c<'0'||c>'9')&&c!='-')c=gc();ll ret=0;int neg=0;if(c=='-')neg=1,c=gc();while(c>='0'&&c<='9'){ret=10*ret+c-48;c=gc();}return neg?-ret:ret;}

int main()
{
	int n;
	cin>>n;
	int a[2][n];
	FOR(i,0,1)
	{
		FOR(j,0,n-1)
		{
			cin>>a[i][j];
		}
	}
	vector<int>prefix(n,0),suffix(n,0);
	FOR(j,0,n-1)
	if(j==0)prefix[j] = a[0][0];
	else prefix[j] = prefix[j-1]+a[0][j];
	RFOR(j,n-1,0)
	if(j==n-1)suffix[j] = a[1][n-1];
	else suffix[j] = suffix[j+1]+a[1][j];
	int ans = 0;
	FOR(i,0,n-1)
	ans = max(ans,prefix[i]+suffix[i]);//cout<<prefix[i]<<" "<<suffix[i]<<endl;
	cout<<ans;
	
	return 0;
}

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


int main() {
    int a,b,c;
    cin >> a >> b >>c;
    if (a == 5 && b == 5) {
        if (c == 7) cout << "YES" << endl;
        else cout << "NO" << endl;
    }
    else if (a == 5 && b == 7) {
        if (c == 5)cout << "YES" << endl;
        else cout << "NO" << endl;
    }
    else if (a == 7 && b == 5) {
        if (c == 5)cout << "YES" << endl;
        else cout << "NO" << endl;
    }
    else cout << "NO" << endl;
    return 0;
}

Measured memory_bytes: 256
#!/usr/bin/env ruby

require 'set'

class Hash
  def push(key, value)
    self[key] = [] if self[key] == nil
    self[key].push(value)
  end
end

class Array
  def lower_bound(value)
    left = -1;
    right = self.length;
    while left + 1 < right
      mid = left + (right - left) / 2;
      if self[mid] >= value
        right = mid
      else
        left = mid
      end
    end
    right
  end

  def unique
    res = [self.first]
    each_cons(2) do |a, b|
      if a != b
        res.push(b)
      end
    end
    res
  end
end

def get_ints
  gets.chomp.split.map(&:to_i)
end

def get_ints_minus_one
  get_ints.map { |x| x - 1 }
end

def get_int
  gets.chomp.to_i
end

N, Q = get_ints
S = gets.chomp


count = 0
ruiseki = [0]
S.split('').each_cons(2).with_index do |(a, b), i|
  if a + b == 'AC'
    count += 1
  end
  ruiseki.push(count)
end

Q.times do
  l, r = get_ints_minus_one
  puts ruiseki[r] - ruiseki[l]
end


Measured memory_bytes: 23732
sx,sy,tx,ty=map(int,input().split())

ans=""
for i in range(ty-sy):
    ans+="U"

for i in range(tx-sx+1):
    ans+="R"

for i in range(ty-sy+1):
    ans+="D"

for i in range(tx-sx+1):
    ans+="L"
ans+="UL"

for i in range(ty-sy+1):
    ans+="U"

for i in range(tx-sx+1):
    ans+="R"

for i in range(ty-sy+1):
    ans+="D"

for i in range(tx-sx):
    ans+="L"

print(ans)

Measured memory_bytes: 9168
#include<bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;++i)
#define rrep(i,n) for(int i=n-1;i>=0;--i)
#define yesno(flg) if(flg){cout<<"YES"<<endl;}else{cout<<"NO"<<endl;}
#define MAX_N 1002
#define i197 1000000007

using namespace std;

typedef long long ll;
typedef pair<ll,ll> P1;
typedef pair<int,int> Pi;
typedef pair<double,Pi> Pdi;
typedef pair<ll,int>Pli;
typedef pair<P1,ll> P2;
const ll INF=1000000000000000001;
struct edge{int to,cost;};
int dy[]={0, 0, 1, -1};
int dx[]={1, -1, 0, 0};
struct Road{double cost;int a,b;};

int main() {

	ll n,q,h,s,d;

	cin>>q>>h>>s>>d;
	cin>>n;

	ll t=0,t2=n;
	ll m=d;

	if(n>1){
		t=d*(n/2);
		t2%=2;
		if(m>=q*8){
			m=q*8;
			t=q*8*(n/2);
			t2%=2;
		}
		if(m>=h*4){
			m=h*4;
			t=h*4*(n/2);
			t2%=2;
		}
		if(m>=s*2){
			m=s*2;
			t=s*2*(n/2);
			t2%=2;
		}
	}
	int r=0;
	if(t2==1){
		r=min(q*4,h*2);
		if(r>s)r=s;
		t+=r;
	}
	cout<<t<<endl;

	return 0;

}


Measured memory_bytes: 256
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int H;
		int W;

		while (true) {
			H = sc.nextInt();
			W = sc.nextInt();

			if (H == 0 && W == 0)
				break;

			printChessboard(H, W);

		}

	}

	static void printChessboard(int H, int W) {
		for (int i = 0; i < H; i++) {
			for (int j = 0; j < W; j++) {
				if((i+j)%2==0)
				System.out.print("#");
				
				else
					System.out.print(".");

				if (j == (W - 1))
					System.out.println("");
			}
		}
		System.out.println();
	}

}

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

int pcnt(int x) {
  return __builtin_popcount(x);
}
int f(int x) {
  if (x == 0) return 0;
  return f(x%pcnt(x))+1;
}

int main() {
  int n;
  cin >> n;
  string s;
  cin >> s;
  vector<int> x(n);
  rep(i,n) x[i] = s[i]-'0';
  int pc = 0;
  rep(i,n) pc += x[i];
  vector<int> ans(n);
  rep(b,2) {
    int npc = pc;
    if (b == 0) npc++; else npc--;
    if (npc <= 0) continue;
    int r0 = 0;
    rep(i,n) {
      r0 = (r0*2)%npc;
      r0 += x[i];
    }
    int k = 1;
    for (int i = n-1; i >= 0; --i) {
      if (x[i] == b) {
        int r = r0;
        if (b == 0) r = (r+k)%npc;
        else r = (r-k+npc)%npc;
        ans[i] = f(r)+1;
      }
      k = (k*2)%npc;
    }
  }

  rep(i,n) cout << ans[i] << endl;
  return 0;
}


Measured memory_bytes: 5220
from math import *
r=pi/180
while 1:
 a,b,c,d=e=map(lambda x: float(x)*r,raw_input().split())
 if e==[-r]*4:break
 print int(round(6378.1*acos((sin(a)*sin(c)+cos(a)*cos(c)*cos(d-b)))))

Measured memory_bytes: 4448
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
#define rep(i,n) for( int i = 0; i < n; i++ )
#define REP(i,s,t) for( int i = s; i < t; i++ )
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define INF 2000000000
#define mod 1000000007
#define INF2 1000000000000000000
#define int long long int

int F[200000];

int Mul(int a, int b){
    return ((a % mod) * (b % mod)) % mod;
}
 
int fact(void){
    F[0] = 1;
    F[1] = 1;
    for( int i = 2; i < 200000; i++){
        F[i] = Mul(i ,F[i-1]);
    }
}
int square(int x){
    return (x * x) % mod;
}
 
int power(int x, int y){
    if( y == 0) return 1;
    else if( y == 1) return x % mod;
    else if( y % 2 == 0) return square(power(x, y/2)) % mod;
    else return square(power(x, y/2)) * x % mod;
}
 
int Div(int a, int b){
    return Mul(a, power(b, mod-2));
}
 
int C(int n, int r){
    if( n < r ) return 0;
    int ret;
    ret = Div(F[n],Mul(F[n-r],F[r])) % mod;
    return ret;
}

signed main(void)
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    fact();
    int H, W, A, B;
    cin >> H >> W >> A >> B;

    int ans = 0;
    REP(i, B+1, W+1) {
        ans += C(H - A + i - 1 - 1, i - 1) * C(A - 1 + W - i, A - 1);
        ans %= mod;
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 1792
k, n = map(int, input().split())
a = list(map(int, input().split()))
l = 0
for i in range(n - 1):
    if l < a[i + 1] - a[i]:
        l = a[i + 1] - a[i]
if l < k - a[n - 1] + a[0]:
    l = k - a[n - 1] + a[0]
print(k - l)

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

int N, A, B;

int main() {
	scanf("%d%d%d", &N, &A, &B);
	if (A > B || (N == 1 && A != B)) printf("0\n");
	else printf("%lld\n", (long long)B * (N - 1) + A - (long long)A * (N - 1) - B + 1);
}


Measured memory_bytes: 256
#include "bits/stdc++.h"
#define PRECISION(x) cout << fixed << setprecision(x)
#define FAST_IO ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define SZ(X) ((int)(X).size())
#define ALL(X) (X).begin(), (X).end()
#define ALLR(X) (X).rbegin(), (X).rend()
#define MP make_pair
#define PB push_back
#define EB emplace_back
#define F first
#define S second

using namespace std;
 
template<class T> bool max_self(T & a, const T & b){ 
  return b > a ? a = b, true : false; 
}
template<class T> bool min_self(T & a, const T & b){ 
  return b < a ? a = b, true : false;    
}
typedef long long LL;
const int INF = 1e9 + 7;
const double PI = acos(-1.0);
const double EPS = (1e-9);

int main(){
  FAST_IO
  int N, cnt[10], diff = 0, extra = 0;
  memset(cnt, 0, sizeof cnt);
  cin >> N;
  for(int rep = 0, x; rep < N; ++rep){
    cin >> x;
    x /= 400;
    if(x > 7) extra++;
    else cnt[x]++;
  }

  for(int rep = 0; rep < 8; ++rep) if(cnt[rep] > 0) diff++;

  cout << (diff ? diff : 1) << " " << diff + extra << '\n';
  return 0;
}


Measured memory_bytes: 3620
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define repr(i, n) for (int i = (int)(n); i >= 0; i--)
#define REP(i, m, n) for (int i = (int)(m); i <= (int)(n); i++)
#define all(v) v.begin(), v.end()
typedef long long ll;

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; }

const long long INF = 1LL << 60;

int main(){
  int n; cin >> n;
  vector<int> a(n);
  map<int, int> mp;
  rep(i, n){
    cin >> a[i];
    mp[a[i]]++;
  }

  ll sum = 0;
  for(pair<int, int> p : mp){
    sum += ((ll)p.second * (ll)(p.second-1)) / 2;
  }

  rep(i, n){
    cout << sum - (ll)(mp[a[i]]-1) << endl;
  }

  return 0;
}


Measured memory_bytes: 8320
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int A,B,C,D;
  cin >> A >> B >> C >> D;
 
  if (A + B > C + D) {
    cout << "Left" << endl;
  }
  else if (A + B == C + D){
    cout << "Balanced" << endl;
  }
  else {
    cout << "Right" << endl;
  }
}

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

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int INF = (1<<30) - 1;
const ll LINF = (1LL<<60) - 1;
const int mod = 1e9 + 7;

map<ll, ll> prime_factor(ll n){
    map<ll, ll> res;
    for (ll i = 2; i * i <= n; ++i) {
        while(n % i == 0){
            res[i]++;
            n /= i;
        }
    }
    if(n != 1) res[n] = 1;
    return res;
}

int main(){
    ll n;
    cin >> n;
    map<ll, ll> mp = prime_factor(n);

    ll res = 0;
    for (auto iter = mp.begin(); iter != mp.end(); ++iter) {
        ll num = iter->second;
        ll tmp = 0;
        while(1){
            if (tmp * (tmp + 1) <= 2 * num && 2 * num < (tmp + 1) * (tmp + 2)){
                res += tmp;
                break;
            }
            tmp++;
        }
    }
    cout << res << endl;
}


Measured memory_bytes: 3628
//#include<bits/stdc++.h>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<map>
#include<queue>
#include<stack>
#include<set>
using namespace std;
#define int long long
#define ll long long
#define str string
#define db double
#define ac() cout<<"Yes"<<endl;
#define wa() cout<<"No"<<endl;
#define ddd cout<<"---debug---"<<endl;
#define ff(a,b) for(signed (a)=1;(a)<=(b);(a)++)
#define fff(a,b) for(signed (a)=0;(a)<(b);(a)++)
#define re readdd()
#define pr(a) printtt(a)
#define pee puts("");
#define eee putchar(' ');
#define pss(a) push_back(a)
#define ps(a) push(a)
int gcd(int a,int b){return b==0?a:gcd(b,a%b);}//
int ppow(int a,int b,int mod){a%=mod;//
int ans=1;while(b){if(b&1)ans=ans*a%mod;
a=a*a%mod;b>>=1;}return ans;}
int readdd(){int x=0,f=1;char c=getchar();//
while(!isdigit(c)&&c!='-')c=getchar();
if(c=='-')f=-1,c=getchar();
while(isdigit(c))x=x*10+c-'0',c=getchar();
return f*x;}
void printtt(int x){if(x<0)putchar('-'),x=-x;
if(x>=10)printtt(x/10);putchar(x%10+'0');}
//
const int maxm=2e5+5;
int a[maxm];
int b[maxm];
int c[maxm];
int d[maxm];
int n;
int ask(int left,int right){//计算d数组中l<=x<r的x的数量
    int st=0,ed=0;
    int l=1,r=n;
    while(l<=r){//st尽量向左扩展
        int mid=(l+r)/2;
        if(d[mid]>=left){
            st=mid;
            r=mid-1;
        }else{
            l=mid+1;
        }
    }
    l=1,r=n;
    while(l<=r){//ed尽量向右扩展
        int mid=(l+r)/2;
        if(d[mid]<right){
            ed=mid;
            l=mid+1;
        }else{
            r=mid-1;
        }
    }
    if(!st||!ed)return 0;
    return ed-st+1;
}
signed main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    for(int i=1;i<=n;i++){
        cin>>b[i];
    }
    int ans=0;
    for(int i=0;i<30;i++){
        int t=(1<<i);
        for(int j=1;j<=n;j++){
            c[j]=a[j]%(t*2);
            d[j]=b[j]%(t*2);
        }
        sort(c+1,c+1+n);
        sort(d+1,d+1+n);
        int cnt=0;
        for(int j=1;j<=n;j++){//枚举c
            cnt+=ask(t-c[j],t*2-c[j]);
            cnt+=ask(t*3-c[j],t*4-c[j]);
            cnt%=2;
        }
        if(cnt){
            ans+=(1<<i);
        }
    }
    cout<<ans<<endl;
    return 0;
}



Measured memory_bytes: 6528
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
const int N=4e5+10;
int to[N],next[N],first[N],ecnt;
int n,rt,ans,tot;
int c[N],vis[N],nes[N],dp[N],d[N];
char temps[N];
void addEdge(int a,int b){
	next[++ecnt]=first[a],first[a]=ecnt,to[ecnt]=b;
}
void readit()
{ 
	scanf("%d",&n);
	for(int a,b,i=1;i<n;i++){
		scanf("%d%d",&a,&b);
		addEdge(a,b);addEdge(b,a);
	}
	scanf("%s",temps+1);
	for(int i=1;i<=n;i++)
		c[i]=temps[i]=='W'?0:1,rt=c[i]?rt:i;
}	

void dfs(int k,int f){
	vis[k]=c[k];
	int pcnt=0;
	for(int i=first[k];i;i=next[i],pcnt++){
		if(to[i]==f) continue;
		dfs(to[i],k);
		if(!vis[to[i]]) d[k]++,d[to[i]]++;
		vis[k]&=vis[to[i]];
	}
}
int f[N],g[N];
void findp(int k,int fa){
	ans+=d[k];
	if((d[k]+c[k])&1) nes[k]=0;
	else ans++,nes[k]=2;
	int mx1=0,mx2=0,fl=0;
	for(int i=first[k];i;i=next[i]){
		if(to[i]==fa||vis[to[i]]) continue;
		fl=1;findp(to[i],k);
		tot=max(tot,f[to[i]]+mx2+nes[k]);
		tot=max(tot,g[to[i]]+mx1+nes[k]);
		mx1=max(mx1,f[to[i]]),mx2=max(mx2,g[to[i]]);
		//if(dp[to[i]]>mx1) mx1=dp[to[i]];
		//else if(dp[to[i]]>mx2) mx2=dp[to[i]];
	}
	f[k]=mx1+nes[k];
	g[k]=fl?mx2+nes[k]:-10000000;
	//dp[k]=1+(nes[k]?1:-1)+mx1;
	//tot=max(tot,dp[k]+mx2);
}
int main()
{
	readit();
	dfs(rt,0);findp(rt,0);
	if(rt)
	printf("%d",ans-tot);
	else 
		printf("0");
	return 0;
}
/*
5
1 2
2 3
3 4
4 5
BBWWB
*/



Measured memory_bytes: 18304
#include <iostream>
#include <string>
typedef long long ll;
using namespace std;
int main() {
    string s;
    int n, x=0, max=0;
    cin >> n >> s;
    for(int i=0; i<s.length(); i++) {
        if(s[i]=='D') {
            x--;
        } else if(s[i]=='I') {
            x++;
            if(max<x) max=x;
        }
    }
    cout << max << endl;
    return 0;
}



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

struct BIT{
  int size;
  ll t[100000];
  void init(int n){
    size=n+5;
    for(int i=0;i<=size;i++)t[i]=0;
  }
  
  ll sum(int i){
    ll res=0;
    while(0<i){
      res+=t[i];
      i-=(i&-i);
    }
    return res;
  }
  ll sum(int a,int b){
    if(a>b)return 0;
    if(a<=1)return sum(b);
    else return sum(b)-sum(a-1);
  }
  void add(int i,ll x){
    while(i<size){
      t[i]+=x;
      i+=(i&-i);
    }
  }
};

ll W,N;
BIT X,DP;

int judge(int l,int r,ll M){
  if(l==r)return -1;
  ll d=X.sum(l,r);
  if(d+(r-l)>W)return 1;
  if(d+(ll)(r-l)*M<W)return -1;
  return 0;
}

bool check(int M){
  DP.init(N+1);
  DP.add(N+1,1);
  int fi=N,se=N;
  for(int i=N;i>=1;i--){
    if(X.sum(i,N)+N-i<=W){
      DP.add(i,1);
      continue;
    }
    while(judge(i,fi-1,M)>=0)fi--;
    while(judge(i,se,M)==1)se--;
    
    if(DP.sum(fi+1,se+1)>0)DP.add(i,1);
  }
  return (DP.sum(1)==1);
}

int main(){
  while(1){
    scanf("%lld %lld",&W,&N);
    if(W==0&&N==0)break;
    X.init(N+5);
    for(int i=1;i<=N;i++){
      ll x;
      scanf("%lld",&x);
      X.add(i,x);
    }
    int L=1,R=W-2,M;
    while(L<R){
      M=(L+R)/2;
      if(check(M))R=M;
      else L=M+1;
    }
    printf("%d\n",L);
  }
  return 0;
}

Measured memory_bytes: 3932
#include<bits/stdc++.h>
#define F first
#define S second
#define pb push_back
#define mp make_pair
#define full(a) a.begin(),a.end()
#define rfull(a) a.rbegin(),a.rend()

using namespace std;
const double pi=acos(-1.0);
const double pii=2*pi;
const double eps=1e-6;
const long long MOD=1e9+7;

void solve(){
    int n;
    cin>>n;
    vector<long long> a(n,0);
    for(int i=0;i<n;i++) cin>>a[i];
    long long ans=0;
    for(int i=1;i<n;i++)
        if(a[i]<a[i-1]){
            ans+=(a[i-1]-a[i]);
            a[i]=a[i-1];
        }
    cout<<ans<<"\n";
}

int main(){
    std::ios::sync_with_stdio(false);
    std::cin.tie(NULL);
    std::cout.tie(NULL);

    solve();
    return 0;
}

Measured memory_bytes: 4748
s=input()
t=input()
ns=len(s)
nt=len(t)
if t in s:
      print(s.replace('?','a'))
      exit()
ans=''
for i in range(ns-nt,-1,-1):
      flg=True
      for j in range(nt):
            if s[i+j]!='?' and s[i+j]!=t[j]:
                  flg=False
      if flg:
            ans=s[:i]+t+s[i+nt:]
            ans=ans.replace('?','a')
            break

print(ans if ans!='' else 'UNRESTORABLE')



Measured memory_bytes: 3064
class FenwickTree:
    def __init__(self, n):
        self.n = n
        self.bit = [0] * (n + 1)
    
    def build(self, lst):
        self.value = lst
        for i, x in enumerate(lst):
            self.add(i + 1, x)
        
    def sum(self, i):
        s = 0
        while i > 0:
            s += self.bit[i]
            i -= i & -i
        return s
    
    def add(self, i, x):
        while i <= self.n:
            self.bit[i] += x
            i += i & -i
    
    def get_sum(self, i, j):
        return self.sum(j) - self.sum(i)
    
N, Q = map(int, input().split())
A = list(map(int, input().split()))

bit = FenwickTree(N)
bit.build(A)

for i in range(Q):
    a, b, c = map(int, input().split())
    if a == 0:
        bit.add(b + 1, c)
    else:
        print(bit.get_sum(b, c))
        

Measured memory_bytes: 132544
#include <stdio.h>
int main(void){
	int p[131072]={0},i,n;
	unsigned long long int m=0;
	scanf("%d",&n);
	for(i=1;i<=n;i++){
		scanf("%d",&p[i]);
	}
	for(i=1;i<=n;i++){
		m = m + (p[i] / 2);
		p[i] = p[i] % 2;
		if(i != n && p[i] >= 1 && p[i + 1] >= 1){
			p[i]--;
			p[i+1]--;
			m++;
		}
	}
	printf("%llu\n",m);
	return 0;
}

Measured memory_bytes: 640
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstdlib>
#include<vector>
#include<string>
#include<sstream>
#include<cmath>
#include<numeric>
#include<map>
#include<stack>
#include<queue>
#include<cassert>
using namespace std;
int inf = 1000000000;


int main(void) {

  int n, m;
  while(cin >> n >> m){
    if( n == 0||m==0 ) break;

    int cnt = 0;
    vector<bool> b(n, true);
    int a = n;
    int pos = 0;
    while(true){
      pos %= n;
      pos++;
      if( !b[pos] ) continue;
      cnt++;
      if( cnt == m ){
        b[pos] = false;
        a--;
        // cerr << pos << endl;
        if( a == 0 ){
          cout << pos << endl;
          break;
        }
        cnt = 0;
      }
    }

  }


  return 0;
}


// EOF

Measured memory_bytes: 3028
n, m = map(int, input().split())
ab = []
for _ in range(n):
    a, b = map(int, input().split())
    ab.append((a,b))

sorted_ab = sorted(ab)
sum = 0
total_cost = 0
for a, b in sorted_ab:
    diff = m - sum
    if diff < b:
        sum += diff
        total_cost += a*diff
        break
    else:
        sum += b
        total_cost += a*b

print(total_cost)

Measured memory_bytes: 17808
h, w = map(int, input().split())
s = ["".join(["_"] * (w + 2))]
s += [("_" + input().strip() + "_") for _ in range(h)]
s += ["".join(["_"] * (w + 2))]
ans = [[""] * w for _ in range(h)]

for i in range(1, (h + 1)):
    for j in range(1, (w + 1)):
        if s[i][j] == "#":
            ans[i - 1][j - 1] = "#"
        else:
            tmp = 0
            if s[i - 1][j - 1] == "#":
                tmp += 1
            if s[i - 1][j] == "#":
                tmp += 1
            if s[i - 1][j + 1] == "#":
                tmp += 1
            if s[i][j - 1] == "#":
                tmp += 1
            if s[i][j + 1] == "#":
                tmp += 1
            if s[i + 1][j - 1] == "#":
                tmp += 1
            if s[i + 1][j] == "#":
                tmp += 1
            if s[i + 1][j + 1] == "#":
                tmp += 1
            ans[i - 1][j - 1] = str(tmp)
for i in range(h):
    print("".join(ans[i]))


Measured memory_bytes: 40044
N=int(input())
H=list(map(int,input().split()))
cnt=0
ans=0

for i in range(1,N):
  if H[i-1]>=H[i]:
    cnt=cnt+1
  else:
    if cnt>ans:
	    ans=cnt
    cnt=0
    
if ans>cnt:
  print(ans)
else:
  print(cnt)
  
  

Measured memory_bytes: 14224
#include "bits/stdc++.h"
#define rep(i,b) for(ll i=0;i<b;i++)
#define ll long long
using namespace std;
#define vl vector<ll>
#define vvl vector<vector<ll>>
#define vvvl vector<vector<vector<ll>>>
#define debug(x) cerr<<#x<<" "<<x<<'\n';
bool cmp(pair<ll,ll> a, pair<ll,ll> b) { return a.second > b.second; }

int main(){
    string s1,s2,s3="";
    cin>>s1>>s1>>s2;
    rep(i,s1.size()){
        s3+=s1.substr(i,1)+s2.substr(i,1);
    }
    cout<<s3<<endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
const int INF = 1e9;
const int MOD = 1e9+7;
const long long LINF = 1e18;
#define dump(x)  cout << 'x' << ' = ' << (x) << ` `;
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define rep(i,n) for(int i=0;i<(n);++i)
#define REPR(i,n) for(int i=n;i>=0;i--)
#define FOREACH(x,a) for(auto& (x) : (a) )
typedef long long ll;
using namespace std;
typedef pair<ll, ll> P;

template<typename T>
void print(const vector<T> &x) {
    int n = x.size();
    rep(i,n) {
        cout << x[i];
        if (i!=n-1) cout<<" ";
        else cout << endl;
    }
}

template<typename T>
void print(const vector<vector<T>> &x) {
    int n = x.size();
    rep(i,n) {
        rep(j,x[i].size()) {
            cout << x[i][j] << " ";
        }
        cout << endl;
    }
}

template<typename T>
void print(const vector<T> &x, int n) {
    rep(i,n) {
        cout << x[i];
        if (i!=n-1) cout<<" ";
        else cout << endl;
    }
}

template<typename T>
void print(const vector<vector<T>> &x, int n, int m) {
    rep(i,n) {
        rep(j,m) {
            cout << x[i][j] << " ";
        }
        cout << endl;
    }
}

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; }

void input_init() {
    cin.tie(0); ios::sync_with_stdio(false);
}

int main(int argc, char const *argv[]) {
    int n,k; cin>>n>>k;
    int m = (n-1)*(n-2)/2;
    if (k>m) {
        cout << -1 << '\n';
        return 0;
    }
    vector<vector<int>> g(n);
    int cnt = 0;
    // init
    for (int i = 1; i < n; ++i) {
        g[0].push_back(i);
        cnt++;
    }


    int del = m-k;

    auto construct = [&]() {
        for (int i = 1; i < n; ++i) {
            for (int j = i+1; j < n; ++j) {
                if (del<=0) return;
                del--;
                g[i].push_back(j);
                cnt++;
            }
        }
    };

    construct();

    cout << cnt << '\n';
    rep(i,n) {
        for (auto &&f: g[i]) {
            cout << i+1 << ' ' << f+1 << '\n';
        }
    }


    return 0;
}

Measured memory_bytes: 256
package main

import "fmt"

func main() {
	var a, b int
	fmt.Scanf("%d %d", &a, &b)

	fmt.Println(logic(a, b))
}

func logic(a, b int) int {
	s := 1
	num := 0

	for s < b {
		s--
		s += a
		num++
	}
	return num
}

Measured memory_bytes: 512
#include <cassert>
#include <cctype>
#include <cerrno>
#include <cfloat>
#include <ciso646>
#include <climits>
#include <clocale>
#include <cmath>
#include <csetjmp>
#include <csignal>
#include <cstdarg>
#include <cstddef>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <cwchar>
#include <cwctype>
#include <ccomplex>
#include <cfenv>
#include <cinttypes>
#include <cstdbool>
#include <cstdint>
#include <ctgmath>
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
#include <array>
#include <atomic>
#include <chrono>
#include <codecvt>
#include <condition_variable>
#include <forward_list>
#include <future>
#include <initializer_list>
#include <mutex>
#include <random>
#include <ratio>
#include <regex>
#include <scoped_allocator>
#include <system_error>
#include <thread>
#include <tuple>
#include <typeindex>
#include <type_traits>
#include <unordered_map>
#include <unordered_set>
using namespace std;
int main() {
    vector<char> v(6);
    for(int i=0;i<6;i++){
    	cin >> v.at(i);
    	}
    	
    if(v.at(2)==v.at(3)&&v.at(4)==v.at(5)){
    	cout<<"Yes"<<endl;
    	}
    else{
    cout  << "No" <<endl;
    	}
       }


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

int main(){
	int N, i, j, k;
	scanf("%d", &N);
	N = (1 << N);
	vector<int> S(N);
	for(i = 0; i < N; i++){
		scanf("%d", &S[i]);
		S[i] *= -1;
	}
	sort(S.begin(), S.end());
	for(i = 1; i < N; i <<= 1){
		sort(S.begin(), S.begin() + i);
		sort(S.begin() + i, S.end());
		for(j = 0, k = i; j < i; swap(S[i + j++], S[k])){
			while(S[j] >= S[k]){
				if(++k == N){
					printf("No\n");
					return 0;
				}
			}
		}
	}
	printf("Yes\n");
	return 0;
}

Measured memory_bytes: 1280
#include <iostream>
#include <vector>
#include <algorithm>
#include <unordered_set>
#include <stack>

using namespace std;

typedef long long int ll;

const ll MOD = 1000000007;

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

  int N, K;
  cin >> N >> K;
  vector<unordered_set<int> > edge;
  for (int i = 0; i < N; i++) edge.push_back(unordered_set<int>());
  for (int i = 0; i < N-1; i++) {
    int a, b;
    cin >> a >> b;
    edge[a-1].insert(b-1); // zero index
    edge[b-1].insert(a-1); // zero index
  }

  if (N == 1) {
    cout << K << endl;
    return 0;
  }

  vector<ll> factorial(1, 1);
  for (ll i = 1; i < 2 * N; i++) factorial.push_back((factorial[i-1] * i) % MOD);
  int root = -1;
  for (int i = 0; i < N; i++) {
    if (edge[i].size() == 1) {
      root = i;
      break;
    }
  }
  ll ans = K;
  bool first = true;
  vector<bool> visited(N, false);
  stack<int> st;
  st.push(root);
  while(!st.empty()) {
    int now = st.top();
    st.pop();
    visited[now] = true;
    ll factor = K-2;
    if (first) {
      factor++;
      first = false;
    }
    for (int x : edge[now]) {
      if (visited[x]) continue;
      ans = (ans * factor) % MOD;
      factor--;
      st.push(x);
    }
  }

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


Measured memory_bytes: 21740
#include<iostream>
#include<string>
#include<cmath>
#include<iomanip>

using namespace std;

int main(){
    int a,b,h,m;
    cin>>a>>b>>h>>m;
    static const double pi = 3.141592653589793;
    double ma,ha;
    ma=m*pi/30.0;
    ha=pi*(h/6.0+m/360.0);
    double c;
    double tmp=ma-ha;
    if(tmp<pi){
        c=a*a+b*b-2*a*b*cos(tmp);
        c=sqrt(c);
    }else if(tmp==pi){
        c=a+b;
    }else{
        tmp=2*pi-tmp;
        c=a*a+b*b-2*a*b*cos(tmp);
        c=sqrt(c);
    }
    cout<<setprecision(10)<<c<<"\n";
    
    return 0;
}

Measured memory_bytes: 4224
import java.util.*;
public class Main{
	
	
	private static Scanner sc=new Scanner(System.in);
	
	public static void main(String []args){
		
		String num=sc.nextLine();
		int reminder=0;
		for(int i=0;i<num.length();i++){
			reminder+=num.charAt(i)-'0';
			if(reminder>=9)
				reminder-=9;
		}
		if(reminder==0)
			System.out.println("Yes");
		else
			System.out.println("No");
	}
	
}

Measured memory_bytes: 41556
#include <iostream>
#include <vector>
#include <cmath>
#include <iomanip>

int main() {
  int N;
  std::cin >> N;
  
  auto pos = std::vector<std::pair<int,int>>();
  auto dist = std::vector<std::vector<double>>(N, std::vector<double>(N, 0.0));
  
  int x, y;
  for (int i=0; i<N; ++i) {
    std::cin >> x >> y;
    pos.emplace_back(x, y);
  }
  for (int i=0; i<N; ++i) {
    for (int j=0; j<N; ++j) {
      if (i == j) continue;
      double distx = pos[i].first - pos[j].first;
      double disty = pos[i].second - pos[j].second;
      double distance = std::sqrt(distx * distx + disty * disty);
      dist[i][j] = distance;
    }
  }
  double sum = 0.0;
  for (int i=0; i<N; ++i) {
    for (int j=0; j<N; ++j) {
      if (i != j) sum += dist[i][j];
    }
  }
  std::cout << std::setprecision(10) << std::fixed << sum / N << std::endl;
}

Measured memory_bytes: 256
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <string.h>
#include <math.h>

#define MOD 1000000007
#define REP(i,n) for ((i)=0;i<(n);i++)
#define SET(a,c) memset(a,c,sizeof a)
#define CLR(a) memset(a,0,sizeof a)
#define MIN(a,b) (a>b?b:a)
#define MAX(a,b) (a>b?a:b)
#define LL long long
#define ULL unsigned long long

int compare_ll(const void *a, const void *b){
	return *(ULL*)b - *(ULL*)a;
}



int main(void) {

	char Sa[101],Sb[101],Sc[101];
	int anum,bnum,cnum,acnt,bcnt,ccnt;
	char now = 'a';
	int flag = 1;

	scanf("%s", &Sa);
	scanf("%s", &Sb);
	scanf("%s", &Sc);

	anum = strlen(Sa);
	bnum = strlen(Sb);
	cnum = strlen(Sc);

	acnt = 0;
	bcnt = 0;
	ccnt = 0;

	while(flag){
		switch(now){
		case 'a':
			now = Sa[acnt];
			acnt++;
			if(anum+1 == acnt){
				printf("A");
				flag = 0;
			}
		break;

		case 'b':
			now = Sb[bcnt];
			bcnt++;
			if(bnum+1 == bcnt){
				printf("B");
				flag = 0;
			}
		break;

		case 'c':
			now = Sc[ccnt];
			ccnt++;
			if(cnum+1 == ccnt){
				printf("C");
				flag = 0;
			}
		break;
		}
	}


	return 0;
}

/* 最後の改行忘れるな！！ */


Measured memory_bytes: 128
#include <stdio.h>

int main(){
        char  line[20], line2[20];
        int   R[200000];
        int   i, n;
    int   min, max = -999999999;

        fgets(line, sizeof(line), stdin);
        sscanf(line, "%d", &n);

        for(i = 0; i < n; i++){
                fgets(line2, sizeof(line2), stdin);
                sscanf(line2, "%d", &R[i]);
        }
        min = R[0];
        for(i = 1; i < n; i++ ){
                if(max < (R[i] - min)) max = R[i] - min;
                if(min > R[i]) min = R[i];
        }

        //if(max < (R[i] - min)) max = R[i] - min;
        printf("%d\n", max);


        return 0;
}

Measured memory_bytes: 1384
N,K=[int(x) for x in input().split()]
Plist=[int(p)+1 for p in input().split()]
tmp=sum(Plist[0:K])
ans=tmp
for i in range(K,N):
    tmp=tmp-Plist[i-K]+Plist[i]
    ans=max(ans, tmp)
print(ans/2)

Measured memory_bytes: 71792
N = int(input())
dp = [float("inf")]*(N + 1)
dp[0] = 0
pull_list_9 = [9**i for i in range(1, 6)]
pull_list_6 = [6**i for i in range(1, 7)]
pull_list = pull_list_9 + pull_list_6 + [1]
p_s = sorted(pull_list)

for i in range(1, N + 1):
  for j in p_s:
    if i - j < 0:
      break
    dp[i] = min(dp[i], dp[i-j] + 1)

print(dp[-1])


Measured memory_bytes: 3828
DIR = {">": (0, 1), "<": (0, -1), "^": (-1, 0), "v": (1, 0)}

while True:
    w, h = map(int, raw_input().split())
    if w == 0 and h == 0:
        break

    m = []
    for i in range(w):
        m.append([c for c in raw_input().strip()])

    x = 0
    y = 0
    while m[x][y] != '.':
        i = m[x][y]
        if i == 'x':
            break
        m[x][y] = 'x'
        x += DIR[i][0]
        y += DIR[i][1]

    if m[x][y] == '.':
        print("{} {}".format(y, x))
    else:
        print("LOOP")

Measured memory_bytes: 4324
#include<stdio.h>

long int mai(long int a, long int b);


int main(void)
{
	long int a,b,yak;
	int i=0,j=0;

	while(scanf("%ld %ld",&a,&b) != EOF)
	{
		yak = mai(a,b);
		printf("%ld %ld\n",yak,a*b/yak);
	}

	return 0;
}

long int mai(long int a, long int b)
{
	if(a>b)
		return mai(a-b,b);
	else if(a<b)
		return mai(b-a,a);
	else
		return a;
}

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

#define MAX_HEAP_LENGTH 100

void swap(int array[], int i, int j) {
    int temp = array[i];
    array[i] = array[j];
    array[j] = temp;
}

typedef struct {
    int * array;
    int heap_size;
    int length;
} Heap;

Heap createHeap(int length) {
    Heap heap;
    
    heap.array = (int *)malloc((length+1) * sizeof(int));
    heap.array[0] = NULL; // NOT USED
    heap.heap_size = heap.length = length;
    
    return heap;
}

int parentOfIndex(int index) {
    return index/2;
}
int leftOfIndex(int index) {
    return 2*index;
}
int rightOfIndex(int index) {
    return 2*index+1;
}

void maxHeapify(Heap heap, int iThis) {
    int iLeft = leftOfIndex(iThis);
    int iRight = rightOfIndex(iThis);
    
    int iLargest = (iLeft <= heap.heap_size && heap.array[iLeft] > heap.array[iThis] ? iLeft : iThis);
    if (iRight <= heap.heap_size && heap.array[iRight] > heap.array[iLargest]) iLargest = iRight;
    
    if (iLargest != iThis) {
        swap(heap.array, iThis, iLargest);
        // iLargest is no longer the index for largest value within the trinode.
        maxHeapify(heap, iLargest);
    }
}
void buildMaxHeap(Heap heap) {
    heap.heap_size = heap.length;
    
    for (int i = heap.length/2; i >= 1; i--)
        maxHeapify(heap, i);
}
void heapSort(Heap heap) {
    buildMaxHeap(heap);
    
    for (int i = heap.length; i >= 2; i--) {
        swap(heap.array, 1, i);
        heap.heap_size--;
        maxHeapify(heap, 1);
    }
}


int main(int argc, char** argv) {
    int nNode;
    scanf("%d", &nNode);
    
    Heap heap = createHeap(nNode);
    // 1-origin
    
    for (int i = 1; i <= nNode; i++)
        scanf("%d", &(heap.array[i]));
    
    
    for (int i = 1; i <= nNode; i++) {
        printf("node %d: ", i);
        printf("key = %d, ", heap.array[i]);
        
        if (i/2 > 0)
            printf("parent key = %d, ", heap.array[i/2]);
        
        if (2*i <= heap.length)
            printf("left key = %d, ", heap.array[2*i]);
        
        if (2*i+1 <= heap.length)
            printf("right key = %d, ", heap.array[2*i+1]);
        
        printf("\n");
    }

    return (EXIT_SUCCESS);
}




Measured memory_bytes: 2040
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#define int long long
using namespace std;

int n, k, s;
int x[2000], y[2000], z[2000];
vector<int> et[2000];
vector<int> ec[2000];

int f(int sid, int dir) {
	int ret = 0;
	bool used[2000] = {false};
	int id = sid;
	
	for (int i = 0; i < k - 1; i++) {
		used[id] = true;
		
		int next = -1;
		
		if (dir == 0) {
			for (int j = 0; j < et[id].size(); j++) {
				if (!used[et[id][j]]) { next = j; break; }
			}
		}
		else {
			for (int j = (int)et[id].size() - 1; j >= 0; j--) {
				if (!used[et[id][j]]) { next = j; break; }
			}
		}
		
		if (next == -1) { return -1; }
		ret += ec[id][next];
		id = et[id][next];
	}
	
	if (k >= 3) {
		for (int j = 0; j < et[id].size(); j++) {
			if (et[id][j] == sid) {
				ret += ec[id][j];
				break;
			}
		}
	}
	
	return ret;
}

signed main() {
	int i, j;
	
	while (cin >> n >> k >> s) {
		if (!n) break;
		for (i = 0; i < n; i++) cin >> x[i] >> y[i] >> z[i];
		
		for (i = 0; i < n; i++) { et[i].clear(); ec[i].clear(); }
		for (i = 0; i < n; i++) {
			for (j = 0; j < n; j++) {
				if (i == j) continue;
				int sx = s - abs(x[i] - x[j]);
				int sy = s - abs(y[i] - y[j]);
				int sz = s - abs(z[i] - z[j]);
				if (sx < 0 || sy < 0 || sz < 0) continue;
				et[i].push_back(j);
				ec[i].push_back(2 * (sx * sy + sy * sz + sz * sx));
			}
		}
		
		int maxi = -1;
		for (i = 0; i < n; i++) {
			maxi = max(maxi, max(f(i, 0), f(i, 1)));
		}
		if (maxi == -1) { cout << -1 << endl; }
		else { cout << k * s * s * 6 - maxi << endl; }
	}
	return 0;
}

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

using namespace std;

#define REP(i,a,b) for(int i=a;i<(int)b;i++)
#define rep(i,n) REP(i,0,n)
#define all(c) (c).begin(), (c).end()
#define zero(a) memset(a, 0, sizeof a)
#define minus(a) memset(a, -1, sizeof a)
#define watch(a) { std::cout << #a << " = " << a << "\n"; }
template<class T1, class T2> inline bool minimize(T1 &a, T2 b) { return b < a && (a = b, 1); }
template<class T1, class T2> inline bool maximize(T1 &a, T2 b) { return a < b && (a = b, 1); }
template<class T, class V> istream& operator>> (istream& ist, pair<T, V>& p) { return ist >> p.first >> p.second; }
template<class T> ostream& operator<< (ostream& ost, pair<T, T>& p) { return ost << p.first << ", " << p.second; }
template<class T> istream& operator>> (istream& ist, vector<T>& vs) { for(auto& e: vs) ist >> e; return ist; }

typedef long long ll;
int const inf = 1<<29;

int N;

struct F {
  double t1, t2, a, b;
};
vector<F> funcs;

double calc_b(double a, double y1, double x1) {
  // y1 = a * x1 + b;
  return y1 - a * x1;
}

void p(double t1, double t2, double a, double b) {
  //printf("%.f %.f %.f %.f\n", t1, t2, a, b);
  funcs.push_back(F{t1, t2, a, b});
}

void make_f_set(vector<double> const& ts, vector<double> const& vs) {
  rep(i, N) {
    if (i) {
      auto b = calc_b(-1, vs[i], ts[i - 1]);
      p(0, ts[i - 1], -1, b);
    }
    if (i < N - 1) {
      auto b = calc_b(+1, vs[i], ts[i]);
      p(ts[i], ts.back(), +1, b);
    }
    {
      auto b = vs[i];
      p(i ? ts[i - 1] : 0, ts[i], 0, b);
    }
  }
  p(0, ts.back(), +1, 0);
  p(0, ts.back(), -1, calc_b(-1, 0, ts.back()));
}

double calc_v(double t) {
  double ret = inf;
  for (auto f: funcs) {
    if (t < f.t1 - 0.001 || f.t2 + 0.001 < t) continue;
    minimize(ret, f.a * t + f.b);
  }
  return ret;
}

int main() {
  cin >> N;
  vector<double> ts(N);
  rep(i, N) {
    cin >> ts[i];
    if (i) ts[i] += ts[i - 1];
  }
  vector<double> vs(N);
  rep(i, N) {
    cin >> vs[i];
  }
  make_f_set(ts, vs);
  double prevv = 0.0;
  double ans = 0.0;
  for (double t = 0.5; t <= ts.back() + 0.001; t += 0.5) {
    double currv = calc_v(t);
    ans += (currv + prevv) / 4.0;
    prevv = currv;
  }
  printf("%.12f\n", ans);
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <algorithm>
#include <cmath>
#include <deque>
#include <queue>
#include <stack>
#include <vector>
#include <utility>
#include <iomanip>
#include <bitset>
#include <set>
#include <map>
#include <stdio.h>
#include <numeric>
#include <cstring>

#define rep(i,n) for (int i = 0; i < (n); i++)
#define rep1(i,n) for (int i = 1; i < (n); i++)
#define FOR(i,a,b) for (int i=(a); i < (b); i++)
#define MOD 1000000007 //10^9+7
using namespace std;
using ll = long long;
using PII = pair<int, int>;
const int INF = numeric_limits<int>::max();

// 負の数にも対応した % 演算
long long mod(long long val, long long m) {
    long long res = val % m;
    if (res < 0) res += m;
    return res;
}

//greatest common divisor
long long gcd(ll a, ll b) 
{
    if (a % b == 0) {
        return b;
    } else {
        return gcd(b, a % b);
    }
}

//least common multiple
long long lcm(ll a, ll b)
{
    return a / gcd(a, b) * b ;
}

int main()
{
    int k; cin >> k;
    int ans = 0;
    for (int a =1; a <= k; a++) {
        for (int b = 1; b <= k; b++) {
            for (int c = 1; c <= k; c++) {
                ans += gcd(a, gcd(b,c));
            }
        }
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 3632
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
using namespace std;
typedef long long ll;
ll MOD = 1e9+7;
#define rep(i,n) for(int i = 0; i < (n); ++i)
int main() {
    int n;
    cin >> n;
    ll ans = 1e18;
    rep(i, n) {
        ll tmp_a;
        cin >> tmp_a;
        ll anum = 0;
        while(1) {
            if ( tmp_a % 2 == 1 ) break;
            ++anum;
            tmp_a /= 2;
        }
        ans = min(ans, anum);
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 256
#include <stdio.h>
#include <cmath>
#include <algorithm>
#include <cfloat>
#include <stack>
#include <queue>
#include <vector>
#include <string>
#include <iostream>
typedef long long int ll;
typedef unsigned long long int ull;
#define BIG_NUM 2000000000
#define MOD 1000000007
#define EPS 0.000000001
using namespace std;

struct Info{
	double vw,pf,vf,th;
};

int N;
double pw;

Info* flower;

//?°´?????????water_amount??§????????¨????????±????????±???????????????????????????????¨????????????¢??°
double calc(double water_amount){
	double ret = water_amount*pw;

	for(int i = 0; i < N; i++){
		ret += max(0.0,flower[i].pf*((flower[i].th-water_amount*flower[i].vw)/flower[i].vf)); //??\??????????????£??§????????¨????????????
	}
	return ret;
}

//????????¢?´¢???????????¢??°(??????????????¢??°???????°????????±???????)
double thirds_search(double left,double right){

	if(fabs(right-left) < EPS){
		return calc((right+left)/2);
	}

	double mid1 = (2.0*left+right)/3.0;
	double mid2 = (1.0*left+2.0*right)/3.0;

	if(calc(mid1) > calc(mid2)){ //??§?????????????????´?????¨??????
		return thirds_search(mid1,right);
	}else{
		return thirds_search(left,mid2);
	}
}

void func(){
	scanf("%lf",&pw);

	for(int i = 0; i < N; i++){
		scanf("%lf %lf %lf %lf",&flower[i].vw,&flower[i].pf,&flower[i].vf,&flower[i].th);
	}

	printf("%.10lf\n",thirds_search(0.0,(double)BIG_NUM)); //?°´?????????0.0??\???
}

int main(){

	flower = (Info*)malloc(sizeof(Info)*100000);

	while(true){
		scanf("%d",&N);
		if(N == 0)break;

		func();
	}

	return 0;
}

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

using namespace std;

struct Initializer {
  Initializer() {
    cin.tie(0);
    ios::sync_with_stdio(0);
    cout << fixed << setprecision(15);
  }
} initializer;

int main() {
  int n, x = 0;
  cin >> n;
  for (int m = n; m; m /= 10) x += m % 10;
  cout << (n % x == 0 ? "Yes" : "No") << endl;
}



Measured memory_bytes: 892
n,q=map(int,input().split())
P=[i for i in range(n)]
def root(x):
  path_to_root = []
  while P[x] != x:
    path_to_root.append(x)
    x = P[x]
  for node in path_to_root:
    P[node] = x
  return x
def same(x,y):
  return root(x) == root(y)
def unite(x,y):
  P[root(x)] = root(y)
for i in range(q):
  t,x,y=map(int,input().split())
  if t==0: unite(x,y)
  else: print('1' if same(x,y) else '0')


Measured memory_bytes: 5976