akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>
#include <map>
#include <numeric>
#include <set>
#include <queue>
#include <list>
using namespace std;
typedef long long ll;

void solve() {
	char x; cin >> x;
	if (isupper(x))cout << 'A';
	else cout << 'a';
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL);
#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
#endif

	// int t; cin >> t;
	// while (t--)
	solve();

}

Measured memory_bytes: 3648
#define _USE_MATH_DEFINES
#include <iostream>
#include <sstream>
#include <string>
#include <list>
#include <vector>
#include <queue>
#include <algorithm>
#include <climits>
#include <cstring>
#include <cmath>
#include <stack>
#include <iomanip>
#include <tuple>
#include <functional>
#include <cfloat>
#include <map>
#include <set>
#include <array>
#include <stdio.h>
#include <string.h>
using ll = long long;
using ull = unsigned long long;
using namespace std;
#define int long long
#define CONTAINS_VEC(v,n) (find((v).begin(), (v).end(), (n)) != (v).end())
#define SORT(v) sort((v).begin(), (v).end())
#define RSORT(v) sort((v).rbegin(), (v).rend())
#define ARY_SORT(a, size) sort((a), (a)+(size))
#define REMOVE(v,a) (v.erase(remove((v).begin(), (v).end(), (a)), (v).end()))
#define REVERSE(v) (reverse((v).begin(), (v).end()))
#define ARY_REVERSE(v,a) (reverse((v), (v)+(a)))
#define REP(i, n) for (int (i)=0; (i) < (n); (i)++)
#define CONTAINS_MAP(m, a) (m).find((a)) != m.end()
#define CONTAINS_SET(m, a) (m).find((a)) != m.end()
void YesNo(bool b) { cout << (b ? "Yes" : "No") << endl; }
void YESNO(bool b) { cout << (b ? "YES" : "NO") << endl; }

int dp[1000001][2];

int func1(string N)
{
	int len = N.length();

	dp[0][1] = 10 - (N[len - 1] - '0');
	dp[0][0] = (N[len - 1] - '0');

	for (int i = 1; i < len; i++)
	{
		char ch = N[len - i - 1];
		int n = ch - '0';

		int a0 = 10 - (n + 1) + dp[i - 1][1];
		int a1 = 10 - n + dp[i - 1][0];
		dp[i][1] = min(a0, a1);

		int b0 = n + 1 + dp[i - 1][1];
		int b1 = n + dp[i - 1][0];
		dp[i][0] = min(b0, b1);
	}

	return min(dp[len - 1][1] + 1, dp[len - 1][0]);
}

int count_func(int n)
{
	int cnt = 0;
	while (n > 0)
	{
		cnt += n % 10;
		n /= 10;
	}
	return cnt;
}

int func2(string s)
{
	int n;
	istringstream iss(s);
	iss >> n;

	int mi = INT_MAX;
	for (int i = n; i < 2000; i++)
	{
		int sub = i - n;
		int n = count_func(i) + count_func(sub);
		mi = min(mi, n);
	}
	return mi;
}

signed main()
{
	string N;
	cin >> N;
	cout << func1(N) << endl;
}



Measured memory_bytes: 20480
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define all(x) (x).begin(),(x).end()
#define pb push_back
#define fi first
#define se second
#define dbg(x) cout<<#x" = "<<((x))<<endl
template<class T,class U> ostream& operator<<(ostream& o, const pair<T,U> &p){o<<"("<<p.fi<<","<<p.se<<")";return o;}
template<class T> ostream& operator<<(ostream& o, const vector<T> &v){o<<"[";for(T t:v){o<<t<<",";}o<<"]";return o;}

using pi = pair<int,int>;
using E = pair<int,pi>;

int main()
{
    int n,m;
    cin >>n >>m;

    vector<E> e(m);
    rep(i,m)
    {
        int a,b,c;
        cin >>a >>b >>c;
        --a;
        --b;
        e[i] = {c,{a,b}};
    }
    sort(all(e));

    int ans = -1;
    vector<bool> vis(n);
    vis[0] = true;
    rep(i,m)
    {
        pi p = e[i].se;

        if(vis[p.fi])
        {
            vis[p.se] = true;
            if(p.se == n-1) ans = e[i].fi;
        }
    }

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

Measured memory_bytes: 5108
#include <bits/stdc++.h>
 #include <string> 
 #include <math.h>
 #include <bitset>
 #include <numeric>
 #include <stdio.h>
 #include <algorithm>

 using namespace std;

 int main(){
    long long N,i;
    long long A[220000];
    long long p_sum[220000];
    long long ans=0;
    long long tmp_mod=0;
    cin >> N;

    for (i=0; i<N; i++)
        cin >> A[i];

    p_sum[0]=A[0];
   
    for (i=1; i<N; i++)
        p_sum[i]=p_sum[i-1]+A[i];
   
    for (i=0; i<N-1; i++){
        tmp_mod=(p_sum[N-1]-p_sum[i])%1000000007;
        ans = ans + A[i]*tmp_mod;
        ans = ans%1000000007;
        }
    cout << ans << endl;

    return 0;
 }
 



Measured memory_bytes: 6768
#include <bits/stdc++.h>
using namespace std;
 
int main()
{
    int N;
    cin >> N ;

    vector<int> a(3*N);
    for(int i = 0; i < (3*N); i++)
    {
        cin >> a.at(i);
    }

    //aを降順にソート
    sort(a.begin(), a.end(), greater<int>());

    long sum = 0;
    for(int i = 0; i < (2*N); i+=2)
    {
        sum += (long)a.at(i+1);
    }

    cout << sum;

    return 0;
}

Measured memory_bytes: 1408
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define tcase int _; cin >> _; while(_--)
const int MAX = 1e3;

int h, w, k;
char v[MAX][MAX];

int check(int x, int y) {
	int cnt=0;
	for(int i=0; i<h; i++) {
		for(int j=0; j<w; j++) {
			if(v[i][j] == '#' && !((1<<i)&x) && !((1<<j)&y)) cnt++;
		}
	}
	// if(cnt == k) cout << x << " " << y << "\n";
	//cout << "\n";
	return cnt == k;
}

void solve() {
	cin >> h >> w >> k;
	for(int i=0; i<h; i++) for(int j=0; j<w; j++) cin >> v[i][j];
	int ans=0;
	for(int i=0; i<(1<<h); i++) {
		for(int j=0; j<(1<<w); j++) {
			if(check(i, j)) ans++;
		}
	}
	cout << ans << "\n";
}

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

 	solve();

  	return 0;
}



Measured memory_bytes: 3560
#include<bits/stdc++.h>
#define rep(i,n,m) for(int i = (n); i <(m); i++)
#define rrep(i,n,m) for(int i = (n) - 1; i >=(m); i--)
#define pvec(vec) {for (auto v: vec) cout << v << ' '; cout << endl;}
#define pivec(vec) {rep(i, 0, vec.size()) cout << i << ':' << vec[i] << ' '; cout << endl;}

