akhauriyash/Code-Regression huggingface dataset:
from collections import deque
def solve():
    H,W = map(int,input().split())
    Ch,Cw = map(lambda x:int(x)-1,input().split())
    Dh,Dw = map(lambda x:int(x)-1,input().split())
    A = [list(input()) for _ in range(H)]
    V = [[-1]*W for _ in range(H)]
    d = ((1,0),(0,1),(-1,0),(0,-1))

    def bfs_2d(sy,sx,v):
        que = deque()
        V[sy][sx] = v
        que.append((sy,sx))

        while que:
            uh, uw = que.popleft()
            for dy, dx in d:
                next_h = uh+dy
                next_w = uw+dx
                if 0 <= next_h < H and 0 <= next_w < W \
                    and A[next_h][next_w] == '.' \
                    and V[next_h][next_w] == -1:
                    V[next_h][next_w] = v
                    que.append((next_h,next_w))
    
    vertex = 0
    for h in range(H):
        for w in range(W):
            if A[h][w] == '#' or V[h][w] != -1:
                continue
            bfs_2d(h,w,vertex)
            vertex += 1

    G = [[] for _ in range(vertex)]
    used = [set() for _ in range(vertex)]
    for h in range(H):
        for w in range(W):
            if A[h][w] == '#':
                continue
            for dh in range(-2, 2+1):
                for dw in range(-2, 2+1):
                    if h + dh < 0 or H <= h + dh or w + dw < 0 or W <= w + dw:
                        continue
                    if A[h+dh][w+dw] == "#":
                        continue
                    if V[h][w] == V[h+dh][w+dw]:
                        continue
                    if V[h+dh][w+dw] in used[V[h][w]]:
                        continue
                    G[V[h][w]].append((V[h+dh][w+dw]))
                    used[V[h][w]].add((V[h+dh][w+dw]))
    
    s = V[Ch][Cw]
    g = V[Dh][Dw]

    dist = [-1 for _ in range(vertex)]
    que = deque()
    dist[s] = 0
    que.append(s)
    while que:
        u = que.popleft()
        for v in G[u]:
            if dist[v] != -1:
                continue
            dist[v] = dist[u] + 1
            que.append(v)
    
    print(dist[g])

if __name__ == '__main__':
    solve()


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

int main(){
    long long n,cnt[60];
    for(long long i = 0 ; i < 60 ; i += 1){
        cnt[i] = 0;
    }
    cin >> n;
    long long val1=0,val2=0,sum;
    for(long long i = 0 ; i < n ; i += 1){
        long long a;
        cin >> a;
        if(i == 0){
        	val1 = a;
        	continue;
        }else if(i == 1){
        	val2 = a;
        	continue;
        }
        long long tag=0;
        while(a){
            if(a % 2 == 1){
                cnt[tag] += 1;
            }
            a /= 2;
            tag += 1;
        }
    }
    sum = val1+val2;
    long long val3 = 0;
    for(long long i = 0 ; i < 60 ; i += 1){
    	if(cnt[i] % 2 == 1){
    		val3 += (1ll<<i);
    	}
    }
    if(val3 > sum){
    	cout << -1 << endl;
    	return 0;
    }
    if((sum-val3)%2 == 1){
    	cout << -1 << endl;
    	return 0;
    }
    long long val4 = (sum-val3)/2;
    if(val4 & val3){
    	cout << -1 << endl;
    	return 0;
    }
    long long ans = val4;
    for(long long i = 59 ; i >= 0 ; i -= 1){
    	if(ans + (1ll << i) < val1 && (val3 & (1ll<<i))){
    		ans += (1ll<<i);
    	}
    }
    if(ans == 0 || ans > val1){
    	cout << -1 << endl;
    	return 0;
    }
    cout << val1-ans << endl;
}

Measured memory_bytes: 3584
#include<bits/stdc++.h>
using namespace std;
int a,b,i,j;
void task(int x) {
	for(i=2; i<a; i++) {
		for(j=i+1; j<=a; j++) {
			if(!x)return;
			cout<<i<<" "<<j<<endl,x--;
		}
	}
}
int main() {
	cin>>a>>b;
	if(b>(a-1)*(a-2)/2)cout<<-1;
	else {
		cout<<a-1+(a-1)*(a-2)/2-b<<endl;
		for(i=2; i<=a; i++)cout<<1<<" "<<i<<endl;
		task((a-1)*(a-2)/2-b);
	}
	return 0;
}


Measured memory_bytes: 256
#include<stdio.h>

int gcd(long long a, long long b)
{
	if (b == 0)
		return a;
	return gcd(b, a%b);
}

int main()
{
	long long a, b,g,l;
	while (scanf("%lld%lld", &a, &b) != EOF)
	{
		g = gcd(a, b);
		l = b / g * a;
		printf("%lld %lld\n", g, l);
	}
	return 0;
}



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

class UnionFind {
    vector<int> data;
    ll num;
public:
    UnionFind(int size) : data(size, -1), num(size) { }
    bool unite(int x, int y) {//xとyの集合を統合する
        x = root(x); y = root(y);
        if (x != y) {
            if (data[y] < data[x]) swap(x, y);
            data[x] += data[y]; data[y] = x;
        }
        num -= (x != y);
        return x != y;
    }
    bool findSet(int x, int y) {//xとyが同じ集合か返す
        return root(x) == root(y);
    }
    int root(int x) {//xのルートを返す
        return data[x] < 0 ? x : data[x] = root(data[x]);
    }
    ll size(int x) {//xの集合のサイズを返す
        return -data[root(x)];
    }
    ll numSet() {//集合の数を返す
        return num;
    }
};


int main(){
  int n,m;
  cin>>n>>m;
  UnionFind uf(n);
  rep(i,m){
    int a,b;
    cin>>a>>b;
    a--;b--;
    uf.unite(a,b);
  }
  ll ans=0;
  rep(i,n) ans=max(ans,uf.size(i));
  cout<<ans<<endl;

}

Measured memory_bytes: 4048
#include<bits/stdc++.h>
#define INF 2000000000
#define MOD 1000000007
#define EPS (1e-10)

using namespace std;

int main(int argc, char *argv[]) {

	int S,W; cin >> S >> W;

	if (W >= S) {
		cout << "unsafe" << endl;
	}else {
		cout << "safe" << endl;
	}
	
	return 0;
}


Measured memory_bytes: 3636
d, g = io.read("*n", "*n")
g = g / 100
psum = 0
p, c = {}, {}
for i = 1, d do
  p[i], c[i] = io.read("*n", "*n")
  c[i], psum = c[i] / 100, psum + p[i]
end
t = {}
currentmax = 0
ignoremax = psum + 1
for i = 0, psum do t[i] = 0 end

for i_d = 1, d do
  searchmax = currentmax + p[i_d]
  for summed_count = searchmax, 0, -1 do
    i_count_min = math.max(0, summed_count - currentmax)
    i_count_max = math.min(summed_count, p[i_d])
    for i_count = i_count_min, i_count_max do
      i_score = i_count * i_d
      if(i_count == p[i_d]) then i_score = i_score + c[i_d] end
      t[summed_count] = math.max(t[summed_count], t[summed_count - i_count] + i_score)
    end
  end
  currentmax = searchmax
