akhauriyash/Code-Regression huggingface dataset:
using System;
using System.Collections.Generic;
using System.Linq;

class Program
{
    static void Main()
    {
        string[] s = Console.ReadLine().Split().ToArray();
        int n = int.Parse(s[0]);
        int k = int.Parse(s[1]);
        List<int> h = new List<int>();
        for (int i = 0; i < n; i++)
            h.Add(int.Parse(Console.ReadLine()));
        h.Sort();

        List<int> gap = new List<int>();
        for (int i = 0; i < n - k + 1; i++)
        {
            gap.Add(h[i + k - 1] - h[i]);
        }

        Console.WriteLine(gap.Min());
    }
}

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

const int MOD=1000000007;
const int INF=0x3f3f3f3f;
const ll INFL=0x3f3f3f3f3f3f3f3f;

int main(){
	int n;string s;cin>>n>>s;
	int cnt=0;
	rep(i,s.size()-2){
		if(s[i]=='A'&&s[i+1]=='B'&&s[i+2]=='C')cnt++;
	}
	cout<<cnt<<endl;
}

Measured memory_bytes: 256
class UnionFind:
    def __init__(self, n):
        self.v = [-1 for _ in range(n)]  # 根(負): 連結頂点数 * (-1) / 子(正): 根の頂点番号(0-indexed)
        self.bk = [1 if s[r][c] == '#' else 0 for r in range(H) for c in range(W)]
        self.wt = [1 if s[r][c] == '.' else 0 for r in range(H) for c in range(W)]

    def find(self, x):  # xを含む木における根の頂点番号を返す
        if self.v[x] < 0:  # (負)は根
            return x
        else:  # 根の頂点番号
            self.v[x] = self.find(self.v[x])  # uniteでは, 旧根に属する頂点の根が旧根のままなので更新
            return self.v[x]

    def unite(self, x, y):  # 違う根に属していたらrankが低くなるように連結
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if -self.v[x] < -self.v[y]:  # size比較, 　(-1) * (連結頂点数 * (-1)), (正)同士の大小比較
            x, y = y, x  # 連結頂点数が少ない方をyにすると, findでの更新回数が減る？
        self.v[x] += self.v[y]  # 連結頂点数の和を取る, 連結頂点数 * (-1)
        self.v[y] = x  # 連結頂点数が少ないy(引数yの根の頂点番号)の根をx(引数xの根の頂点番号)にする

        self.bk[x % (H * W)] += self.bk[y % (H * W)]
        self.wt[x % (H * W)] += self.wt[y % (H * W)]

    def root(self, x):
        return self.v[x] < 0  # (負)は根

    def same(self, x, y):
        return self.find(x) == self.find(y)  # 同じ根に属するか

    def size(self, x):
        return -self.v[self.find(x)]  # 連結頂点数を返す

    def calc(self, x):
        return self.bk[x % (H * W)] * self.wt[x % (H * W)]

dr = [0, 0, 1, -1]
dc = [1, -1, 0, 0]

H, W = map(int, input().split())
s = [input() for _ in range(H)]
uf = UnionFind(2 * H * W)  # 全頂点 * 2
for r in range(H):
    for c in range(W):
        if s[r][c] == '#':
            for i in range(4):
                nr = r + dr[i]
                nc = c + dc[i]
                if 0 <= nr < H and 0 <= nc < W:
                    if s[nr][nc] == '.':
                        uf.unite(r * W + c, H * W + (nr * W + nc))  # #: *1, .: * 2
        else:
            for i in range(4):
                nr = r + dr[i]
                nc = c + dc[i]
                if 0 <= nr < H and 0 <= nc < W:
                    if s[nr][nc] == '#':
                        uf.unite(H * W + (r * W + c), nr * W + nc)  # #: *1, .: * 2

ans = 0
for r in range(H):
    for c in range(W):
        if uf.root(r * W + c):
            # print(r, c, '#')
            sz = uf.size(r * W + c)
            # print(' ', r * W + c, sz, '#')
            if sz > 1:
                ans += uf.calc(r * W + c)

        if uf.root(H * W + (r * W + c)):
            # print(r, c, '.')
            sz = uf.size(H * W + (r * W + c))
            # print(' ', r * W + c, sz, '.')
            if sz > 1:
                ans += uf.calc(H * W + (r * W + c))

print(ans)
# print(uf.v)


Measured memory_bytes: 9108
K, S = map(int, input().split())
c = 0
for x in range(K + 1):
    for y in range(x + 1):
        if x + y > S:
            break
        z = S - x - y
        if z >= 0 and z < y + 1:
            if x != y and x!= z and y!= z:
                c += 6
            elif x == y and x == z and y == z:
                c += 1
            else:
                c += 3
print(c)


Measured memory_bytes: 41820
#include <bits/stdc++.h>
using namespace std;
 
int main() {
    int a,b;
    cin >> a>>b;
    if(a+b>=a-b&&a+b>=a*b){
        cout << a+b << endl;
    }
    else if(a-b>=a+b&&a-b>=a*b){
        cout << a-b << endl;
    }
    else{cout << a*b << endl;}

}

Measured memory_bytes: 256
# Break Number
import sys

N = int(input())

cnt = [0 for x in range(N)]
a = [int(_ + 1) for _ in range(N)]

for i in range(N) :
    while True :
        if a[i] % 2 == 0 :
            a[i] = a[i] // 2
            cnt[i] += 1
        else :
            break

print(cnt.index(max(cnt)) + 1)

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

using namespace std;

#define rep(i, n) for (int i = 0; i < (int)n; ++i)
#define REP(i, a, b) for (int i = (int)a; i < (int)b; ++i)
#define each(i,c) for(__typeof((c).begin()) i = (c).begin(); i != (c).end(); ++i)
#define all(v) v.begin(), v.end()
#define mset(a, n) memset(a, n, sizeof(a))

typedef long long ll;

const int INF = 1000000000;
const int MOD = 1000000007;

int main(int argc, char const *argv[])
{
	int H, W; cin >> H >> W;
	vector<string> S(H);
	vector<bool> flg_h(H, false), flg_w(W, false);
	rep(i, H) {
		cin >> S[i];
		rep(j, W) if (S[i][j] == '#') flg_h[i] = true, flg_w[j] = true;
	}

	rep(i, H) {
		if (flg_h[i]) {
			rep(j, W) {
				if (flg_w[j]) cout << S[i][j];
			}
		cout << endl;
		}
	}
	return 0;
}

Measured memory_bytes: 256
package main

import "fmt"

func check(s string) bool {
	var l int32 = 0
	h := map[rune]int32{}
	for _, c := range s {
		if _, ok := h[c]; ok == true {
			h[c]++
			l = h[c]
		} else {
			h[c] = 1
		}
	}
	if len(h) != 2 {
		return false
	}
	for _, v := range h {
		if v != l {
			return false
		}
	}
	return true
}

func main() {
	var s string
	fmt.Scan(&s)
	if check(s) {
		fmt.Println("Yes")
	} else {
		fmt.Println("No")
	}
}


