akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
 
using namespace std;
 
#define lli long long int
#define MOD 10000000070
#define DEBUG 0
#define REP(i,n) for(int i=0;i<n;i++)
 
vector<lli> a,b,c;
 
class p{
public:
	lli x,y,z;
	lli sum;
	lli hash;
	p(lli sX,lli sY,lli sZ){
		x = sX;
		y = sY;
		z = sZ;
		sum = a[x]+b[y]+c[z];
		hash = x*10000*10000 + y*10000+z;
	}
};
 
p make_p(lli sX,lli sY,lli sZ){
	p tmp(sX,sY,sZ);
	return tmp;
}

bool operator < (const p &p1,const p &p2){
	if(p1.sum != p2.sum)return p1.sum < p2.sum;
	else if(p1.x != p2.x)return p1.x < p2.x;
	else if(p1.y != p2.y)return p1.y < p2.y;
	else p1.z < p2.z;
}
 
void sort2(vector<lli> *a){
	sort(a->begin(),a->end(),greater<lli>());
}
 
int main(){
 
	lli x,y,z,k;
	cin>>x>>y>>z>>k;
	a.resize(x);
	b.resize(y);
	c.resize(z);
 
	REP(i,x)cin>>a[i];
	REP(i,y)cin>>b[i];
	REP(i,z)cin>>c[i];
 
	sort2(&a);
	sort2(&b);
	sort2(&c);
 
	priority_queue<p> pQ;
	set<lli> flag;
 
	p first(0,0,0);
	pQ.push(first);
	flag.insert(first.hash);
 
	lli cnt=0;
	while(pQ.size()){
		p top = pQ.top();
		if(DEBUG)cout<<"x,y,z="<<top.x<<" "<<top.y<<" "<<top.z<<endl;
		
		pQ.pop();
		cout<<top.sum<<endl;
		cnt++;
		if(cnt>=k)break;
 
		if(top.x+1<x){
			if(flag.find(make_p(top.x+1,top.y,top.z).hash) == flag.end()){
				pQ.push(make_p(top.x+1,top.y,top.z));
				flag.insert(make_p(top.x+1,top.y,top.z).hash);
			}
		}
		if(top.y+1<y){
			if(flag.find(make_p(top.x,top.y+1,top.z).hash) == flag.end()){
				pQ.push(make_p(top.x,top.y+1,top.z));
				flag.insert(make_p(top.x,top.y+1,top.z).hash);
			}
		}
		if(top.z+1<z){
			if(flag.find(make_p(top.x,top.y,top.z+1).hash) == flag.end()){
				pQ.push(make_p(top.x,top.y,top.z+1));
				flag.insert(make_p(top.x,top.y,top.z+1).hash);
			}
		}
	}
	return 0;
 
}

Measured memory_bytes: 896
#include <bits/stdc++.h>
#include <string>
using namespace std;
#define ll long long
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rrep(i, n) for (int i = n - 1; i >= 0; i--)
#define _GLIBCXX_DEBUG

void printv(vector<int> v) {
  for (int i : v)
    cout << i << " ";
  cout << endl;
}

vector<int> coins = {10, 50, 100, 500};

//お釣りの枚数を硬貨の種類ごとに返す。
vector<int> cntChange(int now) {
  vector<int> res(4, 0);
  rep(i, 4) {
    int cntCoin = now / coins[3 - i];
    res[3 - i] += cntCoin;
    now %= coins[3 - i];
  }
  return res;
}

int main() {
  bool first = true;
  while (true) {
    int p;
    cin >> p;
    if (!p)
      break;
    if (!first)
      cout << endl;
    else
      first = false;

    vector<int> cntC(4);
    int summ = 0;
    for (int i = 0; i < 4; i++) {
      cin >> cntC[i];
      summ += coins[i] * cntC[i];
    }
    vector<int> changes = cntChange(summ - p);
    for (int i = 0; i < 4; i++) {
      int ans = cntC[i] - changes[i];
      if (ans>0)
        cout << coins[i] << " " << ans << endl;
    }
  }
}



Measured memory_bytes: 3104
# ABC104C - All Green
def rec(score: int, idx: int) -> int:
    if idx == 0:  # base case
        return 1 << 30

    point, (num, bonus) = idx * 100, A[idx]
    cnt = min(score // point, num)
    cur_score = cnt * point
    if cnt == num:
        cur_score += bonus

    rest = score - cur_score
    if rest > 0:
        cnt += rec(rest, idx - 1)  # make up for the shortage

    # compare to other cases without A[idx] recursively
    return min(cnt, rec(score, idx - 1))


def main():
    global A
    D, G = map(int, input().split())
    A = [(0, 0)] + [tuple(map(int, input().split())) for _ in range(D)]
    ans = rec(G, D)
    print(ans)


if __name__ == "__main__":
    main()


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

int main() {
	string S,T;
	bool ok=0;
	cin >> S >> T;
	S += S;
	
	rep(i,S.size())
		if(S.substr(i,T.size()) == T)
			ok = 1;

	if(ok)
		cout << "Yes";
	else
		cout << "No";
	cout << endl;
}

Measured memory_bytes: 256
#include<iostream>
#include<stdio.h>
#include<string.h>
#include<algorithm>
#define maxn 2000005
using namespace std;
typedef long long ll;
const ll mod=1e9+7;
ll fac[maxn],inv[maxn];
ll pow25[maxn],pow26[maxn];
ll quickpow(ll p,ll k)
{
	ll ans=1;
	while(k)
	{
		if(k&1)
			ans=(ans*p)%mod;
		p=(p*p)%mod;
		k>>=1;
	}
	return ans;
}
ll c(ll n,ll m)
{
	if(n<m) return 0;
	return (((fac[n]*inv[m])%mod)*inv[n-m])%mod;
}
char s[maxn];
int main()
{
	pow25[0]=1;
	pow26[0]=1;
	fac[0]=1;
	for(int i=1;i<=2e6;i++)
	{
		pow25[i]=(pow25[i-1]*25)%mod;
		pow26[i]=(pow26[i-1]*26)%mod;
		fac[i]=(fac[i-1]*i)%mod;
	}
	inv[2000000]=quickpow(fac[2000000],mod-2);
	for(int i=2e6-1;i>=0;i--)
		inv[i]=(inv[i+1]*(i+1))%mod;
	ll ans=0;
	int k,len;
	scanf("%d",&k);
	scanf("%s",s+1); len=strlen(s+1);
	for(int i=1;i<=k+len;i++)
	{
		ll temp1=pow26[i-1];
		ll temp2=c(k+len-i,len-1);
		if(temp2==0) break;
		temp1=(temp1*temp2)%mod;
		ll temp3=pow25[k-i+1];
		temp1=(temp1*temp3)%mod;
		ans=(ans+temp1)%mod;
	}
	printf("%lld\n",ans);
}

Measured memory_bytes: 67112
#include<bits/stdc++.h>
using namespace std;
#define rep(i,x,y) for(int i=x;i<y;i++)
#define print(A,x,n) rep(I,0,n){cout<<(I ? " ":"")<<A[I]x;}cout<<endl;
#define pprint(A,y,m,n) rep(J,0,m){print(A[J],y,n);}
const long mod=998244353;
const int size=3e5+1;
const int inf=1e9;
int main(){
	int T; cin>>T;
	long A,B,C,D;
	rep(i,0,T){
		cin>>A>>B>>C>>D;
		long g = __gcd(B, D);
        long r = (A - C) % D;
		long x = (D - r) / g + 1;
		long y = (g * x + r) - D; //cout<<y<<" ";
        if(B > D || A < B) cout<<"No"<<endl;
		else if(C + y >= B) cout<<"Yes"<<endl;
		else cout<<"No"<<endl;
	}
}

Measured memory_bytes: 256
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner scan= new Scanner(System.in);
		int a=scan.nextInt();
		int b=scan.nextInt();
		int c=scan.nextInt();
		if(a>b) System.out.println("0");
		else if(a*c<=b) System.out.println(c);
		else System.out.println(b/a);

	}

}


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


