akhauriyash/Code-Regression huggingface dataset:
#include <math.h>
#include <stdio.h>
#include <algorithm>
#include <fstream>
#include <functional>
#include <iostream>
#include <map>
#include <string>
#include <utility>
#include <vector>
using namespace std;


int main() {
  int N;
  char S[N];
  cin >> N >> S;
  int x = 0;
  int max = 0;
  for (int i = 0; i < N; i++) {
    if (S[i] == 'I') x++;
    if (S[i] == 'D') x--;
    if (x > max) max = x;
  }
  cout << max << endl;
}


Measured memory_bytes: 256
#include <bit>
#include <bitset>
#include <assert.h>
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <sstream>
#include <iostream>
#include <set>
#include <map>
#include <vector>
#include <math.h>
#include <stdlib.h>
#include <queue>
#include <stack>


typedef long double ld;
typedef long long ll;

using namespace std;

int main() {
	int a, b;
	cin >> a >> b;
	if (a >= 1 && a <= 9 && b >= 1 && b <= 9) {
		cout << a * b << endl;
	} else {
		cout << -1 << endl;
	}

	return 0;
}


Measured memory_bytes: 3592
class PriorityQueue
  MIN = -(2 << 60)

  attr_reader :size

  def initialize(&block)
    @size = 0
    @heap = Array.new
    @get_key = block || :itself.to_proc
  end

  def empty?
    size == 0
  end

  def pop
    return nil if @size <= 0
    max = @heap[1]
    @heap[1] = @heap[@size]
    @size -= 1
    max_heapify(1)
    max
  end

  def push(x)
    @size += 1
    i = @size
    @heap[i] = x
    while i > 1 && @get_key.call(@heap[i / 2]) < @get_key.call(@heap[i])
      t = @heap[i / 2]
      @heap[i / 2] = @heap[i]
      @heap[i] = t
      i = i / 2
    end
  end

  def top
    return nil if @size <= 0
    @heap[1]
  end

  def to_a
    return [] if @size == 0
    @heap[1..@size]
  end

  private

  def max_heapify(i)
    l = 2 * i
    r = 2 * i + 1
    largest =
      l <= @size && @get_key.call(@heap[l]) > @get_key.call(@heap[i]) ? l : i
    largest = r \
      if r <= @size && @get_key.call(@heap[r]) > @get_key.call(@heap[largest])
    unless largest == i
      t = @heap[i]
      @heap[i] = @heap[largest]
      @heap[largest] = t
      max_heapify(largest)
    end
  end
end

N, M = gets.split.map(&:to_i)
a_list = gets.split.map(&:to_i)
bc_list = M.times.map { gets.split.map(&:to_i) }
sorted = bc_list.sort_by { |(_, c)| -c }
pq = PriorityQueue.new { |a| -a } # 小さい値を優先
a_list.each { |a| pq.push(a) }
sorted.each do |(b, c)|
  while b > 0
    break if pq.top >= c
    pq.pop
    pq.push(c)
    b -= 1
  end
end
ans = pq.to_a.reduce(&:+)
puts ans


Measured memory_bytes: 19984
import numpy as np
N, D = map(int, input().split())
X = [[int(i) for i in input().split()] for j in range(N)]

ans = 0
d2 = 0
for j in range(N):
    for i in range(j):
        d2 = 0
        for k in range(D):
            d2 += (X[i][k] - X[j][k])**2
        d = np.sqrt(d2)
        if d.is_integer():
            ans += 1
            
print(ans)

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

using namespace std; 

typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef vector<PII> VPII;
typedef long long LL;
typedef priority_queue<int> PQ_DESC;
typedef priority_queue<int, vector<int>, greater<int>> PQ_ASC;
typedef priority_queue<PII> PQ_DESC_PII;
typedef priority_queue<PII, vector<PII>, greater<PII>> PQ_ASC_PII;

#define ALL(c) (c).begin(),(c).end()
#define PB push_back
#define MP make_pair
#define SORT_ASC(c) sort(ALL(c))
#define SORT_DESC(c) sort(ALL(c), greater<typeof(*((c).begin()))>())
#define SIZE(a) int((a).size())

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define ROF(i,a,b) for(int i=(b-1);i>=(a);--i)
#define REP(i,n) FOR(i,0,n)
#define REP(i,n) FOR(i,0,n)
#define PER(i,n) ROF(i,0,n)

const double EPS = 1e-10;
const double PI  = acos(-1.0);
const int LARGE_INT = 1e9+100;
const int INF = 2e9+100;
const LL INF_LL = (LL)INF * 300 * 300;
const int MOD = 1e9+7;

//debug
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;

LL modpow(LL a, LL n) {
    LL res = 1;
    while (n > 0) {
        if (n & 1) res = res * a % MOD;
        a = a * a % MOD;
        n >>= 1;
    }
    return res;
}

LL modinv(LL a) {
    LL b = MOD, u = 1, v = 0;
    while (b) {
        LL t = a / b;
        a -= t * b; swap(a, b);
        u -= t * v; swap(u, v);
    }
    u %= MOD;
    if (u < 0) u += MOD;
    return u;
}

LL moddev(LL a, LL b){
	return a * modinv(b) % MOD;
}

void Main()
{
    string s;cin>>s;

    int numA=0;
    int numB=0;

    REP(i,3){
        if(s[i] == 'A'){
            numA++;
        }
        else{
            numB++;
        }
    }

    if(numA == 0 || numB == 0){
        cout<<"No"<<endl;
    }
    else{
        cout<<"Yes"<<endl;
    }

	return;
}

int main()
{
	cin.tie(nullptr);
	ios_base::sync_with_stdio(false);
	cout << fixed << setprecision(15);
	Main();
    return 0;
}

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

int main() {
    int N;
    cin >> N;
    deque<ll> A;
    deque<ll> B;
    ll count = 0;
    rep(i, N) {
        ll a, b;
        cin >> a >> b;
        A.push_back(a);
        B.push_back(b);
    }
    for (int i = N-1; i >= 0; i--) {
        A[i] += count;
        if (A[i] % B[i] != 0) {
            count += (B[i] - (A[i] % B[i]));
        }
    }
    cout << count << endl;
}

Measured memory_bytes: 1920
import java.util.Scanner;
public class Main {
	public static void main(String[] args){
		final Scanner sc=new Scanner(System.in);
		int n=sc.nextInt();
		int[] matrix=new int[n+1];
		matrix[0]=matrix[1]=1;
		for(int i=2;i<=n;i++){
			matrix[i]=matrix[i-1]+matrix[i-2];
		}
		System.out.println(matrix[n]);
	}
	
}

Measured memory_bytes: 17324
s = input()
n = len(s)

is_danceable_odd = all([s[i] != 'L' for i in range(n) if i % 2 == 0])
is_danceable_even = all([s[i] != 'R' for i in range(n) if i % 2 == 1])
is_danceable = is_danceable_odd and is_danceable_even

if is_danceable:
	print('Yes')
else:
	print("No")
	

Measured memory_bytes: 2940
using System;
using System.Linq;

