akhauriyash/Code-Regression huggingface dataset:
import java.util.Scanner

import scala.collection.Searching._
import scala.annotation.tailrec
import scala.collection.immutable.Queue

class IUnionFind(val size: Int) {

  private case class Node(var parent: Option[Int], var treeSize: Int)

  private val nodes = Array.fill[Node](size)(new Node(None, 1))

  def union(t1: Int, t2: Int): IUnionFind = {
    if (t1 == t2) return this

    val root1 = root(t1)
    val root2 = root(t2)
    if (root1 == root2) return this

    val node1 = nodes(root1)
    val node2 = nodes(root2)

    if (node1.treeSize < node2.treeSize) {
      node1.parent = Some(t2)
      node2.treeSize += node1.treeSize
    } else {
      node2.parent = Some(t1)
      node1.treeSize += node2.treeSize
    }
    this
  }

  def connected(t1: Int, t2: Int): Boolean = t1 == t2 || root(t1) == root(t2)

  @tailrec
  private def root(t: Int): Int = nodes(t).parent match {
    case None => t
    case Some(p) => root(p)
  }
}


object Main {
  def solve(sc: => Scanner): Unit = {
    val K, A, B = sc.nextLong
    if (K <= A) {
      println(1)
    } else if (A <= B) {
      println(-1)
    } else {
      println(1 + ((K - A - 1) / (A - B) + 1) * 2)
    }
  }

  def main(args: Array[String]): Unit = {
    val sc: Scanner = new Scanner(System.in)
    solve(sc)
  }
}

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

typedef unsigned long long ull;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<double, double> pdd;
const ull mod = 1e9 + 7;
#define REP(i,n) for(int i=0;i<(int)n;++i)

//debug
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;

template<class S, class T> ostream& operator << (ostream& os, const pair<S, T> v){
  os << "(" << v.first << ", " << v.second << ")"; return os;
}
template<class T> ostream& operator << (ostream& os, const vector<T> v){
  for(int i = 0; i < v.size(); i++){if(i > 0){os << " ";} os << v[i];} return os;
}
template<class T> ostream& operator << (ostream& os, const vector<vector<T>> v){
  for(int i = 0; i < v.size(); i++){if(i > 0){os << endl;} os << v[i];} return os;
}

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

    ll N, A, B, C, D;
    cin >> N >> A >> B >> C >> D;
    A--, B--, C--, D--;
    string S;
    cin >> S;

    bool flag1 = true;
    bool flag2 = true;
    bool flag3 = false;
    for(int i=A;i<C;i++){
    	if(S[i] == '#' && S[i+1] == '#') flag1 = false;
    }
    for(int i=B;i<D;i++){
    	if(S[i] == '#' && S[i+1] == '#') flag2 = false;
    }
    for(int i=B;i<=D;i++){
    	if(S[i-1] == '.' && S[i] == '.' && S[i+1] == '.') flag3 = true;
    }
    //dump(flag1)
    //dump(flag2)
    //dump(flag3)
    if(C<D){
    	cout << (flag1 && flag2 ? "Yes" : "No") << endl;
    }else{
    	cout << (flag1 && flag2 && flag3 ? "Yes" : "No") << endl;
    }
    return 0;
}

Measured memory_bytes: 592
#include <bits/stdc++.h>
using namespace std;
 
int main()
{
    int n;
    cin >> n;
    vector<pair<long long int,long long int>> v;
    for(int i=0;i<n;i++)
    {
        int x,y;
        cin >> x >> y;
        v.push_back({x+y,x-y});
    }
    sort(v.begin(),v.end());
    int ans=1;
    int lrange=v[0].first;
    for(int i=1;i<n;i++)
    {
        if(v[i].second>=lrange)
        {++ans;lrange=v[i].first;}
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 2420
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int a,b,c,d;
  
  cin >> a >> b >> c >> d;
  
  if (a+b > c+d ) {
      cout << "Left" << endl;
  }else if (a+b == c+d ) {
  	  cout << "Balanced" << endl;
  }else {
  	  cout << "Right" << endl;
  }
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define PB push_back
#define MP make_pair
//#define REP(i,a,b) for(int i=a;i<=b;i++)

typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> pi;
long long MOD=1e9+7;
int main()
{	
	ios_base:: sync_with_stdio(0);
	cin.tie(0);
	//freopen("input.txt","r",stdin);
	//freopen("output.txt","w",stdout);
	double l,v;
	cin>>l;
	v = (double) (pow(l,3)/27);
	printf("%0.8lf",v);
}


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

#define int long long
#define pb push_back
#define f first
#define s second
#define all(container) container.begin(),container.end()

#define fast ios::sync_with_stdio(0); cin.tie(0)
#define print(...) __f(#__VA_ARGS__, __VA_ARGS__)

template <typename Arg1> void __f(const char* name, Arg1&& arg1){
  cout << name << ": " << arg1 << '\n';
}

template <typename Arg1, typename... Args> void __f(const char* names, Arg1&& arg1, Args&&... args){
  const char* comma = strchr(names + 1, ',');cout.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...);
}

int32_t main(){
    
  fast;
  int n; cin >> n;
  int ar[n-1];

  for(int i=0;i<n-1;i++) cin >> ar[i];

  int ans[n] = {0};

  ans[0] = ans[1] = ar[0];

  for(int i=1;i<n-1;i++){
    if(ar[i]>max(ans[i],ans[i+1])){
      ans[i+1] = ar[i];
    }else{
      ans[i] = ans[i+1] = ar[i];
    }
  }

  int sum = 0;
  
  for(auto k : ans){
    sum+=k;
  }

  cout << sum;

 
  
  return 0;
} 

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

typedef long long int LL;
typedef long long int LLint;
typedef pair<int,int> intpair;
typedef pair<bool,bool> boolpair;
typedef pair<string,string> strpair;
typedef pair<LL,LL> LLpair;
typedef pair<double,double> doublepair;
typedef pair<float,float> floatpair;
typedef vector<int> intvector;
typedef vector<bool> boolvector;
typedef vector<string> strvector;
typedef vector<LL> LLvector;
typedef vector<double> doublevector;
typedef vector<float> floatvector;
#define Hardmode usleep(1.5 * 1000000);
#define ED return 0;
#define TEST cout << "OK" << endl;
#define UP(a,b) ((a+(b-1))/b)
#define SORT(vec) sort(vec.begin(),vec.end());
#define DOUBLECHANGE(count) cout << setprecision(count);
#define REV(vec) reverse(vec.begin(),vec.end());
#define ipow(x,y) LL(pow(x,y))
#define INF 999999999
const long long mod = 1000000007;

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N;
    cin >> N;
    vector<pair<long long int,pair<long long int,long long int>>> vec (N);
    for(int i = 0;i < N;i++){
    	cin >> vec[i].second.first >> vec[i].second.second >> vec[i].first;
    }
    SORT(vec);
    REV(vec);
    for(int x = 0;x < 101;x++){
    	for(int y = 0;y < 101;y++){
    		long long int h = -1;
    		bool test = true;
    		for(int i = 0;i < N;i++){
    			if(h == -1){
    				if(vec[i].first != 0){
    					h = abs(x-vec[i].second.first)+abs(y-vec[i].second.second)+vec[i].first;
    					continue;
    				}
    				else{
    					continue;
    				}
    			}
    			if(abs(x-vec[i].second.first)+abs(y-vec[i].second.second)+vec[i].first != h){
    				if(h < abs(x-vec[i].second.first)+abs(y-vec[i].second.second) && vec[i].first == 0){
    					continue;
    				}
    				test = false;
    				break;
    			}
    		}
    		if(test){
    			cout << x << " " << y << " " << h << endl;
    			ED;
    		}
    	}
    }
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){
	int a,b,c,d;
	cin>>a>>b>>c>>d;
	for(int i=1;;i++){
		if(c-i*b<=0){
			cout<<"Yes";
			break;
		}
		else if(a-i*d<=0){
			cout<<"No";
			break;
		}
	}
	return 0;
} 

