akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

string S; int N, maxn = 0;

int main() {
	cin >> S; N = S.size(); S = "0" + S + "0";
	for (int i = 0; i < S.size() - 1; i++) {
		int W1 = i, W2 = S.size() - 2 - i;
		if (S[i] != S[i + 1]) maxn = max(maxn, min(W1, W2));
	}
	cout << N - maxn << endl;
	return 0;
}

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

using ll = long long;

const int N = 2 * 1e5 + 10;
const ll inf = 5e18;

ll res, n;
ll a[N][4], dp[N][4];

ll go(ll idx, ll prev){
	if(idx == n + 1) return 0;
	if(dp[idx][prev] != -1) return dp[idx][prev];
	ll mx = -inf;
	for (int i = 1; i <= 3; ++i){
		if(prev == i) continue;
		mx = max(mx, a[idx][i] + go(idx + 1, i));
	}
	return dp[idx][prev] =  mx;
}


void solve(){
	cin >> n;
	for (int i = 1; i <= n; ++i){
		cin >> a[i][1] >> a[i][2] >> a[i][3];
	}
	memset(dp, -1, sizeof(dp));
	cout << go(1, 0);
}

int main(int argc, char const *argv[]){
  ios_base::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL);
  ll t = 1;
  //cin >> t;
  while(t--){
    solve();
  }
    return 0;
}

Measured memory_bytes: 18304
#include <bits/stdc++.h>
using namespace std;
int n, m;
vector<int> pa(100000),ran(100000,0),si(100000,1);

int root(int x) {
	if (pa[x] == x)
		return x;
	else {
		pa[x] = root(pa[x]);
		return pa[x];
	}
}

void unite(int x, int y) {
	x = pa[x];
	y = pa[y];
	if (x == y)
		return;
	else {
		if (ran[x] > ran[y]) {
			pa[y] = x;
			si[x] += si[y];
		}
		else {
			pa[x] = y;
			si[y] += si[x];
		}
		if (ran[x] = ran[y])
			ran[y]++;
	}
}

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

int siz(int x) {
	x = root(x);
	return si[x];
}

int main() {
	cin >> n >> m;
	vector<int> a(m), b(m);
	vector<long long> ans(m);
	for (int i = 0;i < m;i++)
		cin >> a[i] >> b[i];
	for (int i = 0;i < n;i++) {
		pa[i] = i;
	}
	ans[m - 1] = (long long)n * (n - 1) / 2;
	for (int i = m - 1;i >0;i--) {
		long long dv;
		if (same(a[i] - 1, b[i] - 1))
			dv = 0;
		else {
			dv =(long long) siz(a[i] - 1)*siz(b[i] - 1);
			unite(a[i] - 1, b[i] - 1);
		}
		ans[i - 1] = ans[i] - dv;
	}
	for (int i = 0;i < m;i++)
		cout << ans[i] << endl;
}


Measured memory_bytes: 4224
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n)for(int i=0;i<(n);i++)
#define ALL(a) (a).begin(), (a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define pb push_back
using ll = long long;
using P = pair<int, int>;
using Graph = vector<vector<int>>;

const int INF = 1001001001;

int main(){
    int n, m; cin >> n >> m;
    Graph G(n);
    rep(i, m){
        int u, v;
        cin >> u >> v; 
        --u , --v;
        G[u].pb(v);
    }
    int s, t; cin >> s >> t;
    --s, --t;
    vector<vector<int>> dist(n, vector<int>(3, -1));
    dist[s][0] = 0;
    //bfs
    queue<P> q;
    q.push(P(s, 0));
    while(!q.empty()){
        P now = q.front(); q.pop();
        int v = now.first;
        int p = now.second;
        for(auto nv : G[v]){
            int np = (p+1) % 3;
            if(dist[nv][np] == -1){
                dist[nv][np] = dist[v][p] + 1;
                q.push(P(nv, np));
            }
        }
    }
    if(dist[t][0] == -1) cout << -1 << endl;
    else cout << dist[t][0]/3 << endl;
    return 0;
}

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

typedef long long ll;
typedef long double ld;
typedef pair<int,int> ii;
typedef vector<int> vi;
typedef vector<ii> vii;

#define f first
#define s second
#define sz(x) (int)x.size()
#define all(x) begin(x), end(x)
#define rall(x) rbegin(x), rend(x)
#define pb push_back

#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define F0R(i, a) FOR(i, 0, a)
#define ROF(i, a, b) for (int i = (b); i >= (a); i--)
#define R0F(i, a) ROF(i, 0, a-1)
#define trav(x, a) for (auto& x: a)

const int MX  = 2e5+5;
const int MOD = 1e9+7;
const ll  INF = 1061109567; // 4557430888798830399LL
const ld  EPS = 1e-9;
const ld  PI  = acos(-1);

int N;
int arr[MX];
unordered_map<int,int> dp[10005];

int solve_dp(int pos, int s = 0) {
    if (pos == N) {
        return (s%10 == 0) ? 0 : s;
    }

    if (dp[pos].count(s)) return dp[pos][s];

    int res = 0;
    res = max(res,solve_dp(pos+1,s+arr[pos]));
    res = max(res,solve_dp(pos+1,s));

    dp[pos][s] = res;

    return res;
}

int main() {

    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    cin >> N;

    F0R(i,N) cin >> arr[i];

    cout << solve_dp(0) << "\n";

}


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