using namespace std;
using ll = long long;

int main()
{
    rep(i,1,6)
    {
        int x;
        cin >> x;
        if (x == 0)
            cout << i << endl;
    }
    return 0;
}


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

#define POS(i,j,k) ((((i)%2)*(1+cnt[1]+cnt[2])+(j))*(1+n)+(k))

void run(void){
  int n;
  scanf("%d",&n);
  const double p=(double)1/n;
  int cnt[3]={0,0,0};
  int i,j,k;
  for(i=0;i<n;i++){
    int a;
    scanf("%d",&a);
    cnt[a-1]++;
  }
  double *dp=(double *)calloc(2*(1+cnt[1]+cnt[2])*(1+n),sizeof(double));
  for(i=0;i<=cnt[2];i++){
    for(j=0;j<=cnt[1]+cnt[2]-i;j++){
      for(k=(i==0 && j==0?1:0);k<=n-i-j;k++){
	double local=1;
	if(i>0) local+=p*i*dp[POS(i-1,j+1,k)];
	if(j>0) local+=p*j*dp[POS(i,j-1,k+1)];
	if(k>0) local+=p*k*dp[POS(i,j,k-1)];
	dp[POS(i,j,k)]=local*n/(i+j+k);
      }
    }
  }
  printf("%.9f\n",dp[POS(cnt[2],cnt[1],cnt[0])]);
}

int main(void){
  run();
  return 0;
}


Measured memory_bytes: 1536
#include <cstdio>
int main(void){
    char X, Y;
    scanf("%c %c", &X, &Y);
    if (X > Y)
    {
        printf(">");
    }
    else if (X < Y)
    {
        printf("<");
    }
    else
    {
        printf("=");
    }
    return 0;

}


Measured memory_bytes: 128
k=int(input())

def dp(k):
    if k<=9:
        return k
    else:
        prev_keta_nums=[1,2,3,4,5,6,7,8,9]
        count=9
        flag = False
        while True:
            next_keta_nums=[]
            for num in prev_keta_nums:
                num_last = int(str(num)[-1])
                if num_last == 9:
                    cands = [8,9]
                elif num_last == 0:
                    cands = [0,1]
                else:
                    cands = [num_last-1,num_last,num_last+1]
                for cand in cands:
                    new_num=int(str(num)+str(cand))
                    next_keta_nums.append(new_num)
                    count+=1
                    if count == k:
                        flag = True
                    if flag:
                        break
                if flag:
                    break
                else:
                    prev_keta_nums = next_keta_nums
            if flag:
                break
        return next_keta_nums[-1]
print(dp(k))

Measured memory_bytes: 43100
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main(){
	int n;
	cin>>n;
	vector< pair<int,int> > v;
	for(int i = 0; i<n ; i++){
		int k;
		cin>>k;
		v.push_back(make_pair(k,i));
	}
	sort(v.begin(),v.end());
	for(int i=0;i<n;i++){
		cout<<v[i].second+1<<" ";
	}
	return 0;
}


Measured memory_bytes: 1780
#include<stdio.h>
int main() {
    int a,b;

    scanf("%d %d",&a,&b);

    double f1,f2,f3;

    f1 = a/b;
    f2 = a%b;
    f3 = 1.0 * a/b;

    printf("%.0lf %.0lf %.8lf\n ",f1,f2,f3);

    return 0;
}



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

string s;

signed main()
{
	cin>>s;
	int n=s.size()-1;
	if (s[n]=='s')  cout<<s<<"es"<<endl;
	else cout<<s<<"s"<<endl;
	
	return 0;
}

Measured memory_bytes: 3628
#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=2e5+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()
{
    int n;
    while(cin>>n)
    {
        int ans=1;
        ll last=0;
        cin>>last;
        for(int i=2;i<=n;i++)
        {
            ll a;cin>>a;
            if(a<=last)
            {
                ans++;
            }
            last=min(last,a);
        }
        cout<<ans<<endl;
    }
    return 0;
}


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

int main(){
    int N,X;
    cin>>N>>X;
    vector<int> zahyo(N);
    long min=999999999999;

    for(auto &&x:zahyo){
        cin>>x;    

    }

    int ans=abs(zahyo[0]-X);



    for(int i=1;i<N;i++){
        ans=__gcd(ans,abs(zahyo[i]-X));
    }


cout<<ans<<endl;





}

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

using namespace std;

using ll = long long;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  string s;
  cin >> s;
  int n = (int)s.size();
  auto is_batch = [](string s) {
    string rs = s;
    reverse(rs.begin(), rs.end());
    return rs == s;
  };
  bool b1 = is_batch(s);
  bool b2 = is_batch(s.substr(0, (n - 1) / 2));
  bool b3 = is_batch(s.substr((n + 3) / 2 - 1));
  if (b1 && b2 && b3) {
    cout << "Yes" << '\n';
  } else {
    cout << "No" << '\n';
  }
  return 0;
}


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

int main() {
    int N, l, r, total;
    cin >> N;
    total = 0;

    for (int i = 0; i < N; i++)
    {
        cin >> l >> r;
        total += (r - l + 1);
    };

    cout << total << endl;
    
    
}


Measured memory_bytes: 256
// ConsoleApplication98.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//
#include <iostream>
#include<cstring>
#include<algorithm>
#include<iomanip>
#include<set>
#include<map>
#include<vector>
#include<cmath>
using namespace std;
typedef long long ll;

int main()
{
	ll n, a, b, sum;
	cin >> n >> a >> b;
	sum = 0;
	sum = n / (a + b) * a;

	n = n % (a + b);
	if (n > a)n = a;
	sum += n;
	cout << sum;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using P = pair<ll, ll>;

const ll INF64 = 1LL << 60;
const int INF32 = 1 << 29;
const ll MOD = 1000000007;

int main(){
    int n, t; cin >> n >> t;
    int ans = INF32;
    for(int i = 0; i < n; ++i){
    	int c, tmp; cin >> c >> tmp;
        if(tmp <= t){
        	ans = min(ans, c);
        }
    }
    if(ans == INF32){cout << "TLE" << endl;}
    else{cout << ans << endl;}
    return 0;
}

Measured memory_bytes: 256
package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
	"strings"
)

func getScanner(fp *os.File) *bufio.Scanner {
	scanner := bufio.NewScanner(fp)
	scanner.Split(bufio.ScanWords)
	scanner.Buffer(make([]byte, 1000005), 1000005)
	return scanner
}

func getNextString(scanner *bufio.Scanner) string {
	scanner.Scan()
	return scanner.Text()
}

func getNextInt(scanner *bufio.Scanner) int {
	i, _ := strconv.Atoi(getNextString(scanner))
	return i
}

func getNextInt64(scanner *bufio.Scanner) int64 {
	i, _ := strconv.ParseInt(getNextString(scanner), 10, 64)
	return i
}

func getNextUint64(scanner *bufio.Scanner) uint64 {
	i, _ := strconv.ParseUint(getNextString(scanner), 10, 64)
	return i
}