int main() {
    int k;
    string s;
    cin >> k >> s;
    int length = s.size();
    if(length <= k){
        cout << s << endl;
    }
    else{
        rep(i, k){
            cout << s[i];
        }
        cout << "..." << endl;
    }


    return 0;
}

Measured memory_bytes: 3624
#include <bits/stdc++.h>
using namespace std;
string s;
long long ans,f[300]={0};
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin>>s;
	for (int i=0; i<s.length(); i++)
		f[s[i]]++;
	long long len = s.length();
	ans = len*(len-1)/2;
	for (int i='a'; i<='z'; i++){
		ans-=(f[i]*(f[i]-1)/2);
	}
	++ans;
	cout<<ans<<"\n";
}

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

int main(){
  int n;
  cin>>n;
  ll ans=0;
  rep(i,n) ans+=i;
  cout<<ans;   

}

Measured memory_bytes: 3608
#include<bits/stdc++.h>
using namespace std;
#define INF 1000000007
#define F first
#define S second
#define FF first.first
#define FS first.second
#define SF second.first
#define SS second.second
typedef long long ll;
typedef pair<int, int> P;
typedef pair<P, P> PP;
typedef pair<int, P> iP;
typedef pair<P, int> Pi;
int main(void){
	ll h, r;
	cin >> h >> r;
	if(h + r == 0) cout << 0 << endl;
	else if(h + r < 0) cout << -1 << endl;
	else if(h + r > 0) cout << 1 << endl;
	return 0;
}



Measured memory_bytes: 3096
n,x,y = map(int,input().split())
ans = [0]*n
for i in range(1,n):
    for j in range(i+1,n+1):
        z = min(j-i, abs(x-i)+abs(j-y)+1, abs(y-i)+abs(j-x)+1)
        ans[z] += 1
for i in range(1,n):
    print(ans[i])

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

#define REP(i, m, n) for (int i = (m); i < (int)(n); i++)
#define REPS(i, m, n) for (int i = (m); i <= (int)(n); i++)
#define rep(i, n) REP(i, 0, n)
#define reps(i, n) for (int i = 0; i <= (int)(n); i++)
#define rrep(i, x) for (int i = ((int)(x)-1); i >= 0; i--)
#define rreps(i, x) for (int i = (int)(x); i >= 0; i--)
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define pb push_back
#define fi first
#define se second
typedef long long ll;
typedef pair<int, int> P;
const int inf = INT_MAX;
const ll INF = 1LL << 60;
const ll mod = 1e9 + 7;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
template<typename A, size_t N, typename T> void Fill(A (&array)[N], const T &val) { fill( (T*)array, (T*)(array+N), val ); }

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

    int A, B;
    cin >> A >> B;

    if (A % 3 == 0|| B % 3 == 0 || (A+B) % 3 == 0) {
        cout << "Possible" << endl;
    } else {
        cout << "Impossible" << endl;
    }
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <string>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <set>
#include <vector>
#include <map>

#define rep2(i, b, n) for(int i=b; i < n; ++i)
#define repm(i, b, n) for(int i=b; i > n; --i)
#define rep(i, n) rep2(i, 0, n)
#define sz(v) v.size()
#define mp(x, y) make_pair(x, y)
#define fst first
#define scd second
#define MEMSET(x, n) memset(x, n, sizeof(x))
#define MEMZERO(x) MEMSET(x, 0)
#define URU(y) (!(y % 4) && y % 100 || !(y % 400))

#define X fst
#define Y scd

using namespace std;

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

int main( void )
{
	int m;
	
	while (cin >> m, m)
	{
		pii p[200];
		
		rep (i, m)
		{
			cin >> p[i].X >> p[i].Y;
		}
		
		set<pii> s;
		int n;
		cin >> n;
		
		rep (i, n)
		{
			pii z;
			cin >> z.X >> z.Y;
			s.insert(z);
		}
		
		set<pii>::iterator it = s.begin();
		while (it != s.end())
		{
			pii a = mp((it->X - p[0].X), (it->Y - p[0].Y));
			bool flg = true;
			for (int i=1; i < m && flg; ++i)
			{
				if (!s.count(mp((p[i].X + a.X), (p[i].Y + a.Y))))
					flg = false;
			}
			if (flg)
			{
				cout << a.X << ' ' << a.Y << endl;
				break;
			}
			++it;
		}
	}
	return 0;
}

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

int main() {
  int N;
  cin >> N;
  vector<int> time(N);
  vector<int> speed(N);
  cin >> time.at(0);
  if ( N != 1 ) {
    for(int i = 1 ; i < N ; i++) { 
      int x = 0;
      cin >> x ; 
      time.at(i) = time.at(i-1) + x;
    }  
  }
  
  for(int i = 0; i < N ; i++) { 
    cin >> speed.at(i); 
  } 
  int p = time.at(N-1)*2;  
  vector<double> limit(p); 
  vector<double> resp(p); 

  for(int i = 0; i < p ; i++) {
    limit.at(i) = 100;
    double ihalf = i * 0.5;
    for(int j = 0; j < N ; j++) {
      if ( ihalf + 0.05 >= time.at(j) ) { 
        continue; 
      }
      
      double lim = 0;
      if ( j == 0 ) {
        limit.at(i) = speed.at(j);
      }
      if ( j != 0 ) {
        if ( ihalf + 0.05 >= time.at(j-1) ) {
          lim = speed.at(j);
        }
        else {
          lim = speed.at(j) + time.at(j-1) - ihalf - 0.5 ;
        }
        
        if ( lim + 0.05 < limit.at(i) ) {
          limit.at(i) = lim;
        }
      }
      if ( j == N - 1 ) {
        lim = time.at(j) - ihalf - 0.5;
        if ( lim + 0.05 < limit.at(i) ) {
          limit.at(i) = lim;
        }
      }
    }
  }
  
  double v = 0;
/*  for(int i = 0; i < p ; i++) {
    if ( v + 0.5 <= limit.at(i) + 0.05 ) {
      v += 0.5;
    }
    else if ( v + 0.05 >= limit.at(i) + 0.5 ) {
      v -= 0.5;
    }
    resp.at(i) = v;
  }
*/
  resp.at(0) = 0.5;
  for(int i = 0; i < p-1 ; i++) {
    resp.at(i+1) = min( limit.at(i+1) , resp.at(i) + 0.5 );
  }

  double range2 = 0;
  for(int i = 0; i < p ; i++) {
    if ( i == 0) {
      range2 += resp.at(i) * 0.25;
    }
    else {
      range2 += (resp.at(i) + resp.at(i-1)) * 0.25;
    }
    /*range2 += resp.at(i); */
  }
  cout << setprecision(10) << range2 << endl;
}

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

