akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define rep(i,n)   FOR(i,0,n)
#define pb emplace_back
typedef long long ll;
typedef pair<int,int> pint;

ll a[100001];
vector<int> fst[100001];
vector<int> g[100001];
bool used[100001];
bool used2[100001];
bool used3[100001];
int c[100001];
void dfs(int v,int cnt){
    rep(i,g[v].size()){
        if(used[g[v][i]]) continue;
        used[g[v][i]]=true;
        fst[cnt].pb(a[g[v][i]]);
        dfs(g[v][i],cnt);
    }
}
int main(){
    int n,m,xi,yi;
    cin>>n>>m;
    rep(i,n) cin>>a[i];
    if(n==1){
        cout<<0<<endl;
        return 0;
    }
    rep(i,m){
        cin>>xi>>yi;
        g[xi].pb(yi);
        g[yi].pb(xi);
    }
    int cnt=0;
    rep(i,n){
        if(used[i]) continue;
        used[i]=true;
        fst[cnt].pb(a[i]);
        dfs(i,cnt);
        ++cnt;
    }
    if(cnt<2){
        cout<<0<<endl;
        return 0;
    }
    /*rep(i,cnt){
        sort(fst[i].begin(),fst[i].end());
    }*/
    vector<pint> vp;
    rep(i,cnt){
        rep(j,fst[i].size()){
            vp.pb(make_pair(fst[i][j],i));
        }
    }
    sort(vp.begin(),vp.end());
    int sz=vp.size();
    ll sum=0,cnt2=0;
    rep(i,vp.size()){
        if(used2[vp[i].second])continue;
        sum+=vp[i].first;++cnt2;
        used2[vp[i].second]=true;
        used3[i]=true;
    }
    if(cnt==2&&cnt2==2){
        cout<<sum<<endl;
        return 0;
    }
    rep(i,vp.size()){
        if(used3[i]) continue;
        sum+=vp[i].first;++cnt2;
        if(cnt2>=(cnt-1)*2){
            cout<<sum<<endl;
            return 0;
        }
    }
    cout<<"Impossible"<<endl;
    return 0;
}

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

#define int long long
#define ld long double

#define rep(i,a,b) for(int i=a;i<b;i++)
#define repb(i,a,b) for(int i=a;i>b;i--)

#define pb push_back
#define mp make_pair
#define all(A) A.begin(),A.end()
#define allr(A) A.rbegin(),A.rend()
#define precise(i) fixed << setprecision(i)
#define fi first
#define se second

#define err() cout<<"\n==================================\n";
#define errA(A) for(auto i:A) cout<<i<<" "; cout<<"\n";
#define err1(a) cout<<#a<<" "<<a<<"\n";
#define err2(a,b) cout<<#a<<" "<<a<<" "<<#b<<" "<<b<<"\n";
#define err3(a,b,c) cout<<#a<<" "<<a<<" "<<#b<<" "<<b<<" "<<#c<<" "<<c<<"\n";
#define err4(a,b,c,d) cout<<#a<<" "<<a<<" "<<#b<<" "<<b<<" "<<#c<<" "<<c<<" "<<#d<<" "<<d<<"\n";

const int logN = 20;
const int M = 1000000007;
const int INF = 1e12;
#define PI 3.14159265;
const int N = 200005;

#define Pii pair<int,int>
#define Vi vector<int>
#define Vpii vector<Pii>

void solve()
{
       string s,t;
       cin>>s>>t;
       int n=s.size();
       int m=t.size();
       int mi=INF;
       rep(c,0,n-m+1)
       {
              int temp=0;
              rep(d,0,m)
              {
                     if(t[d]!=s[c+d])
                     {
                            temp++;
                     }
              }
              mi=min(mi, temp);
       }
       cout<<mi;
}

int32_t main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int t=1;
//    cin>>t;
    while(t--)
    {
           solve();
    }
    return 0;
}

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

