akhauriyash/Code-Regression huggingface dataset:
n,k = map(int,input().split())
al = list(map(int,input().split()))

onel = []

for i in range(n):
   p = 0
   for j in range(i+1, n):
      if al[i] > al[j]:
         p += 1
   onel.append(p)

alll = []
for i in range(n):
   p = 0
   for a in al:
      if al[i] > a:
         p += 1
   alll.append(p)

ans = 0
for i, j in zip(onel, alll):
   ans += k*i + (k-1)*k*j//2
   ans %= 10**9 + 7
print(ans)

Measured memory_bytes: 3188
#include <iostream>
#include <string>
#include <vector>
#include <math.h>
#include <stdio.h>
#define rep(i,n) for(int i=0;i<(n);i++)
typedef long long ll;
#define mod 1000000007;
using namespace std;


int main(){
    int N;
    int d[100007];
    cin >> N;
    rep(i,N){
        cin >> d[i];
    }
    sort(d,d+N);
    cout << d[N/2]-d[N/2-1] <<endl;
}



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

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



int main(){

    ll r;
    cin >> r;

    cout << fixed;
    cout << setprecision(10) << 2*r*M_PI << endl;



    return 0;
}  



Measured memory_bytes: 3784
#line 2 "header.hpp"

//%snippet.set('header')%
//%snippet.fold()%
#ifndef HEADER_H
#define HEADER_H

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

// varibable settings
#define int long long
const int INF = 1e18;

#define _overload3(_1, _2, _3, name, ...) name
#define _rep(i, n) repi(i, 0, n)
#define repi(i, a, b) for (int i = (int)(a); i < (int)(b); ++i)
#define rep(...) _overload3(__VA_ARGS__, repi, _rep, )(__VA_ARGS__)
#define _rrep(i, n) rrepi(i, 0, n)
#define rrepi(i, a, b) for (int i = (int)((b)-1); i >= (int)(a); --i)
#define r_rep(...) _overload3(__VA_ARGS__, rrepi, _rrep, )(__VA_ARGS__)
#define each(i, a) for (auto &&i : a)
#define all(x) (x).begin(), (x).end()
#define sz(x) ((int)(x).size())
#define pb(a) push_back(a)
#define mp(a, b) make_pair(a, b)
#define mt(...) make_tuple(__VA_ARGS__)
#define ub upper_bound
#define lb lower_bound
#define lpos(A, x) (lower_bound(all(A), x) - A.begin())
#define upos(A, x) (upper_bound(all(A), x) - A.begin())
template <class T>
inline void chmax(T &a, const T &b) {
    if ((a) < (b)) (a) = (b);
}
template <class T>
inline void chmin(T &a, const T &b) {
    if ((a) > (b)) (a) = (b);
}

#define divceil(a, b) ((a) + (b)-1) / (b)
#define is_in(x, a, b) ((a) <= (x) && (x) < (b))
#define uni(x)    \
    sort(all(x)); \
    x.erase(unique(all(x)), x.end())
#define slice(l, r) substr(l, r - l)

typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef long double ld;
typedef pair<int, int> pii;
typedef tuple<int, int, int> iii;

template <typename T>
using PQ = priority_queue<T, vector<T>, greater<T>>;
struct Fast {
    Fast() {
        std::cin.tie(0);
        ios::sync_with_stdio(false);
    }
} fast;
void check_input() {
    assert(cin.eof() == 0);
    int tmp;
    cin >> tmp;
    assert(cin.eof() == 1);
}

#if defined(PCM) || defined(LOCAL)
#else
#define dump(...) ;
#define dump_1d(...) ;
#define dump_2d(...) ;
#define cerrendl ;
#endif

#endif /* HEADER_H */
//%snippet.end()%
#line 2 "solve.cpp"

signed main() {
    //input
    int k;cin>>k;
    int a,b;cin>>a>>b;
    check_input();

    //solve
    rep(i, a, b+1){
        if (i%k==0){
            cout << "OK" << endl;
            return 0;
        }
    }
    cout << "NG" << endl;

    return 0; 
}


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

int main() { /* ここに書く */

  long long H , W , Ans ;
  cin >> H >> W ;
  
  if(H==1 || W==1){
    cout << 1 << endl;}
  
  else{
  Ans = H*W/2 ;
  
  if(H*W%2==1){
    Ans = Ans + 1 ;
  }

  cout << Ans << endl;
  }
}

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

using namespace std;

int main() {
  int n, k;
  cin >> n >> k;
  vector<int> vec(n);
  for (auto &v : vec)
    cin >> v;
  sort(vec.begin(), vec.end());
  int ans = INT_MAX;
  for (int i = 0; i + k - 1 < n; ++i)
    ans = min(ans, vec[i+k-1] - vec[i]);
  cout << ans << endl;
}

Measured memory_bytes: 3672
#include <iostream>
#include <cstdio>
using namespace std;
typedef long long ll;

ll n, s, s1, a[100005];
int main() {
	ll i, k;
	cin>>n;
	for(i=0; i<n; i++) {
		scanf("%lld", &a[i]);
		s += a[i];
		if(i%2) s1 += a[i] * 2;
	}
	k = s - s1;
	for(i=0; i<n; i++) {
		printf("%lld ", k);
		k = a[i] * 2 - k;
	}
	return 0;
}


Measured memory_bytes: 2048
#include <bits/stdc++.h>
#define N 200010
using namespace std;
int A[N];

int main(){
  int n;
  cin>>n;
  for(int i=0;i<n;i++)cin>>A[i];
  
  deque <int> B;
  B.push_back(A[0]);
  for(int i=1;i<n;i++){
    if((n-i)%2==0) B.push_back(A[i]);
    else B.push_front(A[i]);
  }
  
  for(int i=0;i<B.size();i++){
    if(i)cout<<" ";
    cout<<B[i];
  }
  cout<<endl;

    
  
  return 0;
}


Measured memory_bytes: 3840
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define ll long long
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define sz(a) ll((a).size())
#define all(a) (a).begin(), (a).end()
#define REP(i,n) for(int i=0;i<(n);++i)
#define REPD(i,n) for(int i=(n)-1;i>=0;--i)
#define FOR(i,a,b) for(int i=(a);i<=(b);++i)
#define FORD(i,a,b) for(int i=(a);i>=(b);--i)
const ll MOD = 1E9+7;
const ll INF = 1E18;
const double EPS = 1E-9;
const double PI = atan(1.0) * 4.0;
template<class T> T getbit(T s, int i) {return s>>i&1;}
template<class T> void flipbit(T& s, int i) {s^=(1LL<<i);}
constexpr int cntbit(ll x) {return __builtin_popcountll(x);}
constexpr int lg2(ll x) {return __lg(x);} // return int(log2(x))
// mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
mt19937 rng((uint32_t)chrono::steady_clock::now().time_since_epoch().count()); 
ll fpow(ll a,ll p){ll res=1LL;while(p){if(p&1LL) res=res*a%MOD;a=a*a%MOD;p>>=1LL;} return res;}

int main() {
	ios_base::sync_with_stdio(0);cin.tie(0);
	string s;
	int m,n;
	cin>>m>>n>>s;
	s[n-1]-='A';
	s[n-1]+='a';
	cout<<s<<'\n';
}



