akhauriyash/Code-Regression huggingface dataset:
from sys import stdin
 
n = int(input())
k = [int(x) for x in stdin.readline().rstrip().split()]

k.sort()

ave = round(sum(k) / len(k) )

#print(ave)

def calc_pow(n):
    i = pow(n - ave, 2) 
    return i
  
j = map(calc_pow, k)

print(sum(j))

Measured memory_bytes: 38384
#include <bits/stdc++.h>
#define fo(i,a,b) for(int i=a;i<=b;++i)
#define fod(i,a,b) for(int i=a;i>=b;--i)
#define N 300005
#define LL long long
#define mo 1000000007
using namespace std;
LL f[N];
int lst[N],a[N],n;
int main()
{
	cin>>n;
	fo(i,1,n) scanf("%d",&a[i]);
	f[0]=1;
	fo(i,1,n)
	{
		f[i]=f[i-1];
		if(lst[a[i]]!=i-1&&lst[a[i]]!=0) f[i]=(f[i]+f[lst[a[i]]])%mo;
		lst[a[i]]=i;
	}
	printf("%lld\n",f[n]);
}

Measured memory_bytes: 3840
////////////////////////// Author
////////////////////////// Nasim Hossain Rabbi
////////////////////////// JU-CSE28
////////////////////////// CF - imnasim3.1415
////////////////////////// UVA - imnasim3.1415
////////////////////////// Mail - imnasim3.1415@gmail.com
#include<bits/stdc++.h>
using namespace std;
#define E end()
#define B begin()
#define sz size()
#define EM empty()
#define clr clear()
#define sqr(a) (a*a)
#define mk make_pair
#define pb push_back
string en="\n";
string t="hello";
string Y="YES\n";
string N="NO\n";
#define rep(i,n) for(i=0;i<n;i++)
#define Rep(i,n) for(i=1;i<=n;i++)
#define per(i,n) for(i=n-1;i>=0;i--)
#define peR(i,n) for(i=n;i>0;i--)
#define mem(a,b) memset(a,b,sizeof(a))
#define all(cont) cont.begin(),cont.end()
#define fast ios_base::sync_with_stdio(false); cin.tie(NULL);cout.tie(NULL)
#define pi 3.1415926535897932384626433832795
#define vi vector<long long>
#define vs vector<string>
#define vp(vi,x) cin>>x; vi.pb(x);
#define srch(a,x) binary_search(all(a),x)
#define LB(a,x) (lower_bound(all(a),x)-a.B)
#define UB(a,x) (upper_bound(all(a),x)-a.B)
typedef long long LL;
typedef unsigned long long ULL;
bool isprm(LL a){for(LL i=2;i*i<=a;i++){if(a%i==0)return false;}return true;}
bool palin(string a){for(int i=0;i<a.sz;i++){if(a.at(i)!=a.at(a.sz-i-1))return 0;} return 1;}
bool isVowel(char ch){ ch=toupper(ch); if(ch=='A'||ch=='U'||ch=='I'||ch=='O'||ch=='E') return true; return false;}
int toInt(string s){int sm;stringstream ss(s);ss>>sm;return sm;}
template<typename T>inline T gcd(T a,T b){if(a<0)return gcd(-a,b);if(b<0)return gcd(a,-b);return (b==0)?a:gcd(b,a%b);}
template<typename T>inline T lcm(T a,T b) {if(a<0)return lcm(-a,b);if(b<0)return lcm(a,-b);return a*(b/gcd(a,b));}
int main()
{
//    fast;
    LL i,j,k,n,m,l,s=0,x,y,tc=1,c=0;
    while(cin>>n>>m)
    {
        m+=n*3;
        m=m/2;
        cout<<m<<en;
    }
}



Measured memory_bytes: 256
#include <bits/stdc++.h>
#define syosu(x) fixed<<setprecision(x)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> P;
typedef pair<double,double> pdd;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<string> vs;
typedef vector<P> vp;
typedef vector<vp> vvp;
typedef vector<pll> vpll;
typedef pair<int,P> pip;
typedef vector<pip> vip;
const int inf=1<<30;
const ll INF=1ll<<60;
const double pi=acos(-1);
const double eps=1e-8;
const ll mod=1e9+7;
const int dx[4]={-1,0,1,0},dy[4]={0,-1,0,1};

int n;
vi a;

int main(){
	cin>>n;
	a=vi(n+1,inf);
	a[0]=0;
	for(int i=1;i<=n;i++){
		int t=1;
		while(i-t>=0){
			a[i]=min(a[i],a[i-t]+1);
			t*=6;
		}
		t=1;
		while(i-t>=0){
			a[i]=min(a[i],a[i-t]+1);
			t*=9;
		}
	}
	cout<<a[n]<<endl;
}

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

using namespace std;

typedef long long ll;

int main() {
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n;
    cin >> n;
    int t2 = 0, t4 = 0;
    int a;
    for (int i = 0; i < n; ++i) {
        cin >> a;
        if (a % 4 == 0) {
            ++t4;
        } else {
            if (a % 2 == 0) {
                ++t2;
            }
        }
    }
    if (t2 == 0 && t4 * 2 + 1 >= n) {
        cout << "Yes";
        return 0;
    }
    if (t2 + t4 * 2 >= n) {
        cout << "Yes";
    } else {
        cout << "No";
    }
    return 0;
}

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

typedef long long ll;

int main() {
	int H[2], ans = (int)1e5;
	cin >> H[0] >> H[1];
	for (int i = 0; i < 2; i++) {
		if (H[i] % 3 == 0) {
			cout << 0 << endl;
			return 0;
		}
		ans = min(ans, H[1 - i]);
		int H1 = H[i] / 3;
		int S_max = (H1 + 1) * H[1 - i];
		int S_min = (H[i] - H1 - 1) * (H[1 - i] / 2);
		ans = min(ans, S_max - S_min);
		S_min = H1 * H[1 - i];
		S_max = (H[i] - H1) * ((H[1 - i] + 1) / 2);
		ans = min(ans, S_max - S_min);
	}
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 256
fn main() {
    let v = read_vec::<usize>();

    if v[0] == v[1] && v[1] == v[2] {
        println!("No");
        return;
    }
    if v[0] != v[1] && v[1] != v[2] && v[0] != v[2] {
        println!("No");
        return;
    }

    println!("Yes");
}

fn read_vec<T: std::str::FromStr>() -> Vec<T> {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).ok();
    s.trim().split_whitespace().map(|e| e.parse().ok().unwrap()).collect()
}

Measured memory_bytes: 4352
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }
ll lcm(ll a, ll b) { return a / gcd(a, b) * b; }


int main() {
    ll n, m, l;
    cin >> n >> m >> l;
    vector<vector<ll>> dist(330, vector<ll>(330, 1LL<<60));
    vector<vector<ll>> new_dist(330, vector<ll>(330, 1LL<<60));
    for(int i = 0; i < m; ++i){
        ll a, b, c;
        cin >> a >> b >> c;
        a--; b--;
        dist[a][b] = dist[b][a] = c;
    }

    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
            for(int k = 0; k < n; k++){
                    dist[j][k] = min(dist[j][k], dist[j][i] + dist[i][k]);
            }
        }
    }
    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
            if(dist[i][j] <= l){
                new_dist[i][j] = 1;
            }
        }
    }

    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
            for(int k = 0; k < n; k++){
                new_dist[j][k] = min(new_dist[j][k], new_dist[j][i] + new_dist[i][k]);
            }
        }
    }

    int q;
    cin >> q;
    while(q--){
        int a, b;
        cin >> a >> b;
        a--; b--;
        if(new_dist[a][b] == 1LL<<60) new_dist[a][b] = 0;
        cout << new_dist[a][b]-1 << endl;
    }
}


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


int main(){
    string s;
    cin >> s;
    if(s.length() % 2 == 1){
        cout << "No" << endl;
        return 0;
    }
    for(int i = 0; i < s.length(); i += 2){
        if(s[i] != 'h'){
            cout << "No" << endl;
            return 0;
        }
    }
    for(int i = 1; i < s.length(); i += 2){
        if(s[i] != 'i'){
            cout << "No" << endl;
            return 0;
        }
    }
    cout << "Yes" << endl;
}

Measured memory_bytes: 256
#include <stdio.h>
#include <math.h>
 
int sprime(int);
 
int main(){
 
  int A[10000],i,r,s=0,n;
 
 
  scanf("%d",&n);
  for(i=0;i<n;i++){
    scanf("%d",&A[i]);
    
  }
 
  for(i=0;i<n;i++){
    r=sprime(A[i]);
    if(r==1) s++;
  }
 
  printf("%d\n",s);
 
  return 0;
}
 
 
 
int sprime(int x){
  int i;
    
  if(x==2) return 1;
  else if(x<2 || x%2==0) return 0;
   
  i=3;
  while(i<=sqrt(x)){
    if(x%i==0) return 0;
      i=i+2;
  }
         return 1;
     
  } 

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

#define rep(i, n) for (int i = 0, i##_len = (n); i < i##_len; i++)
#define rep1(i, n) for (int i = 1, i##_len = (n); i <= i##_len; i++)
#define repr(i, n) for (int i = ((int)(n)-1); i >= 0; i--)
#define rep1r(i, n) for (int i = ((int)(n)); i >= 1; i--)


void func(long long A, long long B, long long K){
    if (A>=K) {
        cout << A-K << ' ' << B << endl;
    } else if (A+B-K >=0) {
        cout << 0 << ' ' << A + B - K << endl;
    } else {
        cout << 0 << ' ' << 0 << endl; 
    }
}

int main(){
    // cout << fixed << setprecision(5);

    long long A;
    scanf("%lld",&A);
    long long B;
    scanf("%lld",&B);
    long long K;
    scanf("%lld",&K);
    func(A, B, K);
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
const int MOD = (int)1e9 + 7;
const int INF = 100100100;
const double PI = 3.14159265358979323846;
typedef long long ll;
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define REP(i, n) for (int i = 0; i < (n); ++i)

int main() {
  int n;
  string s;
  map<string, bool> mp;
  cin >> n;
  REP(i, n) {
    cin >> s;
    mp[s] = true;
  }
  cout << mp.size() << endl;
  return 0;
}

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

#define FOR(i, m, n) for (int i = (m); i < (n); ++i)
#define REP(i, n) FOR(i, 0, n)
#define dump(x)  cerr << #x << " = " << (x) << endl
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl

using namespace std;

typedef long long LL;

typedef pair<int, int> C;

template<typename T>
ostream& operator << (ostream& os, const vector<T>& vec) {
    os << "[ ";
    REP(i, vec.size()) {
        os << vec[i] << " ";
    }
    os << "]";

    return os;
}


void print(C c) {
    cout << "x: " << c.first << ", y: " << c.second << endl;
}

C operator+(C a, C b) {
    return make_pair(a.first + b.first, a.second + b.second);
}

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

    int N;
    cin >> N;

    vector<C> V(N);
    REP(i, N) {
        int x, y;
        cin >> x >> y;
        V[i] = make_pair(x, y);
    }

    sort(V.begin(), V.end(), [&](C a, C b){
        return atan2(a.second, a.first) < atan2(b.second, b.first);
    });

    LL d = 0.0;
    REP(i, N) {
        C cur = make_pair(0, 0);
        REP(j, N) {
            cur = cur + V[(i + j) % N];
            d = max(d, cur.first * LL(cur.first) + cur.second * LL(cur.second));
        }
    }

    cout << fixed;
    cout << setprecision(52) << sqrtl(d) << endl;
}


Measured memory_bytes: 256
N = int(input())
A = list(map(int,input().split()))
B = [0]*N
C = [0]*N
D = [0]*N
for i in range(N):
    B[A[i]-1]+=1
for i in range(N):
    C[i] = int(B[i]*(B[i]-1)/2)
    D[i] = int((B[i]-1)*(B[i]-2)/2)
S = sum(C)
for i in A:
    print(S-C[i-1]+D[i-1])

Measured memory_bytes: 84684
def solve():
    from sys import stdin
    f_i = stdin
    
    N = int(f_i.readline())
    
    count = dict()
    S = []
    for i in range(N):
        s = f_i.readline().rstrip()
        if s in count:
            count[s] += 1
        else:
            count[s] = 1
        S.append(s)
    
    S = set(S)
    count_max = max(count.values())
    answers = filter(lambda x: count[x] == count_max, S)
    
    print('\n'.join(sorted(answers)))

solve()

Measured memory_bytes: 45700
#include<bits/stdc++.h>
using namespace std;
double tu[10][10];
int x[10],y[10];
int sum=0;
double su=0;
int n;
int fg[10];
void dfs(int now,int ci,double ju){
	if(ci==n-1){
		sum++;
		su+=ju;
		return;
	}
	for(int i=1;i<=n;i++){
		if(!fg[i]){
			fg[i]=1;
			dfs(i,ci+1,ju+tu[now][i]);
			fg[i]=0;
		}
	}
}
double dis(int i,int j){
	return sqrt(pow(x[i]-x[j],2)+pow(y[i]-y[j],2));
}
int main(){
	cin >> n;
	for(int i=1;i<=n;i++){
		cin >> x[i] >> y[i];
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			tu[i][j]=dis(i,j);
		}
	}
	for(int i=1;i<=n;i++){
		fg[i]=1;
		dfs(i,0,0);
		fg[i]=0;
	}
	printf("%.10lf",su/sum);
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <map>

using namespace std;

int main() {

    string S;
    cin >> S;

    map<string, int> days;
    days["SUN"] = 7;
    days["MON"] = 6;
    days["TUE"] = 5;
    days["WED"] = 4;
    days["THU"] = 3;
    days["FRI"] = 2;
    days["SAT"] = 1;

    cout << days[S] << endl;

    return 0;
}

Measured memory_bytes: 256
class Solver
  def initialize

    loop do
      h, w = gets.chomp.split(' ').map(&:to_i)

      break if h.zero? && w.zero?

      puts '#' * w

      (h-2).times do
        puts ['#','.' * (w-2),'#'].join
      end

      puts '#' * w

      puts
    end
  end
end

Solver.new

Measured memory_bytes: 6104
//#pragma GCC optimize("Ofast")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
//#pragma GCC optimize("unroll-loops")
//#pragma GCC optimize("-O3")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define int long long
#define F first
#define S second
#define pb push_back
#define bit __builtin_popcount
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
#define mkp make_pair
#define ffs fflush(stdout)

using namespace std;
using namespace __gnu_pbds;

//order_of_key(k) : Number of items strictly smaller than k
//find_by_order(k) : K-th element in a set (counting from 0)

template<typename T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

typedef long long ll;
typedef long double ld;
typedef vector <int> lnum;
typedef pair <int, int> pii;

const int N = (int)1e6 + 5;
const int MOD = (int)1e9 + 7;
const int inf = (int)1e18;
const int dx[] = {1, -1, 0, 0, 1, -1, 1, -1};
const int dy[] = {0, 0, 1, -1, 1, -1, -1, 1};
const ld eps = 1e9 - 7;
const int pp[] = {29, 31, 53, 67, 71};
const double pi = acos(-1.0);

mt19937 gen(chrono::system_clock::now().time_since_epoch().count());

signed main() {
  ios_base :: sync_with_stdio(false);
  cin.tie(0); cout.tie(0);
  int n, k;
  cin >> n >> k;
  vector <pii> v;
  v.pb(mkp(1, 2));
  for (int i = 3; i <= n; ++i)
    v.pb(mkp(2, i));
  int all = (n - 2) + ((n - 2) * ((n - 2) - 1)) / 2;
  if (all < k) {
    cout << -1;
    return 0;
  }
  for (int i = 3; i <= n; ++i) {
    for (int j = i + 1; j <= n; ++j) {
      if (all == k)
        break;
      all--;
      v.pb(mkp(i, j));
    }
  }
  for (int i = 3; i <= n; ++i) {
    if (all == k)
      break;
    all--;
    v.pb(mkp(1, i));
  }
  if (all != k) {
     cout << -1;
     return 0;
  }
  cout << sz(v) << "\n";
  for (auto x : v)
    cout << x.F << " " << x.S << "\n";
  return 0;
}


Measured memory_bytes: 512
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>

#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>

#include <complex>

#include <functional>
#include <cassert>

typedef long long ll;
using namespace std;

#define debug(x) cerr << __LINE__ << " : " << #x << " = " << (x) << endl;


#define mod 1000000007 //1e9+7(prime number)
#define INF 1000000000 //1e9
#define LLINF 2000000000000000000LL //2e18
#define SIZE 200010


int main(){
  int n,m;
  int a[SIZE], b[SIZE];
  int in1[SIZE] = {}, inn[SIZE] = {};
  scanf("%d%d",&n,&m);

  for(int i=0;i<m;i++){
    scanf("%d%d",a+i, b+i);

    if(a[i] > b[i]) swap(a[i], b[i]);
    
    if(a[i] == 1)
      in1[b[i]-1] = true;

    if(b[i] == n)
      inn[a[i]-1] = true;
  }

  bool ans = false;
  
  for(int i=1;i<n-1;i++){
    ans |= in1[i] && inn[i];
  }

  puts(ans ? "POSSIBLE" : "IMPOSSIBLE");
  
  return 0;
}


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

int main(void) {
  int X, N; 
  cin >> X >> N;
  if ( N == 0 ) {
    cout << endl;
    cout << X << endl;
  } else {
    vector<int> p(N);

  for (int i = 0; i < p.size(); i++) {
    cin >> p.at(i);
  }
  sort(p.begin(), p.end());
  
  bool ans = true;
  for (int i = 0; i < 100; i++) {
    for (int j = 0; j < p.size(); j++) {
      if (X-i == p.at(j)) {ans = false; break;}
    }
    if (ans == true) {cout << X-i << endl; break;}
    else {ans = true; }
    for (int j = 0; j < p.size(); j++) {
      if (X+i == p.at(j)) {ans = false; break; } 
    }
     if (ans == true) {cout << X+i << endl; break;}
     else {ans = true;}
  }
  }
  

}

Measured memory_bytes: 3600
#include<cstdio>
#include<algorithm>
using namespace std;
#define MAXN 1000010
char s[MAXN],t[MAXN];
int n,p[MAXN],l,ans,x[MAXN],y[MAXN],sl,sr,k;
int main()
{
	scanf("%d%s%s",&n,s+1,t+1);
	char ls=t[n];
	int np=n,flag=1;
	for(int i=1;i<=n;i++)
		if(s[i]!=t[i])
		{
			flag=0;
			break;
		}
	if(flag==1)
	{
		printf("0\n");
		return 0;
	}
	flag=1;
	for(int i=n-1;i>=0;i--)
		if(t[i]!=ls)
		{
			np=min(np,i+1);
			for(;np;np--)
				if(s[np]==ls)
				{
					p[i+1]=np;
					break;
				}
			if(np==0)
			{
				flag=0;
				break;
			}
			ls=t[i];
		}
	if(flag==0)
	{
		printf("-1\n");
		return 0;
	}
	ans=1;
	sl=0,sr=0;
	for(int i=1;i<=n;i++)
	{
		if(p[i]==0) continue;
		if(l>=p[i])
		{
			k++;
			ans=max(ans,y[sl]+k);
			x[sr]=i-k,y[sr++]=2-k;
			l++;
		}
		else if(l<p[i]&&p[i]<i)
		{
			if(ans==1)
			{
				ans=2,l=i;
				x[sr]=i-k,y[sr++]=2-k;
			}
			else if(ans==2)
			{
				sl=sr;
				x[sr]=i-k,y[sr++]=2-k;
				l=i;
			}
			else
			{
				l=p[i];
				k++;
				for(int j=sl;j<sr;j++)
					if(x[sl]+k-1<p[i]) sl++;
					else
					{
						ans=max(ans,y[j]+k);
						break;
					}
				x[sr]=i-k,y[sr++]=2-k;
			}
		}
		else if(l<p[i]&&p[i]==i)
		{
			k=0;
			sl=sr;
			l=i;
		}
	}
	printf("%d\n",ans);
}

Measured memory_bytes: 13824
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define fi first
#define se second
//a<<b” means 
//shifting the bits of the number ‘a’ on left side by ‘b’ times. 

template<class T> inline bool chmin(T& a, T b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}//a>bならaをbにする

int main(){
    int n;
    cin >> n;
    int dp[n];
    int h[n];
    for(int i=0;i < n;i++){
        cin >> h[i];
    }
    dp[0]=0;
    dp[1]=abs(h[1]-h[0]);
    
    for(int i=2 ;i < n;i++){
        dp[i]=min(dp[i-1]+abs(h[i]-h[i-1]),dp[i-2]+abs(h[i]-h[i-2]));
    }

    cout << dp[n-1] << endl;

}

Measured memory_bytes: 1024
#include <iostream>
#include <vector>
#include <string>

int main()
{
	int N; std::cin >> N;
	std::string S; std::cin >> S;

	int x = 0, max = 0;
	for(int i=0; i<N; i++)
	{
		if(S[i]=='I') x++;
		else x--;
		if(x > max) max = x;
	}
	std::cout << max << std::endl;

	return 0;
}

Measured memory_bytes: 256
import java.util.ArrayList;
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner scan=new Scanner(System.in);
		long n=scan.nextLong();
		ArrayList<Character> al=new ArrayList<Character>();
		while(n>0) {
			long x=(n-1)%26;
			al.add((char) ('a'+x));
			n=(n-1)/26;
		}
		for(int i=al.size()-1;i>=0;i--) {
			System.out.print(al.get(i));
		}
	}

}


Measured memory_bytes: 35920
#include<bits/stdc++.h>
#include<iostream>
#include<cstdio>
#include<vector>
#include<string>
#include<algorithm>
#include<map>
using namespace std;
#define rep(i,x) for(ll i = 0; i < (ll)(x); i++)
#define pb push_back
#define eb emplace_back
#define debug(x) cerr << #x << ": " << (x) << "\n";
#define all(x) (x).begin(), (x).end()
typedef long long ll;
typedef long double ld;
typedef pair<int,int> P;
typedef pair<ll,ll> Pll;
typedef vector<ll> vl;
typedef vector<vector<ll>> vvl;
typedef vector<vector<vector<ll>>> vvvl;
const ll INF = numeric_limits<ll>::max()/4;
const ll MOD = 1e9+7;
const int n_max = 1e5+10;

int main(){
    ll a,b,c; cin >> a >> b >> c;
    ll k; cin >> k;
    ll ans;
    if(k & 1)ans = b-a;
    else ans = a-b;
    if(abs(ans) > 1e18){
        cout << "Unfair" << endl;
        return 0;
    }
    cout << ans << endl;
}

Measured memory_bytes: 256
import java.util.*;
public class Main {
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		String s = in.next();
		String t = in.next();
		String t2 = t.substring(0, t.length()-1);
		if (s.length()== t.length()-1 && s.equals(t2)) {
			System.out.println("Yes");}
		else {
			System.out.println("No");
		}
	}
}

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

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

  int sum = 0;
  for (int i = 0; i < 2; i++) {
    if (A > B) {
      sum += A;
      A--;
    } else {
      sum += B;
      B--;
    }
  }

  cout << sum << endl;
}
/*
  5 3
 */

 


Measured memory_bytes: 256
# -*- coding: utf-8 -*-
h,w = map(int, input().split())
al = [input() for _ in range(h)]
dp = [[0 for _ in range(w)] for _ in range(h)]
MOD = 10**9 + 7
dp[0][0] = 1
for hi in range(h):
    for wi in range(w):
        if al[hi][wi]=="#":
            continue
        s = 0
        if hi-1>=0:
            s += dp[hi-1][wi]
        if wi-1>=0:
            s += dp[hi][wi-1]
        dp[hi][wi] += s
        dp[hi][wi] %= MOD

print(dp[h-1][w-1])


Measured memory_bytes: 44600
#include<bits/stdc++.h>
using namespace std;
 
#define pb push_back
#define ll long long
#define maxn 1000005
#define fr(i,j,k) for(int i=j;i<k;i++)
#define f(n) fr(i,0,n)
#define f1(n) fr(i,1,n+1)
#define ms(i) memset(i,0,sizeof(i));
#define ms1(i) memset(i,-1,sizeof(i));
#define F first
#define S second
#define all(x) x.begin(), x.end()
const int mod = 1e9 + 7;
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n;
    cin >> n;
    map<int,int>mp;
    ll ans = 0;
    vector<int>v(n);
    for (auto &i : v) {
        cin >> i;
        ans += mp[i];
        mp[i]++;
    }
    for (auto &i : v) {
        cout << ans - mp[i] + 1 << '\n';
    }
}


Measured memory_bytes: 8320
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0; i<(n); i++)
#define rep2(i,x,n) for(int i=x; i<(n); i++)
#define all(n) begin(n),end(n)
struct cww{cww(){ios::sync_with_stdio(false);cin.tie(0);}}star;
const long long INF = numeric_limits<long long>::max();
typedef long long ll;
typedef vector<int> vint;
typedef vector<char> vchar;
typedef vector<vector<int>> vvint;
typedef vector<ll> vll;
typedef vector<vector<ll>> vvll;
typedef unsigned long long ull;
#define T 60
#define mod 1000000007
ull modpow(ull k)
{
    if(k==0)
        return 1;
        else
        {
            return (2 * modpow(k - 1)) % mod;
        }
}

int main()
{
    int N;
    cin >> N;
    vector<ull> A(N);
    vector<bitset<T>> B(N);
    ull ans=0;
    vector<ull> S(T);
    ull k = 0;
    rep(i, N)
    {
        cin >> k;
        B[i] = bitset<T>(k);
    }
    rep(i,T)
    {
        ull n0 = 0, n1 = 0;
        rep(j,N)
        {
            if(B[j][i] == 0)
            {
                n0++;
            }
            else
                n1++;
        }
        S[i] = (n0 * n1)%mod;
    }
    rep(i,T)
    {
        ans = (ans + S[i] * modpow(i)) % mod;
    }
    cout << ans;
    return 0;
}

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

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

  int len = S.size();
  int count = 0;
  for(int i = 0; i < len / 2; i++){
    if(S.at(i) != S.at(len - 1 - i)) count++;
  }
  cout << count << endl;
}


Measured memory_bytes: 256
// #include "common.hpp"
// #include "bridge_decomposition.hpp"
#define REP(i, n) for (int i = 0; i < (int)(n); i++)
#define fst first
#define snd second

#include <iostream>
#include <queue>
using namespace std;

#include <vector>
#include <cstdlib>
#include <algorithm>

class BridgeDecomposition{
  std::vector<std::vector<int> >  G;
  std::vector<int> ord;
  std::vector<int> low;
  std::vector<int> par;
  void Dfs(int v, int &times);
  
public:
  std::vector<std::vector<int> > edge_group;
  BridgeDecomposition(const std::vector<std::pair<int, int> > &es);
};

void BridgeDecomposition::Dfs(int v, int &times){
  ord[v] = low[v] = times++;
  for (int w : G[v]){
    if (ord[w] == -1){
      par[w] = v;
      Dfs(w, times);
      low[v] = min(low[v], low[w]);
    } else if (w != par[v]){
      low[v] = min(low[v], low[w]);
    }
  }
}

