akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
#define Maxn 100007
#define modp 1000000007
using namespace std;
int read()
{
	int x=0,f=1;char ch=getchar();
	while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
	while (ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
int n,a[Maxn],x,y;
int pre[Maxn],inv[Maxn],last[Maxn];
int power(int a,int b)
{
	int ans=1,now=a,left=b;
	while (left>0)
	{
		if (left%2==1) ans=(1LL*ans*now)%modp;
		left/=2;
		now=(1LL*now*now)%modp;
	}
	return ans;
}
int calc(int x,int y)
{
	int ans=(1LL*pre[x]*inv[y])%modp;
	ans=(1LL*ans*inv[x-y])%modp;
	return ans;
}
int main()
{
	n=read();
	for (int i=1;i<=n+1;i++) 
	{
		a[i]=read();
		if (last[a[i]]>0)
		{
			x=last[a[i]];
			y=i;
		} else last[a[i]]=i;
	}
	pre[0]=1;
	for (int i=1;i<=n+1;i++) pre[i]=(1LL*i*pre[i-1])%modp;
	inv[n+1]=power(pre[n+1],modp-2);
	for (int i=n;i>=0;i--) inv[i]=(1LL*(i+1)*inv[i+1])%modp;
	for (int i=1;i<=n+1;i++)
	{
		int ans=calc(n+1,i);
		if (x+n-y>=i-1) ans=(ans+modp-calc(x+n-y,i-1))%modp;
		printf("%d\n",ans);
	}
	return 0;
}


Measured memory_bytes: 2816
import sys
input = sys.stdin.readline
from itertools import accumulate
N, K = map(int, input().split())
A = map(int, input().split())
B = accumulate(A)
C = [0]+[(b-i)%K for i, b in enumerate(B,start=1)]
cnt = dict()
cnt[C[0]] = 1
res = 0
for i in range(1, N+1):
    if i >= K:
        cnt[C[i-K]] = cnt.get(C[i-K],0) - 1
    res += cnt.get(C[i], 0)
    cnt[C[i]] = cnt.get(C[i],0) + 1
print(res)


Measured memory_bytes: 127944
#include<iostream>
using namespace std;
int main ()
{
long long int i,n,sum=0;
cin>>n;

for(i=1;i<=n;i++)
{
    if(i%3==0 || i%5==0)
    {

    }
    else
    {
        sum+=i;
    }
}
cout<<sum<<endl;
return 0;
}


Measured memory_bytes: 3600
n = int(input())
ans = 0
for i in range(3, n+1, 2):
    div_cnt = 0
    # print(i, end=" ")
    for j in range(1, i+1):
        if i % j == 0:
            div_cnt += 1
            # print(j, end=" ")
    if div_cnt == 8:
        ans += 1
    # print(div_cnt)
print(ans)



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

int N;
int res; 
int A[] = {1, 2, 4, 8, 16, 32, 64, 128};

int main() {
    cin >> N;
    for(int i=0; i<10; ++i){
        res = A[i-1];
        if(N<A[i]) break;
    }
    cout << res << endl;
}

Measured memory_bytes: 256
def gcd(x,y):
    if x<y:
        x,y=y,x
    if y==0:
        return x
    if x%y==0:
        return y
    else:
        return gcd(x%y,y)
N=int(input())
a=[int(input()) for i in range(N+1)][::-1]
#N=10000
#a=[i+1 for i in range(N+1)]
g=abs(a[0])
for i in range(1,N+1):
    g=gcd(g,abs(a[i]))
def check(P):
    b=[a[i]%P for i in range(1,N+1)]
    if a[0]%P!=0:
        return False
    if N<P:
        for i in b:
            if i!=0:
                return False
        return True
    else:
        c=[0 for i in range(P-1)]
        for i in range(N):
            c[i%(P-1)]+=b[i]
            c[i%(P-1)]%=P
        for i in c:
            if i!=0:
                return False
        return True
Plist=set()
X=[1 for i in range(max(N+1,3))]
X[0]=0;X[1]=0
i=2
while(i*i<=N):
    for j in range(i,N+1,i):
        if i==j:
            if X[i]==0:
                break
        else:
            X[j]=0
    i+=1
i=2
tmp=g
while(i*i<=g):
    if tmp%i==0:
        Plist.add(i)
        while(1):
            if tmp%i==0:
                tmp=tmp//i
            else:
                break
    i+=1
if tmp>1:
    Plist.add(tmp)
for j in range(N+1):
    if X[j]==1:
        Plist.add(j)
Plist=sorted(list(Plist))
for p in Plist:
    if check(p):
        print(p)
    

Measured memory_bytes: 65496
import java.util.*;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int N = sc.nextInt();
    int A = sc.nextInt();
    int B = sc.nextInt();
    int[] P = new int[N];
    for (int i = 0; i < N; i++) {
      P[i] = sc.nextInt();
    }
    int ans1 = 0;
    int ans2 = 0;
    int ans3 = 0;
    for (int i = 0; i < N; i++) {
      if (P[i] <= A) {
        ans1++;
      }
      if (A + 1 <= P[i] && P[i] <= B) {
        ans2++;
      }
      if (B + 1 <= P[i]) {
        ans3++;
      }
    }
    System.out.println(Math.min(Math.min(ans1, ans2), ans3));
  }
}

Measured memory_bytes: 21972
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define rrep(i,n) for(int i = 1; i <= (n); ++i)
#define drep(i,n) for(int i = (n)-1; i >= 0; --i)
#define all(x) (x).begin(),(x).end()
#define SZ(x) ((int)(x).size())
#define bit(n) (1<<(n))
#define fi first
#define se second
#define ii(x) int x; cin >> (x)
#define ii2(x, y) int x, y; cin >> (x) >> (y)
#define ii3(x, y, z) int x, y, z; cin >> (x) >> (y) >> (z)
#define yn(x, ok, ng) cout << ((x)?(ok):(ng)) << endl
using namespace std;
typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<vi> vvi;
typedef vector<bool> vb;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
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 const INF = 1001001001;


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

int N,K;
cin >> N >> K;

set<int> st;
rep(i,K) {
    int d; cin >> d;
    rep(i,d) {
        int a; cin >> a;
        st.insert(a);
    }
}
cout << N - SZ(st) << endl;

return 0;
}

Measured memory_bytes: 3656
#!/usr/bin/env python3
import sys, math, itertools, collections, bisect
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf') ;mod = 10**9+7
mans = inf ;ans = 0 ;count = 0 ;pro = 1

n,m,p=map(int,input().split())
E=[]
for i in range(m):
	a,b,c=map(int,input().split())
	a-=1; b-=1; c-=p; c*=-1
	E.append((a,b,c))

