akhauriyash/Code-Regression huggingface dataset:
N,M,C=map(int,input().split())
B=list(map(int,input().split()))
A=[[] for _ in range(N)]

for i in range(N):
    A[i]=list(map(int,input().split()))
    
ans=0
for i in range(N):
    sc=C
    for j in range(M):
        sc+=A[i][j]*B[j]
    if sc>0:
        ans+=1
        
print(ans)

Measured memory_bytes: 38384
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using P = pair<ll, ll>;
const string ln = "\n";
constexpr int INF = 1001001001;
constexpr int MOD = 1000000007;

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

  string s;
  cin >> s;

  string key = "keyence";

  int len = s.size();

  string ans = "NO";
  for (int i = 0; i < len; i++) {
    for (int j = 0; j < len - i; j++) {
      string copy = s;
      copy.erase(i, j);

      if (copy == key) {
        ans = "YES";
        break;
      }
    }
  }

  cout << ans << endl;

  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int tax(int x){
  if((x*100)%108==0){
  return x*100/108;
  }
  else{
  return x*100/108+1;
  }
}
int main() {
  int a,b;
  cin >> a;
  b=tax(a);
  if(b*108/100==a){
  cout << b << endl;
  }
  else{
  cout << ":(" << endl;
  }  
}  

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

int spf[MAX] = {0}; 
  
void genPrimeFactors() { 
    spf[1] = 1; 
  
    for (int i = 2; i < MAX; i++) 
        spf[i] = i; 
  
    for (int i = 4; i < MAX; i += 2) 
        spf[i] = 2; 

    for (int i = 3; i * i < MAX; i++) {  
        if (spf[i] == i) { 
            for (int j = i * i; j < MAX; j += i) { 
                if (spf[j] == j) {spf[j] = i;}
            } 
        } 
    } 
} 
  
ll calcNoF(int n) { 
    if (n == 1) return 1; 
  
    int ans = 1; 
    int dup = spf[n];
    int c = 1; 
    int j = n / spf[n]; 
  
    while (j != 1) { 
        if (spf[j] == dup) 
            c += 1; 
        else { 
            dup = spf[j]; 
            ans = ans * (c + 1); 
            c = 1; 
        } 
        j = j / spf[j]; 
    } 
    ans = ans * (c + 1); 
  
    return ans; 
} 
  
int main() { 
    genPrimeFactors();
  
    int n;
    cin >> n;

    ll total  = 0;

    for(int i = 1; i < n; i++){
    	total += calcNoF(n-i);
    }

    cout << total << endl;
  
    return 0; 
} 

Measured memory_bytes: 7512
#define _GLIBCXX_DEBUG    //空コンテナ操作禁止　Clang環境では#define _LIBCPP_DEBUG 0
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<bitset>
#include<set>
#include<map>
#include<stack>
#include<queue>
#include<deque>
#include<list>
#include<iomanip>
#include<cmath>
#include<cstring>
#include<functional>
using namespace std;
using ll = long long;

int main(){
  int p, q, r;
  cin >> p >> q >> r;
  cout << min( p+q, min( q+r, r+p ) );
  return 0;
}



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

//#define int long long
#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()
#define rep(i,n) for(int i=0;i<n;++i)
#define rep1(i,n) for(int i=1;i<n;++i)
#define exrep(i, a, b) for(ll i = a; i < b; i++)
#define out(x) cout << x << endl
#define EPS (1e-7)
#define gearup ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
typedef long double ld;
typedef long long int ll;
typedef unsigned long long int ull;
typedef vector<int> vi;
typedef vector<char> vc;
typedef vector<bool> vb;
typedef vector<double> vd;
typedef vector<string> vs;
typedef vector<pair<int,int> > vpii;
typedef vector<vector<int> > vvi;
typedef vector<vector<char> > vvc;
typedef vector<vector<bool> > vvb;
typedef vector<vector<double> > vvd;
typedef vector<vector<string> > vvs;
typedef vector<ll> vl;
typedef vector<vector<ll> > vvl;
typedef vector<vector<vector<ll> > > vvvl;
ll MOD = 1000000007;
const long long L_INF = 1LL << 60;
const int INF = 2147483647; // 2^31-1
const double PI = acos(-1);
//cout<<fixed<<setprecision(10);

template<class T> inline bool chmin(T& a, T b) {if (a > b) {a = b;return true;}return false;}
template<class T> inline bool chmax(T& a, T b) {if (a < b) {a = b;return true;}return false;}
template<class T> void debug(T v){rep(i,v.size()) cout<<v[i]<<" ";cout<<endl;}
const ll dx[8] = {1, 1, 0, -1, -1, -1, 0, 1};
const ll dy[8] = {0, 1, 1, 1, 0, -1, -1, -1};

signed main(){
    gearup;
    ll n;cin>>n;
    vl a(n),b(n);
    rep(i,n)cin>>a[i]>>b[i];
    ll res = 0;
    for(int i=n-1;i>=0;i--){
        a[i]+=res;
        int mod = a[i]%b[i];
        if(mod)res+= b[i]-mod;
    }
    out(res);
}

Measured memory_bytes: 1792
#include <bits/stdc++.h>
#define REP(i, n) for (int i = 0; i < n; i++)
#define FOR(i, m, n) for (int i = m; i < n; i++)
#define ALL(v) (v).begin(), (v).end()
#define coutd(n) cout << fixed << setprecision(n)
#define ll long long int
#define vl vector<ll>
#define vi vector<int>
const int INF = 2147483647;
const ll MOD = 1000000007;

using namespace std;

int main() {
  int h, w, _k;
  cin >> h >> w >> _k;
  vector<string> s(h);
  REP(i, h) { cin >> s[i]; }

  int ans[h][w] = {};

  bool empty[h] = {};
  REP(i, h) {
    bool flag = true;
    REP(j, w) {
      if (s[i][j] == '#') {
        flag = false;
        break;
      }
    }
    empty[i] = flag;
  }

  int init = 0;
  REP(i, h) {
    if (!empty[i]) {
      init = i;
      break;
    }
  }

  int last = 0;
  int k = 1;
  REP(j, w) {
    if (s[init][j] == '#') {
      FOR(q, last, j + 1) { ans[init][q] = k; }
      k++;
      last = j + 1;
    }
  }
  FOR(j, last, w) { ans[init][j] = (k - 1); }

  REP(i, init) {
    REP(j, w) { ans[i][j] = ans[init][j]; }
  }

  FOR(i, init + 1, h) {
    if (empty[i]) {
      REP(j, w) { ans[i][j] = ans[i - 1][j]; }
    } else {
      last = 0;
      REP(j, w) {
        if (s[i][j] == '#') {
          FOR(q, last, j + 1) { ans[i][q] = k; }
          k++;
          last = j + 1;
        }
      }
      FOR(j, last, w) { ans[i][j] = (k - 1); }
    }
  }

  REP(i, h) {
    REP(j, w) {
      cout << ans[i][j];
      if (j != w - 1) {
        cout << " ";
      }
    }
    cout << endl;
  }
}


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

