akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define rep(i,n)  FOR(i,0,n)
#define req(i,n) for(int i = 1;i <=n;i++)
#define pai 3.14159265358979323846
const int INF = 1001001001;
typedef long long ll;
int A[3][3], N;
bool punched[3][3];
bool ok[3][3];
using Graph = vector<vector<int>>;
vector<vector<int>> field;
vector<bool> seen;

const int MOD = 1000000007;
typedef pair<int,int> P;

//最大公約数
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 /gcd(a,b) * b;
}

//素数判定
bool is_prime(long long N) {
    if (N == 1) return false;
    for (long long i = 2; i * i <= N; ++i) {
        if (N % i == 0) return false;
    }
    return true;
}



  








int main() {
  int n,m,k;
  cin >> n >> m >> k;
  vector<int> a(n);
  vector<int> b(m);
  rep (i,n) cin >> a[i];
  rep (i,m) cin >> b[i];

  ll t=0;
  rep (i,m) t += b[i];

  int j = m;
  int ans = 0;
  rep (i,n+1){
    while (t > k && j > 0){
      --j;
      t -= b[j];
    }
    if (t > k) break;
    ans = max (ans,i+j);
    if (i==n) break;
    t += a[i];
  }
  cout << ans << endl;
  
}

Measured memory_bytes: 4844
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#include <stack>
#include <cmath>
#define ll long long
#define out(a) printf("%d",a)
using namespace std;
int n,m,l;
int read()
{
	int s=0,t=1; char c;
	while (c<'0'||c>'9') {if (c=='-') t=-1; c=getchar();}
	while (c>='0'&&c<='9') {s=s*10+c-'0'; c=getchar();}
	return s*t;
}
int main()
{
	n=read(); m=read(); l=1;
	for (int i=1;i<=m;i++)
	  l*=2;
	out(l*(100*(n-m)+1900*m));
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <string>
#define flush fflush(stdout)
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
typedef pair<ll, int> Pl;
const int mod = (int)1e9 + 7, INF = (int)1e9;
const int di[4] = { 1,0,-1,0 }, dj[4] = { 0,1,0,-1 };


int main(void) {
    int n, i, j, dp[3003][3003] = {}, ps;
    string s;

    scanf("%d", &n);
    cin >> s;

    for (j = 0; j < n; j++) {
        dp[0][j] = 1;
    }

    for (i = 0; i < n - 1; i++) {
        if (s[i] == '<') {
            ps = 0;
            for (j = 0; j < n - i - 1; j++) {
                ps = (ps + dp[i][j]) % mod;
                dp[i + 1][j] = ps;
            }
        }
        else {
            ps = 0;
            for (j = n - 1; j >= 0; j--) {
                dp[i + 1][j] = ps;
                ps = (ps + dp[i][j]) % mod;
            }
        }
    }

    printf("%d\n", dp[n - 1][0]);

    return 0;
}

Measured memory_bytes: 35456
#include <iostream>
#include <algorithm>
#include <cmath>
#include <complex>
#include <cstdio>

using namespace std;

int main(){

	int n;
	cin >> n;
	for(int i = 0; i < n; i++){
		complex<double> A,B,C;
		cin >> A.real() >> A.imag() >> B.real() >> B.imag() >> C.real() >> C.imag();
		double b = abs(A-C);
		double a = abs(B-C);
		double c = abs(A-B);
		double s = (a+b+c)/2;
		double S = sqrt(s*(s-a)*(s-b)*(s-c));
		double R = a*b*c/(4*S);
		complex<double> cent;

		cent.real() = (a*a*(b*b+c*c-a*a)*A.real() + b*b*(a*a+c*c-b*b)*B.real() + c*c*(b*b+a*a-c*c)*C.real())/(16*S*S);
		cent.imag() = (a*a*(b*b+c*c-a*a)*A.imag() + b*b*(a*a+c*c-b*b)*B.imag() + c*c*(b*b+a*a-c*c)*C.imag())/(16*S*S);

		printf("%.3f %.3f %.3f\n",cent.real(),cent.imag(),R);
		//cout << cent.real() << " " << cent.imag() << " " << R << endl;
		//double cosA = (b*b+c*c-a*a)/(2*b*c);
		//double sinA = sqrt(1-cosA*cosA);
		//double R = a/(2*sinA);

	}

	return 0;
}

Measured memory_bytes: 0
<?php
// $n = (int)trim(fgets(STDIN));
$input = explode(' ', trim(fgets(STDIN)));

$a = (int)$input[0];
$b = (int)$input[1];
$large = max($a, $b);
$small = min($a, $b);

// 最大公約数
$gcd = gcd($large, $small);
$ps = primefactors($gcd);
echo count($ps);

function gcd($large, $small){
	while($small !== 0){
		$tmp_n = $small;
		$small = $large % $small;
		$large = $tmp_n;
	}
	return $large;
}
// 素因数分解
function primefactors($n){
	$result = [1 => 1];
	while ($n % 2 === 0) {
		$n = (int)floor($n/2);
		if (isset($result[2])) {
			$result[2] += 1;
		}else{
			$result[2] = 1;
		}
	}
	for ($i=3; $i*$i <= $n; $i+=2) { 
		while ($n % $i === 0) {
			$n = (int)floor($n/$i);
			if (isset($result[$i])) {
				$result[$i] += 1;
			}else{
				$result[$i] = 1;
			}
		}
	}
	if ($n > 2) {
		$result[$n] = 1;
	}
	return $result;
}
// 素数判定
// function sieve($n){
// 	$list = range(2, $n);
// 	$result = [1];
// 	for ($i=1; $i < $n; $i++) { 
// 		// echo implode(' ', $list) , PHP_EOL;
// 		$tmp_list = [];
// 		$target = array_shift($list);
// 		if (empty($target)) {
// 			break;
// 		}
// 		$result[] = $target;
// 		foreach ($list as $v) {
// 			if ($v % $target !== 0) {
// 				$tmp_list[] = $v;
// 			}
// 		}
// 		$list = $tmp_list;
// 	}
// 	return $result;
// }


Measured memory_bytes: 4604
#include <bits/stdc++.h>
#define fast_io()                \
    ios::sync_with_stdio(false); \
    std::cin.tie(0);
typedef long long ll;
typedef long double ld;
using namespace std;

int main() {
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < max(n, m); i++) {
        cout << min(n, m);
    }

    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < n; i++)
#define rrep(i, n) for (int i = n - 1; i >= 0; i--)
using namespace std;
#define INF ((1<<30)-1)
#define LINF (1LL<<60)
#define EPS (1e-10)
typedef long long ll;
typedef pair<ll, ll> P;
const int MOD = 1000000007;
const int MOD2 = 998244353;

ll dp[1<<13]; // 状態sに到達する最小のコスト
int a[1010], b[1010];
int c[1010][15];

int main(){
    int n, m;
    cin >> n >> m;
    rep(i, m){
        cin >> a[i] >> b[i];
        rep(j, b[i]) cin >> c[i][j];
    }

    rep(i, 1<<13) dp[i] = LINF;
    dp[0] = 0;

    rep(i, m){
        int now = 0;
        rep(j, b[i]) now |= (1<<(c[i][j]-1)); 
        rep(bits, 1<<n){
            dp[bits|now] = min(dp[bits|now], dp[bits] + a[i]);
        }
    }

    if (dp[(1<<n)-1] == LINF) cout << -1 << endl;
    else cout << dp[(1<<n)-1] << endl;

    return 0;
}


