akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>

#define CEIL(a,b) ((a) / (b) + ((a) % (b) == 0 ? 0 : 1))

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

constexpr int MOD = 1'000'000'007;
constexpr int INF = 1'000'000'001;
constexpr ll LLINF = 4'000'000'000'000'000'001;
// constexpr int INF = 2147483647; // 2 * 1e9
// constexpr ll LLINF = 9223372036854775807; // 9 * 1e18

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

int mod_pow(int x, int y){
    ll tmp = x, ret = 1;
    while(y){
        if(y & 1){
            ret *= tmp;
            ret %= MOD;
        }
        tmp = tmp * tmp % MOD;
        y >>= 1;
    }
    return ret;
}

int fact[2001], inv[2001];

int nCr(int n, int r){
    return (ll)fact[n] * inv[r] % MOD * inv[n-r] % MOD;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout << fixed << setprecision(10);
    fact[0] = inv[0] = 1;
    for(int i = 1; i <= 2000; ++i){
        fact[i] = (ll)i * fact[i-1] % MOD;
        inv[i] = mod_pow(fact[i], MOD-2);
    }
    int n, k;
    cin >> n >> k;
    for(int i = 1; i <= k; ++i){
        if(n - k + 1< i){
            cout << "0\n";
            continue;
        }
        int ans = (ll)nCr(k-1, i-1) * nCr(n-k+1, i) % MOD;
        cout << ans << "\n";
    }
    return 0;
}

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

using namespace std;

#define rep(i,j) REP((i), 0, (j))
#define REP(i,j,k) for(int i=(j);(i)<(k);++i)
#define F first
#define S second

typedef pair<int, int> P;

int N,W,H,x,y,w,p,r;
P Y[100005],X[100005];

int main(){
  cin>>N>>W>>H;  
  rep(i,N){
    cin>>x>>y>>w;
    Y[i] = P(y,w); X[i] = P(x,w);
  }
  sort(Y,Y+N); sort(X,X+N);
  p=0;
  rep(i,N){
    if(p < Y[i].F-Y[i].S || Y[i].F+Y[i].S < p) continue;
    p = Y[i].F+Y[i].S;
    if(p >= H)r=1;
  }
  p=0;
  rep(i,N){
    if(p < X[i].F-X[i].S || X[i].F+X[i].S < p) continue;
    p = X[i].F+X[i].S;
    if(p >= W)r=1;
  }
  cout<<(r?"Yes\n":"No\n");
  return 0;
}

Measured memory_bytes: 2688
#include <stdio.h>
#include <iostream>
#include <stdlib.h>
#include <utility>
#include <math.h>
#include <stdexcept>
#include <algorithm>
#include <vector>
#include <cstring>
#include <string>
#include <cassert>
#include <string.h>

using namespace std;
#define  rep(i,n) for(int i=0;i<n;i++)
#define  rrep(i,n) for(int i=n-1;i>=0;i--)///n-1番目からn回
#define  REP(i,a,b) for(int i=a;i<b;i++) ///a番目からb回
#define  RREP(i,a,b) for(int i=a;i<b;i--)
typedef long long int ll;
typedef vector<ll> vl;
typedef vector<int> vi;
typedef vector<string> vs;

#define MOD 1000003

//int arr[N]
////sort(arr,arr +N)

//vector <int> hoge
////sort(hoge.begin(),hoge.end());
///*min_element(hoge.begin(),hoge.end();　最小値　　　最大値はmax_element();
///(10-(n%10))%10  1桁目取得

#define Ru(n)  ( ((n)+9)/10*10  ) //切りあげ
#define Rd(n)  ( ((n)-10)/10*10 +10 )	切り捨て

int gcd(int a,int b);
size_t length(const std::string& str) {
	return str.length();
}



int main() {
	int n,m,p=0;
	vl a(10000000);
	vl ans(1000000);
	ans[0]=1;
	cin>>n>>m;
	rep(i,m)
		cin>>a[i] ;
	if(a[0]==1)
		p++;
	else
		ans[1]=1;
	REP(i,2,n+1){
		ans[i] =( ans[i - 1] + ans[i - 2])%1000000007;
		if(i==a[p]) {
			ans[i]=0;
			p++;
			
			
		}
		//cout<<i<<" "<<ans[i]<<endl;
	}
	cout<<ans[n]%1000000007<<endl;
	return 0;


}


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


Measured memory_bytes: 86144
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define rep(i, n) for(int i = 0; i < n; i++)
#define all(a) a.begin(), a.end()
#define P pair<int, int>
#define F first
#define S second
#define mod 1000000007
#define INF 9000000000000000000
vector<int>G[1005];
int bfs(int x){
    queue<int>q;
    vector<int>dist(1005,-1);
    dist[x]=0;
    q.push(x);
    while(!q.empty()){
        int fr=q.front();q.pop();
        for(auto t:G[fr]){
            if(t==x){
                return dist[fr]+1;
            }
            if(dist[t]==-1){
                dist[t]=dist[fr]+1;
                q.push(t);
            }
            
        }
    }
    return INF;
    
}
signed main() {
    int n,m;cin>>n>>m;
    rep(i,m){
        int f,t;cin>>f>>t;f--;t--;
        G[f].push_back(t);
    }
    vector<int>Min(n,-1);
    int r=INF;
    rep(i,n){
        Min[i]=bfs(i);
        r=min(r,Min[i]);
    }
    //cout<<r<<endl;
    if(r==INF)cout<<-1<<endl;
    else{
        rep(i,n){
            if(Min[i]==r){
                vector<int>Ans;
                int pre[n];
                queue<int>q;
                vector<int>dist(1005,-1);
                
                int x=i;
                dist[x]=0;
                q.push(x);
                bool ju=false;
                while(!q.empty()){
                    int fr=q.front();q.pop();
                    for(auto t:G[fr]){
                        if(t==x){
                            pre[x]=fr;
                            ju=true;
                            break;
                      }
                      if(dist[t]==-1){
                          dist[t]=dist[fr]+1;
                          pre[t]=fr;
                          q.push(t);
                      }
            
                    }
                    if(ju)break;
             }
            rep(j,r){
                Ans.push_back(x);
                x=pre[x];
            }  
            sort(all(Ans));
            cout<<r<<endl;
            rep(j,r)cout<<Ans[j]+1<<endl;
                break;
                
                
                
                
            }
        }
        
        
        
        
    }
    
    
    
}

Measured memory_bytes: 384
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <climits>
#include <cmath>
#include <map>
#include <queue>
#include <iomanip>
#include <set>