typedef long long ll;

template<typename T>
void out(T x) { cout << x << endl; exit(0); }
#define watch(x) cout << (#x) << " is " << (x) << endl

const int maxn = 1e6 + 5;
const ll mod = 1e9 + 7;

ll fac[maxn], ifac[maxn];

ll modpow(ll, ll);
ll inv(ll);
ll nck(ll, ll);
void build();
void testlib();



int n, k;
ll a[maxn];

int main() {
  ios_base::sync_with_stdio(false); cin.tie(0);  cout.tie(0);
  build();
  cin>>n>>k;
  for (int i=1; i<=n; i++) {
    cin>>a[i];
  }
  sort(a+1,a+1+n);

  ll ans = 0;

  // iterate over max
  for (int i=k; i<=n; i++) {
    ans += a[i]*nck(i-1,k-1);
    ans %= mod;
  }

  // iterate over min
  for (int i=1; i<=n-(k-1); i++) {
    ans -= a[i]*nck(n-i,k-1);
    ans %= mod;
  }

  ans %= mod;
  ans += mod;
  ans %= mod;
  cout<<ans<<endl;  

  return 0;
}

///////////////////////////////////////////////////////////////////////////////////////////////////


ll modpow(ll x, ll y) {
  x %= mod;
  ll res = 1;
  while (y > 0) {
    if (y%2 == 1) {
      res *= x;
      res %= mod;
    }
    x = x * x;
    x %= mod;
    y = y / 2;
  }
  return res;
}

ll inv(ll x) {
  assert(x != 0);
  return modpow(x, mod-2);
}

void build() {
  fac[0] = ifac[0] = 1;
  for (int i=1; i<maxn; i++) {
    fac[i] = fac[i-1] * i;
    fac[i] %= mod;
    ifac[i] = inv(fac[i]);
    ifac[i] %= mod;
  }
}

ll nck(ll n, ll k) {
  assert(n>=0 && k>=0);
  if (k > n) return 0;
  return (((fac[n] * ifac[k]) % mod) * ifac[n-k]) % mod;
}

void testlib() {
  assert(modpow(1,1) == 1);
  assert(modpow(4,2) == 16);
  assert(modpow(2,5) == 32);
  assert(fac[3] == 6);
  assert(nck(4,2) == 6);
  assert(nck(10,2) == 45);
}


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

int main(void){

	int n,k,p;

	cin >> n;
	for(int i=0;i<n;i++){
		cin >> k >> p;
		if(k>p){
			if(k%p!=0)cout << k%p << endl;
			else cout << p << endl;
		}
		else if(k<p)cout << k << endl;
		else cout << p << endl;
	}

	return 0;
}

Measured memory_bytes: 1164
import java.util.Scanner;

public class Main {
    public static void main(String[] args){
        int sum = 0;
        double ave;
        double s = 0;
        Scanner sc = new Scanner(System.in);
        while(true){
            int Length = sc.nextInt();
            if(Length == 0){
                break;
            }
            int[] number = new int[Length];
            for(int i=0; i<Length; i++){
                number[i] = sc.nextInt();
                sum += number[i];
            }
            ave = (double) sum / Length;

            for(int i=0; i<Length; i++){
                s += (number[i] - ave)*(number[i] - ave);
            }
            s /= Length;
            s = Math.sqrt(s);
            //System.out.printf("%d", number[i]);
            System.out.println(s);
            s = 0;
            sum = 0;
        }
        sc.close();
    }
}


Measured memory_bytes: 31720
#!/usr/bin/env python3

N = int(input())
# S = input()
# N, K = map(int, input().split())
# A = list(map(int, input().split()))

def main():
    if N == 1:
        print("Hello World")
    else:
        A = int(input())
        B = int(input())
        print(A + B)

if __name__ == "__main__":
    main()


Measured memory_bytes: 2940
#include<iostream>
using namespace std;
int x[999999],y,n,q,r;
main(){
cin>>n;
for(int i=0;i<n;i++){
cin>>x[i];
}
cin>>q;
for(int i=0;i<q;i++){
cin>>y;
for(int j=0;j<n;j++){
if(y==x[j]){
r++;
break;
}
}
}
cout<<r<<endl;
}

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

const ll int INF = 1e18 + 5;

int main(int argc, char const *argv[])
{
	ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    ll int n;
    cin>>n;
    ll int a[n];
    ll int pre[n] = {0};
    for(ll int i=0;i<n;i++){
    	cin>>a[i];
    	pre[i] = a[i] + pre[max(0ll,i-1)];
    }
    ll int dp[n][n] = {0};
    for(ll int k=1;k<n;k++){
    for(ll int i=0;i<(n-k);i++){
    	
    		ll int j = i+k;
    		ll int min1 = 1e14;
    		for(ll int z = i;z<j;z++){
    			ll int sum1;
    			if(i>=1)
    				sum1 = pre[z] - pre[i-1];
    			else
    				sum1 = pre[z];
    			ll int sum2 = pre[j] - pre[z];
    			min1 = min(min1,dp[i][z] + dp[z+1][j] + sum1 + sum2);
    		}
    		dp[i][j] = min1;
    		// cout<<dp[i][j]<<" "<<i<<" "<<j<<endl;
    	}
    }
    cout<<dp[0][n-1];
	return 0;
}

Measured memory_bytes: 1536
#include <iostream>
using namespace std;
 
#define MAXN 3010
 
int N;
long long dp[MAXN][MAXN];
long long a[MAXN];
long long pre[MAXN];
 
int main() {
  cin >> N;
  for (int i = 1; i <= N; i++) cin >> a[i];
  for (int i = 1; i <= N; i++) pre[i] = pre[i-1] + a[i];
  
  for (int i = 1; i <= N; i++) dp[i][i] = a[i];
  
  for (int j = 1; j < N; j++) {
    for (int i = 1; i+j <= N; i++) {
      dp[i][i+j] = max(a[i]+(pre[i+j]-pre[i])-dp[i+1][i+j],a[i+j]+(pre[i+j-1]-pre[i-1])-dp[i][i+j-1]);
    }
  }
      
      
  long long x = dp[1][N];
  long long y = pre[N] - x;
  cout << x-y << endl;
}

Measured memory_bytes: 70016
# Template 1.0
import sys, re
from collections import deque, defaultdict, Counter, OrderedDict
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, gcd
from heapq import heappush, heappop, heapify, nlargest, nsmallest
def STR(): return list(input())
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def list2d(a, b, c): return [[c] * b for i in range(a)]
def sortListWithIndex(listOfTuples, idx):   return (sorted(listOfTuples, key=lambda x: x[idx]))
def sortDictWithVal(passedDic):
    temp = sorted(passedDic.items(), key=lambda kv: (kv[1], kv[0]))
    toret = {}
    for tup in temp:
        toret[tup[0]] = tup[1]
    return toret
