akhauriyash/Code-Regression huggingface dataset:
import sys
input = sys.stdin.readline

n, k = [int(i) for i in input().split()]
p = [0] * n
for i,v in enumerate(input().split()):
    p[i] = 1.0 + 0.5 * (float(v) - 1.0)

_max_sum = 0
_prev_sum = 0
for i in range(0, n-k+1):
    if i == 0:
        _sum = sum(p[:k])
    else:
        _sum = _prev_sum - p[i-1] + p[i+k-1]
    if _sum >= _max_sum:
        _max_sum = _sum
    _prev_sum = _sum
print(_max_sum)


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

#define ll long long int
#define mod 1000000007

#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;

int sub(int a,int b){
	int x = (a-b)%mod;
	if(x<0)x+=mod;
	return x;
}
int add(int a,int b){
	return (a+b) % mod;
}
    
    
int main()
{  
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n,k;
    cin>>n>>k;
    
    vector<int> s(n+1);
    for(int i=1;i<=n;i++){
		s[i]=add(s[i-1],i);
	}
    
    int ans=0;
    for(int i=k;i<=n+1;i++){
		int from = sub(s[n],(n-i < 0)?0:s[n-i]);
		int to = s[i-1];
		ans=add(ans,add(sub(from,to),1));
	}
	cout<<ans<<"\n";
    
}
    



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

int main(){
  long int N, counter = 0;
  cin >> N;
  vector<long int> A(N);
  for(long int i = 0; i < N; i++){
    cin >> A.at(i);
  }
  for(long int i = 0; i < N - 1; i++){
    if(A.at(i) > A.at(i + 1)){
      counter += (A.at(i) - A.at(i + 1));
      A.at(i + 1) = A.at(i);
    }
  }
  cout << counter << endl;
}

Measured memory_bytes: 4756
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7
import numpy as np

X, t = MAP()

print(X-t if X > t else 0)

Measured memory_bytes: 22868
#include <cctype>
#include <climits>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>

#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>
#include <tuple>
using namespace std;

int h[100002];
int dp[100002];

int main() {
  int n;

  while (cin >> n) {
    for (int i = 0; i < n; i++) {
      cin >> h[i];
      dp[i] = INT_MAX;
    }

    dp[0] = 0;

    for (int i = 0; i < n; i++) {
      if (dp[i] == INT_MAX) continue;
      for (int j = 1; j <= 2; j++) {
        if (i + j < n) {
          dp[i + j] = min(dp[i + j], dp[i] + abs(h[i + j] - h[i]));
        }
      }
    }

    cout << dp[n - 1] << endl;
  }
}


Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
typedef vector <int> vi;

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	//freopen("in.txt", "r", stdin);
	//freopen("out.txt", "w", stdout);
	int n, a;
	cin >> n >> a;
	cout << (n*n - a) << endl;
	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
void pre(){}
long long int inf = 1e10;
void solve(){
    long long int h,w;cin>>h>>w;
    bool arr[h+1][w+1];
    char c;
    long long int dp[h+1][w+1];
    for(long long int i=0;i<h;i++){
        for(long long int j=0;j<w;j++){
            cin>>c;
            dp[i+1][j+1]=inf;
            if(c=='.')
                arr[i+1][j+1]=1;
            else
                arr[i+1][j+1]=0;
        }
    }
    for(long long int i=0;i<=w;i++){
        dp[0][i]=inf;
        arr[0][i]=1;
    }
    for(long long int i=0;i<=h;i++){
        dp[i][0]=inf;
        arr[i][0]=1;
    }
    dp[1][0]=0;
    dp[0][1]=0;
    dp[0][0]=inf;
    for(long long int i=1;i<=h;i++){
        for(long long int j=1;j<=w;j++){
            if(arr[i][j]){
                dp[i][j]=min(min(dp[i][j-1],dp[i-1][j]),dp[i][j]);
                //cout<<dp[i][j];
                continue;
            }    
            if(!arr[i-1][j]){
                dp[i][j]=min(dp[i][j],dp[i-1][j]);
            }else{
                dp[i][j]=min(dp[i][j],dp[i-1][j]+1);
            }
            if(!arr[i][j-1]){
                dp[i][j]=min(dp[i][j],dp[i][j-1]);
            }else{
                dp[i][j]=min(dp[i][j],dp[i][j-1]+1);
            }
            //cout<<dp[i][j];
        }
        //cout<<"\n";
    }
    cout<<dp[h][w]<<"\n";
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    pre();
    long long int num = 1;
    //cin>>num;
    for(long long int i=0;i<num;i++){
       	solve();
    }   
}

Measured memory_bytes: 384
#include <bits/stdc++.h>
using namespace std;
 
int main(){
long long N, M;
cin >> N >> M;
long long cnt = 0;
  if(M <= 2 * N){
  cnt = M / 2;
  }
  else{
  cnt = N + ((M - 2 * N)) / 4;
  }
  
  cout << cnt << endl;
  return 0;
  
}

Measured memory_bytes: 256
#include <stdio.h>
int main(void)
{
   int a,b,c,d,e,f;

   scanf("%d%d%d%d",&a,&b,&c,&d);

   if(a<b) e=a;
   else e=b;

   if(c<d) f=c;
   else f=d;

   printf("%d\n",e+f);

   return 0;
}



Measured memory_bytes: 128
#define _USE_NATH_DEFINES
#include <cstdio>
#include <iostream>
#include <sstream>
#include <fstream>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <complex>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <bitset>
#include <numeric>
#include <limits>
#include <climits>
#include <cfloat>
#include <functional>
#include <iterator>
#include <random>
#include <tuple>


using namespace std;
#define REP(i,m,n) for(int i=(int)m ; i < (int) n ; ++i )
#define rep(i,n) REP(i,0,n)
using ll = long long;
#define EPS 1e-9
const int INF = 1050000000;
const long long LINF = 1LL << 60;
const ll MOD = 1e9 + 7;
const int MINF = -1050000000;

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; }


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

	int sum = 0;
	sum = (n*(n - 1)) / 2 + (m*(m-1))/2;

	cout << sum << endl;
	return 0;
}

Measured memory_bytes: 256
//
//  main.cpp
//  C - Distinct or Not
//
//  Created by Hashizo on 2020/02/09.
//  Copyright © 2020 Hashizo. All rights reserved.
//

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <regex>
#include <cmath>

using namespace std;
 
#undef LONG_MAX
#undef LONG_MIN
 
#define LONG_MAX    9223372036854775807
#define LONG_MIN    (-LONG_MAX  -1)
 
#define ll long long
 
#define FOR(i, a, b) for (ll i = (a); i < (b); i++)
#define REP(i, n) FOR(i, 0, n)
 
#define SORT(c) sort((c).begin(), (c).end())
#define REVERSE(v) reverse((v).begin(), (v).end())


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


	ll n;
	cin >> n;

	vector<ll> point(n);
	REP(i, n) {
		cin >> point[i];
	}
	
	SORT(point);
	
	
	REP(i,n-1) {
		if(point[i] == point[i+1]) {
			cout << "NO" << endl;
			return 0;

		}
	}

	cout << "YES" << endl;
	return 0;
}


