akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define fastio ios_base::sync_with_stdio(false); cin.tie(0)
#define loop(i, a, b) for(lli i=a; i<b; i++)
#define loopb(i, a, b) for(lli i=a; i>=b; i--)
#define pb push_back
#define umap unordered_map
typedef long long int lli;
typedef pair<lli, lli> pii;
typedef vector<lli> vll;
// use to avoid collision
struct custom_hash {
    static uint64_t splitmix64(uint64_t x) {
        // http://xorshift.di.unimi.it/splitmix64.c
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }
 
    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
};
// for pair in unordered_map
struct hash_pair {
    static uint64_t splitmix64(uint64_t x) {
    // http://xorshift.di.unimi.it/splitmix64.c
    x += 0x9e3779b97f4a7c15;
    x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
    x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
    return x ^ (x >> 31);
	}
    template <class T1, class T2>
    size_t operator()(const pair<T1, T2>& p) const{
        auto hash1 = hash<T1>{}(p.first);
        auto hash2 = hash<T2>{}(p.second);
        uint64_t x = hash1 ^ hash2;
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
};
lli M = 1e9 + 7;
lli power(lli x, lli y){
    lli res = 1;
    x = x;
    while (y > 0) {
        if (y & 1)
            res = (res*x);
        y = y>>1;
        x = (x*x);
    }
    return res;
}
lli A[1005], B[1005], dp[10005][1005];
lli n, h;
lli calc(lli health, lli index){
	if(health <= 0)
		return 0;
	else if(index == n)
		return 1e15;
	else if(dp[health][index] != -1)
		return dp[health][index];
	lli ans = 1e15;
	ans = min(ans, min(calc(health - A[index], index) + B[index], min(calc(health, index+1), calc(health-A[index], index+1) + B[index])));
	dp[health][index] = ans;
	return ans;
}
lli solve(){
	cin>>h>>n;
	memset(dp, -1, sizeof(dp));
	loop(i, 0, n)
		cin>>A[i]>>B[i];
	cout<<calc(h, 0)<<"\n";
	return 0;
}
int main(){
	fastio;
	lli t;
	// cin>>t;
	t = 1;
	while(t>0){
		t--;
		solve();
	}
}

Measured memory_bytes: 79360
n,m = gets.chomp.split(" ").map(&:to_i)
edge = m.times.map{gets.chomp.split(" ").map(&:to_i)}
path = Array.new(n).map{Array.new(n,100000)}
ans = 0
edge.each do |i,j,k|
  path[i-1][j-1] = path[j-1][i-1] = k
end
n.times do |i|
  path[i][i] = 0
end
for i in 0..n-1
  for j in 0..n-2
    for k in j+1..n-1
      if path[j][k] > path[j][i]+path[i][k]
        path[j][k] = path[k][j] = path[j][i]+path[i][k]
      end
    end
  end
end
edge.each do |i,j,k|
  if path[i-1][j-1] < k
    ans += 1
  end
end
p ans

Measured memory_bytes: 2172
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define inf 1000000010
#define N 55
char getc(){char c=getchar();while ((c<'A'||c>'Z')&&(c<'a'||c>'z')&&(c<'0'||c>'9')) c=getchar();return c;}
int gcd(int n,int m){return m==0?n:gcd(m,n%m);}
int read()
{
	int x=0,f=1;char c=getchar();
	while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}
	while (c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();
	return x*f;
}
typedef pair<int,int> pii;
int n,ans;
struct data{int x,y;
}a[N];
map<pii,int> f;
signed main()
{
	n=read();
	for (int i=1;i<=n;i++) a[i].x=read(),a[i].y=read();
	for (int i=1;i<=n;i++)
		for (int j=1;j<=n;j++)
		if (i!=j)
		{
			ans=max(ans,++f[make_pair(a[i].x-a[j].x,a[i].y-a[j].y)]);
		}
	cout<<n-ans;
	return 0;
	//NOTICE LONG LONG!!!!!
}

Measured memory_bytes: 384
#include<iostream>
#include<algorithm>
#include<queue>
using lint=int64_t;
using namespace std;

const lint dh[]={1,0,-1,0};
const lint dw[]={0,-1,0,1};
const lint INF=1e11;
int main()
{
	lint H,W;
	cin >> H >> W;
	char mat[1010][1010];
	lint dist[1010][1010];

	for(int i=0;i<=H+1;i++)
	{
		for(int j=0;j<=W+1;j++)
		{
			if(i==0 || j==0 || i==H+1 || j==W+1)
				dist[i][j]=INF;
		}
	}
	for(int i=1;i<=H;i++)
	{
		for(int j=1;j<=W;j++)
		{
			cin >> mat[i][j];
			if(mat[i][j]=='#')
				dist[i][j]=1;
		}
	}

	for(int i=1;i<=H;i++)
	{
		for(int j=1;j<=W;j++)
		{
			if(dist[i][j]==0)
			{
				dist[i][j]=dist[i][j-1];
				if(dist[i][j]!=0)dist[i][j]++;
			}
			else
				dist[i][j]=min(dist[i][j],dist[i][j-1]+1);
		}
		for(int j=W;j>0;j--)
		{
			if(dist[i][j]==0)
			{
				dist[i][j]=dist[i][j+1];
				if(dist[i][j]!=0)dist[i][j]++;
			}
			else
				dist[i][j]=min(dist[i][j],dist[i][j+1]+1);
		}
	}

	for(int j=1;j<=W;j++)
	{
		for(int i=1;i<=H;i++)
		{
			if(dist[i][j]==0)
			{
				dist[i][j]=dist[i-1][j];
				if(dist[i][j]!=0)dist[i][j]++;
			}
			else
				dist[i][j]=min(dist[i][j],dist[i-1][j]+1);
		}
		for(int i=H;i>0;i--)
		{
			if(dist[i][j]==0)
			{
				dist[i][j]=dist[i+1][j];
				if(dist[i][j]!=0)dist[i+1][j]++;
			}
			else
				dist[i][j]=min(dist[i][j],dist[i+1][j]+1);
		}
	}
	
	lint ans=0;
	for(int i=1;i<=H;i++)
	{
		for(int j=1;j<=W;j++)
		{
			ans=max(ans,dist[i][j]);
			//cout << dist[i][j] << " ";
		}
		//cout << endl;
	}
	ans--;
	if(ans<0)ans=0;
	cout << ans << endl;
	return 0;
}
/*
using Info=pair<lint,pair<lint,lint>>;
Info makeInfo(int x,int y,int z)
{
	return make_pair(x,make_pair(y,z));
}

int main()
{
	lint H,W;
	cin >> H >> W;
	string mat[1010];

	for(int i=0;i<H;i++)
		cin >> mat[i];
	
	lint ans=0;
	for(int i=0;i<H;i++)
	{
		for(int j=0;j<W;j++)
		{
			if(mat[i][j]=='#')
				continue;
			bool used[1010][1010]={};
			queue<Info> que;
			que.push(makeInfo(0,i,j));
			while(!que.empty())
			{
				lint cd=que.front().first;
				lint ch=que.front().second.first;
				lint cw=que.front().second.second;

				que.pop();
				
				used[ch][cw]=true;
				if(mat[ch][cw]=='#')
				{
					ans=max(ans,cd);
					break;
				}

				for(int i=0;i<4;i++)
				{
					lint nh=ch+dh[i];
					lint nw=cw+dw[i];

					if(nh<0 || nw<0 || nh>=H || nw>=W || used[nh][nw]==true)
						continue;

					que.push(makeInfo(cd+1,nh,nw));
				}
			}
		}
	}

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


Measured memory_bytes: 9216
#include <iostream>
#include <cmath>
#include <algorithm>
#include <climits>
#include <vector>
#include <string>
#include <set>
#include <iomanip>
#include <map>
#define rep(i,n) for (int i=0;i<(n);++i)
#define REP(i,n) for (int i=0;i<=(n);++i)
#define all(x) (x).begin(), (x).end()
using namespace std;
typedef long long ll;
const int INF = 10000000;

int gcd(int a,int b){return b?gcd(b,a%b):a;}

int main() {
    int a, b; cin >> a >> b;
    cout << a * b << endl;
}

Measured memory_bytes: 3644
#include <iostream>
#include <string>
#include <algorithm>

using namespace std;

int main(void) {
    string S, T;
    cin >> S >> T;
    size_t N = S.size();
    for(int i=0; i<N; ++i) {
        if(S == T) {
            cout << "Yes" << endl;
            return 0;
        } else {
            rotate(S.begin(), S.end()-1, S.end());
        }
    }
    cout << "No" << endl;
    return 0;
}


Measured memory_bytes: 256
N=int(input())
A=[int(i) for i in input().split()]
D={}
x=0
lis=[]
for a in A:
	try:
		D[a]=D[a]+((D[a]*2)**0.5//1)+1
	except:
		D[a]=0

z=sum(D.values())
for i in range(len(A)):
	x=0
	y=((D[A[i]]*2)**0.5)//1
	x=x+z-y
	print(int(x))


Measured memory_bytes: 92496
#include <bits/stdc++.h>
using namespace std;
int main(){
  int N;
  cin >> N;
  vector <int> vec(N);
  for (int i = 0; i < N; i++){
    cin >> vec.at(i);
  }
  int count=0;
  for (int i=0; i < N; i++){
    if(vec.at(i) != (i+1)){
      count ++;
    }
  }
  if (count >= 3){
    cout << "NO" << endl;
  }
  else{
    cout << "YES"<< endl;
  }
}
  
  
  

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

class Main{
    public static void main(String[] args) throws IOException{
	Scanner S=new Scanner(System.in);
	int i,n,m,t=0;
	Queue<String>P=new LinkedList<String>();
	Queue<Integer>T=new LinkedList<Integer>();
	n=S.nextInt();
	m=S.nextInt();
	for(i=0;i<n;i++){
	    P.add(S.next());
	    T.add(S.nextInt());
	}
	while(0<P.size()){
	    if(0<(T.peek()-m)){
		P.add(P.poll());
		T.add(T.poll()-m);
		t=t+m;
	    }
	    else{
		t=t+T.poll();
		System.out.println(P.poll()+" "+t);
	    }
	}
    }
}
	
			      



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

#ifdef LOCAL
#include "dump.hpp"
#else
#define dump(...)
#define dumpv(...)
#endif

#define rep(i, n) for (int i = 0; i < (n); i++)
typedef long long ll;
typedef pair<int, int> P;
const int MOD = 1e9 + 7;
const int INF = 1001001001;
const ll LINF = 1001002003004005006ll;

void solve() {
  int n, c;
  cin >> n >> c;
  vector<int> p(100005 * 2);
  vector<int> q(100005 * 2);
  rep(i, n) {
    int s, t, cn;
    cin >> s >> t >> cn;
    cn--;
    s = s * 2 - 1;
    t = t * 2;
    if (q[s + 1] & (1 << cn))
      q[s + 1] ^= (1 << cn);
    else
      p[s] |= (1 << cn);
    if (p[t - 1] & (1 << cn))
      p[t - 1] ^= (1 << cn);
    else
      q[t] |= (1 << cn);
  }
  dumpv(p, 90);
  dumpv(q, 90);
  int cnt = 0;
  int ans = 0;
  rep(i, p.size()) {
    if (!p[i] && !q[i]) continue;
    rep(j, 30) {
      if (p[i] & (1 << j)) cnt++;
      if (q[i] & (1 << j)) cnt--;
    }
    dump(i, cnt);
    ans = max(ans, cnt);
  }
  cout << ans << endl;
}

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  cout << fixed << setprecision(15);
  // freopen("temp.1", "r", stdin);
  solve();
  return 0;
}

Measured memory_bytes: 1792
n=int(input())
red=[-1]*(n*2)
blue=[-1]*(n*2)
ans=0

for i in range(0,n):
    a,b=map(int,input().split())
    red[a]=b

for i in range(0,n):
    a,b=map(int,input().split())
    blue[a]=b

for i in range(0,n*2):
    if blue[i]>=0:
        k=-1
        for j in range(0,i):
            if red[j]>=0 and red[j]<blue[i]:
                if k<0 or red[k]<red[j]:
                    k=j
        if k>=0:
            red[k]=-1
            ans+=1
            # print(k,i)

print(ans)


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

int main(){
  double n,m,ans=0;
  cin>>n;
  rep(i,n){
    cin>>m;
    m=1/m;
    ans+=m;
  }
  cout<<fixed<<setprecision(8);
  ans=1/ans;
  cout<<ans;
}


Measured memory_bytes: 3748
import sys
input = sys.stdin.readline
n = int(input())
m = []
for _ in range(2):
    m.append(list(map(int,input().split())))
ans = 0
for i in range(n):
    #print("------")
    #print(i)
    sx,sy = 0,0
    sum = 0
    j = 0
    while j < n :
        #print(sx,sy,j)
        sum += m[sx][sy]
        if j == i:
            if sx > 0:
                sy += 1
                j += 1
            else:
                sx += 1
        else:
            sy += 1
            j += 1
    ans = max(ans,sum)
print(ans)


Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
#define endl "\n"
#define debug(x) cerr << #x " = " << (x) << endl;
#define P(x) cerr << #x << endl;    
#define int long long
typedef pair<int, int> pii;
const int mod = 1000000007;

vector<int> z_function(string s) {
    int n = (int) s.length();
    vector<int> z(n);
    for (int i = 1, l = 0, r = 0; i < n; ++i) {
        if (i <= r)
            z[i] = min (r - i + 1, z[i - l]);
        while (i + z[i] < n && s[z[i]] == s[i + z[i]])
            ++z[i];
        if (i + z[i] - 1 > r)
            l = i, r = i + z[i] - 1;
    }
    return z;
}

int32_t main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout << fixed << setprecision(9);
    
    int n;
	cin >> n;
	string s;
	cin >> s;
	int glob = 0;
	for(int i = 0; i < n; ++ i)
	{
		vector<int> cur = z_function(s.substr(i));
		for(int j = 1; j < (int) cur.size(); ++ j)
		{
			glob = max(glob, min(cur[j], j));
		}
	}
    cout << glob << endl;
    
    return 0;
}






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

a = list(map(int, input().split()))
a.sort()

c = [0] * (10**6+1)
for i in a:
    c[i] += 1

uni = []
a = list(set(a))

for i in a:
    if c[i] == 1:
        uni.append(i)

b = [0 for _ in range(10**6+1)]

for i in a:
    for j in range(i*2, 10**6+1, i):
        b[j] = 1

cnt = 0
for i in uni:
    if b[i] == 0:
        cnt += 1

print(cnt)

Measured memory_bytes: 213136
import java.util.Scanner;

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

        int N = Integer.parseInt(sc.next());

        for (int i = 0; i < N; i++) {
            double x1 = Double.parseDouble(sc.next());
            double y1 = Double.parseDouble(sc.next());
            double r1 = Double.parseDouble(sc.next());

            double x2 = Double.parseDouble(sc.next());
            double y2 = Double.parseDouble(sc.next());
            double r2 = Double.parseDouble(sc.next());

            double xy = Math.sqrt(Math.pow(x2 - x1, 2) + Math.pow(y2 - y1, 2));
            double rs = r1 + r2;
            double rd = r1 - r2;

            if (xy > rs) {
                System.out.println("0");
            } else if (Math.abs(rd) <= xy && xy <= rs) {
                System.out.println("1");
            } else if (rd > 0) {
                System.out.println("2");
            } else {
                System.out.println("-2");
            }
        }
    }
}

Measured memory_bytes: 26196
import java.util.*;

public class Main {
		public static void main(String args[]) {
		Scanner input = new Scanner(System.in);
			String s = input.nextLine();
			boolean found = false;
			boolean[] arr = new boolean[26];
			for(int i = 0; i < s.length(); i++){
				arr[(int)s.charAt(i)-97] = true;
			}
			for(int i = 0; i < 26; i++){
				if(arr[i] == false){
					System.out.println((char) ( i + 97));
					found = true;
					break;
				}
			}
			
			if(!found){
				System.out.println("None");
			}
		}
}


Measured memory_bytes: 26176
# include <bits/stdc++.h>
using namespace std;
# define eps 1e-8
# define INF 1e20
# define pi  acos(-1.0)
# define MX  105
struct Node
{
    double t,v;
    double ev; //从终点的最大速度
}seg[MX];
 
int n;
double spd, ans;
 
void gogo(int x)
{
    double l=0, r=seg[x].t;
    double res = 0;
    while (l<r-eps) // <
    {
        double mid = (l+r)/2;
        if (mid + spd > seg[x].v-eps)
        {
            if ((seg[x].v - seg[x+1].ev) + mid < seg[x].t+eps)
            {
                res = mid;
                l = mid;
            }
            else r = mid;
        }
        else
        {
            if (mid + spd - (seg[x].t-mid) - seg[x+1].ev < -eps) //<=
            {
                res = mid;
                l = mid;
            }
            else r = mid;
        }
    }
 
    double jia, yun, jian;
    if (spd + res < seg[x].v)
    {
        jia = res;
        yun = 0;
        jian = seg[x].t - jia;
    }
    else
    {
        jia = seg[x].v - spd;
        yun = res - jia;
        jian = seg[x].t - jia - yun;
    }
    ans += 1.0/2.0*jia*jia + spd * jia;
    ans += yun * seg[x].v;
 
    if (res+spd < seg[x].v)
    {
        ans += -1.0/2.0*jian*jian +  (spd+jia) * jian;
        spd = spd + jia - jian;
    }
    else
    {
        ans += -1.0/2.0*jian*jian +  seg[x].v * jian;
        spd = seg[x].v - jian;
    }
 
}
 
int main()
{
    scanf("%d",&n);
    for (int i=1;i<=n;i++)
        scanf("%lf",&seg[i].t);
    for (int i=1;i<=n;i++)
        scanf("%lf",&seg[i].v);
    spd=0.0;
    for (int i=n;i>=1;i--)
    {
        if (spd+seg[i].t < seg[i].v+eps) //<=
            spd += seg[i].t;
        else
            spd = seg[i].v;
        seg[i].ev = spd;
    }
    ans = 0;
    spd = 0;
    seg[n+1] = (Node){0.0, 0.0, 0.0};
 
    for (int i=1;i<=n;i++)
    {
        gogo(i);
    }
    printf("%.5f\n",ans);
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define ll long long 
#define endl "\n"
#define pb push_back
#define f(i,n) for(i=0;i<n;i++)
#define F(i,a,b) for(i=a;a<=b;i++)
#define arr(a,n) for( i=0;i<n;i++)cin>>a[i];
#define fi first
#define se second
#define mp make_pair
#define mod 1000000007
#define YES cout<<"YES"<<endl;
#define Yes cout<<"Yes"<<endl;
#define NO cout<<"NO"<<endl;
#define No cout<<"No"<<endl;
#define yes cout<<"yes"<<endl;
#define no cout<<"no"<<endl;
#define vi vector<ll>
#define ed end()
#define bg begin()
#define sz size()
#define ln length()
#define s() sort(a,a+n);
#define sr() sort(a,a+n,greater<ll>());
#define v()  sort(v.begin(),v.end());
#define vr() sort(v.begin(),v.end(),greater<ll>());
#define mod 1000000007
#define fast() ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
ll gcd(ll a, ll b){if(!b)return a;return gcd(b, a % b);}
ll power(ll x,ll y,ll p){ll res=1;x%=p;while(y>0){if(y&1)res=(res*x)%p;y=y>>1;x=(x*x)%p;}return res;}
int main() {

fast();

{
  int a,b,c,d;
  cin>>a>>b>>c>>d;
  if((a+b)>(c+d))
  {
    cout<<"Left"<<endl;
  }
 
   else  if((a+b)==(c+d))
    {
      cout<<"Balanced"<<endl;
    }
    else
    {
      cout<<"Right"<<endl;
    }
 
  
  
  

}
return 0;
}


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

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

  vector<int> cnts(N, 0);
  for (int i = 0; i < N; i++) {
    int A;
    cin >> A;

    cnts[A - 1]++;
  }

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

  int cnt = 0;
  for (int i = 0; i < N; i++) {
    if (cnts[i] == 0) {
      continue;
    }

    if (N - i <= K) {
      break;
    }

    cnt += cnts[i];
  }

  cout << cnt << endl;

  return 0;
}


Measured memory_bytes: 1024
#include <iostream>
#include <string>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <numeric>
#include <vector>
#include <queue>
#include <map>
typedef unsigned long long ull;
typedef long long ll;
#define MAX 10005
using namespace std;

int main() {
  string s;
  cin >> s;
  int count=0;
  for(int i=0;i<s.size();i++) {
    if(s[i]=='-') count--;
    else count++;
  }
  cout << count << endl;
  return 0;
}

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


int main(){
double L;
cin >> L;
double ans = L*L*L/27;
printf("%.10f\n",ans);


return 0;

}

Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<cmath>
#include<stack>
#include<queue>
#include<deque>
#include<map>
#include<set>
using namespace std;
typedef long long ll;
typedef vector<int> VI;
#define FOR(i,a,n) for(int (i)=(a);(i)<(n);(i)++)
#define eFOR(i,a,n) for(int (i)=(a);(i)<=(n);(i)++)
#define SORT(i) sort((i).begin(),(i).end())
#define rSORT(i,a) sort((i).begin(),(i).end(),(a))
constexpr auto INF = 1000000000;
constexpr auto LLINF = 1LL << 62;
constexpr auto mod = 1000000007;
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; }

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

    int n;
    cin >> n;
    VI p(n);
    FOR(i, 0, n)cin >> p[i];

    int ans = 0;
    FOR(i, 1, n - 1) {
        if ((p[i - 1] < p[i] && p[i] < p[i + 1]) || (p[i - 1] > p[i] && p[i] > p[i + 1])) {
            ans++;
        }
    }
    cout << ans << endl;
}

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

struct DSU {
    int n;
    vector<int> par, sz;

    void init(int _n) {
        n = _n;

        par.resize(n + 1);
        sz.resize(n + 1);

        for(int i = 1; i <= n; i++){
            par[i] = i;
            sz[i] = 1;
        }
    }

    int getRoot(int u) {
        if(par[u] == u) {
            return u;
        }

        return par[u] = getRoot(par[u]);
    }

    bool unite(int u, int v) {
        u = getRoot(u);
        v = getRoot(v);

        if(u == v) {
            return false;
        }

        par[u] = v;
        sz[v] += sz[u];

        return true;
    }

    bool same(int u, int v) {
        return getRoot(u) == getRoot(v);
    }
};

const int maxN = 2e5 + 55;

int n, m, k;

int f[maxN];
set<int> g[maxN];

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

    cin >> n >> m >> k;

    DSU dsu;

    dsu.init(n);

    for(int i = 0; i < m; i++){
        int u, v;   cin >> u >> v;

        g[u].insert(v);
        g[v].insert(u);

        dsu.unite(u, v);
    }

    for(int i = 1; i <= n; i++){
        //cerr << dsu.sz[dsu.getRoot(i)] << ' ';
        f[i] = dsu.sz[dsu.getRoot(i)] - (int)g[i].size() - 1;
    }

    for(int i = 0; i < k; i++){
        int u, v;   cin >> u >> v;

        if(dsu.same(u, v)) {
            f[u]--; f[v]--;
        }
    }

    for(int i = 1; i <= n; i++){
        cout << f[i] << ' ';
    }
    cout << '\n';

    return 0;
}


Measured memory_bytes: 21120
#include<iostream>
#include<vector>
#include<algorithm>
#include<math.h>
#include<string>
#include<map>

using namespace std;

vector<int>to[200005];
vector<int>ans;

void dfs(int v, int p = -1) {
	for (int u : to[v]) {
		if (u == p) {
			continue;
		}
		ans[u] += ans[v];
		dfs(u, v);
	}
}
int main(void) {
	int n, q;
	cin >> n >> q;
	for (int i = 0; i < n-1; i++) {
		int a, b;
		cin >> a >> b;
		--a;
		--b;
		to[a].push_back(b);
		to[b].push_back(a);
	}
	ans.resize(n);
	for (int i = 0; i < q; i++) {
		int p, x;
		cin >> p >> x;
		--p;
		ans[p] += x;
	}
	dfs(0);
	for (int i = 0; i < n; i++) {
		cout << ans[i] << endl;
	}
	return 0;
}


Measured memory_bytes: 23552
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
#define all(x) (x).begin(),(x).end()
#define pll pair<ll,ll>
#define pii pair<int,int>
#define rep(i,n) for(int i=0;i<n;i++)
#define sz(x) ((ll)(x).size())
#define pb push_back
#define mp make_pair
#define bit(n) (1LL<<(n))
#define F first
#define S second
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};
const ll INF = 1LL<<60;
const ll mod = (int)1e9 + 7;

vector<ll> divisor(ll n) {
  vector<ll> ret;
  for(ll i = 1; i * i <= n; i++) {
    if(n % i == 0) {
      ret.push_back(i);
      if(i * i != n) ret.push_back(n / i);
    }
  }
  return (ret);
}

int main() {
    int x;
    cin >> x;
    while(true){
        if(sz(divisor(x))==2){
            cout << x;
            return 0;
        }
        x++;
    }

    


}

/*



 */


Measured memory_bytes: 256
package main

import "fmt"

func main() {

	var a int
	fmt.Scan(&a)

	list := make([]int, a)
	for i := 0; i < a; i++ {
		fmt.Scan(&list[i])
	}

	h := 0
	for i := 0; i < a; i++ {
		for j := i + 1; j < a; j++ {
			h += list[i] * list[j]
		}
	}
	fmt.Println(h)
}


Measured memory_bytes: 512
//#define _GLIBCXX_DEBUG

#include<bits/stdc++.h>
using namespace std;
const int INF= 1e9+5;
typedef long long ll;

int main(){
  int r;
  cin>>r;
  if(r<1200)cout<<"ABC"<<endl;
  else if(r<2800)cout<<"ARC"<<endl;
  else cout<<"AGC"<<endl;
}
  

Measured memory_bytes: 256
#include"bits/stdc++.h"
#include<unordered_set>
#include<unordered_map>
#include<random>
using namespace std;
typedef long long ll;
const ll MOD = 1'000'000'007LL; // 998'244'353LL
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(), (x).end()
#define rep(i, n) for(int (i)=0; (i)<(n); (i)++)
int dx[4]={ 1,0,-1,0 };
int dy[4]={ 0,1,0,-1 };

int A, B, C, D, K;

signed main(){
    cin >> A >> B >> C >> D >> K;
    int X = 60*A+B;
    int Y = 60*C+D;
    cout << Y-X-K << endl;
}


Measured memory_bytes: 3632
import math
def kock(n, p1, p2):
 if n == 0:
  return

