2008B
をテンプレートにして作成
[
トップ
] [
新規
|
一覧
|
単語検索
|
最終更新
|
ヘルプ
|
ログイン
]
開始行:
[[08年度-ACM-ICPC国内予選]]
***2008B [#i0a53608]
回答者:[[ほへい]]&br;
所要時間:3時間&br;
予選時:クリア/5ミス?&br;
&br;
全部ファイルの送り間違いです。&br;
ペナルティ加算しまくり。申し訳ない限りで…。~
B問題だから強引にいっても大丈夫だろうと踏んで爆死した良い例。~
今泉先生の解答例みるまでエラトステネスのふるいが使えることに気付きませんでした。~
問題とコードを見ればわかると思うんで解説はパスします。~
~
~
#include <iostream>
#include <fstream>
#include <vector>
#include <cmath>
const char *const fileNameIn("B_in.txt");
const char *const fileNameOut("B_out.txt");
std::ifstream f_in(fileNameIn);
std::ofstream f_out(fileNameOut);
std::vector<int> prime;
void searchPrime();
bool isGetuDo(int a);
void getAnswer(int searchNum);
int main()
{
if( !f_in || !f_out)
{
std::cout << "ファイルが開けませんでした\n";
}
prime.push_back(6);
prime.push_back(8);
std::cout << "searchStart" << std::endl;
searchPrime();
std::cout << "end : " << prime.size() << std::endl;
int searchNum;
while(true)
{
f_in >> searchNum;
if(searchNum == 1) break;
getAnswer(searchNum);
}
f_in.close();
f_out.close();
return 0;
}
bool isGetuDo(int a) {
return (a % 7 == 1) || (a % 7 == 6);
}
void searchImpl(int i)
{
std::vector<int>::iterator iter = prime.begin();
std::vector<int>::iterator endIter = prime.end();
bool isPrime = true;
int limit = (int)sqrt((double)i);
for(; iter != endIter; ++iter)
{
if(limit < (*iter)) break;
if((i % (*iter) == 0) )
{
isPrime = false;
break;
}
}
if(isPrime) prime.push_back(i);
}
void searchPrime()
{
int i = 2;
while(true)
{
if((i * 7 - 1) <= 300000) searchImpl(i * 7 - 1);
if((i * 7 + 1) <= 300000) searchImpl(i * 7 + 1);
if((i * 7 + 1) >= 300000) break;
i++;
}
}
void getAnswer(int searchNum)
{
f_out << searchNum << ':';
std::vector<int>::iterator iter = prime.begin();
std::vector<int>::iterator endIter = prime.end();
for(; iter != endIter; ++iter)
{
if(searchNum % (*iter) == 0 && isGetuDo(searchNum / (*iter)))
{
f_out << " " << (*iter);
}
}
f_out << std::endl;
}
終了行:
[[08年度-ACM-ICPC国内予選]]
***2008B [#i0a53608]
回答者:[[ほへい]]&br;
所要時間:3時間&br;
予選時:クリア/5ミス?&br;
&br;
全部ファイルの送り間違いです。&br;
ペナルティ加算しまくり。申し訳ない限りで…。~
B問題だから強引にいっても大丈夫だろうと踏んで爆死した良い例。~
今泉先生の解答例みるまでエラトステネスのふるいが使えることに気付きませんでした。~
問題とコードを見ればわかると思うんで解説はパスします。~
~
~
#include <iostream>
#include <fstream>
#include <vector>
#include <cmath>
const char *const fileNameIn("B_in.txt");
const char *const fileNameOut("B_out.txt");
std::ifstream f_in(fileNameIn);
std::ofstream f_out(fileNameOut);
std::vector<int> prime;
void searchPrime();
bool isGetuDo(int a);
void getAnswer(int searchNum);
int main()
{
if( !f_in || !f_out)
{
std::cout << "ファイルが開けませんでした\n";
}
prime.push_back(6);
prime.push_back(8);
std::cout << "searchStart" << std::endl;
searchPrime();
std::cout << "end : " << prime.size() << std::endl;
int searchNum;
while(true)
{
f_in >> searchNum;
if(searchNum == 1) break;
getAnswer(searchNum);
}
f_in.close();
f_out.close();
return 0;
}
bool isGetuDo(int a) {
return (a % 7 == 1) || (a % 7 == 6);
}
void searchImpl(int i)
{
std::vector<int>::iterator iter = prime.begin();
std::vector<int>::iterator endIter = prime.end();
bool isPrime = true;
int limit = (int)sqrt((double)i);
for(; iter != endIter; ++iter)
{
if(limit < (*iter)) break;
if((i % (*iter) == 0) )
{
isPrime = false;
break;
}
}
if(isPrime) prime.push_back(i);
}
void searchPrime()
{
int i = 2;
while(true)
{
if((i * 7 - 1) <= 300000) searchImpl(i * 7 - 1);
if((i * 7 + 1) <= 300000) searchImpl(i * 7 + 1);
if((i * 7 + 1) >= 300000) break;
i++;
}
}
void getAnswer(int searchNum)
{
f_out << searchNum << ':';
std::vector<int>::iterator iter = prime.begin();
std::vector<int>::iterator endIter = prime.end();
for(; iter != endIter; ++iter)
{
if(searchNum % (*iter) == 0 && isGetuDo(searchNum / (*iter)))
{
f_out << " " << (*iter);
}
}
f_out << std::endl;
}
ページ名: