akhauriyash/Code-Regression huggingface dataset:
/*
 _  __    _   _   _ ____ _____ 
| |/ /   / \ | | | / ___|_   _|
| ' /   / _ \| | | \___ \ | |  
| . \  / ___ \ |_| |___) || |  
|_|\_\/_/   \_\___/|____/ |_|  
*/
#include <bits/stdc++.h>
#include <fstream>
#define rep(i, a, b) for (long long i = (a); i < (b); i++)
#define per(i, a, b) for (long long i = (a); i > (b); i--)
#define a(x) (x.begin(), x.end())
#define ar(x) (x.rbegin(), x.rend())
#define pb push_back
#define Pb() pop_back()
#define ll long long int
#define ull unsigned long long int
#define pii pair<int, int>
#define pll pair<ll, ll>
#define sc scanf
#define scin(x) sc("%d", &(x))
#define scln(x) sc("%lld", &(x))
#define pf prllf
#define ms(a, b) memset(a, b, sizeof(a))
#define mp make_pair
#define db double
#define EPS 10E-10
#define ff first
#define ss second
#define sqr(x) (x) * (x)
#define vi vector<int>
#define vl vector<ll>
#define vii vector<vector<int>>
#define vll vector<vector<ll>>
#define DBG pf("HI\n")
#define MOD 1000000007
#define CIN                       \
    ios_base::sync_with_stdio(0); \
    cin.tie(0);                   \
    cout.tie(0)
#define RUN_CASE(t, T) for (__typeof(t) t = 1; t <= T; t++)
#define CASE(t) prllf("Case %d: ", t)
#define CASEL(t) prllf("Case %d:\n", t)
#define intlimit 2147483647
#define longlimit 9223372036854775807
#define infinity (1 << 28)
#define gcd(a, b) __gcd(a, b)
#define lcm(a, b) ((a) * (b) / gcd(a, b))
#define PI 2 * acos(0.0)
using namespace std;
vi par;
vii v;
ll dp[100002][5];
void dfs(int x)
{
    for (int u : v[x])
    {
        if (par[x] != u)
        {
            par[u] = x;
            dfs(u);
        }
    }
}
ll counto(int x, int turn)
{
    if(dp[x][turn]!=-1){
        return dp[x][turn];
    }
    ll sum = 1;
    for (int u : v[x])
    {
        if (u != par[x])
        {
            if (turn)
                sum *= counto(u, turn) + counto(u, 1 - turn);
            else
                sum *= counto(u, 1 - turn);
            sum %= MOD;
        }
    }
    return dp[x][turn] = sum;
}
int main()
{
    CIN;
    int n;
    cin >> n;
    v.resize(n + 1);
    par.resize(n + 1, -1);
    rep(i,0,100002){
        rep(j,0,2){
            dp[i][j] = -1;
        }
    }
    rep(i, 0, n-1)
    {
        int n1, n2;
        cin >> n1 >> n2;
        v[n1].pb(n2);
        v[n2].pb(n1);
    }
    dfs(1);
    cout << (counto(1, 0) + counto(1, 1))%MOD;
}


Measured memory_bytes: 18432
val MOD = 1000000007

fun main(args : Array<String>) {
    val n = readLine()!!.toInt()
    val aa = readLine()!!.split(" ").map { it.toInt() }
    val hats = IntArray(3) { 0 }

    var sum = 1L

    for (a in aa) {
        val pattern = hats.count { it == a }
        if (pattern == 0) {
            println(0)
            return
        }

        hats[hats.indexOfFirst { it == a }]++
        sum *= pattern
        sum %= MOD
    }

    println(sum)
}

Measured memory_bytes: 49964
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define Y cout<<"YES"<<endl
#define N cout<<"NO"<<endl
map<char,ll>mpp;
map<ll,ll>mp;

int main()
{
    ll q,n,m,i,j,t=0,x,y,x1,y1,k;

    ll a,b,c;

    cin>>a>>b>>c>>x;

    t=a+b;

    if(x<=a){

        cout<<x<<endl;
        return 0;
    }

    if(x<=t){

        cout<<a<<endl;
        return 0;
    }
    if(x>t){

        y=x-t;

        cout<<a-y<<endl;

        return 0;
    }



    return 0;
}



Measured memory_bytes: 3636
N = int(input())
List = list(map(int,input().split()))
import math
def seki(L):
  num = 1
  for i in L:
    num *= i
  return num
