akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
#include<iostream>
#include<string>
#include<vector>
#define ll long long
#define MAX 1000003
#define IOS ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)
#define endl "\n"
using namespace std;

int main(){
	IOS;
	string s; cin>>s;
	map<char,int> mp;
	//cin>>s;
	if(s.length()!=4){
		cout<<"No";	
		return 0;
	}
	else {
		for(int i=0;i<4;i++)
			mp[s[i]]++;
		if(mp.size()!=2){
			cout<<"No";
			return 0;
		}
		for(int i=0;i<4;i++){
			if(mp[s[i]]==2)
				continue;
			else {
				cout<<"No";
				return 0;
			}
		}
		cout<<"Yes";
	}
return 0;
}

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

int main(){
    int A,B,K; cin >> A >> B >> K;
    int cnt = 0;
    int d = min(A,B);
    int ans = 1;
    while(cnt < K){
        if(A%d == 0 && B%d==0){
            cnt++;
            ans = d;
        }
        d--;
    }
    cout << ans << endl;
}



Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
vector<int> books[10];
int main(){
      int n,k,i,j,tm1,tm2,dp[15][2005];
      cin>>n>>k;
      for(i=0;i<n;i++){
            cin>>tm1>>tm2;
            books[tm2].push_back(tm1);
      }
      for(i=0;i<=10;i++)sort(books[i].begin(),books[i].end());
      for(i=0;i<=10;i++)for(j=0;j<=k;j++)dp[i][j]=-1;
      dp[0][0] = 0;
      for(i=0;i<10;i++){
            for(j=0;j<=k;j++){
                  if(dp[i][j]==-1)continue;
                        int ct = 0;
                        for(int x=1;x<=books[i+1].size();x++){
                              if(j+x>k)break;
                              ct += books[i+1][books[i+1].size()-x];
                              dp[i+1][j+x] = max(dp[i+1][j+x],dp[i][j]+ct+(x-1)*x);
                        }
                        dp[i+1][j]=max(dp[i+1][j],dp[i][j]);
            }
      }
      cout << dp[10][k]<<endl;
}

Measured memory_bytes: 1328
object Main extends App  {

  import scala.io.StdIn.readLine
  readLine()
  val stamps = readLine().toList

  println(OXCount(stamps))

  def OXCount(stamps: List[Char], count: Int = 0): Int = stamps match {
    case x1 :: x2 :: xs if x1 != x2 => OXCount(xs, count + 1)
    case _ :: x2 :: xs  => OXCount(x2::xs, count)
    case _ => count
  }
}


Measured memory_bytes: 51792
x, n = map(int, input().split())
p = list(map(int, input().split()))
ans = 0
m = float('inf')
for i in range(102):
    if i in p:
        continue
    else:
        if abs(x - i) < m:
            ans = i
            m = abs(x - i)
print(ans)


Measured memory_bytes: 9172
H, W = map(int, input().split())
a = []
tmp = []
for i in range(H):
    tmp = list(map(str,input().split()))
    a.append(list(tmp[0]))

for i in range(H):
    for j in range(W):
        if a[i][j] == '#':
            if j - 1 >= 0 and a[i][j - 1] == "#":
                continue
            elif j + 1 < W and a[i][j + 1] == "#" :
                continue
            elif i + 1 < H and a[i + 1][j] == "#" :
                continue
            elif i - 1 >= 0 and a[i - 1][j] == "#":
                continue
            else:
                print("No")
                exit()
 
print("Yes")

Measured memory_bytes: 3064
#include<stdio.h>

int main() {
	int a, b;
	scanf("%d %d", &a, &b);
	if (!(a - b)) {
		printf("a == b\n");
	}
	else if (a - b > 0) {
		printf("a > b\n");
	}
	else printf("a < b\n");


	return 0;
}


Measured memory_bytes: 2592
#include <bits/stdc++.h>
using intl = long long;
using ld = long double;
using namespace std;
#define rep(i, n) for(intl i = 0; i < (intl)(n); i++)
#define repd(i, n) for(intl i = (intl)(n); i >= 0; i--)
#define repi(i, a, b) for(intl i = (intl)(a); i < (intl)(b); i++)
#define repid(i, a, b) for(intl i = (intl)(a); i >= (intl)(b); i--)
#define max(a, b) ((a) > (b) ? (a) : (b))
#define min(a, b) ((a) < (b) ? (a) : (b))
#define all(x) (x).begin(),(x).end()
#define m0(x) memset(x,0,sizeof(x))
#define m1(x) memset(x,1,sizeof(x))
#define fill(x,y) memset(x,y,sizeof(x))
#define alength(a) (sizeof(a) / sizeof(a[0]))
#define cin(i, a) rep(i, alength(a))cin >> a[i]
#define ccin(i, j, a) rep(i, alength(a))rep(j, alength(a[i]))cin >> a[i][j]
#define debug(x) cout << #x << ":" << x << endl
#define rdebug(i,x) rep(i, alength(x))cout << #x << "[" << i << "]:" << x[i] << endl
#define sqrt sqrtl
#define int intl
#define itn intl
#define double ld
#define pb push_back
#define mp make_pair
const intl INF = 1e9;
const intl MOD = 1e9+7;
const ld eps = 1.0e-14;//-9
void fp(bool f){cout << (f ? "Yes" : "No") << endl;}
void fp(bool f, string s, string t){cout << (f ? s : t) << endl;}
intl kai(intl k){
    intl a = 1;
    for(int i = 2; i <= k; i++){
        a *= i;
    }
    return a;
}
intl gcd(intl a, intl b){
    if(!b)return a;
    return gcd(b, a % b);
}
intl digit10(intl a){
    if(!a)return 1;
    intl b = 0;
    while(a){
        a /= 10;
        b++;
    }
    return b;
}
signed main(){
    cout << fixed << setprecision(10);
    intl a,b,c,d;
    cin >> a >> b >> c;
    cout << min(a * b,c) << endl;
    return 0;
}

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

int main() {
  double a,b,h,m;
  cin >> a >> b >> h >> m;
  cout << fixed << setprecision(14);
  cout << sqrt(a*a+b*b-2*a*b*cos(h/6*M_PI-m*11/360*M_PI));
}

Measured memory_bytes: 4228
A, B = map(int, input().split())
S = input()
i = S.find("-")
if i == -1:
    print("No")
    exit()

s = list(S)
if not(i == A):
    print("No")
    exit()
if not(len(s)-(i+1) == B):
    print("No")
    exit()
for index in range(len(s)):
    if index == i:
        continue
    if s[index] == "-":
        print("No")
        exit()

print("Yes")


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

int main(){
    int n;
    cin >> n;
    int a[n] = {};
    rep(i,n) cin >> a[i];
    bool can = false;
    rep(i,n) if(a[i] % 2) can = true;
    cout << (can ? "first" : "second") << endl; 
    return 0;
}

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