Measured memory_bytes: 512
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<cstdlib>
#include <cmath>
#include<stdio.h>
#include<queue>
#include<stack>
#include<set>
#define MAX 1000000000000000000LL
long long inf=1000000007;
using namespace std;
int main(){
    int a,b,c,d;
    cin>>a>>b>>c>>d;
    if(c>=b||a>=d){
      cout<<0<<endl;
        return 0;
    }
    int ans=0;
    for(int i=0; i<=100;i++){
        if(a<=i&&b>=i&&c<=i&&d>=i){
            ans++;
        }
    }
    cout<<ans-1<<endl;
    return 0;
}


Measured memory_bytes: 256
n = int(input())
xy = [[]for i in range(n)]
for i in range(n):
    ai = int(input())
    for j in range(ai):
        x,y = list(map(int,input().split()))
        xy[i].append([x-1,y])
ma = 0
for bit in range(2**n):
    bo = True
    for i in range(n):
        if bit >> i & 1:
            for x,y in xy[i]:
                if bit >> x & 1 != y:
                    bo = False
                    break
        if not bo:
            break
    if bo:
        count = bin(bit)[2:].count('1')
        ma = max(ma,count)
print(ma)

Measured memory_bytes: 3064
N = int(input())
zorome = [0,111,222,333,444,555,666,777,888,999]
diff = [0]*10
for i in range(len(zorome)):
    if zorome[i] == N:
        print(zorome[i])
        break
    elif zorome[i] > N:
        print(zorome[i])
        break


Measured memory_bytes: 2940
#include <bits/stdc++.h>
#include <iostream>
//#include <algorithm>
// #include <iomanip>
#define ll long long
#define map unordered_map
#define set unordered_set

using namespace std;

const ll MOD = 1000000007;

int main() {
  ll n;
  scanf("%lld", &n);

  string s;
  cin >> s;

  ll r = 0;
  ll c = 0;
  for (;;) {
    int i = s.find("ABC", c);
    if (i < 0) {
      break;
    } else {
      r += 1;
    }
    c = i + 2;
  }
  cout << r << endl;
}


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

//型定義
typedef long long ll;

//定数
const int INF=1e+9;
const int MOD=1e+9+7;

//REPマクロ
#define REP(i,n) for(ll i=0;i<(ll)(n);i++)
#define REPD(i,n) for(ll i=n-1;i>=0;i--)
#define REP2(i,a,b) for(ll i=a;i<(ll)(b);i++)
#define REPD2(i,a,b) for(ll i=a;i>(ll)(b);i--)

// 多次元 vector 生成
template<class T>
vector<T> make_vec(size_t a){
    return vector<T>(a);
}
template<class T, class... Ts>
auto make_vec(size_t a, Ts... ts){
  return vector<decltype(make_vec<T>(ts...))>(a, make_vec<T>(ts...));
}

//vectorの扱い
#define ALL(x) (x).begin(),(x).end() //sortなどの引数省略
#define SIZE(x) ((ll)(x).size()) //size
#define MAX(x) *max_element(ALL(x)) //最大値
#define MIN(x) *min_element(ALL(x)) //最小値

// xのn乗%modを計算
ll mod_pow(ll x, ll n, ll mod){
    ll res = 1;
    while(n > 0){
        if(n & 1) res = res*x%mod;
        x = x*x%mod;
        n >>= 1;
    }
    return res;
}

int main(){
    ll K;
    cin>>K;
    ll ans=1;
    ll num=7;

    if(K%2==0||K%5==0){
        ans=-1;
    }else{
        ans=1;
        num=7;
        while(num%K!=0){
            num+=7*mod_pow(10,ans,K);
            num%=K;
            ans++;
        }
    }
    
    cout<<ans<<endl;
}

Measured memory_bytes: 3672
#include <bits/stdc++.h>
#define all(a) (a).begin(), (a).end()
#define REP(i, n) for(int (i)=0; (i)<(n); (i)++)
#define RREP(i, n) for(int (i)=(n)-1, (i)>=0; (i)--)
#define ios() cin.tie(0), ios::sync_with_stdio(false)
typedef long long ll;
typedef unsigned long long ull;
ll const MOD = 1e9+7;
ll const INF = 1e18;
using namespace std;