BridgeDecomposition::BridgeDecomposition(const vector<pair<int, int> > &es){
  int V = 0;
  for (const auto &e : es) V = max(V, max(e.fst, e.snd) + 1);
  
  ord = vector<int>(V, -1);
  low = vector<int>(V, -1);
  par = vector<int>(V, -1);
  G   = vector<vector<int> >(V);
  for (const auto &e : es){
    G[e.fst].push_back(e.snd);
    G[e.snd].push_back(e.fst);
  }

  int times = 0;
  REP(v, V) if (ord[v] == -1){
    Dfs(v, times);
  }
  
  G.clear();
  G = vector<vector<int> > (V);
  
  for (size_t i = 0; i < es.size(); i++){
    pair<int, int> e = es[i];
    if (par[e.snd] != e.fst) swap(e.fst, e.snd);
    if (par[e.snd] != e.fst) continue;
    if (low[e.snd] > ord[e.fst]){
      edge_group.push_back(vector<int>(1, i));
    } else {
      G[e.fst].push_back(e.snd);
      G[e.snd].push_back(e.fst);
    }
  }

  vector<int> visit(V, -1);
  
  int num_cc = edge_group.size();
  REP(s, V) if (visit[s] == -1){
    visit[s] = num_cc;
    queue<int> que;
    while (!que.empty()){
      int v = que.front(); que.pop();
      for (int w : G[v]){
        if (visit[w] == -1){
          visit[w] = num_cc;
          que.push(w);
        }
      }
    }
    num_cc++;
  }
  edge_group.resize(num_cc);
  for (size_t i = 0; i < es.size(); i++){
    pair<int, int> e = es[i];
    if (visit[e.fst] == visit[e.snd]) edge_group[visit[e.fst]].push_back(i);
  }
}


int main(int argc, char *argv[])
{
  int n, m, u, v;
  cin >> n >> m;
  vector<pair<int, int> > es;
  REP(i, m){
    cin >> u >> v;
    if (u > v) swap(u, v);
    es.emplace_back(u, v);
  }
  BridgeDecomposition bd(es);
  vector<pair<int, int> > bs;
  REP(i, bd.edge_group.size()) if (bd.edge_group[i].size() == 1) {
    bs.push_back(es[bd.edge_group[i][0]]);
  }
  sort(bs.begin(), bs.end());
  for (const auto &e : bs){
    cout << e.fst << " " << e.snd << endl;
  }
  return 0;
}

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

using namespace std;

int main() {
    int h, w, n;
#ifdef debug
    w = 1e9;
    n = 1e5;
    cout << w << " " << w << " " << n << endl;
    for (int i = 0; i < n; ++i) cout << i << " " << 2 << endl;
#endif
    scanf("%d %d %d", &h, &w, &n);
    map<pair<int, int>, int> m, visit;
    vector<pair<int, int>> v;
    for (int i = 0; i < n; ++i) {
        int a, b;
        scanf("%d%d", &a, &b);
        m[{a - 1, b - 1}] = 1;
        v.push_back({a - 1, b - 1});
    }
    int dir[] = {0, -1,  -2};
    vector<long long> res(10, 0);

    
    for (auto e: v) {
        for (int i = 0; i < 3; ++i)
            for (int j = 0; j < 3; ++j) {
                int x = e.first  - i;
                int y = e.second - j;
                if (x < 0 || y < 0 || x + 2 >= h || y + 2 >= w || visit.find({x, y}) != visit.end()) continue;
                visit[{x, y}] = 1;
                int travel[] = {0, 1, 2};
                int black = 0;
                for (int ii = 0; ii < 3; ++ii)
                    for (int jj = 0; jj < 3; ++jj) {
                        if (m.find({x + ii, y + jj}) == m.end()) continue;
                        else black++;
                    }
                res[black]++;
            }
    }
    res[0] = 1LL * (h - 2) * (w - 2);
    for (int i = 1; i < 10; ++i) res[0] -= res[i];

    for (int i = 0; i < 10; ++i) printf("%lld\n", res[i]);

    return 0;
}


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

#define MAXN 100005
int n,m;
vector<int> adj[MAXN];
vector<int> in[MAXN];

bool vis[MAXN];
vector<int> topo;

void dfs(int x){
	if(vis[x]) return;
	vis[x] = 1;
	for (int i : adj[x]){
		dfs(i);
	}
	topo.push_back(x);
}

int main(){
	cin>>n>>m;
	for(int i=0; i<m; i++){
		int u,v;cin>>u>>v;
		adj[u].push_back(v);
		in[v].push_back(u);
	}
	memset(vis,0,sizeof(vis));

	for(int i=1; i<=n; i++){
		if(!vis[i]) dfs(i);
	}
	reverse(topo.begin(),topo.end());
	int lp[n+5];
	for(int i : topo){
		if(in[i].size()==0){ lp[i]=0; continue;}
		int mx=0;
		for(int j : in[i]) mx=max(mx,lp[j]);
		lp[i]=mx+1;
	}
	int gmx = 0;
	for(int i=1; i<=n; i++){
		gmx = max(gmx,lp[i]);
	}
	cout<<gmx;
}

Measured memory_bytes: 13952
#include <bits/stdc++.h>
#define FAST ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define MAXX 1000005
#define PI 3.14159265358979323846264338327950
#define ll signed long long int
using namespace std;
ll t , n, ans = 0, k, a[MAXX], b[MAXX], x, y, mn, mx, m = 0;
double f = 0.5;
vector<ll> v;
int main()
{
	string s;
	cin >> s;
	for(ll i = 0; i < s.size(); i+=2){
		if(s[i] != 'R' && s[i] != 'U' && s[i] != 'D'){
			cout << "No";
			return 0;
		}
	}
	for(ll i = 1; i < s.size(); i+=2){
		if(s[i] != 'L' && s[i] != 'U' && s[i] != 'D'){
			cout << "No";
			return 0;
		}
	}
	cout << "Yes";
	return 0;
    
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
 
using namespace std;
using ll = long long;
const int Inf = 1e9 + 5;

bool isPalindrome(string s) {
    string t = s;
    reverse(t.begin(), t.end());
    return t == s;
}

int main()
{
    cin.tie(0);
    ios_base::sync_with_stdio(0); 
    string s;
    cin >> s;
    int n = s.length();
    string t = s.substr(0, (n - 1) / 2);
    string k = s.substr((n + 3) / 2 - 1);
    if (isPalindrome(s) && isPalindrome(t) && isPalindrome(k)) {
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }
    return 0;
}

Measured memory_bytes: 256
/*
  AUTHOR:SOURABH
  CREATED:19:01:20
*/
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

#define ordered_set tree<ll , null_type, less< ll >, rb_tree_tag, tree_order_statistics_node_update>
#define ll long long int
#define ld long double
#define fi first
#define se second
#define pb push_back
#define pob pop_back
#define W while
#define fn(i,x) for(i=0;i<x;i++)
#define fs(i,s,x) for(i=s;i<x;i++)
#define fr(i,x) for(i=x;i>=0;i--)
#define fit(it,s) for(it=s.begin();it!=s.end();it++)
#define mp make_pair
#define pii pair<int,int>
#define pll pair<ll,ll>
#define vii vector<int>
#define vll vector<ll>
#define mii map<int,int>
#define mll map<ll,ll>
#define mod 1000000007
#define MAX 100005
#define M 32

using namespace std;
using namespace __gnu_pbds;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    //freopen("in.txt","r",stdin);
    //freopen(2 "out.txt","w",stdout);

    ll n,m;
    cin>>n>>m;
    if(n==m)
        cout<<"Yes";
    else
        cout<<"No";
    return 0;
}







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