func getNextFloat64(scanner *bufio.Scanner) float64 {
	i, _ := strconv.ParseFloat(getNextString(scanner), 64)
	return i
}

func main() {
	fp := os.Stdin
	wfp := os.Stdout
	cnt := 0

	if os.Getenv("MASPY") == "ますピ" {
		fp, _ = os.Open(os.Getenv("BEET_THE_HARMONY_OF_PERFECT"))
		cnt = 2
	}
	if os.Getenv("MASPYPY") == "ますピッピ" {
		wfp, _ = os.Create(os.Getenv("NGTKANA_IS_GENIUS10"))
	}

	scanner := getScanner(fp)
	writer := bufio.NewWriter(wfp)
	solve(scanner, writer)
	for i := 0; i < cnt; i++ {
		fmt.Fprintln(writer, "-----------------------------------")
		solve(scanner, writer)
	}
	writer.Flush()
}

func solve(scanner *bufio.Scanner, writer *bufio.Writer) {
	s := getNextString(scanner)
	takuya := "AKIHABARA"

	a := [2]string{
		"",
		"A",
	}
	t := strings.Split(takuya, "")
	pos := make([]int, 0)
	for i := 0; i < len(takuya); i++ {
		if takuya[i] != 'A' {
			continue
		}
		pos = append(pos, i)
	}
	for i := 0; i < 1<<4; i++ {
		for j := 0; j < 4; j++ {
			t[pos[j]] = a[i>>uint(j)&1]
		}
		if strings.Join(t, "") == s {
			fmt.Fprintln(writer, "YES")
			return
		}
	}
	fmt.Fprintln(writer, "NO")
}


Measured memory_bytes: 640
N=int(input())
xyh=sorted([list(map(int, input().split())) for _ in range(N)], key=lambda x: x[2], reverse=True)

def find(cx, cy, H):
	for x,y,h in xyh:
		if h != max(H-abs(x-cx)-abs(y-cy), 0):
			return False
	return True

def solve():
	for cx in range(101):
		for cy in range(101):
			x,y,h = xyh[0]
			H = h + abs(x-cx) + abs(y-cy)
			if find(cx, cy, H):
				return "%d %d %d" % (cx, cy, H)
	raise Exception

print(solve())


Measured memory_bytes: 3188
#include <iostream>
#include <string>
#include <string.h>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
using namespace std;
const int maxn = 30;
int main(){
	string s,t;
	cin >> s >> t;
	int flag = 0;
	if(s == t) cout << "Yes" << endl;
	else{
		int i,j;
		for(i = 1;i <= s.length();i++){
			string str = s.substr(0,i);
			string ttr="";
			for(j = 0;j < t.length();j++){
				ttr = t.substr(j,t.length()-j);
				if(str == ttr) {
				flag = 1;
				break;
				}
			}
			if(flag) break;
		}
		if(flag == 1){
			if(s.substr(i,s.length()-i)==t.substr(0,j)){
				cout << "Yes" << endl;
			}
			else cout << "No" << endl;
		}else{
			cout << "No" << endl;
		}
		
	}
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll mod = 1000000007;


int main(){
  long double a,v,b,w,t;
  cin >> a >> v;
  cin >> b >> w;
  cin >> t;
  if(v-w<=0){
    cout << "NO"<< endl;
    return 0;

  }
  
  long double ans = (b-a)/(v-w);
  if(ans<0)ans*=-1;
  if(ans<=t){
    cout << "YES" << endl;
  }
  else cout << "NO" << endl;
 
}
  
  
  


Measured memory_bytes: 3780
# マイナスが大きいものの開催頻度をあげる
d=int(input())
c= list(map(int, input().split()))
D= [list(map(int, input().split())) for i in range(d)]
cc=[0]*26
for i in range(26):
    cc[i]=[c[i],i+1]
cc.sort(reverse=True)

ans=[0]*d
# 最後にどの試験がいつ行われたか？
PL=[0]*26

for i in range(d):
    cnt=0
    cntt=-10**9
    x=1
    for k in range(len(c)):
        v=PL[:]
        cnt = D[i][cc[k][1]-1]
        v[cc[k][1]-1] = i+1
        for j in range(len(c)):
            cnt-=(i+1-v[j])*c[j]
        if cnt>cntt+100:
            x=cc[k][1]
            cntt=max(cnt,cntt)
    ans[i]=x
    PL[x-1]=i


for i in range(d):
    print(ans[i])

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



#define TRACE
 
#ifdef TRACE
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void __f(const char* name, Arg1&& arg1){
    cerr << name << " : " << arg1 << std::endl;
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args){
    const char* comma = strchr(names + 1, ',');cerr.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...);
}
#else
#define trace(...)
#endif

#define ll   long long 
#define ld long double
#define all(v) v.begin(),v.end()
#define pb push_back
#define S second
#define F first
#define die() return 0;
 
#define md          1000000007
#define fmd         998244353 
#define M           1011
#define N            18
ll exp(ll a,ll b){if(b<0)return 0;ll r=1;while(b){if(b&1)r=r*a%md,r%=md;a=a*a%md;b/=2;}return r;}

ll F[M],iv[M];
void prec(){
	F[0]=iv[0]=1;
	for(int i=1;i<M;++i){
		F[i]=F[i-1]*i%md;F[i]%=md;
		iv[i]=iv[i-1]*exp(i,md-2)%md;iv[i]%=md;
	}
}
ll chose(ll n,ll k){
	if(n<k)return 0;
	ll r=F[n];r=r*iv[k];r%=md;r=r*iv[n-k];return r%md;
}
ll bo(ll j,ll i){
	ll up=F[i*j];
	ll down=iv[i];
	// trace(down,up);
	down=exp(down,j);
	up=up*down%md;up%=md;
	up=up*iv[j];
	// trace(up,down);
	return up%md;
}

ll a,b,c,d;
ll dp[M][M];



ll f(ll i,ll n){
	if(n==0)return 1;
	if(i<a)return 0;
	if(dp[i][n]!=-1)return dp[i][n];
	ll &ans=dp[i][n];
	ans=0;
	ans=ans+f(i-1,n);
	for(ll j=c;n-j*i>=0&&j<=d;++j){
		ll p=f(i-1,n-i*j);
		// trace(i-1,n-i*j,i,j,n,p,bo(j,i));
		p=p*bo(j,i);
		p%=md;
		p=p*chose(n,i*j);p=p%md;
		ans+=p;ans%=md;
	}
	return ans;


}


int solve(){
    ll n,i,j,k,m,x,y,z;
    cin>>n>>a>>b>>c>>d;
    memset(dp,-1,sizeof(dp));
    ll p=f(b,n);
    cout<<p<<"\n";

    die();
}
 
 
int main(){
 
 
#ifndef ONLINE_JUDGE
    double _tBeg=clock();
#endif

     
    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);

    int t;
    t=1;;
    prec();
    // cin>>t;
 
    while(t--){

        solve();
    }
 
 
 
 