int main(){
    int n, m;
    cin >> n >> m;
    ll ans1 = 0, ans2 = 0, sum = 0;
    REP(i, n){
        ll x;
        cin >> x;
        ans1 = (ans1 + x*i%MOD - sum + MOD) % MOD;
        sum = (sum + x)%MOD;
    }
    sum = 0;
    REP(i, m){
        ll x;
        cin >> x;
        ans2 = (ans2 + x*i%MOD - sum + MOD) % MOD;
        sum = (sum + x)%MOD;
    }
    cout << ans1 * ans2 % MOD << endl;
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define int long long
#define PB push_back
#define MP make_pair
#define FI first
#define SE second
using namespace std;
static const int INF = 1ll<<60;
static const int MAX_N = 100000;
typedef pair<int,int> pii;

int N;
int A[MAX_N];
int V[MAX_N];
int ans=0;

int binary(int l,int r,int res){
    int mid=(l+r)/2;
    for(int i=0;i<20;++i){
        mid=(l+r)/2;
        if(V[mid]>res)r=mid;
        else l=mid;
    }
    return l;
}

signed main(){
    cin>>N;
    for(int i=0;i<N;++i){
        cin>>A[i];
    }
    for(int i=0;i<N;++i){
        if(i==0)V[i]=A[i];
        else V[i]=V[i-1]+A[i];
    }
    for(int i=N;i<2*N;++i)V[i]=V[i-1]+A[i-N];
    int mid = V[N-1]/3;
    for(int i=0;i<N;++i){
        int r = i+N;
        int p1;
        if(i==0)p1=binary(i,r,mid);
        else p1=binary(i,r,mid+V[i-1]);
        int mina;
        if(i==0)mina=V[p1];
        else mina=V[p1]-V[i-1];
        int p2=binary(p1+1,r,mid+V[p1]);
        int minb,minc;
        minb=V[p2]-V[p1];
        minc=V[N-1]-(mina+minb);
        if(minb>=mina&&minc>=mina)ans=max(mina,ans);
        p2++;
        minb=V[p2]-V[p1];
        minc=V[N-1]-(mina+minb);
        if(minb>=mina&&minc>=mina)ans=max(mina,ans);
    }
    for(int i=0;i<N;++i){
        int r = i+N;
        int p1;
        if(i==0)p1=binary(i,r,mid);
        else p1=binary(i,r,mid+V[i-1]);
        p1--;
        int mina;
        if(i==0)mina=V[p1];
        else mina=V[p1]-V[i-1];
        int p2=binary(p1+1,r,mid+V[p1]);
        int minb,minc;
        minb=V[p2]-V[p1];
        minc=V[N-1]-(mina+minb);
        if(minb>=mina&&minc>=mina)ans=max(mina,ans);
        p2++;
        minb=V[p2]-V[p1];
        minc=V[N-1]-(mina+minb);
        if(minb>=mina&&minc>=mina)ans=max(mina,ans);
    }
    cout<<ans<<endl;
}

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

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

    int ans = 1001001001;
    for(int i = -100; i <= 100; i++){
        int coans = 0;
        for(int j = 0; j < n; j++){
            coans += (a[j]-i)*(a[j]-i);
        }
        if(ans > coans) ans = coans;
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 3596
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MOD = 1e9 + 7;
const int inf = 1e9;
const ll INF = 1e18;
const double pi = 3.14159265358979323846;
#define rep(i,n) for(ll i=0;i<n;i++)
using Graph = vector<vector<int>>;
int dx[4]={1,0,-1,0},dy[4]={0,1,0,-1};

int main(){
	int h,w;cin>>h>>w;
	char g[h][w];
	int cnt=h*w-1;
	rep(i,h) rep(j,w){
		cin>>g[i][j];
		if(g[i][j]=='#') cnt--;
	}

	int dist[h][w];
	rep(i,h) rep(j,w) dist[i][j]=inf;
	dist[0][0]=0;
	queue<pair<int,int>> q;
	q.push(make_pair(0,0));

	while(q.size()){
		pair<int,int> now=q.front();
		q.pop();
		rep(i,4){
			int ny=now.first+dy[i],nx=now.second+dx[i];
			if(ny>=0&&ny<h&&nx>=0&&nx<w&&g[ny][nx]!='#'&&dist[ny][nx]==inf){
				dist[ny][nx]=dist[now.first][now.second]+1;
				q.push(make_pair(ny,nx));
			}
		}
	}
	cnt-=dist[h-1][w-1];
	if(dist[h-1][w-1]==inf) cnt=-1;
	cout<<cnt<<"\n";
}

Measured memory_bytes: 256
#include<iostream>
#include<functional>
#include<queue>
#include<vector>
#include<algorithm>
using namespace std;
#pragma warning(disable:4996)
int n, m, q, a[1 << 18], b[1 << 18], c[1 << 18], d[1 << 18], e[1 << 18], dist[1 << 18];
vector<pair<int, int>>x[1 << 18], y[1 << 18], z[1 << 18];
vector<int>D[1 << 18];
void reader(int *x) {
	int k = getchar_unlocked(); *x = k - '0';
	while (true) {
		k = getchar_unlocked();
		if (k < '0' || k > '9') break;
		*x = ((*x) << 1) + ((*x) << 3) + k - '0';
	}
}
int main() {
	reader(&n); reader(&m); reader(&q);
	fill(d, d + m + 1, 1 << 30);
	for (int i = 1; i <= m; i++) reader(&a[i]), reader(&b[i]);
	for (int i = 1; i <= q; i++) reader(&c[i]), d[c[i]] = i;
	for (int i = 1; i <= m; i++) {
		x[a[i]].push_back(make_pair(b[i], d[i]));
		x[b[i]].push_back(make_pair(a[i], d[i]));
	}
	fill(dist, dist + n + 1, -1); dist[1] = 0;
	queue<int> Q1; Q1.push(1);
	while (!Q1.empty()) {
		int a1 = Q1.front(); Q1.pop();
		for (pair<int, int> i : x[a1]) {
			if (dist[i.first] == -1) {
				dist[i.first] = dist[a1] + 1;
				Q1.push(i.first);
			}
		}
	}
	for (int i = 1; i <= n; i++) {
		D[dist[i]].push_back(i);
		for (pair<int, int> j : x[i]) {
			if (dist[i] < dist[j.first]) y[i].push_back(j);
			if (dist[i] > dist[j.first]) z[i].push_back(j);
		}
	}
	e[1] = (1 << 30);
	for (int i = 1; i < n; i++) {
		for (int j : D[i]) {
			for (pair<int, int>k : z[j]) {
				e[j] = max(e[j], min(e[k.first], k.second));
			}
		}
	}
	sort(e + 1, e + n + 1);
	int T = 1;
	for (int i = 1; i <= q; i++) {
		while (e[T] <= i) T++;
		printf("%d\n", T - 1);
	}
	return 0;
}

Measured memory_bytes: 45224
//自称高知能系Vtuberの高井茅乃です。
//Twitter: https://twitter.com/takaichino
//YouTube: https://www.youtube.com/channel/UCTOxnI3eOI_o1HRgzq-LEZw

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

#define INF 1999999999
#define REP(i,n) for(int i=0;i<n;i++)
#define REP1(i,n) for(int i=1;i<=n;i++)
#define MODA 1000000007 

int main() {
    int ans = 0;
	int k; 
	cin >> k;

    cout << (k/2) * ((k+1)/2) << endl;
}

Measured memory_bytes: 256
import numpy as np
N = int(input())
letters = 'abcdefghij'
count = 0
L = ['']
while count < N:
    next_L = []
    for i in L:
        n = len(np.unique(i))
        for l in letters[:n+1]:
            next_L.append(i + l)
    L = next_L
    count += 1

for j in next_L:
    print(j)

Measured memory_bytes: 22108
//ABC 162 A-Lucky 7
#include <bits/stdc++.h>
using namespace std;

int main(){
	int n;
	cin >> n;
	
	while (n!=0){
		int x;
		x = n%10;
		if (x==7) {
			cout << "Yes";
			return 0;
		}
		n /= 10;
	}
	
	cout << "No";
	return 0;
}

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


int main()
{
	int n,k;
	cin>>n>>k;
	int a[n+1],sum=0;
	for(int i=0;i<n;i++) cin>>a[i];
	sort(a,a+n);
	for(int i=0;i<k;i++) sum += a[i];
	cout<<sum<<endl;
	return 0;
}


Measured memory_bytes: 3640
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int N=104;
char s[N];
int n;
int main() {
	scanf("%d",&n);
	scanf("%s",s+1);
	if (n&1) {
		puts("No");
	} else {
		int m=n>>1;
		bool f=true;
		for (int i=1;i<=m;++i) {
			if (s[i]^s[i+m]) {
				f=false;
				break;
			}
		}
		puts(f?"Yes":"No");
	}
	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define inf 1e9
#define ll long long
#define ull unsigned long long
#define M 1000000007
#define P pair<int,int>
#define PLL pair<ll,ll>
#define FOR(i,m,n) for(int i=m;i<n;i++)
#define RFOR(i,m,n) for(int i=m;i>=n;i--)
#define rep(i,n) FOR(i,0,n)
#define rrep(i,n) RFOR(i,n,0)
#define all(a) a.begin(),a.end()
const int vx[4] = {0,1,0,-1};
const int vy[4] = {1,0,-1,0};
#define PI 3.14159265

string s[100];
int a[100];
int n;


void g(int k,int m){

  int i=k+1;
  int res = a[k];

  while((int)s[i].length()==m){
    if(s[k-1][s[k-1].length()-1]=='+'){
      res+=a[i];
    }
    else{
      res*=a[i];
    }
    i++;
  }

  a[k-1]=res;
  rep(j,n){
    s[k+j]=s[i+j];
    a[k+j]=a[i+j];
  }

}




void f(){

  int m=0;
  rep(i,n){
    cin>>s[i];
    m = max(m,(int)s[i].length());
    a[i]=s[i][(int)s[i].length()-1]-'0';
  }

  while(m>1){
    rep(i,n){
      if((int)s[i].length()==m){
        g(i,m);
      }
    }
    m--;
  }

  cout<<a[0]<<endl;


}


int main(){

  while(1){
    cin>>n;
    if(n==0) break;
    f();
  }

  return 0;
}


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

int main() {
  int N, K;
  cin >> N >> K;
  int ans = 0;
  
  for(int i=0; i<N; i++) {
    int x;
    cin >> x;
    if(x <= K) {
      ans += min(x, K-x);
    }
    else {
      ans += min(x, x-K);
    }
  }
  
  cout << 2 * ans << endl;
}

Measured memory_bytes: 3624
const input = require("fs").readFileSync("/dev/stdin", "utf8")

;(input => {

    const lines = input.split("\n")
    const [N, M, X] = lines[0].split(" ").map(Number)
    const C = []
    const A = []

    for (let i = 0; i < N; i++) {
        const row = lines[i + 1].split(" ").map(Number)
        C[i] = row[0]
        A[i] = row.splice(1)
    }

    var ss = []
    for (var n = 1; n <= N; n++) {
        let s = []
        let d = 0
        let v = -1
        while (v !== undefined) {
            if (d === n) {
                ss.push([...s])
                s.pop()
                d--
            } else if (v >= N - 1) {
                v = s.pop()
                d--
            } else {
                v++
                s.push(v)
                d++
            }
        }
    }

    let t = Infinity
    let books = null
    while (books = ss.pop()) {
        let c = 0
        let s = Array(M).fill(0)
        books.forEach(book => {
            for (let i = 0; i < M; i++) {
                s[i] += A[book][i]
            }
            c += C[book]
        })
        if (Math.min(...s) >= X) {
            t = Math.min(t, c)
        }
    }

    console.log(t === Infinity ? -1 : t)

})(input)

Measured memory_bytes: 34072
# input
n = int(input())
A = []
for _ in range(n):
    A.append(list(map(int, input().split())))
    
# 変数定義
inf = 100 * 2000 + 1
M = A.copy()
M = [[a if a > -1 else inf for a in line] for line in M]
d = [inf] * n
V = set([i for i in range(n)])
T = set()

# 探索
start = 0
target = start
d[target] = 0
T.add(target)
while V != T:
    for i in (V - T):
        if M[target][i] < d[i]:
            d[i] = M[target][i]

    min_wheght = min([d[i] for i in (V - T)])
    min_path = [i for i in (V - T) if d[i] == min_wheght][0]
    target = min_path
    T.add(target)

# 出力
print(sum(d))


Measured memory_bytes: 6012
#include<stdio.h>
#include<string.h>
int main()
{
    char arr[3000]={0};
    scanf("%s",arr);
    int w,len,i,j,count=0;
    scanf("%d",&w);
    len=strlen(arr);
    char arr2[3000]={0};
    for(i=0,j=0;i<len;i+=w,j++)
    {
      arr2[j]=arr[i];
    }
    printf("%s\n",arr2);
    return 0;
}


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

#define ll long long
#define pb push_back

const ll N=1e5+9,inf=1e18,mod=1e9+7;



int main()
{
    int n;
    string a,b,c;
    cin>>n>>a>>b>>c;
    int cnt=0;
    for(int i=0;i<n;i++)
    {
        if(a[i]==b[i]&&b[i]==c[i])continue;
        if(a[i]==b[i]||b[i]==c[i]||a[i]==c[i])cnt++;
        else cnt+=2;
    }
   cout<<cnt<<"\n";
    return 0;
}




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

#define FOR(i, a, b) for(int i = (a); i < (b); i++)
#define REP(i, n)  FOR(i, 0, n)
#define ASC(c) sort((c).begin(), (c).end())
#define DESC(c) sort((c).begin(), (c).end(), greater<int>())

#define DUMP(x)  cerr << #x << " = " << (x) << endl;
#define DEBUG(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;

typedef long long ll;
typedef unsigned long long ull;
struct edge { int u, v; ll w; };
 
ll MOD = 1000000007;
ll _MOD = 1000000009;
double EPS = 1e-10;

int main() {
  int n; cin >> n;
  vector<int> v(n), c(n);
  REP(i, n) cin >> v[i];
  REP(i, n) cin >> c[i];
  int ans = 0;
  REP(i, n) {
    int diff = v[i] - c[i];
    if(diff > 0) ans +=  diff;
  }
  cout << ans << endl;
}


Measured memory_bytes: 256
Cards,Hints = map(int,input().split())
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        '''
        注意：0-idx
        '''
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

uf = UnionFind(Cards)
for i in range(Hints):
    x,y,z = map(int,input().split())
    uf.union(x-1,y-1)
print(uf.group_count())


Measured memory_bytes: 81568
#include <bits/stdc++.h>
using namespace std;
using LL = long long; using PII = pair<LL, LL>; using VI = vector<LL>; using VVI = vector<VI>;
using VB = vector<bool>; using VS = vector<string>; using VP = vector<PII>;
#define VV(T)        vector<vector<T>>
#define PB           push_back
#define MP           make_pair
#define SZ(a)        LL((a).size())
#define EACH(x, c)   for (auto x : (c))
#define ALL(c)       (c).begin(), (c).end()
#define REVERSE(c)   reverse(ALL(c))
#define SORT(c)      stable_sort(ALL(c))
#define RSORT(c)     stable_sort((c).rbegin(), (c).rend())
#define FOR(i, a, b) for (LL i = (a); i < (b); ++i)
#define REP(i, n)    FOR(i, 0, n)
#define $(x)         {cout << #x << " = " << (x) << endl;}


void solve(LL M, LL D){
    LL ans = 0;
    FOR(m, 1, M + 1) {
        FOR(d, 1, D + 1) {
            LL d1 = d % 10;
            LL d10 = d / 10;
            if (d1 >= 2 && d10 >= 2 && d1 * d10 == m) {
                ans++;
            }
        }
    }
    cout << ans << endl;
}

int main(){
    LL M;
    scanf("%lld",&M);
    LL D;
    scanf("%lld",&D);
    solve(M, D);
    return 0;
}


Measured memory_bytes: 256
n,p=map(int,input().split())
b=list(map(int,input().split()))
odd=[0]*(len(b)+1)
even=[0]*(len(b)+1)
even[0]=1
for i in range(len(b)):
  if b[i]%2==0:
    even[i+1]=even[i]*2
    odd[i+1]=odd[i]*2
  else:
    even[i+1]=odd[i]+even[i]
    odd[i+1]=odd[i]+even[i]

print((even[-1],odd[-1])[p])

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

int main(){
   int X;
   cin >> X;
   bool flag;
   for (int i=X; i<=100003; i++){
      flag = false;
      for (int j=2; j<pow(i, 0.5); j++){
         if (i % j == 0){
            flag = true;
            break;
         }
      }
      if (!flag){
         cout << i << endl;
         break;
      }
   }
}



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

int number = 1e9 + 7;

int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int h, w;
cin >> h >> w;
int a[h][w];
char b;
for (int i = 0; i<h; i++){
for (int j = 0; j<w; j++){
cin >> b;
if (b == '.'){
a[i][j] = 1;
}else{
a[i][j] = 0;
}
}
}

int dp[h][w] = {0};
for (int ii = 0; ii < h; ii++){
for (int jj = 0; jj < w; jj++){
if (a[ii][jj]){
if (ii == 0 && jj == 0){
dp[ii][jj] = 1;
}else if (ii == 0){
dp[ii][jj] = dp[ii][jj-1];
}else if (jj == 0){
dp[ii][jj] = dp[ii-1][jj];
}else{
dp[ii][jj] = dp[ii-1][jj] + dp[ii][jj-1];
}
}else{
dp[ii][jj] = 0;
}
dp[ii][jj] = dp[ii][jj] % number;

}
}

/*
for (int aa = 0; aa < h; aa++){
for (int bb = 0; bb < w; bb++){
cout << dp[aa][bb] << " ";
}
cout << "\n";
}
*/



cout << dp[h-1][w-1] << "\n";
return 0;
}


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

using namespace std;
typedef long long ll;
typedef vector<ll> vl;
typedef vector<string> vs;
using pll = pair<ll, ll>;
using vl = vector<ll>;
using vll = vector<vl>;
using vpll = vector<pll>;
struct Edge {
	ll to;
 	ll cost;
 };
using Graph = vector<vector<Edge>>;

#define FOR(i, a, b) for (ll i = (a); i < (b); i++)
#define REP(i, n) FOR(i, 0, n)
/***** define constant start *******/
const ll MOD = 1000000007;
const double PI = 3.1415926535897932;
const ll INF = LLONG_MAX;
string abc = "abcdefghijklmnopqrstuvwxyz";
string ABC = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
const ll MAX = 10000000;
/****** define constant end ********/
/****** define variable start ******/
ll n, k;
vl d;
/******* define variable end *******/
int solve() {
	cin >> n >> k;
	d.resize(k);
	vector<vector<ll>> a(k);
	REP(i, k){
		cin >> d[i];
		REP(j, d[i]){
			ll tmp;
			cin >> tmp;
			a[i].push_back(tmp);
		}
	}
	vector<bool> have(n);
	REP(i, k){
		REP(j, d[i]){
			have[a[i][j]-1] = true;
		}
	}
	ll ans = 0;
	REP(i, n){
		if(have[i] == false){
			ans++;
		}
	}
	cout << ans << endl;
	return 0;
}

int main() {
	//clock_t start = clock();
	cout << std::fixed << std::setprecision(10);
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int end_solve = solve();
	/*
	clock_t end = clock();
	const double time = static_cast<double>(end - start) / CLOCKS_PER_SEC *
	1000.0; printf("time %lf[ms]\n", time);
	*/

	return end_solve;
}


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

#define REP(i,n) for(int (i)=0;(i)<(n);++(i))
#define FOR(i,a,b) for(int (i)=(a);i<(b);++(i))
#define ALL(obj) (obj).begin(),(obj).end()
#define space <<" "<<
#define maxs(x,y) (x=max(x,y))
#define mins(x,y) (x=min(x,y))

using namespace std;

using ll = long long; using ull = unsigned long long;
using vb = vector<bool>; using vvb = vector<vb>;
using vi = vector<int>; using vvi = vector<vi>;
using vl = vector<ll>; using vvl = vector<vl>;
using pii = pair<int,int>; using pll = pair<ll,ll>;

const ll MOD = 1e9+7;

int main(){
char ch;
char an;
int number[26]={}; 
while(cin>>ch){
if(isalpha(ch)){
ch=tolower(ch);
number[ch-'a']++;
}
}
REP(i,26){
an='a'+i;
cout<<an<<" : "<<number[i]<<endl;
}
}


Measured memory_bytes: 3060
import sys
input = sys.stdin.readline
from collections import deque

N, D, A = map(int, input().split())
X = []
for _ in range(N):
    x, h = map(int, input().split())
    X.append((x, h))
X = sorted(X, key = lambda x: x[0])[::-1]
Q = deque([])

ans = 0
k = 0
while X:
    if len(Q) == 0 or X[-1][0] <= Q[0][0]:
        x, h = X.pop()
        h = max(h - k * A, 0)
        a = (h + A - 1) // A
        ans += a
        k += a
        deque.append(Q, (x + 2 * D, a))
    else:
        x, a = deque.popleft(Q)
        k -= a

print(ans)

Measured memory_bytes: 76860
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cmath>
#include <ctime>
#include <algorithm>
#include <utility>
#include <functional>
#include <string>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <bitset>
using namespace std;
typedef long long ll;

const int N = 1e5 + 5, INF = 0x3f3f3f3f;

struct P
{
	ll dif; int id;
	P(ll dif = 0, int id = -1) :dif(dif), id(id) {}
	P operator + (const P &a) const { return P(dif + a.dif, id); }
	bool operator < (const P &a) const { return dif > a.dif; }
};

P p[N];
int n, ans, loc[N];
ll L, a[N], b[N], c[N], d[N];

ll ok(int mid, int i)
{
	if (i <= mid) return p[mid].dif - a[p[i].id] + b[p[i].id];
	return p[mid].dif;
}

int main()
{
	while (~scanf("%d%lld", &n, &L))
	{
		for (int i = 0; i < n; i++)
		{
			scanf("%lld%lld", &a[i], &b[i]);
			p[i] = P(a[i] - b[i], i);
		}
		for (int i = 0; i < n; i++)
		{
			scanf("%lld", &c[i]);
			if (i) c[i] += c[i - 1];
		}
		sort(p, p + n);
		for (int i = 0; i < n; i++)
			loc[p[i].id] = i;
		int fu = n - 1;
		for (; fu >= 0 && p[fu].dif <= 0; fu--);
		for (int i = 1; i < n; i++)
			p[i] = p[i] + p[i - 1];
		ans = INF;
		for (int i = 0; i < n; i++)
		{
			ll len = L - a[i];
			int l = -1, r = fu;
			if (len <= 0) { ans = min(ans, 1); continue; }
			while (r - l > 1)
			{
				int mid = l + r >> 1;
				if (ok(mid, loc[i]) < len) l = mid;
				else r = mid;
			}
			int now = r - (r >= loc[i]), v = ok(r, loc[i]);
			if (v >= len&& v > c[now])
				ans = min(ans, now + 2);
		}
		printf("%d\n", ans == INF ? -1 : ans);
	}
	return 0;
}

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

#define EPS (1e-10)
#define rep(i, a, b) for (int i = a; i < (int)(b); ++i)
#define rrep(i, a, b) for (int i = b - 1; i >= (int)(a); --i)
#define all(a) a.begin(), a.end()

using namespace std;
using ll = long long;
using vi = vector<int>;
using vb = vector<bool>;
using vll = vector<ll>;
using vd = vector<double>;
using vvi = vector<vi>;
using vvb = vector<vb>;

constexpr int MOD = 1000000007;

map<int, int> factorize(int n) {
    map<int, int> factors;

    for (int i = 2; i * i <= n; i++) {
        while (n % i == 0) {
            ++factors[i];
            n /= i;
        }
    }
    if (n != 1) { factors[n] = 1; }
    return factors;
}

void divisors(const map<int, int>& factors, vi& ans, int x, int i) {
    if (i == (int)factors.size()) {
        ans.push_back(x);
        return;
    }

    pair<int, int> p = *(next(factors.begin(), i));
    rep(power, 0, p.second + 1) {
        divisors(factors, ans, x * (int)pow(p.first, power), i + 1);
    }
}

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

    int n;
    cin >> n;

    vi a(n + 1, 0);
    rep(i, 1, n + 1) { cin >> a[i]; }

    vi b;
    rrep(i, 1, n + 1) {
        if (a[i] == 1) {
            b.push_back(i);
            vi div;
            divisors(factorize(i), div, 1, 0);

            for (int d : div) {
                if (d == i) { continue; }
                a[d] ^= 1;
            }
        }
    }

    cout << b.size() << endl;
    rep(i, 0, b.size()) {
        cout << b[i];
        if (i == (int)b.size() - 1) {
            cout << endl;
        } else {
            cout << " ";
        }
    }

    return 0;
}

Measured memory_bytes: 2424
n = int(input())
x_lst = list(map(int,input().split()))
average1 = sum(x_lst) // n
average2 = sum(x_lst) // n + 1

answer1 = 0
for i in range(n):
    x = x_lst[i]
    answer1 += (x-average1) ** 2

answer2 = 0
for i in range(n):
    x = x_lst[i]
    answer2 += (x-average2) ** 2

answer = min(answer1,answer2)
print(answer)

Measured memory_bytes: 3188
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define ll long long
#define rep(i,l,r)for(ll i=(l);i<(r);i++)
#define max(p,q)((p)>(q)?(p):(q))
#define min(p,q)((p)<(q)?(p):(q))

char s[55],t[55];
int main(){
	scanf("%s%s",s,t);
	ll n=strlen(s);
	rep(i,0,n){
		putchar(s[i]);
		if(t[i])putchar(t[i]);
	}
}

Measured memory_bytes: 128
import std.stdio, std.string, std.conv, std.algorithm, std.numeric;
import std.range, std.array, std.math, std.typecons, std.container, core.bitop;

void main() {
    while (true) {
        int n, m, p;
        scan(n, m, p);

        if (!n && !m && !p) return;

        auto x = iota(n).map!(i => readln.chomp.to!int).array;
        solve(n, m, p, x).writeln;
    }
}

int solve(int n, int m, int p, int[] x) {
    return x[m-1] == 0 ? 0 : x.sum * (100 - p) / x[m-1];
}


void scan(T...)(ref T args) {
    string[] line = readln.split;
    foreach (ref arg; args) {
        arg = line.front.to!(typeof(arg));
        line.popFront();
    }
    assert(line.empty);
}



void fillAll(R, T)(ref R arr, T value) {
    static if (is(typeof(arr[] = value))) {
        arr[] = value;
    }
    else {
        foreach (ref e; arr) {
            fillAll(e, value);
        }
    }
}

Measured memory_bytes: 2448
#include<iostream>
#include<algorithm>
#include<string>
#include<cstdlib>
#include<map>
#include<iomanip>
#include<sstream>
#include<vector>
#include<stack>
#include<queue>
#include<math.h>
using namespace std;

int main(){
	
	long long int m=0,n,a[200005];
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		while(a[i]%2==0){
			m++;
			a[i]/=2;
		}
		
	}
	cout<<m;
}

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