public class Solution
{
    /// <summary>
    /// 2分探索で値vの位置を得る．vが無いときは，vを超える最小の値の位置を得る
    /// </summary>
    /// <typeparam name="T"></typeparam>
    /// <param name="v">探す値</param>
    /// <param name="list">対象リスト</param>
    /// <returns>vの位置</returns>
    static int BinSearchIndex(int v, int[] list)
    {
        int minRange = 0;
        int maxRange = list.Count();
        while (minRange != maxRange)
        {
            var center = (minRange + maxRange) / 2;
            if (list[center] < v)
            {
                minRange = center + 1;
            }
            else
            {
                maxRange = center;
            }
        }

        return minRange;
    }

    static bool IsIncludeSame(int[] list)
    {
        return list.Zip(list.Skip(1), (a, b) => a - b).Any(v => v == 0);
    }

    public static void Main()
    {
        const int mod = (int)1e9 + 7;
        var vals = Console.ReadLine().Split(' ').Select(int.Parse).ToArray();
        var n = vals[0];
        var m = vals[1];
        var nm = n * m;
        var a = Console.ReadLine().Split(' ').Select(int.Parse).OrderBy(v => v).ToArray();
        var b = Console.ReadLine().Split(' ').Select(int.Parse).OrderBy(v => v).ToArray();

        if (IsIncludeSame(a) || IsIncludeSame(b))
        {
            Console.WriteLine(0);
            return;
        }

        long pattern = 1;
        for (int i = 1; i <= nm; i++)
        {
            var aIndex = BinSearchIndex(i, a);
            var bIndex = BinSearchIndex(i, b);
            var foundA = aIndex < n && a[aIndex] == i;
            var foundB = bIndex < m && b[bIndex] == i;
            if (foundA && foundB)
            {
                continue;
            }

            int p;
            if (foundA)
            {
                p = m - bIndex;
            }
            else if (foundB)
            {
                p = n - aIndex;
            }
            else
            {
                p = (n - aIndex) * (m - bIndex) - (nm - i);
            }

            pattern *= p;
            pattern %= mod;
        }

        Console.WriteLine(pattern);
    }
}

Measured memory_bytes: 13544
N,K = map(int,input().split())
A = list(map(int,input().split()))
species = list(set(A))
dic = {}
for i in species:
    dic[i] = 0
for i in A:
    dic[i] += 1
if K >= len(species):
    print(0)
else:
    tmp = sorted(dic.values(),reverse=1)
    print(sum(tmp[K:]))

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

using namespace std;

using ll = long long;
using ld = long double;
using P = pair<int, int>;
constexpr ld EPS = 1e-12;
constexpr int INF = numeric_limits<int>::max() / 2;
constexpr int MOD = 1e9 + 7;

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

    string s;
    cin>>s;
    int n=s.length();
    int res=0, d=0;
    for(int i=0;i<n;i++){
        if(s[i]=='L') d -=90;
        else d += 90;
        if(d==360){
            res++;
            d=0;
        }
        else if(d%360==0){
            d=0;
        }
    }
    cout<<res<<endl;
}



Measured memory_bytes: 3212
#include <iostream> 
#include <algorithm> 
#include <cmath> 

using namespace std;

int main() {
	int n;
	cin >> n;
	
	int sum = 0;
	for (int i = 1; i <= n; i+=2) {
		int ans = 0;
		for (int j = 1; j <= i; j++) {
			if (i % j == 0) {
				ans++;
			}
		}
		if (ans == 8) {
			sum++;
		}
	}
	cout << sum;
	
}

Measured memory_bytes: 3608
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, n) for (int i = 0; i < n; ++i)
#define rrep(i, st, n) for (int i = st; i < n; ++i)
using pii = pair<int, int>;
#define chmax(a, b) a = max(a, b)
#define chmin(a, b) a = min(a, b)
#define inf (int)(1e9+7)
#define eb emplace_back
#define mod (ll)(1e9+7)
long power(long a,long b){return b?power(a*a%inf,b/2)*(b%2?a:1)%inf:1;}

/*
 L = 11001010
 11001010
 1100100...
 11000...
 10...
 0...
 
 ... -> (1, 0), (0, 1), (0, 0)
 数字書いてるとこ
 0 -> (0, 0)
 1 -> (1, 0), (0, 1)
 
 ... -> d
 数字書いてるとこで1立ってる個数 -> e
 
 参考
 http://drken1215.hatenablog.com/entry/2019/06/10/150000
 */

int main() {
    string s; cin >> s;
    int sum = 0;
    int e = 0; //standing 1
    //0...
    //10...
    //と見る
    rep(i, s.size()) {
        int d = (int)s.size() - 1 - i; //...
        //cout << s[i] << " " << d << " " << e << endl;
        if (s[i] == '1') (sum += power(2, e++) * power(3, d) % inf) %= inf;
    }
    //11001010
    (sum += power(2, e)) %= inf;
    cout << sum << endl;
}

/*
 L = 1100101, last is 1
 1100100
 11000...
 10...
 0...
 
 cout << s[i] << " " << d << " " << e << endl;
 1 6 0 //0... 2^6 * 3^0
 1 5 1 //10... 2^5 * 3^1
 0 4 2
 0 3 2
 1 2 2 //11000... 2^2 * 3^2
 0 1 3
 1 0 3 //1100100 2^0 * 3^3
 //1100101
 
 1が立ってると、その桁まで、1の数は手前の1まで
 よって最後の1を含めるのを最後に足す
 */


Measured memory_bytes: 512
import java.util.*;

public class Main {
    public static void main(String[] args){
    
    Scanner sc = new Scanner(System.in);
    	 int N = sc.nextInt();
      	 int M = sc.nextInt();
		
        	System.out.println((N-1)*(N-1+1)/2+(M-1)*(M-1+1)/2);
    }
}

Measured memory_bytes: 22740
#include <bits/stdc++.h>
#include <vector>
#include <numeric>
#define PI 3.14159265358979323846
#define MAXINF (1e18L)
#define INF (1e9L)
#define EPS (1e-9)
#define MOD (1e9+7)
#define REP(i, n) for(int i=0;i<int(n);++i)
#define Rep(i,sta,n) for(int i=sta;i<n;i++)
#define RREP(i, n) for(int i=int(n)-1;i>=0;--i)
#define ALL(v) v.begin(),v.end()
#define FIND(v,x) (binary_search(ALL(v),(x)))
#define SORT(v) sort(ALL(v))
#define RSORT(v) sort(ALL(v));reverse(ALL(v))
#define DEBUG(x) cerr<<#x<<": "<<x<<endl;
#define DEBUG_VEC(v) cerr<<#v<<":";for(int i=0;i<v.size();i++) cerr<<" "<<v[i]; cerr<<endl
#define Yes(n) cout<<((n)?"Yes":"No")<<endl
#define YES(n) cout<<((n)?"YES":"NO")<<endl
#define pb push_back
#define fi first
#define se second
using namespace std;
template<class A>void pr(A a){cout << (a) << endl;}
template<class A,class B>void pr(A a,B b){cout << a << " "  ;pr(b);}
template<class A,class B,class C>void pr(A a,B b,C c){cout << a << " " ;pr(b,c);}
template<class A,class B,class C,class D>void pr(A a,B b,C c,D d){cout << a << " " ;pr(b,c,d);}
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll,ll> pll;

