akhauriyash/Code-Regression huggingface dataset:
s = input()


def solve(x):
    while 1:
        for frag in ("erase", "eraser", "dream", "dreamer"):
            if x.endswith(frag):
                x = x[:-len(frag)]
                break
        else:
            print("NO")
            break
        if not x:
            print("YES")
            break



solve(s)

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

int main() {
  int n;
  cin>>n;
  int plus[n];
  int x_y[n];
  int y_x[n];

  for(int i=0; i<n; i++) {
    int x,y;
    cin>>x>>y;
    plus[i] = x+y;
    x_y[i] = x-y;
    y_x[i] = y-x;
  }

  sort(plus, plus+n);
  sort(x_y, x_y+n);
  sort(y_x, y_x+n);

  int tmp1 = plus[n-1] - plus[0];
  int tmp2 = x_y[n-1] + y_x[n-1];

  cout<<max(tmp1, tmp2)<<endl;


  return 0;
}

Measured memory_bytes: 5980
import heapq

def main():
    Q = int(input())
    hs, hl = [], []
    ss, sl = 0, 0
    B = 0
    for _ in range(Q):
        q = input()
        if q == '2':
            x = -hs[0]
            print(x, x * (len(hs) - len(hl)) + sl - ss + B)
            continue
        _, a, b = map(int, q.split())
        B += b
        if hl and a >= hl[0]:
            heapq.heappush(hl, a)
            sl += a
        else:
            heapq.heappush(hs, -a)
            ss += a
        if len(hl) > len(hs):
            while len(hl) > len(hs):
                a = heapq.heappop(hl)
                sl -= a
                heapq.heappush(hs, -a)
                ss += a
        else:
            while len(hs) - len(hl) > 1:
                a = -heapq.heappop(hs)
                ss -= a
                heapq.heappush(hl, a)
                sl += a

main()


Measured memory_bytes: 11108
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>

using namespace std;

struct vertex {
    int x, y, index;
};

struct edge {
    int from, to, cost;
};

bool vcomp_x(const vertex &v1, const vertex &v2){
    return v1.x < v2.x;
}
bool vcomp_y(const vertex &v1, const vertex &v2){
    return v1.y < v2.y;
}

int main(int argc, char** argv){
    int N;
    cin >> N;
    vector<vertex> vs(N);
    vector<vector<edge>> es(N, vector<edge>());
    for (int i=0; i<N; i++){
        cin >> vs[i].x >> vs[i].y;
        vs[i].index = i;
    }

    sort(vs.begin(), vs.end(), vcomp_x);
    for (int i=1; i<N; i++){
        edge e1, e2;
        int ix1 = vs[i-1].index, ix2 = vs[i].index;
        e1.from = ix1; e1.to = ix2; e1.cost = vs[i].x - vs[i-1].x;
        e2.from = ix2; e2.to = ix1; e2.cost = vs[i].x - vs[i-1].x;
        es[ix1].push_back(e1);
        es[ix2].push_back(e2);
    }

    sort(vs.begin(), vs.end(), vcomp_y);
    for (int i=1; i<N; i++){
        edge e1, e2;
        int ix1 = vs[i-1].index, ix2 = vs[i].index;
        e1.from = ix1; e1.to = ix2; e1.cost = vs[i].y - vs[i-1].y;
        e2.from = ix2; e2.to = ix1; e2.cost = vs[i].y - vs[i-1].y;
        es[ix1].push_back(e1);
        es[ix2].push_back(e2);
    }

    auto comp_pq = [](edge &e1, edge &e2){
        return e1.cost > e2.cost;
    };
    priority_queue<edge, vector<edge>, decltype(comp_pq)> pq(comp_pq);

    int sum = 0;
    bool v_picked[N];
    for (int i=0; i<N; i++) v_picked[i] = false;
    v_picked[0] = true;
    for (auto itr = es[0].begin(); itr != es[0].end(); itr++)
        pq.push(*itr);
    for (int i=1; i<N; i++){
        edge e;
        while (1){
            e = pq.top();
            pq.pop();
            if (!v_picked[e.to]) break;
        }
        sum += e.cost;
        v_picked[e.to] = true;
        for (auto itr = es[e.to].begin(); itr != es[e.to].end(); itr++)
            pq.push(*itr);
    }

    cout << sum << "\n";

    return 0;
}


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

void SetX(int n, const char* src, char* dst)
{
	if(n<10)
	while(*src != '\0')
	{
		if(*src == 'X')*dst='0'+n;
		else *dst=*src;

		src++; dst++;
	}
	*dst='\0';
}

void Reverse(char* s, int len)
{
	int i;
	char tmp;
	for(i=0; i<len/2; i++)
	{
		tmp = s[i];
		s[i] = s[len-i-1];
		s[len-i-1] = tmp;
	}
}

char* Sum(const char* a, const char* b, char* ans)
{
	int i;
	int aDigit=strlen(a),
		bDigit=strlen(b),
		ansDigit,
		inc=0;

	const char
		*currA=a+aDigit-1,
		*currB=b+bDigit-1;
	char* currAns=ans;

	while(a<=currA || b<=currB)
	{
		*currAns += inc;
		if(a<=currA)*currAns += *(currA--) -'0';
		if(b<=currB)*currAns += *(currB--) -'0';
		
		if(*currAns>=10)
		{
			inc = 1;
			(*currAns)%=10;
		}
		else
			inc = 0;
		*currAns += '0';
		currAns++;
	}
	*currAns += inc+inc*'0';

	ansDigit = strlen(ans);
	Reverse(ans, ansDigit);

	return ans;
}

#include <stdlib.h>
int main(void)
{
	int i, n, na;
	char srcA[128], srcB[128], srcC[128];
	char a[128], b[128], c[128], sum[128];
	
	while( scanf("%[^+]+%[^=]=%s%*c", srcA, srcB, srcC) != EOF )
	{
		na=1;
		for(i=0; i<128; i++)
			{a[i]=0; b[i]=0; c[i]=0;}
		
		for(n=0; n<10; n++)
		{
			if(n==0 && (
				( strlen(srcA)>1 && srcA[0]=='X') ||
				( strlen(srcB)>1 && srcB[0]=='X') ||
				( strlen(srcC)>1 && srcC[0]=='X') ) )
				continue;

			for(i=0; i<128; i++)sum[i]=0;
			SetX(n, srcA, a);
			SetX(n, srcB, b);
			SetX(n, srcC, c);
			if( strcmp(Sum(a, b, sum), c)==0 )
			{
				na=0;
				break;
			}
		}
		if(!na)printf("%d\n", n);
		else   puts("NA");
	}
	
	return 0;
}

Measured memory_bytes: 560
#include<iostream>
#include<array>

using namespace std;

