akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rrep(i, n) for (int i = (int)(n - 1); i >= 0; i--)
#define all(x) (x).begin(), (x).end()
#define sz(x) int(x.size())
#define get_unique(x) x.erase(unique(all(x)), x.end());
#define fout cout << fixed << setprecision(20)
typedef long long ll;
typedef complex<double> Complex;
const int INF = 1e9;
const ll MOD = 1e9 + 7;
const ll LINF = 1e18;
template <class T>
bool chmax(T &a, const T &b) {
    if (a < b) {
        a = b;
        return 1;
    }
    return 0;
}
template <class T>
bool chmin(T &a, const T &b) {
    if (b < a) {
        a = b;
        return 1;
    }
    return 0;
}
template <class T>
vector<T> make_vec(size_t a) {
    return vector<T>(a);
}
template <class T, class... Ts>
auto make_vec(size_t a, Ts... ts) {
    return vector<decltype(make_vec<T>(ts...))>(a, make_vec<T>(ts...));
}

int main() {
    int k;
    cin >> k;
    queue<ll> q;
    for (int i = 1; i <= 9; i++) {
        q.push(i);
    }
    vector<ll> ans;
    while (sz(q)) {
        ll x = q.front();
        q.pop();
        ans.push_back(x);
        if (sz(to_string(x)) < 10) {
            q.push(10 * x + x % 10);
            if (x % 10 > 0) q.push(10 * x + x % 10 - 1);
            if (x % 10 < 9) q.push(10 * x + x % 10 + 1);
        }
    }
    sort(all(ans));
    cout << ans[k - 1] << endl;
}

Measured memory_bytes: 3444
#include<iostream>
#include<algorithm>
#include<queue>
#include<cstring>
#define k first
#define w second
using namespace std;
typedef pair<int,int> pii;
typedef long long ll;
const int N=200010;
pii a[N],b[N];
int main()
{
    int T;
    cin>>T;
    while(T--)
    {
        int n,cnta=0,cntb=0;
        cin>>n;
        ll res=0;
        for(int i=0;i<n;i++)
        {
            int k,l,r;
            cin>>k>>l>>r;
            if((k==0&&l>=r)||(k==n&&r>l)) 
            {
                res+=min(l,r);
                continue;
            }
            if(l>=r) res+=r,a[cnta++]={k,l-r};
            else res+=l,b[cntb++]={n-k,r-l};
        }
        sort(a,a+cnta),sort(b,b+cntb);
        priority_queue<int,vector<int>,greater<int> >heap;
        for(int i=0;i<cnta;i++)
        {
            heap.push(a[i].w);
            while(heap.size()>a[i].k) heap.pop();
        }
        while(heap.size())
        {
            res+=heap.top();
            heap.pop();
        }
        for(int i=0;i<cntb;i++)
        {
            heap.push(b[i].w);
            while(heap.size()>b[i].k) heap.pop();
        }
        while(heap.size())
        {
            res+=heap.top();
            heap.pop();
        }
        cout<<res<<endl;
    }
    return 0;
}

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

int a[204800], n;
int l[204800], r[204800];
vector<int> q;
int main() {
	scanf("%d", &n);
	for(int i = 1; i <=n ;++ i) scanf("%d", a + i);
	a[0] = a[n + 1] = -1;
	q.push_back(0);
	for(int i = 1; i <=n; ++i) {
		for(;q.size() && a[q.back()] > a[i];) q.pop_back();
		l[i] = q.back();
		q.push_back(i);
	}
	q.clear();
	q.push_back(n + 1);
	for(int i = n; i >=1; --i) {
		for(;q.size() && a[q.back()] > a[i];) q.pop_back();
		r[i] = q.back();
		q.push_back(i);
	}
	int64_t res = 0;
	for(int i = 1; i <=n; ++i) {
		int x = i - l[i], y = r[i] - i;
		res += x * (int64_t) y * a[i];
	}
	cout << res << endl;
}

Measured memory_bytes: 3448
input_lines = readlines.map(&:chomp)
K = input_lines.shift.to_i
A, B = input_lines.shift.split(' ').map(&:to_i)

judge = (A..B).each_with_object(false) do |num, result|
  if num % K == 0
    break true
  end
end

result = judge ? "OK" : "NG"

puts result

Measured memory_bytes: 14324
def main():
    s=input()
    n=len(s)
    res = []
    if s[0]=="0" or s[-1] == "1":
        print(-1)
        return 1
    m=n//2
    t=m
    for i in range(m,0,-1):
        if s[i-1] != s[n-i-1]:
            print(-1)
            return 1
        if i == m:
            if s[i-1]=="1":
                res.append([m,m+1])
                for j in range(m+2,n+1):
                    res.append([m+1,j])
            else:
                for j in range(m+1,n+1):
                    res.append([m,j])
        else:
            if s[i-1]=="1":
                res.append([t,i])
                t=i
            else:
                res.append([t,i])
    for sres in res:
        print(" ".join(map(str, sres)))


main()

Measured memory_bytes: 54800
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(10000)


def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, X):
    if X == 1 or X == 2*N-1:
        print('No')
        return

    a = list(range(1, 2*N))
    if N == 2:
        if a.index(X) != 1:
            print('No')
            return

    else:
        ci = 2*N//2 - 1
        xi = a.index(X)
        a[xi], a[ci] = a[ci], a[xi]

        if X != 2*N-2:
            xm1i = a.index(X-1)
            a[xm1i], a[ci-1] = a[ci-1], a[xm1i]

            xp1i = a.index(X+1)
            a[xp1i], a[ci-2] = a[ci-2], a[xp1i]

            xp2i = a.index(X+2)
            a[xp2i], a[ci+1] = a[ci+1], a[xp2i]
        else:
            xm1i = a.index(X+1)
            a[xm1i], a[ci-1] = a[ci-1], a[xm1i]

            xp1i = a.index(X-1)
            a[xp1i], a[ci-2] = a[ci-2], a[xp1i]

            xp2i = a.index(X-2)
            a[xp2i], a[ci+1] = a[ci+1], a[xp2i]

    print('Yes')
    for v in a:
        print(v)


def main():
    N, X = read_int_n()
    slv(N, X)


if __name__ == '__main__':
    main()


Measured memory_bytes: 70232
import java.util.*;

public class Main {
	Scanner sc = new Scanner(System.in);

	public static void main(String[] args) {
		new Main();
	}

	public Main() {
		new aoj0072().doIt();
	}

	class aoj0072 {
		int cost[][];
		int mincost[];
		boolean used[];
		int V;

		int prim() {
			for (int i = 0; i < V; i++) {
				mincost[i] = Integer.MAX_VALUE;
				used[i] = false;
			}
			mincost[0] = 0;
			int res = 0;
			while (true) {
				int v = -1;
				for (int u = 0; u < V; u++) {
					if (!used[u] && (v == -1 || mincost[u] < mincost[v]))
						v = u;
				}
				if (v == -1)
					break;
				used[v] = true;
				res += mincost[v];

				for (int u = 0; u < V; u++) {
					mincost[u] = Math.min(mincost[u], cost[v][u]);
				}
			}
			return res;
		}