using namespace std;
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++ )
#define repf(i,m,n) for(int (i)=m;(i)<n;(i)++)
#define all(v) (v).begin(), (v).end()
#define ll long long
#define vec(name,num) vector<ll> name((num),0);
#define op(i) cout<<(i)<<endl;
#define ip(i) cin>>(i);
#define opN cout<<"No"<<endl;
#define opY cout<<"Yes"<<endl;
#define opP cout<<"Possible"<<endl;
#define opI cout<<"Impossible"<<endl;
#define mat(name,fnum,snum); vector<vector<ll>> name((fnum),vector<ll>((snum),0));
#define matC(name,fnum,snum); vector<vector<char>> name((fnum),vector<char>((snum),0));
#define debugP int debug_point; cin>>debug_point;
#define FI first
#define SE second
const ll MOD= 1e9 + 7;
template <typename T>
void putv(vector<T>& V){
	// cout << "The elements in the vector are: " << endl;
	for(auto x: V)
		cout << x << " ";
	cout << endl;
}
ll pow_mod(ll fi,ll se,ll mod){
  if(se==0){
    return 1;
  }
  if(se%2){
    return pow_mod(fi,se-1,mod)*fi%mod;
  }
  ll t=pow_mod(fi,se/2,mod);
  return t*t%mod;
}
template <class T>
vector<T> getv(ll n){
	vector<T> Vector_temp;
	rep(i,n){
		T input;
		cin >> input;
		Vector_temp.emplace_back(input);
	}
	return Vector_temp;
}
ll gcd(ll c,ll b){
    while(1){
        if(c%b!=0){
        ll tmp=b;
        b=c%b;
        c=tmp;
        }else{
            return b;
        }
    }
}

vector<pair<int,int>> Dir={{-1,0},{1,0},{0,1},{0,-1}};
/* <3<3<3<3<3<3<3<3<3<3<3<3<3<3<3<3<3<3<3<3<3<3<3<3<3<3<3<3<3<3<3<3*/


int main(){
  ll x,a;
  cin>>x>>a;
  if(x<a)op(0)
  else op(10)
  return 0;
}


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

int main(){
  int Ntown; int64_t Nteleport;
  cin >> Ntown >> Nteleport;

  vector<int> func(Ntown);
  int buf;
  for(int i=0; i<Ntown; i++){
    cin >> buf;
    buf--; // 1-indexed -> 0-indexed
    func.at(i)= buf;
  }

  vector<int> ans(Ntown);
  iota(ans.begin(), ans.end(), 0);
  vector<int> buffunc(Ntown);

  int64_t D= Nteleport;
  while(D > 0){
    if(D&1){
      for(int i=0; i<Ntown; i++){
        ans.at(i)= func.at(ans.at(i));
      }
    }

    D >>= 1;
    for(int i=0; i<Ntown; i++){
      buffunc.at(i)= func.at(func.at(i));
    }
    func= buffunc;
  }

  cout << ans.at(0)+ 1 << endl; // 0-indexed -> 1-indexed
}

Measured memory_bytes: 5616
#pragma GCC optimize ("O3")
#include <iostream>
#include <iomanip>
#include <istream>
#include <ostream>
#include <sstream>
#include <iterator>
#include <vector>
#include <algorithm>
#include <queue>
#include <deque>
#include <list>
#include <stack>
#include <map>
#include <unordered_map>
#include <set>
#include <bitset>
#include <utility>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <string>
#include <ctime>
#include <cctype>
#include <cstdlib>
#define IINF 10e8
#define INF 1<<30
#define MOD 1000000007
#define mod 998244353
#define REP(i, a, n) for (ll i = a; i < (ll)(n); i++)
#define REPE(i, a, n) for (ll i = a; i <= (ll)(n); i++)
#define Endl endl
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define eb emplace_back
#define mmax(x,y)(x>y?x:y)
#define mmin(x,y)(x<y?x:y)
#define chmax(x,y) x=mmax(x,y)
#define chmin(x,y) x=mmin(x,y)
#define all(x) (x).begin(),(x).end()
#define siz(x) (ll)(x).size()
#define PI acos(-1.0)
using namespace std;
typedef long long int ll;
typedef unsigned long long int ull;
typedef long double ld;
typedef pair<int,int>Pin;
typedef pair<ll,ll>Pll;
template<class T> using V=vector<T>;
long long GCD(long long a, long long b) {return b?GCD(b,a%b):a;}
long long LCM(long long a, long long b) {return a/GCD(a,b)*b;}
int dx[4]={-1,0,1,0};
int dy[4]={0,-1,0,1};
int ddx[8]={-1,0,1,0,1,1,-1,-1};
int ddy[8]={0,-1,0,1,1,-1,1,-1};
ll cmp(pair<ll,ll>a,pair<ll,ll> b){
        if(a.se!=b.se)
        return a.se<b.se;
        else
        return a.fi<b.fi;
}
//----------------------------------------------------------------------

//----------------------------------------------------------------------
int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    //-------------------------------  
    //ll begin_time=clock();
    //-------------------------------
    
    int dp[1000100],dpodd[1000100];
    for(int i=0;i<1000100;i++){
        dp[i]=INF;
        dpodd[i]=INF;
    }
    dp[0]=0;
    dpodd[0]=0;
        for(int i=1;;i++){
            ll y=i*(i+1)*(i+2)/6;
            if(y>1e6)break;
            for(int j=y;j<1000100;j++){
                chmin(dp[j],dp[j-y]+1);
                if(y%2!=0)chmin(dpodd[j],dpodd[j-y]+1);
            }
        }
    int n;cin>>n;
    while(n){
        cout<<dp[n]<<" "<<dpodd[n]<<Endl;
        cin>>n;
    }
    //-------------------------------  
    //ll end_time=clock();cout<<"time="<<end_time-begin_time<<"ms"<<endl;
    //-------------------------------
    return 0;
}
//----------------------------------------------------------------------





























Measured memory_bytes: 10948
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <vector>
#include <utility>
#include <queue>
using namespace std;

bool pair_compare(const pair<int, int>& a, const pair<int, int>& b)
{
  return a.first < b.first;
}

int
main(int argc, char *argv[])
{
  vector<pair<int,int> > data;
  int n, m, a, b;
  cin >> n >> m;
  for (int i = 0; i < n; i++) {
    cin >> a >> b;
    if (a <= m) data.push_back(make_pair(a, b));
  }

  sort(data.begin(), data.end(), pair_compare);

  int p = 1; int k = 0; int ans = 0;
  priority_queue<int> que;
  
  do {
    while (k < data.size() && data.at(k).first <= p) {
      que.push(data.at(k).second);
      k++;
    }
    if (!que.empty()) {
      ans += que.top();
      que.pop();
    }
    p++;
  } while (p <= m);

  cout << ans << endl;

  return 0;
}
    


Measured memory_bytes: 1908
//Volume5-0532
import java.util.Scanner;

class Main {

	public static void main(String[] args){

		Scanner sc = new Scanner(System.in);

		int start,end,time;

		for(int i=0;i<3;i++){
			start = (sc.nextInt() * 60 + sc.nextInt()) * 60 + sc.nextInt();
			end   = (sc.nextInt() * 60 + sc.nextInt()) * 60 + sc.nextInt();
			time  = end - start;
			System.out.println((time/3600)+" "+(time%3600/60)+" "+(time%60));
		}
	}
}

Measured memory_bytes: 17368
#include <cstdio>
#include <iostream>
#include <string>
using namespace std;
int c,x[100][100],y[100][100];
bool G[100][100],d[100][100];

void fs(int i,int j){
  if(G[i][j]){
    if(d[i][j]) c++;
  }
  else{
    G[i][j] = true;
    d[i][j] = true;
    fs(x[i][j],y[i][j]);
  }
}

