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

int main() {
	int n;
	bool card[52];
	cin >> n;
	for(int i = 0; i < 52; i++) card[i] = 0;
	for(int i = 0; i < n; i++){
		char c;
		int a;
		cin >> c >> a;
		if(c == 'S') card[a-1] = 1;
		else if(c == 'H') card[13+a-1] = 1;
		else if(c == 'C') card[26+a-1] = 1;
		else card[39+a-1] = 1;
	}
	for(int i = 0; i < 52; i++){
		if(!card[i]){
			if(i / 13 == 0) cout << "S " << i%13+1 << endl;
			else if(i / 13 == 1) cout << "H " << i%13+1 << endl;
			else if(i / 13 == 2) cout << "C " << i%13+1 << endl;
			else cout << "D " << i%13+1 << endl;
		}
	}
	return 0;
}


Measured memory_bytes: 3080
a, b = map(int, input().split())
if a == b:
    print(a)
else:
    a -= 1
    if a%2 == 0:
        fa = (a//2)%2 ^ a
    else:
        fa = ((a+1)//2)%2
    if b%2 == 0:
        fb = (b//2)%2 ^ b
    else:
        fb = ((b+1)//2)%2
    print(fb ^ fa)


Measured memory_bytes: 9168
#pragma region header
#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
#include<atcoder/all>
using namespace std;
using namespace atcoder;
#define int long long
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rep1(i, n) for (int i = 1; i <= (int)(n); i++)
#define rev(i, n) for(int i = (int)(n - 1); i >= 0; i--)
#define rev1(i, n) for(int i = (int)(n); i > 0; i--)
#define pb push_back
#define all(v) (v).begin(), (v).end()
#define resort(v) sort((v).rbegin(), (v).rend())
#define vi vector<int>
#define vvi vector<vector<int>>
#define vc vector<char>
#define vvc vector<vector<char>>
#define vb vector<bool>
#define vvb vector<vector<bool>>
using ll = long long;
using P = pair<int, int>;
/* ----------------よく使う数字や配列----------------- */
int dx[] = {1,0,-1,0};
int dy[] = {0,1,0,-1};
constexpr ll mod = 1e9+7;
constexpr int inf = INT32_MAX/2;
constexpr ll INF = LLONG_MAX/2;
constexpr long double eps = DBL_EPSILON;
constexpr long double pi = 3.141592653589793238462643383279;
/* ----------------------end----------------------- */

/* --------------------テンプレート------------------ */
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;
}
/* ----------------------end----------------------- */

/* --------------------ライブラリ-------------------- */
ll fact(int i) {       //階乗
    if (i == 0) return 1;
    return (fact(i - 1)) * i % mod;
}
ll gcd(ll a, ll b) {        //最大公約数
    if(b == 0) return a;
    return gcd(b, a % b); 
}
ll lcm(ll a, ll b) {      //最小公倍数
    return a / gcd(a, b) * b ;
}
int keta(ll n) {        //桁数を求める
    if(n == 0) return 1;
    int count = 0;
    while(n != 0) {
        n /= 10;
        count++;
    }
    return count;
}
ll ketasum(ll n) {    //各桁の和
    ll sum = 0;
    while(n != 0) {
        sum += n % 10;
        n /= 10;
    }
    return sum;
}
bool isprime(int n) { //素数判定
    if(n==1)return false;
    if(n==2)return true;
    for(int i = 2;i<=sqrt(n);i++) {
        if(n%i==0) return false;
    }
    return true;
}
/* ----------------------end----------------------- */
#pragma endregion
int op(int a,int b) {return max(a,b);}
int e() {return 0;}
signed main() {
    int n,k;cin >> n >> k;
    vi v(n);
    rep(i, n) cin >> v[i];
    segtree<int,op,e> dp(300300);
    rep(i, n) {
        int x = v[i];
        int l = max(0LL,x-k),r=min(300300LL,x+k+1);
        dp.set(x,dp.prod(l,r)+1);
    }
    cout << dp.prod(0,300300) << endl;
    return 0;
}

Measured memory_bytes: 16304
#include <iostream>
#include <sstream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cctype>
#include <cstring>
#include <climits>
#include <iomanip>
#include <bitset>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <list>
#include <map>

using namespace std;

const long long inf = (int) 1e18;
const int N = 3005;

int n;
double dp[N][N];
double p[N];

int main() {
  cin >> n;
  for (int i = 1; i <= n; i++) {
    cin >> p[i];
  }
  dp[1][1] = p[1];
  dp[1][0] = (1.0 - p[1]);
  for (int i = 2; i <= n; i++) {
    for (int j = 0; j <= i + 1; j++) {
      dp[i][j] += dp[i - 1][j] * (1.0 - p[i]);
      dp[i][j + 1] += dp[i - 1][j] * p[i];
    }
  }
  double ans = 0;
  for (int i = n / 2 + 1; i <= n; i++) {
    ans += dp[n][i];
  }
  cout << fixed << setprecision(12) << ans << endl;
  return 0;
}


Measured memory_bytes: 69120
#include<stdio.h>
#define MAX 500000
#define SENTINEL 2000000000

int L[MAX/2+2],R[MAX/2+2];
int cnt;

void merge(int A[],int n,int left,int mid,int right){
    int n1=mid-left;
    int n2=right-mid;

    for(int i=0;i<n1;i++)L[i]=A[left+i];
    for(int i=0;i<n2;i++)R[i]=A[mid+i];
    L[n1]=SENTINEL;
    R[n2]=SENTINEL;
    int i=0,j=0;
    for(int k=left;k<right;k++){
        cnt++;
        if(L[i]<=R[j]){
            A[k]=L[i];
            i++;
        }
        else{
            A[k]=R[j];
            j++;
        }
    }
}

void mergesort(int A[],int n,int left,int right){
    if(left+1<right){
        int mid=(left+right)/2;
        mergesort(A,n,left,mid);
        mergesort(A,n,mid,right);
        merge(A,n,left,mid,right);
    }
}

int main(void){
    int n;
    scanf("%d",&n);
    int A[n];
    for(int i;i<n;i++)scanf("%d",&A[i]);

    cnt=0;
    mergesort(A,n,0,n);

    for(int i=0;i<n-1;i++){
        printf("%d ",A[i]);
    }
    printf("%d\n",A[n-1]);
    printf("%d\n",cnt);

    return 0;
}


Measured memory_bytes: 5628
#include <iostream>
#include <iomanip>
#include <vector>
#include <algorithm>
#include <numeric>
#include <functional>
#include <cmath>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <sstream>
#include <string>
#define repd(i,a,b) for (int i=(int)(a);i<(int)(b);i++)
#define rep(i,n) repd(i,0,n)
#define all(x) (x).begin(),(x).end()
#define mod 1000000007
#define inf 2000000007
#define mp make_pair
#define pb push_back
typedef long long ll;
using namespace std;
template <typename T>
inline void output(T a, int p) {
    if(p) cout << fixed << setprecision(p)  << a << "\n";
    else cout << a << "\n";
}
// end of template

int main() {
    cin.tie(0);
    ios::sync_with_stdio(0);
    // source code
    
    map<ll, int> M;
    ll H, W, N;
    cin >> H >> W >> N;
    rep(i, N){
        int h, w;
        cin >> h >> w;
        h--, w--;
        rep(j, 3)rep(k, 3){
            if(h - j >= 0 && w - k >= 0 && h - j + 2 < H && w - k + 2 < W){
                if(M[W * (h - j) + (w - k)] >= 1){
                    M[W * (h - j) + (w - k)]++;
                }
                else{
                    M[W * (h - j) + (w - k)] = 1;
                }
            }
        }
        
    }
    vector<ll> ret(10, 0);
    for(auto it = M.begin(); it != M.end(); it++ ) {
        ret[it -> second]++;
    }
    
    ll sum = 0;
    rep(i, 10) sum += ret[i];
    ret[0] = (H - 2) * (W - 2) - sum;
    
    rep(i, 10){
        output(ret[i], 0);
    }
    
    return 0;
}

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

int main()
{
	string S;
	cin >> S;
	int a = stoi(S.substr(0, 2));
	int b = stoi(S.substr(2, 2));
	if (1 <= a && a <= 12 && 1 <= b && b <= 12) {
		cout << "AMBIGUOUS" << endl;
	}
	else if (1 <= a && a <= 12) {
		cout << "MMYY" << endl;
	}
	else if (1 <= b && b <= 12) {
		cout << "YYMM" << endl;
	}
	else {
		cout << "NA" << endl;
	}
	return 0;
}


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

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

int main(){
    int n, x;
    cin >> n >> x;
    vector<int> vec;
    for(int i=0; i<n; i++){
        int xi;
        cin >> xi;
        vec.push_back(abs(xi - x));
    }
    int skip = vec[0];
    for (int i=0; i<n; i++){
        skip = gcd(skip, vec[i]);
    }
    cout << skip << endl;
    return 0;
}


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

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

int main() {
	cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);
	int n,mis=0,x; cin>>n;
	for (int i=1; i<=n; i++) {
		cin>>x;
		if(i!=x) mis++;
	}
	cout<<(mis==2||mis==0?"YES":"NO")<<"\n";
	return 0;
}

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

   typedef long long ll;
   typedef pair<ll, ll> P;

   const double EPS = (1e-7);
   const ll INF =(1e13);
   const double PI = (acos(-1));
   const ll MOD = ll(1e9) + 7;

   #define REP(i, n) for(ll i = 0; i < (ll)(n); i++)
   #define REPR(i, n) for(ll i = n; i > -1; i--)
   #define FOR(i, a, b) for (ll i = (ll)(a); i < (ll)(b); i++)
   #define ALL(x) (x).begin(),(x).end()
   #define SORT(x) sort((x).begin(), (x).end())
   #define REVERSE(x) reverse((x).begin(), (x).end())
   #define SZ(x) ((ll)(x).size())
   #define pb push_back
   #define mp make_pair

   //chmax(a, b): a>bならaをbで更新　更新したときにtrueを返す
   //chmin(a, b): a<bならaをbで更新　更新したときにtrueを返す
   template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
   template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }

   #define dump(x) cerr<< #x << "= " << (x) << endl;

   int gcd(int a,int b){return b?gcd(b,a%b):a;};

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

const ll MAX_N = 1e3;
ll N, K;
ll a[MAX_N];
ll s[MAX_N + 1] = {}; // 累積和

vector<ll> v;

void solve(){
   ll ans = 0;
   REP(i, 51){
      if ((v.end() - lower_bound(v.begin(), v.end(), 1ull << (50 - i)))>= K){
         ans += 1ull << (50 - i);
         REP(j, v.size()){
            if (v[j] >= (1ull << (50 - i))) v[j] -= (1ull << (50 - i));
            else v[j] = 0;
         }
      }
      else{
         REP(j, v.size()){
            v[j] &= ((1ull << (50 - i)) - 1);
         }
      }
      SORT(v);
   }
   cout << ans << endl;
}

int main(){
   cin >> N >> K;
   REP(i, N) {
      cin >> a[i];
      s[i + 1] = s[i] + a[i];
   }
   FOR(i, 0, N){
      FOR(j, i, N){
         v.pb(s[j + 1] - s[i]);
      }
   }
   SORT(v);
   solve();
}

Measured memory_bytes: 6512
#include <bits/stdc++.h>
#include <iostream>
#include <vector>
using namespace std;
typedef long long ll;
int N, Q;
vector <int> edge[200005];
ll inc[200005];

void dfs(int v, int p){
    for (int e: edge[v]){
        if (e != p){
            inc[e] += inc[v];
            dfs(e, v);
        }
    }
}

int main() {
    cin >> N >> Q;
    int a, b;
    for (int i=1; i<=N-1; i++){
        scanf("%d %d", &a, &b);
        edge[a].push_back(b);
        edge[b].push_back(a);
    }
    for (int i=0; i<Q; i++){
        scanf("%d %d", &a, &b);
        inc[a] += b;
    }
    dfs(1, -1);
    for (int i=1; i<=N; i++){
        printf("%lld ", inc[i]);
    } cout << endl;
    return 0;
}

Measured memory_bytes: 24320
<?php

class Scanner
{
    private $arr = [];
    private $count = 0;
    private $pointer = 0;

    public function next()
    {
        if ($this->pointer >= $this->count) {
            $str = trim(fgets(STDIN));
            $this->arr = explode(" ", $str);
            $this->count = count($this->arr);
            $this->pointer = 0;
        }
        $result = $this->arr[$this->pointer];
        $this->pointer++;
        return $result;
    }

    public function hasNext()
    {
        return $this->pointer < $this->count;
    }

    public function nextInt()
    {
        return (int)$this->next();
    }

    public function nextDouble()
    {
        return (double)$this->next();
    }
}

class out
{
    public static function printIn($str = "")
    {
        echo $str . PHP_EOL;
    }
}

$sc = new Scanner;

$a = $sc->nextInt();
$b = $sc->nextInt();
$c = $sc->nextInt();
$x = $sc->nextInt();
$d = 0;

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

echo $d;

Measured memory_bytes: 4856
N = int(input())
h = [int(i) for i in input().split()]

def g(n, h):
    g2 = 0
    g1 = abs(h[1] - h[0])
    for i in range(2, n+1):
        g = min(abs(h[i] - h[i-1]) + g1, abs(h[i] - h[i-2]) + g2)
        g2 = g1
        g1 = g
    return g1

print(g(N-1, h))


Measured memory_bytes: 13708
a1=list(map(int,input().split()))
a2=list(map(int,input().split()))
a3=list(map(int,input().split()))
n=int(input())

for i in range(n):
    b=int(input())
    for j in range(3):
        if a1[j]==b:
            a1[j]=0
        if a2[j]==b:
            a2[j]=0
        if a3[j]==b:
            a3[j]=0

if a1[0]+a1[1]+a1[2]==0:
    print("Yes")
    exit()
if a2[0]+a2[1]+a2[2]==0:
    print("Yes")
    exit()
if a3[0]+a3[1]+a3[2]==0:
    print("Yes")
    exit()
if a1[0]+a2[0]+a3[0]==0:
    print("Yes")
    exit()
if a1[1]+a2[1]+a3[1]==0:
    print("Yes")
    exit()
if a1[2]+a2[2]+a3[2]==0:
    print("Yes")
    exit()
if a1[0]+a2[1]+a3[2]==0:
    print("Yes")
    exit()
if a1[2]+a2[1]+a3[0]==0:
    print("Yes")
    exit()

print("No")

Measured memory_bytes: 3064
#include <stdio.h>

int main(){
int A, K, B, flag=0 ;
scanf("%d %d %d", &K, &A, &B);
for(int i=A; i<=B; i++)if(i%K==0) flag=1;
if(flag==1)printf("OK\n");
else printf("NG\n");
return 0;
}

Measured memory_bytes: 1660
#include<iostream>
#include<algorithm>
#include<vector>
#include<bitset>
#include<map>
#include<cassert>
#include<deque>
#define rep(i,n) for(int i=0;i<n;i++)
using namespace std;
int ans;
map<vector<int>,bool> exist;
bool check(vector<int>& box);

void dfs(int p,vector<int>& box,int bit)
{
  if(p == 10)
    {
      ans += check(box)?1:0;
      return;
    }
  
  if(box[p])
    {
      dfs(p+1,box,bit);
      return;
    } 
  /*
  if(exist[box])
    return;
  exist[box] = true; 
  */
  for(int j=1;j<=10;j++)
    {
      if((bit >> j) & 1)
	continue;
      box[p] = j;
      dfs(p+1,box,bit|(1<<j));
      box[p] = 0;
    }


}

int main()
{
  while(1)
    {
      vector<int> box(10);
      ans = 0;
      exist.clear();
      int bit = 0;
      bool F = true;
      rep(i,10)
	{
	  cin >> box[i];
	  bit |= (1 << box[i]);
	  if(box[i] != -1)
	    F = false;	  
	}
      
      if(F)
	break;
      bit &= (((1<<20)-1)-1);
      dfs(0,box,bit);
      cout <<ans << endl;
   
    }
  return 0;
}

bool check(vector<int>& g)
{
  int module = g[9]; 
  int sum = (g[0]+g[1]+g[2])%module;
  if((g[3]+g[4]+g[5])%module != sum || (g[6]+g[7]+g[8])%module != sum)
    return false;

  if((g[0]+g[3]+g[6])%module != sum || (g[1]+g[4]+g[7])%module != sum || (g[2]+g[5]+g[8])%module != sum)
    return false;

  if((g[0]+g[4]+g[8])%module != sum || (g[2]+g[4]+g[6])%module != sum)
    return false;

  return true;
  
}

Measured memory_bytes: 1192
#include <iostream>
#include <string>
#include <cmath>
#include <algorithm>

#define ll long long

using namespace std;
struct stu{
    ll hui;
    ll tou;
};
struct stu1{
    ll hui;
    ll tou;
};
bool com(struct stu a,struct stu b){
    return a.hui>b.hui;
}
bool com1(struct stu1 a,struct stu1 b){
    return a.tou>b.tou;
}
struct stu z[100001];
struct stu1 z1[100001];
int main(){
    ll a=0,b,c=0,i,n,m;
    cin>>n>>m;
    for(i = 0;i < n;i++){
        cin>>z[i].hui>>z[i].tou;
        z1[i].hui = z[i].hui;
        z1[i].tou = z[i].tou;
        //a = a+z[i].tou;
    }
    sort(z,z+n,com);
    sort(z1,z1+n,com1);
    b = 0;
    int h=0;
    for(i = 0;i <n;i++){
        if(z1[i].tou>z[0].hui){
            h++;
            m = m-z1[i].tou;
            //cout<<z1[i].<<endl;
            if(m<=0){
                cout<<h<<endl;
                return 0;
            }
        }
        else{
            break;
        }
    }
    //cout<<h<<' '<<m<<endl;
        if((m-c)%z[0].hui==0){
            h = h+(m-c)/z[0].hui;
        }
        else{
            h = h+(m-c)/z[0].hui+1;
        }
    cout<<h;
}


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

#define FLASH ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define ll long long int
#define MAX 1e9
#define MIN -1e9
#define mod 1000000007
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define debug(x) cerr<<#x<<'='<<(x)<<endl;
#define mxn 300005
using namespace std;

int main()
{
    FLASH
    int x;
    cin >> x;
    if(x >= 30){
    	cout << "Yes";
    }
    else{
    	cout << "No";
    }

    return 0;
}


Measured memory_bytes: 3648
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <set>
#include <map>
#include <string>

using namespace std;

#define fastInp cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);

typedef long long ll;
const ll MOD = 1e9 + 7, SZ = 5002;

ll n, k, dp[SZ][SZ * 2];

int main() {
	fastInp;

	cin >> n >> k;

	dp[0][0] = 1;
	ll pw = 1;
	for (int i = 0; i < n - 1; i++) {
		pw *= (k + 1);
		pw %= MOD;
	}
	ll add = 0;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j <= k; j++) {
			add += (j * pw);
			add %= MOD;
			for (int curs = 0; curs < SZ * 2; curs++) {
				ll s = 0;
				if (j > (n - i)) {
					s = curs;
				}
				else {
					s = curs + (curs + j) / (n - i);
				}
				dp[i + 1][s] += dp[i][curs];
				dp[i + 1][s] %= MOD;
			}
		}
	}

	ll dis = 0;
	for (int j = 0; j < SZ * 2; j++) {
		dis += dp[n][j] * j;
		dis %= MOD;
	}
	cout << (add - dis + MOD) % MOD;

	return 0;
}

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

