akhauriyash/Code-Regression huggingface dataset:
//コンパイラ最適化用
#pragma GCC optimize("Ofast")
#define _GLIBCXX_DEBUG
//インクルード(アルファベット順)
#include<algorithm>//sort,二分探索,など
#include<bitset>//固定長bit集合
#include<chrono>//実行時間計測
#include<cmath>//pow,logなど
#include<complex>//複素数
#include<deque>//両端アクセスのキュー
#include<functional>//sortのgreater
#include<iomanip>//setprecision(浮動小数点の出力の誤差)
#include<iostream>//入出力
#include<iterator>//集合演算(積集合,和集合,差集合など)
#include<map>//map(辞書)
#include<numeric>//iota(整数列の生成),gcdとlcm,accumulate
#include<queue>//キュー
#include<set>//集合
#include<stack>//スタック
#include<string>//文字列
#include<unordered_map>//順序保持しないmap
#include<unordered_set>//順序保持しないset
#include<utility>//pair
#include<vector>//可変長配列
#include<bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> pll;
typedef pair<ll, int> pli;
typedef pair<int, int> pii;
typedef pair<ll, ld> pld;
typedef pair<pii, int> ppiii;
typedef pair<pii, ll> ppiill;
typedef pair<pll, ll> ppllll;
typedef pair<pli, int> pplii;
typedef map<int, int> mii;
typedef deque<ll> dll;
typedef queue<ll> qll;
typedef priority_queue<ll> pqll;
typedef priority_queue<ll, vector<ll>, greater<ll>> pqrll;
typedef vector<int> vint;
typedef vector<ll> vll;
typedef vector<vector<ll>> vvll;
typedef vector<vector<int>> vvint;
typedef vector<vector<pll>> vvpll;

//マクロ
//forループ
//引数は、(ループ内変数,動く範囲)か(ループ内変数,始めの数,終わりの数)、のどちらか
//Dがついてないものはループ変数は1ずつインクリメントされ、Dがついてるものはループ変数は1ずつデクリメントされる
#define REP(i,n) for(ll i=0;i<ll(n);i++)
#define REPD(i,n) for(ll i=n-1;i>=0;i--)
#define FOR(i,a,b) for(ll i=a;i<=ll(b);i++)
#define FORD(i,a,b) for(ll i=a;i>=ll(b);i--)
//xにはvectorなどのコンテナ
#define ALL(x) x.begin(),x.end() 
#define SIZE(x) ll(x.size()) 
//定数
#define INF 1000000000000 //10^12:∞
#define MOD 1000000007 //10^9+7:合同式の法
#define MAXR 100000 //10^5:配列の最大のrange
//略記
#define PB push_back //挿入
#define MP make_pair //pairのコンストラクタ
#define F first //pairの一つ目の要素
#define S second //pairの二つ目の要素
#define cin(x) cin >> x

signed main(){
    //入力の高速化用のコード
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    //入力
    string N;
    cin >> N;

    //vll X(N);
    //REP(i,N) cin >> X[i];


    //本文
    ll size = N.size();
    ll ans = 0;
    REP(i,size){
        ans += N[i]-'0';

    }
    //出力
    if(ans%9==0){
        cout << "Yes";return 0;
    }
    cout << "No" << endl;
    //REP(i,N) cout << ans.at(i) <<endl;
  return 0;
}


Measured memory_bytes: 3720
#include<bits/stdc++.h>
#define fori(j,n) for(ll i=j;i<n;i++)
#define forb(n,j) for(ll i=n-1;i>=0;i--)
#define endl "\n"
#define pb push_back
#define ll long long
#define mp make_pair
#define ff first
#define ss second
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
using namespace std;

ll sgn(ll x){
    if(x>0)
        return 1;
    if(x==0)
        return 0;
    return -1;
}
const ll N = 2e5 + 5;
ll n;
ll a[N];
int32_t main()
{
    IOS;
    ll b,k;
    cin>>b>>k;
    fori(0,b)
    {
        cin>>a[i];
    }
    sort(a,a+b);
    ll sum=0;
    fori(0,k)
    {
        sum+=a[i];
    }
    cout<<sum<<endl;
    return 0;
}




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

#define F first
#define S second
#define pb(x) push_back(x)
#define pf(x) push_front(x)
#define in(x) insert(x)
#define forr(i, a, b) for(int i = a;i <= b;i++)
#define sz(s) (int)(s.size())
#define all(x) x.begin(), x.end()
#define did_you_calis_enough ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define file(s) if (fopen(s".in", "r")) freopen(s".in", "r", stdin), freopen(s".out", "w", stdout)
#define int long long

using namespace std;

const int INF =  4294967295;
const int  N = 2e6 + 667;
const int mod = 1e9 + 7;
const int dx[] = {1, -1, 0, 0, 1, 1, -1, -1};
const int dy[] = {0, 0, 1, -1, 1, -1, 1, -1};
const double PI = acos(-1.0);


main() {
	did_you_calis_enough
	int n;cin >> n;n %= 1000;
	cout << ((n) ? (1000 - n) : 0);
}

//Coded by LoliThief

Measured memory_bytes: 3612
#include <iostream>
#include <string>
#include <vector>

using namespace std;

#define fore(l) for(auto && value:l)

int main()
{
    vector<int> values;
    auto cnt = 0;
    cin >> cnt;
    values.resize( cnt );
    for ( auto i = 0; i < cnt; i++ )
    {
        cin >> values[i];
    }

    auto res = 0;
    for ( auto i = 0; i < cnt - 2; i++ )
    {
        for ( auto j = i + 1; j < cnt - 1; j++ )
        {
            for ( auto k = j + 1; k < cnt; k++ )
            {
                const auto a = values[i];
                const auto b = values[j];
                const auto c = values[k];

                const auto s = (a + b + c) * 0.5f;
                const auto m = sqrtf(s * (s - a) * (s - b) * (s - c));
                if (a !=b && a != c && b != c && m > 0.0001f) {
                    res++;
                    //cout << i << "  " << j << "  " << k << endl;
                }
            }
        }
    }
    cout << res;
}


Measured memory_bytes: 3188
#include <bits/stdc++.h>
typedef long long ll;
#define rep(i,a,n) for(ll i = a;i < n;i++)
#define rrep(i,a,n) for(ll i = n; i >= a;i--)
#define index_check(i,n) if(i > n-1 || i < 0) continue; 
#define LINF 1e18
#define INF 1e9
using namespace std;

#define fs first
#define sc second

using P = pair<ll,ll>;
using Pll = pair<P,ll>;
using PQ = priority_queue<P,vector<P>,greater<P>>;


const ll MOD = 1e9+7;
 

signed main(){
    ll n,k;
    cin >> n >> k;
    ll a[n],f[n];
    rep(i,0,n) cin >> a[i];
    rep(i,0,n) cin >> f[i];

    sort(a,a+n);
    sort(f,f+n,greater<ll>());
    ll ok = (ll)(1e16),ng = -1;
    while(abs(ok-ng) > 1){
        ll mid = (ok+ng)/2;
        ll cnt = 0;
        rep(i,0,n){
            cnt += max((ll)ceil((double)a[i] - (double)mid/(double)f[i]),0LL);
        }

        if(cnt <= k){
            ok = mid;
        }
        else{
            ng = mid;
        }
    }

    cout << ok << endl;
    return 0;
}


