akhauriyash/Code-Regression huggingface dataset:
n,m,l=map(int,input().split())

#基本的にワーシャルフロイドの場合、行列式のリストで距離を保管する
from scipy.sparse import csr_matrix
from scipy.sparse import csgraph 
d = [[10**12 for i in range(n+1)] for i in range(n+1)]
for i in range(m):
    x,y,z = map(int,input().split())
    #有向グラフか無向グラフかによってここで場合わけが生じる
    d[x][y] = z
    d[y][x] = z
    
for i in range(n+1):
    d[i][i] = 0 #自身のところに行くコストは０
q=int(input())
que=[]
for _ in range(q):
    s,t=map(int,input().split())
    que.append((s,t))
       
csr=csr_matrix(d)
K=csgraph.shortest_path(csr,method="FW",directed=True)
e = [[10**12 for i in range(n+1)] for i in range(n+1)]

for i in range(1,n+1):
    for j in range(1,n+1):
        if K[i][j]<=l:
            e[i][j]=1
            
for i in range(n+1):
    e[i][i]=0
    

A=csr_matrix(e)
ANS=csgraph.shortest_path(A,method="FW",directed=True)

for some in que:
    s,t=some[0],some[1]
    if int(ANS[s][t])<10**12:
        print(int(ANS[s][t])-1)
    else:
        print(-1)




Measured memory_bytes: 29356
s = gets.chomp
stack = []
cnt = 0
stack << s[0]
1.upto(s.length-1) do |i|
	c = s[i]
	if stack[-1] == c || stack.length == 0
		stack << c
	elsif stack.length > 0
		# puts "i:#{i}"
		# p stack
		stack.pop
		cnt += 1
	end
end

puts cnt * 2


Measured memory_bytes: 19104
#include <bits/stdc++.h>
#define FIO ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define PI 3.141592653589793238462643383279502884L
#define lli long long int
#define d double
#define mod 1000000007
#define mx 200001
using namespace std;
lli n,k;
vector<vector<lli>> standard;
void mul(vector<vector<lli>>&m1,vector<vector<lli>>&m2){
	vector<vector<lli>> ck(n,vector<lli>(n));
	for(lli i=0;i<n;i++){
		for(lli j=0;j<n;j++){
			ck[i][j]=0;
			for(lli k=0;k<n;k++){
				ck[i][j]+= ((m1[i][k])%mod*(m2[k][j])%mod)%mod;
				if(ck[i][j]>=mod) ck[i][j]-=mod;
			}
		}
	}
	for(lli i=0;i<n;i++){
		for(lli j=0;j<n;j++) m1[i][j]=ck[i][j];
	}
}
void pw(vector<vector<lli>>&adjMat,lli e){
	if(e==1) return;
	pw(adjMat,e/2);
	mul(adjMat,adjMat);
	if(e%2==1) mul(adjMat,standard);
}
int main() {
	FIO;
	cin>>n>>k;
	vector<vector<lli>> adjMat(n,vector<lli>(n));
	standard.resize(n,vector<lli>(n));
	for(lli i=0;i<n;i++){
		for(lli j=0;j<n;++j){
			cin>>adjMat[i][j];
			standard[i][j]=adjMat[i][j];
		}
	}
	pw(adjMat,k);
	lli ans=0;
	for(lli i=0;i<n;i++){
		for(lli j=0;j<n;j++){
			ans+=adjMat[i][j];
			if(ans>=mod) ans-=mod;
		}
	}
	cout<<ans<<endl;
}

Measured memory_bytes: 512
from fractions import gcd
N, M = [int(x) for x in input().split()]
ans = 1
d = 1
if (N == 1):
    print(M)
else:
    while (d*d <= M):
        if (M//d * d != M): 
            d += 1
            continue
        d2 = M//d
        if (d*N <= M):
            ans = max(ans, d)
        if (d2*N <= M):
            ans = max(ans, d2)
        d += 1
    print(ans)


Measured memory_bytes: 64364
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define IOS                  \
    ios::sync_with_stdio(0); \
    cin.tie(0);              \
    cout.tie(0)
#define rep(i, a, b) for (int i = a; i < (b); ++i)
#define repd(i, a, b) for (int i = a; i >= (b); --i)
#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x).size()
template <typename H>
bool chmin(H &v1, const H v2)
{
    if (v1 > v2)
    {
        v1 = v2;
        return true;
    }
    return false;
}
template <typename H>
bool chmax(H &v1, const H v2)
{
    if (v1 < v2)
    {
        v1 = v2;
        return true;
    }
    return false;
}
typedef long long ll;
const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3fll;

int main()
{
    int a, b;
    cin >> a >> b;
    cout << (a + b) / 2 + ((a + b) % 2 != 0) << endl;
}


Measured memory_bytes: 3644
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using pint = pair<int,  int>;
using pll = pair<ll, ll>;
using edge = pair<int, ll>;
using graph = vector<vector<int>>; 
using WeightedGraph = vector<vector<edge>>;
const ll INF = 1LL << 60;
const int INF32 = 1 << 29;
const ll MOD = 1000000007;

int main() {
  ll n; cin >>n;
  vector<int> p(n);
  for(int i = 0; i < n; ++i)cin >>p[i];
  vector<ll> a(n), b(n);
  for(int i = 0; i < n; ++i){
    a[i]=30000*(i+1);
    b[i]+=30000*(n-i);
    b[p[i]-1]+=i;
  }
  for(int i = 0; i < n; ++i){
    cout << a[i];
    if(i==n-1){cout << endl;}
    else{cout << " ";}
  }
  for(int i = 0; i < n; ++i){
    cout << b[i];
    if(i==n-1){cout << endl;}
    else{cout << " ";}
  }
}


Measured memory_bytes: 1024
bingo_map = [[int(j) for j in input().split()] for i in range(3)]
n = int(input())
b_inputs = [int(input()) for i in range(n)]

for i in range(3):
    for j in range(3):
        if bingo_map[i][j] in b_inputs:
            bingo_map[i][j]=1
        else:
            bingo_map[i][j]=0

def check():
    for i in range(3):
        if sum(bingo_map[i])==3:
            return 'Yes'
                
    for j in range(3):
        if sum([bingo_map[k][j] for k in range(3)])==3:
            return 'Yes'

    if bingo_map[0][0] + bingo_map[1][1] + bingo_map[2][2]==3:
        return 'Yes'
    if bingo_map[0][2] + bingo_map[1][1] + bingo_map[2][0]==3:
        return 'Yes'
    return 'No'

print(check())



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

using namespace std;

int main()
{
 int n;
 cin>>n;
 string s;
 cin>>s;
 
 int tw=0,tr=0;
 for(int i=0;i<n;i++)
 {
     if(s[i]=='R')
     tr++;
     else tw++;
 }
 int mr=0;
 for(int i=0;i<tr;i++)
 {
if(s[i]=='R')
mr++;
 }
 int ans;
 tr-=mr;
 
 ans=tr;
 
 int i=0,j=n-1;
 while(i<n&&s[i]=='R')
 {
     i++;
 }
 while(j>=0&&s[j]=='W')
 {
     j--;
 }
 int r=0,w=0;
for(int k=i;k<=j;k++)
 {
     if(s[k]=='R')
     r++;
     else w++;
 }
 cout<<min(ans,min(r,w));
    return 0;
}



Measured memory_bytes: 3728
using System;
using System.Collections.Generic;
using System.Linq;
using System.Web;

namespace Competitive
{
    internal class Solution
    {
        public int N, M;

        public void Run()
        {
            {
                var line = Input.ReadIntArray();
                N = line[0];
                M = line[1];
            }

            long T = M * 1900 + (N - M) * 100;

            for (int i = 0; i < M; i++) T *= 2;

            Console.WriteLine(T);
        
        }
    }

    // libs ----------


    // common ----------

    internal static class Input
    {
        public static string ReadString()
        {
            string line = Console.ReadLine();
            return line;
        }

        public static int ReadInt()
        {
            string line = Console.ReadLine();
            return int.Parse(line);
        }

        public static int[] ReadIntArray()
        {
            string line = Console.ReadLine();
            return line.Split(' ').Select(int.Parse).ToArray();
        }

        public static long ReadLong()
        {
            string line = Console.ReadLine();
            return long.Parse(line);
        }

        public static long[] ReadLongArray()
        {
            string line = Console.ReadLine();
            return line.Split(' ').Select(long.Parse).ToArray();
        }

        public static double[] ReadDoubleArray()
        {
            string line = Console.ReadLine();
            return line.Split(' ').Select(double.Parse).ToArray();
        }
    }

    internal class Program
    {
        public static void Main(string[] args)
        {
            var s = new Solution();
            s.Run();
        }
    }
}

Measured memory_bytes: 13396
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MOD = 1e9+7;



int main(){
    ll A, B, N; cin >> A >> B >> N;
    ll ans = 0;
    if(N < B-1){
        cout << floor((A*N)/B) - A * floor(N / B) << endl;
        return 0;
    }
    /*for(int i = 1;; i++){
        ll X = B*i-1;
        if(X > N) break;
        ll temp = floor((A*X)/B)- A* floor(X / B);
        ans = max(ans, temp);
    }*/
    ll X = (N / B + 1) * B-1;
    while(X > N) X -= B;
    //cout << X << endl;
    cout << floor((A*X)/B)- A* floor(X / B) << endl;



}


Measured memory_bytes: 3784
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <cstdlib>
#include <set>
#include <utility>
#include <climits>

#define ll long long
#define ull unsigned long long
using namespace std;

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	
	ll sum = 0;
	long n;
	cin >> n;
	
	for (long i = 1; i <= n; ++i) {
		if (i % 5 && i % 3)
			sum += i;
	}
	cout << sum;
}

