akhauriyash/Code-Regression huggingface dataset:
/******************************************************************************
 
рассвет. 
 
*******************************************************************************/
#include <bits/stdc++.h>
typedef long long int lli;
typedef unsigned long long int ulli;
typedef long double ld;
#define rapgame ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define pb push_back
#define eb emplace_back
#define vi vector <int>
#define vlli vector <lli>
#define vulli vector <ulli>
#define vchar vector <char>
#define vstr vector <string>
#define vb vector <bool>
#define fst first
#define sec second
#define all(a) (a).begin(),(a).end()
#define srt(a) sort(a.begin(),a.end())
#define rev(a) reverse(a.begin(),a.end())
#define vpii vector <pair <int,int> >
#define pii pair <int,int> 
#define vplli vector <pair <lli,lli> >
#define vvi vector <vector <int> >
#define vvlli vector <vector <lli> >
#define vvpii vector <vector <pair <int,int>> >
#define fr(i,n) for (int i = 0; i < (n); ++i)
#define frbig(i,n) for (lli i = 0; i < (n); ++i)
#define fra(i,a,n) for (lli i = a; i < (n); ++i)
#define run(c,s) for(auto c:s) 
#define read(n) int n; cin >> n;
#define readchar(n) char n; cin >> n;
#define readstr(n) string n; cin >> n;
#define readarr(a,n) fr(i,n) cin >> a[i];
#define read2(x,y) int x,y; cin >> x >> y;
#define read2ll(x,y) long long int x,y; cin >> x >> y;
#define readll(n) lli n; cin >> n;
#define watch(x) cout << (#x) << " is " << (x) << endl
#define print_array(x) fr(i,x.size()) cout << x[i] << " ";
using namespace std;
 
const lli MOD=1e9+7;
const lli MAXN=1e6+1;
const ld PI=acos(-1);
 
int main(){
    rapgame
    //freopen("unionday.in", "r", stdin);
    //freopen("unionday.out", "w", stdout);
    int t=1;
    //cin>>t;
    while(t--){
        char x;
        cin >> x;
        if(x>='a') cout << "a";
        else cout << "A";
    }
    return 0;
}

Measured memory_bytes: 3608
#define _USE_MATH_DEFINES
#include <cstdio>
#include <iostream>
#include <sstream>
#include <fstream>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <complex>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <bitset>
#include <numeric>
#include <limits>
#include <climits>
#include <cfloat>
#include <functional>
#include <iterator>
using namespace std;

int main()
{
    int h, w;
    cin >> h >> w;

    int cnt = 0;
    for(int i=0; i<h*w; ++i){
        char c;
        cin >> c;
        if(c == '#')
            ++ cnt;
    }

    if(cnt == h + w - 1)
        cout << "Possible" << endl;
    else
        cout << "Impossible" << endl;

    return 0;
}

Measured memory_bytes: 764
#include <algorithm>
#include <iostream>
#include <vector>

using namespace std;

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

#define MOD 1000000007
#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 ALL(a) a.begin(), a.end()

int main() {
  string a;
  cin >> a;
  int n = a.size();
  int cnt[26] = {};
  REP(i, n) cnt[a[i] - 'a']++;
  ll ans = 1ll * n * (n - 1) / 2 + 1;
  REP(i, 26) ans -= 1ll * cnt[i] * (cnt[i] - 1) / 2;
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 640
N, K = map(int, input().split())
A = [int(i) for i in input().split()]

def gcd(a, b) :
    if b > a : 
        a, b = b, a
    
    while b != 0 :
        a, b = b, a % b
    return a

def solve() :
    x = A[0]

    for a in A[1:] :
        x = gcd(x, a)
        
    for a in A :
        if a >= K and (a - K) % x == 0 :
            return 'POSSIBLE'
            
    return 'IMPOSSIBLE'
    
print(solve())

Measured memory_bytes: 62576
def _main():
  N = int(input())
  lst = list(map(int, input().split()))
  K = int(input())
  key_lst = list(map(int, input().split()))

  ans = 0
  for k in range(K):
    if binary_search(N, lst, key_lst[k]): ans += 1
  print(ans)

def binary_search(N ,lst, key):
  left = 0
  right = N
  while left < right:
    mid = (left + right) // 2
    if lst[mid] == key:
      return True
    elif key < lst[mid]:
      right = mid
    else:
      left = mid + 1
  return False

if __name__ == '__main__':
  _main()


Measured memory_bytes: 16712
num = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 100, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 200, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 300, 293, 307, 311, 313, 317, 331]
prime = list()

cnt = 0
for i in range(331, 100004):
  for j in num:
    if i%j == 0:
      cnt = 1
  if cnt == 0:
    prime.append(i)
  cnt = 0

primes = num + prime

x = int(input())

if x in primes:
  print(x)
else:
  if x%2 == 0:
    x -= 1
  while x > 0:
    x += 2
    if x in primes:
      print(x)
      break

Measured memory_bytes: 3520
import java.util.*;
class Main
{
    public static void main (String[] args)
    {
        String ans = judge()? "TBD" : "Heisei";
        System.out.println(ans);
    }
    static boolean judge(){
        Scanner sc = new Scanner(System.in);

        String s = sc.next();
        String y= "", m = "", d = "";
        for(int i = 0; i < 2; i++){
            m += s.charAt(i + 5);
            d += s.charAt(i + 8);
        }
        int month = Integer.parseInt(m), date = Integer.parseInt(d);
        if(month < 4) return false;
        if(month == 4 && date <= 30) return false;
        return true;
    }
}

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

const double EPS = 1e-10;
const ll INF = 100000000;
const ll MOD = 1000000007;

int n;
int p[1000], x[1000];
vector<int> chi[1000];
ll dp[1000];
bool ddp[5002];

bool dfs(int v) {
    if(chi[v].size() == 0) {
        dp[v] = 0;
        return true;
    }
    rep(i,chi[v].size()) {
        if(!dfs(chi[v][i])) {
            return false;
        }
    }
    memset(ddp, false, sizeof(ddp));
    int sum = 0;
    rep(i,chi[v].size()) {
        sum += x[chi[v][i]]+dp[chi[v][i]];
    }
    ddp[0] = true;
    rep(i,chi[v].size()) {
        for(int j = x[v]; j >= 0; j--) {
            if(ddp[j] == false) continue;
            if(j+dp[chi[v][i]] <= x[v]) {
                ddp[j+dp[chi[v][i]]] |= ddp[j];
            }
            if(j+x[chi[v][i]] <= x[v]) {
                ddp[j+x[chi[v][i]]] |= ddp[j];
            }
            if(x[chi[v][i]] != 0 && dp[chi[v][i]] != 0) ddp[j] = false;
        }
    }
    for(int j = x[v]; j >= 0; j--) {
        if(ddp[j]) {
            sum -= j;
            if(sum >= 5001) {
                sum = 5001;
            }
            dp[v] = sum;
            return true;
        }
    }
    return false;
}

