akhauriyash/Code-Regression huggingface dataset:
n,m=map(int,input().split())
num="a"*n
flag=False

for i in range(m):
    s,c=map(int,input().split())
    s-=1
    if num[s]=="a" or num[s]==str(c):
        num=num[:s]+str(c)+num[s+1:]
    else:
        flag=True
if n==1 and ( m==0 or num=="0" ):
    print(0)
elif flag or num[0]=="0":
    print(-1)
else:
    if num[0]=="a":
        num="1"+num[1:]
    print(num.replace("a","0"))

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

#define         pb         push_back
#define         sf(x)      scanf("%d",&x)
#define         sfl(x)     scanf("%lld",&x)
#define         pf(x)      printf("%d\n",x)
#define         pfl(x)     printf("%lld\n",x)
#define         endl       '\n'
#define         pii        pair<int,int>
#define         mapii      map<int,int>
#define         mapll      map<ll,ll>
#define         mapci      map<char,int>
#define         mapcl      map<char,ll>
#define         mapsi      map<string,int>
#define         mapsl      map<string,ll>
#define         pll        pair<ll,ll>
#define         vi         vector<int>
#define         vl         vector<ll>
#define         vd         vector<double,double>
#define         all(c)     c.begin(),c.end()
#define         F          first
#define         S          second
#define         mp         make_pair
#define        ftc(x)      cerr << #x << ": " << x << " " << endl;
#define         PI         acos(-1)
#define         lcm(a,b)   ((a*b)/__gcd(a,b))
//int dx[] = {0,1,0,-1};
//int dy[] = {-1,0,1,0};

//   cout<<std::setprecision(12)<<

int ok(ll a,ll b)
{
    if(a%b == 0)return ok(a/b,b);
    else return a%b;
}
int main()
{
    ll i,j,k,l,m,n;

    cin >> n;
    ll cnt = 1;
    for(i=2;i*i<=n;i++)
    {
        if(n%i == 0)
        {
            l = n/i;

            if(ok(l,i) == 1)cnt++;
        }
    }
    n--;
    if(n>1)cnt++;
    for(i=2;i*i<=n;i++)
    {
        if(n%i == 0)
        {
            if(n/i != i)cnt+=2;
            else cnt++;
        }
    }

    cout << cnt << endl;
}


Measured memory_bytes: 256
N, M, K = map(int, input().split())
ans = [0] * N
class unionfind():
  def __init__(self, N):
    self.__N = N
    self.__parent = [-1] * (N + 1)
    
  def table(self):
    print(self.__parent)
    
  def find_parent(self, x):
    if self.__parent[x] < 0:
      return x
    else:
      self.__parent[x] = self.find_parent(self.__parent[x])
      return self.__parent[x]
    
  def union(self, x, y):
    x = self.find_parent(x)
    y = self.find_parent(y)
    if x == y :
      return
    if self.__parent[x] > self.__parent[y]:
      x, y = y, x
    self.__parent[x] += self.__parent[y]
    self.__parent[y] = x
    
  def size(self, x):
    return  -self.__parent[self.find_parent(x)]
  
  def same(self, x, y):
    if self.find_parent(x) == self.find_parent(y):
      return True
    else:
      return False

uf = unionfind(N)
for _ in range(M):
  A, B = map(int, input().split())
  uf.union(A, B)
  ans[A-1] += 1
  ans[B-1] += 1

for _ in range(K):
  C, D = map(int, input().split())
  if uf.same(C, D):
    ans[C-1] += 1
    ans[D-1] += 1

for i in range(N):
  print(uf.size(i+1) - ans[i] - 1,end=" ")

Measured memory_bytes: 82888
#include <iostream>
#include <vector>
#include <stack>

using std::cin;
using std::cout;
using std::endl;

int main(void) {
	int W,H;
	cin >> W;
	cin >> H;

	while (W!=0||H!=0) {
		int count = 0;
		char c;
		std::stack<int> st_x;
		std::stack<int> st_y;
		int xn,yn;
		std::vector< std::vector<bool> > tile(W+2, std::vector<bool>(H+2));
		for (int i = 0; i < H+2; i++) {
			for (int j = 0; j < W+2; j++) {
				if (i==0||i==H+1||j==0||j==W+1) {
					tile[j][i] = false;
				} else {
					cin >> c;
					if (c=='.') {
						tile[j][i] = true;
					}
					if (c=='#') {
						tile[j][i] = false;
					}
					if (c=='@') {
						tile[j][i] = false;
						st_x.push(j);
						st_y.push(i);
						count++;
					}
				}
			}
		}
		while (!st_x.empty()) {
			xn = st_x.top();
			yn = st_y.top();
			st_x.pop();
			st_y.pop();

			if (tile[xn+1][yn]) {
				st_x.push(xn+1);
				st_y.push(yn);
				tile[xn+1][yn] = false;
				count++;
			}
			if (tile[xn-1][yn]) {
				st_x.push(xn-1);
				st_y.push(yn);
				tile[xn-1][yn] = false;
				count++;
			}
			if (tile[xn][yn+1]) {
				st_x.push(xn);
				st_y.push(yn+1);
				tile[xn][yn+1] = false;
				count++;
			}
			if (tile[xn][yn-1]) {
				st_x.push(xn);
				st_y.push(yn-1);
				tile[xn][yn-1] = false;
				count++;
			}
		}
		cout << count << endl;

		cin >> W;
		cin >> H;
	}
	return 0;
}

Measured memory_bytes: 3016
A = int(input())
B = list(map(int, input().split()))

a = 0
b = 0
res = 0
while a < A:
    if a < A - 1 and B[a + 1] <= B[a]:
        a += 1
        res = max(res, a - b)
    elif a != b:
        b += 1
    else:
        b += 1
        a += 1
print(res)

Measured memory_bytes: 14252
#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
constexpr ll mod=998244353;
constexpr int N=1800000;

inline unsigned long xor128() {
	static unsigned long x=123456789, y=362436069, z=521288629, w=88675123;
	unsigned long t=(x^(x<<11));
	x=y; y=z; z=w;
	return (w=((w>>19)^t^(t>>8)));
}

int D,c[26],s[200000][26],t[200000],T[200000];
set<int>st[26];

int main(){
	scanf("%d",&D);
	for(int i=0;i<26;i++){
		scanf("%d",&c[i]);
	}
	for(int i=0;i<D;i++){
		for(int j=0;j<26;j++){
			scanf("%d",&s[i][j]);
		}
	}
	for(int i=0;i<D;i++){
		pair<int,int>mx={-1,-1};
		for(int j=0;j<26;j++){
			mx=max(mx,{s[i][j],j});
		}
		t[i]=mx.second;
		st[mx.second].insert(i);
	}
	for(int i=0;i<26;i++){
		st[i].insert(-1);
		st[i].insert(D);
	}
	for(int i=0;i<N;i++){
		int K=xor128()%D;
		pair<int,int>mx={0,t[K]};
		auto it1=st[t[K]].find(K);
		auto it2=it1;
		it1--;
		auto it3=it2;
		it3++;
		int a=c[t[K]]*((*it3-*it1)*(*it3-*it1-1)/2-(*it3-*it2)*(*it3-*it2-1)/2-(*it2-*it1)*(*it2-*it1-1)/2);
		for(int j=0;j<26;j++){
			if(j==t[K])continue;
			auto it=st[j].lower_bound(K);
			auto jt=it;
			jt--;
			mx=max(mx,{s[K][j]-s[K][t[K]]+c[j]*((*it-*jt)*(*it-*jt-1)/2-(*it-K)*(*it-K-1)/2-(K-*jt)*(K-*jt-1)/2)-a,j});
		}
		st[t[K]].erase(it2);
		t[K]=mx.second;
		st[mx.second].insert(K);
	}
	for(int i=0;i<D;i++){
		printf("%d\n",t[i]+1);
	}
}


