akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;

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

  map<char, int> counter;

  bool yes = true;

  for(int i=0;i<s.size();i++) {
    counter[s[i]]++;
    if(counter[s[i]] == 2) {
      yes = false;
      break;
    }
  }

  if(yes) {
    cout << "yes" << endl;
  } else {
    cout << "no" << endl;
  }
}

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

int main() {
  int n;
  cin >> n;
  vector<int> h(n);
  for (auto &e : h) cin >> e;
  int r = 0, m = 0;
  for (auto e : h) {
    if (m <= e) {
      m = e;
      r++;
    }
  }
  cout << r << endl;
}


Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<set>
#include<map>
#include<queue>
#include<cmath>
#define REP(i,a) for (int i = 0;i < (a);++i)
#define FOR(i,a,b) for (int i = (a);i < (b); ++i)
#define FORR(i,a,b) for (int i = (a);i >= (b); --i)
#define ALL(obj) (obj).begin(),(obj).end()
#define SORT(list) sort(ALL((list)));
#define MOD 1000000007
using namespace std;
using ll = long long;
int main(){
    int n,m,c;
    cin >>n >> m >> c;
    vector<int>b(m);
    REP(i,m)cin >> b[i];
    int a[n][m];
    REP(i,n)REP(j,m)cin >> a[i][j];
    ll answer = 0;
    REP(i,n){
        ll count = 0;
        REP(j,m){
            count+=a[i][j]*b[j];
        }
        if(count+c>0)answer++;
    }
    cout << answer << endl;
    return 0;
}

Measured memory_bytes: 3592
#include<bits/stdc++.h>
 
using namespace std;
 
#define FOR(i, x, y) for(int i = (x); i < (y); ++i)
#define REP(i, x, y) for(int i = (x); i <= (y); ++i)
#define PB push_back
#define MP make_pair
#define PH push
#define fst first
#define snd second
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ldb;
typedef pair<int, int> pii;
 
const int maxn = 55;
const int base = maxn * maxn * maxn;
const ll INF = 0x3f3f3f3f3f3f3f3f;
 
class Item{
public:
	int v, id, lim;
	ll w, cnt;
	inline bool operator < (const Item &oth)const{ return MP(v * oth.w, v) > MP(oth.v * w, oth.v); } 
}dat[maxn];
 
int n, x, d;
int sz[maxn], a[maxn];
ll ans = 0;
ll dp[maxn][base];
int f[maxn][base];
ll sum[maxn];
vector<int> g[maxn];
 
inline int _(int x){ return x + base; }
 
inline void dfs(int u){
	FOR(i, 0, g[u].size()){
		int v = g[u][i];
		dfs(v);
		sz[u] += sz[v];
		sum[u] += sum[v];
	}
	++sz[u];
	sum[u] += a[u];
	return;
}
 
inline void umin(ll &x, ll y){ x = min(x, y); }
inline void umax(ll &x, ll y){ x = max(x, y); }
 
int main(){
	scanf("%d%d%d%d", &n, &x, &d, a + 0);
	
	FOR(i, 1, n){
		int p; scanf("%d%d", a + i, &p); --p;
		g[p].PB(i);
	}
	
	dfs(0);
	
	FOR(i, 0, n)
		dat[i].v = sz[i], dat[i].w = sum[i], dat[i].id = i, dat[i].lim = (i ? d : INF);
	sort(dat, dat + n);

	memset(dp, 0x3f, sizeof(dp));
//	memset(f, 0x3f, sizeof(f));
	dp[0][0] = 0;
	FOR(i, 0, n) REP(j, 0, 50 * 50 * 50) if(dp[i][j] != 0x3f3f3f3f){
		REP(k, 0, min(dat[i].lim, 50)) if(j + k * dat[i].v < base && (dp[i + 1][j + k * dat[i].v] > dp[i][j] + k * dat[i].w || dp[i + 1][j + k * dat[i].v] == dp[i][j] + k * dat[i].w && f[i + 1][j + k * dat[i].v] < k)){
			dp[i + 1][j + k * dat[i].v] = dp[i][j] + k * dat[i].w;
			f[i + 1][j + k * dat[i].v] = k;
		}
	}
	
	REP(j, 0, 50 * 50 * 50) if(x - dp[n][j] >= 0){
		FOR(i, 0, n)
			dat[i].cnt = 0;
		for(int i = n, j_ = j; i >= 0; --i){
			dat[i - 1].cnt = dat[i - 1].lim - f[i][j_]; 
			j_ -= f[i][j_] * dat[i - 1].v;
		}
		int nx = x - dp[n][j];
		ll res = 0;
		FOR(i, 0, n){
			dat[i].cnt = min(dat[i].cnt, nx / dat[i].w);
			res += dat[i].cnt * dat[i].v;
			nx -= dat[i].cnt * dat[i].w;
		}
		res += j;
		ans = max(ans, res);
	}
	printf("%lld\n", ans);
	return 0;
}

Measured memory_bytes: 83860
#include<stdio.h>
#include<stdlib.h>
int main(){
    int a,s,i,j;
    int *retu;
    
    scanf("%d",&a);
    retu=(int *)malloc(a * sizeof(int));
    for(i=0;i<a;i++){
        scanf("%d",&retu[i]);
    }
    for(i=0;i<a;i++){
        s=retu[i];
        j=i-1;
        while(retu[j]>s && j>=0){
            retu[j+1]=retu[j];
            j--;
        }
	retu[j+1]=s;
	for(j=0;j<a;j++){
        printf("%d",retu[j]);
	if(j!=a-1)printf(" ");}
	printf("\n");
    }
}



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

const int N = 100010;

int a[N];

int main(){
    int n;
    scanf("%d", &n);
    std::map <int, int> map;
    for (int i = 0; i < n; ++ i){
        scanf("%d", &a[i]);
        ++ map[a[i]];
    }
    if (int(map.size()) == 1){
        if (map.begin() -> first == 0){
            puts("Yes");
            return 0;
        }
    }
    if (int(map.size()) == 2){
        if (map.begin() -> first == 0 && map.begin() -> second * 2 == std::prev(map.end()) -> second){
            puts("Yes");
            return 0;
        }
    }
    if (int(map.size()) != 3){
        puts("No");
        return 0;
    }
    std::vector <std::pair <int, int>> vec;
    for (auto u : map){
        vec.push_back(u);
    }
    if ((vec[0].first ^ vec[1].first ^ vec[2].first) != 0){
        puts("No");
        return 0;
    }
    if (vec[0].second != vec[1].second || vec[1].second != vec[2].second){
        puts("No");
        return 0;
    }
    puts("Yes");
    return 0;
}


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

int gcd (int a, int b) {
    if (b == 0) return a;
    return gcd(b, a%b);
}

int main () {
    int n; cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++) cin >> a[i];
  
    int ans = a[0];
    for (int i = 1; i < n; i++) {
        ans = gcd(ans, a[i]);
    }
    
    cout << ans << endl;
}


