akhauriyash/Code-Regression huggingface dataset:
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("sse2")

#include<bits/stdc++.h>
#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>
using namespace std;

#define int         long long
#define ll          long long
#define pb          push_back
#define pii         pair<int,int>
#define vi          vector<int>
#define vii         vector<pii>
#define mi          map<int,int>
#define mii         map<pii,int>
#define mp          make_pair
#define all(a)      (a).begin(),(a).end()
#define FF           first
#define SS           second
#define sz(x)       (int)x.size()
#define endl        '\n'
//#define hell          1000000007
#define rep(i,a,b)  for(int i=a;i<b;i++)
// mp::cpp_int
#define pp pair<pii,pii>
const int hell =1000000007;



int power(int a,int b)
{
  if(b==0)return 1;
  if(b==1)return a;
  int t=power(a,b/2);
  t%=hell;
  t*=t;
  t%=hell;
  if(b%2)return (t*a)%hell;
  else
     return t;
}

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

int digitsum(int x)
{
  while(x>9)
    {  int ans=0;
       while(x!=0)
       {
        ans+=x%10;
        x/=10;
       }
       x=ans;
    }
    return x;
}

int pw(int a,int b)
{
  int x=a;
  rep(i,1,b){a=a*x;}
  return a;
}



int solve( ){

int n,w;
cin>>n>>w;
int a[n][2];
rep(i,0,n)cin>>a[i][0]>>a[i][1];

int dp[n+1][w+1];

rep(i,0,n+1)
{
  rep(j,0,w+1)
  {
      if(i==0||j==0)dp[i][j]=0;
      else
      { 
        

        if(a[i-1][0]<=j)
        {
          dp[i][j]=max(dp[i-1][j],dp[i-1][j-a[i-1][0]]+a[i-1][1]);
        }
        else
          dp[i][j]=dp[i-1][j];
      }
     
  }

}

cout<<dp[n][w];

return 0;
}

signed main()
{  int t=1;
 ios::sync_with_stdio(false);
   cin.tie(0);
   cout.tie(0);
   cin.exceptions(cin.failbit);


  clock_t time_req;

    // Without using pow function
    time_req = clock();
    
//cin>>t;

    int k=1;
   while(t--)
     {
       //cout<<"case #"<<k<<":"<<" ";k++;
      solve();
     }

         time_req = clock() - time_req;
 // cout << "Processor time taken is "
   // << (double)time_req/CLOCKS_PER_SEC << " seconds" << endl;


    return 0;
}

Measured memory_bytes: 79232
import collections
import sys
from functools import lru_cache
sys.setrecursionlimit(int(10**9))
n, m  = [int(i) for i in input().strip().split(' ')] 
edges = collections.defaultdict(list)
for i in range(m):
    s,d = [int(i) for i in input().strip().split(' ')]
    edges[s-1].append(d-1) 
# dp = [-1]*n
maxPath = 0 
@lru_cache(None)
def dfs(node): 
    ans = 0 
    for i in edges[node]:
        ans = max(ans,dfs(i)+1)
    return ans
 
for i in range(n):
    maxPath = max(dfs(i), maxPath) 
print(maxPath)

Measured memory_bytes: 91052
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
#define ll long long
#define ld long double
#define all(a) a.begin(),a.end()
#define endl '\n'
#define ios ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define ull unsigned long long
#define int long long
#define iter set<int>::iterator
using namespace std;
using namespace __gnu_pbds;

template<class T>
using ordered_set=tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;

template<class T>
using ordered_multiset=tree<T,null_type,less_equal<T>,rb_tree_tag,tree_order_statistics_node_update>;

mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
mt19937_64 rnd1(chrono::steady_clock::now().time_since_epoch().count());

//find_by_order
//order_of_key

const int N=2e5+7;
const int inf=1e18+5;
const int mod=1e9+7;

int tin[N],tout[N];
int timer=0;
int t[N*4],ob[N*4];
vector<int>g[N];

void dfs(int v,int p=-1)
{
    tin[v]=++timer;
    for (int i=0;i<g[v].size();++i){
        int to=g[v][i];
        if (to==p)continue;
        dfs(to,v);
    }
    tout[v]=timer;
}

void push(int v,int l,int r)
{
    t[v]+=(r-l+1)*ob[v];
    if (l!=r){
        ob[v+v]+=ob[v];
        ob[v+v+1]+=ob[v];
    }
    ob[v]=0;
}

void update(int v,int l,int r,int l1,int r1,int x)
{
    push(v,l,r);
    if (l>r1 || r<l1)return;
    if (l>=l1 && r<=r1){
        ob[v]+=x;
        push(v,l,r);
        return;
    }
    int mid=(l+r)/2;
    update(v+v,l,mid,l1,r1,x);
    update(v+v+1,mid+1,r,l1,r1,x);
    t[v]=t[v+v]+t[v+v+1];
}

int get(int v,int l,int r,int l1,int r1)
{
    push(v,l,r);
    if (l>r1 || r<l1)return (int)0;
    if (l>=l1 && r<=r1)return t[v];
    int mid=(l+r)/2;
    return (get(v+v,l,mid,l1,r1)+get(v+v+1,mid+1,r,l1,r1));
}

main ()
{
    ios;
    int n,q;
    cin>>n>>q;
    for (int i=1;i<=n-1;++i){
        int x,y;
        cin>>x>>y;
        g[x].pb(y);
        g[y].pb(x);
    }
    dfs(1);
    for (int i=1;i<=q;++i){
        int v,x;
        cin>>v>>x;
        update(1,1,n,tin[v],tout[v],x);
    }
    for (int i=1;i<=n;++i){
        cout<<get(1,1,n,tin[i],tin[i])<<' ';
    }
}


Measured memory_bytes: 38400
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); i++)
using namespace std;
using ll = long long;
using ld = long double;
const int INF = (1<<30)-1;
const long long LINF = (1LL<<62)-1;
const long double PI = acos(-1.0L);
const int dx[] = {-1, 0, 1, 0};
const int dy[] = {0, 1, 0, -1};
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }

signed main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  string s;
  cin >> s;
  int ans = 0;
  for (auto e : s) {
    if (e == '1')
      ans++;
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 256
import sys
import copy
input = sys.stdin.readline

n = int(input())
a = list(map(int,input().split()))
b = copy.copy(a)
sum_odd = sum(a[1::2])
sum_eve = sum(a[::2])

ans = 0
sum_a  = 0
for i in range(n):
        
    sum_a = sum_a + a[i]
        
    if sum_a *(-1)**(i+1) < 1:
        kari = 1-sum_a *(-1)**(i+1)
        a[i] += 1*(-1)**(i+1) *(kari)
        sum_a += 1*(-1)**(i+1) *(kari)
            
        ans = ans + abs(kari)
            
ans1 = 0
sum_b = 0
             
for i in range(n):
       
    sum_b = sum_b + b[i]
    if sum_b *(-1)**(i) < 1:
        kari = (1-sum_b *(-1)**(i))
        b[i] += 1*(-1)**(i) * kari
        sum_b += 1*(-1)**(i) * kari

        ans1 = ans1 + abs(kari)


print(min(ans,ans1))


Measured memory_bytes: 20260
#![allow(unused_imports)]
#![allow(clippy::many_single_char_names)]
#![allow(clippy::suspicious_arithmetic_impl)]

// using Rust(1.42.0)
// My Library Repo is at "https://github.com/Loptall/prcn_lib"
// check available crates on AtCoder at "https://atcoder.jp/contests/language-test-202001"

/*
    AtCoder Language Update 2020204 お疲れ様でした! 有難いです
*/

// Dep crates are...
use std::cmp::{max, min, Ordering};
use std::collections::{BTreeMap, BTreeSet, HashMap, HashSet, VecDeque};
use std::mem::swap;
use std::ops::*;
use std::{i128, i16, i32, i64, i8, isize, u128, u16, u32, u64, u8, usize};

use itertools::*;
use itertools_num::*;
use lazy_static::lazy_static;
use maplit::{btreemap, btreeset, hashmap, hashset};
use num_bigint::{BigInt, BigUint};
use num_integer::{binomial, gcd, lcm, Integer};
use permutohedron::Heap;
use proconio::{fastout, input, is_stdin_empty, marker::*};
use rand::random;

// code...
fn main() {
    input! {
        mut x: usize
    }

    let mut ans = 0usize;
    let mut m = 100.;

    while m < x as f64 {
        ans += 1;
        m *= 1.01;
        m = m.floor();
    }

    println!("{}", ans);
}


Measured memory_bytes: 2544
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees#, log2
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
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()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10**9 + 7
#from decimal import *

N = INT()
p = LIST()

ans = 0
i = 0
while i < N:
	if p[i] == i+1:
		ans += 1
		i += 1
	i += 1
print(ans)




Measured memory_bytes: 15960
/*Function Template*/
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
const int mod = 1000000007;
const ll MOD = 1000000000000000001;
#define rep(i, n) for(ll i = 0; i < (n); i++)
#define ALL(a)  (a).begin(),(a).end()
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);


ll Len(ll n) {
  ll s=0;
  while(n!=0) s++, n/=10;
  return s;
}


ll Sint(ll n) {
  ll m=0,s=0,a=n;
  while(a!=0) s++, a/=10;
  for(ll i=s-1;i>=0;i--) m+=n/((ll)pow(10,i))-(n/((ll)pow(10,i+1)))*10;
  return m;
}


ll Svec(vector<ll> v){
  ll n=0;
  for(ll i=0;i<v.size();i++) n+=v[i];
  return n;
}


ll GCD(ll a,ll b){
  ll r,tmp;
/*自然数 a > b を確認・入替*/
  if(a<b){
    tmp=a,a=b,b=tmp;
  }
/*ユークリッドの互除法*/
  r=a%b;
  while(r!=0){
    a=b,b=r,r=a%b;
  }
  return b;
}


ll LCM(ll a,ll b){
  ll c=a,d=b,r,tmp;
/*自然数 a > b を確認・入替*/
  if(a<b){
    tmp=a,a=b,b=tmp;
  }
/*ユークリッドの互除法*/
  r=a%b;
  while(r!=0){
    a=b,b=r,r=a%b;
  }
  return c/b*d;
}


ll Factorial(ll n){
  ll m=1;
  while(n>=1) m*=n,n--;
  return m;
}

vector<pair<char,ll>> runlength(string s,vector<pair<char,ll>> p){
  ll x=1;
  if(s.size()==1){
    p.push_back(pair<char,ll>(s[0],1));
    return p;
  }
  for(ll i=0;i<s.size()-1;i++){
    if(s[i]==s[i+1]){
      x++;
      if(i==s.size()-2){
        p.push_back(pair<char,ll>(s[i],x));
      }
    }else{
      p.push_back(pair<char,ll>(s[i],x));
      x=1;
      if(i==s.size()-2){
        p.push_back(pair<char,ll>(s[s.size()-1],x));
      }
    }
  }
  return p;
}



/*↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓*/
int main() {
  IOS;
  string n;
  cin>>n;
  ll ans=0;
  rep(i,n.size()){
    if(n[i]=='2') ans++;
  }
  cout<<ans<<endl;
}

Measured memory_bytes: 256
import java.util.Scanner;
public class Main {
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		long Q = sc.nextInt();
		long H = sc.nextInt();
		long S = sc.nextInt();
		long D = sc.nextInt();
		
		long minOne = Math.min(H * 2, Q * 4);
		minOne = Math.min(minOne, S);
		
		long min = Math.min(D, minOne * 2);
		
		long N = sc.nextLong();
		long ans = min * (N / 2) + minOne * (N % 2);
		
		System.out.println(ans);
	}

}

Measured memory_bytes: 23764
#include <stdio.h>

int	is_all_even(int *nums, int N)
{
	for (int i = 0; i < N; i++)
	{
		if (nums[i] % 2)
			return (0);
	}
	return (1);
}

int	main()
{
	int	N;
	int	nums[201];
	int	count;

	count = 0;
	scanf("%d\n", &N);
	for (int i = 0; i < N; i++)
		scanf("%d ", &nums[i]);
	while (1)
	{
		if (!is_all_even(nums, N))
			break ;
		for (int i = 0; i < N; i++)
			nums[i] /= 2;
		count++;
	}
	printf("%d\n", count);
	return (0);
}

Measured memory_bytes: 128
#include <iostream>
#include <string>
#include <cstring>
#include <fstream>
#include <cmath>
#include <iomanip>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <map>
#include <deque>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <list>
#include <unordered_map>
#include <bitset>
#include <sstream>

typedef  long long ll;
#define mop 1000000007
using namespace std;

int main() {
    

    vector <ll> lis[5];
    for (ll i=0;i<3;i++){
        ll a,b;
        cin >> a >> b;
        lis[a].push_back(b);
        lis[b].push_back(a);
    }
    ll tmp = 0;
    for (ll i=1;i<=4;i++){
        if(lis[i].size() % 2 == 1){
            tmp++;
        }
    }
    if(tmp == 2 or tmp == 0){
        cout << "YES" << endl;
    }else{
        cout << "NO" << endl;
    }
}




Measured memory_bytes: 256
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
    	
		Scanner sc = new Scanner(System.in);
		// 整数の入力
		int a = sc.nextInt();
		
		int intArray[] = new int[4];

		for(int i = 0 ;i < 4;i++){
			intArray[i] = a % 10;
			a = a / 10;
		}
		for(int i = 0 ;i < 3;i++){
			if(intArray[i] == intArray[i+ 1]){
				System.out.println("Bad");
				return ;
			}	
		}

		System.out.println("Good");


	    
   		sc.close();
        return ;

    }
    
}



Measured memory_bytes: 21716
object Main {