int main(){
    int n,x;
    cin >> n >> x;
    vector<int> a(n);
    rep(i,n) {
        cin >> a[i];
        a[i] = abs(a[i]-x);
    }
    sort(a.begin(),a.end());
    int e = a.front();
    vector<int> s;
    for(int i=1; i*i<=e; i++){
        if(e%i==0){
            s.push_back(i);
            s.push_back(e/i);
        }
    }
    for(int i=1; i<n; i++){
        vector<int> f;
        for(int j=0; j<(int)s.size(); j++){
            if(a[i]%s[j]==0){
                f.push_back(s[j]);
            }
        }
        s = f;
    }
    sort(s.begin(),s.end(),greater<int>());
    cout << s.front() << endl;
    

    return 0;
}

Measured memory_bytes: 3700
import java.util.Scanner;
import java.util.*;

public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int a= sc.nextInt();
        int b=sc.nextInt();
   System.out.printf("%d %d %f\n",a/b,a%b,(double)a/b);
        }
    }


Measured memory_bytes: 26372
#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <algorithm>
#include <bits/stdc++.h>

using namespace std;
using ll = long long ;
const int INF = 1001001001;


int main() {

    int x,y;
    cin >> x >> y ;
    string board[x];
    bool goodx[x],goody[y];
    for(int i=0;i<x;i++){
            cin >> board[i] ;
            goodx[i] = false ;
    } 

    for(int i=0;i<y;i++){
            goody[i] = false ;
    } 

    for(int i=0;i<x;i++){
        for(int j=0;j<y;j++){
            if(board[i][j]=='#'){
                goodx[i]=true;
                goody[j]=true;
            }
            }
    }

    for(int i=0;i<x;i++){
        if(goodx[i]){
        for(int j=0;j<y;j++){
            if(goody[j]){
                cout << board[i][j] ;
            }
        }
                cout << endl ;
        }
    }

    return 0 ;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#define ll          long long
#define pb          push_back
#define eb 			emplace_back
#define mp 			make_pair
#define pii         pair<ll,ll>
#define vi          vector<int>
#define vii         vector<pii>
#define mi          map<ll,ll>
#define mii         map<pii,ll>
#define all(a)      (a).begin(),(a).end()
#define fi          first
#define si          second
#define sz(x)       (ll)x.size()
#define endl        "\n"
#define checkbit(n, b) ((n >> b) & 1)
#define mod        1000000007
#define inf        1000000000000000000
#define puts(n)		cout<<n;
#define rep(i,a,b)  for(int i=a;i<b;i++)
#define setbits(x) __builtin_popcount(x)
#define mset(m,v) memset(m,v,sizeof(m))
using namespace std;
int main()
{
   ios_base::sync_with_stdio(false);
   cin.tie(NULL);
   cout.tie(NULL);
  
int a,b,c,d;
cin>>a>>b>>c>>d;
while(a>0&&c>0)
{
c-=b;
if(c<=0)
break;
a-=d;	
}
if(a<=0)
cout<<"No"<<endl;
else
cout<<"Yes"<<endl;
return 0;
}

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

int main(){
  int N,D,ans;
  cin >> N >> D ;
  
  if(N % (2*D+1)==0){
    ans = N/(2*D+1) ;
  }else{
    ans = N/(2*D+1)+1 ;
  }
  
  cout << ans ;
}

Measured memory_bytes: 256
// In the name of GOD
#include<bits/stdc++.h>
using namespace std;

#define debug(x) cout<<#x<<" :: "<<x<<"\n";
#define debug2(x,y) cout<<#x<<" :: "<<x<<"\t"<<#y<<" :: "<<y<<"\n";
#define debug3(x,y,z) cout<<#x<<" :: "<<x<<"\t"<<#y<<" :: "<<y<<"\t"<<#z<<" :: "<<z<<"\n";

#define     IOS         ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define 	setprecn(x) cout<<fixed<<setprecision(x);
#define 	ll          long long int
#define 	pb          push_back
#define 	pll         pair<ll,ll>
#define 	vll         vector<ll>
#define 	ff          first
#define 	ss          second
#define 	all(a)      (a).begin(),(a).end()
#define 	sz(x)       (ll)x.size()
#define 	mod         1000000007
#define 	inf         10000000000000007
#define 	rep(i,n)    for(ll i=0;i<n;i++)
#define 	repe(i,a,b) for(ll i=a;i<b;i++)
#define 	lbnd        lower_bound
#define 	ubnd        upper_bound
#define 	bs          binary_search

ll power(ll a,ll b,ll m=mod)
{
	if(b==0)
		return 1;
	if(b==1)
		return a;
	ll c=power(a,b/2,m);
	if(b%2==0)
		return((c%m)*(c%m))%m;
	return ((((c%m)*(c%m))%m)*(a%m))%m;
}

/********************************************************/
//	d.erase(unique(all(d)), d.end());



int main()
{
	IOS;
	ll n,k,m,i,j,c=0,cs=0,t;
	t=1;

	// cin>>t;
	string s;
	while(t--)
	{
		cin>>n;
		// n=s.length();
		ll a[n],b[n+1];
		memset(b,0,sizeof b);
		rep(i,n)
		{
			cin>>a[i];
			b[a[i]]++;
		}
		rep(i,n)
		{
			j=b[i+1];
			c+=(j*(j-1))/2;
		}
		rep(i,n)
		{
			j=b[a[i]];
			// debug3(i,j,c);
			ll x=c;
			x-=(j*(j-1))/2;;
			j--;
			x+=(j*(j-1))/2;
			cout<<x;
			cout<<"\n";
		}

		
	}
	return 0;
}

Measured memory_bytes: 5760
#coding=utf-8
n,a,b = list(map(int,input().split()))
mod = 10**9+7

#繰り返し二乗法
def pow_k(x, n):
    if n == 0:
        return 1
    K = 1
    while n > 1:
        if n % 2 != 0:
            K *= x
        x *= x
        x %= mod
        n //= 2
    return K * x

def cmb(n,r):
  res = 1
  for i in range(r):
    res *= n - i
    res *= pow(i + 1, mod - 2, mod)
    res %= mod
  return res

ans = (pow_k(2,n) - 1)%mod
A = cmb(n, a)
B = cmb(n, b)

print((ans-A-B)%mod)



Measured memory_bytes: 3064
n = int(input());
a = input().split(" ");
x = int(a[0]);
y = 0;
for i in range(1,n) :
	y += int(a[i]);

ans = abs(x - y);
for i in range(1,n-1) :
	x += int(a[i]);
	y -= int(a[i]);
	if abs(x - y) < ans :
		ans = abs(x - y);
print(ans);


Measured memory_bytes: 19068
using System;
using System.Linq; 
 
class Program
{
    static void Main(string [] args)
    {
        var l = Console.ReadLine().Split(' ').Select(x => int.Parse(x)).ToList();
        var sl = Enumerable.Range(1, l[0]).Select(x => Console.ReadLine()).OrderBy(x => x).ToList();

        var result = "";
        foreach (var s in sl)
        {
            result = result + s;
        }
        Console.WriteLine(result);
    }
}

Measured memory_bytes: 14688
object Main extends App {
  var get = readLine.split(" ")
    var a = get(0).toInt
    var b = get(1).toInt
  var sum =0
if(a>=b) {
 sum =  a
  a = a - 1
 } else {
sum =  b
    b= b-1
  }
  if(a>=b) {
  sum = 
 sum +  a
  }
  else {
  sum = 
 sum +  b
  }
    println(sum)
}

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

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

	vector<int> A(N);
	for(int i = 0; i < N; i++){
		cin >> A[i];
	}

	vector<int> temp = A;
	sort(temp.begin(), temp.end(), greater<int>());

	int max = temp[0];
	int max_second = temp[1];

	for(int i = 0; i < N; i++){
		if(A[i] == max){
			cout << max_second << endl;
		}
		else{
			cout << max << endl;
		}
	}

	return 0;
}

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

