akhauriyash/Code-Regression huggingface dataset:
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
#define MOD (1000000007)

long long inv(long long a) {
	if (a == 0) return 1;
    long long b = MOD, u = 1, v = 0;
    while (b) {
        long long t = a / b;
        a -= t * b; swap(a, b);
        u -= t * v; swap(u, v);
    }
    u %= MOD; 
    if (u < 0) u += MOD;
    return u;
}


int main()
{
	cin.tie(0);
	ios::sync_with_stdio(false);
	int n, tmp, m;
	cin >> n;
	vector<int> a(n+1);
	for (int i = 1; i <=n+1; ++i) {
		cin >> tmp;
		if (a[tmp] > 0) {
			m = i - a[tmp]-1;
		}
		else {
			a[tmp] = i;
		}
	}
	cout << n << endl;
	long long all = n+1, dbl = 1, ans;
	for(int i=2;i<=n+1;++i){
		all *= (n + 2 - i);
		all %= MOD;
		all *= inv(i);
		all %= MOD;
		dbl *= (n +1- m - i);
		dbl %= MOD;
		dbl *= inv(i - 1);
		dbl %= MOD;
		ans = (all - dbl + MOD) % MOD;
		cout << ans << endl;
	}

}

Measured memory_bytes: 1664
Suits = ['S', 'H', 'C', 'D']
Taro = []
Missing = []
n = int(input())
for i in range(n):
    Taro.append(input())
