akhauriyash/Code-Regression huggingface dataset:
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1]*n

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

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if self.parents[x] > self.parents[y]:
            x, y = y, x
        self.parents[x] += self.parents[y]
        self.parents[y] = x

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

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

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}


n, m = map(int,input().split())
b = []
for _ in range(m):
    A, B = map(int,input().split())
    b.append([A-1,B-1])
b = b[::-1]
uf = UnionFind(n)
ans = []
for i in range(m):
    if uf.same(b[i][0], b[i][1]):
        ans.append(0)
    else:
        ans.append(uf.size(b[i][0])*uf.size(b[i][1]))
    uf.union(b[i][0], b[i][1])
ans = ans[::-1]
tmp = 0
for i in ans:
    tmp += i
    print(tmp)


Measured memory_bytes: 26884
(R,C),*X=$<.map{|l|l.split.map &:to_i};s,*t=->x,y{y==C ?3e9+x:x==R ?6e9-y:y<1?9e9-x:y*1[x]};X.flat_map{|a,b,c,d|[[v=s[a,b],v],[w=s[c,d],v]]*-2[v*w]}.sort.map{|i,x|x==t[-1]?t.pop: t<<x};puts t[0]?:NO: :YES

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

long long int N, K;

int main(){
    cin >> N >> K;
    if(N % K == 0)cout << 0 << endl; // N が K の倍数のとき
    else cout << 1 << endl; // そうでないとき
    return 0;
}


Measured memory_bytes: 256
<?php
  list($a, $b, $c) = explode(" ", trim(fgets(STDIN)));
  list($k) = explode(" ", trim(fgets(STDIN)));

  for ($i=0; $i<$k; $i++) {
    if($a >= $b){
      $b = $b * 2;
    }else if($b >= $c){
      $c = $c * 2;
    }
    if($a < $b && $b < $c){
      echo "Yes";
      exit;
    }
  }

  echo "No";
exit;

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

typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> pi;

#define F first
#define S second
#define PB push_back
#define MP make_pair

#define FOR_EX(i, a, b) for (int i = a; i < b; i++)
#define FOR_IN(i, a, b) for (int i = a; i <= b; i++)

#define ALL(a) a.begin(), a.end()

// g++ -std=c++17 -O2 -Wall template.cpp -o template
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    // freopen("input.txt", "r", stdin);
    // freopen("output.txt", "w", stdout);

    int a, b;
    cin >> a >> b;
    FOR_IN(i, 1, 1000) {
        if (floor(i * 0.08) == a && floor(i * 0.1) == b) {
            cout << i << endl;
            return 0;
        }
    }
    cout << -1 << endl;
}


Measured memory_bytes: 256
#include <iostream>
 
using namespace std;
 
int main()
{
    int n,count=0;
    int arr[n];
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>arr[i];
      if(i%2==0&&arr[i]%2!=0)
         count++;
        }
    
    cout<<count;
    return 0;
}

Measured memory_bytes: 3572
#define _USE_MATH_DEFINES

#include <iostream>
#include <iomanip>
#include <stdio.h>

#include <sstream>
#include <algorithm>
#include <iterator>
#include <cmath>
#include <complex>

#include <string>
#include <cstring>
#include <vector>
#include <bitset>

#include <queue>
#include <set>
#include <map>
#include <stack>
#include <list>

#include <ctime>
////
//#include <random>//
/////////
#define R(i,n) for(int i=0;i<(n);i=i+1)
/////////
typedef long long LL;
typedef long double LD;
typedef unsigned long long ULL;

////定数
const int INF = (int)1e9 + 10;
const LL MOD = (LL)1e9 + 7;
const LL LINF = (LL)4e18 + 20;
const LD PI = acos(-1.0);
const double EPS = 1e-9; 
/////////
using namespace::std;
template<typename T>
void chmax(T& a, T b) {
	a = max(a, b);
}

template<typename T>
void chmin(T& a, T b) {
	a = min(a, b);
}

template<typename T>
void IN(vector<T> &A,int N=-1) {
	if (N == -1) {
		N = A.size();
	}
	for (int i = 0; i < N; ++i) {
		cin >> A[i];
	}
}

template<typename T>
void SO(vector<T> &A,bool F=false) {
	sort(A.begin(), A.end());
	if (F) {
		reverse(A.begin(), A.end());
	}
}
//////////////
vector<int> f1(string s) {
	vector<int> ans(26, 0);
	for (auto a : s) {
		ans[a - 'a']++;
	}
	return ans;
}
int f2(string s1,string s2) {
	
	vector<int> A = f1(s1);
	vector<int> B = f1(s2);
	int ans = 0;
	for (int i = 0; i < 26; ++i) {
		if (A[i] && B[i])ans++;
	}
	return ans;
}
void solve() {
	int N;
	string S;
	cin >> N >> S;
	int ans = 0;
	for (int i = 1; i < N; ++i) {
		int res = f2(S.substr(0, i), S.substr(i, (N - i)));
		chmax(ans, res);
	}
	cout << ans << endl;
}

signed main(void) {
	std::cin.tie(0);
	std::ios::sync_with_stdio(false);
	std::cout << std::fixed;//小数を10進数表示
	cout << setprecision(16);//小数点以下の桁数を指定//coutとcerrで別	

	solve();
}

Measured memory_bytes: 256
def use_fast_io():
    global input
    import io
    import sys
    f = io.BytesIO(sys.stdin.buffer.read())
    input = f.readline


use_fast_io()

from scipy.sparse.csgraph import floyd_warshall
import numpy as np


def solve():
    n, m, l = map(int, input().split())
    graph = np.full((n, n), 10 ** 10)
    for _ in range(m):
        s, t, w = map(int, input().split())
        if w <= l:
            graph[s - 1][t - 1] = graph[t - 1][s - 1] = w
    graph = floyd_warshall(graph, directed=False)
    graph = floyd_warshall(graph <= l, directed=False)
    graph[np.isinf(graph)] = 0
    Q = int(input())
    ans = []
    for _ in range(Q):
        s, t = map(int, input().split())
        ans.append(int(graph[s - 1][t - 1]) - 1)
    print(*ans, sep='\n')


if __name__ == '__main__':
    solve()


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

ll f(ll n, ll g1, ll s1, ll b1, ll g2, ll s2, ll b2) {
  vector<ll> dp(n + max({g1, s1, b1}));
  for (ll i = 0; i < n; i++) {
    dp[i + g1] = max(dp[i + g1], dp[i] - g1 + g2);
    dp[i + s1] = max(dp[i + s1], dp[i] - s1 + s2);
    dp[i + b1] = max(dp[i + b1], dp[i] - b1 + b2);
  }
  return n + *max_element(begin(dp), begin(dp) + n + 1);
}

int main() {
  ll n, g1, s1, b1, g2, s2, b2;
  cin >> n >> g1 >> s1 >> b1 >> g2 >> s2 >> b2;
  n = f(n, g1, s1, b1, g2, s2, b2);
  n = f(n, g2, s2, b2, g1, s1, b1);
  cout << n << endl;
}


