akhauriyash/Code-Regression huggingface dataset:
class BinarySearchTree
	class Node
		attr_reader :key
		attr_accessor :parent, :left, :right
		def initialize(key, parent)
			@key = key
			@parent = parent
		end
	end

	attr_accessor :root

	def insert(key)
		parent  = nil
		current = @root
		while current
			parent = current
			if key < current.key
				current = current.left
			else
				current = current.right
			end
		end

		new_node = Node.new(key, parent)
		if !parent
			@root = new_node
		elsif key < parent.key
			parent.left = new_node
		else
			parent.right = new_node
		end
		self
	end

	def find(key)
		current = @root
		while current && current.key != key
			if key < current.key
				current = current.left
			else
				current = current.right
			end
		end
		current
	end

	def delete(key)
		target = find(key)
		return nil unless target
		delete_helper(target)
	end

	def keys_inorder
		inorder_helper(@root)
	end

	def keys_preorder
		preorder_helper(@root)
	end

	private
	def copy_node(node, new_key=nil)
		new_key ||= node.key

		copied = Node.new(new_key, node.parent)
		copied.left  = node.left
		copied.right = node.right
		copied
	end

	def replace(node, new_node)
		parent = node.parent
		new_node.parent = parent if new_node

		if !parent
			@root = new_node
		elsif parent.left && parent.left.key == node.key
			parent.left = new_node
		else
			parent.right = new_node
		end

		node
	end

	def delete_helper(node)
		if node.left && node.right
			next_node_index = inorder_helper(node.right).first
			next_node = find(next_node_index)

			copied = copy_node(node, next_node.key)
			node.right.parent = copied
			node.left.parent  = copied
			replace(node, copied)

			delete_helper(next_node)
			return node # 元々の削除対象を返したい為
		end

		return replace(node, node.left)  if node.left
		return replace(node, node.right) if node.right
		replace(node, nil)
	end

	def inorder_helper(node)
		return [] unless node
		result = []
		result.concat(inorder_helper(node.left))
		result << node.key
		result.concat(inorder_helper(node.right))
	end

	def preorder_helper(node)
		return [] unless node
		result = [node.key]
		result.concat(preorder_helper(node.left))
		result.concat(preorder_helper(node.right))
	end

end

tree = BinarySearchTree.new
n = STDIN.gets.to_i
n.times do
	command, param = STDIN.gets.split[0..1]
	if command == "insert"
		tree.insert(param.to_i)

	elsif command == "find"
		puts (tree.find(param.to_i) ? "yes" : "no")

	elsif command == "delete"
		tree.delete(param.to_i)

	elsif command == "print"
		puts " #{tree.keys_inorder.join(" ")}"
		puts " #{tree.keys_preorder.join(" ")}"

	else
		raise "Unexpected input #{command}, #{param}"
	end
end

Measured memory_bytes: 112360
/***************************************************************************
                                AUTHOR: SPARSH SINHA
            **************************************************************************/


#include <bits/stdc++.h>
using namespace std;
#define si(N) scanf("%d",&N);
#define sll(N) scanf("%lld",&N);
#define ss(s) scanf("%s",s);
#define ll long long
#define pi pair<int,int>
#define pll pair<ll,ll>
#define pb push_back
#define eb emplace_back
#define rep(i,a,b) for(int i = a; i<=b;i++)
#define fori(i,n) for(int i = 0 ; i < n; i++)
#define umapii unordered_map<int,int>
#define umapll unordered_map<ll,ll>
#define mapll map<ll,ll>
#define mapii map<int,int>
#define debug(x)       cerr<< #x <<" : "<<x<<endl;
#define debuga(A,N)    cerr<< #A <<" : [";for(int i = 0; i<N;i++) cerr<<A[i]<<" "; cerr<<"]\n";
#define debuga2(A,N,M) cerr<< #A << " : \n"; for(int i=0;i<N;i++){cerr<<"[";for(int j=0;j<M;++j) cerr<<A[i][j]<<" ";cerr<<"]\n";}
#define debugp(p)      cerr<< #p <<" : "<<"("<<(p).first<<","<<(p).second<<")\n";
#define debugv(v)      cerr<< #v <<" : "<<"[";for(int i = 0; i< (v).size(); i++) cerr<<v[i]<<" "; cerr<<"]\n";
#define debugv2(v)     cerr<< #v << " : \n"; for(int i=0;i<v.size();i++){cerr<<"[";for(int j=0;j<(v[0].size());++j) cerr<<v[i][j]<<" ";cerr<<"]\n";}
#define debugs(m)      cerr<< #m <<" : [ "; for(auto itr = m.begin(); itr!=m.end();itr++) cerr<<*itr<<" "; cerr<<"]\n";
#define debugm(m)      cerr<< #m <<" : [ "; for(auto itr = m.begin();itr!=m.end(); itr++) cerr<<"("<<itr->first<<","<<itr->second<<") ";cerr<<"]\n";
const int INF = 1e9 + 7;

int main()
{
              int mn = -1000000;
              int mx = 1000000;
               int K , X;
               cin >> K >> X;
              int r = min(X + K - 1 , mx);
              int l = max(X - K + 1 ,  mn);
              for(int i = l ; i <= r; i++){
                  cout << i << " "; 
              }
              cout << endl;
}


Measured memory_bytes: 256
#include <cstdio>
#include <functional>
#include <algorithm>
#include <vector>
#include <limits>
#include <numeric>
#include <type_traits>
#include <iostream>
#include <queue>
#include <math.h>
#include <bits/stdc++.h>
#include <queue>
#include <map>

using namespace std;

#define INF (1ll<<60)
#define INFint (1<<30)
#define MOD 1000000007
#define BOUND 27182818284

typedef long long ll;
typedef long long int lli;
// typedef pair<ll,ll> P;

#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)

template<class T>
bool umax(T &a, const T &b){
    if (a<b) {
        a=b; return true;
    }
    return false;
}

template<class T>
bool umin(T &a, const T &b) {
    if (b<a) {
        a=b; return true;
    }
    return false;
}

// gcd
template<typename T>
T gcd(T a, T b){
    if(a==0)
        return b;
    return gcd(b%a,a);
}

// gcd array
int findGCD(int arr[], int n){
    int result = arr[0];
    for (int i=1; i < n; i++)
        result = gcd(arr[i], result);
    return result;
}

template<typename T>
T lcm( T m, T n ){
    // 引数に0がある場合は0を返す
    if ( ( 0 == m ) || ( 0 == n ) )
        return 0;
    return ((m/gcd(m, n)) * n); // lcm = m * n / gcd(m,n)
}

template<typename A, size_t N, typename T>
void Fill(A (&array)[N], const T &val){
    fill( (T*)array, (T*)(array+N), val );
}


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

// v.front() = -BOUND;
// v.back() = BOUND;

//struct edge{
//    int cost, to;
//
//    edge(int in_cost, int in_to){
//        cost=in_cost;
//        to=in_to;
//    }
//    bool operator<(const edge &a) const
//    {
//        return cost > a.cost;
//    }
//};

