Tuesday, November 20, 2012

November 2012 Bronze Problem 1: Find the Cow!

The contest has ended! I have posted the first solution now.
Result: 9/10 *********t (timeout)
cowfind.cpp
#include <iostream>
#include <fstream>
#include <string>

#define loopi(x) loopi_start(x,0)
#define loopi_start(x,s) for(int i = (s); i < (x); ++i)
#define loop_rev(a,x,stop) for(int a = (x); a >= (stop); --a)

using namespace std;

int main() {
 ofstream fout ("cowfind.out");
 ifstream fin("cowfind.in");
 // get input
 string str;
 fin >> str;
 int locations = 0;
 //)((()())())
 loopi(str.length() - 3){
  if(str[i] == '(' && str[i + 1] == '('){
   loop_rev(j, str.length() - 1, i + 3){
    if(str[j] == ')' && str[j - 1] == ')')
     ++locations;
   }
  }
 }
 // output
 fout << locations << '\n';
 // cleanup
 fin.close();
 fout.close();
 return 0;
}

3 comments:

  1. You made it too complex, while it's not! :-p

    /*
    ID: minlite
    PROG: cowfind
    LANG: C++
    */
    #include
    #include
    using namespace std;

    int main() {
    ofstream fout ("cowfind.out");
    ifstream fin ("cowfind.in");
    char in[50000];
    int out = 0;
    fin>>in;
    for(int i=0; i<50000; i++) {
    if(in[i] == '(' && in[i+1] == '(') {
    for(int j=i;j<50000;j++) {
    if(in[j] == ')' && in[j+1] == ')'){
    out++;
    }
    }
    }
    }
    fout<<out<<endl;
    return 0;
    }

    ReplyDelete
    Replies
    1. That solution has a buffer overread, and it's prone to failure if the input is longer than 50000. std::string is safer to use.

      Delete
    2. To be specific: in[i+1] when i = 49999.

      Delete