akhauriyash/Code-Regression huggingface dataset:
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;

const ll MOD = 1000000007;

class Combination{
    private:
    vector<ll>fact, inv;
    ll mod;
    ll modpow(ll x, ll n){
        ll res = 1;
        while(n > 0){
            if(n & 1)res = res * x % mod;
            x = x * x % mod;
            n >>= 1;
        }
        return res;
    }
    ll modinv(ll x){
        ll y = mod, u = 1, v = 0;
        while(y){
            ll t = x / y;
            x -= t * y; swap(x, y);
            u -= t * v; swap(u, v);
        }
        u %= mod;
        if(u < 0)u += mod;
        return u;
    }

    public:
    Combination(ll num, ll _mod = 1000000007){
        fact = vector<ll>(2 * num + 10);
        inv = vector<ll>(2 * num + 10);
        mod = _mod;
        fact[0] = 1;
        inv[0] = modinv(fact[0]);
        for(ll i = 1; i < fact.size(); i++){
            fact[i] = fact[i - 1] * i % mod;
            inv[i] = modinv(fact[i]);
        }
    }
    ll factrial(ll n){
        return fact[n];
    }
    ll nPk(ll n, ll k){
        return fact[n] * inv[n - k] % mod;
    }
    ll nCk(ll n, ll k){
        return nPk(n, k) * inv[k] % mod;
    }
    ll nHk(ll n, ll k){
        return nCk(n+k-1, k);
    }
};

int main(){
    
    ll N;
    cin >> N;
    N++;
    Combination cmb(N, MOD);
    vector<ll>pos(N, -1);
    int l, r;
    for(int i = 0; i < N; i++){
        int a;
        cin >> a;
        if(pos[a] == -1)pos[a] = i;
        else{
            l = pos[a];
            r = i;
        }
    }
    int len = l + N - r - 1;
    for(int i = 1; i <= N; i++){
        ll ans = cmb.nCk(N, i);
        if(len >= i - 1){
            ll tmp  = cmb.nCk(len, i - 1);
            ans -= tmp;
            if(ans < 0)ans += MOD;
            ans %= MOD;
        }
        cout << ans << endl;
    }

    return 0;
}

Measured memory_bytes: 5120
i=int(input())
if(0<i and i<10):
    cnt1=i
    print(cnt1)
if(10<=i and i<100):
    print(9)
if(100<=i and i<1000):
    cnt2=i-99+9
    print(cnt2)
if(1000<=i and i<10000):
    print(909)
if(10000<=i and i<100000):
    cnt3=i-9999+999-99+9
    print(cnt3)
if(i==100000):
    print(90909)

Measured memory_bytes: 3064
n, c, k = gets.split.map(&:to_i)
ts = n.times.map { gets.to_i }.sort!.reverse!

ans = 1
base = ts[0]
passengers = 1

1.upto(n - 1) do |i|
  if ts[i] + k < base || (ts[i] + k <= base + k && passengers == c)
    ans += 1
    passengers = 0
    base = ts[i]
  end

  passengers += 1
end

puts ans


Measured memory_bytes: 4016
#include <iostream>
#include <fstream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <cstring>
#include <string>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <algorithm>
#include <array>
#include <bitset>
#include <assert.h>
using namespace std;

#define REP(i,n) for(int i=0; i<n; ++i)
#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 ALL(c) (c).begin(), (c).end()

typedef long long ll;
typedef vector<int> VI;
typedef vector<ll> VL;
typedef vector<VI> VVI;
typedef vector<VL> VVL;
typedef pair<int,int> P;
typedef pair<ll,ll> PL;

int in() { int x; scanf("%d", &x); return x; }
ll lin() { ll x; scanf("%lld", &x); return x; }

int main() {
    int n, m;
    cin >> n >> m;
    vector<P> p(n);
    multiset<int> st;
    REP(i,n){
        p[i].first = in();
        p[i].second = in();
        st.insert(p[i].second);
    }
    sort(ALL(p));

    int l = 0;
    REP(i,n){
        if (l < p[i].first && l <= m) l++;
    }

    priority_queue<int> que;
    int j = n;
    FORR(i,l,1){
        while (j > 0 && p[j - 1].first >= i){
            que.push(p[j - 1].second);
            j--;
        }
        int x = que.top();
        que.pop();
        st.erase(st.find(x));
    }

    VI hoge;
    for (int x : st) hoge.push_back(x);
    reverse(ALL(hoge));

    int r = m + 1;
    for (int x : hoge){
        // cout << x << endl;
        if (x < r && r - 1 > l) r--;
    }

    // cout << l << " " << r << endl;

    cout << n - (l + (m - r + 1)) << endl;


    return 0;
}

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

using namespace std;

int main() {

    int n;
    cin>>n;
    vector<vector<int>> points(n, vector<int>(3, 0));
    for(int i = 0; i < n; i++ ) {
        for(int j = 0; j < 3; j++ ) {
            cin>>points[i][j];
        }
    }
    // The following method has O(n^2) space complexity

    // vector<vector<int>> dp(n, vector<int>(3, INT_MIN));

    // for(int i = 0; i < 3; ++i) {
    //     dp[n-1][i] = points[n-1][i];
    // }

    // for(int i = n-2; i >= 0; i--) {
    //     for(int r = 0; r < 3; r++) {
    //         for(int j = 0; j < 3; j++) {
    //             if(j != r) {
    //                 dp[i][r] = max(dp[i][r], dp[i+1][j] + points[i][r]);
    //             }
    //         }
    //     }
    // }

    // Optimized Approach Space Complexity - O(6)

    vector<int> dp(points[n-1].begin(), points[n-1].end());

    for(int i = n-2; i >= 0; i--) {
        vector<int> newDp(3, 0);
        for(int c = 0; c < 3; c++ ) {
            for(int j = 0; j < 3; j++ ) {
                if(j!= c) {
                    newDp[c] = max(newDp[c], dp[j] + points[i][c]);
                }
            }
        }
        dp = newDp;
    }

    cout<<*max_element(dp.begin(), dp.end())<<endl;
}

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

int main() {
  int N;
  cin >> N;
  if (N % 2 == 1) {
    ++N;
  }
  cout << (N) / 2 << endl;
  return 0;
}


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