Measured memory_bytes: 195712
n = gets.chomp.to_i

require 'prime'

h = Hash.new(0)
2.upto(n) do |i|
  Prime.prime_division(i).each do |k, v|
    h[k] += v
  end
end

ans = 1
MOD = 10 ** 9 + 7

h.each_value do  |v|
  ans = ans * (v + 1) % MOD
end
p ans


Measured memory_bytes: 2300
n,a,b = map(int,input().split())
c = a + b #一つの塊
d = n //c #塊が何個あるか
e = n%c #塊じゃないものが何個残るか
katamariblue = a*d
if e >=a:
    blue = a
else:
    blue = e
print(blue + katamariblue)

Measured memory_bytes: 3060
using System;
using System.Collections.Generic;

class Program {
    static List<int> primeList = new List<int>();
    static int maxV = 0;

    static int Main(string[] args) {
        primeList.Add(2);
        primeList.Add(3);
        maxV = 3;

        List<int> list = new List<int>();

        while (true) {
            string v = Console.ReadLine();
            if (string.IsNullOrEmpty(v) == true) { break; }

            list.Add(int.Parse(v));
        }

        for (int i = 0; i < list.Count; i++) {
            AddPrime(list[i]);
            Calc(list[i]);
        }

        return 0;
    }

    static bool IsPrime(int v) {
        for (int i = 0; i < primeList.Count; i++) {
            if (Math.Sqrt(v) < primeList[i]) {
                return true;
            }
            if (v % primeList[i] == 0) {
                return false;
            }
        }
        return true;
    }

    static void AddPrime(int v) {
        if (v % 2 == 0) { v++; }

        if (v <= maxV) { return; }

        for (int i = maxV + 2; i <= v; i += 2) {
            if (IsPrime(i) == false) { continue; }

            primeList.Add(i);
        }

        maxV = v;
    }

    static void Calc(int v) {
        int cnt = primeList.FindAll((x) => (x <= v)).Count;
        Console.WriteLine(cnt);
    }
}

Measured memory_bytes: 11092
/**
 * Created by karayuu on 2019/06/02
 */
fun main(args: Array<String>) {
    var (x, y) = readLine()!!.split(" ").map { it.toInt() }
    if (x < y) {
        val _x = x
        x = y
        y = _x
    }

    while (true) {
        val div = x % y
        if (div == 0) {
            println(y)
            return
        }

        x = y
        y = div
    }
}



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

int main(){
	char s[20],t[20],u[20];
	int S,T;
	scanf("%s %s",s,t);
	scanf("%d %d",&S,&T);
	scanf("%s",u);
	if( strcmp(s,u)==0 ) S--;
	if( strcmp(t,u)==0 ) T--;
	printf("%d %d",S,T);
	return 0;
}


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

using namespace std;
using lint = long long int;


int main() {
	int n;
	int* h;
	cin >> n;
	h = new int[n];
	for (int i = 0; i < n; i++)
		cin >> h[i];

	int maxVal = 0;

	int count = 0;
	for (int i = 0; i < n-1; i++) {
		if (h[i] >= h[i + 1])
			count++;
		else {
			maxVal = max(maxVal, count);
			count = 0;
		}
	}
	maxVal = max(maxVal, count);
	
	cout << maxVal;

	return 0;
}

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

#define int long long
#define all(V) (V).begin(),(V).end()
#define umap unordered_map
#define uset unordered_set
#define br cout<<"\n";

const int MAXN=1e5+10, MOD=1e9+7;
int n,m;


signed main()
{
//	#ifndef ONLINE_JUDGE
//		freopen("./input.txt","r",stdin);
//		freopen("./output.txt","w",stdout);
//	#endif
	ios::sync_with_stdio(false); cin.tie(nullptr);
    int a,b,c;
    cin>>a>>b>>c;
    int days=0,mny=0;
    while(mny<c){
        if(mny+(7*a)+b<=c){
            mny+= 7*a;
            mny+=b;
            days+=7;
        }
        else{
            for(int i=1; i<=7; i++){
                mny+= a;
                if(i==7)mny+=b;
                days++;
                if(mny>=c)break;
            }
        }
        if(mny>=c)break;
    }
    cout<<days; br;

}


Measured memory_bytes: 3216
#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
using namespace std;
typedef long long int64;
const double PI = 3.14159265358979323846;
const double EPS = 1e-12;
const int INF = 1<<29;
const long long  INFL = 1e18;
const int MOD = 1000000007;
const int MAX = 210000;
const int MAX_NUM = 999999999;
void solve() {
	int A, B, K; cin >> A >> B >> K;
	int cnt = 0;
	vector<int> ans;
	for (int i = 1; i <= max(A, B); ++i) {
		if (A % i == 0 && B % i == 0) {
			ans.push_back(i);
		}
	}
	sort(all(ans));
	cout << ans[ans.size() - K] << endl;
	return;
}
int main() {
	solve();
	return 0;
}

Measured memory_bytes: 256
/*
これを入れて実行
g++ code.cpp
./a.out
 */

#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <algorithm>
#include <utility>
#include <set>
#include <map>
#include <cmath>
#include <tuple>
#include <iomanip>

using namespace std;
typedef long long ll;
typedef long double ld;

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

const long long INF = 1LL << 60;
const ll MOD = 1e9 + 7;

bool greaterSecond(const pair<int, int>& f, const pair<int, int>& s){
    return f.second > s.second;
}

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

//-----------------------ここから-----------


int main(void){
	int n;
	cin >> n;

	int ans = 1e9;
	for(int i = 0; i <= n; i++){
		int tmp = i;
		int counter = 0;
		while(tmp > 0){
			int nine = 9;
			if(tmp < 9){
				counter += tmp;
				break;
			}
			while(nine * 9 <= tmp){
				nine *= 9;
			}
			tmp -= nine;
			counter++;
		}

		int tmp2 = n - i;

		while(tmp2 > 0){
			int six = 6;
			if(tmp2 < 6){
				counter += tmp2;
				break;
			}
			while(six * 6 <= tmp2){
				six *= 6;
			}
			tmp2 -= six;
			counter++;
		}

		ans = min(ans, counter);
	}

	cout << ans << endl;

}



Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define fs first
#define sc second
#define pb push_back
#define mp make_pair
#define eb emplace_back
#define ALL(A) A.begin(),A.end()
#define RALL(A) A.rbegin(),A.rend()
typedef long long ll;
typedef pair<ll,ll> P;
const ll mod=1000000007;
const ll LINF=1LL<<60;
const int INF=1<<30;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
int n,m,q;
ll ans = 0;
vector<int> a;
vector<P> t(q);
vector<ll> c(q);
vector<ll> d(q);
ll calc(){
	ll res = 0;
	for(int i = 0; i < q; i++) {
		if (a[t[i].sc - 1] - a[t[i].fs - 1] == c[i]){
			res += d[i];
		}
	}
	return res;
}
void dfs(int d,int x){//長さd、最後の要素がｘの場合での全探索
	if (d == n){
		ans = max(ans,calc());
		return;
	}
	for(int i = x; i <= m; i++) {
		a.pb(i);
		dfs(d + 1,i);
		a.pop_back();
	}
}