vector<vector<pair<int, int>>> graph;
vector<bool> visited;
vector<int> diff;
vector<int> ans;

int DFS(int v){
    visited[v] = true;
    int d = diff[v];// want to make it 0 at last

    for(auto adjacent : graph[v]){
        if(visited[adjacent.first] == true) continue;// search except for the parent node

        int edge_id = adjacent.second;
        int nd = DFS(adjacent.first);
        if(nd == 1) ans.push_back(edge_id);// must cut the cord to flip nd = diff[child] (= 1) to 0
        d += nd;
        d %= 2;// flipped if the cord is cut
    }

    return d;// must be 0 for the root (if not, impossible to turn off all...)
}

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

    vector<pair<int, int>> bomb(n);
    for(int i=0; i<n; i++){
        cin >> bomb[i].first >> bomb[i].second;
    }
    sort(bomb.begin(), bomb.end());

    // original difference
    diff.resize(n+1);
    diff[0] = (0 + bomb[0].second) % 2;
    for(int i=0; i+1<n; i++){
        diff[i+1] = (bomb[i].second + bomb[i+1].second) % 2;
    }
    diff[n] = (bomb[n-1].second + 0) % 2;

    // (potential) additional contribution to diff
    graph.resize(n+1);
    for(int i=0; i<m; i++){
        int l, r;
        cin >> l >> r;
        l = lower_bound(bomb.begin(), bomb.end(), make_pair(l,0)) - bomb.begin();
        r = upper_bound(bomb.begin(), bomb.end(), make_pair(r,1)) - bomb.begin();
        graph[l].push_back({r,i+1});// (target node, edge id) with latter 1-indexed
        graph[r].push_back({l,i+1});
    }

    // DFS
    visited.assign(n+1, false);
    for(int i=0; i<n+1; i++){
        if(visited[i] == true) continue;// for each conneced component
        
        if(DFS(i) == 1){
            cout << -1 << endl;
            return 0;
        }
    }

    // output
    sort(ans.begin(), ans.end());

    int k = ans.size();
    cout << k << endl;
    
    for(int j=0; j<k; j++){
        cout << ans[j];
        if(j == k-1) break;
        cout << " ";
    }
    cout << endl;
    return 0;
}

Measured memory_bytes: 18944
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <iomanip>
#include <cmath>
#include <cstdlib>
#include <map>
#include <utility>
#include <numeric>
#define ll long long
#define REP(i, x) for(int (i) = 0; (i) < (x); (i) ++)
#define pi 3.1415926535
const int MOD = 1000000007;
using namespace std;

int main() {
	string s;
	cin >> s;
	if (s.size() == 2) {
		cout << s << endl;
	}
	else {
		cout << s[2] << s[1] << s[0] << endl;
	}
	return 0;
}

Measured memory_bytes: 256
n=int(input())
x=[-1]*n
y=[-1]*n
h=[-1]*n
for i in range(n):
  x[i],y[i],h[i]=map(int,input().split())
  
cnt=0
now=0
for i in range(n):
  if h[i]>0:
    cnt+=1
    now=i
if cnt==1:
  print(x[now],y[now],h[now])
  exit()

for cx in range(0,101):
  for cy in range(0,101):
    H=[]
    for i in range(n):
      if h[i]>0:
        H.append(h[i]+abs(cx-x[i])+abs(cy-y[i]))
    if len(set(H))==1:
      print(cx,cy,H[0])
      exit()


Measured memory_bytes: 9048
/// In the name of ALLAH
/// I'm THEOVE46
#include<bits/stdc++.h>
using namespace std;

#define gap             " "
#define nn              "\n"
#define pi              2*acos(0.0)
#define db              double
#define ft              float
#define ll              long long
#define ull             unsigned long long
#define pf              printf
#define sf              scanf
#define ff              first
#define ss              second
#define sc(n)           sf("%d",&n)
#define sc2(n, m)       sf("%d%d",&n,&m);
#define scl(n)          sf("%lld",&n)
#define scl2(n, m)      sf("%lld%lld",&n,&m);
#define pc(n)           pf("%d",n)
#define scf(f)          sf("%f",&f)
#define pcf(f)          pf("%f",f)
#define bfs             cin.get()
#define bfc             getchar()
#define gl(s)           getline(cin, s);
#define loop(a,n)       for(ll i=a; i<n; i++)
#define rloop(a,n)      for(ll i=a; i>n; i--)
#define tloop(test)     for(ll tl=1; tl<=test; tl++)
#define case1(z)        cout<<"Case "<<z<<": "
#define case2(z)        printf("Case %d: ",z)
#define vi              vector<int>
#define vl              vector<ll>
#define vld(vc,rw)      vector<vector<ll> >vc(rw)
#define pii             pair<int,int>
#define pll             pair<ll,ll>
#define pis             pair<int,string>
#define psi             pair<string,int>
#define mls             map <ll,string>
#define msl             map <string,ll>
#define mll             map <ll,ll>
#define mp              make_pair
#define pb              push_back
#define itr             vector<int> :: iterator
#define sz(s)           s.size()
#define sl(s)           s.length()
#define Sort(s)         sort(s.begin(), s.end());
#define SortR(s)        sort(s.rbegin(), s.rend());
#define all(x)          x.begin(),x.end()
#define rall(x)         x.end(), x.begin()
#define MEM(ar,val)     memset(ar, (val), sizeof(ar))
#define IN(A,B,C)       assert(B<=A && A<=C)
#define EPS             1e-9
#define bug1            "**1**"
#define bug2            "****2****"
#define artri(b,h)      0.5*b*h
#define artrap(b1,b2,h) (b1+b2)/2*h
#define arcrl(r)        pi*r*r
#define vlsyl(r,h)      pi*r*r*h
#define vlcone(r,h)     pi*r*r*(h/3)
#define vlsph(r)        (4/3)*pi*r*r*r
#define flush           fflush(stdout);
#define pcn(dg,val)     fixed << setprecision(dg) << val
#define fap(x)          cout << __LINE__ << " says: " << #x << " = " << x << "\n"
#define FastIO          ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define showsort(n, a)  for(int i=0; i<n; i++) cout << a[i] << gap; cout << endl;

