akhauriyash/Code-Regression huggingface dataset:
using System;
using System.Collections.Generic;
using System.Text;
using System.Linq;

class Program
{
    void solve()
    {
        int N = int.Parse(Console.ReadLine());
        string s = Console.ReadLine();

        //byte[] said = new byte[N];
        //byte[,] who = new byte[4, N];
        char[][] who = new char[4][];
        who[0] = new char[N];
        who[1] = new char[N];
        who[2] = new char[N];
        who[3] = new char[N];

        who[0][0] = 'S'; who[0][N - 1] = 'S';
        who[1][0] = 'S'; who[1][N - 1] = 'W';
        who[2][0] = 'W'; who[2][N - 1] = 'S';
        who[3][0] = 'W'; who[3][N - 1] = 'W';


        //for (int i = 0; i < N; ++i)
        //    said[i] = (byte)(s[i] == 'o' ? 0 : 1);

        for (int i = 0; i < N; ++i)
        {
            for (int j = 0; j < 4; ++j)
            {
                who[j][(i + 1) % N] = ((s[i] == 'o' ? 0 : 1) ^ (who[j][(N + i - 1) % N] == 'S' ? 0 : 1) ^ (who[j][i] == 'S' ? 0 : 1)) == 1 ? 'W' : 'S';
            }
        }

        int k = -1;
        if (who[0][0] == 'S' && who[0][N - 1] == 'S')
            k = 0;
        else if (who[1][0] == 'S' && who[1][N - 1] == 'W')
            k = 1;
        else if (who[2][0] == 'W' && who[2][N - 1] == 'S')
            k = 2;
        else if (who[3][0] == 'W' && who[3][N - 1] == 'W')
            k = 3;

        string ans = string.Empty;
        if (k == -1)
        {
            ans = "-1";
        }
        else
        {
            ans = string.Join("", who[k]);
        }
        Console.WriteLine(ans);
    }
    public static int Main()
    {
        bool loop = false;
#if ES_DEBUG
        loop = true;
#endif
        do
        {
            new Program().solve();
        } while (loop);
        return 0;
    }
}


Measured memory_bytes: 14944
def gcd(a,b,i):
	return (a,i) if b == 0 else gcd(b,a%b,i+1)
while 1:
	n,m = sorted(map(int,raw_input().split()),reverse = True)
	if n == m == 0: break
	g,i = gcd(n,m,0)
	print g,i

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

using namespace std;

// 辺を表す構造体 (行き先、容量、逆辺)
struct edge { int to, cap, rev; };
vector<edge> G[2000]; // グラフの隣接リスト表現
bool used[2000]; // DFSですでに調べたかのフラグ
				  // fromからtoへ向かう容量capの辺をグラフに追加する
void add_edge( int from, int to, int cap ) {
	edge a, b;
	a.to = to;
	a.cap = cap;
	a.rev = G[to].size();
	G[from].push_back( a );
	b.to = from;
	b.cap = cap;
	b.rev = G[from].size() - 1;
	G[to].push_back( b );
}
// 増加パスをDFSで探す
int dfs( int v, int t, int f ) {
	if( v == t ) return f;
	used[v] = true;
	for( int i = 0; i < G[v].size(); i++ ) {
		edge &e = G[v][i];
		if( !used[e.to] && e.cap > 0 ) {
			int d = dfs( e.to, t, min( f, e.cap ) );
			if( d > 0 ) {
				e.cap -= d;
				G[e.to][e.rev].cap += d;
				return d;
			}
		}
	}
	return 0;
}
// sからtへの最大流を求める
int max_flow( int s, int t ) {
	int flow = 0;
	for( ;;) {
		memset( used, 0, sizeof( used ) );
		int f = dfs( s, t, INT_MAX / 6 );
		if( f == 0 ) return flow;
		flow += f;
	}
}

int main() {
	int H, W;
	cin >> H >> W;
	vector<string>S( H );
	int start, goal;
	for( size_t i = 0; i < H; i++ ) {
		cin >> S[i];
		for( size_t j = 0; j < W; j++ ) {
			if( S[i][j] != '.' ) {
				add_edge( i + W, j, 1 );
				if( S[i][j] == 'S' ) {
					start = i*W + j;
					add_edge( H + W + 1, i + W, 1000 );
					add_edge( H + W + 1, j, 10000 );
				} else if( S[i][j] == 'T' ) {
					goal = i*W + j;
					add_edge( H + W + 2, i + W, 1000 );
					add_edge( H + W + 2, j, 1000 );
				}
			}
		}
	}
	if( start / W == goal / W || start%W == goal%W ) {
		cout << -1 << endl;
		return 0;
	}
	cout << max_flow( H + W + 1, H + W + 2 ) << endl;
}

Measured memory_bytes: 640
n = int(input())
a_list = list(map(int, input().split()))

step_ttl = 0
step = 0
for i, a in enumerate(a_list):
  if i == 0:
    continue
  if a_list[i-1] + step < a:
    step = 0
    continue
  if a < step + a_list[i-1]:
    step = (step + a_list[i-1]) - a
  step_ttl += step

print(step_ttl)

Measured memory_bytes: 32152
#include <bits/stdc++.h>
#define rep(i, a, b) for (int i = a; i < (b); i++)
#define rrep(i, a, b) for (int i = a; i >= b; i--)
#define all(x) (x).begin(), (x).end()
using namespace std;
using llong = long long;
using P = pair<int, int>;
const int inf = 1 << 20;
const int mod = 1e9 + 7;

int main() {
   llong n, a, b;
   cin >> n >> a >> b;
   llong ans = n / (a + b) * a;
   llong c = n % (a + b);
   if (a == 0) {
      cout << 0 << endl;
      return 0;
   }
   if (c >= a)
      ans += a;
   else
      ans += c;
   cout << ans << endl;
   return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
    int N, L;
    cin >> N >> L;
    int s = (2*L+N-1)*N/2;
    if ( L > 0 ) s -= L;
    if ( L + N - 1 < 0 ) s -= L + N - 1;
    cout << s << '\n';
    return 0;
}

Measured memory_bytes: 256
#include <stdio.h>
 
int main() {
	int n, a;
	float x, t;
	scanf("%d", &n);
	if (n >= 1 && n <= 50000) {
		x = n / 1.08;
		t = (int)x;
		a = t * 1.08;
		if (a == n) {
			a = t;
			printf("%d", a);
		}
		else {
			t++;
			a = t * 1.08;
			if (a == n) {
				a = t;
				printf("%d", a);
			}
			else {
				printf(":(");
			}
		}
 
	}
	else {
		printf(":(");
	}
 
}

Measured memory_bytes: 128
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