int main(){
	cin>>n>>m>>q;
	t.resize(q);
	c.resize(q);
	d.resize(q);
	for(int i = 0; i < q; i++) {
		cin>>t[i].fs >> t[i].sc >> c[i] >> d[i];
	}
	dfs(0,1);
	cout << ans << endl;
	return 0;
}

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

int main(){
	int n; 
	cin >> n;

	vector<int> v(n);
	for(int &e : v) 
		cin >> e;
	
	sort(v.begin(), v.end());

	long long ans = 0;	
	for(int j = 0;j < n;++j)
		for(int i = j+1;i < n;++i)
				ans += (lower_bound(v.begin(), v.end(), v[j] + v[i]) - v.begin()) - (i+1); 
	cout << ans;
}


Measured memory_bytes: 3600
#include <iostream>
#include <string>

using namespace std;

int N, ans{}, d[10][10];

pair<int, int> f(int n) {
  auto s = to_string(n);
  return {s.back()-'0',s[0]-'0'};
}

int pow10(int p) {
  int ret = 1;
  while(p--) ret *= 10;
  return ret;
}

void add_d(int i, int j, string s = "") {
  int n = (s.size() ? i * pow10(s.size()+1) + stoi(s)*10 + j
           : i*10 + j);
  if (n > N) return;
  ++d[i][j];
  for (char c = '0'; c <= '9'; ++c) {
    add_d(i,j,s+c);
  }
}

int main() {

  cin >> N;

  for (int i = 1; i != 10; ++i) {
    if (i > N) break;
    ++d[i][i];
    for (int j = 1; j != 10; ++j) {
      add_d(i,j);
    }
  }

  for (int i = 1; i <= N; ++i) {
    auto [a,b] = f(i);
    ans += d[a][b];
  }
  cout << ans << endl;
}


Measured memory_bytes: 3664
#include <stdio.h>
#define MAX 100005
#define NIL -1

struct Node{int p,l,r;};

struct Node T[MAX];
int n,D[MAX];

void print(int u)
{
  int i,c;
  printf("node %d: ",u);
  printf("parent = %d, ",T[u].p);
  printf("depth = %d, ",D[u]);
  if(T[u].p == NIL) printf("root, ");
  else if(T[u].l == NIL) printf("leaf, ");
  else printf("internal node, ");
  printf("[");
  i = 0;
  for(c = T[u].l; c != NIL; c = T[c].r)
    {
      if(i) printf(", ");
      printf("%d",c);
      i++;
    }
  printf("]\n");
};

int rec(int u)
{
  int d;
  d = 0;
  while(T[u].p != NIL)
    {
      u = T[u].p;
      d++;
    }
  return d;
};

int main()
{
  int i,j,d,v,c,l,r;
  
  scanf("%d",&n);
  for(i = 0; i < n; i++)
    {
      T[i].p = NIL;
      T[i].l = NIL;
      T[i].r = NIL;
    }
  
  for(i = 0; i < n; i++)
    {
      scanf("%d %d",&v,&d);
      
      for(j = 0; j < d; j++)
	{
	  scanf("%d",&c);
	  if(!j) T[v].l = c;
	  else T[l].r = c;
	  l = c;
	  T[c].p = v;
	}
    }
  for(i = 0; i < n; i++)
    if(T[i].p == NIL) 
  for(i = 0; i < n; i++)
    D[i]=rec(i);
  for(i = 0; i < n; i++)
    print(i);
  
  return 0;
}



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

using namespace std;
int t[100][6];
int ans = 0;

bool remove(){
  bool ret = 0;
  rep(i,20)rep(j,4){
    if(t[i][j] != 0 && t[i][j] == t[i][j+1] && t[i][j+1] == t[i][j+2]){
      //cout << t[i][j] << " " << t[i][j+1] << endl;
      for(int jj = j + 1; t[i][jj] == t[i][j]; jj++){
        ans += t[i][jj];
        t[i][jj] = 0;
      }
      ans += t[i][j];
      t[i][j] = 0;
      ret = 1;
    }
  }
  return ret;
}

void fall(){
  rep(tt,50)rep(i,20)rep(j,5)if(t[i][j] == 0)t[i][j] = t[i+1][j],t[i+1][j] = 0;
}

int main(){
  int x;
  while(cin >> x, x){
    ans = 0;
    rep(i,100)rep(j,6)t[i][j] = 0;
    rep(i,x)rep(j,5)  cin >> t[x-i-1][j];
    rep(i,500){
      remove();
      fall();
      //rep(i,x){{rep(j,5)cout << t[i][j] <<  " ";}cout<<endl;}cout << endl;
    }
    cout << ans << endl;
  }
}


Measured memory_bytes: 3084
#include <iostream>
#include <algorithm>
#include <map>
#include <regex>
#include <string>
#include <cstdlib>
#include <math.h>
#include <vector>
#include <queue>
using namespace std;
using ll = long long;

int main() {
  int N, M;
  cin >> N >> M;
  if (N == M) {
    cout << "Yes" << endl;
  } else {
    cout << "No" << endl;
  }
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i, n) for(long long int i = 0; i < n; i++)
#define _rep(i, m, n) for(long long int i = m; i < n; i++)
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
//const int N = 1000000;
const ll mod = 1000000007;
//using Graph = vector<vector<int>>;
/*const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};
const int dh[8] = {0, 0, 1, 1, 1, -1, -1, -1};
const int dw[8] = {1, -1, 0, 1, -1, 0, 1, -1};*/
const int dx[6] = {1, 0, -1, 1, -1, 0};
const int dy[6] = {1, 1, 1, 0, 0, -1};
  
ll gcd(ll A, ll B){
    if(B == 0)return A;
    return gcd(B, A % B);
}
ll lcm(ll A, ll B){
    return A * (B / gcd(A, B));
}
using Graph = vector<vector<int>>;
Graph G;
  
/*------------------------------------------------------------------*/
int main(){
    long double a, b; cin >> a >> b;
    long double c = a * b;
    ll d = (ll)c;
    cout << d << endl;
}

Measured memory_bytes: 3720
#include <iostream>
#include <vector>
#include <string>
#include <cctype>
#include <cmath>
#include <iomanip>
#include <climits>
#include <cfloat>
#include <algorithm>
#include <memory>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef unsigned uint;
typedef long double l_double;