Measured memory_bytes: 3696
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<string>
#include<vector>
#include<stack>
#include<bitset>
#include<cstdlib>
#include<cmath>
#include<set>
#include<list>
#include<deque>
#include<map>
#include<queue>
using namespace std;
typedef long long ll;

int main()
{
    int a,b,c,x;
    while(~scanf("%d %d %d %d",&a,&b,&c,&x))
    {
        int sum=0;
        for(int i=0;i<=a;i++)
        {
            for(int j=0;j<=b;j++)
            {
                for(int k=0;k<=c;k++)
                {
                    if(i*500+j*100+k*50==x)
                        sum++;
                }
            }
        }
        printf("%d\n",sum);
    }
    return 0;
}


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

int main(){
  int a,b;cin >> a >>b;
  if((a*b)%2==0)cout << "Even";
  else cout << "Odd";
}

Measured memory_bytes: 256
#include <stdio.h>

int main() {
	int Zx, Xz, dup = 1;
	scanf("%d", &Zx);
	scanf("%d", &Xz);
	for (int o = 0; o < Zx; o++) {
		if (dup < Xz) {
			dup *= 2;
		} else {
			dup += Xz;
		}
	}
	printf("%d", dup);
	return 0;
}

Measured memory_bytes: 1704
#include <bits/stdc++.h>
using namespace std;
#define int long long 
#define dd double
#define pb              push_back
#define mp              make_pair
#define pii             pair<int,int>
#define vi              vector<int>
#define mii             map<int,int>
#define pqb             priority_queue<int>
#define pqs             priority_queue<int,vi,greater<int> >
#define setbits(x)      __builtin_popcountll(x)
#define zrobits(x)      __builtin_ctzll(x)
#define mod 1000000007
#define tc(t) 			int t;cin >> t;while(t--)
#define for0(i , n)		for(int i=0;i<n;i++)
#define loop(i , a, b)	for(int i=a;i<=b;i++)
#define endl '\n'

int n;
dd a[3000];
vector<vector<dd>> dp(3000,vector<dd>(3000,-1));

dd coins(int ind,int H){
	if(ind == n){
		if(H>(n-H)) 
			return 1.0;
		else
			return 0.0;
	}

	if(dp[ind][H]!=-1) return dp[ind][H];

	dd sum = (1.0*a[ind]*coins(ind+1,H+1)) + (1.0-a[ind])*coins(ind+1,H);
	return dp[ind][H]=sum;
}


signed main() {

	ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
#ifndef ONLINE_JUDGE
	freopen("input.txt" , "r" , stdin);
	freopen("output.txt" , "w" , stdout);
#endif

	cin >> n;

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

	cout << setprecision(10) << coins(0,0) << endl;

	return 0;
}

Measured memory_bytes: 74500
#include<iostream>
#include<algorithm>
#include<cmath>
#include<map>
#include<stdio.h>
#include<vector>
using namespace std;
#define rep(s,i,n) for(int i=s;i<n;i++)
#define c(n) cout<<n<<endl;
#define ic(n) int n;cin>>n;
#define sc(s) string s;cin>>s;
#define mod 1000000007
#define f first
#define s second
#define int long long
int a[114514];
int ans[114514];
bool p(int x){
	if(x==1)return false;
	rep(2,i,x){
		if(x%i==0)return false;
	}
	return true;
}		
signed main(){
	sc(s) sc(t)
	cout<<t<<s<<endl;
}	

Measured memory_bytes: 256
import java.util.Scanner;
import java.util.Stack;

public class Main {

    static class Pair
    {
        int key;
        int value;

        public Pair(int key, int value) {
            this.key = key;
            this.value = value;
        }

        public int getKey() {
            return key;
        }

        public int getValue() {
            return value;
        }
    }


    public static void main(String[] args) {

        int sum = 0;
        Scanner sc = new Scanner(System.in);
        String s = sc.next();
        Stack<Integer> s1 = new Stack<Integer>();
        Stack<Integer> s3 = new Stack<Integer>();
        Stack<Pair> s2 = new Stack<Pair>();
        char[] ss = new char[s.length()];
        s.getChars(0,s.length(),ss,0);

        for(int i = 0;i < ss.length;i++)
        {
            if('\\' == ss[i])
            {
                s1.push(i);
            }
            else if('/' == ss[i] && s1.size() > 0)
            {
                int j = s1.pop();
                int tmp = i - j;
                sum += tmp;
                while(s2.size() > 0 && s2.peek().getKey() > j )
                {
                    tmp += s2.peek().getValue();
                    s2.pop();
                }
                s2.push(new Pair(j,tmp));
            }
        }

        System.out.println(sum);
        while(!s2.isEmpty())
        {
            s3.push(s2.pop().getValue());
        }
        System.out.print(s3.size());
        while (!s3.isEmpty())
        {
            System.out.print(" " + s3.pop());
        }
        System.out.println();
    }
}



Measured memory_bytes: 28624
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define REP(i, n) for (int i = 0; i < (int)(n); i++)
#define ALL(x) (x).begin(), (x).end()


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

    int N;
    cin >> N;
    vector<pair<int, int>> ranges(N);
    REP(i, N) {
        int X, L;
        cin >> X >> L;
        ranges[i] = make_pair(X+L, X-L);
    }
    sort(ALL(ranges));
    int ans = 0;
    int x = -1e9;
    for (auto& range : ranges) {
        if (x <= range.second) {
            ans++;
            x = range.first;
        }
    }
    cout << ans << endl;
}

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

using namespace std;

#define forn for (ll i = 0; i < n; i++)
#define form for (ll j = 0; j < m; j++)
#define NO cout << "NO\n";
#define YES cout << "YES\n";
#define pb push_back
#define mp make_pair
#define rep(i,a,b) for (ll i = a; i < b; i++)

typedef long long ll;
typedef vector<ll> vi;
typedef pair<ll, ll> pi;

ll gcd(ll a, ll b){
    ll r;
    while (b != 0){
        r = a % b;
        a = b;
        b = r;
    }
    return a;
}


ll *calc_z(string s){
    ll n = s.size();
    ll *z = new ll[n] {0};
    ll l = 0, r = 0;
    for (ll i = 1; i < n; i++){
        if (r >= i) z[i] = min(z[i-l], r-i+1);
        while (z[i]+i < n && s[z[i]] == s[z[i]+i]) z[i]++;
        if (i + z[i] - 1 > r){
            l = i;
            r = i+z[i]-1;
        }
    }
    return z;
}

ll find_lower(ll *a, ll n, ll v){
    ll l = -1, r = n;

    while (r>l+1){
        ll m = (l+r)/2;

        if (a[m] >= v) r = m;
        else l = m;
    }
    if (r == n) return n-1;
    if (a[r] == v) return r;
    return r == 0 ? 0 : r-1;
}