Measured memory_bytes: 3916
#include<cstdio>
#include<cstring>
#include<string>
#include<iostream>
#include<cmath>
#include<algorithm>
#include<queue>
#include<map>
#include<ctime>

using namespace std;

template <typename T>

inline T read()
{
	T x=0,f=1;char c=getchar();
	while(!isdigit(c))
	{if(c=='-') f=-f;c=getchar();}
	while(isdigit(c))
	{x=(x<<3)+(x<<1)+(c-48);c=getchar();}
	return x*f;
}

#define lint long long int
#define ulint unsigned lint

const int inf=1e9+1e7;
const int MAXN=1e6+1e1;

int a[MAXN];

int n;

int main(void)
{

	// freopen("testdata.in","r",stdin);
	// freopen("testdata.out","w",stdout);

	scanf("%d",&n);

	for(int i=1;i<n;i++) ++a[read<int>()];

	for(int i=1;i<=n;i++) printf("%d\n",a[i]);

	return 0;

}

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

int main(){
	int n, m;
	cin >> n >> m;
	int a[n][m], b[m], r[n];
	for(int i = 0; i < n; i++){
		r[i] = 0;
	}
	for(int i = 0; i < m; i++){
		b[i] = 0;
	}
	for(int i = 0; i < n; i++){
		for(int j = 0; j < m; j++){
			a[i][j] = 0;
		}
	}

	for(int i = 0; i < n; i++){
		for(int j = 0; j < m; j++){
			cin >> a[i][j];
		}
	}
	for(int i = 0; i < m; i++){
		cin >> b[i];
	}

	for(int i = 0; i < n; i++){
		for(int j = 0; j < m; j++){
			r[i] += (a[i][j]*b[j]);
		}
		cout << r[i] << endl;
	}
	return 0;
}


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

using namespace std;

#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define all(x) (x).begin(), (x).end()
#define itn int
typedef long long ll;
typedef pair<int,int> p;


int main()
{
  int n, m;
  cin >> n >> m;
  vector<ll> x(n, 0);
  vector<ll> y(n, 0);
  vector<ll> z(n, 0);
  vector<ll> sum(n, 0);

  for (ll i = 0; i < n; i++)
  {
    cin >> x[i] >> y[i] >> z[i];
  }

  vector<ll> opeSet = {1, -1};
  ll res = -1;
  for (ll j = 0; j < 2; j++)
  {
    for (ll k = 0; k < 2; k++)
    {
      for (ll l = 0; l < 2; l++)
      {
        for (ll i = 0; i < n; i++)
        {
          sum[i] = x[i] * opeSet[j] + y[i] * opeSet[k] + z[i] * opeSet[l];
        }
        sort(sum.rbegin(), sum.rend());
        ll tmp = 0;
        for (ll i = 0; i < m; i++) tmp += sum[i];
        res = max(tmp, res);
      }
    }
  }
  cout << res << endl;

}

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

const int N = 1e5 + 10;
const ll inf = 1e18;
struct SEG{
  ll data[N*4];
  int n;
  SEG(int t) {
    t++;
    t = max(16, t);
    n = 1;
    while(n < t) n <<= 1;
    for(int i= 0; i < n * 2; i++) data[i] = (1ll << 31) - 1;
  }
  void set(int i, ll x) {
    i += n-1;
    data[i] = x;
    while(i > 0) i = (i - 1) / 2, data[i] = min(data[i * 2 + 1], data[i * 2 + 2]);
  }
  ll query(int a, int b, int k = 0, int l = 0, int r = -1){
    if(r<0)r=n;
    if(b <= l || r <= a) return inf;
    if(a <= l && r <= b) return data[k];
    return min(
        query(a, b, k * 2 +1, l, (l + r)>>1),
        query(a, b, k * 2 +2, (l + r)>>1, r));
  }
};

int main() {
  std::ios::sync_with_stdio(false), std::cin.tie(0);
  int n, q;cin >>n>>q;
  SEG seg(n);
  // cout << "TEST" << endl;
  while(q--){
    int com,x,y; cin >>com>> x>>y;
    if(com == 0) {
      seg.set(x, y);
    } else {
      cout << seg.query(x, y+1) << endl;
    }
  }
  return 0;
}



Measured memory_bytes: 5220
#include <cstdio>
#include <string>

using namespace std;

string scan_string() {
    char input[4000];

    if (scanf("%s", input) == EOF) {
        return "";
    }

    return string(input);
}

int main() {
    while (1) {
        int i;
        int n;
        string str1;
        string str2 = "";
        int max_sum = 0;

        str1 = scan_string();
        if (str1 == string("")) return 0;

        for (i=0;i<str1.length();i++) {
            str2 += " ";
        }
        str2 += scan_string();

        n = str2.length();
        for (i=0;i<n;i++) {
            int j;
            int m;
            string str3 = str2.substr(i, n-i);
            int sum = 0;

            m = min(str1.length(), str3.length());
            for (j=0;j<m;j++) {
                if (str1[j] == str3[j]) {
                    sum++;
                } else {
                    if (max_sum < sum) max_sum = sum;
                    sum = 0;
                }
            }
            if (max_sum < sum) max_sum = sum;
        }

        printf("%d\n", max_sum);
    }
}

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

const int MAX_N = 1 << 17;
const int INF = 1 << 30;

struct MinSegTree2 {
	int n, segMin[2 * MAX_N - 1], segAdd[2 * MAX_N - 1];
	void init(int n_) {
		n = 1;
		while(n < n_) n *= 2;
		for(int i = 0; i < 2 * n - 1; i++) segMin[i] = 0;
	}

	void add(int a, int b, int x) { add(a, b, x, 0, 0, n); }

	void add(int a, int b, int x, int k, int l, int r) {
		if(r <= a || b <= l) return;
		if(a <= l && r <= b) {
			segAdd[k] += x;
			return;
		}
		add(a, b, x, k * 2 + 1, l, (l + r) / 2);
		add(a, b, x, k * 2 + 2, (l + r) / 2, r);
		segMin[k] = min(segMin[k * 2 + 1] + segAdd[k * 2 + 1], segMin[k * 2 + 2] + segMin[k * 2 + 2]);
	}

	int query(int a, int b) { return query(a, b, 0, 0, n); }

	int query(int a, int b, int k, int l, int r) {
		if(r <= a || b <= l) return INF;
		if(a <= l && r <= b) return segMin[k] + segAdd[k];
		int vl = query(a, b, k * 2 + 1, l, (l + r) / 2);
		int vr = query(a, b, k * 2 + 2, (l + r) / 2, r);
		return min(vl, vr) + segAdd[k];
	}
};

