akhauriyash/Code-Regression huggingface dataset:
use std::io::{BufRead, Write};
use std::io;
use std::iter;

fn abs_sub(lhs: usize, rhs: usize) -> usize {
    return if lhs > rhs { lhs - rhs } else { rhs - lhs };
}

fn solve<R: BufRead, W: Write>(mut input: R, mut output: W) {
    let mut buf = String::new();
    input.read_line(&mut buf).unwrap();
    let n: usize = buf.trim_right().parse().unwrap();
    let txy: Vec<(usize, (usize, usize))> = iter::once((0, (0, 0))).chain((0..n).map(|_| {
        buf.clear();
        input.read_line(&mut buf).unwrap();
        let mut split = buf.split_whitespace();
        (split.next().unwrap().parse::<usize>().unwrap(), (split.next().unwrap().parse::<usize>().unwrap(), split.next().unwrap().parse::<usize>().unwrap()))
    })).collect();
    let possible = txy.windows(2).all(|w| {
        let distance = abs_sub((w[0].1).0, (w[1].1).0) + abs_sub((w[0].1).1, (w[1].1).1);
        let time = w[1].0 - w[0].0;
        time >= distance && (time - distance) % 2 == 0
    });
    writeln!(output, "{}", if possible { "Yes" } else { "No" }).unwrap();
}

fn main() {
    let stdin = io::stdin();
    let stdout = io::stdout();
    solve(stdin.lock(), stdout.lock());
}

#[cfg(test)]
mod tests {
    fn test(input: &str, output: &str) {
        let mut v: Vec<u8> = Vec::new();
        ::solve(input.as_bytes(), &mut v);
        assert_eq!(String::from_utf8(v).unwrap(), output);
    }

    #[test]
    fn case1() {
        test(
            "2
3 1 2
6 1 1
",
            "Yes\n",
        );
    }

    #[test]
    fn case2() {
        test(
            "1
2 100 100
",
            "No\n",
        );
    }

    #[test]
    fn case3() {
        test(
            "2
5 1 1
100 1 1
",
            "No\n",
        );
    }
}

Measured memory_bytes: 8444
#include<bits/stdc++.h>
using namespace std;
int main()
{int a,b,c;
 cin>>a>>b>>c;
 int q[a],w[b],n,m,k;
 int ans=INT_MAX,a1=INT_MAX,a2=INT_MAX;
 for(int i=0;i<a;i++)cin>>q[i],a1=min(a1,q[i]);
 for(int i=0;i<b;i++)cin>>w[i],a2=min(a2,w[i]);
 while(c--)
 {
 cin>>n>>m>>k;
   ans=min(ans,(q[n-1]+w[m-1]-k));
 }cout<<min(ans,a1+a2);
  return 0;
}


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

#define ll long long
#define ull unsigned long long 
#define endl '\n'
#define pii pair<int, int>
#define all(a) a.begin(),a.end()

int main(){
    int a, b, c, x;
    cin >> a >> b >> c >> x;
    int cnt=0;

    for(int i=0; i<=a; ++i){
        for(int j=0; j<=b; ++j){
            for(int k=0; k<=c; ++k){
                if(500*i + 100*j + 50*k == x){
                    cnt++;
                }
            }
        }
    }
    cout << cnt;
}

Measured memory_bytes: 3568
import java.util.Scanner;

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

    int N = scanner.nextInt();
    int K = scanner.nextInt();
    char[] s = scanner.next().toCharArray();
    int lr = 0;
    int rl = 0;
    for (int i = 0; i < N - 1; i++) {
      if (s[i] == 'L' && s[i + 1] == 'R') lr++;
      if (s[i] == 'R' && s[i + 1] == 'L') rl++;
    }
    int pairs = Math.min(lr, rl);
    int score = 0;
    for (int i = 0; i < N - 1; i++) if (s[i] == 'R' && s[i + 1] == 'R') score++;
    for (int i = 1; i < N; i++) if (s[i] == 'L' && s[i - 1] == 'L') score++;
    score += 2 * Math.min(pairs, K);
    lr -= pairs;
    rl -= pairs;
    K -= Math.min(pairs, K);
    if (K > 0 && (lr > 0 || rl > 0)) score++;
    System.out.println(score);
  }
}


Measured memory_bytes: 29476
# -*- coding: utf-8 -*-
"""
Created on Sat May  2 21:39:58 2020
"""

import sys
#import numpy as np

sys.setrecursionlimit(10 ** 9)
#def input():
#    return sys.stdin.readline()[:-1]
mod = 10**9+7

#N = int(input())
N, M = map(int,input().split())
#A = list(map(int,input().split()))
#graph = [[] for _ in range(N+1)]
#for _ in range(N-1):
#    a, b = map(lambda x : int(x)-1, input().split())
#    graph[a].append(b)
#    graph[b].append(a)

odd = (N % 2 != 0)
ans = []
if odd:
    x = N - 1
    for i in range(M):
        ans.append([i+1,x])
        x -= 1
else:
    x = N
    flg = True
    for i in range(M):
        if flg and x - (i+1) <= N//2:
            x -= 1
            flg = False
        ans.append([i+1,x])
        x -= 1
#        
#    for i in range(M//2 + 1,M):
#        ans.append([i+1,x-1])
#        x -= 1

for a in ans:
    print(' '.join(map(str,a)))
    

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

int main() {
    int n,k;
    while(true){
        cin>>n>>k;
        if(n==0)break;
        vector<int> a(n+1,0);
        for (int i = 1; i <= n; ++i) {
            cin>>a[i];
            a[i]+=a[i-1];
        }
        int ans=0;
        for (int i = 0; i+k < n; ++i) {
            ans=max(ans,a[i+k]-a[i]);
        }
        cout<<ans<<endl;
    }
    return 0;
}


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


signed main(){
	int N;
	cin >> N;
	int ans=1;
	for(int i=0;i<N;i++){
		if(i*i>N) {
			ans=i-1;
			break;
		}
	}
	
	cout<<ans*ans<<endl;
}



Measured memory_bytes: 256
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
#include<time.h>

int main()
{
    long n,j,i;
    scanf("%ld", &n);
    for (i = (long)sqrt(n); i >= 1;i--)
    {
        //printf("%d %d\n", i, n % i);
        if(n%i==0)
        {
            j = n / i;
            break;
        }
    }
    printf("%ld", i + j - 2);
    return 0;
}

Measured memory_bytes: 128
#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
#include <set>
#include <map>
#include <bitset>
using namespace std;
#define prev prev228
#define all(x) (x).begin(), (x).end()

const long long INF = 1e14;

int n;
int x[5000], y[5000];
vector<int> ans;
vector<char> s[5000];

int r(int x, int y)
{
    return abs(x) % y;
}

char U = 'U', D = 'D', L = 'L', R = 'R';
set<int> c;

