akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double db;
#define fi first
#define se second
#define pi pair<ll,ll>
#define pii pair<ll,pi>
#define pb push_back
#define mk make_pair
ll cal(ll a) {
	if (a % 4 == 0)return a;
	if (a % 4 == 1)return 1;
	if (a % 4 == 2)return a + 1;
	return 0;
}
int main() {
#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
#endif
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	clock_t begin = clock();
	ll a, b;
	cin >> a >> b;
	ll ans = cal(b)^cal(a - 1) ;
	cout << ans << endl;
	clock_t end = clock();
	cerr << "Time run: " << (float)(end - begin) / CLOCKS_PER_SEC << " s" << endl;
}

Measured memory_bytes: 3768
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <cctype>
#include <climits>
#include <string>
#include <bitset>
using namespace std;
typedef long double ld;
typedef long long int ll;
typedef unsigned long long int ull;
typedef vector<int> vi;
typedef vector<char> vc;
typedef vector<string> vs;
typedef vector<ll> vll;
typedef vector<pair<int,int> > vpii;
typedef vector<vector<int> > vvi;
typedef vector<vector<char> > vvc;
typedef vector<vector<string> > vvs;
typedef vector<vector<ll> > vvll;
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define rrep(i,n) for(int i = 1; i <= (n); ++i)
#define drep(i,n) for(int i = (n)-1; i >= 0; --i)
#define fin(ans) cout<<(ans)<<endl
#define STI(s) atoi(s.c_str())
#define mp(p,q) make_pair(p,q)
#define pb(n) push_back(n)
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define Sort(a) sort(a.begin(),a.end())
#define Rort(a) sort(a.rbegin(),a.rend())
template<class T> inline bool chmax(T& a,T b){if(a<b){a=b;return 1;}return 0;}
template<class T> inline bool chmin(T& a,T b){if(a>b){a=b;return 1;}return 0;}
const int P = 1000000007;
const int INF = INT_MAX;
const ll LLINF = 1LL<<60;

ll gcd(ll a, ll b) { return b ? gcd(b, a%b) : a;}
int ngcd(int n, vi a){
    int i,d;
    d = a[0];
    for(i = 1; i < n && d != 1; i++) d = gcd(a[i], d);
    return d;
}

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

    
    int n;
    int k;
    cin>>n>>k;
    vi v(n);
    rep(i,n)cin>>v[i];
    Sort(v);
    if(k%ngcd(n,v)==0&&v[n-1]>=k){
        fin("POSSIBLE");
    }else{
        fin("IMPOSSIBLE");
    }


//////////////////////////////////////////////////////
return 0;}

Measured memory_bytes: 1024
#include <iostream>
#include <map>
#include <algorithm>
#include <string>
#include <vector> 
#include <numeric>
#include <cmath>
#include <queue>
#include <iomanip>
#include <functional>


#define CHMAX(a,b) a = std::max(a,b)
#define CHMIN(a,b) a = std::min(a,b)
#define MAXMIN(a,b,c) std::max(a,min(b,c))
#define CHABS(a) a = std::abs(a) 
#define COUT(a) std::cout << a << std::endl
#define CERR(a) std::cerr << a << std::endl
#define FOR(n) for(lli i = 0; i < n; i++)

using namespace std;
using lli = long long int;
using pll = pair<lli, lli>;
using tlll = tuple<lli, lli, lli>;
using vll = vector<lli>;

constexpr lli inf = 10000 * 10000;

lli mod197 = 1000000007LL;
lli INF = 10000000000000;

// ax + by = gcd(a,b) 最大公約数
template< typename T >
T extgcd(T a, T b, T& x, T& y) {
	T d = a;
	if (b != 0) {
		d = extgcd(b, a % b, y, x);
		y -= (a / b) * x;
	}
	else {
		x = 1;
		y = 0;
	}
	return d;
}

int main(void) {

	lli a, b, k;
	cin >> k >> a >> b;

	if (k == 1) {
		cout << "OK" << endl;
		return 0;
	}


	lli t = a % k;
	b = b - (a - t);
	a = t;

	if (a == 0) {
		cout << "OK" << endl;
	}else if (a <= k && k <= b) {
		cout << "OK" << endl;
	}
	else {
		cout << "NG" << endl;
	}

	return 0;
}


Measured memory_bytes: 3576
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <bitset>
#include <string>
#include <cmath>
#include <complex>
#include <numeric>
#include <cassert>

#include <vector>
#include <array>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <deque>
#include <utility>

#define int64 long long
#define uint64 unsigned long long
using namespace std;

int main()
{
	int64 aa, bb, cc;
	cin >> aa >> bb >> cc;
	if(aa == bb && bb != cc)
	{
		puts("Yes");
	}
	else if(bb == cc && aa != bb)
	{
		puts("Yes");
	}
	else if(aa == cc && aa != bb)
	{
		puts("Yes");
	}
	else
	{
		puts("No");
	}
	return 0;
}

Measured memory_bytes: 3532
import java.util.Scanner;
import java.util.Arrays;

public class Main {

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

        int N = sc.nextInt();

        int[] W = new int[N];

        int sum1 = 0;

        for (int i = 0; i < N; i++) {
            W[i] = sc.nextInt();
            sum1 += W[i];
        }

        int sum2 = 0;

        int m_sum = 1000000000;

        for (int i = 0; i < N; i++) {
            sum1 -= W[N - 1 - i];
            sum2 += W[N - 1 - i];
            if (Math.abs(sum1 - sum2) < m_sum) {
                m_sum = Math.abs(sum1 - sum2);
            }
        }

        System.out.println(m_sum);

        sc.close();
        ;
    }
}

Measured memory_bytes: 22740
//入力マクロここから
//https://qiita.com/tanakh/items/0ba42c7ca36cd29d0ac8
macro_rules ! input_inner { ( $ next : expr ) => { } ; ( $ next : expr , ) => { } ; ( $ next : expr , $ var : ident : $ t : tt $ ( $ r : tt ) * ) => { let $ var = read_value ! ( $ next , $ t ) ; input_inner ! { $ next $ ( $ r ) * } } ; }
macro_rules ! read_value { ( $ next : expr , ( $ ( $ t : tt ) ,* ) ) => { ( $ ( read_value ! ( $ next , $ t ) ) ,* ) } ; ( $ next : expr , [ $ t : tt ; $ len : expr ] ) => { ( 0 ..$ len ) . map ( | _ | read_value ! ( $ next , $ t ) ) . collect ::< Vec < _ >> ( ) } ; ( $ next : expr , chars ) => { read_value ! ( $ next , String ) . chars ( ) . collect ::< Vec < char >> ( ) } ; ( $ next : expr , usize1 ) => { read_value ! ( $ next , usize ) - 1 } ; ( $ next : expr , $ t : ty ) => { $ next ( ) . parse ::<$ t > ( ) . expect ( "Parse error" ) } ; }
macro_rules ! input { ( source = $ s : expr , $ ( $ r : tt ) * ) => { let mut iter = $ s . split_whitespace ( ) ; let mut next = || { iter . next ( ) . unwrap ( ) } ; input_inner ! { next , $ ( $ r ) * } } ; ( $ ( $ r : tt ) * ) => { let stdin = std :: io :: stdin ( ) ; let mut bytes = std :: io :: Read :: bytes ( std :: io :: BufReader :: new ( stdin . lock ( ) ) ) ; let mut next = move || -> String { bytes . by_ref ( ) . map ( | r | r . unwrap ( ) as char ) . skip_while ( | c | c . is_whitespace ( ) ) . take_while ( | c |! c . is_whitespace ( ) ) . collect ( ) } ; input_inner ! { next , $ ( $ r ) * } } ; }
//入力マクロここまで

