akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
#include<time.h>
#include<stdlib.h>
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("sse4")
#define pb push_back
#define mp make_pair
#define IOS ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define ll long long
#define pll pair<ll,ll>
#define vll vector<ll,ll>
#define all(a) (a).begin(),(a).end()
#define ff first
#define ss second
#define sz(x) (ll)x.size()
#define hell 1000000007
#define repf(i,a,b) for(ll i=a;i<b;i++)
#define repb(i,a,b) for(ll i=a;i>b;i--)
#define lbnd lower_bound
#define ubnd upper_bound
#define bs binary_search
#define gcd(a,b) __gcd((a),(b))
#define EPS 1e-12
#define lcm(a,b) ((a)*(b))/__gcd((a),(b))
#define sqrt sqrtl
#define cbrt cbrtl
using namespace std;


int main()
{
  IOS
 ll a,p;
 cin>>a>>p;
 ll tot=a*3+p;
 cout<<tot/2;
  return 0;
}

Measured memory_bytes: 256
package main

import (
	"fmt"
)

func main() {
	var a, b, ans int
	fmt.Scan(&a, &b)
	
	if a >= 13 {
		ans = b
	} else if a >= 6 {
		ans = b/2
	} else {
		ans = 0
	}
	
	fmt.Println(ans)
}


Measured memory_bytes: 512
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (n); i++)
#define rep2(i, x, n) for (int i = x; i < (n); i++)
#define all(n) begin(n), end(n)
struct cww
{
    cww()
    {
        ios::sync_with_stdio(false);
        cin.tie(0);
    }
} star;
const long long INF = numeric_limits<long long>::max();
typedef long long ll;
typedef vector<int> vint;
typedef vector<char> vchar;
typedef vector<vector<int>> vvint;
typedef vector<ll> vll;
typedef vector<vector<ll>> vvll;
typedef unsigned long long ull;
template <class T>
bool chmax(T &a, const T &b)
{
    if (a < b)
    {
        a = b;
        return 1;
    }
    return 0;
}
template <class T>
bool chmin(T &a, const T &b)
{
    if (b < a)
    {
        a = b;
        return 1;
    }
    return 0;
}
string S;
int K, keta;

vector<vvint> memo(101, vvint(101, vint(2, -1)));

ll solve(int i, int num, bool smaller) //i桁目まで決めて、0でない数字がnum個あるようなやつ
{
    int x = S[i] - '0';
    if (i == keta)
    {
        memo[i][num][smaller] = num == 0;
        return num == 0;
    }
    if (memo[i][num][smaller] != -1)
    {
        return memo[i][num][smaller];
    }
    if (num == 0)
    {
        return memo[i][num][smaller] = 1;
    }

    if (smaller)
    {
        ll tmp = 0;
        tmp += solve(i + 1, num, true);
        tmp += solve(i + 1, num - 1, true) * 9;
        memo[i][num][true] = tmp;
        return tmp;
    }
    else
    {

        ll tmp = 0;
        if (x != 0)
            tmp += solve(i + 1, num, true);
        else
        {
            tmp += solve(i + 1, num, false);
            memo[i][num][false] = tmp;
            return tmp;
        }
        rep2(j, 1, x)
        {
            tmp += solve(i + 1, num - 1, true);
        }
        tmp += solve(i + 1, num - 1, false);
        memo[i][num][false] = tmp;
        return tmp;
    }
}

int main()
{

    cin >> S >> K;
    keta = S.size();
    cout << solve(0, K, false);
    return 0;
}

Measured memory_bytes: 896
import sys

sys.setrecursionlimit(10 ** 7)
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    s = set(input())
    for i in [chr(i) for i in range(97, 97 + 26)]:
        if i not in s:
            print(i)
            break
    else:
        print("None")


if __name__ == '__main__':
    resolve()


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

int main() {
    int n;
    cin >> n;
    string P, Q;
    for(int i=0; i<n; i++){
        string x;
        cin >> x;
        P+=x;
    }
    for(int i=0; i<n; i++){
        string x;
        cin >> x;
        Q+=x;
    }
    int cnt=1;
    vector<int> AR;
    for (int i = 1; i <= n; i++)
    {
        AR.push_back(i);
        cnt *= i;
    }
    
    vector<string> RETU;
    
    do
    {
        string num;
        for (int i = 0; i < n; i++)
        {
            string z = to_string(AR[i]);
            num+=z;
        }
        RETU.push_back(num);
    } while (next_permutation(AR.begin(), AR.end()));
    
    sort(RETU.begin(), RETU.end());

    int a=-1, b=-1;
    for (int i = 0; i < cnt; i++)
    {
        if(RETU[i]==P) a=i;
        if(RETU[i]==Q) b=i;
        if(a>=0 && b>=0) break;
        //cout << RETU[i] << endl;
    }
    cout << abs(a-b) << endl;
    return 0;
}



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

