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

int main() {
double N;
cin >> N;
int A = N;
if(A % 2 == 0)
{
  cout << (N / 2) / N << endl;
}
if(A % 2 == 1){
  cout << ((N + 1) / 2) / N << endl;
}
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){
    #define ll long long
    ll a, b, c, d;
    cin >> a >> b >> c >> d;
    ll cl =  b/c  - (a-1)/c;
    ll dl = b/d  - (a-1)/d;
    ll cdc = c*d/(__gcd(c,d));
    ll cdl = (b/cdc  - (a-1)/cdc);
    ll w = cl  + dl - cdl;
    cout << b - a + 1 - w << '\n';
}

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

int main(){
  	ios_base::sync_with_stdio(0);
  	cin.tie(0);
  	cout.tie(0);
  	char a;
  	cin >> a;
  	if('A' <= a && a <= 'Z')
      cout << 'A';
  	else
      cout << 'a';
	return 0;
}


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

int main(){
	int n;
  cin >> n;
  vector<int> val(n), cos(n);
  for(int i = 0;i < n;i++){
  	cin >> val.at(i);
  }
  for(int i = 0;i < n;i++){
  	cin >> cos.at(i);
  }
  int max = 0;
  int l;
  for (int i = 0;i < n;i++){
  	l = val.at(i) - cos.at(i);
    if(l > 0)
      max = l + max;
  }
  cout << max << endl;
}

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

#define ll long long
#define fornum(A,B,C) for(A=B;A<C;++A)
#define pii pair<int,int>
#define pll pair<ll,ll>

using namespace std;

/////////////////////////////////////////////////////
ll N,X,Y;
ll mk[2020][2020];
ll i, j, k;
vector<ll> abv[2020];
ll ans[2020];

int main(){
    scanf("%lld%lld%lld", &N,&X,&Y);
    abv[X].push_back(Y);
    abv[Y].push_back(X);
    fornum(i,1,N){
        abv[i].push_back(i + 1);
        abv[i + 1].push_back(i);
    }
    fornum(i,0,N){
        queue<ll> q;
        mk[i+1][i+1] = 1;
        ++ans[1];
        q.push(i + 1);
        while(q.size()){
            ll qa = q.front();
            q.pop();
            //printf("%lld,%d:\n", qa, abv[qa].size());
            fornum(j, 0, abv[qa].size())
            {
                ll b = abv[qa][j];
                //printf("%lld::", b);
                //printf("%lld,%lld,%lld\n", qa, b,mk[i+1][b]);
                if(mk[i+1][b])
                    continue;
                ++ans[mk[i + 1][b] = mk[i + 1][qa] + 1];
                //printf("%lld,%lld,%lld %lld\n",i+1, b,mk[i + 1][b] ,ans[mk[i + 1][b]]);
                q.push(b);

            }
        }
    }
    fornum(i,1,N){
        printf("%lld\n", ans[i+1]/2);
    }

    return 0;
}

Measured memory_bytes: 32000
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAX_N = 400;
const ll INF = 1000000000000000000LL;

ll dp[MAX_N + 5][MAX_N + 5];
ll num[MAX_N + 5], acc[MAX_N + 5];

ll DP(int l,int r) {
	if (l == r) return 0;
	if (dp[l][r] != 0) return dp[l][r];
	ll &ret = dp[l][r];
	ret = INF;
	ll sum = acc[r] - acc[l - 1];
	for (int i = l; i < r; i++) {
		ll temp = DP(l, i) + DP(i + 1, r);
		ret = min(ret, temp);
	}
	ret += sum;
	return ret;
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	ll n;
	cin >> n;
	for(int i = 1; i <= n; i++) cin >> num[i];
	for (int i = 1; i <= n; i++) acc[i] = acc[i - 1] + num[i];
	ll answer = DP(1, n);
	cout << answer << endl;
	return 0;
}

Measured memory_bytes: 1536
#include <algorithm>
#include <climits>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <iostream>
#include <sstream>
#include <functional>
#include <map>
#include <string>
#include <cstring>
#include <vector>
#include <queue>
#include <stack>
#include <deque>
#include <set>
#include <list>
#include <numeric>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll,ll> P;
const double PI = 3.14159265358979323846;
const double EPS = 1e-12;
const ll INF = 1LL<<29;
const ll mod = 1e9+7;
#define rep(i,n) for(int (i)=0;(i)<(ll)(n);++(i))
#define repd(i,n,d) for(ll (i)=0;(i)<(ll)(n);(i)+=(d))
#define all(v) (v).begin(), (v).end()
#define pb(x) push_back(x)
#define mp(x,y) make_pair((x),(y))
#define mset(m,v) memset((m),(v),sizeof(m))
#define chmin(X,Y) ((X)>(Y)?X=(Y),true:false)
#define chmax(X,Y) ((X)<(Y)?X=(Y),true:false)
#define fst first
#define snd second
#define UNIQUE(x) (x).erase(unique(all(x)),(x).end())
template<class T> ostream &operator<<(ostream &os, const vector<T> &v){int n=v.size();rep(i,n)os<<v[i]<<(i==n-1?"":" ");return os;}
#define N 100010
int n, k, a[N], d[N];
vector<int> g[N];
void dfs(int u, int x){
	d[u] = x;
	for(auto &&v: g[u]) dfs(v, x+1);
}
int main(){
	scanf("%d %d", &n, &k);
	rep(i, n) scanf("%d", a+i);
	rep(i, n) a[i]--;
	int res = 0;
	if(a[0]!=0){
		a[0] = 0;
		res++;
	}
	rep(i, n-1) g[a[i+1]].push_back(i+1);
	dfs(0, 0);
	priority_queue<P> q;
	rep(i, n) if(d[i]>k) q.push(P(d[i], i));
	while(!q.empty()){
		int u = q.top().snd; q.pop();
		int u2 = u;
		bool f = false;
		rep(_, k){
			if(d[u]==0){
				f = true;
				break;
			}
			u = a[u];
		}
		if(f) continue;
		res++;
		u = u2;
		rep(_, k){
			d[u] = 0;
			u = a[u];
		}
	}
	printf("%d\n", res);
	return 0;
}


Measured memory_bytes: 11764
#include <iostream>
using namespace std;
    long long rec(long long x, long long y){
    if(y == 1) return x;
    else if(y%2 == 1) {return rec(x*x%1000000007, y/2)*x%1000000007;}
    else {return rec(x*x%1000000007, y/2);}
    }

int main(void){
   long long m,n;
   cin >> m >> n;
   cout << rec(m, n)<<endl;
   return 0;
}



Measured memory_bytes: 3080
#include <bits/stdc++.h>
using namespace std;
int main()
{
	int a[6],f=0,maxv=0,s=0;
	for(int i=1;i<=5;i++)
	{
		cin>>a[i];
		if(10-a[i]%10>maxv&&a[i]%10!=0)
		{
			f=i;
			maxv=10-a[i]%10;
		}
	}
	for(int i=1;i<=5;i++)
	{
		if(i!=f&&a[i]%10!=0)
		{
			a[i]=(a[i]/10+1)*10;
		}
		s+=a[i];
	}
	cout<<s;
	return 0;
}