int main(){
  int i,j,n;
  while(1){
    cin >> n;
    if(n == 0) break;
    c = 0;
    for(j=0;j<n;j++){
      for(i=0;i<n;i++){
	cin >> x[i][j] >> y[i][j];
	G[i][j] = false;
      }
    }

    for(j=0;j<n;j++){
      for(i=0;i<n;i++){
	if(!G[i][j]){
	  for(int k=0;k<n;k++){
	    for(int l=0;l<n;l++) d[k][l] = 0;
	  }
	  fs(i,j);
	}
      }
    }
    cout << c << endl;
  }
  return 0;
}

Measured memory_bytes: 960
HWK = input().split()
H = int(HWK[0])
W = int(HWK[1])
K = int(HWK[2])

image = [0]*H*W
# black : 0
# white : 1
# red : 2
for row in range(H):
    c_values = input()
    for col in range(W):
        if c_values[col] == ".":
            image[W*row + col] = 1
        if c_values[col] == "#":
            image[W*row + col] = 0

result = 0
for i in range(2**H):
    for j in range(2**W):
        rows = [int(x) for x in bin(i)[2:]] # 0 : remove, 1 : keep
        rows = max((H - len(rows)), 0)*[0] + rows

        cols = [int(x) for x in bin(j)[2:]]
        cols = max((W - len(cols), 0))*[0] + cols
        # print(cols)
        count_black = 0
        for row in range(H):
            for col in range(W):
                if rows[row] == 0:
                    continue
                if cols[col] == 0:
                    continue
                if image[row*W + col] == 0:
                    count_black += 1
        if count_black == K:
            result += 1



print(result)

Measured memory_bytes: 9240
def resolve():
    # 整数 1 つ
    n = int(input())
    # 整数複数個
    # a, b, c = list(map(int, input().split()))
    # 整数 N 個 (改行区切り)
    # N = [int(input()) for i in range(N)]
    # 整数 N 個 (スペース区切り)
    # N = list(map(int, input().split()))
    # 整数 (縦 H 横 W の行列)
    # A = [list(map(int, input().split())) for i in range(H)]

    A = [1,2,4,8,16,32,64]
    B = sorted(A, reverse=True)

    for i in B:
        if i <= n:
            print(i)
            break

#    print("n")


resolve()

Measured memory_bytes: 38384
#include <iostream>
#include <iomanip>
#include <string>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <algorithm>
#include <numeric>
#include <cmath>
#include <cassert>

using namespace std;
typedef long long LL;
template <typename F, typename S> std::ostream& operator<<(ostream& os, const pair<F,S>& p) {
    os << "(" << p.first << "," << p.second << ")"; return os; }
template <typename T> ostream& operator<<(ostream& os, const vector<T>& v) {
    os << "["; for(const T& a: v){ os << a << ", "; } os << "]"; return os; }
template <typename K, typename V> ostream& operator<<(ostream& os, const map<K,V>& m) {
    os << "{"; for(const auto& p: m){ os << p.first <<":"<< p.second << ", "; } os << "}"; return os; }



int main(){
    LL n;
    cin >> n;
    vector<LL> a(n), b(n);
    for(LL i = 0; i < n; ++i){
        cin >> a[i] >> b[i];
    }
    sort(a.begin(), a.end());
    sort(b.begin(), b.end(), greater<LL>());
    LL left, right;
    if(n % 2 == 0){
        left = a[(n-1)/2] + a[n/2];
        right = b[(n-1)/2] + b[n/2];
    }else{
        left = a[(n-1)/2];
        right = b[(n-1)/2];
    }
    LL ans = (1 + right - left);
    cout << ans << endl;
    return 0;
}



Measured memory_bytes: 6084
#include<algorithm>
#include<cstring>
#include<iostream>
#include<cmath>

using namespace std;

int main() {
	int n;
	scanf("%d", &n);

	int a[n];
	for(int i=0; i<n; i++) {
		scanf("%d", &a[i]);
	}
	long long sum[n];
	sum[0] = a[0];
	for(int i=1; i<n; i++) {
		sum[i] = sum[i-1] + a[i];
	}

	long long dp[n][n];
	for(int i=0; i<n; i++) {
		dp[i][i] = a[i];
	}
	for(int i=0; i+1<n; i++) {
		dp[i][i+1] = a[i]+a[i+1];
	}
	for(int len=3; len<=n; len++) {
		for(int i=0,j=i+len-1; j<n; i++,j++) {
			dp[i][j] = 1e18;
			for(int k=i+1; k+1<j; k++) {
				dp[i][j] = min(dp[i][j], dp[i][k]+dp[k+1][j]);
			}
			dp[i][j] = min(dp[i][j], dp[i+1][j]);
			dp[i][j] = min(dp[i][j], dp[i][j-1]);
			dp[i][j] += sum[j]-(i?sum[i-1]:0);
		}
	}
	printf("%lld\n", dp[0][n-1]);
    return 0;
}

Measured memory_bytes: 1536
#include<stdio.h>
	int k=0;
	long func(long x,long y){		
		long h;
		x=x%y;
		h=y;
		y=x;
		x=h;
		k++;
		if(y==0)
			return x;
		else
			return func(x,y);
}
	
	
	
	
	int main(){
		long x,y,f;
		while(scanf("%ld %ld",&x,&y),x||y){
			k=0;
			if(x>=y)
				f=func(x,y);
			else
				f=func(y,x);
			printf("%ld %d\n",f,k);
			
			
		}
		return 0;
}

Measured memory_bytes: 0
h,*s=open(0)
h,w,k=map(int,h.split())
s=[list(map(int,t[:w]))for t in s]
m=9e9
for i in range(1<<h-1):
  t=[]
  b=v=l=0
  for j in range(h):
    if i>>j&1:
      t+=s[b:j+1],
      b=j+1
      l+=1
  t+=s[b:],
  l+=1
  c=[0]*l
  for i in range(w):
    f=g=0
    u=[]
    for j in range(l):
      d=sum(t[i]for t in t[j])
      u+=d,
      if d>k:
        g=1
        break
      c[j]+=d
      f|=c[j]>k
    else:
      v+=f
      if f:c=u
    if g:break
  else:m=min(m,v+l-1)
print(m)

Measured memory_bytes: 49756
from collections import deque, defaultdict
N, M = map(int, input().split())
tree = [[] for _ in range(N)]
for _ in range(M):
    a, b = map(lambda x: int(x)-1, input().split())
    tree[a].append(b)
    tree[b].append(a)

visited = [False]*N
q = deque([0])
visited[0] = True
ans = defaultdict(int)
while len(q):
    v = q.popleft()
    for e in tree[v]:
        if visited[e]:
            continue
        visited[e] = True
        ans[e] = v
        q.append(e)
print("Yes")
for i in range(1, N):
    print(ans[i]+1)