using namespace std;

int mp[400][400];
int vis[400];


int n, m;


int slove() {
    int cnt[350];
    memset(cnt, 0, sizeof(cnt));
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (!vis[mp[i][j]]) {
                cnt[mp[i][j]]++;
                break;
            }
        }
    }
    int maxx = 0, pos = 0;
    for (int i = 1; i <= m; i++) {
        if (cnt[i] > maxx) {
            maxx = cnt[i];
            pos = i;
        }
    }
    return pos;
}

int main() {
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            scanf("%d", &mp[i][j]);
        }
    }
    int cnt[310];
    int ans = n;
    int temp;
    for (int i = 1; i <= m; i++) {
        temp = 0;

        memset(cnt, 0, sizeof(cnt));
        for (int j = 1; j <= n; j++) {
            for (int k = 1; k <= m; k++) {
                if (!vis[mp[j][k]]) {
                    cnt[mp[j][k]]++;
                    temp = max(temp, cnt[mp[j][k]]);
                    break;
                }
            }
        }
        vis[slove()] = 1;
        ans = min(ans, temp);
    }
    printf("%d\n", ans);
    return 0;
}

Measured memory_bytes: 768
#include <stdio.h>

int main(void){
	int H, W, i, j;

	do{
		scanf("%d %d", &H, &W);
		if(H == 0 && W == 0){
			
			break;
		
		}else{
			
			for(i = 0; H > i; i++){
				for(j = 0; W > j; j++){

					if(i == 0 || i == (H-1) || j == 0 || j == (W-1)){
						printf("#");
					}else{
						printf(".");
					}

				}
				printf("\n");
			}
			
			printf("\n");

		}
	
	}while(H != 0 && W != 0);
	
	return(0);

}

Measured memory_bytes: 572
n,m = map(int,input().split())

ans,ansf = 1,n

for i in range(m):
    l,r = map(int,input().split())
    ans = max(ans,l)
    ansf = min(ansf,r)
    
if ansf - ans <0:
    print(0)
else:
    print(ansf-ans+1)

Measured memory_bytes: 9192
N = int(input())
A_1 = [int(a_1) for a_1 in input().split()]
A_2 = [int(a_2) for a_2 in input().split()]
ans = 0
for n in range(N):
  c = sum(A_1[0:n+1]) + sum(A_2[n:N])
  if ans < c:
    ans = c
print(ans)

Measured memory_bytes: 3060
import java.util.*;
public class Main {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int x = 0, y = 0;
        for(int i = 1; i <= N; i++){
        	x += 800;
        	if(i % 15 == 0) y += 200;
        }
        System.out.println(x-y);
	}

}


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

int main() {
	int n; string m;
	while (cin >> n >> m) {
		vector<pair<int, int>>v;
		rep(i, n) {
			int a, b; scanf("%d%d", &a, &b); a--; b--;
			v.push_back({ a,b });
		}
		reverse(v.begin(), v.end());
		for (auto p : v) {
			swap(m[p.first], m[p.second]);
			rep(i, p.second - p.first) {
				if (m[p.first] == 'z')m[p.first] = 'a';
				else m[p.first]++;
				if (m[p.second] == 'z')m[p.second] = 'a';
				else m[p.second]++;
			}
		}
		cout << m << endl;
	}
}

Measured memory_bytes: 3132
#include <iostream>
#include <string>

using namespace std;

