akhauriyash/Code-Regression huggingface dataset:
#define _USE_MATH_DEFINES
#include <iomanip>
#include <iostream>
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <map>
#include <tuple>
#include <climits>
#include <algorithm>
#include <cmath>
using namespace std;

typedef long long LL;
typedef vector<int> VI;
typedef vector<double> VD;
typedef vector<LL> VLL;
typedef vector<string> VS;
typedef vector<bool> VB;
typedef vector<vector<int>> VVI;
typedef vector<vector<long long>> VVLL;
typedef vector<vector<bool>> VVB;
typedef vector<vector<double>> VVD;

#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define all(a) (a).begin(),(a).end()

const int MOD = 1000000007;

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

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

void debug(VI &arr){
	int n=arr.size();
	rep(i,n){
		cout<<arr.at(i)<<endl;
	}
}

void debug(VVI &board){
	int h = board.size();
	int w = board.at(0).size();
	rep(i,h){
		rep(j,w){
			cout << board.at(i).at(j) << " ";
		}
		cout<<endl;
	}
}

void debug(VVLL &board){
	int h = board.size();
	int w = board.size();
	rep(i,h){
		rep(j,w){
			cout<<board.at(i).at(j)<<" ";
		}
		cout<<endl;
	}
}

LL gcd(LL a,LL b){
	return b==0?a:gcd(b,a%b);
}

LL lcm(LL a,LL b){
	return a*b/gcd(a,b);
}

int main(){
	//cout<<fixed;
	//cout<<setprecision(9)<<...
	int x;cin>>x;
	VB dp(x+1,false);
	dp[0]=true;
	for(int i=1;i<=x;i++){
		for(int j = 100;j<=105;j++){
			if(i-j<0)continue;
			dp[i] = dp[i-j] or dp[i];
		}
	}
	cout<<dp[x]<<endl;
	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define ll long long
int n;
vector<vector<ll>> v(16,vector<ll>(16));
vector<ll> dp((1<<16)-1,-1);
vector<ll> dp1((1<<16)-1,-1);
ll solve(int s)
{
    if(s==0)
    return 0;
    ll ans=0;
    for(int m=s;m!=0;m=((m-1)&s))
    {
        // cout<<m<<" "<<dp[m]<<"\n";
        if(dp1[(~m)&s]!=-1)
        ans = max(ans,dp[m]+dp1[(~m)&s]);
        else
        ans = max(ans,dp[m]+solve((~m)&s));
    }
    return dp1[s] = ans;
}
int main() {
    cin>>n;
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<n;j++)
        {
            cin>>v[i][j];
        }
    }
    for(int k=1;k<(1<<n);k++)
    {
        ll ans=0;
        for(int i=0;i<16;i++)
        {
            for(int j=i+1;j<16;j++)
            {
                if(((1<<i)&k)&&((1<<j)&k))
                ans+=v[i][j];
            }
        }
        dp[k]=ans;
    }
    cout<<solve((1<<n)-1);
}


Measured memory_bytes: 4108
#include <iostream>
#include <vector>
#include <algorithm>
#include <string.h>
#include <string>
#include <iomanip>
#include <math.h>

typedef long long int ll;

#define FOR(i,n,m) for(ll i=(ll)(m);i<(ll)(n);++i)
#define REP(i,n) FOR(i,n,0)
#define IREP(i,n) for(ll i=(ll)(n);i>=0;--i)
#define OF64 std::setprecision(10)

const ll MOD = 1000000007;

using namespace std;

int main()
{
	ll A, B, C, K;
	cin >> A >> B >> C >> K;
	if (K % 2 == 0)
	{
		cout << A - B << endl;
	}
	else
	{
		cout << B - A << endl;
	}
	return 0;
}

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

#define MAX_N 1000
#define MAX_M 1000



int main(){
    double l;
    cin >> l;
    double tmp = l / 3;
    double ans = pow(tmp, 3);
    prtd(10, ans);
}




Measured memory_bytes: 256
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <queue>
#include <cmath>

using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)

double dd(double a, double b){
	return sqrt(a * a + b * b);
}

int n, x[1002], y[1002], r[1002];
double dist[1002];
double d[1002][1002];
int main(){
	int xs, ys, xt, yt;
	cin >> xs >> ys >> xt >> yt >> n;
	rep(i, n) cin >> x[i] >> y[i] >> r[i];
	x[n] = xs; y[n] = ys;
	x[n+1] = xt; y[n+1] = yt;
	rep(i, n + 2) rep(j, i) d[j][i] = d[i][j] = max(0.0, dd(x[i] - x[j], y[i] - y[j]) - r[i] - r[j]);
	
	//rep(i, n + 2) rep(j, n + 2) cerr<<d[i][j]<<(j==n+1?"\n":" ");

	rep(i, n + 2) dist[i] = 1e12;
	priority_queue<pair<double,int>> q;
	q.emplace(0, n);
	while(!q.empty()){
		double cd;
		int c;
		cd = q.top().first; c = q.top().second; q.pop();
		if(dist[c] <= -cd) continue;
		dist[c] = -cd;

		rep(i, n + 2) if(dist[i] > -cd + d[c][i] + 1e-9){
			q.emplace(cd - d[c][i], i);
		}
	}
	cout << fixed << setprecision(20) << dist[n + 1] << endl;
	return 0;
}

Measured memory_bytes: 18412
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <string>
#include <sstream>
#include <complex>
#include <vector>
#include <list>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <set>

#define rep(i, n) for (int i = 0; i < (n); i++)
#define rrep(i, n) for (int i = (n) - 1; i >= 0; i--)
#define reps(i, n) for (int i = 1; i <= (n); i++)
#define repi(i, a, b) for (int i = (a); i < (b); i++)
#define all(a) (a).begin(), (a).end()
#define bit(b) (1ull << (b))

using namespace std;
using i32 = long long;
using u32 = unsigned long long;
using i64 = long long;
using u64 = unsigned long long;
using f64 = double;
using vi32 = vector<i32>;
using vu32 = vector<u32>;
using vi64 = vector<i64>;
using vu64 = vector<u64>;
using vf64 = vector<f64>;
using vstr = vector<string>;
using vvi32 = vector<vi32>;
using vvu32 = vector<vu32>;
using vvi64 = vector<vi64>;
using vvu64 = vector<vu64>;
using vvf64 = vector<vf64>;

template<typename T, typename S> void amax(T &x, S y) { if (x < y) x = y; }
template<typename T, typename S> void amin(T &x, S y) { if (y < x) x = y; }

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout << fixed << setprecision(16);
  int a, b;
  cin >> a >> b;
  if (b % a == 0) cout << a + b << endl;
  else cout << b - a << endl;
  return 0;
}


Measured memory_bytes: 256
N = int(input())
ans = []

for i in range(N + 1):
    count = 0
    n_f = N - i
    n_s = i
    while n_f != 0:
        count += n_f % 6
        n_f //= 6
    while n_s != 0:
        count += n_s % 9
        n_s //= 9
    ans.append(count)

print(min(ans))

Measured memory_bytes: 3864
#include<bits/stdc++.h>
using namespace std;
typedef vector<int> vi;
typedef pair<int, int> pi;
typedef long long ll;
typedef vector<ll> vll;
typedef vector<pi> vpi;

#define debugone(x) cout << #x << " " << x << endl;
#define debugtwo(x) cout << #x << "-------------" << endl;for(auto &it: x) cout << it << " ";cout << endl;
#define debugthree(x, i, j) cout << #x << "------------" << endl;cout << "from " << i << " to " << j << endl;for(int k=i; k<=j; k++) cout << x[k] << " ";cout << endl;

const int mod = (int)1e9 + 7;

int main(int argc, char *argv[]){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	int n, m;
	cin >> n >> m;
	vector<bool> dang(n+1);
	for(int i=0; i<m; i++){
		int x;
		cin >> x;
		dang[x] = true;
	}

	vector<long long> numberOfWays(n+1);
	numberOfWays[0] = 1;
	numberOfWays[1] = (dang[1] ? 0 : 1);
	for(int step = 2; step <= n; step++){
		numberOfWays[step] = (dang[step] ? (0) : (numberOfWays[step-1] + numberOfWays[step-2])%mod);
	}

	cout << numberOfWays[n] << endl;
}

Measured memory_bytes: 1024
N, M = map(int, input().split())
H = list(map(int, input().split()))
X = [tuple(map(int, input().split())) for _ in range(M)]

mp = {}
for v in range(1, N+1):
    mp[v] = True
for a, b in X:
    if H[a-1] <= H[b-1]:
        mp[a] = False
    if H[b-1] <= H[a-1]:
        mp[b] = False
ans = 0
for v in range(1, N+1):
    if mp[v]:
        ans += 1
print(ans)

Measured memory_bytes: 105392
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
#define rep(i,n) for(ll i=0;i<(ll)(n);i++)
#define all(a)  (a).begin(),(a).end()
#define pb push_back
#define maxup(a,b) (a=max(a,b))
#define minup(a,b) (a=min(a,b))
#define INF 999999999
int n;




int main(){
    int n;
    while(cin>>n&&n){
        int dp[256][256][4];
        rep(i,256)rep(j,256)rep(k,4)dp[i][j][k] = 0;
        vector<string> data(n);
        rep(i,n)cin>>data[i];

        rep(i,n){
            rep(j,n){
                if(data[i][j]=='1'){
                    if(j-1>=0)          dp[i][j][0] = dp[i  ][j-1][0]+1;
                    else                dp[i][j][0] = 1;
                    if(i-1>=0&&j-1>=0)  dp[i][j][1] = dp[i-1][j-1][1]+1;
                    else                dp[i][j][1] = 1;
                    if(i-1>=0)          dp[i][j][2] = dp[i-1][j  ][2]+1;
                    else                dp[i][j][2] = 1;
                    if(i-1>=0&&j+1>=0)  dp[i][j][3] = dp[i-1][j+1][3]+1;
                    else                dp[i][j][3] = 1;
                }
            }
        }
        int maxi = -1;
        rep(i,n){
            rep(j,n){
                rep(k,4){
                    maxup(maxi,dp[i][j][k]);
                }
            }
        }
        cout<<maxi<<endl;
    }
}
 

Measured memory_bytes: 2312
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <numeric>
using namespace std;
int main() {
  string s, t;
  cin >> s >> t;
  if (s.length() + 1 != t.length()) {
    printf("No\n");
    return 0;
  }
  for (int i = 0; i < s.length(); i++) {
    if (s[i]!=t[i]) {
      printf("No\n");
      return 0;
    }
  }
  printf("Yes\n");
  return 0;
}

Measured memory_bytes: 3156
r,g,b,n=map(int,input().split())
cnt=0
for i in range(0,n+1):
    for j in range(0,n-i+1):
        bb=n-(i*r+j*g)
        s=bb+i*r+j*g
        if bb<0:
            continue
        if s==n and bb%b==0:
            cnt+=1
        if j*g>n or i*r>n or s-bb>n:break
    if i*r>n:break
print(cnt)


Measured memory_bytes: 41692
#include <bits/stdc++.h>
typedef long long ll;
typedef long double ld;
const int INF=1e9,MOD=1e9+7,ohara=1e6+10;
const ll LINF=1e18;
using namespace std;

#define rep(i,n) for(int (i)=0;(i)<(int)(n);(i)++)
#define rrep(i,a,b) for(int i=(a);i<(b);i++)
#define rrrep(i,a,b) for(int i=(a);i>=(b);i--)
#define all(v) (v).begin(), (v).end()
#define Size(n) (n).size()
#define Cout(x) cout<<(x)<<endl
#define doublecout(a) cout<<fixed<<setprecision(15)<<a<<endl;
#define Cerr(x) cerr<<(x)<<endl
#define fi first
#define se second
#define P pair<ll,ll> 
#define m_p make_pair
#define V vector<ll> 
#define U_MAP unordered_map<ll,ll>

ll n,cnt,ans,a,b,c,d,tmp,tmpp,m,h,w,x,y,sum,pos,k,l,r;
ld doua;
int dy[]={1,0,-1,0};
int dx[]={0,1,0,-1};
//int dy[]={-1,0,1,-1,1,-1,0,1};
//int dx[]={-1,-1,-1,0,0,1,1,1};
string alph("abcdefghijklmnopqrstuvwxyz"),s;
bool fl;
struct edge{int to,cost;};
ll yoyu;

//-------------------------↓↓↓↓↓↓------------------------

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

    cin>>l>>r;
    if(r-l>=2019){
        Cout(0);
    }
    else{
        ans=LINF;
        rrep(i,l,r){
            rrep(j,i+1,r+1){
                ans=min(ans,(i%2019LL*j%2019LL));
            }
        }
        Cout(ans);
    }
    return 0;
}


Measured memory_bytes: 256
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace ABC052A
{
    class Program
    {
        static void Main(string[] args)
        {
            int s,S,A, B, C, D;

			var word = Console.ReadLine().Split(' ');
			A = int.Parse(word[0]);
			B = int.Parse(word[1]);
			C = int.Parse(word[2]);
			D = int.Parse(word[3]);

			s = A * B; S = C * D;

            if (s < S)
            {
                Console.WriteLine(S);
            }

            else if (A * B > C * D)
            {
                Console.WriteLine(s);
            }

            else if (A * B == C * D)
            {
                Console.WriteLine(s);
            }
               
			Console.ReadKey();
        }
    }
}


Measured memory_bytes: 11092
#include <bits/stdc++.h>
#include <boost/multiprecision/cpp_int.hpp>
#include <boost/range/adaptor/reversed.hpp>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
typedef long long int ll;

#define PI (acos(-1))
#define REP(i,n) for(ll (i)=0;(i)<(n);(i)++)

#define dump(x)  cerr << #x << " = " << (x) << endl;
#define dumparr(x) cerr << #x ; for(auto elem: x){cerr << " " << elem;} cerr << endl;
#define dumppairs(x) cerr << #x ; for(auto elem: x){cerr << "(" << elem.first << " " << elem.second << ") ";} cerr << endl;
#define dumpline cerr << "**********************" << endl;
#define dumpwline(x) cerr << "******** " << #x << "=" << (x) << " ********" << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;
#define ARRAY_LENGTH(array) (sizeof(array) / sizeof(array[0]))

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

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    cin>>n;
    map<int,int>mp;
    int a[n+1];
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        mp[a[i]]=i;
    }
    sort(a+1,a+n+1);
    for(int i=1;i<=n;i++)
        cout<<mp[a[i]]<<' ';
    cout<<endl;
    return 0;
}


Measured memory_bytes: 5888
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <sstream>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <numeric>
#include <cctype>

#define rep(i, n) for(int i = 0; i < (n); i++)
#define FOR(i, a, b) for(int i = (a); i < (b); i++)
#define ALL(v) (v).begin(), (v).end()
#define REV(s) (s).rbegin(), (s).rend()
#define MEMSET(v, s) memset(v, s, sizeof(v))
#define MP make_pair
#define X first
#define Y second

using namespace std;

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

int notes[31];
int yuta[31];
int dp[31][1<<16];
int pop[1<<16];

int popcnt(int x){
	int cnt = 0;
	while(x){
		++cnt;
		x &= x-1;
	}
	return cnt;
}

int main(){
	rep(i, 1<<16) pop[i] = popcnt(i);

	int n, c;
	while(cin >> n >> c, n|c){
		MEMSET(notes, 0);
		MEMSET(yuta, 0);
		MEMSET(dp, -1);
		rep(i, n){
			rep(j, 16){
				int x;
				cin >> x;
				if(x) notes[i] |= 1<<j;
			}
		}
		rep(i, c){
			rep(j, 16){
				int x;
				cin >> x;
				if(x) yuta[i] |= 1<<j;
			}
		}

		dp[0][0] = 0;
		rep(i, n){
			rep(j, 1<<16){
				if(dp[i][j] < 0) continue;
				int x = j|notes[i];
				rep(k, c+1){
					dp[i+1][x^(x&yuta[k])] = max(dp[i+1][x^(x&yuta[k])], dp[i][j]+pop[x&yuta[k]]);
				}
			}
		}
		cout << *max_element(dp[n], dp[n+1]) << endl;
	}

	return 0;
}

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

int main() {
  char a;
  cin >> a;
  switch (a) {
    case 'A':
      cout << 'T';
      break;
    case 'C':
      cout << 'G';
      break;
    case 'G':
      cout << 'C';
      break;
    case 'T':
      cout << 'A';
  }
  return 0;
}

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

using namespace std;

int main() {
  int N;
  long long H, W;
  cin >> N >> H >> W;
  vector<long long> A(N), B(N);
  for (int i = 0; i < N; i++) cin >> A[i] >> B[i];
  int ans = 0;
  for (int i = 0; i < N; i++) ans += A[i] >= H && B[i] >= W;
  cout << ans << endl;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define rep(i,n)for(int i=0;i<(n);i++)
#define MOD 1000000007
#define INF 0x3f3f3f3f
#define INFL 0x3f3f3f3f3f3f3f3f
#define EPS (1e-10)
using namespace std;
typedef long long ll;
typedef pair<int, int>P;

string s[2];
int dx[]{ 1,-1,0,0 }, dy[]{ 0,0,1,-1 };
signed main() {
	map<char, bool>used;
	int n; scanf("%d", &n);
	cin >> s[0] >> s[1];
	ll ans = 1;
	if (s[0][0] == s[1][0])ans *= 3;
	else ans *= 6;
	used[s[0][0]] = used[s[1][0]] = true;
	for (int i = 1; i < n; i++) {
		if (used[s[0][i]]) {
			continue;
		}
		used[s[0][i]] = used[s[1][i]] = true;
		if (s[0][i] == s[1][i]) {
			if (s[0][i - 1] == s[1][i - 1])ans *= 2;
			else ans *= 1;
		}
		else {
			if (s[0][i - 1] == s[1][i - 1])ans *= 2;
			else ans *= 3;
		}
		ans %= MOD;
	}
	cout << ans%MOD << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#define _USE_MATH_DEFINES
#include <math.h>
#include <stdio.h>
#include <vector>
#include <functional>
#include <map>
using namespace std;

int n,m;
int list[100][100];
int list2[100];
int main(){
	cin >> n >> m;

	for (int y = 0; y < n; ++y) {
		for (int x = 0; x < m; ++x) {
			cin >> list[y][x];
		}
	}

	for (int x = 0; x < m; ++x)
		cin >> list2[x];

	for (int y = 0; y < n; ++y) {
		int buf = 0;
		for (int x = 0; x < m; ++x) {
			buf += list[y][x] * list2[x];
		}
		cout << buf << endl;
	}

	return 0;
}

Measured memory_bytes: 1200
#include <stdio.h>
#define INF 2000000
#define MAX 101
int m[MAX][MAX],p[MAX],length;

void MatrixChainOrder(){
  int n = length,i,l,j,k,q;
  for (i=1;i<=n;i++) {
    m[i][i]=0;
  }
  for (l=2;l<=n;l++){
    for (i=1;i<=n-l+1;i++) {
      j = i+l-1;
      m[i][j]=INF;
      for (k=i;k<=j-1;k++){
        q = m[i][k]+m[k+1][j]+p[i-1]*p[k]*p[j];
        if (m[i][j]>q) {
          m[i][j]=q;
        }
      }
    }
  }
}

int main() {
  int i,j;
  scanf ("%d",&length);
  for (i=0;i<length;i++){
    scanf ("%d%d",&p[i],&j);
  }
  p[length]=j;
  MatrixChainOrder();
  printf ("%d\n",m[1][length]);
  return 0;
}

Measured memory_bytes: 636
N, M = map(int, input().split())
switch_li = [list(map(int, input().split())) for i in range(M)]
p_li = list(map(int, input().split()))

all_bit = []
for i in range(2**N):
  bit_li = [0] * N
  for j in range(N):
    if (i >> j) & 1:
      bit_li[j] = 1
  all_bit.append(bit_li)

count = 0
for i in all_bit:
  light_li = [0] * M
  for j in range(len(switch_li)):
    for k in range(N):
      if i[k] == 1:
        if k+1 in switch_li[j][1:]:
          light_li[j] += 1
  m_count = 0        
  for a,b in zip(light_li, p_li):
    if a % 2 == b % 2:
      m_count += 1
    if m_count == M:
      count += 1
      
print(count)
    

Measured memory_bytes: 3188
#include<iostream>
#include<vector>
#include<set>
#include<unordered_set>
#include<string>
#include<stack>
#include<algorithm>
#include<cmath>

using namespace std;

struct query{
    int l;
    int r;
    int i;
    int ans;
};
 
signed main() {
    int n, t;
    cin >> n >> t;
    vector<int> a(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }
    vector<query> q(t);
    for (int i = 0; i < t; ++i) {
        cin >> q[i].l >> q[i].r;
        q[i].i = i;
        q[i].l--;
        q[i].r--;
    }
 
    int sqrtn = sqrt(n) + 1;
    sort(q.begin(), q.end(), [&sqrtn](query &a, query &b) {
        if (a.l / sqrtn != b.l / sqrtn) {
            return a.l / sqrtn < b.l / sqrtn;
        }
        return a.r < b.r;
    });
 
    vector<int> m(n+1);
    int l = 0;
    int r = -1;
    int cnt = 0;
 
    for (auto &q : q) {
        if (r < q.l || q.r < l) {
            m.assign(n+1, 0);
            cnt = 0;
            l = q.l;
            r = q.l - 1;
        }
        while (r < q.r) {
            r++;
            if (m[a[r]] == 0) cnt++;
            m[a[r]]++;
        }
        while (r > q.r) {
            m[a[r]]--;
            if (m[a[r]] == 0) cnt--;
            r--;
        }
        while (l < q.l) {
            m[a[l]]--;
            if (m[a[l]] == 0) cnt--;
            l++;
        }
        while (l > q.l) {
            l--;
            if (m[a[l]] == 0) cnt++;
            m[a[l]]++;
        }
        q.ans = cnt;
    }
    sort(q.begin(), q.end(), [](query &a, query &b) {return a.i < b.i;});
 
    for (auto &q : q) {
        cout << q.ans << '\n';
    }
}

Measured memory_bytes: 15460
#include <stdio.h>

int cnt;

void insertionSort(int A[], int n, int g);
void shellSort(int A[], int n);

int n;
int A[1000000];

int main() {
  int i;
  scanf("%d", &n);
  for(i = 0; i < n; ++i) scanf("%d", A+i);
  shellSort(A, n);
  printf("%d\n", cnt);
  for(i = 0; i < n; ++i) printf("%d\n", A[i]);
  return 0;
}

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

void shellSort(int A[], int n) {
  int m = 0;
  int G[100];
  int i;
  G[0] = 1;
  for(m = 1; 3*G[m-1]+1 <= n; ++m) G[m] = 3*G[m-1]+1;
  printf("%d\n", m);
  cnt = 0;
  for(i = m-1; i >= 0; --i) {
    printf("%d%c", G[i], " \n"[i==0]);
    insertionSort(A, n, G[i]);
  }
}



Measured memory_bytes: 5608
#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 ALL(v) (v).begin(),(v).end()
#define fi first
#define se second

template<typename A, typename B> inline bool chmax(A &a, B b) { if (a<b) { a=b; return 1; } return 0; }
template<typename A, typename B> inline bool chmin(A &a, B b) { if (a>b) { a=b; return 1; } return 0; }

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<int, pll> pip;
const ll INF = 1ll<<60;
const ll MOD = 1000000007;
const double EPS  = 1e-9;

struct UnionFind {
	vector<int> par;
	vector<int> rank;
	
	UnionFind() {}
	UnionFind(int n) {
		init(n);
	}
	
	int operator[] (int x) {
		return find(x);
	}

	void init(int n) {
		par.resize(n);
		rank.resize(n);
		REP(i, n) {
			par[i] = i;
			rank[i] = 0;
		}
	}

	int find(int x) {
		if (par[x] == x) return x;
		return par[x] = find(par[x]);
	}

	void unite(int x, int y) {
		x = find(x);
		y = find(y);
		if (x == y) return;

		if (rank[x] < rank[y]) {
			par[x] = y;
		} else {
			par[y] = x;
			if (rank[x] == rank[y]) rank[x]++;
		}
	}

	bool same(int x, int y) {
		return find(x) == find(y);
	}
};

int main() {
	int N, K, L;
	cin >> N >> K >> L;
	
	UnionFind uf[2] = {UnionFind(N), UnionFind(N)};
	
	REP(i, K) {
		int q, k;
		scanf("%d %d", &q, &k);
		uf[0].unite(q - 1, k - 1);
	}
	
	REP(i, L) {
		int r, s;
		scanf("%d %d", &r, &s);
		uf[1].unite(r - 1, s - 1);
	}
	
	map<pii, int> m;
	REP(i, N) m[pii(uf[0][i], uf[1][i])]++;
	
	REP(i, N) printf("%d%c", m[pii(uf[0][i], uf[1][i])], i == N - 1 ? '\n' : ' ');
	
	return 0;
}


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

using namespace std;
#define repeat(i,n) for(int i=0;i<(n);i++)

int main(){
  int n;
  int a[100000],in,pre;
  cin>>n;
  cin>>in;
  pre=in;
  a[0]=0;
  for(int i=1; i<n; i++){
    cin>>in;
    if(in>pre){
      a[i]=a[i-1]+1;
    }
    else if(in<pre){
      a[i]=a[i-1]-1;
    }
    else{
      a[i]=a[i-1];
    }
    pre=in;
  }
  int fugou=1;
  int cnt=1,max_renzoku=-10000000;
  for(int i=1; i<n; i++){
    if((a[i]-a[i-1])*fugou>0){
      cnt++;
      max_renzoku=max(max_renzoku,cnt);
    }
    else if(a[i]!=a[i-1]){
      cnt=2;
      max_renzoku=max(max_renzoku,cnt);
      fugou*=(-1);
    }
  }
  cout<<max(max_renzoku,1)<<endl;


  return 0;
}

Measured memory_bytes: 3500
#include<iostream>
#include<vector>
#include<cstdio>
#include<string>
#include<algorithm>
#include<climits>
#include <numeric>
using namespace std;

int main() {
  int ans=0;
  int N;
  int all=0;
  int sum = 0;
  int tmp = 100000;

  cin >> N;
  vector<int> W(N);
  for(long i = 0; i < N; i++){
    cin >> W[i];
    all = all + W[i];
  }

  for(int i=0; i< N; i++){
    sum=sum+W[i];
    all=all-W[i];


    if (tmp < abs(all - sum)){
      break;
    }

    tmp = abs(all - sum);
  }

  cout << tmp << endl;
}


Measured memory_bytes: 256
r, c = map(int, input().split())

res = [0 for i in range(c)]
for i in range(r):
    li = [int(x) for x in list(input().split())]
    for j, k in enumerate(li):
        print("{} ".format(k), end="")
        res[j] += k
    print(sum(li), end="")
    print("")

for rr in res:
    print("{} ".format(rr), end="")
print(sum(res))




Measured memory_bytes: 5632
require 'set'

def main
    a,b,h,m = gets.chomp.split(" ").map(&:to_i)

    theta_m = m*360/60
    theta_h = (h+m*1.0/60)*360/12
    if (theta_h - theta_m).abs <= 180
        theta = (theta_h - theta_m).abs
    else
        theta = 360 - (theta_h - theta_m).abs
    end

    puts ( a**2 + b**2 - 2*a*b*Math.cos(theta*Math::PI/180) )**0.5
end

main

## イディオムなど
# until s.empty? do
#
## 配列のインデックス
# s[0,6] # 0番目から6文字
# s[0..6] # 0番目から6番目まで
# s[5..-1] # 5番目から最後まで
#
## 全探索
# [0, 1].repeated_permutation(n) do |combination| # 2^n の全探索
# array.combination(i) do |selected| # array から要素が i 個である部分列を全部抽出

Measured memory_bytes: 14980
#include <iostream>
#include <vector>
#include <utility>
#include <map>
using namespace std;

int N, W;
map<pair<int, int> , int> dp; //<i番目まで見たときの重さに対する価値の最大値>
vector<int> w(1, 0), v(1, 0);

int func(int, int);
int main(){
  cin >> N >> W;
  int wt, vt;
  for(int i=1; i<=N; i++) {
    cin >> wt >> vt;
    w.push_back(wt);
    v.push_back(vt);
  }

  int ans=func(N, W);

  cout << ans << endl;

  return 0;
}

int func(int i, int j){
  pair<int, int> tmp = make_pair(i, j);
  if(dp.find(tmp)==dp.end()){
    if(i==0 || j==0){
      return dp[tmp]=0;
    }
    else if(j<w[i]){
      return dp[tmp]=func(i-1, j);
    }
    else{
      return dp[tmp]=max(func(i-1, j), func(i-1, j-w[i])+v[i]);
    }
  }
  else{
    return dp[tmp];
  }
}


Measured memory_bytes: 6400
from fractions import gcd

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    divisors.sort()
    return divisors



N,M=map(int,input().split())
L=make_divisors(gcd(N, M))
ANS=[]
for i in L:
  FLG = True
  for j in L[1:]:
    if j > i:
      break
    if i != j and i % j == 0:
      FLG = False
      break
  if FLG:
    ANS.append(i)
      

print(len(ANS))


Measured memory_bytes: 5348
#include <iostream>
#include <cmath>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;
int main() {
	bool ans = false;
	int N,M,X,Y;
	cin >> N >> M >> X >> Y;
	vector<int>x(N);
	vector<int>y(M);
	for (int i = 0; i < N; i++)
		cin >> x[i];
	for (int i = 0; i < M; i++)
		cin >> y[i];

	sort(x.begin(), x.end());
	sort(y.begin(), y.end());

	for (int i = X+1; i <= Y; i++) {
		if (x[N - 1] < i&&y[0] >= i) {
			ans = true;
			break;
		}
	}
	if (ans)
		cout << "No War" << endl;
	else
		cout << "War" << endl;

	return 0;
}

Measured memory_bytes: 256
#二分探査かぁ…
from math import *
import fractions
import collections
import itertools
import pprint
from collections import deque
from heapq import *
N,K=map(int,input().split())
A=list(map(int,input().split()))
maxnum=10**9+20
minnum=1
def is_ok(arg):
    return arg<=K
def mgr_bisect(ng,ok):
    while (abs(ok-ng)>1):
        mid=(ok+ng)//2
        cnt=0
        for i in range(N):
            cnt=cnt+ceil(A[i]/mid)-1
        if is_ok(cnt):
            ok=mid
        else:
            ng=mid
    return ok
print(mgr_bisect(0,10**9+1))

Measured memory_bytes: 96660
#include<iostream>
#include<string>
#include<cctype>
using namespace std;

string shuffle(string str, int h){
  string head = str.substr(0, h);
  string tail = str.substr(h, str.size()-h);
  return tail + head;
}

int main(){
  string cards;
  int m, h;

  while(1){
    cin >> cards;
    if(cards == "-") break;
    
    cin >> m;
    for(int i = 0; i < m; i++){
      cin >> h;
      cards = shuffle(cards, h);
    }
  cout << cards << endl;
  }

  return 0;
}

Measured memory_bytes: 1216
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <string>
#include <cmath>
#include <vector>
#include <queue>
#include <climits>
#include <utility>
typedef long long ll;
using namespace std;

int main(void){
  int n,i,a;

  cin>>n;
  
  for(i=0;i<n;i++){
    cin>>a;

    if(a%2==0&&a%3!=0&&a%5!=0){
      cout<<"DENIED"<<endl;
      return 0;
    }
  }

  cout<<"APPROVED"<<endl;

  return 0;
}


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

int main() {
  string ans ="YES";
  int N,M,i;
  cin >> N;
  int D[N+1];
  for(i=0;i<N;i++) cin >> D[i];
  cin >> M;
  int T[M+1];
  for(i=0;i<M;i++) cin >> T[i];

  sort(D,D+N);
  sort(T,T+M);

  int j=0;
  
  while(j<M) {
	int count = upper_bound(T,T+M,T[j])-lower_bound(T,T+M,T[j]);
	if(count>upper_bound(D,D+N,T[j])-lower_bound(D,D+N,T[j])) ans = "NO";
	j = j+count;
	}
  cout << ans << endl;

  return 0;
}     

Measured memory_bytes: 1792
import java.math.BigInteger;
import java.util.Scanner;

public class Main {
	static long MOD = 1000000007;
	static BigInteger BMOD = new BigInteger(Long.toString(MOD));

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int k = sc.nextInt();
		int q = sc.nextInt();
		long[] d = new long[k];

		for ( int i = 0 ; i < k ; i++ ) {
			d[i] = sc.nextLong();
		}

		long[] n = new long[q];
		long[] x = new long[q];
		long[] m = new long[q];
		for ( int j = 0 ; j < q ; j++ ) {
			n[j] = sc.nextLong();
			x[j] = sc.nextLong();
			m[j] = sc.nextLong();
		}

		for ( int j = 0 ; j < q ; j++ ) {
			long[] pcnt = new long[k + 1];
			long[] psum = new long[k + 1];
			psum[0] = 0;
			pcnt[0] = 0;
			for ( int i = 0 ; i < k ; i++ ) {
				long dd = d[i] % m[j];
				psum[i + 1] = psum[i] + dd;
				if ( dd > 0 ) {
					pcnt[i + 1] = pcnt[i] + 1;
				} else {
					pcnt[i + 1] = pcnt[i];
				}
			}
			long goal = (x[j] % m[j]) + psum[k] * ((n[j] - 1) / k) + psum[(int)((n[j] - 1) % k)];

			System.out.println(pcnt[k] * ((n[j] - 1) / k) + pcnt[(int)((n[j] - 1) % k)] - goal / m[j] + (x[j] % m[j]) / m[j]);
		}
	}
}


Measured memory_bytes: 148552
using System;
class Program
{
    static void Main(string[] args)
    {
        string[] input = Console.ReadLine().Split(' ');

        int x = int.Parse(input[0]+input[1]);

        for(int i=1;i<=x;i++)
        {
            if((i*i)==x)
            {
                Console.WriteLine("Yes");
                return;
            }
        }
        Console.Write("No");
    }
}

Measured memory_bytes: 13140
#include <iostream>
#include <math.h>
#include <stdexcept>

using namespace std;
typedef long long ll;

#define N 1000000000000 + 5
ll n;

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

  cin >> n;

  ll ans = 1 + n/1;

  ll i = int(sqrt(n));
  for (; i>=2; i--) {
    if (n % i == 0) {
      ll j = n/i;
      if (i + j < ans) {
        ans = i + j;
      }
    }
  }

  cout << ans-2 << "\n";
  return 0;
}

Measured memory_bytes: 256
# -*- coding: utf-8 -*-
import sys
import math
from bisect import bisect_left
from bisect import bisect_right
from collections import defaultdict
from heapq import heappop, heappush
import itertools
import random
from collections import deque
from decimal import *
import queue
from functools import reduce

input = sys.stdin.readline

def inputInt(): return int(input())
def inputMap(): return map(int, input().split())
def inputList(): return list(map(int, input().split()))
def inputStr(): return input()[:-1]

inf = float('inf')
mod = 1000000007

#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-

def main():
	N = inputInt()
	L = inputList()

	L.sort()

	ans = 0
	for aa in range(N):
		a = L[aa]
		for bb in range(aa+1,N):
			b = L[bb]
			for cc in range(bb+1,N):
				c = L[cc]
				if a == b or a == c or b == c:
					continue
				if abs(a-b) < c and c < a+b:
					#print("{} {} {}".format(a,b,c))
					ans += 1
	print(ans)


#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
if __name__ == "__main__":
	main()


Measured memory_bytes: 78304
#include<bits/stdc++.h>
using namespace std;
int main()
{
    string s;
    bool v=true;
    cin>>s;
	for(int i=0;i<s.size();i+=2)
		if(s[i]=='L'||s[i+1]=='R')
			v=false;
	if(v==true)
		cout<<"Yes";
	else
		cout<<"No";
} 