int main(){
    int n,ans;
    array<int,100000>a;
    for(int i = 0; i < 100000; i++){
        a.at(i) = 0;
    }
    cin>>n;
    for(int i = 0; i < n; i++){
        int k=0;
        cin>>k;
        if(k>100000){
            ans++;
        }else{
            a.at(k-1)++;
        }
    }

//  cout<<ans<<endl;
//  cout<<a.at(99999)<<endl;

    for(int i = 1; i <= 100000; i++){
        if(i>a.at(i-1)){
            ans = ans + a.at(i-1);
        }else if(i<a.at(i-1)){
            ans = ans + a.at(i-1) - i;
        }
    }
    cout<<ans<<endl;
}

Measured memory_bytes: 640
#include <bits/stdc++.h>
#define For(i, a, b) for(int (i)=(int)(a); (i)<(int)(b); ++(i))
#define rFor(i, a, b) for(int (i)=(int)(a)-1; (i)>=(int)(b); --(i))
#define rep(i, n) For((i), 0, (n))
#define rrep(i, n) rFor((i), (n), 0)
#define fi first
#define se second
using namespace std;
typedef long long lint;
typedef unsigned long long ulint;
typedef pair<int, int> pii;
template<class T> bool chmax(T &a, const T &b){if(a<b){a=b; return true;} return false;}
template<class T> bool chmin(T &a, const T &b){if(a>b){a=b; return true;} return false;}
template<class T> T div_floor(T a, T b){
    if(b < 0) a *= -1, b *= -1;
    return a>=0 ? a/b : (a+1)/b-1;
}
template<class T> T div_ceil(T a, T b){
    if(b < 0) a *= -1, b *= -1;
    return a>0 ? (a-1)/b+1 : a/b;
}

constexpr lint mod = 1e9+7;
constexpr lint INF = mod * mod;
constexpr int MAX = 200010;

string split(string &s, int i, int flag){
    int j = i;
    if(flag == 0) while(j < s.size() && s[j] != ':') ++j;
    else while(j < s.size() && s[j] != ',' && s[j] != '.') ++j;
    return s.substr(i, j-i);
}

int n;
string g[110];
map<string, int> mp;
vector<string> G[110];
set<string> ans[110];

void dfs(int v){
    if(!ans[v].empty()) return;
    for(auto &s: G[v]){
        if(mp.find(s) != mp.end()){
            int nv = mp[s];
            dfs(nv);
            for(auto &t: ans[nv]) ans[v].insert(t);
        }
        else{
            ans[v].insert(s);
        }
    }
}

int main(){
    while(scanf("%d", &n) && n){
        mp.clear();
        rep(i, n){
            ans[i].clear();
            G[i].clear();
        }

        rep(i, n){
            string tmp;
            cin >> tmp;
            g[i] = split(tmp, 0, 0);
            mp[g[i]] = i;
            for(int cur=(int)g[i].size()+1; cur<tmp.size();){
                string t = split(tmp, cur, 1);
                G[i].push_back(t);
                cur += (int)t.size()+1;
            }
        }
        dfs(0);
        printf("%d\n", ans[0].size());
    }
}


Measured memory_bytes: 3540
use std::io;

fn main() {
    let n = read_int();
    let j = (1..(n as f64).sqrt().floor() as u64 + 1)
        .rev()
        .filter(|i| n % i == 0)
        .next()
        .expect("at least one divisor");
    println!("{}", digits(n / j));
}

fn digits(n: u64) -> usize {
    n.to_string().len()
}

fn get_line() -> String {
    let mut buf = String::new();
    io::stdin().read_line(&mut buf).expect("read");
    buf
}

fn read_int() -> u64 {
    get_line().trim().parse().expect("parse error")
}

Measured memory_bytes: 4352
S = input()
h = len(S)//2
for i in range(h):
  if S[i] != S[-i-1]:
    print('No')
    exit()
