akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
typedef signed long long ll;

#undef _P
#define _P(...) (void)printf(__VA_ARGS__)
#define FOR(x,to) for(x=0;x<(to);x++)
#define FORR(x,arr) for(auto& x:arr)
#define ITR(x,c) for(__typeof(c.begin()) x=c.begin();x!=c.end();x++)
#define ALL(a) (a.begin()),(a.end())
#define ZERO(a) memset(a,0,sizeof(a))
#define MINUS(a) memset(a,0xff,sizeof(a))
//-------------------------------------------------------

int N;
int P[1010];
vector<int> E[1010];
int X[1010];
int A[1010],B[1010];

int from[5050];
int to[5050];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N-1) {
		cin>>P[i+1];
		E[--P[i+1]].push_back(i+1);
	}
	FOR(i,N) cin>>X[i];
	
	for(i=N-1;i>=0;i--) {
		FOR(x,5050) from[x]=1LL<<30;
		from[0]=0;
		FORR(e,E[i]) {
			FOR(x,5050) to[x]=1LL<<30;
			FOR(x,5002) if(from[x]<1LL<<30) {
				to[min(5001,x+A[e])]=min({to[min(5001,x+A[e])],from[x]+B[e],5001});
				to[min(5001,x+B[e])]=min({to[min(5001,x+B[e])],from[x]+A[e],5001});
			}
			swap(from,to);
		}
		B[i]=1LL<<30;
		A[i]=X[i];
		FOR(x,X[i]+1) B[i]=min(B[i],from[x]);
		if(B[i]==1LL<<30) return _P("IMPOSSIBLE\n");
	}
	
	cout<<"POSSIBLE"<<endl;
	
}


int main(int argc,char** argv){
	string s;int i;
	if(argc==1) ios::sync_with_stdio(false), cin.tie(0);
	FOR(i,argc-1) s+=argv[i+1],s+='\n'; FOR(i,s.size()) ungetc(s[s.size()-1-i],stdin);
	cout.tie(0); solve(); return 0;
}


Measured memory_bytes: 384
#include<bits/stdc++.h>
#include<cctype>
using namespace std;
#define rep(i,n) for (int i=0;i<(n);i++)
#define reps(i,n) for (int i=1;i<=(n);i++)
#define rrep(i,n) for (int i=(n)-1;i>=0;i--)
#define rreps(i,n) for (int i=(n);i>0;i--)
#define all(v) (v).begin(),(v).end()
#define pi 3.1415926535897932384
#define E9 1000000000
#define eps 1e-4
#define pii pair<int,int>
template<class T> inline bool chmin(T &a, T b) {if (a>b) {a = b; return 1;} return 0;};
template<class T> inline bool chmax(T &a, T b) {if (a<b) {a = b; return 1;} return 0;};
typedef long long int ll;
const long long INF = 1LL << 60;


int N, A, B, C;
int l[10];
int dfs(int n, int a, int b, int c){
  if (n==N){
    if (min({a,b,c})>0) return abs(a-A) + abs(b-B) + abs(c-C) - 30;
    else return 1000000000;
  }

  int ret0 = dfs(n+1, a, b, c); // 選ばない
  int ret1 = dfs(n+1, a+l[n], b, c) + 10;
  int ret2 = dfs(n+1, a, b+l[n], c) + 10;
  int ret3 = dfs(n+1, a, b, c+l[n]) + 10;
  return min({ret0, ret1, ret2, ret3});

}

int main(){
  cin >> N >> A >> B >> C;
  rep(i,N) cin >> l[i];

  cout << dfs(0,0,0,0) << endl;




  // cout << fixed << setprecision(10);
  
  return 0;
}

Measured memory_bytes: 3640
#include <stdio.h>
#include <iomanip>
#include <math.h>
#include <iostream>
#include <algorithm>
#include <string.h>
#include <queue>
#include <vector>
#define mod 1000000007
#define ll long long
#define pi acos(-1)
using namespace std;

int main(){
	ios::sync_with_stdio(false);
	int n;
	cin>>n;
	while(n>0){
		if(n%10==7){
			cout<<"Yes";
			return 0;
		}
		n/=10;
	}
	cout<<"No";
	
	return 0;
}

Measured memory_bytes: 3640
# C Skill Up

def list_add(li1, li2):
  return [a+b for a, b in zip(li1, li2)]

N, M, X = map(int, input().split())
data = []
for n in range(N):
  data.append(list(map(int, input().split())))

ans = 10000000
for c in range(1 << N):
  x = [0] * M
  yen = 0
  for i, n in enumerate(format(c, f"{N}b")):
    if n == "1":
      yen += data[i][0]
      x = list_add(x, data[i][1:])
  for xm in x:
    if xm < X:
      break
  else:
    ans = min(ans, yen)
    
if ans == 10000000:
  print(-1)
else:
  print(ans)

Measured memory_bytes: 9228
n=int(input())
G=[[0 for i in range(n)]for j in range(n)]
u=[0 for i in range(n)]
for i in range(n):
    A=input().split()
    u[i]=int(A[0])
    k=int(A[1])
    for j in range(k):
        x=int(A[j+2])-1
        G[i][x]=1
for i in range(n):
    for j in range(n):
        if j<n-1:
            print(G[i][j],end=" ")
        else:
            print(G[i][j])



Measured memory_bytes: 6384
#include <stdio.h>
#include <stdlib.h>
#include <iostream> 
#include <string> 
#include <cstring> 
#include <cstdio> 
using namespace std;
const int N = 1e7;
int ans[N];

int main() {
	ios::sync_with_stdio(0);
	string s;
		cin >> s;
		int n = s.length();
		int cnt = 0;
		for (int i = 0; i < n; i++) {
			if (s[i] == 'R') {
				if (s[i + 1] == 'R') {
					ans[i] = 0; 
					cnt++;
				}
				else {
						ans[i] = cnt / 2 + 1;
						ans[i + 1] = (cnt +1) / 2 + 1;
						cnt = 0;
						for (int j = i+2; j < n; j++) {
							if (s[j] == 'L') {
								ans[j] = 0;
								cnt++;
							}
							else break;
						}
						ans[i] += (cnt + 1) / 2;
						ans[i + 1] += cnt / 2;
						i += cnt;
						cnt = 0;
					}
				}
			}
		
		cout << ans[0];
		for (int i = 1; i < n; i++)
			cout << ' ' << ans[i];
		cout << '\n';
	
	 
	return 0;
}


Measured memory_bytes: 1104
N = int(input())
X = [list(map(int, input().split())) for _ in range(N)]

lb = sorted(v for v, _ in X)
ub = sorted(v for _, v in X)

