akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
 
#define REP(i,n) for(int i=0; i < (n); ++i)
#define REPR(i,n) for(int i=(n); i >=0; --i)
#define FOR(i, m, n) for(int i = (m); i < (n); ++i)
 
typedef long long ll;
#define INF 1e9
 
 
int main(){
   double W, H, x, y;
   cin >> W >> H >> x >> y;
   double ans = W * H /2;
   
   if((x*2 == W) && (y*2 == H)){
      //printf("%.11f 1\n", ans);
      cout << ans << " "<< 1 << endl;
   }
   else{
      //printf("%.11f 0\n", ans);
      cout << ans << " " << 0 << endl;
   }

   return 0;
}


Measured memory_bytes: 256
s = input()
sets = set()
for v in s:
    sets.add(v)
    
ans = "Yes"
if "N" in sets and "S" not in sets:
    ans = "No"
if "S" in sets and "N" not in sets:
    ans = "No" 
if "E" in sets and "W" not in sets:
    ans = "No" 
if "W" in sets and "E" not in sets:
    ans = "No"    
print(ans)

Measured memory_bytes: 3060
// -----------------------------------
// Author     : MatsuTaku
// Country    : Japan
// Created    : 05/03/20 20:34:41
// -----------------------------------

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

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

  int n,m; cin>>n>>m;
  vector<int> H(n); for (auto& h:H) cin>>h;
  vector<int> graph[n];
  for (int i = 0; i < m; i++) {
    int a,b; cin>>a>>b; a--; b--;
    graph[a].push_back(b);
    graph[b].push_back(a);
  }
  int ans = 0;
  for (int i = 0; i < n; i++) {
    bool res = true;
    for (auto t:graph[i]) {
      res &= H[i] > H[t];
    }
    ans += res;
  }
  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 8760
#include <iostream>
#include <vector>
//#include <numeric>
//#include <algorithm>
using namespace std;

typedef vector<long long> Vl;

int main() {
	int N, M, x=0;

	cin >> N >> M;

	vector<int> L(M+1), R(M+1);

	for(int i=1; i<=M; i++){
		cin >> L[i] >> R[i];

	}


	int cc = N, a, b;

	a=L[1];
	b=R[1];
	for(int j=1; j<=M; j++){
		a=max(a, L[j]);
		b=min(b, R[j]);
//		if(!(L[j] <= i && i <= R[j])){
//			--cc;
//			break;
//		}
	}
//
//	for(int i=1; i<=N; ++i){
//		for(int j=1; j<=M; j++){
//			if(!(L[j] <= i && i <= R[j])){
//				--cc;
//				break;
//			}
//		}
//	}
//
//
//	for(int i=1; i<=N; ++i){cout << i << " " << ok[i] << endl;}
	cout << max(b-a+1, 0) << endl;
//	cout <<  cc << endl;

	return 0;
}


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

using namespace std;
using VI = vector<int>;
using VPI = vector<pair<int, int>>;
using LL = long long;

#define FOR(a,n) for(int i=a;i<n;i++)
#define rFOR(a,n) for(int i=n-1;i>=a;i--)
#define IN(n,a) for(int i=0;i<n;i++) cin>>a[i]
#define pIN(n,t) for(int i=0;i<n;i++){int a,b; cin>>a>>b; t.emplace_back(a,b);}
#define SORT(a) sort(a.begin(), a.end())
#define ALL(a) a.begin(), a.end()

int main()
{
	int n;
	string s, t, ans;
	cin >> n;
	cin >> s >> t;

	FOR(0, n)
	{
		ans += s[i];
		ans += t[i];
	}

	cout << ans << endl;
}

Measured memory_bytes: 256
def paintable(grid, rows, columns):
    def isolated(r, c):
        if r > 0 and grid[r-1][c] == '#':
            return False
        if r < rows - 1 and grid[r+1][c] == '#':
            return False
        if c > 0 and grid[r][c-1] == '#':
            return False
        if c < columns - 1 and grid[r][c+1] == '#':
            return False
        return True

    for r in range(rows):
        for c in range(columns):
            if grid[r][c] == '#' and isolated(r, c):
                return False
    return True
            

if __name__ == '__main__':
    h, w = map(int, input().split())
    grid = [list(input()) for _ in range(h)]
    if paintable(grid, h, w):
        print('Yes')
    else:
        print('No')

Measured memory_bytes: 3064
#include <stdio.h>
 
int main(){
   	
   	long long a,b,c,d;
   	scanf("%lld %lld %lld %lld",&a,&b,&c,&d);
   	long long num1,num2,num3,num4;
   	num1 = a * c;
   	num2 = a * d;
   	num3 = b * c;
   	num4 = b * d;
   	long long max = num1;
   
   	if ( num2 > max ){
   		max = num2;
	   }
	   if( num3 > max){
	   	max = num3;
	   }
	    if( num4 > max){
	   	max = num4;
	   }
	   printf("%lld",max);
   	
    return 0;
}

Measured memory_bytes: 1704
#include <bits/stdc++.h>
using namespace std;
#define MOD 1000000007
#define ll long long

int main() {
	ll S;
	cin >> S;
	ll X = sqrt(S), C;
	if (X*X > S)
		X--;
	if (X*X == S) {
		cout << 0 << " " << 0 << " "
			<< X << " " << 0 << " "
			<< 0 << " " << X << endl;
	}
	else {
		C = X*(X + 1);
		if (C < S) {
			C = (X + 1) * (X + 1) - S;
			cout << 0 << " " << 0 << " "
				<< X + 1 << " " << 1 << " "
				<< C << " " << X + 1 << endl;
		}
		else {
			C -= S;
			cout << 0 << " " << 0 << " "
				<< X << " " << 1 << " "
				<< C << " " << X + 1 << endl;
		}
	}
}

Measured memory_bytes: 256
#include <algorithm>
#include <bitset>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <fstream>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>

using namespace std;

typedef long long ll;
typedef pair<int,int> PP;

/*
 freopen("input","r",stdin);
 freopen("output","w",stdout);
*/

