akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <algorithm>
#include <string>
using namespace std;


int main()
{
    int n;
    string s;
    cin >> n >> s;
    if (n % 2 != 0)
    {
        cout << "No" << endl;
        return(0);
    }
    for (int i = 0; i < n/2 ; i++)
    {
        if(s[i] != s[i + n/2])
        {
            cout << "No" << endl;
            return(0);
        }
    }
    cout << "Yes" << endl;

}

Measured memory_bytes: 256
//Name: A-B Problem
//Level: 2
//Category: 動的計画法,DP
//Note:

/**
 * dp[n][k][b] = n桁目以降で、あとk回まで繰り下がりを忘れていい時に作れる最大値（ただしn桁目におけるborrowの値はb）
 * として、メモ化再帰の形で書く。
 *
 * オーダーは O(K log A)。
 */
#include <iostream>
#include <string>
#include <array>
#include <algorithm>

using namespace std;

template <typename T>
struct Maybe {/*{{{*/
    T val;
    bool valid;

    Maybe() : valid(false) {}
    Maybe(T &t) : val(t), valid(true) {}

    T& operator =(const T &rv) {
        val = rv;
        valid = true;
        return val;
    }
};/*}}}*/

string A, B;
array<array<array<Maybe<int>,2>,10>,10> memo;
int solve(int n, int k, int b) {
    if(n >= A.size()) return 0;
    if(memo[n][k][b].valid) return memo[n][k][b].val;
    const int av = A[n] - '0';
    const int bv = n < B.size() ? B[n] - '0' : 0;

    int ans = 0;
    // consider borrow
    {
        int rem = av - b;
        if(rem >= bv) {
            ans = solve(n+1, k, 0) * 10 + (rem - bv);
        } else {
            ans = solve(n+1, k, 1) * 10 + (rem + 10 - bv);
        }
    }
    // ignore borrow
    if(b > 0 && k > 0) {
        if(av >= bv) {
            ans = max(ans, solve(n+1, k-1, 0) * 10 + (av - bv));
        } else {
            ans = max(ans, solve(n+1, k-1, 1) * 10 + (av + 10 - bv));
        }
    }
    memo[n][k][b] = ans;
    return ans;
}

bool solve() {
    int K;
    if(!(cin >> A >> B >> K)) return false;
    reverse(begin(A), end(A));
    reverse(begin(B), end(B));

    for(int n = 0; n < 10; ++n) {
        for(int k = 0; k <= K; ++k) {
            for(int b = 0 ; b < 2; ++b) {
                memo[n][k][b].valid = false;
            }
        }
    }

    cout << solve(0, K, 0) << endl;
    return true;
}

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

    while(solve()) ;
    return 0;
}

Measured memory_bytes: 1212
#define IDX(tx,ty,kx,ky) ((((tx)*51+(ty))*51+(kx))*51+(ky))
S[51*51*51*51];
m[51][51];
X,Y;
tx,ty,kx,ky;
tx2,ty2,kx2,ky2;
q,s;
move(vx,vy){
	int idx;
	tx2=tx+vx;
	ty2=ty+vy;
	kx2=kx-vx;
	ky2=ky-vy;
	if(tx2<1||tx2>X||ty2<1||ty2>Y||m[tx2][ty2])
		tx2=tx,ty2=ty;
	if(kx2<1||kx2>X||ky2<1||ky2>Y||m[kx2][ky2])
		kx2=kx,ky2=ky;
	//printf("step%d : (%d,%d,%d,%d) -> (%d,%d,%d,%d)",s,tx,ty,kx,ky,tx2,ty2,kx2,ky2);
	idx=IDX(tx2,ty2,kx2,ky2);
	if(!S[idx]){
		//printf(" S[%d]=%d\n",q,idx);
		S[idx]=s;
		S[q]=idx*256+s;
		q=idx;
	}else{
		//printf(" visited\n");
	}
	return tx2==kx2&&ty2==ky2;
}
main(){
	int x,y,c,t;
	for(;scanf("%d%d",&X,&Y),X;){
		scanf("%d%d%d%d",&tx,&ty,&kx,&ky);
		for(y=1;y<=Y;y++)
			for(x=1;x<=X;x++)
				scanf("%d",&m[x][y]);
		q=0;//(0,0,0,0)Í³øÈÀWÈÌÅn_ÆµÄgpµÄæ¢
		s=0;
		c=0;
		move(0,0);
		for(;/*printf("dequeue S[%d]=%d:%d\n",c,S[c]/256,S[c]%256),*/c=S[c],c>=256;){
			s=c%256,c/=256;
			t=c;
			ky=t%51,t/=51;
			kx=t%51,t/=51;
			ty=t%51,t/=51;
			tx=t;
			if(tx==kx&&ty==ky){
				break;
			}
			if(++s<100){
				if(move(1,0)|move(-1,0)|move(0,1)|move(0,-1)){
					printf("%d\n",s);
					break;
				}
			}
		}
		if(c<256)
			puts("NA");
		memset(S,0,sizeof(S));
	}
	{int n;for(n=1000000;n--;)getchar();}//delay(0.52s)
	exit(0);
}

Measured memory_bytes: 26000
#include<iostream>
#include<vector>
#include<string>
#include<queue>
//#include<set>
#define all(x) x.begin(), x.end()
using namespace std;
typedef long long ll;
typedef double db;
const int MOD = 1e9 + 7;
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	//freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);
	int n;
	cin >> n;
	ll a[300];
	for (int i = 0; i < n; ++i)
		cin >> a[i];
	ll bone = 0;
	for (int i = 2; i < n; ++i)
		bone ^= a[i];
	ll meat = a[0] + a[1];
	if (meat < bone || (meat - bone) & 1)
	{
		cout << "-1";
		return 0;
	}
	meat = (meat - bone) >> 1;
	if (meat > a[0] || (bone & meat) != 0)
	{
		cout << "-1";
		return 0;
	}
	for (int i = 40; i >= 0; --i)
	{
		if ((ll(1) << i) & bone)
		{
			if (meat + (ll(1) << i) <= a[0])
				meat += (ll(1) << i);
		}
	}
	if (meat == 0)
	{
		cout << "-1";
		return 0;
	}
	cout << a[0] - meat;
	return 0;
}

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

int main(){
  int A,B;
  cin >> A >> B;
  int sum=0;
 for(int i=0; i<100000; i++){
   if(i==0&&A*i+1-i>B){
     break;}
   if(i>0){sum++;}
   if(A*i+1-i>=B){
     break;}}
   
  cout << sum << endl;}


Measured memory_bytes: 256
loop do
  n = gets.chomp.to_i
  break if n == 0

  keys = gets.chomp.split(' ').map(&:to_i)
  key_pos = 0
  station_list = 'abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ'
  stations_pos = {}
  i = 0
  station_list.each_char do |station|
    stations_pos[station] = i
    i += 1
  end

  enc_stations = gets.chomp
  dec_stations = ''

  enc_stations.each_char do |enc_station|
    pos = stations_pos[enc_station]
    dec_stations << station_list[pos - keys[key_pos]]
    key_pos = key_pos + 1 == keys.size ? 0 : key_pos + 1
  end

  puts dec_stations
