akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <cstring>
#include <string>
#include <map>
#include <queue>
using namespace std;

class Edge
{
public:
	int src, dst, cst;
	Edge() {}
	Edge(int s, int d, int c)
		:src(s),dst(d),cst(c)
	{}
};

typedef vector<vector<Edge> > Graph;

class State
{
public:
	int node, gas, cst;
	State(int n, int g, int c)
		:node(n),gas(g),cst(c)
	{}

	bool operator<(const State& s) const
	{
		return cst>s.cst;
	}
};

int M,N,cap;
bool station[3005];
bool visited[3005][2005];

int solve(int S, int T, vector<Edge>& edges, int V)
{
	Graph graph(V);

	for(int i=0; i<edges.size(); i++){
		Edge e = edges[i];
		graph[e.src].push_back(Edge(e.src, e.dst, e.cst));
		graph[e.dst].push_back(Edge(e.dst, e.src, e.cst));
	}

	memset(visited, 0, sizeof(visited));

	priority_queue<State> q;
	q.push(State(S,cap*10,0));

	while(!q.empty()) {
		State s = q.top(); q.pop();
		if(s.node == T) return s.cst;

		if(visited[s.node][s.gas]) continue;
		visited[s.node][s.gas] = true;

		for(int i=0; i<graph[s.node].size(); i++)
		{
			Edge e = graph[s.node][i];

			if(e.cst > s.gas) continue;

			int ngas = (station[e.dst]?cap*10:s.gas-e.cst); 
			if(visited[e.dst][ngas]) continue;

			q.push(State(e.dst, ngas, s.cst + e.cst));
		}
	}

	
	return -1;
}

int main()
{
	while(cin >> N >> M >> cap, (M||N||cap)) {
		string s,t;
		cin >> s >> t;

		int id = 0;
		map<string, int> dic;

		if(!dic.count(s)) dic[s] = id++;
		if(!dic.count(t)) dic[t] = id++;
		
		vector<Edge> edges(N);

		for(int i=0; i<N; i++) {
			string a,b;
			int c;

			cin >> a >> b >> c;
			if(!dic.count(a)) dic[a] = id++;
			if(!dic.count(b)) dic[b] = id++;

			edges[i] = Edge(dic[a], dic[b], c);
		}

		memset(station, 0, sizeof(station));

		for(int i=0; i<M; i++) {
			string a;
			cin >> a;
			if(!dic.count(a)) dic[a] = id++;

			station[dic[a]] = true;
		}

		cout << solve(dic[s], dic[t], edges, dic.size()) << endl;
	}
}

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

const int N = 1e5 + 5;

vector<int> g[N];
int n;

static int dfs(int u, int far = -1) {
    int sg = 0;
    for (auto v: g[u]) if (v != far)
        sg^= dfs(v, u);
    return sg + 1; }

int main() {
#ifdef HOME
    freopen("dat.in", "r", stdin);
    freopen("dat.out", "w", stdout);
#endif
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    cin >> n;
    for (int a, b, i = 1; i < n; ++i) {
        cin >> a >> b;
        g[a].push_back(b);
        g[b].push_back(a); }

    cout << (dfs(1) > 1 ? "Alice" : "Bob") << endl;

    return 0; }


Measured memory_bytes: 10368
n = gets.to_i
t, a = gets.split.map(&:to_f)
x = gets.split.map(&:to_f)
x = x.map{|x| t-x*0.006}
r = 0
min = 100000
x.each_with_index do |x, i|
  hoge = (x-a).abs
  if hoge < min
    min = hoge
    r = i+1
  end
end
p r

Measured memory_bytes: 1916
#include <iostream>
#include<algorithm>
#include<sstream>
#include<cmath>
#include<vector>
#include<iomanip>
#include<map>
#include<set>
#include<queue>
#include<deque>
using namespace std;
typedef long long ll;
typedef long double ld;
#define rep(i,n) for(int i = 0; i < n;i++)
int main() {
	string s;int k,sum = 0;cin >> s;k = s.size();
	rep(i, k) {
		if (s[i] == 'o') sum++;
	}
	if (15 - k + sum >= 8) cout << "YES" << endl;
	else cout << "NO" << endl;
}

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

using namespace std;

#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 DEBUG_MAT(v) cerr<<#v<<endl;for(int i=0;i<v.size();i++){for(int j=0;j<v[i].size();j++) {cout<<v[i][j]<<" ";}cout<<endl;}


typedef long long ll;
#define vi vector<int>
#define vl vector<ll>
#define vii vector< vector<int> >
#define vll vector< vector<ll> >
#define vs vector<string>
#define pii pair<int,int>
#define pis pair<int,string>
#define psi pair<string,int>
#define pll pair<ll,ll>
template<class S, class T> pair<S, T> operator+(const pair<S, T> &s, const pair<S, T> &t) { return pair<S, T>(s.first + t.first, s.second + t.second); }
template<class S, class T> pair<S, T> operator-(const pair<S, T> &s, const pair<S, T> &t) { return pair<S, T>(s.first - t.first, s.second - t.second); }
template<class S, class T> ostream& operator<<(ostream& os, pair<S, T> p) { os << "(" << p.first << ", " << p.second << ")"; return os; }
#define X first
#define Y second
#define rep(i,n) for(int i=0;i<(n);i++)
#define rep1(i,n) for(int i=1;i<=(n);i++)
#define rrep(i,n) for(int i=(n)-1;i>=0;i--)
#define rrep1(i,n) for(int i=(n);i>0;i--)
#define REP(i,a,b) for(int i=a;i<b;i++)
#define in(x, a, b) (a <= x && x < b)
#define all(c) c.begin(),c.end()
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 UNIQUE(v) v.erase(std::unique(v.begin(), v.end()), v.end());
const ll inf = 1000000001;
const ll INF = (ll)1e18 + 1;
const ll MOD = 1000000007;
//const ll MOD = 998244353;
const double pi = 3.14159265358979323846;
#define Sp(p) cout<<setprecision(15)<< fixed<<p<<endl;
int dx[4] = { 1,0, -1,0 }, dy[4] = { 0,1,0,-1 };
int dx2[8] = { 1,1,0,-1,-1,-1,0,1 }, dy2[8] = { 0,1,1,1,0,-1,-1,-1 };
#define fio() cin.tie(0); ios::sync_with_stdio(false);
//#define mp make_pair


int main() {
  ll k, a, b;
  cin >> k >> a >> b;
  ll now = 1;
  if (now + k <= a) {
    cout << now + k << endl;
    return 0;
  }
  k -= a - now;
  now = a;
  if (k % 2 == 1) {
    k--;
    now++;
  }
  if (b - a >= 2) {
    now += (k / 2) * (b - a);
  }
  else {
    now += k;
  }
  cout << now << endl;
}