///THEOVE46

int main()
{
    FastIO;
    ll a, b, v, w, x, y, t, d;
    cin >> a >> v >> b >> w >> t;
    d = abs(a-b);
    x = v*t+1;
    y = w*t+d+1;
    if(x>=y) cout << "YES\n";
    else cout << "NO\n";
    return 0;
}

///   check for integer overflow, array bounds
///   check for n=1
///   - - - The Ove 46



Measured memory_bytes: 3648
#include<cstdio>
using namespace std;
int main(){
    long n,a,b,c,d;
    scanf("%ld %ld %ld %ld %ld",&n,&a,&b,&c,&d);
    for(long i=0;i<n-1;i++){
        if(c*i-d*(n-1-i)<=b-a&&d*i-c*(n-1-i)>=b-a){
            printf("YES\n");
            return 0;
        }
    }
    printf("NO\n");
}
  

Measured memory_bytes: 128
#include <iostream>
using namespace std;
 
int main() {
  int n,d,flg[1002]={};
  cin >> n >> d;
  for(int i=0;i<d;i++) {
    int a,b;
    cin >>a>>b;
    flg[a] = max(flg[a],b);
  }
   
  int sta=0,sum=0,L=0,R=0;
  for(int i=0;i<=n;i++) {
    if(flg[i] != 0 && sta==1) R=max(R,flg[i]);
    else if(flg[i] != 0) L=i,R=flg[i],sta=1;
    else if(i==R) sum += 3*(R-L)+1,sta=0;
    else if(sta==0) sum++;
  }
  cout << sum <<endl;
  return 0;
}

Measured memory_bytes: 1164
#include <iostream>

using namespace std;

const long MOD = 1000000007;
typedef pair<int, int> P;
typedef long long ll;

int main(){
    int S, W;
    cin >> S >> W;

    if(W >= S) cout << "unsafe" << endl;
    else cout << "safe" << endl;

    return 0;
}


Measured memory_bytes: 3636
#169D
#Div Game

n=int(input())

def factorize(n):
    fct=[]
    b,e=2,0
    while b**2<=n:
        while n%b==0:
            n/=b
            e+=1
        if e>0:
            fct.append([b,e])
        b+=1
        e=0
    if n>1:
        fct.append([n,1])
    return fct
l=factorize(n)
ans=0
for i in l:
    c=1
    while i[1]>=c:
        ans+=1
        i[1]-=c
        c+=1
print(ans)

Measured memory_bytes: 9232
#include <stdio.h>

int main(void) {
    int n, ketasu = 0, count = 0;
    scanf("%d", &n);
    int n_2 = n;
    while(n_2 != 0) {
        n_2 /= 10;
        ++ketasu;
    }
    if(ketasu % 2 == 0) {
        for(int i = 1; i <= ketasu/2; i++) {
            int j = i, ju = 1;
            while(j <= ketasu-i-1) {
                ju *= 10;
                j++;
            }
            count += 9*ju;
        }
    } else {
        for(int i = 1; i <= ketasu/2; i++) {
            int j = i, ju = 1;
            while(j <= ketasu-i-2) {
                ju *= 10;
                j++;
            }
            count += 9*ju;
        }
        if(ketasu == 5) {
            count += n-10000+1;
        } else if(ketasu == 3) {
            count += n-100+1;
        } else if(ketasu == 1) {
            count = n;
        }
    }
    printf("%d\n", count);
    return 0;
}


Measured memory_bytes: 128
/*
ID: learnin7
TASK: test
LANG: C++                 
*/
/* LANG can be C++11 or C++14 for those more recent releases */
#include<bits/stdc++.h>

using namespace std;
typedef long long ll;

int main(){
        
    ios_base::sync_with_stdio(0);
    //ofstream fout ("test.out");
    //ifstream fin ("test.in");
    //fin >> a >> b;
    //fout << a+b << endl;
    int n,m,x;
    cin>>n>>m>>x;
    int c[n];
    int a[n][m];
    for(int i=0;i<n;i++){
        cin>>c[i];
        for(int j=0;j<m;j++){
            cin>>a[i][j];
        }
    }
    int mincost= INT_MAX;
    for(int i=0;i<pow(2,n);i++){
        int sum=0;
        vector<int> algo(m,0);
        for(int j=0;j<n;j++){
            if((1<<j & i)>0){
                sum += c[j];
                for(int k=0;k<m;k++) algo[k] += a[j][k];   
            }
        }
        bool flag = true;
        for(int k=0;k<m;k++){
            if(algo[k]<x){
                flag = false;
                break;
            }
        }
        if(flag)    mincost = min(mincost,sum);
    }
    if(mincost == INT_MAX)  cout<<-1<<endl;
    else                    cout<<mincost<<endl;
    return 0;
}



Measured memory_bytes: 4028
#include <bits/stdc++.h>
#define rep(i, a, n) for(int i = a; i < n; i++)
#define REP(i, n) rep(i, 0, n)
#define repb(i, a, b) for(int i = a; i >= b; i--)
#define all(a) a.begin(), a.end()
#define int long long
#define chmax(x, y) x = max(x, y)
#define chmin(x, y) x = min(x, y)
using namespace std;
typedef pair<int, int> P;
const int mod = 1000000007;
const int INF = 1e12;

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int a, b, c, d;
    cin >> a >> b >> c >> d;
    int l = a + b;
    int r = c + d;
    if(l > r) cout << "Left" << endl;
    else if(l == r) cout << "Balanced" << endl;
    else cout << "Right" << endl;
}

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

const long double PI = (acos(-1));
const long double EPS = 0.0000000001;

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

	ll l,r;
	


	cin >> l >> r;
	
	int ans=2019;
	
	int diff=r-l;
	if(diff>2019){
		cout << 0 << endl;
		return 0;
	}
	//diff=diff%2019;
	
	
	l=l%2019;
	r=l+diff;
	
	
	
	//int m=2019; //min
	
	for(int i=l;i<r;i++){
		for(int j=i+1;j<=r;j++){
			ans=min((i*j)%2019,ans);
		}
	}
	
	
	
	cout << ans << "\n";
	
	return 0;
}


//vector<int> a(n);  sort(a.begin(),a.end());
//cout << "test" << "\n";


//g++ -o a a.cpp


Measured memory_bytes: 256
N,M=map(int,input().split())
d={}
PY=[]
import bisect
for _ in range(M):
    p,y=map(int,input().split())
    PY.append((p,y))
    t=d.get(p, [0])
    i=bisect.bisect_left(t,y)
    t.insert(i,y)
    d[p]=t
    
dx={}
for k, v in d.items():
    for i in range(len(v)):
        dx[(k,v[i])]=i
        
for p,y in PY:
    print(str(p).zfill(6)+str(dx[(p,y)]).zfill(6))

Measured memory_bytes: 69680
n, k = map(int, input().split())
s = str(input())
v = [0]
for i in range(len(s)-1):
  if s[i] != s[i+1]:
    v.append(i+1)