Measured memory_bytes: 3456
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+10;
int n,a[N],sig[N];ll dp[N][10];
int main()
{
	scanf("%d%d",&n,&a[1]);
	for (int i=2;i<=n;i++){
		char ch;
		do ch=getchar();while (ch!='-'&&ch!='+');
		if (ch=='-') sig[i]=1;
		scanf("%d",&a[i]);
	}
	for (int i=0;i<=n;i++)
	for (int j=0;j<=5;j++)
		dp[i][j]=-1e16;
	dp[0][0]=0;
	for (int i=0;i<n;i++)
	for (int j=0;j<=5;j++){
		ll v=dp[i][j];int k=j+sig[i+1];
		dp[i+1][k]=max(dp[i+1][k],k&1?v-a[i+1]:v+a[i+1]);
		if (j) dp[i+1][k-1]=max(dp[i+1][k-1],k&1?v+a[i+1]:v-a[i+1]);
	}
	ll ans=-1e16;
	for (int i=0;i<=5;i++) ans=max(ans,dp[n][i]);
	printf("%lld\n",ans);
	return 0;
}

Measured memory_bytes: 8832
N,W = map(int,input().split())
w = [0 for _ in range(N)]
v = [0 for _ in range(N)]

for i in range(N):
    w[i],v[i] = map(int,input().split())

dp = [[0 for i in range(W+1)]for j in range(N+1)]
for i in range(N):
    for j in range(W+1):
        if j+w[i] <= W:
            dp[i+1][j+w[i]] = max(dp[i][j], dp[i][j]+v[i])
            dp[i+1][j] = max(dp[i+1][j],dp[i][j])
        else:
            dp[i+1][j] = max(dp[i+1][j],dp[i][j])
print(dp[-1][-1])

Measured memory_bytes: 171528
import java.util.*;

import static java.lang.System.*;

// https://atcoder.jp/contests/abc055/tasks/arc069_b
// 12:30-  ２つを固定すると4パターンしかないので全探索。O(n)
public class Main {

    static final char sheep = 'S';
    static final char wolf = 'W';

    static final char same = 'o';
    static final char diff = 'x';

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        char[] statements = sc.next().toCharArray();

        solver(N, statements);
    }

    public static void solver(int N, char[] statements) {

        char[] animals = new char[]{sheep, wolf};
        for (char a1 : animals) {
            for (char a2 : animals) {
                char[] ans = existPattern(a1, a2, N, statements);
                if (ans != null) {
                    out.println(String.valueOf(ans));
                    return;
                }
            }
        }
        out.println("-1");
    }

    // 与えれれた条件（1番目・2番目の動物、発言）から動物のパターンが存在するかチェックする
    // 存在する場合は、存在するパターンを返却する。なければNullを返却する
    public static char[] existPattern(char first_animal, char second_animal, int N, char[] statements){

        char[] ans = new char[N];
        ans[0] = first_animal;
        ans[1] = second_animal;

        char left_ani = first_animal;
        char center_ani = second_animal;
        char right_ani;

        // パターンを列挙
        for(int n=2; n<N; n++){
            char center_statement = statements[n-1];
            right_ani = rightAnimal(left_ani, center_ani, center_statement);
            ans[n] = right_ani;
            left_ani = center_ani;
            center_ani = right_ani;
        }

        //out.println(ans);

        // 1週回ったところで矛盾するかチェック
        // まだチェックしていない1番目と最後の動物の発言をチェック

        char last_before_animal = ans[N-2];
        char last_animal = ans[N-1];

        char first_statement = statements[0];
        char last_statement = statements[N-1];

        if (rightAnimal(last_animal, first_animal, first_statement) == second_animal &&
                rightAnimal(last_before_animal, last_animal, last_statement) == first_animal){
            return ans;
        }

        return null;
    }

    public static char rightAnimal(char left_ani, char center_ani, char center_statement){
        char right_ani;
        switch (center_ani) {
            case (sheep):
                switch (center_statement){
                    case (same):
                        right_ani = left_ani;
                        break;
                    default:
                        right_ani = diffAnimal(left_ani);
                }
                break;

            default:    // wolf
                switch (center_statement){
                    case(same):
                        right_ani = diffAnimal(left_ani);
                        break;
                    default:
                        right_ani = left_ani;
                }
        }
       return right_ani;
    }

    public static char diffAnimal(char animal){
        if(animal == sheep){
            return wolf;
        }
        return sheep;
    }
}


Measured memory_bytes: 24404
use proconio::*;
use proconio::marker::Chars;

fn main() {
    input! {
        s: Chars,
    }

    print!("{}", s.iter().collect::<String>());
    if *s.last().unwrap() == 's' {
        println!("es");
    }
    else {
        println!("s");
    }
}


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

int main(){
	int n, m, c;
  	cin >> n >> m >> c;
  	vector <int> b(m);
  	vector<vector<int>> a(n, vector<int>(m));
  	for(int i=0; i<m; i++){
      cin >> b[i];
    }
  	for(int i=0; i<n; i++){
    	for(int k =0; k<m; k++){
        	cin >> a[i][k];
        }
    }
  
  	int cnt = 0;
  	for(int k =0; k< n; k++){
		int sum = 0;
      for(int i = 0; i < m; i++){
     		sum += a[k][i]*b[i];
    	}
   
      if(sum +c >0){
      cnt++;
      }
    
    }
  cout << cnt << endl;
  
}

Measured memory_bytes: 256
use proconio::*;

#[fastout]
fn run() {
    input! {
        n: usize,
        mut a: [usize; n],
    }
    a.sort();
    let mut ans = a[n - 1];
    let mut cnt = 1;
    for a in a.iter().rev().skip(1) {
        let v = std::cmp::min(2, n - 1 - cnt);
        ans += *a * v;
        cnt += v;
    }
    println!("{}", ans);
}

fn main() {
    run();
}