// def
#define debug(x) cout << #x << ": " << x << endl
#define out(x) cout << x << endl
#define repeat(i, a, b) for (int i = (a); i < (b); i++)
#define revrepeat(i, a, b) for (int i = (b)-1; i >= (a); i--)
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define revrep(i, n) for (int i = (n)-1; i > 0; i--)
#define all(x) (x).begin(), (x).end()
#define CYES cout << "Yes" << endl
#define CNO cout << "No" << endl
#define SPC(x) cout << fixed << setprecision(x)

typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef vector<vector<int>> vii;
typedef vector<ll> vl;
typedef vector<vector<ll>> vll;
typedef pair<int, int> P;
typedef complex<ld> Point;
const int MOD = 1e9 + 7;
const int INF = 1e9;
const int MAX_V = 1e5 + 5;
const int MAX_N = 1e5 + 5;
const double PI = acos(-1);

template <class T>
inline bool chmin(T &a, T b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}
template <class T>
inline bool chmax(T &a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}

// how to use priority_queue on pair

int main() {
    int n, t;
    cin >> n >> t;
    vector<P> a(n);
    rep(i, n) {
        cin >> a[i].first >> a[i].second;
    }

    vii dp1(3050, vi(3050, 0));
    vii dp2(3050, vi(3050, 0));

    rep(i, n) {
        auto p = a[i];
        rep(j, t + 1) {
            if (j + p.first <= t) {
                chmax(dp1[i + 1][j + p.first], dp1[i][j] + p.second);
            }

            chmax(dp1[i + 1][j], dp1[i][j]);

            // debug(i);
            // debug(j);
            // debug(dp1[i][j]);
        }
    }

    reverse(all(a));
    rep(i, n) {
        auto p = a[i];
        rep(j, t + 1) {
            if (j + p.first <= t) {
                chmax(dp2[i + 1][j + p.first], dp2[i][j] + p.second);
            }

            chmax(dp2[i + 1][j], dp2[i][j]);

            // debug(i);
            // debug(j);
            // debug(dp2[i][j]);
        }
    }

    reverse(all(a));
    int ans = 0;
    rep(i, n) {
        rep(j, t) {
            chmax(ans, dp1[i][j] + dp2[n - i - 1][t - 1 - j] + a[i].second);

            // debug(ans);
        }
    }
    out(ans);
    return 0;
}


Measured memory_bytes: 73216
#include <iostream>

using namespace std;

int is_haming(int num)
{
	while (num % 2 == 0) num /= 2;
	while (num % 3 == 0) num /= 3;
	while (num % 5 == 0) num /= 5;

	if (num == 1) return (1);
	else return (0);
}

int main()
{
	int n, m;

	while (cin >> n, n){
		cin >> m;

		int count = 0;
		for (int i = n; i <= m; i++){
			count += is_haming(i);
		}

		cout << count << endl;
	}

	return 0;
}

Measured memory_bytes: 1160
import java.util.*;

class Main {
    public static void main(String[] args) {
        new Solver().run();
    }
}

class Pair1 implements Comparable<Pair1> {
    int h;
    int b;
    public Pair1(int h, int b) {
        this.h = h;
        this.b = b;
    }

    @Override
    public int compareTo(Pair1 other) {
        return -Integer.compare(this.b, other.b);
    }
}

class Solver {

    private boolean check(List<Pair1> a) {
        int cur = 0;
        for (Pair1 p : a) {
            if (cur + p.b < 0) return false;
            cur += p.h;
        }
        return true;
    }

    public void run() {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int total = 0;
        List<Pair1> ls = new ArrayList<Pair1>();
        List<Pair1> rs = new ArrayList<Pair1>();
        List<String> S = new ArrayList<String>();
        for (int i = 0; i < N; i++) {
            String s = sc.next();
            int h = 0, b = 0;
            for (char ch : s.toCharArray()) {
                if (ch == '(') h++;
                else h--;
                b = Math.min(h, b);
            }
            if (h >= 0) ls.add(new Pair1(h, b));
            else rs.add(new Pair1(-h, b-h));
            total += h;
        }
        Collections.sort(ls);
        Collections.sort(rs);

        if (check(ls) && check(rs) && total == 0) {
            System.out.println("Yes");
        } else {
            System.out.println("No");
        }

        return;
    }

}

Measured memory_bytes: 92404
#include <iostream>
#include <vector>
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <iomanip>
using namespace std;

long long gcd(long long x, long long y){
    if(y==0) return x;
    return gcd(y, x%y);
}
int main() {
    int N; cin >> N;
    long long ans=0;
    for(int i=0; i<N; ++i){
        int a; cin >> a;
        ans+=a-1;
    }
    cout << ans << endl;
    return 0;
}
        

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

public class Main{
	public static void main(String[] args){
		try{
			new Main();
		}catch(IOException e){
			e.printStackTrace();
		}
	}
	
	public Main() throws IOException{
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		List<String> Ans = new ArrayList<String>();
		String line = in.readLine();
		
		int size = Integer.parseInt(line);
		for(int n=0; n<size; n++){
			line = in.readLine();
			int type = 0;
			
			String c = line.substring(0, 2);
			if(c.equals(">'")){
				int count = 0;
				int sharp = 0;
				for(int i=2; i<line.length(); i++){
					c = line.substring(i, i+1);
					if(c.equals("=")){
						count++;
					}
					else if(c.equals("#")){
						if(count > 0){
							count = -count;
							sharp = 1;
						}
						else{
							type = -1;
							break;
						}
					}
					else if(c.equals("~")){
						if(i != line.length()-1){
							type = -1;
							break;
						}
						
						if(count==0 && sharp==1){
							type = 1;
							break;
						}
						else{
							type = -1;
							break;
						}
					}
					else{
						type = -1;
						break;
					}
				}
			}
			else if(c.equals(">^")){
				int count = 0;
				for(int i=2; i<line.length(); i++){
					c = line.substring(i, i+1);
					if(count%2==0 && count>=2 && c.equals("~")){
						if(i==line.length()-1){
							type = -1;
							break;
						}
						
						c = line.substring(i+1, i+2);
						if(c.equals("~")){
							type = 2;
							break;
						}
						else{
							type = -1;
							break;
						}
					}
					if(i%2==0){
						if(!c.equals("Q")){
							type = -1;
							break;
						}
						count++;
					}
					if(i%2==1){
						if(!c.equals("=")){
							type = -1;
							break;
						}
						count++;
					}
					
					if(!c.equals("Q") && !c.equals("=") && !c.equals("~")){
						type = -1;
						break;
					}
				}
			}
			else{
				type = -1;
			}
			
			switch(type){
				case 1:
					Ans.add("A");
					break;
					
				case 2:
					Ans.add("B");
					break;
					
				default:
					Ans.add("NA");
			}
		}
		
		for(int n=0; n<Ans.size(); n++){
			System.out.println(Ans.get(n));
		}
	}
}