vector<ll> dijkstra(ll s, vector<vector<pll>>& cost_map){
    vector<ll> d(cost_map.size(), MAXINF);
    priority_queue<pll, vector<pll>, greater<pll>> q;
    q.push(pll(0, s));
    d[s] = 0;
    while(!q.empty()){
        pll f = q.top();q.pop();
        if(d[f.se] < f.fi) continue;
        for(auto&& v : cost_map[f.se]){
            // ll value = f.fi + v.se;
            if(f.fi + v.se < d[v.fi]) {
                // d[v.fi] = value;
                q.push(pll(d[v.fi] = (f.fi + v.se), v.fi));
            }
        }
    }
    return d;
}

int main(void)
{
    ll n,m;
    cin >> n >> m;
    ll s,t;
    cin >> s >> t;
    s--;t--;

    vector<vector<pll>>Y(n);
    vector<vector<pll>>S(n);
    REP(i, m){
        ll u,v;
        cin >> u >> v;
        ll a,b;
        cin >> a >> b;
        u--;v--;
        Y[u].pb(make_pair(v, a));
        Y[v].pb(make_pair(u, a));
        S[u].pb(make_pair(v, b));
        S[v].pb(make_pair(u, b));
    }

    auto yen = dijkstra(s, Y);
    auto snk = dijkstra(t, S);

    vector<ll> ans(n+1,MAXINF);
    RREP(i, n){
        ans[i]=min(ans[i+1], yen[i] + snk[i]);
    }

    // DEBUG_VEC(yen);
    // DEBUG_VEC(snk);
    // DEBUG_VEC(ans);

    REP(i, n){
        pr(1'000'000'000'000'000 - ans[i]);
    }
}

Measured memory_bytes: 19012
#include <bits/stdc++.h>
using namespace std ;
int main()
{
    string s;
    cin >> s;
    for(int i = 0;i < 4;++i) {
        cout << s.at(i);
    }
    cout << " ";
    for(int i = 4;i < 12;++i) {
        cout << s.at(i);
    }
    cout << endl;
}


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

using namespace std;

const vector<int> dx = {1, -1, 0, 0}, dy = {0, 0, 1, -1};

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int H, W;
  cin >> H >> W;
  queue<pair<int, int>> que;
  vector<string> A(H);
  for (int i = 0; i < H; i++) {
    cin >> A[i];
    for (int j = 0; j < W; j++) {
      if (A[i][j] == '#') que.push(make_pair(i, j));
    }
  }

  int res = 0;
  vector<vector<int>> grid(H, vector<int>(W, 0));
  while (!que.empty()) {
    auto q = que.front();
    que.pop();

    int y = q.first, x = q.second;
    for (int i = 0; i < 4; i++) {
      int ny = y + dy[i], nx = x + dx[i];
      if (ny < 0 || ny >= H || nx < 0 || nx >= W) continue;
      if (A[ny][nx] == '#' || grid[ny][nx] != 0) continue;
      grid[ny][nx] = grid[y][x] + 1;
      res = max(res, grid[ny][nx]);
      que.push(make_pair(ny, nx));
    }
  }
  cout << res << '\n';
  return 0;
}


Measured memory_bytes: 13456
package main

import (
	"fmt"
)

func main() {
	var n int // こま数

	_, _ = fmt.Scan(&n)

	xa := make([]int, n) // こま座標

	for i:= 0;i < n ; i++ {
		_, _ = fmt.Scan(&xa[i])
	}

	var m int // 操作数

	_, _ = fmt.Scan(&m)

	ma := make([]int, m) // 操作対象

	for i:= 0;i < m ; i++ {
		_, _ = fmt.Scan(&ma[i])
	}

	for _, v := range calc(xa, ma) {
		fmt.Println(v)
	}
}

func calc(xa []int, ma []int) []int {
	for _, v := range ma {
		if xa[v-1] < 2019 {
			if  len(xa) != v {
				if xa[v]-1 != xa[v-1] {
					xa[v-1]++
				}
			} else {
				xa[v-1]++
			}
		}
	}
	return xa
}


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

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

int main(void) {
    int h, w;
    char s[52][52];
    cin >> h >> w;
    for (int i = 0; i <= 51; i++) {
        for (int j = 0; j <= 51; j++) {
            s[i][j] = '.';
        }
    }
    for (int i = 1; i <= h; i++) {
        for (int j = 1; j <= w; j++) {
            cin >> s[i][j];
        }
    }
    for (int i = 1; i <= h; i++) {
        for (int j = 1; j <= w; j++) {
            if (s[i][j] == '.') {
                int cnt = 0;
                for (int k = 0; k < 8; k++) {
                    if (s[i + dy[k]][j + dx[k]] == '#') cnt++;
                }
                cout << cnt;
            }
            else cout << '#';
        }
        cout << endl;
    }
}


Measured memory_bytes: 256
#include <cstdio>
#include <iostream>
#include <vector>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <string>
#include <cstring>
#include <sstream>
#include <algorithm>
#include <functional>
#include <queue>
#include <stack>
#include <cmath>
#include <iomanip>
#include <list>
#include <tuple>
#include <bitset>
#include <ciso646>
#include <cassert>

using namespace std;

#define int long long
#define double long double

typedef pair<int, int> P;
typedef tuple<int, int, int> T;

template<class T> string tostr(T x) { stringstream o; o << x; return o.str(); }
template<class T> T sqr(T x) { return x*x; }
template<class T> T mypow(T x, int n) { T r = 1; while (n > 0) { if (n & 1)r = r*x; x = x*x; n >>= 1; }return r; }

int toint(string s) { int v; stringstream i(s); i >> v; return v; }
bool check(int x, int y, int w, int h) { return x >= 0 && y >= 0 && w > x && h > y; }
int gcd(int a, int b) { return b ? gcd(b, a%b) : a; }
int lcm(int a, int b) { return a / gcd(a, b) * b; }

#define REP(i,a,b)	for(int (i) = (a);i < (b);(i)++)
#define rep(i,n)	REP(i,0,n)
#define PER(i,a,b)	for(int (i) = (a-1);i >= (b);(i)--)
#define per(i,n)	PER(i,n,0)
#define each(i,n)	for(auto &i : n)
#define clr(a)		memset((a), 0 ,sizeof(a))
#define mclr(a)		memset((a), -1 ,sizeof(a))
#define all(a)		(a).begin(),(a).end()
#define dump(val) 	cerr << #val " = " << val << endl;
#define dum(val)	cerr << #val " = " << val;
#define FILL(a,v)	fill(a,a+sizeof(a)/sizeof(*a),v)

const int dx[8] = { +1,+0,-1,+0,+1,+1,-1,-1 };
const int dy[8] = { +0,-1,+0,+1,-1,+1,-1,+1 };
const int mod = 1e9 + 7;
const int INF = 1e17 + 9;

typedef tuple<int, int, int, int> F;