Measured memory_bytes: 256
N,M=[int(i) for i in input().split()]
graph = [[] for _ in range(N+1)]
from collections import deque
aa = [0] * M
bb = [0] * M
ans = 0
for i in range(M):
    a,b = [int(j) for j in input().split()]
    graph[a].append(b)
    graph[b].append(a)
    aa[i] = a
    bb[i] = b
import copy
grapha = copy.deepcopy(graph)
for k in range(M):
    graph[aa[k]].remove(bb[k])
    graph[bb[k]].remove(aa[k])
    seen = [False] * (N+1)
    from collections import deque
    que = deque()
    que.append(1)
    while len(que) != 0:
        x = que.popleft()
        seen[x] = True
        for i in graph[x]:
            if seen[i]:
                continue
            que.append(i)
            seen[i] = True
    for l in range(1,N+1):
        if seen[l]:
            continue
        ans +=1
        break
    graph = copy.deepcopy(grapha)
print(ans)

Measured memory_bytes: 3444
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using P = pair<int, int>;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rep2(i, s, n) for (int i = (s); i < (int)(n); i++)
#define all(v) v.begin(), v.end()
#define sz(v) v.size()
#define INF 1000000009
// aよりもbが大きいならばaをbで更新する
// (更新されたならばtrueを返す)
template <typename T>
bool chmax(T &a, const T& b) {
  if (a < b) {
    a = b;  // aをbで更新
    return true;
  }
  return false;
}
// aよりもbが小さいならばaをbで更新する
// (更新されたならばtrueを返す)
template <typename T>
bool chmin(T &a, const T& b) {
  if (a > b) {
    a = b;  // aをbで更新
    return true;
  }
  return false;
}

int main(){
  ll H, W;
  cin >> H >> W;
  if(H == 1 || W == 1){
    cout << 1 << endl;
    return 0;
  }
  cout << (W / 2 * H) + (W % 2) * (H + 1) / 2 << endl;
}

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

#define rep(i,a,b)     for(int i=a;i<(b);i++)
#define lop(n)         for(int i=0;i<n;i++)
#define revlop(n)      for(int i=n-1;i>=0;i--)
#define trav(a,x)      for(auto &a :x)
#define all(x)         begin(x),end(x)
#define mod            1000000007
#define inf            1e18
#define ps(x,y)        fixed<<setprecision(y)<<x
#define w(x)           int x; cin>>x;

#define pb             push_back
#define mp             make_pair
#define lb             lower_bound
#define ub             upper_bound
#define bs             binary_search
#define F              first
#define S              second

typedef long long                ll;
typedef vector<int>              vi;
typedef pair<int, int>           pii;
typedef vector<pair<int, int>>   vpii;
typedef vector<pair<ll, ll>>     vpll;
ll a[200005];
ll pre[200005];
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);

#ifndef ONLINE_JUDGE
  freopen("input.txt", "r", stdin);
  freopen("output.txt", "w", stdout);
#endif

  ll n;
  cin >> n;

  rep(i, 0, n)
  {
    cin >> a[i];
  }
  sort(all(a), greater<int>());
  rep(i, 0, n)
  {
    if (!i)
      pre[i] = a[i];
    else
      pre[i] = (a[i] + pre[i - 1]) % mod;
  }
  ll ans = 0;
  rep(i, 1, n)
  {
    ans = (ans % mod + (pre[i - 1] * a[i]) % mod) % mod;
  }
  cout << ans;
  return 0;
}


Measured memory_bytes: 6768
using System;

namespace aoj4a
{
    class Program
    {
        static void Main(string[] args)
        {
            
            string[] num = Console.ReadLine().Split(' ');
            int a = int.Parse(num[0]);
            int b = int.Parse(num[1]);
            Console.WriteLine( a / b + " " + a % b + " " + ( (double)a / b ).ToString("F6"));
                
            

        }
    }
}

Measured memory_bytes: 9140
#include <iostream>
#include <string>
#include <vector>
#include <set>
#include <queue>
#include <stack>
#include <map>
#include <algorithm>
#include <math.h>
#include <cassert>
#define rep(i,n) for(int i = 0; i < n; ++i )
using namespace std;
using ll = long long;
using P = pair<int,int>;

const ll inf = 1e9;
int main() {
  int n;
  cin >> n;
  vector<ll> x(n),y(n),p(n);
  rep(i,n) cin >> x[i] >> y[i] >> p[i];
  vector<vector<int>> v(1<<n,vector<int>(n)),h(1<<n,vector<int>(n));
  rep(b,1<<n){
    vector<int> vi={-inf,0,inf},hi={-inf,0,inf};
    rep(i,n) if(b>>i&1) vi.push_back(x[i]), hi.push_back(y[i]);
    sort(vi.begin(),vi.end());
    sort(hi.begin(),hi.end());
    rep(i,n){
      if(b>>i&1) continue;
      int xi = lower_bound(vi.begin(),vi.end(),x[i])-vi.begin();
      int yi = lower_bound(hi.begin(),hi.end(),y[i])-hi.begin();
      v[b][i] = min(vi[xi]-x[i],x[i]-vi[xi-1]);
      h[b][i] = min(hi[yi]-y[i],y[i]-hi[yi-1]);
    }
  }

  int t = 1;
  rep(_,n) t *= 3;
  vector<ll> ans(n+1,1e18L);
  rep(b,t){
    int k=0;
    int x=0,y=0,bi=b;
    rep(i,n){
      int t = bi%3;
      if(t!=0) ++k;
      if(t==1) x |= 1<<i;
      if(t==2) y |= 1<<i;
      bi /= 3;
    }
    ll res = 0;
    rep(i,n) res += p[i] * min(v[x][i],h[y][i]);
    ans[k] = min(ans[k],res);
  }
  rep(k,n+1) cout << ans[k] << endl;
}


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