def BellmanFord(edges,n,s):
	#edgesは有向グラフの辺集合で辺は(始点,終点,コスト)
  #グラフの初期化
  dist=[inf for i in range(n)]
  dist[s]=0
  
  #辺の緩和
  for i in range(n+10000):
    update = False
    for u,v,cost in edges:
      if dist[u] != inf and dist[v] > dist[u] + cost:
        dist[v] = dist[u] + cost
        if i>=n+5000: dist[v]=-inf
        update = True
  return dist
  #   if i==n-2: data=dist[n-1]
  # return -1 if dist[n-1] < data else dist

dist = BellmanFord(E,n,0)
if dist[n-1] == -inf:
	print(-1)
else:
	print(max(0,-dist[n-1]))

	

Measured memory_bytes: 45276
#include<bits/stdc++.h>
#define llu unsigned long long
#define ll long long
#define INF 0x3f3f3f3f
#define fast ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define endl "\n"
#define PI 3.141592653589793
using namespace std;

int main()	
{
	#ifdef SANS
		freopen("C:\\Users\\ASUS\\Documents\\Sublime\\input_output\\inputf.txt","r",stdin);
		freopen("C:\\Users\\ASUS\\Documents\\Sublime\\input_output\\outputf.txt","w",stdout);
	#endif
	fast
	int t=1;
	while(t--)
	{
		int n,m, temp;
		cin>>n;
		map<int,int> mp;
		for(int i=1; i<=n+1; i++)
		{
			mp[i]=0;
		}
		for(int i=0; i<n-1; i++) 
		{
			cin>>temp;
			mp[temp]++;
		}
		for(int i=1; i<=n; i++)
		{
			cout<<mp[i]<<endl;
		}
	}
	#ifdef SANS
		cout<<"\nTime Elapsed:"<<1.0*clock()/CLOCKS_PER_SEC <<"sec\n";
	#endif
}

Measured memory_bytes: 13024
#include<iostream>
#include<algorithm>
using namespace std;
int N_MAX = 50;
int main()
{
  int n,k,i,res=0;
  int l[N_MAX];
  cin >> n >> k;
  for(i=0;i<n;i++)
    cin >> l[i];
  sort(l,l+n,greater<int>());
  for(i=0;i<k;i++)
    res+=l[i];
  cout << res << endl;
  return 0;
}

Measured memory_bytes: 3584
#include<bits/stdc++.h>
using namespace std;
#define max(a,b) (a>b?a:b)

int main()
{
    int N;
    cin>>N;
    int A[N], B[N], C[N];
    int dp[N][3];
    for(int i=0; i<N; i++)
    {
        cin>>A[i]>>B[i]>>C[i];
    }
    dp[0][0]=A[0];
    dp[0][1]=B[0];
    dp[0][2]=C[0];
    for(int i=1;i<N;i++)
    {
        for(int j=0;j<3;j++)
        {
            //dp[i][j]=0;
            if(j==0){ dp[i][j]=A[i]+max(dp[i-1][1],dp[i-1][2]);}
            else if(j==1){ dp[i][j]=B[i] +max(dp[i-1][0],dp[i-1][2]);}
            else{ dp[i][j]=C[i]+max(dp[i-1][0],dp[i-1][1]);}
        }
    }
    cout<<max(max(dp[N-1][0],dp[N-1][1]),dp[N-1][2]);
    return 0;
}

Measured memory_bytes: 2560
#include <cstdio>
#include <algorithm>

int n;
int t[1000], a[1000];
long long int x, y;