end

Measured memory_bytes: 6116
#include <iostream>      // cout, endl, cin
#include <string>        // string, to_string, stoi
#include <vector>        // vector
#include <algorithm>     // min, max, swap, sort, reverse, lower_bound, upper_bound
#include <utility>       // pair, make_pair
#include <tuple>         // tuple, make_tuple
#include <cstdint>       // int64_t, int*_t
#include <cstdio>        // printf
#include <map>           // map
#include <queue>         // queue, priority_queue
#include <set>           // set
#include <stack>         // stack
#include <deque>         // deque
#include <unordered_map> // unordered_map
#include <unordered_set> // unordered_set
#include <bitset>        // bitset
#include <bits/stdc++.h> // isupper, islower, isdigit, toupper, tolower
#include <iomanip>
#define rep(i, n) for (int i = 0; i < (n); i++)
using namespace std;
typedef long long ll;
typedef pair<ll, ll> Pl;
typedef pair<int, int> P;
#include <cmath>

int main()
{
  ll a, b, h, m;
  cin >> a >> b >> h >> m;
  double ang1 = 6.0 * m, ang2 = 30.0 * h + 0.5 * m;
  double res = a * a + b * b - 2 * a * b * cos(abs(ang1 - ang2) * acos(-1) / 180);
  cout << fixed << setprecision(15) << sqrt(res) << endl;
  return 0;
}


Measured memory_bytes: 4196
#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
#include <map>
using namespace std;

typedef long long LL;
typedef pair<int, int> PII;

int n, k;

int main(){
	scanf(" %d %d", &n, &k);
	if(n % 2 == 0){
		if(k <= n / 2) printf("YES\n");
		else printf("NO\n");
	}
	else{
		if(k <= n / 2 + 1) printf("YES\n");
		else printf("NO\n");
	}
}

Measured memory_bytes: 256
n = int(input())
p = list(map(int ,input().split()))
q = list(map(int ,input().split()))

p_o = 0
p_s = set()
q_o = 0
q_s = set()

fact = [1, 1]
for i in range(2,n):
  fact += [fact[i-1]*i]

for i in range(n):
  k = 0
  for j in range(1, p[i]):
    if not j in p_s:
      k += 1
  p_o += k * fact[n-i-1]
  p_s.add(p[i])

for i in range(n):
  k = 0
  for j in range(1, q[i]):
    if not j in q_s:
      k += 1
  q_o += k * fact[n-i-1]
  q_s.add(q[i])
  
print(abs(p_o - q_o))

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

using namespace std;

const int MAX_N = 100005;
const int INF = (1 << 30);

int n, k;

long long h[MAX_N], dp[MAX_N];

int mod(int i, int j) {
  if (i > n || j > n) {
    return INF;
  }
  return abs(h[i] - h[j]);
}

int main() {
  scanf("%d %d", &n, &k);
  for (int i = 1; i <= n; ++i) {
    scanf("%lld", &h[i]);
    dp[i] = INF;
  }
  dp[1] = 0;
  for (int i = 1; i <= n; ++i) {
    for (int j = 1; j <= k; ++j) {
      dp[i + j] = min(dp[i + j], dp[i] + mod(i, i + j));
    }
  }
  printf("%lld", dp[n]);
  return 0;
}


Measured memory_bytes: 1792
import sys
from math import factorial
from collections import Counter
from fractions import Fraction
import heapq, bisect, fractions
import math
import itertools
sys.setrecursionlimit(10 ** 5 + 10)
INF = 10**15 +5
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
MOD = 10**9 + 7


N = INT()
A = LIST()
c = Counter(A)

for i in range(N):
    print(c[i+1])

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

const int INF = 100100100;
const int MOD = (int)1e9 + 7;
typedef long long ll;
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define REP(i, n) for (int i = 0; i < (n); ++i)

int main() {
  int n;
  cin >> n;
  string tmp;
  int ans = 0;
  FOR(i,1,n+1) {
    tmp = to_string(i);
    if (tmp.size()%2!=0) ans +=1; 
  }
  cout << ans << endl;
  
}

Measured memory_bytes: 3668
#include <algorithm>
#include <cmath>
#include <iomanip>
#include <iostream>
#include <limits>
#include <map>
#include <queue>
#include <stack>
#include <vector>

using namespace std;

using Pair = pair<int, int>;
using lint = long long;

// const int mod = 1e9 + 7;
// const int mod = 998244353;

template <typename T> vector<T> make_v(size_t a) { return vector<T>(a); }

template <typename T, typename... Ts> auto make_v(size_t a, Ts... ts) {
  return vector<decltype(make_v<T>(ts...))>(a, make_v<T>(ts...));
}

int main(){
  string s;
  cin >> s;
  if (s == "RSR") cout << 1 << endl;
  else 
  cout << count(s.begin(), s.end(), 'R') << endl;
}



Measured memory_bytes: 3624
// ?????¬???????????¬??????

#include <iostream>
#include <iomanip>
#include <cstdio>
#include <string>
#include <cstring>
#include <deque>
#include <list>
#include <queue>
#include <stack>
#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>
using namespace std;

#define rep(i,a,n) for(int (i)=(a); (i)<(n); (i)++)
#define repq(i,a,n) for(int (i)=(a); (i)<=(n); (i)++)
#define repr(i,a,n) for(int (i)=(a); (i)>=(n); (i)--)
#define int long long int

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

typedef pair<int, int> pii;
typedef long long ll;

int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};
constexpr ll INF = 1001001001001001LL;
constexpr ll MOD = 1000000007LL;

map< vector<int>, int > mp;

void init(vector<int> vs) {
    queue< vector<int> > que;
    que.push(vs);

    while(!que.empty()) {
        vector<int> cur = que.front(); que.pop();
        
        int idx = -1;
        rep(i,0,8) {
            if(cur[i] == 0) {
                idx = i;
                break;
            }
        }

        rep(k,0,4) {
            int nx = (idx / 4) + dx[k];
            int ny = (idx % 4) + dy[k];
            if(nx < 0 || nx >= 2 || ny < 0 || ny >= 4) continue;
            int nc = nx * 4 + ny;
            vector<int> tmp = cur;
            swap(tmp[nc], tmp[idx]);
            if(mp.count(tmp)) continue;
            mp[tmp] = mp[cur] + 1;
            que.push(tmp);
        }
    }
}

signed main() {
    vector<int> v(8);
    iota(v.begin(), v.end(), 0);
    mp[v] = 0;
    init(v);

    string s;
    while(getline(cin, s)) {
        stringstream ss(s);
        vector<int> vs;
        int val;
        while(ss >> val) vs.push_back(val);

        cout << mp[vs] << endl;
    }
    return 0;
}

Measured memory_bytes: 6252
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>