ll W[110];
ll V[110];
ll DP[100010];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int N, w;
    cin >> N >> w;
    memset(DP, 0, sizeof(DP));
    for (int i = 0;i < N;i++) cin >> W[i] >> V[i];
    ll ans = 0;
    for (int i = 0;i < N;i++) {
        for (int j = w;j >= 0;j--) {
            if (W[i] + j <= w) {
                DP[W[i] + j] = max(DP[W[i] + j], DP[j] + V[i]);
                ans = max(ans, DP[W[i] + j]);
            }
        }
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 1024
#include <cstdio>
#include <queue>
#include <algorithm>
#include <cstring>
#include <utility>
#define INF 2000
using namespace std;
typedef pair<int,int> P;

struct data{
	int x,y,c,dc;
	data(int xx,int yy,int cc,int dd){
		x=xx;
		y=yy;
		c=cc;
		dc=dd;
	}

	bool operator<(const data& d1)const{
		return d1.dc<dc;
	}
};

int h,w;

int fie[61][61];
int dx[4]={0,1,0,-1};
int dy[4]={1,0,-1,0};
int dp[61][61][901];
int cost[61][61][4];
int used[61][61];

int bfs(int sx,int sy){
	queue<P> que;
	que.push(P(sx,sy));
	memset(used,-1,sizeof(used));
	used[sx][sy]=0;
	while(que.size()){
		P q=que.front();
		que.pop();
		int x=q.first,y=q.second;
		if(x==(w-1)*2 && y==(h-1)*2)return used[x][y];
		for(int i=0;i<4;i++){
			int nx=x+dx[i],ny=y+dy[i];
			if(nx>=0 && nx<w*2-1 && ny>=0 && ny<h*2-1){
				if(fie[nx][ny]==1)continue;
				nx+=dx[i];
				ny+=dy[i];
				if(used[nx][ny]==-1){
					used[nx][ny]=used[x][y]+1;
					que.push(P(nx,ny));
				}
			}
		}
	}
	return INF;
}

int dijk(){
	priority_queue<data> que;
	que.push(data(0,0,0,0));
	for(int i=0;i<=60;i++){
		for(int j=0;j<=60;j++){
			for(int k=0;k<=900;k++){
				dp[i][j][k]=INF;
			}
		}
	}
	que.push(data(0,0,0,0));
	dp[0][0][0]=0;
	while(que.size()){
		data d=que.top();
		que.pop();
		if(dp[d.x][d.y][d.c]!=d.dc)continue;
		if(d.x==(w-1)*2 && d.y==(h-1)*2)return d.dc;
		//printf("%d %d %d %d\n",d.x,d.y,d.c,d.dc);
		for(int i=0;i<4;i++){
			if(cost[d.x][d.y][i]==INF)continue;
			int nx=d.x+dx[i]*2,ny=d.y+dy[i]*2;
			if(nx>=0 && nx<w*2-1 && ny>=0 && ny<h*2-1){
				if(fie[nx-dx[i]][ny-dy[i]]==1)continue;
				int ndc=max(d.dc,cost[d.x][d.y][i]+d.c);
				if(dp[nx][ny][d.c+1]>ndc && d.c<900){
					dp[nx][ny][d.c+1]=ndc;
					que.push(data(nx,ny,d.c+1,ndc));
				}
			}
		}
	}

	return -1;
}

int main(void){
	while(1){
		scanf("%d %d",&h,&w);
		if(h==0 && w==0)break;
		memset(fie,0,sizeof(fie));
		for(int i=0;i<2*h-1;i++){
			if(i%2==0){
				for(int j=0;j<w-1;j++){
					scanf("%d",&fie[j*2+1][i]);
				}
			}else{
				for(int j=0;j<w;j++){
					scanf("%d",&fie[j*2][i]);
				}
			}
		}
		for(int i=0;i<2*h-1;i+=2){
			for(int j=0;j<w*2-1;j+=2){
				for(int k=0;k<4;k++){
					int x=j+dx[k],y=i+dy[k];
					if(x>=0 && x<w*2-1 && y>=0 && y<h*2-1){
						if(fie[x][y]==0){
							fie[x][y]=1;
							cost[j][i][k]=bfs(j,i);
							fie[x][y]=0;
						}else cost[j][i][k]=INF;
					}else cost[j][i][k]=INF;
				}
			}
		}
		printf("%d\n",dijk());
	}
	return 0;
}

Measured memory_bytes: 14296
#include <bits/stdc++.h>
#define REP(i, n) for (int i = 0; i < (int)(n); i++)
using namespace std;
template<class T>inline bool chmax(T &a, const T &b){if(a < b){a = b; return 1;}return 0;}
template<class T>inline bool chmin(T &a, const T &b){if(a > b){a = b; return 1;}return 0;}
typedef long long ll;
 
int main(){
  ios::sync_with_stdio(false);
  cin.tie(0);
  int R; cin >> R;
  const double PI = 3.1415926535;
  cout << fixed << setprecision(10) << 2*PI*R << endl;
}

Measured memory_bytes: 3776
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=505;
int f[505][505],sum[2][505][505];
int calc(int type,int x1,int y1,int x2,int y2){
	return sum[type][x2][y2]-sum[type][x1-1][y2]-sum[type][x2][y1-1]+sum[type][x1-1][y1-1];
}
int a[505][505];
void add(int &x,int y){
	x=min(x,y);
}
signed main(){
	int n;
	cin>>n;
	for(int i=1;i<=n;++i)
		for(int j=1;j<=n;++j){
			if(i==j) continue;
			cin>>a[i][j];
		}
	for(int i=1;i<=n;++i)
		for(int j=1;j<=n;++j){
			sum[0][i][j]=sum[0][i-1][j]+sum[0][i][j-1]-sum[0][i-1][j-1]+(i<j?a[i][j]:0);
			sum[1][i][j]=sum[1][i-1][j]+sum[1][i][j-1]-sum[1][i-1][j-1]+(i>j?a[i][j]:0);
		}
	memset(f,0x3f,sizeof(f));
	f[0][0]=0;
	for(int i=0;i<=n;++i)
		for(int j=0;j<=i;++j)
			for(int k=i+1;k<=n;++k)
				add(f[k][i],f[i][j]+calc(0,i+1,i+1,k,k)+calc(1,i+1,1,k,j));
	int ans=1e18;
	for(int i=0;i<n;++i)
		add(ans,f[n][i]);
	cout<<ans;
	return 0;
}

Measured memory_bytes: 11532
s=input()
ans1=False
if s[0]=="A":
    ans1=True
ans2=False
x=len(s)
for i in range(2,len(s)-1):
    if s[i]=="C":
        ans2=True
        x=i
        break
ans3=(s[1:x]+s[x+1:]).islower()
#print(ans1,ans2,ans3)
if ans1 and ans2 and ans3:
    print("AC")
else:
    print("WA")

Measured memory_bytes: 3188
#include <iostream>
#include <algorithm>
#include <queue>

using namespace std;

int main(){
    int K;
    cin >> K;
    queue<long> q;
    for(int i=1; i<10; i++) q.push(i);
    long cur;
    for(int i=0; i<K; i++){
        cur = q.front(); q.pop();
        int d = cur % 10;
        if(d != 0) q.push(cur * 10 + d - 1);
        q.push(cur * 10 + d);
        if(d != 9) q.push(cur * 10 + d + 1);
    }
   cout << cur << endl;
   return 0; 
}

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

drink = []
for i in range(n):
    a, b = map(int, input().split())
    drink.append((a, b))

drink.sort(reverse=True)

ans = 0
while m > 0:
    a, b = drink.pop()
    if m > b:
        ans += a * b
        m -= b
    else:
        ans += a * m
        m = 0

print(ans)


Measured memory_bytes: 16892
def run(N, K, R, S, P, T):
    ans = 0
    main = ''
    for i in range(len(T)):
        t = T[i]
        if i < K:
            if t == 'r':
                ans += P
                main += 'p'
            elif t == 's':
                ans += R
                main += 'r'
            elif t == 'p':
                ans += S
                main += 's'
        else:
            pre_t = main[i - K]
            if t == 'r' and pre_t != 'p':
                ans += P
                main += 'p'
            elif t == 's' and pre_t != 'r':
                ans += R
                main += 'r'
            elif t == 'p' and pre_t != 's':
                ans += S
                main += 's'
            else:
                main += ' '
    return ans


def main():
    N, K = map(int, input().split())
    R, S, P = map(int, input().split())
    T = input()
    print(run(N, K, R, S, P, T))


if __name__ == '__main__':
    main()


Measured memory_bytes: 3444
s=input()
fo=s[0:2]
la=s[2:]
n=int(fo)
m=int(la)
a=(n<13) and (n>0)
b=(m<13) and (m>0)
ans='NA'
if a and b:
  ans='AMBIGUOUS'
elif a and not b:
  ans='MMYY'
elif not a and b:
  ans='YYMM'
else:
  ans='NA'
print(ans)

Measured memory_bytes: 3064
#!/usr/bin/perl
#A - AtCoder Beginner Contest 999

use strict;
use warnings;

# データ取得
our ($data);

    {
        $data = <STDIN>;
        chomp($data);
    }

    # 置き換え 1をaに変換する。
    # g忘れてた
    $data =~ s/1/a/g;
    $data =~ s/9/1/g;
    $data =~ s/a/9/g;

print("$data\n");

exit(0);


Measured memory_bytes: 640
import sys
import math
n, h = [int(i) for i in sys.stdin.readline().split()]
a_ls = []
b_ls = []
for i in range(n):
    a, b = [int(i) for i in sys.stdin.readline().split()]
    a_ls.append(a)
    b_ls.append(b)
a_ls.sort()
b_ls.sort()
cnt = 0
_sum = 0
for b in b_ls[::-1]:
    if b < a_ls[-1]:
        break
    _sum += b
    cnt += 1
    if _sum >= h:
        break
cnt += math.ceil(max(0, h - _sum) / a_ls[-1])
print(cnt)

Measured memory_bytes: 53980
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;

int main(){

    ll imos[501][501] = {};
    ll N, M, Q;
    cin >> N >> M >> Q;
    for(ll i = 0; i < M; i++){
        ll l, r;
        cin >> l >> r;
        imos[l][r]++;
    }
    for(ll y = 1; y <= 500; y++){
        for(ll x = 1; x <= 500; x++){
            imos[y][x] += imos[y][x - 1];
        }
    }
    for(ll x = 1; x <= 500; x++){
        for(ll y = 1; y <= 500; y++){
            imos[y][x] += imos[y - 1][x];
        }
    }
    for(ll i = 0; i < Q; i++){
        ll p, q;
        cin >> p >> q;
        cout << imos[q][q] - imos[p - 1][q] - imos[q][p - 1] + imos[p - 1][p - 1] << endl;
    }

    return 0;
}


Measured memory_bytes: 2944
#include<stdio.h>
int main()
{
	int a,b,c,d,e;
	scanf("%d%d",&a,&b);
c=a+b;
d=a*b;
e=a-b;
if(c>d)
{
	if(c>e)
printf("%d",c);
else
printf("%d",e);
}
else if(d>e)
     printf("%d",d);
     else
     printf("%d",e);
return 0;
}     






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

long long factorial(int N) {
  int n = 0;
  while(N>0) {
    n *= N;
    N--;
  }
  return n;
}

int main() {
  int N; cin >> N;
  vector<int> x(N), y(N);
  rep(i, N) {
    cin >> x[i];
    cin >> y[i];
  }
  
  double ans = 0;
  
  rep(i, N) {
    rep(j, N) {
      ans += sqrt(pow(x[i]-x[j],2)+pow(y[i]-y[j],2));
    }
  }
  
  ans = ans /N;
  
  cout << fixed << setprecision(10) << ans << endl;

}

Measured memory_bytes: 256
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

n, k = map(int, readline().split())
v = list(map(int, readline().split()))
ans = -float('inf')
nk = min(n, k)
for a in range(nk + 1):
    for b in range(nk - a + 1):
        vv = v[:a] + v[n - b:]
        if k - a - b >= 0:
            vv.sort()
            cnt = 0
            for check in vv[:k - a - b]:
                if check >= 0:
                    break
                cnt += check
            ans = max(ans, sum(vv) - cnt)
print(ans)


Measured memory_bytes: 3064
#include<iostream>
#include<set>
#include<vector>
#include<cmath>
#include<complex>
#include<string>
#include<algorithm>
 
using namespace std;
 
#define rep(i,n) for(int i=0;i<n;i++)
#define pb push_back
 
typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef vector<vi> vvi;
 
 
int main(void)
{
  int a,b,c;
  cin >> a >> b >> c;
 
  if((a+b)>=c){
    cout << "Yes" << endl;
    return 0;
  }
 
  cout << "No" << endl;
 
 
  return 0;
}

Measured memory_bytes: 256
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef pair<int, int> pi;
#define debug(x) cerr << #x << ": " << x << endl;
#define debug2(x, y) debug(x) debug(y);
#define repn(i, a, b) for(int i = (int)(a); i < (int)(b); i++)
#define rep(i, a) for(int i = 0; i < (int)(a); i++)
#define all(v) v.begin(), v.end() 
#define mp make_pair
#define pb push_back
#define lb lower_bound
#define ub upper_bound
#define fi first
#define se second
#define sq(x) ((x) * (x))

template<class T> T gcd(T a, T b){ return ((b == 0) ? a : gcd(b, a % b)); }

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	//freopen("input.in", "r", stdin);
	//freopen("output.out", "w", stdout);
	int x, a, b;
	cin >> x >> a >> b;
	cout << (x - a) % b << endl;
	return 0;
}
/*
Things to look out for:
	- Integer overflows
	- Array bounds
	- Special cases
Be careful!
*/


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int n;
int main() {
    cin >> n;
    vector<long long> a(n, 0);
    for(int i = 0; i < n; ++i) cin >> a.at(i);

    sort(a.begin(), a.end());
    a.push_back(0);
    int cnt = 0;
    long long no = a.at(0);
    int len = 1;
    for(int i = 1; i <= n; ++i) {
        if(no != a.at(i)) {
            if(len < no) {
                cnt += len;
            }else if(len > no) {
                cnt += len-no;
            }
            no = a.at(i);
            len = 1;
        }else {
            len++;
        }
    }
    cout << cnt << endl;
}

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