ll value[110][100010]; // 添え字は重さに対応
int main() {
    int N,W; cin >> N >> W;
    vector<int>w(N),v(N);
    rep(i,N){
        cin >> w[i] >> v[i];
    }

    for(int i=0; i<=N; i++){
        for(int j=0; j<=W; j++){
            value[i][j]=-1;
        }
    }

    for(int i=0; i<=W; i++){
        value[0][i]=0LL;
    }

    for(int i=0; i<N; i++){
        for(int j=1; j<=W; j++){
            if(j-w[i]<0) {
                value[i+1][j]=value[i][j];
            }else{
                value[i+1][j]=max(value[i][j], value[i][j-w[i]]+v[i]);
            }
        }
    }

    cout << value[N][W] << endl;
    return 0;
}


Measured memory_bytes: 80128
let () =
    let split s =
        let rec loop i cur flag acc =
            if i = String.length s then ( if flag then cur :: acc else acc) else (
                match flag, s.[i] with
                | true,  ' ' -> loop (i + 1) "" false (cur :: acc)
                | false, ' ' -> loop (i + 1) "" false acc
                | true,  v   -> loop (i + 1) (Printf.sprintf "%s%c" cur v) true acc
                | false, v   -> loop (i + 1) (Printf.sprintf "%s%c" cur v) true acc
            )
        in
        List.map int_of_string (List.rev (loop 0 "" false []))
    in
    let main () =
        let n = int_of_string (read_line ()) in
        let l = split (read_line ()) in
        let l = Array.of_list l in
        Array.sort compare l;
        let hist = Array.make 1001 0 in
        for i = 0 to n - 1 do hist.(l.(i)) <- hist.(l.(i)) + 1 done;
        let accsum = Array.make 1001 0 in
        let rec loop i acc =
            if i < 1001 then (
                let acc = acc + hist.(i) in
                accsum.(i) <- acc;
                loop (i + 1) acc
            )
        in
        loop 0 0;
        (*
        let t = Array.make 1001 0 in
        for i = 1 to 1000 do
            t.(i) <- if l.(i) <> l.(i - 1) then 1 else t.(i - 1) + 1
        done;
        *)

        let rec loop_i i acc =
            let rec loop_j j acc =
                if j = n then acc else
                    let v = accsum.(min 1000 (l.(i) + l.(j) - 1)) - j - 1 in
                    loop_j (j + 1) (acc + v)
            in
            if i = n - 1 then acc else loop_i (i + 1) (loop_j (i + 1) acc)
        in
        let r = loop_i 0 0 in
        Printf.printf "%d\n" r
    in
    main ()

Measured memory_bytes: 4736
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int X = Integer.parseInt(sc.next());
		int Y = Integer.parseInt(sc.next());
		sc.close();

		int ans = X + Y / 2;
		System.out.println(ans);
	}
}

Measured memory_bytes: 21716
#include <stdio.h>

int main(void){
	int w, h, x, y;
	scanf("%d %d %d %d", &w, &h, &x, &y);
	double sum = (double)w * h / 2;
	int chk = (w == x * 2 && h == y * 2) ? 1 : 0;
	printf("%f %d\n", sum, chk);
	return 0;
}


Measured memory_bytes: 128
#define _CRT_SECURE_NO_WARNINGS
#define _USE_MATH_DEFINES
#include <iostream>
#include <iomanip>
#include <string>
#include <cmath>
#include <vector>
#include <algorithm>
#include <queue>
#include <functional>

using namespace std;

#define MOD 1000000007
#define INT_MAX

int main()
{
	string s;
	cin >> s;

	int a = -1;
	int z = -1;

	for (int i = 0; i < s.size(); i++) {
		if (s[i] == 'A' && a == -1) {
			a = i;
		}
		if (s[i] == 'Z') {
			z = i;
		}
	}
	cout << z - a + 1 << endl;

	return (0);
}

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

int main()
{
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int n;
    long long broj=1e18,g,p=1;
    bool tacno=true;
    cin >> n;
    for (int i=0;i<n;i++)
    {
        cin >> g;
        if(g==0)
        {p=0;tacno=true;break;}
        if(tacno)
        {
            if(g>broj/p) tacno=false;
            else p*=g;
        }
    }
    if(tacno)
        cout << p;
    else
        cout << -1;
}


Measured memory_bytes: 3592
s = input()
r = s[::-1]
n = len(s)
count = 0
if n % 2 == 0:
  t = n // 2
  for i in range(t):
    if s[i] != r[i]:
      count += 1
else:
  t = n // 2
  for i in range(t):
    if s[i] != r[i]:
      count += 1
print(count)


Measured memory_bytes: 3060
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<(int)n;i++)
int main() {
  int c[3][3],a[3],b[3];
  rep(i,3) rep(j,3) cin>>c[i][j];
  rep(i,c[0][0]+1){
    a[0]=i;
    rep(i,3) b[i]=c[0][i]-a[0];
    rep(i,2) a[i+1]=c[i+1][0]-b[0];
    rep(i,3) rep(j,3) if(c[i][j]!=a[i]+b[j]){cout<<"No"; return 0;}
  }
  cout<<"Yes";
}

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

const int N = int(1e6) + 5;
int _size[N], root[N];
int n;

void Init() {
    for (int i=1; i<=n; i++) {
        _size[i] = 1;
        root[i] = i;
    }
}

int GetRoot(int x) {
    while (root[x] != x) {
        root[x] = root[root[x]];
        x = root[x];
    }
    return x;
}

int Union(int a, int b) {
    int ra = GetRoot(a), rb = GetRoot(b);
    if (ra == rb) return 0;
    else {
        if (_size[ra] < _size[rb]) {
            root[ra] = root[rb];
            _size[rb] += _size[ra];
        } else {
            root[rb] = root[ra];
            _size[ra] += _size[rb];
        }
        return 1;
    }
}


void solve() {
    cin >> n;
    Init();
    int m;
    cin >> m;
    for (int a,b; m; m--) {
        cin >> a >> b;
        Union(a, b);
    }
    cout << *max_element(_size+1, _size + n+1) << '\n';
}

int main() {
    solve();
}

Measured memory_bytes: 5136
//containing t test cases
#include<bits/stdc++.h>
#define pb push_back
#define mod 1000000007
#define mkp make_pair
#define fi first
#define se second
#define ll long long
#define scan(n) ll a[n]; for(ll i = 0 ; i<n ; i++) cin>>a[i]
#define scan1(b,n) for(ll i = 0 ; i<n ; i++) cin>>b[i]
#define sortt(a) sort(a.begin(),a.end());
#define print(a,n) for(ll i = 0 ; i < n ; i++) cout<<a[i]<<' '
#define fast ios_base::sync_with_stdio(false); cin.tie(0);cout.tie(0);
#define rep(i,x,y) for(ll i=x;i<y;i++)
#define pi 3.1415926535897932384626433832795028841971
#define mem(a,b) memset(a , b , sizeof a ) ;
//#define int long long
using namespace std;
//typedef vector<int>vi ;
typedef vector<ll>vi ;
typedef vector<vector<ll> >vvl ; 
typedef pair<ll,ll> pll ;
typedef vector<pair<ll,ll> > vpll;
//cout<<fixed<<setprecision(15);
/*vi adj[200005];
ll vis[200005];
ll parent[200005];
ll level[200005];
ll arr[200005];
ll size[200005];*/
//endl mut bhool!!
void solve()
{
	ll n;
	cin>>n;
	if(n%1000==0)
	{
		cout<<"0"<<endl;
		return;
	}
	ll x=1000-(n%1000);
	cout<<x;
}
int main()
{
	fast;
	ll test=1;
	//cin>>test;
	while(test--)
	{
		solve();
	}
	return 0;
}
/*
cout<<"YES"<<endl;
cout<<"NO"<<endl;
*/