  def main(args: Array[String]): Unit = {
    val sc = new java.util.Scanner(System.in)
    val S = sc.next
    var prev = ' '
    for (s <- S) {
      if (prev == s) {
        println("Bad")
        sys.exit
      }
      prev = s
    }

    println("Good")
  }
}

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

int main(){
  int n , x; cin >> n; int cnt = 0;
  for(int i = 1; i <= n; i++){
     cin >> x;
      if(x!=i)cnt++;
  }
  if(cnt > 2){
    cout << "NO\n";
  }
  else{
    cout << "YES\n";
  }
}

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

int x, y;

int main(void){
	while(1){
		scanf("%d %d", &x, &y);
		if( x == 0 && y == 0 ) break;

		if( x > y ) swap(x, y);

		printf("%d %d\n", x, y);
	}

	return 0;
}

Measured memory_bytes: 2684
let kFMax = 3000 in
let kWMax = 30 in
Scanf.scanf " %d %d %d %d %d %d" @@ fun a b c d e f ->
  let water = Array.make (kWMax + 1) false in
  for i = 0 to kWMax do
    for j = 0 to kWMax do
      let w = a * i + b * j in
      if w <= kWMax then water.(w) <- true
    done
  done;
  let sugar = Array.make (kFMax + 1) false in
  for i = 0 to kFMax do
    for j = 0 to kFMax do
      let s = c * i + d * j in
      if s <= kFMax then sugar.(s) <- true
    done
  done;
  let (/>) (a, b) (c, d) = a * d > c * b in
  let ans = ref (0, a * 100) in
  for w = 1 to kWMax do
    if water.(w) then
      for s = 0 to kFMax do
        if sugar.(s) then
          let w_s = w * 100 + s in
          if w_s <= f && w * e >= s then
            if (s, w_s) /> !ans then ans := s, w_s
      done
  done;
  let s, w_s = !ans in Printf.printf "%d %d\n" w_s s

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

#define LL long long
#define REP(i, n) for(int i = 0; i < (int)(n); i++)
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define ALL(x) (x).begin(),(x).end()
const int IINF = 1e9;
const LL LINF = 1e18;
const LL mod = 1e9+7;

int main() {
    LL X, Y;
    cin >> X >> Y;
    if(1 < abs(X - Y)) {
        cout << "Alice" << endl;
    }else{
        cout << "Brown" << endl;
    }
    return 0;
}



Measured memory_bytes: 256
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cctype>
#include <cmath>
#include <cstdint>
#include <cstdio>
#include <cstring>
#include <deque>
#include <fstream>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <vector>
using namespace std;
using ll = long long;
#define fst first
#define snd second

/* clang-format off */
template <class T, size_t D> struct _vec { using type = vector<typename _vec<T, D - 1>::type>; };
template <class T> struct _vec<T, 0> { using type = T; };
template <class T, size_t D> using vec = typename _vec<T, D>::type;
template <class T> vector<T> make_v(size_t size, const T& init) { return vector<T>(size, init); }
template <class... Ts> auto make_v(size_t size, Ts... rest) { return vector<decltype(make_v(rest...))>(size, make_v(rest...)); }
template <class T> inline void chmin(T &a, const T& b) { if (b < a) a = b; }
template <class T> inline void chmax(T &a, const T& b) { if (b > a) a = b; }
/* clang-format on */

int main() {
#ifdef DEBUG
  ifstream ifs("in.txt");
  cin.rdbuf(ifs.rdbuf());
#endif
  int N;
  while (cin >> N) {
    vec<int, 2> grid = make_v(N, N, 0);
    for (int y = 1; y < N; y += 3) {
      for (int x = 0; x < N; x++) {
        if ((y + x) % 2 == 1) {
          grid[y][x] = 1;
        }
      }
    }
    for (int x = 0; x < N; x++) {
      if ((N - 1 + x) % 2 == 1) grid[N - 1][x] = 1;
    }
    for (int y = 0; y < N; y++) {
      if (y % 2 == 1) grid[y][0] = 1;
    }
    vector<int> ys, xs;
    for (int y = 0; y < N; y++) {
      for (int x = 0; x < N; x++) {
        if (grid[y][x]) {
          ys.push_back(y);
          xs.push_back(x);
        }
      }
    }
    cout << ys.size() << endl;
    for (int i = 0; i < ys.size(); i++) {
      cout << ys[i] << " " << xs[i] << endl;
    }
  }
  return 0;
}


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

using namespace std;
long long n, k, p[200005], sum, ans;
int main() {
	cin >> n >> k;
	for (int i = 0; i < n; i++) {
		cin >> p[i];
	}
	for (int i = 0; i < k; i++) {
		sum += p[i];
	}
	ans = sum;
	for (long long i = k; i < n; i++) {
		sum -= p[i - k];
		sum += p[i];
		if (sum > ans) ans = sum;
	}
	ans += k;
	if (ans % 2 == 1) {
		cout << ans / 2 << '.' << 5;
	}
	else {
		cout << ans / 2;
	}
	return 0;
}

Measured memory_bytes: 1792
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(ll i=0;i<n;i++)
#define repl(i,l,r) for(ll i=(l);i<(r);i++)
#define per(i,n) for(ll i=n-1;i>=0;i--)
#define perl(i,r,l) for(ll i=r-1;i>=l;i--)
#define fi first
#define se second
#define pb push_back
#define ins insert
#define pqueue(x) priority_queue<x,vector<x>,greater<x>>
#define all(x) (x).begin(),(x).end()
#define CST(x) cout<<fixed<<setprecision(x)
#define vtpl(x,y,z) vector<tuple<x,y,z>>
#define rev(x) reverse(x);
using ll=long long;
using vl=vector<ll>;
using vvl=vector<vector<ll>>;
using pl=pair<ll,ll>;
using vpl=vector<pl>;
using vvpl=vector<vpl>;
const ll MOD=1000000007;
const ll MOD9=998244353;
const int inf=1e9+10;
const ll INF=4e18;
const ll dy[8]={1,0,-1,0,1,1,-1,-1};
const ll dx[8]={0,-1,0,1,1,-1,1,-1};
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;
}
ll n,m,q,ans=0;
ll a[50],b[50],c[50],d[50];
ll score(vl v){
    ll res=0;
    rep(i,q){
        if(v[b[i]-1]-v[a[i]-1]==c[i])res+=d[i];
    }
    return res;
}
void dfs(vl &v){
    if(v.size()==n){
        chmax(ans,score(v));
        return;
    }
    ll l=v[v.size()-1];
    repl(i,l,m+1){
        vl nv=v;
        nv.pb(i);
        dfs(nv);
    }
}
int main(){
    cin >> n >>m >>q;
    rep(i,q){
        cin >> a[i] >> b[i] >>c[i] >>d[i];
    }
    vl v;v.pb(1);
    dfs(v);
    cout <<ans <<endl;
}

Measured memory_bytes: 3608
H, W = map(int, input().split())
A = [list(map(int, input().split())) for _ in range(H)]
path = []
for i in range(H * W):
    h = i // W
    w = i % W if h % 2 == 0 else (W - i % W - 1)
    path.append((h, w))

