akhauriyash/Code-Regression huggingface dataset:
#include<iostream>
using namespace std;
#define m long long
#define d(s,i,n) for(m i=s;i<n;i++)
m l[90][90],r[90][90];
int main(){m n;cin>>n;d(0,i,89){l[i][0]=1,r[i][0]=1;d(1,j,90){if(i==j)r[i][j]=r[i][j-1]*2+l[i][j-1];else r[i][j]=r[i][j-1]+l[i][j-1];l[i][j]=r[i][j-1];}}d(0,i,n){m a,b; cin>>a>>b;if(b>a)swap(a,b);m k=0;d(0,j,90)if(a>=r[0][j]&&b>=l[0][j])k=j;m g;if(k==0)k=1,g=1;else if(k==1)if(b==1)g=a;else g=4;else{g=1;if(b>=r[0][k]&&a>=l[0][k]&&l[0][k]!=r[0][k])g++;d(1,j,k+1)if(r[j][k]<=a&&l[j][k]<=b)g+=1+(a-r[j][k])/l[j][k];d(1,j,k+1)if(r[j][k]<=b&&l[j][k]<=a)g+=1+(b-r[j][k])/l[j][k];}cout<<k<<" "<<g%1000000007<<" ";}}

Measured memory_bytes: 4452
#include<stdio.h>
#include<iostream>
#include<algorithm>
using namespace std;
struct XYZ{
long long xxx,yyy,ddd,xx,yy,dd;
};
long long x[101],y[101],d[101];
XYZ m[50];
int main(){
int i,j,n,k,delx=0,dely=0,deld=0,r,u,cnt=0,l;
int t;
long long ans=0;
cin>>n>>k;
for(i=0;i<n;i++){
cin>>x[i*2]>>y[i*2]>>d[i*2]>>x[i*2+1]>>y[i*2+1]>>d[i*2+1];
m[i].xxx=x[i*2];
m[i].yyy=y[i*2];
m[i].ddd=d[i*2];
m[i].xx=x[i*2+1];
m[i].yy=y[i*2+1];
m[i].dd=d[i*2+1];
}
for(i=0;i<n*2;i++){
for(j=i+1;j<n*2;j++){
if(x[i]==x[j]&&x[j]<10000000){
x[j]=10000010;
delx++;
}
if(x[i]>x[j]){
t=x[i];
x[i]=x[j];
x[j]=t;
}
if(y[i]==y[j]&&y[j]<10000000){
y[j]=10000010;
dely++;
}
if(y[i]>y[j]){
t=y[i];
y[i]=y[j];
y[j]=t;
}
if(d[i]==d[j]&&d[j]<10000000){
d[j]=10000001;
deld++;
}
if(d[i]>d[j]){
t=d[i];
d[i]=d[j];
d[j]=t;
}
}
}
for(i=0;i<n*2-delx-1;i++){
for(j=0;j<n*2-dely-1;j++){
for(r=0;r<n*2-deld-1;r++){
cnt=0;
for(u=0;u<n;u++){
//cout<<"bx="<<m[u].xxx<<" x="<<x[i]<<" x+1="<<x[i+1]<<" ax="<<m[u].xx<<" by="<<m[u].yyy<<" y="<<y[j]<<" y+1="<<y[j+1]<<" ay="<<m[u].yy<<" bd="<<m[u].ddd<<" d="<<d[r]<<" d+1="<<d[r+1]<<" ad="<<m[u].dd; 
if(m[u].xxx<=x[i]&&m[u].xx>=x[i+1]&&m[u].yy>=y[j+1]&&m[u].yyy<=y[j]&&m[u].ddd<=d[r]&&m[u].dd>=d[r+1])cnt++;
//cout<<"   cnt="<<cnt<<endl;
}
if(cnt>=k)ans=ans+(x[i+1]-x[i])*(y[j+1]-y[j])*(d[r+1]-d[r]);
}
}
}
cout<<ans<<endl;
return 0;
}



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

int main()
{
    long long L, R;
    long long modv = 2019;
    cin >> L >> R;

    if ((R - L) > modv) {
        cout << "0";
        return 0;
    }
    L = L % modv;
    R = R % modv;
    while (R <= L ) {
        R += modv;
    }
    
    //            cout << L << ", " << R << endl;
    
    long long minValue = modv + 1;
    for (long long i = L; i < R; i++) {
        for (long long j = i + 1; j <= R; j++) {
            if ((i * j) % modv < minValue) {
                minValue = (i * j) % modv;
                //                cout << i << ", " << j << " = " << (i * j) % modv << endl;;
            }
        }
    }
    
    cout << minValue;
    
    return 0;
}


Measured memory_bytes: 256
//=================================
// Created on: 2018/07/04 12:13:08 => 12:37
//=================================
#include <bits/stdc++.h>
using namespace std;
constexpr int INF = 1 << 30;
struct CostGraph
{
    CostGraph(const int v) : V{v}, edge(v) {}
    struct Edge
    {
        const int from, to, cost;
    };
    void addEdge(const int from, const int to, const int cost) { edge[from].push_back(Edge{from, to, cost}); }
    const int V;
    vector<vector<Edge>> edge;
};

vector<int> Dijkstra(const CostGraph& g, const int s)
{
    vector<int> d(g.V, INF);
    using P = pair<int, int>;
    priority_queue<P, vector<P>, greater<P>> q;
    d[s] = 0, q.push({0, s});
    while (not q.empty()) {
        const int cost = q.top().first, v = q.top().second;
        q.pop();
        if (d[v] < cost) { continue; }
        for (const auto& e : g.edge[v]) {
            if (d[e.to] <= d[v] + e.cost) { continue; }
            d[e.to] = d[v] + e.cost, q.push({d[e.to], e.to});
        }
    }
    return d;
}

int main()
{
    for (int N, M, L, K, A, H;;) {
        cin >> N >> M >> L >> K >> A >> H;
        if (N == 0 and M == 0 and L == 0 and K == 0 and A == 0 and H == 0) { break; }
        const int NUM = N * (M + 1);
        CostGraph g(NUM);
        for (int l = 0, i; l < L; l++) {
            cin >> i;
            for (int j = 0; j < M; j++) { g.addEdge(i * (M + 1) + j, i * (M + 1) + j + 1, 1); }
        }
        for (int i = 0, u, v, d; i < K; i++) {
            cin >> u >> v >> d;
            for (int j = d; j <= M; j++) { g.addEdge(u * (M + 1) + j, v * (M + 1) + j - d, d), g.addEdge(v * (M + 1) + j, u * (M + 1) + j - d, d); }
        }
        const auto d = Dijkstra(g, A * (M + 1) + M);
        int ans = INF;
        for (int i = 0; i <= M; i++) { ans = min(ans, d[H * (M + 1) + i]); }
        cout << (ans == INF ? "Help!" : to_string(ans)) << endl;
    }
    return 0;
}



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

using namespace std;

long long mod=1e9+7;

