akhauriyash/Code-Regression huggingface dataset:
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;
const int inf = 1 << 30;
const LL INF = 1LL << 60;

int n;
LL a, b;

LL Get_sqrt(LL x) 
{
	LL l = 1, r = 1e9 + 10;
	LL ans = 1;
	while(l <= r) {
		LL mid = (l + r) >> 1;
		if(mid * mid <= x) ans = mid, l = mid + 1; 
		else r = mid - 1;
	}
	return ans;
}

int main()
{
	scanf("%d", &n);
	for(int i = 1; i <= n; i++) {
		scanf("%lld%lld", &a, &b);
		LL x = Get_sqrt(a * b - 1LL);
		LL ans;
		if(x * (x + 1LL) <= a * b - 1LL) {
			ans = x * 2LL;
			if(x >= min(a, b)) ans--;
		}
		else {
			ans = 2LL * x - 1LL;
			if(x >= min(a, b)) ans--;
		}
		printf("%lld\n", ans);
	}
	return 0;
}

Measured memory_bytes: 128
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#include <math.h>
#include <limits.h>
#define swap(type,a,b) do{type t=a;a=b;b=t;}while(0);
#define MAX(a,b) (((a)>(b))?(a):(b))
#define MIN(a,b) (((a)<(b))?(a):(b))
#define ll long long
#define INF 100000000
#define MOD 1000000007
#define SIZE 100005
#define FOR(i,a,n) for(i=(a);i<(n);i++)
int comp(const void* a,const void* b){
	return *(int*)a-*(int*)b;
}
int used[1000001];
int main(void)
{
	int n,m,k,i,j;
	scanf("%d%d%d",&n,&m,&k);
	FOR(i,0,n+1){
		FOR(j,0,m+1){
			used[i*m+j*n-i*j*2]=1;
		}
	}
	printf("%s\n",used[k]?"Yes":"No");
	return 0;
}


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

using namespace std; 

#define pb push_back
#define ppb pop_back
#define pf push_front
#define ppf pop_front
#define mmp make_pair
#define st first
#define nd second
#define rd third
#define ll long long
#define pii pair <int, int>
#define tri pair <pii, int>
#define itr pair <int, pii>
#define PQ priority_queue
#define all(v) (v).begin(), (v).end()
#define REP(i, n) for (int (i) = 0; (i) < (int)(n); i++)
#define FOR(i, a, n) for (int (i) = (a); (i) < (int)(n); i++)
#define FORN(i, a, n) for (int (i) = (a); (i) > (int)(n); i--)
#define Rep(i, n) for (int (i) = 0; (i) <= (int)(n); i++)
#define For(i, a, n) for (int (i) = (a); (i) <= (int)(n); i++)
#define Forn(i, a, n) for (int (i) = (a); (i) >= (int)(n); i--)
#define rep(i, n) for (int (i) = 1; (i) <= (int)(n); i++)
#define EACH(it, a) for (__typeof(a.begin()) it = a.begin(); it != a.end(); it++)

#define DEBUG(x) cout << #x << " = " << (x) << endl; 
#define PR(a, n) {cout << #a << " = "; FOR(_, 1, n) cout << a[_] << ' '; puts(""); }
#define PRO(a, n) { cout << #a << " = "; REP(_, n) cout << a[_] << ' '; puts(""); }
#define pi 3.1415926535897932384626433832795028841971
//#define LOCAL

const int INF = 1e9; 
const int N = 1005; 
const int dx[] = {-1, 0, 1, 0}; 
const int dy[] = {0, 1, 0, -1}; 

inline ll read()
{
	ll x = 0; int f = 1, c = getchar(); 
	for (; !isdigit(c); c = getchar()) if (c == '-') f = -f; 
	for (; isdigit(c); c = getchar()) x = (x << 3) + (x << 1) + (c ^ 48); 
	return x * f; 
}

int n; 
vector <int> p; 

int main()
{
	#ifdef LOCAL
		freopen("input.txt", "r", stdin); 
		freopen("output.txt", "w", stdout); 
	#endif
	
	n = read(); 
	REP(i, n)
	{
		int x = read(); 
		p.pb(x); 
	}
	
	int ans = 0; 
	rep(i, n - 2)
	{
		if (p[i - 1] <= p[i] && p[i] <= p[i + 1]) ans++; 
		else if (p[i - 1] >= p[i] && p[i] >= p[i + 1]) ans++; 
	}
	
	printf("%d\n", ans); 
	
	return 0; 
}


Measured memory_bytes: 256
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <stdio.h>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
#define rep(i,a,n) for(ll i =(a);i<(n);++i)
#define urep(i,a,n) for(ll i = (a);i>=(n);--i)
#define all(x) (x).begin(),(x).end()
#define INF 1e18
const int mod = 1e9 + 7;
typedef long long ll;
using namespace std;
ll dx[4] = { 1,-1,0,0 };
ll dy[4] = { 0,0,1,-1 };
ll N,M,X,Y,A,B,C,D,Q,K,R,W,H,P,L,G;
ll ans;
string S,T;
ll y[101010];
ll a[201010];
ll k[101010];
ll b[201010];
ll d[101010];
ll t[101010];
ll p[101010];
ll n[101010];
ll l[101010];
ll r[101010];
ll v[101010];
ll s[101010];
ll x[101010];
ll gcd(ll a, ll b) {
	if (b == 0)return a;
	else return gcd(b, a%b);
}
ll lcm(ll a,ll b){
    return a/gcd(a,b)*b;
}
struct Edge{
	ll to,cost;
	 Edge(ll to, ll cost) : to(to), cost(cost) {}
};
typedef vector<vector<Edge> > AdjList;
AdjList graph;
vector<ll> dist;

struct UnionFind {
    vector<ll> par; // par[i]:iの親の番号　(例) par[3] = 2 : 3の親が2
	vector<ll> size;
    UnionFind(ll N) : par(N),size(N) { //最初は全てが根であるとして初期化
        for(ll i = 0; i < N; i++) par[i] = i;
		for(ll i = 0; i < N; i++) size[i] = 1;
    }

    ll root(ll x) { // データxが属する木の根を再帰で得る：root(x) = {xの木の根}
        if (par[x] == x) return x;
        return par[x] = root(par[x]);
    }
	ll GetSize(ll x){
		return size[root(x)];
	}

    void unite(ll x, ll y) { // xとyの木を併合
        ll rx = root(x); //xの根をrx
        ll ry = root(y); //yの根をry
        if (rx == ry) return; //xとyの根が同じ(=同じ木にある)時はそのまま
        par[rx] = ry; //xとyの根が同じでない(=同じ木にない)時：xの根rxをyの根ryにつける
		size[ry]+=size[rx];

    }

