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

int main(){
  int r,d,f;
  cin >> r >> d >> f;
  long long p = r * f - d;
  cout << p << endl;
  for(int i = 1; i < 10; i++){
    p = r * p - d;
    cout << p << endl;
  }
}

Measured memory_bytes: 3600
import sys
sys.setrecursionlimit(1 << 25)
read = sys.stdin.readline


def read_ints():
    return list(map(int, read().split()))


def read_a_int():
    return int(read())


def read_tuple(H):
    '''
    H is number of rows
    '''
    ret = []
    for _ in range(H):
        ret.append(tuple(map(int, read().split())))
    return ret


def read_col(H, n_cols):
    '''
    H is number of rows
    n_cols is number of cols
    A列、B列が与えられるようなとき
    '''
    ret = [[] for _ in range(n_cols)]
    for _ in range(H):
        tmp = list(map(int, read().split()))
        for col in range(n_cols):
            ret[col].append(tmp[col])
    return ret


def read_matrix(H):
    '''
    H is number of rows
    '''
    ret = []
    for _ in range(H):
        ret.append(list(map(int, read().split())))
    return ret
    # return [list(map(int, read().split())) for _ in range(H)] # 内包表記はpypyでは遅いため


def read_map(H):
    '''
    H is number of rows
    文字列で与えられた盤面を読み取る用
    '''
    return [read()[:-1] for _ in range(H)]


def read_map_as_int(H):
    '''
    #→1,.→0として読み込む
    '''
    ret = []
    for _ in range(H):
        ret.append([1 if s == '#' else 0 for s in read()[:-1]])
        # 内包表記はpypyでは若干遅いことに注意
        # #numpy使うだろうからこれを残しておくけど
    return ret


MOD = 10**9 + 7
# default import
from collections import defaultdict, Counter, deque
from operator import itemgetter
from itertools import product, permutations, combinations
from bisect import bisect_left, bisect_right  # , insort_left, insort_right

# 幅が一番大きいのを調べて引けば良い
K, N = read_ints()
A = read_ints()
import numpy as np
A_diff = list(np.diff(A))
A_diff.append(A[0] + K - A[-1])
print(K - max(A_diff))
# print(A_diff)


Measured memory_bytes: 38320
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define ALL(v) v.begin(), v.end()
typedef long long ll;

#include <atcoder/all>
#include <bits/stdc++.h>
using namespace std;
using namespace atcoder;

int main(){
  int n;
  cin>>n;
  
  string a="ACL";
  
  rep(i,n) cout<<a;
  cout<<endl;
  
  return 0;
}

Measured memory_bytes: 3516
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (n); i++)
#define rep2(i, x, n) for (int i = x; i < (n); i++)
#define all(n) begin(n), end(n)
struct cww
{
    cww()
    {
        ios::sync_with_stdio(false);
        cin.tie(0);
    }
} star;
const long long INF = numeric_limits<long long>::max();
typedef long long ll;
typedef vector<int> vint;
typedef vector<char> vchar;
typedef vector<vector<int>> vvint;
typedef vector<ll> vll;
typedef vector<vector<ll>> vvll;
typedef unsigned long long ull;

int main()
{
    int N;
    string S;
    cin >> N;
    cin >> S;
L:
    int count = 0;
    
    rep(i, N)
    {
        if (S[i] == '(')
        {
            count++;
        }
        else
        {
            count--;
        }
        if (count < 0)
        {
            S.insert(S.begin(), '(');
            N++;
            goto L;
        }
    }
    R:
        count = 0;
        for (int i = N - 1; i >= 0; i--)
        {
            if (S[i] == ')')
            {
                count++;
            }
            else
            {
                count--;
            }
            if (count < 0)
            {
                S.insert(S.end(), ')');
                N++;
                goto R;
            }
    }
        cout << S;
    return 0;
}

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

int main(){
  int N;
  cin >> N;

  vector<int > A(N);
  int B, C, k;
  B = 0;
  for ( int i = 0; i < N; i++ ) {
    cin >> A.at(i);
    if ( A.at(i) > B ) {
      C = B; // No.2
      B = A.at(i); // No.1
      k = i;
    } else if ( A.at(i) > C ) { // no_2
      C = A.at(i);
    }
  }

  for ( int i = 0; i < N; i++ ){
    if ( i == k ) {
      cout << C << endl;
    } else {
      cout << B << endl;      
    }
  }


  return 0;
}


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

int main(){
  int N;
  cin >> N;
  
  double T, A;
  cin >> T >> A;
  
  double H[N];
  double a = 10e5;
  int h = 0;
  int n;
  
  for(int i=0;i<N;i++){
    cin >> H[i];
    h++;
    if(a > abs(A-(T-H[i]*0.006))){
      a = abs(A-(T-H[i]*0.006));
      n = h;
    }
  }
  cout << n;
  
  return 0;
}



Measured memory_bytes: 256
#include<iostream>
#include<fstream>
#include<stdio.h>
#include<string>
#include<vector>
#include<map>
#include<math.h>
#include<algorithm>
#include<iomanip>
#include<set>
#include<utility>

using namespace std;

int main() {
  int n, y;
  cin >> n >> y;
  y /= 1000;
  bool dp[n + 1][y + 1];
  int back[n + 1][y + 1];
  for(int i = 0; i < n + 1; i++) for(int j = 0; j < y + 1; j++) dp[i][j] = false;
  for(int i = 0; i < n + 1; i++) for(int j = 0; j < y + 1; j++) back[i][j] = 0;
  dp[0][0] = true;
  for(int i = 0; i < n; i++) for(int j = 0; j < y; j++) {
    if(dp[i][j]) {
      if(j + 1 <= y) {
        dp[i + 1][j + 1] = true;
        back[i + 1][j + 1] = 1;
      }
      if(j + 5 <= y) {
        dp[i + 1][j + 5] = true;
        back[i + 1][j + 5] = 5;
      }
      if(j + 10 <= y) {
        dp[i + 1][j + 10] = true;
        back[i + 1][j + 10] = 10;
      }
    }
  }
  if(dp[n][y]) {
    int ans[11] = {0};
    int x = y;
    for(int i = n; i > 0; i--) {
      ans[back[i][x]]++;
      x -= back[i][x];
    }
    cout << ans[10] << " " << ans[5] << " " << ans[1] << endl;
  } else {
    cout << "-1 -1 -1" << endl;
  }
  
  return 0;
}


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

using namespace std;

int main(void) {
  long long n,a,b,c,d,e;
  cin >> n >> a >> b >> c >> d >> e;
  cout << max({(n-1)/a,(n-1)/b,(n-1)/c,(n-1)/d,(n-1)/e})+5 << endl;

  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define REP(i, n) for(int i = 0; i < (int)(n); i++)
#define REPR(i, n) for(int i = n;i >= 0;i--)
#define FOR(i, m, n) for(int i = m;i < n;i++)
#define FORR(i, m, n) for(int i = m;i >= n;i--)
#define ALL(x) (x).begin(),(x).end()
#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end());
#define INF 99999999999
#define PRINT(var) std::cout<<#var"= "<<var<<std::endl

using namespace std;
typedef long long  int ll;

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

ll m;

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  string s;
  cin >>s;
  s.pop_back();
  if(s.length()%2==1) s.pop_back();

  while(1){
    if(s.substr(0,s.length()/2)==s.substr(s.length()/2,s.length()/2)){
      cout << s.length() <<endl;
      return 0;
    }else{
      s.pop_back();
      s.pop_back();
    }
  }

  return 0;
}