Measured memory_bytes: 3588
#include <bits/stdc++.h>
#define maxn 100005
using namespace std;
struct Node{
    int to,next,val,col;
}q[maxn<<1];
struct Query{
    int id,col,dis,tag;
    Query(){}
    Query(int _id,int _col,int _dis,int _tag){
        id=_id,col=_col,dis=_dis,tag=_tag;
    }
};
vector<Query>vec[maxn];
int head[maxn],cnt=0;
void add_edge(int from,int to,int col,int val){
    q[cnt].to=to;
    q[cnt].val=val;
    q[cnt].next=head[from];
    q[cnt].col=col;
    head[from]=cnt++;
}
struct LCA{
#define LOG 20
    int ST[maxn<<1][LOG];
    int val[maxn<<1],depth[maxn<<1],first[maxn<<1],len;
    int cal(int x,int y){
        return depth[x]<depth[y]?x:y;
    }
    void dfs(int x,int fa,int dis){
        val[++len]=x,depth[len]=dis;
        first[x]=len;
        for(int i=head[x];i!=-1;i=q[i].next){
            int to=q[i].to;
            if(to==fa) continue;
            dfs(to,x,dis+1);
            val[++len]=x;
            depth[len]=dis;
        }
    }
    void init(int root){
        len=0;
        dfs(root,-1,1);
        for(int i=1;i<=len;i++) ST[i][0]=i;
        for(int j=1;(1<<j)<=len;j++){
            for(int i=1;i+(1<<j)-1<=len;i++){
                ST[i][j]=cal(ST[i][j-1],ST[i+(1<<(j-1))][j-1]);
            }
        }
    }
    int query(int x,int y){
        int l=first[x],r=first[y];
        if(l>r) swap(l,r);
        int k=log2(r-l+1);
        return val[cal(ST[l][k],ST[r-(1<<k)+1][k])];
    }
}lca;
int res[maxn],dis[maxn],Cnt[maxn];
void dfs(int x,int fa,int d){
    for(auto it:vec[x]){
        res[it.id]+=it.tag*(d-dis[it.col]+Cnt[it.col]*it.dis);
    }
    for(int i=head[x];i!=-1;i=q[i].next){
        int to=q[i].to;
        if(to==fa) continue;
        Cnt[q[i].col]++;dis[q[i].col]+=q[i].val;
        dfs(to,x,q[i].val+d);
        Cnt[q[i].col]--,dis[q[i].col]-=q[i].val;
    }
}
int main()
{
    int n,Q;
    memset(head,-1,sizeof(head));
    cnt=0;
    scanf("%d%d",&n,&Q);
    for(int i=1;i<n;i++){
        int from,to,cal,val;
        scanf("%d%d%d%d",&from,&to,&cal,&val);
        add_edge(from,to,cal,val);
        add_edge(to,from,cal,val);
    }
    lca.init(1);
    for(int i=1;i<=Q;i++){
        int cal,dis,from,to;
        scanf("%d%d%d%d",&cal,&dis,&from,&to);
        vec[from].push_back(Query(i,cal,dis,1));
        vec[to].push_back(Query(i,cal,dis,1));
        int LCA=lca.query(from,to);
        vec[LCA].push_back(Query(i,cal,dis,-2));
    }
    dfs(1,0,0);
    for(int i=1;i<=Q;i++){
        printf("%d\n",res[i]);
    }
    return 0;
}

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

public class Main {
    BufferedReader in;
    PrintWriter out;
    StringTokenizer tok = new StringTokenizer("");

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

    public void run() {
        try {
            in = new BufferedReader(new InputStreamReader(System.in));
            out = new PrintWriter(System.out);
            solve();
            in.close();
            out.close();
        } catch (Throwable t) {
            t.printStackTrace(System.err);
            System.exit(-1);
        }
    }

    String readString() throws IOException {
        while (!tok.hasMoreTokens()) {
            tok = new StringTokenizer(in.readLine());
        }
        return tok.nextToken();
    }

    int readInt() throws IOException {
        return Integer.parseInt(readString());
    }

    long readLong() throws IOException {
        return Long.parseLong(readString());
    }

    double readDouble() throws IOException {
        return Double.parseDouble(readString());
    }

    int found(int[][] all, int m, int x, int y){
        for(int i=0;i<m;i++)
            if(all[i][0] == x || all[i][0] == y || all[i][1] == x || all[i][1] == y)
                continue;
            else
                return i;
        return -1;
    }

    // solution
    public static int log2(int x)
    {
        return (int) (Math.log(x) / Math.log(2));
    }

    void solve() throws IOException {
        int n = readInt();
        int[] all = new int[n];
        int[] res = new int[n];
        for(int i=0;i<n;i++)
            all[i]=readInt();
        res[0]=0;
        for(int i=1;i<n;i++){
            int cost1 = Math.abs(all[i]-all[i-1]) + res[i-1];
            int cost2 = i==1? Integer.MAX_VALUE : Math.abs(all[i]-all[i-2]) + res[i-2];
            res[i]=Math.min(cost1, cost2);
        }
        System.out.println(res[n-1]);
    }
}


Measured memory_bytes: 30408
import sys
import math
import copy
import random
import itertools
from heapq import heappush, heappop, heapify
from functools import cmp_to_key
from bisect import bisect_left, bisect_right
from collections import defaultdict, deque, Counter
sys.setrecursionlimit(1000000)

