akhauriyash/Code-Regression huggingface dataset:
#include<cstdio>
#include<cmath>

int main(){
    
    double x1;
    double x2;
    double y1;
    double y2;
    double r;
    
    scanf("%lf %lf %lf %lf", &x1, &y1, &x2, &y2);
    
    r = sqrt(pow(x2-x1, 2) + pow(y2-y1, 2));
    
    
    printf("%f\n",r);
    
    return 0;
    
}


Measured memory_bytes: 2700
#include<iostream>
#include<string.h>
#include<string>
#include<stdio.h>
#include<algorithm>
#include<vector>
#include<bitset>
#include<math.h>
#include<stack>
#include<queue>
#include<set>
#include<map>
using namespace std;
typedef long long ll;
typedef long double db;
typedef vector<int> vi;
typedef pair<int,int> pii;
const int N=100000+100;
const db pi=acos(-1.0);
#define lowbit(x) ((x)&(-x))
#define sqr(x) (x)*(x)
#define rep(i,a,b) for (register int i=a;i<=b;i++)
#define per(i,a,b) for (register int i=a;i>=b;i--)
#define go(u,i) for (register int i=head[u],v=sq[i].to;i;i=sq[i].nxt,v=sq[i].to)
#define fir first
#define sec second
#define mkp make_pair
#define pb push_back
#define maxd 998244353
#define eps 1e-8
inline int read()
{
    int x=0,f=1;char ch=getchar();
    while ((ch<'0') || (ch>'9')) {if (ch=='-') f=-1;ch=getchar();}
    while ((ch>='0') && (ch<='9')) {x=x*10+(ch-'0');ch=getchar();}
    return x*f;
}

inline ll readll()
{
    ll x=0;int f=1;char ch=getchar();
    while ((ch<'0') || (ch>'9')) {if (ch=='-') f=-1;ch=getchar();}
    while ((ch>='0') && (ch<='9')) {x=x*10+(ch-'0');ch=getchar();}
    return x*f;
}

int n,a[100100];

int main()
{
    n=read();
    rep(i,1,n) a[i]=read();
    if (a[n]!=2) {puts("-1");return 0;}
    ll L,R;L=R=2;
    per(i,n,1)
    {
        L=(L-1)/a[i]+1;R=R/a[i];
        if (L>R) {puts("-1");return 0;}
        L*=a[i];R=(R+1)*a[i]-1;
        if (L>R) {puts("-1");return 0;}
    }
    printf("%lld %lld\n",L,R);
    return 0;
}
        

Measured memory_bytes: 640
from collections import deque
S=input()
st="X"
Q=int(input())
q=[]
for _ in range(Q):
  q.append(input())#qは文字列のリストだよ
t=0#totalひっくり返し
for i in range(Q):
  if q[i]=="1":
    t+=1
  else:
    T,F,C=q[i].split()
    if F=="1" and t%2==0:
      st=C+st
    elif F=="2" and t%2==0:
      st=st+C
    elif F=="1" and t%2==1:
      st=st+C
    else:
      st=C+st
if t%2==0:
  print(st.replace("X",S))
else:
  print(st.replace("X",S)[::-1])

Measured memory_bytes: 17428
#!/usr/bin/env python3

S = list(input())
T = list(input())

def srch(num,li):
    if len(li)==0:
        return -10

    fst = 0
    lst = len(li)-1
    while(lst>fst):
        mid = (fst+lst)//2
        if li[mid] <= num:
            fst = mid+1
        else:
            lst = mid
    return li[fst]

def main():
    N = len(S)
    li = [[] for _ in range(26)]
    for i in range(N):
        mm = ord(S[i])-97
        li[mm].append(i)
    for i in range(26):
        if len(li[i])>0:
            li[i].append(li[i][0]+N)
    
    cnt1 = 0
    cnt2 = -1
    for i in range(len(T)):
        mm = ord(T[i])-97
        cnt2 = srch(cnt2,li[mm])
        if cnt2 == -10:
            print(-1)
            return

        if cnt2>=N:
            cnt2 %= N
            cnt1 += 1
    print(cnt1*N+cnt2+1)


    

    
        

if __name__ == '__main__':
    main()





Measured memory_bytes: 9052
N = int(input())
a = N // 100
b = N % 100
ans = 'NA'
x = 1 <= a <= 12
y = 1 <= b <= 12
if x and y:
    ans = 'AMBIGUOUS'
elif x and not y:
    ans = 'MMYY'
elif not x and y:
    ans = 'YYMM'

print(ans)



Measured memory_bytes: 38256
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
ll dp[100003];int n,k;int a[100003];
ll solve(int idx)
{
  if(idx>=n)
    return 1e9+7;
  if(idx==n-1)
    return 0;
  if(dp[idx]!=-1)
    return dp[idx];
  ll res=1e9+7;
  for(int i=1;i<=k;i++)
  {
    if(idx+i<n)
      res=min(res,abs(a[idx]-a[idx+i])+solve(idx+i));
              else
              break;
              }
              if(res>1e9)
              res=0;
  return dp[idx]=res;
}
int main()
{
  
  cin>>n>>k;
  
  for(int i=0;i<n;i++)
    cin>>a[i];
  memset(dp,-1,sizeof(dp));
  ll ans=solve(0);
  cout<<ans<<"\n";
  return 0;
}

Measured memory_bytes: 6144
#include <bits/stdc++.h>
#define ll long long
#define ulli unsigned long long int
#define ld long double  
#define endl "\n"
using namespace std; 

void solve() {
    string s;
    cin >> s;

    vector<char> c {'A', 'C', 'G', 'T'};

    int ans = 0;
    for (int i = 0; i < (int)s.size(); i++) {
        if (find(c.begin(), c.end(), s[i]) != c.end()) {
            int len = 1;
            for (int j = i + 1; j < (int)s.size(); j++) {
                if (find(c.begin(), c.end(), s[j]) != c.end()) {
                    len++;
                } else {
                    break;
                }
            }
            ans = max(ans, len);
        }
    }

    cout << ans << endl;
}

int main() 
{ 
    ios_base::sync_with_stdio(false); 
    cin.tie(NULL); 
  
    int t = 1; 
    //cin >> t; 
    while (t--) { 
        solve(); 
    } 
  
    cerr << "time taken : " << (float)clock() / CLOCKS_PER_SEC << " secs" << endl; 
    return 0; 
} 


Measured memory_bytes: 256
#include <iostream>
using namespace std;
int moid(int a)
{
	int sumv=0;
	while (a!=0)
	{
		sumv+=a%10;
		a=a/10;
	}
	return sumv;
}
int main() 
{
	int N;
	cin>>N;
	if (N%moid(N)==0)  cout<<"Yes";
	else cout<<"No";
	return 0;
}

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

int in()
{
    int a;
    scanf("%d", &a);
    return a;
}

int check[200000 + 5];

int main()
{
    int n = in(), k = in();
    for(int i = 0; i < n; i++)
        check[in()]++;
    sort(check, check + 200000);
    reverse(check, check + 200000);
    int ans = 0;
    for(int i = 0; i < k; i++)
        ans += check[i];
    ans = n - ans;
    printf("%d\n", ans);
    return 0;
}


