akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
using namespace std;

struct UnionFind {
    vector<int> par; // par[i]:iの親の番号　(例) par[3] = 2 : 3の親が2

    UnionFind(int N) : par(N) { //最初は全てが根であるとして初期化
        for(int i = 0; i < N; i++) par[i] = i;
    }

    int root(int x) { // データxが属する木の根を再帰で得る：root(x) = {xの木の根}
        if (par[x] == x) return x;
        return par[x] = root(par[x]);
    }

    void unite(int x, int y) { // xとyの木を併合
        int rx = root(x); //xの根をrx
        int ry = root(y); //yの根をry
        if (rx == ry) return; //xとyの根が同じ(=同じ木にある)時はそのまま
        par[rx] = ry; //xとyの根が同じでない(=同じ木にない)時：xの根rxをyの根ryにつける
    }

    bool same(int x, int y) { // 2つのデータx, yが属する木が同じならtrueを返す
        int rx = root(x);
        int ry = root(y);
        return rx == ry;
    }
};

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

int main() {
    int H,W;
    cin>>H>>W;
    int ch,cw,dh,dw;
    cin>>ch>>cw>>dh>>dw;
    ch--;cw--;dh--;dw--;
    UnionFind u(1e7);
    char s[H][W];
    for(int i=0;i<H;++i){
        for(int j=0;j<W;++j){
            cin>>s[i][j];
        }
    }
    for(int i=0;i<H;++i){
        for(int j=0;j<W;++j){
            for(int k=0;k<4;++k){
                if(s[i][j]=='.'&&s[i+dx[k]][j+dy[k]]=='.'&&0<=i+dx[k]&&i+dx[k]<H&&0<=j+dy[k]&&j+dy[k]<W){
                    u.unite(i*W+j,(i+dx[k])*W+j+dy[k]);
                }
            }
        }
    }
    int d[H][W];
    for(int i=0;i<H;++i){
        for(int j=0;j<W;++j){
            if(s[i][j]=='.'){
                int x=u.root(i*W+j);
                d[i][j]=x;
            }
        }
    }
    vector<vector<int>>g(1e7);
    for(int i=0;i<H;++i){
        for(int j=0;j<W;++j){
            for(int k=-2;k<=2;++k){
                for(int l=-2;l<=2;++l){
                    if(0<=i+k&&i+k<H&&0<=j+l&&j+l<W&&s[i][j]=='.'&&s[i+k][j+l]=='.'&&d[i][j]!=d[i+k][j+l]){
                        g[d[i][j]].push_back(d[i+k][j+l]);
                        g[d[i+k][j+l]].push_back(d[i][j]);
                    }
                }
            }
        }
    }
    vector<int>ans(1e7,-1);
    queue<int>q;
    int x=u.root(ch*W+cw),y=u.root(dh*W+dw);
    ans[x]=0;
    q.push(x);
    while(!q.empty()){
        int v=q.front();
        q.pop();
        for(int nv:g[v]){
            if(ans[nv]!=-1)continue;
            ans[nv]=ans[v]+1;
            q.push(nv);
        }
    }
    cout<<ans[y]<<endl;
}


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

int main() {
  int D,N;
  cin >> D >> N;
  int s = 1;
  for(int i = 0;i < D;i++){
  s *= 100;
  }
  if(N < 100){
  cout << s*N;
  }
  else{
  cout << s*(N+1);
  }
}

Measured memory_bytes: 256
array = [1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51]

i = int(input())

print(array[i - 1])

Measured memory_bytes: 3060
#include<bits/stdc++.h>
using namespace std;
using Graph=vector<vector<int>>;
#define rep(i,n) for(int i=0;i<(int)(n);i++)
typedef long long 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;
}
int main(){
    int H1,M1,H2,M2,K;
    cin>>H1>>M1>>H2>>M2>>K;
    if(H2<H1){
        H2+=24;
    }
    cout<<(H2*60+M2)-(H1*60+M1)-K<<endl;
}


Measured memory_bytes: 3612
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <cstring>
#include <string>
#include <vector>
#include <random>
#include <bitset>
#include <queue>
#include <cmath>
#include <stack>
#include <set>
#include <map>
#define rep(i,n) for (int i=0; i<n;++i)
#define rep_down(i,n) for (int i=n-1; i>=0; --i)
typedef long long ll;
using namespace std;
int N;
const ll MOD = 1000000007LL;
ll ls, rs;

int main() {
    cin.sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    
    priority_queue<ll, vector<ll>, greater<ll> > left_pque;
    priority_queue<ll> right_pque;


    cin >> N;

    ll a[3*N];
    ll left_sum[N+1];
    ll right_sum[N+1];

    rep(i, N){
      ll b;
      cin >> b;
      a[i] = b;
      ls+=b;
      left_pque.push(b);
    } 
    rep(i, N) cin >> a[N+i]; 
    rep(i, N){
      ll b;
      cin >> b;
      a[2*N+i] = b;
      rs+=b;
      right_pque.push(b);
    }

    left_sum[0] = ls;
    rep(i, N){
      int trgt =a[N+i];
      ls+= trgt;
      left_pque.push(trgt);
      ll c = left_pque.top();
      ls -= c;
      left_pque.pop();
      left_sum[i+1] = ls;
    }

    right_sum[N] = rs;
    rep_down(i, N){ // N-1から0へ。
      int trgt =a[N+i];
      rs+=trgt;
      right_pque.push(trgt);
      ll c = right_pque.top();
      rs -= c;
      right_pque.pop();
      right_sum[i] = rs;
    }

    ll ans = (-1)* N * MOD;
    rep(i, N+1) ans = max(ans, left_sum[i] - right_sum[i]);
    cout << ans << endl;
    return 0;
}

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

using namespace std;