int main(){
    string o,i;
    cin >> o >> i;

    string ans;

    for(int n = 0; n < o.size() + i.size(); n++){
        if(n % 2 == 0){
            ans = ans + o[n / 2 ];
        }else{
            ans = ans + i[(n - 1) / 2];
        }
    }

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

Measured memory_bytes: 256
#include <iostream>

using namespace std;

#define INT_MIN     (-2147483647 - 1) /* minimum (signed) int value */
#define INT_MAX       2147483647    /* maximum (signed) int value */
static const int MAX = 100;
static const int WHITE = 0;
static const int GRAY = 1;
static const int BLACK = 2;

int n, m[MAX][MAX];

int prim()
{
	int color[MAX], p[MAX], d[MAX];
	int u, minv;

	for (int i = 0; i < n; ++i)
	{
		color[i] = WHITE;
		p[i] = -1;
		d[i] = INT_MAX;
	}

	d[0] = 0;

	while (1)
	{
		minv = INT_MAX;
		u = -1;
		for (int i = 0; i < n; ++i)
		{
			if (d[i] < minv && color[i] != BLACK)
			{
				u = i;
				minv = d[i];
			}
		}

		if (-1 == u) 
			break;
		color[u] = BLACK;

		for (int i = 0; i < n; ++i)
		{
			if (m[u][i] < d[i] && color[i] != BLACK)
			{
				d[i] = m[u][i];
				p[i] = u;
				color[i] = GRAY;
			}
		}
	}

	int sum = 0;
	for (int i = 0; i < n; ++i)
	{
		if (p[i] != -1) 
			sum += m[p[i]][i];
	}
	return sum;
}

int main()
{
	cin >> n;
	for (int i = 0; i < n; ++i)
	{
		for (int j = 0; j < n; ++j)
		{
			int e; cin >> e;
			m[i][j] = (e == -1) ? INT_MAX : e;
		}
	}
	cout << prim() << endl;
}

Measured memory_bytes: 3112
#include <bits/stdc++.h>
#include <unordered_map>
using namespace std;
#define all(v)          ((v).begin()), ((v).end())
#define fast ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define clr(v,d)		memset(v, d, sizeof(v))
const double EPS = 1e-8;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int>P;
const ll mod = 998244353;
int dx[] = { 0, 0, -1, 1, 1, 1, -1, -1 };
int dy[] = { 1, -1, 0, 0, 1, -1, -1, 1 };
const int N = 500001;
#define endl '\n'
#define F first
#define S second
#define pii pair<int,int>
#define pll pair<ll,ll>
void stop(){
#ifndef ONLINE_JUDGE
	system("pause");
#endif
}
struct point{
	double x, y;
};
ll gcd(ll a, ll b){ return !b ? a : gcd(b, a % b); }
ll fixMod(ll a, ll b){ return ((a%b) + b) % b; }
double triangle_area(int x1, int y1, int x2, int y2, int x3, int y3) {
	return abs((x2 - x1) * (y3 - y1) - (y2 - y1) * (x3 - x1)) / 2.;
};
ll dis(point a, point b) {
	ll x = a.x - b.x, y = a.y - b.y;
	return x * x + y * y;
}
double traingleArea(double a, double b, double c) {
	double s = (a + b + c) / 2.0;
	return sqrt(s * (s - a) * (s - b) * (s - c));
}
double circleArea(double r) {
	return acos(-1) * r * r;
}
ll power(ll x, ll y)
{
	if (y == 0)return 1;
	if (y == 1)return x;
	ll r = power(x, y / 2) % mod;
	return r%mod*r%mod*power(x, y % 2) % mod;
}
char g[1000][1000];
int n, m;
bool vis[1000][1000];
bool vis2[1000][1000];
ll a, b;
void dfs(int i, int j,int cur){
	vis[i][j] = 1;
	vis2[i][j] = 1;
	for (int k = 0; k < 4; k++){
		int x = i + dx[k], y = j + dy[k];
		if (x >= 0 && x < n&&y >= 0 && y < m &&!vis[x][y]){
			if (cur == 1 && g[x][y] == '#')continue;
			if (cur == 0 && g[x][y] == '.')continue;
			if (g[x][y] == '.')a++;
			if (g[x][y] == '#')b++;
			  dfs(x, y, !cur);
		}
	}
	//vis[i][j] = 0;
}
int main(){
	fast
	
	cin >> n >> m;
	for (int i = 0; i < n; i++)cin >> g[i];
	ll ans = 0;
	for (int i = 0; i < n; i++){
		for (int j = 0; j < m; j++){
			if (!vis2[i][j]&&g[i][j]=='#'){
				dfs(i, j, 1);
				b++;
				ans += a*b;
				//cout << a << " " << b << endl;
				a = b = 0;
			}
		}
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 8960
# C
from collections import deque

N, M = map(int, input().split())
s = list(input())
s_ = []
for c in s:
    s_.append(c)

# Graph
G = dict()
for i in range(1, N+1):
    G[i] = dict()

for _ in range(M):
    a, b = map(int, input().split())
    G[a][b] = 1
    G[b][a] = 1
    
# clean up
queue = deque()
go = True

As = [0]*N
Bs = [0]*N

for i in range(1, N+1):
    if s[i-1] != "C":
        a = 0
        b = 0
        for k in G[i].keys():
            v = s_[k-1]
            if v == "A":
                a += 1
            elif v == "B":
                b += 1
        As[i-1] = a
        Bs[i-1] = b
        if a*b == 0:
            queue.append(i)
            s[i-1] = "C"

while len(queue) > 0:
    j = queue.popleft()
    for i in G[j].keys():
        if s[i-1] != "C":
            if s_[j-1] == "A":
                As[i-1] -= 1
            else:
                Bs[i-1] -= 1
            if As[i-1] * Bs[i-1] == 0:
                queue.append(i)
                s[i-1] = "C"

if "A" in s and "B" in s:
    print("Yes")
else:
    print("No")

Measured memory_bytes: 126480
using System;

class lec01_B{
  public static void Main(){
    string[] str = Console.ReadLine().Split(' ');
    int x = int.Parse(str[0]);
    int y = int.Parse(str[1]);
    Console.WriteLine(Gcd(x,y));
  }
  public static int Gcd(int a,int b){
    if(a < b)
      return Gcd(b,a);
      while(b != 0){
        var remainder = a % b;
        a = b;
        b = remainder;
      }
      return a;
  }
}



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

using namespace std;

//int N,M,K,L,R,H,W;
long long int N,M,K,L,R,H,W;

constexpr long long int MOD=1000000007;
//constexpr  int MOD=1000000007;
//constexpr int MOD=998244353;
//constexpr long long int MOD=998244353;

constexpr long double EPS=1e-8;



int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	
	cin>>N>>M;
	vector<int>v(M);
	for(auto &i:v){
		cin>>i;
		i--;
	}
	vector<vector<int>>w(M,vector<int>(N));
	for(auto &i:w)for(auto &j:i)cin>>j,j--;
	vector<int>ans(N);
	for(int i=0;i<M;i++){
		for(int j=0;j<N;j++){
			if(w[i][j]==v[i])ans[j]++;
			else ans[v[i]]++;
		}
	}
	for(auto i:ans)cout<<i<<endl;
	return 0;
}


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

struct DLL {
  DLL *prev, *next;
  int val;
};

DLL* nil; //番兵

void init(){
  nil = new DLL();
  nil->prev = nil;
  nil->next = nil;
}

void insert(int x){
  DLL* node = new DLL();
  nil->next->prev = node;
  node->val = x;
  node->next = nil->next;
  node->prev = nil;
  nil->next = node;

};

void del(DLL* node){
  if(node==nil){return;}
  node->prev->next = node->next;
  node->next->prev = node->prev;
  delete node;
};

DLL* search(int x){
  DLL* node = nil->next;
  while (node!=nil) {
    if(node->val == x){
      return node;
    }else{
      node = node->next;
    }
  }
  return nil;
}

void delFirst(){
  del(nil->next);
};

void delLast(){
  del(nil->prev);
};

void show(){
  DLL* node = nil->next;
  while (node!=nil) {
    std::cout << node->val;
    node = node->next;
    if (node!=nil) {
      std::cout << " ";
    }
  }
  std::cout << '\n';
};

void showback(){
  DLL* node = nil->prev;
  while (node!=nil) {
    std::cout << node->val << ' ';
    node = node->prev;
  }
  std::cout << '\n';
};

int main(int argc, char const *argv[]) {
  int n;
  int x;
  string command;

  std::cin >> n;

  init();

  for (size_t i = 0; i < n; i++) {
    std::cin >> command;

    if (command == "insert") {
      std::cin >> x;
      insert(x);
    }else if(command == "delete"){
      std::cin >> x;
      DLL* node = search(x);
      del(node);
    }else if(command == "deleteFirst"){
      delFirst();
    }else if(command == "deleteLast"){
      delLast();
    }
  }

  show();

  return 0;
}



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

#undef _P
#define _P(...) (void)printf(__VA_ARGS__)
#define FOR(x,to) for(x=0;x<(to);x++)
#define FORR(x,arr) for(auto& x:arr)
#define ITR(x,c) for(__typeof(c.begin()) x=c.begin();x!=c.end();x++)
#define ALL(a) (a.begin()),(a.end())
#define ZERO(a) memset(a,0,sizeof(a))
#define MINUS(a) memset(a,0xff,sizeof(a))
//-------------------------------------------------------

int N,L;
string A;
int ismin[256];


vector<pair<int,int>> construct(int mask) {
	vector<pair<int,int>> V;
	
	int i;
	FOR(i,N) if(mask&(1<<i)) {
		if(__builtin_popcount(mask)==1) {
			V.push_back({i,1});
			V.push_back({i+1,1});
			V.push_back({i+1,0});
			V.push_back({i,0});
		}
		else {
			vector<pair<int,int>> W=construct(mask^(1<<i));
			V.push_back({i,1});
			while(V.back().first+1<W[0].first) {
				V.push_back(V.back());
				V.back().first++;
			}
			FORR(w,W) V.push_back(w);
			V.push_back(W.back());
			V.back().second=1;
			while(V.back().first>i) {
				V.push_back(V.back());
				V.back().first--;
			}
			V.push_back({i,0});
			V.push_back({i+1,0});
			V.push_back({i+1,1});
			reverse(ALL(W));
			while(V.back().first<W[0].first) {
				V.push_back(V.back());
				V.back().first++;
			}
			
			FORR(w,W) V.push_back(w);
			while(V.back().first>i+1) {
				V.push_back(V.back());
				V.back().first--;
			}
			V.push_back({i+1,0});
			V.push_back({i,0});
		}
		break;
	}
	return V;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>A;
	L=1<<N;
	FORR(c,A) c-='0';
	FOR(x,L) FOR(y,L) if((x&y)==y && A[x] && A[y]==0) return _P("Impossible\n");
	FOR(x,L) ismin[x]=A[x]==0;
	FOR(x,L) if(A[x]==0) FOR(y,L) if((x&y)==y && y<x && A[y]==0) ismin[y]=0;
	
	vector<pair<int,int>> W;
	W.push_back({0,0});
	FOR(x,L) if(A[x]==0) {
		vector<pair<int,int>> V=construct(x);
		FOR(i,V[0].first) W.push_back({i,1});
		FORR(v,V) W.push_back(v);
		for(i=V[0].first;i>=0;i--) W.push_back({i,1});
		W.push_back({0,0});
	}
	cout<<"Possible"<<endl;
	cout<<W.size()-1<<endl;
	FORR(w,W) cout<<w.first<<" "<<w.second<<endl;
	/*
	FOR(i,W.size()-1) {
		cout<<i<<" "<<W[i].first<<" "<<W[i].second<<" "<<W[i+1].first<<" "<<W[i+1].second<<endl;
		assert(abs(W[i].first-W[i+1].first)+abs(W[i].second-W[i+1].second)==1);
	}
	*/
	
}


int main(int argc,char** argv){
	string s;int i;
	if(argc==1) ios::sync_with_stdio(false), cin.tie(0);
	FOR(i,argc-1) s+=argv[i+1],s+='\n'; FOR(i,s.size()) ungetc(s[s.size()-1-i],stdin);
	cout.tie(0); solve(); return 0;
}


Measured memory_bytes: 892
#include<bits/stdc++.h>
using namespace std;
const int N=5010;
int n;
int head[N],cnt;
struct edge
{
	int to,next;
}e[N<<1];
const int mod=1000000007;
void adde(int a,int b)
{
	e[++cnt].to=b; e[cnt].next=head[a]; head[a]=cnt;
}
long long f[N][N],g[N];
int sz[N];
void dfs(int u,int fa)
{
	f[u][1]=1;sz[u]=1;
	int tmp[N];
	memset(tmp,0,sizeof(tmp));
	for(int i=head[u];i;i=e[i].next)
	{
		int v=e[i].to;
		if(v==fa)continue;
		dfs(v,u);
		for(int j=sz[u];j>=0;j--)
			for(int k=sz[v];k>=0;k--)
				(tmp[j+k]+=f[u][j]*f[v][k]%mod)%=mod;
		sz[u]+=sz[v];
		for(int j=0;j<=sz[u];j++)
			f[u][j]=tmp[j],tmp[j]=0;
	}
	f[u][0]=0;
	for(int i=1;i<=sz[u];i++)
		(f[u][0]+=mod-f[u][i]*g[i]%mod)%=mod;
}
int main()
{
	scanf("%d",&n);
	int u,v;
	for(int i=1;i<n;i++)
	{
		scanf("%d%d",&u,&v);
		adde(u,v); adde(v,u);
	}
	g[2]=1;
	for(int i=4;i<=n;i+=2)g[i]=g[i-2]*(i-1)%mod;
	dfs(1,0);
	printf("%lld\n",(mod-f[1][0])%mod);
	return 0;
}


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

int main()
{
    int n,i;
    double sum=0;
    cin>>n;
    double a[n];
    for(i=0;i<n;i++)
        cin>>a[i];
    for(i=0;i<n;i++)
    {
        sum+=1.0/a[i];

    }
    cout<<fixed<<setprecision(6)<<(1/sum);
    return 0;
}


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

#define REP(i, n) for(int i = 0; i < n; i++)
#define RREP(i,n) for(int i = (n)-1; i >= 0; i--)
#define FOR(i, l, r) for(int i = l; i < r; i++)
#define RFOR(i, l,r) for(int i= (l)-1; i>= (r) ; i--)

#define int64 int64_t
#define uint64 uint64_t
#define uint unsigned

array< array< array<short, 10>, 3>, 4> in = { 0 };
constexpr char sa[] = "####################\n";

int main()
{
    int n;
    cin >> n;
    REP(i, n)
    {
        short b, f, r, v;
        cin >> b >> f >> r >> v;
        in[b-1][f-1][r-1] += v;
    }
    REP(q, 3)
        {
            REP(r, 10)
                cout << ' ' << in[0][q][r];
            cout << '\n';
        }
    FOR(p, 1, 4){
        cout << sa;
        REP(q, 3)
        {
            REP(r, 10)
                cout << ' ' << in[p][q][r];
            cout << '\n';
        }
    }
}

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

int n, m;
string s;

int main()
{
  cin >> n >> s;
  if (n&1) {puts("No"); return 0;}
  m = n/2;
  for(int i=0; i<m; ++i) if (s[i] != s[m+i]) {
    puts("No"); return 0;
  }
  puts("Yes");
}

Measured memory_bytes: 256
#!/usr/bin/env python3
import sys, math
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
sys.setrecursionlimit(10**8)
inf = float('inf')
ans=count=0

n=int(input())
S=input()
if n%2!=0:
    print("No")
    exit()
n=n//2
if S[:n]==S[n:]:
    print("Yes")
else:
    print("No")
# print(S[:n],S[n:])
    


Measured memory_bytes: 38384
#include<bits/stdc++.h>
#define ll long long
#define N 1000010
#define mo 1000000007
using namespace std;
ll n,jie[N],nj[N],ansn;
ll c(ll x,ll y){return (jie[x]*nj[y]%mo)*nj[x-y]%mo;}
ll po(ll x,ll y){ll z=1;while (y){if (y%2)z=x*z%mo;x=x*x%mo;y/=2;}return z;}
int main(){
	cin>>n;
	jie[0]=1;for (int i=1;i<=n;i++){jie[i]=jie[i-1]*i%mo;}
	nj[n]=po(jie[n],mo-2);for (int i=n-1;i>=0;i--)nj[i]=nj[i+1]*(i+1)%mo;
	int a=1,b=0;
	for (int i=1;i<=n;i++){
		int na=(b+b)%mo,nb=(b+a)%mo;
		b=nb;a=na;
		ansn=(ansn+((b*c(n,i)%mo)*po(i,mo-2)%mo)*po(n,mo-2))%mo;
	}
	cout<<ansn*po(3,(mo-2)*n)%mo<<endl;
	return 0;
}

Measured memory_bytes: 15872
# -*- coding: utf-8 -*-

N, K = map(int, input().split())
h_list = [int(input()) for i in range(N)]

h_list.sort()
'''
best = 1000000000
for i in range(N - K + 1):
    diff = h_list[i:i+K][-1] - h_list[i:i+K][0]
    if diff < best:
        best = diff
'''
print (min(h_list[i+K-1] - h_list[i] for i in range(N-K+1)))

Measured memory_bytes: 7428
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int H,A,N,M,K,S,T,X,Y,Z;
  cin >> H >> N;
  vector<int> val(N);

  for(int i=0 ; i < N ; i++){
    cin >> val.at(i);
  }

  if((N * (10000)) < H){
    cout << "No" << endl;
    return(0);
  }


  for(int j=0 ; j < N ; j++){
    H -= val.at(j);
    if(H <= 0){
        cout << "Yes" << endl;
        return(0);
    }
  }
  cout << "No" << endl;
  return(0);
}

Measured memory_bytes: 640
// https://atcoder.jp/contests/abc104/tasks/abc104_c

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <stack>
#include <queue>
#include <set>
#include <map>

using namespace std;

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

typedef long long ll;

void Main()
{
    int D, G; cin >> D >> G;
    int p[15];
    int c[15];
    rep(i, D) cin >> p[i] >> c[i];
    
    int res = 10000;
    for (int bit = 0; bit < (1<<D); ++bit) {
        vector<int> S;
        int max_num = -1;
        for (int i = 0; i < D; ++i) {
            if (bit & (1 << i)) {
                S.push_back(i);
            } else {
                max_num = max(i, max_num);
            }
        }
        int sum = 0;
        int cnt = 0;
        rep(i, S.size())
        {
            sum += (c[S[i]] + 100 * (S[i] + 1) * p[S[i]]);
            cnt += p[S[i]];
        }
        if (sum < G) {
            int a = G - sum;
            int b = (100 * (max_num + 1));
            int _cnt = (a + b - 1) / b;
            if (p[max_num] < _cnt) continue;
            cnt += _cnt;
        }
        res = min(res, cnt);
    }
    cout << res << endl;
}

int main()
{
    cin.tie(nullptr);
	ios_base::sync_with_stdio(false);
	Main();
}


Measured memory_bytes: 256
#include<iostream>
#include<cmath>
using namespace std;
typedef long long ll;
ll dp[18][100000];
ll powd[18];

bool can(ll mid, ll pos, ll a){
	ll submi = mid;
	ll cango = a;
	while(submi){
		ll flag = 0;
		while(submi >= powd[flag]){
			++flag;
		}
		--flag;
		cango = dp[flag][cango];
		submi -= powd[flag];
	}
	return cango >= pos;
}
	

int main(){
	for(int i = 0; i < 18; ++i) powd[i] = pow(2, i);
	ll n; cin >> n;
	ll x[n];
	for(ll i = 0; i < n; ++i){
		cin >> x[i];
		for(ll j = 0; j < 18; ++j){
			dp[j][i] = 0;
		}
	}

	ll l, q; cin >> l >> q;
	for(ll i = 0; i < n; ++i){
		ll upper = n - 1;
		ll lower = 0;
		while(upper - lower > 1){
			ll mid = (upper + lower) / 2;
			if(x[mid] - x[i] <= l) lower = mid;
			else upper = mid;
		}
		dp[0][i] = (x[upper] - x[i] <= l ? upper : lower);
	}

	for(ll i = 1; i < 18; ++i){
		for(ll j = 0; j < n; ++j) dp[i][j] = dp[i - 1][dp[i - 1][j]];
	}
	for(ll que = 0; que < q; ++que){
		ll a, b; cin >> a >> b;
		--a; --b;
		if(a > b) a ^= b ^= a ^= b;
		ll lower = 0;
		ll upper = n - 1;
		while(upper - lower > 1){
			ll mid = (upper + lower) / 2;
			if(can(mid, b, a)) upper = mid;
			else lower = mid;
		}
		cout << (can(lower, b, a) ? lower : upper) << endl;
	}
	return 0;
}

Measured memory_bytes: 15616
n=int(input())
xl=[list(map(int,input().split())) for _ in range(n)]
lr=[[xl[i][0]-xl[i][1],xl[i][0]+xl[i][1]] for i in range(n)]
lr.sort(key=lambda x:x[1])
ans=n
r=lr[0][1]
for i in range(1,n):
  if lr[i][0]<r:
    ans-=1
  else:
    r=lr[i][1]
print(ans)

Measured memory_bytes: 42792
import java.util.*;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int N = sc.nextInt();
    long L = 1;
    long l = 2;
    long m;

    if(N == 1) {
      System.out.println(1);
    } else {
    for(int i=1; i<N; i++) {
      m = L;
      L = L + l;
      l = m;
    }
    System.out.println(L);
  }
}
}

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