Measured memory_bytes: 1792
#include<bits/stdc++.h>
#include<vector>
#include<string>
#include<algorithm>
#include<cmath>
 
#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define int long long int
#define mod 1000000007

#define out1(a) cout<<#a<<" "<<a<<endl
#define out2(a,b) cout<<#a<<" "<<a<<" "<<#b<<" "<<b<<endl
#define out3(a,b,c) cout<<#a<<" "<<a<<" "<<#b<<" "<<b<<" "<<#c<<" "<<c<<endl

#define ft first
#define sd second
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
 
using namespace std;

signed main()
{
    fast;
    int k,n;
    cin>>k>>n;

    vector<int> a(n);

    for( int i = 0 ; i < a.size() ; i++ )
    {
        cin>>a[i];
    }
    
    vector<int> dif;

    for ( int i = 0 ; i < a.size()-1 ; i++ )
    {
        if ( (a[i+1]-a[i]) > k/2 )
        {
            dif.pb(k-(a[i+1]-a[i]));
        }
        else
        {
            dif.pb(a[i+1]-a[i]);
        }
    }
    if ( (a[a.size()-1] - a[0]) > k/2 )
    {
        dif.pb(k-(a[a.size()-1] - a[0]));
    }
    else
    {
        dif.pb((a[a.size()-1] - a[0]));
    }

    sort(all(dif));

    int ans = 0;

    for ( int i = 0 ; i < dif.size()-1 ; i++ )
    {
        ans += dif[i];
    }

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

Measured memory_bytes: 3956
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
ll gcd(ll n,ll m){ 
	if(m==0){
		return n;
	} 
    return gcd(m,n%m);  
} 
ll SolveUtil(ll x) 
{ 
    ll cnt=0,i; 
    if(x%2==0) { 
        cnt++; 
        while(x%2==0){
        	x=x/2;
		} 
    } 
    for(i=3;i<=sqrt(x);i=i+2){ 
        if(x%i==0){ 
            cnt++; 
            while(x%i==0){
            	x=x/i;
			} 
        } 
    } 
    if(x>2){
    	cnt++;
	}  
    return cnt; 
} 
ll Solve(ll n,ll m) 
{ 
    ll g=gcd(n,m); 
    return SolveUtil(g); 
} 
int main()
{
	ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    ll n,m,temp,ans;
    cin>>n>>m;
    ans=Solve(n,m);
    if(n==1 || m==1){
    	cout<<1<<endl;
	}else{
		cout<<ans+1<<endl;
	}
	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h> 
#define REP(i, b) for(int i = 0; i < (b); i++)
#define REPS(i, b) for(int i = 1; i <= (b); i++)
#define FOR(i, a, b) for(int i = (a); i < (b); i++)
#define ALL(v) (v).begin(), (v).end()
using namespace std;
using ll = long long;

signed main()
{
    cin.tie(nullptr);
    ios_base::sync_with_stdio(false);
    cout << fixed << setprecision(20);

    ll N; cin >> N;
    vector<ll> a(N), b(N);
    REP(i, N) cin >> a[i];
    REP(i, N) cin >> b[i];
    
    ll n = 0, c = 0;
    REP(i, N) n += b[i] - a[i];
    REP(i, N)
    {
        if(b[i] > a[i]) c += (b[i] - a[i] + 1) / 2;
    }
    if(c > n) cout << "No" << endl;
    else cout << "Yes" << endl;
}

Measured memory_bytes: 384
#include <iostream>
#include <iomanip>
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>
#include <set>
using namespace std;

int main(){
    int N;
    cin >> N;
    vector<int> P(N);
    for(int i=0; i<N; i++) cin >> P[i];

    vector<bool> a(N+1, false);
    vector<bool> b(N+1, false);
    //b[0] = true;
    for(int i=0; i<N; i++){
        if(b[P[i]-1]) a[P[i]] = true;
        b[P[i]] = true;
    }

    //for(int i=0; i<=N; i++)
    //    cerr << a[i] << " ";
    //cerr << endl;

    int ans = 1;
    int cnt = 0;
    for(int i=1; i<=N; i++){
        if(a[i] == false){
            ans = max(ans, cnt);
            cnt = 1;
        }else{
            cnt++;
            ans = max(ans, cnt);
        }
    }
    cout << N - ans << endl;
    return 0;
}

Measured memory_bytes: 1024
#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

int n, k;
int h[100005];
vector<int> v;

int main(){
	cin >> n >> k;
	for(int i = 0; i < n; ++i){
		cin >> h[i];
		v.push_back(h[i]);
	}
	sort(v.begin(), v.end());
	int answer = 10000000000;
	for(int i = 0; i < n - k + 1; ++i){
		//cout << v[i] << endl;
		if(v[i + k - 1] - v[i] < answer){
			answer = v[i + k - 1] - v[i];
		}
	}
	cout << answer << endl;
}

Measured memory_bytes: 1148
#include <bits/stdc++.h>
using namespace std;
int main() {
  int R = 0;
  string S;
  cin >> S;
  for (int i = 0; i < 3; i++) {
    if (S.at(i) == 'R') {R++;}
  }
  if (R == 0) {cout << 0 << endl;}
  else if (R == 1) {cout << 1 << endl;}
  else if (R == 2) {
    if (S.at(1) == 'R') {cout << 2 << endl;}
    else {cout << 1 << endl;}
  }
  else {cout << 3 << endl;}
}

Measured memory_bytes: 3620
#include <iostream>
#include <vector>
#include <stdio.h>
#include <string>
#include <algorithm>
#include <deque>

using namespace std;
#define MAX_H 100
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;


int H, W;
string str[MAX_H+1];
short dp[MAX_H+1][MAX_H+1][MAX_H+1][MAX_H+1];
int x, y;
bool in[MAX_H+1][MAX_H+1][MAX_H+1][MAX_H+1];

void update(pair<int, int> p1, pair<int, int> p2, int k){
	if(p1.first<0 || p1.second>=H || p2.first<0 || p2.second>=W)	return;
	dp[p1.first][p1.second][p2.first][p2.second] = max(dp[p1.first][p1.second][p2.first][p2.second], (short)k);
}

int sum(pii p1, pii p2){
	//cout<<'*'<<p1.first<<' '<<p1.second<<' '<<p2.first<<' '<<p2.second<<endl;
	int ret= 0;
	for(int i=p1.first; i<=p2.first; i++){
		for(int j=p1.second; j<=p2.second; j++){
			if(str[i][j]=='o')	ret++;
		}
	}
	return ret;
}

void solve(pair<int, int> n1, pair<int, int> n2){
	if(n1.first!=0){
		update({n1.first-1, n1.second}, n2, dp[n1.first][n1.second][n2.first][n2.second] + sum({max(n1.second-x ,n1.first-1), max(n2.first, n2.second-y)}, {n1.first-1, min(n2.second, W-1-(y-n2.first))}));
	}
	if(n1.second!=H-1){
		update({n1.first, n1.second+1}, n2, dp[n1.first][n1.second][n2.first][n2.second] + sum({n1.second+1, max(n2.first, n2.second-y)}, {min(H-1-(x-n1.first), n1.second+1), min(n2.second, W-1-(y-n2.first))}));
	}
	if(n2.first!=0){
		update(n1, {n2.first-1, n2.second}, dp[n1.first][n1.second][n2.first][n2.second] + sum({max(n1.first, n1.second-x), max(n2.second-y, n2.first-1)}, {min(n1.second, H-1-(x-n1.first)), n2.first-1}));
	}
	if(n2.second!=W-1){
		update(n1, {n2.first, n2.second+1}, dp[n1.first][n1.second][n2.first][n2.second] + sum({max(n1.second-x, n1.first), n2.second+1}, {min(n1.second, H-1-(x-n1.first)), min(W-1-(y-n2.first), n2.second+1)}));
	}
}


int main(){
	cin>>H>>W;
	for(int i=0; i<H; i++){
		cin>>str[i];
		for(int j=0; j<W; j++){
			if(str[i][j]=='E'){
				x = i; y = j;
			}
		}
	}
	dp[x][x][y][y] = 0;
	in[x][x][y][y] = true;
	for(int li = 0; li < H; li++){
		for(int lj = 0; lj < W; lj++){
			for(int i1 = max(0, x-li); i1<min(H-li, x+1); i1++){
				int i2 = i1+li;
				for(int j1 = max(0, y-lj); j1<min(W-lj, y+1); j1++){
					int j2 = j1+lj;
					solve({i1, i2}, {j1, j2});
				}
			}
		}
	}
	printf("%d", dp[0][H-1][0][W-1]);
}	


Measured memory_bytes: 173696
import java.util.*;
 
class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int A = sc.nextInt();
      	int B = sc.nextInt();
      	int C = sc.nextInt();
      	int K = sc.nextInt();
      	int ans = 0;
      	int i = 0;
        while(i<K){
          for(int j=0;j<A && i<K;j++){
            ans = ans + 1;
            i++;
          }
          for(int j=0;j<B && i<K;j++){
            ans = ans;
            i++;
          }
          for(int j=0;j<C && i<K;j++){
            ans = ans -1;
            i++;
          }
        }
      	System.out.println(ans);
    }
}