int main() {
  long W,H,x,y;
  cin>>W>>H>>x>>y;

  double val = (float)(W*H)/2.;
  int flag = (x*2 == W && y*2 == H)?1:0;
  cout<<val<<" "<<flag<<endl;
  return 0;
}

Measured memory_bytes: 256
# coding: utf-8
import re
import math
import itertools
from copy import deepcopy
import fractions
import random
from heapq import heappop,heappush
import time
import os
import sys
import datetime
from functools import lru_cache
readline=sys.stdin.readline
sys.setrecursionlimit(2000)
#import numpy as np
alphabet="abcdefghijklmnopqrstuvwxyz"
mod=int(10**9+7)
inf=int(10**20)
def yn(b):
    if b:
        print("yes")
    else:
        print("no")
def Yn(b):
    if b:
        print("Yes")
    else:
        print("No")
def YN(b):
    if b:
        print("YES")
    else:
        print("NO")
class union_find():
    def __init__(self,n):
        self.n=n
        self.P=[a for a in range(N)]
        self.rank=[0]*n
 
    def find(self,x):
        if(x!=self.P[x]):self.P[x]=self.find(self.P[x])
        return self.P[x]
 
    def same(self,x,y):
        return self.find(x)==self.find(y)
 
    def link(self,x,y):
        if self.rank[x]<self.rank[y]:
            self.P[x]=y
        elif self.rank[y]<self.rank[x]:
            self.P[y]=x
        else:
            self.P[x]=y
            self.rank[y]+=1
 
    def unite(self,x,y):
        self.link(self.find(x),self.find(y))
 
    def size(self):
        S=set()
        for a in range(self.n):
            S.add(self.find(a))
        return len(S)
def bin_(num,size):
    A=[0]*size
    for a in range(size):
        if (num>>(size-a-1))&1==1:
            A[a]=1
        else:
            A[a]=0
    return A
def fac_list(n,mod_=0):
    A=[1]*(n+1)
    for a in range(2,len(A)):
        A[a]=A[a-1]*a
        if(mod>0):A[a]%=mod_
    return A
def comb(n,r,mod,fac):
    if(n-r<0):return 0
    return (fac[n]*pow(fac[n-r],mod-2,mod)*pow(fac[r],mod-2,mod))%mod
def next_comb(num,size):
    x=num&(-num)
    y=num+x
    z=num&(~y)
    z//=x
    z=z>>1
    num=(y|z)
    if(num>=(1<<size)):return False
    else:
        return num
def get_primes(n,type="int"):
    A=[True]*(n+1)
    A[0]=False
    A[1]=False
    for a in range(2,n+1):
        if A[a]:
            for b in range(a*2,n+1,a):
                A[b]=False
    if(type=="bool"):return A
    B=[]
    for a in range(n+1):
        if(A[a]):B.append(a)
    return B
def is_prime(num):
    if(num<=2):return False
    i=2
    while i*i<=num:
       if(num%i==0):return False
       i+=1
    return True
def join(A,c=" "):
    n=len(A)
    A=list(map(str,A))
    s=""
    for a in range(n):
        s+=A[a]
        if(a<n-1):s+=c
    return s