Measured memory_bytes: 6244
# include <iostream>
# include <algorithm>
#include <array>
# include <cassert>
#include <cctype>
#include <climits>
#include <numeric>
# include <vector>
# include <string>
# include <set>
# include <map>
# include <cmath>
# include <iomanip>
# include <functional>
# include <tuple>
# include <utility>
# include <stack>
# include <queue>
# include <list>
# include <bitset>
# include <complex>
# include <chrono>
# include <random>
# include <limits.h>
# include <unordered_map>
# include <unordered_set>
# include <deque>
# include <cstdio>
# include <cstring>
using namespace std;
using LL = long long;
using ULL = unsigned long long;
constexpr long long MOD = 1000000000 + 7;
constexpr long long INF = std::numeric_limits<long long>::max();
const double PI = acos(-1);
#define fir first
#define sec second
typedef pair<LL, LL> Pll;
typedef pair<LL, pair<LL, LL>> Ppll;
typedef pair<LL, pair<LL, bitset<100001>>> Pbll;
typedef pair<LL, pair<LL, vector<LL>>> Pvll;
typedef pair<LL, LL> Vec2;
struct Tll { LL first, second, third; };
typedef pair<LL, Tll> Ptll;
#define rep(i,rept) for(LL i=0;i<rept;i++)
#define Mfor(i,mf) for(LL i=mf-1;i>=0;i--)
LL h, w, n, m, k, s, t, q, ans, sum, last, cnt, a[100];
struct Edge { LL to,cost; };
vector<Edge>vec[100];
string str;
bool f=0;
void YN(bool f) {
	if (f)
		cout << "YES" << endl;
	else
		cout << "NO" << endl;
}
void yn(bool f) {
	if (f)
		cout << "Yes" << endl;
	else
		cout << "No" << endl;
}
int main(){
	cin >> n >> m >> s;
	yn(n+m>=s);
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 100001;
const ll mod = 1e9+7;
int n, tot;
struct coo
{
    int x, y;
    int id;
}c[maxn];
bool cmp1(coo a, coo b){
  return a.x < b.x;
}
bool cmp2(coo a, coo b){
  return a.y < b.y;
}
int dx[maxn],dy[maxn];
struct Edge{
  int u, v;
  int cost;
}e[maxn*2];
bool cmp(Edge a, Edge b){
  return a.cost < b.cost;
}
int p[maxn];
int find(int x){return p[x] == x ? x : p[x] = find(p[x]);}
int main(){
  ios::sync_with_stdio(false);
  cin.tie(0);cout.tie(0);
  scanf("%d", &n);
  for(int i = 0; i <= n; i++) p[i] = i;
  for(int i = 1; i <= n; i++){
    scanf("%d%d", &dx[i], &dy[i]);
  }
  for(int i = 1; i <= n; i++)
  {
    c[i].x = dx[i]; c[i].y = dy[i];c[i].id = i;
  }
  sort(c+1,c+1+n,cmp1);
  for(int i = 2; i <= n; i++){
    e[tot].u = c[i].id;
    e[tot].v = c[i-1].id;
    e[tot].cost = c[i].x - c[i-1].x;
    tot++;
  }
  sort(c+1,c+1+n,cmp2);
  for(int i = 2; i <= n; i++){
    e[tot].u = c[i].id;
    e[tot].v = c[i-1].id;
    e[tot].cost = c[i].y - c[i-1].y;
    tot++;
  }
  sort(e,e+tot,cmp);
  ll ans = 0;
  int cnt = 0;
  for(int i = 0; i < tot; i++){
    int f = find(e[i].u);
    int t = find(e[i].v);
    if(f!=t){ans+=e[i].cost;p[f] = t;cnt++;}
    if(cnt == n-1)break;
  }
  printf("%lld\n", ans);
  return 0;
}

Measured memory_bytes: 4992
S = list(input())
n = len(S)
res = 0

for i in range(2 ** (n - 1)):
    sub = []
    for j in range(n - 1):
        if (i >> j) & 1 == 1:
            sub.append('+')
        else:
            sub.append('')            
    f = S[0]
    for k in range(n - 1):
        f += sub[k] + S[k + 1]
    res += eval(f)            

print(res)

Measured memory_bytes: 40944
str = gets.chomp.split("").map(&:to_i)
list = []
["+","-"].repeated_permutation(3) do |s|
  list << s
end
list.each do |a|
  moji = []
  str.each_with_index do |s, i|
    moji << s
    moji << a[i] if i < a.length
  end
  if eval(moji.join) == 7
    puts "#{moji.join}"+"=7"
    break
  end
end


Measured memory_bytes: 1788
#include <bits/stdc++.h>
#define For(i, a, b) for(int (i)=(int)(a); (i)<(int)(b); ++(i))
#define rFor(i, a, b) for(int (i)=(int)(a)-1; (i)>=(int)(b); --(i))
#define rep(i, n) For((i), 0, (n))
#define rrep(i, n) rFor((i), (n), 0)
#define fi first
#define se second
using namespace std;
typedef long long lint;
typedef unsigned long long ulint;
typedef pair<int, int> pii;
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;}
template<class T> T div_floor(T a, T b){
    if(b < 0) a *= -1, b *= -1;
    return a>=0 ? a/b : (a+1)/b-1;
}
template<class T> T div_ceil(T a, T b){
    if(b < 0) a *= -1, b *= -1;
    return a>0 ? (a-1)/b+1 : a/b;
}

constexpr lint mod = 1e9+7;
constexpr lint INF = mod * mod;
constexpr int MAX = 100010;

int n, m;
vector<int> G[MAX];
int c[MAX];
lint cnt[2];

bool dfs(int v, int col){
    if(c[v] >= 0) return c[v] == col;
    c[v] = col;
    ++cnt[col];
    for(int nv: G[v]){
        if(!dfs(nv, col^1)) return false;
    }
    return true;
}

int main(){
    scanf("%d%d", &n, &m);
    rep(i, m){
        int a, b;
        scanf("%d%d", &a, &b);
        --a; --b;
        G[a].push_back(b);
        G[b].push_back(a);
    }

    cnt[0] = cnt[1] = 0;
    fill(c, c+n, -1);
    if(dfs(0, 0)) printf("%lld\n", cnt[0]*cnt[1] - m);
    else printf("%lld\n", 1LL * n*(n-1)/2 - m);
}

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

int main() {
  int h, w;
  cin >> h >> w;
  vector<string> m(h);
  for (int i = 0; i < h; i++) cin >> m[i];
  vector<vector<int>> a(h, vector<int>(w));

  for (int i = 0; i < h; i++) {
    for (int j = 0; j < w; j++) {
      if (i == 0 && j == 0) {
        if (m[i][j] == '#') a[0][0] = 1;
      }
      else if (i == 0) {
        a[i][j] = a[i][j - 1];
        if (m[i][j] != m[i][j - 1]) a[i][j]++;
      }
      else if (j == 0) {
        a[i][j] = a[i - 1][j];
        if (m[i][j] != m[i - 1][j]) a[i][j]++;
      }
      else{
        int add1 = 0, add2 = 0;
        if (m[i][j] != m[i][j - 1]) add1++;
        if (m[i][j] != m[i - 1][j]) add2++;

        a[i][j] = min(a[i][j-1] + add1, a[i - 1][j] + add2);
      }

    }
  }

  cout << (a[h - 1][w - 1] + 1) / 2 << endl;

  return 0;
}