int main(){
  int i,j;ll cnt=0;
  int n;
  cin>>n;
  ll a[n];
  for(i=0;i<n;i++)cin>>a[i];
  ll p=0,m=0;
  ll S=0;
  for(i=0;i<n;i++){
    S+=a[i];
    if(i%2==0){
      if(S<=0){
        cnt=1-S;
        p+=cnt;
        S+=cnt;
      }
    }else{
      if(S>=0){
        cnt=S+1;
        p+=cnt;
        S-=cnt;
      }
    }
  }
  S=0;
  for(i=0;i<n;i++){
    S+=a[i];
    if(i%2==1){
      if(S<=0){
        cnt=1-S;
        m+=cnt;
        S+=cnt;
      }
    }else{
      if(S>=0){
        cnt=S+1;
        m+=cnt;
        S-=cnt;
      }
    }
  }
  cout<<min(p,m)<<endl;
}

Measured memory_bytes: 1024
S = input()
A = input()

if len(S) < len(A):
    print('UNRESTORABLE')
    exit(0)


for i in reversed(range(len(S)-len(A)+1)):
    for j in range(len(A)):
        if not(S[i+j] == A[j] or S[i+j] == '?'):
            break
    else:
        ans = S[:i] + A + S[i+len(A):]
        ans = ans.replace('?', 'a')
        print(ans)
        break