# input aliases
input = sys.stdin.readline
getS = lambda: input().strip()
getN = lambda: int(input())
getList = lambda: list(map(int, input().split()))
getZList = lambda: [int(x) - 1 for x in input().split()]

INF = float("inf")
MOD = 10**9 + 7
divide = lambda x: pow(x, MOD-2, MOD)



def solve(n=None, s1=None, s2=None):
    s = getS()
    cnt = Counter(s)
    n = len(s)
    ans = 0
    for k, v in cnt.items():
        ans += v * (n - v)
        

    ans //= 2
    ans += 1

    print(ans)


def main():
    for _ in range(n):
        solve()
    return


if __name__ == "__main__":
    # main()
    solve()


Measured memory_bytes: 83808
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <algorithm>
#define p 998244353
using namespace std;

int n,m,i,j,k,ans;
int fac[1000005],fac_inv[1000005];

int C(int n,int m){return (long long)fac[n]*fac_inv[m]%p*fac_inv[n-m]%p;}
int Power(int a,int b)
{
	int ans=1;
	for(;b;b>>=1,a=(long long)a*a%p)if(b&1)ans=(long long)ans*a%p;
	return ans;
}

int main()
{
	scanf("%d%d",&n,&m);if(n>m)swap(n,m);
	for(fac[0]=i=1;i<=n+m;++i)fac[i]=(long long)fac[i-1]*i%p;
	for(i=0;i<=n+m;++i)fac_inv[i]=Power(fac[i],p-2);
	
	for(i=m-n;i<m;++i)ans=(ans+(long long)C(i+i-(m-n),i)*C(m+m-i-i,m-i))%p;
	ans=((long long)ans*Power(2,p-2)%p*Power(C(n+m,n),p-2)+m)%p;
	printf("%d\n",ans);
}

Measured memory_bytes: 8064
#include <bits/stdc++.h>
#define all(v) (v).begin(),(v).end()
#define rep(i,n) for (int i = 0; i < (n); ++i)
using namespace std;
using LL = long long;
const int INF = 1e9;

int main(void) {
    int N, K;
    int R, S, P;
    string T;
    cin >> N >> K;
    cin >> R >> S >> P;
    cin >> T;
    vector<int> E;
    vector<int> H;
    for (auto&& t : T) {
        if (t == 'r') {E.push_back(0); H.push_back(2); }
        if (t == 's') {E.push_back(1); H.push_back(0); }
        if (t == 'p') {E.push_back(2); H.push_back(1); }
    }

    for (size_t i = K; i < T.size(); i++) {
        if (H[i] == H[i-K]) {
            H[i] = (H[i]+1)%3;
            if (i+K < T.size() && H[i] == H[i+K]) {
                H[i] = (H[i]+1)%3;
            }
        }
    }
    int point = 0;
    for (size_t i = 0; i < T.size(); i++) {
        if (E[i] == 0 && H[i] == 2) point += P;
        if (E[i] == 1 && H[i] == 0) point += R;
        if (E[i] == 2 && H[i] == 1) point += S;
    }
    cout << point << endl;
}



Measured memory_bytes: 1404
n[M];main(i,j){n[0]=n[1]=1;for(i=2;i<M;i++)if(!n[i])for(j=i*2;j<M;j+=i)n[j]=1;for(;~scanf("%d",&i);printf("%d %d\n",i,j)){for(j=i+1,i--;n[i];i--);for(;n[j];j++);}return 0;}

Measured memory_bytes: 0
// https://beta.atcoder.jp/contests/abc071

#define SUBMIT
#include <bits/stdc++.h>
using namespace std;


int main() {
#ifdef SUBMIT
    auto& stream = cin;
#else
    stringstream stream(R"(10
3 3 3 3 4 4 4 5 5 5
)");
#endif
    // (side, count)
    map<int, int> sides;
    int N, A;
    stream >> N;
    for (int i = 0; i < N; ++i) {
        stream >> A;
        sides[A]++;
    }

    int select = 0;
    uint64_t area = 1;
    for (auto it = sides.rbegin(); it != sides.rend(); ++it) {
        if (select == 2) break;
        while (2 <= it->second) {
            area *= it->first;
            it->second -= 2;

            select++;
            if (select == 2) break;
        }
    }
    if (select == 2) cout << area << endl;
    else cout << "0" << endl;
    return 0;
}

Measured memory_bytes: 4992
#include<iostream>
#include<iomanip>
#include<functional>
#include<algorithm>
#include<string>
#include<vector>
#include<utility>
#include<tuple>
#include<map>
#include<set>
#include<queue>
#include<cmath>

using namespace std;
#define LL long long

double R;

int main() {
	cin>>R;
	cout<<setprecision(10)<<R*2.0*3.14159265<<endl;
	return 0;
}



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

public class Main {
    public static final long mod = (long)1e9+7;
    public static final int inf = Integer.MAX_VALUE/10;
    public static ArrayList<String> list;
    public static int k;
    static void solve(InputReader in, PrintWriter out){
        k = in.ni();
        list = new ArrayList<>();
        dfs("a", 0);
        Collections.sort(list);
        for (int i = 0; i < list.size(); i++) {
            out.println(list.get(i));
        }
    }
    public static void dfs(String s, int a){
        if(s.length()==k){
            list.add(s);
            return;
        }else{
            for (int i = 0; i <= a+1; i++) {
                dfs(s.concat(String.valueOf((char)(i+'a'))), Math.max(a,i));
            }
        }
    }

    public static void main(String[] args) throws Exception{
        InputReader in = new InputReader(System.in);
        PrintWriter out = new PrintWriter(System.out);
        solve(in, out);
        out.close();
    }
    public static class InputReader{
        private BufferedReader br;
        private StringTokenizer st;
        public InputReader(InputStream is){
            br = new BufferedReader(new InputStreamReader(is));
            st = null;
        }
        public String ns(){
            if(st == null || !st.hasMoreTokens()){
                try{
                    st = new StringTokenizer(br.readLine());
                }catch (Exception e){
                    throw new RuntimeException(e);
                }
            }
            return st.nextToken();
        }
        public long nl(){
            return Long.parseLong(ns());
        }
        public int ni(){
            return Integer.parseInt(ns());
        }
        public Double nd(){
            return Double.parseDouble(ns());
        }
        public int[] ni(int n){
            int[] a = new int[n];
            for (int i = 0; i < n; i++) {
                a[i] = ni();
            }
            return a;
        }
        public long[] nl(int n){
            long[] a = new long[n];
            for (int i = 0; i < n; i++) {
                a[i] = nl();
            }
            return a;
        }
        public double[] nd(int n){
            double[] a = new double[n];
            for (int i = 0; i < n; i++) {
                a[i] = nd();
            }
            return a;
        }
    }
}

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