end
for i = 1, psum do
  if(g <= t[i]) then print(i) break end
end


Measured memory_bytes: 256
fun main (args:Array<String>){
    val N = readLine()!!.toInt()
    val d = readLine()!!.split(" ").map(String::toInt)

    var sum = 0
    for (i in 0..N-2) {
        for (j in i + 1..N-1) {
            sum += d[i] * d[j]
        }
    }
    println(sum)
}


Measured memory_bytes: 36568
import java.util.*;

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

		long ans = 0;
		for(int i=1; i<=N; i++) {
			for(int j=1; j<=N; j++) {
				long gcdAB = gcd(i, j);
				for(int k=1; k<=N; k++) {
					ans += gcd(gcdAB, k);
				}
			}
		}

		System.out.println(ans);
		sc.close();
	}
	
	static long gcd(long a, long b) {
		return b==0 ? a : gcd(b, a%b);
	}
}


Measured memory_bytes: 27264
#include<iostream>
#include<vector>
#include<algorithm>
#include<cstdio>

using namespace std;

int main(){
  const int MAX = 2 * 123456 + 10;
  vector<bool> isPrime( MAX, true );
  isPrime[0] = isPrime[1] = false;

  for(int i = 4; i < MAX; i += 2)
    isPrime[i] = false;

  for(int i = 3; i * i < MAX; i += 2)
    if(isPrime[i])
      for(int j = i + i; j < MAX; j += i)
        isPrime[j] = false;

  int n;

  while(scanf("%d", &n), n)
    printf("%d\n", count(isPrime.begin() + n + 1, isPrime.begin() + 2 * n + 1, true));

  return 0;
}

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

#define lli long long int
#define REP(i,s,n) for(int i=s;i<n;i++)
#define MOD 1000000007
#define NUM 2520
#define INF (1LL<<50)
#define DEBUG 0
#define mp(a,b) make_pair(a,b)
#define SORT(V) sort(V.begin(),V.end())
#define PI (3.141592653589794)
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; }

//dp[i][j],i前の日にしたもの,j:index
lli dp[101000];

int main(){

	lli N,W;
	cin>>N>>W;
	REP(i,0,101000)dp[i]=INF;
	dp[0]=0;

	REP(i,0,N){
		lli w,v;
		cin>>w>>v;
		for(lli j=100999;j>=0;j--){
			if(j+v>100999)continue;
			chmin(dp[j+v],dp[j]+w);
		}
	}
	lli maxV=0;
	for(lli i=100999;i>=0;i--){
		if(dp[i]<=W){
			cout<<i<<endl;
			return 0;
		}
	}
	

    return 0;
}


Measured memory_bytes: 1024
#include <stdio.h>

int main(void) {
	int W,H,x,y,r,i;
	scanf("%d%d%d%d%d",&W,&H,&x,&y,&r);
	i=0;
	if(H<(y+r))i=1;
	if(W<(x+r))i=1;
	if(0>(y-r))i=1;
	if(0>(x-r))i=1;
	if(i==0){
		printf("Yes\n");
	}else{
		printf("No\n");
	}
	return 0;
}



Measured memory_bytes: 2644
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <cmath>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <bitset>
#include <iomanip>
#include <climits>
using namespace std;
typedef long long ll;
typedef vector<int> VI;
typedef vector<ll> VL;
typedef vector<string> VS;
typedef vector< vector<int> > VVI;
typedef vector< vector<ll> > VVL;
typedef pair<int,int> PII;
typedef pair<ll,ll> PLL;
#define rep(i,n) for(ll i=0;i<(n);i++)
#define all(a) (a).begin(),(a).end()
#define pf push_front
#define pb push_back
#define mp make_pair
#define mt make_tuple
#define ub upper_bound
#define lb lower_bound

int main(){
  int N;
  cin>>N;
  VI A(3*N);
  rep(i,3*N) cin>>A[i];
  priority_queue< int,VI,greater<int> > L;
  priority_queue<int> R;
  rep(i,N) L.push(A[i]);
  rep(i,N) R.push(A[3*N-1-i]);
  VL B(N+1),C(N+1);
  rep(i,N) B[0]+=A[i];
  rep(i,N) C[0]+=A[3*N-1-i];
  rep(i,N){
    L.push(A[N+i]);
    B[i+1]=B[i]+A[N+i]-L.top();
    L.pop();
  }
  rep(i,N){
    R.push(A[2*N-1-i]);
    C[i+1]=C[i]+A[2*N-1-i]-R.top();
    R.pop();
  }
  ll ans=-1001001001001001001;
  rep(i,N+1) ans=max(ans,B[i]-C[N-i]);
  cout<<ans<<endl;
}

Measured memory_bytes: 3960
#include <bits/stdc++.h>
using namespace std;
#define SELECTER(_1, _2, _3, SELECT, ...) SELECT
#define REP1(i, n) for(int i=0; (i)<(n); (i)++)
#define REP2(i, a, b) for(int i=(a); (i)<(b); (i)++)
#define REP(...) SELECTER(__VA_ARGS__, REP2, REP1,) (__VA_ARGS__)

template <class T> ostream& operator<<(ostream& os, const vector<T>& v){ os << "{"; for(size_t i=0; i<v.size(); i++) os << v[i] << (i+1==v.size() ? "" : ", "); os << "}"; return os; }
template <class T, class U> ostream& operator<<(ostream& os, const pair<T, U>& p){ return os << "{" << p.first << ", " << p.second << "}"; }


int main(){
    int L;
    cin >> L;
    vector<int> A(L);
    REP(i, L) cin >> A[i];

    vector<vector<long long>> dp(L+1, vector<long long>(5, 1LL<<30));
    REP(i, 5) dp[0][i] = 0;
    for(int i=0; i<L; i++){
        for(int j=0; j<5; j++){
            if(dp[i][j] == 1LL<<30) continue;
            long long pena = 0;
            if(j==0||j==4) pena = A[i];
            if(j==1||j==3){
                if(A[i]==0) pena = 2;
                else pena = A[i]%2;
            }
            if(j==2) pena = (A[i]+1)%2;
            for(int k=j; k<5; k++){
                dp[i+1][k] = min(dp[i+1][k], dp[i][j] + pena);
            }
        }
    }
    cout << dp[L][4] << endl;
    return 0;
}

Measured memory_bytes: 18032
S = input()
K = int(input())
str_set = set()
for i in range(1, 6):
  for n in range(len(S)):
    if i + n <= len(S):
      str_set.add(S[n:i+n])
str_set = list(str_set)
str_set.sort()
print(str_set[K-1])

Measured memory_bytes: 4464
#include <iostream>
#include <string>

int main(void) {
    std::string s;
    std::string t = "";
    std::cin >> s;
    for (int i = s.length() - 1; i >= 0; i--) {
        t += s[i];
    }
    std::cout << t << std::endl;
    return 0;
}

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

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

  int64_t l0=2,l1=1,l2;
  if ( N == 1 ) {
    cout << l1;
  } else {
    for (int i = 2; i <= N; i++) {
      l2 = l1 + l0;
      l0 = l1;
      l1 = l2;
    }
    cout << l2;
  }
}


Measured memory_bytes: 3584
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		// TODO 自動生成されたメソッド・スタブ
		Scanner sc = new Scanner(System.in);

		int a = sc.nextInt();
		int b = sc.nextInt();

		if(a<b) {
			System.out.println("a < b");
		} else if(a>b) {
			System.out.println("a > b");
		} else {
			System.out.println("a == b");
		}
	}

}


Measured memory_bytes: 26144
#include<iostream>
#include<cstdio>
#include<set>
#include<algorithm>
#include<queue>
#include<cstring>
#include<vector>
using namespace std;
typedef long long ll;
const int N=1e5+5;
int a[N];
int n,A,B,C;
bool check(ll);
int main(){
    scanf("%d%d%d",&n,&A,&B);
    C=A-B;
    for(int i=1;i<=n;i++) scanf("%d",a+i);
    ll l=0,r=2e9,mid;
    while(l<r){
        mid=(l+r)/2;
        if(check(mid))r=mid;
        else l=mid+1;
    }
    cout<<l;
}
bool check(ll x){
    ll cnt=0,sum=x*B;
    for(int i=1;i<=n;i++)if(a[i]>sum){
        cnt+=(a[i]-sum+C-1)/C;
    }
    return cnt<=x;
}


Measured memory_bytes: 640
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define FOR(i,a,b) for(ll i=a;i<=b;i++)
#define FORD(i,a,b) for(ll i=a;i>=b;i--)
#define ALL(a)  (a).begin(),(a).end()
#define SZ(a) int((a).size())
#define SORT(c) sort((c).begin(),(c).end())
#define PB push_back
#define MP make_pair
#define MEMSET(v, h) memset((v), h, sizeof(v))
#define sqr(x)  ((x) * (x)) 
#define cub(x)  ((x) * (x) * (x))
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
// ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
// ll lcm(ll a,ll b){return a/gcd(a,b)*b;}

int main(){
  ll n,m; cin >> n >> m;
  ll x[n],y[n],z[n];
  FOR(i,0,n-1){
    cin >> x[i] >> y[i] >> z[i];
  }

  ll ans = 0;

  FOR(i,0,1){
    FOR(j,0,1){
      FOR(k,0,1){
        ll sum[n];
        ll res = 0;
        MEMSET(sum,0);
        FOR(p,0,n-1){
          sum[p] += x[p] * pow(-1,i+1) + y[p] * pow(-1,j+1) + z[p] * pow(-1,k+1); 
        }
        sort(sum,sum+n,greater<ll>());
        FOR(p,0,m-1) res += sum[p];
        chmax(ans,res);
      }
    }
  }

  cout << ans << endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
vector <int> a;
vector <int> all;
int n,m;

int bainary_search(int i) {
  int L=0;int R = all.size()-1,M;
  
  while(L<R) {
    M = (L+R)/2;
    if(all[i]+all[M] <= m) L = M+1;
    else R = M;
  }

  if(L != 0) L--;
  return L;
}

int main() {

  while(1) {
    cin >> n >> m;
    if(n == 0 && m == 0) break;
    a.resize(n);
    for(int i=0;i<n;i++) cin >>a[i];
    a.push_back(0);
    all.clear();
    for(int i=0;i<=n;i++)
      for(int j=i;j<=n;j++)
	all.push_back(a[i]+a[j]);

    sort(all.begin(),all.end());

    int allsize = all.size();
    int ans = 0;
    for(int i=0;i<allsize;i++) {
      int res = all[i] + all[bainary_search(i)];
      if(ans < res && res <= m) ans = res;
    }
    cout << ans << endl;
  }
  return 0;
}

Measured memory_bytes: 3172
#![allow(unused, non_snake_case, dead_code, non_upper_case_globals)]
use {
    proconio::{marker::*, *},
    std::{cmp::*, collections::*, mem::*, ops::*},
};

#[fastout]
fn main() {
    input! {//
        n:usize,q:usize,
      mut   stx:[(i64,i64,i64);n],
        d:[i64;q],
    }
    let mut rng = vec![];
    for (s, t, x) in stx {
        rng.push((s - x, 0, x));
        rng.push((t - x, -1, x));
    }
    for &d in d.iter() {
        rng.push((d, 1, 999999999i64));
    }
    rng.sort();
    // dbg!(&rng);
    // let mut q = MinQueue::new();
    let mut st = BTreeSet::new();

    for &(x, typ, val) in rng.iter() {
        if typ == 0 {
            st.insert(val);
        } else if typ == -1 {
            st.remove(&val);
        } else {
            // dbg!(&st);
            println!(
                "{}",
                if let Some(x) = st.iter().next() {
                    *x
                } else {
                    -1
                }
            );
        }
    }
}


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

int main(){
	// sengen
	int n,q;
	string s;
	// nyuryoku
	cin >> n >> q >> s;
	int l[q],r[q];
	for(int i=0;i<q;i++){
		cin >> l[i] >> r[i];
		l[i]--; r[i]--;
	}
	int sum[s.size()];
	sum[0] = 0;
	for(int i=1;i<n;i++){
		if(s[i-1] == 'A' && s[i] == 'C'){
			sum[i] = sum[i-1] + 1;
		}else{
			sum[i] = sum[i-1];
		}
	}
	// keisan
	for(int i=0;i<q;i++){
		cout << sum[r[i]] - sum[l[i]] << endl;
	}
	// syutsuryoku
}

Measured memory_bytes: 4940
N, Q = map(int, input().split())
S = list(input())

class bit:
  def __init__(self, N):
    self.__N = N
    self.__a = [0] * N
  def add_(self, x, v):
    x += 1
    while x < self.__N:
      self.__a[x] += v
      x += x & -x
  def show_(self):
    print(self.__a[1:])
    
  def sum_(self, x):
    ans = 0
    while x > 0:
      ans += self.__a[x]
      x -= x & -x
    return ans
  def sub_sum_(self, x, y):
    return self.sum_(y) - self.sum_(x)
prev = "0"
BIT = bit(N)
for i, val in enumerate(S):
  if prev == "A" and val == "C":
    BIT.add_(i-1, 1)
  prev = val
for i in range(Q):
  x, y = map(int, input().split())
  x -= 1
  y -= 1
  print(BIT.sub_sum_(x,y))

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

using namespace std;

#define all(x) x.begin(), x.end()
#define sz(x) (int) x.size()
#define pb push_back
#define endl '\n'
#define snd second
#define fst first
#define fastio cin.tie(NULL),cout.sync_with_stdio(true)

typedef long long int ll;
typedef unsigned long long int ull;
typedef vector <int> vi;
typedef pair <ll, int> ii;
typedef pair <ii,int> iii;

const ll inf = 1e17;
const ll mod = 1e9 + 7;
const int N = 200005;

ll v[N];

void solve(){
	int n;
	cin >> n;
	for(int i = 1; i <= n; i++){
		cin >> v[i];
		v[i] += v[i-1];
	}
	ll ans = inf, l = 1, r = 3;
	for(int i = 2; i <= n-2; i++){
		while(l < i and abs(v[l] - (v[i] - v[l])) >= abs(v[l+1] - (v[i] - v[l+1])))
			l++;
		while(r < n and abs(v[r] - v[i] - (v[n] - v[r])) >= abs(v[r+1] - v[i] - (v[n] - v[r+1])))
			r++;
		ll a = v[l], b = v[i] - v[l], c = v[r] - v[i], d = v[n] - v[r];
		ans = min(ans, max(a,max(b,max(c,d)))-min(a,min(b,min(c,d))));
	}
	cout << ans << endl;
}

int main(){
	fastio;
	int t = 1;
	//cin >> t;
	while(t--)
		solve();
	return 0;
}


Measured memory_bytes: 5100
#include<bits/stdc++.h>
using namespace std;
#define N 15
char s[N+5];
int main(){
	int n,cnt=0;scanf("%s",s+1);n=strlen(s+1);
	for(int i=1;i<=n;i++)cnt+=s[i]=='o';
	puts(15-n>=8-cnt?"YES":"NO");
	return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<cstdio>

using namespace std;

int main(void){
	while( true ){
		int digits[10] = {0,};
		for(int i = 0; i < 10; i++){
			char c;

			cin >> c;
			if( cin.eof() ) return 0;
			digits[i] = c - '0';
		}
		cin.ignore();
		for(int i = 0; i < 9; i++){
			for(int j = 0; j < 9 - i; j++){
				digits[j] = (digits[j] + digits[j + 1]) % 10;
			}
		}
		cout << digits[0] << endl;
	}
	return 0;
}

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

int main()
{
    int n,x;
    cin>>n>>x;
    vector<int> v;
    int num;
    for(int i=0; i<n; i++){
        cin>>num;
        v.push_back(num);
    }
    sort(v.begin(),v.end());
    num = 0;
    for(int i=0; i<n; i++){
        if(x-v[i]>=0) {
            x-=v[i];
            num++;
            if(i==n-1) {
                while(1){
                    if(x-v[0]>=0) {
                        x-=v[0];
                        num++;
                        if(x==0) { break;}
                    }
                    else { break; }
                }
            }
        }
        else if(x-v[i]<0) { break;}
    }
    cout << num << endl;
    return 0;
}

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

#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define ALL(a) begin(a),end(a)
#define COUNTOF(a) (sizeof(a)/sizeof(a[0]))
#define SP << " " <<
#define FMT(a) #a<<":"<<a 
#define FMT2(a,b) #a<<":"<<a<<", "<<#b<<":"<<b 
#define FMT3(a,b,c) #a<<":"<<a<<", "<<#b<<":"<<b<<", "<<#c<<":"<<c 
#define FMT4(a,b,c,d) #a<<":"<<a<<", "<<#b<<":"<<b<<", "<<#c<<":"<<c<<", "<<#d<<":"<<d 
typedef long long ll;
template<class T> istream& operator >> (istream& s, vector<T>& v) {
  for (T& x: v) s >> x;
  return s;
}
inline void Yes(bool f=true){cout<<(f?"Yes":"No")<<endl;}
inline void YES(bool f=true){cout<<(f?"YES":"NO")<<endl;}
#define ANS(a) cout<<a<<endl

int main()
{
    cin.tie(0); ios::sync_with_stdio(false);
    //cout<<std::fixed<<std::setprecision(10);

    int a,b,c;
    int x,y,z;
    int ans;
    cin >>a>>b>>c;

    x=abs(a-b), y=abs(b-c), z=abs(c-a);
    ans = x+y+z-max({x,y,z});

    cout << ans << endl;
}


Measured memory_bytes: 256
import java.util.*;
import java.io.*;
import java.math.*;

public class Main {
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        long[] a = new long[n];
        for(int i = 0; i < n; i++){
            a[i] = sc.nextLong();
        }
        long ans = 0;
        long now = 1;
        for(int i = 0; i < n; i++){
            if(a[i] == now){
                now++;
            }else{
                ans++;
            }
        }
        if(ans == n){
            System.out.println(-1);
        }else{
            System.out.println(ans);
        }
    }
}



Measured memory_bytes: 87860
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
LL gcd(LL a,LL b) {
    return b==0?a:gcd(b,a%b);
}
int main() {
    int n;
    scanf("%d",&n);
    LL gg=1;
    for(int i=0;i<n;i++) {
        LL x,num;
        scanf("%lld",&x);
        num=gcd(gg,x);
        gg=gg/num*x;
    }
    printf("%lld\n",gg);
    return 0;
}

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

#include<cstdio>
#define r(i,n) for(int i=0;i<n;i++)

int check(string sub){
  if(sub<="12" && sub>"00")return 1;
  else return -1;
}

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

  if(check(s.substr(0,2))==1&&check(s.substr(2,2))==1){
    cout<<"AMBIGUOUS"<<endl;
  }else if(check(s.substr(0,2))!=check(s.substr(2,2))){
    if(check(s.substr(0,2))==1){
      cout<<"MMYY"<<endl;
    }else {
      cout<<"YYMM"<<endl;
    }
  }else{
    cout<<"NA"<<endl;
  }

return 0;}