def Seki(L):
  if len(L) <= int(math.sqrt(N)):
    return seki(L)
  else:
    return Seki(L[:len(L)//2]) * Seki(L[len(L)//2:])
if Seki(List) <= 10**18:
  print(Seki(List))
else:
  print(-1)

Measured memory_bytes: 21652
#include <stdlib.h>
#include <stdio.h>
int main(){
int a,b,c,d,e,f;
scanf("%d%d%d",&a,&b,&c);
d=abs(a-b)+abs(a-c);
e=abs(b-a)+abs(b-c);
f=abs(c-a)+abs(c-b);
if(d==e==f) printf("%d",0);
else if(d<=e&&d<=f) printf("%d",d);
else if(e<=d&&e<=f) printf("%d",e);
else if(f<=d&&f<=e) printf("%d",f);




return 0;
}

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

void solver() {
  string s;
  cin >> s;
  int n = (int)(s.length());

  for (int i = 0; i < (int)((n - 1) / 4); i++) {
    char c1 = s[i];
    char c2 = s[(int)((n-2)/2)-i];
    if (c1 == c2) continue;
    else {
      cout << "No" << "\n";
      return;
    }
  }

  for (int i = (int)((n + 3) / 2)-1; i < n; i++) {
    char c1 = s[i];
    char c2 = s[n-1-i];
    if (c1 == c2) continue;
    else {
      cout << "No" << "\n";
      return;
    }
  }

  cout << "Yes" << "\n";
}

int main() {
  solver();
  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#define debug freopen("1.in","r",stdin),freopen("1.out","w",stdout);
#define ios ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
typedef long long ll;
const ll maxn = 1e5 + 10;

int n, arr[maxn], ans;
int main(){
    ios;
    cin >> n;
    cin >> ans;
    for(int i = 2; i <= n; i ++){
        cin >> arr[i];
        ans = __gcd(ans,arr[i]);
    }
    cout << ans;

    return 0;
}

Measured memory_bytes: 640
#include <iostream>
#include <vector>
#include <map>
#include <bitset>
#include <algorithm>
#include <string>
#include <queue>
#include <stack>
#include <cmath>
#include <set>
#include <list>
#include <sstream>
#include <numeric>

#define ll long long
#define ld long double
#define ull unsigned long long
using namespace std;

const ll mod = 1000000007;
const ll inf = 9223372036854775803;
const int maxN = 300005;


int main() {
//    cout.precision(10);
//    cout << fixed;
    cin.tie(0);
    ios_base::sync_with_stdio(false);
    long long a,b,c,k;
    cin >> a >> b >> c >> k;
    if (a + b >= k) {
        cout << min(a,k);
    } else {
        cout << a - (k-a-b);
    }
    return 0;
}



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

#define rep(i,n)  for(int i=0;i<n;++i)
#define per(i,n)  for(int i=n-1;i>=0;--i)
#define sc1(a)  scanf("%d",&a)
#define sc2(a,b)  scanf("%d %d",&a,&b)
#define sc3(a,b,c)  scanf("%d %d %d",&a,&b,&c)
#define sl1(a)  scanf("%lld",&a)
#define sl2(a,b)  scanf("%lld %lld",&a,&b)
#define sl3(a,b,c)  scanf("%lld %lld %lld",&a,&b,&c)
#define PI 3.1415926535897932

int main(){
    int mod=1000000007;
    int a,b,C,m,ans;
    sc3(a,b,C);
    double s,l,h,r,c;
    r=C*PI/180;
    c=sqrt(a*a+b*b-2*a*b*cos(r));
    h=b*sin(r);
    printf("%.15lf\n%.15lf\n%.15lf\n",h*a/2,a+b+c,h);
    return 0;
}



Measured memory_bytes: 3456
a,b = map(int,input().split())

def gcd(m,n):
  x = max(m,n)
  y = min(m,n)
  
  if x%y == 0:
    return y
  else:
    while x%y != 0:
      z = x%y
      x=y
      y=z
      
    return y
    
def lcm(m,n):
  return int((m*n) / gcd(m,n))
  

ans = lcm(a,b)
print(ans)


Measured memory_bytes: 3060
use std::collections::BTreeMap;

const MOD: usize = 1e9 as usize + 7;

fn main() {
    let s = std::io::stdin();
    let mut sc = Scanner { stdin: s.lock() };
    let n: usize = sc.read();

    let mut dp: BTreeMap<(usize, usize), usize> = BTreeMap::new();
    println!("{}", rec(n, n, &mut dp));
}

fn rec(xor: usize, sum: usize, dp: &mut BTreeMap<(usize, usize), usize>) -> usize {
    if sum == 0 { return 1; }
    if let Some(&ans) = dp.get(&(xor, sum)) {
        return ans;
    }

    // odd & odd
    let mut result = if sum >= 2 { rec(xor >> 1, (sum - 2) >> 1, dp) } else { 0 };

    // odd & even
    result += rec((xor - 1) >> 1, (sum - 1) >> 1, dp);

    // even & even
    result += rec(xor >> 1, sum >> 1, dp);

    result %= MOD;
    dp.insert((xor, sum), result);
    return result;
}

pub struct Scanner<R> {
    stdin: R,
}

impl<R: std::io::Read> Scanner<R> {
    pub fn read<T: std::str::FromStr>(&mut self) -> T {
        use std::io::Read;
        let buf = self
            .stdin
            .by_ref()
            .bytes()
            .map(|b| b.unwrap())
            .skip_while(|&b| b == b' ' || b == b'\n')
            .take_while(|&b| b != b' ' && b != b'\n')
            .collect::<Vec<_>>();
        unsafe { std::str::from_utf8_unchecked(&buf) }
            .parse()
            .ok()
            .expect("Parse error.")
    }
    pub fn vec<T: std::str::FromStr>(&mut self, n: usize) -> Vec<T> {
        (0..n).map(|_| self.read()).collect()
    }
    pub fn chars(&mut self) -> Vec<char> {
        self.read::<String>().chars().collect()
    }
}


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

int n,ar[2000];

int f(int i){

              int cost=0;
            for(int j=0;j<=n-1;j++)
                cost+=(int)abs(ar[j]-i)*(int)abs(ar[j]-i);

    return cost;
}

int main(){

    while(cin>>n){

        for(int i=0;i<n;i++)
            scanf("%d",ar+i);

        sort(ar,ar+n);

        int mncost=INT_MAX;
        int low=ar[0],high=ar[n-1];

        if(high-low==0){
            puts("0");
            continue;
        }

        while(high-low>1){
            int mid=(high+low)/2;

            if(f(mid)<f(mid+1))
                high=mid;
            else if(f(mid)>f(mid+1))
                low=mid;

        }

        cout<<f(high)<<endl;

    }




return 0;
}

/*

5
-5 -3 0 2 9
ans=118

5
1 2 3 4 5
ans=10

*/


Measured memory_bytes: 256
import numpy as np


def main():
    n = int(input())
    a = [int(x) for x in input().split()]

    best, solution = int(-1e10), []
    for p in range(2):
        c = a.copy()

        indexes = list(range(p, n, 2))
        if len(indexes) == 0:
            continue

        maks = max([c[i] for i in indexes])
        pick = next((i for i in indexes if c[i] == maks))
        chosen = set([pick] if maks <= 0 else [i for i in indexes if c[i] > 0])
        is_chosen = [(i in chosen) for i in range(n)]

        tot, res = sum([c[i] for i in chosen]), []
        for i in reversed(range(n)):
            if not is_chosen[i]:
                if i == 0 or i + 1 == len(c):
                    res += [i]
                    del c[i], is_chosen[i]
                elif is_chosen[i - 1] == is_chosen[i + 1]:
                    res += [i]
                    c[i - 1] += c[i + 1]
                    del c[i + 1], c[i], is_chosen[i + 1], is_chosen[i]

        for end in (0, ):
            while len(c) > 1 and not is_chosen[end]:
                res += [end]
                del c[end], is_chosen[end]

        if tot > best:
            best, solution = tot, np.array(res) + 1

    print(best, len(solution), *solution, sep='\n')


if __name__ == '__main__':
    main()


Measured memory_bytes: 12392
N, K = map(int, input().split())
MOD = 1000000007

mi = 0
ma = 0
for i in range(K-1):
    mi += i
    ma += N - i

ans = 0
for i in range(K, N+2):
    mi += i - 1
    ma += N - (i - 1)
    ans += ma - mi + 1
    ans %= MOD

print(ans)

Measured memory_bytes: 64304
def i():
	return int(input())
def i2():
	return map(int,input().split())
def s():
	return str(input())
def l():
	return list(input())
def intl():
	return list(int(k) for k in input().split())

n, a, b = i2()
test = 0
memo = []
for i in range(1,n+1):
	c = str(i)
	for j in range(len(c)):
		test += int(c[j])
	if a <= test and test <= b:
		memo.append(i)
	test = 0
# print(memo)
print( sum(memo) )

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

int main()
{
    double x0, y0, x1, y1, x2, y2;
    int q;

    cin >> x0 >> y0 >> x1 >> y1;
    cin >> q;

    for( int i = 0; i < q; i++ )
    {
        cin >> x2 >> y2;

        double a, b, x, y;
        a = x1 - x0;
        b = y1 - y0;

        //p0とp1が縦に並んだ場合
        if( a == 0 )
        {
            if( y0 < y1 && x2 < x0 || y1 < y0 && x0 < x2 )
                cout << "COUNTER_CLOCKWISE" << endl;
            else if( y0 < y1 && x2 > x0 || y1 < y0 && x0 > x2 )
                cout << "CLOCKWISE" << endl;
            else
            {
                if( y2 < y0 && y0 < y1 || y1 < y0 && y0 < y2 )
                    cout << "ONLINE_BACK" << endl;
                else if( y0 < y1 && y1 < y2 || y2 < y1 && y1 < y0 )
                    cout << "ONLINE_FRONT" << endl;
                else
                    cout << "ON_SEGMENT" << endl;
            }
        }
        //p0とp1が横に並んだ場合
        else if( b == 0 )
        {
            if( x0 < x1 && y0 < y2 || x1 < x0 && y2 < y1 )
                cout << "COUNTER_CLOCKWISE" << endl;
            else if( x0 < x1 && y0 > y2 || x1 < x0 && y2 > y1 )
                cout << "CLOCKWISE" << endl;
            else
            {
                if( x2 < x0 && x0 < x1 || x1 < x0 && x0 < x2 )
                    cout << "ONLINE_BACK" << endl;
                else if( x0 < x1 && x1 < x2 || x2 < x1 && x1 < x0 )
                    cout << "ONLINE_FRONT" << endl;
                else
                    cout << "ON_SEGMENT" << endl;
            }
        }
        else
        {
            x = ( y2 - y1 + b * x1 / a ) / ( b / a );
            y = b * x2 / a + y1 - b * x1 / a;
            if( x2 < x && y < y2 && x0 < x1 && y0 < y1 || x < x2 && y < y2 && x0 < x1 && y0 > y1 || x < x2 && y2 < y && x1 < x0 && y1 < y0 || x2 < x && y2 < y && x1 < x0 && y1 > y0 )
                cout << "COUNTER_CLOCKWISE" << endl;
            else if( x2 > x && y > y2 && x0 < x1 && y0 < y1 || x > x2 && y > y2 && x0 < x1 && y0 > y1 || x > x2 && y2 > y && x1 < x0 && y1 < y0 || x2 > x && y2 > y && x1 < x0 && y1 > y0 )
                cout << "CLOCKWISE" << endl;
            else
            {
                if( x0 < x1 && x2 < x0 || x1 < x0 && x0 < x2 )
                    cout << "ONLINE_BACK" << endl;
                else if( x0 < x1 && x1 < x2 || x2 < x1 && x1 < x0 )
                    cout << "ONLINE_FRONT" << endl;
                else
                    cout << "ON_SEGMENT" << endl;
            }
        }
    }
    return 0;
}


Measured memory_bytes: 3228
#pragma target("avx")
#pragma optimize("O3")
#include<bits/stdc++.h>
using ll = int_fast64_t;
using P = std::pair<ll,ll>;
using PP = std::pair<ll,P>;
using V = std::vector<ll>;
template<typename T> using pq = std::priority_queue<T>;
template<typename T> using rpq = std::priority_queue<T, std::vector<T>, std::greater<T>>;

#define REP(i,b,e) for(ll i=b; i<e; i++)
#define ALL(vec) vec.begin(),vec.end()
#define PRINT(vec) printf("[ ");for(auto &i:vec)printf("%ld ",i);puts("]");
#define SCAN(vec) for(auto &i:vec)scanf("%ld",&i)
#define fi first
#define se second

const int MOD = 1e9+7;
const ll INF = 1e18;
int dx[] = {0, 1, 0, -1, 1, 1, -1, -1}, dy[] = {1, 0, -1, 0, 1, -1, -1, 1};

int main(){
	int n, four = 0, two = 0;
	scanf("%d", &n);
	REP(i, 0, n){
		int a;
		scanf("%d", &a);
		if(a%4==0) four++;
		else if(a%2==0) two++;
	}

	if(n-two<=four*2+!two) puts("Yes");
	else puts("No");
	return 0;
}



Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <utility>
#include <map>
#include <algorithm>
#include <queue>
#include <cmath>
#include <numeric>

using namespace std;

typedef pair<int,int> P;

int main() {
  int n;
  cin >> n;
  vector<int> a(n);
  vector<int> b(n);

  for(int i=0; i<n; i++) {
    cin >> a[i];
    b[i] = a[i];
  }

  sort(b.begin(),b.end(), greater<int>());

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

}

Measured memory_bytes: 3200
#include<bits/stdc++.h>
using namespace std;
#define lli long long int
#define rep(i,n) for(lli i=0;i<n;i++)
#define repb(i,n) for(lli i=n-1;i>=0;i--)
#define pb push_back
#define mp make_pair
#define bg() begin()
#define en() end()
#define ft first
#define sc second
#define vect_lli_it vector<lli>::iterator
#define set_lli_it set<lli>::iterator
#define inf 1e18
#define all(X) X.begin(),X.end()
#define iterate(X) for(it=X.begin();it!=X.end();it++)
lli combi(lli n,lli k)
{
    lli ans=1;
    k=k>n-k?n-k:k;
    lli j=1;
    for(;j<=k;j++,n--)
    {
        if(n%j==0)
        {
            ans*=n/j;
        }else
        if(ans%j==0)
        {
            ans=ans/j*n;
        }else
        {
            ans=(ans*n)/j;
        }
    }
    return ans;
}
lli gcd(lli a, lli b)
{
    if (b == 0)
        return a;
    return gcd(b, a % b);
}
lli findlcm(vector <lli> arr, lli n)
{
    lli ans = arr[0];
    for (lli i = 1; i < n; i++)
        ans = (((arr[i] * ans)) /
                (gcd(arr[i], ans)));

    return ans;
}
int main(){
	ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    lli n;
    cin>>n;
    bool arr[n+1];
    rep(i,n+1)
    arr[i]=0;
	for(lli i=3;i<=n;i+=3)
	arr[i]=1;
	for(lli i=5;i<=n;i+=5)
	arr[i]=1;
	lli sum=0;
	for(lli i=1;i<=n;i++){
		if(arr[i]==0)
		sum+=i;
	}
	cout<<sum;
    return 0;
}


Measured memory_bytes: 4616
#include <stdio.h>

int main()
{
	int i, j, H, W, K;
	char s[302][302] = {};
	scanf("%d %d %d", &H, &W, &K);
	for (i = 1; i <= H; i++) scanf("%s", &(s[i][1]));

	int k = 1, l, m, id[302][302] = {}, flag;
	for (i = 1; i <= H; i++) {
		flag = 0;
		for (j = 1; j <= W; j++) {
			id[i][j] = -1;
			if (flag == 1) {
				if (s[i][j] == '#') k++;
				for (l = i; id[l][j] == -1; l--) id[l][j] = k;
			} else if (s[i][j] == '#') {
				flag = 1;
				for (m = 1; m <= j; m++) {
					for (l = i; id[l][m] == -1; l--) id[l][m] = k;
				}
			}
		}
		if (flag == 1) k++;
	}
	
	for (i = H; id[i][1] == -1; i--);
	for (j = 1; j <= W; j++) {
		for (l = i + 1; l <= H; l++) id[l][j] = id[i][j];
	}
		
	for (i = 1; i <= H; i++) {
		for (j = 1; j <= W; j++) printf("%d ", id[i][j]);
		printf("\n");
	}
	fflush(stdout);
	return 0;
}

Measured memory_bytes: 1152
#include <bits/stdc++.h>
#define debug(x) cerr << #x << ": " << x << endl
#define debugArray(x, n)                           \
  for (long long hoge = 0; (hoge) < (n); ++(hoge)) \
  cerr << #x << "[" << hoge << "]: " << x[hoge] << endl
using namespace std;

signed main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  int k, q;
  cin >> k >> q;
  long long d[k];
  for (int i = 0; i < k; i++) {
    cin >> d[i];
  }
  while (q--) {
    long long n, x, m;
    cin >> n >> x >> m;
    long long ans;
    if (n <= k) {
      long long a = x;
      ans = 0;
      for (int i = 0; i < n - 1; i++) {
        if (a % m < (a + d[i]) % m) ans++;
        a += d[i];
      }
    } else {
      ans = n - 1;
      long long dm[k];
      for (int i = 0; i < k; i++) {
        dm[i] = d[i] % m;
        if (!dm[i]) ans -= (n - 2 - i) / k + 1;
      }
      long long an = x;
      for (int i = 0; i < k; i++) {
        an += dm[i] * ((n - 2 - i) / k + 1);
      }
      ans -= an / m - x / m;
    }
    cout << ans << endl;
  }
  return 0;
}

Measured memory_bytes: 3684
n, m = map(int,input().split())
a = [int(input()) for i in range(m)]
mod = 10**9 + 7
dp = [0]*(n + 1)
for i in a:
    dp[i] = -1
for i in range(n+1):
    if dp[i] >= 0:
        if i == 0 or i == 1:
            dp[i] = 1
        else:
            dp[i] = dp[i-1] + dp[i-2]
            dp[i] %= mod
    else:
        dp[i] = 0
print(dp[n])

Measured memory_bytes: 7848
n = gets.chop.to_i
patterns = Array.new(2 ** n) { |i| i.to_s(2).rjust(n, '0') }

person = Array.new(n)
n.times do |m|
  s = Array.new(n)
  a = gets.chop.to_i
  a.times do
    h, t = gets.chop.split.map(&:to_i)
    s[h-1] = t.to_s
  end
  person[m] = s.dup
end

max = 0
patterns.each do |pattern|
  p_sum = 0
  flg = true
  (0..n-1).each do |x|
    next if pattern[x] == '0'
    say = person[x]
    flg = (0..n-1).all? do |y|
      next true if say[y].nil?
      say[y] == pattern[y]
    end
    break p_sum = 0 unless flg
    p_sum += 1 if flg
  end
  max = [max, p_sum].max
end
puts max

Measured memory_bytes: 5756
#include <iostream>
#include <cstdio>
using namespace std;
struct node{int p,l,r;};
node t[25];
int n,h[25],d[25];
void dp1(int now,int de){
  d[now]=de;
  if(t[now].l!=-1) dp1(t[now].l,de+1);
  if(t[now].r!=-1) dp1(t[now].r,de);
}
void dp2(int f,int now,int he){
  h[f]=max(h[f],he);
  if(t[now].l!=-1) dp2(f,t[now].l,he+1);
  if(t[now].l!=-1) if(t[t[now].l].r!=-1) dp2(f,t[t[now].l].r,he+1);
}
int main(){

  int now,tmpl,tmpr,s[25]={0},p[25];
  cin>>n;
  for(int i=0;i<n;i++) t[i].p=t[i].l=t[i].r=p[i]=-1;
  for(int i=0;i<n;i++){
    cin>>now>>tmpl>>tmpr;
    if(tmpl==-1){
      tmpl=tmpr;
      tmpr=-1;
    }
    if(tmpl!=-1){
      s[now]++;
      t[tmpl].p=now;
      t[tmpl].r=tmpr;
    }
    if(tmpr!=-1){
      s[now]++;
      t[tmpr].p=now;
    }
    t[now].l=tmpl;
  }
  for(int i=0;i<n;i++){
    if(t[i].r!=-1) p[i]=t[i].r;
    else if(t[i].p!=-1) if(t[t[i].p].l!=-1&&t[t[i].p].l!=i) p[i]=t[t[i].p].l;
  }
  int st;
  for(int i=0;i<n;i++) if(t[i].p==-1) st=i;
  dp1(st,0);
  for(int i=0;i<n;i++) dp2(i,i,0);
  for(int i=0;i<n;i++){
    printf("node %d: parent = %d, sibling = %d, ",i,t[i].p,p[i]);
    printf("degree = %d, depth = %d, height = %d, ",s[i],d[i],h[i]);
    if(t[i].p==-1) printf("root\n");
    else if(t[i].l!=-1) printf("internal node\n");
    else printf("leaf\n");
  }
  return 0;
}

Measured memory_bytes: 3204
#include <iostream>
#include <algorithm>
#include <vector>
#include <iomanip>
#include <map>
#include <queue>
#include <cmath>

static const int MOD = 1000000007;
using ll = long long;
using u32 = unsigned;
using namespace std;

template<class T>
constexpr T INF = ::numeric_limits<T>::max() / 32 * 15 + 208;

int main() {
    int n;
    cin >> n;
    vector<long double> v(n);
    long double ans = 0, q = 2092358918732;
    for (auto &&i : v) {
        scanf("%Lf", &i);
        ans += i;
    }
    ans /= n;
    int k = 0;
    for (int i = 0; i < n; ++i) {
        if(fabs(ans-v[i]) < q) k = i, q = fabs(ans-v[i]);
    }
    cout << k << "\n";
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define ll long long int
#define MOD 1000000007
#define INF 1e18
#define PI 3.14159265358979

using namespace std;

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

  if (b - a >= 2*k){
     for (int i = a; i < a + k; i++)
       cout << i << endl;
     for (int i = b - k + 1; i < b + 1; i++)
       cout << i << endl;
  }
  else {
    for (int i = a; i < b + 1; i++)
      cout << i << endl;
  }

  return 0;
}


Measured memory_bytes: 256
def prime_factor(n):
    ass = []
    for i in range(2,int(n**0.5)+1):
        while n % i==0:
            ass.append(i)
            n = n//i
    if n != 1:
        ass.append(n)
    return ass

[A,B] = list(map(int,input().split()))

Ad = prime_factor(A)
Bd = prime_factor(B)
ABd = set(Ad) & set(Bd)
print(len(ABd)+1)

Measured memory_bytes: 3188
a, b, c = map(int, input().split())
flg = False
if a == b:
    if a != c:
        flg = True
elif a == c:
    if a != b:
        flg = True
elif b == c:
    if a != b:
        flg = True

if flg == False:
    print("No")
else:
    print("Yes")


Measured memory_bytes: 2940
import Data.List

factorial 0 = 1
factorial n = n * factorial (n - 1)

factor 1 = []
factor n = let divisors = dropWhile ((/= 0) . mod n) [2..ceiling . sqrt $ fromIntegral n]
           in let prime = if null divisors then n else head divisors
              in (prime:) $ factor $ div n prime

solve :: [Int] -> Int
solve [] = 1
solve (n:ns) = (n * solve ns) `mod` (10^9+7)

main :: IO ()
main = do
  n <- factorial <$> readLn
  print . solve . map ((+1) . length) . group $ factor n

Measured memory_bytes: 1148
#include<bits/stdc++.h>
using namespace std;
//using namespace __gnu_pbds;
//typedef tree<ii,null_type,less<ii>,rb_tree_tag,tree_order_statistics_node_update> set_t;
#define fast ios_base::sync_with_stdio(false); cin.tie(NULL);cout.tie(NULL);
#define mp make_pair
#define mt make_tuple
#define pb push_back
#define pf push_front
#define SUM(v) accumulate(v.begin(),v.end(),lli(0))
#define rev(n,d) for(int i=n;i>=d;i--)
#define FOR0(n) for(int i=0;i<n;i++)
#define FOR(a,n) for(int i=a;i<n;i++)
#define FORQ(a,n) for(int i=a;i<=n;i++)
#define inf 1000000009
#define inff 0x3f3f3f3f
#define sz(a) int((a).size())
#define all(c) c.begin(), c.end()
#define ff first
#define ss second
#define endl "\n"
#define mod 1000000007
#define mem(ar,x) memset(ar,x,sizeof ar)
#define present(container, element) (container.find(element) != container.end())
#define max3(a,b,c) return (lli(a)>lli(b)?(lli(a)>lli(c)?a:c):(lli(b)>lli(c)?b:c))
#define max4(a,b,c,d) return (max3(a,b,c)>lli(d)?(max3(a,b,c)):d)
#define min3(a,b,c) return (lli(a)<lli(b)?(lli(a)<lli(c)?a:c):(lli(b)<lli(c)?b:c))
#define min4(a,b,c,d) return (max3(a,b,c)<lli(d)?(max3(a,b,c)):d)
typedef long long int lli;
typedef pair<int,int> pii;
typedef pair<int,pii>ppii;
typedef vector<int>vi;
typedef vector<vi>vvi;
typedef vector<pii>vpii;
const int N=100005;
int dr8[]={0,0,1,-1,1,1,-1,-1};
int dc8[]={1,-1,0,0,-1,1,-1,1};
int dr4[]={0,1,-1,0};
int dc4[]={1,0,0,-1};
int main(){
	fast
	int n;
	cin>>n;
	int a[n];
	int xr=0;
	FOR0(n){
		cin>>a[i];
		xr^=a[i];
	}
	FOR0(n){
		cout<<(xr^a[i])<<" ";
	}
}



Measured memory_bytes: 4388
import java.util.Scanner;

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

        int a = sc.nextInt();
        int b = sc.nextInt();
        int c = sc.nextInt();

        if((a+b) >= c){
            System.out.println("Yes");
        }else{
            System.out.println("No");
        }
    }
}