		void doIt() {
			while (true) {
				V = sc.nextInt();
				if (V == 0)
					break;
				cost = new int[V][V];
				mincost = new int[V];
				used = new boolean[V];
				for (int i = 0; i < V; i++) {
					for (int j = 0; j < V; j++) {
						cost[i][j] = Integer.MAX_VALUE;
					}
				}
				int n = sc.nextInt();
				for (int i = 0; i < n; i++) {
					String[] node = sc.next().split(",");
					int nodea = Integer.valueOf(node[0]);
					int nodeb = Integer.parseInt(node[1]);
					int abcost = Integer.parseInt(node[2]);
					cost[nodea][nodeb] = abcost;
					cost[nodeb][nodea] = abcost;
				}
				int ans = prim();
				ans = (ans / 100) - V + 1;
				System.out.println(ans);
			}
		}
	}
}

Measured memory_bytes: 33048
#include<bits/stdc++.h>
using namespace std;
#define inf INT_MAX
#define INF LLONG_MAX
#define ll long long
#define ull unsigned long long
#define M (int)(1e9+7)
#define P pair<int,int>
#define FOR(i,m,n) for(int i=(int)m;i<(int)n;i++)
#define RFOR(i,m,n) for(int i=(int)m;i>=(int)n;i--)
#define rep(i,n) FOR(i,0,n)
#define rrep(i,n) RFOR(i,n,0)
#define all(a) a.begin(),a.end()
const int vx[4] = {0,1,0,-1};
const int vy[4] = {1,0,-1,0};
#define F first
#define S second
#define PB push_back
#define EB emplace_back
#define int ll
#define vi vector<int>
#define IP pair<int,P>
#define PI pair<P,int>
#define PP pair<P,P>
#define Yes(f){cout<<(f?"Yes":"No")<<endl;}
#define YES(f){cout<<(f?"YES":"NO")<<endl;}
int Madd(int x,int y) {return (x+y)%M;}
int Msub(int x,int y) {return (x-y+M)%M;}
int Mmul(int x,int y) {return (x*y)%M;}


signed main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  cout<<fixed<<setprecision(20);

  int s;
  cin>>s;
  set<int> set;
  int cnt=0;
  
  do{
    set.insert(s);
    if(s%2) s=3*s+1;
    else s=s/2;
    cnt++;
  }while(set.find(s)==set.end());

  cout<<cnt+1<<endl;
    


}

Measured memory_bytes: 256
fun main(args: Array<String>) {
    val (n, k) = readLine()!!.split(" ").map { it.toInt() }

    // n, k は max 10^5
    val pV = 1.0 / n

    var pWin = 0.0
    for ( i in 1 until n + 1){
        pWin += probWin(i, k)
    }

    print(pV * pWin)
}

fun probWin(start: Int, boundary: Int): Double {
    // 2 を最低何回かけるかを求め て　確率を出す
    // 10^5 < 2^17 で すぐに計算が終わるので工夫する必要もない

    var minSeq = boundary / start.toDouble()

    var i = 0
    while(minSeq > 1.0) {
        minSeq /= 2.0
        i += 1
    }

    return Math.pow(0.5, i.toDouble())
}

Measured memory_bytes: 37816
#include <algorithm>
#include <cctype>
#include <climits>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <functional>
#include <iostream>
#include <list>
#include <map>
#include <memory>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <utility>
#include <vector>
using namespace std;

#define EPS 1e-10
#define INF 1000000000
#define mp make_pair
#define pb push_back

typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int,int> pii;
typedef long long ll;

int main() {
  int N, K;
  cin >> N >> K;
  int ans = 1;
  for (int i = 0; i < N; i++) {
    ans = min(ans*2, ans+K);
  }
  cout << ans << endl;
}

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

int main(void) {
  int N;
  cin >> N;
  vector<int> A(N);
  vector<int> B(N);
  for (int i = 0; i < N; i++) {
    cin >> A.at(i);
    B.at(i) = A.at(i);
  }
  sort(B.begin(), B.end());
  for (int i = 0; i < N; i++) {
    if (B.at(N-1) == A.at(i)) {
      cout << B.at(N-2) << endl;
    } else {
      cout << B.at(N-1) << endl;
    }
  }
}

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

int main(){
  int N,A,B;
  cin>>N>>A>>B;
  int a[3];
  a[0]=0;
  a[1]=0;
  a[2]=0;
  for(int i=0;i<N;i++){
    int p;
    cin>>p;
    if(p<=A) a[0]++;
    else if(p>B) a[2]++;
    else a[1]++;
  }
  int ans=a[0];
  ans = min(a[2],min(ans,a[1]));
  cout << ans << endl;
}

Measured memory_bytes: 256
while True:
    n=input()
    if n==0:break
    A=map(int,raw_input().split())
    A.sort()
    cnt=0
    pre=A[0]
    for c in A:
        if c==pre:
            cnt+=1
            if cnt>n/2:
                print c
                break
        else:
            cnt=1
            pre=c
    else:
        print "NO COLOR"

Measured memory_bytes: 103720
#include <stdio.h>
#include <array>

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

using lli = long long int;
constexpr lli inf = 2e18;
constexpr int N = 2e5;
std::array<int, N> A;
std::array<lli, N+1> S;

lli score(lli a, lli b, lli c, lli d){
    lli mx = -1, mn = inf;
    if(a < mn) mn = a; if(a > mx) mx = a;
    if(b < mn) mn = b; if(b > mx) mx = b;
    if(c < mn) mn = c; if(c > mx) mx = c;
    if(d < mn) mn = d; if(d > mx) mx = d;
    return mx - mn;
}
   
int main(void){
    int n; scanf("%d", &n);
    S[0] = 0;
    REP(i, n){
        scanf("%d", &A[i]);
        S[i+1] = S[i] + A[i];
    }
    lli score_ = inf;
    for(int x = 2; x + 1 <= n; ++x){
        int l = 0, r = x;
        while(r - l > 1){
            int mid = (l + r) / 2;
            lli P = S[mid];
            lli Q = S[x] - S[mid];
            if(P <= Q) l = mid;
            else r = mid;
        }
        lli P, Q;
        if(S[x] - 2 * S[l] < 2 * S[r] - S[x]) P = S[l], Q = S[x] - S[l];
        else P = S[r], Q = S[x] - S[r];
        l = x, r = n;
        while(r - l > 1){
            int mid = (l + r) / 2;
            lli R = S[mid] - S[x];
            lli S_ = S[n] - S[mid];
            if(R <= S_) l = mid;
            else r = mid;
        }
        lli R, S_;
        if(S[n] + S[x] - 2 * S[l] < 2 * S[r] - S[n] - S[x]) R = S[l] - S[x], S_ = S[n] - S[l];
        else R = S[r] - S[x], S_ = S[n] - S[r];
        lli scr = score(P, Q, R, S_);
        if(score_ > scr) score_ = scr;
    }
    printf("%lld\n", score_);
    return 0;
}

Measured memory_bytes: 2560
#include<bits/stdc++.h>
using namespace std;
int main() {
  int n,a,i;
  cin>>n;
  map<int,int> m;
  for(i=1;i<=n;i++){
    cin>>a;
    m[a]=i;
  }
  i=0;
  for(auto p:m){
    i++;
    if(i>1) cout<<' ';
    cout<<p.second;
  }
}

