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

struct seg{
    int l,r;
};
int n;
vector < seg > s;

bool cmp_r(seg a,seg b){return a.r<b.r;}
int solve(){
    sort(s.begin(),s.end(),cmp_r);
    int mr=0,ans=0;
    for(int i=0;i<n;++i){
        if(s[i].l>mr){
            mr=s[i].r;
            ans+=1;
        }else{
            ;
        }
    }
    return ans;
}

void _solve(){
    cout<<solve()<<endl;
}

void _prepare(){
    int number;
    cin>>number>>n;
    s.resize(n);
    for(int i=0;i<n;++i)cin>>s[i].l>>s[i].r,s[i].r-=1;
}

int _main_prog(){
    ios::sync_with_stdio(0);
    _prepare();
    _solve();
    return 0;
}

int main(){
    #define uSe_FiLE9
    #ifdef uSe_FiLE
    freopen("task.in","r",stdin);
    freoepn("task.out","w",stdout);
    int r=_main_prog();
    fclose(stdin);fclose(stdout);
    return r;
    #else
    return _main_prog();
    #endif
}



Measured memory_bytes: 1024
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<string>
#include<map>
#include<queue>
#include<set>
#include<vector>
#include<algorithm>
#include<stack>
using namespace std ;
const int dx[]={1,-1,0,0},dy[]={0,0,1,-1};
int n,m;
char sz[55][55];
int main()
{
    cin>>n>>m;
    for(int i=0;i<n;i++)
    {
        string str;
        cin>>str;
        for(int j=0;j<m;j++)
        {
            sz[i][j]=str[j];
        }
    }
    bool flag=1;
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<m;j++)
        {

            if(sz[i][j]=='#')
            {
                bool sign=0;
                for(int k=0;k<4;k++)
                {
                    if(i+dx[k]>=0&&i+dx[k]<n&&j+dy[k]>=0&&j+dy[k]<m)
                    {

                        if(sz[i+dx[k]][j+dy[k]]=='#')
                        {
                            sign=1;
                        }

                    }
                }
                if(!sign) flag=0;
            }

        }
    }
    printf("%s",flag?"Yes":"No");
    return 0;
}


Measured memory_bytes: 256
H,W,K = map(int,input().split())
c = [input() for _ in range(H)]
ans = 0
for i in range(1<<H):
    for j in range(1<<W):
        cnt = 0
        for k in range(H):
            if i >> k & 1: continue
            for l in range(W):
                if j >> l & 1: continue
                if c[k][l] == "#": cnt += 1
        if cnt == K: ans += 1
print(ans)


Measured memory_bytes: 9112
l , r = gets.split.map(&:to_i)
ans = 2018
l.upto(r-1).each do |i|
  (i+1).upto(r).each do |j|
    mod = i*j%2019
    if mod == 0
      puts 0
      exit
    end
    ans = mod if mod < ans
  end
end

puts ans

Measured memory_bytes: 1788
#include <iostream>
#include <string.h>
#include <algorithm>
#include <vector>
#include <queue>

using namespace std;
typedef long long ll;
const ll INF=100000000000000LL;

int main() {
	int a,b,c;
	cin>>a>>b>>c;
	cout<<a+b+c-max(a,max(b,c))<<endl;
	return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <map>
#include <queue>
#include <cstdio>
#include <string.h>
#define rep(i,n) for (int i = 0; i < (int)n; i++)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pi;
typedef pair<pi, pi> pp;
typedef pair<ll, ll> pl;
double PI = 3.1415926535897932;
const double EPS = 1e-9;
const ll MOD = 1000000007;
const int inf = 1 << 30;
const ll linf = 1LL << 60;

int n;
ll dp[19][19];
string s;
ll ans;

int main() {
    cin >> n >> s;
    rep(i,(1<<n)) {
        string s1, s2;
        rep(j,n) {
            if (i&(1<<j)) s1.push_back(s[j]);
            else s2.push_back(s[j]);
        }
        reverse(s1.begin(), s1.end());
        reverse(s2.begin(), s2.end());
        memset(dp, 0, sizeof(dp));
        dp[0][0] = 1;
        for (int j = 0; j <= n-s1.size(); j++) {
            for (int k = 0; k <= n-s2.size(); k++) {
                if (j < s2.size() && s2[j] == s[n+j+k]) dp[j+1][k] += dp[j][k];
                if (k < s1.size() && s1[k] == s[n+j+k]) dp[j][k+1] += dp[j][k];
            }
        }
        ans += dp[s2.size()][s1.size()];
    }
    cout << ans << endl;
}

Measured memory_bytes: 256
fn get_line() -> String {
    let mut line = String::new();
    std::io::stdin().read_line(&mut line).unwrap();
    line.trim().to_string()
}

fn main() {
    let (n, mut k) = {
        let nm = get_line().split_whitespace()
            .map(|e| e.parse().unwrap())
            .collect::<Vec<usize>>();
        (nm[0], nm[1])
    };

    let dest: Vec<usize> = get_line().split_whitespace()
        .map(|e| e.parse::<usize>().unwrap() - 1)
        .collect();

    let mut seen: Vec<bool> = vec![false; n];
    let mut current = 0;
    let mut count = 0;

    loop {
        seen[current] = true;
        count += 1;
        current = dest[current];

        if seen[current] { break; }
    }
    if k <= count {
        count = 0;
        current = 0;
        loop {
            count += 1;
            current = dest[current];
            if count == k { break; }
        }
        println!("{}", current + 1);
        return;
    }

    // 1からループの始まる地点まで何回か => count
    // 残り
    k -= count;

    // ループ始点からループ始点に戻ってくるまで何回か
    count = 0;
    seen = vec![false; n];
    loop {
        seen[current] = true;
        count += 1;
        current = dest[current];

        if seen[current] { break; }
    }


    let diff = k % count;
    for _ in 0..diff {
        current = dest[current];
    }

    println!("{}", current + 1);
}


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

// #define int long long
#define rep(i, n) for (long long i = (long long)(0); i < (long long)(n); ++i)
#define reps(i, n) for (long long i = (long long)(1); i <= (long long)(n); ++i)
#define rrep(i, n) for (long long i = ((long long)(n)-1); i >= 0; i--)
#define rreps(i, n) for (long long i = ((long long)(n)); i > 0; i--)
#define irep(i, m, n) for (long long i = (long long)(m); i < (long long)(n); ++i)
#define ireps(i, m, n) for (long long i = (long long)(m); i <= (long long)(n); ++i)
#define SORT(v, n) sort(v, v + n);
#define REVERSE(v, n) reverse(v, v+n);
#define vsort(v) sort(v.begin(), v.end());
#define all(v) v.begin(), v.end()
#define mp(n, m) make_pair(n, m);
#define cout(d) cout<<d<<endl;
#define coutd(d) cout<<std::setprecision(10)<<d<<endl;
#define cinline(n) getline(cin,n);
#define replace_all(s, b, a) replace(s.begin(),s.end(), b, a);
#define PI (acos(-1))
#define FILL(v, n, x) fill(v, v + n, x);
#define sz(x) long long(x.size())

using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using vll = vector<ll>;
using vvll = vector<vll>;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using vs = vector<string>;
using vpll = vector<pair<ll, ll>>;
using vtp = vector<tuple<ll,ll,ll>>;
using vb = vector<bool>;

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 ll INF = 1e9;
const ll MOD = 1e9+7;
const ll LINF = 1e18;

ll modpow(ll a, ll n) {
  ll res = 1;
  while (n > 0) {
    if (n & 1) res = res * a % MOD;
    (a *= a) %= MOD;
    n >>= 1;
  }
  return res;
}

const ll maxf = 10000000;
ll fact[maxf+5];

void fact_init(){
  fact[0] = 1;
  for(ll i=1; i<=maxf; i++){
    fact[i] = (fact[i-1] * i) % MOD;
  }
}

ll comb(ll a, ll b){
  if(a<b || a<0 || b<0) return 0;
  if(fact[0] == 0) fact_init();
  return (fact[a] * modpow((fact[a-b]*fact[b])%MOD, MOD-2)) % MOD;
}

signed main()
{
  cin.tie( 0 ); ios::sync_with_stdio( false );
  ll n,k; cin>>n>>k;
  reps(i,k){
    ll ans=comb(k-1,i-1)*comb(n-k+1,i);
    ans%=MOD;
    cout<<ans<<endl;
  }
}

Measured memory_bytes: 78336
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <cmath>
#include <utility>
#include <iomanip>
#include <queue>
#include <functional>
using namespace std;
typedef long long ll;
typedef pair<int,ll> P;
const ll MOD = 1e9+7;

bool comp(P &lhs, P &rhs)
{
	if(lhs.first==rhs.first)
		return lhs.second>rhs.second;
	else
		return lhs.first<rhs.first;
}
P p[100000];
priority_queue<ll> q;
int main()
{
	int n,m;
	ll ans=0;
	cin>>n>>m;
	for(int i=0;i<n;i++)
	{
		int a;ll b;
		cin>>a>>b;
		p[i]=P(a,b);
	}
	sort(p,p+n,comp);
	int ind=0;
	for(int i=0;i<m+1;i++)
	{
		while(ind<n && i>=p[ind].first)
		{
			q.push(p[ind].second);
			ind++;
		}
		if(!q.empty())
		{
			cerr<<q.top()<<endl;
			ans+=q.top();q.pop();
		}
	}
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 2936
#include<bits/stdc++.h>
#define endl '\n';
#define rep(i,n) for(int i=0; i<(n); i++)
using namespace std;
using ll = long long;
using P = pair<int,int>;
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma GCC optimize("Ofast")
constexpr ll INF = 1e18;
constexpr int inf = 1e9;
constexpr double INFD = 1e100;
constexpr ll mod = 1000000007;
constexpr ll mod2 = 998244353;
const double PI = 3.1415926535897932384626433832795028841971;
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};
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; }
// ios::sync_with_stdio(false);
// cin.tie(nullptr);
// ---------------------------------------------------------------------------