 #p1.p2??????s,t,u????¨????
 sx = (2 * p1[0] + 1 * p2[0]) / 3
 sy = (2 * p1[1] + 1 * p2[1]) / 3
 s = [sx, sy]
 tx = (1 * p1[0] + 2 * p2[0]) / 3
 ty = (1 * p1[1] + 2 * p2[1]) / 3
 t = [tx, ty]
 ux = (tx-sx) * math.cos(math.radians(60)) - (ty-sy) * math.sin(math.radians(60)) + sx
 uy = (tx-sx) * math.sin(math.radians(60)) + (ty-sy) * math.cos(math.radians(60)) + sy
 u = [ux, uy]

 kock(n-1,p1,s)
 print(" ".join(['{:.5f}'.format(i) for i in s]))
 kock(n-1,s,u)
 print(" ".join(['{:.5f}'.format(i) for i in u]))
 kock(n-1,u,t)
 print(" ".join(['{:.5f}'.format(i) for i in t]))
 kock(n-1,t,p2)

n = float(input())
print("0.00000 0.00000")
kock(n, [0,0], [100,0])
print("100.00000 0.00000")

Measured memory_bytes: 7804
#include<iostream>
#include<algorithm>
#include<cmath>
#include<map>
#include<stdio.h>
#include<vector>
using namespace std;
#define int long long
#define rep(s,i,n) for(int i=s;i<n;i++)
#define c(n) cout<<n<<endl;
#define ic(n) int n;cin>>n;
#define sc(s) string s;cin>>s;
#define mod 1000000007
#define inf 1000000000000000007
#define f first
#define s second
#define mini(c,a,b) *min_element(c+a,c+b)
#define maxi(c,a,b) *max_element(c+a,c+b)
//printf("%.12Lf\n",c);
int keta(int x){
	rep(0,i,30){
		if(x<10){
			return i+1;
		}
		x=x/10;
	}
}
int gcd(int x,int y){
	int aa=x,bb=y;
	rep(0,i,1000){
		aa=aa%bb;
		if(aa==0){
			return bb;
		}	
		bb=bb%aa;
		if(bb==0){
			return aa;
		}
	}
}	
int lcm(int x,int y){
	int aa=x,bb=y;
	rep(0,i,1000){
		aa=aa%bb;
		if(aa==0){
			return x/bb*y;
		}	
		bb=bb%aa;
		if(bb==0){
			return x/aa*y;
		}
	}
}
bool p(int x){
	if(x==1)return false;
	rep(2,i,sqrt(x)+1){
		if(x%i==0&&x!=i){
			return false;
		}
	}	
	return true;
}
int primes[200];
int prime[1000000];
int pr[100000];
int el[314514],wl[314514];
int er[314514],wr[314514];
int a[114514];
int b[214514],c[214514];
int k[11];
int s[11][11];
int pp[11];
int ss[1919][11];
signed main(){
	ic(n) ic(m)
	int k=1;
	rep(0,i,100){
		if(k>n){
			c(i)
			return 0;
		}
		k*=m;
	}	
}	

Measured memory_bytes: 256
package main

import (
	"fmt"
	"sort"
	"strings"
)

type city struct {
	prefecture int
	position   int
	year       int
}

type cities []*city

type cMap map[int]cities

func main() {
	var (
		n, m int
	)
	fmt.Scanf("%d %d\n", &n, &m)
	h := make(cMap)
	for i := 0; i < m; i++ {
		var x, y int
		fmt.Scanf("%d %d\n", &x, &y)
		_, exists := h[x]
		if !exists {
			h[x] = cities{{prefecture: x, year: y, position: i}}
		} else {
			h[x] = append(h[x], &city{prefecture: x, year: y, position: i})
		}
	}

	results := make([]string, m)

	for _, v := range h {
		sort.Sort(v)
		for idx, ci := range v {
			results[ci.position] = fmt.Sprintf("%06d%06d", ci.prefecture, idx+1)
		}
	}
	fmt.Println(strings.Join(results, "\n"))
}

func (c cities) Len() int {
	return len(c)
}

func (c cities) Swap(i, j int) {
	c[i], c[j] = c[j], c[i]
}

func (c cities) Less(i, j int) bool {
	return c[i].year < c[j].year
}


Measured memory_bytes: 37376
n= int(input())
d= list(map(int,input().split()))
if n==1:print(d[0])
else:
    ddict={}
    for sd in d:ddict[sd]=ddict.get(sd,0)+1
    if 3<=max(ddict.values()):
        print(0);exit()
    elif 0 in ddict.keys():
        print(0);exit()
    elif 12 in ddict.keys() and ddict[12]==2:
        print(0);exit()
    else:
        fixtime=[0,24]
        ktime=[]
        for akey in ddict:
            if ddict[akey]==2:
                fixtime.append(akey)
                fixtime.append(24-akey)
            elif ddict[akey]==1:
                if akey==12:fixtime.append(12)
                else:ktime.append((akey,24-akey))
        gmin= min(d)
        skouho=sorted(fixtime)
        for i in range(len(skouho)-1):gmin=min(gmin,skouho[i+1]-skouho[i])
        if len(ktime)==0:print(gmin)
        else:
            longtime=0
            for i in range(2**len(ktime)):
                newtime=[]
                tempmin=24
                for j in range(len(ktime)):newtime.append(ktime[j][i>>j&1])
                temptime=sorted(fixtime+newtime)
                for k in range(len(temptime)-1):
                    tempmin=min(tempmin,temptime[k+1]-temptime[k])
                longtime=max(longtime,tempmin)
            print(longtime)

Measured memory_bytes: 9284
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using Graph = vector<vector<int>>;
#define rep(i,m,n) for(int (i)=(int)(m);(i)<(int)(n);++(i))
#define rREP(i,m,n) for(int (i)=(n)-1;(i)>=(m);--(i))
#define all(x) (x).begin(),(x).end()
#define out(y,x,h,w) (y)<0||(x)<0||(y)>=(h)||(x)>=(w)
constexpr int INF = 1000000001;
constexpr ll mod = 1000000007;
constexpr double PI = 3.1415926535897932;

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;
}
inline void init() {
	cin.tie(nullptr); cout.tie(nullptr);
	ios::sync_with_stdio(false);
	cout << fixed << setprecision(15);
}