Measured memory_bytes: 256
#include <iostream>
using namespace std;
int main()
{
	int n, l, buffer, minap, ans = 0;
	cin >> n >> l;
	minap = l;
	for (int i = 1; i <= n; i++)
	{
		if (abs(l + i - 1)<abs(minap)) minap = l + i - 1;
		ans += l + i - 1;
	}
	ans -= minap;
	cout << ans;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define F first
#define S second
#define pii pair<int, int>
#define eb emplace_back
#define all(v) v.begin(), v.end()
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define rep3(i, l, n) for (int i = l; i < (n); ++i)
#define sz(v) (int)v.size()
const int inf = 1e9 + 7;
const ll INF = 1e18;
#define abs(x) (x >= 0 ? x : -(x))
#define lb(v, x) (int)(lower_bound(all(v), x) - v.begin())
#define ub(v, x) (int)(upper_bound(all(v), x) - v.begin())
template<typename T1, typename T2> inline bool chmin(T1 &a, T2 b) { if (a > b) { a = b; return 1; } return 0; }
template<typename T1, typename T2> inline bool chmax(T1 &a, T2 b) { if (a < b) { a = b; return 1; } return 0; }
template<typename T> T gcd(T a, T b) { if (b == 0) return a; return gcd(b, a % b); }
template<typename T> T lcm(T a, T b) { return a / gcd(a, b) * b; }
template<typename T> T pow(T a, int b) { return b ? pow(a * a, b / 2) * (b % 2 ? a : 1) : 1; }
const int mod = 1000000007;
ll modpow(ll a, int b) { return b ? modpow(a * a % mod, b / 2) * (b % 2 ? a : 1) % mod : 1; }
template<class T> ostream& operator<<(ostream& os, const vector<T>& vec) { for (auto &vi: vec) os << vi << " "; return os; }

void solve();

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int T;
    // cin >> T;
    T = 1;

    while (T--) {
        solve();
    }
}

void solve() {
  string s;
  cin >> s;
  string t;
  rep(i, sz(s)) t += 'x';
  cout << t << endl;
}


Measured memory_bytes: 256
#include <iostream>
using namespace std;
int main(){
    int a,b,n,m,x,y;
    cin>>n>>m>>x>>y;
    int max=x;
    for (int i=1; i<=n; i++) {
        cin>>a;
        if (max<a) max=a;
    }
    int min=y;
    for (int i=1; i<=m; i++) {
        cin>>b;
        if(min>b)min=b;
    }
    if(min<=max)cout<<"War"<<endl;
    else cout<<"No War"<<endl;
}



Measured memory_bytes: 256
import java.util.*;

public class Main {
    static int MAX = 510000;
    static int MOD = 1000000007;
    static long[] fac;
    static long[] finv;
    static long[] inv;
    
    public static void main(String[] args) throws Exception {
        // Your code here!
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int k = sc.nextInt();
        
        int[] array = new int[n];
        for (int i = 0; i < n; i++) {
            array[i] = sc.nextInt();
        }
        Arrays.sort(array);
        
        fac = new long[MAX];
        finv = new long[MAX];
        inv = new long[MAX];
        COMinit();
        
        long ans = 0;
        for (int i = k - 1; i < n; i++) {
            ans = (ans + (nCkMOD(i, k - 1, MOD) * array[i]) % MOD) % MOD;
        }
        
        for (int i = 0; i < n - k + 1; i++) {
            ans = (ans - (nCkMOD(n - 1 - i, k - 1, MOD) * array[i]) % MOD) % MOD;
        }
        
        if (ans < 0) {
            ans += MOD;
        }
        
        System.out.println(ans);
    }
    
    // テーブルを作る前処理
    public static void COMinit() {
        fac[0] = fac[1] = 1;
        finv[0] = finv[1] = 1;
        inv[1] = 1;
        for (int i = 2; i < MAX; i++){
            fac[i] = fac[i - 1] * i % MOD;
            inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
            finv[i] = finv[i - 1] * inv[i] % MOD;
        }
    }
    // 二項係数計算
    public static long nCkMOD(int n, int k, int MOD){
        if (n < k) return 0;
        if (n < 0 || k < 0) return 0;
        return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
    }
}


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

int main(){
  int h,w;
  cin >> h;
  cin >> w;
  
  string line(w+2,'#');
  string read;
  cout << line << endl;
  for(int i = 0; i < h; i++){
    cin >> read;
    cout << '#' << read << '#' << endl;
  }
  cout << line << endl;
}

Measured memory_bytes: 3608
N = int(input())
src = [tuple(map(int,input().split())) for i in range(N)]
src.sort(key=lambda x:sum(x))

a = b = 0
for i,(x,y) in enumerate(reversed(src)):
    if i%2:
        b += y
    else:
        a += x
print(a-b)

Measured memory_bytes: 21384
#include <stdio.h>
#include <stdlib.h>

int main(void){
    int n,k;
    int sum = 0;
    scanf("%d",&n);
    scanf("%d",&k);
    int a[n];
    int buf= 0;

    for(int i= 0;i<n;i ++)scanf("%d",&a[i]);
    
    for(int i = 0;i < n;i++){
        for(int j = n-1;j >= i+1 ;j--){
            if(a[j] < a[j-1]){
                buf = a[j];
                a[j] = a[j-1];
                a[j-1] = buf;
            }
        }
    }
    
    for(int i = 0;i<k;i++)sum += a[i];
    printf("%d\n",sum);

    return 0;
}

Measured memory_bytes: 1736
### main

loop do
  n, pn = gets.split.map(&:to_i)
  break if (n | pn) == 0

  pls = n.times.map{0}
  zeros = n
  bwl = pn

  id = 0

  loop do
    if bwl > 0
      pls[id] += 1
      bwl -= 1
      zeros -= 1 if pls[id] == 1
    else
      zeros += 1 if pls[id] > 0
      bwl = pls[id]
      pls[id] = 0
    end

    break if bwl == 0 && zeros == n - 1

    id = (id + 1) % n
  end

  puts id
end

Measured memory_bytes: 6112
#define _USE_MATH_DEFINES //M_PI, M_E
#include<bits/stdc++.h>
#define mod 1000000007
#define ll long long int
#define ar array
#define pb push_back
ll power(ll a,ll b){ll r=1;for(;b;b>>=1){if(b&1)r=r*a%mod;a=a*a%mod;}return r;}
using namespace std;

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	ll n,h;
	cin>>n>>h;
	vector<ar<ll,2>> v;
	ll ans = 0;
	for(ll i = 0,j,k; i<n; i++){ cin>>j>>k; v.pb({j,k});}
	vector<ar<ll,2>> v2;
	for(ll i=0; i<n; i++) v2.pb({v[i][1],v[i][0]});
	sort(v2.begin(),v2.end(),greater<ar<ll,2>>());	
	sort(v.begin(),v.end(),greater<ar<ll,2>>());
	ll f = v[0][0];
	ll cnt = 0;
	for(int i = 0; i<n; i++)
		if(h>0 && v2[i][0]>f)
		{
			cnt++;
			h -= v2[i][0];
		}
	if(h<=0)cout<<cnt<<endl;
	else
	{
		cnt += (h/f);
		if(h%f!=0) cnt++;
		cout<<cnt<<endl;
	}
	return 0;
}

