akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <cstring>
#include <string>

// #include <glog/logging.h>

void bubbleSort(std::string * A, int * idx, int N) {
    for (int i = 0; i < N; i++) {
        for (int j = N - 1; j > i; j--) {
            if (idx[j] < idx[j - 1]) {
                std::swap(A[j], A[j - 1]);
                std::swap(idx[j], idx[j - 1]);
            }
        }
    }
}

void selectionSort(std::string * A, int * idx, int N) {
    for (int i = 0; i < N; i++) {
        int min_idx = i;
        for (int j = i + 1; j < N; j++) {
            if (idx[min_idx] > idx[j]) {
                min_idx = j;
            }
        }
        if (min_idx != i) {
            std::swap(A[min_idx], A[i]);
            std::swap(idx[min_idx], idx[i]);
        }
    }
}

void printSort(std::string * A, int N) {
    for (int i = 0; i < N - 1; i++) {
        std::cout << A[i] << " ";
    }
    std::cout << A[N - 1] << std::endl;
}

bool isStable(std::string * A, std::string * sorted, int N) {
    bool is_stable = true;
    for (int i = 0; i < N - 1; i++) {
        if (sorted[i][1] == sorted[i + 1][1]) {
            for (int j = 0; j < N; j++) {
                if (A[j] == sorted[i]) {
                    is_stable = true;
                    break;
                } else if (A[j] == sorted[i + 1]) {
                    is_stable = false;
                    break;
                }
            }
            if (!is_stable) {
                std::cout << "Not stable" << std::endl;
                return is_stable;
            }
        }
    }
    std::cout << "Stable" << std::endl;
    return is_stable;
}

int main(int argc, char ** argv) {
// #ifdef NDEBUG
//     google::InitGoogleLogging(argv[0]);
//     google::InstallFailureSignalHandler();
// #endif
    
    int N;
    std::cin >> N;

    std::string A[N], A_bubble[N], A_select[N];
    int bubble[N], select[N];
    
    for (int i = 0; i < N; i++) {
        std::cin >> A[i];
        A_bubble[i] = A_select[i] = A[i];
        bubble[i] = select[i] = std::atoi(&A[i][1]);
    }

    bubbleSort(A_bubble, bubble, N);
    selectionSort(A_select, select, N);

    printSort(A_bubble, N);
    isStable(A, A_bubble, N);
    printSort(A_select, N);
    isStable(A, A_select, N);
}



Measured memory_bytes: 3228
#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define MAX_INF 0x7f
#define MAX_INF_VAL 0x7f7f7f7f
#define pi 3.141592653589
#define eps 1e-6
//#define p 2173412051LL
#define sz 2

using namespace std;

ll pow_mod( ll, ll, ll );
ll cnm( ll, ll, ll );

int main() {
	ll n, a, b;
	ll ans;
	ll p = 1000000007;
	scanf( "%lld%lld%lld", &n, &a, &b );
	ans = pow_mod( 2LL, n, p );
	--ans;
	ans -= cnm( n, a, p );
	ans -= cnm( n, b, p );
	ans %= p;
	ans += p;
	ans %= p;
	printf( "%lld", ans );
	return 0;
}

ll cnm( ll n, ll m, ll p ) {
	ll res = 1;
	for( ll i = 1; i <= m; ++i ) {
		res *= ( n + 1 - i );
		res %= p;
		res *= pow_mod( i, p - 2, p );
		res %= p;
	}
	return res;
}

ll pow_mod( ll x, ll y, ll p ) {
	ll res = 1;
	while( y ) {
		if( y & 1 ) {
			res *= x;
			res %= p;
		}
		x *= x;
		x %= p;
		y >>= 1;
	}
	return res;
}

Measured memory_bytes: 256
#include <bits/stdc++.h> 
#define int long long
#define deb(x) cout<<#x <<" = "<<x<<"\n";
using namespace std; 
signed main() 
{
	//freopen("input.txt", "r", stdin);
	
	int a[3][3];
	for(int i = 0; i < 3; i++)
		cin >> a[i][0] >> a[i][1] >> a[i][2];
	int n; cin >> n;
	bool ok = false;
	while(n--)
	{
		int x; cin >> x;
		for(int i = 0; i < 3; i++)
			for(int j = 0; j < 3; j++)
				if(a[i][j] == x) a[i][j] = 0;
		
		
		for(int i = 0; i < 3; i++)
		{
			ok |= (a[i][0] == 0 && a[i][1] == 0 && a[i][2] == 0);
			ok |= (a[0][i] == 0 && a[1][i] == 0 && a[2][i] == 0);
		}
		ok |= (a[0][0] == 0 && a[1][1] == 0 && a[2][2] == 0);
		ok |= (a[0][2] == 0 && a[1][1] == 0 && a[2][0] == 0);
	}
	if(ok) cout <<"Yes";
	else cout <<"No";
	
	
	
	
}

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

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

using namespace std;