int main(){
	int N;
	cin >> N;
	int A[N];
	for(int i=0; i<N; i++){
		cin >> A[i];
	}
	ll sum = 0, ans = 0;
	map<ll, int> M;
	for(int i=0; i<N; i++){
		sum += A[i];
		if(sum == 0) ans++;
		ans += M[sum];
		M[sum]++;
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 13568
#ifndef _GLIBCXX_NO_ASSERT
#include <cassert>
#endif
#include <cctype>
#include <cerrno>
#include <cfloat>
#include <ciso646>
#include <climits>
#include <clocale>
#include <cmath>
#include <csetjmp>
#include <csignal>
#include <cstdarg>
#include <cstddef>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>

#if __cplusplus >= 201103L
#include <ccomplex>
#include <cfenv>
#include <cinttypes>
#include <cstdbool>
#include <cstdint>
#include <ctgmath>
#include <cwchar>
#include <cwctype>
#endif

// C++
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>

#if __cplusplus >= 201103L
#include <array>
#include <atomic>
#include <chrono>
#include <condition_variable>
#include <forward_list>
#include <future>
#include <initializer_list>
#include <mutex>
#include <random>
#include <ratio>
#include <regex>
#include <scoped_allocator>
#include <system_error>
#include <thread>
#include <tuple>
#include <typeindex>
#include <type_traits>
#include <unordered_map>
#include <unordered_set>
#endif
using namespace std;

typedef long long ll;
//typedef pair<int,int> Pint;
typedef pair<ll, ll> P;
//typedef pair<int, pair<int, int>> P;
//typedef tuple<int,int,int> T;
typedef vector<ll> vec;
typedef vector<vec> mat;
#define rep(i, n) for(ll i = 0; i < n; i++)
#define revrep(i, n) for(ll i = n-1; i >= 0; i--)
ll max(ll a, ll b){return (a > b) ? a : b;}
ll min(ll a, ll b){return (a < b) ? a : b;}
ll Mypow(ll x, ll k){
  ll res = 1;
  while(k > 0){
    if(k % 2) res *= x;
    x *= x;
    k /= 2;
  }
  return res;
}

ll gcd(ll a, ll b){//計算量はO(log(max(a,b))
    if(b == 0) return a;
    return gcd(b, a % b);
}

ll INFL = 1LL << 60;//10^18 = 2^60
int INF = 1 << 30;//10^9
ll MOD  = 1000000007;
//vector<int> dy = {0,0,1,-1};
//vector<int> dx = {1,-1,0,0};

ll kai(ll x){
  if(x == 1) return 1;
  return x * kai(x-1) % MOD;
}



int main(){
  int H, W; cin >> H >> W;
  char mp[H][W];
  rep(i, H)rep(j, W) cin >> mp[i][j];
  rep(i, 2*H){
    rep(j, W){
      cout << mp[i/2][j];
    }
    cout << endl;
  }
}


Measured memory_bytes: 256
#include<iostream>
using namespace std;
int main(){
int h,w;
while(true){
cin>>h>>w;
if(h==0&&w==0){
  break;
}else{
  for(int i=0;i<h;i++){
    for(int i=0;i<w;i++){
     cout <<"#";
    }
    cout <<endl;
  }
  cout <<endl;
}
}
return 0;
}

Measured memory_bytes: 3096
#include <iostream>
using namespace std;
 
int main(){

    int n;

    cin >> n;

    int a;

    int i;

    double sum = 0.0;

    for(i=0; i<n; i++){
        cin >> a;

        sum += 1.0 / (float)a;
    }

    cout << 1.0 / sum << endl; 

    return 0;
}

Measured memory_bytes: 256
#include <algorithm>
#include <iostream>
#include <math.h>
#include <stdio.h>
#include <string>
#include <stack>
#include <sstream>
#include <vector>
#include <set>
#include <map>
#include <cmath>
#define rep(i, n) for(int i = 0; i < (int)(n); i++)

using namespace std;
typedef long long int ll;
const ll modP = 1000000007;


int main()
{

	int n;
	cin>>n;
	cout<<n + n*n + n*n*n<<endl; 
	return 0;
}


Measured memory_bytes: 3152
use std::io::{stdin, Read, StdinLock};
use std::str::FromStr;

fn main() {
    let cin = stdin();
    let mut scan = Scanner::new(cin.lock());
    let n = scan.read::<i64>();
    if n % 2 == 1 {
        println!("{}", 0);
    } else {
        let mut cnt = 0;
        for k in 1.. {
            let p = 5f64.powi(k) as i64;
            if n / p == 0 {
                break;
            }
            cnt += n / 2 / p;
        }
        println!("{}", cnt);
    }
}

// region template
#[allow(dead_code)]
fn iu(i: i64) -> usize { i as usize }

#[allow(dead_code)]
fn ui(i: usize) -> i64 { i as i64 }

#[allow(dead_code, deprecated)]
fn join<T: std::fmt::Display>(slice: &[T], sep: &str) -> String {
    let strings = slice.iter().map(|t| format!("{}", t)).collect::<Vec<_>>();
    strings.connect(sep)
}

#[allow(dead_code)]
fn arr<'a, S, T>(n: usize, mut f: S) -> Vec<T> where S: FnMut(usize) -> T + 'a {
    (0..n).map(|i| f(i)).collect::<Vec<T>>()
}

struct Scanner<'a> {
    cin: StdinLock<'a>,
}

#[allow(dead_code)]
impl<'a> Scanner<'a> {
    fn new(cin: StdinLock<'a>) -> Scanner<'a> {
        Scanner { cin: cin }
    }

    fn read1<T: FromStr>(&mut self) -> Option<T> {
        let token = self.cin.by_ref().bytes().map(|c| c.unwrap() as char)
            .skip_while(|c| c.is_whitespace())
            .take_while(|c| !c.is_whitespace())
            .collect::<String>();
        token.parse::<T>().ok()
    }

    fn read<T: FromStr>(&mut self) -> T {
        self.read1().unwrap()
    }

    fn readn<T: FromStr>(&mut self, n: usize) -> Vec<T> {
        (0..n).map(|_| self.read::<T>()).collect()
    }

    fn chars(&mut self) -> Vec<char> {
        self.read::<String>().chars().collect()
    }
}
// endregion

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

int main()
{
	string s;
	cin >> s;
	int x;
	rep(i,3)
	{
		if(s[i]=='1')
			x++;
	}
	cout << x;
	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define endl "\n"
int main()
{
	int t;
	t=1;;
	while(t--)
	{
      ll a,b,c;
      cin>>a>>b>>c;
      //800 -800
      //kuch bhi least or say close to give gnerate it
      ll k=a/c;
      if(abs(k)>b)
      {
      	k=b;
      }
      b=b-k;
      ll q1=(a-(k*c));
      ll q2=(a+(k*c));
      if(b%2==0)
      {
      ll h1=abs(q1);
      ll h2=abs(q2);
      if(h1>h2)
      {
      cout<<h2<<endl;
      }
      else
      {
      cout<<h1<<endl;
      }

      }
      else
      {
       ll a1=abs(q1-c);
       ll a2=abs(q1+c);
       ll a3=abs(q2+c);
       ll a4=abs(q2-c);
       ll d1=a1;
       ll d2=a3;
       if(a1>a2)
       {
         d1=a2;
       }
       if(a3>a4)
       {
       	d2=a4;
       }
       ll ans=d1;
       if(d1>d2)
       {
       	ans=d2;
       }
       cout<<ans<<endl;
       
      }
	}
}

Measured memory_bytes: 3588
k = [1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51]
n = int(input())
print(k[n-1])

Measured memory_bytes: 3060
#include "bits/stdc++.h"
using namespace std;
#define int long long
#define FOR(i, a, b) for(int i=(a);i<(b);i++)
#define RFOR(i, a, b) for(int i=(b-1);i>=(a);i--)
#define REP(i, n) for(int i=0; i<(n); i++)
#define RREP(i, n) for(int i=(n-1); i>=0; i--)
#define REP1(i, n) for(int i=1; i<=(n); i++)
#define RREP1(i, n) for(int i=(n); i>=1; i--)
#define ALL(a) (a).begin(),(a).end()
#define UNIQUE_SORT(l) sort(ALL(l)); l.erase(unique(ALL(l)), l.end());
#define CONTAIN(a, b) find(ALL(a), (b)) != (a).end()
#define out(...) printf(__VA_ARGS__)

int dxy[] = {0, 1, 0, -1, 0};

void solve();
signed main()
{
#if DEBUG
    std::ifstream in("input.txt");
    std::cin.rdbuf(in.rdbuf());
#endif
    cin.tie(0);
    ios::sync_with_stdio(false);
    solve();
    return 0;
}

/*================================*/
#if DEBUG
#define SIZE 100
#else
#define SIZE 123450
#endif

int S,W;

void solve() {
    cin>>S>>W;
    cout << ((W>=S) ? "unsafe" : "safe") << endl;
}

Measured memory_bytes: 3636
#include <bits/stdc++.h>
using namespace std;
#define REP(i, n) for(int i = 0; i < n; i++)
#define REPR(i, n) for(int i = n - 1; 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 SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end());
 
using ll = long long;
using vll = vector<ll>;
using vvll = vector<vector<ll>>;
using P = pair<ll, ll>;

int main(){
	ll x, y, z, k;
    cin >> x >> y >> z >> k;
    vll a(x), b(y), c(z);
    REP(i, x) cin >> a[i];
    REP(i, y) cin >> b[i];
    REP(i, z) cin >> c[i];

    vll ab(x * y);
    REP(i, x){
        REP(j, y){
            ab.push_back(a[i] + b[j]);
        }
    }
    sort(ab.rbegin(), ab.rend());
    sort(c.rbegin(), c.rend());

    ll s, t, res = 1e15;

    REP(i, k){
        REP(j, k){
            if(i >= x * y || j >= z) continue;
            if(ab[i] + c[j] < res){
                s = i + 1;
                t = j + 1;
            }
        }
    }

    vll ans;
    REP(i, s){
        REP(j, t){
            ans.push_back(ab[i] + c[j]);
        }
    }

    sort(ans.rbegin(), ans.rend());
    REP(i, k) cout << ans[i] << endl;
    return 0;
}

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

using namespace std;

main(){
		int l;
		while(cin>>l){
			int o=0;
			for (int a=0; a < 10; a++){
				for (int b=0; b < 10; b++){
					for (int c=0; c < 10; c++){
						for (int d=0; d< 10; d++){
							if(a+b+c+d==l){
								o=o+1;
							}
						}
					}
				}
			}
			printf("%d\n",o);
		}
}



Measured memory_bytes: 3064
import scala.io.StdIn

object Main{
  def main(args: Array[String]){
    val inputs = Iterator.continually(StdIn.readLine()).takeWhile(_ != null)
    for{
      in <- inputs
      val Array(a, b, c, _*) = in.split(" ").map(_.toInt)
    }(a, b, c) match {
      case (-1, -1, -1) => 
      case (-1, _, _) => println("F")
      case (_ ,-1, _) => println("F")
      case (a, b, c) if a+b >= 80 => println("A")
      case (a, b, c) if a+b >= 65 && a+b < 80 => println("B")
      case (a, b, c) if a+b >= 50 && a+b < 65 => println("C")
      case (a, b, c) if a+b >= 30 && a+b < 50 && c < 50 => println("D")
      case (a, b, c) if c >= 50 => println("C")
      case (a, b, c) if a+b < 30 => println("F")
      case _ =>
    }
  }
}

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

int main(){
    int n; cin >> n;
    for(int i = 0; i <= n; i+=4){
        for(int j = 0; i + j <= n; j+=7){
            if(i + j == n) {
                cout << "Yes" << endl;
                return 0;
            }
        }
    }
    cout << "No" << endl;
    return 0;
}

Measured memory_bytes: 256
import java.io.*;
import java.util.*;

class Main{
    public static void main(String[] args){
        solve();
    }

    public static void solve(){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] x = new int[n];
        int[] y = new int[n];
        int[] h = new int[n];
        int number = 0;
        for(int i=0;i<n;i++){
        	x[i] = sc.nextInt();
        	y[i] = sc.nextInt();
        	h[i] = sc.nextInt();
        	if(h[i]!=0){
        		number = i;
        	}
        }
        int X = 0;
        int Y = 0;
        int H = 0;
        for(int i=0;i<=100;i++){
        	for(int j=0;j<=100;j++){
        		int hnew = h[number] + Math.abs(i-x[number]) + Math.abs(j-y[number]);
        		boolean flag = true;
        		for(int k=0;k<n;k++){
        			int hh = Math.max(hnew - Math.abs(i-x[k]) - Math.abs(j-y[k]), 0);
        			if(h[k] != hh){
        				flag = false;
        				break;
        			}
        		}
        		if(flag){
        			X = i;
        			Y = j;
        			H = Math.max(hnew, 0);
        		}
        	}
        }
        System.out.println(X+" "+Y+" "+H);
    }
}

Measured memory_bytes: 23764
#include <map>
#include <set>
#include <list>
#include <cmath>
#include <queue>
#include <stack>
#include <cstdio>
#include <string>
#include <vector>
#include <complex>
#include <cstdlib>
#include <cstring>
#include <numeric>
#include <sstream>
#include <iostream>
#include <algorithm>
#include <functional>
 
#define mp       make_pair
#define pb       push_back
#define all(x)   (x).begin(),(x).end()
#define rep(i,n) for(int i=0;i<(n);i++)
 
using namespace std;
 
typedef    long long          ll;
typedef    unsigned long long ull;
typedef    vector<bool>       vb;
typedef    vector<int>        vi;
typedef    vector<vb>         vvb;
typedef    vector<vi>         vvi;
typedef    pair<int,int>      pii;
 
const int INF=1<<29;
const double EPS=1e-9;
 
const int dx[]={1,0,-1,0},dy[]={0,-1,0,1};

int tree[500000];
int N;

void maxHeapify(int i) {
	int l = i * 2 + 1;
	int r = i * 2 + 2;
	int largest = i;
	if (l < N && tree[l] > tree[largest]) largest = l;
	if (r < N && tree[r] > tree[largest]) largest = r;

	if (largest != i) {
		int temp = tree[i];
		tree[i] = tree[largest];
		tree[largest] = temp;
		maxHeapify(largest);
	}
}

void buildMaxHeap() {
	for (int i = N / 2 - 1; i >= 0; i--) {
		maxHeapify(i);
	}
}

int main(int argc, char const *argv[]) {
	for (int i = 0; i < 250; ++i) {
		tree[i] = 2000000001;
	}
	cin >> N;
	for (int i = 0; i < N; ++i) {
		cin >> tree[i];
	}
	buildMaxHeap();
	for (int i = 0; i < N; ++i) {
		cout << " " << tree[i];
	}
	cout << endl;
	

	return 0;
}

Measured memory_bytes: 3112
#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>//"geometry.cpp"
using namespace std;
#define pb push_back//Can be used for STRING
#define fi first
#define sc second
#define mp make_pair
#define is insert
typedef pair<int,int> pii;//Add other types in the same way.

#define MAX_N 50

long long n,a[MAX_N];

bool calc(int i){
	bool ret=true;
	for(int j=0;j<n;++j) if(i!=j){
		a[j]+=a[i]/n;
		if(a[j]>=n) ret=false;
	}
	a[i]%=n;
	return ret;
}

int main(){
	cin>>n;
	long long ans=0;
	for(int i=0;i<n;++i){
		cin>>a[i];
		ans+=a[i];
	}
	for(int i=0;;++i) if(calc(i%n)) break;
	for(int i=0;i<n;++i) ans-=a[i];
	cout<<ans<<endl;
}

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

int main(){
    char c;
    cin >> c;
    if(c == 'a' || 
       c == 'e' || 
       c == 'i' || 
       c == 'o' || 
       c == 'u') cout << "vowel" << endl;
    else cout << "consonant" << endl;
    return 0;
}

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

int main()
{
    const int ROOM = 10;
    const int FLOOR = 3;
    const int BUILDING = 4;
    int n,b,f,r,v;
    int arr[BUILDING][FLOOR][ROOM] = {{}};
    cin>>n;
    for(int i=0;i<n;i++)
    {
        cin>>b>>f>>r>>v;
        arr[b-1][f-1][r-1] += v;
    }

    for(int i=0;i<BUILDING;i++)
    {
        for(int j=0;j<FLOOR;j++)
        {
            for(int k=0;k<ROOM;k++)
            {
                    cout<<" "<<arr[i][j][k];
            }
            cout<<"\n";
        }
        if(i==BUILDING-1)break;

        cout<<"####################"<<"\n";
    }

    return 0;
}

Measured memory_bytes: 1164
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
ll MOD=1000000007;

int main() {
    ll X; cin>>X;
    for(int i=-200;i<=200;i++){
        for(int j=-200;j<=200;j++){
            if(X==pow(i,5)-pow(j,5)){
                cout<<i<<" "<<j;
                return 0;
            }
        }
    }
    return 0;
}

Measured memory_bytes: 4012
#include <bits/stdc++.h>
using namespace std;
 
#define int long long
#define pb push_back
#define ub upper_bound
#define lb upper_bound
#define mp make_pair
#define F first
#define S second
#define FOR(i,a,b) for(int (i)=(a);(i)<(b);(i)++)
#define REP(i,n) FOR(i,0,n)
#define ALL(a) (a).begin(),(a).end()
#define RALL(a) (a).rbegin(),(a).rend()
#define SORT(c) sort((c).begin(),(c).end())
#define ve vector
#define vi vector<int>
#define vp vector<pair<int,int>>
#define vvi vector<vector<int>>
 
typedef long long ll;
const ll INF = LLONG_MAX - 100;
const ll mod = 1e9 + 7;
const int MAX_N = 2e5 + 5;
int dx[] = {-1,0,1,0}, dy[] = {0,1,0,-1};
vector<ll> prime;
 
int fac[MAX_N], inv[MAX_N];
 
template <class T = ll> T in() {T x; cin >> x; return (x);}
void DEBUG(vector<int> a) {for(int i=0;i<a.size();i++)cout<<a[i]<<" ";cout<<endl;}
ll GCD(ll a, ll b) {ll c; while (b != 0) {c = a % b; a = b; b = c;}return a;}
ll LCM(ll a, ll b) {return a * b / GCD(a, b);}
ll POW(ll a, ll b, bool usemod = true) {ll c = 1LL; while (b > 0) {if (b & 1LL) {if(!usemod)c*=a;else c = a * c%mod;}if (!usemod) a*=a;else a = a * a%mod; b >>= 1LL;}return c;}
void _nCr() {fac[0] = 1LL; for (int i = 1LL; i < MAX_N; i++) {fac[i] = fac[i - 1LL] * i%mod;}for (int i = 0; i < MAX_N; i++) {inv[i] = POW(fac[i], mod - 2);}}
ll nCr(ll n, ll r) {return (fac[n] * inv[r] % mod)*inv[n - r] % mod;}
void PRI(ll n) {bool a[n + 1LL]; for (int i = 0; i < n + 1LL; i++) {a[i] = 1LL;}for (int i = 2; i < n + 1LL; i++) {if (a[i]) {prime.pb(i); ll b = i; while (b <= n) {a[b] = 0; b += i;}}}}
template <typename T> T chmin(T& a, T b) {if(a>b)a=b;return a;}
template <typename T> T chmax(T& a, T b) {if(a<b)a=b;return b;}

class UnionFind {
private:
	vector<int> par;
public:
	vector<set<int>> X;
	vector<set<int>> Y;
	UnionFind(int N) {par = vector<int>(N, -1);}
	int find(int x);
	ll size(int x);
	void unite(int x, int y);
	bool same(int x, int y);
};

int UnionFind::find(int x) {
	if (par[x] < 0) return x;
	else return par[x] = find(par[x]);
}
 
ll UnionFind::size(int x) {
	return -par[find(x)];
}
 
void UnionFind::unite(int x, int y) {
	x = find(x);
	y = find(y);
 	if (x == y) return;
	//大きい方に小さい方をくっ付ける
	if (size(x) < size(y)) swap(x, y);
	par[x] += par[y];
	par[y] = x;
}
 
bool UnionFind::same(int x, int y) {
	x = find(x);
	y = find(y);
	return x == y;
}

int v,e;
const int MAX = 100010;
vector<int> g[MAX];
bool used[MAX];
vector<int> ans;
int anc[MAX];

void dfs(int u) {
	if (used[u]) return;
	used[u] = true;
	for (auto & i : g[u]) {
		dfs(i);
	}
	ans.push_back(u);
}

void tsort() {
	REP (i,MAX) anc[i] = 0;
	REP (i,v) dfs(i);
	reverse(ALL(ans));
}

bool solve() {
	int n,m;cin >> n >> m;
	v = n; e = n + m -1;
	REP (i,n+m-1) {
		int s,t;cin >> s >> t;
		g[--s].push_back(--t);
	}
	tsort();
	REP (i,n) {
		for (auto &a : g[ans[i]]) {
			anc[a] = ans[i]+1;
		}
	}
	REP (i,n) {
		cout << anc[i] << endl;
	}
}

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

Measured memory_bytes: 12148
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using ld=long double;
using vi=vector<int>;
using vvi=vector<vi>;
using vl=vector<ll>;
using vvl=vector<vl>;
using pii=pair<int,int>;
using pll=pair<ll,ll>;
const ll LINF=0x1fffffffffffffff;
const int INF=0x3fffffff;
const int MOD=1000000007;
#define VAR(type,...) type __VA_ARGS__;in(__VA_ARGS__)
#define VEC(type,name,size) vector<type> name(size);each(i, name)in(i)
#define rep(i,a,b) for(int i=(a);i<(b);++i)
#define rrep(i,a,b) for(int i=(a-1);i>=(b);--i)
#define each(i,v) for(auto &i:(v))
#define all(v) (v).begin(),(v).end()
#define print(...) out(__VA_ARGS__);cout<<endl
void in(){} template<class T,class... U> void in(T &t,U &...u){cin>>t;in(u...);}
void out(){} template<class T,class... U> void out(T t,U ...u){cout<<t<<" ";out(u...);}
void solve();
int main(){cin.tie(0);ios::sync_with_stdio(0);solve();}

void solve() {
  VEC(string, s, 3);
  cout << s[0][0] << s[1][1] << s[2][2] << endl;
}


Measured memory_bytes: 256
let main () =
  let flag = ref true in
  let a, b = Scanf.scanf "%d %d\n" (fun a b -> a, b) in
  let c = Array.make a "" in
  for i = 0 to a - 1 do
    c.(i) <- Scanf.scanf "%s\n" (fun a -> a)
  done;
  for i = 0 to a - 1 do
    for j = 0 to b - 1 do
      if !flag = true && Char.compare (String.get c.(i) j) '#' = 0 then (
        flag := false;
        if i > 0 then (
          if Char.compare (String.get c.(i - 1) j) '#' = 0 then flag := true
        );
        if i < a - 1 && not !flag then (
          if Char.compare (String.get c.(i + 1) j) '#' = 0 then flag := true
        );
        if j > 0 && not !flag then (
          if Char.compare (String.get c.(i) (j - 1)) '#' = 0 then flag := true
        );
        if j < b - 1 && not !flag then (
          if Char.compare (String.get c.(i) (j + 1)) '#' = 0 then flag := true
        );
      )
    done;
  done;
  Printf.printf "%s\n" (if !flag then "Yes" else "No")

let _ = main ()


Measured memory_bytes: 512
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main{ // 

	public static void main(String args[]) {
		ConsoleScanner cin = new ConsoleScanner();
		PrintWriter cout = new PrintWriter(System.out);
		solve(cin, cout);
		cout.flush();
	}

	static long now() {
		return System.currentTimeMillis();
	}

	static void trace(Object... objects) {
		assert null != System.out.format("trace:%s\n", Arrays.deepToString(objects));
	}

	private static void solve(ConsoleScanner cin, PrintWriter cout) {
		// assert solve(1) == 1;

		String s = cin.next();

		long start = now();

		String ans = solve(s);
		cout.println(ans);

		trace("elapsed", now() - start);
	}

	private static String solve(String s) {
		int n = s.length();
		return s.substring(0, 1) + (n - 2) + s.charAt(n - 1);
	}

	static class ConsoleScanner {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer("");

		String next() {
			try {
				while (!st.hasMoreElements())
					st = new StringTokenizer(br.readLine());
				return st.nextToken();
			} catch (IOException e) {
				throw new AssertionError(e);
			}
		}

		int nextInt() {
			return Integer.parseInt(next());
		}

		long nextLong() {
			return Long.parseLong(next());
		}
	}

}


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

using namespace std;

const int maxn = 2e5+1;

int a[maxn], ls[maxn];
long long dp[maxn];
int n, p;

int bp(int x, int k) {
  if (!k) return 1;
  if (k % 2) return (x * bp(x, k - 1)) % p;
  return bp((x * x) % p, k / 2);
}

signed main() {
  cin >> n >> p;
  string s; cin >> s;
  for (int i = 0; i < n; i++)
    a[i] = s[i] - '0';
  long long ans = 0;
  if (10 % p == 0) {
    for (int i = 0; i < n; i++)
      if (a[i] % p == 0)
        ans += i + 1;
    cout << ans;
    return 0;
  }
  for (int i = 0; i < p; i++)
    ls[i] = -1; 
  int din = bp(10, p - 2);
  int cp = 1;
  for (int i = 1; i < n; i++)
    cp = (cp * 10) % p;
  int cx = 0;
  for (int i = 0; i < n; i++)
    cx = (cx * 10 + a[i]) % p;
  for (int i = 0; i < n; i++) {
    int px = cx; ls[px] = i;
    cx = ((cx - cp * a[i]) % p + p) % p;
    if (ls[cx] > 0)
      dp[i] = dp[ls[cx] - 1] + 1;
    else if (ls[cx] == 0) 
      dp[i] = 1;
    ans += dp[i];
    cp = (cp * din) % p;
  }
  cout << ans;
  return 0;
}

Measured memory_bytes: 2948
#include<bits/stdc++.h>
#define N 100009
using namespace std;

int n,cnt,tot,fa[N],f[N],q[N],fst[N],pnt[N<<1],nxt[N<<1],dgr[N],a[N];
void add(int x,int y){
	pnt[++tot]=y; nxt[tot]=fst[x]; fst[x]=tot;
	dgr[y]++;
}
int dfs(int x){
	int i,y;
	for (i=fst[x]; i; i=nxt[i]){
		y=pnt[i];
		if (y!=fa[x]){
			fa[y]=x; dfs(y);
		}
	}
	for (i=fst[x],cnt=0; i; i=nxt[i]){
		y=pnt[i];
		if (y!=fa[x]) q[++cnt]=f[y];
	}
	if (!cnt) return f[x]=a[x];
	sort(q+1,q+cnt+1);
	int tmp=0;
	for (i=1; i<=cnt; i++) tmp+=q[i];
	if (tmp<a[x]){
		puts("NO"); exit(0);
	}
	tmp-=a[x];
	int res=0;
	for (i=1; i<cnt; i++) res+=q[i];
	if (res<tmp){
		puts("NO"); exit(0);
	}
	res+=q[cnt];
	if (res<(tmp<<1)){
		puts("NO"); exit(0);
	}
	return f[x]=a[x]-tmp;
}
int main(){
	scanf("%d",&n);
	int i,x,y;
	for (i=1; i<=n; i++) scanf("%d",&a[i]);
	if (n==2){
		puts(a[1]==a[2]?"YES":"NO"); return 0;
	}
	for (i=1; i<n; i++){
		scanf("%d%d",&x,&y);
		add(x,y); add(y,x);
	}
	for (i=1; i<=n; i++) if (dgr[i]>1){
		puts(dfs(i)?"NO":"YES"); break;
	}
	return 0;
}


Measured memory_bytes: 6400
#include <bits/stdc++.h>
using namespace std;
int main(){
  int n;
  cin>>n;
  vector<int> A(26,50);
  for(int i=0;i<n;i++){
    string S;
    cin>>S;
    vector<int> B(26,0);
    for(char c:S)
      B[c-'a']++;
    for(int i=0;i<26;i++)
      A[i]=min(A[i],B[i]);
  }
  for(int i=0;i<26;i++)
    for(int j=0;j<A[i];j++)
      cout<<(char)(i+'a');
  cout<<endl;
}

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

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

    int N = scanner.nextInt();
    long M = scanner.nextInt();
    long V = scanner.nextInt();
    int P = scanner.nextInt();
    int[] A = new int[N];
    for (int i = 0; i < N; i++) A[i] = scanner.nextInt();
    Arrays.sort(A);
    reverse(A);
    long[] cumsum = new long[N];
    for (int i = 1; i < N; i++) cumsum[i] = cumsum[i - 1] + A[i - 1];

    int res = P;
    for (int i = P; i < N && A[i] + M >= A[P - 1]; i++) {
      long cap = M * (N - i + P - 1);
      cap += (A[i] + M) * (i - P + 1) - cumsum[i] + cumsum[P - 1];
      if (cap >= M * V) res++;
    }
    System.out.println(res);
  }

  private static void reverse(int[] a) {
    int i = 0;
    int j = a.length - 1;
    while (i < j) {
      int tmp = a[i];
      a[i] = a[j];
      a[j] = tmp;
      i++;
      j--;
    }
  }
}