template<typename T>
struct CumulativeSum2D {
    vector<vector<T>> acc;
    CumulativeSum2D(int h = 0, int w = 0) : acc(h + 1, vector<T>(w + 1)) { }
    void add(int i, int j, T x) { acc[i + 1][j + 1] += x; }
    void build() {
        int h = acc.size(), w = acc[0].size();
        for (int i = 1; i < h; i++) for (int j = 1; j < w; j++) {
            acc[i][j] += acc[i][j - 1] + acc[i - 1][j] - acc[i - 1][j - 1];
        }
    }
    T sum(int si, int ti, int sj, int tj) {     // [si, ti) x [sj, tj)
        return acc[ti][tj] - acc[si][tj] - acc[ti][sj] + acc[si][sj];
    }
};

int main() {
    int n, m; cin >> n >> m;
    int q; cin >> q;
    CumulativeSum2D<int> acc(n + 1, n + 1);
    while (m--) {
        int l, r; cin >> l >> r;
        acc.add(l, r, 1);
    }
    acc.build();
    while (q--) {
        int l, r; cin >> l >> r;
        cout << acc.sum(l, r + 1, l, r + 1) << endl;
    }
    return 0;
}


Measured memory_bytes: 1920
#include <stdio.h>
#include <string>
#include <cstring>
#include <stdlib.h>
#include <math.h>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <list>
#include <iterator>
#include <assert.h>
#pragma warning(disable:4996) 
 
typedef long long ll;
#define MIN(a, b) ((a)>(b)? (b): (a))
#define MAX(a, b) ((a)<(b)? (b): (a))
#define LINF 9223300000000000000
#define INF 2140000000
const long long MOD = 1000000007;
//const long long MOD = 998244353;

using namespace std;

int main(int argc, char* argv[])
{
    int n;
    scanf("%d", &n);
    vector<int> p(n),q(n);
    int i;
    for(i=0; i<n; i++) {
        scanf("%d", &p[i]);
    }
    for(i=0; i<n; i++) {
        scanf("%d", &q[i]);
    }
    if(p>q) swap(p,q);

    int cnt=0;
    do {
        if(p==q) break;
        cnt++;
    } while( next_permutation(&p[0]+0, &p[0]+n));

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

    return 0;
}



Measured memory_bytes: 256
import Control.Monad
import Data.List
import Data.Maybe
import qualified Data.Set as S
import qualified Data.ByteString.Char8 as B

main :: IO ()
main = do
    n <- read <$> getLine :: IO Int
    ns <- replicateM n (fst . fromJust . B.readInt <$> B.getLine)
    print . S.size $ foldl (\s x -> if S.member x s then S.delete x s else S.insert x s) S.empty ns


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

int main() {
  int N; cin >> N;
  ll ans = 0, sum = 0;
  map<ll, ll> mp; mp[0] = 1;
  for (int i = 0; i < N; ++i) {
    int A; cin >> A;
    sum += A;
    ans += mp[sum];
    mp[sum] = (mp.find(sum) != end(mp)) ? mp[sum] + 1 : 1;
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 12800
#include"stdio.h"
int main(){
    int N,r=0,g=0,b=0,i,j;
  	long res=0;
    char S[5000];
    scanf("%d%s",&N,S);
    for(i=0;i<N;i++){
        if(S[i]=='R') r++;
        if(S[i]=='G') g++;
        if(S[i]=='B') b++;
    }
    res=r*g;
  	res*=b;
  	//printf("%d %d %d\n",r,g,b);
    for(i=0;i<N-2;i++){
        for(j=i+1;j<N-1;j++){
            int k=2*j-i;
            if(S[i]!=S[j]&&S[i]!=S[k]&&S[j]!=S[k]&&k<N){
                res--;
            }
        }
    }
    printf("%ld",res);
    return 0;
}


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

using namespace std;

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

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

int main() {
  int H, W; cin >> H >> W;
  vector<vector<int>> c(10, vector<int>(10));
  rep(i, 10) cin >> c[i];
  rep(k, 10) rep(i, 10) rep(j, 10) {
    minimize(c[i][j], c[i][k] + c[k][j]);
  }
  vector<vector<int>> A(H, vector<int>(W));
  rep(i, H) cin >> A[i];
  int count = 0;
  rep(i, H) rep(j, W) if (A[i][j] > -1) {
    count += c[A[i][j]][1];
  }
  cout << count << "\n";
}


Measured memory_bytes: 384
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0; i<n; i++)
#define REP(i,m,n) for(ll i=(ll)(m);i<(ll)(n);i++)
long long mo = 1e9 + 7;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> Pii;
typedef pair<ll,ll> Pll;
template<class T, class S> void cmin(T &a, const S &b) { if (a > b)a = b; }
template<class T, class S> void cmax(T &a, const S &b) { if (a < b)a = b; }
template<class A>void PR(A a,ll n){rep(i,n){if(i)cout<<' ';cout<<a[i];}cout << "\n";}
ld PI=3.14159265358979323846;

int main(){
    string S;
    cin >> S;
    ll N = S.size();
    vector<ll> dp(N+1),memo(N);
    memo[N-1] = 1;
    for(ll i=N-1;i>=1;i--){
        memo[i-1] = (memo[i]*10)%2019;
    }
    dp[N] = 0;
    map<ll,ll> mp;
    mp[0]++;
    for(ll i=N-1;i>=0;i--){
        ll c = S[i] - '0';
        dp[i] = (c*memo[i] + dp[i+1])%2019;
        mp[dp[i]]++;
    }
    ll ans = 0;
    for(auto& e:mp){
        ans += e.second*(e.second-1)/2;
    }
    cout << ans << endl;
}


Measured memory_bytes: 6804
//in the name of ALLAH
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
    ll n;
    cin>>n;
    ll a[n],temp[n];
    for(int i=0; i<n; i++)
    {
        cin>>a[i];

    }
    sort(a,a+n);
    ll c=0;
    if(a[0]==1)
    {
        int l=lower_bound(a,a+n,a[0])-a;
        int u=upper_bound(a,a+n,a[0])-a;
        int co=u-l;
        if(co>1)
            c=0;
        else
            c=1;
    }
    else
    {
        for(int i=0; i<n; i++)
        {
            int l=lower_bound(a,a+n,a[i])-a;
            int u=upper_bound(a,a+n,a[i])-a;
            int co=u-l;
            if(co>1)
                i+=co-1;
            else
            {
                if(i==0)
                    c++;
                else
                {
                    bool f=1;
                    //cout<<a[i]<<endl;
                    for(int j=2; j<=sqrt(a[i]); j++)
                    {
                        if(a[i]%j==0)
                        {
                            if(binary_search(a,a+n,j))
                            {
                                //cout<<"in1"<<endl;
                                f=0;
                                break;
                            }
                            else  if(binary_search(a,a+n,a[i]/j))
                            {
                                //cout<<"in2"<<endl;
                                f=0;
                                break;
                            }

                        }

                    }
                    if(f==1)
                        c++;
                }
            }
        }
    }
    cout<<c<<endl;

}



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

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