Measured memory_bytes: 3644
#include <bits/stdc++.h>
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()
{
  string S; cin >> S;
  int n; n = S.size();
  bool isAC = true;
  
  if(S[0] != 'A')
    isAC = false;
  
  int Cnum = 0;
  FOR(i, 2, n-1) {
    if(S[i] == 'C')
      Cnum++;
  }
  if(Cnum != 1)
    isAC = false;
  
  FOR(i, 1, n) {
    if('a' <= S[i] && S[i] <= 'z' || S[i] == 'C')
      continue;
    isAC = false;
    break;
  }
  
  if(isAC)
    cout << "AC" << endl;
  else
    cout << "WA" << endl;
}

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

struct Point { double x, y;};

void koch(int n, Point a, Point b){
  if(n == 0) return;
  Point s, t, u;//三つの構造体を定義
  double th = M_PI * 60.0 / 180.0; //度からラジアンへ単位変換

  s.x = (2.0 * a.x + 1.0 * b.x) / 3.0;
  s.y = (2.0 * a.y + 1.0 * b.y) / 3.0;
  t.x = (1.0 * a.x + 2.0 * b.x) / 3.0;
  t.y = (1.0 * a.y + 2.0 * b.y) / 3.0;
  u.x = (t.x - s.x) * cos(th) - (t.y - s.y) * sin(th) + s.x;
  u.y = (t.x - s.x) * sin(th) + (t.y - s.y) * cos(th) + s.y;

  koch(n-1, a, s);
  printf("%.8f %.8f\n", s.x, s.y);
  koch(n-1, s, u);
  printf("%.8f %.8f\n", u.x, u.y);
  koch(n-1, u, t);
  printf("%.8f %.8f\n", t.x, t.y);
  koch(n-1, t, b);
}

int main(){
  Point a, b;
  int n;

  scanf("%d", &n);

  a.x = 0;
  a.y = 0;
  b.x = 100;
  b.y = 0;

  printf("%.8f %.8f\n", a.x, a.y);
  koch(n, a, b);
  printf("%.8f %.8f\n", b.x, b.y);

  return 0;
}


Measured memory_bytes: 2692
n, k = map(int,input().split())
if k%2 == 1:
    print((n//k)**3)
else:
    cnt1 = 0
    cnt2 = 0
    for i in range(1, n+1):
        if i%k == 0:
            cnt1 += 1
        if i%k == k//2:
            cnt2 += 1
        
    print(cnt1**3 + cnt2**3)
    

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

#define         pb         push_back
#define         sf(x)      scanf("%d",&x)
#define         sfl(x)     scanf("%lld",&x)
#define         pf(x)      printf("%d\n",x)
#define         pfl(x)     printf("%lld\n",x)
#define         endl       '\n'
#define         pii        pair<int,int>
#define         mapii      map<int,int>
#define         mapll      map<ll,ll>
#define         mapci      map<char,int>
#define         mapcl      map<char,ll>
#define         mapsi      map<string,int>
#define         mapsl      map<string,ll>
#define         pll        pair<ll,ll>
#define         vi         vector<int>
#define         vl         vector<ll>
#define         vd         vector<double,double>
#define         all(c)     c.begin(),c.end()
#define         F          first
#define         S          second
#define         mp         make_pair
#define        ftc(x)      cerr << #x << ": " << x << " " << endl;
#define         PI         acos(-1)
#define         lcm(a,b)   ((a*b)/__gcd(a,b))

mapii mpt;
map<pii,int>ma;
vector<pii>ad;
bool vis[2000008];

int main()
{
    int i,j,k,l,m,n,x,y,mx=0;
    cin >> n;
    vector<int>v[n+10];

    for(i=1; i<n; i++)
    {
        cin >> x >> y;
        v[x].pb(y);
        v[y].pb(x);
        ma[ {x,y}]++;
        ma[ {y,x}]++;
        ad.pb({x,y});
    }
    for(i=1; i<=n; i++)
    {
        l = v[i].size();
        mx = max(mx,l);
    }

    int cnt=1;
    vis[1]=true;
    for(i=0; i<v[1].size(); i++)
    {
        ma[ {1,v[1][i]}] = cnt;
        ma[ {v[1][i],1}] = cnt;
        mpt[v[1][i]] = cnt;
        vis[v[1][i]] = true;
        cnt++;
    }

    for(i=2; i<=n; i++)
    {
        for(auto x : v[i])
        {
            if(vis[x])
                continue;
            if(mpt[i]==cnt)
                cnt++;
            if(cnt>mx)
                cnt=1;
            ma[ {i,x}] = cnt;
            ma[ {x,i}] = cnt;
            vis[x]=true;
            mpt[x]=cnt;
            cnt++;
            if(cnt>mx)
                cnt=1;
        }
    }


    cout << mx << endl;

    for(i=0; i<n-1; i++)
    {
        cout<<ma[ad[i]]<<endl;
    }
}


Measured memory_bytes: 24180
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,a) for(int i=0;i<(a);i++)
const ll MOD=1000000007;
//const ll MOD=998244353;

int cnt[20202];

int main(){
  int N,X,Y; cin>>N>>X>>Y; X--,Y--;
  rep(i,N){
    if(i<X){
      for(int j=i+1;j<N;j++){
        if(j<=X) cnt[j-i]++;
        else if(j<=Y){
          cnt[min(j-i,X-i+1+Y-j)]++;
        }else cnt[X-i+1+j-Y]++;
      }
    }else if(i<=Y){
      for(int j=i+1;j<N;j++){
        if(j<=Y) cnt[min(j-i,i-X+1+Y-j)]++;
        else cnt[min(j-i,i-X+1+j-Y)]++;
      }
    }else{
      for(int j=i+1;j<N;j++){
        cnt[j-i]++;
      }
    }
  }
  for(int i=1;i<N;i++) cout<<cnt[i]<<endl;
  return 0;
}

Measured memory_bytes: 256
#!/usr/bin/env python3
import sys

YES = "Yes"  # type: str
NO = "No"  # type: str


def solve(N: int):
    strN = str(N)
    for i in range(3):
        if strN[i] == "7":
            print(YES)
            return
        
    print(NO)
    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    solve(N)

if __name__ == '__main__':
    main()


Measured memory_bytes: 61720
#include <iostream>
#include <algorithm>
#include <cstdlib>
using namespace std;
int main(){
	long long int n, z, w;
	long long int a[2000];
	long long int dp[2][2000];
	cin >> n >> z >> w;
	for(int i = 0;i < n;i++){
		cin >> a[i];
	}
	dp[0][n - 2] = abs(a[n - 1] - a[n - 2]);
	dp[1][n - 2] = abs(a[n - 1] - a[n - 2]);
	for(int i = n - 3;i >= 0;i--){
		dp[0][i] = max(dp[0][i + 1], min(dp[1][i + 1], abs(a[n - 1] - a[i])));
		dp[1][i] = min(dp[1][i + 1], max(dp[0][i + 1], abs(a[n - 1] - a[i])));
	}
	cout << max(dp[0][0], abs(a[n - 1] - w)) << endl;
}

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

int MOD=1000000007;

int main() {
  int N,ans=0;
  cin >> N;
  string s[N+10],X;
  int t[N+10];
  for(int i=0; i<N; i++) cin >> s[i] >> t[i];
  cin >> X;
  for(int i=N-1; i>=0; i--){
    if(X==s[i]) break;
    ans+=t[i];
  }
  cout << ans << endl;
}

Measured memory_bytes: 256
n, W = map(int, input().split())
w, v = [], []
for i in range(n):
	a, b = map(int, input().split())
	w.append(a)
	v.append(b)
dp = [0] * (W + 1)
for i in range(n):
	for j in range(W, 0, -1):
		if j - w[i] >= 0:
			dp[j] = max(dp[j], dp[j - w[i]] + v[i])
print(dp[W])

Measured memory_bytes: 41580
import java.util.*;

public class Main{

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

		int n=sc.nextInt();
		int a[]=new int[n];
		for(int i=0;i<n;i++){
			a[i]=sc.nextInt();
		}

		int Alice=0;
		int Bob=0;

		Arrays.sort(a);

		for(int i=n-1;i>=0;i--){
			if((n-1)%2==0){
				if(i%2==0){
					Alice+=a[i];
				}else{
					Bob+=a[i];
				}
			}else{
				if(i%2!=0){
					Alice+=a[i];
				}else{
					Bob+=a[i];
				}
			}
		}


		System.out.println(Alice-Bob);


	}
}