using namespace std;
using namespace std;

#define ll long long
#define ull unsigned long long
#define PI acos(-1.0)
#define eps 1e-12
#define fi first
#define se second
#define MEM(a,b) memset((a),(b),sizeof(a))
#define mod(x) ((x)%MOD)
#define pii pair

const int maxn = 4e5 + 10, INF = 0x3f3f3f3f;
const ll MOD = 1000000007LL;
const int Move[4][2] = {-1,0,1,0,0,1,0,-1};
const int Move_[8][2] = {-1,-1,-1,0,-1,1,0,-1,0,1,1,-1,1,0,1,1};


int a[maxn];

int main()
{
// freopen("C:\Users\Administrator\Desktop\in.txt","r",stdin);
// freopen("C:\Users\Administrator\Desktop\out.txt","w",stdout);
    int n;
    cin>>n;
    for(int i = 1; i <= n; i++)
    {
        int x;
        cin>>x;
        a[x] = i;
    }
    int res = 1;
    int t = 1;
    for (int i = 2; i <= n; i++)
    {
        if (a[i] > a[i - 1])
        {
            t++;
        }
        else
        {
            res = max(res, t);
            t = 1;
        }
    }
    res = max(res, t);
    cout<<n - res<<endl;

    return 0;
}


Measured memory_bytes: 1024
//Best Pizza
#include <iostream>
#include <algorithm>