const int mod =  1000000007;  //出力は (ans % mod + mod) % mod  (負の剰余を正にする)
const int inf = 1e9;
const long long INF = 1LL << 60;

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

int main()
{
    int n; cin >> n;
    ll ans = 0;
    for(int c = 1; c < n; c++){
        ll ab = n-c;
        if(ab == 1) ans++;
        else{
            map<ll,ll> mp = prime_factors(ab);
            int cnt = 1;
            for(auto i : mp){
                cnt *= (i.second+1);
            }
            ans += cnt;
        }
    }
    cout << ans << endl;
}

Measured memory_bytes: 3628
#include<bits/stdc++.h>
#pragma GCC optimize("Ofast")
using namespace std;
#include<ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> indexed_set;

#define endl            "\n"
#define forn(i,x,n)     for(int i=x; i<n; i++)
#define forit(it, m)    for(decltype(m)::iterator it = m.begin(); it!=m.end(); ++it)
#define ff              first
#define ss              second
#define int             long long
#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 inf             1e18
#define ps(x,y)         fixed<<setprecision(y)<<x
#define mk(arr,n,type)  type *arr=new type[n];
#define w(x)            int x; cin>>x; while(x--)
mt19937                 rng(chrono::steady_clock::now().time_since_epoch().count());


void zeus()
{
    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
}
int fast_pow(long long base, long long n, long long M)
{
    if (n == 0)
        return 1;
    if (n == 1)
        return base;
    long long halfn = fast_pow(base, n / 2, M);
    if (n % 2 == 0)
        return ( halfn * halfn ) % M;
    else
        return ( ( ( halfn * halfn ) % M ) * base ) % M;
}
int32_t main() {

    zeus();

    int x;

    cin >> x;

    if (x >= 30) {
        cout << "Yes" << endl;
    }
    else {
        cout << "No" << endl;
    }

}

Measured memory_bytes: 3632
import java.util.*;
import static java.lang.Math.*;

public class Main{
    public static int gcd(int a, int b){
        if(b == 0) return a;
        else return gcd(b , a%b);
    } 
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int a[] = new int[n];
        for(int i=0; i<n; i++){
            a[i] = sc.nextInt();
        }
        int left[] = new int[n+1];
        int right[] = new int[n+1];
        for(int i=0; i<n; i++){
            left[i+1] = gcd(left[i],a[i]);
        }

        for(int i=n-1; i >= 0; i--){
            right[i] = gcd(right[i+1], a[i]);
        }
        int gcd_max = 0;
        for(int i=0; i<n; i++){
            gcd_max = max(gcd(left[i],right[i+1]),gcd_max);
        }
        System.out.println(gcd_max);

    }
}

Measured memory_bytes: 51120
#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
#include <cmath>
#include <deque>
#include <iterator>
#include <map>
#include <queue>
#include <string>
#include <tuple>
#include <utility>
#include <limits>
#include <iomanip>
using namespace std;

using ll=long long;
template<class T> using V = vector<T>;
template<class T, class U> using P = pair<T, U>;
using vll = V<ll>;
using vvll = V<vll>;
#define rep(i, k, n) for (ll i=k; i<(ll)n; ++i)
#define REP(i, n) rep(i, 0, n)
template<class T> inline bool chmax(T& a, T b) {if (a<b) {a=b; return true;} return false;}
template<class T> inline bool chmin(T& a, T b) {if (a>b) {a=b; return true;} return false;}

const ll MOD = 1000000007;
const ll HIGHINF = (ll)1e18;

int main() {
  string s; cin >> s;
  vll abc(3, 0);
  REP(i, s.size()) abc[s[i] - 'a']++;
  sort(abc.begin(), abc.end());
  if (abc[2]-abc[0] <= 1) cout << "YES" << endl;
  else cout << "NO" << endl;
  return 0;
}


Measured memory_bytes: 512
#include<bits/stdc++.h>
using namespace std;
// ABC098-A-

int main(){
    int a, b;
    cin >> a >> b;
    cout << max(a + b, max(a - b, a * b)) << endl;
}
 

// ABC099-A-
/*
int main(){
    int a;
    bool okey = true;
    cin >> a ;
    if (a > 999) {
        okey = false;
        a -= 1000;
    }
    
    if (okey) {
        cout << "ABC" << endl;
    }else{
        cout << "ABD" << endl;
    }
}
*/

//ABC100-A-
/*
int main(){
    int a, b;
    cin >> a >> b;
    if (a > 8 || b > 8) {
        cout << ":(" << endl;
    }else{
        cout << "Yay!" << endl;
    }
    
}
 */
//ABC101-A-
/*
int main(){
    int ans = 0;
    for (int i = 0; i < 4; i++) {
        char s;
        cin >> s;
        if(s == '+'){
            ans++;
        }else{
            ans--;
        }
    }
    cout << ans << endl;
}
*/
//ABC102-A-
/*
int main(){
    int n;
    cin >> n;
    if (n % 2 == 0) {
        cout << n << endl;
    }else{
        cout << n * 2 << endl;
    }
}
*/
//ABC102-A-
/*
int main(){
    int a, b, c;
    cin >> a >> b >> c;
    vector<int>task;
    task = {a, b, c};
    sort(task.begin(), task.end());
    cout << task.at(2) - task.at(0) << endl;
}
*/




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

int main(void){
    int n;
    cin >> n;
    int p[n];
    for(int i = 0;i < n;i++)cin >> p[i];
    sort(p,p+n,greater<int>());
    int max = p[0],sum = 0;
    for(int i = 1;i < n;i++)sum += p[i];
    if(sum > max)cout << "Yes";
    else cout << "No";
}

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

int N;
int a[110];

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

  sort(a, a+N, greater<int>());
  int Alice = 0;
  int Bob = 0;
  for(int i = 0; i < N; ++i){
    if(i % 2 == 0){
      Alice += a[i];
    }
    else {
      Bob += a[i];
    }
  }
  cout << Alice - Bob <<endl;
}