    bool same(ll x, ll y) { // 2つのデータx, yが属する木が同じならtrueを返す
        ll rx = root(x);
        ll ry = root(y);
        return rx == ry;
    }
};

int main() {
    cin>>N>>K;
    ll num=0;
    rep(i,1,N-1){
        num+=i;
    }
    if(K>num){
        cout<<-1<<endl;
    }else{
        cout<<((N*(N-1))/2)-K<<endl;
        ll count = ((N*(N-1))/2)-K;
        rep(i,2,N+1){
            cout<<1<<" "<<i<<endl;
            count--;
        }
        rep(i,2,N){
            rep(j,i+1,N+1){
                if(count==0)break;
                cout<<i<<" "<<j<<endl;
                count--;
            }
        }
    }

    return 0;
}


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

int main(){
  string S;
  cin >> S;
  bool b1 = (S.at(0) == 'A'), b2 = false, b3 = true;
  
  vector<char> small(28);
  small = {'A','C','q','w','e','r','t','y','u','i','o','p','a','s','d','f','g','h','j','k','l','z','x','c','v','b','n','m'};
  for(int i = 0; i < S.size(); i++){
    int count = 0;
    for(int j = 0; j < 28; j++){
      if(S.at(i) == small.at(j)) break;
      else if(j == 27) count++;
    }
    if(count > 0){
      b3 = false;
      break;
    }
  }
  
  int counter = 0;
  for(int i = 2; i < S.size() - 1; i++){
    if(S.at(i) == 'C') counter++;
  }
  if(counter == 1) b2 = true;
  
 
  
  if(b1 && b2 && b3) cout << "AC" << endl;
  else cout << "WA" << endl;
}
  
      
      
      
    
  
  

Measured memory_bytes: 3628
def solve(items, W):
    dp = [[0]*(W+1) for _ in range(len(items)+1)]

    for i, g in enumerate(items, 1):
        for w in range(W+1):
            if w >= g[0]:
                dp[i][w] = max(dp[i-1][w], dp[i-1][w-g[0]]+g[1])
            else:
                dp[i][w] = dp[i-1][w]

    return dp[len(items)][W]


if __name__ == "__main__":
    N, W = map(int, input().split())
    items = [list(map(int, input().split())) for _ in range(N)]
    print(solve(items, W))