Measured memory_bytes: 256
from collections import defaultdict
Liner = defaultdict(lambda: [])
def inpl(): return [int(i) for i in input().split()]
import sys
N, M = inpl()
for _ in range(M):
    a, b = inpl()
    Liner[a].append(b)
    Liner[b].append(a)
if not Liner[1]:
    print('IMPOSSIBLE')
    sys.exit()
for i in Liner[1]:
    if N in Liner[i]:
        print('POSSIBLE')
        sys.exit()
print('IMPOSSIBLE')

Measured memory_bytes: 102488
#E
n = int(input())
c = [int(i) for i in input().split()]
mod = 10**9+7

c.sort()
ans = 0
for i in range(n):
    ans += c[i]*(n-i+1)

ans %= mod
ans *= 4**(n-1)
ans %= mod
print(ans)

Measured memory_bytes: 26800
import java.util.Scanner

import scala.collection.Searching._
import scala.annotation.tailrec
import scala.collection.immutable.{NumericRange, Queue}
import scala.collection.mutable
import scala.io.StdIn.readLine

class IUnionFind(val size: Int) {

  private case class Node(var parent: Option[Int], var treeSize: Int)

  private val nodes = Array.fill[Node](size)(new Node(None, 1))

  def union(t1: Int, t2: Int): IUnionFind = {
    if (t1 == t2) return this

    val root1 = root(t1)
    val root2 = root(t2)
    if (root1 == root2) return this

    val node1 = nodes(root1)
    val node2 = nodes(root2)

    if (node1.treeSize < node2.treeSize) {
      node1.parent = Some(t2)
      node2.treeSize += node1.treeSize
    } else {
      node2.parent = Some(t1)
      node1.treeSize += node2.treeSize
    }
    this
  }

  def connected(t1: Int, t2: Int): Boolean = t1 == t2 || root(t1) == root(t2)

  def root(t: Int): Int = nodes(t).parent match {
    case None => t
    case Some(p) => root(p)
  }
}


object Main {
  def solve(sc: => Scanner): Unit = {
    val N = sc.nextLong
    println(math.max(solvex(N, 0), calc(N)))
  }

  def solvex(n: => Long, i: Long): Long = {
    val num: Long = math.pow(10, i).toLong
    if (num > n) (0) else {
      math.max(solvex(n, i + 1), calc(n / num * num - 1))
    }
  }

  def calc(n: Long): Long = (if (n == 0) (0) else (calc(n / 10) + n % 10))

  def gcd(i: Long, j: Long): Long = {
    if (i < j) (gcd(j, i)) else (if (j == 0) (i) else (gcd(j, i % j)))
  }

  def main(args: Array[String]): Unit = {
    val sc: Scanner = new Scanner(System.in)
    solve(sc)
  }
}

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

int main() {
  int N,T;
  cin >> N >> T;
  
  vector<vector<int>> routes(N, vector<int>(2, 0));
  
  for (int i = 0; i < N; i++) cin >> routes.at(i).at(0) >> routes.at(i).at(1);
  
  int answer = 1001;
  bool isTLE = true;
  
  for (int i = 0; i < N; i++) {
    if (routes.at(i).at(1) <= T && routes.at(i).at(0) < answer) {
      answer = routes.at(i).at(0);
      isTLE = false;
    }
  }
     
  if (!isTLE) {
    cout << answer << endl;
    return 0;
  } else {
    cout << "TLE" << endl;
    return 0;
  }
    
  return -1;
}

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

#define NREP() for(ll i = 0; i < n; i++)
#define MREP() for(ll j = 0; j < m; j++)
#define REP(i, n) for(ll i = 0; i < n; i++)
#define ALL(x) (x).begin(), (x).end()
#define MSG(x) cout << x << endl;
#define IPT(t, x) t ipt; cin >> ipt; x.push_back(ipt);
#define YN(x) x ? cout << "YES" << endl : cout << "NO" << endl;
#define Yn(x) x ? cout << "Yes" << endl : cout << "No" << endl;
#define yn(x) x ? cout << "yes" << endl : cout << "no" << endl;

using namespace std;
typedef long long ll;
typedef vector<ll> vl;
typedef vector<vector<ll>> vvl;
typedef vector<string> vs;
typedef vector<vector<string>> vvs;

const static ll MOD = 1e9 + 7;
ll n, cnt, ans, tmp, sum, a, b, c, d, k, m, h, w, q, x, y;
string s, t;

int main() {
    cin >> a >> b;
    if (a <= b) {
        MSG(a)
    } else {
        MSG(a - 1)
    }
}


Measured memory_bytes: 256
N, M = map(int, input().split())
 
small=min(N,M)
big  =max(N,M)
if small==1:
    if big==1:
        print (1)
    elif big==2:
        print (0)
    else:
        print (big-2)
 
elif small==2:
    print (0)
    
else:
    print ((small-2)*(big-2))

Measured memory_bytes: 3060
#include <iostream>
#include <string>
#include <stdio.h>
#include <cmath>
#include <cfloat>
#include <algorithm>
#include <numeric>
#include <vector>
#include <iterator>
#include <set>
#include <map>
using namespace std;

const double PI=acos(-1);

int main(){
    string s, t;
    cin >> s >> t;
    sort(s.begin(), s.end());
    sort(t.begin(), t.end(), greater<char>());
    if(s < t) cout << "Yes" << endl;
    else cout << "No" << endl;
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define _GLIBCXX_DEBUG
#define rep(i,n) for (int i = 0; i < (int)(n); i++)
#define all(v) v.begin(),v.end()
#define puts(i) cout << i << endl
#define INF INT_MAX;
#define INFL LLONG_MAX;
typedef long long ll;
using namespace std;
int main(){

int A,B,i,sum=1,count=0;

cin >> A >> B;

for(i=0;i==0;i){

  if(sum<B){
    sum=sum-1+A;
    count++;
  }
  else{
    break;
  }
}
cout << count << endl;
}


Measured memory_bytes: 3580
#include <bits/stdc++.h>
//#include <boost/multiprecision/cpp_int.hpp>
using namespace std;
//using namespace boost::multiprecision;
typedef long long int ll;
typedef long double ld;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
const long long INF = 1LL << 60;
bool pairCompare(const pair<double,ll>& firstElof, const pair<double,ll>& secondElof){
    return firstElof.first < secondElof.first;
}
bool pairCompareSecond(const pair<double,ll>& firstElof, const pair<double,ll>& secondElof){
    return firstElof.second < secondElof.second;
}
#define MAX_N 100100
#define MOD 998244353
// 四方向への移動ベクトル
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};
ll gcd(ll a,ll b) {return b ? gcd(b,a%b):a;}
ll lcm(ll c,ll d){return c/gcd(c,d)*d;}
ll dp[30][51000];

int main(){
    ll n,m;
    cin >> n >> m;
    ll c[m];
    for (ll i=0;i<m;i++)cin >> c[i];
    ll dp[n+100];
    fill(dp,dp+n+100,INF);
    dp[0]=0;
    for (ll i=0;i<=n;i++){
        for (ll j=0;j<m;j++){
            if (i-c[j]>=0){
                chmin(dp[i],dp[i-c[j]]+1);
            }
        }
    }
    cout << dp[n] << endl;
    return 0;
}


Measured memory_bytes: 3524
N=int(input())

s,c=[],1
while N>0:
  if N>26**c:
    N-=26**c
    c+=1
  else:
    N-=1
    while c>0:
      s.append(chr(0x61+N%26))
      N//=26
      c-=1