if N % 2 == 0:
    l = lb[N // 2 - 1] + lb[N // 2]
    u = ub[N // 2 - 1] + ub[N // 2]
    print(u - l + 1)
else:
    l = lb[N // 2]
    u = ub[N // 2]
    print(u - l + 1)

Measured memory_bytes: 116524
# abc172_b.py
# https://atcoder.jp/contests/abc172/tasks/abc172_b

# B - Minor Change /
# 実行時間制限: 2 sec / メモリ制限: 1024 MB
# 配点 : 200点

# 問題文
# 文字列 S, T が与えられます。次の操作を繰り返して S を Tに変更するとき、操作回数の最小値を求めてください。

# 操作：Sの 1

# 文字を選んで別の文字に書き換える

# 制約
#     S, T は長さ 1 以上 2×10^5以下
#     S, Tは英小文字のみからなる
#     Sと Tの長さは等しい

# 入力
# 入力は以下の形式で標準入力から与えられる。

# S
# T

# 出力
# 答えを出力せよ。

# 入力例 1
# cupofcoffee
# cupofhottea

# 出力例 1
# 4

# 例えば、次のような 4回の操作で達成できます。
#     1回目：6文字目の c を h に書き換える
#     2回目：8文字目の f を t に書き換える
#     3回目：9文字目の f を t に書き換える
#     4回目：11文字目の e を a に書き換える

# 入力例 2
# abcde
# bcdea

# 出力例 2
# 5

# 入力例 3
# apple
# apple

# 出力例 3
# 0

# 1度も操作をしなくてもよいこともあります。


def calculation(lines):
    S = lines[0]
    T = lines[1]
    n_diff = 0
    for i in range(len(S)):
        if S[i] != T[i]:
            n_diff += 1
    return [n_diff]


# 引数を取得
def get_input_lines(lines_count):
    lines = list()
    for _ in range(lines_count):
        lines.append(input())
    return lines


# テストデータ
def get_testdata(pattern):
    if pattern == 1:
        lines_input = ['cupofcoffee', 'cupofhottea']
        lines_export = [4]
    if pattern == 2:
        lines_input = ['abcde', 'bcdea']
        lines_export = [5]
    if pattern == 3:
        lines_input = ['apple', 'apple']
        lines_export = [0]
    return lines_input, lines_export


# 動作モード判別
def get_mode():
    import sys
    args = sys.argv
    if len(args) == 1:
        mode = 0
    else:
        mode = int(args[1])
    return mode


# 主処理
def main():
    mode = get_mode()
    if mode == 0:
        lines_input = get_input_lines(2)
    else:
        lines_input, lines_export = get_testdata(mode)

    lines_result = calculation(lines_input)

    for line_result in lines_result:
        print(line_result)

    # if mode > 0:
    #     print(f'lines_input=[{lines_input}]')
    #     print(f'lines_export=[{lines_export}]')
    #     print(f'lines_result=[{lines_result}]')
    #     if lines_result == lines_export:
    #         print('OK')
    #     else:
    #         print('NG')


# 起動処理
if __name__ == '__main__':
    main()


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

using namespace std;
#define rep(i,n) for(int i=0;i<(n);i++)

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

#define MAX 100005
#define INF INT_MAX

int timeStamp = 0;
vector< vector<int> > adj;
vector<int> d, f;

void dfs(int v)
{
    d[v] = ++timeStamp;
    for (auto e : adj[v]) {
        if (d[e]) continue;
        dfs(e);
    }
    f[v] = ++timeStamp;
}

int main(int, char**)
{
    int n;
    cin >> n;

    adj.assign(n, vector<int>());
    d.assign(n,0);
    f.assign(n,0);
    int u, k, v;
    rep(i,n) {
        cin >> u >> k; u--;
        rep(j,k) {
            cin >> v; v--;
            adj[u].push_back(v);
        }
    }
    rep(i,n) {
        if (d[i]) continue;
        dfs(i);
    }
    rep(i,n) {
        cout << i+1 << " " << d[i] << " " << f[i] << endl;
    }
    return 0;
}



Measured memory_bytes: 3164
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define sqr(x) ((x)*(x))
#define ull unsigned long long
#define mp make_pair
#define ld long double
#define fi first
#define se second
#define PI pair<int,int>
inline char gc(){
    static char buf[100000],*p1=buf,*p2=buf;
    return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
#define gc getchar
inline ll read(){
	ll x = 0; char ch = gc(); bool positive = 1;
	for (; !isdigit(ch); ch = gc())	if (ch == '-')	positive = 0;
	for (; isdigit(ch); ch = gc())	x = x * 10 + ch - '0';
	return positive ? x : -x;
}
inline void write(ll a){
    if(a<0){
    	a=-a; putchar('-');
	}
    if(a>=10)write(a/10);
    putchar('0'+a%10);
}
inline void writeln(ll a){write(a); puts("");}
inline void wri(ll a){write(a); putchar(' ');}
const int N=1000005,mod=1000000007;
ll dp[N][2],inv[N],dq=1,ans=0;
ll ksm(ll a,int b){
	int ans=1;
	for(;b;b>>=1){
		if(b&1)ans=ans*a%mod;
		a=a*a%mod;
	}
	return ans;
}
int main(){
	int n=read();
	dp[0][0]=1;
	for(int i=inv[1]=1;i<n;i++){
		dp[i][0]=dp[i-1][1]*2%mod;
		dp[i][1]=(dp[i-1][0]+dp[i-1][1])%mod;
	}
	for(int i=1;i<=n;i++){
		if(i>1)inv[i]=mod-mod/i*inv[mod%i]%mod;
		dq=dq*(n-i+1)%mod*inv[i]%mod;
		//cout<<dq<<" "<<dp[i-1][0]<<" "<<dp[i-1][1]<<" "<<inv[i]<<endl;
		ans=(ans+dq*(dp[i-1][1]+dp[i-1][0])%mod*ksm((ll)3*n*i%mod,mod-2))%mod;
	}
	for(int i=1;i<n;i++)ans=ans*(mod+1)/3%mod;
	cout<<(ans+mod)%mod<<endl;
}

Measured memory_bytes: 23680
#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <string>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <stdio.h>
using namespace std;
#define int long long
int MOD = 1000000007;
signed main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	int N;
	cin >> N;
	vector<int> A(N);
	vector<int> B(N);
	int res = 0;
	for (int i = 0; i < N; i++) {
		cin >> A[i] >> B[i];
	}
	int C;
	int k;
	set<int> X;
	set<int> Y;
	int t = 0;
	for (int i = 0; i < N; i++) {
		C = A[i] * B[i];
		k = sqrt(A[i] * B[i]);
		if (k*k >= A[i] * B[i]) {
			k--;
		}
		t++;
		if (k*(k + 1) < C) {
			res = 2 * k;
			if (A[i] == k + 1) {
				if (k*(k + 2) >= C) {
					res--;
				}
			}
			if (B[i] == k + 1) {
				if (k*(k + 2) >= C) {
					res--;
				}
			}
			if (A[i] <= k)res--;
			if (B[i] <= k)res--;
		}
		else {
			res = 2 * k - 1;
			if (A[i] <= k)res--;
			if (B[i] <= k)res--;
		}
		cout << res << endl;
	}

}

Measured memory_bytes: 384
#include <iostream>
#include <string>
#include <algorithm>
#include  <set>
#include <cmath>
#include <cstdlib>
#include <bitset>
#include<vector>
using namespace std;
typedef long long ll;
#define rep(i,k) for(i=0;i<k;i++)
#define dd(t,h) if(t!=0) h+=10;


int main() {
	int  a = 10, b, c[2000] = {}, d[2000] = {}, e, f, g = 0, n, i, j, k = 0, m = 0,h, w,y,x;
	char ss[2000][2000];
	cin >> h >> w;
	rep(i, h) cin >> ss[i];

	rep(i, h) {
		rep(j, w) {
			if (ss[i][j] == '#') {
				c[j] = 0; d[i] = 0;
			}
			else {
				if (i == 0) {
					m = i;	n = j;	f = 0;
					while (m < h && ss[m][j] == '.') {
						c[j]++;
						m++;
					}
				}
				else {
					if(ss[i-1][j]=='#'){
						m = i;	n = j;	f = 0;
						while (m < h && ss[m][j] == '.') {
							c[j]++;
							m++;
						}
					}
				

				}
				
				
				if (j == 0) {
					m = i;	n = j;
					while (n < w && ss[i][n] == '.') {
						d[i]++;
						n++;
					}
				}
				else {
					if (ss[i][j-1] == '#') {
						m = i;	n = j;	f = 0;
						while (n < w && ss[i][n] == '.') {
							d[i]++;
							n++;
						}
					}


				}

				x = c[j] + d[i]-1;
				g = max(g, x);
			}



		}
	}

	cout << g;
	return 0;
}

Measured memory_bytes: 4224
package main

import (
	"bufio"
	"fmt"
	"math"
	"os"
	"sort"
	"strconv"
	"strings"
)

var (
	sc     scanner
	writer *bufio.Writer
)

func solve() {
	_, t := sc.nextInt(), sc.nextInt()
	a := sc.nextInts()

	x := t
	for i := 0; i < len(a)-1; i++ {
		x += _min(t, a[i+1]-a[i])
	}

	ans := strconv.Itoa(x)
	writer.WriteString(ans + "\n")
}

/* template functions */

func main() {
	solve()
	writer.Flush()
}

func init() {
	sc = scanner{
		buf: make([]string, 0, 64),
		cur: 0,
		r:   bufio.NewReader(os.Stdin),
	}
	writer = bufio.NewWriter(os.Stdout)
}

type scanner struct {
	buf []string
	cur int
	r   *bufio.Reader
}

func (s *scanner) readln() {
	line, err := s.r.ReadString('\n')
	if err != nil {
		panic(err)
	}

	drop := 1
	if len(line) > 1 && line[len(line)-2] == '\r' {
		drop = 2
	}
	line = line[:len(line)-drop]

	s.cur = 0
	s.buf = strings.Split(line, " ")
}

func (s *scanner) isFull() bool {
	if s.cur == len(s.buf) {
		return true
	}
	return false
}

func (s *scanner) resetCur() {
	s.cur = 0
}

func (s *scanner) next() string {
	if s.cur == 0 {
		s.readln()
	}
	res := s.buf[s.cur]
	s.cur++
	if s.isFull() {
		s.resetCur()
	}
	return res
}

func (s *scanner) nexts() []string {
	s.readln()
	s.resetCur()
	return s.buf
}

func (s *scanner) nextByte() byte {
	if s.cur == 0 {
		s.readln()
	}
	res := s.buf[s.cur][0]
	s.cur++
	if s.isFull() {
		s.resetCur()
	}
	return res
}

func (s *scanner) nextInt() int {
	if s.cur == 0 {
		s.readln()
	}
	res, _ := strconv.Atoi(s.buf[s.cur])
	s.cur++
	if s.isFull() {
		s.resetCur()
	}
	return res
}

func (s *scanner) nextInts() []int {
	s.readln()
	res := make([]int, len(s.buf))
	for i, _ := range s.buf {
		res[i], _ = strconv.Atoi(s.buf[i])
	}
	s.resetCur()
	return res
}

func (s *scanner) nextFloat() float64 {
	if s.cur == 0 {
		s.readln()
	}
	res, _ := strconv.ParseFloat(s.buf[s.cur], 64)
	s.cur++
	if s.isFull() {
		s.resetCur()
	}
	return res
}

func (s *scanner) nextFloats() []float64 {
	s.readln()
	res := make([]float64, len(s.buf))
	for i, _ := range s.buf {
		res[i], _ = strconv.ParseFloat(s.buf[i], 64)
	}
	s.resetCur()
	return res
}

func _max(x, y int) int {
	return int(math.Max(float64(x), float64(y)))
}

func _min(x, y int) int {
	return int(math.Min(float64(x), float64(y)))
}

func _abs(x int) int {
	return int(math.Abs(float64(x)))
}

// Searchable
// idx := lower_bound([]int{-199, -1, 0, 2, 4, 67, 100, 8435}, 60)
// => idx = 5
//
// No present
// idx := lower_bound([]int{-199, -1, 0, 2, 4, 67, 100, 8435}, 10000)
// => idx = 8
func lower_bound(a []int, x int) int {
	return sort.SearchInts(a, x)
}

func dump(value ...interface{}) {
	for _, v := range value {
		fmt.Fprintf(os.Stderr, "%#v\n", v)
	}
}

func yes() {
	writer.WriteString("Yes\n")
}

func no() {
	writer.WriteString("No\n")
}


Measured memory_bytes: 9600
N,K = map(int,input().split())
A = list(map(int,input().split()))
route = [1]
for i in range(N):
  route.append(A[route[i]-1])
prepart = route.index(route[-1])
cycle = len(route) - prepart - 1
if K > N:
  K =(K-prepart)%cycle +prepart
print(route[K])

Measured memory_bytes: 32208
#include <cstring>
#include <map>
#include <unordered_map>
#include <string>
#include <list>
#include <vector>
#include <algorithm>
#include <queue>
#include <stack>
#include <cstdio>
#include <iostream>
#include <set>
#include <unordered_set>
using namespace std;

#define MAX(a,b) (a>b?a:b)
#define MIN(a,b) (a<b?a:b)
typedef long long ll;
typedef unsigned long long ull;
typedef unsigned int ui;
typedef pair<int, int> pii;

int gi() {
    int a;
    scanf("%d", &a);
    return a;
}

ll gli() {
    ll a;
    scanf("%lld", &a);
    return a;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int a = gi();
    int b = gi();
    if (a < b) {
        for (int i = 0; i < b; i++)
            printf("%d", a);
    } else {
        for (int i = 0; i < a; i++)
            printf("%d", b);
    }

    printf("\n");

    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define mp make_pair
#define all(x) (x).begin(), (x).end()
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define repp(i, a, b) for (int i = a; i <= (b); ++i)
#define repr(i, a, b) for (int i = a; i >= (b); --i)
#define bit(n) (1LL << (n))
#define len(x) ((ll)(x).size())
#define debug(var) cout << "[" << #var << "]\n" << var << endl
#define int long long
typedef long long ll;
const int INF = 1001001001001001001ll;
const ll LINF = 1001001001001001001ll;
const int MOD = 1000000007;
const double EPS = 1e-9;

template <typename T>
ostream& operator<<(ostream& s, const vector<T>& v) {
  int len = v.size();
  for (int i = 0; i < len; ++i) {
    s << v[i];
    if (i < len - 1)
      s << ' ';
  }
  return s;
}

template <typename T>
ostream& operator<<(ostream& s, const vector<vector<T>>& vv) {
  int len = vv.size();
  for (int i = 0; i < len; ++i) {
    s << vv[i];
    if (i != len - 1)
      s << '\n';
  }
  return s;
}

template <class T>
inline bool chmin(T& a, T b) {
  if (a > b) {
    a = b;
    return true;
  }
  return false;
}

template <class T>
inline bool chmax(T& a, T b) {
  if (a < b) {
    a = b;
    return true;
  }
  return false;
}

__attribute__((constructor)) void initial() {
  cin.tie(nullptr);
  ios::sync_with_stdio(false);
  cout << fixed << setprecision(15);
}

signed main() {
  int N;
  cin >> N;
  vector<int> A(N);
  rep(i, N) {
    cin >> A[i];
  }

  int ans = pow(3, N);

  int temp = 1;
  rep(i, N) {
    temp *= (A[i] % 2 ? 1 : 2);
  }
  ans -= temp;
  cout << ans << endl;
}

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

#define ln '\n'
#define REP(i, n) for (int i = 0; i < (int)(n); ++i)
#define FOR(i, a, b) for (int i = (a); i <= (int)(b); ++i)
#define FORR(i, a, b) for (int i = (a); i >= (int)(b); --i)
#define ALL(c) (c).begin(), (c).end()

typedef long long ll;
typedef vector<int> VI;
typedef vector<ll> VL;
typedef vector<VI> VVI;
typedef vector<VL> VVL;
typedef pair<int, int> P;
typedef pair<ll, ll> PL;
typedef vector<P> VP;
typedef vector<PL> VPL;
typedef vector<string> VS;

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    string s, t;
    cin >> s >> t;
    int ans = 0;
    REP(i, 3) {
        if (s[i] == t[i]) ans++;
    }
    cout << ans << ln;
    return 0;
}


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

typedef long long ll;
typedef unsigned long long ull;

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define RFOR(i,a,b) for(int i=(b-1);i>=(a);--i)
#define REP(i,n)   FOR(i,0,n)
#define RREP(i,n)   RFOR(i,0,n)
#define SORT(s) sort(s.begin(), s.end())
#define P pair<int, int>
#define mp make_pair

const double INF = 1e+09;
const int MOD = 1e9+7;

using namespace std;

template <typename _Ty>
ostream& operator << (ostream& ostr, const vector<_Ty>& v) {if (v.empty()) {ostr << "{ }"; return ostr;}
    ostr << "{" << v.front(); for (auto itr = ++v.begin(); itr != v.end(); itr++) {ostr << ", " << *itr;}
    ostr << "}";
    return ostr;}

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

int gcd(int a, int b){
   if (a%b == 0) return(b);
   else return(gcd(b, a%b));}

int lcm(int a, int b)
{return a * b / gcd(a, b);}

vector<int> uniq(vector<int> vec){
  sort(vec.begin(), vec.end());
  vec.erase(unique(vec.begin(), vec.end()), vec.end());
  return vec;}

vector<ll> divisor(ll n) {
vector<ll> ret;
for(int64_t i = 1; i * i <= n; i++) {
  if(n % i == 0) {
    ret.push_back(i);
    if(i * i != n) ret.push_back(n / i);
  }
}
  sort(begin(ret), end(ret));
  return (ret);
}
void permu(int n){
  vector<int> perm(n);
  REP(i, n) perm[i] = i;
do{
  cout << perm  << endl;
}
while (next_permutation(perm.begin(), perm.end()));
return;}

vector<pair<ll, int>> prime_div(ll n){
  vector<pair<ll, int>> res;
  for (ll i=2; i*i <= n;i++){
    if (n%i == 0){
      int a = 0;
      while(n%i == 0){
        n /= i;
        a++;
      }
      pair<ll, int> tmp;
      tmp.first = i;
      tmp.second = a;
      res.push_back(tmp);
    }
  }
  if (n != 1){
    pair<ll, int> now;
    now.first = n;
    now.second = 1;
    res.push_back(now);}
  return res;
}


// printf("%.10f\n" , ans);
int main(void){
  ios::sync_with_stdio(false);
  int n, m, k;
  cin >> n >> m >> k;
  vector<ll> a(n+1, 0), b(m+1, 0);
  REP(i, n){
    ll tmp;
    cin >> tmp;
    a[i+1] = a[i] + tmp;
  }
  REP(i, m){
    ll tmp;
    cin >> tmp;
    b[i+1] = b[i] + tmp;
  }

int ans = 0;
  int b_cnt = m;
  REP(i, n+1){
    if (a[i] > k) {
      continue;
      cout << k << endl;
    }
    while (a[i] + b[b_cnt] > k) b_cnt--;
    ans = max(ans, i + b_cnt);
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 6396
#include <iostream>
#include <cmath>
#include <climits>
#include <algorithm>

typedef long long ll;

using namespace std;


int main() {
  ll h, w;
  cin >> h >> w;
  if (h % 3 == 0 || w % 3 == 0) {
    cout << 0 << endl;
    return 0;
  }
  ll minimum = LLONG_MAX;
  ll m1 = max(h, w);
  ll m2 = min(h, w);
  for (ll i = 1; i<=m1/2; i++) {
    ll s1 = i * m2;
    ll s2 = (m1 - i) % 2 == 0 || m2 % 2 == 0 ? (m1 - i) * m2 / 2 : max(m1 -i, m2) + ((m1 - i) * m2 - max(m1 -i, m2))/ 2;
    ll s3 = (m1 - i) % 2 == 0 || m2 % 2 == 0 ? (m1 - i) * m2 / 2 : ((m1 - i) * m2 - max(m1 -i, m2)) / 2;
    // cout << i << ' ' << m1 << ' ' << m2 << ' ' << s1 << ' ' << s2 << ' ' << s3 << endl;
    if (max(s1, max(s2, s3)) - min (s1, min(s2, s3)) < minimum) {
      minimum = max(s1, max(s2, s3)) - min (s1, min(s2, s3));
    }
    // cout << minimum << endl;
    s2 = (m1 - i) % 2 == 0 || m2 % 2 == 0 ? (m1 - i) * m2 / 2 : min(m1 -i, m2) + ((m1 - i) * m2 - min(m1 -i, m2))/ 2;
    s3 = (m1 - i) % 2 == 0 || m2 % 2 == 0 ? (m1 - i) * m2 / 2 : ((m1 - i) * m2 - min(m1 -i, m2)) / 2;
    // cout << i << ' ' << m1 << ' ' << m2 << ' ' << s1 << ' ' << s2 << ' ' << s3 << endl;
    if (max(s1, max(s2, s3)) - min (s1, min(s2, s3)) < minimum) {
      minimum = max(s1, max(s2, s3)) - min (s1, min(s2, s3));
    }
    // cout << minimum << endl;
  }
  for (ll i = 1; i<=m2/2; i++) {
    ll s1 = i * m1;
    ll s2 = (m2 - i) % 2 == 0 || m1 % 2 == 0 ? (m2 - i) * m1 / 2 : max(m2 -i, m1) + ((m2 - i) * m1 - max(m2 -i, m1))/ 2;
    ll s3 = (m2 - i) % 2 == 0 || m1 % 2 == 0 ? (m2 - i) * m1 / 2 : ((m2 - i) * m1 - max(m2 -i, m1)) / 2;
    // cout << i << ' ' << m1 << ' ' << m2 << ' ' << s1 << ' ' << s2 << ' ' << s3 << endl;
    if (max(s1, max(s2, s3)) - min (s1, min(s2, s3)) < minimum) {
      minimum = max(s1, max(s2, s3)) - min (s1, min(s2, s3));
    }
    // cout << minimum << endl;
    s2 = (m2 - i) % 2 == 0 || m1 % 2 == 0 ? (m2 - i) * m1 / 2 : min(m2 -i, m1) + ((m2 - i) * m1 - min(m2 -i, m1))/ 2;
    s3 = (m2 - i) % 2 == 0 || m1 % 2 == 0 ? (m2 - i) * m1 / 2 : ((m2 - i) * m1 - min(m2 -i, m1)) / 2;
    // cout << i << ' ' << m1 << ' ' << m2 << ' ' << s1 << ' ' << s2 << ' ' << s3 << endl;
    if (max(s1, max(s2, s3)) - min (s1, min(s2, s3)) < minimum) {
      minimum = max(s1, max(s2, s3)) - min (s1, min(s2, s3));
    }
    // cout << minimum << endl;
  }
  cout << minimum << endl;
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <iostream>
#include <string>
#include <map>
#include <math.h>
#include <vector>
using namespace std;
struct cww { cww() { ios::sync_with_stdio(false); cin.tie(0); } }star;
map<int, int> ct;
map<int, int> ct2;
typedef vector<int> vi;
typedef vector<vector<int> > vvi;
typedef vector<pair<int, int> > vpii;
typedef pair<int, int> pii;
typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> pll;
typedef pair<double, double> pdd;
typedef vector<ll> vll;
#define INF 0x3f3f3f3f
#define MOD 998244353LL
#define EPS 0.00001
#define f first
#define s second
#define pb push_back
#define mp make_pair

#define FOR(i, a, b) for (int i=(a); i<=(signed)(b); i++)
#define AFOR(i, a) for (int i=0; i<(signed)(a); i++)
#define RFOR(i, a, b) for (int i=(a); i >= b; i--)

#define MN 100005
int n, m, l;
int a, b, c;
string s[MN];
string str;
int dx[4] = { 1,0,-1,0 };
int dy[4] = { 0,1,0,-1 };

/*
int N;
cin >> N;
vi vect(N);
FOR(i,N) cin >> vec.at(i);*/
//sort(vec.begin(),vec.end());
//vvi data(N,vi(4));

std::vector<int> Eratosthenes(const int N)
{
	std::vector<bool> is_prime(N + 1);
	for (int i = 0; i <= N; i++)
	{
		is_prime[i] = true;
	}
	std::vector<int> P;
	for (int i = 2; i <= N; i++)
	{
		if (is_prime[i])
		{
			for (int j = 2 * i; j <= N; j += i)
			{
				is_prime[j] = false;
			}
			P.emplace_back(i);
		}
	}
	return P;
}
/*	int bfs(int x, int y,vvi &A,vvi flag) {
		queue<pii> que;
		que.push(pii(x, y));
		while (que.size()) {
			pii p = que.front(); que.pop();
			AFOR(i, 4) {
				int nx = p.first + dx[i]; int ny = p.second + dy[i];
				if (0 <= nx && nx < N && 0 <= ny && ny < N) {
					if (A.at(p.first).at(p.second) + flag.at(p.first).at(p.second) < A.at(nx).at(ny)) {
						A.at(nx).at(ny) = A.at(p.first).at(p.second) + flag.at(p.first).at(p.second);
						que.push(pii(nx, ny));
					}
				}
			}
		}
		return 0;
	}
	*/
	/*int gcd(int p, int q){
		while(q != 0){
		int r = p % q;
		p = q;
		q = r;
		}
	return p;
	}*/
ll N;
ll K;
ll A[200100];
int  L[200100];

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	int x1, x2, x3, x4, x5;
	cin >> x1 >> x2 >> x3 >> x4 >> x5;
	if (x1 == 0) { cout << 1 << endl; }
	else if (x2 == 0) { cout << 2 << endl; }
	else if (x3 == 0) { cout << 3 << endl; }
	else if (x4 == 0) { cout << 4 << endl; }
	else if (x5 == 0) { cout << 5 << endl; }

	return 0;

}

Measured memory_bytes: 6744
#define _USE_MATH_DEFINES
#define _CRT_SECURE_NO_WARNINGS

#include <iostream>
#include <string>
#include <sstream>
#include <iomanip>
#include <cmath>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <stack>
#include <queue>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <bitset>
#include <utility>
#include <numeric>

using namespace std;

using ll = long long;
using ull = unsigned long long;

const ll inf = (ll)1e9;
const ll mod = (ll)1e9 + 7;

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

	vector<int> a(n);
	for (int i = 0; i < n; i++)
	{
		cin >> a.at(i);
	}

	deque<int> b;
	for (int i = 0; i < n; i++)
	{
		if (i % 2 == 0)
		{
			b.push_front(a.at(i));
		}
		else
		{
			b.push_back(a.at(i));
		}
	}

	if (n % 2 == 0)
	{
		reverse(b.begin(), b.end());
	}

	for (int i = 0; i < n; i++)
	{
		cout << (i == 0 ? "" : " ") << b.at(i);
	}

	cout << endl;
}


Measured memory_bytes: 3840
import java.util.Scanner;

class Dice {
    private int dn[] = new int[6];

    Dice(int d[]) {
        for (int i = 0; i < 6; i++) {
            dn[i] = d[i];
        }
    }

    void turnN() {
        int x = dn[0];
        dn[0] = dn[1];
        dn[1] = dn[5];
        dn[5] = dn[4];
        dn[4] = x;
    }

    void turnS() {
        int x = dn[0];
        dn[0] = dn[4];
        dn[4] = dn[5];
        dn[5] = dn[1];
        dn[1] = x;
    }

    void turnW() {
        int x = dn[0];
        dn[0] = dn[2];
        dn[2] = dn[5];
        dn[5] = dn[3];
        dn[3] = x;
    }

    void turnE() {
        int x = dn[0];
        dn[0] = dn[3];
        dn[3] = dn[5];
        dn[5] = dn[2];
        dn[2] = x;
    }

    int Ans() {
        return dn[0];
    }

}

class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int num[] = new int[6];
        for (int i = 0; i < 6; i++) {
            num[i] = sc.nextInt();
        }
        Dice d1 = new Dice(num);
        String com = sc.next();
        for (int i = 0; i < com.length(); i++) {
            switch (com.charAt(i)) {
            case 'S':
                d1.turnS();
                break;
            case 'N':
                d1.turnN();
                break;
            case 'W':
                d1.turnW();
                break;
            case 'E':
                d1.turnE();
                break;
            }
        }
        System.out.println(d1.Ans());
    }
}


Measured memory_bytes: 26288
// https://atcoder.jp/contests/abc173/tasks/abc173_a
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define REP(i, n) FOR(i, 0, n)
#define REPR(i, n) for (int i = n - 1; i >= 0; i--)
#define FOR(i, s, n) for (int i = (s), i##_len = (n); i < i##_len; ++i)
#define ALL(obj) (obj).begin(), (obj).end()
#define ALLR(obj) (obj).rbegin(), (obj).rend()
#define DIV(a, b) ((a - 1) / b + 1)

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int N;
    cin >> N;
    map<string, int> mp;
    while (N--) {
        string t;
        cin >> t;
        mp[t]++;
    }
    cout << "AC x " << mp["AC"] << "\n";
    cout << "WA x " << mp["WA"] << "\n";
    cout << "TLE x " << mp["TLE"] << "\n";
    cout << "RE x " << mp["RE"] << "\n";

    return 0;
}


Measured memory_bytes: 3652
N,M,X=gets.split.map(&:to_i)
as=$<.read.split.map(&:to_i).each_slice(M+1).to_a

min = 10**7
1.upto(N) do |i|
    as.combination(i) do |arr|
        sums = ([0]*(M+1)).zip(*arr).map { |arr| arr.sum }
        if sums[1..-1].all? {|n| X<=n}
            min = sums[0] if sums[0] < min
        end
    end
end

if min != 10**7
    puts min
else
    puts -1
end


Measured memory_bytes: 14656
#include <iostream>
#include <algorithm>
#include <utility>

using namespace std;
	int i,n,a[100010],b[100010]={0},c[100010]={0};
	pair<int,int> p[100010],q[100010];
int main(){
	cin >> n;
	for(i=0;i<n;i++){
		cin >> a[i];
		if(i%2==0){
			b[a[i]]++;
		}else{
			c[a[i]]++;
		}
	}
	p[0] = make_pair(0,0);
	q[0] = make_pair(0,0);
	for(i=1;i<=100000;i++){
		p[i] = make_pair(b[i],i);
		q[i] = make_pair(c[i],i);
	}
	sort(p,p+100001);
	sort(q,q+100001);
	int l,r,x,y,ans1 = 0,ans2 = 0,ans3 = 0,ans4 = 0;
	l = p[100000].second,r = q[100000].second,x = p[99999].second,y = q[99999].second;
	//cout << l << " " << r << " " ;
	for(i=0;i<n;i++){
		if(i%2==0 && a[i]!=l){
			ans1++;
		}
		if(i%2==0 && a[i]!=x){
			ans2++;
		}
		if(i%2==1 && a[i]!=r){
			ans3++;
		}
		if(i%2==1 && a[i]!=y){
			ans4++;
		}
	}
	if(l!=r){
		cout << ans1 + ans3 << endl;
	}else{
		cout << min(ans1+ans4,ans2+ans3) << endl;
	}
}
	

Measured memory_bytes: 2944
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,m,a[100001],pd[100001],ans;
signed main()
{
	int x,y;
	scanf("%lld%lld",&n,&m);
	ans=n;
	for(int i=1;i<=n;i++)
	scanf("%lld",&a[i]);
	for(int i=1;i<=m;i++)
	{
		scanf("%lld%lld",&x,&y);
		if(a[x]<=a[y])
		if(pd[x]==0)
		ans--,pd[x]=1;
		if(a[x]>=a[y])
		if(pd[y]==0)
		ans--,pd[y]=1;
	}
	printf("%lld",ans);
    return 0;
}

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

int main() {
  int N, K;
  string S;
  cin >> N >> K;
  cin >> S;
  
  if (S.at(K-1) == 'A') {
    S.at(K-1) = 'a';
  }
  else if (S.at(K-1) == 'B') {
    S.at(K-1) = 'b';
  }
  else if (S.at(K-1) == 'C') {
    S.at(K-1) = 'c';
  }
  
  cout << S << endl;
}



Measured memory_bytes: 256
#include <bits/stdc++.h>
     
    using namespace std;
     
    int main()
    {
    string s;
cin >> s;
    if (s.size() < 4)
    {
    cout << "No\n";
    return 0;
    }
    while (s.size( ) > 4) s.pop_back();
    cout << (s == "YAKI" ? "Yes" : "No") << '\n';
    }

Measured memory_bytes: 256
n = int(input())
X = [0]*n
for i in range(n):
    t = list(map(int, input().split()))
    X[i] = t


dp = [[0, 0, 0] for _ in range(n)]
dp[0] = X[0]


for i in range(1, n):
    dp[i][0] = max(dp[i-1][1]+X[i][0], dp[i-1][2]+X[i][0])
    dp[i][1] = max(dp[i-1][0]+X[i][1], dp[i-1][2]+X[i][1])
    dp[i][2] = max(dp[i-1][0]+X[i][2], dp[i-1][1]+X[i][2])

print(max(dp[-1]))


Measured memory_bytes: 50220
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <queue>
#include <map>
#include <cmath>
#include <numeric>
#include <iomanip>
#include <set>
#include <string.h>

using namespace std;

typedef long long ll;

#define REP(i,n) for(ll (i)=0;(i)<(n);(i)++)
#define REP3(i,st,en) for(ll (i)=(st);(i)<(en);(i)++)

using P = pair<ll, ll>;
const int MOD = 1e9+7;
const ll INF = 1e+14;
const double PI = 3.14159265349;



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

  ll N, M;
  cin >> N >> M;

  cout << ((N==M) ? "Yes" : "No") << "\n";
  return 0;
}


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

int main() {
	string s;
    cin >> s;
    int r=0;
    for(int i=0;i<s.size()-1;i++){
      if(s.at(i)=='A' && s.at(i+1)=='C'){
        r++;
        break;
      }
    }
    if(r==0){
      cout << "No" << endl;
    }
    else{
      cout << "Yes" << endl;
    }
}


Measured memory_bytes: 256
class UnionFindInt(size: Int) {

  private[this] val arr = new Array[Int](size + 1);

  def addPair(parent: Int, child: Int): Unit = {
    val pr = fetchRoot(parent);
    val cr = fetchRoot(child);
    if (pr != cr) {
      arr(cr) = pr;
    }
  }

  def fetchRoot(elem: Int): Int = {
    @scala.annotation.tailrec
    def sub(elem: Int, pendings: List[(Int, Int)]): Int = {
      val p = arr(elem);
      if (p == 0) {
        pendings.foreach { case (c, p) =>
          if (p != elem) {
            arr(c) = elem;
          }
        }
        elem;
      } else {
        sub(p, (elem, p) :: pendings);
      }
    }
    sub(elem, Nil);
  }

}

object Main extends App {
  val sc = new java.util.Scanner(System.in);
  val n, m = sc.nextInt();
  val ps = Array.fill(n)(sc.nextInt());
  val xys = Array.fill(m)((sc.nextInt(), sc.nextInt()));

  val unionFind = new UnionFindInt(n);
  xys.foreach { case (x, y) =>
    unionFind.addPair(y, x);
  }

  val answer = ps.zipWithIndex.count { case (p, i) =>
    unionFind.fetchRoot(p) == unionFind.fetchRoot(i + 1);
  }
  println(answer);
}

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

int main() {
	int a, b, c, d;

	cin >> a >> b >> c >> d;
	int ab = a * b;
	int cd = c * d;
	
	if (ab < cd) cout << cd << endl;
	if (ab > cd) cout << ab << endl;
	if (ab == cd) cout << ab << endl;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define fastio std::ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define fileIO freopen("input.txt", "r", stdin);freopen("output.txt", "w", stdout)
#define int long long int
#define F first
#define S second
#define pb push_back
#define M 1000000007
#define inf 1e18
#define endl "\n"
#define jam(x) cout<<"Case #"<<x<<": "
#define N 100005
void display2D( vector<vector<int> > &v ) {
	int n = v.size();
	int m = v[0].size();
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cout << v[i][j] << " ";
		}
		cout << endl;
	}
}