Measured memory_bytes: 35840
#include<bits/stdc++.h>
  using namespace std;
const int N=100;
int a[1+N<<1]={0},n,sum;
inline void into(){
  scanf("%d",&n);
  for (int i=1;i<=n<<1;i++)
    scanf("%d",&a[i]);
}
inline void work(){
  sort(a+1,a+n+n+1);
  for (int i=1;i<=n;i++)
    sum+=a[i-1<<1|1];
}
inline void outo(){
  printf("%d\n",sum);
}
int main(){
  into();
  work();
  outo();
  return 0; 
}

Measured memory_bytes: 256
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {

	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String n = br.readLine();		
		for(int i = 0 ; i < Integer.parseInt(n) ; i++){
			String a = br.readLine();
			System.out.println(a.replaceAll("Hoshino","Hoshina"));
		}
	}

}

Measured memory_bytes: 16968
w, a, b = map(int, input().split())

d1 = b-a-w
d2 = a-b-w

if d1 <= 0 and d2 <= 0:
    print(0)
elif d1 > 0 and d2 < 0:
    print(d1)
elif d1 < 0 and d2 > 0:
    print(d2)
else:
    print(min(d1, d2))

Measured memory_bytes: 3060
import collections

N = int(input())
V = list(map(int, input().split()))
Ve = V[::2]
Vo = V[1::2]