Measured memory_bytes: 3688
#include <cstdio>

using namespace std;

const int kMax = 100 + 5;

int n;
int num[kMax];

void print_num() {
    for(int i = 0;i < n;++ i) {
        if(i) printf(" ");
        printf("%d", num[i]);
    }
    printf("\n");
}

void solve() {
    print_num();
    for(int i = 1;i < n;++ i) {
        int j = i - 1;
        int key = num[i];
        while(j >= 0 && num[j] > key) {
            num[j + 1] = num[j];
            -- j;
        }
        num[j + 1] = key;
        print_num();
    }
}

int main() {
    scanf("%d", &n);
    for(int i = 0;i < n;++ i) scanf("%d", &num[i]);
    solve();
}

Measured memory_bytes: 2680
#include<iostream>
#include<string>
#include<functional>
#include<iomanip>
#include<climits>

using namespace std;
typedef unsigned long long int ll;

int main()
{
   string a, b;
   ll t;
   cin >> t;
   cin >> a >> b;
   for(ll i = 0; i < t; i++) cout << a[i] << b[i];
    return 0;
}


Measured memory_bytes: 256
n,m,q = list(map(int, input().split(' ')))
list1 = []
for i in range(q):
    list1.append(list(map(int, input().split(' '))))
def calc(a):
    global list1
    tot = 0
    for l in list1:
        if a[l[1]-1]-a[l[0]-1]==l[2]:
            tot += l[3]
    return tot

max1 = -1
def dfs(a=[]):
    global max1,n,m,q
    if(len(a)==n):
        c = calc(a)
        if c>max1:
            max1 = c
    else:
        start = a[-1] if a else 0
        for i in range(start, m):
            a.append(i)
            dfs(a)
            a.pop(-1)
dfs()
print(max1)


Measured memory_bytes: 78172
#include <iostream>
#include <string>
#include <vector>

template<class T>
T myMin(const T& arg){
	return arg;
}
template<class F, class... S>
F myMin(const F& first, const S&... second){
	F m = myMin(second...);
	if (m > first){
		return first;
	}else{
		return m;
	}
}
int f(std::string::iterator str1, const std::string& str2, const std::vector<int>& vec){
	std::vector<int> new_v;
	new_v.push_back(vec[0] + 1);
	{
		auto v = vec.begin() + 1;
		for (auto i = str2.begin(); i != str2.end(); ++i, ++v){
			if (*i == *str1){
				new_v.push_back(*(v - 1));
			}else{
				new_v.push_back(myMin(*v + 1, new_v.back() + 1));
			}
		}
	}
	if (*(++str1) != '\0'){
		return f(str1, str2, new_v);
	}else{
		return new_v.back();
	}
}
int main(){
	int n;
	std::cin >> n;
	for (int i = 0; i < n; ++i){
		std::string str1, str2;
		std::cin >> str1 >> str2;
		std::vector<int> vec;
    vec.push_back(0);
		for (int j = 0; j < str2.size(); ++j){
			vec.push_back(j);
		}
		std::cout << (str1.size() + str2.size() - f(str1.begin(), str2, vec)) / 2 << "\n";
	}
}

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

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

  if (N >= sum) {
    cout << N - sum << endl;
  } else {
    cout << -1 << endl;
  }
  return 0;
}


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

inline int gi()
{
	char c = getchar();
	while(c < '0' || c > '9') c = getchar();
	int sum = 0;
	while('0' <= c && c <= '9') sum = sum * 10 + c - 48, c = getchar();
	return sum;
}

const int maxn = 200005;

int n, a[maxn], p;

bool check(int t)
{
	for (int i = 2 * t + 1; i <= (n << 1); ++i)
		if (a[i] + a[((n + t) << 1) - i + 1] < p) return 0;
	return 1;
}

int main()
{
	n = gi(); p = gi();
	for (int i = 1; i <= (n << 1); ++i) a[i] = gi();
	sort(a + 1, a + n + n + 1);

	int l = 0, r = n, mid;
	while (l < r) {
		mid = (l + r) >> 1;
		if (check(mid)) r = mid;
		else l = mid + 1;
	}

	int ans = 0;
	for (int i = 1; i <= (l << 1); ++i) ans = max(ans, a[i] + a[(l << 1) - i + 1]);
	for (int i = (l << 1) + 1; i <= (n << 1); ++i) ans = max(ans, a[i] + a[((n + l) << 1) - i + 1] - p);
	printf("%d\n", ans);
	
	return 0;
}



Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define in insert
#define PI 3.1415926535897932384626433832795
#define MOD 100000007
#define F first
#define S second
#define aLL(str) (str).begin(), (str).end()
#define IOS                  \
	ios::sync_with_stdio(0); \
	cin.tie(0);              \
	cout.tie(0)
#define ll long long
#define ld long double
#define lcm(a, b) (a * b) / __gcd(a, b)
#define flu(i, a, b) for (ll i = a; i < b; i++)
#define blu(i, a, b) for (ll i = a; i >= b; i--)
#define upper(s) transform(s.begin(), s.end(), s.begin(), ::toupper)
#define lower(s) transform(s.begin(), s.end(), s.begin(), ::tolower)
#define Unique(X) (X).erase(unique(all(X)), (X).end())
#define all(v) v.begin(), v.end()
typedef vector<ll> vl;
typedef map<ll, ll> ml;
typedef vector<string> vs;
typedef vector<vector<int>> vvi;
char e = '\n';
ll i, j, le;

int main()
{
	IOS;
	int t;
	t=1;
	while (t--)
	{
	 ll n,c=0;
	 double d,x,y,an,x1,y1;
	 cin>>n>>d;
	 
	 flu(i,0,n)
	 {
		 cin>>x>>y;
		 an= sqrt((ld)pow((ld)x,2) + (ld)pow((ld)y,2));
		 if(an<=(ld)d)
		c++;
	 }
		
	 cout<<c<<e;
	}
	return 0;
}

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