Measured memory_bytes: 256
import java.util.*;
public class Main {
	public static void main(String...args) {
		Scanner sc = new Scanner(System.in);
		while(sc.hasNextFloat()) {
			float a = sc.nextFloat();
			float b = sc.nextFloat();
			float c = sc.nextFloat();
			float d = sc.nextFloat();
			float e = sc.nextFloat();
			float f = sc.nextFloat();
			float z = a*e - b*d;
			float x = (c * e - f * b)/z;
			float y = (a * f - d * c)/z;
			x = x == -0.0f ? 0.0f : x;
			y = y == -0.0f ? 0.0f : y;
			System.out.printf("%.3f %.3f\n", x, y);
		}
	}
}

Measured memory_bytes: 12000
#include <bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL);
#define ll long long
#define ull unsigned long long
#define FI(i,a,n) for(int i=a; i<=n; i++)
#define RFI(i,n,a) for(int i=n; i>=a; i--)
#define FLL(i,a,n) for(ll i=a; i<=n; i++)
#define RFLL(i,n,a) for(ll i=n; i>=a; i--)
#define vi vector<int>
#define vll vector<ll>
#define all(v) v.begin(),v.end()
#define pll pair<ll,ll>
#define pi pair<int, int>
#define GCD(a,b) __gcd(a,b)
#define MP make_pair
#define PB push_back
#define PF push_front
#define LB lower_bound
#define UB upper_bound
#define debug(x) cout << x << endl
#define MOD 1000000007
#define INF LLONG_MAX
#define PI 3.14159265359
using namespace std;

ll power(ll x, ll n)
{
  ll ans = 1;
  while(n)
  {
    if(n&1) ans = (ans*x)%MOD;
    n/=2, x = (x*x)%MOD;
  }
  return ans;
}

int main()
{
  fastio
  ll n, k;
  cin >> n >> k;
  ll a[k+1]={};
  for(ll i=k/2+1; i<=k; i++) a[i]=1;
  for(ll i=k/2; i>=1; i--)
  {
    a[i] = power(k/i, n);
    for(ll j=2*i; j<=k; j+=i)
    {
      a[i] -= a[j];
      if(a[i]<0) a[i] += MOD;
    }
  }
  ll ans = 0;
  for(ll i=1; i<=k; i++) ans = (ans + i*a[i])%MOD;
  cout << ans ;



  return 0;
}




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

typedef int64_t Int;
#define all(x) (x).begin(), (x).end()
 
const double EPS = 1e-10;
const Int INF = 1e18;
const int inf = 1e9;
const Int mod = 1e9+7;

bool print_space_enable = false;
void print() { 
    cout << '\n'; 
    print_space_enable = false;
}

template <class Head, class... Tail>
void print(Head&& head, Tail&&... tail) {
    if (print_space_enable) cout << " ";
    cout << fixed << setprecision(15) << head;
    print_space_enable = true;
    print(std::forward<Tail>(tail)...);
}

template<typename T>
void print(vector<T> v) {
    for (size_t i = 0; i < v.size(); i++) {
        if (i > 0) std::cout << " ";
        std::cout << v[i];
    }
    std::cout << std::endl;
}

int main() {
    Int n, k;
    cin >> n >> k;
    vector<Int> p(n), c(n);
    for (Int i = 0; i < n; i++) {
        cin >> p[i];
        p[i]--;
    }
    Int sum = 0;
    for (Int i = 0; i < n; i++) {
        cin >> c[i];
        sum += c[i];
    }
    Int res = -INF;
    for (Int i = 0; i < n; i++) {
        Int score = -INF;
        if (k <= n) {
            Int ma = 0;
            Int cur = i;
            for (Int j = 0; j < k; j++) {
                ma += c[p[cur]];
                cur = p[cur];
                score = max(score, ma);
            }
        } else {
            Int s = c[i];
            Int cur = i;
            Int cycle = 1;
            while (p[cur] != i) {
                s += c[p[cur]];
                cur = p[cur];
                cycle++;
            }
            if (s > 0) {
                Int ma = s * (k / cycle - 1);
                cur = i;
                for (Int j = 0; j < k % cycle + cycle; j++) {
                    ma += c[p[cur]];
                    cur = p[cur];
                    score = max(score, ma);
                }
            } else {
                Int ma = 0;
                cur = i;
                for (Int j = 0; j < cycle; j++) {
                    ma += c[p[cur]];
                    cur = p[cur];
                    score = max(score, ma);
                }
            }
        }
        res = max(res, score);
    }
    print(res);
    return 0;
}


Measured memory_bytes: 3688
#include <iostream>
#include <map>

using namespace std;

long long solve(long long X, map<long long, long long>& memo)
{
	if (X == 1) {
		return 1;
	}
	if (memo.count(X)) {
		return memo[X];
	}
	long long ans = 1 + 2 * solve(X / 2, memo);
	return memo[X] = ans;
}

int main()
{
	long long H;
	cin >> H;
	map<long long, long long> memo;

	cout << solve(H, memo) << endl;
}


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

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

    int ne = 700;
    for(int i = 0; i < 3; i++){
        if(S.substr(i,1) == "o"){
            ne += 100;
        }
    }

    cout << ne << endl;
}

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

void solve(int n, int m){
	vector<int> a;
	vector<int> v;
	for(int i=0; i<n; ++i){
		int t;
		cin >> t;
		a.push_back(t);
	}
	sort(a.begin(), a.end());
	reverse(a.begin(), a.end());
	for(int i=0; i<n; ++i)
		for(int j=i+1; j<n; ++j){
			if(a[i] + a[j] <= m){
				v.push_back(a[i] + a[j]);
			}
		}
	if(v.size() == 0) cout << "NONE\n";
	else{
		sort(v.begin(), v.end());
		cout << v[v.size()-1] << "\n";
	}
	return;
}

int main(){
//	cin.tie(0);
//	ios::sync_with_stdio(false);
	while(1){
		int n, m;
		cin >> n >> m;
		if(n == 0) return 0;
		solve(n, m);
	}
}


Measured memory_bytes: 6844
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n)for(int i=0;i<(n);i++)
#define ALL(a) (a).begin(), (a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define pb push_back
using ll = long long;
using P = pair<int, int>;
using Graph = vector<vector<int>>;

int main(){
    int n; cin >> n;
    map<int, int> ma;
    rep(i,n-1){
        int a; cin >> a;
        ma[a]++;
    }
    for(int i = 1; i <= n; i++){
        cout << ma[i] << endl;
    }
}

Measured memory_bytes: 13008
#include<stdio.h>
int main(void)
{
	int a1,a2,a3,a4,s,q,qq;
	scanf("%d",&a1);
	scanf("%d",&a2);
	scanf("%d",&a3);
	scanf("%d",&a4);
	s=a1+a2+a3+a4;
	q=s/60;
	qq=s%60;
	printf("%d\n",q);
	printf("%d\n",qq);
	return 0;
}
	

Measured memory_bytes: 1024
# -*- coding: utf-8 -*-
import numpy as np
from itertools import combinations