Ve_common = collections.Counter(Ve).most_common(2)
Vo_common = collections.Counter(Vo).most_common(2)
if len(set(V)) == 1:
    print(N//2)
elif Ve_common[0][0] != Vo_common[0][0]:
    print(N - Ve_common[0][1] - Vo_common[0][1])
else:
    print(min(N - Ve_common[1][1] - Vo_common[0][1], N - Ve_common[0][1] - Vo_common[1][1]))

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

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int N, M;
    cin >> N >> M;
    vector<int> K(M);
    vector<vector<int>> S(M);
    for(int i=0; i<M; i++)
    {
        cin >> K[i];
        S[i].resize(K[i]);
        for(int j=0; j<K[i]; j++)
        {
            cin >> S[i][j];
            S[i][j]--;
        }
    }
    vector<int> P(M);
    for(int i=0; i<M; i++) cin >> P[i];

    int ans = 0;
    for(int bit=0; bit < (1<<N); bit++)
    {
        vector<bool> mp(N, false);
        for(int i=0; i<N; i++)
        {
            if(bit & (1<<i))
            {
                mp[i] = true;
            }
        }
        bool ok = true;
        for(int i=0; i<M; i++)
        {
            int cnt = 0;
            for(int j=0; j<K[i]; j++) if(mp[S[i][j]]) cnt++;
            if(cnt%2 != P[i]) ok = false;
        }
        if(ok) ans++;
    }
    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 3668
#include "bits/stdc++.h"

#define rep(i, a) for (int i = 0; i < (int)a; ++i)
#define REP(i, a, b) for (int i = (a); i < (int)b; ++i)

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

void Main() {
  int a, b;
  cin >> a >> b;
  int ans = 0;
  int now = 1;
  while(b > now) {
    now += a-1;
    ans++;
  }
  cout << ans << endl;
}

int main() {
  std::cin.tie(nullptr);
  std::ios_base::sync_with_stdio(false);
  std::cout << std::fixed << std::setprecision(15);
  Main();
  return 0;
}


Measured memory_bytes: 256
#define _CRT_SECURE_NO_WARNINGS
#define _USE_MATH_DEFINES
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <functional>
#include <utility>
#include <tuple>
#include <cctype>
#include <bitset>
#include <complex>
#include <cmath>
#include <array>
using namespace std;
#define INF 0x3f3f3f3f
#define INFLL 0x3f3f3f3f3f3f3f3fLL
#define MOD 1000000007
#define mp make_pair
#define mt make_tuple
#define pb push_back
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pint;
typedef pair<ll,ll> pll;
typedef tuple<int,int,int> tint;
typedef vector<int> vint;
typedef vector<ll> vll;
typedef vector<pint> vpint;
int dx[8]={0,0,-1,1,1,1,-1,-1};
int dy[8]={-1,1,0,0,1,-1,1,-1};
const int SIZE=4050;
//ここまでテンプレ
int main(){
	string S,T;
	cin>>S>>T;
	S='@'+S;
	T='@'+T;
	//DS[i][0 or 1]=S[i]の次に0 or 1が現れる場所のindex
	//length()に-2(終了を意味する),
	int DS[SIZE][2]={},DT[SIZE][2]={};
	for(int i:{0,1}){
		DS[S.length()-1][i]=-1;
		DT[T.length()-1][i]=-1;
	}
	//DSの遷移
	for(int i=S.length()-2;i>=0;i--){
		for(int j:{0,1}){
			DS[i][j]=(S[i+1]-'0'==j?i+1:DS[i+1][j]);
		}
	}
	//DTの遷移
	for(int i=T.length()-2;i>=0;i--){
		for(int j:{0,1}){
			DT[i][j]=(T[i+1]-'0'==j?i+1:DT[i+1][j]);
		}
	}
	for(int i:{0,1}){
		DS[S.length()][i]=-2;
		DT[T.length()][i]=-2;
	}
	//DP[i][j]=S[i],T[j]以降(自身を含まない)の文字列の最小共通非部分列の長さ
	int DP[SIZE][SIZE]={};
	for(int i=0;i<SIZE;i++)
		for(int j=0;j<SIZE;j++)
			DP[i][j]=INF;
	//DPの遷移
	for(int i=S.length();i>=0;i--){
		for(int j=T.length();j>=0;j--){
			for(int k:{0,1}){
				if(DS[i][k]==-2 && DT[j][k]==-2){
					DP[i][j]=0;
				}
				else if(DS[i][k]==-2){
					if(DT[j][k]==-1)
						DP[i][j]=1;
					else
						DP[i][j]=min(DP[i][j],DP[S.length()][DT[j][k]]+1);
				}
				else if(DT[j][k]==-2){
					if(DS[i][k]==-1)
						DP[i][j]=1;
					else
						DP[i][j]=min(DP[i][j],DP[DS[i][k]][T.length()]+1);
				}
				else{
					if(DS[i][k]==-1 && DT[j][k]==-1)
						DP[i][j]=1;
					else if(DS[i][k]==-1)
						DP[i][j]=min(DP[i][j],DP[S.length()][DT[j][k]]+1);
					else if(DT[j][k]==-1)
						DP[i][j]=min(DP[i][j],DP[DS[i][k]][T.length()]+1);
					else
						DP[i][j]=min(DP[i][j],DP[DS[i][k]][DT[j][k]]+1);
				}
			}
		}
	}
	//構築
	string U;
	int Sidx=0,Tidx=0;	//今見ているindex
	while(1){
		//DPの小さい方に飛ぶ(0優先)
		int Snxt=0,Tnxt=0;	//次に見るindex
		if(DP[Sidx][Tidx]==0)
			break;
		//0に飛ぶとき
		if(DP[(DS[Sidx][0]<=-1?S.length():DS[Sidx][0])][(DT[Tidx][0]<=-1?T.length():DT[Tidx][0])]<=DP[(DS[Sidx][1]<=-1?S.length():DS[Sidx][1])][(DT[Tidx][1]<=-1?T.length():DT[Tidx][1])]){
			Snxt=(DS[Sidx][0]<=-1?S.length():DS[Sidx][0]);
			Tnxt=(DT[Tidx][0]<=-1?T.length():DT[Tidx][0]);
			U+='0';
		}
		//1に飛ぶとき
		else{
			Snxt=(DS[Sidx][1]<=-1?S.length():DS[Sidx][1]);
			Tnxt=(DT[Tidx][1]<=-1?T.length():DT[Tidx][1]);
			U+='1';
		}
		Sidx=Snxt;
		Tidx=Tnxt;
	}
	cout<<U<<endl;
	return 0;
}


Measured memory_bytes: 67340
#include <iostream>
#include <vector>
#include <algorithm>
#include <bits/stdc++.h>
using namespace std;
int main(){
    vector<int> s(32);
    s={1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51
};
    int K;
    cin >> K;
    cout << s[K-1];

}

Measured memory_bytes: 256
import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline

global time
time = 0

def dfs(u: int, visited: list, d: list, f: list, M: list, n: int):
    global time
    visited[u] = True
    time += 1
    d[u] = time
    for j in range(n):
        if M[u][j] == 1 and not visited[j]:
            dfs(j, visited, d, f, M, n)
    time += 1
    f[u] += time

def main():
    n = int(input())
    visited = [False] * n
    M = [[0]*n for _ in range(n)]
    for _ in range(n):
        a = list(map(int, input().split()))
        for i in range(a[1]):
            M[a[0]-1][a[i+2]-1] = 1
    d = [0] * n
    f = [0] * n
    for i in range(n):
        if not visited[i]:
            dfs(i, visited, d, f, M, n)
    for i in range(n):
        print(i+1, d[i], f[i])

if __name__ == '__main__': main()


Measured memory_bytes: 5748
#include<stdio.h>
int main(void){
  int a,b;
  scanf("%d%d",&a,&b);
  if(b==1){
printf("0");
    return 0;
  }
  int sum=1,ans=0;
  while(1){
	sum+=a-1;
    ans++;
    if(sum>=b){
printf("%d",ans);
      return 0;
    }
  }
  return 0;
}

Measured memory_bytes: 128
import std.stdio;
import std.conv;
import std.string;
import std.typecons;
import std.algorithm;
import std.array;
import std.range;
import std.math;
import std.regex : regex;
import std.container;
import std.bigint;


void main()
{
  auto n = readln.chomp.count('7');
  if (n) {
    writeln("Yes");
  } else {
    writeln("No");
  }

}


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

int main(void){
  int X;
  bool ans = false;
  cin >> X;
  if(X == 7 || X == 5 || X == 3)
    ans = true;
  if(ans) cout << "YES" << "\n";
  else cout << "NO" << "\n";
  return 0;
}


Measured memory_bytes: 3508
#include <bits/stdc++.h>
using namespace std;
#define watch(x) cout << (#x) << " is " << (x) << '\n'
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define sz(x) ((int)(x).size())
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef pair<int, int> pi;
typedef pair<ll, ll> pll;
typedef double db;
ll gcd(ll a, ll b) { return b?gcd(b,a%b):a; }
//head
 
void solve(){
    int k;
    cin >> k;
    int even = k/2;
    int odd = k/2 + k%2;
    cout << even*odd << '\n';
}

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

    //int t; cin >> t; while (t--)
        solve();
}

Measured memory_bytes: 3636
#include <algorithm>
#include <climits>
#include <deque>
#include <iostream>
#include <map>
#include <math.h>
#include <set>
#include <string.h>
#include <utility>
#include <vector>
using namespace std;

#define dlog(str) cout << "====" << str << endl;
#define INF 999999999
#define REP(i, n) for(int i = 0, i##_l = (n); i < i##_l; i++)
#define REPR(i, n) for(int i = n - 1; 0 <= i; i--)
#define FOR(i, s, e) for(int i = s; i <= e; i++)
#define FORR(i, s, e) for(int i = s; e <= i; i--)
#define LLI long long int
#define chmax(a, b) a = max(a, b)
#define chmin(a, b) a = min(a, b)
#define bit(a, shift) ((a>>shift)&1))
#define ALL(v) (v).begin(), (v).end()
#define SORT(v) sort(ALL(v))
// int 2.14E±9    lli 9.2E±18    double 1.7E±380