Measured memory_bytes: 1024
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(ll i=0;i<n;i++)
#define repl(i,l,r) for(ll i=(l);i<(r);i++)
#define per(i,n) for(ll i=n-1;i>=0;i--)
#define perl(i,r,l) for(ll i=r-1;i>=l;i--)
#define fi first
#define se second
#define pb push_back
#define ins insert
#define pqueue(x) priority_queue<x,vector<x>,greater<x>>
#define all(x) (x).begin(),(x).end()
#define CST(x) cout<<fixed<<setprecision(x)
#define vtpl(x,y,z) vector<tuple<x,y,z>>
#define rev(x) reverse(x);
using ll=long long;
using vl=vector<ll>;
using vvl=vector<vector<ll>>;
using pl=pair<ll,ll>;
using vpl=vector<pl>;
using vvpl=vector<vpl>;
const ll MOD=1000000007;
const ll MOD9=998244353;
const int inf=1e9+10;
const ll INF=4e18;
const ll dy[9]={1,0,-1,0,1,1,-1,-1,0};
const ll dx[9]={0,-1,0,1,1,-1,1,-1,0};
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(){
    ll n,k;cin >> n >> k;
    vl v(n);rep(i,n)cin >> v[i];
    sort(all(v));
    ll sum=0;
    rep(i,k)sum+=v[i];
    cout << sum <<endl;
}   

Measured memory_bytes: 3632
#include <cstdio>
#include <vector>
using namespace std;

typedef struct Node {
	int v;
	Node *l, *r;
	Node *p;
	Node() {
		this->v = 0;
		this->l = NULL;
		this->r = NULL;
		this->p = NULL;
	}
} Node, *pNode;

pNode root;

void InsertNode(const int& v);
pNode FindNode(pNode root, const int&v);

void PreOrder(pNode root);
void InOrder(pNode root);

int main()
{
	root = NULL;
	int T; scanf("%d",&T);
	while(T--) {
		char s[7]; scanf("%s",s);
		if(s[0] == 'p') {
			InOrder(root);
			putchar('\n');
			PreOrder(root);
			putchar('\n');
			continue;
		}
		int v; scanf("%d",&v);
		if(s[0] == 'i') {
			InsertNode(v);
		} else if(s[0] == 'f') {
			printf("%s\n",FindNode(root, v) != NULL?"yes":"no");
		} else if(s[0] == 'd') {
			//DeleteNode(FindNode(&root, v));
		}
	}
	return 0;
}

void PreOrder(pNode root)
{
	if(root == NULL) {
		return;
	}
	printf(" %d",root->v);
	PreOrder(root->l);
	PreOrder(root->r);
}

void InOrder(pNode root)
{
	if(root == NULL) {
		return;
	}
	InOrder(root->l);
	printf(" %d",root->v);
	InOrder(root->r);
}

void InsertNode(const int& v)
{
	pNode p = NULL, q = root;
	while(q != NULL) {
		p = q;
		if(v < q->v) {
			q = q->l;
		} else {
			q = q->r;
		}
	}
	pNode t = new Node;
	t->v = v;
	t->p = p;
	if(root == NULL) {
		root = t;
	} else {
		if(v < p->v) {
			p->l = t;
		} else {
			p->r = t;
		}
	}
}

pNode FindNode(pNode root, const int&v)
{
	while(root != NULL && root->v != v) {
		if(v < root->v) {
			root = root->l;
		} else {
			root = root->r;
		}
	}
	return root;
}



Measured memory_bytes: 21328
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
int main(){
  ll n, k;
  cin >> n >> k;
  ll ans = 0;
  ll add;
  for(ll i = k; i <= n+1; i++){
    ll min = i*(i-1)/2;
    ll max = i*((2*n) - i + 1)/2;
    add = max - min + 1;
    ans = (ans + add) % 1000000007;
  }
  cout << ans;
}

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

int main(){
  int N;
  string S;
  cin >> N >> S;
  vector<int> E(N+2,0);
  vector<int> W(N+2,0);
  for(int i=1; i<=N; i++){
    if(S[i-1]=='E'){
      E[i]= E[i-1]+1;
    }else{
      E[i]=E[i-1];
    }
  }
  for(int i=N; i>=1; i--){
    if(S[i-1]=='W'){
      W[i]=W[i+1]+1;
    }else{
      W[i]=W[i+1];
    }
  }
  int M=0;
  for(int i=1; i<=N; i++){
    M=max(M, E[i-1]+W[i+1]);
  }
  cout << N-M-1 << endl;
  return 0;
}

Measured memory_bytes: 3076
#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0;i< (n);i++)
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<ll, int> pli;
typedef pair<int, ll> pil;
//long long ccw(const Point& A, const Point& B, const Point& C) {
//	return 1LL * (B.x - A.x)*(C.y - A.y) - 1LL * (B.y - A.y)*(C.x - A.x);
//}
int d[100001];

int main() {
	// D , D , 앳코더 1회 ㄱ? 
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	int n; cin >> n;
	d[1] = 1;
	d[2] = 2;
	for (int i = 3; i <= n; i++) {
		d[i] = d[i - 1] + 1; 

		for (int j = 1; (int)pow(9, j) <= i; j++) {
			d[i] = min(d[i], d[i - (int)pow(9, j)] + 1);
		}
		for (int j = 1; (int)pow(6, j) <= i; j++) {
			d[i] = min(d[i], d[i - (int)pow(6, j)] + 1);
		}
	}

	cout << d[n] << '\n';
	

}

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

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

/*
  n m s g1 g2
  a b c
  ...
  am bm cm
  0 0 0 0 0
  */

int n,m,s,g1,g2;
int edge[128][128];
int main(){
  while(scanf("%d%d%d%d%d",&n,&m,&s,&g1,&g2),n|m|s|g1|g2){
    s--; g1--; g2--;
    //init
    rep(i,128)rep(j,128)edge[i][j]=INT_MAX;
    rep(i,128)edge[i][i]=0;

    // input
    rep(i,m){
      int a,b,c;
      scanf("%d%d%d",&a,&b,&c);
      edge[a-1][b-1]=c;
    }

    // í[µáéÓë¢Ç
    rep(k,n){
      rep(i,n){
        rep(j,n){
          if( edge[i][k]!=INT_MAX && edge[k][j]!=INT_MAX ){
            edge[i][j] = min(edge[i][j], edge[i][k]+edge[k][j]);
          }
        }
      }
    }

    int ans = INT_MAX;
    rep(k,n){
      if( k==g1 ){
        if( edge[s][g1]!=INT_MAX && edge[g1][g2]!=INT_MAX ){
          ans = min(ans, edge[s][g1]+edge[g1][g2]);
        }
      }else if( k==g2 ){
        if( edge[s][g2]!=INT_MAX && edge[g2][g1]!=INT_MAX ){
          ans = min(ans, edge[s][g2]+edge[g2][g1]);
        }
      }else{
        if( edge[s][k]!=INT_MAX && edge[k][g1]!=INT_MAX && edge[k][g2]!=INT_MAX ){
          ans = min(ans, edge[s][k]+edge[k][g1]+edge[k][g2]);
        }
      }
    }
    printf("%d\n",ans);
  }
  return 0;
}

Measured memory_bytes: 936
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;


int main(){
  int t,n,cnt=0;
  for(int i=0;i<4;++i){
    cin >> t>>n;
    if(t==1) cout << 6000*n;
    else if(t==2) cout << 4000*n;
    else if(t==3) cout << 3000*n;
    else cout << 2000*n;

    cout << endl;
  }
  
  return 0;
}



