Wrong answer in test №17

http://ideone.com/06yGHW

Maybe someone could improve that solution and get AC with it.  Current status of that code is WA#8. I think it is quite boring and tedious to upgrade it to AC.  Maybe you can see how to upgrade it with small effort.

#include <stdio.h>
#include <algorithm>
#include <stack>
using namespace std;
#define MAXN 100
#define MAXM 10
int ship[MAXN];
int row[MAXM];
int exi[MAXN];
int N, M;

int cmp(const void* a, const void* b);
void divid(int m);
int main()
{
    scanf("%d%d", &N, &M);
    for(int i=0; i<N; i++)
        scanf("%d", &(ship[i]));
    for(int i=0; i<M; i++)
        scanf("%d", &(row[i]));

    for(int i=0; i<N; i++)
        exi[i] = 1;

    qsort(ship, N, sizeof(int), cmp);
    divid(M);

    return 0;
}

int cmp(const void* a, const void* b)
{
    int* x = (int*)a;
    int* y = (int*)b;
    return *y - *x;
}

void divid(int m)
{
    if(m > 1)
        divid(m-1);

    stack<int> s;
    int tot = row[m-1];
    int hav = 0;
    int i = 0;
    for(;;){
        while(i<N && (!exi[i] || ship[i]>(tot-hav))) i++;
        if(i >= N){
            for(;;){
                i = s.top();
                s.pop();
                hav -= ship[i];
                exi[i] = 1;
                i++;
                if(i < N)
                    break;
            }
            continue;
        }
        s.push(i);
        hav +=  ship[i];
        exi[i] = 0;
        i++;
        if(hav == tot){
            int sh_ind;
            int siz = s.size();
            printf("%d\n", siz);
            while(!s.empty()){
                sh_ind = s.top();
                s.pop();
                printf("%d ", ship[sh_ind]);
            }
            printf("\n");
            return;
        }
    }
}

####################################################
I used recursion alg. And I know there is error in this code because I didn't deal with the situation I called "data confliction" such as "5 = 2+3".But how to IMPROVE it ???

email:1813484947@qq.com



Edited by author 15.07.2017 20:00

Edited by author 16.07.2017 15:23

Pozhaluysta, kto-nibud', dayte mne hot' kakie testy k zadache 1070! A to vse testi, kotoriye u menya yest' moya programma prohodit, no na teste #1 dayot nepravil'niy otvet!
I obyasnite, pochemu mozhet byt' test:
"12.00 15.00
01.02 03.07
Answer: 0" ?

#include <iostream>

int main()
{
  int N;
  std:: cin >> N;
  /* dynamic memory allocation */
  int ** p = new int * [N];
  for (int i = 0; i < N; i++)
    p[i] = new int [N];

  /* initialize upper triangle matrix */
  p[0][N-1] = 1;
  int m, n;
  int ct = 1, value = 2, iter = 1, row = 0, column = N - 2;
  while (ct <= N - 1)
  {
    n = column, m = row;
    for (int i = 0; i <= iter; i++)
    {
      p[m++][n++] = value;
      value++;
    }

    iter++; ct++;
    column--;
  }

  /* initialize the lower triangle matrix */
  row = 1; column = 0, iter = N - 2;
  while (ct > 1)
  {
    n = column, m = row;
    for (int i = 0; i <= iter; i++)
    {
      p[m++][n++] = value;
      value++;
    }

    iter--; ct--;
    row++;
  }

  /* display matrix */
  for (int i = 0; i < N; i++)
  {
    for (int j = 0; j < N; j++)
      std::cout << p[i][j] << " ";
    std::cout << std::endl;
  }

  /* release memory */
  for (int i = 0; i < N; i++)
    delete[] p[i];
  delete[] p;

  return 0;
}

first i get acces violation in my code. and then i search what it acces violation, and then i remake my code, then submit again. still get WA #4, before i reamke the code it says Accces Violation in test #4. Can anybody help me?

This is my code.

#include <iostream>
using namespace std;

int n,ar[10000],p;

int main(){
    cin>>n;
    for (int i=1;i<=n*n;i++){
        cin>>p;
        ar[p]=p;
    }
    for (int i=1;i<=n*n;i++){cout<<ar[i]<<' ';}
}

Edited by author 15.07.2017 10:58

tried all mentioned test cases .all correct. still WA on #12.
using surfix array.any idea?

code here:

#include <cstdio>
#include <cstring>
int const N=220000;
int st[256], rank[2*N], rank1[2*N], count[N], tmp[N];
char a[N], b[N], s[N], max1;
int sa[N], height[N], si;
int main(){
    memset(st, 0, sizeof st);
    memset(rank, 0, sizeof rank);
    memset(rank1, 0, sizeof rank1);
    scanf("%s", b);
    int n1=strlen(b);
    for(int i=1; i<=n1; ++i)a[i]=b[i-1];
    for(int i=1; i<=n1; ++i)a[i+n1+1]=b[n1-i];
    a[0]=' ';
    a[n1+1]='#';
    int n=2*n1+1;
    a[n+1]='&';
    for(int i=1; i<=n; ++i)st[a[i]]=1;
    for(int i=1; i<=255; ++i)st[i]+=st[i-1];
    for(int i=1; i<=n; ++i)rank[i]=st[a[i]];

    int k=0;
    for(int p=1; k!=n; p+=p){
        memset(count, 0, sizeof count);
        for(int i=1; i<=n; ++i)count[rank[i+p]]++;
        for(int i=1; i<=n; ++i)count[i]+=count[i-1];
        for(int i=n; i>=1; --i)tmp[count[rank[i+p]]--]=i;

        memset(count, 0, sizeof count);
        for(int i=1; i<=n; ++i)count[rank[i]]++;
        for(int i=1; i<=n; ++i)count[i]+=count[i-1];
        for(int i=n; i>=1; --i)sa[count[rank[tmp[i]]]--]=tmp[i];

        memcpy(rank1, rank, sizeof rank1);
        rank[sa[1]]=k=1;
        for(int i=2; i<=n; ++i){
            if(rank1[sa[i]]!=rank1[sa[i-1]] or rank1[sa[i]+p]!=rank1[sa[i-1]+p])++k;
            rank[sa[i]]=k;
        }
    }
    k=0;
    for(int i=1; i<=n; ++i){
        if(rank[i]==1){
            k=0;
        }else{
            --k;
            if(k<0)k=0;
            while(a[i+k]==a[sa[rank[i]-1]+k])++k;
        }
        height[rank[i]]=k;
    }

    int max=-1;
    for(int i=2; i<=n; ++i){
        int p=sa[i];
        int q=sa[i-1];
        if((p-1)/n1 != (q-1)/n1){
            if(p+q+height[i]==n+2){
                if(height[i]>max){
                    max=height[i];
                    si=p;
                }
            }
        }
    }
    for(int i=si; i<si+max; ++i)printf("%c", a[i]);
    return 0;
}

THX :)

How is that possible that SASUKE UCHIHA got compilation error??
http://imgur.com/BB0osSN

#include <bits/stdc++.h>
#define pb push_back
#define fs first
#define sc second
#define INF (1e9+7)
#define forn(i,z,n) for( auto (i) = (z); (i) < (n); ++i)

using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;

struct node {
    int key;
    node *left, *right, *parent;
    node(int q, node *x, node *y, node *p)  {
        key = q;
        left = x;
        right = y; parent = p;
    }
};
node *tree  = NULL, *f = NULL;
void add_n( node *j, node *&z)  {
    if( z == NULL)  {
        z = new node(j->key,NULL,NULL,NULL);
        return ;
    }
    if( z->key >= j->key)  {
        if( z->left)  {
            add_n(j, z->left);
        }
        else  {
            z->left = j;
            j->parent = z;
        }
    }
    else  {
        if( z->right)  {
            add_n(j,z->right);
        }
        else  {
            j->parent = z;
            z->right = j;
        }
    }
}
void show( node *x)  {
    if( x != NULL)  {
        show(x->left);
        cout << x->key << ' ';
        show(x->right);
    }
    else return ;
}
node *find_min( node *root)  {
    if( root->left != NULL)  {
        return find_min(root->left);
    }
    else  {
        return root;
    }

}
void delete_n(node *root, int val )  {
    if( root == NULL)  return ;
    else if( val < root->key)  delete_n( root->left, val);
    else if( val > root->key) delete_n(root->right, val);
    else  {
        if( root->left == NULL && root->right ==NULL)  {
            //delete root;
            root = NULL;
        }
        else if( root->left == NULL)  {
            root->right->parent = root->parent;
            root = root->right;
            //delete root->right;
            root->right = NULL;
        }
        else if( root->right == NULL)  {
            root->left->parent = root->parent;
            root = root->left;
            //delete root->left;
            root->left = NULL;
        }
        else  {
            node *temp = find_min( root->right);
            temp->parent = root->parent;
            root = temp;
            delete_n( root->right, temp->key);
        }
    }
    return ;
}
void post( node *x)  {
    if( x != NULL)  {
        post(x->right);
        post(x->left);
        cout << x->key << ' ';
    }
}
void show_parents( node *z)  {
    if(z != NULL)  {
        show_parents(z->left);
        show_parents(z->right);
        if( z->parent != NULL)
            cout << z->key << ' ' <<  (z->parent->key) << endl;
    }
}
int main()  {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int n; cin >> n;
    vector <int> v;
    forn(i,0, n)  {
        int x;
        cin >> x;
        v.pb(x);
    }
    for(int i = 0; i <n; ++i)  {
        node *help = new node(v[i], NULL, NULL,NULL);
        add_n( help, tree);
    }
    show(tree);                              // в невозрастающем порядке
    delete_n(tree, 3);
    cout << endl;
    show(tree);
    return 0;
}

