akhauriyash/Code-Regression huggingface dataset:
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Scanner;

public class Main {

	static int count = 0;
	public static void main(String[] args) {

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

		shellSort(a);
		System.out.println(count);

		for (int i = 0; i < a.length; i++) {
			System.out.println(a[i]);
		}

	}
	static void shellSort(int[] a) {

		List<Integer> glist = new ArrayList<Integer>();
		for (int i = 1; i <= a.length; i=i*3+1) {
			glist.add(i);
		}
		Collections.reverse(glist);
		System.out.println(glist.size());
		Integer[] g = glist.toArray(new Integer[glist.size()]);
		for (int i = 0; i < g.length; i++) {
			if (i != g.length-1) {
				System.out.print(g[i]+" ");
			} else {
				System.out.println(g[i]);
			}
		}

		for (int i = 0; i < g.length; i++) {
			insertionSort(a, g[i]);
		}

	}
	static void insertionSort(int[] a, int g) {
		for (int i = g; i < a.length; i++) {
			int v = a[i];
			int j = i-g;
			while (j >= 0 && a[j] > v) {
				a[j+g] = a[j];
				j=j-g;
				count++;
			}
			a[j+g] = v;
		}
	}
}



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

// #define int long long
#define rep(i, n) for (long long i = (long long)(0); i < (long long)(n); ++i)
#define reps(i, n) for (long long i = (long long)(1); i <= (long long)(n); ++i)
#define rrep(i, n) for (long long i = ((long long)(n)-1); i >= 0; i--)
#define rreps(i, n) for (long long i = ((long long)(n)); i > 0; i--)
#define irep(i, m, n) for (long long i = (long long)(m); i < (long long)(n); ++i)
#define ireps(i, m, n) for (long long i = (long long)(m); i <= (long long)(n); ++i)
#define SORT(v, n) sort(v, v + n);
#define REVERSE(v, n) reverse(v, v+n);
#define vsort(v) sort(v.begin(), v.end());
#define all(v) v.begin(), v.end()
#define mp(n, m) make_pair(n, m);
#define cout(d) cout<<d<<endl;
#define coutd(d) cout<<std::setprecision(10)<<d<<endl;
#define cinline(n) getline(cin,n);
#define replace_all(s, b, a) replace(s.begin(),s.end(), b, a);
#define PI (acos(-1))
#define FILL(v, n, x) fill(v, v + n, x);
#define sz(x) long long(x.size())

using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using vll = vector<ll>;
using vvll = vector<vll>;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using vs = vector<string>;
using vpll = vector<pair<ll, ll>>;
using vtp = vector<tuple<ll,ll,ll>>;
using vb = vector<bool>;

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

const ll INF = 1e9;
const ll MOD = 1e9+7;
const ll LINF = 1e18;

vll G[100100];

signed main()
{
  cin.tie( 0 ); ios::sync_with_stdio( false );
  ll n,m; cin>>n>>m;
  vll h(n);
  rep(i,n) cin>>h[i];
  rep(i,m){
    ll a,b; cin>>a>>b; a--,b--;
    G[a].push_back(b);
    G[b].push_back(a);
  }
  
  
  vb visited(n);
  vb ok(n,true);
  rep(i,n){
    if(visited[i]) continue;
    visited[i]=true;
    queue<ll> q;
    q.push(i);
    while(!q.empty()){
      ll v=q.front(); q.pop();
      for(auto nv: G[v]){
        if(visited[nv]) continue;
        if(h[v]<h[nv]){
          ok[v]=false;
        }else if(h[v]>h[nv]){
          ok[nv]=false;
        }else{
          ok[v]=ok[nv]=false;
        }
      }
    }
  }
  
  ll ans=0;
  rep(i,n) if(ok[i]) ans++;
  cout<<ans<<endl;
  
}

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

int main(){
	string S;
	cin >> S;
	for(int i = 0; i < S.length(); i++){
		cout << (char)(((S[i] - 'A') + 23) % 26 + 'A');
	}
	cout << endl;
	return 0;
}


Measured memory_bytes: 3164
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

#define ll long long
#define pb push_back

ll MIN(ll num1,ll num2){
    return num1<num2?num1:num2;
}

int main(){

    while(1){
        int n,p;
        cin>>n>>p;
        if(n==0&&p==0)break;
        //cout<<n<<" "<<p<<endl;
        vector<int> stone;
        for(int i=0;i<n;i++)stone.pb(0);
        int now=0;
        while(1){
            if(p==0){
                p=stone[now];
                stone[now]=0;
            }else{
                p--;
                stone[now]++;
            }

            bool flag=true;
            for(int i=0;i<n;i++){
                if(i==now)continue;
                if(stone[i]!=0)flag=false;
            }
            if(p==0&&flag){
                cout<<now<<endl;
                break;
            }

            now++;
            if(now>=n)now=0;
        }
    }

    return 0;
}


Measured memory_bytes: 3100
using System;

namespace question4
{
    class Program2
    {
        static void Main(string[] args)
        {
            var p = new Program2();
            p.Run();
        }

        private long[] ai;
        private long[] pi;

        void Run()
        {
            var line = Console.ReadLine();
            var n = int.Parse(line.Split(' ')[0]);
            var x = long.Parse(line.Split(' ')[1]);

            ai = new long[n + 1];
            pi = new long[n + 1];

            ai[0] = 1;
            pi[0] = 1;
            for (int i = 1; i <= n; i++)
            {
                ai[i] = ai[i - 1] * 2 + 3;
                pi[i] = pi[i - 1] * 2 + 1;
            }

            var ans = this.Func(n, x);

            Console.WriteLine(ans);
        }

        long Func(int n, long x)
        {
            if( n ==0){
                return x == 1 ? 1 : 0;
            }

            if (x <= ai[n - 1] + 1)
            {
                return this.Func(n - 1, x - 1);
            }
            else if (x == ai[n - 1] + 2)
            {
                return pi[n - 1] + 1;
            }
            else if (x <= ai[n - 1] * 2 + 2)
            {
                return pi[n - 1] + 1 + this.Func(n - 1, x - (ai[n - 1] + 2));
            }
            else
            {
                return pi[n];
            }
        }
    }
}


Measured memory_bytes: 11092
import java.util.*;

public class Main {

	public static void main(String[] args) {
	 Scanner input= new Scanner(System.in);
	  
        int n,k,ans=0;
        n=input.nextInt();
        k=input.nextInt();
        if(n%k!=0)
         ans=n%k;
        System.out.println(ans);
        	
        
	}

}


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