Measured memory_bytes: 3116
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const ll MOD = 1e9 + 7;
const ll INF = LLONG_MAX;

int main()
{
    int n;
    cin >> n;
    int a[200];
    for (int i = 0; i < n; i++)
    {
        cin >> a[i];
    }
    int mi = INT_MAX;
    for (int i = -101; i <= 101; i++)
    {
        int ans = 0;
        for (int j = 0; j < n; j++)
        {
            if (a[j] != i)
                ans += (a[j] - i) * (a[j] - i);
        }
        mi = min(mi, ans);
    }
    cout << mi << endl;
}

Measured memory_bytes: 256
// C - Dice and Coin
#include <bits/stdc++.h>
using namespace std;
#define lli long long int
#define uli unsigned long long int
#define rep(i, m, n) for (lli i = m; i < (n); i++)
#define repe(i, m, n) for (lli i = m; i <= (n); i++)
#define ALL(x) (x).begin(), (x).end()
#define SIZE(x) ((lli)(x).size())
#define MAX(x) *max_element(ALL(x))
#define MIN(x) *min_element(ALL(x))
#define _GLIBCXX_DEBUG
const lli INF = 2147483647;
const lli MINF = -2147483648;
const lli LINF = 9223372036854775807;
const lli MOD = 1000000007; //10^9+7
const double PI = acos(-1);
#define SORT(n) sort(n.begin(), n.end())
#define SORTR(n) sort(n.begin(), n.end(), greater<int>())
#define REV(n) reverse(n.begin(), n.end())
#define pb push_back
#define eb emplace_back
#define mp make_pair
#pragma GCC optimize("Ofast")
using vi = vector<int>;
using vvi = vector<vi>;
using vvvi = vector<vvi>;
using vlli = vector<lli>;
using vvli = vector<vlli>;
using vs = vector<string>;
using vvs = vector<vs>;
using vb = vector<bool>;
using vvb = vector<vb>;
using ll = long long;
// vector入力
template <typename T>
istream &operator>>(istream &is, vector<T> &vec)
{
  for (T &x : vec)
    is >> x;
  return is;
}
// vector出力
template <typename T>
ostream &operator<<(ostream &os, vector<T> &vec)
{
  // os << '{';
  for (int i = 0; i < vec.size(); i++)
  {
    os << vec[i] << (i + 1 == vec.size() ? "" : "");
  }
  // os << '}';
  return os;
}
// aよりもbが大きいならばaをbで更新する(更新されたならばtrueを返す)
template <typename T>
bool chmax(T &a, const T &b)
{
  if (a < b)
  {
    a = b; // aをbで更新
    return true;
  }
  return false;
}
// aよりもbが小さいならばaをbで更新する(更新されたならばtrueを返す)
template <typename T>
bool chmin(T &a, const T &b)
{
  if (a > b)
  {
    a = b; // aをbで更新
    return true;
  }
  return false;
}

int main()
{
  ios::sync_with_stdio(false);
  cin.tie(0);
  lli b = 0, k, n, ans = 0, count = 0;
  double a = 0, w = 0, c = 0, h = 0;
  string s, t;
  vector<pair<string, pair<lli, lli>>> pr;
  cin >> n >> k;
  repe(i, 1, n)
  {
    count = i;
    while (count < k)
    {
      count *= 2;
      ans++;
    }
    b = max(b, ans);
    w += ans;
    ans = 0;
  }

  a = n * pow(2LL, b);

  repe(i, 1, n)
  {
    count = i;
    while (count < k)
    {
      count *= 2;
      ans++;
    }
    h = n * pow(2, ans);
    c += a / h;
    ans = 0;
  }
  // cout << a << " " << b << " " << w << " " << c << endl;
  cout << fixed << setprecision(12) << c / a << endl;
}

Measured memory_bytes: 4104
use itertools::{iproduct, Itertools};
use proconio::input;

fn main() {
    input!(n: usize, k: usize, ijc: [(usize, usize, char); n]);
    let mut g = vec![vec![0; k + 1]; k + 1];
    let mut b_count = 0;
    let mut w_count = 0;
    for &(i, j, c) in &ijc {
        g[i % k + 1][j % k + 1] += if ((i / k + j / k) % 2 == 1) ^ (c == 'W') {
            w_count += 1;
            1
        } else {
            b_count += 1;
            -1
        };
    }
    for (i, j) in iproduct!(0..=k, 0..=k) {
        if 0 < i {
            g[i][j] += g[i - 1][j];
        }
        if 0 < j {
            g[i][j] += g[i][j - 1];
        }
        if 0 < i && 0 < j {
            g[i][j] -= g[i - 1][j - 1];
        }
    }

    let (min, max) = iproduct!(0..k, 0..k)
        .map(|(i, j)| g[k][k] - g[i][k] - g[k][j] + 2 * g[i][j] - g[0][j] - g[i][0])
        .minmax()
        .into_option()
        .unwrap();
    println!("{}", std::cmp::max(-min + w_count, max + b_count));
}


Measured memory_bytes: 10240
#include <stdio.h>
#include <vector>
#include <iostream>
#include <queue>
#include <bits/stdc++.h>
 
#define rep(i,n) for (int i=0;i<(n);++i)
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<double> vd;
typedef pair<int, int> pi;

const int MOD = 1e9+7;

ll mpow(ll a, ll n){
  ll p = 1;
  while(n){
    if (n & 1) p = (p * a) % MOD;
    n >>= 1;
    a = (a * a) % MOD;
  }
  return p;
}

ll comb(ll n, ll m){
  ll mat=1, chi=1;
  rep(i, m){
    mat = (mat * (n-i)) % MOD;
    chi = (chi * (i+1)) % MOD;
  }
  return mat * mpow(chi, MOD - 2) % MOD;
}


