akhauriyash/Code-Regression huggingface dataset:
import sys
from queue import Queue


def main():
    input = sys.stdin.readline
    N = int(input())
    tree = [[] for _ in range(N)]
    for _ in range(N-1):
        u, v, w = map(int, input().split())
        tree[u-1].append([v-1, w])
        tree[v-1].append([u-1, w])

    color = [None] * N
    v_que = Queue()
    v_que.put(0)
    
    c = True
    c_que = Queue()
    c_que.put(c)

    while not v_que.empty():
        v = v_que.get()
        c = c_que.get()
        if color[v] is not None:
            continue
        color[v] = c
        for e in tree[v]:
            v_que.put(e[0])
            c_que.put(c if e[1] % 2 == 0 else not c)

    for c in color:
        print(int(c))


if __name__ == '__main__':
    main()


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

int main () {
  int N, M, Q;
  cin >> N >> M >> Q;
  vector<vector<int>> x(N, vector<int>(N, 0));

  rep(i,M) {
    int L, R;
    cin >> L >> R;
    L--; R--;
    x[L][R]++;
  }
  vector<vector<int>> c(N+1, vector<int>(N+1, 0));
  rep(i,N) {
    rep(j,N) c[i+1][j+1] = c[i+1][j] + x[i][j];
  }

  rep(k,Q) {
    int p, q;
    cin >> p >> q;
    int ans = 0;
    for(int i = p; i <= q; i++) {
      ans += c[i][q] - c[i][p-1];
    }
    cout << ans << endl;
  }
  return 0;
}


Measured memory_bytes: 2944
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;i++)
#define all(x) (x).begin(),(x).end()
using namespace std;
const int INF=1145141919,MOD=1e9+7;
const long long LINF=8101145141919364364;
// const int dx[]={1,1,0,-1,-1,-1,0,1},dy[]={0,-1,-1,-1,0,1,1,1};

int main(){
    int m; cin>>m;
    while(m--){
        string s; cin>>s;
        int n=s.size();
        map<string,long long> mp;
        for(int i=1;i<n;i++){
            string s11=s.substr(0,i),s12=s11;
            string s21=s.substr(i,n-i),s22=s21;
            reverse(all(s12)); reverse(all(s22));
            mp[s11+s21]++;
            mp[s11+s22]++;
            mp[s12+s21]++;
            mp[s12+s22]++;
            mp[s21+s11]++;
            mp[s21+s12]++;
            mp[s22+s11]++;
            mp[s22+s12]++;
        }
        int ans=0;
        for(auto i:mp) ans++;
        cout<<ans<<endl;
    }
    return 0;
}



Measured memory_bytes: 3068
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
typedef  long long ll;
typedef  vector<int> vi;
typedef  pair<int,int> pii;
typedef  pair<int,string> pis;
double   pi=3.1415926535898;
#define speed      ios::sync_with_stdio(false);cin.tie(NULL); cout.tie(NULL);
#define ff(i,a,b)  for(int i=a;i<=int(b);++i)
#define fr(i,a,b)  for(int i=a;i>=int(b);i--)
#define ms(x,a)    memset(x,a,sizeof(x))
#define all(x)     (x).begin(),(x).end()
#define sz(x)      int(x.size())
#define pb         push_back
#define r0         return 0;
#define CC         continue;
#define bb(x)      cerr<< x <<endl;
#define F          first
#define S          second       //  __builtin_popcount;
//freopen("input.txt","r",stdin),freopen("output.txt","w",stdout);
const ll M  = 1e9+7 ;
//const int N = 111;
const int inf = 1<<30;
const double EPS = 1e-9;
//////////////////////    Hi    ^_^  hack me if you can :P
string ys = "YES\n";
string no = "NO\n" ;

int n;
ll a[200];
ll LCM(ll x, ll y)
{
    return x/__gcd(x,y)*y;
}
int main()
{
    speed;
    cin >> n;
    ff(i,1,n) cin >> a[i];
    if (n == 1)
    {
        cout << a[1] ;
        return 0;
    }
    ll l = LCM(a[1],a[2]);

    ff(i,3,n)
    {
        l = LCM(l,a[i]);
    }
    cout << l ;
    return 0;
}

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

int b(int n, vector<ll> l) {
  if(n <3) {
    return 0;
  }
  int ans = 0;
  // n-1, n-2, n-3;
  for(int i = 0;i<=n-3;i++) {
    for(int j=i+1;j<=n-2;j++) {
      for(int k=j+1;k<=n-1;k++) {
	if(l[i] + l[j] > l[k] && 
	    l[i] + l[k] > l[j] && 
	    l[j] + l[k] > l[i] &&
	    l[j] != l[k] &&
	    l[i] != l[k] &&
	    l[i] != l[j]
	    ) {
	  ans++;
	}
      }
    }
  }
  return ans;
}

int main() {
  int n;
  cin >> n;
  vector<ll> l(n);
  for(int i = 0; i<n;i++) {
    cin >> l[i];
  }
  cout << b(n, l);
}

Measured memory_bytes: 3644
//minamoto
#include<bits/stdc++.h>
#define R register
#define fp(i,a,b) for(R int i=(a),I=(b)+1;i<I;++i)
#define fd(i,a,b) for(R int i=(a),I=(b)-1;i>I;--i)
#define go(u) for(int i=head[u],v=e[i].v;i;i=e[i].nx,v=e[i].v)
template<class T>inline bool cmax(T&a,const T&b){return a<b?a=b,1:0;}
template<class T>inline bool cmin(T&a,const T&b){return a>b?a=b,1:0;}
using namespace std;
typedef long long ll;
ll n,res;bool fl;
int main(){
	scanf("%lld",&n),fl=1;
	while(n>9)res+=9,fl&=(n%10==9),n/=10;
	printf("%lld\n",res+n-1+fl);
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define FOR(i, a, n) for(ll i = (ll)a; i < (ll)n; i++)
#define FORR(i, n) for(ll i = (ll)n - 1LL; i >= 0LL; i--)
#define rep(i, n) FOR(i, 0, n)
#define ALL(x) ((x).begin(), (x).end())
using namespace std;
using ll = long long;
template <typename T> using V = vector<T>;

constexpr int Mod = 998244353;
constexpr int mod = 1e9 + 7;
constexpr ll inf = 1LL << 60;

template <typename T> constexpr bool chmax(T &a, const T &b) {
    if(a >= b) return false;
    a = b;
    return true;
}
template <typename T> constexpr bool chmin(T &a, const T &b) {
    if(a <= b) return false;
    a = b;
    return true;
}

/*-------------------------------------------*/

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

    int n;
    cin >> n;
    V<V<pair<int, ll>>> G(n);
    rep(i, n - 1) {
        int u, v, w;
        cin >> u >> v >> w;
        u--;
        v--;
        G[u].emplace_back(v, w);
        G[v].emplace_back(u, w);
    }
    V<int> d(n, -1);
    queue<int> que;
    que.push(0);
    d[0] = 0;
    while(!que.empty()) {
        int u = que.front();
        que.pop();
        for(auto p : G[u]) {
            int v, w;
            tie(v, w) = p;
            if(d[v] == -1) {
                d[v] = d[u] + w & 1;
                que.push(v);
            }
        }
    }
    for(int a : d)
        cout << a << endl;

    return 0;
}