for i in range(h//2):
  if S[i] != S[h-i-1]:
    print('No')
    exit()
for i in range(h//2):
  if S[h+i+1] != S[-i-1]:
    print('No')
    exit()
print('Yes')

Measured memory_bytes: 3060
#include <bits/stdc++.h>
//#pragma GCC optimize "-O3"
typedef unsigned long long ull;
typedef unsigned int ui;
typedef unsigned short us;
typedef long long ll;
typedef long double ld;
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const ll infll=(1ull<<63)-1;
const int inf=(1ull<<31)-1;
int n,a[100001],ans=0,s=0;

int main()
{
	//freopen("input.txt","r",stdin);freopen("output.txt","w",stdout);
	ios_base::sync_with_stdio(false); cin.tie(0);cout.precision(18);
	cin>>n;
	for (int i=0;i<n;i++)
		cin>>a[i];
	int t=a[0];
	for (int i=1;i<n;i++){
		if (a[i]<=t)
			s++;
		else {
			ans=max(ans,s);
			s=0;
		}
		t=a[i];
	}
	ans=max(ans,s);
	cout<<ans;
	return 0;
}

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

int PrimeJudge(int x){
  int k = 0;
  for(int i = 2; i <= sqrt(x); i++){
    if(x % i == 0){
      k = 1;
      break;
    }
  }
  if(k == 1) return 0;
  else return 1;
}

int main(){
	int n, p, cnt = 0;
  cin >> n;

  for(int i = 0; i < n; i++){
    cin >> p;
    if(PrimeJudge(p)) cnt++;
  }

  cout << cnt << endl;

}



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

int main() {

    long long x, y, z, k;
    cin >> x >> y >> z >> k;
    long long arr1[x];
    long long arr2[y];
    long long arr3[z];
    for (long long i=0; i<x; i++) {
        cin >> arr1[i];
    }
    for (long long i=0; i<y; i++) {
        cin >> arr2[i];
    }
    for (long long i=0; i<z; i++) {
        cin >> arr3[i];
    }
    long long narr[x*y];
    for (long long i=0; i<x; i++) {
        for (long long j=0; j<y; j++) {
            narr[i*y+j] = arr1[i] + arr2[j];
        }
    }
    sort(narr, narr+(x*y), greater<long long>());

    vector<long long> fin;
    for (long long i=0; i<min(x*y, k); i++) {
        for (long long j=0; j<z; j++) {
            fin.push_back(narr[i]+arr3[j]);
        }
    }
    sort(fin.begin(), fin.end(), greater<long long>());
    for (long long i=0; i<k; i++) {
        cout << fin[i] << endl;
    }

}

Measured memory_bytes: 42852
def addTime(n):
    keta = n%10
    if keta == 0:
        return n
    return n+10 - keta

def calcKeta(n):
    if n%10!=0:
        return n%10
    return 10

food = [int(input()) for _ in range(5)]
foods = sorted(food,key=calcKeta)
min_food_time = foods[0]
foods.remove(min_food_time)
print(sum(list(map(addTime,foods)))+min_food_time)

Measured memory_bytes: 3064
#include <algorithm>
#include <bitset>
#include <cmath>
#include <ctime>
#include <iostream>
#include <list>
#include <map>
#include <math.h>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <stdio.h>
#include <string>
#include <tuple>
#include <vector>
 
using namespace std;
using Graph = vector<vector<int>>;

#define rep(i,n) for(int i = 0; i < (n); i++)
#define all(a) begin(a),end(a)
 
typedef long long ll;
typedef pair<int,int> P;
const int inf=1000000007;
const ll mod=1000000007;
const double PI=3.14159265358979323846;
 
int dx[] = {1,-1,0,0};
int dy[] = {0,0,1,-1};
 
ll gcd(ll a, ll b){
  if (b==0) return a;
  else return gcd(b,a%b);
}
 
int cans(bool f){
  if(f) cout << "Yes" << endl;
  else cout << "No" << endl;
  return 0;
}





int W,H;
vector<vector<int>> field;



void dfs(int y,int x){
  field[y][x] = 0;
  for(int i = -1; i <= 1; i++){
    for(int j = -1; j <= 1; j++){
      
      int nx,ny; 
      nx = x + i;
      ny = y + j;
      if (ny < 0 || ny >= H || nx < 0 || nx >= W || field[ny][nx] == 0) continue;
      dfs(ny,nx);
    }
  }
}

int main(){
  while(cin >> W >> H){
    if(W == 0 || H == 0) break;
    field.assign(H,vector<int>(W,0));
    rep(i,H){
      rep(j,W) cin >> field[i][j];
    }
    
    int ans = 0;
    rep(i,H){
      rep(j,W){
	if(field[i][j] == 0) continue;
	ans++;
	dfs(i,j);
      }
    }
    cout << ans << endl;
  }
}












// void dfs(int h, int w) {
//     field[h][w] = 0;

//     // 八方向を探索
//     for (int dh = -1; dh <= 1; ++dh) {
//         for (int dw = -1; dw <= 1; ++dw) {
//             int nh = h + dh, nw = w + dw;

//             // 場外アウトしたり、0 だったりはスルー
//             if (nh < 0 || nh >= H || nw < 0 || nw >= W) continue;
//             if (field[nh][nw] == 0) continue;

//             // 再帰的に探索
//             dfs(nh, nw);
//         }
//     }
// }

// int main() {
//     // 入力受け取り
//     while (cin >> W >> H) {
//         if (H == 0 || W == 0) break;
//         field.assign(H, vector<int>(W, 0));
//         for (int h = 0; h < H; ++h) for (int w = 0; w < W; ++w) cin >> field[h][w];

//         // 探索開始
//         int count = 0;
//         for (int h = 0; h < H; ++h) {
//             for (int w = 0; w < W; ++w) {
//                 if (field[h][w] == 0) continue; // 残島じゃなかったらスルー
//                 dfs(h, w);
//                 ++count;
//             }
//         }
//         cout << count << endl;
//     }
// }





Measured memory_bytes: 3252
#include <iostream>
#include <bits/stdc++.h>
#include <iomanip>
#include<math.h>
# define M_PI           3.14159265358979323846  /* pi */
#define ll long long
#define ld long  double
int max(long long int array[],long long int n );
using namespace std;
int  main(){
  ios_base::sync_with_stdio(0);
  	cin.tie(0);
  	cout.tie(0);
double a;
cin>>a;
cout<<fixed<<setprecision(10)<<2*M_PI*a<<endl;


  }


Measured memory_bytes: 3796
#include <stdio.h>

int main(){
  int n,i,flag=0,count=0;
  int a[200];
  
  scanf("%d",&n);
  for(i=0;i<n;i++){
    scanf("%d",&a[i]);
  }
  
  while(flag==0){
    for(i=0;i<n;i++){
      if(a[i]%2==1){
        flag=1;
      } else {
        a[i]=a[i]/2;
      }
    }
    if(flag==0)count++;
  }
  printf("%d",count);
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i = 0;i<n;i++)
using ll = long long;
using P = pair<ll,ll>;
#define PI 3.141592653589793238
 
int main (){
  double n;cin>>n;
  cout <<fixed << setprecision(10)<< 2*n*PI << endl;
}


Measured memory_bytes: 3784
#include <iostream>
#include <algorithm>
#include <functional>
#include <vector>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <string>
#include <numeric>
#include <cmath>

#define rep(i, n) for (int i = 0; i < n; i++)
using namespace std;
typedef long long ll;
typedef vector<int> vec;
typedef vector<vector<int>> mat;
using P = pair<ll, ll>;

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

const ll MOD = 1000000007;
const int INF = 1<<29;

int main(){
  int N; cin >> N;
  vector<int> P(N);
  rep(i, N) cin >> P[i];

  int min = INF;
  int res = 0;
  for (int i = 0; i < N; ++i){
    if (min >= P[i]) res++;
    chmin(min, P[i]);
  }
  cout << res << endl;
}


Measured memory_bytes: 1024
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()))
    total = 0
    for i,j in zip(b,a):
        total += i*j
    total += c
    if total > 0:ans+=1
print(ans)

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

using namespace std;

int a[100007] = {};
bool dp[100007] = {};

int main() {
	
	int i,j;
	int N,K;
	
	cin >> N >> K;
	for( i=1; i<=N; i++) {
		cin >> a[i];
	}
	
	for( i=0; i<=K; i++) {
		bool flag = 0;
		for( j=1; j<=N; j++) {
			if( i - a[j] >= 0 && !dp[ i-a[j] ])
				flag = 1;
		}
		dp[i] = flag;
	}
	
	if( dp[K])
		printf("First\n");
	else
		printf("Second\n");
	
	return 0;
} 

Measured memory_bytes: 3700
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define repr(i, n) for(int i = ((int)(n) - 1); i >= 0; i--)
#define repn(i, n) for(int i = 1; i <= (int)(n); i++)
#define reprn(i, n) for(int i = ((int)(n)); i > 0; i--)
#define all(x) (x).begin(), (x).end()
using llint = long long int;
using lint = long int;

#include <iostream>
#include <array>
#include <string>
#include <algorithm>
#include <vector>
#include <iomanip>
#include <numeric>
using namespace std;

int gcd(int a, int b) {
	while (true) {
		if (a < b) {
			swap(a, b);
		}
		if (b == 0) {
			break;
		}
		a %= b;
	}
	return a;
}

int main() {
	int n;
	cin >> n;
	vector<lint> a(n);
	rep(i, n) {
		cin >> a[i];
	}
	int max_a = a[0];
	int max_b = a[1];
	int max_c = gcd(a[0], a[1]);
	for (int i = 2; i < n; i++) {
		max_a = max(gcd(a[i], max_a), gcd(a[i], max_b));
		max_b = max_c;
		max_c = gcd(max_c, a[i]);
	}
	cout << max({max_a, max_b, max_c}) << endl;
	
	return 0;
}

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