using namespace std;

int main() {
    int N, A, B, C;
    cin >> N >> A >> B >> C;
    int D[N];
    for(int i = 0; i < N; i++) {
        cin >> D[i];
    }

    sort(D, D + N, greater<int>());

    int cal = C, p = C / A;
    for(int i = 0; i < N; i++) {
        cal += D[i];
        if(cal / (A + B * (i + 1)) >= p) {
            p = cal / (A + B * (i + 1));
            continue;
        }
        break;
    }

    cout << p << endl;

    return 0;
}


Measured memory_bytes: 3152
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define F first
#define S second
#define pii pair<int, int>
#define eb emplace_back
#define all(v) v.begin(), v.end()
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define rep3(i, l, n) for (int i = l; i < (n); ++i)
#define sz(v) (int)v.size()
#define inf (int)(1e9+7)
#define abs(x) (x >= 0 ? x : -(x))
#define ceil(a, b) a / b + !!(a % b)
template<typename T1, typename T2> inline void chmin(T1 &a, T2 b) { if (a > b) a = b; }
template<typename T1, typename T2> inline void chmax(T1 &a, T2 b) { if (a < b) a = b; }
// template<typename T> T pow(T a, int b) { return b ? pow(a * a, b / 2) * (b % 2 ? a : 1) : 1; }
template<typename T> T gcd(T a, T b) { if (b == 0) return a; return gcd(b, a % b); }


// 約数の列挙 O(√n)
template <typename T>
vector<T> all_divisor_catch(T n) {
    vector<T> res;
    for (T i = 1; i * i <= n; i++) {
        if (n % i == 0) {
            res.push_back(i);
            if (i != n / i) res.push_back(n / i);
        }
    }
    return res;
}

vector<pair<ll, int> > prime_factorize(ll n) { // n <= 10^12も考慮
    ll tmp = n;
    vector<pair<ll, int> > v;
    for (ll i = 2; i * i <= n; ++i) {
        ll cnt = 0;
        while (tmp % i == 0) {
            tmp /= i;
            cnt++;
        }
        if (cnt) v.eb(i, cnt);
    }
    if (tmp != 1) v.eb(tmp, 1);
    return v;
}


int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    /*
    int n;
    cin >> n;
    vector<int> a(n);
    rep(i, n) cin >> a[i];
    */
    
    /*
    int a, b, c;
    cin >> a >> b >> c;
    */
    
    /*
    int n;
    cin >> n;
    string s;
    cin >> s;
    */
    
    /*
    int n;
    cin >> n;
    int k;
    cin >> k;
    */
    
    ll a, b;
    cin >> a >> b;
    ll tmp = gcd(a, b);
    // cout << tmp << endl;
    
    auto v = all_divisor_catch(tmp);
    // rep(i, sz(v)) cout << v[i] << " "; cout << endl;
    
    set<ll> s;
    rep(i, sz(v)) {
        auto vv = prime_factorize(v[i]);
        rep(j, sz(vv)) {
            if (s.find(vv[j].S) != s.end()) {
                break;
            }
        }
        rep(j, sz(vv)) {
            s.insert(vv[j].F);
        }
    }
    // for (auto e : s) cout << e << " "; cout << endl;
    cout << sz(s) + 1 << endl;
}


Measured memory_bytes: 384
// finish date: 2018/01/22
#include <iostream>
#include <cmath>
#include <vector>
#include <bitset>
#include <algorithm>
#include <stack>
#include <map>
#include <climits>

using namespace std;

#define FOR(i, a, b) for(int (i)=a;(i)<(b);(i)++)
#define rep(i, n)  FOR(i,0,n)
#define ll long long
#define bigmod 1000000007
#define INF 500000000

vector<vector<int>> table;
int K;

int calc(int i, int j) {
    int sum = 0;
    if (i + K - 1 >= 2 * K) {
        sum += table[(i + K - 1) % (2 * K)][min(j + K - 1, 2 * K - 1)];
        if (j > 0) sum -= table[(i + K - 1) % (2 * K)][j - 1];
    }
    if (j + K - 1 >= 2 * K) {
        sum += table[min(i + K - 1, 2 * K - 1)][(j + K - 1) % (2 * K)];
        if (i > 0) sum -= table[i - 1][(j + K - 1) % (2 * K)];
    }
    if (j + K - 1 >= 2 * K && i + K - 1 >= 2 * K) {
        sum += table[(i + K - 1) % (2 * K)][(j + K - 1) % (2 * K)];
    }
    sum += table[min(i + K - 1, 2 * K - 1)][min(j + K - 1, 2 * K - 1)];
    if (i > 0) sum -= table[i - 1][min(j + K - 1, 2 * K - 1)];
    if (j > 0) sum -= table[min(i + K - 1, 2 * K - 1)][j - 1];
    if (i > 0 && j > 0) sum += table[i - 1][j - 1];
    return sum;

}


int main() {
    int N, T;
    cin >> N >> T;
    int t1, t2;
    cin >> t1;
    int sum = 0;
    rep(i, N - 1) {
        cin >> t2;
        sum += min(T, t2 - t1);
        t1 = t2;
    }
    sum += T;
    cout << sum << endl;

    return 0;
}



Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <cmath>
#include <array>
#include <queue>
#include <map>
#include <set>
#include <stack>
#include <cstdint>
#include <unordered_set>
#include <ctime>
typedef long long int llint;

int main(void){

  std::string s, t, u;
  int a, b;
  std::cin >> s >> t >> a >> b >> u;

  if(u == s) a--;
  if(u == t) b--;

  std::cout << a << " " << b << std::endl;
  
  return 0;
}


Measured memory_bytes: 256
import java.math.BigDecimal;
import java.text.DecimalFormat;
import java.util.*;

class Main{
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		int num = sc.nextInt();
		BigDecimal ans = BigDecimal.ZERO;
		Map<String, Integer> list = new HashMap<>();
		for(int i = 0; i < num; i++){
			String str = sc.next();
			char[] chars = str.toCharArray();
			Arrays.sort(chars);
			str = new String(chars);
			try{
				ans = ans.add(BigDecimal.valueOf(list.get(str)));
				list.put(str, list.get(str)+1);
			}catch(Exception e){
				list.put(str, 1);
			}
		}

		System.out.println(new DecimalFormat("0").format(ans));

	}
}

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

int main()
{
    int n;
    cin>>n;
    string maxfreq;
        map<string,int> m;
        while(n--)
        {
            string a;
            cin>>a;
            m[a]++;
        }
        int max=0;
        for(auto it = m.begin();it!=m.end();it++)
        {
            if(it->second>max)
            {
                max= it->second;
            }
        }
        vector<string > v;
        
        for(auto it = m.begin();it!=m.end();it++)
    if(it->second==max)
    v.push_back(it->first);
    sort(v.begin(),v.end());
    for(string x: v)
    cout<<x<<endl;
    return 0;
}


Measured memory_bytes: 28656
#include <stdio.h>
#include <stdlib.h>

typedef struct _data
{
	char name[11];
	int time;
	struct _data *next;
} data;