Measured memory_bytes: 256
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {

	static BufferedReader in;
	static PrintWriter out;
	static StringTokenizer tok;

	void solve() throws IOException {
		long[] A = readArrL(3);

		if (A[0]%2==0||A[1]%2==0||A[2]%2==0) {
			out.println(0);
		} else {
			Arrays.sort(A);
			out.println(A[0] * A[1]);
		}
	}


	public static void main(String[] args) throws IOException {
		in = new BufferedReader(new InputStreamReader(System.in));
		out = new PrintWriter(System.out);
		tok = new StringTokenizer("");
		Main main = new Main();
		main.solve();
		out.close();
	}

	String readString() throws IOException {
		while (!tok.hasMoreTokens()) {
			tok = new StringTokenizer(in.readLine(), " .");
		}
		return tok.nextToken();
	}

	int readInt() throws IOException {
		return Integer.parseInt(readString());
	}

	long readLong() throws IOException {
		return Long.parseLong(readString());
	}

	double readDouble() throws IOException {
		return Double.parseDouble(readString());
	}

	int[] readArr(int n) throws IOException {
		int[] res = new int[n];
		for (int i = 0; i < n; i++) {
			res[i] = readInt();
		}
		return res;
	}

	long[] readArrL(int n) throws IOException {
		long[] res = new long[n];
		for (int i = 0; i < n; i++) {
			res[i] = readLong();
		}
		return res;
	}

	void readArr2(int[] A, int[] B) throws IOException {
		int n = A.length;
		for (int i = 0; i < n; i++) {
			A[i] = readInt();
			B[i] = readInt();
		}
	}

	void readArrL2(long[] A, long[] B) throws IOException {
		int n = A.length;
		for (int i = 0; i < n; i++) {
			A[i] = readLong();
			B[i] = readLong();
		}
	}
}


Measured memory_bytes: 8148
#include<bits/stdc++.h>
#define ll                 long long int
#define mod                1000000007
#define pi                 3.14159265358979323846264338327950288419716939937510
#define setbit(x)          __builtin_popcountll(x)
#define db                 long double
#define pp(x)              pair<x,x>
#define ff                 first
#define ss                 second
#define FIO                ios_base::sync_with_stdio(false); cin.tie(NULL);
#define tc                 ll tc; cin>>tc; for(ll number = 1 ; number <= tc ; number ++ )
#define vv(x)              vector<x>
#define pb                 push_back
#define pob                pop_back
#define pf                 push_front
#define pof                pop_front
#define endl               "\n"
#define pq                 priority_queue
#define dbg(x)             { cout<< #x << ": " << (x) << endl; }
#define dbg2(x,y)          { cout<< #x << ": " << (x) << " , " << #y << ": " << (y) << endl; }
#define bp                 ll kkk; cin >>kkk;
#define dbgArr(a,n)        cout<<"Array "<<#a<<endl; for(ll i=0 ; i<n ; i++) cout<<a[i]<<" "; cout<<endl;
#define maxE(a,n)          *max_element(a,a+n);
#define minE(a,n)          *min_element(a,a+n);
#define forn(i,s,n)        for(ll i=s ; i<n ; i++)
#define fornr(i,e,s)       for(ll i=e-1 ; i>=s ; i--)
#define arr1(a,n)          for(ll i=1;i<=n;i++){ cin>>a[i]; }
#define file freopen("input.txt","r",stdin); freopen("output.txt","w",stdout)
#define print cout<<"Case #"<<number<<": "
#define all(x) x.begin(), x.end()
ll power(ll x, ll b) {ll p = 1;while (b > 0) {if(b&1) {p = p * x; p %= mod;} b >>= 1; x *= x; x %= mod;} return p % mod;}
using namespace std;
# define INF 1e15

struct lex_compare {
    bool operator() (pp(ll) p1,pp(ll) p2){
        ll x1 = (p1.ff*(p1.ss-p1.ss/2));
        ll x2 = (p2.ff*(p2.ss-p2.ss/2));
        return x1 > x2;
    }
};

ll dfs(ll src, vv(vv(ll)) &e, bool vis[]){
    ll ans = 1;
    vis[src] = 1;
    for(auto i : e[src]){
        if(!vis[i]){
            ans += dfs(i,e,vis);
        }
    }
    return ans;
}