int main() {
    long long n, k;
    cin >> n >> k;

    //long long wari;
    long long amari;
    long long ret;


    amari = n % k;
    //wari = n / k;
    if(abs(amari - k) < amari) {
        ret = abs(amari - k);
    } else {
        ret = abs(amari);
    }

    //cout << amari << endl;
    //cout << abs(amari - k) << endl;

    if(n < ret) {
        ret = n;
    }
    if(amari == 0) {
        ret = 0;
    }

    cout << ret << endl;
    return 0;
}

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

int main()
{
  int A,B,C,D,E,F;
  int res=0;
  cin >> A >> B >> C >> D >> E >> F;

  vector<int> vw;
  rep(i,F){
    rep(j,F){
      int x = i*A*100 + j*B*100;
      if( x <= F) {
        vw.push_back(x);
      }
    }
  }

  vector<int> vs;
  rep(i,F){
    rep(j, F){
      int y = i*C + j*D;
      if( y <= F) vs.push_back(y);
    }
  }

  int maxw = 0; int maxs = 0;
  double maxd = 0;
  for( auto itw=vw.begin();itw!=vw.end(); itw++ ) {
    for( auto its=vs.begin();its!=vs.end(); its++ ) {
      int x = *itw; int y = *its;
      if(x==0) continue;
      if(x + y <= F && E*x/100 >= y){
        double dx = (double)x; double dy = (double)y;
        if (maxd <= dy/(dx+dy)){
          maxw = x; maxs = y;
          maxd = dy/(dx+dy);
        }
      }
    }
  }
  cout << maxw+maxs << " " << maxs << endl;
}


Measured memory_bytes: 1400
#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < (int)(n); i++)
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define sz(x) (int)(x).size()
using namespace std;
using ll = long long;
using P = pair<int, int>;
using vi = vector<int>;
using vc = vector<char>;
using vb = vector<bool>;
using vs = vector<string>;
using vll = vector<long long>;
using vp = vector<pair<int, int>>;
using vvi = vector<vector<int>>;
using vvc = vector<vector<char>>;
using vvll = vector<vector<long long>>;
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;}

const int INF = 1001001001;
vvi to;
vi ans;
vi a;

void dfs(int v, vi& dp, int p=-1) {
    for (int u : to[v]) {
        if (u == p) continue;
        int idx = lower_bound(dp.begin(), dp.end(), a[u]) - dp.begin();
        int pre = dp[idx];
        dp[idx] = a[u];
        ans[u] = lower_bound(dp.begin(), dp.end(), INF) - dp.begin();
        dfs(u, dp, v);
        dp[idx] = pre;
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    int n;
    cin >> n;
    a.resize(n);
    rep(i, n) cin >> a[i];
    to.resize(n);
    rep(i, n-1) {
        int u, v;
        cin >> u >> v;
        u--; v--;
        to[u].pb(v);
        to[v].pb(u);
    }
    ans.resize(n);
    ans[0] = 1;

    vi dp(n, INF);
    dp[0] = a[0];
    dfs(0, dp);
    rep(i, n) cout << ans[i] << endl;
}

Measured memory_bytes: 30796
from collections import Counter,defaultdict,deque
from bisect import bisect_left
import sys,math,itertools,pprint,fractions
sys.setrecursionlimit(10**8)
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))

n = inp()
s = list(input())
q = inp()
Qs = [input().split() for i in range(q)]
upd = []
acc = [[0] * 26 for i in range(n+1)]
for i,t in enumerate(s):
    tmp = ord(t) - ord('a')
    # print(tmp)
    for j in range(26):
        if j == tmp:
            acc[i+1][j] = acc[i][j] + 1
            continue
        acc[i+1][j] = acc[i][j]
# print(acc)
for i,t in enumerate(Qs):
    a,b,c = t
    b = int(b)
    if a == '1':
        upd.append([b,ord(s[b-1])-ord('a'),ord(c)-ord('a')])
        s[b-1] = c
    else:
        c = int(c)
        cnt = 0
        now = [0] * 26
        for j in range(26):
            now[j] = acc[c][j] - acc[b-1][j]
        for j,k in enumerate(upd):
            if b <= k[0] <= c:
                now[k[1]] -= 1
                now[k[2]] += 1
        for j in range(26):
            if now[j] > 0: cnt += 1
        print(cnt)
# print(upd)
        

Measured memory_bytes: 209028
//#include <bits/stdc++.h>
#include <iostream>
#include <fstream>
#include <vector>
#include <string>
#include <cmath>
#include <algorithm>
#include <map>
#include <iomanip>
#include <stdlib.h>
#include <queue>
#include <deque>
#include <set>
#include <stack>
#include <time.h>
 
using namespace std;
 
typedef long long ll;
typedef long double ld;
typedef pair<int, int> Pii;
typedef pair<int, ll> Pil;
typedef pair<ll, ll> Pll;
typedef pair<ll, int> Pli;
 
const ll nmax = 1e9 + 7;
const ll Mod = 998244353;
const double PI = 2 * asin(1);

int N;
ll Prime_Count[100], Count[75];

