akhauriyash/Code-Regression huggingface dataset:
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.NoSuchElementException;

public class Main {
	int N, M;
	int[] P,Q;


	public void solve() {
		P = new int[1000];
		Q = new int[2000000];
		while (true) {
			N = nextInt();
			M = nextInt();
			if(N+M==0)break;

			for (int i = 0; i < N; i++) {
				P[i] = nextInt();
			}


			int q = 1;
			for (int i = 0; i < N; i++) {
				Q[q++] = P[i];
				for(int j = 0;j < N;j++){
					Q[q++] = (P[i] + P[j] > M ? 0 : P[i]+P[j]);
				}
			}

			Arrays.sort(Q,0, q);

			int ans = 0;
			for (int i = 0;i < q;i++) {
				int key = M-Q[i];
				int low = 0;
				int high = q;

				while(high-low>1){
					int mid = high+low>>1;

					if(Q[mid] < key){
						low = mid;
					}else{
						high = mid;
					}
				}

				ans = Math.max(ans, Q[low]+Q[i]);
			}
			out.println(ans);
		}
	}
	public static void main(String[] args) {
		out.flush();
		new Main().solve();
		out.close();
	}

	/* Input */
	private static final InputStream in = System.in;
	private static final PrintWriter out = new PrintWriter(System.out);
	private final byte[] buffer = new byte[2048];
	private int p = 0;
	private int buflen = 0;

	private boolean hasNextByte() {
		if (p < buflen)
			return true;
		p = 0;
		try {
			buflen = in.read(buffer);
		} catch (IOException e) {
			e.printStackTrace();
		}
		if (buflen <= 0)
			return false;
		return true;
	}

	public boolean hasNext() {
		while (hasNextByte() && !isPrint(buffer[p])) {
			p++;
		}
		return hasNextByte();
	}

	private boolean isPrint(int ch) {
		if (ch >= '!' && ch <= '~')
			return true;
		return false;
	}

	private int nextByte() {
		if (!hasNextByte())
			return -1;
		return buffer[p++];
	}

	public String next() {
		if (!hasNext())
			throw new NoSuchElementException();
		StringBuilder sb = new StringBuilder();
		int b = -1;
		while (isPrint((b = nextByte()))) {
			sb.appendCodePoint(b);
		}
		return sb.toString();
	}

	public int nextInt() {
		return Integer.parseInt(next());
	}

	public long nextLong() {
		return Long.parseLong(next());
	}

	public double nextDouble() {
		return Double.parseDouble(next());
	}
}

Measured memory_bytes: 38104
N=[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]
M=int(input())
print(N[M-1])

Measured memory_bytes: 3060
#include <bits/stdc++.h>
using namespace std;
int main() {
    int k;
    cin >> k;

    if (k % 2 == 0) {
        cout << k * k / 4 << endl;
    } else {
        cout << (k + 1) * (k - 1) / 4 << endl;
    }
    return 0;
}

Measured memory_bytes: 256
//Author: kaiyu
#include <iostream>
#include <algorithm>
#include <cmath>
#include <map>
#include <vector>
#include <set>
#include <unordered_set>
#include <unordered_map>
#include <cstring>
#include <string>
#include <queue>
#include <stack>
#include <numeric>
#include <iomanip>
#include <climits>
using namespace std;
typedef long long ll;
#define sz(x) ((long long)(x).size())
#define all(x)  x.begin(),x.end()
#define endl "\n"
#define ff first
#define ss second
#define mp make_pair
#define pb push_back
#define setbits(x)      __builtin_popcountll(x)
#define zrobits(x)      __builtin_ctzll(x)
#define mod             1000000007
#define vi vector<ll>
#define vvi vector<vector<ll>>
#define pii pair<int,int>
#define tt ll t;cin >> t;while(t--)
#define int3(x,y,z) ll x,y,z;cin >> x >> y >> z;
#define int2(x,y) ll x,y;cin >> x >>y;
#define int1(x) ll x;cin>>x;
#define  fio ios::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL);
ll power(ll a,ll b,ll m=mod){ ll ans=1; a=a%m;  while(b>0) {  if(b&1)  ans=(1ll*a*ans)%m; b>>=1;a=(1ll*a*a)%m;}return ans;}

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


bool cmp(pair<string,int>p1,pair<string,int>p2) {
    return p1.ss > p2.ss;
}
bool cmp2(string x1 , string x2) {
    return sz(x1) < sz(x2);
}

const int MAXN = 2 * 100 + 10;
int main(){
    int a,b,c,k;
    cin >> a >> b >> c >> k;
    k = k - a;
    int sum = 0;
    if(k <= 0 ){
        k = k+a;
        sum = k;
        cout << sum << endl;
        return 0;
    }
    else {
        sum = a;
    }

    k = k - b;
    if(k <= 0) {
        k = 0;
        cout << sum << endl;
        return 0;
    }
    k = k - c;
    if(k <= 0) {
        k = k + c;
        sum = sum - k;
        cout << sum << endl;
        return 0;
    }
    else {
        sum = sum - c;
        cout << sum << endl;
        return 0;
    }
    return 0;
}

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

typedef long long ll;
typedef pair<int,int> ii;
typedef vector<int> vi;
typedef vector<ii> vii;

const int  MOD=1000000007;
const int  INF= int(1e9);
const int  MAX= int(1e6);



int main() {
    ios_base::sync_with_stdio(false);
    int n, k;
    cin >> n >> k;
    vi dp(n),h(n);
    for(int i = 0; i < n; i++) {
        cin >> h[i];
        dp[i] = INF;
    }
    dp[0] = 0;
    for(int i = 1 ; i < n ; i++) {
        for( int j = 1 ; j <= k ; j++) {
            if (i-j >= 0) {
                dp[i] = min(dp[i],dp[i-j] + abs(h[i] - h[i-j]));
            }
        }
    }
    cout<<dp[n-1]; 

    return 0;
}



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

int main(void){
	int i,n;
	int s[1000];
	double sum_1,sum_2,m,deta,aa,a;

	n=1;
	while(n!=0){
		scanf("%d",&n);
		if(n==0){
			break;
		}
		sum_1=0;
		for(i=0;i<n;i++){
			scanf("%d",&s[i]);
			sum_1=sum_1+s[i];
		}
		m=sum_1/n;
		sum_2=0;
		for(i=0;i<n;i++){
			deta=pow((s[i]-m),2);
			sum_2=deta+sum_2;
		}
		aa=sum_2/n;

		a=sqrt(aa);

		printf("%lf\n",a);
	}

	return 0;
}

Measured memory_bytes: 636
#!/usr/bin/env python3
import sys


def solve(N: int, i: int):
    print(N - i + 1)


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    i = int(next(tokens))  # type: int
    solve(N, i)


if __name__ == '__main__':
    main()


Measured memory_bytes: 2940
#include <stdio.h>

int main() {
    int N;
    scanf("%d", &N);

    int amari;
    amari = N % 10;
    char *ans;
    switch(amari) {
        case 0:
        case 1:
        case 6:
        case 8:
            ans = "pon";
            break;
        case 2:
        case 4:
        case 5:
        case 7:
        case 9:
            ans = "hon";
            break;
        case 3:
            ans = "bon";
            break;
    }
    printf("%s\n", ans);
    return 0;
}



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

