akhauriyash/Code-Regression huggingface dataset:
/**
*    author:  yuya1234
*    created: 10.07.2020 16:09:36
**/

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

#define REP(i,n) for(ll i=0;i<(ll)(n);i++)
#define REPD(i,n) for(ll i=n-1;i>=0;i--)
#define FOR(i,a,b) for(ll i=a;i<=(ll)(b);i++)
#define FORD(i,a,b) for(ll i=a;i>=(ll)(b);i--)
#define FORV(i,v) for(auto i=v.begin(); i!=v.end();i++)

#define SORT(s) sort((s).begin(),(s).end())
#define SORTD(s) sort((s).rbegin(),(s).rend())
#define UNIQUE(v) v.erase( unique(v.begin(), v.end()), v.end() );

#define SZ(x) ((int)(x).size())
#define MEMSET(v, h) memset((v), h, sizeof(v))

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

  double w,h,x,y;
  cin>>w>>h>>x>>y;

  double sum1,sum2,ans=0;
  int cnt=0;

  if(w!=x)
  {
    sum1=(w-x)*h;
    sum2=x*h;
    ans=min(sum1,sum2);
  }

  if(h!=y)
  {
    sum1=(h-y)*w;
    sum2=y*w;
    if(ans==min(sum1,sum2))cnt=1;
    ans=max(ans,min(sum1,sum2));
  }

  if(ans==h*w/2 && cnt==1)cnt=1;
  else cnt=0;
  ans=max(ans,h*w/2);

  printf("%.6lf %d\n",ans,cnt);

  return 0;
}

Measured memory_bytes: 3724
A[9999],B[9999];z(int*a,int*b){return*b-*a;}
main(n,i,j){for(;scanf("%d",&n),n;puts(i>n?"No":"Yes")){
for(i=0;i<n;i++)scanf("%d",A+i);
for(i=0;i<n;i++)scanf("%d",B+i);
for(i=qsort(A,n,4,z);i<n;A[i++]?i=n+1:1)for(j=0;j<n;j++)if(B[j])A[i]--,B[j]--;
}exit(0);}

Measured memory_bytes: 728
#include<iostream>
#include<set>
using namespace std;
int main(){
  set<int>st;
  int n,f;
  cin>>n;
  for (int i=0; i<n;i++){
    cin>>f;
    st.insert(f);
  }
  if(n==st.size()) cout<<"YES"<<endl;
  else cout<<"NO"<<endl;
  return 0;
}

Measured memory_bytes: 12968
(* 素集合データ構造 *)
module UnionFind : sig
  type t

  (* 1要素だけを含む集合を作る *)
  val make : unit -> t
  (* 与えられた集合同士が同一かどうか判定する *)
  val equal : t -> t -> bool
  (* 与えられた集合同士を合併する *)
  val unite : t -> t -> unit
  (* 与えられた集合に属する要素の数を求める *)
  val cardinal : t -> int
end = struct
  type t = node ref
  and node = Root of int | Link of t

  let make () = ref (Root 1)

  let rec find uf =
    match !uf with
    | Root _ -> uf
    | Link uf' ->
        let root = find uf' in
        uf := Link root; root

  let equal uf uf' = find uf == find uf'

  let unite uf uf' =
    let root = find uf in
    let root' = find uf' in
    if root != root' then begin
      let Root card = !root in
      let Root card' = !root' in
      let root, root' =
        if card <= card'
        then root, root'
        else root', root in
      root := Root (card + card');
      root' := Link root
    end

  let cardinal uf =
    match find uf with { contents = Root n } -> n
end

let () = Scanf.scanf "%d %d\n" @@ fun n m ->
  let abs = Array.init m @@ fun _ -> Scanf.scanf "%d %d\n" @@ fun a b -> a - 1, b - 1 in
  let uf = Array.init n @@ fun _ -> UnionFind.make () in
  let ans = Array.make (m + 1) (n * (n - 1) / 2) in
  for i = m - 1 downto 0 do
    let (a, b) = abs.(i) in
    ans.(i) <- ans.(i + 1) -
      if UnionFind.equal uf.(a) uf.(b)
      then 0
      else begin
        let n = UnionFind.cardinal uf.(a) in
        let m = UnionFind.cardinal uf.(b) in
        UnionFind.unite uf.(a) uf.(b); n * m
      end
  done;
  for i = 1 to m do
    Printf.printf "%d\n" ans.(i)
  done



Measured memory_bytes: 14976
parseInt(x) = parse(Int, x)
parseMap(x::Array{SubString{String},1}) = map(parseInt, x)
function bsearch(a,x);l,r=1,length(a);while l<=r;m=l+div(r-l,2);if a[m]<x;l=m+1;else;r=m-1;end;end;return(l-1);end

function main()
	x,a = readline() |> split |> parseMap
	println(x<a?0:10)
end

main()

Measured memory_bytes: 164636
import sys
sys.setrecursionlimit(10 ** 7)

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

# BIT
# Binary Index Tree
# 二分探索

N = int(input())
P = list(map(int, input().split()))
p_to_i = {a: i for i, a in enumerate(P, 1)}


# A1 ... AnのBIT(1-indexed)
BIT = [0]*(N+1)


# A1 ~ Aiまでの和 O(logN)
def BIT_query(idx):
    res_sum = 0
    while idx > 0:
        res_sum += BIT[idx]
        idx -= idx & (-idx)
    return res_sum


# Ai += x O(logN)
def BIT_update(idx, x):
    while idx <= N:
        BIT[idx] += x
        idx += idx & (-idx)
    return


# x <= A1 - Ai となるiの最小値(1-indexed) O(logN)
def BIT_search(x):
    i = 0
    step = 1 << (N.bit_length() - 1)

    while step:
        if i + step <= N and BIT[i + step] < x:
            x -= BIT[i + step]
            i += step

        step >>= 1
    return i + 1


ans = 0
for p in range(N, 0, -1):
    i = p_to_i[p]

    #print("p == ", p, "i =", i)

    # 左,右
    LEFT = BIT_query(i)
    RIGHT = N - p - LEFT

    #print("LEFT,RIGHT : ", LEFT, RIGHT)

    cnt = 0

    # 左に0個 AND 右に0個の時
    if LEFT == 0 and RIGHT == 0:
        BIT_update(i, 1)
        continue

    # a ,,, b ,, i ,, c ,, d
    a = BIT_search(LEFT - 1) if LEFT >= 2 else 0
    b = BIT_search(LEFT) if LEFT >= 1 else 0
    c = BIT_search(LEFT + 1) if RIGHT >= 1 else N + 1
    d = BIT_search(LEFT + 2) if RIGHT >= 2 else N + 1

    if b != 0:
        cnt += (b - a) * (c - i)
    if c != N + 1:
        cnt += (d - c) * (i - b)

    BIT_update(i, 1)
    ans += p * cnt

    #print("a,b,c,d : ", a, b, c, d)
    #print("cnt,score :", cnt, cnt * p)
    #print("ans : ", ans)


print(ans)


Measured memory_bytes: 63136
import copy
w,h = 8,8
tile = [[] for i in xrange(h)]
for i in xrange(h):
    temp = raw_input()
    for j in xrange(w):
        tile[i].append(temp[j])
for i in xrange(3):
    if i is 0: print 90
    elif i is 1: print 180
    elif i is 2: print 270
    tile_copy = copy.deepcopy(tile)
    for i in xrange(w):
        for j in xrange(h):
            tile[j][i] = tile_copy[w-1-i][j]
    for i in xrange(h):
        print "".join(tile[i])

Measured memory_bytes: 5000
#include <cstdio>
#include <functional>
#include <algorithm>
#include <vector>
#include <limits>
#include <numeric>
#include <type_traits>
#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;
//    }
//};
struct UnionFind {
    int n, cnt;
    vector<int> par, rank, sz;

    UnionFind(int n) : n(n), cnt(n), par(n), rank(n), sz(n, 1) { iota(par.begin(), par.end(), 0); }

    int find(int x) {
        if (x == par[x]) return x;
        return par[x] = find(par[x]);
    }

    bool same(int x, int y) { return find(x) == find(y); }

    int size(int x) { return sz[find(x)]; }

    void unite(int x, int y) {
        x = find(x), y = find(y);
        if (x == y) return;
        if (rank[x] < rank[y]) {
            par[x] = y;
            sz[y] += sz[x];
        } else {
            par[y] = x;
            sz[x] += sz[y];
            if (rank[x] == rank[y]) {
                rank[x]++;
            }
        }
        cnt--;
    }
};
bool flag[100010];
int main() {
    int N,M; cin >> N >> M;
    int X[100010], Y[100010], Z[100010];

    UnionFind uni=UnionFind(N+1);
    rep(i,M){
        cin >> X[i] >> Y[i] >> Z[i];
        uni.unite(X[i], Y[i]);
    }

    int ans=0;
    for(int i=1; i<=N; i++){
        if(!flag[uni.find(i)]){
            ans++;
            flag[uni.find(i)]=true;
        }
    }

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


Measured memory_bytes: 2688
def main():
    n=int(raw_input())
    ta=[map(int,raw_input().split()) for _ in xrange(n)]
    for i in xrange(1,n):
        if ta[i-1][0]>ta[i][0] and ta[i-1][1]>ta[i][1]:
            mx=max((ta[i-1][0]-1)/ta[i][0]+1,(ta[i-1][1]-1)/ta[i][1]+1)
            ta[i][0]=ta[i][0]*mx
            ta[i][1]=ta[i][1]*mx
        elif ta[i-1][0]>ta[i][0]:
            ta[i][1]=ta[i][1]*((ta[i-1][0]-1)/ta[i][0]+1)
            ta[i][0]=ta[i][0]*((ta[i-1][0]-1)/ta[i][0]+1)
        elif ta[i-1][1]>ta[i][1]:
            ta[i][0]=ta[i][0]*((ta[i-1][1]-1)/ta[i][1]+1)
            ta[i][1]=ta[i][1]*((ta[i-1][1]-1)/ta[i][1]+1)
    print(ta[n-1][0]+ta[n-1][1])
main()

Measured memory_bytes: 2820
import sys
input=lambda: sys.stdin.readline().rstrip()
n,s=map(int,input().split())
A=[int(i) for i in input().split()]
mod=998244353
B=[[0]*(s+1) for _ in range(n+1)]
ans=0
for i in range(n):
  a=A[i]
  if a<s:
    B[i+1][a]+=i+1
  elif a==s:
    B[i+1][a]+=(i+1)*(n-i)
  for j in range(s+1):
    if j<=s:
      B[i+1][j]+=B[i][j]
    if 0<=j-a and j<s:
      B[i+1][j]+=B[i][j-a]
    if 0<=j-a and j==s:
      B[i+1][j]+=B[i][j-a]*(n-i)
    B[i+1][j]%=mod
print(B[n][s])

Measured memory_bytes: 112604
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		// TODO 自動生成されたメソッド・スタブ

		Scanner sc = new Scanner(System.in);
		int X = sc.nextInt();
		int Coin500 = 0;
		int Coin5 = 0;

		while(X >= 500) {
			X = X - 500;
			Coin500++;
		}
		while(X >= 5) {
			X = X - 5;
			Coin5++;
		}

		System.out.println(Coin500*1000 + Coin5*5);
	}

}


Measured memory_bytes: 22996
#include <iostream>

using namespace std;

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

    int n; cin >> n;
    int data[n];
    for (int i = 0; i < n; i++)
    {   
        cin >> data[i];
    }   
    int mul = 0;
    int halfmul = 0;
    int notmul = 0;
    for (int i = 0; i < n; i++)
    {   
        if (data[i] % 4 == 0) ++mul;
        else if (data[i] % 2 == 0) ++halfmul;
        else ++notmul;
    }   
    if (halfmul > 0) ++notmul;
    if (mul >= notmul || notmul - mul == 1) cout << "Yes\n";
    else cout << "No\n";
    return 0;
}

Measured memory_bytes: 640
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int INF = 1e10;
const int MOD = 1e9 + 7;
#define dump(x) cout << #x << " = " << (x) << endl;
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define pb push_back
#define all(v) (v).begin(), (v).end()
int H, W, w[2010][2010], h[2010][2010], a[2010][2010];
void solve()
{
}

signed main()
{
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    cin >> H >> W;
    FOR(i, 0, H)
    FOR(j, 0, W)
    {
        char x;
        cin >> x;
        if (x == '.')
            a[i][j]++;
    }
    FOR(i, 0, H)
    {
        int t = 0;
        int s = 0;
        FOR(j, 0, W + 1)
        {
            if (a[i][j]) {
                if (!t)
                    s = j;
                t++;
            } else {
                if (t) {
                    FOR(k, s, j)
                    {
                        w[i][k] = t;
                    }
                }
                t = 0;
            }
        }
    }
    FOR(j, 0, W)
    {
        int t = 0;
        int s = 0;
        FOR(i, 0, H + 1)
        {
            if (a[i][j]) {
                if (!t)
                    s = i;
                t++;
            } else {
                if (t) {
                    FOR(k, s, i)
                    {
                        h[k][j] = t;
                    }
                }
                t = 0;
            }
        }
    }
    int ans = 0;
    FOR(i, 0, H)
    {
        FOR(j, 0, W)
        {
            int x;
            x = w[i][j] + h[i][j];
            ans = max(ans, x);
        }
    }
    ans--;
    cout << ans << endl;
    solve();
    return 0;
}


Measured memory_bytes: 94848
#include <bits/stdc++.h>
using namespace std;
int n;
vector <string> str;
string mem[15][15];
typedef pair <string,int> P;

string con(string a,string b){
  int K=0;
  for(int i=0;i<a.size();i++){
    int j=i,k=0;
    while(a[j]&&b[k]&&a[j]==b[k]) j++,k++;
    if(!a[j]||!b[k])K=max(K,k);
  }
  return b.substr(K,b.size());
}