int dp[100001][2][2][2][2];
F pre[100001][2][2][2][2];

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

	int n;
	cin >> n;

	string st;
	cin >> st;

	clr(dp);
	clr(pre);

	dp[0][0][0][0][0] = 1;
	dp[0][0][1][0][1] = 1;
	dp[0][1][0][1][0] = 1;
	dp[0][1][1][1][1] = 1;

	rep(i, n) rep(e, 2) rep(s, 2) rep(p, 2) rep(t, 2) {
		if (dp[i][e][s][p][t]) {
			if (i == n - 1) {
				if (e != t)continue;
			}
			if (t) {
				if (st[i] == 'o') {
					dp[i + 1][e][s][t][p] = 1;
					pre[i + 1][e][s][t][p] = F(e, s, p, t);
				}
				else {
					dp[i + 1][e][s][t][!p] = 1;
					pre[i + 1][e][s][t][!p] = F(e, s, p, t);
				}
			}
			else {
				if (st[i] == 'o') {
					dp[i + 1][e][s][t][!p] = 1;
					pre[i + 1][e][s][t][!p] = F(e, s, p, t);
				}
				else {
					dp[i + 1][e][s][t][p] = 1;
					pre[i + 1][e][s][t][p] = F(e, s, p, t);
				}
			}
		}
	}

	rep(e, 2) rep(s, 2) rep(p, 2) rep(t, 2) {
		if (dp[n][e][s][p][t] && s == t) {
			string ans;
			int j = n;
			while (ans.size() < n) {
				auto tm = pre[j--][e][s][p][t];
				ans.push_back((get<3>(tm) ? 'S' : 'W'));
				e = get<0>(tm); s = get<1>(tm); p = get<2>(tm); t = get<3>(tm);
			}
			reverse(all(ans));
			cout << ans << endl; return 0;
		}
	}
	cout << -1 << endl;

	return 0;
}

Measured memory_bytes: 63232
use whiteread::parse_line;

fn main() {
    let (r, g, b, n): (usize, usize, usize, usize) = parse_line().unwrap();
    let mut cnt = 0;

    for x in 0..=3000 {
        if x > n {
            break;
        }
        for y in 0..=3000 {
            if x * r + y * g > n {
                break;
            }
            if (n - (x * r + y * g)) % b == 0 {
                cnt += 1;
            }
        }
    }
    println!("{}", cnt);
}


Measured memory_bytes: 2132
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h> 
using namespace std;

typedef long long ll;

#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0) 
#define rep(pp,nn) for (int i = pp; i < nn; ++i)
#define vi vector<int>
#define vll vector<ll>
#define vs vector<string>
#define endl "\n"

void __print(int x) {cerr << x;}
void __print(long x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(unsigned x) {cerr << x;}
void __print(unsigned long x) {cerr << x;}
void __print(unsigned long long x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}

string int_to_string(int x) {
    stringstream ss;
	ss << x;
	string ni = ss.str();
	return ni;
}
int string_to_int(string x) {
	int n;
	stringstream s(x);
	s >> n;
	return n;
}

int64_t power_mod(ll a, ll b, ll mo) {
	ll ans = 1;
	while (b) {
		if(b & 1) {
			ans = (ans % mo * a % mo) % mo;
		}
		a = (a % mo * a % mo) % mo;
		b /= 2;
	}
	return ans;
}
int64_t POW(ll a, ll b) {
	ll ans = 1;
	while (b) {
		if(b & 1) {
			ans = ans * a;
		}
		a = a * a;
		b /= 2;
	}
	return ans;
}

vector<int64_t> INVERSE(int64_t nn, int64_t mo) {
	vector<int64_t> inv(nn + 1);
	vector<int64_t> mul(nn + 1);
	inv[0] = 1;
    inv[1] = 1;
	for (ll i = 2; i <= nn; ++i) {
		inv[i] = (mo - (mo / i) * inv[mo % i] % mo) % mo; 
	}
	mul[0] = 1;
	for (int i = 1; i <= nn; ++i) {
		mul[i] = (mul[i - 1] * inv[i]) % mo;
	}
	return mul;
}

template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}

#ifndef ONLINE_JUDGE
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define debug(x...)
#endif

int mod = 1e9 + 7;

void add_self(int &a , int b) {
	a += b;
	if (a >= mod) {
		a -= mod;
	}
}

int main() {
	IOS; //READ THE QUESTION PROPERLY BSDK
	string s;
	int d;
	cin >> s >> d;
	int n = (int)s.size();
	vector<vector<int>> dp(d,vector<int> (2));
	//int m = 1e9 + 7;
	dp[0][0] = 1;
	for (int i = 0; i < n; ++i) {
		vector<vector<int>> new_dp(d, vector<int> (2));
		for (int j = 0; j < d; ++j) {
			for (bool sm_already : {false, true}) {
				for (int digit = 0; digit < 10; ++digit) { 
					if (digit > s[i] - '0' && !sm_already) {
						break;
					} 
				//debug(j,dp[j][0], s[i] - '0',digit,i);
					add_self(new_dp[(j + digit) % d][sm_already || (digit < s[i] - '0')],dp[j][sm_already]);
			    }
			}
		}
		//adebug(new_dp);
		dp = new_dp;
	}
	int answer = (dp[0][0] + dp[0][1]) % mod;
	answer--;
	if (answer == -1) {
		answer = mod - 1;
	}
	cout << answer;
}





























Measured memory_bytes: 3680
#include<iostream>
#include<iomanip>
#include<math.h>
#include<algorithm>
#include<string>
#include<vector>
#include<queue>
#include<stack>
#include<set>
#include<map>
#define REP(i, N) for(ll i = 0; i < N; ++i)
#define FOR(i, a, b) for(ll i = a; i < b; ++i)
#define ALL(a) (a).begin(),(a).end()
#define pb push_back
#define INF (long long)1000000000
#define MOD 1000000007
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};

int main(void) {
	while(true) {
		int N, W, H;
		cin>>N;
		if(N == 0) break;
		cin>>W>>H;
		vector<vector<bool> > m(H, vector<bool>(W, false));
		vector<vector<int> > wa(H + 1, vector<int>(W + 1, 0));
		REP(i, N) {
			int x, y;
			cin>>x>>y;
			--x;
			--y;
			m[y][x] = true;
		}
		REP(i, H) {
			REP(j, W) {
				wa[i + 1][j + 1] += wa[i + 1][j] + (int)m[i][j];
			}
		}
		REP(i, H) {
			REP(j, W) {
				wa[i + 1][j + 1] += wa[i][j + 1];
			}
		}
		int S, T;
		cin>>S>>T;
		int ans = 0;
		REP(i, H - T + 1) {
			REP(j, W - S + 1) {
				ans = max(ans, wa[T + i][S + j] - wa[T + i][j] - wa[i][S + j] + wa[i][j]);
			}
		}
		cout<<ans<<endl;
	}
}

Measured memory_bytes: 3136
#include<stdio.h>
#define MAX 100005
#define NIL -1
struct Node_struct{int p, l, r;}; /*p: 親(parent), l: 一番左の子(left child), r:右の兄弟(right sibling)*/
typedef struct Node_struct Node;
Node T[MAX];
int D[MAX];

void print(int u){
  int i, c;
  printf("node %d: parent = %d, depth = %d, ", u, T[u].p, D[u]);

  if(T[u].p==-1) printf("root, ");
  else if(T[u].l==NIL) printf("leaf, ");
  else printf("internal node, ");

  printf("[");
  for (i=0, c = T[u].l; c != NIL; i++, c = T[c].r){
    if(i) printf(", ");
    printf("%d", c);
  }
  printf("]\n");

}