Measured memory_bytes: 21844
n=int(input())
a=[list(map(int,input().split())) for i in range(n)]
dp=[[0 for j in range(3)] for j in range(n+1)]

for i in range(1,n+1):
    for j in range(3):
        for k in range(3):
            if j==k:
                continue
            dp[i][j]=max(dp[i][j],dp[i-1][k]+a[i-1][k]) 

ans=0
for i in range(3):
    ans=max(ans,dp[n][i])

print(ans)

Measured memory_bytes: 47324
#include<cstdio>
#include<iostream>
#include<string>
#include<algorithm>
#include<stdio.h>
#include<locale.h>
#include<set>
#include<stack>
#include<queue>
#include<math.h>
using namespace std;
typedef long long int ll;
int main()
{
 int n;
 pair<int,int>k[100001];
 pair<int,int>g[100001];
 scanf("%d",&n);
 for(int i=0;i<=100000;i++)
 {
	k[i].first=g[i].first=0;
	k[i].second=g[i].second=i;
 }
 for(int i=1;i<=n;i++)
 {
	int a;
	scanf("%d",&a);
	if(i%2==1){k[a].first++;}
	if(i%2==0){g[a].first++;}
 }

 sort(k,k+100001,greater<>());
 sort(g,g+100001,greater<>());
 int ans=0;
 if(k[0].second!=g[0].second){ans=k[0].first+g[0].first;}
 else{ans=max(k[0].first+g[1].first,k[1].first+g[0].first);}
 ans=n-ans;
 printf("%d",ans);

} 