struct BC {
    int b, c;

    BC(int _b, int _c) : b(_b), c(_c) {}

    bool operator<(BC &another) {
        if(c == another.c) {
            return b > another.b;
        }
        return c > another.c;
    }
};

int main() {
    int N, M;
    cin >> N >> M;
    vector<int> a(N);
    vector<BC> bc;
    int b, c;
    REP(i, N) { cin >> a[i]; }
    REP(i, M) {
        cin >> b >> c;
        bc.push_back(BC(b, c));
    }

    SORT(a);
    SORT(bc);

    int p = 0;
    int j = 0, i = 0;
    LLI cnt = 0;
    while(i < M && j < N) {
        for(int n = 0; n < bc[i].b; j++, n++) {
            if(a[j] < bc[i].c) {
                a[j] = bc[i].c;
            } else {
                break;
            }
        }
        i++;
    }

    REP(i, N) { cnt += a[i]; }
    cout << cnt;
    return 0;
}

Measured memory_bytes: 1784
X, Y, A, B, C = map(int, input().split())
p = sorted(list(map(int, input().split())))[-X:]
q = sorted(list(map(int, input().split())))[-Y:]
r = list(map(int, input().split()))

total = sorted(p + q + r)[::-1]
print(sum(total[:X + Y]))


Measured memory_bytes: 22504
#include <iostream>
#include <vector>
using namespace std;
using ll = long long;

vector<ll> enumDivisor(ll n){
    vector<ll> res;
    for(ll i=1; i*i<=n; i++){
        if (n%i != 0)continue;
        res.push_back(i);
        if (i*i != n)res.push_back(n/i);
    }
    return res;
}
int main(){
    ll n;
    cin >> n;
    int ans=0;
    for(ll x : enumDivisor(n)){
        if (x==1)continue;
        ll tmp = n;
        while (tmp%x == 0)tmp /= x;
        if (tmp%x == 1)ans++;
    }
    ans += enumDivisor(n-1).size()-1;
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 888
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace abc102a
{
    class abc102a
    {
        static void Main(string[] args)
        {
            var n = UInt32.Parse(Console.ReadLine());
            Console.WriteLine(n % 2 == 0 ? n : n * 2);
        }
    }
}


Measured memory_bytes: 11092
S = str(input())
lists = []
for i in range(len(S)):
    if i == 4 or i == 7:
        continue
    else:
        lists.append(S[i])
m = "".join(lists)
if int(m) > 20190430:
    print("TBD")
else:
    print("Heisei")

Measured memory_bytes: 2940
package main

import (
	"bufio"
	"fmt"
	"log"
	"math"
	"os"
	"sort"
	"strconv"
)

type Point struct {
	x int
	y int
}

func (p Point) angle() float64 {
	return math.Atan2(float64(p.y), float64(p.x))
}

type ByAngle []Point

func (a ByAngle) Len() int           { return len(a) }
func (a ByAngle) Swap(i, j int)      { a[i], a[j] = a[j], a[i] }
func (a ByAngle) Less(i, j int) bool { return a[i].angle() < a[j].angle() }

func run() {
	n := nextInt()
	ps := make([]Point, n)
	for i := 0; i < n; i++ {
		x := nextInt()
		y := nextInt()
		ps[i] = Point{
			x: x,
			y: y,
		}
	}
	sort.Sort(ByAngle(ps))
	answer := 0
	for i := 0; i < n; i++ {
		current := Point{
			x: 0,
			y: 0,
		}
		for j := 0; j < n; j++ {
			k := (i + j) % n
			current = Point{
				x: current.x + ps[k].x,
				y: current.y + ps[k].y,
			}
			dist := current.x*current.x + current.y*current.y
			if answer < dist {
				answer = dist
			}
		}
	}
	Println(math.Sqrt(float64(answer)))
}

// --- template ---
// Thanks https://gist.github.com/halllllll/853ab587fd82ee3ffe6f7fb7fb499695

var sc = bufio.NewScanner(os.Stdin)
var out = bufio.NewWriter(os.Stdout)

// Caution: You will get unexpected result if a single token is larger than this size.
const BufferSize = 64 * 1024 * 1024

func Print(a ...interface{}) (n int, err error) {
	return fmt.Fprint(out, a...)
}

func Printf(format string, a ...interface{}) (n int, err error) {
	return fmt.Fprintf(out, format, a...)
}

func Println(a ...interface{}) (n int, err error) {
	return fmt.Fprintln(out, a...)
}

func next() string {
	sc.Scan()
	return sc.Text()
}

func nextInt() int {
	a, err := strconv.Atoi(next())
	if err != nil {
		log.Fatal(err)
	}
	return a
}

func nextFloat() float64 {
	a, err := strconv.ParseFloat(next(), 64)
	if err != nil {
		log.Fatal(err)
	}
	return a
}

func nextInts(n int) []int {
	res := make([]int, n)
	for i := 0; i < n; i++ {
		res[i] = nextInt()
	}
	return res
}

func nextFloats(n int) []float64 {
	res := make([]float64, n)
	for i := 0; i < n; i++ {
		res[i] = nextFloat()
	}
	return res
}

func nextStrings(n int) []string {
	res := make([]string, n)
	for i := 0; i < n; i++ {
		res[i] = next()
	}
	return res
}

func main() {
	sc.Buffer(make([]byte, 0, BufferSize), BufferSize)
	sc.Split(bufio.ScanWords)
	run()
	out.Flush()
}


Measured memory_bytes: 2816
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>

using namespace std;
const int LEN = 1e5 + 10;
int ans[LEN], num;
vector<int> edge[LEN];
int n, m;
queue<int> q;

int bfs(int start) {
    while (!q.empty()) {
        q.pop();
    }
    num = 0;
    q.push(start);
    ans[start] = start;
    num++;
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        for (int i = 0; i < edge[u].size(); i++) {
            int v = edge[u][i];
            if (ans[v] == 0) {
                ans[v] = u;
                q.push(v);
                num++;
            }
        }
    }
    return num;
}

int main() {
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        int u, v;
        scanf("%d%d", &u, &v);
        edge[u].push_back(v);
        edge[v].push_back(u);
    }
    if (bfs(1) == n) {
        printf("Yes\n");
        for (int i = 2; i <= n; i++) {
            printf("%d\n", ans[i]);
        }
    } else {
        printf("No\n");
    }
    return 0;
}

Measured memory_bytes: 10596
#include <bits/stdc++.h>
using namespace std;
 
#define int long long
 
signed main() {
    int n, k;
    cin >> n >> k;
    int res = 1;
    for(int i=0; i<n; ++i) {
        if(res*2 < res+k) res *= 2;
        else res = res + k;
    }
    cout << res << endl;
    return 0;
}