class Program
{

    static void Main(string[] args)
    {
        int N = GetInputInt();
        int[] P = GetInputsInt();

        int count = 0;
        for (int i = 0; i < N; i++)
        {
            if (i + 1 == P[i]) continue;
            if (++count <= 2) continue;
            Console.WriteLine("NO");
            return;
        }

        Console.WriteLine("YES");

    }



    public static int GetInputInt()
    {
        return int.Parse(Console.ReadLine());
    }
    public static int[] GetInputsInt()
    {
        return Console.ReadLine().Split(' ').Select(int.Parse).ToArray();
    }
    public static List<int> GetInputsIntList()
    {
        return Console.ReadLine().Split(' ').Select(int.Parse).ToList();
    }
    public static long GetInputLong()
    {
        return long.Parse(Console.ReadLine());
    }
    public static long[] GetInputsLong()
    {
        return Console.ReadLine().Split(' ').Select(long.Parse).ToArray();
    }

}


Measured memory_bytes: 13396
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0; i<n; i++)
#define rep2(i,a,n) for(int i=(a); i<(n); i++)
#define all(vec) vec.begin(),vec.end()
using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using vll = vector<ll>;
int main() {
  int N, M, X; cin >> N >> M >> X;
  vi cost(N);
  vvi al(N, vi(M)); 
  rep(i,N){
    int c; cin >> cost[i];
    rep(j,M){
      int d; cin >> d;
      al[i][j]=d;
    }
  }
  int ans =1e9;
  bool can = false;
  for (int bit=0; bit<(1<<N); bit++){
    int pr = 0;
    vi alt(M,0); 
    for (int i=0; i<N; i++){
      if(bit & (1<<i)) {
        pr += cost[i];
        rep(j,M) alt[j] += al[i][j];
      }
    }
    int countM = 0;
    rep(i,M){ if (alt[i] >= X) countM++;}
    if(countM == M){
      ans = min(ans, pr);
      can = true;
    }
  }
  if(can) cout << ans << endl;
  else cout << -1 << endl;
}
  