string solve(){
  string dp[1<<14][14];
  for(int i=0;i<n;i++) dp[1<<i][i]=str[i];
  
  for(int i=0;i<(1<<n);i++)
    for(int k=0;k<n;k++){
      if(dp[i][k]=="")continue;
      for(int j=0;j<n;j++){
	if((i&(1<<j)))continue;
	string nx=dp[i][k]+mem[k][j];
	int ni=i|1<<j;
	if(!dp[ni][j].size()||nx.size()<dp[ni][j].size()) dp[ni][j]=nx;
	else if(nx.size()==dp[ni][j].size()&&dp[ni][j]>nx)dp[ni][j]=nx;
      }
    }

  string res;
  for(int i=0;i<n;i++) 
    if(res==""||res.size()>dp[(1<<n)-1][i].size()) res=dp[(1<<n)-1][i];
    else if(dp[(1<<n)-1][i].size()==res.size()) res=min(res,dp[(1<<n)-1][i]);
   return res;
}

int main(){
  
  while(cin>>n,n){
    str.resize(n);
    for(int i=0;i<n;i++)cin>>str[i];

    for(int i=0;i<n;i++)
      for(int j=0;j<n;j++){
	if(i==j)continue;
	if(con(str[i],str[j])==""){
	  str.erase(str.begin()+j);
	  n--;
	  i=-1;
	  break;
	}
      }
    
    for(int i=0;i<n;i++)
      for(int j=0;j<n;j++)mem[i][j]=con(str[i],str[j]);

    cout<<solve().size()<<endl;
  }

  return 0;
}

Measured memory_bytes: 30792
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ll long long
#define P pair<int,int>
#define fi first
#define se second
#define rep(i,n) for(int i=0;i<n;i++)
#define INF 1000000000
#define MOD 1000000007
#define all(v) v.begin(),v.end()
#define pb push_back
int dx[]={0,1,0,-1},dy[]={1,0,-1,0};
int kaijo[200010];
struct edge{int to,cost;};
int gcd(int a,int b){
	if(b==0)return a;
	return gcd(b,a%b);
}
int lcm(int a,int b){
	return a/gcd(a,b)*b;
}
bool prime(int a){
	if(a==1)return false;
	for(int i=2;i*i<=a;i++){
		if(a%i==0)return false;
	}
	return true;
}
bool kosa(double ax,double ay,double bx,double by,double cx,double cy,double dx,double dy){//線分の交差判定
	double ta=(cx-dx)*(ay-cy)+(cy-dy)*(cx-ax);
	double tb=(cx-dx)*(by-cy)+(cy-dy)*(cx-bx);
	double tc=(ax-bx)*(cy-ay)+(ay-by)*(ax-cx);
	double td=(ax-bx)*(dy-ay)+(ay-by)*(ax-dx);
	return tc*td<0&&ta*tb<0;
}
void init_fact(int n){
	kaijo[0]=1;
	for(int i=1;i<=n;i++){
		kaijo[i]=kaijo[i-1]*i;
		kaijo[i]%=MOD;
	}
}
int modpow(int a,int b){
	if(b==0)return 1;
	if(b%2)return modpow(a,b-1)*a%MOD;
	int memo=modpow(a,b/2);
	return memo*memo%MOD;
}
int comb(int a,int b){
	if(b>a)return 0;
	if(a==b)return 1;
	return kaijo[a]*modpow(kaijo[a-b],MOD-2)%MOD*modpow(kaijo[b],MOD-2)%MOD;
}
int g(int x){
	x=modpow(x,MOD-2);
	return x;
}
string s;
int ans=0;
string b,now;
signed main(){
	cin>>s;
	rep(i,s.size()){
		now+=s.substr(i,1);
		if(now!=b){
			b=now;
			now="";
			ans++;
		}
	}
	cout<<ans<<endl;
	return 0;
}


Measured memory_bytes: 1152
MOD = int(1e9) + 7
MAX = int(2e6) + 7


def div(a, b):
    return a * pow(b, MOD-2, MOD) % MOD


FACT = [1] * (MAX+1)
for i in range(1, MAX+1):
    FACT[i] = (i * FACT[i-1]) % MOD
INV = [1] * (MAX+1)
INV[MAX] = div(1, FACT[MAX])
for i in range(MAX, 0, -1):
    INV[i-1] = (INV[i] * i) % MOD


def combination(m, n):
    return (FACT[m] * INV[n] * INV[m-n]) % MOD


def main():
    K = int(input())
    S = input()
    N = len(S)
    pow25 = [1] * (K+1)
    pow26 = [1] * (K+1)
    for i in range(K):
        pow25[i+1] = (pow25[i] * 25) % MOD
        pow26[i+1] = (pow26[i] * 26) % MOD
    ans = 0
    for m in range(N, N+K+1):
        tmp = (combination(m-1, N-1) * pow25[m-N] * pow26[N+K-m]) % MOD
        ans = (ans + tmp) % MOD
    print(ans)


if __name__ == "__main__":
    main()


Measured memory_bytes: 122852
#include <iostream>

using namespace std;

int main(){
	int comp[30], present[28];
	int absent[2], k;

	for (int i = 0; i < 30; i++){
		comp[i] = i + 1;
	}
	
	for (int i = 0; i < 28; i++){
		cin >> present[i];
	}

	for (int i = 0; i < 30; i++){
		for (int j = 0; j < 28; j++){
			if (comp[i] == present[j]){
				comp[i] = 0;
			}
		}
	}
	
	k = 0;
	for (int i = 0; i < 30; i++){
		if (comp[i] != 0){
			absent[k] = comp[i];
			k++;
		}
	}

	if (absent[0] > absent[1]){
		cout << absent[1] << "\n" << absent[0] << endl;
	}
	else {
		cout << absent[0] << "\n" << absent[1] << endl;
	}
}

Measured memory_bytes: 3084
#include <bits/stdc++.h>
#define _CRT_SECURE_NO_WARNINGS
#define ll long long
#define BUF 1e5
#define INF 1<<30
using namespace std;
ll MOD = 1e9 + 7;
ll A, B, C, D, G, H, N, M, L, K, P, Q, R, W, X, Y, Z;
string S;
ll ans = 0;

int main() {
	cin >> H>>W;
	int h, w;
	cin >> h >> w;
	cout << (H - h)*(W - w) << endl;
}

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

int main() {
  int N;
  cin >> N;
  vector<string> W(N);
  for (int i=0;i<N;i++) {
    cin >> W.at(i);
  }
  
  bool same_words=false, judge=false;
  for (int i=1;i<N;i++) {
    if (W.at(i-1).at(W.at(i-1).size()-1) != W.at(i).at(0)) {
      judge = true;
      break;
    }
    for (int j=0;j<i;j++) {
      if (W.at(i) == W.at(j)) {
        same_words = true;
        break;
      }
    }
    if (same_words) {
      judge = true;
      break;
    }
  }
  
  if (judge) {
    cout << "No" << endl;
  }
  else {
    cout << "Yes" << endl;
  }
}   

