akhauriyash/Code-Regression huggingface dataset:
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
#include<set>
#include<string>
#include<stack>
#include<cstdio>
#include<cmath>
using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int,int> P;
typedef pair<int,P> P1;

#define fr first
#define sc second
#define mp make_pair
#define pb push_back
#define rep(i,x) for(int i=0;i<x;i++)
#define rep1(i,x) for(int i=1;i<=x;i++)
#define rrep(i,x) for(int i=x-1;i>=0;i--)
#define rrep1(i,x) for(int i=x;i>0;i--)
#define sor(v) sort(v.begin(),v.end())
#define rev(s) reverse(s.begin(),s.end())
#define lb(vec,a) lower_bound(vec.begin(),vec.end(),a)
#define ub(vec,a) upper_bound(vec.begin(),vec.end(),a)
#define uniq(vec) vec.erase(unique(vec.begin(),vec.end()),vec.end())
#define mp1(a,b,c) P1(a,P(b,c))

const int INF=1000000000;
const int dir_4[4][2]={{1,0},{0,1},{-1,0},{0,-1}};
const int dir_8[8][2]={{1,0},{1,1},{0,1},{-1,1},{-1,0},{-1,-1},{0,-1},{1,-1}};

static int n,q;
static string s;
static char t[200010],d[200010];

bool f(int loc,int T){
	//cout << loc << " " << T << endl;
	if(loc <= -1 || loc >= n)return true;
	if(T == q+1)return false;
	if(t[T] == s[loc]){
		if(d[T] == 'L')loc--;
		else loc ++;
	}
	return f(loc,T+1);
}

int main(){
	scanf("%d%d",&n,&q);
	cin >> s;
	rep1(i,q){
		scanf("\n");
		scanf("%s %s",&t[i],&d[i]);
	}
	
	int l = 0, r = n;
	while(l < r){
		int m = (l+r+1)/2;
		if(f(m-1,1))l = m;
		else r = m-1;
	}
	int l_ = 1, r_ = n+1;
	while(l_ < r_){
		int m = (l_+r_)/2;
		if(f(m-1,1))r_ = m;
		else l_ = m+1;
	}
	if(l >= l_)cout << 0 << endl;
	else cout << l_-1-l << endl;
}

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

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

int main() {
  int a,b,c;
  cin>>a>>b>>c;
  if(c%max(a,b)==0){
    cout<<c/max(a,b)<<endl;
  }
  else{
    cout<<(c/max(a,b))+1<<endl;
  }
}

Measured memory_bytes: 256
import java.util.*;
import java.math.*;

class Main{
	public static void main(String[] args){
		Solve s = new Solve();
		s.solve();
	}	
}

class Solve{
	Solve(){}
	
	Scanner in = new Scanner(System.in);

	void solve(){

		String[] k = {"Mts","Fks","Nyt","Asg","Ggs","Gok","Sai","Sei","Kan","Ko","Jou","Jo","Gai","Kei","Cho","Oku","Man", ""};
		BigInteger zero = new BigInteger("0");

		while(in.hasNext()){
			String s = in.next();
			int n = in.nextInt();

			if(s.equals("0") && n == 0) return;

			BigInteger m = new BigInteger(s);

			m = m.pow(n);
			s = new String(m.toString());

			int d = (s.length() - 1) / 4, a = s.length() % 4;

			//System.out.println(d + " " + a);

			StringBuilder temp = new StringBuilder();
			StringBuilder ans = new StringBuilder();

			for(int i = 0; i < s.length(); i++){
				temp.append(s.charAt(i));
				if((i != 0 && (i - a) % 4 == 3) || (i < a && i == a - 1)){
					while(temp.length() > 0 && temp.charAt(0) == '0'){
						temp.deleteCharAt(0);
					}
					if(temp.length() > 0) {
						ans.append(temp.toString() + k[k.length - 1 - d + i / 4]);
					}
					temp = new StringBuilder();
				}
			}

			System.out.println(ans.toString());
		}
	}
	
}

// while(in.hasNext()){
		// 	int n = in.nextInt();
		// 	if(n == 0) return;
			
		// }

Measured memory_bytes: 26692
#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 r;
  cin >> r;
  if (r < 1200) cout << "ABC" << endl;
  else if (1200 <= r && r < 2800) cout << "ARC" << endl;
  else cout << "AGC" << endl;
  return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){
	int n;
  	cin>>n;
  	vector<int>vec(n);
  	vector<int>vec2(n);
  	for(int i=0;i<n;i++){
    	cin>>vec.at(i);
      	vec2.at(i)=vec.at(i);
    }
  	sort(vec.begin(),vec.end());
  	for(int i=0;i<n;i++){
    	if(vec2[i]==vec[n-1]){
        	 cout<<vec[n-2]<<endl;
          	
        }
      	else{
        	cout<<vec[n-1]<<endl;
        }
    }
}

Measured memory_bytes: 3200
S = input()
flag = True
if S[0] == 'A':
    pass
else:
    flag = False

cnt = 0
for i in range(len(S)-3):
    if S[2+i] =='C':
        cnt += 1

if cnt == 1:
    pass
else:
    flag=False
cnt = 0
for i in range(len(S)):
    if S[i].islower():
        cnt += 1
if cnt == len(S)-2:
    pass
else:
    flag=False
if flag:
    print('AC')
else:
    print('WA')

Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
using vi=vector<int>;
using vvi=vector<vi>;
using vs=vector<string>;
using msi=map<string,int>;
using mii=map<int,int>;
using pii=pair<int,int>;
using vlai=valarray<long long>;
using vlad=valarray<double>;
using ll=long long;
#define rep(i,n) for(int i=0;i<n;i++)
#define range(i,s,n) for(int i=s;i<n;i++)
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define fs first
#define sc second
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define INF 1e9
#define EPS 1e-9

double msum(vlad a,vlad b){
    return (double)((a*b).sum());
}
double msum(vlad a){
    return (double)((a*a).sum());
}

double dot(vlad a,vlad b){
    return msum(a,b)/sqrt(msum(a))/sqrt(msum(b));
}

int main(){
    string s;
    while(cin>>s,s!="#"){
        vvi f(1);
        for(auto c:s){
            if(c=='b')f.back().pb(1);
            else if(c=='/')f.eb();
            else{
                rep(i,(int)(c-'0'))f.back().pb(0);
            }
        }
        int a,b,c,d;cin>>a>>b>>c>>d;
        f[a-1][b-1]=0;
        f[c-1][d-1]=1;
        rep(i,f.size()){
            int l=0;
            for(auto j:f[i]){
                if(j){
                    if(l)cout<<l;
                    cout<<"b";
                    l=0;
                }else{
                    l++;
                }
            }
            if(l)cout<<l;
            if(i+1==f.size()) cout<<endl;
            else cout<<"/";
        }
    }
	return 0;
}



Measured memory_bytes: 3212
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>