int main(){
  cin >> N;
  for (int i = 2; i <= N; i++){
    int num = i;
    for (int j = 2; j <= i; j++){
      while (num % j == 0){
        Prime_Count[j]++;
        num /= j;
      }
    }
  }

  for (int i = 0; i < 100; i++){
    if (Prime_Count[i] >= 75) Count[74]++;
    else Count[Prime_Count[i]]++;
  }
  
  for (int i = 73; i >= 2; i--){
    Count[i] += Count[i + 1];
  }


  ll ans = Count[74];
  ans += Count[24] * (Count[2] - 1);
  ans += Count[14] * (Count[4] - 1);
  ans += Count[4] * (Count[4] - 1) * (Count[2] - 2) / 2;
  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 256
n=int(input())
p=[int(x) for x in input().split()]
pp=[int(x+1) for x in range(n)]
 
for i in range(n):
    buf=i+1
    if buf != p[i]:
        p[p.index(buf)]=p[i]
        p[i]=buf
        break
 
if pp==p:
    print("YES")
else:
    print("NO")

Measured memory_bytes: 3060
n, C = map(int, input().split())
cq = [[] for _ in range(C)]
stc = [tuple(map(int, input().split())) for _ in range(n)]
stc = sorted(stc, key=lambda x: x[0])

for s, t, c in stc:
    c -= 1
    if cq[c]:
        fs, ft = cq[c][-1]
        if ft != s:
            cq[c].append([s, t])
        else:
            cq[c][-1] = [fs, t]
    else:
        cq[c].append([s, t])

R = [0] * (2*10**5+2)
for qq in cq:
    for s, t in qq:
        R[2*s-1] += 1
        R[2*t+1] -= 1

from itertools import accumulate
CR = list(accumulate(R))
print(max(CR))


Measured memory_bytes: 114596
n,x,y=map(int,input().split())
x-=1
y-=1
L=[0]*(n-1)
for i in range(n-1):
    for j in range(i+1,n):
        if j<=x or i>=y:
            L[j-i-1]+=1
        elif i<=x and y<=j:
            L[x-i+j-y]+=1
        else:
            a=j-i
            b=abs(x-i)+1+abs(y-j)
            L[min(a,b)-1]+=1
for k in L:
    print(k)            

Measured memory_bytes: 3444
#include <bits/stdc++.h>
using namespace std;
/*#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
template<typename T> using gpp_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template<typename T, typename L> using gpp_map = tree<T, L, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template<typename T> using gpp_multiset = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;*/
struct fast_ios { fast_ios(){ cin.tie(0); ios::sync_with_stdio(false); cout << fixed << setprecision(20); }; } fast_ios_;
#define FOR(i, begin, end) for(int i=(begin);i<(end);i++)
#define REP(i, n) FOR(i,0,n)
#define IFOR(i, begin, end) for(int i=(end)-1;i>=(begin);i--)
#define IREP(i, n) IFOR(i,0,n)
#define Sort(v) sort(v.begin(), v.end())
#define Reverse(v) reverse(v.begin(), v.end())
#define all(v) v.begin(),v.end()
#define SZ(v) ((int)v.size())
#define Lower_bound(v, x) distance(v.begin(), lower_bound(v.begin(), v.end(), x))
#define Upper_bound(v, x) distance(v.begin(), upper_bound(v.begin(), v.end(), x))
#define Max(a, b) a = max(a, b)
#define Min(a, b) a = min(a, b)
#define bit(n) (1LL<<(n))
#define bit_exist(x, n) ((x >> n) & 1)
#define debug(x) cout << #x << "=" << x << endl;
#define vdebug(v) { cout << #v << "=" << endl; REP(i_debug, v.size()){ cout << v[i_debug] << ","; } cout << endl; }
#define mdebug(m) { cout << #m << "=" << endl; REP(i_debug, m.size()){ REP(j_debug, m[i_debug].size()){ cout << m[i_debug][j_debug] << ","; } cout << endl;} }
#define Return(ans) { cout << (ans) << endl; return 0; }
#define pb push_back
#define f first
#define s second
#define int long long
#define INF 1000000000000000000
template<typename T> istream &operator>>(istream &is, vector<T> &v){ for (auto &x : v) is >> x; return is; }
template<typename T> ostream &operator<<(ostream &os, vector<T> &v){ for(int i = 0; i < v.size(); i++) { cout << v[i]; if(i != v.size() - 1) cout << endl; }; return os; }
template<typename T1, typename T2> ostream &operator<<(ostream &os, pair<T1, T2> p){ cout << '(' << p.first << ',' << p.second << ')'; return os; }
template<typename T> void Out(T x) { cout << x << endl; }
template<typename T1, typename T2> void Ans(bool f, T1 y, T2 n) { if(f) Out(y); else Out(n); }
 
using vec = vector<int>;
using mat = vector<vec>;
using Pii = pair<int, int>;
using PiP = pair<int, Pii>;
using PPi = pair<Pii, int>;
using bools = vector<bool>;
using pairs = vector<Pii>;
 
//int dx[4] = {1,0,-1,0};
//int dy[4] = {0,1,0,-1};
//char d[4] = {'D','R','U','L'};
 
const int mod = 1000000007;
//const int mod = 998244353;
//#define Add(x, y) x = (x + (y)) % mod
//#define Mult(x, y) x = (x * (y)) % mod

#include <bits/stdc++.h>
using namespace std;
signed main(){
  string N; cin>>N;
  REP(i,N.size()){
    if(N[i]=='?') N[i]='D';
  }
  Out(N);
}


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

int main() {
  int N;
  cin >> N;
  
  int ans=-1;
  
  for (int i = 0; i <= N; i++) {
   if(int(i*1.08)==N)
     ans=i;
  }
  if(ans!=-1){
     cout << ans << endl; 
   }
    else{
     cout << ":(" << endl; 
    }
  
}

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

def main():
    N, Z, W = map(int, input().split())
    A = list(map(int, input().split()))
    """
    O(N^2)dpでも行けるそうです。以下写経：
    https://atcoder.jp/contests/abc078/submissions/14886969
    dp[turn][top]の２引数だけでいいのか、[x][y]の２引数も必要ではないかと思うが、
    考えてみれば
        dfs(0, top, x, y) = dfs(1, top', A[top], y)
                          = dfs(0, top", A[top], A[top'])
    となるので、実はdfs(0, top, x, y)はtop = Nでない限りx, yに依らない。
    """
    dp = [[-1] * N for _ in range(2)]
    def dfs(turn, top, x, y): # turn: 0 => x, 1 => y
        if top == N: return abs(x - y)
        if dp[turn][top] != -1: return dp[turn][top]
        if turn == 1:
            """
            yのターンは、top以降を取ってなるべくスコアが低くなるようなiを選ぶ
            """
            ret = 10**9
            for i in range(top, N): ret = min(ret, dfs(0, i + 1, x, A[i]))
            dp[turn][top] = ret
            return ret
        else:
            """
            xのターンは、top以降を取ってなるべくスコアが高くなるようなiを選ぶ
            """
            ret = 0
            for i in range(top, N): ret = max(ret, dfs(1, i + 1, A[i], y))
            dp[turn][top] = ret
            return ret
    
    print(dfs(0, 0, Z, W))

if __name__ == "__main__":
    main()


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


using namespace std;

int main()
{

        int a,b;
        string input;
        int size = 0;
        int count = 0;

        while(cin >> a >> b)
        {
                b += a;
                input = to_string(b);
                size = input.size();
                cout << size << endl;
                count++;
                if(count == 199){break;}
        }

}

Measured memory_bytes: 1220
#pragma comment(linker, "/STACK:512000000")
#include <bits/stdc++.h>
using namespace std;

#define all(a) a.begin(), a.end()
typedef long long li;
typedef long double ld;
void solve(__attribute__((unused)) bool);
void precalc();
clock_t start;
#define FILENAME ""

int main() {
#ifdef AIM
    string s = FILENAME;
//    assert(!s.empty());
    freopen("/home/alexandero/ClionProjects/cryptozoology/input.txt", "r", stdin);
#else
//    freopen(FILENAME ".in", "r", stdin);
//    freopen(FILENAME ".out", "w", stdout);
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
#endif
    start = clock();
    int t = 1;
#ifndef AIM
    cout.sync_with_stdio(0);
    cin.tie(0);
#endif
    precalc();
    cout.precision(10);
    cout << fixed;
    //cin >> t;
    int testNum = 1;
    while (t--) {
        //cout << "Case #" << testNum++ << ": ";
        solve(true);
    }
    cout.flush();
#ifdef AIM1
    while (true) {
      solve(false);
  }
#endif

#ifdef AIM
    cout.flush();
    auto end = clock();

    usleep(10000);
    print_stats(end - start);
    usleep(10000);
#endif

    return 0;
}

template<typename T>
T binpow(T q, T w, T mod) {
    if (!w)
        return 1 % mod;
    if (w & 1)
        return q * 1LL * binpow(q, w - 1, mod) % mod;
    return binpow(q * 1LL * q % mod, w / 2, mod);
}

template<typename T>
T gcd(T q, T w) {
    while (w) {
        q %= w;
        swap(q, w);
    }
    return q;
}
template<typename T>
T lcm(T q, T w) {
    return q / gcd(q, w) * w;
}

template <typename T>
void make_unique(vector<T>& a) {
    sort(all(a));
    a.erase(unique(all(a)), a.end());
}

template<typename T>
void relax_min(T& cur, T val) {
    cur = min(cur, val);
}

template<typename T>
void relax_max(T& cur, T val) {
    cur = max(cur, val);
}

void precalc() {
}

#define int li
const int mod = 998244353;

const int C = 300500;
int fact[C], revfact[C];
int getC(int n, int k) {
    return fact[n] * revfact[k] % mod * revfact[n - k] % mod;
}

void solve(__attribute__((unused)) bool read) {
    fact[0] = 1;
    for (int i = 1; i < C; ++i) {
        fact[i] = fact[i - 1] * i % mod;
    }
    revfact[C - 1] = binpow(fact[C - 1], mod - 2, mod);
    for (int i = C - 2; i >= 0; --i) {
        revfact[i] = revfact[i + 1] * (i + 1) % mod;
    }
    int res = 0;
    int n, A, B, K;
    cin >> n >> A >> B >> K;
    for (int x = 0; x <= n; ++x) {
        int rest = K - A * x;
        if (rest < 0 || rest % B) {
            continue;
        }
        int y = rest / B;
        if (y < 0 || y > n) {
            continue;
        }
        res += getC(n, x) * getC(n, y);
        res %= mod;
    }
    cout << res << "\n";

}

Measured memory_bytes: 4992
str = gets.chomp
a_count = 0
b_count = 0
flag = false
result = 0

str.chars.each do |s|
  if s == "<"
    if flag
      if a_count >= b_count
        result += (a_count + 1) * a_count / 2
        result += (b_count + 1) * b_count / 2 - b_count
      else
        result += (a_count + 1) * a_count / 2 - a_count
        result += (b_count + 1) * b_count / 2
      end

      a_count = 0
      b_count = 0

      flag = false
    end

    a_count += 1
  end

  if s == ">"
    flag = true if !flag

    b_count += 1
  end
end

if a_count > 0 || b_count > 0
  if flag
    if a_count >= b_count
      result += (a_count + 1) * a_count / 2
      result += (b_count + 1) * b_count / 2 - b_count
    else
      result += (a_count + 1) * a_count / 2 - a_count
      result += (b_count + 1) * b_count / 2
    end
  else
    result += (a_count + 1) * a_count / 2
    result += (b_count + 1) * b_count / 2
  end
end

puts result

Measured memory_bytes: 48012
#include<stdio.h>

int main(void)
{
	int W,H,x,y,r;
	
	scanf("%d%d%d%d%d", &W,&H,&x,&y,&r);
	
	if((x + r) > W || (y + r) > H || (x - r) < 0 || (y - r) < 0)
		printf("No\n");
	else
		printf("Yes\n");
	
	
	return 0;
}





Measured memory_bytes: 2108
/**
 * AtCoder Regular Contest 061
 * C- たくさんの数式 / Many Formulas
 *
 * bit全検索パターン
 */
#include <iostream>
using namespace std;

int main() {
  string S; cin >> S;
  size_t len{S.size()};

  long total{};
  for (size_t i{}; i < (1 << (len - 1)); ++i) {
    long temp = S[0] & 0xF;
    for (size_t j{}; j < len - 1; ++j) {
      if (i & (1 << j)) {
        total += temp;
        temp = 0;
      }
      temp *= 10;
      temp += S[j + 1] & 0xF;
    }
    total += temp;
  }

  cout << total << endl;
  return 0;
}


Measured memory_bytes: 256
import sys
#input = sys.stdin.buffer.readline

def main():
    s = list(input())
    K = int(input())
    
    l = len(s)
    for i in range(l-1):
        moji = s[i]
        if moji == "a":
            continue
        else:
            a = ord("z")-ord(moji)+1
            if a <= K:
                s[i] = "a"
                K -= a

    K %= 26
    use = ord(s[-1])+K
    if use >= 123:
        use -= 26
    s[-1] = chr(use)
    print("".join(map(str,s)))
    
if __name__ == "__main__":
    main()

Measured memory_bytes: 4792
import java.util.Arrays;
import java.util.Scanner;
import java.util.stream.Collectors;

public class Main {

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

    int N = sc.nextInt();

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

    int count = bubbleSort(A, N);

    System.out.println(Arrays.stream(A).mapToObj(String::valueOf).collect(Collectors.joining(" ")));
    System.out.println(count);
  }

  public static int bubbleSort(int[] a, int n) {
    int count = 0;
    for (int i = 0; i < n; i++) {
      for (int j = n-1; j > i; j--) {
        if (a[j] < a[j-1]) {
          int tmp = a[j];
          a[j] = a[j-1];
          a[j-1] = tmp;
          count++;
        }
      }
    };

    return count;
  }
}