int main(){
	scanf("%d", &n);
	for(int i=0; i<n; ++i)
		scanf("%d %d", &t[i], &a[i]);
	x = t[0];
	y = a[0];
	for(int i=1; i<n; ++i){
		long long int ts, as;
		ts = x / t[i];
		as = y / a[i];
		if(x % t[i] != 0) ++ts;
		if(y % a[i] != 0) ++as;
		x = t[i] * std::max(as, ts);
		y = a[i] * std::max(as, ts);
//		printf("%lld %lld\n", x, y);
	}
	printf("%lld\n", x + y);
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
using ll = long long;
#define FOR(i, k, n) for(ll i = (k); i < (n); i++)
#define FORe(i, k, n) for(ll i = (k); i <= (n); i++)
#define FORr(i, k, n) for(ll i = (k)-1; i > (n); i--)
#define FORre(i, k, n) for(ll i = (k)-1; i >= (n); i--)
#define REP(i, n) FOR(i, 0, n)
#define REPr(i, n) FORre(i, n, 0)
#define ALL(x) (x).begin(), (x).end()
#define ALLr(x) (x).rbegin(), (x).rend()
#define chmin(x, y) x = min(x, y)
#define chmax(x, y) x = max(x, y)
using namespace std;

const int INF = 1001001001;

int main(void){
  ll n;
  cin >> n;
  vector<ll> a(n);
  REP(i, n) cin >> a[i];

  vector<ll> ans;
  for(ll i = 0; i < n; i += 2) ans.emplace_back(a[i]);
  reverse(ALL(ans));
  for(ll i = 1; i < n; i += 2) ans.emplace_back(a[i]);
  
  if(n%2 == 0) reverse(ALL(ans));
  REP(i, n) printf("%lld ", ans[i]);
  printf("\n");
  return 0;
}

Measured memory_bytes: 5488
n, a, b, c, d = [int(x) for x in input().split()]
s = ''.join(['#',input(),'#'])
if '##' in s[a:c+1] or '##' in s[b:d+1]:
	print("No")
else:
	if c<d:
		print("Yes")
	else:
		if '...' in s[b-1:d+2]:
			print("Yes")
		else:
			print("No")


Measured memory_bytes: 3572
#include <iostream>
#include <cstring>
#include <math.h>
#include <stdio.h>
#include <iomanip>
using namespace std;

int main()
{
    int n, k;
    cin >> n >> k;
    double value = 0;
    for (int i = 1; i <= n; i++)
    {
        int t = i;
        double a = 1;
        while (t < k)
        {
            t *= 2;
            a *= 0.5;
        }
        value += a;
    }
    value /= n;
    cout << fixed << setprecision(15) << value;

    return 0;
}


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

int main()
{
  string s;
  cin >>s;
  int i=s.length()-1;

  while(1){

    if(i<4)break;
    if(s.substr(i-4,5)=="dream"){
      i=i-5;
      continue;
    }else if(s.substr(i-4,5)=="erase"){
      i=i-5;
      continue;
    }

    if(i<5)break;
    if(s.substr(i-5,6)=="eraser"){
      i=i-6;
      continue;
    }

    if(i<6)break;
    if(s.substr(i-6,7)=="dreamer"){
      i=i-7;
      continue;
    }
    break;
  }

  string res;
  if(i==-1){
    res="YES";
  }else{
    res="NO";
  }

  cout << res <<endl;
}

Measured memory_bytes: 512
import sys
from collections import deque, Counter, defaultdict
from fractions import gcd

input = sys.stdin.readline  


def main():
    n, w = map(int, input().split())
    WVs = [list(map(int, input().split())) for i in range(n)]
    #i個目の品物を取る場合
    dp = [[0]*(w+1) for _ in range (n)]
    dp[0] = [0]*(w+1)

    for i in range(n):
        for j in range(w+1):
            wi = WVs[i][0]
            vi = WVs[i][1]

            if j - wi >= 0:
                dp[i][j] = max([dp[i-1][j-wi] + vi, dp[i-1][j]])
            else:
                dp[i][j] = dp[i-1][j] 

    print(dp[n-1][w]) 
    return

if __name__ == "__main__":
    main()


Measured memory_bytes: 124680
import math
def solve():
    def is_prime(n):
        if n == 1: return False
        for k in range(2, int(math.sqrt(n)) + 1):
            if n % k == 0:
                return False
        return True

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

    def make_divisors(n):
        divisors = []
        for i in range(1, int(n**0.5)+1):
            if n % i == 0:
                divisors.append(i)
                if i != n // i:
                    divisors.append(n//i)
        divisors.sort()
        return divisors
    
    A , B = map(int , input().split())

    gcd_value = gcd(A , B)
    cd = []
    div = make_divisors(gcd_value)
    for value in div:
        if A % value == 0 and B % value == 0 and is_prime(value):
            cd.append(value)
    print(len(cd) + 1)
    
if __name__ == "__main__":
    solve()

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

#define sz(x) (int)x.size() 
#define pb push_back 
#define mp make_pair 
#define fi(a, b) for(int i=a; i<=b; i++) 
#define fj(a, b) for(int j=a; j<=b; j++) 
#define fo(a, b) for(int o=a; o<=b; o++) 
#define fdi(a, b) for(int i=a; i>=b; i--) 
#define fdj(a, b) for(int j=a; j>=b; j--) 
#define fdo(a, b) for(int o=a; o>=b; o--) 

#ifdef LOCAL
#define err(...) fprintf(stderr, __VA_ARGS__)
#else
#define err(...) while(false) {}
#endif

typedef long long ll; 
typedef pair<int, int> pii; 
typedef pair<ll, ll> pll; 
typedef vector<int> vi; 
typedef vector<ll> vll;
typedef vector<pii> vpii; 
typedef vector<pll> vpll; 
typedef long double ld;
typedef unsigned long long ull;

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

int const MAX = 1e5 + 41;

int n;
ll p;

ll w[MAX];
ll b[MAX];

void solve() {
	ll cur = 0;
	priority_queue<ll> pq;
	fi(1, n) {
		cur -= b[i] * p;
		pq.push(b[i] * p + (100 - p) * w[i]);
	}
	int ans = 0;

	while (cur < 0) {
		ans++;
		ll x = pq.top();
		cur += x;
		pq.pop();
	}
	printf("%d\n", ans);
}

int main() {
#ifdef LOCAL
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
#endif

  scanf("%d %lld", &n, &p);
  fi(1, n) {
  	scanf("%lld %lld", &w[i], &b[i]);
  }
	solve();		

	
#ifdef LOCAL
	err("ELAPSED TIME: %.3Lf\n", (ld) clock() / CLOCKS_PER_SEC);
#endif	
	
	return 0;
}

Measured memory_bytes: 2936
#include<bits/stdc++.h>
#define REP(i,n) for(int i=0;i<n;i++)
#define ll long long
using namespace std;
int main(){
    ll N,sum=0,ans=LONG_MAX;cin>>N;
    vector<ll> score(N,0);
    REP(i,N){
        cin>>score[i];
        sum+=score[i];
    }
    ll tmpsum=0;
    REP(i,N-1){
        tmpsum+=score[i];
        ans=min(ans,abs(sum-2*tmpsum));
    }
    cout<<ans<<endl;
}

Measured memory_bytes: 1792
import java.util.*;


public class Main {
	
	
	public static void main(String[] args) {

		Scanner s = new Scanner(System.in);
		
		int n = s.nextInt();
		int[] a = new int[n+1];
		for(int i = 1;i<=n;i++)a[i] = s.nextInt();
		int c=  0;
		for(int i = 2;i<n;i++)
		{
			if((a[i]>a[i-1]&&a[i]>a[i+1])||(a[i]<a[i-1]&&a[i]<a[i+1]))
			{}else c++;
		}
		
		 System.out.println(c);
	}
}


Measured memory_bytes: 23508
n=int(input())
dict={"AC":0,"WA":0,"TLE":0,"RE":0}
for i in range(n):
    s=input()
    dict[s]+=1
print("AC x "+str(dict["AC"]))
print("WA x "+str(dict["WA"]))
print("TLE x "+str(dict["TLE"]))
print("RE x "+str(dict["RE"]))


Measured memory_bytes: 9196
using System;
using System.Collections.Generic;
using System.Numerics;
using System.Linq;

namespace AtCoderTemplate
{
    class Program
    {
        static void Main(string[] args)
        {
            var a = Scanner.rescanint(5);
            var b = a.Where(x => x[0] % 10 == 0).ToArray();
            var c = a.Where(x => x[0] % 10 != 0).OrderByDescending(x => x[0] % 10).ToArray();
            var res = 0;
            for (var i = 0; i < c.Length - 1; i++) res += c[i][0] + (10 - c[i][0] % 10);
            for (var i = 0; i < b.Length; i++) res += b[i][0];
            if (c.Length != 0) Console.WriteLine(res + c[c.Length - 1][0]);
            else Console.WriteLine(res);
        }
    }

    public class Scanner
    {
        public static string[] scan => Console.ReadLine().Split(' ');
        public static int[] scanint => Array.ConvertAll(scan, int.Parse);
        public static long[] scanlong => Array.ConvertAll(scan, long.Parse);
        public static string[][] rescan(int n) => Enumerable.Repeat(0, n).Select(_ => scan).ToArray();
        public static int[][] rescanint(int n) => Enumerable.Repeat(0, n).Select(_ => scanint).ToArray();
        public static long[][] rescanlong(int n) => Enumerable.Repeat(0, n).Select(_ => scanlong).ToArray();

    }

    public class Ex
    {
        public static int[] subarr(int[] arr, int begin, int n) { int[] a = new int[arr.Length]; Array.Copy(arr, begin, a, 0, n); return a; }
    }
}


Measured memory_bytes: 13524
#include<stdio.h>
#include<stdlib.h>
int main(void){
        int n,m,i,j,num,tmp;
        int *B,**A;
        scanf("%d %d",&n,&m);
        B = (int *)malloc(sizeof(int)*m);
        A = (int **)malloc(sizeof(int*)*n);
        for(i=0;i<n;i++){
                A[i] = (int *)malloc(sizeof(int)*m);
        }
        for(i=0;i<n;i++){
                for(j=0;j<m;j++){
                        scanf("%d",&A[i][j]);
                }
        }
        for(i=0;i<m;i++){
                scanf("%d",&B[i]);
        }
        for(i=0;i<n;i++){
                tmp = 0;
                for(j = 0;j<m;j++){
                        tmp = tmp + A[i][j] * B[j];
                }
                printf("%d\n",tmp);
        }
        for(i=0;i<n;i++){
                free(A[i]);
        }
        free(A);
        return 0;
}


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

#define rep(i, n) for (int i = 0; i < (n); i++)
using namespace std;
typedef long long ll;
const int INF = 1e9;

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

  vector<vector<int>> vec(M);

  for (int i = 0; i < M; ++i) {
    int k;
    cin >> k;
    vec[i].resize(k);
    for (int j = 0; j < k; ++j) {
      cin >> vec[i][j];
      --vec[i][j];
    }
  }

  vector<int> p(M);
  for (int i = 0; i < M; ++i) cin >> p[i];

  int ans = 0;
  for (int i = 0; i < (1 << N); ++i) {
    bool ok = true;
    for (int j = 0; j < M; ++j) {
      int c = 0;
      for (int id : vec[j]) {
        if ((i >> id) & 1) ++c;
      }
      c %= 2;
      if (c != p[j]) ok = false;
    }
    if (ok) ++ans;
  }

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


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

int get_color(int);

int main()
{
    int color[9]{}, n;
    scanf("%d", &n);
    for (int i = 0; i < n; i++)
    {
        int a;
        scanf("%d", &a);
        color[get_color(a)]++;
    }
    int count{};
    for (int i = 0; i < 8; i++)
        if (color[i] > 0)
            count++;
    if (count)
        printf("%d %d\n", count, count + color[8]);
    else
        printf("1 %d\n", color[8]);

    return 0;
}

int get_color(int c)
{
    int table[8]{400, 800, 1200, 1600, 2000, 2400, 2800, 3200};
    for (int i = 0; i < 8; i++)
    {
        if (c < table[i]) return i;
    }
    return 8;
}

Measured memory_bytes: 256
#include <cstdio>
using namespace std;
const int N=710,M=N*N;
const int INF=1e9;
int n,m;
int link[N][N];
int h[N],tot;
struct Edge{
	int v,next;
}e[M*2];
inline int min(int x,int y){
	return x<y?x:y;
}
void addEdge(int u,int v){
	e[++tot]=(Edge){v,h[u]}; h[u]=tot;
	e[++tot]=(Edge){u,h[v]}; h[v]=tot;
}
void readData(){
	scanf("%d%d",&n,&m);
	int u,v;
	for(int i=1;i<=m;i++){
		scanf("%d%d",&u,&v);
		link[u][v]=link[v][u]=1;
	}
}
void buildGraph(){
	for(int u=1;u<n;u++)
		for(int v=u+1;v<=n;v++)
			if(!link[u][v])
				addEdge(u,v);
}
int col[N];
int w[N][2],bcnt;
void paintDfs(int u){
	w[bcnt][col[u]]++;
	for(int i=h[u],v;i;i=e[i].next){
		v=e[i].v;
		if(col[v]==-1){
			col[v]=col[u]^1;
			paintDfs(v);
		}
		else if(col[v]!=(col[u]^1))
			throw 0;
	}
}
bool paint(){
	for(int i=1;i<=n;i++) col[i]=-1;
	for(int i=1;i<=n;i++)
		if(col[i]==-1){
			try{
				bcnt++;
				col[i]=0;
				paintDfs(i);
			}
			catch(int e){
				return false;
			}
		}
	return true;
}
bool f[N][N];
void dp(){
	f[0][0]=1;
	for(int i=0;i<bcnt;i++)
		for(int j=0;j<=n;j++)
			if(f[i][j]){
				f[i+1][j+w[i+1][0]]=true;
				f[i+1][j+w[i+1][1]]=true;
			}
}
void check(){
	int ans=INF;
	for(int i=1;i<n;i++)
		if(f[bcnt][i])
			ans=min(ans,i*(i-1)/2+(n-i)*(n-i-1)/2);
	printf("%d\n",ans);
}
int main(){
	readData();
	buildGraph();
	if(!paint()){
		puts("-1");
		return 0;
	}
	dp();
	check();
	return 0;
}


Measured memory_bytes: 7936
function gets(str){
  this._s = str.split("\n");
  this._y = 0;
};
gets.prototype = {
  a: function(f){
    var s = this._s, y = this._y, r;
    if(typeof s[y] === "string")s[y] = s[y].split(" ").reverse();
    r = s[y].pop();
    if(!s[y].length)this._y++;
    return f?r:+r;
  },
  l: function(f){
    var s = this._s[this._y++].split(" ");
    return f?s:s.map(a=>+a);
  },
  m: function(n,f){
    var s = this._s, y = this._y, r = [], i = 0;
    if(f)for(;i < n; i++)r[i] = s[y+i].split(" ");
    else for(;i < n; i++)r[i] = s[y+i].split(" ").map(a=>+a);
    this._y += n;
    return r;
  },
};
var o=new gets(require("fs").readFileSync("/dev/stdin","utf8"));

console.log(main());
function main(){
  var n = o.a();
  var t = o.a();
  var a = o.a();
  var h = o.l();
  var ans = 0, m = 9e9;
  for(var i = 0; i < n; i++){
    var x = t - h[i] * 0.006;
    x = Math.abs(x-a);
    if(x < m){
      m = x;
      ans = i;
    }
  }
  return ans+1;
}

Measured memory_bytes: 7500
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<iostream>
#include<queue>

using namespace std;

typedef long long LL;
typedef unsigned long long ULL;

const int MaxN = 1e5;

int n;
char a[200][20];

int main(){
	cin >> n;
	cin >> a[1];
	for(int i = 2;i <= n;i++){
		cin >> a[i];
		for(int j = i-1;j >= 1;j--){
			if(strcmp(a[i],a[j]) == 0){
				cout << "No" << endl;
				return 0;
			}
		}
		int k = strlen(a[i-1]);
	//	cout << k << endl;
		if(a[i][0] != a[i-1][k-1]){
			cout << "No" << endl;
			return 0;
		}
	}
	cout << "Yes" <<endl;
}

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

int main() {
    int n;
    int sum = 0;
    vector<int> s;
    cin >> n;
    FOR(i, n){
        int temp;
        cin >> temp;
        sum += temp;
        s.push_back(temp);
    }

    sort(s.begin(), s.end(), greater<int>() );
    int count = 0;
    while(sum != 0 && sum % 10 == 0) {
        if(count > 0) {
            s.pop_back();
            n--;
            sum = 0;
            FOR(i, s.size() ) sum += s[i];
        }

        bool flag = false;
        for(int i = 0; i < s.size(); i++) {
            sum -= s[n - i - 1];
            if(i != 0) sum += s[n - i];
            if(sum == 0 || sum % 10 != 0) {
                flag = true;
                break;
            }
        }
        if(flag) break;
        count++;
    }

    cout << sum << endl;

    return 0;
}


Measured memory_bytes: 256
#include<stdio.h>

int main(void)
{
	int i,j,k,l,n,m;
	
	while(scanf("%d",&n)!=EOF)
	{
		m=0;
		for(i=0;i<=9;i++)
		{
			for(j=0;j<=9;j++)
			{
				for(k=0;k<=9;k++)
				{
					for(l=0;l<=9;l++)
					{
						if(i+j+k+l==n) m++;
					}
				}
			}
		}
		printf("%d\n",m);
	}
	return 0;
}

Measured memory_bytes: 596
#include<iostream>
#include<cstdio>
#include<queue>
#include<vector>
#include<string.h>
#include<algorithm>
#include <cmath>

using namespace std;

long long N,K,i,j,sum,temp,kmax,k[50],memo[50],fact[50],sumK,a,b,c,ans;

vector<long long> A;

int main()
{
  cin >> N >> K;
  
  A.assign(N,0);
  sum=0;
  sumK=0;
  for(i=0;i<N;i++)
  {
    cin >> A[i];
    sum+=A[i];
    sumK+=A[i]^K;
  }
  if(K==0)
  {
    cout << sum;
    return 0;
  }
  
  fact[0]=1;
  for(i=1;i<46;i++)
  {
    fact[i]=fact[i-1]*2;
  }
 
  for(j=0;fact[j]<=K;j++)
  {
    if(fact[j]==(fact[j]&K))
    {
      k[j]=1;
      kmax=j;
    }
    else
    {
      k[j]=0;
    }

  }
  
  ans=max(sumK,sum);

  for(i=0;i<=kmax;i++)
  {
    temp=sum;
    if(k[i]==1)
    {
      for(j=0;j<i;j++)
      {
        a=0;
        for(b=0;b<N;b++)
        {
          if(fact[j]==(A[b]&fact[j]))
          {
            a++;
          }
          
        }   
        if(a<N-a)
        {
          temp+=fact[j]*(N-2*a);
        }
      }
      
      for(j=i+1;j<=kmax;j++)
      {
        if(k[j]==1)
        {
          a=0;
          for(b=0;b<N;b++)
          {
            if(fact[j]==(A[b]&fact[j]))
            {
              a++;
            }
          }
          temp+=fact[j]*(N-2*a);
        }
      }
      ans=max(ans,temp);
    }
    
  }

  cout << ans;
  
}

Measured memory_bytes: 1024
#include <cstdio>
#include <stack>
#include <queue>
#include <cstring>
#define LL long long
#define PA pair<int,int>
#define INF 0x3f3f3f3f
using namespace std;

namespace FastIO {
	template<typename tp> inline void read(tp &x) {
		x=0; register char c=getchar(); register bool f=0;
		for(;c<'0'||c>'9';f|=(c=='-'),c = getchar());
		for(;c>='0'&&c<='9';x=(x<<3)+(x<<1)+c-'0',c = getchar());
		if(f) x=-x;
	}
	template<typename tp> inline void write(tp x) {
		if (x==0) return (void) (putchar('0'));
		if (x<0) putchar('-'),x=-x;
		int pr[20]; register int cnt=0;
		for (;x;x/=10) pr[++cnt]=x%10;
		while (cnt) putchar(pr[cnt--]+'0');
	}
	template<typename tp> inline void writeln(tp x) {
		write(x);
		putchar('\n');
	}
}
using namespace FastIO;

const int N = 1e5 + 10;
struct node{
    int l,r;
}sons[N];
char s[N];
int n, m;
stack<int> ST;
bool vis[N];
int fa[N];
priority_queue<PA> q;
int main() {
    memset(vis, 0, sizeof vis);
    scanf("%s",s+1);
    n = strlen(s + 1);
    if (s[n] == '1' || s[1] == '0' || s[m = n - 1] == '0') {
        puts("-1");
        return 0;
    }
    s[n] = 0;
    fa[fa[2] = 1] = 0;
    for (int i = 2; i <= (m + 1) >> 1; ++i) {
        if (s[i] != s[m - i + 1]) {
            puts("-1");
            return 0;
        }
        if (s[i] == '1') {
            ST.push(i);
        }
    }
    bool f = 1;
    if(ST.empty()) {
        ST.push(1);
    }
    while (!ST.empty()) {
        int a = ST.top();
        ST.pop();
        if (f) {
            vis[1] = vis[2] = 1;
            sons[1].l = 3;
            sons[1].r = 3 + a - 2;
            sons[2].l = 3 + a - 1;
            sons[2].r = n;
            q.push(make_pair(a - 1, 1));
            q.push(make_pair(a - 1, 2));
            f = 0;
        } else {
            PA cache = q.top();
            q.pop();
            cache.first -= a;
            q.push(cache);
            int son = sons[cache.second].l;
            fa[son] = cache.second;
            sons[cache.second].l += a;
            sons[son].l = son + 1;
            sons[son].r = son + a - 1;
            q.push(make_pair(a - 1, son));
            vis[son] = 1;
        }
    }
    for (int i = 1; i <= n; ++i) {
        if (vis[i]) {
            for (int j = sons[i].l; j <= sons[i].r; ++j) {
                fa[j] = i;
            }
        }
    }
    for (int i = 2; i <= n; ++i) printf("%d %d\n",i ,fa[i]);
    return 0;
}

Measured memory_bytes: 3000
fun main(args: Array<String>) {
  println(questionC(readLine()!!.toLong()))
}
 
fun questionC(n: Long): Long {
    var min = Long.MIN_VALUE

    if (n in 2L..Long.MAX_VALUE) {
        val table = Math.sqrt(n.toDouble()).toLong()
        (1..table).forEach {
            if (n % it != 0L) return@forEach

            min = Math.min(Long.MAX_VALUE, it + n / it - 2)
        }
    }

    return min
}

Measured memory_bytes: 33636
#include <iostream>
#include <fstream>
#include <iomanip>
#include <math.h>
#include <limits.h>
#include <algorithm>
#include <vector>
#include <list>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <bitset>
#include <string>
#include <string.h>
#include <sstream>
#include <ctime>

using namespace std;

#define eps 1e-12
#define pi 3.14159265358979323846
#define pb push_back
#define mp make_pair
#define st first
#define nd second
#define bgn begin
#define ll long long
#define ld long double
#define ull unsigned long long
#define ii pair<ll,ll>








const int N = 1e5 + 10;
ll n, a, b, c, res[N];
string s[N];
bool vld;


bool mv(ll & a, ll & b, int i, int j, char ch)
{
	if(a > b)
	{
		a--;
		b++;
		res[i] = 1;
	}
	else if(a < b)
	{
		a++;
		b--;
		res[i] = 0;
	}
	else
	{
		if(i < n)
		{
			if(s[i + 1][j] == ch)
			{
				a++;
				b--;
				res[i] = 0;
			}
			else
			{
				a--;
				b++;
				res[i] = 1;
			}
		}
		else
		{
			a++;
			b--;
			res[i] = 0;
		}
	}
	return (a >= 0 && b >= 0);
}





void solve()
{
	cin >> n >> a >> b >> c;
	for(int i = 1; i <= n; i++)
	{
		cin >> s[i];
	}
	for(int i = 1; i <= n; i++)
	{
		if(s[i] == "AB")
		{
			vld = mv(a, b, i, 0, 'A');
			
		}
		else if(s[i] == "AC")
		{
			vld = mv(a, c, i, 0, 'A');
		}
		else
		{
			vld = mv(b, c, i, 1, 'B');
		}
		if(!vld)
		{
			cout << "No\n";
			return;
		}
	}
	cout << "Yes\n";
	for(int i = 1; i <= n; i++)
	{
		cout << s[i][res[i]] << "\n";
	}
}

int main()
{
	std::ios::sync_with_stdio(0);
	cin.tie(0);
#ifdef localProject
	freopen("in.txt","r",stdin);
#endif
	solve();
	return 0;
}

Measured memory_bytes: 7560
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		if (N%1000==0) {
			System.out.println(0);
		} else {
			System.out.println((N/1000+1)*1000-N);
		}
	}
}

