akhauriyash/Code-Regression huggingface dataset:
H,W=map(int,input().split())
s=[input() for i in range(H)]
m=[[None]*W for i in range(H)]
if s[0][0]==".":
    m[0][0]=0
    t=0
else:
    m[0][0]=1
    t=1
for i in range(1,W):
    if s[0][i-1]!=s[0][i]:
        t+=1
    m[0][i]=t
t=m[0][0]
for i in range(1,H):
    if s[i-1][0]!=s[i][0]:
        t+=1
    m[i][0]=t
for i in range(1,H):
    for j in range(1,W):
        if s[i][j]==s[i-1][j] and s[i][j]==s[i][j-1]:
            m[i][j]=min(m[i-1][j],m[i][j-1])
        elif s[i][j]==s[i-1][j]:
            m[i][j]=min(m[i-1][j],m[i][j-1]+1)
        elif s[i][j]==s[i][j-1]:
            m[i][j]=min(m[i][j-1],m[i-1][j]+1)
        else:
            m[i][j]=min(m[i-1][j],m[i][j-1])+1
print((m[-1][-1]+1)//2)

Measured memory_bytes: 3188
#include <iostream>

using namespace std;
string s[305];
int n,i,j,add,ind,ans;
int main()
{
    cin>>n;
    for(i=0;i<n;i++)
    {
        cin>>s[i];
    }
    for(ind=0;ind<n;ind++)
    {
        add=n;
        for(i=0;i<n;i++)
            for(j=0;j<n;j++)
               if(s[j][(i+ind)%n]!=s[i][(j+ind)%n])
                 add=0;
        ans+=add;
    }
    cout<<ans;
    return 0;
}


Measured memory_bytes: 384
import sys,collections as cl,bisect as bs
sys.setrecursionlimit(100000)
input = sys.stdin.readline
mod = 10**9+7
Max = sys.maxsize
def l(): #intのlist
    return list(map(int,input().split()))
def m(): #複数文字
    return map(int,input().split())
def onem(): #Nとかの取得
    return int(input())
def s(x): #圧縮
    a = []
    if len(x) == 0:
        return []
    aa = x[0]
    su = 1
    for i in range(len(x)-1):
        if aa != x[i+1]:
            a.append([aa,su])
            aa = x[i+1]
            su = 1
        else:
            su += 1
    a.append([aa,su])
    return a
def jo(x): #listをスペースごとに分ける
    return " ".join(map(str,x))
def max2(x): #他のときもどうように作成可能
    return max(map(max,x))
def In(x,a): #aがリスト(sorted)
    k = bs.bisect_left(a,x)
    if k != len(a) and a[k] ==  x:
        return True
    else:
        return False
"""
def nibu(x,n,r):
    ll = 0
    rr = r
    while True:
        mid = (ll+rr)//2

    if rr == mid:
        return ll
    if (ここに評価入れる):
        rr = mid
    else:
        ll = mid+1
"""

n,k = m()

print(min(n%k,-n%k))






Measured memory_bytes: 38256
#include<bits/stdc++.h>
using namespace std;
#define N 1005
#define ll long long
#define debug(a) cout<<#a<<": ";for(auto i:a)cout<<i<<" ";cout<<endl;
#define trace(a) cout<<#a<<": "<<a<< endl;

int x[N],y[N];
string ans[N];
ll val[41];
string solve(ll x, ll y) {
	string str = "";
	for(int i = 31;i >= 0;i--) {
		if(abs(x) < abs(y)) {
			if(y < 0) {
				y += val[i];
				str.push_back('D');
			}
			else {
				y -= val[i];
				str.push_back('U');
			}
		}
		else {
			if(x < 0) {
				x += val[i];
				str.push_back('L');
			}
			else {
				x -= val[i];
				str.push_back('R');
			}
		}
	}
	reverse(str.begin(),str.end());
	return str;
}
int main() {
	ios_base::sync_with_stdio(false);cout.tie(0);cin.tie(0);
	int i,j,k,l,m,n,t;
	cin >> n;
	bool mark[2] = {false};
	for(i = 0;i < n;i++) {
		cin >> x[i] >> y[i];
		mark[abs(x[i]+y[i])&1] = true;
	}
	if(mark[0] && mark[1]) {
		cout << "-1" << endl;
		return 0;
	}
	vector<ll> v;
	if(mark[1]) {
		for(i = 0;i <= 31;i++) {
			val[i] = (1LL<<i);
			v.push_back(val[i]);
		}
		for(i = 0;i < n;i++) {
			ans[i] = solve(x[i],y[i]);
		}
	}
	else {
		for(i = 0;i <= 31;i++) {
			val[i] = (1LL<<i);
			v.push_back(val[i]);
		}
		for(i = 0;i < n;i++) {
			ans[i] = solve(x[i]-1,y[i]) + "R";
		}
		v.push_back(1);
	}
	cout << v.size() << endl;
	for(ll it : v) {
		cout << it << " ";
	}
	cout << endl;
	for(i = 0;i < n;i++) {
		cout << ans[i] << endl;
	}
}

Measured memory_bytes: 384
#include<iostream>
#include<math.h>
#include<algorithm>
#include<stdint.h>
#include<vector>
#include<deque>
#include<stack>
#include<string>
#include<cstring>
#include<time.h>
#include<array>
#include<iomanip>
#include<list>
#include<set>
#include<unordered_map>
#include<unordered_set>
#include<random>
#include<bitset>
#include <queue>
#include <map>


using namespace std;
using ll = long long;
using ull = unsigned long long;
using uint = unsigned int;
using ldouble = long double;


//BDD,ZDD,kdtree, bdtree,bicalc, bolonoy, doloney,chinesemod,segmenttree,daikusutora, saidairyuu, 2bugurahu, heirokenshutu, topologicalsort, kyourenketuseibun


#define PRI(s) cout << s << endl
#define PRIY PRI("Yes")
#define PRIN PRI("No")

int main() {
	int a, b;
	cin >> a >> b;
	PRI(max(max(a + b, a - b), a * b));
	return 0;
}

Measured memory_bytes: 3628
#include<bits/stdc++.h>
#define pii   pair<int,int>
#define hell  1000000007
#define rep(i,a,b)  for (__typeof(b) i=(a)-((a)>(b));i!=(b)-((a)>(b));i+=1-2*((a)>(b)))
#define boost ios_base::sync_with_stdio(false);cin.tie(0); cout.tie(0)
#define pb  push_back
#define all(a)      (a).begin(),(a).end()

typedef long long  ll;
using namespace std;

const ll INF=(1LL<<60)-1;
const int N=1e5+20;

int main(){
   
    boost;
	
	int n, g;
	cin >> n >> g;
	
	vector<int> score(n), p(n), c(n);
	
	for(int i = 0; i < n; i++){
		score[i] = (i+1)*100;
		cin >> p[i] >> c[i];
	}
	int ans = INT_MAX;
	
	for(int i = 0; i < (1 << n); i++){
		
		bitset<10> bs(i);
		int oo = g;
		int cnt = 0;
		
		for(int j = 0; j < n; j++){
			if(bs[j]){
				oo -= score[j]*p[j] + c[j];
				cnt += p[j];
			}
		}
		
		for(int j = n-1; j >= 0; j--){
			if(!bs[j]){
				int x = min(p[j], (max(0, oo) + score[j] - 1)/score[j]);
				oo -= score[j]*x;
				cnt += x;
			}
		}
		
		ans = min(ans, cnt);
		
	}
	
	cout << ans;
	
	cout << endl;
		 
   	return 0;
}

Measured memory_bytes: 256
import java.util.*;
import java.lang.*;

public class Main{
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		String s = sc.next();
		String t = sc.next();
		int mod = s.length();
		long ans = 0;
		TreeSet<Integer>[] index = new TreeSet[26];
		for (int i = 0; i < 26; i++) {
			index[i] = new TreeSet<>();
		}
		for (int i = 0; i < t.length(); i++) {
			TreeSet<Integer> tmp = index[t.charAt(i) - 'a'];
			if (tmp.size() == 0) {
				if (s.indexOf(t.charAt(i)) == -1) {
					ans = -1;
					break;
				} else {
					int in = 0;
					while (s.indexOf(t.charAt(i), in) != -1) {
						tmp.add(s.indexOf(t.charAt(i), in));
						in = s.indexOf(t.charAt(i), in) + 1;
					}
				}
			}
			int num;
			if (tmp.ceiling((int) (ans % mod)) == null) {
				num = tmp.first();
			} else {
				num = tmp.ceiling((int) (ans % mod));
			}
			if (num + 1 <= ans % mod) {
				ans = mod * (ans / mod + 1) + num + 1;
			} else {
				ans = mod * (ans / mod) + num + 1;
			}
		}
		System.out.println(ans);
	}
}


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