int main() {
	init();

	int K; cin >> K;
	int A, B; cin >> A >> B;
	rep(i, A, B + 1) {
		if (i % K == 0) {
			cout << "OK" << "\n";
			return 0;
		}
	}
	cout << "NG" << "\n";

	return 0;
}

Measured memory_bytes: 3652
#include<bits/stdc++.h>
#define For(i,j,k) for (int i=(int)(j);i<=(int)(k);i++)
#define Rep(i,j,k) for (int i=(int)(j);i>=(int)(k);i--)
#define pii pair<int,int>
#define fi first
#define se second
#define PB push_back
using namespace std;

int main(){
	int n,x=0,y;
	scanf("%d",&n);
	For(i,1,n) scanf("%d",&y),x^=y;
	puts(x?"No":"Yes");
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
int main(){
  string s;cin>>s;
  ll ans=0,k=1<<(s.size()-1),l=k;
  for(ll i=s.size()-1;i>=0;i--) ans+=(s[i]-'0')*k,k=k*5+l/2;
  cout<<ans<<endl;
}

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

#define int long long
const int N = 1e3 + 10 ;
char ch[N][N] ;
int dx[4] = {0 , 0 , -1 , 1} ;
int dy[4] = {-1 , 1 , 0 , 0} ;
map<pair<int,int> , pair<int,int>> parent ;
map<pair<int,int> , map<pair<int,int> , int>> g ;
int n , m ;

void dfs(pair<int,int> cur , pair<int,int> p){
	for(int i = 0 ; i < 4 ; i++){
		int cx = cur.first + dx[i] ;
		int cy = cur.second + dy[i] ;
		if(cx < 0 || cx >= n || cy < 0 || cy >= m || ch[cx][cy] == '#') continue ; 
		if(parent.count({cx,cy})) continue ;
		parent[{cx , cy}] = p ;
		dfs({cx , cy} , p) ;
	}
}

int	bfs(pair<int,int> s , pair<int,int> d){
	queue<pair< pair<int,int>  , int>> q ;
	q.push({s , 0}) ;
	map<pair<int,int> , int> visited ;
	visited[s] = true ;
	while(q.size()){
		auto [cur , dis] = q.front() ;
		q.pop() ;
		if(cur == d) return dis;
		for(auto i : g[cur]){
				if(visited[i.first]) continue ;
				visited[i.first] = 1 ;
				q.push({i.first , dis + 1}) ;
		}
	}
	return -1 ;
}

int32_t main(){
	cin >> n >> m ;
	pair<int,int> s , d ;
	cin >> s.first >> s.second ;
	cin >> d.first >> d.second ;
	s.first-- , s.second-- ;
	d.first-- , d.second-- ;
	for(int i = 0 ; i < n ; i++){
		for(int j = 0 ; j < m ; j++){
			cin >> ch[i][j] ;
		}
	}
	for(int i = 0  ; i < n ; i++){
		for(int j = 0 ; j < m ; j++){
			if(ch[i][j] == '#') continue ;
			if(parent.count({i,j})) continue ;
			dfs({i,j} , {i,j}) ;
		}
	}
	for(int i = 0 ; i < n ; i++){
		for(int j = 0 ; j < m ; j++){
			if(!parent.count({i,j})) parent[{i,j}] = {i,j} ;
		}
	}
	for(int i = 0 ; i < n ; i++){
		for(int j = 0 ; j < m ; j++){
			int p = i - 2 , q = j - 2 ;
			if(ch[i][j] == '#') continue ;
			for(int f = p ; f < p + 5 ; f++){
				for(int s = q ; s < q + 5 ; s++){
					if(f < 0 || f >= n || s < 0 || s >= m) continue ;
					if(ch[f][s] == '#') continue ;
					g[parent[{i,j}]][parent[{f,s}]] = 1 ;
				}
			}
		} 
	}
	cout << bfs(parent[s],parent[d]) ;
	return 0 ;
}

Measured memory_bytes: 142660
#include "bits/stdc++.h"
using namespace std;
#define int long long
#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 FOR(i, s, n) for (int i = s; i < (int)n; ++i)
#define RFOR(i, s, n) for (int i = (int)n - 1; i >= s; --i)
#define ALL(a) a.begin(), a.end()
#define IN(a, x, b) (a <= x && x < b)
template<class T>inline void out(T t){cout << t << "\n";}
template<class T,class... Ts>inline void out(T t,Ts... ts){cout << t << " ";out(ts...);}
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;}
constexpr int INF = 1e18;