int main(){
    cin >> n;
    rep(i,n-1) cin >> p[i];
    rep(i,n) cin >> x[i];
    rep(i,n-1) {
        p[i]--;
        chi[p[i]].push_back(i+1);
    }
    if(!dfs(0)) {
        cout << "IMPOSSIBLE" << endl;
    } else {
        cout << "POSSIBLE" << endl;
    }
}
































Measured memory_bytes: 384
#include<iostream>
#include<stdio.h>
using namespace std;

int main(){
  int i,j,k;
  int n1=0,n2=0;
  int v[5];
  int temp;

  for(i=0;i<5;i++){
    cin>>v[i];
  }
  for(i=0;i<4;i++)
    for(j=0;j<4;j++)
      if(v[j+1] > v[j]){
      temp = v[j];
      v[j] = v[j+1];
      v[j+1] = temp;
      }

  for(i=0;i<4;i++){
    printf("%d ",v[i]);
	   }
      cout<<v[4]<<endl;

    return 0;
  }

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

int gcd(int x, int y) {
    if (x % y == 0) {
        return y;
    } else {
        return gcd(y, x % y);
    }
}

int lcm(int x, int y) { return x * y / gcd(x, y); }

int main() {
    //
    int num;
    cin >> num;

    cout << lcm(num, 360) / num;
    //
}

Measured memory_bytes: 3588
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
	string s,t;cin>>s>>t;
	int an=1000;
	for(int u=0;u<s.size()-t.size()+1;u++){
		int cn=0,v=u;
		for(char x:t){
			if(x!=s[v]) cn++;
		v++;}
		an=min(an,cn);
	}
	cout<<an;
}

Measured memory_bytes: 3624
#include<bits/stdc++.h>
#include<unordered_set>
#include<unordered_map>
using namespace std;
#define REP(i,m,n) for(int i=(m);i<(n);i++)
#define rep(i,n) REP(i,0,n)
#define pb push_back
#define all(a) a.begin(),a.end()
#define rall(c) (c).rbegin(),(c).rend()
#define mp make_pair
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef long double ld;
const ll inf=1e9+7;
const ll mod=1e9+7;
int main(){
    ll n,m;cin>>n>>m;
    vector<queue<ll> >a(n);
    rep(i,n){
        rep(j,m){
            ll b;cin>>b;
            a[i].push(b);
        }
    }
    set<ll>st;
    ll ans=n;
    while(st.size()<m){
        rep(i,n){
            while(st.find(a[i].front())!=st.end())a[i].pop();
        }
        vector<ll>cnt(m+1,0);
        ll ma=0;
        rep(i,n){
            cnt[a[i].front()]++;
            ma=max(ma,cnt[a[i].front()]);
        }
        ans=min(ma,ans);
        rep(i,n){
            if(ma==cnt[a[i].front()])st.insert(a[i].front());
        }
    }
    cout<<ans<<endl;
}

Measured memory_bytes: 1024
fun main(args: Array<String>) {
    abc138c()
}

fun abc138c() {
    val n = readLine()!!.toInt()
    val vList = readLine()!!.split(" ").map { it.toDouble() }.toTypedArray().sortedArray()

    if (vList.size < 2) {
        println(vList[0])
        return
    }

    var sum = (vList[0] + vList[1]) / 2.toDouble()
    (2 until n).forEach() {
        sum = (sum + vList[it]) / 2
    }

    println(sum)
}


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

int main(){
  int n;
  cin >> n;
  vector<int> a(n);
  vector<int> b(n - 1);
  for(int i = 0; i < n - 1; i++){
    cin >> b.at(i);
  }
  for(int i = 0; i < n - 1; i++){
    if(i == 0){
      a.at(0) = b.at(0);
      a.at(1) = b.at(0);
      continue;
    }
    if(b.at(i) > a.at(i)){
      a.at(i + 1) = b.at(i);
    }
    else if(b.at(i) <= a.at(i)){
      a.at(i) = b.at(i);
      a.at(i + 1) = b.at(i); 
    }
  }
  int answer = 0;
  for(auto x : a){
    answer += x;
  }
  cout << answer << endl;
}


Measured memory_bytes: 256
package main
import "fmt"
func main() {
  var n,a,b,c,d int64
  fmt.Scan(&n,&a,&b,&c,&d)
  var min,max int64 = 0,n
  for max-min > 1 {
    var m int64 = (max+min)/2
    if (n-1-m)*c-m*d <= b-a && b-a <= -m*c+(n-1-m)*d {
      fmt.Println("YES")
      return
    }
    if b-a < (n-1-m)*c-m*d {
      min = m
    } else {
      max = m
    }
  }
  fmt.Println("NO")
}

Measured memory_bytes: 512
#include<iostream>

using namespace std;

struct card{
    char suit,value;
};

void selection_sort(card a[],int n)
{
    for(int i=0;i<n-1;i++)
    {
        int Min=i;

        for(int j=i+1;j<n;j++)
        {
            if(a[Min].value>a[j].value)
            {
                Min=j;
            }
        }
        swap(a[Min],a[i]);
    }
}

void bubble_sort(card a[],int n)
{
    bool flag=true;

    for(int i=0;i<n-1&&flag;i++)
    {
        flag=false;
        for(int j=0;j<n-1-i;j++)
        {
            if(a[j].value>a[j+1].value)
            {
                swap(a[j],a[j+1]);
                flag=true;
            }
        }
    }
}

bool IsStable(card a[],card b[],int n)
{
    for(int i=0;i<n;i++)
    {
        if(a[i].suit!=b[i].suit)
        {
            return false;
        }
    }
    return true;
}

void print(card a[],int n)
{
    for(int i=0;i<n;i++)
    {
        if(i)
        {
            cout<<" ";
        }
        cout<<a[i].suit<<a[i].value;
    }

    cout<<endl;
}

int main()
{
    card a[37],b[37];
    int n;

    cin>>n;

    for(int i=0;i<n;i++)
    {
        cin>>a[i].suit>>a[i].value;

        b[i]=a[i];
    }

    bubble_sort(a,n);
    selection_sort(b,n);

    print(a,n);

    cout<<"Stable"<<endl;

    print(b,n);

    if(IsStable(a,b,n))
    {
        cout<<"Stable"<<endl;
    }else
    {
        cout<<"Not stable"<<endl;
    }


    return 0;
}