Measured memory_bytes: 640
import java.io.*;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.Deque;
import java.util.HashMap;
import java.util.List;
import java.util.NoSuchElementException;
import java.util.PriorityQueue;
import java.util.Scanner;
public class Main {
	public static void main(String[] args) {
		
		FastScanner sc = new FastScanner();
		PrintWriter out = new PrintWriter(System.out);
		
		int n = sc.nextInt();
		for(int i = 0; i < n; i++) {
			double xa = sc.nextDouble();
			double ya = sc.nextDouble();
			double ra = sc.nextDouble();
			double xb = sc.nextDouble();
			double yb = sc.nextDouble();
			double rb = sc.nextDouble();
			
			double d = Math.sqrt((xb - xa)*(xb-xa) + (yb-ya)*(yb - ya));
			int ans = 0;
			if(ra - rb > d) {
				ans = 2;
			}
			else if(rb - ra > d) {
				ans = -2;
			}
			else if(ra + rb >= d) {
				ans = 1;
			}
			out.println(ans);
		}
		out.flush();
	}
}
		
//------------------------------//
//-----------//
class FastScanner {
    private final InputStream in = System.in;
    private final byte[] buffer = new byte[1024];
    private int ptr = 0;
    private int buflen = 0;
    private boolean hasNextByte() {
        if (ptr < buflen) {
            return true;
        }else{
            ptr = 0;
            try {
                buflen = in.read(buffer);
            } catch (IOException e) {
                e.printStackTrace();
            }
            if (buflen <= 0) {
                return false;
            }
        }
        return true;
    }
    private int readByte() { if (hasNextByte()) return buffer[ptr++]; else return -1;}
    private static boolean isPrintableChar(int c) { return 33 <= c && c <= 126;}
    private void skipUnprintable() { while(hasNextByte() && !isPrintableChar(buffer[ptr])) ptr++;}
    public boolean hasNext() { skipUnprintable(); return hasNextByte();}
    public String next() {
        if (!hasNext()) throw new NoSuchElementException();
        StringBuilder sb = new StringBuilder();
        int b = readByte();
        while(isPrintableChar(b)) {
            sb.appendCodePoint(b);
            b = readByte();
        }
        return sb.toString();
    }
    public long nextLong() {
        if (!hasNext()) throw new NoSuchElementException();
        long n = 0;
        boolean minus = false;
        int b = readByte();
        if (b == '-') {
            minus = true;
            b = readByte();
        }
        if (b < '0' || '9' < b) {
            throw new NumberFormatException();
        }
        while(true){
            if ('0' <= b && b <= '9') {
                n *= 10;
                n += b - '0';
            }else if(b == -1 || !isPrintableChar(b)){
                return minus ? -n : n;
            }else{
                throw new NumberFormatException();
            }
            b = readByte();
        }
    }
    
    public int nextInt() {
    	return (int)nextLong();
    }
    
    public double nextDouble() {
    	return Double.parseDouble(next());
    }
    

}

Measured memory_bytes: 16932
#include <bits/stdc++.h>
#define rep(i, a, n) for(int i = a; i < n; i++)
#define REP(i, n) rep(i, 0, n)
#define int long long
using namespace std;
typedef pair<int, int> P;
const int mod = 1000000007;
const int INF = 1e18;

vector<int> G[2010];
int ans[2010];

signed main(){
	cin.tie(nullptr);
	ios::sync_with_stdio(false);
	int n, x, y;
	cin >> n >> x >> y;
	x--; y--;
	REP(i, n - 1){
		G[i].push_back(i + 1);
		G[i + 1].push_back(i);
	}
	G[x].push_back(y);
	G[y].push_back(x);
	REP(i, n){
		vector<int> d(n, -1);
		d[i] = 0;
		queue<int> q;
		q.push(i);
		while(q.size()){
			int v = q.front(); q.pop();
			for(auto u : G[v]){
				if(d[u] != -1) continue;
				d[u] = d[v] + 1;
				ans[d[u]]++;
				q.push(u);
			}
		}
	}
	rep(i, 1, n){
		cout << ans[i] / 2 << endl;
	}
}

Measured memory_bytes: 512
from operator import mul
from functools import reduce

def cmb(n,r):
    r = min(n-r,r)
    if r == 0: return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1,r + 1))
    return over // under

N, K = map(int, input().split())
for i in range(1, K+1):
    if i > N-K+1:
        print(0)
    else:
        print(cmb(N-K+1, i) * cmb(K-1, i-1) % (10**9 + 7))


Measured memory_bytes: 3944
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <iostream>
#include <map>
#include <queue>
#include <string>

using namespace std;

void solve(int N, vector<long long> A) {
  vector<long long> X(N + 1);
  long long S = 0;
  long long a = 0;
  for (int i = 0; i < N; i++) {
    S += A[i];
    if ((i + 1) % 2 == 0) {
      a += A[i];
    }
  }
  X[0] = S - 2 * a;
  for (int i = 0; i < N; i++) {
    printf("%lld ", X[i]);
    X[i + 1] = 2 * A[i] - X[i];
  }
  printf("\n");
}

int main() {
  int N;
  cin >> N;
  vector<long long> A(N);
  for (int i = 0; i < N; i++) {
    cin >> A[i];
  }
  solve(N, A);
  return 0;
}

Measured memory_bytes: 3712
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define rep(i,l,r) for(ll i=(l);i<(r);i++)
int main(void){
    int n,k,a=1;
    cin>>n>>k;
    rep(i,0,n)a=min(a*2,a+k);
    cout<<(a);
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
constexpr int SQRT = 40000;
bool isprime[SQRT];
int main()
{
    int N;
    cin >> N;
    cout << N << ":";
    fill(isprime, isprime + SQRT, true);
    for (int i = 2; i < SQRT; i++) {
        if (isprime[i]) {
            while (N % i == 0) {
                cout << " " << i;
                N /= i;
            }
            for (int j = 2; i * j < SQRT; j++) {
                isprime[i * j] = false;
            }
        }
    }
    if (N > 1) {
        cout << " " << N;
    }
    cout << endl;
    return 0;
}



Measured memory_bytes: 3116
#include <bits/stdc++.h>
using namespace std;
int main(){
  string S,T;
  cin>>S>>T;
  int L=S.size();
  for(int i=0;i<L;i++){
    string s;
    for(int j=0;j<L;j++){
      s=s+S[(i+j>=L?i+j-L:i+j)];
    }
    if(s==T){
      cout<<"Yes"<<endl;
      return 0;
    }
  }
  cout<<"No"<<endl;
  return 0;
}

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

using vi = vector<int>;
using vvi = vector<vi>;
using vvvi = vector<vvi>;
using ll = long long;
using vll = vector<ll>;
using vvll = vector<vll>;
using vvvll = vector<vvll>;
using ull = unsigned long long;
using vb = vector<bool>;
using vvb = vector<vb>;
using vd = vector<double>;
using vvd = vector<vd>;
using vs = vector<string>;
using vvs = vector<vs>;
using vc = vector<char>;
using vvc = vector<vc>;
using ii = pair<int,int>;
using vii = vector<ii>;
using vvii = vector<vii>;
using dd = pair<double, double>;
using vdd = vector<dd>;
using vvdd = vector<vdd>;
using Mii = map<int,int>;
using vMii = vector<Mii>;

#define fi first
#define se second
#define INF INT_MAX
#define mod(a,m) (a%m+m)%m
#define PB push_back
#define MP make_pair

const int MOD = 1e9 + 7;

vvi memo;
vvb grid;

int dp(int y, int x) {
	if(y == -1 or x == -1) return 0;
	int& ans = memo[y][x];
	if(ans != -1) return ans;
	if(y == 0 and x == 0) return ans = 1;
	if(not grid[y][x]) return ans = 0;
	return ans = (dp(y-1, x) + dp(y, x-1)) % MOD;
}

int main(){
//	cout.setf(ios::fixed);
//	cout.precision(4);
	int h, w;
	while (cin >> h >> w) {
		memo = vvi(h, vi(w, -1));
		grid = vvb(h, vb(w, true));
		for (int i = 0; i < h; ++i) {
			string s;
			cin >> s;
			for (int j = 0; j < w; ++j) {
				if(s[j] == '#') grid[i][j] = false;
			}
		}
		cout << dp(h-1, w-1) << '\n';
	}
}




Measured memory_bytes: 4480
// https://atcoder.jp/contests/abc170/tasks/abc170_d
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define REP(i, n) FOR(i, 0, n)
#define FOR(i, s, n) for (int i = (s), i##_len = (n); i < i##_len; ++i)
#define ALL(obj) (obj).begin(), (obj).end()
#define ALLR(obj) (obj).rbegin(), (obj).rend()
#define CEIL(a, b) ((a - 1) / b + 1)

void solve() {
    int N;
    cin >> N;
    map<int, int> mp;
    REP(i, N) {
        int t;
        cin >> t;
        mp[t]++;
    }
    // 入力値の最大値
    int maxv = (*mp.rbegin()).first;
    // 入力値の2倍以上を保存
    bitset<1000001> bt;
    int ans = 0;
    for (auto &x : mp) {
        // 重複なし
        if (x.second == 1 && !bt[x.first]) {
            ans++;
        }
        for (int mul = 2; mul * x.first <= maxv; mul++) {
            bt.set(mul * x.first);
        }
    }
    cout << ans << endl;
}

signed main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    solve();
}


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