Measured memory_bytes: 256
#include <bits/stdc++.h>
// #include <boost/multiprecision/cpp_int.hpp>
// using i128 = boost::multiprecision::int128_t;
#define _GLIBCXX_DEBUG
using namespace std;
using ll = long long;
using ld = long double;
using V = vector<int>;
using Vll = vector<ll>;
using Vld = vector<ld>;
using Vbo = vector<bool>;
using VV = vector<V>;
using VVll = vector<Vll>;
using VVld = vector<Vld>;
using VVbo = vector<Vbo>;
using VVV = vector<VV>;
using VVVll = vector<VVll>;
using P = pair<int, int>;
using Pll = pair<ll, ll>;
using Pld = pair<ld, ld>;
#define rep2(i, m, n) for(ll i=int(m); i<int(n); ++i)
#define drep2(i, m, n) for(ll i=int(m)-1; i>=int(n); --i)
#define rep(i, n) rep2(i, 0, n)
#define drep(i, n) drep2(i, n, 0)
#define all(a) a.begin(), a.end()
struct fast_ios { fast_ios(){ cin.tie(nullptr); ios::sync_with_stdio(false); cout << fixed << setprecision(20); }; } fast_ios_;
template<typename T> inline bool chmin(T &a, T b) { if (a > b) { a = b; return true; } return false; }
template<typename T> inline bool chmax(T &a, T b) { if (a < b) { a = b; return true; } return false; }
template<typename T1, typename T2> istream &operator>>(istream &is, pair<T1, T2> &p) { is >> p.first >> p.second; return is; }
template<typename T1, typename T2> ostream &operator<<(ostream &os, const pair<T1, T2> &p) { os << "(" << p.first << ", " << p.second << ")"; return os; }
template<typename T> istream &operator>>(istream &is, vector<T> &v) { for (auto &e : v) is >> e; return is; }
template<typename T> ostream &operator<<(ostream &os, const vector<T> &v) { for (auto &e : v) os << e << " "; return os; }
template<typename T> inline int count_between(vector<T> &a, T l, T r) { return lower_bound(all(a), r) - lower_bound(all(a), l); } // [l, r)
inline int Log2(ll x) { int k; for (k = 0; x > 0; ++k) x >>= 1; return k; } // number of binary digits
const int INF  = 1<<30;
const ll INFll = 1ll<<62;
const ld EPS   = 1e-10;
const ld PI    = acos(-1.0);
const int MOD  = int(1e9)+7;
// const int MOD  = 998244353;

int cDiv(int x, int y) { return y == 0 ? INF : (x+y-1)/y; }


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

  V ans(m+2);
  rep(i, n) {
    int l, r; cin >> l >> r;
    int d = 1;
    while (d <= l) {
      int a = cDiv(l, d);
      int x = r/a+1;
      if (a > 1) chmin(x, cDiv(l, a-1));
      ++ans[d];
      --ans[x];
      d = cDiv(l, a-1);
    }
  }

  rep(i, m) ans[i+1] += ans[i];
  rep(i, m) cout << ans[i+1] << '\n';
  return 0;
}


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

int main() {
    long long  x;
    cin >> x;
    long long  money = 100;
    int year;
    for(int i = 1; ; i++){
        money += money / 100;
        if(money >= x){
            year = i;
            break;
        }
    }
    cout << year;
}

Measured memory_bytes: 3636
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
#define REP(i, a, b) for(int i = a, i##_len = (b); i < i##_len; ++i)

int main()
{
    string S;
    cin >> S;
    ll res = 0;
    REP(status, 0, 1<<(S.size()-1)){
        //左から数えていく
        ll sm = 0;
        ll cur = 0;
        REP(i, 0, S.size()) {
            cur *= 10;
            cur += S[i] - '0';
            if(status & 1 << i) { 
                sm += cur; cur = 0;
            }
        }
        res += sm + cur;
    }
    cout << res << endl;
    return 0;
}

Measured memory_bytes: 256
#include <cstdlib>
#include <iostream>
#include <vector>
#include <string>

using namespace std;

void Parse(vector<int>& stack, const string& s) {
  if (s == "+") {
    const int a = stack.back();
    stack.pop_back();
    const int b = stack.back();
    stack.pop_back();
    stack.push_back(a + b);
  } else if (s == "-") {
    const int a = stack.back();
    stack.pop_back();
    const int b = stack.back();
    stack.pop_back();
    stack.push_back(b - a); // N.B.
  } else if (s == "*") {
    const int a = stack.back();
    stack.pop_back();
    const int b = stack.back();
    stack.pop_back();
    stack.push_back(a * b);
  } else {
    stack.push_back(atoi(s.c_str()));
  }
}

int main() {
  string line;
  getline(cin, line);
  vector<int> stack;

  size_t begin = 0;
  for (;;) {
    const size_t end = line.find_first_of(" ", begin);
    if (end == string::npos) {
      Parse(stack, line.substr(begin));
      break;
    }
    Parse(stack, line.substr(begin, end-begin));
    begin = end + 1;
  }
  cout << stack.back() << endl;
  return 0;
}

Measured memory_bytes: 1220
###############################################################################

from sys import stdout
from bisect import bisect_left as binl
from copy import copy, deepcopy


mod = 1


def intin():
    input_tuple = input().split()
    if len(input_tuple) <= 1:
        return int(input_tuple[0])
    return tuple(map(int, input_tuple))


def intina():
    return [int(i) for i in input().split()]


def intinl(count):
    return [intin() for _ in range(count)]


def modadd(x, y):
    global mod
    return (x + y) % mod


def modmlt(x, y):
    global mod
    return (x * y) % mod


def lcm(x, y):
    while y != 0:
        z = x % y
        x = y
        y = z
    return x


def combination(x, y):
    assert(x >= y)

    if y > x // 2:
        y = x - y

    ret = 1

    for i in range(0, y):
        j = x - i
        i = i + 1

        ret = ret * j
        ret = ret // i

    return ret