int main() {
  int X; cin >> X;
  for (int i = 1; i <= 1000; i++) {
    if (100 * i <= X && X <= 105 * i) {
      cout << 1 << endl;
      return 0;
    }
    if (X < 100 * i) {
      cout << 0 << endl;
      return 0;
    }
  }
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define REP(i, n) for(int i = 0; i < n; i++)
#define REPR(i, n) for(int i = n; i >= 0; i--)
#define FOR(i, m, n) for(int i = m; i < n; i++)
#define INF 2e9
#define ALL(v) v.begin(), v.end()
using namespace std;
typedef long long ll;

int main()
{
	int a, b;
	cin >> a >> b;

	if (a % 3 == 0) cout << "Possible" << endl;
	else if (b % 3 == 0) cout << "Possible" << endl;
	else if ((a + b) % 3 == 0) cout << "Possible" << endl;
	else cout << "Impossible" << endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <vector>

using namespace std;

typedef long long ll;

ll n, q, k, len[100005];
vector<ll> v[100005], d[100005];

void dfs(ll p, ll q)
{
    len[p] = q;
    for(ll i = 0; i < v[p].size(); i++)
    {
        if(len[v[p][i]] != -1) continue;
        dfs(v[p][i], d[p][i] + q);
    }
}

int main()
{
    scanf("%lld", &n);
    for(ll i = 0; i < n - 1; i++)
    {
        ll t1, t2, t3;
        scanf("%lld%lld%lld", &t1, &t2, &t3);
        v[t1].push_back(t2);
        d[t1].push_back(t3);
        v[t2].push_back(t1);
        d[t2].push_back(t3);
    }
    scanf("%lld%lld", &q, &k);
    for(ll i = 1; i <= n; i++) len[i] = -1;
    len[k] = 0;
    dfs(k, 0);
    for(ll i = 0; i < q; i++)
    {
        ll x, y;
        scanf("%lld%lld", &x, &y);
        printf("%lld\n", len[x] + len[y]);
    }
    return 0;
}


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

enum { EMPTY, OBSTACLE, START, GOAL };

constexpr int SIZE = 20;

int w, h;
int field[SIZE][SIZE];

inline bool out(int x, int y) {
	return x < 0 || y < 0 || x >= w || y >= h;
}

bool dfs(int x, int y, int rest) {
	if(rest == 0) return false;
	
	static constexpr int dx[] = {1, 0, -1, 0};
	static constexpr int dy[] = {0, 1, 0, -1};
	
	for(int d = 0; d < 4; ++d) {
		int nx = x + dx[d];
		int ny = y + dy[d];
		
		while(!(out(nx, ny) || field[ny][nx] == OBSTACLE || field[ny][nx] == GOAL)) {
			nx += dx[d];
			ny += dy[d];
		}
		
		if(out(nx, ny)) continue;
		if(field[ny][nx] == GOAL) return true;
		if(x + dx[d] == nx && y + dy[d] == ny) continue;
		
		field[ny][nx] = EMPTY;
		if(dfs(nx - dx[d], ny - dy[d], rest - 1)) return true;
		field[ny][nx] = OBSTACLE;
	}
	
	return false;
}

int main() {
	cin.tie(nullptr);
	ios::sync_with_stdio(false);
	
	while(cin >> w >> h && w) {
		int sx, sy;
		for(int y = 0; y < h; ++y) {
			for(int x = 0; x < w; ++x) {
				cin >> field[y][x];
				
				if(field[y][x] == START) {
					sx = x;
					sy = y;
				}
			}
		}

		int ans = -1;
		for(int i = 1; i <= 10; ++i) {
			if(dfs(sx, sy, i)) {
				ans = i;
				break;
			}
		}
		cout << ans << endl;
	}
	
	return EXIT_SUCCESS;
}

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

int main() {
    int n;
    cin >> n;
    vector<int> a(n,0);
    for (int i=0;i<n-1;++i){
        int tmp;
        cin >> tmp;
        a[tmp-1]++;
    }

    for (int i=0;i<n;++i){
        cout << a[i] << endl;
    }

}

Measured memory_bytes: 4052
#include<iostream>
#include<vector>
#include<queue>

using namespace std;
#define int long long
using P = pair<int,int>;
int N,M,S,T;
struct edge{int to,idx;};//行先とindex
vector<edge> G[101000];//グラフ,二次元配列っぽくあつかってる？
vector<int> A(101000),B(101000);//円とすぬけ

vector<int> dijkstra(int s,vector<int>& cost){
    vector<int> dist(101000,1e18); dist[s] = 0;//距離を無限に
    priority_queue<P,vector<P>,greater<P>> Q;
    Q.push({0,s});

    while(!Q.empty()){
        P p = Q.top(); Q.pop();
        if(dist[p.second] < p.first) continue;
        for(auto & e : G[p.second]){
            if(dist[e.to] > dist[p.second] + cost[e.idx]){
                dist[e.to] = dist[p.second] + cost[e.idx];
                Q.push({dist[e.to],e.to});
            }
        }
    }
    return dist;
}
signed main(){
    cin>>N>>M>>S>>T;
    for(int i=0;i<M;++i){
        int u,v;
        cin>>u>>v>>A[i]>>B[i];
        G[u].push_back({v,i});//駅uからつながるvと年i
        G[v].push_back({u,i});//駅vからつながる
    }

    auto yen = dijkstra(S,A);
    auto snuke = dijkstra(T,B);

    int ans = 0;
    vector<int> res;
    int base = 1e15;
    for(int i=N;i>0;--i){
        ans = max(ans,base - yen[i] - snuke[i]);
        res.push_back(ans);
    }

    for(int i = res.size()-1;i>=0;--i) cout<<res[i]<<endl;

}


Measured memory_bytes: 14204
#include <bits/stdc++.h>
#include <algorithm>
#define rep(i, n) for (int i=0; i<n; ++i)
#define all(obj) (obj).begin(),(obj).end()
using namespace std;
typedef long long ll;
long long GCD(long long x, long long y) { return y ? GCD(y, x%y) : x; }

int main(){
    int N, M, X;
    int ans = 1001001001;
    cin >> N >> M >> X;
    vector<vector<int>> A(N, vector<int>(M));
    vector<int> C(N);
    rep(i, N){
        cin >> C[i];
        rep(j, M) cin >> A[i][j];
    }
    for(int bit=0; bit < (1<<12); ++bit){
        int money = 0;
        vector<int>su(M, 0);
        bitset<12> s(bit);
        for(int i=0; i<12; ++i){
            if(i>=N) continue;
            if(s.test(i)==1){
                for(int j=0; j<M; ++j){
                    su[j]+=A[i][j];
                }
                money+=C[i];
            }
        }
        bool flag = true;
        for(int i=0; i<M; ++i){
            if(su[i]<X) flag = false;
        }
        if(flag) ans = min(ans, money);
    }
    if(ans==1001001001){
        cout << -1 << endl;
        return 0;
    }
    cout << ans << endl;
    return 0;
}


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

typedef long long ll;
#define REP(i,n) for(int i=0,_n=(int)(n);i<_n;++i)
#define ALL(v) (v).begin(),(v).end()
#define CLR(t,v) memset(t,(v),sizeof(t))
template<class T1,class T2>ostream& operator<<(ostream& os,const pair<T1,T2>&a){return os<<"("<<a.first<<","<<a.second<< ")";}
template<class T>void pv(T a,T b){for(T i=a;i!=b;++i)cout<<(*i)<<" ";cout<<endl;}
template<class T>void chmin(T&a,const T&b){if(a>b)a=b;}
template<class T>void chmax(T&a,const T&b){if(a<b)a=b;}


int nextInt() { int x; scanf("%d", &x); return x;}

int main2() {
  int a = nextInt();
  int b = nextInt();
  int n = b - a;
  cout << n * (n+1) / 2 - b << endl;
  return 0;
}

int main() {
  for (;!cin.eof();cin>>ws)
    main2();
  return 0;
}


Measured memory_bytes: 256
#include <stdio.h>

int main(void)
{
	int n = 0;		//整数の個数
	int a[10000];	//数値を入れる配列
	int max = 0;	//最大値
	int min = 0;	//最小値
	long long sum = 0;	//合計
	int i = 0;

	//整数の数を入力する
	scanf("%d", &n);

	//整数を入力する
	for (i = 0; i < n; i++)
	{
		scanf("%d", &a[i]);
	}

	max = min = a[0];
	sum += a[0];
	for (i = 1; i < n; i++)
	{
		if (a[i] > max)
			max = a[i];
		if (a[i] < min)
			min = a[i];
		sum += a[i];
	}

	printf("%d %d %ld\n", min, max, sum);

	return 0;
}


Measured memory_bytes: 2112
#include <algorithm>
#include <functional>
#include <iostream>
#include <numeric>
#include <vector>

using namespace std;

#define ALL(x) begin(x), end(x)

int main() {
  int N, K; 
  cin >> N >> K;
  vector<int> l(N);
  for (int i = 0; i < N; i++) {
    cin >> l[i];
  }
  sort(ALL(l),greater<>());
  cout << accumulate(begin(l),begin(l)+K,0) << endl;
  return 0;
}


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

bool is_even(std::size_t n) { return n % 2 == 0; }

int main() {
  std::string s;
  std::cin >> s;

  std::size_t wb = 0;
  std::size_t bw = 0;

  for (std::size_t i = 0; i < s.size(); ++i) {
    if (is_even(i)) {
      if (s[i] == '0')
        ++wb;
      else
        ++bw;
    } else {
      if (s[i] == '1')
        ++wb;
      else
        ++bw;
    }
  }

  std::cout << std::min(bw, wb) << std::endl;
}


Measured memory_bytes: 512
#!/usr/bin/env python3
import bisect
import collections
import sys

sys.setrecursionlimit(1000000)
ACMOD = 1000000007
INF = 1 << 62


def solve(N: int, A: "List[int]", Q: int, B: "List[int]", C: "List[int]"):
    _sum = sum(A)
    ac = collections.Counter(A)
    for i in range(Q):
        b, c = B[i], C[i]

        diff = ac[b] * (c - b)
        _sum += diff
        ac[c] += ac[b]
        ac[b] = 0
        print(_sum)
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word

    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    Q = int(next(tokens))  # type: int
    B = [int()] * (Q)  # type: "List[int]"
    C = [int()] * (Q)  # type: "List[int]"
    for i in range(Q):
        B[i] = int(next(tokens))
        C[i] = int(next(tokens))
    solve(N, A, Q, B, C)


if __name__ == '__main__':
    main()


Measured memory_bytes: 90608
#include <iostream>
#include <string>
#include <algorithm>
#include <utility>
#include <iomanip>
#include <functional>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <vector>
#include <cmath>
#include <cctype>
#include <cstdio>
#define ll long long
#define INF 1000000000000000001
#define MOD 1000000007
using namespace std;



int main(){
    int N;
    cin >> N;
    ll a[100000];
    for(int i=0; i<N; i++){
        cin >> a[i];
    }
    
    if(N%3==0){
        ll num[3]={};
        ll numa[3]={};
        ll numcnt=0;
        for(int i=0; i<N; i++){
            int exist_num=0;
            for(int n=0; n<numcnt; n++){
                if(numa[n]==a[i]){
                    num[n]++;
                    exist_num=1;
                }
            }
            
            if(exist_num==0){
                if(numcnt==3){
                    cout<<"No"<<endl;
                    return 0;
                }else{
                    numa[numcnt]=a[i];
                    num[numcnt]=1;
                    numcnt++;
                }
            }
                   
        }
        
        if(numcnt==3 && num[0]*numcnt==N && num[1]*numcnt==N && num[2]*3==N && ((numa[0] ^ (numa[1] ^ numa[2]))==0)){
            cout<<"Yes"<<endl;
        }else if(numcnt==1 && num[0]==N && ((numa[0]^numa[0])^numa[0])==0){
            cout<<"Yes"<<endl;
        }else if(numcnt==2 && max(num[0],num[1])*3==N*2 && min(num[0],num[1])*3==N){
            if(num[0]>=num[1]){
                if(numa[1]==0){
                    cout<<"Yes"<<endl;
                }else{
                    cout<<"No"<<endl;
                }
            }else{
                if(numa[0]==0){
                    cout<<"Yes"<<endl;
                }else{
                    cout<<"No"<<endl;
                }
            }
        }else{
            cout<<"No"<<endl;
        }
    }else{
        int ans=1;
        for(int i=1; i<N; i++){
            if(a[i]!=a[0]){
                ans=0;
                break;
            }
        }
        cout<<(ans?"Yes":"No")<<endl;
    }
    return 0;
}


Measured memory_bytes: 1024
#include <iostream>
#include <functional>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <string>
#include <sstream>
#include <complex>
#include <vector>
#include <list>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <set>
using namespace std;
typedef long long unsigned int ll;
#define rep(i, n) for(int i = 0; i < (int)(n); i++)

int main()
{
    ll N, K;
    cin >> N >> K;
    vector<ll> v;
    ll count = 0;
    if ((N + 1) / K >= 2) {
        cout << "YES" << endl;
    } else {
        cout << "NO" << endl;
    }
    //cout << count << endl;
    return 0;
}



Measured memory_bytes: 256
n=int(input())
S=input()
s=[]
s0=S.count("E",1,n)
slast=S.count("W",0,n-1)
s.append(s0)
for i in range(1,n):
    si=s[i-1]
    if S[i-1:i+1]=="EE":
        si+=-1
    if S[i-1:i+1]=="WW":
        si+=1
    s.append(si)
s.append(slast)
print(min(s))

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

using namespace std;
typedef long long ll;
typedef vector<ll> vl;
typedef vector<string> vs;
typedef pair<ll, ll> pair_t;
using Graph = vector<vector<ll>>;

#define FOR(i, a, b) for (ll i = (a); i < (b); i++)
#define REP(i, n) FOR(i, 0, n)
/***** define constant start *******/
const ll MOD = 1000000007;
const double PI = 3.1415926535897932;
const ll INF = 1 << 29;
/****** define constant end ********/
/****** define variable start ******/
ll a, b, c, d, e, f;
/******* define variable end *******/
ll solve() {
	cin >> a >> b >> c >> d >> e >> f;
	long double max_water = 100 * (long double)f / (100 + e);
	ll water;
	ll suger = 0;
	ll water_ans = 100 * a;
	ll noudo_bo = 0;
	ll noudo_si = INF;
	REP(i, f / (100 * a) + 10){
		REP(j, f / (100 * b) + 10){
			water = i * 100 * a + j * b * 100;
			REP(k, f/c + 10){
				REP(l, f/d + 10){
					if(noudo_bo * (water + k * c + l * d) < 100 * (k * c + l * d) * noudo_si&& water + k * c + l * d <= f && water * e >= (k * c + l * d) * 100){
						suger = k * c + l * d;
						water_ans = water;
						noudo_bo = 100 * (k * c + l * d);
						noudo_si = (water + k * c + l * d);
					}
				}
			}
		}
	}

	cout << suger + water_ans << " "<< suger << endl;
	return 0;
}
int main() {
	// clock_t start = clock();
	cout << std::fixed << std::setprecision(10);
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	ll end_solve = solve();
	/*
	clock_t end = clock();
	const double time = static_cast<double>(end - start) / CLOCKS_PER_SEC *
	1000.0; printf("time %lf[ms]\n", time);
	*/

	return (int)end_solve;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define F(i,a,b) for(ll i=a;i<=(b);++i)
#define dF(i,a,b) for(int i=a;i>=(b);--i)
#define inf 0x3f3f3f3f
#define infll 0x3f3f3f3f3f3f3f3f
#define pb push_back
#define maxnkp make_pair
#define fi first
#define se second
#define eps 1e-7
#define PI acos(-1.0)
using namespace std;
typedef long long ll;
const int mods = 1e9+7;
const int maxn = 2e5+10;
const int N = 1e5+10;
const int E = 1e6+10; 

int n;
int m;
vector<int> g[maxn];
bool vis[maxn];
int ans,cnt;
 
void dfs(int x){
	cnt++;
	vis[x] = 1;
	for(int i = 0;i<g[x].size();i++){
		int p = g[x][i];
		if(vis[p]) continue;
		else dfs(p);
	}
}
 
int main(){
	cin>>n>>m;
	int u,v;
	F(i,1,m){
		cin>>u>>v;
		g[u].pb(v);
		g[v].pb(u);
	}
	F(i,1,n){
		if(vis[i]) continue;
		else{
			cnt = 0;
			dfs(i);
			ans = max(ans,cnt);
		} 
	}
	cout<<ans<<endl;
}

Measured memory_bytes: 20836
import functools
import operator

n = int(input())
a_list = list(map(int, input().split()))

if 0 in a_list:
    ans = 0
else:
    k = len(a_list) - a_list.count(1)
    # print(k)
    if k > 60:
        ans = -1
    else:
        ans = functools.reduce(operator.mul, a_list)
        if ans > 10 ** 18:
            ans = -1
        else:
            pass
print(ans)


Measured memory_bytes: 82212
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define ff first
#define ss second
#define quick                    \
    ios::sync_with_stdio(false); \
    cin.tie(0);
#define time cerr << (0.1 * clock()) / CLOCKS_PER_SEC << endl;
#define mod 1000000007
typedef long long ll;
typedef pair<ll, ll> pl;
#define forn(n) for (ll i = 0; i < ll(n); i++)

void solve() {
    double n;
    cin >> n;
    double od = floor((n + 1) / 2);
    cout << fixed << setprecision(9) << od / n << '\n';
}

int main() {
    quick;
    solve();
    // ll t;
    // cin >> t;
    // while (t--) {
    //     solve();
    // }
}

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

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

Measured memory_bytes: 3616
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define rep(i,n) FOR(i,0,n)
#define repr(i,n) for(int i=(n)-1;0<=i;--i)
#define each(e,v) for(auto&& e:(v))
#define all(v) begin(v),end(v)
#define dump(x) cerr<<#x<<": "<<(x)<<endl
#define INF 100000000
#define IINF 9999999999999;
using vint = std::vector<int>;
using ll = long long;
using vll = std::vector<ll>;
template <class T> void chmin(T& a, const T& b) { a = std::min(a, b); }
template <class T> void chmax(T& a, const T& b) { a = std::max(a, b); }

//original problem

int prime[25] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97};
string S;
int B;
int decomposition_of_numbers[101];
int prime_filling_up[101];

int main() {
    vector<int> A;
    rep(i, 3) {
        int temp;
        cin >> temp;
        A.push_back(temp);
    }
    sort(A.begin(), A.end());
    int ans = 0;
    ans += abs(A[1] - A[0]);
    ans += abs(A[2] - A[1]);
    cout << ans << endl;
}


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

int main()
{
    int n, min{10000000};
    scanf("%d", &n);
    for (int i = 0; i < n; i++)
    {
        int a, count{};
        scanf("%d", &a);
        while (!(a & 1))
        {
            count++;
            a >>= 1;
        }
        if (count < min) min = count;
    }
    printf("%d\n", min);

    return 0;
}

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

int roof(int x)
{
  if (x % 10 == 0) {
    return x;
  } else {
    return x + 10 - (x % 10);
  }
}

int main()
{
  int a, b, c, d, e;
  std::vector<int> v(5);
  std::cin >> v.at(0) >> v.at(1) >> v.at(2) >> v.at(3) >> v.at(4);
  int res = INT_MAX;
  do {
    res = std::min(res, roof(v.at(0)) + roof(v.at(1)) + roof(v.at(2)) + roof(v.at(3)) + v.at(4));
  } while (std::next_permutation(v.begin(), v.end()));
  std::cout << res << '\n';
  return 0;
}


Measured memory_bytes: 256
#include<stdio.h>
#define _CRT_SECURE_NO_WARNINGS

int a, b, c, x, y, z;

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

	

	if (b > c) {
		x = b;
		b = c;
		c = x;
	}

    if (a > b) {
		y = a;
		a = b;
		b = y;
	}

	if (b > c) {
		z = b;
		b = c;
		c = z;
	}

	printf("%d %d %d\n", a, b, c);

	return 0;

}

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

int main() {
	int n; cin >> n;
	vector<int> h(n); rep(i, 0, n) cin >> h[i];

	int ans = 0;
	vector<int> vec(n - 1);
	rep(i, 0, n - 1) vec[i] = h[i] - h[i + 1];
	rep(i, 0, n - 1) {
		int count = 0;
		while (vec[i] >= 0 && i < n - 1) {
			count++;
			i++;
		}
		ans = max(ans, count);
	}

	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 1024
let n = stdin.ReadLine() |> int
let s = [| for _ in 1.. n -> stdin.ReadLine()|]

let combi2 x =int64 x * int64 (x-1L) / 2L
s |> Seq.map (fun str -> str.ToCharArray() |> Seq.countBy(fun x -> x ))
|> Seq.countBy (fun x -> x |> Set.ofSeq)
|> Seq.sumBy (fun (_, count) -> combi2 <| int64 count)
|> stdout.WriteLine

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

const int vmax=10010;
const int inf=1<<28;
struct edge{int to,cap,cost,rev;};
vector<edge> graph[vmax];

int h[vmax],dist[vmax];
int pv[vmax],pe[vmax];
typedef tuple<int,int> state;

void add_edge(int from,int to,int cap,int cost){
	graph[from].push_back({to,cap,cost,(int)graph[to].size()});
	graph[to].push_back({from,0,-cost,(int)graph[from].size()-1});
}

int min_cost_flow(int s,int t,int n){
	int res=0;

	// Graph is DAG
	fill(h,h+n,inf);
	h[s]=0;
	rep(v,n){
		if(h[v]==inf) continue;
		rep(i,graph[v].size()){
			edge &e=graph[v][i];
			if(e.cap==0) continue;
			h[e.to]=min(h[e.to],h[v]+e.cost);
		}
	}

	// ????????¶?????????
	while(h[t]<0){
		priority_queue <state,vector<state>,greater<state> > q;
		fill(dist,dist+n,inf);
		dist[s]=0;
		q.push(state(0,s));
		while(!q.empty()){
			int cost,v;
			tie(cost,v)=q.top();q.pop();
			if(dist[v] < cost) continue;
			rep(i,graph[v].size()){
				edge &e=graph[v][i];
				if(e.cap>0&&dist[e.to]>dist[v]+e.cost+h[v]-h[e.to]){
					dist[e.to]=dist[v]+e.cost+h[v]-h[e.to];
					pv[e.to]=v,pe[e.to]=i;
					q.push(state(dist[e.to],e.to));
				}
			}
		}
		if(dist[t]==inf) return -1;
		rep(v,n) h[v]+=dist[v];

		int d=inf;
		for(int v=t;v!=s;v=pv[v]) d=min(d,graph[pv[v]][pe[v]].cap);
		res+=d*h[t];
		for(int v=t;v!=s;v=pv[v]){
			edge &e=graph[pv[v]][pe[v]];
			e.cap-=d;
			graph[v][e.rev].cap+=d;
		}
	}
	return res;
}

const int infinity=1<<20;
int dp[110];

int main(void){
	int n,m;
	cin >> n >> m;
	vector<tuple<int,int,int>> ary;
	rep(i,m){
		int a,b,c;
		cin >> a >> b >> c;
		add_edge(a,b,infinity-1,-c);
		add_edge(a,b,1,-c-infinity);
		ary.push_back(make_tuple(a,b,c));
	}

	sort(ary.begin(),ary.end());
	for(auto &it:ary){
		int x,y,s;
		tie(x,y,s)=it;
		dp[y]=max(dp[y],dp[x]+s);
	}

	add_edge(n-1,n,infinity,dp[n-1]);

	cout << min_cost_flow(0,n,n+1)+m*infinity << endl;
	return 0;
}

Measured memory_bytes: 1612
def solve(n, m, v, p, a_list):
    a_list_s = sorted(a_list, reverse=True)
    # member
    # vote: v
    # problem: p
    base_bar = a_list_s[p - 1]
    res = p
    space = 0
    for i in range(p, n):
        if a_list_s[i] + m - base_bar < 0:
            break
        space_now = space + (a_list_s[i] + m - base_bar) * (i - p + 1)
        v_now = max(v - (n - i) - (p - 1), 0)
        if space_now >= v_now * m:
            res += 1
        space += base_bar - a_list_s[i]

    return res


def main():
    n, m, v, p = map(int, input().split())
    a_list = list(map(int, input().split()))
    res = solve(n, m, v, p, a_list)
    print(res)


def test():
    assert solve(6, 1, 2, 2, [2, 1, 1, 3, 0, 2]) == 5
    assert solve(6, 1, 5, 2, [2, 1, 1, 3, 0, 2]) == 3
    assert solve(10, 4, 8, 5, [7, 2, 3, 6, 1, 6, 5, 4, 6, 5]) == 8


if __name__ == "__main__":
    test()
    main()


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

int main() {
  	long long int N;;
  	cin >> N;
  	long long int A[N + 1];
  	for (int i = 0; i < N + 1; i++) cin >> A[i];
  
  	long long int dp1[N + 1], dp2[N + 1];
  	dp1[N] = A[N];
  	dp2[N] = A[N];
  	for (int i = N - 1; i >= 0; i--){
      	dp1[i] = (dp1[i + 1] + 1) / 2;
      	dp2[i] = dp2[i + 1];
      	dp1[i] += A[i];
      	dp2[i] += A[i];
    }
  
  	long long int res = 1;
  	long long int count[N + 1];
  	count[0] = 1;
  	bool flag = false;
  	for (int i = 1; i < N + 1; i++){
      	res *= 2;
      	if (res > dp2[i]) res = dp2[i];
      	if (res < dp1[i]) {
          	flag = true;
          	break;
        }
      	count[i] = res;
      	res -= A[i];
    }
  
  	if (N == 0) {
      	if (A[0] == 1) cout << 1 << endl;
      	else cout << -1 << endl;
    }
  	else if (flag == true || A[0] != 0) cout << -1 << endl;
  	else {
      	long long int ans = 0;
      	for (long long int i = 0; i < N + 1; i++){
          	ans += count[i];
        }
      	cout << ans << endl;
    }
}

Measured memory_bytes: 6748
#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() {
    int X;
    cin >> X;

   	if(X>=30){
       cout << "Yes" << endl;
    }else{
      cout << "No" << endl;
    }
    return 0;
}

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

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

int main()
{
    int N, K;
    string S;
    cin >> N;
    cin >> S;
    cin >> K;

    char numberK = S[K-1];
    for(int i = 0; i < S.size(); i++)
    {
        if (S[i] != numberK)
        {
            S[i] = '*';
        }
        else
        {
            
        }
        
    }
    cout << S << endl;
}

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

int main() {
  int H, W; cin >> H >> W;
  int input[500][500];
  for(int i=0; i<H; i++){
    for(int j=0; j<W; j++){
      cin >> input[i][j];
    }
  }
  
  vector<tuple<int,int,int,int>> output;
  int move=0;
  for(int i=0; i<H-1; i++){
    if(H==1) continue;
    for(int j=0; j<W; j++){
      if(input[i][j]%2==1){
        input[i][j]--;
        input[i+1][j]++;
        move++;
        output.push_back(make_tuple(i,j,i+1,j));
      }
    }
  }
  for(int j=0; j<W-1; j++){
    if(W==1) continue;
    if(input[H-1][j]%2==1){
      input[H-1][j]--;
      input[H-1][j+1]++;
      move++;
      output.push_back(make_tuple(H-1,j,H-1,j+1));
    }
  }
  cout << move << endl;
  for(auto i: output){
    cout << get<0>(i)+1 << " " <<  get<1>(i)+1 << " " 
      << get<2>(i)+1 << " " <<  get<3>(i)+1 << endl;
  }
}

Measured memory_bytes: 5104
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
//#include <boost/multiprecision/cpp_int.hpp>
//typedef boost::multiprecision::cpp_int ll;
typedef long double dd;
#define i_7 (ll)(1E9+7)
//#define i_7 998244353
#define i_5 i_7-2
ll mod(ll a){
    ll c=a%i_7;
    if(c>=0)return c;
    return c+i_7;
}
typedef pair<ll,ll> l_l;
ll inf=(ll)1E16;
#define rep(i,l,r) for(ll i=l;i<=r;i++)
#define pb push_back
ll max(ll a,ll b){if(a<b)return b;else return a;}
ll min(ll a,ll b){if(a>b)return b;else return a;}
void Max(ll &pos,ll val){pos=max(pos,val);}//Max(dp[n],dp[n-1]);
void Min(ll &pos,ll val){pos=min(pos,val);}
void Add(ll &pos,ll val){pos=mod(pos+val);}
dd EPS=1E-9;
#define fastio ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
///////////////////////////

struct edge{ ll to,cost; };
vector<edge> G[10];
ll d[10][10];

void dijkstra(ll s){
    fill(d[s],d[s]+10,inf);
    d[s][s]=0;
    priority_queue<l_l,vector<l_l>,greater<l_l>> que;
    que.push(l_l(0,s));
    while(!que.empty()){
        l_l p=que.top();que.pop();
        ll v=p.second;
        if(d[s][v]<p.first)continue;
        if(G[v].size()>0){
            rep(i,0,G[v].size()-1){
                edge e=G[v][i];
                if(d[s][e.to]>d[s][v]+e.cost){
                    d[s][e.to]=d[s][v]+e.cost;
                    que.push(l_l(d[s][e.to],e.to));
                }
            }
        }
    }
}


int main(){
    ll h,w;cin>>h>>w;
    ll c[10][10];
    edge e;
    rep(i,0,9){
        rep(j,0,9){
            cin>>c[i][j];
            if(i!=j){
                e.to=j;
                e.cost=c[i][j];
                G[i].pb(e);
            }
        }
    }
    rep(i,0,9){
        dijkstra(i);
    }
    ll a[h][w];
    ll ans=0;
    rep(i,0,h-1){
        rep(j,0,w-1){
            cin>>a[i][j];
            if(a[i][j]!=-1 && a[i][j]!=1){
                ans+=d[a[i][j]][1];
            }
        }
    }
    cout<<ans<<endl;
    
    return 0;
}


Measured memory_bytes: 512
"use strict";
    
function permutateWithRepetitions(
  permutationOptions,
  permutationLength
) {
  if (permutationLength === 1) {
    return permutationOptions.map(permutationOption => [permutationOption]);
  }

  // Init permutations array.
  const permutations = [];

  // Get smaller permutations.
  const smallerPermutations = permutateWithRepetitions(
    permutationOptions,
    permutationLength - 1
  );

  // Go through all options and join it to the smaller permutations.
  permutationOptions.forEach((currentOption) => {
    smallerPermutations.forEach((smallerPermutation) => {
      permutations.push([currentOption].concat(smallerPermutation));
    });
  });

  return permutations;
}

const main = arg => {
    arg = arg.trim().split("\n");
    const N = parseInt(arg[0].split(" ")[0]);
    const M = parseInt(arg[0].split(" ")[1]);
    
    const info = arg.slice(1, M + 1);
    const p = arg.slice(-1)[0].split(" ").map(n=>parseInt(n));
    
    const combos = permutateWithRepetitions([0, 1], N);
    let answer = 0;

    for(let i in combos) {
        let lightOn = 0;

        for(let j=0; j<M; j++) {
            let temp = info[j].split(" ").map(n=>parseInt(n));
            let k = temp[0];
            let s = temp.slice(1, k + 1);
            
            let cnt = 0;
            
            for(let k=0; k<s.length; k++) {
                if(combos[i][s[k] - 1] === 1) cnt++;
            }

            if(cnt % 2 === p[j]) {
                lightOn++;
            }
        }
        
        if(lightOn === M) {
            answer++;
        }
    }
    
    console.log(answer);
}
main(require('fs').readFileSync('/dev/stdin', 'utf8'));

Measured memory_bytes: 10924
#include <bits/stdc++.h>
using namespace std;
int main()
{
  int N;
  cin>>N;
  char c;
  bool isThree = true;
  for(int i=0;i<N;i++) {
    cin.get(c);
    if (c=='\n') continue;
    if (isThree && c == 'Y')  {
      isThree = false;
    }
  }
  if (isThree) cout << "Three" << endl;
  else cout << "Four" << endl;
}


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

typedef long long ll;
typedef pair<ll,ll> P;

const double PI = 3.14159265358979323846;
const double EPS = 1e-12;
const ll INF = 1LL<<29;
const ll mod = 1e9+7;

#define rep(i, a, b) for(ll (i) = (a); (i) < (b);++i)

int main()
{
  char A[5];
  rep(i, 0, 5) cin >> A[i];
  int a = A[0] - '0', b = A[1] - '0', c = A[2] - '0', d = A[3] - '0';

  if (a+b+c+d == 7) printf("%d+%d+%d+%d=7\n", a, b, c, d);
  else if (a-b+c+d == 7) printf("%d-%d+%d+%d=7\n", a, b, c, d);
  else if (a+b-c+d == 7) printf("%d+%d-%d+%d=7\n", a, b, c, d);
  else if (a+b+c-d == 7) printf("%d+%d+%d-%d=7\n", a, b, c, d);
  else if (a-b-c+d == 7) printf("%d-%d-%d+%d=7\n", a, b, c, d);
  else if (a+b-c-d == 7) printf("%d+%d-%d-%d=7\n", a, b, c, d);
  else if (a-b+c-d == 7) printf("%d-%d+%d-%d=7\n", a, b, c, d);
  else if (a-b-c-d == 7) printf("%d-%d-%d-%d=7\n", a, b, c, d);
  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define st first
#define nd second
#define mp make_pair
#define pb push_back
#define sol (k+k)
#define sag (k+k+1)
#define orta ((bas+son)/2)
#define coc g[node][i]
#define mod 1000000007
#define inf 1000000009
#define N 1000005
using namespace std;

typedef long long ll;
typedef pair < int , int > ii;

int n, m;

int main() {
	// freopen("in.txt", "r", stdin);
	// freopen("out.txt", "w", stdout);
	scanf("%d %d",&n ,&m);
	printf("%d\n", (n + m - 1)/m);
	return 0;
}

Measured memory_bytes: 256
from collections import deque
A,B,C,D = list(input())

dq = deque()
dq.append("")
while dq:
    op = dq.pop()
    if len(op) == 3:
        res = A + op[0] + B + op[1] + C + op[2] + D
        if eval(res) == 7:
            ans = res + "=7"
            print(ans)
            break
    else:
        dq.append(op+"+")
        dq.append(op+"-")

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

int main(){
    int N, A, B; cin >> N >> A >> B;

    if((B-A)%2  == 1 ){
        cout << "Borys" << endl;
    }

    else{
        cout << "Alice" << endl;
    }
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i, n) for(ll i = 0; i < n; i++)
#define repr(i, n) for(ll i = n; i >= 0; i--)
#define inf LLONG_MAX
#define all(v) v.begin(), v.end()
using namespace std;
typedef long long ll;
typedef vector<ll> vll;
typedef vector<vll> vvll;

int main()
{
	ll n;
	cin >> n;
	vvll c(10, vll(10));
	for (int i = 1; i <= n; i++) {
		string _i = to_string(i);
		c[_i[0] - '0'][_i[_i.size()-1] - '0']++;
	}

	ll cnt = 0;
	rep(i, 10) rep(j, 10) {
		cnt += c[i][j] * c[j][i];
	}
	cout << cnt << endl;
	return 0;
}

Measured memory_bytes: 256
#include <stdio.h>
#define _USE_MATH_DEFINES
#include <math.h>
#include <vector>
#include <algorithm>

using namespace std;

int main(){
    long a, b, k;
    scanf("%ld %ld %ld", &a, &b, &k);
    if(a + b <= k){
        printf("%ld %ld", 0, 0);
    } else if (a <= k){
        printf("%ld %ld", 0, a+b-k);
    } else{
        printf("%ld %ld", a-k, b);
    }
    
    return 0;
}


Measured memory_bytes: 3208
//  cd Desktop/Atcoder
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define rep(i,n) for(i=0;i<(n);i++)
#define ll long long
#define ull unsigned long long
#define MOD 1000000007

int main(){
    ll i,n,a[200002]={},sum=0,tmp=0;
    scanf("%lld",&n);
    rep(i,n){
        scanf("%lld",&a[i]);
        sum^=a[i];
    }
    rep(i,n) printf("%lld ",sum^a[i]);
    return 0;
}


Measured memory_bytes: 4056
#include "bits/stdc++.h"
using namespace std;
const int maxn = 1111;
long long cnt[3][2];
int main(){
    int n, p;
    scanf("%d %d", &n, &p);
    vector<int> arr[3];
    int len[3];
    len[0] = len[1] = len[2] = n/3;
    while(len[0] + len[1] + len[2] != n) len[2]++;
    for(int e = 0; e < 3; e++){
        arr[e].resize(len[e]);
        for(int &v:arr[e])
            scanf("%d", &v);
    }
    for(int e = 0; e < 3; e++){
        for(int f = 1; f < (1 << len[e]); f++){
            int sum = 0;
            for(int g = 0; g < len[e]; g++)
                if(f & (1 << g))
                    sum += arr[e][g];
            cnt[e][sum&1]++;
        }
    }
    long long ans = 0;
    for(int e = 0; true; e++){
        int cur = e;
        int st[3];
        long long res = 1, sum = 0;
        for(int t = 0; t < 3; t++) st[t] = cur%3, cur /= 3;
        if(cur > 0) break;
        for(int t = 0; t < 3; t++){
            if(st[t] == 0) res *= cnt[t][0];
            if(st[t] == 1) res *= cnt[t][1], sum++;
        }
        sum %= 2;
        if(sum == p) ans += res;
    }
    pi:;
    printf("%lld\n", ans);
    return 0;
}


Measured memory_bytes: 256
// fuck rating
// experience matters

#include <bits/stdc++.h>

#define fast                          \
    ios_base::sync_with_stdio(false); \
    cin.tie(0);                       \
    cout.tie(0);

#define ll long long
#define ld long double
#define pb push_back
#define mkpr make_pair
#define fi(i,a,b) for (int i=a;i<b;i++)
#define vll vector<ll>
#define vch vector<char>
#define vst vector<string>
#define vpll vector<pll>
#define vii vector<int>
#define vvl vector<vector<ll>>
#define rev(v) reverse(v.begin(),v.end())
#define srt(v) sort(v.begin(),v.end())
#define rsrt(v) sort(v.rbegin(), v.rend())
#define mxe(v) *max_element(v.begin(),v.end())
#define pii pair<int, int>
#define pll pair<ll, ll>
#define ff first
#define ss second
#define mll map<ll, ll>
#define gcd(a, b) __gcd(a, b)
#define lcm(a, b) ((a)*1ll * (b)) / gcd(a, b)
#define nl "\n"
#define sp " "
#define sz(x)  (int)x.size()

using namespace std;

double PI = (acos(-1));
ll md = 1000000007;
//ll md = 998244353;
ll pw(ll a, ll b){ll c=1,m=a;while (b){if (b&1)c=(c*m);m=(m*m);b/=2;}return c;}
ll pwmd(ll a, ll b){ll c = 1, m = a;while (b){if (b & 1)c = ((c * m)) % md;m = (m * m) % md;b /= 2;}return c;}
ll modinv(ll n){return pwmd(n, md - 2);}
ll nc2(ll n){return (1ll * n * (n - 1)) / 2;}
ll nsum(ll n){return (1ll * n * (n + 1)) / 2;}
bool prime(ll a){for(int i=2;i*i<=a;i++){if(a%i==0)return false;}return true;}
ll ceel(ll a,ll b){if(a%b==0) return a/b;else return a/b+1;}


#define MAX_SIZE 1005
void Sieve(vector<int> &primes){bool IsPrime[MAX_SIZE];memset(IsPrime, true, sizeof(IsPrime));
for (int p = 2; p * p < MAX_SIZE; p++){if (IsPrime[p] == true){
            for (int i = p * p; i < MAX_SIZE; i += p)IsPrime[i] = false;}}
    for (int p = 2; p < MAX_SIZE; p++)if (IsPrime[p])primes.push_back(p);}
        


vector<char> sml={'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'};
vector<char> cap={'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'};



//---------VIPUL SHARMA----------\\


void solve(){
    ll a;
    cin>>a;
    cout<<((pwmd(10,a)-(2*pwmd(9,a))+pwmd(8,a)+md)%md+md)%md<<nl;
}



int main(){
    //vector<int> primes;
    //Sieve(primes);

    fast
    ll tests=1;
    //cin>>tests;
    while(tests--){
        solve();
    }
    
    return 0;
}










Measured memory_bytes: 3652
#define _USE_MATH_DEFINES
#include <iostream>
#include <string>
#include <cctype>
#include <algorithm>
#include <cmath>
#include <climits>
#include <list>
#include <stdio.h>
#include <string.h>
#include <math.h>

using namespace std;

int main()
{
	double a, b, c, C, S, L, h;
	cin >> a >> b >> C;
	C = C * M_PI / 180;
	h = b * sin(C);
	S = a * h / 2;
	c = sqrt(pow(a, 2) + pow(b, 2) - 2 * a*b*cos(C));
	L = a + b + c;
	printf("%.8f %.8f %.8f\n", S, L, h);
	return 0;
}

Measured memory_bytes: 1240
#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < (int)(n); i++)
using namespace std;
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 (b<a) {a=b; return 1;} return 0;}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    int a, b, c;
    cin >> a >> b >> c;
    int mx = 0;
    chmax(mx, a);
    chmax(mx, b);
    chmax(mx, c);

    int nokori = 3*mx - a - b - c;
    if (nokori&1) {
        cout << (nokori + 3) / 2 << endl;
    } else {
        cout << nokori / 2 << endl;
    }
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i, n) for (rint i = 1; i <= (n); i ++)
#define re0(i, n) for (rint i = 0; i < (int) n; i ++)
#define travel(i, u) for (rint i = head[u]; i; i = e[i].nxt)
#define rint register int
using namespace std;
     