Measured memory_bytes: 6384
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define FOR(i, s, e) for (int i = (int)(s); i <= (int)(e); i++)
#define printYesNo(is_ok) puts(is_ok ? "Yes" : "No");
#define printVector(v) rep(i, v.size()) cout << v[i] << endl;

int main()
{
  long long N, A, B, preX;
  cin >> N >> A >> B >> preX;
  long long ans = 0;

  rep(i, N - 1)
  {
    long long X;
    cin >> X;
    ans += min((X - preX) * A, B);
    preX = X;
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<map>
#include<set>
#include<stack>
#include<queue>
#include<math.h>
using namespace std;
typedef long long ll;
#define int long long
typedef vector<int> VI;
typedef pair<int, int> pii;
typedef priority_queue<int> PQ;
#define fore(i,a) for(auto &i:a)
#define REP(i,n) for(int i=0;i<n;i++)
#define eREP(i,n) for(int i=0;i<=n;i++)
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define eFOR(i,a,b) for(int i=(a);i<=(b);++i)
#define SORT(c) sort((c).begin(),(c).end())
#define rSORT(c) sort((c).rbegin(),(c).rend())
#define LB(x,a) lower_bound((x).begin(),(x).end(),(a))
#define UB(x,a) upper_bound((x).begin(),(x).end(),(a))
#define INF 1000000000
#define LLINF 9223372036854775807
#define mod 1000000007
//vector<vector<int> > dp;
//vector<vector<vector<int> > > vvvi;
//dp=vector<vector<int> >(N, vector<int>(M,0));
//vector<pair<int,int> > v;
//v.push_back(make_pair(x,y));
//priority_queue<int,vector<int>, greater<int> > q2;



signed main() {
	cin.tie(0);
	ios::sync_with_stdio(false);

	int N;
	cin >> N;
	VI A(N);
	int sum = 0;
	REP(i, N) {
		cin >> A[i];
		sum += A[i];
	}
	int ans = LLINF;
	int cnt = 0;
	REP(i, N) {
		cnt += A[i];
		ans = min(ans, abs((sum - cnt)-cnt));
	}
	cout << ans << endl;
	return 0;
}



Measured memory_bytes: 1792
n = int(input())
A = list(map(int, input().split()))

def bubbleSort(A, N):
    flag = 1
    cnt = 0
    
    while flag:
        flag = 0
        for i in range(N-1, 0, -1):
            if A[i] < A[i-1]:
                temp = A[i]
                A[i] = A[i-1]
                A[i-1] = temp
                flag = 1
                cnt += flag
            
    print(*A)
    print(cnt)
    
bubbleSort(A, n)


Measured memory_bytes: 5604
# ABC097B - Exponential
def main():
    X = int(input())
    cand = [1]
    for i in range(2, int(X ** 0.5) + 1):
        p = 2
        while i ** p <= X:
            cand.append(i ** p)
            p += 1
    ans = max(cand)
    print(ans)


if __name__ == "__main__":
    main()

Measured memory_bytes: 2940
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using VI = vector<int>;
using VL = vector<ll>;
#define FOR(i,a,n) for(int (i)=(a);(i)<(n);(i)++)
#define eFOR(i,a,n) for(int (i)=(a);(i)<=(n);(i)++)
#define rFOR(i,a,n) for(int (i)=(n)-1;(i)>=(a);(i)--)
#define erFOR(i,a,n) for(int (i)=(n);(i)>=(a);(i)--)
#define SORT(i) sort((i).begin(),(i).end())
#define rSORT(i,a) sort((i).begin(),(i).end(),(a))
#define all(i) (i).begin(),(i).end()
constexpr ll INF = 1000000000;
constexpr ll LLINF = 1LL << 60;
constexpr ll mod = 1000000007;
constexpr ll MOD = 998244353;
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; }
inline void init() { cout.tie(nullptr); cin.tie(nullptr); ios::sync_with_stdio(false); cout << fixed << setprecision(15); }

struct edge {
    int from, to; ll cost;
    edge(int s, int t, ll w = 0) : from(s), to(t), cost(w) {}
};
int main() {
    init();

    int n;
    cin >> n;
    vector<VI> a(n, VI(n)), wh(n, VI(n, -1));
    FOR(i, 0, n)FOR(j, 0, n - 1) {
        cin >> a[i][j];
        wh[i][--a[i][j]] = j;
    }

    int v = n * (n - 1) / 2;
    vector<vector<edge>> g(v);

    vector<VI> id(n, VI(n));
    int o = 0;
    FOR(i, 0, n)FOR(j, i + 1, n)id[i][j] = o++;

    VI in(v, 0);
    FOR(i, 0, n)FOR(j, 0, n - 2) {
        int x = i, y = a[i][j], X = i, Y = a[i][j + 1];
        if (x > y)swap(x, y);
        if (X > Y)swap(X, Y);
        g[id[x][y]].emplace_back(id[x][y], id[X][Y]);
        in[id[X][Y]]++;
    }
    
    VI len(v, 0);
    queue<int> que;
    FOR(i, 0, v)if (in[i] == 0) {
        que.push(i);
        len[i] = 1;
    }

    deque<int> ans;
    while (!que.empty()) {
        int now = que.front(); que.pop();
        ans.push_back(now);
        for (edge next : g[now]) {
            if (--in[next.to] == 0) {
                que.push(next.to);
                chmax(len[next.to], len[now] + 1);
            }
        }
    }

    if (v == ans.size()) {
        int mlen = 0;
        for (int i : len)chmax(mlen, i);
        cout << mlen << "\n";
    }
    else cout << "-1\n";
}


Measured memory_bytes: 54912
#include <iostream>
#include <string>
#include <vector>
#include <array>
#include <queue>
#include <deque>
#include <algorithm>
#include <set>
#include <map>
#include <bitset>
#include <cmath>
#include <functional>
#include <cassert>
#include <iomanip>
#define vll vector<ll>
#define vvvl vector<vvl>
#define vvl vector<vector<ll>>
#define VV(a, b, c, d) vector<vector<d>>(a, vector<d>(b, c))
#define VVV(a, b, c, d) vector<vvl>(a, vvl(b, vll (c, d)));
#define re(c, b) for(ll c=0;c<b;c++)
#define all(obj) (obj).begin(), (obj).end()
typedef long long int ll;
typedef long double ld;
using namespace std;

int main(){
  string s;std::cin >> s;
  if(s[s.size()-1]=='s') s += "es";
  else s += "s";
  std::cout << s << '\n';
}


Measured memory_bytes: 3592
#include <iostream>
#include <cmath>
#include <string>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <math.h>
#include <iomanip>
#include <bitset>
#include <cstring>
#include <stdlib.h>
#include <utility>
#include <set>
#include <map>
#include <string.h>
#include <cstring>

using namespace std;

int main(){
    
    int n;
    cin >> n;
    long double* a;
    a = new long double[n];
    for(int i=0;i<n;i++){
        cin >> a[i];
    }
    long double ans=0;
    for(int i=0;i<n;i++){
        ans+=1/a[i];
    }
    cout << 1/ans << endl;
    
   
    return 0;
}

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

namespace ITP1_10C
{
    class Program
    {
        static void Main(string[] args)
        {
            while (true)
            {
                var input = Console.ReadLine();
                var n = int.Parse(input);

                if (n == 0)
                {
                    break;
                }

                input = Console.ReadLine();
                var words = input.Split(' ');
                var arrayOfS = new int[words.Length];
                var sumOfS = 0;
                for (var i = 0; i < n; ++i)
                {
                    arrayOfS[i] = int.Parse(words[i]);
                    sumOfS += arrayOfS[i];
                }
                var averageOfS = sumOfS / (double)arrayOfS.Length;

                var dOfS = 0.0;
                for (var i = 0; i < n; ++i)
                {
                    dOfS += (arrayOfS[i] - averageOfS) * (arrayOfS[i] - averageOfS);
                }

                var standardDeviation = Math.Sqrt(dOfS / arrayOfS.Length);
                Console.WriteLine(standardDeviation);

            }
        }
    }
}

Measured memory_bytes: 5748
#include <iostream>
#include <cstring> 
#include <cmath>
#include <cstdio>
const long long mod=1e9+7;
using namespace std;
long long f(long long m,long long n){
	long long ans=1;
	while(n>0){
		if(n&1)
			ans=(ans*m)%mod;
		m=(m*m)%mod;
		n=(n/2)%mod;
	}
	return ans;
}
int main(){
	long long n;
	scanf("%lld",&n);	
		cout<<(f(10,n)%mod-(2*f(9,n))%mod+f(8,n)%mod+mod)%mod<<endl;	
	return 0;
}

Measured memory_bytes: 3764
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(n);i++)
#define all(v) v.begin(),v.end()
#define len(x) (ll)(x).length()
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
const int INF=1e9;
const ll INFS=1e18;
const int MOD=INF+7;
const int di[] = {-1,0,1,0};
const int dj[] = {0,-1,0,1};