Measured memory_bytes: 256
n = int(input())
h = list(map(int,input().split()))
ans = []

for i in range(n):
    if i == 0:
        ans.append(0)
    elif i == 1:
        ans.append(abs(h[1]-h[0]))
    else:
        ans.append(min(ans[-1]+abs(h[i]-h[i-1]),ans[-2]+abs(h[i]-h[i-2])))

print(ans[-1])


Measured memory_bytes: 13908
#include "bits/stdc++.h"
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/detail/standard_policies.hpp>

using namespace std;
using namespace __gnu_pbds;

#define _ ios_base::sync_with_stdio(0);cin.tie(0);
#define endl '\n'
#define debug(x) cerr << #x << " == " << (x) << '\n';
#define all(X) X.begin(), X.end()
#define sz(X) (int)X.size()

template<typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
using ll = long long;
using ii = pair<int, int>;
using vi = vector<int>;
using vii = vector<ii>;

mt19937 rng((int) chrono::steady_clock::now().time_since_epoch().count());

const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3fLL;

// xz

int main()
{ _
    int n; cin >> n;
    vi L(n);
    for (int i = 0; i < n; ++i) cin >> L[i];

    sort(all(L));

    auto check = [](int x, int y, int z)
    {
        if (x == y) return false;
        if (x == z) return false;
        if (y == z) return false;
        if (x + y <= z) return false;
        return true;
    };

    int ans = 0;
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < i; ++j)
            for (int k = 0; k < j; ++k)
                ans += check(L[k], L[j], L[i]);

    cout << ans << endl;


    exit(0);
}



Measured memory_bytes: 3668
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define REP(i, a, b) for(ll i=(a); i<(b); i++)
#define PER(i, a, b) for(ll i=(a); i>=(b); i--)
#define rep(i, n) REP(i, 0, n)
#define per(i, n) PER(i, n, 0)
#define ALL(a)  (a).begin(),(a).end()
const ll INF = 1e18+18;
const ll MAX = 200000;
const ll MOD = 1000000007;
#define Yes(n) cout << ((n) ? "Yes" : "No") << endl;
#define YES(n) cout << ((n) ? "YES" : "NO") << endl;