ans = 0
arr = v + [n] *(2*k+1)
for i, j in enumerate(v):
  if s[j] == "0":
    ans = max(ans, arr[i+2*k]-arr[i])
  else:
    ans = max(ans, arr[i + 2*k +1] -arr[i])
print(ans)

Measured memory_bytes: 8692
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<(n);++i)
#define FOR(i,n,j) for(int i=(j);i<(n);++i)
#define ssort(n) sort((n).begin(),(n).end())
#define rsort(n) sort((n).begin(),(n).end(),greater<int>())
#define mp make_pair
using ll=long long;
using ld=long double;
typedef pair<int,int> P;
typedef pair<P,int> COST;
#define repl(i,n) for(ll i=0;i<(n);++i)
#define Yes cout << "Yes" << endl
#define No cout << "No" << endl
#define YES cout << "YES" << endl
#define NO cout << "NO" << endl
using Graf=vector<vector<int>>;
#define MAX 1000000007

int main()
{
    int h,w;
    cin >> h >> w;
    vector<string> s(h);
    Graf g(h,vector<int>(w));
    rep(i,h){
        cin >> s[i];
    }
    rep(i,h){
        rep(j,w){
            int count_bom=0;
            if(i>0){
                if(j>0){
                    if(s[i-1][j-1]=='#'){
                        count_bom++;
                    }
                }
                if(s[i-1][j]=='#'){
                    count_bom++;
                }
                if(j<w-1){
                    if(s[i-1][j+1]=='#'){
                        count_bom++;
                    }
                }
            }
            if(j>0){
                if(s[i][j-1]=='#'){
                    count_bom++;
                }
            }
            if(j<w-1){
                if(s[i][j+1]=='#'){
                    count_bom++;
                }
            }
            if(i<h-1){
                if(j>0){
                    if(s[i+1][j-1]=='#'){
                        count_bom++;
                    }
                }
                if(s[i+1][j]=='#'){
                    count_bom++;
                }
                if(j<w-1){
                    if(s[i+1][j+1]=='#'){
                        count_bom++;
                    }
                }
            }
            g[i][j]=count_bom;
        }
    }
    rep(i,h){
        rep(j,w){
            if(s[i][j]!='#'){
                cout << g[i][j];
            }else{
                cout << '#';
            }
        }cout << endl;
    }
}

Measured memory_bytes: 3536
#include<iostream>
#include<algorithm>
#include<bits/stdc++.h>
using namespace std;
#define mp make_pair
#define pb push_back
#define int long long
#define pi 3.141592653589793238462643383279502
#define M 1000000007

signed main()
{int n;
cin>>n;
string s;
cin>>s;
int x=s.size();
for(int i=0;i<x;i++)
    s[i]=(s[i]-'A'+n)%26+'A';

cout<<s;
return 0;
}


Measured memory_bytes: 256
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <climits>
#include <cfloat>
#include <ctime>
#include <map>
#include <utility>
#include <set>
#include <iostream>
#include <memory>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <sstream>
#include <complex>
#include <stack>
#include <queue>
#include <numeric>
#include <list>

using namespace std;

#ifdef _MSC_VER
#define __typeof__ decltype

template <class T>
int __builtin_popcount(T n) { return n ? 1 + __builtin_popcount(n & (n - 1)) : 0; }
#endif

#define foreach(it, c) for (__typeof__((c).begin()) it=(c).begin(); it != (c).end(); ++it)
#define all(c) (c).begin(), (c).end()
#define rall(c) (c).rbegin(), (c).rend()
#define popcount __builtin_popcount

#define rep(i, n) for (int i = 0; i < n; ++i)

template <class T> void max_swap(T& a, const T b) { a = max(a, b); }
template <class T> void min_swap(T& a, const T b) { a = min(a, b); }

const double EPS = 1e-10;
typedef long long ll;
typedef pair<int, int> pint;


int main()
{
	const int mod = 100000;
	int n, m;
	static int a[100100], sum[100100], s[100100];
	scanf("%d%d", &n, &m);
	--n;
	rep (i, n)
		scanf("%d", s + i);
	rep (i, m)
		scanf("%d", a + i);

	sum[0] = 0;
	rep (i, n)
		sum[i + 1] = (sum[i] + s[i]) % mod;

	int res = 0;
	int pos = 0;
	rep (i, m)
	{
		int x = pos, y = pos + a[i];
		if (x < y)
			swap(x, y);

		(res += sum[x] - sum[y]) %= mod;
		pos += a[i];
	}
	printf("%d\n", res);
}

Measured memory_bytes: 0
#include<iostream>
#include<cmath>
using namespace std;
typedef long long ll;
const long double PI = acos(-1);
const long double EPS = 0.0000000001;

long double calc_volume(long double a, long double b, long double theta) {
    if(theta > PI / 2.0 - EPS) return 0.0;

    if (a * tan(theta) >= b) {
        return a * b * b / tan(theta) / 2.0;
    } else {
        return a * a * b - a * a * a * tan(theta) / 2.0;
    }
}

int main() {
    cin.tie(0);
    cin.sync_with_stdio(0);
    
    int a, b, x;
    cin >> a >> b >> x;

    long double l = 0.0, r = PI / 2.0;
    for(int _ = 1; _ <= 100000; _++) {
        long double mid = (l + r) / 2.0;
        if(calc_volume(a, b, mid) < x) r = mid;
        else l = mid;
    }
    long double ans = 180 * r / PI;
    printf("%.10Lf\n", ans);
}

Measured memory_bytes: 4068
int main()
{
  int a, b, r, tmp;
  scanf("%d%d",&a,&b);

if(a<b){
    tmp = a;
    a = b;
    b = tmp;
  }

 r = a % b;
  while(r!=0){
    a = b;
    b = r;
    r = a % b;
  }

  printf("%d\n",b);

}



Measured memory_bytes: 2140
#include <bits/stdc++.h>
using namespace std;
 
int main(){
 int H;
 int N;
 long long int dp[20000];
 dp[0]=0;
 cin >> H >> N;
 int D[N];
 int M[N];
 for(int i=0;i<N;i++)cin >> D[i] >> M[i];
 for(int i=1;i<H+1;i++){    
     dp[i]=1e10;//モンスターのHPでのDP
     for(int j=0;j<N;j++){  //HPごとに技ごとで最小のMPをチェック
         dp[i]=min(dp[i],dp[max(0,i-D[j])]+M[j]);
     }}
     cout << dp[H] << endl;
 }