Measured memory_bytes: 35624
#include <iostream>
#include <cmath>
#include <limits.h>
using namespace std;

int main()
{
	int dt,t,mae,tmp;
	cin >> dt;
	for(;dt>0;dt--)
	{
		int mi=0,ma=0;
		cin >> t >> mae;
		for(int i=0;i<t-1;i++)
		{
			cin >> tmp;
			mi=min(tmp-mae,mi);
			ma=max(tmp-mae,ma);
			mae=tmp;
		}
		if(mi>0)ma=0;
		if(ma<0)mi=0;
		
		cout << ma << " " << -mi << endl;
	}
}

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

int main(void)
{		
	int r, c;
	cin >> r >> c;
	
	int ary[100 + 1][100 + 1];
	for (int i = 0; i < r; i++) {
		for (int j = 0; j < c; j++) {
			cin >> ary[i][j];
		}
	}
	
	for (int i = 0; i < r; i++) {
		int sum = 0;
		for (int j = 0; j < c; j++) {
			sum += ary[i][j];
		}
		ary[i][c] = sum;
	}
	
	for (int j = 0; j < c + 1; j++) {
		int sum = 0;
		for (int i = 0; i < r; i++) {
			sum += ary[i][j];
		}
		ary[r][j] = sum;
	}
	
	for (int i = 0; i < r + 1; i++) {
		for (int j = 0; j < c + 1; j++) {
			cout << ary[i][j];
			if (j < c) cout << " ";
		}
		cout << endl;
	}
	
	return 0;
}