Measured memory_bytes: 8320
N=int(input())
a=list(map(int,input().split()))

data=[0 for i in range(N+1)]
ans=0
q=0
for i in range(N):
    q+=(a[i]+1)//(N+1)
    data[(a[i]+1)%(N+1)]+=1
ans=q*(N+1)

for r in range(1,N+1):
    q+=data[N+1-r]-1
    t=max(q,0)*(N+1)+r
    ans=min(ans,t)

print(ans)


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

int N;
vector<int>G[100];

bool used[100];
int dfs(int pos){
    used[pos]=true;

    int ret=0;
    for(int i=0;i<G[pos].size();i++){
        int to=G[pos][i];
        if(used[to])continue;
        ret=max(ret,dfs(to));
    }
    used[pos]=false;

    return ret+1;
}

void solve(){
    fill_n(G,100,vector<int>());
    for(int i=0;i<N;i++){
        int a,b;cin>>a>>b;
        G[--a].push_back(--b);
        G[b].push_back(a);
    }

    int ma=0;

    for(int i=0;i<100;i++){
        fill_n(used,100,false);
        ma=max(ma,dfs(i));
    }
    cout<<ma<<endl;

}
int main(){
    cin.tie(0);
    ios_base::sync_with_stdio(0);
    while(cin>>N,N)solve();
    return 0;
}

Measured memory_bytes: 1228
#include <bits/stdc++.h>
using namespace std;
 