signed main(){
	int N;
	cin >> N;
	vector<int>a(N);
	vector<int>cnt(1000100);
	REP(i,N){
		cin >> a[i];
		++cnt[a[i]];
	}
	FOR(i,1,1000100){
		for(int j = i + i;j < 1000100;j += i){
			cnt[j] += cnt[i];
			//out(j);
		}
	}
	int ans = 0;
	REP(i,N){
		if(cnt[a[i]]==1){
			++ans;
		}
	}
	out(ans);
}

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

using namespace std;

int main()
{
	int n, m, k, mid, num, size, l = 0, r = INT_MAX / 4;
	
	scanf("%d %d", &n, &m);
	
	vector<int> v;
	
	for(int i = 0; i < n; i++)
	{
		scanf("%d", &k);
		v.push_back(k);
	}
	
	while(r-l > 1)
	{
		mid = (l + r) / 2;
		num = 0;
		
		for(int i = 0; i < m; i++)
		{
			size = mid;
			
			for(;;)
			{
				if(num == n)
					break;
				if(size - v[num] < 0)
					break;
				size -= v[num++];
			}
			if(num == n)
				break;
		}
		if(num == n)
			r = mid;
		else
			l = mid;
	}
	
	printf("%d\n", l+1);
	
	return 0;
}