Measured memory_bytes: 52812
#include <iostream>
#include <string>
#include <sstream>
#include <iomanip> 
#include <math.h>
#include <stdio.h>
#include <string.h>
#include <queue>
#include <stack>
#include <vector>
#include <map>
#include <set>
#include <functional>
#include <algorithm>
#include <unordered_map>
#include <unordered_set>
#include <bitset>
#include <numeric>

using namespace std;


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

	long long n, w, i, j, k, ans;
	cin >> n >> w;
	vector<long long> ww(n), vv(n);
	for (i = 0; i < n; i++) cin >> ww[i] >> vv[i];

	vector<long long> dp(w + 1, 0);
	for (i = 0; i < n; i++) {
		for (j = w; j >= 0; j--) {
			if (j - ww[i] >= 0) dp[j] = max(dp[j], dp[j - ww[i]] + vv[i]);
		}
	}

	ans = *max_element(dp.begin(), dp.end());
	cout << ans << "\n";

	return 0;
}




Measured memory_bytes: 1024
#include<iostream>
using namespace std;
int main() {
	long long K;
	cin >> K;
	long long ans = 100; 
	long long y = 0;
	while (ans < K) {
		ans *= (1 + 0.01);
		y++;
	}
	cout << y << endl;
	return 0;
}