#include<iostream>
#include<string>
using namespace std;
int main ()
{
    string s;
    cin>>s;
    int max=0,i=0,index=0,a=0,p=0;
    for (i=0; i<s.size()-5; i++)
    {
    if(s[i]>'a' && s[i]<='z')
    p--;
    if(s[i]=='S')
    p+=2;
    if(s[i+1]=='a')
     p+=2;
    if(s[i+1]>='A' && s[i+1]<='Z')
     p--;
    if(s[i+2]=='n')
    p+=2;
    if(s[i+2]>='A' && s[i+2]<='Z')
    p--;
    if(s[i+3]=='d')
    p+=2;
    if(s[i+3]>='A' && s[i+3]<='Z')
    p--;
    if(s[i+4]=='r')
    p+=2;
    if(s[i+4]>='A' && s[i+4]<='Z')
    p--;
    if(s[i+5]=='o')
    p+=2;
    if(s[i+5]>='A' && s[i+5]<='Z')
     p--;
        if (p>max)
        {
            max=p;
            index=i;
        }
        p=0;
            }
    i=index;
    if (s[i]!='S' && s[i]>='A' && s[i]<='Z' || s[i]=='s')
    a+=5;
    else if (s[i]!='S' && s[i]>='a' && s[i]<='z')
    a+=10;
    if (s[i+1]!='a' && s[i+1]>='a' && s[i+1]<='z' || s[i+1]=='A')
    a+=5;
    else if (s[i+1]!='a' && s[i+1]>='A' && s[i+1]<='Z')
    a+=10;
    if (s[i+2]!='n' && s[i+2]>='a' && s[i+2]<='z' || s[i+2]=='N')
    a+=5;
    else if (s[i+2]!='n' && s[i+2]>='A' && s[i+2]<='Z')
    a+=10;
    if (s[i+3]!='d' && s[i+3]>='a' && s[i+3]<='z' || s[i+3]=='D')
    a+=5;
    else if (s[i+3]!='d' && s[i+3]>='A' && s[i+3]<='Z')
    a+=10;
    if (s[i+4]!='r' && s[i+4]>='a' && s[i+4]<='z' || s[i+4]=='R')
    a+=5;
    else if (s[i+4]!='r' && s[i+4]>='A' && s[i+4]<='Z')
    a+=10;
    if (s[i+5]!='o' && s[i+5]>='a' && s[i+5]<='z' || s[i+5]=='O')
    a+=5;
    else if (s[i+5]!='o' && s[i+5]>='A' && s[i+5]<='Z')
    a+=10;
    cout<<a<<endl;
    return 0;
}

Edited by author 30.12.2014 18:40

Edited by author 03.01.2015 17:13

Edited by author 03.01.2015 17:13

1)Look at my solution 7450309 (Runtime error (non-zero exit code) on test 23)) and 7450312(AC). Why i got Runtime error (non-zero exit code) on test 23?
  In first solution i have nmax=123456 and in second 223456. What is range of n?

2)Look on problem 1974. In forum i wrote test when my AC solution get wrong answer(I can write more tests where my old AC solution falls)

I have solved it by reduction to a graph exploration task.
Each vertex consists of three parameters (i, j, pr).
Where i, j denote number of card at the top of each pile and pr denotes previous state.  pr is also a "used"  array.  So,  if pr[N] [N] =none,  then impossible.  Otherwise  just recover answer using pr.  You can also have in your state additional parameter diff denotes difference between red and black cards.  I have used instead additional two arrays diff11 and diff2 denote difference between first i cards in first pile and in the second pile respectively.  There is an edge iff difference at the next step would be not greater than one (abs) ,  obviously.