def answer(l):
    results = [np.linalg.norm(np.array(i) - np.array(j))for i, j in combinations(l, 2)]
    return sum(float.is_integer(i) for i in results)


n, d = map(int, input().split())
coodinates = [[int(x) for x in input().split()] for _ in range(n)]
print(answer(coodinates))


Measured memory_bytes: 12500
import java.util.*;



import java.io.*;
public class Main {

	public static void main(String[] args) {
	FastScanner sc=new FastScanner();
	int n=sc.nextInt();
	int a[][]=new int[n][3];
	for(int i=0;i<n;i++) {
		a[i][0]=sc.nextInt();
		a[i][1]=sc.nextInt();
		a[i][2]=sc.nextInt();
	}
	int dp[][]=new int[n][3];
	dp[0][0]=a[0][0];
	dp[0][1]=a[0][1];
	dp[0][2]=a[0][2];
	for(int i=1;i<n;i++) {
		dp[i][0]=Math.max(dp[i-1][1], dp[i-1][2])+a[i][0];
		dp[i][1]=Math.max(dp[i-1][0], dp[i-1][2])+a[i][1];
		dp[i][2]=Math.max(dp[i-1][0], dp[i-1][1])+a[i][2];
	}
//	for(int i=0;i<n;i++)
//		System.out.println(dp[i][0]+" "+dp[i][1]+" "+dp[i][2]);
	int ans=Integer.MIN_VALUE;
	for(int i=0;i<3;i++)ans=Math.max(ans, dp[n-1][i]);
	System.out.println(ans);


	}
	static class FastScanner{
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st=new StringTokenizer("");
		
		String next() {
			while (!st.hasMoreTokens())
				try {
					st=new StringTokenizer(br.readLine());
				} catch (IOException e) {
					e.printStackTrace();
				}
			return st.nextToken();
		}
		int nextInt() {
			return Integer.parseInt(next());
		}
		long nextLong() {
			return Long.parseLong(next());
		}
		int [] readArray(int n) {
			int a[]=new int[n];
			for(int i=0;i<n;i++) a[i]=nextInt();
			return a;
		}
		
		
	}
	

}



Measured memory_bytes: 62924
#include <bits/stdc++.h>
using namespace std;
#define QOEINDIEDIS freesteed
#define rep(i,a,n) for (int i=a;i<n;i++)
#define pb push_back
#define fill(x,c) memset(x,c,sizeof(x))
#define fi first
#define se second
#define sz(A) (int)(A.size())
#define all(x) (x).begin(),(x).end()
#define caset int ___T; cin>>___T; for(int cs=1;cs<=___T;cs++)
#define get(c,x) (lower_bound(c.begin(),c.end(),x)-c.begin())
typedef long long ll;
typedef pair<int,int> PII;
typedef vector<int> VI;
const ll mod=1e9+7;
const int Max = 1e6+10;
ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
void solve(){
	ll n;
	cin>>n;
	ll N = n-1,cnt=2;//n,n-1
	if(n==2)cnt--;
	for(ll i=2;i<=sqrt(N);i++){
		if(N%i==0){
			cnt++;
			if(N/i!=i){
				cnt++;
			}
		}
	}
	//cout<<cnt<<endl;
	for(ll i=2;i<=sqrt(n);i++){
		if(n%i==0){
			ll n1=n;
			while(n1%i==0)n1/=i;
			if(n1%i==1){
				cnt++;
			}
		}
	}
	cout<<cnt;
}
int main() {
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	//caset{
		solve();
	//}
  	return 0;
}






Measured memory_bytes: 256
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <cstring>
#include <queue>
#include <stack>
#include <cmath>
#include <functional>
#include <set>
#include <map>

using namespace std;
typedef long long int ll;
typedef pair <int,int> P;

int main()
{
	int n,A,B;
	scanf("%d %d %d",&n,&A,&B);
	int ret=0;
	for(int i=0;i<n;i++)
	{
		int t;
		scanf("%d",&t);
		if(t<A||t>=B)
		{
			ret++;
		}
	}
	printf("%d\n",ret);
	return 0;
}


Measured memory_bytes: 128
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <vector>
#include <set>
#include <queue>
#include <map>
#include <string>

#define rep(i, a, b) for ( ll i = (a); i < (b); i++ )
#define per(i, a, b) for ( ll i = (b)-1; i >= (a); i--)
#define pb push_back
#define mp make_pair
#define bg begin()
#define en end()
#define all(v) (v).begin(), (v).end()
#define sz(v) (int)(v).size()

using namespace std;

typedef long long ll;
typedef long double ld;

using P = pair<int, int>;

static const long long MOD = 1000000007;
static const long long LINF = (ll)(1e18+99);
static const int INF = 1e9+99;

int n;
ll ans;
vector<ll> l, r;

int main(void) {
  cin >> n;
  rep (i, 0, n) {
    ll a, b;
    cin >> a >> b;
    l.pb(a);
    r.pb(b);
  }
  sort(all(l));
  sort(all(r));
  
  ll lm = (l[n/2] + l[(n-1)/2]);
  ll rm = (r[n/2] + r[(n-1)/2]);
  
  ans = rm - lm;
  if (n%2==1) ans /= 2;
  
  cout << ans + 1 << endl;
   
    return 0;
}


Measured memory_bytes: 6544
#include<bits/stdc++.h>
using namespace std;
int c,b,B;
int n;
int a[234234];

int main()
{int i;
  scanf("%d",&n);
  for(i=1;i<=n;i++) 
   {
    scanf("%d",&a[i]);
    if(a[i]>b) b=a[i],c=0;
    else if(a[i]==b) c++;
  }
  for(i=1;i<=n;i++)
    {
	  if(a[i]!=b) B=max(B,a[i]);
	}
  for(i=1;i<=n;i++) 
    {
	  if(c) printf("%d\n",b);
	  else printf("%d\n",(a[i]==b)?B:b);
	}
} 

Measured memory_bytes: 2432
#include <bits/stdc++.h>
#define For(i, a, b) for(int (i)=(a); (i)<(b); ++(i))
#define rFor(i, a, b) for(int (i)=(a)-1; (i)>=(b); --(i))
#define rep(i, n) For((i), 0, (n))
#define rrep(i, n) rFor((i), (n), 0)
#define fi first
#define se second
using namespace std;
typedef long long lint;
typedef pair<int, int> pii;

int main(){
    int n;
    scanf("%d", &n);
    map<array<int, 26>, lint> mp;
    rep(i, n){
        string s;
        cin >> s;
        array<int, 26> a;
        rep(j, 26) a[j] = 0;
        rep(j, s.size()) ++a[s[j] - 'a'];
        ++mp[a];
    }
    lint ans = 0;
    for(auto itr=mp.begin(); itr!=mp.end(); ++itr){
        ans += (lint)itr->se * (itr->se-1) / 2;
    }
    printf("%lld\n", ans);
}

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

#define LL long long