else:
    print('UNRESTORABLE')


Measured memory_bytes: 9076
N = int(input())
S = input()
ans = S.count("R") * S.count("G") * S.count("B")


for i in range(N-2):
    for j in range(i+1,N-1):
        k = j + (j-i)
        if k < N and S[i] != S[j] and S[k] != S[j] and S[i] != S[k]:
            ans -= 1

print(ans)


Measured memory_bytes: 9192
#include<iostream>
#include<algorithm>
#include<vector>
#include<string>
#define int long long
using namespace std;
int c, n;
char map[1234][1234];
bool b(int i, int j) {
	return (map[i][j] == map[i][n - j + 1] && map[i][j] == map[n - i + 1][j] && map[i][j] == map[n - i + 1][n - j + 1]);
}
signed main() {
	cin >> c >> n;
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= n; j++)
			cin >> map[i][j];
	int t = 0, ans = 0;
	for (int i = 1; i <= n / 2; i++)
		for (int j = 1; j <= n / 2; j++)
			t += !b(i, j);
	ans += (t == 0);
	for (int i = 1; i < c; i++) {
		int d; cin >> d;
		for (int j = 0; j < d; j++) {
			int x, y; cin >> x >> y;
			int t1 = !b(x, y);
			map[x][y] = (map[x][y] == '0' ? '1' : '0');
			int t2 = !b(x, y);
			t += t2 - t1;
		}
		ans += (t == 0);
	}
	cout << ans << endl;
}


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