int main() {
	string s;
	cin >> s;
	int counter = 0;
	for (int j = 0; j < s.size(); j++) {
		for(int i = j+1; i < s.size(); i++) {
			if(s.at(j) == s.at(i)) {
				counter++;
			}
		}
	}
	if (counter == 0) {
		cout << "yes" << endl;
	}
	else {
		cout << "no" << endl;
	}
}

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

bool h[100];
bool w[100];

int main(){

  int H,W;
  cin >> H >> W;

  string S[100];

  for(int i = 0;i < H;i++)cin >> S[i];




  for(int i = 0;i < H;i++){
    bool flag = true;
    for(int j = 0;j < W;j++){
      if(S[i][j] != '.'){
        flag = false;
        break;
      }
    }
    if(flag)h[i] = true;
  }

  for(int j = 0;j < W;j++){
    bool flag = true;
    for(int i = 0;i < H;i++){
      if(S[i][j] != '.'){
        flag = false;
        break;
      }
    }
    if(flag)w[j] = true;
  }

  for(int i = 0;i < H;i++){
    for(int j = 0;j < W;j++){
      if(h[i] == false and w[j] == false)cout << S[i][j];
      if(h[i] == false and j == W-1)cout << '\n';
    }
  }

}


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

int nxt[200010][26];

signed main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    string s, t;
    cin >> s >> t;
    int tmp[26] = {};
    rep(i, 0, 26) tmp[i] = -1;
    string ss = s + s;
    for(int i = ss.size() - 1; i >= 0; i--){
        tmp[ss[i] - 'a'] = i;
        rep(j, 0, 26){
            nxt[i][j] = tmp[j];
        }
    }
    int cnt = 0;
    int prv = -1;
    for(int i = 0; i < t.size(); i++){
        int idx = nxt[prv + 1][t[i] - 'a'];
        if(idx == -1){
            cout << -1 << endl;
            return 0;
        }
        if(idx >= s.size()){
            cnt++;
            idx %= s.size();
        }
        prv = idx;
    }
    cout << cnt * (s.size()) + prv + 1 << endl;
}

Measured memory_bytes: 41424
import sys
#input = sys.stdin.readline
S=input()
if len(S)%2==1:
    print("No")
    exit()
ans=[]
count =0 
for i in range(len(S)):
    ans.append(S[i])
#print(ans)
while len(ans)>1:
    if ans[0]+ans[1]=="hi":
        ans.pop(0)
        ans.pop(0)
    else:
        print("No")
        exit()
    #print(ans)
print("Yes")

Measured memory_bytes: 3064
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Scanner;
import java.util.stream.IntStream;

public class Main{
	static final Scanner s=new Scanner(System.in);
	static IntStream REPS(int v){
		return IntStream.range(0,v);
	}
	static IntStream REPS(int l,int r){
		return IntStream.rangeClosed(l,r);
	}
	static IntStream INS(int n){
		return REPS(n).map(i->getInt());
	}
	static int getInt(){
		return Integer.parseInt(s.next());
	}

	public static void main(String[]$){
		int n=getInt();
		ArrayList<ArrayList<Integer>> in=new ArrayList<>();
		Boolean[]black=new Boolean[n];

		int blacks=0;

		black[0]=true;
		black[n-1]=false;

		for(int i=0;i<n;++i)
			in.add(new ArrayList<>());
		for(int i=0;i<n-1;i++) {
			int a=getInt()-1,b=getInt()-1;
			in.get(a).add(b);
			in.get(b).add(a);
		}

		ArrayDeque<Integer> stack=new ArrayDeque<>();
		stack.add(0);
		boolean[]searched=new boolean[n];
		searched[0]=true;

		loop:
		while(true) {
			for(int i:in.get(stack.peekLast())) {
				if(i==n-1) {
					stack.add(i);
					break loop;
				}
				if(!searched[i]) {
					searched[i]=true;
					stack.add(i);
					continue loop;
				}
			}
			stack.pollLast();
		}
		//System.out.println(stack);

		ArrayDeque<Integer> bfs=new ArrayDeque<>();
		for(int i=0;!stack.isEmpty();i++) {
			if(i%2==0) {
				int poll=stack.pollFirst();
				black[poll]=true;
				bfs.add(poll);
				++blacks;
			}else {
				black[stack.pollLast()]=false;
			}
		}


		while(!bfs.isEmpty()){
			for(int l=bfs.size();l>0;--l) {
				for(int i:in.get(bfs.poll())) {
					if(black[i]==null) {
						black[i]=true;
						bfs.add(i);
						blacks++;
					}
				}
			}
		}
		System.out.println(n-blacks<blacks?"Fennec":"Snuke");
	}
}


Measured memory_bytes: 72652
#if !defined(__clang__) && defined(__GNUC__)
#include <bits/stdc++.h>
#else
#include <cstdlib>
#include <climits>
#include <iostream>
#include <cstdint>
#include <vector>
#include <string>
#include <complex>
#include <bitset>
#include <queue>
#include <deque>
#include <stack>
#include <utility>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <regex>
#endif //  !defined(__clang__) && defined(__GNUG__)
#include <boost/lexical_cast.hpp>
#include <boost/algorithm/string.hpp>
#include <boost/multi_array.hpp>
#include <boost/optional.hpp>
#include <boost/math/common_factor_rt.hpp>