Measured memory_bytes: 32592
#include<bits/stdc++.h>
#define int long long
#define ll long long
#define maxN 100005
#define rep(i,n) for(int i=0;i<n;i++)
#define refv(i,l,r) for(int i=l;i<r;i++)
#define rerv(i,l,r) for(int i=r;i>=r;i--)
#define pi pair<ll,ll>
#define pii pair<ll,pair<ll,ll> > 
#define pb push_back
#define mp make_pair
#define F first
#define S second
#define mod 1000000007
#define printvector(v) for(int i= 0;i<v.size();i++) {cout<<v[i]<<" ";} cout<<endl;
#define printset(s) for(auto it = s.begin();it!=S.end();it++){cout<<*it<<" ";} cout<<endl;
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL); 
using namespace std;


int32_t main()
{
	fastio
    int a,b;
    cin>>a>>b;
    int ans=(a*3+b)/2;
    cout<<ans<<endl;
}

Measured memory_bytes: 256
X = int(input())
if 400 <= X <= 599:
    print(8)
elif 600 <= X <= 799:
    print(7)
elif 800 <= X <= 999:
    print(6)
elif 1000 <= X <= 1199:
    print(5)
elif 1200 <= X <= 1399:
    print(4)
elif 1400 <= X <= 1599:
    print(3)
elif 1600 <= X <= 1799:
    print(2)
elif 1800 <= X <= 1999:
    print(1)