int main() {
    int n;
    cin >> n;
    long long ans = 0;
    for (int i = 1; i <= n; i++) {
        int w = n / i;
        ans += 1LL * i * (1LL * w * (w + 1) / 2);
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 3584
N, M, X, Y = map(int, input().split())
x = [int(i) for i in input().split()]
y = [int(i) for i in input().split()]
x_max = max(x)
y_min = min(y)
for z in range(x_max+1, y_min+1):
    if X < z and z < Y:
        print("No War")
        quit()

print("War")


Measured memory_bytes: 3060
from collections import deque
K = int(input())

if K <= 10:
    print(K)

else:
    cnt = 9
    l = deque(list(range(1,10)))
    while True:
        a = l.popleft()
        a1 = a% 10
        if a1 != 0:
            a2 = a*10 + a1 - 1
            cnt += 1
            if cnt == K:
                print(a2)
                break
            l.append(a2)
        
        a2 = a*10 + a1
        cnt += 1
        if cnt == K:
            print(a2)
            break
        l.append(a2)

        if a1 != 9:
            a2 = a*10 + a1 + 1
            cnt += 1
            if cnt == K:
                print(a2)
                break
            l.append(a2)

Measured memory_bytes: 12084
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;
typedef long long LL;
int _min(int x, int y) {return x < y ? x : y;}
int _max(int x, int y) {return x > y ? x : y;}
int read() {
	int s = 0, f = 1; char ch = getchar();
	while(ch < '0' || ch > '9') {if(ch == '-') f = -1; ch = getchar();}
	while(ch >= '0' && ch <= '9') s = s * 10 + ch - '0', ch = getchar();
	return s * f;
}

int a[110000], b[110000];

int main() {
	int n = read();
	for(int i = 1; i <= n; i++) {
		int x = read();
		if(i & 1) a[(i + 1) / 2] = x;
		else b[i / 2] = x;
	} sort(a + 1, a + n / 2 + 1), sort(b + 1, b + n / 2 + 1);
	int max1 = 0, p1, max2 = 0, p2, max3 = 0, p3, max4 = 0, p4, cc = 1;
	for(int i = 2; i <= n / 2 + 1; i++) {
		if(a[i] == a[i - 1]) cc++;
		else {
			if(cc > max1) max2 = max1, max1 = cc, p2 = p1, p1 = a[i - 1];
			else if(cc > max2) max2 = cc, p2 = a[i - 1];
			cc = 1;
		}
	} cc = 1;
	for(int i = 2; i <= n / 2 + 1; i++) {
		if(b[i] == b[i - 1]) cc++;
		else {
			if(cc > max3) max4 = max3, max3 = cc, p4 = p3, p3 = b[i - 1];
			else if(cc > max4) max4 = cc, p4 = b[i - 1];
			cc = 1;
		}
	} if(p1 != p3) printf("%d\n", n - max1 - max3);
	else {
		printf("%d\n", _min(n - max1 - max4, n - max3 - max2));
	}
	return 0;
}


Measured memory_bytes: 512
/**
 *      ABC 60 B
 *      author  : kyomukyomupurin
 *      created : 2018-09-05 22:25:17
**/

#include <bits/stdc++.h>
using namespace std;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    int A, B, C; cin >> A >> B >> C;
    for (int i = 1; i <= B; ++i){
        if ((i * (A % B)) % B == C){
            cout << "YES" << endl; return 0;
        }
    }
    cout << "NO" << endl;

    return 0;
}


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

using namespace std;

typedef long long ll;
typedef long double ld;

const int M = 107;

string s, t;
int n;

void read() {
  cin >> n;
  cin >> s >> t;
}


void kill() {
  for (int k = n; k >= 0; --k)
    if (s.substr(n - k, k) == t.substr(0, k)) {
      cout << 2 * n - k << endl;
      return;
    }
  assert(false);
}


int main() {
  cout.precision(20);
  cout << fixed;
  ios_base::sync_with_stdio(false);
  read();
  kill();
}


Measured memory_bytes: 256
f = [[], [[1, 0], [0, 1]]]
dp = [[], [0, 1]]
for i in xrange(1, 1010):
    a = []
    d = []
    for j in xrange(2):
        b = f[i][j]
        g = [0] * (i + 2)
        for k, l in enumerate(b):
            if not l:
                continue
            if k > 0:
                g[k] = i
            if k < i:
                g[k+2] = i
        a.append(g)
        t = 0
        for k, l in enumerate(g):
            if l:
                t = k
        d.append(t)
    f.append(a)
    dp.append(d)
t = int(raw_input())
for _ in xrange(t):
    n, d = map(int, raw_input().split())
    s = 0
    for i in xrange(7):
        s += dp[n][d>>i&1] << i
    print s


Measured memory_bytes: 11012
//
//  main.cpp
//  testDebbug
//
//  Created by Manikanta Nallagatla on 18/02/20.
//  Copyright © 2020 Manikanta Nallagatla. All rights reserved.
//
// testDebug.cpp : Defines the entry point for the console application.
//

#include<iostream>
#include<string>
#include<cstdio>
#include<vector>
#include<map>
#include<algorithm>
#include<queue>
#include<set>
#include<functional>
#include<stack>
#include<unordered_map>
#include<unordered_set>
#include <fstream>
#include <math.h>

using namespace std;



struct TreeNode
{
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
struct TreeLinkNode
{
    int val;
    TreeLinkNode *left;
    TreeLinkNode *right;
    TreeLinkNode *next;
    TreeLinkNode(int x) : val(x), left(NULL), right(NULL), next(NULL) {}
};
struct ListNode
{
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};

template <class T>
void printv1(T v)
{
    cout << v << endl;
}


template <class T>
void printv2(vector<T> v)
{
    for (auto x : v) {
        cout<<x<<endl;
    }
    cout << endl;
}

template <class T>
void printv3(vector<vector<T>> v)
{
    for (auto x : v) {
        for (auto y : x) {
            cout << y << " ";
        }cout << endl;
    }
}

void printv4(vector<string> v)
{
    for (auto x : v) {
        for (auto y:x )
        {
            cout << char(y+int('0')) << " ";
        }
        cout << endl;
    }
    cout << endl;
}

static auto magic = []() {ios_base::sync_with_stdio(false); cin.tie(nullptr); return false; }();

#define POD 1000000007
#define ll long long int




int main(int argc, const char * argv[]) {
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    
    
    float r;
    cin>>r;
    cout<<(3.1416*r*2)<<endl;
    return 0;
}



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

void solve()
{
	int k;
	cin>>k;
	
	int val=7;
	val=val%k;
	
	for(int i=1;i<=10000000;i++)
    {
    	if(val==0)
    	{
    		cout<<i<<endl;
    		return ;
		}
    	val=val*10+7;
    	val=val%k;
	}
	cout<<-1<<endl;	
}

int main()
{
	solve();
	
	return 0;
}

Measured memory_bytes: 3608
#include <bits/stdc++.h>
#define REP(i, n) for(int i = 0; i < n; i++)
#define REP1(i,n) for(int i = 1; i < n+1 ;i++)
#define REPR(i, n) for(int i = n; i >= 0; i--)
#define FOR(i, m, n) for(int i = m; i < n; i++)
#define INF 2e9
#define ALL(v) v.begin(), v.end()
#define ARRAY_LENGTH(array) (sizeof(array) / sizeof(array[0]))
using namespace std;
typedef long long ll;

int main(){
    int n;
    cin >> n;
    vector<int> a(n);
    REP(i,n) cin >> a[i];
    sort(a.begin(),a.end());
    //REP(i,n) cout << a[i]<< endl;
    vector <int> dp(10000000);
    /*int mi = INF;
    REP(i,a[n-1]){
        REP(j,n){
              dp[i]+=(a[j]-i)* (a[j]-i);
        }
        mi = min(dp[i],mi);


    }
    cout << mi << endl;*/


    int sum = 0;
    REP(i,n) sum += a[i];
    double ave = double(sum) / double (n);
    int dpo=0;
    if (ave-floor(ave)<0.5){
        REP(j,n){
              dpo+=(a[j]-floor(ave))* (a[j]- floor(ave));
        }
        cout << dpo << endl;
        return 0;
    }
    else{
         REP(j,n){
              dpo+=(a[j]-floor(ave)-1)* (a[j]- floor(ave)-1);
        }
        cout << dpo << endl;
        return 0;

    }


    //return 0;

}

Measured memory_bytes: 39296
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define Rep(i,s,n) for(int i=s;i<n;i++)
#define per(i,s,n) for(int i=n-1;i>=s;i--)
#define fi first
#define se second
#define all(c) c.begin(),c.end()
typedef long long int ll;
typedef pair<int, int> P;
typedef long double ld;
void Ans(bool x){if(x) cout<<"Yes"<<endl;else cout<<"No"<<endl;}

const ll INF=1001001001;
const ll mod=1000000007;

int main(){
  int x,y;
  cin>>x>>y;
  Ans(y%2==0&&(2*x-y/2)>=0&&(y/2-x)>=0);
}

Measured memory_bytes: 3676
#include<bits/stdc++.h>
#define fr first
#define sc second
#define pb push_back
#define maxheap priority_queue<int>
#define minheap priority_queue<int, vector<int>, greater<int> >
#define ll long long
const int INF = 1e8;
const int MAXN = 2e6 + 200;
const  long double eps = 1e-16;
const long double pi = acos(-1.0);
using namespace std;

int dx[] = {0, 0, 1, 1, 1, -1, -1, -1};
int dy[] = {1, -1, 0, 1, -1, 0, 1, -1};

int n, m;
vector <int> a[2];
vector <int> ans;
void solve() {
    cin >> m >> n;
    for (int i = 1; i <= n; i++){
        int x;
        cin >> x;
        a[x & 1].pb(x);
    }
    if (a[1].size() > 2){
        cout << "Impossible\n";
        return;
    }
        if (a[1].size() >= 1) ans.pb(a[1][0]);
        for (auto x : a[0]) ans.pb(x);
        if (a[1].size() > 1)
            ans.pb(a[1][1]);
        for (auto x : ans) cout << x << " ";
        cout << "\n";
       
        if (n == 1 && ans[0] != 1){
            ans[0]--;
            ans.pb(1);
        }
        else{
            ans[0]++;
            ans[ans.size() - 1]--;
            if (ans[ans.size() - 1] == 0) ans.pop_back();
        }
        cout << ans.size() << endl;
        for (auto x : ans) cout << x  << " ";
}
int main(){
    ios::sync_with_stdio(NULL), cin.tie(0), cout.tie(0);
    cout.setf(ios::fixed), cout.precision(7);
    //freopen("input.in", "r", stdin);
    //freopen("output.out", "w", stdout)
    int step;
    step = 1;
    //cin >> step;
    for (int i = 1; i <= step; i++)
        solve();

}

Measured memory_bytes: 892
package main

import "fmt"

func main() {
	var n int
	fmt.Scan(&n)
	as := make([]int, n)
	for i := range as {
		fmt.Scan(&as[i])
	}

	pressed := make([]bool, n)
	for i, cnt := 0, 0; ; i, cnt = as[i]-1, cnt+1 {
		if i == 1 {
			fmt.Println(cnt)
			break
		}
		if pressed[i] {
			fmt.Println(-1)
			break
		}
		pressed[i] = true
	}
}


Measured memory_bytes: 5504
n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
c = list(map(int, input().split()))

ans = sum(b)
for i in range(n-1):
    if a[i] + 1 == a[i+1]:
        ans += c[a[i]-1]
print(ans)

Measured memory_bytes: 3064
#include <bits/stdc++.h>
#define SORT(x) sort((x).begin(), (x).end())
#define ALL(x) (x).begin(), (x).end()
#define rep(i, n) for (ll i = 0; i < n; i++)
#define reps(i, m, n) for (ll i = m; i < n; i++)
#define repr(i, m, n) for (ll i = m; i >= n; i--)
template <class T> bool maxi(T &a, const T &b) {
    if (a < b) {
        a = b;
        return 1;
    }
    return 0;
}
template <class T> bool mini(T &a, const T &b) {
    if (b < a) {
        a = b;
        return 1;
    }
    return 0;
}
#define dame {cout<< "-1" <<"\n"; return;}
#define INF2 1000000000000000037
#define INF  1000000007
#define MOD  1000000007
#define PI (acos(-1))
using namespace std;
using ll = long long;
using ld = long double;
using P  = pair<ll,ll>;
//--GLOBAL---------------------------------

//--MAIN-----------------------------------
void Main() {
    ll N; cin>>N;
    if(N%2==1){
        cout<< 0 <<"\n"; return;
    }
    ll ct=0;
    /*
    reps(i,1,60){
        ct+=((N/2)/(pow(5LL,i)) );
        cout<< ct <<"\n";
        if(pow(5LL,i)>(N/2)) break;
    }
    */
   N/=2;
   while(N>0){
       N/=5;
       ct+=N;
   }
    cout<< ct <<"\n";

}

//--START----------------------------------
int main() {
    cin.tie(nullptr);
    ios_base::sync_with_stdio(false);
    //cout << fixed << setprecision(15);
    Main();
}
//-----------------------------------------


Measured memory_bytes: 256
import java.io.BufferedReader
import java.io.InputStream
import java.io.InputStreamReader
import java.util.*
import kotlin.math.abs
import kotlin.math.max
import kotlin.math.min

val MOD = 1_000_000_007L

class Solver(stream: InputStream, private val out: java.io.PrintWriter) {
  fun solve() {
    val N = ni()
    val K = ni()
    val A = na(N)
    for (i in 0 until N - K) {
      val j = i + K
      if (A[j] > A[i]) out.println("Yes")
      else out.println("No")
    }
  }













































  private val isDebug = try {
    // なんか本番でエラーでる
    System.getenv("MY_DEBUG") != null
  } catch (t: Throwable) {
    false
  }

  private var tokenizer: StringTokenizer? = null
  private val reader = BufferedReader(InputStreamReader(stream), 32768)
  private fun next(): String {
    while (tokenizer == null || !tokenizer!!.hasMoreTokens()) {
      tokenizer = StringTokenizer(reader.readLine())
    }
    return tokenizer!!.nextToken()
  }

  private fun ni() = next().toInt()
  private fun nl() = next().toLong()
  private fun ns() = next()
  private fun na(n: Int, offset: Int = 0): IntArray {
    return map(n) { ni() + offset }
  }
  private fun nal(n: Int, offset: Int = 0): LongArray {
    val res = LongArray(n)
    for (i in 0 until n) {
      res[i] = nl() + offset
    }
    return res
  }

  private fun na2(n: Int, offset: Int = 0): Array<IntArray> {
    val a  = Array(2){IntArray(n)}
    for (i in 0 until n) {
      for (e in a) {
        e[i] = ni() + offset
      }
    }
    return a
  }

  private inline fun map(n: Int, f: (Int) -> Int): IntArray {
    val res = IntArray(n)
    for (i in 0 until n) {
      res[i] = f(i)
    }
    return res
  }

  private inline fun debug(msg: () -> String) {
    if (isDebug) System.err.println(msg())
  }

  private fun debug(a: LongArray) {
    debug { a.joinToString(" ") }
  }

  private fun debug(a: IntArray) {
    debug { a.joinToString(" ") }
  }

  private fun debug(a: BooleanArray) {
    debug { a.map { if (it) 1 else 0 }.joinToString("") }
  }

  private fun debugDim(A: Array<LongArray>) {
    if (isDebug) {
      for (a in A) {
        debug(a)
      }
    }
  }
  private fun debugDim(A: Array<IntArray>) {
    if (isDebug) {
      for (a in A) {
        debug(a)
      }
    }
  }

  /**
   * 勝手にimport消されるのを防ぎたい
   */
  private fun hoge() {
    min(1, 2)
    max(1, 2)
    abs(-10)
  }
}

fun main() {
  val out = java.io.PrintWriter(System.out)
  Solver(System.`in`, out).solve()
  out.flush()
}

Measured memory_bytes: 57196
#include <stdio.h>
int main()
{
		int D,L,j,i;
		scanf("%d %d",&D,&L);
		if (!D%L==0){
			i=D/L+D%L;
			printf("%d\n",i);
		}
		else {
			i=D/L;
			
			printf("%d\n",i);
		}
	return 0;
}

Measured memory_bytes: 596
#include <iostream>
#include <string>
#include <utility>
#include <algorithm>
#include <map>
#include <set>
#include <vector>
#include <cmath>
#include <cstdlib>
#include <queue>
#include <stack>
#include <iomanip>


using namespace std;

#define REP(i, n) for(ll i = 0;i < n;i++)
#define REPR(i, n) for(ll i = n;i >= 0;i--)
#define FOR(i, m, n) for(ll i = m;i < n;i++)
#define FORR(i, m, n) for(ll i = m;i >= n;i--)
#define REPO(i, n) for(ll i = 1;i <= n;i++)
#define ll long long
#define INF (ll)1 << 60
#define MINF (-1 * INF)
#define ALL(n) n.begin(),n.end()
#define MOD 1000000007
#define P pair<ll, ll>


string a, b, ans;
ll dp[3100][3100];
int main() {
	cin >> a >> b;
	REP(i, a.size()) {
		REP(j, b.size()) {
			if (a[i] == b[j])dp[i + 1][j + 1] = max(dp[i + 1][j + 1], dp[i][j] + 1);
			else dp[i + 1][j + 1] = max(dp[i + 1][j], dp[i][j + 1]);
		}
	}
	ll na = a.size(), nb = b.size();
	while(dp[a.size()][b.size()] > 0){
		if (a[na - 1] == b[nb - 1]) {
			dp[a.size()][b.size()]--;
			ans.push_back(a[na - 1]);
			na--;
			nb--;
		}
		else if (dp[na][nb] == dp[na][nb - 1])nb--;
		else na--;
	}
	reverse(ALL(ans));
	cout << ans << endl;
}

Measured memory_bytes: 73984
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define sz(x) int(x.size())
#define ALL(c) (c).begin(), (c).end()
#define SUM(x) std::accumulate(ALL(x), 0LL)
#define MIN(v) *std::min_element(v.begin(), v.end())
#define MAX(v) *std::max_element(v.begin(), v.end())
#define EXIST(v, x) (std::find(v.begin(), v.end(), x) != v.end())

using namespace std;
using ll = long long;

template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
template<class T> inline void dump(vector<T> v) { for (auto& x : v) cerr << x << " "; cerr << endl; }
template<class T> inline void dump(vector<pair<T, T>> v) { for (auto& p : v) cerr << p.first << " " << p.second << endl; }
template<class T> inline void dump(vector<vector<T>> vv) { for (auto& v : vv) {for (auto& x : v) cerr << x << " "; cerr << endl;} }

constexpr int INF = 1e9 + 5;
constexpr long long INFLL = 1LL << 62;
constexpr double eps = (1e-9);


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

  ll n, m;
  cin >> n >> m;
  vector<ll> a(n, 0);
  rep(i, n) cin >> a[i];

  vector<ll> cs(n, 0);
  cs[0] = a[0] % m;
  for (int i = 1; i < n; i++) {
    cs[i] = (cs[i-1] + a[i]) % m;
  }

  map<ll, ll> mp;
  for (auto& x : cs) {
    mp[x]++;
  }

  ll ans = 0;
  for (auto& p : mp) {
    if (p.first == 0) ans += p.second;
    if (p.second >= 2) ans += (p.second * (p.second - 1)) / 2LL;
  }

  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 8560
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
const ll MOD=1000000007;
const double PI=3.14159265358979;
const ll INF= pow(10,18);
typedef pair<ll,ll> P;
typedef vector<ll> vl;
typedef vector<vl> vvl;
#define FOR(i,a,b) for(ll i=a;i<b;i++)
#define rep(i,n) FOR(i,0,n)
string abc="abcdefghijklmnopqrstuvwxyz";
string ABC="ABCDEFGHIJKLMNOPQRSTUVWXYZ";

int main() {
  ll n,k,s;
  cin >> n >> k >> s;
  if(s!=1000000000){
    rep(i,k){
      cout << s << " ";
    }
    FOR(i,k,n){
      cout << 1000000000 << " ";
    }
  }
  else{
    rep(i,k){
      cout << s << " ";
    }
    FOR(i,k,n){
      cout << 1 << " ";
    }
  }
}

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

#define ENDL '\n'
#define sayy cout<<"YES"<<ENDL;
#define sayn cout<<"NO"<<ENDL;

int main(){

    int a,b;
    cin >> a >> b;

    int c = (6-a)-b;
    cout << c << ENDL;

    return 0;
}

Measured memory_bytes: 3620
#include <algorithm>  
#include <iostream>  
#include <sstream>  
#include <string>  
#include <cstring>
#include <vector>  
#include <queue>  
#include <set>  
#include <map>  
#include <cstdio>  
#include <cstdlib>  
#include <cctype>  
#include <cmath>  
#include <list>  
#include <cassert>
#include <ctime>
#include <climits>
using namespace std;  

#define PB push_back  
#define MP make_pair  
#define SZ(v) ((int)(v).size())  
#define FOR(i,a,b) for(int i=(a);i<(b);++i)  
#define REP(i,n) FOR(i,0,n)  
#define FORE(i,a,b) for(int i=(a);i<=(b);++i)  
#define REPE(i,n) FORE(i,0,n)  
#define FORSZ(i,a,v) FOR(i,a,SZ(v))  
#define REPSZ(i,v) REP(i,SZ(v))  
typedef long long ll;
typedef unsigned long long ull;
ll gcd(ll a,ll b) { return b==0?a:gcd(b,a%b); }

const int MAXN = 100000;

int n, limit;
int a[MAXN], b[MAXN];

ll solve(int mask) {
	ll ret = 0;
	REP(i, n) if ((mask&a[i]) == a[i]) ret += b[i];
	return ret;
}

void run() {
	scanf("%d%d", &n, &limit);
	REP(i, n) scanf("%d%d", &a[i], &b[i]);
	ll ret = solve(limit);
	for (int i = 0; (1 << i) <= limit; ++i) if (limit&(1 << i)) {
		int nlimit = (limit ^ (1 << i)) | ((1 << i) - 1);
		ll cur = solve(nlimit);
		if (cur > ret) ret = cur;
	}
	printf("%lld\n", ret);
}

int main() {
	run();
	return 0;
}


Measured memory_bytes: 1024
n=int(input())
x=[]
y=[]
for _ in range(n):
  xt,yt=map(int,input().split())
  x.append(xt)
  y.append(yt)
ans=0
for i in range(n):
  for j in range(n):
    ans+=((x[i]-x[j])**2+(y[i]-y[j])**2)**0.5
    
print(ans/n)

Measured memory_bytes: 3064
package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
)

var sc, wr = bufio.NewScanner(os.Stdin), bufio.NewWriter(os.Stdout)

func scanString() string   { sc.Scan(); return sc.Text() }
func scanRunes() []rune    { return []rune(scanString()) }
func scanInt() int         { a, _ := strconv.Atoi(scanString()); return a }
func scanInt64() int64     { a, _ := strconv.ParseInt(scanString(), 10, 64); return a }
func scanFloat64() float64 { a, _ := strconv.ParseFloat(scanString(), 64); return a }

func scanInts(n int) []int {
	res := make([]int, n)
	for i := 0; i < n; i++ {
		res[i] = scanInt()
	}
	return res
}

func debug(a ...interface{}) { fmt.Fprintln(os.Stderr, a...) }

func abs(a int) int {
	if a < 0 {
		return -a
	}
	return a
}
func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}
func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