int main()
{
    cin >> n;
    for (int i = 0; i < n; i++) cin >> x[i] >> y[i];
    for (int i = 0; i < n; i++)
    {
        c.insert(r(x[i] + y[i], 2));
    }
    if (c.size() > 1)
    {
        cout << -1, exit(0);
    }
    int gg = *c.begin();
    if (gg == 0)
    {
        for (int i = 0; i < n; i++)
            s[i].push_back(U), y[i]--;
        ans.push_back(1);
    }
    long long ss = 0;
    for (int i = 0; i < 31; i++)
    {
        ss += (1LL << i);
        ans.push_back(1LL << i);
    }
    cout << ans.size() << endl;
    for (int i = 0; i < ans.size(); i++) cout << ans[i] << " ";
    cout << endl;
    for (int i = 0; i < n; i++)
    {
        swap(x[i], y[i]);
        int nx = x[i] + y[i];
        int ny = x[i] - y[i];
        x[i] = nx, y[i] = ny;
        long long kekex = ss - nx, kekey = ss - ny;
        kekex /= 2;
        kekey /= 2;
        for (int j = 0; j < 31; j++)
        {
            int x = ((1 << j) & kekex) > 0;
            int y = ((1 << j) & kekey) > 0;
            if (!x && !y) s[i].push_back(U);
            if (!x && y) s[i].push_back(R);
            if (x && y) s[i].push_back(D);
            if (x && !y) s[i].push_back(L);
        }
        for (auto e : s[i]) cout << e;
        cout << "\n";
    }
}


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

