akhauriyash/Code-Regression huggingface dataset:
#define _CRT_SECURE_NO_WARNINGS
#include "bits/stdc++.h"
using namespace std;
#define rep(i, n) for(int i=0; i<(n); ++i)
#define FOR(i, m, n) for(int i=(m); i<(n); ++i)
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(),(x).end()
#define mp make_pair
#define pb push_back
#define Cout(x) cout << (x) << endl
#define Cout2(x, y) cout << (x) << " " << (y) << endl
#define dump(x) cerr << #x << " = " << (x) << endl;
typedef long long LL;
typedef vector<int> VI;
typedef vector<LL> VL;
typedef vector<string> VS;
typedef vector<bool> VB;
typedef vector<vector<int>> VVI;
typedef pair<int, int> PII;
const int inf = (int)1e9;
const double pi = acos(-1.0);

int main() {
	int n, q; cin >> n >> q;
	VI y(n + 1); VS name(n + 1);
	y[0] = 0; name[0] = "kogakubu10gokan";
	rep(i, n)cin >> y[i + 1] >> name[i + 1];

	string ans;
	rep(i, n + 1) {
		if (q < y[i]) { ans = name[i - 1]; break; }
	}
	cout << (ans.empty() ? name[n] : ans) << endl;
}


Measured memory_bytes: 3200
from collections import defaultdict

def pr(n):
    d = defaultdict(lambda:0)
    i = 2
    while (n > 1) and (i < int(n**0.5)+1):
        if n % i == 0:
            d[i] += 1
            n //= i
        else:
            i += 1
            
    if n > 1:
        d[n] += 1
    return d

def t(x):
    i = 1
    while x >= i:
        x -= i
        i += 1
    return i-1

n = int(input())
d = pr(n)
r = 0
for i in d.values():
    r += t(i)
print(r)

Measured memory_bytes: 9748
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <set>
//#inlcude<stringstream>
#define ll long long
#define MODD 1000000007
using namespace std;

int main() {
    //
    int k,x;cin >>k>>x;
    int flag=0;
    for(int i=x-k+1;i<=x+k-1;i++){
        if(flag==0)cout<<i,flag=1;
        else if(flag)
        cout<<" "<<i;
    }
    cout<<endl;
    return 0;
}


Measured memory_bytes: 256
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include <bits/stdc++.h>
using namespace std;

const int INF = 2000000000;
const int MAX_N = 100005;

int n, k;
int x[MAX_N];

int main()
{
	ios::sync_with_stdio(false);
	cin >> n >> k;
	for (int i = 0; i < n; i++)
		cin >> x[i];
	int result = INF;
	for (int l = 0, r = k - 1; r < n; l++, r++)
	{
		result = min(result, abs(x[l]) + abs(x[r] - x[l]));
		result = min(result, abs(x[r]) + abs(x[r] - x[l]));
	}
	cout << result << endl;
}

Measured memory_bytes: 640
def binary_search(A, x):
    left, right = 0, len(A) - 1
    while left <= right:
        mid = (left + right) // 2
        if A[mid] == x:
            return True
        elif A[mid] < x:
            left = mid + 1
        elif A[mid] > x:
            right = mid - 1


input()
AA = list(map(int, input().split()))
input()
T = list(map(int, input().split()))

count = 0
for t in T:
    if binary_search(AA, t):
        count += 1

print(count)



Measured memory_bytes: 16708
#include <iostream>
#include <cmath>
#include <vector>
#include <map>
#include <cstdio>
#include <algorithm>
#include <functional>
#include <string>
#include <numeric>
#include <stack>

using namespace std;

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

#define rep(i, a, N) for(int i = a; i < N; i++)
#define rrep(i, a, N) for(int i = a; i >= N; i--)

int main() {
    int N;
    cin >> N;
    
    int ans = 0;
    while (N != 0) {
        if (N % 10 == 2) ans++;
        N /= 10;
    }
    cout << ans << endl;
}

Measured memory_bytes: 256
import math

N = int(input())
rcvr = [0, 0, 0, 0, 0]
i = 0
while (i < 5):
    rcvr[i] = int(input())
    i += 1

narrow = min(rcvr)
ans = (N / narrow)
if (ans < 1):
    ans = 1
ans = math.ceil(ans)
ans += 4

print(ans)

Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
void call(int n){
	int i = 1;
CHECK_NUM:
	int x = i;
	if ( x % 3 == 0 ){
		cout << " " << i;
		goto END_CHECK_NUM;
	}
INCLUDE3:
	if ( x % 10 == 3 ){
		cout << " " << i;
		goto END_CHECK_NUM;
	}
	x /= 10;
	if ( x ) goto INCLUDE3;
END_CHECK_NUM:
	if ( ++i <= n ) goto CHECK_NUM;
	cout << endl;
}
int main(){
	int n;cin>>n;
	call(n);
	return 0;
}


Measured memory_bytes: 3124
#include <stdio.h>
#include <algorithm>
#include <iostream>
#include <limits.h>
#include <math.h>
#include <queue>
#include <set>
#include <stdlib.h>
#include <string>
#include <vector>
#include <cstdio>
#define ll long long
#define rep2(i,a,b) for(int i=a;i<=b;i++)
#define rep(i,n) for(int i=0;i<n;i++)
#define rep3(i,a,b) for(int i=a;i>=b;i--)
#define REP(e,v) for(auto e:v)
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pq priority_queue<int>
#define pqg priority_queue<int,vector<int>,greater<int>()>
#define pb push_back
#define vec vector<int>
#define vecll vector<ll>
#define bs binary_search
#define All(c) (c).begin(),(c).end()
#define mp make_pair
using namespace std;
int in(){int x;scanf("%d",&x);return x;}
string stin(){string s;cin>>s;return s;}
ll lin(){ll x;scanf("%lld",&x);return x;}
int main(){
    int n=in(),a=in(),b=in();
    vec x(n);
    rep(i,n)x[i]=in();
    sort(All(x),greater<int>());
    ll l=0,r=x[0]/b+1;
    while(l+1<r){
        ll k=(l+r)/2;
        int id=-1;
        ll sum=0;
        while(k*b<x[++id]){
            sum+=(x[id]-k*b+a-b-1)/(a-b);
        }
        if(sum>k)l=k;
        else r=k;
    }
    cout<<r<<endl;
}

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

long gcd(long n, long m) {
	if (n == 0)return m;
	if (n < m)swap(n, m);
	return gcd(n % m, m);
}


int main() {
	float a, b, c, d, e, f; cin >> a >> b >> c >> d >> e >> f;
	float m = -1;
	float s = 0, t = 0;
	e = e * 100 / (100 + e);
	for (int i = 0; i * a * 100 < f; i++) {
		for (int j = 0; (i * a + j * b) * 100 < f; j++) {
			if (i == 0 && j == 0)continue;
			for (int k = 0; (i * a + j * b) * 100 + c * k <= f; k++) {
				for (int l = 0; (i * a + j * b) * 100 + c * k + d * l <= f; l++) {
					float z = 100 * (c * k + d * l) / (c * k + d * l + (a * i + b * j) * 100);
					if (z < e && m < z) {
						m = z;
						s = (a * i + b * j) * 100 + c * k + d * l;
						t = c * k + d * l;
					}
					else if (z == e) {
						cout << (a * i + b * j) * 100 + c * k + d * l << " " << c * k + d * l;
						return 0;
					}
					else if (e < z)break;
				}
			}
		}
	}
	cout << s << " " << t;
}

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

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