#include <iostream>
#include <complex>
#include <string>
#include <algorithm>
#include <numeric>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>

#include <functional>
#include <cassert>

typedef long long ll;
using namespace std;

#ifndef LOCAL
#define debug(x) ;
#else
#define debug(x) cerr << __LINE__ << " : " << #x << " = " << (x) << endl;

template <typename T1, typename T2>
ostream &operator<<(ostream &out, const pair<T1, T2> &p) {
  out << "{" << p.first << ", " << p.second << "}";
  return out;
}

template <typename T>
ostream &operator<<(ostream &out, const vector<T> &v) {
  out << '{';
  for (const T &item : v) out << item << ", ";
  out << "\b\b}";
  return out;
}
#endif

#define mod 1000000007 //1e9+7(prime number)
#define INF 1000000000 //1e9
#define LLINF 2000000000000000000LL //2e18
#define SIZE 200010

vector<pair<int,int>> G[SIZE];
bool base[SIZE];

using DPVec = vector<vector<int>>;

DPVec dfs(int now, int back = -1, int cost = INF) {
  DPVec dpL;

  for(auto p : G[now]) {
    int to = p.first;
    int dc = p.second;

    if (to == back) continue;

    DPVec dpR = dfs(to, now, dc);

    if (dpL.size() == 0) {
      swap(dpR, dpL);
    } else {
      int L = dpL.size();
      int R = dpR.size();

      for (int i=1; i<R; i++)
        dpL.push_back(vector<int>(2, INF));

      for (int i=L-1; i>=0; i--) {
        for (int j=R-1; j>=0; j--) {
          dpL[i+j][0] = min(dpL[i+j][0], dpL[i][0] + dpR[j][0]);
          dpL[i+j][1] = min(dpL[i+j][1], dpL[i][1] + dpR[j][0]);
          dpL[i+j][1] = min(dpL[i+j][1], dpL[i][0] + dpR[j][1]);
          dpL[i+j][1] = min(dpL[i+j][1], dpL[i][1] + dpR[j][1]);
        }
      }
    }
  }

  if (dpL.size() == 0) {
    dpL.assign(1, vector<int>(2, INF));
    dpL[0][0] = 0;
  }

  if (base[now]) {
    int L = dpL.size();
    for (int i=0; i<L; i++) {
      dpL[i][1] = min(dpL[i][1], dpL[i][0]);
      dpL[i][0] = INF;
    }
  }

  int L = dpL.size();
  dpL.push_back(vector<int>(2, INF));
  for (int i=0; i<L; i++) {
    dpL[i+1][0] = min(dpL[i+1][0], dpL[i][1] + cost);
  }

  return dpL;
}

int solve() {
  int N, T, K;

  scanf("%d%d%d", &N, &T, &K);

  if (N == 0) return -1;

  for (int i=0; i<N; i++) {
    G[i] = vector<pair<int,int>>();
    base[i] = false;
  }

  for (int i=0; i<N-1; i++) {
    int a, b, c;
    scanf("%d%d%d", &a, &b, &c);
    a--; b--;
    G[a].push_back({b, c});
    G[b].push_back({a, c});
  }

  for (int i=0; i<T; i++) {
    int a;
    scanf("%d", &a);
    a--;
    base[a] = true;
  }

  auto res = dfs(0);

  return res[K][1];
}


int main(){
  for(int i=1;; i++) {
   int ans = solve();

   if (ans == -1) break;

   printf("Case %d: %d\n", i, ans);
  }

  return 0;
}



Measured memory_bytes: 10944
def main():
    from functools import reduce

    N = int(input())

    def gcd(a, b):
        while b:
            a, b = b, a % b
        return a

    def lcm(a, b):
        return a // gcd(a, b) * b

    ret = reduce(lcm, (int(input()) for _ in range(N)))
    print(ret)


if __name__ == '__main__':
    main()


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

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

int main()
{
  int N, K;
  cin >> N >> K;
  vector<int> A(N);
  int A_max = 0;
  for (int i = 0; i < N; i++)
  {
    cin >> A[i];
    if (A_max < A[i])
      A_max = A[i];
  }
  int g = A[0];
  for (int i = 1; i < N; i++)
    g = gcd(g, A[i]);
  if (K % g == 0 && K <= A_max)
    cout << "POSSIBLE" << endl;
  else
    cout << "IMPOSSIBLE" << endl;
  return 0;
}

Measured memory_bytes: 640
n, k = map(int, input().split())
a = list(map(int, input().split()))

dp = [1] * (k + 1)
player = ["First", "Second"]

for i in range(1, k + 1):
    for j in range(n):
        if 0 <= i - a[j] and dp[i - a[j]] == 1:
            dp[i] = 0

print(player[dp[k]])
        

Measured memory_bytes: 42000
N = int(input())
T = [list(map(int,input().split())) for _ in range(N)]

T.sort(key = lambda x:x[0])

class Node:
    def __init__(self,data,l_child,r_child):
        self.data = data
        self.l_child = l_child
        self.r_child = r_child

T = [Node(T[i][0],T[i][1],T[i][2]) for i in range(N)]

P = [-1 for _ in range(N)]
for i in range(N):
    if T[i].l_child != -1:
        P[T[i].l_child] = T[i].data
    if T[i].r_child != -1:
        P[T[i].r_child] =T[i].data
for i in range(N):
    if P[i] == -1:
        root = i

def Pre_patrol(node,List):
    if node.data != -1:
        List.append(node.data)
        if node.l_child != -1:
            Pre_patrol(T[node.l_child],List)
        if node.r_child != -1:
            Pre_patrol(T[node.r_child],List)
    return List

def In_patrol(node,List):
    if node.data != -1:
        if node.l_child != -1:
            In_patrol(T[node.l_child],List)
        List.append(node.data)
        if node.r_child != -1:
            In_patrol(T[node.r_child],List)
    return List

def Pos_patrol(node,List):
    if node.data != -1:
        if node.l_child != -1:
            Pos_patrol(T[node.l_child],List)
        if node.r_child != -1:
            Pos_patrol(T[node.r_child],List)
        List.append(node.data)
    return List

print("Preorder")
for i in range(N):
    print(" "+str(Pre_patrol(T[root],[])[i]),end="")
print()
print("Inorder")
for i in range(N):
    print(" "+str(In_patrol(T[root],[])[i]),end="")
print()
print("Postorder")
for i in range(N):
    print(" "+str(Pos_patrol(T[root],[])[i]),end="")
print()



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

int main(){
  int n;
  int ans;
  cin >> n ;
  if(n<600)ans=8;
  else if(n<800)ans=7;
  else if(n<1000)ans=6;
  else if(n<1200)ans=5;
  else if(n<1400)ans=4;
  else if(n<1600)ans=3;
  else if(n<1800)ans=2;
  else if(n<2000)ans=1;
  cout << ans << endl;
  return 0;
}


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

int main () {
    ll kane = 100;
    ll x; 
    cin >> x;
    ll ans = 0;
    while (x > kane){
        kane *= 1.01;
        ans++;
    }
    cout << ans << endl;
}

