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

ll mod = 1e9+7;

ll modpower(ll a, ll r){ //a^r
    ll x = 1;
    while (r > 0) {
        if (r & 1) x = x * a % mod;
        r >>= 1;
        a = a * a % mod;
    }
    return x;
}

ll modinv(ll a){
    return modpower(a, mod-2);
}

ll modconv(ll n, ll k){
	if (k > n || k < 0) return 0;
	ll res = 1;
	if (k > n/2) k = n-k;
	for (ll i = n; i >= n-k+1; i--) res = res * i % mod;
	for (ll i = 1; i <= k; i++) res = res * modinv(i) % mod;
	return res;
}

int main(){
    ll H, W, A, B;
    cin >> H >> W >> A >> B;
    ll ans = 0;
    vector<ll> fact(200001, 1);
    vector<ll> invfact(200001, 1);
    for (int i = 2; i <= 200000; i++) {
        fact[i] = (fact[i-1] * i) % mod;
        invfact[i] = modinv(fact[i]);
    }
    for (int i = 0; i <= H-A-1; i++) {
        ans = (ans + (fact[i+B-1] * invfact[i] %mod *invfact[B-1] %mod) 
               *fact[H-i-1+W-B-1]%mod*invfact[H-i-1]%mod*invfact[W-B-1]%mod) % mod;
    }
    cout << ans << endl;
    return 0;
}

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

int n, k;
vector<int> a;
bool check(int sam){
  int l = a.size();
  int cnt = 0;
  for(int i = 0; i < l; i++){
    int now = a.at(i);
    if(now <= sam) continue;
    cnt += (now+sam-1) / sam - 1;
  }
  return cnt <= k;
}

int solve(int ok, int ng){
  if(abs(ok-ng) <= 1) return ok;
  int mid = (ok+ng) / 2;
  if(check(mid)) ok = mid;
  else ng = mid;
  return solve(ok, ng);
}

int main() {
  cin >> n >> k;
  a.resize(n);
  for(int i = 0; i < n; i++) cin >> a.at(i);
  
  sort(a.begin(), a.end());
  
  cout << solve(a.at(n-1), 0) << endl;
}

Measured memory_bytes: 3924
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#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 2e9
#define ALL(v) v.begin(), v.end()
using namespace std;
typedef long long ll;
const int max_n = 50;
const int max_m = 25*49;

int parent[max_n];
int Rank[max_n];

void init(int n){
    REP(i,n){
        parent[i] = i;
        Rank[i] = 0;
    }
}

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

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

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

int N,M;
int A[max_m], B[max_m];
int main(){
    cin >> N >> M;
    REP(i,M){
        cin >> A[i] >> B[i];
    }

    //init(N);
    int ans = 0;
    REP(i,M){
        init(N);
        int a_bridge, b_bridge;
        REP(k,M){
            int a = A[k]-1, b = B[k]-1;
            if(k != i){
                unite(a,b);
            }
            else{
                a_bridge = a;
                b_bridge = b;
            }
        }
        if(!same(a_bridge, b_bridge)){
            //cout << "not same:"<< find(a_bridge) << " " << find(b_bridge) << endl;
            ans++;
        }
        else{
            //cout << "same:" <<find(a_bridge) << " " << find(b_bridge) << endl;
        }
    }
    cout << ans << endl;
}



Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll fun(ll n)
{
    switch(n % 4)
    {
    case 0:
        return n;
    case 1:
        return 1;
    case 2:
        return n + 1;
    case 3:
        return 0;
    }
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    ll a,b;
    while(cin>>a>>b)
    {
        ll x=fun(b);
        x=x^fun(a-1);
        cout<<x<<endl;
    }
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
//#define f(i,a,n) for(ll i=a;i<n;i++)
#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
ll isPrime(int n) 
{ 
	// Corner cases 
	if (n <= 1) 
		return 1; 
	if (n <= 3) 
		return 2; 

	// This is checked so that we can skip 
	// middle five numbers in below loop 
	if (n % 2 == 0 || n % 3 == 0) 
		return 1; 

	for (int i = 5; i * i <= n; i = i + 6) 
		if (n % i == 0 || n % (i + 2) == 0) 
			return 1; 

	return 2; 
} 

 
int main() 
{
    fast;
    ll t=1;
    //cin>>t;
    while(t--)
    {
        ll n,k=1,j=1;
        cin>>n;
        ll A[n+1];
        A[0]=0;
        for(ll i=1;i<=n;i++)
        {
            cin>>A[i];
        }
        for(ll i=0;i<n+1;i++)
        {
            if(A[j]==2)
            {
                cout<<k;
                k=0;
                break;
            }
            else
            {
                j=A[j];
            }
            k++;
        }
        if(k!=0)
        cout<<"-1";
    }    
    return 0;
}


Measured memory_bytes: 4436
import sys
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())


input = sys.stdin.readline
N, M = map(int, input().split())
uf = UnionFind(N)
for _ in range(M):
    x, y, z = map(int, input().split())
    x -= 1
    y -= 1
    uf.union(x, y)
print(uf.group_count())


Measured memory_bytes: 74956
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String passStr = sc.next();
        int a = Character.getNumericValue(passStr.charAt(0));
        int b = Character.getNumericValue(passStr.charAt(1));
        int c = Character.getNumericValue(passStr.charAt(2));
        int d = Character.getNumericValue(passStr.charAt(3));
        if (a == b || b == c || c == d) {
            System.out.println("Bad");
        } else {
            System.out.println("Good");
        }
    }
}

Measured memory_bytes: 23764
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <regex>
#include <numeric>
using namespace std;

/*--- Macro ---*/
#define rep(i, n) for(int i=0; i<(int)n; i++)
#define rep1(i, n) for(int i=1; i<(int)n; i++)
#define mp make_pair
#define pb push_back

/*---  Type ---*/
typedef long long ll;

/*--- Constants ---*/
template <typename T> const T INF = numeric_limits<T>::max() / 10;
const int MOD = (int)1e9 + 7;

// Floating
const double EPS = 1e-11;
#define EQ0(x) (abs(x) < EPS)
#define EQ(x, y) (abs(a-b) < EPS)

// Util
int max(int a, int b, int c) {return max(a, max(b, c));}
int min(int a, int b, int c) {return min(a, min(b, c));}
ll max(ll x, ll y) {return x > y ? x : y;}
ll min(ll x, ll y) {return x < y ? x : y;}
ll max(ll a, ll b, ll c) {return max(a, max(b, c));}
ll min(ll a, ll b, ll c) {return min(a, min(b, c));}