#define vtr vector
#define PB push_back
#define EB emplace_back
#define gcd __gcd
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
#define st_ct static_cast // <>
#define TEST uint _ {}; cin >> _; while (_--)
#define PI (3.1415926535897932384626433832795)
#define MOD st_ct<int>(1e9 + 7)
#define EPS 1e-9
#define deb1(x) cerr << #x << " -> " << x << endl;
#define deb2(x,y) cerr << "(" << #x << ", " << #y << ") -> (" << x << ", " << y << ")" << endl;
#define deb3(x,y,z) cerr << "(" << #x << ", " << #y << ", " << #z << ") -> (" << x << ", " << y << ", " << z << ")" << endl;
#define debVV(V) cerr << #V << ":\n" << V << endl; // 2D

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

template <typename T>
ostream& operator<<(ostream &os, const vector<T> &A) {
    for (T const &v: A)
        os << v << " ";
    return os;
}

template<typename T>
void vtrV(const vector<T> &A)
{ for (T const &val: A) cout << val << endl; }

// 2D
template<typename T>
istream& operator>>(istream &is, vector<vector<T>> &A) {
    for (vector<T> &i: A)
        for (T &j: i)
            is >> j;
    return is;
}

template <typename T>
ostream& operator<<(ostream &os, const vector<vector<T>> &A) {
    for (vector<T> const &i: A) {
        for (T const &j: i)
            os << j << " ";
        os << endl;
    }
    return os;
}

template<typename T>
void vvtrNS(const vector<vector<T>> &A) {
    for (vector<T> const &i: A) {
        for (T const &j: i)
            cout << j;
        cout << endl;
    }
}

template<typename T>
T cntDigits(const T &N) { return (floor(log10(N)) + 1); }

template<typename T>
bool isPowOfTwo(const T &N) { return (N && (!(N&(N-1)))); }

template<typename T>
T lcm(T a, T b) { return ((a*b)/gcd(a, b)); }
/* -------------------------------------------------------- */
/* -------------------------------------------------------- */

//

int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    // cout.setf(std::ios::boolalpha);
    cout<<std::fixed;
    cout<<std::setprecision(6); // default
    /* -------------------------------- */

    int k {};
    int a {}, b {};
    cin >> k >> a >> b;

    int extra {b%k};
    int reach {b - extra};
    if (reach >= a && reach <= b)
    	cout << "OK" << endl;
    else cout << "NG" << endl;
    return 0;
}

Measured memory_bytes: 3644
#include <bits/stdc++.h>
using namespace std;
int a,b,flag=1;
char c[15];
int main()
{
	cin>>a>>b;
	for(int i=0;i<a+b+1;i++)
		cin>>c[i];
	for(int i=0;i<a+b+1;i++)
	if(i!=a && (c[i]<'0' || c[i]>'9'))
	flag=0;
	if(c[a]=='-' && flag==1)
	cout<<"Yes";
	else	
	cout<<"No";
	return 0;
}

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

const int num = 3;
int main() {
	int target,times=1;
	std::vector<int> day;  //何日でもできるように拡張したい
	day.resize(num);

	for (int i = 0; i < day.size(); i++) {
		std::cin>>day[i];
	}

	std::sort(day.begin(), day.end());

	target = day[0];

	for (int j = 1; j < day.size(); j++) {
		if (target < day[j]) {
			target = day[j];
			times++;
		}
	}

	std::cout << times << std::endl;

	return 0;
}

Measured memory_bytes: 256
n = gets.to_i
i = 1

loop do
  x = i
  if (x % 3 == 0) 
    printf " %d", i
  else
    loop do
      if (x % 10 == 3 ) 
        printf " %d", i
        break
      end
      x /= 10
      break if x == 0
    end
  end
  i += 1
  break if (i > n)
end

puts


Measured memory_bytes: 6884
#include<iostream>
#include<vector>
#include<algorithm>
#include<cmath>
#include<string>
#include<utility>
#include<queue>
#include<tuple>
#include<stdio.h>
#define rep(i, n) for(int i=0;i<n;i++)
using namespace std;

int main(){
	int k,a,b;
	bool f=0;
	cin>>k>>a>>b;
	for(int i=a;i<=b;i++){
		if(i%k==0)
			f=1;
	}
	if(f==1)
		cout<<"OK"<<endl;
	else
		cout<<"NG"<<endl;
	return 0;
}

Measured memory_bytes: 3632
n = int(input())
res = 0
numa = numb = numboth = 0
for _ in range(n):
    s = input()
    res += s.count("AB")
    if s[0] == "B" and s[-1] == "A":
        numboth += 1
    elif s[0] == "B":
        numb += 1
    elif s[-1] == "A":
        numa += 1

#print(numboth, numa, numb)
#print(res)

if numboth == 0:
    res += min(numa, numb)
else:
    if numa == 0 and numb == 0:
        res += numboth - 1
    else:
        res += numboth
        res += min(numa, numb)
print(res)

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

int main(){
    int K;
    cin >> K;
    vector<int> al(K, 0);

    int cnt = 1;
    int ans = 7 % K; // cnt1個前の答えmod K

    while(ans != 0){
        ans = (ans * 10 + 7) % K;
        if (al[ans] == 1){
            cout << "-1" << endl;
            return 0;
        }else{
            al[ans] = 1;
        }
        cnt++;
    }
    
    cout << cnt << endl;

    return 0;
}

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

const long long MOD = 1000000007;

void Main() {
  int N;
  cin >> N;
  char S1[N], S2[N];
  for (int i = 0; i < N; i++) {
    cin >> S1[i];
  }
  for (int i = 0; i < N; i++) {
    cin >> S2[i];
  }

  long long ans = 1;
  int i = 0;
  if (S1[i] == S2[i]) {
    ans = 3;
    i++;
  } else {
    ans = 6;
    i += 2;
  }
  for (; i < N; i++) {
    if (S1[i] == S2[i]) {
      if (S1[i - 1] == S2[i - 1])  {
        ans = (ans * 2) % MOD;
      }
    } else {
      if (S1[i - 1] == S2[i - 1])  {
        ans = (ans * 2) % MOD;
      } else {
        ans = (ans * 3) % MOD;
      }
      i++;
    }
  }
  cout << ans << endl;
}

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



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

Measured memory_bytes: 60120
#include <iostream>
#include <algorithm>
#include <string>
#include <string.h>
#include <stdlib.h>
#include <math.h>
#include <vector>
#include <queue>
#include <stack>
#include <cmath>
using namespace std;

#define rep(i, s) for (int i = 0; i < s; ++i)
#define all(v) (v.begin(), v.end())
#define COUT(x) cout << #x << ” = ” << (x) << ” (L” << __LINE__ << “)” << endl
#define EACH(i, s) for (__typeof__((s).begin()) i = (s).begin(); i != (s).end(); ++i)
#define VEC(a, n) vector<int>a(n)
#define PQ(a) priority_queue<int>a
#define PQmin(a) priority_queue< int, :vector<int>, greater<int> >a
#define PAIR pair<int, int>
/*
sort(sp.begin(), sp.end(), [](PAIR l, PAIR r){
       return l.first<r.first || (l.first==r.first && l.second > r.second);
       });
*/

typedef long long  ll;

#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))