Measured memory_bytes: 3128
using System;
using System.Collections.Generic;
using System.Linq;

namespace ConsoleApp10
{
    class Program
    {
        static void Main(string[] args)
        {
            Calc calc = new Calc();

            string str;
            List<int[]> num = new List<int[]>();

            int gcd, lcm;

            while (!((str = Console.ReadLine()) == null))
            {
                num.Add(str.Split(' ').Select(int.Parse).ToArray());
            }

   

            for (int i = 0; i < num.Count(); i++)
            {
                int[] num2 = { num[i][0], num[i][1] };

                gcd = calc.EucledeanAlgorithm(num[i]);
                lcm = calc.LCM(num2, gcd);

                Console.WriteLine("{0} {1}", gcd, lcm);
            }
        }
    }

    class Calc
    {
        int r;
        int[] num;

        internal int EucledeanAlgorithm(int[] number)
        {
            int gcd;
            num = number;
            r = 1;

            while (r != 0)
            {
                num = Remainder();
            }
            gcd = num[0];

            return gcd;
        }

        internal int[] Remainder()
        {
            int a, b;

            if (num[0] >= num[1])
            {
                a = num[1]; b = num[0];
            }
            else
            {
                a = num[0]; b = num[1];
            }
            r = b - (b / a) * a;

            num[0] = a;  num[1] = r;

            return num;
        }