Measured memory_bytes: 3092
#include<bits/stdc++.h>
#define rep(i,start,lim) for(lld i=start;i<lim;i++)
#define repd(i,start,lim) for(lld i=start;i>=lim;i--)
#define scan(x) scanf("%lld",&x)
#define print(x) printf("%lld ",x)
#define f first
#define s second
#define pb push_back
#define mp make_pair
#define br printf("\n")
#define sz(a) lld((a).size())
#define YES printf("YES\n")
#define NO printf("NO\n")
#define all(c) (c).begin(),(c).end()
#define INF         1011111111
#define LLINF       1000111000111000111LL
#define EPS         (double)1e-10
#define MOD         1000000007
#define PI          3.14159265358979323
using namespace std;
typedef long double ldb;
typedef long long lld;
lld powm(lld base,lld exp,lld mod=MOD) {lld ans=1;while(exp){if(exp&1) ans=(ans*base)%mod;exp>>=1,base=(base*base)%mod;}return ans;}
lld ctl(char x,char an='a') {return (lld)(x-an);}
char ltc(lld x,char an='a') {return (char)(x+an);}
#define bit(x,j) ((x>>j)&1)
typedef vector<lld> vlld;
typedef pair<lld,lld> plld;
typedef map<lld,lld> mlld;
typedef set<lld> slld;
#define sync ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define mxm(a,b) a = max(a,b)
#define mnm(a,b) a = min(a,b)
#define endl '\n'
#define fre freopen("1.in","r",stdin); freopen("1.out","w",stdout);
#define N 1005
int main()
{
    //sync;
    lld mk[N], prv[N];
    rep(i,1,N+1) if(i*i <= N) mk[i*i] = 1; else break;
    rep(i,1,N+1) if(i*i*i <= N) mk[i*i*i] = 1; else break;
    rep(i,1,N+1) if(i*i*i*i <= N) mk[i*i*i*i] = 1; else break;
    rep(i,1,N+1) if(i*i*i*i*i <= N) mk[i*i*i*i*i] = 1; else break;
    rep(i,1,N+1) if(i*i*i*i*i*i <= N) mk[i*i*i*i*i*i] = 1; else break;
    rep(i,1,N+1) if(i*i*i*i*i*i*i <= N) mk[i*i*i*i*i*i*i] = 1; else break;
    rep(i,1,N) if(mk[i]) prv[i]=i; else prv[i]=prv[i-1];
    lld X;
    cin>>X;
    cout<<prv[X];
    return 0;
}

Measured memory_bytes: 256
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <map>
#include <utility>
#include <set>
#include <iostream>
#include <memory>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <sstream>
#include <deque>
#include <complex>
#include <stack>
#include <queue>
#include <cstdio>
#include <cctype>
#include <cstring>
#include <ctime>
#include <iterator>
#include <bitset>
#include <numeric>
#include <list>
#include <iomanip>
using namespace std;
#define ll int64_t
const long MOD = 1e9 + 7;
const long LINF = 1e13;
const long LLINF = 1e18;
const long ALPHABET = 26;

template <class T>
void Swap(T& r, T& l) {
  T tmp = r;
  r = l;
  l = tmp;
}



int main() {

  long s, m;
  cin >> s ;


  long ss =s;

  vector<bool> li(10000000,false);
  // li[s]=true;


  long ans =0;

  while(true){
    ans++;

    if (li[s]==true)break;

    li[s]=true;

    if (s%2==0){//奇数
      s = s/2;
    }else{//偶数
      s=s*3+1;
    }
    
  }




  cout << ans;

  // cout << ((ans)? "Yes": "No");




}




















Measured memory_bytes: 1408
#include <bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(false); cin.tie(0);
#define FOR(i,s,n) for(int i = s; i < (n); i++)
#define REP(i,n) FOR(i,0,n)
#define ALL(n) (n).begin(), (n).end()
#define RALL(n) (n).rbegin(), (n).rend()
#define ATYN(n) cout << ( (n) ? "Yes":"No") << '\n';
#define CFYN(n) cout << ( (n) ? "YES":"NO") << '\n';
#define OUT(n) cout << (n) << '\n';
using ll = long long;
using ull = unsigned long long;
using pii = pair<int,int>;
using pll = pair<ll,ll>;

int main(void)
{
    IOS
    int n; cin >> n;
    vector<int> a(n+1), b(n);
    REP(i,n+1) cin >> a[i];
    REP(i,n) cin >> b[i];

    int next = 0;
    ll ans = 0;
    REP(i,n) {
        int c = max(a[i] - next,0);
        next = max(b[i]-c,0);
        c = max(0,c-b[i]);
        ans += a[i] - c;
    } 
    ans += min(a[n], next);

    cout << ans << '\n';

    return 0;
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int N;
  cin >> N;
  int N1 = N;
  int total = 0;
  int i = 1;
  int ten = 10;
  while (N >= ten){
    i++;
    ten *= 10;
  }
  while (i > 0){
    total += N1/(ten/10);
    N1 = N1 % (ten/10);
    ten /= 10;
    i--;
    if (N1 == 0){
      break;
    }
  }
  if (N % total == 0){
    cout << "Yes" << endl;
  }
  else{
    cout << "No" << endl;
  }
}

Measured memory_bytes: 256
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int max(int a, int b) {
	return a > b ? a : b;
}

char* longest_subsequence(char *s, char *t) {
	int a = strlen(s), b = strlen(t);
	int dp[a+1][b+1];

	int i, j;
	for (i = 0; i <= a; i++) {
		for (j = 0; j <= b; j++) {
			if (i == 0 || j == 0) {
				dp[i][j] = 0;
				continue;
			}

			if (s[i-1] == t[j-1]) {
				dp[i][j] = 1 + dp[i-1][j-1];
			} else {
				dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
			}
		}
	}

	int len = dp[a][b];
	char *lcs = (char*)malloc((len+1)*sizeof(char));
	lcs[len] = '\0';
	i = a; j = b;
	while (i > 0 && j > 0) {
		if (s[i-1] == t[j-1]) {
			lcs[--len] = s[i-1];
			i--; j--;
			continue;
		} else if (dp[i-1][j] > dp[i][j-1]) {
			i--;
		} else if (dp[i-1][j] <= dp[i][j-1]) {
			j--;
		}
	}
	return lcs;
}

int main() {
	char s[3000], t[3000];
	scanf("%s %s", s, t);
	char *lcs = longest_subsequence(s, t);
	printf("%s\n", lcs);
	free(lcs);
}


Measured memory_bytes: 35328
N = int(input())
if 1 <= N <= 10**6:
    Sum = 0
    for i in range(1, N+1):
        if i % 3 == 0 and i % 5 == 0:
            continue
        elif i % 3 == 0:
            continue
        elif i % 5 == 0:
            continue
        Sum = Sum + i
    print(Sum)
else:
    pass



Measured memory_bytes: 9152
#include<stdio.h>
int main(void)
{
	int a,b ;
	scanf("%d %d",&a,&b);
	if(a<b){
		printf("a < b\n");
	}
	else if(a>b){
		printf("a > b\n");
	}
	else{
		printf("a == b\n");
	}
	return 0 ;
}

Measured memory_bytes: 580
#include <cstdio>
#include <cstring>

using namespace std;