Measured memory_bytes: 146864
import math
A, B, H, M = map(int, input().split())
time = 60 * H + M
angle = 5.5 * time - (5.5 * time // 360 * 360)
angle = min(angle, 360 - angle)
cos_a = math.cos(math.radians(angle))
c2 = A**2 + B**2 - 2*A*B*cos_a
print(math.sqrt(c2))

Measured memory_bytes: 9388
#include<stdio.h>

int main(void)
{
  int a, b, c;
  int i;
  int count=0;

  scanf("%d %d %d", &a, &b, &c);

  for(i=a;i<=b;i++)
    {
      if(c%i==0)
	{
	  count++;
	}
    }
  
  printf("%d\n", count);

  return 0;
}

Measured memory_bytes: 596
import Data.List
import Control.Monad
import Control.Applicative

solve' :: String -> String -> String
solve' a b =
	let ns = map read $ words a :: [Int]
	    ms = map read $ words b :: [Int]
	    h  = length $ filter id $ zipWith (==) ns ms
	    m  = (length $ filter (\c -> c `elem` ns) ms) - h
	in (show h) ++ " " ++ (show m)

solve :: [String] -> [String]
solve [] = []
solve (a:b:cs) = (solve' a b) : (solve cs)
	
main :: IO ()
main = do
	ls <- fmap lines getContents
	mapM_ putStrLn $ solve ls

Measured memory_bytes: 4112
#include<iostream>
using namespace std;
int main(){
  int a,b;
  char map[300][300];
  while(1){
    cin>>a>>b;
    if(a==0&&b==0){
      break;
    }
    for(int i=1;i<=a;i++){
      for(int j=1;j<=b;j++){
	if(j%2==0&&i%2!=0||j%2!=0&&i%2==0){
	  map[j][i]='.';
	}else{
	  map[j][i]='#';
	}
	cout<<map[j][i];
      }
      cout<<endl;
    }
    cout<<endl;
  }
  return(0);
}

Measured memory_bytes: 3068
#include <bits/stdc++.h>
#include <ext/rope>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("unroll-loops")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
//#define int long long
#define pb push_back
#define x first
#define y second
#define mk(a,b) make_pair(a,b)
#define rr return 0
#define sqr(a) ((a)*(a))
#define all(a) (a).begin(), (a).end()
#define sz(a) (int)(a).size()

using namespace std;
using namespace __gnu_cxx;
using namespace __gnu_pbds;

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

template<class value, class cmp = less<value> >
using ordered_set = tree<value, null_type, cmp, rb_tree_tag, tree_order_statistics_node_update>;
template<class value, class cmp = less_equal<value> >
using ordered_multiset = tree<value, null_type, cmp, rb_tree_tag, tree_order_statistics_node_update>;
template<class key, class value, class cmp = less<key> >
using ordered_map = tree<key, value, cmp, rb_tree_tag, tree_order_statistics_node_update>;

/// find_by_order()
/// order_of_key()
mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
inline int randll(int l = INT_MIN, int r = INT_MAX) {
    return uniform_int_distribution<int>(l, r)(rng);
}
const int INF = 1e9, MOD = 1e9 + 7; /// think
const ll LINF = 1e18;


const int dx[] = {0, 0, 1, -1}, dy[] = {1, -1, 0, 0};
inline bool inside (int x, int y, int n, int m) {
    return 0 <= x && 0 <= y && x < n && y < m;
}

template<class T> bool umin (T &a, T b) {return a > b ? (a = b, true) : false; }
template<class T> bool umax (T &a, T b) {return a < b ? (a = b, true) : false; }

const int N = 1e7 + 11;
int mn[N] = {};
inline void precalc () {
    for (int i = 2; i < N; i++) {
        if (!mn[i]) {
            for (int j = i; j < N; j += i) {
                if (!mn[j]) mn[j] = i;
            }
        }
    }
}
main()
{
    ios::sync_with_stdio(0);
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    precalc();
    int n;
    cin >> n;
    ll ans = 1;
    for (int i = 2; i <= n; i++) {
        int cnt = 1;
        int x = i;
        while (x > 1) {
            int y = mn[x], c = 0;
            while (x % y == 0) {
                x /= y;
                ++c;
            }
            cnt *= c + 1;
        }
        ans += cnt * 1ll * i;
    }
    cout << ans << '\n';
}


Measured memory_bytes: 42704
import Foundation
// Decimal型の有効桁数は38桁
let line = readLine()!.components(separatedBy: " ").map { Int($0)! }
let X = line[0]
let Y = line[1]

for kame in 0...X {
    let turu = X - kame
    if (kame * 4 + turu * 2) == Y {
        print("Yes")
        exit(EXIT_SUCCESS)
    }
}
print("No")


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

// #include <ext/pb_ds/assoc_container.hpp> 
// #include <ext/pb_ds/tree_policy.hpp> 
// using namespace __gnu_pbds; 

#define mod 1000000007
#define pb push_back
#define S second
#define F first
#define INF 1e18
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update> 

#define deb(x) cerr << "\n" \
                    << #x << "=" << x << "\n";
#define deb2(x, y) cerr << "\n" \
                        << #x << "=" << x << "\n" \
                        << #y << "=" << y << "\n";
#define w(x) \
  int x;     \
  cin >> x;  \
  while (x--)

const int N = 2001;
int dp[N];

int32_t main() {

  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  int n;
  cin >> n;
  dp[n] = 1;
  for(int i = n; i >= 3; --i) {
    for(int j = 3; j <= i; j++) 
      dp[i - j] = (dp[i - j] + dp[i]) % mod;
  }
  int ans = 0;
  for(int i = 3; i <= n; ++i)
    ans = (ans % mod + dp[i] % mod) % mod;
  cout << ans; 
  return 0;
}


Measured memory_bytes: 3628
#include<stdio.h>
#include<stdlib.h>
#define END 2100000000

typedef struct cell{
	int data;
	struct cell *left;
	struct cell *right;
}cell;

cell * makecell(int x){
	cell *new=malloc(sizeof(cell));
	new->data=x;
	new->left=NULL;
	new->right=NULL;
	return new;
}

int main(){
	int q,com,x;
	cell *new;
	cell *front=makecell(END);
	cell *p=front;
	
	scanf("%d",&q);
	
	for(int i=0;i<q;i++){
		
		scanf("%d",&com);
		
		if(com==0){
			scanf("%d",&x);
			new=makecell(x);
			if(front->data == END){/*要素なし*/
				front=new;
				new->right=p;
				p->left=new;
				p=new;
			}
			else {
				if(front==p){/*先頭に挿入*/
					front=new;
					new->right=p;
					p->left=new;
					p=new;
				}
				else {
					p->left->right=new;
					new->left=p->left;
					new->right=p;
					p->left=new;
					p=new;
				}
			}
		}
		
		if(com==1){
			scanf("%d",&x);
			if(x>0)for(int j=0;j<x;j++)p=p->right;
			else for(int j=0;j<(-x);j++)p=p->left;
		}
		
		if(com==2){
			if(front==p){/*先頭*/
				p->right->left=NULL;
				front=front->right;
				p=front;
			}
			else {
				p->left->right=p->right;
				p->right->left=p->left;
				p=p->right;
			}
		}
	}
	
	p=front;
	while(p!=NULL){
		if(p->data!=END)printf("%d\n",p->data);
		p=p->right;
	}
	
	return 0;
	
}


Measured memory_bytes: 17348
n=int(input())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
c=list(map(int,input().split()))
p=-1
ans=0
for i in range(n):
    ans+=b[a[i]-1]
    if p+1==a[i]:
        ans+=c[a[i]-2]
    p=a[i]
print(ans)

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

int main() {
    int N;
    long long x;
    cin >> N >> x;
    vector<long long> a(N);
    for (int i = 0; i < N; i++) {        
        cin >> a.at(i);
    }
    // 少ない数で満足できる子の順に並べる
    sort(a.begin(), a.end());
    int ret = 0;
    for (int i = 0; i < N; i++) {
        if (x-a.at(i) < 0) {break;}
        x -= a.at(i);
        ret++;
    }
    if (ret == N && x>0) {ret--;} // 全員に行き届いてお菓子が余ったら誰かに全てあげる（その子は不満になる）
    cout << ret << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define rep(i,n) for(int i = 0;(i) < (int)(n);i++)
using namespace std;
int main(){
    int n,m;
    cin >> n >> m;
    vector<vector<int>> work(m);
    rep(i,n){
        int a,b;
        cin >> a >> b;
        //期間内に金もらえるかチェック
        if(a > m) continue;
        //m-a日目に始めればm日後で金を受け取れる
        work[m-a].push_back(b);
    } 
    priority_queue<int> que;
    long long ans = 0;
    for(int i=m-1;i>=0;--i){
        for(int b : work[i]) {
            
            que.push(b);
        
        }
    
        if(!que.empty()){
            ans+=que.top();
            que.pop();
        }
    }
    cout << ans  << endl;

}

Measured memory_bytes: 5504
#include<bits/stdc++.h>
using namespace std;
#define all(a) (a).begin(),(a).end()
#define rall(a) (a).rbegin(),(a).rend()
#define rep(i,n) for(int i=0; i<(n); ++i)
#define per(i,n) for(int i=n-1;i>=0;++i)
#define rep1(i,n) for(int i=1; i<=n; ++i)
#define per1(i,n) for(int i=n; i>=1; ++i)
#define debug cout << "line : " << __LINE__ << " debug" << endl
#define Dcout(N) cout << setprecision(20) << N << endl
#define UNIQUE(v) v.erase( unique(v.begin(), v.end()), v.end() ) //被り削除
#define pb push_back
#define mp make_pair
#define F first
#define S second
#define INF 1e8
#define MOD 1000000007
typedef long long ll;

int n,m,q; 
vector<int> a,b,c,d;
int ans;

void dfs(vector<int> A){
    if(A.size()==n+1){
        // calc score
        int now = 0;
        rep(i,q){
            if(A[b[i]] - A[a[i]] == c[i]) now += d[i];
        }
        ans = max(ans,now);
        return;
    }

    A.push_back(A.back());
    while(A.back() <= m){
        dfs(A);
        A.back()++;
    }
}

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

      cin >> n >> m >> q;

      a = b = c = d = vector<int>(q);
      rep(i,q){
          cin >> a[i] >> b[i] >> c[i] >> d[i];
      }

      dfs(vector<int>(1,1));

      cout << ans << endl;

      return 0;
}


Measured memory_bytes: 3664
//#include <bits/stdc++.h>
#include <iostream>
#include <fstream>
#include <vector>
#include <string>
#include <cmath>
#include <algorithm>
#include <map>
#include <iomanip>
#include <stdlib.h>
#include <stdio.h>
#include <queue>
#include <deque>
#include <set>
#include <stack>
#include <time.h>
 
using namespace std;
 
typedef long long ll;
typedef long double ld;
typedef pair<int, int> Pii;
typedef pair<int, ll> Pil;
typedef pair<ll, ll> Pll;
typedef pair<ll, int> Pli;

#define fi first
#define se second
#define mp make_pair
 
const ll MOD = 1e9 + 7;
const ll MOD2 = 998244353;
const ll MOD3 = 1812447359;
const ll INF = 1ll << 60;
const double PI = 2 * asin(1);

void yes() {printf("yes\n");}
void no() {printf("no\n");}
void Yes() {printf("Yes\n");}
void No() {printf("No\n");}
void YES() {printf("YES\n");}
void NO() {printf("NO\n");}

int main(){
  string S; cin >> S;
  int N = S.length();

  if (N % 2 != 0 && S[0] == S[N - 1]){
    cout << "Second\n";
  }else if (N % 2 == 0 && S[0] != S[N - 1]){
    cout << "Second\n";
  }else{
    cout << "First\n";
  }

  return 0;
}


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

double t[300],v[300],mn[20010][2],sp[20010][2],sum=0,ans=0;
int main(){
	cout.precision(10);
	int i,j,n,k=1,l=1;
	cin >> n;
	t[0] = 0;
	v[0] = 0;
	for(i=1;i<=n;i++){
		cin >> t[i] ;
		sum += t[i];
		t[i] += t[i-1];
	}
	t[n+1] = sum;
	for(i=1;i<=n;i++){
		cin >> v[i];
	}
	v[n+1] = 0;
	
	for(i=0;i<20010;i++){
		mn[i][0] = 1000000;
		mn[i][1] = 1000000;
	}
	
	for(i=0;i<=sum;i++){
		if(i>t[k]){
			k++;
		}
		if(i>=t[l]){
			l++;
		}
		for(j=1;j<=n+1;j++){
			if(t[j-1]>=i) mn[i][0] = min(mn[i][0],v[j]+t[j-1]-i);
			if(t[j-1]>i) mn[i][1] = min(mn[i][1],v[j]+t[j-1]-i-0.5);
		}
		mn[i][0] = min(mn[i][0],v[k]);
		mn[i][1] = min(mn[i][1],v[l]);
	}
		
	mn[(int)sum][0] = 0;
	sp[0][0] = 0;
	sp[0][1] = min(mn[0][1],0.5);
	for(i=0;i<sum;i++){
		sp[i+1][0] = min(sp[i][1]+0.5,mn[i+1][0]);
		sp[i+1][1] = min(sp[i+1][0]+0.5,mn[i+1][1]);
	}
	
	for(i=0;i<sum;i++){
		ans += (sp[i][0]+sp[i][1])/4;
		ans += (sp[i][1]+sp[i+1][0])/4;
	}
	
	cout << ans << endl;
}


Measured memory_bytes: 896
import java.util.Scanner;

class Main {
    public static void main(String[] args) {
        String cmd;
        char c;
        int[] label;
        int temp;
        Scanner sc = new Scanner(System.in);
        label = new int[6];
        for (int i = 0; i < 6; i++)
            label[i] = sc.nextInt();
        cmd = sc.next();

        for (int i = 0; i < cmd.length(); i++) {
            c = cmd.charAt(i);
            switch (c) {
            case 'N':
                temp = label[0];
                label[0] = label[1];
                label[1] = label[5];
                label[5] = label[4];
                label[4] = temp;
                break;
            case 'S':
                temp = label[0];
                label[0] = label[4];
                label[4] = label[5];
                label[5] = label[1];
                label[1] = temp;
                break;
            case 'W':
                temp = label[0];
                label[0] = label[2];
                label[2] = label[5];
                label[5] = label[3];
                label[3] = temp;
                break;
            case 'E':
                temp = label[0];
                label[0] = label[3];
                label[3] = label[5];
                label[5] = label[2];
                label[2] = temp;
                break;
            }
        }
        System.out.println(label[0]);
    }
}


Measured memory_bytes: 26376
#include <bits/stdc++.h>
#define REP(i,s,e) for(int i=(s); i<(e);i++)
#define rep(i,n) REP(i,0,n)
#define rep1(i,n) REP(i,1,n)
#define repe(i,n) for(auto &&i:n)
#define all(v) (v).begin(),(v).end()
#define decimal fixed<<setprecision(20)
#define fastcin() cin.tie(0);ios::sync_with_stdio(false)
using namespace std;
using LL = long long;
using Graph = vector<vector<int>>;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
const int INF = 1e9;
const LL LLINF = 1e16;

struct p{
    int a, b, c;
};

int main(){
    fastcin();

    int n, k;
    cin >> n >> k;
    if(2*k > n+1){
        cout << -1 << endl;
        return 0;
    }
    vector<p> ans;
    int tg = 2*n-1-(n-1)/2;
    int c = 2*n;
    for(int a=(n-1)/2-1; a>=0; a--){
        int b = tg-a;
        // cout << a << " " << b << endl;
        ans.push_back((p){a, b, c});
        tg++; c++;
    }
    ans.push_back((p){n-1, n, c}); c++;
    if(n%2==0){
        ans.push_back((p){n-2, n+1, c}); c++;
    }
    tg++;
    for(int a=(n-1)-1-(n+1)%2; a>=(n-1)/2; a--){
        int b = tg-a;
        // cout << a << " " << b << endl;
        ans.push_back((p){a, b, c});
        tg++; c++;
    }
    repe(i, ans){
        cout << i.a+k << " " << i.b+k << " " << i.c+k << endl;
    }
}

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

using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin >> n;
    vector<int> a(n), b(n), c(n-1);
    for (int& x : a) {
        cin >> x;
        --x;
    }
    for (int& x : b) {
        cin >> x;
    }
    for (int& x : c) {
        cin >> x;
    }
    int satis = 0;
    for (int i = 0; i < n; ++i) {
        satis += b[a[i]];
        if (i + 1 < n && a[i+1] == a[i]+1) {
            satis += c[a[i]];
        }
    }
    cout << satis << endl;
    return 0;
}


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

using namespace std;

#define ll long long
#define mp make_pair

int n, m;

vector <int> l[200000];
int bio[200000];
deque <int> Q; 

int dfs2 (int x) {
	bio[x] = 1;
	Q.push_front(x);
	for (int i=0; i<l[x].size(); i++) {
		if (bio[l[x][i]] == 0) {
			return dfs2(l[x][i]);
		}
 	}
}

int dfs1 (int x) {
	bio[x] = 1;
	Q.push_back(x);
	for (int i=0; i<l[x].size(); i++) {
		if (bio[l[x][i]] == 0) {
			return dfs1(l[x][i]);
		}
 	}
}

int main() {
	
	cin >>n >>m;
	
	for (int i=0; i<m; i++) {
		int a, b;
		cin >>a >>b;
		l[a].push_back(b);
		l[b].push_back(a);
	}
	
	dfs1(1);
	for (int i=0; i<l[1].size(); i++) {
		if (bio[l[1][i]] == 0) {
			dfs2(l[1][i]);
			break;
		}
	}
	cout <<Q.size() <<endl;
	while(!Q.empty()) {
		cout <<Q.front() <<" ";
		Q.pop_front();
	}
	
	return 0;
}


Measured memory_bytes: 9472
/**
*    author:  yamako
*    created: 05.08.2020 23:02:17
**/

#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <algorithm>
#include <vector>
#include <math.h>
using namespace std;

struct Node {
    int key;
    Node *right, *left, *parent;
};

Node *root, *NIL;

Node *treeMinimum(Node *x) {
    while(x->left != NIL) x = x->left;
    return x;
}

Node *find(Node *u, int k) {
    while (u != NIL && k != u->key) {
        if (k < u->key) u = u->left;
        else u = u->right;
    }
    return u;
}

Node *treeSuccessor(Node *x) {
    if (x->right != NIL) return treeMinimum(x->right);
    Node *y = x->parent;
    while(y != NIL && x == y->right) {
        x = y;
        y = y->parent;
    }
    return y;
}

void *treeDelete(Node *z) {
    Node *y;
    Node *x;

    if (z->left == NIL || z->right == NIL) y = z;
    else y = treeSuccessor(z);

    if (y->left != NIL) {
        x = y->left;
    } else {
        x = y->right;
    }

    if (x != NIL) {
        x->parent = y->parent;
    }

    if (y->parent == NIL) {
        root = x;
    } else {
        if (y == y->parent->left) {
            y->parent->left = x;
        } else {
            y->parent->right = x;
        }
    }

    if (y != z) z->key = y->key;

    free(y);
}

void insert(int k) {
    Node *y = NIL;
    Node *x = root;
    Node *z;

    z = (Node *)malloc(sizeof(Node));
    z->key = k;
    z->left = NIL;
    z->right = NIL;

    while (x != NIL) {
        y = x;
        if (z->key < x->key) {
            x = x->left;
        } else {
            x = x->right;
        }
    }

    z->parent = y;
    if (y == NIL) {
        root = z;
    } else {
        if (z->key < y->key) {
            y->left = z;
        } else {
            y->right = z;
        }
    }
}



void inorder(Node *u) {
    if (u == NIL) return;
    inorder(u->left);
    printf(" %d", u->key);
    inorder(u->right);
}

void preorder(Node *u) {
    if (u == NIL) return;
    printf(" %d", u->key);
    preorder(u->left);
    preorder(u->right);
}

int main() {
    int n, i, x;
    string com;

    scanf("%d", &n);

    for (int i = 0; i < n; i++) {
        cin >> com;
        if (com[0] == 'f') {
            scanf("%d", &x);
            Node *t = find(root, x);
            if (t != NIL) printf("yes\n");
            else printf("no\n");
        } else if (com == "insert") {
            scanf("%d", &x);
            insert(x);
        } else if (com == "delete") {
            scanf("%d", &x);
            treeDelete(find(root, x));
        } else if (com == "print") {
            inorder(root);
            printf("\n");
            preorder(root);
            printf("\n");
        }
    }

    return 0;
}


Measured memory_bytes: 22028
#include <bits/stdc++.h>
#define pb push_back
#define all(a) a.begin(), a.end()
#define sz(a) (int)a.size()
#define x first
#define y second
#define debug(...) cout << "[" << #__VA_ARGS__ << ": " << __VA_ARGS__ << "]\n"
#define rd() abs((int)rng())
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int>pii;
const int maxn = 2e3 + 100;
const int mod = 1e9 + 7;
mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
int n, A, B, C, D;
string s;
int main()
{
	ios_base::sync_with_stdio(false), cin.tie(0);
	cin >> n >> A >> B >> C >> D;
	--A, --B, --C, --D;
	cin >> s;
	while(A != C || B != D)
	{
		bool chk = false;
		if(A != C)
		{
			if(A + 2 <= C && A + 2 != B && s[A + 2] != '#')
			{
				chk = true;
				A += 2;
			}
			else if(A + 1 != B && s[A + 1] != '#')
			{
				chk = true;
				A++;
			}
		}
		if(!chk && B != D)
		{
			if(B + 1 != A && s[B + 1] != '#')
			{
				chk = true;
				B++;
			}
			else if(B + 2 <= D && B + 2 != A && s[B + 2] != '#')
			{
				chk = true;
				B += 2;
			}
		}
		if(!chk)
			return cout << "No\n", 0;
	}
	assert(A == C && B == D);
	cout << "Yes\n";
	return 0;
}

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

using namespace std;

#define sp(x) cout<<setprecision(x);
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define REP(i,n) FOR(i,0,n)
#define all(a) (a).begin(), (a).end()
#define inf 10000000
#define linf INT64_MAX*0.99
#define print(s) cout<<(s)<<endl

typedef pair<int, int> P;
typedef long long ll;
 
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    vector<int> n(4);
    REP(i,4) cin>>n[i];
    sort(all(n));
    if(n[0] == 1 && n[1] == 4 && n[2] == 7 && n[3] == 9) print("YES");
    else print("NO");
    return 0;
}