Measured memory_bytes: 3596
#B問題

#文字列のSの先頭から、順にT文字ずつ照合して行って、一番取り替える文字数が少ないものを出力
#計算量は|S||T| (あるT文字に対し、|S|-|T|-1回作業が必要)

# 入力
S = input()
T = input()

#最初に巨大な値を用意することで、最小値をどんどん更新して行く。

ans = 1000000

for i in range(len(S) - len(T) + 1):
    #取り換え文字数の格納
    score = 0
    # Sのi文字目から連続するlen(T)文字を、Uとします
    # : は「スライス」と呼ばれる記法。始点:終点　と表記し、始点から終点までのインデックス番号の文字列を抽出。
    U = S[i:i + len(T)]
    for j in range(len(T)):
        if U[j] != T[j]:
            score += 1
    ans = min(ans, score)
    
print(ans)

Measured memory_bytes: 73200
#include<iostream>
#include<algorithm>
#include<cstdio>
using namespace std;

int a, b, c, d;

void Expression(int e, int f, int g, int h)
{
	int A[4] = { e,f,g,h };
	int B[4] = { 0,1,2,3 };
	do
	{
		int p = A[B[0]], q = A[B[1]], r = A[B[2]], s = A[B[3]];
		if (p + q + r + s == 10) { printf("%d + %d + %d + %d\n", p, q, r, s); return; }
		if (p + q + r - s == 10) { printf("%d + %d + %d - %d\n", p, q, r, s); return; }
		if (p + q - r - s == 10) { printf("%d + %d - %d - %d\n", p, q, r, s); return; }
		if (p * q + r + s == 10) { printf("%d * %d + %d + %d\n", p, q, r, s); return; }
		if (p * q + r - s == 10) { printf("%d * %d + %d - %d\n", p, q, r, s); return; }
		if (p * q - r - s == 10) { printf("%d * %d - %d - %d\n", p, q, r, s); return; }
		if (p * q * r - s == 10) { printf("%d * %d * %d - %d\n", p, q, r, s); return; }
		if (p - q * r + s == 10) { printf("%d - %d * %d + %d\n", p, q, r, s); return; }
		if (p * q * r + s == 10) { printf("%d * %d * %d + %d\n", p, q, r, s); return; }
		if (p * q * r - s == 10) { printf("%d * %d * %d - %d\n", p, q, r, s); return; }
		if (p * q * r * s == 10) { printf("%d * %d * %d * %d\n", p, q, r, s); return; }
		if (p * q + r * s == 10) { printf("%d * %d + %d * %d\n", p, q, r, s); return; }
		if (p * q - r * s == 10) { printf("%d * %d - %d * %d\n", p, q, r, s); return; }

		if ((p + q) * r - s == 10) { printf("(%d + %d) * %d - %d\n", p, q, r, s); return; }
		if ((p + q) * r + s == 10) { printf("(%d + %d) * %d + %d\n", p, q, r, s); return; }
		if ((p - q) * r - s == 10) { printf("(%d - %d) * %d - %d\n", p, q, r, s); return; }
		if ((p - q) * r + s == 10) { printf("(%d - %d) * %d + %d\n", p, q, r, s); return; }
		if ((p + q) * (r + s) == 10) { printf("(%d + %d) * (%d + %d)\n", p, q, r, s); return; }
		if ((p + q) * (r - s) == 10) { printf("(%d + %d) * (%d - %d)\n", p, q, r, s); return; }
		if ((p - q) * (r + s) == 10) { printf("(%d - %d) * (%d + %d)\n", p, q, r, s); return; }
		if ((p - q) * (r - s) == 10) { printf("(%d - %d) * (%d - %d)\n", p, q, r, s); return; }

	} while (next_permutation(B, B + 4));
	printf("0\n");
	return;
}

