akhauriyash/Code-Regression huggingface dataset:
#include<iostream>
#include<string>
#include<cstring>
using namespace std;
long long name[5], n;
int main(){
  cin >> n;
  memset(name, 0, sizeof(name));
  for(int i=0; i<n; i++){
    string s;
    cin >> s;
    if(s[0] == 'M') name[0]++;
    else if(s[0] == 'A') name[1]++;
    else if(s[0] == 'R') name[2]++;
    else if(s[0] == 'C') name[3]++;
    else if(s[0] == 'H') name[4]++;
    }
  long long ret = 0;
  for(int i=0; i<5; i++){
    for(int j=i+1; j<5; j++){
      for(int k=j+1; k<5; k++){
        ret += name[i] * name[j] * name[k];
        }
      }
    }
  cout << ret << endl;
  return 0;
  }


Measured memory_bytes: 256
N = int(input())
A = [int(x) for x in input().split()]

for n in range(N-1):
  r = -1
  while r!= 0:
    r = A[n] % A[n+1]
    A[n] = A[n+1]
    A[n+1] = r
  A[n+1] = A[n]

print(A[-1])

Measured memory_bytes: 14252
#include "bits/stdc++.h"
#include <sys/timeb.h>
#include <fstream>

using namespace std;

#define repl(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
#define rep(i,n) repl(i,0,n)
#define replrev(i,a,b) for(int i=(int)(b)-1;i>=(int)(a);i--)
#define reprev(i,n) replrev(i,0,n)
#define repi(itr,ds) for(auto itr=ds.begin();itr!=ds.end();itr++)
#define all(a) a.begin(),a.end()
#define mp make_pair
#define mt make_tuple
#define INF 2000000000
#define INFL 1000000000000000000LL
#define EPS (1e-10)
#define MOD 1000000007
#define PI 3.1415926536
#define RMAX 4294967295

typedef long long ll;
typedef pair<int, int> P;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<bool> vb;
typedef vector<char> vc;
typedef vector<string> vs;
typedef vector<double> vd;
typedef vector<P> vP;
typedef vector<vector<int> > vvi;
typedef vector<vector<bool> > vvb;
typedef vector<vector<ll> > vvll;
typedef vector<vector<char> > vvc;
typedef vector<vector<string> > vvs;
typedef vector<vector<double> > vvd;
typedef vector<vector<P> > vvP;
typedef priority_queue<int, vector<int>, greater<int> > pqli;
typedef priority_queue<ll, vector<ll>, greater<ll> > pqlll;
typedef priority_queue<P, vector<P>, greater<P> > pqlP;
struct Edge {
	int from, to, cost;
	bool operator<(Edge e) {
		return cost < e.cost;
	}
};
typedef vector<Edge> Edges;
typedef vector<Edges> Graph;


int main() {
	int N;
	cin >> N;
	vi a(N);
	int n1 = 0, n2 = 0, n4 = 0;
	rep(i, N) {
		cin >> a[i];
		if (a[i] % 4 == 0)n4++;
		else if (a[i] % 2 == 0)n2++;
		else n1++;
	}
	if (n1 <= n4) {
		cout << "Yes" << endl;
	}
	else if (n2 == 0 && n1 == n4 + 1) {
		cout << "Yes" << endl;
	}
	else {
		cout << "No" << endl;
	}


	return 0;
}

Measured memory_bytes: 640
import java.util.*;

public class Main {
	public static void main (String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int a = sc.nextInt();
		int b = sc.nextInt();
		int c = sc.nextInt();
	    System.out.println(n - a - b + c);
	}
}



Measured memory_bytes: 26208
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <math.h>
#include <iomanip>
#include <cmath>
#include <queue>
#include <stack>
#include <cstdlib>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
#define pie 3.141592653589793238462643383279
#define INF 1000000007
#define ggr getchar(); getchar();return 0;
int gcd(int x, int y) {
	if (y == 0)return x;
	return gcd(y, x%y);
}
int lcm(int x, int y) {
	return x / gcd(x, y)*y;
}

int n, a[100010], b[100010], c[100010];
long long ta;

signed main() {
	cin >> n;
	rep(i, n)cin >> a[i];
	rep(i, n)cin >> b[i];
	rep(i, n)cin >> c[i];
	sort(a, a + n);
	sort(b, b + n);
	sort(c, c + n);
	rep(i, n) {
		ta += ((lower_bound(a, a + n, b[i]) - a)*(n - (upper_bound(c, c + n, b[i]) - c)));
	}
	cout << ta << endl;
	ggr
}

Measured memory_bytes: 1408
#include <stdio.h>