def sortDictWithKey(passedDic):
    return dict(OrderedDict(sorted(passedDic.items())))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

n = INT()
set1 = set()
while (n != 0):

    set1.add(input())


    n-=1
print(len(set1))

Measured memory_bytes: 31660
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <stack>
using namespace std;
typedef long long ll;
const ll INF = 1e9 + 7;
int main(void) {
	string s, t;
	cin >> s >> t;
	cout << t + s << endl;
	return 0;
}

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

int N;
long long int W;
long long int weight[101];
long long int value[101];
long long int DP[100001]={};
const long long int INF =1000000001;


long long int knapsack(){
	long long int ret=0;
	for(int i=1;i<=100000;i++){
		DP[i]=INF;
	}
	for(int i=1;i<=N;i++){
		for(long long int j=100000;j>=value[i];j--){
			if(DP[j-value[i]]!=INF){
				DP[j]=min(DP[j],DP[j-value[i]]+weight[i]);
				if(DP[j]<=W){
					ret=max(ret,j);
				}
			}
		}
	}
	return ret;
}

int main(){
	cin>>N>>W;
	for(int i=1;i<=N;i++){
		cin>>weight[i]>>value[i];
	}
	cout<<knapsack()<<"\n";
	return 0;
}

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

int main() {
    //
    long long num;
    long long waru = 1000000007;
    long long ans = 0;
    cin >> num;

    long long a = 1;
    long long bc = 1;
    long long d = 1;
    // ans += pow(10, num);
    for (int i = 0; i < num; i++) {
        a *= 10;
        a %= waru;
    }
    // ans -= pow(9, num);
    // ans -= pow(9, num);
    for (int i = 0; i < num; i++) {
        bc *= 9;
        bc %= waru;
    }
    // ans += pow(8, num);
    for (int i = 0; i < num; i++) {
        d *= 8;
        d %= waru;
    }

    ans = a - bc * 2 + d;
    ans %= waru;

    if (ans < 0) ans += waru;

    cout << ans << endl;

    //
}


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

using namespace std;

#define rep(i, n) for(int i = 0; i < (int)n; ++i)
#define FOR(i, a, b) for(int i = a; i < (int)b; ++i)
#define rrep(i, n) for(int i = ((int)n - 1); i >= 0; --i)

using ll = long long;
using ld = long double;

const ll INF = 1e18;
const int Inf = 1e9;
const double EPS = 1e-9;
const ll MOD = 1e9 + 7;

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(0);
	string s;
	cin >> s;
	bool ok = true;
	rep (i, 4) {
	  if (i - 1 >= 0) {
		if (s[i] == s[i - 1]) ok = false;
	  }
	  if (i + 1 <= 3) {
		if (s[i] == s[i + 1]) ok = false;
	  }
	}
	cout << (ok ? "Good" : "Bad") << endl;
    
    return 0;
}



Measured memory_bytes: 3620
import itertools,math,numpy as np
def I(): return int(input())
def LI(): return list(map(int,input().split()))
N = I()
xy = np.array([LI() for _ in range(N)])
sum_norm = 0
dict_norm = {}
for a in itertools.permutations(range(N)):
    for i in range(len(a)-1):
        vector = xy[a[i+1]]-xy[a[i]]
        if not tuple(vector) in dict_norm:
            dict_norm[tuple(vector)] = np.linalg.norm(vector)
        sum_norm += dict_norm[tuple(vector)]
print(sum_norm/math.factorial(N))


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

int main(){
    int a,b;
    cin>>a>>b;
    if(a>=13){
        cout<<b<<endl;
    }
    else if(a>=6){
        cout<<b/2<<endl;
    }
    else{
        cout<<0<<endl;
    }
    return 0;
}


Measured memory_bytes: 888
N,K=gets.split.map &:to_i
W=$<.map &:to_i
l=0
r=$$**3
m=r/2
def a m
i=k=s=0
while i<N
return if W[i]>m
s+=W[i]
if m<s
s=W[i]
k+=1
end
i+=1
end
k<K
end
while l+1<r
a(m)?r=m :l=m
m=(l+r)/2
end
p r

Measured memory_bytes: 7028
#define _GLIBCXX_DEBUG
#define rep(i,n) for(int i=0;i<n;i++)
#include <bits/stdc++.h>
#include <numeric>
using namespace std;
typedef long long ll;
const int mod= 1e+9+7;

bool judge(string t,char z){
    for(int i=0;i<t.size();i++){
        if(t[i]!=z)return false;
    }
    return true;
}

int main() {
    string s; cin>>s;
    int mn =100000;
    for(char c='a';c<='z';c++){
        string t=s;
        for(int i=0;;i++){
            if(judge(t,c)){
                mn = min(mn,i);
                break;
            }
        string nt;
        for(int j=0;j<t.size()-1;j++){
            if(t[j]==c||t[j+1]==c)nt+=c;
            else nt+=t[j];
        }
        t=nt;
        }

    }
    cout<<mn<<endl;

}



Measured memory_bytes: 256
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <fstream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;
const double PI = acos(-1.0);