def get_divisors(x):
    retlist = []
    for i in range(1, int(x**0.5) + 3):
        if x % i == 0:
            retlist.append(i)
            retlist.append(x // i)
    return retlist


def get_factors(x):
    retlist = []
    for i in range(2, int(x**0.5) + 3):
        while x % i == 0:
            retlist.append(i)
            x = x // i
    retlist.append(x)
    return retlist


def make_linklist(xylist):
    linklist = {}
    for a, b in xylist:
        linklist.setdefault(a, [])
        linklist.setdefault(b, [])
        linklist[a].append(b)
        linklist[b].append(a)
    return linklist


def calc_longest_distance(linklist, v=1):
    distance_list = {}
    distance_count = 0
    distance = 0
    vlist_previous = []
    vlist = [v]
    nodecount = len(linklist)

    while distance_count < nodecount:
        vlist_next = []
        for v in vlist:
            distance_list[v] = distance
            distance_count += 1
            vlist_next.extend(linklist[v])
        distance += 1
        vlist_to_del = vlist_previous
        vlist_previous = vlist
        vlist = list(set(vlist_next) - set(vlist_to_del))

    max_distance = -1
    max_v = None
    for v, distance in distance_list.items():
        if distance > max_distance:
            max_distance = distance
            max_v = v

    return (max_distance, max_v)


def calc_tree_diameter(linklist, v=1):
    _, u = calc_longest_distance(linklist, v)
    distance, _ = calc_longest_distance(linklist, u)
    return distance


###############################################################################


def main():
    n, k = intin()

    ans = (n // k) ** 3

    if k & 1:
        print(ans)
        return

    ans += ((n + k // 2) // k) ** 3
    print(ans)


if __name__ == '__main__':
    main()


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

using namespace std;


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

    long long n, k;
    cin >> n >> k;
    long long x[n];
    long long zero_i = -1;
    for (long long i = 0; i < n; ++i) {
        cin >> x[i];
        if (zero_i < 0 and x[i] >= 0) zero_i = i;
    }
    // long long start_i; // = max(0, zero_i - k);
    // start_i = 0 < zero_i - k? zero_i - k : 0;
    // long long end_i = min(zero_i + k - 1, n - 1);

    long long res = 3 * pow(10, 8) + 1;
    // for (long long i = start_i; i <= end_i - k + 1; ++i) {
    for (long long i = 0; i <= n - k; ++i) {
        long long st = i;
        long long ed = i + k - 1;
        long long left_ds = abs(x[st]);
        long long right_ds = abs(x[ed]);
        if (x[st] * x[ed] >= 0) {
            res = min(res, max(left_ds, right_ds));
        } else {
            res = min(res, left_ds + right_ds + min(left_ds, right_ds));
        }
    }

    cout << res << '\n';

    return 0;
}


Measured memory_bytes: 1024
#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;
int main(){
  int N;
  cin>>N;
  map<string,int>memo;
  rep(i,N) {
    string s;
    cin >> s;
    memo[s]++;
  }
  int vmax=0;
  for(auto p:memo){
    auto v=p.second;
    vmax=max(vmax,v);
  }
  for(auto it=memo.begin();it!=memo.end();it++){
    if(it->second==vmax){
      cout<<it->first<<endl;
    }
  }
  
}
  



Measured memory_bytes: 25216
#include <bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<(b);++i)
#define erep(i,a,b) for(int i=a;i<=(int)(b);++i)
#define per(i,a,b) for(int i=(b);i>(a);--i)
#define eper(i,a,b) for(int i=((int)(a));i>=b;--i)
#define pb push_back
#define mp make_pair
#define INF (1<<28)-1
#define MOD 1000000007
#define all(x) (x).begin(),(x).end()
using namespace std;
typedef long long ll;
typedef pair<int,int> Pii;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a = b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a = b; return 1; } return 0; }
int dy[]={0, 0, 1, -1};
int dx[]={1, -1, 0, 0};
int gcd(int a,int b){return b?gcd(b,a%b):a;}
int lcm(int a,int b){return a/gcd(a, b)*b;}

int h, w, n, sx, sy, d[1005][1005];
char g[1005][1005];

int bfs(int x, int y, int cnt) {
    queue<Pii> que;
    que.push(mp(x, y));
    rep(i, 0, h) rep(j, 0, w) d[i][j] = INF;
    d[x][y] = 0;
    int gx, gy;
    while (!que.empty()) {
        Pii p = que.front(); que.pop();
        if (g[p.first][p.second] == (char)('0'+cnt)) {
            gx = sx = p.first, gy = sy = p.second;
            break;
        }
        rep(i, 0, 4) {
            int nx = p.first + dx[i], ny = p.second + dy[i];
            if (0 <= nx && nx < h && 0 <= ny && ny < w && g[nx][ny] != 'X' && d[nx][ny] == INF) {
                que.push(mp(nx, ny));
                d[nx][ny] = d[p.first][p.second] + 1;
            }
        }
    }
    return d[gx][gy];
}

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
    cin >> h >> w >> n;
    rep(i, 0, h) rep(j, 0, w) {
        cin >> g[i][j];
        if (g[i][j] == 'S') sx = i, sy = j;
    }
    int ans = 0;
    rep(i, 0, n) {
        ans += bfs(sx, sy, i+1);
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 7976
// inputに入力データ全体が入る
function Main(input) {
	var input = input.split("\n");
	var N = Number(input[0]);
	var strobj = {};
	for(var i = 1; i < N+1; i++){
		if(!strobj[input[i]]) strobj[input[i]] = 0;
		strobj[input[i]]++; 
	}
	var M = Number(input[N+1]);
	for(var j = 1; j < M+1; j++){
		if(!strobj[input[N+j+1]]) strobj[input[N+j+1]] = 0;
		strobj[input[N+j+1]]--;
	}

	var max = 0;;
	for(var key in strobj){
		if(strobj[key] > max) max = strobj[key];
	}
	console.log(max);
}

//*この行以降は編集しないでください（標準入出力から一度に読み込み、Mainを呼び出します）
Main(require("fs").readFileSync("/dev/stdin", "utf8"));

Measured memory_bytes: 21064
#include<bits/stdc++.h>
#define maxn 120
#define maxv 120000
using namespace std;
typedef long long LL;
LL w[maxn], v[maxn];
LL f[maxn][maxv];
int main(){
	ios::sync_with_stdio(false);
	int N, W;
	cin >> N >> W;
	for(int i = 1; i <= N; i += 1) cin >> w[i] >> v[i];
	fill(f[0] + 1, f[0] + maxv, W + 1);
	for(int i = 1; i <= N; i += 1)
		for(int j = 1; j < maxv; j += 1){
				f[i][j] = j >= v[i] ? f[i][j] = min(f[i - 1][j], f[i - 1][j - v[i]] + w[i]) : f[i - 1][j];
		}
	for(int i = maxv - 1; i >= 0; i -= 1) if(f[N][i] <= W){
		cout << i;
		return 0;
	}
} 

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

#define pb push_back

#define ll long long

#define ft first

#define sd second

using namespace std;

const int N = 5050 ;

bool used[N];

ll z , r , w ;

int main(){

    int n , m ;
    cin >> n >> m ;
    int k = n / m ;
    if( k * m >= n ){
        cout<<k<<endl;
    }
    else{
        cout<<k+1<<endl;
    }

}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define REP(i,a,N) for(int i=a;i<N;i++)
using namespace std;
int main() {
	int sx,sy,tx,ty;
/*	queue<int> qx,qy;
	int dx[4]={0,0,-1,1};
	int dy[4]={1,-1,0,0};
	int frag[4000001]={0};
*/
	cin>>sx>>sy>>tx>>ty;
	REP(i,sy,ty){
		printf("U");
	}
	REP(i,sx,tx){
		printf("R");
	}
	REP(i,sy,ty){
		printf("D");
	}
	REP(i,sx,tx){
		printf("L");
	}
	printf("D");
	REP(i,sx,tx+1){
		printf("R");
	}
	REP(i,sy,ty+1){
		printf("U");
	}
	printf("LU");
	REP(i,sx,tx+1){
		printf("L");
	}
	REP(i,sy,ty+1){
		printf("D");
	}
	printf("R");
	
	
	return 0;
}

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

int main(){
	string s ; cin >> s ;
	int cnt = s.size() ;
	int sub = 0 ;
	vector<char> c ;
	for(int i=0;i<cnt;i++){
		if(s.at(cnt-1-i)=='B') sub++ ;
		else{
			if(sub==0) c.push_back(s.at(cnt-1-i)) ;
			else sub-- ;
		}
	}
	reverse(c.begin(),c.end()) ;
	for(int i=0;i<c.size();i++) cout << c.at(i) ;
	cout << endl ;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int gcd (int a,int b){
    if(a==0)
        return b;
    else if (b==0)
        return a;
    else if (a==b)
        return a;
    else if (a > b)
        return gcd (a-b,b);
    else
        return gcd (a,b-a);
}
int main(){
    long long int n,sum=0,call=0;
    cin>>n;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            for(int k=1;k<=n;k++)
                sum+=gcd(i,gcd(j,k));
    cout<<sum;
        return 0;
}

Measured memory_bytes: 3620
import std.stdio;
import std.ascii;
import std.c.stdio;
import std.range;
import std.array;
import std.functional;
import std.algorithm;
import std.conv;
import std.container;
import std.math;
import std.numeric;
import std.string;
import std.c.string;
import std.regex;
import std.typecons;

void main() {
    string s;
    char[] E;
    bool input() {
        s = readln.chomp;
        E = new char[s.length];
        return s != "#";
    }
    bool[26] used;
    bool Check(in char[] R) { // R: Raw
        memset(cast(void*)used, 0, used.sizeof);
        foreach (i, r; R) {
            if (r == 'a' || used[ r - 'a' ]) {
                E[i] = r;
            } else {
                E[i] = cast(char)(r - 1);
                used[ r - 'a' ] = true;
            }
        }
        return E[0 .. R.length] == s[0 .. R.length];
    }
    void solve() {
        string[] rs;
        char[] P = new char[s.length];
        void dfs(int index) {
            if (index == s.length) {
                if (!Check(P)) return;
                rs ~= cast(string)(P.dup);
                return;
            }
            if (!Check(P[0 .. index])) return;
            char a = s[index],
                 b = cast(char)(s[index] + 1);
            if (a == 'z') {
                P[index] = 'z';
                dfs(index + 1);
            } else {
                P[index] = a;
                dfs(index + 1);
                P[index] = b;
                dfs(index + 1);
            }
        }
        dfs(0);
        writeln(rs.length);
        if (rs.empty) return;
        if (rs.length < 10) {
            writeln(rs.join("\n"));
        } else {
            writeln(rs[0 .. 5].join("\n"));
            writeln(rs[$ - 5 .. $].join("\n"));
        }
    }
    while (input) solve;
}

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

template<typename F>
class FixPoint : private F {
public:
  explicit constexpr FixPoint(F&& f) noexcept : F(forward<F>(f)) {}

  template<typename... Args>
  constexpr decltype(auto) operator()(Args&&... args) const {
    return F::operator()(*this, forward<Args>(args)...);
  }
};

template<typename F>
static inline constexpr decltype(auto) fix(F&& f) noexcept {
  return FixPoint<F>{forward<F>(f)};
}


int main(int argc, char *argv[]) {
  // C-style stdio functions should not be used.
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  cout << setprecision(20);

  int N; cin >> N;
  vector<vector<int>> nbr(N);
  unordered_map<int, unordered_map<int, int>> mp;
  for (int i = 0; i < N-1; i++) {
    int a, b; cin >> a >> b; a--; b--;
    nbr.at(a).push_back(b);
    nbr.at(b).push_back(a);
    mp[a][b] = i;
  }
  int K = 0;
  for (int i = 0; i < N; i++) K = max(K, (int)nbr.at(i).size());
  
  vector<int> colors(N-1);

  auto func = fix([&](auto recF, int n, int p, int c) -> void {
      int nc = 0;
      for (int x : nbr.at(n)) {
	if (x == p) continue;
	if (nc == c) nc++;
	int m1 = min(x, n);
	int m2 = max(x, n);
	colors.at(mp.at(m1).at(m2)) = nc;
	recF(x, n, nc);
	nc++;
      }
    });
  
  func(0, -1, -1);

  cout << K << "\n";
  for (int i = 0; i < N-1; i++) cout << 1 + colors.at(i) << "\n";

  return 0;
}



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

int main() {
    ll n,m;
    cin >>n>>m;
    vector<ll> a(n);
    for(ll i=0;i<n;i++) cin>>a[i];
    sort(a.begin(),a.end());
    vector<pair<ll,ll>> d(m);
    for(ll i=0;i<m;i++) {
        ll b,c;
        cin>>b>>c;
        d[i] = make_pair(c,b);
    }
    sort(d.begin(),d.end(),greater<pair<ll,ll>>());
    ll p=0;
    for(ll i=0;i<n;i++) {
        if(p>m-1)break;
        if(a[i] < d[p].first) {
            for(ll j=0;j<d[p].second;j++) {
                if(i+j>n-1) {
                    p++;
                    break;
                }
                if(a[i+j] < d[p].first) {
                    a[i+j] = d[p].first;
                }else {
                    p++;
                    break;
                }
            }
            p++;
        }
    }
    ll sum=0;
    for(ll i=0;i<n;i++) {
        sum+=a[i];
    }
    cout<<sum<<endl;
}


Measured memory_bytes: 2560
#include<cstdio>
using namespace std;
int f[4][4];
int main()
{
	int a,b,c;
	scanf("%d%d%d",&f[1][1],&f[1][2],&f[2][2]);
	a=f[2][2]*3;
	f[1][3]=a-f[1][1]-f[1][2];
	f[3][1]=a-f[1][3]-f[2][2];
	f[3][3]=a-f[1][1]-f[2][2];
	f[2][1]=a-f[1][1]-f[3][1];
	f[2][3]=a-f[2][1]-f[2][2];
	f[3][2]=a-f[1][2]-f[2][2];
	for(int i=1;i<=3;i++)
	{
		for(int j=1;j<=3;j++)
		{
			printf("%d ",f[i][j]);
		}
		printf("\n");
	}
	return 0;
}

Measured memory_bytes: 128
N, K, Q = map(int, input().split())
score = {str(i): 0 for i in range(1, N+1)}
for _ in range(Q):
  answerer = input()
  score[answerer] += 1

for k, v in sorted(score.items(), key=lambda x:int(x[0])):
  if K - (Q - v) > 0:
    print("Yes")
  else:
    print("No")

Measured memory_bytes: 26596
import java.util.ArrayList;
import java.util.Scanner;

class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		// 入力値を取得
		int a = sc.nextInt();
		int b = sc.nextInt();
		String aStr = String.valueOf(a);
		String bStr = String.valueOf(b);
		String abStr = aStr + bStr;
		int ab = Integer.parseInt(abStr);
		boolean squareFlag = false;
		// 約数を求める
		ArrayList <Integer> divList = new ArrayList<Integer>();
		for(int i = 1; i <= ab ; i++){
			if(ab%i == 0 && ab/i == i){
				squareFlag = true;
			}
		}
		if(squareFlag){
			System.out.println("Yes");
		}else{
			System.out.println("No");
		}
	}
}

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

vector<int> v, t;
int n;

int main() {
#ifdef HOME
	freopen("arc95c.in", "r", stdin);
	freopen("arc95c.out", "w", stdout);
#endif
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);


	cin >> n;
	v.resize(n);
	for (auto &i: v)
		cin >> i;

	t = v;
	sort(begin(t), end(t));

	for (int i = 0; i < n; ++i) {
		if (v[i] < t[n / 2])
			cout << t[n / 2] << '\n';
		else
			cout << t[n / 2 - 1] << '\n'; }

	return 0; }