Measured memory_bytes: 3648
#include<bits/stdc++.h>
#define ft(i,l,r) for(register int i=l;i<=r;i++)
#define fd(i,r,l) for(register int i=r;i>=l;i--)
using namespace std;
int mx=-233,a[5];
int main()
{
    cin>>a[1]>>a[2]>>a[3];
    for(int i=1;i<=3;i++)
      for(int j=1;j<=3;j++)
        for(int k=1;k<=3;k++)
          if(i!=j&&i!=k&&j!=k)
            mx=max(mx,a[i]+a[j]*10+a[k]);
    cout<<mx;
    return 0;
}

Measured memory_bytes: 256
n, q = [int(x) for x in input().strip().split(" ")]
S = input().strip()
s, e = 0, n-1

import sys
qs = []
for line in sys.stdin:
    qs.append([x for x in line.strip().split(" ")])

for q in qs[::-1]:
    t, d = q
    if d == 'L':
        if S[s] == t:
            if s < n-1:
                s += 1
        if e < n-1:
            if S[e+1] == t:
                e += 1
    if d == 'R':
        if s > 0:
            if S[s-1] == t:
                s -= 1
        if S[e] == t:
            if e > 0:
                e -= 1
    if s == e:
        break
if s == e:
    print(0)
elif s < e:
    print(n - s - (n - 1 - e))


Measured memory_bytes: 28376
import itertools

N = int(input())
P = tuple([int(i) for i in input().split()])
Q = tuple([int(i) for i in input().split()])

ls = [i+1 for i in range(N)]
for i, p in enumerate(itertools.permutations(ls, N)):
    if p == P:
        a = i
    if p == Q:
        b = i

print(abs(a-b))

Measured memory_bytes: 3064
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		while(true) {
			int n = scanner.nextInt();	// 3 ≤ n ≤ 100
			int x = scanner.nextInt();	// 0 ≤ x ≤ 300
			if(n==0&&x==0) {
				break;
			}
			int num = 0;
			for(int i=1;i<=n-2;i++) {
				for(int j=i+1;j<=n-1;j++) {
					for(int k=j+1;k<=n;k++) {
						if (i+j+k==x) {
							num++;
						}
					}
				}
			}
			System.out.println(num);
			
		}
		scanner.close();
	}
}


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

#define rep(i,n) for(ll i=0;i<n;i++)
#define REP(i,a,n) for(ll i=a;i<n;i++)

typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef tuple<int,int,int> tiii;
typedef pair<ll, ll> pll;

const int INF = 100000000;
const ll LINF = 1e18+5;

int main() {

    ll A, B, K;
    cin >> A >> B >> K;
    if(A >=K) {
        cout << A-K << " " << B << endl;
    } else {
        B -= (K - A);
        A = 0;
        if(B < 0) {
            cout << 0 << "  " << 0 << endl;
        } else {
            cout << A << " "  << B << endl;
        }
    }
    return 0;
}

Measured memory_bytes: 256
from collections import deque
def main():
  h,w=map(int,input().split())
  hw=h*w
  maze=[list(input()) for i in range(h)]
  visited=[[hw]*w for i in range(h)]
  ans,q=0,deque()
  for i in range(h):
    for j in range(w):
      if maze[i][j]=='#':
        q.append((i,j))
        visited[i][j]=0
  while q:
    x,y=q.popleft()
    for i,j in ((0,1),(1,0),(-1,0),(0,-1)):
      newx,newy=x+i,y+j
      if 0<=newx<h and 0<=newy<w:
        if maze[newx][newy]!='#' and visited[newx][newy]==hw:
          visited[newx][newy]=visited[x][y]+1
          q.append((newx,newy))
          ans=max(ans,visited[newx][newy])
  return print(ans)
if __name__=='__main__':
  main()


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

#define TCLOOP() int tc; cin>>tc; while(tc--)

#define fa(x,v) for(auto x:v)
#define f(i,a,b) for(ll i=(ll)a;i<=(ll)b;i++)
#define rf(i,a,b) for(ll i=(ll)a;i>=(ll)b;i--)
#define spc " "
#define endl '\n'
#define ll long long
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define len(s) int(s.length())
#define sz(v) int(v.size())
#define MOD 1000000007

// Code Here

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    ll n; cin>>n;
    string a,b; cin>>a>>b;
    string c = "";
    f(i,0,n-1) c += a[i], c += b[i];
    cout<<c;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("Ofast")