A_list = list(map(int, input().split())) # case1 : [7, 6, 8]

def gcd(a, b):
    while b != 0:
        a, b = b, int(a%b)
    return a

left_gcd = [0] * (N+1)
right_gcd = [0] * (N+1)
for i in range(N):
    left_gcd[i+1] = gcd(A_list[i], left_gcd[i])
for i in range(N-1, 0, -1):
    right_gcd[i] = gcd(A_list[i], right_gcd[i+1])

ans = 0

for i in range(N):
    i_gcd = gcd(left_gcd[i], right_gcd[i+1])
    if ans < i_gcd:
        ans = i_gcd

print(ans)

Measured memory_bytes: 14436
while True:
    try:
        n = tuple(map(int,raw_input()))
    except EOFError:
        break
    tmp=list(n)
    while len(tmp)>1:
        tmp2 = [(tmp[i]+tmp[i+1])%10 for i in range(len(tmp)-1)]
        tmp = tmp2
    else:
        print tmp[0]

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

int32_t main() {

	int n; cin >> n; 
	string str; cin >> str;

	int i = 0, j = str.length() - 1, count = 0;

	while(i < j) {

		if(str[i] == 'W' && str[j] == 'R') {
			count ++;
			i ++;
			j --;
		}

		else if(str[i] == 'W' && str[j] == 'W')
			j --;

		else if(str[i] == 'R' && str[j] == 'R')
			i ++;
		else {
			i ++;
			j --;
		}
	}

	cout << count << endl;
}

Measured memory_bytes: 3756
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)n; ++i)
#define repi(i, a, b) for (int i = int(a); i < int(b); ++i)
#define repr(i, n) for (int i = (int)n - 1; i >= 0; --i)
#define ALL(a) (a).begin(), (a).end()
using ll = long long;
using Graph = vector<vector<int>>;
const ll MOD = 1e9 + 7;
const ll INF = 1e9;
const ll LINF = 1LL << 60;

int main() {
  string s;
  cin >> s;
  ll cur = 0, m = 1;  // mは桁目に対応するmod2019の増加量
  map<int, int> mp;
  mp[0]++;
  repr(i, s.length()) {
    ll a = s[i] - 48;
    cur = (cur + m * a) % 2019;
    m = (m * 10) % 2019;
    mp[cur]++;
  }
  ll ans = 0;
  for (auto m : mp) {
    ans += m.second * (m.second - 1) / 2;
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 3756
code="""
#include <bits/stdc++.h>
using namespace std;

#define dump(...) cout<<"# "<<#__VA_ARGS__<<'='<<(__VA_ARGS__)<<endl
#define repi(i,a,b) for(int i=int(a);i<int(b);i++)
#define peri(i,a,b) for(int i=int(b);i-->int(a);)
#define rep(i,n) repi(i,0,n)
#define per(i,n) peri(i,0,n)
#define all(c) begin(c),end(c)
#define mp make_pair
#define mt make_tuple

typedef unsigned int uint;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef vector<string> vs;

template<typename T1,typename T2>
ostream& operator<<(ostream& os,const pair<T1,T2>& p){
	return os<<'('<<p.first<<','<<p.second<<')';
}

template<typename Tuple>
void print_tuple(ostream&,const Tuple&){}
template<typename Car,typename... Cdr,typename Tuple>
void print_tuple(ostream& os,const Tuple& t){
	print_tuple<Cdr...>(os,t);
	os<<(sizeof...(Cdr)?",":"")<<get<sizeof...(Cdr)>(t);
}
template<typename... Args>
ostream& operator<<(ostream& os,const tuple<Args...>& t){
	print_tuple<Args...>(os<<'(',t);
	return os<<')';
}

template<typename Ch,typename Tr,typename C,typename=decltype(begin(C()))>
basic_ostream<Ch,Tr>& operator<<(basic_ostream<Ch,Tr>& os,const C& c){
	os<<'[';
	for(auto i=begin(c);i!=end(c);++i)
		os<<(i==begin(c)?"":" ")<<*i;
	return os<<']';
}

constexpr int INF=1e9;
constexpr int MOD=1e9+7;
constexpr double EPS=1e-9;

int dfs(const vvi& g,int u)
{
	int res=1<<u;
	for(int v:g[u]) res|=dfs(g,v);
	return res;
}

int main()
{
	for(int n,m;cin>>n>>m && n|m;){
		array<int,20> cs;
		vvi g(n);
		rep(i,n){
			cin>>cs[i];
			int k; cin>>k;
			rep(j,k){
				int r; cin>>r;
				g[i].push_back(r);
			}
		}

		array<int,20> bs;
		rep(i,n) bs[i]=dfs(g,i);

		static array<int,1<<20> sums; sums.fill(0);

		rep(i,n) sums[1<<i]=cs[i];
		rep(i,1<<n) sums[i]=sums[i&-i]+sums[i-(i&-i)];

		int res=INF;
		rep(i,1<<n) if(__builtin_popcount(i)<res){
			int b=0;
			rep(j,n) b|=(i>>j&1)*bs[j];
			if(sums[b]>=m) res=min(res,__builtin_popcount(b));
		}
		cout<<res<<endl;
	}
}
"""

import os,tempfile
(_,filename)=tempfile.mkstemp(".cpp")

f=open(filename,"w")
f.write(code)
f.close()

os.system("g++ -std=c++0x {} -o ./a.out".format(filename))
os.system("./a.out")

Measured memory_bytes: 115484
#include <iostream>
#include <algorithm>
using namespace std;
int main(){
    int n; cin >> n;
    int a[n+1];
    for (int i=0; i<n; i++) cin >> a[i];
    sort(a, a+n);
    int suma=0, sumb=0;
    for (int i=0; i<n; i++){
        if (i%2==0) suma += a[n-i-1];
        else sumb += a[n-i-1];
    }
    int ans = suma - sumb;
    cout << ans << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
long double dp[3009][3009],a[3009];
int n;
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i];
    dp[0][0]=1;
    for(int i=1;i<=n;i++)
    {
        for(int j=0;j<=i;j++)
        {
            dp[i][j]=dp[i-1][j]*(1.0-a[i]);
            if(j==0)continue;
            dp[i][j]+=dp[i-1][j-1]*a[i];
        }
    }
    long double ans=0;
    for(int j=n/2+1;j<=n;j++)ans+=dp[n][j];
    cout<<setprecision(10)<<fixed<<ans<<"\n";
    /*for(int i=0;i<n+1;i++)
    {
        for(int j=0;j<=i;j++)
        {
            cout<<dp[i][j]<<" ";
        }
        cout<<"\n";
    }*/
}


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

ll EX_GCD(ll a, ll b, ll& x, ll& y) {
	ll d = a;
	if (b != 0) {
		d = EX_GCD(b, a % b, y, x);
		y -= (a / b) * x;
	}
	else {
		x = 1;
		y = 0;
	}
	return d;
}

int main()
{
	ll a, b, d;
	while (cin >> a >> b >> d, a | b | d) {
		ll cx, cy;
		ll gcd = EX_GCD(a, b, cx, cy);
		a /= gcd; b /= gcd; d /= gcd;
		cx *= d, cy *= d;
		ll x = cx, y = cy;
		for (ll i = -100000; i <= 100000; i++) {
			if (abs(cx + b * i) + abs(cy - a * i) < abs(x) + abs(y) || (abs(cx + b * i) + abs(cy - a * i) == abs(x) + abs(y) && abs(cx + b * i) * a + abs(cy - a * i) * b < abs(x) * a + abs(y) * b)) {
				x = cx + b * i;
				y = cy - a * i;
			}
		}
		cout << abs(x) << ' ' << abs(y) << endl;
	}
	return 0;
}

Measured memory_bytes: 3032
#include "bits/stdc++.h"

using namespace std;


int main(int argc, char* argv[]){
    long long N;
    scanf("%lld", &N);

    long long answer = N + 5;
    for (long long i=1; i * i <= N; i++) {
        if (N % i == 0) {
            answer = min(answer, i + (N / i));
        }
    }

    printf("%lld\n", answer - 2);
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#include <math.h>
#include <iomanip>
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; }
const int INF=1001001001;
vector<pair<int64_t,int64_t>>prime_factorize(int64_t x){
  vector<pair<int64_t,int64_t>>p;
  for(int64_t i=2;i*i<=x;i++){
    int cnt=0;
    if(x%i==0){
    while(x%i==0){cnt++;x/=i;}
    p.push_back(make_pair(i,cnt));
    }
  }
  if(x!=1){p.push_back(make_pair(x,1));}
  return p; 
}

int main() {
  int64_t N;
  cin>>N;
  string t;
  int64_t x=N;
  while(x){
    x--;
    int k=x%26;
    t=(char)(k+'a')+t;
    x/=26;
  }
  cout<<t<<endl;
  return 0;
}

Measured memory_bytes: 3632
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Main main = new Main();
        main.solve();
    }
    public void solve() {
        Scanner scan = new Scanner(new BufferedReader(new InputStreamReader(System.in)));
        int N = scan.nextInt();
        int[] a = new int[N];
        for (int i = 0; i < N; i++) {
            a[i] = scan.nextInt()-1;
        }
        int answer = 0;
        for (int i = 0; i < N; i++) {
            if (a[a[i]] == i) {
                answer += 1;
            }
        }
        System.out.println(answer/2);
    }
}