Measured memory_bytes: 3528
package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
)

type edge struct {
	next   int
	weight int
}

var (
	color []int
	graph [][]edge
)

func dfs(now, prev, d int) {
	if d%2 == 0 {
		color[now] = 0
	} else {
		color[now] = 1
	}

	for _, e := range graph[now] {
		if e.next == prev {
			continue
		}
		dfs(e.next, now, d+e.weight)
	}
}

func main() {
	n := getInt()
	graph = make([][]edge, n)
	for i := range graph {
		graph[i] = make([]edge, 0)
	}
	for i := 0; i < n-1; i++ {
		a, b, w := getInt()-1, getInt()-1, getInt()
		graph[a] = append(graph[a], edge{b, w})
		graph[b] = append(graph[b], edge{a, w})
	}
	color = make([]int, n)
	for i := range color {
		color[i] = -1
	}

	dfs(0, -1, 0)

	for i := range color {
		fmt.Println(color[i])
	}
}

// -----------------------------------------

var sc = bufio.NewScanner(os.Stdin)

func init() {
	// tmp := 200001
	// sc.Buffer(make([]byte, tmp), tmp)
	sc.Split(bufio.ScanWords)
}

func getInt() int {
	i, err := strconv.Atoi(getString())
	if err != nil {
		panic(err)
	}
	return i
}