Measured memory_bytes: 5376
n, k = map(int, input().split(' '))
trees = sorted([ int(input()) for _ in range(n) ])

ans = None
for i in range(n-k+1):
  if ans is None:
    ans = trees[i+k-1] - trees[i]
  else:
    ans = min(ans, trees[i+k-1] - trees[i])
    
print(ans)


Measured memory_bytes: 8280
/*
Author - Glitched
Yeet!!
*/
#include "bits/stdc++.h"
using namespace std;
#define ll long long int
#define loop(i,x,n) for(ll i = x;i<n;i++)

int main()
{
    string s;
    cin>>s;
    if(count(s.begin(),s.end(),'7')>=1)cout<<"Yes";
    else cout<<"No";
}

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

#define all(x)        (x).begin(),(x).end()
#define mp            make_pair
#define pb            push_back
#define fi            first
#define se            second
#define sz(x)         ((int)(x).size())
#define rep(x,y,z)    for(int x=y;x<z;x++)
#define per(x,z,y)    for(int x=z-1;x>=y;x--)
#define trav(y,x)     for(auto& y:x)
#define pii           pair<int,int>
#define vi            vector<int>

int dbg = 0;
#define cri           if(0)
#define shame         cri cerr<<(++dbg)<<"\n\n";

// aaaaaaaaaaaaaaaa
const int N = 2e3 + 1;
const int lg = 20;
const ll mod = 0xfffff;