int main(){
    int N;
    cin>>N;
    N%=10;
    if(N==2||N==4||N==5||N==7||N==9){
        cout<<"hon"<<endl;
        return 0;
    }
    if(N==0||N==1||N==6||N==8){
        cout<<"pon"<<endl;
        return 0;
    }
    if(N==3){
        cout<<"bon"<<endl;
        return 0;
    }
}

Measured memory_bytes: 3636
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {

	public static void main(String[] args) throws IOException {
		// TODO 自動生成されたメソッド・スタブ
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		while(true){
			String[] tmpArray = br.readLine().split(" ");

			int n = Integer.parseInt(tmpArray[0]);
			int l = Integer.parseInt(tmpArray[1]);
			int r = Integer.parseInt(tmpArray[2]);

			if(n == 0){
				break;
			}

			int a[] = new int[n];

			for(int i = 0; i < n; i++){
				a[i] = Integer.parseInt(br.readLine());
			}

			int count = 0;
			for(int i = l; i <= r; i++){
				//閏年チェック
				boolean hit = false;
				for(int j = 0; j < n; j++){
					if(i % a[j] == 0){
						hit = true;
						if(j % 2 == 0){
							count++;
						}

						break;
					}
				}
				if(!hit && n % 2 == 0){
					count++;
				}
			}

			System.out.println(count);
		}
	}

}



Measured memory_bytes: 25976
#include "cstdio"
#include "vector"
#define INF 0x7fffffff
using namespace std;
vector<int> vec;
int main()
{
	int n,count;
	int i,j,min=INF;
	scanf("%d",&n);
	vec.resize(n);
	for(i=0;i<n;i++)
	{
		scanf("%d",&vec[i]);
		count=0;
		while(vec[i]%2==0)
		{
			vec[i]/=2;
			count++;
		}
		if(count==0)
		{
			printf("0\n");
			return 0;
		}
		if(count<min)
		{
			min=count;
		}
	}
	printf("%d\n",min);
	return 0;
}

Measured memory_bytes: 256
def main():
    n = int(input())
    As = list(map(int, input().split()))

    std = As[0]
    ans = 0
    for i in range(1, n):
        if std >= As[i]:
            ans += std - As[i]
        else:
            std = As[i]
    print(ans)


if __name__ == "__main__":
    main()


Measured memory_bytes: 32264
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, N) for (int i = 0; i < (int)N; ++i)
#define all(a) (a).begin(), (a).end()

const int MOD = 1e9 + 7;

int N, M;

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

  vector<bool> broken(N, false);
  rep(i, M) {
    int a;
    cin >> a;
    broken[a] = true;
  }

  vector<int> c(N + 1, 0);
  c[0] = 1;
  rep(i, N) {
    if (i + 1 <= N && !broken[i + 1]) c[i + 1] = (c[i + 1] + c[i]) % MOD;
    if (i + 2 <= N && !broken[i + 2]) c[i + 2] = (c[i + 2] + c[i]) % MOD;
  }

  cout << c[N] << endl;

  return 0;
}


Measured memory_bytes: 640
#define _USE_MATH_DEFINES
#include<stdio.h>
#include<string>
#include<iostream>
#include<cctype>
#include<cstdio>
#include<vector>
#include<queue>
#include<stack>
#include<algorithm>
#include<math.h>
#include<set>
#include<map>
#include<iomanip>
#include<functional>
using namespace std;

#define ll long long
#define MOD 1000000007

int main() {
	cin.tie(0); ios::sync_with_stdio(false);
	ll N; cin >> N;
	vector<ll> a(N);
	for (int i = 0; i < N; i++) cin >> a[i];
	sort(a.begin(), a.end());
	cout << a[N - 1] - a[0] << endl;
}

Measured memory_bytes: 256
#include<iostream>
#include<map>
#include<set>
#include<string>
#include<algorithm>
#include<cmath>
#include<vector>
#include<queue>
#include<stack>
#include<limits>
#include<sstream> 
#include<unordered_map>      

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef int itn;

const int inf = numeric_limits<int>::max() >> 2;
const ll linf = numeric_limits<ll>::max() >> 2;
const ull ulinf = numeric_limits<ull>::max() >> 2;
const double pi = acos(-1);
const int dx[4]={1,0,-1,0};
const int dy[4]={0,1,0,-1};
const int dx8[8]={-1,0,1,-1,1,-1,0,1};
const int dy8[8]={-1,-1,-1,0,0,1,1,1};

#define p_queue(i) priority_queue<i> 
#define rp_queue(i) priority_queue<i, vector<i>, greater<i>> 
#define umap(i,j) unordered_map<i,j>
#define P(p) cout<<(p)<<endl
#define PS(p) cout<<(p)<< " "
#define PN cout << endl
#define rep(i,m,n) for(int i = (m); i < (int)(n); i++)
#define rrep(i,m,n) for(int i = (n-1); i >= (int)(m); i--)
#define inrep(n,a) for(int i = 0; i < (int)(n); i++)cin >> a[i];
#define mod(i) ((i)%(ll)(1e9 + 7))
#define divm(a,b) (mod(a * modpow((ll)b,(ll)(1e9+5))))
#define rsort(a,b,c) sort(a, b, greater<c>())
#define vsort(v) sort(v.begin(), v.end())
#define rvsort(v,c) sort(v.begin(), v.end(), greater<c>()) 
#define ft first
#define sd second
#define pb push_back
#define it insert
#define sz(x) ((int)(x).size())
#define lb(a,n,k) (lower_bound(a,a+n,k) - (a)) 
#define vlb(a,k)  (lower_bound(a.begin(),a.end(),k) - a.begin())
#define ub(a,n,k) (upper_bound(a,a+n,k) - (a)) 
#define vub(a,k)  (upper_bound(a.begin(),a.end(),k) - a.begin())
#define YES cout<<"YES"<< endl
#define NO cout<<"NO"<<endl
#define Yes cout<<"Yes"<<endl
#define No cout<<"No"<<endl  
#define yes cout<<"yes"<<endl
#define no cout<<"no"<<endl
#define ret return


ll modpow(ll i,ll j){ ll tmp=1; while(j){ if(j%2)tmp=mod(tmp*i);i=mod(i*i);j/=2;}return tmp;}
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
ll lcm(ll a, ll b) { return a / gcd(a, b) * b; }


/*
vector<string> split(const string &str, char sep){
    vector<string> v;
    stringstream ss(str);
    string buffer;
    while( getline(ss, buffer, sep) ) {
        v.push_back(buffer);
    }
    return v;
}
*/

/*
ll ncr[100][100];
ll nCr(int n, int r){if(n==r) ret ncr[n][r] = 1; if(r==0) ret ncr[n][r] = 1; if(r==1) ret ncr[n][r] = n;if(ncr[n][r]) ret ncr[n][r]; ret ncr[n][r] = nCr(n-1,r) + nCr(n-1,r-1);}

ll npr[100][100]={};
ll nPr(int n,int r){if(npr[n][r])ret npr[n][r];if(r==0)ret npr[n][r] = 1;if(r==1)ret npr[n][r] = n;ret npr[n][r] = n * nPr(n-1,r-1);}

ll nHr(int n,int r){ret nCr(n+r-1,r);}
*/

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

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

    rep(i,0,n-1){
	ll a;
	cin >>a ;
	m[a]++;
    }

    rep(i,1,n+1){
	P(m[i]);
    }
    
    return  0;
}


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