typedef long long lo;
     
template<typename tp> inline void read(tp &x) {
	x = 0; char c = getchar(); int f = 0;
	for (; c < '0' || c > '9'; f |= c == '-', c = getchar());
	for (; c >= '0' && c <= '9'; x = (x << 3) + (x << 1) + c - '0', c = getchar());
	if (f) x = -x;
}
namespace mf {
    static const int N = 5e5 + 233;
    static const int M = 2e6 + 233;
    static const int inf = 1e8;
    struct E {
		int nxt, to, fl;
    }e[M << 1];
    int d[N], head[N], cur[N], e_cnt = 1;
    int n, s, t;
    inline void init(int _n, int _s, int _t) {
		n = _n; s = _s; t = _t;
		fill(head, head + n + 1, 0);
		e_cnt = 1;
    }
    inline void add(int u, int v, int fl) {
		e[++ e_cnt] = (E) {head[u], v, fl}; head[u] = e_cnt;
    }
    inline void link(int u, int v, int fl) {
		add(u, v, fl); add(v, u, 0);
    }
    inline bool bfs(void) {
		queue<int> q;
		fill(d, d + n + 1, -1);
		d[s] = 0; q.push(s);
		while(!q.empty()) {
			int u = q.front(); q.pop();
			for(int i = head[u]; i; i = e[i].nxt) if(e[i].fl) {
					int v = e[i].to;
					if(!~ d[v]) d[v] = d[u] + 1, q.push(v);
				}
		}
		return d[t] != -1;
    }
    inline int dfs(int u, int f) {
		if(u == t || !f) return f;
		int used = 0, t;
		for(int &i = cur[u]; i; i = e[i].nxt) if(e[i].fl) {
				int v = e[i].to;
				if(d[v] != d[u] + 1) continue;
				t = dfs(v, min(f - used, e[i].fl));
				used += t; e[i].fl -= t; e[i ^ 1].fl += t;
				if(used == f) break;
			}
		if(!used) d[u] = -1;
		return used;
    }
    inline int doit(void) {
		int fl = 0;
		while(bfs()) {
			memcpy(cur, head, sizeof (int) * (n + 2));
			fl += dfs(s, inf);
		}
		return fl;
    }
}
const int N = 5e5 + 233;
int n, cnt, a[N], b[N], p[N], q[N], x[N][2], y[N][2], vis[N];
inline void doit(int p[], int a[]) {
	memset(vis, 0, sizeof vis);
	rep (i, n) if (!vis[i]) {
		++cnt;
		for (int u = i; !vis[u]; u = p[u])
			a[u] = cnt, vis[u] = true;
	}
}