void enq(data **h, data **t, data *p)
{
	p->next = NULL;
	if (*t == NULL) *h = p;
	else (*t)->next = p;
	*t = p;
}

data *deq(data **h, data **t)
{
	data *w;
	if (*h == NULL) return NULL;
	w = *h;
	*h = (*h)->next;
	if (*h == NULL) *t = NULL;
	return w;
}

int main()
{
	int n, q, c, i;
	data *h, *t, *p;

	scanf("%d",&n);
	scanf("%d",&q);

	h = t = NULL;
	for (i = 0; i < n; i++)
	{
		p = (data*)malloc(sizeof(data));
		scanf("%10s",p->name);
		scanf("%d",&(p->time));
		enq(&h,&t,p);
	}

	c = 0;
	while ((p = deq(&h,&t)) != NULL)
	{
		if (p->time <= q)
		{
			c += p->time;
			p->time = 0;
		}
		else
		{
			c += q;
			p->time -= q;
		}

		if (p->time == 0)
		{
			printf("%s %d\n",p->name,c);
			free(p);
		}
		else
			enq(&h,&t,p);
	}

	return 0;
}

Measured memory_bytes: 3240
/*
author: Apoorv Singh
*/
 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/detail/standard_policies.hpp>
using namespace std;
using namespace __gnu_pbds;
 
typedef vector <int> vi;
typedef pair <int, int> pii;
typedef vector <long long> vll;
typedef pair <long long, long long> pll;
#define pb push_back   
#define all(c) c.begin(), c.end()
#define For(i, a, b) for (long long i = a; i < b; ++i)
#define Forr(i, a, b) for (long long i = a; i > b; --i)
#define um unordered_map
#define F first
#define S second
#define ll long long 
#define endl "\n"
#define min(a,b) (a < b ? a : b)
#define max(a,b) (a > b ? a : b)
#define fast_io() ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

#define TRACE
#ifndef ONLINE_JUDGE
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void __f(const char* name, Arg1&& arg1) {
	cout << name << " : " << arg1 << endl;  
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args) {
	const char* comma = strchr(names + 1, ',');cout.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...);
}
#else
#define trace(...)
#endif

template <class X>
void printarr(X arr[], int n) {
	for (int i = 0; i < n; ++i)
		cout << arr[i] << ' ';
	cout << endl;
}
 
template <class T, class cmp = less<T>> using ordered_set = tree<T, null_type, cmp, rb_tree_tag, tree_order_statistics_node_update>;
 
ll modulo = 1e9 + 7;

ll fpow(ll a, ll n) {
	ll ans = 1;
	while (n) {
		if (n&1) ans = (ans*a)%modulo;
		a = (a*a)%modulo; n = n >> 1;
	}
	return ans;
}

void solve() {
	int a,b,c,d;
	cin >> a >> b >> c >> d;
	int turn = 1;
	while (true) {
		if (turn == 1) {
			c -= b;
			if (c <= 0) {
				cout << "Yes" << endl;
				return;
			}
		}
		else {
			a -= d;
			if (a <= 0) {
				cout << "No" << endl;
				return;
			}
		}
		turn *= -1; 
	}		
}

int main() {
	fast_io();
	int t = 1;
	// cin >> t;
	while (t--) solve();
	return 0;
}

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

using namespace std;



int main(){

		string s,S; cin >> s >> S;
		int ans = 0;
		for(int i = 0; i<3;i++){
			if(s.at(i)==S.at(i)){
				ans++;
			}
			
		}
			cout << ans <<endl;

		
	}




Measured memory_bytes: 256
#include<bits/stdc++.h>
#define fast ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
using namespace std;



int main() {
    fast

    int n;
    cin>>n;

    //set<pair<int,int>>s;
    map<pair<int,int>,int>mp;
    string s;
    int first,last;
    for(int i=1;i<=n;i++ ){
        s=to_string(i);
        first=s[0];
        last=s[s.size()-1];
        mp[{first,last}]++;
    }

    long long ans=0;

    for(auto i:mp){
        ans+=i.second*mp[{i.first.second,i.first.first}];
    }
    //ans/=2;
    cout<<ans;







	return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=int(a);i<int(b);++i)
using namespace std;
typedef long long ll;
int INF = (1LL << 30) - 1;
int MOD = 1e9+7;
main(){
    int N;
    cin >> N;
    rep(i,1,10)rep(j,1,10){
        if(i * j == N){
            cout << "Yes" << endl;
            return 0;
        }
    }
    cout << "No" << endl;
}

Measured memory_bytes: 256
x,y, a, b, c= map(int,input().split())
red = list(map(int,input().split()))
green = list(map(int,input().split()))
trans = list(map(int,input().split()))
fr = sorted(red, reverse= True)[:x]
fg = sorted(green, reverse= True)[:y]
candidate = fr + fg + trans
candidate = sorted(candidate, reverse= True)
candidate = candidate[:x+y]
print(sum(candidate))

Measured memory_bytes: 23328
#include<iostream>
#include<vector>
#include<algorithm>
#include<set>
#include<map>
#include<cmath>
#include<string>
#include<queue>
#include<iomanip>
#include<bitset>
#include<math.h>
#include<stack>
#include<set>
using namespace std;
#define int long long
signed main() {
	ios_base::sync_with_stdio(0);
	cin.tie();
	cout.tie();
	int n;
	cin >> n;
	string s;
	cin >> s;
	int g = 0;
	for (int i = 0; i < n; i++) {
		if (s[i] == 'G') {
			g++;
		}
	}
	int r = 0;
	for (int i = 0; i < n; i++) {
		for (int j = i + 1; j < n; j++) {
			if (s[i] != s[j] && s[i] != 'G' && s[j] != 'G') {
				r += g;
				if (2*j-i < n && s[j + j - i] == 'G') {
					r--;
				}
				if (2*i - j >= 0 && s[2*i-j] == 'G') {
					r--;
				}
				if (((i+j+1)&1) && s[(i+j)/2] == 'G') {
					r--;
				}
			}
		}
	}
	cout << r;
}
	

Measured memory_bytes: 3576
with Ada.Text_IO;
use Ada.Text_IO;
with Ada.Integer_Text_IO;
use Ada.Integer_Text_IO;

procedure Main is
	s:Integer;
    w:Integer;
begin
	get(s);
	get(w);
	if w>=s then
		Put_Line("unsafe");
	else
		Put_Line("safe");
	end if;
      
end Main;


Measured memory_bytes: 3672
#include<bits/stdc++.h>
using namespace std;
#define fs first
#define sc second
#define pb push_back
#define mp make_pair
#define eb emplace_back
#define ALL(A) A.begin(),A.end()
#define RALL(A) A.rbegin(),A.rend()
typedef long long LL;
typedef pair<LL,LL> P;
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; }
const LL mod=1000000007;
const LL LINF=1LL<<60;
const int INF=1<<30;
int dx[]={1,0, 0,-1,1,-1, 1,-1};
int dy[]={0,1,-1, 0,1,-1,-1, 1};


int main(){
    int k,x;cin >> k >> x;
    cout << (k*500>=x?"Yes":"No") << endl;
    return 0;
}


Measured memory_bytes: 256
import java.util.*;
import java.io.*;
import java.math.*;
 