int main(){
  int a, b;
  cin >> a >> b;
  int x = a + b;
  int y = a-b;
  int z = a * b;
  int w = max(x, max(y, z));

  cout << w << endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>

using namespace std;
 
struct P {
    int x, y;
    P(int x, int y) : x{x}, y{y} {}
};
 
int limit;
vector<int> v;

constexpr int X[] = {2, 1, 2, 3, 0, 1, 2, 3, 4, 1, 2, 3, 2};
constexpr int Y[] = {0, 1, 1, 1, 2, 2, 2, 2, 2, 3, 3, 3, 4};
 
int next_pos(int x, int y)
{
    for (int i = 0; i < 13; i++) {
        if (x == X[i] && y == Y[i]) {
            return i;
        }
    }        
    return -1;
}
 
int getMD()
{
    int sum = 0;
    for (int i = 0; i < 13; i++) {
        if (v[i] == 0) continue;
        sum += abs(X[i] - X[v[i]]) + abs(Y[i] - Y[v[i]]);
    }
    return sum;
}
 
constexpr int dx[] = {-1, 0, 1, 0};
constexpr int dy[] = {0, -1, 0, 1};
 
bool dfs(const int* sp, int step)
{
    int md = getMD();
    if (md == 0) return 1;
    if (md + step > limit) {
        return 0;
    }
    
    for (int i = 0; i < 2; i++) {
        int x = X[sp[i]], y = Y[sp[i]];
        for (int j = 0; j < 4; j++) {
            int nx = x + dx[j], ny = y + dy[j];
            int next = next_pos(nx, ny);
            if (next == -1) continue;
            
            const int nsp1[] = {next, sp[1]}, nsp2[] = {sp[0], next};
            
            swap(v[sp[i]], v[next]);
            if (i == 0 && dfs(nsp1, step + 1)) {
                return 1;
            }
            if (i == 1 && dfs(nsp2, step + 1)) {
                return 1;
            }
            swap(v[sp[i]], v[next]);
        }
    }
    return 0;
}
 
int main()
{
    int x;
    while (cin >> x, x != -1) {
        int sp[2];
        v.resize(13); v[0] = x;
        for (int i = 1; i < 13; i++) {
            cin >> v[i];
        }

        for (int i = 0, j = 0; i < 13; i++) {
            if (v[i] == 0) {
                sp[j++] = i;
            }
        }

        bool found = 0;
        constexpr int LIMIT = 20;
        for (limit = 0; limit <= LIMIT; limit++) {
            if (dfs(sp, 0)) {
                cout << limit << endl;
                found = 1;
                break;
            }
        }
        if (!found) {
            cout << "NA" << endl;
        }
    }
    return 0;
}

Measured memory_bytes: 3004
n,q=map(int,input().split())
S=input()
L=[list(map(int,input().split())) for i in range(q)]

s=[0]*(n+1)
for i in range(1,n+1):
    if i<=n-1 and S[i-1]=='A' and S[i]=='C':
        s[i]=s[i-1]+1
    else:
        s[i]=s[i-1]

#print(s)
for l,r in L:
    ans=s[r-1]-s[l-1]
    print(ans)

Measured memory_bytes: 30640
#include<iostream>
#include<cmath>
using namespace std;
int main (){
  unsigned long long MAX = 1000000000;
  int rock,k;
  cin>>rock>>k;
  int values[rock] = {0};
  unsigned long long dp[rock] = {0};
  for(int i=0;i<rock;++i){
    cin>>values[i];
  	dp[i] = MAX;
  }
  dp[0] = 0;
  for(int i=1;i<rock;++i)
    for(int j=1;j<=k;++j)
      if(j<=i)
    	dp[i] = min(dp[i], dp[i-j] + abs(values[i] - values[i-j]));
  cout<<dp[rock-1];
  
return 0;
}

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

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

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

         sort(a,a+n);

         int ans=10000000;
         for(int i=1; i<n; i++){
             ans = min(ans,a[i]-a[i-1]);
         }
         cout<<ans<<endl;
    }
    return 0;
}