int main(){
    FIO;
    ll n,m; cin >> n >> m;
    vv(vv(ll)) e(n+1);
    for(int i = 0;i<m;i++){
        ll a,b; cin >> a >> b;
        e[a].pb(b);
        e[b].pb(a);
    }
    bool vis[n+1] = {0};
    ll ans = 0;
    for(int i = 1;i<=n;i++){
        if(!vis[i]){
            ans = max(ans, dfs(i,e,vis));
        }
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 23664
s1 = input()
s2 = input()
n = len(s1)
m = len(s2)
dp = [[0 for j in range(m+1)] for i in range(n+1)]
for i in range(n+1):
    dp[i][0] = i
for j in range(m+1):
    dp[0][j] = j
for i in range(1,n+1):
    for j in range(1,m+1):
        cost = 0 if s1[i-1] == s2[j-1] else 1
        dp[i][j] = min(dp[i-1][j]+1,dp[i][j-1]+1,dp[i-1][j-1]+cost)
print(dp[n][m])


Measured memory_bytes: 44016
#include <iostream>
#include <string>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <cstdlib>
#include <ctime>
#include <queue>

#define fill(v,val) fill((v).begin(), (v).end(), (val))
#define fillt(tab, n, val) fill((t), (t) + (n) ,(val))
#define MAX 100005
#define INF 9999999
#define in(a,b)  ( (b).find(a) != (b).end())
#define clr(a,b) memset((a), (b), sizeof((a)))
#define pb       push_back
#define all(a)   a.begin(), a.end()  
#define mp         make_pair
/**
*
* @Author Mehdi Maick
*/

using namespace std;

int main(int argc , char* argv[]) {
    
    long long a, b, c;
    cin >> a >> b >> c;
    if(a == b){
        cout << (a % c == 0 ? 1 : 0) << endl;
        return 0;
    }
    long long aa = min(a, b);
    long long bb = max(a, b);
    long long ans = 0LL;
    ans = (bb+1 - aa) / c + (bb%c < (aa+c-1)%c);
    cout << ans << endl;

    return 0;
}



Measured memory_bytes: 888
#include <bits/stdc++.h>
#define fi first
#define se second
#define pii pair<int,int>
#define mp make_pair
#define pb push_back
#define space putchar(' ')
#define enter putchar('\n')
#define MAXN 40005
#define eps 1e-12
//#define ivorysi
using namespace std;
typedef long long int64;
typedef unsigned int u32;
typedef double db;
template<class T>
void read(T &res) {
	res = 0;T f = 1;char c = getchar();
	while(c < '0' || c > '9') {
		if(c == '-') f = -1;
		c = getchar();
	}
	while(c >= '0' && c <= '9') {
		res = res * 10 + c - '0';
		c = getchar();
	}
	res *= f;
}
template<class T>
void out(T x) {
	if(x < 0) {x = -x;putchar('-');}
	if(x >= 10) {
		out(x / 10);
	}
	putchar('0' + x % 10);
}
int N,K;
int main() {
#ifdef ivorysi
	freopen("f1.in","r",stdin);
#endif
	read(N);read(K);
	if(K <= (N + 1) / 2) puts("YES");
	else puts("NO");
}


Measured memory_bytes: 256
import time, math
def gcd(a,b):
  while b!=0:
    a,b=b,a%b
  return a

def f(a):
    M=10**9+7
    ans, z = 0, 1
    for x in a:
        z = (z * x) // gcd(z, x)
    #print(z)
    z %= M
    for x in a:
        ans += z * pow(x, M-2, M)
        ans %= M
    return ans

n = input()
a = list(map(int, input().split()))
#a = []
#for i in range(1000):
#    a.append(1000000-i)
print(f(a))


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

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

ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }
ll lcm(ll a, ll b) { return a / gcd(a, b) * b; }

int main() {
    ios::sync_with_stdio(false);
    string s;
    cin >> s;

    if (s == "ABC") {
        cout << "ARC" << endl;
    } else {
        cout << "ABC" << endl;
    }

    return 0;
}


Measured memory_bytes: 3656
#include<stdio.h>
#include<math.h>
#include<algorithm>
#include<queue>
#include<deque>
#include<string>
#include<string.h>
#include<vector>
#include<set>
#include<map>
#include<bitset>
#include<stdlib.h>
#include<cassert>
#include<time.h>
#include<bitset>
using namespace std;
const long long mod=1000000007;
const long long inf=mod*mod;
const long long d2=(mod+1)/2;
const double EPS=1e-6;
const double PI=acos(-1.0);
int ABS(int a){return max(a,-a);}
long long ABS(long long a){return max(a,-a);}
int b[110];
int dp[11000];
int main(){
	int a;scanf("%d",&a);
	for(int i=0;i<a;i++){
		scanf("%d",b+i);
	}
	dp[0]=1;
	for(int i=0;i<a;i++){
		for(int j=10100;j>=0;j--){
			if(dp[j])dp[j+b[i]]=1;
		}
	}
	int ret=0;
	for(int i=0;i<10100;i++)if(i%10&&dp[i])ret=i;
	printf("%d\n",ret);
}

Measured memory_bytes: 256
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
struct Node{
    int key;
    struct Node* per;
    struct Node* l;
    struct Node* r;
};
typedef struct Node node;
node* insert(node* px,int k);
void printI(node* x);
void printP(node* x);
node* find(node* px,int k);

int main(void){
    int i;
    int n,k;
    node* x=NULL;
    char com[10];
    scanf("%d",&n);
    for(i=0;i<n;i++){
        scanf("%s",&com);
        if(strcmp(com,"insert")==0){
            scanf("%d",&k);
            x=insert(x,k);
        }else if(strcmp(com,"print")==0){
            printI(x);
            printf("\n");
            printP(x);
            printf("\n");
        }else{
            scanf("%d",&k);
            if(find(x,k)==NULL){
                printf("no\n");
            }else{
                printf("yes\n");
            }
        }
    }
    return 0;
}

node* insert(node* px,int k){
    node* x=px;
    node* y=NULL;
    node* z=(node*)malloc(sizeof(node));
    z->key=k;
    z->l=NULL;
    z->r=NULL;
    z->per=NULL;
    while(x!=NULL){
        y=x;
        if(z->key<x->key){
            x=x->l;
        }else{
            x=x->r;
        }
    }
    z->per=y;
    if(y==NULL){
        px=z;
    }else if(z->key<y->key){
        y->l=z;
    }else{
        y->r=z;
    }
    return px;
}

void printI(node* x){
    if(x->l != NULL){
        printI(x->l);
    }
    printf(" %d",x->key);
    if(x->r != NULL){
        printI(x->r);
    }
}

void printP(node* x){
    printf(" %d",x->key);
    if(x->l != NULL){
        printP(x->l);
    }
    if(x->r != NULL){
        printP(x->r);
    }
}

node* find(node* px,int k){
    while(1){
        if(px==NULL){
            return NULL;
        }
        if(px->key==k){
            return px;
        }
        if(px->key>k){
            px=px->l;
        }else{
            px=px->r;
        }
    }
}

Measured memory_bytes: 19360
import scala.math._

object Main extends App {

  val YES = "YES"
  val Yes = "Yes"
  val NO = "NO"
  val No = "No"
  ///////////////////////////////////////////

  val sc = new java.util.Scanner(System.in)
  val n, x = sc.nextInt
  val l = List.fill(n)(sc.nextInt)

  val ans = l.foldLeft(Tuple2(1, 0)){(acc, v) => if (x < acc._2 + v) (acc._1, acc._2 + v) else (acc._1 + 1, acc._2 + v) }

  println(ans._1)

  ///////////////////////////////////////////

  def bigIterator(start: BigInt, end: BigInt, step: BigInt = 1) =
    Iterator.iterate(start)(_ + step).takeWhile(_ <= end)

  def lcm(a :Int, b :Int): Int =
    a / gcd(a, b) * b

  def lcm(a :Long, b :Long): Long =
    a / gcd(a, b) * b

  def gcd(a: Int, b: Int): Int =
    if (b == 0) a else gcd(b, a % b)

  def gcd(a: Long, b: Long): Long =
    if (b == 0) a else gcd(b, a % b)

  def setOrUpdated[A, B](a: Map[A, B], key: A, value: B, f: (B, B) => B) =
    a.get(key) match {
      case Some(v) => a.updated(key, f(value, v))
      case _ => a + (key -> value)
    }
}

Measured memory_bytes: 25536
import java.util.*;

public class Main {
  // 頂点と辺の番号は全てインデックスに合わせる。
  static final int MAX_S = 50*50+10;
  static long dp[][]; // [頂点][銀貨] 頂点で銀貨を持った状態にかかる最小時間
  static PriorityQueue<Data> q = new PriorityQueue<>(); //最適としてありうる状態を全て保持しておく優先度つきキュー、時間xが小さいほど先頭
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    int m = sc.nextInt();
    int s = sc.nextInt();
    ArrayList<ArrayList<Edge>> g = new ArrayList<>(n); // g<頂点<辺>> 各頂点から出る辺
    dp = new long[n][MAX_S+5];
    for (int i = 0; i < n; i++) {
      g.add(new ArrayList<Edge>());
    }
    for (int i = 0; i < m; i++) { // gの初期化
      int u = sc.nextInt();
      int v = sc.nextInt();
      int a = sc.nextInt();
      int b = sc.nextInt();
      u--; v--;
      g.get(u).add(new Edge(v, a, b));
      g.get(v).add(new Edge(u, a, b));
    }
    for (int i = 0; i < n; i++) { // dpの初期化
      for (int j = 0; j < MAX_S+5; j++) {
        dp[i][j] = Long.MAX_VALUE;
      }
    }
    s = Math.min(s, MAX_S);
    push(0, s, 0);
    ArrayList<Integer> c = new ArrayList<>(); //c<頂点> 各頂点で得られる銀貨
    ArrayList<Integer> d = new ArrayList<>(); //d<頂点> 各頂点で銀貨を得るのにかかる時間
    for (int i = 0; i < n; i++) {
      c.add(sc.nextInt());
      d.add(sc.nextInt());
    }

    while (!q.isEmpty()) { // ダイクストラ法を回す、かかる時間でdpを回すイメージ
      Data hoge = q.poll();
      int v = hoge.v;
      s = hoge.s;
      long x = hoge.x;
      if (dp[v][s] != x) continue; // Data(v, s, x)より最適なものが既出ならスキップ
      // 以下お金を増やすパターンと辺を辿るパターンの遷移
      int ns = Math.min(s+c.get(v) ,MAX_S);
      push(v, ns, x+d.get(v));
      for (Edge e: g.get(v)) {
        push(e.to, s-e.a, x+e.b);
      }
    }
    for (int i = 1; i < n; i++) {
      long res = Long.MAX_VALUE;
      for (int j = 0; j < MAX_S+5; j++) {
        res = Math.min(res, dp[i][j]);
      }
      System.out.println(res);
    }
    sc.close();
  }

  static void push(int v, int s, long x) { // Data(v, s, x)が最適である時dpに追加するメソッド
    if (s < 0) return;
    if (dp[v][s] <= x) return;
    dp[v][s] = x;
    q.add(new Data(v, s, x));
  }

  static class Data implements Comparable<Data> {
    int v, s; // 頂点v,銀貨s
    long x; // 時間x
    Data(int v, int s, long x) {
      this.v = v;
      this.s = s;
      this.x = x;
    }

    @Override
    public int compareTo(Data o) {
      return Long.compare(x, o.x);
    }
  }

  static class Edge {
    int to, a, b;
    Edge(int to, int a, int b) {
      this.to = to;
      this.a = a;
      this.b = b;
    }
  }
}