using mf::link;

int main(void) {
	read(n);
	rep (i, n) read(p[i]), ++p[i];
	rep (i, n) read(q[i]), ++q[i];
	doit(p, a); doit(q, b);
	int S = cnt + 1, T = S + 1;
	mf::init(T, S, T);
	int ans = 0;
	rep (i, n) {
		if (p[i] == q[i]) {
			if (q[i] == i) ++ans;
			else {
				link(a[i], b[i], 1);
				link(b[i], a[i], 1);
			}
		} else {
			if (q[i] == i) link(a[i], T, 1);
			else if (p[i] == i) link(S, b[i], 1);
			else link(a[i], b[i], 1);
		}
	}
	ans += mf::doit();
	cout << n - ans << "\n";
}


Measured memory_bytes: 23168
fn read<T: std::str::FromStr>() -> T {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).ok();
    s.trim().parse().ok().unwrap()
}

fn read_vec<T: std::str::FromStr>() -> Vec<T> {
    read::<String>()
        .split_whitespace()
        .map(|e| e.parse().ok().unwrap())
        .collect()
}

fn read_vec2<T: std::str::FromStr>(n: usize) -> Vec<Vec<T>> {
    (0..n).map(|_| read_vec()).collect()
}

fn read_col<T: std::str::FromStr>(n: usize) -> Vec<T> {
    (0..n).map(|_| read()).collect()
}