void calcDepth(int u, int p){
  D[u] = p;
  if(T[u].r != NIL) calcDepth(T[u].r,p);
  if(T[u].l != NIL) calcDepth(T[u].l,p+1);
}

int main(){
  int i, j, k;
  int n;
  int id, sib, child;
  int root = NIL;
  scanf("%d", &n);
  for(i=0; i<n; i++) T[i].p = T[i].l = T[i].r = NIL;
  for(i=0; i<n; i++){
    scanf("%d %d", &id, &k);
    for(j = 0, sib = NIL; j<k; j++){ //子を入力する (input children)
      scanf("%d", &child);
      T[child].p = id;
      if(j == 0) T[id].l = child; //idの一番左の子 (the most left child of id)
      else T[sib].r = child; //左の兄弟に繋げる (connect to left sibling)
      sib = child;//次の子供の左の兄弟 (the left sibling of the next child)
    }
  }

  //根を求める (find the root)
  for(i=0; i<n; i++){
    if(T[i].p == -1) root = i;
  }

  //それぞれのノードの深さを求める (find depth of each node)
  calcDepth(root, 0);

  //出力 (output)
  for(i=0; i<n; i++) print(i);

  return 0;
}


Measured memory_bytes: 6480
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long ll;

#define REP(i, n) for(int i = 0; i < (int)(n); i++)
#define ALL(x) (x).begin(), (x).end()

int main()
{
	int a, b;
	cin >> a >> b;

	int d = a / b;
	int r = a % b;
	double f = (double)a / b;

	printf("%d %d %.10f\n", d, r, f);

	return 0;
}




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

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

#define fi first
#define se second
#define repl(i,a,b) for(ll i=(ll)(a);i<(ll)(b);i++)
#define rep(i,n) repl(i,0,n)
#define each(itr,v) for(auto itr:v)
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define dbg(x) cout<<#x"="<<x<<endl
#define mmax(x,y) (x>y?x:y)
#define mmin(x,y) (x<y?x:y)
#define maxch(x,y) x=mmax(x,y)
#define minch(x,y) x=mmin(x,y)
#define uni(x) x.erase(unique(all(x)),x.end())
#define exist(x,y) (find(all(x),y)!=x.end())
#define bcnt __builtin_popcount

#define INF 1e16

#define MAX_V 500

struct edge{ ll to,cap,rev; };
vector<edge> G[MAX_V];
ll level[MAX_V];
ll iter[MAX_V];

void add_edge(ll from,ll to,ll cap){
  G[from].push_back((edge){to,cap,G[to].size()});
  G[to].push_back((edge){from,0,G[from].size()-1});
}

void bfs(ll s){
  memset(level,-1,sizeof(level));
  queue<ll> que;
  level[s]=0;
  que.push(s);
  while(!que.empty()){
    ll v=que.front(); que.pop();
    for(ll i=0;i<G[v].size();i++){
      edge &e=G[v][i];
      if(e.cap>0&&level[e.to]<0){
        level[e.to]=level[v]+1;
        que.push(e.to);
      }
    }
  }
}

ll dfs(ll v,ll t,ll f){
  if(v==t)return f;
  for(ll &i=iter[v];i<G[v].size();i++){
    edge &e=G[v][i];
    if(e.cap>0&&level[v]<level[e.to]){
      ll d=dfs(e.to,t,min(f,e.cap));
      if(d>0){
        e.cap-=d;
        G[e.to][e.rev].cap+=d;
        return d;
      }
    }
  }
  return 0;
}

ll max_flow(ll s,ll t){
  ll flow=0;
  while(1){
    bfs(s);
    if(level[t]<0)return flow;
    memset(iter,0,sizeof(iter));
    ll f;
    while((f=dfs(s,t,INF))>0){
      flow+=f;
    }
  }
}

ll n;
ll a[10101];