Measured memory_bytes: 41492
#include <bits/stdc++.h>
#define LL long long
#define MOD 1000000007
using namespace std;
int a[200005];
int N, K;
int check(int M)
{
  int cnt = 0;
  for (int i = 0; i < N; ++i)
    {
      cnt += (a[i] - 1) / M;
    }
  if (cnt <= K)
    return true;
  return false;
}
int main()
{
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  cin >> N >> K;
  int maxx = 0;
  for (int i = 0; i < N; ++i)
    {
      cin >> a[i];
      maxx = max(a[i], maxx);
    }
  int L = 0, R = maxx;
  while (L + 1 < R)
    {
      int mid = (L + R) / 2;
      if (check(mid)) R = mid;
      else L = mid;
    }
  cout << R << endl;
  return 0;
}


Measured memory_bytes: 4352
#include<bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define each(it,c) for(__typeof((c).begin()) it=(c).begin();it!=(c).end();it++)
#define all(obj) (obj).begin(),(obj).end() 
#define dump(x)  cout << #x << " = " << (x) << endl;
typedef long long lint;
using namespace std;
int main(){
	int x,a,b;
	cin>>x>>a>>b;
	cout<<(x-a)%b<<endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define For(i, a, b) for(int (i)=(int)(a); (i)<(int)(b); ++(i))
#define rFor(i, a, b) for(int (i)=(int)(a)-1; (i)>=(int)(b); --(i))
#define rep(i, n) For((i), 0, (n))
#define rrep(i, n) rFor((i), (n), 0)
#define fi first
#define se second
using namespace std;
typedef long long lint;
typedef unsigned long long ulint;
typedef pair<int, int> pii;
typedef pair<lint, lint> pll;
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(a>b){a=b; return true;} return false;}
template<class T> T div_floor(T a, T b){
    if(b < 0) a *= -1, b *= -1;
    return a>=0 ? a/b : (a+1)/b-1;
}
template<class T> T div_ceil(T a, T b){
    if(b < 0) a *= -1, b *= -1;
    return a>0 ? (a-1)/b+1 : a/b;
}

constexpr lint mod = 1000000007;
constexpr lint INF = mod * mod;
constexpr int MAX = 200010;

struct state{
    int x, y, dir, dist;
    state(int x, int y, int dir, int dist): x(x), y(y), dir(dir), dist(dist){}
};

int w, h;

void solve(){
    int a[h][w];
    rep(i, h)rep(j, w){
        char c;
        scanf(" %c", &c);
        if(isdigit(c)) a[i][j] = c-'0';
        else a[i][j] = (c == 'X' ? mod : 0);
    }

    auto cmp = [](const state &s1, const state &s2){
        return s1.dist > s2.dist;
    };
    priority_queue<state, vector<state>, decltype(cmp)> que(cmp);
    int d[h][w][2];
    rep(i, h)rep(j, w)rep(k, 2) d[i][j][k] = mod;
    rep(j, w)if(a[h-1][j] == 0){
        rep(k, 2){
            d[h-1][j][k] = 0;
            que.emplace(h-1, j, k, 0);
        }
    }
    while(!que.empty()){
        auto s = que.top();
        que.pop();
        if(s.dist > d[s.x][s.y][s.dir]) continue;
        for(int dx=-2; dx<=2; ++dx)for(int dy=1; dy+abs(dx)<=3; ++dy){
            int nx = s.x + dx, ny = s.y + dy * (2*s.dir - 1), nd = s.dir^1;
            if(0<=nx && nx<h && 0<=ny && ny<w && chmin(d[nx][ny][nd], s.dist + a[nx][ny])){
                que.emplace(nx, ny, nd, d[nx][ny][nd]);
            }
        }
    }
    int ans = mod;
    rep(j, w)if(a[0][j] == 0)rep(k, 2) chmin(ans, d[0][j][k]);
    printf("%d\n", ans == mod ? -1 : ans);
}

int main(){
    while(scanf("%d%d", &w, &h) && w){
        solve();
    }
}


Measured memory_bytes: 3164
// ------------------------------------
// Date:2018/ 3/24
// Problem:D- Wide Flip rere_d.cpp
//
// ------------------------------------

#include <bits/stdc++.h>

using namespace std;

#define EACH(i,a) for (auto& i : a)
#define FOR(i,a,b) for(int i=(int)a;i<(int)b;++i)
#define RFOR(i,a,b) for(int i=(int)b-1;i>=(int)a;--i)
#define REP(i,n) FOR(i,0,n)
#define RREP(i,n) RFOR(i,0,n)
#define ALL(a) (a).begin(),(a).end()
#define debug(x) cerr << #x << ":" << x << endl;
#define OK(ok) cout << (ok ? "Yes" : "No") << endl;
typedef long long ll;

void CINT(){}
template <class Head,class... Tail>
void CINT(Head&& head,Tail&&... tail) {
  cin >> head; CINT(move(tail)...);
}
#define CIN(...) int __VA_ARGS__;CINT(__VA_ARGS__)
#define LCIN(...) ll __VA_ARGS__;CINT(__VA_ARGS__)
#define SCIN(...) string __VA_ARGS__;CINT(__VA_ARGS__)

static const int INF = 1e9 + 1;
static const int MAX_N = 1;

int main()
{
  SCIN(s);
  int ans = ans;
  int SIZE = s.size();
  FOR(i, 1, SIZE + 1) {
    if (s[i] != s[i - 1]) {
      ans = min(ans, max(i, SIZE - i));
    }
  }
  
  cout << ans << endl;

  return 0;
}



Measured memory_bytes: 512
n = input()
a = []
c = []
for i in ['S ','H ','C ','D ']:
	for j in map(str,xrange(1,14)):
		a.append(i+j)
for i in xrange(n):
	a.remove(raw_input())
for i in xrange(len(a)):
	print a[i]

Measured memory_bytes: 6440
#pragma GCC optimize("O3")
            #pragma comment(linker, "/stack:200000000")
            #pragma GCC optimize("unroll-loops")
             
            #include <algorithm>
            #include <bitset>
            #include <cassert>
            #include <chrono>
            #include <cmath>
            #include <complex>
            #include <cstdio>
            #include <cstdlib>
            #include <cstring>
            #include <ctime>
            #include <deque>
            #include <functional>
            #include <iomanip>
            #include <iostream>
            #include <iterator>
            #include <limits>
            #include <climits>
            #include <list>
            #include <map>
            #include <numeric>
            #include <queue>
            #include <random>
            #include <ratio>
            #include <set>
            #include <sstream>
            #include <stack>
            #include <string>
            #include <unordered_map>
            #include <unordered_set>
            #include <utility>
            #include <vector>
            using namespace std;
             
            typedef long long ll;
            typedef long double LD;
            #define int ll
            #define double LD
            #define pb push_back
            #define mp make_pair
            #define REP(i,n) for (int i = 0; i < n; i++)
            #define loop(i,n) for (int i = 0; i < n; i++)
            #define FOR(i,a,b) for (int i = a; i < b; i++)
            #define REPD(i,n) for (int i = n-1; i >= 0; i--)
            #define FORD(i,a,b) for (int i = a; i >= b; i--)
            #define remax(a,b) a = max(a,b)
            #define remin(a,b) a = min(a,b)
            #define mem(a, b) memset(a, b, sizeof a)
            #define append push_back
            #define all(v) v.begin(),v.end()
            #define F first
            #define S second
            #define print(x) cout << (x) << endl
            #define PRECISION(x) cout << fixed << setprecision(x)
            #define FAST_IO ios::sync_with_stdio(0); cin.tie(0); cout.tie(0)
            #define N 505
            #define pb push_back
            const double PI=acos(-1);
            const int MOD = 1000000007;
            const int FMOD = 998244353;
            const double eps = 1e-9;
             
            mt19937 RNG(chrono::steady_clock::now().time_since_epoch().count()); 
            
         
           signed main()
           {
           		double r;
           		cin>>r;
           		double ans=2.0*3.14*r;
           		cout<<fixed<<setprecision(6)<<ans;
		   }