Measured memory_bytes: 256
#include <algorithm>
#include <iostream>
#include <vector>
#define N 200001
using namespace std;

int main(){
  int n,k[N],ans;
  vector<int> v;
  ans=0;
  cin>>n;
  for(int i=1;i<=n;i++) cin>>k[i];
  for(int i=1;i<=n;i++){
    v.push_back(k[i]);
    if(n%i!=0) continue;
    vector<int> t;
    int f=0;
    for(int j=i+1;j<=n;j++){
      t.push_back(k[j]);
      if(t.size()==i){
	if(v!=t){
	  f=1;
	  break;
	}
	t.clear();
      }
    }
    if(f==0){
      ans=n/i;
      break;
    }
  }
  cout<<ans<<endl;
  return 0;
}

Measured memory_bytes: 2992
#include <stdio.h>
#include <string.h>
#define N 10000
typedef struct aa{
  int value;
  char egara;
}Card;
void BubbleSort(int);
void SelectionSort(int);
void copy();
Card  a[N],b[N],c[N];
int flag1=0;
int main(){
  int num,i,j,judge,flag=0,k=0;
  char d[N];
  scanf("%d",&num);
  for(i =1;i<=num;i++){
    scanf(" %c%d",&a[i].egara,&a[i].value);
  }
  copy(num);
  BubbleSort(num);
  SelectionSort(num);


  for(i = 1;i<=num;i++){
    for(j =1;j<=num;j++){
      if(i!=j && a[j].value ==a[i].value){
	flag=1;
	d[k] = a[i].egara;
	k++;
      }
    }
  }
  k=0;
  for(i = 1;i<=num;i++){
    if(a[i].value == c[i].value){
      if(d[k] !=c[i].egara){
	flag1 = 1;
      }
      k++;
    }
  }
  
  for(i = 1;i<=num;i++){
    if(i == num){
      printf("%c%d\n",b[i].egara,b[i].value);
      printf("Stable\n");
    }
     else printf("%c%d ",b[i].egara,b[i].value);
  }

  for(i = 1;i<=num;i++){
    if(i == num){
      printf("%c%d\n",c[i].egara,c[i].value);
      if(flag ==1 && flag1==1){
	printf("Not stable\n");
      }
      else printf("Stable\n");
    }
    else   printf("%c%d ",c[i].egara,c[i].value);
  } 
    return 0;
  }
void copy(int n){
  int i;
  for(i =1;i<=n;i++){
    b[i].value = a[i].value;
    c[i].value = a[i].value;
    b[i].egara = a[i].egara;
    c[i].egara = a[i].egara;
  }
}
void BubbleSort(int n){
  int i,j,tmp;
  char tmp1;
  for(i = 1;i<=n;i++){
    for(j = n;j>=i+1;j--){
      if(b[j].value <b[j-1].value){
	tmp = b[j].value;
	b[j].value = b[j-1].value;
	b[j-1].value = tmp;
	tmp1 = b[j].egara;
	b[j].egara = b[j-1].egara;
	b[j-1].egara = tmp1;
      }
    }
  }
}
	
void SelectionSort(int n){
  int minj,i,tmp,j,flag=0;
  char tmp1;
  for(i = 1;i<=n;i++){
    minj = i;
    for(j=i;j<=n;j++){
      if(c[j].value <c[minj].value){
	minj =j;
      }
    }
    tmp = c[i].value;
    c[i].value = c[minj].value;
    c[minj].value = tmp;
    tmp1 = c[i].egara;
    c[i].egara = c[minj].egara;
    c[minj].egara = tmp1;
  }
}



Measured memory_bytes: 2112
#include <iostream>
#include <vector>
#include <cmath>

using namespace std;

int sento(int n);

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

	long long c[10][10] = { 0 };
	for (int i = 1; i <= n; i++) {
		c[sento(i)][i % 10]++;
	}

	long long ans = 0;
	for (int i = 1; i < 10; i++) {
		for (int j = 1; j < 10; j++) {
			ans += c[i][j] * c[j][i];
		}
	}
	cout << ans << endl;

	return 0;
}

int sento(int n)
{
	while (n / 10 != 0) {
		n /= 10;
	}

	return n;
}

Measured memory_bytes: 256
const stdin = require('fs').readFileSync('/dev/stdin', 'utf8').trim()

const s = stdin
  .split('\n')[0]
  .split('')
  .map(Number)

const ans = () => {
  const ops = []

  for (let i = 0; i < 2 ** 3; i++) {
    const op = []
    for (let j = 0; j < 3; j++) {
      if ((i >> j) & 1) {
        op.push('+')
      } else {
        op.push('-')
      }
    }

    ops.push(op)
  }

  const svn = ops.map(e => calculate(e)).filter(o => o.res === 7)

  return svn[0].calc.map(String).join('')
}

const calculate = op => {
  const calc = []
  for (let i = 0; i < 3; i++) {
    calc.push(s[i])
    calc.push(op[i])
  }
  calc.push(s[3])
  calc.push('=7')

  let res = calc[0]
  for (let i = 0; i < 7; i++) {
    if (calc[i] === '+') {
      res += calc[i + 1]
    } else if (calc[i] === '-') {
      res -= calc[i + 1]
    }
  }

  return { res, calc }
}

console.log(ans())


Measured memory_bytes: 7372
#include "bits/stdc++.h"
using namespace std;
#define INF 1000000000
#define rep(i, n) for(int i = 0; i < n; i++)
#define ALL(x) (x).begin(), (x).end()  //昇順
#define RALL(x) (x).rbegin(), (x).rend() // 降順
const long long mod = 1e9+7;
typedef priority_queue<int> PQ;
typedef vector<long long> Vl;
typedef vector<int> VI;  // VI a(n);
typedef vector<string> VS;  
typedef vector<char> VC; 
typedef vector<VS> VSS;
typedef vector<VC> VCC;    
typedef vector<VI> VVI;   // VVI a(n,vector<int>(m)) n * m 
typedef vector<Vl> VVl;
typedef pair<int, int> PII;
typedef map<int, int> MP;   //MP a;
typedef vector<pair<int, int> > PS;
typedef long long ll;  //ll とdoubleは違う
template <class T>  // chmax(max, a);
bool chmax(T &a, const T &b)
{
    if (a < b)
    {
        a = b;
        return 1;
    }
    return 0;
}
template <class T> //chmin(min,a)
bool chmin(T &a, const T &b)
{
    if (b < a)
    {
        a = b;
        return 1;
    }
    return 0;
}
template<typename T>   // operator << (cout,a);
ostream& operator << (ostream& os, vector<T>& v) {
    os << "{";
    rep(i, (int)v.size()) { os << v[i] << (i < v.size() - 1 ? ", " : ""); }
    os << "}";
    return os;
}

