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

void solve(long long N, deque<long long> a){
	sort(a.begin(),a.end());
	long long ans = 0;
	while(a.size()){
		ans += a[a.size()-2];
		a.pop_back();
		a.pop_back();
		a.pop_front();
	}
	cout << ans << endl;
}

int main(){	
	long long N;
	scanf("%lld",&N);
	deque<long long> a(3*N-1+1);
	for(int i = 0 ; i <= 3*N-1 ; i++){
		scanf("%lld",&a[i]);
	}
	solve(N, a);
	return 0;
}



Measured memory_bytes: 5120
#pragma GCC optimize("O3")
#include<bits/stdc++.h>
using namespace std;
#define rc(x) return cout<<x<<endl,0
#define pb push_back
#define dbg(x) cout << #x << '=' << x << '\n';
#define ll long long
#define sz size()
#define pb push_back
const ll mod = 1e9 + 7;
int n, x, y, ans;

int32_t main(){
    ios_base :: sync_with_stdio(0); cin.tie(); cout.tie();
    cin>>n>>y; y=y/1000; int a, b;
    for(int i=0; i<=y/10; i++){
        x=y-10*i; ans=i;
            if(x>=n-ans && x%4==(n-ans)%4 && n-ans>=(x+ans-n)/4){cout<<i<<" "<<(x+ans-n)/4<<" "<<(n-ans-((x+ans-n)/4)); return 0;}
    } cout<<-1<<" "<<-1<<" "<<-1;
}


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

int main(void){
    string s;
    cin>>s;
    int ans=0;
    for(int i=0;i<s.size();i++){
        if(s[i]=='+') ans++;
        else ans--;
    }
    cout<<ans<<endl;
    return 0;
}



Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<b;i++)
#define rrep(i,b,a) for(int i=b;i>=a;i--)
#define fori(a) for(auto i : a )
#define all(a) begin(a), end(a)
#define set(a,b) memset(a,b,sizeof(a))
#define sz(a) a.size()
#define pi 3.14159
#define ll long long
#define ull unsigned long long
#define pb push_back
#define PF push_front //deque
#define mp make_pair
#define pq priority_queue
#define mod 1000000007
#define f first
#define s second
#define pii pair< int, int >
#define vi vector<int>
#define vpii vector<pii>
#define debug(v) for(auto i:v) cout<<i<<" ";
#define tc int t; cin >> t; while(t--)

using namespace std;
string repeat(string s, int n) {
    string s1 = "";
    for (int i=0; i<n;i++)
        s1+=s;
    return s1;
}
string getString(char x) {
    string s(1, x);
    return s;
}

void optimizeIO(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
}
int gcd(int a, int b){
    if (a == 0)  return b;
    return gcd(b % a, a);
}
void  solve(){
  int n;
  cin>>n;
  string s;
  cin>>s;
  int ans=0;
  rep(i,1,n){
    string g=s.substr(0,i),h=s.substr(i);
    set<char> s1(g.begin(),g.end());
    set<char> s2(h.begin(),h.end());
    int c=0;
    for(auto i:s2) if(s1.find(i)!=s1.end()) c++;
    ans=max(c,ans);
  }
  cout<<ans<<endl;
}
int main(){
    optimizeIO();
    // tc
    { solve();
    }
}