int32_t main() {
	fastio;
#ifndef ONLINE_JUDGE
	fileIO;
#endif

	int n, m;
	char temp;
	cin >> n >> m;
	std::vector < vector<int> > dp(n, vector<int>(m, -1));

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cin >> temp;
			if (temp == '#') dp[i][j] = 0;
		}
	}
	int filler = 1;
	for (int j = 0; j < m; j++) {
		if (dp[0][j] == 0) filler = 0;
		dp[0][j] = filler;
	}
	filler = 1;
	for (int i = 0; i < n; i++) {
		if (dp[i][0] == 0) filler = 0;
		dp[i][0] = filler;
	}



	for (int i = 1; i < n; i++) {
		for (int j = 1; j < m; j++) {
			if (dp[i][j] != 0) dp[i][j] = (dp[i - 1][j] % M + dp[i][j - 1] % M) % M;
		}
	}
	//display2D(dp);
	cout << dp[n - 1][m - 1] << endl;

	return 0;
}

Measured memory_bytes: 11124
main :: IO ()
main = do
  _ <- getLine
  a <- reads2List :: IO [Int]
  print $ solve a

solve :: [Int] -> Int
solve a = minimum $ fmap (\n -> abs (2 * n - la')) (init a') where
  a' = scanl1 (+) a
  la' = last a'


s2List :: Read a => String -> [a]
s2List = fmap read . words

reads2List :: Read a => IO [a]
reads2List = do
  s <- getLine
  return (s2List s)


Measured memory_bytes: 108924
#include <stdio.h>

int main(void)

{  

    char num[1001];  

    int i=0;  

    int sum=1;  

    while(sum!=0){  

     sum=0;  

     i=0;  

     scanf("%c",&num[i]);  

      while(num[i]!='\n'){   

      i++;   

      scanf("%c",&num[i]);  

     }  

     num[i]='\0';  

     i=0;  

     while(num[i]!='\0'){   

      sum+=num[i]-'0';   

      i++;  

     }  

     if(sum!=0){  

     printf("%d\n",sum);  

     }  

    }  

    return 0; 

}    

Measured memory_bytes: 536
import math
import decimal
n,k=list(map(int,input().split()))
#出た目がk以上 1
#k/2以上 1/2
#k/4以上 1/4
a=decimal.Decimal(0)

for i in range(n):
  if i>=k:
    a+=1
  else:
    a+=(decimal.Decimal(1/2)**abs(math.floor(math.log2((i+1)/k))))
print(a/n)

Measured memory_bytes: 5076
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
#define INF (1<<30)
#define INFLL (1ll<<60)
typedef pair<int, int> P;
typedef pair<int, P> E;
#define MOD (1000000007ll)
#define l_ength size

void mul_mod(ll& a, ll b){
	a *= b;
	a %= MOD;
}

void add_mod(ll& a, ll b){
	b += MOD;
	a += b;
	a %= MOD;
}

int n;
bool done[334][334][334];
double memo[334][334][334];

double solve(int i, int j, int k){
	if(done[i][j][k]){
		return memo[i][j][k];
	}
	if(i==0 && j==0 && k==0){
		return 0.0;
	}
	done[i][j][k] = true;
	memo[i][j][k] = ((double)(n))/((double)(i+j+k));
	if(i>0){
		memo[i][j][k] += ((double)(i))/((double)(i+j+k))*solve(i-1,j+1,k);
	}
	if(j>0){
		memo[i][j][k] += ((double)(j))/((double)(i+j+k))*solve(i,j-1,k+1);
	}
	if(k>0){
		memo[i][j][k] += ((double)(k))/((double)(i+j+k))*solve(i,j,k-1);
	}
	return memo[i][j][k];
}

int main(void){
	int i,a,c[3]={0,0,0};
	fill(done[0][0],done[334][0],false);
	cin >> n;
	for(i=0; i<n; ++i){
		cin >> a;
		++c[a-1];
	}
	printf("%.15lf\n",solve(c[2],c[1],c[0]));
	return 0;
}


Measured memory_bytes: 299008
import java.io.IOException;
import java.math.BigInteger;
import java.util.Arrays;
import java.util.Scanner;

public class Main {

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

		new Main().run();
	}

	private void run() throws IOException {
		Scanner scanner = new Scanner(System.in);
		String a = scanner.nextBigInteger().subtract(BigInteger.ONE).toString();
		String b = scanner.next();
		M = scanner.nextInt();
		
		System.out.println((slove(b) - slove(a) + mod) % mod);
	}

	private int slove(String s) {
		n = s.length();
		num = new int[n];
		for (int i = 0; i < n; i++)
			num[n - i - 1] = s.charAt(i) - '0';
		dp = new int[2][2][10][n][M];
		for (int[][][][] dp1 : dp)
			for (int[][][] dp2 : dp1)
				for (int[][] dp3 : dp2)
					for (int[] dp4 : dp3)
						Arrays.fill(dp4, -1);
		int res = 0;
		for (int i = n - 1; i >= 0; i--)
			for (int j = 1; j <= (i == n - 1 ? num[i] : 9); j++) {
				res = (res + slove(i, j % M, j, 1, i == n - 1 && j == num[i]))
						% mod;
				if (i != 0)
					res = (res + slove(i, j % M, j, 0, i == n - 1
							&& j == num[i]))
							% mod;

			}
		return res % mod;
	}

	private int slove(int p, int m, int pre, int s, boolean b) {
		if (p == 0)
			return m == 0 ? 1 : 0;
		if (dp[s][b ? 1 : 0][pre][p][m] != -1)
			return dp[s][b ? 1 : 0][pre][p][m];
		int ans = 0;

		if (s == 0) {
			int size = (b ? num[p - 1] : 9);
			for (int i = pre + 1; i <= size; i++)
				ans += slove(p - 1, (m * 10 + i) % M, i, 1, b
						&& i == num[p - 1]);
		} else {
			int size = Math.min(b ? num[p - 1] : 9, pre - 1);
			for (int i = 0; i <= size; i++)
				ans += slove(p - 1, (m * 10 + i) % M, i, 0, b
						&& i == num[p - 1]);
		}
		return dp[s][b ? 1 : 0][pre][p][m] = ans % mod;

	}

	int M, n;
	int mod = 10000;
	int[] num;
	int[][][][][] dp;
}