int main(){
  int N;
  cin >> N;
  vector<int> c(N);
  rep(i,N){
    cin >> c[i];
  }
  vector<vector<int>> places(200100);
  rep(i,N){
    places[c[i]].push_back(i);
  }
  vector<ll> dp(200100,0);
  dp[0] = 1;
  for(int i=1; i<=N; i++){
    dp[i] += dp[i-1];
    dp[i] %= mod;
    int color = c[i-1];
    int it = lower_bound(places[color].begin(),places[color].end(),i-1) - places[color].begin();
    if(it>0){
      int j = places[color][it-1];
      if((i-1)-j > 1){
        dp[i] += dp[j+1];
        dp[i] %= mod;
      }
    }
  }
  cout << dp[N] << endl;
  return 0;
}

Measured memory_bytes: 13568
from collections import deque
n, m = map(int, input().split())
route = [[] for i in range(n)]

for i in range(m):
    a, b = map(int, input().split())
    route[a-1].append(b - 1)
    route[b-1].append(a - 1)

next_queue = deque()
sign = [-1 for i in range(n)]
sign[0] = 999

next_queue.append(0)

while next_queue:
    current_number = next_queue.popleft()
    for room in route[current_number]:
        if sign[room] == -1:
            sign[room] = current_number
            next_queue.append(room)
print("Yes")
for i in range(1, n):
    print(sign[i] + 1)



Measured memory_bytes: 95084
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define mx2 102
#define mx3 1003
#define mx4 10004
#define mx5 100005
#define mx6 1000006
#define mod 1000000007
#define PI 3.14159265
#define deb(x) cout << #x << " " << x << endl;
#define fo(i,n) for(int i=0 ; i<n ; i++)
#define Fo(i,k,n) for(int i=k ; i<n ; i++)
 
typedef long long int ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<pair<int,int>,int> piii;

const int inf=0x3f3f3f3f;
int n , ans , sum , a , b ,arr[mx5];
string str;
 