void solve(){
    string s, t;
    cin >> s >> t;
    int n = s.size();
    ll ans = 0;
    for (int i = 0; i < n; i++){
        if (s[i] != t[i]) ans++;
    }
    cout << ans << "\n";
}

int main(){
    //init();

    ios::sync_with_stdio(0);
    cin.tie(0);

    //ll t; cin >> t; while (t--)
        solve();
    return 0;
}


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

int main(int argc, const char * argv[]) {
    // insert code here...
    int W, H, N;
    cin >> W >> H >> N;
    
    vector<int> x(N);
    vector<int> y(N);
    vector<int> a(N);
    for (int i = 0; i < N; i++) cin >> x.at(i) >> y.at(i) >> a.at(i);
    
    int left = 0, right = W, top = H, buttom = 0;
    for (int i = 0; i < N; i++) {
        if (a.at(i) == 1) left = max(left, x.at(i));
        else if (a.at(i) == 2) right = min(right, x.at(i));
        else if (a.at(i) == 3) buttom = max(buttom, y.at(i));
        else top = min(top, y.at(i));
    }
    
    cout << max(0, (right - left)) * max(0, (top - buttom)) << endl;
    //cout << (right - left) * (top - buttom) << endl;
    
    return 0;
}


Measured memory_bytes: 256
n = int(input())
top = list(map(int,input().split()))
bottom = list(map(int,input().split()))

sl = [0 for _ in range(n)]
sr = [0 for _ in range(n)]

for i in range(n):
    sl[i] =sum(top[:i+1])
    sr[i] =sum(bottom[i:])

ans = 0

for i in range(n):
    ans = max(ans,sl[i]+sr[i])
print(ans)

Measured memory_bytes: 3064
#include <iostream>
#include <vector>
#include <string>
#include <map>

int main()
{
  int N;
  std::cin >> N;
  std::vector<std::string> W(N);
  std::map<std::string, int> check;
  char pre_char = '#';
  bool is_NG = false;
  for (int i = 0; i < N; i++)
  {
    std::cin >> W.at(i);
    if (pre_char == '#')
      pre_char = W.at(i)[W.at(i).size()-1];
    else if (pre_char == W.at(i)[0])
      pre_char = W.at(i)[W.at(i).size()-1];
    else
      is_NG = true;
    if (check.count(W.at(i)))
      is_NG = true;
    else
      check[W.at(i)] = 0;
    if (is_NG) break;
  }
  if (is_NG) std::cout << "No" << std::endl;
  else std::cout << "Yes" << std::endl;

}


Measured memory_bytes: 256
N = int(input())
MOD = 10 ** 9 + 7
memo = [{} for _ in range(101)]

def ok(last4):
    for i in range(4):
        t = list(last4)
        if i >= 1:
            t[i-1], t[i] = t[i], t[i-1]
        if ''.join(t).find('AGC') != -1:
            return False
    return True

def dfs(cur, last3):
    if last3 in memo[cur]:
        return memo[cur][last3]
    if cur == N:
        return 1
    ret = 0
    for c in 'AGCT':
        if ok(last3 + c):
            
            ret = (ret + dfs(cur+1, last3[1:] + c)) % MOD
    memo[cur][last3] = ret
    return ret

print(dfs(0, 'TTT'))

Measured memory_bytes: 48092
#include<bits/stdc++.h>
#define all(x) (x).begin(),(x).end()
#define deb(x) cout<<#x<<" is "<<x<<endl;
typedef long long ll;
using namespace std;
int main()
{
    string s,t;
    cin>>s>>t;
    int m=s.size(),n=t.size();
    //dp[i][j] is longest common subsequence for strings ending at s[0...i-1],t[0...j-1]
    int dp[m+1][n+1];

    for(int i=0;i<=m;i++)
    {
        for(int j=0;j<=n;j++)
        {
            if(i==0 || j==0)
                dp[i][j]=0;
            else if(s[i-1]==t[j-1])
                dp[i][j]=dp[i-1][j-1]+1;
            else
                dp[i][j]=max(dp[i][j-1],dp[i-1][j]);

            // cout<<i<<" "<<j<<" "<<dp[i][j]<<endl;
        }
    }

    // cout<<dp[m][n]<<endl;

    if(dp[m][n]==0)
    {
        cout<<" "<<endl;
        return 0;
    }

    int i=m,j=n;
    string ans="";
    while(i>0 && j>0)
    {
        if(s[i-1]==t[j-1])
        {
            ans=ans+s[i-1];
            i--;
            j--;
        }
        else if(dp[i][j-1] > dp[i-1][j])
            j--;
        else
            i--;
    }
    reverse(ans.begin(),ans.end());
    cout<<ans<<endl;
}


Measured memory_bytes: 38792
#include<iostream>
#include<algorithm>
#include<vector>
#include<map>
#include<string>
#define rep(i,N) for(int i=0;i<N;i++)

long long  INF=1000000000000000000;
long long mod=1000000007;
using namespace std;
long long a[51]={};


long long eat_patty(int N,long long x){
    long long ans;
    int n=N;
    if(N==0){
        if(x>0)return 1;
        else return 0;
    }
    if(x==1){
        return 0;
    }
    if(x<=1+a[N-1]){
        return eat_patty(N-1,x-1);
    }
    if(x==2+a[N-1]){
        return eat_patty(N-1,x-2)+1;
    }
    if(x<=2+2*a[N-1]){
        return eat_patty(N-1,a[N-1])+1+eat_patty(N-1,x-2-a[N-1]);
    }
    if(x==3+2*a[N-1]){
        return 2*eat_patty(N-1,a[N-1])+1;
    }
    return ans;
}


int main(){
int N;
long long X;
cin>>N>>X;
a[0]=1;
for(int i=1;i<=50;i++){
    a[i]=2*a[i-1]+3;
}
cout<<eat_patty(N,X);
 return 0;
}
/*
2 7

4

1 1

0


50 4321098765432109

2160549382716056

*/

Measured memory_bytes: 256
"""
# 標準入力取得
## 文字列
 = sys.stdin.readline().rstrip()
 = list(sys.stdin.readline().rstrip())

## 数値
 = int(sys.stdin.readline())
 = map(int, sys.stdin.readline().split())
 = list(map(int, sys.stdin.readline().split()))
 = [list(map(int,list(sys.stdin.readline().split()))) for i in range(h)]  # 二次元配列入力　二次元マップみたいな入力のとき

# 0埋め, 小数点出力桁指定時のときの出力
a = 100
b = 0.987654321
print("{0:06d}-{1:6f}".format(a,b))
000100-0.987654

# 文字列をリストに格納
char_list = list("abcd") # ["a","b","c","d"]
"""

import math
import sys
import itertools
import queue
from fractions import gcd

def lcm(a, b):
    return a * b // gcd(a, b)

mod = 1000000007

if __name__ == "__main__":
    n = int(sys.stdin.readline())
    a = list(map(int, sys.stdin.readline().split()))
    c=1
    for i in range(1,n):
        if a[i] is max(a[:i+1]):
            c+=1
    print(c)

Measured memory_bytes: 5072
#E

N=int(input())
a=list(map(int,input().split()))
b=[0]*N
for i in range(N-1):
    b[i]=a[i]^a[i+1]