for j in range(52):
    card = Suits[j//13] + ' ' + str(j % 13 + 1)
    if card not in Taro:
        Missing.append(card)
if Missing != []:
    print('\n'.join(Missing))

Measured memory_bytes: 7652
#include <iostream>
#include <vector>
#include <queue>
using namespace std;

typedef long long ll;

const int MOD=1e9+7;

struct modint {
    int val;
    modint inv() const{
        int tmp,a=val,b=MOD,x=1,y=0;
        while(b)tmp=a/b,a-=tmp*b,swap(a,b),x-=tmp*y,swap(x,y);
        return modint(x);
    }
public:
    modint():val(0){}
    modint(ll x){if((val=x%MOD)<0)val+=MOD;}
    modint pow(ll t){modint res=1,b=*this; while(t){if(t&1)res*=b;b*=b;t>>=1;}return res;}
    modint& operator+=(const modint& x){if((val+=x.val)>=MOD)val-=MOD;return *this;}
    modint& operator-=(const modint& x){if((val+=MOD-x.val)>=MOD)val-=MOD; return *this;}
    modint& operator*=(const modint& x){val=(ll)val*x.val%MOD; return *this;}
    modint& operator/=(const modint& x){return *this*=x.inv();}
    bool operator==(const modint& x) const{return val==x.val;}
    bool operator!=(const modint& x) const{return val!=x.val;}
    bool operator<(const modint& x) const{return val<x.val;}
    bool operator<=(const modint& x) const{return val<=x.val;}
    bool operator>(const modint& x) const{return val>x.val;}
    bool operator>=(const modint& x) const{return val>=x.val;}
    modint operator+(const modint& x) const{return modint(*this)+=x;}
    modint operator-(const modint& x) const{return modint(*this)-=x;}
    modint operator*(const modint& x) const{return modint(*this)*=x;}
    modint operator/(const modint& x) const{return modint(*this)/=x;}
};

int main() {
  ll n;
  cin >> n;
  vector<ll> la(n);
  for (ll &a: la) cin >> a;
  modint ans(0);
  for (ll d = 0; d < 60; ++d) {
    ll n1 = 0;
    ll mask = ((ll)1<<d);
    for (int i = 0; i < n; ++i) {
      if (la[i] & mask) {
        // cout << la[i] << " " << mask << endl;
        ++n1;
      }
    }
    modint tmp(n1*(n-n1));
    tmp *= mask;
    ans += tmp;
  }
  cout << ans.val << endl;
}



Measured memory_bytes: 2688
<?php /*atcoder.php*/

$at = new Atcoder();
$at->main();
unset($at);

class Atcoder{
	private function arrayIn(){
		$buf = explode(" ", fgets(STDIN));
		return $this->killNewLine($buf);
	}
	private function killNewLine($buf = null){
		$buf = str_replace("\r\n", "", $buf);
		$buf = str_replace("\n", "", $buf);
		$buf = str_replace("\r", "", $buf);
		return $buf;
	}

	public function main(){
		$s = $this->arrayIn();

		$ans = abs($s[0] - $s[1]) + 1;

		echo $ans . "\n";

	}
}
?>


Measured memory_bytes: 4728
# -*- coding: utf-8 -*-
import sys
import math
import os
import itertools
import string
import heapq
import _collections
from collections import Counter
from collections import defaultdict
from functools import lru_cache
import bisect
import re
import queue
from decimal import *


class Scanner():
    @staticmethod
    def int():
        return int(sys.stdin.readline().rstrip())

    @staticmethod
    def string():
        return sys.stdin.readline().rstrip()

    @staticmethod
    def map_int():
        return [int(x) for x in Scanner.string().split()]

    @staticmethod
    def string_list(n):
        return [Scanner.string() for i in range(n)]

    @staticmethod
    def int_list_list(n):
        return [Scanner.map_int() for i in range(n)]

    @staticmethod
    def int_cols_list(n):
        return [Scanner.int() for i in range(n)]


class Math():
    @staticmethod
    def gcd(a, b):
        if b == 0:
            return a
        return Math.gcd(b, a % b)

    @staticmethod
    def lcm(a, b):
        return (a * b) // Math.gcd(a, b)

    @staticmethod
    def divisor(n):
        res = []
        i = 1
        for i in range(1, int(n ** 0.5) + 1):
            if n % i == 0:
                res.append(i)
                if i != n // i:
                    res.append(n // i)
        return res

    @staticmethod
    def round_up(a, b):
        return -(-a // b)

    @staticmethod
    def is_prime(n):
        if n < 2:
            return False
        if n == 2:
            return True
        if n % 2 == 0:
            return False
        d = int(n ** 0.5) + 1
        for i in range(3, d + 1, 2):
            if n % i == 0:
                return False
        return True


def pop_count(x):
    x = x - ((x >> 1) & 0x5555555555555555)
    x = (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333)
    x = (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f
    x = x + (x >> 8)
    x = x + (x >> 16)
    x = x + (x >> 32)
    return x & 0x0000007f


MOD = int(1e09) + 7
INF = int(1e15)


def solve():
    S = Scanner.string()
    T = Scanner.string()
    if S == T[0:-1]:
        print('Yes')
    else:
        print('No')


def main():
    # sys.stdin = open("sample.txt")
    solve()


if __name__ == "__main__":
    main()


Measured memory_bytes: 10600
import java.util.Scanner;

class Main{
	public static void main(String[] args){
		
		Scanner sc = new Scanner(System.in);
		int a = sc.nextInt();
		int b = sc.nextInt();
		int c = sc.nextInt();
		if(a<b && b<c){
			System.out.println("Yes");
		}else{
			System.out.println("No");
		}
	}
}


Measured memory_bytes: 26240
#include<bits/stdc++.h>
using namespace std;
 
#define ll          long long int
#define ld          long double
#define pb          push_back
#define mp          make_pair
#define ff          first
#define se          second
#define endl        '\n'
#define fd(n)       fixed<<setprecision(n)
#define MAX         100000000000000000
#define MAXN        1000005
#define mod         1000000007  
#define pi          3.1415926535897932384626433
 
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    string s;
    cin>>s;
    ll n=s.size();
    if(s[n-1]=='s'){
        cout<<s<<"es";
    }
    else{
        cout<<s<<"s";
    }
}

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

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

long long MOD = 10000000000 + 7;

int main(){
  cout << setprecision(10);
  int N;
  cin >> N;
  map<pair<int,int>, ll> m; // 距離
  vector<vector<int>> v(N); // 隣接リスト

  vector<int> color(N, -1);

  for(int i = 0; i < N-1; i++){
    int x,y;
    ll w;
    cin >> x >> y >> w;
    x--; y--;
    m[make_pair(x,y)] = w;
    m[make_pair(y,x)] = w;
    v.at(x).push_back(y);
    v.at(y).push_back(x);
  }

  // 幅優先探索　距離が偶数なら同じ色、奇数なら違う色
  queue<int> q;
  q.push(0);
  color[0] = 0;

  while(!q.empty()){
    int now = q.front();
    q.pop();

    for(auto next: v.at(now)){
      if(color.at(next) == -1){
        if(m[make_pair(now, next)] %2 == 0){
          color[next] = color[now];
        } else {
          color[next] = color[now] + 1;
        }
        q.push(next);
      } else { 
        continue;
      }
    }
  }

  for(auto x: color){
    cout << x%2 << endl;
  }

}


Measured memory_bytes: 18816
#include<stdio.h>
 
int a[1000000],n;
int binarysearch(int key){
    int left = 0;
    int right = n;
    int mid;
    while(left<right){
        mid = (left + right)/2;
        if( key == a[mid] )return 1;
        if( key > a[mid] )left = mid+1;
        else if( key < a[mid] )right = mid;
    }
    return 0;
}
     
    int main(){
        int i,q,k,sum = 0;
          
        scanf("%d",&n);
        for(i=0;i<n;i++){
            scanf("%d",&a[i]);
        }
        scanf("%d",&q);
        for(i=0;i<q;i++){
            scanf("%d",&k);
            if(binarysearch(k))sum++;
        }
        printf("%d\n",sum);
        return 0;
    }

Measured memory_bytes: 980
#include<bits/stdc++.h>
using namespace std;
#define ll long long
int n,m,a,b;
char s[100005],t[100005];
int gcd(int a,int b){if(b)return gcd(b,a%b);return a;}
int main(){
    scanf("%d%d%s%s",&n,&m,s,t);
    int g=gcd(n,m);
    a=n/g,b=m/g;
    for(int i=0,j=0;i<n&&j<m;i+=a,j+=b)if(s[i]!=t[j]){printf("-1");return 0;};
    printf("%lld",(ll)n/g*m);
    return 0;
}

Measured memory_bytes: 512
#include <stdio.h>
#include <cmath>
#include <algorithm>
#include <cfloat>
#include <stack>
#include <queue>
#include <vector>
#include <string>
#include <iostream>
#include <set>
#include <map>
#include <time.h>
typedef long long int ll;
typedef unsigned long long int ull;
#define BIG_NUM 2000000000
#define MOD 1000000007
#define EPS 0.000000001
using namespace std;



int main(){

	int N;
	vector<int> V;

	scanf("%d",&N);

	int num_0 = 0,num_1 = 0;

	int tmp;
	for(int loop = 0; loop < N; loop++){
		scanf("%d",&tmp);
		if(tmp == 0){
			num_0++;
		}else if(tmp == 1){
			num_1++;
		}else{
			V.push_back(tmp);
		}
	}

	sort(V.begin(),V.end());

	int size = (int)V.size();

	if(num_0%2 == 0){
		if(size >= 2 && V[size-2] == 2 && V[size-1] == 3){
			swap(V[size-2],V[size-1]);
		}

		for(int i = 0; i < size; i++){
			printf("%d\n",V[i]);
		}
		for(int i = 0; i < num_0; i++){
			printf("0\n");
		}
		for(int i = 0; i < num_1; i++){
			printf("1\n");
		}
	}else{

		if(num_1 > 0){

			if(size >= 2 && V[size-2] == 2 && V[size-1] == 3){
				swap(V[size-2],V[size-1]);
			}
			for(int i = 0; i < size; i++){
				printf("%d\n",V[i]);
			}
			for(int i = 0; i < num_0-1; i++){
				printf("0\n");
			}
			printf("1\n0\n");
			for(int i = 0; i < num_1-1; i++){
				printf("1\n");
			}
		}else{

			if(size > 0){
				tmp = V[0];
				V.erase(V.begin()+0);

				size--;

				if(size >= 2 && V[size-2] == 2 && V[size-1] == 3){
					swap(V[size-2],V[size-1]);
				}

				for(int i = 0; i < size; i++){
					printf("%d\n",V[i]);
				}

				for(int i = 0; i < num_0-1; i++){
					printf("0\n");
				}
				printf("%d\n0\n",tmp);

			}else{

				for(int i = 0; i < num_0; i++){
					printf("0\n");
				}
			}
		}
	}

	return 0;
}



Measured memory_bytes: 3236
#include<iostream>
#include<vector>
#include<string>
#include<cmath>
#include<algorithm>
#include<functional>
#include<numeric>
#include<queue>
#include<stack>
#include<map>
#include<unordered_map>
#include<set>
#include<bitset>
#include<random>

#pragma region
using namespace std;
#define FOR(i,r,n) for(ll i = (ll)(r); i < (ll)(n); i++)
#define rep(i,n) FOR(i,0LL,n)
#define RFOR(i,r,n) for(ll i=(ll)(n-1);i>=r;i--)
#define rrep(i,n) RFOR(i,0LL,n)
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define COUNT(a,y,x) upper_bound(all(a), y) - lower_bound(all(a), x)
#define UNIQUE(a) sort(all(a)); a.erase(unique(all(a)), a.end())
#define pb push_back
typedef long long int ll;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef pair<ll, ll> pll;
typedef vector<pll> vpll;
typedef vector<string> vs;
typedef map<ll, ll> MAP;
const ll inf = 2222222222222222222LL;
const ll mod = 1000000007LL;

ll n = 0, m = 0, ans = 0, tmp = 0, ma = -inf, mi = inf;
string s;
bool ok;
ll dx[9] = { 0,1,-1,0,0,1,1,-1,-1 }, dy[9] = { 0,0,0,1,-1,1,-1,1,-1 };
#define endl '\n'
#pragma endregion
#define MAX 222222


ll a[33][33], b[33];


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


  ll c;
  cin >> n >> m >> c;
  rep(i, m) cin >> b[i];
  rep(i, n) rep(j, m) cin >> a[i][j];
  rep(i, n) {
    ll sum = 0;
    rep(j, m) sum += a[i][j] * b[j];
    if (sum + c > 0) ans++;
  }
  cout << ans << endl;



  return 0;
}

Measured memory_bytes: 256
import java.util.Scanner;
public class Main {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		try (Scanner sc = new Scanner(System.in)) {
			int w = sc.nextInt();
			int n = sc.nextInt();
			int[] values = new int[w];
			for (int i = 0; i < values.length; i++) {
				values[i] = i + 1;
			}
			for (int i = 0; i < n; i++) {
				String str = sc.next();
				String[] ab = str.split(",");
				int a = Integer.parseInt(ab[0]) - 1;
				int b = Integer.parseInt(ab[1]) - 1;
				int cp = values[a];
				values[a] = values[b];
				values[b] = cp;
			}
			for (int i = 0; i < values.length; i++) {
				System.out.println(values[i]);
			}
		}
	}

}


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

using namespace std;
using ll = long long;

template <typename K,typename V>
using umap = unordered_map<K,V>;
template <typename V>
using uset = unordered_set<V>;
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; }
#define REP(i,n) for(int i=0;i<n;i++)
#define REPD(i,n) for(int i=n-1;i>=0;i--)
#define FOR(i,a,b) for(int i=a;i<b;i++)
#define FORD(i,a,b) for(int i=a;i>=b;i--)
#define ALL(v) v.begin(),v.end()