using LL = long long;
using LD = long double;
using PII = pair<int, int>;
using PLL = pair<LL, LL>;
using VI = vector<int>;
using VVI = vector<vector<int>>;
template<class T> using V = vector<T>;
template<class T> using VV = vector<vector<T>>;
template<class T> inline void IN(T &x) {
	x = 0; T f = 1; char ch = getchar();
	while (!isdigit(ch)) { if (ch == '-') f = -1; ch = getchar(); }
	while (isdigit(ch)) { x = (x << 3) + (x << 1) + (ch ^ 48); ch = getchar(); }
	x *= f;
}
template<typename A, typename B> inline void IN(A &x, B &y) { IN(x); IN(y); }
template<typename A, typename B, typename C> inline void IN(A &x, B &y, C &z) { IN(x); IN(y); IN(z); }

#define FastI ios_base::sync_with_stdio(0), cin.tie(0);
#define FastIO ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);
#define endl '\n'
#define REP(i, l, r) for (auto i = (l); i <= (r); ++i)
#define PER(i, l, r) for (auto i = (l); i >= (r); --i)
#define FOR(i, l, r) for (auto i = (l); i < (r); ++i)
#define ROF(i, l, r) for (auto i = (l); i > (r); --i)
#define FORN(i, n) for (auto i = 0; i < (n); ++i)
#define REPN(i, n) for (auto i = 1; i <= (n); ++i)
#define FORA(i, a) for (auto &i : a)
template<class T> void cout_1d(T &v) { FORA(i, v) cout << i << " "; puts(""); }
template<class T> void cout_2d(T &vv) { FORA(v, vv) cout_1d(v); }
#define ALL(X) (X).begin(), (X).end()
#define RALL(X) (X).rbegin(), (X).rend()
#define SIZE(X) ((int)(X).size())
#define UNIQUE(x) (X).erase(unique(ALL(x), (X).end())
#define ZERO(a) memset(a, 0, sizeof(a))
#define NEG1(a) memset(a, -1, sizeof(a))
#define MAXA(a) memset(a, 0x3f, sizeof(a))
#define MAXB(b) memset(b, 0x7f, sizeof(b))
#define MP make_pair
#define PB push_back
#define X first
#define Y second

const LD PI = acos(-1.0);
const LL MOD = 998244353;
//const LL MOD = 1e9+7;
const LL MAXN = 2e5 + 7;

int h[MAXN];
void solve1() {
	int N;  IN(N);
	REPN(i, N) IN(h[i]);
	VI dp(N+1, 0);  dp[2] = abs(h[2] - h[1]);
	REP(i, 3, N) dp[i] = min(dp[i-1] + abs(h[i] - h[i-1]), dp[i-2] + abs(h[i] - h[i-2]));
	cout << dp[N] << endl;
}

void solve2() {
	int N, K;  IN(N, K);
	REPN(i, N) IN(h[i]);
	VI dp(N+1, INT_MAX);
	dp[1] = 0;
	REP(i, 2, N) REP(j, 1, K) // if (j >= i) break;
		dp[i] = min(dp[i], i <= j ? INT_MAX : dp[i-j] + abs(h[i] - h[i-j]));
	cout << dp[N] << endl;
}

int main() {
#ifdef _DEBUG
    freopen("../in.txt", "r", stdin);
    freopen("../out.txt", "w", stdout);
#endif
    FastI

	solve1();
	// solve2();

    return 0;
}


Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
 
long long gcd(long x,long y){
    if(y==0)return x;

    return gcd(y,x%y);
}
long long lcm(long x,long y){
    return x*y/gcd(x,y);
}

int ctoi(char c) {
	if (c >= '0' && c <= '9') {
		return c - '0';
	}
	return 0;
}

int main()
{
    int N,ans=1;
    string S;
    cin>>N>>S;

    for(int i=1;i<N;i++){
        if(S[i]!=S[i-1])ans++;
    }

    cout<<ans<<endl;

    return 0;
}

Measured memory_bytes: 512
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<b;i++)
#define rrep(i,a,b) for(int i=a;i>=b;i--)
#define fore(i,a) for(auto &i:a)
#define all(x) (x).begin(),(x).end()
//#pragma GCC optimize ("-O3")
using namespace std;

int main() {
  
  int a,b,c,d,x;
  long long la,lb;
  double da,db;
  string s,ss,sss;
  
  int ans = 0;
  string anss = "";
  
  cin >> la >> lb;
  
  int ab [] = {0 , 1 , 3 , 1 , 2 , 1 , 2 , 1 , 1 , 2 , 1 , 2 , 1};
  int result3 = std::max({a, b, c});
//--------------------------------------------------------------------------------

  if((la+lb)%2 == 0) cout << (la+lb)/2 << endl;
  else cout << "IMPOSSIBLE" << endl;

  //cout << a*a*3 << endl;

}

Measured memory_bytes: 256
#pragma warning(disable:4996)
#include<iostream>
#include<stdio.h>
#include<sstream>
#include<cmath>
#include<stack>
#include<vector>
#include<string>
#include<algorithm>
#include<queue>
#include<map>
#include<set>
#include<limits.h>
using namespace std;
using ll = long long int;
inline ll get(ll i) {
	return (i + 1) * i / 2;
}
int main() {
	ll N;
	cin >> N;
	ll NDT = get(N / 3) * 3, NDF = get(N / 5) * 5, NDFIT = get(N / 15) * 15,
		FN = get(N);
	cout << FN - NDT - NDF + NDFIT;
	return 0;
}

Measured memory_bytes: 3196
import sys
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import bellman_ford, connected_components
from scipy.sparse.csgraph._shortest_path import NegativeCycleError

input = sys.stdin.buffer.readline


N, M = map(int, input().split())
starts = []
ends = []
costs = []
for _ in range(M):
    a, b, c = map(int, input().split())
    starts.append(a-1)
    ends.append(b-1)
    if c != 0:
        costs.append(-c)
    else:
        costs.append(sys.float_info.epsilon)

look_for_loop = csr_matrix((costs + [0], (starts + [N-1], ends + [0])), shape = (N, N))
_, labels = connected_components(look_for_loop, connection = "strong")
mask = (labels == labels[0])

graph = csr_matrix((costs, (starts, ends)), shape = (N, N)).toarray()
graph = graph[mask, :][:, mask]

try:
    ans = bellman_ford(graph, directed = True, indices = [0])[0][-1]
    ans = int(round(-ans))
except NegativeCycleError:
    ans = "inf"

print(ans)


Measured memory_bytes: 40240
#include <iostream>
#include <algorithm>

using namespace std;

int n, m, ans, table[9][9];

int chack(){
	int res=1;
	for(int i=0; i<n; i++){
		int tmp=0;
		for(int j=0; j<n; j++){
			tmp += table[i][j];
		}
		if(tmp){
			res = 0;
			break;
		}
	}
	return res;
}


void solve(int x, int y){
	if(y < n-1) y++;
	else if(x < n-1){
		y=0;
		x++;
	} else {
		ans += chack();
		return;
	}
	
	if(y==0 && x>0){
		int tmp =0;
		for(int i=0; i<n; i++){
			//cout << table[x-1][i] << " ";
			tmp +=table[x-1][i];
		}
		//cout << endl;
		if(tmp) return;
	}
	

	if(table[x][y] == 0 && x != y){
		table[x][y] = 1;
		table[y][x] = -1;

		solve(x, y);

		table[x][y] = -1;
		table[y][x] = 1;
		solve(x, y);

		table[x][y] = table[y][x] = 0;
	} else solve(x, y);
}