b[-1]=a[-1]^a[0]
#print("b:",b)

ans=[0]*N
for i in range(1,N):
    ans[0] ^=a[i]
for i in range(1,N):
    ans[i]= ans[i-1]^b[i-1]

print(*ans)

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

int n, d;
int ans[15] = {0};
int p[15][15] = {0};
int dp[15][15][100005] = {0};

void solve();

int main() {
  int i, j;
  cin >> n >> d >> ans[0];
  for(i = 0; i < d; ++i)
    for(j = 0; j < n; ++j) cin >> p[i][j];
  for(i = 0; i < d; ++i) p[i][n] = 1;
  ++n;
  for(i = 0; i < d; ++i) ans[i] = ans[0];
  solve();
  cout << ans[d - 1] << endl;
  return 0;
}

void solve() {
  int i, j, k;
  for(i = 0; i < d - 1; ++i) {
    for(j = 0; j < n; ++j) {
      for(k = 0; k <= ans[i]; ++k) {
        if(j != 0) dp[i][j][k] = dp[i][j - 1][k];
        if(p[i][j] <= k)
          dp[i][j][k] =
              max(dp[i][j][k],
                  dp[i][j][k - p[i][j]] + p[i + 1][j]);
        ans[i + 1] = max(ans[i + 1], dp[i][j][k]);
      }
    }
  }
}


Measured memory_bytes: 5056
#include <iostream>

using namespace std;

int digits_sum(int num) {
    int digit, sum = 0, base = 1000;
    
    while(base != 0) {
        digit = num / base;
        sum += digit;
        num -= base * digit;
        base /= 10;
    }
    
    return sum;
}

int main() {
    int n, res, cnt;
    
    while(cin >> n) {
        cnt = 0;
        
        for(int i = 0;i < 10000;i++) {
            res = digits_sum(i);
            
            if(res == n) {
                cnt++;
            }
        }
        
        cout << cnt << endl;
    }
    
    return 0;
}


Measured memory_bytes: 3088
#include <iostream>
#include <vector>
#include <algorithm>

typedef long long ll;
using namespace std;

int main()
{
    int N, M;
    cin >> N >> M;
    int P[100001], Y[100001];
    vector<int> list[100001];
    for (int i = 0; i < M; i++)
    {
        cin >> P[i] >> Y[i];
        list[P[i]].push_back(Y[i]);
    }
    for (int i = 0; i < N; i++)
    {
        sort(list[i + 1].begin(), list[i + 1].end());
    }
    int temp;
    for (int i = 0; i < M; i++)
    {
        // イテレータから添え字に変換する方法
        temp = int(lower_bound(list[P[i]].begin(), list[P[i]].end(), Y[i]) - list[P[i]].begin()) + 1;
        printf("%012lld\n", 1000000 * ll(P[i]) + temp);
    }
    // cin >> N;
}

Measured memory_bytes: 7808
n, q = map(int, input().split())

p = [i for i in range(n)]
rank = [0 for i in range(n)]
diff_weight = [0 for i in range(n)]


def link(x, y, z):
 if rank[x] > rank[y]:
  p[y] = x
  diff_weight[y] = z
 else:
  p[x] = y
  diff_weight[x] = -z
  if rank[x] == rank[y]:
   rank[y] = rank[y] + 1

def findSet(x):
 if x != p[x]:
  parent = p[x]
  p[x] = findSet(p[x])
  diff_weight[x] += diff_weight[parent]
 return p[x]


def relate(x, y, z):
 rootx = findSet(x)
 rooty = findSet(y)
 z += diff_weight[x]
 z -= diff_weight[y]
 if rootx != rooty:
  link(rootx, rooty, z)


def same(x, y):
 x = findSet(x)
 y = findSet(y)

 if x == y:
  return 1
 else :
  return 0

def weight(x):
 findSet(x)
 return diff_weight[x]

def diff(x, y):
 if same(x, y) != 1:
  return '?'
 else :
  return diff_weight[y] - diff_weight[x]


output = []

for i in range(q):
 #print(p)
 #print(rank)
 #print(diff_weight)
 line = list(map(int, input().split()))

 if line[0] == 0:
  relate(line[1], line[2], line[3])

 else :
  output.append(diff(line[1],line[2]))
  #print(diff(line[1],line[2]))


for ans in output:
 print(ans)


Measured memory_bytes: 15252
n = int(input())
for i in range(1, n+1):
    if i % 3 == 0:
        print(f" {i}", end="")
    else:
        x = i
        while x:
            if x % 10 == 3:
                print(f" {i}", end="")
                break
            x = x // 10
print()


Measured memory_bytes: 5880
#include <bits/stdc++.h>
template<class T> inline bool chmin(T&a, T b){if(a > b){a = b; return true;}else{return false;}}
template<class T> inline bool chmax(T&a, T b){if(a < b){a = b; return true;}else{return false;}}
#define ll long long
#define double long double
#define rep(i,n) for(int i=0;i<(n);i++)
#define REP(i,n) for(int i=1;i<=(n);i++)
#define mod (ll)(1e9+7)
#define inf (ll)(3e18+7)
#define pi (double) acos(-1.0)
#define P pair<int,int>
#define PiP pair<ll,pair<ll,ll>>
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
using namespace std;

class UnionFind {
public:
	vector < ll > par;
	vector < ll > siz;
	UnionFind(ll sz_) : par(sz_), siz(sz_, 1) {
		for (ll i = 0; i < sz_; ++i) par[i] = i;
	}
	void init(ll sz_) {
		par.resize(sz_);
		siz.assign(sz_, 1);
		for (ll i = 0; i < sz_; ++i) par[i] = i;
	}
	ll root(ll x) {
		while (par[x] != x) {
			x = par[x] = par[par[x]];
		}
		return x;
	}
	bool unite(ll x, ll y) {
		x = root(x);
		y = root(y);
		if (x == y) return false;
		if (siz[x] < siz[y]) swap(x, y);
		siz[x] += siz[y];
		par[y] = x;
		return true;
	}
	bool same(ll x, ll y) {
		return root(x) == root(y);
	}
	ll size(ll x) {
		return siz[root(x)];
	}
};
 
int main(){
    int n, m;
    cin >> n >> m;
    UnionFind uf(n);
    rep(i, m){
        int a, b;
        cin >> a >> b;
        uf.unite(a-1, b-1);
    }
    ll ans = 0;
    rep(i, n)chmax(ans, uf.size(i));
    cout << ans << endl;
} 


Measured memory_bytes: 6424
#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
typedef long long ll;
ll inf = 100000000;
typedef pair<ll, ll> P;
int dx[4] = { 1,-1,0,0 };
int dy[4] = { 0,0,1,-1 };
int main() {
	int n;
	cin >> n;
	if (n % 2 == 1) {
		cout << n / 2 + 1 << endl;
		return 0;
	}
	cout << n / 2 << endl;
	return 0;
}

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

ll gcd(ll a,ll b){
    if(b>a) swap(a,b);
    ll r=a%b;
    while(r!=0){
        a=b;
        b=r;
        r=a%b;
    }
    return b;
}