Measured memory_bytes: 11000
#include<bits/stdc++.h>
using namespace std;
#define boost ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define mp make_pair
#define pb push_back
#define fp first
#define sp second
typedef long long int ll;
typedef pair<ll,ll> pp;
#define check(x, i) ((x>>i)&1LL)
#define set(x,i) (x|(1LL<<i))
#define unset(x,i) (x&~(1LL<<i))
#define INF LONG_MAX
#define MAX_N 20
#define MAX 4000005
#define mod 1000000007
#define REP(i,n) for(i=0;i<n;i++)
#define FOR(i,a,b) for(i=a;i<=b;i++)
#define RFOR(i,a,b) for(i=a;i>=b;i--)
#define len(i,s) for(i=0;s[i];i++)
#define T() while(t--)
ll gcd (ll a, ll b){return (a?gcd(b%a,a):b);}
ll pow1(ll a,ll b,ll MOD){ll ans=1;while(b!=0){if(b&1)ans=(ans*a)%MOD;a=(a*a)%MOD;b=b/2;}return ans;}
ll modInverse(ll a,ll p){return pow1(a,p-2,p);}
#define PI 3.14159265


int main()
{
  boost
  #ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);    
    freopen("output.txt", "w", stdout);
#endif
ll k;
string s;
cin>>k>>s;
ll l=s.length();
if(l>k)
{
	for(int i=0;i<k;i++)
		cout<<s[i];
		cout<<"...";
}
else
cout<<s;

}

Measured memory_bytes: 3660
#include<iostream>
int s,t,u,v,n,c,d,x,y,i,j,f[102][102],a[4]={1,0,-1,0};int rec(int x,int y){if(f[x][y]==c)for(int i=4;i-->0;f[x][y]=9)rec(x+a[i],y+a[(i+3)%4]);}main(){for(;std::cin>>x>>y>>s>>t>>u>>v>>n,x;puts(f[u][v]-9?"NG":"OK")){for(j=0;j++<101;)for(i=0;i++<101;)f[i][j]=0;for(;n-->0;c=f[s][t]){std::cin>>c>>d>>x>>y;for(i=2;d&i-->0;)for(j=4;j-->0;)f[x+i][y+j]=c;for(i=4;!d&i-->0;)for(j=2;j-->0;)f[x+i][y+j]=c;}c&&rec(s,t);}}

Measured memory_bytes: 0
from math import floor
N, P = map(int, input().split())

if N == 1:
  print(P)
  exit(0)
  
ans = 1
#i = floor(pow(P,1/N))
#print(i)
i = 2

def prime_table(n):
  list = [True for _ in range(n + 1)]
  i = 2
  while i * i <= n:
    if list[i]:
      j = i + i
      while j <= n:
        list[j] = False
        j += i
    i += 1

  table = [i for i in range(n + 1) if list[i] and i >= 2]
  return table

T = prime_table(floor(pow(P,1/N)))

for i in range(len(T)):
  if T[i] ** N > P:
    break
  while P % T[i]**N == 0:
    ans *= T[i]
    P = P // T[i]**N
  
print(ans)

Measured memory_bytes: 12760
'''
問題：
    高橋君は金色の硬貨が好きです。
    自分が持っている 500円硬貨 1枚につき 1000、
    5円硬貨 1枚につき 5の嬉しさ を得ます。

    高橋君は X 円を持っています。
    これを高橋君の嬉しさが最大になるように両替したとき、高橋君の嬉しさはいくらになりますか？

    (なお、利用できる硬貨は 500 円玉、100 円玉、50 円玉、10 円玉、5円玉、1 円玉の 6 種類とします。)
'''