Measured memory_bytes: 256
#include <map>
#include <set>
#include <ctime>
#include <cmath>
#include <queue>
#include <stack>
#include <ctime>
#include <string>
#include <vector>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
//#include <random>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
#define PB push_back
#define MP make_pair
#define INF 1073741824
#define inf 1152921504606846976
#define pi 3.14159265358979323846
//#pragma comment(linker,"/STACK:10240000,10240000")
//mt19937 rand_(time(0));
const int N=3e5+7,M=2e6;
const long long mod=1e9+7;
inline int read(){int ret=0;char ch=getchar();bool f=1;for(;!isdigit(ch);ch=getchar()) f^=!(ch^'-');for(;isdigit(ch);ch=getchar()) ret=(ret<<1)+(ret<<3)+ch-48;return f?ret:-ret;}
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
ll ksm(ll a,ll b,ll mod){int ans=1;while(b){if(b&1) ans=(ans*a)%mod;a=(a*a)%mod;b>>=1;}return ans;}
ll inv2(ll a,ll mod){return ksm(a,mod-2,mod);}//逆元
//int head[N],NEXT[M],ver[M],tot;void link(int u,int v){ver[++tot]=v;NEXT[tot]=head[u];head[u]=tot;}

char str[12000];
int num[12000];
ll dp[12000][120];
int k;
ll dfs(int pos,bool up,int sum){
    if(pos==1){
        if(sum%k==0) return 1;
        return 0;
    }
    if(dp[pos][sum]!=-1&&!up) return dp[pos][sum];
    ll res=0;
    for(int i=0;i<=(up?num[pos-1]:9);i++){
        if(up&&i==num[pos-1]){
            res+=dfs(pos-1,1,(sum+i)%k);
        }
        else {
            res+=dfs(pos-1,0,(sum+i)%k);
        }
//        cout<<res<<endl;
        res%=mod;
    }
//    cout<<pos<<' '<<sum<<' '<<res<<endl;
    dp[pos][sum]=res;
    return res;
}
ll solve(){
    int len=strlen(str);
    int ant=0;
    for(int i=len-1;i>=0;i--){
        num[++ant]=str[i]-'0';
//        cout<<num[ant]<<' ';
    }
//    cout<<endl;
    return dfs(ant+1,1,0);
}
int main(){
    //freopen("1.txt","r",stdin);
    //ios::sync_with_stdio(false);
    scanf("%s",str);
    scanf("%d",&k);
    memset(dp,-1,sizeof(dp));
    printf("%lld\n",(solve()-1+mod)%mod);
    //cout << "time: " << (long long)clock() * 1000 / CLOCKS_PER_SEC << " ms" << endl;
    return 0;
}




Measured memory_bytes: 12544
import sys
input = sys.stdin.readline
from collections import deque

nn = 200200
mod = 10**9+7

fa = [1] * (nn+1)
fainv = [1] * (nn+1)
inv = [1] * (nn+1)
for i in range(nn):
    fa[i+1] = fa[i] * (i+1) % mod
fainv[-1] = pow(fa[-1], mod-2, mod)
for i in range(nn)[::-1]:
    fainv[i] = fainv[i+1] * (i+1) % mod
for i in range(1, nn)[::-1]:
    inv[i] = fainv[i] * fa[i-1]

C = lambda a, b: fa[a] * fainv[b] % mod * fainv[a-b] % mod if 0 <= b <= a else 0

N = int(input())
X = [[] for i in range(N)]
for i in range(N-1):
    x, y = map(int, input().split())
    X[x-1].append(y-1)
    X[y-1].append(x-1)

P = [-1] * N
Q = deque([0])
R = []
while Q:
    i = deque.popleft(Q)
    R.append(i)
    for a in X[i]:
        if a != P[i]:
            P[a] = i
            X[a].remove(i)
            deque.append(Q, a)

f = lambda a, b: a * b % mod
g_bu = lambda a, i=-1: a * inv[SI[i]] % mod
g_td = lambda a, i=-1: a * inv[N - SI[i]] % mod

SI = [1] * N
for i in R[::-1]:
    for j in X[i]:
        SI[i] += SI[j]

BU = [1] * N
TD = [1] * N
for i in R[::-1]:
    a = 1
    for j in X[i]:
        a = f(a, BU[j])
    BU[i] = g_bu(a, i)

for i in R:
    c = len(X[i])
    AL = [1] * (c + 1)
    AR = [1] * (c + 1)
    for k, j in enumerate(X[i]):
        AL[k+1] = f(AL[k], BU[j])
    for k in range(c-1, 0, -1):
        j = X[i][k]
        AR[k] = f(AR[k+1], BU[j])
    for k, j in enumerate(X[i]):
        TD[j] = g_td(f(TD[i], f(AL[k], AR[k+1])), j)

print(*[BU[i] * SI[i] % mod * TD[i] % mod * fa[N - 1] % mod for i in range(N)], sep = "\n")

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

using namespace std;
typedef long long ll;

string s;

int main(){
    cin >> s;
    int n = s.size();
    int max_len = 0;
    for(int i=0;i<n;i++){
        for(int j=1;i+j<=n;j++){
            string ss = s.substr(i,j);
            bool flag = true;
            for(const auto& e : ss){
                if(e != 'A' && e != 'C' && e != 'G' && e != 'T'){
                    flag = false;
                }
            }
            if(flag && max_len < j) max_len = j;
        }
    }
    cout << max_len << endl;
    return 0;
}


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