using namespace std;

int r,d,x,last;

int main(){
	scanf("%d%d%d",&r,&d,&x);
	last=x;
	for(int i=1;i<=10;i++){
		last*=r;
		last-=d;
		printf("%d\n",last);
	}
	return 0;
}

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


int main(){
  int N;
  cin >> N;
  string S;
  cin >> S;
  int ans=0;
  for(int ii=1; ii<N-1; ii++){
    string a = S.substr(0, ii);
    string b = S.substr(ii, N-ii);
    set<char> set_a;
    set<char> set_b;
    set<char> set_a_and_b;
    for(auto c : a){
      set_a.insert(c);
    }
    for(auto c : b){
      set_b.insert(c);
    }
    set_intersection(
      set_a.begin(), set_a.end(),
      set_b.begin(), set_b.end(),
      inserter(set_a_and_b, set_a_and_b.end()));
    ans = max(ans, (int)set_a_and_b.size());
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 256
#include <stdio.h>
#define rep(i, a, b) for(int i = (a); i < (b); ++i)

int main(){
    int A[10000];
    int count = 0;
    while(1){
        int a;
        scanf("%d", &a);
        if(a == 0) break;
        A[count] = a;
        count++;
    }

    rep(i, 0, count) printf("Case %d: %d\n", i + 1, A[i]);

    return 0;
}



Measured memory_bytes: 2028
#include <fstream>
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <queue>
#include <set>
#include <cmath>
#include <tuple>
#include <sstream>
#include <iomanip>

#define rep(i,n) for (int i = 0; i < (n); ++i)
#define sz(x) int(x.size())

using namespace std;
typedef long long ll;

int main(int argc, const char * argv[]) {
    //    ifstream in("input.txt");
    //    cin.rdbuf(in.rdbuf());
    
    cin.tie(0);
    ios::sync_with_stdio(false);

    string n;
    cin >> n;
    
    rep(i, 3)
    {
        if (n[i] == '1') cout << '9';
        if (n[i] == '9') cout << '1';
    }
    cout << endl;
    
    return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<cctype>
#include<cstring>
#define maxn 1007
#define SDOI2020 RP++ 
using namespace std;
int n,m,map[maxn][maxn],cut[maxn],ans,sum[maxn][maxn],K,num[17]; 
char s[maxn];
inline int read()
{
	int x=0;
	int flag=0;
	char ch;
	ch=getchar();
	while(!isdigit(ch)) 
	{
		if(ch=='-') flag=1;
	ch=getchar();	
	}
	while(isdigit(ch))
	{
		x=(x<<3)+(x<<1)+ch-48;
		ch=getchar();
		}
		if(flag==1) x=-x;	
		return x;
}

inline void dfs(int x,int cnt)
{
	if(x == n)
	{
		memset(num,0,sizeof(num));
		cut[++cnt] = n;
		int now = cnt - 1;
		for(register int j = 1;j <= m;j++)
		{
			for(register int i = 1;i <= cnt;i++)
			{
				//cout<<j<<endl;
				int pos = sum[cut[i]][j] - sum[cut[i - 1]][j];
				if(pos > K) return ;
				num[i] += pos;
			}
			int flag = 0;
			for(register int i = 1;i <= cnt;i++)
			{
				if(num[i] > K)
				{
					flag = 1;
					break;
				}
			}
			if(flag)
			{
				now++;
				for(register int i = 1;i <= cnt;i++)
				{
					num[i] = sum[cut[i]][j] - sum[cut[i - 1]][j];
				}
			}
		}
		ans = min(ans,now);
		return ;
	}
	cut[cnt + 1] = x;
	dfs(x + 1,cnt + 1);
	cut[cnt + 1] = 0;
	dfs(x + 1,cnt);
}


int main()
{
	n = read();
	m = read();
	K = read();
	for(register int i = 1;i <= n;i++)
	{
		scanf("%s",s + 1);
		for(register int j = 1;j <= m;j++)
		{
			map[i][j] = s[j] - '0';
		}
	}
	for(register int i = 1;i <= n;i++)
	{
		for(register int j = 1;j <= m;j++)
		{
			sum[i][j] = sum[i - 1][j] + map[i][j];
		}
	}
	ans = 1e9 + 7;
	dfs(1,0);
	printf("%d\n",ans);
	return 0;
} 

Measured memory_bytes: 2304
#include <algorithm>
#include <iostream>
#include <vector>
#include <queue>
#include <tuple>
using namespace std;
const int INF = (int)1e9 + 7;

// ------ graph ------ //
using Weight = int;
using Flow = int;
struct Edge {
    int src, dst;
    Weight weight;
    Flow cap;
    Edge() : src(0), dst(0), weight(0) { }
    Edge(int s, int d, Weight w) : src(s), dst(d), weight(w) { }
};
bool operator < (const Edge &e, const Edge &f) {
    return e.weight != f.weight ? e.weight > f.weight : // pqが降順のため
        e.src != f.src ? e.src < f.src : e.dst < f.dst;
}
using Edges = vector<Edge>;
struct Graph {
    vector<Edges> adj;
    Graph(int n) : adj(n) { }
    int size() { return adj.size(); }
    Edges operator [] (int v) { return adj[v]; }
    void add_edge(int a, int b, Weight w = 1) { // graph
        adj[a].emplace_back(a, b, w);
        adj[b].emplace_back(b, a, w);
    }
    void add_arc(int a, int b, Weight w = 1) {  // digraph
        adj[a].emplace_back(a, b, w);
    }
};
using Array = vector<Weight>;
using Matrix = vector<Array>;

// ------ dijkstra ------ //
vector<Weight> dijkstra(Graph &g, int s) {
    int n = g.size();
    using state = tuple<Weight, int>;
    priority_queue<state> q;
    vector<Weight> dist(n, INF);
    dist[s] = 0;
    q.emplace(0, s);
    while (!q.empty()) {
        Weight d; int v;
        tie(d, v) = q.top(); q.pop(); d *= -1;
        if (dist[v] < d) continue;
        for (auto &e : g[v]) {
            if (dist[e.dst] > dist[v] + e.weight) {
                dist[e.dst] = dist[v] + e.weight;
                q.emplace(-dist[e.dst], e.dst);
            }
        }
    }
    return dist;
}
//---------------------------------------------------------------

int main() {
    int n; cin >> n;
    Graph G(n);
    for (int i = 0; i < n - 1; i++) {
        int u, v, w; cin >> u >> v >> w; u--, v--;
        G.add_edge(u, v, w % 2);
    }
    vector<Weight> d = dijkstra(G, 0);
    for (int i = 0; i < n; i++) {
        cout << d[i] % 2 << endl;
    }
    return 0;
}

Measured memory_bytes: 8320
n, x = (int(i) for i in input().split())
l = [int(i) for i in input().split()]
count = 1
current = 0

if sum(l) <= x:
    print(n+1)
else:
    while current <= x:
        current += l[count-1]
        count += 1
    print(count-1)

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

int main() {
  int n, i;
  int div = 1000;
  int digit[4];
  
  cin >> n;
  
  for (i = 0; i < 4; i++) {
    digit[i] = n / div;
    n %= div;
    div /= 10;
  }
    
  if (digit[0] == digit[1]) {
    if (digit[1] == digit[2])
      cout << "Yes" << endl;
    else
      cout << "No" << endl;
  } else if (digit[1] == digit[2]) {
    if (digit[2] == digit[3])
    	cout << "Yes" << endl;
    else
      cout << "No" << endl;
  } else
    cout << "No" << endl;
 
}



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

int main() {
    int A, B, C, D, E, k;
    cin >> A >> B >> C >> D >> E >> k;
    vector<int> antennas = {A, B, C, D, E};
    for (int i = 0; i < 5; i++){
        for (int j = i + 1; j < 5; j++) {
            if (abs(antennas.at(i) - antennas.at(j)) > k) {
                cout << ":(" << "\n";
                return 0;
            }
        }
    }
    cout << "Yay!" << "\n";
    return 0;
}

Measured memory_bytes: 256
function main(arg) {
  var X = parseInt(arg[0]);
  var amt = 100;
  var year = 0;
  while(amt < X) {
  	amt *= 1.01
    amt = Math.floor(amt)
    year ++;
  }
  console.log(year)
}

main(require("fs").readFileSync("/dev/stdin", "utf8").trim().split("\n"));


Measured memory_bytes: 29708
#include <bits/stdc++.h>
#define pb push_back
#define ll long long
#define pi 3.14
using namespace std;
typedef pair<int,int> pii;
typedef pair<long long,long long> pll;
typedef pair<long long,int> pli;
typedef pair<int,long long> pil;
const int INF=1000000007;
const int MOD=1000000007;
const int nmax=201234;

ll n,x,d,d2,flg[nmax],cnt[nmax],res;
vector<pli> v2;

bool cmp(pli a,pli b)
{
    if(flg[a.second]<flg[b.second] || flg[a.second]==flg[b.second] && a.first<b.first)
        return 1;
    return 0;
}

int main()
{
    scanf("%lld%lld%lld",&n,&x,&d);
    if(d==0)
    {
        printf("%lld\n",x==0?(ll)1:(n+1));
        return 0;
    }
    else if(d<0)
    {
        x=-x;
        d=-d;
    }
    d2=2*d;
    for(ll i=0; i<=n; ++i)
    {
        ll st=(2*i-n)*x+(i*(i-1)-n*(n-1)/2)*d;
        cnt[i]=i*(n-i)+1;
        flg[i]=st%d2;
        if(flg[i]<0)
            flg[i]+=d2;
        v2.pb({st,i});
    }
    sort(v2.begin(),v2.end(),cmp);
    for(int i=0; i<v2.size(); ++i)
    {
        ll r;
        if(i==0 || flg[v2[i].second]!=flg[v2[i-1].second] || r<v2[i].first)
            r=v2[i].first;
        else if(r>=v2[i].first+cnt[v2[i].second]*d2)
            continue;
        res+=(v2[i].first+cnt[v2[i].second]*d2-r)/d2;
        r=v2[i].first+cnt[v2[i].second]*d2;
    }
    printf("%lld\n",res);
    return 0;
}


Measured memory_bytes: 8432
#include <bits/stdc++.h>
using namespace std;
using Graph = vector<vector<int>>;
#define ll long long
#define _GLIBCXX_DEBUG
const ll MOD = 1000000007;
const int MAX = 510000;

int main() {
  ll N, M;
  cin >> N >> M;
  if (N>=3&&M>=3) cout << (N-2)*(M-2) << endl;
  else if ((N==2&&M>=2)||(N>=2&&M==2)) cout << 0 << endl;
  else if (N==1&&M!=1) cout << M-2 << endl;
  else if (N!=1&&M==1) cout << N-2 << endl;
  else if (N==1&&M==1) cout << 1 << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i < (int)n;i++)
int main() {
  int n,count = 1000000;
  cin >> n;
  vector <int> v(n);
  rep(i,n) cin >> v.at(i);
  sort(v.begin(),v.end());
  
  rep(i,101){
    int cou=0;
    for(int a:v) cou += pow(a-i,2);
    count = min(cou,count);
  }
 cout << count << endl;
}


Measured memory_bytes: 256
from functools import reduce
def f(acc, a):
  if acc == 0 or a == 0:
    return 0
  elif acc == -1:
    return -1
  elif acc * a > 10 ** 18:
    return -1
  else:
    return acc * a

n = int(input())
a_list = list(map(int, input().split()))
print(reduce(f, a_list, 1))

Measured memory_bytes: 22788
#include<iostream>
#include<vector>
#include<string>
#include<cmath>
#include<sstream>
#pragma GCC optimize ("Ofast")
using namespace std;

bool check(string a){
    int n=a.size();
    for(int i=0;i<(a.length()/2);i++){
       if(a[i]!=a[n-i-1])return false;
    }
    return true;
}
int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    string s;
    cin>>s;
    int b=s.size();
    string s1=s.substr(0,(b-1)/2);
    string s2=s.substr((b+1)/2,(b-1)/2);
    if(check(s) && check(s1) && check(s2))cout<<"Yes";
    else cout<<"No";
}

Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<algorithm>
#include<bits/stdc++.h>
#include<vector>
 
using namespace std;
 
int main() {
  int N,ans=0;
  cin >> N;
  int a[N+10];
  for(int i=0; i<N; i++) cin >> a[i];
  for(int i=1; i<=N; i++){
    if(a[i]==a[i-1]){
      ans+=1;
      a[i]=-5;
    }
  }cout << ans << endl;
}

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 INF 2e9
#define ll long long

int main(){
    string s, t;
    cin>>s>>t;

    int i, j;

    for(i=0; i<s.length(); i++){
        if(s==t){
            cout<<"Yes"<<endl;
            return 0;
        }
        s = s.back() + s.substr(0, s.size()-1);
    }

    cout<<"No"<<endl;

    return 0;
}

Measured memory_bytes: 256
n=int(input())
a=list(map(int,input().split()))
a.sort()
import bisect 
if a[0]*a[-1]<0:
  print(abs(sum([abs(x) for x in a])))
  tmp=a[0]
  t=bisect.bisect_right(a,0)
  for i in range(t+1,n):
    print(tmp,a[i])
    tmp-=a[i]
  a[0]=tmp
  tmp=a[t]
  for i in range(t-1):
    print(tmp,a[i])
    tmp-=a[i]
  print(tmp,a[t-1])

elif a[0]==0:
  print(abs(sum([abs(x) for x in a])))
  tmp=a[0]
  for i in range(1,n-1):
    print(tmp,a[i])
    tmp-=a[i]
  print(a[-1],tmp)
elif a[-1]==0:
  print(abs(sum([abs(x) for x in a])))
  tmp=a[-1]
  for i in range(n-2,-1,-1):
    print(tmp,a[i])
    tmp-=a[i]

elif a[0]>0:
  print(sum(a)-2*a[0])
  tmp=a[0]
  for i in range(1,n-1):
    print(tmp,a[i])
    tmp-=a[i]
  print(a[-1],tmp)
else:
  print(abs(sum(a))+2*a[-1])
  tmp=a[-1]
  for i in range(n-2,-1,-1):
    print(tmp,a[i])
    tmp-=a[i]


Measured memory_bytes: 83524
#include <iostream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <map>
#include <stack>
#include <queue>
#include <algorithm>
#include <set>

#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define REP(i,j) FOR(i,0,j)

const int INF = 1 << 24;
const int dx[4] = {0, 0, 1, -1}, dy[4] = {1, -1, 0, 0};

typedef unsigned long long ull;
typedef std::tuple<int, int> P;



struct Edge{
    int to, cost;
};

namespace W5{
    template<typename T>
    T max(T t){
        return t;
    }

    template<typename First, typename... Rest>
    First max(First f, Rest... r){
        return std::max(f, W5::max(r...));
    }
};

std::vector<Edge> G[3010];
std::vector<int> S;
int d[3010];
int N, M, K;

int dijkstra(int s){
    int res = 0;
    std::priority_queue<P, std::vector<P>, std::greater<P>> q;
    std::fill(d, d+3010, INF);

    d[s] = 0;
    q.push(std::make_tuple(0, s));

    while(!q.empty()){
        P p = q.top(); q.pop();
        int u = std::get<0>(p), v = std::get<1>(p);
        
        if(d[v] < u){continue;}

        REP(i, G[v].size()){
            Edge e = G[v][i];
            if(d[e.to] > d[v] + e.cost){
                d[e.to] = d[v] + e.cost;
                q.push(std::make_tuple(d[e.to], e.to));
                res = std::max(res, d[e.to]);
            }
        }
    }

    return res;
}

int main(){
    std::cin >> N >> M >> K;
    
    REP(i, M){
        int from, to, l;
        std::cin >> from >> to >> l;
        from--; to--;

        G[from].push_back({to, l});
        G[to].push_back({from, l});
    }

    REP(i, K){
        int s;
        std::cin >> s;
        s--;

        S.push_back(s);
    }

    int smallest[3010];
    std::fill(smallest, smallest+3010, INF);

    REP(i, K){
        dijkstra(S[i]);

        REP(j, N){
            smallest[j] = std::min(smallest[j], d[j]);
        }
    }

    int res = 0;
    REP(i, N){
        int l = 0;
        REP(j, G[i].size()){
            Edge e = G[i][j];

            l = std::max(l, static_cast<int>(1. * (smallest[i] + smallest[e.to] + e.cost) / 2.0 + 0.5));
        }

        res = W5::max(res, smallest[i], l);
    }

    std::cout << res << std::endl;
}

Measured memory_bytes: 4220
syu,n=gets.split.map!(&:to_i)
s=gets.split.map!(&:to_i)
s.sort!
max=0
a1=0
for i in 0..n-2
  a1=(s[i]-s[i+1]).abs
  if a1>max
    max=a1
  end
end
a1=(s[0]+syu-s[n-1]).abs
if a1>max
  max=a1
end
puts syu-max


Measured memory_bytes: 28100
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll dis[2005][2005],num[2005];
int main()
{
    ios::sync_with_stdio(false);
    for(ll i=0;i<2005;i++) for(ll j=0;j<2005;j++) dis[i][j]=0x3fffffff;
    ll n,x,y;cin>>n>>x>>y;
    for(ll i=1;i<=n;i++)
    {
        for(ll j=i;j<=n;j++)
        {
            dis[j][i]=dis[i][j]=j-i;
        }
    }
    dis[x][y]=dis[y][x]=1;
    for(ll i=1;i<=n;i++)
    {
        for(ll j=i+1;j<=n;j++)
        {
            dis[j][i]=dis[i][j]=min(dis[i][j],min(dis[i][x]+dis[y][j],dis[i][y]+dis[x][j])+1);
        }
    }
//    for(ll i=1;i<=n;i++)
//    {
//        for(ll j=1;j<=n;j++)
//        {
//            cout<<dis[i][j]<<" ";
//        }
//        cout<<endl;
//    }
    for(ll i=1;i<=n;i++)
    {
        for(ll j=i+1;j<=n;j++)
        {
            ll c=dis[i][j];
            num[c]++;
        }
    }
    for(ll i=1;i<n;i++) cout<<num[i]<<endl;
	return 0;
}


Measured memory_bytes: 31744
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#define _USE_MATH_DEFINES
#include <math.h>
#include <iomanip>
#include <stdio.h>
#include <numeric>
#include <cmath>
#include <limits>
#include <bitset> 
#include <iterator> 
using namespace std;

int main()
{
	int n, x,cnt=0;
	cin >> n >> x;
	vector<int>m(n);
	for (int& x : m)cin >> x;
	for (int i = 0; i < n; i++) {
		x -= m[i];
		cnt++;
		
		if (x <= 0)return cout << cnt << endl, 0;
	}
	sort(m.begin(), m.end());
	cout << x / m[0] + cnt << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
typedef long long T;
 
struct point { 
    T x,y;
    int i; 
    point operator - (const point &q) const { return {x-q.x, y-q.y}; } 
    T operator * (const point &q) const { return x*q.x + y*q.y; } 
    T operator % (const point &q) const { return x*q.y - y*q.x; }
    T len2() const { return x*x + y*y; }
};
 
int compare(T x, T y) {
    if(y - x > 0) return -1;
    if(x - y > 0) return 1;   
    return 0;
}
 
T cross(point p, point q, point r) { return (r-q)%(p-q); }
 
int turn(point p, point q, point r) { return compare(cross(p,q,r), 0); }
 
int cw(point p, point q, point r) { return turn(p,q,r) < 0; }
 
double angle(point a, point o, point b) // angle AOB (in radians)
{
    point u = a - o; // u: vector oa
    point v = b - o; // v: vector ob
    return acos(u * v / sqrt(1.0 * u.len2() * v.len2())); 
}

bool cmp(const point &p, const point &q)
{
    return p.x < q.x || (p.x == q.x && p.y < q.y);
}
 
vector<point> convex_hull(vector<point> &p)
{
    int n = (int)p.size(), k = 0;
    vector<point> h(2 * n);
    sort(p.begin(), p.end(), cmp);
    for(int i = 0; i < n; i++) 
    {
        while(k >= 2 && cw(h[k-2], h[k-1], p[i])) k--;
        h[k++] = p[i];
    }
    for(int i = n - 2, t = k + 1; i >= 0; i--) 
    {
        while(k >= t && cw(h[k-2], h[k-1], p[i])) k--;
        h[k++] = p[i];
    }
    h.resize(k); h.pop_back(); 
    return h;
}
 
int main()
{
    ios_base::sync_with_stdio(false); cin.tie(0);
    cout << fixed << setprecision(10);
    int n,m;
    vector<point> p,h;
    double ans[105];
    while(cin >> n)
    {
        p = vector<point>(n);
        for(int i = 0; i < n; i++)
        {
            cin >> p[i].x >> p[i].y;
            p[i].i = i;
        }
        h = convex_hull(p);
        for(int i = 0; i < n; i++)
            ans[i] = 0;
        m = h.size();
        for(int i = 0; i < m; i++)
            ans[h[i].i] = (M_PI - angle(h[(i-1+m)%m], h[i], h[(i+1)%m])) / (2*M_PI);
        for(int i = 0; i < n; i++)
            cout << ans[i] << '\n';
    }
    return 0;
} 

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

using namespace std;

const int INF = 1001001001;
int a[12][12];

int main(){
    ios::sync_with_stdio(false);
    int n,m,x;
    cin >> n >> m >> x;
    vector<int> c(n);
    rep(i,n){
        cin >> c[i];
        rep(j,m)cin >> a[i][j];
    }

    int ans = INF;
    rep(i,1<<n){
        int cost = 0;
        vector<int> exp(m);
        rep(j,n){
            if(i>>j&1){
                cost += c[j];
                rep(k,m)exp[k]+=a[j][k];
            }
        }
        bool ok = true;
        rep(j,m)if (exp[j] < x) ok =false;
        if(ok)ans = min(ans,cost);
    }

    if(ans == INF)cout << -1 << endl;
    else cout << ans << endl;
    return 0;
}

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

// N が 2 で何回割れるか
int how_many_times(int N) {
    int exp = 0;
    while (N % 2 == 0) N /= 2, ++exp;
    return exp;
}

// 無限大を表す値
const int INF = 1234567890;

int main() {
    int N;
    cin >> N;
    vector<int> A(N); 
    for (int i = 0; i < N; ++i) cin >> A[i];

    // 2 で何回割れるかの最小値を求める
    int result = INF;
    for (auto a : A) {
        result = min(result, how_many_times(a));
    }
    cout << result << endl;
}

Measured memory_bytes: 3600
def printBlock(height,width):
    for x in range(height):
        if x == 0 or x == (height-1):
            for i in range(width):
                print('#',end='')
            print('')
        else:
            print('#',end='')
            for i in range(width-2):
                print('.',end='')
            print('#')
    print('')
        
while True:
    x,y = map(int,input().split())
    if x ==0 and y==0:
        break;
    else:
        printBlock(x,y)



Measured memory_bytes: 7008
N,_=gets.chomp.split(' ').map{|n| n.to_i}

arr = []
if(N%2==1)
	for i in 1..(N-1)
		for j in (i+1)..(N)
			arr << "#{i} #{j}" if j!=i && j!=(N-i)
		end
	end
else
	for i in 1..(N-1)
		for j in (i+1)..(N)
			arr << "#{i} #{j}" if j!=i && j!=(N+1-i)
		end
	end
end
puts arr.size
puts arr


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

using namespace std;

int cnt;
vector<int> G;

void insertionSort(int A[], int n, int g) {
  for (int i = g; i < n; i++) {
    int v = A[i];
    int j = i - g;
    while (j >= 0 && A[j] > v) {
      A[j+g] = A[j];
      j = j - g;
      cnt++;
    }
    A[j+g] = v;
  }
}

void shellSort(int A[], int n) {
  cnt = 0;
  for (int h = 1; ;) {
    if (h > n) break;
    G.push_back(h);
    h = 3*h + 1;
  }

  for (int i = G.size()-1; i >= 0; i--) {
    insertionSort(A, n, G[i]);
  }
}


int main() {
  int n, A[1000000];
  cin >> n;
  for (int i = 0; i < n; i++) cin >> A[i];

  shellSort(A, n);

  cout << G.size() << endl;
  cout << G[G.size()-1];
  for (int i = G.size()-2; i >= 0; i--) {
    cout << " " << G[i]; 
  }
  cout << endl;

  cout << cnt << endl;

  for (int i = 0; i < n; i++) cout << A[i] << endl;
}



Measured memory_bytes: 6988
# -*- coding: utf-8 -*-
# abc143/abc143_a
import sys

s2nn = lambda s: [int(c) for c in s.split(' ')]
ss2nn = lambda ss: [int(s) for s in list(ss)]
ss2nnn = lambda ss: [s2nn(s) for s in list(ss)]
i2s = lambda: sys.stdin.readline().rstrip()
i2n = lambda: int(i2s())
i2nn = lambda: s2nn(i2s())
ii2ss = lambda n: [i2s() for _ in range(n)]
ii2nn = lambda n: ss2nn(ii2ss(n))
ii2nnn = lambda n: ss2nnn(ii2ss(n))

def main():
    A, B = i2nn()
    print(A - 2 * B if A > (2 * B) else 0)
    return

main()


Measured memory_bytes: 3064
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
class Program
{
    static void Main(string[] args)
    {
            // 入力
            string sS = Console.ReadLine().Trim();
            int iA = int.Parse(sS);
            sS = Console.ReadLine().Trim();
            int iB = int.Parse(sS);
            sS = Console.ReadLine().Trim();
            int iC = int.Parse(sS);
            sS = Console.ReadLine().Trim();
            int iX = int.Parse(sS);

            System.Diagnostics.Stopwatch sw = new System.Diagnostics.Stopwatch();
            sw.Start();

            // 解析
            int iG = iX / 500 + 1;                                      // 伍百枚数
            int iH = 0;                                                 // 百  枚数
            int iJ = 0;                                                 // 伍拾枚数
            if (iG > iA + 1) { iG = iA + 1; }                           // 最大枚数で調整
            int iOut = 0;
            for (int i = 0; i <= iA; i++)
            {
                iG -= 1;                                                // 伍百
                if (iG < 0) { break; }
                iH = -1;
                for (int j = 0; j <= iB; j++)
                {
                    iH += 1;                                            // 百
                    iJ = -1;
                    for (int k = 0; k <= iC; k++)
                    {
                        iJ += 1;                                        // 伍拾
                        if (iX == 500 * iG + 100 * iH + 50 * iJ) { iOut += 1; }
                    }
                }
            }

            // 出力
            Console.WriteLine("{0}", iOut.ToString().Trim());

            sw.Stop();
#if DEBUG
            Console.WriteLine();
            Console.WriteLine("{0}", sw.Elapsed.ToString());
            Console.WriteLine("続行するには何かキーを押してください．．．");
            Console.ReadKey();
#endif
    }
}


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

long OPT_bottomup(int n,int W,long w[],long v[])
{
    long x[n+1][W+1]={0};
    for(int i=0;i<n+1;i++)
    {
        for(int j=0;j<W+1;j++)
        {
            if(i==0||j==0) x[i][j]=0;
            else if(j>=w[i-1]) x[i][j]=max(x[i-1][j],x[i-1][j-w[i-1]]+v[i-1]);
            else x[i][j]=x[i-1][j];
        }
    }
    return x[n][W];
}

int main()
{
    int n;
    int W;
    cin>>n>>W;
    long w[n],v[n];
    for(int i=0;i<n;i++)
    {
        cin>>w[i]>>v[i];
    }
    cout<<OPT_bottomup(n,W,w,v);
}


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

int main(){
    std::string s;
    std::cin >> s;
    if(s.length() % 2){
        int i = s.length()/2;
        int d = 1;
        while (1) {
            if(s[i-d] == s[i] && s[i+d] == s[i]){
                d++;
            }
            else{
                break;
            }
        }
        int max = s.length()-((s.length()-(d*2-1))/2);
        std::cout << s.length()-((s.length()-(d*2-1))/2) << std::endl;
    }
    else{
        int i = s.length()/2;
        if(s[i] != s[i-1]){
            std::cout << (s.length()/2) << std::endl;
            return 0;
        }
        int d = 1;
        while (1) {
            if(s[i-1-d] == s[i] && s[i+d] == s[i]){
                d++;
            }
            else{
                break;
            }
        }
        std::cout << s.length()-((s.length()-(d*2))/2) << std::endl;
    }

}


Measured memory_bytes: 512
#include<stdio.h>
#define N 500000
 
int n;
int p(int i){
  return i/2;
}

int l(int i){
  return 2*i;
}
 
int r(int i){
  return 2*i+1;
}   
 
 
void maxheapify(int h[],int i){
  int largest=0,aa,le,ri;
  le = l(i);
  ri = r(i);
  if(le <= n && h[le] > h[i]){
    largest = le;
  }
  else{
    largest = i;
   }
  if(ri <= n && h[ri] > h[largest]){
    largest = ri;
  }
  if(largest != i){
    aa = h[i];
    h[i] = h[largest];
    h[largest] = aa;
    maxheapify(h,largest);
  }
}

 void buildMaxHeap(int  h[]){
  int i;
  for(i = (n/2); i > 0; i--){
    maxheapify(h,i);
  }
}
   
 
int main(){
  int i;
  int S[N];
  scanf("%d",&n);
  for(i = 1;i <= n;i++){
    scanf("%d",&S[i]);
  }
  
  buildMaxHeap(S);
  
  for(i = 1;i <= n;i++){
    printf(" %d",S[i]);
  }
  printf("\n");
  return 0;
}

Measured memory_bytes: 2552
# a, bを素因数分解する。O(ルートa + ルートb)
# 共通の素因数を見つける。O(loga + logb)

a,b = map(int, input().split())

def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a
a_prime = set(prime_factorize(a))
b_prime = set(prime_factorize(b))
ans = 0
for ap in a_prime:
  for bp in b_prime:
    if ap == bp:
      ans += 1
      break
print(ans+1)


Measured memory_bytes: 9160
#include<iostream>

using namespace std;

int main(){


  double x[4], y[4], kata[2];

  while(cin >>x[0]>>y[0]>>x[1]>>y[1]>>x[2]>>y[2]>>x[3]>>y[3]){
    if(x[0] - x[1] != 0 && x[2] - x[3] != 0){
      kata[0] = (y[0] - y[1]) / (x[0] - x[1]);
      kata[1] = (y[2] - y[3]) / (x[2] - x[3]);

      if(kata[0] * kata[1] == -1) cout << "YES" << endl;
      else cout << "NO" << endl;

    }else{
      if(x[0] - x[1] == 0 && y[2] - y[3] == 0 || y[0] - y[1] == 0 && x[2] - x[3] == 0) cout << "YES" << endl;
      else cout <<"NO"<<endl;
	
    }
  }

  return 0;
  
}

Measured memory_bytes: 0
#include <stdio.h>
void swap(int *x, int *y){
    int temp;
    temp = *x;
    *x = *y;
    *y = temp;
}

int main(){
    int x, y;

    while(1){
        scanf("%d %d",&x, &y);
        if(x == 0 && y == 0) break;

        if(x > y) swap(&x, &y);

        printf("%d %d\n",x, y);
    }

    return 0;
}


Measured memory_bytes: 2044
import java.util.Scanner;

public class Main{
  public static void main(String[] args){
    Scanner scan = new Scanner(System.in);
    int a = scan.nextInt();
    int b = scan.nextInt();
    int c = scan.nextInt();
    int count = 0;
    for(int i= a; i <= b; i++){
      if(c%i == 0){
        count = count + 1;
      }
    }
    System.out.println(count);
  }
}

Measured memory_bytes: 26372
#include <iostream>
using namespace std;
void output(int array[],int array2[],int number){
    int num = 0;
    for(int j = 0;j<number;j++){
        num = num + array[j]*array2[j];               
    }
    cout<<num<<endl;
}

int main(){
    int n,x;
    int count = 0;
    cin>>n>>x;
    while(n != 0 || x != 0){
        if(x >= 3*n){
            count = 0;
        }else{
            for(int i = 1;i < n+1;i++){
                for(int j = i+1;j<n+1;j++){
                    int last = x - i - j;
                    if(last <= n && last > j){
                        count++;
                    }
                }
            }
        }
        cout<<count<<endl;
        count = 0;
        cin>>n>>x; 
    }
    return 0;
}


Measured memory_bytes: 3088
/* You are being watched. */


//~ while (clock() <= 69*CLOCKS_PER_SEC)
//~ #pragma comment(linker, "/stack:200000000")

#include <bits/stdc++.h>

//~ #pragma GCC optimize("Ofast")
//~ #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
//~ #pragma GCC optimize("unroll-loops")

using namespace std;

//~ #include <ext/pb_ds/assoc_container.hpp>
//~ #include <ext/pb_ds/tree_policy.hpp>
//~ using namespace __gnu_pbds;
//~ template <typename T>
//~ using ordered_set =
  //~ tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

#define all(x) (x).begin(), (x).end()
#define show(x) cerr << __LINE__ << " says: " << #x << " = " << (x) << "\n"
#define FastIO ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);

using ll = long long;
using ld = long double;
using uint = unsigned int;
using ull = unsigned long long;
//using li = __int128;
//using uli = unsigned __int128;
using pii = pair<int, int>;
using pli = pair<ll, int>;
using pll = pair<ll, ll>;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

double getTime() {
  return clock() / (double) CLOCKS_PER_SEC;
}

void read() {};

template<typename T, typename... Args>
void read(T& a, Args&... args) {
  cin >> a;
  read(args...);
}

void print() {};

template <typename T, typename... Args>
void print(T a, Args... args) {
  cout << a << " \n"[sizeof...(args) == 0];
  print(args...);
}

void solve() {
  ll x, k, d;
  cin >> x >> k >> d;
  ll ans = 1e18;
  ll df = abs(x);
  ll X = (df / d);
  if(X >= k) X = k;
  ll baki = (k - X);
  ll P = x >= 0 ? x - (d * X) : x + (d * X);
  ll Q = P;
  if(baki & 1) {
    Q = x >= 0 ? P + d : P - d;
  }
  ans = min(ans, abs(Q));
  if(baki) {
    baki--;
    P = x >= 0 ? P - d : P + d;
    Q = P;
    if(baki & 1) {
      Q = x >= 0 ? P + d : P - d;
    }
    ans = min(ans, abs(Q));
  }
  print(ans);
}

int main() {
  int t; t = 1;
  while(t--) solve();
}

Measured memory_bytes: 3632
#include<bits/stdc++.h>
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 Would
#define you
#define please


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


	string S, T;
	cin >> S >> T;

	int A = S.size();
	int B = T.size();
	int N = min(A, B);

	vector<int> C[200];
	rep(i, T.size()) C[T[i]].pb(i);

	int dp[3001][3001] = {};
	rep(i, 3001) rep(j, 3001) dp[i][j] = -1;
	dp[0][0] = 0;
	rep(i, S.size()) {
		rep(j, N) {
			if (dp[i][j] != -1) {
				if (dp[i + 1][j] == -1 || dp[i][j] < dp[i + 1][j]) dp[i + 1][j] = dp[i][j];

				auto P = lower_bound(C[S[i]].begin(), C[S[i]].end(), dp[i][j]);
				if (P != C[S[i]].end()) {
					if (dp[i + 1][j + 1] == -1 || dp[i + 1][j + 1] > *P + 1) {
						dp[i + 1][j + 1] = *P + 1;
					}
				}
			}
		}
	}
	int saidai = 0;
	rep(i, 3001) {
		if (dp[S.size()][i] != -1) saidai = i;
	}
	vector<int> V;
	int kari = dp[S.size()][saidai] + 1;
	rep(i, saidai) {
		int kari2 = 0;
		int ret = 0;
		rep(j, 3001) {
			if (dp[j][saidai - i] < kari && kari2 < dp[j][saidai - i]) {
				kari2 = dp[j][saidai - i];
				ret = j;
			}
		}
		V.pb(ret);
		kari = dp[ret][saidai - i];
	}
	reverse(V.begin(), V.end());
	for (int i : V) cout << S[i - 1];
	cout << endl;

	Would you please return 0;
}

Measured memory_bytes: 35584
# 5桁固定なので1桁目と5桁目、2桁目と4桁目を比較して同じであればいい
a, b = gets.split.map{|i| i.to_i}
ans = 0
(a..b).each do |i|
    x, y = i%10, i/10000
    p, q = (i/10)%10, (i/1000)%10
    if x==y && p==q then
        ans+=1
    end
end

puts ans

Measured memory_bytes: 1788
#include <bits/stdc++.h>
#define F first
#define S second
#define PB push_back
#define MP make_pair

using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef pair<int , int> pi;

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n;
	cin>>n;
	string s;
	cin>>s;
	set<int> r, g, b;
	for(int i=0; i<n; i++)
	{
		char ch = s[i];
		if(ch == 'R')
			r.insert(i);
		else if(ch == 'G')
			g.insert(i);
		else
			b.insert(i);
	}
	int add = b.size();
	ll answer = 0;
	for(auto ii: r)
	{
		for(auto jj: g )
		{
			answer += add;
			if(b.find(2*jj-ii) != b.end())
				answer--;
			if((ii+jj)%2 == 0 && b.find((ii+jj)/2) != b.end())
				answer--;
			if(b.find(2*ii-jj) != b.end())
				answer--;
		}
	}
	cout<<answer<<endl;
	return 0;
};


Measured memory_bytes: 3840
N = gets.chomp.to_i
price_of_cake = 4
price_of_dounut = 7
answer = 'No'
(0..25).each do |c|
  (0..15).each do |d|
    answer = 'Yes' if N == (d * price_of_dounut + c * price_of_cake)
  end
end

puts answer


Measured memory_bytes: 1788
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;


public class Main {

	/**
	 * @param args
	 * @throws IOException 
	 * @throws NumberFormatException 
	 */
	public static void main(String[] args) throws NumberFormatException, IOException {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		while(true){
			int n = Integer.parseInt(br.readLine());
			
			if(n == 0){
				break;
			}
			
			System.out.println(Factorial.numOfLast0(n));
		}
	}

}

class Factorial {
	public static long factor(int n){
		long result = 1;
		
		for(int i = 2; i <= n ; i++){
			result *= i;
		}
		
		return result;
	}
	
	public static int numOfLast0(int n){
		int two = 0;
		int five = 0;
		int result = 0;
		
		for(int i = 2; i <= n ; i++){
			int tmp = i;
			while(tmp % 2 == 0){
				tmp /= 2;
				two++;
			}
			while(tmp % 5 == 0){
				tmp /= 5;
				five++;
			}
		}
		
		while(two > 0 && five > 0){
			result++;
			two--;
			five--;
		}
		
		return result;
	}
}

Measured memory_bytes: 24356
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define REP(i,m,n) for(int i=(int)(m); i<(int)(n); i++)
#define rep(i,n) REP(i,0,n)
#define RREP(i,m,n) for(int i=(int)(m); i>=(int)(n); i--)
#define rrep(i,n) RREP(i,(n)-1,0)
#define all(v) v.begin(), v.end()
#define endk '\n'
const int inf = 1e9+7;
const ll longinf = 1LL<<60;
const ll mod = 1e9+7;
const ll mod2 = 998244353;
const ld eps = 1e-10;
template<typename T1, typename T2> inline void chmin(T1 &a, T2 b){if(a>b) a=b;}
template<typename T1, typename T2> inline void chmax(T1 &a, T2 b){if(a<b) a=b;}

ll modpow(ll a, ll N) {
  ll ans = 1;
  ll tmp = a;
  while(N > 0) {
    if(N % 2 == 1) (ans *= tmp) %= mod;
    (tmp *= tmp) %= mod;
    N /= 2;
  }
  return ans;
}
int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  int n; cin >> n;
  ll ans = (((modpow(10, n) - modpow(8, n) + mod) % mod) - ((modpow(9, n) - modpow(8, n) + mod) % mod) * 2 % mod + mod) % mod;
  cout << ans << endk;
  return 0;
}