Measured memory_bytes: 3084
MOD = 10 ** 9 + 7
INF = 10 ** 10
import sys
sys.setrecursionlimit(100000000)
dy = (-1,0,1,0)
dx = (0,1,0,-1)

def main():
    a,b,c,d = map(int,input().split())
    i = 0
    while a > 0 and c > 0:
        if i%2 == 0:
            c -= b
            i += 1
        else:
            a -= d
            i += 1
    if i%2 == 0:
        print('No')
    else:
        print('Yes')

if __name__ == '__main__':
    main()

Measured memory_bytes: 9240
class UnionFind():
    '''
    UnionFindでグラフの状態を管理する
    '''
    def __init__(self, n):
        self.n = n
        self.root = [-1]*(n)
        self.rnk = [0]*(n)

    def find_root(self, x):
        '''
        ルートのノードを見つける
        '''
        if(self.root[x] < 0):
            return x
        else:
            self.root[x] = self.find_root(self.root[x])
            return self.root[x]

    def unite(self, x, y):
        '''
        ノード同士を連結する
        '''
        x = self.find_root(x)
        y = self.find_root(y)
        if(x == y):
            return 
        elif(self.rnk[x] > self.rnk[y]):
            self.root[x] += self.root[y]
            self.root[y] = x
        else:
            self.root[y] += self.root[x]
            self.root[x] = y
            if(self.rnk[x] == self.rnk[y]):
                self.rnk[y] += 1

    def is_same_group(self, x, y):
        '''
        同一のルーツを持つかどうか調査する
        '''
        return self.find_root(x) == self.find_root(y)

    def count(self, x):
        return -self.root[self.find_root(x)]