int main(void){
	ll a,b;
	cin>>a>>b;
	if(a>12){
		cout<<b<<endl;
	}else if(a>5){
		cout<<b/2<<endl;
	}else{
		cout<<0<<endl;
	}
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define REP(i, n) for(int i = 0; i < n; i++)
#define REPR(i, n) for(int i = n; i >= 0; i--)
#define FOR(i, m, n) for(int i = m; i < n; i++)
#define INF 2e9
#define ALL(v) (v).begin(), (v).end()
using namespace std;
typedef long long ll;

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

int main()
{
	string s;
	cin >> s;
	int k;
	cin >> k;
	int len = (int)s.size();

	REP(i, k){
		if (len == i) break;
		if (s[i] != '1'){
			cout << s[i] << endl;
			return 0;
		}
	}

	cout << 1 << endl;


}


Measured memory_bytes: 256
import java.util.*;
public class Main{
 public static void main(String[] args){
   Scanner sc = new Scanner(System.in);
   int D = sc.nextInt();
   
   if(D==25) System.out.println("Christmas");
   else if(D==24) System.out.println("Christmas Eve");
   else if(D==23) System.out.println("Christmas Eve Eve");
   else if(D==22) System.out.println("Christmas Eve Eve Eve");
 }
}

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

#define FOR(i,n,j) for(int i=(j);i<(n);++i)
#define ssort(n) sort((n).begin(),(n).end())
#define rsort(n) sort((n).begin(),(n).end(),greater<ll>())
using ll=long long;
using ld=long double;
typedef pair<int,int> P;
typedef pair<P,int> COST;
#define repl(i,n) for(ll i=0;i<(n);++i)
#define Yes cout << "Yes" << endl
#define No cout << "No" << endl
#define YES cout << "YES" << endl
#define NO cout << "NO" << endl
using Graf=vector<vector<int>>;

int main()
{
    string s;
    cin >> s;
    vector<int> alph(26);
    rep(i,s.size()){
        alph[s[i]-97]++;
    }
    if(s.size()<=25){
        int c=26;
        int i=0;
        while(alph[i]!=0){
            i++;
        }
        c=i;
        cout << s+char(c+97) << endl;
    }else{
        if(s=="zyxwvutsrqponmlkjihgfedcba")cout << -1;
        else{
            string t=s;
            next_permutation(t.begin(),t.end());
            rep(i,s.size()){
                cout << t[i];
                if(s[i]!=t[i])return 0;
            }
        }
    }
    
}

Measured memory_bytes: 3636
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
typedef long long ll;

vector<int> cache(1 << 11, -1);

bool check(ll g, const vector<ll>& p, const vector<ll>& c, ll k,
           unsigned int state){
    if(g <= 0){ return true; }
    if(k <= 0){ return false; }
    if(cache.at(state) != -1){ return cache.at(state); }

    for(int i = 0; i < p.size(); ++i){
        if(state & (1 << i)){ continue; }
        if(k >= p.at(i)){
            ll g2 = g - c.at(i) - 100 * (i + 1) * p.at(i);
            if(check(g2, p, c, k - p.at(i), state | (1 << i))){
                cache.at(state) = 1;
                return true;
            }
        }else if(g <= 100 * (i + 1) * k){
            cache.at(state) = 1;
            return true;
        }
    }
    cache.at(state) = 0;
    return false;
}

int main(){
    ll d, g;
    cin >> d >> g;
    vector<ll> p(d);
    vector<ll> c(d);
    for(int i = 0; i < d; ++i){
        cin >> p.at(i);
        cin >> c.at(i);
    }

    for(int i = 1; i <= 1000; ++i){
        fill(cache.begin(), cache.end(), -1);
        if(check(g, p, c, i, 0)){
            cout << i << endl;
            return 0;
        }
    }
    return 0;
}


Measured memory_bytes: 384
s = input()
if((s[0]==s[1] and s[2]==s[3] and s[0]!=s[2]) or (s[0]==s[2] and s[1] ==s[3] and s[0]!=s[1])
   or (s[0]==s[3] and s[1]==s[2] and s[0]!=s[1])):
  print("Yes")
else:
  print("No")


Measured memory_bytes: 8924
#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
int main(){
	ll n,cnt=0,m=100;
	scanf("%lld",&n);
	for(;m<n;++cnt){
		m+=m/100;
	}
	printf("%lld\n",cnt);
	return 0;
}

Measured memory_bytes: 3756
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <queue>
#define print(n) std::cout << n << std::endl
#define print_no_indention(n) std::cout << n
using namespace std;


int main() {
   int a,b;
   cin >> a >> b;

   if(a == 1) a = 14;
   if(b == 1) b = 14;

   if(a > b) print("Alice");
   else if(a < b) print("Bob");
   else print("Draw");
}

Measured memory_bytes: 256
i,j,c,b,v,u,D[10000];main(N,K,T,U,V,L,x){
scanf("%d%d%d%d%d%d",&N,&K,&T,&U,&V,&L);
for(;i<N;i++)scanf("%d",&x),D[x]=1;
for(;j<L;b?v++,b--:u++,j++)if((c+=D[j])>K|(c&&!b))c--,b=T*V;
printf("%f\n",1.*v/V+1.*u/U);
exit(0);}

Measured memory_bytes: 668
#include<stdio.h>
int main(void)
{
	int n, k, x, y;
	int sum = 0;
	scanf("%d",&n);
	scanf("%d", &k);
	scanf("%d", &x);
	scanf("%d", &y);
	int i;
	for (i = 1; i <=n; i++)
	{
		if (i > k)
		{
			sum = sum + y;
			continue;
		}
		sum = sum + x;
	}
	printf("%d\n", sum);
	return 0;
}

Measured memory_bytes: 128
//#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i, n) for (int i = 0; i < (n); i++)
#define all(v) v.begin(), v.end()
#define allr(v) v.rbegin(), v.rend()


int main() {
  ll n;
  cin >> n;
  map<ll, ll> mp;
  rep(i, n) {
    ll a;
    cin >> a;
    mp[a]++;
  }
  ll a=0, b=0;
  for (auto p : mp) {
    if (p.second >= 2) {
      a = p.first;
    }
  }
  mp[a] -= 2;
  for (auto p : mp) {
    if (p.second >= 2) {
      b = p.first;
    }
  }
  cout << a*b << endl;
  return 0;
}

Measured memory_bytes: 6528
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define REP(i,n) for(ll i=0, i##_len=(n); i<i##_len; ++i)
#define REPR(i,n) for(ll i = n;i >= 0;--i)
#define FOR(i,m,n) for(ll i = m, i##_len=(n);i <i##_len; ++i)
#define all(x) (x).begin(),(x).end()
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; }
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
const int INF = 1e9;
const ll LLINF = 1e16;

ll modinv(ll a, ll m) {
    ll b = m, u = 1, v = 0;
    while (b) {
        ll t = a / b;
        a -= t * b; swap(a, b);
        u -= t * v; swap(u, v);
    }
    u %= m;
    if (u < 0) u += m;
    return u;
}


int main(void)
{
    int n,m;
    cin >> n >> m;
    vector<int> a(n);
    REP(i,n){
        cin >>a[i];
    }
    vector<pair<int,int>> op(m);
    REP(i,m){
        cin >> op[i].second >> op[i].first;
    }
    sort(all(a));
    sort(all(op),greater<pair<int,int>>());

    int left = 0;
    REP(i,m){
        int idx = upper_bound(a.begin()+left,a.end(),op[i].first) - a.begin() - 1;
        if(idx < left){
            break;
        }
        int range = min(idx,left + op[i].second - 1);
        for(int j = left;j<=range;j++){
            a[j] = op[i].first;
        }
        left = range + 1;
    }

    ll sum = 0;
    REP(i,n){
        sum += a[i];
    }

    cout << sum << endl;

    return 0;
}

Measured memory_bytes: 1408
# -*- coding: utf-8 -*-
#ABC130C
import sys


hoge=input()
#tmp = input().split()
#hoge = list(map(lambda a: int(a), tmp))
#n=hoge[0]
#m=hoge[1]

n=len(hoge)

ans=0
for i in range(0,n-1):
	if(hoge[i]!=hoge[i+1]):
		ans+=1
print(ans)




Measured memory_bytes: 3188
n, m = map(int,input().split())
if n==2 and m==2:
  print(0)
elif n==1 and m!=1:
  print(m-2)
elif m==1 and n!=1:
  print(n-2)
elif n==1 and m==1:
  print(1)
else:
  print((n-2)*(m-2))

Measured memory_bytes: 3060
#include<stdio.h>

int n,q,a[2001],m;

int rec(int i,int sum){
  if(sum==m)return 1;
  if(i>=n)return 0;
  return rec(i+1,sum) || rec(i+1,sum+a[i]);
}

int main(void){

  int i,j;

  scanf("%d",&n);
  for(i=0;i<n;i++)scanf("%d",&a[i]);

  scanf("%d",&q);
  for(i=0;i<q;i++){
    scanf("%d",&m);
    if(rec(0,0))printf("yes\n");
    else printf("no\n");
  }
  return 0;
}

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

int main(void) {
    int h, w;
    cin >> h >> w;
    char s[h][w];
    for (int i = 0; i < h; i++) {
        for (int j = 0; j < w; j++) {
            cin >> s[i][j];
            if (s[i][j] == '.') {
                s[i][j] = '0';
            }
        }
    }

    for (int i = 0; i < h; i++) {
        for (int j = 0; j < w; j++) {
            // 配列の値に周囲 8 マス中に存在する # の数を加算
            if (s[i][j] != '#') {
                for (int k = -1; k <= 1; k++) {
                    for (int l = -1; l <= 1; l++) {
                        if ((i+k < 0 || h <= i+k) || (j+l < 0 || w <= j+l)) {
                            continue;
                        }
                        if (s[i+k][j+l] == '#') {
                            int tmp;
                            tmp = (int)s[i][j];
                            tmp++;
                            s[i][j] = (char)tmp;
                        }
                    }
                }
            }
        }
    }

    for (int i = 0; i < h; i++) {
        for (int j = 0; j < w; j++) {
            cout << s[i][j];
        }
        cout << endl;
    }
}

Measured memory_bytes: 256
N,M=map(int,input().split())
ans=[10]*N
for i in range(M):
	s,c=map(int,input().split())
	if ans[s-1]!=10 and ans[s-1]!=c:
		print('-1')
		break
	else:
		ans[s-1]=c
else:
	if ans[0]==0 and len(ans)>1:
		print('-1')
	else:
		for i in range(N-1):
			if ans[i+1]==10:
				ans[i+1]=0
		if ans[0]==10:
			if len(ans)>1:
				ans[0]=1
			else:
				ans[0]=0
		A=0
		for i in range(N):
			A+=ans[i]*10**(N-i-1)
		print(A)

Measured memory_bytes: 3064
#include <stdio.h>
 
int gcd(int a, int b){
 
if(a<b){
int temp=a;
a=b;
b=temp;
}
 
int c;
 
do{
c=a%b;
a=b;
b=c;
}while(c!=0);
 
return a;
}
 
int lcm(int a, int b){
 
int c, va, vb;
 
c=gcd(a,b);
va=a/c;
vb=b/c;
 
return c*va*vb;
}
 
int main(void){
 
int a, b;
 
while(scanf("%d %d", &a, &b)!=-1){
 
printf("%d %d\n", gcd(a,b), lcm(a,b));
 
}
 
return 0;
}

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

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

#define p_ary(ary,a,b,i) do { cout << "["; for (int (i) = (a);(i) < (b);++(i)) cout << ary[(i)] << ((b)-1 == (i) ? "" : ", "); cout << "]\n"; } while(0)
#define p_map(map,it) do {cout << "{";for (auto (it) = map.begin();;++(it)) {if ((it) == map.end()) {cout << "}\n";break;}else cout << "" << (it)->first << "=>" << (it)->second << ", ";}}while(0)

struct block {
    int w,s,v;
    bool operator<(const block& a) const {
        return w+s < a.s+a.w;
    }
};

int main() {
    int n;
    cin >> n;
    vector<block> a(n);
    for (int i = 0;i < n;++i) cin >> a[i].w >> a[i].s >> a[i].v;
    sort(a.begin(),a.end());
    vector<vector<ll>> dp(n+1,vector<ll>(20010,0));
    for (int i = 0;i < n;++i) {
        dp[i+1] = dp[i];
        for (int j = 0;j <= a[i].s;++j) dp[i+1][j+a[i].w] = max(dp[i+1][j+a[i].w],dp[i][j]+a[i].v);
    }
    ll ans = 0;
    for (int i = 0;i < 20010;++i) ans = max(ans,dp[n][i]);
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 160640
#include<bits/stdc++.h>
#define ll long long
#define re register
#define cs const

using std::cerr;
using std::cout;
using pii=std::pair<int,int>;
#define fi first
#define se second

std::string inv(std::string s){
	std::string res="";
	std::reverse(s.begin(),s.end());
	for(char c:s)
		if(isupper(c))res+=c-'A'+'a';
		else res+=c-'a'+'A';
	return res;
}

int n;
std::string A;

void Main(){
	std::cin>>n>>A;
	if(A[0]=='0'){
		puts("Impossible");
		return ;
	}for(int re i=0;i<(1<<n);++i)
		if(A[i]=='1')for(int re j=i;j;j=i&(j-1))
			if(A[j]=='0'){
				puts("Impossible");
				return ;
			}
	std::vector<pii> p({{0,0}});
	for(int re s=0;s<(1<<n);++s)if(A[s]=='0'){
		bool flag=true;
		for(int re t=s&(s-1);t&&flag;t=s&(t-1))
			if(A[t]=='0')flag=false;
		if(!flag)continue;
		std::string q;
		for(int re i=0;i<n;++i)
			if(s&(1<<i)){
				if(q.empty())q+='a'+i;
				else q=(char)('a'+i)+q+(char)('A'+i)+inv(q);
			}
		int nw=0;
		for(char c:q){
			int i,dir;
			if(isupper(c))
				i=c-'A',dir=0;
			else 
				i=c-'a',dir=1;
			for(int j=nw+1;j<=i;++j)
				p.push_back({j,0});
			for(int j=nw-1;j>=i;--j)
				p.push_back({j,0});
			nw=i;
			if(dir){
				p.push_back({i,1});
				p.push_back({i+1,1});
				p.push_back({i+1,0});
				p.push_back({i,0});
			}else {
				p.push_back({i+1,0});
				p.push_back({i+1,1});
				p.push_back({i,1});
				p.push_back({i,0});
			}
		}
		for(int j=nw-1;~j;--j)
			p.push_back({j,0});
	}
	cout<<"Possible\n"<<(p.size()-1)<<"\n";
	for(auto t:p)cout<<t.fi<<" "<<t.se<<"\n";
}

inline void file(){
#ifdef zxyoi
	freopen("E.in","r",stdin);
#endif
}signed main(){file();Main();return 0;}



Measured memory_bytes: 512
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
typedef pair<ll, ll>PLL;
#define rep(i,n) for (int i = 0; i < (n); ++i)
ll MOD = 1e4+7;
int main() {
    int n;
    cin >> n;
    map<string, vector<pair<int, int>>> mp;
    rep(i, n) {
        string s;
        int p;
        cin >> s >> p;
        mp[s].emplace_back(p, i+1);
    }
    for ( auto tmp_mp : mp ) {
        vector<pair<int, int>> sort_v;
        for ( auto tmp_v : tmp_mp.second ) {
            sort_v.emplace_back(tmp_v);
        }
        sort(sort_v.begin(), sort_v.end());
        reverse(sort_v.begin() ,sort_v.end());
        for ( auto tmp_v: sort_v ) {
            cout << tmp_v.second << endl;
        }
    }
    return 0;
}



Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int const nax = 3e5 + 10;
vector <int> a[nax];
int h[nax];
int n, m;

int main () {

    scanf("%d %d", &n, &m);

    for (int i = 1 ; i <= n ; ++ i)
        scanf("%d", h + i);

    for (int i = 1 ; i <= m ; ++ i) {
        int u, v;
        scanf("%d %d", &u, &v);
        a[u].push_back(v);
        a[v].push_back(u);
    }

    int ans = 0;

    for (int i = 1 ; i <= n ; ++ i) {
        bool ok = true;

        for (int j : a[i])
            ok &= (h[i] > h[j]);

        if (ok) ++ ans;
    }

    cout << ans << endl;
}
/*
    Good Luck
        -Lucina
*/


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

#define times(n, i)      uptil(0, n, i)
#define rtimes(n, i)     downto((n) - 1, 0, i)
#define upto(f, t, i)    for(int _##i = (t), i = (f); i <= _##i; i++)
#define uptil(f, t, i)   for(int _##i = (t), i = (f); i <  _##i; i++)
#define downto(f, t, i)  for(int _##i = (t), i = (f); i >= _##i; i--)
#define downtil(f, t, i) for(int _##i = (t), i = (f); i >  _##i; i--)
typedef long double LD;
#define long long long

#if defined(EBUG) && !defined(ONLINE_JUDGE)
#define debug true
#define ln << endl
#else
#define debug false
#define ln << '\n'
#endif
#define tb << '\t'
#define sp << ' '



signed main() { // long: 64bit
    if(!debug) {
        cin.tie(0);
        ios::sync_with_stdio(0);
    }

    int N;
    scanf("%d",&N);

    vector<int> A(N);
    times(N, i) scanf("%d",&A[i]);

    long ans = LLONG_MAX;

    times(2, k) {
        long a = 0, s = 0;
        times(N, i) {
            s += A[i];
            if(k == i%2 && s<=0) {
                a += 1 - s;
                s = 1;
            } else if(k != i%2 && s>=0) {
                a += s - (-1);
                s = -1;
            }
        }
        ans = min(ans, a);
    }

    cout << ans ln;

    return 0;
}


Measured memory_bytes: 640
#include<iostream>
#include<string>
#include<algorithm>
#include<cmath>
#include<iomanip>
#include<cstring>
#include<map>
#include<vector>
#include<queue>
#include<stack>
#include<climits>
#include<set>
#include<utility>
#include<typeinfo>
using namespace std;
typedef long long int ll;
typedef pair<int, int> P;
typedef set<int> S;
#define rep(i, n) for(int i=0; i<n; i++)
const ll MOD=1e9+7;

int main(){

  int n, d[51];
  cin >> n;
  for(int i=0; i<n; i++){
    cin >> d[i];
  }
  int ans=0;
  for(int i=0; i<n; i++){
    for(int j=0; j<n; j++){
      if(i!=j){
        ans+=d[i]*d[j];
      }
    }
  }
  cout << ans/2 << endl;

	return 0;
}

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

const int MOD=1000000007;
const int INF=0x3f3f3f3f;
const ll INFL=0x3f3f3f3f3f3f3f3f;

int main() {
  string t; cin>>t;
  int sum=0;
  rep(i,6){
    if(t[i]=='1') sum++;
  }
  cout<<sum;
  return 0;
}


Measured memory_bytes: 256
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <string>
#include <math.h>
#include <functional>
#include <algorithm>
#include <utility>
#include <iomanip>

typedef long long Int;
#define REP(i,n) for(int i = 0 ; i < n ; ++i)
#define REPS(a,i,n) for(int i = a ; i < n ; ++i)
using namespace std;

vector<pair<double, int >>kumi1;
vector<pair<double, int >>kumi2;
vector<pair<double, int >>kumi3;

int main(){

	REP(i, 8){
		pair<double, int>tmp;
		cin >> tmp.second;
		cin >> tmp.first;
		kumi1.push_back(tmp);
	}
	REP(i, 8){
		pair<double, int>tmp;
		cin >> tmp.second;
		cin >> tmp.first;
		kumi2.push_back(tmp);
	}
	REP(i, 8){
		pair<double, int>tmp;
		cin >> tmp.second;
		cin >> tmp.first;
		kumi3.push_back(tmp);
	}

	sort(kumi1.begin(), kumi1.end());
	sort(kumi2.begin(), kumi2.end());
	sort(kumi3.begin(), kumi3.end());

	cout << fixed << setprecision(2) << kumi1[0].second << " " << kumi1[0].first << endl << kumi1[1].second << " " << kumi1[1].first << endl;
	kumi1.erase(kumi1.begin());
	kumi1.erase(kumi1.begin());
	cout << fixed << setprecision(2) << kumi2[0].second << " " << kumi2[0].first << endl << kumi2[1].second << " " << kumi2[1].first << endl;
	kumi2.erase(kumi2.begin());
	kumi2.erase(kumi2.begin());
	cout << fixed << setprecision(2) << kumi3[0].second << " " << kumi3[0].first << endl << kumi3[1].second << " " << kumi3[1].first << endl;
	kumi3.erase(kumi3.begin());
	kumi3.erase(kumi3.begin());

	auto aa = kumi1.begin();
	auto bb = kumi2.begin();
	auto cc = kumi3.begin();

	if (*aa < *bb){
		if (*aa < *cc){
			cout << fixed << setprecision(2) << aa->second << " " << aa->first << endl;
			kumi1.erase(aa);
		}
		else
		if (*aa > *cc){
			cout << fixed << setprecision(2) << cc->second << " " << cc->first << endl;
			kumi3.erase(cc);
		}
	}
	else{
		if (*bb < *cc){
			cout << fixed << setprecision(2) << bb->second << " " << bb->first << endl;
			kumi2.erase(bb);
		}
		else
		if (*bb > *cc){
			cout << fixed << setprecision(2) << cc->second << " " << cc->first << endl;
			kumi3.erase(cc);
		}

	}
	////////

	aa = kumi1.begin();
	bb = kumi2.begin();
	cc = kumi3.begin();

	if (*aa < *bb){
		if (*aa < *cc){
			cout << fixed << setprecision(2) << aa->second << " " << aa->first << endl;
			kumi1.erase(aa);
		}
		else
		if (*aa > *cc){
			cout << fixed << setprecision(2) << cc->second << " " << cc->first << endl;
			kumi3.erase(cc);
		}
	}
	else{
		if (*bb < *cc){
			cout << fixed << setprecision(2) << bb->second << " " << bb->first << endl;
			kumi2.erase(bb);
		}
		else
		if (*bb > *cc){
			cout << fixed << setprecision(2) << cc->second << " " << cc->first << endl;
			kumi3.erase(cc);
		}

	}

	return 0;
}

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

using ll = long long int;

const int MAX = (int)(1e5 + 5);
const ll INF = (ll)(1e10 + 5);

const int MAX_N = (int)(1e5 + 5);

int n;
ll a[MAX_N];

multiset<ll> mst;

int main(void) {
  // Here your code !
  scanf("%d", &n);

  for (int i = 0; i < n; ++i) {
    scanf("%lld", &(a[i]));
  }

  mst.insert(INF);

  for (int i = 0; i < n; ++i) {
    if (mst.empty()) {
      mst.insert(a[i]);
      continue;
    }

    auto ptr = mst.upper_bound(a[i] - 1);

    if (ptr == mst.begin()) {
      mst.insert(a[i]);
      continue;
    }

    auto prv = prev(ptr);
    mst.erase(prv);
    mst.insert(a[i]);
  }

  printf("%d\n", mst.size() - 1);

  return 0;
}


Measured memory_bytes: 5760
import java.util.Scanner;

public class Main {
	static int[][] bingo = new int[3][3];

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

		int n = Integer.parseInt(sc.next());
		int a = Integer.parseInt(sc.next());
		System.out.println(n*n-a);
	}


}


Measured memory_bytes: 21844
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <queue>
#include <functional>
#include <cstring>
#include <cmath>

using namespace std;
#define inputInt(a) int a; cin >> a; 
#define inputInt2(a,b) int a; int b; cin >> a >> b; 
#define inputInt3(a,b,c) int a; int b; int c; cin >> a >> b >> c;
#define inputLong(a) long a;cin >> a; 
#define inputIntArray(a,N) int a[N];for(int i=0;i<N;i++){cin >> a[i];}
#define inputIntArray2(a,b,N) int a[N]; int b[N]; for(int i=0;i<N;i++){cin >> a[i] >> b[i];}
#define output(answer) cout << answer << endl;
#define fN(i,N)    for(int i=0; i<N; i++)
#define fSE(i,s,e) for(int i=s; i<=e; i++)
#define ll long long
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; }