int main()
{
	int x1, y1, x2, y2;
	cin >> x1 >> y1 >> x2 >> y2;

	int x3, y3, x4, y4;
	x3 = x2 - (y2 - y1);
	y3 = y2 - (x1 - x2);
	x4 = x3 - (y3 - y2);
	y4 = y3 - (x2 - x3);
	cout << x3 << " " << y3 << " " << x4 << " " << y4 << endl;
	return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <string.h>
#include <vector>
#include <queue>
#include <cmath>
#include <bitset>
#include <complex>
#include <functional>
#include <numeric>
#include <iomanip>

// output
#define SPBR(w, n) std::cout<<(w + 1 == n ? '\n' : ' ');
#define YES cout << "YES" << endl
#define Yes cout << "Yes" << endl
#define NO cout << "NO" << endl
#define No cout << "No" << endl
// utility
#define ALL(i) (i).begin(), (i).end()
#define FOR(i, a, n) for(int i=(a);i<(n);++i)
#define RFOR(i, a, n) for(int i=(n)-1;i>=(a);--i)
#define REP(i, n) for(int i=0;i<int(n);++i)
#define RREP(i, n) for(int i=int(n)-1;i>=0;--i)
#define IN(a, x, b) (a<=x && x<b)
#define OUT(a, x, b) (x<a || b<=x)
template<class T> inline T chmax(T & a, const T b) { return a = (a < b) ? b : a; }
template<class T> inline T chmin(T& a, const T b) { return a = (a > b) ? b : a; }

// type/const
#define int ll
using ll = long long;
using ull = unsigned long long;
using ld = long double;
const int MOD = 1000000007;
/* const int MOD = 998244353; */
const int INF = 1e18;
const double PI = acos(-1);

using namespace std;
struct INIT { 
  INIT(){cin.tie(0); ios::sync_with_stdio(false);
  cout << fixed << setprecision(10);
}}INIT;

vector<pair<int, int>> primeFact(int n) {
  vector<pair<int, int>> res;
  for (int i = 2; i * i <= n; i++) {
    int divcnt = 0;
    if (n % i == 0) {
      do {
        divcnt++;
        n /= i;
      } while (n % i == 0);
      res.emplace_back(i, divcnt);
    }
  }
  if (n != 1)
    res.emplace_back(n, 1);
  return res;
}

signed main() {
  int A, B; 
  cin >> A >> B;

  vector<int> v;
  int C = __gcd(A, B);
  for(int i = 1; i*i <= C; i++){
    if(C%i == 0){
      v.emplace_back(i);
      if(i*i != C) v.emplace_back(C/i);
    }
  }

  int ans = 1;
  REP(i, v.size()){
    auto p = primeFact(v[i]);
    if(p.size() == 1 && p[0].second == 1) ans++;
  }

  cout << ans << "\n";

  return 0;
}

Measured memory_bytes: 384
#include <stdio.h>
#define MAX 10000
#define NIL -1

struct Node {int p,l,r;};
struct Node T[MAX];
int n;

void preParse(int u){
  if(u==NIL) return;
  printf(" %d",u);
  preParse(T[u].l);
  preParse(T[u].r);
}

void inParse(int u){
  if(u==NIL) return;
  inParse(T[u].l);
  printf(" %d",u);
  inParse(T[u].r);
}

void postParse(int u){
  if(u==NIL) return;
  postParse(T[u].l);
  postParse(T[u].r);
  printf(" %d",u);
}

int main(){
  int i,v,l,r,root;

  scanf("%d",&n);
  for(i=0;i<n;i++) T[i].p=NIL;

  for(i=0;i<n;i++){
    scanf("%d %d %d",&v,&l,&r);
    T[v].l=l;
    T[v].r=r;
    if(l!=NIL) T[l].p=v;
    if(r!=NIL) T[r].p=v;
  }

  for(i=0;i<n;i++) if(T[i].p==NIL) root=i;

  printf("Preorder\n");
  preParse(root);
  printf("\n");
  printf("Inorder\n");
  inParse(root);
  printf("\n");
  printf("Postorder\n");
  postParse(root);
  printf("\n");

  return 0;
}



Measured memory_bytes: 2148
import math

def distance(a, b):
    return math.sqrt((a[0] - b[0]) ** 2 + (a[1] - b[1]) ** 2)

def recursive(pos):
    if len(pos) == 1:
        return 0
    dist = 0
    for p in range(len(pos) - 1):
        dist += distance(pos[0], pos[p + 1])
    dist += recursive(pos[1:])
    return dist

N = int(input())
pos = []
for i in range(int(N)):
    p = input().split(" ")
    pos.append([int(p[0]), int(p[1])])

print(recursive(pos) * 2 / N)


Measured memory_bytes: 9160
#include<bits/stdc++.h>
long long int a[200001];
bool cmp(long long int a,long long int b)
{
	return a>b;
}
using namespace std;
int main()
{
	long long int n,k,c=0,i;
	scanf("%lld %lld",&n,&k);
	for(i=0;i<n;i++)
	{
		scanf("%d",&a[i]);
	}
	sort(a,a+n,cmp);
	for(i=0;i<k;i++)
	{
		a[i]=0;
	}
	for(i=0;i<n;i++)
	{
		c+=a[i];
	}
	printf("%lld",c);
}

Measured memory_bytes: 1920
S = input()
T = input()

ans = 'UNRESTORABLE'

for i in range(len(S)-len(T)+1): #
    flag = True
    for j in range(len(T)):
        if S[i+j] != T[j] and S[i+j] != '?':
            flag = False
            break
    if flag:
        ans = []
        for j in range(len(S)): ans.append(S[j])
        for j in range(len(T)): ans[i+j] = T[j]
        for j in range(len(S)):
            if ans[j] == '?': ans[j] = 'a'
            
for i in range(len(ans)):
    print(ans[i], end='')
print()


Measured memory_bytes: 3064
### subroutines

def doy(y, m, d)
  (y % 3 == 0) ?
    (m - 1) * 20 + d :
    (1...m).map{|m0| (m0 % 2 == 1) ? 20 : 19}.inject(0){|s, md| s + md} + d
end

def yd(y)
  (y % 3 == 0) ? 20 * 10 : (20 + 19) * 5
end

### main

n = gets.to_i

n.times do
  yi, mi, di = gets.split.map(&:to_i)
  #p [yi, mi, di]

  puts (yi...1000).map{|y0| yd(y0)}.inject(:+) - doy(yi, mi, di) + 1
end

Measured memory_bytes: 6316
#include <bits/stdc++.h>
#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 FORR(i, m, n) for(int i = m;i >= n;i--)
#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end());
#define llong long long
#define pb(a) push_back(a)
#define INF 999999999
using namespace std;
typedef pair<int, int> P;
typedef pair<llong, llong> LP;
typedef pair<int, P> PP;
typedef pair<llong, LP> LPP;

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

int main(){
	int t=17;
	int tmp;
	bool pos=true;
	REP(i, 3){
		cin >> tmp;
		if(tmp==5 || tmp==7) t-=tmp;
		else{
			pos=false;
			goto LAST;
		}
	}
	pos=(t==0);
LAST:
	if(pos) cout << "YES\n";
	else cout << "NO\n";

	return 0;
}


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

typedef long long ll;
typedef unsigned long long ull;
typedef unsigned int ui;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> pii;
typedef vector<pii> vpii;

// #define OJ
#define pb push_back
#define F first
#define S second

#define WLL(t) while(t--)
#define FOR(i,a,b) for(int i = a; i < b; i++)
#define STF(i, a, b) for(size_t i = a; i < b; i++)
#define RFOR(i, a, b) for(int i = a; i >= b; i--)
#define SRF(i, a, b) for(size_t i = a;i >= b;i--)

#define ALL(v) v.begin(),v.end()
#define PRECISION(x) cout<<fixed<<setprecision(x)
#define FASTIO ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define READ freopen("input.txt", "r", stdin)
#define WRITE freopen("output.txt", "w", stdout)
#define MOD 1000000007

#define TO(v, type) static_cast<type>(v)

int main()
{
#ifdef OJ
	READ;
	WRITE;
#endif

	FASTIO;
	string s;
	cin >> s;
	int mx = 0;
	int count{};
	STF(i, 0, 3) {
		if (s[i] == 'R') {
			count++;
		}
		else {
			count = 0;
		}
		mx = max(count, mx);
	}
	cout << mx << "\n";
	return 0;
}

Measured memory_bytes: 3636
#include<bits/stdc++.h>
using namespace std;
#define MOD 1000000000000000000

int main(){
  int n;
  cin >> n;
  vector<long long> a(n);
  long long ans = 1;
  for(int i = 0; i < n; i++){
    cin >> a[i];
    if(a[i] == 0){
      cout << 0 << endl;
      return 0;
    }
  }
  for(int i = 0; i < n; i++){
    if(ans > MOD / a[i]){
      cout << -1 << endl;
      return 0;
    }
    ans *= a[i];
  }
  cout << ans << endl;
}

Measured memory_bytes: 3980
while True:
    n,x=map(int,input().split())
    if n==0 and x==0 : break
    a=0
    for i in range(1,n+1):
        for j in range(1,n+1):
            if i<j:
                for k in range(1,n+1):
                    if j<k:
                        if k+j+i == x :
                            a+=1
    print(a)


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

const int N = 100005;

string s;
int n, sz;
int a[N];
int par[N];
int sum[N];

int find(int p) { return p == par[p] ? p : par[p] = find(par[p]); }
void join(int p, int q) {
	p = find(p); q = find(q);
	if (p == q) return;
	par[p] = q;
	sum[q] += sum[p]; sum[q] %= 26; sum[p] = 0;
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(0);
	cin >> s;
	sz = s.size();
	a[1] = s[0] - 'a';
	for (int i = 2; i <= sz; ++i) a[i] = s[i-1] - s[i-2];
	a[sz + 1] = 'a' - s[sz-1];
	++sz;

	for (int i = 1; i <= sz; ++i) a[i] = (a[i] + 26) % 26;
	for (int i = 1; i <= sz; ++i) par[i] = i, sum[i] = a[i];

	cin >> n;
	for (int i = 1; i <= n; ++i) {
		int l, r; cin >> l >> r; ++r;
		join(l, r);
	}

	for (int i = 1; i <= sz / 2; ++i) join(i, sz + 1 - i);

	for (int i = 1; i <= sz; ++i) if (i == find(i)) {
		if (sum[i] != 0) return cout << "NO\n", 0;
	}
	cout << "YES\n";
}

Measured memory_bytes: 1616
#include <bits/stdc++.h>
using namespace std;
int main(void){
    
    int N;cin>>N;
    long long x;cin>>x;
    vector<long long> A(N);
    for(long long i=0;i<N;i++){
        cin>>A[i];
    }
    sort(A.begin(),A.end());
    long long ans=0;
    for(long long i=0;i<N;i++){
        if(x>=A[i]){
            ans++;
            x-=A[i];
        }
        else{
            cout<<ans<<endl;
            return 0;
        }
    }
    if(x!=0){
        ans--;
    }
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 3588
#include <iostream>
using namespace std;
int N, K, a[100009];
int main() {
	cin.tie(0);
	ios_base::sync_with_stdio(false);
	cin >> N >> K; K--;
	long long sum = 0, opt = 1LL << 60, ca = 0, cb = 0;
	for (int i = 0; i < N; i++) {
		cin >> a[i];
		if (a[i] > 0) sum += a[i], ca += a[i];
		if (a[i] < 0) cb -= a[i];
		if (i >= K && opt > ca) opt = ca;
		if (i >= K && opt > cb) opt = cb;
		if (i >= K && a[i - K] > 0) ca -= a[i - K];
		if (i >= K && a[i - K] < 0) cb += a[i - K];
	}
	cout << sum - opt << "\n";
	return 0;
}

Measured memory_bytes: 640
#include <algorithm>
#include <bitset>
#include <climits>
#include <cmath>
#include <cstdio>
#include <functional>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<vector<ll>> vvl;
#define REP(var, a, b) for (int var = (a); var < (b); var++)
#define rep(var, n) for (int var = 0; var < (n); ++var)
#define ALL(c) (c).begin(), (c).end()
#define rALL(c) (c).rbegin(), (c).rend()
ll MOD = 1000000007;
const ll INF = 1LL << 50;

int main() {
  //
  ll n;
  cin >> n;
  vector<string> s(n);
  vvl dist(n, vl(n, INF));
  rep(i, n) dist[i][i] = 0;
  rep(i, n) {
    cin >> s[i];
    rep(j, n) {
      if (s[i][j] == '1') {
        dist[i][j] = 1;
      }
    }
  }
  if (n == 2) {
    cout << 2 << endl;
    return 0;
  }

  rep(k, n) {
    rep(i, n) {
      rep(j, n) { dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]); }
    }
  }
  ll maxdist = 0;
  rep(i, n) {
    map<ll, vl> mp;  // dist->vertices
    rep(j, n) {
      // cerr << dist[i][j] << " ";
      if (i != j) {
        mp[dist[i][j]].push_back(j);
      }
      maxdist = max(maxdist, dist[i][j]);
    }
    for (auto& m : mp) {
      vl vs = m.second;
      if (vs.size() == 1) continue;
      rep(ii, vs.size() - 1) {
        REP(jj, ii + 1, vs.size()) {
          if (dist[vs[ii]][vs[jj]] == 1) {
            // cerr << "!" << i << ":" << vs[ii] << "," << vs[jj] << endl;
            cout << -1 << endl;
            return 0;
          }
        }
      }
    }
    // cerr << endl;
  }
  cout << maxdist + 1 << endl;
  return 0;
}