Measured memory_bytes: 3652
def partition(a, left, right):
    pivot = a[right-1]
    i = left - 1
    for j in range(left, right-1):
        if a[j] <= pivot:
            i += 1
            a[i], a[j] = a[j], a[i]
    a[i+1], a[right-1] = a[right-1], a[i+1]
    return i + 1

def main():
    n = int(input())
    a = list(map(int, input().split()))
    p = partition(a, 0, len(a))
    a[p] = '[' + str(a[p]) + ']'
    print(' '.join(map(str, a)))

if __name__ == '__main__':
    main()


Measured memory_bytes: 16388
def is_alphabet(s):
    if (0x41 <= ord(s) and ord(s) <= 0x5A) or (0x61 <= ord(s) and ord(s) <= 0x7A):
        return True
    else:
        return False


def is_upper(s):
    if 0x41 <= ord(s) and ord(s) <= 0x5A:
        return True
    else:
        return False


def is_lower(s):
    if 0x61 <= ord(s) and ord(s) <= 0x7A:
        return True
    else:
        return False


S = input().strip()
ans = ""

for s in S:
    if is_alphabet(s):
        if is_upper(s):
            ans += s.lower()
        else:
            ans += s.upper()
    else:
        ans += s

print(ans)



Measured memory_bytes: 5556
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Diagnostics;