Measured memory_bytes: 5504
from heapq import heappush, heappop
N, K, *L = map(int, open(0).read().split())
ls = []
for t,d in zip(*[iter(L)]*2):
  ls += [(d,t)]
used = []
cnt = {}
hq = []
S = set()
ls.sort(reverse=True)
m = 0
for i in range(K):
  d,t = ls[i]
  cnt[t] = cnt.get(t,0)+1
  m += d
  if cnt[t]>1:
    heappush(used,(d,t))
  S.add(t)
m += len(S)**2
for i in range(K,N):
  d,t = ls[i]
  if t not in S:
    heappush(hq,(-d,t))
ans = m
while used:
  d,t = heappop(used)
  while hq:
    if hq[0][1] not in S:
      break
    heappop(hq)
  else:
    break
  m -= d
  n,s = heappop(hq)
  m += -n+2*len(S)+1
  ans = max(ans,m)
  S.add(s)
print(ans)

Measured memory_bytes: 32140
// Problem : B - Golden Coins
// Contest : AtCoder Beginner Contest 160
// URL : https://atcoder.jp/contests/abc160/tasks/abc160_b
// Memory Limit : 1024 MB
// Time Limit : 2000 ms
// Powered by CP Editor (https://github.com/cpeditor/cpeditor)

//QWsin
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define rep(i,x,y) for(int i=x;i<=y;++i)
#define out(i,u) for(int i=first[u];i!=-1;i=nxt[i])
#define repvc(i,vc) for(int i=0,Sz=vc.size();i<Sz;++i)
using namespace std;
inline int read()
{
	char ch=getchar();int ret=0,f=1;
	while(ch<'0' || ch>'9') {if(ch=='-')f=-1;ch=getchar();}
	for(;ch>='0' && ch<='9';ch=getchar()) ret=ret*10+ch-'0';
	return ret*f;
}

typedef long long ll;
const int INF=1<<30;

int main()
{
	int x;cin>>x;
	long long ans=(x/500)*1000;
	ans+=x%500/5*5;
	cout<<ans<<endl;
	return 0;
}


Measured memory_bytes: 256
#include <iostream>
using namespace std;
int main(){
  int a,i=0,b;
  while(1){
    i=0;
    cin>>a;
    if(a==0)break;
    b=1000-a;
      i=b/500;
      b=b%500;
      i+=b/100;
      b=b%100;
      i+=b/50;
      b=b%50;
      i+=b/10;
      b=b%10;
      i+=b/5;
      b=b%5;
      i+=b/1;
    cout<<i<<endl;
  }
  return 0;
}

Measured memory_bytes: 1160
import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner scan = new Scanner(System.in);
        long N = scan.nextLong();
        long ans=1;
        long two = 2;
        if(N%2==1){
            N-=1;
        }
        while(true){
            if(N/two==0){
                break;
            }else{
                ans*=2;
                ans++;
                two*=2;
            }
        }
        System.out.println(ans);
    }
}


Measured memory_bytes: 21844
package main

import "fmt"

func main() {
	var s string
	fmt.Scan(&s)
	n := len(s)
	if s[n-1] == '3' {
		fmt.Println("bon")
	} else if s[n-1] == '0' || s[n-1] == '1' || s[n-1] == '6' || s[n-1] == '8' {
		fmt.Println("pon")
	} else {
		fmt.Println("hon")
	}
}


Measured memory_bytes: 1768
n = int(input())
a = list(map(int, input().split()))
total = 0
for i in range(n):
  cnt = 0
  while True:
    if a[i] % 2 == 0:
      cnt += 1
      a[i] = a[i] // 2
    else:
      break
  total += cnt
print(total)

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

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

    for (int i = 1; i < 1010; i++) {
        if ((int)(i * 0.08) == A && (int)(i * 0.1) == B) {
            cout << i << endl;
            return 0;
        }
    }
    cout << -1 << endl;
    return 0;
}

Measured memory_bytes: 256
#include "bits/stdc++.h"
#define in std::cin
#define out std::cout
#define rep(i,N) for(LL i=0;i<N;++i)
typedef long long int LL;

int main()
{
	LL N;
	in >> N;
	std::vector<LL>V(N), C(N);
	rep(i, N) in >> V[i];
	rep(i, N) in >> C[i];

	LL ans = 0;
	rep(bit, (1LL << N))
	{
		LL X = 0, Y = 0;
		rep(i, N)
		{
			if (bit & (1LL << i))
			{
				X += V[i];
				Y += C[i];
			}
		}
		ans = std::max(ans, X - Y);
	}
	out << ans << std::endl;
}


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

using namespace std;

typedef long long ll;

mt19937 rnd(chrono::high_resolution_clock::now().time_since_epoch().count());

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  int n, m;
  cin >> n >> m;
  vector <char> s(n, 'a');
  for (int i = 0; i < m; i++) {
    int p;
    cin >> p;
    p--;
    char c;
    cin >> c;
    if (s[p] == 'a') {
      s[p] = c;
    } else {
      if (s[p] != c) {
        cout << -1 << endl;
        return 0;
      }
    }
    if (n > 1 && p == 0 && c == '0') {
      cout << -1 << endl;
      return 0;
    }
  }
  if (n > 1 && s[0] == 'a') s[0] = '1';
  for (int i = 0; i < n; i++) {
    if (s[i] == 'a') s[i] = '0';
    cout << s[i];
  }
  cout << endl;
  return 0;
}

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

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	string s;
	cin>>s;
	if(s.find('7')!=-1) cout<<"Yes\n";
	else cout<<"No\n";
	return 0;
}

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

#define pb push_back
#define mp make_pair
#define ll long long
#define ull unsigned ll
#define db double
#define INF 0x3f3f3f3f
#define MOD 1000000007
#define PII pair<int, int>
 
using namespace std;

const int N=100010;
int n;
ll a,b;
ll h[N];

bool ok(int k) {
    ll rem=k;
    ll aa=a-b;
    for (int i=0;i<n;i++) {
        ll tmp=h[i]-b*k;
        if (tmp>0) {
            ll cost=tmp/aa;//printf("i:%d cost:%lld\n",i,cost);
            if (tmp%aa!=0) cost++;
            if (rem<cost) return false;
            rem-=cost;
        }//printf("i:%d rem:%lld\n",i,rem);
    }//printf("",rem);
    return true;
}

int main()
{
    scanf("%d%lld%lld",&n,&a,&b);
    for (int i=0;i<n;i++) {
        scanf("%lld",h+i);
    }
    int lo=0,hi=1e9;
    while (lo<hi) {
        int mid=(lo+hi)/2;
        if (!ok(mid)) {
            lo=mid+1;
        } else {
            hi=mid;
        }
    }
    printf("%d\n",lo);
}

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

int main() {
  ll n, k;
  cin >> n >> k;
  vector<pair<ll, ll>> ab;
  for (int i = 0; i < n; i++) {
    ll a, b;
    cin >> a >> b;
    ab.push_back(make_pair(a, b));
  }
  sort(ab.begin(), ab.end());

  ll r   = 0;
  ll ans = 0;
  ll i   = 0;
  while (r < k) {
    r += ab[i].second;
    ans = ab[i].first;
    i++;
  }
  cout << ans << endl;
}