int g[N][N];
void solve() {
  int n, x, y;
  cin >> n >> x >> y;
  --x; --y;
  vi ans(n, 0);
  rep(i, 0, n) {
    rep(j, i + 1, n) {
      int a = j - i;
      int b = abs(x - i) + 1 + abs(y - j);
      int c = abs(y - i) + 1 + abs(x - j);
      int mn = min(a, min(b, c));
      ans[mn]++;
    }
  }
  rep(i, 1, n)
    cout << ans[i] << "\n";
} 

int main() {
  // freopen("input.in", "r", stdin);
  // freopen("input.out", "w", stdout);
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	// cout<<setprecision(15);
	// int t; cin>>t; while(t--)
	solve();
	return 0;
}



Measured memory_bytes: 256
#include<bits/stdc++.h>
// Begin Header {{{
#define all(x) (x).begin(), (x).end()
#define lli long long int
#define rep(i,n) for(lli i=0; i<n; i++)
#define loop(i, j, n) for(lli i=j; i<n; i++)
#define Max(a, b) ((a) > (b) ? (a) : (b))
#define Min(a, b) ((a) < (b) ? (a) : (b))
constexpr int INF  = 0x3f3f3f3f;
const long long mod=1e9+7;
//Function
lli combi(lli n, lli r)
{
	if(r==0 || r==n) return 1;
	else return combi(n-1,r) + combi(n-1,r-1);
}
lli sigma1(lli n){return n*(n+1)/2;}
lli sigma2(lli s, lli n){return sigma1(n) - sigma1(s -1);}
using namespace std;
// }}} End Header

int n, m, q;
vector<int> a, b, c, d;
int ans = 0;

void dfs(vector<int> A){
	if(A.size() == n+1){
		int now = 0;
		rep(i,q){
			if(A[b[i]] - A[a[i]] == c[i]) now+= d[i];
		}
	ans = Max(ans, now);
	return;
	}

	A.push_back(A.back());
	while(A.back() <= m){
		dfs(A);
		A.back()++;
	}
	return;
}
int main()
{
	ios::sync_with_stdio(false); cin.tie(nullptr);
	cin >> n >> m >> q;
	a = b = c = d = vector<int>(q);
	rep(i,q){
		cin >> a[i] >> b[i] >> c[i] >> d[i];
	}
	dfs(vector<int>(1,1));
	cout << ans << endl;

	return 0;
}

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

using namespace std;

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