#ifndef ONLINE_JUDGE
    double _tEnd=clock();
    // printf("\ntotal time %.6f\n",(_tEnd-_tBeg)/CLOCKS_PER_SEC);
#endif
 
    die();
}

Measured memory_bytes: 8320
#include <bits/stdc++.h>
#ifdef ONLINE_JUDGE
#define endl "\n"
#endif
using namespace std;
typedef long long LL;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef pair<int, int> PII;

void solve() {
    int n; cin >> n;
    int g = 0;
    for (int i = 0; i < n; i++) { int x; cin >> x; g = __gcd(x, g); }
    cout << g << endl;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    // int t;cin >> t;while(t--)
    solve();
    return 0;
}


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

#define REP(i,s,n) for(int i=s;i<n;++i)
#define rep(i,n) REP(i,0,n)
#define ALL(x) x.begin(),x.end()
#define EPS (1e-8)
#define equals(a,b) (fabs((a)-(b))<EPS)

using namespace std;

typedef long long ll;
bool LTE(double a,double b) { return equals(a,b) || a < b; }
bool LT(double a,double b) { return !equals(a,b) && a < b; }

int H,W,K;
string s[310], t[310][310];

int d[] = {0,1,0,-1};
bool used[310][310];
bool check() {
  memset(used,false,sizeof used);
  rep(i,H) {
    rep(j,W) {
      if( used[i][j] ) continue;
      deque<int> deq;
      deq.push_back(j+i*W);
      used[i][j] = true;
      int cnt = 0;
      if( s[i][j] == '#' ) ++cnt;
      while( !deq.empty() ) {
	int cur =deq.front(); deq.pop_front();
	int x = cur % W, y = cur / W;
	rep(k,4) {
	  int nx = x + d[k];
	  int ny = y + d[(k+1)%4];
	  if( 0 <= nx && nx < W && 0 <= ny && ny < H && !used[ny][nx] ) {
	    if( t[i][j] == t[ny][nx] ) {
	      deq.push_back(nx+ny*W);
	      used[ny][nx] = true;
	      if( s[ny][nx] == '#' ) {
		++cnt;
	      }
	    }
	  }
	}
      }
      if( cnt >= 2 || cnt == 0 ) {
	cout << "FAILED... t = " << t[i][j] << endl;
	return false;
      }
    }
  }
  return true;
}

void draw(int xL,int yL,int xR, int yR,int id) {
  string v = to_string(id);
  REP(y,yL,yR+1) {
    REP(x,xL,xR+1) {
      t[y][x] = v;
    }
  }
}

void compute() {
  vector<int> vec(H,0);
  rep(i,H) rep(j,W) t[i][j] = "?";
  rep(i,H) {
    rep(j,W) if( s[i][j] == '#' ) ++vec[i];
  }
  vector<int> sumY(W,0);
  rep(x,W) {
    rep(y,H) if( s[y][x] == '#' )++sumY[x];
  }
  int all_cnt = 0;
  int id = 1;
  int prey = 0;
  vector<int> curY(W,0);
  rep(i,H) {
    if( vec[i] == 0 ) continue;
    int prex = 0;
    int cnt = 0;
    rep(j,W) {
      if( s[i][j] == '#' ) {
	++curY[j];
	++cnt;
	++all_cnt;
	int nx = j;
	int ny = i;
	if( cnt == vec[i] )  {
	  nx = W - 1;
	}
	if( curY[j] == sumY[j] ) {
	  ny = H - 1;
	}
	if( all_cnt == K ) {
	  nx = W - 1;
	  ny = H - 1;
	}
	draw(prex,prey,nx,ny,id);
	++id;
	prex = j + 1;
      }
    }
    prey = i + 1;
  }
  
  rep(i,H) {
    rep(j,W) {
      if( j ) cout << " ";
      cout << t[i][j];
    }
    puts("");
  }
  //assert( check());
}

int main() {
  cin >> H >> W >> K;
  rep(i,H) cin >> s[i];
  compute();
  return 0;
}


Measured memory_bytes: 5888
alice = 0
bob= 0

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

for i in range(N):
    max_num = max(a)
    if i % 2 == 0:
        alice += max_num
    else:
        bob += max_num
    a.remove(max_num)

print(alice - bob)


Measured memory_bytes: 3316
#include <stdio.h>
#include <string.h>

#define LEN 100010


typedef struct pp {
    char name[100];
    int t;
} P;


P Q[LEN];
int head, tail;

void enqueue(P x) {
    Q[tail] = x;
    tail = (tail+1)%LEN;
}


P dequeue() {
    P x;
    x = Q[head];
    head = (head+1)%LEN;
    return x;
}

int main() {
    int n, q;
    int i;
    int sumtime = 0;
    P u;
    scanf("%d %d", &n, &q);
    
    for ( i = 1; i <= n; i++ ) {
        scanf("%s", Q[i].name);
        scanf("%d", &Q[i].t);
    }

    head = 1;
    tail = n + 1;

    while ( head != tail ) {
        u = dequeue();
        if ( u.t > q ) {
            u.t -= q;
            enqueue(u);
            sumtime += q;
        } else {
            sumtime += u.t;
            printf("%s %d\n", u.name, sumtime); 
        }
    }

    return 0;
}


Measured memory_bytes: 12756
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MOD=1000000007;
#define INF 1LL<<30
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define all(x) (x).begin(),(x).end()


int main(){
    ll K,A,B;
    cin>>K>>A>>B;

    ll have=1;

    ll a=min(K,A-1);
    have+=a;
    K-=a;
    if(K==0){
        cout<<have<<endl;
        return 0;
    }

    if(A+2<=B){
        ll cnt=K/2;
        have+=cnt*(B-A);
        if(K%2==1) have++;
        cout<<have<<endl;
    }
    else cout<<have+K<<endl;

}



Measured memory_bytes: 3604
a,b=gets(p).split("\n\n");
c=[0]*2000;d=[0]*2000;
ans=[];
a.split.map{|s|l=s.to_i;c[l]+=1}
b.split.map{|s|b=s.to_i;ans<<b if c[b]>0;d[b]+=1}
ans=ans.sort.uniq;
ans.map{|a|puts "#{a} #{c[a]+d[a]}"}


Measured memory_bytes: 6892
#include<stdio.h>
#include<math.h>

int main(){
  int A[10000];
  int prime=0,fl=0,i,j,num;

  for(i=0;i<10000;i++){
    if(scanf("%d",&A[i])==EOF) break;
    num++;
  }

  for(j=0;j<num;j++){
  for(i=2;i<1+sqrt(A[j]);i++){
    if(A[j]==2){
      fl=0;
      break;
    }
    if(A[j]%i==0){
      fl = 1;
      break;
    }
  }

  if(fl==0) prime++;
  fl = 0;
  }

printf("%d\n",prime);

  return 0;
}