Measured memory_bytes: 3632
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cctype>
#include <climits>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstring>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <vector>
#define rep(i, n) for (int i = 0; i < (int)(n); ++i)
#define show(x) cout << #x << " = " << (x) << endl;
using namespace std;
using ll = long long;
using pii = pair<int,int>;
int nx[200005][26];
int dp[200005];
int dp2[200005];
int dfs(int x){
    if(dp[x]!=-1)return dp[x];
    vector<int>a;
    rep(i,26)a.push_back(dfs(nx[x][i])+1);
    int id = (int)(min_element(a.begin(),a.end())-a.begin());
    dp2[x] = id;
    return dp[x] = a[id];
}
int main(){
    string s;
    cin >> s;
    int a[26];
    s = "?" + s;
    int n = (int)s.size();
    rep(i,26)a[i] = n;
    rep(i,26)nx[n-1][i] = nx[n][i] = n;
    rep(i,n)dp[i] = -1;
    dp[n] = 0;
    for(int i = n-1; i >= 0; i--){
        rep(j,26)nx[i][j] = a[j];
        a[s[i]-'a'] = i;
    }
    dfs(0);
    string ans;
    int pos = 0;
    rep(i,dp[0]){
        ans += 'a'+dp2[pos];
        pos = nx[pos][dp2[pos]];
    }
    cout << ans << endl;
    
}