Measured memory_bytes: 768
#include <iostream>
#include <map>
using namespace std;
#define int long long
 main() {
 int n;
  cin>>n;
  int a[n];
  map<int,int> freq;
  for(int i=0;i<n;i++)
  {
    cin>>a[i];
    freq[a[i]]++;
    
  }

  int answer=0;
  for(auto i=freq.begin();i!=freq.end();++i)
  {
    int count = i->second;
      answer+=(count*(count-1))/2;
  }
  for(int i=0;i<n;i++)
  {

      cout<<answer-freq[a[i]]+1<<endl;
  
  }
  
	return 0;
}


Measured memory_bytes: 11008
package main

import "fmt"

func normalize(s string) []int {
	ret := make([]int, len(s))
	m := make(map[rune]int)
	cnt := 1
	for i, r := range s {
		if m[r] == 0 {
			m[r] = cnt
			cnt++
		}
		ret[i] = m[r]
	}
	return ret
}

func equal(a, b []int) bool {
	if len(a) != len(b) {
		return false
	}
	for i := range a {
		if a[i] != b[i] {
			return false
		}
	}
	return true
}

func main() {
	var s, t string
	fmt.Scan(&s, &t)
	if equal(normalize(s), normalize(t)) {
		fmt.Println("Yes")
	} else {
		fmt.Println("No")
	}
}


Measured memory_bytes: 5376
#include <stdio.h>
#include <iostream> 
using namespace std;

int main(){
	int n = 0;
	int a[100] = { 0 };
	scanf("%d", &n);
	for (int i = 0; i < n; i++){
		scanf("%d", &a[i]);
	}
	for (int i = n - 1; i >= 0; i--){
		printf("%d", a[i]);
		if (i>0){
			putchar(' ');
		}
	}
	printf("\n");
	return 0;
}

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

#define mp make_pair
#define fst first
#define snd second
#define forn(i,n) for (int i = 0; i < int(n); i++)
#define forn1(i,n) for (int i = 1; i <= int(n); i++)
#define popcnt __builtin_popcount

using namespace std;

typedef unsigned int uint;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<ll,int> pli;
typedef pair<int,ll> pil;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;

template <typename T> T id(T b) {return b;};
template <class It> bool all(It f,It l){return std::all_of(f,l,id<bool>);}
template <class It> bool any(It f,It l){return std::any_of(f,l,id<bool>);}
template <typename T> void chmax(T &x, T y) {if (x < y) x = y;}
template <typename T> void chmin(T &x, T y) {if (x > y) x = y;}

ll n;
ll p[5];