namespace AtCoder
{
    class Program
    {
        private static string Read() { return Console.ReadLine(); }
        private static int ReadInt() { return int.Parse(Read()); }
        private static long ReadLong() { return long.Parse(Read()); }
        private static double ReadDouble() { return double.Parse(Read()); }
        private static int[] ReadInts() { return Array.ConvertAll(Read().Split(), int.Parse); }
        private static long[] ReadLongs() { return Array.ConvertAll(Read().Split(), long.Parse); }
        private static double[] ReadDoubles() { return Array.ConvertAll(Read().Split(), double.Parse); }

        static int Solve(int N, int M, Tuple<int, int>[] demands)
        {
            Array.Sort(demands);
            int cnt = 1;
            int min = demands[0].Item1;
            int max = demands[0].Item2;
            for (int i = 0; i < M; ++i)
            {
                min = Math.Max(demands[i].Item1, min);
                max = Math.Min(demands[i].Item2, max);
                if (min >= max)
                {
                    min = demands[i].Item1;
                    max = demands[i].Item2;
                    ++cnt;
                }
            }
            return cnt;
        }
        static void Main(string[] args)
        {
            int[] V1 = ReadInts();
            int N = V1[0];
            int M = V1[1];
            var demands = new Tuple<int, int>[M];
            for (int i = 0; i < M; ++i)
            {
                int[] V2 = ReadInts();
                demands[i] = new Tuple<int, int>(V2[0], V2[1]);
            }
            Console.WriteLine(Solve(N, M, demands));
        }
    }
}