Measured memory_bytes: 53876
#include<stdio.h>
 
int main(void){
  int N;
  scanf("%d",&N);
  int a,b,c;
  a=N%10;
  N/=10;
  b=N%10;
  N/=10;
  c=N%10;
  if(a==7 || b==7 || c==7){
    printf("Yes\n");
  }else{
    printf("No\n");
  }
  return 0;
}

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


def main():
    sx, sy, tx, ty = map(int, input().split())
    x_count = abs(tx - sx)
    y_count = abs(ty - sy)
    first = list()
    second = list()

    for y in range(y_count):
        first.append('U')

    for x in range(x_count):
        first.append('R')

    for y in range(y_count):
        second.append('D')

    for x in range(x_count):
        second.append('L')

    third = ['L', 'U'] + first + ['R', 'D']
    fourth = ['R', 'D'] + second + ['L', 'U']

    print(''.join(map(str, first + second + third + fourth)))


if __name__ == '__main__':
    main()


Measured memory_bytes: 3444
#include <bits/stdc++.h>
using namespace std;
int main()
{
  long long a,b,hcf;
  cin >> a >> b;
  hcf = __gcd(a,b);
  long long ans = a*b;
  ans /= hcf;
  cout << ans << endl;
  
  return 0;
}

Measured memory_bytes: 256
from collections import defaultdict, deque
import sys
import heapq
import bisect
import itertools
import queue
import copy
import time
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7

def inp(): return int(sys.stdin.readline())

def inpl(): return list(map(int, sys.stdin.readline().split()))

def inpl_str(): return list(sys.stdin.readline().split())

N, D = inpl()
ans = 0
for i in range(N):
    X, Y = inpl()
    X = X**2
    Y = Y**2
    X = pow(X+Y, 0.5)
    if D >= X:
        ans += 1
print(ans)


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

typedef unsigned long long ll;