using pii = pair<int, int>;

constexpr int INF = 1e9;

string get_time(int s) {
    string h = to_string(s / 3600);
    s %= 3600;
    string m = to_string(s / 60);
    s %= 60;
    string ss = to_string(s);
    if(h.size() == 1) {
        h = "0" + h;
    }
    if(m.size() == 1) {
        m = "0" + m;
    }
    if(ss.size() == 1) {
        ss = "0" + ss;
    }
    return h + ':' + m + ':' + ss;
}

int main() {
    int n;
    while(cin >> n, n) {
        vector<pii> ws;
        for(int i=0; i<n; ++i) {
            vector<int> t(3);
            cin >> t[0] >> t[1] >> t[2];
            sort(t.begin(), t.end());
            do {
                for(int j=0; j<60; ++j) {
                    int h = (t[0] + j) % 60;
                    int m = (t[1] + j) % 60;
                    int s = (t[2] + j) % 60;
                    if(h % 5 != m / 12) {
                        continue;
                    }
                    h /= 5;
                    ws.push_back(make_pair(h*3600 + m*60 + s, i));
                }
            } while(next_permutation(t.begin(), t.end()));
        }
        sort(ws.begin(), ws.end());
        pii res = make_pair(-INF, INF);
        for(int i=0; i<ws.size(); ++i) {
            vector<bool> used(n);
            int first = ws[i].first, last;
            int cnt = 0;
            for(int j=i; j<ws.size(); ++j) {
                if(!used[ws[j].second]) {
                    last = ws[j].first;
                    cnt++;
                    used[ws[j].second] = true;
                }
            }
            if(cnt != n) {
                continue;
            }
            if(last - first < res.second - res.first) {
                res.first = first;
                res.second = last;
            }
        }
        cout << get_time(res.first) << ' ' << get_time(res.second) << endl;
    }
}


Measured memory_bytes: 3276
#include<bits/stdc++.h>
typedef long long ll;
#define pb push_back
#define mp make_pair
#define fi first
#define se second
using namespace std;
ll n,i,ta,tb,p[101010],hz,has;
int main()
{
	ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>n;
	for(i=1;i<=n;i++)
	{
		cin>>ta>>tb;
		p[ta]++;
		p[tb+1]--;
	}
	for(i=1;i<=100000;i++)
	{
		hz+=p[i];
		if(hz>0)
			has++;
	}
	cout<<has<<"\n";
}

Measured memory_bytes: 1024
#include<iostream>
#include<stdio.h>
#include<math.h>
using namespace std;

int main(){
	int N;
	double a,b,c,X;
	cin>>N;
	for(int i=0;i<N;i++){
		cin>>a>>b>>c;
		if(a>b){
			X=a;
			a=b;
			b=X;
		}
		if(a>c){
			X=a;
			a=c;
			c=X;
		}
		if(b>c){
			X=b;
			b=c;
			c=X;
		}
		if(sqrt(a*a+b*b)==c){
			cout<<"YES"<<endl;
		}else{
			cout<<"NO"<<endl;
		}
		//cout<<a<<b<<c;
	}
    return 0;
}

Measured memory_bytes: 1220
#include <cstdio>
#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 150;

int a, b, c, d[N][N][N];
vector < pair < int, pair <int, int> > > q;

void add(int x, int y, int z, int c) {
    if (x >= N || y >= N || z >= N) {
        return;
    }
    if (d[x][y][z] == -1) {
        d[x][y][z] = c + 1;
        q.push_back(make_pair(x, make_pair(y, z)));
    }
}

int main() {

    scanf("%d %d %d", &a, &b, &c);

    memset(d, -1, sizeof d);

    d[a][b][c] = 0;
    q.push_back(make_pair(a, make_pair(b, c)));

    for (int i = 0; i < q.size(); i++) {
        int x = q[i].first;
        int y = q[i].second.first;
        int z = q[i].second.second;
        if (x == y && y == z) {
            printf("%d\n", d[x][y][z]);
            exit(0);
        }
        add(x + 1, y + 1, z, d[x][y][z]);
        add(x + 1, y, z + 1, d[x][y][z]);
        add(x, y + 1, z + 1, d[x][y][z]);
        add(x + 2, y, z, d[x][y][z]);
        add(x, y + 2, z, d[x][y][z]);
        add(x, y, z + 2, d[x][y][z]);
    }

    return 0;

}


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

typedef long long  LL;
const int N=200010;
struct edge{int s,t,n;}e[2*N];
int n,m,h[N],sum[N],maxdep[N];
LL ans;
char s[N];

void dfs(int x,int f)
{
	sum[x]=(s[x]=='1');
	for (int i=h[x],y; y=e[i].t,i; i=e[i].n)
		if (y!=f)  dfs(y,x),sum[x]+=sum[y],maxdep[x]=max(maxdep[x],maxdep[y]+1);
}