using namespace std;

int a[55],b[55],c[55];

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

    int n,i,sum=0,pr=-1;
    cin>>n;
    for(i=1;i<=n;i++)cin>>a[i];
    for(i=1;i<=n;i++)cin>>b[i];
    for(i=1;i<n;i++)cin>>c[i];
    for(i=1;i<=n;i++){
        sum+=b[a[i]];
        if(pr == a[i]-1)sum+=c[pr];
        pr = a[i];
    }
    cout<<sum<<endl;
    return 0;
}



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

using ll = long long;

constexpr int INF =1e9;

constexpr ll mod = 1e9+7;

int main() {
    string s,t ;
    cin >> s >> t;
    vector<int> scnt(s.size()+1), tcnt(t.size()+1);
    for(int i=0; i<s.size(); ++i) {
        scnt[i+1] = s[i] == 'A';
        scnt[i+1] += scnt[i];
    }
    for(int i=0; i<t.size(); ++i) {
        tcnt[i+1] = t[i] == 'A';
        tcnt[i+1] += tcnt[i];
    }
    int q;
    cin >> q;
    while(q--) {
        int a, b, c, d;
        cin >> a >> b >> c >> d;
        int sc = scnt[b] - scnt[a-1];
        int tc = tcnt[d] - tcnt[c-1];
        int slen = b - a + 1, tlen = d - c + 1;
        if((sc * 2 + slen - sc) % 3 == (tc * 2 + tlen - tc) % 3) {
            cout << "YES" << endl;
        } else {
            cout << "NO" << endl;
        }
    }
}


Measured memory_bytes: 1664
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rrep(i, n) for (int i = (int)(n - 1); i >= 0; i--)
#define all(x) (x).begin(), (x).end()
#define sz(x) int(x.size())
#define get_unique(x) x.erase(unique(all(x)), x.end());
typedef long long ll;
typedef complex<double> Complex;
const int INF = 1e9;
const ll MOD = 1e9 + 7;
const ll LINF = 1e18;
template <class T>
bool chmax(T &a, const T &b) {
    if (a < b) {
        a = b;
        return 1;
    }
    return 0;
}
template <class T>
bool chmin(T &a, const T &b) {
    if (b < a) {
        a = b;
        return 1;
    }
    return 0;
}
template <class T>
vector<T> make_vec(size_t a) {
    return vector<T>(a);
}
template <class T, class... Ts>
auto make_vec(size_t a, Ts... ts) {
    return vector<decltype(make_vec<T>(ts...))>(a, make_vec<T>(ts...));
}

int main() {
    int n;
    cin >> n;
    map<string, int> mp;
    int MAX = 0;
    rep(i, n) {
        string s;
        cin >> s;
        mp[s]++;
        chmax(MAX, mp[s]);
    }
    for (auto p : mp) {
        if (p.second == MAX) {
            cout << p.first << endl;
        }
    }
}


Measured memory_bytes: 26240
from heapq import *

n,m,s,t=map(int,input().split())
s-=1
t-=1
INF=float("inf")
Gyen=[[]for i in range(n)]
Gsnu=[[]for i in range(n)]
for i in range(m):
  u,v,a,b=map(int,input().split())
  u-=1
  v-=1
  Gyen[u].append([v,a])
  Gyen[v].append([u,a])
  Gsnu[u].append([v,b])
  Gsnu[v].append([u,b])

def dijkstra(G,s):
  d=[INF]*n
  d[s]=0
  visited={s}
  que=[(0,s)]
  while(que):
    p=heappop(que)
    v=p[1]
    visited.add(v)
    for node,cost in G[v]:
      if (node not in visited) and d[node]>d[v]+cost:
        d[node]=d[v]+cost
        heappush(que,(d[node],node))
  return d

yen=dijkstra(Gyen,s)
snu=dijkstra(Gsnu,t)
ans=10**15
ans_list=[]
for i in reversed(range(n)):
  ans=min(ans,yen[i]+snu[i])
  ans_list.append(10**15-ans)
for i in ans_list[::-1]:
  print(i)

Measured memory_bytes: 134348
#include<stdio.h>
int main(){
           int a,b;
           scanf("%d %d",&a, &b);
           if(a<b){
                   printf("a < b\n");
           }else if(a>b){
                   printf("a > b\n");
           }else{
                   printf("a == b\n");
           }
           return 0;
}

Measured memory_bytes: 580
n=int(input())
a=list(map(int,input().split()))
d=dict()
for i in range(n):
  if a[i] not in d:
    d[a[i]]=1
  else:
    d[a[i]]+=1
s=0
l=list(d.items())
for i in range(len(l)):
  if l[i][1]>=2:
    s+=l[i][1]*(l[i][1]-1)//2
for i in range(n):
  if d[a[i]]<2:
    print(s)
  else:
    print(s-(d[a[i]]-1))

Measured memory_bytes: 92492
#include<iostream>
#include <bits/stdc++.h>
#include<stdio.h>
#include <stdlib.h>
#include<string>
#include<queue>
#include<algorithm>
#include<math.h>
#include<map>
using namespace std;


int main(){
	int N,M,ans=0;
	double cut;
	cin>>N;
	cin>>M;
	cut=sqrt(M);
	for(int i=1;i<=cut+1;i++){
		if(M%i==0){
			if(M/i>=N){
				ans=max(ans,i);
			}
			if(i>=N){
				ans=max(ans,M/i);
				break;
			}
		}
	}
	cout<<ans<<endl;
}

Measured memory_bytes: 256
package main

import (
	"fmt"
)

func main() {
	var N, M int
	fmt.Scan(&N, &M)

	L := make(map[int]int, M)

	for i := 0; i < N; i++ {
		var K int
		fmt.Scan(&K)
		for j := 0; j < K; j++ {
			var A int
			fmt.Scan(&A)
			L[A]++
		}
	}

	c := 0
	for _, v := range L {
		if v == N {
			c++
		}
	}
	fmt.Println(c)
}


Measured memory_bytes: 512
#include <stdio.h>

static const int N = 1000;

int main(){
  int i, j, A[N], length, swap, count = 0, mini;

  scanf("%d",&length);
  for(i = 0; i < length; i++){
    scanf("%d",&A[i]);
  }

  for(i = 0; i <= length-2; i++){
    mini = i;
    for(j = i; j <= length-1; j++){
      if(A[j] < A[mini]){
	mini = j;
      }
    }
    swap = A[i];
    A[i] = A[mini];
    A[mini] = swap;
    if(A[i] < A[mini]) count++;
  }

  for(i = 0; i < length; i++){
    printf("%d",A[i]);
    if(i <= length-2) printf(" ");
  }
  printf("\n");
  printf("%d\n",count);
  
  return 0;
}

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

int main() {
  int A, B, counter;
  cin >> A >> B;
  counter = 0;
  
  for (int i = A; i <= B; i++){
    int a, b, c, d;
    a = i / 10000;
    b = i / 1000 % 10;
    c = i / 10 % 10;
    d = i % 10;
    if (a == d && b == c){
      counter++;
    }
  }
  cout << counter << endl;
}