#define FOR(INDEX, START, END) for (LL INDEX = (START); INDEX < (END); ++INDEX)
#define REP(INDEX, COUNT) for (LL INDEX = 0; INDEX < (COUNT); ++INDEX)

void chmin(LL& a, LL b) {
	a = min(a, b);
}
void chmax(LL& a, LL b) {
	a = max(a, b);
}

LL N, W;
struct Item {
	LL weight;
	LL value;
};

Item items[1000];

LL dp[101][100001];

int main()
{
	cin >> N >> W;
	REP(i, N) {
		cin >> items[i].weight >> items[i].value;
	}

	REP(i, N) {
		REP(k, W + 1) {
			if (k < items[0].weight) {
				dp[0][k] = 0;
			}
			else {
				dp[0][k] = items[0].value;
			}
		}
	}

	FOR(i, 1, N) {
		REP(k, W + 1) {
			if (k - items[i].weight >= 0) {
				chmax(dp[i][k], dp[i-1][k - items[i].weight] + items[i].value);
			}
			chmax(dp[i][k], dp[i - 1][k]);
		}
	}

	cout << dp[N-1][W] << endl;

	return 0;
}


Measured memory_bytes: 78336
n = gets.to_i
f = []
(1..(Math.sqrt(n))).each do |a|
  if n%a == 0
    b = n/a
    f << [a, b]
  end
end
ans = []
count = 0
f.each do |n|
  num = n.max.to_s.length
  ans << num
end
puts ans.min


Measured memory_bytes: 1788
#include<bits/stdc++.h>
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define rep2(i, m, n) for(int i = (int)(m); i < (int)(n); i++)
#define rep_inv(i, n, m) for(int i = (int)(n); i > (int)(m); i--)
using namespace std;
using ll = long long;
using vl = vector<ll>;
using vc = vector<char>;
using vvl = vector<vl>;
using vvc = vector<vc>;
using pll = pair<ll, ll>;
using vpll = vector<pll>;

int main(){
  vl A(3);
  rep(i, 3) cin >> A[i];

  stable_sort(A.begin(), A.end());

  cout << (A[1] - A[0]) + (A[2] - A[1]) << endl;
  
  return 0;
}


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

#define REP(i, n) for(int i=0; i<n; i++)
#define REPR(i, n) for(int i=n-1; i>=0; i--)
#define FOR(i, m, n) for(int i=m; i<n; i++)

#define INF 2e9
#define ll long long

int main(){
    int n, m, i, j;
    cin>>n>>m;
    int a[m];
    int b[n];

    REP(i, n+1){
        b[i] = 1;
    }

    for(i=0; i<m; i++){
        cin>>a[i];
        b[a[i]] = 0;
    }

    int ans[n+1];
    ans[0] = 1;
    if(b[1]==1){
        ans[1] = 1;
    }
    else{
        ans[1] = 0;
    }

    for(i=0; i<n-1; i++){
        ans[i+2] = (ans[i+1]*b[i+1] + ans[i]*b[i])%1000000007;
    }

    cout<<ans[n]<<endl;
    return 0;
}

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

int main() {
  int n;
  cin >> n;
  for (int i = 1; i <= n; i++) {
    if (i % 3 == 0) {
      cout << " " << i;
      continue;
    }
    if (i % 10 == 3) {
      cout << " " << i;
      continue;
    }
    int x = i;
    while (x > 0) {
      if (x % 10 == 3) {
        cout << " " << i;
        break;
      } else {
        x /= 10;
        continue;
      }
    }
  }
  cout << endl;
}


Measured memory_bytes: 3088
import kotlin.comparisons.*
import java.util.*

const val MOD = 1000000007L

fun readI() = readLine()!!.toInt()
fun readL() = readLine()!!.toLong()
fun readD() = readLine()!!.toDouble()
fun readIs() = readLine()!!.split(' ').map(String::toInt)
fun readLs() = readLine()!!.split(' ').map(String::toLong)
fun readDs() = readLine()!!.split(' ').map(String::toDouble)
fun max(a: Int, b: Int) = Math.max(a, b)
fun min(a: Int, b: Int) = Math.min(a, b)

fun main(args: Array<String>) {
  val (n, m) = readIs()
  var a = 0
  var b = Int.MAX_VALUE
  repeat(m) {
    val (l, r) = readIs()
    a = max(a, l)
    b = min(b, r)
  }
  println(max(0, b - a + 1))
}


Measured memory_bytes: 56700
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cmath>
#include <climits>
#include <cstdlib>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <string>
#include <vector>
#define DEBUG 1
using namespace std;
constexpr int kMod = 1000000007;
typedef long long LL;
typedef pair<int, int> P;

template<typename T>
istream& operator >> (istream& is, vector<T>& vs){
  for(T& v: vs) is >> v;
  return is;
}

int main() {
  int H, W; cin >> H >> W;
  vector<string> S(H); cin >> S;
  vector<vector<int>> Cell(H, vector<int>(W, 0));

  vector<int> ids;
  for (int r = 0; r < H; ++r) {
    for (int c = 0; c < W; ++c) {
      if (S[r][c] == '#') {
        if (!ids.empty()) {
          for (int id : ids) Cell[r][id] = ids.size();
        }
        ids.clear();
      } else {
        ids.push_back(c);
      }
    }

    if (!ids.empty()) {
      for (int id : ids) Cell[r][id] = ids.size();
    }
    ids.clear();
  }

  for (int c = 0; c < W; ++c) {
    for (int r = 0; r < H; ++r) {
      if (S[r][c] == '#') {
        if (!ids.empty()) {
          for (int id : ids) {
            if (Cell[id][c] > 0) Cell[id][c] += ids.size() - 1;
            else                 Cell[id][c] = ids.size();
          }
        }
        ids.clear();
      } else {
        ids.push_back(r);
      }
    }

    if (!ids.empty()) {
      for (int id : ids) {
        if (Cell[id][c] > 0) Cell[id][c] += ids.size() - 1;
        else                 Cell[id][c] = ids.size();
      }
    }
    ids.clear();
  }

  int vmax = 0;
  for (int r = 0; r < H; ++r) {
    for (int c = 0; c < W; ++c) {
      vmax = max(vmax, Cell[r][c]);
    }
  }
  cout << vmax << endl;
}


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

using namespace std;