Measured memory_bytes: 3840
# C - Traveling Salesman around Lake
# https://atcoder.jp/contests/abc160/tasks/abc160_c

# 各家において、時計回りか反時計回りのどちらで移動した方が良いかチェックする。

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

result = A[0] - A[N - 1] + K
for i in range(N - 1):
    result = max(result, A[i + 1] - A[i])
print(K - result)



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

#define GO ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define int long long int

const int maxr = 1e5 + 5;


int32_t main()
{
	GO;
	int a, b, n;
	cin >> a >> b >> n;
	int ans = 0;
	int val = (b / n) * n;
	int i = val - 1;
	if (i >= 0 && i <= n)
		ans = max(ans, (a * i) / b - a * (i / b));
	i = (n / b) * b;
	i --;
	if (i >= 0 && i <= n)
		ans = max(ans, (a * i) / b - a * (i / b));
	i = n;
	ans = max(ans, (a * i) / b - a * (i / b));
	cout << ans << endl;
	return 0;
}

//!

Measured memory_bytes: 3648
import itertools
import numpy as np
n,m,x = map(int,input().split())
a = [list(map(int, input().split())) for i in range(n)]
#print(a)
bit = (list(itertools.product([0,1], repeat=n)))
#print(bit)
d=[]
for i in range(len(bit)):
    kounyuu = []
    nedan=[]
    for j in range(n):
        if bit[i][j]==1:
            kounyuu.append(a[j])
            #print(kounyuu)
            c=[]
            for k in range(1,m+1):
                b = []
                for z in range(len(kounyuu)):
                    b.append(kounyuu[z][k])
                if(sum(b))>=x:
                    c.append(sum(b))
            if len(c)==m:
                for z in range(len(kounyuu)):
                    nedan.append(kounyuu[z][0])
                d.append(sum(nedan))