Measured memory_bytes: 3668
#include <bits/stdc++.h>
using namespace std;
int main(){
    int n;
    cin >> n;
    vector <int> x(n,0);
    for(int i = 0; i < n; i++){
        cin >> x[i];
    }
    sort(x.begin(),x.end());
    int start = x[0];
    int end = x[n-1];
    int ans = -1;
    for(int i = start; i <= end; i++){
        int sum = 0;
        for(int j = 0; j < n; j++){
            sum += pow(x[j]-i,2);
        }
        if(ans==-1){
            ans = sum;
            continue;
        }
        if(ans>sum){
            ans = sum;
            continue;
        }
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
#include<algorithm>
#include<iostream>
#include<cstring>
#include<string>
#include<vector>
#include<cstdio>
#include<cmath>
#include<set>
#include<map>
using namespace std;
typedef long long ll;
const int MAXN=1e5+5;
int read()
{
    int s=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){s=s*10+ch-'0';ch=getchar();}
    return s*f;
}
int main()
{
    string a,b;
    int n;
    while(cin>>n>>a>>b)
    {
        string ans="";
        for(int i=0;i<a.size();i++)
        {
            cout<<a[i]<<b[i];
        }cout<<endl;
    }
    return 0;
}


Measured memory_bytes: 256
use std::cmp;
use std::collections::*;
use std::i32;
use std::io::{self, Read};
use std::mem;

const MOD: usize = 1000000007;

fn main() {
    let stdin = io::stdin();
    let mut sc = Scanner::new(stdin.lock());

    let k: usize = sc.read().unwrap();

    // 2: 1 * 0 = 0, ()
    // 3: 1 * 2 = 2, (2, 1), (2, 3)
    // 4: 2 * 2 = 4, (2, 1), (2, 3), (4, 1), (4, 3)
    // 5: 2 * 3 = 6
    // 6: 3 * 3 = 9
    // 7: 3 * 4 = 12
    // 8: 4 * 4 = 16
    // 9: 4 * 5 = 20
    // 10: 5 * 5 = 25
    // 11: 5 * 6 = 30
    // n: (n / 2) * ((n / 2) + (n % 2))

    // println!("{}", (k / 2) * ((k / 2) + (k % 2)));
    println!("{}", (k / 2) * ((k + 1) / 2));
}

struct Scanner<R: Read> {
    reader: R,
}

impl<R: Read> Scanner<R> {
    fn new(reader: R) -> Scanner<R> {
        Scanner { reader: reader }
    }

    fn read<T: std::str::FromStr>(&mut self) -> Option<T> {
        self.reader
            .by_ref()
            .bytes()
            .map(|b| b.unwrap() as char)
            .skip_while(|c| c.is_whitespace())
            .take_while(|c| !c.is_whitespace())
            .collect::<String>()
            .parse()
            .ok()
    }

    fn read_vec<T: std::str::FromStr>(&mut self, n: usize) -> Option<Vec<T>> {
        (0..n).map(|_| self.read()).collect()
    }

    fn read_vec2d<T: std::str::FromStr>(&mut self, m: usize, n: usize) -> Option<Vec<Vec<T>>> {
        (0..m).map(|_| self.read_vec(n)).collect()
    }

    fn read_board(&mut self, n: usize) -> Option<Vec<Vec<char>>> {
        (0..n)
            .map(|_| {
                self.read::<String>()
                    .map(|s| s.chars().collect::<Vec<char>>())
            })
            .collect()
    }
}


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

using namespace std;

#define INF 2000000000
#define MOD 1000000007
typedef long long ll;
typedef pair<int, int> P;


int main()
{
	int w, h, n;
	cin >> w >> h >> n;
	int x, y, a;

	int l=0;
	int r=w;
	int u=h;
	int d=0;

	for (int i = 0; i < n; i++) {
		cin >> x >> y >> a;
		switch (a) {
		case 1: {
			l = max(l, x);
			break;
		}
		case 2: {
			r = min(r,x);
			break;
		}
		case 3: {
			d = max(d, y);
			break;
		}
		case 4: {
			u = min(u, y);
			break;
		}
		}
	}

	if (l>=r||d>=u) {
		cout << 0 << "\n";
		return 0;
	}
	cout << (r-l)*(u-d) << "\n";
}


Measured memory_bytes: 384
#define _USE_MATH_DEFINES
#include <iostream>
#include <fstream>
#include <sstream>
#include <string>
#include <cstring>
#include <vector>
#include <set>
#include <map>
#include <unordered_map>
#include <queue>
#include <deque>
#include <stack>
#include <algorithm>
#include <bitset>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <numeric>
#include <functional>
#include <cctype>
#include <list>
#include <limits>
#include <cassert>
#include <random>
#include <time.h>
//#include <boost/multiprecision/cpp_int.hpp>



using namespace std;
using Int = long long;
//using namespace boost::multiprecision;

const double EPS = 1e-10;
long long const MOD = 1000000007;

long long mod_pow(long long x, long long n) {
    long long res = 1;
    for (int i = 0;i < 60; i++) {
        if (n >> i & 1) res = res * x % MOD;
        x = x * x % MOD;
    }
    return res;
}

template<typename T>
T gcd(T a, T b) {
    return b != 0 ? gcd(b, a % b) : a;
}

template<typename T>
T lcm(T a, T b) {
    return a * b / gcd(a, b);
}

void fastInput() {
    cin.tie(0);
    ios::sync_with_stdio(false);
}

vector<Int> X;
vector<Int> V;
vector<Int> left_round;
vector<Int> left_max;
vector<Int> right_round;
vector<Int> right_max;


int main(void) {
    int N;
    Int C;
    cin >> N >> C;
    X.resize(N+2);
    V.resize(N+2);
    left_round.resize(N+2);
    left_max.resize(N+2);
    right_round.resize(N+2);
    right_max.resize(N+2);

    X[0] = 0;
    V[0] = 0;
    X[N+1] = C;
    V[N+1] = 0;
    for (int i = 1; i <= N; i++) {
        cin >> X[i] >> V[i];
    }

    for (int i = 1; i <= N; i++) {
        right_round[i] = right_round[i-1] + V[i] - (X[i] - X[i-1]);
        right_max[i] = right_round[i];
        right_max[i] = max(right_max[i-1], right_max[i]);
    }
    for (int i = N; 1 <= i; i--) {
        left_round[i] = left_round[i+1] + V[i] - (X[i+1] - X[i]);
        left_max[i] = left_round[i];
        left_max[i] = max(left_max[i+1], left_max[i]);
    }

    Int ans = 0;
    // right-first
    for (int i = 0; i <= N; i++) {
        Int sum = right_round[i] - X[i];
        sum += left_max[i+1];
        ans = max(sum, ans);
        ans = max(right_round[i], ans);
    }
    // left-first
    for (int i = N; 1 <= i; i--) {
        Int sum = left_round[i] - (C - X[i]);
        sum += right_max[i-1];
        ans = max(sum, ans);
        ans = max(left_round[i], ans);
    }
    cout << ans << endl;
}

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

using namespace std;

int main()
{
  int D,T,S;										
  cin>>D>>T>>S;
  if(D%S==0)
  {  
    if(D/S<=T)
      cout<<"Yes";
    else
      cout<<"No";
  }
  else
  {  
    if(D/S<T)
      cout<<"Yes";
    else
      cout<<"No";
  }
}


Measured memory_bytes: 3608
n, a, b = map(int, input().split())
H = [int(input()) for _ in range(n)]

def ok(x):
    tot = 0
    for i in range(n):
        if b*x >= H[i]:
            continue
        else:
            r = H[i] - b*x
            if r%(a-b) == 0:
                tot += r//(a-b)
            else:
                tot += r//(a-b)+1
    if tot <= x:
        return True
    else:
        return False

l = 0
r = 10**10
while l+1 < r:
    c = (l+r)//2
    if ok(c):
        r = c
    else:
        l = c
print(r)

Measured memory_bytes: 50904
#include <bits/stdc++.h>
#define _GLIBCXX_DEBUG
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()

using namespace std;
using ll = long long;
using vpii = vector<pair<int, int>>;
using vpll = vector<pair<ll, ll>>;
// ceil() 切り上げ, floor() 切り捨て
// next_permutation(all(x))

int		main(void)
{
	int N;
	string S;
	cin >> N >> S;
	string ans;
	int L = 0, R = 0;
	for (int i = 0; S[i]; i++)
	{
		if (S[i] == ')' && L == 0)
			R++;
		if (S[i] == ')' && L != 0)
			L--;
		if (S[i] == '(')
			L++;
	}
	for (int i = 0; i < R; i++)
		ans += '(';
	ans += S;
	for (int i = 0; i < L; i++)
		ans += ')';
	cout << ans << endl;
}



Measured memory_bytes: 256
n,m = map(int,input().split())
lis = [list(map(int,input().split())) for x in range(m)]
key = [-1,100001]
for x in lis:
    if key[0] < x[0]:
        key[0] = x[0]
    if key[1] > x[1]:
        key[1] = x[1]
print(len(range(key[0],key[1]+1)))


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


int main(){
    int n;
    cin >> n;
    vector<int> vec(n+1);
    for (int i=1;i<=n;i++){
        cin >> vec.at(i);
    }
    int temp =1;
    int count=0;
    for (int j=1;j <=n;j++){
        temp = vec.at(temp);
        count++;
        if (temp == 2) {
            break;
        }
        if (j == n) {
            count = -1;
        }
    }
    cout << count << endl;
}

Measured memory_bytes: 640
#include "bits/stdc++.h"
#define ll long long
#define mk make_pair
#define pb push_back
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pil pair<int,ll>
#define pli pair<ll,int>
using namespace std;
const int MAXN=1e5+9;
vector<int> g[MAXN];
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int n,m;
	cin>>n>>m;
	int h[n+1];
	for(int i=1;i<=n;i++)
	{
		cin>>h[i];
	}
	for(int i=1;i<=m;i++)
	{
		int x,y;
		cin>>x>>y;
		g[x].pb(y);
		g[y].pb(x);
	}
	int fans=0;
	for(int i=1;i<=n;i++)
	{
		bool ans=true;
		for(int j=0;j<g[i].size();j++)
		{
			if(h[i]<=h[g[i][j]])
			{
				ans=false;
				break;
			}
		}
		if(ans)
		{
			fans++;
		}
	}
	cout<<fans<<endl;
	return 0;
}

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

#define ALL(a) begin(a), end(a)
#define TPL template
#define TNM typename

using ll = long long;
using ull = unsigned long long;