int main(void) {
	while(1) {
		cin >> n;
		if(!n) break;
		fill(table[0], table[8], 0);
		cin >> m;
		for(int i=0; i<m; i++){
			int x, y; cin >> x >> y;
			x--; y--;
			table[x][y] = 1;
			table[y][x] = -1;
		}
		int x, y;
		for(int i=0; i<n; i++){
			for(int j=0; j<n; j++){
				if(table[i][j]==0 && i != j){
					x = i;
					y = j-1;
					goto AA;
				}
			}
		}
	AA:

		ans = 0;
		solve(x, y);
		cout << ans << endl;
	}
}


Measured memory_bytes: 3100
def main(S, T):
    ans = len(T)
    for w in range(len(S)-len(T)+1):
        tmp = len(T)
        for s, t in zip(S[w:w+len(T)], T):
            if s == t:
                tmp -= 1
        if tmp < ans:
            ans = tmp
    return ans

if __name__ == '__main__':
    S = input()
    T = input()
    ans = main(S, T)
    print(ans)



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

#pragma GCC optimize("O3")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
//(UNCOMMENT WHEN HAVING LOTS OF RECURSIONS)
#pragma comment(linker, "/stack:200000000")
//(UNCOMMENT WHEN TRYING TO BRUTEFORCE WITH A LOT OF LOOPS)
#pragma GCC optimize("unroll-loops")

#define DEBUG(x) cout << ">> " << #x << ": " << x << endl;
#define _ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
typedef long long ll;
typedef long double ld;
const ll MOD = 1000000007
;

int main() { _
  int n; cin >> n;
  ll count = 1, group = 0, cof = 1;
  vector<ll> v(1, 0);
  bool end = false;
  for (int i = 0; i < n; i++) {
    ll temp; cin >> temp;
    if (cof == 0 || temp > count) { break; end = true; }
    if (temp == count) {
      count++;
      v.push_back(0);
    }

    if (temp == 0) {
      group++;
    }
    if (temp != 0) {
      cof *= v[temp-1];
      cof %= MOD;
      v[temp-1]--;
    }
    v[temp]++;
  }
  ll ans = group == 3 || group == 2 ? 6 : 3;
  ans *= cof;
  ans %= MOD;
  cout << (group > 3 || group == 0 || end ? 0 : ans) << endl;
  return 0;
}

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

using namespace std;

int main() {
  int N;
  cin >> N;
  vector<int> counts(N, 0);
  for (int i = 0; i < N - 1; i++) {
    int boss;
    cin >> boss;
    boss--;
    counts[boss]++;
  }

  for (int i = 0; i < N; i++) {
    cout << counts[i] << endl;
  }

  return 0;
}


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

#define CPP_STR(x) CPP_STR_I(x)
#define CPP_CAT(x,y) CPP_CAT_I(x,y)
#define CPP_STR_I(args...) #args
#define CPP_CAT_I(x,y) x ## y

using i8  = int8_t;
using u8  = uint8_t;
using i16 = int16_t;
using u16 = uint16_t;
using i32 = int32_t;
using u32 = uint32_t;
using i64 = int64_t;
using u64 = uint64_t;

using f32 = float;
using f64 = double;

#define FOR(i, start, end) for(i64 i = (start), CPP_CAT(i,xxxx_end)=(end); i < CPP_CAT(i,xxxx_end); ++i)
#define REP(i, n) FOR(i, 0, n)
#define REPS(i, n) for(i64 i = 1; i <= n; ++i)
#define RREP(i, n) for(i64 i = n - 1; i >= 0 ; --i)
#define RREPS(i, n) for(i64 i = n; i >= 1; --i)

#define ALL(f,c,...) (([&](decltype((c)) cccc) { return (f)(std::begin(cccc), std::end(cccc), ## __VA_ARGS__); })(c))

#define UNIQUE(v) v.erase( unique(v.begin(), v.end()), v.end() );

#define pb push_back
#define mp make_pair

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

template<typename C>
i64 SIZE(const C& c) { return static_cast<i64>(c.size()); }

template<typename T, size_t N>
i64 SIZE(const T (&)[N]) { return static_cast<i64>(N); }


struct ProconInit {
    static constexpr int IOS_PREC = 15;
    static constexpr bool AUTOFLUSH = false;

    ProconInit() {
        cin.tie(nullptr);
        ios::sync_with_stdio(false);
        cout << fixed << setprecision(IOS_PREC);
        if(AUTOFLUSH)
            cout << unitbuf;
    }
} PROCON_INIT;


const char c[5] = {'M', 'A', 'R', 'C', 'H'};


int main() {
    i64 N; cin >> N;
    string s;
    unordered_map<char, i64> mp;
    REP(i, N) {
        cin >> s;
        mp[s[0]]++;
    }

    i64 cnt = 0;
    for (i64 bit = 0; bit < (1 << 5); bit++) {
        if (__builtin_popcount(bit) != 3) continue;
        i64 p = 1;
        REP(i, 5) {
            if (bit >> i & 1) {
                p *= mp[c[i]];
            }
        }
        cnt += p;
    }
    cout << cnt << endl;

    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
typedef long long ll;
int main(void){
  ll n,i,a[100010],b[100010],k=0,s=0;
  vector<ll> u;
  cin >> n;
  for (i=0;i<n;i++) cin >> a[i];
  for (i=0;i<n;i++) cin >> b[i];
  for (i=0;i<n;i++){
    if (a[i]>b[i]) u.push_back(a[i]-b[i]);
    else if (a[i]<b[i]){
      s+=b[i]-a[i];
      k++;
    }
  }
  sort(u.begin(),u.end(),greater<int>());
  for (i=0;i<u.size();i++){
    if (s<=0) break;
    s-=u[i];
  }
  if (i==u.size() && s>0) cout << -1 << endl;
  else cout << k+i << endl;
  return 0;
}

Measured memory_bytes: 2428
N, K = map(int, raw_input().split())
prob = 0

if N < K:
    for i in range(1,N+1):
        tmp = i
        tmp_prob = 1.0/N
        while tmp < K:
            tmp = 2 * tmp
            tmp_prob = 0.5 * tmp_prob
        prob = prob + tmp_prob
else:
    prob = (N-K+1.0)/N
    for i in range(1,K):
        tmp = i
        tmp_prob = 1.0/N
        while tmp < K:
            tmp = 2 * tmp
            tmp_prob = 0.5 * tmp_prob
        prob = prob + tmp_prob

print prob

Measured memory_bytes: 2948
#include<iostream>
#include<cstdio>
#include<string>
#include<cctype>
#include<algorithm>

using namespace std;

int main(){
    int card[205]={0},card2[205]={0},n,m;
    cin >>n>>m;
    for(int i=1;i<=2*n;++i){
        card[i]=card2[i]=i;
    }
    for(int i=0;i<m;++i){
        for(int j=1;j<=2*n;++j){card2[j]=card[j];}
        int k;
        int cut=1;
        scanf("%d",&k);
        if(k==0){
            for(int k=1;k<=2*n;k++){
                if(k%2==0)card[k]=card2[cut+n-1];
                else {
                        card[k]=card2[cut];
                        cut++;
                }
            }
        }
        else {
            for(int q=1;q<=2*n;++q){
                if(q<=2*n-k)card[q]=card2[q+k];
                else card[q]=card2[q-(2*n-k)];
            }
        }
    }
    for(int i=1;i<=2*n;++i){cout <<card[i]<<endl;}
    return 0;
}

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

typedef long long int ll;
using ii= pair<ll,ll>;
#define F first
#define S second
#define MP make_pair
#define PB push_back
//using min_of_3=min({ll a,ll b,ll c});

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);cout.tie(NULL);
	
	string s;
	cin>>s;
	string t;
	cin>>t;
	
	ll a=s.length();
	
	ll count=0;
	
	for(ll i=0;i<a;i++)
	{
	    if(s[i]!=t[i])
	    {
	        count++;
	    }
	}
	
	cout<<count<<"\n";
}