int main() {
	ios::sync_with_stdio(false);
	//int t;cin>>t;while(t--)
	{
		cin>>n;
		vector<int> v(n);
		fo(i,n)
		{
			cin>>v[i];
		}
		sort(v.begin(),v.end());
		for(int i=n-1 ; i>=0 ; i--)
		{
			for(int j=i-1 ; j>=0 ; j--)
			{
				if(j-1>=0)
				{
					b=v[i]-v[j];
					auto it=v.begin();
					advance(it,j);
					auto tmp=upper_bound(v.begin(),it,b);
					ans+=(j-(tmp-v.begin()));
					// cout<<(it-v.begin())<<" "<<b<<" "<<*tmp<<" "<<(tmp-v.begin())<<"\n";
				}
			}
		}
		cout<<ans;
		
	}
	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using ll = long long;
using ull = unsigned long long;
using namespace std;
double const PI = acos(-1);
int const N = 3000 + 10;
int a[N], n;
ll dp[N][N];

ll solve(int l, int r){
	if (l > r)
		return 0;
	ll &dp = ::dp[l][r];
	if (dp != -1)
		return dp;
	if ((n - r + l) & 1)
		dp = max(solve(l + 1, r) + a[l], solve(l, r - 1) + a[r]);
	else
		dp = min(solve(l + 1, r) - a[l], solve(l, r - 1) - a[r]);
	return dp;
}

int main(){
	ios_base::sync_with_stdio(0), cin.tie(0);
	memset(dp, -1, sizeof(dp));
	cin >> n;
	for (int i = 0; i < n; ++i) cin >> a[i];
	cout << solve(0, n - 1);
	return 0;
}


Measured memory_bytes: 71168
#include <bits/stdc++.h>
#define int long long
#define double long double
using namespace std;
const int MOD = 1000000007;
const int INF = 1e14;
using Graph = vector<vector<int>>;

signed main(){
  int N, K;
  cin >> N >> K;

  vector<int> plus;
  vector<int> minus;
  int kake = 1;
  for (int i = 0; i < N; i++){
    int A;
    cin >> A;
    if (A > 0) plus.push_back(A);
    else minus.push_back(A);
    kake *= A;
    kake %= MOD;
  }

  if (N == K){
    kake %= MOD;
    if (kake < 0) kake += MOD;
    cout << kake << endl;
    return 0;
  }

  sort(plus.rbegin(), plus.rend());

  int ans = 1;
  //正の数が1つもなかったら
  int m = (int)minus.size();
  if (plus.size() == 0){
    if (K % 2 == 1){
      sort(minus.rbegin(), minus.rend());
      for (int i = 0; i < K; i++){
        ans *= minus[i];
        ans %= MOD;
      }
    }
    else{
      sort(minus.begin(), minus.end());
      for (int i = 0; i < min(K, m); i++){
        ans *= minus[i];
        ans %= MOD;
      }
      if (minus.size() < K){
        cout << 0 << endl;
        return 0;
      }
    }
  }
  else{ //正の数が一つ以上あったら
    sort(minus.begin(), minus.end());
    int cnt = 0;
    int pnow = 0;
    int mnow = 0;
    if (K % 2 == 1){
      ans *= plus[0];
      ans %= MOD;
      pnow++;
      cnt++;
    }
    while (cnt < K){
      int pkouho = -1;
      int mkouho = -1;
      if (pnow + 1 < plus.size()){
        pkouho = plus[pnow] * plus[pnow + 1];
        // pkouho %= MOD;
      }
      if (mnow + 1 < minus.size()){
        mkouho = minus[mnow] * minus[mnow + 1];
        // mkouho %= MOD;
      }
      if (pkouho > mkouho){
        ans *= pkouho % MOD;
        ans %= MOD;
        pnow += 2;
      }
      else{
        ans *= mkouho % MOD;
        ans %= MOD;
        mnow += 2;
      }
      cnt += 2;
    }
  }

  if (ans < 0){
    ans %= MOD;
    ans += MOD;
  }

  cout << ans << endl;
}


Measured memory_bytes: 5644
#while True:     
#  try:         
#    listC.append(list(map(int,input().split())))
#  except:         
#    break; 
#x,y = map(int,input().split())
N = int(input())
d = list(map(int,input().split()))
d.sort()
l = int(0.5*N -1)
r = int(0.5*N)

ans = int(d[r] - d[l])
                        
print(ans)
  

Measured memory_bytes: 14428
import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws Exception {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
        
        int n = Integer.parseInt(br.readLine());
        long ans = 0;
        
        for(int i = 1; i <= n; i++){
            if((i % 3 != 0) && (i % 5 != 0)){
                ans += i;
            }
        }
         
        out.println(ans);
        out.close();
        
    }
}

Measured memory_bytes: 32768
#include<stdio.h>
char func(int m,int f,int r);
int main(){
	int m,f,r;
	char seiseki;
	
	while(1){
		scanf("%d %d %d",&m,&f,&r);
		if(m==-1&&f==-1&&r==-1){
			break;
		}
		seiseki=func(m,f,r);
		
		printf("%c\n",seiseki);
	}
	
	return 0;
}



char func(int m,int f,int r){
	
	char seiseki;
	
	 if(m==-1||f==-1){
		seiseki='F';
	}
	else if((m+f)>=80){
		seiseki='A';
	}
	else if((m+f)>=65&&(m+f)<80){
		seiseki='B';
	}
	else if((m+f)>=50&&(m+f)<65){
		seiseki='C';
	}
	else if((m+f)>=30&&(m+f)<50){
		seiseki='D';
		if(r>=50){
			seiseki='C';
		}
	}
	else if((m+f)<30){
		seiseki='F';
	}
	
	return seiseki;
}

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

#define  ll    long long int

int cnt[111];
set<int> prime;
set<int>::iterator it;

void go(int n)
{
    int i, j, rt = sqrt(n);
    for (i = 2; i <= rt; i++) {
        if (n % i == 0) {
            while (n % i == 0) {
                n /= i;
                cnt[i]++;
            }
            prime.insert(i);
        }
    }
    if (n != 1) {
        prime.insert(n);
        cnt[n]++;
    }
}

int main( )
{
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        go(i);
    }
    int i, j, k;
    vector<int> v;
    for (it = prime.begin(); it != prime.end(); it++) {
        //cout << (*it) << ' ' << cnt[(*it)] << '\n';
        v.push_back(*it);
    }
    int c = 0;
    set< pair<int, pair<int, int> > > st1;
    for (i = 0; i < (int) v.size(); i++) {
        if (cnt[v[i]] >= 74) c++;
        for (j = 0; j < (int) v.size(); j++) {
            if (i == j) continue;
            if (cnt[v[i]] >= 2 && cnt[v[j]] >= 24) c++;
            if (cnt[v[i]] >= 4 && cnt[v[j]] >= 14) c++;
            for (k = 0; k < (int) v.size(); k++) {
                if (i == k || j == k)  continue;
                if (cnt[v[i]] >= 2 && cnt[v[j]] >= 4 && cnt[v[k]] >= 4) {
                    int a = v[j];
                    int b = v[k];
                    if (a < b) swap(a, b);
                    st1.insert(make_pair(v[i], make_pair(a, b)));
                }
            }
        }
    }
    cout << c + (int) st1.size() << '\n';
    return 0;
}

Measured memory_bytes: 256
#include <stdio.h>
#include <stdlib.h>

struct node{
  struct node *right;
  struct node *left;
  struct node *parent;
  int key;
};
typedef struct node * Node;
#define NIL NULL

Node root;

void insert(int a){
  Node y = NIL;
  Node x = root;
  Node z;

  z = malloc(sizeof(struct node));
  z->key = a;
  z->left = NIL;
  z->right = NIL;

  while(x!=NIL){
    y=x;
    if(z->key < x->key){
      x = x->left;
    } else {
      x = x->right;
    }
  }
  z->parent = y;
  if(y==NIL){
    root=z;
  }else if(z->key < y->key){
    y->left = z;
  }else{
    y->right = z;
  }
}

void inorder(Node u){
  if(u==NIL){
    return;
  }
  inorder(u->left);
  printf(" %d",u->key);
  inorder(u->right);
}

void preorder(Node u){
  if(u==NIL){
    return;
  }
  printf(" %d",u->key);
  preorder(u->left);
  preorder(u->right);
}

int main(){
  int h, i, a;
  char com[20];

  scanf("%d", &h);
  for ( i = 0; i < h; i++ ){
    scanf("%s%d", com,&a);
    if ( com[0] == 'i' ){
      insert(a);
    }else{
      inorder(root);
      printf("\n");
      preorder(root);
      printf("\n");
    }
  }

  return 0;
}



Measured memory_bytes: 25176
def isPrime( x ):
	if 2 == x or 3 == x:
		return True
	if 0 == x&1:
		return False
	i = 3 
	while  i*i <= x:
		if 0 == x%i:
			return False
		i += 1
	return True


n = int( raw_input( ) )
nums = []
i = 0
while i < n:
	nums.append( int( raw_input( ) ) )
	i += 1
cnt = i = 0
for num in nums:
	if isPrime( num  ):
		cnt += 1
	i += 1

print( cnt )

Measured memory_bytes: 4544
n=int(input())
A=list(map(int,input().split()))
mod=10**9+7