int main(){

    double a, b;
    cin >> a >> b;

    int a_max = (a + 1) / 0.08;
    int a_min = ceil(a / 0.08);

    for(int i = a_min; i < a_max; i++){
        if(int(i*0.1) == b){
            cout << i << endl;
            return 0;
        }
    }

    cout << -1 << endl;
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MOD = 1e9+7;
int main() {
    ll x;
    cin >> x;
    ll ta=x%100;
    ll judge=0;
    while(ta>=5){
        ta-=5;
        judge++;
    }
    if(ta>0) judge++;
    if(100*judge>x){
        cout << 0 << endl;
    }
    else {
        cout << 1 << endl;
    }
}

Measured memory_bytes: 3632
#include <iostream>
#include <vector>

using namespace std;

int main() {
	
	while (1) {
		int n, r; cin >> n >> r; if (n==0 && r==0) break;
		
		vector<int> num(n);
		for (int i=0; i<n; i++) num[i] = n-i;
		
		for (int rep = 0; rep<r; rep++) {
			int p, c; cin >> p >> c;
			
			vector<int> next(n);
			int index = 0;
			for (int i=p-1; i<p+c-1; i++) next[index++] = num[i];
			for (int i=0; i<p-1; i++) next[index++] = num[i];
			for (int i=p+c-1; i<n; i++) next[index++] = num[i];
			
			num = next;
		}
		
		cout << num[0] << endl;
	}
	
	return 0;
}

Measured memory_bytes: 1220
#include <iostream>
using namespace std;
int main(void){
    long long K,max,min;
    cin>>K;
    long long A[K],i;
    for(i=0;i<K;i++){
        cin>>A[K-1-i];
    }
    max=2;min=2;
    for(i=0;i<K;i++){
        if((min-1)/A[i]+1>max/A[i]){
            cout<<-1<<endl;
            return 0;
        }
        min=((min-1)/A[i]+1)*A[i];
        max=(max/A[i]+1)*A[i]-1;
    }
    cout<<min<<" "<<max<<endl;
}


Measured memory_bytes: 1024
//#define NDEBUG
#include <cstddef>
#include <cstdint>
#include <vector>

namespace n91 {

	using i8 = std::int_least8_t;
	using i32 = std::int_least32_t;
	using i64 = std::int_least64_t;
	using u8 = std::uint_least8_t;
	using u32 = std::uint_least32_t;
	using u64 = std::uint_least64_t;
	using isize = std::ptrdiff_t;
	using usize = std::size_t;

	class rep {
		const usize f, l;

	public:
		class itr {
			friend rep;
			usize i;
			constexpr itr(const usize x) noexcept : i(x) {}

		public:
			void operator++() noexcept { ++i; }
			constexpr usize operator*() const noexcept { return i; }
			constexpr bool operator!=(const itr x) const noexcept { return i != x.i; }
		};
		constexpr rep(const usize first, const usize last) noexcept
			: f(first), l(last) {}
		constexpr itr begin() const noexcept { return itr(f); }
		constexpr itr end() const noexcept { return itr(l); }
	};
	class revrep {
		const usize f, l;

	public:
		class itr {
			friend revrep;
			usize i;
			constexpr itr(usize x) noexcept : i(x) {}

		public:
			void operator++() noexcept { --i; }
			constexpr usize operator*() const noexcept { return i; }
			constexpr bool operator!=(const itr x) const noexcept { return i != x.i; }
		};
		constexpr revrep(usize first, usize last) noexcept : f(--first), l(--last) {}
		constexpr itr begin() const noexcept { return itr(l); }
		constexpr itr end() const noexcept { return itr(f); }
	};
	template <class T> using vec_alias = std::vector<T>;
	template <class T> auto md_vec(const usize n, const T &value) {
		return std::vector<T>(n, value);
	}
	template <class... Args> auto md_vec(const usize n, Args... args) {
		return std::vector<decltype(md_vec(args...))>(n, md_vec(args...));
	}
	template <class T> constexpr T difference(const T &a, const T &b) {
		return a < b ? b - a : a - b;
	}

} // namespace n91

#include <algorithm>
#include <iostream>
#include <utility>
#include<string>

namespace n91 {

	void main_() {
		usize n;
		std::string s;
		std::cin >> n >> s;
		const usize r = std::count(s.cbegin(), s.cend(), 'R');
		const usize b = std::count(s.cbegin(), s.cend(), 'B');
		std::cout << (b < r ? "Yes" : "No") << std::endl;
	}

} // namespace n91

int main() {
	n91::main_();
	return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<fstream>
#include<algorithm>
#include<cmath>
#include<cstdio>
#include<string>
#include<cstring>
using namespace std;
int x,y,z,h,g;
int main()
{
	cin>>x>>y>>z;
	h=x-z;
	while(h-y>0)
	{
		if(h-y-z<0)break;
		else h=h-y-z;
		g++;
	}
	cout<<g<<endl;
	return 0;
}

Measured memory_bytes: 256
object Main extends App {
  import scala.collection.mutable.{ArrayBuffer, ArrayOps}

  var count: Long = 0
  val n = io.StdIn.readLine()
  val arr: collection.mutable.ArrayOps[Int] = split(io.StdIn.readLine())

  def split(str: String): Array[Int] = {
    val buf: ArrayBuffer[Int] = ArrayBuffer.empty[Int]
    var num_builder = 0
    val iter = str.toIterator

    while(iter.hasNext) {
      val v = iter.next()
      if (v != ' ') num_builder = num_builder*10 + v.toInt
      else {buf += num_builder; num_builder = 0}
    }
    (buf += num_builder).toArray
  }

  def merge(left: Int, middle: Int, right: Int): Unit = {
    val l = arr.slice(left, middle)
    val r = arr.slice(middle, right)
    val lLen = l.length
    val rLen = r.length

    var i = left
    var li = 0
    var ri = 0

    while(li < lLen && ri < rLen) {
      if (l(li) <= r(ri)) {
        arr(i) = l(li)
        i += 1
        li += 1
      } else {
        arr(i) = r(ri)
        count += (lLen - li)
        i += 1
        ri += 1
      }
    }

    if (li < lLen) while (li < lLen) {arr(i) = l(li); i += 1; li += 1}
    else while (ri < rLen) {arr(i) = r(ri); i += 1; ri += 1}
  }

  def msort(left: Int, right: Int): Unit = {
    val middle = (left+right+1)/2
    if (middle < right) {
      msort(left, middle)
      msort(middle, right)
      merge(left, middle, right)
    } else {
      ()
    }
  }

  msort(0, arr.length)
  println(count)
}

Measured memory_bytes: 206904
#include<iostream>
#include <algorithm>
#include<string>
#include <numeric>
#include<math.h>
#include <bits/stdc++.h>
using namespace std;

int main(void) {
    char a;
    cin >>a;
    if(a=='a'||a=='i'||a=='u'||a=='e'||a=='o')cout<<"vowel"<<endl;
    else cout<<"consonant"<<endl;
}


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

#define ll long long

void solve() {
	int a,b,h,m;
	cin>>a>>b>>h>>m;
	double hd,md;
	double pi=4*atan(1.0);
	hd=(double)((h*60+m)%720)/720*2*pi;
	md=(double)m/60*2*pi;
	double ddeg=abs(hd-md);
	double c=a*a+b*b-2*a*b*cos(ddeg);
	c=sqrt(c);
	cout<<setprecision(16)<<c<<"\n";
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	solve();
	return 0;
}
































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

int main() {
  char c;cin>>c;
  char d;
  if (c>='a') cout<<"a";
  else cout<<"A";
}


Measured memory_bytes: 3620
def main():
    n = int(input())
    cakes = range(n // 4 + 1)
    donuts = range(n // 7 + 1)

    for i in cakes:
        for j in donuts:
            if 4 * i + 7 * j == n:
                print("Yes")
                exit()
    print("No")


main()

Measured memory_bytes: 9020
#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("Ofast")
#define all(x) (x).begin(),(x).end()
#define rep(i,n) for(int (i)=0;i<(n);i++)
#define REP(i,m,n) for(int (i)=(m);(i)<(n);(i)++)
#define INF INT_MAX
#define MOD 1000000007
#define fcout cout << fixed << setprecision(15)
#define int long long
#define yorn(f) puts((f)?"Yes":"No")
#define YORN(f) puts((f)?"YES":"NO")
#define sec second
#define fir first
typedef long long ll;
typedef pair<int, int> P;
typedef priority_queue<int> pque;
typedef vector<int> Vec;
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;};
int mod(int a,int b){return (a+b-1)/b;};
template<typename A, size_t N, typename T>
void Fill(A(&array)[N],const T &val){std::fill((T*)array,(T*)(array+N),val);}
template<class T>inline bool chmax(T& a,T b){if(a<b){a=b;return true;}return false;};
template<class T>inline bool chmin(T& a,T b){if(a>b){a=b;return true;}return false;};



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

	int k, n;
	cin >> k >> n;
	int a[n];
	int dif = 0;
	rep(i, n) {
		cin >> a[i];
		if(i) {
			chmax(dif, a[i] - a[i-1]);
		}
	}
	chmax(dif, k + a[0] - a[n-1]);
	cout << k - dif << endl;
	return 0;
}

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

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

int main(){
    int n;
    while(cin>>n,n){
        vector<long long> v(n);
        rep(i,n){
            string s;
            cin>>s;
            if(s[0]=='x'){
                v[i]=INT_MAX;
            }
            else{
                stringstream ss;
                ss<<s;
                ss>>v[i];
            }
        }
        bool f=true;
        rep(i,n-1){
            if(v[i]==-1&&v[i+1]==-1){
                f=false;
            }
        }
        if(!f){
            cout<<"none"<<endl;
            continue;
        }
        f=true;
        rep(i,n){
            if(v[i]==INT_MAX) f=false;
        }
        if(f){
            rep(i,n){
                if(i%2){
                    if(i&&v[i]<=v[i-1]) f=false;
                    if(i+1!=n&&v[i]<=v[i+1]) f=false;
                }
                else{
                    if(i&&v[i]>=v[i-1]) f=false;
                    if(i+1!=n&&v[i]>=v[i+1]) f=false;
                }
            }
            if(f){
                cout<<"ambiguous"<<endl;
            }
            else{
                cout<<"none"<<endl;
            }
            continue;
        }
        // cout<<"a"<<endl;
        long long l=-LLONG_MAX/2;
        long long r=LLONG_MAX/2;
        rep(i,n){
            if(v[i]==INT_MAX){
                if(i%2){
                    if(i) l=max(l,v[i-1]+1LL);
                    if(i!=n-1) l=max(l,v[i+1]+1LL);
                }
                else{
                    if(i) r=min(r,v[i-1]-1LL);
                    if(i!=n-1) r=min(r,v[i+1]-1LL);
                }
            }
        }
        // cout<<l<<" "<<r<<endl;
        f=true;
        rep(i,n){
            if(v[i]==INT_MAX) continue;
            if(i%2){
                if(i&&v[i-1]!=INT_MAX&&v[i-1]>=v[i]) f=false;
                if(i!=n-1&&v[i+1]!=INT_MAX&&v[i]<=v[i+1]) f=false;
            }
            else{
                if(i&&v[i-1]!=INT_MAX&&v[i-1]<=v[i]) f=false;
                if(i!=n-1&&v[i+1]!=INT_MAX&&v[i]>=v[i+1]) f=false;
            }
        }
        if(!f){
            cout<<"none"<<endl;
        }
        else if(r-l==0LL){
            cout<<r<<endl;
        }
        else if(r-l>0LL){
            cout<<"ambiguous"<<endl;
        }
        else{
            cout<<"none"<<endl;
        }
        // cout<<endl;
    }
}

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

using namespace std;
long long a[100010];

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

  int n;
  cin >> n;

  rep(i, n) {
    cin >> a[i];
    if(a[i]==0) {
      cout << "0\n";
      return 0;
    }
  }

  long long prod = 1;
  rep(i,n) {
    if(a[i] <= 1000000000000000000/prod) {
      prod *= a[i];
    } else {
      prod = -1;
      break;
    }
  }

  cout << prod;

  return 0;
}

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

int main(){
    ll x; cin >> x;
    ll cumsum = 0;
    int cnt = 1;
    int ans = 0;
    while(true){
        cumsum += cnt;
        if(cumsum >= x){
            ans = cnt;
            break;
        }
        cnt++;
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 3600
#include<iostream>
#include<cstdio>
#include<queue>
#include<vector>
#include<string.h>
#include<algorithm>
#include <cmath>

using namespace std;

int i,j,k,N,A[3][3],B[10],a;

int main()
{
  for(i=0;i<3;i++)
  {
    for(j=0;j<3;j++)
    {
      cin>>A[i][j];
    }
  }
  
  cin>>N;
  for(i=0;i<N;i++)
  {
    cin>>B[i];
  }
  
  for(k=0;k<N;k++)
  {
    for(i=0;i<3;i++)
    {
      for(j=0;j<N;j++)
      {
        if(B[k]==A[i][j])
        {
          A[i][j]=0;
        }
      }
    }
  }
  
  a=0;
  
  for(i=0;i<3;i++)
  {
    if(A[i][0]+A[i][1]+A[i][2]==0)
    {
      cout<<"Yes";
      a=1;
      break;
    }
    else if(A[0][i]+A[1][i]+A[2][i]==0)
    {
      cout<<"Yes";
      a=1;
      break;
    }
  }
  
  if(A[0][0]+A[1][1]+A[2][2]==0 && a==0)
  {
      cout<<"Yes";
    a=1;
  }
  
    if(A[0][2]+A[1][1]+A[2][0]==0 && a==0)
  {
      cout<<"Yes";
    a=1;
  }
  
  if(a==0)
  {
    cout <<"No";
  }
}

Measured memory_bytes: 256
#include <iostream>
#include <cmath>

int main(){
  int N;
  int X[100];
  int Min=100;
  int Max = 0;
  
  std::cin >> N;

  for(int i=0;i<N;i++){
    std::cin >> X[i];
    if(Min > X[i])
      Min = X[i];
    if(Max < X[i])
      Max = X[i];
    
  }
  
  long SumMin = pow(2,32) -1;
  
  for(int where=Min;where<=Max;where++){
    long Sum=0;
    for(int i =0;i<N;i++){
      Sum += pow(X[i] - where,2);
    }
    if(SumMin > Sum)
	SumMin = Sum;
  }

  std::cout << SumMin << std::endl;
  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <map>
#include <cmath>
using namespace std;

int main(){
    int n;
    cin >> n;
    deque<int> d;
    for(int i = 0; i < n; i++){
        int a;
        cin >> a;
        if(n%2==0){
            if(i%2==0) d.push_back(a);
            else d.push_front(a);
        }else{
            if(i%2==0) d.push_front(a);
            else d.push_back(a);
        }
    }
    for(int i = 0; i < n; i++) cout << d[i] << " ";
    cout << endl;
}

Measured memory_bytes: 2944
using System;
using System.Linq;
using System.Collections.Generic;

namespace AtCoder.Contests.ABC157
{
    /// <summary>
    /// 
    /// </summary>
    static class B
    {
        static void Main(string[] args)
        {
            var aas = ReadMatrix(3, 3);
            var n = ReadInt();
            var bs = new HashSet<int>();
            for (int i = 0; i < n; i++)
            {
                bs.Add(ReadInt());
            }

            for (int i = 0; i < 3; i++)
            {
                if (Enumerable.Range(0, 3).All(j => bs.Contains(aas[i, j])))
                {
                    Console.WriteLine("Yes");
                    return;
                }
            }
            for (int i = 0; i < 3; i++)
            {
                if (Enumerable.Range(0, 3).All(j => bs.Contains(aas[j, i])))
                {
                    Console.WriteLine("Yes");
                    return;
                }
            }
            if (Enumerable.Range(0, 3).All(i => bs.Contains(aas[i, i]))
              || Enumerable.Range(0, 3).All(i => bs.Contains(aas[2-i, i])))
            {
                Console.WriteLine("Yes");
                return;
            }

            Console.WriteLine("No");
        }

        #region Console
        static int ReadInt()
        {
            return int.Parse(Console.ReadLine());
        }
        static long ReadLong()
        {
            return long.Parse(Console.ReadLine());
        }
        static int[] ReadIntArray()
        {
            return Console.ReadLine().Split(' ').Select(int.Parse).ToArray();
        }
        static int[] ReadIntArray(int n)
        {
            var a = new int[n];
            for (int i = 0; i < n; i++)
            {
                a[i] = ReadInt();
            }
            return a;
        }
        static long[] ReadLongArray()
        {
            return Console.ReadLine().Split(' ').Select(long.Parse).ToArray();
        }
        static long[] ReadLongArray(int n)
        {
            var a = new long[n];
            for (int i = 0; i < n; i++)
            {
                a[i] = ReadLong();
            }
            return a;
        }
        static List<T> ReadObjects<T>(int n, Func<int[], T> creator)
        {
            var l = new List<T>(n);

            for (int i = 0; i < n; i++)
            {
                var a = ReadIntArray();
                l.Add(creator(a));
            }

            return l;
        }

        static int[,] ReadMatrix(int n, int m)
        {
            var r = new int[n, m];
            for (int i = 0; i < n; i++)
            {
                var a = ReadIntArray();
                for (int j = 0; j < m; j++)
                {
                    r[i, j] = a[j];
                }
            }
            return r;
        }
        #endregion
    }
}


Measured memory_bytes: 13408
//“Make it work, make it right, make it fast.” – Kent Beck
	#include<bits/stdc++.h>
	using namespace std;
	typedef long long ll;
	typedef double dd;
	const int siz = 1e6 + 5;
	const int MOD = 1e9 + 7;
	#define endl '\n'
	#define deb(x) cout << #x << " = " << x << endl;
	void solve(){
		int h, n;
		cin >> h >> n;
		int s = 0, x;
		for(int i = 0; i < n; i++)
		{
			cin >> x;
			s+=x;
		}
		if(s >= h)
			cout << "Yes\n";
		else
			cout << "No\n";
	}

	int main(){
		#ifndef RAY
			//freopen("input.txt", "r", stdin);
		#endif
			ios::sync_with_stdio(false);
			cin.tie(nullptr);
			int t = 1;
			//cin >> t;
			while(t--){
				solve();
			}
		return 0;
	}


Measured memory_bytes: 256
fun main(args: Array<String>) {
    val INF = 1001001001
    val (N, A, B, C) = listOfInt()
    val L = (0 until N).map { nextInt() }.sortedDescending()
    fun min(vararg v: Int) = v.asList().min()!!
    fun dfs(cur: Int, a: Int, b: Int, c: Int): Int {
        if (cur == N) return if (min(a, b, c) > 0) Math.abs(a - A) + Math.abs(b - B) + Math.abs(c - C) - 30 else INF
        val r0 = dfs(cur + 1, a, b, c)
        val r1 = dfs(cur + 1, a + L[cur], b, c) + 10
        val r2 = dfs(cur + 1, a, b + L[cur], c) + 10
        val r3 = dfs(cur + 1, a, b, c + L[cur]) + 10
        return min(r0, r1, r2, r3)
    }
    println(dfs(0, 0, 0, 0))
}
fun next() = readLine()!!
fun nextInt() = next().toInt()
fun listOfString() = next().split(" ")
fun listOfInt() = listOfString().map(String::toInt)

Measured memory_bytes: 43496
#include <bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<(b);++i)
#define erep(i,a,b) for(int i=a;i<=(int)(b);++i)
#define per(i,a,b) for(int i=(a);i>(b);--i)
#define eper(i,a,b) for(int i=(a);i>=b;--i)
#define pb push_back
#define mp make_pair
#define INF 1000100100000000
#define MOD 1000000007
#define ALL(x) begin(x),end(x)
using namespace std;
typedef long long ll;
typedef pair<int,int> Pii;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a = b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a = b; return 1; } return 0; }
int dy[]={0, 0, 1, -1};
int dx[]={1, -1, 0, 0};
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;}

int n, m;
ll d[2005], a[2005], b[2005], c[2005], negative[2005], ans;
bool negative_loop() {
  rep(i, 0, 2005) d[i] = INF;
  d[0] = 0;
  rep(i, 0, n-1) {
    rep(j, 0, m) {
      if (d[a[j]] != INF && d[b[j]] > d[a[j]] + c[j]) {
        d[b[j]] = d[a[j]] + c[j];
      }
    }
  }
  ans = d[n-1];
  rep(i, 0, n) {
    rep(j, 0, m) {
      if (d[a[j]] != INF) {
        if (d[b[j]] > d[a[j]] + c[j]) {
          d[b[j]] = d[a[j]] + c[j];
          negative[a[j]] = true;
        }
        if (negative[a[j]]) negative[b[j]] = true;
      }
    }
  }
  return negative[n-1];
}

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
    cin >> n >> m;
    rep(i, 0, m) {
      cin >> a[i] >> b[i] >> c[i];
      a[i]--, b[i]--;
      c[i] = -c[i];
    }
    bool flag = negative_loop();
    if (flag) cout << "inf" << endl;
    else cout << -ans << endl;
    return 0;
}