Measured memory_bytes: 256
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		// TODO 自動生成されたメソッド・スタブ

		Scanner sc = new Scanner(System.in);

		int a = sc.nextInt();
		int b = sc.nextInt();
		int h = sc.nextInt();

		System.out.println(((a + b) * h) / 2);

	}

}

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

using ll = long long;

const int mod = 1e9 + 7;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int N;
    cin >> N;
    string S;
    cin >> S;
    int ans = 0;
    for (int i = 0; i + 3 <= S.size(); i++) {
        if (S.substr(i, 3) == "ABC")
            ans++;
    }
    cout << ans << endl;
}

Measured memory_bytes: 256
#include "bits/stdc++.h"
 
typedef long long ll;
#define int ll
#define fi first
#define se second
#define SORT(a) sort(a.begin(),a.end())
#define rep(i,n) for(int i = 0;i < (n) ; i++) 
#define REP(i,n) for(int i = 0;i < (n) ; i++) 
#define MP(a,b) make_pair(a,b)
#define pb(a) push_back(a)
#define INF LLONG_MAX/2
#define all(x) (x).begin(),(x).end()
#define debug(x) cerr<<#x<<": "<<x<<endl
#define debug_vec(v) cerr<<#v<<":";rep(i,v.size())cerr<<" "<<v[i];cerr<<endl
using namespace std;
int MOD = 1000000007;