Measured memory_bytes: 21972
import java.util.Arrays;
import java.util.Comparator;
import java.util.Scanner;

public class Main{
    public static void main(String[] a){
    	Scanner scanner = new Scanner(System.in);
    	Integer[] data = new Integer[10];
    	for (int i = 0; i < 10; i++) {
    		int number = scanner.nextInt();
    		while (!(0 <= number && number <= 10000)) {
    			number = scanner.nextInt();
    		}
    		data[i] = number;
    	}
    	scanner.close();
    	Arrays.sort(data, Comparator.reverseOrder());
    	for (int i = 0; i < 3; i++) {
    		System.out.println(data[i]);
    	}

    }
}

Measured memory_bytes: 26104
#include <bits/stdc++.h>
 
#define int         long long
#define uint        unsigned int
#define ld          long double
#define showoff     ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define pb          push_back
#define pii         pair<int,int>
#define FOR(i,a,b)  for(int i=a;i<b;++i)
#define RFOR(i,a,b) for(int i=a;i>b;--i)
#define f           first
#define se          second
#define maxn        200005
#define all(v)      v.begin(),v.end()
#define sz(x)       (int)x.size()
#define mod         1000000007
#define pqueue      priority_queue<int>
#define pdqueue     priority_queue< int,vector<int> ,greater< int >>
 
using namespace std;
 
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); 
 
int power(int a,int n)
{
    a %= mod;
    if(n == 1)return a;
    if(n == 0)return 1;
    if(n%2)return (a*(power((a*a)%mod,n/2)%mod))%mod;
    return power((a*a)%mod,n/2)%mod;
}
const int inf = (int) 1e18;
 
int inverse(int x){
    return power(x,mod-2)%mod;//little fermat....
}   

void solve(){
    int n,k;
    cin >> n >> k;
    vector<int>v(n+5),p,ne;
    FOR(i,1,n+1){
        cin >> v[i];
        if(v[i] >= 0)p.pb(v[i]);
        else ne.pb(-v[i]);
    }
    if(n == k){
        int ans = 1;
        FOR(i,1,n+1)if(v[i] < 0)ans *= (v[i]+mod)%mod,ans %= mod;
        else ans *= v[i],ans %= mod;
        cout << ans << "\n";
        return ;
    }
    sort(ne.begin(),ne.end(),greater<int>());
    sort(p.begin(),p.end(),greater<int>());
    int ans = 1;
    if(!sz(p)){
        if(k%2 != 0){
            sort(ne.begin(),ne.end());
            FOR(i,0,k){
                ne[i] = (-1*ne[i]+mod)%mod;
                ans *= ne[i],ans %= mod;
            }
        }
        else {
            FOR(i,0,k)ans *= ne[i],ans %= mod;
        }
    }
    else {
        int nt,pt = min(k,sz(p));
        if((k-pt)%2)pt--;
        nt = k-pt;
        while(nt+2 <= sz(ne) && pt >= 2 && ne[nt]*ne[nt+1] >= p[pt-1]*p[pt-2]){
            pt -= 2;
            nt += 2;
        }
        ans = 1;
        FOR(i,0,pt)ans *= p[i],ans %= mod;
        FOR(i,0,nt)ans *= ne[i],ans %= mod;
    }
    cout << ans << "\n";
}

signed main()
{
    showoff;
    int t = 1;
    //cin >> t;
    while(t--){
        solve();
    }
    return 0;
}
//*->for large size of matrix take int not long long if possible......
//*->always take maximum as inf for safer side ...#include <bits/stdc++.h>
 


Measured memory_bytes: 7004
N = int(input())
A= list(map(int, input().split()))
S = sum(A)
ans = 0
leaf = 1
S_now = 0

if A[0] == 1:
  if N==0:
    print(1)
  else:
    print(-1)
elif A[0] != 0:
  print(-1)
else:
  for i in range(N):
    ans += leaf
    leaf -= A[i]
    S_now += A[i] 
    leaf = min(leaf*2,S-S_now)
  if A[-1] != leaf:
    print(-1)
  else:
    print(ans+A[-1])

Measured memory_bytes: 83324
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<vector>
using namespace std;

long long cnt;
int l;
int A[1000000];
int n;
vector<int> G;

void insertionSort(int A[], int n, int g){
  for (int i = 0; i < n; i++){
    int v = A[i];
    int j = i - g;
    while(j >= 0 && A[j] > v){
      A[j + g] = A[j];
      j -= g;
      cnt++;
    }
    A[j + g] = v;
  }
}
void shellSort(int A[], int n){
  for (int h = 1; ; ){
    if( h > n ) break;
    G.push_back(h);
    h = 3*h + 1;
  }
  
  for (int i = G.size()-1; i >= 0; i--){
    insertionSort(A, n, G[i]);
  }
}

int main()
{
  cin >> n;
   
  for (int i = 0; i < n; i++) scanf("%d", &A[i]);
  cnt = 0;

  shellSort(A, n);
  
  cout << G.size() << endl;
  for (int i = G.size() - 1; i >= 0; i--){
    printf("%d", G[i]);
    if (i) printf(" ");
  }
  printf("\n");
  printf("%lld\n", cnt);
  for (int i = 0; i < n; i++) printf("%d\n", A[i]);
  
  return 0;
}



Measured memory_bytes: 7168
#include <bits/stdc++.h>
using namespace std;
const int64_t MOD = 1000000007;
int64_t pow3[100010];
bool dp[100010];

void init()
{
  pow3[0] = 1;
  for (int i = 1; i < 100010; i++)
  {
    pow3[i] = 3 * pow3[i - 1] % MOD;
  }
}

int64_t POW3(int x)
{
  if (x < 0)
    return 0;
  else
    return pow3[x];
}

int main()
{
  string S;
  cin >> S;
  int N = S.size();
  vector<int64_t> A(N + 1, 0), B(N + 1, 0), C(N + 1, 0), Q(N + 1, 0); // V[r+1] - V[l]
  for (int i = 0; i < N; i++)
  {
    if (S[i] == 'A')
      A[i + 1]++;
    if (S[i] == 'B')
      B[i + 1]++;
    if (S[i] == 'C')
      C[i + 1]++;
    if (S[i] == '?')
      Q[i + 1]++;
    A[i + 1] += A[i];
    B[i + 1] += B[i];
    C[i + 1] += C[i];
    Q[i + 1] += Q[i];
  }
  init();
  int64_t ans = 0;
  for (int i = 1; i < N - 1; i++)
  {
    if (S[i] == 'A' || S[i] == 'C')
      continue;
    int64_t la = A[i], lq = Q[i], rc = (C[N] - C[i + 1]), rq = (Q[N] - Q[i + 1]);

    int64_t l = ((la * POW3(lq)) % MOD + (lq * POW3(lq - 1)) % MOD) % MOD;
    int64_t r = ((rc * POW3(rq)) % MOD + (rq * POW3(rq - 1)) % MOD) % MOD;
    (ans += (l * r)) %= MOD;
  }
  cout << ans << endl;
}


