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;

}

"covers segment [0, M] completely" means:

0 1
2 3
does not cover [0,3] completely

0 1
1 3
covers [0,3] completely

4 3 2
1 2
2 3
2 4
3 4
1 4

correct answer is 0.

6 12
+.+-+-+-+-+-+-+-+-+-+-+.+
| | . . . . . . . . . | |
+.+.+-+-+-+-+-+-+-+-+.+.+
| | | . . . . . . . | | |
+.+.+.+-+-+-+-+-+-+.+.+.+
| | | | . . . . | | . . |
+.+.+.+.+.+.+.+.+.+.+-+-+
| . . | . . . . | . | . |
+.+.+-+.+.+.+.+.+.+.+.+.+
| | | . . . . . | . | . |
+.+.+.+.+.+.+.+.+.+.+.+.+
|1|2| . . . . . | . | . |
+-+-+.+.+.+.+.+.+.+.+.+.+

According to the problem statement, right answer is 37. But the solution which returns 40 also got AC.
So is the answer 40 or 37?

I had WA2 with std::cout and round|trunc|floor functions. Then I used printf("%.2f", result) and got WA4. What's going on with output requirements?

Hey, this is the test 16 - it was a long path to get there. What can possibly go wrong?

I don't understand why my prog don't work
Can you give me some data or advice

Edited by author 20.03.2007 14:04

Edited by author 20.03.2007 14:04