int main(){
  cin>>n;
  ll s=0;
  rep(i,n){
    cin>>a[i];
    s+=max(a[i],0LL);
  }
  ll source=n,sink=n+1;
  rep(i,n){
    if(a[i]>0)add_edge(source,i,a[i]);
    else add_edge(i,sink,-a[i]);
    repl(j,i+1,n){
      if((j+1)%(i+1)==0)add_edge(j,i,INF);
    }
  }
  cout<<s-max_flow(source,sink)<<endl;
	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main(void){
    int a,b,c;
    cin>>a>>b>>c;
    if (a==b&&b==c&&c==a) {
        cout<<"No"<<endl;
    } else if (a==b) {
        cout<<"Yes"<<endl;
    } else if (a==c) {
        cout<<"Yes"<<endl;
    } else if (b==c) {
        cout<<"Yes"<<endl;
    } else {
        cout<<"No"<<endl;
    }
}


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

if N == 1:
    L, R = 0, 9
elif N == 2:
    L, R = 10, 99
else:
    L, R = 100, 999

for x in range(L, R+1):
    ss = list(map(int, str(x)))
#    print(x, ss)
    for s, c in scs:
        if ss[s-1] != c:
            break
    else:
        print(x)
        break
else:
    print(-1)


Measured memory_bytes: 3188
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vi;
#define REP(i, n) for (ll i = 0; i < (n); ++i)
#define OUT(x) cout << (x) << endl;
#define OUTA(a, n) \
    REP(i, n) { cout << (a[i]) << (i == n - 1 ? "\n" : " "); }
#define ALL(a) (a).begin(), (a).end()
#define SORT(a) sort(ALL(a))
#define RSORT(a) \
    SORT(a);     \
    reverse(ALL(a))

const ll INF = 1e18;
const ll MOD = 1e9 + 7;

int main()
{
    string S;
    cin >> S;
    string ans = "Yes";
    REP(i, S.size())
    {
        if (!(i % 2 == 0 and S[i] == 'h' or i % 2 == 1 and S[i] == 'i'))
        {
            ans = "No";
        }
    }
    if (S.size() % 2 == 1)
    {
        ans = "No";
    }

    OUT(ans);
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define ll long long int 
#define IOS ios_base::sync_with_stdio(false);cin.tie(NULL);
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define mx *max_element
#define mn *min_element
#define fo(i,n) for(ll i=0;i<n;i++)
#define loop(i,a,b) for(ll i=a;i<=b;i++)
#define rfo(i,n) for(ll i=n-1;i>=0;i--)
#define rloop(i,a,b) for(ll i=a;i>=b;i--)
#define all(x) x.begin(),x.end()
#define sortall(x) sort(all(x))
#define precision cout<<fixed<<setprecision(10)
#define mem(x,p) memset(x,p,sizeof(x))
#define w(t) ll t;cin>>t;while(t--)
#define kk "\n"
#define setbits(x) __builtin_popcountll(x)
const double pi=3.1415926535897932384626;
//const ll mod = 998244353;
const ll mod=1e9+7;
int main()
{
  IOS
  ll n;
  cin>>n;
  ll a[n];
  fo(i,n)
  cin>>a[i];
  sort(a,a+n);
  ll s=a[n-1];ll c=1;
  for(ll i=n-2;i>0;i--)
  {
      s=s+(min(2ll,n-1-c)*a[i]);
      c=c+min(2ll,n-1-c);
      if(c==n-1)
      break;
  }
  cout<<s;
  return 0;
}

Measured memory_bytes: 5224
N = int(raw_input())
s = [int(raw_input()) for _ in range(N)]

result = sum(s)
if (result % 10) != 0:
    print(result)
else:
    s.sort()
    for i in range(len(s)):
        if (s[i] % 10) != 0:
            result -= s[i]
            break
    if (result % 10) != 0:
        print(result)
    else:
        print(0)

Measured memory_bytes: 2568
#include <iostream>
using namespace std;
bool isInputOk(int v)
{
	return v>=0 && v<86400; 
}
int main()
{
	int S;
	cin >> S;
	int s=S%60;
	int m1=S/60;
	int h=m1/60;
	int m=m1%60;
	if(isInputOk(S)) cout <<h<<":"<<m<<":"<<s<<endl ;
	else cout <<"input error"<<endl;
	return 0;
} 

Measured memory_bytes: 3084
#include <bits/stdc++.h>
#define REP(i,n) for (int i=0;i<(n);i++)
#define ALL(a) (a).begin(),(a).end()
#define RFOR(i,a,b) for (int i=(b)-1;i>=(a);i--)
#define REP(i,n) for (int i=0;i<(n);i++)
#define RREP(i,n) for (int i=(n)-1;i>=0;i--)
#define ll long long
#define ull unsigned long long
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};

using namespace std;

int main(){
  //  cin.tie(0);
  //  ios::sync_with_stdio(false);
  int n,m;
  while(cin>>n>>m,n){
    int nsize = n*(n+1)/2;
    int msize = m*(m+1)/2;
    vector<int> rrr(nsize);
    vector<int> ccc(msize);
    int tmp;


    int k = n;
    REP(i,n){
      cin >> tmp;
      rrr[i] = tmp;
      int wa = tmp;
      for(int j = i-1;j>=0;j--){
	wa += rrr[j];
	rrr[k] = wa;
	k++;
      }
    }
    k = m;
    REP(i,m){
      cin >> tmp;
      ccc[i] = tmp;
      int wa = tmp;
      for(int j = i-1;j>=0;j--){
	wa += ccc[j];
	ccc[k] = wa;
	k++;
      }
    }
    sort(rrr.begin(),rrr.end());
    sort(ccc.begin(),ccc.end());
    rrr.push_back(-1);ccc.push_back(-1);
    int ri = 0, ci = 0;
    int ans = 0;
    int cct = 1, rct = 1;
    
    bool is_r = true, is_c = true;
    while(true){
      while(is_r && rrr[ri] == rrr[ri+1]){
	rct++;
	ri++;
      }
      while(is_c && ccc[ci] == ccc[ci+1]){
	cct++;
	ci++;
      }
      if(rrr[ri] == ccc[ci]){
	ans += rct * cct;
	//	cout << rrr[ri] << " " << ccc[ci] << endl;
	is_c = true;
	is_r = true;
	rct = 1;
	cct = 1;
	ri++;
	ci++;
      }
      else if(rrr[ri] > ccc[ci]){
	ci++;
	is_c = true;
	is_r = false;
	cct = 1;
      }else{
	ri++;
	is_r = true;
	is_c = false;
	rct = 1;
      }
      if(ri > nsize-1 || ci > msize-1)break;
    }
    cout << ans << "\n";
  }
  return 0;
}

Measured memory_bytes: 20448
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
//#define ll long long
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 (a>b) { a=b; return 1; } return 0; }
#define rep(i, n) REP(i, 0, n)
#define rep_rev(i, n) for (int (i) = (int)(n) - 1 ; (i) >= 0 ; --(i))
#define ALL(v) v.begin(), v.end()
#define MSG(a) cout << #a << " " << a << endl;
#define REP(i, x, n) for(int i = x; i < n; i++)
#define all(x) (x).begin(),(x).end()
ll t1,t2;
const ll mod = 1000000007;
const int INF = 1e9;
const ll INFLONG = 1e18;
void swap(ll *x,ll *y){
  ll tmp;
  tmp = *x;
  *x = *y;
  *y = tmp;
}
int main(){
  ll n,k,s;
  cin >> n >> k >> s;
  vector<ll> vec(n);
  ll tmp = 3;
  if(s <= 2){
    tmp = 5;
  }else{
    tmp = s-1;
  }
  rep(i,n){
    if(k){
      vec[i] = s;
      k--;
    }else{
      vec[i] = tmp;
    }
  }
  rep(i,n){
    cout << vec[i] << endl;
  }
}

Measured memory_bytes: 2048
a = int(input())
b = int(input())
c = int(input())
d = int(input())
e = int(input())

items = [a, b, c, d, e]
import itertools
import math
min_total = 1000
p = itertools.permutations(items, len(items))
for v in itertools.permutations(items, len(items)):
    total = 0
    for i, item in enumerate(v):
        if i != len(v) - 1:
            total += math.ceil(item / 10) * 10
        else:
            total += item
    min_total = min(min_total, total)
print(min_total)


Measured memory_bytes: 3064
#include <iostream>
using namespace std;
int sp(int num,int s,int n)
{
    if(!num&!s)return 1;
    if(n>9)return 0;
    return sp(num-1,s-n,n+1)+sp(num,s,n+1);
}
int main()
{
    while(1)
    {
        int n,s;
        cin>>n>>s;if(!n)return 0;
        cout<<sp(n,s,0)<<endl;
    }
    return 0;
}

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

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

using namespace std;

typedef long long ll;
const int IINF = INT_MAX;
const ll LLINF = LLONG_MAX;

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

void compute() {

}

bool check(string s) {
  int a = 0;
  rep(i,(int)s.size()) {
    if( s[i] == ')' ) --a;
    else ++a;
    if( a < 0 ) return false;
  }
  return a == 0;
}

int main() {
  int n;
  cin >> n;
  string s;
  cin >> s;
  int a = 0, mini = INT_MAX;
  rep(i,(int)s.size()) {
    if( s[i] == ')' ) --a;
    else ++a;
    mini = min(mini,a);
  }
  string t = "";
  if( mini < 0 ) t = string(-mini,'(');
  t += s;
  a = 0;
  rep(i,(int)t.size()) {
    if( t[i] == ')' ) --a;
    else ++a;
  }
  if( a ) {
    t += string(a,')');
  }
  cout << t << endl;
  assert(check(t));
  compute();
  return 0;
}


Measured memory_bytes: 256
import fractions
from functools import reduce
n=int(input())
a=list(map(int,input().split()))


l=[0]
r=[0]
for i in range(0,n):
    l.append(fractions.gcd(l[i],a[i]))
    r.append(fractions.gcd(r[i],a[n-i-1]))

#print(l,r)
r=r[::-1]
ans=[]
for i in range(n):
    ans.append(fractions.gcd(l[i],r[i+1]))
print(max(ans))

Measured memory_bytes: 16160
#include <iostream>

using namespace std;