int main()
{
  //input
  inputInt2(N,K);
  vector<int> h(N);
  fN(i,N) cin >> h[i];
  sort(h.begin(), h.end());
  
  //main
  int C = (lower_bound(h.begin(),h.end(),K) - h.begin());
  int ans = N-C;
  
  
  // output
  output(ans);
    
  return 0;
}

Measured memory_bytes: 640
#include<iostream>
#include<vector>
using namespace std;
typedef long long ll;

int main(){
  ll n;
  cin >> n;
  ll one=0,two=0,four=0;
  for(ll i=0;i<n;i++){
    ll a;
    cin >> a;
    if(a % 4 == 0){
      four++;
    }else if(a % 2 == 0){
      two++;
    }else{
      one++;
    }
  }
  
  if(two >= 1 && four >= one){
    cout << "Yes" << endl;
    return(0);
  }else if(two == 0 && four >= one-1){
    cout << "Yes" << endl;
    return(0);
  }
  
  cout << "No" << endl;
  return(0);
}

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

using namespace std;

using ll = long long;
constexpr int mo = 1e9+7;
constexpr int inf = 1<<30;
constexpr ll infl = 1ll<<60;
constexpr ll mo2 = 998244353;
int main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);

    int k,n;
    cin>>k>>n;
    int num = 0;
    vector<int> ai(n);
    for(auto &a : ai) cin>>a;
    for(int i=0;i<n-1;++i){
        num = max(num,abs(ai[i+1]-ai[i]));
    }
    num = max(num,k-ai[n-1]+ai[0]);
    cout << k-num << endl;
    return 0;
}