void dfs(int x,int f,int MaxDep)
{
	int l=(s[x]=='1'?0:1<<30),r,mx1=MaxDep,mx2=0;
	if (m-sum[x])  l=min(l,MaxDep);
	for (int i=h[x],y; y=e[i].t,i; i=e[i].n)
		if (y!=f)
			{
				if (maxdep[y]+1>mx2)  mx2=maxdep[y]+1;
				if (mx2>mx1)  swap(mx1,mx2);
				if (sum[y])  l=min(l,maxdep[y]+1);
			}
	if (mx1==mx2)  r=mx2-1;
	else  if (mx1==mx2+1)  r=mx2;
	else  r=mx2+1;
	if (l<=r)  ans+=r-l+1;
	for (int i=h[x],y; y=e[i].t,i; i=e[i].n)
		if (y!=f)
			{
				if (maxdep[y]+1!=mx1)  dfs(y,x,mx1+1);
				else  dfs(y,x,mx2+1);
			}
}

void work()
{
	scanf("%d",&n),ans=1;
	for (int i=1,u,v,tot=0; i<n; i++)
		{
			scanf("%d %d",&u,&v);
			e[++tot]=(edge){u,v,h[u]},h[u]=tot;
			e[++tot]=(edge){v,u,h[v]},h[v]=tot;
		}
	scanf("%s",s+1);
	for (int i=1; i<=n; i++)  m+=(s[i]=='1');
	dfs(1,0);
	dfs(1,0,0);
	printf("%lld",ans);
}

int main()
{
	work();
	return 0;
}


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

int main() {
  string a;

  cin >> a;
  
  if ( a == "111"  ) {
    cout << "3" << endl;   
  }
  else if ( a == "000" ) {
    cout << "0" << endl;
  }
  else if ( a == "110" || a == "101" || a == "011" ) {
    cout << "2" << endl;
  }
  else {
    cout << "1" << endl;
  }
    
}

Measured memory_bytes: 256
s = input()
A = int(s[0])
B = int(s[1])
C = int(s[2])
D = int(s[3])

if A + B + C + D == 7:
    print("{0}+{1}+{2}+{3}=7".format(A, B, C, D))
elif A + B + C - D == 7:
    print("{0}+{1}+{2}-{3}=7".format(A, B, C, D))
elif A + B - C - D == 7:
    print("{0}+{1}-{2}-{3}=7".format(A, B, C, D))
elif A + B - C + D == 7:
    print("{0}+{1}-{2}+{3}=7".format(A, B, C, D))
elif A - B + C + D == 7:
    print("{0}-{1}+{2}+{3}=7".format(A, B, C, D))
elif A - B + C - D == 7:
    print("{0}-{1}+{2}-{3}=7".format(A, B, C, D))
elif A - B - C - D == 7:
    print("{0}-{1}-{2}-{3}=7".format(A, B, C, D))
elif A - B - C + D == 7:
    print("{0}-{1}-{2}+{3}=7".format(A, B, C, D))

Measured memory_bytes: 3064
N = int(input())
W = [input() for i in range(N)]
flag = True

for i in range(N-1):
    if W[i][len(W[i])-1] != W[i+1][0]:
        flag = False
        
for i in range(N):
    for j in range(N):
        if i != j:
            if W[i] == W[j]:
                flag = False

if flag:
    print('Yes')
else:
    print('No')
    

Measured memory_bytes: 3060
#include <bits/stdc++.h>
#define MAX 100005
#define MOD 1e9
#define pb push_back
#define pairs pair<int, int>
#define vi vector<int>
#define vb vector<bool>
#define vii vector<pairs>
#define lb lower_bound
#define ub upper_bound
#define ll long long
#define endl '\n'
using namespace std;
/* ----------------------------------------------------------------------------------- */

#define fastInput ios_base::sync_with_stdio(false), cin.tie(NULL);
#define all(x) x.begin(), x.end()
#define scan(a) scanf("%d", &a)
#define scanll(a) scanf("%lld", &a)
#define scanD(a) scanf("%lf", &a)
#define print(a) printf("%d\n", a)
#define printll(a) printf("%lld\n", a)
#define printD(a) printf("%lf\n", a)
#define printTwo(a) printf("%.2lf\n", a);
#define read(x) freopen(x, "r", stdin)
#define write(x) freopen(x, "w", stdout)
#define rep(i, a, n) for (int i = a; i < n; i++)
#define REP(i, a, n) for (int i = a; i <= n; i++)
#define inputArray(a,n) rep(i, 0, n) cin >> a[i];
#define copyArray(a,temp,n) rep(i, 0, n) temp[i]=a[i];
#define printArray(a,n) rep(i, 0, n) cout << a[i] << " "; cout << endl;

/* ----------------------------------------------------------------------------------- */

#define Cases  cout << "Case " << ++Case << ": ";
#define __test int tt; int Case=0; cin >> tt; while(tt--)
#define showTime cerr << "time = " << (clock() / CLOCKS_PER_SEC) << " sec" << '\n';

#define dbgA2(A, n, m) {cout<<"--> "<<#A<<" = \n";rep(i, 0, n){rep(j, 0, n){cout<<A[i][j]<<" ";}cout<<"\n";}cout<<"\n";}
#define dbgA(A, n) {cout<<" --> "<<#A<<" = (";rep(i, 0, n)cout<<A[i]<<" ";cout<<")\n";}
#define dbg(args...) {string sss(#args);sss+=',';cout<<" --> ";debugger::call(all(sss), args);cout<<"\n";}

/* ----------------------------------------------------------------------------------- */

ll gcd(ll n, ll m) { return m ? gcd(m, n % m) : n; }
ll lcm(ll n, ll m) { return n / gcd(n, m) * m; }

struct debugger {
	typedef string::iterator si;
	static void call(si it, si ed) {}
	template<typename T, typename ... aT>
	static void call(si it, si ed, T a, aT... rest) {
		string b;
		for(; *it!=','; ++it)
			if(*it!=' ')
				b+=*it;
		cout << b << "=" << a << " ";
		call(++it, ed, rest...);
	}
};

/* ----------------------------------------------------------------------------------- */


void solve() {
	int n, k;
	scan(k);
	scan(n);
	vi vc(n);
	int minDis = INT_MAX;

	rep(i, 0, n) {
		scan(vc[i]);
	}
	
	rep(i, 0, n) {
		int start = vc[i];
		if (i) {
			int end = vc[i - 1];
			minDis = min(minDis, abs(start - k) + abs(0 - end));
		} else {
			int end = vc[n - 1];
			minDis = min(minDis, abs(start - end));
		}
	}
	print(minDis);
}

int main() {
#ifdef Niloy
	read("input.txt");
	write("output.txt");
#endif

	solve();

	// __test {
	// 	solve();
	// }

	showTime;
	return 0;
}




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

long long gcd(long long x, long long y) { return y ? gcd(y, x%y) : x;}

vector<pair<long long, int>> factorize(long long n){ //素因数とその何乗か
    vector<pair<long long, int>> res;
    for (long long i = 2; i*i <= n; i++){
        if (n%i) continue; //割り切れなかったら
        res.emplace_back(i, 0); //first,secondの末尾に追加
        while (n%i == 0){//割り切れる
            n /= i;
            res.back().second++; //何乗するか
        }
    }
    if (n != 1) res.emplace_back(n, 1); //その数自体も追加
    return res;
}