int main(){
	string s,t; cin>>s>>t;
	int n=s.length(),m=t.length();

	if(n<m){ cout<<"UNRESTORABLE"<<endl; return 0; }

	string ans="~";
	rep(i,n-m+1){
		bool ok=true;
		string r=s;
		rep(j,m){
			if(s[i+j]=='?'){
				r[i+j]=t[j];
			}
			else if(s[i+j]!=t[j]){
				ok=false;
			}
		}
		if(!ok) continue;

		rep(j,n) if(r[j]=='?') r[j]='a';
		ans=min(ans,r);
	}
	cout<<(ans=="~"?"UNRESTORABLE":ans)<<endl;

	return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <algorithm>	// require sort next_permutation count __gcd reverse etc.
#include <cstdlib>	// require abs exit atof atoi 
#include <cstdio>		// require scanf printf
#include <functional>
#include <numeric>	// require accumulate
#include <cmath>		// require fabs
#include <climits>
#include <limits>
#include <cfloat>
#include <iomanip>	// require setw
#include <sstream>	// require stringstream 
#include <cstring>	// require memset
#include <cctype>		// require tolower, toupper
#include <fstream>	// require freopen
#include <ctime>		// require srand
#define rep(i,n) for(int i=0;i<(n);i++)
#define ALL(A) A.begin(), A.end()

using namespace std;

typedef long long ll;
typedef pair<bool, int> BI;

bool stone[100005];

int main()
{
//	cut here before submit 
//	freopen ("testcase.SGS", "r", stdin );
	int n;
	while (scanf ("%d", &n ), n ){
		memset (stone, false, sizeof (stone ) );
		rep (i, n ){
			int in;
			scanf ("%d", &in );
			stone[i] = (in == 1 ? true : false );
		} // end rep
		stack<BI> st;
		st.push (BI (stone[0], 1 ) );
		for (int i = 1; i < n; i++ ){
			// 前の碁石と色が同じとき
			if (st.top().first == stone[i] ){
				st.top().second++;
			}else
			if ((i+1) % 2 == 0 ){		// 偶数番目のとき
				int curr = 0;
				do{
					curr += st.top().second; st.pop();
				}while (!st.empty() && st.top().first != stone[i] );
				st.push (BI (stone[i], curr + 1 ) );
			}else{						// 奇数番目のとき
				st.push (BI (stone[i], 1 ) );	
			} // end if
		} // end for

		int res = 0;
		while (!st.empty() ){
			BI curr = st.top(); st.pop();
			if (!curr.first ) res += curr.second;
		} // end while
		printf ("%d\n", res ); 
	} // end loop
		
	return 0;
}

Measured memory_bytes: 1292
#include<stdio.h>
int n, d, a, i;
int ans;
int main(){
	scanf("%d%d%d", &n, &d, &ans);
	for(i=0; i<n; i++){
		scanf("%d", &a);
		ans += (d-1)/a+1;
	}
	printf("%d\n", ans);
}

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

using namespace std;

#define debug(n) cerr << #n << ' ' << n << endl;

inline bool ChangeMin(int&a, int b){
  if(a > b){
    a = b;
    return true;
  }
  return false;
}

void CheckReachableNode(const vector<unordered_set<int>>&movable_list
			, int pos
			, bitset<2500>&nodes){
  
  if(nodes[pos] == 1){
    return;
  } else {
    nodes[pos] = 1;
    for(auto&&node:movable_list[pos]){
      CheckReachableNode(movable_list, node, nodes);
    }
  }
}

int main(){
  int v, e, p;
  cin >> v >> e >> p;

  vector<tuple<int, int, int>> edges;
  vector<unordered_set<int>> in_list(v);
  vector<unordered_set<int>> out_list(v);
  bitset<2500> reachable_from_start = 0;
  bitset<2500> reachable_in_goal = 0;

  for(int i = 0; i < e; ++i){
    int a, b, c;
    cin >> a >> b >> c;
    a--;
    b--;
    edges.emplace_back(a,b,-(c-p));
    out_list[a].insert(b);
    in_list[b].insert(a);
  }


  CheckReachableNode(out_list, 0, reachable_from_start);
  CheckReachableNode(in_list, v - 1, reachable_in_goal);

  bitset<2500>on_path;

  on_path = reachable_from_start & reachable_in_goal;
  
  vector<int> costs(v, 1e+9);
  int loop_count = 0;
  bool loop_fin = false;

  costs[0] = 0;

  while(!loop_fin){
    loop_fin = true;
    for(auto&&edge:edges){
      int a, b, c;
      tie(a,b,c) = edge;
      if(out_list[a].count(b) != 0  &&  on_path[a] & on_path[b]){
	if(ChangeMin(costs[b], costs[a] + c)){
	  loop_fin = false;
	}
      }
    }
    if(loop_count++ > v) {
      cout << -1 << endl;
      return 0;
    }
  }

  cout << max(-costs[v - 1], 0) << endl;
  
  return 0;
}


Measured memory_bytes: 1280
#include <iostream>
#include <string>
#include <cassert>
#include <cctype>
#include <cstdio>

using namespace std;

int main(void) {

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

    while (a != b) {
        (a > b ? a : b) = a > b ? a - b : b - a;
    }

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

    return 0;
}

Measured memory_bytes: 1144
#include<bits/stdc++.h>
using namespace std;
main()
{
    long long t,i,n;
        cin>>n;
        long long a[n];
        for(i=0;i<n;i++)cin>>a[i];
        map<int,int>m;
        long long ans=0;
        for(i=0;i<n;i++)
        {
            int a1=i+a[i];
            int b=i-a[i];
            m[a1]++;
            ans+=m[b];
        }
        cout<<ans<<endl;
}

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

#define lp(var,start,end) for (ll var = start; var <end ; ++var)
#define rlp(var,start,end) for(ll var = start; var>=end ; var--)
#define pb push_back
#define mp make_pair
#define pf push_front
#define ff first
#define ss second
#define vll vector<ll>
#define vld vector<ld>
#define pll pair<ll,ll> 
#define pld pair<ld,ld> 
#define vpll vector<pll>
#define vpld vector<pld>
#define all(X) X.begin(),X.end()
#define endl "\n"
#define sz(x) ((ll)((x).size()))
const ll N=2e5+5,inf=1e18,mod=1e9+7;
ll expo(ll a, ll b, ll mod) {
    ll ans = 1;
    while(b!=0 ) 
    {
        if((b&1) == 1) 
            ans = (ans*a)%mod ;
        a= (a*a)%mod;
       	b>>= 1;
    }
    return ans%mod;
}
vll G[N];
ll fac[N],sub[N],dp[N],invfac[N],ans[N];
ll dfs(ll a,ll p)
{
	dp[a]=1;
	lp(i,0,sz(G[a]))
	{
		ll x=G[a][i];
		if(x!=p)
		{
			dfs(x,a);
			sub[a]+=sub[x];
			dp[a]*=invfac[sub[x]];
			dp[a]%=mod;
			dp[a]*=dp[x];
			dp[a]%=mod;
		}
	}
	dp[a]*=fac[sub[a]];
	dp[a]%=mod;
	sub[a]+=1;
	// if(dp[a]==0)dp[a]=1;
	// cout<<a<<" "<<dp[a]<<" "<<sub[a]<<endl;

}
ll n;
ll dfs2(ll a,ll p,ll val)
{
	// cout<<val<<" "<<a<<endl;
	ans[a]=val;
	ans[a]*=fac[n-1];
	ans[a]%=mod;
	ans[a]*=invfac[n-sub[a]];
	ans[a]%=mod;
	lp(i,0,sz(G[a]))
	{
		ll x=G[a][i];
		if(x!=p)
		{
			ans[a]*=dp[x];
			ans[a]%=mod;	
			ans[a]*=invfac[sub[x]];
			ans[a]%=mod;
		}
	}
	lp(i,0,sz(G[a]))
	{
		ll x=G[a][i];
		if(x!=p)
		{
			ll val=ans[a];
			val*=invfac[n-1];
			val%=mod;
			val*=fac[n-1-sub[x]];
			val%=mod;
			val*=expo(dp[x],mod-2,mod);
			val%=mod;
			val*=fac[sub[x]];
			val%=mod;
			// cout<<a<<" "<<x<<" "<<val<<" "<<ans[a]<<endl;
			dfs2(x,a,val);
		}
	}
}
int main()
{
	ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
	fac[0]=1;
	invfac[0]=1;
	lp(i,1,N)
	{
		fac[i]=(fac[i-1]*i)%mod;
		invfac[i]=expo(fac[i],mod-2,mod);
	}
	// ll n;
	cin >> n;
	lp(i,0,n-1)
	{
		ll a,b;
		cin >> a >> b;
		G[a].pb(b);
		G[b].pb(a);
	}	    
	dfs(1,0);
	dfs2(1,0,1);
	lp(i,1,n+1)
	{
		cout<<ans[i]<<endl;
	}
	return 0;
}

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

// バケット法を用いる
signed main() {
  string s; cin >> s;
  int backet[1000] = {0};

  bool ans = true;
  for(int i = 0; i < s.size(); i++) {
    backet[(int)s.at(i)]++;
    if(backet[s.at(i)] >= 2) {
      ans = false;
      break;
    }
  }

  cout << (ans ? "yes" : "no") << endl;
  return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<stdio.h>
#include<string>
#include<vector>
#include<map>
#include<tuple>
#include<algorithm>
#include<cmath>
#include<limits>
#include<set>
#include<deque>
#include<queue>
using namespace std;
#define int long  long int
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
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; }
typedef pair<int, int>P;
const int MOD = 1e9 + 7;
const int INF = 1e10;
const long double PI = (acos(-1));


signed main() {
	int N, M;
	cin >> N >> M;
	int ans = N * (N - 1) / 2 + M * (M - 1) / 2;
	cout << ans;
}

Measured memory_bytes: 256
"use strict";

const main = (input) => {
    const spi = input.split('\n');
    const [k, n] = spi[0].split(' ').map(e => Number(e));
    const a = spi[1].split(' ').map(e => Number(e));
    for (let i = 0; i < n; i++) {
        a.push(a[i] + k);
    }

    let ans = 1000000000000000000n;
    for (let i = 0; i < n; i++) {
        if (ans > a[n+i-1]-a[i]) ans = a[n+i-1]-a[i];
    }

    console.log(ans);
};

main(require("fs").readFileSync("/dev/stdin", "utf8"));


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

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

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



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

#define rep(i, s, n) for(int i = s; i < n; ++i)
#define rrep(i, n) for(int i = n - 1; i > -1; --i)
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
using namespace std;
const long long INF = 1000000000;
const int MOD = 1000000007;
typedef long long ll;
typedef pair<int, int> P;

int main() {
    int n, m;
    cin >> n >> m;
    vector<int> num(n, -1);
    int s, c;
    int f = 0;
    rep(i, 0, m){
        cin >> s >> c;
        if(s == 1 && c == 0){
            if(n == 1) f = 0;
            else f = 1;
        }
        if(num[s - 1] == -1){
            num[s - 1] = c;
        }else{
            if(num[s - 1] != c){
                f = 1;
            }
        }
    }
    if(f == 1){
        cout << -1 << endl;
    }else{
        rep(i, 0, n){
            if(i == 0){
                if(num[i] == -1){
                    if(n == 1) cout << 0;
                    else cout << 1;
                }
                else cout << num[i];
            }else{
                if(num[i] == -1) cout << 0;
                else cout << num[i];
            }
        }
        cout << endl;
    }




}


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

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int[] d = new int[N];
		for(int i = 0; i < N; i++) {
			d[i] = sc.nextInt();
		}
		Arrays.sort(d);
		int diff = d[N / 2] - d[N / 2 - 1];
		System.out.println(diff);
	}

}

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