def inverse(a): #aに対し、a**(mod-2)、つまり逆元を返す
    T=[a]
    while 2**(len(T))<mod: #a**1,a**2.a**4,a**8,...を計算しておく
        T.append(T[-1]**2%mod)
    b=bin(mod-2) #mod-2を2進数表記にする
    ans=1
    for i in range(len(b)-2):
        if int(b[-i-1])==1:
            ans=ans*T[i]%mod
    return ans

def make_eratosthenes(n): #エラストテネスの篩(最大の素因数を格納した配列)
    A=[0]*n
    A[0],A[1]=-1,-1
    for i in range(2,n):
        if A[i]==0:
            j=i
            while j<n:
                A[j]=i
                j+=i
    return A

E=make_eratosthenes(10**6+5)

l={}
for a in A:
    now=a
    f=[] #素因数格納配列
    while now>1:
        f.append(E[now])
        now//=E[now]
    chk=0 
    for p in f:
        if chk==p: #同じ素因数が複数あるときに飛ばす
            continue
        chk=p
        if p in l.keys(): #辞書に素因数がある場合、個数の多いほう
            l[p]=max(l[p],f.count(p))
        else: #辞書にない場合新規追加
            l[p]=f.count(p)

lcm=1
for k in l:
    for i in range(l[k]):
        lcm=lcm*k%mod
s=0
for i in range(n):
    s+=lcm*inverse(A[i])%mod
    s%=mod
print(s)

Measured memory_bytes: 14476
#include <stdio.h>
//#include <stdlib.h>
//#include <string.h>
//#include <stdbool.h>
//#include <limits.h>
//#include <math.h>

int main() {
  char s[3][4];
  for (int i=0; i<3; i++) scanf("%s", s[i]);
  printf("%c%c%c\n", s[0][0], s[1][1], s[2][2]);
  return 0;
}


Measured memory_bytes: 128
/*Author : Harsh AKA Codula*/

#include<iostream>
using namespace std;
#define ll long long
#define inp freopen("input.txt","r",stdin)
#define fast ios_base::sync_with_stdio(false);cin.tie(NULL)
 
//main class

class Solution
{
	public:
		void run()
		{
			ll t=1;//cin>>t;
			while(t--)
			{
				string s;
				cin>>s;
				ll a;
				a=0;
				for(char i : s)
				{
					a+=i-'0';
				}
				if(a%9==0)
				{
					cout<<"Yes";
				}
				else
				{
					cout<<"No";
				}
				cout<<"\n";
			}
		}	
};
//driver func

int main()
{
	//fast;
	//inp;
	Solution MAIN1;
	MAIN1.run();
	return 0;
}


Measured memory_bytes: 3720
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#define loop(i,a,b) for(int i=a;i<b;i++)
#define rep(i,a) loop(i,0,a)
#define pb push_back
#define all(in) in.begin(),in.end()
using namespace std;
typedef long long ll;
typedef int Def;
typedef pair<Def,Def> pii;
typedef vector<string> vs;
typedef vector<Def> vi;
Def inf = sizeof(Def) == sizeof(long long) ? 2e18 : 1e9+10;

int main(){
  int n;
  while(cin>>n,n){
    vs in(n);
    rep(i,n)cin>>in[i];
    rep(i,n)rep(j,in[i].size())if(in[i][j]=='.')in[i][j]=' ';
    else if(j&&isalpha(in[i][j])&&in[i][j-1]==' ')in[i][j-1]='+';
    rep(i,1200){
      int t=inf;
      rep(j,n)if(i<in[j].size()){
	if(in[j][i]=='+'){
	  if(t!=inf){
	    loop(k,t+1,j)in[k][i]='|';
	  }
	  t=j;
	}else if(isalpha(in[j][i]))t=inf;
      }else{
	t=inf;
      }
    }
    rep(i,n)cout<<in[i]<<endl;
  }
}



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

int main()
{
  vector<int> v(5);
  while (cin >> v[0] && v[0] != 0) {
    vector<bool> t(3, false);
    --v[0];
    t[v[0]] = true;
    vector<int> ans(5, 3);
    for (int i = 1; i < 5; i++) {
      cin >> v[i];
      --v[i];
      t[v[i]] = true;
    }

    for (int a = 0; a < 3; a++) {
      if (!t[a]) {
        if (!t[(a+1)%3] || !t[(a+2)%3]) {
          // all a+1 or a+2
        } else {
          // a+1 wins, a+2 lose
          for (int i = 0; i < 5; i++) {
            if (v[i] == (a+1)%3) {
              ans[i] = 1;
            } else if (v[i] == (a+2)%3) {
              ans[i] = 2;
            } else {
              while (1) {}
            }
          }
          break;
        }
      }
    }
    for (int i = 0; i < 5; i++) {
      cout << ans[i] << endl;
    }
  }
  return 0;
}

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

using namespace std;

#define int long long
#define FOR(i, j, k) for(int i = j; i < k; ++i)
#define rep(i, j) FOR(i, 0, j)
#define INF 1e9
#define LINF 1e18

typedef unsigned long long ull;
typedef pair<int, int> P;
typedef pair<P, int> Pi;
typedef pair<P, P> PP;

const int MOD = 1e9 + 7;
const int dy[]={0, 0, 1, -1};
const int dx[]={1, -1, 0, 0};

template <class T> void chmin(T& a, const T& b) { a = min(a, b); }
template <class T> void chmax(T& a, const T& b) { a = max(a, b); }