Measured memory_bytes: 7480
package main

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

type Point struct {
	x float64
	y float64
}

// d: deepness of recursion
// p1, p2: points of edges
func koch(d int, p1, p2 Point) {
	if d == 0 {
		return
	}

	var s, t Point // Points equally divided into 3
	var u Point    // Vertex of equilateral triangle

	// calc point of s, u, t by using values of p1 and p2
	th := math.Pi * 60.0 / 180.0
	s.x = (2.0*p1.x + 1.0*p2.x) / 3.0
	s.y = (2.0*p1.y + 1.0*p2.y) / 3.0
	t.x = (1.0*p1.x + 2.0*p2.x) / 3.0
	t.y = (1.0*p1.y + 2.0*p2.y) / 3.0
	// rotation matrix
	u.x = (t.x-s.x)*math.Cos(th) - (t.y-s.y)*math.Sin(th) + s.x
	u.y = (t.x-s.x)*math.Sin(th) + (t.y-s.y)*math.Cos(th) + s.y

	koch(d-1, p1, s)
	fmt.Println(s.x, s.y)
	koch(d-1, s, u)
	fmt.Println(u.x, u.y)
	koch(d-1, u, t)
	fmt.Println(t.x, t.y)
	koch(d-1, t, p2)
}

func main() {
	sc := bufio.NewScanner(os.Stdin)
	var p1 = Point{
		x: 0,
		y: 0,
	}
	var p2= Point{
		x: 100,
		y: 0,
	}
	sc.Scan()
	d, _ := strconv.Atoi(sc.Text())

	fmt.Println(p1.x, p1.y)
	koch(d, p1, p2)
	fmt.Println(p2.x, p2.y)
}



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

int V[40];
int C[40];

int main()
{
	int n,x,i,j,y,z;
	cin>>n;
	int ans = 0;
	for(i=0;i<n;i++)
		cin>>V[i];
	for(i=0;i<n;i++)
		cin>>C[i];
	
	for(i=0;i<n;i++){

		ans += max(0,V[i]-C[i]);
	}
	cout<<ans;
}

Measured memory_bytes: 3616
#include <iostream>
#include <algorithm>
#include <map>
#include <vector>
#include <queue>

using namespace std;

typedef pair<int, int> P;

const int N = 100;
const int INF = 1<<28;

class S{
public:
  int p, m, c;
  S(){};
  S(int p, int m, int c) : p(p), m(m), c(c) {}
  bool operator < (const S& s) const {
    if(c == s.c) return m < s.m;
    return c > s.c;
  }
};

int n, m, L, d[N][N+1];
vector<pair<int, P> > G[N];

void dijkstra(int s){
  priority_queue<S> que;
  fill(d[0], d[N], INF);
  d[s][L] = 0;
  que.push(S(0, L, 0));
  while(!que.empty()){
    S u = que.top(); que.pop();
    if(d[u.p][u.m] < u.c) continue;
    for(int i=0;i<G[u.p].size();i++){
      int v = G[u.p][i].first;
      int cost = G[u.p][i].second.second;
      if(d[v][u.m] > d[u.p][u.m] + cost){
        d[v][u.m] = d[u.p][u.m] + cost;
        que.push(S(v, u.m, d[v][u.m]));
      }
      int nm = u.m - G[u.p][i].second.first;
      if(nm >= 0 && d[v][nm] > d[u.p][u.m]){
        d[v][nm] = d[u.p][u.m];
        que.push(S(v, nm, d[v][nm]));
      }
    }
  }
}

main(){
  while(cin >> n >> m >> L && (n|m|L)){
    for(int i=0;i<N;i++) G[i].clear();
    for(int i=0;i<m;i++){
      int a, b, d, e;
      cin >> a >> b >> d >> e;
      a--; b--;
      G[a].push_back(make_pair(b, P(d, e)));
      G[b].push_back(make_pair(a, P(d, e)));
    }
    dijkstra(0);
    int ans = INF;
    for(int i=0;i<=L;i++) ans = min(ans, d[n-1][i]);
    cout << ans << endl;
  }
}

Measured memory_bytes: 1736
import java.util.*;

public class Main{
	public static void main(String[] args){
		
		Scanner sc = new Scanner(System.in);
		int H,W;	
		int i,j;

		while(true) {
			H = sc.nextInt();
			W = sc.nextInt();
			
			if (H==0 && W==0) {
				break;
			}
			
			for (i=0 ; i<H ; i++) {
				for (j=0 ; j<W ; j++) {
					if ((i+j)%2==0) {
						System.out.printf("#");
					}else {
						System.out.printf(".");
					}
				}
				System.out.printf("\n");
			}
			System.out.printf("\n");
		}
		sc.close();
	}
	
}


Measured memory_bytes: 58300
#include <iostream>
#include <cmath>
#include <vector>
#include <string>
#include <queue>
#include <map>
#include <algorithm>
#include <numeric>

typedef long long ll;
const ll INF = 1e18;

int main(int argc, char* argv[])
{
  int x, a, b;
  std::cin >> x >> a >> b;

  if (std::fabs(x-a) < std::fabs(x-b)) {
    std::cout << 'A' << std::endl;
  } else {
    std::cout << 'B' << std::endl;
  }

  return 0;
}


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

int main(){

    int n,k;

    cin >> n >> k;
    int now=1;

    for(int i=0;i<n;i++){
        if(now*2>now+k){
            now+=k;
        }else{
            now*=2;
        }
    }

    cout << now << endl;

    return 0;
}

Measured memory_bytes: 256
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<vector>
#include<functional>
#include<algorithm>
#include<stdlib.h>
#include<string>
#include<string.h>
#define _USE_MATH_DEFINES
#include<math.h>
#include<deque>
#include<set>
#include<map>
#include<queue>
#include<list>
#include<iostream>
#include <bitset>
using namespace std;
typedef long long ll;
#define rep(i,a,b) for(auto i=a;i<b;i++)
#define all(_x) _x.begin(), _x.end()
#define r_sort(_x) sort(_x.begin(), _x.end(), std::greater<int>())
#define vec_cnt(_a, _n) (upper_bound(all(_a), _n) - lower_bound(all(_a), _n))
#define vec_unique(_a) _a.erase(std::unique(all(_a)), _a.end());
ll gcd(ll a, ll b) { return a % b == 0 ? b : gcd(b, a % b); }
//ll lcm(ll a, ll b) { return (a / gcd(a, b)) * b; }
#define INF 1 << 30
const int mod = 998244353;
ll power(ll x, ll p) { ll a = 1; while (p > 0) { if (p % 2 == 0) { x *= x; p /= 2; } else { a *= x; p--; } }return a; }
ll mpower(ll x, ll p) { ll a = 1; while (p > 0) { if (p % 2 == 0) { x = x * x % mod; p /= 2; } else { a = a * x % mod; p--; } }return a; }
ll c(ll n, ll k) { ll a = 1; rep(i, 1, k) { a *= n - i + 1; a /= i; }return a; }
ll mc(ll n, ll m) { ll k = 1, l = 1; rep(i, n - m + 1, n + 1) k = k * i % mod; rep(i, 1, m + 1) l = l * i % mod; l = mpower(l, mod - 2); return k * l % mod; }
int f[3][100001];
int main() {
	string s;
	int q, m = 0;
	cin >> s >> q;
	deque<char>ans;
	for(auto c : s)ans.push_back(c);
	rep(i, 0, q) {
		int t, f;
		char c;
		cin >> t;
		if (t == 1) {
			m = m == 0;
		}
		else {
			cin >> f >> c;
			if ((f == 2) ^ (m))ans.push_back(c);
			else ans.push_front(c);
		}
	}
	if (m)reverse(all(ans));
	rep(i, 0, ans.size()) {
		printf("%c", ans[i]);
	}
	puts("");
	return 0;
}


