akhauriyash/Code-Regression huggingface dataset:
fact_list=[None]*300001
inv_fact_list=[None]*300001
fact_list[0]=1
inv_fact_list[0]=1
"""
def inv(n):
    if inv_fact_list[n]!=None:
        return inv_fact_list[n]
    m=fact_list[n]
    s=1
    for i in range(30):
        if i!=23 and i!=26:
            s=(s*m)%998244353
        m=(m**2)%998244353
    inv_fact_list[n]=s
    return s
def enc(n):
    if n==0:
        return "("
    s=""
    while n>0:
        s+=chr(n%86+40)
        n//=86
    return s
 
def dec(s):
    n=0
    for i in range(len(s)):
        n+=(86**i)*(ord(s[i])-40)
    return n
"""
def comb(n,r):
    if r==0 or r==n:
        return 1
    if r==1 or r==n-1:
        return n
    if inv_fact_list[n-r]!=None:
        invnr=inv_fact_list[n-r]
    else:
        m=fact_list[n-r]
        invnr=1
        for i in range(30):
            if i!=23 and i!=26:
                invnr=(invnr*m)%998244353
            m=(m**2)%998244353
        inv_fact_list[n-r]=invnr
    if inv_fact_list[r]!=None:
        invr=inv_fact_list[r]
    else:
        m=fact_list[r]
        invr=1
        for i in range(30):
            if i!=23 and i!=26:
                invr=(invr*m)%998244353
            m=(m**2)%998244353
        inv_fact_list[r]=invr
    return (((fact_list[n]*invnr)%998244353)*invr)%998244353
 
for i in range(1,300001):
    fact_list[i]=(fact_list[i-1]*i)%998244353
 
s=input().split()
n,a,b,k=int(s[0]),int(s[1]),int(s[2]),int(s[3])
res=0
for i in range(n+1):
    if k-a*i<0:
        break
    if (k-a*i)%b==0 and 0<=(k-a*i)//b<=n:
        res=(res+comb(n,i)*comb(n,(k-a*i)//b))%998244353
print(res)

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

#define REP(i, n ,N) for(ll i = (n); i < (N); i++)
#define RREP(i, n ,N) for(ll i = (N-1); i >= (n); i--)
#define p(s) cout<<(s)<<endl
#define p2(a, b) cout<<(a)<<" "<<(b)<<endl
using namespace std;
typedef long long ll;
ll mod = 1e9+7;
ll inf = 1e18;

ll N;
string S;
bool dp[11][11][11];
ll ans;
int main(){
	cin >> N >> S;
	REP(i,0,S.size()){
		ll now = S[i] - '0' + 1;
		RREP(j,0,11){
			if(j == 0) {
				dp[now][0][0] = true;
			}else{
				RREP(k,0,11){
					if(k == 0){
						dp[j][now][0] = dp[j][0][0];
					}else{
						dp[j][k][now] = dp[j][k][0];
					}
				}
			}
		}
	}
	REP(i,1,11){
		REP(j,1,11){
			REP(k,1,11){
				ans += dp[i][j][k];
			}
		}
	}
	p(ans);
	return 0;
}

Measured memory_bytes: 256
#include<cstdio>
#include<cstring>
#include<vector>
#include<queue>
#include<algorithm>
#include<cmath>
using namespace std;
#define rep(i,n) for(int i=0;i<(n);i++)
#define reg(i,a,b) for(int i=(a);i<=(b);i++)
typedef long long int lli;
typedef pair<int,int> mp;
#define fir first
#define sec second


bool warshell(int n,vector<mp>* vs,vector<int>* dist,vector<int> *gone){
	rep(i,n){
		gone[i].clear();
		dist[i].clear();
		gone[i].resize(n,-1);
		dist[i].resize(n,-1);
		
		gone[i][i]=1;
		dist[i][i]=0;
		rep(j,vs[i].size()){
			int to=vs[i][j].fir,
				co=vs[i][j].sec;
			gone[i][to]=1;
			dist[i][to]=co;
		}
	}
	
	rep(k,n){
		rep(i,n){
			rep(j,n){
				if(gone[i][k]==-1 || gone[k][j]==-1)continue;
				int cd=dist[i][k]+dist[k][j];
				if(gone[i][j]==-1 || dist[i][j]>cd){
					gone[i][j]=1;
					dist[i][j]=cd;
				}
			}
		}
	}
	rep(i,n)if(dist[i][i]!=0)return false;
	return true;
}


	
	
	
int n,m;

vector<mp> vs[105];


vector<int> dist[105];
vector<int> gone[105];




int main(void){
	int n,m;
	scanf("%d%d",&n,&m);
	rep(i,m){
		int a,b,c;
		scanf("%d%d%d",&a,&b,&c);
		vs[a].push_back(mp(b,c));
		//vs[b].push_back(mp(a,c));
	}
	if(warshell(n,vs,dist,gone)){
		rep(i,n){
			rep(j,n){
				if(gone[i][j]!=-1)printf("%d",dist[i][j]);
				else printf("INF");
				printf("%s",j==n-1?"\n":" ");
			}
		}
	}
	else printf("NEGATIVE CYCLE\n");
	return 0;
	
}

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

int main(){
  int N;
  int x = 0;
  string S;
  cin >> N ;
  for (int i = 0; i < N; i++){
    cin >> S;
    if(S=="Y"){
      x = 1;
    }
  }
  if(x == 1){
    cout << "Four";
  }else{
    cout << "Three";
  }
}
    

Measured memory_bytes: 256
#include<stdio.h>
int main(){
  int a,b;
  scanf("%d%d",&a,&b);
  if(a<b){
    for(int i=0;i<b;i++)printf("%d",a);
    }else{for(int i=0;i<a;i++)printf("%d",b);
          }
  printf("\n");
}

Measured memory_bytes: 128
#include <stdio.h>
#include <cstring>
#include <iostream>
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>
#include <set>
#include <string>
using namespace std;
const int maxn = 1e5+10;
vector<int> edge[maxn];
int high[maxn];
int main(){
    int n, m;
    cin>>n>>m;
    
    for(int i=0; i<n; i++){
        cin>>high[i];
    }
    int a,b;
    for(int i=0; i<m; i++){
        cin>>a>>b;
        a-=1;
        b-=1;
        edge[a].push_back(b);
        edge[b].push_back(a);
    }
    int res = 0;
    for(int i=0; i<n; i++){
        bool flag = true;
        for(int j=0; j<edge[i].size(); j++){
            if(high[edge[i][j]] >= high[i] ){
                flag = false;
            }
        }
        if(flag) ++res;
    }
    cout<<res<<endl;
    return 0;
}


Measured memory_bytes: 9132
#include<bits/stdc++.h>
#define MOD 1000000007
#define ll long long
#define mp make_pair
#define pb push_back
#define N 100010
using namespace std;
vector<int> graph[N];
int dp[N];
ll dfs(int s){
	if(dp[s] != -1)
		return dp[s];
	ll maxi = 0;
	for(auto to: graph[s]){
		maxi = max(maxi, 1 + dfs(to));
	}
	return dp[s] = maxi;
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	int n, m;
	cin >> n >> m;
	for(int i = 0; i < m; i++){
		int a, b;
		cin >> a >> b;
		graph[a - 1].pb(b - 1);
	}
	memset(dp, -1, sizeof(dp));
	int maxi = 0;
	for(int i = 0; i < n; i++){
		if(dp[i] == -1){
			dfs(i);
			maxi = max(maxi, dp[i]);
		}
	}
	cout << maxi;


}

Measured memory_bytes: 8192
#include <iostream>
using namespace std;
 
int main() {
	int x;
	int y;
 
	cin >> x;
	cin >> y;
 
	if(x<y) {
		cout << "a < b" << endl;
	}
	else if(x>y) {
		cout << "a > b" << endl;
	}
	else {
		cout << "a == b" << endl;
	}
 
	return 0;
}

Measured memory_bytes: 3084
"use strict";

const main = arg => {
  const input = arg.trim().split("\n");
  const a = arg.trim();
  let num_diffrent = 0;
  for(let i=0;i<a.length/2;i++){
    if(a[i]!==a[a.length-i-1]){
      num_diffrent++;
    }
  }
  console.log(""+num_diffrent);
  return num_diffrent;
}
main(require('fs').readFileSync('/dev/stdin', 'utf8'));

Measured memory_bytes: 7500
#include <iostream>
#include <algorithm>
#include <cmath>
#include <string>
using namespace std;
#define inf 1000000007

int main(void){
    long long int n , t;
    cin >> n >> t;
    long long int time[n];
    long long int sum = 0;
    long long int check=0;
    for(long long int i = 0; i < n; i++){
        cin >> time[i]; 
        if(time[i]<check) sum+=t-(check-time[i]);
        else if(time[i]>=check) sum+=t;
        check=time[i]+t;
    }
    cout << sum << endl;
    return 0;
}

Measured memory_bytes: 1792
#include <iostream>
#include <algorithm>

using namespace std;

int main() {
    int N;
    cin >> N;
    int H[N];
    for(int i = 0; i < N; i++) cin >> H[i];
    for(int i = N-1; i > 1; --i) {
        if(H[i-1]- H[i] == 1) {
            H[i-1]-=1;
        }else if(H[i-1]-H[i] > 1) {
            cout << "No" << endl;
            return 0;
        }
    }
    cout << "Yes" << endl;
}

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

int main() {
  ll s, c, ans;
  cin >> s >> c;
  if(2*s >= c) ans = c/2;
  else {
    ans = s;
    c -= 2*s;
    s = 0;
    ans += c/4;
  }
  cout << ans << "\n";
}

Measured memory_bytes: 256
# coding: utf-8

K, T = map(int, input().split())
A = list(map(int, input().split()))

if len(A) == 1:
    print(A[0] - 1)
else:
    A.sort()
    max_num = A.pop()
    tmp = max_num - sum(A)
    if tmp > 1:
        print(tmp - 1)
    else:
        print(0)

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

using namespace std;

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

  int n;
  string s, t;
  cin >> n >> s >> t;
  for (int i = 0; i < n; ++i) {
    cout << s[i] << t[i];
  }
  cout << endl;

  return 0;
}



Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){
  int v,d;
  while(cin>>v>>d){
    int p[1003];
    p[0]=p[1]=1;
    for(int i=2;i<v+2;i++)p[i]=(p[i-1]+p[i-2])%1001;
    sort(p+2,p+v+2);
    int ans=1;
    for(int i=2;i<v+1;i++)if(p[i+1]-p[i]>=d)ans++;
     cout<<ans<<endl;  
}
  return 0;
}