using namespace std;
#define rep(i, n) for(int i=0;i<n;i++)
#define REP(i, n) for(int i=1;i<=n;i++)
typedef long long ll;

int main() {
	int n;
	cin >> n;
	vector<int> v(n);
	rep(i, n) v[i] = i;
	vector<double> x(n);
	vector<double> y(n);
	rep(i, n) cin >> x[i] >> y[i];
	int count = 0;
	double dist = 0;
	do {
		rep(i,n-1){
			dist += sqrt((x[v[i+1]] - x[v[i]]) * (x[v[i+1]] - x[v[i]]) + (y[v[i+1]] - y[v[i]])*(y[v[i+1]] - y[v[i]]) );
		}
		count++;
	} while (next_permutation(v.begin(),v.end()));
	double ans = dist / count;
	printf("%.10f", ans);
	return 0;
}



Measured memory_bytes: 3808
function Main(input) {
    var values = input.split(" ");
    var A = parseInt(values[0], 10);
    var B = parseInt(values[1], 10);
    var H = parseInt(values[2], 10);
    var M = parseInt(values[3], 10);
    var hpos = [
        A * Math.cos( (H + M / 60) * 30 * (Math.PI / 180) ),
        A * Math.sin( (H + M / 60) * 30 * (Math.PI / 180) )
    ];
    var mpos = [
        B * Math.cos( M * 6 * (Math.PI / 180) ),
        B * Math.sin( M * 6 * (Math.PI / 180) )
    ]
    var dist = Math.sqrt(
        Math.pow(hpos[0] - mpos[0], 2) +
        Math.pow(hpos[1] - mpos[1], 2)
    );
    console.log('%d', dist);
}
Main(require("fs").readFileSync("/dev/stdin", "utf8"));


Measured memory_bytes: 29788
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#include <bits/stdc++.h>
using namespace std;
int main(){
  random_device rnd;
  mt19937 mt(rnd());
  int D;
  cin >> D;
  vector<int> c(26);
  for (int i = 0; i < 26; i++){
    cin >> c[i];
  }
  vector<vector<int>> s(D, vector<int>(26));
  for (int i = 0; i < D; i++){
    for (int j = 0; j < 26; j++){
      cin >> s[i][j];
    }
  }
  vector<int> last(26, -1);
  for (int i = 0; i < D; i++){
    int t = min(9, D - i);
    vector<vector<int>> L(26, vector<int>(t, 0));
    for (int j = 0; j < 26; j++){
      for (int k = 0; k < t; k++){
        L[j][k] = c[j] * (i + k - last[j]);
      }
    }
    int mx = 0;
    int a = 0;
    vector<int> best(t);
    vector<vector<int>> L2 = L;
    for (int j = 0; j < 30000; j++){
      vector<int> next(t, 0);
      if (j < 18000){
        for (int k = 0; k < t; k++){
          next[k] = mt() % 26;
        }
      } else if (j < 28000){
        next = best;
        for (int k = 0; k < 3; k++){
          int pos = mt() % t;
          int upd = mt() % 26;
          next[pos] = upd;
        }
      } else {
        next = best;
        for (int k = 0; k < 2; k++){
          int pos = mt() % t;
          int upd = mt() % 26;
          next[pos] = upd;
        }
      }
      int diff = 0;
      for (int k = 0; k < t; k++){
        diff += s[i + k][next[k]];
        for (int l = k; l < t; l++){
          diff += L2[next[k]][l] - (l - k) * c[next[k]];
          L2[next[k]][l] = (l - k) * c[next[k]];
        }
      }
      if (diff > mx){
        mx = diff;
        best = next;
      }
      for (int k = 0; k < t; k++){
        L2[next[k]] = L[next[k]];
      }
    }
    cout << best[0] + 1 << endl;
    last[best[0]] = i;
  }
}

Measured memory_bytes: 3704
import java.util.*;
public class Main {
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
        int K = sc.nextInt();
		String S = sc.next();
		
        for(int i=0;i<N;i++){
          if (i+1 == K){
            System.out.print(Character.toLowerCase(S.charAt(i)));
          }else{
            System.out.print(S.charAt(i));
          }
        }
	}
}

Measured memory_bytes: 22356
#include <iostream>
#include <algorithm>
#include <iomanip>
#include <string>
#include <vector>
#include <math.h>
#include <queue>
#include <deque>
#include <map>
const int MOD = 1e9+7;
typedef long long ll;
using namespace std;


int main(){
	int n, m, temp;
	cin >> n >> m;
	vector<bool> broken(n+1);
	vector<ll> dp(n+1);
	for (int i = 0; i < m; i++){
		cin >> temp;
		broken[temp] = true;
	}
	dp[0] = 1;
	if (!broken[1]) dp[1] = 1;
	for (int i = 2; i <= n; i++){
		if (!broken[i]){
			dp[i] = dp[i-1] + dp[i-2];
			dp[i] %= MOD;
		}
	}
	cout << dp[n] << endl;
	return 0;
}


Measured memory_bytes: 1024
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0; i<(n) ;i++)
#define pb push_back
#define all(v) (v).begin(),(v).end()
#define fi first
#define se second
using ll=long long;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
#define MOD  1000000007
int dx[4]={0,0,-1,1},dy[4]={1,-1,0,0};