int main (){
    string s;
    cin >> s;
    if(s[2]==s[3]){
        if(s[4]==s[5])
        {
            cout << "Yes" <<endl;
            return 0;
        }
    }
    cout << "No" <<endl;
    return 0;
}


Measured memory_bytes: 256
#include <cstdio>
#include <algorithm>
using namespace std;
long long N,D;
int main(){
  	scanf("%lld%lld",&N,&D);D = D*D;
	int ans = 0;	
  for(int i = 1;i <= N;i++){
    	long long x,y;
  		  scanf("%lld%lld",&x,&y);
    	if(x * x + y * y <= D)ans++;
  }
  printf("%lld\n",ans);
  return 0;
}

Measured memory_bytes: 1736
#include<iostream>
using namespace std;
int z[1000][7][7][7], n, m, p;
int a[27], b[27];
int getsum(int t, int i, int j, int k) {
	int S = 0;
	for (int I = -1; I <= 1; I++) {
		for (int J = -1; J <= 1; J++) {
			for (int K = -1; K <= 1; K++) {
				S += z[t][i + I][j + J][k + K];
			}
		}
	}
	return S - z[t][i][j][k];
}
int main() {
	int cnt = 0;
	while (true) {
		for (int i = 0; i < 1000; i++) {
			for (int j = 0; j < 7; j++) {
				for (int k = 0; k < 7; k++) {
					for (int l = 0; l < 7; l++) {
						z[i][j][k][l] = 0;
					}
				}
			}
		}
		for (int i = 0; i < 27; i++) {
			a[i] = 0; b[i] = 0;
		}
		cin >> n; cnt++; if (n == 0)break;
		if (cnt >= 2)cout << endl;
		for (int i = 1; i <= 5; i++) {
			for (int j = 1; j <= 5; j++) {
				for (int k = 1; k <= 5; k++) {
					char c; cin >> c;
					if (c == '0')z[0][i][j][k] = 0;
					if(c == '1')z[0][i][j][k] = 1;
				}
			}
		}
		cin >> m;
		for (int i = 0; i < m; i++) { cin >> p; a[p] = 1; }
		cin >> m;
		for (int i = 0; i < m; i++) { cin >> p; b[p] = 1; }
		for (int i = 0; i < n; i++) {
			for (int j = 1; j <= 5; j++) {
				for (int k = 1; k <= 5; k++) {
					for (int l = 1; l <= 5; l++) {
						int G = getsum(i, j, k, l);
						if (z[i][j][k][l] == 0 && a[G] == 1) {
							z[i + 1][j][k][l] = 1;
						}
						else if (z[i][j][k][l] == 1 && b[G] == 0) {
							z[i + 1][j][k][l] = 0;
						}
						else { z[i + 1][j][k][l] = z[i][j][k][l]; }
					}
				}
			}
		}
		cout << "Case " << cnt << ':' << endl;
		for (int i = 1; i <= 5; i++) {
			for (int j = 1; j <= 5; j++) {
				for (int k = 1; k <= 5; k++) {
					cout << z[n][i][j][k];
				}
				cout << endl;
			}
			if (i <= 4) { cout << endl; }
		}
	}
	return 0;
}

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

typedef long long int LLI;

int N;
int A[110];

int main() {
  scanf("%d", &N);
  LLI tot = 1;
  LLI sub = 1;
  for (int i=0; i<N; i++) {
    scanf("%d", &A[i]);
    tot *= 3;
    if (A[i]%2 == 0) sub *= 2;
    else sub *= 1;
  }
  
  printf("%lld\n", tot-sub);
}



Measured memory_bytes: 256
#include <iostream>
#include <sstream>
#include <cstdlib>
#include <cmath>
#include <map>
#include <set>
#include <queue>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <cstdio>
#include <numeric>
#include <bitset>
#include <stack>
using namespace std;

class Point
{
public:
  int x, y;
  Point(int _x = 0, int _y = 0)
    :x(_x), y(_y) {}
};

class State
{
public:
  int jewel, num, cost;
  State(int _jewel, int _num, int _cost)
    :jewel(_jewel), num(_num), cost(_cost) {}
  bool operator < (const State& st) const
  {
    return this->cost > st.cost;
  }
};

int manhattan(const Point& p1, const Point& p2)
{
  return abs(p1.x - p2.x) + abs(p1.y - p2.y);
}

int main()
{
  const int INF = 1 << 30;

  int w, h;
  while (cin >> w >> h) {
    if (w == 0 && h == 0)
      break;

    int jewel = 0;
    vector<vector<string> > floor(h, vector<string>(w));
    for (int i = 0; i < h; ++i) {
      for (int j = 0; j < w; ++j) {
	cin >> floor[i][j];
	if (floor[i][j] != "S" && floor[i][j] != "G" && floor[i][j] != ".")
	  jewel = max(jewel, atoi(floor[i][j].c_str()));
      }
    }

    unsigned int size = 1;
    vector<vector<Point> > path(jewel+2);
    for (int i = 0; i < h; ++i) {
      for (int j = 0; j < w; ++j) {
	if (floor[i][j] == "S") {
	  path[0].push_back(Point(j, i));
	} else if (floor[i][j] == "G") {
	  path[jewel+1].push_back(Point(j, i));
	} else if (floor[i][j] != ".") {
	  int num = atoi(floor[i][j].c_str());
	  path[num].push_back(Point(j, i));
	  size = max(size, path[num].size());
	}
      }
    }

    vector<vector<int> > cost(jewel+2, vector<int>(size, INF));
    priority_queue<State> que;
    que.push(State(0, 0, 0));
    while (!que.empty()) {
      const State st = que.top();
      que.pop();
      
      if (st.jewel == jewel+1) {
	cout << st.cost << endl;
	break;
      }

      if (cost[st.jewel][st.num] < st.cost)
	continue;
      cost[st.jewel][st.num] = st.cost;

      for (unsigned int i = 0; i < path[st.jewel+1].size(); ++i) {
	int new_cost = st.cost + manhattan(path[st.jewel][st.num], path[st.jewel+1][i]);
	if (cost[st.jewel+1][i] > new_cost) {
	  cost[st.jewel+1][i] = new_cost;
	  que.push(State(st.jewel+1, i, new_cost));
	}
      }
    }

  }
  return 0;
}

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

int main() {
  int N, K; cin >> N >> K;
  vector<long long> x(N), y(N);
  for (int i = 0; i < N; i++) cin >> x.at(i) >> y.at(i);
  long long ans = 1LL << 62;
  for (int i = 0; i < N; i++) {  // 左端
    for (int j = 0; j < N; j++) {  // 右端
      if (!(x.at(i) <= x.at(j))) continue;
      for (int s = 0; s < N; s++) {  // 上端
        for (int t = 0; t < N; t++) {  // 下端
          if (!(y.at(t) <= y.at(s))) continue;
          int cnt = 0;
          for (int k = 0; k < N; k++) {
            if (!(x.at(i) <= x.at(k))) continue;
            if (!(x.at(k) <= x.at(j))) continue;
            if (!(y.at(k) <= y.at(s))) continue;
            if (!(y.at(t) <= y.at(k))) continue;
            cnt++;
          }
          if (cnt >= K) {
            ans = min(ans, (x.at(j) - x.at(i)) * (y.at(s) - y.at(t)));
          }
        }
      }
    }
  }
  cout << ans << endl;
}

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