Measured memory_bytes: 1024
#include <iostream>
#include <set>
#include <string>
#include <algorithm>
using namespace std;
int main(void){
    string a,b;
    cin>>a>>b;
    string s;
    for(int i=0;i<a.size()+b.size();i++){
        if(i%2==0){
            s+=a[i/2];
        }else{
            s+=b[i/2];
        }
    }
    cout<<s<<endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define repz(i, z, n) for (decltype(n) i = (z); i < (n); i++)
#define rep(i, n) for (decltype(n) i = 0; i < (n); i++)

#define REPZ(i, z, n) for (decltype(n) i = (z); i <= (n); i++)
#define REP(i, n) for (decltype(n) i = 0; i <= (n); i++)
#define ALL(v) v.begin(), v.end()
#define SIZE(v) ((ll)(v).size())
#define MAX(v) (*max_element(ALL(v)))
#define MIN(v) (*min_element(ALL(v)))
#define INF 1000000000000  // 1E+12

// 略
#define PB push_back
#define F first
#define S second
#define MP make_pair
#define READ cin >>
#define PRINT cout <<
#define PYES cout << "Yes" << endl;
#define POK cout << "OK" << endl;
#define PNO cout << "No" << endl;
#define PNG cout << "NG" << endl;

using namespace std;

// デバッグ用
void debug_out() { cout << endl; }
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
  cout << H << " ";
  debug_out(T...);
}

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