print(''.join(s[::-1]))


Measured memory_bytes: 9172
n=int(input())
if n>10**6 or 1>n:
    pass
else:
    result=0
    for i in range(1,n+1,1):
        if i%3==0 and i%5==0:
            pass
        elif i%3==0:
            pass
        elif i%5==0:
            pass
        else:
            result+=i
        
    print(result)

Measured memory_bytes: 9088
import numpy as np

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

mod = 1000000007

A = np.zeros(N)

ans = 1

for i in range(N):
    hoge = D[i]
    if hoge == 0:
        ans *= int(3-A[hoge])
        A[hoge] += 1
    else:
        ans *= int(A[hoge-1]-A[hoge])
        A[hoge] += 1
    
    if ans > mod:
        ans = ans % mod

print(ans)


Measured memory_bytes: 23356
#include<stdio.h>

int main(void){
 int five=0;
  int hund=0;
  int ten=0;
  int price;
  int count=0;
  int nfive,nhund,nten;
  scanf("%d",&nfive);
  scanf("%d",&nhund);
  scanf("%d",&nten);
  scanf("%d",&price);
  
  for(five=0;five<=nfive;five++){
    for(hund=0;hund<=nhund;hund++){
      for(ten=0;ten<=nten;ten++){
        if(five*500+hund*100+ten*50==price)count++;
      }
    }
  }
  printf("%d",count);
  
}

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

int main(){
    int n;
    int p[5005];
    int temp[5005];
    int min_a=20000,ans;
    cin >> n;
    for(int i=0;i<n;i++){
        cin >> p[i];
    }
    for(int i=0;i<=p[0];i++){
        temp[0] = p[0] - i;
        ans = i;
        for(int j=1;j<n;j++){
            temp[j] = p[j];
        }
        for(int j=0;j<n-1;j++){
            if(temp[j] > 0){
                ans += temp[j] * 2;
                temp[j+1] -= temp[j];
                temp[j] = 0;
            }
        }
        if( temp[n-1] > 0){
            ans += temp[n-1];
        }
        min_a = min(ans,min_a);
    }
    cout << min_a << "\n";
    return 0;
}


Measured memory_bytes: 3168
// finish date: 2019/11/18

#include <bits/stdc++.h>

using namespace std;

#define FOR(i, a, b) for(int (i)=a;(i)<(b);(i)++)
#define rep(i, n)  FOR(i,0,n)
typedef long long ll;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef vector<vector<vector<int>>> vvvi;
typedef vector<ll> vl;
typedef vector<vector<ll>> vvl;
typedef vector<double> vd;
typedef vector<vector<double>> vvd;
typedef vector<vector<vector<double>>> vvvd;
typedef vector<bool> vb;
typedef vector<vector<bool>> vvb;
typedef vector<string> vs;
typedef vector<char> vc;
typedef vector<vector<char>> vvc;
typedef pair<int, int> pii;
typedef pair<ll, int> pli;
typedef pair<ll, pair<int, int>> plii;
const int bigmod = 1000000007;
const int INF = 1000000007;
const long long INFll = 100000000000000000;


int main() {
    int N, T;
    cin >> N >> T;
    vvi AB(N, vi(2));
    vi A(N), B(N);
    rep(i, N) {
        cin >> AB[i][0] >> AB[i][1];
    }
    sort(AB.begin(), AB.end());
    rep(i, N) {
        A[i] = AB[i][0];
        B[i] = AB[i][1];
    }


    int ma = 0;
    vvi DP(N + 1, vi(T));
    rep(i, N) {
        rep(j, T) {
            if ((j == 0) || DP[i][j] != 0) {
                DP[i + 1][j] = max(DP[i + 1][j], DP[i][j]);
                if (j + A[i] < T) {
                    DP[i + 1][j + A[i]] = max(DP[i + 1][j + A[i]], DP[i][j] + B[i]);
                } else {
                    ma = max(ma, DP[i][j] + B[i]);
                }
            }
        }
    }
    rep(i, T) {
        ma = max(ma, DP[N][i]);
    }
    cout << ma << endl;


    return 0;
}


Measured memory_bytes: 35712
#include <iostream>
#include <string>
#include <cstring>
#include <vector>
#include <algorithm>
#include <set>
#include <stack>
#include <deque>
#include <cmath>
#include <map>
using namespace std;
using ll = long long;
#define rep(i, n) for (ll i = 0; i < n; i++)
template<typename T1,typename T2> inline void chmin(T1 &a,T2 b){if(a>b) a=b;}
template<typename T1,typename T2> inline void chmax(T1 &a,T2 b){if(a<b) a=b;}

int main() {
    string s;
    cin >> s;
    cout << s.substr(0, 4) << " " << s.substr(4, 8) << endl;
}

Measured memory_bytes: 256
S = ' ' + input()
T = ' ' + input()

dp = [[i+j for j in range(len(T)+1)] for i in range(len(S)+1)]

for i in range(len(S)):
    for j in range(len(T)):
        c = 0 if S[i] == T[j] else 1
        dp[i+1][j+1] = min(dp[i][j] + c, dp[i][j+1] + 1, dp[i+1][j] + 1)

print(dp[len(S)][len(T)])


Measured memory_bytes: 45204
#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;

int a,b;

bool check(int x)
{
	double v1 = double(x) * 0.08;
	double v2 = double(x) *0.1;
	if(v1 >= a && v1 - a < 1 && v2 >= b && v2 -b <1)
		return true;
	return false;
}