int main() {
  int n, a, b;
  cin >> n >> a >> b;

  int ans = mpow(2, n) - 1;
  ans -= comb(n, a);
  ans -= comb(n, b);
  
  while (ans < 0) ans += MOD;

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

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <string>
#include <cmath>
#include <algorithm>
#include <utility>
#include <queue>
#include <set>
#include <map>
#include <deque>
#include <iomanip>
#include <cstdio>
#include <stack>
#include <numeric>

using namespace std;
typedef  long long ll;
typedef pair<int,int> PII;
typedef vector<int> VI;
typedef vector<VI> VVI;
#define  MP make_pair
#define  PB push_back
#define inf 1000000007
#define mod 1000000007
#define rep(i,n) for(int i=0;i<(int)(n);++i)


int main(){
    int n;
    cin >> n;
    vector<int>a(n+1);
    rep(i,n){
        cin >> a[i+1];
    }
    vector<int>b(n+1);
    for(int i=n;i>0;i--){
        int k= i;
        int c = 0;
        for(int j=k;j<=n;j+=k){
            c += b[j];
        }
        if(c%2!=a[i]){
            b[i] = 1;
        }
        
        
    }
    vector<int>s;
    rep(i,n+1){
        if(b[i])s.push_back(i);
    }
    cout << s.size() << endl;
    if(s.size()==0)return 0;
    for(auto x:s){
        cout << x << " ";
    }
    cout << endl;
    return 0;
}

Measured memory_bytes: 3192
#include <stdio.h>
int main(void){
    char a[4];
    // char siki[10];
    int i,j;
    for(i=0;i<4;i++){
        scanf("%c",&a[i]);
    }
    for(i=0;i<8;i++){
        // printf("%d回目\n",i);
        char siki[10]={'\0'};
        siki[0]=a[0];
        for(j=0;j<3;j++){
            if(i&(1<<j)){
                sprintf(siki,"%s%c%c",siki,'+',a[j+1]);
            }
            else{
                sprintf(siki,"%s%c%c",siki,'-',a[j+1]);
            }
        }
        int g=a[0]-'0';
        /*for(j=0;j<8;j++){
            printf("%c",siki[j]);
        }
        printf("\n");*/
        for(j=0;j<5;j+=2){
            // printf("%c,%d\n",siki[j+1],j);
            if(siki[j+1]=='+')
                g=g+(siki[j+2]-'0');
            else
                g=g-(siki[j+2]-'0');
            // printf("%c,j=%d\n",siki[j+2],j);
            // printf("%d\n",g);
        }
        // printf("%d\n",g);
        if(g==7){
            for(j=0;siki[j]!='\0';j++)
                printf("%c",siki[j]);
            printf("=7\n");
            return 0;
        }
    }
}

Measured memory_bytes: 128
n,m = map(int,input().split(" "))
li = []

for i in range(n):
    a,b = map(int,input().split(" "))
    li.append((a,b))

li.sort()

result = 0
count = 0
flag = False
for i in range(m):
    for j in range(li[i][1]):
        result += li[i][0]
        count += 1
        if count == m:
            flag = True
            break
    if flag:
        break
print(result)

Measured memory_bytes: 16892
#include<iostream>
#include<string>
#include<cstring>
using namespace std;
int main()
{
        int num1=0,num2=0,e=0;
        char test1[8][8];
        
        cin>>num1>>num2;
        for(int i=0;i<num1;i++){
        	for(int q=0;q<num2;q++){
        		cin>>test1[i][q];
        	}
        }
        for(int w=0;w<num1-1;w++){
        	for(int r=0;r<num2;r++){
        	e=w+1;
        	if(test1[w][r]=='#'){
        		for(int t=0;t<r;t++){
        			if(test1[e][t]=='#'){
        				cout<<"Impossible\n";
        				goto AA;
        			}
        		}
        	}
        	}
        }
        cout<<"Possible\n";
        AA:;
	return 0;
}


Measured memory_bytes: 384
S=input()
T=input()
t=len(T)
for i in range(len(S)-t,-1,-1):
    for j in range(t):
        k=S[i+j]
        if k !=T[j] and k!="?" :break
    else:
        print((S[:i]+T+S[i+t:]+"").replace("?","a"))
        exit()
print("UNRESTORABLE")







Measured memory_bytes: 3060
#include<iostream>
using namespace std;
int main()
{
   long long int i,m,p;
   cin>>i>>m;
   p=i*m;
   if(p%2!=0)
   {
       cout<<"Odd"<<endl;
   }
   if(p%2==0)
   {
       cout<<"Even"<<endl;
   }

}


Measured memory_bytes: 256
#include <iostream>
#include <sstream>
#include <fstream>
#include <string>
#include <vector>
#include <deque>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <algorithm>
#include <functional>
#include <utility>
#include <bitset>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <cstdio>

using namespace std;

int main(){
	int n,m;cin>>n>>m;
	string s;cin>>s;
	s[m-1] += 32;
	cout<<s;
	return 0;

}


Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
#include <stdio.h>
#include<algorithm>
#include<cstring>
#include <string>
#include<cmath>
#include<cstdlib>
#include<queue>
#include<map>
#include<vector>
#include<bits/stdc++.h>
#include <set>
#define ll   long long
#define IO ios::sync_with_stdio(false);cin.tie();cout.tie(0)
#define inf 0x3f3f3f
#define pi 3.1415926535898
using namespace std;
const int N=1e5+10;
const int mod=1e9+7;
ll a[N];
map<ll,int > m1;
int main()
{
    int n,m;
    cin>>n>>m;
    ll ans=0;
    for(int i=1; i<=n; i++)
    {
        ll x;
        cin>>x;
        a[i]=a[i-1]+x;
        ll k=a[i]%m;
        ans+=m1[k];
        if(k==0)
        {
            ans++;
        }
        m1[k]++;
    }
    cout<<ans<<endl;
    return 0;
}


Measured memory_bytes: 8088
#include<iostream>
#include<string>
using namespace std;
int main(){
  string str;
  int ab[26]={};
  int i;
  while(getline(cin,str)){
    for(i=0;i<str.size();i++){
      if(str[i]>='a'&&str[i]<='z') ab[str[i]-'a']++;
      else if(str[i]>='A'&&str[i]<='Z') ab[str[i]-'A']++;
    }
  //cout << str << endl;
  }
  for(i=0;i<26;i++){
    cout << (char)('a'+i) << " : " << ab[i] << endl;
  }
  return 0;
}



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

using ll = long long;
using namespace std;
const int INFint = 2e9+1;
const ll INFll = 2e18+1;
ll MOD=1e9+7;


int main(){
  int N,A,B;
  cin>>N>>A>>B;
  vector<int> P(N);
  for(int i(0);i<N;i++){
    cin>>P[i];
  }
  int cnt1(0),cnt2(0),cnt3(0);
  for(int i(0);i<N;i++){
    if(P[i]<=A){
      cnt1++;
    }else if(P[i]>B){
      cnt3++;
    }else{
      cnt2++;
    }
  }
  cout << min({cnt1,cnt2,cnt3}) << endl;
  return 0;
}



Measured memory_bytes: 256
#include<cstdio>

int main(void){
        int i,j;
        long long n;
        scanf("%lld", &n);

        if(n%2==1){
                printf("0\n");
                return 0;
        }

        n=n/2;
        long long ans=0;
        while(n!=0){
                ans=ans+(n/5);
                n=n/5;
        }
        printf("%lld\n", ans);
        return 0;
}


Measured memory_bytes: 128
#include <iostream>
using namespace std;
int min_cost(int h[],int n){
    int dp[n];
    dp[0]=0,dp[1]=abs(h[0]-h[1]);
   for(int i=2;i<n;i++)
       dp[i]=min(dp[i-1]+abs(h[i]-h[i-1]),dp[i-2]+abs(h[i]-h[i-2]));
       
    return dp[n-1];
}
int main() {
    int n;
    cin>>n;
    int h[n];
    for(int i=0;i<n;i++) cin>>h[i];
    cout<<min_cost(h,n);
	return 0;
}

Measured memory_bytes: 4344
#include <stdio.h>

int main(void) {
  int a, b, c;
  scanf("%d%d%d", &a, &b, &c);
  int memo;
  if (a > b) {
    memo = a;
    a = b;
    b = memo;
  }
  if (b > c) {
    memo = b;
    b = c;
    c = memo;
  }
  if (a > b) {
    memo = a;
    a = b;
    b = memo;
  }

  printf("%d %d %d\n", a, b, c);

  return 0;
}



Measured memory_bytes: 2056
#include <iostream>
#include <vector>
using namespace std;
long long const mod = 998244353;
long long mod_fact(int x){
    static vector<long long> fact = {1, 1};
    if(x < 0)return 0; //
    if(x < fact.size())return fact[x];
    for(int i = fact.size(); i <= x; i++){
        fact.push_back((fact[i-1] * i) % mod);
    }
    return fact[x];
}

long long mod_pow(long long a, long long b){
    long long res = 1;
    a %= mod;
    while(b > 0){
        if(b%2 == 1) res = (res * a) % mod;
        a = (a * a) % mod;
        b /= 2;
    }
    return res;
}

long long mod_inv(long long a){
    return mod_pow(a, mod-2);
}

long long mod_comb(int a, int b){
    if(b < 0 || a < b)return 0;
    if(b > a/2)return mod_comb(a, a-b);
    return (((mod_fact(a) * mod_inv(mod_fact(a-b))) % mod) * mod_inv(mod_fact(b))) % mod;
}


int main(void){
    int n, s;
    cin >> n >> s;
    vector<int> a(n+1, 0);
    vector< vector< long long > > b(n+1, vector<long long>(s+1, 0));
    for(int i=1;i<=n;i++) cin >> a[i];
    b[0][0] = mod_pow(2, n);
    long long p = mod_inv(2);
    for(int i=1;i<=n;i++){
        for(int j=0;j<=s;j++){
            b[i][j] = b[i-1][j];
            if(a[i] <= j){
                b[i][j] += b[i-1][j-a[i]]*p;
                b[i][j] %= mod;
            }

        }
    }
    cout << b[n][s] << endl;
}


Measured memory_bytes: 73556
#include "bits/stdc++.h"
using namespace std; 

#define IOS {ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);}
#define ll long long 

ll powermod(ll x,ll ex,ll md){ll ans=1ll;while(ex>0){if(ex&1ll) ans=(ans*x)%md; ex>>=1ll;x=(x*x)%md;}return ans;}
inline ll gcd(ll a,ll b) {if(b==0)return a;a%=b;return gcd(b,a);}
inline ll max(ll a,ll b) {return((a>b)?a:b);}
inline ll min(ll a,ll b) {return((a>b)?b:a);}

const ll mod=1e9+7;
int main(){
        IOS;
        ll n;
        cin>>n;
        if(n==1) cout<<0<<"\n";
        else{
                ll ans=0;
                ans=powermod(10, n  ,mod);
                ans%=mod;

                ans-=powermod(9, n  ,mod);
                // ans-=powermod(n , 9,mod);
                ans=(ans+mod)%mod;

                ans-=powermod(9, n  ,mod);
                // ans-=powermod(n , 9,mod);
                ans=(ans+mod)%mod;

                ans+=powermod(8, n  ,mod);
                // ans+=powermod(n , 8,mod);
                ans=(ans+mod)%mod;

                cout<<ans<<'\n';
        }
}


Measured memory_bytes: 3656
#include <bits/stdc++.h>
#include <boost/multiprecision/cpp_int.hpp>

using namespace std;
using boost::multiprecision::cpp_int;

typedef long long ll;
typedef pair<ll, ll> pll;

const ll INF = 1e17;
const ll MOD = 1e9+7;

int main() {
    // input, ready
    ll n;
    cin >> n;

    ll x = (ll)sqrt(n);
    for (ll i=x; i>=0; i--) {
        if (n%x == 0) break;
        x--;
    }

    cout << x + (n /x) -2 << endl;

    return 0;
}


Measured memory_bytes: 256
#include <iostream>

using namespace std;

int main()
{
    int A = 0, N = 0, B = 0;
    int ans = 0;
    cin >> N >> A >> B;

    if((N * A) > B){
        ans = B;
    }else{
        ans = (N * A);
    }

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



Measured memory_bytes: 256
//AOJ ITP1_1_C

using System;

class sample
{
    public static void Main()
    {
        string[] str = Console.ReadLine().Split(' ');
        int a = int.Parse(str[0]);
        int b = int.Parse(str[1]);

        Console.WriteLine("{0} {1}", a * b, (a + b) * 2);
    }
}

Measured memory_bytes: 9176
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <climits>
#include <cmath>
#include <map>
using namespace std;
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++ )
#define repf(i,m,n) for(int (i)=m;(i)<n;(i)++)
#define all(v) (v).begin(), (v).end()
#define ll long long
#define vec(name,num) vector<ll> name((num),0);
#define op(i) cout<<(i)<<endl;
#define ip(i) cin>>(i);
#define opN cout<<"No"<<endl;
#define opY cout<<"Yes"<<endl;
#define opP cout<<"Possible"<<endl;
#define opI cout<<"Impossible"<<endl;
#define mat(name,fnum,snum); vector<vector<ll>> name((fnum),vector<ll>((snum),0));
#define debugP int debug_point; cin>>debug_point;
const ll MOD= 1e9 + 7;
template <typename T>
void putv(vector<T>& V){
	// cout << "The elements in the vector are: " << endl;
	for(auto x: V)
		cout << x << " ";
	cout << endl;
}

template <class T>
vector<T> getv(ll n){
	vector<T> Vector_temp;
	rep(i,n){
		T input;
		cin >> input;
		Vector_temp.emplace_back(input);
	}
	return Vector_temp;
}
ll gcd(ll c,ll b){
    while(1){
        if(c%b!=0){
        ll tmp=b;
        b=c%b;
        c=tmp;
        }else{
            return b;
        }
    }
}
/* <3<3<3<3<3<3<3<3<3<3<3<3<3<3<3<3<3<3<3<3<3<3<3<3<3<3<3<3<3<3<3<3*/

int main(){
  string s;
  ll n;
  cin>>n;
  cin>>s;
  vec(aa,26);
  vec(bb,26);
  ll cnt=0;
  ll ans=0;
  rep(i, s.size()) {
    rep(j,i+1 ) {
      aa[s[j]-'a']++;
    }
    repf(j,i+1,s.size() ) {
      bb[s[j]-'a']++;
    }
    rep(j, 26) {
      if(bb[j]!=0&&aa[j]!=0){
        cnt++;
        
      }
      aa[j]=0;bb[j]=0;
    }
    ans=max(ans,cnt);
    cnt=0;
  }
  op(ans);
   return 0;
}

Measured memory_bytes: 256
// clang-format off
#include <bits/stdc++.h>
#define int long long
#define main signed main()
// #define main int main()
#define loop(i, a, n) for (int i = (a); i < (n); i++)
#define rep(i, n) loop(i, 0, n)
#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()
#define prec(n) fixed << setprecision(n)
#define stlice(from, to) substr(from, (to) - (from) + 1)
#define pb push_back
#define mp make_pair
#define mt make_tuple
#define fi first
#define se second
using namespace std;
using pii = pair<int, int>;
using vi = vector<int>;
using vd = vector<double>;
using vc = vector<char>;
using vb = vector<bool>;
using vs = vector<string>;
using vpii = vector<pii>;
using vvi = vector<vi>;
using vvb = vector<vb>;
using vvpii = vector<vpii>;
template<typename A> using fn = function<A>;
constexpr int INF = sizeof(int) == sizeof(long long) ? 1000000000000000000LL : 1000000000;
constexpr int MOD = 1000000007;
constexpr double PI = acos(-1);
template<typename A, typename B> bool cmin(A &a, const B &b) { return a > b ? (a = b, true) : false; }
template<typename A, typename B> bool cmax(A &a, const B &b) { return a < b ? (a = b, true) : false; }
constexpr bool odd(const int &n) { return n & 1; }
constexpr bool even(const int &n) { return !odd(n); }
void solve();
main { solve(); return 0; }
// clang-format on

void solve() {
  for (;;) {
    vs s(12);
    rep(i, 12) if (!(cin >> s[i])) return;
    int c = 0;
    rep(i, 12) rep(j, 12) {
      fn<void(int, int)> f = [&](int i, int j) {
        if (i < 0 || j < 0 || i >= 12 || j >= 12) return;
        if (s[i][j] == '0') return;
        s[i][j]  = '0';
        int di[] = {1, 0, -1, 0}, dj[] = {0, 1, 0, -1};
        rep(k, 4) f(i + di[k], j + dj[k]);
      };
      c += s[i][j] == '1';
      f(i, j);
    }
    cout << c << endl;
  }
}

Measured memory_bytes: 3108
#include<iostream>
#include<vector>
#include<queue>

int main(){
	int n, m;
	std::cin >> n >> m;
	std::vector<std::vector<int>> g(n);
	for(int i=0; i<m; i++){
		int a, b;
		std::cin >> a >> b;
		--a; --b;
		g[a].push_back(b);
		g[b].push_back(a);
	}

	std::vector<int> dist(n, -1); //訪問済み確認
	std::queue<int> que; //検知したノードを格納するキュー
	//初期条件
	dist[0] = 0;
	que.push(0);
	while(!que.empty()){
		int v = que.front();
		que.pop();
		for(auto next_v : g[v]){
			if(dist[next_v] == -1){
				que.push(next_v);
				dist[next_v] = v;
			}
		}
	}

	for(int i=0; i<n; i++){
		if(dist[i] == -1){
			std::cout << "No" << std::endl;
			return 0;
		}
	}
	std::cout << "Yes" << std::endl;
	for(int i=1; i<n; i++){
		std::cout << dist[i]+1 << std::endl;
	}

	return 0;
}

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

long long int n,m,aux;
long long int Posibles[59][59][2509];
long long int Grande=0;
long long int Array[59];

long long int solve(long long int x,long long int y,long long int A){
	if ( x == n ){
		if ( ( A == 0 ) && ( y == 0 ) ){
			return 1ll;
		}else{
			return 0ll;
		}
	}
	if ( y < 0 || A < 0) return 0ll;
	if ( Posibles[x][y][A] != -1 ) return Posibles[x][y][A];
	Posibles[x][y][A] = solve( x+1 , y , A ) + solve( x+1 , y-1 , A-Array[x] );
	return Posibles[x][y][A];
}

int main(){
	for (long long int i = 0; i < 59; ++i){
		for (long long int j = 0; j < 59; ++j){
			for (long long int k = 0; k < 2509; ++k){
				Posibles[i][j][k]=-1;
			}
		}
	}
	scanf("%lld %lld",&n,&m);
	for (long long int i = 0; i < n; ++i)
	{
		scanf("%lld",&aux);
		Array[i]=aux;
	}
	long long int aux2;
	for (long long int j = 1 ; j < n+1 ; j++){
		aux2 = solve(0 , j , j*m );
		Grande+=aux2;
	}
	cout << Grande;
	return 0;
}

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

using namespace std;

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

    int n;
    cin >> n;
    vector <int> A(n), B(n), mark(n, -1);

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

        if (i == 0 || A[i] != A[i - 1]) {
            mark[i] = A[i];
        }
    }

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

    for (int i = n - 1; i >= 0; i--) {
        if (i == n - 1 || B[i] != B[i + 1]) {
            if (mark[i] != -1 && mark[i] != B[i]) {
                cout << "0\n";
                return 0;
            }
            mark[i] = B[i];
        }
    }
    
    for (int i = 0; i < n; i++) {
        if (A[i] < mark[i] || B[i] < mark[i]) {
            cout << "0\n";
            return 0;
        }
    }
    long long res = 1;
    const int mod = 1000 * 1000 * 1000 + 7;

    for (int i = 0; i < n; i++) {
        if (mark[i] == -1) {
            res = (res * min(A[i], B[i])) % mod;
        }
    }
    cout << res << '\n';

    return 0;
}

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