struct UnionFind {
    vector<int> par; // par[i]:iの親の番号　(例) par[3] = 2 : 3の親が2

    UnionFind(int N) : par(N) { //最初は全てが根であるとして初期化
        for(int i = 0; i < N; i++) par[i] = i;
    }

    int root(int x) { // データxが属する木の根を再帰で得る：root(x) = {xの木の根}
        if (par[x] == x) return x;
        return par[x] = root(par[x]);
    }

    void unite(int x, int y) { // xとyの木を併合
        int rx = root(x); //xの根をrx
        int ry = root(y); //yの根をry
        if (rx == ry) return; //xとyの根が同じ(=同じ木にある)時はそのまま
        par[rx] = ry; //xとyの根が同じでない(=同じ木にない)時：xの根rxをyの根ryにつける
    }

    bool same(int x, int y) { // 2つのデータx, yが属する木が同じならtrueを返す
        int rx = root(x);
        int ry = root(y);
        return rx == ry;
    }
};


using Graph = vector<vector<int> >;

int main() {
   int n,m;
   cin>>n>>m;
   vector<int>a(m,0);
   for(int i=0;i<n;i++){
       int k;
       cin>>k;
       for(int j=0;j<k;j++){
           int x;
           cin>>x;
           x--;
           a.at(x)++;
       }
   }
   int ans=0;
   for(int i=0;i<m;i++){
       if(a.at(i)==n){
           ans++;
       }
   }

    cout<<ans<<endl;



   return 0;
}

Measured memory_bytes: 256
#include<iostream>
using namespace std;
int c;
int sub(int n, int x, int s, int sum){
	int i;
	if (n == 0){
		if (s == sum){
			c++;
		}
		return 0;
	}
	for (i = x; i <= 10 - n; i++){
		sub(n - 1, i + 1, s, sum+i);
	}
}
int main(void){
	int i, n, s, sum;
	while (1){
		cin >> n >> s;
		if (n == 0 && s == 0){ break; }
		c = 0;
		sub(n, 0, s, 0);
		cout << c << endl;
	}
	return 0;
}

Measured memory_bytes: 3000
#include <algorithm>
#include <iostream>
#include <cstdio>
#include <map>
#include <numeric>
#include <cmath>
#include <set>
#include <sstream>
#include <string>
#include <vector>
#include <queue>
#include <stack>
#include <complex>
#include <string.h>
#include <unordered_set>
#include <unordered_map>
#include <bitset>
#include <iomanip>
#include <sys/time.h>
#include <tuple>
#include <random>
using namespace std;

#define endl '\n'
#define ALL(v) (v).begin(), (v).end()
#define RALL(v) (v).rbegin(), (v).rend()
#define UNIQ(v) (v).erase(unique((v).begin(), (v).end()), (v).end())

typedef long long ll;
typedef long double ld;
typedef pair<int, int> P;
typedef complex<double> comp;
typedef vector< vector<ld> > matrix;
struct pairhash {
public:
    template<typename T, typename U>
    size_t operator()(const pair<T, U> &x) const {
	size_t seed = hash<T>()(x.first);
	return hash<U>()(x.second) + 0x9e3779b9 + (seed<<6) + (seed>>2);
    }
};
const int inf = 1e9 + 9;
const ll mod = 1e9 + 7;
const double eps = 1e-8;
const double pi = acos(-1);

int a, b;

int solve() {
    if (a >= 13) return b;
    if (a >= 6) return b/2;
    return 0;
}

void input() {
    cin >> a >> b;
}

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

    input();
    cout << solve() << endl;
}


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

int main(void){
    int a, b, c, x;
    cin >> a >> b >> c >> x;

    int ans = 0;

    for (int i=0; i<=a; i++) {
        for (int j=0; j<=b; j++) {
            for (int k=0; k<=c; k++) {
                if ((500 * i + 100 * j + 50 * k) == x) {
                    ans++;
                }
            }
        }
    }

    cout << ans;
    cout << "\n";
}

Measured memory_bytes: 256
package main

import (
	"bufio"
	"fmt"
	"math"
	"os"
	"sort"
	"strconv"
)

var sc = bufio.NewScanner(os.Stdin)

func next() string {
	sc.Scan()
	return sc.Text()
}

func nextInt() int {
	sc.Scan()
	i, e := strconv.Atoi(sc.Text())
	if e != nil {
		panic(e)
	}
	return i
}

func main() {
	sc.Split(bufio.ScanWords)

	N, M := nextInt(), nextInt()
	var nums []int
	for i := 0; i < M; i++ {
		nums = append(nums, nextInt())
	}

	sort.Sort(sort.Reverse(sort.IntSlice(nums)))

	m := map[int]int{
		1: 2, 2: 5, 3: 5, 4: 4, 5: 5,
		6: 6, 7: 3, 8: 7, 9: 6,
	}

	dp := make([]int, N+1)
	for i := 1; i <= N; i++ {
		max := math.MinInt64
		for _, num := range nums {
			match := m[num]
			if i - match >= 0 && max < dp[i - match] + 1 {
				max = dp[i - match] + 1
			}
		}
		dp[i] = max
	}

	var res []byte
	i := N
	for i > 0 {
		for j := 0; j < M; j++ {
			if i - m[nums[j]] >= 0 && dp[i] - 1 == dp[i - m[nums[j]]] {
				res = append(res, strconv.Itoa(nums[j])[0])
				i -= m[nums[j]]
				break
			}
		}
	}

	fmt.Println(string(res))
}


Measured memory_bytes: 768
n = int(input())
a,b = map(int,input().split())
p = list(map(int,input().split()))
l = []
m = []
h = []
for i in p:
    if i <= a:
        l.append(i)
    elif i <= b:
        m.append(i)
    else:
        h.append(i)
ans = min(len(l),len(m),len(h))
print(ans)

    


Measured memory_bytes: 3060
use std::cmp;
use std::fmt::{Debug, Display};
use std::io::{self, Read};
use std::str::{self, FromStr};


fn solve(a: Vec<u64>) -> u64 {
    a.into_iter().fold(1, lcm)
}


fn lcm(a: u64, b: u64) -> u64 {
    fn gcd(a: u64, b: u64) -> u64 {
        let (mut a, mut b) = (a, b);
        while b > 0 {
            let r = a % b;
            a = b;
            b = r;
        }
        a
    }
    a / gcd(cmp::max(a, b), cmp::min(a, b)) * b
}


fn main() {
    let stdin = io::stdin();
    let mut sc = Scanner::new(stdin.lock().bytes());
    let n = sc.next();
    println!("{}", solve(sc.vec(n)));
}


struct Scanner<R: Read> {
    buf: Vec<u8>,
    bytes: io::Bytes<R>,
}

#[allow(dead_code)]
impl<R: Read> Scanner<R> {
    fn new(bytes: io::Bytes<R>) -> Self {
        Scanner {
            buf: Vec::with_capacity(256),
            bytes: bytes,
        }
    }