int main(){
  int n,k;
  cin>>n>>k;
  map<int,int> mp;
  rep(i,n){
    int a;
    cin>>a;
    mp[a]++;
  }
  vector<int> cnt;
  for(auto x:mp){
    cnt.push_back(x.second);
  }
  sort(all(cnt));
  ll ans=0;
  int t=mp.size();
  for(int i=0;t>k;i++){
    ans+=cnt[i];
    t--;
  }
  cout<<ans<<endl;
}

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

using namespace std;

/* g++ -g -fsanitize=address -lasan -std=c++11 -Dfoo_ */

/* freopen("input.txt", "rt", stdin); */
/* freopen("output.txt", "wt", stdout); */

#define ALL(c)          (c).begin(), (c).end()
#define ALLR(c)         (c).rbegin(), (c).rend()
#define FOR(i,a,b)      for (int i=(a); i < (b); ++i)
#define FORR(i,a,b)     for (int i=(a); i > (b); --i)
#define FOR_ALL(i,c)    for (__typeof((c).begin()) i=(c).begin();   \
                             i != (c).end(); ++i)
#define FOR_ALLR(i,c)   for (__typeof((c).rbegin()) i=(c).rbegin(); \
                             i != (c).rend(); ++i)
#define SZ(array)       (sizeof(array)/sizeof(array[0]))
#define lc(x)           (x<<1)     /* 2*x */
#define rc(x)           (x<<1 | 1) /* 2*x+1 */
#define lowbit(x)       (x & (-x)) /* 0b10100 -> 0b100 */

typedef long long       LL;
typedef map<int,int>    MII;
typedef pair<int,int>   PII;
typedef set<int>        SI;
typedef vector<bool>    VB;
typedef vector<double>  VD;
typedef vector<int>     VI;
typedef vector<string>  VS;

/* check if a key is in container C */
template <class C>
inline bool in_(const typename C::key_type& k, const C& A)
{ return A.find(k) != A.end(); }
inline bool in_(const string& s, const string& S)
{ return S.find(s) != string::npos; }

const int maxx = 1e3+5;
const int maxy = 1e3+5;
vector<pair<double,double>> A;

double dist(const double x, const double y)
{
    const int n = A.size();
    double ans = 0;
    FOR(i,0,n) {
        const double X = A[i].first;
        const double Y = A[i].second;
        const double dx = x-X;
        const double dy = y-Y;
        const double d = sqrt(dx*dx + dy*dy);
        ans = max(ans,d);
    }
    return ans;
}

double dist(const double x)
{
    double lft = 0, rht = maxy;
    FOR(_,0,100) {
        const double m1 = lft+(rht-lft)/3;
        const double m2 = rht-(rht-lft)/3;
        const double v1 = dist(x,m1);
        const double v2 = dist(x,m2);
        if (v1 > v2)
            lft = m1;
        else
            rht = m2;
    }
    return dist(x,lft);
}

int main()
{
#ifdef foo_
    freopen("foo", "rt", stdin);
#endif
    ios::sync_with_stdio(false);
    int n;
    while (cin >> n) {
        A.resize(n);
        FOR(i,0,n)
            cin >> A[i].first >> A[i].second;
        double lft = 0, rht = maxx;
        FOR(_,0,100) {
            const double m1 = lft+(rht-lft)/3;
            const double m2 = rht-(rht-lft)/3;
            const double v1 = dist(m1);
            const double v2 = dist(m2);
            if (v1 > v2)
                lft = m1;
            else
                rht = m2;
        }
        cout.precision(9);
        cout << fixed << dist(lft) << endl;
    }
    return 0;
}