Measured memory_bytes: 137748
#include <bits/stdc++.h>
using namespace std;
 
#define rep(i, n) for (int i = (int)(0); i < (int)(n); ++i)
#define reps(i, n) for (int i = (int)(1); i <= (int)(n); ++i)
#define rrep(i, n) for (int i = ((int)(n)-1); i >= 0; i--)
#define rreps(i, n) for (int i = ((int)(n)); i > 0; i--)
#define irep(i, m, n) for (int i = (int)(m); i < (int)(n); ++i)
#define ireps(i, m, n) for (int i = (int)(m); i <= (int)(n); ++i)
#define FOR(e, c) for (auto &e : c)
#define SORT(v, n) sort(v, v + n);
#define vsort(v) sort(v.begin(), v.end());
#define rvisort(v) sort(v.begin(), v.end(), greater<int>());
#define all(v) v.begin(), v.end()
#define mp(n, m) make_pair(n, m);
#define cout(d) cout<<d<<endl;
#define coutd(d) cout<<std::setprecision(10)<<d<<endl;
#define cinline(n) getline(cin,n);
#define replace_all(s, b, a) replace(s.begin(),s.end(), b, a);
// #define int long long
#define PI (acos(-1))
#define FILL(v, n, x) fill(v, v + n, x);
 