Measured memory_bytes: 23232
n,k = map(int, input().split())
A = list(map(int, input().split()))
F = list(map(int, input().split()))
A.sort()
F.sort(reverse=True)

def isOk(x):
    cost = 0
    for a, f in zip(A,F):
        eatable = x//f
        if eatable >= a:
            continue
        cost += a - eatable
    if cost <= k:
        return True
    return False

left = -1
right = A[-1] * F[0]
while left+1 < right:
    # mid = int(left + (right-left)//2)
    mid = (left+right)//2
    if isOk(mid):
        right = mid
    else:
        left = mid
print(right)

Measured memory_bytes: 34120
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i = 0, i##_len = (n); i < i##_len; ++i)
#define rep2(i, x, n) for(int i = x, i##_len = (n); i < i##_len; ++i)
#define all(n) begin(n), end(n)
using ll = long long;
using P = pair<ll, ll>;
using vi = vector<int>;
using vl = vector<ll>;
using vs = vector<string>;
using vc = vector<char>;
using vb = vector<bool>;
using vd = vector<double>;
vi dir = {-1, 0, 1, 0, -1, -1, 1, 1, -1};

int main() {
  ll a, b, c, k;
  cin >> a >> b >> c >> k;
  ll ans = 0;
  if(k <= a)
    ans = k;
  else if(k <= a + b)
    ans = a;
  else
    ans = a - (k - a - b);
  cout << ans << endl;
}