func getString() string {
	sc.Scan()
	s := sc.Text()
	return s
}


Measured memory_bytes: 25344
#include<bits/stdc++.h>
using namespace std;
#define N 1111116

int n,k,tmp;
char s[N];
queue<int> q;

int read(){
	int x=0,f=1;char ch=getchar();
	for (;!isdigit(ch);ch=getchar()) if (ch=='-')  f=-f;
	for (;isdigit(ch);ch=getchar()) x=x*10+ch-'0';
	return x*f;
}

int main(){
	n=read();k=read();scanf(" %s",s);
	for (int i=0;i<n;i++) q.push(s[i]-'A');
	for (int i=1;i<=k&&i<=2*n+(k&1);i++)
		if (q.front()==tmp) q.front()^=1;
		else q.pop(),q.push(tmp^=1);
	for (;!q.empty();q.pop())
		printf(q.front()==tmp?"A":"B");
	printf("\n");return 0;
}

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

bool IsOneBit(int bits, int i) {
	return (bits & (1 << i)) > 0;
}
int main() {
	int H, W, K;
	cin >> H >> W >> K;
	vector<vector<int>>Map(H, vector<int>(W));
	for (int i = 0; i < H; i++) {
		for (int j = 0; j < W; j++) {
			char c;
			cin >> c;
			Map[i][j] = (c == '#');
		}
	}
	int ans = 0;
	for (int b1 = 0; b1 < (1 << H); b1++) {
		for (int b2 = 0; b2 < (1 << W); b2++) {
			int num = 0;
			for (int i = 0; i < H; i++) {
				if (IsOneBit(b1, i)) continue;
				for (int j = 0; j < W; j++) {
					if (IsOneBit(b2, j)) continue;
					if (Map[i][j]) num++;
				}
			}
			if (num == K) ans++;
		}
	}
	cout << ans << endl;
}

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

using namespace std;