int main(void)
{
  int a, b, c;
  scanf("%d%d%d", &a, &b, &c);
  int max = a;
  if(a < b) max = b;
  if(max < c) max = c;
  printf("%d\n", a+b+c+max*9);
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
#include <math.h>
using namespace std;
int main(){
  int N,A,B,a=0,b=0,c=0;
  cin>>N>>A>>B;
  int P[N];
  for(int i=0;i<N;i++){
    cin>>P[i];
    if(P[i]<=A) a++;
    else if(P[i]>B) c++;
    else b++;
  }
  cout<<min(a,min(b,c))<<endl;
}

Measured memory_bytes: 256
import sys

read = sys.stdin.read
N, M, V, P, *A = map(int, read().split())

A += [10 ** 10]
A.sort(reverse=True)
left = P
right = N + 1
# i番目の問題が採用される可能性があるか否や
e = tuple(enumerate(A))
while right - left > 1:
    mid = (right + left) // 2
    score = A[mid] + M
    if score < A[P]:
        right = mid
        continue
    s = M * (V - P)
    for idx, i in e[P:]:
        if mid == idx:
            continue
        if i + M <= score:
            s -= M
        else:
            s -= score - i

    if s <= 0:
        left = mid
    else:
        right = mid

print(left)


Measured memory_bytes: 18404
#include <stdio.h>

int main( void ) {
	int s1, s2, d, sum[ 2 ] = {};

	while ( scanf( "%d,%d,%d", &s1, &s2, &d ) == 3 ) {
		sum[ 0 ] += s1 * s1 + s2 * s2 == d * d;
		sum[ 1 ] += s1 == s2;
	}

	printf( "%d\n%d\n", sum[ 0 ], sum[ 1 ] );

	return 0;
}

Measured memory_bytes: 596
import java.util.ArrayDeque;
import java.util.Deque;
import java.util.Scanner;

public class Main {
	public static void main(String[]args) {
		try(Scanner scan = new Scanner(System.in)){
			
			int H  = scan.nextInt();
			int W  = scan.nextInt();
			GM[][]map = new GM[H][W];
			for(int i = 0;i<H;i++) {
				String s = scan.next();
				char[]c = new char[s.length()];
				c = s.toCharArray();
				for(int j = 0;j<W;j++) {
					map[i][j] = new GM(c[j],i,j);
				}
			}
			
			int []dx = {0,1,0,-1};
			int []dy = {1,0,-1,0};
			
			Deque<GM>queue = new ArrayDeque<GM>();
			queue.addFirst(map[0][0]);
			map[0][0].se = true;
			
			while(!queue.isEmpty()) {
				GM p = queue.removeLast();
				for(int i = 0;i<4;i++) {
					int x = p.x+dx[i];
					int y = p.y+dy[i];
					if(0<=x&&x<W&&0<=y&&y<H) {
						if(map[y][x].type!='#'&&map[y][x].se ==false) {
							queue.addFirst(map[y][x]);
							map[y][x].se = true;
							map[y][x].kyori = p.kyori+1;
							//map[y][x].sy = p.y;
							//map[y][x].sx = p.x;
						}
					}
					
				}
			}
			
			
			
			
			int X = W-1;
			int Y = H-1;
			map[Y][X].sirusi=1;
			if(map[Y][X].kyori==0) {
				System.out.println(-1);
				System.exit(0);
			}
			
			
			while(true) {
				if(map[Y][X].kyori==0) {
					map[Y][X].sirusi = 1;
					break;
				}
				for(int i = 0;i<4;i++) {
					int x =X+dx[i];
					int y= Y+dy[i];
					if(0<=x&&x<W&&0<=y&&y<H) {
						if(map[Y][X].kyori-map[y][x].kyori==1&&map[y][x].type=='.') { 
							X = x;
							Y = y;
							map[Y][X].sirusi =1;
							break;
						}
					}
				}
				
			}
			
			
			
			/*
			int X = W-1;
			int Y = H-1;
			map[Y][X].sirusi   =1;
			
			while(true) {
				if(Y==0&&X==0) {
					map[Y][X].sirusi = 1;
					break;
				}
				X = map[Y][X].sx;
				Y = map[Y][X].sy;
				map[Y][X].sirusi=1;
			}
			*/
			
			
			int count = 0;
			for(int i = 0;i<H;i++) {
				for(int j = 0;j<W;j++) {
					if(map[i][j].type=='.') {
						if(map[i][j].sirusi==1) {
							//System.out.print(map[i][j].kyori);
							//System.out.print('@');
						}else {
							//System.out.print(map[i][j].kyori);
							//System.out.print('.');
							count++;
						}
					
					}
					//else System.out.print(map[i][j].type);
					
					
					
				}
				//System.out.println();
			}
			
			
			
			
			System.out.println(count);
			
			
			
		}
		
		
	}
	
	
	static class GM{
		int y ;
		int x;
		boolean se;
		char type;
		int kyori = 0;
		int sy;
		int sx;
		int sirusi  =0;
		GM(char s,int Y,int X){
			type = s;y = Y;x = X;
		}
	}
		

}


Measured memory_bytes: 23252
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e6 + 5;
int a[maxn];
int main() {
	int n, x;
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> x;
		a[x] = i;
	}
	for (int i =1 ; i <= n; i++) {
		cout << a[i] << " ";
	}
	return 0;
}

Measured memory_bytes: 1152
import sys
import numpy as np 
from itertools import permutations

I = np.array(sys.stdin.read().split(), dtype=np.int64)
n, C = I[:2]
cost = I[2:2+C**2].reshape(C, C)
color = I[2+C**2:].reshape(n, n) - 1

def main():
    mod_3 = (np.arange(1, n+1)[:, None] + np.arange(1, n+1)) % 3
    c0 = np.bincount(color[mod_3 == 0], minlength=C)
    c1 = np.bincount(color[mod_3 == 1], minlength=C)
    c2 = np.bincount(color[mod_3 == 2], minlength=C)

    ans = float('inf')
    for i, j, k in permutations(range(C), 3):
        res = np.sum(c0 * cost[:, i])
        res += np.sum(c1 * cost[:, j])
        res += np.sum(c2 * cost[:, k])
        ans = min(ans, res)
    return ans

if __name__ == '__main__':
    ans = main()
    print(ans)

Measured memory_bytes: 34912
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
#define int ll
typedef pair<int,int> pii;
#define rep(i,n) for(ll i=0;i<(ll)(n);i++)
#define all(a) (a).begin(),(a).end()
#define pb emplace_back
#define INF (1LL<<60)

#define MAX_V 5000
struct edge{int to, cap, rev;};

vector<edge> G[MAX_V];
int level[MAX_V];
int iter[MAX_V];

void add_edge(int from, int to, int cap){
    G[from].push_back(  (edge){ to  , cap, (int)G[to  ].size()   }  );
    G[to  ].push_back(  (edge){ from, 0  , (int)G[from].size()-1 }  );
}


void bfs(int s){
    rep(i,MAX_V)level[i] = -1;
    queue<int> que;
    level[s] = 0;
    que.push(s);
    while(!que.empty()){
        int v = que.front();
        que.pop();
        rep(i,G[v].size()){
            edge &e = G[v][i];
            if(e.cap>0&& level[e.to]<0){
                level[e.to] = level[v]+1;
                que.push(e.to);
            }
        }
    }
}

int dfs(int v, int t, int f){
    if(v==t)return f;
    for(int &i = iter[v]; i<G[v].size();i++){
        edge &e = G[v][i];
        if(e.cap>0 && level[v]<level[e.to]){
            int d = dfs(e.to, t, min(f,e.cap));
            if(d>0){
                e.cap -= d;
                G[e.to][e.rev].cap += d;
                return d;
            }
        }
    }
    return 0;
}

int max_flow(int s, int t){
    int flow = 0;
    for(;;){
        bfs(s);
        if(level[t]<0) return flow;
        memset(iter, 0, sizeof(iter));
        int f;
        while( (f=dfs(s,t,INF))>0 ){
            flow+=f;
            if(flow>100000000)return -1;
        }
    }
}

signed main(){
    int v,e;
    cin>>v>>e;
    set<pii> edges;
    rep(i,e){
        int s,t,c;
        cin>>s>>t>>c;
        if(c==1){
            edges.insert(pii(s,t));
            add_edge(s,t,4999);
            add_edge(t,s,4999);
        }
        else{
            add_edge(s,t,c*5000);
            add_edge(t,s,c*5000);
        }
    }
    
    int res = max_flow(0,v-1);
    
    if(res==-1){
        cout<<-1<<endl;
        return 0;
    }
    if(res%5000!=0)res-=5000;
    if(res>50000000) cout<<-1<<endl;
    else cout<<(res+4999)/5000<<endl;
}

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

#define rep(i, n) for(long long i=0;i<(long long)(n);i++)
#define rep2(i, s, n) for(long long i=(s);i<(long long)(n);i++)
#define repi(i, n) for(int i=0;i<(int)(n);i++)
#define rep2i(i, s, n) for(int i=(s);i<(int)(n);i++)
#define all(v) v.begin(), v.end()