int main()
{
	int n, m, k, t;
	cin >> n >> m;

	vector<int> p(m);
	vector<vector<int> > c(m, vector<int>(n, 0));

	for(int i = 0; i < m; i++) {
		cin >> k;
		for(int j = 0; j < k; j++) {
			cin >> t;
			c[i][t-1] = 1;
		}
	}
	for(int i = 0; i < m; i++) {
		cin >> p[i];
	}

	int al = (int)pow(2.0, (double)n);
	int res = 0;
	for(int i = 0; i < al; i++) {
		int ret = 1;
		for(int j = 0; j < m; j++) {
			int sw = 0;
			for(int l = 0; l < n; l++) {
				sw ^= c[j][l] & (i >> l);
			}
			if(sw != p[j]) {
				ret = 0;
				break;
			}
		}
		if(ret == 1) {
			res++;
		}
	}

	cout << res << endl;

    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define ios ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
using namespace std;
int a[200006],b[200006];
int n1[200006],n2[200006];
int min(int a,int b)
{
	return a>b?b:a;
}
int main()
{
	ios;
	int len;
	int l=0,r=0;
	cin>>len;
	for(int i=1;i<=len;++i)
	{
		cin>>a[i];
		n1[a[i]]++;
	}
	for(int i=len;i>0;--i)
	{
		cin>>b[i];
		n2[b[i]]++;
	}
	int flag=0;
	for(int i=1;i<=len;++i)
	{
		if(a[i]==b[i]&&!flag){l=i;r=i;flag=1;}
		else if(a[i]==b[i])
		{
			r=i;
		}
	}
	if(l==0){
		cout<<"Yes\n"<<b[1];
		for(int i=2;i<=len;++i){cout<<' '<<b[i];}
		cout<<'\n';
		return 0;
	}
	if(len-n2[a[l]]<r-l+1)cout<<"No"<<'\n';
	else 
	{
		int l1=l;
		int goal=a[l];
		for(int i=1;i<l;++i)
		{
			if(l1>r)break;
			if(b[i]!=goal&&a[i]!=goal){b[l1]+=b[i];b[i]=b[l1]-b[i];b[l1]-=b[i];l1++;}
		}
		for(int i=r+1;i<=len;++i)
		{
			if(l1>r)break;
			if(b[i]!=goal&&a[i]!=goal){b[l1]+=b[i];b[i]=b[l1]-b[i];b[l1]-=b[i];l1++;};
		}
		if(l1>r)
		{
			cout<<"Yes\n"<<b[1];
			for(int i=2;i<=len;++i){cout<<' '<<b[i];}
			cout<<'\n';
		}
		else cout<<"No"<<'\n';
	}
} 

Measured memory_bytes: 6744
import std.stdio;
import std.algorithm;
import std.string;
import std.range;
import std.array;
import std.conv;
import std.complex;
import std.math;
import std.ascii;
import std.bigint;
import std.container;
import std.typecons;

auto readInts() {
	return array(map!(to!int)(readln().strip().split()));
}
auto readInt() {
	return readInts()[0];
}
auto readLongs() {
	return array(map!(to!long)(readln().strip().split()));
}
auto readLong() {
	return readLongs()[0];
}

const real eps = 1e-10;

void main(){
	while(true) {
		auto n = readInt();
		if(n == 0) {
			return;
		}
		auto c = [[0,0]];
		for(int i = 1; i < n; ++i) {
			auto nd = readInts();
			auto dx = [[-1, 0], [0, -1], [1, 0], [0, 1]];
			c ~= c[nd[0]].dup;
			c.back[] += dx[nd[1]][];
		}
		int b, u, l, r;
		foreach(ci; c) {
			b = min(b, ci[1]);
			u = max(u, ci[1]);
			l = min(l, ci[0]);
			r = max(r, ci[0]);
		}
		writeln(r-l+1, " ", u-b+1);
	}
}

Measured memory_bytes: 3416
/**
 * code generated by JHelper
 * More info: https://github.com/AlexeyDmitriev/JHelper
 * @author jcg
 */

#include <iostream>

#include <iostream>
#include <vector>
#include <algorithm>

class ESequenceDecomposing
{
public:
    void solve(std::istream& in, std::ostream& out)
    {
        int N;
        in >> N;

        std::vector<int> a;
        for (int i = 0; i < N; ++i)
        {
            int x;
            in >> x;
            if (a.empty() || a.back() >= x)
                a.emplace_back(x);
            else *std::upper_bound(a.begin(), a.end(), x, std::greater<int>()) = x;
        }
        out << a.size() << '\n';
    }
};


int main()
{
    std::ios_base::sync_with_stdio(0);
    std::istream& in(std::cin);
    std::ostream& out(std::cout);
    in.tie(0);
    ESequenceDecomposing solver;
    solver.solve(in, out);
    return 0;
}


Measured memory_bytes: 892
#include <bits/stdc++.h>
using namespace std;
int main () {
    int n;
    cin >> n;
    map<int, int> mp;
    for (int i = 0; i < n; i++) {
        int a;
        cin >> a;
        mp[a]++;
    }
    int ans = 0;
    for (auto x: mp) {
        if (x.first < x.second) {
            ans += x.second - x.first;
        }
        else if (x.first > x.second) {
            ans += x.second;
        }
    }
    cout << ans << endl;
}

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

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

  sort(a, a + n);
  long long acc[n];
  acc[0] = a[0];
  for (int i=1; i<n; i++) {
    acc[i] = acc[i-1] + a[i];
  }
  int cnt = n;
  for (int i=0; i<n-1; i++) {
    if (2 * acc[i] < a[i+1]) {
      cnt = n - i -1;;
    }
  }
  cout<<cnt<<endl;
}

Measured memory_bytes: 1408
from sys import stdin
N=int(stdin.readline().rstrip())
D,X=[int(x) for x in stdin.readline().rstrip().split()]

data=[]
for i in range(N):
    data.append(int(input()))