Measured memory_bytes: 3788
#include<map>
#include<queue>
#include<string>
#include<iostream>
using namespace std;
int n,m,Max=0;
string S;
map<string,int>Count;
map<string,bool>vis;
queue<string>Q;
int main() {
	cin>>n;
	for(int i=1;i<=n;i++) {
		cin>>S;
		Count[S]++;
		if(!vis[S]) {
			Q.push(S);
			vis[S]=true;
		}
	}
	cin>>m;
	for(int i=1;i<=m;i++) {
		cin>>S;
		Count[S]--;
		if(!vis[S]) {
			Q.push(S);
			vis[S]=true;
		}
	}
	while(!Q.empty()) {
		string s=Q.front();Q.pop();
		if(Count[s]>Max) Max=Count[s];
	}
	printf("%d\n",Max);
	return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int dfs(int vertex, vector<int> &dp, vector<vector<int>>& adj)
{
    if(dp[vertex]!=-1)
        return dp[vertex];
        
    int len = 0;
    for(int i=0; i<adj[vertex].size(); i++)
        len = max(len, 1+dfs(adj[vertex][i], dp, adj));
    
    return dp[vertex] = len;
}
int main()
{
    int n, m;
    cin>>n>>m;
    char ch;
    vector<vector<long long int>> mat(n, vector<long long int>(m, 0));
    for(int i=0; i<n; i++)
    {
        for(int j=0; j<m; j++)
        {
            cin>>ch;
            if(ch=='#')
                mat[i][j] = -1;
        }
    }
    mat[0][0] = 1;
    for(int i=1; i<n; i++)
    {
        if(mat[i][0]==-1)
            break;
        mat[i][0] = mat[i-1][0];
    }
    for(int j=1; j<m; j++)
    {
        if(mat[0][j]==-1)
            break;
        mat[0][j] = mat[0][j-1];
    }
    for(int i=1; i<n; i++)
    {
        for(int j=1; j<m; j++)
        {
            if(mat[i][j]!=-1)
            {
                int x = mat[i-1][j]==-1?0:mat[i-1][j];
                int y = mat[i][j-1]==-1?0:mat[i][j-1];
                mat[i][j] = (x+y)%1000000007;
            }
        }
    }
    cout<<mat[n-1][m-1]<<endl;
    return 0;
}

Measured memory_bytes: 8064
#include <iostream>
#include <stdio.h>
using namespace std ;
int main (){
long a , b , c ;
scanf("%ld%ld%ld",&a,&b,&c) ;
long ans = b  ;
if ( c <= a ) ans += c ;
else ans += a ;
c -= a ;
if (c > 0){
if ( c <= b ) ans += c ;
else ans += b + 1 ;
}
printf("%ld\n",ans) ;
return 0 ;
}

Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;
int main()
{
	double r,area,cir;
	cin>>r;
	area=M_PI*r*r;
	cir=2*M_PI*r;
	printf("%.6lf %.6lf\n",area,cir);
	return 0;
}


Measured memory_bytes: 3204
using System;

public class Hello
{
    public static void Main()
    {
        var n = int.Parse(Console.ReadLine().Trim()) % 10;
        string ans;
        if (n == 3) ans = "bon";
        else if (n == 0 | n == 1 | n == 6 | n == 8) ans = "pon";
        else ans = "hon";
        Console.WriteLine(ans);
    }
}



Measured memory_bytes: 27480
n = int(input())
dat = []
for i in range(n):
    dat.append(int(input()))

# print(dat)

def lcm(x, y):
    import fractions
    return (x * y) // fractions.gcd(x, y)

res = dat[0]

for i in range(n):
    res = lcm(res, dat[i])

print(res)

Measured memory_bytes: 64492
#include<bits/stdc++.h>
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define rep2(i, m, n) for(int i = (int)(m); i < (int)(n); i++)
#define rep_inv(i, n, m) for(int i = (int)(n); i > (int)(m); i--)
using namespace std;
using ll = long long;
using vl = vector<ll>;
using vc = vector<char>;
using vvl = vector<vl>;
using vvc = vector<vc>;
using pll = pair<ll, ll>;
using vpll = vector<pll>;

int main(){
  vl x(5);
  rep(i, 5) cin >> x[i];

  rep(i, 5){
    if(x[i] == 0){
      cout << i + 1 << "\n";
      return 0;
    }
  }
  
  return 0;
}


Measured memory_bytes: 3588
counter=0
n=gets.to_i
monster=gets.chomp.split.map(&:to_i)
brave=gets.chomp.split.map(&:to_i)
n.times do|x|
  defeated = [monster[x],brave[x]].min
  counter= counter+defeated
  rest_brave=brave[x]-defeated
  next_defeated = [monster[x+1],rest_brave].min
  counter= counter+next_defeated
  monster[x+1]=monster[x+1]-next_defeated
end  
puts counter

Measured memory_bytes: 21788
"""
import random
import functools
import copy
import bisect
import array
import re
import collections
import heapq
import fractions
import itertools
import string
import math
from operator import itemgetter as ig
from bisect import bisect_left, bisect_right, insort_left, insort_right
from itertools import permutations, combinations, product, accumulate, groupby
from heapq import heappush, heappop
from collections import deque, defaultdict, Counter
import sys
sys.setrecursionlimit(10 ** 7)
# import numpy as np

inf = 10 ** 20
INF = float("INF")
mod = 10 ** 9 + 7
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]
ddn = dd + [(-1, 1), (1, 1), (1, -1), (-1, -1)]
ddn9 = ddn + [(0, 0)]
'''for dx, dy in dd:
        nx = j + dx; ny = i + dy
            if 0 <= nx < w and 0 <= ny < h:'''
"""
from collections import deque, defaultdict, Counter
import math
import sys
sys.setrecursionlimit(10 ** 7)


def wi(): return list(map(int, sys.stdin.readline().split()))
# WideIntPoint


def wip(): return [int(x) - 1 for x in sys.stdin.readline().split()]


def ws(): return sys.stdin.readline().split()


def si(): return int(sys.stdin.readline())  # SingleInt


def ss(): return input()


def hi(n): return [si() for _ in range(n)]


def hs(n): return [ss() for _ in range(n)]  # HeightString


def s_list(): return list(input())


def mi(n): return [wi() for _ in range(n)]  # MatrixInt


def mip(n): return [wip() for _ in range(n)]


def ms(n): return [ws() for _ in range(n)]


def num_grid(n): return [[int(i) for i in sys.stdin.readline().split()[
    0]] for _ in range(n)]  # NumberGrid


def grid(n): return [s_list() for _ in range(n)]


def gcd(a, b):
    while b:
        a, b = b, a % b
    return a


def lcm(a, b):
    """a,bの最小公倍数"""
    return a * b // gcd(a, b)


def main():
    k, n = wi()
    A = wi()
    B = A.copy()
    C = A + B
    # print(C)
    m = 0
    for i in range(n):
        m = max(m, C[i+1] - C[i])
        if i == n-1:
            m = max(m, k - C[i]+C[0])
    print(k-m)


if __name__ == '__main__':
    main()


Measured memory_bytes: 26176
N,X,Y = map(int, input().split())

min_xy = min(X,Y)
max_xy = max(X,Y)

ans = [0]*(N-1)
for i in range(1,N+1):
    for j in range(i+1, N+1):
        k = min(j-i, abs(min_xy-i)+abs(max_xy-j)+1)
        ans[k-1] += 1

for i in range(N-1):
    print(ans[i])

Measured memory_bytes: 3444
#include <bits/stdc++.h>
#define rep(i,n)for(long long i=0;i<(n);i++)
using namespace std;
typedef long long ll;
const int MOD=1e9+7;
const int MAX = 510000;
const int INF = 1e9;
const double pi=acos(-1);


  
int main(){
  string s;
  cin >> s;
  int n=s.size();
  int sum=0;
  rep(i,n){
    sum+=s[i]-'0';
  }
  sum=max(sum,s[0]-'0'-1+9*(n-1));

  cout << sum << endl;
  return 0;
}


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

#define ll long long
#define ld long double
#define mod 1000000007LL
#define INF 1000000011
#define INFLL 1000000000000000011LL
#define endl '\n'
#define vi vector<int>
#define vs vector<string>
#define vll vector<long long>
#define vc vector<char>
#define pii pair<int, int>
#define pll pair<long long, long long>
#define pil pair<int, long long>
#define pli pair<long long, int>
#define pcc pair<char, char>
#define pdd pair<double, double>
#define mp make_pair
#define pb(x) push_back(x)
#define fo(i, a, n) for (i = (a); i < (n); i++)
#define foe(i, a, n) for (i = (a); i <= (n); i++)
// clang-format off
#define vin(a) for (ll i = 0; i < sz(a); i++) { cin >> a[i]; } 
#define vout(a) for (auto x : a) { cout << x << " "; }
#define sws                                                                    \
  ios_base::sync_with_stdio(false);                                            \
  cin.tie(0)
// clang-format on
#define pd(x) cout << x
#define sd(x) cin >> x
#define nl cout << endl
#define gcd __gcd
#define all(a) (a).begin(), (a).end()
#define foreach(i, a)                                                          \
  for (__typeof((a).begin()) i = (a).begin(); i != (a).end(); ++i)
#define sz(a) (int)((a).size())
// int dw[8][2]={{0,1},{1,0},{0,-1},{-1,0},{1,1},{1,-1},{-1,1},{-1,-1}};
void solve() {
  ll m, n;
  ll i, j;
  cin >> n;
  ll ans = 0;

  fo(i, 1, n) {
    ans += n / i;
    if (n % i == 0)
      ans--;
  }

  cout << ans << endl;
}

int main() {
  sws;
  solve();
  return 0;
}

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

using ll = long long;

const int mod = 1000000007;
const int INF = 1000000000;
const double EPS = 1e-9;

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int K, X;
    cin >> K >> X;
    cout << (K * 500 >= X ? "Yes" : "No") << endl;
}


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)