Measured memory_bytes: 3800
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <deque>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <utility>
#include <vector>

#define CK(N, A, B) (A <= N && N < B)
#define REP(i, a, b) for (int i = a; i < b; i++)
#define RREP(i, a, b) for (int i = (b - 1); a <= i; i--)
#define F first
#define S second
#define ll long long

const int INF = 1e9;
const long long LLINF = 1e18;

using namespace std;

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

/*==================================================*/
/*variable*/
int N;

/*==================================================*/
/*function*/
vector<int> hurui_v(int n) {
    vector<int> v;
    bool *isPrime_v;
    isPrime_v = new bool[n + 1]; // 処理用のメモリ確保

    // 初期化
    isPrime_v[0] = isPrime_v[1] = false;
    for (int i = 2; i < n + 1; i++) isPrime_v[i] = true;

    // isPrime[0~n]で素数のものだけtrueにする
    for (int i = 2; i * i <= n; i++) {
        for (int j = i * 2; j < n + 1; j += i) {
            isPrime_v[j] = false;
        }
    }

    // 素数のみ追加
    for (int i = 0; i < n + 1; i++) {
        if (isPrime_v[i]) v.push_back(i);
    }

    delete[] isPrime_v; //メモリ解放
    return v;
}
/*==================================================*/

int main() {
    cin>>N;

    ll ans = 1LL;

    vector<int> v = hurui_v(N);

    REP(j,0,v.size()){
        ll cnt = 0;
        REP(i,1,N+1){
            int t = i;
            while(t % v[j] == 0){
                t /= v[j];
                cnt++;
            }
        }
        ans = (ans * (cnt+1)) % 1000000007LL;
    }

    cout<<ans<<endl;

    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
using namespace std;
int main(){
int h,w;
cin >> h>>w;
char a[h][w];
for (int i=0;i<h;i++){
for (int j=0;j<w;j++) cin >> a[i][j];
}
for (int i=0;i<w+2;i++) cout << "#";
cout <<endl;
for (int i=0;i<h;i++){
cout << "#";
for (int j=0;j<w;j++) cout << a[i][j];
cout << "#"<<endl;
}
for (int i=0;i<w+2;i++) cout << "#";
return 0;
}

Measured memory_bytes: 256
N, M = map(int,input().split())
ps = dict()
for m in range(M):
    a = input().split()
    if a[0] not in ps:
        ps[a[0]] = []
    ps[a[0]].append(a[1])
ans = [0, 0]
for x in ps:
    if "AC" in ps[x]:
        for y in ps[x]:
            if y == "WA":
                ans[1] += 1
            else:
                ans[0] += 1
                break
print(ans[0],ans[1])


Measured memory_bytes: 31564
/**
 *   @FileName	a.cpp
 *   @Author	kanpurin
 *   @Created	2020.08.16 00:41:37
**/

#include "bits/stdc++.h" 
using namespace std; 
typedef long long ll;

int main() {
    int r,c,k;cin >> r >> c >> k;
    vector<vector<int>> v(r,vector<int>(c,0));
    for (int i = 0; i < k; i++) {
        int x,y,z;cin >> x >> y >> z;
        x--;y--;
        v[x][y] = z;
    }
    vector<vector<vector<ll>>> dp(r+1,vector<vector<ll>>(c+1,vector<ll>(4,0)));
    for (int i = 0; i < r; i++) {
        for (int j = 0; j < c; j++) {
            dp[i + 1][j + 1][0] = dp[i + 1][j][0];
            for(int s = 0; s < 4; s++) dp[i + 1][j + 1][0] = max(dp[i + 1][j + 1][0],dp[i][j + 1][s]);
            dp[i + 1][j + 1][1] = dp[i + 1][j][1];
            dp[i + 1][j + 1][1] = max(dp[i + 1][j + 1][1],dp[i + 1][j][0] + v[i][j]);
            for(int s = 0; s < 4; s++) dp[i + 1][j + 1][1] = max(dp[i + 1][j + 1][1],dp[i][j + 1][s] + v[i][j]);
            dp[i + 1][j + 1][2] = max(dp[i + 1][j][2],dp[i + 1][j][1] + v[i][j]);
            dp[i + 1][j + 1][3] = max(dp[i + 1][j][3],dp[i + 1][j][2] + v[i][j]);
        }
    }
    cout << max({dp[r][c][0],dp[r][c][1],dp[r][c][2],dp[r][c][3]}) << endl;
    return 0;
}

Measured memory_bytes: 671968
#include<iostream>
#include<algorithm>
using namespace std;
int main(){
  const int MAX = 1e5;
  for(int n,m;cin>>n>>m,n;){
    int cost[m][m];
    int time[m][m];
    for(int i=0;i<m;i++){
      for(int j=0;j<m;j++){
	cost[i][j] = MAX;
	time[i][j] = MAX;
      }
    }
    int a,b,c,t;
    for(int i=0;i<n;i++){
      cin>>a>>b>>c>>t;
      cost[max(a-1,b-1)][min(a-1,b-1)] = c;
      time[max(a-1,b-1)][min(a-1,b-1)] = t;
    }
    for(int k=0;k<m;k++){
      for(int i=0;i<m;i++){
	for(int j=0;j<=i;j++){
	  int mai = max(i,k),mii=min(i,k);
	  int maj = max(j,k),mij=min(j,k);
	    cost[i][j] = min(cost[i][j],cost[mai][mii]+cost[maj][mij]);
	    time[i][j] = min(time[i][j],time[mai][mii]+time[maj][mij]);
	}
      }
    }
    int l,r;
    cin>>l;
    for(int i=0;i<l;i++){
      cin>>a>>b>>r;
      if(r)cout<<time[max(a-1,b-1)][min(a-1,b-1)]<<endl;
      else cout<<cost[max(a-1,b-1)][min(a-1,b-1)]<<endl;      
    }
  }
  return 0;
}

Measured memory_bytes: 944
pre = [11,31,41,61,71,101,131,151,181,191,211,241,251,271,281,311,331,401,421,431,461,491,521,541,571,601,631,641,661,691,701,751,761,811,821,881,911,941,971,991,1021,1031,1051,1061,1091,1151,1171,1181,1201,1231,1291,1301,1321,1361,1381]
main=readLn>>=putStrLn.unwords.map show.(\n->take n pre)

Measured memory_bytes: 508
num = int(input())
import math
min = 1000000000000000
limit = math.floor((num ** 0.5) + 1)
for i in range(1, limit):
  if num % i == 0:
    j = num / i
    lsti = []
    lstj = []
    while i > 0:
      lsti.append(i%10)
      i //= 10
    while j > 0:
      lstj.append(j%10)
      j //= 10
    lengthi = len(lsti)
    lengthj = len(lstj)
    if max(lengthi, lengthj) < min:
      min = max(lengthi, lengthj)
print(min)

Measured memory_bytes: 3064
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MOD=1e9+7;
const int INF=1e9;

int main(){
    string s;
    cin>>s;
    int i=0,n=s.size();
    int ans[n]={};
    while(i<n){
        int c,r=0,l=0;
        while(s[i]=='R'&&i<n){
            ++i;
            ++r;
        }
        c=i-1;
        while(s[i]=='L'&&i<n){
            ++i;
            ++l;
        }
        ans[c]=(r+1)/2+l/2;
        ans[c+1]=r/2+(l+1)/2;
    }
    for(int i=0;i<n;i++){
        if(i)cout<<" ";
        cout<<ans[i];
    }
    cout<<endl;
}


Measured memory_bytes: 1024
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;

int main() {
    int n; cin >> n;
    vector<vector<ll>> dp(n, vector<ll>(2));
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    dp[0][0] = 0;
    dp[0][1] = 0;
    dp[1][0] = a[0];
    dp[1][1] = a[1];
    for (int i = 2; i < n; i++) {
        if (i & 1) {
            dp[i][1] = max(dp[i - 2][0], dp[i - 2][1]) + a[i];
            dp[i][0] = dp[i - 2][0] + a[i - 1];
        }
        else {
            dp[i][0] = max(dp[i - 1][1], dp[i - 1][0]);
            dp[i][1] = max(dp[i - 2][0], dp[i - 2][1]) + a[i];
        }
    }
    //dump(dp);
    cout << max(dp[n - 1][0], dp[n - 1][1]) << endl;
    return 0;
}

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

#define fst(t) std::get<0>(t)
#define snd(t) std::get<1>(t)
#define thd(t) std::get<2>(t)
#define unless(p) if(!(p))
#define until(p) while(!(p))

using ll = std::int64_t;
using P = std::tuple<int,int>;

template <typename T>
std::tuple<T, T, T> extgcd(T a, T b){
    T s1 = 1, t1 = 0, s2 = 0, t2 = 1;
    while(b != 0){
        std::tie(s1, t1, s2, t2) = std::make_tuple(s2, t2, s1 - (a / b) * s2, t1 - (a / b) * t2);
        std::tie(a, b) = std::make_tuple(b, a % b);
    }
    return std::make_tuple(s1, t1, a);
}

// 注意: a と mod が互いに素である必要がある
template <typename T>
T mod_inverse(T a, T mod){
    T b;
    std::tie(b, std::ignore, std::ignore) = extgcd(a, mod);
    if(b < 0){b += mod;}
    return b;
}

template <typename T>
struct Combinatorics{
    T modulo;
    std::vector<T> fact, inv_fact;

    Combinatorics(T max, T modulo) : modulo(modulo), fact(max + 1), inv_fact(max + 1) {
        fact[0] = 1;
        for(T i=1;i<=max;++i){
            fact[i] = i * fact[i - 1] % modulo;
        }

        inv_fact[max] = mod_inverse(fact[max], modulo);
        for(T i=max;i>0;--i){
            inv_fact[i - 1] = i * inv_fact[i] % modulo;
        }
    }

    T nPk(T n, T k){
        if(n < k){return 0;}
        return fact[n] * inv_fact[n - k] % modulo;
    }

    T nCk(T n, T k){
        if(n < k){return 0;}
        return fact[n] * inv_fact[k] % modulo * inv_fact[n - k] % modulo;
    }

    T nHk(T n, T k){
        if(n == 0 && k == 0){return 1;}
        return nCk(n + k - 1, k);
    }
};

constexpr ll MOD = 1'000'000'007;
Combinatorics<ll> comb(400100, MOD);

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

  int N, K;
  std::cin >> N >> K;

  ll res = 0;

  if(N <= K){
      res = comb.nHk(N, N);
  }else{
      for(int i=0;i<=K;++i){
          ll x = comb.nCk(N, i) * comb.nCk(N - 1, i) % MOD;
          res = (res + x) % MOD;
      }
  }

  std::cout << res << std::endl;
}