#ifdef _DEBUG
#define debug(...) debug_out(__VA_ARGS__)
#else
#define debug(...)
#endif

// typedef
typedef long long ll;
typedef unsigned long long ul;
typedef long double ld;

// const
// 円周率
const double pi = M_PI;
// mod用
// 1E+9 +7
const ll mod = (int)1e+9 + 7;
// 1s間で可能なループ回数2E+8回
// int        最大値2147483647         〜2E+9
// long long  最大値9223372036854775807〜9E+18
// 総和accumulate
// 単純リストvector<type> push_back
// 連想配列map<key,value> insert,
// 集合set<type>
// pair キーとバリューを格納 firstとsecondでアクセス
// 小数点指定 cout << fixed << setprecision(15) << endl;
// to_string<->stoi
// stoll(longlong)
// stod(double)
// deep copy v1->v2 copy(v1.begin(), v1.end(), back_inserter(v2) );
// 大文字65-90(-32)
// 小文字97-122(+32)

int main() {
  // faster
  // C言語流の入出力は使用できない
  ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
  int n;
  cin >> n;
  rep(i, n) {
    int temp;
    cin >> temp;
    if (temp % 2 == 0) {
      if (temp % 3 != 0 and temp % 5 != 0) {
        cout << "DENIED" << endl;
        return 0;
      }
    }
  }
  cout << "APPROVED" << endl;

  return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define mod 1000000007
using namespace std;
int n;
int a[200010];
int x[200010],cnt=0;
long long dp[200010];
long long ey[200010];

int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
	for(int i=1;i<=n;i++){
		if(a[i]!=a[i-1]){
			x[++cnt]=a[i];
		}
	}
	dp[0]=1;
	for(int i=1;i<=cnt;i++){
		dp[i]+=dp[i-1];
		dp[i]%=mod;
		dp[i]+=ey[x[i]];
		dp[i]%=mod;
		ey[x[i]]+=dp[i-1];
		ey[x[i]]%=mod;
	}
	printf("%d\n",dp[cnt]);
	
	return 0;
}

Measured memory_bytes: 4992
#include<stdio.h>
int main(void){
  
  char c;
  scanf("%c",&c);
  
  if(c <= 'z' && c >= 'a') {
    printf("a\n");
  }else if(c <= 'Z' && c >= 'A'){
    printf("A\n");
  }
  
  
  return 0;
}

Measured memory_bytes: 1596
import static java.lang.System.*;
import java.util.*;

public class Main {
	static Scanner sc = new Scanner(System.in);

	public static void main(String[] args) {
		
		while(true) {
			int n = sc.nextInt();
			if (n == 0) break;
			
			String s = Integer.toOctalString(n);
			s = s.replace("7","9").replace("6","8").replace("5","7").replace("4","5");
			
			out.println(s);
		}
	}
}



Measured memory_bytes: 73480
#include<stdio.h>
#include<stdlib.h>
#pragma GCC optimize("O2")
#pragma GCC optimize("O3")
#pragma GCC target("avx")
#define rep(i,N) for(int i=0;i<(int)N;i++)
typedef long unsigned int UL;
static inline char CH()
{
  static char buf[100000],*ptr1=buf,*ptr2=buf;
  return ptr1==ptr2&&(ptr2=(ptr1=buf)+fread(buf,1,100000,stdin),ptr1==ptr2)?EOF:*ptr1++;
}
static inline int IN(void)
{
  int x=0,f=0,c=CH();while(c<48||c>57){f^=c==45,c=CH();}
  while(c>47&&c<58){x=x*10+c-48,c=CH();}return f?-x:x;
}
static inline void OUT(long x){if(x<0)putchar('-'),x=-x;if(x>=10)OUT(x/10);putchar(x%10+48);}
static void radix(int bitsOffset,UL N,UL *source,UL *dest)
{
  //https://cubic.org/docs/download/radix_ar.c
  UL count[256],*cp,*sp,s,c,i;
  cp=count;
  for(i=256;i>0;--i,++cp)*cp=0;
  sp=source;
  for(i=N;i>0;--i,++sp){cp=count+(((*sp)>>bitsOffset)&0xff);++(*cp);}
  s=0;cp=count;for(i=256;i>0;--i,++cp){c=*cp;*cp=s;s+=c;}
  sp=source;for(i=N;i>0;--i,++sp){s=*sp;cp=count+((s>>bitsOffset)&0xff);dest[*cp]=s;++(*cp);}
}
static void Radix32(UL *source,int N)
{
  UL *temp =(UL*)malloc(N*sizeof(UL));
  radix(0,N,source,temp);
  radix(8,N,temp,source);
  radix(16,N,source,temp);
  radix(24,N,temp,source);
  free(temp);
}
int main(void)
{
  int N=IN(),x=CH(),p=0,m=0,z=0;UL A[N];
  long K=0,count=0,l=-1e18,r=-l,mid;while(x>47&&x<58){K=K*10+x-48,x=CH();}
  rep(i,N){x=IN();if(x>0)A[m+p++]=x;else if(x<0)A[p+m++]=x;else z++;}
  if(K>1l*m*p&&K<1l*m*p+1l*z*(N-1)/2)return puts("0"),0;
  Radix32(A,m+p);
  if(K<=1l*m*p)r=1l;else l=-1l;
  while(l<=r)
  {
    mid=(l+r)/2;count=0;
    if(mid>=0)
    {
      int plus=p-1,minus=m-1;count+=1l*z*(p+m)+1l*z*(z-1)/2+1l*p*m;
      rep(i,plus){while(1l*A[i]*A[plus]>mid){plus--;}if(i>=plus){break;}count+=1l*plus-i;}
      rep(i,minus){while(1l*A[m+p-1-i]*A[m+p-1-minus]>mid){minus--;}if(i>=minus){break;}count+=1l*minus-i;}
    }
    else{int low=0;rep(i,m){while(1l*A[low]*A[p+i]>mid&&low<p){low++;}count+=1l*p-low;}}
    if(count>=K)r=mid-1l;else l=mid+1l;
  }
  return OUT(l),0;
}