int main(){
    double c,d,n,r,g,m,p,h,k,max=-10000000,min=1000000000,ans=0,sum=0;
    string s;
    bool f=true;
    cin >> n;
    VI t(n);
    VI x(n);
    VI y(n);
    rep(i,n){
        cin >> t[i] >> x[i] >> y[i];
	}
    if(t[0]==x[0]+y[0])
        for(int i=1; i<n;i++){
            if((t[i]-t[i-1]) < abs(x[i]+y[i]-(x[i-1]+y[i-1]))){ 
                cout << "No" << endl;
                return 0;
            }
            if((t[i]-t[i-1])%2 != abs(x[i]+y[i]-(x[i-1]+y[i-1]))%2){
                cout << "No" << endl;
                return 0;
            }
        }
    else{
        cout << "No" << endl;
        return 0;
    }
    cout << "Yes" << endl;
    return 0;
}

Measured memory_bytes: 1408
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;

int main() {
  cin.tie(0);
  ios_base::sync_with_stdio(false);
  cout << fixed << setprecision(10);
  
  int n;
  while (cin >> n, n) {
    map<string, int> mp;
    cin.ignore();
    for (int i = 0; i < n; i++) {
      string s;
      getline(cin, s);
      stringstream ss(s);
      while (ss >> s) mp[s]++;
    }
    char k;
    cin >> k;
    vector<string> v;
    for (auto i : mp) {
      string s = i.first;
      if (s[0] != k) continue;
      v.emplace_back(s);
    }
    sort(v.begin(), v.end(), [&](string a, string b) {
      return mp[a] != mp[b] ? mp[a] > mp[b] : a < b;
    });
    if (v.empty()) {
      cout << "NA" << endl;
    } else {
      int lim = min(5, (int)v.size());
      for (int i = 0; i < lim; i++) {
        cout << v[i] << " \n"[i + 1 == lim];
      }
    }
  }

  return 0;
}


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

int main()
{
    char c;
    int count=0,kaisu = 0;
    char moji = '0';
    while( cin >> c ){
        kaisu++;
        if (c == moji){count++;}
        
        if (moji == '0'){moji = '1';}else{moji = '0';}
    }
    if (kaisu-count < count){count = kaisu - count;}
    cout << count;
}

Measured memory_bytes: 256
/*.....Bismillahir Rahmanir Rahim.....*/
#include <iostream>
#include <algorithm>
#include <stdio.h>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <cstring>
#include <unordered_map>
#include <queue>
#define   mod  998244353
#define   int  long long 
#define   ld long double
#define   pb push_back
#define   sz(x)  (int)x.size()
#define   ff first
#define   ss second
#define   pii  pair<int,int> 
#define   pb  push_back
#define   eb  emplace_back
#define   lcm(a,b)  (a*b)/gcd(a,b)
using namespace std;

const int inf=10000000;
signed main(){
	map <pii,int> mp; 
	int n,m;
	cin>>n>>m;
	int a[1001],b[1001],c[1001],dist[1001][1001];	
	for(int i=1;i<=m;++i) { 
		cin>>a[i]>>b[i]>>c[i] ; 
		if (mp[{a[i],b[i]}] ) 
			mp[{a[i],b[i]}] = mp[{b[i],a[i]}] = min(mp[{a[i],b[i]}],c[i]);
		else 
			mp[{a[i],b[i]}] = mp[{b[i],a[i]}] = c[i] ; 
	} 
	for(int i=1;i<=n;++i){
		for(int j=1;j<=n;++j){
			if(i==j) dist[i][j]=0;
			else dist[i][j]=inf;
		}
	}
	for(int i=1;i<=m;++i){
		dist[a[i]][b[i]]=min(dist[a[i]][b[i]],c[i]);			dist[b[i]][a[i]]=min(dist[b[i]][a[i]],c[i]);
	}
	for(int k=1;k<=n;++k){
		for(int i=1;i<=n;++i){
			for(int j=1;j<=n;++j){
				dist[i][j]=min(dist[i][j],dist[i][k]+dist[k][j]);
			}
		}
	}
	int ans=0;
	for(int i=1;i<=n;++i){
		for(int j=1;j<=n;++j){
			if(mp[{i,j}]) {
				if ( mp[{i,j}] > dist[i][j] ) ans++; 
			}
		}
	}
	cout<<ans/2<<endl;
}
/*
3 3
1 2 1
1 3 1
2 3 3

*/


Measured memory_bytes: 3328
#include <iostream>
#include <string>
#include <sstream>
#include <algorithm>
#include <vector>
#include <utility>
#include <functional>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <deque>
#include <ctime>
  
using namespace std;
  
#define rep(i,n) REP(i,0,n)
#define REP(i,s,e) for(int i=(s); i<(int)(e); i++)
#define pb push_back
#define mp make_pair
#define all(r) (r).begin(),(r).end()
#define rall(r) (r).rbegin(),(r).rend()
#define fi first
#define se second
#define println(X) cout<<X<<endl;
#define DBG(X) cout<<#X<<" : "<<X<<endl;
  
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vii;
typedef vector<ll> vl;
typedef vector<vl> vll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
 
const int INF = 1e9;
const ll LINF = 1e18;
const ll MOD = 1e9 + 7;
double EPS = 1e-8;
const double PI = acos(-1);

ll dp[(1<<15)+10][5];

int main(){
	int n;
	while(cin>> n && n) {
		for(int i = 0; i < (1<<15) + 10; i++) rep(j, 5) dp[i][j] = 0;
		dp[0][0] = 1;
		for(int i = 1; i * i <= n; i++){
			for(int j = 0; j + i * i <= n; j++) {
				rep(k, 4) dp[j + i * i][k + 1] += dp[j][k];
			}
		}
		cout<<dp[n][1] + dp[n][2] + dp[n][3] + dp[n][4] << endl;
	}
}

Measured memory_bytes: 4340
import java.util.ArrayList;
import java.util.Scanner;
class Main{


	static final int MOD = 1000000007;


	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);			//文字の入力
		int n = sc.nextInt();
		

		if(n % 2 == 0){
			System.out.println(((double)1/2));
		}else{
			System.out.println((double)((double)(n/2+1)/n));
		}
				
		
		
	}




	static int upperbond(int k,int min,int[] data){		//kより小さい最大の値をdataの中から探し、返す二分探索
		int max = data.length;
//		if(min == data.length-1){
//			if(data[min] > k){
//				return min;
//			}
//		}

		while(max-min > 1){
			int mid = (max+min)/2;
			if(data[mid] >= k){
				max = mid;
			}else{
				min = mid;
			}
		}

		return max;
	}

	static int lowerbond(int k,int min,int[] data){		//kより大きい最小の値をdataの中から探し、返す二分探索
		int max = data.length;

		while(max-min > 1){
			int mid = (max+min)/2;
			if(data[mid] >= k){
				max = mid;
			}else{
				min = mid;
			}
		}
		return min;
	}



	static int gcd(int a,int b){				//最大公約数を返す
		if(b == 0){
			return a;
		}else{
			return gcd(b, a%b);
		}
	}
	static long gcd(long a,long b){
		if(b == 0){
			return a;
		}else{
			return gcd(b, a%b);
		}
	}



	static long lcm (long a, long b) {
		long g = gcd(a,b);
		return a/g*b;
	}




}