Measured memory_bytes: 2420
open Printf
open Scanf

let id x = x

let solve n =
  let ht = Hashtbl.create n in
  let rec loop x =
    if x = 0 then ()
    else begin
        (let s = scanf "%s " id in
        try
          let v = Hashtbl.find ht s
          in Hashtbl.replace ht s (v + 1)
        with
          Not_found -> Hashtbl.add ht s 1);
        loop (x - 1)
      end in
  loop n;
  List.sort compare @@
    snd @@
      Hashtbl.fold (fun k v (ct, ls) ->
                    if v > ct then (v, [k])
                    else if v = ct then (ct, k::ls)
                    else (ct, ls)) ht (0, [])
    
let () =
  scanf "%d " solve |> List.iter @@ printf "%s\n"


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

int main(){
  int N,D,X,k,count=0;
  cin >> N >> D >> X;
  vector<int> a(N);
  for(int i=0;i<N;i++)cin >> a.at(i);
  for(int i=0;i<N;i++){
    k=1;
    while(k<=D){
      k+=a.at(i);
      count++;
    }
  }
  cout << X+count << endl;
  return 0;
}


Measured memory_bytes: 256
package main

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

var sc = bufio.NewScanner(os.Stdin)

func nextInt() int {
	sc.Scan()
	i, e := strconv.Atoi(sc.Text())
	if e != nil {
		panic(e)
	}
	return i
}

func nextText() string {
	sc.Scan()
	return sc.Text()
}

func main() {
	sc.Split(bufio.ScanWords)
  h := nextInt()
  w := nextInt()
  a := h * w
  if h == 1 || w == 1 {
    fmt.Println(1)
    return
  }
  if a % 2 == 0 {
    fmt.Println(a/2)
  } else {
    fmt.Println(a/2+1)
  }
}


Measured memory_bytes: 640
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <vector>
#include <set>
#include <cmath>
#define rep(i,n) for (int i = 0; i < n; ++i)
using namespace std;
using ll = long long;
using P = pair<int,int>;

int main() {
  int A, B;
  cin >> A >> B;
  if (max(100 * A, 80 * B) < min(80 * (B+1), 100 * (A+1))) cout << max(int(12.5 * A + 0.5), 10 * B) << endl;
  else cout << -1 << endl;
  return 0;
}

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

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

int main(void) {
    int n, ans = 1;

    cin.tie(0);
    ios::sync_with_stdio(false);
    cin >> n;
    
    vector<int> h(n);
    REP(i, n) {
        cin >> h[i];
    }

    int max_h = h[0];
    FOR(i, 1, n) {
        if (max_h <= h[i]) {
            max_h = h[i];
            ans++;
        }
    }

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

Measured memory_bytes: 256
# abc170_c.py
# https://atcoder.jp/contests/abc170/tasks/abc170_c

# C - Forbidden List /
# 実行時間制限: 2 sec / メモリ制限: 1024 MB
# 配点 : 300点

# 問題文
# 整数 Xと、長さ N の整数列 p1,…,pNが与えられます。
# 整数列 p1,…,pNに含まれない整数 (正とは限らない) のうち X に最も近いもの、
# つまり Xとの差の絶対値が最小のものを求めてください。そのような整数が複数存在する場合は、そのうち最も小さいものを答えてください。

# 制約
#     1≤X≤100
#     0≤N≤100
#     1≤pi≤100
#     p1,…,pNはすべて異なる。
#     入力中のすべての値は整数である。

# 入力
# 入力は以下の形式で標準入力から与えられる。
# X N
# p1 ... pN

# 出力
# 答えを出力せよ。

# 入力例 1
# 6 5
# 4 7 10 6 5

# 出力例 1
# 8

# 整数列 4,7,10,6,5に含まれない整数のうち、最も 6 に近いものは 8です。

# 入力例 2
# 10 5
# 4 7 10 6 5

# 出力例 2
# 9

# 整数列 4,7,10,6,5に含まれない整数のうち、最も 10 に近いものは 9 と 11 です。このうち小さい方である 9を出力します。

# 入力例 3
# 100 0

# 出力例 3
# 100

# N=0の場合、入力の 2 行目は空行となります。また、この場合のように、X 自身も答えとなりえます。


global FLAG_LOG
FLAG_LOG = False


def log(value):
    # FLAG_LOG = True
    FLAG_LOG = False
    if FLAG_LOG:
        print(str(value))


def calculation(lines):
    # S = lines[0]
    # N = int(lines[0])
    X, N = list(map(int, lines[0].split()))
    if N == 0:
        return [X]
    else:
        values = list(map(int, lines[1].split()))
    # values = list(map(int, lines[2].split()))
    # values = list()
    # for i in range(N):
    #     values.append(int(lines[i]))
    # valueses = list()
    # for i in range(N):
    #     valueses.append(list(map(int, lines[i+1].split())))

    mi = min(values)
    ma = max(values)

    distance = None
    # for i in [8]:
    for i in range(mi-1, ma+2):
        if i not in values:
            tmp = abs(X-i)
            if distance is None:
                result = i
                distance = tmp
            elif distance > tmp:
                result = i
                distance = tmp

    return [result]


# 引数を取得
def get_input_lines(lines_count):
    lines = list()
    for _ in range(lines_count):
        lines.append(input())
    return lines


# テストデータ
def get_testdata(pattern):
    if pattern == 1:
        lines_input = ['6 5', '4 7 10 6 5']
        lines_export = [8]
    if pattern == 2:
        lines_input = ['10 5', ' 4 7 10 6 5']
        lines_export = [9]
    if pattern == 3:
        lines_input = ['100 0', '']
        lines_export = [100]
    return lines_input, lines_export


# 動作モード判別
def get_mode():
    import sys
    args = sys.argv
    global FLAG_LOG
    if len(args) == 1:
        mode = 0
        FLAG_LOG = False
    else:
        mode = int(args[1])
        FLAG_LOG = True
    return mode


# 主処理
def main():
    import time
    started = time.time()
    mode = get_mode()
    if mode == 0:
        lines_input = get_input_lines(2)
    else:
        lines_input, lines_export = get_testdata(mode)

    lines_result = calculation(lines_input)

    for line_result in lines_result:
        print(line_result)

    # if mode > 0:
    #     print(f'lines_input=[{lines_input}]')
    #     print(f'lines_export=[{lines_export}]')
    #     print(f'lines_result=[{lines_result}]')
    #     if lines_result == lines_export:
    #         print('OK')
    #     else:
    #         print('NG')
    # finished = time.time()
    # duration = finished - started
    # print(f'duration=[{duration}]')


# 起動処理
if __name__ == '__main__':
    main()


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

#define dforsn(i,s,n) for(int i=int(n-1);i>=int(s);i--)
#define forsn(i,s,n) for(int i=int(s);i<int(n);i++)
#define dforn(i,n) for(int i=int(n-1);i>=0;i--)
#define forn(i,n) for(int i=0;i<int(n);i++)
#define D(a) cerr << #a << " = " << a << endl
#define all(a) a.begin(),a.end()
#define si(a) int((a).size())
typedef pair<int,int> pii;
typedef long long int ll;
typedef vector<int> vi;
#define pb emplace_back
#define mp make_pair
#define snd second
#define fst first

const int M = 1e9+7, F = 4e5;
int add(int a, int b){ return a+b < M ? a+b : a+b-M; }
int sub(int a, int b){ return a-b >= 0 ? a-b : a-b+M; }
int mul(int a, int b){ return int(ll(a)*b % M); }
ll pot(ll b, ll e){ // O(log e)
	if(!e) return 1;
	ll q = pot(b, e/2); q = mul(q, q);
	return (e & 1 ? mul(b, q) : q);
}
int inv(int x){ return pot(x, M-2); }
int divide(int a, int b) { return mul(a, inv(b)); }
int fact[F+1];
int choose(int n, int c){
    return divide(fact[n], mul(fact[n-c], fact[c]));
}
int k_tuples_of_non_neg_int_whose_sum_is_n(int k, int n){ 
    return choose(n+k-1, n); 
}
int k_tuples_of_pos_int_whose_sum_is_n(int k, int n){ 
    return choose(n-1, k-1); 
}

int main() {
    ios_base::sync_with_stdio(0), cin.tie(0);
    
    fact[0] = 1;
    forsn(i,1,F+1) fact[i] = mul(i, fact[i-1]);

    int n,k; cin >> n >> k;
    int r = k_tuples_of_non_neg_int_whose_sum_is_n(n,n);
    if(k < n) forsn(i,1,n-k){
        int x = k_tuples_of_pos_int_whose_sum_is_n(i,n);
        r = sub(r, mul(x, choose(n,i)));
    }
    cout << r << endl;
    return 0;
}


Measured memory_bytes: 1792
from collections import deque
N = int(input())
T = deque(list(input()))
W = deque([])
R = deque([])
i = 1
while T:
  x = T.popleft()
  if x=="W":
    W.append(i)
  else:
    R.append(i)
  i += 1
len_w = len(W)
len_r = len(R)
if len_w==0 or len_r==0:
    print(0)
    exit()
else:
    c = 0
    while R[-1]>W[0]:
        x = W.popleft()
        y = R.pop()
        W.append(y)
        R.appendleft(x)
        c += 1
    print(min(c,len_w,len_r))

Measured memory_bytes: 17224
#include <bits/stdc++.h>
#define FOR(i, n) for (int i = 0; i < n; i++) 

using namespace std;

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

int main() {
  char s[200];
  scanf("%s", s);
  int n = strlen(s);
  int res = 0;
  FOR(i, (n/2)) {
    if (s[i] != s[n-i-1]) res++;
  }
  printf("%d\n", res);

  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
 
using namespace std;
using ll = long long;
 
#define rep(i, a) for (int i = 0; (i) < (int) (a); (i)++)
#define reps(i, a, b) for (int i = (int) (a); (i) < (int) (b); (i)++)
#define rrep(i, a) for (int i = (int) a-1; (i) >= 0; (i)--)
#define rreps(i, a, b) for (int i = (int) (a)-1; (i) >= (int) (b); (i)--)
#define MP(a, b) make_pair((a), (b))
#define PB(a) push_back((a))
#define all(v) (v).begin(), (v).end()
#define PERM(v) next_permutation(all(v))
#define UNIQUE(v) sort(all(v));(v).erase(unique(all(v)), v.end())
#define CIN(type, x) type x;cin >> x
#define TRUE__  "Yes"
#define FALSE__ "No"
#define PRINT(f) if((f)){cout << (TRUE__) << endl;}else{cout << FALSE__ << endl;}
#define RS resize
#define CINV(v, N) do {\
	v.RS(N);\
	rep(i, N) cin >> v[i];\
} while (0);
#define RCINV(v, N) do {\
	v.RS(N);\
	rrep(i, N) cin >> v[i];\
} while (0);
 