Measured memory_bytes: 9180
from scipy.sparse import*
from itertools import*
n,m,r = map(int,input().split())
R = [int(i)-1 for i in input().split()]
cost = [[0]*n for i in range(n)]
ans = 10**9
for j in range(m):
  a,b,c = map(int,input().split())
  cost[a-1][b-1] = c
  cost[b-1][a-1] = c

Co = csgraph.floyd_warshall(csr_matrix(cost))

for v in permutations(R):
  temp = 0
  for i in range(1,r):
    temp += Co[v[i-1]][v[i]]
  ans = min(ans,temp)
print(int(ans))

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

#define All(v) (v).begin(),(v).end()
int dy[8] = {-1,0,1,0,-1,1,1,-1};
int dx[8] = {0,1,0,-1,1,1,-1,-1};
const int mod = 1000000007;

long long pow(long long x,long long n){
    long long res=1;
    while(n>0){
        if(n&1)res*=x;
        x*=x;
        n/=2;
    }
    return res;
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n,k;
    cin>>n>>k;
    vector<long long> a(n+1,0);
    for(int i=1;i<=n;i++)cin>>a[i];
    for(int i=1;i<=n;i++)a[i]+=a[i-1];
    vector<long long> v;
    for(int i=0;i<=n;i++){
        for(int j=i+1;j<=n;j++){
            v.push_back(a[j]-a[i]);
        }
    }

    long long res=0;
    for(int bit=50;bit>=0;bit--){
        int cnt=0;
        for(auto it:v){
            if(it&(1ll<<bit))cnt++;
        }
        if(cnt>=k){
            res+=pow(2,bit);
            vector<long long> vv;
            for(auto it:v){
                if(it&(1ll<<bit))vv.push_back(it);
            }
            v=vv;
        }
    }
    cout<<res<<endl;
}


Measured memory_bytes: 6384
package main

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

var sc = bufio.NewScanner(os.Stdin)

func main() {
	scanInit()

	n := nextInt()
	vlist := make([]int, n)

	for i := 0; i < n; i++ {
		vlist[i] = nextInt()
	}

	sort.Ints(vlist)

	now := float64(vlist[0])
	for i := 1; i < n; i++ {
		now = (now + float64(vlist[i])) / 2.0
	}

	fmt.Println(now)

}

// ---- readfunc
func scanInit() {
	const cap = 64 * 1024
	var buf = make([]byte, cap)
	sc.Buffer(buf, cap)
	sc.Split(bufio.ScanWords)
	return
}
func nextInt() int {
	sc.Scan()
	i, e := strconv.Atoi(sc.Text())
	if e != nil {
		panic(e)
	}
	return i
}
func nextStr() string {
	sc.Scan()
	return sc.Text()
}


Measured memory_bytes: 1776
#include <bits/stdc++.h>
#define IO(i, o) freopen(i, "r", stdin), freopen(o, "w", stdout)
using namespace std;

int a, b, h;