#######################################################################################################
x=int(input())
ans=(x//500)*1000
x%=500
ans+=(x//5)*5
print(ans)



































































































































































































Measured memory_bytes: 6640
N,M=map(int,input().split())

def make_divisors(n):
    lower_divisors , upper_divisors = [], []
    i = 1
    while i*i <= n:
        if n % i == 0:
            lower_divisors.append(i)
            if i != n // i:
                upper_divisors.append(n//i)
        i += 1
    return lower_divisors + upper_divisors[::-1]
  
d = make_divisors(M)
d = list(filter(lambda x:x<=M/N,d))

print(d[-1])

Measured memory_bytes: 9136
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp> 
using namespace __gnu_pbds;
#define ordered_set tree<int, null_type,less_equal<int>, rb_tree_tag,tree_order_statistics_node_update>
using namespace std;
#define ll long long
#define pb push_back
#define F first
#define S second
#define all(c)  c.begin(), c.end()
#define llv vector< ll >
#define mp make_pair
#define endl "\n"
const int N = (int)1e5+10 ;
const int M = (int)1000000007;

int main(){
    // #ifndef ONLINE_JUDGE
    // freopen("input.txt", "r", stdin);
    // freopen("output.txt", "w", stdout);
    // #endif
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    
    ll n , i ;
    cin >> n ;
    ll h[n] ;
    for(i=0 ; i<n ; i++){
        cin >> h[i] ;
    }
    ll dp[n] ;
    dp[0]=0 ;
    dp[1]=abs(h[1]-h[0]) ;
    for(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] ;
    
    
    return 0 ;
}

Measured memory_bytes: 1792
n = int(input())

num2alpha = lambda c: chr(c+96)

ans = ""

while True:
    a = n % 26
     
    if n < 1:
        break
    
    
    if a == 0:
        a = 26

    n = int((n - a)  / 26)

    ans += num2alpha(int(a))
    
print(ans[::-1])




Measured memory_bytes: 9104
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for (int i=(a),_b=(b);i<=_b;i=i+1)
#define FORD(i,b,a) for (int i=(b),_a=(a);i>=_a;i=i-1)
#define REP(i,n) for (int i=0,_n=(n);i<_n;i=i+1)
#define FORE(i,v) for (__typeof((v).begin()) i=(v).begin();i!=(v).end();i++)
#define ALL(v) (v).begin(),(v).end()
#define pb push_back
#define mp make_pair
#define fi first
#define se second+++
#define SZ(x) ((int)(x).size())
#define double db
typedef long long ll;
typedef pair<int,int> PII;
const ll mod=1000000007;
ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
const int MAXN = 1E5+3;
const ll oo = 1e18+3;


int a, b;

int main() {
	cin >> a >> b;
	cout << ((a<9 && b<9)?"Yay!":":(");
	return 0;
}


Measured memory_bytes: 256
N,T = map(int, input().split())
AB = [tuple(map(int, input().split())) for _ in range(N)]
AB.sort()


"""
最後に食べる料理は時刻Tを超えても食べていてOKなので、時刻Tの時点で、食べるのに必要な時間が長くても得点の高いものを食べればよい
最後に食べるやつ x N-1品からi番目まで選べる時 x T-1分までのうちt分までに食べ終えて得られる最大のおいしさ
でDPをやると、O(N*N*T)で間に合わない

↑は最後に食べるものを軸に考えたDPだが、実際の所、その後ろの「N-1品～T-1までに食べ終えて得られる最大のおいしさ」を軸にしてみると、
この「」の後に食べる候補で全体の美味しさを最大化できるのは、残りの中で最も美味しいものである。
なので、最後に食べるもののループは実際は必要ない
これでO(N*T)程度になるので間に合う
ただし、食べる時間が速い順に並べおく必要がある。（先にT-1までに食べ終えておくものの中で、最後に食べるのより時間がかかるものがあるなら、入れ替えたほうがよいケースが出てくるので）
"""


dp = [[0 for _ in range(T)] for _ in range(N+1)]

for i in range(N):
    for j in range(T):
        if AB[i][0] > j:
            dp[i+1][j] = dp[i][j]
        else:
            dp[i+1][j] = max(dp[i][j], dp[i][j - AB[i][0]] + AB[i][1])

ans = 0

for i in range(N):
    tmp = 0
    if i < N-1:
        for j in range(i+1, N):
            tmp = max(tmp, AB[j][1])

    ans = max(ans, dp[i+1][-1] + tmp)


print(ans)

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


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

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


ll INF = 1LL<<60;

int main() {
  int N; ll W;
  cin >> N >> W;
  
  ll w[N];
  int v[N], mv = 0;
  rep(i,N) {cin >> w[i] >> v[i]; mv +=v[i];}
  
  ll dp[N+1][mv+1];
  rep(i,N+1)rep(j,mv+1) dp[i][j] = INF;
  
  dp[0][0] = 0;
  
  rep(i, N) {
    for (int value = 0; value <= mv; value++) {
      if(value - v[i] >= 0) {
        chmin(dp[i+1][value], dp[i][value - v[i]] + w[i]);
      }
      chmin(dp[i+1][value],dp[i][value]);
    }
  }
  
  ll ans;
  for (int vi = 0; vi <= mv; vi++) {
    if (dp[N][vi] <= W) ans = vi;
  }
  cout << ans << endl;
}


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

int main(){
    char s[1000];
    scanf("%s",s);
    int N;
    scanf("%d",&N);

    char command[10];
    for(int i=0;i<N;i++){
        scanf("%s",command);
        if(strcmp(command,"replace")==0){
            int a,b;
            char q[1000];
            scanf("%d %d %s",&a,&b,q);
            for(int f=a;f<=b;f++){
                s[f]=q[f-a];
            }
        }else if(strcmp(command,"reverse")==0){
            int a,b;
            char q[1000];
            scanf("%d %d",&a,&b);
            for(int f=b,g=0;a<=f;f--,g++){
                q[g]=s[f];
            }
            for(int f=a;f<=b;f++){
                s[f]=q[f-a];
            }
        }else if(strcmp(command,"print")==0){
            int a,b;
            char q[1000];
            scanf("%d %d",&a,&b);
            for(int f=a;f<=b;f++){
                printf("%c",s[f]);
            }
            printf("\n");
        }
    }
}


Measured memory_bytes: 2100
#include <bits/stdc++.h>
#define endl "\n"
using namespace std;
typedef long long ll;
typedef pair<ll, ll> l_l;
typedef pair<int, int> i_i;
template<class T>
inline bool chmax(T &a, T b) {
    if(a < b) {
        a = b;
        return true;
    }
    return false;
}

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

const long long INF = 1e18;
//const ll mod = 1000000007;

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    string S;
    cin >> S;
    cout << S.substr(0, 3) << endl;
    return 0;
}


Measured memory_bytes: 3640
#include<iostream>
#include<vector>
#include<algorithm>
#include<set>
#include<map>
#include<unordered_map>
#include<queue>
#include<iomanip>
#include<math.h>
#include<bitset>
#include<cassert>
#include<random>
#include<time.h>
using namespace std;
using ll=long long;
using ld=long double;
using P=pair<ll,ll>;
#define MOD 1000000007LL
#define INF 1000000000LL
#define EPS 1e-10
#define FOR(i,n,m) for(ll i=n;i<(ll)m;i++)
#define REP(i,n) FOR(i,0,n)
#define DUMP(a) REP(d,a.size()){cout<<a[d];if(d!=a.size()-1)cout<<" ";else cout<<endl;}
#define ALL(v) v.begin(),v.end()
#define UNIQUE(v)  sort(ALL(v));v.erase(unique(ALL(v)),v.end());
#define pb push_back

/* --------------------------------------- */

int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	ll n, x;
	cin >> n >> x;
	if(n == 2) {
		if(x == 2) {
			cout << "Yes" << endl;
			cout << 1 << " " << 2 << " " << 3 << endl;
		}
		else cout << "No" << endl;
		return 0;
	}
	if(x == 1 || x == 2 * n - 1) {
		cout << "No" << endl;
		return 0;
	}
	cout << "Yes" << endl;
	vector<ll> ans(2 * n - 1, -1);
		queue<ll> q;
	if(x != 2) {
		ans[n] = x - 1;
		ans[n - 1] = x;
		ans[n - 2] = 2 * n - 1;
		ans[n - 3] = x - 2;
		REP(i, 2 * n - 1) {
			ll num = i + 1;
			if(num != x && num != x - 1 && num != x - 2 && num != 2 * n - 1) {
				q.push(num);
			}
		}
	} else {
		ans[n] = x + 1;
		ans[n - 1] = x;
		ans[n - 2] = 1;
		ans[n - 3] = x + 2;
		REP(i, 2 * n - 1) {
			ll num = i + 1;
			if(num != x && num != x + 1 && num != x + 2 && num != 1) {
				q.push(num);
			}
		}
	}
	REP(i, 2 * n - 1) {
		if(ans[i] == -1) {
			ans[i] = q.front();
			q.pop();
		}
	}
	REP(i, 2 * n - 1) {
		cout << ans[i] << endl;
	}
	return 0;
}

/* --------------------------------------- */



Measured memory_bytes: 4736
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <map>
#include <set>
#include <functional>
#include <limits>
#include <queue>
#include <iomanip>
#include <deque>
#include <stack>
#include <cstdio>
#include <cmath>
#include <complex.h>
#include <cstdio>
#include <random>
#include <chrono>
#include <numeric>
#include <cassert>
#include <iso646.h>
#include <exception>
#include <stdexcept>

using namespace std;

typedef long long i64;

pair<i64, i64> facts[100100];

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

    int n;
    cin >> n;

    for (int i = 0; i < n; i++)
        cin >> facts[i].first >> facts[i].second;

    sort(facts, facts + n);

    i64 last_place = facts[n - 1].first;
    i64 last_score = facts[n - 1].second;

    cout << last_place + last_score;
}

Measured memory_bytes: 1792