using namespace std;

#define reps(i,f,n) for(int i=f; i<n; ++i)
#define rep(i,n) reps(i,0,n)

int main()
{
    int m, a, b;
    
    while(cin >> m >> a >> b, m){
        vector<int> pt(m);
        for(int i=0; i<m; ++i){
            cin >> pt[i];
        }
        
        pair<int, int> ans{-1, -1};
        
        rep(p, 10000){
            vector<int> ok, ng;
            
            rep(i, m){
                if(pt[i] < p) ng.push_back(pt[i]);
                else ok.push_back(pt[i]);
            }
            
            int n = ok.size();
            if(a <= n && n <= b){
                int gap = *min_element(ok.begin(), ok.end()) - *max_element(ng.begin(), ng.end());
                ans = max(ans, {gap, ok.size()});
            }
        }
        
        cout << ans.second << endl;
    }
}

Measured memory_bytes: 3164
#include <stdio.h>
#include <stdlib.h>
int compar(const void *a, const void *b)
{
     return *(int *)a - *(int *)b;
}

int main(){
 int i,k,N,K,h[100000],ans;
 scanf("%d%d",&N,&K);
 for(i=0;i<N;i++){
    scanf("%d",&h[i]);
 }

//quicksort
	qsort(h,N,4,compar);

//出力
ans=h[K-1]-h[0];
for(i=1;i+K-1<N;i++){
   if(ans>h[i+K-1]-h[i]){ans=h[i+K-1]-h[i];}
}
 printf("%d\n",ans);
 return 0;
}


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

import sys

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

N = INT()

# dp[i][j][k][l] := i文字目まで見て、3文字前がj、2文字前がk、1文字前がlである通り数
dp = list4d(N+1, 5, 5, 5, 0)
dp[0][0][0][0] = 1

# A: 1, C: 2, G: 3, T: 4
for i in range(N):
    for j in range(5):
        for k in range(5):
            for l in range(5):
                # A,C,G,Tへの遷移
                for m in range(1, 5):
                    # AGC
                    if k == 1 and l == 3 and m == 2:
                        continue
                    # ACG
                    elif k == 1 and l == 2 and m == 3:
                        continue
                    # GAC
                    elif k == 3 and l == 1 and m == 2:
                        continue
                    # A?GC
                    elif j == 1 and l == 3 and m == 2:
                        continue
                    # AG?C
                    elif j == 1 and k == 3 and m == 2:
                        continue
                    dp[i+1][k][l][m] += dp[i][j][k][l]
                    dp[i+1][k][l][m] %= MOD
ans = 0
for j in range(5):
    for k in range(5):
        for l in range(5):
            ans += dp[N][j][k][l]
            ans %= MOD
print(ans)


Measured memory_bytes: 3572
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#define ll long long
using namespace std;

struct pt{
    ll x, y, z;
};

int main()
{
    int n, m;
    long long ans(0);
    cin >> n >> m;
    vector <pt> a(n);
    for(int i = 0; i < n; i++)
        cin >> a[i].x >> a[i].y >> a[i].z;
    for(int i = 0; i < 8; i++)
    {
        vector <long long> val;
        for(int j = 0; j < n; j++)
        {
            long long cur(0);
            if((i >> 2) % 2)
                cur += a[j].x;
            else
                cur -= a[j].x;
            if((i >> 1) % 2)
                cur += a[j].y;
            else
                cur -= a[j].y;
            if(i % 2)
                cur += a[j].z;
            else
                cur -= a[j].z;
            val.push_back(cur);
        }
        sort(val.begin(), val.end());
        long long cur_ans(0);
        for(int j = n - 1; j >= n - m; j--)
            cur_ans += val[j];
        //cout << i << " " << cur_ans << '\n';
        ans = max(ans, cur_ans);
    }
    cout << ans;
}


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

int main() {

	long long n; cin >> n;

	long long ans = 0;
	for (int i = 1; i <= n; i++) {

		if (i % 3 == 0 && i % 5 == 0) {	}
		else if(i % 3 == 0){}
		else if (i % 5 == 0) {}
		else {
			ans += i;
		}

	}
		cout << ans << endl;
	
	return 0;

}