int main(){
    int n;
    cin>>n;
    string str;
    cin>>str;
    int total=0;
    for(int i=0;i<n;i++){
        if(str[i]=='A' && i+1<n && str[i+1]=='B' && i+2<n && str[i+2]=='C' )
            total++;
    }
    cout<<total;
	return 0;
}



Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){
	string s;
	int k;
	cin>>k>>s;
	if(s.length()<=k)
	{
		cout<<s;
		return 0;
	}
	else
	{
		for(int i=0;i<k;i++)
		{
			cout<<s[i];
		}
		cout<<"..."<<endl;
		return 0;
	}
}

Measured memory_bytes: 3624
#include <algorithm>
#include <cmath>
#include <iomanip>
#include <ios>
#include <iostream>
#include <vector>

#define ll long long

using namespace std;

size_t N, L;
vector<string> S;

int main()
{
    cin >> N >> L;
    S.resize(N);
    for (size_t i = 0; i < N; i++) {
        cin >> S[i];
    }

    sort(S.begin(), S.end());

    for (size_t i = 0; i < N; i++) {
        cout << S[i];
    }
    cout << endl;
    return 0;
}

Measured memory_bytes: 256
#include <stdlib.h>
#include <stdio.h>
#include <time.h>
#include <math.h>
#include <iostream>
#include <string>
#include<algorithm>
#include <vector>
#include <cassert>
#include<cmath>
using namespace std;
int main() {
	int N, M;
	int i, j;
	int K[50];
	int A[50][50];
	int iter = 1;
	int res=0;
	int ans = 0;


	cin >> N >> M;

	for (i = 0; i < N; ++i) {
		cin >> K[i];
		for (j = 0; j < K[i]; ++j) {
			cin >> A[i][j];
		}
	}
	while (iter <= M) {
		for (i = 0; i < N; ++i) {

			for (j = 0; j < K[i]; ++j) {
				if (A[i][j] == iter) {
					++res;
				}
			}
		}

		if (res == N) {
			++ans;
		}
	//	cout << "res" << res << endl;
		res = 0;
		++iter;
	}

	cout << ans << endl;
}



Measured memory_bytes: 256
b,s,o,i;main(a){for(scanf("%d",&i);i<50&&~scanf("%s",&a);b=a%3?a&1?o?b:(s=!printf("%d\n",b>3?s+b-3:s)):b+1:!(s+=++b))  o=a&1?-~o%3:o;return 0;}

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

int main() {
  string s,t;
  cin >>s>>t;
  rep(i,s.size()){
    if(s[i]!=t[i]){
      cout<<"No"<<endl;
      return 0;
    }
  }
  cout<<"Yes"<<endl;
}

Measured memory_bytes: 3632
import sys
from collections import deque

read = sys.stdin.buffer.read


def main():
    MOD = 1000000007
    N, *AB = map(int, read().split())
    G = [[] for _ in range(N)]
    for a, b in zip(AB[::2], AB[1::2]):
        G[a - 1].append(b - 1)
        G[b - 1].append(a - 1)

    stack = deque([0])
    order = []
    prev = [0] * N
    prev[0] = -1
    while stack:
        v = stack.pop()
        order.append(v)
        for nv in G[v]:
            if nv != prev[v]:
                stack.append(nv)
                prev[nv] = v

    pow2 = [0] * (N + 1)
    pow2[0] = 1
    for i in range(N):
        pow2[i + 1] = pow2[i] * 2 % MOD

    nodes = [1] * N
    numer = 0

    for v in reversed(order):
        if prev[v] != -1:
            nodes[prev[v]] += nodes[v]
        numer = (numer + pow2[N - 1] - 1 - (pow2[N - nodes[v]] - 1)) % MOD
        for nv in G[v]:
            if nv != prev[v]:
                numer = (numer - (pow2[nodes[nv]] - 1)) % MOD

    denom = pow2[N]
    ans = (numer * pow(denom, MOD - 2, MOD)) % MOD
    print(ans)
    return


if __name__ == '__main__':
    main()


Measured memory_bytes: 75336
N, M = map(int, input().split())
set_a = set([int(input()) for _ in range(M)])
MOD = 10**9 + 7

dp = [0] * (N + 1)
dp[0] = 1
dp[1] = 0 if 1 in set_a else 1
for i in range(2, N+1):
    dp[i] = 0 if i in set_a else dp[i-1] + dp[i-2]
ans = dp[N] % MOD

print(ans)

Measured memory_bytes: 470264
N, M = map(int, input().split())
ans1 = 0
import math
if N <= M:
    ans1 = 0
    if 2 * N <= M:
        ans1 = N
        M -= ans1 * 2
        ans2 = math.floor(M / 4)
        print(int(ans1 + ans2))
    else:
        ans1 = math.floor(M / 2)
        print(ans1)
else:
    print(int(math.floor(M / 2)))

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

S = []
for i in range(H):
    S.append(input())

U = [[0] * W for h in range(H)]
D = [[0] * W for h in range(H)]
L = [[0] * W for h in range(H)]
R = [[0] * W for h in range(H)]

for h in range(H):
    for w in range(W):
        if S[h][w] == 1:
            continue
        # up
        if h-1 < 0 or S[h-1][w] == '#':
            U[h][w] = 0
        else:
            U[h][w] = U[h-1][w] + 1
        # left
        if w-1 < 0 or S[h][w-1] == '#':
            L[h][w] = 0
        else:
            L[h][w] = L[h][w-1] + 1

for h in range(H-1, -1, -1):
    for w in range(W-1, -1, -1):
        if S[h][w] == 1:
            continue
        # down
        if h+1 >= H or S[h+1][w] == '#':
            D[h][w] = 0
        else:
            D[h][w] = D[h+1][w] + 1
        # right
        if w+1 >= W or S[h][w+1] == '#':
            R[h][w] = 0
        else:
            R[h][w] = R[h][w+1] + 1

ans = 0
for h in range(H):
    for w in range(W):
        if S[h][w] == '#':
            continue
        cnt = U[h][w] + L[h][w] + D[h][w] + R[h][w] + 1
        if cnt > ans:
            ans = cnt

print(ans)


Measured memory_bytes: 180100
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define forn(i, n) for (ll i = 0; i < (n); i++)
#define fori(i, b, e) for (ll i = (b); i < (e); i++)
#define forr(i, b, e) for (ll i = (b); i >= (e); i--)
#define allele(v) v.begin(), v.end()
#define fi first
#define se second

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	ll r, g, b, n;
	cin >> r >> g >> b >> n;
	ll ans = 0;
	fori(x, 0, n + 1)
		fori(y, 0, n + 1)
		{
			ll tgt = (n - x * r - y * g);
			if (tgt >= 0 && tgt % b == 0)
				ans++;
		}
	cout << ans << endl;
	return 0;
}

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

int main(){
    int n, q, input, cnt=0;
    vector<int> S(0), T(0);

    cin >> n;
    for(int i=0; i<n; i++){
        cin >> input;
        S.push_back(input);
    }
    cin >> q;
    for(int i=0; i<q; i++){
        cin >> input;
        T.push_back(input);
    }

    for(vector<int>::iterator it=T.begin(); it<T.end(); it++){
        if(*lower_bound(S.begin(), S.end(), *it) == *it) cnt++;
    }

    cout << cnt << endl;

    return 0;
}


Measured memory_bytes: 3548
#include <bits/stdc++.h>
      