int main()
{
    int n, a[100010];
    cin >> n;
    for (int i = 0; i < n; i++) cin >> a[i];

    int ans = 1, f = 0;
    for (int i = 0; i < n - 1; i++) {
        if (a[i] > a[i + 1]) {
            if (f == -1) ans++, f = 0;
            else f = 1;
        }
        else if (a[i] < a[i + 1]) {
            if (f == 1) ans++, f = 0;
            else f = -1;
        }
    }
    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 640
N=int(input())
h=[int(i) for i in input().split()]
cost = [-1]*N
cost[0]=0
cost[1]=abs(h[1]-h[0])
for i in range(2,N):
    cost[i] = min(cost[i-2]+abs(h[i]-h[i-2]), cost[i-1]+abs(h[i]-h[i-1]))
print(cost[-1])

Measured memory_bytes: 52208
while 1:
	m, f, r = map(int, raw_input().split())
	if m == -1 and f == -1 and r == -1:
		break
	else:
		if m == -1 or f == -1:
			print 'F'
		elif m+f >= 80:
			print 'A'
		elif m+f >= 65 and m+f < 80:
			print 'B'
		elif m+f >= 50 and m+f < 65:
			print 'C'
		elif m+f >= 30 and m+f < 50:
			if r >= 50:
				print 'C'
			else:
				print 'D'
		else:
			print 'F'

Measured memory_bytes: 4636
use std::io::prelude::*;

fn input<T>() -> T
where
    T: std::str::FromStr,
{
    let stdin = std::io::stdin();
    let token = stdin
        .lock()
        .bytes()
        .map(|c| c.unwrap() as char)
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .collect::<String>();
    token.parse().ok().unwrap()
}

fn main() {
    let n = input::<i64>();
    let i = input::<i64>();

    println!("{}", n - i + 1);
}


Measured memory_bytes: 4352
#include <cassert>

#include <cctype>
#include <cerrno>
#include <cfloat>
#include <ciso646>
#include <climits>
#include <clocale>
#include <cmath>
#include <csetjmp>
#include <csignal>
#include <cstdarg>
#include <cstddef>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <ccomplex>
#include <cfenv>
#include <cinttypes>
#include <cstdbool>
#include <cstdint>
#include <ctgmath>
#include <cwchar>
#include <cwctype>

// C++
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
#include <array>
#include <atomic>
#include <chrono>
#include <condition_variable>
#include <forward_list>
#include <future>
#include <initializer_list>
#include <mutex>
#include <random>
#include <ratio>
#include <regex>
#include <scoped_allocator>
#include <system_error>
#include <thread>
#include <tuple>
#include <typeindex>
#include <type_traits>
#include <unordered_map>
#include <unordered_set>
//#include <boost/foreach.hpp>
//#include <boost/range/algorithm.hpp>
#define rep(i,j,k) for(int i=(int)j;i<(int)k;i++)
#define ll long long
#define Sort(v) sort(all(v))
#define INF 1e9
#define LINF 1e18
#define END return 0
#define pb push_back
#define se second
#define fi first
#define pb push_back
#define all(v) (v).begin() , (v).end()
#define MP make_pair
#define MOD 1000000007LL
#define int long long
using namespace std;
int day[12]={31,28,31,30,31,30,31,31,30,31,30,31};
struct edge{int to,cost;};
typedef pair<int,int> P;

bool isupper(char c){if('A'<=c&&c<='Z')return 1;return 0;}
bool islower(char c){if('a'<=c&&c<='z')return 1;return 0;}
bool isPrime(int x){if(x==1)return 0;if(x==2)return 1;if(x%2==0)return 0;for(int i=3;i*i<=x;i++)if(x%i==0)return 0;return 1;}
bool iskaibun(string s){for(int i=0;i<s.size()/2;i++)if(s[i]!=s[s.size()-i-1])return 0;return 1;}

vector<int> v;
vector<vector<int>> dp;

int  rec(int l,int r){
    if(dp[l][r]!=-1)return dp[l][r];
    if(abs(r-l)<=1)return 0;
    int res=0;
    if(abs(v[l]-v[r-1])<=1 && rec(l+1,r-1)==r-l-2){
        res=r-l;
    }
    for(int i=l+1;i<=r-1;i++){
        res=max(res,rec(l,i)+rec(i,r));
    }
    return dp[l][r]=res;
}


signed main (){
    int n;
    while(cin>>n && n){
        v.resize(n);
        dp.resize(n+1,vector<int>(n+1,-1));
        rep(i,0,n)cin>>v[i];
        rec(0,n); 
        cout<<dp[0][n]<<endl;
        v.clear();
        dp.clear();
    }  


}
/*
1-2
0.5-2

010
01110
00111
000000111
*/



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

using VS = vector<string>;    using LL = long long;
using VI = vector<int>;       using VVI = vector<VI>;
using PII = pair<int, int>;   using PLL = pair<LL, LL>;
using VL = vector<LL>;        using VVL = vector<VL>;

#define ALL(a)  begin((a)),end((a))
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define SZ(a) int((a).size())
#define SORT(c) sort(ALL((c)))
#define RSORT(c) sort(RALL((c)))
#define UNIQ(c) (c).erase(unique(ALL((c))), end((c)))
#define FOR(i, s, e) for (int(i) = (s); (i) < (e); (i)++)
#define FORR(i, s, e) for (int(i) = (s); (i) > (e); (i)--)
#define debug(x) cerr << #x << ": " << x << endl
const int INF = 1e9;                          const LL LINF = 1e16;
const LL MOD = 1000000007;                    const double PI = acos(-1.0);
int DX[8] = { 0, 0, 1, -1, 1, 1, -1, -1 };    int DY[8] = { 1, -1, 0, 0, 1, -1, 1, -1 };

/* -----  2018/03/03  Problem: code-festival-2017-final_c / Link: https://cf17-final.contest.atcoder.jp/tasks/cf17_final_c?lang=en  ----- */
/* ------問題------

XXXX年のCODE FESTIVALには、世界中から高橋君を含めて N+1 人の参加者が集まりました。
高橋君の都市と他の N 人の都市の時刻の差を調べてみたところ、i 番目の人の都市との時刻の差は Di 時間でした。 ただし 2 つの都市について、片方の都市で 0 時の瞬間にもう一方の都市で d 時であるようなとき、これらの都市の時刻の差は min(d,24−d) であるものとします。 ここで、時刻の表記には 24 時間表記を用いるものとします。 つまり、例えば高橋君の都市で 0 時の瞬間には i 番目の人の都市は Di 時または 24−Di 時のいずれかとなります。
高橋君は次に、N+1 人のうちの全ての 2 人組についてその人の都市どうしの時刻の差を書き出し、それらの時刻の差のうちの最小値を s としました。
s として考えられる最大値を求めて下さい。

-----問題ここまで----- */
/* -----解説等-----



----解説ここまで---- */

LL N;

LL ans = 0LL;

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

	cin >> N;
	VI a(N);
	VI cnt(13, 0);

	FOR(i, 0, N) {
		cin >> a[i];
		cnt[a[i]]++;
	}
	cnt[0]++;
	FOR(i, 0, 13) {
		if (cnt[i] > 2) {
			cout << 0 << endl;
			return 0;
		}
	}

	if (cnt[0] > 1 || cnt[12] > 1) {
		cout << 0 << endl;
		return 0;
	}
	VI base(24, false);
	base[0] = true;
	if (cnt[12] == 1) {
		base[12] = true;
	}
	FOR(i, 0, 13) {
		if (cnt[i] == 2) {
			base[i] = base[24 - i] = true;
		}
	}
	ans = 0;
	FOR(i, 0, (1 << 11)) {
		VI used(48,0);
		FOR(i, 0, 24) {
			used[i] = base[i];
		}
		FOR(j, 0, 11) {
			if (cnt[j + 1] != 1) continue;
			if ((i >> j) & 1) {
				used[j + 1] = true;
			}
			else {
				used[24 - (j + 1)] = true;
			}
		}
		FOR(j, 0, 24) used[j + 24] = used[j];
		int l = 0;
		int tans = INF;
		FOR(r, 1, 48) {// 2周
			if (used[r]) {
				int t = min(r - l, 24 - (r - l));
				tans = min(tans, t);
				l = r;
			}
		}
		ans = max(ans, (LL)tans);
	}
	cout << ans << endl;


	return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <map>
#include <set>
#include <vector>
#include <queue>
#include <math.h>

using namespace std;
typedef pair<int, int> pii;
typedef pair<int, long double> pild;
typedef pair<long double, int> pldi;

void solve();

int main() {
	solve();
	return 0;
}

//////////////////////////////////////////////////
//////////////////////////////////////////////////
//素数判定
//O(√n)
bool isPrime(int n) {
	for (int i = 2; i <= floor(sqrt(n)); i++) {
		if (n%i == 0)return false;
	}
	return true;
}

//n未満の自然数のでのエラトステネスの篩
//arr[n]=true -> 素数
//O(nlog(logn)) , 実質O(n)
bool* eratosthenes(int n) {
	bool* array = new bool[n];
	for (int i = 0; i < n; i++)array[i] = true;
	for (int i = 2; i < n; i++) {
		if (!array[i])continue;
		int t = 2*i;
		while (t < n) {
			array[t] = false;
			t += i;
		}
	}
	array[0] = false;
	array[1] = false;
	return array;
}

int c[100000 + 1];
vector<int> v;

void solve() {
	bool* arr = eratosthenes(100000+1);
	for (int n = 0; n <= 100000; n++) {
		if (n % 2 == 0)c[n] = 0;
		else {
			if (arr[n] && arr[(n + 1) / 2])c[n] = 1;
			else c[n] = 0;
		}
	}
	for (int n = 1; n <= 100000; n++) c[n] += c[n - 1];
	int Q;
	cin >> Q;
	v.resize(Q);
	for (int q = 0; q < Q; q++) {
		int l, r;
		cin >> l >> r;
		v[q] = c[r] - c[l - 1];
	}
	for (auto itr = v.begin(); itr != v.end(); itr++)cout << *itr << endl;
	delete arr;
	return;
}

Measured memory_bytes: 1536
n,k=map(int,input().split())
a=list(map(int,input().split()))
 
c=[[0 for _ in range(2)] for _ in range(64)]
 
for i in range(n):
    for j in range(60):
        c[j][a[i]>>j&1] += 1
x=0
for i in range(59,-1,-1):
    if(c[i][0] > c[i][1] and x+(1<<i) <= k):
        x += 1<<i
 
sum = 0
for i in range(n):
    sum += a[i]^x
print(sum)

Measured memory_bytes: 14620
#include <iostream> // cout, endl, cin
#include <string> // string, to_string, stoi
#include <vector> // vector
#include <algorithm> // min, max, swap, sort, reverse, lower_bound, upper_bound
#include <utility> // pair, make_pair
#include <tuple> // tuple, make_tuple
#include <cstdint> // int64_t, int*_t
#include <cstdio> // printf
#include <map> // map
#include <queue> // queue, priority_queue
#include <set> // set
#include <stack> // stack
#include <deque> // deque
#include <unordered_map> // unordered_map
#include <unordered_set> // unordered_set
#include <bitset> // bitset
#include <cctype> // isupper, islower, isdigit, toupper, tolower
#define _GLIBCXX_DEBUG // check []
#define DIVISOR 1000000007

using namespace std;
typedef pair<int,int> pii;
typedef pair<int64_t, int64_t> pII;

template<typename T>
void cins(vector<T>& arr) { for(T& e: arr) cin >> e; }

#ifdef DEBUG
#define debug(fmt, ...) \
    printf("[debug: %s] " fmt, __func__, __VA_ARGS__)
#define ps(arr) \
    debug("size %ld: ", arr.size()); \
    for(auto e: arr) cout << e << " "; \
    cout << endl;
#else
#define debug(fmt, ...)
#define ps(arr)
#endif

int power10(int num) {
    if(num == 0) return 0;
    int ans = 1;
    while(num--) {
        ans *= 10;
    }
    return ans;
}

int main(void) {
    int num, qs;
    cin >> num >> qs;
    vector<pii> queries(qs);
    for(int i = 0; i < qs; i++) {
        int s, c;
        cin >> s >> c;
        queries[i] = make_pair(s, c);
    }
    int ans = -1;
    for(int n = power10(num-1); n < power10(num); n++) {
        int flag = 1;
        for(int k = 0; k < qs; k++) {
            int val = n;
            pii q = queries[k];
            int s = num+1-q.first; // power10(s)
            while(--s) {
                val /= 10;
            }
            val %= 10;
            if(val != q.second) { flag = 0; break; }
        }
        if(flag) { ans = n; break; }
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 3628
#include <cstdio>
#include <vector>
#include <cmath>
#include <algorithm>
using namespace std;

int rank(int num){
	int a = 0;
	
	while(num > 0){
		num /= 10;
		a++;
	}
	
	return a;
}

int main(){
	int n, m, res;
	vector<int> a;
	vector<int> b;
	
	scanf("%d", &n);
	for(int i = 0; i < n; i++){
		scanf("%d", &m);
		a.push_back(m);
		if(a.size() > 4){
			sort(a.begin(), a.end());
			a.pop_back();
		}
	}
	
	sort(a.begin(), a.end());
	
	for(int i = 0; i < a.size(); i++){
		for(int j = 0; j < a.size(); j++){
			if(i == j) continue;
			res = a[i];
			res *= pow(10, rank(a[j]));
			res += a[j];
			b.push_back(res);
		}
	}
	
	sort(b.begin(), b.end());
	
	printf("%d\n", b[2]);
	
	return 0;
}

Measured memory_bytes: 1092
#include <bits/stdc++.h>
using namespace std;
 
int main() {
int N,M;
  cin>>N;
  M = N;
  int sum = 0;
  while(N > 0){
    sum = sum + N%10;
    N /= 10;
  }
  if(M%sum == 0){
  cout<<"Yes";
  }
  else{
  cout<<"No";
  }
}

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

int main() {
    ll X;
    cin >> X;
    vector<ll> va,vb;
    ll a, b;
    rep(i, -200, 200){
        va.push_back(pow(i,5));
        vb.push_back(pow(i,5));
    }
    rep(i, 0, 401){
        rep(j, 0, 401){
            if(va[i]-vb[j] == X){
                a = i-200;
                b = j-200;
                goto end;
            }
        }
    }
    end:
    cout << a << " " << b << endl;
}

Measured memory_bytes: 4100
n, p = [int(i) for i in input().split()]
X = [int(i) for i in input().split()]

ans = []
S = [0]

for x in X:
    S.append(S[-1] + x)

for t in range(1, n+1):
    cur = n - t
    time = 5
    tmp = time * (S[-1] - S[cur]) + (t + n) * p
    cur -= t
    while True:
        tmp += time * (S[cur+t] - S[max(0,cur)])
        if cur <= 0:
            break
        cur -= t
        time += 2

    ans.append(tmp)

print(min(ans))

Measured memory_bytes: 31676