int main()
{
    int H, A;
    cin >> H >> A;

    int ans = 0;

    while (true)
    {
        H -= A;
        ans++;
        if (H <= 0)
        {
            break;
        }
    }

    cout << ans << endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <cmath>
#include <algorithm>
#include <queue>
#define rep(i,n) for (int i = 0; i < n; i++)
using namespace std;
typedef long long ll;

int main()
{
	string A, B;
	cin >> A >> B;
	if (A.size()>B.size())
	{
		cout << "GREATER";
		return 0;
	}
	else if (A.size() < B.size())
	{
		cout << "LESS";
		return 0;
	}
	else
	{
		int i = 0;
		while (i < A.size())
		{
			if (A[i]>B[i])
			{
				cout << "GREATER";
				return 0;
			}
			else if (A[i]<B[i])
			{
				cout << "LESS";
				return 0;
			}
			else
			{
				i++;
			}
		}
		cout << "EQUAL";
	}
	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define bug1(x) cout<<#x<<" = "<<x<<endl
#define bug2(x,y) cout<<#x<<" = "<<x<<" "<<#y<<" = "<<y<<endl
#define bug3(x,y,z) cout<<#x<<" = "<<x<<" "<<#y<<" = "<<y<<" "<<#z<<" = "<<z<<endl
#define bug4(x,y,z,m) cout<<#x<<" = "<<x<<" "<<#y<<" = "<<y<<" "<<#z<<" = "<<z<<" "<<#m<<" = "<<m<<endl

using namespace std;

class Debugger {
public:
	template<typename T>
	void printVector(vector<T> const &vec, bool printSize=true){
		if(printSize){
			cout << vec.size() << endl;
		}
		for(auto &elem : vec){
			cout << elem << " ";
		}
		cout << endl;
	}

	template<typename T>
	void printMatrix(vector<vector<T>> const &matrix){
		cout << matrix.size()<< " ";
		if(!matrix.empty()){
			cout << matrix[0].size();
		}
		cout << endl; 
		for(auto &vec : matrix){
			printVector(vec, false);
		}
		cout << endl;
	}
};

const int maxN = 100005;
const int INF = 1e9;
#define ll long long

class TaskA {
private:
	Debugger debugger;

public:
	void solveOne(int it){
		int x;
		cin >> x;
		for(int k = 1; ; k++){
			if( (x * k) % 360 == 0){
				cout << k << endl;
				return;
			}
		}
	}

	void solve(){
		int tc = 1;
		for(int it = 1; it <= tc; it++){
			solveOne(it);
		}
	}
};

int main(){
	srand(time(NULL));
	ios_base::sync_with_stdio(false);
	TaskA solver;
	solver.solve();
	return 0;
}


Measured memory_bytes: 3608
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const static ll INF = 1e9;
const static ll MOD = 1e9+7;


int main(){
    ll N; cin >> N;
    set<ll> ST, ST2;
    if(N % (N-1) != 0)ST2.insert(N-1);
    ST2.insert(N);

    for(ll K = 2; K*K  <= N; K++){
        ll temp = N;
        while(temp > 0){
            if(temp % K==0) temp /=K;
            else {temp %= K;}
            if(temp == 1){
                ST.insert(K);
                ST2.insert(K);
                break;
            } 
            if(temp == temp % K) break;
        }
    }
    for(auto st : ST) {
        if((N-1) % st == 0) {
            //if()
            ST2.insert((N-1)/st);
        }
    }
    //for(auto k : ST2) cout << " " <<k << endl;
    

    cout << ST2.size() << endl;
}

Measured memory_bytes: 256
A, B, C = map(int, input().split())

BC = min(B, C)
B -= BC
C -= BC

if C > 0:
    if A >= C:
        ans = BC * 2 + C
    else:
        ans = BC * 2 + A + 1
else:
    ans = BC*2+B


print(ans)


Measured memory_bytes: 2940
#include <algorithm>
#include <cmath>
#include <deque>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <set>
#include <string>
#include <vector>

using namespace std;
using LLONG = long long;
const LLONG MOD = 1000000007;

int main()
{
    string S;
    cin >> S;
    if (S == "SUN") cout << 7 << endl;
    if (S == "MON") cout << 6 << endl;
    if (S == "TUE") cout << 5 << endl;
    if (S == "WED") cout << 4 << endl;
    if (S == "THU") cout << 3 << endl;
    if (S == "FRI") cout << 2 << endl;
    if (S == "SAT") cout << 1 << endl;
}


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

using namespace std;

int main() {
	int n, t, a;
	cin >> n >> t >> a;
	vector<int> h(n);
	for (int i = 0; i < n; i++)
	{
		cin >> h[i];
	}
	double deg = DBL_MAX;
	int ans;
	for (int i = 0; i < n; i++)
	{
		double temp = fabs(a - (t - h[i] * 0.006));
		if (temp < deg) {
			deg = temp;
			ans = i + 1;
		}
	}

	cout << ans << endl;
	return 0;
}

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

int calc(int x, vector<int> b, const vector<int> &p) {
	const int n = b.size();

	int res = 0;
	int index = 0;

	for(const auto &e : p) {
		for(int i = 0; i < e; ++i) {
			int next_index = index;
			while(next_index < n && b[next_index] != x) ++next_index;

			if(next_index == n) return INT_MAX;
			res += next_index - index;
			swap(b[index], b[next_index]);
			++index;
		}

		x ^= 0x1;
	}
	return res;
}

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

	int n, m;
	cin >> n >> m;

	vector<int> b(n), p(m);
	for(auto &e : b) cin >> e;
	for(auto &e : p) cin >> e;

	cout << min(calc(1, b, p), calc(0, b, p)) << endl;

	return EXIT_SUCCESS;
}

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

using namespace std;

int main()
{
	int N;
	cin >> N;

	map<long long, long long> limit;
	long long A, B;
	string ans = "Yes";

	for (int i = 0; i < N; i++)
	{
		cin >> A >> B;
		map<long long, long long>::iterator it = limit.find(B);

		if (it == limit.end())
		{
			limit[B] = 0;
		}
		limit[B] += A;

		if (limit[B] > B)
		{
			ans = "No";
			break;
		}
	}

	if (ans == "Yes")
	{
		long long sum = 0;
		for (map<long long, long long>::iterator it = limit.begin(); it != limit.end(); it++)
		{
			it->second += sum;
			if (it->second > it->first)
			{
				ans = "No";
				break;
			}
			sum = it->second;
		}
	}
	
	cout << ans;
}

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

int main()
{
  int k;
  string s;

  cin >> k >> s;
  for (int i = 0; i < min(k, (int)s.size()); i++)
    cout << s[i];
  if (k < s.size())
    cout << "...";
  cout << endl;
}

Measured memory_bytes: 3632
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <cassert>
using namespace std;
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef vector<int> VI;
typedef long long ll;
typedef pair<int,int> PII;
const ll mod=1000000007;
ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
// head

struct point {
	int x,y,z;
	point() {}
	point(int x,int y,int z):x(x),y(y),z(z){}
};
vector<point> vs;
int a,b,c,n,x,y,z;
map<point,int> pt,del;
bool operator < (const point &a,const point &b) {
	return a.x<b.x||(a.x==b.x&&a.y<b.y)||(a.x==b.x&&a.y==b.y&&a.z<b.z);
}
bool valid(point p) {
	return p.x>=0&&p.x<a&&p.y>=0&&p.y<b&&p.z>=0&&p.z<c;
}
void dfs(point p) {
	vs.pb(p); del[p]=1;
	rep(dx,-1,2) rep(dy,-1,2) rep(dz,-1,2) {
		point q(p.x+dx,p.y+dy,p.z+dz);
		if (del.count(q)&&del[q]==0) dfs(q);
		if (valid(q)&&!del.count(q)) pt[q]=0;
	}
}
void dfs2(point p) {
	pt[p]=1;
	rep(dx,-1,2) rep(dy,-1,2) rep(dz,-1,2) if (abs(dx)+abs(dy)+abs(dz)==1) {
		point q(p.x+dx,p.y+dy,p.z+dz);
		if (pt.count(q)&&pt[q]==0) dfs2(q);
	}
}

int main() {
	scanf("%d%d%d%d",&a,&b,&c,&n);
	rep(i,0,n) {
		scanf("%d%d%d",&x,&y,&z);
		del[point(x,y,z)]=0;
	}
	vector<point> d;
	for (auto p:del) d.pb(p.fi);
	int ret=1;
	for (auto p:d) if (del[p]==0) {
		pt.clear();
		dfs(p);
		ret--;
		vector<point> vs;
		for (auto q:pt) vs.pb(q.fi);
		for (auto q:vs) if (pt[q]==0) {
			dfs2(q);
			ret++;
		}
	}
	printf("%d\n",ret);
}

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

signed main() {
  int N, A, B, C, D;
  cin >> N >> A >> B >> C >> D;
  string S;
  cin >> S;
  
  string T = S;
  if( C < D ){
    //Bについて
    bool fg = true;
    bool mae = false;
    for( int i = B-1; i < N; i++ ){
      if( mae == true && S.at(i) == '#' ){
        fg = false;
        break;
      }else if( mae == false && S.at(i) == '#' ){
        mae = true;
      }
      if( S.at(i) == '.' ) mae = false;
      if( i == D-1 ){
        break;
      }
    }
    mae = false;
    for( int i = A-1; i < N; i++ ){
      if( mae == true && S.at(i) == '#' ){
        fg = false;
        break;
      }else if( mae == false && S.at(i) == '#' ){
        mae = true;
      }
      if( S.at(i) == '.' ) mae = false;
      if( i == C-1 ){
        break;
      }
    }
    if( fg == true ){
      cout << "Yes" << endl;
    }else{
      cout << "No" << endl;
    }
  }else if( C > D ){
    bool san = false;
    bool fg = true;
    bool mae = false;
    for( int i = B-1; i < N; i++ ){
      if( B-1 <= i && i < D ){
        if( S.at(i-1) == '.' && S.at(i) == '.' && S.at(i+1) == '.' ) san = true;
      }
      if( mae == true && S.at(i) == '#' ){
        fg = false;
        break;
      }else if( mae == false && S.at(i) == '#' ){
        mae = true;
      }
      if( S.at(i) == '.' ) mae = false;
      if( i == D-1 ){
        break;
      }
    }
    if( fg == true && san == true ) cout << "Yes" << endl;
    else cout << "No" << endl;
  }
}


Measured memory_bytes: 772
#include<bits/stdc++.h>
#define MAX 100005
using namespace std;
 
int main(){
  int n, a, b, c, q, k, x, y;
  long long d[MAX];
  vector<pair<int,int>> v[MAX];
  queue<pair<int,int>> qu;
  scanf("%d", &n);
  for(int i = 0; i < n-1; i++){
    scanf("%d%d%d", &a, &b, &c);
    v[a].push_back(make_pair(b, c));
    v[b].push_back(make_pair(a, c));
  }
  scanf("%d%d", &q, &k);
  d[k] = 0;
  qu.push(make_pair(k, k));
  while(!qu.empty()){
    pair<int,int> p = qu.front(); qu.pop();
    for(vector<pair<int,int>>::iterator it = v[p.first].begin(); it != v[p.first].end(); it++){
      if(it->first == p.second) continue;
      d[it->first] = d[p.first] + it->second;
      qu.push(make_pair(it->first, p.first));
    }
  }
  for(int i = 0; i < q; i++){
    scanf("%d%d", &x, &y);
    printf("%lld\n", d[x] + d[y]);
  }
}

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

const int N = 2e5 + 5;
long long  n, k, ans, mn;

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
    	cin >> k;
    	if (k >= mn) mn = k;
    	else ans += mn - k;
    }
    cout << ans << endl;
    return 0;
}


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