using namespace std;

int main()
{
    int64_t N, Y;
    std::cin >> N >> Y;

    for (int64_t m = 0; m <= N; ++m) {
        for (int64_t g = 0; g <= (N-m); ++g) {
            auto s = N - m - g;

            if (m*10000 + g*5000 + s*1000 == Y) {
                std::cout << m << " " << g << " " << s << std::endl;
                return 0;
            }
        }
    }

    std::cout << "-1 -1 -1" << std::endl;

    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int n,c;
string s;
int main(){
    cin>>n>>s;
    for(int i=0;i<n;i++){
        if(s[i]=='A'){
            if(s[i+1]=='B'){
                if(s[i+2]=='C')c++;
            }
        }
    }
    cout<<c<<endl;
}


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

bool IsDi(string test){
    if ((test == "0") or (test == "1") or (test == "2") or (test == "3") or (test == "4") or (test == "5") or (test == "6") or (test == "7") or (test == "8") or (test == "9")) return false;
    else return true;
}
int main() {
    string S, T;
    cin >> S >> T;

    string t;
    string tt;
    t = T.substr(0, T.length()-1);
    tt = T.substr(T.length()-1);

    if ((S == t) and (IsDi(tt))) cout << "Yes" << endl;
    else cout << "No" << endl;
}

Measured memory_bytes: 3604
fun main(args:Array<String>):Unit {
    repeat(readLine()!!.toInt()){
        val n = readLine()!!.toInt()
        val blocks = readLine()!!.split(' ').map(String::toInt).toIntArray()
        var maxUp = 0
        var minDown = 0
        for (i in 1 until n){
            if (maxUp < blocks[i] - blocks[i - 1])
                maxUp = blocks[i] - blocks[i - 1]
            if (minDown > blocks[i] - blocks[i - 1])
                minDown = blocks[i] - blocks[i - 1]
        }
        println("${maxUp} ${-minDown}")
    }
}


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

int mod = 1000000007;
int64_t large = 9223372036854775807;

int main()
{
    int N, M;
    cin >> N >> M;

    vector<vector<int>> list(N);
    vector<int> count(N); //各洞窟から何箇所行けるか
    for (int i = 0; i < M; i++)
    {
        int p, q;
        cin >> p >> q;
        p--, q--;
        list[p].push_back(q);
        list[q].push_back(p);
        count[p]++, count[q]++;
    }

    vector<bool> arrived(N, false); //訪問済みかどうか
    vector<int> from(N);            //どこから来たか
    int number = 0;                 //1から行ける洞窟の数
    queue<int> que;                 //訪問予定

    que.push(0);
    while (!que.empty())
    {
        int now = que.front();
        que.pop();
        for (int i = 0; i < count[now]; i++)
        {
            int search = list[now][i];
            if (!arrived[search]) //未訪問
            {
                arrived[search] = true;
                que.push(search);
                number++;
                from[search] = now;
            }
        }
    }
    if (number != N)
        cout << "No";
    else
    {
        cout << "Yes" << endl;
        for (int i = 1; i < N; i++)
            cout << from[i] + 1 << endl;
    }
}

Measured memory_bytes: 10580
import math

A, B, C, D = list(map(int,input().split()))

def gcd_(a, b):
    if a < b:  a, b = b, a
    if b == 0:  return a
    return gcd_(b, a % b)

def lcm_(x,y):
    return (x * y) // gcd_(x, y)

def f(x, y):
    return x // y

lcm = lcm_(C, D)
ret1 = A - 1 - f(A - 1, C) - f(A - 1, D) + f(A - 1, lcm)
ret2 = B - f(B, C) - f(B, D) + f(B, lcm)
ans = ret2 - ret1
print(ans)

Measured memory_bytes: 38384
#include<bits/stdc++.h>
#include<cmath>
#define SZ(x) ((int)x.size())
#include<vector>
#include<set>
#include<map>
#define ll long long
#define lli long long int
#define REP(i,a,b) for(ll i=a;i<b;i++)
#define pb push_back
#include<string>
#include<cctype>
#include<queue>
#define ii pair<int,int>
#include <sstream>
#define lli long long int
#define pairs pair<int,int>
#define mod 1000000007
#define endl "\n"
const double PI = 3.141592653589793238460;
typedef std::complex<double> Complex;
typedef std::valarray<Complex> CArray;
using namespace std;
ll pows(ll a,ll n,ll m)
{
	ll res=1;
	while(n)
	{
	if(n%2!=0)
	{
		res=(res*a)%m;
		n--;
		}
		else
		{
			a=(a*a)%m;
			n=n/2;
			}	
	}
	return res%m;
}
ll  gcd(ll a,ll b)
{
	if(b==0)
	return a;
	else 
	return gcd(b,a%b);
}
bool isprime(ll n)
{
	if(n==1)
	{
		return false;
	}
	for(ll i=2;i*i<=n;i++)
	{
		if(n%i==0)
		{
			return false;
		}
	}
	return true;
}
bool istrue(string s)
{
	int i=0;
	int j=s.size()-1;
	while(i<j)
	{
	if(s[i]==s[j])
	{
		i++;
		j--;
		}
		else
		{
			return false;
			}	
	}
	return true;
}
int main()
{
ios::sync_with_stdio(false);
	 cin.tie(0);
    cout.tie(0);
int k;
cin>>k;
for(int i=0;i<k;i++)
{
	cout<<"ACL";
}
    
}



 

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

typedef long long ll;
const ll INF = 1e18;
const int BIG = 1e9 + 555;
const int maxN = 100 * 1000 + 9;

int n;
int nxt[300][2 * maxN];
string s, t;

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

	cin >> s;
	cin >> t;
	
	n = s.size();

	for(int i = 0; i < n; i++){
		s.push_back(s[i]);
	}
		
	//cerr << s << '\n';

	for(char c = 'a'; c <= 'z'; c++){
		for(int i = (int)s.size() - 1; i >= 0; i--){
			nxt[c][i] = -1;
		}
		
		for(int i = (int)s.size() - 1; i >= 0; i--){
			if(i + 1 < (int)s.size()){
				nxt[c][i] = nxt[c][i + 1];
				if(s[i] == c){
					nxt[c][i] = i;
				}
			}
		}
	}
	
	int pos = -1;
	ll ans = 0;
	for(int i = 0, L = (int)t.size(); i < L; i++){
		if(nxt[t[i]][(pos + 1) % n] != -1){
			ans += nxt[t[i]][(pos + 1) % n] - ((pos + 1) % n) + 1;
			//cerr << (pos + 1) % n << ' ' << nxt[t[i]][(pos + 1) % n] << ' ' << nxt[t[i]][(pos + 1) % n] - ((pos + 1) % n) + 1 << '\n';
			pos = nxt[t[i]][(pos + 1) % n];
			pos %= n;
		} else {
			cout << "-1\n";
			return 0;
		}
	}
	
	cout << ans << '\n';

	return 0;
}