using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using vll = vector<ll>;
using vvll = vector<vll>;
using pii = pair<int, int>;
using ul = unsigned long;
 
const int MOD = 1e9+7;
const int INF = 1e9;
const ll LINF = 1e18;
 
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; }
 
int GCD(int a, int b) { return b ? GCD(b, a%b) : a; }
int LCM(int a, int b) { return a * b / GCD(a, b); }
 
 
signed main()
{
  double a,b,x; cin>>a>>b>>x;
  
  if(2*x>=a*a*b){
    double v=a*a*b-x;
    double h=2*v/(a*a);
    double radian=atan2l(h,a);
    double degree = radian * 180.0 / PI;
    coutd(degree);
  }else{
    double h=2*x/(a*b);
    // cout<<h<<endl;
    double radian=atan2l(b,h);
    double degree = radian * 180.0 / PI;
    coutd(degree);
  }
  
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int>P;
const double eps = 1e-8;
const int NINF = 0xc0c0c0c0;
const int INF  = 0x3f3f3f3f;
const ll  mod  = 1e9 + 7;
const ll  maxn = 1e6 + 5;

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	ll a,b,c,k;
	cin>>a>>b>>c>>k;
	if(a>=k){
		cout<<k<<'\n';
	}else{
		if(a+b>=k) cout<<min(k,a)<<'\n';
		else{
			cout<<a-(k-a-b)<<'\n';
		}
	}
	return 0;
}

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