Measured memory_bytes: 4240
#include <regex>
#include "bits/stdc++.h"
#define FOR(i, s, e) for (int i = int(s); i < int(e); ++i)
#define REP(i, e) FOR(i, 0, e)
#define INF (INT_MAX / 2)
#define LINF (LLONG_MAX / 2)
#define EPS (1.0e-8)
#define mkpr make_pair
const int MGN = 10;
const int ARY_SZ_MAX = (int)1e7;
using namespace std;
using ll = long long; using ull = unsigned long long;
using vi = vector<int>; using vvi = vector<vi>;
using vc = vector<char>; using vvc = vector<vc>;
using vb = vector<bool>; using vvb = vector<vb>;
using vl = vector<ll>; using vvl = vector<vl>;
using vd = vector<double>; using vs = vector<string>;
using pii = pair<int, int>; using pll = pair<ll, ll>; using psl = pair<string, ll>;


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


  int N, R; cin>>N>>R;

  int  ans = 0;
  if (N>=10) {
    ans = R;
  } else {
    ans = R + 100*(10-N);
  }

  cout << ans << endl;


  return 0;
}


Measured memory_bytes: 256
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.stream.LongStream;

public class Main {

    public static void main(String[] args) throws Exception {
        try (BufferedReader reader = new BufferedReader(new InputStreamReader(System.in))) {
            String[] array = reader.readLine().split(" ");
            long A = Long.parseLong(array[0]);
            long B = Long.parseLong(array[1]);

            long gcd = gcd(A, B);
            List<Long> divisors = divisor(gcd);

            int ans = 0;
            for (Long divisor : divisors) {
                if (isPrime(divisor)) {
                    ans++;
                }
            }

            System.out.println(ans);
        }
    }

    public static long gcd(long A, long B) {
        while (true) {
            if (A >= B) {
                A = A % B;
                if (A == 0) {
                    return B;
                }
            } else {
                B = B % A;
                if (B == 0) {
                    return A;
                }
            }
        }
    }

    public static List<Long> divisor(long N) {
        List<Long> list = new ArrayList<Long>();
        for (long n = 1; n <= Math.sqrt(N); n++) {
            if (N % n == 0) {
                list.add(n);
                long n2 = N / n;
                if (n != n2) {
                    list.add(N / n);
                }
            }
        }

        Collections.sort(list);

        return list;
    }

    public static boolean isPrime(long N) {
        return LongStream.rangeClosed(2, (long) Math.sqrt(N)).allMatch(n -> N % n != 0);
    }

}


Measured memory_bytes: 26452
#include <iostream>
#include <iomanip>
#include <utility>
#include <cmath>
#include <random>
#include <vector>
#include <tuple>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <string>
#include <algorithm>
using namespace std;

#define rep(i,n) for(int i = 0; i<n; ++i)
#define REP(i,n) for(int i = 1; i<=n; ++i)
#define all(x) begin(perm),end(perm)
#define showall(obj) for(auto x:obj)cout<<x<<endl;
typedef long long ll;
typedef pair<int,int> ip;
typedef pair<ll,ll> lp;
typedef vector<int> vint;
typedef vector<ll> vll;
const int inf = 100100100;
const ll INF = 1LL<<60;
const int MOD = (int)1e9 + 7;

int main(){
    int x;cin>>x;
    double ans = 1;
    for(int i = 2; i<=32; ++i){
        for(int j = 2; pow(i,j)<=x; j++){
            ans= max(ans,pow(i,j));
        }
    }
    cout<<ans<<endl; return 0;
}


Measured memory_bytes: 256
#include<iostream>

using namespace std;

int main()
{
	int a,b;
	cin>>a>>b;
	if((a&&b<=13)&&(a&&b>=1))
	{
	if(a==b)
	{
		cout<<"Draw";
	}
	
	else if(a==1)
	{
		cout<<"Alice";
	}
	else if(b==1)
	{
		cout<<"Bob";
	}

	else if (a>b)
	{
		cout<<"Alice";
	}
	else if(a<b)
	{
		cout<<"Bob";
	}
}
	return 0;
}

Measured memory_bytes: 888
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();
		int c = sc.nextInt();
		for(int i=0;i<=10000;i++) {
			if(a*i % b == c) {
				System.out.println("YES");
				System.exit(0);
			}
		}
		System.out.println("NO");
	}
}

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

using namespace std;
using ll = long long;
#define int ll
using VI = vector<int>;
using VVI = vector<VI>;
using PII = pair<int, int>;

#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()
#define PB push_back

const ll LLINF = (1LL<<60);
const int INF = (1LL<<30);
const int MOD = 1000000007;

template <typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template <typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }
template <typename T> bool IN(T a, T b, T x) { return a<=x&&x<b; }
template<typename T> T ceil(T a, T b) { return a/b + !!(a%b); }
template<class S,class T>
ostream &operator <<(ostream& out,const pair<S,T>& a){
  out<<'('<<a.first<<','<<a.second<<')';
  return out;
}
template<class T>
ostream &operator <<(ostream& out,const vector<T>& a){
  out<<'[';
  REP(i, a.size()) {out<<a[i];if(i!=a.size()-1)out<<',';}
  out<<']';
  return out;
}

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

int dp[1<<10][10];
signed main(void)
{
  cin.tie(0);
  ios::sync_with_stdio(false);

  while(true) {
    int n;
    cin >> n;
    if(!n) break;
    string s;
    cin >> s;

    memset(dp, false, sizeof(dp));
    int now = 0;
    bool safe = true;
    REP(i, n) {
      if(s[i] == 'u') now = 0;
      else {
        dp[now][s[i]-'0'] = true;
        if(now & 1<<(s[i]-'0')) {
          safe = false;
          break;
        }
        now |= 1<<(s[i]-'0');
      }
    }

    if(!safe) {
      cout << "UNSAFE" << endl;
      continue;
    }

    REP(s1, 1<<10) REP(t1, 10) {
      if(!dp[s1][t1]) continue;
      // dp[s1][t1] と マージ
      REP(s2, 1<<10) REP(t2, 10) {
        if(!dp[s2][t2]) continue;
        bool cond1 = !(s1&s2) && (s2 & 1 << t1),
             cond2 = !(s1&s2) && (s1 & 1 << t2);
        if(cond1 && cond2) {
          safe = false;
        } else if(cond1) {
          dp[s1 | s2][t2] = true;
        } else if(cond2) {
          dp[s1 | s2][t1] = true;
        }
      }
    }

    if(safe) cout << "SAFE" << endl;
    else cout << "UNSAFE" << endl;
  }

  return 0;
}



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

#define rep(i, n) for (int i = 0; i < n; ++i)
#define ALL(a) (a).begin(), (a).end()

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

using ll = long long;
using ld = long double;
using P = pair<int, int>;
using DoP = pair<double, double>;
using edge = struct { int to; double cost;}; // edge x = {to, cost}