a_c = (a-1)//c
b_c = b//c
a_d = (a-1)//d
b_d = b//d
a_cd = (a-1)//lcm(c, d)
b_cd = b//lcm(c, d)

ans = (b - a + 1) - (b_c - a_c) - (b_d - a_d) + (b_cd - a_cd)

print(ans)

Measured memory_bytes: 66028
#pragma GCC optimize("O3")
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <bits/stdc++.h>

#define DEBUG
#ifdef DEBUG
    #define IFD(...) __VA_ARGS__
    #define IFN(...)
    #define L cout<<__LINE__<<"\n";
    #define PRINT(...) __VA_ARGS__ cout<<__LINE__<" : "<<#__VA_ARGS__<<"\n"
    #define PRT(x) cout<<__LINE__<<" : "<<#x<<" = "<<x<<"\n"
#else // DEBUG
    #define IFD(...)
    #define IFN(...) __VA_ARGS__
    #define L
    #define PRINT(...) __VA_ARGS__
    #define PRT(x)
#endif // DEBUG

#define it iterator
#define rit reverse_iterator
#define mp make_pair
#define mems(a,b) memset(a,b,sizeof(a))
#define mem0(a) mems(a,0)
#define mem1(a) mems(a,1)
#define mem255(a) mems(a,255)
#define halt exit(0)
#define all(c) (c).begin() , (c).end()
#define sz(c) ((long long)((c).size()))
#define phb push_back
#define ppb pop_back
#define phf push_front
#define ppf pop_front
#define fort0(i,a,b) for(ll i=a,i##_TO=b;i<i##_TO;i++)
#define for0(i,n) fort0(i,0,n)
#define fort1(i,a,b) for(ll i=a,i##_TO=b;i<=i##_TO;i++)
#define for1(i,n) fort1(i,1,n)
#define ford(i,a,b) for(ll i=a,i##_TO=b;i>=i##_TO;i--)

using namespace __gnu_pbds;
using namespace std;

#define int ll

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

template
<
    class key,
    class val=null_type,
    class comp=less<key>
>
using ord_set=tree
<
    key,
    val,
    comp,
    rb_tree_tag,
    tree_order_statistics_node_update
>;

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int n;
    cin>>n;
    int s=0;
    map<int,int> m;
    m[0]++;
    for(int i=0;i<n;i++)
    {
        int t;
        cin>>t;
        s+=t;
        m[s]++;
    }
    int ans=0;
    for(auto p:m)
        //cout<<p.first<<" "<<p.second<<"\n",
        ans+=p.second*(p.second-1)/2;
    cout<<ans;
}


Measured memory_bytes: 12800
#include <iostream>
#include <string>
#include <algorithm>
#include <iomanip>
#include <cmath>
using namespace std;

int main()
{
    
    int N, K, arr[100000], dp[100000];
    cin >> N >> K;
    for (int i = 0; i < N; i++){
        cin >> arr[i];
        dp[i] = 1000000001;
    }
    dp[0] = 0;
    int i, j;
    for ( i = 0; i < N; i++){
        for ( j = i + 1; j < i + K + 1; j++){
            if (j < N) {
                dp[j] = min(dp[j], dp[i] + abs(arr[i] - arr[j]));
            }
        }
    }
    cout << dp[N - 1];

    return 0;
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
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)

using ll = long long;
#define INF 1e9

int N, M;
vector<int> a, b, c;
vector<ll> dist;
void dfs(int i){
  
}