Measured memory_bytes: 3636
#include<iostream>
#include<string>
#include<algorithm>    
#include<cmath>
#include<map>
#include<vector>
#include<math.h>
#include<stdio.h>
#include<stack>
#include<queue>
#include<tuple>
#include<cassert>
#include<set>
#define int long long
#define mod(int)(1000000007)
using namespace std;
int test[213456];
int ok[213456];
signed main() {
	int n, m; cin >> n >> m;
	for (int h = m; h <= m * 10 * 10; h++) {
		if (h * 8 / 100 == n && h * 10 / 100 == m) {
			cout << h << endl; return 0;
		}
	}
	cout << -1 << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <cmath>
#include <map>
#include <iomanip>
#include <deque>
typedef long long ll;
#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;
using vi = vector<int>;
using vll = vector<ll>;
ll mod = 1e9 + 7;
ll llmax = 10000000000000000000ll;
using namespace std;
using Graph = vector<vector<int>>;
Graph G;
const int AMAX = 100000;
/*int cnt_digit(ll N)
{
	int digit = 0;

	while (N > 0)
	{
		N /= 10;
		digit++;
	}
	return digit;
}



int n;
vll a;

ll solve(bool isp)
{
	ll sum = 0ll;
	ll ret = 0ll;

	for (int i = 0; i < n; i++)
	{
		sum += a[i];
		if (isp and sum <= 0)
		{
			ret += -sum + 1;
			sum = 1ll;
		}
		if (not isp and sum >= 0)
		{
			ret += sum + 1;
			sum = -1ll;
		}
		isp ^= 1;
	}
	return ret;
}

*/

//計算クラス
class Calc
{
public:
	// 最大公約数計算
	int calcGCD(int a, int b);
};

/*
 * 最大公約数計算
 */
	int Calc::calcGCD(int a, int b)
{
	if (b == 0) {
		return a;
	}
	else {
		return calcGCD(b, a % b);
	}
}

int main()
{
	cin.tie(0);
	ios::sync_with_stdio(false);
	
	int N, M;
	cin >> N >> M;
	
	
	bool f[200010] = {};
	bool s[200010] = {};
	for (int i = 0; i < M; i++)
	{
		int a, b;
		cin >> a >> b;
		if (a == 1)
		{
			f[b] = true;
		}
		if (b == N)
		{
			s[a] = true;
		}
		
	}
	for (int i = 0; i < 200010; i++)
	{
		if ((f[i] == true) && (s[i] == true))
		{
			cout << "POSSIBLE" << endl;
			return 0;
		}
	}
	
	cout << "IMPOSSIBLE" << endl;

	/*ll N;
	cin >> N;
	vector<vector<ll>> data(N, vector<ll>(N));
	vector <ll> gcb1(N * N);
	ll sum = 0;
	for (int i = 1; i <= N; i ++)
	{
		for (int j = 1; j <= N; j++)
		{
			Calc objCalc;
			data[i-1][j-1] = objCalc.calcGCD(i, j);
			sum += data[i-1][j-1];

		}
	}
	sum += N * N;
	cout << sum << endl;
	//int ans = 1;
	//ll ans = 10000000000000000000ll;
	int a, b;

	
		// データ入力
		cout << "１つ目の自然数：";
		cin >> a;
		cout << "２つ目の自然数：";
		cin >> b;
		cout << "a = " << a << ", "
			<< "b = " << b << endl;

		// 計算
		Calc objCalc;
		cout << "最大公約数 = " << objCalc.calcGCD(a, b) << endl;
	*/

	return 0;

	


}

Measured memory_bytes: 640
#include<bits/stdc++.h>
using namespace std;
int main(){
    int n,k;
    cin>>n>>k;
    int a[n];
    for(int i=0;i<n;i++)cin>>a[i];
    long long wa[n+1];
    wa[0]=0;
    map<int,vector<int>>x;
    set<int>s;
    for(int i=1;i<=n;i++)wa[i]=wa[i-1]+a[i-1];
    for(int i=0;i<=n;i++){
        wa[i]=((wa[i]-i)%k+k)%k;
        x[wa[i]].push_back(i);
        s.insert(wa[i]);
    }
    long long ans=0;
    for(auto itr=s.begin();itr!=s.end();itr++){
        vector<int>v=x[*itr];
        for(int i=0;i<v.size();i++)ans+=lower_bound(v.begin(),v.end(),v[i]+k)-v.begin()-i-1;
    }
    cout<<ans<<endl;
    return 0;
}

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

int main() {
  int N;
  cin >> N;
  vector<double> x(N);
  vector<string> u(N);
  for (int i=0; i<N; i++) {
    cin >> x[i] >> u[i];
  }
  double answer = 0;
  for (int i=0; i<N; i++) {
    if (u[i].at(0) == 'J') {
      answer += x[i];
    }
    else {
      answer += x[i] * 380000;
    }
  }
  cout << answer << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
using namespace std;
int n, x[210000], a[210000];
int main(void){
    // Your code here!
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> x[i];
        a[i] = x[i];
    }
    sort(x, x + n);
    for (int i = 0; i < n; i++) cout << (a[i] < x[n / 2] ? x[n / 2] : x[n / 2 - 1]) << endl;
}


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

class BipartiteMatching {
private:
  struct edge {
    int to, cap, rev;
  };
  int U, V;
  vector<vector<edge>> G;
  vector<int> level;
  vector<int> iter;
public:
  BipartiteMatching(int u, int v) : U(u), V(v), G(U + V + 2) {
    for (int i = 0; i < U; i++) {
      init_edge(0, i + 1);
    }
    for (int i = 0; i < V; i++) {
      init_edge(U + i + 1, U + V + 1);
    }
  }
  void init_edge(int from, int to) {
    G.at(from).push_back((edge) {to, 1, (int) G.at(to).size()});
    G.at(to).push_back((edge) {from, 0, (int) G.at(from).size() - 1});
  }
  void add(int from, int to) {
    from += 1, to += U + 1;
    G.at(from).push_back((edge) {to, 1, (int) G.at(to).size()});
    G.at(to).push_back((edge) {from, 0, (int) G.at(from).size() - 1});
  }
  void bfs(int s) {
    fill(level.begin(), level.end(), -1);
    queue<int> que;
    level.at(s) = 0;
    que.push(s);
    while (!que.empty()) {
      int v = que.front();
      que.pop();
      for (auto &e : G.at(v)) {
        if (e.cap > 0 && level.at(e.to) < 0) {
          level.at(e.to) = level.at(v) + 1;
          que.push(e.to);
        }
      }
    }
  }
  int dfs(int v, int t, int f) {
    if (v == t) {
      return f;
    }
    for (int &i = iter.at(v); i < (int) G.at(v).size(); i++) {
      edge &e = G.at(v).at(i);
      if (e.cap > 0 && level.at(v) < level.at(e.to)) {
        int d = dfs(e.to, t, min(f, e.cap));
        if (d > 0) {
          e.cap -= d;
          G.at(e.to).at(e.rev).cap += d;
          return d;
        }
      }
    }
    return 0;
  }
  int solve() {
    level.resize(U + V + 2),  iter.resize(U + V + 2);
    int flow = 0;
    int s = 0, t = U + V + 1;
    for (;;) {
      bfs(s);
      if (level.at(t) < 0) return flow;
      fill(iter.begin(), iter.end(), 0);
      int f;
      while ((f = dfs(s, t, numeric_limits<int>::max())) > 0) {
        flow += f;
      }
    }
  }
  vector<int> allocate() {
    vector<int> res(U, -1);
    for (int i = 0; i < U; i++) {
      for (auto &e : G.at(i + 1)) {
        if (e.cap == 0 && e.to != 0) {
          res.at(i) = e.to - U - 1;
          break;
        }
      }
    }
    return res;
  }
};

int main() {
  int N;
  cin >> N;
  vector<pair<int, int>> R(N), B(N);
  for (int i = 0; i < N; i++) {
    int a, b;
    cin >> a >> b;
    R.at(i) = {a, b};
  }
  for (int i = 0; i < N; i++) {
    int c, d;
    cin >> c >> d;
    B.at(i) = {c, d};
  }
  BipartiteMatching BM(N, N);
  for (int i = 0; i < N; i++) {
    for (int j = 0; j < N; j++) {
      auto[a, b] = R.at(i);
      auto[c, d] = B.at(j);
      if (a < c && b < d) BM.add(i, j);
    }
  }
  cout << BM.solve() << "\n";
}

Measured memory_bytes: 3656
#include<cstdio>
#include<vector>
#include<algorithm>
#include<utility>
#include<numeric>
#include<iostream>
#include<array>
#include<string>
#include<sstream>
#include<stack>
#include<queue>
#include<list>
#include<functional>
#define _USE_MATH_DEFINES

#include<math.h>
#include<map>

#define INF 200000000

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<ll, int> pli;

struct OwnVector2
{
	double x, y;
	OwnVector2(double x, double y) :x(x), y(y) {}
	OwnVector2() :OwnVector2(0, 0) {}
	OwnVector2 operator+(const OwnVector2& v)const
	{
		return OwnVector2(x + v.x, y + v.y);
	}
	OwnVector2 operator-(const OwnVector2& v)const
	{
		return OwnVector2(x - v.x, y - v.y);
	}
	OwnVector2 operator*(const double v)const
	{
		return OwnVector2(x*v, y*v);
	}
	bool operator==(const OwnVector2& v)const
	{
		return abs(x - v.x) <= 0.0000000000001&&abs(y - v.y) <= 0.00000000000001;
	}
	bool operator!=(const OwnVector2& v)const
	{
		return abs(x - v.x) > 0.0000000000001 || abs(y - v.y) > 0.00000000000001;
	}

	double dot(const OwnVector2& v)const
	{
		return x*v.x + y*v.y;
	}
	double cross(const OwnVector2& v)const
	{
		return x*v.y - y*v.x;
	}
	double length()const
	{
		return sqrt(x*x + y*y);
	}
	double length2()const
	{
		return x*x + y*y;
	}
};

OwnVector2 vertices[100];

int JudgeType(OwnVector2 p, int n)
{
	int count = 0;
	OwnVector2 p0 = vertices[0];
	bool bFlag0x = (p.x <= p0.x);
	bool bFlag0y = (p.y <= p0.y);

	if ((p0 - p).length2() <= 0.000000000001)
	{
		return 1;
	}

	for (int i = 1; i < n + 1; i++)
	{
		OwnVector2 p1 = vertices[(i) % n];
		if ((p1 - p).length2() <= 0.00000000001 || (abs((p0 - p).cross(p1 - p)) <= 0.00000000000001 && (p0 - p).dot(p1 - p) <= 0.0))
		{
			return 1;
		}
		bool bFlag1x = (p.x <= p1.x);
		bool bFlag1y = (p.y <= p1.y);
		if (bFlag0y != bFlag1y)
		{
			if (bFlag0x == bFlag1x)
			{
				if (bFlag0x)
				{
					count++;
				}
			}
			else
			{
				if (p.x <= (p0.x + (p1.x - p0.x)*(p.y - p0.y) / (p1.y - p0.y)))
				{
					count++;
				}
			}
		}
		p0 = p1;
		bFlag0x = bFlag1x;
		bFlag0y = bFlag1y;
	}

	return count % 2 == 0 ? 0 : 2;
}

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

	int n;
	cin >> n;

	for (int i = 0; i < n; i++)
	{
		double x, y;
		cin >> x >> y;
		vertices[i] = OwnVector2(x, y);
	}

	int q;
	cin >> q;

	for (int i = 0; i < q; i++)
	{
		double px, py;
		cin >> px >> py;
		OwnVector2 p(px, py);

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


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

using namespace std;

#define REP(i,n)	for(int i=0, i##_len=(n); i<i##_len; ++i)
#define REPS(i,s,n)	for(int i=(s), i##_len=(n); i<i##_len; ++i)

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

typedef unsigned int 			uint;
typedef unsigned long long int	ull;
typedef long long int 			ll;

typedef pair<int,int>			P;
typedef vector<int>				V;
typedef vector<V>				VV;

#undef _P
#define _P(...) (void)printf(__VA_ARGS__)
#define MAX 		2505

const ll LINF = (ll)1e18+7;		//
const int INF = 1e9+7;			//2,147,483,647 (Max int)
const int MOD = 1e9+7;
// テンプレ終了
//====================================================================//

//
int main(){
	int N;cin>>N;
	V v(N);
	REP(i,N)cin>>v[i];

	sort(ALL(v));

	double ans = (double)(v[0]+v[1])/2;
	REPS(i,2,N){
		ans = ((double)ans + v[i])/2;
	}

	printf("%0.6lf\n",ans);

	return 0;
}




Measured memory_bytes: 256
N = int(input())
D = list(map(int,input().split()))
M = int(input())
T = list(map(int,input().split()))

P = dict()
for k in range(N):
    if D[k] in P:
        P[D[k]] += 1
    else:
        P[D[k]] = 1

for k in range(M):
    if T[k] in P:
        P[T[k]] -= 1
        if P[T[k]] == -1:
            print("NO")
            exit(0)
    else:
        print("NO")
        exit(0)
print("YES")

Measured memory_bytes: 41316
<?php
fscanf(STDIN, "%d", $n);
$ans = 0;
for($i = 0; $i <= $n; $i++){
    $t = $i;
    $cnt = 0;
    while($t > 0){
        $t = floor($t / 10);
        $cnt++;
    }
    if($cnt % 2 == 1){
        $ans++;
    }
}
echo $ans;

Measured memory_bytes: 4604
#include<iostream>
using namespace std;
int main(){
  int N;
  cin>>N;
  int ans=0;
  for(int i=0;i<N;i++){
    int l,r;
    cin>>l>>r;
    l--;
    ans += r-l;
  }
  cout<<ans<<endl;
  return 0;
}

Measured memory_bytes: 256
package main

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

var S string

func main() {
	S = nextString()
	ss := strings.Split(S, "/")
	year, _ := strconv.Atoi(ss[0])
	month, _ := strconv.Atoi(ss[1])
	day, _ := strconv.Atoi(ss[2])
	if year < 2019 {
		fmt.Printf("Heisei")
		return
	}
	if month <= 4 && day <= 30 {
		fmt.Printf("Heisei")
		return
	}
	fmt.Printf("TBD")
	return
}

func nextInt() int {
	v, _ := strconv.Atoi(nextReader())
	return v
}

func nextString() string {
	return nextReader()
}

func nextInts(n int) []int {
	r := make([]int, n)
	for i := 0; i < n; i++ {
		r[i] = nextInt()
	}
	return r
}

var nextReader func() string

func init() {
	nextReader = NewScanner()
}

func NewScanner() func() string {
	r := bufio.NewScanner(os.Stdin)
	r.Buffer(make([]byte, 1024), int(1e+11))
	r.Split(bufio.ScanWords)
	return func() string {
		r.Scan()
		return r.Text()
	}
}

func Min(a int, b int) int {
	if a > b {
		return b
	}
	return a
}

func MaxIn2Values(a int, b int) int {
	if a > b {
		return a
	}
	return b
}

func MinIn2Values(a int, b int) int {
	if a < b {
		return a
	}
	return b
}

func Abs(a int) int {
	if a < 0 {
		return a * -1
	}
	return a
}


Measured memory_bytes: 640
#include <iostream>
#include <cmath>
#include <algorithm>
#include <vector>
using namespace std;
int main() {
    int A, B, K; cin >> A >> B >> K;
    vector<int> ans;
    for (int i = A; i <= B; ++i) {
        if (A + (K - 1) >= i || B - (K - 1) <= i) ans.push_back(i);
    }
    for (int i = 0; i < ans.size(); ++i) printf("%d\n", ans[i]);
}


Measured memory_bytes: 3736
#include <stdio.h>
#include <math.h>
#include <stdlib.h>
int main(){
  int W, H, x, y;
  long double max = 0;
  int ans = 0;

  scanf("%d%d%d%d", &W, &H, &x, &y);

  if(W == (x+x) && H == (y+y)){
    ans = 1;
  }
  /*
  if((x == 0 && y == 0) || (x == 0 && y == H) || (x == W && y == 0) || (x == W && y == H)){
    //    max = (W * H) / 2;
    ans = 0;
  }
  */
  max = ((double)W * (double)H) / 2;

  printf("%Lf %d", max, ans);
  printf("\n");

}


Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
//typedef pair<ll, ll> P;
struct edge{ll to,cost;};
const int inf = 1<<27;
const ll INF = 1LL<<60;
const int COMBMAX = 1001001;
const ll MOD = 1000000007;
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define eachdo(v, e) for(const auto& e : (v))
#define all(v) (v).begin(), (v).end()
#define lower_index(v, e) (ll)distance((v).begin(), lower_bound((v).begin(), (v).end(), e))
#define upper_index(v, e) (ll)distance((v).begin(), upper_bound((v).begin(), (v).end(), e))
ll mpow(ll a, ll n, ll mod = MOD){ll res = 1; while(n > 0){if(n & 1)res = res * a % mod; a = a * a % mod; n >>= 1;} return res;}
void YesNo(bool j){cout << (j ? "Yes" : "No") << endl; return;}
void yesno(bool j){cout << (j ? "yes" : "no") << endl; return;}
template<class T1, class T2> ll bcount(T1 v, T2 a){return upper_index(v, a) - lower_index(v, a);} 
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;}
template<class T> void debug(T v){rep(i, v.size()) cout << v[i] << " " ; cout << endl;}
template<class T> void debug2(T v){rep(i, v.size()){rep(j, v[i].size()) cout << v[i][j] << " " ; cout << endl;}}

int main(){
    ll N, P; cin >> N >> P;
    string S; cin >> S;
    ll ans = 0;
    if (P == 2 || P == 5){
        rep(i, N){
            if (!((S[i] - '0') % P)) ans += i + 1;
        }
    }else{
        reverse(all(S));
        vector<ll> tb(P);
        vector<ll> dp(N + 1, 0);
        vector<ll> dp10(N + 1, 1);
        rep(i, N){
            dp10[i + 1] = (dp10[i] * 10) % P;
        }
        rep(i, N){
            dp[i + 1] = (dp[i] + dp10[i] * (S[i] - '0')) % P;
        }
        rep(i, N + 1){
            tb[dp[i]]++;
        }
        rep(i, P){
            ans += (tb[i] * (tb[i] - 1)) / 2;
        }
        // debug(dp);
        // debug(tb);
        // cout << accumulate(all(tb), 0LL) << endl;
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 3716
#include <cstdint>
#include <iostream>
#include <map>
#include <string>

int main()
{
    int n, prime;
    std::cin >> n >> prime;
    std::cin.get();

    std::string str;
    std::getline(std::cin, str);

    std::map<int, int64_t> count;
    count[0] = 1;

    int64_t total = 0;
    int sum = 0;
    int pow = 1;

    for (int i = str.size() - 1; i >= 0; i -= 1) {
        sum = (1LL * pow * (str[i] - '0') + sum) % prime;
        pow = (1LL * pow * 10) % prime;

        total += count[sum];
        count[sum] += 1;
    }

    if (prime == 2 || prime == 5) {
        total = 0;
        for (size_t i = 0; i < str.size(); i += 1) {
            if ((str[i] - '0') % prime == 0) {
                total += i + 1;
            }
        }
    }

    std::cout << total << "\n";
    return 0;
}


Measured memory_bytes: 1028
#include<bits/stdc++.h>
using namespace std;
int main(){
  int N,W;
  cin>>N>>W;
  vector<int> w(N);
  vector<int> v(N);
  int64_t sw=0;
  int sv=0;
  for(int i=0;i<N;i++){
    cin>>w.at(i)>>v.at(i);
    sw+=w.at(i);
    sv+=v.at(i);
  }
  vector<vector<int64_t>> dp(sv+1,vector<int64_t>(N+1,sw));
  int a=0;
  for(int j=0;j<=N;j++)
    dp[0][j]=0;
  for(int i=1;i<=sv;i++){
    for(int j=1;j<=N;j++)
      dp[i][j]=min(dp[i][j-1],dp[max(i-v.at(j-1),0)][j-1]+w.at(j-1));
    if(dp[i][N]>W)
      break;
    a=i;
  }
  cout<<a<<endl;
}

Measured memory_bytes: 82304
import java.io.*;
import java.util.*;
//import java.util.stream.*;
//import java.math.*;

public class Main {

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        Scanner sc = new Scanner(System.in);
        String str = br.readLine();
        System.out.println(str.lastIndexOf("Z") - str.indexOf("A") + 1);
        bw.flush();
    }
}


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

const double PI = acos(-1);
const double EPS = 1e-15;
using ll = long long;
using ull = unsigned long long;
const int inf = 2e9;
const ll INF = 2e18;
const ll MOD = 1e9+7;
const ll MOD1 = 998244353;
//typedef pair<int,int> P;

#define REP(i,n) for (int i = 0; i < (n); i++)
#define sz(s) (s).size()
#define pb push_back
#define fi first
#define se second
//#define mp make_pair

int main(){
  /**入力**/
  int a,b,t;
  cin >> a >> b>> t;
  cout << b * (t/a) << endl;
  return 0;
}



Measured memory_bytes: 256
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[sc.nextInt() - 1] = i;
        }
        
        int count = 1;
        int max = 1;
        boolean un = false;
        for (int i = 0; i < n - 1; i++) {
            if (array[i] < array[i + 1]) {
                count++;
                if (i == n - 2) {
                    un = true;
                }
            } else {
                max = Math.max(max, count);
                count = 1;
            }
        }
        
        if (un) {
            max = Math.max(max, count);
        }
        
        System.out.println(n - max);
    }
}


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

