akhauriyash/Code-Regression huggingface dataset:
# We Like AGC

N = int(input())
MOD = 1e+9+7
dp = [[[[0 for _ in range(4)] for _ in range(4)] for _ in range(4)] for _ in range(N+1)]
for c1 in range(4):
	for c2 in range(4):
		for c3 in range(4):
			dp[3][c1][c2][c3] = 1

dp[3][0][1][2] = 0
dp[3][0][2][1] = 0
dp[3][1][0][2] = 0

for n in range(4, N+1):
	for c1 in range(4):
		for c2 in range(4):
			for c3 in range(4):
				for a in range(4):
				
					if a==2 and c2 == 0 and c3 == 1:
						continue
					if a==2 and c2 == 1 and c3 == 0:
						continue
					if a==2 and c1 == 0 and c3 == 1:
						continue
					if a==2 and c1 == 0 and c2 == 1:
						continue
					if a==1 and c2 == 0 and c3 == 2:
						continue
				
					dp[n][c2][c3][a] += dp[n-1][c1][c2][c3]
					dp[n][c2][c3][a]  = int(dp[n][c2][c3][a]%MOD)
cnt = 0
mod = 1e+9+7
for c1 in range(4):
	for c2 in range(4):
		for c3 in range(4):
			cnt += dp[N][c1][c2][c3]
cnt = int(cnt%mod)
print(cnt)

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

typedef long long ll;
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int a,b;
    cin>>a>>b;
    if((a%3==0)||(b%3==0)||(a+b)%3==0)
    {
        cout<<"Possible"<<endl;
    }
    else
    {
        cout<<"Impossible"<<endl;
    }
    return 0;
}

Measured memory_bytes: 256
n=int(input())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
s=0
c=0
for i in range(n):
    if b[i]<=a[i]:
        s+=b[i]
    else:
        s+=a[i]
        c=a[i+1]
        a[i+1]+=a[i]-b[i]
        if a[i+1]<0:
            a[i+1]=0
            s+=c
        else:
            s+=b[i]-a[i]
print(s)

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

int main(){
    int N;
    cin>>N;
    vector<int> C(N-1),S(N-1),F(N-1);
    for(int i=0;i<N-1;i++) cin>>C[i]>>S[i]>>F[i];

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

int t=0;
for(int i=0;i<N-1;i++){
    for(int j=i;j<N-1;j++){
    if(time[i]<S[j]) time[i] = S[j];
    else if(time[i]%F[j]==0);
    else time[i] += F[j] - time[i]%F[j];
    time[i]+=C[j];
    }
    cout<<time[i]<<endl;
}
cout<<"0"<<endl;
return 0;
}

Measured memory_bytes: 256
import java.util.*;


public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int K = sc.nextInt();
        int ans = 0;
        for (int a = 1; a <= K; a++) {
            for (int b = 1; b <= K; b++) {
                int d = gcd(a, b);
                for (int c = 1; c <= K; c++) {
                    ans += gcd(d, c);
                }
            }
        }
        System.out.println(ans);
    }

    private static int gcd(int x, int y) {
        if (y == 0) {
            return x;
        }
        return gcd(y, x%y);
    }
}


Measured memory_bytes: 27272
#include "bits/stdc++.h"
using namespace std;
#define mod 1000000007
#define all(c) begin(c),end(c)
template <typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template <typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }
using ll = long long;
using vi = vector<int>; using vs = vector<string>;
int dd[] = { 0, 1, 0, -1, 0 }; //→↓←↑

void solve()
{
	int N;
	vi B;
	vi A;
	vs S;
	while (cin >> N, N)
	{
		B = vi(N + 1100, -1);
		A = vi(N);
		S = vs(N);
		for (int i = 0; i < N; i++)
		{
			cin >> S[i];
			for (int j = 0; j < S[i].size(); j++)
			{
				if (S[i][j] != '.')
				{
					A[i] = j;
					if (j > 0)S[i][j - 1] = '+';
					break;
				}
				else
				{
					S[i][j] = ' ';
				}
			}
			if (B[A[i]] >= 1)
			{
				bool flag = true;
				for (int j = B[A[i]] + 1; j < i; j++)
				{
					if (A[j] < A[i])flag = false;
				}
				if (flag)
				{
					for (int j = B[A[i]] + 1; j < i; j++)
					{
						S[j][A[i] - 1] = '|';
					}
				}
			}
			B[A[i]] = i;
		}
		for (int i = 0; i < N; i++)
		{
			cout << S[i] << endl;
		}
	}
}


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


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

//#define int long long
#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()
#define rep(i,n) for(int i=0;i<n;++i)
#define rep1(i,n) for(int i=1;i<n;++i)
#define exrep(i, a, b) for(ll i = a; i < b; i++)
#define out(x) cout << x << endl
#define EPS (1e-7)
#define gearup ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
typedef long double ld;
typedef long long int ll;
typedef unsigned long long int ull;
typedef vector<int> vi;
typedef vector<char> vc;
typedef vector<bool> vb;
typedef vector<double> vd;
typedef vector<string> vs;
typedef vector<pair<int,int> > vpii;
typedef vector<vector<int> > vvi;
typedef vector<vector<char> > vvc;
typedef vector<vector<bool> > vvb;
typedef vector<vector<double> > vvd;
typedef vector<vector<string> > vvs;
typedef vector<ll> vl;
typedef vector<vector<ll> > vvl;
typedef vector<vector<vector<ll> > > vvvl;
ll MOD = 1000000007;
const long long L_INF = 1LL << 60;
const int INF = 2147483647; // 2^31-1
const double PI = acos(-1);
//cout<<fixed<<setprecision(10);

template<class T> inline bool chmin(T& a, T b) {if (a > b) {a = b;return true;}return false;}
template<class T> inline bool chmax(T& a, T b) {if (a < b) {a = b;return true;}return false;}
template<class T> void debug(T v){rep(i,v.size()) cout<<v[i]<<" ";cout<<endl;}
const ll dx[8] = {1, 1, 0, -1, -1, -1, 0, 1};
const ll dy[8] = {0, 1, 1, 1, 0, -1, -1, -1};