ans = []
for i in range(H * W - 1):
    p, n = path[i], path[i + 1]
    if A[p[0]][p[1]] % 2 == 1:
        A[p[0]][p[1]] -= 1
        A[n[0]][n[1]] += 1
        ans.append("{} {} {} {}".format(
            p[0] + 1, p[1] + 1, n[0] + 1, n[1] + 1))

print(len(ans))
for a in ans:
    print(a)


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


int main(){
    ll N;cin>>N;
    vector<ll> a;
    a.push_back(1);
    rep(i,0,10){
        if(pow(6,i+1)<=100000)a.push_back((ll)pow(6,i+1));
        if(pow(9,i+1)<=100000)a.push_back((ll)pow(9,i+1));
    }
    ll dp[100010];
    rep(i,0,100010)dp[i]=99999999999;
    dp[0]=0;
    rep(i,0,a.size()){
        for(ll j=0;j+a.at(i)<=N;j++){
            dp[j+a.at(i)]=min(dp[j+a.at(i)],dp[j]+1);
        }
    }
    cout<<dp[N]<<endl;
}







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

using namespace std;

#define FOR(i, a, b) for(ll i = (a); i < (b); ++i)
#define FORR(i, a, b) for(ll i = (a); i > (b); --i)
#define REP(i, n) for(ll i = 0; i < (n); ++i)
#define REPR(i, n) for(ll i = n; i >= 0; i--)
#define FOREACH(x, a) for(auto &(x) : (a))
#define VECCIN(x)                                                              \
    for(auto &youso_ : (x)) cin >> youso_
#define mp make_pair
#define bitcnt __builtin_popcount
#define SZ(x) ((ll)(x).size())
#define All(a) (a).begin(), (a).end()
template <typename T = long long> inline T IN() {
    T x;
    cin >> x;
    return (x);
}
inline void CIN() {}
template <class Head, class... Tail>
inline void CIN(Head &&head, Tail &&... tail) {
    cin >> head;
    CIN(move(tail)...);
}
#define CINT(...)                                                              \
    int __VA_ARGS__;                                                           \
    CIN(__VA_ARGS__)
#define LCIN(...)                                                              \
    ll __VA_ARGS__;                                                            \
    CIN(__VA_ARGS__)
#define SCIN(...)                                                              \
    string __VA_ARGS__;                                                        \
    CIN(__VA_ARGS__)
#define Yes(a) cout << (a ? "Yes" : "No") << "\n"
#define YES(a) cout << (a ? "YES" : "NO") << "\n"

typedef long long ll;
typedef unsigned long long ul;
typedef vector<int> V;
typedef vector<ll> VL;
typedef pair<ll, ll> PL;
typedef priority_queue<ll> PQ;
typedef priority_queue<ll, V, greater<ll>> PQG;

const int INF = 1e9;
const int MOD = 1e9 + 7;
// const int MOD = 998244353;
const ll LINF = 1e18;

ll N, M;
vector<VL> G;
vector<bool> went;
VL d;

signed main() {
    cin >> N;
    G.resize(N);
    d.resize(N, LINF);
    REP(i, N) {
        LCIN(u, k);
        REP(i, k) { G[u - 1].emplace_back(IN() - 1); }
    }
    queue<ll> q;
    q.emplace(0);
    d[0] = 0;
    while(!q.empty()) {
        ll now = q.front();
        q.pop();
        FOREACH(to, G[now]) {
            if(d[to] > d[now] + 1) {
                d[to] = d[now] + 1;
                q.emplace(to);
            }
        }
    }
    REP(i, N) { cout << i + 1 << " " << (d[i] == LINF ? -1 : d[i]) << "\n"; }
    return 0;
}



Measured memory_bytes: 3164
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct node
{
    ll x;
    ll h;
    bool operator < (const node &nex) {
        return x < nex.x;
    }
}mon[200010];
struct atk
{
    ll r;
    ll ak;
    bool operator > (const atk &nex) {
        return r < nex.r;
    }
};