using ll = long long;
using ld = long double;
using vll = vector<ll>;
using vvll = vector<vll>;
using P = pair<ll, ll>;
using vi = vector<int>;
using vvi = vector<vi>;

const ll INF = (1LL<<60);
const int INFi = (1<<29);

int main(){

    char c;cin >> c;

    if(c>='a') cout << 'a' << endl;
    else cout << 'A' << endl;



    return 0;
}

Measured memory_bytes: 3632
#include <algorithm>
#include <bitset>
#include <climits>
#include <cstring>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <unordered_map>
#include <unordered_set>
#include <vector>

using namespace std;
typedef long long ll;

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

struct Node {
  int x, y, steps;
};

class Solution {
 public:
  void solve() {
    int n, m;
    cin >> n >> m;
    vector<string> maze(n);
    for (int i = 0; i < n; ++i) cin >> maze[i];
    int ans = 0;
    for (int i = 0; i < n; ++i)
      for (int j = 0; j < m; ++j) {
        if (maze[i][j] == '#') continue;
        queue<Node> q;
        vector<vector<bool>> visited(n, vector<bool>(m));
        visited[i][j] = true;
        q.push({j, i, 0});
        while (!q.empty()) {
          Node f = q.front();
          q.pop();
          ans = max(ans, f.steps);
          for (int k = 0; k < 4; ++k) {
            int nx = f.x + dx[k];
            int ny = f.y + dy[k];
            if (nx < 0 || nx >= m || ny < 0 || ny >= n || visited[ny][nx] ||
                maze[ny][nx] == '#')
              continue;
            visited[ny][nx] = true;
            q.push({nx, ny, f.steps + 1});
          }
        }
      }
    cout << ans;
  }
};

int main() {
  Solution solution = Solution();
  solution.solve();
}

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

#define SIZE 100010

int len;
map<int, int> mp;

bool check() {
    if (mp.find(0) != mp.end() && mp[0] == len)
        return true;
    if (len % 3 != 0)
        return false;

    if (mp.size() > 3)
        return false;
    if (mp.size() == 3) {
        auto it1 = mp.begin(), it2 = next(mp.begin()), it3 = prev(mp.end());
        if (it1 -> second == it2 -> second && it2 -> second == it3 -> second) {
            int fst = it1 -> first, snd = it2 -> first, thd = it3 -> first;
            return ((fst ^ snd) == thd || (fst ^ thd) == snd || (snd ^ thd) == fst);
        }
        return false;
    }

    if (mp.size() == 2) {
        auto it1 = mp.begin(), it2 = next(mp.begin());
        return (it1 -> first == 0 && it2 -> second == it1 -> second * 2);
    }

    return false;
}

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

    cin >> len;
    for (int i = 0; i < len; i++) {
        int cnt; cin >> cnt;
        mp[cnt]++;
    }

    cout << (check() ? "Yes\n" : "No\n");
    return 0;
}

Measured memory_bytes: 3840
#include <iostream>
#include <vector>
#include <limits.h>
#include <algorithm>
#include <string>
#include <math.h>
#include <limits.h>
#include <queue>
#include <map>
#include <set>
#include <iomanip>
#include <bitset>
#include <cassert>
#include <random>
#include <functional>
#include <stack>
#include <iomanip>
#include <cassert>
//#include <boost/multiprecision/cpp_int.hpp>
#include <complex>
#include <cstdio>
#include <list>
#include <bitset>

//< in.txt > out.txt
using namespace std;
//std::ios::sync_with_stdio(false);
//std::cin.tie(0);
const long long MOD = 1e9 + 7;
typedef long long LL;
typedef long double LD;
typedef pair<LL, LL> PLL;
typedef pair<LD, LL> pdl;
typedef pair<LD, LD> pdd;
typedef vector<LL> VLL;
typedef vector<VLL> VVLL;
typedef unsigned long long ULL;
//typedef boost::multiprecision::cpp_int bigint;

LL N;
LL calc(LL K) {
	LL n = N;
	while (n >= K) {
		if (n % K == 0) {
			n /= K;
			continue;
		}
		else break;
	}
	return n % K;
}

int main() {
	std::ios::sync_with_stdio(false);
	std::cin.tie(0);
	cin >> N;
	set<LL> s;
	for (LL r = 2; r * r <= N-1; r++) {
		if ((N - 1) % r == 0) {
			s.insert(r);
			s.insert((N - 1) / r);
		}
	}
	s.insert(N - 1);
	for (LL r = 2; r * r <= N; r++) {
		if (N % r != 0)continue;
		if (calc(r) == 1)s.insert(r);
		if (calc(N / r) == 1)s.insert(N/r);
	}
	s.insert(N);
	s.insert(1);
	cout << s.size()-1 << "\n";
	return 0;
}


Measured memory_bytes: 256
N = int(input())

slime = list(map(int, input().split()))
ans = 0 
flag = 0
for s,t in zip (slime[:-1],slime[1:]):
  if flag == 1:
    flag = 0
  else:
    if s == t:
      ans += 1
      flag = 1
      
print(ans)

Measured memory_bytes: 3060
#include<bits/stdc++.h>
using namespace std;
using Graph = vector<vector<int>>;
#define ll long long
#define all(x) (x).begin(),(x).end()
#define rep(i, n) for(ll i = 0; i < n; i++)
const ll INF = 1LL << 60;


vector<bool> seen;
void dfs(Graph &G, int v){
    seen[v] = true;
    for(auto x:G[v]){
        if(seen[x])continue;
        dfs(G, x);
    }
}

int main(){
    int N, M; cin >> N >> M;
    vector<pair<int, int>> edges(M);
    rep(i, M){
        int a, b; cin >> a >> b;
        a--;b--;
        edges[i] = {a, b};
    }
    
    int ans = 0;
    rep(i, M){
        Graph G(N, vector<int>());
        rep(j, M){
            if(i != j){
                G[edges[j].first].push_back(edges[j].second);
                G[edges[j].second].push_back(edges[j].first);
            }
        }
        seen.assign(N, false);
        dfs(G, 0);
        bool res = all_of(all(seen), [](bool x) {return x == true; });
        if(!res) ans++;
    }
    cout << ans << endl;
}

Measured memory_bytes: 3616
/* ABC168_A
    Stuartyg */

#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdbool.h>


int main(void){
        int num; /*nのこと*/
        scanf("%d",&num);
        num%=10; /*10で割った余りがnの1の位*/
        switch(num){
                case 3: /*1の位が3ならbonと出力*/
                        printf("bon\n");
                        break;
                case 0: /*1の位が0，1，6，8ならponと出力*/
                        printf("pon\n");
                        break;
                case 1:
                        printf("pon\n");
                        break;
                case 6:
                        printf("pon\n");
                        break;
                case 8:
                        printf("pon\n");
                        break;
                default: /*1の位がそれ以外ならhonと出力*/
                        printf("hon\n");
                        break;
                }
        return 0;
}