int main(int argc, char const *argv[]) {
  int h,w,cnt=0;
  std::cin >> h >> w;
  char a[10][10];
  rep(i,h){
    rep(j,w){
      std::cin >> a[i][j];
      if(a[i][j]=='#') cnt++;
    }
  }
  if(cnt==h+w-1) std::cout << "Possible" << '\n';
  else std::cout << "Impossible" << '\n';

  return 0;
}


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

int main() {
    long N,M;
    cin>>N>>M;
    
    vector<long> x(M),y(M),num(N);
    vector<bool> pos(N);
    
    for(int i=0;i<M;i++){
        cin>>x.at(i)>>y.at(i);
    }
    
    
    for(int i=0;i<N;i++){
        num.at(i)=1;
        pos.at(i)=(i==0);
    }
    //cout<<pos.at(0)<<endl;
    
    for(int i=0;i<M;i++){
        num.at(x.at(i)-1)--;
        num.at(y.at(i)-1)++;
        
        pos.at(y.at(i)-1)=(pos.at(x.at(i)-1) || (pos.at(y.at(i)-1)));
        pos.at(x.at(i)-1)=(pos.at(x.at(i)-1) && num.at(x.at(i)-1)>0);
    }
    
    long ans=0;
    for(int i=0;i<N;i++){
        //cout<<pos.at(i)<<endl;
        if(pos.at(i)) ans++;
    }
    
    cout<<ans<<endl;
}

Measured memory_bytes: 2560
s = sorted(input())
t = sorted(input())

if s[0] < t[-1]:
  print("Yes")
elif s[0] > t[-1]:
  print("No")
else:
  if s == t:
    print("No")
  elif "".join(s) in "".join(t):
    print("Yes")
  else:
    print("No")

Measured memory_bytes: 3060
import Control.Applicative
import Data.Function
import Control.Monad
import Data.List
import Data.Char
import Text.Printf

sd :: Double -> [Double] -> Double
sd n s = sqrt $ (sum $ map ((^2) . subtract m) s) / n
    where m = sum s / n


main :: IO ()
main = fix $ \loop -> do
    n <- readLn
    unless (n == 0) $ do
        s <- map read . words <$> getLine
        printf "%.10f\n" $ sd n s
        loop


Measured memory_bytes: 5024
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
string num;
int k[10005];
int d;
ll dp[10005][105][2];
ll MOD = 1e9 + 7;
ll solve(int pos, int sum, int f) {
  if (dp[pos][sum][f] != -1)
    return dp[pos][sum][f];
  if (pos == num.size())
    return dp[pos][sum][f] = (sum == 0);
  ll nsum = 0, up = (f ? k[pos] : 9);
  for (int i = 0; i <= up; i++) {
    nsum += solve(pos + 1, (sum + i) % d, f && (i == up));
    nsum %= MOD;
  }
  return dp[pos][sum][f] = nsum;
}
int main() {
  cin >> num >> d;
  for (int i = 0; i < num.size(); i++) {
    k[i] = num[i] - '0';
  }
  memset(dp, -1, sizeof dp);
  cout << (solve(0, 0, 1) - 1 + MOD) % MOD << endl;
}

Measured memory_bytes: 17664
/*suri_kumkaran*/

#include <bits/stdc++.h>

using namespace std;

#define UB upper_bound
#define LB lower_bound
#define BS binary_search
#define MP make_pair
#define EB emplace_back
#define endl "\n"
#define PI 3.1415926535897932384626433832795
#define MOD 1000000007
#define F first
#define S second
#define ALL(a) (a).begin(),(a).end()
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define int long long

typedef long long int64;
typedef vector<int> VI64;
typedef vector<pair<int,int>> VII64;
typedef vector<string> VS;
typedef vector<vector<int>> VVI;

int n,m,k,ans;
int dp[12][1005];

void suri(int idx,VI64 v)
{
	if(idx==n)
	{
		v.EB(idx);
		suri(idx+1,v);
		return;
	}
    if(idx==n+1)
    {
        int i;
        int cuts=v.size()-1;
        int precut=0;
        
        for(i=1;i<=m;i++)
        {
            int stj=precut+1;
            int enj=i;
            int pre=0;
            int mx=0;
          	for(auto x:v)
          	{
          		int sti=pre+1;
            	int eni=x;
            	int cnt=dp[eni][enj]-dp[eni][stj-1]-dp[sti-1][enj]+dp[sti-1][stj-1];
                mx=max(mx,cnt);
            	pre=x;
          	}
          	if(mx>k)
            {
                if(enj==stj)
                    return;
                else
                {
                    cuts++;
                    precut=i-1;
                }
            }
        }

        int stj=precut+1;
        int enj=m;
        int pre=0;
        int mx=0;
      	for(auto x:v)
      	{
      		int sti=pre+1;
        	int eni=x;
        	int cnt=dp[eni][enj]-dp[eni][stj-1]-dp[sti-1][enj]+dp[sti-1][stj-1];
            mx=max(mx,cnt);
        	pre=x;
      	}
      	if(mx>k)
        {
            return;
        }
        ans=min(ans,cuts);

        return;
    }
    suri(idx+1,v);
    v.EB(idx);
    suri(idx+1,v);
}

int32_t main()
{
    IOS;
    int T=1;
    //cin>>T;
    while(T--)
    {
        int i,j;
        cin>>n>>m>>k;
        vector<string> s(n);
        for(i=0;i<n;i++)
        {
            cin>>s[i];
        }
        ans=1e15;
        for(i=1;i<=n;i++)
        {
            for(j=1;j<=m;j++)
            {
                dp[i][j]=dp[i-1][j]+dp[i][j-1]-dp[i-1][j-1];
                if(s[i-1][j-1]=='1')
                    dp[i][j]++;
            }
        }

        VI64 v; 
        suri(1,v);
        cout<<ans;
    }

    return 0;
}

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

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

#define rep(i, n) for(int i = 0; i < (n); i++)
#define repto(i, n) for(int i = 0; i <= (n); i++)
#define all(c) (c).begin, (c).end()
#define uniq(c) c.erase(unique(all(c)), (c).end())
#define _1 first
#define _2 second
#define pb push_back
#define INF 1145141919
#define MOD 1000000007
#define DEBUG(x) cout << #x << ": " << x << endl;
template<typename T> T gcd(T a, T b) { if (b == 0) return a; return gcd(b, a % b); }

map<ll, int> prime_factor(ll n) {
  map<ll, int> res;
  for (ll i = 2; i * i <= n; i++) {
    while(n % i == 0) {
      res[i]++;
      n /= i;
    }
  }
  if (n != 1)
    res[n] = 1;
  return res;
}

int main() {
  ll A, B;
  map<ll, int> p;
  int ans = 0;
  cin >> A >> B;
  ll n = gcd(A, B);
  p = prime_factor(n);
  for (auto i = p.begin(); i != p.end(); i++) {
    ans++;
  }
  cout << ans+1 << endl;
}


Measured memory_bytes: 256
/*---------------------------------
 *File name: A.cpp
 *Creation date: 2020-07-05 19:35
 *Link: 
 *-------------------------------*/
#include<set>
#include<map>
#include<cmath>
#include<queue>
#include<vector>
#include<cstdio>
#include<string>
#include<cstring>
#include<iostream>
#include<algorithm>
#define fi first
#define se second
#define pb push_back
#define LL long long
#define PII pair<int, int>
#define Pque priority_queue 
using namespace std;
const int maxn = 1e5 + 5;
const int inf = 0x3f3f3f3f;
const LL mod = 1e9 + 7;
const double EPS = 1e-8;