#define FOR(i,a,b) for( ll i = (a); i < (ll)(b); i++ )
#define REP(i,n) FOR(i,0,n)
#define YYS(x,arr) for(auto& x:arr)
#define ALL(x) (x).begin(),(x).end()
#define SORT(x) sort( (x).begin(),(x).end() )
#define REVERSE(x) reverse( (x).begin(),(x).end() )
#define UNIQUE(x) (x).erase( unique( ALL( (x) ) ) , (x).end() )
#define PW(x) (1LL<<(x))
#define SZ(x) ((ll)(x).size())
#define SHOW(x) cout << #x << " = " << x << endl
#define SHOWA(x,n) for( int yui = 0; yui < n; yui++ ){ cout << x[yui] << " "; } cout << endl

#define pb emplace_back
#define fi first
#define se second

using namespace std;

typedef long double ld;
typedef long long int ll;
typedef pair<int,int> pi;
typedef pair<ll,ll> pl;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<bool> vb;
typedef vector<ld> vd;
typedef vector<pi> vpi;
typedef vector<pl> vpl;
typedef vector<vpl> gr;
typedef vector<vl> ml;
typedef vector<vd> md;
typedef vector<vi> mi;
     
const ll INF = (ll)1e9 + 10;
const ll INFLL = (ll)1e18 + 10;
const ld EPS = 1e-12;
const ll MOD = 1e9+7;
     
template<class T> T &chmin( T &a , const T &b ){ return a = min(a,b); }
template<class T> T &chmax( T &a , const T &b ){ return a = max(a,b); }
template<class T> inline T sq( T a ){ return a * a; }

ll in(){ long long int x; scanf( "%lld" , &x ); return x; }
char yuyushiki[1000010]; string stin(){ scanf( "%s" , yuyushiki ); return yuyushiki; }

// head

int n, m;

string s[110];
int cnt[30];

int ni;

int main(){

  n = in();
  m = in();

  REP( i , n ){
    s[i] = stin();
    REP( j , m ){
      cnt[ s[i][j] - 'a' ]++;
    }
  }

  bool f = n % 2 == 0;
  bool g = m % 2 == 0;
  
  if( f && g ){
    ni = 0;
  } else if( f && !g ){
    ni = n / 2;
  } else if( !f && g ){
    ni = m / 2;
  } else {
    ni = n / 2 + m / 2;
    int c = 0;
    REP( i , 26 ){
      if( cnt[i] % 2 == 1 ){
        c++;
        cnt[i]--;
      }
    }
    if( c != 1 ){
      puts( "No" );
      return 0;
    }
  }

  REP( i , 26 ){
    if( cnt[i] % 2 == 1 ){
      puts( "No" );
      return 0;
    }
  }
  
  int c = 0;
  REP( i , 26 ){
    if( cnt[i] % 4 == 2 ){
      c++;
    }
  }
  
  if( c > ni ){
    puts( "No" );
  } else {
    puts( "Yes" );
  }
  
  return 0;
}


Measured memory_bytes: 256
import fractions
a,b,c,d=map(int,input().split())
def lcm(x, y):
    return (x * y) // fractions.gcd(x, y)
ans=b//d + b//c - (a-1)//c - (a-1)//d - b//lcm(c,d) + (a-1)//lcm(c,d)
ans=b-a+1-ans
print(ans)

Measured memory_bytes: 5048
#include<bits/stdc++.h>
using namespace std;
const int inf=1<<30;
int dp[12][200005],p[12],c[12];
int read() {
	char c=getchar(); int x=0,f=1;
	while (c<'0' || c>'9') {
		if (c=='-') f=-1;
		c=getchar();
	}
	while (c>='0' && c<='9') {
		x=x*10+c-'0';
		c=getchar();
	}
	return x*f;
}
int main() {
	int d=read(),g=read(),s=0;
	g/=100;
	for (int i=1; i<=d; i++) {
		p[i]=read();
		c[i]=read();
		c[i]/=100;
		s+=p[i]*i+c[i];
	}
	for (int i=0; i<=d; i++) {
		for (int j=0; j<=s; j++) {
			dp[i][j]=inf;
		}
	}
	int mx=0;
	dp[0][0]=0;
	for (int i=1; i<=d; i++) {
		for (int j=0; j<p[i]; j++) {
			for (int k=0; k<=mx; k++) {
				dp[i][k+j*i]=min(dp[i][k+j*i],dp[i-1][k]+j);
			}
		}
		for (int k=0; k<=mx; k++) {
			dp[i][k+p[i]*i+c[i]]=min(dp[i][k+p[i]*i+c[i]],dp[i-1][k]+p[i]);
		}
		mx+=p[i]*i+c[i];
	}
	int ans=inf;
	for (int k=g; k<=mx; k++) ans=min(ans,dp[d][k]);
	printf("%d\n", ans);
	return 0;
}

Measured memory_bytes: 7680
#include<bits/stdc++.h>
#define ll long long
using namespace std;
int main()
{
    ll n;
    cin>>n;
    ll sum=0;
    for(int i=1;;i++)
    {
        sum+=i;
        if(sum>=n)
        {
            cout<<i<<endl;
            return 0;
        }
    }
}


Measured memory_bytes: 256
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

S = list(input().strip())
K = int(input())

L = [i for i in S]