//•*¨*•.¸¸♪main•*¨*•.¸¸♪(　-ω-)ノ　(　・ω・)
func main() {
	defer wr.Flush()
	sc.Split(bufio.ScanWords)
	sc.Buffer(make([]byte, 10000), 1001001)

	n := scanInt()
	a := scanInts(n + 1)

	memo := make([]int, n+1)
	t := 1
	for i := 0; i < n+1; i++ {
		t -= a[i]
		if t < 0 {
			fmt.Fprintln(wr, -1)
			return
		}
		memo[i] = a[i] + t
		t = min(t*2, 1e15)
	}

	ans := 0
	for i := n; i > 0; i-- {
		ans += a[i]
		if a[i-1]+(a[i]+1)/2 > memo[i-1] {
			fmt.Fprintln(wr, -1)
			return
		}
		a[i-1] = min(a[i-1]+a[i], memo[i-1])
	}

	if a[0] != 1 {
		fmt.Fprintln(wr, -1)
	} else {
		fmt.Fprintln(wr, ans+1)
	}
}


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

typedef long long ll;
typedef pair<ll,ll> P;
typedef pair<P,ll> PLL;
typedef pair<P,P> PP;
typedef vector<ll> VECLL;
typedef vector<P> VECP;
typedef priority_queue<P,VECP,greater<P> > PQP;
typedef priority_queue<ll, VECLL, greater<ll> > PQll;