int main(){
  int n,m;
  cin >> n >> m;
  char a[n][m];
  for(int i=0;i<n;i++){
    for(int j=0;j<m;j++){
      cin >> a[i][j];
    }
  }
  char b[n+2][m+2];
  for(int i=0;i<n+2;i++){
    b[i][0]='#';
    b[i][m+1]='#';
  }
  for(int i=0;i<m+2;i++){
    b[0][i]='#';
    b[n+1][i]='#';
  }
  for(int i=1;i<n+1;i++){
    for(int j=1;j<m+1;j++){
      b[i][j]=a[i-1][j-1];
    }
  }
  for(int i=0;i<n+2;i++){
    for(int j=0;j<m+2;j++){
      cout << b[i][j];
    }
    cout << endl;
  }
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define u 1000000
#define  ll long long
using namespace std;
int main()
{
ll n,x,t,a,b;
cin>>n>>x>>t;
if(n%x==0)
{
    a=n/x;
    a=a*t;
}
else
{
    a=n/x+1;
    a=a*t;
}
cout<<a<<endl;





 return 0;
}


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

using namespace std;
using ll = long long;
using P = pair<int,int>;
const ll mod = 1000000007;


int ri() {
    int n;
    scanf("%d", &n);
    return n;
}

int n;
vector<vector<int>> hen;
vector<int> f, s; 

void bfs(int t, vector<int>& v){
	queue<int> que;
	vector<bool> seen(n);
	seen[t] = 1;
	que.push(t);
	while(que.size()){
		auto cur = que.front(); que.pop();
		for(auto i : hen[cur]){
			if(seen[i])continue;
			v[i] = v[cur] + 1;
			seen[i] = 1;
			que.push(i);
		}
	}
}

int main()
{
	n = ri();
	hen.resize(n);
	f.resize(n);
	s.resize(n);
	for(int i = 0; i < n - 1; i++){
		int a = ri(), b = ri(); a--; b--;
		hen[a].push_back(b);
		hen[b].push_back(a);
	}
	bfs(0, f);
	bfs(n - 1, s);
	int cnt = 0; //fennecが塗れる
	for(int i = 0; i < n; i++){
		//cerr << f[i] << " : " << s[i] << endl;
		if(f[i] <= s[i])cnt++;
	}
	//cerr << cnt << endl;

	cout << (cnt > n - cnt ? "Fennec" : "Snuke") << endl;
}

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

int main(){
  int n;
  cin >> n;
  int cnt = 0;
  for(int i = 0; i < n; i++){
    int a, b;
    cin >> a >> b;
    if(a == b) cnt++;
    else cnt = 0;
    if(cnt == 3){
      cout << "Yes" << endl;
      return 0;
    }
  }
  cout << "No" << endl;
  return 0;
}

Measured memory_bytes: 3544
def abc152c_low_elements():
    n = int(input())
    p = list(map(int, input().split()))
    cnt = 1
    min_val = p[0]
    for i in range(1, n):
        if min_val > p[i]:
            cnt += 1
            min_val = min(min_val, p[i])
    print(cnt)
abc152c_low_elements()

Measured memory_bytes: 32280
import scala.annotation.tailrec
import scala.collection.mutable
import scala.collection.mutable.ArrayBuffer
object Main extends App {
  import scala.io.StdIn._


  val n = readLong
  val prime = primes(1000000)
  val primeFactor = calPrimeFactor(n)
  if (primeFactor.length == 1 && primeFactor.head == 1){
    println(s"1 1")
  }else {
    val divisor = divisors(primeFactor)
    println(s"${primeFactor.length} $divisor")
  }

  def divisors(primeFactor: List[Int]): Long = {
    var r = 1L
    for (e ← primeFactor){
      r *= (e + 1)
    }
    r - 1
  }
  def calPrimeFactor(number: Long): List[Int] = {
    @tailrec
    def sub(n: Long, i: Int, rest: List[Int] = Nil): List[Int] ={
      if (n == 1) rest
      else if (i == prime.length) 1::rest
      else if (n % prime(i) != 0) sub(n, i + 1, rest)
      else {
        var c = 0
        var nn = n
        while(nn % prime(i) == 0){
          c += 1
          nn /= prime(i)
        }
        sub(nn, i + 1, c::rest)
      }
    }
    sub(number, 0)
  }
  def primes(upper: Int): Array[Int] = {
    val memo = Array.tabulate(upper + 1){_ ⇒ true}
    for (i ← 2 to math.sqrt(upper).toInt if memo(i)){
      for (j ← i * 2 to upper by i){
        memo(j) = false
      }
    }
    (2 to upper).filter(memo).toArray
  }
  implicit class Scope[T](val value: T) extends AnyVal {
    @inline
    def let[A](func: T ⇒ A): A = func(value)
    @inline
    def also(func: T ⇒ Unit): T = {
      func(value)
      value
    }
  }
}


Measured memory_bytes: 66928
n, m = list(map(int, input().split()))
a = []
for i in range(m):
    a.append(int(input()))
a = set(a)
dp = [0 for _ in range(n+1)]
dp[0] = 1
if 1 in a:
    dp[1] = 0
else:
    dp[1] = 1
for i in range(2, n+1):
    if not(i in a):
        dp[i] = dp[i - 2] + dp[i - 1]
print(dp[n] % 1000000007)


Measured memory_bytes: 460056
#include <stdio.h>
#include <iostream>

using namespace std;
#define max(a,b)(a<b?a:b)

int main(){

	int fi[100][2]={0};
	int fiPos=0;
 
	while(1){

	int n,m;
	int tr[100]={0};
	int hnk[100]={0};
	int trSum=0,hnkSum=0;

	cin >> n>>m;

	if(!n&&!m)
		break;

	for(int i=0;i<n+m;i++){
		if(i<n){
			cin >> tr[i];
			trSum+=tr[i];
		}
		else{
			cin >> hnk[i-n];
			hnkSum+=hnk[i-n];
		}
	}

	int max=1000;
	bool ANS=0;
	for(int i=0;i<n;i++){
		for(int j=0;j<m;j++){
			if(trSum==hnkSum+(tr[i]*2)-(hnk[j]*2)){
				int tMax=max;
				max=max(max,tr[i]+hnk[j]);
				if(max!=tMax){
					fi[fiPos][0]=tr[i];
					fi[fiPos][1]=hnk[j];
					ANS=true;
				}
			}
		}
	}

	if(ANS==0){
		fi[fiPos][0]=-1;
	}
		fiPos++;

}

	for(int i=0;i<fiPos;i++){
		if(fi[i][0]==-1)
			cout << -1<<endl;
		else
			cout << fi[i][0] << " " << fi[i][1]<<endl;
	}

	return 0;
}

Measured memory_bytes: 1164
#include<cstdio>
#include<vector>
#include<algorithm>
#include<utility>
#include<numeric>
#include<iostream>
#include<array>
#include<string>
#define _USE_MATH_DEFINES

#include<math.h>
#include<unordered_map>

#define min(a,b) (a)>(b)?(b):(a)
#define max(a,b) (a)>(b)?(a):(b)

using namespace std;

int a[200000];

int main()
{
	int p, l, h;
	int n;
	bool topFlag = false;
	
	cin >> n;
	for (int i = 0; i < n; i++)
	{
		cin >> a[i];
	}

	l = a[0];
	h = a[0];
	p = -1100000000;

	for (int i = 1; i < n; i++)
	{
		p = max(p, a[i] - a[i - 1]);
		if (a[i] >= a[i - 1])
		{
			if (!topFlag)
			{
				h = a[i];
			}
			h = max(h, a[i]);
			topFlag = true;
		}
		else
		{
			if (a[i] < l)
			{
				if (topFlag)
				{
					p = max((h - l), p);
					topFlag = false;
				}
				l = a[i];
			}
		}
	}
	if (topFlag)
	{
		p = max((h - l), p);
	}

	cout << p << endl;

	return 0;
}

Measured memory_bytes: 3872
n, m, x, y = map(int,input().split())
xList = list(map(int,input().split()))
yList = list(map(int,input().split()))

judge = sorted(xList,reverse=True)[0]+1

if judge <= sorted(yList)[0] and x < judge <= y:
  print("No War")
else:
  print("War")


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

int main() {
    // 入力
    int N, Q;
    cin >> N >> Q;
    vector<int> S(N), T(N), X(N);
    for (int i = 0; i < N; i++) {
        cin >> S.at(i) >> T.at(i) >> X.at(i);
    }
    vector<int> D(Q);
    for (int i = 0; i < Q; i++) {
        cin >> D.at(i);
        D[i] = D[i];
    }

    // イベント
    vector<tuple<int, int, int>> event;
    for (int i = 0; i < N; i++) {
        event.push_back(make_tuple(S[i] - X[i], 1, X[i]));   // 通行止め開始イベント
        event.push_back(make_tuple(T[i] - X[i], -1, X[i]));  // 通行止め終了イベント
    }
    sort(event.begin(), event.end());  // 時系列順に並べる

    set<int> se;  // 現在出発した人が当たる可能性のある通行止めの情報を保存する set

    vector<int> ans(Q);
    int t = 0;
    int id = 0;
    for (int i = 0; i < Q; i++) {
        t = D[i];
        for (; id < (int)event.size() && get<0>(event[id]) <= t; id++) {
            if (get<1>(event[id]) == 1) {
                se.insert(get<2>(event[id]));
            } else {
                se.erase(get<2>(event[id]));
            }
        }
        if (se.empty()) {
            ans[i] = -1;
        } else {
            ans[i] = *se.begin();
        }
    }

    for (int i = 0; i < Q; i++) {
        cout << ans[i] << endl;
    }

    return 0;
}


Measured memory_bytes: 19564
/* tempate
 *
 *
 */

#include <iostream>
#include <iomanip>
#include <cstdio>
#include <string>
#include <queue>
#include <deque>
#include <list>
#include <vector>
#include <utility>
#include <algorithm>
#include <map>
#include <set>
#include <complex>
#include <cmath>
#include <limits>
#include <cfloat>
#include <climits>
#include <ctime>
#include <cassert>
#include <numeric>
#include <fstream>
#include <functional>
#include <bitset>

using namespace std;


#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define repr(i,n) for(int (i)=(n); (i)>=(0); (i)--)
#define SIZE(x) ((int)(x).size())
#define GCD(a, b) int gcd(int a,int b){return b?gcd(b,a%b):a;}
#define QP(a, b) int qp(int a,ll b){int ans=1;do{if(b&1)ans=1ll*ans*a%mo;a=1ll*a*a%mo;}while(b>>=1);return ans;}
#define pb(a) push_back(a)
#define mp(a,b) make_pair(a,b)
#define all(v) (v).begin(),(v).end()


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 chadd(T &a, T b) {a = a + b;}
template<typename A, size_t N, typename T>
void FILL(A (&array)[N], const T &val){
    std::fill( (T*)array, (T*)(array+N), val );
}

typedef vector<int, int> vint;
typedef pair<int,int> pint;
typedef vector<pint>vpint;
typedef long long ll;

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


int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll n; cin >> n;
    vector<ll> p(n);
    ll count = 0;
    rep(i, n) cin >> p[i];
    rep(i, n){
        if(p[i] != i + 1) count++;
    }
    if(count <= 2) cout << "YES";
    else cout << "NO";
    cout << endl;
    return 0;
}