    fn next<T: FromStr>(&mut self) -> T
    where
        <T as FromStr>::Err: Debug,
    {
        self.buf.clear();
        for c in self.bytes
            .by_ref()
            .map(|c| c.unwrap())
            .skip_while(|&c| c == ' ' as u8 || c == '\n' as u8)
            .take_while(|&c| !(c == ' ' as u8 || c == '\n' as u8))
        {
            self.buf.push(c);
        }
        str::from_utf8(&self.buf).unwrap().parse().unwrap()
    }

    fn vec<T: FromStr>(&mut self, n: usize) -> Vec<T>
    where
        <T as FromStr>::Err: Debug,
    {
        (0..n).map(|_| self.next()).collect()
    }

    fn pairs<A: FromStr, B: FromStr>(&mut self, n: usize) -> Vec<(A, B)>
    where
        <A as FromStr>::Err: Debug,
        <B as FromStr>::Err: Debug,
    {
        (0..n).map(|_| (self.next(), self.next())).collect()
    }

    fn trios<A: FromStr, B: FromStr, C: FromStr>(&mut self, n: usize) -> Vec<(A, B, C)>
    where
        <A as FromStr>::Err: Debug,
        <B as FromStr>::Err: Debug,
        <C as FromStr>::Err: Debug,
    {
        (0..n)
            .map(|_| (self.next(), self.next(), self.next()))
            .collect()
    }

    fn mat<T: FromStr>(&mut self, m: usize, n: usize) -> Vec<Vec<T>>
    where
        <T as FromStr>::Err: Debug,
    {
        (0..n).map(|_| self.vec(m)).collect()
    }
}


#[allow(dead_code)]
fn print_foreach<T: Display>(answer: &[T]) {
    for x in answer {
        println!("{}", x);
    }
}


#[allow(dead_code)]
fn print_yn(answer: bool, yes: &str, no: &str) {
    println!("{}", if answer { yes } else { no });
}


#[allow(dead_code)]
fn print_or<T: Display>(answer: &Option<T>, or: &T) {
    match *answer {
        Some(ref x) => println!("{}", x),
        None => println!("{}", or),
    }
}


Measured memory_bytes: 4352
# -*- coding: utf-8 -*-

import sys

sys.setrecursionlimit(10 ** 9)
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
INF=float('inf')

# Union-Find木
class UnionFind:
    def __init__(self, n):
        self.n = n
        # 親要素のノード番号を格納。par[x] == xの時そのノードは根
        # 1-indexedのままでOK、その場合は[0]は未使用
        self.par = [i for i in range(n+1)]
        # 木の高さを格納する（初期状態では0）
        self.rank = [0] * (n+1)
        # あるノードを根とする集合に属するノード数
        self.size = [1] * (n+1)
        # あるノードを根とする集合が木かどうか
        self.tree = [True] * (n+1)

    # 根の検索(グループ番号と言えなくもない)
    def find(self, x):
        # 根ならその番号を返す
        if self.par[x] == x:
            return x
        else:
            # 走査していく過程で親を書き換える
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    # 併合
    def union(self, x, y):
        # 根を探す
        x = self.find(x)
        y = self.find(y)

        # 木かどうかの判定用
        if x == y:
            self.tree[x] = False
            return
        if not self.tree[x] or not self.tree[y]:
            self.tree[x] = self.tree[y] = False

        # 木の高さを比較し、低いほうから高いほうに辺を張る
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
            self.size[y] += self.size[x]
        else:
            self.par[y] = x
            self.size[x] += self.size[y]
            # 木の高さが同じなら片方を1増やす
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

    # 同じ集合に属するか判定
    def same(self, x, y):
        return self.find(x) == self.find(y)

    # あるノードの属する集合のノード数
    def get_size(self, x):
        return self.size[self.find(x)]

    # 木かどうかの判定
    def is_tree(self, x):
        return self.tree[self.find(x)]

    # 集合の数
    def len(self):
        res = set()
        for i in range(self.n+1):
            res.add(self.find(i))
        # グループ0の分を引いて返却
        return len(res) - 1

N=INT()
G=[[None] for i in range(N)]
for i in range(N):
    G[i]=LIST()

# 隣接行列を辺集合(cost, u, v)にする
edges=[]
for i in range(N):
    for j in range(i+1, N):
        if G[i][j]!=-1:
            edges.append((G[i][j], i, j))

# クラスカル法
edges.sort()
uf=UnionFind(N)
ans=0
for cost, u, v in edges:
    if not uf.same(u, v):
        uf.union(u, v)
        ans+=cost
print(ans)



Measured memory_bytes: 6020
import sys

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

S = sr()[::-1]
MOD = 10 ** 9 + 7
answer = 0
dp = [0, 0, 1] #Cの数, BC数, 総数
for i in range(len(S)):
    s = S[i]
    if s == 'A':
        answer += dp[1]
    elif s == 'B':
        dp[1] += dp[0]
    elif s == 'C':
        dp[0] += dp[2]
    elif s == '?':
        answer *= 3
        answer += dp[1]
        dp[1] *= 3
        dp[1] += dp[0]
        dp[0] *= 3
        dp[0] += dp[2]
        dp[2] *= 3
    answer %= MOD
    dp[0] %= MOD; dp[1] %= MOD; dp[2] %= MOD
print(answer)


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

int main() {
  int n;
  std::cin >> n;
  std::vector<int> cards;
  for (int i = 0; i < n; ++i) {
    int input;
    std::cin >> input;
    cards.push_back(input);
  }
  int alice = 0, bob = 0;
  bool alice_turn = true;
  for( int i = 0; i < n; ++i ) {
    int* max = &cards[0];
    for (auto& number: cards) {
      max = (*max < number) ? &number : max;
    }
    if (alice_turn) {
      alice += *max;
    } else {
      bob += *max;
    }
    alice_turn = !alice_turn;
    *max = 0;
  }
  std::cout << alice - bob << std::endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define _GLIBCXX_DEBUG
#define rep(i,n) for(int i = 0; i < (int)(n); i++)
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define sz(x) (int)(x).size()
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
using namespace std;
using ll = long long;
using P = pair<int, int>;
using vi = vector<int>;
using vc = vector<char>;
using vb = vector<bool>;
using vs = vector<string>;
using vll = vector<long long>;
using vp = vector<pair<int, int>>;
using vvi = vector<vector<int>>;
using vvc = vector<vector<char>>;
using vvll = vector<vector<long long>>;
template<class T> inline bool chmax(T &a, T b) { if (a<b) {a=b; return 1;} return 0;}
template<class T> inline bool chmin(T &a, T b) { if (b<a) {a=b; return 1;} return 0;}

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

    ll x, y;
    cin >> x >> y;
    int cnt = 1;
    while (x * 2 <= y) {
        x *= 2;
        cnt++;
    }
    cout << cnt << endl;
}


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