#define rep(i,a,n) for(ll i = a;i < n;i++)   
#define rrep(i,a,n) for(ll i = n; i >= a;i--)
#define index_check(i,n) if(i > n-1 || i < 0) continue; 
#define LINF (ll)1e18
#define INF (int)1e9
#define fs first
#define sc second


int main(){
    string s;
    cin >> s;
    ll k;
    cin >> k;

    rep(i,0,s.size()){
        if(i != s.size()-1){
            if(s[i] != 'a' && (ll)('z' - s[i]) + 1 <= k){
                k -= (ll)('z' - s[i]) + 1;
                s[i] = 'a';
            }
        }
        else{
            if((ll)('z' - s[i]) + 1 <= k){
                k -= (ll)('z' - s[i]) + 1;
                k %= 26;
                s[i] = (k + 'a');
            }
            else{
                s[i] = (s[i] + k - 'a') % 26 + 'a';
            }
        }
    }
    cout << s << endl;
    return 0;
}


Measured memory_bytes: 3740
import std.stdio, std.conv, std.functional, std.string;
import std.algorithm, std.array, std.container, std.typecons;
import std.numeric, std.math;
import core.bitop;

string FMT_F = "%.10f";

T RD(T = long)() { static string[] ss; while(!ss.length) ss = readln.chomp.split; string res = ss[0]; ss.popFront; return res.to!T; }
string RDR()() { return readln.chomp; }
T[] ARR(T = long)(in string str, T fix = 0) { auto r = str.split.to!(T[]); r[] += fix; return r; }
size_t[] MAKE_IDX(alias less = "a < b", Range)(Range range) { auto idx = new size_t[](range.length); makeIndex!(less)(range, idx); return idx;}
size_t MIN_POS(alias less = "a < b", Range)(Range range) { auto r = minPos!(less)(range); return range.length - r.length; }