Measured memory_bytes: 888
#include <string>
#include <algorithm>
#include <vector> 
#include <math.h>
#include <iostream>
using namespace std;
long long mod = 1000000000 + 7;


int main()
{
	int x, y;
	cin >> x >> y;
	int ans = max(x + y, max(x + x - 1, y + y - 1));
	
	cout << ans << endl;
	return 0;

}

Measured memory_bytes: 256
#include<iostream>

#include<cstdio>

using namespace std;
int main(){

  int a,b,d,r;
  double f;
  cin >> a >> b;

  d=a/b;
  r=a%b;
  f=1.00000000*a/b;

  printf("%d %d %.8lf\n",d,r,f);
  return 0;

}

Measured memory_bytes: 3220
#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <queue>
#include <typeinfo>
#include <map>
#define INF 100000000
#define rep(i,a) for(int i=0;i<(a);i++)

using namespace std;
typedef long long ll;

double is(double x,double h){
    return x*x + 2*x * sqrt( h*h + (0.25)*x*x );
}


int main(){
    int x,h;
    while(1){
        cin>>x>>h;
        if(x==h && x==0)break;
        
        printf("%15.10lf\n",is(x,h));
    }
    return 0;
}

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

using namespace std;

int main() {
    long long int N, K, tmp;
    cin >> N >> K;

    tmp = (N % K);
    if (abs(tmp - K) > tmp) {
        cout << tmp;
    } else {
        cout << abs(tmp - K);
    }

    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <stack>
#include <queue>

using namespace std;

static const long long FAR = (1LL << 21);
static const int N = 100;

int n, m[N][N];
bool visited[N];
int d[N], p[N];

int prim(){
	for (int i = 0; i < n; ++i) {
		d[i] = FAR;
		p[i] = -1;
		visited[i] = false;
	}

	d[0] = 0;
	while (true)
	{
		int mi = FAR;
		int u = -1;
		for (int i = 0; i < n; ++i)	{
			if (!visited[i] && d[i] < mi){
				u = i;
				mi = d[i];
			}
		}

		if (-1 == u) break;
		visited[u] = true;

		for (int v = 0; v < n; ++v) {
			if (!visited[v] && m[u][v] < d[v]){
				p[v] = u;
				d[v] = m[u][v];
			}
		}
	}

	int res = 0;
	for (int i = 0; i < n; ++i) {
		if (p[i] != -1) res += m[i][p[i]];
	}
	return res;
}

int main()
{
	cin >> n;
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < n; ++j) {
			int e; cin >> e;
			m[i][j] = ((e == -1) ? FAR : e);
		}
	}

	cout << prim() << endl;

	return 0;
}

Measured memory_bytes: 3088
#include <algorithm>
#include <cstdio>
#include <iostream>
using namespace std;

long calc(long p, int d){
	int q[6], r[6];
	
	for(int i=0; i<d; ++i){
		q[d-i-1]=p%10;
		r[d-i-1]=p%10;	
		p /= 10;
	}
	sort(r, r+d, greater<int>());
	sort(q, q+d);
	
	long mx=0, mn=0, t=1;
	
	for(int i=d-1; i>=0; --i){
		mx += r[i]*t;
		mn += q[i]*t;
		t *= 10;
	}
	//printf("%ld - %ld", mx, mn);
	return mx-mn;
}

int main(){
	while(1){
		long a[1000];
		int digit;
		
		scanf(" %ld %d", &a[0], &digit);
		if(digit==0) break;
		
		int i=0, j=0;
		while(1){
			a[i+1]=calc(a[i], digit);
			++i;
			//printf("a[%d]=%ld\n", i, a[i]);
			
			bool ok=true;
			for(j=0; j<i; ++j){
				if(a[i] == a[j]){
					ok=false;
					break;
				}
			}
			if(!ok) break;
		}
		
		printf("%d %ld %d\n",j, a[i], i-j);
	}
	return 0;
}

Measured memory_bytes: 1216
//14
#include<iostream>
#include<algorithm>

using namespace std;

int main(){
  for(int n,m;cin>>n>>m;){
    int st[3][100000]={{}};
    while(n--){
      char nl[31];
      int c,s[3];
      cin.ignore().getline(nl,31);
      cin>>c>>s[0]>>s[1]>>s[2];
      for(int i=c;i<=m;i++){
	for(int j=0;j<3;j++){
	  st[j][i]=max(st[j][i],st[j][i-c]+s[j]);
	}
      }
    }
    cout<<max(st[0][m],max(st[1][m],st[2][m]))<<endl;
  }
  return 0;
}

Measured memory_bytes: 2336
#include <stdio.h>
int z[9999],r[9999];
int f(int a,int b){
	printf("? %d %d\n",a,b);
	fflush(0);
	char c[2];
	scanf("%s",c);
	return*c=='Y';
}
int main(){
	int a,b,c=0,h,i;
	scanf("%d%d",&a,&b);
	if(a<=b){puts("Impossible");return 0;}
	for(i=a+=b;~--i;)!c||f(i,z[c-1])?(z[c++]=i):c--;
	for(h=*z,i=a;~--i;)r[i]=f(h,i);
	for(printf("! "),i=0;i<a;)printf("%d",r[i++]);
	puts("");
}