TPL<TNM T> using vec = vector<T>;
TPL<TNM T> using vec2 = vec<vec<T>>;
TPL<TNM T> using vec3 = vec<vec2<T>>;
TPL<TNM T> using vec4 = vec<vec3<T>>;
TPL<TNM T> using vec5 = vec<vec4<T>>;

TPL<TNM T> inline istream& operator >> (istream& is, vector<T>& vec) { for (T& x : vec) is >> x; return is; }
TPL<TNM V, TNM H> void resize(vector<V>& _v, const H _h) { _v.resize(_h); }
TPL<TNM V, TNM H, TNM ... T> void resize(vector<V>& _v, const H& _h, const T& ... _t) { _v.resize(_h); for (auto& __v : _v) resize(__v, _t ...); }
TPL<TNM V, TNM T> TNM enable_if<!is_class<V>::value>::type fill(vector<V>& _v, const T& _t) { std::fill(ALL(_v), _t); }
TPL<TNM V, TNM T> TNM enable_if<is_class<V>::value>::type fill(vector<V>& _v, const T& _t) { for (auto& _e : _v) fill(_e, _t); }
TPL<TNM T> inline void UNIQUE(vector<T>& _v) { sort(ALL(_v)); _v.erase(unique(ALL(_v)), _v.end()); }
struct pre_ { pre_() { cin.tie(nullptr); ios::sync_with_stdio(false); cout << fixed << setprecision(6); } } pre__;

int main(void) {
	int r;
	cin >> r;
	cout << 3 * r * r << endl;
	return 0;
}

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

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

typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> pll;
typedef pair<ll, int> pli;

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

int H,W,K;
vector<int> hlines;
vector<int> wlines;
int chocolate[11][1001];

bool getWLines() {
    int left = 0;
    ll whiteChoco = 0;
    vector<ll> block(hlines.size());

    while(left < W) {
        int start = 0;
        for (int i=0; i<hlines.size(); i++) {
            int end = hlines[i];
            int block_tmp = 0;
            for (int j=start; j<end; j++) {
                if (chocolate[j][left]) block_tmp++;
            }
            if (block_tmp > K ) return false;
            if ((block[i] + block_tmp) <= K) block[i]+=block_tmp;
            else {
                wlines.push_back(left-1);
                left--;
                block.clear();
                block.resize(hlines.size());
                break;
            }       
            start = end;
        }
        left++;
    }
    return true;
}

int main() {
    // input, ready
    cin >> H >> W >> K;
    vector<string> S(H);
    for (int i=0; i<H; i++) cin >> S[i];
    memset(chocolate,0, sizeof(chocolate));
    ll total=0;
    for (int i=0; i<H; i++) {
        for (int j=0; j<W; j++) {
            chocolate[i][j] = S[i][j] - '0';
            if (chocolate[i][j]) total++;
        }
    }

    // K以下なら何もしなくてよい
    if (total <= K) {
        cout << 0 << endl;
        return 0;
    }

    // resolve
    // bit全探索
    ll ans = INF;
    ll hline_max = pow(2,H-1);
    for (int i=0; i<=hline_max; i++) {
        hlines.clear();
        wlines.clear();
        for (int j=0; j<(H-1); j++) {
            if (i & 1 << j) hlines.push_back(j+1);
        }
        hlines.push_back(H);
        if(getWLines()) ans = min(ans, (ll)(hlines.size() -1 + wlines.size()));
    }


    // output
    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define rrep(i,n) for(int (i)=((n)-1);(i)>=0;(i)--)
#define itn int
#define all(x) (x).begin(),(x).end()
#define F first
#define S second
using P = pair <int,int>; //to, cost
using WeightedGraph = vector<vector <P>>; //to cost
const long long INF = 1LL << 60;
const int MOD = 1000000007;
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; }
//https://www.creativ.xyz/dump-cpp-652/
#define repi(itr, ds) for (auto itr = ds.begin(); itr != ds.end(); itr++)
 
// vector
template <typename T>
istream &operator>>(istream &is, vector<T> &vec) {
    for (T &x : vec) is >> x;
    return is;
}
// pair
template <typename T, typename U>
ostream &operator<<(ostream &os, pair<T, U> &pair_var) {
    os << "(" << pair_var.first << ", " << pair_var.second << ")";
    return os;
}
// vector
template <typename T>
ostream &operator<<(ostream &os, const vector<T> &vec) {
    os << "{";
    for (int i = 0; i < vec.size(); i++) {
        os << vec[i] << (i + 1 == vec.size() ? "" : ", ");
    }
    os << "}";
    return os;
}
// map
template <typename T, typename U>
ostream &operator<<(ostream &os, map<T, U> &map_var) {
    os << "{";
    repi(itr, map_var) {
        os << *itr;
        itr++;
        if (itr != map_var.end()) os << ", ";
        itr--;
    }
    os << "}";
    return os;
}
// set
template <typename T>
ostream &operator<<(ostream &os, set<T> &set_var) {
    os << "{";
    repi(itr, set_var) {
        os << *itr;
        itr++;
        if (itr != set_var.end()) os << ", ";
        itr--;
    }
    os << "}";
    return os;
}
 
#define DUMPOUT cerr
 
void dump_func() {
    DUMPOUT << endl;
}
template <class Head, class... Tail>
void dump_func(Head &&head, Tail &&... tail) {
    DUMPOUT << head;
    if (sizeof...(Tail) > 0) {
        DUMPOUT << ", ";
    }
    dump_func(std::move(tail)...);
}

#ifdef DEBUG_
#define DEB
#define dump(...)                                                              \
    DUMPOUT << "  " << string(#__VA_ARGS__) << ": "                            \
            << "[" << to_string(__LINE__) << ":" << __FUNCTION__ << "]"        \
            << endl                                                            \
            << "    ",                                                         \
        dump_func(__VA_ARGS__)
#else
#define DEB if (false)
#define dump(...)
#endif

signed main(void) { cin.tie(0); ios::sync_with_stdio(false);
    int n; cin>>n;
    int ans = n+1;
    for(int i=1;i*i<=n;i++){
        if(n % i==0) chmin(ans,n/i + i);
    }
    cout<<ans - 2<<endl;
}


Measured memory_bytes: 256
import collections
def solve(n, k, a_list):

    counter = collections.Counter()

    for i in a_list:
        counter[i] += 1

    key_num = len(counter.keys())
    if key_num > k:
        tmp = sorted(counter.items(), key=lambda x: x[1])
        ans = sum([v for k, v in tmp[: key_num - k]])
    else:
        ans = 0

    return ans

if __name__ == "__main__":
    n, k = [int(i) for i in input().split()]
    a_list = [int(i) for i in input().split()]
    print(solve(n, k, a_list))


Measured memory_bytes: 40956
while true
    p, n = gets.chomp.split.map(&:to_i)
    break if [n, p] == [0, 0]
    rootp = Math.sqrt(p)
    left, right = Rational(rootp.floor, 1), Rational(rootp.ceil, 1)
    2.upto(n){|i|
        r = Rational((rootp * i).floor, i)
        r = Rational([r.numerator, n].min, i)
        left = r if left < r
        r = Rational((rootp * i).ceil, i)
        r = Rational([r.numerator, n].min, i)
        right = r if right > r && r > rootp
    }
    puts "#{right} #{left}"
end


Measured memory_bytes: 6888
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
#define INF (1<<30)
#define INFLL (1ll<<60)
typedef pair<int, int> P;
typedef pair<int, P> E;
#define MOD (1000000007ll)
#define l_ength size

void mul_mod(ll& a, ll b){
	a *= b;
	a %= MOD;
}

void add_mod(ll& a, ll b){
	b += MOD;
	a += b;
	a %= MOD;
}

int main(void){
	int n,i,a[12345],s,ans;
	cin >> n;
	while(n){
		s = 0; ans = 0;
		for(i=0; i<n; ++i){
			cin >> a[i];
			s += a[i];
			a[i] *= n;
		}
		for(i=0; i<n; ++i){
			if(a[i]<=s){
				++ans;
			}
		}
		cout << ans << endl;
		cin >> n;
	}
	return 0;
}



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

struct Puzzle{
	int f[9], space;
	string path;
	bool operator < (const Puzzle &p) const {
		for (int i = 0; i < 9; ++i){
			if (f[i] == p.f[i])continue;
			return f[i] > p.f[i];
		}
		return false;
	}
};

static const int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, -1, 0, 1};
static const char dir[4] = {'u', 'l', 'd', 'r'};