Measured memory_bytes: 384
N, X = map(int, input().split())
x = list(map(int, input().split()))
for i in range(N):
    x[i] = abs(x[i] - X)
m = x[0]
import fractions
for i in range(1, N):
    m = fractions.gcd(m, x[i])
print(m)

Measured memory_bytes: 14224
class UnionFind(object):
    def __init__(self, num):
        self.parent = [-1 for i in range(num + 1)]

    def find(self, x):
        if self.parent[x] < 0:
            return x
        else:
            self.parent[x] = self.find(self.parent[x])
            return self.parent[x]

    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return

        if self.size(x) > self.size(y):
            self.parent[x] += self.parent[y]
            self.parent[y] = x
        else:
            self.parent[y] += self.parent[x]
            self.parent[x] = y

    def size(self, x):
        return -self.parent[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

n, m = map(int, input().split())
lis = []
count = 0
for i in range(m):
    lis.append(list(map(int, input().split())))
for i in range(m):
    u = UnionFind(n)
    for j in range(m):
        if i == j:
            continue
        u.unite(lis[j][0], lis[j][1])
    if not u.same(lis[i][0], lis[i][1]):
        count += 1
print(count)


Measured memory_bytes: 3064
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<vector>
#include<functional>
#include<algorithm>
#include<stdlib.h>
#include<string>
#include<string.h>
#define _USE_MATH_DEFINES
#include<math.h>
#include<deque>
#include<set>
#include<map>
#include<queue>
#include<iostream>
using namespace std;
typedef long long ll;
#define rep(i,a,b) for(auto i=a;i<b;i++)
#define all(_x) _x.begin(), _x.end()
#define r_sort(_x) sort(_x.begin(), _x.end(), std::greater<int>())
#define vec_cnt(_a, _n) (upper_bound(all(_a), _n) - lower_bound(all(_a), _n))
ll gcd(ll a, ll b) { return a % b == 0 ? b : gcd(b, a % b); }
ll lcm(ll a, ll b) { return (a / gcd(a, b)) * b; }
#define INF 1 << 30
const ll mod = 1000000007;
map<ll, int> prime_factor(ll num) {
	map<ll, int> mp;
	ll k = (ll)sqrt(num);
	mp[1]++;
	rep(i, 2, k + 1) {
		while (num % i == 0) {
			num /= i;
			mp[i]++;
		}
	}
	if (num != 1)mp[num]++;
	return mp;
}
int main() {
	ll A, B;
	cin >> A >> B;
	printf("%d\n", prime_factor(gcd(A, B)).size());
	return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
     
using namespace std;
     
typedef long long ll;
typedef pair<int,int>P;

#define INF INT_MAX;
#define F first
#define S second

int main(){
  int n;
  int ans=0;
  string s;
  string e8="E869120";

  scanf("%d",&n);
  for(int i=0;i<n;i++){
    cin>>s;
    if(s==e8) ans++;
  }

  printf("%d\n",ans);  
  
  return 0;
}



Measured memory_bytes: 3312
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<iomanip>
#include<math.h>
#include<complex>
#include<queue>
#include<deque>
#include<stack>
#include<map>
#include<set>
#include<bitset>
#include<functional>
#include<assert.h>
#include<numeric>
using namespace std;
#define REP(i,m,n) for(int i=(int)(m) ; i < (int) (n) ; ++i )
#define rep(i,n) REP(i,0,n)
using ll = long long;
const int inf=1e9+7;
const ll longinf=1LL<<60 ;
const ll mod=1e9+7 ;


void solve(int h,int w){
    vector<vector<int>> v(h*w);
    rep(i,h){
        rep(j,w-1){
            int x;
            cin>>x;
            if(!x){
                v[i*w+j].push_back(i*w+j+1);
                v[i*w+j+1].push_back(i*w+j);
            }
        }
        if(i==h-1)break;
        rep(j,w){
            int x;
            cin>>x;
            if(!x){
                v[i*w+j].push_back((i+1)*w+j);
                v[(i+1)*w+j].push_back(i*w+j);
            }
        }
    }
    vector<int> dist(h*w,inf);
    dist[0]=1;
    queue<int> que;
    que.push(0);
    while(que.size()){
        int cur=que.front();
        que.pop();
        for(auto to :v[cur]){
            if(dist[to]>dist[cur]+1){
                dist[to]=dist[cur]+1;
                que.push(to);
            }
        }
    }
    if(dist[h*w-1]==inf)cout<<0<<endl;
    else cout<<dist[h*w-1]<<endl;
}
int main(){
    int w,h;
    while(cin>>w>>h,w!=0)solve(h,w);
    return 0;
}


Measured memory_bytes: 3180
import java.io.PrintWriter;
import java.util.*;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		PrintWriter out = new PrintWriter(System.out);
		long N = Long.parseLong(sc.next());
		long max = 1;
		for(int i=1;i<=Math.round(Math.sqrt(N));i++) {
			if(N%i==0) {
				max = i;
			}
		}
		long pair = N/max;
		long result = (pair-1) + (max-1);
		out.println(result);

		out.flush();
	}
}