#define int long long
typedef vector<int>vint;
typedef pair<int,int>pint;
typedef vector<pint>vpint;
#define rep(i,n) for(int i=0;i<(n);i++)
#define reps(i,f,n) for(int i=(f);i<(n);i++)
#define all(v) (v).begin(),(v).end()
#define each(it,v) for(__typeof((v).begin()) it=(v).begin();it!=(v).end();it++)
#define pb push_back
#define fi first
#define se second
template<typename A,typename B>inline void chmin(A &a,B b){if(a>b)a=b;}
template<typename A,typename B>inline void chmax(A &a,B b){if(a<b)a=b;}

int N;
int X[111111],Y[111111];

set<pint>xy,yx;
int ans;
int len;

map<int,vint>xx,yy;

void dfs(int y,int x){
    xy.erase({x,y});
    yx.erase({y,x});

    if(xx.find(x-len)!=xx.end())ans+=lower_bound(all(xx[x-len]),y+len)-lower_bound(all(xx[x-len]),y-len);
    if(xx.find(x+len)!=xx.end())ans+=upper_bound(all(xx[x+len]),y+len)-upper_bound(all(xx[x+len]),y-len);
    if(yy.find(y-len)!=yy.end())ans+=upper_bound(all(yy[y-len]),x+len)-upper_bound(all(yy[y-len]),x-len);
    if(yy.find(y+len)!=yy.end())ans+=lower_bound(all(yy[y+len]),x+len)-lower_bound(all(yy[y+len]),x-len);

    for(int i=-1;i<=1;i+=2){
        while(true){
            auto it=xy.lower_bound({x+len*i,y-len});
            if(it==xy.end()||it->fi!=x+len*i||it->se>y+len)break;
            dfs(it->se,it->fi);
        }
        while(true){
            auto it=yx.lower_bound({y+len*i,x-len});
            if(it==yx.end()||it->fi!=y+len*i||it->se>x+len)break;
            dfs(it->fi,it->se);
        }
    }

}

signed main(){
    cin>>N;
    int a,b;
    cin>>a>>b;a--;b--;
    rep(i,N){
        cin>>X[i]>>Y[i];
        int x=X[i]+Y[i];
        int y=X[i]-Y[i];
        X[i]=x;Y[i]=y;
        xy.insert({x,y});yx.insert({y,x});
        xx[X[i]].pb(Y[i]);yy[Y[i]].pb(X[i]);
    }
    each(it,xx)sort(all(it->se));
    each(it,yy)sort(all(it->se));
    len=max(abs(X[a]-X[b]),abs(Y[a]-Y[b]));
    dfs(Y[a],X[a]);
    cout<<ans/2<<endl;
    return 0;
}


Measured memory_bytes: 39424
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define REP(i, n) for(int i = 1; i <= (int)(n); i++)
const long long INF = 1LL << 60;
const double PI=3.14159265358979323846;
int main() 
{
    int n;
  	cin >> n;
    long long ans=0;

    REP(i,n){
        if(i%3!=0 && i%5!=0){
            ans+=i;
        }
    }

    cout << ans << endl;
}

Measured memory_bytes: 3632
#include <stdio.h>
#include <string.h>

int main(int argc, char *argv[]) {
    char s[10010], t[10010];
    scanf("%s %s", s, t);
    long long min_difference = 100000;
    for (size_t i = 0; i < strlen(s) + 1 - strlen(t); i++) {
        long diff = 0;
        for (size_t j = 0; j < strlen(t); j++) {
            if (s[i + j] != t[j]) {
                diff++;
            }
        }
        if (diff < min_difference) {
            min_difference = diff;
        }
    }
    printf("%lld", min_difference);

    return 0;
}


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

ans = 0

for i in range(n):
    ans += b[a[i]-1]
    if 0 < i and a[i] == a[i-1]+1:
        ans += c[a[i-1]-1]

print(ans)


Measured memory_bytes: 3060
# -*- coding: utf-8 -*-

import sys
from heapq import heapify, heappop

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

N, K = MAP()
DT = []
tmp = [[] for i in range(N)]
for i in range(N):
    t, d = MAP()
    DT.append((d, t))
DT.sort(reverse=1)

que = []
D = {}
dcnt = 0
# ポイント上位K個をまず取る
for i in range(K):
    d, t = DT[i]
    dcnt += d
    # 種類tが1つ目
    if t not in D:
        D[t] = d
    # 2つ目以降なら、最大のものはDに残して他はキューへ
    else:
        if D[t] < d:
            D[t], d = d, D[t]
        que.append((d, t))
heapify(que)
tcnt = len(D)

ans = dcnt + tcnt**2
for i in range(K, N):
    d2, t2 = DT[i]
    # 既に持っている種類ならスキップ
    if t2 in D:
        continue
    D[t2] = d2
    tmp = []
    # 全部1種類ずつならもう種類数を増やせないので終了
    if not que:
        break
    d, t = heappop(que)
    # この候補と交換してみる
    dcnt -= d
    dcnt += d2
    tcnt += 1
    ans = max(ans, dcnt + tcnt**2)
print(ans)


Measured memory_bytes: 29316
#include<stdio.h>
int main(){
    int n,k,num,snuck,cnt=0,i;
    int snuck_true[105]={0};
    scanf("%d %d",&n,&k);
    while(k>0){
        scanf("%d",&num);
        while(num>0){
            scanf("%d",&snuck);
            snuck_true[snuck]=1;
            num--;
        }
        k--;
    }
    for(i=1;i<=n;i++){
        if(snuck_true[i]==0) cnt++;
    }
    printf("%d",cnt);
    return 0;
}

Measured memory_bytes: 1732
#include <bits/stdc++.h>
using namespace std;
int a, b, c, maxV, ans, now;

void Adjust(int v) {
    int t = maxV - v;
    if (t % 2 == 1) ++now;
    ans += t / 2;
}

int main() {
    scanf("%d%d%d", &a, &b, &c);
    maxV = max(max(a, b), c);
    Adjust(a); Adjust(b); Adjust(c);
    if (now == 1) ans += 2; else if (now == 2) ++ans;
    printf("%d", ans);
}


Measured memory_bytes: 256
'use strict';
console.log(function(args){
  const N = args.trim()|0;
  let count = 0;
  for ( let i = 1; i <= N; i=i+2 ) {
    let divisor = 0;
    for ( let j = 1; j <= i; j++ ) {
      if ( i % j === 0 && ++divisor > 8 ) break;
    }
    if ( divisor === 8 ) count++;
  }
  return count.toString();
}(require('fs').readFileSync('/dev/stdin', 'utf8')));

Measured memory_bytes: 7756
while 1:
    N = int(raw_input())
    if N == 0: break
    free = [map(int,raw_input().split())[1:] for i in xrange(N)]
    have = [set([i]) for i in xrange(N)]
    for day in xrange(1,31):
        gather = set([])
        for i in xrange(N):
            if day in free[i]:
                gather |= have[i]
        if len(gather) == N:
            print day
            break
        for i in xrange(N):
            if day in free[i]:
                have[i] = gather.copy()
    else:
        print -1
    

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

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