int main()
{
#ifdef FASTIO
  ios_base::sync_with_stdio(false); cin.tie(nullptr);
#endif

  cin >> n;
  forn(i,5) cin >> p[i];

  ll m = *min_element(p,p+5);

  ll res = n/m;
  if(n % m != 0) res += 1;

  cout << res+4 << "\n";


  return 0;
}


Measured memory_bytes: 256
while True:
    H, W = input().split()
    if H == W == "0":
        break
    H = int(H)
    W = int(W)

    for i in range(H):
        if i % 2 == 0:
            for j in range(W):
                if j % 2 == 0:
                    print("#", end="")
                else:
                    print(".", end="")
        else:
            for j in range(W):
                if j % 2 == 0:
                    print(".", end="")
                else:
                    print("#", end="")
        print()
    print()


Measured memory_bytes: 7000
n = int(input())
s = input()
lm = [0] *(n+1)
rm = [0] *(n+1)

def check_l(x):
    if x=='W':
        r = 1
    else:
        r = 0
    return r
def check_r(x):
    if x=='E':
        r = 1
    else:
        r = 0
    return r
    
for i in range(1,n):
    lm[i+1] = lm[i] + check_l(s[i-1])
for i in range(n-1,0,-1):
    rm[i] = rm[i+1] + check_r(s[i])
ans = float('inf')
for i in range(1,n+1):
    ans = min(ans,lm[i]+rm[i])
print(ans)

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

using namespace std;
using ll = long long;

constexpr ll dx[] = {0, 1, 0, -1};
constexpr ll dy[] = {-1, 0, 1, 0};
constexpr char dc[] = {'D', 'R', 'U', 'L'};

vector<ll> ans;
map<pair<ll, ll>, bool> used;
void dfs(ll x, ll y, ll gx, ll gy) {
    if (x == gx && y == gy) {
        return;
    }
    used[make_pair(x, y)] = true;
    used[make_pair(gx, gy)] = false;
    vector<pair<double, pair<pair<ll, ll>, ll>>> pq;
    for (ll d = 0; d < 4; d++) {
        ll nx = x + dx[d];
        ll ny = y + dy[d];
        auto np = make_pair(nx, ny);
        if (!used[np]) {
            pq.emplace_back(make_pair(hypot(gy - ny, gx - nx), make_pair(np, d)));
        }
    }
    sort(pq.begin(), pq.end());
    if (!pq.empty()) {
        auto& p = pq.front().second;
        ans.emplace_back(p.second);
        dfs(p.first.first, p.first.second, gx, gy);
    }
}

int main() {
    ll sx, sy, tx, ty, x, y;
    cin >> sx >> sy >> tx >> ty;
    dfs(sx, sy, tx, ty);
    dfs(tx, ty, sx, sy);
    dfs(sx, sy, tx, ty);
    dfs(tx, ty, sx, sy);
    dfs(sx, sy, tx, ty);
    for (int i = 0; i < ans.size(); i++) {
        cout << dc[ans[i]];
    }
    cout << endl;
    return 0;
}

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

using namespace std;

int main(void) {
	string str;
	cin >> str;
	if (str.length() > 3 && str.substr(0,4) == "YAKI") {
		cout << "Yes" << endl;
	}
	else {
		cout << "No" << endl;
	}
	return 0;
}


Measured memory_bytes: 256
#include<stdio.h>
#include<math.h>
#define PI 3.1415926535897932
int main()
{
	double x,y,r,ang;
	int turn,i;

	while(1)
	{
		scanf("%d",&turn);
		if(turn==-1)break;
		
		ang=0;
		for(i=2;i<=turn;i++)
		{
			ang+=asin(sqrt(1/(double)i));
			if(ang>=PI*2){ang-=PI*2;}
		}
		r=sqrt(turn);
		x=r*cos(ang);
		y=r*sin(ang);
		printf("%lf\n%lf\n",x,y);
	}
	return 0;
}

Measured memory_bytes: 0
#include<stdio.h>
int main(void) {
	int i,a, b;
	int g = 0;
	scanf("%d%d", &a, &b);
	for (i = a; i <= b; i++) {
		if ((i % 10 == i / 10000) && ((i / 1000) % 10 == (i % 100) / 10))g++;
	}
	printf("%d", g);
	return 0;
}

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


int main(){
    vector<int> vct = { 0, 2, 0, 1, 0, 1,
                        0, 0, 1, 0, 1, 0};

    int x, y;
    cin >> x >> y;

    cout << (vct.at(x - 1) == vct.at(y - 1) ? "Yes" : "No") <<endl;
    return 0;
}


Measured memory_bytes: 256
//Sani buyuk Osman Pasa Plevneden cikmam diyor.
//FatihSultanMehmedHan
//Abdulhamid Han Elmuzaffer Daima
//Bismillahirrahmanirrahim

#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")

#include <bits/stdc++.h>

using namespace std;

typedef long long int lo;
typedef pair< int,int > PII;

#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define fio() ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define FOR for(int i=1;i<=n;i++)
#define mid (start+end)/2
#define ort (bas+son)/2

const lo MAX = -1000000000000000000; 
const lo MIN = 1000000000000000000; 
const lo inf = 1000000000; 
const lo KOK = 100000; 
const lo LOG = 30; 
const lo li = 100005; 
const lo mod = 1000000007; 

int n,m,cev,b,a[li],k;
string s;
vector<int> v;

int main(void){
	scanf("%d%d%d",&n,&m,&k);
	if(k>=n && k<=m){printf("Yes\n");return 0;}
	printf("No\n");
	return 0;
}


Measured memory_bytes: 256
function Main(input){
  var ones = parseInt(input.trim().slice(-1));
  var ans = '';
  var honArray = [2,4,5,7,9];
  var ponArray = [0,1,6,8];
  var bonArray = [3];
  if (honArray.indexOf(ones) !== -1){
    ans = 'hon';
  }else if (ponArray.indexOf(ones) !== -1){
    ans = 'pon';
  }else{
    ans = 'bon';
  }
  console.log(ans);
}
  


Main(require("fs").readFileSync("/dev/stdin", "utf8"));

Measured memory_bytes: 29484
#include<bits/stdc++.h>
using namespace std;
//define
#define int long long
#define rep(x,y) for(int i=x;i<y;i++)
#define REP(x,y) for(int j=x;j<y;j++)
#define all(x) x.begin(),x.end()
#define pb() push_back()
#define mod 100000007
#define elif else if
#define str string
//main
signed main(){
  int N,M,O,P,Q,count=0,count2=0,count3=0;
  double D=0;
  int c='A'-'a';
  //char C;
  str S,T;
  cin>>N>>M;
  int A[N];
  rep(0,N){
    cin>>A[i];
    if(A[i]>=M)count++;
  }
  cout<<count<<endl;
}


Measured memory_bytes: 1024
#include <stdio.h>
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <sstream>
using namespace std;

int main() {
	int a, b;
	cin >> a >> b;
	
	if (a > 8 | b > 8) {
		cout << ":(" << endl;
	}
	else {
		cout << "Yay!" << endl;
	}
}

Measured memory_bytes: 256
fn b() {
    input!{
        s: Chars,
        t: Chars,
    }

    let mut ans = std::usize::MAX;

    for i in 0..=(s.len() - t.len()) {
        let mut count = 0;
        for j in 0..t.len() {
            if s[i + j] != t[j] {
                count += 1;
            }
        }
        if ans > count {
            ans = count;
        }
    }
    println!("{}", ans);
}