ans=X
for j in data:
    if D % j == 0:
        ans += (D/j)
    else:
        ans += 1
        ans += (D//j)

print(int(ans))

Measured memory_bytes: 3064
#include<iostream>
using namespace std;
int main(void)
{
  long long n, a, b;
  cin>>n>>a>>b;
  long long pre;
  long long next;
  long long ans=0;
  cin>>pre;
  for(int i=0; i<n-1; i++)
    {
      cin>>next;
      long long x=(next-pre)*a;
      ans+=min(x, b);
      pre=next;
    }
  cout<<ans<<endl;
  return 0;
}


Measured memory_bytes: 384
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, int> pli;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
#define rep(i,a,n) for(int i=a;i<n;++i)
#define per(i,a,n) for(int i=n-1;i>=a;--i)
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define fi first
#define se second
#define sz(x) ((int)x.size())
#define all(x) begin(x), end(x)
#define rall(x) rbegin(x), rend(x)
const ll mod=1000000007; // 998244353 = (119<<23)+1
ll powmod(ll a,ll b) {ll res=1;a%=mod;assert(b>=0);for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
ll gcd(ll a,ll b) {return b?gcd(b,a%b):a;}
// head
ll a,b;
ll f(ll x) {
	ll s=x&3LL;
	if(s==0) return x;
	if(s==1) return 1;
	if(s==2) return x+1LL;
	return 0;
}
int main() {
	  ios::sync_with_stdio(false);
  	cin.tie(0);
		cin>>a>>b;
		ll ans=f(b)^f(a-1);
		cout<<ans;
		return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <cstdio>

using namespace std;

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

int main() {
	int n, m;
	int mass[1000], s[1000];

	while (cin >> n >> m, n && m) {
		REP(i,n) scanf("%d", &mass[i]);
		REP(i,m) scanf("%d", &s[i]);

		int l = 0, i = 0;
		while (l < n - 1) {
			l += s[i++];
			if (l >= n - 1)
				break;
			l += mass[l];
		}

		cout << i << endl;
	}

	return 0;
}

Measured memory_bytes: 1252
type t = { v : int; w : int }

let () =
  let (n, w) = Scanf.scanf "%d %d " (fun n w -> n, w) in
  let a = Array.init n (fun _ -> Scanf.scanf "%d %d " (fun v w -> { v; w })) in
  let z = (100*n + 1) in
  let dp = Array.make z (w + 1) in
  dp.(0) <- 0;
  for i = 0 to n - 1 do
    for j = z - 1 downto a.(i).v do
      if dp.(j - a.(i).v) + a.(i).w < dp.(j) then dp.(j) <- dp.(j - a.(i).v) + a.(i).w
    done
  done;
  let rec print i =
    if i < 0 then assert false
    else if dp.(i) <= w then Printf.printf "%d\n" i
    else print (i - 1) in
  print (z - 1)

Measured memory_bytes: 2536
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#define FOR(i,a,b) for(int i=a; i<b; i++)
#define rep(i,N) FOR(i,0,N)

/*問題文
N枚のカードがあります.i枚目のカードには,aiという数が書かれています.
 Alice と Bob は, これらのカードを使ってゲームを行います. ゲームでは, Alice と Bob が交互に 1 枚ずつカードを取っていきます.
 Alice が先にカードを取ります.2 人がすべてのカードを取ったときゲームは終了し, 取ったカードの数の合計がその人の得点になります.
 2 人とも自分の得点を最大化するように最適な戦略を取った時, Alice は Bob より何点多く取るか求めてください.
 */

using namespace std;

int main(){

    int N;
    cin >> N;
    vector<int> cards(N);
    rep(i,N){
        cin >> cards.at(i);
    }

    sort(cards.begin(), cards.end(), greater<int>());
/*
    rep(i,N){
        cout << cards.at(i);
    }
*/
    int Alice=0;
    int Bob=0;

    for(int i=0; i<N; i = i+2 ){
            Alice += cards.at(i);
            if(i+1 < N){
                Bob += cards.at(i+1);
            }
    }

    cout << Alice-Bob << endl;

    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define sz(a) a.size()
#define re return
#define all(a) a.begin(),a.end()
#define int long long
using namespace std;
const int dx[4]={-1,1,0,0};
const int dy[4]={0,0,-1,1};
inline __int128 read(){
    __int128 x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-')
            f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=x*10+ch-'0';
        ch=getchar();
    }
    return x*f;
}
inline void print(__int128 x){
    if(x<0){
        putchar('-');
        x=-x;
    }
    if(x>9)
        print(x/10);
	putchar(x%10+'0');
}
signed main()
{
	int n;
	cin>>n;
	int lu=1e16,rd=-1;
	int ld=-1e16,ru=1e16;
	while (n--){
		int x,y;
		cin>>x>>y;
//		cout<<x<<' '<<y<<' '<<x-y<<'\n';
		lu=min(lu,x+y);
		rd=max(rd,x+y);
		ld=max(ld,x-y);
		ru=min(ru,x-y);
//		cout<<lu<<' '<<rd<<' '<<ld<<' '<<ru<<'\n';
	}
//	cout<<rd<<' '<<lu<<' '<<ld<<' '<<ru;
	cout<<max(rd-lu,ld-ru);
	re 0;
}


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

// 型定義
typedef long long ll;
typedef pair<ll, ll> P;

// forループ
#define REP(i,n) for(ll i=0; i<(ll)(n); ++i)

// 定数宣言
const int INF = 1e9;
const int MOD = 1e9+7;
const ll LINF = 1e18;

// グラフ表現
using Graph = vector<vector<int>>;

// グラフの辺表現
using Edge = map<pair<int,int>,int>;

// n次元配列の初期化。第２引数の型のサイズごとに初期化していく。
template<typename A, size_t N, typename T>
void Fill(A (&array)[N], const T &val){
    std::fill( (T*)array, (T*)(array+N), val );
}

// 最大公約数
ll gcd(ll a,ll b){
   if (a%b == 0) return(b);
   else return(gcd(b, a%b));
}

// 最小公倍数
ll lcm(ll a, ll b){
    return a*b/gcd(a, b);
}

int main()
{
    cout << fixed << setprecision(15);
    ll N, M, Q;
    cin >> N >> M >> Q;

    vector<vector<ll>> A(N+1, vector<ll>(N+1, 0));
    REP(i, M){
        ll l;
        ll r;
        cin >> l >> r;
        A[l][r]++;
    }

    // REP(i, N){
    //     REP(j, N){
    //         cout << A[i][j];
    //     }
    //     cout << endl;
    // }

    // 累積カウント用
    vector<vector<ll>> B(N+1, vector<ll>(N+1, 0));
    REP(i, N+1){
        REP(j, N+1){
            if(j == 0){
                B[i][j] = A[i][j];
            }
            else{
                B[i][j] = B[i][j-1] + A[i][j];
            }
        }
    }

    REP(i, Q){
        ll p,q;
        cin >> p >> q;

        ll ans = 0;
        for(ll j=p; j<=q; j++){
            ans += B[j][q] - B[j][p-1];
        }
        cout << ans << endl;
    }
    return 0;
}

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

int main() {
  int N;
  cin >> N;
  vector<string> blue(N);
  for (int i = 0; i < N; i++){
  	cin >> blue.at(i);
  }
  
  int M;
  cin >> M;
  vector<string> red(M);
  for (int j = 0; j < M; j++){
  	cin >> red.at(j);
  }
  
  int say = 0;
  for (int i = 0; i < N; i++){
  	int score =0;
    
    for (int j = 0; j < N; j++){
    if (blue.at(i) == blue.at(j)){
        	score ++;
        }
    }
    
    for (int k = 0; k < M; k++) {
    	if (blue.at(i) == red.at(k)){
        	score --;
        }
    }
    
    if (score > say){
    	say = score;
    }
    
  }
  
  cout << say;
  
  
  
}

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

int main()
{
	string s;
	cin >> s;
	for (char c = 'a'; c <= 'z'; c++) {
		if (count(s.begin(), s.end(), c) == 0) {
			cout << c << endl;
			return 0;
		}
	}
	cout << "None" << endl;
	return 0;
}

Measured memory_bytes: 512
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
    int n;
    cin>>n;
    string s;
    cin>>s;
    stack<char>a;
    for(int i = 0 ; i < n ; i++){
        if(!a.empty()&&a.top()==s[i])continue;
        a.push(s[i]);
    }
    int y=a.size();
    cout<<y;

    return 0;
}

Measured memory_bytes: 512
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define pb push_back
#define inf 1e9
#define mod 1000000007
#define ff first
#define ss second

map<int, int> m1;

void factors(int n)
{
	for (int i = 2; i * i <= n; i++)
	{
		if (n % i == 0)
		{
			while (n % i == 0)
			{
				m1[i]++;
				n = n / i;
			}
		}
	}
	if (n > 1)
		m1[n] = 1;
}

void solve()
{
	int n;
	cin >> n;
	factors(n);

	int cnt = 0;
	for (auto i : m1)
	{
		int x = 0, y = 0;
		while (x + y + 1 <= i.ss)
		{
			x++;
			y += x;
		}
		cnt += x;
	}
	cout << cnt << "\n";

}

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


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

int main(){
  string s;
  cin >> s;
  int ans = 0;
  if(s.at(0) == '1'){
    ans++;
  }
  if(s.at(1) == '1'){
    ans++;
  }
  if(s.at(2) == '1'){
    ans++;
  }
  cout << ans << endl;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long int lli;
#define vv vector<lli>
#define vp vector<pair<lli,lli>>
#define vpp vector<pair<lli,pair<lli,lli>>>
#define lims(w) (w).begin(),(w).end()
#define rlims(w) (w).rbegin(),(w).rend()
#define pb push_back
#define mp make_pair
#define f(i,a,b) for(lli i=a;i<b;i++)

int main()
{
	lli n;
	cin>>n;
	vv a;
	lli val;

	f(i,0,n)
	{
		cin>>val;
		a.pb(val);
	}

	sort(lims(a));
	lli ans = a.back();
	a.pop_back();
	lli ctr = 0;
	
	f(i,0,n-2)
	{
		if(ctr == 2)
		{
			a.pop_back();
			ctr = 1;
			ans += a.back();
			continue;
		}

		if(ctr == 0 || ctr == 1)
		{
			ans += a.back();
			ctr++;
		}
	}

	cout<<ans<<endl;
	return 0;
}


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

using namespace std;

int main(void){
  ll Q;
  string s;
  cin >> s >> Q;
  int n = s.size();

  int t, f;
  char c;
  vector<char> hoge(600010);
  int head = 300003, tail = 300003 + n - 1;

  for (int i = 0; i < n; i++){
    hoge[head + i] = s[i];
  }


  int oe = 0;
  for (int i = 0; i < Q; i++){
    cin >> t;
    if (t == 1){
      oe = 1 - oe;
    }
    else {
      cin >> f >> c;
      if ((2 - f) != oe){
        head--;
        hoge[head] = c;
      }
      else {
        tail++;
        hoge[tail] = c;
      }
    }
  }

  if (!oe){
    for (int i = head; i <= tail; i++){
      cout << hoge[i];
    }
  }
  else {
    for (int i = tail; i >= head; i--){
      cout << hoge[i];
    }
  }
  cout << endl;

  return 0;
}


Measured memory_bytes: 1408
H, W = map(int, input().split())
costs = []
wall = []

for _ in range(10):
  costs.append(list(map(int, input().split())))
  
for _ in range(H):
  wall.append(list(map(int, input().split())))
  

for k in range(10):
  for i in range(10):
    for j in range(10):
      costs[i][j] = min(costs[i][j], costs[i][k] + costs[k][j])

total_cost = 0

for i in range(H):
  for j in range(W):
    n = wall[i][j]
    if n == -1:
      continue
    total_cost += costs[n][1]
    
print(total_cost)


Measured memory_bytes: 41564
#include <bits/stdc++.h>
using namespace std;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
using ll = long long;
using P = pair<ll, ll>;
ll GCD(ll a, ll b) { return b?GCD(b, a%b):a; }
ll LCM(ll a, ll b) { return a/GCD(a, b)*b; }

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

int h, w, n;
struct xydata {
    int x; int y;
};
struct xyldata {
    int xx; int yy; int dist;
};

vector< vector<char> > cmap(1010, vector<char>(1010, '.'));

int bfs(vector< vector<bool> > &xmap, xydata first, xydata goal) {
    int len = 0;
    queue<xyldata> que;
    xyldata lfirst; lfirst.xx = first.x; lfirst.yy = first.y;
    lfirst.dist = 0;
    que.push(lfirst);
    xmap.at(first.y).at(first.x) = true;

    while(!que.empty()) {
        xyldata now = que.front(); que.pop();
        if(now.xx == goal.x && now.yy == goal.y) {
            len = now.dist;
            break;
        }
        for(int i = 0; i < 4; ++i) {
            int nx = now.xx+dx[i]; int ny = now.yy+dy[i];
            int ndist = now.dist+1;
            if(nx >= 0 && nx < w && ny >= 0 && ny < h) {
                if(cmap.at(ny).at(nx) != 'X') {
                    if(!xmap.at(ny).at(nx)) {
                        xmap.at(ny).at(nx) = true;
                        xyldata next;
                        next.xx = nx; next.yy = ny; next.dist = ndist;
                        que.push(next);
                    }
                }
            }
        }
    }
    return len;
}

int main() {
    cin >> h >> w >> n;
    vector<xydata> chese(10);
    xydata start;
    for(int i = 0; i < h; ++i) {
        for(int j = 0; j < w; ++j) {
            cin >> cmap.at(i).at(j);
            xydata indata;
            if(isdigit(cmap.at(i).at(j))) {
                int no = cmap.at(i).at(j) - '0';
                no--;
                indata.x = j; indata.y = i; chese.at(no) = indata;
            }else if(cmap.at(i).at(j) == 'S') {
                start.x = j; start.y = i;
            }
        }
    }

    ll sum = 0;
    for(int i = 0; i < n; ++i) {
        vector< vector<bool> > cvisit(h, vector<bool>(w, false));
        if(i == 0) sum += bfs(cvisit, start, chese.at(i));
        else sum += bfs(cvisit, chese.at(i-1), chese.at(i));
    }
    cout << sum << endl;
}


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

using namespace std;

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

    int n,ans=0;
    cin >> n;
    ans+=min(n,9);
    if(n > 99)
    {
        ans+=min(n-99,999-99);
    }
    if(n > 9999)
    {
        ans+=min(n-9999,99999-9999);
    }
    cout << ans;
    return 0;
}


Measured memory_bytes: 256
//全くわからんので解き方を見てみる
//行列dpを作って、dp[i][j]はi~jのかけ算をした際の最小の回数
//これを順に計算すれば確かに最小のものは出そう

#include<iostream>
#include<vector>
#include<utility>
#include<algorithm>

using namespace std;

int main(){
  int INF=1000000000;
  int n;cin >> n;
  vector< vector<int> > dp(n,vector<int>(n,INF));
  //vector< vector< pair<int,int> > > x(n,vector< pair<int,int> >(n,make_pair(0,0)));
  vector< pair<int,int> > m(n);
  for(int i=0;i<n;i++){
    int r,c;cin >> r >> c;
    m[i]=make_pair(r,c);
  }

  for(int i=0;i<n;i++){dp[i][i]=0;}

  for(int l=0;l<n;l++){//長さのループ
    for(int i=0;i<n-l;i++){//行のループ
      if(l==0){dp[i][i+l]=0;}
      for(int j=i;j<i+l;j++){//更新のループ(d[i][i+l])
        dp[i][i+l]=min({dp[i][i+l],dp[i][j]+dp[j+1][i+l]+m[i].first*m[j].second*m[i+l].second});
      }
    }

  }
  /*
  for(int i=0;i<n;i++){
    for(int j=0;j<n;j++){
      cout << dp[i][j] << " ";
    }
    cout << endl;
  }
  */
  cout<< dp[0][n-1] << endl;

}



Measured memory_bytes: 3180
#include<stdio.h>
int main()
{
 int a;
 int b;
 int c;
 scanf("%d %d %d",&a,&b,&c);
 if(a<b&&b<c)
 {
    printf("Yes\n");
 }
 else
 {
     printf("No\n");
 }
return 0;
}

Measured memory_bytes: 580
//47
#include<iostream>
#include<algorithm>

using namespace std;

int main(){
  int t;
  cin>>t;
  while(t--){
    int n,m;
    cin>>n>>m;
    string t[50000];
    for(int i=0;i<n;i++){
      cin>>t[i];
    }
    string s[50000];
    for(int i=0;i<m;i++){
      cin>>s[i];
    }
    int i;
    for(i=0;i<=1;i++){
      int x=n-1-i;
      int j;
      for(j=m-1;j>=0;j--){
	if(x<0||n<=x)break;
	static string sn[]={"C", "C#", "D", "D#", "E", "F", "F#", "G", "G#", "A", "A#", "B"};
	int c=find(sn,sn+12,t[x])-sn;
	if(sn[c]==s[j]){
	  x--;
	}else if(sn[(c+1)%12]==s[j]){
	  x-=2;
	}else if(sn[(c+11)%12]==s[j]){
	  x++;
	}else{
	  break;
	}
      }
      if(j<0&&x==-1){
	break;
      }
    }
    cout<<((i>1)?"No":"Yes")<<endl;
  }
  return 0;
}

Measured memory_bytes: 6680
from collections import Counter

def main():
    N = int(input())
    a = Counter(map(int, input().split()))
    a1, a2, a3 = a.get(1, 0), a.get(2, 0), a.get(3, 0)
    a123 = a1 + a2 + a3 + 1
    u = [[0.0] * (a123 - c2) for c2 in range(a123)]
    v = [[0.0] * (a123 - c2) for c2 in range(a123)]
    t1 = 0.0
    v2 = v[0]
    for c1 in range(1, a123):
        v2[c1] = t1 = N / c1 + t1
    for c2 in range(1, a123):
        v2 = v[c2]
        for c1, t2 in zip(range(301 - c2), v[c2 - 1][1:]):
            v2[c1] = t1 = (N + c1 * t1 + c2 * t2) / (c1 + c2)

    for c3 in range(1, a3 + 1):
        u, v = v, u
        v2 = v[0]
        for c1, t3 in zip(range(a123 - c3), u[1]):
            v2[c1] = t1 = (N + c1 * t1 + c3 * t3) / (c1 + c3)
        for c2 in range(1, a123 - c3):
            v2 = v[c2]
            c23 = c2 + c3
            for c1, t2, t3 in zip(range(a123 - c3 - c2), v[c2 - 1][1:], u[c2 + 1]):
                v2[c1] = t1 = (N + c1 * t1 + c2 * t2 + c3 * t3) / (c1 + c23)

    print(v[a2][a1])
main()


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

int main() {
  long N, A, B, C, Q, sum = 0;
  map<int, int> M;
  cin >> N;
  while (N-- && cin >> A) M[A]++, sum += A;
  cin >> Q;
  while (cin >> B >> C) {
    cout << (sum += (C - B) * M[B]) << "\n";
    M[C] += M[B], M[B] = 0;
  }
}

Measured memory_bytes: 8020
import math

N, K = map(int, input().split())
A = list(map(int, input().split()))

#  にぶたん！ 半開区間二分探索は正義

def calc(x):
    count = 0
    for a in A:
        count += (a - 1) // x

    return count <= K

A.sort(reverse=True)

r = 10 ** 9
l = 0

while abs(r - l) > 1:
    mid = (r + l) // 2
    
    if calc(mid):
        r = mid
    else:
        l = mid

print(r)


Measured memory_bytes: 31140
#include <bits/stdc++.h>
//#define int long long

using namespace std;
using LL = long long;
using P = pair<int, int>;

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

#define pb(a) push_back(a)
#define all(x) (x).begin(),(x).end()

const int INF = (int)1e9;
const LL INFL = (LL)1e18;
const int MOD = 1e9 + 7;

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

    int n;
    cin >> n;
    
    int ans = 0;
    for(int i = 0; i < 9; i++){
        if(n & (1 << i)) ans = (1 << i);
    }

    cout << ans << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
int main () {
  int N;
  cin >> N;
  
  int a1, a2, a3, a4;
  a1 = N / 1000;
  a2 = N % 1000 / 100;
  a3 = N % 100 / 10;
  a4 = N % 10;
  if (a2 == a3){
    if (a1 == a2 || a3 == a4) cout << "Yes" << endl;
    else cout << "No" << endl;
  }
    else cout << "No" << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <deque>

using namespace std;
int main(void){
    deque<int> a;
    int i,o,x,q;
    bool d;//0 front 1 back
    
    cin>>q;
    for(i=0;i<q;i++){
        cin>>o;
        if(o==0){
            cin>>d>>x;
            if(d){
                a.push_back(x);   
            }
            else{
                a.push_front(x);
            }
        }
        else if(o==1){
            cin>>x;
            cout<<a[x]<<endl;
        }
        else{
            cin>>d;
            if(d){
                a.pop_back();   
            }
            else{
                a.pop_front();
            }
        }
    }
    
    return 0;
}



Measured memory_bytes: 4532
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline int read()
{
	int out=0,fh=1;
	char jp=getchar();
	while ((jp>'9'||jp<'0')&&jp!='-')
		jp=getchar();
	if (jp=='-')
		fh=-1,jp=getchar();
	while (jp>='0'&&jp<='9')
		out=out*10+jp-'0',jp=getchar();
	return out*fh;
}
int main()
{
	int n=read();
	cout<<(1LL*n*(n-1)/2)<<endl;
	return 0;
}


Measured memory_bytes: 256
#include <stdio.h>
#include <math.h>
#include <string.h>
int main(void)
{
  int N, K;
  scanf("%d %d", &N, &K);
  char S[N];
  scanf("%s", S);
  S[K-1] = S[K-1] + 0x20;
  printf("%s", S);
 return 0;
}

Measured memory_bytes: 128
#include<stdio.h>
 
int main(){
	int a, b, i, count = 0, s = 0;
	while(scanf("%d %d", &a, &b) != 0){
		if(a == 0 || b == 0) break;
		if(s == 1) printf("\n");
		for(i = a; i <= b; i++){
			if(i % 400 == 0){
				printf("%d\n", i);
				count = 1;
			}else if(i % 100 == 0) continue;
			else if(i % 4 == 0){
				printf("%d\n", i);
				count = 1;
			}
		}
		if(count == 0) printf("NA\n");
		count = 0;
		s = 1;
	}
	return 0;
}

Measured memory_bytes: 616
#include<bits/stdc++.h>
#pragma GCC optimize("Ofast")
using namespace std;
#define ll long long

unordered_map<ll,list<pair<ll,ll>>> graph;
void add(ll a, ll b,ll dist)
{
    graph[a].push_back({b,dist});
    graph[b].push_back({a,dist});
}


ll dijkstra(ll src,ll n)
{
    unordered_map<ll,ll> dist;
    for(auto i:graph)
    {
        dist[i.first]=INT_MAX;
    }
    dist[src]=0;
    set<pair<ll, ll> > s;
    s.insert({0,src});
    
    while(!s.empty())
    {
        auto p = *(s.begin());
        
        ll d = p.first;
        ll node = p.second;
        
        s.erase(p);
        for(auto i:graph[node])
        {
            if((i.second + d) < (dist[i.first]))
            {
                if(s.find({dist[i.first],i.first})!=s.end())
                {
                    s.erase({dist[i.first],i.first});
                }
                
                dist[i.first] = d + i.second;
                s.insert({dist[i.first],i.first});
            }
        }
        
    }
    
    return dist[n];
}


int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    
    // ll t;cin>>t;while(t--)
    {
    
        ll a;cin>>a;
        unordered_map<ll,ll> mp;
        for(ll i=1;i<=9;i++)
        {
            for(ll j=1;j<=9;j++)
            {
                mp[i*j]=1;
            }
        }
        if(mp[a]==1)
            cout<<"Yes\n";
        else
            cout<<"No\n";
    }
    
}

Measured memory_bytes: 256