Measured memory_bytes: 1600
#include<stdio.h>
const int MAX_V = 10000;
int main(void){
    int i,k,n,p1,q1;
    int prime[MAX_V+1];
    for(i = 2; i <= MAX_V; i ++){
        prime[i] = 1;
    }
    for(i = 2; i * i <= MAX_V; i ++ ){
        if(prime[i]){
            for(k = 2 * i; k <= MAX_V; k += i){
                prime[k] = 0;
            }
        }
    }
    while(1){
        scanf("%d",&n);
        if(n == 0)break;
        for(i = n; i >= 2; i --){
            if(prime[i] == 1 && prime[i-2] == 1){
                q1 = i;
                p1 = i - 2;
                printf("%d %d\n",p1,q1);
                break;
            }
        }
    }
    return 0;
}

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

def factorization(n):
    arr = set()
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp % i == 0:
            while temp % i == 0:
                temp //= i
            arr.add(i)

    if temp != 1:
        arr.add(temp)

    if not arr:
        arr.add(n)

    return arr

if a == b == 1:
    print(1)
else:
    fa = factorization(a)
    fb = factorization(b)
    res = 1
    for n in fa:
        if n in fb:
            res += 1
    print(res)

Measured memory_bytes: 38768
import java.util.Scanner;

class Main{
  public static void main(String[] args){
    Scanner sc = new Scanner(System.in);
    int[][] A = new int[3][3];
    for(int i = 0; i < 3; i++){
      for(int j = 0; j < 3; j++){
        A[i][j] = sc.nextInt();
      }
    }
    
    int n = sc.nextInt();
    
    int[] b = new int[n];
    for(int k = 0; k < n; k++){
      b[k] = sc.nextInt();
    }
    
    int cnt = 0;
    for(int i = 0; i < 3; i++){
      for(int j = 0; j < 3; j++){
        for(int k = 0; k < n; k++){
          if(A[i][j] == b[k]){
            A[i][j] = 0;
            cnt++;
          }
        }
      }
    }
    
    if(cnt < 3){
      System.out.println("No");
      return;
    }
    
    int virtical = 0;
    int side = 0;
    
    for(int i = 0; i < 3; i++){
      for(int j = 0; j < 3; j++){
        virtical += A[i][j];
        side += A[j][i];
        if(j == 2){
          if(virtical == 0 || side == 0){
            System.out.println("Yes");
            return;
          }else{
            virtical = 0;
            side = 0;
          }
        }
      }
    }
    
    if(A[0][0] + A[1][1] + A[2][2] == 0 || A[2][0] + A[1][1] + A[0][2] == 0){
      System.out.println("Yes");
    }else{
      System.out.println("No");
    }
  }
}


Measured memory_bytes: 22736
#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
#include<list>
#include<vector>
#include<cmath>

using namespace std;

int main(){

    int n;
    cin >> n;

    int a[n], b[n], c[n];
    for(int i=0;i<n;i++)cin >> a[i] >> b[i] >> c[i];

    unsigned long long dp[3][n];
    dp[0][0] = a[0];
    dp[1][0] = b[0];
    dp[2][0] = c[0];

    for(int i=1;i<n;i++){
        dp[0][i] = max(dp[1][i-1],dp[2][i-1])+a[i];
        dp[1][i] = max(dp[0][i-1],dp[2][i-1])+b[i];
        dp[2][i] = max(dp[1][i-1],dp[0][i-1])+c[i];
    }
    unsigned long long ans = max(dp[0][n-1], dp[1][n-1]);
    ans = max(ans, dp[2][n-1]);
    cout << ans << endl;
}


Measured memory_bytes: 3712
#include <bits/stdc++.h>
using ll = long long;
#define FOR(i, k, n) for(ll i = (k); i < (n); i++)
#define FORe(i, k, n) for(ll i = (k); i <= (n); i++)
#define FORr(i, k, n) for(ll i = (k)-1; i > (n); i--)
#define FORre(i, k, n) for(ll i = (k)-1; i >= (n); i--)
#define REP(i, n) FOR(i, 0, n)
#define REPr(i, n) FORre(i, n, 0)
#define ALL(x) (x).begin(), (x).end()
#define ALLr(x) (x).rbegin(), (x).rend()
#define chmin(x, y) x = min(x, y)
#define chmax(x, y) x = max(x, y)
using namespace std;

const int INF = 1001001001;

int main(void){
  ll n , h;
  cin >> n >> h;
  vector<ll> a(n), b(n);
  REP(i, n) cin >> a[i] >> b[i];
  sort(ALLr(a));
  sort(ALLr(b));
  ll ans = 0;
  int i = 0;
  while(b[i] >= a[0] && h > 0){
    h -= b[i];
    i++;
    ans++;
  }
  while(h > 0){
    h -= a[0];
    ans++;
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 1792
import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        // Your code here!
        Scanner sc = new Scanner(System.in);
        int L = sc.nextInt();
        int R = sc.nextInt();
        int d = sc.nextInt();
        int count = 0;
        int x[] = new int[(R-L)+1];
        x[0] = L;
        if(x[0]%d == 0){
            count++;
        }
        for(int i = 1; i < x.length; i++){
            L++;
            x[i] = L; 
            if(x[i]%d == 0){
                count++;
            }
        }
        System.out.println(count);
    }
}


Measured memory_bytes: 35596
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define repI(i, d, n) for (int i = (d); i < (n); ++i)
#define reps1(i, n) for (int i = 1; i < (n); ++i)
using namespace std;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

using ll = long long;
using P = pair<int, int>;
using Pl = pair<ll, ll>;
using M = map<int, int>;
using Ml = map<ll, ll>;
ll const INF = 1ll<<61;
double pi = 3.141592653589793238;

int main() {
  ll x;
  cin >> x;
  x -= 400;

  cout << 8 - x / 200 << endl;

  return 0;
}


Measured memory_bytes: 3632
#include <stdio.h>

int main(void){
  int a,b,c,n,i;

  scanf("%d",&n);

  for(i=0;i<n;i++){
    scanf("%d %d %d",&a,&b,&c);

    if(((a*a)+(b*b)==(c*c))||((a*a)+(c*c)==(b*b))||((c*c)+(b*b)==(a*a))){
      printf("YES\n");
    }else{
      printf("NO\n");
    }
  }
  
  return 0;  
}

Measured memory_bytes: 580
n = int(input())
a = list(map(int, input().split()))
# step 1 後ろからの累積
cum = [0] * (n + 1)
cum[n] = a[n]
for i in range(n):
    cum[n - 1 - i] = cum[n - i] + a[n - 1 - i]