bool chk(){

}

int main(){
  int a1 = 0;
  vector<vector<int>> d(3,vector<int>(3));
  vector<int> a(3);
  vector<int> b(3);
  for(int i=0;i<3;i++)for(int j=0;j<3;j++)cin >> d.at(i).at(j);
  int b1 = d.at(0).at(0);
  int a2 = d.at(1).at(0) -b1;
  int a3 = d.at(2).at(0) -b1;
  int b2 = d.at(0).at(1);
  int b3 = d.at(0).at(2);
  a.at(0) = a1;
  a.at(1) = a2;
  a.at(2) = a3;
  b.at(0) = b1;
  b.at(1) = b2;
  b.at(2) = b3;
  // vector<vector<int>> ans(3,vector<int>(3))
  bool chk = true;
  for(int i=0;i<3;i++){
    for(int j=0;j<3;j++){
      if(d.at(i).at(j) != a.at(i) + b.at(j)){
        chk = false;
      }
    }
  }
  if(chk){
    cout << "Yes" << endl;
  }
  else{
    cout << "No" << endl;
  }
}


Measured memory_bytes: 256
e,s=gets
h=Hash[gets.split.map(&:to_i).sort.chunk{|e|e}.map{|k,v|s||=k;[e=k,v.size]}]
 
puts h[s] == s*2+1-e && (s+1..e).all?{|e|h[e]&&h[e]>=2} ? "Possible" : "Impossible"

Measured memory_bytes: 1788
n=int(input())
num=[]
def ap(num1):
    num.append(num1)
for i in range(n):
    ap(list(map(int,input().split())))
num2=0
str1= lambda val: val[1]
num.sort(key=str1)
ans=0
for i in range(n):
    num2+=num[i][0]
    if num2>num[i][1]:
        ans=1
        break
if ans==1:
    print("No")
else:
    print("Yes")


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

#define INF (1e9+5)
using namespace std;
typedef long long ll;

ll mod = 998244353;
int a[100005];
int main() {
  int n;
  scanf("%d", &n);

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

  ll ans=1;
  for (int i=1; i<n+1; i++) {
    for (int j=0; j<a[i]; j++) {
      ans = 1ll*ans*a[i-1]%mod;
    }
  }
  printf("%lld\n", ans);
}


Measured memory_bytes: 640
N = int(input())
MOD = 10**9+7
ans = 1
for i in range(N):
  ans*=10
  ans%=MOD
sub = 2
for i in range(N):
  sub*=9
  sub%=MOD
sub2 = 1
for i in range(N):
  sub2*=8
  sub2%=MOD
print((ans-(sub-sub2))%MOD) 

Measured memory_bytes: 64204
#include<cstdio>
#include<vector>
#include<numeric>
#include<algorithm>

#define rep(i,n) for(int i=0;i<(n);i++)

using namespace std;

int main(){
	for(int n,d;scanf("%d%d",&n,&d),n;){
		vector<int> mis[100];
		rep(i,n){
			int m; scanf("%d",&m);
			mis[i].resize(m);
			rep(j,m) scanf("%d",&mis[i][j]);
		}

		int sum[100];
		rep(i,n) sum[i]=accumulate(mis[i].begin(),mis[i].end(),0);

		while(1){
			bool change=false;
			rep(i,n) if(mis[i].size()>0) {
				sum[i]-=mis[i].back();
				if(*max_element(sum,sum+n)-*min_element(sum,sum+n)<=d){
					mis[i].pop_back();
					change=true;
				}
				else{
					sum[i]+=mis[i].back();
				}
			}
			if(!change) break;
		}

		bool ok=true;
		rep(i,n) if(mis[i].size()>0) ok=false;
		puts(ok?"Yes":"No");
	}

	return 0;
}

Measured memory_bytes: 824
#include<stdio.h>
#define MAX 1000
#define NIL -1
struct Node_struct{int p, l, r;}; 
typedef struct Node_struct Node;
Node T[MAX];
int D[MAX], H[MAX];

int Sibling(int u){
  if(T[u].p == NIL) return NIL;
  if(T[T[u].p].l != u && T[T[u].p].l != NIL) return T[T[u].p].l;
  if(T[T[u].p].r != u && T[T[u].p].r != NIL) return T[T[u].p].r;
  return NIL;
}