MinSegTree2 st;

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

	int n, q;
	cin >> n >> q;

	st.init(n);
	while(q--) {
		int a;
		cin >> a;
		if(a == 0) {
			int s, t, x;
			cin >> s >> t >> x;
			st.add(s - 1, t, x);
		}
		else {
			int i;
			cin >> i;
			cout << st.query(i - 1, i) << endl;
		}
	}
}

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

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

h, w, m = LI()
bomb = defaultdict(lambda : 0)
cnt_h = [0] * h
cnt_w = [0] * w
for _ in range(m):
    H, W = LI()
    bomb[(H-1, W-1)] = 1
    cnt_h[H-1] += 1
    cnt_w[W-1] += 1

m_h = max(cnt_h)
m_w = max(cnt_w)
H_l = []
W_l = []
for i in range(h):
    if cnt_h[i] == m_h:
        H_l.append(i)

for i in range(w):
    if cnt_w[i] == m_w:
        W_l.append(i)

ans = m_h + m_w

for i in H_l:
    for j in W_l:
        if not bomb[(i, j)]:
            print(ans)
            quit()
print(ans-1)

Measured memory_bytes: 168348
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
using ll = long long;

ll gcd(ll a,ll b){
  ll g = a%b;
  if(g==0) return b;
  else return gcd(b,g);
}
int main(){
  int n;
  cin>>n;
  vector<ll> a(n);
  for(int i=0;i<n;i++) cin>>a[i];

  ll g=a[0];
  for(int i=1;i<n;i++){
    g=gcd(g,a[i]);
  }

  cout << g << endl;
}


Measured memory_bytes: 1024
fun main(args: Array<String>) {
    val n = readLine()!!.toInt()
    val aList = readLine()!!.split(' ').map(String::toInt)
    val max = aList.max()!!
    val map = IntArray(max+1) { 0 }
    aList.forEach { map[it]++ }
    (1..max).forEach { map[it] = Math.max(map[it] - 1, 0) }
    val sum = map.sum()
    if (sum % 2 == 0) {
        println(n - sum)
    } else {
        println(n - sum - 1)
    }
}


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

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

    if(n>1799)  ans=1;
    else if(n>1599) ans=2;
    else if(n>1399) ans=3;
    else if(n>1199) ans=4;
    else if(n>999)  ans=5;
    else if(n>799)  ans=6;
    else if(n>599) ans=7;
    else ans=8;

    cout<<ans<<endl;
}

int main(){
    //int t;cin>>t;while(t--)
    solve();
}



Measured memory_bytes: 3632
// May this submission get accepted
#pragma GCC optimize ("O3")

#include <bits/stdc++.h>

// 汎用マクロ
#define ALL_OF(x) (x).begin(), (x).end()
#define REP(i,n) for (long long i=0, i##_len=(n); i<i##_len; i++)
#define RANGE(i,is,ie) for (long long i=(is), i##_end=(ie); i<=i##_end; i++)
#define DSRNG(i,is,ie) for (long long i=(is), i##_end=(ie); i>=i##_end; i--)
#define STEP(i, is, ie, step) for (long long i=(is), i##_end=(ie), i##_step = (step); i<=i##_end; i+=i##_step)
#define UNIQUE(v) do { sort((v).begin(), (v).end()); (v).erase(unique((v).begin(), (v).end()), (v).end()); } while (false)
template<class T> bool chmax(T &a, const T &b) { if (a < b) {a = b; return true;} return false; }
template<class T> bool chmin(T &a, const T &b) { if (a > b) {a = b; return true;} return false; }
#define INF 0x7FFFFFFF
#define LINF 0x7FFFFFFFFFFFFFFFLL
#define Yes(q) ((q) ? "Yes" : "No")
#define YES(q) ((q) ? "YES" : "NO")
#define Possible(q) ((q) ? "Possible" : "Impossible")
#define POSSIBLE(q) ((q) ? "POSSIBLE" : "IMPOSSIBLE")
#define DUMP(q) cerr << "[DEBUG] " #q ": " << (q) << " at " __FILE__ ":" << __LINE__ << endl
#define DUMPALL(q) do { cerr << "[DEBUG] " #q ": ["; REP(DUMPALL_ITR, (q).size()) { cerr << (q)[DUMPALL_ITR] << (DUMPALL_ITR == DUMPALL_ITR_len-1 ? "" : ", "); } cerr << "] at " __FILE__ ":" << __LINE__ << endl; } while (false)
template<class T> T gcd(T a, T b) { if (a < b) std::swap(a, b); while (b) std::swap(a %= b, b); return a; }
template<class T> T lcm(const T a, const T b) { return a / gcd(a, b) * b; }

// gcc拡張マクロ
#define popcount __builtin_popcount
#define popcountll __builtin_popcountll

// エイリアス
#define DANCE_ long
#define ROBOT_ unsigned
#define HUMAN_ signed
using  ll = DANCE_ HUMAN_ DANCE_;
using ull = DANCE_ ROBOT_ DANCE_;
using  ld = long double;
using namespace std;

// 標準入出力
struct inp {
    size_t sz;
    inp(size_t _sz = 1) : sz(_sz) {}
    template <typename T> operator T () const { T a; cin >> a; return a; }
    template <typename T> operator vector<T> () const { vector<T> a(sz); for (size_t i = 0; i < sz; i++) cin >> a[i]; return a; }
    template <typename T, typename U> operator pair<T, U> () const { T f; U s; cin >> f >> s; return pair<T, U>(f, s); }
};
inp inp1; // input one
template <typename T> void say(T &x, char end = '\n') { cout << x << end; }
template <typename T> void say(vector<T> &x, char sep = ' ', char end = '\n') { for (size_t i = 0, sz = x.size(); i < sz; i++) { cout << x[i] << (i == sz-1 ? end : sep); } }

// モジュール


// 処理内容
int main() {
    
    ios::sync_with_stdio(false); // stdioを使うときはコメントアウトすること
    cin.tie(nullptr);            // インタラクティブ問題ではコメントアウトすること
    
    ll n = inp1;
    ll k = inp1;
    ll s = inp1;

    vector<ll> a(n, 0);
    ll s_janai;
    if (s == 1) {
        s_janai = 2;
    } else if (s == 2) {
        s_janai = 3;
    } else {
        s_janai = s-1;
    }
    REP(i, n) {
        if (i < k) {
            a[i] = s;
        } else {
            a[i] = s_janai;
        }
    }
    say(a);
    
}

Measured memory_bytes: 2176
def f(a, ratio)
  a.step(a + 1 - 0.1, 0.1).map {|v| (v / ratio).ceil}
end

a, b = gets.split.map(&:to_i)
min = (f(a, 0.08) & f(b, 0.1)).min
p min.nil? ? -1 : min

Measured memory_bytes: 1788
Tiles=input()

N_len=len(Tiles)

type1 = 0

# １スタート
for i in range(N_len):
    if Tiles[i] == str(i%2):
        type1 += 1
        
# 0スタート
type2=0
for i in range(N_len):
    if Tiles[i] != str(i%2):
        type2 += 1
        
print(min(type1,type2))

Measured memory_bytes: 3188
import java.util.*;

public class Main{
  public static void main(String[] args){
    Scanner sc = new Scanner(System.in);

    long a = sc.nextLong();
    long b = sc.nextLong();
    long k = sc.nextLong();

    if(a > k){
      a -= k;
    } else if(b - k + a > 0){
      b = b - k + a; 
      a = 0;
    } else {
      a = 0;
      b = 0;
    }

    System.out.println(a + " " + b);
  }
}