class Inning {
 public:
  enum class Event { Hit, Homerun, Out };
  Inning() : bases_({ false, false, false }), out_count_(0), score_(0) {}
  int GetScore() { return score_; }
  bool IsFinished() { return out_count_ >= 3; }
  void Update(Event event) {
    switch (event) {
      case Event::Hit:
        if (bases_[2]) { ++score_; }
        bases_[2] = bases_[1];
        bases_[1] = bases_[0];
        bases_[0] = true;
        break;
      case Event::Homerun:
        score_ += CountRunners() + 1;
        bases_[2] = false;
        bases_[1] = false;
        bases_[0] = false;
        break;
      case Event::Out:
        ++out_count_;
        break;
    }
  }
 private:
  int CountRunners() {
    int count = 0;
    for (int i = 0; i < 3; ++i) { if (bases_[i]) { ++count; } }
    return count;
  }
  bool bases_[3];
  int out_count_;
  int score_;
};

Inning::Event ToEvent(const char *event_name) {
  if (strcmp(event_name, "HIT") == 0) { return Inning::Event::Hit; }
  if (strcmp(event_name, "HOMERUN") == 0) { return Inning::Event::Homerun; }
  return Inning::Event::Out;
}

int main() {
  int n;
  scanf("%d", &n);
  for (int i = 0; i < n; ++i) {
    Inning inning;
    while (!inning.IsFinished()) {
      char event[40];
      scanf("%s", event);
      inning.Update(ToEvent(event));
    }
    printf("%d\n", inning.GetScore());
  }
  return 0;
}

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

void solve() {
    string S; cin >> S;
    if(S.back() == 's') S += "es";
    else S += 's';
    cout << S << '\n';
}

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


Measured memory_bytes: 3684
import java.util.Scanner;
public class Main{
    public static void calc(double x1, double y1, double x2, double y2, double px, double py){
        if(y1 == y2)
            System.out.println(px + " " + (py - 2*(py - y1)));
        else if(x1 == x2)
            System.out.println((px - 2*(px - x1)) + " " + py);
        else{
            double katamuki1 = (y2 - y1)/(x2 - x1);
            double seppen1 = -1.0 * katamuki1 * x1 + y1;
            double katamuki2 = -1.0 / katamuki1;
            double seppen2 = -1.0 * katamuki2 * px + py;
            double ansx = (seppen2 - seppen1)/(katamuki1 - katamuki2);
            double ansy = ansx * katamuki1 + seppen1;
            System.out.println((px - 2*(px - ansx)) + " " + (py- 2 * (py - ansy)));
        }
    }
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int x1 = sc.nextInt();
        int y1 = sc.nextInt();
        int x2 = sc.nextInt();
        int y2 = sc.nextInt();
        int q = sc.nextInt();
        for(int i = 0 ; i < q ; i++){
            int px = sc.nextInt();
            int py = sc.nextInt();
            calc((double)x1,(double)y1,(double)x2,(double)y2,(double)px,(double)py);
        }
    }
}


Measured memory_bytes: 34916
#include <iostream>
#include <string>
#include <vector>
#define range(i, r) for(int i=0;i<r;i++)
#define ranges(i, l, r) for(int i=l;i<r;i++)
#define MODs 1000000007;
typedef long long int ll;
using namespace std;

int main(int argc, char const *argv[]) {
  ll N;
  std::cin >> N;
  std::vector<ll> C(N);
  range(i, N) std::cin >> C[i];
  std::vector<ll> dp(C.size()+1);
  std::vector<ll> v(1000000, 0);
  dp[0] = dp[1] = 1;
  v[C[0]] = 1;
  ranges(i, 2, N+1){
    if(C[i-1]==C[i-2]){
      dp[i] = dp[i-1];
    }else{
      dp[i] = (dp[i-1] + v[C[i-1]])%MODs;
      v[C[i-1]] = dp[i];
      //std::cout << dp[i] << v[C[i-1]] << '\n';
    }
  }
  std::cout << dp[N] << '\n';
  return 0;
}


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

using lint = long long;

template <int MOD_>  struct modnum {
private:
	using lint = long long;
	lint v;
	static int modinv(int a, int m) {
		a %= m;
		assert(a);
		return a == 1 ? 1 : int(m - lint(modinv(m, a)) * lint(m) / a);
	}
public:
	static constexpr int MOD = MOD_;
	modnum() : v(0) {}
	modnum(lint v_) : v(int(v_ % MOD)) { if (v < 0) v += MOD; }
	explicit operator int() const { return v; }
	friend std::ostream &operator<<(std::ostream& out, const modnum& n) { return out << int(n); }
	friend std::istream &operator>>(std::istream& in, modnum& n) { lint v_; in >> v_; n = modnum(v_); return in; }
	friend bool operator==(const modnum& a, const modnum& b) { return a.v == b.v; }
	friend bool operator!=(const modnum& a, const modnum& b) { return a.v != b.v; }
	modnum inv() const {
		modnum res;
		res.v = modinv(v, MOD);
		return res;
	}
	modnum neg() const {
		modnum res;
		res.v = v ? MOD-v : 0;
		return res;
	}
	modnum operator-() const { return neg(); }
	modnum operator+() const { return modnum(*this); }
	modnum& operator+=(const modnum& o) {
		v += o.v;
		if (v >= MOD) v -= MOD;
		return *this;
	}
	modnum& operator-=(const modnum& o) {
		v -= o.v;
		if (v < 0) v += MOD;
		return *this;
	}
	modnum& operator*=(const modnum& o) {
		v = int(lint(v) * lint(o.v) % MOD);
		return *this;
	}
	modnum& operator/=(const modnum& o) { return *this *= o.inv(); }
	friend modnum operator+(const modnum& a, const modnum& b) { return modnum(a) += b; }
	friend modnum operator-(const modnum& a, const modnum& b) { return modnum(a) -= b; }
	friend modnum operator*(const modnum& a, const modnum& b) { return modnum(a) *= b; }
	friend modnum operator/(const modnum& a, const modnum& b) { return modnum(a) /= b; }
};
 
template <typename T> T pow(T a, lint b) {
	assert(b >= 0);
	T r = 1; while (b) { if (b & 1) r *= a; b >>= 1; a *= a; } return r;
}

using num = modnum<int(1e9)+7>;

vector<num> fact = {1}, ifact;

num ncr(int n, int k) {
	if(k < 0 || k > n) return 0;
	return fact[n] * ifact[k] * ifact[n-k];
}

int main() {
    ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int n, k;
    cin >> n >> k;
    vector<int> values(n);
    for (int i = 0; i < n; ++i) cin >> values[i];
    sort(values.begin(), values.end());
	for (int i = 1; i <= 101010; ++i)
		fact.push_back(fact[i-1] * i);
	for (num x : fact) ifact.push_back(1/x);
	vector<num> difference;
	for (int i = 0; i+1 < n; ++i)
		difference.push_back(values[i+1] - values[i]);
	num result = 0;
	num binom = ncr(n, k);
	for (int i = 0; i+1 < n; ++i) {
		num total_ways = binom;
		num left = ncr(n-i-1, k); // how many from the left
		num right = ncr(i+1, k); // how many from the right
		num contribution = total_ways - left - right;
		contribution *= difference[i];
		result += contribution;
	}
	cout << result << '\n';
}