# step2 dpを更新する
# dp はその深さに存在する頂点の数
dp = [0] * (n + 1)
dp[0] = 1
ans = dp[0]
ng = 0
for i in range(n):
    if dp[i] < a[i]:
        ng = 1
    dp[i + 1] = min(2 * (dp[i] - a[i]), cum[i + 1])
    if i < n and dp[i + 1] <= 0:
        ng = 1
    ans += dp[i + 1]
if n == 0:  # この時、a1 まで入っている。
    if a[0] == 1:
        print(1)
    else:
        print(-1)
elif a[n] != dp[n]:
    print(-1)
elif ng:
    print(-1)
else:
    print(ans)
# -1 ではないケースで落ちてる


Measured memory_bytes: 650980
#include<iostream>
#include<algorithm>
#include<stack>
#include<queue>
#include<map>
#include<vector>
using namespace std;
typedef long long llong;

llong N, M, B[100010];
llong A[100010], C[100010];
pair<llong, llong> p[100010];
llong ans = 0;
llong counter = 0;

bool Compare(pair<llong, llong> a, pair<llong, llong> b)
{
	return a.second > b.second;
}

int main()
{
	cin >> N >> M;
	for (llong i = 0; i < N; i++) {
		cin >> A[i];
	}

	for (llong i = 0; i < M; i++) {
		cin >> B[i] >> C[i];
		p[i] = make_pair(B[i], C[i]);
	}

	sort(A, A + N);
	sort(p, p + M, Compare);
	for (llong i = 0; i < M; i++) {

		for (llong j = 0; j < p[i].first; j++) {
			A[counter] = max(A[counter], p[i].second);
			counter++;
			if (counter >= N) break;
		}

		if (counter >= N) break;
	}

	for (llong i = 0; i < N; i++) ans += A[i];
	cout << ans;
	return 0;
}

Measured memory_bytes: 4096
a, b, c, d = map(int, input().split())
mod = 998244353

dp = [[0 for _ in range(d+1)] for _ in range(c+1)]
for i in range(a, c+1):
    for j in range(b, d+1):
        if i == a and j == b:
            dp[i][j] = 1
            continue
        dp[i][j] += dp[i-1][j] * j
        dp[i][j] += dp[i][j-1] * i
        dp[i][j] -= dp[i-1][j-1] * (i-1) * (j-1)
        dp[i][j] %= mod


print(dp[c][d])

Measured memory_bytes: 153384
#include <bits/stdc++.h>
 
 
#define se second
#define sz(x) (int)(x.size())
#define ll long long
#define rep(i,x,y) for(int i = x; i <= y; ++i)
#define repr(i,x,y) for(int i = x; i >= y; --i)
#define pb push_back
#define mp make_pair
#define fi first
#define ull unsigned ll
 
#define pi 3.14159265358979
 
 
using namespace std;
 
const int N = (int)(1e6) + 322;
const ll INF = 2e18 + 17;
const int inf = 2e9;
const int mod = 1000000007;
const double eps = 1e-9;
 
int gcd(int a, int b) { return b ? gcd (b, a % b) : a; }
 
int nbr_bits(int a){
	return log2(a)+1;
}
 
 
int fastpow(int a, int n, int mod) {
    if(n==0)
    	return 1;
    if(n%2==0){
    	int res = fastpow(a,n/2,mod);
    	res*=res;
    	res%=mod;
    	return res;
	}
	int res = (fastpow(a,n-1,mod)*a)%mod;
	return res;
    
}
 
// ---------------------------------------------------
int p[N];
 
int find(int u){
	if(p[u]==u) return u;
	return p[u] = find(p[u]);
}
 

 
 
signed main()
{
 
	ios_base::sync_with_stdio(false);
	
	int n, m, ans = -1;
	cin >> n >> m;
	
	rep(i, 1, n) p[i] = i;
	
	while(m--){
	
	  int a, b;
	  cin >> a >> b;
	  
	  a = find(a);
	  b = find(b);
	  if(a != b) p[a] = b;
	  
	}
	
	 rep(i, 1, n){
	    
	    if( p[i] == i){
	      ans++;
		 }
	    
    }
	
	cout << ans << endl;
	
	
	
	return 0;
}

Measured memory_bytes: 3944
h,w=map(int,input().split())
ans=h*w
if h%3==0 or w%3==0:
  ans=0
else:
  ans=min(h,w)