# define rep(i, n) for(int(i)=0;(i)<(n);(i)++)
# define reps(i, n) for(int(i)=1;(i)<=(n);(i)++)
# define rrep(i, n) for(int i=((int)(n)); i>0; --i)
# define rreps(i, n) for(int i=((int)(n)); i>=0; --i)
# define ALL(v) v.begin(), v.end()
template<class T>inline bool chmax(T &a, const T &b) { if (a<b) { a=b; return true; } return false; }
template<class T>inline bool chmin(T &a, const T &b) { if (b<a) { a=b; return true; } return false; }
template<typename T> void dump(T e){std::cout << e << std::endl;}
template<typename T> void dump(const std::vector<T>& v){for(const auto& e : v){ std::cout << e << " "; } std::cout << std::endl;}
template<typename T> void dump(const std::vector<std::vector<T> >& vv){ for(const auto& v : vv){ dump(v); } }
typedef long long ll;

int main() {
  ll N,C,K; cin >> N >> C >> K;
  vector<double> T(N); rep(i, N) cin >> T[i];
  sort(T.begin(), T.end());
  
  int ans=0;
  int people=0;
  int time=0;
  rep(i, N) {
    if(i==0) {
      time = T[i];
      people++;
      ans++;
    } else {
      if(T[i] <= time+K && people+1 <= C) {
        people++;
      } else {
        time = T[i];
        people = 1;
        ans++;
      }
    }
  }
  dump(ans);
}