Measured memory_bytes: 22320
import java.io.PrintWriter;
import java.util.Scanner;

public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        PrintWriter out = new PrintWriter(System.out);

        int h = sc.nextInt();
        int w = sc.nextInt();
        char[][] s = new char[h][w];
        
        String tmp = sc.nextLine();
        for(int i = 0; i < h; i++){
            tmp = sc.nextLine();
            for(int j = 0; j < w; j++){
                s[i][j] = tmp.charAt(j);
            }
        }

        for(int i = 0; i < h; i++){
            for(int j = 0; j < w; j++){
                if(s[i][j] == '.'){
                    int count = 0;
                    for(int p = Math.max(0,i-1); p <= Math.min(h-1,i+1); p++){
                        for(int q = Math.max(0,j-1); q <= Math.min(w-1, j+1); q++){
                            if(s[p][q] == '#') count++;
                        }
                    }
                    out.print(count);
                }else{
                    out.print('#');
                }
            }
            out.println();
        }

        out.flush();
        sc.close();
    }
}

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

using namespace std;

int main () {
  string str,answer;
  cin >> str;
  
  for(int i = 0; i < str.size(); i++){
    if(str.at(i) == '0'){answer.push_back('0');}
    if(str.at(i) == '1'){answer.push_back('1');}
    if(str.at(i) == 'B' && answer.size() > 0){answer.pop_back();}
  }
  cout << answer << endl;
}

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