'''
    Xは整数
    0 ≦ X ≦ 1,000,000,000
'''
class Yorokobi:
    def __init__(self, money, yorokobi):
        self.money = money
        self.yorokobi = yorokobi

    def calc_yorokobi(self, credit):    # credit （残金？）を入力として受け取り、喜びを計算して返す
        return (credit // self.money) * self.yorokobi

# 標準入力から X の値を取得する
input_x = int(input())

yorokobi_500 = Yorokobi(500, 1000)
yorokobi_5 = Yorokobi(5, 5)

result = 0  # 結果格納用
if input_x >= 500:
    result += yorokobi_500.calc_yorokobi(input_x)   # 高橋君 500円の喜び
    result += yorokobi_5.calc_yorokobi(input_x % 500)   # 高橋君 5円の喜び
else:
    result += yorokobi_5.calc_yorokobi(input_x)

print(result)

# ret1 = input_x // 500  # 500円で割った商
# ret2 = ret1 * 1000  # 高橋君 500円の喜び
# ret3 = input_x - (ret1 * 500)   # X円から500円の枚数分を引いたお金
# ret4 = ret3 // 5 # （X円から500円の枚数分を引いたお金）÷ 5
# ret5 = ret4 * 5 # 高橋君 5円の喜び
# print(ret2 + ret5)


Measured memory_bytes: 9112
# coding: utf-8
import sys
#from operator import itemgetter
sysread = sys.stdin.buffer.readline
read = sys.stdin.buffer.read
#from heapq import heappop, heappush
from collections import defaultdict
sys.setrecursionlimit(10**7)
#import math
#from itertools import product, accumulate, combinations, product
#import bisect# lower_bound etc
#import numpy as np
#from copy import deepcopy
#from collections import deque

def run():
    N = int(sysread())
    D = list(map(int, sysread().split()))
    mod = 998244353
    dict = defaultdict(lambda:[])
    max_depth = 0
    for node, d in enumerate(D, 1):
        dict[d].append(node)
        max_depth = max(max_depth, d)
    if dict[0] != [1]:
        print(0)
        return None

    ans = 1
    for i in range(1, max_depth+1):
        pre = len(dict[i-1])
        current = len(dict[i])
        val =pow(pre, current, mod)
        ans *= val
        ans %= mod
    print(ans)
    return None

    #print(factorials)
if __name__ == "__main__":
    run()

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

int d, g;
int ans = 100100100;


bool dfs(int i, int now, int count, vector<int> p, vector<int>& c) {
    if(i == d) {
        if(g <= now) {
            ans = min(ans, count);
        } else {
            for(int j = d-1; 0 <= j; j--) {
            if(g <= now + p.at(j) * (j+1) * 100) {
                int r = (g - now) / ((j+1) * 100);
                if(now + r * (j+1) * 100 < g) r++;
                ans = min(ans, count + r);
                }
            }
        }

        return false;
    }

    int next = now;

    if(dfs(i + 1, next, count, p, c)) return true;

    next += p.at(i) * (i + 1) * 100 + c.at(i);
    count += p.at(i);
    p.at(i) = 0;
    if(dfs(i + 1, next, count, p, c)) return true;

    return false;
}

int main() {
    cin >> d >> g;
    vector<int> p(d), c(d);
    rep(i, d) cin >> p.at(i) >> c.at(i);
    dfs(0, 0, 0, p, c);
    cout << ans << endl;
    return 0;
}

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


Measured memory_bytes: 256
import Control.Applicative
import Control.Monad
import Control.Monad.ST
import qualified Data.ByteString as BS
import Data.Functor
import Data.Function
import Data.Monoid
import Data.Maybe
import Data.List
import qualified Data.Foldable as Foldable
import qualified Data.Set as Set
--import qualified Data.Sequence as Sequence
import Data.List.Split
import Data.Bits
import Data.Char
import Data.Ix
import Data.Ratio
import Data.Ord
import Data.Tuple
--import Data.Array
--import Data.Array.Unboxed
import Data.Array.IArray
import Data.Array.MArray
import Data.Array.IO
import Data.Array.ST
import Data.IORef
import Data.STRef
-- import System.IO.Unsafe

-- templete
readInt = read :: String -> Int
readInteger = read :: String -> Integer
readDouble = read :: String -> Double
getInt = readLn :: IO Int
getInts = map readInt . words <$> getLine
getInteger = readLn :: IO Integer
getIntegers = map readInteger . words <$> getLine
getDouble = readLn :: IO Double
getDoubles = map readDouble . words <$> getLine
sjoin :: (Show a) => [a] -> String
sjoin = unwords . map show
cond :: a -> a -> Bool -> a
cond t f c = if c then t else f
apply2 :: (a -> a -> b) -> [a] -> b
apply2 f [x,y] = f x y
apply3 :: (a -> a -> a -> b) -> [a] -> b
apply3 f [x,y,z] = f x y z
apply4 :: (a -> a -> a -> a -> b) -> [a] -> b
apply4 f [x,y,z,w] = f x y z w
fnTuple :: (a -> b, a -> c) -> a -> (b, c)
fnTuple (f,g) a = (f a, g a)
replace :: (Eq a) => a -> a -> [a] -> [a]
replace x y = map (\z -> if z==x then y else z)
binMap :: (a -> a -> b) -> [a] -> [b]
binMap f (x:xs@(y:_)) = f x y : binMap f xs
binMap _ _ = []
splitRec :: Int -> [a] -> [[a]]
splitRec _ [] = []
splitRec n xs = let (y,ys) = splitAt n xs in y : splitRec n ys
infixl 7 `divCeil`
divCeil :: Integral a => a -> a -> a
x `divCeil` y = (x+y-1) `div` y
coverC :: Ord a => (a, a) -> a -> Bool
coverC (l,r) x = l<=x && x<=r
coverH :: Ord a => (a, a) -> a -> Bool
coverH (l,r) x = l<=x && x<r
-- templete

data Rank = AAA | AA | A | B | C | D | E | NA deriving (Show, Eq, Ord)

m500 t
  | t < 35.50 = AAA
  | t < 37.50 = AA
  | t < 40.00 = A
  | t < 43.00 = B
  | t < 50.00 = C
  | t < 55.00 = D
  | t < 70.00 = E
  | otherwise = NA

m1000 t
  | t < 71.00 = AAA
  | t < 77.00 = AA
  | t < 83.00 = A
  | t < 89.00 = B
  | t < 105.00 = C
  | t < 116.00 = D
  | t < 148.00 = E
  | otherwise = NA
  
main = map (apply2 (,) . map readDouble . words) . lines <$> getContents >>= mapM_ (print . uncurry max . fmap m500 . swap . fmap m1000)


Measured memory_bytes: 4268
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int INF = 1e9;
const ll LINF = 1e18;
inline ll gcd(ll a, ll b) { return b ? gcd(b, a%b) : a; }
inline ll lcm(ll a, ll b) { return a / gcd(a, b)*b; }


map<char,int> mp;
int N;

pair<bool,char> rec(int& i,const string& S){
    if(i == S.length()) return {true,' '};
    if(S[i] == '['){
        bool ok; char l,r;
        tie(ok,l) = rec(++i,S);
        if(!ok) return {false,' '};
        tie(ok,r) = rec(++i,S);
        if(!ok) return {false,' '};
        
        if(mp[l] != 0 && mp[r] != 0) return {false,' '};
        if(mp[l] == 0 && mp[r] == 0) return {false,' '};
        
        i++;
        if(mp[l] != 0){
            mp[l]--;
            return {true,l};
        }
        if(mp[r] != 0){
            mp[r]--;
            return {true,r};
        }
    }else{
        return {true,S[i++]};
    }
    return {true,' '};
}
int main(void) {
    cin.tie(0); ios_base::sync_with_stdio(false);
    string S; cin >> S;
    char a; int v;
    while(cin >> a >> v){
        mp[a] = v;
    }
    N = (int)mp.size();
    int i = 0;
    bool ok;
    tie(ok,ignore)= rec(i,S);
    for(auto p:mp){
        if(p.second) ok = false;
    }
    if(ok){
        cout << "Yes" << endl;
    }else{
        cout << "No" << endl;
    }
    return 0;
}




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


int main() 
{
    int A, B;

    cin >> A >> B;

    int ans = 0;

    for( int i=0 ; i<2 ; i++ )
    {
        if( A > B ) 
        {
            ans += A;
            A--;
        }
        else
        {
            ans += B;
            B--;
        }
    }

    cout << ans << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <math.h>

using namespace std;

int main(void)
{
    double N, T, A, H[1001], min=100000000, mini=-1;
    int i;

    cin >> N >> T >> A;

    for(i=1; i<=N; i++){
        cin >> H[i];

        if(fabs(A-(T-H[i]*0.006)) < min){
            min = fabs(A-(T-H[i]*0.006));

            mini = i;
        }
    }

    cout << mini << endl;

    return 0;
}

Measured memory_bytes: 256
#include <cstdio>
#include <cstdlib>
#include <string>
#include <iostream>
#include <vector>
#include <stack>
using namespace std;
using ull = unsigned long long;
#define rep(i, n) for (int i = 0; i < n; i++)

int main(){
  string S;
  int K;
  cin >> K >> S;
  if (S.size() <= K) cout << S << endl;
  else {
    rep(i, K) cout << S[i];
    cout << "..." << endl;
  }
  return 0;
}

Measured memory_bytes: 3628
var inp = require('fs').readFileSync('/dev/stdin', 'utf8');
var a = inp.split('\n');
var k = a[0].split(' ').map(v => parseInt(v))[0];
var x = a[1].split(' ').map(v => parseInt(v));

var max = 0;
for (var i = 0; i < x.length; i++) {
  var d = 0;
  if (i === x.length - 1) {
    d = k - x[i] + x[0];
  } else {
    d = x[i + 1] - x[i];
  }
  max = Math.max(max, d);
}
console.log(k - max);

Measured memory_bytes: 33800
// atcoder - dp - C
#include <bits/stdc++.h>

using namespace std;

const int N = 100005;

int n, a[N][3], dp[N][3];

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> n;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < 3; j++) {
			cin >> a[i][j];
		}
	}

	dp[0][0] = a[0][0];
	dp[0][1] = a[0][1];
	dp[0][2] = a[0][2];
	for (int i = 1; i < n; i++) {
		dp[i][0] = max(dp[i-1][1], dp[i-1][2]) + a[i][0];
		dp[i][1] = max(dp[i-1][0], dp[i-1][2]) + a[i][1];
		dp[i][2] = max(dp[i-1][0], dp[i-1][1]) + a[i][2];
	}
	int ans = max(dp[n-1][0], max(dp[n-1][1], dp[n-1][2]));
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 2560