const int di[] = {0, 1, 0, -1, 1, 1, -1, -1};
const int dj[] = {1, 0, -1, 0, 1, -1, 1, -1};
const int INF = 1<<29;
const ll INF64 = 1ll << 45;
const int mod = 1000000007;

struct mint
{
  ll x; // typedef long long ll;
  mint(ll x = 0) : x((x % mod + mod) % mod) {}
  mint operator-() const { return mint(-x); }
  mint &operator+=(const mint a)
  {
    if ((x += a.x) >= mod)
      x -= mod;
    return *this;
  }
  mint &operator-=(const mint a)
  {
    if ((x += mod - a.x) >= mod)
      x -= mod;
    return *this;
  }
  mint &operator*=(const mint a)
  {
    (x *= a.x) %= mod;
    return *this;
  }
  mint operator+(const mint a) const
  {
    mint res(*this);
    return res += a;
  }
  mint operator-(const mint a) const
  {
    mint res(*this);
    return res -= a;
  }
  mint operator*(const mint a) const
  {
    mint res(*this);
    return res *= a;
  }
  mint pow(ll t) const
  {
    if (!t)
      return 1;
    mint a = pow(t >> 1);
    a *= a;
    if (t & 1)
      a *= *this;
    return a;
  }

  // for prime mod
  mint inv() const
  {
    return pow(mod - 2);
  }
  mint &operator/=(const mint a)
  {
    return (*this) *= a.inv();
  }
  mint operator/(const mint a) const
  {
    mint res(*this);
    return res /= a;
  }
};
// h(n, r) = c(n+r-1, r)
struct combination
{
  vector<mint> fact, ifact;
  combination(int n) : fact(n + 1), ifact(n + 1)
  {
    assert(n < mod);
    fact[0] = 1;
    for (int i = 1; i <= n; ++i)
      fact[i] = fact[i - 1] * i;
    ifact[n] = fact[n].inv();
    for (int i = n; i >= 1; --i)
      ifact[i - 1] = ifact[i] * i;
  }
  mint operator()(int n, int k)
  {
    if (k < 0 || k > n)
      return 0;
    return fact[n] * ifact[k] * ifact[n - k];
  }
};

int V, E;
vector<vector<int>> g(20, vector<int>(20, INF));
vector<vector<int>> dp(50000, vector<int>(20, 0));

int rec(int s = (1<<V)-1, int v = 0) {
  if(s == 0 && v == 0) return 0;
  if(s == 0 && v != 0) return INF;
  if(!(s & 1<<v)) return INF;

  if(dp[s][v] != 0) return dp[s][v];
  dp[s][v] = INF;
  rep(u, V) chmin(dp[s][v], rec(s^(1<<v), u) + g[u][v]);
  return dp[s][v]; 
}

int main(){
  cin >> V >> E;

  rep(i, E) {
    int s, t, d;
    cin >> s >> t >> d;
    g[s][t] = d;
  }
  int ans = rec();
  if(ans != INF) cout << ans << endl;
  else cout << -1 << endl;
}


Measured memory_bytes: 8544
#include<bits/stdc++.h>
#define ALL(c) (c).begin(),(c).end()
#define EACH(i,c) for(auto i=(c).begin();i!=(c).end();++i)
using namespace std;

int main(){
	int N;
	cin >> N;
	vector<int> a(N);
	map<int,int> b;
	for(int i = 0; i < N; ++i) {
		cin >> a[i];
		for(int j = -1; j <= 1; ++j) {
			b[a[i] + j]++;
		}
	}
	int res = 0;
	EACH(i, b) {
		res = max(res, i->second);
	}
	cout << res << endl;
	return 0;
}


Measured memory_bytes: 5120
a = int(input())
b = int(input())
c = int(input())
x = int(input())

def func(a, b, c, x):
    count = 0
    for i in reversed(range(a)):
        y = 500 * i
        if x < y:
            continue
        elif x == y:
            count += 1
            continue
        for j in reversed(range(b)):
            y = 500 * i + 100 * j
            if x < y:
                continue
            elif x == y:
                count += 1
                continue
            for k in reversed(range(c)):
                y = 500 * i + 100 * j + 50 * k
                if x < y:
                    continue
                elif x == y:
                    count += 1
                    break
                else:
                    break
    return count

count = func(a+1, b+1, c+1, x)
print(count)

Measured memory_bytes: 3064
#include<stdio.h>

#define LEN 100005
#define MAX 100000

typedef struct{
  char name[100];
  int t;
}P;

P g_Q[LEN];
int g_head,g_tail,g_n;

void enqueue(P);
P dequeue();
int isEmpty();
int isFull();

int main(){

  int elaps = 0, c;
  int i, q;
  P u;
  scanf("%d %d", &g_n, &q);

  for(i = 1; i <= g_n; i++){
    scanf("%s", g_Q[i].name);
    scanf("%d",&g_Q[i].t);
  }

  g_head = 1;
  g_tail = g_n+1;

  while(g_head != g_tail){
    u = dequeue();
    if(q < u.t) c = q;
    else c = u.t;
    u.t -= c;
    elaps += c;
    if(u.t > 0) enqueue(u);
    else printf("%s %d\n",u.name, elaps);
  }

  return 0;
}

int isEmpty(){
  if(g_head == g_tail) return 1;
  else return 0;
}

int isFull(){
  if(g_head == (g_tail + 1) % MAX) return 1;
  else return 0;
}

void enqueue(P x){
  if(isFull() == 1) fprintf(stderr,"error,enqueu\n");
  g_Q[g_tail] = x;
  if(g_tail + 1 == MAX) g_tail = 0;
  else g_tail++;
}

P dequeue(){
  P x;
  if(isEmpty() == 1) fprintf(stderr,"error,dequeu\n");
  x = g_Q[g_head];
  if(g_head+1 == MAX) g_head = 0;
  else g_head++;

  return x;
}
    



Measured memory_bytes: 11852
#include<bits/stdc++.h>
#define MAX_N 100001
#define INF_INT 2147483647
#define INF_LL 9223372036854775807
#define REP(i,n) for(int i=0;i<(int)(n);i++)
using namespace std;
typedef long long int ll;
typedef pair<ll,ll> P;
const int MOD = 1000000007;

int main()
{
  string A,B,C;
  cin >> A >> B >> C;
  cout << (char)(A[0]+('A'-'a')) << (char)(B[0]+('A'-'a')) << (char)(C[0]+('A'-'a')) << endl; 
  return 0;
}



Measured memory_bytes: 256
#include <bits/stdc++.h>
#define range(i,a,b) for(int (i)=(a);(i)<(b);(i)++)
#define rep(i,n) range(i,0,n)
using namespace std;

int main(void){
	while(1){
		string num;
		cin >> num;
		if(cin.eof())break;
		int ans=0;
		int coef=1;
		rep(i,num.size()){
			ans+=coef*(num[i]-'0');
			coef*=(9-i);
			coef/=(1+i);
		}
		cout << ans%10 << endl;
	}
	return 0;
}

Measured memory_bytes: 1184