int main(){
    long long a, b;
    cin >> a >> b;
    long long g = gcd(a, b); //a,bの最大公約数
    auto f = factorize(g);
    int ans = f.size() + 1; //
    cout << ans << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
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; }
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define all(vec) vec.begin(),vec.end()
typedef long long ll;
const int MAX=2e5;
const ll MOD=1e9+7;
const int INF=1<<30;
ll kiriage(ll a,ll b){return a%b==0?a/b:a/b+1;}

int main(){
  int D;
  ll G;
  cin >> D >> G; 
  vector<ll> p(D),c(D);
  rep(i,D) cin >> p[i] >> c[i];
  ll res;
  ll ans=INF;
  for(int i=0;i<(1LL<<D);i++){
    bool flag=true;
    ll sum=0;
    ll pans=0;
    for(int j=0;j<D;j++){
      if(flag&&!(i& (1LL<<j) ) ){
        res=j;
        flag=false;
      }
      if(i&(1LL<<j)){
        sum+=100*(D-j)*p[D-j-1]+c[D-j-1];
        pans+=p[D-j-1];
      }
    }
    if(sum>=G){
      if(pans<ans) ans=pans;
      continue;
    } 
    else{
      if(kiriage(G-sum,100*(D-res) )<=p[D-res-1]){
        pans+=kiriage(G-sum,100*(D-res));
        if(pans<ans) ans=pans;
      }
    }
  }
  cout << ans << endl;
}

Measured memory_bytes: 256
package main

import "fmt"

func main() {
	var a, n int
	fmt.Scan(&a)
	n = a % 10

	if n == 3{
		fmt.Println("bon")
	} else if n == 0 || n == 1 || n ==6 || n == 8{
		fmt.Println("pon")
	}else{
		fmt.Println("hon")
	}
}

Measured memory_bytes: 1752
#include <bits/stdc++.h>
#define SORT(x) sort((x).begin(),(x).end())
#define ALL(x) (x).begin(),(x).end()
#define rep(i, n) for(int i = 0; i < n; i++)
#define reps(i, m, n) for(int i = m; i < n; i++)
#define repr(i, m, n) for(int i = m; i >= n; i--)
template<class T>bool maxi(T &a,const T &b){if(a<b){ a=b; return 1;} return 0;}
template<class T>bool mini(T &a,const T &b){if(b<a){ a=b; return 1;} return 0;}
#define y0 y3487465 //j0
#define y1 y1347829 //j1
#define INF2 4000000000000000037
#define INF 1000000007
#define PI (acos(-1))
#define MOD 1000000007
using namespace std;
typedef long long ll;

void Main(){

  int N,M;
  cin>>N>>M;

  priority_queue<int> qu;

  rep(i,N){
    int a; cin>>a;
    qu.push(a);
  }

  rep(i,M){
    int now=qu.top();
    qu.pop();
    qu.push(now/2);
  }

  ll ans=0;

  rep(i,N){
    ans+=qu.top();
    qu.pop();
  }

  cout<< ans<<"\n";

}

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


Measured memory_bytes: 892
#include <iostream>
#include <vector>
using namespace std;
const int INF = 1001001001;
const int MAX = 200005;

int a[MAX], ans[MAX];
vector<vector<int>> g;

void dfs(int v, int parent, vector<int> &dp) {
	auto itr = lower_bound(dp.begin(), dp.end(), a[v]);
	int tmp = *itr;
	*itr = a[v];
	ans[v] = lower_bound(dp.begin(), dp.end(), INF) - dp.begin();
	for (int nv : g[v]) {
		if (nv == parent) continue;
		dfs(nv, v, dp);
	}
	*itr = tmp;
}

int main() {
	int n;
	cin >> n;
	g.resize(n);
	for (int i = 0; i < n; i++) {
		scanf("%d", a+i);
	}
	for (int i = 0; i < n-1; i++) {
		int u, v;
		scanf("%d%d", &u, &v);
		u--, v--;
		g[u].push_back(v);
		g[v].push_back(u);
	}
	vector<int> dp(n, INF);
	dfs(0, -1, dp);
	for (int i = 0; i < n; i++) {
		cout << ans[i] << endl;
	}
	return 0;
}

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

int main(){
        int N,ans,divide;
        ans=0;
        cin >> N;
        for(int i=3; i >= 0; i--){
          divide = N / pow(10,i);
          if (divide == 2){
                  ans++;
          }
          N = N - divide * pow(10,i);
        }
        
        cout << ans << endl;
        return 0;
}


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

ll n;
ll a[200001];
ll k;
vector<int> adj[200001];
bool visited[200001];
vector<int> path, cycle;
int cyc_start;
int path_len;

void dfs(int x) {
    visited[x] = true;
    path.push_back(x);

    for (int nx : adj[x]) {
        if (!visited[nx]) {
            dfs(nx);
        } else {
            cyc_start = nx;
        }
    }
}

int main() {
    #ifdef DEBUG
        freopen("in.txt", "r", stdin);
    #endif
    ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);

    cin >> n >> k;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        adj[i].push_back(a[i]);
    }

    dfs(1);
    // cout << cyc_start << '\n';
    int sw = 0;
    for (int& it : path) {
        if (it == cyc_start) {
            sw = 1;
            cycle.push_back(it);
        } else {
            if (!sw) {
                path_len++;
            } else {
                cycle.push_back(it);
            }
        }
    }

    if (k < path_len) {
        cout << path[k] << '\n';
    } else {
        k -= path_len;
        cout << cycle[k % cycle.size()] << '\n';
    }



    return 0;
}


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

 	ll mod = 1000000000+7;
 
	int main() {

		#ifndef ONLINE_JUDGE
	        freopen("input.txt","r",stdin);
	        // freopen("output.txt","w",stdout);
	    #endif
	    ios::sync_with_stdio(false);
	    cin.tie(0);
	    cout.tie(0);
	   	int n,k,t;
	   	cin>>n>>k>>t;
	   	cout<<(int)ceil(1.0*n/k)*t<<endl;
	   	
		
	}

	


Measured memory_bytes: 3560
import java.util.Scanner;

public class Main{
    public static void main(String[] args){
     double r,pi,s,l;
     Scanner sc = new Scanner(System.in); 
         r =   sc.nextDouble();
     pi = Math.PI;
     s = r*r*pi;
     l = 2*r*pi;
     System.out.printf("%f %f\n",s,l);
    }
}


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

using namespace std;

int main(){
    string s;
    cin >> s;
    int ramen = 700;
    int egg = 100;
    int roasted = 100;
    int green_onions = 100;
    int result = 700;
    if(s[0] == 'o'){
        result += egg;
    }
    if(s[1] == 'o'){
         result += roasted;
    }
    if(s[2] == 'o'){
         result += green_onions;
    }
    cout << result << endl;
}

Measured memory_bytes: 256
#include <cstdio>
#include <algorithm>

const int kMaxn = 5e5, MOD = 998244353;

typedef long long LL;

int n, m, t;
LL fac[kMaxn * 2 + 10], ifac[kMaxn * 2 + 10];