Measured memory_bytes: 732
while True:
    H, W = map(int, input().split())
    if H == W == 0:
        break
     
    for i in range(H):
        if i % 2 == 0:
            if W % 2 != 0:
                print("#." * (W // 2) + "#")
                continue
            print("#." * (W // 2))
        else:
            if W % 2 != 0:
                print(".#" * (W // 2) + ".")
                continue
            print(".#" * (W // 2))
    print()

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

const long INF = 1 << 29;

int dp[100010];

int main(){
	int n;
	scanf("%d", &n);
	for(int i = 0; i <= n; i++)
		dp[i] = INF;
	dp[0] = 0;
	for(int i = 0; i < n; i++) {
		for(int j = 1; i + j <= n; j*=6)
			dp[i+j] = min(dp[i+j], dp[i] + 1);
		for(int j = 1; i + j <= n; j*=9)
			dp[i+j] = min(dp[i+j], dp[i] + 1);
	}
	printf("%d\n", dp[n]);
}


Measured memory_bytes: 640
#include<bits/stdc++.h>
#include<iostream>
#include<cstdio>
#include<vector>
#include<string>
#include<algorithm>
#include<map>
using namespace std;
#define rep(i,x) for(int i = 0; i < x; i++)
#define pb push_back
#define mp make_pair
typedef long long ll;
typedef long double ld;
typedef pair<int,int> P;
typedef pair<ll,ll> Pll;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef vector<vector<vector<int>>> vvvi;
const ll MOD = 1e9+7;
const int n_max = 1e5+10;

int main(){
    int n; cin >> n;
    vector<pair<pair<string, int>, int>> rest;
    rep(i,n){
        string s;cin >> s;
        int p; cin >> p;
        pair<pair<string, int>, int> temp = make_pair(make_pair(s,-p),i+1);
        rest.push_back(temp);
    }
    sort(rest.begin(), rest.end());
    for(auto i : rest)cout << i.second << endl;
    return 0;
}

Measured memory_bytes: 256
// abc170_c
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>

#if __cplusplus >= 201103L
#include <array>
#include <atomic>
#include <chrono>
#include <condition_variable>
#include <forward_list>
#include <future>
#include <initializer_list>
#include <mutex>
#include <random>
#include <ratio>
#include <regex>
#include <scoped_allocator>
#include <system_error>
#include <thread>
#include <tuple>
#include <type_traits>
#include <typeindex>
#include <unordered_map>
#include <unordered_set>
#endif

template <typename A, typename B> bool cmin(A &a, const B &b) {
  return a > b ? (a = b, true) : false;
}
template <typename A, typename B> bool cmax(A &a, const B &b) {
  return a < b ? (a = b, true) : false;
}
const double PI = acos(-1);
const double EPS = 1e-9;
int inf = sizeof(int) == sizeof(long long) ? 2e18 : 1e9 + 10;
int dx[] = {0, 1, 0, -1};
int dy[] = {1, 0, -1, 0};
#define rep(i, n) for (int i = 0; i < (n); ++i)
using namespace std;
using ll = long long;
using P = pair<int, int>;

int main() {
  int x, n;
  cin >> x >> n;
  if (n == 0) {
    cout << x << endl;
    return 0;
  }

  vector<int> p(n);
  rep(i, n) cin >> p[i];

  int ans = x, minum = inf;

  for (int i = -100; i <= 200; ++i) {
    auto res = find(p.begin(), p.end(), i);
    int now = abs(x - i);
    if (res == p.end() && now < minum) {
      minum = now;
      ans = i;
    }
  }
  cout << ans << endl;
  return 0;
}


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

int main() {
  int N;
  cin >> N;
  
  int l, r;
  int x = 0;
  
  for (int i = 0; i < N; i++) {
    cin >> l >> r;
    x += r - l + 1;
  }
  
  cout << x << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for (auto i=(a); i<(b); ++i)
#define iter(it,c) for (auto it = (c).begin(); it != (c).end(); ++it)
typedef pair<int, int> ii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<vi> vvi;
typedef long long ll;
const int INF = 2147483647;

int mod = 1000000007;

int broken[101000],
    mem[101000];

int n;
int dp(int at) {
    if (broken[at] || at > n) {
        return 0;
    }
    if (at == n) {
        return 1;
    }
    if (mem[at] != -1) {
        return mem[at];
    }

    int res = dp(at+1) + dp(at+2);
    if (res >= mod) res -= mod;
    return mem[at] = res;
}

int main() {
    memset(mem,-1,sizeof(mem));

    int m;
    scanf("%d %d", &n, &m);
    rep(i,0,m) {
        int x;
        scanf("%d", &x);
        broken[x] = true;
    }

    printf("%d\n", dp(0));

    return 0;
}



Measured memory_bytes: 4096
#include<bits/stdc++.h>
using namespace std;
#define fastio ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define start_routine() int begtime = clock();
#define end_routine() int endtime = clock(); \
                      cerr << "\n\n" << "Time elapsed: " << \
                      (endtime - begtime)*1000/CLOCKS_PER_SEC << " ms\n\n"; \
                      return 0
#define ll long long int
#define ull unsigned long long int
#define db long double
#define ff first
#define ss second
#define mp make_pair
#define pb push_back
#define lb lower_bound
#define ub upper_bound 
#define pii pair<int , int>
#define pdd pair<db , db>
#define pll pair<ll , ll>
#define vpl vector<pll >
#define vll vector<ll >
#define mod 1000000007
#define mod1 998244353 
#define inf 1000000000000000007
#define eps 0.000001
#define stp fixed<<setprecision(20)
#define endl '\n'



int main()
{
    fastio;
    #ifdef APNA_IO
        start_routine();
        freopen("input.txt", "rt", stdin);
        freopen("output.txt", "wt", stdout);    
    #endif

    ll n;cin>>n;
    ll p[n+1];

    for(ll i=1;i<=n;i++)
        cin>>p[i];

    bool ch=1;
    for(ll i=1;i<=n;i++)
    {
        for(ll j=i;j<=n;j++)
        {
            swap(p[i],p[j]);
            ch=1;
            for(ll k=1;k<=n;k++)
                if(p[k]!=k)
                    ch=0;
            if(ch) return cout<<"YES",0;
            swap(p[i],p[j]);
        }
    }
    cout<<"NO";





    #ifdef APNA_IO
        end_routine();
    #endif
}


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

using namespace std;

int lcs(string s1, string s2) {
    int c[1005][1005];
    int m = s1.length();
    int n = s2.length();
    s1 = " " + s1;
    s2 = " " + s2;
    int max1 = 0;
    for (int i = 0; i <= m; i++) {
        c[i][0] = 0;
    }
    for (int i = 0; i <= n; i++) {
        c[0][i] = 0;
    }
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (s1[i] == s2[j]) {
                c[i][j] = c[i - 1][j - 1] + 1;
            } else {
                c[i][j] = max(c[i - 1][j], c[i][j - 1]);
            }
            max1 = max(max1, c[i][j]);
        }
    }
    return max1;
}

int main() {
    int q;
    cin >> q;
    string s1, s2;
    for (int k = 0; k < q; k++) {
        cin >> s1;
        cin >> s2;
        cout << lcs(s1, s2) << endl;
    }

    return 0;
}

Measured memory_bytes: 7124
#include <iostream>
#include <string>
int main(){
  std::string s;
  int a=0;
  std::cin>>s;
  for(int i=0;i<s.size()/2;++i){
    if(s[i]!=s[s.size()-i-1])++a;
  }
  std::cout<<a<<"\n";
}

Measured memory_bytes: 256
//#include"stdc++.h"
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define fast  ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define cases ll t;cin>>t;while(t--)
#define f1(a,n) for(int i=a;i<n;i++)
#define f2(b,n) for(int j=b;j<n;j++)
#define INF 1000000000000009
#define pb push_back
ll ar[100005];
#define MAX 1000005
int main() {
    fast
    ll n,k;
    cin>>n>>k;
    ll ar[n];
    f1(0,n)
        cin>>ar[i];
    ll dp[n];
    dp[0]=0;
    f1(1,n)
    {
        dp[i]=INT_MAX;
        f2(i-k,i)
        {
            if(j>=0)
                dp[i]=min(dp[i],dp[j]+llabs(ar[i]-ar[j]));
        }
    }
    cout<<dp[n-1]<<endl;
    return 0;
}



Measured memory_bytes: 1792
import java.util.Scanner;

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

		// [house] [floor] [room]
		int[][][] bldgs = new int[4][3][10];

		for (int b, f, r, v, i = 0; i < n; i++) {
			b = sc.nextInt() - 1;
			f = sc.nextInt() - 1;
			r = sc.nextInt() - 1;
			v = sc.nextInt();
			bldgs[b][f][r] += v;
		}

		sc.close();

		StringBuilder sb = new StringBuilder();
		boolean flag = true;;
		
		for (int[][] f : bldgs) {
			if (flag) flag = false;
			else sb.append("####################\n");
			
			for (int[] r : f) {
				for (int v : r) {
					sb.append(" ").append(v);
				}
				sb.append("\n");
			}
		}
		System.out.print(sb);
	}
}

Measured memory_bytes: 29532
#![allow(non_snake_case,unused_imports,dead_code)]
use std::io::Read;
use std::cmp::max;
use std::cmp::min;
use std::str::FromStr;
use std::collections::HashMap;
use std::collections::HashSet;
use std::collections::BinaryHeap;

fn main() {

    let mut buf = String::new();
    std::io::stdin().read_to_string(&mut buf).unwrap();
    let mut buf_it = buf.split_whitespace();

    let N = buf_it.next().unwrap().parse::<usize>().unwrap();
    let Q = buf_it.next().unwrap().parse::<usize>().unwrap();
    let STX = (0..N).map(|_| 
        (buf_it.next().unwrap().parse::<isize>().unwrap(),
         buf_it.next().unwrap().parse::<isize>().unwrap(),
         buf_it.next().unwrap().parse::<isize>().unwrap()
    )).collect::<Vec<_>>();
    let D = (0..Q).map(|_| buf_it.next().unwrap().parse::<isize>().unwrap()).collect::<Vec<_>>();

    let mut C = HashSet::new();
    for &d in &D{
        C.insert(-d);
    }
    for &(s,t,x) in &STX{
        C.insert(x-s+1);
        C.insert(x-t+1);
    }
    let mut C = C.iter().map(|&c| c).collect::<Vec<_>>();
    C.sort();
    let mut C2 = HashMap::new();
    for (i,&c) in C.iter().enumerate(){
        C2.insert(c,i);
    }

    let INF = 1_000_000_100;
    let mut T = SegmentTree::new(4*N,min,INF);
    for &(s,t,x) in &STX{
        T.set(*C2.get(&(x-t+1)).unwrap(),*C2.get(&(x-s+1)).unwrap(),x)
    }
    for &d in &D{
        let d = *C2.get(&(-d)).unwrap();
        let mut ans = T.get(d);
        if ans == INF {ans = -1;}
        println!("{}",ans);
    }


}

struct SegmentTree<N,F>
where F:Fn(N,N) ->N{
//モノイドが乗るセグ木(区間更新一点取得)
    n: usize,
    T: Vec<N>,
    func: F,
    identity: N,
}

impl<N:Copy,F> SegmentTree<N,F>
where F:Fn(N,N) ->N {
    fn new(n:usize,func:F,identity:N) -> SegmentTree<N,F>{
        let mut T = SegmentTree { n:n,T:Vec::new(),func:func,identity:identity};
        T.init();
        T
    }
    fn init(&mut self){
        self.n = 1<<format!("{:b}",self.n-1).len();
        self.T = (0..(2*self.n-1)).map(|_| self.identity).collect();
    }
    fn get(&mut self,index:usize) -> N{
        let i = index + self.n - 1;
        self._get(i)
    }
    fn _get(&mut self,i:usize) -> N{
        let n = self.T[i];
        if i==0{return n;}
        let m = self._get((i-1)/2);
        (self.func)(n,m)
    }
    fn set(&mut self,l:usize,r:usize,value:N){
        let n = self.n;
        self._set(l,r,value,0,0,n);
    }
    fn _set(&mut self,l:usize,r:usize,value:N,i:usize,a:usize,b:usize){
        if l==a && b==r{
            let v = self.T[i];
            let v = (self.func)(v,value);
            self.T[i] = v;
            return;
        }
        let j = (a+b)/2;
        if l<j{
            self._set(l,min(r,j),value,2*i+1,a,j);
        }
        if j<r{
            self._set(max(l,j),r,value,2*i+2,j,b);
        }
    }
}

Measured memory_bytes: 85704
k,n = [int(x) for x in input().split()]
a = [int(x) for x in input().split()]
b = []
for i in range(0,n):
  if i < n-1:
    b.append(a[i+1]-a[i])
  else:
    b.append(k + a[0] - a[n-1])

print(k - max(b))

Measured memory_bytes: 24908
#include <bits/stdc++.h>
#include <boost/range/irange.hpp>

using namespace std;
using namespace boost;

main() {
    int64_t n, p;

    cin >> n >> p;

    if (n == 1) {
        cout << p << endl;
        return 0;
    }

    int64_t ans = 1;
    for (int64_t x = pow(p, 1.0/n) + 1; x >= 1; --x) {
        if (p % (int64_t)(pow(x, n) + 0.5) == 0) {
            cout << x << endl;
            break;
        }
    }
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;

int n,m,x;

bool ok(vector<int> a){
    int p = a.size();
    bool ng = false;
    for(int i=0;i<p;i++){
        if(a[i]<x){
            return false;
        }
    }
    return true;
}

int main(){
    
    cin >> n >> m >> x;
    vector<int> c(n);
    vector<vector<int>> a(n,vector<int>(m));
    for(int i=0;i<n;i++){
        cin >> c[i];
        for(int j=0;j<m;j++){
            cin >> a[i][j];
        }
    }
    for(int i=0;i<m;i++){
        int sum = 0;
        for(int j=0;j<n;j++){
            sum += a[j][i];
        }
        if(sum < x){
            cout << "-1" << endl;
            return 0;
        }
    }
    int ans = 100000100;
    int x = 0;
    
    for (int bit = 0; bit < (1<<n); ++bit) {
        int cnt = 0;
        x++;
        vector<int> s1(m,0);
        bitset<12> s(bit);
        //cout << s << endl;
        for(int i=0;i<n;i++){
            if(s[i]){
                for(int j=0;j<m;j++){
                    s1[j] += a[i][j];                   
                }
                cnt += c[i];
            }          
        }
        if(ok(s1)) {ans = min(ans,cnt);}

    }
    cout << ans << endl;
}

Measured memory_bytes: 3640
from itertools import product
s = input()
l = len(s)
ans = 0
for pattern in product(range(2), repeat=l-1):
  #print(pattern)
  tempsum = 0
  temp = [s[0]]
  for i in range(l-1):
    if pattern[i] == 0:
      temp.append(s[i+1])
    else:
      tempsum+=int("".join(temp))
      temp = [s[i+1]]
  tempsum+=int("".join(temp))
  #print(tempsum)
  ans+=tempsum
print(ans)
      

Measured memory_bytes: 9192
#include <iostream>
#include <cstdio>
#include <string>
#include <cmath>
#include <cctype>
#include <cstdlib>
#include <stack>
#include <queue>
#include <vector>
#include <algorithm>
#include <list>
using namespace std;

int main() {
    int d, n;
    cin >> d >> n;
    int m;
    if (d == 0) m = 1;
    else if (d == 1) m = 100;
    else m = 10000;
    if (n == 100) cout << 101 * m << endl;
    else cout << n * m << endl;
}


Measured memory_bytes: 256
N, A, B, *H = map(int, open(0).read().split())

def is_ok(K):
    return sum(max(0, -(-(h - B * K) // (A - B))) for h in H) <= K

ng, ok = 0, 10 ** 9
while abs(ok - ng) > 1:
    mid = (ok + ng) // 2
    if is_ok(mid):
        ok = mid
    else:
        ng = mid

print(ok)

Measured memory_bytes: 14092
import java.util.*;

public class Main{
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int ans = 0;
        for(int i = 1;i<=n;i++){
            if(String.valueOf(i).length() % 2 == 1){
                ans += 1;
            }
        }
        System.out.println(ans);
    }
}

Measured memory_bytes: 28372
#define _GLIBCXX_DEBUG
typedef long long ll;
#include <bits/stdc++.h>

using namespace std;

ll mod = 1000000007;

template<class Type> inline bool chmax(Type& a, Type b) { if (a < b) { a = b; return 1; } return 0; }
template<class Type> inline bool chmin(Type& a, Type b) { if (a > b) { a = b; return 1; } return 0; }

template<class Type>
Type modpow(Type a, Type n, Type mod)
{
	Type res = 1;
	while (0 < n)
	{
		if (n & 1)
		{
			res = res * a % mod;
		}
		a = a * a % mod;
		n >>= 1;
	}
	return res;
}

template<class Type>
Type gcd(Type x, Type y)
{
	Type r;
	if (x < y)
	{
		swap(x, y);
	}

	while (0 < y)
	{
		r = x % y;
		x = y;
		y = r;
	}
	return x;
}

template<class Type>
bool isPrime(Type x)
{
	if (x == 2) return true;
	if (x < 2 || x % 2 == 0) return false;

	for (Type i = 3; i <= sqrt(x); i += 2)
	{
		if (x % i == 0) return false;
	}
	return true;
}

template<class Type>
vector<bool> eratos(Type n)
{
	vector<bool> isPrime(n + 1, true);
	isPrime[0] = isPrime[1] = false;
	for (Type i = 2; i <= n; i++)
	{
		if (isPrime[i])
		{
			Type j = i + i;
			while (j <= n)
			{
				isPrime[j] = false;
				j = j + i;
			}
		}
	}
	return isPrime;
}

bool binarySearchJudge(vector<int> a, int index, int key)
{
	if (key <= a[index]) return true;
	else return false;
}

int binarySearch(vector<int> a, int key)
{
	int ng = -1;
	int ok = a.size();
	while (1 < abs(ng - ok))
	{
		int mid = (ng + ok) / 2;
		if (binarySearchJudge(a, mid, key)) ok = mid;
		else ng = mid;
	}
	return a[ok] == key;
}

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

	vector<int> dp(n,INT_MAX);
	dp[0] = 0;
	for (int i = 1; i < n; i++)
	{
		if (1 < i)
		{
			dp[i] = min(dp[i], dp[i - 2] + abs(h[i] - h[i - 2]));
		}
		dp[i] = min(dp[i], dp[i - 1] + abs(h[i] - h[i - 1]));
	}
	cout << dp[n - 1] << endl;
}

Measured memory_bytes: 1024
/*
Author: Fuadul Hasan(fuadul202@gmail.com)
BSMRSTU,Gopalganj
*/
#include<bits/stdc++.h>
using namespace std;
void    		print(int n)    {printf("%d ", n);}
void    		printl(long long n)     {printf("%I64d ", n);}
long long    	readline(){long long x;scanf("%I64d", &x);return x;}
/*
1.#define  gcd(a,b) __gcd(a,b) 2. #define  lcm(a,b) (a*b)/gcd(a,b) 3. #define  PI acos(-1.0) 4.#define  sqr(x) ((x)*(x))
5.#define  min3(a,b,c) min(a,min(b,c))6.#define  min4(a,b,c,d) min(d,min(a,min(b,c)))7.#define  max3(a,b,c) max(a,max(b,c))
8.#define  max4(a,b,c,d) max(d,max(a,max(b,c)))
*/
//.............ignore it................//
/*....... scanf.......*/
template <typename T> inline void readline(T &n) {
  n = 0; int f = 1; register int ch = getchar();
  for (; !isdigit(ch); ch = getchar()) if (ch == '-') f = -1;
  for (; isdigit(ch); ch = getchar()) n = (n << 3) + (n << 1) + ch - '0';n = n * f;}
template <typename T, typename TT> inline void readline(T &n, TT &m) { readline(n); readline(m); }
template <typename T, typename TT, typename TTT> inline void readline(T &n, TT &m, TTT &l) { readline(n, m); readline(l);}
/*..........error........*/
#define error(args...) {vector<string>_v=split(#args,',');err(_v.begin(),args);cout<<endl;}
vector<string> split(const string &s, char c) {
  vector<string>v; stringstream ss(s); string x;
  while (getline(ss, x, c))v.emplace_back(x); return move(v);
} void err(vector<string>::iterator it) {}
template<typename T, typename... Args>void err(vector<string>::iterator it, T a, Args...args) {
cout << it->substr((*it)[0] == ' ', it->length()) << " = " << a << " "; err(++it, args...);}
//............ignore it..................//
typedef   pair<int, int> ii;
typedef   std::vector<ii> vii;
#define   vi   std::vector<int>
#define   vll  std::vector<ll>
#define   all(n) n.begin(),n.end()
#define  mpsi std::map<string, int>
#define  pb             push_back
#define  ll             long long int
#define  nl             printf("\n");
#define  happy          cin.tie(0);
#define  coding         ios::sync_with_stdio(false);

#define  max3(a,b,c) max(a,max(b,c))


int dx[8]= {1,0,-1,0,-1,-1,1,1};
int dy[8]= {0,1,0,-1,-1,1,-1,1};
const int mod           = 1e9 + 7;
const int inf           = (int)2e9 + 5;
const ll  Inf           = (ll)2e18 + 5;
const int N             = 4e5 + 5;
const int N1            = 1e5 + 5;


 
int solve() 
{
	//happy coding
	int n;
	cin>>n;
	int a[32]= {1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51};

	cout<<a[n-1]<<endl;
	
	return 0;

	//error();
}

int main(){
	
	int test = 1, tc = 0;
	//scanf("%d", &test);//(void)getchar();
	while (test--){
		solve();
	}


	return 0;
}

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

int main(){
	int n;
  	cin >> n;
  vector<int> dp(n+4,0);
  vector<int> stones(n);
  for(int i= 0; i<n; i++)
  {
    cin >> stones[i];
  }
  dp[0]=0;
  dp[1] = abs(stones[0]-stones[1]);
  for(int i = 2; i<n;i++)
  {
    dp[i]=min(dp[i-1]+abs(stones[i]-stones[i-1]),dp[i-2]+abs(stones[i]-stones[i-2]));
  }
  cout << dp[n-1]<<endl;
}

Measured memory_bytes: 1024
/********************************
*** ******** ********** *********
*** * ****** ********* * ********
*** ** ***** ******** *** *******
*** *** **** ******* ***** ******
*** **** *** ****** ******* *****
*** ***** ** ***** +++++++++ ****
*** ****** * **** *********** ***
*** *******  *** ************* **
*** ******** ** *************** *
**********_**********************
* |   /  / \  \     /    /\     *
* |  /  |   |  \   /    /  \    *
* | /   |   |   \ /    /    \   *
* |+\   |   |    |    /______\  *
* |  \  |   |    |   |        | *
* |   \  \_/     |   |        | *
********************************/
#include<bits/stdc++.h>
#define lli long long int
#define MOD 1000000007
#define KING 1000000002
#define queen 1000002
#define fi first
#define se second
#define se second
#define lsb(i) (i & -i)
#define nl cout<<'\n'
#define TEST cout<<"TEST",nl
#define pr pair<lli,lli>
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define vi vector<lli>
#define vpi vector<pr> 
#define P pair<lli,pr>
#define fastIO ios_base::sync_with_stdio(false); cin.tie(NULL)
#define NA(i,s,n) for(lli i=s;i<n;i++)
using namespace std;



void solve(){
    lli a,b,c,k; cin>>a>>b>>c>>k;
    lli sm  =0;
    sm += min(a,k); k-=min(a,k);
    k-=min(b,k);
    sm -= min(c,k); k-=min(c,k);
    cout<<sm;
    return ;
}
int main(){
    fastIO;
    lli t = 1; 
    // cin>>t;
    NA(i,0,t) solve();
    return 0;
}

Measured memory_bytes: 3640
#include <iostream>
#include<string>
#include<vector>
#include<algorithm>

#define REP(i, n) for(ll i = 0; i < n; i++)
#define REPR(i, n) for(ll i = n; i >= 0; i--)
#define FOR(i, m, n) for(ll i = m; i < n; i++)
#define INF 2e9
#define ALL(v) v.begin(), v.end()
#define  DESC std::greater<int>() //sort 3rd arg

using namespace std;
typedef long long ll;

using namespace std;

int count(string t) {
	int counter = 0;

	for (int i = 0; i < t.size() - 1; i++) {
		if (t[i] == 'P' && t[i + 1] == 'D') {
			counter++;
		}
	}

	for (char c : t) {
		if (c == 'D') {
			counter++;
		}
	}

	return counter;
}

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

	string t2 = t;

	ll q_count = 0;
	

	if (t.size() == 1) {
		cout << 'D' << endl;
		return 0;

	}

	for(char c : t) {
		if (c=='?') {
			q_count++;
		}
	}

	if (q_count==t.size()) {
		bool flag = true;
		REP(i, t.size()){
			if (flag) {
				cout << 'P';
				flag = false;
			}else {
				cout << 'D';
				flag = true;
			}
		}
		return 0;
	}


	for (ll i = 0; i < t.size(); i++) {
		if (t[i] == '?') {
			if (i + 1 < t.size() && t[i + 1] == 'D') {
				t[i] = 'P';
			}
			else if (i>0 && t[i - 1] == 'P') {
				t[i] = 'D';
			}
			/*
			else if (i + 1 < t.size()&& t[i+1] == '?') {
				t[i] = 'P';
			}
			else if (i > 0 && t[i - 1] == 'D') {
				if (i == t.size() - 1)
					t[i] = 'D';
			}
			*/
			else {
				t[i] = 'D';
			}

		}
	}

	//cout << t << endl;

	
	int my_algo_score = count(t);

	for (int i = 0; i < t2.size();i++) {
		if (t2[i] == '?') {
			t2[i] = 'D';
		}
	}

	int all_D_score = count(t2);

	if (my_algo_score > all_D_score) {
		cout << t << endl;
		//return 0;
	}
	else {
		cout << t2 << endl;
		//return 0;
	}
	
	
	return 0;
}



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

using namespace std;
//using namespace __gnu_pbds;

const int N = 2005;
const int MOD = 1e9 + 7;
const int64_t INF = 5e18;
const double PI = 2 * acos(0.0);
//template<typename T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

int64_t s, dp[N];

int64_t fun(int cnt, int sum) {
//    cout << sum << '\n';
    if (sum > s) {
        return 0;
    }
    if (sum == s) {
        return 1;
    }
    int64_t &tmp = dp[sum];
    if (tmp != -1) {
        return tmp;
    }
    tmp = 0;
    for (int i = 3; i <= s; i++) {
//        cout << " -- " << i << '\n';
        int64_t x = fun(cnt + 1, sum + i);
        tmp += x;
        tmp %= MOD;
    }
    return tmp;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> s;
    memset(dp, -1, sizeof dp);
    cout << fun(0, 0) << '\n';
    return 0;
}


Measured memory_bytes: 3676
#include<bits/stdc++.h>
using namespace std;
int n,m,k,r,c,v,a[3005][3005];
long long ans,dp[3005][3005][5];
int main()
{
	cin>>n>>m>>k;
	for(int i=1;i<=k;i++)
	{
		cin>>r>>c>>v;
		a[r][c]=v;
	}
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
		{
			dp[i][j][0]=dp[i][j-1][0];
			for(int k=0;k<=3;k++)
			{
				dp[i][j][0]=max(dp[i][j][0],dp[i-1][j][k]);
				dp[i][j][1]=max(dp[i][j][1],dp[i-1][j][k]+(long long)a[i][j]);
			}
			for(int k=1;k<=3;k++)
				dp[i][j][k]=max(max(dp[i][j][k],dp[i][j-1][k]),dp[i][j-1][k-1]+(long long)a[i][j]);
		}
	for(int i=0;i<=3;i++)
		ans=max(ans,dp[n][m][i]);
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 390768
#include <bits/stdc++.h>
#define speed                   \
  ios_base::sync_with_stdio(0); \
  cin.tie(0);                   \
  cout.tie(0);
#define oprecision    \
  cout.precision(30); \
  cerr.precision(7);
#define ll long long
#define ld long double
#define ss string
#define pii pair<int, int>
#define pll pair<ll, ll>
#define forn(n) for (int i = 1; i <= n; i++)
#define forlr(l, r) \
  for (int i = l; (l > r ? i >= r : i <= r); (l > r ? i-- : i++))
#define pb push_back
#define pc __builtin_popcount
#define pcll __builtin_popcountll
#define mp make_pair
#define mt make_tuple
#define F first
#define S second
using namespace std;
ll n;
ll p(ll x) { return x * x * x * x * x; }
int main() {
  speed;
  oprecision;
  // code
  cin >> n;
  for (ll i = -200; i <= 200; i++) {
    for (ll j = -200; j <= 200; j++) {
      if ((p(i) - p(j)) == n) {
        cout << i << " " << j << "\n";
        return 0;
      }
    }
  }
  // endl
#ifndef ONLINE_JUDGE
  cerr << "\nTime elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
#endif
  return 0;
}

Measured memory_bytes: 3644
from heapq import heappush, heappop, heapify
from collections import deque, defaultdict, Counter
import itertools
from itertools import permutations, combinations, accumulate
import sys
import bisect
import string
import math
import time


def I(): return int(input())


def S(): return input()


def MI(): return map(int, input().split())


def MS(): return map(str, input().split())


def LI(): return [int(i) for i in input().split()]


def LI_(): return [int(i)-1 for i in input().split()]


def StoI(): return [ord(i)-97 for i in input()]


def ItoS(nn): return chr(nn+97)


def input(): return sys.stdin.readline().rstrip()


def show(*inp, end='\n'):
    if show_flg:
        print(*inp, end=end)


YNL = {False: 'No', True: 'Yes'}
YNU = {False: 'NO', True: 'YES'}
MOD = 10**9+7
inf = float('inf')
IINF = 10**10
l_alp = string.ascii_lowercase
u_alp = string.ascii_uppercase
ts = time.time()
sys.setrecursionlimit(10**6)
nums = ['1', '2', '3', '4', '5', '6', '7', '8', '9', '10']

show_flg = False
# show_flg = True


def main():
    H, W = MI()
    alpha = [0] * len(l_alp)

    for i in range(H):
        s = S()
        for j in range(W):
            alpha[ord(s[j])-97] += 1

    for i in range((H+1)//2):
        for j in range((W+1)//2):
            V = 4
            if H % 2 != 0 and i == (H+1)//2-1:
                V //= 2
            if W % 2 != 0 and j == (W+1)//2-1:
                V //= 2
            f = False

            if V == 2:
                for k in range(len(alpha)):
                    if alpha[k] % 2 == 0 and alpha[k] % 4 == 2:
                        f = True
                        alpha[k] -= V
                        break

            if not f:
                for k in range(len(alpha)):
                    if alpha[k] >= V:
                        f = True
                        alpha[k] -= V
                        break
            # print(i+1, j+1, V, alpha)
            if not f:
                print('No')
                return
    # print(alpha)
    print('Yes')

if __name__ == '__main__':
    main()


Measured memory_bytes: 39660
n = gets.chomp.to_i
hash = {}
no = {}
n.times do |i|
	ngo = gets.chomp.split 
	no[ngo[0]+"_"+ngo[1]] = i + 1
	if hash.has_key?(ngo[0])
		hash[ngo[0]] << ngo[1].to_i
	else
		hash[ngo[0]] = [ngo[1].to_i]
	end
end

#p no

arr = hash.to_a.sort{|a, b| a[0] <=> b[0]}
arr.each do |a|
	a[1] = a[1].sort.reverse
	a[1].each do |aa|
		puts no[a[0]+"_"+aa.to_s]
	end
end

Measured memory_bytes: 14308
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<utility>
#include<queue>
using namespace std;
int MAX = 9999999;
int mod = 10007;
//---------------------------------------------------------------------------
int n;
string s;
int sch[1009];//joi 012
int dp[1009][9];// joi 001 010 011 100 101 110 111

int so(int d, int typ) {
	if (dp[d][typ] != -1)return dp[d][typ];
	if (d == n) {
		if (sch[d] == 0) {
			if (typ == 6 || typ == 5 || typ == 4 || typ == 3)return 1;
		}
		else if (sch[d] == 1) {
			if (typ == 6 || typ == 5 || typ == 2 || typ == 1)return 1;
		}
		else {
			if (typ == 6 || typ == 4 || typ == 2 || typ == 0)return 1;
		}
	}
	if (typ == 0 && sch[d] == 2) {//6420
		dp[d][typ] = so(d + 1, 6) + so(d + 1, 4);
		dp[d][typ] += so(d + 1, 2) + so(d + 1, 0);
	}
	else if (typ == 1 && sch[d] == 1) {//6521
		dp[d][typ] = so(d + 1, 6) + so(d + 1, 5);
		dp[d][typ] += so(d + 1, 2) + so(d + 1, 1);
	}
	else if (typ == 2 && sch[d] != 0) {//012456
		dp[d][typ] = so(d + 1, 6) + so(d + 1, 5) + so(d + 1, 4);
		dp[d][typ] += so(d + 1, 2) + so(d + 1, 1) + so(d + 1, 0);
	}
	else if (typ == 3 && sch[d] == 0) {//6543
		dp[d][typ] = so(d + 1, 6) + so(d + 1, 5);
		dp[d][typ] += so(d + 1, 4) + so(d + 1, 3);
	}
	else if (typ == 4 && sch[d] != 1) {//023456
		dp[d][typ] = so(d + 1, 6) + so(d + 1, 5) + so(d + 1, 4);
		dp[d][typ] += so(d + 1, 2) + so(d + 1, 3) + so(d + 1, 0);
	}
	else if (typ == 5 && sch[d] != 2) {//123456
		dp[d][typ] = so(d + 1, 6) + so(d + 1, 5) + so(d + 1, 4);
		dp[d][typ] += so(d + 1, 2) + so(d + 1, 1) + so(d + 1, 3);
	}
	else if (typ == 6) {
		dp[d][typ] = so(d + 1, 6) + so(d + 1, 5) + so(d + 1, 4);
		dp[d][typ] += so(d + 1, 3) + so(d + 1, 2);
		dp[d][typ] += so(d + 1, 1) + so(d + 1, 0);
	}
	else dp[d][typ] = 0;
	dp[d][typ] %= mod;
	return dp[d][typ];

}

int main() {
	cin >> n >> s;
	for (int i = 1; i <= n; i++) {
		if (s[i - 1] == 'J')sch[i] = 0;
		if (s[i - 1] == 'O')sch[i] = 1;
		if (s[i - 1] == 'I')sch[i] = 2;
		for (int j = 0; j < 7; j++) {
			dp[i][j] = -1;
		}
	}
	dp[0][3] = -1; sch[0] = 0;

	cout << so(0, 3) % mod << endl;

	return 0;
}



Measured memory_bytes: 3220
def div(x, y):
    if x % y == 0:
        return x // y
    else:
        return x // y + 1


n = int(input())
p = 1
q = 1
for _ in range(n):
    t, a = map(int, input().split())
    n = max(div(p, t), div(q, a))
    p = n * t
    q = n * a

print(p + q)

Measured memory_bytes: 3060