int main()
{
    double xa1, xa2, ya1, ya2;
    double xb1, xb2, yb1, yb2;

    while (cin >> xa1 >> ya1 >> xa2 >> ya2
           >> xb1 >> yb1 >> xb2 >> yb2) {
        if (xa1 <= xb2 && xb1 <= xa2 && ya1 <= yb2 && yb1 <= ya2)
            cout << "YES" << endl;
        else
            cout << "NO" << endl;
    }

    return 0;
}

Measured memory_bytes: 1220
import java.util.Scanner;
import java.lang.Math;
public class Main{
    public static void main(String[] args) {
	Scanner scan = new Scanner(System.in);
	while(scan.hasNext()) {
	    String input = scan.nextLine();
	    String[] inputs = input.split(" ");
	    int a = Integer.parseInt(inputs[0]);
	    String op = inputs[1];
	    int b = Integer.parseInt(inputs[2]);
	    if (op.equals("+")) {
		System.out.println(a+b);
	    } else if (op.equals("-")) {
		System.out.println(a-b);
	    } else if (op.equals("*")) {
		System.out.println(a*b);
	    } else if (op.equals("/")) {
		System.out.println(a/b);
	    } else if (op.equals("?")) {
		break;
	    }
	}
    }
}

Measured memory_bytes: 26100
#include <iostream>
#include <vector>
#include <set>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <algorithm>
#include <queue>
#include <cmath>
// #include <atcoder/all>
using namespace std;
// using namespace atcoder;

int main() {
	int n;
	cin >> n;
	vector<int> v(n, 0);
	int res = 0;
	for (int i = 0; i < n; i++) {
		cin >> v[i];
		if (i > 0 && v[i] == v[i - 1]) {
			v[i] = -1;
			res++;
		}
	}
	cout << res << endl;
}






Measured memory_bytes: 3592
import std.algorithm, std.container, std.conv, std.math, std.range, std.typecons, std.stdio, std.string;

auto rdsp(){return readln.splitter;}
void pick(R,T)(ref R r,ref T t){t=r.front.to!T;r.popFront;}
void readV(T...)(ref T t){auto r=rdsp;foreach(ref v;t)pick(r,v);}

void main()
{
  int a, b, c, d; readV(a, b, c, d);

  auto n = 101, e = new int[](n);
  e[a]++; e[b]--; e[c]++; e[d]--;
  foreach (i; 1..n) e[i] += e[i-1];

  writeln(e.filter!"a==2".count);
}


Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<set>
#include<string>
#include<vector>
#include<queue>

using namespace std;

/*
//1
int main(){
	int d, c;
	cin >> d >> c;

	cout << d*c << endl;

	return 0;
}
*/


//2
int main(){
	int c1, c5, c10,c50,c100, c500;
	cin >> c1 >>  c5 >> c10 >> c50 >> c100 >> c500;
	int x = c1 + c5*5 + c10*10 + c50*50 + c100*100 + c500*500;
	if(x>=1000) cout << 1 << endl;
	else cout << 0 << endl;

	return 0;
}


/*
//3
int main(){


	return 0;
}
*/

/*
//4
int main(){


	return 0;
}
*/

//=====

/*
//5
int main(){


	return 0;
}
*/

/*
//6
int main(){


	return 0;
}
*/

/*
//7
int main(){


	return 0;
}
*/

/*
//8
int main(){


	return 0;
}
*/

/*
//9
int main(){


	return 0;
}
*/

/*
//10
int main(){


	return 0;
}
*/


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

using namespace std;

#define sp(x) cout<<setprecision(x);
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define REP(i,n) FOR(i,0,n)
#define all(a) (a).begin(), (a).end()
#define inf 10000000
#define linf INT64_MAX*0.99
#define print(s) cout<<(s)<<endl

typedef pair<int, int> P;
typedef long long ll;
 
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n, x, y; cin>>n>>x>>y;
    int minimum = x+y-n;
    if(minimum<0) minimum =0;
    cout<<min(x,y)<<" "<<minimum<<endl;
    return 0;
}

Measured memory_bytes: 256
// D - Candy Distribution - https://atcoder.jp/contests/abc105/tasks/abc105_d

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define REP(i,s,t) for(int i = (s); i < (t); i++)

int N;
ll M;
vector<ll> A;
map<ll, int> nmod;
vector<ll> sum;

int main() {
//    freopen("input", "r", stdin);
    scanf("%d %lld", &N, &M);
    A.assign(N, 0LL);
    sum.assign(N+1, 0LL);
    REP(i,0,N) {
        scanf("%lld", &A[i]);
        A[i] %= M;
        sum[i+1] = sum[i] + A[i];
        sum[i+1] %= M;
    }

    ll sol = 0LL;
    REP(i,0,N) {
        ll tmp = sum[i+1];
        sol += nmod[tmp];
        if(tmp==0) sol++;
        nmod[tmp]++;
    }

    printf("%lld\n", sol);
}


Measured memory_bytes: 5760
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int sx,sy,tx,ty;
    cin>>sx>>sy>>tx>>ty;
    int dx = tx-sx;
    int dy = ty - sy;
    cout<<string(dy,'U')<<string(dx,'R');
    cout<<string(dy,'D')<<string(dx,'L');
    cout<<'L'<<string(dy+1,'U')<<string(dx+1,'R')<<'D';
    cout<<'R'<<string(dy+1,'D')<<string(dx+1,'L')<<'U';
    cout<<endl;

}


Measured memory_bytes: 256
#include <stdio.h>

int main(){

  int i,n,flag = 1,arr[100],tmp,count = 0;;

  //in
  scanf("%d",&n);

  for(i=0;i<n;i++){
    scanf("%d",&arr[i]);
  }
  
  //sort
  while(flag){
    flag = 0;
  
    for(i=n-1;i>0;i--){
      if(arr[i]<arr[i-1]){
	tmp = arr[i-1];
	arr[i-1] = arr[i];
	arr[i] = tmp;
	flag = 1;
	count++;
      }
    }
  }
  
  //out
  for(i=0;i<n;i++){
    if(i!=0) printf(" ");
    printf("%d",arr[i]);
  }
  printf("\n%d\n",count);
  
  
  return 0;

}

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

int main(){
    int N;
    double z;
    cin >> N;
    vector<int> f(N + 1);
    for(int n = 6; n <= N; n++){
        for(int x = 1; x < sqrt(n); x++){
            for(int y = 1; y < sqrt(n); y++){
                if(- 3 * (pow(x, 2) + pow(y, 2)) - 2 * x * y + 4 * n < 0) continue;
                z = (-(y + x) + sqrt(- 3.0 * (pow(x, 2) + pow(y, 2)) - 2.0 * x * y + 4.0 * n)) / 2.0;
                int z_d = z;
                double z_i = z - z_d * 1.0;
                if(z_i != 0 or z <= 0) continue;
                if(pow(x, 2) + pow(y, 2) + pow(z_d, 2) + x * y + y * z + z * x == n){
                    f[n]++;
                }
            }
        }
    }
    for(int n = 1; n <= N; n++) cout << f[n] << endl;
}