class Edge extends ArrayList<P>{

}

class P{
	int to;
	long cost;
	P(int to,long cost){
		this.to = to;
		this.cost = cost;
	}
}


class Pair implements Comparable{
	int from;
	int end;
	@Override
	public int compareTo(Object other) {
		Pair otherpair = (Pair)other;

		return   from- otherpair.from;
	}








}






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

int main(){
  string x,y;
  cin>>x>>y;
  sort(x.begin(),x.end());
  sort(y.begin(),y.end());
  reverse(y.begin(),y.end());
  if(x<y){
  cout<<"Yes"<<endl;
  }
  else{
  cout<<"No"<<endl;
  }
}

Measured memory_bytes: 256
#include <stdio.h>
#include <string.h>
int main(void) {
	int i,l,p=0;
	char x[128];
	while(scanf("%s",x)!=EOF){
		l=strlen(x);
		for(i=0;i<l/2+1;i++){
			if(x[i]!=x[l-1-i])
				break;
			}
		if(i==l/2+1)
			p++;
	}
	printf("%d\n",p);
	return 0;
}

Measured memory_bytes: 540
#include <bits/stdc++.h>
 
using namespace std;
 
#define rep(i, n) for(int i=0; i<(n); i++)
#define FOR(i, m, n) for(int i=(m);i<(n);i++)
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(),(x).end()
#define SORT(x) sort((x).begin(),(x).end())
#define REVE(x) reverse((x).begin(),(x).end())
#define mp make_pair
#define pb push_back
 
typedef vector<int> VI;
typedef vector<string> VS;
typedef vector<vector<int> > VVI;
typedef pair<int, int> PII;
typedef long long LL;
typedef vector<bool> VB;
 
int main() {
    int n,m;
    cin >> n >> m;
    VI a(m,0);
    rep(i,m) {
        cin >> a[i];
    }

    int count = 0;

    rep(i,m) {
        if(n-a[i]>=0) {
            n -= a[i];
        } else {
            cout << -1 << endl;
            return 0;
        }
    }
    cout << n << endl;
}

Measured memory_bytes: 3588
import java.util.*;
import java.io.*;
import java.text.*;
public class Main{
    //SOLUTION BEGIN
    void pre() throws Exception{}
    void solve(int TC) throws Exception{
        int n = ni(), k = ni();
        if(k==1)pn(0);
        else pn(n-k);
    }
    //SOLUTION END
    void hold(boolean b)throws Exception{if(!b)throw new Exception("Hold right there, Sparky!");}
    long mod = (long)1000000007, IINF = (long)1e18;
    final int INF = (int)1e9, MX = (int)2e5+5;
    DecimalFormat df = new DecimalFormat("0.00000000000");
    double PI = 3.141592653589793238462643383279502884197169399, eps = 1e-8;
    static boolean multipleTC = false, memory = false;
    FastReader in;PrintWriter out;
    void run() throws Exception{
        in = new FastReader();
        out = new PrintWriter(System.out);
        //Solution Credits: Taranpreet Singh
        int T = (multipleTC)?ni():1;
        pre();for(int t = 1; t<= T; t++)solve(t);
        out.flush();
        out.close();
    }
    public static void main(String[] args) throws Exception{
        if(memory)new Thread(null, new Runnable() {public void run(){try{new Main().run();}catch(Exception e){e.printStackTrace();}}}, "1", 1 << 28).start();
        else new Main().run();
    }
    long gcd(long a, long b){return (b==0)?a:gcd(b,a%b);}
    int gcd(int a, int b){return (b==0)?a:gcd(b,a%b);}
    int bit(long n){return (n==0)?0:(1+bit(n&(n-1)));}
    void p(Object o){out.print(o);}
    void pn(Object o){out.println(o);}
    void pni(Object o){out.println(o);out.flush();}
    String n()throws Exception{return in.next();}
    String nln()throws Exception{return in.nextLine();}
    int ni()throws Exception{return Integer.parseInt(in.next());}
    long nl()throws Exception{return Long.parseLong(in.next());}
    double nd()throws Exception{return Double.parseDouble(in.next());}

    class FastReader{
        BufferedReader br;
        StringTokenizer st;
        public FastReader(){
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        public FastReader(String s) throws Exception{
            br = new BufferedReader(new FileReader(s));
        }

        String next() throws Exception{
            while (st == null || !st.hasMoreElements()){
                try{
                    st = new StringTokenizer(br.readLine());
                }catch (IOException  e){
                    throw new Exception(e.toString());
                }
            }
            return st.nextToken();
        }

        String nextLine() throws Exception{
            String str = "";
            try{   
                str = br.readLine();
            }catch (IOException e){
                throw new Exception(e.toString());
            }  
            return str;
        }
    }
}

Measured memory_bytes: 25300
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using P = pair<int, int>;
using vint = vector<int>;
using vvint = vector<vint>;
using vll = vector<ll>;
using vvll = vector<vll>;
using vchar = vector<char>;
using vvchar = vector<vchar>;
using vp = vector<P>;
using vpp = vector<pair<P, P>>;
using vvp = vector<vp>;

#define rep(i, n) for (int i = 0; i < n; ++i)
#pragma region Debug
istream &operator>>(istream &is, P &a)
{
    return is >> a.first >> a.second;
}
ostream &operator<<(ostream &os, const P &a) { return os << "(" << a.first << "," << a.second << ")"; }

template <typename T>

void view(const std::vector<T> &v)
{
#ifndef ONLINE_JUDGE
    for (const auto &e : v)
    {
        std::cout << e << " ";
    }
    std::cout << std::endl;
#endif
}
template <typename T>
void view(const std::vector<std::vector<T>> &vv)
{
    for (const auto &v : vv)
    {
        view(v);
    }
}
#pragma endregion

int main()
{
    int n, q;
    cin >> n >> q;
    int size = 1 << (int)(log2(n) + 1) + 1;
    vint seg(size, 0);

    auto get = [&](int i) {
        int k = i + n;
        int ans = seg[k];
        while (k)
        {
            k /= 2;
            ans += seg[k];
        }
        return ans;
    };
    auto addRange = [&](int s, int t, int x) {
        int l = s + n,
            r = t + n;
        while (l < r)
        {
            if (l % 2)
            {
                seg[l] += x;
                l++;
            }
            l /= 2;
            if (r % 2)
            {
                seg[r - 1] += x;
                r--;
            }
            r /= 2;
        }
    };
    rep(i, q)
    {
        int com, s, t, x;
        cin >> com;
        if (com)
        {
            cin >> t;
            int ans = get(t);
            cout << ans << "\n";
        }
        else
        {
            cin >> s >> t >> x;
            addRange(s, t + 1, x);
        }
    }

    return 0;
}


Measured memory_bytes: 4088