signed main(){
    int n;
    cin >> n;
    vector<int> a(n);
    map<int,int> m;
    rep(i,n){
        int a;
        cin >> a;
        m[a]++;
    }

    auto itr = m.find(0);
    if(itr != m.end()){
        if(m[0] == n){
            cout << "Yes" << endl;
        }else{
            if(m.size() != 2){
                cout << "No" << endl;
            }else{
                int val[2];
                int i = 0;
                for(auto x:m){
                    if(x.fi == 0)val[0] = x.se;
                    else val[1] = x.se;
                }
                if(val[0]*2 == val[1]){
                    cout << "Yes" << endl;
                }else{
                    cout << "No" << endl;
                }
            }
        }
    }else{
        if(m.size() != 3){
            cout << "No" << endl;
        }else{
            int val[2][3];
            int i = 0;
            for(auto x:m){
                val[0][i] = x.fi;
                val[1][i] = x.se;
                i++;
            }
            if(val[1][0] == val[1][1] && val[1][0] == val[1][2]
                && (val[0][0]^val[0][2]) == val[0][1]
                && (val[0][1]^val[0][0]) == val[0][2]
                && (val[0][2]^val[0][1]) == val[0][0]){
                    cout << "Yes" << endl;
            }else{
                cout << "No" << endl;
            }
        }
    }

    
    
    return 0;
}