public class Main {

	public static void main(String[] args) throws NumberFormatException, IOException {
		// TODO 自動生成されたメソッド・スタブ
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		int q = Integer.parseInt(br.readLine());

		String[] tmpArray;
		//愚直に文字列を作ってみる
		StringBuffer sb = new StringBuffer();

		long left = 0;
		long right = 0;
		for(int i = 0; i < q; i++){
			tmpArray = br.readLine().split(" ");

			long pos = Long.parseLong(tmpArray[0]);
			char c = tmpArray[1].charAt(0);
			long n = Long.parseLong(tmpArray[2]);

			StringBuffer tmpSb = new StringBuffer();

//			for(int j = 0; j < n; j++){
//				tmpSb.append(c);
//			}

//			sb.insert(pos, tmpSb);

			if(c == '('){
				left += n;
			}
			else {
				right += n;
			}

//			System.out.println(sb);

			int len = sb.length();

			//判定
//			System.out.println("matching -> " + "({"+len/2+"}?){"+len/2+"}?");
			if(right == left){
				System.out.println("Yes");
			}
			else {
				System.out.println("No");
			}
//
//			if(sb.length() % 2 == 1){
//				System.out.println("No");
//			}
//			else if(sb.toString().matches("\\({"+len/2+"}?\\){"+len/2+"}?")){
//
//				System.out.println("Yes");
//			}
//			else if(sb.toString().matches("\\){"+len/2+"}?\\({"+len/2+"}?")){
//
//				System.out.println("Yes");
//			}
//			else {
//				System.out.println("No");
//			}
		}
	}

}



