当前位置：首页 → 问答吧 → Help on SPOJ IITKWPCA

Help on SPOJ IITKWPCA

时间：2013-09-21

来源：互联网

The following problem seems very easy but I got WA (wrong answer):
http://www.spoj.com/problems/IITKWPCA/

Can any one help?

作者: fitcat07 发布时间: 2013-09-21

引用:原帖由 fitcat07 於 2013-8-30 16:34 发表
The following problem seems very easy but I got WA (wrong answer):
http://www.spoj.com/problems/IITKWPCA/

Can any one help?

1. Why need to reverse? Would reverse affect the result? I couldn't think of a case yet.2. Case sensitive perhaps.

作者: a8d7e8 发布时间: 2013-09-21

引用:原帖由 a8d7e8 於 2013-8-30 05:24 PM 发表

1. Why need to reverse? Would reverse affect the result? I couldn't think of a case yet.2. Case sensitive perhaps.

1. I agreed. I don't think reverse is needed.
2. I tried either way.

作者: fitcat07 发布时间: 2013-09-21

引用:原帖由 fitcat07 於 2013-8-30 17:43 发表
1. I agreed. I don't think reverse is needed.
2. I tried either way.

Btw, how do you compute the distinct set? By sorting?
how about the 0 case? " "

作者: a8d7e8 发布时间: 2013-09-21

引用:原帖由 a8d7e8 於 2013-8-30 05:46 PM 发表

Btw, how do you compute the distinct set? By sorting?
how about the 0 case? " "

In C++, I used std::set. I computed the hash value of each word and put it into the set. Instead of hash values, I also tried std::string (slower method) as the element type of the set.
No reverse was done.

In Python, I also used set and reverse each word before putting it into the set.

作者: fitcat07 发布时间: 2013-09-21

Most recently accepted answers are PYTH........and one JAVA.

Um it might tell a difference.

What is easy in Python and Java but not quite as same in C++? String manipulation?

But you've tried Python too......

引用:原帖由 fitcat07 於 2013-8-30 18:38 发表
In C++, I used std::set. I computed the hash value of each word and put it into the set. Instead of hash values, I also tried std::string (slower method) as the element type of the set.
No reverse wa ...

作者: a8d7e8 发布时间: 2013-09-21

My Python version (WA):

复制内容到剪贴板代码:from sys import stdin
from sets import Set

input = stdin.readlines()
for line in input[1:]:
words = line.strip().split()
s = Set()
for word in words:
s.add(word[::-1])
print len(s)

作者: fitcat07 发布时间: 2013-09-21

Range checking?size of string >= 1 && <= 10^4)relate to more than maximum input length?

作者: a8d7e8 发布时间: 2013-09-21

引用:原帖由 a8d7e8 於 2013-8-30 06:52 PM 发表
Range checking?size of string >= 1 &&

Yeah, I noted most AC solutions are in Python. So, I tried Python so as to avoid such problem but in vain...

作者: fitcat07 发布时间: 2013-09-21

Accepted.......

作者: a8d7e8 发布时间: 2013-09-21

I just got AC

I modified the Python version a little bit so that it reads T lines instead of all the lines (there are some extra lines in the input file).
Findings:
1. Case sensitive
2. No need to reverse the words

However, I still don't know why my C++ version got WA.

作者: fitcat07 发布时间: 2013-09-21

Here is my C++ version:

复制内容到剪贴板代码:#include
#include
#include
#include
using namespace std;

const int MAX_LEN = 10000;

int t;
char line[MAX_LEN+4];

int main() {
fgets(line, sizeof(line), stdin);
sscanf(line, "%d", &t);
while (t--) {
fgets(line, sizeof(line), stdin);
set s;
char *p = strtok(line, " \n");
while (p) {
s.insert(string(p));
p = strtok(NULL, " \n");
}
printf("%llu\n", s.size());
}
}

What's wrong?

作者: fitcat07 发布时间: 2013-09-21

引用:原帖由 a8d7e8 於 2013-8-30 02:44 AM 发表
Most recently accepted answers are PYTH........and one JAVA.

Um it might tell a difference.

What is easy in Python and Java but not quite as same in C++? String manipulation?

But you've tr ...

Python嘅hash table （dictionary）超易用，俾我都用Python。

作者: code4food 发布时间: 2013-09-21

Someone from SPOJ's forum find out the problem. I should use "%u" instead of "%llu" as the judge is a 32-bit system.
I used "%llu" as mine is a 64-bit system.

作者: fitcat07 发布时间: 2013-09-21

引用:原帖由 fitcat07 於 2013-8-30 02:45 AM 发表
My Python version (WA):

This can be simplified as:

复制内容到剪贴板代码:from sys import stdin

input = stdin.readlines()
for line in input[1:]:
print len(set(line.split()))

作者: code4food 发布时间: 2013-09-21

Great! Only 4 lines of code.

作者: fitcat07 发布时间: 2013-09-21

OH!!!!!!!

引用:原帖由 fitcat07 於 2013-9-1 19:22 发表
Someone from SPOJ's forum find out the problem. I should use "%u" instead of "%llu" as the judge is a 32-bit system.
I used "%llu" as mine is a 64-bit system.

作者: a8d7e8 发布时间: 2013-09-21

my first dart program

复制内容到剪贴板代码:import 'dart:io';
import 'dart:async';
import 'dart:convert';

void total_each_line(var Lines) {
var lines = Lines.trim().split(new RegExp(r"\n"));
for(var line in lines.skip(1)){
var t = line.trim().split(new RegExp(r"\s+"));
//print(t);
var len = t[0].length == 0 ? 0 : new Set.from(t).length;
print(len);
}
}

void main() {
Stream inputStream = stdin.transform(new Utf8Decoder());

StreamSubscription sub = inputStream.listen(
(line) => total_each_line(line),
onDone: () => print(' finished'),
onError: (e) => print(' error'));
}

[ 本帖最后由 form5 於 2013-9-9 02:27 AM 编辑 ]

作者: form5 发布时间: 2013-09-21

Help on SPOJ IITKWPCA

热门阅读

热门下载