int main()
{
	int64_t W, H, x, y;
	scanf("%lld%lld%lld%lld", &W, &H, &x, &y);
	printf("%lf %d\n", (double)W * H / 2, 2 * x == W && 2 * y == H? 1: 0);

	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
using Int = long long;
using Double = long double;
signed main(){
  Int h,w;
  cin>>w>>h;
  vector<string> s(h);
  for(Int i=0;i<h;i++) cin>>s[i];
  vector<vector<Int> > dg(h,vector<Int>(w,-1)),ds=dg;
  using T = pair<Int,int>;
  queue<T> qg,qs;
  
  for(Int i=0;i<h;i++){
    for(Int j=0;j<w;j++){
      if(s[i][j]=='g'){
	qg.push(T(i,j));
	dg[i][j]=0;
      }
      if(s[i][j]=='*'){
	qs.push(T(i,j));
	ds[i][j]=0;
      }
    }
  }

  Int dy[]={0,0,1,-1};
  Int dx[]={1,-1,0,0};
  auto bfs=[&](queue<T> &q,vector<vector<Int> > &d){
    while(!q.empty()){
      T t=q.front();q.pop();
      Int y=t.first,x=t.second;
      for(Int k=0;k<4;k++){
	Int ny=y+dy[k],nx=x+dx[k];
	if(s[ny][nx]=='#'||s[ny][nx]=='*') continue;
	if(~d[ny][nx]&&d[ny][nx]<=d[y][x]+1) continue;
	d[ny][nx]=d[y][x]+1;
	q.push(T(ny,nx));
      }
    }
    if(0){
      cout<<endl;
      for(Int i=0;i<h;i++){
	for(Int j=0;j<w;j++){
	  if(d[i][j]<0) cout<<"x";
	  else cout<<hex<<d[i][j];
	}
	cout<<endl;
      }
    }
  };

  bfs(qg,dg);
  bfs(qs,ds);

  auto get=[&](Int i,Int j,Double p){
    if(~dg[i][j]&&~ds[i][j])
      return min((Double)dg[i][j],ds[i][j]+p);
    if(~ds[i][j]) return ds[i][j]+p;
    if(~dg[i][j]) return (Double)dg[i][j];
    return Double(0);
  };
  
  auto calc=[&](Double p){
    Double q=0,c=0;
    for(Int i=0;i<h;i++){
      for(Int j=0;j<w;j++){
	if(s[i][j]=='#'||s[i][j]=='g'||s[i][j]=='*') continue;
	c+=1.0;
	q+=get(i,j,p);
      }
    }
    q/=c;
    //printf("%.12Lf %.12Lf\n",p, p-q);
    return p-q;
  };

  Double l=0,r=1e15;

  for(int k=0;k<300;k++){
  //while(abs(calc(l))>1e-10){
    Double m=(l+r)/2;
    if(calc(m)<=Double(0)) l=m;
    else r=m;
  }
  
  //printf("%.12f\n",calc(l));
  for(Int i=0;i<h;i++)
    for(Int j=0;j<w;j++)
      if(s[i][j]=='s')
	printf("%.12Lf\n",get(i,j,l));
  
  return 0;
}

Measured memory_bytes: 7424
#include <iostream>

using namespace std;

int
main(int argc, char **argv)
{
    int n,d;
    cin >> n;
    cin >> d;

    int x = d * 2 + 1;
    if(n % x == 0)
        cout << n / x << endl;
    else
        cout << n / x + 1 << endl;

    return 0;

}

Measured memory_bytes: 256
def divisors(n)
  r = []
  1.upto(n) do |i|
    break unless i <= n / i
    next unless (n % i).zero?
    r << i
    r << n / i if i != n / i
  end
  r
end

def worm(a, d)
  l, r = 0, N - 1
  s = a1 = a2 = 0
  while l <= r
    if s <= 0
      s += a[l]
      a1 += a[l]
      l += 1
    else
      s -= d - a[r]
      a2 += d - a[r]
      r -= 1
    end
  end
  [a1, a2].min
end

N, K = gets.split.map(&:to_i)
A = gets.split.map(&:to_i)
S = A.inject(:+)

p divisors(S).map{|d| worm(A.map{|i| i % d}.sort, d) <= K ? d : 1}.max


Measured memory_bytes: 8056
n,k = map(int,input().split())
a = [int(i) for i in input().split()]
a.sort()
mod = 10**9+7
fac = [0]*(n+1)
finv = [0]*(n+1)
def comb(n,k):
    if n < k: return 0
    if n < 0 or k < 0: return 0
    return fac[n]*finv[k]%mod*finv[n-k]%mod
fac[0] = finv[0] = 1
for i in range(1,n+1):
    fac[i] = fac[i-1]*i%mod
    finv[i] = pow(fac[i],mod-2,mod)
smin = 0
smax = 0
for i in range(n):
    smin += (a[i]*comb(n-i-1,k-1))%mod
    smin %= mod
    smax += (a[n-1-i]*comb(n-i-1,k-1))%mod
    smax %= mod
ans = (smax-smin)%mod
print(ans)

Measured memory_bytes: 14872
n = int(input())
sn = [input() for i in range(n)]
m = int(input())
sm = [input() for i in range(m)]

ans = 0

for i in range(n):
    ans_n = 0
    for j in range(m):
        if sn[i]==sm[j]:
            ans_n -= 1
    for k in range(n):
        if sn[i]==sn[k]:
            ans_n += 1
    ans = max(ans, ans_n)

print(ans)

Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
 
 
#define FAST std::ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define M 1000000007
#define mp make_pair
#define pb push_back
#define PB pop_back
#define sl(a) (int)a.length()
#define sz(a) (int)a.size()
#define lcase(a) (char)tolower(a)
#define ucase(a) (char)toupper(a)
#define precise(a) fixed<<setprecision(a)<<
#define F first
#define S second
#define I insert
#define pii pair<int,int>
#define trav(a, x) for(auto& a : x)
#define fl(i,n) for(int i = 0;i<n;i++)
#define rfl(n) for(int i = n-1;i>=0;i--)
#define time cerr << "\nTime elapsed: " << 1000 * clock() / CLOCKS_PER_SEC << "ms\n";
#define invect(data,n,commands) for(int i = 0;i<n;i++){int tmp;cin>>tmp;data.pb(tmp);commands}
#define inset(data,n,commands) for(int i = 0;i<n;i++){int tmp;cin>>tmp;data.I(tmp);commands}
#define display(x) trav(a,x) cout<<a<<" "; cout<<endl;
#define ingrid(data,n,commands) for(int i = 0; i<n; i++){cin>>data[i];commands}
#define section(a,b,w) set_intersection(a.begin(), a.end(),b.begin(), b.end(),back_inserter(w));
#define union(a,b,w) set_union(a.begin(), a.end(),b.begin(), b.end(),back_inserter(w));
#define copy(a,w) copy(a.begin(), a.end(),back_inserter(w));
#define all(data) data.begin(), data.end()
#define PI 3.14159265358979323844
#define endl '\n'
#define last(a) a[sz(a)-1]
 
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void __f(const char* name, Arg1&& arg1){
    std::cerr << name << " : " << arg1 << endl;
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args){
    const char* comma = strchr(names + 1, ',');std::cerr.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...);
}
 
// Graph DFS
const int fx[]={+1,-1,+0,+0};
const int fy[]={+0,+0,+1,-1};
 
//primes for hashing 937,991,1013,1409,1741
 
//Returns index of first element not less than key and more than key respectively
#define lb(data,key) lower_bound(all(data),key) - data.begin();
#define up(data,key) upper_bound(all(data),key) - data.begin();
#define fnd(data,key) find(all(data),key) - data.begin();
/* Long Long Int */
#define int long long int
int min(int a,int b)
{
    if(a>b)
        return b;
    else 
        return a;
}
std::vector<int> v,a;
int dp(int n)
{
    if(v[n]==-1)
        v[n]=min(dp(n+1)+abs(a[n]-a[n+1]),dp(n+2)+abs(a[n]-a[n+2]));
    return v[n];
}

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

fl(i,n)
{int j;
    cin>>j;a.pb(j);v.pb(-1);

}
v[v.size()-1]=0;
v[v.size()-2]=abs(a[n-1]-a[n-2]);
int k=dp(0);
cout<<k;
return;
}

 
signed main()
{
    FAST
    
    
    int t = 1;
//cin>>t;
    while(t--) 
    solve();
    
 
return 0;
}   







Measured memory_bytes: 4332
import bisect
import copy
import heapq
import sys
import itertools
import math
import queue
input = sys.stdin.readline
sys.setrecursionlimit(1000000)
mod = 10 ** 9 + 7

def read_values(): return map(int, input().split())
def read_index(): return map(lambda x: int(x) - 1, input().split())
def read_list(): return list(read_values())
def read_lists(N): return [read_list() for n in range(N)]
def init_dp1(init, N): return [init for _ in range(N)]
def init_dp2(init, N, M): return [[init for _ in range(M)] for _ in range(N)]


class UF:
    def __init__(self, N):
        self.parent = [i for i in range(N)]
    
    def get_parent(self, a):
        p = self.parent[a]
        if a == p:
            return a
        
        q = self.get_parent(p)
        self.parent[a] = q
        return q

    def make_pair(self, a, b):
        pa = self.get_parent(a)
        pb = self.get_parent(b)
        if pa == pb:
            return
        
        self.parent[pa] = pb
        self.parent[a] = pb
    
    def is_pair(self, a, b):
        return self.get_parent(a) == self.get_parent(b)

    def num_group(self):
        return sum(1 for i, j in enumerate(self.parent) if i == j)


def main():
    N, M = read_values()
    uf = UF(N)
    
    for _ in range(M):
        X, Y, _ = read_index()
        uf.make_pair(X, Y)

    print(uf.num_group())