Measured memory_bytes: 50048
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.Scanner;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        Scanner in = new Scanner(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        Task solver = new Task();
        solver.solve(1, in, out);
        out.close();
    }

    static class Task {
        public void solve(int testNumber, Scanner in, PrintWriter out) {
            int[] array = new int[]{in.nextInt(), in.nextInt(), in.nextInt()};
            Arrays.sort(array);

            out.append(Arrays.equals(array, new int[]{5, 5, 7}) ? "YES" : "NO");
        }

    }
}



Measured memory_bytes: 21332
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
	string s;
	ll i,j,k,p=0;
	cin>>s;
	ll q;
	cin>>q;
	vector<char> v;

	ll rev=0;
	vector<char >fr;
	vector<char >br;
	//cin>>s;
	while(q--)
	{
		ll io;
		cin>>io;
		if(io==1)
		{
			rev++;
		}
		if(io==2)
		{
			ll iz;
			cin>>iz;
			if(iz==1)
			{
				
				char e;
				cin>>e;
				if(rev%2==0) fr.push_back(e);
				else br.push_back(e);
				
			
			}
			if(iz==2)
			{
				char e;
				cin>>e;
				if(rev%2==0) br.push_back(e);
				else fr.push_back(e);
				
			}
		}
	}
	for(i=fr.size()-1;i>=0;i--) v.push_back(fr[i]);
	for(i=0;i<s.size();i++) v.push_back(s[i]);
	for(i=0;i<br.size();i++) v.push_back(br[i]);
	if(rev%2==1) reverse(v.begin(),v.end());
	for(i=0;i<v.size();i++) cout<<v[i];
	
}

Measured memory_bytes: 1464
using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;

namespace AtCoder.A
{
    public class Program
    {
        public static void Main() { var r = GetResult(); Debug.WriteLine(r); Console.Write(r); }

        private static object GetResult()
        {
            var (A, B) = Read2Longs();
            return (A - 1) * (B - 1);
        }

        #region Console.Read

        public static string ReadText() { return Console.ReadLine(); }
        public static List<string> ReadTexts() { return Console.ReadLine().Split(' ').ToList(); }
        public static long ReadLong() { return long.Parse(Console.ReadLine()); }
        public static (long, long) Read2Longs() { var ls = ReadLongs(); return (ls[0], ls[1]); }
        public static (long, long, long) Read3Longs() { var ls = ReadLongs(); return (ls[0], ls[1], ls[2]); }
        public static (long, long, long, long) Read4Longs() { var ls = ReadLongs(); return (ls[0], ls[1], ls[2], ls[3]); }
        public static (long, long, long, long, long) Read5Longs() { var ls = ReadLongs(); return (ls[0], ls[1], ls[2], ls[3], ls[4]); }
        public static List<long> ReadLongs() { return Console.ReadLine().Split(' ').Select(x => long.Parse(x)).ToList(); }

        #endregion
    }
}


Measured memory_bytes: 28260
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <climits>
#include <cassert>
#include <iostream>
#include <iomanip>
#include <sstream>
#include <algorithm>
#include <numeric>
#include <complex>
#include <stack>
#include <queue>
#include <list>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <bitset>
#include <functional>
#include <iterator>

using namespace std;

#define dump(n) cout<<"# "<<#n<<'='<<(n)<<endl
#define repi(i,a,b) for(int i=int(a);i<int(b);i++)
#define peri(i,a,b) for(int i=int(b);i-->int(a);)
#define rep(i,n) repi(i,0,n)
#define per(i,n) peri(i,0,n)
#define foreach(i,c) for(auto i=(c).begin();i!=(c).end();++i)
#define all(c) begin(c),end(c)
#define mp make_pair

typedef unsigned int uint;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<vvi> vvvi;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef vector<string> vs;
typedef pair<int,int> pii;