Measured memory_bytes: 37720
#include <iostream>
#include <iomanip>
#include <sstream>
#include <vector>
#include <string>
#include <set>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <stack>
#include <queue>
#include <deque>
#include <algorithm>
#include <functional>
#include <iterator>
#include <limits>
#include <numeric>
#include <utility>
#include <type_traits>
#include <cmath>
#include <cassert>
#include <cstdio>

using namespace std;
using namespace placeholders;

using LL = long long;
using ULL = unsigned long long;
using VI = vector< int >;
using VVI = vector< vector< int > >;
using VS = vector< string >;
using SS = stringstream;
using PII = pair< int, int >;
using VPII = vector< pair< int, int > >;
template < typename T = int > using VT = vector< T >;
template < typename T = int > using VVT = vector< vector< T > >;
template < typename T = int > using LIM = numeric_limits< T >;

template < typename T > inline istream& operator>>( istream &s, vector< T > &v ){ for ( T &t : v ) { s >> t; } return s; }
template < typename T > inline ostream& operator<<( ostream &s, const vector< T > &v ){ for ( int i = 0; i < int( v.size() ); ++i ){ s << ( " " + !i ) << v[i]; } return s; }
template < typename T > inline T fromString( const string &s ) { T res; istringstream iss( s ); iss >> res; return res; }
template < typename T > inline string toString( const T &a ) { ostringstream oss; oss << a; return oss.str(); }