N, M, K = map(int, input().split())
union_find = UnionFind(N)
AB = [[] for _ in range(N)]
for _ in range(M):
    a, b = map(int,input().split())
    a, b = a-1,b-1
    AB[a].append(b)
    AB[b].append(a)
    union_find.unite(a, b)

CD = [[] for _ in range(N)]
for _ in range(K):
    c, d = map(int,input().split())
    c, d = c-1,d-1
    CD[c].append(d)
    CD[d].append(c)

ret = [-1] * N
for i in range(N):
    ret[i] += union_find.count(i)

for i in range(N):
    for a in AB[i]:
        if union_find.is_same_group(i, a):
            ret[i] -= 1
    for c in CD[i]:
        if union_find.is_same_group(i, c):
            ret[i] -= 1

print(*ret, sep=" ")


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

#define COUT(x) cout << #x << " = " << (x) << ", "
typedef long long ll;
const int MOD = 1000000007;

int R,S,P;
int pt(char a){
  if(a == 'r'){
    return P;
  }else if(a == 's'){
    return R;
  }else{
    return S;
  }
}

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

  cin >> R >> S >> P;
  string T;
  cin >> T;
  ll res = 0;
  vector<bool> flag(N, true);
  for(int i = 0; i < N; i++){
    if(i < K) res += pt(T[i]);
    else{
      if(T[i] == T[i-K]){
	if(flag[i-K]){
	  flag[i] = false;
	}else{
	  res += pt(T[i]);
	}
      }else{
        res += pt(T[i]);
      }
    }
  }
  cout << res << endl;
}


Measured memory_bytes: 512
/*Lucky_Glass*/
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

const int N=2e5;

int n,dis,num;
struct MOS{long long hel,pos;}mos[N+3];
bool cmpMOS(MOS A,MOS B){return A.pos<B.pos;}

#define lowbit(x) (x&-x)
long long tre[N+3];
void Modify(int pos,long long add){
    while(pos<=n){
        tre[pos]+=add;
        pos+=lowbit(pos);
    }
}
long long Query(int pos){
    long long res=0;
    while(pos){
        res+=tre[pos];
        pos-=lowbit(pos);
    }
    return res;
}

int main(){
    scanf("%d%d%d",&n,&dis,&num);
    dis<<=1;
    for(int i=1;i<=n;i++) scanf("%lld%lld",&mos[i].pos,&mos[i].hel);
    sort(mos+1,mos+1+n,cmpMOS);
    mos[n+1].pos=(1ll<<60);
    int las=1;
    long long ans=0;
    for(int i=1;i<=n;i++){
        while(las<=i && mos[las].pos+dis<mos[i+1].pos){
            long long atk=Query(las);
            if(atk<mos[las].hel){
                mos[las].hel-=atk;
                // printf("%d = %lld\n",las,mos[las].hel);
                long long tim=(mos[las].hel/num);
                if(mos[las].hel%num) tim++;
                ans+=tim;
                Modify(las,tim*num);
                Modify(i+1,-tim*num);
            }
            las++;
        }
    }
    long long mx=0;
    for(int i=las;i<=n;i++)
        mx=max(mx,mos[i].hel-Query(i));
    ans+=mx/num;
    if(mx%num) ans++;
    printf("%lld\n",ans);
    return 0;
}


Measured memory_bytes: 4864
#include<iostream>
#include<algorithm>
#include<vector>
#include<numeric>
#include<string>
#include<cmath>
#include<set>
#include<queue>
#include<deque>
#include<bitset>
#include<iomanip>
#include<cctype>
#include<map>
#include<cstring>
#include<bitset>
#include<cassert>
 
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define rep2(i,a,b) for (int (i)=a;(i)<(b);(i)++)
#define all(x) (x).begin(),(x).end()
 
using namespace std;
using ll = long long int;
 
const int inf = 1001001000;
const long long int Inf = 1001001001001001000;
 
template<typename T>
void print(vector<T> a){
	for (auto x:a){
		cout << x << " ";
	}
	cout << endl;
}
 