int main()
{
    int i, j, k;
    queue<atk> p;
    ll H, N;
    ll D, A;
    ll ans = 0;
    cin >> N >> D >> A;
    for(i = 0; i < N; i++) {
        cin >> mon[i].x >> mon[i].h;
    }
    sort(mon, mon+N);
    ll xxx = 0;
    for(i = 0; i < N; i++) {
        while(!p.empty() && p.front().r < mon[i].x) {
            atk tmp = p.front();
            p.pop();
            xxx -= tmp.ak;
        }
        if(mon[i].h-xxx > 0) {
            ans += (mon[i].h-xxx+A-1) / A;
            p.push(atk{mon[i].x+2*D, (mon[i].h-xxx+A-1) / A * A});
            xxx += (mon[i].h-xxx+A-1) / A * A;
        }
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 4992
#include <algorithm>
#include <climits>
#include <iostream>
#include <string>
#include <utility>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <iomanip>

using namespace std;
using ll = long long int;

template <class T> ostream &operator<<(ostream &os, vector<T> &v) {
  for (auto i = v.begin(); i != v.end(); i++) {
    os << *i << " ";
  }
  return os;
}



int main(){
  ll h, w, k;
  cin>>h>>w>>k;
  vector<string> v(h);
  vector<vector<ll>> ans;
  for(ll i=0; i<h; i++) {
    cin>>v[i];
    vector<ll> vv(w);
    ans.push_back(vv);
  }
  ll n = 1;
  vector<pair<ll, ll>> st;
  for(ll i=0; i<h; i++) {
    for(ll j=0; j<w; j++) {
      if(v[i][j] == '#') {
	ans[i][j] = n++;
	st.push_back(make_pair(i, j));
      } else {
	ans[i][j] = 0;
      }
    }
  }

  for(auto p: st) {
    ll x = p.second;
    ll y = p.first;
    ll min_x = x;
    ll min_y = y;
    ll max_x = x;
    ll max_y = y;
    for(; min_x >= 0 and
	  (ans[y][min_x] == 0 or ans[y][min_x] == ans[y][x]); min_x--);
    for(; min_y >= 0 and
	  (ans[min_y][x] == 0 or ans[min_y][x] == ans[y][x]); min_y--);
    min_x++;
    min_y++;
    bool ff = false;
    for(; max_x<w; max_x++) {
      bool f = false;
      for(ll j = y; j>=min_y; j--) {
	if(ans[j][max_x]!=0 and ans[j][max_x]!=ans[y][x]) {
	  f = true;
	  break;
	}
      }
      if(f) {
	max_x--;
	ff = true;
	break;
      }
    }
    if(!ff)
      max_x--;
    ff = false;
    for(; max_y<h; max_y++) {
      bool f = false;
      for(ll j = min_x; j<=max_x; j++) {
	if(ans[max_y][j]!=0 and ans[max_y][j]!=ans[y][x]) {
	  f = true;
	  break;
	}
      }
      if(f) {
	max_y--;
	ff = true;
	break;
      }
    }
    if(!ff)
      max_y--;
    for(ll i = min_y; i<=max_y; i++) {
      for(ll j = min_x; j<=max_x; j++) {
	ans[i][j] = ans[y][x];
      }
    }
  }

  for(int i=0; i<h; i++) {
    std::cout << ans[i] << std::endl;
  }
  
  return 0;
}



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

//repetition
#define FOR(i,a,b) for(ll i=(a);i<(b);++i)
#define rep(i, n) for(ll i = 0; i < (ll)(n); i++)

//container util
#define all(x) (x).begin(),(x).end()

//typedef
typedef long long ll;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<ll> VLL;
typedef vector<VLL> VVLL;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef pair<ll, ll> PLL;

//const value
//const ll MOD = 1e9 + 7;
//const int dx[] = {0,1,0,-1};//{0,0,1,1,1,-1,-1,-1};
//const int dy[] = {1,0,-1,0};//{1,-1,0,1,-1,0,1,-1};

//conversion
inline int toInt(string s) {int v; istringstream sin(s);sin>>v;return v;}
inline ll toLL(string s) {ll v; istringstream sin(s);sin>>v;return v;}
template<class T> inline string toString(T x) {ostringstream sout;sout<<x;return sout.str();}

template <typename T1, typename T2> 
inline bool chmax(T1 &a, T2 b) {
  return a < b && (a = b, true);
}

template <typename T1, typename T2>
inline bool chmin(T1 &a, T2 b) {
  return a > b && (a = b, true);
}


ll dp[101010][2][2][4] ;// pos, less , start, notK
int main(){
  string A;
  cin >> A;
  ll n = A.length();
  ll K;
  cin >> K;
  dp[0][0][0][0] = 1;
  rep(i,n) rep(j,2) rep(k,2) rep(notK,4) {
    int lim;
    if(j) lim = 9;
    else  lim = A[i] - '0';

    rep(d, lim + 1){
      if(k == 0){
        if(d==0) dp[i+1][j || d < lim][0][notK] += dp[i][j][k][notK];
        else     dp[i+1][j || d < lim][1][notK+1] += dp[i][j][k][notK];
      }else{
        if(d!=0){
          if(notK + 1 < 4)dp[i+1][j || d < lim][k][notK+1] += dp[i][j][k][notK];
        }else{
          dp[i+1][j || d < lim][k][notK] += dp[i][j][k][notK];
        }
      }
    }
  }
  int ans = 0;
  rep(j,2) ans += dp[n][j][1][K];
  cout << ans << endl;
  return 0;
}



Measured memory_bytes: 256
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {


		Scanner sc = new Scanner(System.in);
		String[] input = sc.next().split("");
		int hug = 0;
		for(int i = 0; i < (input.length/2);i++) {
			if(!input[i].equals(input[input.length-1 -i])) {
				hug++;
			}
		}
		System.out.println(String.valueOf(hug));

	}

}

Measured memory_bytes: 23124
import java.util.Scanner;

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

	if(a==b){
		System.out.println("a == b");
	}else if(a>b){
		System.out.println("a > b");
	}else{
		System.out.println("a < b");
	}

	}

}

Measured memory_bytes: 26040
n=input()
S=['S 1','S 2','S 3','S 4','S 5','S 6','S 7','S 8','S 9','S 10','S 11','S 12','S 13']
H=['H 1','H 2','H 3','H 4','H 5','H 6','H 7','H 8','H 9','H 10','H 11','H 12','H 13'] 
C=['C 1','C 2','C 3','C 4','C 5','C 6','C 7','C 8','C 9','C 10','C 11','C 12','C 13']
D=['D 1','D 2','D 3','D 4','D 5','D 6','D 7','D 8','D 9','D 10','D 11','D 12','D 13']
cards=[S,H,C,D]
for i in range(n):
  exist=raw_input()
  if 'S' in exist:
    cards[0].remove(exist)
  if 'H' in exist:
    cards[1].remove(exist)
  if 'C' in exist:
    cards[2].remove(exist)
  if 'D' in exist:
    cards[3].remove(exist)
for j in range(4):
  for i in cards[j]:
    print i

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

int main() {
	int n, m;
	cin >> n >> m;
	int count_ball[100000];
	for (int i = 0; i < n; ++i)count_ball[i] = 1;
	bool red[100000] = { false };
	red[0] =  true;
	for (int i = 0; i < m; ++i) {
		int x, y;
		cin >> x >> y;
		--x; --y;
		if (red[x]) {
			--count_ball[x];
			++count_ball[y];
			red[y] = true;
			if (count_ball[x] == 0) {
				red[x] = false;
			}
		}
		else {
			--count_ball[x];
			++count_ball[y];
		}
	}
	int ans = 0;
	for (bool i : red) {
		ans += i ? 1 : 0;
	}
	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 768
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int a = sc.nextInt();
        int b = sc.nextInt();
        
        String result = "";
        for (int i = 0; i < Math.max(a,b); i++) {
            result += Math.min(a,b);
        }
        System.out.println(result);
    }
}

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

struct Node {
	int key;
	struct Node* parent;
	int degree;
	int depth;
	int height;
	char type[15];
	
	int * child_list;
};
typedef struct Node * NodePointer;


void serach_depth (NodePointer ,int  ,NodePointer[]);

int main (){
	int n;
	scanf("%d\n",&n);
	
	//setting part
	NodePointer array [n];
	for (int i = 0; i < n;i++)
	{
		array[i] = (NodePointer) malloc (sizeof(struct Node));
		array[i]->parent = NULL;
		array[i]->degree = 0;
		strcpy(array[i]->type,"internal node");
	}
	
	//input part
	for (int i = 0; i < n;i++)
	{
		int id;
		scanf("%d ",&id);
		array[id]->key = id;
		int child_num;
		scanf("%d" ,&child_num);
		array[id]->child_list = (int *) malloc (child_num * sizeof(int));
		
		if ( child_num == 0){
			strcpy(array[id]->type ,"leaf");
		}else {
			for (int j = 0; j < child_num; j++){
				int child_id;
				scanf(" %d" ,&child_id);
				array[id]->child_list[j] = child_id;
				array[child_id]->parent = array[id];
				array[id]->degree++;
			}
		}

	}
	
	//search part
		for (int i = 0; i < n;i++)
	{
		if(array[i]->parent == NULL) {
			strcpy(array[i]->type ,"root");
			serach_depth(array[i],0 ,array); break;
		}
	}
	
	//print part
	for (int i = 0; i < n ;i++){
		printf("node %d: ",i);
		if (array[i] -> parent != NULL){
		printf("parent = %d, ",array[i]->parent->key);
		}else {
			printf("parent = -1, ");
		}
		printf("depth = %d, %s, [",array[i]->depth,array[i]->type );
		for ( int j = 0; j < array[i]->degree; j++){
			printf("%d" ,array[i]->child_list[j]);
			if ( j + 1 != array[i]->degree){printf(", ");}
		}
		printf("]\n");
	}
	
	return 0;
}

