Hi,
Could anyone please point me to the error I might have in the code. I can't seem to find it. It looks like it works for every case I've tried but get WA in systests.
Maybe I'm using the wrong algorithm?
Here's how it tries to solve it:
1. Loops from i = 2 to 9 and if it's possible to divide the number n by i, then one possibility is i appended to findmin(n/i). Ex, for findmin(18), it would be "2" + findmin(18/2) = "2" + findmin(9) = "29". The base case is if n is a single digit.
2. If findmin returns "", then it tries the next i in the loop.
Len is up to how many digits to go. It checks up to the amount of digits in n + 3. Perhaps this is the problem?
Thanks for your help.
string findmin( int n, int len){
if (len==0)return "";
for (int i=2;i<10;i++){
if (n<10){
string s;
s+=char(n+'0');
return s;
}
if (n%i==0){
string x = findmin(n/i,len-1);
if (x.size()!=0){
return char(i+'0')+x;
}
}
}
return "";
}
int main(){
//ifstream in("in.txt");
int n;
while (cin>>n && n!=-1){
int len=0;
int z=n;
while (z!=0){
z/=10;
len++;
}
string r;
if (n<10){
r="1";
r+=char(n+'0');
}
else {
for (int i=0;i<3;i++){
r= findmin(n,len+i);
if (r.size()!=0)break;
}
}
if (r.size()==0)cout<<"There is no such number.\n";
else cout<<r<<endl;
Well, actually, this one is very specific, so you don't need the entire bigint class, you just need to implement what you need...
And the easiest (for me anyhow) way to do this is to represent it as a string, and do it the slow way... not very efficient, but during a contest, it should suffice..
I don't have one right now. I'll make it in the upcoming days. Probably using recursion will make very short (able to be typed in a few minutes).
I'm guessing the basic operations for a general would be toString, add, sub, mult, div, mod, and exp.
-Eric
Hi,
Try changing istream& operator >>(istream& instr, bigint& N) to this instead:
[cpp]while(isdigit(instr.peek()))
buffer.push_back(instr.get());
if (instr.peek()!='\n'){
instr.setstate(instr.failbit);
instr.setstate(instr.eofbit); //Maybe this one too
}[/cpp]
If it still do not work, I'll look at it tomorrow in more details.
i am pasting my code which is giving right answer for given test case but giving wrong answer after submitting the code please find where i am wrong.
if possible can u give me some test cases.
Runtime Error (Signal 11)...
hello everybody . i am try to solve this problem but getting RTE , don't know why.
plz help me ..here is my code .kindly tell me why RTE.
I'd like to ask if I can use BigInteger class from package java.math.BigInteger in Java. I'm not getting any compilation error or runtime error, I am getting WA, so I assume that it is ok to use it, but just for assure.
import java.io.IOException;
import java.math.BigInteger;
import java.util.ArrayList;
import java.util.StringTokenizer;
public class Main {
// processing number
private BigInteger processing;
// all the input
private ArrayList<BigInteger> in;
// static BigInteger representation of some numbers
private static final BigInteger twoVal = new BigInteger("2");
private static final BigInteger threeVal = new BigInteger("3");
private static final BigInteger fiveVal = new BigInteger("5");
private static final BigInteger sevenVal = new BigInteger("7");
private static final BigInteger oneVal = new BigInteger("1");
private static final BigInteger fourVal = new BigInteger("4");
private static final BigInteger sixVal = new BigInteger("6");
private static final BigInteger eightVal = new BigInteger("8");
private static final BigInteger nineVal = new BigInteger("9");
private static final BigInteger tenVal = new BigInteger("10");
// counts of the one digit primes in the prcessing NUM
private BigInteger twoCount = new BigInteger("0");
private BigInteger threeCount = new BigInteger("0");
private BigInteger fiveCount = new BigInteger("0");
private BigInteger sevenCount = new BigInteger("0");
public Main()
{
in = new ArrayList<BigInteger>();
}
// reads all the avialable bytes from System.in (as far as -1)
public void readInput()
{
try
{
//pole pro nacteni celeho vstupu naraz
byte[] b = new byte[System.in.available()];
int r = System.in.read(b);
if (r == -1)
{
System.exit(1);
}
StringTokenizer tok = new StringTokenizer(new String(b));
// pocet radku, standartni delimitery staci
int radku = tok.countTokens();
// int pro ulozeni radku
BigInteger tmp;
for (int i = 0; i < radku; i++)
{
// dostanu jeden radek jako string a udelam z nej int
tmp = new BigInteger(tok.nextToken());
// pri nule je konec, davaji za nulu jeste dalsi cisla...
if( tmp.intValue() == -1 ) break;
// pridam do arraylistu
in.add(tmp);
}
}
catch (IOException ex)
{
System.out.println("chyba");
System.exit(1);
}
}
// just sets the field
public void setNum(BigInteger n)
{
processing = n;
}
// divides the number by one digit primes (2, 3, 5, 7) and counts how many times NUM was
// divided by each of the prime
public void getParts()
{
if(processing.intValue() == 0)
return;
BigInteger tmp = processing;
while(processing.remainder(twoVal).intValue() == 0 )
{
twoCount = twoCount.add(oneVal);
processing = processing.divide(twoVal);
}
while(processing.remainder(threeVal).intValue() == 0 )
{
threeCount = threeCount.add(oneVal);
processing = processing.divide(threeVal);
}
while(processing.remainder(fiveVal).intValue() == 0 )
{
fiveCount = fiveCount.add(oneVal);
processing = processing.divide(fiveVal);
}
while(processing.remainder(sevenVal).intValue() == 0 )
{
sevenCount = sevenCount.add(oneVal);
processing = processing.divide(sevenVal);
}
processing = tmp;
}
// check if all of the parts we got multiplied give the original number
public boolean check()
{
BigInteger chck = new BigInteger("0");
BigInteger tmp1 = sevenVal.pow(sevenCount.intValue());
BigInteger tmp2 = fiveVal.pow(fiveCount.intValue());
BigInteger tmp3 = threeVal.pow(threeCount.intValue());
BigInteger tmp4 = twoVal.pow(twoCount.intValue());
chck = tmp1.multiply(tmp2.multiply(tmp3.multiply(tmp4)));
if ( chck.equals(processing) )
return true;
return false;
}
// method that builds the smallest number from the parts
public BigInteger createPrevious()
{
BigInteger prev = new BigInteger("0");
BigInteger digit_place = new BigInteger("1");
if (processing.intValue() == 1)
return new BigInteger("11");
while(contains(9))
{
prev = prev.add(digit_place.multiply(nineVal));
digit_place= digit_place.multiply(tenVal);
threeCount = threeCount.subtract(twoVal);
}
while(contains(8))
{
prev = prev.add(digit_place.multiply(eightVal));
digit_place= digit_place.multiply(tenVal);
twoCount = twoCount.subtract(threeVal);
}
while(contains(7))
{
prev = prev.add(digit_place.multiply(sevenVal));
digit_place= digit_place.multiply(tenVal);
sevenCount = sevenCount.subtract(oneVal);
}
while(contains(6))
{
prev = prev.add(digit_place.multiply(sixVal));
digit_place= digit_place.multiply(tenVal);
threeCount = threeCount.subtract(oneVal);
twoCount = twoCount.subtract(oneVal);
}
while(contains(5))
{
prev = prev.add(digit_place.multiply(fiveVal));
digit_place= digit_place.multiply(tenVal);
fiveCount = fiveCount.subtract(oneVal);
}
while(contains(4))
{
prev = prev.add(digit_place.multiply(fourVal));
digit_place= digit_place.multiply(tenVal);
twoCount = twoCount.subtract(twoVal);
}
while(contains(3))
{
prev = prev.add(digit_place.multiply(threeVal));
digit_place= digit_place.multiply(tenVal);
threeCount = threeCount.subtract(oneVal);
}
while(contains(2))
{
prev = prev.add(digit_place.multiply(twoVal));
digit_place= digit_place.multiply(tenVal);
twoCount = twoCount.subtract(oneVal);
}
if (prev.compareTo(tenVal) == -1 )
prev = prev.add(tenVal);
return prev;
}
// can we get NUMBER from the parts we have right now?
boolean contains(int number)
{
switch (number)
{
case 9:
if (threeCount.compareTo(twoVal) == -1)
return false;
return true;
case 8:
if (twoCount.compareTo(threeVal) == -1)
return false;
return true;
case 7:
if (sevenCount.compareTo(oneVal) == -1)
return false;
return true;
case 6:
if (twoCount.compareTo(oneVal) == -1 || threeCount.compareTo(oneVal) == -1)
return false;
return true;
case 5:
if (fiveCount.compareTo(oneVal) == -1)
return false;
return true;
case 4:
if (twoCount.compareTo(twoVal) == -1)
return false;
return true;
case 3:
if (threeCount.compareTo(oneVal) == -1)
return false;
return true;
case 2:
if (twoCount.compareTo(oneVal) == -1)
return false;
return true;
default:
return false;
}
}
// sets the working NUM, gets all the parts,
// check if the parts gives the original number and than prints a result
public void processANumber(BigInteger n)
{
setNum(n);
getParts();
if(check() || processing.compareTo(BigInteger.valueOf(10)) == -1 )
System.out.println(createPrevious());
else
System.out.println("There is no such number.");// ("+num.toString()+")");
}
// launch a process for every number we've got in the input (resets counts after each)
public void run()
{
int s = in.size();
for (int i = 0; i < s; i++)
{
init();
processANumber(in.get(i));
}
}
// just creates an instance, reads a data and launches the program
public static void main(String[] args)
{
Main m = new Main();
m.readInput();
m.run();
System.exit(0);
}
// resets the counters
private void init()
{
twoCount = new BigInteger("0");
threeCount = new BigInteger("0");
fiveCount = new BigInteger("0");
sevenCount = new BigInteger("0");
}
}