if __name__ == "__main__":
    main()


Measured memory_bytes: 8204
#include <bits/stdc++.h>
#define rep(i, a, n) for(int i = a; i < n; i++)
#define REP(i, n) rep(i, 0, n)
#define repb(i, a, b) for(int i = a; i >= b; i--)
#define all(a) a.begin(), a.end()
#define int long long
#define chmax(x, y) x = max(x, y)
#define chmin(x, y) x = min(x, y)
using namespace std;
typedef pair<int, int> P;
const int mod = 1000000007;
const int INF = 1e12;

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n, k;
    cin >> n >> k;
    bool f[10] = {};
    rep(i, 0, k){
        int in; cin >> in;
        f[in] = true;
    }
    for(int i = n;; i++){
        string s = to_string(i);
        bool g = true;
        rep(j, 0, s.size()){
            if(f[s[j] - '0']) g = false;
        }
        if(g){
            cout << i << endl;
            return 0;
        }
    }
}

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

typedef struct{
  char key[2];
  int value;
} SHCD;

int main(){
  SHCD A[N],temp,B[N];
  int i,j,n,minj,flag;

  scanf("%d",&n);

  for(i = 0 ; i < n ; i++){
    scanf("%s",A[i].key);
    A[i].value = atoi(&A[i].key[1]);
    B[i] = A[i];  
  }

  i = 0;
  flag = 1;
  while(flag==1){
    flag = 0;
    for(j = n-1 ; j >= i ; j--){
      if(A[j].value < A[j-1].value){
	temp = A[j];
	A[j] = A[j-1];
	A[j-1] = temp;
      }
      flag = 1;
    }
    i+=1;
  }


  for(i = 0 ; i < n ; i++){
    minj = i;
    for(j = i ; j < n ; j++){
      if(B[j].value < B[minj].value){
	minj = j; 
      } 
    }
    if(B[j].value != B[minj].value ) {
      temp = B[minj];
      B[minj] = B[i];
      B[i] = temp;
    }
  }

  for(i = 0 ; i < n-1 ; i++){
    printf("%c%d ",A[i].key[0],A[i].value);
  }
  printf("%c%d\n",A[i].key[0],A[i].value);
  printf("Stable\n");

  for(i = 0 ; i < n-1 ; i++){
    printf("%c%d ",B[i].key[0],B[i].value);
  }
  printf("%c%d\n",B[i].key[0],B[i].value);
 
  flag = 0;
  for( i = 0 ; i < n ; i++ )
    {
      if( strcmp(A[i].key,B[i].key) != 0 ){
	flag = 1;
	break;
      }
    } 
  if( flag == 0 ) printf("Stable\n");
  else printf("Not stable\n");
  return 0;
}

Measured memory_bytes: 616
#ifdef _DEBUG
#include "MyLib.h"
#else
#define main_A main
#include "bits/stdc++.h" 
#include <regex>
#define _USE_MATH_DEFINES
#include <math.h>
#define FOR(i,s,e) for (int i = int(s); i < int(e); ++i)
#define REP(i,e) FOR(i,0,e)
#define INF (INT_MAX/2)
#define EPS (1.0e-8)
#define LINF (LONG_MAX/2)
const int MGN = 8;
const int ARY_SZ_MAX = 10000000;
using namespace std;
using ll = long long; using ull = unsigned long long;
using vi = vector<int>; using vvi = vector<vi>; using vvvi = vector<vvi>;
using vb = vector<bool>; using vvb = vector<vb>; using vvvb = vector<vvb>;
using vl = vector<ll>; using vvl = vector<vl>;
using vd = vector<double>; using vs = vector<string>;
using pii = pair<int, int>; using pll = pair<ll, ll>;
// functions

#endif


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

    string S; cin >> S;
    int N = S.size();

    string ans = "";
    REP(i,N) {
        if (S[i] == '1') ans += "9";
        else if (S[i] == '9') ans += "1";
        else ans += S[i];            
    }
    
    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 256
#include <stdio.h>
#define MAX 100
int main(){
  int i,n,s[MAX],max=0,min=0,point;
  float p,sum;
  scanf("%d",&n);
  while(n){
    sum=0;
    for(i=0;i<n;i++){
      scanf("%d",&s[i]);
    }
    max=s[0];
    min=s[0];
    for(i=0;i<n;i++){
      if(max<s[i]){
	max=s[i];
      }
      if(min>s[i]){
	min=s[i];
      }
    }
      for(i=0;i<n;i++){
	sum+=s[i];
      }
      sum-=max;
      sum-=min;
      n-=2;
      p=sum/n;
      point=(int)p;
      printf("%d\n",point);
      scanf("%d",&n);
  }


  return 0;
}

Measured memory_bytes: 600
#!/usr/bin/python3
# -*- coding: utf-8 -*-



N = int(input())
S = str(input())

r,i,j = 0,0,0
while j < N:
  t = S[i:j]
  if t in S[j:]:
    r = max(r,j-i)
    j += 1
  else:
    i += 1
print(r)

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

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

	for (int i = 3; i <= n; ++i) {
		int x = i;
		if (!(i % 3) || (i % 10) == 3) {
			cout << " " << i;
			continue;
		}
		x /= 10;
		while (x) {
			if (x % 10 == 3) {
				cout << " " << i;
				break;
			}
			x /= 10;
		}

	}
	cout << endl;
}


Measured memory_bytes: 3104
import java.util.*;

public class Main{
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int a = sc.nextInt();
        int b = sc.nextInt();
        if(a==2 || b==2){
            System.out.println("No");
        }else{
            System.out.println("Yes");
        }
        
    }
}

Measured memory_bytes: 22356
#include <bits/stdc++.h>
#include <boost/multiprecision/cpp_int.hpp>
#include <queue>

using boost::multiprecision::cpp_int;
using namespace std;

#if __has_include("print.hpp")
  #include "print.hpp"
#endif

#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define ALL(x) (x).begin(), (x).end()
#define RALL(x) (x).rbegin(), (x).rend()
#define MOD 1000000007

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

typedef long long ll;
typedef pair<ll, ll> p;
template< typename T >
struct edge {
  int src, to;
  T cost;

  edge(int to, T cost) : src(-1), to(to), cost(cost) {}

  edge(int src, int to, T cost) : src(src), to(to), cost(cost) {}

  edge &operator=(const int &x) {
    to = x;
    return *this;
  }

  operator int() const { return to; }
};

template< typename T >
using Edges = vector< edge< T > >;
template< typename T >
using WeightedGraph = vector< Edges< T > >;
using UnWeightedGraph = vector< vector< int > >;
template< typename T >
using Matrix = vector< vector< T > >;