Measured memory_bytes: 896
#include <cstdio>
#include <vector>
#include <set>
#include <map>
#include <algorithm>
#include <math.h>
#include <queue>
#define ll long long
#define pb push_back
#define vi vector<int>
#define vl vector<ll>
#define pii pair<int,int>
#define pll pair<ll,ll>
#define f first
#define s second
#define mp make_pair
#define forn(i,n) for(int i=0;i<n;i++)

using namespace std;

int main()
{
    int h,w,n;
    scanf("%d%d%d",&h,&w,&n);
    printf("%d\n",w>h?(n-1)/w+1:(n-1)/h+1);
    return 0;
}

Measured memory_bytes: 128
#include <iostream>
#include <string>
#include <vector>
#define _USE_MATH_DEFINENS
#include <cmath>

using namespace std;

#define p(x) cout << x << endl;
#define el cout << endl;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)

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

    string s;
    cin >> s;

    int ans;

    for(int i = 0, size = s.size(); i < size; i++){
        if(s[i] == '+'){
            ans++;
        }else if(s[i] == '-'){
            ans--;
        }
    }
    p(ans);
}

Measured memory_bytes: 256
#include<stdio.h>

int main(void)
{
  char a[101],b[101],i=0,j=0,k=0;
  scanf("%s %s",a,b);
  while(a[i] != '\0')
    {
      i++;
    }
  while(b[j] != '\0')
    {
      j++;
    }
  if(i > j)
    {
      printf("GREATER\n");
      return 0;
    }
  else if(i < j)
    {
      printf("LESS\n");
      return 0;
    }
  for(;k<i;k++)
    {
      if(a[k] > b[k])
	{
	  printf("GREATER\n");
	  return 0;
	}
      else if(a[k] < b[k])
	{
	  printf("LESS\n");
	  return 0;
	}
    }
  printf("EQUAL\n");
  return 0;
}


Measured memory_bytes: 128
#include <bits/stdc++.h>
 
using namespace std;
 
#define rep(i, n) for(int i=0; i<(n); i++)
#define FOR(i, m, n) for(int i=(m);i<(n);i++)
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(),(x).end()
#define SORT(x) sort((x).begin(),(x).end())
#define RSORT(x) sort((x).rbegin(),(x).rend())
#define REVE(x) reverse((x).begin(),(x).end())
#define mp make_pair
#define pb push_back
#define chmax(x,y) x = max(x,y)

 
typedef vector<int> VI;
typedef vector<string> VS;
typedef vector<vector<int> > VVI;
typedef pair<int, int> PII;
typedef long long LL;
typedef vector<bool> VB;
typedef vector<LL> VL;
typedef vector<vector<long long>> VVLL;
typedef vector<set<int>> VSI;
const int MOD = 1e9+7;
const int INF = 1e9;
const LL LINF = 1e18;

LL Combination(LL n, LL r){
    LL num = 1;
    for(LL i = 1; i <= r; i++){
        num = num * (n - i + 1) / i;
    }
    return num;
}

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

int lcm(int a, int b)
{
   return a * b / gcd(a, b);
}
struct UnionFind {
    VI d;
    UnionFind(int n = 0): d(n,-1) {}
    int find(int x) {
        if(d[x] < 0) return x;
        return d[x] = find(d[x]);
    }
    bool unite(int x,int y) {
        x = find(x); y = find(y);
        if(x == y) return false;
        if(d[x] > d[y]) swap(x,y);
        d[x] += d[y];
        d[y] = x;
        return true;
    }
    bool same(int x,int y) { return find(x) == find(y); }
    int size(int x) { return -d[find(x)]; }
};
int deg[100005];
VI to[100005];

struct mint {
  LL x; // typedef long long ll;
  mint(LL x=0):x((x%MOD+MOD)%MOD){}
  mint operator-() const { return mint(-x);}
  mint& operator+=(const mint a) {
    if ((x += a.x) >= MOD) x -= MOD;
    return *this;
  }
  mint& operator-=(const mint a) {
    if ((x += MOD-a.x) >= MOD) x -= MOD;
    return *this;
  }
  mint& operator*=(const mint a) {
    (x *= a.x) %= MOD;
    return *this;
  }
  mint operator+(const mint a) const {
    mint res(*this);
    return res+=a;
  }
  mint operator-(const mint a) const {
    mint res(*this);
    return res-=a;
  }
  mint operator*(const mint a) const {
    mint res(*this);
    return res*=a;
  }
  mint pow(LL t) const {
    if (!t) return 1;
    mint a = pow(t>>1);
    a *= a;
    if (t&1) a *= *this;
    return a;
  }
 
  // for prime mod
  mint inv() const {
    return pow(MOD-2);
  }
  mint& operator/=(const mint a) {
    return (*this) *= a.inv();
  }
  mint operator/(const mint a) const {
    mint res(*this);
    return res/=a;
  }
};

mint f(int n) {
    if(n == 0) return 1;
    mint x = f(n/2);
    x *= x;
    if(n%2 == 1) x *= 2;
    return x;
}

mint choose(int n,int a) {
    mint x = 1, y = 1;
    rep(i,a) {
        x *= n-i;
        y *= i+1;
    }
    return x/y;
}

int main() {
    LL n,a,b;
    cin >> n >> a >> b;
    mint ans = f(n);
    ans -= 1;
    ans -= choose(n,a);
    ans -= choose(n,b);
    cout << ans.x << endl;
}


Measured memory_bytes: 2560
#include <iostream>
#include <map>
#include <algorithm>
using namespace std;
int main()
{
	int N;
	cin >> N;
	map<string, uint64_t> map;
 
	for (auto i = 0; i < N; i++) {
		string str;
		cin >> str;
		sort(str.begin(), str.end());
		map[str]++;
	}
 
	uint64_t result = 0;
	for (auto& e : map) {
		result += (e.second) * (e.second - 1) / 2;
	}
	cout << result << endl;
	return 0;
}

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

using namespace std;
#define all(a)a.begin(),a.end()
#define rep2(i,m,n) for(int i=int(m);i<int(n);i++)
#define drep2(i,m,n) for(int i=int(m-1);i>=int(n);i--)
#define rep(i,n) rep2(i,0,n)
#define drep (i,n) drep2(i,n,0)
using ll=long long;
const int INF = 1<<30;
const ll INFll =1LL<<62;
const int MOD = int(1e9)+7;