// g++ -std=c++14 code1.cpp
// rm -r -f test;oj dl https://cf17-final-open.contest.atcoder.jp/tasks/cf17_final_a
// rm -r -f test;oj dl http://agc035.contest.atcoder.jp/tasks/agc035_a

Measured memory_bytes: 5632
sx,sy,tx,ty=map(int,input().split())
x=tx-sx
y=ty-sy
ans=""
ans+="U"*y
ans+="R"*x
ans+="D"*y
ans+="L"*(x+1)
ans+="U"*(y+1)
ans+="R"*(x+1)
ans+="DR"
ans+="D"*(y+1)
ans+="L"*(x+1)
ans+="U"
print(ans)


Measured memory_bytes: 38384
#include <cstdio>
#include <algorithm>
using namespace std;

int dp[100001] = {};

int main() {
    int n;
    scanf("%d", &n);
    
    dp[0] = 0;
    for (int p = 0; p <= n; p++) {
        for (int base = 9; base <= n; base *= 9) {
            if (p + base <= n) {
                dp[p+base] = dp[p+base] ? min(dp[p+base], dp[p] + 1) : dp[p] + 1;
            }
        }
        for (int base = 6; base <= n; base *= 6) {
            if (p + base <= n) {
                dp[p+base] = dp[p+base] ? min(dp[p+base], dp[p] + 1) : dp[p] + 1;
            }
        }
        dp[p+1] = dp[p+1] ? min(dp[p+1], dp[p] + 1) : dp[p] + 1;
    }

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

    return 0;
}

Measured memory_bytes: 512
#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 ALL(x) x.begin(),x.end()
#define REVERSE(x) reverse(x.begin(),x.end())
#define SORT(x,n) sort(x,x)
#define P pair<int,int>
typedef long long LL;
const int INF=1000000007;
using namespace std;
int gcd(int a,int b){
  if(a%b==0){return b;}
  else{return gcd(b,a%b);}
}
int main(){
  int N,K;
  cin>>N>>K;
  vector<int> h(N);
  REP(i,N){
    cin>>h[i];
  }
  sort(ALL(h));
  int ans=INF;
  REP(i,N-K+1){
    ans=min(ans,h[i+K-1]-h[i]);
  }
  cout<<ans;
}

Measured memory_bytes: 640
n,k=map(int,input().split())
a=list(map(int,input().split()))
total=sum(a)
if k<a[0]:
    a[0]=k
for i in range(n-1):
    if k<a[i]+a[i+1]:
        a[i+1]=k-a[i]
print(total-sum(a))


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

using namespace std;

typedef long long ll;

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

	string S;
	cin >> S;

	for(int i = 0; i < 3; i++){
		if(S[i] == S[i+1]){
			cout << "Bad" << endl;
			return 0;
		}
	}

	cout << "Good" << endl;
}


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

ll maxi(ll a, ll b){
  if (a>b) return a;
  else return b;
}

int main(){
  ll N;
  cin >> N;
  vector<ll> H(N);
  for(int i=0; i<N; i++) cin >> H[i];
  
  ll ans=0;
  ll temp=0;
  for(int i=0; i<N-1; i++){
    if (H[i+1]<=H[i]){
      temp++;
      if (ans<temp) ans=temp;
    }else{
      temp=0;
    }
  }
  cout <<ans<<endl;
}

Measured memory_bytes: 1024
H, W, M = map(int, input().split())

h_list = [0 for i in range(H)]
w_list = [0 for i in range(W)]

point = {}
for _ in range(M):
    h, w = map(int, input().split())
    h_list[h - 1] += 1
    w_list[w - 1] += 1
    point[(h - 1, w - 1)] = 1

hmax = 0
wmax = 0
hmap = {}
wmap = {}
for i, h in enumerate(h_list):
    if hmax <= h:
        hmax = h
        hmap.setdefault(h, []).append(i)
for i, w in enumerate(w_list):
    if wmax <= w:
        wmax = w
        wmap.setdefault(w, []).append(i)
# print(hmap)
# print(wmap)
# hmax = max(h_list)
# wmax = max(w_list)
h_index = h_list.index(hmax)
w_index = w_list.index(wmax)

for h in hmap[hmax]:
    for w in wmap[wmax]:
        if (h, w) not in point:
            print(hmax + wmax)
            exit(0)

print(hmax + wmax - 1)

Measured memory_bytes: 169744
using System;
using System.Collections;
using System.Collections.Generic;
using System.Text;
using System.Linq;
using static MyIO;


public class A
{
	public static void Main()
	{
		Console.WriteLine(GetString().ToCharArray().Count(x => x == '2'));
	}
}


public static class MyIO
{
	private static string[] args = null;
	private static int num = -1;
	private static int used = -1;

	private static string getArg()
	{
		if(used == num)
		{
			args = Console.ReadLine().Split(' ');
			num = args.Length;
			used = 0;
		}
		return args[used++];
	}

	public static int GetInt(){ return int.Parse(getArg()); }
	public static long GetLong(){ return long.Parse(getArg()); }
	public static double GetDouble(){ return double.Parse(getArg()); }
	public static string GetString(){ return getArg(); }
}

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

int main(){
    int K,N;
    while(cin>>K>>N){
        int ans=0;
        for(int a=0;a<=K;a++){
            for(int b=0;b<=K;b++){
                int c=N-a-b;
                if(c<0) break;
                else if(c<=K) ans++;
            }
        }
        cout<<ans<<endl;
    }
    return 0;
}


Measured memory_bytes: 3192
#include <queue>
#include <vector>
#include <iostream>
 
#define INF (1 << 25)
 
using namespace std;
 
vector<vector<vector<vector<int> > > > dp;
 