Measured memory_bytes: 21136
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vll = vector<ll>;
using vvll = vector<vll>;
using vc = vector<char>;
using vvc = vector<vc>;
using pll = pair<ll, ll>;
using stkll = vector<pll>;
const ll INF = 1LL << 60;
const ll MOD = 1e9 + 7;
#define rep(i, n) for (ll i = 0; i < (n); i++)
template<typename T1,typename T2> inline void chmin(T1 &a,T2 b){if(a>b) a=b;}
template<typename T1,typename T2> inline void chmax(T1 &a,T2 b){if(a<b) a=b;}
#ifndef ONLINE_JUDGE
    #define debug(x) cerr << #x << ": " << x << endl;
#else
    #define debug(x)
#endif

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

    string s;
    cin >> s;
    bool ok = false;
    for(auto c : s) if(c == '7') ok = true;
    if(ok) cout << "Yes" << endl;
    else cout << "No" << endl;
}


Measured memory_bytes: 3672
# ABC067c
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

n = int(input())
a = list(map(int, input().split()))


def cum(array):
    result = [0]
    for i in range(len(array)):
        result.append(array[i]+result[i])
    return result


cumArray = cum(a)
#print(cumArray)

ans = 10**12
for i in range(1, n):
    # print(i, cumArray[i], cumArray[n]-cumArray[i],
    #      abs(cumArray[n]-2*cumArray[i]))
    ans = min(ans, abs(cumArray[n]-2*cumArray[i]))

print(ans)


Measured memory_bytes: 23792
N = int(input())
red = []
blue = []
for i in range(N):
    a,b = map(int,input().split())
    red.append([a,b])
for i in range(N):
    c,d = map(int,input().split())
    blue.append([c,d])

blue.sort(key=lambda x: x[0])
used_red = [0]*N
for i in range(N):
    idx = -1
    for j in range(N):
        if used_red[j] != 0:
            continue
        if blue[i][0]-red[j][0]>0 and blue[i][1]-red[j][1]>0:
            if idx == -1 or red[idx][1]<red[j][1]:
                idx = j
    if idx!=-1:
        used_red[idx] += 1

print(sum(used_red))

Measured memory_bytes: 40400
import java.util.*;
public class Main{
    public static long memo[][];
    public static int w[],v[];
    public static int n;

    public static long dp(int i,int rw){
        if(rw<0) return (long) -1e9;
        if(i==n) return 0;
        if(memo[i][rw] != -1) return memo[i][rw];
        return memo[i][rw] = Math.max(dp(i+1,rw),v[i] + dp(i+1,rw - w[i])); 
    }

    public static void main(String args[]){
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        int s = sc.nextInt();
        w = new int[n];
        v = new int[n];
        memo = new long[n+1][s+1];
        for(long x[] : memo)
            Arrays.fill(x,-1L);
        for(int i=0;i<n;i++){
            w[i] = sc.nextInt();
            v[i] = sc.nextInt();
        }
        System.out.println(dp(0,s)); 
    } 
}

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

int main() {
  long long int A,B,ans;
  cin >>A >>B;
  long long int mini,maxi;
  mini=min(A,B);
  maxi=max(A,B);
  long long int c,d,gcm;
  while(mini!=0){
  c=mini;
  mini=maxi%mini;
  maxi=c;
  }
  ans=A*B/maxi;
  cout <<ans <<endl;
}

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

using ll = long long;
using P = pair<int, int>;

const int INF = 1e9;
const int MOD = 1e9 + 7;
const int MAX = 1e5 + 10;

ll dp[MAX];

int main() {
  int N, K;
  cin >> N >> K;
  ll h[N];
  for (int i = 0; i < N; i++) scanf("%lld", h + i);

  dp[0] = 0;
  for (int i = 1; i < N; i++) {
    ll mini = INF;
    for (int j = max(0, i - K); j < i; j++) {
      mini = min(mini, dp[j] + llabs(h[i] - h[j]));
    }
    dp[i] = mini;
  }

  cout << dp[N-1] << endl;
  return 0;
}


Measured memory_bytes: 1792
#include <iostream>
using namespace std;
int main(){
  int A, B;
  cin >> A >> B;
  
  int coin = 0;
  for (int i=0; i < 2; i++){
    if (A < B) {
      coin += B;
      B--;
    } else {
        coin += A;
        A--;
      }
  }
  cout << coin << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int (i) = 0; (i) < (n); ++(i))
#define rrep(i,n) for(int (i) = (n) - 1; (i) >= 0; --(i)) //Reversi rep
#define nfor(i,a,b) for(int (i) = (a); (i) < (b); ++(i)) //Natural for
#define rfor(i,a,b) for(int (i) = (b); (i) >= (a); --(i)) //Reversi for
#define ll long long
#define mod (1000000007)
#define YES cout << "YES" << endl;
#define Yes cout << "Yes" << endl;
#define NO cout << "NO" << endl;
#define No cout << "No" << endl;

int asc(const void *a, const void *b) {
    return *(int *)a - *(int *)b;
}

int desc(const void *a, const void *b) {
    return *(int *)b - *(int *)a;
}

int main()
{
    int a,b,c;
    cin >> a >> b >> c;
    if (a > c && c > b) {
        Yes;
    }else if(a < c && c < b){
        Yes;
    }else{
        No;
    }
    return 0;
}


Measured memory_bytes: 256
parseInt(x) = parse(Int, x)
function main()
	h, w = map(parseInt, split(readline()))
	n = parseInt(readline())
	a = map(parseInt, split(readline()))
	c = Array{Int}(h*w)
	count = 1
	for i in 1:n
		for j in 1:a[i]
			c[count] = i
			count += 1
		end
	end
	for i in 1:h
		if i%2 == 1
			for j in 1:w-1
				print(c[w*(i-1)+j], " ")
			end
			println(c[w*i])
		else
			for j in 1:w-1
				print(c[w*i+1-j], " ")
			end
			println(c[w*(i-1)+1])
		end
	end
end
main()

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

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; }

using ll = long long;
using lb = long double;
using P = pair<ll,ll>;
using graph = vector<vector<ll>>;

const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};
const ll INF = 1LL<<60;
const ll mod = 1000000007LL;

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