struct UnionFind{
    vector<int> d;
    UnionFind(int n=0):d(n,-1){}
    int root(int x){
        if(d[x]<0)return x;
        return d[x]=root(d[x]);
    }
    bool unite(int x,int y){
        x=root(x);y=root(y);
        if(x==y)return false;
        if(d[x]>d[y])swap(x,y);
        d[x]+=d[y];
        d[y]=x;
        return true;
    }
    bool same(int x,int y){return root(x)==root(y);}
    int usize(int x){return -d[root(x)];}
};

int main()
{
    int n,m,k;cin  >>n >>m >>k;
    vector<int> f(n,0);
    vector<int> bl[n];
    UnionFind uf(n);
    rep(i,m){
        int a,b;cin >>a >>b;
        a--;b--;
        f[a]++;f[b]++;
        uf.unite(a,b);
    }
    rep(i,k){
        int c,d;cin >>c>>d;
        c--;d--;
        bl[c].push_back(d);
        bl[d].push_back(c);
    }
    rep(i,n){
        int ans=uf.usize(i)-1-f[i];
        for(int j:bl[i]){
            if(uf.same(i,j))ans--;
        }
        cout <<ans<< " ";
    }
    cout << endl;
    return 0;
}


Measured memory_bytes: 6784
#include <iostream>
#include <vector>
#include <set>
#include <string>
#include <utility>
#include <functional>
#include <queue>
#include <cmath>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <boost/range/irange.hpp>
#include <boost/range/algorithm.hpp>
#include <boost/range/numeric.hpp>
#include <boost/multi_array.hpp>
#include <boost/math/common_factor_ct.hpp>
#include <boost/algorithm/string.hpp>
#include <boost/pending/disjoint_sets.hpp>
#include <boost/icl/interval_map.hpp>
#include <boost/graph/graph_traits.hpp>
#include <boost/graph/strong_components.hpp>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/dijkstra_shortest_paths.hpp>
#include <boost/graph/bellman_ford_shortest_paths.hpp>
#include <boost/graph/kruskal_min_spanning_tree.hpp>
#include <boost/graph/graph_utility.hpp>

#define REP(i, N) for(int i=0; i<(N); i++)
using namespace std;
using namespace boost::math;
using namespace boost::icl;

int main() {
	string S, p = "", n = "";

	cin >> S;
  
    int r = 0;
    for (auto i : S) {
      n += i;
      if (n != p) {
        r++;
        p = n;
        n = "";
      }
    }

	cout << r << endl;

	return 0;
}


Measured memory_bytes: 1152
#include <bits/stdc++.h>
using namespace std;
int main()
{
	#ifndef ONLINE_JUDGE
	freopen("input.txt","r",stdin);
	freopen("output.txt","w",stdout);
	#endif
	ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    // int t;
    // cin>>t;
    // while(t--)
    // {
    // 	cout<<"Hi"<<endl;    	
    // }
    int n;
    cin>>n;
    if(n==0)
    	cout<<"1"<<endl;
    else
    	cout<<"0"<<endl;
}


Measured memory_bytes: 3632
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define rep(i,n) for(int i=0;i<n;i++)
#define INF 10000000000000000
#define MOD 1000000007
typedef pair<int, int> P;

bool prime(int n) {
	for (int i = 2; i <= sqrt(n); i++) {
		if (n % i == 0)return false;
	}
	return n != 1;
}
int gcd(int x, int y) {
	if (y == 0)return x;
	return gcd(y, x % y);
}
int lcm(int x, int y) {
	return x / gcd(x, y) * y;
}
int mod_pow(int n, int p, int m) {
	if (p == 0) return 1;
	if (p % 2 == 0) {
		int t = mod_pow(n, p / 2, m);
		return (t * t) % m;
	}
	return n * mod_pow(n, p - 1, m) % m;
}
int extGCD(int a, int b, int& x, int& y) {
	if (b == 0) {
		x = 1;
		y = 0;
		return a;
	}
	long long d = extGCD(b, a % b, y, x);
	y -= a / b * x;
	return d;
}
int modinv(int a, int m) {
	int b = m, u = 1, v = 0;
	while (b) {
		long long t = a / b;
		a -= t * b; swap(a, b);
		u -= t * v; swap(u, v);
	}
	u %= m;
	if (u < 0) u += m;
	return u;
}

signed main() {
	int n, ans = 0;
	cin >> n;
	int d[51];
	rep(i, n) {
		cin >> d[i];
	}
	rep(i, n) {
		for (int j = i + 1; j < n; j++) {
			ans += d[i] * d[j];
		}
	}
	cout << ans << endl;

	return 0;
}


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

using namespace std;

int main() {
    // 考え方メモ
    // 9*9通りの2重ループ
    // 計算量O(9*9) -> O(1)

    int N;
    cin >> N;

    string res = "No";
    for (int i = 1; i <= 9; i++) {
        for (int j = 1; j <= 9; j++) {
            if (N == i * j) {
                res = "Yes";
            }
        }
    }

    cout << res << endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
int main() {
    int a, b, c;
    cin >> a >> b >> c;

    int n = a - b;

    if (n >= c){
        cout << 0 <<endl;
    }
    else{
        n = c - n;
        cout << n << endl;
    }
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(n);i++)
typedef  long long ll;
ll gcd(ll x,ll y){
   if(y==0) return x;
   else return gcd(y,x%y);
}
ll lcm(ll x,ll y){
   return x/gcd(x,y)*y;
}
using namespace std;
int main(){
  int k,n;
  cin>>k>>n;
  vector<int> a(n);

  rep(i,n){
     cin>>a[i];
  }
  int x=a[0]+k-a[n-1];
  rep(i,n-1){
     x=max(x,a[i+1]-a[i]);
  }
  
  cout<<k-x;

  
  
  


return 0;
}


Measured memory_bytes: 1024
#include<iostream>
#include<algorithm>
#include<vector>
#include<string>
//#include<bits/stdc++.h>
#define int long long
#define mod 1000000007
#define P pair<int,int>
using namespace std;

string a[1000];
int dp[1001][1001];
signed main() {
	int h, w; cin >> h >> w;
	for (int i = 0; i < h; i++) {
		cin >> a[i];
	}
	dp[0][0] = 1;
	for (int i = 0; i < h; i++) {
		for (int j = 0; j < w; j++) {
			dp[i][j] %= mod;
			if (a[i][j] == '#')dp[i][j] = 0;
			dp[i + 1][j] += dp[i][j];
			dp[i][j + 1] += dp[i][j];
		}
	}
	cout << dp[h - 1][w - 1] << endl;
}

Measured memory_bytes: 9088
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return true; } return false; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return true; } return false; }
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define mp make_pair
#define si(x) int(x.size())
const int mod=1000000007,MAX=1000005;
const ll INF=1LL<<60;

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

void make(){
    
    fac[0]=fac[1]=1;
    finv[0]=finv[1]=1;
    inv[1]=1;
    
    for(int i=2;i<MAX;i++){
        inv[i]=mod-inv[mod%i]*(mod/i)%mod;
        fac[i]=fac[i-1]*(ll)i%mod;
        finv[i]=finv[i-1]*inv[i]%mod;
    }
    
}

ll comb(ll a,ll b){
    if(a<b) return 0;
    return fac[a]*(finv[b]*finv[a-b]%mod)%mod;
}

ll perm(ll a,ll b){
    if(a<b) return 0;
    return fac[a]*finv[a-b]%mod;
}