int main() {
	ll n;
	cin >> n;
	ll ans = 0;
	ll divide = 10;

	if (n % 2 == 1) {
		cout << 0 << endl;
		return 0;
	}
	while(divide <= n) {
		ans += n / divide;
		divide *= 5LL;
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 512
import bisect
N = int(input())
lst = list(map(int, input().split()))
lst1 = sorted(lst)
x1 = lst1[N//2-1]
x2 = lst1[N//2]

for i in range(N):
    if bisect.bisect_right(lst1, lst[i]) <= N//2:
        print(x2)
    else:
        print(x1)

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

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.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 INF = (1<<30) - 1;
const ll LINF = (1LL<<60) - 1;

int main(){
    ll n;
    cin >> n;
    if (n % 2 == 1) cout << 0 << endl;
    else {
        ll res = 0;
        ll div = 10;
        while (n >= div){
            res += n / div;
            div *= 5;
        }
        cout << res << endl;
    }
}

Measured memory_bytes: 3624
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<string>
#include<cmath>
#include<cstring>
#include<map>
#include<set>
#include<stack>
#include<utility>
#include<queue>
#include<vector>
#include<cctype>
using namespace std;
#define fore(i,a,b) for(int i=a;i<=b;i++)
#define forb(i,a,b) for(int i=a;i>=b;i--)
#define fir first
#define sec second
#define ABS(a) ((a)>0?(a):-(a))
#define PI acos(-1,0)
typedef long long ll;
typedef long double ld;
const int MAXN=100005;
ll a[MAXN];

int main(){
    ll ans=1,n;
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    sort(a + 1, a + n + 1);
    for (int i = 1; i <= n; i++)
        a[i] += a[i - 1];
    for (int i = n - 1; i>=1;i--)
        if (a[i] * 3 >= a[i + 1] )
            ++ans;
        else
            break;
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
#include <math.h>
#define ALL(a)    a.begin(), a.end() 
#define rep(i, K, N)  for(long long int i = K; i < N; i++)
#define ll long long int
using namespace std;

ll F(ll N, ll a, ll p){
 
    if(a == 0)return 1;
 
    if(a%2 == 0 && a != 0)return (F(N, a/2, p)*F(N, a/2, p))%p;
 
    if(a%2 == 1)return N*F(N, a - 1, p)%p;
 
}

int main(){
ll x, y, k, K, n, N, Ans = 0;cin >> x >> y;
ll prime = 1000000007;
k = (x + y)/3;
n = min(2*k - x, 2*k - y);N = 1;
K = k - n + 1;
  
if((x + y)%3 != 0 || x > 2*k || y > 2*k){cout << 0;exit(0);}

if(n == 0){cout << 1;exit(0);}
  
else{
  
    rep(i, 1, n + 1){

        N *= i;N %= prime;

    }
  
}
  
rep(i, 1, n){

    K *= (k - n + 1) + i;K %= prime;

}

Ans = ( F(N, prime - 2, prime)%prime )*( K%prime );

cout << Ans%prime;
  
}

Measured memory_bytes: 3584
fn read_stdin() -> String {
    use std::io::Read;
    let mut input = String::new();
    std::io::stdin().read_to_string(&mut input).unwrap();
    input
}

fn scan<'a, I: Iterator<Item = &'a str>, T: std::str::FromStr>(tokens: &mut I) -> T {
    tokens.next().unwrap().parse().ok().unwrap()
}

fn main() {
    let input = read_stdin();
    let tokens = &mut input.split_whitespace();
    let n: usize = scan(tokens);
    println!("{}", ((n + 1) / 2) as f64 / n as f64);
}


Measured memory_bytes: 4352
#include<stdio.h>
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<map>
#include<vector>
using namespace std;
const int maxn = 2e5 + 5;
map<int,int>dp[maxn];
vector<int>ve[maxn];
int n;
int ans[maxn];
int dfs2(int x,int ba,int v) {
	if(dp[x].count(v)) return dp[x][v];
	int sm = 1;
	for(int y:ve[x]) {
		if(y==ba) continue;
		if(y<v) sm += dfs2(y,x,v);
	}
	return dp[x][v] = sm;
}
void dfs1(int x,int ba,int pr,int cc) {
	cc += dfs2(x,ba,max(ba,pr));
	if(pr>x) cc -= dfs2(x,ba,pr);
	ans[x] = cc;
	for(int y:ve[x]) {
		if(y==ba) continue;
		dfs1(y,x,max(pr,ba),cc);
	}
}
int main() {
	scanf("%d",&n);
	for(int i=1;i<n;i++) {
		int x,y; scanf("%d%d",&x,&y);
		ve[x].push_back(y);
		ve[y].push_back(x);
	}
	for(int y:ve[1]) {
		dfs1(y,1,1,0);
	}
	for(int i=2;i<=n;i++) printf("%d ",ans[i]);
}

Measured memory_bytes: 53888
# include <iostream>
# include <cstdio>
# include <algorithm>

using namespace std;

const int maxn = 12000;

int n;

pair<int, int> a[maxn];

int cnt[maxn];

int main() {
	scanf("%d", &n);
	for(int i = 1; i <= n; ++i) {
		scanf("%d", &a[i].first);
		cnt[a[i].first] += 1;
		a[i].second = i;
	}

	sort(a + 1, a + n + 1);
	
	bool flag = true;
	int mi = a[1].first, mx = a[n].first;

	if(cnt[mi] == 2) {
		for(int i = mi + 1; i <= mx; ++i) 
			if(cnt[i] < 2) flag = false;
		if(mx - mi + 1 != mi) flag = false;
	} else if(cnt[mi] == 1) {
		for(int i = mi + 1; i <= mx; ++i)
			if(cnt[i] < 2) flag = false;
		if(mx - mi != mi) flag = false;
	} else flag = false;

	puts(flag ? "Possible" : "Impossible");

	return 0;
}


Measured memory_bytes: 256
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <deque>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <vector>

using namespace std;

int main() {
    int n, m;
    cin >> n >> m;
    cout << n * (n - 1) / 2 + m * (m - 1) / 2 << endl;
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <array>
#include <vector>
#include <cmath>

using namespace std;

static void printArray(int A[], int N) {
  for (int i = 0; i < N; i++) {
    cout << A[i] << endl;
  }
}

static void inputArray(int A[], int N) {
  for (int i = 0; i < N; i++) {
    cin >> A[i];
  }
}

static int insersionSort(int A[], int N, int g) {
  int v, j, count = 0;
  for (int i = g; i < N; i++) {
    v = A[i];
    j = i - g;
    while (j >= 0 && A[j] > v) {
      A[j + g] = A[j];
      j = j - g;
      count++;
    }
    A[j + g] = v;
  }
  return count;
}

#include <cstdio>

static int shellSort(array<int, 1000000>& A,  int N) {
  array<int, 1000000> sortArray(A);
  int g = 1, startedIndex = 0, count = 0;
  vector<int> G = { 1 };
  for (; g < N; ) {
    G.push_back(g);
    g = 3 * g;
  }
  for (g = G.size() - 1;  g >= 0; g--) {
    if (G[g] * 2 > N) {
      continue;
    }
    if (startedIndex == 0) {
      startedIndex = g;
    }
    count += insersionSort(sortArray.data(), N, G[g]);
/* 
    if (count > pow(N, 1.5f)) {
      sortArray = A;
      continue;
    } 
*/
  }

  cout << startedIndex + 1 << endl;
  for (int i = startedIndex; i >= 0; i--) {
    cout << G[i];
    cout << ' ';
  }
  cout << endl;
  cout << count << endl;
  A = sortArray;
  return count;
}
  
int main() {
  int N;
  cin >> N;

  array<int, 1000000> A;
  inputArray(A.data(), N);

//  printArray(A.data(), N);

  shellSort(A, N);

  printArray(A.data(), N);
  
  return 0;
}



Measured memory_bytes: 10992
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <cmath>
#include <map>
#include <set>

using namespace std;

long long n;
map<string, long long> mm;
string s[500000];


signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> n;
    for (int i = 0; i < n; i++)
        cin >> s[i];
    for (int i = 0; i < n; i++) sort(s[i].begin(), s[i].end());
    for (int i = 0; i < n; i++) mm[s[i]]++;
    long long ans = 0;
    for (auto it : mm)
    {
        ans = ans + (it.second * (it.second - 1)) / 2;
    }
    cout << ans;
}


Measured memory_bytes: 19840
while True:
    H, W = [int(i) for i in input().split()]
    if H == W == 0:
        break
    for h in range(H):
        for w in range(W):
            if (h+w) % 2 == 0:
                print('#', end='')
            if (h+w) % 2 == 1:
                print('.', end='')

        print()
    print()

Measured memory_bytes: 9076
def temp(H):
  ans = - H *0.006
  return ans
N = int(input())
T, A = map(int, input().split())
H = list(map(int, input().split()))
TE = list(map(temp,H))
TLA = list(map(lambda x: abs(T + x -A) , TE))
ans=TLA.index(min(TLA))
print(ans+1)


Measured memory_bytes: 3060
import java.util.*;

public class Main{
	public static void main(String[]$){
		Scanner s=new Scanner(System.in);
		int n=s.nextInt(),b=1,i=0;
		long[]a=new long[n+1];
		while(++i<=n)a[i]=s.nextInt();
		Arrays.sort(a);
		Arrays.parallelPrefix(a,Long::sum);
		while(--n>0&&a[n+1]-a[n]<=a[n]*2)b++;
		System.out.println(b);
	}
}

Measured memory_bytes: 52892
#include <algorithm>
#include <cstdio>
#include <iostream>

typedef long long ll;

using namespace std;

int main() {
	int N, K, X, Y;
	scanf("%d%d%d%d", &N, &K, &X, &Y);

	if (N <= K)
		printf("%d\n", N * X);
	else
		printf("%d\n", K * X + (N - K) * Y);

	return 0;
}


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

int main()
{
    int i;

    int n;
    scanf("%d", &n);
    int x[n], y[n];
    for( i = 0; i < n; ++i )
        scanf("%d", &x[i]);
    for( i = 0; i < n; ++i )
        scanf("%d", &y[i]);

    int p;
    double D;
    for( p = 1; p < 4; ++p ){
        D = 0;
        for( i = 0; i < n; ++i )
            D += (double)(pow(fabs(x[i] - y[i]), p));
        D = (double)pow(D, 1.0/p);
        printf("%lf\n", D);
    }

    D = 0;
    for( i = 0; i < n; ++i ){
        double tmp = (double)(fabs(x[i] - y[i]));
        D = D < tmp ? tmp : D;
    }
    printf("%lf\n", D);

    return 0;
}


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

//#define int long long
#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()
#define rep(i,n) for(int i=0;i<n;++i)
#define rep1(i,n) for(int i=1;i<n;++i)
#define exrep(i, a, b) for(ll i = a; i < b; i++)
#define out(x) cout << x << endl
#define EPS (1e-7)
#define gearup ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
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<bool> vb;
typedef vector<double> vd;
typedef vector<string> vs;
typedef vector<pair<int,int> > vpii;
typedef vector<vector<int> > vvi;
typedef vector<vector<char> > vvc;
typedef vector<vector<bool> > vvb;
typedef vector<vector<double> > vvd;
typedef vector<vector<string> > vvs;
typedef vector<ll> vl;
typedef vector<vector<ll> > vvl;
typedef vector<vector<vector<ll> > > vvvl;
ll MOD = 1000000007;
const long long L_INF = 1LL << 60;
const int INF = 2147483647; // 2^31-1
const double PI = acos(-1);
//cout<<fixed<<setprecision(10);

template<class T> inline bool chmin(T& a, T b) {if (a > b) {a = b;return true;}return false;}
template<class T> inline bool chmax(T& a, T b) {if (a < b) {a = b;return true;}return false;}
template<class T> void debug(T v){rep(i,v.size()) cout<<v[i]<<" ";cout<<endl;}
const ll dx[8] = {1, 1, 0, -1, -1, -1, 0, 1};
const ll dy[8] = {0, 1, 1, 1, 0, -1, -1, -1};

signed main()
{   
    gearup;
    ll n;cin >> n;
    vl a(n),b(n);
    vpii p;
    rep(i,n){
        cin>>a[i]>>b[i];
        p.emplace_back(b[i],a[i]);
    }
    sort(all(p));
    ll now = 0;
    rep(i,n){
        now+=p[i].second;
        if(p[i].first < now){
            out("No");
            return 0;
        }
    }
    out("Yes");
}

Measured memory_bytes: 5620
#include<bits/stdc++.h>
using namespace std;
#define rep(i,x,y) for(int i=x;i<y;i++)
#define range(a) (a).begin(),(a).end()
#define print(A,n) rep(i,0,n){cout<<(i ? " ":"")<<A[i];}cout<<endl;
#define pprint(A,m,n) rep(j,0,m){print(A[j],n);}
const long mod=1e9+7;
const int size=1e5;
const int inf=1e9;
int main(){
	char c;cin>>c;
	cout<<(char)(c+1)<<endl;
}

Measured memory_bytes: 256
#include<cstdio> 
using namespace std;
int cnt,isprime[1000005],prime[1000005];
int main(){
	for (int i=2; i<=10000; i++){
		if (!isprime[i]) prime[++cnt]=i;
		for (int j=1; j<=cnt && prime[j]*i<=10000; j++){
			isprime[i*prime[j]]=1;
			if (i%prime[j]==0) break;
		}
	}
	int n;
	scanf("%d",&n);
	for (int i=1; i<=cnt; i++)
		if (prime[i]%5==1){
			n--;
			printf("%d ",prime[i]);
			if (!n) return 0;
		}
	return 0;
}

Measured memory_bytes: 2176
#include <stdio.h>

int main (void) {
  int A, B, C;

  scanf ("%d %d %d", &A, &B, &C);

  if (A < C && C < B) {
    printf ("Yes\n");
  } else if (A > C && C > B) {
    printf ("Yes\n");
  } else {
    printf ("No\n");
  }
}

Measured memory_bytes: 128
#include<bits/stdc++.h>
#define ll long long
#define inf 1000000000+1
#define rep(a,b) for(ll i=a;i<b;i++)
#define io ios_base::sync_with_stdio(false);cin.tie(NULL);

using namespace std;

int main()
{   io

    ll n=0;
    cin>>n;
    ll a[n],b[n],c[n];
    ll dp[3][n+1];
    rep(0,n)
        cin>>a[i]>>b[i]>>c[i];

    rep(0,n+1)
        for(int j=0;j<3;j++)
            dp[j][i]=0;

    //construct dp table
    rep(1,n+1)
        //for(ll j=0;j<3;j++)
        {
            dp[0][i]=max(dp[0][i],a[i-1]+max(dp[1][i-1],dp[2][i-1]));
            dp[1][i]=max(dp[1][i],b[i-1]+max(dp[0][i-1],dp[2][i-1]));
            dp[2][i]=max(dp[2][i],c[i-1]+max(dp[1][i-1],dp[0][i-1]));
        //printf("<%d %d %d>",dp[0][i],dp[1][i],dp[2][i]);
        }
    ll maxh=0;
    rep(0,3)
        maxh=max(maxh,dp[i][n]);

    cout<<maxh;
    return 0;
}


Measured memory_bytes: 4992
#include<iostream>
using namespace std;
int main()
{
  int a,b;
  cin>>a>>b;
  if((a==1&&b==2)||(a==2&&b==1))
    cout<<"3"<<endl;
  if((a==1&&b==3)||(a==3&&b==1))
    cout<<"2"<<endl;
  if((a==2&&b==3)||(a==3&&b==2))
    cout<<"1"<<endl;
  return 0;
}

Measured memory_bytes: 384
def read():
    N = int(input())
    A = list(map(int, input().split()))
    return N, A

def solve(N, A):
    x = 1000
    y = 0
    op = "buy"
    for i in range(N):
        if i == N-1:
            x += y * A[i]
        elif op == "buy":
            if A[i] >= A[i+1]:
                continue
            else:
                c = x // A[i]
                x -= c * A[i]
                y += c
                op = "sell"
        elif op == "sell":
            if A[i] <= A[i+1]:
                continue
            else:
                c = y
                x += c * A[i]
                y -= c
                op = "buy"
    return max(x, 1000)


if __name__ == '__main__':
    inputs = read()
    print(solve(*inputs))


Measured memory_bytes: 9216