int main() {
  int H, W;
  cin >> H >> W;
 vector<string> image(H);
  for(int i = 0; i < H; i++){
    cin >>  image.at(i);
    }
  vector<string> kakudai(2*H);
  for(int i = 0; i < H; i++){
    string c = image.at(i);
    kakudai.at(2*i) = c;
    kakudai.at(2*i+1) = c;
  }
  for(int i = 0; i < 2*H; i++){
    cout << kakudai.at(i) << endl;
  }
}


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

int main() {
  int H, W;
  cin >> H >> W;
  
  for (int i = 0; i < H + 2; i++){
  	vector<char> vec(W+2, '#');
    
    if(i > 0 && i < H + 1){
    	for (int j = 0; j < W; j++){
        	cin >> vec.at(j+1);
        }
    }
    
    for (int k =0; k < W+2; k++){
    	cout << vec.at(k);
    }
    cout << endl;
  }
  
}








Measured memory_bytes: 3592
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<vector>
#include<cmath>
#include<algorithm>
#include<map>
#include<queue>
#include<deque>
using namespace std;
typedef long long int LL;
typedef pair<int,int> P;
typedef pair<int,pair<int,int> > PP;
typedef pair<LL,int> LP;
const int INF=1<<30;
 
 
void array_show(int *a,int n){
	for(int i=0;i<n;i++)printf("%d%c",a[i],(i!=n-1?' ':'\n'));
}
void array_show(LL *a,int n){
	for(int i=0;i<n;i++)printf("%lld%c",a[i],(i!=n-1?' ':'\n'));
}
 
vector<P> v1;
 
int main(){
	int h,w,n;
	int i,j,k;
	int a,b,c,s;
	int dis=0;
	cin>>h>>w>>n;
	for(i=0;i<n;i++){
		cin>>a>>b;
		v1.push_back(make_pair(a,b));
	}
	sort(v1.begin(),v1.end());
	s=h;
	for(i=0;i<n;i++){
		a=v1[i].first-v1[i].second;
		if(a<dis)continue;
		if(a==dis)dis++;
		else s=min(s,v1[i].first-1);
	}
	cout<<s<<endl;
}

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

using namespace std;

int dp[100010];

int main() {
    int N;
    
    int power;

    cin >> N;
    dp[0] = 0;
    for(int i = 1; i <= N; i++) {
        dp[i] = 100010;
        power = 1;
        while(power <= i) {
            dp[i] = min(dp[i], dp[i-power] + 1);
            power *= 6;
        }
        
        power = 1;
        while(power <= i) {
            dp[i] = min(dp[i], dp[i-power] + 1);
            power *= 9;
        }
    }

    cout << dp[N] << endl;

    return 0;
}


Measured memory_bytes: 640
#include<iostream>
#include<cstdio>
#include<cmath>
#include<complex>
#include<vector>
#include<queue>
using namespace std;
typedef complex<int> xy_t;
int main()
{
  int n,k = 1;
  double x,y,sum = 0.0;
  queue<double> answer;
  while(cin >> n && n > 0){
    vector<xy_t> p(n);
    for( int i = 0; i < n; ++i){
      cin >> x >> y;
      p[i] = xy_t(x,y);
    }
    for( int i = 0; i + 2 < n; ++i){
      xy_t a = p[0],b = p[i + 1],c = p[i + 2];
      sum += ((conj(b - a)*(c - a)).imag())/2.0;
    }
    answer.push(abs(sum));
    sum = 0.0;
  }
  while(!answer.empty()){
    printf("%d %.1f\n",k,answer.front());
    answer.pop();
    ++k;
  }
}

Measured memory_bytes: 1252
#include <iostream>
#include <string>
#include <queue>
#include <stack>
#include <algorithm>
#include <list>
#include <vector>
#include <complex>
#include <utility>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <climits>
#include <bitset>
#include <ctime>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <cassert>
#include <cstddef>
#include <iomanip>
#include <numeric>
#include <tuple>
#include <sstream>
#include <fstream>

using namespace std;
#define REP(i, n) for (int (i) = 0; (i) < (n); (i)++)
#define FOR(i, a, b) for (int (i) = (a); (i) < (b); (i)++)
#define RREP(i, a) for(int (i) = (a) - 1; (i) >= 0; (i)--)
#define FORR(i, a, b) for(int (i) = (a) - 1; (i) >= (b); (i)--)
#define DEBUG(C) cerr << #C << " = " << C << endl;
using LL = long long;
using VI = vector<int>;
using VVI = vector<VI>;
using VL = vector<LL>;
using VVL = vector<VL>;
using VD = vector<double>;
using VVD = vector<VD>;
using PII = pair<int, int>;
using PDD = pair<double, double>;
using PLL = pair<LL, LL>;
using VPII = vector<PII>;
#define ALL(a) begin((a)), end((a))
#define RALL(a) rbegin((a)), rend((a))
#define SORT(a) sort(ALL((a)))
#define RSORT(a) sort(RALL((a)))
#define REVERSE(a) reverse(ALL((a)))
#define MP make_pair
#define FORE(a, b) for (auto &&a : (b))
#define FIND(s, e) ((s).find(e) != (s).end())
#define EB emplace_back

const int INF = 1e9;
const int MOD = INF + 7;
const LL LLINF = 1e18;

void solve(string s) {
    set<string> se;
    REP(i, s.size() - 1) {
        string sbufa = s.substr(0, i + 1);
        string sbufb = s.substr(i + 1);
        string sbufar = sbufa; REVERSE(sbufar);
        string sbufbr = sbufb; REVERSE(sbufbr);
        se.insert(sbufa + sbufb);
        se.insert(sbufa + sbufbr);
        se.insert(sbufar + sbufbr);
        se.insert(sbufar + sbufb);
        se.insert(sbufb + sbufa);
        se.insert(sbufb + sbufar);
        se.insert(sbufbr + sbufa);
        se.insert(sbufbr + sbufar);
    }
    //FORE(el, se) cout << el << endl;
    cout << se.size() << endl;
    return;
}

signed main(void) {
    int n, p, m, w, h;
    string s;
    int a, b, c, d;
    while (cin >> n) {
        REP(i, n) cin >> s, solve(s);
        return 0;
    }
}

Measured memory_bytes: 3200
#include <bits/stdc++.h>
using namespace std;
int main() {
  int N;
  cin >> N;
  long long a;
  long long min = 1000000000;
  long long max = -1;
  for (int i=0; i <N; i++) {
    cin >> a;
    if (a < min) {
      min = a;
    }
    if (a > max) {
      max = a;
    }
  }
  cout << max - min  << endl;
}

Measured memory_bytes: 3592
#include <bits/stdc++.h>
#include <stdio.h>
#include<iostream>
#include<cstdio>
#include<bitset>
#include<algorithm>
#include<vector>
#include<list>
#include<queue>
#include<stack>
#include<string>
#include<string.h>
#include<cmath>
#include<utility>
#include<functional>
#include<map>
#include<set>
#include<cctype>
#include<fstream>
#include <numeric>
#include <iomanip>
#include <cstring> 
using namespace std;
using ll=long long;