bool inside(T)(T x, T b, T e) { return x >= b && x < e; }
bool minimize(T)(ref T x, T y) { if (x > y) { x = y; return true; } else { return false; } }
bool maximize(T)(ref T x, T y) { if (x < y) { x = y; return true; } else { return false; } }

long mod = 10^^9 + 7;
void moda(ref long x, long y) { x = (x + y) % mod; }
void mods(ref long x, long y) { x = ((x + mod) - (y % mod)) % mod; }
void modm(ref long x, long y) { x = (x * y) % mod; }

void main()
{
	auto A = RD;
	auto B = RD;
	auto K = RD;

	long ans;
	foreach_reverse (i; 1..min(A, B)+1)
	{
		if (A % i == 0 && B % i == 0) 
		{
			--K;
			//stderr.writeln(i);
		}
		if (K == 0)
		{
			ans = i;
			break;
		}
	}

	writeln(ans);
	stdout.flush();
}

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

int main(){
    int ans=0;
    int n,num;
    int max1=0,max2=0;
    int index1,index2;
    cin >>n;
    
    int data1[(int)1e5+1]={};
    int data2[(int)1e5+1]={};


    for (int i = 0; i < n; i++){
        cin >>num;

        if(i%2==0){
            data2[num]++;
            if(data2[num]>max2){
                max2=data2[num];
                index2=num;
            }
        }else{
            data1[num]++;
            if(data1[num]>max1){
                max1=data1[num];
                index1=num;
            }
        }
    }
    sort(data1,data1+100001,greater<int>());
    sort(data2,data2+100001,greater<int>());

    if(index1==index2){
        ans=min((n-(data2[1]+max1)),(n-(max2+data1[1])));
    }else{
        ans=n-max2-max1;
    }
    cout << ans << '\n';
    return 0;
}


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

using namespace std;

int main(){
    long long int A,B,N;
    cin >> A >> B >> N;
    long long int x = B*(N/B) -1;
    if(A==1 || B==1){
        cout << 0 << endl;
    }else if(N<B){
        cout << A*N/B + A*(N/B) << endl;
    }else{
        cout << A*x/B + A*(x/B) << endl;
    }
}

Measured memory_bytes: 3596
#include <stdio.h>

#define WHITE 0
#define GRAY 1
#define BLACK 2

int d[101], f[101], color[101];
int A[101][101];
int n, t;

void visit(int u) {
  int v;
  color[u] = GRAY;
  d[u] = ++t;

  for (v = 1; v <= n; v++) {
    if (color[v] == WHITE && A[u][v] == 1) visit(v);
  }
  color[u] = BLACK;
  f[u] = ++t;
}

void dfs() {
  int u;
  for (u = 1; u <= n; u++) {
    color[u] = WHITE;
  }
  t = 0;
  for (u = 1; u <= n; u++) {
    if (color[u] == WHITE) {
      visit(u);
    }
  }
}

int main() {
  int i, j, u, k, v;

  scanf("%d\n", &n);
  for (i = 1; i <= n; i++) {
    scanf("%d %d", &u, &k);
    for (j = 1; j <= k; j++) {
      scanf("%d ", &v);
      A[u][v] = 1;
    }
  }

  dfs();
  for (i = 1; i <= n; i++) {
    printf("%d %d %d\n", i, d[i], f[i]);
  }


  return 0;
}

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



main(){

 map<int,bool>memo; 
 int n;
 cin>>n;
 int cnt=0;

 for(int i=0;i<n;i++){
	int p[3];
	cin>>p[0]>>p[1]>>p[2];

	sort(p,p+3);

	int k=((p[0]-1)*1000+(p[1]-1))*1000+(p[2]-1);

	if(memo.find(k)!=memo.end()){
		cnt++;
	}else{
		memo[k]=true;
	}
 }
cout<<cnt<<endl;

return 0;
}

Measured memory_bytes: 3176
using System;

namespace ConsoleApplication1
{
    class Program
    {
        static void Main(string[] args)
        {

            while (true)
            {
                string input = Console.ReadLine();
                string[] result = input.Split(' ');

                int m = int.Parse(result[0]);
                int f = int.Parse(result[1]);
                int r = int.Parse(result[2]);

                if (m == -1 && f == -1 && r == -1)
                {
                    break;
                }
                else if (m == -1 || f == -1)
                {
                    Console.WriteLine("F");
                }
                else if (m + f >= 80)
                {
                    Console.WriteLine("A");
                }
                else if (m + f >= 65)
                {
                    Console.WriteLine("B");
                }
                else if (m + f >= 50)
                {
                    Console.WriteLine("C");
                }
                else if (m + f >= 30 && r >= 50)
                {
                    Console.WriteLine("C");
                }
                else if (m + f >= 30)
                {
                    Console.WriteLine("D");
                }
                else if (m + f < 30)
                {
                    Console.WriteLine("F");
                }
            }
        }
    }
}

Measured memory_bytes: 8852
package main

import (
	"fmt"
	"math"
	"os"
)

func MinInts(nums []int) (int, int) {
	var minIdx, minVal int
	for i, e := range nums {
		if i == 0 || e < minVal {
			minIdx = i
			minVal = e
		}
	}
	return minVal, minIdx
}

func ReadInt(f *os.File) int {
	var n int
	fmt.Fscanf(f, "%d", &n)
	return n
}

func ReadInts(f *os.File, n int) []int {
	nums := make([]int, n)
	for i := 0; i < n; i++ {
		fmt.Fscanf(f, "%d", &nums[i])
	}
	return nums
}

func diff(a, b int) int {
	return int(math.Abs(float64(a - b)))
}

func main() {
	N, K := ReadInt(os.Stdin), ReadInt(os.Stdin)
	h := ReadInts(os.Stdin, N)

	dp := make([]int, N)
	for i := 1; i < N; i++ {
		v := []int{}
		for j := 1; j < K+1; j++ {
			if i-j >= 0 {
				v = append(v, dp[i-j]+diff(h[i-j], h[i]))
			}
		}

		dp[i], _ = MinInts(v)
	}

	fmt.Println(dp[N-1])
}

Measured memory_bytes: 6528
#include <stdio.h>