int main()
{
    long long H, W;
    cin >> H >> W;

    long long total = H * W;
    long long ans = 1e18;
    long long a, b, c;
    for (long long i = 1; i <= H; i++)
    {
        a = i * W;
        if ((total - a) % 2 == 0)
        {
            b = (total - a) / 2;
        }
        else
        {
            b = (H - i) * (W / 2);
        }
        c = total - a - b;
        long long S_max = max(a, max(b, c));
        long long S_min = min(a, min(b, c));
        ans = min(ans, S_max - S_min);
    }

    for (long long i = 1; i <= W; i++)
    {
        a = i * H;
        if ((total - a) % 2 == 0)
        {
            b = (total - a) / 2;
        }
        else
        {
            b = (W - i) * (H / 2);
        }
        c = total - a - b;
        long long S_max = max(a, max(b, c));
        long long S_min = min(a, min(b, c));
        ans = min(ans, S_max - S_min);
    }

    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define GET_MACRO(_1,_2,_3,_4,_5,NAME,...) NAME
#define pr(...) GET_MACRO(__VA_ARGS__,pr5,pr4,pr3,pr2,pr1)(__VA_ARGS__)
#define pr1(a) (#a)<<"="<<(a)
#define pr2(a,b) pr1(a)<<", "<<pr1(b)
#define pr3(a,b,c) pr2(a,b)<<", "<<pr1(c)
#define pr4(a,b,c,d) pr3(a,b,c)<<", "<<pr1(d)
#define pr5(a,b,c,d,e) pr4(a,b,c,d)<<", "<<pr1(e)
#define int long long
#define double long double
using namespace std;
const int N = 100010;
const int INF = 1LL<<55;
const int mod = (1e9)+7;
const double EPS = 1e-8;
const double PI = 6.0 * asin(0.5);
typedef pair<int,int> P;
typedef long long ll;
template<class T> T Max(T &a,T b){return a=max(a,b);}
template<class T> T Min(T &a,T b){return a=min(a,b);}
ostream& operator<<(ostream& o,P p){return o<<"("<<p.first<<","<<p.second<<")";}
istream& operator>>(istream& i,P &p){return i>>p.first>>p.second;}
ostream& operator<<(ostream& o,vector<auto> &a){int i=0;for(auto t:a)o<<(i++?" ":"")<<t;return o;}
istream& operator>>(istream& i,vector<auto> &a){for(auto &t:a)i>>t;return i;}
void prArr(auto a,string s=" "){int i=0;for(auto t:a)cout<<(i++?s:"")<<t;cout<<endl;}


signed main(){
  int n,A,B;
  cin>>n>>A>>B;
  vector<int> X(n);
  cin>>X;
  
  int ans = 0;
  for(int i=1;i<n;i++){
    ans += min(A*(X[i]-X[i-1]), B);
  }

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


Measured memory_bytes: 1024
#include <iostream>

int main(){
    int a,b,c;
    std::cin >> a >> b >> c;
    std::string s="No";
    if(a==b){
        if(b==c){
            s="No";
        } else {
            s="Yes";
        }
    } else {
        if(a==c){
            s="Yes";
        } else if(b==c){
            s="Yes";
        } else {
            s="No";
        }
    }
    
    std::cout << s << std::endl;
    return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<math.h>
#include<map>
#include<functional>
#include<queue>
using namespace std;
int main(){
    int x,y,z;
    cin>>x>>y>>z;
    cout<<(x-z)/(z+y)<<endl;
}



Measured memory_bytes: 256
#include<iostream>
using namespace std; //or std::cin et al.

int main() {
	int w,h;
	
	while (1) {
	    cin >> h >> w;
		if ( w == 0 && h == 0 ) {
			break;
		}
		for ( int i = 0; i < h; i++ ) {
	        for ( int j = 0; j < w; j++ ) {
	        	if ( i == 0 || i == h - 1 || j == 0 || j == w - 1 ) {
	        		cout << "#";
	        	} else {
	    	        cout << ".";
	        	}
	        }
	        cout << "\n";
        }
        cout << endl;
	}
	return 0;
}


Measured memory_bytes: 3132
#include<iostream>
#include<algorithm>
#include<stack>
using namespace std;
int coun=0;
long long T;
bool is_357(long long r)
{
    int j=0,i,cou[3]={3,7,5};
    while(r)
    {
        i=r%10;
        for(int p=0;p<3;p++)
            if(i==cou[p])
            {
                cou[p]=10;
                j++;
            }
        r/=10;
    }
    if(j==3)
        return true;
    return false;
}
void dfs(long long t)
{
    if(t<=T)
    {
        if(is_357(t))
        {
            coun++;
        }
        dfs(t*10+3);
        dfs(t*10+5);
        dfs(t*10+7);
    }
}
int main()
{
    scanf("%lld",&T);
    dfs(0);
    printf("%d\n",coun);
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <queue>
#include <climits>
#include <functional>
#include <array>

using namespace std;
int N;

static const int K = 1000000007;

int main(){
	
	cin >> N ;

	int64_t mod = 1 % K;
	for (int i = 2; i <= N; ++i) {
		mod = (mod * i) % K;
#ifdef _DDD
//		cout << i << " : " << mod << endl;
#endif
	}

	cout << mod << endl;

	return 0;
}



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

using namespace std;

bool knew[101][101];
int pat[101];
int main(){
    int n,m,k,p;

    while(cin >> n && n){
        memset(knew, 0, sizeof(knew));
        memset(pat,0,sizeof(pat));
        for(int i=0;i<n;i++){
            cin >> m;
            for(int j=0;j<m;j++){
                cin >> p;
                knew[i][p] = true;
            }
        }
        cin >> k;
        for(int i=0;i<k;i++){
            cin >> p;
            pat[i] = p;
        }

        int cand=-1;
        bool sus;
        for(int i=0;i<n;i++){
            sus = true;
            for(int j=0;j<k;j++){
                if(knew[i][pat[j]] == false){
                    sus = false;
                    break;
                }
            }
            if(sus){
                if(cand == -1){
                    cand = i+1;
                }else{
                    cand = -1;
                    break;
                }
            }
        }
        cout << cand << endl;
    }
}

Measured memory_bytes: 876
#include <bits/stdc++.h>
#define rep(i, n) for (int i=0; i<(int)(n); i++)
#define all(v) v.begin(), v.end()
using namespace std;
using ll = long long;
using Graph = vector<vector<int>>;
const ll MOD = 1000000007;
const ll INF = 10000000000000000;
vector<int> x4 = {0, 1, 0, -1}, x8 = {0, 1, 1, 1, 0, -1, -1, -1};
vector<int> y4 = {1, 0, -1, 0}, y8 = {1, 1, 0, -1, -1, -1, 0, 1};
template<class T> struct edge { int from, to; T cost;};
template<class T> inline bool chmin(T& a, T b){if (a>b){a = b; return true;}return false;}
template<class T> inline bool chmax(T& a, T b){if (a<b){a = b; return true;}return false;}
template<class T> inline T powerM(T a,T b){if (b==0) return 1;
T tmp = powerM(a,b/2); if (b%2==0) return tmp*tmp%MOD; else return tmp*tmp%MOD*a%MOD; }
template<class T> inline T power(T a,T b,T m){ if (b==0) return 1;
  T tmp = power(a,b/2,m); if (b%2==0) return tmp*tmp%m; else return tmp*tmp%m*a%m; }
template<class T> inline T gcd(T a, T b){if (b==0) return a; return gcd(b, a%b);}
template<class T> inline T lcm(T a, T b){return a / gcd(a,b) * b;}
// ax+by=gcd(a,b)を解く
template<class T> inline T extgcd(T a,T b,T &x,T &y){if (b==0){x=1; y=0; return a;} T d=extgcd(b,a%b,y,x); y -= a/b*x; return d;}
void hey(){ cout <<"hey" <<endl; }


void priv(vector<int> &a){
  int N = a.size();
  rep(i, N){
    cout <<a[i];
    if (i == N-1) cout <<endl;
    else cout <<" ";
  }
}

int bubbleSort(vector<int> &a, int N){
  int res = 0;
  bool flag = true;
  while (flag){
    flag = false;
    for (int j=N-1; j>=1; j--){
      if (a[j] < a[j-1]){
        swap(a[j], a[j-1]);
        res++;
        flag = 1;
      }
    }
  }
  priv(a);
  return res;
}

int selectionSort(vector<int> &a, int N){
  int res = 0;
  for (int i=0; i<N; i++){
    int minj = i;
    for (int j=i; j<N; j++){
      if (a[j] < a[minj]) minj = j;
    }
    if (a[i] > a[minj]) res++;
    swap(a[i], a[minj]);
  }
  priv(a);
  return res;
}


int main() {
  int N; cin >>N;
  vector<int> a(N); rep(i, N) cin >>a[i];
  cout <<selectionSort(a, N) <<endl;
}


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

vector<ll>v;

int main()
{
	ll n, i, ans, x;

	cin>>n;

	for(i=1; i<=n; i++)
	{
		cin>>x;
		v.push_back(x);
	}
	sort(v.begin(),v.end());
	v.resize(unique(v.begin(),v.end())-v.begin());
	if(v.size()==n)cout<<"YES"<<endl;
	else{
		cout<<"NO"<<endl;
	}
}

Measured memory_bytes: 2420
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt() + 1;
        List<Long> leaf = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            leaf.add(sc.nextLong());
        }
        List<Long> accLeaf = new ArrayList<>();
        accLeaf.add(0L);
        long acc  = 0L;
        for (int i = 0; i < n; i++) {
            acc += leaf.get(i);
            accLeaf.add(acc);
        }

        long  ans = 1;
        long  nonLeaf;
        long  vertexes = 1;
        for (int i = 1; i < n; i++) {
            nonLeaf = vertexes - leaf.get(i-1);
            if (nonLeaf <= 0) {
                System.out.println(-1);
                return;
            }
            vertexes = Math.min(2*nonLeaf, accLeaf.get(n)-accLeaf.get(i));
            ans += vertexes;
        }
        if (vertexes != leaf.get(n-1)) {
            System.out.println(-1);
            return;
        }
        System.out.println(ans);
    }
}


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

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

    for(int i = 0;i*4 <= N;i++){
        for(int j=0;i*4+j*7 <=N;j++){
            if(i == 0 && j== 0)continue;
            if(N%(i*4+j*7) == 0){
                cout << "Yes" << endl;
                return 0;
            }
        }
    }
    cout << "No" << endl;

    return 0;
}

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