Measured memory_bytes: 3828
#include<iostream>
#include<string>
using namespace std;
int main() {
	int a;
	while (cin >> a) {
		int b = a % 39;
		string c;
		if (b == 0) {
			cout << "3C" << 39 << endl;
			goto stop;
		}
		c = to_string(b);
		if (c.length() == 1) {
			string d = "0";
			c = (d+c);
		}
		cout << "3C" << c << endl;
	stop:;
	}
}

Measured memory_bytes: 3204
//#include <bits/stdc++.h>
#include <iostream>
#include <fstream>
#include <vector>
#include <string>
#include <cmath>
#include <algorithm>
#include <map>
#include <iomanip>
#include <stdlib.h>
#include <stdio.h>
#include <queue>
#include <deque>
#include <set>
#include <stack>
#include <time.h>
 
using namespace std;
 
typedef long long ll;
typedef long double ld;
typedef pair<int, int> Pii;
typedef pair<int, ll> Pil;
typedef pair<ll, ll> Pll;
typedef pair<ll, int> Pli;

#define fi first
#define se second

const ll MOD = 1e9 + 7;
const ll MOD2 = 998244353;
const ll MOD3 = 1812447359;
const ll INF = 1ll << 62;
const double PI = 2 * asin(1);

void yes() {printf("yes\n");}
void no() {printf("no\n");}
void Yes() {printf("Yes\n");}
void No() {printf("No\n");}
void YES() {printf("YES\n");}
void NO() {printf("NO\n");}

int N, M;
int cnt[int(1e5 + 5)];

int main(){
  scanf("%d%d", &N, &M);
  for (int i = 0; i < M; i++){
    int L, R; scanf("%d%d", &L, &R);
    cnt[L]++; cnt[R + 1]--;
  }

  int ans = 0;
  for (int i = 1; i <= N; i++){
    cnt[i] += cnt[i - 1];
    if (cnt[i] == M) ans++;
  }
  printf("%d\n", ans);

  return 0;
}


Measured memory_bytes: 4180
#include <stdio.h>
#include <stdlib.h>
#define ll long long
#define rep(i,l,r)for(ll i=(l);i<(r);i++)

ll a[100010];
int main(){
	ll n;
	scanf("%lld",&n);
	rep(i,0,n){
		ll l,r;
		scanf("%lld%lld",&l,&r);
		a[l]++;
		a[r+1]--;
	}
	ll ans=0;
	rep(i,1,100005){
		a[i]+=a[i-1];
		if(a[i]>=i-1)ans=i-1;
	}
	printf("%lld\n",ans);
}


Measured memory_bytes: 2572
#include <bits/stdc++.h>
#define ll long long


using namespace std;

const int MAXN = 100;

string str[MAXN + 1];

int fr[26], fr1[5];