bool isTarget(Puzzle p)
{
	for (int i = 0; i < 9; ++i)if (p.f[i] != i + 1)return false;
	return true;
}

string bfs(Puzzle s)
{
	queue<Puzzle> Q;
	map<Puzzle, bool> V;
	Puzzle u, v;
	s.path = "";
	Q.push(s);
	V[s] = true;
	while (!Q.empty()){
		u = Q.front();
		Q.pop();
		if (isTarget(u))return u.path;
		int sx = u.space / 3, sy = u.space % 3;
		for (int r = 0; r < 4; ++r){
			int tx = sx + dx[r];
			int ty = sy + dy[r];
			if (tx < 0 || ty < 0 || tx >= 3 || ty >= 3)continue;
			v = u;
			swap(v.f[u.space], v.f[tx * 3 + ty]);
			v.space = tx * 3 + ty;
			if (!V[v]){
				V[v] = true;
				v.path += dir[r];
				Q.push(v);
			}
		}
	}
	return "unsolvable";
}

int main()
{
	Puzzle in;
	for (int i = 0; i < 9; ++i){
		cin >> in.f[i];
		if (in.f[i] == 0){
			in.f[i] = 9;
			in.space = i;
		}
	}
	string ans = bfs(in);
	cout << ans.size() << endl;
	return 0;
}


Measured memory_bytes: 30616
import bisect
INF = 10**15
A, B, Q = map(int, input().split())
s = [-INF] + [int(input()) for _ in range(A)] + [INF]
t = [-INF] + [int(input()) for _ in range(B)] + [INF]
for i in range(Q):
  x = int(input())
  sw = bisect.bisect_right(s, x)-1 #xより西で一番近い(同じ場所でもいい)神社の番号
  se = sw + 1 #xより東で一番近い神社の番号
  tw = bisect.bisect_right(t, x)-1
  te = tw + 1
  res = INF
  for S in [s[sw], s[se]]:
    for T in [t[tw], t[te]]:
      d1, d2 = abs(x-S) + abs(T-S), abs(x-T) + abs(S-T)
      res = min(res, d1, d2)
  print(res)



Measured memory_bytes: 12804
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N = LIST()
print("YES" if sorted(N)==[1, 4, 7, 9] else "NO")


Measured memory_bytes: 10600
a = []
a = gets.split.map(&:to_i)
cnt = 0
for i in 0..a[0]
  for j in 0..a[0]
    if a[1] - i - j >= 0 && i <= a[0] && j<=a[0] && (a[1] - i - j) <= a[0]
      cnt = cnt +1
    end
  end
end
puts cnt

Measured memory_bytes: 1788
#include <iostream>
#include <algorithm>
#include <vector>
#include <iomanip>
#include <map>
#include <queue>

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

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

int main() {
    int n;
    while(cin >> n, n){
        for (int i = 0; i < 9; ++i) {
            int m;
            cin >> m;
            n -= m;
        }
        cout << n << "\n";
    }
    return 0;
}



Measured memory_bytes: 3092
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
int main()
{
  ll h,w;
  cin>>h>>w;
  if(h==1 || w==1)
    cout<<1<<"\n";
  else
  cout<<(h*w +1)/2<<"\n";
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define REP(i, n) for(int i = 0; i < n; i++)
#define REPR(i, n) for(int i = n - 1; i >= 0; i--)
#define FOR(i, m, n) for(int i = m; i <= n; i++)
#define FORR(i, m, n) for(int i = m; i >= n; i--)
#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end());
#define ll long long
#define pb(a) push_back(a)

ll mod = 1e9 + 7;

int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  ll n;
  cin >> n;
  ll a[n], b[n];
  REP(i, n) cin >> a[i];
  REP(i, n) cin >> b[i];

  ll ap = 0, bp = 0, d;
  
  REP(i, n){
    d = b[i] - a[i];
    if(d > 0) ap += d / 2;
    else bp += -d;
  }
  if(ap >= bp) cout << "Yes" << endl;
  else cout << "No" << endl;
  return 0;
}


Measured memory_bytes: 384
#include <bits/stdc++.h>
using namespace std;
const int vertices=1e5+2;
int dp[vertices];
vector<int> graph[vertices];
// top down memoization
int solve(int src){
    if(dp[src]!=-1)
        return dp[src];
    if(graph[src].size()==0)// No children
        return dp[src]=0;
    // else return max path length children
    int maxLength=0;
    for(int child:graph[src]){
        int temp=solve(child);
        maxLength=max(maxLength,temp);
    }
    return dp[src]=1+maxLength; // memoizing and returning 
}



int main() {
	for(int i=0;i<vertices;++i)
        dp[i]=-1;
    int n=0;cin>>n;int m;cin>>m;
    int src=0;int des=0;
    for(int i=0;i<m;++i){
        cin>>src>>des;
        graph[src].push_back(des);
    }
    int ans=0;
    for(int src=1;src<=n;++src){
        int temp=solve(src);
        //cout<<temp<<endl;
        ans=max(ans,temp);
    }
    cout<<ans<<endl;
    return 0;
}


Measured memory_bytes: 8192
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < n; i++)
#define MOD 1000000007
#define MOD2 998244353
#define INF MOD
#define LINF (1LL<<60)
#define EPS (1e-10)
typedef long long Int;
typedef pair<Int, Int> P;

int main() {
    int n;
    cin >> n;
    Int mx = 0;
    Int ans = 0;
    rep(i,n) {
        Int a;
        cin >> a;
        if (mx > a) {
            ans += mx - a;
        }
        mx = max(mx, a);
    }
    cout << ans << endl;
}