a=round(h/3)*w
b=(h-round(h/3))*(w//2)
c=h*w-a-b
d=max(a,b,c)-min(a,b,c)
ans=min(ans,d)
a=round(w/3)*h
b=(w-round(w/3))*(h//2)
c=h*w-a-b
d=max(a,b,c)-min(a,b,c)
ans=min(ans,d)
print(ans)

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

int main() {
  int n; cin>>n;
  vector<int64_t> vec(0);
  int array [512345];
  int left=212345, right=left+1;
  for (int i = 0; i < n; i++) {
    int64_t a; cin>>a;
    if (i%2==(n-1)%2) array[left--] = a;
    else array[right++] = a;
  }
  for (int i = left+1;i<right;i++) cout<<array[i]<<" ";
  cout<<endl;
}



Measured memory_bytes: 2944
from collections import deque, defaultdict
import sys
import math

if __name__ == '__main__':
    n = int(input())
    s = defaultdict(int)
    for _ in range(n):
        a, b = input().split()
        if a == 'insert':
            s[b] += 1
        else:
            if s[b]:
                print('yes')
            else:
                print('no')


Measured memory_bytes: 58648
#include <bits/stdc++.h>
#define FOR(i, a, n) for(ll i = (ll)a; i < (ll)n; i++)
#define rep(i, n) FOR(i, 0, n)
#define ALL(x) (x).begin(), (x).end()
using namespace std;
typedef long long ll;

constexpr ll mod = 1e9 + 7;

template <class T> inline bool chmax(T &a, const T b) {
    if(a >= b) return false;
    a = b;
    return true;
}
template <class T> inline bool chmin(T &a, const T b) {
    if(a <= b) return false;
    a = b;
    return true;
}

/*-------------------------------------------*/
// 点
struct Point {
    double x, y;
    Point(double x = 0, double y = 0) : x(x), y(y) {}
    Point operator+(const Point &p) { return Point{x + p.x, y + p.y}; }
    Point operator-(const Point &p) { return Point{x - p.x, y - p.y}; }
    Point operator*(const double k) { return Point{x * k, y * k}; }

    double norm() { return x * x + y * y; }
    double abs() { return sqrt(norm()); }
};

// ベクトル
typedef Point Vector;
double dot(Vector a, Vector b) { return a.x * b.x + a.y * b.y; }
double cross(Vector a, Vector b) { return a.x * b.y - a.y * b.x; }

// 線分
struct Segment {
    Point p1, p2;
};
// 直線
typedef Segment Line;
bool isOrthogonal(Line l1, Line l2) {
    return dot(l1.p1 - l1.p2, l2.p1 - l2.p2) == 0;
}
bool isParallel(Line l1, Line l2) {
    return cross(l1.p1 - l1.p2, l2.p1 - l2.p2) == 0;
}
// 円
struct Circle {
    Point c;
    double r;
    Circle(Point c = Point(), double r = 0) : c(c), r(r) {}
};
// 多角形
typedef vector<Point> Polygon;

int main() {
    int n;
    cin >> n;
    while(n--) {
        Line l1, l2;
        cin >> l1.p1.x >> l1.p1.y >> l1.p2.x >> l1.p2.y;
        cin >> l2.p1.x >> l2.p1.y >> l2.p2.x >> l2.p2.y;
        int ret = 0;
        if(isParallel(l1, l2)) ret = 2;
        if(isOrthogonal(l1, l2)) ret = 1;
        cout << ret << endl;
    }
}


Measured memory_bytes: 3232
n = int(input())
a = [int(input()) for _ in range(n)]
b = [-1]
c = 1


def bi(a, x):
    i, j = 0, len(a) - 1
    while i != j:
        k = (i + j) // 2
        if a[k] >= x:
            i = k+1
        else:
            j = k
    if a[-1] >= x:
        i =-1
    return i


for i in a:
    j = bi(b, i)
    if j == -1:
        b.append(i)
        c += 1
    else:
        b[j] = i
print(c)


Measured memory_bytes: 55000
n,m = map(int,input().split())
student = []
Coodinate = []
for i in range(n):
    student.append(list(map(int,input().split())))
for j in range(m):
    Coodinate.append(list(map(int,input().split())))
ans = []
#print(student)
#print(Coodinate)
for k in student:
    manhattan = 100000000000
    number = 0
    for u in range(m):
        manhattann = abs(k[0]-Coodinate[u][0])+abs(k[1]-Coodinate[u][1])
        if manhattann < manhattan:
            manhattan = manhattann
            number = u+1
    ans.append(number)
for y in ans:
    print(y)

Measured memory_bytes: 3064
import java.util.Scanner

object Main {
  def main(args: Array[String]): Unit = {
    //nextLineとnextを同時に使ったら死ぬ
    val sc = new Scanner(System.in)
    val n = sc.nextInt()
    var acc = 1
    while (acc * 2 <= n) {
      acc *= 2
    }
    println(acc)
  }

  def debug(args: Any*): Unit = {
    Console.err.println(args.mkString(" "))
  }
}


Measured memory_bytes: 25660
#include <iostream>
#include <cmath>
#include <string>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <math.h>
#include <iomanip>
#include <bitset>
#include <cstring>
#include <stdlib.h>
#include <utility>
#include <set>
#include <map>
#include <string.h>
#include <cstring>

long long gcd(long long a, long long b){
    while(b!=0){
        long long r = a%b;
        a=b;
        b=r;
    }
    return a;
}
 
using namespace std;
int main() {
    long long a;
    cin >> a;
    
    int ans=0;
    for(int i=1;i<=a;i++){
        for(int j=1;j<=a;j++){
            for(int k=1;k<=a;k++){
                ans+=gcd(gcd(i, j), gcd(j, k));
            }
        }
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 3600
using System;
using System.Linq;
using System.Collections.Generic;

class P
{
    static void Main()
    {
        long[] abx = Console.ReadLine().Split().Select(long.Parse).ToArray();

        Console.WriteLine(abx[1] / abx[2] - (abx[0] / abx[2] - (abx[0] % abx[2] != 0 ? 0 : 1)));
    }
}

Measured memory_bytes: 13396
#include<string.h>
#include<stdio.h>

int main(){

	int i;
	char str[1200];
	size_t len;

	scanf("%[^\n]", str);

	len = strlen(str);

	for(i = 0; i < len; i++){
		if((str[i] >= 65) && (str[i] <= 90)){
			str[i] += 32;
		} else if((str[i] >= 97) && (str[i]) <=122){
			str[i] -= 32;
		}
	}

	printf("%s\n", str);


	return 0;
}

Measured memory_bytes: 524
#include <iostream>
#include <iomanip>
#include<math.h>
#include<list>
#include <algorithm>
#include<set>
#include<vector>
#include<math.h>
#include<map>
#include<string>
#include <numeric>
#include <queue>
#include <sstream>
#include <bitset>
#include<stack>

using namespace std;
using ll = long long;
using vll = vector<long long>;
using sll = set<long long>;

template<typename T>
T gcd(T a, T b) { return b ? gcd(b, a % b) : a; }
template<typename T>
T lcm(T a, T b) { return a / gcd(a, b) * b; }

template<typename T>
map<T, T> getPrimeFactor(T n) {
	map<T, T> res;
	for (T i = 2; i * i <= n; ++i) {
		while (n % i == 0) {
			res[i] ++;
			n /= i;
		}
	}
	if (n != 1) res[n] = 1;
	return res;
}

template<typename T>
bool IsPrimeNumber(T num)
{
	if (num <= 2) return true;
	else if (num % 2 == 0) return false;

	double sqrtNum = sqrt(num);
	for (int i = 3; i <= sqrtNum; i += 2)
	{
		if (num % i == 0)
		{
			return false;
		}
	}

	return true;
}

long long modinv(long long a, long long m) {
	long long b = m, u = 1, v = 0;
	while (b) {
		long long t = a / b;
		a -= t * b; swap(a, b);
		u -= t * v; swap(u, v);
	}
	u %= m;
	if (u < 0) u += m;
	return u;
}

#define rep(i,s,e) for(ll i=s;i<e;i++)
#define repeq(i,s,e) for(ll i=s;i<=e;i++)




int main() {
	ll N, W;
	std::cin >> N >> W;
	ll w, v;
	vector<vll> t(N + 1, vll(W + 1, 0));
	repeq(i, 1, N) {
		std::cin >> w >> v;
		repeq(j, 1, W) {
			if (w > j) {
				t[i][j] = t[i - 1][j];
			}
			else {
				t[i][j] = max(t[i - 1][j - w] + v, t[i-1][j]);
			}
		}
	}
	std::cout << t[N][W] << endl;


	return 0;
}


Measured memory_bytes: 80256
#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
using namespace std;
bool col[502][502];

inline int read()
{
    int x=0,f=1;char ch=getchar();
    for (;ch<'0'||ch>'9';ch=getchar()) if (ch=='-') f=-1;
    for (;ch>='0'&&ch<='9';ch=getchar()) x=(x<<1)+(x<<3)+ch-'0';
    return x*f;
}

int main()
{
	int n=read(), m=read();
	for (int i=1; i<=n; i++)
	{
		for (int j=1; j<=m; j++)
			{char ch=getchar(); col[i][j]=(ch=='#');}
		getchar();
	}
	for (int i=1; i<=n; i++)
	{
		for (int j=1; j<=m; j++)
			if ((j!=1)&&(col[i][j] || j==m || (i&1))) printf("#"); 
				else printf(".");
		puts("");
	}
	puts("");
	for (int i=1; i<=n; i++)
	{
		for (int j=1; j<=m; j++)
			if ((j!=m)&&(col[i][j] || j==1 || !(i&1))) printf("#"); 
				else printf(".");
		puts("");
	}
	return 0;
}


Measured memory_bytes: 1024
#include <algorithm>
#include <functional>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <vector>
#include <list>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <bitset>
#include <climits>

#define all(c) (c).begin(), (c).end()
#define rep(i,n) for(int i=0;i<(n);i++)
#define pb(e) push_back(e)
#define mp(a, b) make_pair(a, b)
#define fr first
#define sc second

const int INF=100000000;
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};
using namespace std;
typedef pair<int ,int > P;
typedef long long ll;

set<int> S;
int m,n;
string func(int a) {
    if(a%15==0) {
        return "FizzBuzz";
    }
    if(a%3==0) {
        return "Fizz";
    }
    if(a%5==0) {
        return "Buzz";
    }
    stringstream ss;
    ss << a;
    return ss.str();


}
int next(int a) {
    set<int>::iterator it = S.find(a);
    it++;
    if(it==S.end()) it=S.begin();
    return *it;
}
void solve() {
    int now=0;
    S.clear();
    rep(i,m) S.insert(i);
    rep(i,n) {
        string s;
        cin>>s;
        if(S.size()==1) continue;
        int n = next(now);
        if(s != func(i+1)) {
           S.erase(now); 
        }
        now=n;
    }
    bool flag = false;
    for(auto& e : S) {
        if(flag) {
            cout<<" ";
        }
        cout<<e+1;
        flag = true;
    }
    cout<<endl;
}
int main() {
    while(cin>>m>>n) {
        if(m+n==0) break;
        solve();
    }
    
    return 0;
}

Measured memory_bytes: 1280
#include <bits/stdc++.h>
#include <cstdlib>
#include <cmath>
#include <algorithm>
using namespace std;
using ll = long long;
using P = pair<int,int>;
using Graph= vector<vector<int>>; 
#define rep(i,n) for (ll i=0; i < (n); ++i)
#define rep2(i,n,m) for(ll i=n;i<=m;i++)
#define rep3(i,n,m) for(ll i=n;i>=m;i--)
#define pb push_back
#define eb emplace_back
#define ppb pop_back
const ll INF=1e18 ;
inline void chmax(ll& a,ll b){a=max(a,b);}
inline void chmin(ll& a,ll b){a=min(a,b);}
// ミント
const int mod = 998244353;

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

  // for prime mod
  mint inv() const { return pow(mod-2);}
  mint& operator/=(const mint a) { return *this *= a.inv();}
  mint operator/(const mint a) const { return mint(*this) /= a;}
};
istream& operator>>(istream& is, const mint& a) { return is >> a.x;}
ostream& operator<<(ostream& os, const mint& a) { return os << a.x;}
//昆布
struct combination {
  vector<mint> fact, ifact;
  combination(int n):fact(n+1),ifact(n+1) {
    assert(n < mod);
    fact[0] = 1;
    for (int i = 1; i <= n; ++i) fact[i] = fact[i-1]*i;
    ifact[n] = fact[n].inv();
    for (int i = n; i >= 1; --i) ifact[i-1] = ifact[i]*i;
  }
  mint operator()(int n, int k) {
    if (k < 0 || k > n) return 0;
    return fact[n]*ifact[k]*ifact[n-k];
  }
}   ;
 
 mint dp[305][90005] ;
 mint ep[305][90005] ;
int main(){
  ll n ; cin>> n;
  vector<ll> A(n) ;
  rep(i,n) cin>> A[i] ;
  ll sum=0 ;rep(i,n) sum+=A[i] ;
  dp[0][0]=1 ; ep[0][0]=1 ;
  mint ni=2 ;
  rep(i,n){
    rep(j,90005){
      if(j-A[i]<0){
       dp[i+1][j]=ni*dp[i][j] ;
       ep[i+1][j]=ep[i][j] ; 
      }
      else{
      dp[i+1][j]=ni*dp[i][j]+dp[i][j-A[i]] ;
      ep[i+1][j]=ep[i][j]+ep[i][j-A[i]] ;}
    }
  }
  ll half = (sum+1)/2 ;
  mint ans= 0;
  rep2(i,half,sum){
    ans+=dp[n][i] ;
  }
    mint san=3 ;
    ans= ans*san ;
    if(sum%2==0) ans= ans- san*ep[n][half] ;
    mint bns=1 ;
    rep(i,n) bns=bns*san ;
    cout<< bns-ans <<endl;
    return 0;
  }

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

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

int main() {
	long N, C;
	cin >> N >> C;
	
	long ch[C+1][100001]={0};
	
	for(long i=0; i<N; i++){
		long s,t,c;
		cin >>s>>t>>c;
		
	
		ch[c][s]++;
		ch[c][t]++;
		
	}
	
	for(int i=1; i<=C; i++){
		int flag=0;
		for(long k=0; k<100000; k++){
			if(ch[i][k]==2){
				ch[i][k]=1;
			}
			else if(ch[i][k]==1 && flag==0){
				flag=1;
			}else if(ch[i][k]==1 && flag==1){
				flag=0;
				ch[i][k]--;
			}else if(ch[i][k]==0 && flag==1){
				ch[i][k]=1;
			}
		}
		
		for(long j=0; j<100000; j++){
			if(ch[i][j]==0 && ch[i][j+1]==1){ch[i][j]=1;}
		}
	}
	
	long sum[100001]={0};
	for(int i=1; i<=C; i++){
	for(long j=0; j<=100000; j++){
		sum[j]+=ch[i][j];	
	}
	}
	
	long ans=0;
	for(long i=0; i<=100000; i++){
		if(ans < sum[i]){ans=sum[i];}
	}
	
	cout << ans << endl;
	
	return 0;
}

Measured memory_bytes: 25216
# http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1160&lang=jp

import sys
sys.setrecursionlimit(10000)


def dfs(x: int, y: int):
    """dfsで1つの地続きの島を探索
    Parameters
    ----------
        x, y : 探索対称点のxy座標
    """
    seen[x][y] = True
    for i in range(8):
        nx = x + dx[i]
        ny = y + dy[i]
        if (0 <= nx < H
                and 0 <= ny < W
                and seen[nx][ny] is False
                and chart[nx][ny] == 1):
            dfs(nx, ny)


while True:
    try:
        W, H = map(int, input().split())
        if W == 0:
            break
        else:
            chart = []
            for _ in range(H):
                chart.append(list(map(int, input().split())))
            seen = [[False] * W for _ in range(H)]
            dx = [1, 0, -1, 0, 1, 1, -1, -1]
            dy = [0, 1, 0, -1, 1, -1, -1, 1]
            ans = 0
            for i in range(H):
                for j in range(W):
                    # seen=Trueのマスは既に島としてカウントされた故それ以外を探索
                    if seen[i][j] is False and chart[i][j] == 1:
                        dfs(i, j)
                        # dfsで島1つを探索終了した故カウントをインクリメント
                        ans += 1
            print(ans)
    except ValueError:
        break



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


int main() {
    vector<string> result;
    while(1){
        string s;
        cin >> s;
        if(s == "-")break;
        int n;
        cin >> n;
        rep(j,n){
            int t;
            cin >> t;
            s = s.substr(t) + s.substr(0,t);
        }
        result.push_back(s);
    }
    rep(i,result.size())cout << result[i] << endl;
    return 0;
}

/*
やっほい！
　　　　　　　やほほい！
　　　　+　　 　*
　　　 ∧∧　　. ∧∞∧　*
*　ヽ(=´ω｀)人(´ω｀*)ﾉ
　.～（ O x.） （ 　 O)～　+
。*　 　∪　　　　∪
*/


Measured memory_bytes: 3184
from math import sin, cos, sqrt, pi

def polar2euclidean(r, theta):
    x = r * cos(theta)
    y = r * sin(theta)
    return x, y

A, B, H, M = map(int, input().split())
x1, y1 = polar2euclidean(A, -(H * 60 + M) / 720 * 2 * pi)
x2, y2 = polar2euclidean(B, -M / 60 * 2 * pi)
ans = sqrt((x2 - x1) ** 2 + (y2 - y1) ** 2)
print(ans)

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

using namespace std;

#define INF 1000000000
#define pb(a) push_back(a)
#define vi vector<int>
#define vvi vector<vi>
#define P pair<int,int>
#define all(vec) (vec.begin()),(vec.end())
#define ll long long;
#define sz(x) ((int)(x).size())
#define in(x) int x;cin>>x;
#define bit(n) (1<<(n))

#define REP(i, n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define REPR(i, n) for(int i = n;i >= 0;i--)
#define REP3(i, m, n) for(int i = m, i##_len=(n);i < i##_len;i++)
#define FORVEC(i, v) for(int i = 0;i < sz(v);i++)


int main(){
	int n,a,b,ans=0;
	cin>>n>>a>>b;
	//ijkl
	REP(i,10){
		REP(j,10){
			REP(k,10){
				REP(l,10){
					if(i+j+k+l>=a&&i+j+k+l<=b&&i*1000+j*100+k*10+l<=n)ans+=i*1000+j*100+k*10+l;
				}
			}
		}
	}
	if(n==10000&&a==1)ans+=10000;
	cout<<ans<<"\n";
	return 0;
}


Measured memory_bytes: 256
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.io.PrintStream;
import java.io.IOException;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 *
 * @author Spandan
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        InputReader in = new InputReader(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        FDivisionOrSubtraction solver = new FDivisionOrSubtraction();
        solver.solve(1, in, out);
        out.close();
    }

    static class FDivisionOrSubtraction {
        public void solve(int testNumber, InputReader in, PrintWriter out) {
            long n = in.readLong();
            // no of divisors of n-1
            // if k(simulate 2 to sqrt n) divisible by n , add +1

            long  n1 = (n == 2) ? 0 : 1;

            for (long i = 2L; i*i <= (n - 1); i++)
                if ((n - 1) % i == 0) {
                    if (i*i == (n - 1))
                        n1++;
                    else
                        n1 += 2;
                }


            long n2 = 1;
            for (long i = 2L; i*i <= (n); i++) {
                if (n % i == 0) {
                    long tmp = n;
                    while (tmp%i == 0) {
                        tmp /= i;
                    }
                        if (tmp % i == 1) {
                            n2++;
                        }
                }
            }

            System.out.println(n1 + n2);
        }

    }

    static class InputReader {
        private InputStream stream;
        private byte[] buf = new byte[1024];
        private int curChar;
        private int numChars;

        public InputReader(InputStream stream) {
            this.stream = stream;
        }

        public int read() {
            if (numChars == -1)
                throw new RuntimeException();
            if (curChar >= numChars) {
                curChar = 0;
                try {
                    numChars = stream.read(buf);
                } catch (IOException e) {
                    throw new RuntimeException();
                }
                if (numChars <= 0)
                    return -1;
            }
            return buf[curChar++];
        }

        public long readLong() {
            int c = read();
            while (isSpaceChar(c))
                c = read();
            int sgn = 1;
            if (c == '-') {
                sgn = -1;
                c = read();
            }
            long res = 0;
            do {
                res *= 10;
                res += c - '0';
                c = read();
            } while (!isSpaceChar(c));
            return res * sgn;
        }

        public boolean isSpaceChar(int c) {
            return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
        }

    }
}



Measured memory_bytes: 22996
#include<stdio.h>
int main(void){
    int A[4][13],a,b,c,d,e,f,x,y;
    char C,D;
    for(a=0;a<4;a++){
        for(d=0;d<13;d++){
            A[a][d]=1;
        }
    }
    scanf("%d",&c);
    for(y=0;y<c;y++){
        scanf(" %c %d",&C,&b);

        if(C=='S'){
            x=0;
        }else if(C=='H'){
            x=1;
        }else if(C=='C'){
            x=2;
        }else{
            x=3;
        }
        A[x][b-1]=0;
    }
    for(e=0;e<4;e++){
        for(f=0;f<13;f++){

            if(A[e][f]==1){
                    if(e==0){
                        D='S';
                    }else if(e==1){
                        D='H';
                    }else if(e==2){
                        D='C';
                    }else{
                        D='D';
                    }
                printf("%c %d\n",D,f+1);
            }
        }

    }
return 0;
}

Measured memory_bytes: 596
import java.util.Scanner;

	public class Main{

		public static void main(String[] args){

			Scanner sc = new Scanner(System.in);
			String chara = sc.next();
			if(Character.isLowerCase( chara.charAt(0))){
				System.out.println("a");
			}else{
				System.out.println("A");
			}
			}
}


Measured memory_bytes: 26884
nums = list(map(int, input().split()))
nums = sorted(nums)

def is_even(n):
  if n % 2 == 0:
    return True
  else:
    return False

def f(a,b,c_max):
  return (2 * c_max - a - b) // 2

num_even = sum(1 for n in nums if is_even(n))

if num_even == 0 or num_even == 3:
  result = f(*nums)
elif num_even == 1:
  if is_even(nums[2]):
    result = f(nums[0]+1, nums[1]+1, nums[2]) + 1
  else:
    result = f(nums[0], nums[1], nums[2]+1)+1
elif num_even == 2:
  if not is_even(nums[2]):
    result = f(nums[0]+1, nums[1]+1, nums[2]) + 1
  else:
    result = f(nums[0], nums[1], nums[2]+1)+1

print(result)

Measured memory_bytes: 3064