int main() {
    //fstream cin("A.in");
    //ofstream cout("A.out");
    int n, m, i, j;
    ios::sync_with_stdio(false);
    cin >> n >> m;
    for(i = 1; i <= n; i++) {
        cin >> str[i];
        str[i] = " " + str[i];
        for(j = 1; j <= m; j++)
            fr[str[i][j] - 'a']++;
    }
    for(i = 1; i <= n; i++) {
        for(j = 1; j <= m; j++) {
            if(i <= (n + 1) / 2 && j <= (m + 1) / 2) {
                int cnt = 1;
                if(i != (n + 1) / 2 || n % 2 == 0)
                    cnt++;
                if(j != (m + 1) / 2 || m % 2 == 0)
                    cnt++;
                if(cnt == 3)
                    cnt++;
                fr1[cnt]++;
            }
        }
    }
    sort(fr, fr + 26);
    int s = 0;
    for(i = 25; i >= 0; i--) {
        for(j = 4; j >= 1; j--) {
           while(fr[i] >= j && fr1[j] > 0) {
               fr[i] -= j;
               s += j;
               fr1[j]--;
           }
        }
    }
    if(s == n * m)
        cout << "Yes";
    else
        cout << "No";
    //cin.close();
    //cout.close();
    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 sz(x) int(x.size())
#define pb push_back
#define eb emplace_back
using ll=long long;
using P = pair<int,int>;
#define chmax(x,y) x = max(x,y)
#define chmin(x,y) x = min(x,y)
const ll MOD=1000000007,MOD2=998244353;



int main() {
    int N,M;
    cin>>N>>M;
    vector<vector<int>> to(N);
    vector<int> from(N);
    rep(i,M){
        int x,y;
        cin>>x>>y;
        --x;--y;
        to[x].pb(y);
        from[y]++;
    }
    set<P> start;
    rep(i,N){
        start.insert({from[i],i});
    }
    vector<int> dp(N,0);
    while(!start.empty()){
        P p=*begin(start);
        start.erase(p);
        int x=p.second,d=dp[x];
        for(int u:to[x]){
            chmax(dp[u],dp[x]+1);
            start.erase({from[u],u});
            from[u]--;
            start.insert({from[u],u});
        }
    }
    int ans=0;
    rep(i,N){
        chmax(ans,dp[i]);
    }
    cout<<ans<<endl;
}

Measured memory_bytes: 11264
#include<bits/stdc++.h>
using namespace std;
#define dbg(var) cout<<#var<<"="<<var<<" "
#define nl cout<<"\n"
#define fr(i,n) for(int i=0;i<n;i++)
#define rep(i,a,n) for(int i=a;i<=n;i++)
#define fast ios::sync_with_stdio(false);cin.tie(0);
#define vi vector<int>
#define vvi vector<vi>
#define pb push_back
#define fa(v) for(auto &i:v)
#define all(v) v.begin(),v.end()
typedef unsigned long long ll;
int main()
{
    ll n;cin>>n;
    if(n&1){cout<<0;return 0;}
    n/=2;
    ll ans=0;ll x=5;
    while(x<=n){
    	ans+=(n/x);
    	x*=5;
    }
    cout<<ans;

}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int main()
{
	int a, b;

	cin >> a >> b;

	if (a==1 && b==1) {
		cout << "Draw" << endl;
	}
	else if(a==1){
		cout << "Alice" << endl;
	}
	else if (b == 1) {
		cout << "Bob" << endl;
	}
	else if (a < b) {
		cout << "Bob" << endl;
	}
	else if(a > b){
		cout << "Alice" << endl;
	}
	else {
		cout << "Draw" << endl;
	}

}

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

int main(){
    ll r, d, x;
    cin >> r >> d >> x;
    for (int i = 0; i < 10; i++)
    {   
        x = r*x - d;
        cout << x << endl;
    }
    
    
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
#define fr(i,n) for(int i=0;i<(n);++i)
#define Fr(i,n) for(int i=1;i<=(n);++i)
#define ifr(i,n) for(int i=(n)-1;i>=0;--i)
#define iFr(i,n) for(int i=(n);i>0;--i)

ll comb(ll a,ll b){
    if(a<0||b<0||a<b) return 0;
    ll c=1;
    fr(i,b) c*=a-i;
    Fr(i,b) c/=i;
    return c;
}

int main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    istream& in(cin);
    ostream& out(cout);
    string n;
    int k;
    in>>n>>k;
    ll ans{},p[]={1,9,81,729};
    int m=n.length(),cnt{k};
    fr(i,m){
        if(n[i]-'0'){
            ans+=comb(m-i-1,cnt)*p[cnt];
            if(cnt) fr(j,n[i]-'1') ans+=comb(m-i-1,cnt-1)*p[cnt-1];
            --cnt;
            if(!cnt){
                ++ans;
                break;
            }
        }
    }
    cout<<ans<<endl;
}

Measured memory_bytes: 256
#include<iostream>
#include<cmath>
#include<cstdio>
using namespace std;
#define PI 3.14159265359
int main(){
	double a,b,C;
	cin>>a>>b>>C;
	C=C/180*PI;
	printf("%.6f\n%.6f\n%.6f\n",a*b*sin(C)*0.5,sqrt(a*a+b*b-2*a*b*cos(C))+a+b,b*sin(C));
	return 0;
}



Measured memory_bytes: 3468
#include <bits/stdc++.h>
using namespace std;
int main(void){
    string s;
    cin>>s;
    int flag=0,h=0;
    if (s.size()==1) {
        flag=1;
    } else {
        for (int i=0;i<s.size();i++) {
            if (s[i]=='h') {
                if (h==0) {
                    h=1;
                } else {
                    flag=1;
                    break;
                }
            } else if (s[i]=='i') {
                if (h==1) {
                    h=0;
                } else {
                    flag=1;
                    break;
                }
            } else {
                flag=1;
                break;
            }
        }
    }
    if (flag==0&&h==0) {
        cout<<"Yes"<<endl;
    } else {
        cout<<"No"<<endl;
    }
}


Measured memory_bytes: 256
/*Lucky_Glass*/
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
char str[10];
int main(){
	scanf("%s",str);
	for(int i=1;i<4;i++)
		if(str[i-1]==str[i]){
			printf("Bad\n");
			return 0;
		}
	printf("Good\n");
	return 0;
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define space " "
#define MOD (long long) 1000000007
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename T> void __f(const char* variable_name, T&& value){cout << variable_name << ": " << value << endl;}
template <typename T1, typename... T2> void __f(const char* names, T1&& arg1, T2&&... args){const char* comma = strchr(names + 1, ',');cout.write(names, comma - names) << ": " << arg1 << " |";__f(comma + 1, args...);}

const ll N = 5e5 + 5;
ll *v;
ll n;

void solve(){
    n = 3;
    ll arr[n][n];
    for(ll i = 0; i < n; i++)
        for(ll j = 0; j < n; j++)
            cin >> arr[i][j];
    ll x;
    cin >> x;
    while(x--){
        ll y;
        cin >> y;
        for(ll i = 0; i < n; i++)
            for(ll j = 0; j < n; j++)
                if(arr[i][j] == y){
                    arr[i][j] = -arr[i][j];
                }
    }
    for(ll i = 0; i < n; i++){
        bool poss = true;
        for(ll j = 0; j < n; j++)
            if(arr[i][j] > 0){
                poss = false;
                break;
            }
        if(poss){
            cout << "Yes" << endl;
            return;
        }
    }
    for(ll i = 0; i < n; i++){
        bool poss = true;
        for(ll j = 0; j < n; j++)
            if(arr[j][i] > 0){
                poss = false;
                break;
            }
        if(poss){
            cout << "Yes" << endl;
            return;
        }
    }
    bool poss = true;
    for(ll i = 0; i < n; i++)
        if(arr[i][i] > 0){
            poss = false;
            break;
        }
    if(poss){
        cout << "Yes" << endl;
        return;
    }
    poss = true;
    for(ll i = 0; i < n; i++)
        if(arr[i][n - i - 1] > 0){
            poss = false;
            break;
        }
    if(poss){
        cout << "Yes" << endl;
        return;
    }
    cout << "No" << endl;
    return;
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    ll t = 1;
    // cout << "\n\nBLAH BLAH BLAH\n\n";
    // cin >> t;
    while(t--){
        solve();
    }
    return 0;
}

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

using namespace std;
using ll = long long;
using P = pair<int,int>;
using Graph = vector<vector<int>>;

int main(void) {
    int n, m; 
    cin >> n >> m;
    vector<int> a(n);
    REP(i, n) cin >> a[i];
    int sum = accumulate(a.begin(),a.end(),0);
    double eps = sum / (double)(4*m);

    int ans = 0;
    REP(i, n) {
        if(a[i]>= eps) ans++;
        if(ans>=m) {
            cout << "Yes" << endl;
            return 0;
        }
    }
    cout << "No" << endl;
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>                          
using namespace std;
char s[5][5];
int main(){
    for(int i=1;i<=3;i++)
        for(int j=1;j<=3;j++)
            cin>>s[i][j];
    cout<<s[1][1]<<s[2][2]<<s[3][3];
	return 0;
}
//68871358
//76140264
//25446011
//200841159

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

#define rep(i,n) for(int i = 0; i < (n); ++i)
#define per(i,n) for(int i = (n)-1; i >= 0; --i)
#define rng(i,a,b) for(int i = (a); i < (b); ++i)
#define all(a) (a).begin(), (a).end()

struct Testimony {
    int x, y;
};
using vt = vector<Testimony>;
using vvt = vector<vt>;

int main() {
    int N;
    cin >> N;
    vvt ts(N);
    rep(i,N) {
        int A;
        cin >> A;
        rep(j,A) {
            int x, y;
            cin >> x >> y;
            ts[i].push_back(Testimony{x-1, y});
        }
    }
    int ans = 0;
    rep(b,(1<<N)) {
        vl isHonest(N);
        int honest_cnt = 0, isOk = 1;
        rep(i,N) {
            isHonest[i] = (b>>i) & 1;
            honest_cnt += isHonest[i];
        }
        rep(i,N) {
            if (!isHonest[i]) continue;
            rep(j,int(ts[i].size())) {
                if (isHonest[ts[i][j].x] == ts[i][j].y) continue;
                isOk = false;
            }
        }
        if (isOk) {
            ans = max(ans, honest_cnt);
        }
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 3640
#include <iostream>
#include <string>
#include <algorithm>
#include <cmath>
#include <map>
#include <vector>
#include <stack>
#include <queue>
#include <tuple>
#include <cassert>
#include <functional>
#include <set>
#include <deque>
#include <list>
using namespace std;
typedef long long ll;
int dx[4] = {0,0,1,-1};
int dy[4] = {1,-1,0,0};
const int INF = 1<<29;
#define LNF __LONG_LONG_MAX__
const ll MOD = 1000000007;
const int MAX = 200000;

long long fac[MAX], finv[MAX], inv[MAX];

// テーブルを作る前処理
void COMinit() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (int i = 2; i < MAX; i++){
        fac[i] = fac[i - 1] * i % MOD;
        inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }
}

// 二項係数計算
long long COM(int n, int k){
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}
// 法mでのaの逆元を計算
long long modinv(long long a, long long m) {
    long long b = m, u = 1, v = 0;
    while (b) {
        long long t = a / b;
        a -= t * b; swap(a, b);
        u -= t * v; swap(u, v);
    }
    u %= m;
    if (u < 0) u += m;
    return u;
}
// a^n mod を計算する
long long modpow(long long a, long long n, long long mod) {
    long long res = 1;
    while (n > 0) {
        if (n & 1) res = res * a % mod;
        a = a * a % mod;
        n >>= 1;
    }
    return res;
}
//最大公約数
int gcd(int x, int y) { return (x % y)? gcd(y, x % y): y; }
//最小公倍数
int lcm(int x, int y) { return x / gcd(x, y) * y; }
// nが大きく,kが10^7程度の時の二項係数
long long com[200005];
void combination(long long n,long long k){
    com[0] = 1;
    for(int i=1;i<=k;i++){
        com[i] = (com[i-1]*(n-i+1)%MOD)*modinv(i,MOD)%MOD;
    }
}

int main(){
    int a; cin >> a;
    cout << a + a*a + a*a*a << endl;
    return 0;
}


Measured memory_bytes: 3620
#include<stdio.h>
int main()
{
  int h, a ;
  scanf("%d%d",&h,&a) ;

  if(h%a == 0){
    printf("%d\n", h/a) ;
  }else{
    printf("%d\n", 1+(h/a)) ;
  }
  
  return 0 ;
}


Measured memory_bytes: 128
#include <bits/stdc++.h>
#include <iostream>
#include <cstring>
#include <stack>
#include <cstdlib>
#include <queue>
#include <cmath>
#include <cstdio>
#include <algorithm>
#include <string>
#include <vector>
#include <list>
#include <iterator>
#include <set>
#include <map>
#include <utility>
#include <iomanip>
#include <ctime>
#include <sstream>
#include <bitset>
#include <deque>
#include <limits>
#include <numeric>
#include <functional>

#define gc getchar()
#define mem(a) memset(a,0,sizeof(a))
#define mod 1000000007
#define sort(a,n,int) sort(a,a+n,less<int>())
#define fread() freopen("in.in","r",stdin)
#define fwrite() freopen("out.out","w",stdout)
using namespace std;

typedef long long ll;
typedef char ch;
typedef double db;  

const int maxn=1e5+10;
//ll a[maxn];
int aa[maxn];

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

int main(){
	int n , d , res;
	cin>>n>>d;
	res = n/(2*d+1);
	if(n%(2*d+1))res++;
	cout<<res;
	
}

Measured memory_bytes: 256
#include<cstdio>
#include<cstring>
#include<vector>
#include<queue>
#include<algorithm>
#include<cmath>
#include<climits>
#include<string>
#include<set>
#include<numeric>
#include<map>
#include<iostream>
using namespace std;
#define rep(i,n) for(int i = 0;i<((int)(n));i++)
#define reg(i,a,b) for(int i = ((int)(a));i<=((int)(b));i++)
#define irep(i,n) for(int i = ((int)(n)-1);i>=0;i--)
#define ireg(i,a,b) for(int i = ((int)(b));i>=((int)(a));i--)
typedef long long ll;
typedef pair<ll, ll> mp;

ll N,h=0,n=0,w=0;

int main(void){
	cin>>N;
	reg(i,1,3500){
		reg(j,1,3500){
			if( 4*i*j-N*(i+j)>0 && (N*i*j)%(4*i*j-N*(i+j))==0 ){
				w=i;
				h=j;
				n=(N*i*j)/(4*i*j-N*(i+j));
				break;
			}
		}
	}
	printf("%lld %lld %lld\n",h,w,n);
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <functional>
#include <cmath>
using namespace std;
#define rep(i,n) for(int i=0;i<(n);++i)
#define rep1(i,n) for(int i=1;i<=(n);++i)
#define all(c) (c).begin(),(c).end()
#define pb push_back
#define fs first
#define sc second
#define show(x) cout << #x << " = " << x << endl;
int p,q,a,n,ans;
double eps=1e-12;
void dfs(int pro,int cnt,double sum,int mx){
	if(abs(sum-(double)p/q)<eps) ans++;
	if(sum+eps>(double)p/q) return;
	if(cnt==n) return;
	rep1(i,mx){
		if(i*pro>a) break;
		dfs(i*pro,cnt+1,sum+1.0/i,min(mx,i));
	}
}
int main(){
	while(true){
		cin>>p>>q>>a>>n;
		if(p==0) break;
		ans=0;
		dfs(1,0,0,a);
		cout << ans << endl;
	}
}

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

namespace ABC119C
{
    static class MainClass
    {

        static int[] sin;
        static int N;
        static List<int> tlst = new List<int>();
        static int INF = int.MaxValue;

        public static void Main(string[] args)
        {

            sin = Array.ConvertAll(Console.ReadLine().Split().ToArray(), int.Parse);
            N = sin[0];

            for(int i = 0; i < N; i++)
            {
                int t = int.Parse(Console.ReadLine());
                tlst.Add(t);
            }

            Console.WriteLine(Dfs(0, ""));


        }

        public static int Dfs(int cur, string s)
        {
            if(cur == N)
            {
                if (!s.Contains('0') || !s.Contains('1') || !s.Contains('2')) return INF;
                else
                {
                    int cnt0 = 0;
                    int cnt1 = 0; 
                    int cnt2 = 0;
                    int sum0=0;
                    int sum1 = 0;
                    int sum2 = 0;
                    for (int i = 0; i < N; i++)
                    {
                        if (s[i] == '0') {
                            cnt0++;
                            sum0 += tlst[i];
                        }
                        else if (s[i] == '1')
                        {
                            cnt1++;
                            sum1 += tlst[i];
                        } else if (s[i] == '2')
                        {
                            cnt2++;
                            sum2 += tlst[i];
                        }
                    }
                    int ans = (10 * (cnt0 - 1)) + Math.Abs(sum0 - sin[1]) 
                    +  (10 * (cnt1 - 1)) + Math.Abs(sum1 - sin[2])
                    +  (10 * (cnt2 - 1)) + Math.Abs(sum2 - sin[3]);
                   
                    return ans;
                }
            }
            else
            {
                int ans = INF;
                for(int i = 0; i < 4; i++)
                {
                    string news = s + i.ToString();
                    //Console.WriteLine("call dfs cur, lst: " + (cur + 1) + " " + news);
                    ans = Math.Min(ans, Dfs(cur + 1, news));
                }
                return ans;
            }
        }
    }
}


Measured memory_bytes: 17368
#include <iostream>
#include <type_traits>
#include <iomanip>
#include <cstdint>
#include <string>
#include <set>
#include <map>

using int64 = long long;

int n;
int64 has[100010];

int main() {
    int64 sum = 0;
    std::cin >> n;
    
    for(int i = 0; i < n; ++i) {
        std::cin >> has[i + 1];

        if(has[i] && has[i + 1]) {
            ++sum, --has[i + 1];
        }
        
        sum += has[i + 1] / 2;
        has[i + 1] %= 2;
    }
    
    std::cout << sum << std::endl;
}

Measured memory_bytes: 1024
# -*- coding: utf-8 -*-
import sys

def main():
	N = int(input())
	nums = [0 for _ in range(N)]
	
	if N == 0:
		print(2)
		sys.exit()
	if N == 1:
		print(1)
		sys.exit()
		
	nums[0] = 2
	nums[1] = 1
	for i in range(N):
		if i < 2:
			continue
		nums[i] = nums[i-1] + nums[i-2]
	
	print(nums[N-1] + nums[N-2])
	
if __name__ == "__main__":
	main()
	

Measured memory_bytes: 3064
#include <stdio.h>
#include <string.h>

int main() {
  char s[101], p[101], ss[202];
  scanf("%s %s", s, p);

  strcpy(ss, s);
  strcat(ss, s);

  if (strstr(ss, p) == NULL) {
    printf("No\n");
  } else {
    printf("Yes\n");
  }

  return 0;
}


Measured memory_bytes: 2100
import sys
from collections import *
import heapq
import math
import bisect
from itertools import permutations
from itertools import accumulate
from fractions import gcd
def input():
    return sys.stdin.readline()[:-1]
mod=10**9+7

n=int(input())
c=[int(input()) for i in range(n)]
dp=[0]*n
dic={}
dp[0]=1
dic[c[0]]=1
for i in range(1,n):
    if c[i]==c[i-1]:
        dp[i]=dp[i-1]
        continue
    if c[i] in dic:
        dp[i]=(dp[i-1]+dic[c[i]])%mod
        dic[c[i]]=dp[i]
    else:
        dp[i]=dp[i-1]%mod
        dic[c[i]]=dp[i]
print(dp[-1]%mod)
# print(dic)

Measured memory_bytes: 99672
#include<cstdlib>
#include<vector>
#include<string>
#include<algorithm>
#include<cstring>
#include<queue>
#include<map>
#include<stack>
#include<cstdio>
#include<iostream>
#include<vector>
#define MAXN 1000
using namespace std;
typedef long long ll;
inline ll rd() {ll x=0;char c=getchar();while(c<'0'||c>'9')c=getchar();while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();return x;}
ll num[200000];
ll cnt;
ll loc[64]={0};
void insert(ll value) {
	for (ll i = 61; i >= 0; i--) {
		if ((value >> i) & 1) {
			if (!loc[i]) {
				loc[i] = value;
				return;
			} else
				value ^= loc[i];
		}
		if (!value)
			return;
	}
}
int main() {
	ios::sync_with_stdio(false);
	//freopen("../in", "r", stdin);
	//freopen("../out", "w", stdout);
	cin >> cnt;
	ll all = 0;
	for (ll i = 0; i < cnt; i++) {
		cin >> num[i];
		all ^= num[i];
	}
	for (ll i = 0; i <= 60; i++) {
		if((all>>i)&1) {
			for (ll j = 0; j < cnt; j++)
				if ((num[j] >> i) & 1)
					num[j] -= (1ll << i);
		}
	}
	for(ll i=0;i<cnt;i++)
		insert(num[i]);
	ll ans=0;
	for(ll i=60;i>=0;i--)
	{
		if((ans^loc[i])>ans)
			ans=ans^loc[i];
	}
	cout<<(ans+(ans^all))<<endl;
	return 0;
}

Measured memory_bytes: 1024
//header{{{
#include<bits/stdc++.h>
  
using namespace std;
 
#define rep(i,n) for(int i=0;i<(n);++i)
#define reps(i,n) for(int i=1;i<=(n);++i)
#define all(x) (x).begin(),(x).end()
#define setout(n,x) setw(n) << setfill(x)
#define Fixed fixed << setprecision(10)
#define int long long
using pii = pair<int,int>;
constexpr int INF  = 0x3f3f3f3f;
constexpr long long LINF = 0x3f3f3f3f3f3f3f3fLL;
constexpr int mod = 1e9+7; 
 
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;}
//}}}

signed main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	int n,m,x;
	cin >> n >> m >> x;
	vector<bool> a(n+1);
	rep(i,m){
		int A;
		cin >> A;
		a[A] = true;
	}
	int sum = 0;
	for(int i = x;i <= n;++i){
		sum += a[i];
	}
	int tmp = sum;
	sum = 0;
	for(int i = x;i >= 0;--i){
		sum += a[i];
	}
	cout << min(tmp,sum) << '\n';
	return 0;
}


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

using ll = long long;

#define pb push_back
#define ff first
#define ss second
#define all(a) a.begin(), a.end()
#define sz(a) (int)(a.size())
#define clr(a, b) memset(a, b, sizeof(a))
#define REP(i, a, b) for(int i=(int)(a); i<(int)(b); ++i)
#define REPD(i, a, b) for(int i=(int)(a)-1; i>=(int)(b); --i)

template<typename T> inline bool chkmin(T &a, const T &b) { return a > b ? a = b, 1 : 0; }
template<typename T> inline bool chkmax(T &a, const T &b) { return a < b ? a = b, 1 : 0; }

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    string s;
    cin >> s;
    string res = "";
    REP(i, 0, sz(s)) {
    	if(s[i] == 'g') s[i] = 'r';
    	res += 'p';
    }
    int p = 0, r = 0;
    vector<int> v[2];
    REP(i, 0, sz(s)) {
    	if(s[i] == 'r') {
    		v[0].pb(i);
    	} else {
    		v[1].pb(i);
    	}
    	++p;
    	if(p > r) {
    		while(p > r && !v[0].empty()) {
    			res[v[0].back()] = 'r';
    			v[0].pop_back();
    			--p;
    			++r;
    		}
    		while(p > r && !v[1].empty()) {
    			res[v[1].back()] = 'r';
    			v[1].pop_back();
    			--p;
    			++r;
    		}
    	}
    }
    int bad = 0, good = 0;
    REP(i, 0, sz(s)) {
    	if(s[i] == 'p' && res[i] == 'r') ++bad; 
    	if(s[i] == 'r' && res[i] == 'p') ++good;
    }
    cout << good - bad << "\n";
    return 0;
}


Measured memory_bytes: 4024