signed main() {
    cin.tie(0);
    ios::sync_with_stdio(false);

    string s;
    cin >> s;
    int res = 700;
    rep(i, 3) if(s[i] == 'o') res += 100;
    cout << res << endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define ff first
#define ss second
#define pb push_back
#define debug(val) cerr << "The value of " << #val << " is = " << val << '\n';
typedef long long ll;
typedef unsigned long long ull;
const ll mod = 1e9 + 7;
const ll inf = 922337203685477;
const ll mininf = -922337203685477;
const ll nax = 2e6 + 5;

ll fac[nax], iv[nax], k, n;
string s;

ll pangkat(ll x, ll y){
	if(y == 0){
		return 1;
	}
	ll temp = pangkat(x, y / 2);
	if(y & 1){
		return temp * temp % mod * x % mod;
	}
	else{
		return temp * temp % mod;
	}
}

ll c(ll x, ll y){
	return fac[x] * iv[y] % mod * iv[x-y] % mod;
}

int main(){
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	
	fac[0] = 1ll;
	for(ll i = 1; i < nax; i++){
		fac[i] = (fac[i-1] * i) % mod;
	}
	iv[nax-1] = pangkat(fac[nax-1], mod - 2);
	for(ll i = nax - 2; i >= 0; i--){
		iv[i] = iv[i+1] * (i + 1) % mod;
	}
	
	cin >> k >> s;
	n = s.size();
	
	ll ans = 0;
	for(ll i = 0; i <= k; i++){
		ans = ans + (pangkat(26, i) * pangkat(25, k - i) % mod * c(k-i+n-1, n-1) % mod);
		ans %= mod;
	}
	cout << ans << '\n';
}


Measured memory_bytes: 35492
#include<bits/stdc++.h>
using namespace std ;
typedef long long ll ;
int main () {
  int N ;
  cin >> N ;
  ll h[N] ;
  for(int i =0 ; i < N ; i++) cin >> h[i] ;
  ll dp[N] ;
  dp[0] = 0 ;
  for(int i =1 ;i < N;i++) {
    dp[i] = 1e10 ;
    if(i-1>=0) dp[i] = min(dp[i] , abs(h[i]-h[i-1]) + dp[i-1]) ;
    if(i-2>=0)  dp[i] = min(dp[i] , abs(h[i]-h[i-2]) + dp[i-2]) ;
  }
  cout<<dp[N-1]<<endl;
  return 0 ;
}


Measured memory_bytes: 1792
import std.stdio,
       std.string,
       std.conv,
       std.algorithm;

void main() {
  int N = readln.chomp.to!(int);
  long[] A = readln.chomp.split.to!(long[]);
  sort(A);

  long max_, cnt, now;
  for (int i = N - 1; i >= 0; i--) {
    if (now == A[i]) {
      cnt++;
    }
    else {
      now = A[i];
      cnt = 1;
    }

    if (cnt == 4) {
      writeln(now * now);
      return;
    }
    else if (cnt == 2) {
      if (max_ != 0) {
        writeln(now * max_);
        return;
      }
      else {
        max_ = max(max_, now);
      }
    }
  }

  writeln(0);
}


Measured memory_bytes: 4348
#include<bits/stdc++.h> 
//#define <- プログラムの文字列を置換する
//typedef <- 新しい型に名前を付けるためのキーワード

using namespace std;

#define MAX_N 100000

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

const double PI = 3.141592653589793;
const long long MOD = 1e9 + 7;
const long long INF = 1e15;
const int INF_INT = 1e9;

int main(){
    string s;
    cin >> s;
    int n = s.length();
    if(s[n-1] == '3') cout << "bon" << endl;
    else if(s[n-1] == '0' || s[n-1] == '1' || s[n-1] == '6' || s[n-1] == '8') cout << "pon" << endl;
    else cout << "hon" << endl;
    return 0;
}


Measured memory_bytes: 3596
#include <iostream>
#include <set>
#include <map>
#include <string>
#include <math.h>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <bitset>
#include <string.h>

using namespace std;

// #define for(i,a,b) for (int i=(a);i<(b);++i)
typedef long long ll;
typedef pair<ll,ll> P;
#define REP(i,n) for(long long i = 0; i < (long long)(n); i++)
#define pb push_back // vectorに要素追加
#define INF (ll)1e18

ll mod = 1e9+7;



// 検索タグ
int main() {
	// 入力
	string S;cin>>S;

	// 解法
	bool ans = (S[2]==S[3]) & (S[4]==S[5]);

	//出力
	if (ans) printf("Yes\n");
	else printf("No\n");
}


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

#define rep(i,n) for(int i=0; i<(n); ++i)
#define rrep(i,n) for(int i=1; i<=(n); ++i)
#define drep(i,n) for(int i=(n)-1; i>=0; --i)
#define foreach(it, v) for(typeof(v.begin()) it=v.begin(); it!=v.end(); ++it)
#define pb push_back
#define sz(x) (int)(x).size()
#define fi first
#define se second

typedef unsigned int uint;
typedef long long int ll;
typedef vector<int> vi;
typedef pair<int,int> pii;
typedef vector<pii> vpii;
typedef set<int> si;

int N;

vi m[200010];

pii visit(int b, int v) {
  pii r(0, v);
  for(const auto& e : m[v]) {
    if (e != b) {
      auto t = visit(v, e);
      t.fi++;
      if (r.fi < t.fi) r = t;
    }
  }
  return r;
}
int diameter() {
  pii r = visit(-1, 1);
  pii t = visit(-1, r.se);
  return t.fi; // r.se <=> t.se is farthest pair
}

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

  cin >> N;
  int a, b;
  rep(i, N-1) {
    cin >> a >> b;
    m[a].pb(b);
    m[b].pb(a);
  }
  int s = diameter();
  if (s%3!=1) cout << "First\n";
  else cout << "Second\n";
  return 0;
}


Measured memory_bytes: 23680
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<(int)(n);++i)
#define repone(i,n) for(int i=1;i<(int)(n);++i)
#define repo(i,o,n) for(int i=o;i<(int)(n);++i)
#define Rep(j,n) for(int j=0;j<(int)(n);++j)
#define Repo(j,o,n) for(int j=o;j<(int)(n);++j)
#define Repone(j,n) for(int j=1;j<(int)(n);++j)
#define all(v) (v).begin(),(v).end()
#define rall(v) (v).rbegin(),(v).rend()
#define int long long
#define pb(a) push_back(a)
#define eraser(v,i) (v).erase(v.begin()+(i))
#define pbpair(a,b) push_back(make_pair(a,b))
#define MOD 1000000007
#define INF 9223372036854775807
#define pairint pair<int,int>
int num[12] = {31,28,31,30,31,30,31,31,30,31,30,31};
bool uru(int checkyear){if(checkyear%4==0){if(checkyear%100!=0||checkyear%400==0)return true;}return false;}
int gcd( int x, int y ){return y ? gcd(y, x%y) : x;}
signed main()
{
int x=0,y=0,z=0,w=0,n=0,m=0;
std::cin >> x;
std::vector<int> v(x);
rep(i,x){
  std::cin >> y;
  v[y-1]=i+1;
}
rep(i,x){
  std::cout << v[i] << ' ';
}
}


Measured memory_bytes: 1536
#include<stdio.h>
#define MAX 100
#define INFTY 900000000
#define WHITE 0
#define GRAY 1
#define BLACK 2

int n,M[MAX][MAX];

void sssp(){
  int i,u,v,minicost;
  int d[MAX],color[MAX];
  for(i=0;i<n;i++){
    d[i]=INFTY;
    color[i]=WHITE;
  }
  d[0]=0;
  color[0]=GRAY;
  while(1){
    minicost=INFTY;
    u=-1;
    for(i=0;i<n;i++){
      if(minicost>d[i] && color[i]!=BLACK){
	u=i;
	minicost=d[i];
      }
    }
    if(u==-1)break;
    color[u]=BLACK;
    for(v=0;v<n;v++){
      if(color[v]!=BLACK && M[u][v]!=INFTY){
	if(d[v]>d[u]+M[u][v]){
	  d[v]=d[u]+M[u][v];
	  color[v]=GRAY;
	}
      }
    }
  }
  for(i=0;i<n;i++){
    printf("%d ",i);
    if(d[i]==INFTY)printf("-1\n");
    else printf("%d\n",d[i]);
  }
}

int main(){
  int i,j;
  int k,c,u,v;
  scanf("%d",&n);
  for(i=0;i<n;i++){
    for(j=0;j<n;j++){
      M[i][j]=INFTY;
    }
  }

  for(i=0;i<n;i++){
    scanf("%d%d",&u,&k);
    for(j=0;j<k;j++){
      scanf("%d%d",&v,&c);
      M[u][v]=c;
    }
  }
  sssp();
  return 0;
}

