My program works with tests like this:

4

0 00 0

10 11

And my program give right answers but WA#1. That my code, whats wrong??

#include <bits/stdc++.h>

using namespace std;

int n;
string ans,q;

int main()
{
    cin >> n;

    while (!cin.eof()) {                                     //while not eof reading
        getline(cin,q);                                      //read 1 line
        ans = "";

        for (int i = 0; i < q.length(); i++)                 //remove all except 0 and 1
            if (q[i] == '0' || q[i] == '1')
                ans += q[i];


        if (ans.length() < n-1 || ans.length() > n+1)         //if its empty continue
            continue;

        int pos_sum = 0;

        for (int i = 0; i < ans.length(); i++) {              //count sum of positions
            if (ans[i] == '1') {
                pos_sum += i+1;
            }
        }

        if (ans.length() > n) {                              //if there 1 unnecessary element check all
            bool fg = false;                                 //elements and remove him

            for (int i = 0; i < ans.length(); i++) {
                int loc_pos_sum = 0;

                if (fg) {
                    cout << ans[i];
                    continue;
                }

                for (int j = 0; j < ans.length(); j++) {
                    if (j == i)
                        continue;

                    if (ans[j] == '1')
                        loc_pos_sum += j+1 - int(j >= i);
                }

                if (loc_pos_sum % (n+1) == 0) {
                    fg = true;
                } else {
                    cout << ans[i];
                }
            }
        } else if (ans.length() < n) {                                 //if there 1 removed element
            bool fg = false;                                           //check all positions for him

            for (int i = 0; i <= ans.length(); i++) {
                int loc_pos_sum = 0;

                if (fg) {
                    cout << ans[i];
                    continue;
                }

                for (int j = 0; j < ans.length(); j++) {
                    if (ans[j] == '1') {
                        loc_pos_sum += j+1 + int(j >= i);
                    }
                }

                if (loc_pos_sum % (n+1) == 0) {
                    cout << 0;
                    fg = true;
                }

                if ((i+1+loc_pos_sum) % (n+1) == 0) {
                    cout << 1;
                    fg = true;
                }

                cout << ans[i];
            }
        } else {                                                          //if '0' replaced to '1' check all
            bool fg = false;                                              //elements and replace
            for (int i = 0; i < ans.length(); i++) {
                if (ans[i] == '1' && (pos_sum-i-1)%(n+1) == 0 && !fg) {
                    cout << 0;
                    fg = true;
                } else {
                    cout << ans[i];
                }
            }
        }

        cout << "\n";
    }
    return 0;
}

Edited by author 30.10.2018 16:07

For some inputs multiple answers are possible, e.g.:

4
1011

has two possible answers: 1111 and 1001. However only 1001 seems to be accepted.

Either the wording of the problem should be changed or the alternative answers should be accepted.

Somebody can give me test case 4?
I don't understand why it's wrong answer...

Edited by author 30.10.2018 11:59

#include <iostream>
#include <math.h>
using namespace std;

int Prime[15000], nPrime;
int mark[15000];

void sieve(int n)
{
    int i, j, limit=sqrt(15000)+2;

    mark[1]=1;  ///mark is not prime...so...

    for(i=4; i<=n; i+=2)
        mark[i]=1;

    Prime[nPrime++]=2;

    for(i=3; i<=n; i+=2)
        if(!mark[i])
        {
            Prime[nPrime++]=i;
            if(i<=limit)
            {
                for(j=i*i; j<=n; j+=i*2)
                    mark[j]=1;
            }
        }
}

int main()
{
    sieve(15000);
    int n;
    cin >> n;
    int arr[2000];
    //cout << Prime[n-1] << endl;

    for(int i=0; i<n; i++)
        {
            cin >> arr[i];
        }
    for(int i=0; i<n; i++)
        cout << Prime[arr[i]-1] << endl;

        return 0;
}

HHHHHH.KJDFDKJ(newline)
ADFFG

right answer

Hhhhhh.Kjdfdkj
adffg

I WA here for five times

Edited by author 25.07.2008 08:43

Edited by author 25.07.2008 08:54

subj

if you use dp, l, r can be (>30000).

Edited by author 26.10.2018 11:42

Edited by author 26.10.2018 11:42

You may just want to continue the sequence from sample, for me it was enough to get it for n = 5
{ 1, 3, 2, 6, 8, 4, 11, 5 } to start noticing the pattern.

Alternatively, just plug it into OEIS and come across A019444 with an explanation how to compute the answer :D

suppose the slope of line on the x>0 is k ,and slope of (0,0) to n
points is k1,k2,...kn then intersection point of x1==1/(k1-k),x2=1/(k2-k)...xn=1/(kn-k)
then we choose (x4-x1)/(x2-x1)==(x4'-x1')/(x2'-x1') and (x3-x2)/(x3-x4)==（x3'-x2'）/(x3'-x4')
we multiply these two equations guess what happens, yes: k is offset
then we can get (k4-k1)*(k3-k2)/((k2-k1)*(k3-k4))==(k4'-k1')*(k3'-k2')/((k2'-k1')*(k3'-k4'))
en.. this convert to string matching prolems,so suffix array can solve it

#include <iostream>
#include <cmath>