int main(){
    int N;
    ll x[200000];
    ll y[200000];
    P p[200000];
    priority_queue<P, vector<P>, greater<P>> que;
    ll x_min = 10e+10, y_min = 10e+10;
    ll x_max = 0, y_max = 0;
    cin >> N;
    ll que_max = 0;
    for(int i = 0; i < N; i++) {
        cin >> x[i] >> y[i];
        if(x[i] > y[i]) swap(x[i], y[i]);
        p[i] = P(x[i], y[i]);
        que_max = max(que_max, y[i]);
        x_max = max(x_max, x[i]);
        x_min = min(x_min, x[i]);
        y_max = max(y_max, y[i]);
        y_min = min(y_min, y[i]);
    }
    ll ans = (x_max-x_min)*(y_max-y_min);
    sort(p, p+N);
    ll r_min = 10e+10;
    ll r_max = p[N-1].first;
    for(int i = 1; i < N; i++){
        r_min = min(r_min, p[i-1].second);
        r_max = max(r_max, p[i-1].second);
        ll tmp = (r_max-min(r_min, p[i].first))*(y_max-x_min);
        ans = min(ans, tmp);
    }
    cout << ans << endl;
}

Measured memory_bytes: 6528
#include <iostream>
#include <string>
#include <algorithm>
#include <functional>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <cstdio>
#include <cmath>
#include <tuple>
#define rep(i, n) for(i = 0; i < n; i++)
using namespace std;

signed main() {
	int n, d;
	cin >> n >> d;
	cout << (n + 2 * d) / (2 * d + 1) << endl;
	return 0;
}

Measured memory_bytes: 256
n,m=map(int,input().split())
l=[0]*m
for i in range(m):
    l[i]=int(input())
#print(l)
dp=[-1]*(n+1)
dp[0]=1
for j in l:
    dp[j]=0
#print(dp)
if dp[1]==-1:dp[1]=1
for i in range(2,n+1):
    if dp[i]==-1:
        dp[i]=(dp[i-1]+dp[i-2])%1000000007
print(dp[-1]%1000000007)

Measured memory_bytes: 7668
using System;

public class Program
{
    public void Solve()
    {
        var sc = new Scanner();
        int a = sc.NextInt();
        int b = sc.NextInt();

        Console.WriteLine(b < a ? a - 1 : a);
    }

    public static void Main(string[] args)
    {
        new Program().Solve();
    }
}

class Scanner
{
    public Scanner()
    {
        _pos = 0;
        _line = new string[0];
    }

    const char Separator = ' ';
    private int _pos;
    private string[] _line;

    #region スペース区切りで取得

    public string Next()
    {
        if (_pos >= _line.Length)
        {
            _line = Console.ReadLine().Split(Separator);
            _pos = 0;
        }

        return _line[_pos++];
    }

    public int NextInt()
    {
        return int.Parse(Next());
    }

    public long NextLong()
    {
        return long.Parse(Next());
    }

    public double NextDouble()
    {
        return double.Parse(Next());
    }

    #endregion

    #region 型変換

    private int[] ToIntArray(string[] array)
    {
        var result = new int[array.Length];
        for (int i = 0; i < array.Length; i++)
        {
            result[i] = int.Parse(array[i]);
        }

        return result;
    }

    private long[] ToLongArray(string[] array)
    {
        var result = new long[array.Length];
        for (int i = 0; i < array.Length; i++)
        {
            result[i] = long.Parse(array[i]);
        }

        return result;
    }

    private double[] ToDoubleArray(string[] array)
    {
        var result = new double[array.Length];
        for (int i = 0; i < array.Length; i++)
        {
            result[i] = double.Parse(array[i]);
        }

        return result;
    }

    #endregion

    #region 配列取得

    public string[] Array()
    {
        if (_pos >= _line.Length)
            _line = Console.ReadLine().Split(Separator);

        _pos = _line.Length;
        return _line;
    }

    public int[] IntArray()
    {
        return ToIntArray(Array());
    }

    public long[] LongArray()
    {
        return ToLongArray(Array());
    }

    public double[] DoubleArray()
    {
        return ToDoubleArray(Array());
    }

    #endregion
}

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

from sys import stdin



############################################

#from sys import stdin
import numpy as np

# read data for n sequences.
data = stdin.readline().split()
#data=str(data)
#data2=[]
#for a in data:
#    data2.append(int(a))
data2 = str(data)[1:-1]

# 0101...
count1=0
count2=0
data = data[1:-1]

for i,a in enumerate(data2[1:-1]):
    a = int(a)
    if i %2 == 0:
        if a == 1:
            count1+=1
        else:
            count2+=1
    else:
        if a == 0:
            count1+=1
        else:
            count2+=1
    
if count1<count2:
    count=count1
else:
    count=count2
print(count)
#count2=0
# 1010..

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

const string YES = "Yes";
const string NO = "No";
int main(){
  int N; cin >> N;
  bool ans = false;
  while (N > 0) {
    if (N % 10 == 7) ans =true;
    N /= 10;
  }

  if (ans) cout << YES << endl;
  else cout << NO << endl;
}


Measured memory_bytes: 3588
#pragma GCC optimize ("O3")

#include <bits/stdc++.h>
#define FOR(i, m, n) for (int i = (m); i < (n); ++i)
#define REP(i, n) FOR(i, 0, n)
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define eb emplace_back
#define bcnt __builtin_popcountll

using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef pair<ll,ll> Pll;
typedef pair<int,int> Pin;

ll INF = 1e16;
int inf = 1e9;
ll MOD = 1e9+7;

template<typename T>
ostream& operator << (ostream& os, const vector<T>& vec) {
    os << "{ ";
    REP(i, vec.size()) {
        os << vec[i] << " ";
    }
    os << "}";

    return os;
}

ll pow_mod(ll a, ll p) {
    ll res = 1;
    while(p) {
        if (p & 1) res = (res * a) % MOD;
        a = (a * a) % MOD;
        p >>= 1;
    }

    return res;
}


ll mod_inv(ll a, ll m) {
    ll b = m, u = 0, v = 1;
    while(a) {
        ll t = b / a;
        swap(b -= t * a, a);
        swap(u -= t * v, v);
    }

    return (u % m + m) % m;
}

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

void d_err() {
    cerr << endl;
}

template <typename H, typename... T>
void d_err(H h, T... t) {
    cerr << h << " ";
    d_err(t...);
}

#ifdef LOCAL
#define debug(...)  cerr << "[" << #__VA_ARGS__ << "]: ", d_err(__VA_ARGS__);
#else
#define debug(...) 83;
#endif

int main(){
    cin.tie(0);
    ios_base::sync_with_stdio(false);
    cout << fixed << setprecision(20);
    
    int N;
    cin >> N;

    int a;
    bool f = true;
    REP (i, N) {
        cin >> a;
        if (a % 2) continue;

        if (a % 3 && a % 5) {
            f = false;
            break;
        }
    }

    if (f) cout << "APPROVED" << endl;
    else cout << "DENIED" << endl;
    
}


Measured memory_bytes: 256
const input = require("fs").readFileSync("/dev/stdin", "utf8")
const lines = input.split('\n')
let [N, M] = lines[0].split(' ').map(Number)

const A = []
const B = []
for (let i = 0; i < M; i++) {
    const l = lines[i + 1].split(' ').map(Number)
    A[i] = l[0]
    B[i] = l[1]
}