use std::cmp::*;

fn main() {
    input! {
        n: u64,
        a: u64,
        b: u64,
    }

    let ans = if (b - a) % 2 == 0 {
        (b - a) / 2
    } else {
        min(min(b - 1, n - a), min(a, n - b + 1) + (b - a) / 2)
    };

    println!("{}", ans);
}


Measured memory_bytes: 4352
def main():
    N = input_ints()

    a = input_int_list_in_line()

    print(len([True for i in range(N) if i % 2 == 0 and a[i] % 2 == 1]))




def input_ints():
    line_list = input().split()

    if len(line_list) == 1:
        return int(line_list[0])
    else:
        return map(int, line_list)


def input_int_list_in_line():
    return list(map(int, input().split()))


def input_int_tuple_list(n: int):
    return [tuple(map(int, input().split())) for _ in range(n)]


main()


Measured memory_bytes: 8976
#include <iostream>
#include <iomanip>
#include <sstream>
#include <vector>
#include <string>
#include <set>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <stack>
#include <queue>
#include <deque>
#include <algorithm>
#include <functional>
#include <iterator>
#include <limits>
#include <numeric>
#include <utility>
#include <cmath>
#include <cassert>
#include <cstdio>

using namespace std; using namespace placeholders;

typedef long long LL;
typedef unsigned long long ULL;
typedef vector< int > VI;
typedef vector< vector< int > > VVI;
typedef vector< string > VS;
typedef stringstream SS;
typedef pair< int, int > PII;
typedef vector< pair< int, int > > VPII;
#define VT( T ) vector< T >
#define VVT( T ) vector< vector< T > >
#define LIM( T ) numeric_limits< T >

template < typename T > inline istream& operator>>( istream &s, vector< T > &v ){ for ( T &t : v ) { s >> t; } return s; }
template < typename T > inline ostream& operator<<( ostream &s, const vector< T > &v ){ for ( int i = 0; i < int( v.size() ); ++i ){ s << ( " " + !i ) << v[i]; } return s; }
template < typename T > inline T fromString( const string &s ) { T res; istringstream iss( s ); iss >> res; return res; };
template < typename T > inline string toString( const T &a ) { ostringstream oss; oss << a; return oss.str(); };

#define REP2( i, n ) REP3( i, 0, n )
#define REP3( i, m, n ) for ( int i = ( int )( m ); i < ( int )( n ); ++i )
#define GET_REP( a, b, c, F, ... ) F
#define REP( ... ) GET_REP( __VA_ARGS__, REP3, REP2 )( __VA_ARGS__ )
#define FOR( e, c ) for ( auto &e : c )
#define ALL( c ) ( c ).begin(), ( c ).end()
#define AALL( a, t ) ( t* )a, ( t* )a + sizeof( a ) / sizeof( t )
#define DRANGE( c, p ) ( c ).begin(), ( c ).begin() + p, ( c ).end()

#define SZ( v ) ( (int)( v ).size() )
#define PB push_back
#define EM emplace
#define EB emplace_back
#define BI back_inserter

#define EXIST( c, e ) ( ( c ).find( e ) != ( c ).end() )

#define MP make_pair
#define fst first
#define snd second

#define DUMP( x ) cerr << #x << " = " << ( x ) << endl

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

	int N;
	cin >> N;

	VVI G( N, VI( N ) );
	cin >> G;

	LL res = 0;
	REP( i, N )
	{
		REP( j, i )
		{
			res += min( G[i][j], G[j][i] );
		}
	}
	cout << res << endl;

	return 0;
}

Measured memory_bytes: 1260
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

#define F first
#define S second
#define prev azaza
#define MP make_pair
#define PB push_back

using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
typedef long double ld;

typedef tree<int,
null_type,
less<int>,
rb_tree_tag,
tree_order_statistics_node_update> or_set;

const int max_n = 300111, inf = 1000111222;

int m[max_n];
int m1[max_n];
int pos[max_n];

int main()
{
    srand(time(0));
    //freopen("input.txt", "r", stdin);
    int n;
    cin >> n;
    for (int i = 0; i < n; ++i) {
        cin >> m[i];
        --m[i];
        m1[i] = m[i];
        pos[m[i]] = i;
    }
    or_set os;
    ll ans = 0;
    for (int i = n - 1; i >= 0; --i) {
        ans += os.order_of_key(m[i]);
        os.insert(m[i]);
    }
    if (ans % 3 == 0) {
        for (int i = 0; i < n; ++i) {
            if (abs(pos[i] - i) % 2 == 1) {
                cout << "No" << endl;
                return 0;
            }
        }
        for (int i = 0; i < n; ++i) {
            if (1.0 * clock() / CLOCKS_PER_SEC > 1) {
                break;
            }
            int st = 0;
            for (int j = i; j < n; ++j) {
                if (m[j] == i) {
                    st = j;
                    break;
                }
            }
            while (st > i) {
                if (m[st - 2] > m[st - 1] && m[st - 1] > m[st]) {
                    swap(m[st], m[st - 2]);
                    st -= 2;
                } else {
                    cout << "No" << endl;
                    return 0;
                }
            }
        }
        if (is_sorted(m, m + n)) {
            cout << "Yes" << endl;
            return 0;
        }
        for (int i = n - 1; i >= 0; --i) {
            if (1.0 * clock() / CLOCKS_PER_SEC > 1.95) {
                if (rand() % 10 == 6) {
                    cout << "No" << endl;
                } else {
                    cout << "Yes" << endl;
                }
                return 0;
            }
            int st = 0;
            for (int j = 0; j < n; ++j) {
                if (m[j] == i) {
                    st = j;
                    break;
                }
            }
            while (st < i) {
                if (m[st] > m[st + 1] && m[st + 1] > m[st + 2]) {
                    swap(m[st], m[st + 2]);
                    st += 2;
                } else {
                    cout << "No" << endl;
                    return 0;
                }
            }
        }
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }
    return 0;
}

// 13:24
















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

int main() {
	int a, W;
	scanf("%d%d", &a, &W);
	vector<int> w(a), v(a);
	vector<long long> dp(W + 1, 0);
	for (int i = 0; i < a; i++) {
		scanf("%d%d", &w[i], &v[i]);
	// }
	// for (int i = 0; i < a; i++) {
		for (int j = W - w[i]; j >= 0 ; j--) {
			if (j + w[i] <= W)
				dp[j + w[i]] = max(dp[j + w[i]], dp[j] + v[i]);
		}
	}

	long long ans = 0;
	for (int i = 0; i <= W; i++)
		ans = max(ans, dp[i]);

	printf("%lld\n", ans);
}

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