vector<vector<int> > M;
 
int H, W, sx1, sy1, sx2, sy2;
 
const int dx[4] = { 0, 1, 0, -1 };
const int dy[4] = { 1, 0, -1, 0 };
 
int bfs()
{
    dp = vector<vector<vector<vector<int> > > >(H, vector<vector<vector<int> > >(W, vector<vector<int> >(H, vector<int>(W, INF)))); dp[sy1][sx1][sy2][sx2] = 0;
 
    queue<pair<pair<pair<int, int>, pair<int, int> >, int> > que; que.push(make_pair(make_pair(make_pair(sx1, sy1), make_pair(sx2, sy2)), 0));
 
    while (!que.empty())
    {
        int x1 = que.front().first.first.first;
        int y1 = que.front().first.first.second;
        int x2 = que.front().first.second.first;
        int y2 = que.front().first.second.second;
 
        int turn = que.front().second;
 
        que.pop();
 
        for (int dir = 0; dir < 4; dir++)
        {
            int tx1 = x1 + dx[dir]; if (tx1 < 0 || tx1 >= W) { tx1 -= dx[dir]; }
            int ty1 = y1 + dy[dir]; if (ty1 < 0 || ty1 >= H) { ty1 -= dy[dir]; }
            int tx2 = x2 - dx[dir]; if (tx2 < 0 || tx2 >= W) { tx2 += dx[dir]; }
            int ty2 = y2 - dy[dir]; if (ty2 < 0 || ty2 >= H) { ty2 += dy[dir]; }
 
            if (M[ty1][tx1] == 1) { tx1 -= dx[dir]; ty1 -= dy[dir]; }
            if (M[ty2][tx2] == 1) { tx2 += dx[dir]; ty2 += dy[dir]; }
 
            if (tx1 == tx2 && ty1 == ty2) { return turn + 1; }
 
            if (dp[ty1][tx1][ty2][tx2] == INF)
            {
                dp[ty1][tx1][ty2][tx2] = turn + 1;
 
                que.push(make_pair(make_pair(make_pair(tx1, ty1), make_pair(tx2, ty2)), turn + 1));
            }
        }
    }
 
    return -1;
}
 
int main()
{
    while (true)
    {
        cin >> W >> H;
 
        if (H == 0 && W == 0) { break; }
 
        M = vector<vector<int> >(H, vector<int>(W));
 
        cin >> sx1 >> sy1 >> sx2 >> sy2;
 
        sx1--; sy1--; sx2--; sy2--;
 
        for (int i = 0; i < H; i++)
        {
            for (int j = 0; j < W; j++)
            {
                cin >> M[i][j];
            }
        }
 
        int Ans = bfs();
 
        if (Ans == -1)
        {
            cout << "NA" << endl;
        }
        else
        {
            cout << Ans << endl;
        }
    }
 
    return 0;
}


Measured memory_bytes: 60288
#include <iostream>
using namespace std;
int n, m, a, b, s, v[55][55];

int main() {
	int i, j;
	cin>>n>>m;
	while(m--) {
		cin>>a>>b;
		v[a][b] = v[b][a] = 1;
		v[a][0]++, v[b][0]++;
	}
	for(i=1; i<=n; i++) if(v[i][0]==1) {
		s++;
		for(j=1; j<=n; j++) if(v[i][j]) {
			v[i][j] = v[j][i] = 0;
			v[i][0]--, v[j][0]--;
			i = 0;
			break;
		}
	}
	cout<<s;
	return 0;
}

Measured memory_bytes: 256
#include<stdio.h>

int main(){
  int n, i;
  int a[1001];
  scanf("%d", &n);
  for(i = 0;i<n;i++){
    scanf("%d", &a[i]);
    if(a[i]%2==0){
      if(a[i]%3!=0&&a[i]%5!=0){
        printf("DENIED");
        return 0;
      }
    }
  }
  printf("APPROVED");
  return 0;
}

Measured memory_bytes: 128
#include<bits/stdc++.h>
using namespace std ; 
int main()
{
	std::ios_base::sync_with_stdio(false);
	std::cin.tie(NULL);
	int n  , m  , temp; 
	cin >> n >> m ; 
	for(int i = 0 ; i < m ; ++i)
	{
		cin >> temp ; 
		n -= temp ; 
	}
	if(n < 0)
	{
		cout << "-1" ;
	}
	else
	{
		cout << n ; 
	}
}



Measured memory_bytes: 3656
#include<bits/stdc++.h>
#include<unordered_set>
#include<unordered_map>
#include <algorithm> 
#include <iostream>
#include <string>
#include <cmath>
using namespace std;
#define ll long long
#define rep(i,n) for (ll i = 0; i < (n); i++)
#define FOR(i,a,b) for(ll i=(a);i<(b);i++)
#define FORR(i,a,b)for(ll i=(a);i<=(b);i++)
#define repR(i,n) for(ll i=n;i>=0;i--)
#define all(v)(v).begin(),(v).end()
#define rall(v)(v).rbegin(),(v).rend()
#define F first
#define S second
#define pb push_back
#define pu push
#define COUT(x) cout<<(x)<<"\n"
#define PQ priority_queue<ll>
#define PQR priority_queue<ll,vector<ll>,greater<ll>>
#define YES(n) cout << ((n) ? "YES\n" : "NO\n"  )
#define Yes(n) cout << ((n) ? "Yes\n" : "No\n"  )
#define mp make_pair
#define sz(x) (ll)(x).size()
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef tuple<ll,ll,ll> tll;
const ll MOD = 1000000007LL;
const ll INF = 1LL << 60;
using vll = vector<ll>;
using vb = vector<bool>;
using vvb = vector<vb>;
using vvll = vector<vll>;
using vstr = vector<string>;
using vc = vector<char>;
using vvc = vector<vc>;
template<class T> inline bool chmax(T& a, T b) { 
 if (a < b) { a = b; return true; } return false; 
}
template<class T> inline bool chmin(T& a, T b) {
 if (a > b) { a = b; return true; } return false; 
}
ll dx[4]={0,1,0,-1};
ll dy[4]={1,0,-1,0};
//二項係数 nCr
const int MAX = 700000;

long long fac[MAX], finv[MAX], inv[MAX];

// テーブルを作る前処理
void COMinit() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (int i = 2; i < MAX; i++){
        fac[i] = fac[i - 1] * i % MOD;
        inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }
}

// 二項係数計算
long long COM(int n, int k){
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}
int main(){
  COMinit();
  ll n;
  cin>>n;
  if(n<3){
    COUT(0);
    return 0;
  }
  ll mi=1;
  ll ma=n/3;
  ll ans=0;
  for(int i=mi;i<=ma;i++){
    ll no=n-i*3;
    ans+=COM(no+i-1,i-1);
    ans%=MOD;
  }
  COUT(ans);
}