int main() {
	while (true) {
		cin >> a >> b >> c >> d;
		if (a == 0 && b == 0 && c == 0 && d == 0) { break; }
		Expression(a, b, c, d);
	}
	return 0;
}

Measured memory_bytes: 1148
#include <bits/stdc++.h>
using namespace std;
using lint = long long int;
lint N, W;

vector<lint> w, v;
int main()
{
    cin >> N >> W;
    w.resize(N);
    v.resize(N);
    for (int i=0; i<N; i++) cin >> w[i] >> v[i];

    int max_ = 0;
    for (int n=1; n<=100; n++)
    {
        // n個購入する場合
        lint w_res = min(W - w[0] * n, 3LL*n);
        if (w_res < 0) continue;
        vector<vector<vector<int> > > dp(N+1, vector<vector<int> > (n+1, vector<int>(w_res+1, 0)));
        for (int i=1; i<=N; i++)
        {
            int w_ = w[i-1] - w[0];
            int v_ = v[i-1];
            for (int j=1; j<=n; j++)
            {
                for (int iw=0; iw<=w_res; iw++)
                {
                    dp[i][j][iw] = dp[i-1][j][iw];
                    if (iw - 1 >= 0) dp[i][j][iw] = max(dp[i][j][iw], dp[i][j][iw-1]);
                    if (iw - w_ >= 0) dp[i][j][iw] = max(dp[i][j][iw], dp[i-1][j-1][iw-w_] + v_);
                }
            }
        }
        max_ = max(max_, dp.back().back().back());
    }
    cout << max_ << endl;
}