#define MOD 1000000007
bool init();
int solve();

signed main()
{
    while (init()) {
    	cout << solve() << endl;
	}
}

int N;
vector<int> w;

bool init()
{
	cin >> N;
	if (N == 0) return false;
	w.RS(N);
	rep(i, N) cin >> w[i];
	return true;
}


int solve()
{
	vector<vector<int> > dp;
	dp.RS(N, vector<int>(N, 0));
	rep(i, N) rep(j, N) dp[i][j] = abs(j - i) + 1;
	for (int i = 0; i + 1 < N; i++) {
		if (abs(w[i] - w[i+1]) <= 1) dp[i][i+1] = 0;
	}

	for (int l = 3; l <= N; l++) {
		for (int i = 0; i + l - 1 < N; i++) {
			int j = i + l - 1;
			int r = dp[i][j];
			reps(k, i, j) {
				r = min(r, dp[i][k] + dp[k+1][j]);
			}
			if (abs(w[i] - w[j]) <= 1 && dp[i+1][j-1] == 0) {
				r = 0;
			}
			dp[i][j] = r;
		}
	}
	return N - dp[0][N-1];
}




Measured memory_bytes: 3232
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll a[214514];
int main(){
	ll n;
	cin>>n;
	for(int i=0;i<n;i++)cin>>a[i];
	map<ll,ll>mp;
	ll ans=0;
	for(int i=0;i<n;i++){
		ans+=mp[i-a[i]];
		mp[i+a[i]]++;
	}
	cout<<ans;
	return 0;
}

Measured memory_bytes: 27724
from collections import deque, defaultdict

N, M, P = map(int, input().split())

edge_dic = defaultdict(lambda: [])
reverse_edge_dic = defaultdict(lambda: [])

for _ in range(M):
    A, B, C = map(int, input().split())
    edge_dic[A-1].append([B-1, C-P])
    reverse_edge_dic[B-1].append([A-1, C-P])

forward_set = set()
node_deque = deque()
node_deque.append(0)
forward_set.add(0)
while len(node_deque):
    edge = node_deque.pop()
    for v in edge_dic[edge]:
        goal, cost = v
        if goal not in forward_set:
            forward_set.add(goal)
            node_deque.append(goal)

backward_set = set()
node_deque = deque()
node_deque.append(N-1)
backward_set.add(N-1)
while len(node_deque):
    edge = node_deque.pop()
    for v in reverse_edge_dic[edge]:
        goal, cost = v
        if goal not in backward_set:
            backward_set.add(goal)
            node_deque.append(goal)
can_use = forward_set & backward_set
# print(forward_set, backward_set, can_use)

new_edge_dic = {i: edge_dic[i] for i in can_use}

INF = 10 ** 10

ans_array = [-INF] * N
ans_array[0] = 0


for i in range(len(can_use)+1):
    change_flag = 0
    for key, value in new_edge_dic.items():
        for v in value:
            goal, cost = v
            if ans_array[goal] < ans_array[key] + cost:
                ans_array[goal] = ans_array[key] + cost
                change_flag = 1
    if change_flag == 0:
        break
else:
    print(-1)
    exit()

ans = max(0, ans_array[N-1])
print(ans)