Measured memory_bytes: 256
import java.util.*;

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

        int X = sc.nextInt();
        int Y = sc.nextInt();
        int Z = sc.nextInt();
        int K = sc.nextInt();

        CakeSet.A = new Long[X];
        CakeSet.B = new Long[Y];
        CakeSet.C = new Long[Z];

        for (int a = 0; a < X; a++) {
            CakeSet.A[a] = sc.nextLong();
        }
        for (int b = 0; b < Y; b++) {
            CakeSet.B[b] = sc.nextLong();
        }
        for (int c = 0; c < Z; c++) {
            CakeSet.C[c] = sc.nextLong();
        }

        Arrays.sort(CakeSet.A, Collections.reverseOrder());
        Arrays.sort(CakeSet.B, Collections.reverseOrder());
        Arrays.sort(CakeSet.C, Collections.reverseOrder());

        TreeSet<CakeSet> cakeSets = new TreeSet<>();
        cakeSets.add(new CakeSet(0, 0, 0));

        for (int k = 0; k < K; k++) {
            CakeSet first = cakeSets.first();
            cakeSets.remove(first);
            System.out.println(first.getTaste());

            int a = first.getA();
            int b = first.getB();
            int c = first.getC();

            if (a < X - 1) {
                cakeSets.add(new CakeSet(a + 1, b, c));
            }
            if (b < Y - 1) {
                cakeSets.add(new CakeSet(a, b + 1, c));
            }
            if (c < Z - 1) {
                cakeSets.add(new CakeSet(a, b, c + 1));
            }
        }
    }

    public static class CakeSet implements Comparable {
        public static Long A[];
        public static Long B[];
        public static Long C[];

        private int a;
        private int b;
        private int c;
        private long taste;

        public CakeSet(int a, int b, int c) {
            this.a = a;
            this.b = b;
            this.c = c;
            this.taste = A[a] + B[b] + C[c];
        }

        public long getTaste() {
            return taste;
        }

        public int getA() {
            return a;
        }

        public int getB() {
            return b;
        }

        public int getC() {
            return c;
        }

        @Override
        public int compareTo(Object o) {
            CakeSet cakeSet2 = (CakeSet) o;

            long diffTaste = getTaste() - cakeSet2.getTaste();
            if (diffTaste > 0) return -1;
            if (diffTaste < 0) return 1;

            int diffA = getA() - cakeSet2.getA();
            int diffB = getB() - cakeSet2.getB();
            int diffC = getC() - cakeSet2.getC();

            return (diffA != 0) ? diffA : ((diffB != 0) ? diffB : diffC);
        }
    }
}


Measured memory_bytes: 30624
import java.util.Arrays;
import java.util.Scanner;

class Main {

	Scanner sc = new Scanner(System.in);
	final static long LNF = 1L << 60;
	final static double EPS = 1e-9;

	public static void main(String[] args) {
		new Main().run();
	}

	void run() {
		int n = ni();
		long w = ni();
		long[] weight = new long[110];
		long[] value = new long[110];

		for (int i = 0; i < n; i++) {
			weight[i] = nl();
			value[i] = nl();
		}

		long[][] dp = new long[110][100100];
		for (int i = 0; i < n; i++) {
			for (int sum_w = 0; sum_w <= w; sum_w++) {
				if(sum_w - weight[i] >= 0) {
					dp[i+1][sum_w] = Util.max(dp[i+1][sum_w], dp[i][(int) (sum_w - weight[i])] + value[i]);
				}
				dp[i+1][sum_w] = Util.max(dp[i+1][sum_w], dp[i][sum_w]);
			}

		}
		System.out.println(dp[n][(int) w]);
	}

	int ni() {
		return Integer.parseInt(sc.next());
	}

	long nl() {
		return sc.nextLong();
	}

	double nd() {
		return Double.parseDouble(sc.next());
	}

	void debug(Object... os) {
		System.out.println(Arrays.deepToString(os));
	}

	static class Util {
		static <T extends Comparable<T>> T max(T a, T b) {
			if (a.compareTo(b) > 0) {
				return a;
			} else {
				return b;
			}
		}

		static <T extends Comparable<T>> T min(T a, T b) {
			if (a.compareTo(b) < 0) {
				return a;
			} else {
				return b;
			}
		}
	}

}


Measured memory_bytes: 272316
n, q = gets.split.map(&:to_i)

count = Array.new(n + 1, 0)
road = Array.new(n + 1) {[]}

(n-1).times do
    a, b = gets.split.map(&:to_i)
    road[a] << b
    road[b] << a
end

q.times do
    q, x = gets.split.map(&:to_i)
    count[q] += x
end

que = [[1, 0]]
while !que.empty?
    now, pre = que.shift
    road[now].each do |i|
        next if i == pre
        count[i] += count[now]
        que << [i, now]
    end
end

puts count[1..-1].join(" ")

Measured memory_bytes: 34684
//  यस्य स्मरणमात्रेण जन्मसंसारबन्धनात् ।  विमुच्यते नमस्तस्मै विष्णवे प्रभविष्णवे ॥

// Float like a butterfly, sting like a bee.

/****
*     Author- Indrajeet Mishra
*             MNNIT Allahabad, Prayagraj
*             Chemical Engineering undergraduate

        2019 will be mine!

*     Behind this mask, a curious child dwells!

****/

#pragma warning(disable:4996)
#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize ("Ofast")
#pragma GCC target ("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma GCC optimize ("-ffloat-store")

#include <bits/stdc++.h>
#define ll long long
#define rep(i,x,y) for(ll i=x;i<y;i++)
#define test(s) if (!(s)) { cout << __LINE__ << " " << #s << endl; exit(-1); }
#define debug(x) do { std::cerr << x; } while (0)
//#define endl "\n"
#define pb push_back
#define pf push_front
#define vll vector<ll>
#define dll deque<ll>
#define sll set<ll, greater <ll>>
#define mll map<ll, ll>
#define vii vector<int>
#define dii deque<int>
#define sii set <int, greater <int>>
#define mii map<int, int>
#define pii pair<int,int>
#define pll pair<ll,ll>
#define mod 1000000007
#define inv2 500000004
#define inv6 166666668
#define N 1000005
#define inf 200000000
#define eps 1e-10
#define PI 3.14159265359
#define all(v) (v).begin(),(v).end()
#define min(a,b) (((a)<(b))?(a):(b))
#define max(a,b) (((a)>(b))?(a):(b))
#define gcd(a,b) __gcd(a,b)


using namespace std;
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    ll n=0,k=0;cin>>n>>k;
    if(n%2==0)
    n/=2;
    else{
        n/=2;
        n++;
    }
    if(n>=k)
    cout<<"YES";
    else cout<<"NO";
    return 0;
}

Measured memory_bytes: 256
#include "bits/stdc++.h"
using namespace std;
const int N = 305;
const int inf = 1e9 + 9;
int n;
int graph[N][N];
vector < pair < int , pair < int , int > > > v;
unsigned dp[N][N];
long long ans;
int main(){
	scanf("%d" , &n);
	for(int i = 1 ; i <= n ; ++i){
		for(int j = 1 ; j <= n ; ++j){
			scanf("%d" , &graph[i][j]);
			if(j > i){
				v.push_back({graph[i][j] , {i , j}});
			}
			dp[i][j] = inf;
		}
		dp[i][i] = 0;
	}
	sort(v.begin() , v.end());
	for(auto it : v){
		int a = it.second.first;
		int b = it.second.second;
		int c = it.first;
		if(dp[a][b] < c){
			printf("-1\n");
			return 0;
		}
		if(dp[a][b] == c){
			continue;
		}
		ans += c;
		for(int i = 1 ; i <= n ; ++i){
			for(int j = 1 ; j <= n ; ++j){
				dp[i][j] = min(dp[i][j] , min(dp[i][a] + dp[b][j] , dp[i][b] + dp[a][j]) + c);
			}
		}
	}
	printf("%lld\n" , ans);
}

Measured memory_bytes: 1656
#include<stdio.h>
#include<stdlib.h>
#include<string.h>

int top = 0, S[1000];

void push(int x){
	S[++top] = x;
}

int pop(void){
	top--;
	return S[top + 1];
}