#define FOR(i, a, b) for( int i=(a);i<=(b);i++)
#define RFOR(i, a, b) for( int i=(a);i>=(b);i--)
#define LFOR(i, a, b) for( long long int i=(a);i<=(b);i++)
#define LRFOR(i, a, b) for(long long int i=(a);i>=(b);i--)
#define MOD 1000000007
#define LLONG_MAXs 9223372036854775800

#include <iostream>
#include <cmath>
using namespace std;
 

 
bool isPrimeNum( ll x ){ // 素数である場合 true を返す
  if( x <= 1 ){ // 1以下である場合は素数でないことがすぐにわかる
    return false;
  }
  // sqrt( double型 ) は引数の平方根を double型で返すので、int型でキャスト
  int n = (int)sqrt( (double)x );
  for( int i = 2; i <= n; i++ ){
    if( x % i == 0 ){ // 割り切る整数がある場合、即判定終了
      return false;
    }
  }
  return true; // 割り切る整数がない場合、素数である
}

constexpr ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
constexpr ll lcm(ll a,ll b){return a*b/gcd(a,b);}
constexpr ll abs(ll a,ll b){
if(a>=b)return a-b;
if(a<b)return b-a;
}
constexpr ll min(ll a,ll b){
if(a>=b)return b;
if(a<b)return a;
}

constexpr ll max(ll a,ll b){
if(a>=b)return a;
if(a<b)return b;
}

int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};

struct UnionFind {
    vector<int> par; // par[i]:iの親の番号　(例) par[3] = 2 : 3の親が2

    UnionFind(int N) : par(N) { //最初は全てが根であるとして初期化
        for(int i = 0; i < N; i++) par[i] = i;
    }

    int root(int x) { // データxが属する木の根を再帰で得る：root(x) = {xの木の根}
        if (par[x] == x) return x;
        return par[x] = root(par[x]);
    }

    void unite(int x, int y) { // xとyの木を併合
        int rx = root(x); //xの根をrx
        int ry = root(y); //yの根をry
        if (rx == ry) return; //xとyの根が同じ(=同じ木にある)時はそのまま
        par[rx] = ry; //xとyの根が同じでない(=同じ木にない)時：xの根rxをyの根ryにつける
    }

    bool same(int x, int y) { // 2つのデータx, yが属する木が同じならtrueを返す
        int rx = root(x);
        int ry = root(y);
        return rx == ry;
    }
};

int main() {
  ll N;
  cin>>N;
  ll T[N];
  ll A[N];

  FOR(i,0,N-1){
    cin>>T[i]>>A[i];
  }

  ll ans,ta,tb;
  ta=T[0];
  tb=A[0];

  FOR(i,1,N-1){
    ll tmpa,tmpb;
    tmpa=ta/T[i];
    if(ta%T[i]!=0)tmpa++;
    tmpb=tb/A[i];
    if(tb%A[i]!=0)tmpb++;

    ll tmp=max(tmpa,tmpb);
    ta=tmp*T[i];
    tb=tmp*A[i];
  }



  cout<<ta+tb<<endl;



  return 0;
}
 


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

int main(void)
{
  int n, k, x, y;
  std::cin >> n >> k >> x >> y;

  int sum = 0;
  for (int i = 1; i <= n; i++) {
    if (i <= k) {
      sum += x;
    }
    else {
      sum += y;
    }
  }

  std::cout << sum << std::endl;

  return 0;
}

Measured memory_bytes: 3568
k = int(input())
import math
import fractions
ans = 0
e = 0
d = 0
for a in range(1,k+1):
    for b in range(a,k+1):
        e = math.gcd(a,b)
        #e = fractions.gcd(a,b)
        for c in range(b,k+1):
            d = math.gcd(e,c)
            #d = fractions.gcd(e,c)
            if a != b and b!= c and a!= c:
                ans+= d*6
            elif (a==b and a!=c) or (a==c and a!= b) or (b == c and a!= b):
                ans+= d*3
            else:
                ans+= d
print(ans)


Measured memory_bytes: 10344
#include <cmath>
#include <iostream>
#include <stdio.h>
#include <string>
#include <sstream>
#include <iomanip>
#include <algorithm>
#include <vector>
#include <set>
#include <limits.h>
#include <map>
#include <numeric>

namespace test {
	std::string to_string (char val) {
		return std::string (1, val);
		// return std::string{val};
	}
	//if( str.find ("r") != string::npos)
}

using namespace std;
typedef long long int llint;

int main (void) {
	char a ,b; cin >> a >> b;
	if (a == 'H') {
		cout << b << endl;
	}
	else {
		cout << (b == 'H' ? 'D' : 'H' ) << endl;
	}
	return 0;
}

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

signed main() {
  int N, C, K;
  cin >> N >> C >> K;
  
  vector<int> T(N);
  for( int i = 0; i < N; i++ ) cin >> T.at(i);
  sort( T.begin(), T.end() );
  
  int bus = 1;
  int count = 0; //乗客数カウント
  int time = 0; //1人目の客の乗車時刻
  for( int i = 0; i < N; i++ ){
    if( count == C ){
      bus++;
      count = 0;
    }
    if( count == 0 ){
      time = T.at(i);
      count++;
    }else{
      if( T.at(i) <= time + K ) count++;
      else{
        bus++;
        count = 1;
        
        time = T.at(i);
      }
    }
    
  }
  
  cout << bus << endl;
      
    
}



Measured memory_bytes: 1024
#include <iostream>
#include <string>
#include <utility>
#include <stack>
#include <vector>
#include <queue>
#include <algorithm>
#include <map>
#include <climits>
#include <set>
#include <cmath>