int main()
{
	int n;

	cin >> n;

	for (long d = 0; d < (1 << n); d++) {
		cout << d << ":";

		for (int i = 0; i < n; i++) {
			if (d & (1 << i))
				cout << " " << i;
		}

		cout << endl;
	}

	return 0;
}


Measured memory_bytes: 3136
use proconio::input;

fn main() {
    input! {
        n: usize,
        mut a : [usize; n],
    }

    a.sort_by(|a,b| b.cmp(a));
    let mut ans = a[0];

    let mut count = n-2;
    for f in a.iter().skip(1) {
        if count == 0 {
            break;
        }
        ans += f;
        count-=1;
        if count == 0 {
            break;
        }
        ans += f;
        count-=1;
        if count == 0 {
            break;
        }
    }

    println!("{}", ans);
}


Measured memory_bytes: 6240
#include<bits/stdc++.h>
using namespace std;
struct node{
	int a[3];
	int step;
};
int main()
{
	int a[3];
	for(int i = 0;i<3;i++)
		cin>>a[i];
	queue<node> q;
	sort(a,a+3);
	q.push({a[0],a[1],a[2],0});
	while(!q.empty()){
		node t = q.front();q.pop();
		if(t.a[0] == t.a[1] &&t.a[1]==t.a[2]){
			cout<<t.step<<endl;
			break;
		}
		int x = t.a[0],y = t.a[1] ,z = t.a[2];
		if(z-x>=2){
			a[0] = x+2,a[1] =y;a[2]=z;
			sort(a,a+3);
			q.push({a[0],a[1],a[2],t.step+1});
		}else{
			a[0]=x+1,a[1]=y+1;a[2]=z;
			sort(a,a+3);
			q.push({a[0],a[1],a[2],t.step+1});
		}
	}
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i,s,n) for(ll i = (s); i < (n); i++)
#define all(v) v.begin(), v.end()

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  
  ll n;
  cin >> n;
  
  vector<pair<ll, ll> > a(n);
  rep(i, 0, n) {
    cin >> a[i].first;
    a[i].second = i;
  }
  sort(all(a));
  
  rep(i, 0, n) {
    cout << ( i==a[n-1].second ?a[n-2].first :a[n-1].first) << "\n";
  }
}