Measured memory_bytes: 1024
#include <bits/stdc++.h>
#define ll long long
using namespace std;
struct state
{
	ll s;
	int v,len;
};
struct comp{
bool operator()(state a,state b)
{
	return a.len>b.len;
}};
priority_queue<state,vector<state>,comp> que;
int n,m,c[50],ans;
vector<int> G[50];
map<ll,int> d[50];
ll mask[50];
inline void add_edge(int f,int t)
{
	G[f].push_back(t);
	G[t].push_back(f);
}
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
	scanf("%d",&c[i]);
	for(int i=1,a,b;i<=m;i++)
	{
		scanf("%d%d",&a,&b);
		add_edge(a,b);
		mask[a]|=1LL<<b;
		mask[b]|=1LL<<a;
	}
	for(int i=1;i<=n;i++)
	{
		mask[i]|=1LL<<i;
		if(mask[1]&(1LL<<i)) ans+=c[i];
	}
	que.push((state){mask[1],1,ans});
	d[1][mask[1]]=ans;
	while(!que.empty())
	{
		state S=que.top(); que.pop();
		if(S.v==n) {printf("%d\n",S.len); return 0;}
		for(int i=0;i<G[S.v].size();i++)
		{
		    state New=(state){0,0,0};	
		    New.v=G[S.v][i];
			New.s=S.s|mask[New.v];
			for(int j=1;j<=n;j++)
			if(New.s&(1LL<<j)) New.len+=c[j];
			if(d[New.v].find(New.s)==d[New.v].end() || d[New.v][New.s]>New.len) que.push(New),d[New.v][New.s]=New.len;
		}
	 } 
	return 0;
}