Measured memory_bytes: 256
#include<stdio.h>
   
struct dice{
           int a[6];
       };
struct dice dice1;
struct dice dice2;
   
void tate(){
            int cmp=dice2.a[0];
            dice2.a[0]=dice2.a[4];
            dice2.a[4]=dice2.a[5];
            dice2.a[5]=dice2.a[1];
            dice2.a[1]=cmp;
             }
void yoko(){
            int cmp=dice2.a[1];
            dice2.a[1]=dice2.a[2];
            dice2.a[2]=dice2.a[4];
            dice2.a[4]=dice2.a[3];
            dice2.a[3]=cmp;
             }
   
   
int main(){
    int i,j;
    for(i=0;i<6;i++){
           scanf("%d",&dice1.a[i]);
                     }
for(i=0;i<6;i++){
           scanf("%d",&dice2.a[i]);
                     }
   
for(i=0;i<5;i++){
   
              for(j=0;j<5;j++){
                              if(dice1.a[0]==dice2.a[0])break;
                               tate();
                               }
              for(j=0;j<5;j++){
                                if(dice1.a[1]==dice2.a[1])break;
                                yoko();
                                }
                  }
   
if(dice1.a[0]==dice2.a[0]&&dice1.a[1]==dice2.a[1]&&dice1.a[2]==dice2.a[2])printf("Yes\n");
else printf("No\n");
    
return 0;
}


Measured memory_bytes: 2112
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define F first
#define S second
#define mkp make_pair
#define pii pair<int,int>
typedef long long ll;
const int maxn=2e5+5;
const int mod=1e9+7;
int a[maxn];
int main(){
	int n;
	scanf("%d",&n);
	int ok=1;
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
		if(a[i]%2==0)if((a[i]%3!=0&&a[i]%5!=0))ok=0;
	}
	if(ok)printf("APPROVED\n");
	else printf("DENIED\n");
}



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

class Main{
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        char[] c=sc.next().toCharArray();
        sc.close();
        int l=c.length;
        if(l%2!=0){
            System.out.println("No");
            return;
        }
        for(int i=0;i<l/2;i++){
            if(c[i]!=c[i+l/2]){
                System.out.println("No");
                return;
            }
        }
        System.out.println("Yes");
    }
    
}


Measured memory_bytes: 23636
N, K = gets.split.map(&:to_i)
A = gets.split.map(&:to_i)
HH = Hash.new(0)

A.each do |a|
    HH[a] += 1
end

nums = HH.values.sort
sum = 0
while nums.size > K
    sum += nums.shift
end
puts sum

Measured memory_bytes: 32880
#include <stdio.h>
 
int main(){
    int n;
    double x1, x2, x3, x4, y1, y2, y3, y4, crs;
    
    scanf("%d", &n);
    
    while(n--){
        scanf("%lf %lf %lf %lf %lf %lf %lf %lf", &x1, &y1, &x2, &y2, &x3, &y3, &x4, &y4);
        
        crs = (x2 - x1) * (y4 - y3) - (x4 - x3) * (y2 - y1);
        
        if(crs < 0) crs *= -1;
        
        if(crs < 1e-10)
            printf("YES\n");
        else
            printf("NO\n");
    }
     
    return 0;
}

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

#define pb push_back
#define mp make_pair
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef complex<double> point;
#define xx real()
#define yy imag()

#define REP(i, a, b) for(int i = (a); i < (int)(b); i++)
#define REPN(i, a, b) for(int i = (a); i <= (int)(b); i++)
#define FA(it, x) for(__typeof((x).begin()) it = (x).begin(); it != (x).end(); it++)
#define SZ(x) (int)(x).size()
#define BE(x) (x).begin(), (x).end()
#define SORT(x) sort(BE(x))
#define _1 first
#define _2 second

#define x1 gray_cat_x1
#define y1 gray_cat_y1

template<class T> T gcd(T a, T b) { return b ? gcd(b, a % b) : a; }

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

#define file "I1"

const double EPS = 1e-9;
const double PI = acos(-1.);
const int INF = 1e9 + 10;
const ll MOD = 1e9 + 7;

const int MAXN = 500 + 5;

int g[MAXN][MAXN];

void rec_fill(int l, int r, int d) {
	if (l == r) {
		return;
	}
	int mid = (l + r) >> 1;
	rec_fill(l, mid, d + 1);
	rec_fill(mid + 1, r , d + 1);
	REPN(i, l, mid) {
		REPN(j, mid + 1, r) {
			g[i][j] = d;
		}
	}
}

void solve(){
	int n;
	scanf("%d", &n);
	rec_fill(1, n, 1);
	REP(i, 1, n) {
		REPN(j, i + 1, n) {
			printf("%d ", g[i][j]);
		}
		putchar('\n');
	}
}   

int main(){

    //freopen(file".in", "r", stdin); freopen(file".out", "w", stdout);
    int t = 1;
    //cin >> t;
    while(t--){
        solve();    
    }
}


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

using namespace std;


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

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

  int cur = 0;
  if (K < N * 2) {
    for (int step = 0; step < K; step++) {
      cur = A[cur];
    }
    cout << cur + 1 << endl;
    return 0;
  }

  cur = 0;
  int stepI = -1;
  vector<int> c;

  for (int step = 0; step < N * 2; step++) {
    if (stepI == -1 && numVisits[cur] == 1) {
      stepI = step;
    }
    if (stepI >= 0 && numVisits[cur] == 1) {
      c.push_back(cur);
    }
    numVisits[cur]++;
    cur = A[cur];
  }

  cout << c.at((K - stepI) % c.size()) + 1 << endl;
  return 0;
}


Measured memory_bytes: 5316
import java.lang.*;
import java.util.*;
public class Main{
public static void main(String[] args) 
{
	Scanner scanner=new Scanner(System.in);
	int n=scanner.nextInt();
	int x=scanner.nextInt();
	long[] a=new long[n];
	for(int i=0;i<n;i++)a[i]=scanner.nextInt();
	long cnt=0;
	long r,u;
	for(int i=0;i<n-1;i++)
	{	
		if((a[i+1]+a[i])>x){
			r=a[i+1]+a[i]-x;
			u=(int)Math.min(a[i+1],r);
			cnt+=u;
			a[i+1]-=u;
			if(a[i]>x)cnt+=a[i]-x;
		}
	}
	System.out.print(cnt);
}	
}


Measured memory_bytes: 60304
n = int(input())

xyh = []

for i in range(n):
    xyh.append(list(map(int, input().split())))

isOk = False
i = 0
j = 0
constant = -1

for i in range(101):
    for j in range(101):

        constant = -1
        for xyhTemp in xyh:
            if xyhTemp[2] != 0:
                temp = xyhTemp[2] + abs(i - xyhTemp[0]) + abs(j - xyhTemp[1])

                if constant == -1:
                    constant = temp

                if constant != temp:
                    break
        else:

            for p in xyh:
                if p[2] == 0 and constant - abs(i - p[0]) - abs(j - p[1]) > 0:
                    break
            else:
                isOk = True
                break
        
    if isOk:
        break

print(i, j, constant)
        


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

#define INF (1<<24)

int common[14][14], N;