use std::cmp::max;
use std::collections::BTreeMap;

fn main() {
    let n: usize = read();
    let v: Vec<u32> = read_vec();

    let mut odd: BTreeMap<u32, u32> = BTreeMap::new();
    let mut even: BTreeMap<u32, u32> = BTreeMap::new();

    for i in 0..(n / 2) {
        let e = 2 * i;
        let tmp: u32;
        if let Some(x) = even.get(&v[e]) {
            tmp = x + 1;
        } else {
            tmp = 1;
        }
        even.insert(v[e], tmp);

        let o = 2 * i + 1;
        let tmp: u32;
        if let Some(x) = odd.get(&v[o]) {
            tmp = x + 1;
        } else {
            tmp = 1;
        }
        odd.insert(v[o], tmp);
    }

    let mut fste: (u32, u32) = (0, 0);
    let mut snde: (u32, u32) = (0, 0);
    for (key, val) in even.iter() {
        if *val > fste.1 {
            snde = fste;
            fste = (*key, *val);
        } else if *val > snde.1 {
            snde = (*key, *val);
        }
    }

    let mut fsto: (u32, u32) = (0, 0);
    let mut sndo: (u32, u32) = (0, 0);
    for (key, val) in odd.iter() {
        if *val > fsto.1 {
            sndo = fsto;
            fsto = (*key, *val);
        } else if *val > sndo.1 {
            sndo = (*key, *val);
        }
    }

    let n: u32 = n as u32;

    if fste.0 != fsto.0 {
        println!("{}", n - fste.1 - fsto.1);
    } else {
        println!("{}", n - max(fste.1 + sndo.1, fsto.1 + snde.1));
    }
}