Measured memory_bytes: 58344
n, y = map(int, input().split())
y //= 1000
for c in range(max((5*n - y)//4,0), (10*n - y)//9+1):
    if (y - c) % 5 == 0:
        a = (y-c)//5 - n + c
        b = n - a - c
        print(a,b,c)
        exit()
print(-1,-1,-1)

Measured memory_bytes: 3064
#include <bits/stdc++.h>
#define MOD 1000000007
#define ll long long int
#define db double
#define fastio ios_base::sync_with_stdio(false);cin.tie(NULL);
#define pb push_back
#define endl "\n"
#define mp make_pair
#define f first
#define se second
ll power(ll x, ll y, ll mod = 2e18) {ll ans = 1;x %= mod;while(y){if(y&1) ans = (x * ans) % mod;x = (x * x) % mod;y >>= 1;}return ans;}

ll modInverse(ll a, ll m) { ll m0 = m; ll y = 0, x = 1; if (m == 1) return 0; while (a > 1) { ll q = a / m; ll t = m; m = a % m,a = t; t = y; y = x - q * y; x = t; } if(x < 0) x += m0;return x;}

int takemod(int a, int mod = MOD){a%=mod;if(a<0)a+=mod;return a;}

ll binsearch(std::vector<ll>& nums, ll target) {ll n = nums.size();ll l = 0;ll r = n-1;while(l<=r){ll mid = l+ (r-l)/2;if(nums[mid]==target)return mid;else if(nums[mid]>target)r = mid-1;else l = mid+1;}return -1;}

using namespace std;

int main()
{
   fastio
   string s,t;
   cin>>s>>t;
   int n = s.size();
   int o = t.size();
   int flag =1;
   for(int i =0;i<n;i++)
   {
       if(s[i]!=t[i])
       {
           flag =0;
           break;
       }

   }
   if(flag==1&&n+1==o)
   {
       cout<<"Yes"<<endl;
   }
   else cout<<"No"<<endl;


}




Measured memory_bytes: 3656
// https://atcoder.jp/contests/abc044/tasks/abc044_b

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

int main()
{
  /* Magic word */
  cin.tie(0);
  ios::sync_with_stdio(false);
  /* ---------- */

  string w, r = "Yes";
  char n;
  int cnt;

  cin >> w;

  sort(w.begin(), w.end());

  if (w.length() == 1)
    r = "No";

  for (char c : w)
  {
    if (n == c)
    {
      cnt++;
    }
    else
    {
      if (cnt % 2 == 1)
      {
        r = "No";
        break;
      }
      n = c;
      cnt = 1;
    }
  }

  cout << r << '\n';

  return 0;
}


Measured memory_bytes: 256
//s配列に格納した単語を、辞書順にソートする
//  sort(s.begin(), s.end());
//  string t = "keyence";//で文字列入力ができる
//s.empty() //emptyなら1を出力 入っていれば0を出力
/*//ABC018-B 部分的にreverseをかける解法
int main() {
  string s;
  cin >> s;
  int n;
  cin >> n;
  vector<int>a(n);
  vector<int>b(n);
  rep(i,n) cin>>a.at(i)>>b.at(i);
  rep(i,n)a.at(i)--;
  rep(i,n)b.at(i)--;
  string t;
  rep(i,n){
    t = s;
    for(int k=0;k<=b.at(i)-a.at(i);k++){
      t.at(a.at(i)+k) = s.at(b.at(i)-k);
    }
    s = t;
  }
  cout << s << endl;
}
*///ABC018-B
//  string s;
//  cin >> s;
//  cout << s.at(0) <<endl;
//  cout << s.at(0)-'0' <<endl;
//  Aが16？
//  cout << char(i+48) << endl;//なぜかaは47と得る時がある。+48で出力もaにできる。
//  cout << char(97) << endl;//アスキーコードでaを出力
// sort(b.begin(), b.end());//bという配列を小さい方からソート
// reverse(b.begin(), b.end());//bという配列をリターン
// 10桁でdouble出力するパターン１ 
// printf("%.10f\n", ma);
// 10桁でdouble出力するパターン２
//cout << fixed << setprecision(10);
//  cout << ma << endl;

/*01 02 03 12 13 23　と６回見ていくパターン 
for(int i=0;i<n-1;i++){
  for(int j=i+1;j<n;j++){
    }
  }
*///vector<vector<int>> data(3, vector<int>(4));//int型の2次元配列(3×4要素の)の宣言
//int64_t a;
//10のi乗pow(10, i);
/*string s; stringでの文字列を数字型に変える方法
  cin >> s;
  rep(i,s.size()-2) {
  int a= (s.at(i)-'0')*100 + (s.at(i+1)-'0')*10+ s.at(i+2) -'0';
    */
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
int kan_hyaku(int n){
  int kurai = 0;
  for(int i=0;i<3;i++){
    kurai = n%10;
    n /=10;
  }
  return kurai;
}
int kan_ju(int n){
  int kurai = 0;
  for(int i=0;i<2;i++){
    kurai = n%10;
    n /=10;
  }
  return kurai;
}
int kan_ichi(int n){
  int kurai = 0;
  for(int i=0;i<1;i++){
    kurai = n%10;
    n /=10;
  }
  return kurai;
}
int main() {
  int x;
  cin >> x;
  int sum = 0;
  int ans = 0;
  for(int i=1;i<10000000000;i++){
    sum += i;
//    cout << i << endl;
    if(sum >= x){
      ans = i;
      break;
    }
  }
  cout << ans << endl;
}

Measured memory_bytes: 3632
package main

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

// Scan Standard Input
var sc = bufio.NewScanner(os.Stdin)

func nextLine() string {
	sc.Scan()
	return sc.Text()
}

func main() {
	c, _ := strconv.Atoi(nextLine())

	t_score := 0
	h_score := 0

	for i := 0; i < c; i++ {
		phase := strings.Split(nextLine(), " ")

		comp := strings.Compare(phase[0], phase[1])

		if comp > 0 {
			t_score += 3
		} else if comp == 0 {
			t_score++
			h_score++
		} else {
			h_score += 3
		}
	}
	fmt.Printf("%d %d\n", t_score, h_score)
}



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

int main() {
  string a, b;
  while ( cin >> a >> b ) {
    int n = a.size();
    int m = b.size();
    vector<vector<int>> dp(n + 1, vector<int>(m + 1));
    for ( int i = 1; i <= n; ++i ) {
      for ( int j = 1; j <= m; ++j ) {
        if ( a[i - 1] == b[j - 1] ) dp[i][j] = dp[i - 1][j - 1] + 1;
        else {
          dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
        }
      }
    }
    string answer;
    int i = n, j = m;
    while ( dp[i][j] != 0 ) {
      if ( a[i - 1] == b[j - 1] ) {
        answer.push_back(a[i - 1]);
        i--; j--;
      } else {
        if ( dp[i][j] == dp[i - 1][j] ) {
          i--;
        } else {
          j--;
        }
      }
    }
    reverse(answer.begin(), answer.end());
    cout << answer << endl;
  }
  return 0;
}

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


//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>

//using namespace __gnu_pbds;

	//typedef tree<
			//int,
			//null_type,
			//less<int>,
			//rb_tree_tag,
			//tree_order_statistics_node_update>
	//ordered_set;
	

//#define REP(i,m) for(int i=0;i<(m);++i)
//struct dsu{
	//static const int MAXN=105;
	//int par[MAXN];
	//int size[MAXN];
	//void init(){
		//memset(par,-1,sizeof(par));
		//REP(i,MAXN) size[i]=1;
	//}
	//int root(int a){
		//if(par[a]==-1) return a;
		//return par[a]=root(par[a]);
	//}
	//void unite(int a,int b){
		//a=root(a);b=root(b);
		//if(a==b) return;
		//if(size[a]<size[b]) swap(a,b);
 
		//par[b]=a;
		//size[a]+=size[b];
	//}
	//bool same(int a,int b){
		//return root(a)==root(b);
	//}
//};	

#define ll long long 

int main(){
	ios::sync_with_stdio(false);cin.tie(0);
	ll n;cin>>n;
	vector <ll> vec(n);
	for(int i=0;i<n;i++){
		cin>>vec[i];	
	}
	sort(vec.begin(),vec.end());
	reverse(vec.begin(),vec.end());
	ll ans=vec[0],cnt=n-2,idx=1;
	while(cnt>0){
		if(cnt-2>=0){
			ans+= vec[idx]*2;
			cnt-=2;
		}else{
			ans+= vec[idx];
			cnt--;
		}
		idx++;
	}
	cout<<ans<<endl;
	return 0;
	
}


Measured memory_bytes: 4784
A, B, C, X, Y = map(int, input().split())

res = 0

if A + B > C * 2:
    if X > Y:
        res = min(Y * C * 2 + (X - Y) * A, X * C * 2)
    else:
        res = min(X * C * 2 + (Y - X) * B, Y * C * 2)

else:
    res = A * X + B * Y

print(res)

Measured memory_bytes: 9188
#include <iostream>
#include <vector>
#include <string>
#include <cstring>
#include <queue>
#include <set>
#include <stack>
#include <map>
#include <unordered_map>
#include <cmath>
#include <utility> // pair make_pair
#include <algorithm>
#include <functional>
#include <iomanip>
#include <numeric>
#include <climits> // LLONG_MAX, LLONG_MIN, INT_MIN, INT_MAX
#include <assert.h>

#define m0(x) memset(x,0,sizeof(x))
#define m1(x) memset(x,63,sizeof(x))
#define fill(x,y) memset(x,y,sizeof(x))
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define chmin(x, y) x = min(x, y)
#define ll long long
#define ld long double
//#define int ll
#define INF INT_MAX/10
#define MOD 1000000007

using namespace std;
using Pi = pair<int, int>;
using Graph = vector<vector<int> >;
using WeightGraph = vector<vector<Pi> >;

int Input[100100];

int main() {
  int N; cin >> N;
  string S; cin >> S;
  rep(i, S.size()) {
    S[i] = S[i] + N;
    if (S[i] > 'Z') {
      S[i] = 'A' + S[i] - 'Z' - 1;
    }
  }
  cout << S << endl;
}


Measured memory_bytes: 256
list1 = list(map(int, input().split()))
list2 = list(map(int, input().split()))
list3 = list(map(int, input().split()))
x=list1[0]
y=list1[1]
a=list2[0]
b=list2[1]
c=list3[0]
d=list3[1]
if a * x + b * y == c * x + d * y:
  print("infinity")
else:
  if a * x + b * y < c * x + d * y:
    a,c=c,a
    b,d=d,b
  t = a * x + b * y - (c * x + d * y)
  if a>c:
    print(0)
  else:
    k=x*(c-a)
    if k%t==0:
      print((k//t)*2)
    else:
      print((k//t)*2+1)

Measured memory_bytes: 38256
import scala.annotation.tailrec
import scala.collection.mutable
import scala.io.StdIn._
object Main extends App {
  val Array(length, initial, diff, mod) = readLine.trim.split(' ').map(_.toLong)
  println((1 to 18).map{s ⇒ sumValueOfSameDigit(s)}.foldLeft(0L){(acc, i) ⇒ (acc + i) % mod})
  def power(base: Long, exp: Long): Long = {
    exp match {
      case 0 ⇒ 1L
      case 1 ⇒ base % mod
      case _ ⇒ power(base * base % mod, exp >> 1) * power(base, exp & 1) % mod
    }
  }
  def term(rank: Long): Long = {
    (initial % mod + diff % mod * (rank % mod)) % mod
  }
  def firstRankOver(digit: Int): Long = {
    if (digit > 18) length
    else {
      val min = (1 until digit).foldLeft(1L) { (acc, _) ⇒ acc * 10 }
      math.max(0, math.min(length, (min - initial + diff - 1) / diff))
    }
  }

  def sumValue(size: Int): Long = {
    val from = firstRankOver(size)
    val until = firstRankOver(size + 1)
    val len = until - from
    val first = term(from)
    val mul = power(10, size)
    val den = power(mul - 1, mod - 2)
    val muln = power(mul, len)
    val x = ((muln + mod - 1) % mod * den % mod - len) % mod
    val sumDiff= x * diff % mod * den % mod
    val sumFirst = (muln % mod + mod - 1) * den % mod * first % mod
    val upper = (size + 1 to 18).map{d ⇒ d * (firstRankOver(d + 1) - firstRankOver(d))}.sum
    (sumDiff + sumFirst) % mod * power(10, upper) % mod
  }
  def sumValueOfSameDigit(size: Int): Long = {
    val m = power(10, size)
    val from = firstRankOver(size)
    val until = firstRankOver(size + 1)
    val len = until - from
    val init = term(from)
    def multiplier(n: Long): Long = {
      n match {
        case 0L ⇒ 0
        case 1L ⇒ 1
        case _ if (n & 1) == 1 ⇒  (multiplier(n - 1) * m + 1) % mod
        case _ ⇒ multiplier(n >> 1).let{v ⇒ v * power(m, n >> 1) + v} % mod
      }
    }
    def multiplierN(n: Long): Long = {
      n match {
        case 0L ⇒ 0
        case 1L ⇒ 0
        case _ if (n & 1) == 1 ⇒ (multiplierN(n - 1) * m % mod + n - 1) % mod
        case _ ⇒ multiplierN(n >> 1).let{v ⇒ v * power(m, n >> 1) % mod + v + (n >> 1) % mod * multiplier(n >> 1) % mod} % mod
      }
    }
    val x = multiplier(len)
    val y = multiplierN(len)
    val upper = (size + 1 to 18).map(d ⇒ power(power(10, (firstRankOver(d + 1) - firstRankOver(d))), d)).foldLeft(1L){(acc, p) ⇒ acc * p % mod}
    //println(s"$init, $x, ${diff % mod}, $y")
    ((x * init % mod + diff % mod * y % mod) % mod * upper % mod)//.tap(println)
  }
  implicit class Scope[T](val receiver: T) extends AnyVal {
    def let[A](@inline func: T ⇒ A): A = func(receiver)
    def tap(@inline func: T ⇒ Unit): T = {
      func(receiver)
      receiver
    }
  }
}


Measured memory_bytes: 27440
#include <cstdio>
#include <cctype>
using namespace std;

int main()
{
  char ch;

  while(1)
    {
      scanf("%c", &ch);

      if(isalpha(ch))
	{
	  if(isupper(ch))
	    printf("%c", tolower(ch));
	  
	  if(islower(ch))
	    printf("%c", toupper(ch));
	}else
	{
	  printf("%c", ch);
	  if(ch =='\n')
	    break;
	}
    }
}

Measured memory_bytes: 948
///-----Bismillahir Rahmanir Rahim-----///

#include<bits/stdc++.h>
using namespace std;

///---FAST I/O---///
#define Boost() ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);

///---DATA TYPE---///
typedef long long ll;
typedef long long int lli;
///vector
typedef vector<int> vi;
typedef vector<ll> vl;
///pair
typedef pair<int,int> pii;
typedef pair<double, double> pdd;
typedef pair<ll, ll> pll;

///---LOOP---///
#define rep0(i,n) for(i=0;i<n;i++)
#define rep1(i,n) for(i=1;i<=n;i++)

///---I/O---///
#define sf scanf
#define pf printf

///---OTHERS---///
#define pb push_back
#define all(c)		c.begin(),c.end()
#define MK make_pair
#define F first
#define S second
#define endl '\n'


///---INITIALIZATION---//
#define mem(a,b) memset(a, b, sizeof(a) )

///---CALCULATE---///
#define gcd(a,b) __gcd(a,b)
#define lcm(a,b) (a*(b/gcd(a,b)))
#define sqr(a) ((a) * (a))

///---BIT OPERATION---///
inline bool checkBit(ll n, int i)
{
    return n&(1LL<<i);
}
inline ll setBit(ll n, int i)
{
    return n|(1LL<<i);;
}
inline ll resetBit(ll n, int i)
{
    return n&(~(1LL<<i));
}

///------String/Char Related Functions-----///
string makeintString(int x)
{
    stringstream ss;
    ss << x;
    string str = ss.str();
    ///cout<<str<<endl;
    return str;
}
string makellString(ll x)
{
    stringstream ss;
    ss << x;
    string str = ss.str();
    ///cout<<str<<endl;
    return str;
}
char cpp(char c)
{
    return static_cast<char>(c + 1);
}

///---CONSTANT---///
const double PI = acos(-1);
const double eps = 1e-9;
const int inf = 2000000000;
const ll infLL = 9000000000000000000;
#define MOD 1000000007

ll cnt[2000005];
int main()
{
    Boost();

    int t;
    t=1;
    //cin>>t;
    while(t--)
    {
        ll n,x,sum=0;
        cin>>n;
        for(ll i=0; i<n; i++)
        {
            cin>>x;
            cnt[x]++;
            sum+=x;
        }
        ll q;
        cin>>q;
        ll b,c;
        for(ll i=0; i<q; i++)
        {
            cin>>b>>c;
            ll minusKoro=b*cnt[b];
            ll plusKoro=c*cnt[b];
            cnt[c]+=cnt[b];
            cnt[b]=0;
            sum-=minusKoro;
            sum+=plusKoro;
            cout<<sum<<endl;
        }
    }
    return 0;
}


Measured memory_bytes: 4364
N = int(input())
A = list(map(int, input().split()))


def get_divisors(n, reverse=False):
    from math import sqrt
    divisors = []
    for num in range(1, int(sqrt(n))+1):
        if n % num == 0:
            divisors.append(num)
            if n//num != num:
                divisors.append(n//num)
    return sorted(divisors, reverse=reverse)

status = [0] * N
answers = []
for i in range(N, 0, -1):
    if A[i-1] == status[i-1]:
        continue
    answers.append(i)
    divisors = get_divisors(i)
    a = A[i-1]
    for divisor in divisors:
        status[divisor-1] = (1 + status[divisor-1]) % 2

print(len(answers))
for ans in answers:
    print(ans, end=" ")


Measured memory_bytes: 71404
#include <algorithm>
#include <iostream>
#include <vector>
#include <set>

#include <string.h>

using namespace std;

typedef long long ll;

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 int MAX_N = 3000;
const int MAX_T = 3000;

ll dp1[MAX_N + 2][MAX_T + 2];
ll dp2[MAX_N + 2][MAX_T + 2];

void print_dp(int N, int T, ll dp[MAX_N + 2][MAX_T + 2]) {
    for (int n = 1; n <= N; n++) {
        for (int t = 1; t <= T; t++) {
            cout << dp[n][t] << " ";
        }
        cout << endl;
    }
}

int main(void) {
    int N, T;
    cin >> N >> T;
    
    vector<pair<int, int> > dishes(N);
    for (int i = 0; i < N; i++) {
        int a, b;
        cin >> a >> b;
        dishes[i] = {a, b};
    }

    memset(dp1, 0, sizeof(ll) * (MAX_N + 2) * (MAX_T + 2));
    memset(dp2, 0, sizeof(ll) * (MAX_N + 2) * (MAX_T + 2));

    for (int n = 1; n <= N; n++) {
        for (int t = 1; t <= T; t++) {
            if (dishes[n - 1].first <= t) {
                dp1[n][t] = max(dp1[n - 1][t], dp1[n - 1][t - dishes[n - 1].first] + dishes[n - 1].second);
            } else {
                dp1[n][t] = dp1[n - 1][t];
            }
        }
    }

    for (int n = N; n >= 1; n--) {
        for (int t = 1; t <= T; t++) {
            if (dishes[n - 1].first <= t) {
                dp2[n][t] = max(dp2[n + 1][t], dp2[n + 1][t - dishes[n - 1].first] + dishes[n - 1].second);
            } else {
                dp2[n][t] = dp2[n + 1][t];
            }
        }
    }

    ll max = 0;
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= T - 1; j++) {
            chmax(max, dp1[i - 1][j] + dp2[i + 1][T - 1 - j] + dishes[i - 1].second);
        }
    }

    // print_dp(N, T, dp1);
    // cout << endl;
    // print_dp(N, T, dp2);
    // cout << endl;

    cout << max << endl;

    return 0;
}


Measured memory_bytes: 141056
#include <bits/stdc++.h>
using namespace std;
int tmp(int a) {
    if (a==2) {
        return 1;
    } else if (a%2==0 || a<=1) {
        return 0;
    } else {
        for (int i=3;i<=sqrt(a);i=i+2) {
            if (a%i==0) {
                return 0;
            }
        }
        return 1;
    }
}

int main(void) {
    int n,x,count;
    count = 0;
    cin >> n;
    for (int i=0;i<n;i++) {
        cin >> x;
        tmp(x);
        if (tmp(x)==1) {
            count = count + 1;
        }
    }
    cout << count << endl;
}



Measured memory_bytes: 3076
#include"bits/stdc++.h"
using namespace std;
#define ll long long
#define LL long long
#define MOD 1000000007
#define INF 2000000000000
int dx[4] = { 0,1,0,-1 };
int dy[4] = { 1,0,-1,0 };
ll N, M, K, H, W, L, R, l, r, u, d, sum, Q;
LL ans;
LL no;
bool b, bb[1000001];
string s, t;

int main() {
	cin >> N;
	vector<LL> P(N), Q(N),A(N);
	for (int i = 0; i < N; i++) {
		cin >> P[i];
	}

	for (int i = 0; i < N; i++) {
		cin >> Q[i];
		A[i] = i + 1;
	}
	LL con = 0;
	do {
		con++;
			if (A==P)L=con;
			if (A == Q)R = con;
		
	} while (next_permutation(A.begin(), A.end()));

	cout << abs(R-L) << endl;
	return 0;
}



Measured memory_bytes: 384