if d == []:
    print(-1)
else:
    print(min(d))

Measured memory_bytes: 28076
import sys
readline = sys.stdin.readline

N, M = map(int, readline().split())
Edge = [[] for _ in range(N)]
for _ in range(M):
    s, t = map(int, readline().split())
    s -= 1
    t -= 1
    Edge[s].append(t)

E = [0]*N
for i in range(N-2, -1, -1):
    res = 0
    for j in Edge[i]:
        res += E[j]
    E[i] = 1 + res/len(Edge[i])

p = [0]*N
p[0] = 1
for i in range(N):
    pi = p[i]
    cnt = len(Edge[i])
    for j in Edge[i]:
        p[j] += pi/cnt

ans = E[0]
for i in range(N):
    if len(Edge[i]) <= 1:
        continue
    mj = max(Edge[i], key = lambda x: E[x])
    
    res = 0
    for j in Edge[i]:
        if mj != j:
            res += E[j]
    ans = min(ans, E[0] + p[i]*(1+res/(len(Edge[i])-1)-E[i]))
print(ans)    

Measured memory_bytes: 52756
#include <bits/stdc++.h>
#define MOD 1000000007
#define INF 1001001001
#define LINF 1001001001001001001
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define bit(n) (1LL<<(n))
using namespace std;

typedef long long ll;
typedef pair<int, int> P;
typedef pair<ll, ll> LLP;

int H, W;

int getPos(int i, int j) {
  return i * H + j;
}

bool check(int i, int j) {
  return i >= 0 && i < H && j >= 0 && j < W;
}

int main() {
  
  cin >> H >> W;
  P C, D;
  cin >> C.first >> C.second >> D.first >> D.second;
  C.first--; C.second--; D.first--; D.second--;
  vector<string> S(H);
  rep(i,H) cin >> S[i];

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

  vector maze(H, vector<int>(W, INF));

  queue<P> next_que, que;
  next_que.emplace(C.first, C.second);
  int now = 0;

  while (!next_que.empty()) {
    while (!next_que.empty()) {
      que.push(next_que.front()); next_que.pop();
    }
    while (!que.empty()) {
      P p = que.front(); que.pop();
      if (maze[p.first][p.second] <= now) continue;
      maze[p.first][p.second] = now;
      rep(i,4) {
        if (check(p.first + dy[i], p.second + dx[i]) && S[p.first + dy[i]][p.second + dx[i]] == '.' && maze[p.first + dy[i]][p.second + dx[i]] > now) {
          que.emplace(p.first + dy[i], p.second + dx[i]);
        }
      }
      for (int i = -2; i <= 2; i++) for (int j = -2; j <= 2; j++) {
        if (check(p.first + i, p.second + j) && S[p.first + i][p.second + j] == '.' && maze[p.first + i][p.second + j] == INF) {
          next_que.emplace(p.first + i, p.second + j);
        }
      }
    }
    now++;
  }

  if (maze[D.first][D.second] == INF) cout << -1 << endl;
  else cout << maze[D.first][D.second] << endl;

  return 0;
}

Measured memory_bytes: 9816
#include <iostream>
#include <string>
#include <map>
#include <queue>
#include <math.h>
#include <bitset>
#include <cmath>
#include <set>
#include <queue>
#include <stack>
#include <algorithm>
#include <vector>
#include <random>
using namespace std;
typedef long long ll;
#define repe(i,s,n)for(ll i = s;i<=n;i++)
#define rep_r(i,s,n)for(ll i = n-1;i>s;i--)
#define rep_re(i,s,n)for(ll i = n-1;i>=s;i--)
ll MOD = 1e9 + 7;

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

typedef long long ll;
#define rep_re(i,s,n)for(ll i = n-1;i>=s;i--)
#define rep(i,s,n)for(ll i = s;i<n;i++)



ll A[200001] = {};
ll a[200001] = {};
ll b[200001] = {};
int main()
{
    ll n; cin >> n;
    repe(i, 1, n) {
        cin >> A[i];
        a[A[i]]++;
    }

    ll sum = 0;
    repe(i, 1, n) {
        if (a[i] >= 2) {
            b[i] = a[i] * (a[i]-1)/ 2;
            sum += b[i];
        }
    }

    repe(i, 1, n) {
        ll ans = sum;
        ans -= b[A[i]];

        if (a[A[i]] - 1 >= 2) {
            ans += (a[A[i]] - 1) * (a[A[i]] - 2) / 2;
        }

        cout << ans << endl;
    }

    return 0;
}

//Solution* sol = new Solution();
//vector<int> v1 = { 1,2,3,4 };
//vector<vector<int>> v;
//vector<int> p = { 1,0 };
// Solution* sol = new Solution();


Measured memory_bytes: 6272
/*
    Author : Nishant Gupta 2.0
*/
#include<bits/stdc++.h>