Measured memory_bytes: 12284
#include<iostream>

using namespace std;

const int maxWH = 52;
int H, W;
int C[maxWH][maxWH] = {0};

void dfs(int hh, int ww) {
  int dh[] = {-1, 0, 1, 0, -1, -1, 1, 1};
  int dw[] = {0, -1, 0, 1, -1, 1, -1, 1};
  //cout<<hh<<" "<<ww<<endl;
  if(0<=hh && 0<=ww && hh<H && ww<W) {
    if(C[hh][ww] == 1) {
      C[hh][ww] = 0; // false
      /*
      cout<<"now "<<hh<<" "<<ww<<endl;
      for(int i=0; i<8; i++) {
        cout<<hh+dh[i]<<" "<<ww+dw[i]<<endl;
      }
      */
      for(int i=0; i<8; i++) {
        dfs(hh+dh[i], ww+dw[i]);
      }
    }
  }
}

int main() {
  while(cin>>W>>H && !(W==0 && H==0)) {
    for(int i=0; i<H; i++) {
      for(int j=0; j<W; j++) {
	cin>>C[i][j];
      }
    }

    /*
    cout<<endl;
    for(int i=0; i<H; i++) {
      for(int j=0; j<W; j++) {
	cout<<C[i][j]<<" ";
      }
      cout<<endl;
    }
    */
    
    int ans = 0;
    for(int i=0; i<H; i++) {
      for(int j=0; j<W; j++) {
	if(C[i][j] == 1) {
	  ans++;
	  dfs(i,j);
	}
      }
    }
    cout<<ans<<endl;
  }
}

Measured memory_bytes: 1384
n, m = map(int, input().split())
l_lst = [0] * m
r_lst = [0] * m
for i in range(m):
    l, r = map(int, input().split())
    l_lst[i] = l
    r_lst[i] = r

if max(l_lst) <= min(r_lst):
    print(min(r_lst) - max(l_lst) + 1)
else:
    print(0)

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

int main(){
    int n,m;
    cin >> n >> m;
    vector<int> a;
    ll sum=0;
    for(int i=0; i<n; i++){
        int tmp;
        cin >> tmp;
        a.push_back(tmp);
    }
    sort(a.begin(),a.end());
    vector<pair<int,int>> p;
    for(int i=0; i<m; i++){
        int a,b;
        cin >> a >> b;
        p.push_back(make_pair(b,a));
    }
    sort(p.begin(),p.end(),greater<pair<int,int>>());
    int j=0;
    bool flag=true;
    for(int i=0; i<n; i++){
        while(true){
            if(a[i]<p[j].first&&p[j].second!=0){
                a[i]=p[j].first;
                p[j].second--;
            }
            else if(a[i]>=p[j].first){
                flag=false;
                break;
            }
            else if(p[j].second==0){
                //cout << "OK!" << i << endl;
                i--;
                break;
            }
            i++;
        }
        if(!flag)break;
        j++;
    }
    for(int i=0; i<n; i++){
        sum+=a[i];
        //cout << a[i] << " ";
    }
    cout << sum << endl;
}

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

#define sz(a) ((int)a.size())
#define forn(i,n) for(int i=0;i<(int)n;i++)
#define forse(i,s,e) for(int i=(int)s;i<(int)e;i++)
#define all(v) (v).begin(),(v).end()
#define pb push_back
#define mp make_pair
#define fi first
#define se second

using dbl=double;
using ll=long long;
using pii=pair<int, int>;
using pll=pair<ll, ll>;

dbl PI=3.141592653589793;


void solve(){
	char k;
	cin >> k;
	if(k>='a'){
		cout << 'a';
	}else cout << 'A';
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0); 
	int T=1;
//	cin >> T;
	for(int c=1;c<=T;c++){
		solve();
	}
}


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