Measured memory_bytes: 636
#include <algorithm>
#include <cstdio>
#include <functional>
#include <iostream>
#include <cfloat>
#include <climits>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <map>
#include <unordered_map>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <time.h>
#include <vector>
using namespace std;

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

const long double pi = 3.141592653589793;

#define debug(x) cout << #x << " = " << (x) << endl;
#define rep(i, n) for(int i = 0;i < n;i++)
#define pb push_back
#define mp make_pair
#define mod 1000000007

int r, c, n, x1, y, x2, y2;
vector<pii> g[4];
map<pii, int> ma;

bool boundary() {
    bool a1 = false, a2 = false;
    if(x1 == 0 || x1 == r || y == 0 || y == c) a1 = true;
    if(x2 == 0 || x2 == r || y2 == 0 || y2 == c) a2 = true;
    return (a1 && a2);
}

int main() {
	ios::sync_with_stdio(false);
    //freopen("input.in","r",stdin);
  	//freopen("output.out","w",stdout);
    cin>>r>>c>>n;
    rep(i, n) {
        cin>>x1>>y>>x2>>y2;
        if(boundary()) {
            ma[{x1, y}] = ma[{x2, y2}] = i+1;

            if(x1 == 0) g[0].pb({x1, y});
            else if(x1 == r) g[2].pb({x1, y});
            else if(y == 0) g[3].pb({x1, y});
            else g[1].pb({x1, y});

            x1 = x2, y = y2;
            if(x1 == 0) g[0].pb({x1, y});
            else if(x1 == r) g[2].pb({x1, y});
            else if(y == 0) g[3].pb({x1, y});
            else g[1].pb({x1, y});
        }
    }

    sort(g[0].begin(), g[0].end());
    sort(g[1].begin(), g[1].end());
    sort(g[2].begin(), g[2].end());
    reverse(g[2].begin(), g[2].end());
    sort(g[3].begin(), g[3].end());
    reverse(g[3].begin(), g[3].end());

    stack<int> s;
    rep(j, 4)
    rep(i, g[j].size()) {
        int val = ma[g[j][i]];
        if(s.empty()) s.push(val);
        else if(s.top() == val) s.pop();
        else s.push(val);
    }

    if(s.empty()) cout<<"YES"<<endl;
    else cout<<"NO"<<endl;

	return 0;
}

Measured memory_bytes: 14696
#include <iostream>
#include <vector>
#include <bitset>
using namespace std;
int main(){
  string s;
  cin >> s;
  s += 'T';
  int x, y;
  cin >> x >> y;
  vector< vector<int> > L(2);
  vector<int> S(2,0);
  int d = 0, t = 0;
  for(int i = 0; i < s.length(); ++i){
    if(s[i] == 'T'){
      L[d].push_back(t);
      S[d] += t;
      t = 0;
      d = 1 - d;
    }else{
      ++t;
    }
  }
  //cout << S[0] << " "<< S[1] << " " << x << " " << y << endl;
  if(S[0] < x || S[1] < y){
    cout << "No" << endl;
    return 0;
  }
  //cout << "L[0] : "; for(int i = 0; i < L[0].size(); ++i) cout << L[0][i] << " "; cout << endl;
  //cout << "L[1] : "; for(int i = 0; i < L[1].size(); ++i) cout << L[1][i] << " "; cout << endl;
  x = abs(x-S[0]);
  y = abs(y-S[1]);
  if(x%2 || y%2){
    cout << "No" << endl;
    return 0;
  }
  x /= 2;
  y /= 2;
  //cout << x << " " << y << endl;
  /*
  int n = 8000;
  vector< vector<bool> > dp_x(n,vector<bool>(n,false)),dp_y(n,vector<bool>(n,false));  
  dp_x[0][0] = true;
  for(int i = 0; i < L[0].size(); ++i){
    for(int j = 0; j < n; ++j){
      if(dp_x[i][j]){
        dp_x[i+1][j] = true;
        if(j+L[0][i] < n) dp_x[i+1][j+L[0][i]] = true;
      }
    }
  }
  dp_y[0][0] = true;
  for(int i = 0; i < L[1].size(); ++i){
    for(int j = 0; j < n; ++j){
      if(dp_y[i][j]){
        dp_y[i+1][j] = true;
        if(j + L[1][i] < n) dp_y[i+1][j+L[1][i]] = true;
      }
    }
  }
  if(dp_x[L[0].size()-1][x] && dp_y[L[1].size()-1][y]) cout << "Yes" << endl;
  else cout << "No" << endl;
  */
  bitset<8001> dp_x = 1, dp_y = 1;
  for(int i = 1; i < L[0].size(); ++i) dp_x |= (dp_x<<(L[0][i]));
  for(int i = 0; i < L[1].size(); ++i) dp_y |= (dp_y<<(L[1][i]));
  if(dp_x[x] && dp_y[y]) cout << "Yes" << endl;
  else cout << "No" << endl;
  return 0;
}


Measured memory_bytes: 256
#include<cstdio>
#include<iostream>
#include<string>
#include<algorithm>

using namespace std;

int main()
{
  int m, f, r;
  char ans;
  while(true)
  {
    cin >> m >> f >> r;
    if(m == f && f == r && r == -1)
      break;
    else if(m == -1 || f == -1 || m + f < 30)
      ans = 'F';
    else if(m + f >= 80)
      ans = 'A';
    else if(m + f >= 65)
      ans = 'B';
    else if(m + f >= 50 || r >= 50)
      ans = 'C';
    else 
      ans = 'D';
    cout << ans << endl;
  }
  return 0;
}

Measured memory_bytes: 1152
#include <bits/stdc++.h>
using namespace std;
#define mp       make_pair
#define pb       push_back
#define all(x)   (x).begin(),(x).end()
#define YES() printf("YES\n")
#define NO() printf("NO\n")
#define Yes() printf("Yes\n")
#define No() printf("No\n")
#define in(x,y,h,w) x >= 0 && x < h && y >= 0 && y < w

#define int long long
//typedef    long long          ll;
typedef    vector<bool>       vb;
typedef    vector<int>        vi;
typedef    vector<vb>         vvb;
typedef    vector<vi>         vvi;
typedef    pair<int,int>      P;

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); }
 
const int INF=1e+18;
const double EPS=1e-9;
const int MOD=1000000007;
 
const int dx[]={1,0,-1,0},dy[]={0,-1,0,1};