if len(S) == 1:
    if K == 1:
        print(0)
    else:
        print(K//2)
    sys.exit()

count = 0
tmp = S[0]
for i in range(1, len(S)):
    if S[i] == tmp:
        count += 1
        S[i] = "A"
        tmp = S[i]
    else:
        tmp = S[i]

count2 = 0
if S[0] == S[-1]:
    L[0] = "A"
    count2 += 1
    tmp = L[0]
    for i in range(1, len(L)):
        if L[i] == tmp:
            count2 += 1
            L[i] = "A"
            tmp = L[i]
        else:
            tmp = L[i]
    if L[-1] == "A":
        print((K//2)*count2 + (K//2+K%2)*count)
    else:
        print(count + (K-1)*count2)
else:
    print(count * K)

Measured memory_bytes: 38256
#include<iostream>
#include<algorithm>
#include<vector>
#define int long long
using namespace std;
signed main() {
	int mx = 3000;
	int n,m,k;
	cin >> n >> m >> k;
	vector<int> sc(n,0);
	vector<int> a(m);
	vector<int> b(m);
	vector<int> l(m);
	vector<int> ma(m);
	for (int i = 0; i < m; i++) {
		cin >> a[i] >> b[i] >> l[i];
		a[i]--; b[i]--;
		sc[a[i]]++;
		sc[b[i]]++;
	}
	vector<vector<int> > hy(n);
	for (int i = 0; i < n; i++) {
		vector<int> ze(sc[i]);
		hy[i] = ze;
	}
	vector<int> co(n, 0);
	for (int i = 0; i < m; i++) {
		int a1 = a[i];
		int b1 = b[i];
		hy[a1][co[a1]] = i;
		hy[b1][co[b1]] = i;
		co[a1]++;
		co[b1]++;
	}
	vector<int> dis(n, mx*mx);
	vector<int> ne(n,0);
	vector<int> nne(n);
	vector<int> ze(n, 0);
	vector<int> alch(n, 0);
	int to = 0;
	for (int i = 0; i < k; i++) {
		int x;
		cin >> x;
		x--;
		dis[x] = 0;
		ne[to] = x;
		to++;
	}
	while (0 < to) {
alch=ze;
		int qto = 0;
		nne = ze;
		for (int i = 0; i < to; i++) {
			int x = ne[i];
			for (int j = 0; j < sc[x]; j++) {
				int num = hy[x][j];
				int y = a[num] + b[num] - x;
				if (dis[y] > dis[x] + l[num]) {
					dis[y] = dis[x] + l[num];
					if (alch[y] == 0) {
						nne[qto] = y;
						qto++;
						alch[y] = 1;
					}
				}
			}
		}
		ne = nne;
		to = qto;
	}
	int ans = 0;
	for (int i = 0; i < m; i++) {
		int x = a[i];
		int y = b[i];
		ans = max(ans, (dis[x] + dis[y] + l[i] + 1) / 2);
	}
	cout << ans << endl;
}



Measured memory_bytes: 8080
#include<iostream>
#include<algorithm>
#include<cmath>
#include<string>
#include<vector>
#include<set>
using namespace std;

int main(){
    int N; cin>>N;
    int X[200000],Y[200000];
    for(int i=0;i<N;i++)cin>>X[i];
    for(int i=0;i<N;i++)Y[i]=X[i];
    sort(X,X+N);
    int med1=X[N/2];
    int med2=X[N/2-1];
    for(int i=0;i<N;i++){
        if(Y[i]<X[N/2])cout<<med1<<endl;
        else cout<<med2<<endl;
    }
    return 0;
}

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

int main() {
  int a,b,c,d,e,f;cin >> a >> b;
  c = a+b;
  d = a-b;
  e = a*b;
  f = max(c,d);
  f = max(f,e);
  cout << f << endl;
}

Measured memory_bytes: 256
#include <stdio.h>

int main()
{
    long long k,a,b,ans = 0;
    scanf("%lld %lld %lld",&k,&a,&b);

    if(2 >= b - a)
    {
        printf("%lld",k + 1);
    }
    else
    {
        ans += a;
        k -= a - 1;

        ans += (b - a) * (k / 2) + (k % 2);
        printf("%lld",ans);
    }
    
}

Measured memory_bytes: 128
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>

#include <iostream>
#include <complex>
#include <string>
#include <algorithm>
#include <numeric>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>

#include <functional>
#include <cassert>

typedef long long ll;
using namespace std;

#ifndef LOCAL
#define debug(x) ;
#else
#define debug(x) cerr << __LINE__ << " : " << #x << " = " << (x) << endl;

template <typename T1, typename T2>
ostream &operator<<(ostream &out, const pair<T1, T2> &p) {
  out << "{" << p.first << ", " << p.second << "}";
  return out;
}

template <typename T>
ostream &operator<<(ostream &out, const vector<T> &v) {
  out << '{';
  for (const T &item : v) out << item << ", ";
  out << "\b\b}";
  return out;
}
#endif

#define mod 1000000007 //1e9+7(prime number)
#define INF 1000000000 //1e9
#define LLINF 2000000000000000000LL //2e18
#define SIZE 200010

/* UnionFind */

struct UnionFind{
  vector<int> data;
  vector<ll> sum, sum2, sum3;
  vector<priority_queue<pair<int,pair<int,int> > > > pqs;

  UnionFind(int s):data(s, -1), sum(s, 0), sum2(s), sum3(s), pqs(s) {}

  int root(int x){
    if(data[x] < 0) return x;
    return data[x] = root(data[x]);
  }

  bool set(int x, int y){
    x = root(x); y = root(y);
    if(x == y) return false;
    data[x] += data[y];
    sum[x] += sum[y];
    sum2[x] += sum2[y];
    sum3[x] += sum3[y];

    while(pqs[y].size()) {
      pqs[x].push(pqs[y].top());
      pqs[y].pop();
    }

    data[y] = x;
    sum[y] = sum2[y] = 0;
    return true;
  }

  bool check(int x, int y){
    return root(x) == root(y);
  }

  int size(int x){
    return -data[root(x)];
  }
};



int main(){
  int n, m;
  int x[SIZE];
  vector<pair<int,pair<int,int> > > vec;

  scanf("%d%d", &n, &m);

  UnionFind uf(n);

  for(int i=0;i<n;i++){
    scanf("%d", x+i);
    uf.sum[i] = x[i];
  }

  for(int i=0;i<m;i++){
    int a, b, y;
    scanf("%d%d%d", &a, &b, &y);
    vec.push_back({y, {a-1, b-1}});
  }

  sort(vec.begin(), vec.end());

  int ans = 0;

  for(int i=0;i<m;i++){
    int a = vec[i].second.first;
    int b = vec[i].second.second;
    int y = vec[i].first;

    uf.set(a, b);

    int r = uf.root(a);

    auto &pq = uf.pqs[r];
    uf.sum3[r]++;

    pq.push({-y, {a, b}});

    while(pq.size()){
      if(uf.sum[r] >= -pq.top().first)
        pq.pop();
      else
        break;
    }

    if(pq.size() == 0) {
      ans += uf.sum3[r] - uf.sum2[r];
      debug(uf.sum2[r]);
      debug(uf.sum3[r]);
      uf.sum2[r] = uf.sum3[r];
    }

  }

  cout << m - ans << endl;


  return 0;
}


Measured memory_bytes: 247412
import math

r = 999999
sqrt = int(math.sqrt(r))
prime = [1 for i in range(r)]
prime[0] = 0
for i in range(2,r/2):
    prime[2*i-1] = 0
for i in range(3,sqrt,2):
    for j in range(2*i,r+1,i):
        prime[j-1] = 0

while True:
    try:
        n = int(raw_input())
        print sum(prime[:n])
    except:
        break

Measured memory_bytes: 43964
n=int(input())
A=[]
B=[]
for i in range(n):
    a,b=map(int,input().split())
    A.append(a)
    B.append(b)

A.sort()
B.sort()

if n%2==1:
    print(B[n//2]-A[n//2]+1)
else:
    print(int(((B[n//2]+B[n//2-1])/2-(A[n//2]+A[n//2-1])/2)*2+1))



Measured memory_bytes: 104796
#include <stdio.h>
main(){
  int i,j,n,x,y,b,m,c,a[21][21];
  char com[2];
  while(1){
    for(i=0;i<=20;i++){
      for(j=0;j<=20;j++){
	a[i][j]=0;
      }
    }
    scanf("%d",&n);
    if(n==0) break;
    for(i=0;i<n;i++){
      scanf("%d%d",&x,&y);
      a[x][y]=1;
    }
    
    x=10;
    y=10;
    c=0;
    scanf("%d",&m);
    for(i=0;i<m;i++){
      scanf("%s%d",com,&b);
      if(com[0] == 'N'){
	for(j=0;j<b;j++){
	  y++;
	  if(a[x][y] == 1){
	    c++;
	    a[x][y]=0;
	  }
	}
      }
      if(com[0] == 'S'){
	for(j=0;j<b;j++){
	  y--;
	  if(a[x][y] == 1){
	    c++;
	    a[x][y]=0;
	  }
	}
      }
      if(com[0] == 'E'){
	for(j=0;j<b;j++){
	  x++;
	  if(a[x][y] == 1){
	    c++;
	    a[x][y]=0;
	  }
	}
      }
      if(com[0] == 'W'){
	for(j=0;j<b;j++){
	  x--;
	  if(a[x][y] == 1){
	    c++;
	    a[x][y]=0;
	  }
	}
      }
    }
    if(c == n) printf("Yes\n");
    else printf("No\n");
  }
  return 0;
}

Measured memory_bytes: 0
#include <bits/stdc++.h>
#include <math.h>
#define rep(i, n) for(int i = 0; i < (n); i++)
#define rrep(i, n) for(int i = 0; i <= (n); i++)
using namespace std;
typedef long long ll;
 
const ll INF = 1LL<<62;
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; }
// 多次元 vector 生成
template<class T>
vector<T> make_vec(size_t a){
    return vector<T>(a);
}
template<class T, class... Ts>
auto make_vec(size_t a, Ts... ts){
  return vector<decltype(make_vec<T>(ts...))>(a, make_vec<T>(ts...));
}

using Graph = vector<vector<int>>;

typedef pair<int, int> P;
typedef priority_queue<int, vector<int>, greater<int>> PQ;
const int MOD = 1000000007;

bool comp(pair<int,int> a, pair<int,int> b){
    return a.second < b.second;
}

int main(){
    int N; cin >> N;
    vector<pair<int, int>> AB;
    rep(i,N){
        int a,b;
        cin >> a >> b;
        AB.emplace_back(a,b);
    }

    sort(AB.begin(), AB.end(), comp);

    int time = 0;
    rep(i,N){
        time += AB[i].first;
        if (time > AB[i].second){
            cout << "No" << endl;
            return 0;
        }
    }
    cout << "Yes" << endl;
    
}



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

int main(){
    int n,cntn = 0;
    cin >> n;
    ll s = 0;
    vector<ll> a(n);
    for(int i = 0;i < n;i ++){
        cin >> a[i];
        s += abs(a[i]);
        if(a[i]<0) cntn ++;
    }

    sort(a.begin(),a.end());

    if(cntn==n) cout << s+2*a.back() << endl;
    else if(cntn) cout << s << endl;
    else cout << s-2*a[0] << endl;

    for(int i = 0;i < n-1;i ++){
        if(cntn==0){
            if(i<n-2){
                cout << a[0] << " " << a[n-1-i] << endl;
                a[0] -= a[n-1-i];
            }else cout << a[1] << " " << a[0] << endl;
        }else if(cntn<n){
            if(n-1-i>cntn){
                cout << a[0] << " " << a[n-1-i] << endl;
                a[0] -= a[n-1-i];
            }else{
                cout << a[cntn] << " " << a[n-2-i] << endl;
                a[cntn] -= a[n-2-i];
            }
        }else{
            cout << a.back() << " " << a[i] << endl;
            a.back() -= a[i];
        }
    }
    return 0;
}

Measured memory_bytes: 2688
function Main(input) {
  input = input.split(" ");
  const n = parseInt(input[0],10);
  const a = parseInt(input[1],10);
  const b = parseInt(input[2],10);
  let ans = 0;
  let end = 0;
  for (var n_i = 0; n_i <= n; n_i++) {
    let n_i_sum = intsum(n_i);
    if ((n_i_sum >= a) && (n_i_sum <= b)) {
      ans += n_i;
    }
  }
  console.log(ans);
}

function intsum(n) {
  if (n <= 0) {
    return n;
  }
  return (n % 10) + intsum(Math.floor(n/10));
}

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


Measured memory_bytes: 31700
#include <iostream>
using namespace std;
int main()
{
  int a,b,c;
  cin>>a>>b>>c;
  if(a>b)
    if(b>c)
      cout<<c<<' '<<b<<' '<<a;
    else if(c>a)
      cout<<b<<' '<<a<<' '<<c;
    else
      cout<<b<<' '<<c<<' '<<a;
  else
    if(c<a)
      cout<<c<<' '<<a<<' '<<b;
    else if(c<b)
      cout<<a<<' '<<c<<' '<<b;
    else
      cout<<a<<' '<<b<<' '<<c;
  cout<<endl;
}

Measured memory_bytes: 3092
#include <bits/stdc++.h>
using namespace std;
typedef long long int LL;

template <typename T>
ostream& operator <<(ostream& out, const vector<T>& vec) {
    out << "[";
    for (int x : vec) out << x << ", ";
    out << "]";
    return out;
}

#if DEBUG && !ONLINE_JUDGE
    ifstream input_from_file("input.txt");
    #define cin input_from_file
    #define dbg_var(x) cerr << #x << ": " << x << endl;
#endif


int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    string s;
    cin >> s;
    int n = s.size();
    if(n < 26){
        char c = 'a';
        while(1){
            bool ok = true;
            for(char d:s) if(c == d) {c++; ok = false; break;}
            if(ok)break;
        }
        //~ dbg_var(c);
        cout << s << c << '\n';
        return 0;
    }
    int pos[300];
    for(int i=0; i<n; i++){
        pos[(int)s[i]] = i;
    }
    
    for(int i=n-1; i>=0; i--){
        char c = s[i] + 1;
        while(c <= 'z'){
            if(pos[(int)c] > i){
                for(int j=0; j<i; j++) cout << s[j];
                cout << c << '\n';
                return 0;
            }
            c++;
        }
    }
    cout << "-1\n";
}


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

int main()
{
    int n, m;
    cin >> n >> m;
    vector<int> a(m);
    vector<int> b(m);
    int ans = 0;

    for (auto i = 0; i < m; i++)
    {
        int a_i, b_i;
        cin >> a_i >> b_i;
        a_i -= 1;
        b_i -= 1;
        a[i] = a_i;
        b[i] = b_i;
    }

    for (auto i = 0; i < m; i++)
    {
        vector<bool> visited(n, false);
        vector<vector<int>> graph(n, vector<int>());
        for (auto j = 0; j < m; j++)
        {
            if (j == i)
            {
                continue;
            }
            graph[a[j]].push_back(b[j]);
            graph[b[j]].push_back(a[j]);
        }

        queue<int> qu;
        qu.push(0);

        while (!qu.empty())
        {
            int now = qu.front();
            qu.pop();
            visited[now] = true;
            for (auto i = 0; i < graph[now].size(); i++)
            {
                if(!visited[graph[now][i]]){
                    qu.push(graph[now][i]);
                }
            }
            
        }

        bool isConnected = true;
        for (auto j = 0; j < n; j++)
        {
            if(!visited[j]){
                isConnected = false;
                break;
            }
        }

        if(!isConnected){
            ans += 1;
        }
        
    }
    cout << ans << endl;
}

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

template<class T> inline bool chmax(T &a, T b)
{
    if(a < b)
    {
        a = b;
        return true;
    }
    return false;
}

template<class T> inline bool chmin(T &a, T b)
{
    if(a > b)
    {
        a = b;
        return true;
    }
    return false;
}

const ll INF = 1LL << 60;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    ll n, w;
    cin >> n >> w;
    vector<pll> wvs;
    ll naxv = 0;
    for(int i=0; i<n; i++)
    {
        ll wi, vi;
        cin >> wi >> vi;
        wvs.emplace_back(wi, vi);
        naxv += vi;
    }

    vector<vector<ll>> dp(n+1, vector<ll>(naxv+1, INF));
    dp.at(0).at(0) = 0;
    for(int i=1; i<=n; i++)
    {
        pll wv = wvs.at(i-1);
        for(int j=0; j<=naxv; j++)
        {
            if(j >= wv.second) dp.at(i).at(j) = min(dp.at(i-1).at(j), dp.at(i-1).at(j-wv.second) + wv.first);
            else dp.at(i).at(j) = dp.at(i-1).at(j);
        }
        // for(auto &num : dp.at(i))
        // {
        //     if(num == 1LL << 60) cout << "INF ";
        //     else cout << setw(3) << num << ' ';
        // }
        // cout << '\n';
    }
    ll ans = 0;
    for(int i=0; i<=naxv; i++)
    {
        if(dp.at(n).at(i) <= w) ans = i;
    }
    cout << ans << '\n';

    return 0;
}


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

int main(void) {
  ll N;
  cin >> N;
  vector<ll> A(N), B(N);
  REP(i, 0, N) cin >> A[i];
  REP(i, 0, N) cin >> B[i];

  ll sa = 0, sb = 0;
  REP(i, 0, N) {
    sa += A[i];
    sb += B[i];
  }

  if (sa < sb) {
    cout << -1 << endl;
    return 0;
  }

  vector<ll> d(N);
  REP(i, 0, N) d[i] = A[i] - B[i];
  sort(d.begin(), d.end());

  vector<bool> b(N);
  for (ll i = 0, j = N - 1;; i++) {
    if (d[i] >= 0) break;
    while (d[i] < 0) {
      ll x = min(-d[i], d[j]);
      d[i] += x;
      d[j] -= x;
      b[i] = true;
      b[j] = true;
      if (d[j] == 0) j--;
    }
  }

  ll ans = 0;
  REP(i, 0, N) if (b[i]) ans++;
  cout << ans << endl;
}

Measured memory_bytes: 2560
/*
 *
 *   Author     : Amit Kumar
 *   Date    	: August 10
 * 
 */

#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <memory.h>
#include <cassert>
#define FAST_INPUT_OUTPUT
//#define MORE_THAN_ONE_TESTCASE // COMMENT IT

#define vi vector<int>
#define vl vector<long long>
#define mii map<int , int>
#define mll map<long long , long long>
#define msi map<string , i>
#define msl map<string , long long>
#define umii unordered_map<int,int>
#define umll unordered_map<long long ,long long>
#define umsi unordered_map<string , int>
#define umsl map<string , long long> 
#define si set<int>
#define sl set<long long>
#define pii pair<int , int >
#define psi pair<string,int>
#define psl pair<string , long > 
#define pll pair<long long , long long>
#define vpii vector<pii>
#define vpll vector<pll>
#define vpsi vector<psi>
#define vpsl vector<psl>
#define pqi priority_queue<int>
#define pql priority_queue<long long>
#define ub upper_bound
#define lb lower_bound
#define bint long long int
#define ff first
#define ss second
#define all(x) x.begin(),x.end()
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define iv(v) for(auto &i:v){cin>>i;}
#define ov(v) for(auto i:v){cout<<i<<" ";}cout<<endl;
#define ovn(v) for(auto i:v){cout<<i<<endl;}
#define euv(v) for(auto i:v){cerr<<i<<" ";}cerr<<endl;
#define eovn(v) for(auto i:v){cerr<<i<<endl;}
#define os(s) for(auto itr:s){cout<<itr<<" ";}cout<<endl;
#define osn(s) for(auto itr:s){cout<<itr<<endl;}
#define eos(s) for(auto itr:s){cerr<<itr<<" ";}cerr<<endl;
#define eosn(s) for(auto itr:s){cerr<<itr<<endl;}
#define rep(x) for(auto i=0 ; i<(x); ++i)
#define _rep(a,b) for(auto i=(a); i<(b); ++i)
#define ef else if
#define wh while
#define el else
#define ivv(x) int x; cin>>x
#define lv(x) bint x; cin>>x
#define sv(x) string x; cin>>x
#define cv(x) char x; cin>>x
#define fv(x) float x; cin>>x
#define dv(x) double x; cin>>x
#define endl '\n'
using namespace std;




auto SOLUTION_FUNCTION( void ) ->void {

    // your solution goes here 

    ivv(n);
    map<string,bint>m;
    while(n--){
        sv(s);
        sort(all(s));
        m[s]++;
    }
    bint counter=0;
    for(auto itr=m.begin();itr!=m.end();++itr){
        counter+=(itr->ss*(itr->ss-1LL))/2LL;
    }
    cout<<counter<<endl;

    return ;
}




int main(void){
#ifdef FAST_INPUT_OUTPUT
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    cout<<setprecision(10);
    cout<<fixed;
    cout<<boolalpha;
#endif
#ifdef MY_LOCAL_PROJECT
    freopen("input","r",stdin);
    freopen("output","w",stdout);
#endif
    int testcase = 1;


#ifdef MORE_THAN_ONE_TESTCASE
    cin>>testcase;
#endif
    
    while(testcase--){
        SOLUTION_FUNCTION();
    }

#ifdef MY_LOCAL_PROJECT
    cout<<"Time : "<<1.0*(double)clock()/CLOCKS_PER_SEC<<endl;
#endif
    return 0;
}

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

int main()
{
    int n,k,x,ans = 0;
    cin >> n >> k;
    for(int i = 0; i < n; i++){
        cin >> x; 
        ans += min(x*2,abs(k-x)*2);
    }

    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 256
import math

A,B,H,M = map(int, input().split())

angle = abs(M*6-(H*30+M*0.5))
if angle > 180: angle=360-angle

angle_2 = math.radians(angle)

C = A**2 + B**2 -2*A*B*math.cos(angle_2)
C = C**0.5
print(C)

Measured memory_bytes: 9500
#include <iostream>
#include <string>

using namespace std;

int main()
{
    bool possibility = false;
    string str1, str2;
    getline(cin, str1);
    getline(cin, str2);

    for(size_t i = 0; i < str1.length(); i++)
    {
        if(str1[i] == str2[0])
        {
           if(str1.length() - i >= str2.length())
           {
               if(str1.substr(i, str2.length()) == str2)
               {
                   possibility = true;
                   break;
               }
           }
           else
           {
               if(str1.substr(i) + str1.substr(0, str2.length() - str1.length() + i) == str2)
               {
                   possibility = true;
                   break;
               }
           }
        }
    }


    if(possibility){ cout << "Yes" << endl; }
    else           { cout << "No"  << endl; }

    return 0;
}

Measured memory_bytes: 3240
//
//  ROIGold.cpp
//  Main calisma
//
//  Created by Rakhman on 05/02/2019.
//  Copyright © 2019 Rakhman. All rights reserved.
//

#include <cstring>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <queue>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <cassert>
#include <iterator>

#define ios ios_base::sync_with_stdio(0), cout.tie(0), cin.tie(0);
#define S second
#define F first
#define pb push_back
#define nl '\n'
#define NL cout << '\n';
#define EX exit(0)
#define all(s) s.begin(), s.end()
#define FOR(i, start, finish, k) for(int i = start; i <= finish; i += k)

const int MXN = 2e5 + 5;
const long long MNN = 1e5 + 1;
const long long MOD = 1e9 + 7;
const long long INF = 1e18;
const int OO = 1e9 + 500;

typedef long long llong;
typedef unsigned long long ullong;

using namespace std;

string s;
llong ans, sum;
map<char, int> mp;

int main(){
    ios;
    cin >> s;
    for(int i = 0; i < s.size(); i++){
        mp[s[i]]++;
        sum++;
    }
    for(int i = 0; i < s.size(); i++){
        mp[s[i]]--;
        sum--;
        ans += (sum - mp[s[i]]);
    }
    cout << ans + 1;
    return 0;
}


/*
 //    cin >> n;
 //    for(int i = 1; i <= n; i++){
 //        cin >> p[i].F;
 //    }
 //    for(int i = 1; i <= n; i++){
 //        cin >> p[i].S;
 //    }
 //    sort(p + 1, p + n + 1);
 //    for(int i = 1; i <= n; i++){
 //        if(p[i].F == p[i - 1].F && i != 1){
 //            st.insert(p[i].F);
 //        }
 //    }
 //    for(int i = 1; i <= n; i++){
 //        for(set<llong> :: iterator it = st.begin(); it != st.end(); it++){
 //            llong x = *it;
 //            if((x | p[i].F) == x){
 //                //cout << p[i].F << ' ' << x << ' ' << (x | p[i].F) << nl;
 //                ans += p[i].S;
 //                break;
 //            }
 //        }
 //    }
 //    cout << ans;
 */


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

int main()
{
	int a[50] = {1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51};
	
	int k;
	cin >> k;
	
	cout << a[k-1] << endl;
	
	return 0;
}


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

import io
import sys
import math

CASES = "abcdefghijklmnopqrstuvwxyz"

def format_multi_line_answer(lst):
    ans = ""
    ans += f"{len(lst)}\n"  # Line count
    for y in lst:
        ans += f"{y}\n"
    return ans

# アンバランス文字列には、"aa"または"axa"のような部分が現れる。
def is_unballance(s):
    if len(s) == 2 and s[0] == s[1]:
        return True
    if len(s) == 3 and s[0] == s[2]:
        return True
    return False

def solve(s):
    # implement process
    ans_l = []
    has_unbalance = False
    a,b = -1,-1
    for c in CASES:
        i = s.find(c)
        ii = s.find(c,i+1)
        while ii != -1:
            if ii - i < 3 and is_unballance(s[i:ii+1]):
                a,b = i+1,ii+1
                has_unbalance = True
                break
            i = ii
            ii = s.find(c,i+1)

        if has_unbalance:
            break
    return f"{a} {b}"

def main():
    # input
    s = input()
    # process
    ans = str( solve(s) )
    
    # output
    print(ans)
    return ans
        
### DEBUG I/O ###
_DEB = 0   # 1:ON / 0:OFF

_INPUT = """\
abcaxa
"""
_EXPECTED = """\
2 5
"""

def logd(str):
    """usage:
    if _DEB: logd(f"{str}")
    """
    if _DEB: print(f"[deb] {str}")

### MAIN ###
if __name__ == "__main__":
    if _DEB:
        sys.stdin = io.StringIO(_INPUT)
        print("!! Debug Mode !!")

    ans = main()

    if _DEB:
        print()
        if _EXPECTED.strip() == ans.strip(): print("!! Success !!")
        else: print(f"!! Failed... !!\nANSWER:   {ans}\nExpected: {_EXPECTED}")

Measured memory_bytes: 9320
#include <bits/stdc++.h>
#define ll long long
#define vi vector <int>
#define vl vector <ll>
#define dl pair <ll, ll>
#define ii pair <ll, ll>
#define vii vector <ii>
#define graph vector <vector <int> >
#define REP(a, b) for (int i = a; i < b; i++)
#define REP2(a, b) for (int j = a; j < b; j++)
#define REPS(a, b, c) for (int i = a; i < b; i += c)
#define mod 1000000007

using namespace std;
 
int main() {
    ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
 
    ll n;
    cin >> n;
    ll ans = 1;
    for (ll i = 0; i < n; i++) {ans *= 10; ans %= mod;}
    ll temp1 = 1; //no llevan ni 9 ni 0
	ll temp2 = 1; //llevan 9 o 0
	ll temp3 = 1; //levan exactamente un 9 o un cero
	for (ll i = 0; i < n; i++) {temp1 *= 8; temp1 %= mod;}
	for (ll i = 0; i < n; i++) {temp2 *= 9; temp2 %= mod;}
	temp3 = ((temp2 - temp1 + mod) * 2) % mod;
	ans = (ans - temp1 + mod - temp3 + mod) % mod;
    cout << ans << "\n";
    return 0;
}

Measured memory_bytes: 3604
// @flow

const main = (input /*: string */) => {
  const r = reader(input)
  const [m1, d1] = r.ns()
  // const [m2, d2] = r.ns()
  console.log(Number(lastDay(m1) === d1))
}
const lastDay = m => ({ '2': 28 }[m] || 30 + ((m >> 3) ^ (m & 1)))

// const values = obj => Object.keys(obj).map(e => obj[e]);

const reader = (str /*: string*/) => {
  const lines = str.trim().split('\n')
  const s = () => lines.shift() || ''
  const n = () => Number(s())

  const ss = () => s().split(' ')
  const ns = () => ss().map(v => Number(v))
  return { lines, s, n, ss, ns }
}

const getInput = () => require('fs').readFileSync('/dev/stdin', 'utf8')
main(getInput())


Measured memory_bytes: 7372
#include <bits/stdc++.h>
#define int long long
#define uint unsigned int
#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, a, b) for (int i = (a); i < (b); ++i)
#define FORR(i, a, b) for (int i = (a); i >= (b); --i)
#define ALL(a) (a).begin(), (a).end()
#define ALLR(a) (a).rbegin(), (a).rend()
#define SZ(a) ((int)(a).size())
#define PB(a) push_back(a)
#define EMP emplace
#define EMPB(...) emplace_back(__VA_ARGS__)
#define MP(a, b) make_pair(a, b)
#define MT(...) make_tuple(__VA_ARGS__)
#define Bit(n) (1LL << (n))
using namespace std;
using pii = pair<int, int>;
template <class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
template <class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
const int MOD = 1000000007;
const int INF = 1LL << 30;
const double EPS = 1e-10;

int N;
int a[110][110];

signed main() {
  cin.tie(0);
  ios_base::sync_with_stdio(false);
  cout << fixed << setprecision(10);
  
  cin >> N;
  REP(i, N) {
    int h;
    cin >> h;
    REP(j, h) a[i][j] = 1;
  }
  int ans = 0;
  REP(j, 110) {
    int flag = -1;
    REP(i, N) {
      if (flag < 0 && a[i][j]) {
        ans++; 
        flag = 1;
      } else if (!a[i][j]) {
        flag = -1;
      }
    }
  }
  cout << ans << endl;

  return 0;
}

Measured memory_bytes: 384
(defvar *days*
  '("SUN" "MON" "TUE" "WED" "THU" "FRI" "SAT"))

(defun solve (s)
  (- 7 (position s *days* :test 'equal)))

#-swank
(let ((s (read-line)))
  (format t "~A~%" (solve s)))


Measured memory_bytes: 3684
#include <iostream>
#include <string>
#include <utility>
#include <algorithm>
#include <map>
#include <vector>
#include <cmath>
#include <cstdlib>
#include <queue>
#include <numeric>
#include <set>

using namespace std;

#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 FORR(i, m, n) for(int i = m;i >= n;i--)
#define REPO(i, n) for(int i = 1;i <= n;i++)
#define INF 999999999
#define MINF -999999999
#define ALL(n) n.begin(),n.end()
#define ll long long
#define MOD 1000000007

ll dp[1100][1100];
int main() {
	dp[0][0] = 1;
	int h, w;
	string s[1100];
	cin >> h >> w;
	REP(i, h)cin >> s[i];
	REP(i, h) {
		REP(j, w) {
			if (i + 1 < h) {
				if (s[i + 1][j] == '.') {
					dp[i + 1][j] += dp[i][j];
					dp[i + 1][j] %= MOD;
				}
			}
			if (j + 1 < w) {
				if (s[i][j + 1] == '.') {
					dp[i][j + 1] += dp[i][j];
					dp[i][j + 1] %= MOD;
				}
			}
		}
	}
	cout << dp[h - 1][w - 1] << endl;
}


Measured memory_bytes: 9856
s = input()
n = len(s)
answer = [1] * n
for i in range(0,n-2):
	if s[i] == 'R' and s[i+1] == 'R':
			answer[i+2] += answer[i]
			answer[i] = 0
for i in range(n-1,1,-1):
	if s[i] == 'L' and s[i-1] == 'L':
			answer[i-2] += answer[i]
			answer[i] = 0
print(*answer)


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

int main() {
    int64_t N, M;
    cin >> N >> M;
    vector<int64_t> X(N);
    for (int64_t& x : X) {
        cin >> x;
    }

    const int64_t max_value = *max_element(X.begin(), X.end());

    vector<int64_t> num(max_value + 1, 0);
    for (int64_t x : X) {
        num[x]++;
    }

    //card[i][j] := カードの値をMで割ったあまりがiで、カード数を2で割った余りがｊであるもの
    vector<vector<stack<int64_t>>> card(M, vector<stack<int64_t>>(2));
    for (int64_t i = 0; i <= max_value; i++) {
        if (num[i] == 0) {
            continue;
        }
        card[i % M][num[i] % 2].push(num[i]);
    }

    //マッチングを考えていく
    int64_t ans = 0;
    while (true) {
        bool change = false;
        for (int64_t i = 0; i < M; i++) {
            //奇数番目のものは奇数番目のもの同士でくっつければ良い
            while (!card[i][1].empty()) {
                int64_t top = card[i][1].top();
                card[i][1].pop();

                int64_t pair = (M - i) % M;

                //card[pair][1]に要素があればそれと結合
                if (!card[pair][1].empty()) {
                    int64_t inv = card[pair][1].top();
                    card[pair][1].pop();
                    ans++;
                    change = true;

                    if (inv != 1) {
                        card[pair][0].push(inv - 1);
                    }
                } else if (!card[pair][0].empty()) {
                    //偶数側から貰ってくる
                    int64_t inv = card[pair][0].top();
                    card[pair][0].pop();
                    ans++;
                    change = true;

                    //一つ減るので奇数側に追加
                    card[pair][1].push(inv - 1);
                }

                //一つ減るので偶数側に追加(1だったら消滅)
                if (top != 1) {
                    card[i][0].push(top - 1);
                }
            }
        }
        if (!change) {
            break;
        }
    }

    //同じカード同士で結合
    for (int64_t i = 0; i < M; i++) {
        for (int64_t j = 0; j < 2; j++) {
            while (!card[i][j].empty()) {
                ans += card[i][j].top() / 2;
                card[i][j].pop();
            }
        }
    }

    cout << ans << endl;
}

Measured memory_bytes: 140160
#include<bits/stdc++.h>
using namespace std;
int main (){
	int a,b;
	cin >> a >> b;
	bool flg;
	flg = false;
	if(a%2==1&&b%2==1){
		flg = true;
	}
	if(flg){
		cout<<"Yes"<<endl;
	}else{
		cout<<"No"<<endl;
	}
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,N) for (int i = 0; i < (N); ++i)
#define all(v) v.begin(), v.end()
using namespace std;
using ll = long long;
using P = pair<int, int>;
const int inf{int(1e9)};
int main(void){
  string S, T;
  cin >> S >> T;

  int ans = T.size();

  for (int start = 0; start <= S.size() - T.size(); start++){
    int diff = 0;
    for (int i = 0; i < T.size(); i++){
      if (T[i] != S[start + i]){
        diff++;
      }
    }
    ans = min(ans, diff);
  }
  cout << ans << endl;
}


Measured memory_bytes: 3568
#include <math.h>

#include <cmath>
#include <iostream>
using namespace std;
int main() {
    string k, l;
    string alp[26] = {"a", "b", "c", "d", "e", "f", "g", "h", "i",
                      "j", "k", "l", "m", "n", "o", "p", "q", "r",
                      "s", "t", "u", "v", "w", "x", "y", "z"};
    cin >> k >> l;
    for (int i = 0; i < 26;i++){
        if(k+alp[i]==l){
            cout << "Yes" << endl;
            break;
        }else if(i==25){
            cout << "No" << endl;
        }
    } return 0;
}

Measured memory_bytes: 3628
package main

import "fmt"

func main() {
	var A, B, C int
	fmt.Scan(&A, &B, &C)
	var cnt int
	for {
		// log.Println(A, B, C)
		if A%2 == 1 || B%2 == 1 || C%2 == 1 || cnt > 1000000 {
			break
		}
		A, B, C = B/2+C/2, A/2+C/2, A/2+B/2
		cnt++
	}
	if cnt == 1000001 {
		cnt = -1
	}
	fmt.Println(cnt)
}


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

int main() {
    int A, B, C, K;
    cin >> A >> B >> C;
    cin >> K;

    int cnt = 0;
    while(A >= B) {
        B *= 2;
        cnt++;
    }
    while(B >= C) {
        C *= 2;
        cnt++;
    }

    if(cnt <= K) {
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }

    return 0;
}

Measured memory_bytes: 3632
b = input()
h = [int(i) for i in input().split(" ")]
hh = [i - 1 for i in h]
n = hh[0]
for i in range(1, len(h)):
    if n <= hh[i]:
        n = hh[i]
    elif n <= h[i]:
        n = h[i]
    else:
        print("No")
        break
else:
    print("Yes")


Measured memory_bytes: 14396