if you get runtime in c#, it's probably stack overflow. So use bfs instead of dfs, it helped me!

InPut
5 5
1 4
4 5
5 1
1 2
2 3

OutPut
3 2 1 4 5 1

Please show 8 test

#include <iostream>
#include <vector>

using namespace std;

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

    vector<int> nums(n + 1, 1);

    for (int i = s; i <= n; i++)
    {
        for (int j = 101; j <= 200; j++)
        {
            if ((i * j) % 100 == 0 and (i * j) / 100 <= n)
            {
                nums[(i * j) / 100] = nums[(i * j) / 100] > nums[i] + 1 ? nums[(i * j) / 100] : nums[i] + 1;
            }
        }
    }

    cout << nums[n] << endl;

    return 0;
}

How one can mathematically prove that it is always optimal to send people in one direction with max number of seats?

if you got WA on this test try to change SHORT on INT or CHAR.
it looks like an error in task.

import math
m = int(input())
mass = [int(input()) for i in range(m)]
def bit_sieve(n):
    if n < 2:
        return []
    bits = [1] * n
    sqrt_n = int(math.sqrt(n)) + 1
    for i in range(2, sqrt_n):
        if bits[i - 2]:
            for j in range(i + i, n + 1, i):
                bits[j - 2] = 0
    return bits
for j in range(m):
    k = mass[j]
    sieve = bit_sieve(int(1.5 * k * math.log(k)) + 1)
    i = 0
    while k:
        k -= sieve[i]
        i += 1
    print(i + 1)

package main

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

func main(){
  scanner := bufio.NewScanner(os.Stdin)
  scanner.Scan()
  line := scanner.Text()
  s := strings.Fields(line)


  for ix := len(s) - 1; ix >= 0; ix--{
    i, _ := strconv.Atoi(s[ix])
    x := fmt.Sprintf("%.4f", math.Sqrt(float64(i)))
    fmt.Println(x)
  }
}

I try heap and sort to get AC using java, but memory usage is about 7M.
I browse the java submits, and find some top-rank solution only using about 3M memory.
e.g.
commit 9822957 by @hduads2022_20321226, 0.14 secs, 2908 KB.
commit 9290600 by @Mikhail, 0.109 secs, 1 272 KB.
how to lower the memory usage.

WA4: s1 is already palindrome.
ex: aba ababa
WA7: s1 consist of only one character.
ex: a aa

If you're having trouble with WA 5 or WA 6, try this test:

10 1
2 1
3 2
4 3
5 2
6 3
7 2
8 2
9 3
10 8
9 2

Correct answer is 2, 4 or 6.

Need help :))))

I think in future I will be a powerfull programmer

[code deleted]

Please help me I have WA on test 10.

Edited by moderator 13.02.2007 20:47

#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define sz(a) ((int)a.size())
#define re return
#define all(a) a.begin(),a.end()
#define int long long
#define rept(i,a,b) for(int i=(a);i<(b);i++)
#define rep(i,a) rept(i,0,a)
#define vi vector<int>
#define pii pair<int,int>
#define F first
#define S second
using namespace std;
const int MOD=1000000007,INF=1000000000000000000;
template<typename T>inline void Mx(T &a,T b){a=max(a,b);}
template<typename T>inline void Mi(T &a,T b){a=min(a,b);}
inline int ad(int &a,int b,int c=MOD){re a=(a+b)%c;}
template<typename T>inline T read(){T a;cin>>a;re a;}
inline bool is_digit(int msk,int d){re (msk>>d)&1;}
const int dx[4]={-1,1,0,0},dy[4]={0,0,-1,1};
struct thing{int a,b,c,id;}p[100005];
bool operator<(thing a,thing b){
    int p=a.a+b.c+max(a.b+a.c,b.a+b.b);
    int q=b.a+a.c+max(b.b+b.c,a.a+a.b);
    if(p==q)re a.a<b.a;
    re p<q;
}
int n;
void run(){
    cin>>n;
    rep(i,n)cin>>p[i].a>>p[i].b>>p[i].c,p[i].id=i+1;
    sort(p,p+n);
    int a=0,b=0,c=0;
    rep(i,n){
        a=a+p[i].a;
        b=max(a,b)+p[i].b;
        c=max(b,c)+p[i].c;
    }
    cout<<c<<"\n";
    rep(i,n)cout<<p[i].id<<" ";
    cout<<"\n";
}
signed main()
{
//    ios::sync_with_stdio(0);
//    cin.tie(0);cout.tie(0);
//    for(int tc=read<int>();tc;tc--)
        run();
    re 0;
}

Be careful.
It will play a circle when your Eps<=1e-10.
Because Cpp's double is unable to stop the Binary Search.

Sorry for my poor Eng

Here is test generator that helped me beat TLE!

-------------------
#include <stdio.h>

void test1()
{
    FILE* stream = freopen ("BusRoutes.big", "w", stdout);
    const int n = 1000;
    const int endp = 100000;
    int cur = endp;
    printf ("%d 100000\n", n);
    for (int i = 0; i < n; ++i) {
        int cnt = (cur == 100) ? 100 : 200;
        printf ("%d ", cnt);
        for (int j = 0; j < cnt; ++j) {
             printf ("%d ", cur--);
        }
        printf ("\n");
        cur += 100;
    }
    printf ("1 %d\n", endp);
    fclose (stream);
}

int main()
{
    test1();
    return 0;
}
-------------------

...........................

#include <stdio.h>
#include <stdlib.h>
int main(){
    int harry,larry,res,res1,c;
    scanf("%d %d",&harry,&larry);
    c=(harry+larry)-1;
    if(c<=10){
        res1=10-harry;
        res=10-larry;
        printf("%d %d \n", res1,res);


    }else


    return 0;

}