Measured memory_bytes: 6396
#include<iostream>
#include<string.h>
#include<queue>
#include<map>
#include<vector>
#include <cstdlib>
#include<algorithm>
#include <cstdio>
#include <cctype>
using namespace std;
const long long INF=10000000000000LL;
typedef long long ll;
typedef pair<ll,ll> P;
ll N,M,K=1,C;
ll A,B,W;
ll T,a,b;
double v[55],D[55],Q,l,r;
ll ans=0;
//bool D[100005];
ll S[50][50]={};
string str1[55],str2="abcdefghijklmnopqrstuvwxyz";
map<string,int> m;

int main(){
	cin>>W>>A>>B;
	if(A>B+W){
		ans=A-B-W;
	}
	if(B>A+W){
		ans=B-A-W;
	}
	cout<<ans<<endl;
	return 0;
}


Measured memory_bytes: 256
# -*- coding: utf-8 -*-
N = int(input())
H = tuple(map(int, input().split()))

def calc(i, h):
    tmp_max = 0
    while stack[-1][1] > h:
        pi, ph = stack.pop()
        tmp_max = max(tmp_max, (i-pi)*ph)
        if len(stack) == 0:
            break
    if len(stack) == 0:
        stack.append([pi, h])
    elif stack[-1][1] < h:
        stack.append([pi, h])
    return tmp_max