Measured memory_bytes: 3596
import math
import numpy as np
N,D = map(int,input().split())
X = np.array([list(map(int,input().split())) for n in range(N)])
ans = 0

for n in range(N):
  for m in range(N):
    d = 0
    for x,y in zip(X[n],X[m]):
      d += (x-y)**2
    if math.sqrt(d).is_integer() and d != 0:
      ans+=1
        
print(ans//2)

Measured memory_bytes: 26868
#include<iostream>
#include<numeric>
#include<string>
#include<vector>
#include<algorithm>
using namespace std;

int main(){ 
	int a,b,c,x; cin>>a>>b>>c;
	x=b-c;
	if(x>=0){
		cout<<"delicious"<<endl;
	}
	else if(a>=abs(x)){
		cout<<"safe"<<endl;
	}
	else{
		cout<<"dangerous"<<endl;
	}
}

Measured memory_bytes: 256
import heapq

N, M = map(int, input().split())
h = list(map(lambda x: -1 * int(x), input().split()))

heapq.heapify(h)

for _ in range(M):
    min_value = heapq.heappop(h)
    heapq.heappush(h, min_value / 2)

print(sum(map(lambda x: -1 * int(x), h)))


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

using namespace std;

#define ok1 printf("ok1\n");
#define ok2 printf("ok2\n");
#define M 1000000000000000000LL
#define rep(i,n) for(int i=0;i<n;i++)
#define REP(i,s,n)　for(int i=(s);i<(n);i++)
#define repr(i,n) for(int i=n-1;i>=0;i--)
#define REPR(i,s,n) for(int i=(s);i>=(n);i--)
#define all(a) (a).begin(),(a).end()
#define rall(a) (a).rbegin(),(a).rend()
#define pb push_back
#define pf push_front
#define MIN(a,b) a=min((a),(b))
#define MAX(a,b) a=max((a),(b))
#define SIZE(v) (int)v.size()
#define Eunique(v) v.erace(unique(all(v)),v.end())
#define pvec(v)　rep(i,v.size()){cout << v[i] << " ";}
#define INF 0x3f3f3f3f
#define mset(m,v) memset(m,v,sezeof(m))
#define mod 1e9 +7;

const double pi = acos(-1.0);

typedef string ss;
typedef vector<int> vi;
typedef vector<string> vs;
typedef long long ll;
typedef vector<ll> vll;
typedef vector<vi> vvi;
typedef vector<vll> vvll;
typedef deque<ll> dll;
typedef pair<ll,ll> P;
ll dx[4] = {1,0,-1,0},dy[4] = {0,1,0,-1};

ll gcd(ll x,ll y)
{
    ll r;
    while((r = x % y) != 0)
    {
        x = y;
        y = r;
    }
    return y;
}

ll lcm(ll x,ll y)
{
    x /= gcd(x,y);
    y /= gcd(x,y);
    return (x*y);
}

int main()
{
    ll x,a,b;
    cin >> x >> a >>b;
    x -= a;
    while(x>=0)x-=b;
    cout << x+b << endl;
    return 0;
}

Measured memory_bytes: 256
s = input()
a=s[0:2]
b=s[2:4]
if a =="00" or int(a)>12:
  if b=="01" or b=="02"or b=="03"or b=="04" or b=="05" or b=="06" or b=="07" or b=="08" or b=="09" or b=="10" or b=="11" or b=="12":
    print("YYMM")
  else:
    print("NA")
elif a=="01" or a=="02"or a=="03"or a=="04" or a=="05" or a=="06" or a=="07" or a=="08" or a=="09" or a=="10" or a=="11" or a=="12":
  if b=="01" or b=="02"or b=="03"or b=="04" or b=="05" or b=="06" or b=="07" or b=="08" or b=="09" or b=="10" or b=="11" or b=="12":
    print("AMBIGUOUS")
  else:
    print("MMYY")


Measured memory_bytes: 3064
#include  <bits/stdc++.h>
using namespace std;
static int fast_io = []() { std::ios::sync_with_stdio(false); cin.tie(nullptr); return 0; }();

int main(){
  int x;
  cin>>x;
  int ans=0;
  int amount =x/500;
  int rest = x%500;
  ans+=1000*amount;
  amount =  rest/5;
  ans+=5*amount;
  cout<<ans<<"\n";  
  return 0;
}

Measured memory_bytes: 256
/********************************
*** ******** ********** *********
*** * ****** ********* * ********
*** ** ***** ******** *** *******
*** *** **** ******* ***** ******
*** **** *** ****** ******* *****
*** ***** ** ***** +++++++++ ****
*** ****** * **** *********** ***
*** *******  *** ************* **
*** ******** ** *************** *
**********_**********************
* |   /  / \  \     /    /\     *
* |  /  |   |  \   /    /  \    *
* | /   |   |   \ /    /    \   *
* |+\   |   |    |    /______\  *
* |  \  |   |    |   |        | *
* |   \  \_/     |   |        | *
********************************/
#include<bits/stdc++.h>
#define lli long long int
#define MOD 1000000007
#define KING 1000000002
#define queen 1000002
#define fi first
#define se second
#define se second
#define lsb(i) (i & -i)
#define Pi 3.141592653589793238
#define nl cout<<'\n'
#define TEST cout<<"TEST",nl
#define all(a) a.begin(), a.end()
#define remax(a, b) (a = ((a<b) ? b : a))
#define remin(a, b) (a = ((a<b) ? a : b))
#define pr pair<lli,lli>
#define pb push_back
#define eb emplace_back
#define precise(a) cout<<fixed<<setprecision(a)
#define mp make_pair
#define vi vector<lli>
#define vpi vector<pr> 
#define P pair<lli,pr>
#define fastIO ios_base::sync_with_stdio(false); cin.tie(NULL)
#define NA(i,s,n) for(lli i=s;i<n;i++)
using namespace std;

lli power(lli x,lli y,lli p) { 
	lli res = 1;	 
	x = x % p; 
	while (y > 0) 
	{ 
		if (y & 1) 
			res = (res*x) % p; 
		y = y>>1; 
		x = (x*x) % p; 
	} 
	return res; 
} 

void solve(){
    lli n, w, sm_val = 0;
    cin >> n >> w;
    vi val(n), wg(n);
    NA(i,0,n) cin >> wg[i] >> val[i], sm_val += val[i];
    vi dp(sm_val + 1, 1e15);
    dp[0] = 0;
    NA(i,0,n){
        for(lli j=sm_val; j>-1; --j){
            if(j+val[i] <= sm_val)
                remin(dp[j+val[i]], dp[j] + wg[i]);
        }
    }
    lli ans = 0;
    for(lli i=sm_val; i>-1; --i) {
        if(dp[i] <= w){
            ans = i;
            break;
        }
    }
    cout << ans ;
    return;
}
int main(){
    fastIO;
    lli t = 1;
    // cin>>t;
    NA(i,0,t){
        solve();
    }
    return 0;

}


Measured memory_bytes: 1024
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define mp make_pair
#define mt make_tuple
#define min_3(a,b,c) min(a,min(b,c))
#define max_3(a,b,c) max(a,max(b,c))
#define nout(ans) cout << (ans) << "\n"
#define sout(ans) cout << (ans) << " "
using namespace std;

const double pi = 3.14159265359;
const ll INF = 1e12;
const ll MOD = 1e9 + 7;
const ll N = 1e5+5; 
/*
Decimal Places: cout << fixed << setprecision(n) << ans << endl
*/

bool compare(const pair<int, int>&i, const pair<int, int>&j)
{
    return i.second < j.second;
}

ll raise(ll a, ll b) {
    ll res = 1;
    while (b > 0) {
        if (b & 1)
            res = res * a;
        a = a * a;
        b >>= 1;
    }
    return res;
}


ll n, ans=0;

void solve()
{
    cin >> n;
    if (n==1) {
        nout(0); return;
    }
    ll k=1, l=1, r=1;
    for (int i=1; i<=n; ++i) k = (k*10)%MOD;
    for (int i=1; i<=n; ++i) l = (l*9)%MOD;
    for (int i=1; i<=n; ++i) r = (r*8)%MOD;
    ans = (k+r-(2*l)%MOD);
    nout((ans+MOD)%MOD);
    
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    int t = 1;
    //cin >> t;
    for (int i=1; i<=t; i++)
    {
        solve();
    }
    return 0;
}

Measured memory_bytes: 3564
#include <iostream>
#include <complex>
#include <vector>
#include <cmath>
using namespace std;
typedef complex<double> C;
#define EPS (1e-10)
#define EQ(a,b) (abs(a-b) < EPS)
#define EQV(a,b) (EQ(a.real(), b.real()) && EQ(a.imag(), b.imag()))
int n;
C s[101], e[101];
double cross(C a, C b) {
  return a.real() * b.imag() - a.imag() * b.real();
}

C intersection(C a1, C a2, C b1, C b2) {
  C b = b2 - b1;
  double d1 = abs(cross(b, a1 - b1));
  double d2 = abs(cross(b, a2 - b1));
  double t = d1 / (d1 + d2);
  return a1 + (a2 - a1) * t;
}

void solve() {
  for(int i=0;i<n;i++)
  cin>>s[i].real()>>s[i].imag()>>e[i].real()>>e[i].imag();
  
  int res = 1;
  for (int i = 0; i < n; i += 1) {
    vector<C> iss;
    for (int j = 0; j < i; j += 1) {
      C ii = e[i] - s[i];
      C jj = e[j] - s[j];
      // üªª½s©
      if (abs(cross(ii, jj)) < EPS) continue;
      // ð_ðßé
      //C is = intersection(s[i], e[i], s[j], e[j]);
      C is = s[i] + ii * cross(jj, s[j]-s[i]) / cross(jj, ii);
      // ð_ÌÀWªÍÍO©
      if (abs(is.real()) + EPS > 100.0) continue;
      if (abs(is.imag()) + EPS > 100.0) continue;
      // ùÉ¶ÝµÄ¢éð_©mF
      bool exist_flag = false;
      for (int i = 0; i < iss.size(); i += 1) {
        if (EQV(is, iss[i])) {
          exist_flag = true;
          break;
        }
      }
      // ¶ÝµÄ¢È©Á½ÌÅÇÁ
      if (!exist_flag) {
        iss.push_back(is);
      }
    }
    // ð_Ì + 1Ì¾¯ªðâ·
    res += iss.size() + 1;
  }
  cout<<res<<endl;
}

int main (int argc, char const* argv[]) {
  while (cin>>n, n) {
    solve();
  }
  return 0;
}

Measured memory_bytes: 964
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define inf 1e9+5
using namespace std;

int32_t main(){
      ios_base::sync_with_stdio(false);
    cin.tie(NULL);
  ll n,k;
  cin>>n>>k;
  vector<int> a(n);
  for(int i=0;i<n;i++)cin>>a[i];
   vector<int> dp(n,inf);
  dp[0]=0;
  for(int i=0;i<n;i++){
     for(int j=i+1;j<=i+k;j++){
         if(j<n){
             dp[j]=min(dp[j],dp[i]+abs(a[j]-a[i]));
         }
     }
  }
  cout<<dp[n-1];
}



Measured memory_bytes: 1152
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
using namespace std;

typedef long long ll;
vector<int> vec[203];
int maxdep,flag,e[203][203], n, in[203], dep[203], vis[203];

void bfs(int x) {
    memset(vis, 0, sizeof(vis));
    memset(dep, 0, sizeof(dep));
    queue<int> q;
    q.push(x);
    dep[x] = 1;
    while(!q.empty()) {
        int u = q.front();
        q.pop();
        vis[u] = 1;
        for (int i = 0; i < vec[u].size(); i++) {
            int v = vec[u][i];
            //cout << u << " " << v << " " << vis[v] << " " << dep[v] <<" " << dep[u] << endl;
            if (vis[v]) continue;
            if (dep[v] == 0) {
                dep[v] = dep[u] + 1;
                maxdep = max(maxdep, dep[v]);
                q.push(v);
            }else if(dep[v] != dep[u] + 1) {
                flag = 1;
                return;
            }
        }
    }
}
int main() {
    //freopen("test.in","r",stdin);
    //freopen("test.out","w",stdout);
    cin >> n;
    string s;
    for (int i = 1; i <= n; i++) {
        cin >> s;
        for (int j = 0; j < n; j++) {
            if (s[j] == '1') {
                vec[i].push_back(j + 1);
                vec[j + 1].push_back(i);
                in[i]++;
                in[j + 1]++;
            }
        }
    }
    for (int i = 1; i <= n; i++) {
        bfs(i);
        if (flag) break;
    }
    if (flag) cout << -1 << endl;
    else
        cout << maxdep << endl;
}

Measured memory_bytes: 640
use std::io;
use std::collections::HashMap;
use std::collections::BinaryHeap;
use std::mem;
use std::cmp;


fn read_line() -> String{
    let mut s = String::new();
    io::stdin().read_line(&mut s).unwrap();
    s.trim().to_string()
}

fn read_ints() -> Vec<i64>{
    let s = read_line();
    let split:Vec<&str> = s.split(" ").collect();
    split.iter().map(|&x| x.to_string().parse().unwrap()).collect()
}


fn main(){
    let s = read_line();
    let n = s.chars().filter(|c| *c == '1').count();
    println!("{}",n);
}



/*
DOCS


let mut h = HashMap::new();
let a = 5;
h.insert(a,true);
match h.get(&a){
    Some(v) => println!("{}",v),
    None    => println!("none"),
}


use std::mem;

let mut x = 5;
let mut y = 1;
mem::swap(&mut x,&mut y);


let v = vec![0;2]; // [0,0]

s.chars().nth(i as usize).unwrap();


// priority queue
// https://doc.rust-lang.org/std/collections/struct.BinaryHeap.html
use std::collections::BinaryHeap;
let mut heap = BinaryHeap::new();

heap.push(1);
heap.push(5);
heap.push(2);

assert_eq!(heap.pop(), Some(5));
assert_eq!(heap.pop(), Some(2));
assert_eq!(heap.pop(), Some(1));
assert_eq!(heap.pop(), None);


let mut vs = heap.into_vec();
vs.reverse();



*/


Measured memory_bytes: 4352
#pragma GCC optimize("O3")
#pragma GCC target("avx")
#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>(int)(n);--i)
#define rep1(i ,n) for(int i=1;i<=(int)(n);++i)
#define ALL(a) a.begin(), a.end()
#define RSORT(a) sort(ALL(a),greater<>())
#define SORT(a) sort(ALL(a))
#define bit_check(bit, i) ((bit>>(i)) & 1)
#define PRINT(x) printf("%d\n",(x));
#define ENDL printf("\n");
using namespace std;
typedef long long int i64;
typedef unsigned long long u64;
template<class T> using V = vector<T>;
using VI = V<int>;
const int INF = 2e9;
const i64 MOD = 1e9 + 7;

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;}