int main(){
  double a, b, c, d, e, f;
  cin >> a >> b >> c >> d >> e >> f;
  set<double> st;
  for(int i = 0; i * a * 100 <= f; i++){
    for(int j = 0; j * b * 100 <= f; j++){
      if(a*100*i + b*100*j <= f) st.insert(a*100*i + b*100*j);
    }
  }
  int ans1, ans2;
  double tmp = -1;
  for(int water : st){
    double psbl = min(water/100*e, f-water);
    double sugar = -1;
    for(int j = 0; j*c <= psbl; j++){
      for(int k = 0; k*d <= psbl; k++){
        if(c*j + d*k <= psbl) sugar = max(sugar, c*j + d*k);
      }
    }
    if(chmax(tmp, sugar*100/(water + sugar))){
      ans1 = sugar + water;
      ans2 = sugar;
    }
  }
  cout << ans1 << " " << ans2 << endl;    
}

Measured memory_bytes: 3740
#include <bits/stdc++.h>
using namespace std;
#define fastIO ios::sync_with_stdio(0), cin.tie(0)
#define endl '\n'
#define ft first
#define sd second
#define pb push_back
#define pob pop_back()
#define pf push_front
#define pof pop_front()
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin, (x).rend()
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<char,char> pcc;
typedef pair<double,double> pdd;
typedef pair<long long,long long> pll;
// scanf("%d %d %d %d",&w,&b,&d,&s); %lld
// printf("%d\n" ,points);
// const double PI=acos(-1);

int main()
{
	int n; cin >> n;
	int d[n];
	for(int i = 0; i<n; i++) cin >> d[i];
	
	ll ans = 0;
	for(int i = 0; i<n; i++){
		for(int j = i+1; j<n; j++){
			ans+=(d[i]*d[j]);
		}
	}
	cout << ans << endl;
}

Measured memory_bytes: 3592
void main() {
	alias Pair = Tuple!(int, "value", int, "count");
	auto n = ri;
	auto v = readAs!(int[]);
	Pair[] e, o;
	foreach(i; 0..100000) {
		e ~= Pair(i, 0);
		o ~= Pair(i, 0);
	}
	foreach(i, j; v) {
		if(i & 1) {
			o[j-1].count++;
		} else e[j-1].count++;
	}
	sort!"a.count > b.count"(e);
	sort!"a.count > b.count"(o);
	if(e[0].value != o[0].value) {
		writeln(n - e[0].count - o[0].count);
	} else {
		writeln(n - max(e[0].count + o[1].count, e[1].count + o[0].count));
	}
}

// ===================================

import std.stdio;
import std.string;
import std.functional;
import std.algorithm;
import std.range;
import std.traits;
import std.math;
import std.container;
import std.bigint;
import std.numeric;
import std.conv;
import std.typecons;
import std.uni;
import std.ascii;
import std.bitmanip;
import core.bitop;

T readAs(T)() if (isBasicType!T) {
	return readln.chomp.to!T;
}
T readAs(T)() if (isArray!T) {
	return readln.split.to!T;
}

T[][] readMatrix(T)(uint height, uint width) if (!isSomeChar!T) {
	auto res = new T[][](height, width);
	foreach(i; 0..height) {
		res[i] = readAs!(T[]);
	}
	return res;
}

T[][] readMatrix(T)(uint height, uint width) if (isSomeChar!T) {
	auto res = new T[][](height, width);
	foreach(i; 0..height) {
		auto s = rs;
		foreach(j; 0..width) res[i][j] = s[j].to!T;
	}
	return res;
}

int ri() {
	return readAs!int;
}

double rd() {
	return readAs!double;
}

string rs() {
	return readln.chomp;
}

Measured memory_bytes: 7236
import sys;sys.setrecursionlimit(9**9);n=int(input());s=list(map(int,list(input())));e=[[]for _ in[0]*n]
for _ in[0]*(n-1):a,b=map(int,input().split());e[a-1].append(b-1);e[b-1].append(a-1)
def f(a):
  l,r,c=a[0]
  for u,v,d in a[1:]:l,r=max(max(l,u)-min(r,v),(l^u)&1),r+v;c+=d
  return[l,r,c]
def dfs(o,u):
  if(o!=u)&(len(e[u])==1):return[s[u]]*3
  l,r,c=f([dfs(u,v)for v in e[u]if o-v]);c+=s[u];return[l+c,r+c,c]