int main() {
    int N;
    while (cin >> N, N) {
        if (N < 19) cout << 13 << endl;
        else {
            for (int i = (N-19)/30; i > -1; i--) {
                int num = (i*30+19);
                int sq = sqrt((N-19)/30*30+19);
                bool flag = true;
                for (int j = 2; flag && j <= sq; j++) {
                    if (num - 8 > 0 && ((num-8)%j==0 || (num-6)%j==0 || (num-2)%j==0 || num%j==0)) flag = false;
                }
                if (flag) {
                    cout << num << endl;
                    break;
                }
            }
        }
    }

    return 0;
}

Measured memory_bytes: 3080
#include <bits/stdc++.h> //abc148b
using namespace std;
typedef long long ll;
int main() {
    int n;
    cin >> n;
    string s;
    cin >> s;
    int ans = 0;
    for (int i = 0; i < n / 2; i++) {
        if (s[i] == s[i + n / 2]) {
            ans++;
        }
    }
    if (n % 2 == 1) {
        cout << "No" << endl;
    } else if (n % 2 == 0 && ans == n / 2) {
        cout << "Yes" << endl;
    } else if (n % 2 == 0 && ans != n / 2) {
        cout << "No" << endl;
    }
    return 0;
}

Measured memory_bytes: 3592
import numpy as np

class MyClass:
    def __init__(self):
        self.sum = 0

    def water(self, H):
        if len(H)<=0:
            return
        min_h = np.min(H)
        self.sum += min_h
        H -= min_h
        on = False
        for i in range(len(H)):
            if not on:
                if H[i]>0:
                    st = i
                    on = True
                else:
                    continue
            else:
                if H[i]>0:
                    continue
                else:
                    ed = i
                    on = False
                    self.water(H[st:ed])
        if on:
            self.water(H[st:])
        return


def main():
    N = int(input())
    H = np.array([int(x) for x in input().split()]) # Length of N
    my_class = MyClass()
    my_class.water(H)
    print(my_class.sum)

if __name__=='__main__':
    main()

Measured memory_bytes: 12392
#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
using namespace std;

int main() {
  int n;
  cin >> n;
  vector<vector<int> > points(n); // points[igame][iplayer]
  for(int i = 0; i < n; ++i) {
    for(int j = 0; j < 3; ++j) {
      int p;
      cin >> p;
      points[j].push_back(p);
    }
  }
  vector<int> players(n, 0);
  for(int igame = 0; igame < 3; ++igame) {
    set<int> decided;
    for(int iplayer = 0; iplayer < n; ++iplayer) {
      auto currentGamePoints = points[igame];
      if(count(decided.begin(), decided.end(), iplayer) >= 1) continue;
      decided.insert(iplayer);
      int fplayer = iplayer;
      bool flag = false;
      while(true) {
        auto itr = find(currentGamePoints.begin() + fplayer + 1, currentGamePoints.end(), currentGamePoints[iplayer]);
        fplayer = distance(currentGamePoints.begin(), itr);
        if(fplayer == currentGamePoints.size()) {
          if(!flag) players[iplayer] += currentGamePoints[iplayer];
          break;
        } else {
          flag = true;
          decided.insert(fplayer);
        }
      }
    }
  }
  for(auto i = players.begin(); i != players.end(); ++i) cout << *i << endl;
  return 0;
}