const int INFTY=1<<29;
const double EPS=1e-9;

template<typename T1,typename T2>
ostream& operator<<(ostream& os,const pair<T1,T2>& p){
	return os<<'('<<p.first<<','<<p.second<<')';
}
template<typename T>
ostream& operator<<(ostream& os,const vector<T>& a){
	os<<'[';
	rep(i,a.size()) os<<(i?" ":"")<<a[i];
	return os<<']';
}

int main()
{
	for(int h,w,m;cin>>h>>w>>m && h|w|m;){
		vs grid(h);
		rep(i,h) cin>>grid[i];
		vvi con(h,vi(w)),on=con,off=con;
		rep(i,h) rep(j,w) cin>>con[i][j];
		rep(i,h) rep(j,w) cin>>on[i][j];
		rep(i,h) rep(j,w) cin>>off[i][j];
		
		vector<pii> order(m);
		for(pii& p:order) cin>>p.first>>p.second;
		
		vector<pii> path(1,order[0]);
		rep(o,m-1){
			vector<vector<pii>> prev(h,vector<pii>(w,mp(-1,-1)));
			prev[order[o].first][order[o].second];
			queue<pii> q; q.push(order[o]);
			while(q.size()){
				int ci,cj; tie(ci,cj)=q.front(); q.pop();
				rep(k,4){
					int ni=ci+"\xff\x1\0\0"[k],nj=cj+"\0\0\xff\x1"[k];
					if(ni<0 || h<=ni || nj<0 || w<=nj
					|| grid[ni][nj]=='#' || prev[ni][nj]!=mp(-1,-1))
						continue;
					prev[ni][nj]=mp(ci,cj);
					q.emplace(ni,nj);
				}
			}
			vector<pii> temp;
			for(pii p=order[o+1];p!=order[o];p=prev[p.first][p.second])
				temp.push_back(p);
			reverse(all(temp));
			path.insert(end(path),all(temp));
		}
		
		vvvi time(h,vvi(w));
		rep(i,path.size()) time[path[i].first][path[i].second].push_back(i);
		
		int res=0;
		rep(i,h) rep(j,w) if(time[i][j].size()){
			int tmp=on[i][j];
			rep(k,time[i][j].size()-1){
				int t1=time[i][j][k],t2=time[i][j][k+1];
				tmp+=min(off[i][j]+on[i][j],con[i][j]*(t2-t1));
			}
			tmp+=off[i][j];
			res+=tmp;
		}
		cout<<res<<endl;
	}
}

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

bool isEven(int *, int);
void divideBy2(int *, int);

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

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

  int counter = 0;
  while (true) {
    if (!isEven(A, N)) {
      break;
    }

    divideBy2(A, N);
    counter++;
  }

  cout << counter << endl;
}

bool isEven(int A[], int N) {
  for (int i = 0; i < N; i++) {
    if (A[i] % 2 != 0) return false;
  }
  return true;
}

void divideBy2(int A[], int N) {
  for (int i = 0; i < N; i++) {
    A[i] = A[i] / 2;
  }
}

Measured memory_bytes: 3572
N, M = map( int, input().split())
A = list( map( int, input().split()))
Needs = [0,2,5,5,4,5,6,3,7,6]
A.sort(reverse = True)
V = [0]*10
Check = []
for a in A:
    if V[Needs[a]] == 0:
        Check.append(Needs[a])
        V[Needs[a]] = a
Check.sort()
dp = [-100000]*(N+1)
dp[0] = 0

for x in Check:
    if x <= N:
        dp[x] = 1
for i in range(1,N):
    t = dp[i]
    for x in Check:
        if x + i <= N:
            if dp[x+i] < t + 1:
                dp[x+i] = t+1
ans = ""
t = N
W = [0]*10
while t > 0:
    for a in A:
        x = Needs[a]
        if t-x>=0:
            if dp[t-x]+1 == dp[t]:
                W[V[x]] += 1
                t -= x
                break
for i in range(9,0,-1):
    ans += str(i)*W[i]
print(ans)


Measured memory_bytes: 3312
#include<iostream>
#include<vector>
#include<queue>
#define PP std::pair<int,int>
int N, M;
int ans;
bool went[51];
std::vector<PP> G[51];
void bfs(int d) {
	std::queue<int> q;
	q.push(1);
	went[1] = true;
	while (!q.empty()) {
		int p = q.front();
		q.pop();
		for (auto u : G[p]) {
			if (u.first == d)continue;
			if (!went[u.second]) {
				went[u.second] = true;
				q.push(u.second);
			}
		}
	}
}
int main() {
	std::cin >> N >> M;
	for (int i = 1; i <= M; i++) {
		int a, b;
		std::cin >> a >> b;
		G[a].emplace_back(PP{ i,b });
		G[b].emplace_back(PP{ i,a });
	}
	for (int i = 1; i <= M; i++) {
		for (int j = 1; j <= N; j++) {
			went[j] = false;
		}
		bfs(i);
		for (int j = 1; j <= N; j++) {
			if (!went[j]) {
				ans++;
				break;
			}
		}
	}
	std::cout << ans << std::endl;
	return 0;
}

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

using namespace std;

#define INF 1000000007
#define LINF (1LL << 62)
#define PI 3.14159265358979

typedef long long i64;
typedef pair<i64,i64> P;

inline i64 mod(i64 a, i64 m) { return (a % m + m) % m; }

template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }



int n, g, a[11],b[11];
void solve(){
	cin >> n >> g;
	g /= 100;
	for(int i = 0; i < n; i++){
		cin >> a[i] >> b[i];
		b[i] /= 100;
	}
	
	int ans = INF;
	for(int i = 0; i < (1<<n); i++){
		int cnt = 0, score = g;
		for(int j = 0; j < n; j++){
			if(i>>j&1){
				cnt += a[j];
				score -= a[j]*(j+1) + b[j];
			}
		}
		for(int j = n-1; j >= 0; j--){
			if(score < 0) break;
			if(i>>j&1) continue;
			cnt += min((score+j)/(j+1),a[j]);
			score -= a[j]*(j+1);
			break;
		}
		if(score > 0) continue;
		chmin(ans,cnt);
	}
	cout << ans << endl;
}

int main(){
	std::cin.tie(0);
	std::ios::sync_with_stdio(false);
	int t = 1;
	//cin >> t;
	while(t--){
		solve();
	}
	
	return 0;
}

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

#define int long long
#define pb push_back
#define f first
#define s second
#define all(container) container.begin(),container.end()

#define fast ios::sync_with_stdio(0); cin.tie(0)