using namespace std;
long long A[100000];
map <long long, int> AtoInd;
long long cum_max[100000];
long long cum_min[100000];
int main(){
    int N;
    long long T;
    cin >> N >> T;
    for(int i = 0; i < N; i++){
        cin >> A[i];
    }

    cum_max[0] = A[0];
    cum_min[0] = A[0];

    for(int i = 1; i < N; i++){
        cum_min[i] = min(cum_min[i - 1], A[i]);
    }

    long long max_profit = 0;
    for(int i = 0; i < N; i++){
        max_profit = max(max_profit, A[i] - cum_min[i]);
    }

    int ans = 0;
    for(int i = 0; i < N; i++){
        if((A[i] - cum_min[i]) == max_profit){
            ans ++;
        }
    }
    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 1792
#include <bits/stdc++.h>
#pragma clang diagnostic push
#pragma clang diagnostic ignored "-Weverything"
#include <boost/multi_array.hpp>
#include <boost/optional.hpp>
#include <boost/range/adaptors.hpp>
#include <boost/range/algorithm.hpp>
#include <boost/range/irange.hpp>
#pragma clang diagnostic pop

using namespace std;

static std::string YYMM = "YYMM";
static std::string MMYY = "MMYY";
static std::string AMBIGUOUS = "AMBIGUOUS";
static std::string NA = "NA";

std::string solve(int64_t s) {
  int const back = s % 100;
  int const front = s / 100;
  bool const backCanMM = back > 0 && back < 13;
  bool const frontCanMM = front > 0 && front < 13;
  if (frontCanMM) {
    if (backCanMM) {
      return AMBIGUOUS;
    } 
      return MMYY;
    
  } else {
    if (backCanMM) {
      return YYMM;
    } 
      return NA;
    
  }
}

int main() {
  std::cin.tie(nullptr);
  std::ios::sync_with_stdio(false);
  int64_t s;
  std::cin >> s;
  auto const res = solve(s);
  std::cout << res << std::endl;
  return 0;
}


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

int main(){
    int x,y,r,w,h;
    cin>>w>>h>>x>>y>>r;
    
    if(((x-r)<0 || (x+r)>w) || ((y-r)<0 || (y+r)>h)) cout<<"No"<<endl;
    else cout<<"Yes"<<endl;
}


Measured memory_bytes: 3104
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
using Graph = vector<vector<int>>;
const int INT_INF = 1001001001;
//stoi(s) : string→int stoll(s) :string→longlong  int→string to_string(i)
const double PI = acos(-1.0);
const int MAXN = 10010;
//小数点の表し方 cout << fixed << setprecision(5);
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
int h,n;



int main(){
    cin >> h >> n;
    vector<vector<int>> dp(n+1,vector<int>(h+1,INT_INF)); //dp[i][j] i番目までの魔法を使ってjのダメージを与得る時の魔法の最小値
    vector<int> a(n),b(n);
    for(int i=0;i<n;i++){
        cin >> a[i] >> b[i];
    } 
    dp[0][0] = 0;
    for(int i=0;i<n;i++){
        for(int j=0;j<=h;j++){
            chmin(dp[i+1][j],dp[i][j]);
            chmin(dp[i+1][min(j+a[i],h)],dp[i+1][j] + b[i]);
        }
    } 
    cout << dp[n][h] << endl;
}

Measured memory_bytes: 39424
#pragma GCC optimize("Ofast")
#define _USE_MATH_DEFINES
#include "bits/stdc++.h"

using namespace std;

using u8 = uint8_t;
using u16 = uint16_t;
using u32 = uint32_t;
using u64 = uint64_t;
using i8 = int8_t;
using i16 = int16_t;
using i32 = int32_t;
using i64 = int64_t;

constexpr char newl = '\n';
constexpr double eps = 1e-10;

#define FOR(i,a,b) for (int i = (a); i < (b); i++)
#define F0R(i,b) FOR(i,0,b)
#define RFO(i,a,b) for (int i = ((b)-1); i >=(a); i--)
#define RF0(i,b) RFO(i,0,b)
#define fi first
#define se second
#define debug(x) cout << #x << ": " << x << '\n';
#define rng(a) a.begin(),a.end()
#define rrng(a) a.rbegin(),a.rend()

template<typename T1, typename T2> inline void chmin(T1& a, T2 b) { if (a > b) a = b; }
template<typename T1, typename T2> inline void chmax(T1& a, T2 b) { if (a < b) a = b; }
template<class T> void Print(vector<T> v) {
  F0R(i, v.size()) {
    cout << v[i] << ' ';
  }
  cout << newl;
}

#if 1


// INSERT ABOVE HERE
signed main() {
  cin.tie(0);
  ios_base::sync_with_stdio(false);

  bitset<101> bs(false);

  FOR(i, 1, 10) {
    FOR(j, i, 10) {
      bs[i * j] = true;
    }
  }

  int n;
  cin >> n;
  cout << (bs[n] ? "Yes" : "No");
}
#endif


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

int main(){
    string s;
    cin >> s;
    int n = s.size();
    int maxp = n/2;
    int p = 0;
    for(int i = 0; i < n; i++){
        if(s[i] == 'p'){p++;}
    }
    cout << maxp - p << endl;
    return 0;

}


Measured memory_bytes: 512
import qualified Data.Text as T
import qualified Data.Text.IO as T
import qualified Data.Text.Read as T
import Data.List (sort)

main :: IO ()
main = do
  (n : d : a : _) <- map unsafeTextToInt . T.words <$> T.getLine :: IO [Int]
  let
    walk :: Int -> Int -> [(Int, Int)] -> [(Int, Int)] -> [(Int, Int)]
    walk _ _ [] _
      = []
    walk 0 _ ((x, h) : xhs') yks
      = (x, k') : walk 1 k' xhs' yks
      where
        k' = (h + a - 1) `div` a
    walk l c xhs@((x, _) : _) ((y, k) : yks')
      | y + 2 * d < x = walk (pred l) (c - k) xhs yks'
    walk l c ((x, h) : xhs') yks
      = (x, k') : walk (succ l) (c + k') xhs' yks
      where
        k' = (max 0 (h - c * a) + a - 1) `div` a
  xhs <- sequence . replicate n $ unsafeListToTuple . map unsafeTextToInt . T.words <$> T.getLine :: IO [(Int, Int)]
  print . sum . map snd . fix . (walk 0 0) . sort $ xhs

fix :: (a -> a) -> a
fix f = x
  where
    x = f x

unsafeListToTuple :: [Int] -> (Int, Int)
unsafeListToTuple (x : y : _) = (x, y)

unsafeTextToInt :: T.Text -> Int
unsafeTextToInt s = case T.signed T.decimal s of
  Right (n, _) -> n


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

using namespace std;

int main() {
    while (true) {
        int n;
        cin >> n;
        if (n == 0) return 0;
        vector<int> color(n);
        for (int i = 0; i < n; ++i) {
            cin >> color[i];
        }
        vector<pair<int,int>> a;
        int now = 1;
        for (int i = 0; i < n - 1; ++i) {
            if (color[i] != color[i + 1]) {
                a.emplace_back(pair<int,int>(now, color[i]));
                now = 1;
            } else {
                ++now;
            }
        }
        a.emplace_back(pair<int,int>(now, color[n - 1]));
        int ans = 0;
        for (int i = 1; i < a.size() - 1; ++i) {
            int left = i - 1;
            int right = i + 1;
            int cnt = 0;
            if (a[left].second == a[right].second && a[left].first + a[right].first >= 3) {
                cnt += a[left].first + a[right].first + a[i].first;
                --left;
                ++right;
                while (left >= 0 || right < a.size()) {
                    if (a[left].first + a[right].first >= 4 && a[left].second == a[right].second) {
                        cnt += a[left].first + a[right].first;
                        --left;
                        ++right;
                    } else {
                        break;
                    }
                }
                ans = max(ans, cnt);
            }
        }
        cout << n - ans << '\n';
    }
}


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

int main(){
  int n,ans=1;
  cin >>n;
  int tmp=0;
  vector<int>a(n);
  for(int i=0;i<n;i++)
    cin >>a.at(i);
  for(int i=0;i<n;i++){
    if(a.at(tmp)==2){
      cout <<ans<<endl;
      return 0;
    }
    ans++;
    tmp=a.at(tmp)-1;
    if(i==n-1){
      cout <<-1<<endl;
      return 0;
    }
  }
}

Measured memory_bytes: 640
#include "bits/stdc++.h"
#define rep(i, j) for (int i = 0; i < j; i++)
using namespace std;
using ll = long long;

/*struct mint {
    ll x; // typedef long long ll;
    mint(ll x = 0) :x((x% mod + mod) % mod) {}
    mint operator-() const { return mint(-x); }
    mint& operator+=(const mint a) {
        if ((x += a.x) >= mod) x -= mod;
        return *this;
    }
    mint& operator-=(const mint a) {
        if ((x += mod - a.x) >= mod) x -= mod;
        return *this;
    }
    mint& operator*=(const mint a) { (x *= a.x) %= mod; return *this; }
    mint operator+(const mint a) const { return mint(*this) += a; }
    mint operator-(const mint a) const { return mint(*this) -= a; }
    mint operator*(const mint a) const { return mint(*this) *= a; }
    mint pow(ll t) const {
        if (!t) return 1;
        mint a = pow(t >> 1);
        a *= a;
        if (t & 1) a *= *this;
        return a;
    }

    // for prime mod
    mint inv() const { return pow(mod - 2); }
    mint& operator/=(const mint a) { return *this *= a.inv(); }
    mint operator/(const mint a) const { return mint(*this) /= a; }
};
istream& operator>>(istream & is, const mint & a) { return is >> a.x; }
ostream& operator<<(ostream & os, const mint & a) { return os << a.x; }*/

int main() {
    int n, m, c;
    cin >> n >> m >> c;
    vector<int> b(m);
    rep(i, m) cin >> b[i];
    vector<vector<int> > a(n, vector<int> (m));
    rep(i, n)rep(j, m) cin >> a[i][j];

    int ans = 0;

    rep(i, n) {
        int num = 0;
        rep(j, m) {
            num += a[i][j] * b[j];
        }
        num += c;
        if (num > 0)
            ans++;
    }

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


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

namespace ABC048A
{
    class Program
    {
        static void Main(string[] args)
        {
            var s = Console.ReadLine().Split().ToArray();

            Console.WriteLine($"A{s[1][0]}C");
        }
    }
}


Measured memory_bytes: 13268
#include <bits/stdc++.h>
#define FAST  ios_base::sync_with_stdio(false);cin.tie(NULL);
using namespace std;
typedef long long ll;
void solve()
{
    ll n;
    cin>>n;
    ll ans=n%1000;
    if(ans==0)
        cout<<0<<endl;
    else
        cout<<1000-ans<<endl;




}

int main()
{
//cout<<1900/1000<<endl;


    //#ifndef oj
    //freopen("in", "r", stdin);
    //freopen("out.txt","w",stdout);
    //#endif
    //system("cls");
    //getchar();
    ll t=1;
    //cin>>t;
    while(t--)
    {
        solve();
    }

}


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

int main() {
  long int N,A,B,ans;
  cin >> N >> A >> B;
  
  if(!A){
    cout << 0 << endl;
    return 0;
  }
  ans=N/(A+B);
  ans*=A;
  if((N%(A+B))/A) ans+=A;
  else ans+=(N%(A+B));
  
  cout << ans << endl;
  
  return 0;
}


Measured memory_bytes: 256
from collections import defaultdict

def main():
    _ = int(input())

    d = defaultdict(lambda: 0)
    for a in [int(i) for i in input().split()]:
        d[a-1] += 1
        d[a] += 1
        d[a+1] += 1
    print(sorted(d.items(), key=lambda x: x[1], reverse=True)[0][1])
        

if __name__ == "__main__":
    main()

Measured memory_bytes: 23472
# include "iostream"
# include "cstdio"

using namespace std;

const int maxm=1e5+10;

int N,M;
long long DP[maxm],W[maxm],V[maxm];

int main(){
	register int i,j;
	scanf("%d%d",&N,&M);
	for(i=1;i<=N;i++){
		scanf("%lld%lld",W+i,V+i);
	}
	for(i=1;i<=N;i++){
		for(j=M;j>=W[i];j--){
			DP[j]=max(DP[j],DP[j-W[i]]+V[i]);
		}
	}
	printf("%lld",DP[M]);
	return 0;
}

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

int main (){
  int n;
  int counter = 0;
  cin >> n;
  string a, b, c;
  cin >> a >> b >> c;
  for (int i = 0; i < n; i++){
    counter += max((a.at(i)!=b.at(i))+(b.at(i)!=c.at(i))+(c.at(i)!=a.at(i))-1,0);
  }
  cout << counter << endl;
  return 0;
}
  

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

public class Main {
	public static void main(String[] args) {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		try {
			String line;
			/* input */
			line = br.readLine();

			int n = Integer.parseInt(line);
			if(n==0) return;

			for(int k=0;k<n;k++){
				String ex[] = br.readLine().split(" ");
				String sum ="";
				int m=0,c=0,x=0,i=0;
				for(int j=0;j<=1;j++){
					int ii = ex[j].indexOf("i");
					if(ii>-1){
						if(ii==0){
							i += 1;
						} else {
							if(Character.isDigit(ex[j].charAt(ii-1))){
								i += Integer.parseInt(ex[j].substring(ii-1,ii));
							} else {
								i += 1;
							}
						}
					}
					if(i>=10){
						x += 1;
						i -= 10;
					}
					int xi = ex[j].indexOf("x");
					if(xi>-1){
						if(xi==0){
							x += 1;
							if(x>=10){
								c += 1;
								x -= 10;
							}
						} else {
							if(Character.isDigit(ex[j].charAt(xi-1))){
								x += Integer.parseInt(ex[j].substring(xi-1,xi));
							} else {
								x += 1;
							}
						}
					}
					if(x>=10){
						c += 1;
						x -= 10;
					}
					int ci = ex[j].indexOf("c");
					if(ci>-1){
						if(ci==0){
							c += 1;
						} else {
							if(Character.isDigit(ex[j].charAt(ci-1))){
								c += Integer.parseInt(ex[j].substring(ci-1,ci));
							} else {
								c += 1;
							}
						}
					}
					if(c>=10){
						m += 1;
						c -= 10;
					}
					int mi = ex[j].indexOf("m");
					if(mi>-1){
						if(mi==0){
							m += 1;
						} else {
							if(Character.isDigit(ex[j].charAt(mi-1))){
								m += Integer.parseInt(ex[j].substring(mi-1,mi));
							} else {
								m += 1;
							}
						}
					}
				}
				String ms = ((m==0)?"":(m==1)?"m":(m+"m"));
				String cs = ((c==0)?"":(c==1)?"c":(c+"c"));
				String xs = ((x==0)?"":(x==1)?"x":(x+"x"));
				String is = ((i==0)?"":(i==1)?"i":(i+"i"));
				sum = ms + cs + xs + is;
				System.out.println(sum);
			}
		} catch (IOException e) {
			e.printStackTrace();
		}
	}
}

Measured memory_bytes: 26432
my $tmp = <STDIN>;

chomp($tmp);

my ($n, $k) = split / /, $tmp;

my $ans = 0;
for(1..$n)
{
    my ($a, $c, $i) = (1/$n, 0, $_);

    while($i < $k)
    {
	$i= $i * 2;
	$c = $c + 1;
    }
    for(1..$c)
    {
	$a = $a * 1 / 2;
    }
    $ans = $ans + $a;
}

print "$ans\n";


Measured memory_bytes: 640
{-# LANGUAGE BangPatterns #-}
import Control.Applicative((<$>))
import Control.Monad
import Data.Map ((!))
import qualified Data.Map as M
import qualified Data.List as L
import Data.Maybe (catMaybes)
-- import qualified Data.Char as C
-- import qualified Data.IntSet as I
import Debug.Trace
-- import Text.Regex.Posix ((=~))
--------------------------------------------
readInt    = read :: String -> Int
getInt     = readInt <$> getLine
getIntList = map readInt . words <$> getLine
int2bin 0 =  []
int2bin n =  n `mod` 2 : int2bin (n `div` 2)
----------------------------------------------

data Recode = Recode {
                m :: Int,
                a :: Int,
                r :: Int,
                c :: Int,
                h :: Int } deriving Show

counter rr [] = rr
counter rr@(Recode m a r c h) (s:ss)
  | head s == 'M' = counter (Recode (m+1) a r c h) ss
  | head s == 'A' = counter (Recode m (a+1) r c h) ss
  | head s == 'R' = counter (Recode m a (r+1) c h) ss
  | head s == 'C' = counter (Recode m a r (c+1) h) ss
  | head s == 'H' = counter (Recode m a r c (h+1)) ss
  | otherwise = counter rr ss

main :: IO ()
main = do
  n <- getInt
  ss <- replicateM n getLine
  let Recode m a r c h = counter (Recode 0 0 0 0 0) ss
  print $ m*a*r + m*r*c + m*c*h + m*a*c + m*a*h + m*r*h + a*r*c + a*r*h + a*c*h + r*c*h


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

int main() {
  string s;
  cin >> s;
  string a = "";
  a += s[0];
  a += s[1];
  string b = "";
  b += s[2];
  b += s[3];

  int c = stoi(a);
  int d = stoi(b);

  if (c >= 1 && c <= 12) {
    if (d >= 1 && d <= 12) {
      cout << "AMBIGUOUS" << endl;
    } else {
      cout << "MMYY" << endl;
    }
  } else if (d >= 1 && d <= 12) {
    if (c >= 1 && c <= 12) {
      cout << "AMBIGUOUS" << endl;
    } else {
      cout << "YYMM" << endl;
    }
  } else {
    cout << "NA" << endl;
  }
}

Measured memory_bytes: 256
package main

import (
  "fmt"
)

func main() {
	var a, b, c int
	fmt.Scan(&a, &b, &c)

	if a == b && b == c {
		fmt.Println("No")
		return
	} else if (a == b) || (b == c) || (a == c) {
		fmt.Println("Yes")
		return
	}
	fmt.Println("No")
}

Measured memory_bytes: 512
h, w, k = map(int, input().split())
s = [list(map(int, list(input()))) for _ in range(h)]
result = []
if h*w<=k:
    result.append(0)
else:
    for i in range(2**(h-1)):
        checker, num = 0, i
        while num > 0:
            checker += num%2
            num >>= 1
        x = 0
        c = [0 for _ in range(checker+1)]

        for j in range(w):
            num = i
            p = 0
            nex = [0 for _ in range(checker+1)]
            for m in range(h):
                nex[p] += s[m][j]
                p += num%2
                num = num >> 1          
            if any(nex[m]>k for m in range(checker+1)):
                x = 10**5
                break

            if all(nex[m]+c[m] <= k for m in range(checker+1)):
                c = [c[I]+nex[I] for I in range(checker+1)]
            else:
                x += 1
                c = nex
        result.append(checker+x)
print(min(result))


Measured memory_bytes: 54104
#include <stdio.h>

int n, A[50];

// 入力値のMから選んだ要素を引いていく再帰関数
int solve(int i, int m) {
    if(m==0) return 1;
    if(i>=n) return 0;
    int res = solve(i+1,m) || solve(i+1,m-A[i]);
    return res;
}

int main(void) {
    int q, M, i;

    scanf("%d", &n);
    for(i=0;i<n;i++) scanf("%d",&A[i]);
    scanf("%d",&q);
    for(i=0;i<q;i++) {
        scanf("%d", &M);
        if(solve(0,M)) printf("yes\n");
        else printf("no\n");
    }
    return 0;
}


Measured memory_bytes: 2128
#include <iostream>

using namespace std;

void attack(int S,int W){
    if(W>S){
        cout << "unsafe";
    }else if (W==S){
        cout << "unsafe";
    }else{
        cout << "safe";
    }


}
int main()
{
    int S,W;
    cin >> S;
    cin >> W;
    attack (S,W);
    return 0;
}


Measured memory_bytes: 3632
# pragma GCC optimize("Ofast")
# pragma GCC optimization ("unroll-loops")
#include<bits/stdc++.h>

#define for0(i,n) for(ll i = 0;i < (n);i++)
#define for1(i,n) for(ll i = 1;i<=(n);i++)
#define for2(i,n) for(ll i = 2;i<=(n);i++)
#define fastio cin.tie(0);cout.tie(0);ios::sync_with_stdio(0)
#define rep(i,st,en,cnt) for(ll i = st;i <= en;i+=cnt)
#define PB push_back
#define MP make_pair
#define F first
#define S second
#define bit(x,n) (x & (1<<(n)))
#define EPS 1e-8
#define all(x) (x).begin(),(x).end()
#define INF 0x3f3f3f3f3f3f3f
#define NEGINF -INF
#define TYPEMAX(type)   std::numeric_limits<type>::max()
#define inp_arr(a,n) for0(i,n) {cin>>a[i];}
#define out_arr(a,n) for0(i,n) {cout<<a[i]<<" ";}

using namespace std;

typedef pair<int,int> ii;
typedef pair<long long,long long> pll;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<vi> vvi;
typedef long long ll;
typedef vector<long long> vl;
typedef vector<vector<ll> > vvl;
typedef vector<pair<long long, long long> > vll;

ii DR8[] = {{-1,0},{0,1},{1,0},{0,-1},{-1,1},{-1,-1},{1,1},{1,-1}};
ii DR4[] = {{-1,0},{0,-1},{0,1},{1,0}};

const ll mod = 998244353;
/*
ll nop = 70;
vi primes(nop+1,1);

void sieve(){
    primes[1] = primes[0] = 0;
    for(ll i = 2;i * i <= nop;i++){
        if(primes[i]){
            for(ll j = i*i; j <= nop;j+=i){
                primes[j] = 0;
            }
        }
    }
}

ll gcd(ll a,ll b){
    if(b>a) swap(b,a);
    if(b==0) return a;
    return gcd(b,a%b);
}

void extgcd(ll a,ll b,ll& x,ll& y){  //a smaller b larger
    if(a==0) {
        x = a;y = b;
        return;
    }
    extgcd(b%a,a,x,y);
    ll y1 = y,x1 = x;
    x = y1 - (b/a)*x1;
    y = x1;
}

ll lcm(ll a,ll b){
    return (a*b)/gcd(a,b);
}

ll bexp(ll num,ll e){
    ll ans = 1;
    while(e>0){
        if(e&1){
            ans *= num;
        }
        num *= num;
        e>>= 1;
    }
    return ans;
}
*/
ll mexp(ll num,ll e){
    ll ans = 1;
    while(e>0){
        if(e&1){
            ans = (ans *num)%mod;
        }
        num *= num;
        num %= mod;
        e>>=1;
    }
    return ans%mod;
}

ll modinv(ll a){
    a %= mod;
    return mexp(a,mod-2);
}

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


int main() {
    fastio;
    #ifndef ONLINE_JUDGE
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    #endif
    int t = 1;
    //cin>>t;
    for1(T,t){
        //cout<<fixed<<setprecision(8);
        //cout<<"Case #"<<T<<": ";
        solve();
    }
    /* #ifndef ONLINE_JUDGE
    cout<<"\nTime Elapsed: " << 1.0*clock() / CLOCKS_PER_SEC << " sec\n";
    #endif */
    return 0;
}


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

typedef unsigned long long ull;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<double, double> pdd;
const ull mod = 1e9 + 7;
#define REP(i,n) for(int i=0;i<(int)n;++i)

//debug
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;

template<class S, class T> ostream& operator << (ostream& os, const pair<S, T> v){
  os << "(" << v.first << ", " << v.second << ")"; return os;
}
template<class T> ostream& operator << (ostream& os, const vector<T> v){
  for(int i = 0; i < v.size(); i++){if(i > 0){os << " ";} os << v[i];} return os;
}
template<class T> ostream& operator << (ostream& os, const vector<vector<T>> v){
  for(int i = 0; i < v.size(); i++){if(i > 0){os << endl;} os << v[i];} return os;
}

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

    ll N;
    cin >> N;

    ll K = (N+1)/2;

    double res = (1.0*K)/(1.0*N);
    printf("%.10f\n", res);
    return 0;
}

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

class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String line;
        char[][] map = { { 'a', 'f', 'k', 'p', 'u', 'z' }, { 'b', 'g', 'l', 'q', 'v', '.' },
                { 'c', 'h', 'm', 'r', 'w', '?' }, { 'd', 'i', 'n', 's', 'x', '!' }, { 'e', 'j', 'o', 't', 'y', ' ' } };
        while ((line = br.readLine()) != null) {

            if (line.length() % 2 == 1) {
                System.out.println("NA");
                continue;
            }

            String result = "";
            while (line.length() > 1) {
                int w = (int) (line.charAt(0) - '0');
                int h = (int) (line.charAt(1) - '0');
                try {
                    result += map[h - 1][w - 1];
                } catch (ArrayIndexOutOfBoundsException e) {
                    result = "NA";
                    break;
                }
                line = line.substring(2);
            }

            System.out.println(result);
        }
    }
}


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

int island[12][12];

void drow(int x, int y);
	

int main()
{
	int sima = 0;
	string str;

	while(1)
	{
		for(int i = 0; i < 12; i++)
		{
			cin >> str;
			for(int j = 0; j < 12; j++)
			{
				if(str[j] == '1')
				{
					island[i][j] = 1;
				}
			
				else
				{
					island[i][j] = 0;
				}
			}
		}
		if (cin.eof()) 
		{
			break;
		}
		
	
		for(int i = 0; i < 12; i++)
		{
			for(int j = 0; j < 12; j++)
			{
				if(island[i][j] == 1)
				{
					sima = sima + 1;
					
					drow(i , j);
					
				}	
			}
		}
		
		cout << sima << endl;
		sima = 0;
	}
	
	return 0;
}

void drow(int x, int y)
{
	island[x][y] = 0;
	
	if(island[x - 1][y] == 1 && x - 1 >= 0)
	{
		drow((x - 1), y);
	}
	
	if(island[x + 1][y] == 1 && x + 1 <= 11)
	{
		drow((x + 1), y);
	}
	
	if(island[x][y - 1] == 1 && y - 1 >= 0)
	{
		drow( x, (y - 1));
	}
	
	if(island[x][y + 1] == 1 && y + 1 <=11)
	{
		drow( x, (y + 1));
	}
}

Measured memory_bytes: 1184
class UnionFind:
    """
    size の要素数の UnionFind を管理する
    data 中の負数の要素が根となる
    """

    def __init__(self, size):
        # 根は子を含む集合のデータ数を負数でもつ
        self.data = [-1] * size

    def merge(self, x, y):
        x = self.root(x)
        y = self.root(y)
        if x == y: return False

        # y の方がデータ数を多く
        if self.data[x] < self.data[y]:
            x, y = y, x

        # y に x をつなげる
        self.data[y] += self.data[x]
        self.data[x] = y
        return True

    def root(self, x):
        if self.data[x] < 0:
            return x
        self.data[x] = self.root(self.data[x])
        return self.data[x]

    def size(self, x):
        """
        根は負数でデータ数を管理しているのでそれを返す
        """
        return -self.data[self.root(x)]


N, M, K = [int(_) for _ in input().split()]
NG = [0] * (N + 1)
uf = UnionFind(N + 1)
for i in range(M):
    a, b = [int(_) for _ in input().split()]
    uf.merge(a, b)
    NG[a] += 1
    NG[b] += 1

# KG = [[] for _ in range(N + 1)]
for i in range(K):
    a, b = [int(_) for _ in input().split()]
    if uf.root(a) == uf.root(b):
        NG[a] += 1
        NG[b] += 1

res = [0] * (N)
for i in range(1, N + 1):
    cnt = uf.size(i) - NG[i] - 1
    res[i-1]=cnt
print(*res)


Measured memory_bytes: 15508
S = input()

length = len(S)
ans = 0

for x in range(2 ** (length - 1)):
    res = ""
    b = str(format(x, '010b'))
    for i in range(length):
        res += str(S[i])
        if b[-(i + 1)] == "1":
            res += "+"
        else:
            pass
    ans += eval(res)
        
print(ans)

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

int main() {
  
  string N;
  
  cin >> N;
  
  if(N.at(0)==N.at(1) && N.at(0)==N.at(2) && N.at(0)==N.at(3)) {
    
    cout << "Yes" << endl;
    
  } else if(N.at(0)==N.at(1) && N.at(0)==N.at(2)) {

    cout << "Yes" << endl;
    
  } else if(N.at(1)==N.at(2) && N.at(1)==N.at(3)) {
    
    cout << "Yes" << endl;
    
  } else {
    
    cout << "No" << endl;
    
  }
  
  return 0;
  
}

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

using namespace std;

long long int a, b, n, m, x, y;

int main()
{
    cin>>n>>a>>b;
    x = max(a, b); y = min(a, b);
    m = x - y;
    if(m % 2 == 0) cout<<m / 2;
    else cout<<(min(x - 1, n - y) + min(n - x, y) + 1) / 2;
    return 0;
}

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

#define int long long

int func(int n){
    int ans = 0;
    while(n>0){
        n/=10;
        ans++;
    }
    return ans;
}

signed main() {
    
    int N;
    cin >> N;
 
    int ans = 0;
    for(int i=1; i<=N; i++){
        if(func(i)%2==1) ans++;
    }
    cout << ans << endl;
    
    return 0;
}


Measured memory_bytes: 256
#define _CRT_SECURE_NO_WARNINGS
#define _SCL_SECURE_NO_WARNINGS
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <string>
#include <vector>
#include <list>
#include <utility>
#include <algorithm>
#include <functional>
#include <cmath>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <iomanip>
#include <sstream>
#include <bitset>
#include <limits>
#include <numeric>
#include <valarray>
#include <fstream>

using namespace std;
typedef unsigned int uint;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<LL, LL> PP;
#define REP(i,a,n) for(LL i = (a); i < (LL)(n); ++i)
#define REM(i,a,n) for(LL i = ((n) - 1); i >= (a); --i)
#define FLOAT fixed << setprecision(16)
#define SPEEDUP {cin.tie(0); ios::sync_with_stdio(false);}
const int INF = 0x3FFFFFFF;
const LL INFLL = 0x3FFFFFFF3FFFFFFF;
const double INFD = 1.0e+308;
const string INFSTR = "\x7f";
const double EPS = 1.0e-9;

void YesNo(bool b) { cout << (b ? "Yes" : "No") << endl; }
void YESNO(bool b) { cout << (b ? "YES" : "NO") << endl; }
template <class T, class U>
istream& operator>>(istream& ist, pair<T, U>& right) { return ist >> right.first >> right.second; }
template <class T, class U>
ostream& operator<<(ostream& ost, const pair<T, U>& right) { return ost << right.first << ' ' << right.second; }
template <class T, class TCompatible, size_t N>
void Fill(T(&dest)[N], const TCompatible& val) { fill(dest, dest + N, val); }
template <class T, class TCompatible, size_t M, size_t N>
void Fill(T(&dest)[M][N], const TCompatible& val) { for (int i = 0; i < M; ++i) Fill(dest[i], val); }
template<class T>
T Compare(T left, T right) { return left > right ? 1 : (left < right ? -1 : 0); }
istream& Ignore(istream& ist) { string s; ist >> s; return ist; }
bool Inside(int i, int j, int h, int w) { return i >= 0 && i < h && j >= 0 && j < w; }
// all_of
// partial_sum, adjacent_difference

#ifdef ONLY_MY_ENVIR
#include "IntMod.h"
#include "Union_Find.h"
#include "Graph.h"
#include "Range.h"
#include "Global.h"
#include "Flow_Solver.h"
#include "Tree.h"
#include "Suffix_Array.h"
#include "Geometry.h"
#include "Matrix.h"
#endif

#ifdef __GNUC__
typedef __int128 LLL;
istream& operator>> (istream& ist, __int128& val) { LL tmp;  ist >> tmp; val = tmp; return ist; }
ostream& operator<< (ostream& ost, __int128 val) { LL tmp = val; ost << tmp; return ost; }
#endif

#if 1234567891
#include <array>
#include <random>
#include <unordered_set>
#include <unordered_map>
template<typename T>
using PriorityQ = priority_queue<T, vector<T>, greater<T> >;	// コスト小を優先
#endif



int main() {
	int a, b, c, d;
	cin >> a >> b >> c >> d;
	int cnt = 0;
	REP(i, 0, a + 1) {
		REP(j, 0, b + 1) {
			REP(k, 0, c + 1) {
				if (i * 500 + j * 100 + k * 50 == d)++cnt;
			}
		}
	}
	cout << cnt << endl;
	return 0;
}

Measured memory_bytes: 256
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

n,k = map(int,readline().split())
if k == 1:
  print(0)
  exit()
  
a = [0]+[int(i) for i in readline().split()]
for i in range(1,n+1):
  a[i] = a[i-1]+a[i]
  
a = [(ai-i)%k for i,ai in enumerate(a)]
#print(a)
from collections import Counter,deque
c = Counter({a[0]:1})
d = deque([a[0]])
ans = 0
cnt = 1
for j,aj in enumerate(a[1:]):
  ans += c[aj]
  d.append(aj)
  c.update({aj:1})
  cnt += 1
  if cnt >= k:
    p = d.popleft()
    c.update({p:-1})
  
print(ans)


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

const int maxn=1e5+10;

int n,L,T,x[maxn],y[maxn];
bool w[maxn];

int main()
{
#ifdef h10
	freopen("C.in","r",stdin);
	freopen("C.out","w",stdout);
#endif
	int i,tmp;
	scanf("%d%d%d",&n,&L,&T);
	for (i=1;i<=n;i++)
		scanf("%d%d",&x[i],&tmp),w[i]=tmp==1;
	for (i=1;i<=n;i++)
		y[i]=w[i]?(x[i]+T)%L:((x[i]-T)%L+L)%L;
	int id=1;
	for (i=2;i<=n;i++)
		if (w[i]!=w[1])
		{
			int d0=w[1]?(x[i]-x[1]+L)%L:(x[1]-x[i]+L)%L;
			if (2*T<d0) continue;
			if (w[1]) id+=1+(2*T-d0)/L;
			else id-=1+(2*T-d0)/L;
			id=((id-1)%n+n)%n+1;
		}
	int pos1=y[1];
	sort(y+1,y+n+1);
	for (i=1;i<=n;i++)
		if (y[i]==pos1) break;
	if (y[i]==y[i+1]&&w[1]) i++;
	tmp=((i-id)%n+n)%n+1;
	for (i=tmp;i<=n;i++)
		printf("%d\n",y[i]);
	for (i=1;i<tmp;i++)
		printf("%d\n",y[i]);
}


Measured memory_bytes: 2048
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <set>
#include <cmath>
#include <stdio.h>
#include <list>
#include <numeric>
#include <stack>
#include <queue>
#include <tuple>
#include <bitset>
#include <map>
#include <math.h>
//　ceil(a/b)   (a + (b - 1))/ b
using namespace std;
#define rep(i,n) for(int i = 0; i < (n); i++)
typedef long long ll;
typedef pair<int,int> P;
const int inf=1000000007;
const ll mod=1000000007;
const double PI=3.14159265358979323846;
int dx[] = {1,-1,0,0};
int dy[] = {0,0,1,-1};

ll gcd(ll a, ll b){
  if (b==0) return a;
  else return gcd(b,a%b);
}

int cans(bool f){
  if(f) cout << "Yes" << endl;
  else cout << "No" << endl;
  return 0;
}



ll comb(ll num){
  return num*(num-1)/2;
}


ll idx[1000000];
ll cnt[1000000];

int main(){
  int N;
  ll ans = 0;
  ll M = 0;
  cin >> N;
  rep(i,N){
    cin >> idx[i];
    cnt[idx[i]]++;
    M = max(M,idx[i]);
  }
  for(int i = 1; i <=M; i++){
    if(!cnt[i]) continue;
    ans += comb(cnt[i]);
  }






  rep(i,N){
    cout << ans - comb(cnt[idx[i]])  + comb(cnt[idx[i]]-1) << endl;
  }
  return 0;
}



Measured memory_bytes: 7296