int main() {
  ll N,Q;
  cin>>N>>Q;
  vector<ll> v(N);
  rep(i,N) cin>>v[i];
  vector<ll> sumeven(N+1),sumodd(N+1),sumall(N+1);
  rep(i,N){
    if(i%2==0) sumeven[i+1]+=v[i];
    else sumodd[i+1] += v[i];
    sumall[i+1] += v[i];
  }
  rep(i,N) {
    sumeven[i+1] += sumeven[i];
    sumodd[i+1] += sumodd[i];
    sumall[i+1] += sumall[i];
  }

  rep(i,Q){
    ll X;
    cin>>X;
    ll ans = 0;
    if(X>=v[N-1]) ans = max(sumeven[N],sumodd[N]);
    else{
      ll l = -1,r = INF;
      while(r-l>1){
        ll mid = (r+l)/2;
        auto iter = upper_bound(v.begin(),v.end(),X+mid);
        auto itel = lower_bound(v.begin(),v.end(),X-mid);
        ll cnt = iter - itel;
        ll rest = v.end() - iter;
        if(rest<cnt) r = mid;
        else l = mid;
      }
      auto iter = lower_bound(v.begin(),v.end(),X+r);
      ll t = iter - v.begin();
      ans += sumall[N] - sumall[t];
      ll s = v.end() - iter;
      s = N - 2*s;
      if(s>=0) ans += max(sumeven[s],sumodd[s]);
    }
    cout<<ans<<endl;
  }
}

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

using namespace std;

typedef long long ll;
typedef vector<ll> vi;
typedef pair<ll, ll> ii;
typedef vector<ii> vii;
typedef long double ld;

ll n, x1, y_1, x2, y2, x, y, aux, M = 1e8;
ld PI = acos(-1);
bool rh, rv;

struct BIT {
	vi ft;

	BIT (int n) : ft(n+3) {}

	void update (int i, ll k) {
		while (i < ft.size()) {
			ft[i] = max(ft[i], k);
			i += (i & -i);
		}	
	}

	int query (int i) {
		ll res = 0;
		while (i) {
			res = max (res, ft[i]);
			i -= (i & -i);
		}
		return res;
	}
};

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

	cin >> x1 >> y_1 >> x2 >> y2 >> n;

	rv = x1 > x2;
	rh = y_1 > y2;

	if (rv) {
		x1 = M - x1;
		x2 = M - x2;
	}

	if (rh) {
		y_1 = M - y_1;
		y2 = M - y2;
	}

	vii punt;
	vi conj;
	while (n--) {
		cin >> x >> y;
		
		if (rv)
			x = M - x;
		if (rh)
			y = M - y;

		if (x1 <= x && x <= x2 && y_1 <= y && y <= y2) {
			punt.emplace_back(x, y);
			conj.push_back(y);
		}
	}

	BIT ft(conj.size()); 
	sort (punt.begin(), punt.end());
	sort (conj.begin(), conj.end());

	ll k = 0;
	for (int i = 0; i < punt.size(); i++) {
		tie (x, y) = punt[i];

		y = upper_bound(conj.begin(), conj.end(), y) - conj.begin();
		aux = ft.query(y) + 1;
		k = max(k, aux);
		ft.update(y, aux);
	}

	cout << fixed << setprecision(11);
	if (k > min(x2 - x1, y2 - y_1))
		cout << ld(100) * (x2 - x1 + y2 - y_1) - (20 - 5 * PI) * (k - 1) - (20 - 10 * PI);
	else
		cout << ld(100) * (x2 - x1 + y2 - y_1) - (20 - 5 * PI) * k;
	cout << endl;

	return 0;
}


Measured memory_bytes: 8304
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define mp make_pair
#define f first
#define s second

using namespace std;

const int inf = 1e9 + 7;
const long long INF = 1e18 + 7;
const int maxn = 2e5 + 7;

ll n, s, w[maxn], a[maxn];
ll dp[maxn], mx;

int main(){
	ios_base::sync_with_stdio(NULL);
	cin.tie(0);
	cout.tie(0);
	cin >> n >> s;
	for (int i = 1; i < maxn; i++)
		dp[i] = inf;
	dp[0] = 0;
	for (ll i = 1; i <= n; i++){
		cin >> w[i] >> a[i];
		for (ll j = 100000; j >= 0; j--){
			if (dp[j] != inf && dp[j] + w[i] <= s){
				dp[j + a[i]] = min(dp[j + a[i]], dp[j] + w[i]);	
			}
		}
	}
	for (ll i = 0; i < maxn; i++)
		if (dp[i] != inf)
			mx = max(mx, i);
	cout << mx;
	return 0;
} 


Measured memory_bytes: 3840
#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;

using i64 = long long;
using pii = pair<i64, i64>;

vector<pii> stk;
i64 sum, ant;
int n;

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

	cin >> n;
	for (int i = 0; i < n; ++i) {
		cin >> t;
		add = 1;
		while (!stk.empty() && stk.back().x > t) {
			add+= stk.back().y;
			sum-= stk.back().x * stk.back().y;
			stk.pop_back(); }
		sum+= t * add;
		ant+= sum;
		stk.emplace_back(t, add); }

	cout << ant << endl;

	return 0; }


Measured memory_bytes: 5616
#include <bits/stdc++.h>
#include <map>
#include <string.h>
#include <math.h>
#include <set>
#include <vector>
#include <algorithm>
#define rep(i, n) for(int i = 0; i < n; i++)
#define All(a) (a).begin(), (a).end()
using namespace std;

int main(){
    int a, b, k;
    cin >> a >> b >> k;
    int cnt = 0;
    for(int i = min(a, b); i > 0; i--){
        if(a % i == 0 & b % i == 0) cnt++;
        if(cnt == k){
            cout << i << endl;
            return 0;
        }
    }
}


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

int gcd(int x, int y) {
  if (x > y) swap(x,y);
  if (x == 0) return y;
  else if (y % x == 0) return x;
  else return gcd (x, y % x);
}
 
int main() {
  int N,X;
  cin >> N >> X;
  vector<int> x(N);
  for (int i = 0; i < N; i++) {
    cin >> x[i];
    x[i] = abs(x[i] - X);
  }
  int ans = 0;
  for (int i = 0; i < N; i++) ans = gcd(ans,x[i]);
  
  cout << ans << endl;  
}

Measured memory_bytes: 640
#include<bits/stdc++.h>
using namespace std;
#define FOR(i,l,r) for(long long i=(l);i<(r);++i)
#define REP(i,n) FOR(i,0,n)
#define REPS(i,n) FOR(i,0,n+1)
#define int long long
#define mp make_pair
#define pb push_back
#define eb emplace_back
const int MOD=1e9+7;
const int INF=1e18;
 