int32_t main(){
  
    fast;
    string s; cin >> s;
    string temp="";
    for(int i=0;i<s.size();i++){
      if(s[i]=='B'&&temp.size()>0) temp.pop_back();
      else if(s[i]!='B') temp+=s[i];
    }

    cout << temp;
 
    return 0;
} 

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


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

  set<pair<int, int>> S, T;
  rep(i, w) S.emplace(i, 0);
  rep(i, w) T.emplace(0, i);

  rep(k, h) {
    int a, b; cin >> a >> b;
    --a;

    auto l = S.lower_bound({a, -1});
    auto r = S.lower_bound({b, -1});

    int x = w;
    while (l != r) {
      auto [i, j] = *l;
      x = min(x, j-i+b);
      l = S.erase(l);
      T.erase({j, i});
    }

    if (x < w && b < w) S.emplace(b, x);
    if (x < w && b < w) T.emplace(x, b);

    int ans = -1;
    if (!T.empty()) ans = k+1 + T.begin()->first;
    printf("%d\n", ans);
  }
}


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

int K;
vector<int> answer = {1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51};
int main()
{
  cin >> K;
  cout << answer.at(K - 1) << endl;
}



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

int main(){
    int N;cin >> N;
    int V[N] = {};int C[N] = {};int X[N] = {};
    for (int i = 0;i < N;i++){
        cin >> V[i];
    }
    for (int i = 0;i < N;i++){
        cin >> C[i];
    }
    int ans = 0;
    for (int i = 0;i < N;i++){
        if (V[i] > C[i]) ans += (V[i] - C[i]);
    }
    cout << ans << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main(){
    int N,K,X,Y,i;
    cin >> N >> K >> X >> Y;
    int ans = 0;
    for (i = 1; i <= N; i++){
        if (i <= K){
            ans = ans + X;
        }else{
            ans = ans + Y;
        }
    }
    cout << ans << endl;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main()
{
	int a,b;
	scanf("%d%d",&a,&b);
	if(a+b==15){
		printf("+\n");
	}else if(a*b==15){
		printf("*\n");
	}else{
		printf("x");
	}
	return 0;
}

Measured memory_bytes: 256
import heapq
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)


def main():
    l = [-int(x) for x in input().split()]
    heapq.heapify(l)
    k = int(input())

    for _ in range(k):
        a = heapq.heappop(l) * 2
        heapq.heappush(l, a)

    ans = 0
    for x in l:
        ans += -x
    print(ans)


if __name__ == '__main__':
    main()


Measured memory_bytes: 3060
#include <stdio.h>
#include <string.h>
#include <math.h>
int main(void){
    
    char s[9];
    
    scanf("%s", s);
    
    if(s[0]=='S'){
        
        printf("Cloudy");
        return 0;
        
    }
    
    if(s[0]=='C'){
        
        printf("Rainy");
        return 0;
        
    }
    
    if(s[0]=='R'){
        
        printf("Sunny");
        return 0;
        
    }
    
    return 0;
    
}

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

const int N = 1e5 + 5, M = 2e5 + 5;

struct Graph
{
    int head[N], to[M << 1], next[M << 1], v[M << 1], cnt;

    inline void add_edge(int x, int y, int v_)
    {
        to[++cnt] = y, next[cnt] = head[x], v[cnt] = v_, head[x] = cnt;
    }
} e;
int n, m;

queue<int> q;
int dis[N];
bool vis[N];
bool spfa(int st)
{
    vis[st] = 1, dis[st] = 0, q.push(st);
    while (!q.empty())
    {
        int x = q.front();
        q.pop();
        for (R i = e.head[x]; i; i = e.next[i])
        {
            int u = e.to[i];
            if (vis[u])
            {
                if (dis[x] + e.v[i] != dis[u]) return false;
            }
            else dis[u] = min(dis[u], dis[x] + e.v[i]), vis[u] = 1, q.push(u);
        }
    }
    return true;
}

int main()
{
    memset(dis, 0x3f, sizeof dis);
    ios::sync_with_stdio(false);
    cin >> n >> m;
    for (R i = 1; i <= m; ++i)
    {
        int x, y, v;
        cin >> x >> y >> v;
        e.add_edge(x, y, v), e.add_edge(y, x, -v);
    }
    bool flag = true;
    for (R i = 1; i <= n; ++i)
        if (!vis[i] && !spfa(i)) { flag = false; break; }
    if (flag) cout << "Yes\n";
    else cout << "No\n";
    return 0;
}


Measured memory_bytes: 6272
import java.util.Scanner;

public class Main {
    public static void debug(String str) {
        System.out.println(str);
    }

    public static void main(String[] args) {

        int N;
        int[][] A;

        try (Scanner sc = new Scanner(System.in)) {
            N = sc.nextInt();
        }
        System.out.println(N*N*N);



    }

}


Measured memory_bytes: 21844
from collections import Counter
from collections import deque
from functools import reduce
from operator import mul
from pprint import pprint
import bisect
import copy
import fractions
import itertools
import math
import queue
import random
import sys
import time
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def MI(): return map(int, sys.stdin.readline().split())
def II(): return int(sys.stdin.readline())
def IS(): return input()
def C(x): return Counter(x)
def GCD_LIST(numbers): return reduce(fractions.gcd, numbers)
def LCM_LIST(numbers): return reduce(LCM, numbers)
def LCM(m, n): return (m * n // fractions.gcd(m, n))
def COMBINATION(n, r):
    if n < 0 or r < 0 or n < r:
        return 0
    r = min(n-r, r)
    if r == 0:
        return 1
    o = reduce(mul, range(n, n - r, -1))
    u = reduce(mul, range(1, r + 1))
    return o // u
class UnionFind():

    def __init__(self, n):
        self.n = n
        self.node = [i for i in range(n)]
        self.size = [1 for _ in range(n)]

    def same(self, x, y):
        return bool(self.root(x) == self.root(y))

    def root(self, x):
        if self.node[x] == x:
            return x
        else:
            self.node[x] = self.root(self.node[x])  # 経路圧縮
            return self.node[x]

    def unite(self, x, y):
        x, y = self.root(x), self.root(y)
        if x == y:
            return  # 結合不要
        if self.size[x] < self.size[y]:
            x, y = y, x
        self.node[y] = x
        self.size[x] += self.size[y]

    def return_size(self, x):
        return self.size[self.root(x)]


n = II()
cnt = 0
for i in range(1, n+1):
    if len(str(i)) % 2 == 1:
        cnt += 1
print(cnt)



Measured memory_bytes: 68076
#include <iostream>
#include <map>
#include <algorithm>
#include <vector>
#include <iomanip>
#include <sstream>
#include <cmath>
#include <math.h>
#include <string>
#include <queue>
#include <utility>
using namespace std;
typedef long long ll;
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n , d , x , c = 0;
    cin >> n >> d >> x;
	int a[n];
	for( int i = 0 ; i < n ; i++ ) cin >> a[i];
	for( int i = 0 ; i < n ; i++ ) {
		for( int j = 0 ; j <= ( d - 1 ) / a[i] ; j++ ) c++;
	} 
	cout << c + x;
} 

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

using namespace std;

#define PROBLEM "F"
#define TESTC ""

#define USE_CPPIO() ios_base::sync_with_stdio(0); cin.tie(0)
typedef pair<int, int> P;
#define F first
#define S second
#define INF 0x3f3f3f3f
#define MP make_pair
#define PB push_back
#define MAXN 100005

int main()
{
	#ifdef DBG
	freopen(PROBLEM TESTC ".in", "r", stdin);
	freopen(PROBLEM ".out", "w", stdout);
	#endif


	int c,times;

	while(~scanf("%d %d",&c,&times))
	{
		int arr[MAXN];
		int num[MAXN];
		for(int i = 0; i < MAXN; i++)
			arr[i] = i, num[i] = 1;
		while(times--)
		{
			int a,b,z;
			
			scanf("%d %d %d",&a,&b,&z);
			
			while(arr[a] != a)
			{
				a = arr[a];
			}

			while(arr[b] != b)
			{
				b = arr[b];
			}

			if(a != b)
			{
				c -= 1;
				if(num[a] > num[b])
				{
					//b老爸是a，a多了累贅
					arr[b] = a;
					num[a] += num[b];
				}
				else
				{
					arr[a] = b;
					num[b] += num[a];
				}
			}
			
		}

		printf("%d\n",c);
	}
	return 0;
}

Measured memory_bytes: 1024
#include<iostream>
#include<vector>

int main(){
    int n, ans = 0, tmp;
    
    std::cin >> n;

    std::vector<int> p(n), v(n);

    for(int i = 0; i < n; i++){
        std::cin >> p.at(i);
        v.at(i) = i + 1;
    }

   for(auto i = 0; i < n; i++){
       if(p.at(i) != v.at(i)){
           ans++;
       }
   }

    if(ans > 2){
        std::cout << "NO" << std::endl;
    }else{
        std::cout << "YES" << std::endl;
    }

    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <sstream>
#include <string>
#include <cmath>
#include <array>
#include <vector>
#include <set>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <utility>
#include <iomanip>
#include <numeric>
#include <climits>
#include <algorithm>
#include <cstdint>
using namespace std;

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

    vector<int> niz(n);
    for (int i = 0; i < n; i++)
        cin >> niz[i];

    int min = INT_MAX;
    for (int i = 0; i < n - 1; i++)
    {
        int first_sum = 0, second_sum = 0;
        for (int k = 0; k < i + 1; k++)
        {
            first_sum += niz[k];
        }
        for (int j = i + 1; j < n; j++)
        {
            second_sum += niz[j];
        }
        int x = abs(first_sum - second_sum);
        if (x < min)
            min = x;
    }
    cout << min;
}

Measured memory_bytes: 3620
#include <bits/stdc++.h>
using namespace std;
long long mod = 1e9+7;
int main()
{
    unsigned long long sum = 0 ;
    int n ;
    cin >> n ;
    long long arr[n+5]{};
    long long pre[n+5]{};
    for(int i = 0 ;i < n ; i++){
        cin >> arr[i];
        sum+=arr[i];
    }
    for(int i = 0 ; i < n ; i++){
        if(i==0)
            pre[i] = arr[i];
        else
            pre[i] = arr[i] + pre[i-1];
    }
    unsigned long long ans = 0 ;
    for (int i = 0 ; i < n ; i++){
        unsigned long long a = sum - pre[i];
        unsigned long long b = ( (arr[i]%mod) * (a%mod) )%mod;
        ans = ( (ans%mod) + (b%mod) )%mod;
    }
    cout << ans << endl;
    return 0;
}


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

string stringlower(string stra){
  for(int i = 0; i < stra.size(); i++){
    if(stra.at(i) >= 'A'&& stra.at(i) <= 'Z'){
      stra.at(i) = stra.at(i) - 'A' + 'a';
    }
  }
  return stra;
}
 
int main() {
  int count = 0;
  string w, t;
  cin >> w;
  while(t != "END_OF_TEXT"){
    cin >> t;
    if(stringlower(w) == stringlower(t)){
     count++;
    }
  }
  cout << count << endl;
}


Measured memory_bytes: 3172
#include<bits/stdc++.h>
#define pb push_back
#define pii pair<int,int>
#define F first
#define S second
#define MP make_pair
#define vii vector<pii>
#define vi vector<int>
#define ll long long
using namespace std;
int a,b,c;
int main()
{
	cin>>a>>b>>c;
	cout<<max(b+c-a,0)<<endl;
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0; i<(n); i++)
#define all(v) v.begin(),v.end()

using namespace std;
typedef long long ll;





int main()
{
    
    int N,M;
    cin >> N >> M;
    vector<pair<pair<int,ll>,int>> LRC(M);
    rep(i,M) cin >> LRC[i].first.first >> LRC[i].second >> LRC[i].first.second;
    
    sort(all(LRC));
    vector<ll> ans(N,-1);
    
    if(LRC[0].first.first == 1) ans[0] = 0;
    else{
        cout << -1 << endl;
        return 0;
    }
    
    int u = -1;
    int v = -1;
    
    for (int i = 0; i < M; i++) {
        //rep(i,N) cout << ans[i] << " ";
        //cout << endl;
        ll dd = 0;
        
        if(u != LRC[i].first.first){
            u = LRC[i].first.first;
            v = LRC[i].second;
            
            if(ans[u-1] != -1) dd = ans[u-1] + LRC[i].first.second;
            else{
                cout << -1 << endl;
                return 0;
            }
            
            for (int j = u; j < v; j++) {
                
                if(ans[j] == -1){
                    ans[j] = dd;
                    
                }else{
                    ans[j] = min(dd, ans[j]);
                    
                }
            }
        }else{
            int vv = LRC[i].second;
            if(ans[u-1] != -1) dd = ans[u-1] + LRC[i].first.second;
            else{
                cout << -1 << endl;
                return 0;
            }
            for (int j = v; j < vv; j++) {
                
                if(ans[j] == -1){
                    ans[j] = dd;
                }
                else{
                    ans[j] = min(dd, ans[j]);
                }
            }
            v = vv;
        }
    }
    
    //rep(i,N) cout << ans[i] << " ";
    //cout << endl;
    cout << ans[N-1] << endl;
    
    return 0;
}



Measured memory_bytes: 3328