int main(void){
	int a, b;
	top = 0;
	char s[100];
	while(scanf("%s", s) != EOF){
		if(s[0] == '+'){
			a = pop();
			b = pop();
			push(a + b);
		} else if(s[0] == '-'){
			b = pop();
			a = pop();
			push(a - b);
		} else if(s[0] == '*'){
			a = pop();
			b = pop();
			push(a * b);
		} else if(s[0] == '/'){
			b = pop();
			a = pop();
			push(a / b);
		} else {
			push(atoi(s));
		}
	}
	printf("%d\n", pop());
	
	return 0;
}


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

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    vector<int> a(n);
    rep(i,n) cin >> a[i];
    vector<int> cnt(1000005);
    vector<int> m(1000005);
    rep(i,n) m[a[i]]++;
    bool flag = true;
    for(int i = 2; i <= 1000000; i++){
        int t = 0;
        if(cnt[i] != 0) continue;
        for(int j = i; j <= 1000000; j+=i){
            t += m[j];
            cnt[j]++;
        }
        if(t >= 2){
            flag = false;
            break;
        }
    }
    if(flag){
        cout << "pairwise coprime" << endl;
        return 0;
    }
    int g = a[0];
    rep(i,n) g = __gcd(g, a[i]);
    if(g == 1) cout << "setwise coprime" << endl;
    else cout << "not coprime" << endl;
}


Measured memory_bytes: 15072
N = int(input())
A = list(map(int, input().split()))

cum = [0]

for a in A:
    s = a + cum[-1]
    cum.append(s)

ans = None

for s in cum[1:-1]:
    x = s
    y = cum[-1] - s
    if ans is None:
        ans = abs(x - y)
    else:
        ans = min(ans, abs(x - y))

print(ans)

Measured memory_bytes: 23800
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define MOD 1000000007
#define PI 3.141592653589793
int dx[] = {0,1,-1,0,1,-1,1,-1};
int dy[] = {1,0,0,-1,1,-1,-1,1};

int main(){
    int n, m, x, y;
    cin >> n >> m >> x >> y;
    vector<int> X(n);
    vector<int> Y(m);
    for(int i = 0; i < n; i++)
        cin >> X[i];
    for(int i = 0; i < m; i++)
        cin >> Y[i];
    int xn = *max_element(X.begin(), X.end());
    int ym = *min_element(Y.begin(), Y.end());
    for(int z = xn+1; z <= ym; z++){
        if(z > x && z <= y){
            cout << "No War" << endl;
            return 0;
        }
    }
    cout << "War" << endl;
}


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

int main()
{
    int P, Q, R;
    int min, min2;

    scanf("%d%d%d", &P, &Q, &R);

    if(P > Q){
        min = Q;
        min2 = P;        
    }
    else{
        min = P;
        min2= Q;
    }

    if(min > R){
        min2 = min;
        min  = R;
    }
    else{
        if(min2 > R){
            min2 = R;
        }
    }

    printf("%d",min + min2);
    return 0;
    
}


Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
const int MOD = 1e9 + 7;
const long long INF = 1e15;

#include <math.h>
#define PI 3.14159265358979323846264338327950L

int mxN = 500000;
vector<int> cnt(mxN + 1);

int main() {
    int a, b;
    cin >> a >> b;
    if (a <= 5) {
        cout << 0;
    }
    else if (a <= 12) {
        cout << b / 2;
    }
    else {
        cout << b;
    }

    return 0;
}

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

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

int N, K;

int main() {
    cin >> N;
    ll a[N] = {};
    cin >> a[0];
    ll z = 0;
    if (a[0] == 0) z++;
    for (int i = 1; i < N; i++) {
        cin >> a[i];
        a[i] += a[i-1];
        if (a[i] == 0) z++;
    }
    sort(a, a + N);
    ll n = a[0];
    ll k = 1;
    ll ans = 0;
    for (int i = 1; i < N+1; i++) {
        if (a[i] == n) {
            k++;
        } else {
            ans += (k * (k-1)) / 2;
            k = 1;
            n = a[i];
        }
    }
    ans += (k * (k-1)) / 2;
    ans += z;
    cout << ans << endl;
 
    return 0;
}

Measured memory_bytes: 1792
// eddy1021
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
typedef double D;
typedef long double LD;
typedef long long LL;
typedef pair<int,int> PII;
typedef pair<LL,LL> PLL;
#define mod9 1000000009LL
#define mod7 1000000007LL
#define INF  1023456789LL
#define INF16 10000000000000000LL
#define eps 1e-9
#define SZ(x) (int)(x).size()
#define ALL(x) (x).begin(), (x).end()
#define IOS ios_base::sync_with_stdio(0); cin.tie(0)
#ifndef ONLINE_JUDGE
#define debug(...) printf(__VA_ARGS__)
#else 
#define debug(...)
#endif
inline LL getint(){
  LL _x=0,_tmp=1; char _tc=getchar();    
  while( (_tc<'0'||_tc>'9')&&_tc!='-' ) _tc=getchar();
  if( _tc == '-' ) _tc=getchar() , _tmp = -1;
  while(_tc>='0'&&_tc<='9') _x*=10,_x+=(_tc-'0'),_tc=getchar();
  return _x*_tmp;
}
inline LL add( LL _x , LL _y , LL _mod = mod7 ){
  _x += _y;
  return _x >= _mod ? _x - _mod : _x;
}
inline LL sub( LL _x , LL _y , LL _mod = mod7 ){
  _x -= _y;
  return _x < 0 ? _x + _mod : _x;
}
inline LL mul( LL _x , LL _y , LL _mod = mod7 ){
  _x *= _y;
  return _x >= _mod ? _x % _mod : _x;
}
LL mypow( LL _a , LL _x , LL _mod ){
  if( _x == 0 ) return 1LL;
  LL _ret = mypow( mul( _a , _a , _mod ) , _x >> 1 , _mod );
  if( _x & 1 ) _ret = mul( _ret , _a , _mod );
  return _ret;
}
LL mymul( LL _a , LL _x , LL _mod ){
  if( _x == 0 ) return 0LL;
  LL _ret = mymul( add( _a , _a , _mod ) , _x >> 1 , _mod );
  if( _x & 1 ) _ret = add( _ret , _a , _mod );
  return _ret;
}
inline bool equal( D _x ,  D _y ){
  return _x > _y - eps && _x < _y + eps;
}
void sleep( double sec = 1021 ){
  clock_t s = clock();
  while( clock() - s < CLOCKS_PER_SEC * sec );
}
#define Bye exit(0)
int __ = 1 , _cs;
/*********default*********/

void build(){

}
int n , a , b;
void init(){
  n = getint();
  a = getint();
  b = getint();
}
void solve(){
  puts( (b - a) % 2 ? "Borys" : "Alice" );
}
int main(){
  build();
  //__ = getint();
  while( __ -- ){
    init();
    solve();
  }
}