template< typename T >
vector< T > dijkstra(WeightedGraph< T > &g, int s) {
  const auto INF = numeric_limits< T >::max();
  vector< T > dist(g.size(), INF);

  using Pi = pair< T, int >;
  priority_queue< Pi, vector< Pi >, greater< Pi > > que;
  dist[s] = 0;
  que.emplace(dist[s], s);
  while(!que.empty()) {
    T cost;
    int idx;
    tie(cost, idx) = que.top();
    que.pop();
    if(dist[idx] < cost) continue;
    for(auto &e : g[idx]) {
      auto next_cost = cost + e.cost;
      if(dist[e.to] <= next_cost) continue;
      dist[e.to] = next_cost;
      que.emplace(dist[e.to], e.to);
    }
  }
  return dist;
}

int main(){
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n, u, v;
  cin >> n >> u >> v;
  u--; v--;
  WeightedGraph<int> tree(n);
  rep(i, n-1){
    int from, to;
    cin >> from >> to;
    from--;to--;
    auto e = edge<int>(to, 1);
    tree[from].push_back(e);
    e = edge<int>(from, 1);
    tree[to].push_back(e);
  }

  // takahashi
  auto res1 = dijkstra(tree, u);
  // aoki
  auto res2 = dijkstra(tree, v);
  priority_queue<p> pq;
  for(int i = 0; i < n; i++) pq.push({res2[i], i});
  int res = 0;
  // print(res1);
  // print(res2);
  rep(i, n){
    // aoki
    int d = pq.top().first;
    int p = pq.top().second;
    pq.pop();
    if(d <= res1[p]) continue;
    chmax(res, d-1);
    // if((res2[p] - res1[p]) % 2 == 0) chmax(res, res1[p]-1);
    // else chmax(res, res1[p]);
  }
  cout << res << endl;

}


Measured memory_bytes: 9820
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#define loop(i,a,b) for(int i=a;i<b;i++)
#define rep(i,a) loop(i,0,a)
#define pb push_back
#define all(in) in.begin(),in.end()
using namespace std;
typedef long long ll;
typedef int Def;
typedef pair<Def,Def> pii;
typedef vector<Def> vi;
Def inf = sizeof(Def) == sizeof(long long) ? 2e18 : 1e9+10;

int main(){
  int n;
  while(cin>>n,n){
    int co=0,out=0,h=0;
    rep(i,n){
      string s;
      cin>>s;
      if(s[1]=='u')co++;
      else co--;
      if(co==2&&h==0){
	h=1;out++;
      }else if(co==0&&h==1){
	h=0;out++;
      }
    }
    cout<<out<<endl;
  }
}



Measured memory_bytes: 3148
// C++ 14
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define loop(__x, __start, __end) for(int __x = __start; __x < __end; __x++)
#define chmax(x,y) (x = max(x, y))
void solve(); int main() { solve(); return 0; }

void solve() {
  int a, b, c; cin >> a >> b >> c;
  cout << min(a*b, c) << endl;
}


Measured memory_bytes: 3604
#include<iostream>
#include<climits>
#include<vector>
#include<list>
#include<functional>
#include<algorithm>
#include<string>
#include<cmath>
#include<complex>
#include<set>
#include<map>
#include<stack>
#include<queue>
#include<deque>
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define REP(i,n) for(int i=0;i<(n);i++)
#define INF (int)1e9
#define INFL (ll)1e11
using namespace std;
typedef long long ll;
typedef pair<int, int> P;

int gcd(int x, int y) {
	return y == 0 ? x : gcd(y, x%y);
}

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

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

	int N, M;
	string S, T;
	cin >> N >> M >> S >> T;
	
	int g = gcd(N, M);
	ll l = lcm(N, M);
	int a = l / M, b = l / N;
	REP(i, g) {
		if (S[i*a] != T[i*b]) {
			l = -1;
			break;
		}
	}
	cout << l << "\n";

	return 0;
}


Measured memory_bytes: 640
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

#define ll                 long long
#define LL                 long long
#define pii                pair<int, int>
#define pll                pair<ll, ll>
#define pil                pair<int, ll>
#define pli                pair<ll, int>
#define vi                 vector<int>
#define vl                 vector<ll>
#define vii                vector<pii>
#define vll                vector<pll>
#define vil                vector<pil>
#define vli                vector<pli>
#define pb                 push_back
#define mp                 make_pair
#define ff                 first
#define ss                 second
#define sz(x)              (int)x.size()
#define TN                 typename
#define all(v)             v.begin(), v.end()
#define fill(a, b)         memset(a, b, sizeof(a))
#define endl               '\n'
#define Int                in()
#define Long               Lin()
#define policy_set         tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
#define policy_multiset    tree<int, null_type,less_equal<int>, rb_tree_tag,tree_order_statistics_node_update>

template <TN T> T gcd(T a, T b) {return !b ? a : gcd(b, a % b);}
template <TN T> T lcm(T a, T b) {return a * (b / gcd(a, b));}
template <TN T> inline void smin(T &a, T b) {a = a < b ? a : b;}
template <TN T> inline void smax(T &a, T b) {a = a > b ? a : b;}

#define error(args...) { string _s = #args; replace(_s.begin(), _s.end(), ',', ' '); stringstream _ss(_s); istream_iterator<string> _it(_ss); err(_it, args); }
void err(istream_iterator<string> it) {cout << endl ;}
template<typename T, typename... Args>
void err(istream_iterator<string> it, T a, Args... args) {
    cerr << *it << " = " << a << ", " ;
    err(++it, args...);
}

inline int in() {int n; scanf("%d", &n); return n;}
inline ll Lin() {ll n; scanf("%lld", &n); return n;}
inline double Din() {double n; scanf("%lf", &n); return n;}

const int mod        = (int)1e9 + 7;
const ll  Mod        = (ll)1e9 + 7;

inline int add(int a, int b) {a += b; return a >= mod ? a - mod : a;}
inline int sub(int a, int b) {a -= b; return a < 0 ? a + mod : a;}
inline int mul(int a, int b) {return (ll)a * b % mod;}

const int inf        = (int)2e9 + 5;
const ll  Inf        = (ll)1e18 + 5;
const int N          = 2e5 + 5;



int solve() {
    int n,cnt=0,x=0;
    cin>>n;
    while(n--){
    	int a,b;
    	cin>>a>>b;
    	if (a==b)
    	{
    		cnt++;
    	}
    	if (cnt>=3)
    	{
    		x=1;
    	}
    	if(a!=b&&cnt<3){
    		cnt=0;
    	}
    }
    if (x==1)
    {
    	cout<<"Yes"<<endl;
    }
    else
    	cout<<"No"<<endl;
    return 0;
}

int main() {
    //ios_base::sync_with_stdio(false); cin.tie(NULL);
    int test = 1, tc = 0;
    //scanf("%d", &test);
    //cin >> test;
    while (test--) {
        //printf("Case %d: ", ++tc);
        solve();
    }
    return 0;
}

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

abc = list(map(int, input().split()))

abc.sort()