void serach_depth (NodePointer tag,int dep , NodePointer array[]){
	tag->depth = dep;
	if ( tag->degree == 0 ){tag->height = 0; return;}
	for ( int j = 0; j < tag->degree ; j++){
		serach_depth(array [ (tag->child_list[j]) ] , dep + 1 ,array);
	}
}



Measured memory_bytes: 12268
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		final Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		long x = sc.nextLong();
		long[] candy = new long[100000];
		for(int i = 0; i < n; i++) {
			candy[i] = sc.nextLong();
		}
		long ans = 0L;
		for(int i = 1; i < n; i++) {
			if(candy[i-1]+candy[i] > x) {
				ans += candy[i-1]+candy[i] - x;
				if(candy[i-1]+candy[i] - x > candy[i]) {
					candy[i] = 0;
				} else {
					candy[i] = x - candy[i-1];
				}
			}
		}
		System.out.println(ans);
	}
}

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

int main(){
    int n,id;
    int *H;
    
    scanf("%d",&n);
    H = malloc(sizeof(int)*(n+1));
    
    for(id=1;id<=n;id++){
        scanf("%d",&H[id]);
    }
    
    for(id=1;id<=n;id++){
        printf("node %d: key = %d, ",id,H[id]);
        if(id/2>0){
            printf("parent key = %d, ",H[id/2]);
        }
        if(id*2<=n){
            printf("left key = %d, ",H[id*2]);
        }
        if(id*2+1<=n){
            printf("right key = %d, ",H[id*2+1]);
        }
        printf("\n");
    }
    
    return 0;
}



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

flag = 1

for i in range(n):
    if a[i] % 2 == 0:
        if a[i] % 3 == 0 or a[i] % 5 == 0:
            continue
        else:
            flag = 0

if flag == 0:
    print("DENIED")
elif flag == 1:
    print("APPROVED")

Measured memory_bytes: 3060
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
 
#define int long long
#define ull unsigned long long
#define ld long double
#define rep(a) rep1(i,a)
#define rep1(i,a) rep2(i,0,a)
#define rep2(i,b,a) for(int i=(b); i<((int)(a)); i++)
#define rep3(i,b,a) for(int i=(b); i>=((int)(a)); i--)
#define all(a) a.begin(),a.end()
#define pii pair<int,int>
#define pb push_back
#define mp make_pair
#define sz(a) ((int)a.size())
#define pow2(x) (1ll<<(x))
#define print0(a) cout << (a) << ' '
#define print1(a) cout << (a) << '\n'
#define print2(a,b) cout << (a) << ' ',print1(b)
#define print3(a,b,c) cout << (a) << ' ',print2(b,c)
#define print4(a,b,c,d) cout << (a) << ' ',print3(b,c,d)
#ifdef i_am_noob
#define debug(a) print1(a)
#else
#define debug(a) 
#endif
#define ordered_set tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>
 
using namespace std;
using namespace __gnu_pbds;
 
const int Mod=1000000007,Mod2=998244353;
const int MOD=Mod2;
 
inline int add(int a, int b){return (a+b>=MOD?a+b-MOD:a+b);}
inline int sub(int a, int b){return (a+MOD-b>=MOD?a-b:a+MOD-b);}
int Pow(int a, int b){
	if(!b) return 1;
	int tmp=Pow(a*a%MOD,b>>1);
	return (b&1?tmp*a%MOD:tmp);
}
inline int inverse(int n){return Pow(n,MOD-2);}
 
const int maxn=55;
//i_am_noob
int k,x;

signed main(){
	ios_base::sync_with_stdio(0),cin.tie(0);
	cin >> k >> x;
	print1(500*k>=x?"Yes":"No");
	return 0;
}

Measured memory_bytes: 256
#include <iostream>

using namespace std;

int main()
{
    int n,ac=0,wa=0,tle=0,re=0;
    cin>>n;
    string s;
    for(int i=0;i<n;i++)
    {
        cin>>s;
        if(s=="AC")
            ac++;
        else if(s=="WA")
            wa++;
        else if(s=="TLE")
            tle++;
        else if(s=="RE")
            re++;
    }
    cout<<"AC x "<<ac<<endl;
    cout<<"WA x "<<wa<<endl;
    cout<<"TLE x "<<tle<<endl;
    cout<<"RE x "<<re<<endl;
    return 0;
}


Measured memory_bytes: 3528
#include<bits/stdc++.h>
#define inf 1000000009
using namespace std;
typedef long long ll;

ll dp[100004];
ll solve(ll height[], ll n, ll k) {
	if (dp[n] != inf)
		return dp[n];
	else {
		if (n <= 1)
			return 0;
		else {
			ll val = 0;
			val = (n > k) ? (k) : (n - 1);
			for (ll i = 1; i <= val; i++)
			{
				ll ans1 = abs(height[n] - height[n - i]);
				dp[n] = min(dp[n], ans1 + solve(height, n - i, k));
			}

			return dp[n];
		}
	}
}
int main() {
// #ifndef ONLINE_JUDGE
// 	freopen("input.txt", "r", stdin);
// 	freopen("output.txt", "w", stdout);
// #endif
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	ll n, k;
	cin >> n >> k;

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

	for (ll i = 1; i <= 100004; i++)
		dp[i] = inf;
	cout << solve(height, n, k) << endl;
	return 0;
}

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