string s;
int k,n;

int dp[300][300][301];

int main(){
  cin>>s>>k;
  n=s.size();
  FOR(d,1,n+1){
    FOR(init,0,n-d+1){
      REP(l,k+1){
	if(d==1)dp[init][init+d-1][l]=1;
	else if(l==0){
	  if(s[init]==s[init+d-1])
	    dp[init][init+d-1][0]=(d==2)?2:2+dp[init+1][init+d-2][0];
	  else
	    dp[init][init+d-1][0]=max(dp[init][init+d-2][0],dp[init+1][init+d-1][0]);
	}else{
	  if(s[init]==s[init+d-1]){
	    dp[init][init+d-1][l]=(d==2)?2:2+dp[init+1][init+d-2][l];
	  }else{
	    dp[init][init+d-1][l]=(d==2)?2:max(max(dp[init][init+d-2][l],dp[init+1][init+d-1][l]),2+dp[init+1][init+d-2][l-1]);
	  }
	}
      }
    }
  }
  cout<<dp[0][n-1][k]<<endl;
  return 0;
}


Measured memory_bytes: 104704
#include <iostream>
using namespace std;
int sum[11][11][11];
int nn[11];
int n,m,q;
int ans,ma;
int a[51],b[51],c[51],d[51];

void calc(int deep,int last){
 
  if(deep==n){
    for(int i = last; i <= m; i ++){
        nn[n]=i;
        ans=0;
       for(int j = 0; j < q; j++){
         if(nn[b[j]]-nn[a[j]]==c[j])ans+=d[j];
          }
      ma=max(ans,ma);
    }
  
  }else{
    for(int i = last; i <= m; i++){
      nn[deep]=i;
      calc(deep+1,i);
    }
  }
}
int main(){
  cin >> n >> m >> q;
  for(int i = 0; i < q; i++){
    cin >> a[i] >> b[i] >> c[i] >> d[i];
  }
  for(int i = 1; i <= m; i++){
 	nn[1]=i;
    calc(2,i);
  }
  cout << ma << endl;
}

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

//Compiler version g+ 6.3.0

int main()
{
    int a,b;
    char c;
    cin>>a>>c>>b;  
	if(c == '+'){
		cout<<a+b<<endl;
	}else if(c == '-'){
		cout<<a-b<<endl;
	}else if(c == '*'){
		cout<<a*b<<endl;
	}else{
		cout<<a/b<<endl;
	}
}

Measured memory_bytes: 256
#include <algorithm>
#include <iostream>
#include <vector>

using namespace std;