template<typename T>
void print2d(vector<vector<T>> a){
	for (auto v:a){
		for (auto x:v){
			cout << x << " ";
		}
		cout << endl;
	}
}
 
 
 
int main()
{
	string s;

	cin >> s;
	if(s.back()=='s')
		cout << s + "es" << endl;
	else
		cout << s + "s" << endl;
	return 0;
}

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

int main() {
    int a,b,c,res;
    cin>>a>>b>>c;
    res=b/a;
    if (res>c) cout<<c<<endl;
    else cout<<res<<endl;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int mod=1e9+7;
string s;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>s;
    int len=s.length();
    while(len--)
    {

        cout<<"x";
    }
    cout<<'\n';





}




Measured memory_bytes: 256
#include<stdio.h>
#define X 1000000007

long long dist(long long a,long long b){if(a>b){return a-b;}return b-a;}

int main(void){
	long long n,m,x[131072],y[131072],i,p,s=0,t=0,a;
	scanf("%lld%lld",&n,&m);
	for(i = 1;i <= n;i++){scanf("%lld",&x[i]);}
	for(i = 1;i <= m;i++){scanf("%lld",&y[i]);}
	p = 0;
	for(i = 1;i < n;i++){
		a = (p+i*dist(x[i],x[i+1]))%X;
		s+=a;s%=X;
		p = a;
	}
	p = 0;
	for(i = 1;i < m;i++){
		a = (p+i*dist(y[i],y[i+1]))%X;
		t+=a;t%=X;
		p = a;
	}
	printf("%lld\n",(s*t)%X);
	return 0;
}

Measured memory_bytes: 1792
//---------- begin union_find ----------
mod union_find {
    pub struct UF {
        p: Vec<i32>,
    }
    #[allow(dead_code)]
    impl UF {
        pub fn new(n: usize) -> UF {
            UF {p: vec![-1; n] }
        }
        pub fn init(&mut self) {
            for p in self.p.iter_mut() {
                *p = -1;
            }
        }
        pub fn root(&mut self, mut x: usize) -> usize {
            while self.p[x] >= 0 {
                x = self.p[x] as usize;
            }
            x
        }
        pub fn same(&mut self, x: usize, y: usize) -> bool {
            self.root(x) == self.root(y)
        }
        pub fn unite(&mut self, mut x: usize, mut y: usize) {
            x = self.root(x);
            y = self.root(y);
            if x == y {
                return;
            }
            if self.p[x] > self.p[y] {
                let s = x;
                x = y;
                y = s;
            }
            self.p[x] += self.p[y];
            self.p[y] = x as i32;
        }
        pub fn get_size(&mut self, x: usize) -> usize {
            let r = self.root(x);
            (-self.p[r]) as usize
        }
    }
}
//---------- end union_find ----------
//https://qiita.com/tanakh/items/0ba42c7ca36cd29d0ac8
macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
    ($($r:tt)*) => {
        let s = {
            use std::io::Read;
            let mut s = String::new();
            std::io::stdin().read_to_string(&mut s).unwrap();
            s
        };
        let mut iter = s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
}

macro_rules! input_inner {
    ($iter:expr) => {};
    ($iter:expr, ) => {};
    ($iter:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($iter, $t);
        input_inner!{$iter $($r)*}
    };
}

macro_rules! read_value {
    ($iter:expr, ( $($t:tt),* )) => {
        ( $(read_value!($iter, $t)),* )
    };
    ($iter:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($iter, $t)).collect::<Vec<_>>()
    };
    ($iter:expr, chars) => {
        read_value!($iter, String).chars().collect::<Vec<char>>()
    };
    ($iter:expr, usize1) => {
        read_value!($iter, usize) - 1
    };
    ($iter:expr, $t:ty) => {
        $iter.next().unwrap().parse::<$t>().expect("Parse error")
    };
}

//

fn run() {
    input! {
        n: usize,
        m: usize,
        q: usize,
        p: [(usize, usize, u8); q],
    }
    let mut u = union_find::UF::new(n);
    let mut cnt = 0;
    for &(a, b, c) in &p {
        if c == 1 {
            continue;
        }
        if !u.same(a, b) {
            u.unite(a, b);
            cnt += 1;
        }
    }
    for &(a, b, c) in &p {
        if c == 0 {
            continue;
        }
        if u.same(a, b) || m == n - 1 {
            println!("No");
            return;
        }
    }
    let c = n - cnt;
    let max = cnt + c * (c - 1) / 2;
    if max < m {
        println!("No");
    } else {
        println!("Yes");
    }
}

fn main() {
    run();
}


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

char F[102][102];

void DFS(int y, int x, char a){
  if(F[y][x]!=a){
    return;
  }
  F[y][x]='.';

  DFS(y-1,x,a);
  DFS(y,x+1,a);
  DFS(y+1,x,a);
  DFS(y,x-1,a);
}

int main(){
  int n,m;
  while(1){
    cin >> n >> m;
    if(n==0&&m==0){
      return 0;
    }
    for(int y=1; y<=n; y++){
      for(int x=1; x<=m; x++){
        cin >> F[y][x];
      }
    }

    int cnt=0;
    for(int y=1; y<=n; y++){
      for(int x=1; x<=m; x++){
        if(F[y][x]=='#'){
          cnt++;
          DFS(y,x,'#');
        }
        if(F[y][x]=='*'){
          cnt++;
          DFS(y,x,'*');
        }
        if(F[y][x]=='@'){
          cnt++;
          DFS(y,x,'@');
        }
      }
    }
    cout << cnt << endl;
  }

}


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

#define ll long long
#define ull unsigned long long 
#define endl '\n'

int main(){
    int c[3][3];
    for(int i=0; i<3; ++i)
        for(int j=0; j<3; ++j)
            cin >> c[i][j];
        
    
    int a[3], b[3];
    a[0] = 0;
    for(int i=0; i<3; ++i)
        b[i] = c[0][i]-a[0];

    a[1] = c[1][0]-b[0];
    a[2] = c[2][0]-b[0];

    for(int i=0; i<3; ++i){
        for(int j=0; j<3; ++j){
            if(c[i][j] != a[i]+b[j]){
                cout << "No";
                return 0;
            }
        }
    }
    cout << "Yes";
}


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

#define int long long

signed main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int N, M, R;
    cin >> N >> M >> R;
    vector<int> r(R);
    for (int i = 0; i < R; i++) cin >> r[i], r[i]--;
    vector<vector<int>> d(N, vector<int>(N, 1e9));
    for (int i = 0; i < M; i ++) {
        int a, b, c;
        cin >> a >> b >> c;
        a--; b--;
        d[a][b] = c;
        d[b][a] = c;
    }
    // ワーシャルフロイド法
    for (int k = 0; k < N; k++) {
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N;j ++) {
                d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
            }
        }
    }

    int min = 1e9;
    sort(r.begin(), r.end());
    do {
        int sum = 0;
        for (int i = 0; i < R - 1; i ++) {
            sum += d[r[i]][r[i + 1]];
        }
        if (min > sum) {
            min = sum;
        }
    } while(next_permutation(r.begin(), r.end()));

    cout << min << endl;
    return 0;
}

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