signed main(){
	int x,a,b;
	cin >> x >> a >> b;
	cout << (x - a) % b << endl;
	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define scn(n) scanf("%d",&n)
#define lscn(n) scanf("%lld",&n)
#define pri(n) printf("%d",n)
#define lpri(n) printf("%lld",n)
#define priln(n) printf("%d\n",n)
#define lpriln(n) printf("%lld\n",n)
#define F first
#define S second
const int mod=1e9+7;

int main()
{
    int t=1;
   // cin>>t;

    while(t--)
    {
        string s;
        cin>>s;

        int x=0;
        for(int i=0;i<s.size();i++)
        {
            int temp=(int)(s[i]-'0');
            x+=temp;
        }
        if(x%9==0)
        cout<<"Yes";
        else
        cout<<"No";
    }
}

Measured memory_bytes: 3712
/*~=~=~=~=~=~=~=~=~=~=~=~=~=~=~=~=~=~=~=
*$* WRITER:kakitamasziru/OxOmisosiru *$*
~=~=~=~=~=~=~=~=~=~=~=~=~=~=~=~=~=~=~=*/
#ifdef LOCAL_JUDGE
#define _GLIBCXX_DEBUG //FOR THE DEBUG! COMMENT OUT THIS WHEN SUBMITTING!
#endif
#include <iostream> // cout, endl, cin
#include <string> // string, to_string, stoi
#include <vector> // vector
#include <algorithm> // min, max, swap, sort, reverse, lower_bound, upper_bound
#include <utility> // pair, make_pair
#include <tuple> // tuple, make_tuple
#include <cstdint> // int64_t, int*_t
#include <iomanip>
#include <limits>//setprecision
//#include <cstdio> // printf
#include <map> // map
#include <queue> // queue, priority_queue
#include <set> // set
#include <stack> // stack
#include <deque> // deque
#include <math.h>//pow,,,
#include <cmath>//abs,,,
#include <bitset> // bitset
//It is so troublesome that I include bits/stdc++.h !
using namespace std;

template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
const long long INF = 100100100100;
const long long MOD = 1000000007;
typedef pair<int,int> P;
//NのM乗を求める(繰り返し二乗法)
long long mod_pow(long long N, long long M) {
    if (M == 0) return 1;
    long long res = mod_pow((N * N) % MOD, M / 2);
    //最下位ビット(*N)が1の時は単独でNをかける
    if (M & 1) res = (res * N) % MOD;

    return res %= MOD;
}
long long nCr(long long n, long long r) {
    long long A = 1, B = 1;
    //Aが分子Bが1/r!
    for (long long i = n - r + 1; i <= n; i++) {
        A = A * i % MOD;
    }
    for (long long i = 1; i <= r; i++) {
        B = B * i % MOD;
    }
    B = mod_pow(B, MOD - 2);
    B %= MOD;
    //Bは割るのではなく掛ける
    return (A * B) % MOD;
}

long long gcd(long long a, long long b) {
    if (b == 0) return a;
    else return gcd(b, a % b);
}
 
long long lcm(long long a, long long b) {
    return a * b / gcd(a, b);
}

long long A,B;
bool ok(long long key,long long index){
    if(index > key) return true;
    else if(index <= key) return false;
}
long long binary_search(long long key,long long size){
    //left,right,midはいずれもindex
    long long left = -1,right = size;
    while(right - left > 1){
        long long mid = left + (right-left)/2;
        long long hantei = ok(key,mid);
        if(hantei) right = mid;
        else left = mid;
    }
    if(left == -1)return 0;
    return left;
}

int main() {
    long long A,B,N;
    cin >> A >> B >> N;
    long long Bs = min(B-1,N);
    cout << ((Bs)*A)/B - A*((Bs)/B) << endl;


    // PLEASE GIVE ME THE "ACCEPTED" !
}


Measured memory_bytes: 3596
import java.io.*;
import java.util.*;

public class Main {

    public static void main(String[] args) throws IOException {
        InputStream inputStream = System.in;
        Scanner in = new Scanner(inputStream);
        PrintWriter out = new PrintWriter(System.out);

        int n = in.nextInt();
        int l = in.nextInt();
        int sum = 0;
        int first = l;
        int last = l + n - 1;
        boolean zero = false;
        for (int i = 1; i <= n; i++) {
            zero = zero || (l + i - 1 == 0);
            sum += l + i - 1;
        }

        if (zero) out.println(sum);
        else {
            if (Math.abs(sum - last) > Math.abs(sum -first)) out.println(sum - last);
            else out.println(sum - first);
        }

        out.close();
    }
}

Measured memory_bytes: 21844
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Scanner;

public class Main{
	
	private static List<Integer>[] graph = new ArrayList[100010];
	private static boolean[] vis1 = new boolean[100010];
	private static boolean[] vis2 = new boolean[100010];
	
	public static void main(String[] args) {
		
		Scanner scan = new Scanner(System.in);
		int i , n = scan.nextInt();
		for (i = 1;i <= n;i ++) {
			graph[i] = new ArrayList<>();
		}
		for (i = 0;i < n - 1;i ++) {
			int from , to;
			from = scan.nextInt();
			to = scan.nextInt();
			graph[from].add(to);
			graph[to].add(from);
		}
		bfs(n);
		int cnt1 = 0 , cnt2 = 0;
		for (i = 1;i <= n;i ++) {
			if (vis1[i]) {
				cnt1 ++;
			} else {
				cnt2 ++;
			}
		}
		if (cnt1 > cnt2) {
			System.out.println("Fennec");
		} else {
			System.out.println("Snuke");
		}
		
	}
	
	private static void bfs(int n) {
		
		Queue<Integer> queue1 = new LinkedList<>();
		Queue<Integer> queue2 = new LinkedList<>();
		
		queue1.add(1);
		queue2.add(n);
		vis1[1] = true;
		vis2[n] = true;
		
		while (!queue1.isEmpty() || !queue2.isEmpty()) {
			List<Integer> nextList = new ArrayList<>();
			if (!queue1.isEmpty()) {
				while (!queue1.isEmpty()) {
					int current = queue1.poll();
					for (int next : graph[current]) {
						if (!vis1[next] && !vis2[next]) {
							vis1[next] = true;
							nextList.add(next);
						}
					}
				}
				for (int index : nextList) {
					queue1.add(index);
				}
			}
			nextList.clear();
			if (!queue2.isEmpty()) {
				while (!queue2.isEmpty()) {
					int current = queue2.poll();
					for (int next : graph[current]) {
						if (!vis1[next] && !vis2[next]) {
							vis2[next] = true;
							nextList.add(next);
						}
					}
				}
				for (int index : nextList) {
					queue2.add(index);
				}
			}
		}
		
	}
	
}








Measured memory_bytes: 102736
M1, D1 = map(int, input().split(" "))
M2, D2 = map(int, input().split(" "))

if M1 == 1 or M1 == 3 or M1 == 5 or M1 == 7 or M1 == 8 or M1 == 10 or M1 == 12:
  print(1) if D1 == 31 else print(0)
elif M1 == 4 or M1 == 6 or M1 == 9 or M1 == 11:
  print(1) if D1 == 30 else print(0)
elif M1 == 2:
  print(1) if D1 == 28 else print(0)

Measured memory_bytes: 3064
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <queue>
#include <array>
#include <unordered_set>
#include <unordered_map>
#include <cmath>
#include <algorithm>
#include <numeric>
#include <cassert>
#include <utility>
#include <functional>

using namespace std;
using lli = long long int;
template<class T, class U> void init_n(vector<T>& v, size_t n, U x) 
{ v = vector<T>(n, x); }
template<class T> void init_n(vector<T>& v, size_t n) { init_n(v, n, T()); }
template<class T> void read_n(vector<T>& v, size_t n) 
{ v = vector<T>(n); for (lli i=0; i<n; ++i) cin >> v[i]; }
template<class T, class U> void read_n(vector<pair<T, U>>& v, size_t n)
{ v = vector<pair<T, U>>(n); 
  for (lli i=0; i<n; ++i) cin >> v[i].first >> v[i].second; }
template<class T> T gabs(const T& x) { return max(x, -x); }
#define abs gabs

lli n;
vector<string> s;
int main() {
  cin >> n;
  read_n(s, n);
  lli ans = 0;
  for (lli d=0; d<n; ++d) {
    bool ok = true;
    for (lli j=0; j<n; ++j) {
      for (lli i=0; i<n; ++i) {
	if (s[j][i] != s[i][j]) {
	  ok = false;
	  goto out;
	}
      }
    }
out:
    if (ok) ans += n;
    auto t = s.back();
    s.pop_back();
    s.insert(begin(s), t);
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 384
#include<iostream>
#include<string>
#include<algorithm>
#include<math.h>
#include<queue>
#include<set>
#include<map>

using namespace std;


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


	int tmp = (N + 1) / 2;

	if (tmp >= K) {
		cout << "YES" << endl;
	}
	else {
		cout << "NO" << endl;
	}


	return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <iomanip>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <numeric>
#include <bitset>
#include <cmath>

static const int MOD = 1000000007;
using ll = long long;
using namespace std;

template<class T> constexpr T INF = ::numeric_limits<T>::max()/32*15+208;

int main() {
    vector<string> v{"SAT", "FRI", "THU", "WED", "TUE", "MON", "SUN"};
    string s;
    cin >> s;
    for (int i = 0; i < 7; ++i) {
        if(v[i] == s){
            cout << i+1 << "\n";
        }
    }
    return 0;
}

Measured memory_bytes: 256
import Data.Maybe (maybe)

import qualified Data.List as L

main :: IO ()
main = do
    [n, x] <- fmap read . words <$> getLine
    answer $ solve n x

type Answer = Maybe [Int]
answer :: Answer -> IO ()
answer = putStrLn "No" `maybe` \xs -> putStrLn "Yes" >> mapM_ print xs

solve :: Int -> Int -> Answer
solve n x
    | x == 1    = Nothing
    | x == z    = Nothing
    | otherwise = Just $ wing [1 ..] ++ [x] ++ wing [m ..]
  where
    z     = 2 * n - 1
    m     = if x < n then n + 1 else n
    wing  = L.reverse . L.take (n - 1) . L.filter (x /=)

valid :: Int -> [Int] -> Bool
valid k = go
  where
    median (x, y, z)
      | max x (min y z) == x && min x (max y z) == x = x
      | max y (min z x) == y && min y (max z x) == y = y
      | max z (min x y) == z && min z (max x y) == z = z
    inner (x : y : z : xs) = median (x, y, z) : inner (y : z : xs)
    inner               _  = []
    go [x] = x == k
    go  xs = go $ inner xs


Measured memory_bytes: 12796
#include "bits/stdc++.h"
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using vi = vector<int>;
using vl = vector<ll>;
using vvi = vector<vi>;
using vvl = vector<vl>;
const ll INF = 1LL << 60;
const ll MOD = 1000000007;
template <class T>
bool chmax(T &a, const T &b) {
    return (a < b) ? (a = b, 1) : 0;
}
template <class T>
bool chmin(T &a, const T &b) {
    return (b < a) ? (a = b, 1) : 0;
}

int main() {
    ll n, k;
    cin >> n >> k;
    vl a(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }
    vl s;
    map<int, int> as;
    vvi pos(200001); /// 200001!!!
    for (int i = 0; i < n; ++i) {
        pos[a[i]].push_back(i);
    }
    int idx = 0;
    ll ks = 0;
    while (true) {
        auto currpositr = find(pos[a[idx]].begin(), pos[a[idx]].end(), idx);
        auto nextpositr = next(currpositr);
        if (nextpositr == pos[a[idx]].end()) { // loop
            nextpositr = pos[a[idx]].begin();
            ks++;
        }
        idx = *nextpositr + 1;
        if (idx == n) {
            ks++;
            idx = 0;
            break;
        }
    }
    k %= ks;
    idx = 0;
    ks = 0;
    while (true) {
        auto currpositr = find(pos[a[idx]].begin(), pos[a[idx]].end(), idx);
        auto nextpositr = next(currpositr);
        if (nextpositr == pos[a[idx]].end()) { // loop
            nextpositr = pos[a[idx]].begin();
            ks++;
            if (ks == k) {
                break;
            }
        }
        idx = *nextpositr;
        if (idx == n - 1) {
            ks++;
            idx = 0;
            break;
        } else {
            idx++;
        }
    }

    for (int i = idx; i < n; ++i) {
        int j = i; // % n;
        if (as[a[j]] == 0) {
            s.push_back(a[j]);
            as[a[j]]++;
        } else {
            while (true) {
                if (s.back() == a[j]) {
                    as[s.back()]--;
                    s.pop_back();
                    break;
                } else {
                    as[s.back()]--;
                    s.pop_back();
                }
            }
        }
    }

    for (int i = 0; i < s.size(); ++i) {
        cout << s[i];
        if (i == s.size() - 1)
            cout << endl;
        else
            cout << " ";
    }
    return 0;
}

Measured memory_bytes: 24944
#include <iostream>
#include <cstring>
using namespace std;
int a[1000], b[1000];
int dp[200001];
int main(){
	int h, n;
	cin >>h>>n;
	memset(dp, 0x3f, sizeof(dp));
	dp[0] = 0;
	int maxn = 0;
	for(int i = 0; i < n; i++){
		cin >> a[i] >> b[i];
		maxn = max(maxn, a[i]);
	}
	for(int i = 0; i < n; i++){
		for(int j = 0; j < h+maxn; j++)
			dp[j+a[i]] = min(dp[j+a[i]], dp[j]+b[i]);
	}
	int ans = 0x3f3f3f3f;
	for(int i = h; i < h+maxn; i++){
		ans = min(ans, dp[i]);
	}
	cout << ans;
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int H, W;
  cin >> H >> W;
  string* board;
  board = new string[H];
  for(int i = 0; i < H; i++)
    cin >> board[i];
  const int dx[8] = {-1, 0, 1, 1, 1, 0, -1, -1};
  const int dy[8] = {1, 1, 1, 0, -1, -1, -1, 0};
  for(int i = 0; i < H; i++){
    for(int j = 0; j < W; j++){
      if(board[i][j] == '.'){
        int add = 0;
        for(int k = 0; k < 8; k++){
          if(i+dx[k] >= 0 && i+dx[k] < H && j+dy[k] >= 0 && j+dy[k] < W)
            if(board[i+dx[k]][j+dy[k]] == '#')
              add++;
        }
        cout << char('0' + add);
      }else{
        cout << '#';
      }
      if(j == W-1){
        cout << endl;
      }
    }
	} 
}

Measured memory_bytes: 256
def gcd(a,b):
    r = a % b
    while r > 0:
        a = b
        b = r
        r = a % b
    return b

def lcm(a,b):
    return a*b / gcd(a,b)

while True:
    try:
        a,b = map(int, raw_input().split())
        print str(gcd(a,b)) + " " + str(lcm(a,b))
    except EOFError:
        break

Measured memory_bytes: 4208