#define endl "\n"
#define INF 1'000'000'000'000 //10^12
//#define MOD 1'000'000'007
#define MOD 998'244'353
struct mod_util {
  vector<long long> fac,finv,inv;
  int mod = -1;
  void init(int n , int mod){
    fac.resize(n);
    finv.resize(n);
    inv.resize(n);
    this->mod = mod;
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[0] = 0;
    inv[1] = 1;
    for(int i=2;i<n;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;
    }
  }

  long long nCk(int n, int k){
      assert(mod != -1);

      if(n < k)return 0;
      if(n < 0 || k < 0)return 0;

      return fac[n] * (finv[n-k] * finv[k] % mod) % mod;
  }

  long long nPk(int n, int k){
    assert(mod != -1);

    if(n < k)return 0;
    if(n < 0 || k < 0)return 0;

    return fac[n] * finv[n-k] % mod;
  }

  // a^x を modで割った余り
  int pow_mod(int a , int x , int mod){
    long long res = 1;
    long long pow = a;
    while(x > 0){
      if(x & 1){
        res *= pow;
        res %= mod;
      }

      pow *= pow;
      pow %= mod;
      x >>= 1;
    }
    return (int)res;
  }
};

int main(){
  cin.tie(nullptr);
  ios_base::sync_with_stdio(false);
  cout << fixed << setprecision(15);

  int n;
  cin >> n;
  int dist_cnt[n] = {0};
  int d[n];
  int max = 0;
  REP(i,n){
    cin >> d[i] ;
    dist_cnt[d[i]]++;
    chmax(max,d[i]);
  }
  mod_util mu;
  if(dist_cnt[0]==1 && d[0] == 0){
    ll res = 1;
    ll prev_branch = 1;
    REP(i,max+1){
      res *= mu.pow_mod(prev_branch,dist_cnt[i],MOD);
      res %= MOD;
      prev_branch = dist_cnt[i];
    }

    cout << res << endl;
  }else{
    cout << 0 << endl;
  }

  return 0;
}


Measured memory_bytes: 4436
#define _CRT_SECURE_NO_WARNINGS
#include <cstdio>
#include <algorithm>
#include <queue>
#include <functional>
#define repi(i,a,b) for(int i=(a);i<(b);++i)
#define rep(i,a) repi(i,0,a)

constexpr int MAX_N = 100000;

using ll = long long;

ll N;
ll a[3*MAX_N];
ll S[3*MAX_N + 1], S2[3*MAX_N + 1];

int main()
{
	scanf("%lld", &N);
	rep(i, 3*N)
		scanf("%lld", a + i);

	std::priority_queue<ll, std::vector<ll>, std::greater<ll> > pque;
	S[0] = a[0];
	rep(i, N)
		pque.push( a[i] ), S[i+1] = S[i]+a[i+1];

	repi(k, N, 2 * N)
	{
		S[k] = S[k - 1];

		ll p = pque.top();
		if (a[k] > p)
		{
			S[k] -= p;
			pque.pop();
			pque.push(a[k]);
			S[k] += a[k];
		}
	}

	std::priority_queue<ll> pque2;
	S2[3*N-1] = a[3*N-1];
	for( int i = 3*N-1; i >= 2*N; --i )
		pque2.push(a[i]), S2[i-1] = S2[i] + a[i-1];

	for( int k = 2*N-1; k >= N; --k )
	{
		S2[k] = S2[k + 1];

		ll p = pque2.top();
		if (a[k] < p)
		{
			S2[k] -= p;
			pque2.pop();
			pque2.push(a[k]);
			S2[k] += a[k];
		}
	}

	ll ans = -1e18;
	repi(k, N, 2 * N+1)
		ans = std::max(ans, S[k-1] - S2[k]);

	printf("%lld\n", ans);

	return 0;
}

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

int main()
{
    /*A
    int a[32]={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};
    int k;
    cin>>k;
    cout<<a[k-1]<<endl;
    */
    /*B
    ll h,w;
    cin>>h>>w;
    ll countOdd;
    if(w%2==0)
    {
        countOdd=w/2;
    }
    else
    {
        countOdd = w/2+1;
    }
    ll countEven =w-countOdd;
    ll count;
    if(w==1 || h==1)
    {
        cout<<1<<endl;
        return 0;
    }
    if(h%2==0)
    {
        count = (countEven+countOdd)*(h/2);
    }
    else
    {
        count = (countEven+countOdd)*(h/2)+countOdd;
    }

    cout<<count<<endl;
    */

    long long a,b,c;
    cin>>a>>b>>c;
    if(b>c || a>c)
    {
        cout<<"No"<<endl;
        return 0;
    }
    if((c-(a+b))*(c-(a+b))-4*a*b>0)
    {
        cout<<"Yes"<<endl;
    }
    else
    {
        cout<<"No"<<endl;
    }
    
    return 0;
}