int main(){
    long N, M;
    cin >> N >> M;
    vector<pair<long, long>> S(N);
    for(auto& i : S)cin >> i.first >> i.second;
    sort(S.begin(), S.end());
    long ans(0);
    for(const auto& i : S){
        if(M < i.second){
            ans += M * i.first;
            break;
        }
        ans += i.first * i.second;
        M -= i.second;
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 1792
dy = [-1, 1, 0, 0, -1, 1, -1, 1]
dx = [ 0, 0,-1, 1, -1, 1,  1,-1]
h, w = map(int, input().split())
S = [[*input()] for _ in range(h)]
for i in range(h):
    for j in range(w):
        if S[i][j] == '#': continue
        c = 0
        for k in range(8):
            y = i + dy[k]; x = j + dx[k]
            if y<0 or h<=y or x<0 or w<=x: continue
            if S[y][x] == '#': c += 1
        S[i][j] = str(c)
print(*map(''.join, S), sep='\n')


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


int main(){
  int X;
  int Y;
  cin >> X >> Y;

  if(X * 2 > Y || Y > X * 4){
    cout << "No";
    return 0;
  }

  for(int kame=0; kame <= X; ++kame){
    int tsuru = X - kame;
    int leg = tsuru * 2 + kame * 4;
    if(Y == leg){
      cout << "Yes";
      return 0;
    }
    if(leg > Y){
      cout << "No";
      return 0;
    }
  }
  cout << "No";
  return 0;
}


Measured memory_bytes: 3632
#include<stdio.h>
#define true 1
#define false 0

int n,A[2000];

int solve(int i,int m){
    int res;
    if(m==0)return true;
    if(i>=n)return false;
    res=solve(i+1,m) || solve(i+1,m-A[i]);
    return res;
}

int main(){
    int m,i,x,y;
    scanf("%d",&n);
    for(i=0;i<n;i++)scanf("%d",&A[i]);
    scanf("%d",&m);
    for(i=0;i<m;i++){
        scanf("%d",&x);
        y=solve(0,x);
        if(y==true)printf("yes\n");
        else printf("no\n");
    }
    return 0;
}



Measured memory_bytes: 2048
#include<iostream>
#include<string>
#include<cstdio>
#include<vector>
#include<cmath>
#include<algorithm>
#include<functional>
#include<iomanip>
#include<queue>
#include<ciso646>
#include<random>
#include<map>
#include<set>
#include<complex>
#include<bitset>
#include<stack>
#include<unordered_map>
#include<utility>
#include<cassert>
using namespace std;

typedef long long ll;

typedef unsigned long long ul;
typedef unsigned int ui;
const ll mod = 998244353;
typedef long double ld;
typedef complex<ld> Point;
const ll INF = mod * mod;
typedef pair<int, int> P;
#define stop char nyaa;cin>>nyaa;
#define rep(i,n) for(int i=0;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define Rep(i,sta,n) for(int i=sta;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define per1(i,n) for(int i=n;i>=1;i--)
#define Rep1(i,sta,n) for(int i=sta;i<=n;i++)
const ld eps = 1e-9;
const ld pi = acos(-1.0);
typedef pair<ld, ld> LDP;
typedef pair<ll, ll> LP;
typedef vector<int> vec;
typedef vector<string> svec;

bool eq(ld a, ld b) {
	return (abs(a - b) < eps);
}

class Line {
public:
	Point a, b;
};
class Circle {
public:
	Point p; ld r;
};

ld dot(Point a, Point b) {
	return real(conj(a)*b);
}
ld cross(Point a, Point b) {
	return imag(conj(a)*b);
}
Point proj(Line l, Point p) {
	ld t = dot(p - l.a, l.a - l.b) / norm(l.a - l.b);
	return l.a + t * (l.a - l.b);
}
ld dist_lp(Line l, Point p) {
	return abs(p - proj(l, p));
}

int ccw(Point a, Point b, Point c) {
	b -= a; c -= a;
	if (cross(b, c) > eps)return 1;//a,b,cが反時計回り
	if (cross(b, c) < -eps)return -1;//a,b,cが時計回り
	if (dot(b, c) < 0)return 2;//c,a,bの順に一直線
	if (norm(b) < norm(c))return -2;//a,b,cの順に一直線
	return 0;//a,c,bの順に一直線
}
bool isis_ll(Line l, Line m) {
	return !eq(cross(l.b - l.a, m.b - m.a), 0);
}
Point is_ll(Line s, Line t) {
	Point sv = s.b - s.a; Point tv = t.b - t.a;
	return s.a + sv * cross(tv, t.a - s.a) / cross(tv, sv);
}

//counterclockwise
struct polygon {
private:
	vector<Point> p;
public:
	polygon(vector<Point> &v) {
		p = v;
	}
	//f=true:left-side
	void convex_cut(Line &l) {
		vector<Point> nex;
		rep(i, p.size()) {
			Point a = p[i], b = p[(i + 1) % p.size()];
			if (ccw(l.a, l.b, a) != -1)nex.push_back(a);
			if (ccw(l.a,l.b,a)*ccw(l.a,l.b,b)<0) {
				nex.push_back(is_ll({ a,b }, l));
			}
		}
		p = nex;
	}
	bool query() {
		return p.size();
	}
};
const ld mn = 100000;
int n;
void solve() {
	vector<Point> v = { {mn,mn},{-mn,mn},{-mn,-mn},{mn,-mn} };
	polygon p(v);
	vector<Point> u(n);
	rep(i, n) {
		ld a, b; cin >> a >> b;
		u[i] = { a,b };
	}
	rep(i, n) {
		Line l = { u[i],u[(i + 1) % n] };
		p.convex_cut(l);
	}
	int ans = p.query();
	cout << ans << endl;
}

signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	//cout << fixed << setprecision(9);
	//init();
	while (cin >> n, n) {
		solve();
	}
	//solve();
	//stop
	return 0;
}



Measured memory_bytes: 3308
#include <stdio.h>
#define Rep(i,a,n)for(int i=(int)(a);i<(int)(n);i++)
#define rep(i,n)Rep(i,0,n)
#define N 200010

int main() {
	int n, a[N], b[N] = { 0 }, c[N] = { 0 }; long long k;
	scanf("%d %lld", &n, &k);
	Rep(i, 1, n + 1)scanf("%d", &a[i]);
	int ch = 1, start, end;
	Rep(i, 1, N+10) {
		if (b[ch]!=0){ start = b[ch]; end = i; break; }
		b[ch] += i;
		ch = a[ch];
    }
	c[0]=ch;
	Rep(i,1,end-start+1) {
		c[i] = a[ch];
		ch = a[ch];
	}
	if (k<=start) {
		ch=1;
		rep(i,k) {
			ch = a[ch];
		}
		printf("%d",ch);
	}
	else if(end-start==1)printf("%d", ch);
	else{
		k -= start-1;
		k%=(end-start);
		printf("%d",c[k]);
	}
}

Measured memory_bytes: 4036
import java.util.*;
import java.util.regex.Matcher;
import java.util.regex.Pattern;

public class Main{
    static final Scanner sc = new Scanner(System.in);
    public static void main(final String[] args){
        final Pattern p = Pattern.compile("R+");
        final Matcher m = p.matcher(sc.next());
        if (m.find()){
            System.out.println(m.group().length());
        }else{
            System.out.println(0);
        }
    }
}


Measured memory_bytes: 35580
n, k = map(int, input().split())
arr = [int(x) for x in input().split()]

dp = [False] * (k+1)

for stones in range(k+1):
    for num in arr:
        # If i'm choosing num stones and dp[stones - num] is false then opponent will loose
        if stones >= num and not dp[stones-num]:
            dp[stones] = True

ans = "First" if dp[k] else "Second"
print(ans)

Measured memory_bytes: 3828
#include <bits/stdc++.h>
#define int long long
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
using namespace std;
constexpr int MOD = 1000000007;
constexpr int INF = numeric_limits<int>::max() / 2;
typedef pair<int,int> P;
using Graph = vector<vector<int>>;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
const double PI = acos(-1.0);
// cout << fixed << setprecision(14);
 
signed main(){
	cin.tie(nullptr);
	ios::sync_with_stdio(false);

    int N;
    cin >> N;
    int A[N], B[N], C[N];
    rep(i,N) cin >> A[i];
    rep(i,N) cin >> B[i];
    rep(i,N) cin >> C[i];
    priority_queue<int, vector<int>, greater<int>> que1; 
    priority_queue<int> que2;
    int sum1{}, sum2{};
    rep(i,N){
        que1.push(A[i]);
        sum1 += A[i];
    }
    rep(i,N){
        que2.push(C[i]);
        sum2 += C[i];
    }
    int ans = sum1 - sum2;
    int W1 = sum1, W2 = sum2;
    int cnt1[N], cnt2[N];
    rep(i,N){
        sum1 += B[i];
        que1.push(B[i]);
        sum1 -= que1.top();
        que1.pop();
        cnt1[i] = sum1;
    }
    rep(i,N){
        sum2 += B[N-1-i];
        que2.push(B[N-1-i]);
        sum2 -= que2.top();
        que2.pop();
        cnt2[N-1-i] = sum2;
    }
    chmax(ans, W1-cnt2[0]);
    chmax(ans, cnt1[N-1]-W2);
    rep(i,N-1){
        chmax(ans, cnt1[i]-cnt2[i+1]);
    }
    cout << ans << endl;
}

Measured memory_bytes: 5876
import re
s = input()
first_len = len(s)

ten_3_zo = "0" * 10 * 10 * 10 + "1" * 10 * 10 * 10
ten_3_oz = "1" * 10 * 10 * 10 + "0" * 10 * 10 * 10

ten_1_zo = "0" * 10 + "1" * 10
ten_1_oz = "1" * 10 + "0" * 10


while True:
    s = s.replace(ten_3_zo,"").replace(ten_3_oz,"")
    s = s.replace(ten_1_zo,"").replace(ten_1_oz,"")
    s = s.replace("01","").replace("10","")
    if not re.search('01|10',s):
        break

print(first_len - len(s))

Measured memory_bytes: 3572
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vi=vector<int>;
using vvi=vector<vi>;
using vl=vector<ll>;
using vvl=vector<vl>;
using vb=vector<bool>;
using vvb=vector<vb>;
using vc=vector<char>;
using vvc=vector<vc>;
using pii = pair<int,int>;
using pil = pair<int,ll>;
using pli = pair<ll,int>;
using pll = pair<ll,ll>;
using tiii = tuple<int,int,int>;
using vpii = vector<pii>;
using vpil = vector<pil>;
using vpli = vector<pli>;
using vpll = vector<pll>;

#define rep(i, n) for(int i=0;i<(int)n;i++)
#define rep2(i, s, n) for(int i=(s);i<(int)n;i++)
int INF=1e9+7;

int main() {
  int N;
  cin >> N;
  ll ans=0;
  rep(i,N-1) {
    ll u,v;
    cin >> u >> v;
    if(u>v) swap(u,v);
    ans-=u*(N-v+1);
  }

  rep2(i,1,N+1) ans+=(ll)i*(N-i+1);
  cout << ans << endl;
}

Measured memory_bytes: 3580
#include <bits/stdc++.h>
#include <cmath>
#include <map>
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define been(ix) (ix).begin(),(ix).end()
using namespace std;
typedef long long ll; 
typedef vector<int> vi;
typedef vector<long long> vl;
const ll INFL = 1e18;
const int INF = 1001001001; 
typedef pair<int,int> P;
#define foreach(ix,i) for(auto& (ix) : (i))
typedef long double ld;
const int mod =1000000007;
int main(){
  int n ,x,y;
  cin>>n>>x>>y;
  vi ans(n+1,0);
  for(int i = 1;i<=n;i++){
    for(int j=i+1;j<=n;j++){
      ans[min(j-i,abs(x-i)+abs(j-y)+1)]++;
    }
  }
  rep(k,n){
    if(k==0)continue;
    cout<<ans[k]<<endl;
  }
}

Measured memory_bytes: 256
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.util.Scanner;

public class Main {

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

//    Scanner cin = new Scanner(new FileReader("input.txt"));
    Scanner cin = new Scanner(System.in);

    String s = cin.next();
    int win = 0;
    int lose = 0;
    for (int i=0;i<s.length();i++) {
      if (s.charAt(i)=='o'){
        win++;
      }
      else if (s.charAt(i)=='x'){
        lose++;
      }

      if (lose>=8) {
        System.out.println("NO");
        return;
      }
    }

    System.out.println("YES");

  }

}