Measured memory_bytes: 6528
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <deque>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>

using namespace std;

typedef long long ll;

#define MOD 1000000007

int main() {
  int x;
  cin >> x;
  for (int i = 1; i <= x; ++i) {
    if (100 * i <= x && x <= 105 * i) {
      cout << 1 << endl;
      return 0;
    }
  }
  cout << 0 << endl;
  return 0;
}

Measured memory_bytes: 3648
def main():
    n = int(input())
    nums = list(map(int, input().split())) 
    exist_odd = False
    result = 0
    while True:
        for i in range(n):
            if nums[i] % 2 != 0:
                exist_odd = True
        if exist_odd:
            break
        nums = list(map(lambda x: x / 2, nums))
        result += 1
    print(result)
if __name__ == '__main__':
    main()

Measured memory_bytes: 3064
s = input().rstrip()
t = input().rstrip()

m = dict()

for a, b in zip(s, t):
    if a in m and b != m[a]:
        print('No')
        exit()

    m[a] = b

if len(m) == len(set(m.values())):
    print('Yes')
else:
    print('No')


Measured memory_bytes: 41932
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools
from collections import deque

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

DR = [1, -1, 0, 0]
DC = [0, 0, 1, -1]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 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 I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
     
def main():
    N = I()
    L = LI()
    cnt = 0
    for i in range(N):
        for j in range(i+1, N):
            for k in range(j+1, N):
                if L[i] == L[j] or L[j] == L[k] or L[k] == L[i]:
                    continue
                if abs(L[i] - L[j]) < L[k] and L[k] < L[i] + L[j]:
                    cnt += 1
    print(cnt)

main()



Measured memory_bytes: 83940
from collections import deque
import bisect
import sys

sys.setrecursionlimit(200000)

N = int(input())
a = list(map(int, input().split()))
uvs = [list(map(int, input().split())) for _ in range(N-1)]
shortest = [10e+10 for _ in range(N)]
shortest[0] = 0

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