int main(){
  cin >> N >> M;
  
  dist.resize(N, 1e15);
  dist[0] = 0;
  a.resize(M), b.resize(M), c.resize(M);
  REP(i, M){
    cin >> a[i] >> b[i] >> c[i];
    a[i]--;
    b[i]--;
    c[i] = -c[i];
  }
  REP(j, N-1){
    REP(i, M){
      if(dist[a[i]] == 1e15){
        continue;
      }
      if(dist[b[i]] > dist[a[i]] + c[i]){
        dist[b[i]] = dist[a[i]] + c[i];
      }
    }
  }
  ll ans = dist[N-1];
  vector<bool> negative(N, false);
  REP(j, N-1){
    REP(i, M){
      if(dist[a[i]] == 1e15){
        continue;
      }
      if(negative[a[i]] == true){
        negative[b[i]] = true;
      }
      if(dist[b[i]] > dist[a[i]] + c[i]){
        dist[b[i]] = dist[a[i]] + c[i];
        negative[b[i]] = true;
      }
    }
  }
  if(negative[N-1] == true){
    cout << "inf" << endl;
  }
  else{
    cout << -ans << endl;
  }



  return 0;
}


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

long long N, M, a[100009][3], maxn = 0;//-(1LL << 60);

int main() {
	cin >> N >> M;
	for (int i = 1; i <= N; i++) {
		for (int j = 0; j < 3; j++) {
			cin >> a[i][j];
		}
	}
	for (int i = 0; i < 8; i++) {//ビットを管理するループ
		vector<long long >vec;
		for (int j = 1; j <= N; j++) {
			long long S = 0;//Sは（綺麗さの合計の絶対値）+（おいしさの合計の絶対値）＋（人気度の合計の絶対値）を計算するための変数
			for (int k = 0; k < 3; k++) {
				if ((i / (1 << k)) % 2 == 0) {
					S += a[j][k];
				}
				else {
					S -= a[j][k];
				}
				
			}
			vec.push_back(S);
		}
		sort(vec.begin(), vec.end());
		reverse(vec.begin(), vec.end());//降順に
		long long ans = 0;
		for (int j = 0; j < M; j++) {//貪欲にとる
			ans += vec[j];
		}


		maxn = max(maxn, ans);

	}
	cout << maxn << endl;
	return 0;
}
/*
i=0のとき　i / (1 << k)) % 2 == 0の値は　　k=0 のとき0 k=1のとき0 k=2のとき0 +++
i=1のとき　i / (1 << k)) % 2 == 0の値は　　k=0 のとき1 k=1のとき0 k=2のとき0 -++
i=2のとき　i / (1 << k)) % 2 == 0の値は　　k=0 のとき0 k=1のとき1 k=2のとき0 +-+
i=3のとき　i / (1 << k)) % 2 == 0の値は　  k=0のとき1  k=1のとき1 k=2のとき0 --+
i=4のとき　i / (1 << k)) % 2 == 0の値は　　　　　　　　　　　　　　　　　　　++-




*/

Measured memory_bytes: 256
N, M = [int(nm) for nm in input().split()]
if N==1:
  if M==1:
    print(1)
  elif M==2:
    print(0)
  else:
    print(M-2)
elif N==2:
  print(0)
else:
  if M==1:
    print(N-2)
  elif M==2:
    print(0)
  else:
    print((N-2)*(M-2))

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

int main(){
    ll n,a[100009],dp[100009],k;
    cin >> n >> k;
    for(int i=1; i<=n; i++)cin >> a[i];
    dp[n]=0;
    for(int i=n-1; i>=1; i--){
        ll z=1e15;
        for(int j=1; j<=k && i+j<=n; j++){
        	z=min(z,dp[i+j]+abs(a[i]-a[i+j]));
        }
        dp[i]=z;
    }
    cout << dp[1] << endl;
}




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

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  int a, b, h;
  cin >> a >> b >> h;
  cout << (a + b) * h / 2 << endl;
  return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
// -----------------<fast IO>------------------
#define IOS             ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define FLSH             fflush(stdout)
#define fileIO(name) \
    freopen(name".in", "r", stdin); \
    freopen(name".out", "w", stdout);
#define PRECISION(x)     cout << fixed << setprecision(x);
// -----------------<TypeDef Start>------------------
typedef long double ld;
typedef long long ll;
typedef unsigned long long ull;
// -----------------<Constants>------------------
const int MAXN = 1000005;
const int SQRTN = 1003;
const int LOGN = 22;
const double PI=acos(-1);

const int INF=1e9;
ll mn1=-9223372036854775808;
int mod = 1000000007;
const int FMOD = 998244353;
const double eps = 1e-9;
/*ll gcd(ll a,ll b)
{
    if(a==0)
    return(b);
    return(gcd(b%a,a));
}*/
// --------------------------------------------------</TEMPLATE>--------------------------------------------------

ll power(ll a,ll b,ll p)
{
    ll res=1;
    a%=p;
    while(b>0)
    {
        if(b&1)
        res=res*a%p;
        a=a*a%p;
        b>>=1;
    }
    return(res);
}
void solve()
{
    ll n;
    cin>>n;
    if(n==1)
        cout<<0<<endl;
    else if(n==2)
        cout<<2<<endl;
    else
    {
        cout<<(power(10,n,mod)%mod+power(8,n,mod)%mod-power(9,n,mod)%mod-power(9,n,mod)%mod+mod+mod)%mod;
    }
}
int main()
{
    IOS
    ll t=1;
    //cin>>t;
    while(t--)
    {
        solve();
    }
    return(0);

}


Measured memory_bytes: 3652
n = int(input())

verdict = []

for i in range(n):
    m = input()
    verdict.append(m)


AC = 0
WA = 0
TLE = 0
RE = 0

for i in range(n):

    if verdict[i] == "AC":
        AC += 1
    elif verdict[i] == "WA":
        WA += 1
    elif verdict[i] == "TLE":
        TLE += 1
    else:
        RE += 1


print("AC x", AC)
print("WA x", WA)
print("TLE x", TLE)
print("RE x", RE)