#pragma GCC target("avx")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#define all(x) (x).begin(),(x).end()
#define rep(i,n) for(int (i)=0;i<(n);i++)
#define REP(i,m,n) for(int (i)=(m);(i)<(n);(i)++)
#define MOD 1000000007
#define fcout cout << fixed << setprecision(15)
#define int long long
#define yorn(f) puts((f)?"Yes":"No")
#define YORN(f) puts((f)?"YES":"NO")
typedef long long ll;
typedef pair<int, int> P;
int gcd(int a,int b){return b?gcd(b,a%b):a;};
int lcm(int a,int b){return a/gcd(a,b)*b;};
int mod(int a,int b){return (a+b-1)/b;};
template<typename A, size_t N, typename T>
void Fill(A(&array)[N],const T &val){std::fill((T*)array,(T*)(array+N),val);}
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;};



signed main() {
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(false);
    
    string s;
    cin >> s;
    int n = s.size();

    vector<int> mods(2020, 0);
    int nowmod = 0, now = 1;
    int ans = 0;
    for(int i = n - 1; i >= 0; i--) {
        mods[nowmod]++;
        nowmod += (s[i] - '0') * now, nowmod %= 2019;
        ans += mods[nowmod];
        now *= 10, now %= 2019;
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 3712
#include <stdio.h>
#include <math.h>

int main(int argc, char const *argv[])
{
	int n, n1=1, n2, a[100], a1, b[100], i1=1, i2, ans=0, flag;
	scanf("%d", &n);
	if (n<10)
	{
		printf("%d\n", 0);
		return 0;
	}
	for (int i = 0; i < 100; ++i)
	{
		b[i]=0;
	}
	a[0]=2;
	for (int i = 3; i <= n; ++i)
	{
		flag=0;
		for (int j = 0; j < i1; ++j)
		{
			if (i%a[j]==0) flag=1;
		}
		if (flag==0)
		{
			a[i1]=i;
			i1++;
		}
	}
	for (int i = 0; i < i1; ++i)
	{
		a1=a[i];
		while (a1<=n)
		{
			b[i]+=n/a1;
			a1*=a[i];
		}
	}
	for (int i = 0; i < i1; ++i)
	{
		for (int j = i+1; j < i1; ++j)
		{
			for (int k = 0; k < i1; ++k)
			{
				if (k!=i && k!=j)
				{
					if (b[i]>=4 && b[j]>=4 && b[k] >=2) ans++;
				}
			}
		}
	}
	for (int i = 0; i < i1; ++i)
	{
		for (int j = 0; j < i1; ++j)
		{
			if (j>7) break;
			if (j!=i)
			{
				if (b[i]>=4 && b[j]>=14) ans++;
			}
		}
	}
	for (int i = 0; i < i1; ++i)
	{
		for (int j = 0; j < i1; ++j)
		{
			if (j>5) break;
			if (j!=i)
			{
				if (b[i]>=2 && b[j]>=24) ans++;
			}
		}
	}
	for (int i = 0; i < i1; ++i)
	{
		if (b[i]>=74) ans++;
	}
	printf("%d\n", ans);
	return 0;
}

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

int main(){
  long long A, B, X, min, max;
  cin >> A >> B >> X;
  
  min=A/X;
  max=B/X;
  
  if(A%X==0)
    cout << max-min+1 << endl;
  else
    cout << max-min << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <iomanip>
#include <utility>
#include <cmath>
#include <random>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <string>
#include <algorithm>
using namespace std;

#define rep(i,n) for(int i = 0; i<n; ++i)
const int INF = 100100100;
const int MOD = (int)1e9 + 7;
typedef long long ll;

int main(){
    set <int> is;
    rep(i,3){int tmp ; cin>>tmp; is.insert(tmp);}
    cout<<is.size()<<endl;return 0;
}

Measured memory_bytes: 256
#include<stdio.h>
#include<math.h>
int main(){
  int a,b,h,m;
  double as,bs,work,s;
  scanf("%d%d%d%d",&a,&b,&h,&m);
  as=h*360.0/12.0+m*360.0/12.0/60;
  bs=m*360.0/60.0;
  if(as<bs){
    work=as;
    as=bs;
    bs=work;
  }
  s=as-bs;
  if(s>180)s=360-s;
  printf("%.11lf\n",sqrt((double)(a*a+b*b)-2.0*a*b*cos(M_PI/180.0*s)));
  return 0;
}

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

using namespace std;

typedef long long ll;

const ll MOD = 1e9 + 7;

ll mod(ll a, ll b){
  a %= b;
  return a < 0 ? a + b : a;
}

ll powmod(ll a, ll b){
  if(b == 0) return 1;
  if(b & 1) {
    return a * powmod(a, b - 1) % MOD;
  } else {
    ll d = powmod(a, b / 2) % MOD;
    return d * d % MOD;
  }
}

ll sub(ll a, ll b){
  a %= MOD, b %= MOD;
  a -= b;
  return a < 0 ? a + MOD : a;
}

ll inv(ll a){
	return powmod(a, MOD - 2);
}

// X^(-1) = X^(p-2) (mod p) (Fermat's little theorem)

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

	ll N, K;
	cin >> N >> K;

	vector<ll> A(N);
	rep(i, N) cin >> A[i];

	ll now = 0;
	for(int i = 0; i < N; i++){
		for(int j = i+1; j < N; j++){
			if(A[i] > A[j]) now++;
		}
	}

	ll next = 0;
	for(int i = 0; i < N; i++){
		for(int j = 0; j < N; j++){
			if(A[i] > A[j]) next++;
		}
	}

	ll ans = now;
	ans *= K;
	ans %= MOD;

	ll add = next;
	add *= K;
	add %= MOD;

	add *= K-1;
	add %= MOD;

	add *= inv(2LL);
	add %= MOD;
	
	ans += add;
	ans %= MOD;

	cout << ans << endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <iomanip>
#include <cmath>
#include <queue>
#include <stack>
#include <cstdlib>
#include <map>
#include <iomanip>
#include <set>
#include <stdio.h>
#include <ctype.h>
#include <random>
#include <string.h>
using namespace std;
#define pie 3.141592653589793238462643383279
#define mod 1000000007
#define int long long
#define P pair<int,int>
#define all(vec) vec.begin(),vec.end()

int gcd(int x, int y) {
	if (y == 0)return x;
	return gcd(y, x%y);
}
int lcm(int x, int y) {
	return x / gcd(x, y)*y;
}
int kai(int x, int y) {
	int res = 1;
	for (int i = x - y + 1; i <= x; i++) {
		res *= i; res %= mod;
	}
	return res;
}
int mod_pow(int x, int y, int m) {
	int res = 1;
	while (y > 0) {
		if (y & 1) {
			res = res * x % m;
		}
		x = x * x % m;
		y >>= 1;
	}
	return res;
}

int comb(int x, int y) {
	if (y > x)return 0;
	return kai(x, y) * mod_pow(kai(y, y), mod - 2, mod) % mod;
}

int n, m, h[100010];
vector<int> vec[100010];
int ans;

signed main() {
	cin >> n >> m;
	for (int i = 1; i <= n; i++)cin >> h[i];
	for (int i = 0; i < m; i++) {
		int a, b; cin >> a >> b;
		vec[a].push_back(b);
		vec[b].push_back(a);
	}
	for (int i = 1; i <= n; i++) {
		bool bl = true;
		for (int j = 0; j < (int)vec[i].size(); j++)if (h[vec[i][j]] >= h[i])bl = false;
		if (bl)ans++;
	}
	cout << ans << endl;
}


Measured memory_bytes: 10244
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = Integer.parseInt(in.nextLine());
        String s = in.nextLine();
        int[] w = new int[n], e = new int[n];
        w[0] = s.charAt(0) == 'W' ? 1 : 0;
        for(int i = 1; i < n; i++) {
            w[i] = w[i - 1] + (s.charAt(i) == 'W' ? 1 : 0);
        }
        e[n - 1] = s.charAt(n - 1) == 'E' ? 1 : 0;
        for(int i = n - 2; i >= 0; i--) {
            e[i] = e[i + 1] + (s.charAt(i) == 'E' ? 1 : 0);
        }
        int ans = Math.min(w[n - 1], e[0]);
        for(int i = 1 ; i < n - 1; i++) {
            ans = Math.min(ans, w[i - 1] + e[i + 1]);
        }
        System.out.println(ans);
    }
}

Measured memory_bytes: 31084
#include <iostream>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <stack>
#include <queue>
#include <algorithm>
#include <numeric>
#include <functional>
using namespace std;

#define Rep(b, e, i) for(int i = b; i <= e; i++)
#define rep(n, i) Rep(0, n-1, i)
#define MAX 200000
#define INF (ll)1e10
#define MOD 1000000007

typedef long long ll;
typedef pair<ll, ll> P;
typedef std::priority_queue<int> IntPrioQueue; //Z->A
typedef std::priority_queue<int, std::vector<int>, std::greater<int> > IntReversePrioQueue; //A->Z


int dx4[4]={1,0,-1,0};
int dy4[4]={0,1,0,-1};

ll R, C;
ll sx, sy;
ll gx, gy;
char map[51][51];
ll steps[51][51];

ll bfs(){
    queue<P> que;

    rep(R, y) rep(C, x) steps[y][x] = INF;
    que.push(P(sx, sy));
    steps[sy][sx] = 1;
    while(que.size()){
        P p = que.front(); que.pop();
        if (p.first == gx && p.second == gy) break;
        rep (4, i) {
            ll nx = p.first + dx4[i];
            ll ny = p.second + dy4[i];
            if (nx >= 0 && nx < C && ny >= 0 && ny < R){
                if (map[ny][nx] == '.' && steps[ny][nx] == INF) {
                    que.push(P(nx, ny));
                    steps[ny][nx] = steps[p.second][p.first] + 1;
                }
            }
        }
    }
    return steps[gy][gx];
}


void solve(void){
    cin >> R >> C;
    rep (R, y) scanf("%s\n", &map[y]);
    sx = sy = 0;
    gx = C-1, gy = R-1;
    ll step = bfs();
    if (step == INF) printf("-1\n");
    else {
        ll ans = 0;
        rep(R, i) rep(C, j) {
            if (map[i][j] == '.') ans++;
        }
        printf("%lld\n", ans-step);
    }
}

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


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <algorithm>
#include <string>
#include <cmath>
#include <cstdio>
#include <iomanip>
#include <fstream>
#include <cassert>
#include <cstring>
#include <unordered_set>
#include <unordered_map>
#include <numeric>
#include <ctime>
#include <bitset>
#include <complex>
#include <chrono>
#include <random>
#include <functional>

using namespace std;

#define rep(i, n) for (int i = 0; i < (n); ++i)
#define sz(x) int(x.size())
typedef long long ll;

using ipair = pair<int, int>;

ll INF = 1e16+7;
ll mod = 1e9+7;

bool operator>(const ipair a,const ipair b){return a.first > b.first;}


const double PI=3.14159265358979323846;

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

  vector<int> candle(N);
  rep(i, N) cin >> candle[i];

  int ans = 1e9;

  rep(l, N){
    int r = l + (K-1);
    if(r > N-1){
      break;
    }
    ans = min(ans, abs(candle[l]) + (candle[r] - candle[l]));
    ans = min(ans, abs(candle[r]) + (candle[r] - candle[l]));
  }

  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 640
#include<stdio.h>
#include<string.h>
#include<stdlib.h>

void push(int);
int pop();

int head,Str[100000];

int main() {

  char str[100000];
  int a,b;
  head=0;

  while(scanf("%s",str) != EOF) {
    
    if(str[0] == '+') {
      a = pop();
      b = pop();
      push(a+b);
      continue;
    }

    if(str[0] == '-') {
      b = pop();
      a = pop();
      push(a-b);
      continue;
    }
    
    if(str[0] == '*') {
      a = pop();
      b = pop();
      push(a*b);
      continue;
    }
    
    push(atoi(str));
    
  }
  
  printf("%d\n",pop());
  
  return 0;

}

void push(int a) {

  head++;
  Str[head] = a;

}

int pop(void) {
  
  head--;
  return Str[head+1];

}


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

using namespace std;

typedef long long ll;
typedef pair<int, int> P;
typedef vector<int> vi;
typedef vector<ll> vll;
// #define int long long
#define pb push_back
#define mp make_pair
#define eps 1e-9
#define INF 2000000000               // 2e9
#define LLINF 2000000000000000000ll  // 2e18 (llmax:9e18)
#define fi first
#define sec second
#define all(x) (x).begin(), (x).end()
#define sq(x) ((x) * (x))
#define dmp(x) cerr << #x << ": " << x << endl;

template <class T>
void chmin(T &a, const T &b) {
  if (a > b) a = b;
}
template <class T>
void chmax(T &a, const T &b) {
  if (a < b) a = b;
}

template <class T>
using MaxHeap = priority_queue<T>;
template <class T>
using MinHeap = priority_queue<T, vector<T>, greater<T>>;
template <class T>
vector<T> vect(int len, T elem) {
  return vector<T>(len, elem);
}

template <class T, class U>
ostream &operator<<(ostream &os, const pair<T, U> &p) {
  os << p.fi << ',' << p.sec;
  return os;
}
template <class T, class U>
istream &operator>>(istream &is, pair<T, U> &p) {
  is >> p.fi >> p.sec;
  return is;
}
template <class T>
ostream &operator<<(ostream &os, const vector<T> &vec) {
  for (int i = 0; i < vec.size(); i++) {
    os << vec[i];
    if (i + 1 < vec.size()) os << ' ';
  }
  return os;
}
template <class T>
istream &operator>>(istream &is, vector<T> &vec) {
  for (int i = 0; i < vec.size(); i++) is >> vec[i];
  return is;
}
void fastio() {
  cin.tie(0);
  ios::sync_with_stdio(0);
  cout << fixed << setprecision(20);
}

#define endl "\n"

void solve() {
  int x;
  cin >> x;
  cout << x / 500 * 1000 + (x % 500) / 5 * 5 << endl;
  return;
}

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


Measured memory_bytes: 256
n,k=map(int,input().split())
arr=list(map(int,input().split()))
for _ in range(min(200,k)):
  tmp=[0]*n
  for i in range(n):
    if i+1<n:
      tmp[i+1]+=1
      if i+arr[i]+1<n:
        tmp[i+arr[i]+1]+=-1
    if i-1>=0:
      tmp[i]+=-1
      if i-arr[i]>=0:
        tmp[i-arr[i]]+=1
      else:
        tmp[0]+=1
  for i in range(1,n):
    tmp[i]+=tmp[i-1]
  for i in range(n):
    tmp[i]+=1
  arr=tmp
print(*arr)

Measured memory_bytes: 169420
#pragma comment(linker, "/STACK:640000000")
#include <bits/stdc++.h>

#define pb push_back
#define ppb pop_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()
#define ll long long
#define bit __builtin_popcountll
#define sqr(x) (x) * (x)
#define forit(it,S) for(__typeof((S).begin()) it = (S).begin(); it != (S).end(); it++)

using namespace std;

typedef pair<int, int> pii;

const double eps = 1e-9;
const double pi = acos(-1.0);

const int INF = (int)1e9;

int main() {
	#ifdef LOCAL
	freopen("a.in", "r", stdin);
	freopen("a.out", "w", stdout);
	#endif

	int n; cin >> n;

	ll sum = 0;
	int mi = INF;

	for (int i = 0; i < n; i++) {
		int x, y; scanf("%d%d",&x ,&y);
		sum += x;
		if (x > y) {
			mi = min(mi, y);
		}
	}

	if (mi == INF) {
		cout << 0 << endl;
	} else {
		cout << sum - mi << endl;
	}

	return 0;
}

Measured memory_bytes: 256
#include<stdio.h>
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int H,A,i=0;
    scanf("%d",&H);
    scanf("%d",&A);
    while(H>0)
    {
        H=H-A;
        i++;

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


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define rep(i,n) for(int i = 0;i < (n);++i)
#define reps(i,n) for(int i = 1;i <= (n);++i)
using namespace std;
int main(){
  int a,b;
  cin >> a >> b;
  if(a <= 8 && b <= 8) cout << "Yay!\n";
  else cout << ":(\n";
  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define ss second
#define ff first
#define all(x) x.begin(), x.end()

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

const int oo = 1e9 + 7;
const ll mod = 1e9 + 7,maxn = 100000000;
const double PI = acos(-1);


int main (){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int a, b, c;
    cin >> a >> b >> c;

    if (b - a == c - b) cout << "YES" << endl;
    else cout << "NO" << endl;
    return 0;
}

Measured memory_bytes: 256
import sys
import queue
import heapq

# input
H, W = map(int, sys.stdin.readline().strip().split())
Ch, Cw = map(int, sys.stdin.readline().strip().split())
Dh, Dw = map(int, sys.stdin.readline().strip().split())
Ch -= 1
Cw -= 1
Dh -= 1
Dw -= 1

S = []
for _ in range(H):
    s = str(input())
    S.append(list(s))


# solve
q = []
heapq.heappush(q, (0, (Ch, Cw)))
fp = [[float('inf')] * W for _ in range(H)]
fp[Ch][Cw] = 0
while q:
    count, coo = heapq.heappop(q)
    uh, uw = coo

    if count > fp[uh][uw]:
        continue

    for dh, dw in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
        vh = uh + dh
        vw = uw + dw

        # 盤上にいるか確認
        if vh < 0 or vh >= H:
            continue
        if vw < 0 or vw >= W:
            continue

        # 壁の確認
        if S[vh][vw] == "#":
            continue

        # 到達済みか確認
        if fp[vh][vw] <= fp[uh][uw]:
            continue

        # 探索候補地に追加
        fp[vh][vw] = fp[uh][uw]
        heapq.heappush(q, (fp[vh][vw], (vh, vw)))

    for dh in range(-2, 3):
        for dw in range(-2, 3):
            if (dh, dw) in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
                continue

            vh = uh + dh
            vw = uw + dw

            # 盤上にいるか確認
            if vh < 0 or vh >= H:
                continue
            if vw < 0 or vw >= W:
                continue

            # 壁の確認
            if S[vh][vw] == "#":
                continue

            # 到達済みか確認
            if fp[vh][vw] <= fp[uh][uw] + 1:
                continue

            # 探索候補地に追加
            fp[vh][vw] = fp[uh][uw] + 1
            heapq.heappush(q, (fp[uh][uw] + 1, (vh, vw)))


if fp[Dh][Dw] == float('inf'):
    print(-1)
else:
    print(fp[Dh][Dw])


Measured memory_bytes: 163228
#include<stdio.h>
#define MAX 2000000

int H,A[MAX+1],a;

void maxH(int i){
  int l,r,largest;
  l=2*i;
  r=2*i+1;
if(l<=H&&A[l]>A[i])largest=l;
else largest=i;
if(r<=H&&A[r]>A[largest])largest=r;

if(largest!=i){
  a=A[i];
  A[i]=A[largest];
  A[largest]=a;
  maxH(largest);
}
}
int main(){
int i;
  scanf("%d",&H);
  for(i=1;i<=H;i++)scanf("%d",&A[i]);
  for(i=H/2;i>=1;i--)maxH(i);
  for(i=1;i<=H;i++){
    printf(" %d",A[i]);
  }
printf("\n");
return 0;
}



Measured memory_bytes: 3684
for i in range(10**6):
  a,b,c = map(str,input().split())
  if b == "?":
    break
  else:
    if b == "+":
      print(int(a)+int(c))
    elif b == "-":
      print(int(a)-int(c))
    elif b == "*":
      print(int(a)*int(c))
    elif b == "/":
      print(int(a)//int(c))


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

struct StNode
{
  StNode* m_poParnt;
  StNode* m_poLeft;
  StNode* m_poRigt;
  int m_nKey;

  StNode(int nNo) :
    m_poParnt(nullptr), m_poLeft(nullptr), m_poRigt(nullptr), m_nKey(nNo)
  { }
};

void fnInsert(StNode*& rpoRoot, StNode* poNewNod)
{
  StNode* poParnt = nullptr;
  StNode* poNode = rpoRoot;

  while (poNode != nullptr)
  {
    poParnt = poNode;
    if (poNewNod->m_nKey < poNode->m_nKey)
      poNode = poNode->m_poLeft;
    else
      poNode = poNode->m_poRigt;
  }

  poNewNod->m_poParnt = poParnt;
  if (poParnt == nullptr)
    rpoRoot = poNewNod;
  else if (poNewNod->m_nKey < poParnt->m_nKey)
    poParnt->m_poLeft = poNewNod;
  else
    poParnt->m_poRigt = poNewNod;
}

StNode* fnFind(StNode* poRoot, int nNo)
{
  StNode* poNode = poRoot;
  while (poNode != nullptr)
    if (nNo == poNode->m_nKey)
      return poNode;
    else if (nNo < poNode->m_nKey)
      poNode = poNode->m_poLeft;
    else
      poNode = poNode->m_poRigt;

  return nullptr;
}

void fnInOrder(StNode* poNode)
{
  if (poNode == nullptr)  return;

  fnInOrder(poNode->m_poLeft);
  cout << " " << poNode->m_nKey;
  fnInOrder(poNode->m_poRigt);
}

void fnPreOrder(StNode* poNode)
{
  if (poNode == nullptr)  return;

  cout << " " << poNode->m_nKey;
  fnPreOrder(poNode->m_poLeft);
  fnPreOrder(poNode->m_poRigt);
}

void fnBinSchTree(StNode*& rpoRoot)
{
  int nMaxSiz;
  cin >> nMaxSiz;

  for (int i = 0; i < nMaxSiz; ++i)
  {
    string sCmd;
    cin >> sCmd;
    if (sCmd[0] == 'i')
    {
      int nNo;
      cin >> nNo;
      StNode* poNewNod = new StNode(nNo);
      fnInsert(rpoRoot, poNewNod);
    }
    if (sCmd[0] == 'f')
    {
      int nNo;
      cin >> nNo;
      if (fnFind(rpoRoot, nNo))
        cout << "yes" << endl;
      else
        cout << "no" << endl;
    }
    if (sCmd[0] == 'p')
    {
      fnInOrder(rpoRoot);
      cout << endl;
      fnPreOrder(rpoRoot);
      cout << endl;
    }
  }
}

void fnPstOrder(StNode* poNode)
{
  if (poNode == nullptr)  return;

  fnPstOrder(poNode->m_poLeft);
  fnPstOrder(poNode->m_poRigt);
  delete poNode;
}

int main()
{
  cin.tie(0);
  ios::sync_with_stdio(false);
  StNode* poRoot = nullptr;

  fnBinSchTree(poRoot);
  fnPstOrder(poRoot);
  return 0;
}

Measured memory_bytes: 22000
N, X, M = [int(_) for _ in input().split()]

def f(x, m):
    return x % m

P = [-1 for _ in range(M+1)]

A = [X]
for i in range(N-1):
    v = f(A[-1] ** 2, M)
    A.append(v)
    if P[v] != -1:
        break
    P[v] = i

v = f(A[-1] ** 2, M)
idx = P[v]

S = sum(A[idx+1:])
q, r = divmod(N - len(A), len(A) - idx - 1)

ans = sum(A) + q * S + sum(A[idx+1:idx+1+r])
print(ans)


Measured memory_bytes: 13652
#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 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)--)
//#pragma GCC optimize ("-O3") 
#ifdef YANG33
#include "mydebug.hpp"
#else
#define DD(x) 
#endif
const int INF = 1e9;                          const LL LINF = 1e16;
const LL MOD = 1000000007;                    const double PI = acos(-1.0);

/* -----  2019/04/27  Problem: ABC 125 A / Link: http://abc125.contest.atcoder.jp/tasks/abc125_a  ----- */


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

	LL A, B, T; cin >> A >> B >> T;
	LL ans = 0;
	FOR(i, 1, 22) {
		LL a = A * i;
		if (a <= T) {
			ans += B;
		}
	}

	cout << (ans) << "\n";

	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>

#define endl "\n"
#define ll long long
#define pb emplace_back
#define fi first
#define se second
#define pll pair<ll, ll>
#define ull unsigned long long
#define ld long double

#define debug(x) cout<<#x<<" :: "<<x<<endl;
#define debug2(x,y) cout<<#x<<" :: "<<x<<"\t"<<#y<<" :: "<<y<<endl;
#define debug3(x,y,z) cout<<#x<<" :: "<<x<<"\t"<<#y<<" :: "<<y<<"\t"<<#z<<" :: "<<z<<endl;

#define rep(i,n) for(ll i=0;i<(n);i++)
#define repr(i,n) for(ll i=n-1; i>=0; i--)
#define repa(i,a,b) for(ll i=(a);i<=(b);i++)
#define all(x) (x).begin(), (x).end()
#define ordered_set tree<int , null_type, less<int> , rb_tree_tag, tree_order_statistics_node_update>
/*
 Ordered set docs:
 order_of_key (k) : Number of items strictly smaller than k .
 find_by_order(k) : K-th element in a set (counting from zero).
*/
#define blc boost::lexical_cast<long long>
#define fast ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
using namespace std;
using namespace __gnu_pbds;
const int MOD = 1e9+7;

ll add(ll x, ll y) {ll res=x+y; return(res>=MOD?res-MOD:res);}

ll sub(ll x, ll y) {ll res=x-y; return(res<0?res+MOD:res);}

ll lcm(ll x, ll y) {ll res=(x*y)/__gcd(x,y); return res;}

ll powerLL(ll x, ll n, ll mod) 
{ 
    ll result = 1; 
    while (n) { if (n & 1) result = (result%mod * x%mod) % mod; n = n / 2; x = (x%mod * x%mod) % mod; } return result; 
} 

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

void solve()
{
    string s;
    cin>>s;
    ll n = s.length();
    ll res = 0;
    rep(i,n)
    {
    	res += s[i]-'0';
    }
    if(res%9 == 0)
    	cout<<"Yes"<<endl;
	else
		cout<<"No"<<endl;
}
int32_t main()
{
    fast;
    int t;
    t=1;
    //cin>>t;
    while(t--)
        solve();
    return 0; 
}

Measured memory_bytes: 3772
#define LOCAL

#undef _GLIBCXX_DEBUG

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

#define IOS ios::sync_with_stdio(false);cin.tie(0)
#define all(x) x.begin(), x.end()
#define ff first
#define ss second
#define MOD 1000000007LL
#define LLINF 100000000000000005LL
#define INF (int)1e9+1
#define pb push_back

// Copied from Gennady-Korotkevich's template

template <typename A, typename B>
string to_string(pair<A, B> p);

template <typename A, typename B, typename C>
string to_string(tuple<A, B, C> p);

template <typename A, typename B, typename C, typename D>
string to_string(tuple<A, B, C, D> p);

string to_string(const string& s) {
	return '"' + s + '"';
}

string to_string(const char* s) {
	return to_string((string)s);
}

string to_string(bool b) {
	return (b ? "true" : "false");
}

string to_string(vector<bool> v) {
	bool first = true;
	string res = "{";
	for (int i = 0; i < static_cast<int>(v.size()); i++) {
		if (!first) {
			res += ", ";
		}
		first = false;
		res += to_string(v[i]);
	}
	res += "}\n";
	return res;
}

template <size_t N>
string to_string(bitset<N> v) {
	string res = "";
	for (size_t i = 0; i < N; i++) {
		res += static_cast<char>('0' + v[i]);
	}
	return res;
}

template <typename A>
string to_string(A v) {
	bool first = true;
	string res = "{";
	for (const auto& x : v) {
		if (!first) {
			res += ", ";
		}
		first = false;
		res += to_string(x);
	}
	res += "}\n";
	return res;
}

template <typename A, typename B>
string to_string(pair<A, B> p) {
	return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}

template <typename A, typename B, typename C>
string to_string(tuple<A, B, C> p) {
	return "(" + to_string(get<0>(p)) + ", " + to_string(get<1>(p)) + ", " + to_string(get<2>(p)) + ")";
}

template <typename A, typename B, typename C, typename D>
string to_string(tuple<A, B, C, D> p) {
	return "(" + to_string(get<0>(p)) + ", " + to_string(get<1>(p)) + ", " + to_string(get<2>(p)) + ", " + to_string(get<3>(p)) + ")";
}

template <typename A, typename B, typename C, typename D, typename E>
string to_string(tuple<A, B, C, D, E> p) {
	return "(" + to_string(get<0>(p)) + ", " + to_string(get<1>(p)) + ", " + to_string(get<2>(p)) + ", " + to_string(get<3>(p)) + "," + to_string(get<4>(p)) + ")";
}

void debug_out() {
	cerr << endl;
}

template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
	cerr << " " << to_string(H);
	debug_out(T...);
}

#ifdef LOCAL
#define debug(...) cerr << "\n[" << #__VA_ARGS__ << "]:\n", debug_out(__VA_ARGS__)
#else
#define debug(...) 42
#endif

// End of Gennady-Korotkevich's template 

using llong = long long;
using PII = pair<int, int>;

int main() {
	IOS;
	string s, t;
	cin >> s >> t;
	int ans = t.length();
	for (int i = 0; i < s.length()-t.length()+1 ; i++) {
		int cnt = 0;
		for (int j = 0; j < t.length(); j++) {
			if (s[i+j] != t[j]) cnt++;
		}
		ans = min(ans, cnt);
	}
	cout << ans;
}


Measured memory_bytes: 3644
#include <iostream>
#include <cmath>
#include <vector>
#include <map>
#include <set>
#include <string>
#include <cstring>
#include <queue>
#include <ctime>
#include <cassert>
#include <cstdio>
#include <algorithm>
#include <unordered_set>
#include <unordered_map>
#include <bitset>

using namespace std;

#define fr first
#define sc second
#define mp make_pair
#define pb push_back
#define epr(...) fprintf(stderr, __VA_ARGS__)
#define db(x) cerr << #x << " = " << x << endl
#define db2(x, y) cerr << "(" << #x << ", " << #y << ") = (" << x << ", " << y << ")\n"; 
#define db3(x, y, z) cerr << "(" << #x << ", " << #y << ", " << #z << ") = (" << x << ", " << y << ", " << z << ")\n"
#define all(a) (a).begin(), (a).end()
#define sz(a) (int)a.size()

#define equal equalll
#define less lesss
const int N = 1e6 + 10;
const long long INF = 1e9 + 19;
typedef long long ll;

int n, a, b;
char s[N];

void read() {
    scanf("%d%d%d", &n, &a, &b);
    scanf("%s", s);
}

void solve() {
    int cntA = 0;
    int cntB = 0;
    for (int i = 0; i < n; i++) {
        bool res = 0;
        if (s[i] == 'a' && cntA + cntB < a + b) {
            cntA++;
            res = 1;
        }
        if (s[i] == 'b' && cntA + cntB < a + b && cntB < b) {
            res = 1;
            cntB++;
        }

        if (res)
            puts("Yes");
        else
            puts("No");
    }

}

void stress() {

}

int main(){
#ifdef MY_DEBUG
    freopen("in", "r", stdin);
    //freopen("out", "w", stdout);
#endif
    if (1) {
        int k = 1;
        for (int tt = 0; tt < k; tt++) {
            read();
            solve();
        }
    }
    else {
        stress();
    }

    return 0;
}


Measured memory_bytes: 768
n = int(input())
xy = []
for _ in range(n):
  xy.append(list(map(int, input().split(' '))))

xy = sorted(xy)
cnt = {}
if n == 1:
  ans = 1
else:
  for i in range(n-1):
    for j in range(i+1,n):
      if i == j:
        continue
      else:
        dx = xy[j][0] - xy[i][0]
        dy = xy[j][1] - xy[i][1]
        k = ','.join([str(dx), str(dy)])
        if k in cnt.keys():
          cnt[k] += 1
        else:
          cnt[k] = 1
  ans = n - max(cnt.values())
print(ans)

Measured memory_bytes: 3188
/*
 * Author : Andrew J
*/
#include <bits/stdc++.h>
using namespace std;
#define rall(x) x.rbegin() , x.rend()
#define all(x) x.begin() , x.end()
#define fi first
#define se second
#define pb push_back
using ll = long long;
using ii = pair <int , int>;
using di = pair <double , int>;
using minHeap = priority_queue <di , vector <di> , greater <di>>;
void in(int &x);
const double INF = 1e18;
const int N = 1050;
#define singleCase
// #define multipleCase
int xs, ys, xf, yf, n;
double dist[N][N], x[N], y[N], r[N], d[N];
bool vis[N];

double distBetweenPoints(double x1 , double y1 , double x2 , double y2) {
  return sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2));
}

double getDist(int u , int v) {
  double shortestPath = distBetweenPoints(x[u] , y[u] , x[v] , y[v]);
  return max(0.0 , shortestPath - r[u] - r[v]);
}

void work() {
  scanf("%d%d%d%d%d" , &xs , &ys , &xf , &yf , &n);
  x[0] = xs, y[0] = ys, r[0] = 0;
  x[n + 1] = xf, y[n + 1] = yf, r[n + 1] = 0;
  for (int i = 1 ; i <= n ; i++) {
    scanf("%lf%lf%lf" , &x[i] , &y[i] , &r[i]);
  }
  fill (d , d + N , INF);
  for (int i = 0 ; i <= n + 1 ; i++) {
    for (int j = 1 + i ; j <= n + 1 ; j++) {
      dist[i][j] = getDist(i , j);
      dist[j][i] = dist[i][j];
    }
  }
  minHeap pq;
  pq.push({0 , 0});
  double sol = -1;
  while (pq.size()) {
    di cur = pq.top(); pq.pop();
    double cd = cur.fi;
    int u = cur.se;
    if (vis[u]) continue;
    vis[u] = 1, d[u] = cd;
    if (u == n + 1) {
      sol = cd;
      break;
    }
    for (int v = 0 ; v <= n + 1 ; v++) {
      if (d[v] > cd + dist[u][v]) {
        pq.push({cd + dist[u][v] , v});
      }
    }
  }
  printf("%.10lf\n" , sol);
  return;
}

int main() {
  #ifdef multipleCase
    int nQ; in(nQ);
    while (nQ--)
      work();
  #endif
  #ifdef singleCase
    work();
  #endif
  return 0;
}

void in(int &x) {
	bool neg = false;
	register int c;
	x = 0;
	c = getchar();
	if(c == '-') {
		neg = true;
		c = getchar();
	}
	for (; c > 47 && c < 58; c = getchar())
	  x = (x << 1) + (x << 3) + c - 48;
	if (neg) x *= -1;
}


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


int main() {
  
  string S,T;
  cin>>S>>T;
  
  int sw=0;
  
  if(S.at(0)==T.at(0)){
    sw++;
  }
  
  if(S.at(1)==T.at(1)){
    sw++;
  }
  
   if(S.at(2)==T.at(2)){
    sw++;
  }
     
  cout<<sw<<endl;
}


Measured memory_bytes: 256
import sys,collections,math;sys.setrecursionlimit(10**7)
def Is(): return [int(x) for x in sys.stdin.readline().split()]
def Ss(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def S(): return input()

n,k = Is()
ls = Is()
_1 = ls.index(1)
ans = []
for i in range(_1-k+1,_1+k):
    ans.append(math.ceil(i/(k-1))+math.ceil((n-1-i)/(k-1)))
print(min(ans))

Measured memory_bytes: 14124
import sys
input = sys.stdin.readline
import math
# キュー(FIFO)
from collections import deque
from operator import itemgetter


N = int(input())
XY1 = []
XY2 = []
for _ in range(N):
    x, y = map(int, input().split())
    theta = math.atan2(y, x)
    if y == 0 and x < 0:
        theta -= 2*math.pi
    if theta < 0:
        XY1.append((x, y, theta))
    else:
        XY2.append((x, y, theta))

XY1.sort(key=itemgetter(2))
XY2.sort(key=itemgetter(2))

q1 = deque()
q2 = deque()
for xy1 in XY1:
    q1.append(xy1)
for xy2 in XY2:
    q2.append(xy2)

ans = 0
for _ in range(N+4):
    px, py = 0, 0
    mx, my = 0, 0
    for xy1 in q1:
        px += xy1[0]
        py += xy1[1]
    for xy2 in q2:
        mx += xy2[0]
        my += xy2[1]
    dp = math.sqrt(px**2+py**2)
    if dp > ans:
        ans = dp
    dm = math.sqrt(mx**2+my**2)
    if dm > ans:
        ans = dm
    
    if len(q1) == 0:
        xy2 = q2.popleft()
        q1.append(xy2)
    elif len(q2) == 0:
        xy1 = q1.popleft()
        q2.append(xy1)
    else:
        xy1 = q1[0]
        xy2 = q2[0]
        theta1 = xy1[2]
        theta2 = xy2[2]
        if theta1 + math.pi < theta2:
            q1.popleft()
            q2.append((xy1[0], xy1[1], theta1+2*math.pi))
        else:
            q2.popleft()
            q1.append((xy2[0], xy2[1], theta2))

print(ans)

Measured memory_bytes: 3444
#pragma GCC optimize ("Ofast")
#include<bits/stdc++.h>
using namespace std;
inline void rd(int &x){
  int k, m=0;
  x=0;
  for(;;){
    k = getchar_unlocked();
    if(k=='-'){
      m=1;
      break;
    }
    if('0'<=k&&k<='9'){
      x=k-'0';
      break;
    }
  }
  for(;;){
    k = getchar_unlocked();
    if(k<'0'||k>'9'){
      break;
    }
    x=x*10+k-'0';
  }
  if(m){
    x=-x;
  }
}
inline void wt_L(char a){
  putchar_unlocked(a);
}
inline void wt_L(const char c[]){
  int i=0;
  for(i=0;c[i]!='\0';i++){
    putchar_unlocked(c[i]);
  }
}
int N;
int M;
int A;
int B;
int cnt[200000];
int main(){
  int Lj4PdHRW;
  rd(N);
  rd(M);
  for(Lj4PdHRW=0;Lj4PdHRW<(M);Lj4PdHRW++){
    rd(A);A += (-1);
    rd(B);B += (-1);
    if(A==0){
      cnt[B]++;
      if(cnt[B]==2){
        wt_L("POSSIBLE");
        wt_L('\n');
        return 0;
      }
    }
    if(B==N-1){
      cnt[A]++;
      if(cnt[A]==2){
        wt_L("POSSIBLE");
        wt_L('\n');
        return 0;
      }
    }
  }
  wt_L("IMPOSSIBLE");
  wt_L('\n');
  return 0;
}
// cLay varsion 20190822-2

// --- original code ---
// int N, M, A, B;
// int cnt[2d5];
// {
//   rd(N,M);
//   rep(M){
//     rd(A--,B--);
//     if(A==0){
//       cnt[B]++;
//       if(cnt[B]==2) wt("POSSIBLE"), return 0;
//     }
//     if(B==N-1){
//       cnt[A]++;
//       if(cnt[A]==2) wt("POSSIBLE"), return 0;
//     }
//   }
//   wt("IMPOSSIBLE");
// }


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

int main()
{
    int N, L;
    cin >> N >> L;
    int ans = 0;
    int min = 100;
    for (int i = 0; i < N; i++)
    {
        int n = L + i;
        if (abs(n) < abs(min))
        {
            min = n;
        }
        ans += n;
    }
    cout << ans - min << endl;
    return 0;
}

Measured memory_bytes: 256
package main

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

var N, M, Q int

func main() {
	N, M, Q = ReadInt(), ReadInt(), ReadInt()

	L := make([]int, M)
	R := make([]int, M)
	for i := 0; i < M; i++ {
		L[i], R[i] = ReadInt(), ReadInt()
	}
	sumTable := buildSumTable(L, R)

	for i := 0; i < Q; i++ {
		p, q := ReadInt(), ReadInt()
		fmt.Println(calcSum(sumTable, p, q))
	}
}

func buildSumTable(L, R []int) [][]int {
	sum := make([][]int, N+1)
	for i := 0; i < N+1; i++ {
		sum[i] = make([]int, N+1)
	}
	for i := 0; i < M; i++ {
		sum[L[i]][R[i]]++
	}
	for i := 1; i <= N; i++ {
		for j := 1; j <= N; j++ {
			sum[i][j] += sum[i-1][j]
			sum[i][j] += sum[i][j-1]
			sum[i][j] -= sum[i-1][j-1]
		}
	}
	return sum
}

func calcSum(sumTable [][]int, L, R int) int {
	return sumTable[R][R] - sumTable[R][L-1] - sumTable[L-1][R] + sumTable[L-1][L-1]
}

var reader = bufio.NewReader(os.Stdin)

func Scan(a ...interface{}) {
	if _, err := fmt.Fscan(reader, a...); err != nil {
		panic(err)
	}
}
func ReadInt() (i int) { Scan(&i); return }


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

int main(){
    int a,b;
    cin >> a >> b;
  
  	string dic="";
  	string s = "";
  	if(a==b){
      	
      	dic =to_string(a);
      	for(int i =0;i<b;i++){
    		s += dic;
        }
      	cout << s;
      return 0;
    }
  
  	if(a<b){
      	dic =to_string(a);
      	for(int i=0;i<b;i++){
        	s +=dic;
        }
    }else if(a>b){
      	dic =to_string(b);
      	for(int i=0;i<a;i++){
        	s+=dic;
        }
    }
  
  	cout << s;
  
  
  
	
  

}

Measured memory_bytes: 256
import sys
import math
import collections
from collections import deque
from functools import reduce
import heapq
#n = int(input())
a, b, c, d = map(int, sys.stdin.readline().split())
#s = input()
#a = list(map(int, sys.stdin.readline().split()))

while (True):
    c -= b
    if c <= 0:
        print("Yes")
        break

    a -= d
    if a <= 0:
        print("No")
        break


    


Measured memory_bytes: 9504