int main(){
	//IO("input.txt", "output.txt");
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> a >> b >> h;
	cout << ((a + b) * h) / 2 << "\n";
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using lli = int_fast64_t;
using ulli = uint_fast64_t;
#define debug(x) cerr << #x << " : " << x << endl
#define debugv(x) cerr << #x << " : {";for(auto value_of_x:x){ cerr << value_of_x << ", ";}cerr << endl
#define debugvp(x) cerr << #x << " : {";for(auto value_of_x:x){ cerr << value_of_x.first << " : " << value_of_x.second << ", ";}cerr << endl
template<typename T>
T ncr(T left, T right) {
	right = min(left - right, right);
	T ans = 1;
	for (T i = 1; i <= right; i++) {
		ans = ans * (left - right + i) / i;
	}
	return ans;
}

const lli MOD = 1000000007;
const lli LIMIT = 1'0'000'000'000'000'000 * 5;
const int tenfive = 100000;

int main() {
	string s;
	cin >> s;
	int ans = 0;
	for (int i = 0; i < s.size(); i++) {
		for (int j = 1; j +i< s.size()+1; j++) {
			string ss = s.substr(i, j);
			int cnt = 0;
			for (int k = 0; k < ss.size(); k++) {
				switch (ss[k]) {
				case 'A':
				case 'G':
				case 'C':
				case 'T':
					cnt++;
				}
			}
			if (cnt == ss.size()) {
				ans = max(ans, cnt);
			}
		}
	}
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 256
class Node():
    def __init__(self, node_id, left, right):
        self.node_id    =   node_id
        self.left       =   left
        self.right      =   right

    def pre_order_search(self):
        l = self.left
        r = self.right
        print("",self.node_id, end="")
        if l != -1:
            tree[l].pre_order_search()
        if r != -1:
            tree[r].pre_order_search()

    def in_order_search(self):
        l = self.left
        r = self.right
        if l != -1:
            tree[l].in_order_search()
        print("",self.node_id, end="")
        if r != -1:
            tree[r].in_order_search()

    def post_order_search(self):
        l = self.left
        r = self.right
        if l != -1:
            tree[l].post_order_search()
        if r != -1:
            tree[r].post_order_search()
        print("",self.node_id, end="")

n = int(input())
tree = [None for i in range(n)]
root_set = set(range(n))

for i in range(n):
    node_id, left, right = map(int, input().split())
    tree[node_id] = Node(node_id, left, right)
    root_set -= set([left, right])
root = root_set.pop()

print("Preorder")
tree[root].pre_order_search()
print()

print("Inorder")
tree[root].in_order_search()
print()

print("Postorder")
tree[root].post_order_search()
print()

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

int main()
{
  ll n;
  cin >> n;
  vector<ll> v(2*n);
  rep(2*n) cin >> v[i];
  sort(v.begin(),v.end());
  ll tmp = 0;
  for (ll i = 0; i < n; i++)
  {
    tmp += v[2*i];
  }

  cout << tmp << endl;
  
  return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define inf INT_MAX
int main()
{

	int n;
	cin>>n;
	int a[n];
	for(int i=0; i<n; i++)
		cin>>a[i];
	int s1=0,s2=0,ans=inf;
	for(int i=0; i<n-1; i++)
	{	s1=0; s2=0;
		for(int j=0; j<n; j++)
		{
			if(j>i)
				s2+=a[j];
			else s1+=a[j];
		}
		//cout<<s1<<s2;
		ans= min (abs(s1-s2),ans);
	}
	cout<<ans;
	return 0;
}

Measured memory_bytes: 256
#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 - 1)
typedef long long ll;
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }


void solve(string S, string T, long long A, long long B, string U){
    if (U==S) {
        A--;
    } else if (U==T) {
        B--;
    }

    printf("%d %d\n", A, B);
}

// Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
int main(){
    string S;
    cin >> S;
    string T;
    cin >> T;
    long long A;
    cin >> A;
    long long B;
    cin >> B;
    string U;
    cin >> U;
    solve(S, T, A, B, U);
}


Measured memory_bytes: 256
n, l = list(map(int, input().split()))
apple = 0
apples = []
eat = None
for i in range(1,n+1):
    apples.append(l+i-1)
    apple = l+i-1
    if i==1:
        eat = apple
    else:
        if abs(eat) > abs(apple):
            eat = apple
print(sum(apples) - eat)


Measured memory_bytes: 3060
#include <bits/stdc++.h>
#define rep(i, z, n) for(int64_t i = z; i < n; i++)
#define all(v) v.begin(), v.end()
typedef long long ll;
//const int64_t INF = 1LL << 60;
//const int INF = 1 << 29;
//const int MODINF = 1000000007;
//const int64_t INF = 998244353;
using namespace std;
int main(){
    vector<vector<int>> A(3, vector<int>(3));
    rep(i, 0, 3){
        rep(j, 0, 3){
            cin >> A.at(i).at(j);
        }
    }
    int N;
    cin >> N;
    vector<int> b(N);
    vector<vector<bool>> C(3, vector<bool>(3, false));
    rep(i, 0, N){
        int b;
        cin >> b;
        rep(j, 0, 3){
            rep(k, 0, 3){
                if (b == A.at(j).at(k)) C.at(j).at(k) = true;
            }
        }
    }
    bool ans = false;
    if(C.at(0).at(0) && C.at(0).at(1) && C.at(0).at(2)) ans = true;
    if(C.at(1).at(0) && C.at(1).at(1) && C.at(1).at(2)) ans = true;
    if(C.at(2).at(0) && C.at(2).at(1) && C.at(2).at(2)) ans = true;
    if(C.at(0).at(0) && C.at(1).at(0) && C.at(2).at(0)) ans = true;
    if(C.at(0).at(1) && C.at(1).at(1) && C.at(2).at(1)) ans = true;
    if(C.at(0).at(2) && C.at(1).at(2) && C.at(2).at(2)) ans = true;
    if(C.at(0).at(0) && C.at(1).at(1) && C.at(2).at(2)) ans = true;
    if(C.at(2).at(0) && C.at(1).at(1) && C.at(0).at(2)) ans = true;
    if(ans) cout << "Yes" << endl;
    else cout << "No" << endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <stack>
#include <queue>
#include <vector>
#include <algorithm>
#include <string>
#include <iomanip>
#include <functional>
#include <map>
#include <math.h>
#include <list>

using namespace std;
#define ll long long int

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


int main(void) {

	ios::sync_with_stdio(false);
	cin.tie(0);

	string a, b;
	cin >> a;
	cin >> b;

	int cnt = 0;
	rep(i, a.length()) {
		if (a[i] != b[i]) cnt++;


	}

	cout << cnt << endl;




	return 0;
}


Measured memory_bytes: 3824
#pragma GCC optimize("Ofast","inline","-ffast-math")
#pragma GCC target("avx,sse2,sse3,sse4,mmx")
#include <bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/hash_policy.hpp>
#define int long long
using namespace __gnu_pbds;
using namespace std;

int n,m,num[30],pw[50],e,ans;
vector<pair<int,int> > v[60];

inline void dfs(int x,int pr,int val)
{
	if(x==e){
		ans=val;
		return;
	}
	for(int i=0;i<v[x].size();i++) if(v[x][i].first!=pr){
		int u=v[x][i].first;
		dfs(u,x,val|(1ll<<(v[x][i].second)));
	}
}

signed main()
{
	ios::sync_with_stdio(false);
	cin>>n;
	for(int i=1;i<n;i++){
		int x,y;cin>>x>>y;
		v[x].push_back(make_pair(y,i-1));
		v[y].push_back(make_pair(x,i-1));
	}
	cin>>m;
	for(int i=1;i<=m;i++){
		int x,y;cin>>x>>y;
		e=y;ans=0;dfs(x,-1,0);
		num[i]=ans;
	}
	int ans=0ll;
	pw[0]=1ll;
	for(int i=1;i<=n;i++) pw[i]=pw[i-1]*2ll; 
	for(int i=0;i<(1<<m);i++){
		int cnt=__builtin_popcountll(i);
		int x=0ll;
		for(int j=1;j<=m;j++) if(i&(1<<(j-1))){
			x|=num[j];
		}
		int cur=n-1-__builtin_popcountll(x);
		if(cnt%2==0) ans+=pw[cur];
		else ans-=pw[cur];
	}
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 3584
import std.stdio, std.algorithm, std.conv, std.array, std.string;

void main()
{
    auto ss = readln.chomp;

    while (ss) {
        ss = ss[0..$-2];
        auto l = ss.length;

        if (ss[0..l/2] == ss[l/2..$]) {
            writeln(l);
            return;
        }
    }
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n)for(int i=0;i<n;i++)
#define MOD 1000000007
#define INF 0x3f3f3f3f
#define INFL 0x3f3f3f3f3f3f3f3f
#define EPS (1e-10)
using namespace std;
typedef long long ll;
typedef pair<int,int>P;

int a[20];
signed main(){
	int n;scanf("%d",&n);
	rep(i,n)cin>>a[i];
	ll cnt=0;
	rep(i,1<<n){//偶数にする場所
		if(i==0)continue;
		ll A=1;
		rep(j,n){
			if(i>>j&1){
				if(a[j]%2==0)A*=1;
				else A*=2;
			}
			else{
				if(a[j]%2==0)A*=2;
				else A*=1;
			}
		}
		cnt+=A;
	}
	cout<<cnt<<endl;
}

Measured memory_bytes: 256
using System;
using System.IO;
using System.Linq;
using System.Collections.Generic;
using System.Text;

public class Program
{

	public void Proc()
	{
        int[] inpt = Reader.ReadLine().Split(' ').Select(a => int.Parse(a)).ToArray();
        int itemCount = inpt[0];
        int selectCount = inpt[1];
        int ans = Reader.ReadLine().Split(' ').Select(a => int.Parse(a)).OrderByDescending(a => a).Take(selectCount).Sum();
        Console.WriteLine(ans);
    }


    public class Reader
	{
		private static StringReader sr;
		public static bool IsDebug = false;
		public static string ReadLine()
		{
			if (IsDebug)
			{
				if (sr == null)
				{
					sr = new StringReader(InputText.Trim());
				}
				return sr.ReadLine();
			}
			else
			{
				return Console.ReadLine();
			}
		}
		private static string InputText = @"




5 3
1 2 3 4 5


";
	}

	public static void Main(string[] args)
	{
#if DEBUG
		Reader.IsDebug = true;
#endif
		Program prg = new Program();
		prg.Proc();
	}
}


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

using namespace std;

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

    int ret = 0;
    for (int i = 0; i < 3; i++) {
        int len = 0;
        while (i + len < 3 && s[i + len] == 'R')len++;
        ret = max(ret, len);
    }

    cout << ret << endl;
    return 0;
}

Measured memory_bytes: 3624
N=int(input())
L=list(map(int,input().split()))
L.sort()
count=0

for i in range(N):
    for j in range(i,N):
        for k in range(j,N):
            if (L[i] != L[j] and L[j] != L[k]):
                    if (L[i] + L[j] > L[k]):
                            count += 1
                        
print(count)

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

int main()
{
	int n = 0;
	std::cin >> n;
	std::string str;
	std::cin >> str;
	std::cout << ((str.substr(0, n / 2) == str.substr(n / 2)) ? "Yes" : "No" )<< std::endl;
}

Measured memory_bytes: 256
#pragma GCC optimize("Ofast")
#pragma GCC target ("avx")
#include <bits/stdc++.h>

constexpr int INF = 2147483647;
constexpr long long int INF_LL = 9223372036854775807;
constexpr int MOD = 1000000007;
using namespace std;
typedef long long int ll;
typedef unsigned long long int ull;


int main() {
	int A, B, C;
	cin >> A >> B >> C;
	cout << max(0, C - (A - B)) << endl;
}

Measured memory_bytes: 384
#define mod 1000000007
#define PI acos(-1)
#include<time.h>
#include<stdio.h>
#include<string.h>
#include<math.h>
#include<map>
#include<queue>
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
typedef long long ll;
const ll INF=0x7fffffffffffffff;
const int inf=0x7fffffff;
const int N=4e5+5;
clock_t start,finish;
void time_in(){start=clock();}
void time_out(){finish=clock();double tim=(double)(finish-start)/CLOCKS_PER_SEC;printf("Running time is %lf\n",tim);}
inline ll mul(ll a,ll b){ll s=0;while(b){if(b&1)s=(s+a)%mod;a=(a<<1)%mod;b>>=1;}return s%mod;}
inline ll pow_mul(ll a,ll b){ll s=1;while(b){if(b&1)s=mul(s,a);a=mul(a,a);b>>=1;}return s;}
inline ll poww(ll a,ll b){ll s=1;while(b){if(b&1)s=(s*a)%mod;a=(a*a)%mod;b>>=1;}return s%mod;}
inline bool read(int &ret){char c=getchar();int sgn;if(c==EOF)return 0;while(c!='-'&&(c<'0'||c>'9'))c=getchar();
	sgn=((c=='-')?-1:1);ret=((c=='-')?0:(c-'0'));while(c=getchar(),c>='0'&&c<='9')ret=ret*10+(c-'0');ret*=sgn;return 1;}
inline void write(int x){if(x>9)write(x/10);putchar(x%10+'0');}
int fact[10]={1,1,2,6,24,120,720,5040,40320,362880};
int st[4][2]={1,0,0,1,-1,0,0,-1};
int t,cas;
int n,m,k;
int main()
{
	char s[10];
	while(~scanf("%s",s))
	{
		if(s[0]==s[1]||s[1]==s[2]||s[2]==s[3])printf("Bad\n");
		else printf("Good\n");
	}
}



Measured memory_bytes: 256
var cnt = 0;
(function main(){
  const lines = require('fs').readFileSync('/dev/stdin', 'utf8').trim().split('\n');
  const n = Number(lines.shift());
  let arr = lines.shift().split(' ').map(Number);
  mergeSort(arr, 0, n);
  // console.log(arr.join(' '));
  console.log(cnt);
})();

function merge(arr, left, mid, right) {
  let L = arr.slice(left, mid);
  let R = arr.slice(mid, right);
  L.push(Infinity);
  R.push(Infinity);
  let i = 0;
  let j = 0;
  let t = 0;
  for (let k = left; k < right; k++) {
    if (L[i] < R[j]) {
      arr[k] = L[i++];
      cnt += t;
    } else {
      arr[k] = R[j++];
      t += 1;
    }
  }
}

function mergeSort(arr, left, right) {
  if (left + 1 < right) {
    let mid = Math.floor((left + right) / 2);
    mergeSort(arr, left, mid);
    mergeSort(arr, mid, right);
    merge(arr, left, mid, right);
  }
}



Measured memory_bytes: 45944
#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>;

const int mod = 1000000007;
struct mint {
  ll x; // typedef long long ll;
  mint(ll x=0):x((x%mod+mod)%mod){}
  mint operator-() const { return mint(-x);}
  mint& operator+=(const mint a) {
    if ((x += a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator-=(const mint a) {
    if ((x += mod-a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator*=(const mint a) { (x *= a.x) %= mod; return *this;}
  mint operator+(const mint a) const { return mint(*this) += a;}
  mint operator-(const mint a) const { return mint(*this) -= a;}
  mint operator*(const mint a) const { return mint(*this) *= a;}
  mint pow(ll t) const {
    if (!t) return 1;
    mint a = pow(t>>1);
    a *= a;
    if (t&1) a *= *this;
    return a;
  }

  // for prime mod
  mint inv() const { return pow(mod-2);}
  mint& operator/=(const mint a) { return *this *= a.inv();}
  mint operator/(const mint a) const { return mint(*this) /= a;}
};
istream& operator>>(istream& is, mint& a) { return is >> a.x;}
ostream& operator<<(ostream& os, const mint& a) { return os << a.x;}

int main() {
	int n;
	cin >> n;
	mint cN8=1,cN9=1,cN10=1;
	rep(i,n) {
		cN8 *= 8;
		cN9 *= 9;
		cN10 *= 10;
	}
	mint ans = cN10 - cN9 - cN9 + cN8;
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 3628
//https://onlinejudge.u-aizu.ac.jp/problems/ALDS1_7_B
//p196.cpp

#include<cstdio>
#define MAX 10000
#define NIL -1

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

Node T[MAX];
int n, D[MAX], H[MAX];

void setDepth( int u, int d){
	if ( u == NIL ) return;
	D[u] = d;
	setDepth(T[u].left, d + 1);
	setDepth(T[u].right, d + 1);
}

int setHeight(int u){
	int h1 = 0, h2 = 0;
	if( T[u].left != NIL )
		h1 = setHeight( T[u].left ) + 1;
	if( T[u].right != NIL )
		h2 = setHeight( T[u].right ) + 1;
	return H[u] = ( h1 > h2 ? h1 : h2);
}

//節点 u の兄弟を返す。
int getSibling(int u){
	if( T[u].parent == NIL ) return NIL;
	if( T[ T[u].parent ].left != u && T[ T[u].parent ].left != NIL )
		return T[ T[u].parent ].left;
	if( T[ T[u].parent ].right != u && T[ T[u].parent ].right != NIL )
		return T[ T[u].parent ].right;
	return NIL;
}

void print(int u){
	printf("node %d: ", u);
	printf("parent = %d, ", T[u].parent);
	printf("sibling = %d, ", getSibling(u));
	int deg = 0;
	if ( T[u].left != NIL ) deg++;
	if ( T[u].right != NIL ) deg++;
	printf("degree = %d, ", deg);
	printf("depth = %d, ", D[u]);
	printf("height = %d, ", H[u]);

	if ( T[u].parent == NIL ){
		printf("root\n");
	}else if ( T[u].left == NIL && T[u].right == NIL ){
		printf("leaf\n");
	}else {
		printf("internal node\n");
	}
}

int main(){
	int v, l, r, root = 0;
	scanf("%d", &n);

	for ( int i = 0; i < n; i++ ) T[i].parent = NIL;

	for ( int i = 0; i < n; i++ ){
		scanf("%d %d %d", &v, &l, &r);
		T[v].left = l;
		T[v].right = r;
		if ( l != NIL ) T[l].parent = v;
		if ( r != NIL ) T[r].parent = v;
	}

	for ( int i = 0; i < n; i++ ) if ( T[i].parent == NIL ) root = i;

	setDepth(root, 0);
	setHeight(root);

	for ( int i = 0; i < n; i++ ) print(i);

	return 0;

}





Measured memory_bytes: 2700
#include<cstdio>
#define MAX 2000000
#define VMAX 10001
using namespace std;

int n;
int A[MAX]={0},B[MAX]={0},C[VMAX]={0};

void CountingSort(){
    for(int j=0;j<n;j++){
        C[A[j]]++;
    }
    for(int i=1;i<VMAX;i++){
        C[i]+=C[i-1];
    }
    for(int j=n-1;j>=0;j--){
        C[A[j]]--;
        B[C[A[j]]]=A[j];
    }
}

int main(){
    scanf("%d", &n);
    for(int i=0;i<n;i++){
        scanf("%d", &A[i]);
    }
    CountingSort();
    for(int i=0;i<n;i++){
        if(i) printf(" ");
        printf("%d", B[i]);
    }
    printf("\n");
}


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

int main(){
int n;
cin >> n;
string s;
cin >> s;

if(n%2==0){
  string t = s.substr(n/2);

  if(s == t+t){
    cout << "Yes" << endl;
  }else{
    cout << "No" << endl; 
  }
}else{
    cout << "No" << endl; 
  }
}





Measured memory_bytes: 3596
def main():
    import sys
    input = sys.stdin.readline
    #Union Find

    #xの根を求める
    def find(x):
        if par[x] < 0:
            return x
        else:
            par[x] = find(par[x])
            return par[x]
    #xとyの属する集合の併合
    def unite(x,y):
        x = find(x)
        y = find(y)
        
        if x == y:
            return False
        else:
            #sizeの大きいほうがx
            if par[x] > par[y]:
                x,y = y,x
            par[x] += par[y]
            par[y] = x
            return True

    #xとyが同じ集合に属するかの判定
    def same(x,y):
        return find(x) == find(y)

    #xが属する集合の個数
    def size(x):
        return -par[find(x)]

    n,m = map(int,input().split())
    #初期化
    #根なら-size,子なら親の頂点
    par = [-1]*n

    for i in range(m):
        X,Y = map(int,input().split())
        unite(X-1,Y-1)
    
    tank = set([])
    for i in range(n):
        tank.add(find(i))
    print(len(tank)-1)

if __name__ == '__main__':
    main()

Measured memory_bytes: 18092
// Problem : B - Popular Vote
// Contest : AtCoder Beginner Contest 161
// URL : https://atcoder.jp/contests/abc161/tasks/abc161_b
// Memory Limit : 1024 MB
// Time Limit : 2000 ms
// Powered by CP Editor (https://github.com/cpeditor/cpeditor)

//QWsin
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define rep(i,x,y) for(int i=x;i<=y;++i)
#define out(i,u) for(int i=first[u];i!=-1;i=nxt[i])
#define repvc(i,vc) for(int i=0,Sz=vc.size();i<Sz;++i)
using namespace std;
inline int read()
{
	char ch=getchar();int ret=0,f=1;
	while(ch<'0' || ch>'9') {if(ch=='-')f=-1;ch=getchar();}
	for(;ch>='0' && ch<='9';ch=getchar()) ret=ret*10+ch-'0';
	return ret*f;
}

typedef long long ll;
const int INF=1<<30;

const int maxn=100+10;
int a[maxn];

int cmp(int a,int b){return a>b;}

int main()
{
	int n,m;cin>>n>>m;
	rep(i,1,n) cin>>a[i];
	int sum=0;
	rep(i,1,n) sum+=a[i];
	double lim=(double)sum/(4*m);
	sort(a+1,a+n+1,cmp);
	puts(a[m]>=lim?"Yes":"No");
	return 0;
}


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

int main(void){
	int a, b, i=1;

	scanf("%d%d",&a, &b);
	while(i<=b){
		i = i*10;
	}
	a = a*i + b;

	int k;
	k = (int)sqrt((double)a);
	if(k*k == a){
		printf("Yes\n");
	}else{
		printf("No\n");
	}
	return 0;
}

Measured memory_bytes: 2064
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
ll p[200005];


int main(){
	int n;
	cin >> n;
	int ans = 0;
	int a[3005];
	for (int i = 0; i < n; i++) {
		cin >> a[i];
		ans += a[i];
	}
	cout << ans - n << endl;
	return 0;
}

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

namespace ABC124A
{
    class Program
    {
        static void Main(string[] args)
        {
            int a, b;
            string[] ss = Console.ReadLine().Split(' ');
            a = int.Parse(ss[0]);
            b = int.Parse(ss[1]);
            if (a - b >= 2)
                Console.WriteLine(a * 2 - 1);
            else if (a - b == 1)
                Console.WriteLine(a + b);
            else if (b - a == 1)
                Console.WriteLine(a + b);
            else if (a == b)
                Console.WriteLine(a + b);
            else if (b - a >= 2)
                Console.WriteLine(b * 2 - 1);
            Console.ReadKey();

        }
    }
}


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

using namespace std;

int N;
const int MAX_N = 100;
int s[MAX_N];

void solve() {
	int A = 0;
	sort(s, s + N);
	for (int i = 0; i < N; i++) {
		A += s[i];
	}
	if (A % 10 != 0) {
		
	}
	else {
		for (int i = 0; i < N; i++) {
			if (s[i] % 10 != 0) {
				A -= s[i];
				break;
			}
		}
	}
	if (A % 10 != 0) {
		cout << A << endl;
	}
	else {
		cout << 0 << endl;
	}
	
	
	
}

int main() {
	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> s[i];
	}
	solve();
	return 0;
}

Measured memory_bytes: 256