Measured memory_bytes: 3632
#include "bits/stdc++.h"
using namespace std;
#define int long long
#define double long double
#define low lower_bound
#define upp upper_bound
#define rep(i,n) for (int i = 0; i < (int)(n); i++)
#define Rep(i,n) for (int i = (int)(n); i >= 0; i--)
#define all(vec) vec.begin(),vec.end()
#define rever(vec) reverse(all(vec));
#define cend cout << endl;
#define prique(T) priority_queue<T,vector<T>,greater<T>>
struct edge { int to, cost; };
using P = pair<int, int>;
using PP=pair<P, int>;
const int mod = 1e9 + 7, inf = 1e16;

int modpow(int x, int n) {
	int ans = 1;
	while (n > 0) {
		if (n & 1) {
			if (mod <= ans * x) ans = ans * x % mod;
			else ans *= x;
		}
		if (mod <= x * x) x = x * x % mod;
		else x *= x;
		n >>= 1;
	}
	return ans;
}

int fact_memo[114514];
int fact(int n) {
	int ans = 1;
	if (fact_memo[n]) return fact_memo[n];
	rep(i, n) {
		ans *= (i + 1);
		if (mod <= ans) ans %= mod;
		fact_memo[i + 1] = ans;
	}
	return (ans + mod) % mod;
}

int comb(int n, int r) {
	if (n < r) return 0;
	if (n - r < r) r = n - r;
	return (fact(n) * modpow(fact(n - r), mod - 2) % mod * modpow(fact(r), mod - 2) + mod) % mod;
}

int perm(int n, int r) {
	if (n < r) return 0;
	if (n - r < r) r = n - r;
	return (fact(n) * modpow(fact(n - r), mod - 2) % mod + mod) % mod;
}

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

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

bool pri(int p) {
	for (int i = 2; i * i <= p; i++) if (p % i == 0) return false;
	return p > 1;
}

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

P operator+(const P& a, const P& b) {
	return P(a.first + b.first, a.second + b.second);
}
P operator-(const P& a, const P& b) {
	return P(a.first - b.first, a.second - b.second);
}