int main(){
	map<string, int> mp;
	int n;
	scanf("%d", &n);
	for(int i = 1; i <= n; ++i){
		string s;
		cin >> s;
		mp[s]++;
	}
	printf("AC x %d\n", mp["AC"]);
	printf("WA x %d\n", mp["WA"]);
	printf("TLE x %d\n", mp["TLE"]);
	printf("RE x %d\n", mp["RE"]);
	return 0;
}

Measured memory_bytes: 3296
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<stack>
#include<queue>
#include<map>
#include<functional>
#include<math.h>
using namespace std;
#define rep(i,n) for(ll i=0;i<(n);i++)
#define pf(n) printf("%lld\n",n)
typedef long long ll;
typedef pair<ll, ll> p;
const int INF = 1001001001;
const double PI = acos(-1);

int main() {
	int n, m;
	cin >> n >> m;
	vector<int> l(m);
	vector<int> r(m);
	rep(i, m) cin >> l[i] >> r[i];

	int left = 0;
	rep(i, m) {
		left = max(left, l[i]);
	}
	int right = 100100;
	rep(i, m) {
		right = min(right, r[i]);
	}
	int ans = 0;
	for (int i = left; i <= right; i++) {
		if (i > n) break;
		ans++;
	}
	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 3972
#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;
const int MAX = 1001;

int V,d;
int v[MAX];

void fibo(){

  v[0] = 1,v[1] = 2;
  for(int i = 2 ; i < MAX ; i++){
    v[i] = (v[i-1]+v[i-2])%MAX;
  }
}

int main(){
  
  while(cin >> V >> d){
    fibo();
    sort(v,v+V+1);
    int cnt = 1;
    for(int i = 2; i <= V ; i++){
      if(v[i-1] + d <= v[i]) cnt++;
    }

    cout << cnt << endl;
  }

  return 0;
}

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

int main(){
    int a,b;
    cin>>a;
    cin>>b;
    if(a<b){
        cout<<"a < b"<<endl;
    }
    else if(a>b){
        cout<<"a > b"<<endl;
    }
    else{
        cout<<"a == b"<<endl;
    }
    return 0;
}


Measured memory_bytes: 3112
#!/usr/bin/env python
# coding: utf-8

import fractions

def ri():
    return int(input())

def rl():
    return list(input().split())

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

def main():
    n = ri()
    la = rli()
    s = sum(la)
    lr = []
    lr.append(s-sum(2*la[i] for i in range(len(la)) if i % 2 == 1))
    for i in range(len(la)-1):
        r_bef = lr[-1]
        lr.append(2*la[i]-lr[-1])
    print(" ".join(map(str, lr)))



if __name__ == '__main__':
    main()


Measured memory_bytes: 21132
#include <cstdio>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <cstring>
#include <string>
#include <cmath>
#include <cstdlib>
#include <iostream>

using namespace std;

#define MOD @
#define ADD(X,Y) ((X) = ((X) + (Y)) % MOD)
typedef long long i64; typedef vector<int> ivec; typedef vector<string> svec;

int T;
int N, D;

int main()
{
	scanf("%d", &T);
	for (; T--;) {
		scanf("%d%d", &N, &D);
		int ret = 0;
		if (N % 2 == 1) {
			ret = (N - 1) * 127 + D;
		} else {
			ret = N * 127 - D;
		}
		printf("%d\n", ret);
	}
	return 0;
}


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

using ll = long long;
using ld = long double;
using P = pair<int, int>;
using vi = vector<int>;
using vl = vector<ll>;
ld EPS = 1e-12;
int INF = numeric_limits<int>::max() / 2;
int MOD = 1e9 + 7;
#define rep(i,n) for(int i = 0; i < n; i++)
#define all(obj) (obj).begin(), (obj).end()
template<class T>
int print(T& x){ cout << x << '\n'; return 0;}
#define debug(x) cerr << #x << ": " << x << '\n'

int n, m;
int match[] = {0,2,5,5,4,5,6,3,7,6};
vi usable;
int maxdigit;
int min_use = 10;
int min_use_ind;
vi dp;

void dfs(int rest){
  if(rest == 0) return;
  rep(i,m){
    if(rest - match[usable[i]] < 0) continue;
    if(dp[rest]-1 == dp[rest-match[usable[i]]]){
      cout << usable[i];
      dfs(rest-match[usable[i]]);
      break;
    }
  }
}

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

  cin >> n >> m;
  usable.resize(m);
  rep(i, m) cin >> usable[i];
  sort(usable.begin(), usable.end(), greater<int>());
  dp.resize(n+1);

  dp[0] = 0;
  for(int i = 1; i < n+1; i++) dp[i] = -1;

  for(int i = 2; i < n+1; i++){
    rep(j,m){
      if(i - match[usable[j]] >= 0){
        if(dp[i-match[usable[j]]] > -1 ){
          dp[i] = max(dp[i], dp[i-match[usable[j]]] + 1);
        }
      }
    }
  }

  rep(i, n+1){
    //cout << "dp[" << i << "]: " << dp[i] << endl;
  }

  dfs(n);
  
  cout << '\n';
  return 0;
}


Measured memory_bytes: 256
import sys
stdin=sys.stdin

ns = lambda:stdin.readline().rstrip()
ni = lambda:int(stdin.readline().rstrip())
nm = lambda:map(int,stdin.readline().split())
nl = lambda:list(map(int,stdin.readline().split()))

N,M,X=nm()
C=[0]*N
A=[[0]*M for i in range(N)]
for i in range(N):
    tmp=nl()
    C[i]=tmp[0]
    A[i][:]=tmp[1:]

r=[[0]*M for i in range(2**N)]
cm=[0]*(2**N)
for i in range(2**N):
    sum_m=0
    for j in range(N):
        if((i>>j) & 1):
            sum_m+=C[j]
            for k in range(M):
                r[i][k]+=A[j][k]
    cm[i]=sum_m

inds=list(range(2**N))
inds.sort(key=lambda x: cm[x])

ind=0
while(ind<2**N):
    flag=True
    for i in range(M):
        if(r[inds[ind]][i]<X):
            flag=False
    if(flag==True):
        print(cm[inds[ind]])
        sys.exit(0)
    ind+=1

print(-1)
            

Measured memory_bytes: 11612
#include <stdio.h>
#include <cmath>
#include <algorithm>
#include <cfloat>
#include <stack>
#include <queue>
#include <vector>
#include <string>
#include <iostream>
typedef long long int ll;
typedef unsigned long long int ull;
#define BIG_NUM 2000000000
#define MOD 1000000007
#define EPS 0.000000001
using namespace std;

vector<int> G[100001];
int N;
int root;
int MAX_LOG_V = 17;
int POW[18];

int** parent;
int* depth;

void dfs(int node_id,int parent_id,int d){
	parent[0][node_id] = parent_id;
	depth[node_id] = d;
	for(int i = 0; i < G[node_id].size(); i++){
		if(G[node_id][i] != parent_id)dfs(G[node_id][i],node_id,d+1);
	}
}