Measured memory_bytes: 4864
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <map>
#include <set>
#include <vector>
#pragma comment(linker,"/STACK:102400000,102400000")
#define inf 0x3f3f3f3f
#define mem(x,t) memset(x,t,sizeof(x));
#define maxm 100000
typedef long long ll;
using namespace std;
int main()
{
    ios::sync_with_stdio(false);
    int cost,n;
    cin>>cost>>n;
    int c[maxm],t[maxm];
    for(int i=1;i<=n;i++)
        cin>>c[i];
    for(int i=0;i<maxm;i++)
    {
        t[i]=inf;
    }
    t[0]=0;
    for(int i=1;i<=n;i++)
    {
        for(int j=0;j+c[i]<=cost;j++)
        {
            t[j+c[i]]=min(t[j+c[i]],t[j]+1);
        }
    }
    cout<<t[cost]<<endl;
    return 0;
}



Measured memory_bytes: 3532
# （高速化）貰うDP
def main():
    N,K=map(int,input().split())
    h=[int(_) for _ in input().split()]

    dp=[0]*(N)

    for n in range(1,N):
        dp[n]=min([dp[k] + abs(h[n] - h[k]) for k in range(max(0,n-K), n)])
    print(dp[N-1])

if __name__ == '__main__':
    main()

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