// -------------------------------------------------------------------------------------

int n;
int solve(vector<int> a) {
  vector<bool> visited;
  visited.assign(n, false);
  visited[0] = true;

  int now = 0, cnt = 0;
  while(true) {
    if(now == 1) {
      return cnt;
    }
    now = a[now]-1;
    if(visited[now]) return -1;
    cnt++;
    visited[now] = true;
  }
}

int main() {
  cin >> n;
  vector<int> a(n);
  rep(i, n) cin >> a[i];

  cout << solve(a) << endl;

  return 0;
}

Measured memory_bytes: 1024
s=input()
n=len(s)
a=""
b=""
for i in range(n):
  if i%2==1:
    a+="1"
  else:
    a+="0"
for i in range(n):
  if i%2==0:
    b+="1"
  else:
    b+="0"

cnt1=0
cnt2=0
for i in range(n):
  if s[i]==a[i]:
    cnt1+=1
  if s[i]==b[i]:
    cnt2+=1
print(min(cnt1,cnt2))

Measured memory_bytes: 3316
#include "bits/stdc++.h"
// Begin Header {{{
#define all(x) (x).begin(), (x).end()
#define rep(i, s, n) for (i64 i = (s), i##_limit = (n); i < i##_limit; ++i)
#define repr(i, s, t) for (i64 i = (s), i##_limit = (t); i >= i##_limit; --i)
#define var(type, ...) \
    type __VA_ARGS__;  \
    read(__VA_ARGS__);
#ifndef DBG
#define dump(...)
#endif
using namespace std;
using i64 = int_fast64_t;
using pii = pair<i64, i64>;
template <class T, class U>
inline bool chmax(T &a, const U &b) {
    return b > a && (a = b, true);
}
template <class T, class U>
inline bool chmin(T &a, const U &b) {
    return b < a && (a = b, true);
}
constexpr int INF = 0x3f3f3f3f;
constexpr i64 LINF = 0x3f3f3f3f3f3f3f3fLL;

template <class T>
inline vector<T> makeV(const T &initValue, size_t sz) {
    return vector<T>(sz, initValue);
}

template <class T, class... Args>
inline auto makeV(const T &initValue, size_t sz, Args... args) {
    return vector<decltype(makeV<T>(initValue, args...))>(
        sz, makeV<T>(initValue, args...));
}

template <class T>
inline istream &operator>>(istream &is, vector<T> &vec) {
    for (auto &e : vec) is >> e;
    return is;
}

inline void read() {}

template <class Head, class... Tail>
inline void read(Head &head, Tail &... tail) {
    cin >> head;
    read(tail...);
}

inline void print() { cout << "\n"; }

template <class Head, class... Tail>
inline void print(Head &&head, Tail &&... tail) {
    cout << head;
    if (sizeof...(tail)) cout << ' ';
    print(forward<Tail>(tail)...);
}

template <class T>
inline ostream &operator<<(ostream &os, const vector<T> &vec) {
    static constexpr const char *delim[] = {" ", ""};
    for (const auto &e : vec) os << e << delim[&e == &vec.back()];
    return os;
}

template <class Container>
struct Rev {
    Container &x_;
    inline Rev(Container &x) : x_(x) {}
    inline auto begin() { return rbegin(x_); }
    inline auto end() { return rend(x_); }
};
// }}} End Header

i64 f(i64 n) { return n * (n + 1) / 2; }

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    var(i64, N, a, b);

    const i64 low = a * (N - 1) + b;
    const i64 high = b * (N - 1) + a;
    print(max<i64>(0, high - low + 1));

    return 0;
}


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

int main(){
  int N;
  int a[110];
  cin >> N;
  for(int i = 0; i < N; i++){
    cin >> a[i];
  }
  int c = 0;
  for(int i = 0; i < N; i++){
    int k = i + 1;
    if((k % 2 == 1)&&(a[i] % 2 == 1)){
      c += 1;
    }
  }

  cout << c << endl;
}

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

int main() {
	string s,p;cin>>s>>p;
  	
  	s=s+s;
  
  	for (int i=0;i<s.size()-p.size()+1;i++){
    	if(s.substr(i,p.size())==p){
        	cout<<"Yes"<<endl;
          	return 0;
        }
    }
        	cout<<"No"<<endl;
}	


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

# define REP(i,n) for (int i=0;i<(n);++i)
# define rep(i,a,b) for(int i=a;i<(b);++i)
# define p(s) std::cout << s ;
# define pl(s)  std::cout << s << endl;
# define printIf(j,s1,s2) cout << (j ? s1 : s2) << endl;
# define YES(j) cout << (j ? "YES" : "NO") << endl;
# define Yes(j) std::cout << (j ? "Yes" : "No") << endl;
# define yes(j) std::cout << (j ? "yes" : "no") << endl;
# define all(v) v.begin(),v.end()
# define showVector(v) REP(i,v.size()){p(v[i]);p(" ")} pl("")
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;}
typedef long long int ll;
typedef pair<ll,ll> P_ii;
typedef pair<double,double> P_dd;

template<class T>
vector<T> make_vec(size_t a){
    return vector<T>(a);
}

template<class T, class... Ts>
auto make_vec(size_t a, Ts... ts){
  return vector<decltype(make_vec<T>(ts...))>(a, make_vec<T>(ts...));
}

template<typename T,typename V>
typename enable_if<is_class<T>::value==0>::type
fill_v(T &t,const V &v){t=v;}

template<typename T,typename V>
typename enable_if<is_class<T>::value!=0>::type
fill_v(T &t,const V &v){
  for(auto &e:t) fill_v(e,v);
}


const int MOD = 1000000007;
const int inf=1e9+7;
const ll longinf=1LL<<60 ;

void addM(long long &a, long long b) {
    a += b;
    if (a >= MOD) a -= MOD;
}

void mulM(long long &a, long long b) {
    a = ((a%MOD)*(b%MOD))%MOD ;
}

// a^b mod M
long myPow(long a,long b,int M) {
    long ret = 1;
    long tmp = a;
    while(b>0) {
        if((b&1)==1) ret = (ret * tmp) % M;
        tmp = (tmp * tmp) % M;
        b = b>>1;
    }
    return ret;
}

 // nCk mod M
int nCk(int n,int k,int M) {
    long ret = 1;
    int mi = min(k, n-k);
    for(int i=1;i<=mi;i++) {
        ret = (ret * myPow(i,M-2,M)) % M;
    }
    for(int i=n-mi+1;i<=n;i++) {
        ret = (ret * i) % M;
    }
    return (int)ret;
};