using namespace std;
typedef long long ll;

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    string s;
    cin >> s;
    int n=s.size();
    array<int,2> res={-1,-1};
    for(int i=0;i<n;i++)
    {
        if(i+1<n&&s[i]==s[i+1]) res={i+1,i+2};
        if(i+2<n&&s[i]==s[i+2]) res={i+1,i+3};
    }
    cout << res[0] << " " << res[1] << "\n";
    return 0;
}


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

using namespace std;

int ds(int x){
  int ret = 0;
  while(x > 0){
    ret += x % 10;
    x /= 10;
  }
  return ret;
}

int main(void){
  int N;
  cin >> N;
  int ans = 100000;
  for(int A = 1; A < N; A++){
    int B = N - A;
    ans = min(ans, ds(A) + ds(B));
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 256
import java.util.Scanner;


public class Main {

	public static void main(String[] args) {
		// TODO 自動生成されたメソッド・スタブ
		Scanner sc = new Scanner(System.in);

		int N = sc.nextInt();
		int M = sc.nextInt();

		int cnt = 0;

		for(int i = 1; i < N; i++) {
			cnt = cnt + N - i;
		}

		for(int i = 1; i < M; i++) {
			cnt = cnt + M - i;
		}

		System.out.println(cnt);
	}

}

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

int main(){
  long long int n;
  cin >> n;
  
  long long int x=1;
  for(long long int i=1;i<=sqrt(n);i++){
    if(n%i==0){
      x=max(x,i);
    }
  }
  cout << (x-1)+((n/x)-1) << endl;
}

Measured memory_bytes: 256
import bisect,collections,copy,heapq,itertools,math,numpy,string
import sys
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
N = I()
a = LI()
count = 0
a_dict = {}
for i,x in enumerate(a,1):
    a_dict[i] = x
for k,v in a_dict.items():
    if k in [a_dict[v]]:
        count +=1
print(count//2)


Measured memory_bytes: 29596
// 2013/10/22 Tazoe

#include <iostream>
using namespace std;

int A[10];

bool DFS(int I, int B, int C){
	if(I==10)
		return true;

	if(A[I]>B && DFS(I+1, A[I], C))
		return true;

	if(A[I]>C && DFS(I+1, B, A[I]))
		return true;

	return false;
}

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

	for(int i=0; i<N; i++){
		for(int j=0; j<10; j++){
			cin >> A[j];
		}

		if(DFS(0, 0, 0)){
			cout << "YES" << endl;
		}
		else{
			cout << "NO" << endl;
		}
	}

	return 0;
}

Measured memory_bytes: 1152
#include <bits/stdc++.h>	
#define pb push_back
typedef long long ll;
const int inf = 2e9;
using namespace std;


class SameColorPairs {
public:
    vector<string> removePairs(vector<string> board) {
        vector<string> ret;
        int H = board.size(), W = board[0].size();
        for (int i = 0; i < H; ++i)
        for (int j = 1; j < W; ++j)
            if (board[i][j] == board[i][j-1]) {
                ret.push_back(to_string(i) + " " + to_string(j) + " " + to_string(i) + " " + to_string(j-1));
            }
        return ret;
    }
};



template<class T> void getVector(vector<T>& v) {
    for (int i = 0; i < v.size(); ++i)
        cin >> v[i];
}

int main(){
  int n,mi=1000000,sum=0,x;
  scanf("%d%d",&n,&x);
  int aux;
  for (int i = 0; i < n; ++i){
  	scanf("%d",&aux);
  	mi = min(mi,aux);
  	sum+=aux;
  } 

	return !printf("%d",((x-sum)/mi)+n);

}


Measured memory_bytes: 256
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
using ll = int64_t;
#define rep(i,n) for(int i = 0; i < ((int)(n)); i++)   // 0-indexed昇順

int main() {
    int P, Q, R;
    cin >> P >> Q >> R;
    cout << min({P+Q, P+R, Q+R}) << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <array>
#include <list>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <string>
#include <sstream>
#include <algorithm>
#include <random>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <cmath>
#include <cassert>
#include <climits>
#include <bitset>
#include <functional>
#include <iomanip>
#include <random>

#define FOR_LT(i, beg, end) for (int i = (int)(beg); i < (int)(end); i++)
#define FOR_LE(i, beg, end) for (int i = (int)(beg); i <= (int)(end); i++)
#define FOR_DW(i, beg, end) for (int i = (int)(beg); (int)(end) <= i; i--)
#define REP(n)              for (int repeat_index = 0; repeat_index < (int)n; repeat_index++)


using namespace std;

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

	int n; cin >> n;
	vector<int> as(n); for (auto& a : as) cin >> a;
	sort(as.begin(), as.end());
	as.push_back(1000001);

	bitset<1000001> occs;
	int ans = 0;

	FOR_LT(i, 0, n) {
		if (occs[as[i]]) continue;

		int a = as[i];
		if (as[i] != as[i + 1]) ans++;

		int v = a;
		while (v <= 1000000) {
			occs.set(v);
			v += a;
		}
	}

	cout << ans;


	return 0;
}


Measured memory_bytes: 4716
#include<iostream>
#include<string>
#define loop(i,a,b) for(int i=a;i<b;i++)
#define rep(i,a) loop(i,0,a)
using namespace std;

int main(){
	string s[3];
	int cnt[3]={0,0,0};
	rep(i,3)cin>>s[i];
	int now=0;
	while(1){
		if(cnt[now]==s[now].size()){
			cout<<(char)(now+'A')<<endl;
			break;
		}
		int alt=now;
		now=(int)(s[alt][cnt[alt]]-'a');
		cnt[alt]++;
	}
	return 0;
}

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

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

  vector<int> a(n);

  for(int i = 0; i < n; i++){
    cin >> a.at(i);
  }

  int ans = 0;

  for(int i = 0; i < n; i++){
    bool can_see = true;
    for(int j = i - 1; j >= 0; j--){
      if(a.at(i) < a.at(j)){
        can_see = false;
      }
    }

    if(can_see == true){
      ans++;
    }
  }

  cout << ans << endl;
}

Measured memory_bytes: 256
#include<stdio.h>

int main(){
    int N;
    int i;
    int g=0;
    scanf("%d",&N);

    int A[N+1];
    int count=0;
    for(i=0;i<N;i++){
        scanf("%d",&A[i]);
        if(A[i]%2==0){
            g +=1;
        }
        if(A[i]%2==0 && (A[i]%3==0 ||A[i]%5==0)){
            count +=1;
        }
    }
    if(count==g){
        printf("APPROVED");
    }
    else{
        printf("DENIED");
    }
    return 0;
    }





Measured memory_bytes: 128
#include <iostream>
#include <string>
#include <algorithm>
#include <queue>
#include <stack>
#include <map>
using namespace std;

int main(){
  int a, b, x; cin >> a >> b >> x;
  cout << ((a <= x && x <= a+b)? "YES": "NO") << endl;

  return 0;
}


Measured memory_bytes: 256