void print(int u){
  int i, c, degree = 0;
  printf("node %d: parent = %d, sibling = %d, ", u, T[u].p, Sibling(u));
  if(T[u].l != NIL) degree += 1;
  if(T[u].r != NIL) degree += 1;
  
  printf("degree = %d, ", degree);
  printf("depth = %d, ", D[u]);
  printf("height = %d, ", H[u]);
  
  if(T[u].p == NIL) printf("root\n");
  else if(T[u].l == NIL && T[u].r == NIL) printf("leaf\n");
  else printf("internal node\n");
}

void calcDepth(int u, int p){
  if(u == NIL) return;
  D[u] = p;
  calcDepth(T[u].l, p + 1);
  calcDepth(T[u].r, p + 1);
}

int Height(int u) {
  int hei1 = 0, hei2 = 0;
  
  if(T[u].l != NIL) hei1 = Height(T[u].l) + 1;
  if(T[u].r != NIL) hei2 = Height(T[u].r) + 1;

  if(hei1 >= hei2) return H[u] = hei1;
  else return H[u] = hei2;
}

int main(){
  int i, n, root;
  int id, left, right;
  
  scanf("%d", &n);
  for(i = 0; i < n; i++) T[i].p = T[i].l = T[i].r = NIL;
  
  for(i = 0; i < n; i++) {
    scanf("%d%d%d", &id, &left, &right);
    
    T[id].l = left;
    if(left != NIL) T[left].p = id;
    
    T[id].r = right;
    if(right != NIL) T[right].p = id;
  }
  for(i = 0; i < n; i++){
    if(T[i].p == NIL) root = i;
  }
  
  //それぞれのノードの深さを求める (find depth of each node)
  calcDepth(root, 0);
  Height(root);
  
  //出力 (output)
  for(i = 0; i < n; i++) print(i);

  return 0;

}



Measured memory_bytes: 2104
#include<stdio.h>
int main()
{
  char a[4],b[4];
  scanf("%s",a);
  scanf("%s",b);
  if(a[1]==b[1]&&a[0]==b[2]&&b[0]==a[2]) printf("YES\n");
  else printf("NO\n");
  return 0;
}

Measured memory_bytes: 128
import sys
input = sys.stdin.readline

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

def main():
    mod=10**9+7
    N,M,K=MI()
    flag=0
    
    for i in range(N+1):
        for j in range(M+1):
            temp=i*M+j*N-(i*j)*2
            if temp==K:
                flag=1
                break
            
            
    if flag:
        print("Yes")
    else:
        print("No")

main()


Measured memory_bytes: 64392
#include <iostream>
#include <iomanip>
#include <sstream>
#include <cstdio>
#include <string>
#include <vector>
#include <algorithm>
#include <complex>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <cassert>
#include <climits>
#include <queue>
#include <set>
#include <map>
#include <valarray>
#include <bitset>
#include <stack>
using namespace std;

#define REP(i,n) for(int i=0;i<(int)n;++i)
#define FOR(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)
#define ALL(c) (c).begin(), (c).end()
typedef long long ll;
typedef pair<int,int> pii;
const int INF = 1<<29;
const double PI = acos(-1);
const double EPS = 1e-8;

string ba;

struct P {
  string s;
  int x, y;
  P(const string &s, int y, int x) : s(s),y(y),x(x) {}
};

int main() {
  int h,w;
  while(cin >> h >> w) {
    ba = "";
    REP(i,h) {
      string s; cin >> s;
      ba += s;
    }
    const string strdir = "URDL";
    map<char, int> mp;
    REP(i,4) mp[strdir[i]] = i;
    const int dx[] = {0,1,0,-1};
    const int dy[] = {-1,0,1,0};
    queue<P> Q;
    REP(i,h) REP(j,w) 
      REP(k,4) if (ba[i*w+j] == strdir[k]) Q.push(P(ba,i,j));
    map<string, pair<string, int> > pre;
    pre[ba] = make_pair("",0);
    string last;
    while(!Q.empty()) {
      P p = Q.front(); Q.pop();

      bool f = 0;
      REP(i,w*h) if (p.s[i] == 'o') f = 1;
      if (!f) {
        last = p.s;
        break;
      }

      // REP(i,h) {
      //   REP(j,w) cout << p.s[i*w+j];cout << endl;
      // }
      
      int y=p.y, x = p.x;
      int sd = mp[p.s[y*w+x]];
      //p.s[y*w+x] = '.';
      for (int dd=sd-1; dd<=sd+1; ++dd) {
        int d = (dd+4)%4;
        int yy=y, xx=x;
        while(1) {
          yy+=dy[d];
          xx+=dx[d];
          if (yy<0||yy>=h||xx<0||xx>=w) break;
          if (p.s[yy*w+xx] == 'o') {
            string next = p.s;
            next[y*w+x] = '.';
            next[yy*w+xx] = strdir[d];
            if (pre.count(next) == 0) {
              pre[next] = make_pair(p.s,d);
              Q.push(P(next,yy,xx));
            }
            break;
          }
        }
      }
    }
    vector<char> ans;
    for(string now=last; now!=""; now=pre[now].first) {
      //REP(i,h){REP(j,w)cout<<now[i*w+j];cout<<endl;}
      ans.push_back(strdir[pre[now].second]);
    }
    ans.pop_back();
    reverse(ALL(ans));
    FOR(it,ans) cout << *it; cout << endl;
  }
  
}

Measured memory_bytes: 8264
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define db double
#define pii pair<int,int>
#define pli pair<ll,int>
#define pil pair<int,ll>
#define pll pair<ll,ll>
#define mat vector<vector<int>>
const int inf = 1 << 30;
const ll linf = 1e18;
const db EPS = 1e-7;
template<class T> void chmin(T& x, T y){if(x > y) x = y;}
template<class T> void chmax(T& x, T y){if(x < y) x = y;}


ll X;
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> X;
    ll num = 100;
    ll cnt = 0;
    while(X > num){
        cnt++;
        num = num + (num / 100);
    }
    cout << cnt << endl;
    return 0;

}

Measured memory_bytes: 3648
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MOD = 1e9 + 7;
const int inf = 1e9;
const ll INF = 1e18;
const double pi = 3.14159265358979323846;
#define rep(i,n) for(int i=0;i<n;i++)

int main(){
	double n;cin>>n;
	double y=ceil(n/1.08);
	if((int)(y*1.08)==n) cout<<y<<endl;
	else cout<<":("<<endl;
}

Measured memory_bytes: 256
#include <cstdio>
#include <vector>
#include <algorithm>
#include <functional>
#include <map>
#include <set>
#include <string>
#include <iostream>
#include <cassert>
#include <cmath>
using namespace std;