Measured memory_bytes: 764
#include <iostream>
#include <cstdio>
#include <string>
#include <algorithm>
#include <cstring>
#include <vector>
#include <queue>
#include <map>
#include <set>
#include <bitset>
#include <stack>
#include <cmath>
#include <time.h>
#include <unordered_set>
#include <unordered_map>
#define ll long long
#define LINF 0x3f3f3f3f3f3f3f3f
#define INF 0x3f3f3f3f
#define PI 3.14159265
#define RAND (rand()*rand())
#define MAX(x, y) ((x) > (y) ? (x):(y)) 
#define MIN(x, y) ((x) > (y) ? (y):(x))
#define ABS(x) ((x) > 0 ? (x) : -(x))
#define CEIL(x, y) (((x) + (y) - 1)/(y))
using namespace std;
const int MAXN = 2e5 + 5;
const ll MOD = 1e9 + 7;
int N, M, Q, T;
ll K;
ll A[MAXN], B[MAXN];

int main() {
	int i, j;
	scanf("%d%lld", &N, &K);
	for (i = 1; i <= N; ++i) {
		scanf("%lld", &A[i]);
	}
	for (i = 1; i <= N; ++i) {
		scanf("%lld", &B[i]);
	}
	sort(A + 1, A + 1 + N);
	sort(B + 1, B + 1 + N);
	reverse(B + 1, B + 1 + N);
	ll l = 0ll;
	ll h = A[N] * B[1];
	ll ans = -1ll;
	while (l <= h) {
		ll m = (l + h) >> 1;
		int j = 1;
		ll ck = 0ll;
		for (i = 1; i <= N; ++i, ++j) {
			if (B[i] > m) {
				ck += A[j];
			}
			else {
				if (A[j] * B[i] > m) ck += (A[j] - m / B[i]);
			}
		}
		if (ck <= K) {
			ans = m;
			h = m - 1;
		}
		else l = m + 1;
	}
	printf("%lld", ans);
	return 0;
}

Measured memory_bytes: 3328
#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for (int i = 0;i < (int)(n);i++)
using ll = long long;
const ll MOD=1000000007;
const long long INF = 1LL << 60;
const double pi=acos(-1.0);

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

pair<ll,ll> my_stoi(string S){
  ll N=S.size();
  ll ret=0;
  ll point;
  rep(i,N){
    if(S.at(i)=='.') {point=i; continue;}
    ret*=10;
    ret+=S.at(i)-'0';
  }
  ll keta=1;
  rep(i,N-point-1) keta*=10;
  
  return {ret,keta};
}


int main()
{
  ll N; cin>>N;
  vector<string> A(N); rep(i,N) cin>>A.at(i);
  
  //2と5で何回割れるか
  vector<pair<ll,ll>> vec(N);
  rep(i,N){
    ll bunsi,bunbo; tie(bunsi,bunbo)=my_stoi(A.at(i));
    ll a=bunsi*(1000000000/bunbo);
    ll c2=0,c5=0;
    while(a%2==0){
      a/=2; c2++;
    }
    while(a%5==0){
      a/=5; c5++;
    }
    
    vec.at(i)={c2,c5};
  }
  
  //二次元累積和
  vector<vector<ll>> svec(50,vector<ll>(50,0));
  
  rep(i,N){
    ll c2,c5; tie(c2,c5)=vec.at(i);
    svec.at(c2).at(c5)++;
  }
  rep(i,50){
    for(int j=48;j>=0;j--){
      svec.at(i).at(j)+=svec.at(i).at(j+1);
    }
  }
  rep(i,50){
    for(int j=48;j>=0;j--){
      svec.at(j).at(i)+=svec.at(j+1).at(i);
    }
  }
  
  //解法部分
  ll ans=0;
  rep(i,N){
    ll c2,c5; tie(c2,c5)=vec.at(i);
    ans+=svec.at(max((int)(18-c2),0)).at(max((int)(18-c5),0));
    if(c2*2>=18&&c5*2>=18) ans--;
  }
  
  cout<<ans/2<<endl;
  return 0;
}

Measured memory_bytes: 12748
import java.lang.Integer.max
import java.lang.Integer.min
import java.util.Scanner

fun main(args: Array<String>) =
        try {
            val sc = Scanner(System.`in`)
            val a = sc.nextInt()
            val b = sc.nextInt()
            if (a < 1 || b < 1
                    || a > 1_000_000_000 || b > 1_000_000_000) {
                throw Exception("Illegal inputs.")
            }
            println(fastGcd(a, b))
        } catch (e: Exception) {
            println(e)
        }

fun fastGcd(a: Int, b: Int): Int {
    val x = max(a, b)
    val y = min(a, b)
    if ((x % y) == 0) {
        return y
    }
    return fastGcd(y, (x % y))
}

fun slowGcd(a: Int, b: Int): Int {
    val n = min(a, b)
    for (i in n downTo 1) {
        if (a % i == 0 && b % i == 0) {
            return i
        }
    }
    return 1
}



Measured memory_bytes: 25552
var
	ans,N,i:Longint;
	B:Array[1..110]of Longint;
begin
	read(N);
	for i:=2 to N do read(B[i]);
	B[1]:=200000;
	B[N+1]:=200000;
	for i:=1 to N do begin
		if B[i]<B[i+1]then inc(ans,B[i])else inc(ans,B[i+1]);
	end;
	writeln(ans);
end.


Measured memory_bytes: 128
#include <bits/stdc++.h>
#define st first
#define nd second

using namespace std;

void debug_out() { cerr << endl; }
template<class T> ostream& prnt(ostream& out, T v) { out << v.size() << '\n'; for(auto e : v) out << e << ' '; return out;}
template<class T> ostream& operator<<(ostream& out, vector <T> v) { return prnt(out, v); }
template<class T> ostream& operator<<(ostream& out, set <T> v) { return prnt(out, v); }
template<class T1, class T2> ostream& operator<<(ostream& out, map <T1, T2> v) { return prnt(out, v); }
template<class T1, class T2> ostream& operator<<(ostream& out, pair<T1, T2> p) { return out << '(' << p.st << ' ' << p.nd << ')'; }
template <typename Head, typename... Tail> void debug_out(Head H, Tail... T) { cerr << " " << H; debug_out(T...);}

#define dbg(...) cerr << #__VA_ARGS__ << " ->", debug_out(__VA_ARGS__)
#define dbg_v(x, n) do{cerr<<#x"[]: ";for(int _=0;_<n;++_)cerr<<x[_]<<" ";cerr<<'\n';}while(0)
#define dbg_ok cerr<<"OK!\n"

const int N = 200100;
int n, f[277], mx[N];
string s, re;

vector <int> v[256];

int min_f() {

}

int main() {
	ios_base::sync_with_stdio(false);

	cin >> s;

	int ans = 1, nr = 0;
	for(int i = s.size() - 1; i >= 0; i--) {
		v[s[i]].push_back(i);
		f[s[i]]++;

		if(f[s[i]] == 1) nr++;
		
		if(nr == 26) {
			ans++;
			nr = 0;
			for(int j = 'a'; j <= 'z'; j++) f[j] = 0;
		}
		mx[i] = ans - 1;
	}
	dbg(ans);
	// dbg(v['a']);
	// dbg(v['c']);

	for(int i = 0; i < ans; i++) {
		int lim = s.size();
		for(int j = 'a'; j <= 'z'; j++) {
			if(v[j].empty() || mx[v[j].back() + 1] < ans - i - 1) {
				re += j;
				if(!v[j].empty())
					lim = v[j].back();
				break;
			}
		}
		// if(lim == 0) dbg(i);
		for(int j = 'a'; j <= 'z'; j++)
			while(!v[j].empty() && v[j].back() <= lim)
				v[j].pop_back();
	}
	cout << re << '\n';
}	
	
	