void init(){

	dfs(root,-1,0);

	for(int k = 0; k + 1 < MAX_LOG_V; k++){
		for(int node_id = 0; node_id < N; node_id++){
			if(parent[k][node_id] < 0)parent[k+1][node_id] = -1;
			else{
				parent[k+1][node_id] = parent[k][parent[k][node_id]];
			}
		}
	}
}


int lca(int left,int right){

	if(depth[left] > depth[right])swap(left,right);

	for(int k = MAX_LOG_V-1; k >= 0; k--){
		if(depth[right]-depth[left] >= POW[k]){
			right = parent[k][right];
		}
	}

	if(left == right)return left;

	for(int k = MAX_LOG_V-1; k >= 0; k--){
		if(parent[k][left] != parent[k][right]){
			left = parent[k][left];
			right = parent[k][right];
		}
	}
	return parent[0][left];
}



int main(){

	for(int i = 0; i <= 17; i++)POW[i] = pow(2,i);

	scanf("%d",&N);

	int num,child;

	for(int i = 0; i < N; i++){
		scanf("%d",&num);
		for(int k = 0; k < num; k++){
			scanf("%d",&child);
			G[i].push_back(child);
		}
	}

	parent = new int*[MAX_LOG_V];
	for(int i = 0; i < MAX_LOG_V;i++)parent[i] = new int[N];
	depth = new int[N];
	root = 0;
	init();

	int Q;
	scanf("%d",&Q);

	int left,right;

	for(int i = 0; i < Q; i++){
		scanf("%d %d",&left,&right);
		printf("%d\n",lca(left,right));
	}

	return 0;
}

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

#ifdef LOCAL
#include "../../dump.hpp"
#else
#define dump(...)
#endif

#define rep(i,n) for(ll i=0,i##_cond=(n);i<i##_cond;++i)
#define FOR(i,a,b) for(ll i=(a),i##_cond=(b);i<i##_cond;++i)
#define ROF(i,a,b) for(ll i=(a)-1,i##_cond=(b);i>=i##_cond;--i)
#define all(a) (a).begin(),(a).end()
#define rall(a) (a).rbegin(),(a).rend() //sortで大きい順
#define UNIQUE(v) v.erase(unique(all(v)),v.end())
#define SUM(a) accumulate(all(a),0)
#define sz(x) ((ll)(x).size())
#define pb push_back
#define fst first
#define snd second
#define mp make_pair

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

const ll inf = 1ll<<62;
const ll mod = 1e9+7;

int main(){
#define int ll
  vi a(3); rep(i,3) cin >> a[i];
  sort(all(a));
  cout << a[2] - a[0] << endl;
}

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

int H, W;

char f(bool c, bool c2) {
	return (c && c2) ||(!c && !c2) ? '#' : '.';
}

int main(){
	while (cin >> H >> W && H != 0) {
		bool c = true, c2 = true;
		for (int i = 0; i < H; i++) {
				for (int j = 0; j < W; j++) {
					cout << f(c, c2);
					c2 = !c2;
				}
			c = !c;
			c2 = true;
			cout << endl;
		}
		cout << endl;
	}

	return 0;
}

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

int n, m, q;
vector<int> a, b, c, d;
int ans;

void dfs(vector<int> A) {
  if (A.size() == n+1) {
    int now = 0;
    rep(i,q) {
      if (A[b[i]] - A[a[i]] == c[i]) now += d[i];
    }
    ans = max(ans, now);
    return;
  }

  A.push_back(A.back());
  while (A.back() <= m) {
    dfs(A);
    A.back()++;
  }
}