signed main()
{   
  gearup;
  ll a,b,c,d; cin>>a>>b>>c>>d;
  ll lcm = c/__gcd(c,d)*d;
  ll res = b - b/c - b/d + b/lcm;
  a--;
  ll res1 = a - a/c-a/d+a/lcm;
  out(res-res1);
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define repit(it, li) for(auto it=li.begin(); it!=li.end(); it++)
using namespace std;
using ll = long long;
using P = pair<int,int>;

map<ll, int> factor(ll x){
	map<ll, int> res;
	ll m=x;
	for(ll i=2; i*i<=x; i++){
		while(m%i==0){
			res[i]++;
			m/=i;
		}
	}
	if(m!=1) res[m]++;
	return res;
}

int main(){
	ll n;
	cin>>n;
	auto fa=factor(n);

	vector<int> fi(fa.size());
	vector<ll> fl;
	repit(it, fa) fl.push_back(it->first);
	ll cnt=0;
	while(1){
		bool ok=false;
		for(int d=0; d<fi.size(); d++){
			fi[d]++;
			if(fi[d]>fa[fl[d]]) fi[d]=0;
			else{
				ok=true;
				break;
			}
		}
		if(!ok) break;
		ll k=1;
		rep(i, fi.size()) rep(_, fi[i]) k*=fl[i];

		ll m=n;
		while(m%k==0) m/=k;
		m%=k;
		if(m==1) cnt++;
	}
	auto fb=factor(n-1);
	ll cnt2=1;
	repit(it, fb) cnt2*=(it->second+1);
	cnt2-=1;
	cnt+=cnt2;

	cout<<cnt<<endl;
	return 0;
}


Measured memory_bytes: 3636
#include<iostream>
#include<string>
#include<string.h>
#include<algorithm>
#include<stdio.h>
#include<cmath>
#include<vector>
#include<utility>
#include<stack>
#include<queue>
#include<list>
#include<bitset>
 
#define FOR(i, a, b) for(int i=(a);i<=(b);i++)
#define RFOR(i, a, b) for(int i=(a);i>=(b);i--)
#define MOD 1000000007
#define INF 1000000000
 
using namespace std;
 
int main(void) {
	string s, t;
	string x, y;
	bool flag = false;
	int dp[51] = {};
 
	cin >> s >> t;
 
	FOR(i, 0, s.size() - 1) {
		FOR(p, 0, t.size() - 1) {
			if (s[i + p] != t[p] && s[i+p] != '?') {
				break;
			}
			if (p == t.size() - 1) {
				dp[i] = 1;
			}
		}
	}
	FOR(i, 0, 50) {
		if (dp[i] == 1) {
			if (flag == false) {
				flag = true;
				x = s;
				FOR(p, i, i + t.size() - 1) {
					x[p] = t[p - i];
				}
				FOR(p, 0, x.size() - 1) {
					if (x[p] == '?') {
						x[p] = 'a';
					}
				}
			}
			else {
				y = s;
				FOR(p, i, i + t.size() - 1) {
					y[p] = t[p - i];
				}
				FOR(p, 0, x.size() - 1) {
					if (y[p] == '?') {
						y[p] = 'a';
					}
				}
				if (y <= x) {
					x = y;
				}
			}
			
		}
	}
	if (x.size() == 0) {
		cout << "UNRESTORABLE" << endl;
	}
	else {
		cout << x << endl;
	}
	
	return 0;
}

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

const int INF = 1001001001;

int main() {
  int d, g;
  cin >> d >> g;
  vector<int> p(d, 0), c(d, 0);
  rep(i, d) cin >> p[i] >> c[i];

  ll ans = INF;
  rep(bit, 1 << d) {
    ll tot = 0;
    ll num = 0;

    // 全完する難易度帯を 2D 通りで決め打ちする
    rep(i, d) {
      if (bit >> i & 1) {
        tot += 100 * (i + 1) * p[i] + c[i];
        num += p[i];
      }
    }

    if (tot >= g) {
      // 決め打ちで g 点に到達している場合はそれで OK
      ans = min(ans, num);
    } else {
      // それだけでは到達していない場合, 全完対象でないもののうち
      // Greedy に高難易度順から解いていけば OK
      for (int i = d - 1; i >= 0; i--) {
        if (bit >> i & 1) continue;
        rep(j, p[i]) {
          if (tot >= g) break;
          tot += 100 * (i + 1);
          num++;
        }
      }
      ans = min(ans, num);
    }
  }

  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 256
M, N = map(int, input().split())

mm = [input() for _ in range(M)]
nn = [input() for _ in range(N)]
ans = False
for i in range(M - N + 1):
    if (ans == True):
        break
    for j in range(M - N + 1):
        if (ans == True):
            break
        x = []
        temp = mm[j:j + N]
        for k in range(N):
            temp2 = temp[k]
            x.append(temp2[i:i + N])
            
        if (x == nn):
            ans = True

if ans == True:
    print("Yes")
else:
    print("No")


Measured memory_bytes: 3064
#include<bits/stdc++.h>
#define ll long long
#define endl "\n"

#define IOS ios_base::sync_with_stdio(false);cin.tie(NULL);

#define vi vector<int>
#define vl vector<ll>
#define vvi vector<vector<int>>
#define vvl vector< vector<long long>>
#define mi map<int,int>
#define pi pair<int,int>

#define Fori(i,a,b) for(int i=a; i<b; i++)
#define Ford(i, a, b) for(int i=a; i>=b; i--)

#define pb push_back
#define mp make_pair

#define read(a, n) for(int i=0; i<n; i++) cin >> a[i];
#define print(x) cout << "X: == " << x << endl;
#define printMap(a) for(auto it=a.begin() ; it!= a.end() ; it++) {cout << it->first << "  " << it->second << endl; }
#define printVector(a) for(auto it = a.begin() ; it!= a.end() ;it++) {cout << *it << endl;}

#define MOD 1000000007
using namespace std;
int main() {
    IOS
    string s;
    getline(cin >> ws, s);
    int n = s.size();
    if(s[n-1] == 's') {
        // s[n-1] = 'e';
        s += "es";
    } else {
        s += 's';
    }
    cout << s << endl;
}

Measured memory_bytes: 3684
#include <stdio.h>

int main(){

   int a[10000];
   int i, n, max, min;
   long int b = 0;

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

   max = a[0];
   min = a[0];

   for (i = 0; i < n; i++){
      if (max < a[i]){
         max = a[i];
      }
      if (min > a[i]){
         min = a[i];
      }
   }

   printf("%d %d %ld\n", min, max, b);

   return 0;

}

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

int main(){
  int i,j,N,cnt=0,f=0;
  long anscnt=0;
  char ss[200002];
  scanf("%s",ss);
  N=strlen(ss);
  vector<int> intss(N,0);
  for(i=0;i<N;i++){
    if(ss[i]=='A'){
      intss[cnt++]=1;
    }else if(ss[i]=='B'&&ss[i+1]=='C'){
      intss[cnt++]=2;
      i++;
    }else{
      intss[cnt]=3;
      f=0;
      j=0;
      while(intss[j]==2){
        f++;
        j++;
      }
      for(j=f+1;j<cnt;j++){
        if(intss[j]==2){
          anscnt=anscnt+(long)(j-f);
          f++;
        }
      }
      cnt=0;
    }
  }

  intss[cnt]=3;
  f=0;
  j=0;
  while(intss[j]==2){
    f++;
    j++;
  }
  for(j=f+1;j<cnt;j++){
    if(intss[j]==2){
      anscnt=anscnt+(long)(j-f);
      f++;
    }
  }
  printf("%ld\n",anscnt);
  return 0;
}

Measured memory_bytes: 1280
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>

using namespace std;

int main() {
	int a, b, c;
	cin >> a >> b >> c;
	int ans = 0;
	for (int i = a; i <= b; i++) {
		if (c%i == 0)ans++;
	}
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 3096
#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <algorithm>
#include <string>
#include <cmath>
#include <cstdio>
#include <iomanip>
#include <fstream>
#include <cassert>
#include <cstring>
#include <numeric>
#include <ctime>
#include <complex>
#include <bitset>
#include <random>

using namespace std;

typedef long long ll;
typedef long double ld;

#define int ll
#define double ld
#define loop(i, n) for(int i = 0; i < (int)n; ++i)
#define loop1(i, n) for(int i = 1; i <= (int)n; ++i)
#define F first
#define S second
#define pb push_back
#define pi pair <int, int>
#define all(x) begin(x), end(x)
#define ti tuple <int, int, int>
#define Point Vect
#define no {cout << "No"; return;}
#define mkp make_pair
#define mkt make_tuple
#define cerr if (0) cerr

void solve() {
    int n; cin >> n;
    vector <pi> good, bad;
    loop(i, n) {
        string s; cin >> s;
        int bal = 0, minbal = 0;
        loop(j, s.size()) {
            if (s[j] == '(')
                ++bal;
            else {
                --bal;
                if (bal < 0)
                    --minbal;
            }
        }
        if (bal >= 0)
            good.pb({ abs(minbal), bal });
        else
            bad.pb({ bal - minbal , bal });
    }
    int sum = 0;
    sort(all(good));
    for (pi x : good) {
        if (sum < x.F)
            no;
        sum += x.S;
    }
    sort(all(bad), greater<pi>());
    for (pi x : bad) {
        if (sum < x.F - x.S)
            no;
        sum += x.S;
    }
    cout << (sum == 0 ? "Yes" : "No");
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    //int t; cin >> t; loop(i, t)
    solve();
    return 0;
}


Measured memory_bytes: 18996
#include<bits/stdc++.h>
#define mp make_pair
#define ll long long
#define F first
#define S second
#define pi2 6.28318530717958623200
using namespace std;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<string> vs;

vector<int> d(200005,0);
int main()
{
    int n;
    cin>>n;
    for(int i=2;i<=n;i++)
    {
        int a;
        cin>>a;
        d[a]++;
    }
    for(int i=1;i<=n;i++) cout<<d[i]<<endl;

    return 0;
}


Measured memory_bytes: 3840
#include <iostream>
using std::cin ;
using std::cout;

int main(){
  std::ios_base::sync_with_stdio(false);
  cin.tie(0);cout.tie(0);
  int N,K,Q; cin>>N>>K>>Q;
  int num = Q-K;
  int member[1000005];
  for (int i=0;i<Q;++i){
    int tmp; cin>>tmp;
    ++member[tmp-1];
  }
  for(int i=0;i<N;++i){
    if((member[i])>num){
      cout << "Yes" << std::endl;
    }else{
      cout << "No" << std::endl;
    }
  }
  return 0;
}


Measured memory_bytes: 3072
#include <bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<vector>
#include<stdio.h>
#include<cstring>
#include<math.h>
#include<map>
#include<bitset>
#include<iomanip>
#include<queue>
#include<functional>
#include<stack>
#include<tuple>
#include<cassert>
using namespace std;

#define rep(i, n) for (long long i = 0; i < (long long)(n); ++i)
using P = pair<long long, long long>;

long long a[100000];

int main() {
  long long N;
  cin >> N;
  for(long long i = 0; i < N; i++) {
    cin >> a[i];
  }
  long long sum = 0;
  rep(i, N) {
    sum += a[i];
  }
  sum /= 2;
  // cout << sum << endl;
  long long temp = 0;
  for(long long i = 1; 2 * i - 1 <= N - 2; i++) {
    temp += a[2*i-1];
  }
  vector<long long> v;
  v.push_back(sum-temp);
  rep(i, N-1) {
    long long t = v.back();
    long long key = a[i] - t;
    v.push_back(key);
  }

  rep(i, v.size()) {
    v[i] *= 2;
    cout << v[i];
    if(i != v.size() - 1) cout << " ";
    else cout << endl;
  }
  return 0;
}

Measured memory_bytes: 5072
#include <bits/stdc++.h>
#define _GLIBCXX_DEBUG
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rep2(i, s, n) for (int i = (s); i < (int)(n); i++)
using ll = long long;
using P = pair<int,int>;
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()
{
    string  S,T;
    cin >> S >> T;
    vector<int> vecS(S.size());
    vector<int> vecT(S.size());
    map<char,int> mapS;
    map<char,int> mapT;

    rep(i,S.size()){
        if(mapS[S[i]] == 0) mapS[S[i]] = i+1;
        if(mapT[T[i]] == 0) mapT[T[i]] = i+1;
        vecS[i] = mapS[S[i]];
        vecT[i] = mapT[T[i]];
    }

    string ans = "No";
    if(vecS == vecT) ans = "Yes";
    cout << ans << endl;

    return 0;
}
//Ctrl+Shift+Bでコンパイルと実行を行ってデバッグすること

Measured memory_bytes: 2312
#include <cstdio>
#include <vector>
#include <utility>
#include <cstring>

std::vector<std::pair<int, int>> v[100000];
int s[100000];

void dfs(int index)
{
  for (auto &p : v[index])
  {
    if (s[p.first] == -1)
    {
      s[p.first] = s[index] ^ (p.second & 1);
      dfs(p.first);
    }
  }
  return;
}

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

  for (int i = 0; i < n; ++i)
  {
    int a, b, w;
    scanf("%d %d %d", &a, &b, &w);
    v[a - 1].emplace_back(std::pair<int, int>(b - 1, w));
    v[b - 1].emplace_back(std::pair<int, int>(a - 1, w));
  }

  memset(s, -1, n * sizeof(int));
  s[0] = 0;
  for (int i = 0; i < n; ++i)
  {
    dfs(i);
  }
  
  for (int i = 0; i < n; ++i)
  {
    printf("%d\n", s[i]);
  }
  return 0;
}

Measured memory_bytes: 7552
"""
参考
blog名  あっとのTECH LOG   2020-01-24 
url     https://at274.hatenablog.com/entry/2020/01/24/060000
id:     AT274
"""

#初期入力
N = int(input())
 
#
import numpy as np
cnt = [[0] * 10 for i in range(10)]
#count = np.zeros((10,10),dtype=np.int64) 
for i in range(1,N+1):
    n_left =str(i)[0]   #左端の数字（N)
    n_right =str(i)[-1] #右端の数字（N)
    #cnt[int(n_left) , int(n_right)] +=1
    cnt[int(n_left)][int(n_right)] +=1

count =np.array(cnt,dtype=np.int64)
count_T_copy =count.T.copy()
ans =np.sum(count *count_T_copy)
print(ans)

Measured memory_bytes: 12500
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int INF = 1<<30;
const ll LINF = 1LL<<60;

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

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

    ll ans = 0;
    for (int i = 1; i < n; i++) {
        if (a[i] >= a[i-1]) continue;
        else {
            ans += a[i-1]-a[i];
            a[i] = a[i-1];
        }
    }
    
    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 4764
#include <cstdio>
#include <cmath>
#include <complex>
using namespace std;

typedef complex<double> Point;
typedef complex<double> Vec;
typedef pair<Point, Point> Line;

#define X real()
#define Y imag()

Point ps[4];

double dot(Point a, Point b) {
  return (conj(a)*b).X;
}

Point proj(Line l, Point p) {
  Vec v = l.second - l.first;
  double ratio = dot(v, p-l.first) / norm(v);
  return l.first + ratio * v;
}

int main() {
  while (1) {
    for (int i=0; i<3; i++) {
      double x, y;
      if (scanf("%lf,%lf", &x, &y) != 2) return 0; 
      ps[i] = Point(x, y);
      if (i < 2) getchar();
    }

    Point ans = proj(Line(ps[0], ps[1]), ps[2])*2.0 - ps[2];
    printf("%f %f\n", ans.X, ans.Y);
  }
}

Measured memory_bytes: 2764
#include<bits/stdc++.h>
#define REP(i,n) for (int i = 1; i <= n; i++)
#define mod 1000000007
#define pb push_back
#define ff first
#define ss second
#define ii pair<int,int>
#define vi vector<int>
#define vii vector<ii>
#define lli long long int
#define INF 1000000000
#define endl '\n'
const double PI = 3.141592653589793238460;
typedef std::complex<double> Complex;
typedef std::valarray<Complex> CArray;

using namespace std;
lli ar[200001];

int main()
{
	int n , k;
	cin>>k>>n;
	REP(i , n) cin>>ar[i] , ar[i] %= k;
	
	sort(ar + 1 , ar + n + 1);
	
	lli res = ar[n] - ar[1];
	for(int i=2;i<=n;i++)
	{
		res = min(res , ar[n] - ar[i] + k - ar[n] + ar[i-1]);
	}
	cout<<res;
}


Measured memory_bytes: 1792
N = int(input())
S = str(input())
w = S.count('W')
r = S.count('R')
A = 'R'*r+'W'*w
count = 0
for i in range(len(S)):
    if S[i]!=A[i]:
        count += 1

if count%2 ==0:
    print(count//2)
else:
    print(count//2 + 1)

Measured memory_bytes: 9612
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
typedef long long ll;
typedef pair<int,int> P;
int V,d[200001],r[200001],z=1;
vector<int> G[200001];
int bfs(int s){
    rep(i,V+1) d[i]=0,r[i]=0;
    queue<int> que;
    que.push(s);
    r[s]=1;
    while (!que.empty()) {
        int v=que.front();
        que.pop();
        for(int nv:G[v]) {
            if(r[nv]){
                if(d[nv]==d[v]) z=0;
                continue;
            }
            r[nv]++;
            d[nv]=d[v]+1;
            que.push(nv);
        }
    }
}
int main(){
    int n,S[200][200];
    char s[200][200];
    cin>>n;
    V=n;
    rep(i,n)rep(j,n){
        cin>>s[i][j];
        S[i][j]=s[i][j]-'0';
        if(S[i][j]) G[i+1].push_back(j+1);
    }
    int ans=0;
    rep(i,V){
        bfs(i+1);
        rep(j,V) ans=max(ans,d[j+1]+1);
    }
    if(z) cout<<ans;
    else cout<<-1;
}

Measured memory_bytes: 6656
#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#include <queue>
#include <string>
#include <bitset>
#include <list>
using namespace std;
#define rep(i,a,n) for(ll i=a;i<n;i++)
#define rrep(i,a,n) for(ll i=n;i>=a;i--)
#define elif else if
typedef long long ll;
typedef pair<ll,ll> P;
const ll INF = 1e+17;
const ll MODcdf = 998244353;
bool pairCompare(const P& firstElof,const P& secondElof){
    return firstElof.first<secondElof.first;
}
int main(){
    cin.tie(0);
    ios_base::sync_with_stdio(false);
    ll n;cin>>n;
    ll ans,memo;
    memo=1;
    rep(i,1,n+1){
        ans=memo;
        memo=pow(i,2);
        if(memo>n)break;
    }
    cout<<ans<<endl;
}


Measured memory_bytes: 256
n,a,b = gets.chomp.split(' ').map{|n| n.to_i}
x = Array.new(n)
x =  gets.chomp.split(' ').map{|n| n.to_i}
c = 0
for i in 0...x.length - 1 do
  if (x[i+1]-x[i]) * a < b
    c += (x[i+1]-x[i])*a
  else
    c += b
  end
end
p c

Measured memory_bytes: 10244
#include<bits/stdc++.h>
#define ALL(v) (v).begin(),(v).end()
#define REP(i,p,n) for(int i=p;i<(int)(n);++i)
#define rep(i,n) REP(i,0,n)
#define dump(a) (cerr << #a << "=" << (a) << endl)
#define DUMP(list) cout << "{ "; for(auto nth : list){ cout << nth << " "; } cout << "}" << endl;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }


using namespace std;

int main (){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int a;
    double b,c;
    cin >> a;

    if ( a % 2 == 0){
        b = 0.5;
        cout << fixed << setprecision(10) << b << endl;
    } else {
        b = a/2 + 1;
        c = (double)a;
        cout<< fixed << setprecision(10) << b / (c + 0.0)  << endl;
    }


}

Measured memory_bytes: 256
program ABC_086_A_Product 
   implicit none
   integer a, b
   read(*, *) a, b
   if( mod(a*b, 2) == 0 ) then
      write(*, *)'Even'
   else if( mod(a*b, 2) == 1 ) then
      write(*, *)'Odd'
   end if
end program ABC_086_A_Product 

Measured memory_bytes: 256
package main

import "fmt"

func main() {
	var a int
	var b int
	fmt.Scan(&a)
	fmt.Scan(&b)
	var c int
	if b < 0 {
		c = a - b
	} else {
		c = a + b
	}
	if c < a*b {
		fmt.Println(a * b)
	} else {
		fmt.Println(c)
	}
}


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

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

	vector<int> A(N);
	int x;
	for (int i = 0; i < N-1; i++) {
		cin >> x;
		A.at(x - 1)++;
	}

	for (auto y : A) {
		cout << y << endl;
	}
	return 0;
}

Measured memory_bytes: 3620
#include <iostream>
#include <cmath>
#include <complex>
#include <string>
#include <sstream>
#include <limits>
#include <algorithm>
#include <functional>

#include <vector>

using namespace std;

vector<int> nlist;

template<typename value_type>
class ter_search
{
public:
	value_type result;

public:
	ter_search(value_type lo, value_type hi)
		: result(0)
	{
		while (hi - lo >= 3)
		{
			value_type mid1 = (lo * 2 + hi) / 3;
			value_type mid2 = (lo + hi * 2) / 3;

			if (func(mid1) > func(mid2))
			{
				lo = mid1;
			}
			else
			{
				hi = mid2;
			}
		}

		result = func(lo);
		for (value_type x = lo + 1; x <= hi; x++)
		{
			result = min(result, func(x));
		}
	}

public:
	value_type func(value_type x)
	{
		value_type cost = 0;
		for (int i = 0; i < nlist.size(); i++)
		{
			cost += pow(nlist[i] - x, 2);
		}

		return cost;
	}
};

//ter_search<long long> ts(lo, hi);
//long long ret = ts.result;

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

	int N;
	cin >> N;

	nlist.assign(N, 0);
	for (int i = 0; i < N; i++)
	{
		cin >> nlist[i];
	}

	ter_search<int> ts(-100, 100);

	cout << ts.result;
	
	return 0;
}

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


int main()
{
    int card[52];
    int n, i, rank, s;
    char suit;

    for(i=0; i<52; i++)
        card[i] = 0;
        
    cin >> n;
    for(i=1; i<=n; i++) 
    {
        cin >> suit;
        cin >> rank;
        if(suit == 'S')
            s = 0;
        else if(suit == 'H')
            s = 13;
        else if(suit == 'C')
            s = 26;
        else
            s = 39;
        
        s = s + rank - 1;
        card[s] = 1;
    }
    
    for(i=0; i<52; i++)
    {
        if(card[i]==0)
        {
            if(i >= 39)
            {
                suit = 'D';
                rank = i - 39 + 1;
            }
            else if(i >= 26)
            {
                suit = 'C';
                rank = i - 26 + 1;
            }
            else if(i >= 13)
            {
                suit = 'H';
                rank = i - 13 + 1;
            }
            else
            {
                suit = 'S';
                rank = i + 1;
            }
            cout << suit << " " << rank << endl;
        }
    }
}






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

int topCup(int tray)
{
    int count = 0;
    while (tray > 0)
    {
        tray = tray >> 1;
        count++;
    }
    return count;
}

uint64_t trays2ll(const array<uint16_t, 3> &trays)
{
    return ((uint64_t)trays[0] << 32) + ((uint64_t)trays[1] << 16) + ((uint64_t)trays[3] << 0);
}

constexpr int list_from[] = {0, 1, 1, 2};
constexpr int list_to[] = {1, 0, 2, 1};

int solve(const array<uint16_t, 3> &trays, int m)
{
    // 探索したトレイ状態を記録する 同じ状態のトレイを複数回探索することを防ぐ
    unordered_set<uint64_t> seen;

    // 探索していくトレイ状態を操作した回数を記録
    queue<int> task_cost;
    queue<array<uint16_t, 3>> task;

    task.push(trays);
    task_cost.push(0);

    int ans = -1;

    while (!task.empty())
    {
        const int now_m = task_cost.front();
        task_cost.pop();
        const auto now_trays = task.front();
        task.pop();

        // #ifdef DEBUG
        //         cerr << "search tray" << now_m << endl
        //              << bitset<6>(now_trays[0]) << endl
        //              << bitset<6>(now_trays[1]) << endl
        //              << bitset<6>(now_trays[2]) << endl
        //              << endl;
        // #endif

        if (now_m >= m)
            continue;

        // 全カップがトレイAとトレイCのいずれか一方に乗っているなら課題成功
        if ((now_trays[0] == 0 || now_trays[2] == 0) && now_trays[1] == 0)
        {
            ans = now_m;
            break;
        }

        // トレイfromからトレイtoにカップを移す
        for (int i = 0; i < 4; i++)
        {
            const int from = list_from[i], to = list_to[i];
            const int top_from = topCup(now_trays[from]), top_to = topCup(now_trays[to]);
            // トレイfromが空 or トレイto一番上のコップがトレイfromの一番上のコップより大きい → 操作できない
            if (top_from == 0 || top_to > top_from)
                continue;

            array<uint16_t, 3> next_trays = now_trays;
            const int cup_moved = 1 << (top_from - 1);
            next_trays[to] += cup_moved;
            next_trays[from] -= cup_moved;

            if (seen.count(trays2ll(next_trays)))
                continue;

            task_cost.push(now_m + 1);
            task.push(next_trays);
            seen.insert(trays2ll(next_trays));
        }
    }

    return ans;
}

signed main()
{
    cin.tie(0);
    ios::sync_with_stdio(0);
    cout << setprecision(10);

    int n, m;
    while (cin >> n >> m)
    {
        if (n == 0)
            continue;
        array<uint16_t, 3> trays{};
        for (auto &&tray : trays)
        {
            int n_cup;
            cin >> n_cup;
            for (int i = 0; i < n_cup; i++)
            {
                int tmp;
                cin >> tmp;
                tray |= 1 << (tmp - 1);
            }
        }
        cout << dec << solve(trays, m) << endl;
    }
}



Measured memory_bytes: 121496
#include<iostream>

using namespace std;

int main(){
 int a,b,c;
  cin >> a >> b >> c;
  
  if(a==b && a==c) cout << 1 << endl;
  else if((a==b && b!=c)||(a==c && c!=b)||(b==c && c!=a)) cout << 2 << endl;
  else cout << 3 << endl;
}


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

using namespace std;
typedef long long ll;
const int MAXN = 2e5 + 5;
int dp[20][20];

int la(int i)
{
   return i % 10;
}

int fi(int i)
{
    string s = to_string(i);
    reverse(s.begin(),s.end());
    int k = stoi(s);
    return k % 10;
    
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n;
    cin >> n;
    long long ans = 0;
    for(int i = 1 ; i <= n ; i++)
    {
       if(i < 10)
         dp[i][i]++;
       else
       {
          dp[fi(i)%10][la(i)%10]++;
       }
    }
    for(int i = 1 ; i <= 9 ; i++)
    {
        for(int j = 1 ; j <= 9 ; j++)
        {
            ans+=(dp[i][j] * dp[j][i]);
        }
    }
    cout << ans ;
     

    
    
    return 0;
} 

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

#define ld long double
#define ll long long
#define ALL(a)  (a).begin(),(a).end()
#define spa << " " <<
#define MP make_pair
ll MOD = 1e9+7;
//ll MOD = 998244353;
ll INF = 1e18;
void chmin(ll &a, ll b) { if (a > b) a = b; }
void chmax(ll &a, ll b) { if (a < b) a = b; }
void ans1(bool x){
  if(x) cout<<"Yes"<<endl;else cout<<"No"<<endl;}
void ans2(bool x){
  if(x) cout<<"YES"<<endl;else cout<<"NO"<<endl;}
void ans3(bool x){
  if(x) cout<<"Yay!"<<endl;else cout<<":("<<endl;}
void ans(bool x, ll y, ll z){
  if(x) cout<<y<<endl;else cout<<z<<endl;}   


int main(){
  ll i,j;
  ll n,h; cin>>n>>h;
  //ll a,b,c,d,e,f; cin>>a>>b;
  //ll a,b,c,d,e,f; cin>>a>>b>>c;
  //ll a,b,c,d,e,f; cin>>a>>b>>c>>d;
  //string s; cin >> s;
  ll result = 0;
  ll buf = 0;
  bool judge = true;
  //cout<<<<endl;

  
  vector<ll> a(n),b(n);
  for(i=0;i<n;i++){
    cin >> a[i]>>b[i];
  }
  sort(ALL(a),greater<ll>());
  buf = a[0];
  b.push_back(a[0]);
  sort(ALL(b),greater<ll>());
  for(i=0;;i++){
    if(b[i]<=buf||result>=h) break;
    else result+=b[i];
  }
  ll buf2 = 0;
  cout<<i+max(buf2,(h-result+buf-1)/buf)<<endl;
  

  return 0;
}

Measured memory_bytes: 2560
N, M = [int(_) for _ in input().split()]
AB = [[int(_) for _ in input().split()] for i in range(N)]

AB.sort(key=lambda x:x[0])

ret = 0
money = 0

for a, b in AB:
    if ret >= M:
        break

    while ret < M and b >= 1:
        b -= 1
        ret += 1
        money += a
        
print(money)

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


int main(){
    ll n, m;
    cin >> n >> m;
    ll ans=0;
    if(n*2 >= m) ans = m/2;
    else
    {
        ll mm = m - 2*n;
        ans = n+mm/4;

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

Measured memory_bytes: 256
#include <iostream>
#include <stdio.h>
using namespace std;
 
int main(){
    char a[2000] = {0};
    int count[26] = {0};
    for(int i = 0; i < 2000; i++){
        scanf("%c", &a[i]);
        if(cin.eof()) break;
        if('a' <= a[i] && a[i] <= 'z'){
            count[a[i] - 'a']++;
        }else if('A' <= a[i] && a[i] <= 'Z'){
            count[a[i] - 'A']++;
        }
    }
    for(int i = 0; i< 26; i++){
        printf("%c", i + 'a');
        cout << ' ' << ':' << ' ' << count[i] << endl;
    }
    return 0;
}


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

int main() {
  int R; cin >> R;
  if (R < 1200) {
    cout << "ABC";
  }
  else if (R < 2800) {
    cout << "ARC";
  }
  else {
    cout << "AGC";
  }
  cout << endl;
}


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

using namespace std;
		int store = 0;
		int s[10];
		int a[5];
		int ma = 0;
		bool unko = 0;

int main (){
	
	while(1){
		ma = 0;
		unko = 0;
		store = 0;
		int i;
	for(int k = 0;k <= 4;k++){
		i = 2 * k;
	cin >> s[i] >>s[i + 1];
	if(s[i] == 0 && s[i + 1] == 0) 
		{unko = 1; 
	break;
	}
	a[k] = (s[i] + s[i + 1]);
	if(ma < a[k]) {
		store = k;
		ma = a[k];
	}
	}
	if(unko == 1)break;
	switch(store){
	case 0:
		cout << "A " << ma <<endl;
		break;

	case 1:
		cout << "B " << ma <<endl;
		break;

	case 2:
		cout << "C " << ma <<endl;
		break;

	case 3:
		cout << "D " << ma <<endl;
		break;

	case 4:
		cout << "E " << ma <<endl;
		break;
	}



	}

	return 0;
}

Measured memory_bytes: 3040
type point = {x: float; y: float}

let distance a b =
    ((a.x -. b.x)**2.0 +. (a.y -. b.y)**2.0)**0.5

let area a b c =
    let s = (a +. b +. c) /. 2.0 in
    (s *. (s -. a) *. (s -. b) *. (s -. c))**0.5

let () =
    try
        while true do
            let (a, b, c, p)  = Scanf.scanf "%f %f %f %f %f %f %f %f\n"
                (fun ax ay bx by cx cy px py -> {x = ax; y = ay}, {x = bx; y = by}, {x = cx; y = cy}, {x = px; y = py}) in

            let area1 = area (distance a b) (distance b c) (distance c a) in
            let area2 = (area (distance p b) (distance b c) (distance c p))
                     +. (area (distance a p) (distance p c) (distance c a))
                     +. (area (distance a b) (distance b p) (distance p a)) in

            let diff   = (abs_float (area1 -. area2)) in
            let result = if diff < 0.000001 then "YES" else "NO" in
            Printf.printf "%s\n" result
        done
    with
        End_of_file -> ()

Measured memory_bytes: 2748
var input=require('fs').readFileSync('/dev/stdin','utf8')
var lines=input.split('\n')
var h=parseInt(lines.shift().split(' ')[0])
var dist=[...Array(10)].map(()=>lines.shift().split(' ').map(v=>parseInt(v,10)))
var counts=new Array(10).fill(0)
for(var i=0;i<h;i++){lines.shift().split(' ').map(v=>parseInt(v,10)).forEach(v=>counts[v]++)}
for(var k=0;k<10;++k){for(var i=0;i<10;++i){for(var j=0;j<10;++j){dist[i][j]=Math.min(dist[i][j],dist[i][k]+dist[k][j])}}}
console.log([...Array(10).keys()].reduce((p,c)=>p+counts[c]*dist[c][1],0))

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

int main(){
    int a, b, c, i;
    cin >> a >> b >> c;
    for(i=1; i<=b; i++){
        if((a*i)%b == c){
            cout << "YES";
            return 0;
        }
    }
    cout << "NO";
    return 0;
}

Measured memory_bytes: 256
//終局から考える。
//S[i] = '1'なるiについて、A[i]が{A[j], i+1≦j≦N-1, S[j] = '0'}と独立ならx≠0.
//全て従属とする。iが大きい方から考えると、最終的にx=0(従属)にできる。
//独立性の判定:
//・各数を2進数ベクトルと考えて {A[j], i+1≦j≦N-1, S[j] = '0'}について掃き出し法をおこない、
//  表現できるベクトル集合が同一のより単純な表現に直す
//・その表現では'1'の立つ最上位ビットの場所がdistinctだから、A[i]を作れるかを貪欲に判定できる
//計算量はO(TN^3). 厳しい？ -> 定数倍が軽いので大丈夫そう. 
//0ベクトルを取り除かない上に、S[i] = '1'なるiについてもA[i]を追加してしまったバージョン
#include <iostream>
#include <string>
#include <vector>
#define rep(i, n) for(i = 0; i < n; i++)
#define int long long
using namespace std;
 
void sweep(vector<int> &vs) {
	int n = vs.size();
	int row = 0;
	
	for (int i = 59; i >= 0; i--) {
		int pipot = -1;
		for (int j = row; j < n; j++) {
			if ((vs[j] >> i) & 1) {
				pipot = j;
				break;
			}
		}
		if (pipot == -1) continue;
		swap(vs[row], vs[pipot]);
		
		for (int j = row + 1; j < n; j++) {
			if ((vs[j] >> i) & 1) {
				vs[j] ^= vs[row];
			}
		}
		row++;
	}
}
 
int solve(vector<int> a, string s) {
	int n = a.size();
	
	vector<int> vs;
	for (int i = n - 1; i >= 0; i--) {
		if (s[i] == '0') {
			vs.push_back(a[i]);
		}
		else {
			sweep(vs);
			int val = a[i];
			for (int j = 0; j < vs.size(); j++) {
				if ((val ^ vs[j]) < val) {
					val ^= vs[j];
				}
			}
			if (val != 0) return 1;
            vs.push_back(a[i]);
		}
	}
	return 0;
}
 
signed main() {
	int T;
	cin >> T;
	while (T--) {
		int i, n; cin >> n;
		vector<int> a(n);
		rep(i, n) cin >> a[i];
		string s; cin >> s;
		cout << solve(a, s) << endl;
	}
	return 0;
}

Measured memory_bytes: 3580
import java.util.*;
 
public class Main{
	public static void main(String[] args){
	Scanner scanner = new Scanner(System.in);
      int n = scanner.nextInt();
      
      List<Integer> list = new ArrayList<>();
      
      for (int i = 0; i < n ; i++){
      	int b = scanner.nextInt();
        list.add(b);
      }
      
      int count = 0;
      Boolean results = true;
      
      while(results){
        
          for(int j = 0; j < list.size(); j++ ){
            if(list.get(j) % 2 != 0){
              results = false;
              break;
            }
              list.set(j,list.get(j) / 2);
        }
        if(results){
          count += 1;
        }
      }
     System.out.println(count);
    }
}

Measured memory_bytes: 35688
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>
#include <map>

using namespace std;

int main()
{
    int n, x;
    long long int a[100010];
    long long int ans = 0;

    cin >> n >> x;

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

    for (int i = 1; i < n; i++) {
        if (a[i]+a[i-1]>x) {
            if (a[i] >= (a[i]+a[i-1])-x) {
                ans += (a[i]+a[i-1])-x;
                a[i] -= (a[i]+a[i-1])-x;
            }
            else {
                ans += a[i] + (((a[i]+a[i-1])-x)-a[i]);
                a[i-1] -= ((a[i]+a[i-1])-x)-a[i];
                a[i] = 0;
            }
        }
    }

    cout << ans << endl;
}


Measured memory_bytes: 1024
N = int(input())
A = list(map(int, input().split()))
 
each_bit_sum = [{"0": 0, "1": 0} for _ in range(62)]
result = 0
for a in A:
    for i, b in enumerate(format(a, "b").zfill(62)[::-1]):
        each_bit_sum[i][b] += 1
 
for i, b in enumerate(each_bit_sum):
    result += ((b["0"] * b["1"]) * (2**i)) % ((10**9) + 7)
 
print(result % ((10**9) + 7))

Measured memory_bytes: 122936
x, k, d = list(map(int,input().split()))

a = (k * d - x) / (2 * d)

if abs(x) < k * d:
   if abs(int(a) + 1 - a) >= abs(int(a) - a):
      print(abs(x + 2 * int(a) * d - k * d))
   else:
      print(abs(x + 2 * (int(a) + 1) * d - k * d))

elif x < 0:
   print(abs(x + k * d))
else:
   print(x - k * d)

Measured memory_bytes: 9104
#include <bits/stdc++.h>
#define rep(i, n) REP(i, 0, n)
#define REP(i, l, r) for (int i = l; i < r; ++i)
#define int long long
#ifdef DEBUG
#define dout cout
#else
std::stringstream dout;
#endif
using namespace std;
typedef pair<int, int> P;
struct edge {
  int to, cost;
};
// other libs
int gcd(int a, int b) {
  if (a % b == 0)
    return b;
  else
    return gcd(b, a % b);
}
int lcm(int a, int b) {
  return a * b / gcd(a, b);
}

class dijkstra {
private:
  int V;
  int d[100002];
  priority_queue<P, vector<P>, greater<>> que;

public:
  dijkstra(int v, int s, vector<edge> G[]) {
    V = v;
    update(s, G);
  }

  void update(int s, vector<edge> G[]) {
    fill(d, d + V + 1, 100000000000ll);
    d[s] = 0;
    que.push(make_pair(0, s));
    while (!que.empty()) {
      P p = que.top();
      que.pop();
      int v = p.second;
      if (d[v] < p.first)
        continue;
      rep(i, G[v].size()) {
        edge e = G[v][i];
        if (d[e.to] > d[v] + e.cost) {
          d[e.to] = d[v] + e.cost;
          que.push(make_pair(d[e.to], e.to));
        }
      }
    }
  }

  int find(int e) {
    return d[e];
  }
};
template<typename T>
class Union_Find {
private:
  vector<T> t, s;

public:
  Union_Find(T max_length) {
    rep(i, max_length + 1) {
      t.push_back(i);
      s.push_back(1);
    }
  }

  void Union(T x, T y) {
    if (same(x, y))
      return;
    T tx = Find(x), ty = Find(y);
    if (s[tx] < s[ty]) {
      s[ty] += s[tx];
      t[tx] = ty;
    }
    else if (s[tx] > s[ty]) {
      s[tx] += s[ty];
      t[ty] = tx;
    }
    else if (tx > ty) {
      t[tx] = ty;
      s[ty] += s[tx];
    }
    else {
      t[ty] = tx;
      s[tx] += s[ty];
    }
  }
  T Find(T n) {
    if (t[n] == n)
      return n;
    else
      return t[n] = Find(t[n]);
  }

  bool same(T x, T y) {
    return Find(x) == Find(y);
  }

  T get_Size(size_t a) {
    return s[a];
  }
};
bool ifPrime(int n) {
  if (n == 1)
    return false;
  for (int i = 2; i * i <= n; i++) {
    if (n % i == 0)
      return false;
  }
  return true;
}

set<int> prime_num_factor(int n){
  if(n<2)return set<int>();
  set<int> prime;
  prime.insert(2);
  for(int i=3;i<=n;i++){
    for(int it:prime){
      if(it*it>i){
        prime.insert(i);
        break;
      }
      if(i%it==0)break;
    }
  }
  return prime;
}
vector<int> makeDivisors(int n){
  vector<int> re;
  REP(i,1,sqrt(n)+1){
    if(n%i==0){
      re.push_back(i);
      if(i!=n/i)re.push_back(n/i);
    }
  }
  return re;
}
int modPow(int a,int n,int mod){
  int ret=1;
  while(n){
    if(n&1)ret=ret*a%mod;
    a=a*a%mod;
    n>>=1;
  }
  return ret;
}
signed main(signed argc, char* argv[]) {
  int n;
  cin>>n;
  REP(i,1,10){
    REP(j,1,10){
      if(i*j==n){
        cout<<"Yes"<<endl;
        return 0;
      }
    }
  }
  cout<<"No"<<endl;
}


Measured memory_bytes: 256
import math
N = int(input())
ans = 0

a = 1
while a <= math.sqrt(N):
  if N % a == 0:
    b = N // a
    len = (a + b) - 2

    if (ans == 0) or (ans > len):
      ans = len
  a += 1

print(ans)

#まだ途中エラーが出ているので明日取り組む


Measured memory_bytes: 3060
import sys
input = sys.stdin.readline
from collections import Counter

N = int(input())
A = list(map(int, input().split()))

A.sort()
C = Counter(A)

ans = 0
for i in reversed(range(N)):
    a = A[i]
    inv = 2**(a.bit_length())-a
    if a == inv:
        if C[a] >= 2:
            C[a] -= 2
            ans += 1
    elif inv in C.keys():
        if C[inv] >= 1 and C[a] >= 1:
            C[a] -= 1
            C[inv] -= 1
            ans += 1

print(ans)    


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

using namespace std;



int main()
{
    int n,k;
    cin>>n>>k;
    if(k%2 || (k>n*2 && k>n*4) || n>=k || (k<n*2))
        printf("No");
    else
    {
        printf("Yes");
    }
    return 0;
}

Measured memory_bytes: 3756
N,K = gets.split.map(&:to_i)
P = gets.split.map {|n| n.to_i*(n.to_i+1)/2 / n.to_f }

sum = P[0, K].inject(:+).to_f
max = sum
while P.size > K
  sum = sum + P[K] - P.shift
  max = sum if max < sum
end
puts max

Measured memory_bytes: 14980
import math
import sys
n,k = map(int,input().split())
ans = 0

for i in range(1,n+1):
    if i >= k:
        ans += (1/n)
    else:
        ans += (1/n) * (1/2)**(math.ceil(math.log2(k/i)))
    
print(ans)

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

#define PI 3.1415926535897932384626433832795

double d; int a;
double vcos[6], vsin[6];
double x, y;

void koch_curve(int k)
{
	if (k == 0) {
		x += d*vcos[a % 6], y += d*vsin[a%6];
		printf("%.8lf %.8lf\n", x, y);
	} else {
		d /= 3;
		koch_curve(k-1), a++, koch_curve(k-1);
		a += 4;
		koch_curve(k-1), a++, koch_curve(k-1);
		d *= 3;
	}
}

int main()
{
	int n, i;
	
	for (i = 0; i < 6; i++) vcos[i] = cos(i*PI/3), vsin[i] = sin(i*PI/3);

	scanf("%d", &n);

	d = 100;		// (0,0) - (100,0);

	a = 0, x = 0, y = 0; puts("0.00000000 0.00000000");
	koch_curve(n);
	return 0;
}



Measured memory_bytes: 2148
#include<bits/stdc++.h>
using namespace std;
#define mod 1000000007
#define ll long long
#define Author std::ios_base::sync_with_stdio(0);
#define ABHISHEK_SHARMA cout.tie(0);
#define IIIT_ALLAHABAD cin.tie(0);

int main(){
    //Booster
    Author
        ABHISHEK_SHARMA
        IIIT_ALLAHABAD
    //Driver Code here
    ll n, i, t, k, count=0;
    ll ans=0;
    cin>>t;
    while(t--){
        cin>>n>>k;
        if(n>ans){
            ans=n;
            count=n+k;
        }
    }
    cout<<count;
    return 0;
}

Measured memory_bytes: 256
#if 0

#endif

#include <bits/stdc++.h>
#include <stdio.h>
#define REP(i, n) for(int i=0;i<int(n);++i)
using namespace std;
template<class A>void p(A a){cout << (a) << endl;}
template<class A,class B>void p(A a,B b){cout << a << " "  ;p(b);}
template<class A,class B,class C>void p(A a,B b,C c){cout << a << " " ;p(b,c);}
template<class A,class B,class C,class D>void p(A a,B b,C c,D d){cout << a << " " ;p(b,c,d);}
typedef long long ll;
typedef pair<ll, ll> l_l;
typedef pair<int, int> i_i;
int INF=numeric_limits<int>::max();
// for copy
// for(int i=0;i<N;++i) {

int main(void) {
  int N,K;cin>>N>>K;
  int P[N+10];
  REP(i,N) {
    cin>>P[i];
  }
  double tmp = (accumulate(P,P+K,0.0)+K)/2;
  double max = tmp;
  for(int i=0;i<N-K;++i) {
    tmp = tmp - P[i]/2.0 + P[i+K]/2.0;
    if (max < tmp) max = tmp;
  }
  printf("%.10f",max);
  return 0;
}


Measured memory_bytes: 1024
#include<iostream>
#include<stack>
#include<string>
#include<stdlib.h>
#include<stdio.h>
#include<map>
#include<vector>
#include<cmath>
#include<algorithm>
#include<queue>
using namespace std;

struct work
{
	int tim;
	string name;
};
int main()
{
	queue<work> k;
	int n, q;
	cin >> n >> q;
	for (int i = 0; i < n; i++)
	{
		work t;
		cin >> t.name >> t.tim;
		k.push(t);
	}
	int ans = 0;
	while (!k.empty())
	{
		work t=k.front();
		t.tim -= q;
		if (t.tim <= 0)
		{
			ans += q;
			ans += t.tim;
			cout << t.name << " " << ans << endl;
			k.pop();
		}
		else
		{
			ans += q;
			k.pop();
			k.push(t);
		}
	}

}



/*
stack<int> X[3];
int n, m;
int ans;
int owa;

void aho(int a, int b)
{
	X[b].push(X[a].top());
	X[a].pop();
	return;
}
int k1[4] = { 0, 1, 1, 2 };
int k2[4] = { 1, 0, 2, 1 };
int check(int now,int mae)
{
	
	if (now > owa)return m + 2;
	if (X[1].empty())
	{
		if (X[0].empty() || X[2].empty())
		{
			owa = now + 1;
			//cout << now << endl;
			return now;
		}
	}
	if (now == m )
	{
		return m+2;
	}
	int ans = m+1;
	for (int i = 0; i < 4; i++)
	{
		if (mae == 0 && i == 1)continue;
		if (mae == 1 && i == 0)continue;
		if (mae == 2 && i == 3)continue;
		if (mae == 3 && i == 2)continue;
		if (X[k1[i]].empty())continue;
		if (X[k2[i]].empty());
		else 
		if (X[k1[i]].top() <= X[k2[i]].top())continue;
		aho(k1[i], k2[i]);
		ans=min(check(now + 1,i),ans);
		aho(k2[i], k1[i]);
	}
	return ans;
	

}

int main()
{
	while (1){
		cin >> n >> m;
		if (n == 0)
			if (m == 0)
				break;
		for (int i = 0; i < 3; i++)
			while (!X[i].empty())X[i].pop();
		ans = m + 1;
		owa = m;
		for (int i = 0; i < 3; i++)
		{
			int g;
			cin >> g;
			for (int I = 0; I < g; I++)
			{
				int s; cin >> s;
				X[i].push(s);
			}
		}
		int g = check(0,-1);
		if (g > m)
		{
			g = -1;
		}
		cout << g << endl;
	}
	
}
*/

Measured memory_bytes: 4404
import sys
import numpy as np


read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
nums = np.array(read().split(), np.int32)[2:]
flg = np.all(np.bincount(nums) % 2 == 0)
if flg:
    print('YES')
else:
    print('NO')


Measured memory_bytes: 39264
#include <iostream>
#include <algorithm>
#include <cmath>
#include <string>
#include <array>
#include <vector>
#include <functional>
#include <unordered_map> 
#include <map> 
#include <numeric>
#include <limits>
#include <utility>
#include <queue>
#include <random>
#include <bitset>
using namespace std;
typedef long long LL;
 
int main() {
	int t, i, j, k;
	int a, b, c ,d,F=0;
	char A[100];
	
	cin >> a >> b;
 
	
		c = -a + 2*b;
 
		
		cout << c << endl;
	return 0;
}

Measured memory_bytes: 256
#include<iostream>

using namespace std;

int main(){
  int A,B=-1;

  int n;
  cin >> n;
  while(n--){
    int a,b;
    cin >> a >> b;

    if(B < b || B == b && A > a){
      A = a;
      B = b;
    }
  }
  cout << A << " " << B << endl;

  return 0;
}

Measured memory_bytes: 1164
object Main {
  def main(args: Array[String]): Unit = {
    val brick_num = io.StdIn.readInt
    val factors   = io.StdIn.readLine.split(" ").map{_.toInt}
    var num_of_bricks_destroyed = 0

    var check_num = 1
    factors.foreach{ i =>
      if(check_num == i) {
        check_num += 1
      }
      else {
        num_of_bricks_destroyed += 1
      }
    }
    if(check_num == 1) println(-1)
    else               println(num_of_bricks_destroyed)
  }
}

Measured memory_bytes: 52860