## 1091 - Barcodes

All about problems in Volume 10. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

tameku
New poster
Posts: 2
Joined: Sun Nov 11, 2012 4:42 pm

### 1091 - Barcodes

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
New poster
Posts: 2
Joined: Sun Nov 11, 2012 4:42 pm

### Re: 1091 - Barcodes - WA help please

#derp
help me please

Lim.YuDe
New poster
Posts: 15
Joined: Sat Dec 13, 2014 1:32 pm

### Re: 1091 - Barcodes

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
Learning poster
Posts: 76
Joined: Sat Feb 23, 2013 4:16 pm
Location: Taiwan, Taipei
Contact:

### Re: 1091 - Barcodes

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.
Life shouldn't be null.