is575 = True

if abc[0] != 5:
    is575 = False
if abc[1] != 5:
    is575 = False
if abc[2] != 7:
    is575 = False

if is575:
    print("YES")
else:
    print("NO")


Measured memory_bytes: 3060
a = int(input())
b = input().split(" ")
i = 0
s = 1
f = 0
while i < a :
    if b[i] == "0" :
        print(0)
        f = f + 1
    i = i + 1
i = 0
while (i < a) and f == 0 :
    s = s * int(b[i])
    i = i + 1
    if s > (10 ** 18):
        print("-1")
        break
    if (s <= 10 ** 18) and (i == a):
        print(s)


Measured memory_bytes: 19524
def main():
    N = int(input())
    ll = input().split(" ")
    d = []
    result = 0
    for l in ll:
        d.append(int(l))
    for i in range(N):
        for j in range(i + 1, N):
            result += d[i] * d[j]
    print(result)


if __name__ == '__main__':
    main()

Measured memory_bytes: 3060
#include<stdio.h>



int main(void)

{
   
	int w,h,x,y,r;


   

	scanf("%d%d%d%d%d",&w,&h,&x,&y,&r);


   

	if(0<=x-r && 0<=y-r && x+r<=w && y+r<=h)

 
 		printf("Yes\n");


  
	 else
   
 
		 printf("No\n");


  

	 return 0;


}



Measured memory_bytes: 2108
#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
#include <random>
#define rep(i,n) for(int i=0;i<n;++i)
#define rep1(i,n) for(int i=1;i<=n;++i)
using namespace std;
template<class T>bool chmax(T &a, const T &b) { if(a < b){ a = b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if(a > b){ a = b; return 1; } return 0; }
typedef long long ll;
ll rand26() {
  random_device rnd;
  mt19937 mt(rnd());
  uniform_real_distribution<> rand(0, 25);
  return (ll)rand(mt);
}
ll rand365() {
  random_device rnd;
  mt19937 mt(rnd());
  uniform_real_distribution<> rand(0, 364);
  return (ll)rand(mt);
}
int main()
{
  ll D; cin >> D;
  vector<ll> c(26);
  rep(i,26) cin >> c[i];
  vector<vector<ll>> s(D, vector<ll>(26));
  vector<ll> t(D);  
  rep(i,D) {
    ll smax = -1;
    rep(j,26) {
      cin >> s[i][j];
      if(smax <= s[i][j]) {
	smax = s[i][j];
	t[i] = j;
      }
    }
  }
  
  ll m = 26*365*140;
  vector<ll> d(m), q(m);
  rep(k,140) {
    rep(i,26) {
      rep(j,365) {
	d[k*26*365 + i*365 + j] = (j + k) % 365;
	q[k*26*365 + i*365 + j] = (i + k) % 26;
      }
    }
  }
  
  vector<set<ll>> st(26);
  rep(i,26) {
    st[i].insert(-1);
    st[i].insert(D);    
  }
  rep(i,D) {
    st[t[i]].insert(i);
  }

  ll res = 0;
  // ペナルティ
  vector<ll> pen(26, 0);
  rep(i,26) {
    auto it = st[i].begin();
    it++;
    while(it != st[i].end()) {
      auto it2 = it;
      it2--;
      ll x = *it - *it2 - 1;
      res -= x * (x + 1) / 2 * c[i];
      pen[i] += x * (x + 1) / 2 * c[i];
      it++;
    }
  }
  rep(i,D) {
    res += s[i][t[i]];
  }

  rep(i,m){
    ll oldres = res;
    ll old = t[d[i]];
    ll neww = q[i];
    if(old == neww) continue;
    set<ll> oldst1 = st[old];
    set<ll> oldst2 = st[neww];    
    ll oldpen1 = pen[old];
    ll oldpen2 = pen[neww];
    
    res += s[d[i]][neww] - s[d[i]][old];
    st[old].erase(d[i]);
    st[neww].insert(d[i]);    
    // old
    res += pen[old];
    pen[old] = 0;
    auto it = st[old].begin();
    it++;
    while(it != st[old].end()) {
      auto it2 = it;
      it2--;
      ll x = *it - *it2 - 1;
      res -= x * (x + 1) / 2 * c[old];
      pen[old] += x * (x + 1) / 2 * c[old];
      it++;
    }
    // new
    res += pen[neww];
    pen[neww] = 0;
    it = st[neww].begin();
    it++;
    while(it != st[neww].end()) {
      auto it2 = it;
      it2--;
      ll x = *it - *it2 - 1;
      res -= x * (x + 1) / 2 * c[neww];
      pen[neww] += x * (x + 1) / 2 * c[neww];
      it++;
    }

    if(oldres < res) {
      t[d[i]] = neww;
    }
    else {
      t[d[i]] = old;
      st[old] = oldst1;
      st[neww] = oldst2;
      pen[old] = oldpen1;
      pen[neww] = oldpen2;      
    }
  }

  rep(i,D) cout << t[i]+1 << "\n";
  
  return 0;
}


Measured memory_bytes: 24112
#include<iostream>
#include<algorithm>
#include<vector>
#include<stack>
#include<queue>
#include<cstdio>
#include<climits>
#include<cmath>
#include<cstring>
#include<map>
#include<string>
#include<complex>

#define f first
#define s second
#define mp make_pair

#define REP(i,n) for(int i=0; i<(int)(n); i++)
#define FOR(i,c) for(__typeof((c).begin()) i=(c).begin(); i!=(c).end(); i++)
#define ALL(c) (c).begin(), (c).end()

using namespace std;

typedef unsigned int uint;
typedef long long ll;

typedef pair<double,pair<int,int> > pp;

int main(){
  int an,bn,r;
  while(scanf("%d%d%d",&an,&bn,&r), an+bn+r){
    int ans = 0;

    vector<pp> p(an);

    REP(i,an){
      int x, y;
      scanf("%d%d", &x, &y);

      p[i].f = sqrt((double)(x*x + y*y));
      p[i].s.f = x; p[i].s.s = y;
    }

    sort(p.begin(), p.end());

    REP(i,bn){
      int x, y;
      scanf("%d%d", &x, &y);

      double rmin = sqrt((double)(x*x + y*y)) - r*4 - 0.1;
      double rmax = sqrt((double)(x*x + y*y)) + r*4 + 0.1;
      vector<pp>::iterator now = lower_bound(p.begin(), p.end(), pp(rmin,mp(INT_MIN,INT_MIN)));
      vector<pp>::iterator end = upper_bound(p.begin(), p.end(), pp(rmax,mp(INT_MAX,INT_MAX)));
      while(now != end){
	int xx = now->s.f, yy = now->s.s;
	if((x-xx)*(x-xx) + (y-yy)*(y-yy) <= 4*r * 4*r) ans++;
	now++;
      }
    }

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

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

int main(){
  ios_base::sync_with_stdio(0); cin.tie(0);
  int n; cin >> n;
  (n%2 == 0) ? cout << n/2-1 << "\n" : cout << (int)n/2 << "\n";
  return 0;
}

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

int main()
{
    std::string s;
    std::cin >> s;
    for (int i = 1; i < 3; i++) {
        if (s[i-1] != s[i]) {
            std::cout << "Yes" << std::endl;
            return 0;
        }
    }
    std::cout << "No" << std::endl;

    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
using namespace std;
int A[100002]={0};
int kaga(int KA,int GA){
	if(GA<KA)swap(KA,GA);
	return A[GA]-A[KA];
}
int main(){
	int n,m;
	int ans=0,pos=1;
	cin>>n>>m;
	
	
	for(int i=2;i<=n;i++){
		cin>>A[i];
		A[i]+=A[i-1];
	}
	
	for(int i=1;i<=m;i++){
		cin>>n;
		ans+=kaga(pos,pos+n);
		ans%=100000;
		pos+=n;
	}
	cout<<ans<<endl;
	
	
	
	return 0;
}


Measured memory_bytes: 1548
#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
#include <numeric>
typedef long long Int;
#define rep(i,a,b) for(Int i=a;i<b;++i)
#define rrep(i,a,b) for(Int i=a;i>=b;--i)
using namespace std;

vector<vector<long long>> graph;

void dfs(long long now, long long parent, long long dist, long long& maxDist, long long& farthestNode) {
    if (dist > maxDist) {
        maxDist = dist;
        farthestNode = now;
    }

    for(auto next : graph[now]) {
        if (next == parent) continue;
        dfs(next, now, dist+1, maxDist, farthestNode);
    }
}

void TreeDiameter(long long& diameter, long long& from, long long& to) {
    long long maxDist = -1, farthestNode = -1;
    dfs(0, -1, 0, maxDist, farthestNode);
    from = farthestNode;
    maxDist = 0;
    dfs(from, -1, 0, maxDist, farthestNode);
    to = farthestNode;
    diameter = maxDist;
}

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

    long long N; cin >> N;
    graph.assign(N, vector<long long>());

    for(long long i = 0; i < N-1; ++i) {
        long long A, B; cin >> A >> B;
        --A, --B;
        graph[A].emplace_back(B);
        graph[B].emplace_back(A);
    }

    long long diameter = -1, from = -1, to = -1;
    TreeDiameter(diameter, from, to);

    if (diameter % 3 == 1) cout << "Second" << endl;
    else cout << "First" << endl;
}


Measured memory_bytes: 167424
import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        // Your code here!
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] array = new int[n];
        for (int i = 0; i < n; i++) {
            array[i] = sc.nextInt();
        }
        
        // ans: 連続部分列の和が0になるi, jのパターン数
        long ans = 0;
        
        // 式変形
        // ・連続部分列の和が0になるi, j
        // -> s[j+1] - s[i] = 0
        // -> s[j+1] = s[i] のパターン数
        
        // s: 累積和
        long[] s = new long[n+1];
        for (int i = 0; i < n; i++) {
            s[i+1] = s[i] + array[i];
        }
        
        // i, jのパターン数を数え上げる
        Map<Long, Integer> map = new HashMap<Long, Integer>();
        for (int i = 0; i <= n; i++) {
            long key = s[i];
            int cnt = map.getOrDefault(key, 0);
            
            ans += cnt;
            map.put(key, ++cnt);
        }
        System.out.println(ans);
    }
}

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