Measured memory_bytes: 23124
import sys

input = sys.stdin.readline

N, K, S = map(int, input().split())
ans = []

large = 1000000000

if S == large:
    for _ in range(K):
        ans.append(S)
    for _ in range(N - K):
        ans.append(1)  
else:
    for _ in range(K):
        ans.append(S)
    for _ in range(N - K):
        ans.append(large)

print(*ans)

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

int main(){

    int N;
    cin >> N;
    map<int, int> count_i;
    rep (i, N-1){
        int a = 0;
        cin >> a;
        count_i[a]++;
    }

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

    return 0;
}

Measured memory_bytes: 13004
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <utility>
#include <tuple>
#include <cstdint>
#include <cstdio>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <deque>
#include <unordered_map>
#include <unordered_set>
#include <bitset>
#include <cctype>
#define ll long long int
#define pb push_back
#define rep(i,n) for(int i=0;i<(n);i++)
#define REP(i,n) for(int i=1;i<=(n);i++)
using namespace std;

int mx8[] = {0,0,1,-1,-1,1,-1,1};
int my8[] = {-1,1,0,0,-1,-1,1,1};
int mx4[] = {1,-1,0,0};
int my4[] = {0,0,-1,1};

//ll mod = 1000000009;

const int MAX = 510000;
const int MOD = 1000000007;

long long fac[MAX], finv[MAX], inv[MAX];

// テーブルを作る前処理
void COMinit() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (int i = 2; i < MAX; i++){
        fac[i] = fac[i - 1] * i % MOD;
        inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }
}

// 二項係数計算
long long COM(int n, int k) {
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}

int main() {
    int n, cnt = 0, a = 0, b = 0,ab = 0; cin >> n;
    rep(i,n){
        string s; cin >> s;
        int l = s.size();
        rep(j,l-1){
            if(s[j]=='A'&&s[j+1]=='B') cnt++;
        }
        if(s[0] == 'B' && s[l-1] == 'A') ab++;
        else if(s[0] == 'B') b++;
        else if(s[l-1] == 'A') a++;
    }
    int ans = 0;
    if(ab > 0) {
        if (a > 0 && b > 0) ans = ab - 1 + 2 + min(a - 1, b - 1);
        else if (a > 0 && b == 0) ans = ab;
        else if (a == 0 && b > 0) ans = ab;
        else ans = ab - 1;
    }else{
        ans = min(a,b);
    }
    cout << ans + cnt << endl;
}




Measured memory_bytes: 3560
#include <algorithm>
#include <string>
#include <math.h>
#include <vector>
#include <iostream>
using namespace std;

int main() 
{
    int N;
    cin >> N;
    vector<int> H(N);
    for (int i = 0; i < N; i++) {
        cin >> H.at(i);
    }
    reverse(H.begin(), H.end());
    
    int ans = 0;
    int hmax = 0;
    for (int i = 1; i < N; i++) {
        if(H.at(i-1) <= H.at(i)){
            hmax++;
        }else{
            hmax = 0;
        }
        ans = max(ans, hmax);
    }
    cout << ans << endl;
}

Measured memory_bytes: 640
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <string>
#include <limits>
#include <algorithm>
#include <map>
#include <sstream>
#include <unordered_map>
#include <set>

using ll = long long;
using ull = unsigned long long;
using uint = unsigned int;
static ull tenq = 1000000000;
static ull mod = tenq + 7;

using namespace std;

int main()
{
  ll N;
  cin >> N;
  vector<ll> ls(N);
  ll A, B, C;
  cin >> A >> B >> C;
  ll take_obj[4] = {0, A, B, C};
  for(auto i = 0; i < N; i++) cin >> ls[i];

  ll beki4 = 1;
  ll res = 1000000000000;
  for (auto i = 0; i < N; i++) beki4 *= 4;
  for (auto i = 0; i < beki4; i++) {
    ll bits = i;
    ll mp = 0;
    ll take[4] = {0, 0, 0, 0};
    for (auto j = 0; bits > 0; bits /= 4, j++) {
      ll k = bits % 4;
      if (k == 0) continue;
      if (take[k] > 0) mp += 10;
      take[k] += ls[j];
    }
    if (take[3] == 0 || take[1] == 0 || take[2] == 0) continue;
    for (auto j = 1; j < 4; j++) mp += abs(take_obj[j] - take[j]);
//    cout << take[0] << ", " << take[1] << ", " << take[2] << " mp=" << mp << endl;
    if (res > mp) {
//      cout << take[0] << ", " << take[1] << ", " << take[2] << " mp=" << mp << endl;
    }
    res = min(res, mp);
  }

  cout << res << endl;

  return 0;
}


Measured memory_bytes: 888
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <string>
#include <vector>
using namespace std;
typedef long long ll;
int main(void){
	int i,n,ans=0,s;
	cin>>n;
	int a[n];
	s=0;
	cin>>a[0];
	for(i=1;i<n;i++){
		cin>>a[i];
		if(a[i]==a[i-1]){
			s++;
		}else if(s>0){
			ans+=max((s+1)/2,1);
			s=0;
		}
		//cout<<s<<" "<<ans<<endl;
	}
	if(s>0)ans+=max((s+1)/2,1);
	cout<<ans<<endl;
}

Measured memory_bytes: 256
#include <stdio.h>
int main()
{
    double r, pi, are, circ;
    pi = 3.141592653589;
    scanf("%lf", &r);
    circ = r * r  * pi;
    are  = 2 * pi * r;
    printf("%lf %lf\n", circ, are);
    return 0;
}


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

#define INF             1e9
#define INFL            1e19
#define XX              first
#define YY              second
#define PB              push_back
#define MP              make_pair

#define NEWLINE         cout << endl;
#define HOISE           cerr << "hoise" << endl
#define PAUSE           system("pause")
#define DEBUG(x)        cerr << #x << " = " << x << endl
#define READ            freopen("alu.txt", "r", stdin)
#define WRITE           freopen("vorta.txt", "w", stdout)
#define FASTIO          ios_base::sync_with_stdio(false);cin.tie(NULL)

#define MASK(x)         for(int i = 0; i < 8; i++){ if(x&(1<<i)){ cout << i << " "; } } cout << endl;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAX = 100 + 2;
const int MAXLOG = log2(MAX) + 2;
const int MAXN = 1e6 + 2;
const int MOD = 1000000007;

inline double dis(pair<double, double> &p1, pair<double,double> &p2)
{
    return sqrt((p1.XX-p2.XX)*(p1.XX-p2.XX) + (p1.YY-p2.YY)*(p1.YY-p2.YY));
}

int main()
{
//    READ;
//    WRITE;
    FASTIO;



    int n;
    cin >> n;
    vector<double> fact(n+1);
    vector< pair<int, pair<double, double> > > v(n);

    fact[0] = 1;
    for(int i = 1; i <= n; i++)
        fact[i] = i*fact[i-1];

    for(int i = 0; i < n; i++){
        v[i].XX = i;
        cin >> v[i].YY.XX >> v[i].YY.YY;
    }
    double sum = 0;
    do{
        double len = 0;
        for(int i = 1; i < n; i++)
            len += dis(v[i].YY, v[i-1].YY);

        sum += len;

    }while(next_permutation(v.begin(), v.end()));

    sum /= fact[n];
    cout << fixed << setprecision(8) << sum;

    return 0;
}




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