Measured memory_bytes: 3604
# coding:utf-8

import sys
import math
import time
#import numpy as np
import collections
from collections import deque
from collections import Counter
import queue
import copy
import bisect
import heapq
import itertools



#sys.setrecursionlimit(10**7)
#N, Q = map(int, input().split())
#G = [list(input()) for i in range(H)]
#INF = V * 10001
#A = [int(i) for i in input().split()]
#AB = [list(map(int, input().split())) for _ in range(K)]

N, M, X = map(int,input().split())
Book = [list(map(int, input().split())) for _ in range(N)]
Alg = [0]*M
money = 10**8
temp = 0
flag = True
ans = 0

for i in range(2**N):
    for j in range(N):
        if((i >> j) & 1):
            temp += Book[j][0]
            for k in range(M):
                Alg[k] += Book[j][k+1]
    for l in range(M):
        #print(Alg)
        if(Alg[l] < X):
            flag = False
            break
    if(flag):
        money = min(money,temp)
    flag = True
    temp = 0
    for m in range(len(Alg)):
        Alg[m] = 0

if(money==10**8):
    print(-1)
else:
    print(money)


Measured memory_bytes: 70668
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main(){
  ll a,b,c,d;
  cin >> a >> b >> c >> d;
  ll ans = -1e+18;
  ans = max(ans, a * c);
  ans = max(ans, a * d);
  ans = max(ans, b * c);
  ans = max(ans, b * d);
  cout << ans << endl;
}

Measured memory_bytes: 3632
from collections import deque

H,W=map(int,input().split())
S=[input() for _ in range(H)]

ans=[]
for i in range(H):
  for j in range(W):
    if S[i][j]=="#":
      continue
    queue=deque([[i,j]])
    visited=[[-1]*W for _ in range(H)]
    visited[i][j]=0
    while queue:
      y,x=queue.popleft()
      for k,l in ([1,0], [-1,0], [0,1], [0,-1]):
        new_y,new_x=y+k,x+l
        if new_y<0 or new_x<0 or new_y>=H or new_x>=W:
          continue
        elif S[new_y][new_x]=="." and visited[new_y][new_x]==-1:
          visited[new_y][new_x]=visited[y][x]+1
          queue.append([new_y,new_x])
    L=0
    for m in range(H):
      val=max(visited[m])
      L=max(L,val)
    ans.append(L)
print(max(ans))

Measured memory_bytes: 3316
/*
神题
巧妙建图
不存在欧拉回路-->无解
构造欧拉回路，为每条边定向，使每个点入度=出度
利用度数相等，确保每个点子树abs=1，以此填数
*/
#include<cstdio>
#include<cstring>
#include<algorithm>
#define N 200010
using namespace std;
struct edge{int x, y, f, v, next;}a[N*3];
int n, l, p[N], S, x, du[N], q[N];
inline void add(int x, int y){
	a[++l].x=x; a[l].y=y; a[l].f=0; a[l].next=p[x]; p[x]=l;
	du[x]++;
}
inline void dfs(int x){
	for(int i=q[x]; i; i=q[x]){
		q[x]=a[i].next;
		if(!a[i].f){
			a[i].f=a[i^1].f=1;
			dfs(a[i].y);
			a[i].v=0; a[i^1].v=1;
		}
	}
}
int main(){
	scanf("%d", &n);
	l=1; memset(p, 0, sizeof(p)); S=n*2+1;
	memset(du, 0, sizeof(du));
	for(int i=1; i<=n; i++){
		scanf("%d", &x);
		if(x==-1){add(i, S); add(S, i);}
		else{add(i, x); add(x, i);}
	}
	for(int i=1; i<=n; i++){
		scanf("%d", &x);
		if(x==-1){add(n+i, S); add(S, n+i);}
		else{add(n+i, n+x); add(n+x, n+i);}
	}
	for(int i=1; i<=n; i++){
		if((du[i]&1)!=(du[n+i]&1)){printf("IMPOSSIBLE"); return 0;}
		if(du[i]&1){add(i, n+i); add(n+i, i); du[i]--; du[n+i]--;}
	}
	memcpy(q, p, sizeof(q)); dfs(S);
	printf("POSSIBLE\n");
	for(int i=1; i<=n; i++){
		if(!(du[i]&1))printf("0");
		else{
			for(int j=p[i]; j; j=a[j].next)if(a[j].y==n+i){
				if(a[j].v)printf("1");
				else printf("-1");
			}
		}
		if(i<=n-1)printf(" ");
	}
	return 0;
}

Measured memory_bytes: 22272
import java.util.*;
public class Main{
    public static void main(String[]args){
        Scanner sc=new Scanner(System.in);
        int N=sc.nextInt();
        int sum=0;
        for(int i=0;i<N;i++){
            int l=sc.nextInt();
            int r=sc.nextInt();
            sum=sum+r-l+1;
        }
        System.out.println(sum);
        
        
     
    }
}

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

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


Measured memory_bytes: 256
s = input()
for _ in range(int(input())):
	o = list(map(str, input().split()))
	a = int(o[1])
	b = int(o[2])
	if o[0] == "print":
		print(s[a:b+1])
	elif o[0] == "reverse":
		s = s[:a] + s[a:b+1][::-1] + s[b+1:]
	else:
		s = s[:a] + o[3] + s[b+1:]



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

using namespace std;