//宣言
typedef long long ll;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> PII;

//数値
#define MOD 1000000007
#define INF (1<<20)
const double EPS = 1e-10;
const double PI = acos(-1.0);

//操作
#define FOR(i,a,b) for(int i=a;i<b;i++)
#define REP(i,n) FOR(i,0,n)
#define REPB(i,n) for(int i=n;i>=0;i--)
#define SORT(A) sort(A,A+sizeof(A)/sizeof(A[0]))
#define VSORT(A) sort(A.begin(),A.end())
#define EXIST(s,e) (s.find(e)!=s.end())
#define PB push_back
#define MP make_pair

//DEBUG
//debug
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;

int main() {

	int n, a[100000] = { 0 };
	int b[100001] = { 0 };
	int ans = 0;
	cin >> n;
	for (int i = 0;i < n;i++) {
		cin >> a[i];
		if (a[i] > 100000) ans++;
		else b[a[i]]++;
	}
	for (int i =1;i <= 100000;i++) {
		if (b[i] < i ) ans += b[i];
		else ans +=b[i] - i;
	}
	cout << ans << endl;
	


}



Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define rep(i,n)  FOR(i,0,n)
#define req(i,n) for(int i = 1;i <=n;i++)
#define pai 3.14159265358979323846
const int INF = 1001001001;
typedef long long ll;
int A[3][3], N;
bool punched[3][3];
bool ok[3][3];
using Graph = vector<vector<int>>;
vector<vector<int>> field;
vector<bool> seen;

const int MOD = 1000000007;
typedef pair<int,int> P;

//最大公約数
int gcd(int a,int b){
	if (a%b == 0){
		return b;
	}
	else{
		return gcd(b,a%b);
	}

}

//最小公倍数
int lcm(int a,int b){
	return a /gcd(a,b) * b;
}

//素数判定
bool is_prime(long long N) {
    if (N == 1) return false;
    for (long long i = 2; i * i <= N; ++i) {
        if (N % i == 0) return false;
    }
    return true;
}



  








      
  int main() {
    string S; int K; cin >> S >> K;
    int ichinum = 0;
    for (int i = 0; i < S.size(); ++i) {
        if (S[i] == '1') ++ichinum;
        else break;
    }
    if (ichinum >= K) cout << 1 << endl;
    else cout << S[ichinum] << endl;
}

Measured memory_bytes: 3584
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const double pi = acos(-1);
#define FOR(i,a,b) for (ll i=(a),__last_##i=(b);i<__last_##i;i++)
#define RFOR(i,a,b) for (ll i=(b)-1,__last_##i=(a);i>=__last_##i;i--)
#define REP(i,n) FOR(i,0,n)
#define RREP(i,n) RFOR(i,0,n)
#define __GET_MACRO3(_1, _2, _3, NAME, ...) NAME
#define rep(...) __GET_MACRO3(__VA_ARGS__, FOR, REP)(__VA_ARGS__)
#define rrep(...) __GET_MACRO3(__VA_ARGS__, RFOR, RREP)(__VA_ARGS__)
template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) {
REP(i,v.size()){if(i)os<<" ";os<<v[i];}return os;}
template<typename T> ostream& operator<<(ostream& os, const vector<vector<T>>& v) {
REP(i,v.size()){if(i)os<<endl;os<<v[i];}return os;}


int maxtime(int x)
{
    return (x + 9) / 10 * 10;
}