Measured memory_bytes: 20032
#include<bits/stdc++.h>
#define X first
#define Y second
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;
const ll N = 2005, inf = 1e18, mod = 1e9+7;

ll n, m, x, v, two[N] = {1}, par[N];
bool mst[N];

vector<pair<ll,pll> > e;
vector<pll> adj[N];
vector<ll> cst;

ll Find (ll X) {
	if(par[X] == X) return X;
	return par[X] = Find(par[X]);
}

ll dfs (ll C, ll P, ll O) {
	if(C == O) return 0;
	for(auto &T : adj[C]) {
		ll A, B, V; tie(A, B) = T;
		if(A == P) continue;
		V = dfs(A, C, O);
		if(~V) return max(V, B);
	}
	return -1;
}

int main()
{
	scanf("%lld%lld%lld",&n,&m,&x);
	for(ll i=1;i<=m;i++) two[i] = two[i-1] * 2 % mod;
	for(ll i=0;i<m;i++) {
		ll A, B, C;
		scanf("%lld%lld%lld",&A,&B,&C);
		e.push_back({C, {A, B}});
	}
	sort(e.begin(), e.end());
	iota(par+1, par+1+n, 1);
	for(ll i=0;i<m;i++) {
		ll A, B, C = e[i].X;
		tie(A, B) = e[i].Y;
		if(Find(A) != Find(B)) {
			v += C; mst[i] = true;
			adj[A].push_back({B,C});
			adj[B].push_back({A,C});
			par[Find(A)] = Find(B);
		}
	}
	for(ll i=0;i<m;i++) {
		if(mst[i]) continue;
		cst.push_back(e[i].X-dfs(e[i].Y.X, 0, e[i].Y.Y));
	}
	ll V1 = 0, V2 = 0, V3 = 0, ans = 0;
	for(auto &T : cst) {
		if(v + T < x) V1++;
		if(v + T == x) V2++;
		if(v + T > x) V3++;
	}
	ans = 2 * (two[V2] + mod - 1) * two[V3] % mod;
	if(v == x) {
		ans = (ans + (two[n-1] + mod - 2) * two[m-n+1]) % mod;
	}
	printf("%lld\n",ans);
}


Measured memory_bytes: 512
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <numeric>

using namespace std;
int main(){
  int n;
  vector<int> x;
  cin >> n;
  for(int i = 0; i < n; i++) {
    int tmp;
    cin >> tmp;
    x.push_back(tmp);
  }

  int p = round((double)accumulate(x.begin(), x.end(), 0) / (double)x.size());
 
  int hp = 0; 
  for(int i = 0; i < n; i++) {
    hp += pow((x[i] - p), 2);
  }

  cout << hp << endl;
  return 0;
}


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

namespace Atcoder
{
    class Program
    {
        static void Main(string[] args)
        {
            string[] input = Console.ReadLine().Split(' ');

            int x = int.Parse(input[0]);
            int a = int.Parse(input[1]);
            int b = int.Parse(input[2]);

            int s = Math.Abs(a - x);
            int t = Math.Abs(b - x);

           if(s > t)
            {
                Console.WriteLine('B');
            }else
            {
                Console.WriteLine('A');
            }
        }
    }
}

Measured memory_bytes: 11092
// ProblemURL : https://atcoder.jp/contests/abc116/tasks/abc116_b
// ---------------------------------------------
package main

import "fmt"

func main() {
	var s int
	fmt.Scan(&s)
	f := func(n int) int {
		if n%2 == 0 {
			return n / 2
		}
		return n*3 + 1
	}
	as := make([]int, 1000001)
	as[0] = s
	for i := 1; i < 1000000; i++ {
		as[i] = f(as[i-1])
	}
	mp := make(map[int]int, 1000001)
	ans := -1
	for i := range as {
		if _, exist := mp[as[i]]; exist {
			ans = i
			break
		}
		mp[as[i]]++
	}
	fmt.Println(ans + 1)
}


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

using namespace std;

#define INF 1000007
#define MOD 1000000007
#define int long long
#define maxn 100
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define rep(i, n) FOR(i, 0, n)

typedef std::pair<int, int> P;

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; }

int mpow(int N, int P, int M) //繰り返し自乗法
{
    if (P == 0)
        return 1;
    if (P % 2 == 0) {
        int t = mpow(N, P / 2, M);
        return t * t % M;
    }
    return N * mpow(N, P - 1, M) % M;
}

int counter(int x) //bit計算
{
    if (x == 0)
        return 0;
    return counter(x >> 1) + (x & 1);
}

vector<bool> prime(maxn + 1, true); //素数テーブル
void prime_table(void) {
    prime[0] = false;
    prime[1] = false;
    for (int i = 2; i * i <= maxn; i++) {
        if (!prime[i]) {
            continue;
        }
        for (int j = i + i; j <= maxn; j += j + i) {
            prime[j] = false;
        }
    }
}

bool IsPrime(int num) //素数判定
{
    if (num < 2)
        return false;
    else if (num == 2)
        return true;
    else if (num % 2 == 0)
        return false;

    double sqrtNum = sqrt(num);
    for (int i = 3; i <= sqrtNum; i += 2) {
        if (num % i == 0) {
            return false;
        }
    }

    return true;
}

vector<int> divisor(int n) //約数列挙
{
    vector<int> ret;
    for (int i = 1; i * i <= n; i++) {
        if (n % i == 0) {
            ret.push_back(i - 1);
            if (i * i != n) {
                ret.push_back((n / i) - 1);
            }
        }
    }
    sort(ret.begin(), ret.end());
    return (ret);
}

signed main() {
    int N, M;
    cin >> N >> M;
    if (N == M) {
        cout << "Yes" << endl;
    }else{
        cout << "No" <<endl;
    }
}


Measured memory_bytes: 256
length, max_num, num_range = list(map(int, input().split()))
import itertools

ds = [0]
get_point = 0

a_list = []
b_list = []
c_list = []
d_list = []

for n in range(num_range):
    a, b, c, d = (list(map(int, input().split())))
    a_list.append(a)
    b_list.append(b)
    c_list.append(c)
    d_list.append(d)

    # ds.append(ds[n] + d)

# print(ds)
ans=0
for _, A in enumerate(itertools.combinations_with_replacement(range(1, max_num + 1), length)):
    tmp = 0
    for i,d in enumerate(d_list):
        a= A[a_list[i] - 1]
        b = A[b_list[i] - 1]

        if b-a == c_list[i]:
            # print(A, a, b,ds[i+1], c_list[i])
            tmp+=d
            ans=max(ans, tmp)
print(ans)



Measured memory_bytes: 9196