using namespace std;
using LL = long long;
using P = pair<int,int>;
const LL mod=1e9+7;
const LL Max_N=21;

LL dp[1<<Max_N+5];

int main(){
	int N;
	cin >> N;
	bool a[25][25];
	rep(i,N){
		rep(j,N) cin >> a[i][j];
	}
	dp[0]=1;
	rep(bit,1<<N){
		LL num=0;
		rep(i,N) if(bit&(1<<i)) num++;
		rep(i,N){
			if(!(bit&(1<<i))) continue;
			if(a[num-1][i]){
				dp[bit]+=dp[bit-(1<<i)];
				dp[bit]%=mod;
			}
		}
	}
	cout << dp[(1<<N)-1] << endl;

	return 0;
}

Measured memory_bytes: 18688
#include <bits/stdc++.h>
#define RI register int
typedef long long LL;

#define FILEIO(name) freopen(name".in", "r", stdin), freopen(name".out", "w", stdout);

using namespace std;

char buf[1000000], *p1 = buf, *p2 = buf;
inline char gc() {
  if (p1 == p2) p2 = (p1 = buf) + fread(buf, 1, 1000000, stdin);
  return p1 == p2 ? EOF : *(p1++);
}
template <class T> inline void read(T &n) {
  n = 0; RI ch = gc(), f;
  while ((ch < '0' || ch > '9') && ch != '-') ch = gc();
  f = (ch == '-' ? ch = gc(), -1 : 1);
  while (ch >= '0' && ch <= '9') n = n * 10 + (ch ^ 48), ch = gc();
  n *= f;
}

int const MAXN = 105, INF = 0x7f7f7f7f;
struct Edges { int to, next, dis; } e[MAXN * MAXN * MAXN];
int head[MAXN * MAXN * MAXN], tot = 1;
int In[MAXN][MAXN], Out[MAXN][MAXN], cnt, S, T, Row[MAXN], Line[MAXN];
int dep[MAXN * MAXN * MAXN], cur[MAXN * MAXN * MAXN];
char s[MAXN][MAXN];
queue <int> q;

inline void addedge(int from, int to, int dis) {
  e[++tot] = (Edges){to, head[from], dis};
  head[from] = tot;
  e[++tot] = (Edges){from, head[to], 0};
  head[to] = tot;
}

bool Bfs() {
  memset(dep, 0, sizeof(dep));
  dep[S] = 1;
  q.push(S);
  while (!q.empty()) {
    int t = q.front(); q.pop();
    for (RI i = head[t]; i; i = e[i].next)
      if (!dep[e[i].to] && e[i].dis)
        dep[e[i].to] = dep[t] + 1, q.push(e[i].to);
  }
  if (!dep[T]) return 0;
  for (RI i = 1; i <= cnt; ++i) cur[i] = head[i];
  return 1;
}

int Dfs(int now, int res) {
  if (now == T || !res) return res;
  int sum = 0;
  for (RI i = cur[now]; i; i = e[i].next) {
    cur[now] = i;
    if (dep[e[i].to] == dep[now] + 1) {
      int d = Dfs(e[i].to, min(res, e[i].dis));
      if (d) {
        sum += d;
        res -= d;
        e[i].dis -= d;
        e[i ^ 1].dis += d;
      }
    }
  }
  return sum;
}

int Dinic() {
  int Maxflow = 0;
  while (Bfs())
    Maxflow += Dfs(S, INF);
  return Maxflow;
}

int main() {
  
#ifdef LOCAL
  FILEIO("a");
#endif

  int n, m; scanf("%d %d", &n, &m);
  for (RI i = 1; i <= n; ++i)
    scanf("%s", s[i] + 1);
  for (RI i = 1; i <= n; ++i) Row[i] = ++cnt;
  for (RI i = 1; i <= m; ++i) Line[i] = ++cnt;
  for (RI i = 1; i <= n; ++i)
    for (RI j = 1; j <= m; ++j) {
      if (s[i][j] == 'o') {
        In[i][j] = ++cnt, Out[i][j] = ++cnt;
        addedge(Out[i][j], Row[i], INF);
        addedge(Out[i][j], Line[j], INF);
        addedge(Row[i], In[i][j], INF);
        addedge(Line[j], In[i][j], INF);
        addedge(In[i][j], Out[i][j], 1);
      }
      if (s[i][j] == 'S') {
        S = ++cnt;
        addedge(S, Row[i], INF);
        addedge(S, Line[j], INF);  
      }
      if (s[i][j] == 'T') {
        T = ++cnt;
        addedge(Row[i], T, INF);
        addedge(Line[j], T, INF);
      }
    }
  int Maxflow = Dinic();
  if (Maxflow > n * m) puts("-1");
  else printf("%d\n", Maxflow);

  return 0;
}

// created by Daniel yuan


Measured memory_bytes: 10624
INF=1e100000
while True:
    n=input()
    if n==0:break
    S=set()
    L=[]
    for i in range(n):
        a,b,c=map(int,raw_input().split())
        L.append((a,b,c))
        S.add(a)
        S.add(b)
    m=len(S)
    R=[[INF]*m for i in range(m)]
    for i in range(m):
        R[i][i]=0
    for a,b,c in L:
        R[a][b]=c
        R[b][a]=c
    for k in range(m):
        for i in range(m):
            for j in range(m):
                R[i][j]=min(R[i][j],R[i][k]+R[k][j])
    city,time=-1,INF
    for i in range(m):
        s=sum(R[i])
        if s<time:
            city=i
            time=s
    print city,time

Measured memory_bytes: 4316
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using vi = vector<int>;
using vvi = vector<vi>;
using vvvi = vector<vvi>;
using vll = vector<ll>;
using vvll = vector<vll>;
using vvvll = vector<vvll>;
using vs = vector<string>;
using pll = pair<ll, ll>;
using vp = vector<pll>;
#define rep(i, n) for(ll i = 0; i < (n); i++)
#define repr(i, a, b) for(ll i = (a); i < (b); i++)
#define ALL(a) (a).begin(), (a).end()
#define SZ(x) ((ll)(x).size())
const ll MOD = 1000000007;
const ll INF = 100000000000000000LL;
inline ll GCD(ll a, ll b){ return b?GCD(b, a % b):a; }
inline ll LCM(ll a, ll b){ return a/GCD(a, b)*b; }
inline ll powint(unsigned long long x, ll y){ ll r=1; while(y){ if(y&1) r*=x; x*=x; y>>=1; } return r; }
inline ll powmod(ll x, ll y, ll m = MOD){ ll r=1; while(y){ if(y&1) r*=x; x*=x; r%=m; x%=m; y>>=1; } return r; }
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; }
#ifdef OJ_LOCAL
#include "dump.hpp"
#else
#define dump(...) ((void)0)
#endif

const ll MAX_N = 510;
ll a[MAX_N][MAX_N];

void solve(ll n, vll& g, ll start){
    //dump(n, g, start);
    if(n <= 1){
        return;
    }
    for(int i = 0; i < n; i += 2){
        for(int j = 1; j < n; j += 2){
            a[g[i]][g[j]] = start;
            a[g[j]][g[i]] = start;
        }
    }
    vll g1;
    vll g2;
    rep(i, n){
        if(i&1){
            g1.push_back(g[i]);
        }else{
            g2.push_back(g[i]);
        }
    }
    solve(SZ(g1), g1, start+1);
    solve(SZ(g2), g2, start+1);
}