inline LL C(int n, int r) {
	return fac[n] * ifac[r] % MOD * ifac[n - r] % MOD;
}
LL FastPow(LL bs, int ex = MOD - 2) {
	LL ret = 1;
	for (; ex; (bs *= bs) %= MOD, ex >>= 1)
		if (ex & 1) (ret *= bs) %= MOD;
	return ret;
}

int main() {
	scanf("%d%d", &n, &m);
	t = n + m;
	
	fac[0] = 1;
	for (LL i = 1; i <= t; i++) fac[i] = fac[i - 1] * i % MOD;
	ifac[t] = FastPow(fac[t]);
	for (LL i = t - 1; i >= 0; i--) ifac[i] = ifac[i + 1] * (i + 1) % MOD;

	if (n > m) std::swap(n, m);
	LL sum = 0;
	for (int i = 1; i <= n; i++) {
		(sum += C(i << 1, i) * C(n - i + m - i, m - i) % MOD) %= MOD;
	}
	(sum *= FastPow(2)) %= MOD;
	LL ans = m + sum * FastPow(C(n + m, n)) % MOD;
	(ans += MOD) %= MOD;
	
	printf("%lld\n", ans);
	return 0;
}

Measured memory_bytes: 15744
import sys, bisect

N = int(input())
L = list(map(int, sys.stdin.readline().rsplit()))
L.sort()

res = 0
for i in reversed(range(1, N)):
    for j in reversed(range(i)):
        l = bisect.bisect_left(L, L[i] + L[j])
        # r = bisect.bisect_right(L, abs(L[i] - L[j]))
        
        res += l - 1 - i
        
print(res)


Measured memory_bytes: 9264
package main

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

func main() {
	N, K := ReadInt(), ReadInt()
	h := ReadInts(N)
	sort.Ints(h)
	ans := 1 << 62
	for i := 0; i < N-(K-1); i++ {
		ans = Min(ans, h[i+K-1]-h[i])
	}
	fmt.Println(ans)
}

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

var reader = bufio.NewReader(os.Stdin)

func Scan(a ...interface{}) {
	if _, err := fmt.Fscan(reader, a...); err != nil {
		panic(err)
	}
}
func ReadInt() (i int) { Scan(&i); return }
func ReadInts(n int) []int {
	v := make([]int, n)
	for i := 0; i < n; i++ {
		Scan(&v[i])
	}
	return v
}


Measured memory_bytes: 4292
#include <bits/stdc++.h>
#include <assert.h>
using namespace std;
using i64 = long long;

int main()
{
  i64 k, x;
  cin >> k >> x;
  for (i64 i = x - k + 1; i < k + x; i++)
    cout << i << (i + 1 == k + x ? "\n" : " ");
  return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main()
{
 long long int a,b,c,k;
  cin>>a>>b>>c>>k;
  if(k<a){cout<<k;}
  else if(k-a<=0)cout<<a;
  else if(k-a-b<=0)
  {cout<<a;}
    else {cout<<a-(k-a-b);}
   return 0;
  }

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

int main()
{
    int n,i;
    string a;
    cin >> n >> a;
    i = 0;
    int found = a.find("ABC");
    while (found >= 0 && found < n){
        if (found >= 0){
            a[found] = 0;
            found = a.find("ABC");
            i++;
        }
    }
    cout << i;
    return 0;
}


Measured memory_bytes: 256
import sys
import numpy as np

sys.setrecursionlimit(10 ** 9)

s = np.array(list(input()), dtype='U1')
t = np.array(list(input()), dtype='U1')

ls, lt = len(s), len(t)

eq = s[:, None] == t[None, :] 
dp = [np.zeros(lt + 1)]

for i in range(ls):
    prev = dp[-1].copy()
    np.maximum(prev[:-1] + eq[i], prev[1:], out=prev[1:])
    np.maximum.accumulate(prev, out=prev)
    dp.append(prev)

ans = ''
i, j = ls, lt
while i > 0 and j > 0:
    if eq[i-1][j-1]:
        ans += s[i-1]
        i, j = i-1, j-1
    elif dp[i][j] == dp[i-1][j]:
        i -= 1
    else:
        j -= 1
ans = ans[::-1]
print(ans)

Measured memory_bytes: 91976
import java.util.Scanner;

public class Main {
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String S = sc.next();
        if (S.equals("AAA") || S.equals("BBB")) {
            System.out.println("No");
        } else {
            System.out.println("Yes");
        }
    }
}

Measured memory_bytes: 25044
#include<iostream>
#include<queue>
#include<algorithm>
#include<vector>
using namespace std;
struct edge{int to,fee,cost;};
struct state{
  int cost,pos,cash;
  bool operator < (const state &s)const{
    return cost>s.cost;
  }
};

#define MAX_V 100
#define INF (1<<24)
vector<edge> G[MAX_V];
int V,E,L;

void init();
int dijkstra(int,int);

int main(){
  int a,b,c,d;
  while(1){
    cin>>V>>E>>L;
    if(V==0&&E==0&&L==0)break;
    init();
    for(int i=0;i<E;i++){
      cin>>a>>b>>c>>d;
      a--;b--;
      G[a].push_back( (edge){b,c,d} );
      G[b].push_back( (edge){a,c,d} );
    }
    cout<<dijkstra(0,V-1)<<endl;
  }
  return 0;
}

int dijkstra(int si,int ti){
  int d[MAX_V][200];
  fill(d[0],d[0]+MAX_V*200,INF);
  d[si][L]=0;
  priority_queue<state> Q;
  Q.push( (state){0,si,L} );

  while(!Q.empty()){
    state now=Q.top();Q.pop();
    if(now.cost>d[now.pos][now.cash])continue;
    for(int i=0;i<(int)G[now.pos].size();i++){
      edge e=G[now.pos][i];
      if(now.cost+e.cost < d[e.to][now.cash]){
	d[e.to][now.cash]=now.cost+e.cost;
	Q.push( (state){now.cost+e.cost,e.to,now.cash} );
      }
      if(now.cash-e.fee<0)continue;
      int ncash=now.cash-e.fee;
      if(now.cost < d[e.to][ncash]){
	d[e.to][ncash]=now.cost;
	Q.push( (state){now.cost,e.to,ncash} );
      }
    }
  }

  int res=INF;
  for(int i=0;i<200;i++)
    res=min(res,d[ti][i]);
  return res;
}

void init(){
  for(int i=0;i<MAX_V;i++)G[i].clear();
}

Measured memory_bytes: 1792
#!/usr/bin/env python3
# coding: utf-8
import math
import itertools
import collections

# def debug(arg):
#     if __debug__:
#         pass
#     else:
#         import sys
#         print(arg, file=sys.stderr)

def main():
    K = int(input())
    print(next(itertools.islice(lunlun(), K - 1, None)))