#define LL long long int
#define getcx getchar_unlocked
#define X first
#define Y second
#define PB push_back
#define MP make_pair
#define MAX 4005
#define MOD 1000000007
#define INF 0x3f3f3f3f
#define INFL (LL(1e18))
#define chk(a) cerr << endl << #a << " : " << a << endl
#define chk2(a,b) cerr << endl << #a << " : " << a << "\t" << #b << " : " << b << endl
#define chk3(a,b,c) cerr << endl << #a << " : " << a << "\t" << #b << " : " << b << "\t" << #c << " : " << c << endl
#define chk4(a,b,c,d) cerr << endl << #a << " : " << a << "\t" << #b << " : " << b << "\t" << #c << " : " << c << "\t" << #d << " : " << d << endl
#define rep(i, a, n) for(i=a;i<n;i++)
#define rev(i, a, n) for(i=a;i>=n;i--)
#define MSV(A,a) memset(A, a, sizeof(A))
#define rep_itr(itr, c) for(itr = (c).begin(); itr != (c).end(); itr++)

using namespace std;

inline void inp( int &n ) { 
	n=0;    int ch=getcx();int sign=1;   
	while( ch < '0' || ch > '9' ){if(ch=='-')sign=-1; ch=getcx();} 
	while(  ch >= '0' && ch <= '9' )    
	n = (n<<3)+(n<<1) + ch-'0', ch=getcx();
	n=n*sign;
}

inline void inp1( LL &n ) { 
	n=0;    LL ch=getcx();LL sign=1;   
	while( ch < '0' || ch > '9' ){if(ch=='-')sign=-1; ch=getcx();} 
	while(  ch >= '0' && ch <= '9' )    
	n = (n<<3)+(n<<1) + ch-'0', ch=getcx();
	n=n*sign;
}

int main() {
	
	LL lr[MAX]= {0}, lg[MAX] = {0}, lb[MAX] = {0};
	LL tr = 0, tg = 0, tb = 0;
	
	string s;
	int n;
	cin>>n;
	cin>>s;
	
	
	for(int i=0;i<s.length();i++) {
		if(s[i] == 'R') {
			lr[i] = 1;
			tr++;
		} else if(s[i] == 'G') {
			lg[i] = 1;
			tg++;
		} else {
			lb[i] = 1;
			tb++;
		}
	}

	for(int i=1;i<MAX;i++) {
		lr[i] += lr[i-1];
		lg[i] += lg[i-1];
		lb[i] += lb[i-1];
	}
	
	LL ans = 0;
	for(int i=1;i<n-1;i++) {
		for(int d=0;d<i;d++) {
			int diff = i-d;
			
			if(s[i] == s[d]) continue;
			
			if(s[i] == 'R') {
				if(s[d] == 'G') {
					ans += (tb - lb[i]);
					if(i+diff < n && s[i+diff] == 'B') ans--;
				}
				else if(s[d] == 'B') {
					ans += (tg - lg[i]);
					if(i+diff < n && s[i+diff] == 'G') ans--;
				}
			}
			
			if(s[i] == 'G') {
				if(s[d] == 'B') {
					ans += (tr - lr[i]);
					if(i+diff < n && s[i+diff] == 'R') ans--;
				}
				else if(s[d] == 'R') {
					ans += (tb - lb[i]);
					if(i+diff < n && s[i+diff] == 'B') ans--;
				}
			}
			
			if(s[i] == 'B') {
				if(s[d] == 'G') {
					ans += (tr - lr[i]);
					if(i+diff < n && s[i+diff] == 'R') ans--;
				}
				else if(s[d] == 'R') {
					ans += (tg - lg[i]);
					if(i+diff < n && s[i+diff] == 'G') ans--;
				}
			}
		}
	}
	
	cout<<ans<<endl;
    return 0;
}



Measured memory_bytes: 3712
#include "bits/stdc++.h"
using namespace std;
int main(){
  int N,x,Nd,a,b,c,ans=0;
  cin>>N;Nd=N;
  a=N/100;Nd-=a*100;
  b=Nd/10;Nd-=b*10;
  c=Nd;
  if(a>=b){
    if(a==b&&b<c){
      ans=(a+1)*100+(a+1)*10+(a+1);
    }else{
      ans=a*100+a*10+a;
    }
  }else{
    ans=(a+1)*100+(a+1)*10+(a+1);
  }
  cout<<ans<<endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
#define REP(i, a, b) for(int i = a, i##_len = (b); i < i##_len; ++i)

int main()
{
    int N, x;
    scanf("%d %d", &N, &x);
    int a[N];
    REP(i, 0, N) scanf("%d", &a[i]);
    int b[N];
    if(a[0] <= x) b[0] = a[0];
    else b[0] = x;
    REP(i, 1, N) {
        int sm = b[i-1] + a[i];
        if(sm > x) b[i] = a[i] - (sm - x);
        else b[i] = a[i];
    }
    ll res = 0;
    REP(i, 0, N) res += a[i] - b[i];
    printf("%lld\n", res);
    return 0;
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using pii  = pair<int,int>;
#define rep(i,n) for(ll i=0; i<(n); i++)
#define rep2(i,x,n) for(ll i=x; i<(n); i++)
#define MOD 1000000007
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; }
const long long INF = 1LL << 60;
const double PI = 3.141593;
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}    //最大公約数
ll lcm(ll a,ll b) {return a * b / gcd(a, b);}   //最小公倍数
ll combination(ll n, ll r) {
  if ( r * 2 > n ) r = n - r;
  ll dividend = 1;
  ll divisor  = 1;
  for ( ll i = 1; i <= r; ++i ) {
    dividend *= (n-i+1);
    divisor  *= i;
  }
  return dividend / divisor;
}

int main(){
  ll x, MIN, MAX;
  MAX = 105;
  MIN = 100;
  cin >> x;
  bool flag = false;
  for (int i = 1; i <= 1000000; i++)
  {
    if(MIN*i<=x&&x<=MAX*i)
      flag = true;
  }
  if(flag)
    cout << 1 << endl;
    else
    {
      cout << 0 << endl;
    }
}

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

class state{
public:
  string str;
  int n,year;
};

int main(){
  int n,m;
  while(cin >> n >> m && n && m){
    vector<state> v;
    for(int i=0;i<n;i++){
      state s;
      cin >> s.str >> s.n >> s.year;
      v.push_back(s);
    }
    for(int i=0;i<m;i++){
	int a;
	cin >> a;
	int j;
	for(j=0;j<n;j++){
	  if(v[j].year - v[j].n < a && a <= v[j].year){
	    cout << v[j].str << " " << v[j].n - (v[j].year - a) << endl;
	    break;
	  }
	}
	if(j == n) cout << "Unknown" << endl;
      }
	  }
    return 0;
  }

Measured memory_bytes: 972
use strict;
use warnings;
use utf8;

use Data::Dumper;
use feature qw(say);

my $n = <STDIN>;
chomp $n;

my $small_character_list = ['a'..'z'];
if (scalar grep { $_ eq $n } @$small_character_list) {
    say 'a';
} else {
    say 'A';
}

Measured memory_bytes: 6432