Measured memory_bytes: 1236
#include <bits/stdc++.h>
#define int long long
#define vi vector <int>
#define si set <int>
#define mii map <int,int>
#define pii pair <int,int>
#define endl "\n"
#define ZERO 0ll
#define FOR(P,Q) for(int P=0;P<(Q);P++)
#define FORR(P,Q) for(int P=1;P<=(Q);P++)
#define rep(P,R,Q) for(int P=(R);P<=(Q);P++)
#define repb(P,R,Q) for(int P=(R);P>=(Q);P--)
#define pb push_back
#define eb emplace_back
typedef long long ll;
typedef long double ld;
using namespace std;


    
int32_t main()
{
	ios_base::sync_with_stdio(0);
	cout.tie(0);
	cin.tie(0);
	#ifndef ONLINE_JUDGE
	freopen("error.txt","w",stderr);
	#endif
	//change ll to int before using string builtin operations
	int tces=1;
	//cin>>tces;
	while(tces--){
		string a,b,s;
		cin>>s;
		int i=s.length();
		FOR(j,(i-1)/2){
			a+=s[j];
		}
		rep(j,(i+3)/2-1,i-1){
			b+=s[j];
		}
		string a1,b1,s1;
		FOR(j,a.length()){
			a1+=a[j];
		}
		FOR(j,b.length()){
			b1+=b[j];
		}
		FOR(j,s.length()){
			s1+=s[j];
		}
		reverse(a.begin(),a.end());
		reverse(b.begin(),b.end());
		reverse(s.begin(),s.end());
		// cout<<a1<<" "<<a<<" "<<b1<<" "<<b<<" "<<s1<<" "<<s<<endl;
		if(a==a1&&b==b1&&s==s1){
			cout<<"Yes";
		}
		else cout<<"No";
		
	}
	
return 0;
}

Measured memory_bytes: 256
#include<iostream>
using namespace std;
int main(){
	long long A,B,C,x,y;
	cin>>A>>B>>C>>x>>y;
	if(A+B<=C*2)
		cout<<A*x+B*y;
	else
		if(x>y)
			cout<<min(2*y*C+A*(x-y),2*C*x);
		else
			cout<<min(2*x*C+B*(y-x),2*C*y);
	return 0;
}

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

using namespace std;

int x[100];
long long dp[100][100][5000];

int main() {

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

    int n, A;
    cin >> n >> A;
    for (int i = 0; i < n; i ++) cin >> x[i];
    dp[0][0][0] = 1;
    for (int i = 0; i < 50; i ++) {
        for (int j = 0; j < 50; j ++) {
            for (int k = 0; k < 5000; k ++) {
                if (dp[i][j][k] == 0) continue;
                dp[i + 1][j + 1][k + x[i]] += dp[i][j][k];
                dp[i + 1][j][k] += dp[i][j][k];
            }
        }
    }
    long long ans = 0;
    for (int i = 1; i <= n; i ++) {
        ans += dp[n][i][i * A];
    }
    cout << ans << endl;
}

Measured memory_bytes: 151808
import java.util.Scanner;

public class Main {
	public static void main(String[] args)  {
		Scanner sc = new Scanner((System.in));
		long n = sc.nextLong();
		int min = String.valueOf(n).length();;
		int tmp = 0;
		for(long i = 1; i * i <= n; i++) {
			if(n%i == 0) {
				tmp = F(i, n/i);
				if(min > tmp) {
					min = tmp;
				}
			}
		}
		System.out.println(min);
	}

	public static int F(long a, long b) {
		if(a > b) {
			return String.valueOf(a).length();
		}else {
			return String.valueOf(b).length();
		}
	}
}

Measured memory_bytes: 22996
#include<stdio.h>
#include<math.h>
typedef struct{
  double x;
  double y;
}Point;
void kock(int,Point,Point);
int main(){
  int x;
  Point A,B;
  scanf("%d",&x);
  A.x=0;
  A.y=0;
  B.x=100;
  B.y=0;
  printf("%.8f %.8f\n",A.x,A.y);
  kock(x,A,B);
  printf("%.8f %.8f\n",B.x,B.y);
  return 0;
}
void kock(int x,Point A,Point B){
  Point s,t,u;
  double theta;
  theta=M_PI*60.0/180.0;
  if(x==0)
    return;
  s.x=(2*A.x+B.x)/3;
  s.y=(2*A.y+B.y)/3;
  t.x=(A.x+2*B.x)/3;
  t.y=(A.y+2*B.y)/3;
  u.x=(t.x-s.x)*cos(theta)-(t.y-s.y)*sin(theta)+s.x;
  u.y=(t.x-s.x)*sin(theta)+(t.y-s.y)*cos(theta)+s.y;
  kock(x-1,A,s);
  printf("%.8f %.8f\n",s.x,s.y);
  kock(x-1,s,u);
  printf("%.8f %.8f\n",u.x,u.y);
  kock(x-1,u,t);
  printf("%.8f %.8f\n",t.x,t.y);
  kock(x-1,t,B);
}



Measured memory_bytes: 2108
import java.util.Scanner;


public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();

		int[][] A = new int[2][N];
		for(int i = 0 ; i < 2 ; i++){
			for(int j = 0 ; j < N ; j++){
				A[i][j] = sc.nextInt();
			}
		}
		sc.close();
		int ans = 0;
		int tmp = 0;
		for(int i = 0 ; i < N ; i++){
			for(int j = 0 ; j <=i ; j++){
				tmp += A[0][j];
			}
			for(int k = i ; k < N ; k++){
				tmp += A[1][k];
			}

			ans = Math.max(ans, tmp);

			tmp = 0;
		}

		System.out.println(ans);


	}
}


Measured memory_bytes: 22608
#include<bits/stdc++.h>
using namespace std;
long long n,dem = 0;
int main()
{
  cin >> n;
  while(n >= 5)
  {
    if(n >= 500)
    {
      dem = dem + 1000 * (n / 500);
      n %= 500;
    }
    else
    {
      dem = dem + 5 * (n / 5);
      n %= 5;
    }
  }
  cout << dem ;
  return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
typedef long long ll;
struct node{
	ll l,r;
}a[100000+20];
bool cmp(node a,node b)
{
	if(a.r==b.r)
		return a.l<b.l;
	return a.r<b.r;
}
int main ()
{
	ll n,m,i;
	scanf("%lld%lld",&n,&m);
	for(i=0;i<m;i++)
		scanf("%lld %lld",&a[i].l,&a[i].r);
	ll mn=a[0].r;
	for(i=0;i<m;i++)
		mn=min(a[i].r,mn);
	sort(a,a+m,cmp);
	ll now=mn,ans=1;
	for(i=1;i<m;i++)
	{
		if(a[i].l>=now)
		{
			now=a[i].r;
			ans++;
		}
	//	printf("%lld\n",now);
	}
	printf("%lld\n",ans);
	return 0;
}

Measured memory_bytes: 1792
from collections import deque    

def cnt(aa):
    for i in range(3):
        if aa[i]!=0 and aa[i]==aa[i+1] and aa[i+1]==aa[i+2]:
            n=aa[i]
            j=i
            k=3
            if i+3<5 and aa[i+2]==aa[i+3]:
                k=4
                if i+4<5 and aa[i+3]==aa[i+4]:
                    k=5
            return n,j,k                             
    return 0,0,0                        
                             
while True:
    h=int(input())
    if h==0:
        break
    a=[[0]*5 for i in range(h)]
    for i in range(h):
        a[i]=list(map(int,input().split()))
#    a=[[5, 9, 5, 5, 9], [5, 5, 6, 9, 9], [4, 6, 3, 6, 9], [3, 3, 2, 9, 9], [2, 2, 1, 1, 1]]
    a.reverse()
#    print(a)
    p=0
    while True:
        dq = deque()
        for i in range(h):
            n,j,k=cnt(a[i])
            p+=n*k
            if n!=0:
                dq.append((i,j,k))
#        print(dq)
        if len(dq)==0 :
            break
        while dq:
            hi,j,k=dq.popleft()
#            print("1:",a)
            for jj in range(j,j+k):
                a[hi][jj]=0
#        print("2:",a)
        for jj in range(5):
            for ii in range(h):
                if a[ii][jj]==0:
                    for iii in range(ii+1,h):
                        if a[iii][jj]!=0:
                            a[ii][jj]=a[iii][jj]
                            a[iii][jj]=0
                            break
#        print(a)
    print(p)
    
                


Measured memory_bytes: 6012
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
//template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
//template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }

/* attention
    long longのシフト演算には気をつけよう
    タイポした時のデバッグが死ぬほどきつくなるので変数名は最低3字くらい使った方がいいかも
*/

bool isPrime(int n){
    for(int i=2; i*i<=n; i++) if(n%i == 0) return false;

    return true;
}

int main(){
    int N; cin >> N;
    int ans = 0;
    for(int i=0; i<N; i++){
        int a; cin >> a;
        if(isPrime(a)) ans++;
    }

    cout << ans << endl;
}


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

using namespace std;
#define int long long
const int N = 1e5 + 5;
int a[N], val = 1;
vector <int> g[N];

int dfs(int v, int p = 0) {
    int sum = 0, mx = 0;
    for (int u : g[v]) if (u != p) {
        int w = dfs(u, v);
        mx = max(mx, w), sum += w;
    }
    int res = a[v] - sum;
    if (res < 0 || (p == 0 && res != 0)) val = 0;
    if (g[v].size() > 1 && a[v] < max(mx, res)*2) val = 0;
    return res;
}

int32_t main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int n; cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 0; i < n - 1; i++) {
        int u, v; cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    int root = 0, res = 0;
    for (int i = 1; i <= n; i++) {
        if (g[i].size() > 1) root = i, a[i]<<=1;
        else res += a[i];
    }
    dfs(root);
    if (res % 2 == 1) val = 0;
    if (root == 0) val = (a[1] == a[2]);
    cout << (val ? "YES\n" : "NO\n");

    return 0;
}