Measured memory_bytes: 632
n,m=map(int, input().split())
d=dict()
for i in range(m):
    a,b=map(int, input().split())
    d[a]=d.get(a,0)+1
    d[b]=d.get(b,0)+1
for i in range(n):
    print(d.get(i+1,0))

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

#define rep(i, n) for (int i = 0; i < n; i++)
#define vi vector<int>

#define ll long long
#define vl vector<ll>
#define vll vector<vl>

const int INF = 1e9;

ll mod=998244353;

ll beki(ll x, ll a)
{
	if(x==0) return 0;
	if(a==0) return 1;
	if(a==1) return x;
	ll tmp=beki(x, a/2);
	tmp=tmp*tmp%mod;
	if(a%2==0) return tmp;
	else return tmp*x%mod;
}

ll kosu[100010];

int main() {
	int n;
	cin >> n;
	ll x;
	cin >> x;
	if(x!=0)
	{
		cout << '0' << endl;
		return 0;
	}
	rep(i, n-1)
	{
		cin >> x;
		kosu[x]++;
	}
	if(kosu[0]!=0)
	{
		cout << '0' << endl;
		return 0;
	}
	ll ans=1;
	kosu[0]++;
	for(int i=1; i<=n-1; i++)
	{
		if(kosu[i]>0)
		{
			ans=ans*beki(kosu[i-1], kosu[i])%mod;
		}
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
 
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define endl "\n"
#define int long long

const int N=21;
const int MOD=1e9+7;

int n;
int a[N][N];
int cache[N][1<<N];

int dp(int idx, int mask)
{
	if(idx==n)
	{
		if((mask+1)==(1<<n))
			return 1;
		return 0;
	}
	int &ans=cache[idx][mask];
	if(ans!=-1)
		return ans;
	ans=0;
	for(int i=0;i<n;i++)
	{
		if((mask>>i)&1)
			continue;
		if(a[idx][i]==0)
			continue;
		ans+=dp(idx+1, mask|(1<<i));
	}
	ans%=MOD;
	return ans;
}

int32_t main()
{
	IOS;
	memset(cache, -1, sizeof(cache));
	cin>>n;
	for(int i=0;i<n;i++)
		for(int j=0;j<n;j++)
			cin>>a[i][j];
	int ans=dp(0, 0);
	cout<<ans;
	return 0;
}

Measured memory_bytes: 344448
import java.util.*;
class Main{
    public static void main(String[] args){
        Scanner scan = new Scanner(System.in);

        int N = scan.nextInt();

        if(N%7 == 0 || N%4 == 0){
            System.out.println("Yes");
            System.exit(0);
        }
        while(N>=4){
            N -= 4;
            if(N%7 == 0){
                System.out.println("Yes");
                System.exit(0);
            }
        }
        System.out.println("No");
    }
}


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

using namespace std;

const int MAX = 222;
int N, M, R;
int r[MAX];
int dp[1 << 10][10];
vector<pair<int, int>> G[MAX];
int minDist[MAX];
int memo[10][10];

int dijkstra(int st, int ed) {
    fill(minDist, minDist + MAX, 1e9);
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    pq.push({0, st});
    minDist[st] = 0;
    while (!pq.empty()) {
        auto e = pq.top(); pq.pop();
        for (pair<int, int> p : G[e.second]) {
            int nxtCost = e.first + p.second;
            if (minDist[p.first] <= nxtCost) {
                continue;
            }
            minDist[p.first] = nxtCost;
            pq.push({nxtCost, p.first});
        }
    }
    return minDist[ed];
}

int main() {
    cin >> N >> M >> R;
    for (int i = 0; i < R; i++) {
        cin >> r[i];
        r[i]--;
    }
    for (int i = 0; i < M; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        a--;b--;
        G[a].push_back({b, c});
        G[b].push_back({a, c});
    }
    assert(R <= 8);
    int ans = 1e9;
    vector<int> vec(R);
    iota(vec.begin(), vec.end(), 0);
    memset(memo, -1, sizeof(memo));
    do {
        int now = -1;
        int buf = 0;
        for (int e : vec) {
            if (now != -1)  {
                if (memo[now][e] == -1) {
                    memo[now][e] = dijkstra(r[now], r[e]);
                }
                buf += memo[now][e];
            }
            now = e;
        }
        ans = min(ans, buf);
    } while (next_permutation(vec.begin(), vec.end()));
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 768
#include <numeric>
#include <bits/stdc++.h>
#include <utility>
#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <math.h>
#include <string>
#define ll long long
#define ull unsigned long long
#define make(type,x) type x; cin>>x
#define make2(type,x,y) type x,y; cin>>x>>y
#define fr(x,y) for(long long x=0;x<y;x++)
#define makevec(x,y,n) vector <x> y(n); for(ll i=0;i<n;i++) cin>>y[i]
#define M (ll)1000000007
#define MM (ll) 1e8
#define INF (ll) 1e18

# define IOS ios_base::sync_with_stdio(false); cin.tie(NULL)

using namespace std;

template <typename T>
T modpow(T base, T exp, T modulus) {
  base %= modulus;
  T result = 1;
  while (exp > 0) {
    if (exp & 1) result = (result * base) % modulus;
    base = (base * base) % modulus;
    exp >>= 1;
  }
  return result;
}
bool sortbysec(const pair <ll,ll> &a,const pair <ll,ll> &b){
    return a.second<b.second;
}

struct cmp {
	bool operator() (const pair<int, int> &a, const pair<int, int> &b) const {
		int lena = a.second - a.first + 1;
		int lenb = b.second - b.first + 1;
		if (lena == lenb) return a.first < b.first;
		return lena > lenb;
	}
};


struct c_h {
    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        x ^= FIXED_RANDOM;
        return x ^ (x >> 16);
    }
};

ll calcpow(ll x, ll y)
{
    ll temp;
    if(y == 0)
        return 1;
    temp = calcpow(x, y / 2);
    if (y % 2 == 0)
        return temp * temp;
    else
    {
        if(y > 0)
            return x * temp * temp;
        else
            return (temp * temp) / x;
    }
}
ll gcd(ll a, ll b){
    if(b==0) return a;
    return gcd(b,a%b);

}
ll egcd(ll a, ll b, ll &x,ll &y){
    if(b==0){
        x=1;
        y=0;
        return a;
    }
    ll x1;
    ll y1;
    ll g=egcd(b,a%b,x1,y1);
    x=y1;
    y=x1-y1*(a/b);
    return g;
}


bool isprime(ll a){
bool flag=1;
for(ll i=2;i*i<=a;i++){
    if(a%i==0) {flag=0; break;}
}
return flag;
}
ll n,m;
bool ok(ll a,ll b){
    return a>=0&&b>=0&&a<n&&b<m;
}
ll dx[8]={1,0,-1,0,1,-1,1,-1};
ll dy[8]={0,1,0,-1,1,-1,-1,1};

int main(){
    IOS;
    make(ll,n);
    makevec(ll,a,n);
    vector <ll> rat(9);
    for(auto x : a){
        ll y=(x)/400;
        if(y>8) y=8;
        rat[y]++;
    }
    ll c=0;
    fr(i,8) if(rat[i]>0) c++;
    if(rat[8]>0 && c==0) cout<<c+1<<" ";
    else cout<<c<<" ";
    cout<<c+rat[8]<<endl;

    return 0;
}


Measured memory_bytes: 3616
n,a,b,c,d = map(int,input().split())
s = input()

e = 'Yes'
f = 0
g = 1

if c < d:
    for i in range(b-1,d-1):
        if s[i]=='#' and s[i+1]=='#':
            e ='No'
    if e =='Yes':
        for j in range(a-1,b-1):
            if s[j]=='#' and s[j+1]=='#':
                e ='No'
                        
if c > d:
    for i in range(a-1,c-1):
        if s[i]=='#' and s[i+1]=='#':
            f = 1
    
    for j in range(b-2,d-1):
        if s[j]=='.' and s[j+1]=='.' and s[j+2]=='.':
            g = 0

    if g == 0 and f ==0:
        e ='Yes'
    else:
        e ='No'
            
print(e)           

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

#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define ll long long

int bs_upper_bound(int a[], int n, int x) {
    int l = 0;
    int h = n; // Not n - 1
    while (l < h) {
        int mid =  l + (h - l) / 2;
        if (x >= a[mid]) {
            l = mid + 1;
        } else {
            h = mid;
        }
    }
    return l;
}

int bs_lower_bound(int a[], int n, int x) {
    int l = 0;
    int h = n; // Not n - 1
    while (l < h) {
        int mid =  l + (h - l) / 2;
        if (x <= a[mid]) {
            h = mid;
        } else {
            l = mid + 1;
        }
    }
    return l;
}

bool sortbysec(const pair<int,int> &a,const pair<int,int> &b) 
{ 
    return (a.second < b.second); 
} 

ll n,k;
vector<ll> a;
ll mod=1e9+7;

int main()
{
    IOS;
    cin>>n>>k;
    for(int i=0;i<n;i++){
        ll x;
        cin>>x;
        a.push_back(x);
    }
    ll dp[k+2];
    for(int i=0;i<=k;i++)
        dp[i]=0;
    dp[0]=1;
    ll t[k+2];
    for(int i=0;i<n;i++){
        for(int j=0;j<=k+1;j++)
            t[j]=0;
        for(int j=k;j>=0;j--){
            int l=j+1;
            int r=min(j+a[i],k);
            if(l<=r){
                t[l]=(t[l]+dp[j])%mod;
                t[r+1]=(t[r+1]-dp[j]+mod)%mod;  
            }
        }
        ll p=0;
        for(int j=0;j<=k;j++){
            p=(p+t[j])%mod;
            dp[j]=(dp[j]+p)%mod;
        }
    }
    cout<<dp[k];
}


Measured memory_bytes: 5192
//include
//------------------------------------------
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <fstream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <string>
#include <cstring>
#include <ctime>


using namespace std;

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

//math
//-------------------------------------------
template<class T> inline T sqr(T x) { return x*x; }

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

//container util
//------------------------------------------
#define ALL(a)  (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define MP make_pair
#define SZ(a) int((a).size())
#define EACH(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define EXISTch(s,c) ((((s).find_first_of(c)) != std::string::npos)? 1 : 0)//cがあれば1 if(1)
#define SORT(c) sort((c).begin(),(c).end())

//repetition
//------------------------------------------
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define rep(i,n)  FOR(i,0,n)
#define loop(n) FOR(i,0,n)
#define rrep(i,a,b) for(int i=(a);i>=(b);--i)
//constant
//--------------------------------------------
const double EPS = 1e-10;
const double PI = acos(-1.0);
const int INF = (int)1000000007;
const LL MOD = (LL)1000000007;//10^9+7
const LL INF2 = (LL)100000000000000000;//10^18

int main()
{
	while (1) {
		int n; cin >> n;
		if (n == 0)break;

		vector<int> s(n);

		double sum = 0;
		for (int i = 0; i < n; i++) {
			cin >> s[i];
			sum += s[i];
		}

		double ave = sum / (double)n;

		double sum2 = 0.0;

		for (int i = 0; i < n; i++) {
			sum2 += (s[i] - ave)*(s[i] - ave);
		}

		double hensa=sqrt(sum2 / (double)n);

		cout << fixed << setprecision(12);
		cout << hensa << endl;
	}
	

	

	return 0;
}


Measured memory_bytes: 3276
n=int(input())
d=dict()
for i in range(n):
    s=input()
    if s not in d.keys():
        d[s]=-1
    else:
        d[s]-=1

a=sorted(d.items(),key=lambda x:(x[1],x[0]))
for k,v in a:
    if v!=a[0][1]:
        break
    print(k)

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

int main(){
long long n,ans;
 cin>>n;
  ans=0;
  vector<long long>a(100001),b(n);
for(int i=0;i<n;i++){
cin>>b[i];
if(b[i]>100000){
b[i]=0;
ans++;
}
  a[b[i]]++;
}
  for(int i=1;i<100001;i++){
  if(a[i]>i){
  while(a[i]!=i){
  a[i]--;
  ans++;
  }
  }
  else if(a[i]==i){
  continue;
  }
  else{
  while(a[i]!=0){
  a[i]--;
  ans++;
  }
 }
  }
cout<<ans<<endl;
}


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

using namespace std;
using i64 = long long;

int main() {
    std::ios::sync_with_stdio(false); 
    cin.tie(nullptr);
    
    int N;
    cin >> N;
    vector<int> A(N), B(N);
    for (int i = 0; i < N; ++i) {
        cin >> A[i];
    }
    for (int i = 0; i < N; ++i) {
        cin >> B[i];
    }
    i64 suma = accumulate(begin(A), end(A), 0LL);
    i64 sumb = accumulate(B.begin(), B.end(), 0LL);
    if (suma < sumb) {
        cout << -1 << "\n";
        return 0;
    }
    vector<int> diff(N, 0);
    for (int i = 0; i < N; ++i) {
        diff[i] = A[i] - B[i];
    }
    sort(begin(diff), end(diff));
    vector<int> changed(N, 0);
    for (int i = 0, j = N - 1; i < N; ++i) {
        if (diff[i] < 0) {
            changed[i] = 1;
        }
        while (diff[i] < 0) {
            int mn = min(-diff[i], diff[j]);
            diff[j] -= mn;
            changed[j] = 1;
            diff[i] += mn;
            if (diff[j] == 0) {
                --j;
            }
        }
    }
    cout << accumulate(begin(changed), end(changed), 0) << "\n";

    return 0;
}

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

void Output(int sum){

  //cout << sum << '=';

  if((int)(sum/1000) != 0){
    if((int)(sum/1000) != 1){
      cout << sum/1000;
    }
    cout << 'm';
  }
  sum = sum%1000;

  if((int)(sum/100) != 0){
    if((int)(sum/100) != 1){
      cout << sum/100;
    }
    cout << 'c';
  }
  sum = sum%100;

  if((int)(sum/10) != 0){
    if((int)(sum/10) != 1 ){
      cout << sum/10;
    }
    cout << 'x';
  }
  sum = sum%10;

  if(sum != 0){
    if(sum != 1){
      cout << sum;
    }
    cout << 'i';
  }

  cout << endl;
}

int main(){

  int n;
  int sum;
  int num;
  char in;

  cin >> n;
  getchar();

  for(int i=0; i<n; i++){
    sum = 0;
    num = 1;
    //getchar();
    while(scanf("%c",&in) && in!='\n'){

      if(in == 'm'){
        sum += num*1000;
        num = 1;
      }
      else if(in == 'c'){
        sum += num*100;
        num = 1;
      }
      else if(in == 'x'){
        sum += num*10;
        num = 1;
      }
      else if(in == 'i'){
        sum += num;
        num = 1;
      }
      else if(in != ' '){
        num = in-'0';
      }

    }

    Output(sum);

  }



  return 0;
}

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

using namespace std;

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

#define all(x) x.begin(),x.end()

const ll mod = 1e9+7;
const ll INF = 1e9;
const ll MAXN = 1e9;

int main()
{
	ll n,a,b;
	cin>>n>>a>>b;
	vector<ll> x(n);
	for(int i = 0; i < n; i++){
		cin>>x[i];
	}

	ll ans = 0;
	for(int i = 1; i < n; i++){
		if((x[i]-x[i-1])*a < b)
			ans += (x[i]-x[i-1])*a;
		else
			ans += b;
	}
	cout<<ans<<endl;

	return 0;
}

Measured memory_bytes: 1024
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<vector>
#include<functional>
#include<iomanip>
#include<cmath>
#include<queue>
#include<limits>
#include<cassert>
#include<set>
#include<tuple>
#include<map>
#define YES cout<<"YES"<<endl
#define NO cout<<"NO"<<endl
#define Yes cout<<"Yes"<<endl
#define No cout<<"No"<<endl
#define None cout<<"None"<<endl
typedef long long ll;
using namespace std;

int main() {
	int X; cin >> X;
	int ans = 1;
	
	for (int i = 2; i <= X; ++i) {
		for (int j = 2; j <= X; ++j) {
			int	k = pow(i,j);
			if (k <= X && k > ans ) ans = k;
		}
	}
	cout << ans;
}


Measured memory_bytes: 256
#!/usr/bin/env python3

import sys
# import math
# import re                                    # re.compile(pattern) => ptn obj; p.search(s), p.match(s), p.finditer(s) => match obj; p.sub(after, s)
# from collections import deque                # deque class. deque(L): dq.append(x), dq.appendleft(x), dq.pop(), dq.popleft(), dq.rotate()
# from collections import defaultdict          # subclass of dict. defaultdict(facroty)
# from collections import Counter              # subclass of dict. Counter(iter): c.elements(), c.most_common(n), c.subtract(iter)
# from heapq import heapify, heappush, heappop # built-in list. heapify(L) changes list in-place to min-heap in O(n), heappush(heapL, x) and heappop(heapL) in O(lgn).
# from heapq import nlargest, nsmallest        # nlargest(n, iter[, key]) returns k-largest-list in O(n+klgn).
# from itertools import product                # product(iter, repeat=n)
# from itertools import accumulate             # accumulate(iter[, f])
# from functools import reduce                 # reduce(f, iter[, init])
# from bisect import bisect_left, bisect_right # bisect_left(a, x, lo=0, hi=len(a)) returns i such that all(val<x for val in a[lo:i]) and all(val>-=x for val in a[i:hi]).
# from fractions import gcd                    # for Python3.4.3


def main():
    mod = 10000007                  # 10^9+7
    inf = float('inf')
    input = sys.stdin.readline      # 改行文字が残ることに注意
    sys.setrecursionlimit(10**6)    # 1000 -> 1000000
    def ii():  return int(input())
    def mi():  return map(int, input().rstrip().split())
    def lmi(): return list(map(int, input().rstrip().split()))
    def li():  return list(input().rstrip())
    
    
    n = ii()
    s = input().rstrip()
    print("".join(list(map(chr, map(lambda x: x+n if x+n<=ord('Z') else ord('A')+(n-1)-(ord('Z')-x), (map(ord, s)))))))

if __name__ == "__main__":
    main()

Measured memory_bytes: 3188
import java.util.Arrays;
import java.util.Scanner;
import java.util.stream.IntStream;

public class Main {

	public static void main(String[] args) {
		try (Scanner scanner = new Scanner(System.in)) {
			int n = scanner.nextInt();
			int[] p = new int[n];
			int sum = IntStream.range(0, n).map(i -> p[i] = scanner.nextInt()).sum();
			System.out.println(sum - Arrays.stream(p).max().getAsInt() / 2);
		}
	}
}


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

int main(){
  
  long long N, i, a, Sum=0, t;
  cin>>N;
  cin>>t;
  for(i=0; i<N-1; i++){
    
    cin>>a;
    if(a<t){//後ろの人の方が小さい場合
      Sum+=t-a;
    }else{//後ろの人が前の人以上の場合
      t=a;
    }
  }
  cout<<Sum<<endl;
  return 0;
}

Measured memory_bytes: 3592
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.Map.Entry;
import java.util.PriorityQueue;
import java.util.Scanner;

class Main {

    static final int MOD = 1000000007;
    static final int INF = 1 << 30;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        String S = sc.next();
        long ans = 0;
        for(int i=3;i<=S.length();i++){
            if(S.substring(i-3, i).equals("ABC"))ans++;
        }
        System.out.println(ans);
    }
}


Measured memory_bytes: 24916
from copy import deepcopy
def f(num,N,S):
    alphabet = ["a","b","c","d","e","f","g","h","i","j","k","l","m","n","o","p","q","r","s","t"]
    if N == num:
        S.sort()
        for i in range(len(S)):
            print(S[i])
        return
    else:
        tmp = []
        length = len(S)
        for i in range(length):
            ttmp = list(S[i])
            ttmp.sort()
            tttmp = alphabet.index(ttmp[-1])
            for j in range(tttmp+2):
                tmp.append(S[i]+alphabet[j])
                    
        S = deepcopy(tmp)
        S.sort()
        f(num+1,N,S)

N = int(input())
f(1,N,["a"])

Measured memory_bytes: 16224
#include <bits/stdc++.h>
#include <vector>
#include <iostream>
#include <map>
#include <cmath>
#include <string>
using namespace std;

#define rep(i, n) for (int i = 1; i <= (n); ++i)
#define REP(i,a,b)for(int i=(int)(a);(i)<(int)(b);i++)
typedef long long ll;


ll gcd(ll a, ll b) { return b ? gcd(b, a%b) : a; }
ll lcm(ll c, ll d) { return c / gcd(c, d) * d; }

int main() {
  int n, k;
  cin >> n >> k;

  double prob = 0;
  rep(i, n) {
      int win = i; int count = 1;
      while (win<k)
      {
          /* code */
          win *= 2;
          count *= 2;
      }
      prob += 1/((double)count*n);
  }
  cout << setprecision(15) << prob << endl;
}

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

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



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

using namespace std;

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

int main() {
    int n, m;
    ll ans = 0;
    cin >> n >> m;
    priority_queue<int> q;
    rep(i, n){
        int t; cin >> t;
        q.push(t);
    }
    rep(i, m){
        q.push(q.top()/2);
        q.pop();
    }
    while(!q.empty()){
        ans += q.top();
        q.pop();
    }
    cout << ans << endl;
}


Measured memory_bytes: 892
import java.util.*;

public class Main{
      public static void main(String[] args) {
            Scanner sc = new Scanner(System.in);
            int N = sc.nextInt();
            int[] list = new int[N];
            int ans = 0;
            for(int i = 0; i < N; i++){
              list[i] = sc.nextInt();
            }
            for(int i = 0; i < N; i++){
              for(int j = i + 1; j < N; j++){
                ans += list[i] * list[j];
              }
            }
            System.out.println(ans);
          }
}

Measured memory_bytes: 21716
from heapq import heappop,heappush
n,m,s,t = (int(i) for i in input().split())
x,y = [[] for i in range(n+1)],[[] for i in range(n+1)]
for i in range(m):
    u,v,a,b = (int(i) for i in input().split())
    x[u].append((v,a))
    x[v].append((u,a))
    y[u].append((v,b))
    y[v].append((u,b))
def dijkstra(n,s,adj):
	dis = [float("inf") for i in range(n+1)]
	dis[s],q = 0,[[0,s]]
	while q:
		num2,num = heappop(q)
		for i,j in adj[num]:
			if dis[i]>num2+j:
				dis[i] = num2+j
				heappush(q,[dis[i],i])
	return dis
X,Y,z = dijkstra(n,s,x),dijkstra(n,t,y),[]
for i in range(1,n+1): z.append((X[i]+Y[i],i))
z,k = sorted(z),0
for i in range(n):
    while z[k][1]<=i: k+=1
    print(10**15-z[k][0])

Measured memory_bytes: 90572
import java.util.Scanner;
 
public class Main {
  public static void main(String[] args) {
    Scanner scan = new Scanner(System.in);
    
    String strT = scan.next();
    String strX = scan.next();
    
    double t = Double.parseDouble(strT);
    double x = Double.parseDouble(strX);
    
    double realTime = t / x;
    
    System.out.print(realTime);
  }
}

Measured memory_bytes: 23764
#include<stdio.h>

#define N 1000000

int main(){
  int A[N],i,j=0,n,tmp;

  scanf("%d",&n);
  
  for(i=0;i<n;i++){
    scanf("%d",&A[i]);
  }

  for(i=0;i<n-1;i++){
    if(A[n-1]>=A[i]){
      tmp=A[i];
      A[i]=A[j];
      A[j]=tmp;
      j++;
    }
    
  }

  tmp=A[n-1];
  A[n-1]=A[j];
  A[j]=tmp;
  
  for(i=0;i<j;i++){
    printf("%d",A[i]);
    printf(" ");
  }
  
    printf("[%d] ",A[j]);

for(i=j+1;i<n-1;i++){
    printf("%d",A[i]);
    printf(" ");
  }
  
 printf("%d\n",A[n-1]);
  return 0;
}

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

void proc(){
  int w,h;
  int x,y;
  int data[500][500];
  cin>>w>>h;
  memset(data,0,sizeof(data));
  rep(i,n){
    cin>>x>>y;
    data[--x][--y]=1;
  }
  cin>>x>>y;
  rep(i,w){
    rep(j,h){
      if(i>=1)data[i][j]+=data[i-1][j];
      if(j>=1)data[i][j]+=data[i][j-1];
      if(i>=1&&j>=1)data[i][j]-=data[i-1][j-1];
    }
  }
  int M=0;
  for(int i=x-1;i<w;++i){
    for(int j=y-1;j<h;++j){
      int cnt=data[i][j];
      if(i-x>=0)cnt-=data[i-x][j];
      if(j-y>=0)cnt-=data[i][j-y];
      if(i-x>=0&&j-y>=0)cnt+=data[i-x][j-y];
      if(M<cnt)M=cnt;
    }
  }
  cout<<M<<endl;
}
int main(){
 while(true){
  cin>>n;
  if(!n)return 0;
  proc();
 }
}

Measured memory_bytes: 2140
#include <bits/stdc++.h>
#define PI 3.14159265359
using namespace std;

typedef long long int ll;

#define all(x) x.begin(),x.end()

const ll mod = 1e9 + 7;
const ll INF = 1e9;
const ll MAXN = 1e9;

int main()
{
	int n;
	cin >> n;
	vector<ll> a(n), t(n);
	for (int i = 0; i < n; i++) {
		cin >> t[i] >> a[i];
	}

	ll T = 1, A = 1;
	for (int i = 0; i < n; i++) {
		//ll co = max(ceil((double)T/t[i]),ceil((double)A/a[i]));　これでWAになる理由が分からない...
		ll x = T / t[i];
		ll y = A / a[i];
		if (T % t[i] != 0) x++;
		if (A % a[i] != 0) y++;
		ll co = max(x, y);
		T = co * t[i];
		A = co * a[i];
	}

	cout << T + A << endl;

	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll a7=10000000007;

int main()
{
  ll d,n;cin>>d>>n;
  ll ans=n+n/100;
  if(ans%100==0)ans++;
  for(ll i=0;i<d;i++){
    ans*=100;
  }
  cout<<ans<<endl;
  return 0;
}


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

int main() {
  long a, b;
  cin >> a >> b;
  long c;
  if(a<b) {
    c=b;
  }else{
    c=a;
  }
  for(long i=c;i>=0;i--) {
    if(labs(a-i) == labs(b-i)) {
      cout << i << endl;
      return 0;
    }
  }
  cout << "IMPOSSIBLE" << endl;
  return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int main(){
  int n;
  int num[1001], p[1001], q[1001], r[1001], cal[1001];
  
  while(cin >> n, n){
    for(int i = 0 ; i < 1001 ; i++){
      num[i] = p[i] = q[i] = r[i] = cal[i] = 0;
    }
    
    for(int i = 0 ; i < n ; i++){
      cin >> num[i] >> p[i] >> q[i] >> r[i];
      cal[i] = p[i]*4 + q[i]*9 + r[i]*4;
    }
   
    int P, Q, R, C;
    cin >> P >> Q >> R >> C;
    bool flag = 1;
    for(int i = 0 ; i < n ; i++){
      if(p[i] <= P && q[i] <= Q && r[i] <= R && cal[i] <= C){
	cout << num[i] << endl;
	flag = 0;
      }
    }
    if(flag) cout <<"NA"<<endl;
  }
  return 0;
}

  

Measured memory_bytes: 884