for uv in uvs:
    routes[uv[0]-1].append(uv[1]-1)
    routes[uv[1]-1].append(uv[0]-1)

lis = [10e+100 for _ in range(N)]
minimum = [10e+100 for _ in range(N)]
seen = [False for _ in range(N)]
seen[0] = True

def function(checking):
    insert_posi = bisect.bisect_left(lis, a[checking])
    preserved = lis[insert_posi]
    lis[insert_posi] = a[checking]
    minimum[checking] = bisect.bisect_left(lis, 10e+50)
    for route in routes[checking]:
        if seen[route] == False:
            seen[route] = True
            shortest[route] = shortest[checking]+1
            function(route)
    lis[insert_posi] = preserved
    return
        
function(0)

[print(x) for x in minimum]

Measured memory_bytes: 272200
#include <bits/stdc++.h>
typedef long long ll;
typedef long double ld;
using namespace std;
#define F first
#define S second
#define pb push_back  
#define all(x) (x).begin(), (x).end()
#define SZ(x) (int)(x).size()
//#define int ll    

const int N = 1e6 + 10;
const int ALPHA = 26;
int cnt = 1;
int sum[N], calc[N][ALPHA];
map<int, int> mp[N];

void add(string &s) {
  int v = 1;
  for (auto c : s) {
    if (!mp[v][c - 'a']) {
      mp[v][c - 'a'] = ++cnt;
    }
    v = mp[v][c - 'a'];
  }
  sum[v] = 1;
}

void dfs(int v) {
  for (auto it : mp[v]) {
    dfs(it.S);
    sum[v] += sum[it.S];
  }
  for (int letter = 0; letter < 26; letter++) {
    for (auto it : mp[v]) {
      if (it.F == letter) {
        calc[v][letter] += sum[it.S];
      }
      else {
        calc[v][letter] += calc[it.S][letter];
      }
    }
  }
}
const int M = 2e5 + 10;
string s[M];

signed main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0); 
  cout.tie(0);
  int n;
  cin >> n;
  for (int i = 0; i < n; i++) {
    cin >> s[i];
    reverse(all(s[i]));
    add(s[i]);
  }
  dfs(1);
  ll ans = 0;
  for (int i = 0; i < n; i++) {
    int v = 1;
    for (int j = 0; j + 1 < SZ(s[i]); j++) {
      v = mp[v][s[i][j] - 'a'];
    }
    ans += calc[v][s[i].back() - 'a'] - 1;
  }
  cout << ans << '\n';
}

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

using namespace std;

vector <long long> v;

int main() {
    for (int i = 1; i < 10; i++) v.push_back(i);
    int k;
    cin >> k;
    for (int i = 0; v.size() < k + 5; i++) {
        long long x = v[i];
        int d = x % 10;
        if (d - 1 >= 0) v.push_back(1LL * x * 10 + (d - 1));
        v.push_back(x * 10 + d);
        if (d + 1 < 10) v.push_back(1LL * x * 10 + (d + 1));
    }
    cout << v[k - 1] << "\n";
    return 0;
}


Measured memory_bytes: 1400
#include <algorithm>
#include <cmath>
#include <vector>
#include <functional>
#include <cstdlib>
#include <map>
#include <set>
#include <iostream>
#include <string>
#include <ctype.h>
#include <climits>
#include <queue>
using namespace std;
typedef long long ll;
#define REP(i, n) for(ll i = 0; i < (ll)(n); ++i)
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;}

bool comp(pair<int,int> l, pair<int,int> r){
	return l.first > r.first;
}

int main(){
	int H,N;
	cin >> H >> N;
	vector<pair<int,int>> a(N);
	REP(i,N) cin >> a[i].first >> a[i].second;
	sort(a.begin(), a.end(), comp);
	
	const ll INF = 1LL << 60;
	vector<ll> dp(H+a[0].first,INF);
	
	dp[0]=0;
	for(int i=0; i<H; i++){
		for(auto x: a){
			chmin(dp[i+x.first], dp[i]+x.second);
		}
	}
	
	ll ans = INF;
	for(int i=H; i<H+a[0].first; i++){
		chmin(ans, dp[i]);
	}
	
	cout << ans << endl;
	
	return 0;
}

Measured memory_bytes: 3736
#78 C - HSI
N,M = map(int,input().split())
# 全て AC となる確率
p = (1/2)**M

# 全て AC となるときの期待値
# k 回目までに「成功しない」確率の期待値
# E = (1-p)**0 + (1-p)**1 + (1-p)**2+...
E = 0
for k in range(10**6):
    E += (1-p)**k

ans = (1900*M + 100*(N-M))*E
ans = round(ans)
print(ans)

Measured memory_bytes: 9500
#include<iostream>
#include<stdio.h>
using namespace std;

int main(){
    int a,b,d,r;
    double f;
    cin >> a >> b;
    
    d = a / b;
    r = a % b;
    f = 1.000000 * a / b;
    
    printf("%d %d %.5lf\n",d ,r ,f);
    return 0;
}


Measured memory_bytes: 3216
#include<bits/stdc++.h>
using namespace std;
int const nax = 3e5 + 10;

vector<int> a[nax], node[2];

int n , ct[3], c[3], col[nax];
int  ptr1 = 1, ptr2 = 2, ptr3  = 0;

void dfs (int nod,  int pa, int lv) {
    ct[lv % 2] ++;
    node[lv % 2].emplace_back(nod);
    for (int i : a[nod]) {
        if (i != pa) dfs(i, nod, lv + 1);
    }
}


int main () {
    scanf("%d", &n);
    for (int i = 1 ; i < n ; ++ i) {
        int u, v;
        scanf("%d %d", &u, &v);
        a[u].emplace_back(v);
        a[v].emplace_back(u);
    }

    c[0] = n / 3 ;
    c[1] = n / 3 + (n % 3 > 0);
    c[2] = n / 3 + (n % 3 > 1);
    dfs(1, 0, 0);
    if (max(ct[0], ct[1]) >= c[1] + c[2]) {
        int toCol = ct[0] >= ct[1] ? 0 : 1;
        for (int i = 0 ;i < c[1] ; ++ i)
            col[node[toCol][i]] = ptr1, ptr1 += 3;

        for (int i = 0 ; i < c[2] ; ++ i)
            col[node[toCol][i + c[1]]] = ptr2, ptr2 += 3;
    }
    else if (max(ct[0], ct[1]) >= c[1] && min(ct[0], ct[1]) >= c[2]) {
        int maxCol = ct[0] >= ct[1] ? 0 : 1;
        int minCol = (maxCol ^ 1);
        for (int i = 0 ; i < c[1] ; ++ i)
            col[node[maxCol][i]] = ptr1 , ptr1 += 3;

        for (int i = 0 ; i < c[2] ; ++ i)
            col[node[minCol][i]] = ptr2 , ptr2 += 3;
    }

    for (int i = 1 ; i <= n ; ++ i)
        printf("%d ", col[i] ? col[i] : ptr3 += 3);


}
/*
    Good Luck
        -Lucina
*/


Measured memory_bytes: 23796