        internal int LCM(int[] num,int gcd)
        {
            int lcm;
            lcm = (num[0] / gcd) * (num[1] / gcd) * gcd;

            return lcm;
        }
    }
}



Measured memory_bytes: 16388
#include<bits/stdc++.h>
using namespace std;
 
void __print(int x) {cout << x;}
void __print(long x) {cout << x;}
void __print(long long x) {cout << x;}
void __print(unsigned x) {cout << x;}
void __print(unsigned long x) {cout << x;}
void __print(unsigned long long x) {cout << x;}
void __print(float x) {cout << x;}
void __print(double x) {cout << x;}
void __print(long double x) {cout << x;}
void __print(char x) {cout << '\'' << x << '\'';}
void __print(const char *x) {cout << '\"' << x << '\"';}
void __print(const string &x) {cout << '\"' << x << '\"';}
void __print(bool x) {cout << (x ? "true" : "false");}

template<typename T, typename V>
void __print(const pair<T, V> &x) {cout << '{'; __print(x.first); cout << ','; __print(x.second); cout << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cout << '{'; for (auto &i: x) cout << (f++ ? "," : ""), __print(i); cout << "}";}
void _print() {cout << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cout << ", "; _print(v...);}
#ifndef ONLINE_JUDGE
#define debug(x...) cout << "[" << #x << "] = ["; _print(x)
#else
#define debug(x...)
#endif
 
#define int long long int
#define fi first
#define se second
#define FIO {ios::sync_with_stdio(0);cin.tie(nullptr);cout.tie(nullptr);}
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define forn(i, n) for (int i = 0; i < (int)(n); ++i)
#define for1(i, n) for (int i = 1; i <= (int)(n); ++i)
#define ford(i, n) for (int i = (int)(n) - 1; i >= 0; --i)
#define all(x) (x).begin(), (x).end()
#define pow10(n) stoll("1"+string(n,'0'))
//fill(all(arr),1)
//if(map.count(key)){}
//bitset<20>(n);
//int mini=min({a,b,c,d,e});
 
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<pii> vpi;
typedef vector<vi> vvi;
typedef long long ll;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef long double ld;

int32_t main(){
  FIO
  int x;cin>>x;
  int total=100;
  int cnt=0;
  while(total<x)
  {
    if(0.01*total>=1)total+=0.01*total;
    cnt++;
  }
  cout<<cnt;
  
  return 0;
}

Measured memory_bytes: 3656
def selectionSort(a, n):
    sw = 0
    for i in range(n):
        minj = i
        for j in range(i, n):
            if a[j] < a[minj]:
                minj = j
        a[i], a[minj] = a[minj], a[i]
        if i != minj:
            sw += 1
    return sw


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

sw = selectionSort(a, n)
print(*a)
print(sw)