#define NUMBERED( name, number ) NUMBERED2( name, number )
#define NUMBERED2( name, number ) name ## _ ## number
#define REP1( n ) REP2( NUMBERED( REP_COUNTER, __LINE__ ), n )
#define REP2( i, n ) REP3( i, 0, n )
#define REP3( i, m, n ) for ( int i = ( int )( m ); i < ( int )( n ); ++i )
#define GET_REP( a, b, c, F, ... ) F
#define REP( ... ) GET_REP( __VA_ARGS__, REP3, REP2, REP1 )( __VA_ARGS__ )
#define FOR( e, c ) for ( auto &&e : c )
#define ALL( c ) begin( c ), end( c )
#define AALL( a ) ( std::remove_all_extents< decltype( a ) >::type * )a, ( std::remove_all_extents< decltype( a ) >::type * )a + sizeof( a ) / sizeof( std::remove_all_extents< decltype( a ) >::type )
#define DRANGE( c, p ) ( c ).begin(), ( c ).begin() + ( p ), ( c ).end()

#define SZ( v ) ( (int)( v ).size() )
#define EXIST( c, e ) ( ( c ).find( e ) != ( c ).end() )

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

#define PB push_back
#define EM emplace
#define EB emplace_back
#define BI back_inserter

#define MP make_pair
#define fst first
#define snd second

#define DUMP( x ) cerr << #x << " = " << ( x ) << endl

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

	int T;
	cin >> T;

	LL x = 1, y = 1;
	REP( T )
	{
		int T, A;
		cin >> T >> A;

		const LL k = max( ( x + T - 1 ) / T, ( y + A - 1 ) / A );
		x = T * k;
		y = A * k;

	}
	cout << x + y << endl;

	return 0;
}


Measured memory_bytes: 384
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define mod 1000000007
main()
{
   int x,n,i,ind,ans=100000;
   cin>>x>>n;int p;
   map<int,int>mp;
   for(i=1;i<=n;i++)
   {
       cin>>p;mp[p]=1;
   }
   for(i=0;i<=150;i++)
   {
      if(mp[i]==1)
      {
          continue;
      }
      if(abs(x-i)<ans)
      {
          ind=i;ans=abs(x-i);
      }
   }
   printf("%d\n",ind);
}



Measured memory_bytes: 3732
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		while (true) {
			int a = scanner.nextInt();
			String s = scanner.next();
			int b = scanner.nextInt();
			int result = 0;
			boolean end = false;
			switch (s) {
				case "+" :
					result = a + b;
					break;
				case "-" :
					result = a - b;
					break;
				case "*" :
					result = a * b;
					break;
				case "/" :
					result = a / b;
					break;
				default :
					end = true;
					break;
			}
			if (end)
				break;
			System.out.println(result);
		}
		scanner.close();
	}
}


Measured memory_bytes: 26336
#include <iostream>
#include <string>
#include <vector>
#include <cmath>
#include <queue>
#include <map>
#include <set>
#include <stack>
#include<algorithm>
#include<sstream>
#include<iomanip>
#include<deque>
#include<list>