Measured memory_bytes: 1180
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

class Program
{
    static void Main(string[] args)
    {
        long value = 100;
        long x = long.Parse(Console.ReadLine());
        long year = 0;
        while (true)
        {
            value = (long)(value * 1.01);
            year++;
            if (value >= x) break;
        }
        Console.WriteLine(year);

        
    }





}



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

int main () {

    int X;
    cin >> X;
    int res(0);
    vector <int> nominations{500, 100, 50, 10, 5, 1};
    
    res += (X/500) * 1000;
    int d = X % 500;
    res += (d / 5) * 5;
    
    cout << res << "\n";
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <queue>
#include <ctime>
#include <cassert>
#include <complex>
#include <string>
#include <cstring>
#include <chrono>
#include <random>
#include <queue>
#include <bitset>
using namespace std;
 
typedef int ll;
 
#define int long long
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
#define sz(x) ((int)x.size())
#define all(x) x.begin(),x.end()
#define endl '\n'
 
typedef pair<int,int>pii;
typedef pair<int,pair<int,int> > piii;
 
const int mod=1e9+7;
 
int POWER[65];
int power(int a, int b) {int ret=1;while(b) {if(b&1) ret*=a;a*=a;if(ret>=mod) ret%=mod;if(a>=mod) a%=mod;b>>=1;}return ret;}
int inv(int x) {return power(x,mod-2);}
 
void precompute() {
	POWER[0]=1;
	for(int i=1;i<63;i++) POWER[i]=POWER[i-1]<<1LL;
}
 
int gcd(int a, int b) {
   if (b == 0)
   return a;
   return gcd(b, a % b);
}
 
ll main() {
	// freopen("Task.in", "r", stdin);freopen("Task.out", "w", stdout);

	map<int, int>rw, col;
	set<int>row, column;
	vector<pii>v;

	int h, w, m;
	cin>>h>>w>>m;
	for (int i=1; i<=m; i++) {
		int x, y;
		cin>>x>>y;
		v.pb(mp(x, y));
		rw[x]++;
		col[y]++;
	}

	int rowMax=0;
	int colMax=0;
	for (map<int, int>::iterator it = rw.begin(); it!=rw.end(); it++) {
		rowMax=max(rowMax, it->second);
	}
	for (map<int, int>::iterator it = col.begin(); it!=col.end(); it++) {
		colMax=max(colMax, it->second);
	}

	// cout<<rowMax<<" "<<colMax<<endl;

	for (map<int, int>::iterator it = rw.begin(); it!=rw.end(); it++) {
		if(it->second==rowMax) {
			row.insert(it->first);
		}
	}
	for (map<int, int>::iterator it = col.begin(); it!=col.end(); it++) {
		if(it->second==colMax) {
			column.insert(it->first);
		}
	}

	int tot=sz(row)*sz(column);
	for (int i=0; i<sz(v); i++) {
		if(row.find(v[i].ff)!=row.end() && column.find(v[i].ss)!=column.end()) {
			tot--;
		}
	}

	int ret=rowMax+colMax;
	if(tot==0)	ret--;
	cout<<ret<<endl;

}

Measured memory_bytes: 73392
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <cmath>

using namespace std;

#define REP(i,n) for (int i=0;i<(n);++i)
#define REP2(i,n) for (int i=0;i<=(n);++i)
#define REP3(i,n) for (int i=1;i<=(n);++i)


int main() {

	int N;
	cin >> N;

	vector<int> M(1000000);
	REP(i, 1000000) {
		M[i] = 999999;
	}

	vector<int> p;
	p.push_back(1);
	REP3(i, 7) {
		p.push_back(pow(6, i));
	}
	REP3(i, 6) {
		p.push_back(pow(9, i));
	}
	
	sort(p.begin(), p.end(),greater<int>());

	REP(i, p.size()) {
		M[p[i]] = 1;
	}

	REP3(i, N) {
		int tmp = 999999;
		REP(j, p.size()) {
			if (i - p[j] > 0) {
				tmp = min(tmp,M[i-p[j]]+1);
			}
			M[i] = min(tmp,M[i]);
		}
	}

	cout << M[N] << endl;

	int end;
	cin >> end;

	return 0;
}

Measured memory_bytes: 4096
# -*- coding: utf-8 -*-
import sys
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

def main():
    H,W=map(int,input().split())
    ans=INF
    for i in range(1,H):
        S0=W*i
        S1=(H-i)*(W//2)
        S2=(H-i)*(-(-W//2))
        S3=W*((H-i)//2)
        S4=W*(-((i-H)//2))
        ans=min(ans,max(abs(S0-S1),abs(S0-S2)),max(abs(S0-S3),abs(S0-S4)))
    for i in range(1,W):
        S0=H*i
        S1=(W-i)*(H//2)
        S2=(W-i)*(-(-H//2))
        S3=H*((W-i)//2)
        S4=H*(-((i-W)//2))
        ans=min(ans,max(abs(S0-S1),abs(S0-S2)),max(abs(S0-S3),abs(S0-S4)))
    print(ans)

if __name__ == '__main__':
    main()


Measured memory_bytes: 40688
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
using Graph = vector<vector<int>>;
using P = pair<int, int>;

int main()
{
  string S;cin>>S;
  for (int i=0;i<S.size();i++)
  {
    if (i%2==0)
    {
      if (S[i]=='L') 
      {
        cout<<"No"<<endl;
        return 0;
      }
    }
    else
    {
      if (S[i]=='R')
      {
        cout<<"No"<<endl;
        return 0;
      }
    }
  }
  
  cout<<"Yes"<<endl;
  return 0;
}

Measured memory_bytes: 256
box = [1,0,0,0]
for c in input():
    if c == "A":
        box[1] = box[0]+box[1]
    elif c == "B":
        box[2] = box[1]+box[2]
    elif c == "C":
        box[3] = box[2]+box[3] 
    elif c == "?":
        box = [box[0]*3,box[1]*3+box[0],box[2]*3+box[1],box[3]*3+box[2]]

    box = [i%(10**9+7) for i in box]
print(box[3])

Measured memory_bytes: 3188
#include <bits/stdc++.h>
using namespace std;
 
int main() {
	int N, K;
	cin >> N >> K;
  
  	int L;
  	L = 0;
  
  while(N){
    int x;
    cin >> x;
    if(2*x < K){
      L += 2*x;
    }
    else{
      L += 2*(K-x);
    }
    
    N--;
    
  }
  
  cout << L << endl;
  
  
}

Measured memory_bytes: 256
#include<iostream>
using namespace std;
int s[400][26];
int last[26];
int LAST(int i, int index, int j1, int j2, int j3, int j4);
int main() {

	int d;
	cin >> d;
	int c[26];
	int heu = 6;
	int i, j, j2, j3, j4;
	for (i = 0; i < 26; i++) {
		cin >> c[i];
	}

	for (i = 0; i < d; i++) {
		for (j = 0; j < 26; j++) {
			cin >> s[i][j];
		}
	}
	for (i = 0; i < 26; i++) {
		last[i] = 0;
	}
	int jmax, jindex, jindex2, jindex3, jindex4;
	for (i = 1; i <= d; i++) {

		jmax = 0;
		jindex = -1;
		jindex2 = -1;
		jindex3 = -1;
		jindex4 = -1;
		/*for (j = 0; j < 26; j++) {
			if (c[j] *(i - last[j]) > jmax) {
				jmax = c[j] *(i - last[j]);
				jindex = j;
			}
			else if (c[j] *(i - last[j]) == jmax) {
				if (s[i - 1][j] > s[i - 1][jindex]) {
					jindex = j;
				}
			}
		}*/
		for (j = 0; j < 26; j++) {
			for (j2 = 0; j2 < 26; j2++) {
				for (j3 = 0; j3 < 26; j3++) {
					for(j4 = 0;j4<26;j4++){
						if (s[i - 1][j] + heu * c[j] * LAST(i,1,j,j2,j3,j4) + s[i][j2] + heu * c[j2] * LAST(i, 2, j, j2, j3, j4) + heu * c[j3] * LAST(i, 3, j, j2, j3, j4) + heu * c[j4] * LAST(i, 4, j, j2, j3, j4) > jmax) {
							jmax = s[i - 1][j] + heu * c[j] * LAST(i, 1, j, j2, j3, j4) + s[i][j2] + heu * c[j2] * LAST(i, 2, j, j2, j3, j4) + heu * c[j3] * LAST(i, 3, j, j2, j3, j4) + heu * c[j4] * LAST(i, 4, j, j2, j3, j4);
							jindex = j;
						}
					}
				}
			}
		}
		/*for (j = 0; j < 26; j++) {
			if (s[i - 1][j] + 15 * c[j] * (i - last[j]) >= jmax) {
				jmax = s[i - 1][j] + 15 * c[j] * (i - last[j]);
				jindex = j;
			}
		}*/
		last[jindex] = i;
		cout << jindex + 1 << endl;
		


	}
	return 0;


}
int LAST(int i, int index, int j1, int j2, int j3, int j4) {
	if (index == 1) {
		return i - last[j1];
	}
	else if (index == 2) {
		if (j2 == j1) {
			return 1;
		}
		else {
			return i + 1 - last[j2];
		}
	}
	else if (index == 3) {
		if (j3 == j2) {
			return 1;
		}
		else if (j3 == j1) {
			return 2;
		}
		else {
			return i + 2 - last[j3];
		}

	}
	else if (index == 4) {
		if (j4 == j3) {
			return 1;
		}
		else if(j4 == j2){
			return 2;
		}
		else if (j4 == j1) {
			return 1;
		}
		else {
			return i + 3 - last[j4];
		}
	}
}


Measured memory_bytes: 3644
import numpy as np

H,W=list(map(int,input().split()))
h,w=list(map(int,input().split()))

s=np.zeros((H,W))
for i in range(h):
    for j in range(W):
        s[i][j]=-1
for i in range(w):
    for j in range(H):
        s[j][i]=-1
        
count=0
for i in range(H):
    for j in range(W):
        if s[i][j]==0:
            count+=1
print(count)

Measured memory_bytes: 12392
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <math.h>

#define ll long long int
#define mod 1000000007

using namespace std;


int main()
{
    ios_base::sync_with_stdio(false); 
    cin.tie(NULL);
    int h,w;
    cin >> h >> w;
    
    vector<vector<char>> vec(h,vector<char>(w));
    
    for(int i = 0;i<h;i++){
        for(int j =0;j<w;j++){
            char x;
            cin >> x;
            vec[i][j] = x;
        }
    }
    
    vector<vector<ll>> dp(h,vector<ll>(w,0));
    
    for(int i = 0;i<w;i++){
        if(vec[0][i] == '.')
        dp[0][i] = 1;
        else
        break;
    }
    for(int i = 0;i<h;i++){
        if(vec[i][0] == '.')
        dp[i][0] = 1;
        else
        break;
    }
    for(int i = 1; i<h;i++){
        for(int j =1;j<w;j++){
            if(vec[i][j] == '.')
            dp[i][j] = (dp[i-1][j]%mod + dp[i][j-1]%mod)%mod;
            else
            dp[i][j] = 0;
        }
    }
    cout << dp[h-1][w-1];
}









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

using namespace std;

typedef long long ll;

int main(){
  ll n;
  cin >> n;
  ll mini = 300000;
  ll ans = 0;
  for(ll i=0;i<n;i++){
    ll a;
    cin >> a;
    if(mini > a){
      mini = a;
      ans ++;
    }
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 256
#include <iostream>
using namespace std;
int main(){
  int N, M;
  cin >> N >> M;
  int p = (1<<M);
  long long int ans = 0, t = (1900*M + (N-M)*100), c = 1;
  for(int i = 0; i < M; ++i) t *= 2;
  cout << t << endl;
  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
using namespace std;
int main(int argc, char* argv[])
{
int a, b, c;
char op;
c=1;

while(c)
{
cin >> a >> op >> b;
switch(op)
{
case '+' :
cout << a+b << endl;
break;
case '-' :
cout << a-b << endl;
break;
case '*' :
cout << a*b << endl;
break;
case '/' :
cout << a/b << endl;
break;
case '?' :
c = 0;
}
}
return 0;
}


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

typedef long long ll;
const int MAXN = 1010;

vector<int> G[MAXN];
int n, s, t, ans1; ll ans;
int dep[MAXN], mx[MAXN];

void dfs(int x, int fa)
{
	dep[x] = dep[fa] + 1;
	int du = 0;
	for(int i = 0; i < (int)G[x].size(); ++i)
	{
		int y = G[x][i];
		if(y == fa) continue;
		dfs(y, x);
		++du;
	}
	mx[dep[x]] = max(mx[dep[x]], du);
}

int main()
{
	scanf("%d", &n);
	for(int i = 1; i < n; ++i)
	{
		int u, v; scanf("%d %d", &u, &v);
		G[u].push_back(v);
		G[v].push_back(u);
	}
	dfs(1, 0);
	for(int i = 1; i <= n; ++i) if(dep[i] > dep[s]) s = i;
	dfs(s, 0);
	for(int i = 1; i <= n; ++i) if(dep[i] > dep[t]) t = i;
	ans1 = (dep[t] + 1) >> 1;
	printf("%d ", ans1);
	for(int i = 1; i <= n; ++i)
	{
		memset(mx, 0, sizeof(mx));
		mx[0] = 1; ll res = 1;
		dfs(i, 0);
		for(int j = 0; j <= n; ++j)
		{
			if(!mx[j]) break;
			res = res * mx[j];
		}
		if(mx[ans1]) continue;
		if(!ans || res < ans) ans = res;
	}
	for(int x = 1; x <= n; ++x)
		for(int i = 0; i < (int)G[x].size(); ++i)
		{
			int y = G[x][i];
			memset(mx, 0, sizeof(mx));
			mx[0] = 2; ll res = 1;
			dep[x] = 0; dfs(y, x);
			dep[y] = 0; dfs(x, y);
			for(int j = 0; j <= n; ++j)
			{
				if(!mx[j]) break;
				res = res * mx[j];
			}
			if(mx[ans1]) continue;
			if(!ans || res < ans) ans = res;
		}
	printf("%lld\n", ans);
	return 0;
}

Measured memory_bytes: 256
package main

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

func main() {
	io, flush := NewIO()
	defer flush()

	n := io.ScanInt()
	p := io.ScanInts(n)
	var minCount int
	for i := range p {
		if i+1 != p[i] {
			continue
		}
		minCount++
		if i == len(p)-1 {
			p[i], p[i-1] = p[i-1], p[i]
		} else {
			p[i], p[i+1] = p[i+1], p[i]
		}
	}
	fmt.Println(minCount)
}

type IO struct {
	scanner *bufio.Scanner
	writer  *bufio.Writer
}

func NewIO() (*IO, func()) {
	io := &IO{
		scanner: newScanner(),
		writer:  newWriter(),
	}
	return io, func() { io.writer.Flush() }
}

func newScanner() *bufio.Scanner {
	s := bufio.NewScanner(os.Stdin)
	s.Buffer(make([]byte, 10000000), 10000000)
	s.Split(bufio.ScanWords)
	return s
}

func newWriter() *bufio.Writer {
	return bufio.NewWriter(os.Stdout)
}

func (io *IO) ScanBytes() []byte {
	if !io.scanner.Scan() {
		panic("scan string failed")
	}
	return io.scanner.Bytes()
}

func (io *IO) ScanString() string {
	if !io.scanner.Scan() {
		panic("scan string failed")
	}
	return io.scanner.Text()
}

func (io *IO) ScanStrings(n int) []string {
	strs := make([]string, n)
	for i := 0; i < n; i++ {
		strs[i] = io.ScanString()
	}
	return strs
}

func (io *IO) Scan2DStrings(y, x int) [][]string {
	strings := make([][]string, y)
	for i := 0; i < y; i++ {
		strings[i] = io.ScanStrings(x)
	}
	return strings
}

func (io *IO) Scan2DGraph(y int) [][]string {
	strs := make([][]string, y)
	for i := 0; i < y; i++ {
		strs[i] = strings.Split(io.ScanString(), "")
	}
	return strs
}

func (io *IO) ScanInt() int {
	return int(io.ScanInt64())
}

func (io *IO) ScanInt2() (int, int) {
	return int(io.ScanInt64()), int(io.ScanInt64())
}

func (io *IO) ScanInt3() (int, int, int) {
	return int(io.ScanInt64()), int(io.ScanInt64()), int(io.ScanInt64())
}

func (io *IO) ScanInt4() (int, int, int, int) {
	return int(io.ScanInt64()), int(io.ScanInt64()), int(io.ScanInt64()), int(io.ScanInt64())
}

func (io *IO) ScanInts(n int) []int {
	ints := make([]int, n)
	for i := 0; i < n; i++ {
		ints[i] = io.ScanInt()
	}
	return ints
}

func (io *IO) Scan2DInts(y, x int) [][]int {
	ints := make([][]int, y)
	for i := 0; i < y; i++ {
		ints[i] = io.ScanInts(x)
	}
	return ints
}

func (io *IO) ScanInt64() int64 {
	i, err := strconv.ParseInt(io.ScanString(), 10, 64)
	if err != nil {
		panic(err)
	}
	return i
}

func (io *IO) ScanFloat64() float64 {
	i, _ := strconv.ParseFloat(io.ScanString(), 64)
	return i
}

func (io *IO) ScanFloat64s(n int) []float64 {
	floats := make([]float64, n)
	for i := 0; i < n; i++ {
		floats[i] = io.ScanFloat64()
	}
	return floats
}

func (io *IO) Println(a ...interface{}) {
	fmt.Fprintln(io.writer, a...)
}


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

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

int main()
{
  string str;

  while (cin >> str){
    int i, jcnt = 0, icnt = 0;
    REP(i, str.size()){
      if (str[i] == 'I' && str[i - 1] == 'O'){
        if (str[i - 2] == 'I') icnt++;
        if (str[i - 2] == 'J') jcnt++;
      }
    }
    cout << jcnt << "\n" << icnt << endl;
  }
}

Measured memory_bytes: 1196
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <utility>
using namespace std;
typedef long long int lli;
int dx[] = {1, 0, -1, 0};
int dy[] = {0, 1, 0, -1};
const int inf = 1e9;

int main(){
    int h,w;
    cin >> h >> w;
    vector<vector<char> > fi(h+2, vector<char>(w+2, '#'));
    vector<vector<int> > minstep(h+2, vector<int>(w+2, inf));
    queue<pair<int, int> > wait;
    for(int i=1; i<=h; i++){
        for(int j=1; j<=w; j++){
            cin >> fi[i][j];
            if(fi[i][j] == '#'){
                minstep[i][j] = 0;
                wait.push(make_pair(i, j));
            }
        }
    }
    int ans = 0;
    while(!wait.empty()){
        int x = wait.front().second;
        int y = wait.front().first;
        ans = max(ans, minstep[y][x]);
        wait.pop();
        for(int d=0; d<4; d++){
            int nx = x+dx[d];
            int ny = y+dy[d];
            if(fi[ny][nx] == '.'){
                wait.push(make_pair(ny, nx));
                minstep[ny][nx] = minstep[y][x] +1;
                fi[ny][nx] = '#';
            }
        }
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 13456
import java.io.*;
import java.util.*;

public class Main {

	final static long MOD = 1000000007;
	public static String[] Ws = null;
	public static int wsIndx = 0;
	public static BufferedReader in = null;
	public static void main(String[] args) throws Exception {

		String s = nextString();
		String t = nextString();
		String ans = "No";
		if(s.equals(t.substring(0,s.length()))){
			ans="Yes";
		};

		System.out.println(ans);
	}


	public static String[] toStringArray(String s) {
		String[] tmp = new String[s.length()];
		char[] c = s.toCharArray();
		for (int i = 0; i < tmp.length; i++) {
			tmp[i] = String.valueOf(c[i]);
		}
		return tmp;
	}

	public static void check() throws Exception{
		if(in == null){
			in = new BufferedReader(new InputStreamReader(System.in));
		}
		if(Ws==null || Ws.length<=wsIndx){
			Ws = in.readLine().split(" ");
			wsIndx=0;
		}
	}
	public static int nextInt()throws Exception{
		check();
		return Integer.parseInt(Ws[wsIndx++]);
	}

	public static long nextLong()throws Exception{
		check();
		return Long.parseLong(Ws[wsIndx++]);
	}

	public static String nextString()throws Exception{
		check();
		return Ws[wsIndx++];
	}

	public static int[] nextInts()throws Exception{
		check();
		int[] tmp = new int[Ws.length];
		for(int i=0;i<tmp.length;i++){
			tmp[i]=Integer.parseInt(Ws[i]);
		}
		wsIndx=Ws.length;
		return tmp;
	}

	public static long[] nextLongs()throws Exception{
		check();
		long[] tmp = new long[Ws.length];
		for(int i=0;i<tmp.length;i++){
			tmp[i]=Long.parseLong(Ws[i]);
		}
		wsIndx=Ws.length;
		return tmp;
	}

	public static String[] nextStrings()throws Exception{
		check();
		wsIndx=Ws.length;
		return Ws;
	}


}


Measured memory_bytes: 25344
#include<bits/stdc++.h>
#define pi 3.141592653589793238
typedef long long int ll;
using namespace std;
int main(){
  ll n,m;
  cin>>n>>m;
  ll a[m],s=0;
  for(int i=0;i<m;i++){
    cin>>a[i];
    s+=a[i];
  }
  ll ans=n-s;
  if(ans>=0)
    cout<<ans<<endl;
  else
    cout<<-1<<endl;
}


Measured memory_bytes: 3676
#include <stdio.h>
#include <cmath>
#include <algorithm>
#include <cfloat>
#include <stack>
#include <queue>
#include <vector>
#include <string>
#include <iostream>
#include <set>
#include <map>
typedef long long int ll;
typedef unsigned long long int ull;
#define BIG_NUM 2000000000
#define MOD 1000000007
#define EPS 0.000000001
using namespace std;

char buf[301],left_buf[301],right_buf[301],ans[301];
int dp[301][301],memo[301][301];

void func(){

	int length,right_length;
	for(length = 0; buf[length] != '\0'; length++){
		left_buf[length] = buf[length];
		right_buf[length] = buf[length];
	}

	int ans_length = 0,right_start;

	for(int left_length = 1; left_length <= length-1; left_length++){

		right_length = length - left_length;
		right_start = left_length;

		for(int a = 0; a <= max(right_length,left_length); a++){
			for(int b = 0; b <= max(right_length,left_length); b++)dp[a][b] = 0;
		}

		for(int i = 0; i < left_length; i++){
			for(int k = 0; k < right_length; k++){
				if(left_buf[i] == right_buf[right_start+k]){
					dp[i+1][k+1] = dp[i][k]+1;
					memo[i+1][k+1] = 0;
				}else{
					if(dp[i][k+1] >= dp[i+1][k]){
						dp[i+1][k+1] = dp[i][k+1];
						memo[i+1][k+1] = 1;
					}else{
						dp[i+1][k+1] = dp[i+1][k];
						memo[i+1][k+1] = -1;
					}
				}
			}
		}


		if(ans_length < dp[left_length][right_length]){
			ans_length = dp[left_length][right_length];

			stack<char> S;

			for(int i = left_length,k = right_length; i > 0 && k > 0;){

				if(memo[i][k] == 1){
					i--;
				}else if(memo[i][k] == -1){
					k--;
				}else{ //memo[i][k] == 0
					S.push(left_buf[i-1]);
					i--;
					k--;
				}
			}

			int index = 0;
			while(!S.empty()){
				ans[index++] = S.top();
				S.pop();
			}
		}
	}

	for(int i = 0; i < ans_length; i++)printf("%c",ans[i]);
	printf("\n");
}

int main(){

	while(true){
		scanf("%s",buf);
		if(buf[0] == '#')break;

		func();
	}

	return 0;
}

Measured memory_bytes: 3832
#include<iostream>
#include<vector>
#include<string>
#include<functional>
#include<utility>
#include<assert.h>
using namespace std;
int sum[3][3] = {
  {0, 1, 2},
  {1, 1, 2},
  {2, 2, 2},
};

int prod[3][3] = {
  {0, 0, 0},
  {0, 1, 1},
  {0, 1, 2},
};

int neg[3] = {2,1,0};

int main(int argc, char *argv[])
{
  for(;;) {
    string str;
    getline(cin, str);
    if(str[0] == '.') break;
    int cnt = 0;
    for(int p = 0; p < 3; p++) {
      for(int q = 0; q < 3; q++) {
        for(int r = 0; r < 3; r++) {
          int sp = 0;
          function<int()> parse = [&str, &sp, p, q, r, &parse](){
            char c = str[sp++];
            if(c=='(') {
              int l = parse();
              char op = str[sp++];
              int r = parse();
              sp++;  // ')'
              if(op == '+') {
                return sum[l][r];
              } else if(op=='*'){
                return prod[l][r];
              } else {
                assert(false);
                return -1;
              }
            } else if(c == '-') {
              return neg[parse()];
            } else if(c == 'P') {
              return p;
            } else if(c == 'Q') {
              return q;
            } else if(c == 'R') {
              return r;
            } else if(c == '0') {
              return 0;
            } else if(c == '1') {
              return 1;
            } else if(c == '2') {
              return 2;
            } else {
              assert(false);
            }
          };
          if(parse()==2) cnt++;
        }
      }
    }
    cout << cnt << endl;
  }
}

Measured memory_bytes: 3140
import java.util.*;
import java.io.*;
import java.math.*;
 
public class Main {
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        HashMap<String,Integer> map = new HashMap<String,Integer>();
        ArrayList<String> ans = new ArrayList<String>();
        int n = sc.nextInt();
        for(int i = 0; i < n; i++){
            String s = sc.next();
            if(map.containsKey(s)){
                
                map.put(s,map.get(s)+1);
            }else{
                map.put(s,1);
            }
        }
        
        List<Map.Entry<String, Integer>> list_entries = new ArrayList<Map.Entry<String, Integer>>(map.entrySet());
        Collections.sort(list_entries, new Comparator<Map.Entry<String, Integer>>() {
            public int compare(Map.Entry<String, Integer> obj1, Map.Entry<String, Integer> obj2)
            {
                return obj2.getValue().compareTo(obj1.getValue());
            }
        });
        int cnt = 0;
        int max = 0;
        for(Map.Entry<String, Integer> entry : list_entries) {
            if(cnt == 0){
                cnt++;
                max = entry.getValue();
                ans.add(entry.getKey());
            }else if(max == entry.getValue()){
                cnt++;
                ans.add(entry.getKey());
            }
        }
        Collections.sort(ans);
        for(String s : ans){
            System.out.println(s);
        }
    }
}

Measured memory_bytes: 82196
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.InputMismatchException;
import java.io.IOException;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        FastReader in = new FastReader(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        ADuplexPrinting solver = new ADuplexPrinting();
        solver.solve(1, in, out);
        out.close();
    }

    static class ADuplexPrinting {
        public void solve(int testNumber, FastReader s, PrintWriter out) {
            int n = s.nextInt();
            out.println((n + 1) / 2);
        }

    }

    static class FastReader {
        private InputStream stream;
        private byte[] buf = new byte[1024];
        private int curChar;
        private int numChars;
        private FastReader.SpaceCharFilter filter;

        public FastReader(InputStream stream) {
            this.stream = stream;
        }

        public int read() {
            if (numChars == -1) {
                throw new InputMismatchException();
            }
            if (curChar >= numChars) {
                curChar = 0;
                try {
                    numChars = stream.read(buf);
                } catch (IOException e) {
                    throw new InputMismatchException();
                }
                if (numChars <= 0) {
                    return -1;
                }
            }
            return buf[curChar++];
        }

        public int nextInt() {
            int c = read();
            while (isSpaceChar(c)) {
                c = read();
            }
            int sgn = 1;
            if (c == '-') {
                sgn = -1;
                c = read();
            }
            int res = 0;
            do {
                if (c < '0' || c > '9') {
                    throw new InputMismatchException();
                }
                res *= 10;
                res += c - '0';
                c = read();
            } while (!isSpaceChar(c));
            return res * sgn;
        }

        public boolean isSpaceChar(int c) {
            if (filter != null) {
                return filter.isSpaceChar(c);
            }
            return isWhitespace(c);
        }

        public static boolean isWhitespace(int c) {
            return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
        }

        public interface SpaceCharFilter {
            public boolean isSpaceChar(int ch);

        }

    }
}



Measured memory_bytes: 21332
#!/usr/local/bin python
# -*- coding: utf-8 -*-
#
# ~/PycharmProjects/atcoder/B-Digits.py
#
# 1<= n <= 10**9
# 2<= k <= 10
#

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

digits = int(1)

for digit in range(1, 30):  # 2**29 < 10**9 < 2**<30 なので最高でも30桁
    if k ** digit <= n:
        digits = digits + 1
    else:
        break

print(digits)


Measured memory_bytes: 2940
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Scanner;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 *
 * @author Eric
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        Scanner in = new Scanner(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        BResale solver = new BResale();
        solver.solve(1, in, out);
        out.close();
    }

    static class BResale {
        public void solve(int testNumber, Scanner in, PrintWriter out) {
            int n = in.nextInt();
            int[] v = new int[n];
            int[] c = new int[n];
            int[] diff = new int[n];
            for (int i = 0; i < n; i++)
                v[i] = in.nextInt();
            for (int i = 0; i < n; i++)
                c[i] = in.nextInt();

            int res = 0;
            for (int i = 0; i < n; i++) {
                diff[i] = v[i] - c[i];
                if (diff[i] > 0)
                    res += diff[i];
            }
            out.println(res);
        }

    }
}



Measured memory_bytes: 24020
import bisect
import cmath
import heapq
import itertools
import math
import operator
import os
import re
import string
import sys
from collections import Counter, deque, defaultdict
from copy import deepcopy
from decimal import Decimal
from fractions import gcd
from functools import lru_cache, reduce
from operator import itemgetter, mul, add, xor

import numpy as np

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7
# MOD = 998244353


N, M, C = list(map(int, sys.stdin.buffer.readline().split()))
B = list(map(int, sys.stdin.buffer.readline().split()))
A = [list(map(int, sys.stdin.buffer.readline().split())) for _ in range(N)]

B = np.array(B, dtype=int)
A = np.array(A, dtype=int)

# ok = (A * B).sum(axis=1) + C > 0
ok = np.dot(A, B) + C > 0
print(ok.sum())


Measured memory_bytes: 13688
#include <bits/stdc++.h>
using namespace std;
 
int main(void)
{
	int d;
    cin >> d;
    if(d==25) cout << "Christmas";
    else if(d==24) cout << "Christmas Eve";
    else if(d==23) cout << "Christmas Eve Eve";
    else if(d==22) cout << "Christmas Eve Eve Eve";
}




Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<queue>
using namespace std;
typedef long long ll;
#define rep(i,n) for(ll i=0;i<n;++i)
#define rep1(i,n) for(ll i=1;i<=n;++i)
class Node{
public:
  vector<int> edge;
  int num;
  int no;
  bool ok;
  void new1(){
    num=edge.size();
    ok=false;
  }
};
class Edge{
public:
  int s;
  int t;
};
Node node[55];
bool judge(Edge const& edge,int const& n){
  rep1(i,n){
    node[i].new1();
    node[i].no=i;
  }
  queue<Node> que;
  que.push(node[1]);
  int s=edge.s;
  int t=edge.t;
  node[1].ok=true;
  while(!que.empty()){
    Node buf=que.front();
    que.pop();
    int k=buf.num;
    rep(i,k){
      if(buf.no==s&&buf.edge[i]==t)continue;
      else if(buf.no==t&&buf.edge[i]==s)continue;
      else {
	if(!node[buf.edge[i]].ok){
	  que.push(node[buf.edge[i]]);
	  node[buf.edge[i]].ok=true;
	}
      }
    }
  }
  int sum=0;
  rep1(i,n){
    if(!node[i].ok){
      sum++;
      //      cout<<edge.s<<" "<<edge.t<<endl;
      //      cout<<i<<endl;
    }
  }
  return sum>0;
}
int main(){
  int n,m;cin>>n>>m;
  vector<Edge> edge(m);
  rep(i,m){
    int a,b;cin>>a>>b;
    edge[i].s=a;edge[i].t=b;
    node[a].edge.push_back(b);
    node[b].edge.push_back(a);
  }
  int bridge=0;
  rep(i,m){
    if(judge(edge[i],n))bridge++;
  }
  cout<<bridge<<endl;
  return 0;
}


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

#define IOS ios_base::sync_with_stdio(false);cin.tie(NULL);
#define inN(A) cin>>n;for(i=0;i<n;++i)cin>>A[i];
#define rep(i,a,b) for(i=a;i<b;++i)
#define repn for(i=0;i<n;++i)
#define ll long long
#define pii pair<int,int>
#define pb push_back
#define sd second
#define ft first
#define vi vector<int>
#define vpii vector<pair<int,int> >
#define abs(a) (a>=0?a:-a)
#define TC //int T;cin>>T;while(T--)
#define n_max 200001
#define mod 1000000007

int cmp(int a,int b){return abs(a)>abs(b);}

int main() {
    int a,b,p,i,j,k,l,n,A[n_max];
    TC
    {
    	cin>>n>>k;
    	rep(i,0,n)cin>>A[i];
    	sort(A,A+n,cmp);
    	ll ans=1;j=0;
    	for(i=0;i<k;++i)if(A[i]<0)j++;
    	if(j%2)
    	{
    		int l1,l2,l3,l4;
    		for(l1=k-1;l1>=0;--l1)if(A[l1]<0)break;
    		for(l2=k;l2<n;++l2)if(A[l2]>=0)break;
    		for(l3=k-1;l3>=0;--l3)if(A[l3]>=0)break;
    		for(l4=k;l4<n;++l4)if(A[l4]<0)break;
    		if(l2<n&&l3>=0&&l4<n)
    		{
    			if((ll)A[l2]*A[l3]>(ll)A[l1]*A[l4])swap(A[l1],A[l2]);
    			else swap(A[l3],A[l4]);
    		}
    		else if(l2<n)swap(A[l1],A[l2]);
    		else if(l3>=0&&l4<n)swap(A[l3],A[l4]);
    		else reverse(A,A+n);
    	}
    	rep(i,0,k)ans=ans*A[i]%mod;
    	cout<<(ans+mod)%mod;
    }
}



Measured memory_bytes: 4312
#include <stdio.h>
int main() {
	int x,a,b;
	scanf("%d %d %d",&x,&a,&b);
	
	int ax;
	
	if ( x > a )
	{
		ax = x - a;
	}
	else if ( a > x )
	{
		ax = a - x;
	}
	
	int bx;
	
	if (x > b)
	{
		bx = x - b;
	}
	else if (b > x)
	{
		bx = b - x;
	}
	
	if (ax < bx)
	{
		printf("A\n");
	}
	else if (ax > bx)
	{
		printf("B\n");
	}
	return 0;
}

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

int main() {
  	int K;
    string S;
    cin >> K; 
    cin >> S;
  	int k = size(S);	
  if(k<=K) {cout << S << endl;}
  else{
	for(int i = 0;i < K ;i++){
      cout << S[i] ; 
    }
    cout << "..." << endl;
  }
  return 0;
}

Measured memory_bytes: 3624
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
#define rep(i,m,n) for(int i=m;i<n;i++)
ll mod=1e9+7;

int main(){
  int n;
  cin>>n;
  ll dp[n+1][64];
  rep(i,0,n+1){
    rep(j,0,64){
      dp[i][j]=0;
    }
  }
  dp[0][63]=1;
  rep(i,0,n){
    rep(j,0,64){
      int p=j%4;
      int q=j/4%4;
      int r=j/16%4;
      if(p==0 && q==1 && r==2) continue;
      if(p==1 && q==0 && r==2) continue;
      if(p==0 && q==2 && r==1) continue;
      rep(k,0,4){
        if(p==0 && q==1 && k==2) continue;
        if(q==0 && r==1 && k==2) continue;
        if(q==1 && r==0 && k==2) continue;
        if(q==0 && r==2 && k==1) continue;
        if(p==0 && r==1 && k==2) continue;
        dp[i+1][q+r*4+k*16]+=dp[i][j];
        dp[i+1][q+r*4+k*16]%=mod;
      }
    }
  }
  ll ans=0;
  rep(i,0,64){
    ans+=dp[n][i];
    ans%=mod;
  }
  cout<<ans<<endl;
}

Measured memory_bytes: 256
// Date: 2020-03-16

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

typedef long long LL;
typedef long double LD;
typedef vector<int> VI;
typedef pair<LL, LL> pll;
typedef pair<int, int> pii;
#define FIO ios::sync_with_stdio(false);cin.tie(0)
#define rep(i, a, b) for(int i = int(a); i <= int(b); ++i)
#define per(i, b, a) for(int i = int(b); i >= int(a); --i)
#define mem(x, y) memset(x, y, sizeof(x))
#define all(x) (x).begin(),(x).end()
#define mk make_pair
#define pb push_back
#define fi first
#define se second
const LL INF = 1e18;
const LL mod = 1e9 + 7;
const int inf = 0x3f3f3f3f;
const int N = 20;
template <typename T> void chkmax(T &x, T y) { x = max(x, y); }
template <typename T> void chkmin(T &x, T y) { x = min(x, y); }
LL qpow(LL x, LL y, LL MOD) {LL a=1; while(y){ if(y&1) a=a*x%MOD; x=x*x%MOD; y>>=1; } return a;}

int n, a[N][N];
VI g[1<<17];
LL val[1<<17], f[1<<17];

int main() {
    FIO;
    cin >> n;
    rep(i, 0, n-1) rep(j, 0, n-1) cin >> a[i][j];
    int lim = (1 << n) - 1;
    rep(i, 0, lim) rep(j, 0, n-1) if(i >> j & 1) g[i].pb(j);
    rep(i, 0, lim) {
        rep(j, 0, g[i].size()-1) rep(k, j+1, g[i].size()-1) val[i] += a[g[i][j]][g[i][k]];
    }
    rep(i, 0, lim) {
        for(int s = i; s; s = ((s-1) & i)) chkmax(f[i], f[s] + val[i ^ s]);
        chkmax(f[i], val[i]);
    }
    cout << f[lim] << endl;

    return 0;
}

Measured memory_bytes: 8192
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <iomanip>
#include <cmath>
#include <map>
#include <ctype.h>
using namespace std;

typedef long long ll;

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

int main() {
  string str, s;
  for (int i = 0; i < 3; ++i) {
    cin >> str;
    s.push_back(str[i]);
  }
  cout << s << endl;
  return 0;
}


Measured memory_bytes: 256
#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
using namespace std;
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define REP(i, n) FOR(i, 0, n)

int main() {
  int n;
  cin >> n;
  if (n == 1) {
    cout << "Hello World" << endl;
  } else {
    int a, b;
    cin >> a >> b;
    cout << a + b << endl;
  }
}


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

#define rep(n) for(int i=0;i<n;i++)
#define repp(j, n) for(int j=0;j<n;j++)
#define reppp(i, m, n) for(int i=m;i<n;i++)
#define all(c) c.begin(), c.end()
#define rall(c) c.rbegin(), c.rend()
#define debug(x) cerr << #x << ": " << x << endl

using namespace std;

typedef long long ll;
typedef pair<ll, ll> Pll;
typedef pair<int, int> Pii;

class UnionFind {
    public:
    ll n;
    vector<ll> par;

    UnionFind(ll n) {
        rep(n) {
            par.push_back(ll(i));
        }
    }

    ll find(ll x) {
        return ((par[x] == x) ? x : par[x]=find(par[x]));
    }

    void unite(ll x, ll y) {
        x = find(x);
        y = find(y);

        if(x == y) return;

        par[y] = x;
        return;
    }

    bool is_same(ll x, ll y) {
        return find(x) == find(y);
    }
};

int main() {
    ll n,q,node;
    char c;
    cin >> n >> q;
    while(n || q){
        vector<ll> parent(n+1, 1), children[n+1];
        reppp(i, 2, n+1){
            cin >> node;
            parent[i] = node;
            children[node].push_back(i);
        }

        vector<Pll> query;
        vector<bool> marked(n+1, false);
        rep(q){
            cin >> c >> node;
            if(c == 'Q'){
                query.emplace_back(1, node);
            }else{
                if(marked[node]) continue;
                query.emplace_back(0, node);
                marked[node] = true;
            }
        }
        q = (ll)query.size();

        UnionFind uf = UnionFind(n+1);
        reppp(i, 2, n+1){
            if(marked[i]) continue;
            uf.unite(parent[i], i);
        }
        
        ll ans = 0;
        for(int i=q-1;i>=0;--i){
            if(query[i].first){
                ans += uf.find(query[i].second);
            }else{
                uf.unite(parent[query[i].second], query[i].second);
            }
        }
        cout << ans << endl;
        cin >> n >> q;
    }
}


Measured memory_bytes: 13360
#include<stdio.h>
#include<math.h>
#include <stdlib.h>
#include<string.h>
#include<limits.h>
#include<time.h>
#include<ctype.h>

int  main()
{
	char num[100]={'\0'};
	char *tp;
	double stack[220]={0};
	int i,j;
	
	while(fgets(num,sizeof(num),stdin)!=NULL)
	{
		i=0;
		tp=strtok(num," ");
		
		stack[i]=atof(tp);
		i++;
		
		while(tp!=NULL)
		{
			tp=strtok(NULL," ");
			if(tp!=NULL)
			{
				if(tp[0]=='+')
				{
					stack[i-2]+=stack[i-1];
					stack[i-1]=0;
					i--;
				}
				else if(tp[0]=='-' && (tp[1]<'0' || tp[1]>'9'))
				{
					stack[i-2]-=stack[i-1];
					stack[i-1]=0;
					i--;
				}
				else if(tp[0]=='*')
				{
					stack[i-2]*=stack[i-1];
					stack[i-1]=0;
					i--;
				}
				else if(tp[0]=='/')
				{
					if(stack[i-1]!=0)
					{
						stack[i-2]/=stack[i-1];
						stack[i-1]=0;
						i--;
					}
					else 
					{
						stack[i-2]=0;
						i--;
					}
				}
				else 
				{
					stack[i]=atof(tp);
					i++;
				}
			}
		}
		printf("%f\n",stack[0]);
	}
return 0;
}

Measured memory_bytes: 576
N = int(input())
A = [int(i) for i in input().split()]
cntswap = 0


for i in range(1,N):
    for j in range(i, 0, -1):
        if A[j-1] > A[j]:
            A[j-1:j+1] = [A[j], A[j-1]]
            cntswap += 1

for i in range(0, N-1):
    print(A[i], '', end='')
print(A[N-1])
print(cntswap)


Measured memory_bytes: 5628
/** 
 * THIS IS MOOONI'S CODE !
 * HACK IT IF YOU CAN !
**/
#include <bits/stdc++.h>

using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  vector<int> v = {1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51};
  int n;
  cin >> n;
  cout << v[n - 1] << '\n';
  return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <set>
#include <algorithm>
#include <cctype>
#include <cmath>
#include <queue>
#include <map>
#include <numeric>
#include <unordered_map>
#include <iomanip>
#include <functional>
#include <bitset>
#include <complex>
#include <stack>



#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define repi(i,a,b) for(int i=int(a);i<int(b);i++)
#define all(x) (x).begin(),(x).end()

template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }

typedef long long ll;

using namespace std;


int main()
{
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n;cin>>n;
  int res=0;
  int sum=0;
  rep(i,n)
  {
    int x;
    cin>>x;
    res-=x*x;
    sum+=x;
  }
  cout<<(sum*sum+res)/2<<endl;

  return 0;

}


Measured memory_bytes: 256
def div(n):
    lower, upper = [], []
    i = 1
    while i * i <= n:
        if n % i == 0:
            lower.append(i)
            if i != n // i:
                upper.append(n // i)
        i += 1
    return lower + upper[::-1]

n = int(input())
ans = 0
for i in div(n):
    if i == 1:
        continue
    elif n // (i - 1) == n % (i - 1):
        ans += i - 1
print(ans)


Measured memory_bytes: 3344