int main(){
  int32_t N, M;
  vector<int32_t> X;
  int32_t ans;

  cin >> N >> M;
  
  int32_t Xsum = 0;  
  for (int i=0; i<M; i++) {
	int Xi;
	cin >> Xi;
	X.push_back(Xi);
	Xsum += Xi;
  }

  sort(X.begin(), X.end());
  
  vector<int32_t> dX;
  int32_t dXsum = 0;
  for (int i=1; i<M; i++) {
	int dXi = X.at(i) - X.at(i - 1);
	dX.push_back(dXi);
	dXsum += dXi;
  }

  sort(dX.begin(), dX.end(), greater<int32_t>());

  ans = dXsum;
  for (int i=0; i<min((N - 1), (M - 1)); i++) {
	ans -= dX.at(i);
	if (ans < 1) break;
  }

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

Measured memory_bytes: 1400
#include <bits/stdc++.h>
using namespace std;
int main(){
    int n;int64_t k;cin>>n>>k;
    vector<int> M(n+1);
    set<int> D;D.insert(1);
    for (int i = 1; i < n+1; i++) {
        cin>>M.at(i);
    }
    int mp=1;
    int count =0;
    int cou=0;
    while(true){
        mp=M.at(mp);
        if(D.count(mp)){
            cou++;
            break;
        }else{cou++;D.insert(mp);}
    }
    if(k<=cou){
        mp=1;
        for (int i = 0; i < k; i++) {
            mp=M.at(mp);
        }
        cout<<mp<<endl;
    }else{
        int dd=mp;
    while(true){
        mp=M.at(mp);
        if(mp==dd){
            count++;
            break;
        }else{count++;}
    }
    k=(k-cou)%count;
    mp=dd;
        for (int i = 0; i < k; i++) {
            mp=M.at(mp);
        }
        cout<<mp<<endl;
    }
    
}

Measured memory_bytes: 13136
#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;
using ll = long long;

struct HLD {
  vector<int> label, parent, head;

  HLD(const vector<vector<int>> &g) : label(g.size()), parent(g.size()), head(g.size()) {
    const int n = g.size();
    vector<int> size(n, 1);
    auto dfs = [&](auto dfs, int u, int p) -> void {
      for (int v : g[u]) if (v != p) {
        dfs(dfs, v, u);
        size[u] += size[v];
      }
    };
    dfs(dfs, 0, -1);
    int k = 0;
    auto dfs2 = [&](auto dfs, int u, int p, int h) -> void {
      label[u] = k++;
      head[u] = h;
      parent[u] = p;
      for (int v : g[u]) if (v != p && size[v] * 2 >  size[u]) dfs(dfs, v, u, h);
      for (int v : g[u]) if (v != p && size[v] * 2 <= size[u]) dfs(dfs, v, u, v);
    };
    dfs2(dfs2, 0, -1, 0);
  }

  int lca(int u, int v) {
    for (;;) {
      if (label[u] > label[v]) swap(u, v);
      if (head[u] == head[v]) return u;
      v = parent[head[v]];
    }
  }
};

int main() {
  cin.tie(nullptr);
  ios::sync_with_stdio(false);
  int n, q;
  cin >> n >> q;
  vector<vector<int>> g(n);
  struct edge {
    int v, c, w;
  };
  vector<vector<edge>> g2(n);
  rep(i, n-1) {
    int u, v, c, w;
    cin >> u >> v >> c >> w;
    u--;
    v--;
    g[u].push_back(v);
    g[v].push_back(u);
    g2[u].push_back((edge){v, c, w});
    g2[v].push_back((edge){u, c, w});
  }
  HLD hld(g);
  vector<ll> ans(q);
  struct query {
    int x, y;
    int coeff;
    int i;
  };
  vector<vector<query>> qs(n);
  rep(i, q) {
    int x, y, u, v;
    cin >> x >> y >> u >> v;
    u--;
    v--;
    qs[u].push_back((query){x, y, 1, i});
    qs[v].push_back((query){x, y, 1, i});
    qs[hld.lca(u, v)].push_back((query){x, y, -2, i});
  }
  ll dist = 0;
  vector<ll> distc(n);
  vector<ll> cnt(n);
  auto dfs = [&](auto dfs, int u, int p) -> void {
    for (query q : qs[u]) {
      ans[q.i] += q.coeff * (dist - distc[q.x] + cnt[q.x] * q.y);
    }
    for (edge e : g2[u]) {
      if (e.v == p) continue;
      distc[e.c] += e.w;
      cnt[e.c]++;
      dist += e.w;
      dfs(dfs, e.v, u);
      dist -= e.w;
      cnt[e.c]--;
      distc[e.c] -= e.w;
    }
  };
  dfs(dfs, 0, -1);
  rep(i, q) {
    cout << ans[i] << '\n';
  }
}


Measured memory_bytes: 53236
Imports System.Collections.Generic
Imports System.Console

Module Program
    Sub Main()
        Dim n As Integer = NextInt()
        Dim a As Integer = NextInt()
        Dim b As Integer = NextInt()

        If (b - a) Mod 2 = 0 Then
            WriteLine("Alice")
        Else
            WriteLine("Borys")
        End If
    End Sub

    Function NextInt() As Integer
        Return CInt(NextString())
    End Function

    Function NextString() As String
        Dim result As New List(Of Char)
        Do
            Dim tmp As Integer = Read()
            If tmp < 0 Then Exit Do
            Dim nextChar As Char = Chr(tmp)

            If Not Char.IsWhiteSpace(nextChar) Then
                result.Add(nextChar)
            ElseIf nextChar <> vbCr Then
                Exit Do
            End If
        Loop
        Return New String(result.ToArray())
    End Function
End Module


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

using namespace std;
using ll = long long;
using ld = long double;

#define int long long
signed main(){
//int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n;
    cin >> n;
    int a[n];
    for(int i = 0; i < n; i++) {
        cin >> a[i];
    }
    vector<int> b(n+1);
    b[0]=0;
    for(int i = 0; i < n; i++) {
        b[i+1]=a[i]+b[i];
    }

//    for(int i = 0; i <= n; i++) {
//        cout << b[i] << " ";
//    }

    sort(b.begin(),b.end());
    map<int,int> cnt;
    for(int i = 0; i <= n; i++) {
        cnt[b[i]]++;
    }
    int ans=0;
    for(auto itr = cnt.begin(); itr !=cnt.end(); itr++) {
        int tmp=itr->second;
        ans+=tmp*(tmp-1)/2;
    }
    cout << ans << "\n";

    return 0;
}

Measured memory_bytes: 18676
N, M = map(int, input().split())
req = [list(map(int, input().split())) for i in range(M)]
req.sort(key = lambda x:(x[0], -x[1]))
ans = 0
left = 0
right = 0
for i in range(M):
    if req[i][0] >= right:
        ans += 1
        left, right = req[i][0], req[i][1]
    else:
        left = req[i][0]
        right = min(req[i][1], right)

print(ans)


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

#include<cstdio>
#define r(i,n) for(int i=0;i<n;i++)

int main(void){
  vector<int> a(3);
  r(i,3)cin>>a.at(i);

  sort(a.begin(),a.end());
  int sum=0;
  r(i,2){
    sum+=a.at(i+1)-a.at(i);
  }
  cout<<sum<<endl;




return 0;}


Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <vector>
#include <stack>
#define rep(i, n) for(i = 0; i < (n); i++)
using namespace std;

const int DEPTH = 18;
const int INF = 1e+8;
struct SegMin {
	int d[1 << (1 + DEPTH)];
	SegMin() { int i; rep(i, (1 << (1 + DEPTH))) d[i] = INF; }
	void update(int pos, int x) {
		pos += (1 << DEPTH) - 1;
		d[pos] = x;
		while (pos > 0) {
			pos = (pos - 1) / 2;
			d[pos] = min(d[pos * 2 + 1], d[pos * 2 + 2]);
		}
	}
	int query(int l, int r, int a = 0, int b = (1 << DEPTH), int id = 0) {
		if (a >= r || b <= l) return INF;
		if (l <= a && b <= r) return d[id];
		int vl = query(l, r, a, (a + b) / 2, id * 2 + 1);
		int vr = query(l, r, (a + b) / 2, b, id * 2 + 2);
		return min(vl, vr);
	}
};

struct SegMax {
	int d[1 << (1 + DEPTH)];
	SegMax() { int i; rep(i, (1 << (1 + DEPTH))) d[i] = -INF; }
	void update(int pos, int x) {
		pos += (1 << DEPTH) - 1;
		d[pos] = x;
		while (pos > 0) {
			pos = (pos - 1) / 2;
			d[pos] = max(d[pos * 2 + 1], d[pos * 2 + 2]);
		}
	}
	int query(int l, int r, int a = 0, int b = (1 << DEPTH), int id = 0) {
		if (a >= r || b <= l) return -INF;
		if (l <= a && b <= r) return d[id];
		int vl = query(l, r, a, (a + b) / 2, id * 2 + 1);
		int vr = query(l, r, (a + b) / 2, b, id * 2 + 2);
		return max(vl, vr);
	}
};

struct UF {
	int par[200000];
	int n;
	void init(int n, int k) {
		int i;
		rep(i, n) { par[i] = i; }
		this->n = n - k + 1;
	}
	int root(int x) {
		if (par[x] == x) return x;
		return par[x] = root(par[x]);
	}
	void unit(int x, int y) {
		x = root(x);
		y = root(y);
		if (x != y) {
			par[x] = y;
			n--;
		}
	}
};

int n, k;
int p[200000];
SegMin segMin;
SegMax segMax;
UF uf;

signed main() {
	int i, j;
	
	cin >> n >> k;
	rep(i, n) cin >> p[i];
	rep(i, n) segMin.update(i, p[i]);
	rep(i, n) segMax.update(i, p[i]);
	
	uf.init(n, k);
	
	for (i = 0; i < n; ) {
		int max1 = -INF;
		int max2 = -INF;
		for (j = i + 1; j < n - k + 1 && j - i < k; j++) {
			if (max1 > p[j - 1]) { break; }
			max1 = p[j - 1];
			if (max2 > p[j + k - 1]) { break; }
			max2 = p[j + k - 1];
			if (max1 > segMin.query(j, j + k)) { break; }
			if (max2 < segMax.query(i, i + k)) { break; }
			//cout << "unit(" << i << ", " << j << ")" << endl;
			uf.unit(i, j);
			//cout << "uf.n = " << uf.n << endl;
		}
		//cout << "i, j = " << i << ", " << j << endl;
		i = j;
	}
	
	int len = 1;
	vector<int> vec;
	for (i = 1; i < n; i++) {
		if (p[i - 1] > p[i]) {
			len = 1;
		}
		else {
			len++;
		}
		if (len >= k) {
			vec.push_back(i - k + 1);
		}
	}
	
	for (i = 0; i + 1 < vec.size(); i++) {
		uf.unit(vec[i], vec[i + 1]);
		//cout << "uf.unit2(" << vec[i] << ", " << vec[i + 1] << ")" << endl;
	}
	
	cout << uf.n << endl;
	return 0;
}

Measured memory_bytes: 7160
using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using static System.Console;

class Program
{
    static void Main(string[] args)
    {
        var DTS = ReadLine().Split(' ').Select(s => int.Parse(s)).ToArray();
        var (D, T, S) = (DTS[0], DTS[1], DTS[2]);
        
        var ans = (D <= T * S) ? "Yes" : "No";

        WriteLine(ans);
    }
}


Measured memory_bytes: 28212
#include <bits/stdc++.h>
using namespace std ;
#define ll long long
inline int D(){
    int t ;
    scanf( "%d" , &t ) ;
    return t ;
}
inline ll LLD(){
    ll t ;
    scanf( "%lld" , &t ) ;
    return t ;
}


//#########################################

int a[5]={1,4,7,9,10};
int x;
bool can(int i){

    return (a[i]<=x);

}

int main() {

char a[3][3];
for(int i=0;i<3;i++){
    for(int j=0;j<3;j++){
        cin>>a[i][j];
        if(i==j){
            cout<<a[i][j];

        }

    }



}


}


Measured memory_bytes: 256
s=input()
k=int(input())
count = 0

if s[0] != "1":
	result = s[0]
else:
	for i in range(len(s)):
		if s[i] == "1":
			count +=1
		else:
			result = s[i]
			break
	if k > count:
		result = s[i]
	else:
		result = 1

print(result)

Measured memory_bytes: 3060
from collections import deque

n, m = map(int, input().split())

roads = [[] for i in range(n)]

answers = [0 for i in range(n)]

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

d = deque()
d.append(0)

seen = {}
will_seen = {}

while len(seen) < n:
    pos = d.popleft()
    if seen.get(pos, None) is not None:
        continue
    else:
        for next_pos in roads[pos]:
            if will_seen.get(next_pos, None) is None:
                d.append(next_pos)
                answers[next_pos] = pos + 1
                will_seen[next_pos] = 1
            seen[pos] = 1

print("Yes")
for ans in answers[1:]:
    print(ans)

Measured memory_bytes: 51584
function Main(input) {
	input = input.trim(); 
  	input = input.split("\n");

  	var member = input[0];

	var imput_tmp = input[1].split(" ");
	var days = parseInt(imput_tmp[0], 10);
 	var nokori = parseInt(imput_tmp[1], 10);

  	var chocolate_cnt = 0;
  	var eatday;
	for (var i = 2; i < input.length + 1; i++) {
      	
		for (var j = 0; j < days + 1; j++) {
        	eatday = input[i] * j + 1;
			if (eatday <= days) {
              chocolate_cnt += 1;
            } else {
            	break;
            }
		}

    }  

	console.log(chocolate_cnt + nokori);

}

//*この行以降は編集しないでください（標準入出力から一度に読み込み、Mainを呼び出します）
Main(require("fs").readFileSync("/dev/stdin", "utf8"));

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

int main(){
  ll x;
  cin >> x;
  ll ans = 0;
  ans += 1000*(x/500);
  x -= 500*(x/500);
  ans += 5*(x/5);
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 256
import java.util.*;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		String N = sc.next();
		int K = sc.nextInt();
		System.out.println(solve(N, K));
//		for(int i=1; i<1000000; i++) {
//			String N = String.valueOf(i);
//			for(int K=1; K<=3; K++) {
//				long ans1 = solve(N, K);
//				long ans2 = solve2(N, K);
//				if(ans1 != ans2) {
//					System.out.println("N=" + N);
//					System.out.println("K=" + K);
//					System.out.println("ans1=" + ans1);
//					System.out.println("ans2=" + ans2);
//					return;
//				}
//			}
//		}
		
		sc.close();
	}
	
	static long solve2(String N, int K) {
		int max = Integer.valueOf(N);
		int ans = 0;
		for(int i=1; i<=max; i++) {
			int v = i;
			int cnt = 0;
			while(v>0) {
				if(v%10>0)
					cnt++;
				v /= 10;
			}
			if(cnt==K)
				ans++;
		}
		return ans;
	}
	
	static long solve(String N, int K) {
		
		int L = N.length();
		int[] d = new int[L];
		for(int i=0; i<L; i++)
			d[i] = N.charAt(i)-'0';
		
		long ans = 0;
		
		int i2 = -1;
		for(int i=1; i<L; i++) {
			if(d[i]!=0) {
				i2 = i;
				break;
			}
		}
		int i3 = -1;
		if(i2>0) {
			for(int i=i2+1; i<L; i++) {
				if(d[i]!=0) {
					i3 = i;
					break;
				}
			}
		}
		
		if(K==1) {
			// 12345
			// x0000
			ans += d[0];
			// .x000
			ans += 9*(L-1);
			// 20345
			// 20300
		} else if(K==2) {
			if(i2 > 0) {
				ans += d[i2];
				ans += 9*(L-i2-1);
			}
			if(d[0]>1 && L>=2) {
				ans += (d[0]-1) * 9 * (L-1);
			}
			if(L>2) {
				ans += 9*9*(L-1)*(L-2)/2;
			}
		} else if(K==3) {
			if(i3 > 0) {
				ans += d[i3];
				ans += 9*(L-i3-1);
			}
			if(i2 > 0) {
				ans += (d[i2]-1) * 9*(L-i2-1);
				ans += 9 * 9*(L-i2-1)*(L-i2-2)/2;
			}
			if(d[0]>1 && L>=3) {
				ans += (d[0]-1) * 9 * 9*(L-1)*(L-2)/2;
			}
			if(L>3) {
				ans += 9*9*9*(L-1)*(L-2)*(L-3)/6;
			}
		}
		
		return ans;
	}

}