int main()
{
	cin>>a>>b;
	for(int i=1;i<=1250;i++)
	{
		if(check(i))
		{
			cout<<i<<endl;
			return 0;
		}
	}
	cout<<"-1"<<endl;
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <vector>
#define debug(x) cout << #x << "==" << x << endl;
 
const int INF = 1e+8;
 
using namespace std;
 
//??\???
#define MAX_N 100
#define MAX_W 10000
int N, W;
int w[MAX_N], v[MAX_N];
 
// memo
int memo[MAX_N + 1][MAX_W + 1];
bool checked[MAX_N + 1][MAX_W + 1];
 
int opt(int i, int cw) {
 
  if( i == -1 ) { return 0; }
 
  if(checked[i][cw] == true) { return memo[i][cw]; }
  checked[i][cw] = true;
 
  int ret;
  if (  cw < w[i] ) {
    ret = opt(i - 1, cw);
  } else {
    ret = max( opt(i - 1, cw), opt(i, cw - w[i]) + v[i] );
  }
 
  return memo[i][cw] = ret;
 
}
 
int main() {
  ios::sync_with_stdio(false);
 
  cin >> N >> W;
  for(int i = 0; i < N; i++) { cin >> v[i] >> w[i]; }
 
  cout << opt(N - 1, W) << endl;
 
  return 0;
}

Measured memory_bytes: 8484
#include <iostream>
#include <queue>
 
using namespace std;
 
#define MAX_H 30
#define MAX_W 30
#define INF (1<<29)
 
struct State{
    int cost,x,y,dir;
    State(int cost,int x,int y,int dir) :
	cost(cost),x(x),y(y),dir(dir) {}
 
    bool operator < (const State &s)const{
	return cost > s.cost;
    }
};
 
int H,W,c[4];
int s[MAX_H][MAX_W];
int dx[] = {-1,0,1,0};
int dy[] = {0,-1,0,1};
 
bool inField(int x,int y){
    return (0 <= x && x < W && 0 <= y && y < H);
}
 
int dijkstra(){
    int d[MAX_H][MAX_W][4];
    fill(d[0][0],d[0][0]+MAX_H*MAX_W*4,INF);
    d[0][0][2] = 0;
    priority_queue<State> Q;
    Q.push(State(0,0,0,2));
    while(!Q.empty()){
	State cur = Q.top(); Q.pop();
	int x = cur.x,y = cur.y,dir = cur.dir;
	if(d[y][x][dir] < cur.cost) continue;
	if(x == W-1 && y == H-1) return d[y][x][dir];
	for(int i = 0 ; i < 4 ; i++){
	    int ndir = (dir+i)%4;
	    int nx = x + dx[ndir];
	    int ny = y + dy[ndir];
	    if(!inField(nx,ny)) continue;
	    if(s[y][x] == i){
		if(d[y][x][dir] < d[ny][nx][ndir]){
		    d[ny][nx][ndir] = d[y][x][dir];
		    Q.push(State(d[ny][nx][ndir],nx,ny,ndir));
		}
	    }else{
		if(d[y][x][dir] + c[i] < d[ny][nx][ndir]){
		    d[ny][nx][ndir] = d[y][x][dir] + c[i];
		    Q.push(State(d[ny][nx][ndir],nx,ny,ndir));
		}
	    }
	}
    }
    return -1;
}
 
int main(){
    while(true){
	cin >> W >> H;
	if(W == 0 && H == 0) break;
	for(int i = 0 ; i < H ; i++){
	    for(int j = 0 ; j < W ; j++){
		cin >> s[i][j];
	    }
	}
	for(int i = 0 ; i < 4 ; i++){
	    cin >> c[i];
	}
	cout << dijkstra() << endl;
    }
    return 0;
}

Measured memory_bytes: 3244
#include<iostream>
#include<vector>

#define MAX 101
using namespace std;

typedef int Integer;

Integer GCD(Integer a, Integer b){return b==0?a:GCD(b,a%b);}

struct Mobile{
  Mobile *parent,*pr,*pb;
  Integer p,q,gcdpq,dp,dq;
  Mobile(){parent=NULL;pr=NULL;pb=NULL;}
  bool realizable(Integer W){
    if( W<=1 ) return false;
    if( (W*gcdpq)%(p+q) != 0 ) return false;
    Integer k = (W*gcdpq)/(p+q);
    if( k<=0 ) return false;
    bool br=true,bb=true;
    if(dq<dp){
      if(pr){br=pr->realizable(k*dq);}
      if(!br)return false;
      if(pb){bb=pb->realizable(k*dp);}
      if(!bb)return false;
    }else{
      if(pb){bb=pb->realizable(k*dp);}
      if(!bb)return false;
      if(pr){br=pr->realizable(k*dq);}
      if(!br)return false;
    }
    return br&&bb;
  }
};

int main()
{
  while(true){
    int n;
    Integer ans=-1;
    cin >> n;
    if( n == 0 )break;
    Mobile *ms[MAX];
    for(int i = 0; i < n; ++i){
      ms[i+1] = new Mobile();
    }
    for(int i = 0; i < n; ++i){
      Integer p,q,r,b;
      cin >> p >> q >> r >> b;
      ms[i+1]->p = p;
      ms[i+1]->q = q;
      ms[i+1]->gcdpq = GCD(p,q);
      ms[i+1]->dp = p/ms[i+1]->gcdpq;
      ms[i+1]->dq = q/ms[i+1]->gcdpq;
      if(r>0){
	ms[r]->parent=ms[i+1];ms[i+1]->pr=ms[r];
      }else{
	ms[i+1]->pr=NULL;
      }
      if(b>0){
	ms[b]->parent=ms[i+1];ms[i+1]->pb=ms[b];
      }else{
	ms[i+1]->pb=NULL;
      }
    }
    for(int i = 1; i <= n; ++i){
      if( ms[i]->parent == NULL ){
	for(Integer k = 1; ; ++k){
	  Integer P=ms[i]->p;
	  Integer Q=ms[i]->q;
	  Integer gcdPQ=ms[i]->gcdpq;
	  Integer W=(k*(P+Q))/gcdPQ;
	  if( (k*(P+Q))%gcdPQ==0 ){
	    if( ms[i]->realizable( W ) ){
	      ans = W;
	      break;
	    }	    
	  }
	}
	break;
      }
    }

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

Measured memory_bytes: 932
#include <cstdio>

using namespace std;

const int MOD = 1000000007;

int main() {
    int n, m;
    scanf("%d%d", &n, &m);
    long long x[100000], y[100000];

    long long xl = 0, yl = 0;

    for(int i=0;i<n;i++) {
        scanf("%lld", x+i);
        if (i!=0) {
            xl += (x[i] - x[i-1]) * (n-i) * (i);
            xl %= MOD;
        }
    }

    for(int i=0;i<m;i++) {
        scanf("%lld", y+i);
        if (i!=0) {
            yl += (y[i] - y[i-1]) * (m-i) * (i);
            yl %= MOD;
        }
    }

    long long res = (xl * yl) % MOD;

    printf("%lld\n", res);

    return 0;
}

Measured memory_bytes: 1664
#include<iostream>
 using namespace std;
int main()
{
    for(int i=1;i<10;++i)
    {
        for(int j=1;j<10;++j)
        {
            cout << i << 'x' << j << '=' << i*j << endl;
        }
    }
	return 0;
}

Measured memory_bytes: 1116
import sys

n, k = [int(i) for i in input().split()]
a = [int(i) for i in input().split()]

l, r = 0, max(a)
while r - l > 1:
  # satisfy l < t < r
  t = (l + r) // 2
  c = sum([(e-1) // t for e in a])
  if k < c:
    l = t
  else:
    r = t
print(r)

Measured memory_bytes: 30932
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
const int MAX=105;
int M[MAX][MAX];
int dis[MAX],n;
bool inq[MAX];
void bfs(int cur){
	queue<int> Q;
	Q.push(cur);
	dis[cur]=0;
	while(!Q.empty()){
		int u=Q.front();
		Q.pop();
		for(int i=1;i<=n;i++){
			if(M[u][i]&&!inq[i]){
				if(dis[i]==-1)dis[i]=dis[u]+1;
				else dis[i]=min(dis[i],dis[u]+1);
				Q.push(i);
				inq[i]=1;
			}
		}
	}
}
int main(){
	int u,k;
	cin>>n;
	memset(M,0,sizeof(M));
	memset(dis,-1,sizeof(dis));
	memset(inq,0,sizeof(inq));
	for(int i=0;i<n;i++){
		cin>>u>>k;
		int v;
		for(int j=0;j<k;j++){
			cin>>v;
			M[u][v]=1;
		}
	}
	bfs(1);	
	for(int i=1;i<=n;i++){
		printf("%d %d\n",i,dis[i]);
	}
	return 0;
}



Measured memory_bytes: 3276
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define llinf (1ll<<62)
#define BG(x) ((x).begin())
#define ED(x) ((x).end())
#define rBG(x) ((x).rbegin())
#define rED(x) ((x).rend())
#define mp(a, b) make_pair((a), (b))

ll t;

ll n, m = 1000000007;
map<pair<ll, ll>, ll> ab[2];
ll zp, pz, zz;
ll ans = 1;

ll fast_p(ll a, ll b) {
	ll now = a, ans = 1;
	for(ll i = 0; i < 64; i++) {
		if((1ll<<i) & b) {
		//	cout << i << ' ' << b << '\n';
			ans *= now;
			ans %= m;
		}
		now = now*now%m;
	}
	return ans;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    
//    cin >> t;
    t = 1;
    
	
	
    for(int _ = 1; _ <= t; _++) {
    //    cout << "Case #" << _ << ": ";
        
		cin >> n;
		for(int i = 0; i < n; i++) {
			ll a, b;
			cin >> a >> b;
			if(a && b) {
				if((a>0 && b>0) || (a<0 && b<0)) {
					ll gcdab = __gcd(abs(a), abs(b));
					ab[0][mp(abs(a)/gcdab, abs(b)/gcdab)]++;
					ab[1][mp(abs(b)/gcdab, abs(a)/gcdab)]+=0;
				}
				else {
					ll gcdab = __gcd(abs(a), abs(b));
					ab[0][mp(abs(b)/gcdab, abs(a)/gcdab)]+=0;
					ab[1][mp(abs(a)/gcdab, abs(b)/gcdab)]++;
				}
			}
			else {
				if(a) {
					pz++;
				}
				else if(b) {
					zp++;
				}
				else {
					zz++;
				}
			}
		}
		ans *= (fast_p(2, pz)+fast_p(2, zp)-1) % m;
		ans %= m;
		while(ab[0].size()) {
			auto now = BG(ab[0])->first;
			auto won = mp(now.second, now.first);
			ans *= (fast_p(2, ab[0][now])+fast_p(2, ab[1][won])-1) % m;
			ans %= m;
			ab[0].erase(now);
			ab[1].erase(won);
			
		}
		cout << ((ans - 1 + zz) % m + m) % m  << '\n';
    }
    return 0;
}

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




string S;
//-----------------------------------------------------------------------------------
vector<pair<int, int>> F;
void parse() {
	S = S + "#";

	if (S[0] != '-') S = "+" + S;

	int i = 0;
	while (S[i] != '#') {
		pair<int, int> p;

		p.first = 0;
		p.second = 0;

		bool minus = false;
		if (S[i] == '-') minus = true;
		i++;
		while ('0' <= S[i] && S[i] <= '9') {
			p.first = p.first * 10 + S[i] - '0';
			i++;
		}
		if (p.first == 0) p.first = 1;
		if (minus) p.first *= -1;

		if (S[i] == 'x') {
			p.second = 1;
			i++;
			if (S[i] == '^') {
				i++;
				p.second = 0;
				while ('0' <= S[i] && S[i] <= '9') {
					p.second = p.second * 10 + S[i] - '0';
					i++;
				}
			}
		}

		F.push_back(p);
	}
}
//-----------------------------------------------------------------------------------
typedef long long ll;
bool chk(int x) {
	ll sm = 0;
	for (auto p : F) {
		ll xx = 1;
		rep(i, 0, p.second) xx *= x;
		sm += xx * p.first;
	}

	return sm == 0;
}
//-----------------------------------------------------------------------------------
int main() {
	cin >> S;
	
	parse();
	//for (auto p : F) printf("%d %d\n", p.first, p.second);

	set<int> ans;
	rep(i, -2000, 2001) if (chk(i)) ans.insert(-i);
	for (int i : ans) {
		printf("(x");
		if (0 < i) printf("+");
		printf("%d)", i);
	}
	printf("\n");
}

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

typedef long long ll;
using namespace std;

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

int main() {
    int x;
    cin >> x;
    while (!isPrime(x)) x++;
    cout << x;
    return 0;
}


Measured memory_bytes: 256
/*
Contest: -
Problem: Atcoder Grand Contest 024 E
Author: tzc_wk
Time: 2020.7.22
*/
#include <bits/stdc++.h>
using namespace std;
#define fi			first
#define se			second
#define fz(i,a,b)	for(int i=a;i<=b;i++)
#define fd(i,a,b)	for(int i=a;i>=b;i--)
#define foreach(it,v) for(__typeof(v.begin()) it=v.begin();it!=v.end();it++)
#define all(a)		a.begin(),a.end()
#define fill0(a)	memset(a,0,sizeof(a))
#define fill1(a)	memset(a,-1,sizeof(a))
#define fillbig(a)	memset(a,0x3f,sizeof(a))
#define fillsmall(a) memset(a,0xcf,sizeof(a))
#define y1			y1010101010101
#define y0			y0101010101010
#define int long long
typedef pair<int,int> pii;
inline int read(){
	int x=0,neg=1;char c=getchar();
	while(!isdigit(c)){
		if(c=='-')	neg=-1;
		c=getchar();
	}
	while(isdigit(c))	x=x*10+c-'0',c=getchar();
	return x*neg;
}
int n=read(),k=read(),m=read();
int C[305][305],s[305][305],dp[305][305];
signed main(){
	fz(i,0,300){
		C[i][0]=1;
		fz(j,1,i)	C[i][j]=(C[i-1][j]+C[i-1][j-1])%m;
	}
//	printf("%d\n",C[5][3]);
	fz(i,0,k)	dp[1][i]=1;
	fd(i,k,0)	s[1][i]=(s[1][i+1]+dp[1][i])%m;
	fz(i,2,n+1){
		fz(j,0,k)
			fz(l,1,i-1)
				dp[i][j]=(dp[i][j]+C[i-2][l-1]*dp[i-l][j]%m*s[l][j+1]%m)%m;
		fd(j,k,0)	s[i][j]=(s[i][j+1]+dp[i][j])%m;
	}
	printf("%lld\n",dp[n+1][0]);
	return 0;
}

Measured memory_bytes: 5768
if __name__ == '__main__':
    N, M = list(map(int, input().split()))
    a = []
    b = []
    for i in range(M):
        tmp_a, tmp_b = list(map(int, input().split()))
        a.append(tmp_a)
        b.append(tmp_b)

    c = set([b[i] for i in range(0, M) if a[i] == 1])

    for i in range(0, M):
        if a[i] in c and b[i] == N:
            print("POSSIBLE")
            break
    else:
        print("IMPOSSIBLE")


Measured memory_bytes: 22708
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int m1,d1,m2,d2;
    cin>>m1>>d1>>m2>>d2;
    if(m1 == 2 && d1 == 28)
        printf("1\n");
    else if(m1<=7 ){
        if(m1&1 && d1 == 31)
            printf("1\n");
        else if(!(m1&1) && d1 == 30)
            printf("1\n");
        else
            printf("0\n");
    }
    else if(m1>7){
        if(m1&1 && d1 == 30)
            printf("1\n");
        else if(!(m1&1) && d1 == 31)
            printf("1\n");
        else
            printf("0\n");
    }
    return 0;
}


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

int main(){
	int a,b,ans=1;
	scanf("%d%d",&a,&b);
	for(int i=a;i<=std::min(-1,b);++i) ans^=1;
	if(a<=0&&b>=0) puts("Zero");
	else puts(ans?"Positive":"Negative");
}

Measured memory_bytes: 256
n, k = gets.split.map(&:to_i)
d = []
c = []

k.times do |i|
  ds = gets.split.map(&:to_i)
  d << ds
end

n.times do |i|
  cs = gets.split.map(&:to_i).map{|c| c-1}
  c << cs
end

# color counting
count = [[0] * k, [0] * k, [0] * k]  # count[(i+j)%3][color] = count
n.times do |i|
  n.times do |j|
    count[(i + j) % 3][c[i][j]] += 1
  end
end

ans = 100000000000

k.times do |k1|
  k.times do |k2|
    next if k1 == k2
    k.times do |k3|
      next if k1 == k3
      next if k2 == k3
      ks = [k1, k2, k3]

      sumcost = 0
      3.times do |mod|
        k.times do |col|
          next if col == ks[mod]
          sumcost += count[mod][col] * d[col][ks[mod]]
        end
      end

      ans = [ans, sumcost].min

    end
  end
end

p ans

# koreha TLE simasu


Measured memory_bytes: 4476
fn main() {
    let (d, t, s): (usize, usize, usize) = {
        let mut buf = String::new();
        std::io::stdin().read_line(&mut buf).unwrap();
        let mut iter = buf.split_whitespace();
        (
            iter.next().unwrap().parse().unwrap(),
            iter.next().unwrap().parse().unwrap(),
            iter.next().unwrap().parse().unwrap(),
        )
    };

    if (d + s - 1) / s <= t {
        println!("Yes");
    } else {
        println!("No");
    }
}

Measured memory_bytes: 2124
n = input()
res = [n[0]]
for i in range(1,4):
    ans = []
    for x in res:
        ans.append(x+'+'+n[i])
        ans.append(x+'-'+n[i])
    res = ans
for j in res:
    if eval(j) == 7:
        print(j+'=7')
        break

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

using namespace std;

int main(){
    string s;
    int flag1=0,flag2=0;
    cin>>s;
    if (s[0]=='A'){
        for (int i=2; i<=s.size()-2; i++){
            if(s[i]=='C'){
                flag1++;
            }
        }
        if(flag1!=1){
            cout<<"WA\n";
            return 0;
        }
        else{
            for (int j=0; j<s.size(); j++){
                if(isupper(s[j])){
                    flag2++;
                }
            }
            if(flag2!=2){
                cout<<"WA\n";
                return 0;
            }
            else {
                cout<<"AC\n";
            }
        }
    }
    else {
        cout<<"WA\n";
    }
    return 0;
}

Measured memory_bytes: 256
import java.io.*;

public class Main {

    public static void main(String[] args) throws IOException  {
        int x;
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        x = Integer.valueOf(br.readLine());
        x = x*x*x;
        System.out.println(x);       
    }    
}

Measured memory_bytes: 24320
#include <bits/stdc++.h>
#define REP(i, n) for(int i = 0; i < (n); i++)
#define REPR(i, n) for(int i = (n); i >= 0; i--)
#define FOR(i, m, n) for(int i = (m); i < (n); i++)
#define INF 1e9
#define ALL(v) (v).begin(), (v).end()
#define debug(x) cerr << #x << ": " << x << endl;

using namespace std;
typedef long long ll;

signed main() {
  string s, t;
  cin >> s >> t;
  if(t.substr(0, s.size()) == s) {
    cout << "Yes" << endl;
  } else {
    cout << "No" << endl;
  }
  return 0;
}


Measured memory_bytes: 3632
#[allow(unused_imports)]
use std::cmp::*;
#[allow(unused_imports)]
use std::collections::*;
#[allow(unused_imports)]
use std::iter::*;
#[allow(unused_imports)]
use std::*;

macro_rules! test {
    ($($input:expr => $output:expr),* $(,)*) => {
#[test]
        fn solve_test() {
            $(
                assert_eq!(solve($input), $output);
            )*
        }
    };
}
macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
    ($($r:tt)*) => {
        let mut s = {
            use std::io::Read;
            let mut s = String::new();
            std::io::stdin().read_to_string(&mut s).unwrap();
            s
        };
        let mut iter = s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
}

macro_rules! input_inner {
    ($iter:expr) => {};
    ($iter:expr, ) => {};

    ($iter:expr, $var:ident : $t:tt $($r:tt)*) => {
        let mut $var = read_value!($iter, $t);
        input_inner!{$iter $($r)*}
    };
}

macro_rules! read_value {
    ($iter:expr, ( $($t:tt),* )) => {
        ( $(read_value!($iter, $t)),* )
    };

    ($iter:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($iter, $t)).collect::<Vec<_>>()
    };

    ($iter:expr, chars) => {
        read_value!($iter, String).chars().collect::<Vec<char>>()
    };

    ($iter:expr, usize1) => {
        read_value!($iter, usize) - 1
    };

    ($iter:expr, $t:ty) => {
        $iter.next().unwrap().parse::<$t>().expect("Parse error")
    };
}

macro_rules! stdin {
    () => {{
        use std::io::Read;
        let mut s = String::new();
        std::io::stdin().read_to_string(&mut s).unwrap();
        s
    }};
}

fn main() {
    println!("{}", solve(&stdin!()));
}
fn solve(src: &str) -> String {
    input! {
        source = src,
        a:usize,
        b:usize,
        c:usize,
        k:usize,
    }
    let mut ga = b > a;
    let mut bg = c > b;
    if !(ga && bg) {
        for _ in 0..k {
            if !ga {
                b *= 2;
                ga = b > a;
                bg = c > b;
            } else if !bg {
                c *= 2;
                ga = b > a;
                bg = c > b;
            }
            if ga && bg {
                break;
            }
        }
    }
    if ga && bg { "Yes" } else { "No" }.to_string()
}
test! {
    include_str!("b1_in.txt") => "Yes",
    include_str!("b2_in.txt") => "No",

}


Measured memory_bytes: 2080
#include <bits/stdc++.h>
using namespace std;
using lint = long long;
const lint mod = 1e9 + 7;
#define all(x) (x).begin(), (x).end()
#define bitcount(n) __builtin_popcountl((lint)(n))
#define fcout cout << fixed << setprecision(15)
#define highest(x) (63 - __builtin_clzl(x))
template<class T> inline void YES(T condition){ if(condition) cout << "YES" << endl; else cout << "NO" << endl; }
template<class T> inline void Yes(T condition){ if(condition) cout << "Yes" << endl; else cout << "No" << endl; }
template<class T = string, class U = char>int character_count(T text, U character){ int ans = 0; for(U i: text){ ans += (i == character); } return ans; }
lint power(lint base, lint exponent, lint module){ if(exponent % 2){ return power(base, exponent - 1, module) * base % module; }else if(exponent){ lint root_ans = power(base, exponent / 2, module); return root_ans * root_ans % module; }else{ return 1; }}
struct position{ int y, x; }; position mv[4] = {{0, -1}, {1, 0}, {0, 1}, {-1, 0}}; // double euclidean(position first, position second){ return sqrt((second.x - first.x) * (second.x - first.x) + (second.y - first.y) * (second.y - first.y)); }
template<class T, class U> string to_string(pair<T, U> x){ return to_string(x.first) + "," + to_string(x.second); } string to_string(string x){ return x; }
template<class itr> void array_output(itr start, itr goal){ string ans; for(auto i = start; i != goal; i++) ans += to_string(*i) + " "; if(!ans.empty()) ans.pop_back(); cout << ans << endl; }
template<class itr> void cins(itr first, itr last){ for(auto i = first; i != last; i++){ cin >> (*i); } }
template<class T> T gcd(T a, T b){ if(a && b){ return gcd(min(a, b), max(a, b) % min(a, b)); }else{ return a; }} template<class T> T lcm(T a, T b){ return a / gcd(a, b) * b; }
struct combination{ vector<lint> fact, inv; combination(int sz) : fact(sz + 1), inv(sz + 1){ fact[0] = 1; for(int i = 1; i <= sz; i++){ fact[i] = fact[i - 1] * i % mod; } inv[sz] = power(fact[sz], mod - 2, mod); for(int i = sz - 1; i >= 0; i--){ inv[i] = inv[i + 1] * (i + 1) % mod; } } lint C(int p, int q) const{ if(q < 0 || p < q) return 0; return (fact[p] * inv[q] % mod * inv[p - q] % mod); } };
template<class itr> bool next_sequence(itr first, itr last, int max_bound){ itr now = last; while(now != first){ now--; (*now)++; if((*now) == max_bound){ (*now) = 0; }else{ return true; } } return false; }

int main(){
    int N, K;
    cin >> N >> K;
    if(K == 1){
        cout << 0 << endl;
    }else{
        cout << N - K << endl;
    }
}


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


int main(void) {
    using namespace std;

    long n;
    cin >> n;
    string s;
    cin >> s;

    bitset<1000> st;

    long r = 0;

    for(int i=0; i<1000; i++) {
        long a = i/100;
        long b = (i/10) % 10;
        long c = i % 10;

        int k = 0;
        while(k < n && s[k++]-'0' != a);
        while(k < n && s[k++]-'0' != b);
        while(k < n && s[k]-'0' != c) k++;
        r += k < n;
    }

    cout << r << endl;


}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
    ll n,cnt=0;
    cin>>n;
    unordered_map<string,long long> mp;
    string s;
    for(int i=0; i<n; i++){
        cin>>s;
        sort(s.begin(),s.end());
        mp[s]++;
    }
     for(auto itr = mp.begin(); itr!=mp.end(); ++itr){
        cnt+=itr->second*(itr->second - 1)/2;
    }
    cout<<cnt<<endl;
    return 0;
}

Measured memory_bytes: 10660
#include <iostream>
#include <vector>
#include <cstdlib>
#include <algorithm>

using namespace std;

int main(void)
{
	long long N,K,Q;
	
	cin >> N >> K >> Q;

	vector<long long> A(Q);
	vector<long long> player(N);

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

	if (K > Q)
	{
		for (int i = 0; i < N; i++)
		{
			player[i] = 1;
		}
	}
	else
	{
		for (int i = 0; i < N; i++)
		{
			player[i] = K - Q;
		}

		for (int i = 0; i < Q; i++)
		{
			A[i]--;
		}

		for (int i = 0; i < Q; i++)
		{
			player[A[i]]++;
		}
	}

	for (int i = 0; i < N; i++)
	{
		if (player[i] > 0)
			cout << "Yes" << endl;
		else
			cout << "No" << endl;
	}
	return 0;
}

Measured memory_bytes: 2176
#include<bits/stdc++.h>
using namespace std;
#define lli long long int
#define pb push_back
#define MOD 1000000007
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int a=0,b=0,c=0;
    cin>>a>>b>>c;
    if((c%(__gcd(a,b)))==0)
        cout<<"YES";
    else
        cout<<"NO";
    cout<<endl;
}


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

class UnionFind
{
	vector<int> par, rank;

public:
	UnionFind(int n) {
		par = rank = vector<int>(n);
		for (int i = 0; i < n; i++) {
			par[i] = i;
			rank[i] = 0;
		}
	}

	int find(int x) {
		if (x == par[x]) {
			return x;
		}
		else {
			return par[x] = find(par[x]);
		}
	}

	void unite(int x, int y) {
		x = find(x);
		y = find(y);
		if (x == y) {
			return;
		}
		if (rank[x] < rank[y]) {
			par[x] = y;
		}
		else {
			par[y] = x;
			if (rank[x] == rank[y]) {
				rank[x]++;
			}
		}
	}

	bool same(int x, int y) {
		return find(x) == find(y);
	}
};

int main()
{
    int n, m;
    cin >> n >> m;
    UnionFind uf(n);
    int a[100001], b[100001];
    vector<int> v[100001];
    for(int i = 0; i < m; i++){
        cin >> a[i] >> b[i];
        a[i]--;
        b[i]--;
        v[b[i]].push_back(a[i]);
    }
    int ans = n - 1;
    for(int i = 1; i < n; i++){
        bool f = true;
        while(v[i].size()){
            if(uf.same(v[i].back(), i - 1)){
                f = false;
            }
            v[i].pop_back();
        }
        if(f){
            uf.unite(i - 1, i);
            ans--;
        }
    }
    cout << ans << endl;
}

Measured memory_bytes: 6400
// Digits in Multiplication
#include <iostream>
#include <math.h>
using namespace std;

long long n,x;
int ans;

int main(){
    cin>>n;
    for(int i=sqrtl(n);i>=1;i--){
        if(n%i==0){
            x=n/i;
            break;
        }
    }
    for(;x;ans++){
        x/=10;
    }
    cout<<ans;
    return 0;
}

Measured memory_bytes: 256
#include <algorithm>
#include <climits>
#include <complex>
#include <cstring>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <vector>

// using
using namespace std;

// typedef
typedef long long ll;

// define
#define FOR(i, a, b, c) for (int i = (int)(a); i < (int)(b); i += (int)(c))
#define REP(i, n) FOR(i, 0, n, 1)
#define RFOR(i, a, b, c) for (int i = (int)(a); i >= (int)(b); i -= (int)(c))
#define RREP(i, n) RFOR(i, n, 0, 1)
#define ALL(c) (c).begin(), (c).end()
#define SORT(c) sort(ALL(c))
#define REVERSE(c) reverse(ALL(c))
#define UNIQ(c) unique(ALL(c))
#define LB(c, x) lower_bound(c.begin(), c.end(), x)
#define UB(c, x) upper_bound(c.begin(), c.end(), x)
#define LI(c, x) distance(c.begin(), LB(c, x))
#define UI(c, x) distance(c.begin(), UB(c, x))

// functions
template <class T> T ceil(T a, T b) {
    return (a + b - 1) / b;
}
template <class T> T round(T a, T b) {
    return (a + b / 2) / b;
}
template <class T> T gcd(T a, T b) {
    return b ? gcd(b, a % b) : a;
}
template <class T> T lcm(T a, T b) {
    return a / gcd(a, b) * b;
}
template <class T> bool amax(T& a, const T& b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}
template <class T> bool amin(T& a, const T& b) {
    if (b < a) {
        a = b;
        return true;
    }
    return false;
}
ll modpow(ll a, ll b, ll m) {
    if (b == 0) {
        return 1;
    } else if (b % 2 == 0) {
        ll h = modpow(a, b / 2, m);
        return h * h % m;
    } else {
        return a * modpow(a, b - 1, m) % m;
    }
}
ll comb(ll a, ll b, ll m) {
    if (b > a - b) {
        return comb(a, a - b, m);
    }
    ll c = 1, d = 1;
    REP(i, b) {
        c *= (a - i);
        d *= (b - i);
        c %= m;
        d %= m;
    }
    return c * modpow(d, m - 2, m) % m;
}

// main
int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    string S;
    cin >> S;
    int N = S.size();
    map<int, int> m;
    int cnt = 0;
    int j = 0;
    REP(i, N - 1) {
        cnt++;
        if (S[i] == 'R' && S[i + 1] == 'L') {
            m[i] = cnt;
            j = i;
            cnt = 0;
        } else if (S[i] == 'L' && S[i + 1] == 'R') {
            m[j + 1] = cnt;
            cnt = 0;
        }
    }
    m[j + 1] = cnt + 1;
    REP(i, N) {
        if (i < N - 1 && S[i] == 'R' && S[i + 1] == 'L') {
            int r = ceil(m[i], 2) + m[i + 1] / 2;
            int l = m[i] / 2 + ceil(m[i + 1], 2);
            i++;
            printf("%d %d ", r, l);
        } else {
            printf("0 ");
        }
    }
    printf("\n");
    return 0;
}