int main(){
    
    std::ifstream in("text.txt");
    std::cin.rdbuf(in.rdbuf());
    cin.tie(0);
    ios::sync_with_stdio(false);
    
    make();
    int N,M;cin>>N>>M;
    ll ans=0;
    for(int i=0;i<=N;i++){
        ll p=comb(N,i)*perm(M-i,N-i)%mod;
        if(i&1) ans-=p;
        else ans+=p;
        
        if(ans<mod) ans+=mod;
        if(ans>=mod) ans-=mod;
    }
    
    ans*=perm(M,N);
    ans%=mod;
    
    cout<<ans<<endl;
}


Measured memory_bytes: 27008
N, A, B = (int(i) for i in input().split())



Sum = 0

for i in range(1, N + 1):
	Y = i
	Judge = 0

	while Y >= 1:
		Judge += Y % 10	#10で割った余り、512の場合は2、2の場合は2
		Y = int(Y // 10)	#10で割った商、512の場合は51、2の場合は0
		

	if A <= Judge and Judge <= B:
		Sum += i


print(Sum)


Measured memory_bytes: 2940
#include <cstdio>
int preorder[40],inorder[40];
void recover(int fp,int lp,int fi,int li){
	int root=fi;
	for(;root<li;root++)if(preorder[fp]==inorder[root])break;
	if(fi<root)recover(fp+1,fp+(root-fi)+1,fi,root);
	if(root<li-1)recover(fp+(root-fi)+1,lp,root+1,li);
	printf(inorder[root]==preorder[0]?"%d\n":"%d ",inorder[root]);
}
main(){
	int n,i;
	scanf("%d",&n);
	for(i=0;i<n;i++)scanf("%d",preorder+i);
	for(i=0;i<n;i++)scanf("%d",inorder+i);
	recover(0,n,0,n);
}

Measured memory_bytes: 1024
n=int(input());f=lambda x:sorted([list(map(int,input().split()))for _ in range(n)],key=lambda k:k[x]);r=f(1)[::-1];b=f(0);a=0
for c,d in b:
  for l in r:
    if c>l[0] and d>l[1]:r.remove(l);a+=1;break
print(a)

Measured memory_bytes: 3060
#include <iostream>
#include <algorithm>
#include <functional>
#include <cstdlib>
#include <sstream>
#include <string>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <complex>
#include <vector>
#include <bitset>
#include <cstdio>
#include <cmath>
#include <time.h>
#include <tuple>
#define all(c) ((c).begin(),(c).end())
#define rall(c) ((c).rbegin(),(c).rend())
#define ll long long
#define fi first
#define se second
#define inf 999999999
using namespace std;
const ll MOD = 1e9 + 7;
const double PI = acos(-1.0);
//---------------------------------------------------------------------------------------------//
int n;

inline ll power(int a, int b) {
	ll res=1;
	ll now = a;
	while (b > 0) {
		if (b & 1) {
			res *= now;
		}
		b >>= 1;
		now *= a;
	}
	return res;
}

int main() {
	while (cin >> n) {
		int a[1001];
		for (int i = 0; i < n; i++) {
			cin >> a[i];
		}
		int ans=0;
		bool b[10000];
		for (int i = 0; i < 10000; i++)b[i] = 0;
		int digit = 1;
		int now1 = 0;
		while (now1<2000) {
			for (int i = 0; i <= n - digit; i++) {
				int now = 0;
				for (int j = 0; j < digit; j++) {
					now *= 10;
					now += a[i + j];
				}
				b[now] = 1;
			}
			for (int i = 0; i < power(10, digit); i++) {
				if (b[i] == 0) {
					cout << i << endl;
					return 0;
				}
			}
			now1++;
			digit++;
		}
	}
	return 0;
}

Measured memory_bytes: 3116
import java.util.*;
public class Main {
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		// 整数の入力
		int a = sc.nextInt();
		int tmp=0;
		int[] b=new int[a]; 
		int[] c=new int [a];
		int sum=0;
		// スペース区切りの整数の入力
		for(int i=0;i<a*2;i++){
		if(i%2==0)
		 b[i/2] = sc.nextInt();
		else
		c[i/2]=sc.nextInt();
		}
		//int c = sc.nextInt();
		// 文字列の入力
		    Arrays.sort(b);
		    Arrays.sort(c);
if(a>1){
	for(int i=0;i<a-1;i++){
	   sum+=(b[i+1]-b[i]-1);
	}	
	sum+=(b[0]-1);
	sum+=c[0];
	sum+=a;
}else
sum=b[0]+c[0];
		//String s = sc.next();
		// 出力
		System.out.println(sum);
	}
}

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

using namespace std;

const int MOD = 1000000007;

int main(){
    vector<long long> inv(1000001);
	vector<long long> fact(1000001);
	vector<long long> factInv(1000001);
	for(int i=0;i<2;i++) inv[i] = fact[i] = factInv[i] = 1;
	for(int i=2;i<inv.size();i++){
		inv[i] = inv[MOD % i] * (MOD - MOD / i) % MOD;
		fact[i] = fact[i-1] * i % MOD;
		factInv[i] = factInv[i-1] * inv[i] % MOD;
	}
	auto comb = [&](int n, int r){
		if(n < r) return 0LL;
		return fact[n] * factInv[n-r] % MOD * factInv[r] % MOD;
	};
    int N;
    while(cin >> N){
        long long res = 0;
        long long sum = 0;
        --N;
        for(int i=1;i<=N;i++){
            long long c = comb(i-1, N-i);
            long long cur = c * fact[i] % MOD * fact[N-i] % MOD;
            cur = (cur + MOD - sum) % MOD;
            sum = (sum + cur) % MOD;
            res = (res + i * cur) % MOD;
        }
        cout << res << endl;
    }
}

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

int main(void){
    int a,b,k;
    cin >> a >> b >> k;
    if(a>b) swap(a,b);

    vector<int> cm;
    for(int i=a;i>=1;i--){
        if(a%i==0 && b%i==0) cm.push_back(i);
    }
    cout << cm[k-1] << endl;
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <math.h>
#include <numeric>
#include <vector>
#include <utility>
#include <algorithm>
#include <map>
#include <queue>
#include <queue>
#include <sstream>
#include <set>

typedef  long long ll;
const int dx[8]={1,0,-1,0,1,-1,-1,1};
const int dy[8]={0,1,0,-1,1,1,-1,-1};
const int dr[4] = {-1, 0, 1, 0};
const int dc[4] = { 0, 1, 0,-1};
const int INF = 1e9;
#define FOR(i, a, n) for(int i = (int)(a); i < (int)(n); ++i)
#define REP(i, n) FOR(i, 0, n)
#define SORT(a) sort(a.begin(),a.end())
#define REVERSE(a) reverse(a.begin(),a.end())
int guki (int a){
    if(a%2==0) return 0;
    else return 1;
}
int gcd(int a, int b){
    if(a%b==0){
        return b;
    }else{
        return (gcd(b,a%b));
    }
}
int lcm(int a, int b){
    int x = gcd(a,b);
    return (a*b/x);
}












const int limit = 51;
int n,m;
bool vec[limit][limit];
bool vis[limit];

void DFS(int x){
    if(vis[x]) return;

    vis[x] = true;

    REP(i,n){
        if(vec[i][x]){
            DFS(i);
        }
    }
}
using namespace std;
int main(){
    int n,ans = 0;
    cin >> n;
    vector<int> vec(n);


    REP(i,n){
        cin >> vec[i];
    }

    REP(i,n-2){
        if(vec[i] < vec[i+1] && vec[i+1] < vec[i+2]){
            ans ++;
        }else if(vec[i] > vec[i+1] && vec[i+1] > vec[i+2]){
            ans ++;
        }
    }

    cout << ans <<endl;
}

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

int main() {
  int N;
  cin >> N;
  int thousand = N/1000;
  int hundred = (N - thousand*1000)/100;
  int ten = (N - thousand*1000 - hundred*100)/10;
  int one = N - thousand*1000 - hundred*100 - ten*10;
  if( thousand == hundred && thousand == ten){
    cout << "Yes" << endl;
  }
  else if (hundred == ten && hundred == one){
    cout << "Yes" << endl;
  }
  else{
    cout << "No" << endl;
  }
}


Measured memory_bytes: 256
k,a,b=map(int,input().split())
if b<=a+2:
  print(k+1)
else:
  if k<=a:
    print(k+1)
  else:
    x=k-a-1
    if x%2==0:
      y=x//2
      ans=(y+1)*b-y*a
      print(ans)
    else:
      y=x//2
      ans=(y+1)*b-y*a+1
      print(ans)

Measured memory_bytes: 3064
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;i++)
#define all(x) (x).begin(),(x).end()
using namespace std;
const int INF=1145141919,MOD=1e9+7;
const long long LINF=8931145141919364364,LMOD=998244353;
inline long long mod(long long n,long long m){return(n%m+m)%m;}
// const int dx[]={1,0,-1,0,1,1,-1,-1},dy[]={0,-1,0,1,1,-1,-1,1};