signed main(){
    int X,Y;cin>>X>>Y;
    Y/=X;
    int ans=1;
    while(Y>=2){
        ans++;
        Y/=2;
    }
    cout<<ans<<endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <queue>
#include <stack>
#include <algorithm>
#include <list>
#include <vector>
#include <complex>
#include <utility>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <climits>
#include <bitset>
#include <ctime>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <cassert>
#include <cstddef>
#include <iomanip>
#include <numeric>
#include <tuple>
#include <sstream>
#include <fstream>

using namespace std;
#define REP(i, n) for (int (i) = 0; (i) < (n); (i)++)
#define FOR(i, a, b) for (int (i) = (a); (i) < (b); (i)++)
#define RREP(i, a) for(int (i) = (a) - 1; (i) >= 0; (i)--)
#define FORR(i, a, b) for(int (i) = (a) - 1; (i) >= (b); (i)--)
#define DEBUG(C) cerr << #C << " = " << C << endl;
using LL = long long;
using VI = vector<int>;
using VVI = vector<VI>;
using VL = vector<LL>;
using VVL = vector<VL>;
using VD = vector<double>;
using VVD = vector<VD>;
using PII = pair<int, int>;
using PDD = pair<double, double>;
using PLL = pair<LL, LL>;
using VPII = vector<PII>;
#define ALL(a) begin((a)), end((a))
#define RALL(a) rbegin((a)), rend((a))
#define SORT(a) sort(ALL((a)))
#define RSORT(a) sort(RALL((a)))
#define REVERSE(a) reverse(ALL((a)))
#define MP make_pair
#define FORE(a, b) for (auto &&a : (b))
#define FIND(s, e) ((s).find(e) != (s).end())
#define EB emplace_back

const int INF = 1e9;
const int MOD = INF + 7;
const LL LLINF = 1e18;

void solve(int n) {
    int cnt = 0;
    FOR(i, 1, n) {
        int sum = i;
        int num = i;
        while (sum < n) {
            sum += ++num;
        }
        if (sum == n) cnt++;
    }
    cout << cnt << endl;
    return;
}

int main(void) {
    int n, p, m;
    string s;
    int a, b, c;
    while (cin >> n) {
        if (n == 0) return 0;
        solve(n);
        //return 0;
    }
}

Measured memory_bytes: 3088
#include <bits/stdc++.h>
#include <atcoder/all>
using namespace std;
using namespace atcoder;
using ll = long long;
using ull = unsigned long long;
using ld = long double;
using pii = pair<int, int>;
using piii = pair<pii, int>;
using pll = pair<ll, ll>;
using pli = pair<ll, int>;
using pil = pair<int, ll>;
using uint = unsigned int;
template <typename T>
using Graph = vector<vector<T>>;
const int MOD = 1e9 + 7;
const ld PI = acosl(-1);

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

    int N, M;
    cin >> N >> M;
    vector<vector<char>> c(N, vector<char>(M));
    for (int i = 0; i < N; ++i)
        for (int j = 0; j < M; ++j)
            cin >> c[i][j];

    mf_graph<int> mf(N * M + 2);
    int dy[] = {1, 0, -1, 0};
    int dx[] = {0, 1, 0, -1};
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < M; ++j) {
            if (c[i][j] == '#')
                continue;
            if ((i + j) & 1) {
                mf.add_edge(N * M, i * M + j, 1);
                for (int k = 0; k < 4; ++k) {
                    int ni = i + dy[k];
                    int nj = j + dx[k];
                    if (ni < 0 || nj < 0 || ni >= N || nj >= M)
                        continue;
                    if (c[ni][nj] == '#')
                        continue;
                    mf.add_edge(i * M + j, ni * M + nj, 1);
                }
            } else
                mf.add_edge(i * M + j, N * M + 1, 1);
        }
    }

    cout << mf.flow(N * M, N * M + 1) << '\n';

    auto edges = mf.edges();
    for (auto e : edges) {
        if (e.from < N * M && e.to < N * M && e.flow == 1) {
            int v1 = e.from, v2 = e.to;
            if (v1 > v2)
                swap(v1, v2);
            if (v2 - v1 == M) {
                c[v1 / M][v1 % M] = 'v';
                c[v2 / M][v2 % M] = '^';
            } else {
                c[v1 / M][v1 % M] = '>';
                c[v2 / M][v2 % M] = '<';
            }
        }
    }

    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < M; ++j) {
            cout << c[i][j];
        }
        cout << '\n';
    }

    return 0;
}


Measured memory_bytes: 5476
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<queue>
#include<deque>
#include<cmath>
#include<map>
#include<unordered_map>
#include<set>
#include<cstring>
#include<iomanip> //cout << fixed << setprecision(15) << x << endl;

using namespace std;
typedef long long ll;
const ll INF = 1e9 + 6;
const ll MOD = 1e9 + 7;
const ll LLINF = 1LL<<60;
#define Pint pair<int, int>
#define rng(i,a,b) for(int i=int(a);i<int(b);i++)
#define rep(i,b) rng(i,0,b)
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
/* -- template -- */

int main() {
    int H_1, M_1, H_2, M_2, K;
    cin >> H_1 >> M_1 >> H_2 >> M_2 >> K;
    int ans = (H_2 - H_1) * 60 + (M_2 - M_1) - K;
    cout << ans << endl;
}


Measured memory_bytes: 3632
#include <bits/stdc++.h>
#define pb push_back
#define rep(i,n) for(int i=0;i<(n);i++)
#define reps(i,n,s) for(int i=(s);i<(n);i++)
#define rrep(i,n) for(int i=(n-1);i>=0;i--)
#define rreps(i,n,s) for(int i=s;i>=n;i--)
#define MOD 1000000007
using ll = long long;
using namespace std;
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; }

int main(){
cin.tie(0);
ios::sync_with_stdio(false);
int a,b,c;
cin>>a>>b>>c;
int k;
cin>>k;
ll max_v=max(max(a,b),c);
cout<<pow(2,k)*max_v+(a+b+c-max_v)<<endl;
//system("pause");
return 0;
}

Measured memory_bytes: 384
import numpy
N, D = map(int, input().split())
listx = []
count = 0
for i in range(N):
    x = list(map(int, input().split()))
    listx.append(x)

for j in range(0, N):
    for k in range(j+1,N):
        a = numpy.array(listx[j])
        b = numpy.array(listx[k])
        u = b - a
        c = float(numpy.linalg.norm(u))
        if c.is_integer() :
            count += 1
print(count)

Measured memory_bytes: 12500
#include<cstdio>
#include<iostream>
using namespace std;
int main(void){
	int i,j,k,n,max,cnt,x,y,
		dx[]={1,1,0,-1},dy[]={0,1,1,1};
	char xy[255][256];
	while(1){
		max=0;
		cin>>n;
		if(n==0) break;
		for(i=0;i<n;i++) cin>>xy[i];
		for(i=0;i<n;i++){
			for(j=0;j<n;j++){
				if(xy[i][j]=='1'){
					for(k=0;k<4;k++){
						cnt=1;
						y=i; x=j;
						while(1){
							y=y+dy[k]; x=x+dx[k];
							if(y>=n||x>=n||y<0||x<0) break;
							if(xy[y][x]!='1')break;
							cnt++;
						}
						if(max<cnt) max=cnt;
					}
				}
			}
		}
		cout<<max<<endl;
	}
	return 0;
}