//I have correct in the IDE, what's wrong?

import java.io.IOException;
import java.util.Scanner;

public class VasyaCare{
    public static void main(String[] args) throws IOException {
    VasyaCare vasya_care = new VasyaCare();
    Scanner scn = new Scanner(System.in);
    int n = scn.nextInt();
    try{                               // Check
            if(n < 10){
        double[] b = vasya_care.setScore(n);
        double median = vasya_care.getMedian(b);
        if(median==3){
            System.out.println("None");
        }
        else if(median==5){
            System.out.println("Named");
        }
        else if(median >= 4.5){
            System.out.println("High");
        }
        else if(median < 4.5){
            System.out.println("Common");
        }
        }
        else throw new IOException("Please, type number from 1 to 10!");
    }
    catch(Exception e){e = new IOException();}
    }


    double getMedian(double[] b{          // calculate median score of exam
    int sum = 0;
    for(int i = 0; i < b.length; i++){
        sum = (int) (sum + b[i]);
    }
    return (double)sum/b.length;
    }

    double[] setScore(int n){            // forming list scores
    Scanner scn = new Scanner(System.in);
    double[] b = new double[n];{
        for(int j = 0; j < n; j++){
            int m = scn.nextInt();
            if(m<3 || m > 5){
                System.out.println("Type score from 3 to 5: ");
                j--;
            }
            else if (m>=3 && m<=5){
                b[j] = m;
            }
        }
    }
    return b;
    }
}

// Thank you for your attention!

Let unsigned long long total_cost=0.
For every edge E in tree total_cost +=cost_of_all_paths_lies_on_edge(E).
double ans=2.0*total_cost/n/(n-1) is overflow and and WA#19.
================
Let double ans = 0.
For every edge E in tree ans+=2.0*cost_of_all_paths_lies_on_edge(E)/n/(n-1).
That is AC.
===========
Maybe if not multiply by two in the first scenario there is also AC,  I have not tested.

Could anyone help me?

5
AAAAA
ans:5.000

6
CBDCBD
ans:3.600

6
DDADDD
ans:2.000
They helped me to solve this problem~
Hope they can help you
o(∩_∩)o...

0-1 bfs on graph with 2 * n verticles.

how to solve this problem?
construct suffix tree for N times and then LCP or there is easier and faster way?

Is it possible to solve this problem using suffix automata? I got TL5.
But I think that O(N * K) solution have to work faster. Am I wrong? Thanks.

PS. Got AC with KMP O(N * K).

Edited by author 26.08.2015 00:30

//#define LOCAL
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define MAXN 250000+10

int N;
char str1[MAXN], str2[MAXN];
char temp[MAXN*2];

int kmp(char* s, char* t, int pos);
void get_next(char* t, int* next, int t_len);
int main()
{
#ifdef LOCAL
    freopen("1423_String_Tale_2.in", "r", stdin);
    freopen("1423_String_Tale_2.out", "w", stdout);
#endif

    scanf("%d", &N);
    scanf("%s%s", str1, str2);

    int s1_len = strlen(str1);
    int s2_len = strlen(str2);

    if(s1_len != s2_len){
        printf("%d\n", -1);
        return 0;
    }

    strcpy(temp, str1);
    strcat(temp, str1);
    int ans;
    ans = kmp(temp, str2, 0);
    if(ans != 0 && ans != -1)
        printf("%d\n", s1_len-ans);
    else
        printf("%d\n", ans);

    return 0;
}

int kmp(char* s, char* t, int pos)
{
    int s_len = strlen(s);
    if(pos<0 || pos>s_len-1){
        fprintf(stderr, "%s", "Error: invalid pos.");
        system("pause");
    }

    int t_len = strlen(t);
    int *next = (int*)malloc(sizeof(int) * t_len);
    get_next(t, next, t_len);

    int i = pos;
    int j = 0;

    while(i<s_len && j<t_len){
        if(j<0 || s[i]==t[j]){
            i++;
            j++;
        }
        else
            j = next[j];
    }

//    free(next);
    if(j >= t_len)
        return i-t_len;
    else
        return -1;
}

void get_next(char* t, int* next, int t_len)
{
    next[0] = -1;
    int j = 0;
    int k = -1;
    while(j < t_len){
        if(k==-1 || t[j]==t[k]){
            j++;
            k++;
            next[j] = k;
        }
        else
            k = next[k];
    }
}

###############################################
Can anyone tell me WHY???

Edited by author 11.07.2017 19:31