stack = [] # loc, height
S_max = 0

for i, h in enumerate(H):
    if len(stack) == 0:
        stack.append([i, h])
    elif h > stack[-1][1]:
        stack.append([i, h])
    elif h == stack[-1][1]:
        pass
    else:
        tmp_max = calc(i, h)
        S_max = max(S_max, tmp_max)

tmp_max = calc(i+1, 0)
S_max = max(S_max, tmp_max)
print(S_max)

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

typedef long long ll;
typedef pair<int, int> pii;

#define MAXN 1010 
const int mod = 1e9 + 7;
const int INF = 1e9 + 10;

int s[MAXN][MAXN];

void add(int x1, int y1, int x2, int y2)
{
	++x1, ++y1, ++x2, ++y2;
	//cout << x1 << " " << y1 << " " << x2 << " " << y2 << endl;
	s[x1][y1]++, s[x1][y2 + 1]--;
	s[x2 + 1][y2 + 1]++, s[x2 + 1][y1]--;
}

int main()
{
	int n, k, x, y, w, ans = 0; char c;
	scanf("%d %d", &n, &k);
	for (int i = 1; i <= n; ++i)
	{
		scanf("%d %d %c", &x, &y, &c);
		w = (c == 'B')? 1 : 0;
		int dx = k - x % k, dy = k - y % k;
		int t = (x / k + y / k) & 1;
		t = (t == w);
		
		if (t == 1) add(0, 0, dx - 1, dy - 1), add(dx, dy, k, k);
		else add(0, dy, dx - 1, k), add(dx, 0, k, dy - 1);
	}
	
	/*for (int i = 1; i <= k; ++i)
	{
		for (int j = 1; j <= k; ++j)
			cout << s[i][j] << " ";
		cout << endl;
	}*/
	for (int i = 1; i <= k; ++i)
	{
		for (int j = 1; j <= k; ++j)
		{
			s[i][j] += s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1];	
			ans = max(ans, max(s[i][j], n - s[i][j]));			
		}
	}
	/*for (int i = 1; i <= k; ++i)
	{
		for (int j = 1; j <= k; ++j)
			cout << s[i][j] << " ";
		cout << endl;
	}*/
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 4224