Measured memory_bytes: 5604
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <numeric>
#include <cmath>
#include <stack>
#include <queue>
#include <set>

#define mod 1000000007
#define mp make_pair
#define rep(i,n) for(int i=0;i<n;i++)
#define _GLIBCXX_DEBUG
#define _LIBCPP_DEBUG 0

using namespace std;
using ll = long long;
using pii = pair<int, int>;

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll n, m, a, b;
    cin >> n >> m;
    vector<ll> x(n+1, 0);
    vector<ll> h(n+1);
    for(ll i=1; i<=n; i++) cin >> h[i];
    rep(i, m){
        cin >> a >> b;
        if(h[a] >= h[b]) x[b]++;
        if(h[a] <= h[b]) x[a]++;
    }
    ll ans = 0;
    for(ll i=1; i<=n; i++){
        if(x[i]== 0) ans++;
    }
    cout << ans;
    return 0;
}

Measured memory_bytes: 4748
#include <bits/stdc++.h>
using namespace std;
using i64 = int64_t;

struct edge {
    int a, b;
    double w;
};

class BellmanFord {    
    int n;
    vector<edge> edges;
    vector<double> d;

public:
    BellmanFord(int n) : n(n) {
        edges = vector<edge>(n);
        d = vector<double>(n, numeric_limits<double>::infinity());
    }

    void addEdge(int a, int b, double w) {
        assert(0 <= a && a < n && 0 <= b && b < n);
        edges.push_back({a, b, w});
        edges.push_back({b, a, w});
    }
    void addArc(int a, int b, double w) {
        assert(0 <= a && a < n && 0 <= b && b < n);
        edges.push_back({a, b, w});
    }

    // return true if has negative loop
    bool run(int a) {
        d[a] = 0;
        for (int i = 0; i < n; i++) {
            bool change = false;
            for (edge e: edges) {
                if (d[e.a] != numeric_limits<double>::infinity()) {
                    if (d[e.b] > d[e.a] + e.w) {
                        d[e.b] = d[e.a] + e.w;
                        change = true;
                    }
                }
            }
            if (!change) {
                return false;
            }
        }
        return true;
    }

    double dist(int a) {
        return d[a];
    }
};

int main() {
    int v, e, r;
    cin >> v >> e >> r;
    BellmanFord g(v);
    for (int i = 0; i < e; i++) {
        int a, b, w;
        cin >> a >> b >> w;
        g.addArc(a, b, w);
    }
    if (g.run(r)) {
        cout << "NEGATIVE CYCLE" << endl;
        return 0;
    }
    for (int i = 0; i < v; i++) {
        if (g.dist(i) == numeric_limits<double>::infinity()) {
            cout << "INF" << endl;
        } else {
            cout << i64(g.dist(i)) << endl;
        }
    }
}


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

int main() {
	char a[3];
	cin >> a[0] >> a[1] >> a[2];
	int x = 0;
	if (a[0] == '1') {
		x += 900;
	} else {
		x += 100;
	}
	if (a[1] == '1') {
		x += 90;
	} else {
		x += 10;
	}
	if (a[2] == '1') {
		x += 9;
	} else {
		x += 1;
	}
	cout << x << endl;
	return 0;
}



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

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

const ll mod =  1000000007;  //出力は (ans % mod + mod) % mod  (負の剰余を正にする)
const int inf = 1e9;
const long long INF = 1LL << 60;   // INF = 1152921504606846976
const double PI = 3.1415926535897932;

int main()
{
    int a,b; cin >> a >> b;
    if(a > 9 || b > 9) cout << -1;
    else cout << a * b;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int a[205];
    int n;
    cin>>n;
    for(int i=0;i<n;i++)
    {
        scanf("%d",&a[i]);
    }
    bool f=false;
    int ans=0;
    while(1)
    {
        for(int i=0;i<n;i++)
        {
            if(a[i]%2!=0)
            {
                f=true;
                break;
            }
            else
            {
                a[i]>>=1;
            }
        }
        if(!f)
            ans++;
        else
            break;
    }
    cout<<ans<<endl;
    return 0;
}


Measured memory_bytes: 256
use std::io::Read;

fn main() {
    let mut buf = String::new();
    std::io::stdin().read_to_string(&mut buf).unwrap();

    let answer = solve(&buf);

    println!("{}", answer);
}

fn solve(input: &str) -> String {
    let mut iterator = input.split_whitespace();

    let mut s: &str = iterator.next().unwrap();

    while !s.is_empty() {
        if s.starts_with("eraser") {
            s = &s[6..];
        } else if s.starts_with("erase") {
            s = &s[5..];
        } else if s.starts_with("dreamerd") || s.starts_with("dreamere") || s == "dreamer" {
            s = &s[7..];
        } else if s.starts_with("dream") {
            s = &s[5..];
        } else {
            break;
        }
    }

    if s.is_empty() {
        return "YES".to_string();
    }

    return "NO".to_string()
}


Measured memory_bytes: 4352
/* 
	بسم الله الرحمن الرحیم
	
	(; طلا یک جهانی
*/

#include <bits/stdc++.h>
using namespace std;

#define X first
#define Y second
typedef pair<int, int> pii;

const int MAX_N = 1000 + 5;
int h, w, dis[MAX_N][MAX_N];
bool mark[MAX_N][MAX_N];
vector<pii> saf;

void read_input() {
	cin >> h >> w;
	memset(dis, 63, sizeof dis);
	for (int i = 0; i < h; i++)
		for (int j = 0; j < w; j++) {
			char ch;
			cin >> ch;
			if (ch == '#') {
				saf.push_back({i, j});
				mark[i][j] = true;
				dis[i][j] = 0;
			}
		}
}

void solve() {
	int dx[] = {0, 1, 0, -1};
	int dy[] = {1, 0, -1, 0};
	int ans = 0;
	for (int i = 0; i < (int) saf.size(); i++) {
		pii v = saf[i];
		for (int j = 0; j < 4; j++) {
			pii u = {v.X + dx[j], v.Y + dy[j]};
			if (u.X >= 0 && u.X < h && u.Y >= 0 && u.Y < w && !mark[u.X][u.Y]) {
				saf.push_back(u);
				mark[u.X][u.Y] = true;
				dis[u.X][u.Y] = dis[v.X][v.Y] + 1;
				ans = max(ans, dis[u.X][u.Y]);
			}
		}
	}
	cout << ans;
}

int main() {
	ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
	read_input();
	solve();
}


Measured memory_bytes: 14828
using System;

namespace AtCoderSnippet
{
    class Program
    {
        static void Main(string[] args)
        {
            var N = long.Parse(Console.ReadLine());
            var A = Console.ReadLine().Split(" ");
            long x = 0;
            
            for (int i = 0; i < N-1; i++)
            {
                var ax = long.Parse(A[i]);
                var ay = long.Parse(A[i+1]);
                if (ax > ay)
                {
                    var z = ax - ay;
                    A[i + 1] = (ay +z).ToString();
                    x += z;
                }
            }
            Console.WriteLine(x);
        }
    }
}