Measured memory_bytes: 12160
#include <bits/stdc++.h>
#define rep(i,n)for(int i=0;i<(n);i++)
using namespace std;
 
int main(){
    int a,b,c;scanf("%d%d%d",&a,&b,&c);
    if(a+b<c)puts("NA");
    else printf("%d\n",max(0,c-a));
}


Measured memory_bytes: 3208
from collections import Counter

N = int(input())
D = list(map(int, input().split()))
c = Counter(D)

# 根は0である必要がある。
if D[0] != 0:
    print(0)
    exit(0)
# 0が1つでない場合の答えは0になる
if c[0] != 1:
    print(0)
    exit(0)

MOD = 998244353
cnt = 1
for i in range(1, max(D)+1):
    cnt *= pow(c[i-1], c[i], MOD)
print(cnt % MOD)


Measured memory_bytes: 24132
#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<cmath>
#include<map>
#include<iomanip>
#include<queue>
#include<stack>
#include<time.h>
#define rep(i,n)for(int i=0;i<n;i++)
#define int long long
#define ggr getchar();getchar();return 0;
#define prique priority_queue
#define mod 1000000007
#define inf 1e15
#define key 1e9
using namespace std;
typedef pair<int, int>P;
void yes() { cout << "Yay!" << endl; }
void no() { cout << ":(" << endl; }
template<class T> inline void chmax(T& a, T b) {
	a = std::max(a, b);
}
template<class T> inline void chmin(T& a, T b) {
	a = std::min(a, b);
}
bool prime(int n) {
	int cnt = 0;
	for (int i = 1; i <= sqrt(n); i++) {
		if (n % i == 0)cnt++;
	}
	if (cnt != 1)return false;
	else return n != 1;
}
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 kai(int x, int y) {
	int res = 1;
	for (int i = x - y + 1; i <= x; i++) {
		res *= i; res %= mod;
	}
	return res;
}
int mod_pow(int x, int y, int m) {
	int res = 1;
	while (y) {
		if (y & 1) {
			res = res * x % m;
		}
		x = x * x % m;
		y >>= 1;
	}
	return res;
}
int comb(int x, int y) {
	if (y > x)return 0;
	return kai(x, y)* mod_pow(kai(y, y), mod - 2, mod) % mod;
}
void debug_out() { cerr << endl; }

template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
	cerr << " " << to_string(H);
	debug_out(T...);
}

#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
struct edge { int to, cost; };
int par[114514], rrank[114514];//親、木の深さ
void init(int n) {
	rep(i, n) {
		par[i] = i;
		rrank[i] = 0;
	}
}
int find(int x) {
	if (par[x] == x) {
		return x;
	}
	else return par[x] = find(par[x]);
}
void unite(int x, int y) {
	x = find(x);
	y = find(y);
	if (x == y)return;
	if (rrank[x] < rrank[y]) {
		par[x] = y;
	}
	else {
		par[y] = x;
		if (rrank[x] == rrank[y])rrank[x]++;
	}
}
bool same(int x, int y) {
	return find(x) == find(y);
}
int n;
int memo[9];
int a[9], b[9];
signed main() {
	cin >> n;
	rep(i, n)cin >> a[i];
	rep(i, n)cin >> b[i];
	rep(i, n)memo[i] = i + 1;
	int cnt = 0, p, q;
	do {
		cnt++;
		int m1 = 0, m2 = 0;
		rep(i, n) {
			if (a[i] == memo[i])m1++;
			if (b[i] == memo[i])m2++;
		}
		if (m1 == n)p = cnt;
		if (m2 == n)q = cnt;
	} while (next_permutation(memo, memo + n));
	cout << abs(p - q) << endl;
	ggr
}

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

class Main {

	public static void main(String[] args) throws IOException {

		BufferedReader br = null;
		InputStreamReader is = null;

		try {

			br = new BufferedReader(is = new InputStreamReader(System.in));

			String[] sentence = br.readLine().split(" ");
			int x = 0;
			int max = 0;
			String word = null;
			String longWord = sentence[0];

			for (int i = 0; i < sentence.length; i++) {

				for (int j = 0; j < sentence.length; j++) {

					if (sentence[i].equals(sentence[j])) {

						x++;

					}
					if (longWord.length() < sentence[j].length()) {

						longWord = sentence[j];

					}

				}
				if (max < x) {

					max = x;
					word = sentence[i];

				}

				x = 0;

			}


			System.out.println(word + " " + longWord);

		} finally {
			br.close();
			is.close();

		}
	}
}

Measured memory_bytes: 16900
n,m=map(int,input().split())
l=[]
for i in range(m):
  p,y=map(int,input().split())
  l.append([p,y,i])
l.sort()
y=[]
q=l[0][0]
r=0
for i in range(m):
  x=''
  if q==l[i][0]:
    r+=1
  else:
    r=1
    q=l[i][0]
  x+='0'*(6-len(str(l[i][0])))+str(l[i][0])
  x+='0'*(6-len(str(r)))+str(r)
  y.append([l[i][2],x])