vector<pair<long long, long long> > prime_factorize(long long n) {
    vector<pair<long long, long long> > res;
    for (long long p = 2; p * p <= n; ++p) {
        if (n % p != 0) continue;
        int num = 0;
        while (n % p == 0) { ++num; n /= p; }
        res.push_back(make_pair(p, num));
    }
    if (n != 1) res.push_back(make_pair(n, 1));
    return res;
}


int main() {

    string s;
    cin >> s;

    if(s=="keyence"){
        cout << "YES" << endl;
        return 0;
    }

    REP(r,s.size()) rep(l,r+1,s.size()) {
        if(s.substr(0,r) + s.substr(l,s.size()-r+1) == "keyence"){
            cout << "YES" << endl;
            return 0;
        }
    }

    cout << "NO" << endl;


    
    return 0;
}

Measured memory_bytes: 256
D,G=map(int,input().strip().split())
pc=[]
for _ in range(D):
    pc.append(list(map(int,input().strip().split())))
    
min_num=0
for i in range(D):
    min_num+=pc[i][0]

def dfs(l,D,G):
    global min_num
    score=0
    num=0
    if len(l)==D:
        for n in range(len(l)):
            if l[n]==1:
                score+=pc[n][0]*100*(n+1)+pc[n][1]
                num+=pc[n][0]
        if score>=G:
            min_num=min(min_num,num)
        else:
            for n in reversed(range(len(l))):
                if l[n]==0:
                    i=0
                    while i<=pc[n][0]-1 and score<G:
                        score+=100*(n+1)
                        num+=1
                        i+=1
                    if score>=G:
                        break
            min_num=min(min_num,num)
        return
    else:
        for n in range(2):
            l.append(n)
            dfs(l,D,G)
            l.pop()
dfs([],D,G)
print(min_num)

Measured memory_bytes: 3064
#[allow(unused_imports)]
use std::cmp::*;
#[allow(unused_imports)]
use std::collections::*;
use std::io::{Write, BufWriter};
// https://qiita.com/tanakh/items/0ba42c7ca36cd29d0ac8
macro_rules! input {
    ($($r:tt)*) => {
        let stdin = std::io::stdin();
        let mut bytes = std::io::Read::bytes(std::io::BufReader::new(stdin.lock()));
        let mut next = move || -> String{
            bytes
                .by_ref()
                .map(|r|r.unwrap() as char)
                .skip_while(|c|c.is_whitespace())
                .take_while(|c|!c.is_whitespace())
                .collect()
        };
        input_inner!{next, $($r)*}
    };
}

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

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

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

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

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

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

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

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

#[allow(unused)]
macro_rules! debug {
    ($($format:tt)*) => (write!(std::io::stderr(), $($format)*).unwrap());
}
#[allow(unused)]
macro_rules! debugln {
    ($($format:tt)*) => (writeln!(std::io::stderr(), $($format)*).unwrap());
}

fn gcd(x: i64, y: i64) -> i64 {
    if y == 0 { x } else { gcd(y, x % y) }
}

fn solve() {
    let out = std::io::stdout();
    let mut out = BufWriter::new(out.lock());
    macro_rules! puts {
        ($($format:tt)*) => (write!(out,$($format)*).unwrap());
    }
    input! {
        a: i64, b: i64,
    }
    let g = gcd(a, b);
    puts!("{}\n", a / g * b);
}

fn main() {
    // In order to avoid potential stack overflow, spawn a new thread.
    let stack_size = 104_857_600; // 100 MB
    let thd = std::thread::Builder::new().stack_size(stack_size);
    thd.spawn(|| solve()).unwrap().join().unwrap();
}