Measured memory_bytes: 384
#include<bits/stdc++.h>
#define de(x) cout<<#x<<"="<<x<<endl;
#define dd(x) cout<<#x<<"="<<x<<" ";
#define rep(i,a,b) for(int i=a;i<(b);++i)
#define repd(i,a,b) for(int i=a;i>=(b);--i)
#define repp(i,a,b,t) for(int i=a;i<(b);i+=t)
#define ll long long
#define mt(a,b) memset(a,b,sizeof(a))
#define fi first
#define se second
#define inf 0x3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f3f
#define pii pair<int,int>
#define pdd pair<double,double>
#define pdi pair<double,int>
#define mp(u,v) make_pair(u,v)
#define sz(a) a.size()
#define ull unsigned long long
#define ll long long
#define pb push_back
#define PI acos(-1.0)
#define qc std::ios::sync_with_stdio(false)
const int mod = 1e9+7;
const int maxn = 1e5+5;
const double EPS = 1e-6;
using namespace std;
int main()
{
	char a,b;
	scanf("%c %c",&a,&b); 
	if(a>b) printf(">");
	else if(a==b) printf("=");
	else printf("<");
	return 0;
}



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


void solver() {
  int n;
  cin >> n;
  vector<int> as(n);

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

  vector<int> bs(n);
  vector<int> cs(n);
  map<long long, int> mpb;
  map<long long, int> mpc;
  for (int i = 0; i < n; i++) {
    mpb[(i+1) + as[i]]++;
    mpc[(i+1) - as[i]]++;
  }

  long long ans = 0;
  for( auto i = mpb.begin(); i != mpb.end() ; ++i ) {
    long long b = i->first;
    long long bn = i->second;
    ans += mpc[b] * bn;
  }
  cout << ans << "\n";
}

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


Measured memory_bytes: 39952
#include<cstdio>
#include<algorithm>
using namespace std;

#define ran 101101

int n;
int h[ran];

int main() {
	scanf("%d", &n);
	for(int i=0;i<n;i++) scanf("%d", &h[i]);
	
	for(int i=n-2;i>=0;i--) {
		int todo = max(0, h[i] - h[i+1]);
		if (todo>1) {
			puts("No");
			return 0;
		}
		h[i] -= todo;
	}
	puts("Yes");
	
	return 0;
}

Measured memory_bytes: 512
#include <bits/stdc++.h>
using namespace std;
int main(){
    long n;
    cin>>n;
    unsigned long ft,fa,sum;
    for(int i=0; i<n; i++){
        unsigned long t,a;
        cin>>t>>a;
        if(i>0){
            int j=0;
            while((ft+j)%t!=0)
                j++;
            sum+=j;
            ft+=j;
            j=0;
            while((fa+j)%a!=0)
                j++;
            sum+=j;
            fa+=j;
            if(ft/t*a>=fa){
                sum+=ft/t*a-fa;
                fa=ft/t*a;
            }
            else{
                sum+=fa/a*t-ft;
                ft=fa/a*t;
            }
        }
        else{
            ft=t;
            fa=a;
            sum=t+a;
        }
    }
    cout<<sum;
}

Measured memory_bytes: 256
#include <cstdio>
#include <cmath>
#include <vector>
#include <algorithm>
#include <functional>
using namespace std;
typedef long long ll;

int main() {
	int N, A, B, C;

	scanf("%d %d %d %d", &N, &A, &B, &C)+1;

	int tmp;
	vector<int> l;
	for (int i = 0; i < N; i++) {
		scanf("%d", &tmp)+1;
		l.push_back(tmp);
	}
	int max = pow(4.0f, N);

	vector<int> a, b, c;
	int minMp = 999999999;
	int point;
	for (int i = 0; i < max; i++) {
		point = 0;
		tmp = i;
		a.clear();
		b.clear();
		c.clear();
		for (int keta = 0; keta < N; keta++) {
			switch (tmp % 4) {
			case 0:
				a.push_back(l[keta]);
				break;
			case 1:
				b.push_back(l[keta]);
				break;
			case 2:
				c.push_back(l[keta]);
				break;
			default:
				break;
			}
			tmp /= 4;
		}
		if (a.size() * b.size() * c.size() == 0) continue;

		point += (a.size() - 1) * 10;
		point += (b.size() - 1) * 10;
		point += (c.size() - 1) * 10;

		int aSum = 0;
		int bSum = 0;
		int cSum = 0;
		auto aEnd = a.end();
		auto bEnd = b.end();
		auto cEnd = c.end();
		for (auto itr = a.begin(); itr != aEnd; itr++) aSum += *itr;
		for (auto itr = b.begin(); itr != bEnd; itr++) bSum += *itr;
		for (auto itr = c.begin(); itr != cEnd; itr++) cSum += *itr;

		point += abs(A - aSum);
		point += abs(B - bSum);
		point += abs(C - cSum);

		if (minMp > point) minMp = point;
	}

	printf("%d\n", minMp);

	return 0;
}


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