int main()
{
	int i, j,k;
	for (i = 1; i <= 9; i++) {
		for (j = 1; j <= 9; j++) 
		{
			k=i*j;

			printf("%dx%d=%d\n", i, j, k);
		}
	}
	return 0;
}

Measured memory_bytes: 520
t = list(map(int, input().split()))
a = list(map(int, input().split()))
b = list(map(int, input().split()))

x = t[0] * (a[0] - b[0])
y = x + t[1] * (a[1] - b[1])
if x*y > 0:
	print(0)
elif x*y == 0:
	print('infinity')
elif abs(x) % abs(y) == 0:
	print(2 * (abs(x) // abs(y)))
else:
	print(2 * (abs(x) // abs(y)) + 1)

Measured memory_bytes: 3064
#include<algorithm>
#include<complex>
#include<ctype.h>
#include<iomanip>
#include<iostream>
#include<map>
#include<math.h>
#include<numeric>
#include<queue>
#include<set>
#include<stack>
#include<stdio.h>
#include<string>
#include<string>
#include<vector>

using namespace std;
typedef long long ll;

#define FOR(i,a,b) for(ll i=(a);i<(b);++i)
#define ALL(v) (v).begin(), (v).end()
#define p(s) cout<<(s)<<endl
#define p2(s, t) cout << (s) << " " << (t) << endl
#define br() p("")
#define pn(s) cout << (#s) << " " << (s) << endl
#define p_yes() p("YES")
#define p_no() p("NO")

template < typename T >
void vprint(T &V){
	for(auto v : V){
    	cout << v << " ";
	}
	cout << endl;
}

int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, 1, 0, -1};

const ll mod = 1e9 + 7;
const ll inf = 1e18;

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

    // input
    ll N;
    cin >> N;

    vector<ll> A(N);
    FOR(i, 0, N){
        cin >> A.at(i);
    }
    sort(ALL(A));

    set<ll> se;
    se.insert(A[0]);
    FOR(i, 1, N){
        ll a = A[i] % A[0];
        if(a!=0){
            se.insert(a);
        }
    }

    while(se.size()>1){
        auto itr = se.begin();
        ll val0 = *itr;
        ll val1 = *(++itr);
   
        ll small = min(val0, val1);
        ll big = max(val0, val1);

        if(small==0){
            p(big);
            return 0;
        }

        ll new_small = big % small;
        se.erase(big);
        se.insert(new_small);
    }

    p(*se.begin());
    
    return 0;
}

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

int main(){
	int N;
	cin >> N;
	vector<int64_t> a(N);
	rep(i, N) cin >> a.at(i);
	int i = 0, count = 0;
	while (i < N) {
		if (a.at(i) % 2 == 0) {
			a.at(i) /= 2;
			count++;
		}
		else i++;
	}
	cout << count << endl;
	return 0;
}

Measured memory_bytes: 384
#include <bits/stdc++.h>
#define FIN         ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define ii          pair<int,int>
#define F           first
#define S           second
#define pb          push_back
#define all(x)      (x).begin(),(x).end()
#define rall(x)     (x).rbegin(),(x).rend()
#define fore(i,a,b) for(int i = a;i < b; i+= 1)
#define forr(i,a)   for(int i = a; i >= 0; i--)
#define fori(i,m)   for(auto i = m.begin(); i != m.end(); i++) 
#define w(t)        while(t--)
#define sz(s)       int(s.size())
#define cls(a,car)  memset(a,car,sizeof (a))
#define db(x)       cerr << #x << " is " << x << '\n'
#define FL          freopen("input.txt", "r", stdin),freopen("output.txt", "w", stdout);
#define EjecuteTime cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n"
#define angle(x)    double(x * acos(-1) / 180.0)
using namespace std;
typedef long long   ll;
typedef vector<int> vi;
typedef vector<ii>  vii;
const int N = 1 * 1e5 + 5;
const ll mod = 1e9 + 7;
const double EPS = 1e-9;
int dx[] = {1, 0}, dy[] = {0, 1};
//int dx[] = {1, 0, -1, 0}, dy[] = {0, 1, 0, -1};
//int dx[] = {2, 1, -1, -2, -2, -1, 1, 2}, dy[] = {1, 2, 2, 1, -1, -2, -2, -1};
//int dx[] = {1, 1, 0, -1, -1, -1, 0, 1}, dy[] = {0 ,1, 1, 1, 0, -1, -1, -1};
// fflush(stdout)
// cout << flush
// a + b = a ^ b + 2 * (a & b)
int sumMod(int a, int b){return 0LL + a + b > mod ? a + b - mod : a + b;}
int n;
double v[3010];
double dp[2][3010];
double f(int i, int tail){
    if(i == n){
        return 1;
    }
    double &ans = dp[i][tail];
    if(ans < 0){
        ans = 0;
        int head = n - tail;
        if(head > tail + 1)
            ans += f(i + 1, tail + 1) * (1.0 - v[i]);
    
        ans += f(i + 1, tail) * v[i];
    }
    return ans;
}
int main(){
    //FL;
    FIN;
    cin >> n;
    for(int i = 0; i < n; i++)
        cin >> v[i];
    for(int i = n; i >= 0; i--){
        for(int tail = 0; tail < n; tail++){
            double &ans = dp[i & 1][tail];    
            if(i == n){
                ans = 1;
                continue;
            }
            ans = 0;
            ans += dp[(i + 1) & 1][tail] * v[i];
            int head = n - tail;
            if(head > tail + 1)
                ans += dp[1 & (i + 1)][tail + 1] * (1.0 - v[i]);
        }
    }
    
    cout << fixed << setprecision(9) << dp[0 & 1][0] << '\n';
    EjecuteTime;
    return 0;
}       

Measured memory_bytes: 3856
#include <bits/stdc++.h>
#define rep(i, a, n) for(int i = a; i < n; i++)
#define repp(i, n) rep(i, 0, n)
#define repb(i, a, b) for(int i = a; i >= b; i--)
#define all(a) a.begin(), a.end()
#define int long long
#define fi first
#define se second
using namespace std;


signed main(){
    int d;
    while(cin >> d, d){
        int n, m;
        cin >> n >> m;
        vector<int> st(n), h(m);
        st[0] = 0;
        rep(i, 1, n){
            cin >> st[i];
        }
        rep(i, 0, m){
            cin >> h[i];
        }
        sort(all(st));
        int ans = 0;
        rep(i, 0, m){
            int ind = upper_bound(all(st), h[i]) - st.begin();
            int t;
            if(ind == n) t = d - h[i];
            else t = st[ind] - h[i];
            ans += min(t, h[i] - st[ind - 1]);
        }
        cout << ans << endl;
    }
}

Measured memory_bytes: 2064
#include <iostream>
#define MOD 1000000007
using namespace std;

int h, w, dist[1100000];
string fld[1100];

int main() {
  cin >> h >> w;
  for (int i = 0; i < h; i++) cin >> fld[i];

  dist[0] = 1;
  for (int i = 0; i < h; i++) {
    for (int j = 0; j < w; j++) {
      int v = i * w + j;
      if (fld[i][j] == '#') continue;
      if (0 <= j - 1) dist[v] += dist[i * w + j - 1];
      if (0 <= i - 1) dist[v] += dist[(i - 1) * w + j];
      dist[v] %= MOD;
    }
  }

  cout << dist[h * w - 1] << endl;
  return 0;
}

Measured memory_bytes: 9360
#include<iostream>
using namespace std;
int main()
{
    int a;
    cin>>a;
    if(a<1200) {
        cout<< "ABC"<<endl;
        return 0;
    }
    if(a==1200) {
        cout<< "ARC"<<endl;
        return 0;
    }

    if(a<2800){
        cout<< "ARC"<<endl;
        return 0;
    }
    if(a==2800) {
        cout<< "AGC"<<endl;
        return 0;}
    if(a<4800) {
        cout<< "AGC"<<endl;
        return 0;}


    return 0;
}



Measured memory_bytes: 3628
import sys


def input(): return sys.stdin.readline().strip()
def I(): return int(input())
def LI(): return list(map(int, input().split()))
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 S(): return input()
def LS(): return input().split()


n, y = LI()
ans = [-1, -1, -1]
for i in range(n + 1):
    for j in range(n + 1):
        k = n - i - j
        if k < 0:
            continue

        money = 10000 * i + 5000 * j + 1000 * k
        if money == y:
            ans = [i, j, k]
            break
print(*ans)


Measured memory_bytes: 9156
#include<cstdio>
#include<cmath>
#include<string>
#include<iostream>
#include<algorithm>
#include<utility>
#include<vector>
#include<map>
#include<set>
#include<limits>
#include<bitset>
#include<array>
#include<numeric>

using namespace std;
typedef long long int ll;

int a,b,r=0,x=1000000007,y=1000000007,z=1000000007,q=1000000007;

int main(){
    scanf("%d %d",&a,&b);
    if(a==b)printf("0\n");
    else{
        if(a<=b)x=b-a;
        if(-a<=b)y=b+a+1;
        if(-a<=-b)z=-b+a+2;
        if(a<=-b)q=-b-a+1;
        printf("%d\n",min(x,min(y,min(z,q))));
    }
    
}

Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<queue>
#include<climits>
#include<set>
#include<map>
#define ll long long
using namespace std;

int main() {
	ll a, b, h;
	cin >> a >> b >> h;
	cout << (a + b)*h / 2 << endl;

}

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


int main(int argc, char *argv[]) {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  cout << setprecision(20);

  int N; cin >> N;
  string S; cin >> S;
	      
  string s1 = S.substr(0, N);
  string s2 = S.substr(N, N);
  reverse(s2.begin(), s2.end());
  map<pair<string, string>, ll> mp1, mp2;

  auto divide = [&](const string& s, int i, string& tA, string& tB) -> void {
    tA = tB = "";
    for (int j = 0; j < N; j++) {
      if ((i >> (N-1 - j)) & 1) tA += s.at(j);
      else                      tB += s.at(j);
    }
  };

  for (int i = 0; i < (1 << N); i++) {
    string tA, tB; divide(s1, i, tA, tB);
    mp1[make_pair(tA, tB)] ++;
  }
  for (int i = 0; i < (1 << N); i++) {
    string tA, tB; divide(s2, i, tA, tB);
    mp2[make_pair(tA, tB)] ++;
  }
  ll cnt = 0;
  for (auto const& x : mp1) {
    cnt += x.second * mp2[x.first];
  }
  cout << cnt << endl;

  return 0;
}



Measured memory_bytes: 108288
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define repbtw(i, a, b) for (int i = a; i <= (int)(b); i++)
#define all(v) v.begin(), v.end()
#define pr(x) cout << x << endl


int main()
{
    int n, m;
    cin >> n >> m;
    int sum = 0;
    rep(i, m){
        int a;
        cin >> a;
        sum += a;
        if(sum > n){
            pr(-1);
            return 0;
        }
    }
    pr(n - sum);
    return 0;
}



Measured memory_bytes: 3624
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=int(a);i<int(b);++i)
using namespace std;
typedef long long ll;
int INF = (1LL << 30) - 1;
int MOD = 1e9+7;
main(){
    int H,W;
    int cost[10][10];
    cin >> H >> W;
    rep(i,0,10)rep(j,0,10){
        cin >> cost[i][j];
    }
    rep(i,0,10)rep(j,0,10)rep(k,0,10)cost[j][k] = min(cost[j][k], cost[j][i] + cost[i][k]);
    ll sum = 0;
    rep(i,0,H)rep(j,0,W){
        int a;
        cin >> a;
        if(a == -1)continue;
        sum += cost[a][1];
    }
    cout << sum << endl;
}

Measured memory_bytes: 256
#include<cstdio>

using int64=long long;

constexpr int Maxn(100000);

inline int rd(){
	static int _;
	return scanf("%d",&_),_;
}
#define io rd()

inline int gcd(const int&x,const int&y)
	{return y?gcd(y,x%y):x;}

unsigned char s[Maxn+1],t[Maxn+1];

int main(){
	const int n=io,m=io;
	scanf("\n");fread(s+1,1,n,stdin);
	scanf("\n");fread(t+1,1,m,stdin);

	const int d=gcd(n,m);
	const int dn=n/d,dm=m/d;
	const int64 lcm=(int64)n/d*m;

	for(int i=1,j=1;i<=n;i+=dn,j+=dm)
		if(s[i]!=t[j])
			return puts("-1"),0;
	return printf("%lld",lcm),0;
}


Measured memory_bytes: 384
#include <iostream>
#include <vector>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <algorithm>
#include <iomanip>
#include <numeric>
#include <queue>
#include <cmath>
using namespace std;

int main() {
    long long int n;
    cin >> n;
    long long int res = 0;
    for (long long int i = 2; i * i <= n; i++) {
        long long int c = 0;
        while (n % i == 0) {
            n /= i;
            c++;
        }
        if (c > 0) {
            long long int r = pow(c * 2, 0.5);
            if ((r + 1) * r / 2 > c) {
                res += r - 1;
            } else {
                res += r;
            }
        }
    }
    if (n > 1) res++;
    cout << res << endl;
}


Measured memory_bytes: 4096
S = list(input())
odd = ['R', 'U', 'D']
even = ['L', 'U', 'D']
for i in range(len(S)):
    if i % 2 == 1:
        if not S[i] in even:
            print('No')
            exit()
    else:
        if not S[i] in odd:
            print('No')
            exit()
print('Yes')

Measured memory_bytes: 3060
#include <stdio.h>

int main() {
    char ch;
    
    while(1){
        scanf("%c", &ch);
        
        if('a' <= ch && ch <= 'z'){
            printf("%c", ch - 32);
        } else if('A' <= ch && ch <= 'Z'){
            printf("%c", ch + 32);
        } else {
            printf("%c", ch);
        }
        
        if(ch == '\n') break;
    }
    return 0;
}


Measured memory_bytes: 2120