Measured memory_bytes: 22100
#include <bits/stdc++.h>
using namespace std;
#define ll long long
ll aarr[100010], barr[100010], carr[100010];
ll ans = 0 ;
int x , y , a ,b , c ;
int main ()
{
cin >> x >> y >> a >> b >> c ;
for (int i=0 ; i<a; i++ )cin >> aarr[i];
for (int i=0 ; i<b; i++ )cin >> barr[i];
for (int i=0 ; i<c; i++ )cin >> carr[i];
sort(aarr,aarr+a,greater<ll>());
sort(barr,barr+b,greater<ll>());
sort(carr,carr+c,greater<ll>());

for (int i = 0 ; i < x ; i++)ans+=aarr[i];
for (int i = 0 ; i < y ; i++)ans+=barr[i];
int i=x-1 , j=y-1;
for (int k =0; k <c ; k++ ){
    if (i>=0 && j>=0){
        if (carr[k]<=aarr[i] && carr[k]<=barr[j])break;
        else if (min(carr[k],min(aarr[i],barr[j]))!=carr[k]){
                ans-=min(aarr[i],barr[j]); ans+=carr[k];
                if (aarr[i]>barr[j])j--;
                else i--;
        }
        else break;
        }
    else if (i<0 && j >= 0){
        if (carr[k]>barr[j]){ans -= barr[j]; ans+=carr[k];j--;}
        else break;
    }
    else if (i>=0 && j<0 ){
        if (carr[k]>aarr[i]){ans -= aarr[i]; ans+=carr[k];i--;}
        else break;
    }
    else break;
}
cout << ans ;
}


Measured memory_bytes: 2560
#include <iostream>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
int main(){
	int plane[5][5];
	int x,y,mx,n;
	bool flag;
	cin >> n;
	
	while(n--){
		rep(i,5)rep(j,5){
			cin >> plane[i][j];
		}
		mx = 0;
		rep(i,5)rep(j,5){
			rep(y,5)rep(x,5){
				if( j+x > 4 || i+y > 4 )continue;
				flag = true;
				rep(Y,i+1)rep(X,j+1)
					if(!plane[y+Y][x+X])flag = false;
				if(flag)mx = max( mx , (i+1)*(j+1) );
			}
		
		}
		cout << mx << endl;
	}
}

Measured memory_bytes: 0
def main():
    n,*a=map(int,open(0).read().split())
    m=n*-~n//2+1>>1
    ng=max(a)+1
    ok=0
    while ng-ok>1:
        mid=ok+ng>>1
        b=[1]+[0]*n*2
        c=d=s=0
        for t in a:
            if t>=mid:
                c+=1
                d+=b[c]+1
            else:
                d-=b[c]-1
                c-=1
            b[c]+=1
            s+=d
        if s>=m:ok=mid
        else:ng=mid
    print(ok)
main()

Measured memory_bytes: 14864