using namespace std;

typedef long long ll;

typedef pair<int, int> pii;

const ll MOD_CONST = 1000000007;
const ll BIG_NUM = 1000000000000000000;
const int BIG_INT = 1000000000;

int main() {
	int n, p;
	cin >> n >> p;
	map<int,int> m;
	for (int i = 0; i < n; i++) {
		int a;
		cin >> a;
		m[a % 2]++;
	}



	ll ans = 0;
	for (int i = p; i <= m[1];i += 2) {
		ll cnt = 1;
		for (int j = 1; j <= i;j++) {
			cnt = (cnt*(m[1] - j + 1)) / j;
		}
		ans += cnt;
	}

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



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

using namespace std;

const int MX = 200000;

vector<int> G[MX];

pair<int, int> farthest(int v, int p = -1) {
	pair<int, int> res = {1, v};
	for (int u : G[v]) {
		if (u == p) continue;
		auto tmp = farthest(u, v);
		tmp.first++;
		res = max(res, tmp);
	}
	
	return res;
}

bool win[MX + 1];

int main() {
	int n;
	ignore = scanf("%d", &n);
	for (int i = 1, u, v; i < n; i++) {
		ignore = scanf("%d %d", &u, &v);
		u--; v--;
		G[u].emplace_back(v);
		G[v].emplace_back(u);
	}
	
	int d = farthest(farthest(0).second).first;
	
	win[0] = false;
	win[1] = true;
	win[2] = false;
	for (int i = 3; i <= d; i++) win[i] = win[i - 1] == false || win[i - 2] == false;
	
	printf("%s\n", win[d] ? "First" : "Second");
	
	return 0;
}


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

public class Main {
	public static void main(String args[]) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		double r = Double.parseDouble(br.readLine());
		double area = r * r * Math.PI;
		double length = r * 2 * Math.PI;
		System.out.printf("%.6f", area);
		System.out.print(" ");
		System.out.printf("%.6f", length);
	}
}

Measured memory_bytes: 24636
from collections import defaultdict, deque, Counter
import sys
import heapq
import math

# input = sys.stdin.readline

sys.setrecursionlimit(1000000000)

MIN = -10 ** 9
MOD = 10 ** 9 + 7


def main():
    N = int(input())
    A = [int(a) for a in input().split()]
    B = [int(a) for a in input().split()]
    # A = [
    #     [int(a) for a in input().split()]
    #     for _ in range(N)
    # ]
    for i in range(N):
        if A[i] > B[i]:
            print(-1)
            return
    target = set(i for i, (a, b) in enumerate(zip(A, B)) if a < b)
    q = [i for i in range(N) if B[N - 1 if i == 0 else i - 1] < B[i] and B[i] > B[0 if i == N - 1 else i + 1]]

    result = 0
    while len(q) != 0:
        i = q.pop()
        if i not in target:
            continue

        pre = N - 1 if i == 0 else i - 1
        fwd = 0 if i == N - 1 else i + 1

        if B[pre] < B[i] and B[i] > B[fwd]:
            minus = B[pre] + B[fwd]
            sa = B[i] - max(B[pre], B[fwd])
            kaisu = (1 + sa // minus)
            if B[i] - kaisu * minus < A[i]:
                sa = B[i] - A[i]
                kaisu = sa // minus
                if kaisu == 0:
                    print(-1)
                    return
                B[i] -= kaisu * minus
            else:
                B[i] -= kaisu * minus
            result += kaisu
            if A[i] == B[i]:
                target.remove(i)
            if A[i] > B[i]:
                print(-1)
                return
            q.append(pre)
            q.append(fwd)
    if len(target) != 0:
        print(-1)
    else:
        print(result)


if __name__ == '__main__':
    main()


Measured memory_bytes: 122004
#include <bits/stdc++.h>
#include<string.h>
using namespace std;
#define FAST ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define Max(x,y,z) max(x,max(y,z))
#define Min(x,y,z) min(x,min(y,z))
#define fr(i,s,e) for(i=s;i<e;i++)
#define rf(i,s,e) for(i=s-1;i>=e;i--)
#define pb push_back
#define eb emblace_back
#define mp make_pair
#define ff first
#define ss second 
//#define int   long long
#define ll   long long
#define pii pair<int, int>
#define trace1(x)                cerr<<#x<<": "<<x<<endl
#define trace2(x, y)             cerr<<#x<<": "<<x<<" | "<<#y<<": "<<y<<endl
#define trace3(x, y, z)          cerr<<#x<<":" <<x<<" | "<<#y<<": "<<y<<" | "<<#z<<": "<<z<<endl
#define trace4(a, b, c, d)       cerr<<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<endl
#define trace5(a, b, c, d, e)    cerr<<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<" | "<<#e<< ": "<<e<<endl
#define trace6(a, b, c, d, e, f) cerr<<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<" | "<<#e<< ": "<<e<<" | "<<#f<<": "<<f<<endl
#define vl vector<long long>
#define inf (1LL<<61)
#define vi vector<int>
#define vii vector< vector<int> >
#define vll vector< vector<long long> >
#define vpi vector< pair<int,int> >
#define vpl vector< pair<ll,ll> >
#define viii vector< vector<vector<int> > >
typedef pair<pair<int, int>,int> P;
#define cd complex<double>
#define PI 4*atan(1)
#define mod %1000000007
#define pi 3.14159265358979323846//20 decimals
#define ld long double

int main(){
    FAST
    int x, y, a,b, c;
    cin>>x>>y>>a>>b>>c;
    vector<int> p(a), q(b), r(c);
    for(int i = 0; i<a; i++){
        cin>>p[i];
    }
    for(int i = 0; i<b; i++){
        cin>>q[i];
    }
    for(int i = 0; i<c; i++){
        cin>>r[i];
    }
    sort(p.begin(), p.end(), greater<int>());
    sort(q.begin(), q.end(), greater<int> ());
    sort(r.begin(), r.end(), greater<int>());
    int l = 0, m = 0, n=0;
    ll sum = 0;
    for(int i =0; i<x+y; i++){
        if(l < x && (m >= y || p[l] >= q[m]) && ( (n >= c) || p[l] >= r[n]) ){
            sum += p[l++];
        }else if(m < y && (l >= x || q[m] >= p[l]) && ( (n >= c) || q[m] >= r[n]) ){
            sum += q[m++];
        }else{
            sum += r[n++];
        }
    }
    cout<<sum<<endl;

    return 0;
}

Measured memory_bytes: 1408
S = input()

a = int(S[0:2])
b = int(S[2:])

if 1 <= a and a <= 12 and 1 <= b and b <= 12:
    print('AMBIGUOUS')
elif (a < 1 or 12 < a) and (b < 1 or 12 < b):
    print('NA')
elif 1 <= a and a <= 12:
    print('MMYY')
else:
    print('YYMM')


Measured memory_bytes: 2940