bool match(string a, string b, int p)
{
	int s=a.size()-1;

	for(int i=0; i<=p; i++)
		if(a[s-p+i]!=b[i]) return false;

	return true;
}

int calc(string a, string b)
{
	int ret=0, len=min(a.size(), b.size());

	if(a.find(b,0)!=a.npos) return len;
		
	for(int i=0; i<len; i++)
		if(match(a,b,i)) ret=i+1;

	return ret;
}

bool isUseless(int p, string s, int used)
{
	int sz=s.size();
	for(int i=0; i<N; i++)
	{
		if(i==p) continue;
		if((used>>i)&1) continue;
		if(common[p][i]==sz||common[i][p]==sz) return true;
	}

	return false;
}


string in[14];
int dp[14][1<<14];

int solve()
{
	for(int i=0; i<N; i++)
	for(int j=0; j<N; j++)
		common[i][j]=calc(in[i],in[j]);

	int used=0;
	for(int i=0; i<N; i++)
		if(isUseless(i,in[i],used)) used|=(1<<i);

	for(int i=0; i<N; i++)
	for(int j=0; j<(1<<N); j++)
			dp[i][j]=INF;

	for(int i=0; i<N; i++)
	{
		if((used>>i)&1) continue;
			dp[i][used|(1<<i)]=in[i].size();
	}

	for(int i=0; i<(1<<N); i++)
	for(int u=0; u<N; u++)
	{
		if(dp[u][i]==INF) continue;
				
		for(int j=0; j<N; j++)
		{
			if( (i>>j) & 1 ) continue;

			int cost = in[j].size()-common[u][j];
		
			dp[j][i|(1<<j)] = min(dp[j][i|(1<<j)], dp[u][i]+cost);
		}
	}

	int res=INF;
	for(int i=0; i<N; i++)
		res=min(res, dp[i][(1<<N)-1]);

	return res;
}


int main()
{
	while(cin >> N, N)
	{
		for(int i=0; i<N; i++)
			cin >> in[i];

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

Measured memory_bytes: 1828
#include <stdio.h>


int main(){
	char buf[10];
	int ue;
	int sita;
	int tate;
	
		fgets(buf,10,stdin);
		sscanf(buf,"%d",&ue);
		fgets(buf,10,stdin);
		sscanf(buf,"%d",&sita);
		fgets(buf,10,stdin);
		sscanf(buf,"%d",&tate);
		
		printf("%d\n",(ue+sita)*tate/2);
	
		
	return 0;
}


Measured memory_bytes: 128
#include<bits/stdc++.h>
using namespace std;
int main(void){
	string s;
	int i;
	int flg;
	cin>>s;
	flg=0;
	for(i=0;i<(int)s.size();i++){
		if(i%2==0){
			if(s[i]=='L')	flg=1;
		}
		else{
			if(s[i]=='R')	flg=1;
		}
	}
	if(flg==0)	cout<<"Yes"<<endl;
	else		cout<<"No"<<endl;
	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using ll  = long long;
using Int = int;
#define int ll
#define rep(i,n) for(int i=0;i<n;i++)
#define loop(i,s,n) for(int i=s;i<n;i++)
#define erep(e,v) for(auto && e :v)
#define all(in) in.begin(), in.end()
#define MP make_pair
#define INF (sizeof(int) == 4 ? (int)1e9:(int)1e18)
#define EPS 0.0000000001
using namespace std;
template<class T, class S> void cmin(T &a, const S &b) { if (a > b)a = b; }
template<class T, class S> void cmax(T &a, const S &b) { if (a < b)a = b; }
template<typename Head, typename Value> auto vectors(const Head &head, const Value &v) { return vector<Value>(head, v); }
template<typename Head, typename... Tail> auto vectors(Head x, Tail... tail) { auto inner = vectors(tail...); return vector<decltype(inner)>(x, inner); }
template<class T> void join(T a){for(auto itr :a){if(itr != *a.begin())cout << " "; cout << itr;} }
using ld  = long double;
using pii = pair<int,int>;
using piii = pair<int,pii>;
int W,H;
int dx[]={0,0,1,-1}, dy[]={1,-1,0,0};
bool valid(int x,int y){return (0<=x&&x<W)&&(0<=y&&y<H);}
int MOD = 1000000007;
class dynamic_bitset{
public:
    long long bit;
    string sbit = "";
    unsigned long long bitsize = 0;
    dynamic_bitset(int _bit):bit{_bit}{
        for(int t = 1,num = 1;bitsize == 0;t++,num *= 2){
            if(num - 1 >= bit) bitsize = t;
        }
        for(int i = 0; i < bitsize; i++){
            sbit = ((bit >> i & 1) == 1 ? "1":"0") + sbit;
        }
    }
    dynamic_bitset(int _bit,int bitrange):bit{_bit}{
        for(int t = 1,num = 1;bitsize == 0;t++,num*=2){
            if(num - 1 >= bit) bitsize = t;
        }
        for(int i = 0; i < bitrange; i++){
            sbit = ( i < bitsize and ((bit >> i & 1) == 1 ) ? "1":"0") + sbit;
        }
    }
    auto test(int _idx){
        assert(_idx < sbit.size() && "excution will be out of range");
        return sbit[_idx] == '1';
    }
    void set(int _idx){
        assert(_idx < sbit.size() && "excution will be out of range");
        sbit[_idx] = '1';
    }
    auto size(){return sbit.size();}
};

int ans = 0;
signed main(){
    int h,w,k;
    cin >> h >> w >> k;
    auto dp = vectors(300, 300,0LL);
    dp[1][1] = 1;
    for(int j = 1; j <= h; j++){
        for(int i = 1; i <= w; i++){
            for(int bit = 0; bit < (1 << (w - 1));bit++){
                auto db = dynamic_bitset(bit,w-1);
                bool isValid = true;
                rep(i,(int)db.size() - 1){
                    if(db.test(i) and db.test(i+1))
                        isValid = false;
                }
                if(!isValid)continue;
                if(i+1 <= w and db.test(i-1)){
                    dp[i+1][j+1] = (dp[i+1][j+1] + dp[i][j]) % MOD;
                } else if(i-1 >= 1 and db.test(i-2)){
                    dp[i-1][j+1] = (dp[i-1][j+1] + dp[i][j]) % MOD;
                } else {
                    dp[i][j+1]   = (dp[i][j+1]   + dp[i][j]) % MOD;
                }
            }
        }
    }
    cout << dp[k][h+1] << endl;
}




Measured memory_bytes: 1024
#素数でない数
#   1
#   ２以外の２の倍数
#   二乗してもnumberを超えない奇数で割り切れる数
def checkPrime(number)
  if number == 2
    return true
  elsif number % 2 == 0
    return false
  else
    i = 3
    while (i * i < number + 1)
      if number % i == 0
        return false
      end
      i += 2
    end
  end
  return true;
end

numPrime = Array.new(1000000)
input = ""

#あらかじめ素数の数を求めておく
numPrime[0] = 0
numPrime[1] = 0
for i in 2...numPrime.size
  numPrime[i] = numPrime[i - 1]
  if checkPrime(i)
    numPrime[i] += 1
  end
end

#メインルーチン
while input = gets
  p numPrime[input.to_i]
end

Measured memory_bytes: 13904