1091 - Barcodes

[tameku]

Code: Select all

#include <iostream>
#include <vector>
#include <string>
#include <math.h>
#include <algorithm>
using namespace std;
void bad(int s){cout<<"Case "<<s<<": bad code" << endl;}
int w(char c){
if(c >= '0' && c <= '9'){ return c-'0';}
if(c == '-'){ return 10;}}
char val(string str){
if(str == "00001"){return '0';}
if(str == "10001"){return '1';}
if(str == "01001"){return '2';}
if(str == "11000"){return '3';}
if(str == "00101"){return '4';}
if(str == "10100"){return '5';}
if(str == "01100"){return '6';}
if(str == "00011"){return '7';}
if(str == "10010"){return '8';}
if(str == "10000"){return '9';}
if(str == "00100"){return '-';}
if(str == "00110"){return 's';}}

bool isWide(int a, double b){
if(b*0.95 <= a && b*1.05 >= a){
return false;}
return true;}

int main(){
int n;
int cnt=0;
while(cin >> n && n){
    cnt++;
vector<int> v;
for(int i=0;i<n;++i){int tmp;cin>>tmp;v.push_back(tmp);}

if((n-11)%6 != 0){bad(cnt); continue;}

bool found=false;
double ile=0;
for(double i=1;i<=200;++i){
bool good=true;

for(int j=0;j<v.size();++j){
if((v[j] >= 0.95*i && v[j] <= 1.05*i  )  || (v[j] >= 1.90*i && v[j] <= 2.10*i  )){} else{good=false;}}
if(good){ ile=i; found=true; break;}}

if(!found){bad(cnt); continue;}


bool cont=false;
for(int i=0;i<v.size();++i){
    if(v[i] > 200 || v[i] <= 0){bad(cnt); cont=true;break;}
if(i%6 != 5) { continue;}
if(isWide(v[i],ile)){bad(cnt);  cont=true; break;} else{v[i] =-1;}
v[i]=-1;
}
if(cont){ continue;}
string code="";
for(int i=0;i<v.size();++i){
    if(v[i] != -1){
if(isWide(v[i],ile)){code.append("1");} else{ code.append("0");}}

}

if(val(code.substr(0,5)) != 's'){ reverse(code.begin(),code.end());}
if(val(code.substr(0,5)) != 's'){bad(cnt); continue;}
else{  if(val(code.substr(code.size()-5,5)) != 's'){bad(cnt); continue;}}
vector<string> vv;
for(int i=1;i<(code.size()/5)-1;++i){
    vv.push_back(code.substr(i*5,5));}

int c=0,k=0;
for(int i=0;i<=(vv.size()-3);++i){
c+= (((vv.size()-3) - i)%10 +1) * w(val(vv[i]));
}
c = c%11;
if(c != (val(vv[vv.size()-2])-'0')){
cout << "Case "<<cnt<<": bad C" << endl; continue;}

for(int i=0;i<=(vv.size()-2);++i){
k+= (((vv.size()-2) - i)%9 +1) * w(val(vv[i]));
}
k = k%11;


if(k != (val(vv[vv.size()-1])-'0')){
cout << "Case "<<cnt<<": bad K" << endl; continue;}

cout << "Case "<<cnt<<": ";
for(int i=0;i<vv.size()-2;++i){cout << val(vv[i]);}
cout << endl;
} return 0;}

That's my code, it works for test cases, it worked for my own test case, I'm getting WA, no idea why Can you give me some test cases and outputs? or check my code

[tameku]

#derp
help me please

[Lim.YuDe]

I pass the sample input test cases and I am quite certain (using a few other test cases) I handled the requirements of the problem fully, but I am still getting WA.
Any ideas, anyone?

Code: Select all

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

#define REP(a, b, c) \
    for (int a = int(b); a < c; a++)

const int START = 11;
const int STOP = 11;
const int DASH = 10;

int caseNo, n, narrow[2], wide[2];
int arr[150];
char chs[150];
int translated[150];
bool isBadCode;
char encoding[12][6] = {"00001","10001","01001","11000","00101","10100","01100","00011","10010","10000","00100","00110"};
map<string, int> encodingToIndexMap;

void initializeEncodingToIndexMap() {
    REP(i, 0, 12) {
        encodingToIndexMap[string(encoding[i])] = i;
    }
}

void reverseCHS() {
    char temp[150];
    REP(i, 0, n) {
        temp[n-i-1] = chs[i];
    }
    REP(i, 0, n) chs[i] = temp[i];
}