Measured memory_bytes: 2196
N = int(input())

minsum = int(1e4)

for A in range(1,int(N/2)):
    B = N-A
    a_sum = sum(list(map(int, list(str(A)))))
    b_sum = sum(list(map(int, list(str(B)))))
    if minsum > a_sum+b_sum: minsum = a_sum+b_sum

if int(N/2)==1:
    minsum=N
print(minsum)

Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
#define ote(x) cout<<(x)<<endl
#define all(x) (x).begin(),(x).end()
#define rp(i,s,e) for(int i=(s);i<(e);++i)
#define irp(i,s,e) for(int i=(s);i>(e);--i)
template<class T>bool chmax(T &a, const T &b){if(a<b){a=b;return 1;}return 0;}
template<class T>bool chmin(T &a, const T &b){if(b<a){a=b;return 1;}return 0;}

template<class T>void outarr(int s,int e,vector<T> &V){
	for(int i=s;i<e;i++)cout<<V[i]<<(i<e-1?" ":"\n");
}
// outarr<int>(0,V.size(),V);
// outarr<ll>(0,V.size(),V);

// #define NMAX 1000000000
int X,a,b,c;
string S,T;
// int dp[1010101010]

ll solve(){
	ll ans = 0;
	ll c;
	c = X/500;
	ans += c*1000;
	X -= c*500;

	c = X/5;
	ans += c*5;
	X -= c*5;
	return ans;
}

int main(){
	cin>>X;
	cout<< solve() <<endl;
}


Measured memory_bytes: 256
// I hate this problem.
#include <cstdio>
#include <iostream>
#include <string>
#include <vector>
#include <cctype>
#include <algorithm>
#define rep(i,n) for (int i = 0; i < n; ++i)
#define pb push_back
#define rng(x) x.begin(),x.end()
using namespace std;
typedef long long ll;
typedef vector<int> vi;

int main() {
  string s;
  cin >> s;
  int n = 12;
  int x = 0;
  vi a(12);
  rep(i,7) a[i] = i+1;
  rep(i,5) a[7+i] = 7+i-5;
  // for (int xs : a) cout<<xs<<endl;
  reverse(rng(a));
  rep(i,11) {
    if (isdigit(s[i])) x += (s[i]-'0')*a[i];
  }
  x %= 11;
  // cout<<x<<endl;
  if (s.back() == '?') {
    int ans = 0;
    if (x <= 1) ans = 0;
    else ans = 11-x;
    cout<<ans<<endl;
  } else {
    if (s.back() == '0') {
      x = (0-x+11)%11;
      string t = s;
      int ans = -1;
      int cnt = 0;
      rep(i,n) {
        if (s[i] == '?') {
          rep(j,10) if (a[i]*j%11 == x) {
            s[i] = '0'+j;
            cnt++;
            ans = j;
          }
        }
      }
      swap(s,t);
      x = (x+1)%11;
      rep(i,n) {
        if (s[i] == '?') {
          rep(j,10) if (a[i]*j%11 == x) {
            s[i] = '0'+j;
            cnt++;
            ans = j;
          }
        }
      }
      if (cnt >= 2) puts("MULTIPLE");
      else cout<<ans<<endl;
    } else {
      int y = 11-(s.back()-'0');
      x = (y-x+11)%11;
      int ans = -1;
      rep(i,n) {
        if (s[i] == '?') {
          rep(j,10) if (a[i]*j%11 == x) {
            s[i] = '0'+j;
            ans = j;
          }
        }
      }
      cout<<ans<<endl;
    }
  }
  return 0;
}

Measured memory_bytes: 3196
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 200000;

void solve()
{
    int n; cin >> n;
    cout << abs(n - ceil((float)n / 1000) * 1000) << '\n';
}
 
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
    //freopen("input.txt", "r", stdin);
 
    // int t; cin >> t;
    // while(t--)
        solve();
    
    return 0;
}

Measured memory_bytes: 3800
import java.util.Scanner;

 
public class Main {
 
	public static void main(String[] args) {
		
		Scanner sc = new Scanner(System.in);
		int x  = sc.nextInt();
        
		while(!isPrime(x)) {
			x++;
		}
					
		System.out.println(x);
		sc.close();
	}

	private static boolean isPrime(int x) {
		for(int i = 2; i <= Math.sqrt(x); i++) {
			if(x % i == 0) {
				return false;
			}
		}
		
		return true;
	}
	
}

Measured memory_bytes: 35812
#include<iostream>
#include<vector>
#include<map>
#include<set>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<string>
#include<queue>
#include<complex>
#include<numeric>
#include<bitset>
#define INF 1001001001
#define EPS 0.000000001

#define x first
#define y second
#define M 1000000

using namespace std;
typedef vector<int> vint;
typedef vector<vint> vvint;
typedef pair<int,int> pint;

int dx[4] = {-1,0,1,0};
int dy[4] = {0,-1,0,1};
//int dx[8] = {0,1,1,1,0,-1,-1,-1};
//int dy[8] = {1,1,0,-1,-1,-1,0,1};

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


int main(){
	vint ss;
	vint so;
	
	static int nums[M+1];
	static int numo[M+1];
	
	for(int i=0; i<=M; i++){
		nums[i] = INF;
		numo[i] = INF;
	}
	
	for(int i=1; i<200; i++){
		int n = i*(i+1)*(i+2)/6;
		if(n>M) break;
		
		ss.push_back(n);
		nums[n]=1;
		if(n%2==1){
			so.push_back(n);
			numo[n]=1;
		}
	}
	
	for(int i=1; i<=M; i++){
		for(int j=0; j<ss.size(); j++){
			if(i+ss[j]>M) break;
			nums[i+ss[j]] = min(nums[i+ss[j]], nums[i]+1);
		}
		for(int j=0; j<so.size(); j++){
			if(i+so[j]>M) break;
			numo[i+so[j]] = min(numo[i+so[j]], numo[i]+1);
		}
	}
	
	while(1){
		int a = nextInt();
		if(a==0) break;
		printf("%d %d\n", nums[a], numo[a]);
	}
	return 0;
}

Measured memory_bytes: 8668
n, m = map(int, input().split())
s = []
k = []
for i in range(m):
    s.append(list(map(int,input().split())))
    k.append(s[i].pop(0))
p = [int(i) for i in input().split()]

ans = 0
for i in range(2**n):
    ok = True
    for j in range(m):
        cnt = 0
        for l in range(k[j]):
            if i & (1 << (s[j][l]-1)):
                cnt += 1
        if cnt % 2 != p[j]:
            ok = False
    if ok:
        ans += 1
print(ans)

Measured memory_bytes: 3316