use proconio::{input, marker::Chars};

fn main() {
    b();
}

Measured memory_bytes: 2180
#include <bits/stdc++.h>
using namespace std;
#define inf (1<<16)

int main(){
  int n;
  cin>>n;
  int a[12]={1,6,9,36,81,216,729,1296,6561,7776,46656,59049};
  vector<int> dp(n+1,inf);
  dp[0]=0;

  for(int i=0;i<=n;++i){
    for(int j=0;j<12;++j){
      if(i+a[j]<=n)dp[i+a[j]]=min(dp[i+a[j]],dp[i]+1);
    }
  }
  cout<<dp[n]<<endl;
}


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

int main() {
	int m, d;
	cin >> m >> d;

	int ans = 0;
	for (int i = 1; i <= m; i++) {
		for (int j = 22; j <= d; j++) {
			if (j / 10 < 2 || j % 10 < 2) {}
			else if ((j / 10) * (j % 10) == i) { ans++; }
		}
	}

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

Measured memory_bytes: 256
# 2020/05/01
# AtCoder Regular Contest 069 - C

# Input
n, m = map(int,input().split())

# c is c
if n >= 2 * m:
    ans = int(m / 2)
else:
    if n < m:
        ans = n + int(max(0, (m - n * 2)) / 4)
    else:
        ans = int(m / 2)

# Output
print(ans)


Measured memory_bytes: 2940
#include <bits/stdc++.h>
#define fi first
#define se second
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define drep(i,n) for(int i = (n)-1; i >= 0; --i)
#define srep(i,s,t) for (int i = s; i < t; ++i)
#define rng(a) a.begin(),a.end()
#define sz(x) (int)(x).size()
#define uni(x) x.erase(unique(rng(x)),x.end())
#define show(x) cout<<#x<<" = "<<x<<endl;
#define PQ(T) priority_queue<T,v(T),greater<T> >
#define newline puts("")
#define v(T) vector<T>
#define vv(T) v(v(T))
using namespace std;
typedef long long int ll;
typedef pair<int,int> P;
typedef set<int> S;
typedef queue<int> Q;
typedef queue<P> QP;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<P> vp;
const ll LINF = 1001002003004005006ll;
const int INF = 1001001001;
const int MOD = 1000000007;
  
int main() {
  int H,A;
  cin >> H >> A;
  cout << (H+A-1) / A << endl;
  return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <map>
#include <cmath>
#include <string>
#include <sstream>
#include <iomanip>
#include <complex>
using namespace std;

#define ll long long
#define vvi vector< vector<int> >
#define All(X) X.begin(),X.end()
#define FOR(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
#define REP(i,n) for(int i=0;i<(int)(n);i++)
#define pb push_back 
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
ll lcm(ll a,ll b){return a/gcd(a,b)*b;}

int main(){
	int n;
	int posx[200];
	int posy[200];
	while(cin >> n,n){
		posx[0] = 0;
		posy[0] = 0;
		FOR(i,1,n){
			int a,b;
			cin >> a >> b;
			if(b==0){
				posx[i] = posx[a]-1;
				posy[i] = posy[a];
 			}
 			if(b==1){
				posx[i] = posx[a];
				posy[i] = posy[a]-1;
 			}
 			if(b==2){
				posx[i] = posx[a]+1;
				posy[i] = posy[a];
 			}
 			if(b==3){
				posx[i] = posx[a];
				posy[i] = posy[a]+1;
 			}
		}
		sort(posx,posx+n);
		sort(posy,posy+n);
		cout << abs(posx[n-1]-posx[0])+1 <<" " << abs(posy[n-1]-posy[0])+1 << endl;
	}
}

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

int main() {
  int n;
  cin >> n;
  vector<int> a, b;
  rep(i, n) {
    int x, y;
    cin >> x >> y;
    a.push_back(x + y);
    b.push_back(x - y);
  }
  sort(a.begin(), a.end());
  sort(b.begin(), b.end());

  int ans = max(a.at(n - 1) - a.at(0), b.at(n - 1) - b.at(0));
  cout << ans << endl;
  return 0;
}

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

int main(){
  int H, W;
  cin >> H >> W;
  vector<string> S(H);
  for (int i=0; i<H; i++){
    cin >> S[i];
  }
  vector<vector<vector<int>>> hoge(H, vector<vector<int>>(W, vector<int>(2,0)));
  for (int i=0; i<H; i++){
    int tmpcnt = 0;
    for (int j=0; j<W; j++){
      if (S[i][j]=='.') tmpcnt++;
      else tmpcnt = 0;
      hoge[i][j][0] = tmpcnt;
    }
    for (int j=W-2; j>-1; j--){
      if (S[i][j]=='#') continue;
      if (hoge[i][j+1][0]>hoge[i][j][0]){
        hoge[i][j][0] = hoge[i][j+1][0];
      }
    }
  }
  for (int j=0; j<W; j++){
    int tmpcnt = 0;
    for (int i=0; i<H; i++){
      if (S[i][j]=='.') tmpcnt++;
      else tmpcnt = 0;
      hoge[i][j][1] = tmpcnt;
    }
    for (int i=H-2; i>-1; i--){
      if (S[i][j]=='#') continue;
      if (hoge[i+1][j][1]>hoge[i][j][1]){
        hoge[i][j][1] = hoge[i+1][j][1];
      }
    }
  }
  int ans = 0;
  for (int i=0; i<H; i++){
    for (int j=0; j<W; j++){
      ans = max(ans, hoge[i][j][0]+hoge[i][j][1]-1);
    }
  }
  cout << ans << endl;
}


Measured memory_bytes: 225280
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxx = 2e5 + 7;
const int Inf = 1 << 30;
const ll INF = 1ll << 60;
int n, ans;
int a[maxx];

int main() {
	scanf("%d", &n);
	for(int i = 1; i <= n; i++) scanf("%d", &a[i]);
	int pre = 1;
	for(int i = 1; i <= n; i++) {
		if(a[i] == pre) {
			pre++;
			continue;
		}
		ans++;
	}
	if(ans > n - 1) puts("-1");
	else printf("%d\n", ans);
	return 0;
}

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

using namespace std;

using ll = long long;

const long long MOD = 1e9+7;

#define ALL(A) A.begin(),A.end()

void ALLIN1_NUMBER(vector<ll>& V)
{
    for(auto& x : V)
    {
        cin >> x;
    }
}

void ALLOUT_NUMBER(vector<ll> V)
{
    ll N = V.size();
    for(ll i=0;i<N;i++)
    {
        cout << V[i];
        if(i<N-1) cout << ' ';
    }
    cout << endl;
}

class Mll
{
    public:
    ll x;

    Mll() : x(0){}
    Mll(ll x=0) : x((x%MOD+MOD)%MOD){}

    Mll operator-() const
    {
        return Mll(-x);
    }

    Mll& operator+=(const Mll& A)
    {
        if((x += A.x) >= MOD) x -= MOD;
        return *this;
    }
    Mll& operator-=(const Mll& A)
    {
        if((x += MOD - A.x) >= MOD) x -= MOD;
        return *this;
    }
    Mll& operator*=(const Mll& A)
    {
        (x *= A.x) %= MOD;
        return *this;
    }
    
    Mll operator+(const Mll& A)
    {
        Mll res(*this);
        return res+=A;
    }
    Mll operator-(const Mll& A)
    {
        Mll res(*this);
        return res-=A;
    }
    Mll operator*(const Mll& A)
    {
        Mll res(*this);
        return res*=A;
    }
    
    Mll pow(ll t) const // t乗
    {
        if(t==0) return 1;
        Mll A = pow(t>>1);
        A *= A;
        if(t&1) A *= *this;
        return A;
    }

    // for prime mod
    Mll inv() const
    {
        return pow(MOD-2);
    }
    Mll& operator/=(const Mll& A)
    {
        return (*this) *= A.inv();
    }
    Mll operator/(const Mll& A) const
    {
        Mll res(*this);
        return res/=A;
    }

    friend ostream& operator<<(ostream& os, const Mll& M)
    {
        os << M.x;
        return os;
    }
};

vector<Mll> ALLIN_MLL(ll N)
{
    vector<ll> numbers_ll(N);
    ALLIN1_NUMBER(numbers_ll);

    vector<Mll> numbers_Mll;
    for(ll i=0;i<N;i++)
    {
        Mll add(numbers_ll[i]);
        numbers_Mll.push_back(add);
    }

    return numbers_Mll;
}

template<class T>
void OUT0(T N)
{
    cout << N << endl;
}

static const double pi = acos(-1.0);

double Cos(double D)
{
    return cos(pi/180 * D);
}

class Point
{
    public:
    ll x,y;
};

int main()
{
    ll N,D;
    cin >> N >> D;

    vector<Point> P(N);
    for(auto& X : P)
    {
        cin >> X.x >> X.y;
    }

    ll counter = 0;

    for(ll i=0;i<N;i++)
    {
        if(D*D>=P[i].x*P[i].x+P[i].y*P[i].y) counter++;
    }

    cout << counter << endl;

    return 0;
}

Measured memory_bytes: 6488
# coding: utf-8
DATA = """
5
1 1 2 2
""".split("\n")

def get_debug_line():
	for i in DATA:
		yield i

if 1:
	get_line = input
else:
	get_line = get_debug_line().__next__
	get_line()

N = int(get_line().strip())

Memo = [0] * (N+1)
for i in get_line().strip().split(" "):
    i = int(i)
    Memo[i] += 1    

for i in range(1, N+1):
    print (Memo[i])








Measured memory_bytes: 25856
import java.util.*;

public class Main {

	public static void main(String[] args) {
		// TODO Auto-generated method stub

		Scanner sc = new Scanner(System.in);
		double best,bestc,sumc,sump;
		int on = sc.nextInt();
		int onc[] = new int[on];
		int basep = sc.nextInt();
		int onp = sc.nextInt();
		int basec = sc.nextInt();
		for(int i=0;i<on;i++){
			onc[i]=sc.nextInt();
		}
		Arrays.sort(onc);
		sumc=basec;//カロリーの合計
		sump=basep;//金額の合計
		best=basec/basep;//生地の1ドル当たりのカロリー
		for(int i=on-1;i>=0;i--){
			sumc+=onc[i];
			sump+=onp;
			bestc=sumc/sump;
			if(best<bestc){
				best=bestc;
			}
			//System.out.println(sumc+""+sump+""+best);
		}
		System.out.println((int)best);
	}

}

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

string kaga(string s,int num){
	string san;
	for(int i=0;i<num;i++)san+=s;
	return san;
}

void check(string s){
	for(int i=1;i<99;i++){
		string a,b;
		a=">'"+kaga("=",i)+'#'+kaga("=",i)+'~';
		b=">^"+kaga("Q=",i)+"~~";
		if(a==s){
			cout<<"A"<<endl;
			goto end;
		}
		if(b==s){
			cout<<"B"<<endl;
			goto end;
		}
	}
	cout<<"NA"<<endl;
	end:;
}

int main(){
	int n;
	string s;
	for(cin>>n;n>0;n--){
		cin>>s;
		check(s);
	}
	return 0;
}


Measured memory_bytes: 1216
#include<stdio.h>
#include<math.h>

int main(void)
{
	int n;   //学生数
	int i;    //くり返し用
	double s[1000];   //それぞれの得点
	double aa;   //分散
	double m;   //得点の平均値
	double a;   //標準偏差

	while (1)
	{
		m = 0;
		aa = 0;
		scanf("%d", &n);
		if (n == 0)
		{
			break;
		}

		/*得点の平均値*/
		for (i = 0; i < n; i++)
		{
			scanf("%lf", &s[i]);
			m = m + s[i];
		}
		m = m / n;

		/*分散*/
		for (i = 0; i < n; i++)
		{
			aa = aa + (s[i] - m)*(s[i] - m);
		}
		aa = aa / n;

		/*標準偏差*/
		printf("%f\n", sqrt(aa));
	}
	return 0;
}


Measured memory_bytes: 2044
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ll long long
#define P pair<int,int>
#define fi first
#define se second
#define rep(i,n) for(int i=0;i<n;i++)
#define INF 1000000000
#define MOD 1000000007
#define all(v) v.begin(),v.end()
#define pb push_back
int dx[]={0,1,0,-1},dy[]={1,0,-1,0};
int kaijo[200010];
struct edge{int to,cost;};
int gcd(int a,int b){
	if(b==0)return a;
	return gcd(b,a%b);
}
int lcm(int a,int b){
	return a/gcd(a,b)*b;
}
bool prime(int a){
	if(a==1)return false;
	for(int i=2;i*i<=a;i++){
		if(a%i==0)return false;
	}
	return true;
}
bool kosa(double ax,double ay,double bx,double by,double cx,double cy,double dx,double dy){//線分の交差判定
	double ta=(cx-dx)*(ay-cy)+(cy-dy)*(cx-ax);
	double tb=(cx-dx)*(by-cy)+(cy-dy)*(cx-bx);
	double tc=(ax-bx)*(cy-ay)+(ay-by)*(ax-cx);
	double td=(ax-bx)*(dy-ay)+(ay-by)*(ax-dx);
	return tc*td<0&&ta*tb<0;
}
void init_fact(int n){
	kaijo[0]=1;
	for(int i=1;i<=n;i++){
		kaijo[i]=kaijo[i-1]*i;
		kaijo[i]%=MOD;
	}
}
int modpow(int a,int b){
	if(b==0)return 1;
	if(b%2)return modpow(a,b-1)*a%MOD;
	int memo=modpow(a,b/2);
	return memo*memo%MOD;
}
int comb(int a,int b){
	if(b>a)return 0;
	if(a==b)return 1;
	return kaijo[a]*modpow(kaijo[a-b],MOD-2)%MOD*modpow(kaijo[b],MOD-2)%MOD;
}
int g(int x){
	x=modpow(x,MOD-2);
	return x;
}
bool b[333];
int n,m,a[333][333],ans=INF;
signed main(){
	cin>>n>>m;
	rep(i,n){
		rep(j,m){
			cin>>a[i][j];
			a[i][j]--;
		}
	}
	rep(_,m){
		int cnt[333];
		fill(cnt,cnt+m,0);
		rep(i,n){
			rep(j,m){
				if(b[a[i][j]]==false){
					cnt[a[i][j]]++;
					break;
				}
			}
		}
		int ma=0,Ma=0;
		rep(i,m){
			if(ma<cnt[i]){
				ma=cnt[i];
				Ma=i;
			}
		}
		ans=min(ans,ma);
		b[Ma]=true;
	}
	cout<<ans<<endl;
	return 0;
}


Measured memory_bytes: 1024
import heapq
from collections import defaultdict
N = int(input())
A = list(map(int,input().split()))
B = list(map(int,input().split()))

d = defaultdict(list)
for i in range(N):
    a = A[i]
    b = B[i]
    if a==b:
        d[a].append(i)

h = []
for a in d:
    heapq.heappush(h,(-len(d[a]),a))

while len(h)>=2:
    x,a = heapq.heappop(h)
    y,b = heapq.heappop(h)
    i = d[a].pop()
    j = d[b].pop()
    B[i],B[j] = B[j],B[i]
    x += 1
    y += 1
    if x<0:
        heapq.heappush(h,(x,a))
    if y<0:
        heapq.heappush(h,(y,b))

if h:
    x,a = heapq.heappop(h)
    d[a] = d[a][::-1]
    for i in range(N):
        if len(d[a])==0:
            break
        if A[i] != a and B[i] != a:
            j = d[a].pop()
            B[i],B[j] = B[j],B[i]

ans = "Yes"
for i in range(N):
    if A[i]==B[i]:
        ans = "No"

print(ans)
if ans=="Yes":
    print(*B)


Measured memory_bytes: 143384
import java.util.Scanner;

public class Main{


	public static void BubbleSort(int[] array){
		int len=array.length;
		int cnt=0;
		int swap;
		for(int i=0;i<len-1;i++){
			for(int j=len-1;i<j;j--){
				if(array[j]<array[j-1]){
					cnt++;
					swap=array[j];array[j]=array[j-1];array[j-1]=swap;
				}
			}
		}
		for(int i=0;i<len;i++){
		System.out.print(array[i]);
		if(i!=len-1)System.out.print(" ");}

		System.out.println();
		System.out.println(cnt);
	}

	public static void main(String[] args){

		int n;

		Scanner scan=new Scanner(System.in);
		n=scan.nextInt();
		int[] box=new int[n];

		for(int i=0;i<n;i++){
		box[i]=scan.nextInt();
		}

		BubbleSort(box);

		scan.close();

	}

}

Measured memory_bytes: 26104
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string>
#include <stack>
#include <queue>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <cmath>

using namespace std;
#define PI 3.1415926535897932384626433832795
#define MOD (1000000007)
#define EPS (1e-15)
#define rep(i, n) for (int i = 0; i < (n); i++)
#define repc(i, s, n) for (int i = (s); i <= (n); i++)
#define rrep(i, n) for (int i = (n) - 1; i >= 0; i--)
#define rrepc(i, s, n) for (int i = (s); i >= (n); i--)
#define bet(x, a, b) (a) <= (x) && (x) < (b)
typedef long long ll;
typedef unsigned long long ull;

int main()
{
	int S, W;

	cin >> S >> W;

	cout << (S <= W ? "unsafe" : "safe") << endl;

	return 0;
}


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

const long long mod=998244353;
long long n, m, k, ans=0, facto[200003];

long long modpow(long long x, long long y){
	long long ret=1;
	while(y>0){
		if (y&1){
			ret*=x;
			ret%=mod;
		}
		x*=x;
		x%=mod;
		y>>=1;
	}
	return ret;
}

long long modinv(long long x){
	return modpow(x,mod-2);
}

long long comb(long long x, long long y){
	if (y==0) return 1;
	long long ret=facto[x];
	ret*=modinv(facto[x-y]);
	ret%=mod;
	ret*=modinv(facto[y]);
	ret%=mod;
	return ret;
}

void init(){
	facto[0]=1;
	for (int i=1;i<200003;i++){
		facto[i]=facto[i-1]*i;
		facto[i]%=mod;
	}
}

int main(){
//	cout << comb(7,0) << "\n";
	init();
	cin >> n >> m >> k;
	for (int i=0;i<=k;i++){
		long long tmp=m;
		tmp*=modpow(m-1,n-i-1);
		tmp%=mod;
//		cout << tmp << "\n";
		tmp*=comb(n-1,i);
		tmp%=mod;
		ans+=tmp;
		ans%=mod;
//		cout << i << " " << ans << "\n";
	}
	cout << ans << "\n";
}

Measured memory_bytes: 5200
#include <bits/stdc++.h>
const long long INF = LLONG_MAX/2;
#define FOR(i, r, n) for(int i=(r); i<(n); i++) 
#define REP(i, n) FOR(i, (0), n)
#define ll long long int
template<typename T>
void remove(std::vector<T>& vector, unsigned int index)
{
	vector.erase(vector.begin() + index);
}

using namespace std;
ll ans=0, sum = 0, n, k, t;
string s;

map<ll,ll> m;

int check(int num)
{
	while (num>0)
	{
		if (m.count(num % 10)) return 0;
		num /= 10;
	}
	return 1;
}

int main()
{
	cin >> n >> k;
	REP(i, k)
	{
		cin >> t;
		m[t]++;
	}
	while (true)
	{
		if (check(n)) break;
		else n++;
	}
	cout << n << endl;
}

Measured memory_bytes: 256
import java.util.*;
import java.awt.geom.*;
import java.awt.geom.Line2D.Double;

public class Main {
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		while(true){
			int n = sc.nextInt();
			int m = sc.nextInt();
			int l = sc.nextInt();
			if(n==0 && m==0 && l==0) break;
			
			Line2D.Double[] z = new Line2D.Double[5*n];
			double[] x = new double[5*n];
			double[] y = new double[5*n];
			double[][] cost = new double[n][n];
			for(int i=0;i<n;i++){
				Arrays.fill(cost[i], Integer.MAX_VALUE);
				cost[i][i] = 0;
			}	
			
			for(int i=0;i<n;i++){
				int p = sc.nextInt();
				int q = sc.nextInt();
				double a = sc.nextDouble();
				int r = sc.nextInt();
				for(int j=0;j<5;j++){
					x[5*i+j] = p - Math.sin((a+72*j)*Math.PI/180)*r;
					y[5*i+j] = q + Math.cos((a+72*j)*Math.PI/180)*r;
				}
				z[5*i] = new Line2D.Double(x[5*i], y[5*i], x[5*i+2], y[5*i+2]);
				z[5*i+1] = new Line2D.Double(x[5*i+2], y[5*i+2], x[5*i+4], y[5*i+4]);
				z[5*i+2] = new Line2D.Double(x[5*i+4], y[5*i+4], x[5*i+1], y[5*i+1]);
				z[5*i+3] = new Line2D.Double(x[5*i+1], y[5*i+1], x[5*i+3], y[5*i+3]);
				z[5*i+4] = new Line2D.Double(x[5*i+3], y[5*i+3], x[5*i], y[5*i]);
				
				for(int j=i-1;j>=0;j--){
					double min = Integer.MAX_VALUE;
					for(int c=0;c<5;c++){
						for(int d=0;d<5;d++){
							min = Math.min(min, z[5*j+d].ptSegDist(x[5*i+c], y[5*i+c]));
							min = Math.min(min, z[5*i+c].ptSegDist(x[5*j+d], y[5*j+d]));
							if(z[5*j+d].intersectsLine(z[5*i+c])==true){
								min = 0;
								c = 5;
								d = 5;
							}
						}
					}
					
					cost[i][j] = min;
					cost[j][i] = min;
				}
			}
			
			for(int i=0;i<n;i++){
				for(int j=0;j<n;j++){
					for(int k=0;k<n;k++){
						if(cost[j][i]!=Integer.MAX_VALUE && cost[i][k]!=Integer.MAX_VALUE){
							cost[j][k] = Math.min(cost[j][k], cost[j][i]+cost[i][k]);
						}
					}
				}
			}
			
			System.out.println(cost[m-1][l-1]);	
		}	
	}	
}

Measured memory_bytes: 44364
#include <algorithm>
#include <cmath>
#include <climits>
#include <functional>
#include <iostream>
#include <queue>
#include <string>
#include <vector>

using namespace std;
using ll = long long;

bool isEqual(const vector<int>& v1, const vector<int>& v2) {
	for (size_t i = 0; i < v1.size(); i++) {
		if (v1[i] != v2[i]) return false;
	}
	return true;
}

int main() {
	int N, a=-1, b=-1;
	cin >> N;
	vector<int> P(N), Q(N), X(N);
	for (int i = 0; i < N; i++) cin >> P[i];
	for (int i = 0; i < N; i++) cin >> Q[i];
	for (int i = 0; i < N; i++) X[i] = i+1;

	ll index = 0;
	do {
		if (a==-1 && isEqual(P, X)) a = index;
		if (b==-1 && isEqual(Q, X)) b = index;
	
		if (a != -1 && b != -1)break;
		index++;
	} while (next_permutation(X.begin(), X.end()));
	cout << abs(a - b) << endl;
}

Measured memory_bytes: 3620
#include<iostream>
#include<string>
#include<algorithm>
#include <stdio.h>
#include<iostream>
#include<iomanip>
#include<cmath>
#include<array>
#include<vector>
#include<set>
#include <utility>
#include <map>
using namespace std;



int main(){
  string s,t; cin>>s>>t;
  int cnt=0;
  for(int i=0;i<3;i++)
  if(s[i]==t[i]) cnt++;

  cout<<cnt<<endl;
}


Measured memory_bytes: 256
#設定
import sys
input = sys.stdin.buffer.readline

#ライブラリインポート
from collections import defaultdict
import queue

#入力受け取り
def getlist():
	return list(map(int, input().split()))

INF = float("inf")

class Graph(object):
    def __init__(self):
        self.graph = defaultdict(list)

    def __len__(self):
        return len(self.graph)

    def add_edge(self, a, b):
        self.graph[a].append(b)

    def get_nodes(self):
        return self.graph.keys()

class BFS(object):
	def __init__(self, graph, S, N):
		self.g = graph.graph
		self.Q = queue.Queue()
		self.dist = [INF] * N
		self.visit = ["No"] * N
		self.Q.put(S)
		self.dist[S] = 0
		self.visit[S] = "Yes"
		while not self.Q.empty():
			v = self.Q.get()
			for i in self.g[v]:
				if self.visit[i] == "No":
					self.dist[i] = self.dist[v] + 1
					self.Q.put(i)
					self.visit[i] = "Yes"

#処理内容
def main():
	#入力処理
	N, M = getlist()
	G = Graph()
	for i in range(M):
		u, v = getlist()
		G.add_edge(u - 1, v - 1 + N)
		G.add_edge(u - 1 + N, v - 1 + 2 * N)
		G.add_edge(u - 1 + 2 * N, v - 1)

	S, T = getlist()
	S -= 1
	T -= 1
	#BFS
	BF = BFS(G, S, 3 * N)
	D = BF.dist
	if D[T] == INF:
		print(-1)
	else:
		print(D[T] // 3)

if __name__ == '__main__':
	main()

Measured memory_bytes: 115356
#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimization_level 3
using ll = long long;
constexpr ll INF = 1'010'000'000'000'000'017LL;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define all(v) v.begin(), v.end()

int main(){
	ll n,y;
	cin>>n>>y;

	ll a,b,c;
	a=-1;
	b=-1;
	c=-1;

	for (size_t i = 0; i <= n; i++)
	{
		for (size_t j = i; j <= n; j++)
		{
			// if (n-(j-i)-i<0)
			// {
			// 	continue;
			// }
			
			if (10000*i+5000*(j-i)+1000*(n-(j-i)-i)==y)
			{
				a=i;
				b=j-i;
				c=n-i-(j-i);
			}
			
		}
		
	}
	
	cout<<a<<" "<<b<<" "<<c;
}


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

int main() {
	string str;
	cin >> str;
	int ans = 10000;
	for(int i=0; i<str.size()-2; i++){
		string tmp = "";
        for(int j=0; j<3; j++){
			tmp += str.at(i+j);
        }
		int num = stoi(tmp);
		ans = min(ans, abs(num-753));
	}
	cout << ans << endl;
}


Measured memory_bytes: 256
module IntMap = Map.Make (struct
  type t = int
  let compare = compare
end)


let () = Scanf.scanf "%d" @@ fun n ->
  let rec pow5s acc i =
    if n < i * i * i * i
    then acc
    else pow5s (IntMap.add (i * i * i * i * i) i acc) (i + 1) in
  let pow5s = pow5s IntMap.empty 0 in
  let Some (a, b) =
    IntMap.fold (fun pow5a a ans ->
      match IntMap.find_opt (abs (pow5a - n)) pow5s with
      | None -> ans
      | Some b -> Some (a, if pow5a - n <= 0 then ~- b else b)) pow5s None in
  Printf.printf "%d %d\n" a b




Measured memory_bytes: 3848
N, A, B = map(int, input().split())
s = input()
t = 0
b = 0
for i in range(N):
    if s[i] == "a":
        if t < A + B:
            print("Yes")
        else:
            print("No")
        t += 1
        
    elif s[i] == "b":
        if t < A + B and b < B:
            print("Yes")
            t += 1
            b += 1
        else:
            print("No")
    else:
        print("No")


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

#define f(i, a, b, c) for(int i = a ; i < b ; i += c)
#define fr(i, a, b, c) for(int i = a ; i >= b ; i -= c)
#define fit(it, v) for(auto it = v.begin() ; it != v.end() ; ++it)
#define frit(it, v) for(auto it = v.rbegin() ; it != v.rend() ; ++it)
#define all(v) v.begin(), v.end()
#define allr(v) v.rbegin(), v.rend()
#define eb emplace_back
#define pb push_back
#define lli long long int
#define modn 998244353
#define NL '\n'

using namespace std;

typedef vector< int > vi;
typedef vector< char > vc;
typedef vector< bool > vb;
typedef vector< lli > vli;
typedef vector< vector< char > > vvc;
typedef vector< vector< int > > vvi;
typedef pair< int, int > ii;
typedef vector< ii > vii;
typedef pair< lli, int> pli;
typedef pair< lli, lli> pll;
typedef set< int > si;
typedef set< ii > sii;

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	
	#ifdef LOCAL_TEST
		clock_t z = clock();
    	ifstream h("in");
	    ofstream g("out");
	#else
	    #define h cin
	    #define g cout
	#endif // LOCAL_TEST
	
	int n, m;
	h >> n >> m;
	g << (n == m ? "Yes" : "No");
	
	#ifdef LOCAL_TEST
		cerr << "Time taken is: " << double(clock() - z) / CLOCKS_PER_SEC << NL;
		h.close();
		g.close();
	#endif // LOCAL_TEST
}



Measured memory_bytes: 256