int main(){
    char S[15],T[15];
    cin >> S;
    
    int n,sum=0;
    cin >> n;
    for(int i=0; i<n; i++){
        char TS[30];
        cin >> TS;
        strcpy(T,TS);
        strcat(TS,T);
        if(!(strstr(TS,S)==NULL)){
            sum++;
        }
    }
    cout << sum << endl;
}

Measured memory_bytes: 3112
import sys
import itertools
import bisect
from operator import itemgetter
 
MAX_INT = int(10e15)
MIN_INT = -MAX_INT
mod = 1000000007
sys.setrecursionlimit(1000000)
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(sys.stdin.readline())
def S(): return input()
def combi(n, r):
  r = min(r, n-r)
  numer = denom = 1
  for i in range(1, r+1):
    numer = numer * (n+1-i) %mod
    denom = denom * i %mod
  return numer * pow(denom, mod-2, mod) %mod
N = I()
a = IL()

dic = {}
for i in a:
  if i in dic:
    dic[i] += 1
  else:
    dic[i] = 1

ans = 0
for i in dic.values():
  ans += i*(i-1)//2

for i in a:
  n = dic[i]
  print(ans - n*(n-1)//2 + (n-1)*(n-2)//2 )

Measured memory_bytes: 86348
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <cstring>
#include <climits>
#include <ctime>

using namespace std;

const int len = 1000010;
int n,a[len];
char s[len];

int main() {
	//freopen("test.in","r",stdin);
	//freopen("test.out","w",stdout);
	scanf("%s",s);
	n = strlen(s);
	for (int i=0;i<n;i++) {
		if (s[i] == ',') cout << ' ';
		else cout << s[i];
	}
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <math.h>
#define rep(i, n) for(int i = 0; i < n; i++)
 
using namespace std;
 
int main() {
  int A, B;
  cin >> A >> B;
  for(int i = 1; i < 1300; i++){
    int c = floor(i * 0.08);
    int d = floor(i * 0.1);
    if(A == c && B == d){
      cout << i << endl;
      return 0;
    }
  }
  cout << "-1" << endl;
  
}

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

using namespace std;

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

const int MM = 1e9 + 7;
const double eps = 1e-8;
const int MAXN = 2e6 + 10;

int n, m;

void prework(){

}

void read(){

}

int k;

void solve(int casi){
//	cout << "Case #" << casi << ": ";
	cin >> n >> m >> k;
	for (int i = 0; i <= n; i++)
		for (int j = 0; j <= m; j++)
			if (i * j + (n-i)*(m-j) == k){
				puts("Yes");return ;
			}
	puts("No");
}

void printans(){

}


int main(){
//	std::ios::sync_with_stdio(false);
	prework();
	int T = 1;
//	cin>>T;
	for(int i = 1; i <= T; i++){
		read();
		solve(i);
		printans();
	}
	return 0;
}

Measured memory_bytes: 256
s = input()
x,y = map(int,input().split())
x1 = 0
y1 = []
muki = 0
t = len(s)
x2 = []
for i in range(len(s)):
  a = s[i]
  if a == "F":
    x1 += 1
  else:
    t = i+0
    break
x3 = 0
y2 = 0
for i in range(t,len(s)):
  a = s[i]
  if a == "F":
    if muki%2 == 0:
      x3+= 1
    else:
      y2 += 1
  else:
    if muki%2 == 0:
      if x3 != 0:
        x2.append(x3)
      x3 = 0
      muki +=1
    else:
      if y2 != 0:
        y1.append(y2)
      y2 = 0
      muki += 1
if x3 != 0:
   x2.append(x3)
if y2 != 0:
   y1.append(y2)
ansx = set([x1])
for i in x2:
  g = len(ansx)
  ansx2 = list(ansx)
  ansx = set([])
  for j in range(g):
    ansx.add(ansx2[j]+i)
    ansx.add(ansx2[j]-i)
ansy = set([0])
for i in y1:
  g = len(ansy)
  ansy2 = list(ansy)
  ansy = set([])
  for j in range(g):
    ansy.add(ansy2[j]+i)
    ansy.add(ansy2[j]-i)
if (x in ansx and y in ansy):
  print("Yes")
else:
  print("No")

Measured memory_bytes: 3904
#include<iostream>
#include<string>
#include<map>
#include<algorithm>
#include<vector>
#include<iomanip>
using namespace std;

int main() {
	string S; cin >> S;
	int N = S.size();
	int cnt1 = 0;
	int cnt2 = 0;
	string S1 = S;
	for (int i = 0; i < N; i++) {
		if (S1[i] == S1[i + 1]) {
			cnt1++;
			if (S1[i + 1] == '0') {
				S1[i + 1] = '1';
			}
			else {
				S1[i + 1] = '0';
			}
		}
	}
	reverse(S.begin(), S.end());
	string S2 = S;
	for (int i = 0; i < N; i++) {
		if (S2[i] == S2[i + 1]) {
			cnt2++;
			if (S2[i + 1] == '0') {
				S2[i + 1] = '1';
			}
			else {
				S2[i + 1] = '0';
			}
		}
	}
	cout << min(cnt1, cnt2) << endl;
}

Measured memory_bytes: 640
N = int(input())
_L = list(map(int,input().split()))

L =[(v,i) for i,v in enumerate(_L)]
L = sorted(L,key = lambda x:(-x[0],-x[1]))

dp = [[0]*(N+1) for _ in range(N+1)]

for i in range(N):#i番目の数字まで見た
    for k in range(N):#k回(i-pi)のパターン
        if k>i:
            continue
        val,ind = L[i]
        dp[i+1][k+1] = max(dp[i+1][k+1],dp[i][k] + val * abs(ind-k))#先頭からk番目に動かす
        dp[i+1][k] = max(dp[i+1][k],dp[i][k]+val * abs(N-1-(i-k)-ind))#すでに後ろからi-k個は使ってる=>後ろからN- (i-k)+1番目に動かす
print(max(dp[-1]))




Measured memory_bytes: 100552
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
int main()
{
    int n,a,b;
    scanf("%d%d%d",&n,&a,&b);

    LL l = (LL)a*(LL)(n-1) + (LL)b;
    LL r = (LL)b*(LL)(n-1) + (LL)a;

    //cout<<"l="<<l<<" "<<"r="<<r<<endl;

    if(l > r)
    {
        puts("0");
        return 0;
    }
    else printf("%lld\n",(r-l+1));
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>
#include <map>
using namespace std;


int main()
{
	int x, a, b;
	cin >> x >> a >> b;
	if (a - b >= 0) {
		cout << "delicious" << endl;
	}
	else if(a + x - b >= 0) {
		cout << "safe" << endl;
	}
	else {
		cout << "dangerous" << endl;
	}
	return 0;
}

Measured memory_bytes: 256
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii =  pair<int, int>;
using pll =  pair<long long, long long>;
constexpr char ln =  '\n';
constexpr long long MOD = 1000000007LL;
constexpr long long INF = 1000000009LL;
#define all(x) (x).begin(),(x).end()
#define rep(i,n) for(int i=0;i<(n);i++)
#define fo(i,j,n) for (int i=(j); i < (n); i++)
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 main() {
    int n, k; cin >> n >> k;
    /*rep(i, n){
        rep(j, n){
            cout << (i+1)%(j+1) << " ";
        }
        cout << ln;
    }*/
    ll res = 0, cnt = 1;
    for(int i=k; i<n; i++){
        res += (n / (i+1)) * cnt;
        //cout << "res:" << res << "  ";
        cnt++;
        res += max(0, (n % (i+1)) - max(0, k-1));
        //cout << "res:" << res << ln;
    }
    cout << res << ln;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define int long
#define ll long long
#define rep(i, n) for(int i = 0; i < n; i++)
#define IOS cin.tie(0); ios::sync_with_stdio(false)
using namespace std;
int gcd(int a,int b){return b ? gcd(b,a%b) : a;}
int lcm(int a,int b){return a/gcd(a,b)*b;}

vector<ll> divisor(ll n){
    vector<ll> ret;
    for(ll 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);
}

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

main() {
    int A,B; cin >> A >> B;
    int M=gcd(A,B);
    cout << prime_factor((ll)M).size()+1 << endl;
}

Measured memory_bytes: 256
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		for (int i = 1;; ++i) {
			int x = scanner.nextInt();
			if (x == 0)
				break;
			System.out.printf("Case %d: %d\n", i, x);
		}
		scanner.close();
	}

}


Measured memory_bytes: 63036
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef long double ld;
typedef vector<ll> vl;
typedef vector<bool> vb;
typedef vector<string> vs;
typedef vector<char> vc;
typedef queue<ll> ql;
typedef deque<ll> dql;
typedef priority_queue<ll/*, vl, greater<ll>*/> pql; //降順(/*昇順*/)
typedef set<ll> sl;
typedef pair<ll, ll> pl;
typedef vector<vl> vvl;
typedef vector<pl> vpl;
#define rep(i, n) for(ll i = 0; i < ll(n); i++)
#define rep2(i, k, n) for(ll i = ll(k); i <= ll(n); i++)
#define rep3(i, n, k) for(ll i = ll(n); i >= ll(k); i--)
#define all(v) (v).begin(), (v).end()
ll mod(ll a, ll b) {if(b == 0) return 0; return (a % b + b) % b;}
bool chmin(ll &a, ll b) {if(b < a) {a = b; return 1;} return 0;}
bool chmax(ll &a, ll b) {if(b > a) {a = b; return 1;} return 0;}
const ll INF = 1LL << 60;
const ll MOD = 1e9 + 7;
//const ll MOD = 998244353;
const ll MAX = 1e9;
const char newl = '\n';

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

  ll n;
  cin >> n;
  vl l(n);
  rep(i, n) cin >> l[i];
  
  sort(all(l));
  
  ll ans=0;
  rep2(i, 0, n-3) rep2(j, i+1, n-2) rep2(k, j+1, n-1) {
    if(l[i]==l[j] or l[j]==l[k] or l[i]+l[j]<=l[k]) continue;
    ans++;
  }
  cout << ans << newl;
  return 0;
}

Measured memory_bytes: 3596
import java.util.Arrays;
import java.util.Scanner;

public class Main {

	static long mod = 1000000007;
	static long INF = Long.MAX_VALUE;

	static long chmin(long a, long b) {
		return Math.min(a, b);
	}

	static long chmax(long a, long b) {
		return Math.max(a, b);
	}

	public static void main(String[] args) {
		// AtCoder_B
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int K = sc.nextInt();
		int P[] = new int[N];

		for(int i=0; i<N; i++) {
			P[i] = sc.nextInt();
		}

		Arrays.sort(P);

		int ans = 0;
		for(int i=0; i<K; i++) {
			ans += P[i];
		}

		System.out.println(ans);

	    // Scannerクラスのインスタンスをクローズ
		sc.close();
	}
}


Measured memory_bytes: 38780
#include <iostream>
#include <string>
using namespace std;
 
int main() {
    int a, c;
    char b;
    cin >> a >> b >> c;
    int ans = 0;
    if ( b == '+') {
        ans = a + c;
        cout << ans << endl;
    } else {
        ans = a - c;
        cout << ans << endl;
    }
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, n) for(ll i = 0, i##_len = (n); i < i##_len; i++)
#define reps(i, s, n) for(ll i = (s), i##_len = (n); i < i##_len; i++)
#define rrep(i, n) for(ll i = (n) - 1; i >= 0; i--)
#define rreps(i, e, n) for(ll i = (n) - 1; i >= (e); i--)
#define all(x) (x).begin(), (x).end()
#define sz(x) ((ll)(x).size())
#define len(x) ((ll)(x).length())

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    // ifstream in("input.txt");
    // cin.rdbuf(in.rdbuf());
    ll n, a, b;
    cin >> n >> a >> b;
    ll cnt = n / (a + b);
    ll acnt = cnt * a;
    ll remain = n % (a + b);
    acnt += min(remain, a);
    cout << acnt << endl;
    return 0;
}


Measured memory_bytes: 256
#include<algorithm>
#include<iostream>
#include<set>
#include<vector>
using namespace std;
typedef long long lint;
typedef vector<int>vi;
typedef pair<int,int>pii;
#define rep(i,n)for(int i=0;i<(int)(n);++i)

int main(){
  int n;
  cin>>n;
  vi a(n),b(n);
  set<int> s,im;
  rep(i,n)cin>>a[i];
  rep(i,n)cin>>b[i];
  rep(i,n)s.insert(a[i]);
  rep(i,n)im.insert(b[i]);
  if((int)im.size()==n){
    cout<<"Yes"<<endl;
    return 0;
  }
  int tmp=-1;
  for(int e:s){
    if(im.count(e)==0)tmp=e;
  }
  vi c(n,tmp),d(n,tmp);
  rep(i,n){
    if(a[i]==tmp){
      c[i]=a[0];
      d[i]=a[1];
    }
  }
  cout<<"No"<<endl;
  rep(i,n){
    cout<<c[i]<<(i==n-1?"\n":" ");
  }
  rep(i,n){
    cout<<d[i]<<(i==n-1?"\n":" ");
  }
}



Measured memory_bytes: 12876
/*****Here we go again!******/

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

#define pi 3.1415926535
#define endl "\n"
#define yes cout << "YES\n"
#define no cout << "NO\n"
#define ll long long
#define llu unsigned long long
#define pb push_back
#define mp make_pair
#define sz(x) (int)x.size()
#define tc int test_case; cin >> test_case; while(test_case--)
#define f(i,a,n) for(int i = a ; i < n ; i++)
#define rf(i,n,a) for(int i = n-1 ; i >= a ; i--)
#define F first
#define S second
#define all(c) (c).begin(),(c).end()
#define get(a,n) f(i,0,n) cin >> a[i];
#define show(a,n) f(i,0,n) cout << a[i] << " "; cout << endl;
#define fast ios:: sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define trace(x) cerr << '>' << #x << ':' << (x) << "\n"
#define trace2(x,y) cerr<< '>' << #x << ':' << (x) << " | " << #y << ':' << (y) << "\n"
#define trace3(a,b,c) cerr<<#a<<"="<<(a)<<", "<<#b<<"="<<(b)<<", "<<#c<<"="<<(c)<<"\n"
#define trace4(a,b,c,d) cerr<<#a<<"="<<(a)<<", "<<#b<<"="<<(b)<<", "<<#c<<"="<<(c)<<", "<<#d<<"="<<(d)<<"\n"

typedef long double ld;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<pii,int> ppi;
typedef vector<pii> vpi;
typedef map<int,int> mii;
typedef map<ll,ll> mll;

const int inf = 1e9;
const ll inf64 = 1e18;
const int mod = inf + 7;
const int N = 1e5 + 10;

ll dp[105][N];

ll ans(vi &wt, vi &val, int w, int n)
{
    if(n == 0 or w == 0)
        return 0;
    if(dp[n][w] != -1)
        return dp[n][w];
    if(wt[n-1] <= w)
        return dp[n][w] = max(val[n-1] + ans(wt, val, w-wt[n-1], n-1), ans(wt, val, w, n-1));
    else
        return dp[n][w] = ans(wt, val, w, n-1);
}

int main()
{
    fast;
    int n, w;
    cin >> n >> w;
    vi wt(n), val(n);
    f(i,0,n)
        cin >> wt[i] >> val[i];
    memset(dp,-1,sizeof dp);

    cout << ans(wt, val, w, n);
}


Measured memory_bytes: 85644
#include <iostream>
#include <cstdio>
#include <vector>
using namespace std;

int main(){
    long long n;
    cin >> n;
    string s;
    cin >> s;

    long long original_pop_count = 0;

    for(long long i = 0; i < n; i++){
        if(s[i] == '1')original_pop_count++;
    }
    long long one_pop_count = original_pop_count - 1;
    long long zero_pop_count = original_pop_count + 1;

    long long one_mod = 0, zero_mod = 0;

    for(long long i = 0; i < n; i++){
        if(one_pop_count != 0) one_mod = (one_mod*2 + (s[i]-'0')) % one_pop_count;
        zero_mod = (zero_mod*2 + (s[i]-'0')) % zero_pop_count;
    }

    //f
    vector<long long> f(220000, 0);
    vector<long long> pop_count(220000, 0);
    for(long long i = 1; i < 220000; i++){
        pop_count[i] = pop_count[i/2] + i % 2;
        f[i]  = f[i % pop_count[i]] + 1;
    }

    //pow2
    vector<long long> one_pow2(220000, 1);
    vector<long long> zero_pow2(220000, 1);

    for(long long i = 1; i < 220000; i++){
        if(one_pop_count != 0) one_pow2[i] = one_pow2[i-1] * 2 % one_pop_count;
        zero_pow2[i] = zero_pow2[i-1] * 2 % zero_pop_count;
    }
    //printf("one_mod %lld zero_mod %lld\n", one_mod, zero_mod);

    for(long long i = n-1; i >= 0; i--){
        if(s[n-1-i] == '1'){
            if(one_pop_count != 0){
                long long nxt = one_mod;
                //todo
                nxt -= one_pow2[i];
                if(nxt < 0) nxt += one_pop_count;
                nxt %= one_pop_count;
                printf("%lld\n", f[nxt]+1);
            }
            else printf("0\n");
            
        }
        else{
            long long nxt = zero_mod;
            //todo
            nxt += zero_pow2[i];
            nxt %= zero_pop_count;
            printf("%lld\n", f[nxt]+1);
        }
    }



    
    return 0;
}

Measured memory_bytes: 10500
#include <iostream>
using namespace std;
 
int main(){
  int N,t,x,y,pt=0,px=0,py=0;
  cin >> N;
  for(int i=0;i<N;i++){
    cin >> t >> x >> y;
    if(abs(x-px)+abs(y-py)>t-pt ||
       (abs(x-px)+abs(y-py)-(t-pt))%2!=0){
      cout << "No" << endl;
      return 0;
    }
    pt=t;px=x;py=y;
  }
  cout << "Yes" << endl;
  return 0;
}


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

using namespace std;

int main() {
	long long a, b, c, d, x;
	cin >> a>>b>>c>>d;
	
	cout << max(a * c, max(a * d, max(b * c, (b * d)))) << endl;

	return 0;
}

Measured memory_bytes: 3616
#define  _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <algorithm>
#include <utility>
#include <functional>
#include <cstring>
#include <queue>
#include <stack>
#include <math.h>
#include <iterator>
#include <vector>
#include <string>
#include <set>
#include <math.h>
#include <iostream>
#include <random>
#include<map>
#include <iomanip>
#include <time.h>
#include <stdlib.h>
#include <list>
#include <typeinfo>
#include <list>
#include <set>
#include <cassert>
#include<fstream>
#include <unordered_map>
#include <cstdlib>
#include <complex>
#include <cctype>
#include <bitset>
using namespace std;
typedef string::const_iterator State;
#define Ma_PI 3.141592653589793
#define eps 1e-5
#define LONG_INF 1e18
#define GOLD 1.61803398874989484820458
#define MAX_MOD 1000000007LL
#define MOD 998244353LL
#define seg_size 262144*4
#define REP(a,b) for(long long a = 0;a < b;++a)
long long gcd(long long a, long long b) {
	if (b == 0) return a;
	return gcd(b, a % b);
}
long long tmp[10100];
int main() {
	int n;
	cin >> n;
	long long hoget = 0;
	vector<long long> inputs;
	n++;
	REP(q, n) {
		int hoge;
		cin >> hoge;
		inputs.push_back(hoge);
		hoget = gcd(abs(hoge), hoget);
	}
	reverse(inputs.begin(), inputs.end());
	set<long long> kouho;
	REP(i, 30000) {
		kouho.insert(i + 2);
	}
	for (int i = 1; i <= sqrt(hoget); ++i) {
		if (hoget % i == 0) {
			kouho.insert(i);
			if (i * i != hoget) kouho.insert(hoget / i);
		}
	}
	for(auto i = kouho.begin();i != kouho.end();++i){
		int now = *i;
		if (now == 1) continue;
		int ok = 1;
		for (int i = 2; i <= sqrt(now); ++i) {
			if (now % i == 0) {
				ok = 0;
				break;
			}
		}
		if (ok == 0) continue;
		if (inputs[0] % now != 0) continue;
		REP(q, 10100) {
			tmp[q] = 0;
		}
		REP(q, n) {
			tmp[q % (now - 1)] += inputs[q];
		}
		REP(q, n) {
			if (tmp[q % (now - 1)] % now != 0) {
				ok = 0;
				break;
			}
		}
		if (ok == 1) {
			cout << now << endl;
		}
	}
}

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

int main(){
int x1,y1,x2,y2;
  cin>>x1>>y1>>x2>>y2;

  cout<< x2-(y2-y1) <<endl;  // ひし形の正方形をモデルにして、
  cout<< y2+(x2-x1) <<endl;  // 対角線を繋げると式を計算できる
  cout<< x1-(y2-y1) <<endl;
  cout<< y1+(x2-x1) <<endl;
  
}

Measured memory_bytes: 256
// ABC-142 D:
// 2019.9.28 bal4u
// Template for Online Contest

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>

typedef long long ll;

#define SIZE  1000
int size;
int factor[SIZE];

int ptbl[] = {
         3,   5,   7,  11,  13,  17,  19,  23,  29,
   31,  37,  41,  43,  47,  53,  59,  61,  67,  71,
   73,  79,  83,  89,  97, 101, 103, 107, 109, 113,
  127, 131, 137, 139, 149, 151, 157, 163, 167, 173,
  179, 181, 191, 193, 197, 199, 211, 223, 227, 229,
  233, 239, 241, 251, 257, 263, 269, 271, 277, 281,
  283, 293, 307, 311, 313, 317, 331, 337, 347, 349,
  353, 359, 367, 373, 379, 383, 389, 397, 401, 409,
  419, 421, 431, 433, 439, 443, 449, 457, 461, 463,
  467, 479, 487, 491, 499, 503, 509, 521, 523, 541,
  547, 557, 563, 569, 571, 577, 587, 593, 599, 601,
  607, 613, 617, 619, 631, 641, 643, 647, 653, 659,
  661, 673, 677, 683, 691, 701, 709, 719, 727, 733,
  739, 743, 751, 757, 761, 769, 773, 787, 797, 809,
  811, 821, 823, 827, 829, 839, 853, 857, 859, 863,
  877, 881, 883, 887, 907, 911, 919, 929, 937, 941,
  947, 953, 967, 971, 977, 983, 991, 997, 0 };

void prime_factor(ll n)
{
  int i, d;
  int *pp;

  size = 0;
  if ((n & 1) == 0) {
    factor[size++] = 2;
    do n >>= 1;
    while ((n & 1) == 0);
  }
  for (pp = ptbl; n > 1 && *pp > 0; pp++) {
    if (n % *pp) continue;
    d = *pp;
    factor[size++] = d;
    do n /= d;
    while (n % d == 0);
  }
  if (n > 1) {
    int b = (int)sqrt((double)n);
    for (i = 1009; n > 1; i+=2) {
      if (i > b) {
        factor[size++] = n;
        break;
      }
      if (n % i == 0) {
        factor[size++] = i;
        do n /= i;
        while (n % i == 0);
      }
    }
  }
}

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

int main()
{
	ll A, B, g;
	int i, b;
	
	scanf("%lld%lld", &A, &B);
	g = gcd(A, B);
	prime_factor(g);
	printf("%d\n", size+1);
	return 0;
}


Measured memory_bytes: 128
#define _CRT_SECURE_NO_WARNINGS
#define _USE_MATH_DEFINES

#include "bits/stdc++.h"
#define REP(i,a,b) for(int i=a;i<b;++i)
#define rep(i,n) REP(i,0,n)
#define ll long long
#define ull unsigned ll
typedef long double ld;
#define ALL(a) (a).begin(),(a).end()
#define ifnot(a) if(not a)
#define dump(x)  cerr << #x << " = " << (x) << endl
using namespace std;

void reader(int &a) { scanf("%d", &a); }
void reader(double &a) { scanf("%lf", &a); }
void reader(char a[]) { scanf("%s", a); }
void reader(char &a) { scanf(" %c", &a); }
void reader(ll &a) { scanf("%lld", &a); }
void reader(ull &a) { scanf("%llu", &a); }
// void reader(string& a){cin >> a;};
template<class T, class U> void reader(T& t, U& u) { reader(t); reader(u); }
template<class T, class U, class V> void reader(T& t, U& u, V& v) { reader(t); reader(u); reader(v); }

void writer(const int a, char c) { printf("%d", a); putchar(c); }
void writer(const ll a, char c) { printf("%lld", a); putchar(c); }
void writer(const ull a, char c) { printf("%llu", a); putchar(c); }
void writer(const double a, char c) { printf("%.20lf", a); putchar(c); }
void writer(const char a[]) { printf("%s", a); };
void writer(const char a[], char c) { printf("%s", a); putchar(c); };
void writer(const char a, char c) { putchar(a); putchar(c); };
template<class T> void writerLn(T t) { writer(t, '\n'); }
template<class T, class U> void writerLn(T t, U u) { writer(t, ' '); writer(u, '\n'); }
template<class T, class U, class V> void writerLn(T t, U u, V v) { writer(t, ' '); writer(u, ' '); writer(v, '\n'); }
template<class T> void writerArr(T x[], int n) { int i; if (!n) { putchar('\n'); return; }rep(i, n - 1) writer(x[i], ' '); writer(x[n - 1], '\n'); }
template<class T> void writerVec(vector<T> x) { int n = x.size(); int i; if (!n) { putchar('\n'); return; }rep(i, n - 1) writer(x[i], ' '); writer(x[n - 1], '\n'); }

vector<string> split(const string &str, char sep) { vector<string> v; stringstream ss(str); string buffer; while (getline(ss, buffer, sep)) { v.push_back(buffer); }return v; }
// #define int ll
bool test = 1;
int dx[] = { 0,1,0,-1 };
int dy[] = { 1,0,-1,0 };
#define MAX 300000
//.....................
ull mod = (int)1e9 + 7;

signed main(void)
{
	while (1) {
		int n, m;
		cin >> n >> m;
		if (n == 0 && m == 0) break;
		int a[100];
		int asum = 0;
		rep(i, n) {
			reader(a[i]);
			asum += a[i];
		}
		set<int> b;
		int bsum = 0;
		rep(i, m) {
			int buf;
			reader(buf);
			bsum += buf;
			b.insert(buf);
		}
		int a1 = 10000;
		int b1 = 10000;
		int target = bsum - asum;
		if (abs(target) % 2 == 0) {
			int d = abs(target) / 2;
			if (target < 0) d *= -1;
			rep(i, n) {
				auto target_b = b.find(d + a[i]);
				if (target_b != b.end()) {
					if (a[i] + *target_b < a1 + b1) {
						a1 = a[i];
						b1 = *target_b;
					}
				}
			}
		}
		if (a1 > 1000) puts("-1");
		else writerLn(a1, b1);
	}
	return 0;
}

Measured memory_bytes: 3124
#define _USE_MATH_DEFINES
#include <cstdio>
#include <iostream>
#include <sstream>
#include <fstream>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <complex>
#include <string>
#include <vector>
#include <array>
#include <list>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <bitset>
#include <numeric>
#include <limits>
#include <climits>
#include <cfloat>
#include <functional>
#include <iterator>
#include <memory>
#include <regex>
using namespace std;

int main()
{
    int h, w, n;
    cin >> h >> w >> n;
    vector<vector<int> > v(h, vector<int>(w, -1));
    int tmp = 0;
    for(int y=0; y<h; ++y){
        for(int x=0; x<w; ++x){
            char c;
            cin >> c;
            if(c == '#'){
                ++ tmp;
                v[y][x] = tmp;
            }
        }
    }
    
    for(int y=0; y<h; ++y){
        for(int x=1; x<w; ++x){
            if(v[y][x] == -1)
                v[y][x] = v[y][x-1];
        }
        for(int x=w-2; x>=0; --x){
            if(v[y][x] == -1)
                v[y][x] = v[y][x+1];
        }
    }
    for(int x=0; x<w; ++x){
        for(int y=1; y<h; ++y){
            if(v[y][x] == -1)
                v[y][x] = v[y-1][x];
        }
        for(int y=h-2; y>=0; --y){
            if(v[y][x] == -1)
                v[y][x] = v[y+1][x];
        }
    }
    
    for(int y=0; y<h; ++y){
        cout << v[y][0];
        for(int x=1; x<w; ++x)
            cout << ' ' << v[y][x];
        cout << endl;
    }

    return 0;
}


Measured memory_bytes: 1152
/*
 ABC-166
 */
#pragma warning(disable:4996)
#pragma comment(linker, "/STACK:336777216")
#pragma GCC optimize("Ofast")

#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <functional>

using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
#define int long long int
typedef complex<long double> cd;
const long double pi=acos(-1);
typedef double db;
typedef long double ldb;
typedef pair <int, int> pii;
typedef pair <db, db> pdd;
typedef vector<int> vi;
typedef vector<vector<int> > matrix;

#define m1 make_pair
#define pb push_back
#define flush fflush(stdout)
#define IOS std::ios::sync_with_stdio(false); cin.tie(NULL);cout.tie(NULL);
#define reset(x,v) memset(x,v,sizeof(x))

#define fi first
#define se second
#define endl "\n"
#define debug(x) (cerr << #x << ": " << x << "\n")
#define setbits(x) __builtin_popcount(x)
#define setbitsll(x) __builtin_popcountll(x)
#define all(x) x.begin(),x.end()
#define pii pair<int,int>

inline ll gcd(ll a,ll b){if(a==0) return b;return gcd(b%a,a);}
inline ll power(ll a,ll n,ll m){if(n==0)return 1;ll p=power(a,n/2,m);p=(p%m*p%m)%m;if(n%2) return (p%m*a%m)%m;else return p;}
const ll MOD =998244353;
const ll hell=1000000007;
const int INF = 1e17;
const ll LL_INF = 0x3f3f3f3f3f3f3f3f;
typedef tree<int, null_type, less<int>, rb_tree_tag,
tree_order_statistics_node_update>
ordered_set;

double startTime;
double getCurrentTime() {
    return ((double)clock() - startTime) / CLOCKS_PER_SEC;
}

const int N=300005;


void solve()
{
    
    int n;
    cin>>n;
    int m;
    cin>>m;
    int h[n+1];
    for(int i=1;i<=n;i++)
        cin>>h[i];
    int mx[n+1]={0};int u,v;
    for(int i=0;i<m;i++)
    {
        cin>>u>>v;
        mx[u]=max(mx[u],h[v]);
        mx[v]=max(mx[v],h[u]);
    }
    int ans=0;
    for(int i=1;i<=n;i++)
        if(h[i]>mx[i])
            ans++;
    cout<<ans<<endl;

}

int32_t main()
{
    IOS;
    // startTime=clock();
    int t;
    t=1;
    //cin>>t;
    while(t--)
    {
        solve();
    }
    // cout<<getCurrentTime()<<endl;
    return 0;
}



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

int main(void){
	int n;
	cin >> n;
	for(int i=0;i<n;++i){
		int k,p;
		cin >> k >> p;
		int ans=k%p;
		if(ans==0) ans=p;
		cout << ans << endl;
	}
	return 0;
}

Measured memory_bytes: 1164
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N = 3e5 + 5, mod = 1e9 + 7;
int read() {
	int x = 0, f = 1; char ch;
	while(! isdigit(ch = getchar())) (ch == '-') && (f = -f);
	for(x = ch ^ 48; isdigit(ch = getchar()); x = (x << 3) + (x << 1) + (ch ^ 48));
	return x * f;
}
template <class T> T Max(T a, T b) { return a > b ? a : b; }
template <class T> T Min(T a, T b) { return a < b ? a : b; }
char s[N];
LL n, ans, f[N][3][3];
void add(LL &x, LL y) {x += y; if(x >= mod) x -= mod;}
int main() {
	scanf("%s", s + 1); n = strlen(s + 1); f[0][0][0] = 1;
	for(int i = 1; i <= n; ++ i) for(int j = 0; j <= 2; ++ j) {
		for(int k = 0; k <= 2; ++ k) {
			if(s[i] != '0') {
				if(k) add(f[i][j][k - 1], f[i - 1][j][k]);
				else add(f[i][min(j + 1, 2)][k], f[i - 1][j][k]);
			}
			if(s[i] != '1') {
				if(k == 2) add(f[i][j][1], f[i - 1][j][k]);
				else add(f[i][j][k + 1], f[i - 1][j][k]);
			}
		}
	}
	for(int i = 0; i <= 2; ++ i) for(int j = 0; j <= i; ++ j) add(ans, f[n][i][j]);
	printf("%lld\n", ans);
	return 0;
}

Measured memory_bytes: 21632
function Main(input) {
    var payment = parseInt(input);
    if (payment % 1000 == 0) {
        console.log(0);
    } else {
        console.log(1000 - payment % 1000);
    }
}
//*この行以降は編集しないでください（標準入出力から一度に読み込み、Mainを呼び出します）
Main(require("fs").readFileSync("/dev/stdin", "utf8"));

Measured memory_bytes: 29588
#include<cstdio>
const int MaxN=510;
int N,u[MaxN][MaxN],l[MaxN][MaxN],r[MaxN][MaxN];
char A[MaxN][MaxN];
int S[MaxN];
int min(int a,int b){return a<b?a:b;}
int max(int a,int b){return a>b?a:b;}
bool d(char c){return c>='0'&&c<='9';}
int main(){
	scanf("%d",&N);
	for(int i=1;i<=N;i++)scanf("%s",A[i]+1);
	for(int i=0;i<=N;i++)
		for(int j=0;j<=N;j++)u[i][j]=d(A[i][j])?min(i,min(u[i-1][j],u[i][j-1])):1<<30;
	long long ans=0;
	for(int x=1;x<=N;x++){
		for(int i=x;i;i--){
			for(int j=1;j<=N;j++)S[j]=S[j-1]+(u[x][j]<=i?A[x][j]-'0':0);
			for(int j=N+1;j;j--){
				l[i][j]=1<<30;r[i][j]=-1;
				if(d(A[i][j])){
					if(i<x){
						l[i][j]=min(l[i][j],l[i+1][j]);
						r[i][j]=max(r[i][j],r[i+1][j]);
					}
					else l[i][j]=r[i][j]=j;
					l[i][j]=min(l[i][j],l[i][j+1]);
					r[i][j]=max(r[i][j],r[i][j+1]);
				}
				if(l[i][j]<=r[i][j])ans+=(A[i][j]-'0')*(S[r[i][j]]-S[l[i][j]-1]-(i==x?A[i][j]-'0':0));
			}
		}
	}
	printf("%lld\n",ans);
}

Measured memory_bytes: 3456
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define fi first
#define se second

int n, a[100005], sum, m[100005];
signed main(){
	cin >> n;
	for(int i = 1 ; i <= n ; i ++){
		cin >> a[i];
		a[i]*= 2;
		sum += a[i];
	}
	sum /= 2;
	int pre = 0;
	for(int i = 2 ; i < n ; i += 2)
		pre += a[i];
	m[1] = sum - pre;
	for(int i = 2 ; i <= n ; i ++)
		m[i] = a[i - 1] - m[i - 1];
	for(int i = 1 ; i <= n ; i ++)
		cout << m[i] << " ";
	
}

Measured memory_bytes: 2816
#include <iostream>
#include <math.h>
using namespace std;
int main(void){
    int n, student[1000]={}, diff, tmp_diff;
    while(1){
        cin >> n;
        if(n==0) break;
        
        diff=1000000;
        for(int i=0;i<n; i++){
            cin >> student[i];
        }
        for(int i=0; i<n-1; i++){
            for(int j=i+1; j<n; j++){
                tmp_diff=abs(student[i]-student[j]);
                if(tmp_diff < diff){
                    diff = tmp_diff;
                }
            }
        }
        cout << diff << endl;
    }
}



Measured memory_bytes: 3068
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using vl = vector<ll>;
using vvl = vector<vl>;

int main(){
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  ll n;
  cin >> n;
  if(n%2 == 1){
    cout << 0 << endl;
    return 0;
  }
  ll ans = 0;
  ll waru = 5;
  while(waru <= n){
    ans += n/waru/2;
    waru *= 5;
  }
  cout << ans << endl;
}

Measured memory_bytes: 3688
n, m, q = map(int, input().split())
abcd = []
x = [1]
ans = 0
for _ in range(q):
    abcd.append(list(map(int, input().split())))
    
def dfs(s):
    global ans
    if len(s) == n+1:
        now = 0
        for a, b, c, d in abcd:
            if s[b] - s[a] == c:
                now += d
        ans = max(ans, now)
        return
    p = s[-1]
    while p <= m:
        s.append(p)
        dfs(s)
        p = s.pop() + 1

dfs(x)
print(ans)

Measured memory_bytes: 9220
import java.math.*

fun main(args: Array<String>) {
    val (N, x) = readInputLine().split(" ").map { it.toInt() }
    val aList = readInputLine().split(" ").map { it.toInt() }
    
    var bef = Math.min(aList.first(), x)
    var ans = if (aList.first() > x) (aList.first() - x).toLong() else 0L
    
    for (a in aList.drop(1)) {
        if (a + bef > x) {
            ans += (a + bef - x).toLong()
            bef = x - bef
        } else {
            bef = a
        }
    }

    println(ans)
}

fun readInputLine(): String {
    return readLine()!!
}



Measured memory_bytes: 74104
from collections import deque

H,W = map(int,input().split())
c =[]
c.append(['×' for _ in range(W+2)])
ans = []
ans.append([0 for _ in range(W+2)])
q = deque()
for i in range(H):
    tmp = list('×'+input()+'×')
    ans_tmp = []
    for j in range(W+2):
        if tmp[j] == '#':
            ans_tmp.append(0)
            q.append([j,i+1])
        elif tmp[j] == '×':
            ans_tmp.append(0)
        else:
            ans_tmp.append(10**4)
    c.append(tmp)
    ans.append(ans_tmp)

c.append(['×' for _ in range(W+2)])
ans.append([0 for _ in range(W+2)])


def bfs(q):
    while q:
        x,y = q.popleft()
        if c[y][x-1] == '.':
            q.append([x-1,y])
            ans[y][x-1] = ans[y][x] + 1
            c[y][x-1] = '#'
        if c[y][x+1] == '.':
            q.append([x+1,y])
            ans[y][x+1] = ans[y][x] + 1
            c[y][x+1] = '#'
        if c[y-1][x] == '.':
            q.append([x,y-1])
            ans[y-1][x] = ans[y][x] + 1
            c[y-1][x] = '#'
        if c[y+1][x] == '.':
            q.append([x,y+1])
            ans[y+1][x] = ans[y][x] + 1
            c[y+1][x] = '#'

bfs(q)
max_ans = 0
for i in range(H+2):
    #print(ans[i])
    max_ans = max(max_ans,max(ans[i]))

print(max_ans)


Measured memory_bytes: 185180
nk = input()
nk = nk.split()
n = int(nk[0])
k = int(nk[1])
trees = []
for i in range(n):
  trees.append(int(input()))
trees.sort()
minimum = 1000000000
i = 0
while i<=n-k:
  if trees[i+k-1]-trees[i]<minimum:
    minimum = trees[i+k-1]-trees[i]
  i+=1
print(minimum)

Measured memory_bytes: 51544
#include <stdlib.h>
#include <iostream>
#include <iomanip>
#include <string>
#include <limits.h>
#include <math.h>
#include <vector>
#include <algorithm>
#include <map>
#include <numeric>
#include <cstdlib>
#include <functional>

using namespace std;

int main(int argc, char* argv[]){
	string a;
	cin >> a;
	if (a[0]=='Y' && a[1]=='A' && a[2] == 'K' && a[3] == 'I'){
		cout << "Yes" << endl;
	}
	else{
		cout << "No" << endl;
	}

    return 0;
}


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

int main(){
    string expr;
    while( cin>>expr ){
        long long int n[3] = {0, 0, 0}, x[3] = {0, 0, 0};
        string::iterator it = expr.begin();
        int i = 0;
        while( true ){
            n[i] *= 10; x[i] *= 10;
            if( isdigit(*it) ) n[i] += *it-'0';
            if( *it == 'X' ) x[i] += 1;
            it++;
            if( it == expr.end() ) break;
            if( *it == '+' || *it == '=' ){
                it++; i++;
            }
        }
        int b = 0;
        for(i = 0; i < 3; i++){
            if( x[i]>=10 && x[i]>n[i] ) b = 1;
        }
        for(i = b; i < 10; i++){
            if( n[0]+n[1]-n[2]+(x[0]+x[1]-x[2])*i == 0 ){
                cout << i << endl;
                break;
            }
        }
        if( i == 10 ) cout << "NA" << endl;
    }
    return 0;
}

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

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

    int K[32] = {1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51};

    int k;
    cin>>k;

    cout<<K[k-1]<<endl;


    return 0;
}

Measured memory_bytes: 256