Measured memory_bytes: 5200
N,M = map(int,input().split())
ab = [list(map(int,input().split())) for _ in range(M)]

dic = {}
for (a, b) in ab:
  if a in dic.keys():
    dic[a].append(b)
  else:
    dic[a] = [b]
  
check = False
for i in dic[1]:
  if i in dic.keys():
    for j in dic[i]:
      if j == N:
        check = True

print("POSSIBLE" if check else "IMPOSSIBLE")  

Measured memory_bytes: 61132
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		String s = scan.next();
		for(int i = 0; i < s.length(); i = i + 2) {
			System.out.print(s.charAt(i) + "");
		}
	}
}

Measured memory_bytes: 33032
#define mod 1000000007
#define INF 1000000000
#include <bits/stdc++.h>
using namespace std;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	char a;
	cin >> a;
	if (a >= 'A' && a <= 'Z') {
		cout << "A" << '\n';
	} else {
		cout << "a" << '\n';
	}
	
	return 0;
}


Measured memory_bytes: 3600
#include <bits/stdc++.h>
typedef long long ll;
#define pb push_back
#define mii map <int, int>
#define mll map <ll, ll>
#define pii pair <int, int>
#define pll pair <ll, ll>
#define vi vector <int>
#define vd vector <double>
#define vll vector <ll>
#define fi first
#define se second
#define si set <int>
#define sll set <ll>
#define spii set <pii>
#define vs vector <string>
#define vpii vector <pair <int,int> >
#define vpll vector <pair <long long,long long> >
#define vvi vector <vector <int> >
#define vvpii vector <vector <pii > >
#define forn(i, n) for (int i = 0; i < (n); i++)
#define rep(i, n) for (int i = 0; i < (n); i++)
#define for1(i, n) for (int i = 1; i < (n); i++)
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(),(x).rend()