Measured memory_bytes: 52492
#include <bits/stdc++.h>
#define fst first
#define snd second
#define rep(n) for(lint I = 0; (I) < (lint)(n); ++(I))
#define repeat(i, n) for(lint i = 0; (i) < (lint)(n); ++(i))
#define repeat_to(i, n) for(lint i = 0; (i) <= (lint)(n); ++(i))
#define repeat_from(i, m, n) for(lint i = (m); (i) < (lint)(n); ++(i))
#define repeat_from_to(i, m, n) for(lint i = (m); (i) <= (lint)(n); ++(i))
#define repeat_reverse_from_to(i, m, n) for(lint i = (m); (i) >= (lint)(n); --(i))
#define el cout<<endl
#define dump(x) cout<<" "<<#x<<"="<<x
#define pdump(p) cout<<" "<<#p<<"=("<<p.fst<<","<<p.snd<<")"
#define vdump(v) for(size_t I=0; I<v.size(); ++I){cout<<" "<<#v<<"["<<I<<"]="<<v[I];} cout<<endl
using namespace std; using lint = long long; using ld = long double;
using pii = pair<int, int>; using pll = pair<lint, lint>;

int main(void) {
    int n;
    cin >> n;
    set<int> st;
    
    lint x = 0;
    while (true) {
        ++x;
        if (st.count(n) == 0) {
            st.insert(n);
        }
        else {
            cout << x << endl;
            break;
        }
        if (n % 2 == 0) n /= 2;
        else n = (n * 3) + 1;
    }
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
 
using namespace std;
 
const long long MOD=1e9+7;
const double PI=3.14159265359;


int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    string s;
    cin>>s;
    s[3]='8';
    cout<<s;
    
    
    return 0;
}

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

#define lli long long int
#define REP(i,s,l) for(lli i=s;i<l;i++)
#define DEBUG 0
#define INF (1LL<<50)
#define MOD 1000000007

int main(){
    int a, b; cin >> a >> b;

    int mul = a*b;
    if(mul%2==0) cout << "Even";
    else cout << "Odd";
    cout << endl;
    return 0;
}

Measured memory_bytes: 256
S = input()
ans = len(S)

for i in range(2):
  cnt = 0
  for j in range(len(S)):
    if j % 2 == 0 and S[j] != str(i):
      cnt += 1
    if j % 2 == 1 and S[j] == str(i):
      cnt += 1
  ans = min(ans, cnt)
print(ans)

Measured memory_bytes: 3188
import java.util.Scanner;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;

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

        while(true){
            int m = sc.nextInt();
            int f = sc.nextInt();
            int r = sc.nextInt();
            if(m == -1 && f == -1 && r == -1){
                break;
            }
            
            if(m == -1 || f == -1){
                System.out.println("F");
                continue;
            }
            if(m + f >= 80){
                System.out.println("A");
                continue;
            }
            if(m + f >= 65 && m + f < 80){
                System.out.println("B");
                continue;
            }
            if(m + f >= 50 && m + f < 65){
                System.out.println("C");
                continue;
            }
            if(m + f >= 30 && m + f < 50){
                if(r >= 50){
                    System.out.println("C");
                }
                else{
                    System.out.println("D");
                }
                continue;
            }
            else{
                System.out.println("F");
            }
        }

        sc.close();
    }
}


Measured memory_bytes: 26244
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    bool flag = true;
    cin>>n;
    int a[n+1]={0};

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

    int mx = a[0];
    mx--;
    for(int i=1; i<n&&flag; i++)
    {
        if(a[i]>mx)a[i]--;
        if(a[i]<mx)flag=false;
        mx=a[i];
        //if(a[i]-a[i-1] < -1)flag=false;
    }
    (flag==true)?cout<<"Yes"<<endl:cout<<"No"<<endl;


    return 0;
}


Measured memory_bytes: 640
# coding=utf-8

n = int(input())
S = list(map(int, input().split()))
q = int(input())
T = map(int, input().split())
found = []

for t in T:
    left = 0
    right = n
    find_flag = False
    while True:
        search_pos = (left + right) // 2
        if t < S[search_pos]:
            right = search_pos
        elif t > S[search_pos]:
            left = search_pos + 1
        elif t == S[search_pos]:
            found.append(t)
            find_flag = True
            break
        if left == right and not find_flag:
            break

print(len(found))

Measured memory_bytes: 18696
def main():
  s = input()
  n = len(s)
  first = s[:(n-1)//2]
  last = s[((n+3)//2)-1:]
  if first != last:
    print('No')
    exit(0)
  print('Yes')
  
def count_section_by_zero(data):
  count = 0
  flg = False
  start = 0
  for i, d in enumerate(data):
    if flg is False and d != 0:
      count += 1
      flg = True
      
    if d == 0:
      flg = False
  return count

def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

def input_list():
  return list(map(int, input().split()))

def input_list_str():
  return map(str, input().split())

def lcm_base(x, y):
    return (x * y) // fractions.gcd(x, y)

def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)

def gcd(*numbers):
    return reduce(fractions.gcd, numbers)

def gcd_list(numbers):
    return reduce(fractions.gcd, numbers)

# 2で割り切れる回数
def divide_two(arg):
  c = 0
  while True:
    if c >= 2:
      break
    if arg % 2 != 0:
      break
    arg //= 2
    c += 1
  return c

# 素因数分解
def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a

import math
import fractions
import collections
from functools import reduce
main()

Measured memory_bytes: 5048
#include <iostream>
#include <string>
#include <vector>
#include <stack>
#include <map>
#include <algorithm>
#include <numeric>
#include <math.h>
#include <stdio.h>
#include <ctype.h>
using namespace std;

#define N_MAX   (100000)
#define LL_MAX_NUM (1LL<<60)
#define INF 1e7

typedef long long ll;
typedef long long int lli;

int main() {
    int x ,a, b;
    cin >> x >> a >> b;
    if (abs(x-a) < abs(x-b)) {
        cout << "A" << endl;
    } else {
        cout << "B" << endl;
    }
    return 0;
}

Measured memory_bytes: 256
#include<iostream>
using namespace std;
int main() {

	long long N, D;
	cin >> N >> D;

	double ans = 0;

	for (int i = 0; i < N; i++) {
		long long X, Y;
		cin >> X >> Y;
		if (X * X + Y * Y <= D * D) {
			ans++;
		}
	}

	cout << ans << endl;
}

Measured memory_bytes: 3784
a, b, k = gets.strip.split.map(&:to_i)


while (a % b != 0) do
	temp  = b
	b = a % b
	a = temp
	
end
c = []

(1..b).each do |i|
	if b % i == 0
		c << i
	end
end

puts c[-1 * k]

Measured memory_bytes: 1788