signed main(){
    int r ; cin >> r;
    double PI = acos(-1);
    cout << fixed << 2 * PI * (double)r << endl;
}

Measured memory_bytes: 3808
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp> 
using namespace __gnu_pbds;
using namespace std;
typedef tree<pair<int,int>,null_type,less<pair<int,int>>,rb_tree_tag,tree_order_statistics_node_update> oset;
#define sim template < class c
#define ris return * this
#define dor > debug & operator <<
#define eni(x) sim > typename \
  enable_if<sizeof dud<c>(0) x 1, debug&>::type operator<<(c i) {
sim > struct rge { c b, e; };
sim > rge<c> range(c i, c j) { return rge<c>{i, j}; }
sim > auto dud(c* x) -> decltype(cerr << *x, 0);
sim > char dud(...);
struct debug {
#ifdef LOCAL
~debug() { cerr << endl; }
eni(!=) cerr << boolalpha << i; ris; }
eni(==) ris << range(begin(i), end(i)); }
sim, class b dor(pair < b, c > d) {
  ris << "(" << d.first << ", " << d.second << ")";
}
sim dor(rge<c> d) {
  *this << "[";
  for (auto it = d.b; it != d.e; ++it)
	*this << ", " + 2 * (it == d.b) << *it;
  ris << "]";
}
#else
sim dor(const c&) { ris; }
#endif
};
#define imie(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "
using ll = long long;
#define ar array 
#define int ll
void test_case() {
	ll x , k , d;
	cin >> x >> k >> d;
	x = abs(x);
	int r = x/d;
	if(r >= k){
		x -= k * d;
		cout << x ;
	}
	else{
		x -= r*d;
		k -= r;
		if(k%2 == 0){
			cout << x;
		}
		else{
			cout << abs(x - d);
		}
	}
}
 
int32_t main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int T = 1;
	//~ cin >> T;
	while(T--){
		test_case();
	}
}


Measured memory_bytes: 3648