int main(int argc, char const *argv[]) {
  string s, t, u;
  int a, b;
  cin >> s >> t >> a >> b >> u;
  if (s == u)
    a--;
  else
    b--;
  cout << a << " " << b << endl;
  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long int ll;

int h[20];

int main(){
	cin.tie(nullptr);
	ios::sync_with_stdio(false);
	int n; cin >> n;
	vector<int> a(n);
	vector<pair<int,int> > v[n];
	for(int i=0;i<n;i++){
		cin >> a[i];
		for(int j=0;j<a[i];j++){
			int x,y; cin >> x >> y;
			x--;
			v[i].push_back(make_pair(x,y));
		}
	}
	int ans=0;
	for(int i=0;i<(1<<n);i++){
		bool ok=true;
		for(int j=0;j<n;j++){
			h[j]=-1;
		}
		for(int j=0;j<n;j++){
			if(i&(1<<j)){
				if(h[j]==0)ok=false;
				h[j]=1;
				for(int k=0;k<a[j];k++){
					int y=v[j][k].first;
					if(v[j][k].second==0){
						if(h[y]==1){
							ok=false;
						}
						else{
							h[y]=0;
						}
					}
					else{
						if(h[y]==0){
							ok=false;
						}
						else{
							h[y]=1;
						}
					}
				}
			}
			else{
				if(h[j]==1)ok=false;
				h[j]=0;
			}
		}
		if(ok){
			ans=max(ans,__builtin_popcount(i));
		}
	}
	cout << ans << endl;
}


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

#define int long long

int32_t main()
{
    int a,b;
    cin >> a >> b;
    if(abs(b-a)%2==0)
    {
        cout << (max(a,b) + min(a,b)) /2 <<endl;
    }
    else cout << "IMPOSSIBLE" <<endl;
}

Measured memory_bytes: 256
package main

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

func main() {
	r := bufio.NewReader(os.Stdin)
	w := bufio.NewWriter(os.Stdout)
	defer w.Flush()
	var N, M int
	fmt.Fscan(r, &N, &M)
	uf := newUF(N)
	var x, y int
	for i := 0; i < M; i++ {
		fmt.Fscan(r, &x, &y)
		uf.unite(x-1, y-1)
	}
	checked := make([]int, uf.n)
	for i := range checked {
		r := uf.root(i)
		checked[r]++
	}
	fmt.Fprintln(w, (max(checked)))

}

type unionFind struct {
	pair []int
	n    int
}

func newUF(N int) *unionFind {
	uf := new(unionFind)
	uf.n = N
	pair := make([]int, N)
	for i := 0; i < N; i++ {
		pair[i] = -1
	}
	uf.pair = pair
	return uf
}
func (uf unionFind) unite(x int, y int) {
	rx := uf.root(x)
	ry := uf.root(y)
	if rx != ry {
		uf.pair[ry] += uf.pair[rx]
		uf.pair[rx] = ry
	}
}
func (uf unionFind) root(x int) int {
	if uf.pair[x] < 0 {
		return x
	}
	uf.pair[x] = uf.root(uf.pair[x])
	return uf.pair[x]
}
func (uf unionFind) same(x int, y int) bool {
	rx := uf.root(x)
	ry := uf.root(y)
	return rx == ry
}
func (uf unionFind) countTree() int {
	ans := 0
	checked := make([]bool, uf.n)
	for i := range checked {
		r := uf.root(i)
		if checked[r] {
			checked[r] = true
			ans++
		}
	}
	return ans
}
func (uf unionFind) size(x int) int {
	return -uf.pair[uf.root(x)]
}
func max(a []int) int {
	max := a[0]
	for _, i := range a {
		if i > max {
			max = i
		}
	}
	return max
}


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

R=[]
for i in range(n):
  r = int(input())
  R.append(r)

maxv = R[1]-R[0]
minv = R[0]

for j in range(1,n):
  maxv = max(maxv,R[j]-minv)
  minv = min(minv, R[j])
    
print(maxv)


Measured memory_bytes: 13592
#include<bits/stdc++.h>
using namespace std;
int main(){
  	cin.tie(0);
  	ios::sync_with_stdio(false);
	int n;
  	cin >> n;
  	int a[3];
  	for (int i = 0; i < 3; i++) cin >> a[i];
  	vector<int> l(n);
  	for (int i = 0; i < n; i++) cin >> l[i];
  	int ans = 1145141919;
  	for (int i = 0; i < (1 << (2 * n)); i++){
      	vector<int> st(n);
      	int hoge = i;
      	for (int j = 0; j < n; j++){
          	st[j] = hoge & 3;
          	hoge /= 4;
        }
		vector<int> x(4, 0);
      	vector<int> cnt(4, 0);
      	for (int j = 0; j < n; j++){
          	x[st[j]] += l[j];
          	cnt[st[j]]++;
        }
		int cost = 0;
		bool f = true;
		for (int j = 0; j < 3; j++) {
			if (cnt[j] == 0) f = false;
			cost += max((cnt[j] - 1) * 10, 0);
			cost += abs(x[j] - a[j]);
		}
		if (f) ans = min(ans, cost);
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 256
import java.util.Scanner;
public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        String w = sc.next().toLowerCase();
        String t;
        int count = 0;

        while( !((t=sc.next()).equals("END_OF_TEXT")) ){
            if(t.toLowerCase().equals(w)) count++;
        }

        System.out.println(count);
    }
}


Measured memory_bytes: 26224
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <utility>
#include <string>

using namespace std;

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

	int ans = (3 * a + p) / 2;
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MOD = 1e9 + 7;
const int inf = 1e9;
const ll INF = 1e18;
const double pi = 3.14159265358979323846;
#define rep(i,n) for(ll i=0;i<n;i++)

int main(){
	ll n;cin>>n;
	if(n%2==1||n<10){
		cout<<0<<"\n";
		return 0;
	}

	ll cnt=0;
	while(n){
		n/=5;
		cnt+=n/2;
	}

	cout<<cnt<<"\n";
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <numeric>
#include <utility>
#include <tuple>

#define REP(i, a, b) for (int i = int(a); i < int(b); i++)
using namespace std;
using ll = long long int;
using P = pair<ll, ll>;

// clang-format off
#ifdef _DEBUG_
#define dump(...) do{ cerr << __LINE__ << ":\t" << #__VA_ARGS__ << " = "; PPPPP(__VA_ARGS__); cerr << endl; } while(false)
template<typename T> void PPPPP(T t) { cerr << t; }
template<typename T, typename... S> void PPPPP(T t, S... s) { cerr << t << ", "; PPPPP(s...); }
#else
#define dump(...) do{ } while(false)
#endif
template<typename T> vector<T> make_v(size_t a, T b) { return vector<T>(a, b); }
template<typename... Ts> auto make_v(size_t a, Ts... ts) { return vector<decltype(make_v(ts...))>(a, make_v(ts...)); }
template<typename T> bool chmin(T &a, T b) { if (a > b) {a = b; return true; } return false; }
template<typename T> bool chmax(T &a, T b) { if (a < b) {a = b; return true; } return false; }
template<typename T> void print(T a) { cout << a << endl; }
template<typename T, typename... Ts> void print(T a, Ts... ts) { cout << a << ' '; print(ts...); }
template<typename T> istream &operator,(istream &in, T &t) { return in >> t; }
// clang-format on

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    int n;
    cin, n;
    vector<int> a(n);
    int sum = 0;
    REP(i, 0, n) {
        cin, a[i];
        sum ^= a[i];
    }
    REP(i, 0, n) {
        cout << (sum ^ a[i]) << " \n"[i + 1 == n];
    }
    return 0;
}


Measured memory_bytes: 3984