Measured memory_bytes: 21844
# https://beta.atcoder.jp/contests/abc111/tasks/abc111_a
def solve():
    anstr = ""
    s = input()
    for ch in s:
        if ch is '1':
            anstr += '9'
        elif ch is '9':
            anstr += '1'
        else:
            anstr += ch
    print(anstr)


if __name__ == '__main__':
    solve()


Measured memory_bytes: 2940
#include <iostream>
#include <set>

using namespace std;

int main(int argc, char* argv[])
{
    int K, S; cin >> K >> S;

    set<int> Z;
    for (int i = 0; i <= K; i++) {
      Z.insert(S-i);
    }
    
    int cnt = 0;
    for (int x = 0; x <= K; x++) {
        for (int y = 0; y <= K; y++) {
	  if (Z.find(x+y) != Z.end()) {
	    cnt++;
	  }
        }
    } 
    cout << cnt << endl;
    return 0;
}


Measured memory_bytes: 384
#include <bits/stdc++.h>
#define F first
#define S second
using namespace std;
 
typedef long long ll;
typedef vector<ll> vi;
typedef vector<vi> vvi;
typedef vector<vvi> vvvi;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef vector<vii> vvii;
typedef vector<vvvi> vvvvi;

const ll z = 127, MOD = 1e9+7;
const int maxlen = 1e6;
ll Zpow[maxlen+1];