typedef long long ll;

int N;
ll a[(int)2e5];

int main() {
    ll ans = 1e18;
    ll sum = 0;
    cin >> N;
    rep(i, N) {
        cin >> a[i];
        sum += a[i];
    }

    // ll sum = accumulate(a, a + N, 0);
    ll x = 0;
    for (int i = 0; i <= N - 2; i++) {
        x += a[i];
        ll y = sum - x;
        // printf("x: %lld y: %lld abs: %lld\n", x, y, abs(x - y));
        // ans = min(ans, abs(x - y));
        ans = min(ans, abs(sum - 2 * x));
    }

    cout << ans << endl;
}


Measured memory_bytes: 1792
import bisect,collections,copy,heapq,itertools,math,numpy,string
import sys
sys.setrecursionlimit(10**7)

def S(): return sys.stdin.readline().rstrip()
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def LS(): return list(sys.stdin.readline().rstrip().split())

def main():
    N = I()
    kuku_list = []
    for i in range(1,10):
        for j in range(1,10):
            kuku_list.append(i*j)
    print("Yes" if N in kuku_list else "No")

main()



Measured memory_bytes: 27220
#include <bits/stdc++.h>
#include <iostream>
#include <queue>
#include <stack>
#include <vector>
#include <string>
#include <set>
#include <map>
#include <random>
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define repp(i,n,m) for (int i = m; i < (n); ++i)
#define repl(i,n) for (long long i = 0; i < (n); ++i)
#define reppl(i,n,m) for (long long i = m; i < (n); ++i)
using namespace std;
using ll = long long;
using ld = long double;
using P = pair<int, int>;
using PL = pair<long long, long long>;
using Pxy = pair<long double, long double>;
using T = tuple<int, int, bool>;
const int INF = 1001001007;
const int MOD = 1000000007;
const ll inf = 1e18;
template <typename AT>
void printvec(vector<AT> &ar){
    rep(i,ar.size()-1) cout << ar[i] << " ";
    cout << ar[ar.size()-1] << endl;
}
template <typename Q>
void printvvec(vector<vector<Q>> &ar){
    rep(i,ar.size()){
        rep(j,ar[0].size()-1) cout << ar[i][j] << " ";
        cout << ar[i][ar[0].size()-1] << endl;
    }
}
template <typename S>
bool range(S a, S b, S x){
    return (a <= x && x < b);
}

int main() {
    int n; cin >> n;
    vector<int> ar(n);
    map<int, int> m;
    rep(i,n){
        int a; cin >> a;
        ar[i] = a;
        if (m.find(i+1-a) == m.end()) m[i+1-a] = 1;
        else m[i+1-a]++;
    }
    ll ans = 0;
    rep(i,n){
        if (m.find(i+1+ar[i]) != m.end()){
            ans += max(0,m[i+1+ar[i]]);
            m[i+1-ar[i]]--;
        }
    }
    cout << ans << endl;
}

Measured memory_bytes: 12628