int main() {
  cin >> n >> m >> q;
  a = b = c = d = vector<int>(q);
  rep(i,q) {
    cin >> a[i] >> b[i] >> c[i] >> d[i];
  }
  dfs(vector<int>(1,1));
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 3588
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N, M = MAP()

def indexs(l, x, default=-1):
    if x in l:
        return l.index(x)
    else:
        return -1

if M == 0:
	print(0, 0)
else:
	temp = [input().split() for _ in range(M)]
	temp.append([N+1, "WA"])
	temp.sort(key=lambda x:int(x[0]))
	temp = [list(x) for x in zip(*temp)]
	p, S = list(map(int, temp[0])), temp[1]

	index = 0
	AC = 0
	WC = 0
	a = []
	for i in range(M):
		if p[i]!=p[i+1]:
			a.append(indexs(S[index:i+1], "AC"))
			index = i+1
	index = 0
	for i in range(M):
		if p[i]!=p[i+1]:
			if a[index]>=0:
				AC += 1
				WC += a[index]
			index += 1	
	print(AC, WC)

Measured memory_bytes: 104024
using System;
using CompLib.Util;

public class Program
{
    public void Solve()
    {
        var sc = new Scanner();
        int a = sc.NextInt();
        int b = sc.NextInt();
        int c = sc.NextInt();
        int k = sc.NextInt();
        int t = 0;
        while (b <= a)
        {
            t++;
            b *= 2;
        }

        while (c <= b)
        {
            t++;
            c *= 2;
        }

        Console.WriteLine(t <= k?"Yes":"No");
    }

    public static void Main(string[] args) => new Program().Solve();
}

namespace CompLib.Util
{
    using System;
    using System.Linq;

    class Scanner
    {
        private string[] _line;
        private int _index;
        private const char Separator = ' ';

        public Scanner()
        {
            _line = new string[0];
            _index = 0;
        }

        public string Next()
        {
            while (_index >= _line.Length)
            {
                _line = Console.ReadLine().Split(Separator);
                _index = 0;
            }

            return _line[_index++];
        }

        public int NextInt() => int.Parse(Next());
        public long NextLong() => long.Parse(Next());
        public double NextDouble() => double.Parse(Next());
        public decimal NextDecimal() => decimal.Parse(Next());
        public char NextChar() => Next()[0];
        public char[] NextCharArray() => Next().ToCharArray();

        public string[] Array()
        {
            _line = Console.ReadLine().Split(Separator);
            _index = _line.Length;
            return _line;
        }

        public int[] IntArray() => Array().Select(int.Parse).ToArray();
        public long[] LongArray() => Array().Select(long.Parse).ToArray();
        public double[] DoubleArray() => Array().Select(double.Parse).ToArray();
        public decimal[] DecimalArray() => Array().Select(decimal.Parse).ToArray();
    }
}

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

int main()
{
	int n, d, x;
	cin >> n >> d >> x;
	int a, ans = x;
	for (int i = 0; i < n; ++i)
	{
		cin >> a;
		ans += d / a + (d % a != 0);
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 256
n = int(input())
A = list(map(int,input().split()))
dp = [[-float("INF")]*(n+1) for i in range(n+1)]
low = [-float("INF")]*(n+1)
m = 0
a,b = A[:2]
dp[a][b] = 0
dp[b][a] = 0
low[a] = 0
low[b] = 0
base = 0
for _ in range(1,n):
    a,b,c = A[3*_-1:3*_+2]
    q = []
    if a==b==c:
        base += 1
        continue
    m1 = m
    for j in range(3):
        q.append((a,b,max(m,dp[c][c]+1)))
        m1 = max(m1,dp[c][c]+1)
        for i in range(1,n+1):
            q.append((a,i,low[i]))
        if a==b:
            for i in range(1,n+1):
                q.append((c,i,dp[a][i]+1))
                m1 = max(m1,dp[a][i]+1)
        a,b,c = b,c,a
    for a,b,v in q:
        dp[a][b] = max(dp[a][b],v)
        dp[b][a] = max(dp[b][a],v)
        low[a] = max(low[a],v)  
        low[b] = max(low[b],v)      
    m = m1
print(max(m,dp[A[-1]][A[-1]]+1)+base)



Measured memory_bytes: 224536
//raja1999
#include <bits/stdc++.h>
#include <vector>
#include <set>
#include <map>
#include <string> 
#include <cstdio>
#include <cstdlib>
#include <climits>
#include <utility>
#include <algorithm>
#include <cmath>
#include <queue>
#include <stack>
#include <iomanip> 
//setbase - cout << setbase (16)a; cout << 100 << endl; Prints 64
//setfill -   cout << setfill ('x') << setw (5); cout << 77 <<endl;prints xxx77
//setprecision - cout << setprecision (14) << f << endl; Prints x.xxxx
//cout.precision(x)  cout<<fixed<<val;  // prints x digits after decimal in val

using namespace std;
#define f(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) f(i,0,n)
#define fd(i,a,b) for(i=a;i>=b;i--)
#define pb push_back
#define mp make_pair
#define vi vector< int >
#define vl vector< ll >
#define ss second
#define ff first
#define ll long long
#define pii pair< int,int >
#define pll pair< ll,ll >
#define sz(a) a.size()
#define inf (1000*1000*1000+5)
#define all(a) a.begin(),a.end()
#define tri pair<int,pii>
#define vii vector<pii>
#define vll vector<pll>
#define viii vector<tri>
#define mod (1000*1000*1000+7)
#define pqueue priority_queue< int >
#define pdqueue priority_queue< int,vi ,greater< int > >

//std::ios::sync_with_stdio(false);
int main(){
	std::ios::sync_with_stdio(false);
	int a[5],i,ans;
	rep(i,3){
		cin>>a[i];
	}	
	sort(a,a+3);
	ans=a[2]*10+a[0]+a[1];
	cout<<ans<<endl;
} 
	

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

public class Main {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		int num = 20;
		while (true) {
			ArrayList<Integer> ary = new ArrayList<Integer>();
			num = sc.nextInt();

			if (num == 0) {
				// System.out.println();
				break;
			}
			for (int i = 0; i < num; i++) {
				int word = sc.nextInt();
				ary.add(word);
			}
			int min = ary.get(0);
			int max = ary.get(0);
			for (int i : ary) {
				if (i < min) {
					min = i;
				}
				if (i > max) {
					max = i;
				}
			}
			int index1 = ary.indexOf(min);
			ary.remove(index1);
			int index2 = ary.indexOf(max);
			ary.remove(index2);

			int sum = 0;
			for (int i : ary) {
				sum += i;
			}
			int ave = sum / ary.size();

			System.out.println(ave);
		}
		sc.close();
	}

}



Measured memory_bytes: 29112
unittest
{
	assert( [ "5 100 90 80", "98", "40", "30", "21", "80" ].solve == 23 );
	assert( [ "8 100 90 80", "100", "100", "90", "90", "90", "80", "80", "80" ].solve == 0 );
	assert( [ "8 1000 800 100", "300", "333", "400", "444", "500", "555", "600", "666" ].solve == 243 );
}



import core.bitop;
import std.algorithm;
import std.conv;
import std.format;
import std.math;
import std.range;
import std.stdio;

void main()
{
	stdin.byLineCopy.solve.writeln;
}

auto solve( Range )( Range input )
if( isInputRange!Range && is( ElementType!Range == string ) )
{
	auto n = 0L;
	auto a = 0L;
	auto b = 0L;
	auto c = 0L;
	input.front.formattedRead!"%s %s %s %s"( n, a, b, c );
	auto ls = new long[ n ];
	foreach( ref l; ls )
	{
		input.popFront;
		l = input.front.to!( long );
	}
	
	// 竹を合成したときの長さを計算
	auto ts = new long[ 1L << n ];
	foreach( i, ref t; ts )
	{
		foreach( j; 0L .. n )
		{
			if( i & ( 1L << j ) ) t += ls[ j ];
		}
	}
	
	// dp[ i本数 ][ 使った竹のbit集合 ] = 消費MP
	auto dp = new long[][]( 1 + 3, 1L << n );
	foreach( ref dpp; dp ) dpp[] = long.max;
	dp[ 0 ][ 0 ] = 0;
	foreach( i, x; [ a, b, c ] )
	{
		foreach( j; 0L .. dp[ i ].length.signed )
		{
			if( dp[ i ][ j ] == long.max ) continue;
			foreach( k; 1L .. dp[ i ].length.signed )
			{
				if( j & k ) continue;
				
				auto m = 10 * ( k._popcnt - 1 ) + abs( x - ts[ k ] );
				dp[ i + 1 ][ j | k ] = min( dp[ i + 1 ][ j | k ], dp[ i ][ j ] + m );
			}
		}
	}
	return dp[ $ - 1 ].reduce!min;
}


Measured memory_bytes: 2892
#include <stdio.h>
int main(){
  int a,b,c;
  scanf("%d %d",&a,&b);
  if(a>12)c=b;
  if((a>5)&&(a<13))c=b/2;
  if(a<6)c=0;
  printf("%d\n",c);
  return 0;
}

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

using namespace std;

#define rep(i,n) for(int i=0;i<(n);i++)
#define repa(i,a,n) for(int i=(a);i<(n);i++)
#define rrep(i,n) for(int i=n;i>=0;i--)
#define rrepa(i,a,n) for(int i=n;i>=(a);i--)
#define all(a) (a).begin(),(a).end()
#define MOD 1000000007
#define maxs(a,b) a=max(a,b)
#define mins(a,b) a=min(a,b)
#define vc vector

typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef pair<int,int> pi;

int main(){
   
    int n,k;cin>>n>>k;
    vi a(n),s(n+1);
    rep(i,n){
        cin>>a[i];
        a[i]--;
        s[i+1]=(s[i]+a[i])%k;

    }

    map<int,int> num;
    num[0]=1;
    ll ans=0;

    repa(i,1,n+1){
        if(i>=k)num[s[i-k]]--;
        ans+=num[s[i]];
        num[s[i]]++;
    }    

    cout<<ans<<endl;
    
    return 0;
}

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

class A
{
	static void Main()
	{
		var n = int.Parse(Console.ReadLine());
		var a = Console.ReadLine().Split().Select(int.Parse).GroupBy(x => x).Select(g => new { x = g.Key, c = g.Count() }).OrderBy(_ => _.c).ToArray();
		Console.WriteLine(a.Length == 1 && a[0].x == 0 || n % 3 == 0 && (a.Length == 2 && a[1].c == 2 * a[0].c && (a[0].x ^ a[1].x) == a[1].x || a.Length == 3 && a.All(_ => _.c == n / 3) && (a[0].x ^ a[1].x) == a[2].x) ? "Yes" : "No");
	}
}


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

int main(){
 ll n,W;
 cin>>n>>W;
 vector<ll> w(n);
 vector<ll> v(n);
 for(ll i=0;i<n;i++){
 	cin>>w[i]>>v[i];
 }
 vector<vector<ll>> dp(n,vector<ll>(1e5+5,0));
 
 dp[0][v[0]]=w[0];
 
 for(ll i=1;i<dp.size();i++){
 	for(ll j=1;j<100005;j++){
 		dp[i][j]=dp[i-1][j];
 		if(j-v[i]==0 && dp[i-1][j])
 			dp[i][j]=min(w[i],dp[i-1][j]);
 		else if(j-v[i]==0)
			dp[i][j]=w[i]; 	
 		if(j-v[i]>=0 && w[i]+dp[i-1][j-v[i]]<=W && dp[i-1][j-v[i]])
			if(dp[i][j]==0)
				dp[i][j]=w[i]+dp[i-1][j-v[i]];
			else
				dp[i][j]=min(dp[i][j],w[i]+dp[i-1][j-v[i]]);	 	
	}
 }
 
 ll maxj=0;
 
 for(ll j=1;j<1e5+5;j++){
 	if(dp[n-1][j]){
 		maxj=j;
	}
 }
 cout<<maxj<<endl;
 return 0;
}



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

ab = [list(map(int, input().split())) for _ in range(n)]

x = ab[0][0]
y = ab[0][1]
j = 1
flg = True
for i in range(1,n):
    xx = ab[i][0]
    yy = ab[i][1]
    j = max(x//xx,y//yy)
    while flg:
        if x> j*xx or y > j*yy:
            j +=1
        else:
            x = xx *j
            y = yy *j
            break

print(x+y)

Measured memory_bytes: 9208
#include <iostream>
#include <cstdio>
#include <cctype>
#define il inline
#define vd void
#define rg register
#define rep(i,x,y) for(rg int i=x;i<=y;++i)
#define drp(i,x,y) for(rg int i=x;i>=y;--i)
using namespace std;
const int Len=2333333;
char buf[Len],*p1=buf,*p2=buf,duf[Len],*q1=duf;
il char gc(); il int rd(); il vd pc(char c); il vd rt(int x); il vd flush();
int n,t;
int main(){
	n=rd();
	rep(i,1,n){
		int x=rd();
		if(x==t+1) ++t;
	}
	if(!t) rt(-1);
	else rt(n-t);
	return flush(),0;
}

il char gc(){return p1==p2&&(p2=(p1=buf)+fread(buf,1,Len,stdin),p1==p2)?-1:*p1++;}
il int rd(){char c;
	while(!isdigit(c=gc())&&c!='-');
	int f=c=='-'?c=gc(),1:0,x=c^48;
	while(isdigit(c=gc())) x=((x+(x<<2))<<1)+(c^48);
	return f?-x:x;
}
il vd pc(char c){q1==duf+Len&&fwrite(q1=duf,1,Len,stdout),*q1++=c;}
il vd rt(int x){x<0?pc('-'),x=-x:0,pc((x>=10?rt(x/10),x%10:x)+48);}
il vd flush(){fwrite(duf,1,q1-duf,stdout);}

Measured memory_bytes: 2304
n,x=map(int,input().split())
A=list(map(int,input().split()))
ans=float("INF")
dp=[[A[i]]*n for i in range(n)]
for l in range(n):
  a=A[l:]+A[:l]
  a=a[::-1]
  for i in range(n-1):
    dp[l][i+1]=min(dp[l][i],a[i])
for i in range(n):
  tmp=0
  for j in range(n):
    tmp+=dp[j][i]
  ans=min(tmp+x*i,ans)
print(ans)

Measured memory_bytes: 74200
#include <bits/stdc++.h>
using namespace std;
#define PII pair<int, int>
#define PLL pair<LL, LL>
#define VI vector<int>
#define VPII vector<PII>
#define LL long long
#define LD long double
#define f first
#define s second
#define MP make_pair
#define PB push_back
#define pb pop_back
#define ALL(c) (c).begin(), (c).end()
#define SIZ(c) (int)(c).size()
#define REP(i, n) for(int i = 0; i < (int)(n); ++i)
#define FOR(i, b, e) for(int i = (b); i <= (int)(e); ++i)
#define FORD(i, b, e) for(int i = (b); i >= (int)(e); --i)

#define Sim template<class n
Sim, class s> ostream & operator << (ostream &p, pair<n, s> x)
{return p << "<" << x.f << ", " << x.s << ">";}
Sim> auto operator << (ostream &p, n y) -> 
typename enable_if<!is_same<n, string>::value, decltype(y.begin(), p)>::type 
{int o = 0; p << "{"; for(auto c: y) {if(o++) p << ", "; p << c;} return p << "}";}
void dor() {cerr << endl;}
Sim, class...s> void dor(n p, s...y) {cerr << p << " "; dor(y...);}
Sim, class s> void mini(n &p, s y) {if(p>y) p = y;}
Sim, class s> void maxi(n &p, s y) {if(p<y) p = y;}
#ifdef DEB
#define debug(...) dor(__FUNCTION__, ":", __LINE__, ": ", __VA_ARGS__)
#else
#define debug(...)
#endif 

#define I(x) #x " = ", (x), " "
#define A(a, i) #a "[" #i " = ", i, "] = ", a[i], " "
const LL mod = 998244353;
const int M = 3003;

int n, x;
LL dp[M][2 * M], dp2[M][2 * M];
LL newt[M][M];

int main()
{
	//ios_base::sync_with_stdio(0);
	//cin.tie(NULL);
	FOR(i, 0, M - 1)
	{
		newt[i][0] = 1;
		FOR(j, 1, i)
		{
			if (i == 0)
			{
				break;
			}
			if (j > 0)
			{
				newt[i][j] += newt[i - 1][j - 1];
			}
			newt[i][j] += newt[i - 1][j];
			newt[i][j] %= mod;
		}
	}
	scanf("%d%d", &n, &x);
	LL res = 0;
	dp[0][0] = 1;
	dp2[0][0] = 1;
	FOR(i, 1, n)
	{
		FOR(j, 0, 2 * i)
		{
			dp[i][j] = dp[i - 1][j];
			if (j >= 1)
				dp[i][j] += dp[i - 1][j - 1];
			if (j >= 2)
				dp[i][j] += dp[i - 1][j - 2];
			dp[i][j] %= mod;
			if (j >= 1)
				dp2[i][j] += dp2[i - 1][j - 1];
			if (j >= 2)
				dp2[i][j] += dp2[i - 1][j - 2];
			dp2[i][j] %= mod;
		}
	}
	FOR(i, 0, 2 * n)
	{
		debug(i, i - 1, res);
		if (i < x)
		{
			res = (res + dp[n][i]) % mod;
			continue;
		}
		if (i == x)
		{
			continue;
		}
		int diff = i - x;
		if (diff % 2 == 0)
		{
			continue;
		}
		int boki = i - (x - 1);
		boki *= 2;
		if (boki >= i)
		{
			if (x % 2 == 1)
			{
				//res = (res + 1) % mod;
				res = (res + newt[n][i / 2]) % mod;
				debug("ololol", i, res, n, i / 2, newt[3][2]);
			}
			continue;
		}
		int l = n - boki / 2;
		FOR(j, 0, l)
		{
			res = (res + dp2[j][i - boki] * newt[n][boki / 2 + j]) % mod;
		}
	}
	printf("%lld\n", res);
	return 0;
}

Measured memory_bytes: 350848