int n, ans = 1, w;
int a[100010];
bool up = true, down = true;
signed main() {
	scanf("%lld", &n);
	rep(i, n) {
		scanf("%lld", &a[i]);
	}
	for (int i = 1; i < n; i++) {
		if (up && down) {
			if (a[i - 1] < a[i]) {
				down = false;
			}
			else if (a[i - 1] > a[i]) {
				up = false;
			}
		}
		else if (up) {
			if (a[i - 1] <= a[i]) continue;
			ans++;
			down = true;
		}
		else if (down) {
			if (a[i - 1] >= a[i]) continue;
			ans++;
			up = true;
		}
	}
	printf("%lld\n", ans);
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
#define endl "\n"
#define faster ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
typedef long long ll;
 
typedef vector<int> vi;;
typedef vector<ll> vll;

#define l() length()
#define sz() size()
 
#define b() begin()
#define e() end()
#define all(x) x.begin(), x.end()
 
#define pb(i) push_back(i)
#define PB() pop_back()
 
 
typedef pair<int, int> pii;
typedef pair<ll,ll> pll;
#define mp make_pair
#define Fi first
#define Se second
 
const int maxx=1e6+9;
 
// Happy Coding!


void solve(){
    
    int n,m;
    cin>>n;
    vi tim(n,0);
    int sum=0;
    for(int i=0;i<n;i++){cin>>tim[i];sum+=tim[i];}
    cin>>m;
    for(int i=0;i<m;i++){
        int p,x;
        cin>>p>>x;
        p--;
        cout<<sum-tim[p]+x<<endl;
    }
}





int main() {
    faster;
    int t=1;
    // cin>>t;
    while(t-->0){
        solve();
    }
	return 0;
}

Measured memory_bytes: 3604
(let* ((n (read))
       (h (read))
       (lst (loop :repeat n :collect (cons (read) (read))))
       (mx (reduce #'max lst :key #'car))
       (my (sort (mapcar #'cdr (remove-if-not (lambda (j) (< mx (cdr j))) lst)) #'>)))
  (princ (if (<= h (reduce #'+ my))
             (1+ (loop :for k :in my :do (setf h (- h k)) :count (< 0 h)))
             (+ (length my) (ceiling (- h (reduce #'+ my)) mx)))))

Measured memory_bytes: 61800
#include "bits/stdc++.h"

#define REP(i,num) for(int i=0;i<(num);++i)
#define ALL(c) c.begin(),c.end()
#define LOOP(i) while(i--)
#define PRINTALL(c) for(auto& x:c){cout<<x<<' ';}cout<<endl;
#define PAIRCOMP(c,comp) [](const pair<ll,ll>& lhs,const pair<ll,ll>& rhs){return lhs.c comp rhs.c;}

using namespace std;
using ll = long long;

constexpr ll atcoder_mod = 1e9+7;

template<typename T=int>
T in(){T x; cin >> x; return (x);}
template<typename T=int,typename C=vector<T>>
C vecin(int N){C x(N);REP(i,N){x[i]=in<T>();}return move(x);}

void vout(){cout << endl;}
template<typename Head,typename... Tail>
void vout(Head&& h,Tail&&... t){cout << ' ' << h;vout(forward<Tail>(t)...);}
void out(){cout << endl;}
template<typename Head,typename... Tail>
void out(Head&& h,Tail&&... t){cout << h;vout(forward<Tail>(t)...);}

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

	const double pi = 4.0*atan(1.0);

	vector<pair<double,double>> P(1000);
	P[0] = make_pair(1.0,0);
	for(int i=1;i<1000;i++){
		double theta = atan2(-P[i-1].second,-P[i-1].first);
		theta += 0.5*pi;
		double x = cos(theta),y = sin(theta);
		P[i].first = x+P[i-1].first;
		P[i].second = y+P[i-1].second;
	}

	while(true){
		int N=in();
		if(N<0) break;
		printf("%.5lf\n%.5lf\n",P[N-1].first,-P[N-1].second);
	}
	return 0;
}


Measured memory_bytes: 3608
//#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define pp pair<int,int>
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define ld long double
#define al(a) (a).begin(),(a).end()
#define mk make_pair
#define check cout<<"?"<<endl;

ll MOD=1000000007;
ll mod=998244353;
int inf=1000001000;
ll INF=1e18+5;

int find_(int x,vector<int> &v){
    if(v[x]<0) return x;
    v[x]=find_(v[x],v);
    return v[x];
}

int same_(int a,int b,vector<int> &v){
    if(find_(a,v)==find_(b,v)) return 1;
    return 0;
}

void union_(int a,int b,vector<int> &v){
    if(same_(a,b,v)) return;
    int a_p=find_(a,v),b_p=find_(b,v);
    if(a_p>b_p) swap(a_p,b_p);
    v[a_p]+=v[b_p]; v[b_p]=a_p;
}

void print_v(vector<int> v){
    rep(i,v.size()) cout<<v[i]<<" ";
    cout<<endl;
}

int size_(int a,vector<int> &v){
    return -v[find_(a,v)];
}




int main() {
    int n,m,k,ans; cin>>n>>m>>k;
    vector<vector<int>> fl(n),bl(n);
    vector<int> flv(n,-1),blv(n,-1);
    rep(i,m){
        int a,b; cin>>a>>b;
        a--; b--;
        fl[a].push_back(b);
        fl[b].push_back(a);
        union_(a,b,flv);
    }
    rep(i,k){
        int a,b; cin>>a>>b;
        a--; b--;
        bl[a].push_back(b);
        bl[b].push_back(a);
        union_(a,b,blv);
    }
    rep(i,n){
        ans=size_(i,flv)-fl[i].size()-1;
        for(auto q : bl[i])
        if(same_(q,i,flv)) ans--;
        cout<<ans<<(i!=n-1 ? " " : "\n");
    }
}

Measured memory_bytes: 12664
import java.util.*;
 
public class Main {
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
        
        int n = sc.nextInt();
        String str = sc.next();
        String s[] = str.split("");

        boolean judge = true;

        if (s.length % 2 == 1) {
            System.out.println("No");
        } else {

            for (int i = 0; i < s.length / 2; i++) {
                if (!(s[i].equals(s[s.length / 2 + i]))) {
                    judge = false;
                }
            }

            if (judge) {
                System.out.println("Yes");
            } else {
                System.out.println("No");
            }
        }
	}
}


Measured memory_bytes: 21844
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<queue>
#include<functional>
#include<cmath>
#include<set>
#include<random>
#include<map>
using namespace std;
#define int long long
#define rep(i,n) for(int i=0;i<n;i++)
const long long mod = 1000000007;
const long long inf = 11451419198109130;
typedef pair<int, int> P;
typedef pair<P, P> PP;
struct edge {int to, cost;};
int p[114], q[114], b[114], r[114];
int h[114];
int gcd(int a, int b) {
	if (!b)return a; return gcd(b, a%b);
}

int heavy(int i) {
	if (r[i]>=0 && !h[r[i]]) heavy(r[i]);
	if (b[i]>=0 && !h[b[i]])heavy(b[i]);

	if (r[i]==-1&& b[i]==-1) {
		int P = p[i], Q = q[i];
		int G = gcd(P, Q);
		P /= G; Q /= G;
		return h[i] = P + Q;
	}
	else if(r[i]==-1){
		int P=p[i], Q = q[i];
		int G = gcd(P, Q*h[b[i]]);
		G = p[i] / G;
		h[b[i]] *= G;
		return h[i] = h[b[i]] + h[b[i]] * q[i] / p[i];
	}
	else if (b[i] == -1) {
		int P = p[i], Q = q[i];
		int G = gcd(P*h[r[i]], Q);
		G = Q / G;
		h[r[i]] *= G;
		return h[i] = h[r[i]] + h[r[i]] * p[i] / q[i];
	}
	else {
		int P = p[i] * h[r[i]], Q = q[i] * h[b[i]];
		int G = gcd(P, Q);
		h[r[i]] *= Q / G;
		h[b[i]] *= P / G;
		return h[i] = h[r[i]] + h[b[i]];
	}
}

signed main() {
	int n;
	while (cin >> n,n) {
		rep(i, n)h[i] = 0;
		rep(i, n) {
			cin >> p[i] >> q[i] >> r[i] >> b[i];
			r[i]--; b[i]--;
		}
		rep(i, n) {
			if (!h[i])heavy(i);
		}
		int ans = 0;
		rep(i, n)ans = max(ans, h[i]);
		cout << ans << endl;
	}
}


Measured memory_bytes: 3064
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		int N = scan.nextInt();
		int []a = new int[N];
		for(int i = 0; i < N; i++) {
			a[i] = scan.nextInt();
		}
		scan.close();
		int cnt = 0;
		for(int i = 0; i < N - 1; i++) {
			if(a[i] == a[i + 1]) {
				cnt ++;
				a[i + 1] = 10000 - i;
			}
		}
		System.out.println(cnt);

	}
}

Measured memory_bytes: 21844
import java.util.*;

class Main {
  public static void main(String[] args) {
    Scanner sc=new Scanner(System.in);
    int A=sc.nextInt();
    int B=sc.nextInt();
    int C=sc.nextInt();
    int X=sc.nextInt();

    int res=0;
    for (int a=0; a<=A; a++) {
      for (int b=0; b<=B; b++) {
        int c=(X-a*500-b*100)/50;
        if (c>=0 && c<=C)
          res++;
      }
    }
    System.out.println(res);
  }
}


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

int		main(void)
{
	int n;

	cin >> n;
	ll ans = 0;

	if (n == 0)
		ans = 2;
	if (n == 1)
		ans = 1;
	ll a = 2, b = 1;

	for (int i = 2; i <= n; i++)
	{	
		ans = a + b;
		a = b;
		b = ans;
	}
	cout << ans << endl;
}



Measured memory_bytes: 256
X,Y,A,B,C=list(map(int, input().split()))
p=sorted(list(map(int, input().split())),reverse=True)
q=sorted(list(map(int, input().split())),reverse=True)
r=sorted(list(map(int, input().split())),reverse=True)
#print(p,q,r)

s=sorted(p[:X]+q[:Y])
#print(s)
for i in range(min(len(r),len(s))):
    if s[i]<r[i]:
        s[i]=r[i]
    else:
        break
#print(s)
print(sum(s))

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

int main() {
  int n1, n2, n3, n4;
  cin >> n1 >> n2 >> n3 >> n4;

  array<bool, 10> a;
  a[n1] = a[n2] = a[n3] = a[n4] = true;

  if (a[1] && a[9] && a[7] && a[4])
    puts("YES");
  else
    puts("NO");
}

Measured memory_bytes: 256
#include<stdio.h>
void Preorder(int);void  Inorder(int);void Postorder(int);
//ST[1]は親はST[0]|は子の数
int ST[100000][2];
int ST2[100000][2];
int main(){
  int n,i,j,NN,MN,free;
  scanf("%d",&n);
  for(i=0;i<n;i++)ST2[i][1]=-1;
  for(i=0;i<n;i++){
    scanf("%d",&NN);
    MN=2;
    ST2[NN][0]=MN;
    for(j=0;j<MN;j++){
      scanf("%d",&free);
      ST[NN][j]=free;
      if(free==-1)continue;
      ST2[free][1]=NN;
    }
  }
  for(i=0;ST2[i][1]!=-1;i++);
  printf("Preorder\n");
  Preorder(i);
  printf("\nInorder\n");
  Inorder(i);
  printf("\nPostorder\n");
  Postorder(i);
  printf("\n");
  return 0;
}
void Preorder(int i){
  if(i==-1)return;
  printf(" %d",i);
  Preorder(ST[i][0]);
  Preorder(ST[i][1]);
}
void Inorder(int i){
   if(i==-1)return;
  Inorder(ST[i][0]);
  printf(" %d",i);
  Inorder(ST[i][1]);
}
void Postorder(int i){
  if(i==-1)return;
  Postorder(ST[i][0]);
  Postorder(ST[i][1]);
  printf(" %d",i);
}



Measured memory_bytes: 2132
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int t_HP = Integer.parseInt(sc.next());
		int t_atk = Integer.parseInt(sc.next());
		int a_HP = Integer.parseInt(sc.next());
		int a_atk = Integer.parseInt(sc.next());

		while (true) {
			a_HP -= t_atk;
			if (a_HP <= 0) {
				System.out.println("Yes");
				break;
			}

			t_HP -= a_atk;
			if (t_HP <= 0) {
				System.out.println("No");
				break;
			}
		}
	}

}


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

using namespace std;
using ll = long long;
using pint = pair<int, int>;

int main() {
	int H, W;
	cin >> H >> W;

	vector<string> ans(2 * H);
	for (int i = 0; i < 2 * H; i += 2) {
		cin >> ans[i];
		ans[i + 1] = ans[i];
	}

	for (auto o : ans) {
		cout << o << endl;
	}
	return 0;
}


Measured memory_bytes: 3624
import sys
sys.setrecursionlimit(10**6)
def MI():  return map(int, input().split())
N,Q=MI()
graph=[[] for i in range(N)]
for i in range(1,N):
  a,b=MI()
  graph[a-1].append(b-1)
  graph[b-1].append(a-1)
point=[0]*N  
for i in range(Q):
  p,x=MI()
  point[p-1]+=x
def dfs(now,pre=-1):  
  for next in graph[now]:
    if next==pre:
      continue
    point[next]+=point[now]
    dfs(next,now)
dfs(0)
print(*point)

Measured memory_bytes: 282864
// 

#include <iostream>
#include <cmath>
#include <vector>
#include <algorithm>
#include <unordered_map>
#include <ios>
#include <iomanip>
#include <string>
#include <numeric>

using namespace std;

int main() {
    int a, b;
    cin >> a >> b;
    if (a >= 13) {
        cout << b << endl;
    } else if (6 <= a && a <= 12) {
        cout << b / 2 << endl;
    } else {
        cout << 0 << endl;
    }

    return 0;
}


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

using namespace std;
const int maxN=1e5+100;
int n,m;
vector<pair<int,int> > g[maxN];
int mx1[maxN],mx2[maxN];
bool mark[maxN];

#define mp make_pair
void input()
{
  cin>>n;
  for(int i=1;i<=n-1;i++)
    {
      int k1,k2,w;
      cin>>k1>>k2>>w;
      g[k1+1].push_back(mp(k2+1,w));
      g[k2+1].push_back(mp(k1+1,w));
    }
}
void dfs(int v)
{
  mark[v]=true;
  
  for(int i=0;i<g[v].size();i++)
    if(!mark[g[v][i].first])
    {
      dfs(g[v][i].first);
      if(mx1[g[v][i].first]+g[v][i].second>mx2[v])
	{
	  mx2[v]=mx1[g[v][i].first]+g[v][i].second;
	  if(mx2[v]>mx1[v])
	    swap(mx2[v],mx1[v]);
	}
    }
}

int main()
{
  input();
  dfs(1);
  int ans=0;
  for(int i=1;i<=n;i++)
    ans=max(ans,mx1[i]+mx2[i]);
  cout<<ans<<endl;
  
  return 0;
}

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

int main(){
  string S, T;

  cin >> S;
  cin >> T;

  int c = 0;

  for (int n = 0; n < S.size(); n++){
    if (S.at(n) != T.at(n)){
      c++;
    }
  }
  cout << c << endl;
  
  return 0;
}


Measured memory_bytes: 3916
$a=Array.new()
class Tree
  attr_accessor :id,:parent,:depth,:children,:type
  def initialize(id,children)
    @id=id
    @parent=-1
    @children=children
    @type=(children==[] ? 'leaf' : 'internal node')
  end
  def print
    puts "node #{id}: parent = #{parent}, depth = #{depth}, #{type}, #{children}"
  end
  def setDepth
    children.each do |c|
      $a[c].depth = depth + 1
      $a[c].setDepth
    end
  end
end
n=gets.to_i
n.times do
  id,d,*children=gets.split.map(&:to_i)
  $a << Tree.new(id,children)
end
$a.sort_by! {|e| e.id}
$a.each {|ele|
  ele.children.each {|e|
    $a[e].parent=ele.id
  }
}
$a.each do |e|
  if e.parent==-1
    e.type='root'
    e.depth=0
    e.setDepth
  end
end
$a.each {|e| e.print}

Measured memory_bytes: 40500
n = int(input())
v = [int(i) for i in input().split()] 

gu = v[::2]
ki = v[1::2]

import collections as co
ki_c = co.Counter(ki)
gu_c = co.Counter(gu)


ki_m = ki_c.most_common()
gu_m = gu_c.most_common()

ki_m.append((0,0))
gu_m.append((0,0))

if ki_m[0][0] != gu_m[0][0]:
  ans = n - ki_m[0][1] - gu_m[0][1]
else:
  ans1 = n - ki_m[0][1] - gu_m[1][1]
  ans2 = n - ki_m[1][1] - gu_m[0][1]
  ans = min(ans1, ans2)
print(ans)


Measured memory_bytes: 21668
import math
a,b,x = map(int,input().split())

if x >= 0.5 * a**2 * b:
    tan_x = 2*(b*a**2 -x)/a**3

else:
    tan_x = (b**2 * a)/(2*x)

print(math.degrees(math.atan(tan_x)))


Measured memory_bytes: 9164
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace abc_057_A
{
    class Program
    {
        static void Main(string[] args)
        {
            int[] a = Console.ReadLine().Split().Select(int.Parse).ToArray();
            Console.WriteLine((a[0]+a[1])%24);
        }
    }
}


Measured memory_bytes: 13396
use std::io::*;
use std::str::FromStr;

pub fn read<T: FromStr>() -> T {
  let stdin = stdin();
  let stdin = stdin.lock();
  let token: String = stdin
    .bytes()
    .map(|c| c.expect("failed to read char") as char)
    .skip_while(|c| c.is_whitespace())
    .take_while(|c| !c.is_whitespace())
    .collect();
  token.parse().ok().expect("failed to parse token")
}

use std::cmp::{max, min};
use std::collections::HashMap;

fn main() {
  let n = read::<usize>();
  let m = read::<usize>();
  let mut map: Vec<Vec<usize>> = vec![vec![0; n + 1]; n + 1];

  for _ in 0..m {
    let a = read::<usize>();
    let b = read::<usize>();
    map[a][b] = 1;
    map[b][a] = 1;
  }

  let mut visited: Vec<usize> = vec![];
  let mut node = 1;
  let mut cnt = 0;

  dfs(node, &mut visited, &map, n, &mut cnt);
  println!("{}", cnt);
}


fn dfs(node: usize, visited: &mut Vec<usize>, map: &Vec<Vec<usize>>, n: usize, cnt: &mut i64) {
  if visited.contains(&node) {
    return;
  }
  visited.push(node);


  if visited.len() == n {
    *cnt += 1;
    return;
  }

  for (i, v) in map[node].iter().enumerate() {
    if *v == 1 {
      let mut copy_visited = visited.clone();
      dfs(i, &mut copy_visited, map, n, cnt);
    }
  }
}

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

from fractions import gcd

N = int(input())
A = list(map(int, input().split()))

l_gcd_list = [0]
r_gcd_list = [0]
for i in range(N):
    l_gcd_list.append(gcd(l_gcd_list[i], A[i]))
    r_gcd_list.append(gcd(r_gcd_list[i], A[-(i+1)]))
r_gcd_list = r_gcd_list[::-1]
# print(l_gcd_list)
# print(r_gcd_list)

results = []
for i in range(N):
    results.append(gcd(l_gcd_list[i], r_gcd_list[i+1]))

print(max(results))


Measured memory_bytes: 16144
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <math.h>
#include <iomanip>
#include <map>
using namespace std;

#define INF 1e9
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
typedef long long ll;


int main() {
    int a, b;
    cin >> a >> b;
    if (a % 3 == 0 || b % 3 == 0 || (a + b) % 3 == 0) {
        cout << "Possible" << endl;
    }
    else cout << "Impossible" << endl;
}

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

#define  __  ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define  int  long long
#define  endl  '\n'
const double pi = acos(-1);
const int mod = 1e9 + 7;
//______________________



int32_t main()
{ 
  __
  
  int n;
  cin >> n;
  int h[n];

  for(int i = 0; i < n; i++)
    cin >> h[i];

  h[0]--;

  for(int i = 1; i < n; i++)
  {
    if(h[i] > h[i - 1])
        h[i]--;
    else if(h[i] == h[i - 1])
        continue;
    else
        return cout << "No", 0;
  }

  cout << "Yes";

 return 0;
}

Measured memory_bytes: 1024
import java.util.Scanner;

public class Main{
    public static void main(String args[]){
        Scanner sc = new Scanner(System.in);
        int i = 1;
        while(true){
            int a = sc.nextInt();
            if(a==0){
                break;
            }
            System.out.println("Case "+i+": "+a);
            
            i++;
            
        }
        
        sc.close();
    }
}


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

int main() {
    string S;
    cin >> S;
    if(S[0] != S[1] && S[1] != S[2] && S[0] != S[2]) {
        cout << "Yes" << endl;
    }
    else {
        cout << "No" << endl;
    }
}

Measured memory_bytes: 384
#include <stdio.h>

#define MAX 100000

int parent(int i){
  return i/2;
}

int left(int i){
  return i*2;
}

int right(int i){
  return i*2+1;
}

int main(){
  int n, i, A[MAX];
  scanf("%d",&n);
  for(i=1;i<=n;i++) scanf("%d",&A[i]);

  for(i=1;i<=n;i++){
    printf("node %d: key = %d, ",i,A[i]);
    if(parent(i)>=1) printf("parent key = %d, ",A[parent(i)]);
    if(left(i)<=n) printf("left key = %d, ",A[left(i)]);
    if(right(i)<=n) printf("right key = %d, ",A[right(i)]);
    printf("\n");
  }
  
  return 0;
}


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

using ll = long long;
using ld = long double;
using pii = pair<int, int>;

#define REP(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define all(x) (x).begin(),(x).end()
#define m0(x) memset(x,0,sizeof(x))

int dx4[4] = {1,0,-1,0}, dy4[4] = {0,1,0,-1};


int main()
{
    int n;
    cin>>n;
    int dp[100100];
    
    for(int i = 0; i <= n; i++)
    {
        dp[i]=i;
    }
    
    
    for(int mul = 6; mul <= n; mul*=6)
    {
        for(int i = 0; i+mul <= n; i++)
        {
            dp[i+mul]=min(dp[i+mul], dp[i]+1);
        }    
    }
        
    for(int mul = 9; mul <= n; mul*=9)
    {
        for(int i = 0; i+mul <= n; i++)
        {
            dp[i+mul]=min(dp[i+mul], dp[i]+1);
        }    
    }

    cout<<dp[n]<<endl;

    return 0;
}

Measured memory_bytes: 640
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstdlib>
using namespace std;
const int NN = 11000;
typedef long long ll;

ll a, b, c;

int main(){
	//freopen("a.in", "r", stdin);
	//freopen("a.out", "w", stdout);
	
	scanf("%lld%lld%lld", &a, &b, &c);
	if (c - a - b <= 0){
		printf("No");
		return 0;	
	}  
	ll l = (a + b - c) * (a + b - c);
	ll r = 4 * a * b;
	if (l > r) printf("Yes");
	else printf("No"); 

	

	return 0;
} 

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main(){
    long long a, b, k, ansa, ansb;
    cin >> a >> b >> k;
    ansa=max((long long)0, a-k);
    k=max(k-a, (long long)0);
    ansb=max((long long)0, b-k);
    cout <<  ansa << " " << ansb <<endl;
    return 0;

}

Measured memory_bytes: 256
#include <stdio.h>
int main(){
	int n,m,l;
	int i,j,k;
	int a[110][110];
	int b[110][110];
	long long c[110][110]={0};
	scanf("%d %d %d",&n,&m,&l);
	for(i=0;i<n;i++){
		for(j=0;j<m;j++){
			scanf("%d",&a[i][j]);
		}
	}
	for(i=0;i<m;i++){
		for(j=0;j<l;j++){
			scanf("%d",&b[i][j]);
		}
	}
	for(i=0;i<n;i++){
		for(j=0;j<l;j++){
			for(k=0;k<m;k++){
				c[i][j]+=a[i][k]*b[k][j];
			}
			if(j!=0) printf(" ");
			printf("%ld",c[i][j]);
		}
		puts("");
	}
	return 0;
}

Measured memory_bytes: 812
import bisect
A, B, Q = map(int, input().split())
INF = 10 ** 18
s = [-INF] + [int(input()) for i in range(A)] + [INF]
t = [-INF] + [int(input()) for i in range(B)] + [INF]
for q in range(Q):
    x = int(input())
    b, d = bisect.bisect_right(s, x), bisect.bisect_right(t, x)
    res = INF
    for S in [s[b - 1], s[b]]:
        for T in [t[d - 1], t[d]]:
            d1, d2 = abs(S - x) + abs(T - S), abs(T - x) + abs(S - T)
            res = min(res, d1, d2)
    print(res)

Measured memory_bytes: 14056
#include <iostream> // cin, cout, cerr, clog
#include <algorithm> // minmax, sort, swap
#include <numeric> // iota, accumulate, inner_product
#include <cstdio> // printf, scanf
#include <climits> // INT_MIN, LLONG_MIN
#include <cmath> // long, trig, pow
#include <string> // string, stoi, to_string
#include <vector> // vector
#include <queue> // queue, priority_queue
#include <deque> // deque
#include <stack> // stack
#include <map> // key-value pairs sorted by keys
#include <set> // set
#include <unordered_map> // hashed by keys
#include <unordered_set> // hashed by keys
#include <iomanip> // cout<<setprecision(n)
#include <functional> // std::function<void(int)>

#define rep(i,n) for(int i = 0; i < n; i++)
#define ENDL "\n"
#define print(i) std::cout << (i) << "\n"

#define int long long // at least int64 > 9*10^18
#define all(v) v.begin(), v.end()

signed main() {
	int a,b;
	std::cin >> a >> b;
	print(std::max({a+b,a-b,a*b}));
	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0; i<(n); i++)
#define FOR(i,a,n) for(int i=(a); i<(n); i++)
#define all(v) v.begin(), v.end()
using namespace std;
typedef long long ll;
const int INF = 1e9;
const int MOD = 1e9+7;

struct node{
    int number;
    int x;
    int y;
};

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

    while(true) {
        int n; cin >> n;
        if(!n) break;

        vector<node> a;
        node nd = {0, 0, 0};
        a.push_back(nd);

        FOR(i, 1, n) {
            int to, act; cin >> to >> act;
            for(const auto aa: a) {
                if (aa.number == to) {
                    int nx = aa.x;
                    int ny = aa.y;
                    if (act==0) nx--;
                    else if (act==1) ny--;
                    else if (act==2) nx++;
                    else ny++;
                    node nd = {i, nx, ny};
                    a.push_back(nd);
                }
            }
        }

        int max_x=0, min_x=INF, max_y=0, min_y=INF;
        for(const auto aa: a) {
            max_x = max(max_x, aa.x);
            min_x = min(min_x, aa.x);
            max_y = max(max_y, aa.y);
            min_y = min(min_y, aa.y);
        }

        cout << max_x-min_x+1 << " " << max_y-min_y+1 << endl;
    }
}


Measured memory_bytes: 3152
#include <bits/stdc++.h>
using namespace std;
#define REP(i,b,e) for(int i=(b);i<(e);++i)
#define RREP(i,b,e) for(int i=(b)-1;i>=e;--i)
#define rep(i,e) for(int i=0;i<(e);++i)

constexpr int MOD = 1000000007;
constexpr int INF = 1LL << 30;
constexpr long long LLINF = 1LL << 60;

inline void print(void) { cout<<'\n'; }
template<class T> inline void print(const T &x) { cout<<x<<'\n'; }
template<class T, class... U> inline void print(const T &x, const U&... y) { cout<<x<<" "; print(y...); }

template<typename T>
vector<vector<T>> warshall_floyd(const vector<vector<pair<int, T>>> &graph) {
  int n = graph.size();
  vector<vector<T>> dists(n, vector<T>(n, numeric_limits<T>::max()));
  for (int i = 0; i < n; ++i) {
    dists[i][i] = 0;
    for (auto e : graph[i]) {
      int nx; T cost;
      tie(nx, cost) = e;
      dists[i][nx] = cost;
    }
  }
  for (int k = 0; k < n; ++k) {
    for (int i = 0; i < n; ++i) if (dists[i][k] != numeric_limits<T>::max()) {
      for (int j = 0; j < n; ++j) if (dists[k][j] != numeric_limits<T>::max()) {
        dists[i][j] = min(dists[i][j], dists[i][k]+dists[k][j]);
      }
    }
  }
  return dists;
}

int main() {
  int n, m, rt; cin>>n>>m>>rt;
  vector<int> r(rt);
  rep(i, rt) {
    cin>>r[i]; --r[i];
  }
  sort(r.begin(), r.end());
  vector<vector<pair<int, int>>> g(n);
  rep(i, m) {
    int a, b, c; cin>>a>>b>>c;
    --a; --b;
    g[a].emplace_back(b, c);
    g[b].emplace_back(a, c);
  }

  auto dists = warshall_floyd(g);
  int ans = INF;
  do {
    int t = 0;
    rep(i, rt-1) {
      t += dists[r[i]][r[i+1]];
    }
    ans = min(ans, t);
  } while (next_permutation(r.begin(), r.end()));
  print(ans);

  return 0;
}


Measured memory_bytes: 768
#include <iostream>
#include <algorithm>
#include <math.h> 
#include <string>
#include <iomanip>
#include <vector>
using namespace std;
int main(){
    int n, t, a;
    cin >> n >> t >> a;
    int h[1500];
    double temp[1500];
    for(int i = 0; i < n; i++){
        cin >> h[i];
        temp[i] = t - h[i]*0.006;
    }

    double dis = 100000;
    int ans;

    for(int i = 0; i < n; i++){
        if(fabs(temp[i] - a) < dis){
            dis = fabs(temp[i] - a);
            ans = i + 1;
        }
    }

    cout << ans << endl;
}

Measured memory_bytes: 256
//AtCoder ABC116 B - Collatz Problem
#include <bits/stdc++.h>
using namespace std;
using ll=int64_t;
int main() {
#if LOCAL&0
    std::ifstream in("./test/sample-1.in"); //input.txt
    std::cin.rdbuf(in.rdbuf());
#endif
    ll s; cin>>s;
    ll i=1;
    ll prev=s,next=s;
    vector<ll> tbl;
    //tbl.push_back(s);
    do{
        prev=next;
        tbl.push_back(prev);
        if (prev%2==0){
            next=prev/2;
        } else {
            next=3*prev+1;
        }
		++i;
    }while(find(tbl.begin(),tbl.end(),next)==tbl.end());
    cout<<i<<endl;
    return 0;
}

Measured memory_bytes: 256
from sys import stdin
nii=lambda:map(int,stdin.readline().split())
lnii=lambda:list(map(int,stdin.readline().split()))

n,m=nii()

ms=1900*m+100*(n-m)

ans=0
for i in range(1,10**6):
  p1=0.5**m
  p2=(1-0.5**m)**(i-1)
  p=p1*p2
  t_ms=ms*i
  ans+=p*t_ms

ans=int(ans)
q=ans%10
if q!=0:
  ans+=10-q

print(ans)

Measured memory_bytes: 9444
def insersionSort(A, N):
    for i in range(1, N):
        print " ".join([str(k) for k in A])
        v = A[i]
        j = i - 1
        while j >= 0 and A[j] > v:
            A[j+1] = A[j]
            j -= 1
        A[j+1] = v
    return A

if __name__ == "__main__":
    N = int(raw_input())
    A = map(int, raw_input().split())
    A = insersionSort(A, N)
    print " ".join([str(k) for k in A])

Measured memory_bytes: 6464
#include<stdio.h>

int main(void){
  int a, b, c, d, e, f, g;

  scanf("%d", &a);
  scanf("%d", &b);
  scanf("%d", &c);
  scanf("%d", &d);
  
  if(a<c){
    e = c;
  }
  else{
    e = a;
  }
  if(b<d){
    f = b;
  }
  else{
    f = d;
  }
  g = f-e;
  
  if(b<c || d<a){
    printf("0");
  }
  else{
    printf("%d", g);
  }
  

  return 0;
}


Measured memory_bytes: 128
S = list(input())

ans = 0
if len(S) % 2 == 0:
    l = S[:len(S) // 2]
    r = list(reversed(S[len(S) // 2:]))
    for i in range(len(l)):
        if l[i] != r[i]:
            ans += 1
else:
    l = S[:len(S) // 2]
    r = list(reversed(S[(len(S) // 2)+1:]))
    for i in range(len(l)):
        if l[i] != r[i]:
            ans += 1

print(ans)

Measured memory_bytes: 3064