struct WeightedUnionFind {
        int n;
        vector<pair<int, int>> parent; // (node, weight)
        WeightedUnionFind(int x) {
                n = x;
                parent.resize(n);
                for (int i = 0; i < n; i ++) parent[i] = make_pair(i, 0);
        }
        pair<int, int> find(int x) {
                if (parent[x].first == x) return parent[x];
                auto res = find(parent[x].first);
                return parent[x] = make_pair(res.first, parent[x].second + res.second);
        }
        bool same(int x, int y) {
                return find(x).first == find(y).first;
        }
        void unite(int x, int y, int val) {
                auto u = find(x);
                auto v = find(y);
                if (u.first == v.first) return;
                parent[u.first] = make_pair(v.first, v.second + val - u.second);
        }
        int diff(int x, int y) {
                return parent[x].second - parent[y].second;
        }
};

int main() {
        int n, m;
        scanf("%d %d", &n, &m);
        WeightedUnionFind wuf(n);
        for (int i = 0; i < m; i ++) {
                int l, r, d;
                scanf("%d %d %d", &l, &r, &d);
                l --, r --;
                if (wuf.same(l, r)) {
                        if (wuf.diff(l, r) != d) {
                                puts("No");
                                return 0;
                        }
                } else {
                        wuf.unite(l, r, d);
                }
        }
        puts("Yes");
        return 0;
}



Measured memory_bytes: 1152
#include <iostream>
#include <string>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <vector>
#include <stack>
#include <queue>
#include <utility>
#include <map>
#include <set>
#include <functional>
typedef long long ll;
using namespace std;
const int MOD = 1000000007;
int main(){
    int n,m;
    cin >> n >> m;

    bool flag = true;
    vector<int> ans(n,-1);
    for(int i = 0;i < m;i++){
        int s,c;
        cin >> s >> c;
        s--;
        if(s == 0 && c == 0 && n != 1){
            flag = false;
        }
        else if(ans[s] != -1 && ans[s] != c){
            flag = false;
        }
        ans[s] = c;
    }

    if(!flag){
        cout << -1 << endl;
        return 0;
    }

    for(int i = 0;i < n;i++){
        if(ans[i] == -1 && i == 0 && n != 1)ans[i] = 1;
        else if(ans[i] == -1)ans[i] = 0;
    }

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


Measured memory_bytes: 256
import java.math.BigInteger;
import java.util.*;

class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        BigInteger N = new BigInteger(sc.next());
        sc.close();

        boolean b = false;
        for (int i=1; i<10; i++) {
            BigInteger d[] = N.divideAndRemainder(new BigInteger(Integer.toString(i)));
            if (d[1].compareTo(BigInteger.ZERO)==0) {
                if (d[0].compareTo(BigInteger.TEN)==-1) {
                    b =true;
                    break;
                }
            }
        }

        if (b)
            System.out.println("Yes");
        else
            System.out.println("No");
    }
}

Measured memory_bytes: 22868
H, W = list(map(int, input().split()))

#迷路の作成
graph = [list(input()) for i in range(H)]
#迷路と同じ形の何もない空間を作成
ans = 0
for i in range(H):
    for j in range(W):
        costs = []
        for l in range(H):
            costs.append([-1] * W)
        sy = i
        sx = j
        if graph[sy][sx] == "#":
            continue
        costs[sy][sx] = 0
        q = [[sy, sx]]
        #移動方向
        di = [1, -1, 0, 0]
        dj = [0, 0, -1, 1]

        while len(q) != 0:
            y, x = q.pop(0)

            for k in range(4):
                t = y + di[k]
                u = x + dj[k]
                if not (0<=t<H and 0<=u<W):
                    continue
                if graph[t][u] == '#':
                    continue
                if costs[t][u] != -1:
                    continue
                costs[t][u] = costs[y][x] + 1
                q.append([t, u])
        ans = max(ans, max([max(d) for d in costs]))
print(ans)

Measured memory_bytes: 3192
A, B, K = map(int,input().split(" "))
c = 1

while c <= K:
    if A % 2 == 1:
        A -= 1
    A //= 2
    B += A
    a = A
    A = B
    B = a
    c += 1

if K % 2 == 0:
    print(A, B)

else:
    print(B, A)


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

#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;

const ll MOD = 1e9 + 7;

int n;
ll ans;

int main() {
	cin.tie(0)->sync_with_stdio(0);
	ll sum = 0;
	cin >> n;
	for (int i = 0; i < n; ++i) {
		ll a; cin >> a;
		ll change = (a % MOD) * (sum % MOD) % MOD;
		ans = (ans % MOD + change % MOD) % MOD;
		ans %= MOD;
		sum += a;
	}
	
	
	cout << ans;
}


Measured memory_bytes: 3652
while True:
    n, p = map(int, raw_input().split())

    if n == 0 and p == 0:
        break

    L = [0 for _ in range(n)]
    bowl, where = p, 0

    while True:
        if bowl > 0:
            bowl -= 1
            L[where % n] += 1
            if L[where % n] == p:
                print where % n
                break
        else:
            bowl += L[where % n]
            L[where % n] = 0
        
        where += 1



Measured memory_bytes: 4652
import java.util.Scanner;

public class Main {
	public static void main(String[] args) throws Exception {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int[] res = new int[4];
		for (int i = 0; i < N; i++) {
			String tmp = sc.next();
			if (tmp.equals("AC")) {
				res[0]++;
			} else if (tmp.equals("WA")) {
				res[1]++;
			} else if (tmp.equals("TLE")) {
				res[2]++;
			} else if (tmp.equals("RE")) {
				res[3]++;
			}

		}
		System.out.println("AC x " + res[0]);
		System.out.println("WA x " + res[1]);
		System.out.println("TLE x " + res[2]);
		System.out.println("RE x " + res[3]);

	}
}

Measured memory_bytes: 58448
#include<bits/stdc++.h>
using namespace std;
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int q;
	cin>>q;
	vector<int> v;
	for(int i=0;i<q;i++){
		int z;
		cin>>z;
		v.push_back(z);
	}
	int ans=0;
	sort(v.begin(),v.end());
	vector<int> vis(q,0);
	for(int i=0;i<q;i++){
		//cout<<v[i]<<endl;
		if(i>0 && v[i-1]==v[i]){
			vis[i-1]=1;
			vis[i]=1;
		}
		if(vis[i]==0){
			int z=v[i]*2;
			while(z<=v[q-1]){
				auto c=lower_bound(v.begin(),v.end(),z);
				if(*c==z){
					vis[c-v.begin()]=1;
				}
				z+=v[i];
			}
		}
	}
	for(auto c:vis)
		if(c==0)
			ans+=1;
	cout<<ans;
	return 0;
}


Measured memory_bytes: 5068
#include <iostream>
#include <bits/stdc++.h>
typedef long long int ll;
using namespace std;
#define pb(a) push_back(a)
#define mp(a,b) make_pair(a,b)
#define vvl vector<vector<ll>>
#define in(a) insert(a)
//#define rep(i,n) for(i=0;i<n;i++)
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
 

 int a[32]={1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51};
 int k; cin>>k;
 cout<<a[k-1];
return 0;


}

Measured memory_bytes: 256