def lunlun():
    q = collections.deque(range(1,10))
    while True:
        x = q.popleft()
        yield x
        r = x % 10
        if r != 0:
            q.append(10 * x + r - 1)
        q.append(10 * x + r)
        if r != 9:
            q.append(10 * x + r + 1)

if __name__ == "__main__":
    main()

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

struct UnionFind {
  UnionFind(int n) : n(n), v(n, -1) {}
  int n;
  vector<int> v;

  int root(int x) {
    return (v[x] < 0 ? x : v[x] = root(v[x]));
  }

  bool same(int x, int y) {
    return root(x) == root(y);
  }

  void unite(int x, int y) {
    x = root(x);
    y = root(y);
    if (x != y) {
      if (v[x] > v[y]) swap(x, y);
      v[x] += v[y];
      v[y] = x;
    }
  }

  int size(int x) {
    return -v[x];
  }
};

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

  UnionFind uf(n);
  while (q--) {
    int c, x, y;
    scanf("%d %d %d", &c, &x, &y);
    if (c) {
      cout << uf.same(x, y) << endl;
    } else {
      uf.unite(x, y);
    }
  }
}

Measured memory_bytes: 3288
#include<iostream>
#include<algorithm>
#include<string>
using namespace std;

int main() {
    int n;
    cin>>n;
    string s;
    cin>>s;
    
    int ans = 0;
    for(int i=1;i<n;i++){
        int cnt = 0;
        
        for(char c ='a';c<='z';c++){
            bool left=false,right=false;
            
            for(int j = 0;j<i;j++)
            if(s[j]==c) left=true;
            
            for(int j=i;j<n;j++)
            if(s[j]==c) right=true;
            
            if(left&&right) cnt++;
        }
        
        if(ans<cnt) ans=cnt;
    }
    
    cout << ans << endl;
    
}

Measured memory_bytes: 256
import java.util.Scanner;
import java.util.Arrays;

public class Main {
        public static void main(String[] args) {
                Scanner sc = new Scanner(System.in);
                int n = sc.nextInt();
                int[] l = new int[n];
                for (int i = 0; i < n; i++) {
                        l[i] = sc.nextInt();
                }
                sc.close();
                int r = 0;
                Arrays.sort(l);
                for (int i = 0; i < n; i++) {
                        for (int j = i + 1; j < n; j++) {
                                int idx = binSearch(l, n, l[i] + l[j]);
                                r += idx - j;
                        }
                }
                System.out.println(r);
        }

        static int binSearch(int[] a, int n, int key) {
                int ok = -1; // 探索範囲先頭のインデックス
                int ng = n; // 探索範囲末尾のインデックス
                while (Math.abs(ok - ng) > 1) {
                        int mid = (ok + ng) / 2; // 中央要素のインデックス
                        if(a[mid] < key) ok = mid;
                        else ng = mid;
                }
                return ok;
        }
}


Measured memory_bytes: 26956
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> ii;
typedef vector<ii> vii;

main(){
    int n,m;
    cin>>n>>m;
    ll h[n+1];
    int count[n+1];
    count[0]=0;
    for(int i=1;i<=n;i++) {
        cin>>h[i];
        count[i]=1;
    }
    int a,b;
    while(m--){
        cin>>a>>b;
        if(h[a]<h[b]) count[a]=0;
        else if(h[a]>h[b]) count[b]=0;
        else {
            count[a]=0;
            count[b] = 0;
        }
    }
    int res = accumulate(count+1,count+n+1,0);
    cout<<res;
}

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

using namespace std;
typedef long long ll;
int _w;

int main() {
	ll a, b, c;
	cin >> a >> b >> c;
	if( !(a&1) || !(b&1) || !(c&1) )
		puts("0");
	else cout << min(a*b, min(a*c, b*c)) << endl;
	return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <unordered_map>
#include <utility>
#include <algorithm>

using namespace std;

int main() {
    vector<pair<int, int>> reds, blues;
    int N;
    cin >> N;
    vector<bool> used(N);
    for (int i = 0; i < N; ++i) {
        int x, y;
        cin >> x >> y;
        reds.emplace_back(x, y);
    }
    for (int i = 0; i < N; ++i) {
        int x, y;
        cin >> x >> y;
        blues.emplace_back(x, y);
    }
    sort(reds.begin(), reds.end());
    sort(blues.begin(), blues.end());

    int answer = 0;
    for (auto&& blue: blues) {
        int ymax = -100;
        int ix = -1;
        for (int i = 0; i < N; i++) {
            if (used[i]) {
                continue;
            }
            auto const& red = reds[i];
            if (red.first < blue.first && red.second < blue.second) {
                if (ymax < red.second) {
                    ix = i;
                    ymax = red.second;
                }
            }
        }
        if (ix != -1) {
            used[ix] = true;
            answer++;
        }
    }
    cout << answer << '\n';
    return 0;
}


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

int main() {
    int n, cn, arr[1000001] = {0}, arr_num[200000], counting;
    long long cl;
    map<int,int> cm;
    cin >> n;
    for (int j = 0; j < n; j++) {
        cin >> cn;
        arr[cn] = 1;
        arr_num[j] = cn;
        cm[cn]++;
    }
    sort(arr_num, arr_num+n);
    counting = 0;
    for (int j = 0; j < n; j++) {
        if (arr[arr_num[j]]) {
            if (cm[arr_num[j]] == 1) {
                counting++;
            }
            cl = (long long)(arr_num[j]);
            for (long long k = 2 * cl; k <= arr_num[n-1]; k+= cl) {
                arr[(int)(k)] = 0;
            }
        }
    }
    cout << counting;
    return 0;
}




Measured memory_bytes: 17616
def main():
    N, L = map(int, input().split())
    A = list(map(int, input().split()))
    for i in range(1, N):
        if A[i-1] + A[i] >= L:
            print("Possible")
            for j in range(1, i):
                print(j)
            for j in range(N-1, i-1, -1):
                print(j)
            return
    print("Impossible")


if __name__ == "__main__":
    main()


Measured memory_bytes: 63984
H, W = map(int, input().split())
N = int(input())
A = [int(x) for x in input().split()]

r = 1
l = []
for i, a in enumerate(A):
    l += [i + 1] * a
    while len(l) >= W:
        t, l = l[:W], l[W:]
        print(*t[::r])
        r *= -1

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

using ll = long long;
using ull = unsigned long long;
using st = string;
using db = double;
using vll = vector<long long>;
using vvll = vector<vll>;
using vchar = vector<char>;
#define rep(i, m, n) for (int i = (int)(m); i < (int)(n); i++)
#define all(v) v.begin(), v.end()
const ll mod = 1000000007;

int main(){
  ll n, x, y;
  cin >> n >> x >> y;

  vll ans(n, 0);
  rep(i, 2, n + 1){
    rep(j, 1, i){
    ll dis = i - j;
    if(dis > abs(j - x) + abs(i - y) + 1) dis = abs(j - x) + abs(i - y) + 1;
    ans.at(dis)++;
  }
  }
  rep(i, 1, n) cout << ans.at(i) << endl;
}

Measured memory_bytes: 256