int main(){
    cin.tie(0); ios::sync_with_stdio(false);
    cout << fixed << setprecision(15);
    ll n;
    cin >> n;
    vll g(n);
    iota(ALL(g), 0ll);
    solve(n, g, 1);
    rep(i, n-1){
        repr(j, i+1, n){
            cout << a[i][j] << " \n"[j == n-1];
        }
    }
    return 0;
}

Measured memory_bytes: 2560
N = int(input())
A = list(map(int, input().split()))
ans = 0
while A.count(0) != len(A):
    if list(map(lambda x: x%2, A)).count(1) > 0:
       break
    A = list(map(lambda x: x/2, A))
    ans += 1
print(ans)

Measured memory_bytes: 3060
#include <bits/stdc++.h>
using namespace std;
const long long mod = 1e9 + 7;

int main(){
	int A, B, C;
	cin >> A >> B >> C;
	A = A - B;
	C = C - A;
	if(C < 0) C = 0;
	cout << C << endl;
}

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

signed main() {
  int N;
  cin >> N;
  string s[100];
  int t[100];
  for (int i = 0; i < N; i++) {
    cin >> s[i] >> t[i];
  }
  string x;
  cin >> x;

  bool flag = false;
  int ans = 0;
  for (int i = 0; i < N; i++) {
    if (flag) {
      ans += t[i];
    }

    if (s[i] == x) {
      flag = true;
    }
  }

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

Measured memory_bytes: 256
#n=gets.split(' ').map(&:to_i)
#h=gets.split(' ').map(&:to_i)
#tajigen = Array.new(4) { Array.new(2,0) }
#maze = h.times.map { gets.chomp }
n = gets.to_i

ans = 0
for i in 0..n
  if (i%3!=0)&&(i%5!=0)
    ans += i
  end
end

puts ans


Measured memory_bytes: 14364
#include<stdio.h>
int main()
{
double a,b,c,d,e,f,x,y;
while(scanf("%lf %lf %lf %lf %lf %lf",&a,&b,&c,&d,&e,&f)!=EOF){
 y=(c*d-f*a)/(b*d-e*a);
 x=(c-b*y)/a;
 printf("%.3f %.3f\n",x,y);
 }
return 0;}

Measured memory_bytes: 652
H,W,K=map(int,input().split())
C=[]
for i in range(H):
    C.append(input())

import itertools

PRD = list(itertools.product([0,1], repeat=H+W))
ans=0

for i in range(len(PRD)):
    p=PRD[i]
    point=0
    for s in range(H):
        for t in range(W):
            if p[s]+p[H+t]==0 and C[s][t]=='#':
                point+=1
    if point==K:
        #print(p)
        ans+=1

print(ans)

Measured memory_bytes: 9652
#include <bits/stdc++.h>
using namespace std;
int k;
long ans=0;
void gcd(int a, int b, int c){
    //cout << a << " " << b << " " << c << endl;
    int tmpAdd = 0;
    int diviser = a;
    if(diviser>b){
        diviser=b;
    }
    if(diviser>c){
        diviser=c;
    }
    for(int i = diviser;i>=0;i--){
        int tmpPrime = i;
        //cout << "tmpPrime:" << tmpPrime<<endl;
        if((a%tmpPrime==0)&&(b%tmpPrime==0)&&(c%tmpPrime==0)){
            tmpAdd=tmpPrime;
            break;
        }
    }
    ans+=tmpAdd;
    //cout << ans << endl;
    #if 0
        if(c<k){
            c++;
            gcd(a,b,c);
        }else if(b < k){
            b++;
            c=1;
            gcd(a,b,c);
        }else if(a < k){
            a++;
            b=1;
            c=1;
            gcd(a,b,c);
        }else{
            //探索終了
        }
    #endif
    return;
}

int main(){
    cin >> k;
    vector<int>seed;
    //kまでの素数を求める。
    for(int i = 1; i<=k; i++){
        for(int j = 1; j<=k; j++){
            for(int cnt = 1; cnt <=k; cnt++){
                gcd(i,j,cnt);
            }
        }
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 3636
#include<bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i = 0; i < n; i++)
#define REP(i, n) for(int i = 1; i < n; i++)
#define P pair<int, int>
typedef long long ll;
const ll mod = 1e9+7;

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

//繰り返し自乗法による累乗計算
//a**n
ll pow(ll a, ll n){
  if(n == 0) return 1;
  if(n%2 == 0){
    ll res = pow(a, n/2);
    return res * res;
  }
  return a * pow(a, n-1);
}
//繰り返し自乗法によるmod累乗計算
//a**n (mod)
ll modpow(ll a, ll n){
  if(n == 0) return 1;
  if(n%2 == 0){
    ll res = modpow(a, n/2);
    return res * res % mod;
  }
  return a * modpow(a, n-1) % mod;
}
//組み合わせ
//nCa
ll com(ll n, ll a){
  ll x = 1, y = 1;
  rep(i,a){
    x *= n-i;
    y *= i+1;
  }
  ll res = x / y;
  return res;
}
//組み合わせ(mod)
//nCa (mod)
ll modcom(ll n, ll a){
  ll x = 1, y = 1;
  rep(i, a){
    x = x * (n-i) % mod;
    y = y * (i+1) % mod;
  }
  ll ans = x * modpow(y, mod-2) % mod;
  return ans;
}
//gcd 最大公約数
ll gcd(ll x, ll y){
  if(x % y == 0) return y;
  return gcd(y, x%y);
}
//lcm 最小公倍数
ll lcm(ll x, ll y){
  return x * y / gcd(x, y);
}
//ngcd n個の最大公約数
ll ngcd(vector<ll> a){
  ll res;
  res = a[0];
  for(ll i = 1; i < a.size() && res != 1; i++) {
    res = gcd(a[i], res);
  }
  return res;
}
//nlcm n個の最小公倍数
ll nlcm(vector<ll> a) {
  ll res;
  res = a[0];
  for (ll i = 1; i < a.size(); i++) {
    res = lcm(res, a[i]);
  }
  return res;
}
// 素数判定
bool isprime(ll x){
  ll i;
  if(x < 2) return false;
  else if(x == 2) return true;
  if(x % 2 == 0) return false;
  for(i = 3; i*i <= x; i += 2){
    if(x % i == 0) return false;
  }
  return true;
}
// 桁和
ll digsum(ll x){
  ll res = 0;
  while(x > 0){
    res += x % 10;
    x /= 10;
  }
  return res;
}


int main(){
  char a, b;
  cin >> a >> b;
  if(a == b) cout << '=' << endl;
  else if(a > b) cout << '>' << endl;
  else if(a < b) cout << '<' << endl;
}






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

int main()
{
  int n;
  cin >> n;
  pair<pair<string, int>, int> pp[n];
  rep(i, n) {
    cin >> pp[i].first.first >> pp[i].first.second;
    pp[i].first.second *= -1;
    pp[i].second = i + 1;
  }
  sort(pp, pp + n);
  rep(i, n){
    cout << pp[i].second << endl;
  }
  return 0;
}

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

int main(){
    int64_t N, K;
    cin >> N >> K;
    double p[N];
    for ( int64_t i = 0; i < N; ++i ){
        cin >> p[i];
    }
    double max_sum = 0;
    double sum = 0;
    
    /* p[0] から p[K-1] までの和 */
    for ( int64_t i = 0; i < K; ++i ){
        sum = sum + p[i];
    }
    max_sum = sum;
    
    for ( int64_t i = K; i < N; ++i ){
        //cout << sum << endl;
        sum = sum - p[i-K] + p[i];
        max_sum = max(max_sum,sum);
    }
    //cout << sum << endl;
    
    double result;
    result = max_sum / 2.0 + K / 2.0;
    
    cout << fixed << setprecision(7) << result << endl;
    
    return 0;
}


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

//#define DEBUG

#ifdef DEBUG
#define PRINT(A) std::cout << (#A) << ":" << (A) << std::endl;
#else
#define PRINT(A)
#endif

int main(){

  int X, Y, Z;
  cin >> X >> Y >> Z;
  cout << Z << " " << X << " " << Y << endl;

  return 0;

}


Measured memory_bytes: 256
#include<iostream>
#include<math.h>
#include<float.h>
#include<cstdio>
using namespace std;
#define EPS (1e-10)
#define equals(a,b) fabs((a)-(b))<DBL_EPSILON*fmax(1,fmax(fabs(a),fabs(b)))
//点のクラス
class Point{
    public:
        double x,y;
        Point(double x=0,double y=0):x(x),y(y){}

        Point operator + (Point p){return Point(x+p.x,y+p.y);}
        Point operator - (Point p){return Point(x-p.x,y-p.y);}
        Point operator * (double a){return Point(a*x,a*y);}
        Point operator / (double a){return Point(x/a,y/a);}

        double norm(Point p){return p.x*p.x+p.y*p.y;}
        double abs(Point p){return sqrt(norm(p));}    
        bool operator < (const Point &p)const{
            return x!=p.x?x<p.x:y<p.y;
        }
        bool operator == (const Point &p)const{
            return equals(x,p.x)&&equals(y,p.y);
        }
};
typedef Point Vector;
struct Segment{ Point p1,p2; };
typedef Segment Line;
double norm(Vector v){return v.x*v.x+v.y*v.y;} 
double abs(Vector v){return sqrt(norm(v));}    
//内積
double dot(Vector a,Vector b){ return a.x*b.x+a.y*b.y; }
//外戚
double cross(Vector a,Vector b){ return a.x*b.y-a.y*b.x; }
//直交
bool isOrthogonal(Vector a,Vector b){ return equals(dot(a,b),0.0); }
bool isOrthogonal(Point a1,Point a2,Point b1,Point b2){ return isOrthogonal(a1-a2,b1-b2); }
bool isOthogonal(Segment s1,Segment s2){ return equals(dot(s1.p1-s1.p2,s2.p1-s2.p2),0.0); }
//平行
bool isParallel(Vector a,Vector b){ return equals(cross(a,b),0.0); }
bool isParallel(Point a1,Point a2,Point b1,Point b2){ return isParallel(a1-a2,b1-b2); }
bool isParallel(Segment s1,Segment s2){ return equals(cross(s1.p2-s1.p1,s2.p2-s2.p1),0.0); }
//射影
Point project(Segment s,Point p){ //射影　p377
    Vector base=s.p2-s.p1;
    double r=dot(p-s.p1,base)/norm(base);
    return s.p1+base*r;
}
//反射　p379
Point reflect(Segment s,Point p){return p+(project(s,p)-p)*2.0;}
//ベクトルa,bの位置関係
int ccw(Point p0,Point p1,Point p2){
    Vector a=p1-p0;
    Vector b=p2-p0;
    if(cross(a,b)>EPS) return 1;//p0,p1,p2が反時計回り
    if(cross(a,b)<-EPS) return -1;//p0,p1,p2が時計回り
    if(dot(a,b)<-EPS) return 2;//p1,p0,p2の順で一直線
    if(norm(a)<norm(b)) return -2;//p0,p1,p2の順で一直線
    return 0; //p0,p2,p1の順で一直線
}
//交差判定　p389
bool intersect(Point p1,Point p2,Point p3,Point p4){
    return ( ccw(p1,p2,p3)*ccw(p1,p2,p4)<=0&&
            ccw(p3,p4,p1)*ccw(p3,p4,p2)<=0);//p1,p2,p3,p4の順で一直線になるのを除く
}
bool intersect(Segment s1,Segment s2){
    return intersect(s1.p1,s1.p2,s2.p1,s2.p2);
}
//交点の座標　p392
Point getCrossPoint(Segment s1,Segment s2){ 
    Vector base=s2.p2-s2.p1;
    double d1=abs(cross(base,s1.p1-s2.p1));
    double d2=abs(cross(base,s1.p2-s2.p1));
    double t=d1/(d1+d2);
    return s1.p1+(s1.p2-s1.p1)*t;
}
int main(){
    int q;
    Point p1,p2;
    cin>>q;
    Point p[4],pp;
    Segment s1,s2;
    for(int i=0;i<q;i++){
        cin>>p[0].x>>p[0].y>>p[1].x>>p[1].y;
        cin>>p[2].x>>p[2].y>>p[3].x>>p[3].y;
        s1.p1=p[0]; s1.p2=p[1];
        s2.p1=p[2]; s2.p2=p[3];
        pp=getCrossPoint(s1,s2);
        printf("%.10f %.10f\n",pp.x,pp.y);
    }
    return 0;
}



Measured memory_bytes: 3280
#include <math.h>
#include <stdlib.h>
#include <string.h>
#include <algorithm>
#include <array>
#include <iomanip>
#include <iostream>
#include <limits>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>

using namespace std;

int main() {
    int A, B;
    cin>> A >> B;
    if(A+B<24)cout<<A+B<<endl;
    else cout<<A+B-24<<endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#ifdef DEBUG
#include "_debug.cpp"
#include "callable.hpp/callable.hpp"
#endif
#define endl '\n'
using namespace std;
using ll = long long;
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int d, n;
    cin >> d >> n;
    if(n == 100) n++;
    cout << n;
    for(int i = 0; i < d; i++) {
        cout << "00";
    }
    cout << endl;
    return 0;
}


Measured memory_bytes: 256
#include <utility>
#include <vector>
#include <iostream>
#include <algorithm>
#include <functional>
#include <map>
#include <set>
#include <list>
#define REP(i, n) for (int i = 0; i < n; i++)
using namespace std;

typedef long long ll;
typedef pair<ll, ll> Pll;

int main()
{
    int A, B, K;
    cin >> A >> B >> K;

    int cnt = 0;
    for (int i = min(A, B); i >= 1; i--)
    {
        if (A % i == 0 && B % i == 0)
        {
            cnt++;
        }
        if (cnt == K)
        {
            cout << i << endl;
            break;
        }
    }
}

void cheatsheet()
{
    // loop
    // vector<int> vec(10);
    vector<int> vecloop;
    REP(i, 10)
    {
        vecloop.push_back(i);
    }

    // swap
    int a = 1;
    int b = 5;
    swap(a, b); // -> a = 5, b = 1

    // sort
    int arr[] = {1, 2, 3, 4, 5, 6, 7, 8, 9};
    sort(arr, arr + 9, greater<int>()); // 9 8 7 6 5 4 3 2 1

    // lower
    vector<int> vec(arr, end(arr));
    sort(vec.begin(), vec.end());
    cout << lower_bound(vec.begin(), vec.end(), 2)[0]; // 2

    // map
    map<Pll, ll> m;
    m[Pll(10, 100)] = 100;
}

Measured memory_bytes: 256
A,B,C,X,Y = map(int,input().split())


ans = X * A + Y * B

bul = True

while bul:

    bul = False

    if X > 0 and Y > 0 and A + B > 2*C:

        bul = True
        X -= 1
        Y -= 1

        ans = ans - (A+B) + 2*C

    elif X > 0 and A > 2*C:

        bul = True
        X -= 1

        ans = ans - A + 2*C

    elif Y > 0 and B > 2*C:

        bul = True
        Y -= 1

        ans = ans - B + 2*C

print (ans)
        


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

int main() {
  int N, K;
  cin >> N >> K;
  double ans = 0.0f;

  for(int i = 1; i <= N; ++i) {
    int score = i;
    double r = (double)N;
    while(score < K) {
      score *= 2;
      r *= 2.0;
    }
    ans += 1.0 / r;
  }
  cout << setprecision(12) << ans << endl;
  return 0;
}

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

long long N, X[1009], Y[1009], H[1009]; vector<tuple<long long, long long, long long>>vec;

int main(){
    cin >> N;
    tuple<long long, long long, long long>G = make_tuple(-1, -1, -1);
    for (int i = 1; i <= N; i++) {
        cin >> X[i] >> Y[i] >> H[i];
        if (H[i] >= 1) G = make_tuple(X[i], Y[i], H[i]);
    }
    for (int i = 0; i <= 100; i++) {
        for (int j = 0; j <= 100; j++) {
            long long V = get<2>(G) + abs(get<0>(G) - i) + abs(get<1>(G) - j); V = max(V, 0LL); bool flag = true;
            for (int k = 1; k <= N; k++) {
                long long VV = V - abs(X[k] - i) - abs(Y[k] - j); VV = max(VV, 0LL);
                if (H[k] != VV) flag = false;
            }
            if (flag == true) cout << i << " " << j << " " << V << endl;
        }
    }
    return 0;
}


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

int main() {
    string s, l, r; cin >> s;
    int q, rev = 0; cin >> q;
    for (int i = 0; i < q; i++) {
        int t; cin >> t;
        if (t == 1) rev = 1 - rev;
        else {
            int f; char c;
            cin >> f >> c;
            f--;
            if (rev) f = 1 - f;
            if (f == 0) l = c + l;
            else r += c;  
        }
    }
    string ans = l + s + r;
    if (rev) reverse(ans.begin(), ans.end());
    cout << ans << endl;
}

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

using namespace std;

int s(int N) {
    if(N == 0) return 0;
    return (N % 10) + s(N / 10);
}

int main() {
    int N;

    scanf("%d", &N);

    printf("%s\n", N % s(N) == 0 ? "Yes" : "No");

    return 0;
}

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

int main(){
    int n; cin >>n;
    int min = 200001;
    int ans = 0;
    for(int i=0; i<=n; ++i){
        int a; cin >> a;
        if(a<min){
            min = a;
            ans ++;
        }
    }
    cout << ans << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define fi			first
#define se			second
#define fz(i,a,b)	for(int i=a;i<=b;i++)
#define fd(i,a,b)	for(int i=a;i>=b;i--)
#define foreach(it,v) for(__typeof(v.begin()) it=v.begin();it!=v.end();it++)
#define all(a)		a.begin(),a.end()
#define giveup(...) return printf(__VA_ARGS__),0;
#define fill0(a)	memset(a,0,sizeof(a))
#define fill1(a)	memset(a,-1,sizeof(a))
#define fillbig(a)	memset(a,0x3f,sizeof(a))
#define fillsmall(a) memset(a,0xcf,sizeof(a))
#define mask(a)		(1ll<<(a))
#define maskx(a,x)	((a)<<(x))
#define _bit(a,x)	(((a)>>(x))&1)
#define _sz(a)		((int)(a).size())
#define filei(a)	freopen(a,"r",stdin);
#define fileo(a)	freopen(a,"w",stdout);
#define fileio(a) 	freopen(a".in","r",stdin);freopen(a".out","w",stdout)
#define eprintf(...) fprintf(stderr,__VA_ARGS__)
#define put(x)		putchar(x)
#define eoln        put('\n')
#define space		put(' ')
#define y1			y_chenxiaoyan_1
#define y0			y_chenxiaoyan_0
#define int long long
typedef pair<int,int> pii;
inline int read(){
	int x=0,neg=1;char c=getchar();
	while(!isdigit(c)){
		if(c=='-')	neg=-1;
		c=getchar();
	}
	while(isdigit(c))	x=x*10+c-'0',c=getchar();
	return x*neg;
}
inline void print(int x){
	if(x<0){
		putchar('-');
		print(abs(x));
		return;
	}
	if(x<=9)	putchar(x+'0');
	else{
		print(x/10);
		putchar(x%10+'0');
	}
}
inline int qpow(int x,int e,int _MOD){
	int ans=1;
	while(e){
		if(e&1)	ans=ans*x%_MOD;
		x=x*x%_MOD;
		e>>=1;
	}
	return ans;
}
int a=read(),b=read(),n=read(),ans=0;
signed main(){
	fz(i,max(min(n,b-1)-100000000,0ll),min(n,b-1)){
		ans=max(ans,(int)(1.0*a*i)/b);
//		cout<<i<<" "<<(int)(1.0*a*i/b)-a*(int)(1.0*i/b)<<endl;
	}
	cout<<ans<<endl;
	return 0;
}

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

int main(){
  ll x, y;
  cin >> x >> y;
  
  ll ans = LLONG_MAX;
  
  if(y >= x){
    ans = min(ans, y - x);
  }
  if(-y >= x){
    ans = min(ans, 1 + -y - x);
  }

  if(y >= -x){
    ans = min(ans, 1 + y + x);
  }

  if(-y >= -x){
    ans = min(ans, 2 - y + x);
  }

  cout << ans << '\n';
  return 0;
}


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

int main()
{
  int N;
  cin >> N;
  vector<int> d(N);
  rep(i,N) cin >> d[i];

  sort(d.begin(),d.end());
  int c= N/2;
  int ans=0;
  if(d[c-1] < d[c]) {
    ans = d[c]-d[c-1];
  }
  cout << ans << endl;
}

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

using namespace std;

int main(){
	string s;
	cin>>s;
	map<char,int>m;
	for(int i=0;i<(int)s.size();i++){
		m[s[i]]++;
	}
	for(auto i:m){
		if(i.second & 1){
			cout<<"No";
			return 0;
		}
	}
	cout<<"Yes";
}

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

int n, cnt[MAXN];

int main(){
    scanf("%d", &n);
    for (int i=0;i<n;i++){
        int x;
        scanf("%d", &x);
        cnt[x]++;
        cnt[(x+1)]++;
        cnt[(x-1)]++;
    }
    sort(cnt, cnt+MAXN);
    printf("%d\n", cnt[MAXN-1]);
    return 0;
}


Measured memory_bytes: 640