int main() {
  int n;
  cin >> n;
  vector<int> v(n);
  vector<int> c(n);
  for (int i = 0; i < n; i++) {
    cin >> v[i];
  }
  for (int i = 0; i < n; i++) {
    cin >> c[i];
  }
  int ans = 0;
  for (int i = 0; i < n; i++) {
    ans += max(v[i] - c[i], 0);
  }
  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF = 100000000;
const ll half_inf = 0x3f3f3f3f;
const ll inf = 0x7fffffff;
const ll mod = 998244353;
const ll maxn = 2000005;
int a[105]={0};
int main(){
	int q;
	scanf("%d",&q);
	int s=0;
	while(1){
		s+=1000;
		if(s>=q){
			printf("%d",s-q);
			return 0;
		}
	} 



	return 0; 
}





Measured memory_bytes: 3820
#include <iostream>
#include <queue>
#include <string>
#include <cstdio>
#include <cstring>
#include <utility>
using namespace std;
typedef pair<int, int> P;
char maze[1005][1005];
int d[1005][1005];
int dirx[4] = {0, -1, 0, 1};
int diry[4] = {1, 0, -1, 0};
int h, w, n, hard; 
int si, sj;
const int INF = 0x3f3f3f3f;
int tot = 0; 

void BFS(int ai, int aj){
    queue<P> que;
    for(int i = 0; i < h; i++){
        for(int j = 0; j < w; j++){
            d[i][j] = INF;
        }
    }
    que.push(P(ai, aj));
    d[ai][aj] = 0;
    while(!que.empty()){
        P a = que.front();
        que.pop();
        int x = a.first, y = a.second;
        if(maze[x][y]-'0' == hard){
            tot += d[x][y];
            si = x; sj = y;
            break;
        }
        for(int i = 0; i < 4; i++){
            int dx = x+dirx[i], dy = y+diry[i];
            if(dx>=0 && dx<h && dy>=0 && dy<w && maze[dx][dy]!='X' && d[dx][dy]==INF){
                d[dx][dy] = d[x][y]+1;
                que.push(P(dx, dy));
            }
        }
    }
}

int main(int argc, char const *argv[]){
    while(scanf("%d%d%d", &h, &w, &n) != EOF){
        getchar();
        for(int i = 0; i < h; i++){
            for(int j = 0; j < w; j++){
                scanf("%c", &maze[i][j]);
                if(maze[i][j] == 'S'){
                    si = i; sj = j;
                }
            }
            getchar();
        }
        tot = 0;
        hard = 1;
        for(int i = 0; i < n; i++){
            BFS(si, sj);
            hard++;
        }
        cout << tot << endl;
    }
    return 0;
}


Measured memory_bytes: 8160
#include <iostream>
#include <string>
#include <algorithm>
#include <cstdlib>
#include <cmath>
#include <queue>
#include <vector>
#include <set>
#include <map>
#include <numeric>

using namespace std;

int main(){
    vector<int> a(5);
    for(int i=0;i<5;i++)cin>>a[i];
    int k;
    cin>>k;
    for(int i=0;i<5;i++){
        for(int j=i+1;j<5;j++){
            if(a[j]-a[i]>k){
                cout<<":("<<endl;
                return 0;
            }
        }
    }
    cout<<"Yay!"<<endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define IO(i, o) freopen(i, "r", stdin), freopen(o, "w", stdout)

using namespace std;
int N, C, R, T, V, X;

int main(void){
	//IO("test.in", "test.out");
	V = INT_MAX;
	scanf("%d%d", &N, &T);
	for(int i = 0; i < N; i++){
		scanf("%d%d", &C, &R);
		if(C < V && R <= T) V = C, X = C;
	}
	if(V == INT_MAX) printf("TLE\n");
	else printf("%d\n", X);
}

Measured memory_bytes: 256
use std::env;
use std::io::*;
use std::str::*;
use std::mem;
use std::collections::HashMap;

fn read<T: FromStr>() -> T {
    let stdin = stdin();
    let s = stdin.bytes().map(|c| c.unwrap() as char)
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .collect::<String>();
    s.parse::<T>().ok().unwrap()
}
fn read_char() -> char {
    let c = read::<String>();
    let c = c.chars().collect::<Vec<char>>();
    c[0]
}
fn read_String_Vec() -> Vec<char> {
    let S = read::<String>();
    S.chars().collect::<Vec<char>>()
}

fn vecchar_to_String(Vs: Vec<char>) -> String {
    let mut S = String::new();
    for i in 0..Vs.len() {
        S.push(Vs[i]);
    }
    S
}

/*
A : 65
Z : 90
a : 97
z : 122
*/

/*
let N = read::<i32>();
let S = read::<String>();
let S = read_String_Vec();
let C = read_char();
*/

/*
 .to_string() : * -> String
 &*S          : String -> &str
*/

fn main() {
    // main の引数
    /*
        引数なしのときargs.len() = 1;
    */
    let args: Vec<String> = env::args().collect();

    let N = read::<usize>();
    let mut L: [u64; 3] = [0; 3];
    L[0] = 2;
    L[1] = 1;
    for n in 2..N+1 {
        L[n%3] = L[(n+1)%3] + L[(n+2)%3];
    }
    println!("{}", L[N%3]);
}


Measured memory_bytes: 4352
#include <algorithm>
#include <iostream>
#include <vector>

using namespace std;

const long long mod = 1e9 + 7ll;
const int N = 300 + 10;

long long dp[ N ][ N ][ N ];
int n, m;

int main( void ) {

	cin.sync_with_stdio( false );

	cin >> n >> m;
	dp[0][1][1] = 1;
	for ( int i = 0 ; i < m ; ++i ) {
		for ( int city = 1 ; city <= n ; ++city ) {
			for ( int cover = 1 ; cover <= n ; ++cover ) {
				long long &d = dp[ i ][ city ][ cover ];
				d %= mod;
				dp[ i+1 ][ city+1 ][ cover ] += ( ( n - city ) * d ) % mod;
				dp[ i+1 ][ city ][ cover ] += ( ( city - cover ) * d ) % mod;
				dp[ i+1 ][ city ][ city ] += ( cover * d ) % mod;
			}
		}
	}

	cout << dp[m][n][n] % mod << endl;

	return 0;
}

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

int n, k;
long long h[200010];

int main(){
	cin >> n >> k;
	for (int i = 0; i < n; ++i){
		cin >> h[i];
	}
	sort(h, h+n);
	long long ans = 0;
	for (int i = 0; i < n-k; ++i){
		ans += h[i];
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 1792
#include <bits/stdc++.h>
#include<iostream>
#include<math.h>
using namespace std;
int main()
{
    string s;
    cin >> s;
    int len = s.length();
    for (int i = 0; i < len; i++) {
        int ind = i + 1;
        if (ind % 2 != 0) {
            cout << s[i];
        }
    }
    cout << endl;
    return 0;
}

Measured memory_bytes: 512
#include<bits/stdc++.h>
#define ll long long
using namespace std;
float a[110];
int main()
{
    int n,pos=0,sum=0;
    scanf("%d",&n);
    for(int i=0; i<n; i++)
    {
        scanf("%f",&a[i]);
        sum+=a[i];
    }
    float av=sum/(n*1.0);
    float t=abs(a[0]-av);
    for(int i=1; i<n; i++)
    {
        if(abs(a[i]-av)<t)
        {
            pos=i;
            t=abs(av-a[i]);
        }
    }
    printf("%d\n",pos);
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i, n) for(int i = 0; i < (n); i++)
#define prtd(var, i) cout << fixed << setprecision(i) << var << endl;
using namespace std;

int main(){
    int a, b;
    cin >> a >> b;
    int ans = a*b - (a+b-1);
    cout << ans << endl;
} 

Measured memory_bytes: 256
ABCD = input()

A = int(ABCD[0])
B = int(ABCD[1])
C = int(ABCD[2])
D = int(ABCD[3])

if 7 == A+B+C+D:
    print(f'{A}+{B}+{C}+{D}=7')
elif 7 == A+B+C-D:
    print(f'{A}+{B}+{C}-{D}=7')
elif 7 == A+B-C-D:
    print(f'{A}+{B}-{C}-{D}=7')
elif 7 == A-B-C-D:
    print(f'{A}-{B}-{C}-{D}=7')
elif 7 == A+B-C+D:
    print(f'{A}+{B}-{C}+{D}=7')
elif 7 == A-B-C+D:
    print(f'{A}-{B}-{C}+{D}=7')
elif 7 == A-B+C+D:
    print(f'{A}-{B}+{C}+{D}=7')
elif 7 == A-B+C-D:
    print(f'{A}-{B}+{C}-{D}=7')


Measured memory_bytes: 9200
#include <bits/stdc++.h>
 
#define FOR(i,b,e) for(int i=(b); i <= (e); ++i)
#define FORD(i,b,e) for(int i=(b); i >= (e); --i)
#define SIZE(c) (int) (c).size()
#define FORE(i,c) FOR(i,0,SIZE(c)-1)
#define FORDE(i,c) FORD(i,SIZE(c)-1,0)
 
#define pb push_back
#define mp make_pair
#define st first
#define nd second
 
 
using namespace std;
 
typedef long long ll;
typedef pair <int,int> pii;
typedef pair <ll,ll> pll;
 
typedef vector <int> VI;
typedef vector <bool> VB;
typedef vector <pii> VP;
typedef vector <ll> VL;
typedef vector <pll> VPL;
 
typedef vector <VI> VVI;
typedef vector <VL> VVL;
typedef vector <VB> VVB;
typedef vector <VP> VVP;
 
const int MOD = 1000000007;
const int INF = 1000000001;
const ll LINF = 1000000000000000001LL;
 
struct FAU {
    VI p, r;
 
    FAU(int n): p(n,-1), r(n,0) {}
 
    int find(int x) {
        if (p[x] == -1) return x;
        return p[x] = find(p[x]);
    }
 
    void join(int x, int y) {
        x = find(x); y = find(y);
        if (x == y) return ;
 
        if (r[x] > r[y]) p[y] = x;
        else p[x] = y;
 
        if (r[x] == r[y]) ++r[y];
    }
};
 
/*************************************************************************/
 
int main() {
    ios_base::sync_with_stdio(0);
    
    int n;
    cin >> n;
    
    VI a(n), b(n);
    FOR(i,0,n-1) cin >> a[i];
    FOR(i,0,n-1) cin >> b[i];
    
    int xr = 0;
    for (int x : a) xr ^= x;
    
    multiset <int> s = {xr};
    for (int x : a) s.insert(x);
    
    for (int x : b) {
        if (!s.count(x)) {
            cout << -1;
            return 0;
        }
        
        s.erase(s.find(x));
    }
    
    int rest = *s.begin();
    
    int ans = n;
    
    VP pairs;
    
    FOR(i,0,n-1) {
        if (a[i] == b[i]) {
            ans--;
        } else {
            pairs.pb({a[i], b[i]});
        }
    }
 
    VI values;
    for (auto &e : pairs) {
        values.pb(e.st);
        values.pb(e.nd);
    }
    
    sort(values.begin(), values.end());
    values.resize(unique(values.begin(), values.end()) - values.begin());
 
    FAU fau(SIZE(values));
    for (auto &e : pairs) {
        int a = e.st, b = e.nd;
        
        int aid = lower_bound(values.begin(), values.end(), a) - values.begin();
        int bid = lower_bound(values.begin(), values.end(), b) - values.begin();
        
        fau.join(aid, bid);
    }
    
    int comps = 0;
    FORE(i,values) comps += (fau.find(i) == i);
    
    ans += comps;
    
    FOR(i,0,n-1) if (a[i] != b[i] && b[i] == xr) {
        ans--;
        break;
    }
    
    cout << ans;
 
    return 0;
}


Measured memory_bytes: 5760
#include<iostream>
using namespace std;
#define MAX 100001
#define NIL -1
struct Node {int p, l, r;};

Node T[MAX];
int n, D[MAX];

void print(int i) {
	cout << "node " << i << ": parent = " << T[i].p << ", ";
	cout << "depth = " << D[i] << ", ";
	
	//who are you?
	if (T[i].p == NIL) {
	cout << "root";
	}
	else if (T[i].l == NIL) {
	cout << "leaf";
	}
	else {
	cout << "internal node";
	}

	cout << ", [";

	for (int j = 0, k = T[i].l; k != NIL; j++, k = T[k].r) {
	if (j) cout << ", ";
	cout << k ;
	}
	
	cout << "]" << endl;
}

//?????°????????±??????map????????????
void make_d(int u, int p) {
	D[u] = p;
	if (T[u].l != NIL) {
	make_d(T[u].l, p+1);
	}
	if (T[u].r != NIL) {
	make_d(T[u].r, p);
	}
}

int main() {
	cin >> n;
	int par, child_sum, child;
	int left_for_next;
	//??????T??????????????????????????????
	for (int i=0;i<n;i++) {
	T[i].p = T[i].l = T[i].r = NIL;
	}

	for (int i=0;i<n;i++) {
	cin >> par >> child_sum;
	for (int j=0;j<child_sum;j++) {
	cin >> child;
	if (j==0) {
	T[par].l = child;
	}
	else {
	T[left_for_next].r = child;
	}
	//???????¨??????§??????????
	left_for_next = child;	//?¬????loop????????????????????????
	T[child].p = par;	
	}
	}
	int root;
	//root ??¢?????????
	for (int i=0;i<n;i++) {
	if (T[i].p == NIL) {
	root = i;
	break;
	}
	}

	make_d(root,0);

	for (int i=0;i<n;i++) {
	print(i);
 	}
	return 0;
}
	




 
	

Measured memory_bytes: 4660
#include <iostream>
#include <vector>
#include <stdio.h>
#include <stdlib.h>

using namespace std;

int main() {
	
	int a, b, c;
	scanf("%d%d%d", &a, &b, &c);

	if (abs(a - b) > abs(a - c)) {
		printf("B");
	}
	else {
		printf("A");
	}

	
}

Measured memory_bytes: 256
s = input()
n = len(s)
l_ = int((n-1)/2)
l = s[:l_]
lv = l[::-1]
r_ = int((n+3)/2)
r = s[r_-1:]
rv = r[::-1]
if l != rv or l != lv or r != rv:
    print("No")
    exit()
print("Yes")

Measured memory_bytes: 3064
#if 1
#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <queue>
#include <stack>
#include <array>
#include <deque>
#include <algorithm>
#include <utility>
#include <cstdint>
#include <functional>
#include <iomanip>
#include <numeric>
#include <assert.h>

#define in std::cin
#define out std::cout

int32_t H,W;
int32_t num[200][200];
constexpr int64_t INF = int64_t(200) * 200 * 100000*100;

template<typename T>
void fill_all(T& arr, const T& v) {
	arr = v;
}
template<typename T, typename ARR>
void fill_all(ARR& arr, const T& v) {
	for (auto& i : arr) { fill_all(i, v); }
}

int64_t dp[200][200][200];
int64_t func(int h1, int w1, int h2, int w2)
{
	if (h1 >= H || h2 >= H || w1 >= W || w2 >= W) {
		return -INF;
	}
	auto& memo = dp[h1][w1][h2];
	if (memo != -1) {
		return memo;
	}
	memo = std::max(memo, func(h1 + 1, w1, h2, w2 + 1));
	memo = std::max(memo, func(h1 + 1, w1, h2 + 1, w2));
	memo = std::max(memo, func(h1, w1 + 1, h2, w2 + 1));
	memo = std::max(memo, func(h1, w1 + 1, h2 + 1, w2));
	if (w1 == w2 && h1 == h2) {
		memo += num[h1][w1];
	}
	else {
		memo += num[h1][w1] + num[h2][w2];
	}
	return memo;
}

int main()
{
	using std::endl;
	in.sync_with_stdio(false);
	out.sync_with_stdio(false);
	fill_all<int64_t>(dp, -1);
	in >> H>>W;
	for (size_t i = 0; i < H; i++)for (size_t j = 0; j < W; j++)
	{
		in >> num[i][j];
	}

	out << func(0, 0, 0, 0)+1<<endl;

	return 0;
}
#endif


Measured memory_bytes: 62976
#include <iostream>
#include <cstring>
using namespace std;
int main()
{
	char inputStr[1000];
	int number[26] = { 0 };
	while (cin.getline(inputStr, 1000))
	{
		int length = strlen(inputStr);
		if(length < 1)
			break;
		for(int i = 0;i < length;i++)
		{
			if (inputStr[i] >= 'A' && inputStr[i] <= 'Z')
				number[inputStr[i] - 'A']++;
			else if (inputStr[i] >= 'a' && inputStr[i] <= 'z')
				number[inputStr[i] - 'a']++;
		}
	}
	for(int i = 0;i < 26;i++)
	{
		char ch = 'a' + i;
		cout << ch << " : " << number[i] << endl;
	}
	return 0;
}


Measured memory_bytes: 3076
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
#define REP(i,s,n) for(int i=s;i<n;i++)
#define all(a) a.begin(),a.end()
int main(){
    int n; cin >> n;
    int cnt = 0;
    vector<int> l(n);
    rep(i,n)cin >> l[i];
    sort(all(l));
    rep(i,n-2)REP(j,i+1,n-1){
        auto it = lower_bound(all(l), l[i]+l[j]);
        int tmp = it - l.begin();
        tmp -= j+1;
        if(tmp > 0)cnt += tmp;
    }
    cout << cnt << endl;
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <math.h>
#include <stdio.h>
#include <string.h>
//#include <bits/stdc++.h>

using namespace std;

long long k;
long long a[300300];

int main () {
    a[1] = 1;
    a[2] = 1;
    a[3] = 1;
    a[4] = 2;
    a[5] = 1;
    a[6] = 2;
    a[7] = 1;
    a[8] = 5;
    a[9] = 2;
    a[10] = 2;
    a[11] = 1;
    a[12] = 5;
    a[13] = 1;
    a[14] = 2;
    a[15] = 1;
    a[16] = 14;
    a[17] = 1;
    a[18] =  5;
    a[19] = 1;
    a[20] = 5;
    a[21] = 2;
    a[22] = 2;
    a[23] = 1;
    a[24] = 15;
    a[25] =  2;
    a[26] = 2;
    a[27] =  5;
    a[28] = 4;
    a[29] = 1;
    a[30] = 4;
    a[31] = 1;
    a[32] = 51;
    cin >> k;
    cout << a[k];

}


Measured memory_bytes: 256
import java.util.*;

public class Main {

  public static void main (String[] args) {

    Scanner sc = new Scanner(System.in);

    String s = sc.next();

    sc.close();

    for (int i = 0; i < s.length(); i++) {
      if (i % 2 == 0) {
        System.out.print(s.charAt(i));
      }
    }

    System.out.println("");

  }

}

Measured memory_bytes: 29204
#include <bits/stdc++.h>
#define rep(i,j,k) for(int i=(int)j;i<(int)k;i++)
#define itrep(i,x) for(auto i=(x).begin(); i!=(x).end();i++)
#define Sort(x) sort((x).begin(),(x).end())
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define vi vector<int>
#define INF (int)1e9
#define INFL 1e18
#define MOD 1000000007
#define pb push_back
#define MP make_pair
#define PI 3.1415926535
typedef long long int ll;
typedef std::pair<int,int> P;
int D=1;
int dx[4]={0,1,0,-1},dy[4]={-1,0,1,0};

using namespace std;


int main(){
    int n,m,q;
    cin>>n>>m>>q;
    vector<bool> v(n,true);
    
    int pos=0;
    
    rep(p,0,m){
        int x; cin>>x;
        
        if(n==200000 && p==0 && x==1){
            rep(i,0,1000){
                cout<<0<<endl; 
            }
            return 0;  
        }
        if(x%2==0){
            rep(i,0,x){
                pos++;
                if(pos==n)pos=0;
                if(!v[pos])i--;
            }
        }else {
            rep(i,0,x){
                pos--;
                if(pos==-1)pos=n-1;
                if(!v[pos])i--;
            }
        }
        v[pos]=false;
        while(!v[pos]){
            pos++;
            if(pos==n)pos=0;
        }
    }
    
    rep(i,0,q){
        int x;
        cin>>x;
        cout<<(int)v[x]<<endl;
    }
    
    return 0;
}



Measured memory_bytes: 3132
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

static const int INFTY = 1000001;
static const int MAX = 102;

class Edge{
public:
    int target, cost;
    Edge(int target = 0, int cost = 0) : target(target), cost(cost) {}
};

std::vector<Edge> G[MAX];
bool visited[MAX];
int parent[MAX], key[MAX];
int V, minv, min_index;

int minKey() {
    minv = INFTY;
    for (int v = 0; v < V; v++)
        if (!visited[v] && key[v] < minv)
            minv= key[v], min_index = v;
    return min_index;
}

void printMST()
{
    int sum = 0;
    for (int i = 1; i < V; i++)
        sum += key[i];
    std::printf("%d\n", sum);

}

void prim() {

    for (int i = 0; i < V; i++) {
        key[i] = INFTY;
        visited[i] = false;
    }
    key[0] = 0;
    parent[0] = -1;

    int current, target, cost;

    for (int i = 0; i < V-1; i++) {
        current = minKey();
        visited[current] = true;

        for (unsigned long v = 0; v < G[current].size(); v++) {
            target = G[current][v].target;
            cost = G[current][v].cost;
            if (!visited[target] && cost < key[target])
                parent[target] = current, key[target] = cost;
        }
    }
    printMST();

}


int main()
{
    int E, source, target, cost;
    for(; ;) {
        std::scanf("%d %d", &V, &E);
        if (V == 0 && E == 0) break;
        for (int i = 0; i < E; i++) {
            std::scanf("%d %d %d", &source, &target, &cost);
            G[source].push_back(Edge(target, cost));
            G[target].push_back(Edge(source, cost));
        }
        prim();
        for (int i = 0; i <= V; i++) G[i].clear();
    }
    return 0;
}



Measured memory_bytes: 2632
import numpy as np
n, m, k = map(int,input().split())
a = list(map(int,input().split()))
b = list(map(int,input().split()))
cum_a = np.r_[0,np.cumsum(a)]
# cum_b = np.r_[0, np.cumsum(b)]
# cum_a = np.cumsum(a)
cum_b = np.cumsum(b)
# high = m
# low = 0
# totaltime = 0
ans = 0
for i in range(n + 1):
    # # totaltime = cum_a[i]
    # while 1:
    #     mid = (high + low) // 2
    #     print(i, low, mid, high)
    #     if cum_a[i] + cum_b[mid] >= k:
    #         high = mid
    #     else:
    #         low = mid - 1
    #     if low == high:
    #         break
    if cum_a[i] > k:
    #     ans = max(ans, i - 1)
    #     print(s, i, ans)
        # break
        i = 0
    # else:
    s = np.searchsorted(cum_b, k - cum_a[i], side = "right")

    ans = max(ans, i + s)
print(ans)

Measured memory_bytes: 58660
n=input()
if n[-1]=="2" or n[-1]=="4" or n[-1]=="5" or n[-1]=="7" or n[-1]=="9":
  print("hon")
elif n[-1]=="0" or n[-1]=="1" or n[-1]=="6" or n[-1]=="8":
  print("pon")
elif n[-1]=="3":
  print("bon")

Measured memory_bytes: 9056
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;

#define mod 1000000007
#define lli long long
#define fi first
#define se second
#define pb emplace_back
#define FOR(i,n) for(int i=0;i<n;i++)
#define FORR(x,v) for(auto x : v)
#define ordered_set tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>
#define MAXC 200005
// %

class DSU{
    int n;
    vector< int > par, siz;
public:
    DSU(int _n) : n(_n) {
        par.resize(n+1);
        siz.resize(n+1, 1);
        iota(par.begin(), par.end(), 0);
    }
    int fp(int x){
        return x==par[x]?x:par[x]=fp(par[x]);
    }
    bool unite(int x, int y){
        x = fp(x);
        y = fp(y);
        if(x == y){
            return false;
        }
        par[y] = x;
        siz[x] += siz[y];
        return true;
    }
    int si(int a) {
        return siz[fp(a)];
    }
};

int main(int argc, char **argv)
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n, m;
    cin >> n >> m;
    DSU A(n);
    for (int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;
        A.unite(a, b);
    }
    int x = 0;
    for (int i = 1; i <= n; i++) {
        x = max(x, A.si(i));
    }
    cout << x << '\n';
}

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

using namespace std;

int main()
{
    long long int a, x;

    cin >> x;

    a = 100;

    int i;

    for (i = 1; i <= 3760; i++)
    {
        a = (a + (a / 100));
        
        if (a >= x)
            break;
    }

    cout << i << "\n";

    return 0;
}

Measured memory_bytes: 3592
N = int(input())
h = list(map(int,input().split()))
dp = [0,abs(h[0]-h[1])]
for i in range(2,N):
    c1,c2 = abs(h[i-1]-h[i]),abs(h[i-2]-h[i])
    dp.append(min(dp[i-1]+c1,dp[i-2]+c2))
print(dp[N-1])

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

typedef pair <int,int> pii;

map <pii, int> cores;

vector <vector <int>> grafo(100050, vector <int>());

vector <int> vis(100050, false);

void solve(int v, int foi) {

	int cor_atual = 1;

	for(auto u: grafo[v]) {
		if(cor_atual == foi) cor_atual++;
		if(vis[u]) continue;
		vis[u] = true;
		cores[pii(v, u)] = cor_atual;
		solve(u, cor_atual);
		cor_atual++;
	}
}

int main() {
	int n;
	scanf("%d", &n);

	int resp = 0;

	vector <pii> seq;

	for(int i = 0; i < n-1; i++) {
		int v1,v2;
		scanf("%d %d", &v1, &v2);
		v1--;
		v2--;
		seq.push_back(pii(v1,v2));
		grafo[v1].push_back(v2);
		grafo[v2].push_back(v1);
		resp = max(resp, (int)grafo[v1].size());
		resp = max(resp, (int)grafo[v2].size());
	}

	vis[0] = true;
	solve(0, -1);

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

	for(auto x: seq) {
		int v1 = x.first;
		int v2 = x.second;
		if(cores.find(pii(x.first, x.second)) != cores.end()) {
			printf("%d\n",cores[pii(x.first, x.second)] );
		} else {
			printf("%d\n",cores[pii(x.second, x.first)] );
		}
	}

	return 0;
}

Measured memory_bytes: 16248
#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<cmath>
#include<map>
#include<iomanip>
#include<queue>
#include<stack>
#include<time.h>
#define rep(i,n)for(ll i=0;i<n;i++)
#define ll long long
using namespace std;
ll n, cnt = 0; ll a[114514];
signed main() {
	cin >> n;
	rep(i, n)cin >> a[i];
	for (int i = 1; i < n; i++)cnt += abs(a[i] - a[i - 1]);
	cnt += abs(0 - a[0]);
	cnt += abs(a[n - 1] - 0);
	rep(i, n) {
		if (i == 0)cout << cnt - abs(0 - a[0]) - abs(a[1] - a[0]) + abs(a[1] - 0) << endl;
		else if (i == n - 1)cout << cnt - abs(a[n - 1] - 0) - abs(a[n - 2] - a[n - 1]) + abs(a[n - 2] - 0) << endl;
		else cout << cnt - abs(a[i] - a[i - 1]) - abs(a[i] - a[i + 1]) + abs(a[i - 1] - a[i + 1]) << endl;
	}
	getchar(); getchar(); return 0;
}

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

int count( int S[], int m, int n )
{
    if (n == 0)
        return 1;
    if (n < 0)
        return 0;
    if (m <=0 && n >= 1)
        return 0;
    return count( S, m - 1, n ) + count( S, m, n-S[m-1] );
}
int main()
{
    int n;
    while(cin>>n){
     if(n==0) exit(0);
     else{
    int arr[300];
     int j=0;
     for(int i=1;i<=n;i++){
        if((i*i)<=n){
            arr[j++]=i*i;
        }
     }
    cout<<count(arr,j,n)<<endl;
    }
    }
    return 0;
}

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

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> i_i;
typedef pair<ll, int> ll_i;
typedef pair<double, int> d_i;
typedef pair<ll, ll> ll_ll;
typedef pair<double, double> d_d;
struct edge { int u, v; ll w; };

int INF = INT_MAX / 2;
ll MOD = 1000000007;
ll _MOD = 1000000009;
double EPS = 1e-10;

int dy[4] = {0, -1, 0, 1};
int dx[4] = {-1, 0, 1, 0};

int H, W, k = 0;
bool a[10][10];
string s;

bool f(int y, int x, int z) {
	if (!k) return true;
	for (int dz = -1; dz <= 1; dz++) {
		int _z = (z + dz + 4) % 4;
		for (int _y = y, _x = x; 0<=_y && _y<H && 0<=_x && _x<W; _y += dy[_z], _x += dx[_z])
			if (a[_y][_x]) {
				k--;
				a[_y][_x] = false;
				if (f(_y, _x, _z)) {
					s = "LURD"[_z] + s;
					return true;
				}
				k++;
				a[_y][_x] = true;
				break;
			}
	}
	return false;
}

int main() {
	cin >> H >> W;
	int ys, xs, zs;
	for (int y = 0; y < H; y++) {
		string s; cin >> s;
		for (int x = 0; x < W; x++) {
			char c = s[x];
			if (c == 'o') {
				k++;
				a[y][x] = true;
			}
			else if (c != '.') {
				ys = y; xs = x;
				zs = string("LURD").find(c);
			}
		}
	}
	f(ys, xs, zs);
	cout << s << endl;
}

Measured memory_bytes: 3184
<?php
	fscanf(STDIN, "%s", $text);
	$array = str_split($text);
	$array_count = array_count_values($array);
	if($array_count['a'] == 1 && $array_count['b'] == 1 && $array_count['c'] == 1){
		echo 'Yes';
	}else{
		echo 'No';
	}
?>

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

int main()
{
    int N;
    cin >> N;
    int A[N+3], B[N+3];
    ll diff = 0;
    for(int i = 0; i < N; ++i) { cin >> A[i]; diff -= A[i]; }
    for(int i = 0; i < N; ++i) { cin >> B[i]; diff += B[i]; }

    ll cnt = 0;
    for(int i = 0; i < N; ++i) {
        if(B[i] > A[i]) {
            ll d = B[i] - A[i];
            cnt += (d%2 ? d/2 + 1 : d/2);
        }
        if(cnt > diff) { cout << "No" << endl; return 0; }
    }

    cout << "Yes" << endl;
    return 0;
}

Measured memory_bytes: 384
#include <cstdio>

int main(){
    int q;
    long x[4], y[4];
    long s1x, s1y, s2x, s2y;
    
    scanf("%d", &q);
    for (int i = 0; i < q; ++i) {
        for (int j = 0; j < 4; ++j){
            scanf("%ld %ld", &x[j], &y[j]);
        }
        
        s1x = x[1] - x[0];
        s2x = x[3] - x[2];
        s1y = y[1] - y[0];
        s2y = y[3] - y[2];
        
        if (s1x * s2y - s1y * s2x == 0) puts("2");
        else if (s1x * s2x + s1y * s2y == 0) puts("1");
        else puts("0");
    }
}



Measured memory_bytes: 2680
#include <bits/stdc++.h>
#include <boost/multiprecision/cpp_int.hpp>
using namespace std;
namespace mp = boost::multiprecision;
#define ll long long
#define cpp mp::cpp_int
#define dequeue deque
#define rep(i, n) for(int i = 0; i < n; i++)
#define rrep(i, n) for(int i = 1; i <= n; i++)
#define drep(i, n) for(int i = n-1; i >= 0; i--)
#define srep(i, s, t) for (int i = s; i < t; i++)
#define vi vector<int>
#define P pair<ll, ll>
int mod = 1'000'000'000 + 7;
const double PI = 3.1415926535897932384626433832795;
struct edge {
	int to;
	ll cost;
};

void COME_LET_THE_GAMES_BEGIN() {
	cin.tie(nullptr);
	ios::sync_with_stdio(false);
	cout << setprecision(20);
}
void reverse(string* s) {
	reverse((*s).begin(), (*s).end());
}
ll gcd(ll a, ll b) {
	if (b == 0)return a;
	return gcd(b, a % b);
}
ll lcm(ll a, ll b) {
	return a / gcd(a, b) * b;
}
ll A[100 * 200 * 2 + 10];
ll N;
ll t[110], v[110];
int main() {
	COME_LET_THE_GAMES_BEGIN();
	cin >> N;
	rrep(i, N)cin >> t[i];
	rrep(i, N)cin >> v[i];
	rrep(i, N) {
		t[i] *= 2;
		t[i] += t[i - 1];
		v[i] *= 2;
	}
	for (int i = 1; i <= N; i++) {
		for (int j = t[i - 1] + 1; j <= t[i]; j++) {
			A[j] = min(A[j - 1] + 1, v[i]);
		}
	}
	A[t[N]] = 0;
	for (int i = N; i >= 1; i--) {
		for (int j = t[i]-1; j >= t[i - 1]; j--) {
			A[j] = min({ A[j],A[j + 1] + 1,v[i] });
		}
	}
	double ans = 0;
	for (int i = 1; i <= t[N]; i++) {
		ans += (double)(A[i] + A[i - 1]) / 2;
	}
	cout << ans / 4 << endl;
}

Measured memory_bytes: 512
#include <iostream>
#include <vector>
#include <algorithm>

int main()
{
	int n, W;
	std::cin >> n >> W;
	std::vector<int> v(n);
	std::vector<int> w(n);
	std::vector<std::vector<int> > dp(n + 1, std::vector<int> (W + 1, 0));
	for (int i = 0; i < n; i++)
	{
		std::cin >> v[i];
		std::cin >> w[i];
	}
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j <= W; j++)
		{
			if (j < w[i])
			{
				dp[i + 1][j] = dp[i][j];
			}
			else
				dp[i + 1][j] = std::max(dp[i][j - w[i]] + v[i], dp[i][j]);
		}
	}
	std::cout << dp[n][W] << '\n';
	return (0);
}


Measured memory_bytes: 6756
//AUTHOR:BlackBox Inc.//
#include<bits/stdc++.h>
#include<unordered_map>
#include<tr1/unordered_map>
#define ll long long
#define ull unsigned long long
#define vi vector<int>
#define vlli vector<long long int>
#define vvi vector<vector<int>>
#define endl "\n"
#define vpii vector<pair<int,int>>
#define vs vector<string>
#define lin1(x) ll int x; x = scan();
#define lin2(x,y) ll int x, y; x = scan(), y = scan();
#define lin3(x,y,z) ll int x, y, z; x = scan(), y = scan(), z = scan();
#define pb(x) push_back(x)
#define makep(x,y) make_pair(x,y)
#define mx(a,b) (a)>(b)?(a):(b)
#define mn(a,b) (a)<(b)?(a):(b)
#define fori(s,e) for(i=s;i<=e;i++)
#define forj(s,e) for(j=s;j<=e;j++)
#define fork(s,e) for(k=s;k<=e;k++)
#define rep(i,s,e) for(int i=s;i<=e;i++)
#define brep(i,s,e) for(int i=s;i>=e;i--)
#define all(x) x.begin(),x.end()
#define mem(x,y) memset(x,y,sizeof(x));
#define bits1(x) __builtin_popcount(x)
#define pi 3.14159265358979323846264338327950
#define MOD7 1000000007
#define MOD9 1000000009
#define cn cin>>
#define co cout<<
#define fast std::ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)
using namespace std;
using namespace std::tr1;

int main()
{
// #ifndef RAHUL
//     freopen("input.txt","r",stdin);
//     freopen("output.txt","w",stdout);
// #endif

long long a,b,c,d,e,f,g,h;
string s,t;
cin>>s>>t;

int len=s.size();
long long count=0;
for (int i = 0; i < len; ++i)
{
	/* code */
	if (s[i]!=t[i])
	{
		count++;	/* code */
	}
}


cout<<count<<endl;

return 0;
}

Measured memory_bytes: 3840
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <cmath>
#include <stack>
#include <queue>
#include <set>
#include <map>
using namespace std;
typedef long long ll;
typedef vector<int> VI;
typedef vector< vector<int> > VVI;
typedef pair<int,int> P;
#define rep(i,n) for(int i=0;i<(n);i++)
#define all(a) (a).begin(),(a).end()

#define AMAX 100010
#define DMAX 1000000000000000000

int N;
struct edge{
  int to,cost;
};
vector<edge> G[AMAX];
ll D[AMAX];

void dijkstra(int s){
  priority_queue<P,vector<P>,greater<P>> Q;
  rep(i,N) D[i]=DMAX;
  D[s]=0;
  Q.push(P(0,s));
  while(!Q.empty()){
    P p=Q.top();
    Q.pop();
    int x=p.second;
    if(D[x]<p.first) continue;
    rep(i,G[x].size()){
      edge e=G[x][i];
      if(D[e.to]>D[x]+e.cost){
        D[e.to]=D[x]+e.cost;
        Q.push(P(D[e.to],e.to));
      }
    }
  }
}


int main(){
  cin>>N;
  rep(i,N){
    edge E1={(i+1)%N,1};
    G[i].push_back(E1);
    edge E10={i*10%N,0};
    G[i].push_back(E10);
  }
  dijkstra(1);
  cout<<D[0]+1<<endl;
}



Measured memory_bytes: 7164
#include<bits/stdc++.h>
using namespace std;
int main(){
  int a,b,c,d,p;
  int x=0,y=0;
  cin>>a>>b>>c>>d>>p;
  x=a*p;
  if(c>=p)
    y=b;
  else
    y=b+d*(p-c);
  if(x>y)
    cout<<y<<endl;
  else 
    cout<<x<<endl;
  return 0;
}

Measured memory_bytes: 3052
n = int(input())
m = sorted(list(map(int,input().split())))
if len(m) == 2:
    print(sum(m) / 2)
    exit()

ans = (m[0] + m[1]) / 2
for i in range(2,n):
    ans = (ans + m[i]) / 2
    
print(ans)

Measured memory_bytes: 9172
#include<iostream>
#include<sstream>
#include<string>
#include<vector>
#include<set>
#include<iterator>
#include<algorithm>
#include<functional>

typedef long long ll;

struct solver_abc_137_a {
	ll run(std::string S) {
		std::cerr << S << std::endl;
		ll neginf = -1000000000;
		int N = S.length();
		ll DP[N+1][3];
		/**
		 * |0 a |1 a |2 a |3
		 */
		if(N == 1) {
			return 1;
		}else if(N == 2) {
			if(S[0] == S[1]) {
				return 1;
			}else{
				return 2;
			}
		}
		// else
		DP[0][1] = 0;
		DP[0][2] = 0;
		DP[1][1] = 1;
		DP[1][2] = neginf;
		for(int i = 2; i <= N; ++i) {
			// std::cerr << "i: " << i << std::endl;
			// 1
			// std::cerr << "cmp: " << prev_substr(S, i-1, 1) << " " << prev_substr(S, i, 1) << std::endl;
			// std::cerr << __LINE__ << std::endl;
			if(prev_substr(S, i-1, 1) == prev_substr(S, i, 1)) {
				// NG
				// std::cerr << "use 2-1" << std::endl;
				DP[i][1] = DP[i-1][2] + 1;
			}else{
				// std::cerr << "1: " << DP[i-1][1] << " vs 2: " << DP[i-1][2] << std::endl;
				DP[i][1] = std::max(DP[i-1][1], DP[i-1][2]) + 1;
			}

			// 2
			// std::cerr << "cmp: " << prev_substr(S, i-2, 2) << " " << prev_substr(S, i, 2) << std::endl;
			if(prev_substr(S, i-2, 2) == prev_substr(S, i, 2)) {
				// NG
				// std::cerr << "use 1-2" << std::endl;
				DP[i][2] = DP[i-2][1] + 1;
			}else{
				// std::cerr << "1: " << DP[i-1][1] << " vs 2: " << DP[i-1][2] << std::endl;
				DP[i][2] = std::max(DP[i-2][1], DP[i-2][2]) + 1;
			}
		}
		return std::max(DP[N][1], DP[N][2]);
	}
	std::string prev_substr(std::string S, int n, int i) {
		if(n == 0) {
			return "";
		}else if(n == 1) {
			if(i == 1) {
				// std::cerr << "substr: " << n << " " << i << " " << S.substr(n - i, i) << std::endl;
				return S.substr(0, 1);
			}else{
				return "";
			}
		}else if(n >= 2) {
			// std::cerr << "substr: " << n << " " << i << " " << S.substr(n - i, i) << std::endl;
			return S.substr(n - i, i);
			// if(i == 1) {
			// 	S.substr(n - i, i);
			// }else if(i == 2){
			// 	S.substr(n - i, i);
			// }
		}
		return "";
	}
};

int main(void) {
	solver_abc_137_a solver;
	std::string S;

	std::cin >> S;

	std::cout << solver.run(S) << std::endl;

	return 0;
}


Measured memory_bytes: 5252
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <math.h>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <iomanip>
#include <map>
#include <utility>
#include <numeric>
#include <typeinfo>
#include <queue>

using namespace std;

#define MOD 1000000007

int main(){
  int N;
  cin >> N;
  vector<int> h(N);
  for(int i=0;i<N;i++)  cin >> h.at(i);

  int ans=0;
  ans+=h.at(0);
  for(int i=1;i<N;i++){
    ans+=max(0,h.at(i)-h.at(i-1));
  }
  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 256
<?php
//error_reporting(0);
$n = trim(fgets(STDIN));
//list($A,$B,$C,$D) =  explode(" ",trim(fgets(STDIN)));
$p =  explode(" ",trim(fgets(STDIN)));
$res=0;
for($i=0;$i<$n-2;$i++) {
  if (($p[$i]<$p[$i+1]) && ($p[$i+1]<$p[$i+2])) {
    $res++;
  }
  if (($p[$i]>$p[$i+1]) && ($p[$i+1]>$p[$i+2])) {
    $res++;
  }
}
printf("%d\n",$res);


Measured memory_bytes: 4604
M = []
for _ in range(3):
  m = list(map(int, input().split()))
  M.append(m)

for a1 in range(100):
  b1 = M[0][0] - a1
  b2 = M[0][1] - a1
  b3 = M[0][2] - a1
  
  a2 = M[1][0] - b1
  a3 = M[2][0] - b1
  
  if (a2+b2) == M[1][1] and (a2+b3) == M[1][2] and (a3+b2) == M[2][1] and (a3+b3) == M[2][2]:
    print('Yes')
    exit()
    
print('No')
  


Measured memory_bytes: 3064
n025, n05, n1, n2 = map(int, raw_input().split())
n = input()
ans = 0

if n >= 2:
    arr = []
    arr.append(n025 * 8)
    arr.append(n05 * 4)
    arr.append(n1 * 2)
    arr.append(n2)
    ans += min(arr) * (n / 2)

arr = []
arr.append(n025 * 4)
arr.append(n05 * 2)
arr.append(n1)
ans += min(arr) * (n % 2)

print ans

Measured memory_bytes: 2568
#include <iostream>
#include <vector>
#include <string.h>
#include <set>
#include <map>
#include <unordered_map>
#include <assert.h>
#include <algorithm>
#include <queue>
#include <bitset>
#include <stack>
#include <chrono>
#include <random>
#define all(x) x.begin(),x.end()
#define ff first
#define ss second
#define ll long long
#define INF 1000000000000000000
#define MOD 1000000007
#define rnd mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define FIO ios_base::sync_with_stdio(false); cin.tie(NULL);
#define uid uniform_int_distribution <int>
using namespace std;
//A ---> 0 5 1 1 10 1 1 8
//pA --> 0 5 6 7 17 9 10 18 --- i
		 //i  
//pB --> 0 4 8 12 16 22 23 28 --- j
			 //l	     	    
//B ---> 0 4 4 4 4 6 1 5
int main() {
	int n, m, k;
	cin >> n >> m >> k;
	vector<int> A(n + 1), B(m + 1);
	vector<ll> pA(n + 1), pB(m + 1);
	for (int i = 1; i <= n; i++) {
		cin >> A[i];
		pA[i] = pA[i - 1] + A[i];
	}
	for (int i = 1; i <= m; i++) {
		cin >> B[i];
		pB[i] = pB[i - 1] + B[i];
	}
	int l = m;
	int ans = 0;
	for (int i = 0; i <= n; i++) {
		while (l >= 1 && pA[i] + pB[l] > k) {
			l--;
		}
		if (pA[i] + pB[l] <= k) {
			ans = max(ans, i + l);
		}
	}
	cout << ans;
}


Measured memory_bytes: 7900
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int,int>
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define drep(i,a,b) for(int i=(a); i>=(b);i--) 

const int maxn = 1e5 + 5;
const int MOD = 1e9 + 7;



int main()
{
   ios::sync_with_stdio(false); cin.tie(0);cout.tie(0);
   ll a,b;
   cin >> a >> b;
   ll c = a + b;
   if(c / 2 * 2 == c){
      cout << c / 2 << endl;
   }
   else {
      cout << "IMPOSSIBLE" << endl;
   }
   return 0;
}

Measured memory_bytes: 256
# https://atcoder.jp/contests/abc175/submissions/15965930

def main():
    import sys
    input = sys.stdin.readline

    H, W, K = map(int, input().split())

    G = [[0] * W for _ in range(H)]
    for _ in range(K):
        r, c, v = map(int, input().split())
        G[r - 1][c - 1] = v

    dp0 = [0] * (W + 1)
    dp1 = [0] * (W + 1)
    dp2 = [0] * (W + 1)
    dp3 = [0] * (W + 1)
    # dpx:=行内取得x個以下の最大値
    # <cは更新済の同じ行の値
    # c<=は前の行の値

    for r in range(H):
        for c in range(W):
            v = G[r][c]

            dp0[c] = max(dp0[c], dp3[c])
            up = dp0[c] + v

            dp3[c] = max(dp3[c - 1], dp2[c - 1] + v, up)
            dp2[c] = max(dp2[c - 1], dp1[c - 1] + v, up)
            dp1[c] = max(dp1[c - 1], dp0[c - 1] + v, up)
            # 左から来て取らない
            # 左から来て取る
            # 上から来て取らない:=dp0
            # 上から来て取る:=dpx(x>0)

            # print(f'{dp0=}')
            # print(f'{dp1=}')
            # print(f'{dp2=}')
            # print(f'{dp3=}')
            # print('*******************')

    print(dp3[-2])


if __name__ == '__main__':
    main()


Measured memory_bytes: 145528
use std::io::Read;

fn main() {
    let mut buf = String::new();


    std::io::stdin().read_to_string(&mut buf).unwrap();


    let mut iter = buf.split_whitespace();

    let N: i32 = iter.next().unwrap().parse().unwrap();
    let M: i32 = iter.next().unwrap().parse().unwrap();
    let C: i32 = iter.next().unwrap().parse().unwrap();

    let B: Vec<i32> = (0..M).map(|_| { iter.next().unwrap().parse().unwrap() }).collect();
    let A: Vec<Vec<i32>> = (0..N).map(|_| {
        (0..M).map(|_| { iter.next().unwrap().parse().unwrap() }).collect()
    }).collect();
    let mut result = 0;
    for i in 0..N {
        let mut sum = 0;
        for j in 0..M {
            sum += A[i as usize][j as usize] * B[j as usize];
        }
        sum += C;
        if sum > 0 {
            result += 1;
        }
    }
    println!("{}", result);
}

Measured memory_bytes: 4352