Measured memory_bytes: 16268
S = str(input())
N = len(S)
ans = 'Yes'
for i in range((N-1)//2):
    if S[i] != S[N-1-i]:
        ans = 'No'
        break

for i in range(((N-1)//2)//2):
    if S[i] != S[(N-1)//2-1-i]:
        ans = 'No'
        break
    if S[(N-1)//2+1+i] != S[N-1-i]:
        ans = 'No'
        break
            
print(ans)

Measured memory_bytes: 8992
#include<stdio.h>
#include<algorithm>
#include<math.h>
using namespace std;
double x[110000];
double y[110000];
double r[110000];
pair<double,int>p[110000];
int main(){
	int a;
	while(scanf("%d",&a),a){
		for(int i=0;i<a;i++){
			double tx,ty;
			scanf("%lf%lf%lf",r+i,&tx,&ty);
			x[i]=cos(1)*tx-sin(1)*ty;
			y[i]=sin(1)*tx+cos(1)*ty;
		}
		double ret=sqrt((x[0]-x[1])*(x[0]-x[1])+(y[0]-y[1])*(y[0]-y[1]))-r[0]-r[1];
		for(int i=0;i<a;i++){
			p[i]=make_pair(x[i]+r[i],i);
		}
		std::sort(p,p+a);
		for(int i=0;i<a;i++){
			for(int j=i-1;j>=0;j--){
				if(p[i].first-r[p[i].second]*2-p[j].first>ret)break;
				int L=p[i].second;
				int R=p[j].second;
				ret=min(ret,sqrt((x[L]-x[R])*(x[L]-x[R])+(y[L]-y[R])*(y[L]-y[R]))-r[L]-r[R]);
			}
		}
		printf("%.12f\n",ret);
	}
}

Measured memory_bytes: 5324
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>

typedef long long ll;
using namespace std;
const ll MOD = 1000000007;
int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  ll n, k;
  cin >> n >> k;
  ll a[n];
  for(int i = 0; i < n; i++) {
    cin >> a[i];
  }
  ll front[n];
  ll all[n];
  fill(all, all + n, 0);
  fill(front, front + n, 0);
  for(int j = 0; j < n; j++) {
    for(int i = 0; i < n; i++) {
      if(a[i] > a[j]) {
        all[j]++;
        if(i < j) {
          front[j]++; 
        }
      }
    }
  }
  ll sum = 0;
  for(int j = 0; j < n; j++) {
    ll allnum = ((k - 1) * k / 2) % MOD;
    sum += (allnum * all[j]) % MOD;
    sum += (k * front[j]) % MOD;
    sum = sum % MOD;
  }
  cout << sum << "\n";
  return 0;
}



Measured memory_bytes: 256
n = int(input())
m = int(input())
mat = [[float("inf")]*n for _ in [0]*n]
for a,b,c,d in((map(int, input().split(","))) for _ in [0]*m):
    mat[a-1][b-1] = c
    mat[b-1][a-1] = d
s,g,v,p = map(int, input().split(","))
for k in range(n):
    for i in range(n):
        for j in range(n):
            mat[i][j] = min(mat[i][j], mat[i][k]+mat[k][j])
print(v-p-mat[s-1][g-1]-mat[g-1][s-1])


Measured memory_bytes: 5616
#include <stdio.h>

int main(){
  
  int S[10000],n,i,j,q,T[500],count=0;

  scanf("%d",&n);
  for(i=0;i<n;i++){
    scanf("%d",&S[i]);
  }
  scanf("%d",&q);
  for(i=0;i<q;i++){
    scanf("%d",&T[i]);
  }
  for(i=0;i<q;i++){
    for(j=0;j<n;j++){
      if(T[i]==S[j]){
	count++;
	break;
      }
    }
  }
  printf("%d\n",count);
  
  return 0;
}

Measured memory_bytes: 640
#include <algorithm>
#include <cmath>
#include <complex>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <vector>
#include <functional>
#include <cstring>
#include <regex>
#include <random>
#include <cassert>
#include <stack>
using namespace std;

#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define repr(i, s, n) for (int i = (s); i < (int)(n); i++)
#define revrep(i, n) for (int i = (n) - 1; i >= 0; i--)
#define revrepr(i, s, n) for (int i = (n) - 1; i >= s; i--)
#define debug(x) cerr << #x << ": " << x << "\n"
#define popcnt(x) __builtin_popcount(x)

using ll = long long;
using P = pair<int, int>;

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

template<class T>
istream& operator >>(istream &is, vector<T> &v) {
    for (int i = 0; i < (int)v.size(); i++) cin >> v.at(i);
    return is;
}

template<class T, class U>
ostream& operator <<(ostream &os, pair<T, U> p) {
    cout << '(' << p.first << ", " << p.second << ')';
    return os;
}

template<class T>
void print(const vector<T> &v, const string &delimiter) { rep(i, v.size()) cout << (0 < i ? delimiter : "") << v.at(i); cout << endl; }

template<class T>
void print(const vector<vector<T>> &vv, const string &delimiter) { for (const auto &v: vv) print(v, delimiter); }

void nxt(vector<int> &d, int &digit) {
    rep(i, digit) {
        if ((abs(d[i + 1] - (d[i] + 1)) <= 1/* || i == digit - 1*/) && d[i] <= 8) {
            d[i]++;
            revrep(j, i) {
                d[j] = max(0, d[j + 1] - 1);
            }
            return;
        }
    }
    
    if (d[digit - 1] == 9) {
        d[digit] = 1;
        revrep(j, digit) {
            d[j] = max(0, d[j + 1] - 1);
        }
        digit++;
    }
    else {
        d[digit - 1]++;
        revrep(j, digit - 1) {
            d[j] = max(0, d[j + 1] - 1);
        }
        //digit++;
    }
}

int main() {
    int k;
    cin >> k;
    if (k <= 9) cout << k << endl;
    else {
        vector<int> d(11);
        d[1] = 1;
        d[0] = 0;
        d[10] = 0;
        int digit = 2;
        rep(i, k - 10) {
            nxt(d, digit);
            //print(d, " ");
        }
        
        /*cout << digit << endl;
        print(d, " ");*/
        
        int i = 9;
        while (d[i] == 0) i--;
        revrep(j, i + 1) cout << d[j];
        cout << endl;
    }
}

Measured memory_bytes: 256
#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 <cctype>
#include <string>
#include <cstring>
#include <ctime>
#include <fstream>
#include <queue>
#include <complex>
 
#define INF 100000000
#define EPS 1e-9
 
using namespace std;
 
typedef long long ll;  

#define MAX_N 101

int n,m;
int s[MAX_N + MAX_N];

vector<pair<int, int> > ans_list;

int main(){

  while(true){
    cin >> n >> m;
    if(n == 0 && m == 0)
      break;
    
    for(int i = 0; i < n+m; i++){
      cin >> s[i];
    }

    int tmpa = 1000,tmpb = 1000;
    int suma = 0, sumb = 0;

    for(int i = 0; i < n+m; i++){
      if(i < n)
	suma += s[i];
      else
	sumb += s[i];
    }

    for(int i = 0; i < n; i++){
      for(int j = n; j < n+m; j++){
	if(suma-s[i]+s[j] == sumb-s[j]+s[i]){
	  if(s[i]+s[j] < tmpa+tmpb){
	    tmpa = s[i];
	    tmpb = s[j];
	  }
	}
      }
    }

    if(tmpa == 1000)
      ans_list.push_back(make_pair(-1,-1));
    else
      ans_list.push_back(make_pair(tmpa, tmpb));

  }
  
  for(int i = 0; i < ans_list.size(); i++){
    if(ans_list[i].first == -1){
      cout << -1 << endl;
    }
    else{
      cout << ans_list[i].first << " " << ans_list[i].second << endl;
    }
  }


  return 0;

}

Measured memory_bytes: 1200
using namespace std;
#include <bits/stdc++.h>
#define rep(i,N) for(int i=0;i<(int)(N);i++)

bool isPrime(int x){
  if(x <= 1) return false;
  for(int i=2;i<int(sqrt(float(x))+1.0);i++){
    if(x%i==0)return false;
  }
  //cout << x << endl;
  return true;
}

int main(){
  int n;
  cin >> n;
  int a[n];
  rep(i,n)cin >> a[i];

  int ans = 0;
  rep(i,n) if(isPrime(a[i])) ans++;
  
  cout << ans << endl;
}


Measured memory_bytes: 3096