Measured memory_bytes: 3092
#include<iostream>
#include<cstring>
#include<vector>
#include<stack>
#include<cstdio>
#define MAXN 100007
using namespace std;
int main()
{
	int i,n,m,x,y,ans=0;
	scanf("%d%d",&n,&m);
	int v[MAXN];
	int maybe[MAXN];
	for(i=1;i<=n;++i)
	{
		v[i]=1;
		maybe[i]=0;
	}
	maybe[1]=1;
	for(i=0;i<m;++i)
	{
		scanf("%d%d",&x,&y);
		if(maybe[x]==1)
		{
			maybe[y]=1;
		}
		v[x]-=1;
		v[y]+=1;
		if(v[x]==0) maybe[x]=0;
	}
	for(i=1;i<=n;++i) if(maybe[i]==1) ++ans;
	printf("%d\n",ans);
	return 0;
}


Measured memory_bytes: 1024
sa=list(str(input()))
sb=list(str(input()))
sc=list(str(input()))
ac,bc,cc=0,0,0
sa.append("g")
sb.append("g")
sc.append("g")
now =1
while ac<len(sa) and bc<len(sb) and cc<len(sc):
    if now ==1:#A
        if sa[ac]=='b':
            now=2
        elif sa[ac]=='c':
            now=3
        elif sa[ac]=='g':
            print("A")
            break
        ac+=1
    elif now == 2:#B
        if sb[bc]=='a':
            now=1
        elif sb[bc]=='c':
            now=3
        elif sb[bc]=='g':
            print("B")
            break
        
        bc+=1
    else:#C
        if sc[cc]=='a':
            now=1
        elif sc[cc]=='b':
            now=2
        elif sc[cc]=='g':
            print("C")
            break

        cc+=1

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

using namespace std;

#define TRACE(x) cerr << #x << " " << x << endl
#define FOR(i, a, b) for (int i = (a); i < int(b); ++i)
#define REP(i, n) FOR(i, 0, n)
#define _ << " " <<

typedef long long llint;

const int MOD = 1e9 + 7;

int m, d;

int main(void) {
  scanf("%d%d", &m, &d);
  int sol = 0;
  for (int j = 1; j <= m; ++j) {
    for (int i = 1; i <= d; ++i) {
      int d1 = i % 10, d2 = i / 10;
      if (d1 >= 2 && d2 >= 2 && d1 * d2 == j) ++sol;
    }
  }
  printf("%d\n", sol);
  return 0;
}


Measured memory_bytes: 256
W , H ,x , y = map(int,input().split())
'''
horizon = min(W * y , W * (H - y))
vertical = min(H * x , H * (W - x))
# 直線上に存在すれば三角形の面積
if x == W or y == H or x == 0 or y == 0:
    print("{:.6f}".format((W * H) / 2) , end = ' ')
    print("0")
# 直線上にない時、長方形の面積
else:
    print('{:.6f}'.format(max(horizon , vertical)) , end = ' ')
    if horizon == vertical:
        print("1")
    else:
        print("0")
'''

print("{:.6f}".format(W * H /2) , end = ' ')
if x + x  == W and y + y == H:
    print('1')
else:
    print("0")

Measured memory_bytes: 2940
#include<bits/stdc++.h>
using namespace std;
int a[25],b[25],mx=0,n;
void funct(int at,int sum1,int sum2)
{
    if(at==n)
    {
        mx=max(mx,sum1-sum2);
        return;
    }
    funct(at+1,sum1+a[at],sum2+b[at]);
    funct(at+1,sum1,sum2);
}
int main()
{

    cin>>n;
    for(int i=0;i<n;i++)
        scanf("%d",&a[i]);
    for(int i=0;i<n;i++)
        scanf("%d",&b[i]);
    funct(0,0,0);
    cout << mx << endl;
}


Measured memory_bytes: 256
def search(table, visited, x, y):
    if visited[x][y]:
        print("LOOP")
        return

    visited[x][y] = True

    if table[x][y] == ">":
        search(table, visited, x, y+1)
    elif table[x][y] == "v":
        search(table, visited, x+1, y)
    elif table[x][y] == "^":
        search(table, visited, x-1, y)
    elif table[x][y] == "<":
        search(table, visited, x, y-1)
    elif table[x][y] == ".":
        print(y, x)
        return


while True:
    X, Y = [int(i) for i in input().split()]
    if X == 0 and Y == 0:
        break

    table = [[0 for i in range(Y)] for j in range(X)]
    visited = [[False for i in range(Y)] for j in range(X)]

    for i in range(X):
        L = input()
        for j in range(Y):
            table[i][j] = L[j]

    search(table, visited, 0, 0)


Measured memory_bytes: 6236
/* cerberus97 - Hanit Banga */

#include <iostream>
#include <iomanip>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <vector>
#include <algorithm>

using namespace std;

#define pb push_back
#define fast_cin() ios_base::sync_with_stdio(false); cin.tie(NULL)

typedef long long ll;
typedef long double ld;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;

const int N = 2e5 + 10, mod = 1e9 + 7;

ll fact[N], finv[N];
ll p2[N], p2_inv[N];

void update(ll &sum, int n, int &l, int &r, int new_l, int new_r);
ll choose(ll n, ll k);
ll pwr(ll x, ll e);

int main() {
	fast_cin();
	int b, w;
	cin >> b >> w;
	fact[0] = finv[0] = 1;
	p2[0] = p2_inv[0] = 1;
	for (int i = 1; i < N; ++i) {
		fact[i] = (i * fact[i - 1]) % mod;
		finv[i] = pwr(fact[i], mod - 2);
		p2[i] = (2 * p2[i - 1]) % mod;
		p2_inv[i] = pwr(p2[i], mod - 2);
	}
	ll sum = 0, sum2 = 0;
	int l = 0, r = 0;
	for (int i = 1; i <= b + w; ++i) {
		int new_l = max(0, i - w);
		int new_r = min(b - 1, i - 1);
		update(sum, i - 2, l, r, new_l, new_r);
		if (i - 1 >= w) {
			sum2 += (p2_inv[i - 1] * choose(i - 2, w - 1));
			sum2 %= mod;
		}
		ll ans = (sum * p2_inv[i]) % mod;
		ans += sum2;
		ans %= mod;
		cout << ans << '\n';
	}
}

void update(ll &sum, int n, int &l, int &r, int new_l, int new_r) {
	sum = (sum * 2) % mod;
	sum -= choose(n, l);
	sum -= choose(n, r);
	sum += 2 * mod;
	sum += choose(n + 1, l);
	while (l < new_l) {
		sum -= choose(n + 1, l);
		++l;
	}
	while (r < new_r) {
		++r;
		sum += choose(n + 1, r);
	}
	sum %= mod;
}

ll choose(ll n, ll k) {
	if (n < 0 or n < k) {
		return 0;
	}
	ll ans = fact[n];
	ans *= finv[k];
	ans %= mod;
	ans *= finv[n - k];
	ans %= mod;
	return ans;
}

ll pwr(ll x, ll e) {
	ll res = 1;
	while (e) {
		if (e & 1) {
			res = (res * x) % mod;
		}
		e /= 2;
		x = (x * x) % mod;
	}
	return res;
}