int main(int argc, char const *argv[])
{
    int n;
    cin >> n;
    double ans = 0;
    for(int i = 0; i < n; i++) {
        double x;
        string s;
        cin >> x >> s;
        if(s == "JPY") {
            ans += x;
        } else {
            ans += x * 380000;
        }
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 256
/* Tuan Kkura */
#include <bits/stdc++.h>
typedef long long ll;
typedef unsigned long long ull;
#define base 31
#define MOD 1e9+7
#define FOR(i, a, b) for(int i = a; i <= b; i++)
#define FORs(i, a, b) for(int i = a; i >= b; i--)
#define REP(i, a, b) for(int i = a; i < b; i++)
#define __FOR(i, a, b, k) for(int i = a; i <= b; i+= k)
#define __REP(i, a, b, k) for(int i = a; i < b; i+= k)
#define pb push_back
#define _io ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
using namespace std;

typedef pair <int, int> ii;
typedef vector <ii> vii;
#define fi first
#define se second
#define mp make_pair
#define PROB "text"
#define MAXN 200005

int main()
{
    _io
    int n; cin >> n;
    int cnt1 = 0;
    FOR(i, 1, n)
        if(i%2 == 1) cnt1++;
    cout << fixed << setprecision(8) << (double)cnt1/n << '\n';
}


Measured memory_bytes: 256
#pragma comment (linker, "/STACK:256000000")
 
#define _USE_MATH_DEFINES
#define _CRT_NO_DEPRECEATE
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <iomanip>
#include <fstream>
#include <cstdio>
#include <cstdlib>
#include <string>
#include <cstring>
#include <vector>
#include <utility>
#include <algorithm>
#include <functional>
#include <set>
#include <map>
#include <cmath>
#include <queue>
#include <memory.h>
#include <sstream>
#include <cassert>
#include <ctime>
#include <complex>
 
//#include <random>
 
using namespace std;
 
 
double PI = 3.1415926535897932384626433832795;
long double EPS = 1e-12;
 
typedef unsigned int uint32;
typedef long long int64;
typedef unsigned long long uint64;
 
typedef pair<int, int> pii;
const int MAXN = 1 << 16;
const int ROOT = 333;


int64 a, b, c;

void solve()
{
	cin >> a >> b >> c;
	if ((a & 1) && (b & 1) && (c & 1))
	{
		int64 res = a * b;
		res = min(res, b * c);
		res = min(res, a * c);
		cout << res;
	}
	else
		cout << 0;

}

 
int main()
{
    ios_base::sync_with_stdio(false); cin.tie(0);
#ifdef _MY_DEBUG
    freopen("input.txt", "rt", stdin); freopen("output.txt", "wt", stdout);
#else
    //freopen(TASK ".in", "rt", stdin); freopen(TASK ".out", "wt", stdout);
#endif
    srand(1313);
	
	int t = 1;
	//cin >> t;

	for(int i = 0; i < t; ++i)
	{
		solve();
		
	}
	
    return 0;
}   

Measured memory_bytes: 384
Scanf.scanf "%s" (fun s ->
    let n = String.length s in
    let rec loop i a b =
        if i = n then min a b * 2 else
            if s.[i] = '0' then loop (i + 1) (a + 1) b
                           else loop (i + 1) a (b + 1)
    in
    loop 0 0 0 |> Printf.printf "%d\n"
)

Measured memory_bytes: 4196
#include<iostream>
using namespace std;
int main()
{
    char n;
    cin>>n;
    if(n=='a'||n=='e'||n=='i'||n=='o'||n=='u')
    {
        cout<<"vowel";
    }
    else
    {
        cout<<"consonant";
    }
    return 0;
}

Measured memory_bytes: 256
def getval():
    n = int(input())
    p = list(map(float,input().split()))
    return n,p

def main(n,p):
    dp = [[0 for i in range(n+1)] for i in range(n+1)]
    dp[1][1] = p[0]
    dp[1][0] = 1 - p[0]
    for i in range(2,n+1):
        locp = p[i-1]
        for j in range(n+1):
            dp[i][j] = dp[i-1][j] * (1 - locp)
            if j>0:
                dp[i][j] += dp[i-1][j-1] * locp
    print(sum(dp[n][(n+1)//2:]))
    #print(dp)

if __name__=="__main__":
    n,p= getval()
    main(n,p)  


Measured memory_bytes: 223832
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define rep(i,n) for(int i=0;i<n;i++)
#define REP(i,n) for(int i=1;i<n;i++)
#define all(v) v.begin(),v.end()
#define P pair<int,int>
#define len(s) (int)s.size()
#define pb push_back

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;
}
constexpr int mod = 1e9+7;
constexpr int inf = 3e18;

struct UnionFind{
	vector<int>par,size;
	int find(int x){
		return (par[x]==x?x:par[x]=find(par[x]));
	}
	void merge(int x,int y){
		x=find(x);y=find(y);
		if(x==y)return;
		if(size[x]<size[y]){
			par[x]=y;
			size[y]+=size[x];
		}else {
			par[y]=x;
			size[y]+=size[x];
		}
	}
	bool same(int x,int y){
		return find(x)==find(y);
	}
	UnionFind(int x){
		rep(i,x){
			par.pb(i);size.pb(1);
		}
	}
};
int N,K,L;
signed main(){
	cin>>N>>K>>L;
	map<P,int>mp;
	UnionFind uf1(N),uf2(N);
	rep(i,K){
		int p,q;cin>>p>>q;p--;q--;
		uf1.merge(p,q);
	}
	rep(i,L){
		int p,q;cin>>p>>q;p--;q--;
		uf2.merge(p,q);
	}
	rep(i,N){
		mp[{uf1.find(i),uf2.find(i)}]++;
	}
	rep(i,N){
		cout<<mp[{uf1.find(i),uf2.find(i)}]<<" ";
	}
	cout<<endl;
}


Measured memory_bytes: 18660
#include<bits/stdc++.h>
using namespace std;
int a[1000001],k,n,i,j,sum,temp,ans;
int main()
{
	cin>>n>>k;
	for(i=1;i<=n;i++)
	{
		cin>>temp;
		a[temp]++;
	}
	i=500;
	while(sum<k)
	{
		i--;
		for(j=1;j<=a[i];j++)
		{
			ans=ans+i;
			sum++;
		}
	}
	cout<<ans<<endl;
 } 

Measured memory_bytes: 256
package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
)

var sc = bufio.NewScanner(os.Stdin)
var out = bufio.NewWriter(os.Stdout)

func main() {
	sc.Buffer(make([]byte, 0), 1e6) // maxTokenSize
	sc.Split(bufio.ScanWords)
	defer out.Flush()
	/* --- code --- */

	a := next()
	if a >= "a" && a <= "z" {
		fmt.Println("a")
	} else {
		fmt.Println("A")
	}
}

// -*-*-*-*-*-*-*-*-
// * I/O utilities *
// -*-*-*-*-*-*-*-*-

func next() string {
	sc.Scan()
	return sc.Text()
}

func nextInt() int {
	a, _ := strconv.Atoi(next())
	return a
}

func nextInt64() int64 {
	a, _ := strconv.ParseInt(next(), 10, 64)
	return a
}

func nextFloat64() float64 {
	a, _ := strconv.ParseFloat(next(), 64)
	return a
}

func nextInts(n int) []int {
	ret := make([]int, n)
	for i := 0; i < n; i++ {
		ret[i] = nextInt()
	}
	return ret
}
func nextFloats(n int) []float64 {
	ret := make([]float64, n)
	for i := 0; i < n; i++ {
		ret[i] = nextFloat64()
	}
	return ret
}
func nextStrings(n int) []string {
	ret := make([]string, n)
	for i := 0; i < n; i++ {
		ret[i] = next()
	}
	return ret
}

func split(s string) []string {
	ret := make([]string, len([]rune(s)))
	for i, v := range []rune(s) {
		ret[i] = string(v)
	}
	return ret
}

// -*-*-*-*-*-*-*-*-
// * tool snippets *
// -*-*-*-*-*-*-*-*-
func duplicate2Int(base [][]int) (ret [][]int) {
	ret = make([][]int, len(base))
	for i, v := range base {
		ret[i] = append([]int{}, v...)
	}
	return
}

func max(a, b int) int {
	return int(max64(int64(a), int64(b)))
}

func max64(a int64, b int64) int64 {
	if a < b {
		return b
	}
	return a
}

func min(a, b int) int {
	return int(min64(int64(a), int64(b)))
}

func min64(a int64, b int64) int64 {
	if a < b {
		return a
	}
	return b
}

// *-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-
// * math flavor typical theories *
// *-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-
func gcd(a, b int) int {
	if a > b {
		return gcd(b, a)
	}
	for a != 0 {
		a, b = b%a, a
	}
	return b
}

func pow(a, b int) (ret int) {
	ret = a
	for i := 0; i < b-1; i++ {
		ret *= a
	}
	return
}

func powMod(n, m, mod int) (ret int) {
	ret = 1
	for m > 0 {
		if m&1 == 1 {
			ret *= n
			ret %= mod
		}
		n *= n
		n %= mod
		m >>= 1
	}
	return ret
}


Measured memory_bytes: 1772
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <vector>
using namespace std;
long long read() {
  long long x = 0, w = 1;
  char ch = getchar();
  while (!isdigit(ch)) w = ch == '-' ? -1 : 1, ch = getchar();
  while (isdigit(ch)) {
    x = x * 10 + ch - '0';
    ch = getchar();
  }
  return x * w;
}
const int Max_n = 1e6 + 5;
int n, m, x, y;
int top, w[Max_n], stk[Max_n];
long long s[Max_n], h[Max_n], f[Max_n], g[Max_n];
long long must[Max_n], G[Max_n];
long long F(int x) { return 1ll * (x + 1) * (x) / 2; }
double slp1(int i, int j) {
  return (double)(f[i] + s[i] + F(i - 1) - f[j] - s[j] - F(j - 1)) /
         (i - j);
}
double slp2(int i, int j) {
  return (double)(g[i] + h[i] + F(i) - g[j] - h[j] - F(j)) /
         (i - j);
}
void Max(long long &a, long long b) { a = a < b ? b : a; }
void Solve(int l, int r) {
  int mid = (l + r) >> 1;
  if (l == r) {
    Max(must[l], f[l - 1] + g[l + 1] - w[l] + 1);
    return;
  }
  top = 0;
  G[r + 1] = G[l - 1] = -2e18;
  for (int i = l - 1; i < mid; i++) {
    while (top > 1 && slp1(stk[top - 1], stk[top]) < slp1(stk[top], i)) top--;
    stk[++top] = i;
  }
  for (int i = mid; i <= r; i++) {
    while (top > 1 && slp1(stk[top - 1], stk[top]) < i) top--;
    G[i] = f[stk[top]] + F(i - stk[top]) - s[i] + s[stk[top]] + g[i + 1];
  }
  for (int i = r; i >= mid; i--) Max(G[i], G[i + 1]), Max(must[i], G[i]);
  top = 0;
  for (int i = r + 1; i > mid; i--) {
    while (top > 1 && slp2(stk[top - 1], stk[top]) > slp2(stk[top], i)) top--;
    stk[++top] = i;
  }
  for (int i = mid; i >= l; i--) {
    while (top > 1 && slp2(stk[top - 1], stk[top]) > i) top--;
    G[i] = g[stk[top]] + F(stk[top] - i) - h[i] + h[stk[top]] + f[i - 1];
  }
  for (int i = l; i <= mid; i++) Max(G[i], G[i - 1]), Max(must[i], G[i]);
  Solve(l, mid), Solve(mid + 1, r);
}
int main() {
  n = read();
  for (int i = 1; i <= n; i++) w[i] = read();
  for (int i = 1; i <= n; i++) s[i] = s[i - 1] + w[i];
  for (int i = n; i >= 1; i--) h[i] = h[i + 1] + w[i];
  stk[top = 1] = 0;
  for (int i = 1; i <= n; i++) {
    while (top > 1 && slp1(stk[top - 1], stk[top]) < i) top--;
    f[i] = f[stk[top]] + F(i - stk[top]) - s[i] + s[stk[top]];
    Max(f[i], f[i - 1]);
    while (top > 1 && slp1(stk[top - 1], stk[top]) < slp1(stk[top], i)) top--;
    stk[++top] = i;
  }
  stk[top = 1] = n + 1;
  for (int i = n; i >= 1; i--) {
    while (top > 1 && slp2(stk[top - 1], stk[top]) > i) top--;
    g[i] = g[stk[top]] + F(stk[top] - i) - h[i] + h[stk[top]];
    Max(g[i], g[i + 1]);
    while (top > 1 && slp2(stk[top - 1], stk[top]) > slp2(stk[top], i)) top--;
    stk[++top] = i;
  }
  for (int i = 1; i <= n; i++) must[i] = -2e18; 
  Solve(1, n);
  m = read();
  while (m--) {
    x = read(), y = read();
    printf("%lld\n", max(f[x - 1] + g[x + 1], must[x] + w[x] - y));
  }
}


Measured memory_bytes: 33280
#include <cstdio>
#include <algorithm>
using namespace std;

int n, l, ans;
int icicles[100002], time[100002];

void solve(int i){
    if(icicles[i] > icicles[i - 1] && icicles[i] > icicles[i + 1]){
        time[i] = l - icicles[i] + max(time[i - 1], time[i + 1]);
        ans = max(ans, time[i]);
        icicles[i] = 0;
        solve(i - 1);
        solve(i + 1);
    }

    return;
}

int main(){
    scanf("%d%d", &n, &l);

    for(int i = 1; i <= n; i++){
        scanf("%d", &icicles[i]);
    }
    icicles[0] = 0;
    icicles[n + 1] = 0;

    for(int i = 1; i <= n; i++){
        solve(i);
    }

    printf("%d\n", ans);

    return 0;
}

Measured memory_bytes: 2976
K, N = map(int, input().split())
A = list(map(int, input().split()))

d_min = K
for i in range(N):
    start = A[i]
    if i + 1 < N:
        end = A[i + 1]
    else:
        end = A[0]
    rest = min(abs(start - end), K - abs(start - end))
    d = K - rest
    d_min = min(d_min, d)

print(d_min)

Measured memory_bytes: 26444