const g = {}
for (let i = 0; i < M; i++) {
    const l = [A[i], B[i]]
    if (!g[A[i]] && !g[B[i]]) {
        g[A[i]] = l
        g[B[i]] = l
    } else if (g[A[i]] && g[B[i]]) {
        if (g[A[i]] !== g[B[i]]) {
            if (g[A[i]].length < g[B[i]].length) {
                g[A[i]].forEach(n => {
                    g[B[i]].push(n)
                    g[n] = g[B[i]]
                })
            } else {
                g[B[i]].forEach(n => {
                    g[A[i]].push(n)
                    g[n] = g[A[i]]
                })
            }
        }
    } else if (g[A[i]]) {
        if (!g[B[i]]) {
            g[B[i]] = g[A[i]]
        }
        g[B[i]].push(B[i])
    } else if (g[B[i]]) {
        if (!g[A[i]]) {
            g[A[i]] = g[B[i]]
        }
        g[A[i]].push(A[i])
    }
}

let ans = 1
for (let key in g) {
    ans = Math.max(ans, g[key].length)
}
console.log(ans)


Measured memory_bytes: 108208
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<cmath>
#include<climits>
#include<map>
#include<set>
#include<queue>
#include<stack>
#include<bitset>
#include<iomanip>
#include<deque>
using namespace std;

#define rep(i,j,n) for(int i=(j);i<(n);i++)
#define rep2(i,j,n) for(int i=(j);i<=(n);i++)
#define all(i) i.begin(),i.end()

typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef vector<string> vs;
typedef vector<vector<string>> vvs;
typedef pair<int, int> pi;
typedef long long i64;