void computeNarrowAndWideWidths() {
    narrow[0] = narrow[1] = arr[0];
    wide[0] = wide[1] = arr[0] * 2;
    narrow[0] -= (narrow[0] * 5/100);
    narrow[1] += (narrow[1] * 5/100);
    wide[0] -= (wide[0] * 5/100);
    wide[1] += (wide[1] * 5/100);
}

int badC() {
    int C = 0;
    int N = (n-17)/6 - 1;
    for (int i = 0; i <= N; i++) {
        C += (((N-i) % 10) + 1) * translated[i];
    }
    C %= 11;
    //printf("C:%d vs %d\n", C, translated[N+1]);
    return (C != translated[N+1]);
}

int badK() {
    int K = 0;
    int N = (n-11)/6 - 1;
    for (int i = 0; i <= N; i++) {
        K += (((N-i) % 9) + 1) * translated[i];
    }
    K %= 11;
    //printf("K:%d vs %d\n", K, translated[N+1]);
    return (K != translated[N+1]);
}

int main() {
    initializeEncodingToIndexMap();
    caseNo = 0;
    while (scanf("%d", &n) == 1 && n) {
        caseNo++;
        printf("Case %d: ", caseNo);
        isBadCode = false;
        REP(i, 0, 150) chs[i] = '\0';
        REP(i, 0, n) {
            scanf("%d", &arr[i]);
        }
        if (((n-5) % 6) != 0 || (n <= 23)) {
            printf("bad code\n");
            continue;
        }
        computeNarrowAndWideWidths();
        REP(i, 0, n) {
            if (arr[i] >= narrow[0] && arr[i] <= narrow[1]) {
                chs[i] = '0';
            } else if (arr[i] >= wide[0] && arr[i] <= wide[1]) {
                chs[i] = '1';
            } else {
                printf("bad code\n");
                isBadCode = true;
                break;
            }
        }
        if (isBadCode) continue;
        // forward translation
        for (int i = 0; i < n; i += 6) {
            chs[i+5] = '\0';
            if (encodingToIndexMap.find(string(&chs[i])) != encodingToIndexMap.end())
                translated[i/6] = encodingToIndexMap[string(&chs[i])];
            else {
                printf("bad code\n");
                isBadCode = true;
                break;
            }
        }
        if (isBadCode) continue;
        /*
        REP(i, 0, (n+1)/6) {
            printf("%d ", translated[i]);
        }
        printf("\n");
        */
        if (translated[0] != START || translated[(n-5)/6] != STOP) {
            // backward translation
            reverseCHS();
            for (int i = 0; i < n; i += 6) {
                chs[i+5] = '\0';
                if (encodingToIndexMap.find(string(&chs[i])) != encodingToIndexMap.end())
                    translated[i/6] = encodingToIndexMap[string(&chs[i])];
                else {
                    printf("bad code\n");
                    isBadCode = true;
                    break;
                }
            }
            if (isBadCode) continue;
            /*
            REP(i, 0, (n+1)/6) {
                printf("%d ", translated[i]);
            }
            printf("\n");
            */
            if (translated[0] != START) {
                printf("bad code\n");
            } else if (translated[(n-5)/6] != STOP) {
                printf("bad code\n");
            } else if (badC()) {
                printf("bad C\n");
            } else if (badK()) {
                printf("bad K\n");
            } else {
                REP(i, 1, (n-17)/6) {
                if (translated[i] >= 0 && translated[i] <= 9) {
                    printf("%c", translated[i] + '0');
                } else {
                    printf("-");
                }
            }
            printf("\n");
            }
        } else if (badC()) {
            printf("bad C\n");
        } else if (badK()) {
            printf("bad K\n");
        } else {
            REP(i, 1, (n-17)/6) {
                if (translated[i] >= 0 && translated[i] <= 9) {
                    printf("%c", translated[i] + '0');
                } else {
                    printf("-");
                }
            }
            printf("\n");
        }
    }
    return 0;
}

[dibery]

Watch out for floating point error.
Also, the width determining between the narrow & wide ones need not to be an integer.

A tricky input is that the width seen in the input are
19 20 21 38 40 42
We can see that the narrow length is in the interval of [19,21] & wide one in [38,42].
However, if we check the validity by N*1.05 with N=20, since 20*1.05 may not be 21.
Therefore, we would get "bad code" even if the code is actually valid.