struct RollingHash
{
	vector<ll> suffixHash;

	RollingHash(string &S)
	{
		int N = S.length();
		suffixHash.resize(N+1,0);
		for(int i = N-1; i >= 0; --i)
			suffixHash[i] = (z*suffixHash[i+1]+S[i])%MOD;
	}

	ll hash(int i, int len)
	{
		return (suffixHash[i]-Zpow[len]*suffixHash[i+len]%MOD+MOD)%MOD;
	}
};

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    Zpow[0] = 1; for(int i = 1; i <= maxlen; ++i) Zpow[i] = z*Zpow[i-1]%MOD;

    int n;
    string s;
    cin >> n >> s;
    map<int, int> letters;
    for (int i = 0; i < n; ++i) letters[s[i]]++;
    bool f = false;
    for (auto v : letters) {
        if (v.S > 1) f = true;
    }
    if (!f) {
        cout << "0\n";
        return 0;
    }
    RollingHash rh(s);
    int low = 1, high = n;
    while (low < high) {
        int mid = (low + high) / 2;
        map<ll, int> L, R;
        for (int i = 0; i < n-mid+1; ++i) {
            ll hash = rh.hash(i, mid);
            if (L.find(hash) == L.end()) L[hash] = i;
            R[hash] = i;
        }
        bool flag = false;
        for (auto v : L) {
            if (v.S <= R[v.F]-mid) flag = true;
        }
        if (flag) low = mid+1;
        else high = mid;
    }
    cout << high-1 << "\n";
    return 0;
}

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

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<ll, ll> P;

#define EACH(i,a) for (auto& i : a)
#define FOR(i,a,b) for (ll i=(a);i<(b);i++)
#define RFOR(i,a,b) for (ll i=(b)-1;i>=(a);i--)
#define REP(i,n) for (ll i=0;i<(n);i++)
#define RREP(i,n) for (ll i=(n)-1;i>=0;i--)
#define debug(x) cout<<#x<<": "<<x<<endl
#define pb push_back
#define ALL(a) (a).begin(),(a).end()

const ll linf = 1e18;
const int inf = 1e9;
const double eps = 1e-12;
const double pi = acos(-1);

template<typename T>
istream& operator>>(istream& is, vector<T>& vec) {
	EACH(x,vec) is >> x;
	return is;
}
template<typename T>
ostream& operator<<(ostream& os, vector<T>& vec) {
	REP(i,vec.size()) {
		if (i) os << " ";
		os << vec[i];
	}
	return os;
}
template<typename T>
ostream& operator<<(ostream& os, vector< vector<T> >& vec) {
	REP(i,vec.size()) {
		if (i) os << endl;
		os << vec[i];
	}
	return os;
}

typedef complex<ld> Point;
namespace std {
	bool operator<(const Point &lhs, const Point &rhs) {
		if (lhs.real() < rhs.real() - eps) return true;
		if (lhs.real() > rhs.real() + eps) return false;
		return lhs.imag() < rhs.imag();
	}
}

class Line {
public:
	Point a, b;
	Line () : a(Point(0, 0)), b(Point(0, 0)) {}
	Line (Point a, Point b) : a(a), b(b) {}
};
ld cross(Point a, Point b) {
	return imag(conj(a) * b);
}
Point is_ll (Line s, Line t) {
	Point sv = s.b - s.a, tv = t.b - t.a;
	assert(cross(sv, tv) != 0);
	return s.a + sv * cross(tv, t.a - s.a) / cross(tv, sv);
}
bool isis_sp (Line s, Point p) {
	return (abs(s.a - p) + abs(s.b - p) - abs(s.b - s.a) < eps);
}


int main() {
	std::ios::sync_with_stdio(false);
	std::cin.tie(0);
	int N;
	while (cin >> N, N) {
		vector<Line> l;
		REP(i,N) {
			int x1, y1, x2, y2; cin >> x1 >> y1 >> x2 >> y2;
			l.pb({Point(x1, y1), Point(x2, y2)});
		}
		int ans = 1;
		REP(i,N) {
			set<Point> s;
			REP(j,i) {
				if (abs( cross(l[i].b-l[i].a, l[j].b-l[j].a) ) < eps) continue;
				Point p = is_ll(l[i], l[j]);
				if (p == l[i].a || p == l[i].b || p == l[j].a || p == l[j].b) continue;
				if (isis_sp(l[i], p) && isis_sp(l[j], p)) {
					s.insert(p);
				}
			}
			ans += s.size()+1;
		}
		cout << ans << endl;
	}
}

Measured memory_bytes: 3208