a=[r-c for l,r,c in[dfs(i,i)for i in range(n)]if l==c];print(min(a)//2if a else-1)

Measured memory_bytes: 226752
def main():
    N = input()
    a = map(int, raw_input().split())
    print ' '.join(map(str,a))
    for i in xrange(1,len(a)):
        v = a[i]
        j = i - 1
        while (j >= 0) & (a[j] > v):
            a[j+1] = a[j]
            j -= 1
        a[j+1] = v
        print ' '.join(map(str,a))
    return 0

main()

Measured memory_bytes: 6472
S = input()
A = int(S[0:2])
B = int(S[2:4])

if (0 < A) and (A <= 12):
    if (0 < B) and (B <= 12):
        print('AMBIGUOUS')
    else:
        print('MMYY')

else:
    if (0 < B) and (B <= 12):
        print('YYMM')
    else:
        print('NA')

Measured memory_bytes: 3060
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define INF 1e9
int MOD = 1e9+7;
ll a[103];
ll n,K;
ll dp[103][(ll)(1e5+1)];
//doing it forward dp style and with a optimisation
int main(){
	cin>>n>>K;
	memset(dp,0,sizeof dp);
	for(ll i=0;i<n;i++) cin>>a[i];
	dp[0][0]=1; 
	for(int i=0;i<n;i++){
		vector<ll> to_add(K+1);
		for(ll used=0;used<=K;used++){
			ll L = used;
			ll R = used + min(K-used,a[i]);
			to_add[L] += dp[i][used];
			if(R+1<=K) to_add[R+1] += (-dp[i][used]);
			// for(int here = 0;used+here<=K&&here<=a[i];here++){
			// 	dp[i+1][used+here]+=dp[i][used];
			// }
		}
		ll pref_sum=0;
		for(int j=0;j<=K;j++){
			pref_sum += to_add[j];
			dp[i+1][j] = pref_sum%MOD;
		}
	}
	cout<<(dp[n][K]%MOD)<<endl;
	return 0;
}

Measured memory_bytes: 84836
import java.util.Scanner;

public class Main {
    /**
     * 9x9
     * @param 1 ≤ A ≤ 20
     * @param 1 ≤ B ≤ 20
     */
    public static void main(String...args) {
        try (Scanner sc = new Scanner(System.in)) {
            int a = sc.nextInt();
            int b = sc.nextInt();
            if (a < 10 && b < 10) {
                System.out.println(a * b);
            } else {
                System.out.println(-1);
            }
        }
    }
}

Measured memory_bytes: 21972
w,m[];R(char*p){*p>45?*p=0,R(p-1),R(p+1),R(p-w),R(p+w),++*m:0;}main(){for(;scanf("%d%*d",&w)*w;printf("%d\n",*m))bzero(m,999),scanf("%[^0-9]",++w+m),R(index(m+w,64));}

Measured memory_bytes: 0
#include<bits/stdc++.h>
#define endl '\n'
#define mp make_pair
typedef long long int ll;
using namespace std;
int main()
{
    ll n,a,b,c,d,k;
    cin>>a>>b>>c>>d;
    ll val= (b/c)- (a-1)/c;
    ll val1=(b/d)- (a-1)/d;
    ll dono= c*d;
    ll f=__gcd(c,d);
    dono=dono/f;
    ll val3=(b/dono)- (a-1)/dono;
    val3=val+val1-val3;
    ll ans=b-a+1-val3;
    cout<<ans<<endl;
}

Measured memory_bytes: 256
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cctype>
#include <climits>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <fstream>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <valarray>
#include <vector>

#define EPS 1e-9
#define INF 1070000000LL
#define MOD 1000000007LL
#define fir first
#define foreach(it,X) for(__typeof((X).begin()) it=(X).begin();it!=(X).end();it++)
#define ite iterator
#define mp make_pair
#define rep(i,n) rep2(i,0,n)
#define rep2(i,m,n) for(int i=m;i<(n);i++)
#define pb push_back
#define sec second
#define sz(x) ((int)x.size())

using namespace std;

struct timer{
	time_t start;
	timer(){start=clock();}
	~timer(){cerr<<1.*(clock()-start)/CLOCKS_PER_SEC<<" secs"<<endl;}
};

typedef istringstream iss;
typedef long long ll;
typedef pair<int,int> pi;
typedef stringstream sst;
typedef vector<int> vi;

int a[15][15];

int main(){
	cin.tie(0);
	ios_base::sync_with_stdio(0);
	
	int y,x,t;
	char c;
	while(cin>>x>>c>>y>>c>>t){
		rep(i,10)rep(j,10){
			if(t==1 || t==3){
				if(abs(i-y)+abs(j-x)<=(t+1)/2){
					a[i][j]++;
				}
			}else{
				if(max(abs(i-y),abs(j-x))<=1){
					a[i][j]++;
				}
			}
		}
	}
	int ans1=0,ans2=0;
	rep(i,10)rep(j,10){
		if(a[i][j]==0)ans1++;
		ans2=max(ans2,a[i][j]);
	}
	cout<<ans1<<endl<<ans2<<endl;
}

Measured memory_bytes: 1192
#include<bits/stdc++.h>
using namespace std;
#define _              ios_base::sync_with_stdio(0);cin.tie(0);
#define pb             emplace_back
#define mp             make_pair
#define F              first
#define S              second
#define rep(i, x)      for (__typeof(x) i = 0; i < x; i++)
#define repp(i, x, y)  for (__typeof(x) i = x; i < y; i++)
#define all(a)         (a).begin(),(a).end()
#define sz(x)          (int)x.size()
#define endl           '\n'
#define DB(x)          cerr << #x << " is " << x << endl;
#define TEST(T)        int T; cin >> T; rep(i, T)
#define MOD            1000000007
typedef long long          ll;
typedef vector<int>        vi;
typedef pair<int, int>     ii;
typedef vector<ii>        vii;

int main(){ _
    ll n, a, b; cin >> n>> a >> b;
    vector<ll> v(n); rep(i, n) cin >>v[i];
    ll f = 0;

    repp(i, 1, n){
        f += min(a*(v[i]-v[i-1]), b);
    }
    cout << f << endl;
}

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

int main() {
	int n; cin >> n;
	map<int, int>a; for (int i = 0, tmp; i < n; i++)cin >> tmp, a[tmp]++;
	long long ans = 0;
	for (auto&& x : a) {
		if (x.first < x.second)ans += (x.second - x.first);
		else if (x.first > x.second)ans += x.second;
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 4736
import sys
input = sys.stdin.readline

def main():
    N = int(input())
    X = list(map(int,input().split()))

    eq = 0
    count = 0
    c_list = []
    for i in range(N):
        if X[i] == i+1:
            eq += 1

    X.append(0)
    for i in range(N):
        if X[i] == i+1 and X[i+1] == i+2:
            count += 1
        elif X[i] == i+1 and X[i+1] != i+2 and count != 0:
            c_list.append(count)
            count = 0
        else:
            count = 0

    for i in range(len(c_list)):
        eq += -(c_list[i]+1)+(c_list[i]//2+1)

    print(eq)

if __name__ == "__main__":
    main()

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

int pos;
string a, b, s;
int var[128];

bool form() {
  if(isupper(s[pos])) return s[pos++] == 'T';
  if(islower(s[pos])) return var[s[pos++]];
  if(s[pos] == '-') return ++pos, !form();
  ++pos;
  bool x = form();
  char op = s[pos++];
  if(op == '-') ++pos;
  bool y = form();
  ++pos;
  if(op == '*') return x && y;
  if(op == '+') return x || y;
  if(op == '-') return !x || y;
  assert(false);
}

void rec(char c) {
  if(c == 'l') {
    s = a; pos = 0;
    int va = form();
    s = b; pos = 0;
    int vb = form();
    if(va != vb) throw 0;
    return;
  }
  var[c] = 0; rec(c+1);
  var[c] = 1; rec(c+1);
}

int main() {
  while(cin >> a && a != "#") {
    int k = a.find('=');
    b = a.substr(k + 1);
    a = a.substr(0, k);
    try {
      rec('a');
      cout << "YES" << endl;
    } catch(...) {
      cout << "NO" << endl;
    }
  }
  return 0;
}

Measured memory_bytes: 1300
from collections import deque

n,q = map(int,input().split())

Q = [deque() for _ in range(n)]

for _ in range(q):
    a = input().split()
    t = int(a[1])
    if a[0] == "0":
        
        Q[t].append(a[2])
    elif a[0] == "1":
        if Q[t]:
            print(*Q[t])
        else:
            print()
    else:
        if Q[t]:
            Q[t].clear()
        else:
            continue


Measured memory_bytes: 42828
using System;
using System.Collections.Generic;
using System.Linq;
class Program
{
    public static void Main()
    {
        int N = int.Parse(Console.ReadLine());
        string input = Console.ReadLine();
        int ans = 0;
        for(int i = 0; i < N - 2; i++)
        {
            if (input[i] == 'A' && input[i+1] == 'B' && input[i+2] == 'C') ans++;
        }
        Console.WriteLine(ans);
    }
}

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

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

	//string s;
	int a,b,c;

	cin >> a >> b >> c;
	
	int ab=a-b;
	int ans=c-ab;
	
	if(ans<0) ans=0;
	
	cout << ans << "\n";
	
	
	return 0;

    }

Measured memory_bytes: 256
/**
 * A - Security
 * https://atcoder.jp/contests/abc131/tasks/abc131_a
 **/
#include<iostream>

using namespace std;

string S;

void solve() {
    bool is_bad = false;
    for(int i = 1; i < S.length(); i++){
        if (S[i] == S[i-1]) {
            is_bad = true;
        }
    }
    if (is_bad) {
        cout << "Bad" << endl;
    } else {
        cout << "Good" << endl;
    }
}

int main() {
    cin >> S;
    solve();
}

Measured memory_bytes: 256