int main() {
	int n;
	cin >> n;
	int ans;
	rep(i, 0, 7) {
		if (pow(2, i) <= n) {
			ans = pow(2, i);
		}
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 384
#include <iostream>
#include <cstdlib>
#include <cmath>
#include <vector>
#include <map>
#include <set>
#include <algorithm>
#include <queue>
#include <stack>
#include <functional>

using namespace std;
typedef long long ll;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef pair<ll,ll> P;
typedef vector<P> vpl;
#define rep(i,n) for(ll i=0; i<(n); i++)
#define REP(i,a,b) for(ll i=(a); i<(b); i++)
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
const int inf = 1<<30;
const ll linf = 1LL<<62;
const int mod = 1e9+7;
const int MAX = 510000;
const int V = 100005;
ll dy[8] = {1,0,-1,0,1,-1,1,-1};
ll dx[8] = {0,1,0,-1,1,-1,-1,1};
const double pi = acos(-1);
template<typename T1,typename T2> inline void chmin(T1 &a,T2 b){if(a>b) a=b;}
template<typename T1,typename T2> inline void chmax(T1 &a,T2 b){if(a<b) a=b;}
template<typename T1,typename T2> inline void print2(T1 a, T2 b){cout << a << " " << b << endl;}
#define INT_MAX 1e9+7

int main(){
    map<string,ll> mp;
    mp["SUN"] = 7;
    mp["MON"] = 6;
    mp["TUE"] = 5;
    mp["WED"] = 4;
    mp["THU"] = 3;
    mp["FRI"] = 2;
    mp["SAT"] = 1;
    string s; cin >> s;
    cout << mp[s] << endl;
}

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

int main(){
  string s,ans="";
  cin >> s;
  for(int i=0;i<s.size();i++){
    if(s[i]=='B'&&!ans.empty()) ans.pop_back();
    else if(s[i]!='B') ans.push_back(s[i]);
  }
  cout<<ans<<endl;
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
void __print(int x) {cout << x;}
void __print(long x) {cout << x;}
void __print(long long x) {cout << x;}
void __print(unsigned x) {cout << x;}
void __print(unsigned long x) {cout << x;}
void __print(unsigned long long x) {cout << x;}
void __print(float x) {cout << x;}
void __print(double x) {cout << x;}
void __print(long double x) {cout << x;}
void __print(char x) {cout << '\'' << x << '\'';}
void __print(const char *x) {cout << '\"' << x << '\"';}
void __print(const string &x) {cout << '\"' << x << '\"';}
void __print(bool x) {cout << (x ? "true" : "false");}
template<typename T, typename V>
void __print(const pair<T, V> &x) {cout << '{'; __print(x.first); cout << ','; __print(x.second); cout << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cout << '{'; for (auto &i: x) cout << (f++ ? "," : ""), __print(i); cout << "}";}
void _print() {cout << "\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cout << ", "; _print(v...);}
#define debug(x...) cout << #x << " = "; _print(x)
typedef long long ll; typedef vector<int> vi; typedef vector<ll> vll;
#define rep(i,a,b) for (ll i = (a); i < (b); ++i)
#define per(i,a,b) for (int i = (b)-1; i >= (a); --i)
#define all(x) begin(x), end(x)
#define mp make_pair 
#define pb push_back
#define ff first
#define ss second
#define fast ios_base::sync_with_stdio(NULL);cin.tie(NULL);cout.tie(NULL) 
const int mod = 1e9 + 7, mxn = 1e5 + 1;

ll mul(ll x, ll y){
    return (x * y) % mod;
}

ll add(ll x, ll y){
    return (x + y) % mod;
}

ll sub(ll x, ll y){
    return ((x - y) % mod + mod) % mod;
}

int solve(){
    ll n;
    cin>> n;
    if(n == 1)
        return cout<< "0\n", 0;
    ll tot = 1, z0 = 1, z9 = 1, z90 = 1;
    rep(i, 0, n){
        tot = mul(tot, 10ll);
        z0 = mul(z0, 9ll);
        z9 = mul(z9, 9ll);
        z90 = mul(z90, 8ll);
    }
    ll ans = add(tot, z90);
    ans = sub(ans, z0);
    ans = sub(ans, z9);
    cout<< ans<< "\n";
    return 0;
}
//Counting problems: Sometimes easier to find complement of the answer
 
int main()
{
    fast;
    int t = 1;
    //cin>> t;
    while(t--){  
        solve();
    }
    return 0;
}
//v.clear(), vis.clear(); vis.resize(n + 1, 0), v.resize(n + 1);
 
/*  inv[1] = 1; // inv is ll
    for(int i=2; i<=mxn; ++i)
        inv[i]=mod-mod/i*inv[mod%i]%mod;*/
        
// lower bound   >=  
// upper bound   >
// vector<int>().swap(vec); //free memory from vec


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

int main()
{
    int N;
    cin>>N;
    vector<int> A(N);
    for (int &a: A)
        cin>>a;
    vector<int> B(N);
    for (int &b: B)
        cin>>b;

    int ans = 0x7fffffff;

    vector<int> T(N), X(N);
    for (int b=0; b<1<<N; b++)
    {
        for (int i=0; i<N; i++)
            T[i] = b>>i&1 ? B[i] : A[i];
        sort(T.begin(), T.end());

        for (int i=0; i<N; i++)
            X[i] = i;
        int a = 0;
        bool ok = true;
        for (int i=0; i<N; i++)
        {
            int p;
            for (p=i; p<N; p++)
                if ((b>>X[p]&1 ? B[X[p]] : A[X[p]])==T[i] &&
                    ((X[p]-i)&1)==(b>>X[p]&1))
                    break;
            if (p>=N)
            {
                ok = false;
                break;
            }

            for (int j=p-1; j>=i; j--)
            {
                swap(X[j], X[j+1]);
                a++;
            }
        }
        if (ok)
            ans = min(ans, a);
    }
    cout<<(ans < 0x7fffffff ? ans : -1)<<endl;
}


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

#define mp make_pair
#define pb push_back

#define int int64_t
#define ld long double

const int MOD = 1e9+7;
const int N = 1e6+5;

int32_t main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin>>n;
    int arr[n+2];
    for(int i=0;i<n;i++) {
        cin>>arr[i+1];
    }
    arr[n+1]=0;
    arr[0]=0;
    int ans = 0;
    int p = 0;
    for(int i=1;i<=n+1;i++) {
        ans+=abs(p-arr[i]);
        p=arr[i];
    }
    for(int i=1;i<=n;i++) {
        cout<<ans+(abs(arr[i+1]-arr[i-1]))-(abs(arr[i+1]-arr[i])+abs(arr[i]-arr[i-1]))<<"\n";
    }

    return 0;
}

Measured memory_bytes: 4448
#include <bits/stdc++.h>
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  for(int i=0;i<(n);++i)
#define FORq(i, m, n) for(int i = (m);i <= (n);++i)
#define SCD(n) scanf("%d",&n)
#define SCD2(m,n) scanf("%d%d",&m,&n)
#define SCD3(m,n,k) scanf("%d%d%d",&m,&n,&k)
#define PB push_back
#define MP make_pair
#define ARSCD(A,N) REP(i,N){SCD(A[i]);}
#define ARSCD1(A,N) FORq(i,1,N){SCD(A[i]);}
#define PRINTD(n) printf("%d\n",n)
#define PRINTLLD(n) printf("%lld\n",n)
#define DEBUG printf("%s\n","debug")
#define fst first
#define snd second
#define IN(x,S) (S.count(x) != 0)
using namespace std;
typedef pair<int,int> PII;
typedef vector<int> VI;
typedef long long ll;
//////////////////////////////////////////////////////
int main(){
	int N; SCD(N);
	getchar();
	
	static char s[300002];
	static int w[300002];
	
	w[0] = 0;
	
	FORq(i,1,N){
		char x;
		scanf("%c",&x);
		if (x == 'W'){
			w[i] = w[i-1] + 1;
		}else{
			w[i] = w[i-1];
		}
	}
	getchar();
	

	
	int ans = 1000000;
	
	FORq(i,1,N){
		int ansa;

		ansa = (N-i) - (w[N] - w[i]) + w[i-1];
		ans = min(ansa,ans);
	}
	
	PRINTD(ans);
	
	return 0;
}


Measured memory_bytes: 1408
import sys
import socket

if socket.gethostname() in ['N551J', 'F551C']:
    sys.stdin = open('e1.in')


def read_int_list():
    return list(map(int, input().split()))


def read_int():
    return int(input())


def read_str_list():
    return input().split()


def read_str():
    return input()

inf = 10 ** 20

def solve():
    H, n = read_int_list()
    a, b = [0] * n, [0] * n
    for i in range(n):
        a[i], b[i] = read_int_list()
    cost = [0] * (H+1)
    for h in range(1, H+1):
        c = inf
        for i in range(n):
            health = h - a[i]
            if health < 0:
                health = 0
            if c > cost[health] + b[i]:
                c = cost[health] + b[i]
        cost[h] = c

    # for h in range(H + 1):
    #     print('\t', h, cost[h], file=sys.stderr)

    return cost[H]



def main():
    res = solve()
    print(res)


if __name__ == '__main__':
    main()


Measured memory_bytes: 4156
import java.util.*;
public class Main {

	public static void main(String[] args) {
		Scanner in=new Scanner(System.in);
		List<Integer> ls=new ArrayList<>();
		int n=in.nextInt();
		
		for(int i=0;i<n;i++) ls.add(Integer.parseInt(in.next()));
		
		int q=in.nextInt(),cnt=0;
		for(int i=0;i<q;i++) {
			if(ls.contains(Integer.parseInt(in.next())))cnt++;
		}
		
		System.out.println(cnt);
	}

}



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

int h, w, c, Max;
int dx[]{ 1,-1,0,0 }, dy[]{ 0,0,1,-1 };
vector<vector<int>>a;
void mark(int x, int y, int b, int c) {
	a[x][y] = c;
	rep(i, 4) {
		int nx = x + dx[i], ny = y + dy[i];
		if (0 <= nx&&nx < h && 0 <= ny&&ny < w&&a[nx][ny] == b)mark(nx, ny, b, c);
	}
}
int cnt = 0;
void dfs(int t) {
	if (t == 0) {
		if (a[0][0] != c)mark(0, 0, a[0][0], c);
		rep(i, h)rep(j, w) {
			if (a[i][j] != c)continue;
			mark(i, j, c, 10);
			int cnt = 0;
			rep(l, h)rep(k, w)if (a[l][k] == 10)Max = max(Max, ++cnt);
			mark(i, j, 10, c);
		}
		return;
	}
	vector<vector<int>>b = a;
	rep(i, 6) {
		if (a[0][0] == i)continue;
		mark(0, 0, a[0][0], i);
		dfs(t - 1); a = b;
	}
}
int main() {
	while (scanf("%d%d%d", &h, &w, &c), h) {
		a = vector<vector<int>>(h, vector<int>(w)); c--;
		rep(i, h)rep(j, w)scanf("%d", &a[i][j]), a[i][j]--;
		Max = 0; dfs(4);
		printf("%d\n", Max);
	}
}

Measured memory_bytes: 3276
#include<bits/stdc++.h>
using namespace std;
#define ar array
#define endl '\n'
#define ll long long
#define in insert
#define pb push_back
#define vt vector
#define P_Q(x) priority_queue<x>
#define p_q(x) priority_queue<x, vector<x>, greater<x>>
#define Rep(i,a,b) for(int i=a;i<=b;i++)
#define Rev(i,a,b) for(ll i=a;i>=b;i--)
#define FOR(m) Rep(i,1,m)
#define For(m) Rep(i,0,m-1)
#define Rbl(x,a) for(auto &x : a)
#define FIO ios::sync_with_stdio(0);   cin.tie(0);
#define F first
#define S second
#define pii pair<int,int>
#define pll pair<ll,ll>
#define mp make_pair
#define vpii vector<pii>
#define vpll vector<pll>
#define all(x) (x).begin(),(x).end()
#define sz(x) (int) (x).size()
const ll INF = 0x3f3f3f3f3f3f3f3fll;
#define mod 1000000007
 
const int mxN = 3e3 + 5;
ll a[mxN][mxN] = {};
ll dp[mxN][mxN][4] = {};
ll n, m, z;
 
 
int main()
{
FIO
    
    cin >> n >> m >> z;     
    For(z)
    {
        ll r, c, v;
        cin >> r >> c >> v;
        a[r][c] = v;
    }   

    Rep(i,1,n)
    {
        Rep(j,1,m)
        {
            dp[i][j][0] = *max_element(dp[i-1][j], dp[i-1][j] + 4);
            dp[i][j][1] = dp[i][j][0] + a[i][j];
            
            Rep(k,0,3)
            {
                dp[i][j][k] = max(dp[i][j][k], dp[i][j-1][k]);
                if(k)
                    dp[i][j][k] = max(dp[i][j][k], dp[i][j-1][k-1] + a[i][j]);
            }
        }
    }

    cout << *max_element(dp[n][m], dp[n][m] + 4);
     
}

Measured memory_bytes: 355668