Measured memory_bytes: 8448
#include <bits/stdc++.h>
#include <cxxabi.h>
using namespace std;
using ll=long long;
using vi=vector<int>;
using vvi=vector<vi>;
using pii=pair<int,int>;
#define rep(i,n) range(i,0,n)
#define range(i,a,n) for(int i=a;i<n;i++)
#define all(a) a.begin(),a.end()
#define LINF    ((ll)1ll<60)
#define INF     ((int)1<<30)
#define EPS     (1e-9)
#define MOD     (1000000007)
template<class S,class T>ostream& operator<<(ostream&os,pair<S,T>p){os<<"["<<p.first<<", "<<p.second<<"]";return os;};
template<class S>auto&operator<<(ostream&os,vector<S>t){bool b=1;for(auto s:t)os<<(exchange(b,0)||strlen(abi::__cxa_demangle(typeid(S).name(),0,0,0))>20?"":" ")<<s;return os<<endl;}

constexpr int gcd(int a,int b){return b?gcd(b,a%b):a;}
constexpr int lcm(int a,int b){return a*b/gcd(a,b);}

int ma;

int solve(int p, int q, int r, int a, int n){
	int ans=0;
	if(p==0) return 1;
	if(n==0) return 0;
	for(int nq=r;a*nq<=ma;nq++){
		if(p*nq>n*q) break;
		if(p*nq>=q){
			int P=p*nq-q;
			int Q=q*nq;
			ans+=solve(P/gcd(P,Q),Q/gcd(P,Q),nq,a*nq,n-1);
		}
	}
	return ans;
}

int main(){
	cin.tie(0);
   	ios::sync_with_stdio(false);
	
	int p,q,n;
	while(cin>>p>>q>>ma>>n,p){
		cout<<solve(p,q,1,1,n)<<endl;
	}
	return 0;
}



Measured memory_bytes: 3128
using System;
using System.Collections.Generic;
using System.Linq;
using static System.Console;
using static System.Math;

class MainClass
{
    static void Main()
    {
        var NM = ReadLine().Split().Select(int.Parse).ToArray();
        int N = NM[0], M = NM[1];
        var ab = new int[M][];
        for (int i = 0; i < M; i++)
        {
            ab[i] = ReadLine().Split().Select(int.Parse).ToArray();
        }
        Array.Sort(ab, (x, y) => x[1].CompareTo(y[1]));
        int ans = 0;
        int last = -1;
        for (int i = 0; i < M; i++)
        {
            var ord = ab[i];
            if (ord[0] <= last) continue;
            else
            {
                ans++;
                last = ord[1] - 1;
            }
        }
        WriteLine(ans);
    }
}


Measured memory_bytes: 47952
#include <iostream>

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

using namespace std;

int main(){
  int x, y;
  cin >> x >> y;
  // 入力終了

  // 1.初めにBを押すか押さないか決める
  // 2.Aを0回以上押す
  // 3.最後にBを押すか押さないか決める
  int firstB[2] = {-1, 1}, secondB[2] = {-1, 1};

  int ans = 2000000000;
  int tmpx, tmpy;
  rep(i, 2){
    rep(j, 2){
      int tmp = 0;
      // 初めにBを押すなら-xを代入，押さないならxを代入
      tmpx = x*firstB[i];
      if(firstB[i] == -1)
	tmp++;
      // 最後にBを押すなら-yを代入，押さないならyを代入
      tmpy = y*secondB[j];
      if(secondB[j] == -1)
	tmp++;
      
      // tmpx > tmpyなら，Aを押しても題意を満たさない
      if(tmpx > tmpy)
	continue;

      // tmpxからtmpyまでAを押す
      tmp = tmp + tmpy - tmpx;
      ans = min(ans, tmp);
    }
  }

  // 解答
  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 3592
n,m = map(int,raw_input().strip().split(' '))
graph = [[] for i in range(n)]
for i in range(m):
  s,t = map(int,raw_input().strip().split(' '))
  graph[s].append(t)
  graph[t].append(s)
color = {}
c = 0
for i in range(n):
  if not i in color:
     que = [i]
     color[i] = c
     while len(que) > 0:
       u = que[0]
       for v in graph[u]:
          if not v in color:
             color[v] = c
             que.append(v)
       del que[0]
     c += 1
q = int(raw_input())
for i in range(q):
    s,t = map(int,raw_input().strip().split(' '))
    if color[s] == color[t]:
        print 'yes'
    else:
        print 'no'

Measured memory_bytes: 32084
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {

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

  public void run() {

    try(BufferedReader br = new BufferedReader(new InputStreamReader(System.in))) {

      int n = Integer.parseInt(br.readLine());
      int[][] graph = new int[n][n];
      String[] vInfo;
      int degree;

      for(int i=0,v=0; i<n; i++) {
        vInfo = br.readLine().split(" ");
        degree = Integer.parseInt(vInfo[1]);
        for(int j=0,k=2; j<degree; j++) {
          v = Integer.parseInt(vInfo[k++]);
          graph[i][v-1] = 1;
        }
      }

      StringBuilder buf = new StringBuilder(n*n);
      for (int[] vertex : graph) {
        for (int v : vertex) {
          buf.append(v).append(" ");
        }
        buf.setLength(buf.length()-1);
        buf.append("\n");
      }

      System.out.print(buf);
    }
    catch (IOException e) {
      System.out.println("IOException!");
    }
  }
}


Measured memory_bytes: 25388
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp> 
#include <functional>
using namespace __gnu_pbds; 
using namespace std;



typedef tree<long long, null_type, less<long long>, rb_tree_tag, 
             tree_order_statistics_node_update> 
    new_data_set; 
 
//defines
typedef long long ll;
typedef long double ld;
ll n,m,k,tar,a,b,d,e;
ll solve(ll t)
{
    cin>>n>>k;
    vector<string>v(n);
    for(ll i=0;i<n;i++)cin>>v[i];
    sort(v.begin(),v.end());
    for(auto p:v)cout<<p;

}

int32_t main()
{
#ifdef ONPC
    freopen("input.txt", "r", stdin);
#endif
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    ll t=1;
   //cin>>t;
    while(t--)
    {
        solve(t);
    }
    
        
    return 0;
}

Measured memory_bytes: 256
#include <iostream>

using namespace std;

int main(void)
{
	int H, W;

	while(true)
	{
		cin >> H >> W;
		
		if( (H==0) && (W==0) )
		{
			break;
		}
		else
		{
			for(int i = 0; i < H; i++)
			{
				for(int j = 0; j < W; j++)
				{
					cout << '#';
				}
				cout << endl;
			}
			cout << endl;
		}
	}

	return 0;
}

Measured memory_bytes: 1152
#include <bits/stdc++.h>
using namespace std;
#define REP(i, t) for (int i = 0; i < t; i++)

int main()
{
    int N;
    cin >> N;
    cout << (N % 111 == 0 ? N : (N / 111 + 1) * 111) << endl;

    return 0;
}


Measured memory_bytes: 256