Measured memory_bytes: 3640
/*Made by Shivam Solanki*/
#include<bits/stdc++.h>
#pragma GCC optimize ("Ofast")
using namespace std;
#define DEBUG(x) cerr << '>' << #x << ':' << x << endl;
#define ll long long int
#define endl '\n'
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<vll> vvl;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<vi> vvi;
typedef vector<bool> vb;
typedef vector<pii> vp;
typedef vector<pll> vpll;
typedef map<int,int> mii;
typedef map<ll,ll> mll;
typedef set<int> sii;
typedef set<ll> sll;
typedef queue<int> qii;
typedef priority_queue<int> pq;
typedef unordered_map<int,int> umii;
typedef unordered_map<ll,ll> umll;
#define all(x) x.begin(),x.end()
#define rep(i,k,n) for (int i = k; i < n; ++i) 
#define repr(i,k,n) for (int i = n; i>=k; --i)
#define repll(i,k,n) for (ll i = k; i < n; ++i) 
#define pb push_back
#define mp make_pair
#define gcd __gcd
#define F first
#define S second
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
const int INF = 1e9+5;
const int MOD = 1e9+7;
const ll inf = 2e18+11;
double pi = 2 * acos(0.0); 
 
void solve(){
    int n;
    cin>>n;
    int a[n];
    int x=0;
    rep(i,0,n){
        cin>>a[i];
        x^=a[i];
    }
    rep(i,0,n){
        x^=a[i];
        cout<<x<<' ';
        x^=a[i];
    }
}
 
int main(){ 
    // #ifndef ONLINE_JUDGE  
        // freopen("input.txt", "r", stdin); 
        // freopen("output.txt", "w", stdout); 
    // #endif 
    fastio;
    int t=1;
    // cin>>t;
    while(t--)
        solve();
    return 0;
}

Measured memory_bytes: 4336
#include<bits/stdc++.h>
#define ll long long int
using namespace std;
//ll s[500500];
//const int N=1e7+5;
//ll f[N],n,ans;
int main(){
   ll n;
  cin >> n;
  ll ans = n - 1;
  for (ll i = 1; i * i <= n; i++) {
    if (n%i)continue;
    ll j = n / i;
    ans = min(ans, i + j - 2);
  }
  cout << ans << "\n";
}




Measured memory_bytes: 3608
#include<bits/stdc++.h>
typedef long long int ll;
typedef unsigned long long int ull;
#define BIG_NUM 2000000000
#define HUGE_NUM 99999999999999999
#define MOD 1000000007
#define EPS 0.000000001
using namespace std;


#define NUM 45

bool is_black[NUM];

int main(){

	double max_diff = 0,tmp_diff;
	int V,num_black;

	for(int tmp_V = 2; tmp_V <= 40; tmp_V++){
		for(int num = 1; num <= tmp_V-1; num++){

			tmp_diff = (double)num-((double)num/(double)(tmp_V-num+1)+(double)(tmp_V-num)/(double)tmp_V);
			if(tmp_diff > max_diff){
				max_diff = tmp_diff;
				V = tmp_V;
				num_black = num;
			}
		}
	}

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

	for(int i = 0; i < num_black; i++){

		is_black[i] = true;
	}

	for(int i = num_black; i < V; i++){

		is_black[i] = false;
	}

	for(int i = 0; i < V; i++){
		for(int k = 0; k < V; k++){
			if(k == i){
				printf("N");
				continue;
			}

			if(!is_black[i]){

				printf("Y");

			}else{

				if(is_black[k]){

					printf("N");

				}else{
					printf("Y");
				}
			}
		}
		printf("\n");
	}

	return 0;
}



Measured memory_bytes: 3136
#include <bits/stdc++.h>
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <string>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <iomanip>
#include <utility>
#include <tuple>
#include <functional>
#include <bitset>
#include <cassert>
#include <complex>
#include <stdio.h>
#include <time.h>
#include <numeric>
#include <unordered_map>
#include <unordered_set>

using namespace std;

#define vv vector< vector< int > >
#define ll long long
#define ALL(a) (a).begin(), (a).end()
const long long mod = 1000000000 + 7;
const long long INF = 9e18;
const double PI = 3.14159265358979323846;

ll gcd(ll a, ll b){if (b == 0) return a;return gcd(b, a % b);}
ll lcm(ll a, ll b) { return a / gcd(a, b) * b; }

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


int main(){
    int H, W;
    cin >> H >> W;
    string tmp, C[2*H];
    for(int i = 0; i < 2*H; i+=2){
        cin >> tmp;
        C[i] = tmp;
        C[i+1] = tmp;
    }
    for(int i = 0; i < 2*H; ++i){
        cout << C[i] << endl;
    }
    return 0;
}




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

typedef long long LL;

int N;
int XYD[100001][3];

LL calc_area(LL n) {
  const int tbl[][2] = {
    {1, 0}, {-1, 0}, {0, 1}, {0, -1},
  };
  LL min_x, min_y, max_x, max_y;
  min_x = min_y = (LL)1e9;
  max_x = max_y = (LL)-1e9;
  
  for (int i = 0; i < N; ++i) {
    // printf("%lf %lf %lf %lf\n", max_x, min_x, max_y, min_y);
    // printf("%d %d\n", tbl[XYD[i][2]][0], tbl[XYD[i][2]][1]);
    LL x = XYD[i][0] * 2;
    LL y = XYD[i][1] * 2;
    x += n * tbl[XYD[i][2]][0];
    y += n * tbl[XYD[i][2]][1];
    if (x < min_x)
      min_x = x;
    if (x > max_x)
      max_x = x;
    if (y < min_y)
      min_y = y;
    if (y > max_y)
      max_y = y;
  }
  return (max_x - min_x) * (max_y - min_y);
}

int main(void) {
  scanf("%d", &N);
  for (int i = 0; i < N; ++i) {
    int x, y, z;
    char d;
    scanf("%d %d %c", &x, &y, &d);
    XYD[i][0] = x;
    XYD[i][1] = y;
    switch (d) {
    case 'R':
      XYD[i][2] = 0;
      break;
    case 'L':
      XYD[i][2] = 1;
      break;
    case 'U':
      XYD[i][2] = 2;
      break;
    default:
      XYD[i][2] = 3;
      break;
    }
  }

  LL l = 0;
  LL r = (LL)1e9;

  for (int i = 0; i < 100; ++i) {
    if (calc_area((l * 2 + r) / 3) < calc_area((l + r * 2) / 3))
      r = (l + r * 2) / 3;
    else
      l = (l * 2 + r) / 3;
  }
  LL c = (l + r) / 2;
  // printf("%lf\n", c);
  printf("%lf\n", (double)calc_area(c) / 4);

  return 0;
}


Measured memory_bytes: 1280
#include <bits/stdc++.h>
using namespace std;
void YesNo(bool);
void YESNO(bool);


int main(){
    vector<int>x(3);
    for (int i = 0; i < 3; i++) {
        cin >> x.at(i);
    }
    sort(x.begin(), x.end());
    cout << x.at(0) * x.at(1) / 2 << endl;
    
}


void YesNo(bool x){
    if (x) {
        cout << "Yes" << endl;
    }else{
        cout << "No" << endl;
    }
    
}

void YESNO(bool x){
    if (x) {
        cout << "YES" << endl;
    }else{
        cout << "NO" << endl;
    }
    
}


Measured memory_bytes: 256