public class Main {
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        String s = "abcdefghijklmnopqrstuvwxyz";
        String c = sc.next();
        System.out.println(s.charAt(s.indexOf(c)+1));
    }
}

Measured memory_bytes: 20692
import bisect
def main():
    N = int(input())
    L = list(map(int,input().split()))
    L.sort()
    
    count = 0
    for i in range(N-2):
        for j in range(i+1,N-1):
            c = bisect.bisect_left(L,L[i]+L[j])
            
            count += max(0,c-1 - j)
    
    print(count)
main()

Measured memory_bytes: 3188
#include <bits/stdc++.h>
#include <numeric>
#define REP(i, n) for(int i = 0; i < n; i++)
#define REPR(i, n) for(int i = n; i >= 0; i--)
#define FOR(i, m, n) for(int i = m; i < n; i++)
#define INF 2e9
#define ALL(v) v.begin(), v.end()
using namespace std;
typedef long long ll;	

int main() {
    int a, b; cin >> a >> b;
    if (a == b) {
        cout << "Draw" << endl;
    }
    else if (a == 1) {
        cout << "Alice" << endl;
    }
    else if (b == 1) {
        cout << "Bob" << endl;
    }
    else if (a > b) {
        cout << "Alice" << endl;
    }
    else {
        cout << "Bob" << endl;
    }
}


Measured memory_bytes: 3596
import java.io.BufferedReader
import java.io.InputStream
import java.io.InputStreamReader
import java.lang.AssertionError
import java.util.*
import kotlin.math.abs
import kotlin.math.max
import kotlin.math.min

val MOD = 1_000_000_007L

class Solver(stream: InputStream, private val out: java.io.PrintWriter) {
  fun solve() {
    val S = ns()
    out.println(S.split('S').map{it.length}.max()!!)
  }













































  private val isDebug = try {
    // なんか本番でエラーでる
    System.getenv("MY_DEBUG") != null
  } catch (t: Throwable) {
    false
  }

  private var tokenizer: StringTokenizer? = null
  private val reader = BufferedReader(InputStreamReader(stream), 32768)
  private fun next(): String {
    while (tokenizer == null || !tokenizer!!.hasMoreTokens()) {
      tokenizer = StringTokenizer(reader.readLine())
    }
    return tokenizer!!.nextToken()
  }

  private fun ni() = next().toInt()
  private fun nl() = next().toLong()
  private fun ns() = next()
  private fun na(n: Int, offset: Int = 0): IntArray {
    return map(n) { ni() + offset }
  }
  private fun nal(n: Int, offset: Int = 0): LongArray {
    val res = LongArray(n)
    for (i in 0 until n) {
      res[i] = nl() + offset
    }
    return res
  }

  private fun na2(n: Int, offset: Int = 0): Array<IntArray> {
    val a  = Array(2){IntArray(n)}
    for (i in 0 until n) {
      for (e in a) {
        e[i] = ni() + offset
      }
    }
    return a
  }

  private inline fun map(n: Int, f: (Int) -> Int): IntArray {
    val res = IntArray(n)
    for (i in 0 until n) {
      res[i] = f(i)
    }
    return res
  }

  private inline fun debug(msg: () -> String) {
    if (isDebug) System.err.println(msg())
  }

  private inline fun debug(a: LongArray) {
    debug { a.joinToString(" ") }
  }

  private inline fun debug(a: IntArray) {
    debug { a.joinToString(" ") }
  }

  private inline fun debug(a: BooleanArray) {
    debug { a.map { if (it) 1 else 0 }.joinToString("") }
  }

  private inline fun debugDim(A: Array<LongArray>) {
    if (isDebug) {
      for (a in A) {
        debug(a)
      }
    }
  }
  private inline fun debugDim(A: Array<IntArray>) {
    if (isDebug) {
      for (a in A) {
        debug(a)
      }
    }
  }

  /**
   * 勝手にimport消されるのを防ぎたい
   */
  private fun hoge() {
    min(1, 2)
    max(1, 2)
    abs(-10)
  }

  private inline fun assert(b: Boolean) = run{if (!b) throw AssertionError()}
}

fun main() {
  val out = java.io.PrintWriter(System.out)
  Solver(System.`in`, out).solve()
  out.flush()
}

Measured memory_bytes: 36536
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
const int INF = 1 << 29;
const int MOD = 1000000007;

int main() {
    long long n, m, k;
    cin >> n >> m >> k;
    vector<long long> a(n);
    rep(i, n) {
        cin >> a.at(i);
    }
    vector<long long> b(m);
    rep(i, m) {
        cin >> b.at(i);
    }

    // cusum_a[i] + cusum_b[j] <= K となるように選ぶとき、i+jが取りうる最大値が答え

    // A, Bそれぞれの累積和を求めて引いたり足したりする
    // \sigma_{k = x}^{y} a[k]  = cusum_a[y + 1] - b[x] がO(1)
    vector<long long> cusum_a(n + 1, 0);
    vector<long long> cusum_b(m + 1, 0);

    rep(i, n) {
        cusum_a.at(i + 1) = cusum_a.at(i) + a.at(i);
    }

    rep(i, m) {
        cusum_b.at(i + 1) = cusum_b.at(i) + b.at(i);
    }

    // 最大読書数
    int ans_max = 0;

    // bの可能な最大読書数
    int num_b = m;

    // i=0から全探索し、それぞれについてj = Mから降順に操作する
    rep(i, n + 1) {
        // 差分
        long long diff = k - cusum_a.at(i);
        // aだけで読みきれなくなって差分がマイナスになったら終了
        if (diff < 0) {
            break;
        }

        // jを大きい方から走査する
        for (int j = num_b; j > -1; j--) {
            // 最初に差分内に収まればok
            if (cusum_b.at(j) <= diff) {
                // 最大数と比較
                ans_max = max(i + j, ans_max);
                // 次のループではこれより下を見ればよい
                num_b = j;
                break;
            }
        }
    }

    cout << ans_max << endl;
}


Measured memory_bytes: 9584
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ii = pair<int, int>;
using iii = pair<ii, int>;
#define vt vector
#define pq priority_queue
#define pb push_back
#define pf push_front
#define mp make_pair
#define fi first
#define se second
#define __lcm(a, b) a * b / __gcd(a, b)
// #define multicase
const int MOD = 1e9 + 7;
const int INF = 2e9;
// const int N = ;

string s, ans;

void solve() {
    int T = 1;
  #ifdef multicase
    cin >> T;
  #endif
    for(int tc = 1; tc <= T; tc++) {
        cin >> s;
        for(int i = 0; i < s.size(); i++) {
            if(s[i] == '1') ans += '1';
            else if(s[i] == '0') ans += '0';
            else {
                if(ans.size())
                    ans.erase(ans.size() - 1);
            }
        }
        cout << ans << "\n";
    }
}

int main() {

    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    solve();
    
}

Measured memory_bytes: 3628
#include <stdio.h>
#define N 9

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

	while (scanf("%d", &n) != EOF) {
		counter = 0;
		for (a = 0; a <= N; a++){
			for (b = 0; b <= N; b++){
				for (c = 0; c <= N; c++){
					for (d = 0; d <= N; d++){
						if ((a + b + c + d) == n){
							counter++;
						}
					}
				}
			}
		}
		printf("%d\n", counter);
	}

	return 0;
}