Measured memory_bytes: 23748
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define si(n) scanf("%d",&n);
#define PI acos(-1.0)
#define sl(n) scanf("%lld",&n);
#define sf(n) scanf("%lf",&n);
#define ss(n) scanf("%s",n);
#define for0(i,n) for(ll i=0;i<n;i++)
#define for1(i,n) for(ll i=1;i<=n;i++)
#define forc(i,j,n) for(ll i=j;i<n;i++)
#define pb push_back
#define sor(n) sort(n.begin(),n.end())
#define sorcmp(n) sort(n.begin(),n.end(),cmp)
#define rev(n) reverse(n.begin(),n.end())
#define pi(x)  prllf("%d",x);
#define pl(x)  prllf("%lld",x);
#define pf(x)  prllf("%.10lf",x);
#define ps(x)  prllf("%s",x);
#define en() prllf("\n");
#define random_shuffle(r...)random_shuffle(r,[](int _){return rand()%_;})
#define SQR(a) (a)*(a)
#define sp(x) fixed<<setprecision(x)
#define mod 100000007
#define endl '\n'
#define pii pair<int,int>
#define pll pair<ll,ll>
#define PIE acos(-1)
void fastio(){ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);}
template <typename T> T POW(T B,T P){ if(P==0) return 1; if(P&1) return B*POW(B,P-1);  else return SQR(POW(B,P/2));}
ll powmod(ll a, ll b){ll ans = 1;while(b){if(b&1) ans = ans*a%mod;a = a*a%mod;b >>= 1;}return ans;}
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
//Naive Solution as follows...


int main()
{


       double r;
       cin>>r;
       double res=2*PIE*r;
       cout<<sp(20)<<res<<endl;


}












Measured memory_bytes: 3764