int main() {
    vector<int> vec{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 << vec.at(K-1) << endl;
}

Measured memory_bytes: 256
#pragma GCC target("avx2")
#pragma GCC optimize("O3")
   
#include <x86intrin.h>
#include <bits/stdc++.h>   
 
using namespace std;
     
#define F first
#define S second           
#define lb lower_bound               
#define ub upper_bound
#define pb push_back
#define pf push_front    
#define ppb pop_back
#define mp make_pair
#define bpp __builtin_popcountll                                                                                        
#define sqr(x) ((x) * (x)) 
#define al 0x3F3F3F3F
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
#define in insert
#define ppf pop_front
#define endl '\n'
//#define int long long
 
typedef unsigned long long ull;
typedef long long ll;
typedef long double ld;
typedef pair <int, int> pii;
 
const int mod = (int)1e9 + 7;
const int N = (int)3e5 + 123;
const ll inf = (ll)1e18 + 1;

const double pi = acos (-1.0);
const double eps = 1e-7;                  
const int dx[] = {0, 0, 1, 0, -1};
const int dy[] = {0, 1, 0, -1, 0};

int n; 
pii a[N];

inline void boost () {                    
   ios_base :: sync_with_stdio (NULL);
   cin.tie (NULL), cout.tie (NULL);          
}                                                     

inline void Solve () {
   cin >> n;
   for (int i = 1; i <= n; i ++) cin >> a[i].F, a[i].S = i;
   sort (a + 1, a + n + 1);
   for (int i = 1; i <= n; i ++) cout << a[i].S << ' ';
}

main () {                                       
// freopen (".in", "r", stdin);    
// freopen (".out", "w", stdout);              
   boost ();
   int tt = 1;
   //cin >> tt;   
   while (tt --) {
      Solve ();
   }                                               
   return 0;      
}
                          

Measured memory_bytes: 1664
def main():
    import numpy as np
    n = int(input())
    a = sorted([int(input()) for _ in [0]*n])
    dp = np.array([1], dtype=np.int64)
    DP = np.array([1], dtype=np.int64)
    s = 1
    mod = 998244353
    for i in a:
        dp2 = np.concatenate([dp, np.zeros(i, dtype=np.int64)])
        DP2 = np.concatenate([DP, np.zeros(i, dtype=np.int64)])
        dp2[i:] = (dp2[i:]+2*dp) % mod
        DP2[i:] = (DP2[i:]+DP) % mod
        dp = dp2
        DP = DP2
        s += i
    ALL = sum(dp)
    A = sum(dp[(s-1)//2+1:])
    if s % 2 == 1:
        B = DP[s//2]
    else:
        B = 0
    print((3*A-2*ALL+3*B) % mod)


main()

Measured memory_bytes: 16716
#include <iostream>

using namespace std;

int Sum(int n) {
  int s = 0;
  while (n) {
    s += n % 10;
    n /= 10;
  }
  return s;
}

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

  int n;
  cin >> n;
  const int s = Sum(n);
  if (n % s == 0)
    cout << "Yes" << endl;
  else
    cout << "No" << endl;

  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#ifdef ONLINE_JUDGE
#define LLD "%I64d"
#else
#define LLD "%lld"
#endif
#define fu(a,b,c) for(int a=b;a<=(int)c;++a)
#define fd(a,b,c) for(int a=b;a>=(int)c;--a)
#define cu(a,b,c) for(int a=b;a<(int)c;++a)
#define cd(a,b,c) for(int a=(b)-1;a>=(int)c;--a)
#define gcd(a,b) __gcd(a,b) 
#define pii pair<int,int>
#define pll pair<long long,long long>
#define all(a) a.begin(),a.end()
#define F first
#define S second
#define pb push_back
#define pf push_front
#define MOD 1000000007 
#define MAXN 52
#define MAXH 20
#define MAXM 52
#define INF 100000000
#define ll long long
#define ull unsigned long long
#define RNG rng mt19937(time(NULL))
#define udist(a,b) uniform_int_distribution<uint32_t> distribution(a,b)
#define max3(a,b,c) max(a, max(b, c))
#define min3(a,b,c) min(a, min(b, c))
#define gmax(a,b) a = max(a, b)
#define gmin(a,b) a = min(a, b)
#define whatis(x) cerr << #x << " is " << x << endl;
#define fast_io() ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define PI 3.1415926535897932384626433
using namespace std;
using namespace __gnu_pbds;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;

int main(){
	int n,m,c;
	cin >> n >> m >> c;
	vector<int> v(m);
	cu(i,0,m)cin >> v[i];
	int cnt = 0;
	cu(i,0,n){
		ll sum = 0;
		cu(j,0,m){
			int x;
			cin >> x;
			sum += v[j] * x;
		}
		sum += c;
		cnt += sum > 0;
	}
	cout << cnt << '\n';
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define IOS ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define ll long long
#define ull unsigned long long
#define db double
#define rep(i,a,b)    for(ll i=a;i<b;i++)
#define repn(i,a,b)   for(ll i=a;i>=b;i--)
#define F first
#define S second
#define qi queue<ll>
#define pii pair<ll,ll>
#define vi vector<ll>
#define si set<ll>
#define vii vector<pii>
#define mi multiset<ll>
#define mii multiset<pii>
#define MI map<ll,ll>
#define pb push_back
#define mp  make_pair
#define lb lower_bound
#define ub upper_bound
#define all(v) (v).begin(), (v).end()
#define allr(v) (v).rbegin(), (v).rend()
#define mod 998244353
#define mod2 998244353
 
const ll N=1e12;
 
int fexp(int a, int b){int ans = 1;while(b){if(b&1) ans = ans*a%mod2; b/=2;a=a*a%mod2;}return ans;}
int inverse(int a, int p){return fexp(a, p-2);}
 
ll solve(){
    
    return 0;
}
 
signed main(){
    IOS
// 	#ifndef ONLINE_JUDGE
//     	freopen("input.txt", "r", stdin);
// 		freopen("output.txt", "w", stdout);
// 	#endif
    ll n,m,a;
    cin>>n>>m>>a;
    if(n>=m){
      if(n%m) cout<<(n/m+1)*a;
      else cout<<(n/m)*a;
    }
  	else cout<<a;
    return 0;
}
// size_t f= str.find(string s,0); find s in str from start
// if found then (f != string::npos)
// m.insert({x,y}); m[x]=y;

Measured memory_bytes: 3644
/**
 * File    : E.cpp
 * Author  : Kazune Takahashi
 * Created : 2018-2-25 21:06:35
 * Powered by Visual Studio Code
 */

#include <iostream>
#include <iomanip>   // << fixed << setprecision(xxx)
#include <algorithm> // do { } while ( next_permutation(A, A+xxx) ) ;
#include <vector>
#include <string> // to_string(nnn) // substr(m, n) // stoi(nnn)
#include <complex>
#include <tuple>
#include <queue>
#include <stack>
#include <map> // if (M.find(key) != M.end()) { }
#include <set>
#include <random> // random_device rd; mt19937 mt(rd());
#include <cctype>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <cstdlib>
using namespace std;

#define DEBUG 0 // change 0 -> 1 if we need debug.

typedef long long ll;

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

// const int C = 1e6+10;
// const ll M = 1000000007;

const int MAX_SIZE = 1000010;
const long long MOD = 998244353;

long long inv[MAX_SIZE];
long long fact[MAX_SIZE];
long long factinv[MAX_SIZE];

void init() {
  inv[1] = 1;
  for (int i=2; i<MAX_SIZE; i++) {
    inv[i] = ((MOD - inv[MOD%i]) * (MOD/i))%MOD;
  }
  fact[0] = factinv[0] = 1;
  for (int i=1; i<MAX_SIZE; i++) {
    fact[i] = (i * fact[i-1])%MOD;
    factinv[i] = (inv[i] * factinv[i-1])%MOD;
  }
}

long long C(int n, int k) {
  if (n >=0 && k >= 0 && n-k >= 0) {
    return ((fact[n] * factinv[k])%MOD * factinv[n-k])%MOD;
  }
  return 0;
}

long long power(long long x, long long n) {
  if (n == 0) {
    return 1;
  } else if (n%2 == 1) {
    return (x * power(x, n-1)) % MOD;
  } else {
    long long half = power(x, n/2);
    return (half * half) % MOD;
  }
}

long long gcm(long long a, long long b) {
  if (a < b) {
    return gcm(b, a);
  }
  if (b == 0) return a;
  return gcm(b, a%b);
}

ll N, K;

ll catalan(ll T, ll X, ll Y)
{
  return (C((X + Y) % MOD, X) + MOD - C((X + Y) % MOD, (Y + MOD - T) % MOD)) % MOD;
}

int main() {
  init();
  cin >> N >> K;
  if (N > K)
  {
    cout << 0 << endl;
    return 0;
  }
  ll ans = 0;
  for (ll R = 0; R <= K; R++)
  {
    ll B = K - R;
    if (R < B)
      continue;
    else if (R == B)
    {
      ans += catalan(R - N + 1, R, B - 1);
      ans %= MOD;
    }
    else if (B - R < N)
    {
      ans += catalan(R - N + 1, R, B);
      ans %= MOD;
    }
    else
    {
      ans += C(R + B, R);
      ans %= MOD;
    }
  }
  cout << ans << endl;
}


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

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

using namespace std;

using ll = long long;
using vi = vector<int>;
using vll = vector<ll>;

char itoc(int i) { return char(97 + i); }

void print(string s, int l, int n) {
    int str_len = s.size();
    if (str_len == n) {
        cout << s << endl;
        return;
    }
    rep(i, 0, l) {
        print(s + itoc(i), l, n);
    }
    print(s + itoc(l), l + 1, n);
}

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

    string s;
    print(s, 0, n);
    return 0;
}

Measured memory_bytes: 1536
import sys
import math
import itertools
import collections
import heapq
import re
import numpy as np

rr = lambda: sys.stdin.readline().rstrip()
rs = lambda: sys.stdin.readline().split()
ri = lambda: int(sys.stdin.readline())
rm = lambda: map(int, sys.stdin.readline().split())
rl = lambda: list(map(int, sys.stdin.readline().split()))
inf = float('inf')
mod = 10**9 + 7

n = ri()
li = rl()
li1 = sorted(li)
cnt = 0
for a, b in zip(li, li1):
  if a != b:
    cnt += 1
print('NO' if cnt > 2 else 'YES')












Measured memory_bytes: 27116
import numpy as np 
N,W=map(int,input().split())
w,v=[],[]
for i in range(N):
    a,b=map(int,input().split())
    w+=[a]
    v+=[b]
DP=np.ones(N*1000+1,dtype=int)*(W+1)
DP[0]=0
for i in range(N):
    DP[v[i]:]=np.minimum(DP[:-v[i]]+w[i],DP[v[i]:])
ans=0
for k in range(N*1000+1):
    if DP[k]<=W:
        ans=k
print(ans)

Measured memory_bytes: 14804
#include <iostream>

int main(){
   int D, N;
   std::cin >> D >> N;
   if (D == 0){
      if (N!=100){
         std::cout << N << std::endl;
      } else{
         std::cout << 101 << std::endl;
      }
   } else if (D == 1){
      if (N!=100){
         std::cout << 100*N << std::endl;
      } else{
         std::cout << 10100 << std::endl;
      }
   } else if (D == 2){
      if (N!=100){
         std::cout << 10000*N << std::endl;
      } else{
         std::cout << 1010000 << std::endl;
      }
   }
}



Measured memory_bytes: 256
import sys
input = sys.stdin.readline
N, M = map(int, input().split())
LR = [list(map(int, input().split())) for _ in range(M)]

A, B = 1, N
for lr in LR:
    L, R = lr
    if R < A or B < L:
        print(0)
        exit()

    if A <= L <= R <= B:
        A, B = L, R
    elif L <= A <= R <= B:
        B = R
    elif A <= L <= B <= R:
        A = L
print(B - A + 1)


Measured memory_bytes: 27400
#include<iostream>
#include<string>
using namespace std;
int main(){
	int a,b,c,d,e,limit;
	int i,j,k,l,total;
	double temp=-1;
	int temptt=0;
	int tempyy=0;
	
	string str;
	
//	cin>>a>>b>>c>>d>>e>>limit;
	while(cin>>str){
		if((str.length()<4)){
		 cout<<"No"<<endl;}
		else if(str[0]=='Y'&str[1]=='A'&str[2]=='K'&str[3]=='I'){
		 cout<<"Yes"<<endl;
		}else
		 cout<<"No"<<endl;
		
	}

	return 0;
	}

Measured memory_bytes: 256
#include<iostream>
#include<stdio.h>
#include<vector>
#include<cmath>
#include<queue>
#include<string.h>
#include<map>
#include<set>
#include<algorithm>
#define ll long long
#define pi pair < ll,ll >
#define mp(a,b) make_pair(a,b)
#define rep(i,a,b) for(int i = a;i < b;i++)
#define N 300004
#define INF 1e9+7

using namespace std;

ll n,dp[N][3],ar[N][3];

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

    cin >> n;

    rep(i,1,n+1)
    {
        cin >> ar[i][0] >> ar[i][1] >> ar[i][2];
    }

    rep(i,1,n+1)
    {
        rep(j,0,3)
        {
            dp[i][j] = 0;

            rep(k,0,3)
            {
                if(j == k)
                    continue;
                dp[i][j]=max(dp[i][j],dp[i-1][k]+ar[i][j]);
            }
        }
    }

    ll ans = max({dp[n][0],dp[n][1],dp[n][2]});
    cout << ans;

    return 0;
}


Measured memory_bytes: 8448
#include <bits/stdc++.h>
#define rep(i,a,n) for(int i=a;i<n;i++)
#define all(a) a.begin(),a.end()
#define o(a) cout<<a<<endl
#define int long long
using namespace std;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int,int> pii;

signed main(){
	int n;
	while(cin>>n && n>0){
		vvi d(n,vi(n,0)),f(n,vi(n,0));
		rep(i,0,n) rep(j,0,n) cin>>d[i][j];
		int a=0,b=0;
		rep(i,0,n){
			a=b=i;
			rep(j,0,n){
				if(d[i][a]>d[i][j]) a=j;
				if(d[b][i]<d[j][i]) b=j;
			}
			f[i][a]++;
			f[b][i]++;
		}
		int ans=0;
		rep(i,0,n){
			rep(j,0,n){
				if(f[i][j]==2){
					ans=max(ans,d[i][j]);
				}
			}
		}
		o(ans);
	}
}

Measured memory_bytes: 1212
import numpy as np
D = int(input())
C = np.array(list(map(int, input().split())))
S = np.zeros((D,26),int)
for i in range(0,D):
    S[i] = list(map(int, input().split()))

np.random.seed(seed=32)
Plan = np.random.randint(1,26,(D))
# print(Plan)
[print(i+1) for i in Plan]

Measured memory_bytes: 27496
#include <bits/stdc++.h>
#define ll long long int
#define forr(i,n) for(int i=0;i<n;i++)
#define mod 1000000007
#define oo 100000000000000000
using namespace std;



void _sol(){
    int n; cin >> n;
    vector<ll> v(n);
    for(auto &i: v) cin >> i;
    ll ans = 0;
    for(int i=1;i<n;i++){
        if(v[i] < v[i-1]){
            ans += v[i-1]  - v[i];
            v[i] = v[i-1];
        }
    }
    cout << ans;
}

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


Measured memory_bytes: 4696
#include <iostream>
using namespace std;
#define MAX 1000010
long long euler[MAX];
long long F[MAX];

void phi(){
  for(int i = 0; i < MAX; i++) euler[i] = i;
  for(int i = 2; i < MAX; i++){
    if(euler[i] == i){
      for(int j = i; j < MAX; j += i) euler[j] = euler[j] / i * (i-1);
    }
  }
}

int main(){
  phi();
  F[0] = F[1] = 2;
  for(int i = 2; i < MAX ; i++) F[i] = F[i-1] + euler[i];
  int t,n;
  cin >> t;
  for(int i = 0; i < t; i++){
    cin >> n;
    cout << F[n] << endl;
  }
  return 0;
}

Measured memory_bytes: 16780