void rSqrt(void)
{
    unsigned long int n = 0;
    if (scanf("%lu", &n) != -1)
    ¦  rSqrt();
    else
    ¦   return;
    printf("%.4f\n", sqrt(n));
    return;
}

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

You have to divide the participants into equal teams (rounded)
For example, for "15 10" test - (1, 1, 1, 1, 1, 2, 2, 2, 2, 2)
Good luck :)

На каких значениях становить ввод?

I got TLE for both, straightforward sort-solution (n*logn) and Moore's algorithm (n).
You can avoid it using this line in your code:
- ios_base::sync_with_stdio(false);

Commands "cout" and "cin" are immensely slow and for large inputs, your code can get TLE.
Surprisingly, both approaches differ from each other only by 0.02 sec (with the aforementioned line included).

Here's my code-

#include <bits/stdc++.h>
using namespace std;

bool upp,downn,leftt,rightt,avleftt,avrightt,avupp,avdownn;


bool vis[105][105],vis2[105][105];
int dist[105][105];
int dist2[105][105];
int xmov[4]={0,-1,0,1};
int ymov[4]={-1,0,1,0};
int main()
{
    // cout << "Hello World!" << endl;
    ios::sync_with_stdio(false);
    for(int i=1;i<105;i++)for(int j=1;j<105;j++)dist[i][j]=INT_MAX;
    int n,m,l,x1,y1,x2,y2;
    cin>>n>>m>>l;
    cin>>x1>>y1;
    cin>>x2>>y2;

    queue <pair <int,int> > q;
    queue <int> distt;
    int ans=0;
    if(abs(x1-x2)+abs(y1-y2)==1){
        ans=1;
    }
    vis[x1][y1]=true;
    dist[x1][y1]=0;
    vis[x2][y2]=true;
    q.push(make_pair(x1,y1));
    distt.push(0);


    while(q.empty()==0){
        pair <int,int> topp=q.front();
        int curdist=distt.front();
        q.pop();
        distt.pop();
        int curx,cury,nextx,nexty;
        curx=topp.first;
        cury=topp.second;
        for(int i=0;i<4;i++){
            nextx=curx+xmov[i];
            nexty=cury+ymov[i];
            if(nextx>=1&&nextx<=n&&nexty>=1&&nexty<=m){

                if(vis[nextx][nexty]==false){
                    vis[nextx][nexty]=true;
                    q.push(make_pair(nextx,nexty));
                    distt.push(curdist+1);
                    dist[nextx][nexty]=curdist+1;
                }
            }
        }
    }


    q.push(make_pair(x2,y2));
    distt.push(-1);
    vis2[x2][y2]=true;
    dist2[x2][y1]=-1;
     while(q.empty()==0){
        pair <int,int> topp=q.front();
        int curdist=distt.front();
        q.pop();
        distt.pop();
        int curx,cury,nextx,nexty;
        curx=topp.first;
        cury=topp.second;
        for(int i=0;i<4;i++){
            nextx=curx+xmov[i];
            nexty=cury+ymov[i];
            if(nextx>=1&&nextx<=n&&nexty>=1&&nexty<=m){

                if(vis2[nextx][nexty]==false){
                    vis2[nextx][nexty]=true;
                    q.push(make_pair(nextx,nexty));
                    distt.push(curdist+1);
                    dist2[nextx][nexty]=curdist+1;
                }
            }
        }
    }

    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(i==x2&&j==y2){
                continue;
            }

            if(dist[i][j]!=INT_MAX){
                cout<<i<<" ::::: "<<j<<"\n";
                int totaldist=dist[i][j]+dist2[i][j];
                if(totaldist<=l){
                    ans=max(ans,max(abs(y2-j),abs(x2-i))+1);
                }
            }

        }
    }

    cout<<ans;
    return 0;
}

тест в примере верный? если нет можно правильный?

This problem can be solved using brute force. The asymptotics is O(n*2^n) but still the time limit is not hit, provided you use bit operations instead of generating arrays. For you beginners, I post my code here, but I strongly recommend to write this on your own first. The language I use is Java; nextInt() function returns the next integer from the input.

[code deleted]

Worst time is 0.187 sec, as reported by Timus.

Edited by moderator 21.10.2019 22:59

Please give me test 8!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!

a=int(input())
b=int(input())
i=a
w=0
while i<=b:
    w=w+1
    i=i+2
if (a%10==0):
    w=w-1
print(w)

1. DP,  f[i][j] represents when solving the substring from index i to j the minimum brackets should add. Then we have
    1) i <= j
    2) if i == j, then f[i][j] = 1. (you can add a bracket to match the one)
    3) if i < j, then f[i][j] = min(f[i][k], f[k+1][j])   i<=k<=(j-1)
    4) that's not the end.... a case when s[i] == s[j], get f[i+1][j-1]. should compare this value to above values in (3), and get the maximum.
 2. how to show the results
    when calculate f[i][j], you can use an array like ans[i][j] to record the way to get f[i][j]. for example, when f[i][j] get maximum when k = k1. so you can record k1 to ans[i][j]. Or f[i+1][j-1] get the maximum , you can record -1 to ans[i][j], or in the case i==j you get the maximum, set ans[i][j] to 0......
    Then you can get result by DFS.

hope it helps :)