using namespace std;
const ll INFLL = 1e18;
const int MAXN = 1e6+100;
const ll INF = 1e9;
const ll mod1=1e9+7;
const ll mod2=2e9+11;
int dp[MAXN][2];
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    #ifdef LOCAL
    freopen("a.in","r",stdin);
    #endif
    string s;
    cin>>s;
    reverse(all(s));
    int n=s.size();
    dp[0][0]=s[0]-'0';
    dp[0][1]=11-(s[0]-'0');
    for (int i=1;i<n;i++)
    {
        dp[i][0]=min(dp[i-1][0],dp[i-1][1])+s[i]-'0';
        dp[i][1]=min(dp[i-1][0]+11-(s[i]-'0'),dp[i-1][1]-1+11-(s[i]-'0'+1));
    }
    cout<<min(dp[n-1][0],dp[n-1][1]);



}

Measured memory_bytes: 9116
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> V;
#define rep(a,j,n) for(ll i=a;i<j;i=i+n )
typedef pair<ll,ll> P;
const ll mod = 1000000007;
const ll INF = 1000000009;
ll i;
ll ruijou(ll x, ll y){
    if(y==0) return x;
    if(y%2==0) return ruijou(x*x,y/2);
    else return x*ruijou(x,y-1);
}


int main(){
    ll N,K;
    cin>>N>>K;
    double ans=0;
    for(ll j=1;j<N+1;j++){
        ll o=1;
        while(j*o<K){
            o*=2;
        }
        ans+=1.0/(1.0*N)*1.0/(1.0*o);
    }
    cout<<setprecision(15)<<fixed<<ans<<endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define N 5006
using namespace std;
int n,ans,k,a[N],sum[N],f[N][N],g[N][N];
int main()
{
	scanf("%d%d",&n,&k);
	f[0][0]=1;
	for(int i=1;i<=n;i++){
		scanf("%d",a+i);
		for(int j=0;j<=k;j++)f[i][j]=f[i-1][j];
		for(int j=a[i];j<=k;j++)f[i][j]|=f[i-1][j-a[i]];
	}
	g[n+1][0]=1;
	for(int i=n;i>=1;i--){
		for(int j=0;j<=k;j++)g[i][j]=g[i+1][j];
		for(int j=a[i];j<=k;j++)g[i][j]|=g[i+1][j-a[i]];
	}
	for(int i=1;i<=n;i++){
		if(a[i]>=k){ans++;continue;}
		sum[0]=1;
		for(int j=1;j<=k;j++)sum[j]=sum[j-1]+g[i+1][j];
		for(int j=0;j<k;j++)
			if(f[i-1][j]&&sum[k-j-1]-(k-j-a[i]-1<0?0:sum[k-j-a[i]-1])>0){
				ans++;break;
			}
	} 
	printf("%d\n",n-ans);
}

Measured memory_bytes: 195968
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define INF 1e9
#define PI 3.14159265359
#define MOD 1000000007
#define ALL(v) v.begin(),v.end()
#define ALLR(v) v.rbegin(),v.rend()
typedef long long ll;
const int dx[4] = {1,0,-1,0};
const int dy[4] = {0,1,0,-1};
//isPrime
//modpow modinv
//getDigit
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() {
  cout << fixed << setprecision(10);
  int n,m;
  cin >> n >> m;
  vector<vector<int>> g(n);
  rep(i,m){
    int a,b;
    cin >> a >> b;
    a--; b--;
    g[a].push_back(b);
    g[b].push_back(a);
  }
  queue<int> que;
  vector<int> ans(n,-1);
  que.push(0);
  while(!que.empty()){
    int v = que.front(); que.pop();
    for(auto nv:g[v]){
      if(ans[nv]==-1){
        ans[nv]=v;
        que.push(nv);
      }else{

      }
    }
  }
  cout << "Yes" << endl;
  rep(i,n-1){
    cout << ans[i+1]+1 << endl;
  }
}


Measured memory_bytes: 10116
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<iostream>
#include<algorithm>
using namespace std;
char a[2][3];
int main(void)
{
     int i,j,k,n,m;
     scanf("%d",&n);
     for(i=1;i<=100000;i++)
     {
          if(i*i<=n&&(i+1)*(i+1)>n)
          {
               printf("%d\n",i*i);
               break;
          }
     }
     return 0;
}


Measured memory_bytes: 384