Measured memory_bytes: 596
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<limits.h>
#include<math.h>

int main(void){
    int N, M;
    scanf("%d %d", &N, &M);
    int *a = (int*)malloc(N * sizeof(int));
    int *b = (int*)malloc(N * sizeof(int));
    int *c = (int*)malloc(M * sizeof(int));
    int *d = (int*)malloc(M * sizeof(int));

    int i, j;
    for(i=0; i<N; i++) {
        scanf("%d %d", &a[i], &b[i]);
    }
    for(i=0; i<M; i++) {
        scanf("%d %d", &c[i], &d[i]);
    }

    for(i=0; i<N; i++) {
        int min = INT_MAX;
        int index = 0;
        for(j=0; j<M; j++) {
            if(abs(a[i]-c[j]) + abs(b[i]-d[j]) < min) {
                min = abs(a[i]-c[j]) + abs(b[i]-d[j]);
                index = j;
            }
        }
        printf("%d\n", index+1);
    }

    free(a);
    free(b);
    free(c);
    free(d);
    return 0;
}

Measured memory_bytes: 128
lists = [int(i) for i in input().rstrip().split(" ")]
w_1 = 100 * lists[0]
w_2 = 100 * lists[1]
s_1 = lists[2]
s_2 = lists[3]
sol = lists[4] / (100 + lists[4])
limit = lists[5]

weight = 0
dens = 0
ans = (1,-1)
w_group = set()

for i in range(limit//w_1 + 1):
    for j in range((limit-w_1*i)//w_2 + 1):
        w_group.add(w_1*i + w_2*j)
w_group.remove(0)

s_group = set()

for w_w in w_group:
    for i in range((limit-w_w)//s_1 + 1):
         for j in range((limit-w_w-s_1*i)//s_2 + 1):
             s_group.add(s_1*i + s_2*j)
    for s_s in s_group:
        weight = w_w + s_s
        dens = s_s / weight
        if sol >= dens > ans[1]/ans[0]:
            ans = (weight, s_s)
    s_group.clear()
print("{0} {1}".format(ans[0], ans[1]))

Measured memory_bytes: 3232
#include <iostream>
#include <string>
#include <cstring>
#include <algorithm>
#include <functional>
#include <cmath>
#include <set>
#include <queue>
#include <vector>
#include <climits>
#include <sstream>
#include <iomanip>
#include <map>
#include <stack>
using namespace std;

int main()
{
	string S;
	cin >> S;

	auto isAllFound = true;
	for (auto c = 'a'; c <= 'z'; ++c)
	{
		if (S.find(c) == string::npos)
		{
			isAllFound = false;
			cout << c << endl;
			break;
		}
	}

	if (isAllFound)
	{
		cout << "None" << endl;
	}

	return 0;
}

Measured memory_bytes: 512
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cassert>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <algorithm>
using namespace std;
typedef long long ll;

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

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

  ll res = 0;
  for(int i=0;i+1<N;i++){
    if(a[i] + a[i+1] > x){
      int t = a[i] + a[i+1] - x;
      res += t;
      a[i+1] = max(0, a[i+1] - t);
    }
  }

  cout << res << endl;
  return 0;
}


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

const int INF=123456789;

typedef pair<int,int> P;

char maze[101][101];
int H,W;

int d[101][101];

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

//sxsyからgxgyへの最短距離を求める

int bfs(int sy,int sx,int gy,int gx){
  if(maze[sy][sx]=='.' || maze[gy][gx]=='.') return 123456789;
  queue<P> que;
  for(int i=0;i<H;i++) {
    for(int j=0;j<W;j++){
       d[i][j]=INF;
     }
   }
  que.push(P(sy,sx));
  d[sy][sx]=0;

  while(que.size()){
    P p=que.front();que.pop();
    if(p.second==gx&&p.first==gy) break;

    for(int i=0;i<2;i++){
      int nx=p.second+dx[i], ny=p.first+dy[i];
      if(0<=nx&&nx<W&&0<=ny&&ny<H&&maze[ny][nx]!='.'&&d[ny][nx]==INF){
        que.push(P(ny,nx));
        d[ny][nx] = d[p.first][p.second]+1;
      }
    }
  }


  return d[gy][gx];
}

void solve(){

}

int main(){
  cin>>H>>W;
  for(int i=0;i<H;i++) for(int j=0;j<W;j++){
    cin>>maze[i][j];
  }
 int ans = bfs(0,0,H-1,W-1);
 int b[101];

 for(int i=0;i<H*W;i++) b[i]=0;
 for(int i=0;i<H;i++) for(int j=0;j<W;j++){
   if(d[i][j]!=INF)b[d[i][j]-1]++;
   if(d[i][j]==INF&&maze[i][j]=='#'){
     cout<<"Impossible"<<endl;
     return 0;
   }
 }

 for(int i=0;i<H*W;i++){
   if(b[i]>=2){
     cout<<"Impossible"<<endl;
     return 0;
   }
 }
 if(d[H-1][W-1]!=INF)  cout<<"Possible"<<endl;
 else cout<<"Impossible"<<endl;

}


Measured memory_bytes: 3612
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <queue>
#include <map>
#include <cmath>
#include <numeric>
#include <iomanip>
#include <set>
#include <string.h>

using namespace std;

typedef long long ll;

#define REP(i,n) for(ll (i)=0;(i)<(n);(i)++)
#define REP3(i,st,en) for(ll (i)=(st);(i)<(en);(i)++)

using P = pair<ll, ll>;
const int MOD = 1e9+7;
const ll INF = 1e+14;
const double PI = 3.14159265349;



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

  ll N;
  string S;
  cin >> N >> S;
  ll ans = N;
  REP3(i,1,N){
    if (S[i]==S[i-1]) ans--;
  }

  cout << ans << "\n";
  return 0;
}


Measured memory_bytes: 512
import static java.util.Arrays.deepToString;

import java.util.Arrays;
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		new Main().run();
	}
	void tr(Object... os) {
		System.err.println(deepToString(os));
	}

	Scanner sc = new Scanner(System.in);
	void run() {
 		for (int testcase = sc.nextInt(); testcase-->0;) {
			char[] s = sc.next().toCharArray();
			char[] ans = new char[1024];
			int p = 512, i = 0;
			ans[p] = s[i++];
			int minp = p, maxp = p;
			for (; i < s.length; i++) {
				if (s[i] == '-') p++; else p--;
				i += 2;
				ans[p] = s[i];
				minp = Math.min(minp, p);
				maxp = Math.max(maxp, p);
			}
			System.out.println(new String(Arrays.copyOfRange(ans, minp, maxp + 1)));
		}
	}
}

Measured memory_bytes: 21300
#include<stdio.h>

main(){
	int a[4][14],n,i,j;
	
	scanf("%d",&n);
	
	for(i=0;i<4;i++){
		for(j=0;j<14;j++){
			a[i][j]=0;
		}
	}
	
	for(i=0;i<=n;i++){
		char b;
		int c;
		
		scanf("%c %d\n",&b,&c);
		
		if(b=='S'){
			a[0][c]=1;
		}
		else if(b=='H'){
			a[1][c]=1;
		}
		else if(b=='C'){
			a[2][c]=1;
		}
		else if(b=='D'){
			a[3][c]=1;
		}
	}
	
	char pattern[4] = {'S','H','C','D'};
	
	for(i=0;i<4;i++){
		for(j=1;j<14;j++){
			if(a[i][j]==0){
				printf("%c %d\n",pattern[i],j);
			}
		}
	}
	
	return 0;
}

Measured memory_bytes: 600
#include <stdio.h>
#define _USE_MATH_DEFINES
#include <math.h>
#include <vector>
#include <algorithm>

using namespace std;

int main(){
    long n,k;
    scanf("%ld %ld", &n, &k);
    vector<long> viLength(n);
    for(long i = 0; i < n; i++){
        scanf("%ld", &viLength[i]);
    }
    
    long nAns = 4294967296 / 2;
    long iTwoPower = 4294967296 / 4;
    for(long i = 0; i < 32; i++){
        long nCount = 0;
        for(long j = 0; j < n; j++){
            nCount += (ceil(viLength[j] / (double)nAns) - 1);
        }
        if(nCount <= k){
            nAns -= iTwoPower;
        }
        else{
            nAns += iTwoPower;
        }
        iTwoPower /= 2;
    }
    long nCount = 0;
    for(long j = 0; j < n; j++){
        nCount += (ceil(viLength[j] / (double)nAns) - 1);
    }
    if(nCount > k){
        nAns++;
    }
    
    printf("%ld", nAns);
    return 0;
}


Measured memory_bytes: 4400
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 = n*a;
				
			System.out.println(Math.min(c, b));
	}
}


Measured memory_bytes: 21844
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
template<class T> bool umin(T &a, T b) { return a > b ? (a = b, true) : false; }
template<class T> bool umax(T &a, T b) { return a < b ? (a = b, true) : false; }
#define ALL(x) (x).begin(), (x).end()
LL POW(LL a,LL p,LL M){ if(!p) return 1LL;LL T = POW(a,p/2,M);T = T*T%M; if(p&1) T=T*(a%M)%M; return T; }
LL SQRT(LL a) { LL b = (LL)sqrtl(((double)a)+0.5); while(b*b<a) ++b; while(b*b>a) --b; return (b*b==a)?b:-1; }
//endl
//<------------------------edits---------------------------------------------->
const LL MOD = 1e9+7;//998244353
// #define LOCAL LDD
#define int LL

int pos(LL no,LL k){
  while(no%k==0) no /= k;
  return no%k==1;
}

signed main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.precision(10);cout << fixed;
#ifdef LOCAL
  freopen("input.txt", "rt", stdin);
#endif
  LL n;cin >> n;
  LL cnt = 0;
  for(LL i=2;i*i<=n;i++){
    if(n%i==0){
      cnt += pos(n,i);
      if(i!=n/i) cnt += pos(n,n/i);
    }
  }
  if(n>=2) cnt++;
  LL no = n;
  n--;
  if(n>=2){
    for(LL i=2;i*i<=n;i++){
      if(n%i==0){
        cnt += pos(no,i);
        if(i!=n/i) cnt += pos(no,n/i);
      }
    }
    if(n>=2) cnt++;
  }  
  cout << cnt << endl; 
  cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s\n";
  return 0;
}

Measured memory_bytes: 384
#include<iostream>
#include<string>
#include<algorithm>
#include<map>
#include<vector>
#include<cmath>
#include<cstdio>
#define loop(i,a,b) for(int i=a;i<b;i++) 
#define rep(i,a) loop(i,0,a)
#define pb(in,tmp) in.push_back(tmp)
#define all(in) in.begin(),in.end()
const double PI=acos(-1);
using namespace std;
int main(){
  int n;
  cin>>n;
  cin.ignore();
  rep(j,n){
    string s;
    getline(cin,s);
    size_t n;
    while(n=s.find("Hoshino"),n!=string::npos)s[n+6]='a';
    //rep(i,s.size()-6)if(s.substr(i,7)=="Hoshino")s.replace(i,7,"Hoshina");
    cout<<s<<endl;
  }


}

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

#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rep1(i, n) for (int i = 1; i < (int)(n); i++)
#define INF 1000000000000
#define MOD 1000000007
using ll = long long;

int main(){
  int n;
  cin >> n;
  n/=2;
  map<int,int> E,O;
  rep(i,n){
    int e,o;
    cin>>e>>o;
    if(E.count(e))E[e]++;
    else E[e]=1;
    if(O.count(o))O[o]++;
    else O[o]=1;
  }
  vector<pair<int,int>> ep,op;
  for(auto p: E){
    ep.push_back(make_pair(p.second,p.first));
  }
  for(auto p: O){
    op.push_back(make_pair(p.second,p.first));
  }
  sort(ep.begin(),ep.end(),greater<pair<int,int>>());
  sort(op.begin(),op.end(),greater<pair<int,int>>());
  ep.push_back({0,0});
  op.push_back({0,0});
  int e1 = ep.at(0).first, o1 = op.at(0).first;
  if(ep.at(0).second!=op.at(0).second)cout<<2*n-e1-o1<<endl;
  else{
    int e2 = ep.at(1).first, o2 = op.at(1).first;
    cout<<2*n-max(e1+o2,e2+o1)<<endl;
  }
  return 0;
}


Measured memory_bytes: 6136
// failed to generate code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
typedef pair<int,P> P1;
typedef pair<P,P> P2;
#define pu push
#define pb push_back
#define mp make_pair
#define eps 1e-7
#define INF 1000000000
#define mod 1000000007
#define fi first
#define sc second
#define rep(i,x) for(int i=0;i<x;i++)
#define repn(i,x) for(int i=1;i<=x;i++)
#define SORT(x) sort(x.begin(),x.end())
#define ERASE(x) x.erase(unique(x.begin(),x.end()),x.end())
#define POSL(x,v) (lower_bound(x.begin(),x.end(),v)-x.begin())
#define POSU(x,v) (upper_bound(x.begin(),x.end(),v)-x.begin())
vector<pair<string,P> >vec;

vector<vector<ll>> dp(105, vector<ll>(105, INF));

int main(){	
	ll H, W;
	cin >> H >> W;
	vector<string> s(H);
	rep(i, H) cin >> s[i];
	if (s[0][0] == '.') dp[0][0] = 0; else dp[0][0] = 1;
	rep(i, H) {
		rep(j, W) {
			if (i > 0) {
				if (s[i][j] == '.') dp[i][j] = min(dp[i][j], dp[i-1][j]);
				else if (s[i-1][j] == s[i][j]) dp[i][j] = min(dp[i][j], dp[i-1][j]); else dp[i][j] = min(dp[i][j], dp[i-1][j]+1);
			}
			if (j > 0) {
				if (s[i][j] == '.') dp[i][j] = min(dp[i][j], dp[i][j-1]);
				else if (s[i][j-1] == s[i][j]) dp[i][j] = min(dp[i][j], dp[i][j-1]); else dp[i][j] = min(dp[i][j], dp[i][j-1]+1);
			}
		}
	}
	// rep(i, H) {
	// 	rep(j, W) {
	// 		cout << dp[i][j];
	// 	}
	// 	cout << endl;
	// }
	cout << dp[H-1][W-1] << endl;
}


Measured memory_bytes: 384