Measured memory_bytes: 4316
#include <bits/stdc++.h>
using namespace std;
#define REP(i, a, b) for (int i = (int)(a); i < (int)(b); i++)
#define rep(i, n) REP(i, 0, n)
#define rrep(i, n) for (int i = (int)(n-1); i >= 0; i--)
#define sz(x) int(x.size())
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define INF 2e9
#define LINF 1e18
template<class T> inline bool chmax(T &a, const T &b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T &a, const T &b) { if (a > b) { a = b; return 1; } return 0; }
typedef long long ll;
typedef pair<int, int> P;

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

int main() {
    int a, b, c, x, y; cin >> a >> b >> c >> x >> y;
    int ans = 0;
    if (a+b <= 2*c) {
        ans = a*x + b*y;
        cout << ans << endl;
    }
    else {
        while (x>0 && y>0) {
            ans += 2*c;
            x--; y--;
        }
        if (x+y == 0) {
            cout << ans << endl;
        }
        else {
            if (x > 0) {
                if (a <= 2*c) ans += x*a;
                else ans += 2*x*c;
            }
            else {
                if (b <= 2*c) ans += y*b;
                else ans += 2*y*c;
            }
            cout << ans << endl;
        }
    }
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <sstream>
#include <iomanip> 
#include <math.h>
#include <stdio.h>
#include <string.h>
#include <queue>
#include <stack>
#include <vector>
#include <map>
#include <set>
#include <functional>
#include <algorithm>
#include <unordered_map>
#include <unordered_set>
#include <bitset>

using namespace std;


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

	int a, b, c, d, e, k;
	cin >> a >> b >> c >> d >> e >> k;
	if (e - a > k) cout << ":(\n";
	else cout << "Yay!\n";

	return 0;
}

Measured memory_bytes: 256
# -*- coding: utf-8 -*-
size ,times = map(int, input().split())
road = [0 for i in range(size)]

for i in range(times):
    t1,t2 = map(int,input().split())
    road[t1-1] += 1
    road[t2-1] += 1

for i in range(size):
    print(road[i])


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

int main(void){
    int a, b, c, d;
    scanf("%d", &a);
    if(1>a || a>100){
        while(1>a || a>100){
            scanf("%d",&a);
        }
    }
    scanf("%d", &b);
    if(1>b || b>100){
        while(1>b || b>100){
            scanf("%d",&b);
        }
    }
    scanf("%d", &c);
    if(1>c || c>100){
        while(1>c || c>100){
            scanf("%d",&c);
        }
    }
    scanf("%d", &d);
    if(1>d || d>100){
        while(1>d || d>100){
            scanf("%d",&d);
        }
    }
    while(a>0 && c>0){
        c=c-b;
        if(c>0){
            a=a-d;
        }
    }
    if(a<=0){
        printf("No\n");
    }
    if(c<=0){
        printf("Yes\n");
    }
}


Measured memory_bytes: 1616
import java.util.*;
class Main{

     public static void main(String []args){
      Scanner scan = new Scanner(System.in);
      int n = scan.nextInt() ;
      char arr[] = new char[n] ; 
      ArrayList<Character> a = new ArrayList<Character>();
      for(int i = 0; i<n ; i++){
          arr[i] = scan.next().charAt(0);
          if(!a.contains(arr[i])){
              a.add(arr[i]) ;
          }
      }
      System.out.println(a.size()==4 ? "Four":"Three") ;
    }
}

Measured memory_bytes: 22868
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>

const int MAX = 1e9+5;

int main()
{
    int n, k;
    scanf("%d%d" ,&n, &k);
    std::vector<int>a(n), dp(n, MAX);
    dp[0]=0;
    for(int& i: a){
        scanf("%d", &i);
    }
    
    for(int i=0 ; i<n; i++){
        for(int j=i+1; j<=i+k; j++){
            if(j<n){
                dp[j] = std::min(dp[j], dp[i]+std::abs(a[i]-a[j]));    
            }
            
        }
    }
    printf("%d\n", dp[n-1]);

    return 0;
}





Measured memory_bytes: 1024