typedef long long  int   ll;
ll a[200];
int main()
{ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    ll n,d5=0,d=0;
    cin>>n;

    for(int i=0;i<n;++i){
        cin>>a[i];}
       for(int i=0;i<n;++i){
        if(a[i]%2==0){d++;
            if(a[i]%5==0||a[i]%3==0)d5++;

        }}
        if(d5==d)cout<<"APPROVED";
        else cout<<"DENIED";

    return 0;
}

Measured memory_bytes: 256
import sys
sys.setrecursionlimit(2000)
def IN(): return map(int,input().split())
ans = 0; mod = pow(10,9)+7
h=int(input())
def dfs(x):
  if x==1: return 1
  else: 
    return dfs(x//2)*2+1

print(dfs(h))

Measured memory_bytes: 3060
#include<iostream>
#include<algorithm>
#include<vector>
#include<string>
#include<utility>
#include<map>
#include<set>
#include<queue>
#include<stack>
#include<functional>
#include<math.h>
using namespace std;
#define N (1000000000+7)
#define M (998244353)
#define INF 1e16
typedef long long ll;
typedef pair<ll,ll> P;




int main(void){
    string s;
    cin>>s;
    if(s.length()<5){
        cout<<"NO"<<endl;
        return 0;
    }
    string t="";
    string a[]={"dream","dreamer","erase","eraser"};
    for(int i=0;i<4;i++)reverse(a[i].begin(),a[i].end());
    reverse(s.begin(),s.end());
    bool flag = true;
    for(int i=0;i<s.length();i++){
        t.push_back(s[i]);
        //cout<<t<<endl;
        if(t.size()==5){
            for(int i=0;i<4;i++){
                if(t==a[i]){
                    t="";
                    break;
                }
            }
        }
        if(t.size()==6){
            for(int i=0;i<4;i++){
                if(t==a[i]){
                    t="";
                    break;
                }
            }
        }
        if(t.size()==7){
            for(int i=0;i<4;i++){
                if(t==a[i]){
                    flag = false;
                    t="";
                    break;
                }
            }
            if(flag){
                cout<<"NO"<<endl;
                return 0;
            }
            flag = true;
        }
    }
    cout<<"YES"<<endl;
    return 0;
}

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

#define NEW(p,n){p=malloc((n)*sizeof(p[0]));if(p==NULL){printf("not enough memory\n");exit(1);};}
//pの型の変数n個の要素分のメモリを確保し、そのアドレスをpに代入するマクロ

//char型のポインタ(=配列と意味は同じ)をString型と定義([0]から数える)
typedef char* String;

//S[0]から始まる文字列の長さを求める関数
int string_len(String str){
    int len=0;
    while(str[len]!=0){
        len++;
    }
    return len;
}

//文字列を標準入力から読み込み、それをString型のメモリを確保し直してくれる関数
//S[0]~S[n-1]までが入力で、S[n]は0になる
//文字列長さの上限は1000まで

String string_input(void){
    int i,len;
    char buf[1000];
    String str;
    scanf("%s",buf);//buf=入力した文字列が入るchar型の配列
    
    len=string_len(buf);//len=文字列の長さを表すint型変数
    NEW(str,len+1);//strはただのポインタだから、ここでNEWを使ってメモリを確保しなくちゃいけない
    for(i=0;i<len;i++){
        str[i]=buf[i];
    }
    str[len]=0;
    
    return str;
}

int main(void){
    String S=string_input(); //入力文字列

    int N=string_len(S);

    int count; //Yesなら1,Noなら0にする
    for(int i=0;i<N;i++){
        if(i%2==0){
            if(S[i]=='L'){
                count=0;
                break;
            }
            else{
                count=1;
            }
        }
        else{
            if(S[i]=='R'){
                count=0;
                break;
            }
            else{
                count=1;
            }
        }
    }

    if(count==1){
        printf("Yes\n");
    }
    else{
        printf("No\n");
    }
    return 0;
}

Measured memory_bytes: 128
#include<cstdio>
#include<cstring>
#include<iostream>
#include<cmath>
#include<ctime>
#include<algorithm>
using namespace std;
const int MR=1010;


int main(){
	int n;
	long long T[MR],A[MR];
	long long t=1,a=1;
	cin>>n;
	for(int i=0;i<n;i++)cin>>T[i]>>A[i];
	for(int i=0;i<n;i++){
		long long k=max((t+T[i]-1)/T[i],(a+A[i]-1)/A[i]);
		t=k*T[i];
		a=k*A[i];
	}
	cout<<t+a<<endl;
	return 0;
}



Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <vector>
#include <queue>
#include <string>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <algorithm>
using namespace std;

#define ll long long
#define PB push_back
#define PP pair<int, int>
#define IOS ios_base::sync_with_stdio(false); cin.tie(0)
#define all(x) x.begin(), x.end()
#define maxn

//structure

//declaration

//functions

int main(void)
{
	IOS;
	
	int n, k ,q;

	while(cin >> n >> k >> q)
	{
		int score[n+5];

		fill(score, score+(n+5), k);

		for(int i = 1; i <= q; i++)
		{
			int tmp;
			cin >> tmp;

			score[tmp]++;
		}

		for(int i = 1; i <= n; i++)
		{
			score[i] -= q;
			if(score[i] <= 0)
				cout << "No\n";
			else
			{
				cout << "Yes\n";
			}
		}
	}

	return 0;
}


Measured memory_bytes: 1024
use List::Util qw(max min sum);

my ($d) = split(/\s+/, <>);
my (@c) = (-1, split(/\s+/, <>));

my @s = ();
for my $i (1..$d) {
    $s[$i] = [-1, split(/\s+/, <>)];
}

sub score {
    my (@contest) = @_;
    my $ret = 0;
    my @last = (-1); for (1..26) { push @last, 0; }
    my $j = 1;

    for my $i (@contest) {
	$ret += $s[$j][$i];
	$last[$i] = $j;
	for (1..26) {
	    $ret -= $c[$_] * ($j-$last[$_]);
	}
	$j++;
    }
    return $ret;
}

sub max_index {
    my (@list) = @_;
    my $maxi = 0;
    for (my $i=0; $i<scalar(@list); $i++) {
	$maxi = $i if $list[$maxi] < $list[$i];
    }
    return $maxi;
}

sub over_index {
    my ($val, @list) = @_;
    my @ret = ();
    for (my $i=0; $i<scalar(@list); $i++) {
	push @ret, $i if $list[$i] > $val;
    }
    return @ret;
}

my @last = (-1); for (1..26) { push @last, 0; }
my @cont = ();
for my $j (1..$d) {
    my $max = max(@{$s[$j]});
    my @can = (1..26);
    #my @can = over_index($max*0.9, @{$s[$j]});
    #print "$j: ", join(",", @can), "\n";
    
    my $index = -1;
    my $maxre = 0;
    for my $i (@can) {
	my $re = $s[$j][$i] + $c[$i] * ($j-$last[$i]);
	if ($maxre < $re) { $maxre=$re; $index = $i; }
    }
    #push @cont, max_index(@{$s[$j]});
    push @cont, $index;
    $last[$index] = $j;
}

print join("\n", @cont), "\n";
#print score(@cont), "\n";


Measured memory_bytes: 6612
#include <bits/stdc++.h>
#define REP(i, n) for (int i = 0; i < n; i++)
#define FOR(i, m, n) for (int i = m; i < n; i++)
#define ll long long int

struct edge
{
  int to, cost;
};
typedef std::vector<std::vector<edge>> graph;
const ll MOD = 1000000007;
using namespace std;

int main()
{
  int n;
  cin >> n;
  int a[100000];
  REP(i, n)
  {
    cin >> a[i];
  }

  int b = 0;
  REP(i, n)
  {
    b = (b ^ a[i]);
  }

  if (b == 0)
  {
    cout << "Yes" << endl;
  }
  else
  {
    cout << "No" << endl;
  }
}


Measured memory_bytes: 640
r1, c1, r2, c2 = map(int, input().split())
mod = 10 ** 9 + 7


def cmb(n, r, mod):
    if r < 0 or r > n:
        return 0
    r = min(r, n - r)
    return g1[n] * pow(g1[r], mod - 2, mod) * pow(g1[n - r], mod - 2, mod) % mod


def make_table(n, mod=10 ** 9 + 7):
    N = n
    # 元テーブル
    g1 = [0] * (N + 1)
    g1[0] = 1
    g1[1] = 1

    tmp = g1[1]
    for i in range(2, N + 1):
        tmp = tmp * i % mod
        g1[i] = (g1[i - 1] * i) % mod

    return g1


def f(x, y):
    return ((x + 2) * cmb(x + y + 2, y, mod) - y - 1) * pow(y + 1, mod - 2, mod)


g1 = make_table(2 * 10 ** 6 + 10)
answer = f(c2, r2) - f(c2, r1 - 1) - f(c1 - 1, r2) + f(c1 - 1, r1 - 1)
answer %= mod
print(answer)


Measured memory_bytes: 82164
package main

import (
	"bufio"
	"fmt"
	"math"
	"os"
	"strconv"
)

func main() {
	var n int
	var t, a float64
	fmt.Scan(&n)
	fmt.Scan(&t, &a)
	h := make([]float64, n)
	sc := bufio.NewScanner(os.Stdin)
	sc.Split(bufio.ScanWords)
	for i := 0; i < n; i++ {
		sc.Scan()
		h[i], _ = strconv.ParseFloat(sc.Text(), 64)
	}
	index := -1
	dif := math.MaxFloat64
	for i := 0; i < n; i++ {
		d := math.Abs(a - (t - h[i]*0.006))
		if dif > d {
			dif = d
			index = i
		}
	}
	fmt.Println(index + 1)
}


Measured memory_bytes: 640
package main

import (
	"bufio"
	"fmt"
	"io"
	"math"
	"os"
	"sort"
	"strconv"
	"strings"

)

func main() {
	solve(os.Stdin, os.Stdout)
}

type ReaderEx struct {
	baseScanner *bufio.Scanner
	words       []string
	nextWordIdx func() int
	initWordIdx func()
}

func NewScannerEx(stdin io.Reader) *ReaderEx {
	var this ReaderEx
	var idx int
	this.baseScanner = bufio.NewScanner(stdin)
	this.baseScanner.Buffer(make([]byte, 0), 1E+11)
	this.nextWordIdx = func() int {
		cur := idx
		idx++
		return cur
	}
	this.initWordIdx = func() {
		idx = 0
	}
	return &this
}

func (me *ReaderEx) ScanAndSplit() (isScanned bool) {
	isScanned = me.baseScanner.Scan()

	me.words = strings.Fields(me.baseScanner.Text())
	me.initWordIdx()
	return
}

func (me *ReaderEx) Scan() (ok bool) {
	ok = me.baseScanner.Scan()
	return
}
func (me *ReaderEx) getString() string {
	return me.baseScanner.Text()
}

func (me *ReaderEx) getInt() int {
	n, err := strconv.Atoi(me.baseScanner.Text())
	defer func() {
		if err != nil {
			panic(err)
		}
	}()

	return n
}

func (me *ReaderEx) nextBytes() []byte {
	return []byte(me.words[me.nextWordIdx()])
}
func (me *ReaderEx) nextString() string {
	return me.words[me.nextWordIdx()]
}

type StringArray []string

func (me *ReaderEx) nextStringArray() StringArray {
	return me.words[me.nextWordIdx():]
}

func (me StringArray) toStrings() []string {
	return me
}

func (me StringArray) toInts() []int {
	strValues := me.toStrings()
	values := make([]int, len(strValues))
	for i, v := range strValues {
		n, err := strconv.Atoi(v)
		if err != nil {
			panic(err)
		}
		values[i] = n
	}
	return values
}
func (me *ReaderEx) nextInt() int {
	n, err := strconv.Atoi(me.words[me.nextWordIdx()])

	defer func() {
		if err != nil {
			panic(fmt.Sprintf("getInt(%d)", n))
		}
	}()
	return n
}

func pow(x, y, mod int) (ans int) {

	ans = 1
	for bit := 1 << uint(math.Floor(math.Log2(float64(y)))); ; bit >>= 1 {
		if y&bit != 0 {
			ans *= x
			if mod > 0 {
				ans %= mod
			}
		}
		if bit <= 1 {
			return
		}
		ans *= ans
		if mod > 0 {
			ans %= mod
		}
	}
}

type factType struct {
	prime int
	count int
}

func fact(n int) (facts []factType) {

	for i := 2; i*i <= n; i++ {
		if n%i == 0 {
			fa := factType{prime: i}
			for n%fa.prime == 0 {
				n /= fa.prime
				fa.count++
			}
			facts = append(facts, fa)
		}
	}
	if n > 1 {
		facts = append(facts, factType{prime: n, count: 1})
	}
	return facts
}
func dec2bin(n int) (ret []bool) {
	for bit := 1 << uint(math.Floor(math.Log2(float64(n)))); ; bit >>= 1 {
		ret = append(ret, n&bit != 0)

		if bit <= 1 {
			return
		}
	}

}

func abs(v int) int {
	if v < 0 {
		v = -v
	}
	return v
}

func solve(stdin io.Reader, stdout io.Writer) {
	r := NewScannerEx(stdin)
	r.Scan()
	r.getInt()
	r.ScanAndSplit()
	a := r.nextStringArray().toInts()

	dp := make(map[int]int)
	for _, value := range a {
		dp[value-1]++
		dp[value+2]--
	}

	dpidx := make([]int, len(dp))

	{
		i := 0
		for idx := range dp {
			dpidx[i] = idx
			i++
		}
		sort.Sort(sort.IntSlice(dpidx))
	}
	m := -1
	w := 0
	for _, v := range dpidx {
		w += dp[v]

		if w > m {
			m = w
		}
	}

	fmt.Fprintln(stdout, m)

}



Measured memory_bytes: 7424