int remtime(int x)
{
    return maxtime(x) - x;
}

int main()
{
    int a, b, c, d, e;
    cin >> a >> b >> c >> d >> e;
    int sum = maxtime(a) + maxtime(b) + maxtime(c) + maxtime(d) + maxtime(e);

    int ans = sum - max({remtime(a), remtime(b), remtime(c), remtime(d), remtime(e)});

    cout << ans << endl;
}

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

int main() {
	int N, K;
  cin >> N >> K;
  double ret=0;
  for(int i=1;i<=N;i++){
    double tmp=1.0/N;
    int now=i;
    while(now<K){
      now*=2;
      tmp/=2;
    }
    ret+=tmp;
  }
  cout<<setprecision(12)<<ret<<endl;
}


Measured memory_bytes: 256
import java.util.*;

public class Main {

    public static void main(String args[]) {

        // 入力
        Scanner sc = new Scanner(System.in);
        int n = Integer.parseInt(sc.next());
        int k = Integer.parseInt(sc.next());
        Integer[] x = new Integer[n];
        Arrays.setAll(x, i -> Integer.parseInt(sc.next()));
        sc.close();

        // 主処理
        int result = 0;
        for (int i = 0; i < n; i++) {
            int a = Math.abs(0 - x[i]);
            int b = Math.abs(k - x[i]);
            int min = Math.min(a, b);
            result += min * 2;
        }

        // 出力
        System.out.println(result);
    }
}


Measured memory_bytes: 26836
def solve():
    s = input()
    s = set(s)
    dic = set(["a", "b", "c", "d", "e", "f", "g", "h", "i", "j", "k", "l", "m", "n", "o", "p", "q", "r", "s", "t", "u", "v", "w", "x", "y", "z"])
    s = sorted(list(dic - s))
    if len(s) == 0:
        print("None")
        return
    print(s[0])


solve()

Measured memory_bytes: 3188
#include <iostream>
#include <algorithm>
#include <bitset>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <cstring>
#include <utility>
#include <vector>
#include <complex>
#include <valarray>
#include <fstream>
#include <cassert>
#include <cmath>
#include <functional>
#include <iomanip>
#include <numeric>
using namespace std;
# define maxn 100000
int main() {
  int n ,a[maxn],sum(0);
  cin>>n;
  for (int i(0);i<n;i++){
    cin>>a[i];
    sum+=a[i];
  }
  double ave= (double)sum/n;
  double min=abs(a[0]-ave);
  int out(0);
  for (int i(n-1);i>=0;i--){
    if (min>=abs(a[i]-ave)){
      min=abs(a[i]-ave);
      out=i;
    }
  }
  cout<<out;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define REP(i,n) for(ll i=0;i<(ll)(n);i++)
#define REPD(i,n) for(ll i=n-1;i>=0;i--)
#define FOR(i,a,b) for(ll i=a;i<=(ll)(b);i++)
#define FORD(i,a,b) for(ll i=a;i>=(ll)(b);i--)
#define ALL(x) (x).begin(),(x).end() 
#define SIZE(x) ((ll)(x).size())
#define MAX(x) *max_element(ALL(x))
#define MIN(x) *min_element(ALL(x))
#define INF 1000000000
using namespace std;
typedef long long ll;

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

vector<pair<ll, ll>> prime_fac(ll N){
    vector<pair<ll, ll>> res;
    for(ll a = 2; a*a <= N; a++){
        if (N%a != 0) continue;
        ll ex = 0;

        while(N%a == 0){
            ex++;
            N /= a;
        }

        res.push_back({a, ex});
    }
    if (N != 1) res.push_back({N, 1});
    return res;
}

int main() {
    ll A, B;
    cin >> A >> B;

    vector<pair<ll, ll>> res;
    res = prime_fac(gcd(A, B));
    cout << SIZE(res) + 1 << endl;
}

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

#define int long long
#define rep(i, a, n) for (int i = a; i < n; i++)
#define pb push_back
#define eb emplace_back
#define dump(x) cout << #x << " = " << (x) << endl
#define chk() cout << "now" << endl;
#define ALL(x) (x).begin(), (x).end()
#define SORT(c) sort((c).begin(), (c).end())
#define SORTG(c) sort(ALL(c), greater<int>());
#define fi first
#define se second
int INF = 1e9 + 7;

typedef pair<int, int> P;
typedef vector<int> vi;
typedef vector<vector<int>> mat;

template <class T>
inline bool chmin(T& a, T b) {
  if (a > b) {
    a = b;
    return true;
  }
  return false;
}
template <class T>
inline bool chmax(T& a, T b) {
  if (a < b) {
    a = b;
    return true;
  }
  return false;
}

int n;
vector<double> a;

void solve() {
  cin >> n;
  a.resize(n);
  rep(i, 0, n) cin >> a[i];

  double sum = 0;
  rep(i, 0, n) {
    double b = 1.0 / a[i];
    sum += b;
  }
  cout << 1.0 / sum << endl;
}

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

  cout << fixed << setprecision(10);

  solve();

  return 0;
}


Measured memory_bytes: 256
import java.util.Scanner;

public class Main {
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);

		int n = sc.nextInt();

		int[] a = new int[n];
		int[] b = new int[n];

		long ans = 0;
		long t;

		for(int i=0; i<n; i++){
			a[i] = sc.nextInt();
			b[i] = sc.nextInt();
		}

		for(int i=n-1; i>=0; i--){
			t = a[i] + ans;
			if(t % b[i] == 0) continue;
			ans += b[i] - t % b[i];
		}

		System.out.println(ans);
	}
}


Measured memory_bytes: 72764
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using vb=vector<bool>;
using vvb=vector<vb>;
using vd=vector<double>;
using vvd=vector<vd>;
using vi=vector<int>;
using vvi=vector<vi>;
using vl=vector<ll>;
using vvl=vector<vl>;
using pii=pair<int,int>;
using pll=pair<ll,ll>;
using tll=tuple<ll,ll>;
using tlll=tuple<ll,ll,ll>;
using vs=vector<string>;

#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define rep(i,n) range(i,0,n)
#define rrep(i,n) for(int i=(n)-1;i>=0;i--)
#define range(i,a,n) for(int i=(a);i<(n);i++)

#define LINF ((ll)1ll<<60)
#define INF ((int)1<<30)
#define EPS (1e-9)
#define MOD (1000000007ll)
#define fcout(a) cout<<setprecision(a)<<fixed
#define fs first
#define sc second
#define PI 3.1415926535897932384

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

template<class T>bool chmax(T&a,T b){if(a<b){a=b; return true;}return false;}
template<class T>bool chmin(T&a,T b){if(a>b){a=b; return true;}return false;}
template<class S>S acm(vector<S>&a){return accumulate(all(a),S());}
template<class S>S max(vector<S>&a){return *max_element(all(a));}
template<class S>S min(vector<S>&a){return *min_element(all(a));}
void YN(bool b){cout<<(b?"YES":"NO")<<"\n";}
void Yn(bool b){cout<<(b?"Yes":"No")<<"\n";}
void yn(bool b){cout<<(b?"yes":"no")<<"\n";}