Measured memory_bytes: 8572
#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < n; i++)
#define repr(i,n) for(int i = n-1; i >= 0; i--)
using namespace std;
typedef long long ll;
int n;
int ans;
vector<int>a,b,c;
int main(int argc, char** argv){
	cin >> n;
	a.resize(n); b.resize(n); c.resize(n-1);
	rep(i,n){
		cin >> a[i];
	}
	rep(i,n){
		cin >> b[i];
	}
	rep(i,n-1){
		cin >> c[i];
	}
	ans = b[a[0]-1];
	rep(i,n-1){
		ans += b[a[i+1]-1];
		if(a[i+1]-a[i]==1){
			ans += c[a[i]-1];
		}
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 256
#include<stdio.h>
#include<string.h>
int main(){
	int n,i,j,k,l,f1,f2,x;
	char s[260],t[260],a[29],k1[]="this",k2[]="that";
	scanf("%d\n",&n);
	strcpy(t,s);
	while(n--){
		fgets(s,257,stdin);
		for(i=1;i<26;i+=2){
			for(j=0;j<26;j++){
				if(i%13!=0){
					for(k=0;k<26;k++)x=(i*k+j)%26,a[x]=k+'a';
					//printf("%s ",a);
					strcpy(t,s);
					for(k=0;k<strlen(t);k++){
						if(t[k]>='a' && t[k]<='z')t[k]=a[t[k]-'a'];
					}
					//printf(" %s",t);
					for(k=0;k<strlen(s)-4;k++){
						f1=f2=0;
						for(l=0;l<4;l++){
							if(k+l<strlen(t) && t[k+l]==k1[l])f1++;
							else break;
						}
						for(l=0;l<4;l++){
							if(k+l<strlen(t) && t[k+l]==k2[l])f2++;
							else break;
						}
						if(f1==4 || f2==4)break;
						//printf("%d %d\n",f1,f2);
					}
				}
				if(f1==4 || f2==4)break;
				
			}
			if(f1==4 || f2==4)break;
		}
		printf("%s",t);
	}
	return 0;
}

Measured memory_bytes: 0
#include <iostream>
using namespace std;
int main(int argc, char** argv) {
    string s; cin >> s;
    long long ans = 0, c = 0;
    for (int i = s.size()-1; i >= 0; i--) {
        if (s[i] == 'B') { ans += s.size() - c - i - 1; c++; }
    }
    cout << ans << endl;
}


Measured memory_bytes: 640
// atcoder/abc089/C/main.cpp
// author: @___Johniel
// github: https://github.com/johniel/

#include <bits/stdc++.h>

#define each(i, c) for (auto& i : c)
#define unless(cond) if (!(cond))

using namespace std;

typedef long long int lli;
typedef unsigned long long ull;
typedef complex<double> point;

template<typename P, typename Q> ostream& operator << (ostream& os, pair<P, Q> p) { os << "(" << p.first << "," << p.second << ")"; return os; }
template<typename P, typename Q> istream& operator >> (istream& is, pair<P, Q>& p) { is >> p.first >> p.second; return is; }
template<typename T> ostream& operator << (ostream& os, vector<T> v) { os << "("; each (i, v) os << i << ","; os << ")"; return os; }
template<typename T> istream& operator >> (istream& is, vector<T>& v) { each (i, v) is >> i; return is; }

template<typename T> inline T setmax(T& a, T b) { return a = std::max(a, b); }
template<typename T> inline T setmin(T& a, T b) { return a = std::min(a, b); }

int main(int argc, char *argv[])
{
  ios_base::sync_with_stdio(0);
  cin.tie(0);

  int n;
  while (cin >> n) {
    vector<string> v(n);
    cin >> v;
    map<char, lli> m;
    each (i, v) ++m[i[0]];
    const string s = "MARCH";
    lli sum = 0;
    for (int i = 0; i < s.size(); ++i) {
      for (int j = i + 1; j < s.size(); ++j) {
        for (int k = j + 1; k < s.size(); ++k) {
          sum += m[s[i]] * m[s[j]] * m[s[k]];
        }
      }
    }
    cout << sum << endl;
  }

  return 0;
}


Measured memory_bytes: 5760
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <queue>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>
#include <fstream>
#include <stdio.h>
#include <complex>

using namespace std;

//conversion
//------------------------------------------
inline int toInt(string s) {int v; istringstream sin(s);sin>>v;return v;}
template<class T> inline string toString(T x) {ostringstream sout;sout<<x;return sout.str();}

//typedef
//------------------------------------------
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef pair<int, PII> TIII;
typedef long long LL;
typedef vector<LL> VLL;

//container util

//------------------------------------------
#define ALL(a)  (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define MP make_pair
#define SZ(a) int((a).size())
#define EACH(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORT(c) sort((c).begin(),(c).end())
#define MT(a,b,c) MP(a, MP(b, c))

//repetition//------------------------------------------
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)

class Dice{//サイコロを扱うクラス
public:
	int t, n, e;//top, north, east
	Dice(int _t, int _n, int _e){
		t = _t;
		n = _n;
		e = _e;
	}
	void North(void){
		int nt, nn;
		nt = 7-n;
		nn = t;
		n = nn;
		t = nt;
	}
	void South(void){
		int nt, nn, ne;
		nt = n;
		nn = 7-t;
		t = nt;
		n = nn;
	}
	void East(void){
		int nt, nn, ne;
		ne = t;
		nt = 7-e;
		e = ne;
		t = nt;
	}
	void West(void){
		int nt, nn, ne;
		ne = 7-t;
		nt = e;
		e = ne;
		t = nt;
	}
	void Left(void){
		int nt, nn, ne;
		nn = e;
		ne = 7-n;
		e = ne;
		n = nn;
	}
	void Right(void){
		int nn, ne;
		nn = 7-e;
		ne = n;
		e = ne;
		n = nn;
	}
};

int main(){
	while(1){
		int n;
		Dice d(1,5,3);
		cin >> n;
		if(n==0)return 0;
		int ret = 1;
		REP(i, n){
			string str;
			cin >> str;
			if(str == "North")d.North();
			else if(str == "South")d.South();
			else if(str == "East")d.East();
			else if(str == "West")d.West();
			else if(str == "Left")d.Left();
			else if(str == "Right")d.Right();
			ret += d.t;
		}
		cout << ret << endl;
	}
}

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

public class Main {
    private static boolean debug = false;
    private static boolean elapsed = false;

    private static PrintWriter _out = new PrintWriter(System.out);
    private static PrintWriter _err = new PrintWriter(System.err);

    private int N;
    private int M;

    private void solve(Scanner sc) {
        N = sc.nextInt();
        M = sc.nextInt();
        int[] a = new int[M];
        int[] b = new int[M];
        int[] c = new int[M];
        for (int i = 0; i < M; ++i) {
            a[i] = sc.nextInt() - 1;
            b[i] = sc.nextInt() - 1;
            c[i] = sc.nextInt();
        }

        long[][] dist = new long[N][N];

        // 初期化
        for (int i = 0; i < N; ++i) {
            for (int j = 0; j < N; ++j) {
                if (i == j) {
                    dist[i][j] = 0;
                } else {
                    dist[i][j] = Integer.MAX_VALUE;
                }
            }
        }
        for (int i = 0; i < M; ++i) {
            dist[a[i]][b[i]] = Math.min(dist[a[i]][b[i]], c[i]);
            dist[b[i]][a[i]] = Math.min(dist[b[i]][a[i]], c[i]);
        }

        // 本計算
        for (int k = 0; k < N; ++k) {
            for (int i = 0; i < N; ++i) {
                for (int j = 0; j < N; ++j) {
                    dist[i][j] = Math.min(dist[i][k] + dist[k][j], dist[i][j]);
                }
            }
        }

        int ans = M;
        for (int i = 0; i < M; ++i) {
            boolean shortest = false;
            for (int j = 0; j < N; ++j) {
                if (dist[j][a[i]] + c[i] == dist[j][b[i]]) {
                    shortest = true;
                    break;
                }
            }
            if (shortest) {
                --ans;
            }
        }

        _out.println(ans);
    }
    private long C(long n, long r) {
        long res = 1;
        for (long i = n; i > n - r; --i) {
            res *= i;
        }
        for (long i = r; i > 1; --i) {
            res /= i;
        }
        return res;
    }
    private long P(long n, long r) {
        long res = 1;
        for (long i = n; i > n - r; --i) {
            res *= i;
        }
        return res;
    }
    /*
     * 10^10 > Integer.MAX_VALUE = 2147483647 > 10^9
     * 10^19 > Long.MAX_VALUE = 9223372036854775807L > 10^18
     */
    public static void main(String[] args) {
        long S = System.currentTimeMillis();

        Scanner sc = new Scanner(System.in);
        new Main().solve(sc);
        _out.flush();

        long G = System.currentTimeMillis();
        if (elapsed) {
            _err.println((G - S) + "ms");
        }
        _err.flush();
    }
}

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

int min(int a, int b);

int main(){
  int n, k, i, re, fin;
  cin >> n >> k;
  fin = 0;
  
  int x[n];
  for(i = 0; i < n; i++){
    cin >> x[i];
  }
  for(i = 0; i < n; i++){
    re = x[i] - k;
    if(re < 0)re *= -1;
    fin += min(2 * x[i], 2 * re);
  }
  cout << fin << endl;
}

int min(int a, int b){
  if(a < b)return a;
  else return b;
}

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

int main(){
    int n,k;
    cin>>n>>k;
    if((n-1)/2+1<k)cout<<"NO"<<endl;
    else cout<<"YES"<<endl;
    return 0;
}

Measured memory_bytes: 256
s = input()
t = input()

slen = len(s)
tlen = len(t)

now = 0
fg=0

for i in range(slen):
    count=0
    for j in range (tlen):
        if i + j > slen-1:
            fg = 1
            continue
        if (s[i+j]) == t[j]:
            count+=1
    if fg == 1:
        break
    if now < count:
        now = count

print(tlen-now)


Measured memory_bytes: 67540
#pragma GCC optimize ("O3")
#pragma GCC target ("avx")
//#include<bits/stdc++.h>
#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long ll;
#define rep(i, n) for(int i = 0; i < (n); i++)
#define rep1(i, n) for(int i = 1; i <= (n); i++)
#define co(x) cout << (x) << "\n"
#define cosp(x) cout << (x) << " "
#define ce(x) cerr << (x) << "\n"
#define cesp(x) cerr << (x) << " "
#define pb push_back
#define mp make_pair
#define chmin(x, y) x = min(x, y)
#define chmax(x, y) x = max(x, y)
#define Would
#define you
#define please

const int cm = 1 << 17;
char cn[cm], * ci = cn + cm, ct;
inline char getcha() {
	if (ci - cn == cm) { fread_unlocked(cn, 1, cm, stdin); ci = cn; }
	return *ci++;
}
inline int getint() {
	int A = 0;
	if (ci - cn + 16 > cm) {
		if ((ct = getcha()) == '-') {
			while ((ct = getcha()) >= '0') A = A * 10 + ct - '0';;
			return -A;
		}
		else {
			A = ct - '0';
			while ((ct = getcha()) >= '0') A = A * 10 + ct - '0';;
			return A;
		}
	}
	else {
		if ((ct = *ci++) == '-') { 
			while ((ct = *ci++) >= '0') A = A * 10 + ct - '0';;
			return -A;
		}
		else {
			A = ct - '0';
			while ((ct = *ci++) >= '0') A = A * 10 + ct - '0';;
			return A;
		}
	}
}

const int mod = 1e9 + 7;
const int IMAX = 100000;
constexpr ll modpow(ll A, ll B) {
	ll kotae = 1;
	while (B > 0) {
		if (B & 1) kotae = kotae * A % mod;
		A = A * A % mod;
		B >>= 1;
	}
	return kotae;
}
class unko {
public:
	int fac[IMAX + 1], ifac[IMAX + 1], inv[IMAX + 1];
	constexpr unko() : fac(), ifac(), inv() {
		fac[0] = 1;
		rep1(i, IMAX) fac[i] = ll(fac[i - 1]) * i % mod;
		ifac[IMAX] = modpow(fac[IMAX], mod - 2);
		for (int i = IMAX; i > 0; i--) ifac[i - 1] = ll(ifac[i]) * i % mod;
		inv[0] = 1;
		rep1(i, IMAX) inv[i] = ll(ifac[i]) * fac[i - 1] % mod;
	}
	int comb(int A, int B) {
		return ll(fac[A]) * ifac[B] % mod * ifac[A - B] % mod;
	}
} f;
void pakuri_sort(int N, int A[]) {
	const int b = 8;
	int tmp[100001];
	rep(k, 4) {
		int kazu[1 << b] = {}, kazu2[1 << b] = {};
		rep(i, N) kazu[A[i] >> k * b & ((1 << b) - 1)]++;
		rep(i, (1 << b) - 1) kazu[i + 1] += kazu[i];
		for (int i = N - 1; i >= 0; i--) tmp[--kazu[A[i] >> k * b & ((1 << b) - 1)]] = A[i];
		k++;
		rep(i, N) kazu2[tmp[i] >> k * b & ((1 << b) - 1)]++;
		rep(i, (1 << b) - 1) kazu2[i + 1] += kazu2[i];
		for (int i = N - 1; i >= 0; i--) A[--kazu2[tmp[i] >> k * b & ((1 << b) - 1)]] = tmp[i];
	}
}
int main() {
	//cin.tie(0);
	//ios::sync_with_stdio(false);


	int N = getint(), K = getint();

	int A[100000];
	rep(i, N) A[i] = getint() + (1 << 30);
	pakuri_sort(N, A);

	ll kotae = 0;
	for (int i = 0; i < min(N - K + 1, K - 1); i++) {
		kotae -= ll(f.comb(N - i - 1, K - 1)) * A[i] % mod;
	}
	for (int i = K - 1; i < N - K + 1; i++) {
		kotae += ll(f.comb(i, K - 1) - f.comb(N - i - 1, K - 1)) * A[i] % mod;
	}
	for (int i = max(K - 1, N - K + 1); i < N; i++) {
		kotae += ll(f.comb(i, K - 1)) * A[i] % mod;
	}

	kotae %= mod;

	printf("%lld", (kotae + mod) % mod);

	Would you please return 0;
}

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

int main() {
    string S, T;
    cin >> S >> T;

    bool flag;
    for (int i = S.size() - T.size(); i >= 0; i--) {
        flag = true;
        for (int j = 0; j < T.size(); j++) {
            if (S[i+j] != '?' && S[i+j] != T[j]) {
                flag = false;
                break;
            }
        }
        if (flag == true) {
            for (int j = 0; j < T.size(); j++) {
                S[i+j] = T[j];
            }
            for (int k = 0; k < S.size(); k++) {
                if (S[k] == '?') {
                    S[k] = 'a';
                }
            }
            cout << S << endl;
            return 0;
        }
    }
    cout << "UNRESTORABLE" << endl;
    return 0;
}


Measured memory_bytes: 256
s=input()
n=len(s)
s1=s[:(n-1)//2]
flag=0
for i in range(len(s1)//2):
  if (s1[i]!=s1[-1-i]):
    flag=1
    break

#print(s1,flag)
#print(len(s1))
s1=s[(n+3)//2-1:]
for i in range(len(s1)//2):
  if (s1[i]!=s1[-1-i]):
    flag=1
    break
#print(len(s1))
#print(s1,flag)

for i in range(n//2):
  if s[i]!=s[-1-i]:
    flag=1
    break
if flag==1:
  print("No")
else:
  print("Yes")


Measured memory_bytes: 3064
n = gets.chomp.to_i
yday = Array.new(1000, 195)
yday[0] = 0
(1..999).select{|i| i % 3 == 0}.each do |i|
  yday[i] += 5
end

(2..999).each do |i|
  yday[i] += yday[i-1]
end

n.times do
  y, m, d = gets.chomp.split(" ").map(&:to_i)
  bday = yday[y-1]
  if y % 3 == 0 then
    bday += 20 * (m - 1)
    bday += d
  else
    (1...m).each do |i|
      if i.odd?
        bday += 20
      else
        bday += 19
      end
    end
    bday += d
  end
  puts yday[999] - bday + 1
end

Measured memory_bytes: 8632
#include <iostream>
#include <string>
#include <sstream>
#include <algorithm>
#include <vector>
#include <utility>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <map>
#include <set>
#include <stack>
#include <queue>
 
using namespace std;
 
#define pb(n)	push_back(n)
#define mp(n,m) make_pair(n,m)
#define fi 	first
#define se 	second
#define all(r) (r).begin(),(r).end()

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

typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
 
const int IMAX=((1<<30)-1)*2+1;
const double EPS=1e-10;
//int mod=1000000007


ll l=10000100;

vi v(l,1);
   

int main(){
	v[0]=0;
	v[1]=0;
	for(int i=2; i<l; i++){
		if(v[i]==1){
			for(int j=2; j<l/i; j++){
				v[i*j]=0;
			}
		}
	}
	int n,ans;
	while(cin>>n && n>0){
		ans=0;
		for(int i=2; i<=n/2; i++){
			if(v[i]==1 && v[n-i]==1)ans++;
		}
		cout<<ans<<endl;
	}
}

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

using namespace std;
typedef long long ll;
const int N = 1e6+50;
const int oo = 1e9;
ll l[100];
int main(){
	l[0]=2;l[1]=1;
	for(int i=2;i<100;i++){
		l[i] = l[i-1]+l[i-2];
	}
	int n;
	cin>>n;
	cout << l[n] << endl;
}

Measured memory_bytes: 256
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
import itertools
from itertools import permutations,combinations
import sys
import bisect
import string
import math
import time
import random
def I():
    return int(input())
def MI():
    return map(int,input().split())
def LI():
    return [int(i) for i in input().split()]
def LI_():
    return [int(i)-1 for i in input().split()]
def StoI():
    return [ord(i)-97 for i in input()]
def ItoS(nn):
    return chr(nn+97)
def GI(V,E,Directed=False,index=0):
    org_inp=[]
    g=[[] for i in range(n)]
    for i in range(E):
        inp=LI()
        org_inp.append(inp)
        if index==0:
            inp[0]-=1
            inp[1]-=1
        if len(inp)==2:
            a,b=inp
            g[a].append(b)
            if not Directed:
                g[b].append(a)
        elif len(inp)==3:
            a,b,c=inp
            aa=(inp[0],inp[2])
            bb=(inp[1],inp[2])
            g[a].append(bb)
            if not Directed:
                g[b].append(aa)
    return g,org_inp
def show(*inp,end='\n'):
    if show_flg:
        print(*inp,end=end)
YN=['Yes','No']
mo=10**9+7
inf=float('inf')
l_alp=string.ascii_lowercase
u_alp=string.ascii_uppercase
ts=time.time()
#sys.setrecursionlimit(10**5)
input=lambda: sys.stdin.readline().rstrip()

def ran_input():
    import random
    n=random.randint(4,16)
    rmin,rmax=1,10
    a=[random.randint(rmin,rmax) for _ in range(n)]
    return n,a

show_flg=False
show_flg=True

ans=0

n,t,a=LI_()
n+=1
g,c=GI(n,n-1)

def bfs(x):  # x スタート
    v=[-1]*(n)
    p=deque()
    p.append(x)
    v[x]=0
    while p:
        c=p.popleft()
        for i in g[c]:
            if v[i]==-1:
                p.append(i)
                v[i]=v[c]+1
    return v

v=bfs(a)
w=bfs(t)
ans=0
for i in range(n):
    if v[i]>=w[i] and max([v[j] for j in g[i]])>v[i]:
        ans=max(ans,v[i])

print(ans)

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

int main(void)
{
  long long n,city[5],i,ans=0,min,r;

  scanf("%lld %lld %lld %lld %lld %lld",&n,&city[0],&city[1],&city[2],&city[3],&city[4]);
  min = city[0];
  for(i=1;i<5;i++)
    {
      if(min > city[i])
	{
	  min = city[i];
	}
    }
  r = n % min;
  n = n - r;
  ans = n / min;
  if(r == 0)
    {
      ans -= 1;
    }
  ans += 5;
  printf("%lld\n",ans);
  return 0;
}

Measured memory_bytes: 128
n = int(input())
A = list(map(int,input().split()))
A.sort(reverse=True)

if n%2==0:
    k = n//2
    print(A[0]+2*sum(A[1:k]))
else:
    print(A[0]+2*sum(A[1:n//2])+A[n//2])


Measured memory_bytes: 105208
#include <iostream>

using namespace std;

int main()
{
    string s;cin >> s;
    int count = 0;
    for (int i = 0;i < s.size();i++)
    {
            if (s[i] == 'R')
            {
                    ++count;
            }
            else if (s[i] != 'R' && s[i-1] == 'R')
            {
                    break;
            }
            else {
                    continue;
            }
    }
    cout << count;
    return 0;
}


Measured memory_bytes: 3600
import math
N = int(input())
N_s = int(math.sqrt(N))

ans_list = []
ans = 0

for i in range(N_s):
  if(N%(i+1) == 0):
    ans = N/(i+1) + (i+1) - 2
    ans_list.append(int(ans))
    
ans_list = sorted(ans_list)
print(ans_list[0])

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

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

int N;
int A[2][100];
int main(void){

	cin >> N;
	rep(i, 2){
		rep(j, N){
			cin >> A[i][j];
		}
	}

	int ans = 0;
	rep(t, N){
		int tmp = 0;
		for(int j=0; j<=t; j++){
			tmp += A[0][j];
		}
		for(int j=t; j<N; j++){
			tmp += A[1][j];
		}
		if(tmp >= ans){
			ans = tmp;
		}
	}
	cout << ans << endl;

	return 0;
}


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

int main(){
  int i,a,b,array[101],c=0;
  cin>>a>>b;
  for(i=0;i<a;i++){
    cin>>array[i];
    c+=array[i];
  }
  b-=c;
  sort(array,array+a);
  cout<<a+b/array[0]<<endl;
}

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

int main()
{
 int a, b, i;
 string c,d,e;

 cin >> c >> d;

 cin >> a >> b;

 cin >> e;

 if (c == e) {
	 a = a - 1;
 }
 else {
	 b = b - 1;
 }


 cout << a << " " << b;

}


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

int fruits[1005];
int main()
{
	int N, K;
	scanf("%d%d", &N, &K);
	
	for(int i = 0; i < N; i++)
		scanf("%d", &fruits[i]);
		
	sort(fruits, fruits + N);
	int ans = 0;
	for(int i = 0; i < K; i++)
		ans += fruits[i];
		
	printf("%d", ans);
}


Measured memory_bytes: 3824
N,M = map(int,input().split())
A = set([int(input()) for _ in range(M)])
step = [0] * (N+1)
step[0] = 1
if 1 not in A:
    step[1] = 1
else:
    step[1] = 0
for i in range(2,N+1):
    if i in A:
        continue
    step[i] = (step[i-1] + step[i-2]) % 1000000007
print(step[-1])

Measured memory_bytes: 18924
/*
*          Name : chaitanya
*
*     Institute : ANITS,Visakhapatnam
*
*/
#include<cstdio>
#include<iostream>
#include<sstream>
#include<fstream>
#include<iomanip>
#include<algorithm>
#include<cmath>
#include<complex>
#include<cstring>
#include<vector>
#include<list>
#include<queue>
#include<stack>
#include<set>
#include<map>
#include<bitset>
#include<numeric>
#include<limits>
#include<climits>
#include<cfloat>
#include<functional>
#include<iterator>
#include <random>
#define infy  1000000000
#define all(x) begin(x),end(x)
#define ll long long int
#define ff first
#define ss second
#define pb push_back
const ll m = 1000000007;
#pragma GCC optimization ("O3")
const int N = 1000010;
using namespace std;
vector<string> vec_splitter(string s) {
  s += ',';
  vector<string> res;
  while(!s.empty()) {
    res.push_back(s.substr(0, s.find(',')));
    s = s.substr(s.find(',') + 1);
  }
  return res;
}
void debug_out(
vector<string> __attribute__ ((unused)) args,
__attribute__ ((unused)) int idx, 
__attribute__ ((unused)) int LINE_NUM) { cerr << endl; } 
template <typename Head, typename... Tail>
void debug_out(vector<string> args, int idx, int LINE_NUM, Head H, Tail... T) {
  if(idx > 0) cerr << ", "; else cerr << "Line(" << LINE_NUM << ") ";
  stringstream ss; ss << H;
  cerr << args[idx] << " = " << ss.str();
  debug_out(args, idx + 1, LINE_NUM, T...);
}
#ifndef ONLINE_JUDGE
#define debug(...) debug_out(vec_splitter(#__VA_ARGS__), 0, __LINE__, __VA_ARGS__)
#else
#define debug(...) 42
#endif

ll f[2000010];

ll lcm(ll a,ll b)
{
  return (a*b)/__gcd(a,b);
}
ll binpow(ll a, ll b) {
     ll res = 1;
    while (b > 0) {
        if (b & 1)
            res = res * a;
        a = a * a;
        b >>= 1;
    }
    return res;
}
 
ll find_ncr(ll n, ll r)
{
    ll m1=max(r,n-r);
    ll i,j,s,d=1,k;
    s=1;
 
    for(i=m1+1;i<=n;i++)
    {
        s=((s%m)*(i%m))%m;
    }
 
    m1=min(r,n-r);
 
    for(i=1;i<=m1;i++)
    {
        k=binpow(i,m-2);
        d=((d%m)*(k%m))%m;
    }
 
    k=(s%m*(d%m))%m;
 
    return k;
}

int main()
{
  // int x = -1, y = 10000;
  // double z = 0.2;
  // string s2 = "beginner1010";
  // long long b = 1LL << 60;
    
  // // debug(x, y, z, s, b);
    
  // double aux = 1010.0;
  // string code = "code";
    
  // debug(code + "forces",-aux / 10 * 2.3);
  // freopen("input.txt","r",stdin);
  // freopen("output.txt","w",stdout);
  //ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
  double r =1,p = 100;
  ll a,c;
  cin >> a;
  c = p*(1+r/100);
  for (int i = 2; i <= 3800; ++i)
  {
    c = c*(1+r/100);
    if(c >= a)
    {
      cout << i <<endl;
      break; 
    }
  }
  return 0;
}



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

int main() {
    int N; cin >> N;
    int ans = 1000000;
    for (int i = 1; i < N; i++) {
        int a = i, b = N - i;
        int dig_sum = 0;
        while (a) {
            dig_sum += a % 10;
            a /= 10;
        }
        while (b) {
            dig_sum += b % 10;
            b /= 10;
        }
        ans = min(ans, dig_sum);
    }
    cout << ans << endl;
}

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

int main() {
  int H, W;
  cin >> H >> W;
  
  vector<string> pix(H);
  for( int i = 0; i < H; i++ ){
    cin >> pix.at(i);
  }
  
  vector<string> pix2(H+2);
  for( int i = 0; i < H+2; i++ ){
    for( int j = 0; j < W+2; j++ ){
      pix2.at(i).push_back('#');
    }
  }
  
  for( int i = 1; i < H+1; i++ ){
    for( int j = 1; j < W+1; j++ ){
      pix2.at(i).at(j) = pix.at(i-1).at(j-1);
    }
  }
  
  for( int i = 0; i < H+2; i++ ){
    cout << pix2.at(i) << endl;
  }
}

Measured memory_bytes: 256
from collections import deque
import math
 
def explore(C, D):
    queue = deque([(C[0]-1, C[1]-1)])
    maze_visited[C[0]-1][C[1]-1] = 0
    while queue:
        y, x = queue.popleft()
        mv_cur = maze_visited[y][x]
        for i, j in [(1,0),(0,1),(-1,0),(0,-1)]:
            n_x, n_y = x + i, y + j
            if n_x >= 0 and n_y >= 0 and n_x < W and n_y < H:
                mv_n = maze_visited[n_y][n_x]
                if mv_n > mv_cur:
                    if S[n_y][n_x] == '.':
                        maze_visited[n_y][n_x] = mv_cur
                        queue.appendleft((n_y, n_x))
        for i in range(-2, 3):
            for j in range(-2, 3):
                if abs(i) + abs(j) <= 1:
                    continue
                n_x, n_y = x + i, y + j
                if n_x >= 0 and n_y >= 0 and n_x < W and n_y < H:
                    mv_n = maze_visited[n_y][n_x]
                    if mv_n > mv_cur + 1:
                        if S[n_y][n_x] == '.':
                            maze_visited[n_y][n_x] = mv_cur + 1
                            queue.append((n_y, n_x))
    
H, W = list(map(int, input().split()))
C = list(map(int, input().split()))
D = list(map(int, input().split()))
 
S = [list(input()) for i in range(H)]
 
maze_visited = [[math.inf] * W for i in range(H)]
 
explore(C,D)
 
if maze_visited[D[0] - 1][D[1] - 1] == math.inf:
    print('-1')
else:
    print(maze_visited[D[0] - 1][D[1] - 1])

Measured memory_bytes: 145500
#include <stdio.h>

#define MAX 100001
#define max(a,b) ((a) < (b) ? (b) : (a))

int par[MAX],sib[MAX],deg[MAX];
int height[MAX],dep[MAX];

void init(int);
int depth(int,int);

int main(){
  int n,i,id,l,r;

  scanf("%d" ,&n); 
  init(n);  

  for(i = 0 ; i < n ; i++){
    scanf("%d%d%d" ,&id ,&l ,&r);

    if(l != -1){
      par[l] = id;
      deg[id]++;
    }
    if(r != -1){
      par[r] = id;
      deg[id]++;
    }
    if(l != -1 && r != -1){
      sib[l] = r;
      sib[r] = l;
    }
  }

  for(i = 0 ; i < n ; i++){
    dep[i] = depth(i,0);
  }

  for(i = 0 ; i < n ; i++){
    printf("node %d: parent = %d, sibling = %d, " 
	   ,i, par[i], sib[i]);

    printf("degree = %d, depth = %d, height = %d, " 
	   , deg[i], dep[i], height[i]);
    
    if(par[i] == -1){
      printf("root\n");
    }else if(deg[i] != 0){
      printf("internal node\n");
    }else{
      printf("leaf\n");
    }
  }

  return 0;
}

void init(int n){
  int i;

  for(i = 0 ; i < n ; i++){
    par[i] = sib[i] = -1;
    deg[i] = height[i] = 0;
  }
}

int depth(int x,int dep){
  height[x] = max(height[x],dep);
  if(par[x] == -1){
    return dep;
  }else{
    return depth(par[x],dep+1);
  }
}



Measured memory_bytes: 2036
#include<bits/stdc++.h>
using namespace std;
 
int main(){
  int a, b;
  cin >> a >> b;
  
  if(b == 1){
    cout << 0 << endl;
    return 0;
  }
  
  int res = 1;
  for(int i = 1; ; i++){
    res--;
    res += a;
    if(res >= b){
      cout << i << endl;
      return 0;
    }
  }
  
  
}

Measured memory_bytes: 256
import 'dart:io';

main(List<String> args){
  int x=int.parse(stdin.readLineSync());
  int i=0;
  int value=100;
  while(true){
    if(value>=x){
      break;
    }
    value=(value*1.01).floor();
    i++;
  }
  print(i);
}

Measured memory_bytes: 13120
#include<bits/stdc++.h>
using namespace std;
int main()
{
  // #ifndef ONLINE_JUDGE
  //freopen("input.txt", "r", stdin);
  //freopen("output.txt", "w", stdout);
  //#endif
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  int n;
  cin>>n;
  int arr[n+1][3];
  for(int i=0;i<n;i++)
  {
  	for(int j=0;j<3;j++)
  		{
  			cin>>arr[i][j];
  		
  		}
  }

  int dp[n+1][3];
  memset(dp,INT_MIN,sizeof(dp));
  for(int i=0;i<3;i++)
  {
  	dp[0][i]=arr[0][i];
  }
  for(int i=1;i<n;i++)
  {
  	for(int j=0;j<3;j++)
  	{
  		for(int k=0;k<3;k++)
  		{
  			if(j==k)
  				{
  					continue;
  				}
  				else
  				{
  					dp[i][j]=max(dp[i][j],dp[i-1][k]+arr[i][j]);
  				}
  		}
  	}
  }

  cout<<max({dp[n-1][0],dp[n-1][1],dp[n-1][2]});
}



Measured memory_bytes: 2560
#include<iostream>
#include<algorithm>
#define F 21000
using namespace std;
int n,p[20010],d[20010];
int main(){
	cin>>n;
	for(int i=0;i<n;i++){
		cin>>p[i];
		d[p[i]-1]=i;
	}
	for(int i=0;i<n;i++){
		if(i)cout<<" ";
		cout<<i*F+1;
	}cout<<endl;
	for(int i=0;i<n;i++){
		if(i)cout<<" ";
		cout<<(n-i)*F+d[i]+1;
	}cout<<endl;
	return 0;	
}


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

using namespace std;

long long int A, B, C;
long long int ans;

int main() {
    cin>>A>>B>>C;
    vector<long long int> p;
    p.push_back(A); p.push_back(B); p.push_back(C);
    sort(p.begin(), p.end());
    
    long long int mid_c1 = p[2] / 2;
    long long int mid_c2 = p[2] - mid_c1;
    
    if (mid_c1 > mid_c2) ans = mid_c1 - mid_c2;
    else ans = mid_c2 - mid_c1;
    
    ans = ans * p[1] * p[0];
    cout<<ans<<endl;
}


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

using namespace std;

const int N = int(2e5) + 5;
const int MOD = int(1e9) + 7;
const int inf = int(2e9);

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

    double A,B;
    cin >> A >> B;
    double T = B*10;
    for (double i = T; i <= T + 9; ++i) {
        double x = i/100*8;
        if (int(x) == A) {
            cout << i;
            return 0;
        }
    }
    cout << -1;
    return 0;
}



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

using namespace std;

struct UnionFind {
    vector<int> par;

    UnionFind(int N) : par(N) {
        for(int i = 0; i < N; i++) par[i] = i;
    }

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

    void unite(int x, int y) { 
        int rx = root(x); 
        int ry = root(y); 
        if (rx == ry) return;
        par[rx] = ry; 
    }

    bool same(int x, int y) { 
        int rx = root(x);
        int ry = root(y);
        return rx == ry;
    }
};

int main() {
    int N, M;
    cin >> N >> M;
    vector<int> P(N);
    for(int i = 0; i < N; i++){
        cin >> P[i];
    }

    UnionFind tree(N);

    for(int i = 0; i < M; i++) {
        int x, y;
        cin >> x >> y;
        tree.unite(x-1, y-1); 
    }

    int cnt = 0;
    for(int i = 0; i < N; i++) {
        if (tree.same(i, P[i]-1)) {
            cnt++;
        }
    }
    cout << cnt << endl;
    return 0;
}


Measured memory_bytes: 3964