template<class T>
struct Parser{
    typedef string::const_iterator itr;
    itr begin;
    vector<T> abcd;
    T ans;
    Parser(const string &s,const vector<T> &abcd):abcd(abcd){
        begin=s.begin();
        ans=Hash(begin);
    }
    T calc(char op,int hash1,int hash2){
        if(op=='+') return hash1|hash2;
        if(op=='*') return hash1&hash2;
        if(op=='^') return hash1^hash2;
        cerr<<"unknown"<<endl;
        return 0;
    }
    T Hash(itr &begin){
        if(*begin=='['){
            consume(begin,'[');
            char Op=*begin;
            consume(begin,Op);
            T hash1=Hash(begin);
            T hash2=Hash(begin);
            consume(begin,']');
            return calc(Op,hash1,hash2);
        }else{
            char Letter=*begin;
            consume(begin,Letter);
            return abcd[Letter-'a'];
        }
    }
    void consume(itr &begin,char expected){
        if(*begin==expected){
            begin++;
        }else{
            fprintf(stderr,"Expected: '%c' Got: '%c'\n",expected,*begin);
            fprintf(stderr,"Rest string is ");
            while(*begin){
                fprintf(stderr,"%c",*begin++);
            }
        }
    }
};

int main(){
    string s,p;
    while(cin>>s&&s!="."){
        cin>>p;
        vector<int> abcd(4);
        for(int i=0;i<4;i++) abcd[i]=p[i]-'0';
        Parser<int> pp(s,abcd);
        int cnt=0;
        for(int i=0;i<10000;i++){
            int tmp=i;
            for(int j=0;j<4;j++){
                abcd[j]=tmp%10;
                tmp/=10;
            }
            reverse(abcd.begin(),abcd.end());
            Parser<int> p1(s,abcd);
            if(pp.ans==p1.ans) cnt++;
        }
        cout<<pp.ans<<" "<<cnt<<endl;
    }
    return 0;
}



Measured memory_bytes: 3200
import sys

input = sys.stdin.readline


def main():
    N = int(input())
    a = list(map(int, input().split()))

    ans = 0
    for i in a:
        while True:
            if i % 2 == 0:
                ans += 1
                i //= 2
            else:
                break

    print(ans)


if __name__ == "__main__":
    main()


Measured memory_bytes: 4084
n = gets.to_i
s = []
n.times do |i|
  s[i] = gets.to_i
end
s.sort!
sum = s.inject(:+)
s.each do |v|
  break if sum % 10 != 0
  sum -= v if v % 10 != 0
end
puts (sum % 10 != 0) ? sum : 0


Measured memory_bytes: 1788
from collections import deque
from collections import Counter
from itertools import product, permutations,combinations
from operator import itemgetter
from heapq import heappop, heappush
from bisect import bisect_left, bisect_right, bisect
#pypyではscipy, numpyは使えない
#from scipy.sparse.csgraph import shortest_path, floyd_warshall, dijkstra, bellman_ford, johnson, minimum_spanning_tree
#from scipy.sparse import csr_matrix, coo_matrix, lil_matrix
#import numpy as np
from fractions import gcd
from math import ceil,floor, sqrt, cos, sin, pi, factorial
import sys
input = sys.stdin.readline
#文字列のときはうまく行かないのでコメントアウトすること
sys.setrecursionlimit(2147483647)

def main():
  n, m = map(int, input().split())
  ans = 0
  if n>=2:
    ans += factorial(n)/(factorial(n-2)*2)
  if m>=2:
    ans += factorial(m)/(factorial(m-2)*2)
  print(int(ans))

if __name__ == '__main__':
  main()

Measured memory_bytes: 5460
#!/usr/bin/env python3
# coding:utf-8
import math


def main():
    stdIn = int(input())
    stdOut = solve(stdIn)
    print(stdOut)


"""
方針
sを3で割った商と余りを考える
商が数列の個数の最大数
数列が1個の場合、1
数列が2個の場合、(s-3*2)+1
数列が3個の場合、3から足す必要のある数はt=(s-3*3)
t=1の時3
t=2の時6
t=3の時10
(t+2)C2
数列が4個の場合、3から足す必要のある数はt=(s-3*4)
(t+3)C3
よって、総数は、
1 + (s-3*2)+1 + (s-3*3+2)C2 + (s-3*4+3)C3 + ...
i0   i1


"""

mod = 1000000007


def solve(s):
    d = s // 3
    if d == 0:
        return 0
    total = 0
    for i in range(d):
        if i == 0:
            total += 1
            continue
        n = s - 3 * (i + 1) + i
        r = i
        c = combinations_count(n, r)
        countd = c % mod
        total += countd
        if (total > mod):
            total -= mod
    return total

# nCr


def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))


if __name__ == "__main__":
    main()


Measured memory_bytes: 9148
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll MOD = 1e9 + 7;
const ll INF = 1LL << 60;
#define rep(i, n) for (ll i = 0; i < (n); i++)
#define debug(x) cerr << #x << ": " << x << endl;
template<typename T1,typename T2> inline void chmin(T1 &a,T2 b){if(a>b) a=b;}
template<typename T1,typename T2> inline void chmax(T1 &a,T2 b){if(a<b) a=b;}

int main() {
    ll N;
    cin >> N;
    vector<ll> x(N), y(N), vec(N);
    rep(i, N) cin >> x[i] >> y[i];
    rep(i, N) vec[i] = i;

    double ans = 0;
    do {
        rep(i, N-1) ans += hypot(x[vec[i]]-x[vec[i+1]], y[vec[i]]-y[vec[i+1]]);
    } while(next_permutation(vec.begin(), vec.end()));

    rep(i, N) ans /= i+1;

    cout.precision(10);
    cout << ans << endl;
}


Measured memory_bytes: 256