ll max(int a,ll b){return max((ll)a,b);} ll max(ll a,int b){return max(a,(ll)b);}
template<class T>void puta(T&&t){cout<<t<<"\n";}
template<class H,class...T>void puta(H&&h,T&&...t){cout<<h<<' ';puta(t...);}
template<class S,class T>ostream&operator<<(ostream&os,pair<S,T>p){os<<"["<<p.first<<", "<<p.second<<"]";return os;};
template<class S>auto&operator<<(ostream&os,vector<S>t){bool a=1; for(auto s:t){os<<(a?"":" ")<<s;a=0;} return os;}

vl pr;

bool isPrime(ll n){
	if(n==1)return false;
	for(ll i=2;i*i<=n;i++)if(n%i==0)return false;
	return true;
}

void solve(int m,int a,int b){
	ll mx=0;
	ll ansa,ansb;
	rep(i,pr.size()){
		range(j,i,pr.size()){
			if(pr[i]*b<pr[j]*a)continue;
			else if(pr[i]*pr[j]>m)j+=pr.size();
			else if(chmax(mx,pr[i]*pr[j])){
				ansa=pr[i];
				ansb=pr[j];
			}
		}
	}
	cout<<ansa<<" "<<ansb<<endl;
}

int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	int m,a,b;
	range(i,1,100008){
		if(isPrime(i))pr.push_back(i);
	}
	while(cin>>m>>a>>b,m)solve(m,a,b);
}



Measured memory_bytes: 3256
#include <algorithm>
#include <bitset>
#include <tuple>
#include <cstdint>
#include <cstdio>
#include <cctype>
#include <assert.h>
#include <stdlib.h>
#include <stdio.h>
#include <cassert>
#include <cfloat>
#include <climits>
#include <cmath>
#include <complex>
#include <ctime>
#include <deque>
#include <fstream>
#include <functional>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <list>
#include <limits>
#include <map>
#include <memory>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
using ll=long long;
using lb = long double;
//#define int long long
//#define _CRT_SECURE_NO_WARNINGS
#define rep(i, n) for (int i = 0; i < n; i++)
#define _GLIBCXX_DEBUG
const int MOD = 1e9 + 7;
const int INF = 1e18 + 9;
constexpr long double pi = 3.141592653589793238462643383279; //円周率
/*---------------------便利な関数--------------------------------------*/
int fact(int i) {       //階乗
    if (i == 0) return 1;
    return (fact(i - 1)) * i;
}

int gcd(int a, int b) {        //最大公約数
    if (b == 0) return a;
    return gcd(b, a % b);
}

int lcm(int a, int b) {      //最小公倍数
    return a * b / gcd(a, b);
}

int keta(int n) {        //桁数を求める
    if (n == 0) return 1;
    int count = 0;
    while (n != 0) {
        n /= 10;
        count++;
    }
    return count;
}

int ketasum(int n) {    //各桁の和
    int sum = 0;
    while (n != 0) {
        sum += n % 10;
        n /= 10;
    }
    return sum;
}
//最小化問題(DP)
template<class T> inline bool chmin(T& a, T b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}
//最大化問題(DP)
template<class T> inline bool chmax(T& a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}
/*-------------ここまで---------------------------------------------*/
int main(){
    int a, b, c;
    cin >> a >> b >> c;
    cout << max({ a,b,c }) * 9 + a + b + c << endl;
    return 0;
}

Measured memory_bytes: 3608
#include<bits/stdc++.h>
using namespace std;
long long n,sum=0;
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
		{
			for(int k=1;k<=n;k++)
				sum+=__gcd(i,__gcd(j,k));	
		}	
	}	
	cout<<sum;
}

Measured memory_bytes: 3636
n, m = gets.split.map(&:to_i)
h = gets.split.map(&:to_i)

a = Array.new n 
b = Array.new n 
m.times do |i|
  a[i], b[i] = gets.split.map(&:to_i)
end

routes = {}

m.times do |i|
  ah = h[a[i]-1]
  bh = h[b[i]-1]
  if ah > bh
    routes[b[i]] ||= 1
  elsif bh > ah 
    routes[a[i]] ||= 1
  else
    routes[a[i]] ||= 1
    routes[b[i]] ||= 1
  end
end

puts n - routes.keys.size

Measured memory_bytes: 25588
N,M,X = map(int,input().split())
C = [0]*N
A = [[] for _ in range(N)]
for i in range(N):
    CA = list(map(int,input().split()))
    C[i] = CA[0]
    A[i] = CA[1:]

INF = 10**10
ans = INF
for i in range(2**N):
    res = 0
    temp = i
    state = [False]*N
    for j in range(N):
        state[j] = temp&1
        temp >>= 1
        if temp==0:
            break
    
    D = [0]*M
    for j in range(N):
        if not state[j]:
            continue
        res += C[j]
        for t in range(M):
            D[t] += A[j][t]
    
    flag = True
    for d in D:
        if d<X:
            flag = False
            break
    if flag:
        ans = min(ans,res)

if ans == INF:
    ans = -1
print(ans)






Measured memory_bytes: 68564
#include<bits/stdc++.h>
#define Fast ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define Freed freopen ("0in.txt","r",stdin);
#define Fout freopen ("0out.txt","w",stdout);
#define ll long long int
#define pb push_back
#define mp make_pair
#define pi acos(-1.0)
#define Mod 1000000007
#define limit 1000008
using namespace std;
bool vis[limit];
vector<int>g[limit];
void dfs(int u)
{
    vis[u] = 1;
    for(int v:g[u])
    {
        if(!vis[v])
            dfs(v);
    }
}
void solve(int t)
{
    int i,j,n,m,k;
    cin >> n >> m;
    for(i=0; i<m; i++)
    {
        int u,v;
        cin >> u >> v;
        g[u].pb(v);
        g[v].pb(u);
    }
    int ct=0;
    dfs(1);
    for(i=1; i<=n; i++)
    {
        if(!vis[i])
        {
            ct++;
            dfs(i);
        }
    }
    cout <<ct<<endl;
    return ;
}
int  main()
{
//    Fast
//    Freed
//    Fout
    int t,tt=1;
  //  cin >> tt;
    for(t=1; t<=tt; t++)
        solve(t);
    return 0;
}



Measured memory_bytes: 30724
group_1 = [1, 3, 5, 7, 8, 10, 12]
group_2 = [4, 6, 9, 11]

x, y = map(int, input().split())

if x in group_1 and y in group_1:
    print("Yes")
elif x in group_2 and y in group_2:
    print("Yes")
else:
    print("No")

Measured memory_bytes: 3060