Measured memory_bytes: 256
import sys,collections,math,random;sys.setrecursionlimit(10**7)
def Is(): return [int(x) for x in sys.stdin.readline().split()]
def Ss(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def S(): return input()

n,m = Is()
a = Is()
d = collections.defaultdict(int)
for e in a:
    d[e] += 1
for i in range(m):
    b,c = Is()
    d[c] += b
a = sorted(d.items(),reverse=True)
ans = 0
for e,f in a:
    if n <= f:
        ans += e*n
        break
    else:
        n -= f
    ans += e*f
print(ans)
    
    

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

#define pb                     push_back
#define ll                     long long
#define forn(i,n)              for(int i=0; i<(int)n; i++)
#define forn1(i,n)              for(int i=1; i<=(int)n; i++)

#define sfd(a)                 scanf("%d", &a)
#define sffd(a,b)              scanf("%d%d", &a, &b)
#define sffl(a,b)              scanf("%lld%lld", &a,&b)
#define sfl(a)                 scanf("%lld", &a)

#define pii                    pair<int , int>
#define pll                    pair<ll , ll>
#define ff                     first
#define ss                     second
#define mem(a, val)            memset(a, val, sizeof(a))
#define all(x)                 (x).begin(), (x).end()

//#define mx                     200005
#define INF_mx                 1e18
#define gcd(a,b)               __gcd(a, b)
#define lcm(a,b)               (a*b)/__gcd(a,b)
#define PRINT                  cout<<"hi"<<endl
#define PI acos(-1)
#define fast_in_out          ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define Q    int q; cin>>q; while(q--)
/*
tree<
       int,
     null_type,
     less<int>,
     rb_tree_tag,
     tree_order_statistics_node_update>t;
*/

int main()
{
  int n;
  cin>>n;
  ll ans=0;
  for(int i=1; i<=n; i++){
     if(i%3 && i%5){
        ans+=i;
    }
  }
  cout<<ans<<endl;
    return 0;
}
/*
1
21 7
wudixiaoxingxingheclp
*/


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

int main() {
  int n, sum = 0;
  cin >> n;
  int a[n], b[n], c[n];
  REP(i, n) cin >> a[i];
  REP(i, n) cin >> b[i];
  REP(i, n - 1) cin >> c[i];

  REP(i, n) {
    sum += b[a[i] - 1];
    if (i != 0 && a[i] - a[i - 1] == 1)
      sum += c[a[i - 1] - 1];
  }

  cout << sum << endl;
  return 0;
}

Measured memory_bytes: 256
package main

import (
	"fmt"
)

func main() {
	var s string
	fmt.Scan(&s)

	ans := ""
	for _, r := range s {
		if r == 'B' {
			if ans != "" {
				ans = ans[:len(ans)-1]
			}
		} else {
			ans += string(r)
		}
	}
	fmt.Println(ans)
}


Measured memory_bytes: 512
#include <cstdio>
#include <cmath>
#include <vector>
#include <string>
#include <queue>
#include <set>

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

typedef std::vector<int> v;
typedef std::vector<std::vector<int>> vv;
typedef unsigned long long ull;

int main(void)
{
    int n, m;
    vv aaa;
    v from;
    scanf("%d %d", &n, &m);
    aaa.resize(n);
    from = std::vector<int>(n, -1);
    REP(i, m)
    {
        int a, b;
        scanf("%d %d", &a, &b);
        aaa[a - 1].push_back(b - 1);
        aaa[b - 1].push_back(a - 1);
    }

    std::queue<int> q;
    q.push(0);
    from[0] = 0;
    while (!q.empty())
    {
        int v = q.front();
        q.pop();
        for (auto to : aaa[v])
        {
            if (from[to] == -1)
            {
                from[to] = v;
                q.push(to);
            }
        }
    }
    puts("Yes");
    for (int i = 1; i < n; i++)
        printf("%d\n", from[i] + 1);
}

Measured memory_bytes: 9820
#include <bits/stdc++.h>
using namespace std;
int main(){
  int a,b,c;cin>>a>>b>>c;
  if((a<c) and (c<b)){
    cout<<"Yes";
  }else if((a>c) and (c>b)){
    cout<<"Yes";
  }else{
    cout<<"No";
  }
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define um unordered_map
#define us unordered_set
#define f first
#define s second
#define pb push_back
#define MOD 998244353
#define eps 1e-9
#define INF 1000000002

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<int, pii> piii;
const int N = 303;

int n;
int main() {
    int n;
    cin>>n;
    cout<<(n%2==0?0.5:(n/2+1)/(double)n);
    return 0;
}


Measured memory_bytes: 256
/********************************************************************************
	
	Code by a weak man who named CYJian, and he hopes the code can get more points.

	Algorithm: 

 ********************************************************************************/

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int __SIZE = 1 << 18;
char ibuf[__SIZE], *iS, *iT;

#define ge (iS == iT ? (iT = (iS = ibuf) + fread(ibuf, 1, __SIZE, stdin), (iS == iT ? EOF : *iS++)) : *iS++)
#define ri read_int()
#define rl read_ll()
#define FILE(s) freopen(s"in", "r", stdin), freopen(s"out", "w", stdout)

template<typename T>
inline void read(T &x) {
	char ch, t = 0; x = 0;
	while(!isdigit(ch = ge)) t |= ch == '-';
	while(isdigit(ch)) x = x * 10 + (ch ^ 48), ch = ge;
	x = t ? -x : x;
}
inline int read_int() { int x; return read(x), x; }
inline ll read_ll() { ll x; return read(x), x; }

template<typename T>
inline void chkmin(T&a, T b) { a = a < b ? a : b; }

const int MAXN = 100010;

int n;

struct UFS {
	int fa[MAXN];
	int d[MAXN];

	inline void init() { for(int i = 1; i <= n; i++) fa[i] = i; }
	inline int find(int x) { return fa[x] == x ? x : (find(fa[x]), d[x] ^= d[fa[x]], fa[x] = fa[fa[x]]); }
	inline void Merge(int u, int v) { int fu = find(u), fv = find(v); if(fu != fv) fa[fu] = fv, d[fu] = d[u] ^ d[v] ^ 1; }
	inline int val(int x) { return find(x), d[x]; }
}ufs;

struct WORK {
	vector<int> to[MAXN];
	int deg[MAXN];
	int id[MAXN];
	int rt;

	inline int dfs(int x) {
		vector<int>v;
		for(auto u : to[x]) v.push_back(dfs(u));
		if(deg[x]) v.push_back(x);
		sort(v.begin(), v.end());
		for(int i = 1; i < v.size(); i += 2)
			ufs.Merge(v[i], v[i + 1]);
		return v[0];
	}

	inline void solve() {
		for(int i = 1; i <= n; i++) deg[i] = 1, id[i] = i;
		for(int i = 1; i <= n; i++) {
			int f = ri;
			if(~f) to[f].push_back(i), deg[f] ^= 1;
			else rt = i;
		} dfs(rt);
	}
}A, B;

int main() {
#ifdef LOCAL
	FILE("");
#endif
	n = ri, ufs.init(), A.solve(), B.solve();
	for(int i = 1; i <= n; i++)
		if(A.deg[i] ^ B.deg[i])
			return puts("IMPOSSIBLE"), 0;
	puts("POSSIBLE");
	for(int i = 1; i <= n; i++)
		printf("%d%c", A.deg[i] * (ufs.val(i) ? 1 : -1), " \n"[i == n]);
	return 0;
}

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


int main()
{
  ll n,m,i,j,temp=0,flag=0;
string s;
cin>>n;
for(i=1;i<=n;i++)
{
    if(i%5&&i%3)temp+=i;
}
cout<<temp<<endl;

return 0;

}






Measured memory_bytes: 3628
#include<bits/stdc++.h>
using namespace std;
#define sc(x) scanf("%d",&x)
#define sc2(x,y) scanf("%d%d",&x, &y)
#define sc3(x,y,z) scanf("%d%d%d",&x, &y, &z)
#define pr(a) printf("%d\n",a)
#define all(v) (v).begin(),(v).end()
#define rall(v) (v).rbegin(),(v).rend()
#define ll long long
#define F first
#define S second
#define inf INT_MAX
const int N = 1e5 + 5;
int n, m, x, y, k, ans;
int a[15], sum;
int main(){

	string s;
	cin >> s;
	for (int i = 0; i < s.size(); i++){
		if (s[i] == ',')s[i] = ' ';
	}
	cout << s << endl;
	return 0;
}









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

typedef struct Node {
    int key;
    Node *parent, *left, *right;
} Node;

Node *NIL, T[MAX];

void print(int n) {
    int i;
    Node *N;
    for (i=1; i<=n; i++) {
        N = &T[i];
        printf("node %d: key = %d, ", i, N->key);
        if (N->parent!=NIL) printf("parent key = %d, ", N->parent->key);
        if (N->left!=NIL) printf("left key = %d, ", N->left->key);
        if (N->right!=NIL) printf("right key = %d, ", N->right->key);
        printf("\n");
    }
}

void fill(int i, int k) {
    if (i==1) {
        T[i].key=k;
    } else {
        T[i].key=k;
        T[i].parent=&T[i/2];
        if (i%2==0) T[i/2].left=&T[i];
        else T[i/2].right=&T[i];
    }
}

void maxHeapify(int i) {
    int j=0, k;
    Node *largest = &T[i];
    Node *l = T[i].left;
    Node *r = T[i].right;
    if (l!=NIL && l->key > T[i].key) {
        largest=l;
        j=2*i;
    }
    if (r!=NIL && r->key > largest->key) {
        largest=r;
        j=2*i+1;
    }

    if (largest!=&T[i]) {
        k = largest->key;
        T[j].key = T[i].key;
        T[i].key = k;
        maxHeapify(j);
    }
}

int main() {
    int n, i, k;
    for (i=0; i<MAX; i++) {
        T[i].parent=T[i].left=T[i].right=NIL;
        T[i].key=0;
    }

    scanf("%d", &n);
    for (i=1; i<=n; i++) {
        scanf("%d", &k);
        fill(i, k);
    }
    
    for (i=n; i>=1; i--) {
        maxHeapify(i);
    }
    
    for (i=1; i<=n; i++) {
        printf(" %d", T[i].key);
    }
    printf("\n");

    return 0;
}


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


/* macro */
#define int long long
#define rep(i,a,b) for(int i=a;i<b;i++)
#define revrep(i,a,b) for(int i = a; i > b; i--)
#define exist(s,e) ((s).find(e)!=(s).end())
#define all(v) (v).begin(), (v).end()
#define each(s,itr) for(auto (itr) = s.begin(); (itr) != s.end(); (itr)++)
#define sum(v) accumulate(all(v), (0LL))
#define sec second
#define fir first
#define pb push_back



/* alias */
template<class T> using vec = vector<T>;
typedef vector<int> vi;
typedef pair<int, int> pi;


/* constant */
const int inf = pow(2, 62);
const int mod = 1e9 + 7;
int dx[8]={1,0,-1,0,-1,1,-1,1};
int dy[8]={0,1,0,-1,-1,-1,1,1};



/* io_method */
int input(){int tmp;cin >> tmp;return tmp;}
string raw_input(){string tmp;cin >> tmp;return tmp;}
string readline(){string s;getline(cin, s);return s;}
template<class T> void printx(T n){cout << n;}
template<class T, class U> void printx(pair<T, U> p){cout << "(" << p.first << "," << p.second << ")";}
template<class T> void printx(vector<T> v){cout << "{";rep(i,0,v.size()){printx(v[i]);if(i != v.size()-1)printx(",");}cout << "}";}
template<class T> void print(T n){printx(n);cout << endl;}
template<class T> void print(set<T> s){cout << "{";each(s, e){if(e != s.begin()) printx(",");printx(*e);}cout << "}" << endl;}
template<class T, class U> void print(map<T, U> mp){cout << "{";each(mp, e){cout << "(" << e -> first << "," << e -> second << ")";}cout << "}" << endl;}


/* general_method */
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; }




/* main */



signed main(){

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

    
    int x, a, b; cin >> x >> a >> b;

    if(abs(x - a) > abs(x - b)){
        print("B");
    }else{
        print("A");
    }

    

    
    




    
    



    
    

    







   




    

    

    




    



    



    

 
    
    


    

    
   
    













}






    










    




    










Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using P = pair<string, string>;
ll MOD = 1e9+7;
int main()
{
    int n;
    cin >> n;
    vector<vector<int>> d(n);
    for(int i = 0; i < n-1; i++)
    {
        int x, y;
        cin >> x >> y;
        x--;y--;
        d[x].push_back(y);
        d[y].push_back(x);
    }
    int size = d[0].size();
    function<int(int, int)> dfs = [&](int v, int pre)
    {
        int grundy = 0;
        for(int cand : d[v])
        {
            if(cand == pre) continue;
            grundy ^= dfs(cand, v) + 1;
        }
        return grundy;
    };
    int x = 0;
    for(int i = 0; i < size; i++)
    {
        int grundy = dfs(d[0][i], 0);
        x ^= grundy+1;
    }
    if(x != 0)
    {
        cout << "Alice" << endl;
    }
    else
    {
        cout << "Bob" << endl;
    }
}



Measured memory_bytes: 13568
from collections import deque

n= int(input())

if n < 10:
    print(n);exit()

q=deque()
for i in range(1,10):
    q.append(i)

for _ in range(1,n):

    t = q.popleft()

    # tt = t%10
    tt = int(str(t)[-1])

    for j in range(-1,2):
        ttt = tt+j
        if ttt >= 0 and ttt <= 9:
            # q.append(t * 10 + ttt)
            q.append(int(str(t) + str(ttt)))

print(q.popleft())


Measured memory_bytes: 10884
#include<bits/stdc++.h>
using namespace std;
int main() {  
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	int n;
	cin>>n;
	vector<pair<int,int> > v;
	int bad_sum = n + !(n%2);
	for(int i=1;i<=n;i++){
		for(int j=i+1;j<=n;j++){
			if(i + j == bad_sum) continue;
			v.push_back({i, j});
		}
	}
	cout<<v.size()<<endl;
	for(auto p : v){
		cout<<p.first<<" "<<p.second<<"\n";
	}
	return 0;  
}


Measured memory_bytes: 384
from heapq import *

N, M, S = tuple(map(int, input().split()))

T = [[10**18 for _ in range(2451)] for _ in range(N)]

act = [[] for _ in range(N)]

for i in range(M):
  U, V, A, B = tuple(map(int, input().split()))
  U -= 1
  V -= 1
  act[U] += [(V, A, B)]
  act[V] += [(U, A, B)]

for i in range(N):
  C, D = tuple(map(int, input().split()))
  act[i] += [(i, -C, D)]

que = [(0, 0, S)]

while que:
  (currentT, n, coins) = heappop(que)
  for m, cost, t in act[n]:
    # もし「払える金額で」「最小時間T[移動先][所持金]を更新できるとき」に値を更新、キューに状態を追加。
    if coins >= cost and currentT + t < T[m][min(2450, coins - cost)]:
      T[m][min(2450, coins - cost)] = currentT + t
      heappush(que, (currentT + t, m, min(2450, coins - cost)))

for i in range(1, N):
  print(min(T[i]))

Measured memory_bytes: 25908
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <stack>
#include <queue>
#include <set>
#include <map>
using namespace std;
#define MOD @
#define ADD(X,Y) ((X) = ((X) + (Y)%MOD) % MOD)
typedef long long i64; typedef vector<int> ivec; typedef vector<string> svec;

int main()
{
	char S[110];
	scanf("%s", S);
	int N = strlen(S);
	int ret = 10000;
	for (int i = 0; i < 26; ++i) {
		int reqmx = 0;
		for (int j = 0; j < N; ++j) {
			int waf = N - j;
			for (int k = j; k < N; ++k) {
				if (S[k] == i + 'a') {
					waf = min(waf, k - j);
				}
			}
			reqmx = max(reqmx, waf);
		}
		ret = min(ret, reqmx);
	}
	printf("%d\n", ret);
	return 0;
}


Measured memory_bytes: 256
#include"bits/stdc++.h"
#define ll long long
#define inf 100005
#define mod 1000000007
using namespace  std;

vector<vector<ll>>g(inf);
vector<ll>indgree(inf);
vector<ll>dist(inf);
bool visted[inf];



int main(){
	ll h,w;
	cin>>h>>w;

	char arr[h][w];

	for(ll i=0;i<h;i++){
		for(ll j=0;j<w;j++){
			cin>>arr[i][j];
		}
	}
	
	vector<vector<ll>> dp(h,vector<ll>(w));
	dp[0][0] = 1;

	for(ll i=0;i<h;i++){
		for(ll j=0;j<w;j++){
			if(j+1<w && arr[i][j+1]=='.'){
				dp[i][j+1]+=dp[i][j];

				if(dp[i][j+1]>=mod){
					dp[i][j+1]-=mod;
				}
			}

			if(i+1<h && arr[i+1][j]=='.'){
				dp[i+1][j]+=dp[i][j];

				if(dp[i+1][j]>=mod){
					dp[i+1][j]-=mod;
				}	
			}
		}
	}

	cout<<dp[h-1][w-1]<<endl;
	return 0;
}

Measured memory_bytes: 15888
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef map<int,int> mii;
typedef map<ll,ll> mll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<ll>   vl;
#define f(i,n)  for(i=0;i<n;i++)
#define f1(i,n)  for(i=1;i<n;i++)
#define fr(i,n) for(i=n-1;i>=0;i--)
#define em emplace_back
#define mp make_pair
#define in insert
#define fi first
#define sc second
#define b begin
#define e end
#define er erase
#define l length
#define c clear
#define si size
#define fastio ios_base::sync_with_stdio(false);cin.tie(0);
const double pi=3.141592653;
const ll infi=1000000001;
const ll MOD=1000000007;
const ll mod=998244353;
const string no="NO\n",yes="YES\n";

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

// ll con(vl v[],ll hai[],ll sz){
//     ll count=0;
//     for(int i=1;i<sz;i++){
//         if(hai[i]==0){
//             count++;
//             dfs(v,i,hai);
//         }
//     }
    // return count;
// }

// void gcde(int a,int b,int *x,int *y){
//     if(a==0){
//         *x=0;
//         *y=1;
//         return;
//     }    
//     int x1,y1;
//     gcde(b%a,a,&x1,&y1);
    
//     *x=y1-(b/a)*x1;
//     *y=x1;
// }


// ll recur(vl v,ll in,ll m,ll n){
//     if(in==-1)  return 1000000000001;
//     ll d,e,c;
//     d=max(m/v[in],n*v[in]);
//     c=recur(v,in-1,m/v[in],n*v[in]);
//     e=recur(v,in-1,m,n);
//     return min(c,min(e,d));
// }

// ll bexpo(ll a,ll p){
//     ll x=1;
//     while(p){
//     if(p&1){
//         x=(x*a)%mod;
//     }
//     a=(a*a)%mod;
//     p>>=1;
//     }
//     return x;
// }
// ll fact[500001],invf[500001];
// int dx[8]{-1,0,0,1,-1,-1,1,1};
// int dy[8]{0,-1,1,0,-1,1,-1,1};
// ll dp[200001];
// int l=0;
//  void dfs(vi v[],int node,int hai[]){
//     hai[node]=1;
//     l++;
//     for(auto i:v[node]){
//         if(hai[i]==0){
//             dfs(v,i,hai);
//         }
//     }
// }
int s[1000001];

int main() {
    fastio
    int n,i,j;
    f(i,1000001){
        s[i]=i;
    }
    for(int j=2;j*j<1000001;j++){
        if(s[j]==j){
            for(int i=j*j;i<1000001;i+=j){
                if(s[i]==i){
                    s[i]=j;
                }
            }
        }
    }
    cin>>n;
    ll a[n];
    f(i,n){
        cin>>a[i];
    }
    set<ll> st;
    map<ll,ll> mp;
    f(i,n){
        while(a[i]>1){
            st.in(s[a[i]]);
            a[i]/=s[a[i]];
        }
        for(auto j:st){
            mp[j]++;
        }
        st.clear();
    }
    int nt=0,se=0;
    for(auto j:mp){
        if(j.sc==n){
            nt=1;
            break;
        }else if(j.sc>1){
            se=1;
        }
    }
    if(nt)  cout<<"not coprime";
    else if(se) cout<<"setwise coprime";
    else cout<<"pairwise coprime";
    

	return 0;
}

Measured memory_bytes: 20120
/**
*    author:  souzai32
*    created: 13.08.2020 13:17:00
**/

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

int main() {

    int n;
    cin >> n;
    vector<int> a(n);
    rep(i,n) cin >> a.at(i);

    sort(a.begin(),a.end());
    int c=0;
    for(int i=0; i<n; i++){
        if(a.at(i)<0){
            a.at(i)*=-1;
            c++;
        }
        else break;
    }

    sort(a.begin(),a.end());
    long long sum;
    if(c%2) sum=-a.at(0);
    else sum=a.at(0);
    for(int i=1; i<n; i++) sum+=a.at(i);

    cout << sum << endl;

    return 0;
}

Measured memory_bytes: 3760
n = int(input())
a = list(map(int, input().split()))
q = int(input())
bc = [list(map(int, input().split())) for i in range(q)]
l = [0] * 100000
suml = 0
for i in a:
  l[i-1] += 1
  suml += i
for i in bc:
  suml += l[i[0]-1] * (i[1] - i[0])
  l[i[1]-1] += l[i[0]-1]
  l[i[0]-1] = 0
  print(suml)

Measured memory_bytes: 32080
#include<stdio.h>

int main(){
  int n, a, b;
  int train, taxi;
  
  scanf("%d %d %d", &n, &a, &b);
  
  train = n * a;
  taxi = b;
  
  printf("%d", ((train <= taxi) ? train : taxi));
  
  return 0;
}

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

bool primeNumber(long long n) {
    if (n<2) return false;
    else {
        for (long long i=2; i*i<n; i++) {
            if (n%i==0) return false;
        }
        return true;
    }
}

int main() {
    long long X;
    cin >> X;
    while(true) {
        if (primeNumber(X)) {
            cout << X << endl;
            return 0;
        }
        X++;
    }
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main()
{
  int N, X, Y;
  cin >> N >> X >> Y;

  int dp[605][605]; // ????????????, ???????????????????¶?
  memset(dp, -1, sizeof(dp));
  dp[X + 302][Y + 302] = 0;

  for(int i = 0; i < N; i++) {
    int A, B, C, D;
    cin >> A >> B >> C >> D;
    for(int j = -300; j <= 300; j++) {
      for(int k = -300; k <= 300; k++) {
        if(j + A + 302 <= 604 && k - B + 302 <= 604 && j + A + 302 >= 0 && k - B + 302 >= 0 && ~dp[j + A + 302][k - B + 302])
          dp[j + 302][k + 302] = max(dp[j + A + 302][k - B + 302], dp[j + 302][k + 302]); 
        if(k + C + 302 <= 604 && ~dp[j + 302][k + C + 302])
          dp[j + 302][k + 302] = max(dp[j + 302][k + C + 302] + D, dp[j + 302][k + 302]); 
      }
    }
  }
  int ret = 0;
  for(int i = 302; i <= 604; i++) {
    for(int j = 302; j <= 604; j++) {
      ret = max(ret, dp[i][j]);
    }
  }
  cout << ret << endl;
 
}

Measured memory_bytes: 2600
#数列のすべての項の積を2で何回割れるか調べて出力する
N=int(input())
ListA=[]
A=input()
ListA=A.split()
ListB=[]
for i in range(0,len(ListA),1):
  ListB.append(int(ListA[i]))
c=0
S=0
for i in range(0,len(ListB),1):
  A=int(ListB[i])
  while A%2==0:
    A=A/2
    c+=1
  else:
    S+=c
    c=0
print(S)
    

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

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

    int s, w;
    cin >> s >> w;
    
    if(w < s)
        cout << "safe";
    else
        cout << "unsafe";   

    return 0;
}

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

using namespace std;

int main (){
	
	char s[3];
	int i,j=0;
	
	cin >> s[0]>>s[1]>>s[2];

	if (s[0] != s[1] || s[1] != s[2] || s[2] != s[0]) {
		cout << "Yes" << endl;
	}
	else {
		cout << "No" << endl;
	}
	

	return 0;
}

Measured memory_bytes: 256
fn run() {
    proconio::input! {
        n: u64,
    }
    let ans = (1..=n)
        .filter(|&v| v % 3 != 0 && v % 5 != 0)
        .fold(0, |s, a| s + a);
    println!("{}", ans);
}

fn main() {
    run();
}

Measured memory_bytes: 2112
// I SELL YOU...! 
#include<iostream>
#include<vector>
#include<algorithm>
#include<functional>
#include<queue>
#include<chrono>
#include<iomanip>
#include<map>
#include<set>
using namespace std;
using ll = long long;
using P = pair<ll,ll>;
void init_io(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  cout << setprecision(10);
}
string s,t;
ll k,n,ans=0;
int z_c(int v){
  int res = 0;
  while(v!=0){
    if(v%10!=0) res++;
    v/=10;
  }
  return res;
}
signed main(){
  init_io();
  cin >> s >> k;
  n = s.size();
  ll n_arr[n];
  for(int i=0;i<n;i++){
    n_arr[i] = s[i]-'0';
  }
  t = s;
  ll dp[110][4][2]={};
  dp[0][1][1] = 1;
  dp[0][1][0] = n_arr[0]-1;
  for(int i=1;i<n;i++){
    dp[i][1][0] = 9;
    for(int j=1;j<=3;j++){
      if(n_arr[i]==0){
        dp[i][j][1] += dp[i-1][j][1];
        dp[i][j][0] += dp[i-1][j][0] + dp[i-1][j-1][0]*9;
      }else{
        dp[i][j][1] += dp[i-1][j-1][1];
        dp[i][j][0] += dp[i-1][j-1][1]*(n_arr[i]-1) + dp[i-1][j-1][0]*9 
          + dp[i-1][j][1] + dp[i-1][j][0];
      }
    }
  }
  cout << dp[n-1][k][0] + dp[n-1][k][1]<<endl;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF= 1LL << 60;
#define REP(i,n) for(ll i=0; i<n; i++)
#define FOR(i,a,n) for(ll i=a; i<n; i++)
struct Point{
    double x,y;
};
ll gcd(ll a, ll b)
{
    if (a < b)
        gcd(b, a);
    ll r;
    while ((r = a % b))
    {
        a = b;
        b = r;
    }
    return b;
}
int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll a,b;
    cin >> a >> b;
    cout << a * b / gcd(a, b) << endl;
}


Measured memory_bytes: 256
#include <algorithm>
#include <cmath>
#include <cstdint>
#include <cstdio>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
using namespace std;
#define rep(i, n) for(int(i) = 0; (i) < (n); (i)++)
#define FOR(i, m, n) for(int(i) = (m); (i) < (n); (i)++)
#define All(v) (v).begin(), (v).end()
#define pb push_back
#define MP(a, b) make_pair((a), (b))
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
const int INF = 1 << 30;
const ll LINF = 1LL << 60;
const int MOD = 1e9 + 7;

int main() {
    int S, W;
    cin >> S >> W;
    if(W >= S) {
        cout << "unsafe" << endl;
    } else {
        cout << "safe" << endl;
    }
    return 0;
}

Measured memory_bytes: 3592
#include <iostream>
#include <fstream>
#include <cmath>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <cstdlib>
#include <cstdio>
#include <string>
#include <cstring>
#include <cassert>
#include <utility>
#include <iomanip>
#include <chrono>
#include <random>
#include <bitset>

using namespace std;

#define sz(x) (int) x.size()
#define unique(x) x.erase(unique(x.begin(), x.end()), x.end())
#define all(a) a.begin(), a.end()
#define sqr(x) ((x) * (x)) 
#define y1 aksjdaskdjksjfksdjf
#define left kdnvldvoiwejifejg
#define right lkdsjflksdjfdjfk
#define prev asdasfsadjkjsdfjs
#define tm aklsjdasjdasjdkdjjf
#define lcm hddalkwjeidjjhasda
#define random_shuffle asdasdd

const int a[] = {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};

int main() { 

  int n;
  cin >> n;
  cout << a[n - 1] << endl;

  return 0;
}


Measured memory_bytes: 256
INF = 10 ** 7
n, m, x = gets.split.map(&:to_i)
books = []
n.times { books << gets.split.map(&:to_i) }
ans = INF
[true, false].repeated_permutation(n).each do |buying|
  skills = Array.new(m, 0)
  price = 0
  buying.each_with_index do |bool, i|
    next if bool
    book = books[i]
    price += book[0]
    book[1..-1].each_with_index do |up, skill|
      skills[skill] += up
    end
  end
  ans = price if skills.min >= x && ans > price
end
puts ans == INF ? -1 : ans


Measured memory_bytes: 14404
def examA():
    S = SI()
    ans = "No"
    flag = False
    for s in S:
        if flag:
            if s=="F":
                ans = "Yes"
                break
        else:
            if s=="C":
                flag = True
    print(ans)
    return

def examB():
    K, T = LI()
    A = LI(); A.sort()
    ans = max(0,A[-1]*2-sum(A)-1)
    print(ans)
    return

def examC(mod):
    N = I()
    T = LI(); A = LI()
    H = [0]*N
    ans = 1
    if T[-1] != A[0]:
        ans = 0
    H[0] = T[0]; H[N-1] = A[N-1]
    for i in range(N-1):
        if T[i+1]>T[i]:
            if H[i+1]==0:
                H[i+1] = T[i+1]
            elif H[i+1]!=T[i+1]:
                ans = 0
        else:
            if H[i+1]==0:
                H[i+1] = -T[i+1]
    for i in range(N-1,0,-1):
        if A[i-1]>A[i]:
            if H[i-1]==0:
                H[i-1] = A[i-1]
            elif H[i-1]<0:
                if -H[i-1]<A[i-1]:
                    ans = 0
                else:
                    H[i-1] = A[i-1]
            elif H[i-1]!=A[i-1]:
                ans = 0
#    print(H)
    flag = False; cur = 0
    for i in H:
        if flag:
            if i<0:
                cur +=1
            else:
                ans *=(min(now,i)**cur)%mod
                ans %=mod
                flag = False
                cur = 0; now = i
        else:
            if i<0:
                cur = 1
                flag = True
            else:
                now = i
    print(ans%mod)
    return

import sys,copy,bisect,itertools,heapq,math
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
mod = 10**9 + 7
inf = float('inf')

if __name__ == '__main__':
    examC(mod)


Measured memory_bytes: 82520
#include <map>
    #include <set>
    #include <list>
    #include <cmath>
    #include <deque>
    #include <queue>
    #include <stack>
    #include <cstdio>
    #include <string>
    #include <vector>
    #include <complex>
    #include <cstdlib>
    #include <cstring>
    #include <iomanip>
    #include <numeric>
    #include <utility>
    #include <iostream>
    #include <algorithm>
    #include <functional>
     
    using namespace std;
     
    #define INF (1 << 30)
    #define INFL (1LL << 62)
    #define MOD7 1000000007
    #define MOD9 1000000009
    #define EPS 1e-10
     
    #define ll long long
    #define ull unsigned long long
    #define pii pair<int, int>
    #define pll pair<ll, ll>
    #define pul pair<ull, ull>
    #define all(a) (a).begin(), (a).end()
    #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)
     
    void YES() { cout << "YES" << endl; }
    void NO() { cout << "NO" << endl; }
    void Yes() { cout << "Yes" << endl; }
    void No() { cout << "No" << endl; }
    void yes() { cout << "yes" << endl; }
    void no() { cout << "no" << endl; }
    void Taka() { cout << "Takahashi" << endl; }
    void Aoki() { cout << "Aoki" << endl; }
    void digit(int d) { cout << fixed << setprecision(d); }
    void IOup() { cin.tie(0); ios::sync_with_stdio(false); }
     
    int main() {
    	int n;
    	cin >> n;
    	if (n / 10 == 9 || n % 10 == 9)
    		Yes();
    	else
    		No();
     
    	return 0;
    }

Measured memory_bytes: 256
#include<stdio.h>
#include<math.h>
int main(void){
	double x1, x2, y1, y2, a, b, c;
	scanf("%lf %lf %lf %lf\n", &x1, &y1, &x2, &y2);
	a = x2-x1;
	b = y2-y1;
	c = pow(a, 2) + pow(b, 2);
	c = sqrt(c);
	printf("%f\n", c);
	
	return 0;
}


Measured memory_bytes: 2064
N,T = map(int, input().split())
cr_list = [list(map(int, input().split())) for _ in range(N)]

def test(lst):
    return lst[0] if lst[1]<=T else 10**4

res = min(map(test, cr_list))
if not res <= 1000:
    res = 'TLE'

print(res)

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

int main()
{
	int n, m, c;
	cin >> n >> m >> c;
	int b[21];
	for (int i = 0; i < m; ++i)
	{
		cin >> b[i];
	}
	int a, now, ans = 0;
	for (int i = 0; i < n; ++i)
	{
		now = 0;
		for (int j = 0; j < m; ++j)
		{
			cin >> a;
			now += a * b[j];
		}
		ans += (now > -c);
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 256
while True:
	m,f,r=map(int,input().split())
	if m==-1 and f==-1 and r==-1:
		break
	if m==-1 or f==-1 or m+f<30:
		print("F")
	elif m+f>=80:
		print("A")
	elif m+f>=65:
		print("B")
	elif m+f>=50:
		print("C")
	elif m+f>=30:
		if r>=50:
			print("C")
		else:
			print("D")


Measured memory_bytes: 5596
#include <bits/stdc++.h>
using namespace std;
#define pp pair<int,int>
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define ll long long
#define ld long double
#define all(a) (a).begin(),(a).end()
#define mk make_pair
ll MOD=1000000007;
ll mod=998244353;
int inf=1000001000;
ll INF=1e18+5;


int main() {
  int a=700;
  string s;
  cin >> s;
  rep(i,3){
    if (s[i]=='o') a+=100;
  }
  cout << a << endl;
}


Measured memory_bytes: 256
import java.util.*;

public class Main{
	public static void main(String[] args){
		Scanner stdIn = new Scanner(System.in);
		List<Double> result = new ArrayList<Double>();
		
		int x = stdIn.nextInt(), h = stdIn.nextInt();
		while( x != 0 || h != 0 ){
			double th = (double)x*x/4 + h*h;
			double a = Math.sqrt(th);
			double b = 2*a*x+x*x;
			result.add(b);
			x = stdIn.nextInt();
			h = stdIn.nextInt();
		}
		
		for(Double ans : result){
			System.out.printf("%.6f%n", ans);
		}
	}
}

Measured memory_bytes: 12000