글 읽기 - 도대체 어디가 문제죠...

p_ce1052 3년 전 0

q에 있는 문자열을 팰린드롬의 절반으로 하는 수를 만들어서 a와 b 사이에 있는지 보고 있다면 소수인지 확인하여 set에 저장해서 쭉 출력하였습니다. 반례나 문제점좀 알려주세요 ㅠㅠ

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<string,int> pi;
int mylen(int b){ //숫자의 길이 
	int ret = 0;
	if(!b) return 1;
	while(b){
		ret++;
		b/=10;
	}
	return ret;
}
bool prime(ll n){ //소수인지 확인 
	for(ll i=2; i*i<=n; i++){
		if(n%i==0) return false;
	}
	return true;
}
ll toint1(string a){ //a를 앞의 절반으로 하는 팰린드롬 수를 만든다
	ll num = 0;
	ll digit = 1;
	int i;
	
	for(i=0; a[i]; i++){
		num+=(a[i]-'0')*digit;
		digit*=10;
	}
	i--;
	while(i>=0){
		num+=(a[i]-'0')*digit;
		digit*=10;
		i--;
	}
	return num;
}
ll toint2(string a, int n){ //a를 앞의 절반으로 하고 가운데 n이 있는 팰린드롬을 만든다.
	ll num = 0;
	ll digit = 1;
	int i;
	
	for(i=0; a[i]; i++){
		num+=(a[i]-'0')*digit;
		digit*=10;
	}
	num+=n*digit;
	digit*=10;
	i--;
	while(i>=0){
		num+=(a[i]-'0')*digit;
		digit*=10;
		i--;
	}
	return num;
}
int main(){
	int a,b;
	cin>>a>>b;
	int len = mylen(b);
	set<int>st;
	
	for(int i=2; i<10; i++){
		if(a<=i && i<=b && prime(i)) st.insert(i); //한 자릿수 확인 
	}

	queue<pi>q;
	for(char ch = '1'; ch<='9'; ch+=2){
		string s;
		s.push_back(ch);
		q.push(pi(s,1));
	}
	while(!q.empty()){
		string cur = q.front().first;
		int l = q.front().second;
		q.pop();
		if(2*l<=len){
			ll num = toint1(cur);
			if(a<=num && num<=b && prime(num)) st.insert(num);
		}
		if(2*l+1<=len){
			for(int i=0; i<10; i++){
				ll num = toint2(cur,i);
				if(a<=num && num<=b && prime(num)) st.insert(num);
			}
		}
		l++;
		if(2*l+1>len && 2*l>len) continue; //길이가 b의 길이를 넘어가면 가망 없음 
		l--;
		for(char ch = '1'; ch<='9'; ch++){
			cur.push_back(ch);
			q.push(pi(cur,l+1));
			cur.pop_back();
		}
	}
	for(auto a:st) cout<<a<<'\n';
	cout<<-1;
}

p_ce1052 3년 전 0

해결되었습니다

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

도대체 어디가 문제죠...

p_ce1052 3년 전 0

p_ce1052 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말