y.sort()
for i in range(m):
  print(y[i][1])

Measured memory_bytes: 41136
#include <bits/stdc++.h>
#define REP(i, a, n) for (ll i = ((ll) a); i < ((ll) n); i++)
using namespace std;
typedef long long ll;

ll N, X;
ll p[51], q[51];
ll ans;

void dfs(ll n, ll t) {
  if (n == 0) {
    return;
  }

  if (t + 1 <= X && X < t + 1 + q[n - 1]) {
    dfs(n - 1, t + 1);
  } else if (t + 1 + q[n - 1] == X) {
    ans += p[n - 1];
  } else if (t + 1 + q[n - 1] + 1 <= X && X < t + 1 + q[n - 1] + 1 + q[n - 1]) {
    ans += p[n - 1] + 1;
    dfs(n - 1, t + 1 + q[n - 1] + 1);
  } else if (t + 1 + q[n - 1] + 1 + q[n - 1] <= X) {
    ans += p[n - 1] + 1 + p[n - 1];
  }
}

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

  p[0] = q[0] = 1;
  REP(i, 0, N) {
    p[i + 1] = p[i] * 2 + 1;
    q[i + 1] = q[i] * 2 + 3;
  }

  dfs(N, 0);
  cout << ans << endl;
}

Measured memory_bytes: 256
use std::io::*;
const MOD: u64 = 998244353;

mod segment_tree {
    pub struct SegmentTree<T, F> {
        size: usize,
        data: Vec<T>,
        identity: T,
        operation: F,
    }
    impl<T: Copy + Clone, F: Fn(T, T) -> T> SegmentTree<T, F> {
        pub fn new(n: usize, id: T, op: F) -> SegmentTree<T, F> {
            let mut size = 1;
            while size < n {
                size <<= 1;
            }
            SegmentTree {
                size: size,
                data: vec![id; size * 2],
                identity: id,
                operation: op,
            }
        }
        pub fn update(&mut self, mut i: usize, x: T) {
            i += self.size;
            self.data[i] = x;
            i >>= 1;
            while i > 0 {
                self.data[i] = (self.operation)(self.data[i * 2], self.data[i * 2 + 1]);
                i >>= 1;
            }
        }
        pub fn query(&self, mut l: usize, mut r: usize) -> T {
            let mut a = self.identity;
            let mut b = self.identity;
            l += self.size;
            r += self.size;
            while l < r {
                if (l & 1) == 1 {
                    a = (self.operation)(a, self.data[l]);
                    l += 1;
                }
                if (r & 1) == 1 {
                    r -= 1;
                    b = (self.operation)(self.data[r], b);
                }
                l >>= 1;
                r >>= 1;
            }
            (self.operation)(a, b)
        }
    }
}

fn lower_bound<T: PartialOrd>(x: T, a: &Vec<T>) -> usize {
    let mut l: usize = 0;
    let mut r: usize = a.len();
    while r != l {
        let mid = (l + r) >> 1;
        if a[mid] < x {
            l = mid + 1;
        } else {
            r = mid;
        }
    }
    l
}

fn main() {
    let mut s: String = String::new();
    std::io::stdin().read_to_string(&mut s).ok();
    let mut itr = s.trim().split_whitespace();
    let n: usize = itr.next().unwrap().parse().unwrap();
    let mut a: Vec<(i64, i64)> = (0..n)
        .map(|_| {
            (
                itr.next().unwrap().parse().unwrap(),
                itr.next().unwrap().parse().unwrap(),
            )
        })
        .collect();
    a.sort();

    let mut x: Vec<i64> = vec![0; n];
    let mut d: Vec<i64> = vec![0; n];
    for i in 0..n {
        x[i] = a[i].0;
        d[i] = a[i].1;
    }
    // dp: iを選ぶ時、選ばない時で遷移
    // 選ばない時はi+1に遷移
    // iを選んだ時は同時に動く最大のもの+1に遷移
    // 同時に動く最大のもの: 再帰的に動きは起こるので、後ろから決めていく
    let mut st = segment_tree::SegmentTree::new(n, 0, std::cmp::max);
    let mut to: Vec<usize> = (0..n).collect();
    for i in (0..n).rev() {
        let j = lower_bound(x[i] + d[i], &x);
        if j > i + 1 {
            to[i] = st.query(i, j);
        }
        st.update(i, to[i]);
    }

    let mut dp: Vec<u64> = vec![0; n + 1];
    dp[0] = 1;
    for i in 0..n {
        dp[i + 1] = (dp[i + 1] + dp[i]) % MOD;
        dp[to[i] + 1] = (dp[to[i] + 1] + dp[i]) % MOD;
    }
    println!("{}", dp[n]);
}


Measured memory_bytes: 25848
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using vi=vector<int>;

int main() {
    int H,W; cin>>H>>W;
    vector<vi> A(H,vi(W));
    for (int i = 0; i < H; i++){
        for (int j = 0; j < W; j++){
            cin>>A[i][j];
        }
    }
    for (int i = 0; i < H; i++){
        for (int j = 0; j < W; j++){
            int B; cin>>B;
            A[i][j]=abs(A[i][j]-B);
        }
    }
    vector<vector<vector<bool>>> dp(H,vector<vector<bool>>(W,vector<bool>(6401,false)));
    dp[0][0][A[0][0]]=true;
    for (int i = 0; i < H; i++){
        for (int j = 0; j < W; j++){
            if(i!=0){
                for (int k = 0; k <= 6400; k++){
                    if(dp[i-1][j][k] && k+A[i][j]<=6400)dp[i][j][k+A[i][j]]=true;
                    if(dp[i-1][j][k])dp[i][j][abs(k-A[i][j])]=true;
                }
            }
            if(j!=0){
                for (int k = 0; k <= 6400; k++){
                    if(dp[i][j-1][k] && k+A[i][j]<=6400)dp[i][j][k+A[i][j]]=true;
                    if(dp[i][j-1][k])dp[i][j][abs(k-A[i][j])]=true;
                }
            }
        }
    }
    for (int i = 0; i < 6401; i++){
        if(dp[H-1][W-1][i]){
            cout<<i<<endl;
            return 0;
        }
    }
}

Measured memory_bytes: 8808
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <iostream>
#include <queue>
# define ll long long
const int M = 100005 ;
using namespace std ;

inline int read(){
	char c = getchar() ; int x = 0 , w = 1 ;
	while(c>'9'||c<'0') { if(c=='-') w = -1; c= getchar() ;}
	while(c>='0'&&c<='9'){ x = x*10+c-'0' ; c = getchar() ;}
	return x*w ;
}
int n ;
int a[M] ;
ll Ans ;
inline ll Solve(int x){
	int tim = 0 ;
	while(x%2==0){
		x /= 2 ;
		++tim ;
	}
	return tim ;
}
int main(){
	n = read() ;
	for(int i=1;i<=n;i++) {
	    a[i] = read() ;
	    Ans += Solve(a[i]) ;
	}
	cout<<Ans<<endl ;
	return 0 ;
}

Measured memory_bytes: 256