10992 - The Ghost of Programmers

lord_burgos · Post by **lord_burgos** » Tue Feb 14, 2006 5:15 pm

lonelyone wrote:any more test data please
I got wrong answer all the time

Input

50
1923823917239712937192837981273971289371293
123981273912739123981278937298371298379812739127
123111111111111111
23123
1232
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
200
300
2148
2149
2150
2151
2152
2153
2154
2155
2156
2157
2158
2159
2160
2161
2162
2163
2164
2165
0

Output

Code: Select all

50
No ghost will come in this year

1923823917239712937192837981273971289371293
Ghost of Shahriar Manzoor!!!

123981273912739123981278937298371298379812739127
No ghost will come in this year

123111111111111111
No ghost will come in this year

23123
Ghost of Shahriar Manzoor!!!

1232
No ghost will come in this year

1
No ghost will come in this year

2
No ghost will come in this year

3
No ghost will come in this year

4
No ghost will come in this year

5
No ghost will come in this year

6
No ghost will come in this year

7
No ghost will come in this year

8
No ghost will come in this year

9
No ghost will come in this year

10
No ghost will come in this year

11
No ghost will come in this year

12
No ghost will come in this year

13
No ghost will come in this year

14
No ghost will come in this year

15
No ghost will come in this year

16
No ghost will come in this year

17
No ghost will come in this year

18
No ghost will come in this year

19
No ghost will come in this year

20
No ghost will come in this year

21
No ghost will come in this year

22
No ghost will come in this year

23
No ghost will come in this year

24
No ghost will come in this year

25
No ghost will come in this year

200
No ghost will come in this year

300
No ghost will come in this year

2148
Ghost of Tanveer Ahsan!!!
Ghost of Shahriar Manzoor!!!
Ghost of Adrian Kugel!!!
Ghost of Anton Maydell!!!
Ghost of Derek Kisman!!!
Ghost of Rezaul Alam Chowdhury!!!
Ghost of Jimmy Mardell!!!
Ghost of Monirul Hasan!!!
Ghost of K. M. Iftekhar!!!

2149
No ghost will come in this year

2150
Ghost of Tanveer Ahsan!!!

2151
No ghost will come in this year

2152
Ghost of Tanveer Ahsan!!!
Ghost of K. M. Iftekhar!!!

2153
Ghost of Shahriar Manzoor!!!

2154
Ghost of Tanveer Ahsan!!!

2155
Ghost of Adrian Kugel!!!

2156
Ghost of Tanveer Ahsan!!!
Ghost of K. M. Iftekhar!!!

2157
No ghost will come in this year

2158
Ghost of Tanveer Ahsan!!!
Ghost of Shahriar Manzoor!!!

2159
Ghost of Anton Maydell!!!

2160
Ghost of Tanveer Ahsan!!!
Ghost of K. M. Iftekhar!!!

2161
No ghost will come in this year

2162
Ghost of Tanveer Ahsan!!!
Ghost of Adrian Kugel!!!

2163
Ghost of Shahriar Manzoor!!!
Ghost of Derek Kisman!!!

2164
Ghost of Tanveer Ahsan!!!
Ghost of K. M. Iftekhar!!!

2165
No ghost will come in this year

check

if(modulo(number, 4) == 0 && (modulo(number,100) != 0 || modulo(number,400) == 0)){
printf("Ghost of K. M. Iftekhar!!!\n");cont++;
}

lonelyone · Post by **lonelyone** » Wed Feb 15, 2006 1:19 am

yes, thanks lord_burgos
the reason why I got wrong answer all the time is I forgot to
output "the input number"; that is, Y.
Thanks anyway.

tan_Yui · Post by **tan_Yui** » Thu Mar 02, 2006 3:46 pm

Hi, everyone.
I solved this problem by using my BigInteger Class (C language).
Can I solve with no use for BigInteger Class?

Thank you.

Cho · Post by **Cho** » Thu Mar 02, 2006 5:35 pm

There are two special rules for checking multiple of 3 and 11. It's well known that, for any integer, if the sum of its digits is multiple of 3, then that integer is multiple of 3. If the alternate sum of the digits of an integer is multiple of 11, then that integer is multiple of 11. e.g. 806190 is multiple of 11 because -8+0-6+1-9+0=-22.

Actually, there is such a rule for ALL integers. But the rule for 3 and 11 is particularly simple.
For example, to check the multiple of 7, you can multiply 1, 3, 2, 6, 4, 5, (repeat this pattern)... to the digits of the integer and sum them up.
i.e. 123456789%7 = (1*2+2*3+3*1+4*5+5*4+6*6+7*2+8*3+9*1)%7 = 134%7 = 1

The above observation provides an alternative approach to solve the problem, though dividing a big int by int is not that hard to code.

Abednego · Post by **Abednego** » Thu Mar 02, 2006 6:34 pm

There is a much simpler rule for checking whether ANY small integer m divides n.

Code: Select all

string n;
int r = 0;
for( int i = 0; i < ( int )n.size(); i++ ) r = ( r * 10 + n[i] - '0' ) % m;
// m divides n if and only if r = 0

Cho · Post by **Cho** » Thu Mar 02, 2006 7:13 pm

Yes, that's why i said dividing a big int by int is not that hard. Especially we are now looking for the remainder only.

tan_Yui · Post by **tan_Yui** » Fri Mar 03, 2006 5:58 am

Thanks, Cho and Abednego!
Your idea is useful and efficient.

I'll try to solve again with this method.

p.s.
My current AC code with BigInteger Class gets the time less than 0:00.100. Because this problem condition is not hard (length of Y<50, at most 250 lines of input data), my code could avoid TimeLimitExceeded.

My brain has little flexibility....

Best regards.

abdullah<cse du> · Post by **abdullah<cse du>** » Sat Jul 14, 2007 5:47 pm

Hi all,

I have tried this problem. I have a problem in finding leap year. For the input 2500 in the problem if we deduct 2148 the result is 352. And it is leap year by the process given in the problem. But the output does not content it.

Please help me to understand it.

Thanks.
ABDULLAH.

Jan · Post by **Jan** » Sat Jul 14, 2007 5:54 pm

abdullah<cse du> wrote:I have tried this problem. I have a problem in finding leap year. For the input 2500 in the problem if we deduct 2148 the result is 352. And it is leap year by the process given in the problem. But the output does not content it.

Why are you subtracting 2148 from 2500 to find the leap year? For the leap year part you don't have to subtract anything. And for the other parts you can check after subtracting.

Hope it helps.

r2ro · Post by **r2ro** » Thu Sep 25, 2008 9:40 am

Hi, anyone willing to provide me with more tricky test cases? Seems that it passes all the cases in this thread, but still comes out as WA

Anyway, here's the code:

Code: Select all

/**
 * @(#)Main.java
 *
 *
 * @author 
 * @version 1.00 2008/9/5
 */


/**
 * @(#)Main.java
 *
 *
 * @author 
 * @version 1.00 2008/8/28
 */

import java.io.*;
import java.util.*;
import java.math.*;

public class Main {

    public Main() {
    }
    
    public static void main(String args[]) throws Exception
    {
   //     Scanner s = new Scanner(System.in);
        Scanner s = new Scanner(new FileReader("input.txt"));
        BigInteger arr[] = new BigInteger[500];
        int nCount = 0,i;
        String sTemp;
        do
        {
            sTemp = s.next();
            if (sTemp.equals("0") != true)
            {
                arr[nCount] = new BigInteger(sTemp);
                nCount++;
            }
        }
        while (sTemp.equals("0") != true);
        
        for (i = 0;i < nCount;i++)
        {
            BigInteger nNum = arr[i];
            BigInteger Temp;
            boolean there = false;
            if (i != 0)
            System.out.printf("\n");
            System.out.println(""+nNum);
            Temp = new BigInteger("0");
            if (nNum.compareTo(new BigInteger("2148")) == -1)
            {
                System.out.printf("No ghost will come in this year\n");
            }
            else if (nNum.compareTo(new BigInteger("2148")) == 0)
            {
            System.out.printf("Ghost of Tanveer Ahsan!!!\n");
            System.out.printf("Ghost of Shahriar Manzoor!!!\n");
            System.out.printf("Ghost of Adrian Kugel!!!\n");
            System.out.printf("Ghost of Anton Maydell!!!\n");
            System.out.printf("Ghost of Derek Kisman!!!\n");
            System.out.printf("Ghost of Rezaul Alam Chowdhury!!!\n");
            System.out.printf("Ghost of Jimmy Mardell!!!\n");
            System.out.printf("Ghost of Monirul Hasan!!!\n");
            System.out.printf("Ghost of K. M. Iftekhar!!!\n");
            }
            else {
            BigInteger Test = nNum.subtract(new BigInteger("2148"));
            if (Test.mod(new BigInteger("2")).compareTo(Temp) == 0) { there = true;
                System.out.printf("Ghost of Tanveer Ahsan!!!\n"); }
            if (Test.mod(new BigInteger("5")).compareTo(Temp) == 0) { there = true;
                System.out.printf("Ghost of Shahriar Manzoor!!!\n"); }
            if (Test.mod(new BigInteger("7")).compareTo(Temp) == 0) { there = true;
                System.out.printf("Ghost of Adrian Kugel!!!\n"); }
            if (Test.mod(new BigInteger("11")).compareTo(Temp) == 0) { there = true;
                System.out.printf("Ghost of Anton Maydell!!!\n"); }
            if (Test.mod(new BigInteger("15")).compareTo(Temp) == 0) { there = true;
                System.out.printf("Ghost of Derek Kisman!!!\n"); }
            if (Test.mod(new BigInteger("20")).compareTo(Temp) == 0) { there = true;
                System.out.printf("Ghost of Rezaul Alam Chowdhury!!!\n"); }
            if (Test.mod(new BigInteger("28")).compareTo(Temp) == 0) { there = true;
                System.out.printf("Ghost of Jimmy Mardell!!!\n"); }
            if (Test.mod(new BigInteger("36")).compareTo(Temp) == 0) { there = true;
                System.out.printf("Ghost of Monirul Hasan!!!\n"); }
            Test.add(new BigInteger("2148"));
            if (Test.mod(new BigInteger("4")).compareTo(Temp) == 0 && (Test.mod(new BigInteger("100")).compareTo(Temp) != 0 || Test.mod(new BigInteger("400")).compareTo(Temp) == 0))
            {
                there = true;
                System.out.printf("Ghost of K. M. Iftekhar!!!\n");
            }
            if (there == false)
            {
                System.out.printf("No ghost will come in this year\n");
            }
            }
      //      if (i == nCount-1)
        //    	System.out.printf("\n");
        }
    }
}

kangroo · Post by **kangroo** » Tue Nov 11, 2008 4:30 am

Hi,
I m getting WA ...I tried BigInt in JAVA...
I cant find wats wrong in my code...
anyone pls help me...

Code: Select all

import java.io.*;
import java.math.*;
import java.util.*;

class Main 
{

 public static boolean leap_year ( BigInteger b )
 {
  int a = 0;boolean leap = false;
  BigInteger [] d1 = new BigInteger[2];
  BigInteger [] d2 = new BigInteger[2];
  BigInteger [] d3 = new BigInteger[2];
  d1 = b.divideAndRemainder( BigInteger.valueOf (4) );
  d2 = b.divideAndRemainder( BigInteger.valueOf (100) );
  d3 = b.divideAndRemainder( BigInteger.valueOf (400) );
  
  if ( d3[1].toString().equals("0") ) 
   leap = true;
  else if ( d1[1].toString().equals("0") && !(d2[1].toString().equals("0")) ) 
   leap = true; 
  else leap = false; 
 	
  return leap;
 }


 public static void main ( String [] ar ) throws Exception 
 {
  BufferedReader br = new BufferedReader ( new InputStreamReader ( System.in ) );
  while ( true )
  {
   String s = br.readLine();   
   StringTokenizer st = new StringTokenizer (s , " ");
   s = st.nextToken();
   if ( s.equals("0") ) break;
   BigInteger yr = new BigInteger (s);
   System.out.println( yr.toString() );

   if ( yr.compareTo (BigInteger.valueOf(2148)) < 0 ) 
   {
    System.out.println( "No ghost will come in this year\n" );      
    continue;
   }
   
   
   long [] y = new long[10];
   y[0] = 2;y[1] = 5;y[2] = 7;y[3] = 11;y[4] = 15;y[5] = 20;y[6] = 28;y[7] = 36;y[8] = 4;

   String [] name = new String [10];
   name[0] = "Tanveer Ahsan";name[1] = "Shahriar Manzoor";
   name[2] = "Adrian Kugel";name[3] = "Anton Maydell";name[4] = "Derek Kisman";
   name[5] = "Rezaul Alam Chowdhury";name[6] = "Jimmy Mardell";
   name[7] = "Monirul Hasan";name[8] = "K. M. Iftekhar";

   BigInteger[] rem = new BigInteger[10];
   rem[0] = BigInteger.ZERO;
   rem[1] = BigInteger.valueOf (3);rem[2] = BigInteger.valueOf (6);
   rem[3] = BigInteger.valueOf (3);rem[4] = BigInteger.valueOf (3);
   rem[5] = BigInteger.valueOf (8);rem[6] = BigInteger.valueOf (20);
   rem[7] = BigInteger.valueOf (24);rem[8] = BigInteger.valueOf (0);
  
   boolean ok = false;
   for ( int i = 0 ; i < 9 ; i ++ )
   {
    BigInteger [] divrem = new BigInteger[2];
    divrem = yr.divideAndRemainder( BigInteger.valueOf (y[i]) );
    if ( i != 8 && divrem[1].toString().equals( rem[i].toString() ) )
    {
     System.out.println( "Ghost of " + name[i] + "!!!" );    
     ok = true;
    }

    if ( i == 8 && leap_year (yr) == true )
    {
     System.out.println( "Ghost of " + name[8] + "!!!" );    	
     ok = true;
    }
   }

   if ( ok == false )
    System.out.println( "No ghost will come in this year" );  
 
   System.out.println(""); 	
  } 
 }
}

thanks in advance!!!
pls help!!!

Eather · Post by **Eather** » Thu Feb 10, 2011 9:31 am

Im getting WA.. Please help me...

Code: Select all

/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */

package theghostofprogrammers;


import java.math.BigInteger;
import java.io.*;
import java.util.*;


/**
 *
 * @author Eather
 */
public class Main {

    /**
     * @param args the command line arguments
     */
    public static void main(String[] ar) throws Exception
    {
        // TODO code application logic here

        BigInteger Year;

        Scanner sc=new Scanner( System.in);
        int b=0;
        
        while(true)
        {
            int not=0;
            Year = sc.nextBigInteger();
            

            if ( Year.compareTo(BigInteger.ZERO) == 0 ) break;

                BigInteger  y = BigInteger.valueOf(2148);

                if(b==1)System.out.print("\n");b=1;

                System.out.println(Year);

                Year= Year.subtract(y);


                if(Year.equals(0))
                    Year = BigInteger.valueOf(2148);
                
                if(Year.compareTo(BigInteger.ZERO) > -1)
                {
                if(  Year.mod(BigInteger.valueOf(2)).compareTo(BigInteger.ZERO) == 0)
                { System.out.print("Ghost of Tanveer Ahsan!!!\n");not=1;}

                if(  Year.mod(BigInteger.valueOf(5)).compareTo(BigInteger.ZERO) == 0)
                {System.out.print("Ghost of Shahriar Manzoor!!!\n");not=1;}

                if(  Year.mod(BigInteger.valueOf(7)).compareTo(BigInteger.ZERO) == 0)
                {System.out.print("Ghost of Adrian Kugel!!!\n");not=1;}

                if(  Year.mod(BigInteger.valueOf(11)).compareTo(BigInteger.ZERO) == 0)
                { System.out.print("Ghost of Anton Maydell!!!\n");not=1;}

                if(  Year.mod(BigInteger.valueOf(15)).compareTo(BigInteger.ZERO) == 0)
                { System.out.print("Ghost of Derek Kisman!!!\n");not=1;}

                if(  Year.mod(BigInteger.valueOf(20)).compareTo(BigInteger.ZERO) == 0)
                {System.out.print("Ghost of Rezaul Alam Chowdhury!!!\n");not=1;}

                if(  Year.mod(BigInteger.valueOf(28)).compareTo(BigInteger.ZERO) == 0)
                {System.out.print("Ghost of Jimmy Mardell!!!\n");not=1;}

                if(  Year.mod(BigInteger.valueOf(36)).compareTo(BigInteger.ZERO) == 0)
                {System.out.print("Ghost of Monirul Hasan!!!\n");not=1;}

                if(  Year.mod(BigInteger.valueOf(4)).compareTo(BigInteger.ZERO) == 0)
                {
                    if(  Year.mod(BigInteger.valueOf(100)).compareTo(BigInteger.ZERO) > 0)
                    {System.out.println("Ghost of K. M. Iftekhar!!!");not=1;}

                    else if(  Year.mod(BigInteger.valueOf(400)).compareTo(BigInteger.ZERO) == 0)
                    {System.out.println("Ghost of K. M. Iftekhar!!!");not=1;}
                }

                if(not==0)System.out.println("No ghost will come in this year");
                }
                
                else   System.out.println("No ghost will come in this year");
            
        }

    }

}

sumit saha shawon · Post by **sumit saha shawon** » Tue Jun 26, 2012 11:03 pm

My output is ok.But I am getting wrong answer.Please help me.
My code is:

#include<stdio.h>
#include<string.h>
//char chech_leap(char);
int main()
{
char year[90];

while(scanf("%s",&year)==1)
{

int len,i;
len=strlen(year);
if(len==1&&year[0]=='0')
break;
puts(year);

if(len<=3)
{
printf("No ghost will come in this year\n\n");
continue;
}
if(len==4)
{
int num=0;
int j;
for(j=0; j<len; j++)
num=(num*10)+(year[j]-'0');
// printf("%d",num);
if(num<=2147)
{
printf("No ghost will come in this year\n\n");
continue;
}
}
int dv2=0,dv5=0,dv7=0,dv11=0,dv15=0,dv20=0,dv28=0,dv36=0,dv400=0,dv4=0,dv100=0;
for(i=0; i<len; i++)
{
dv2=((dv2*10)+(year-'0'))%2;
dv5=((dv5*10)+(year-'0'))%5;
dv7=((dv7*10)+(year-'0'))%7;
dv11=((dv11*10)+(year-'0'))%11;
dv15=((dv15*10)+(year-'0'))%15;
dv20=((dv20*10)+(year-'0'))%20;
dv28=((dv28*10)+(year-'0'))%28;
dv36=((dv36*10)+(year-'0'))%36;
dv4=((dv4*10)+(year-'0'))%4;
dv100=((dv100*10)+(year-'0'))%100;
dv400=((dv400*10)+(year[i]-'0'))%400;

}
if(dv2==0)
printf("Ghost of Tanveer Ahsan!!!\n");
if(dv5==3)
printf("Ghost of Shahriar Manzoor!!!\n");
if(dv7==6)
printf("Ghost of Adrian Kugel!!!\n");
if(dv11==3)
printf("Ghost of Anton Maydell!!!\n");
if(dv15==3)
printf("Ghost of Derek Kisman!!!\n");
if(dv20==8)
printf("Ghost of Rezaul Alam Chowdhury!!!\n");
if(dv28==20)
printf("Ghost of Jimmy Mardell!!!\n");
if(dv36==24)
printf("Ghost of Monirul Hasan!!!\n");
if((dv400==0)||(dv4==0&&dv100!=0))
printf("Ghost of K. M. Iftekhar!!!\n");
else if(dv2!=0&&dv5!=3&&dv7!=6&&dv11!=3&&dv15!=3&&dv20!=8&&dv28!=20&&dv36!=24)
printf("No ghost will come in this year\n");
printf("\n");
}
return 0;
}

sumit saha shawon · Post by **sumit saha shawon** » Tue Jun 26, 2012 11:09 pm

My output is ok.But I am getting wa.
my code:

#include<stdio.h>
#include<string.h>
//char chech_leap(char);
int main()
{
char year[90];

while(scanf("%s",&year)==1)
{

int len,i;
len=strlen(year);
if(len==1&&year[0]=='0')
break;
puts(year);

if(len<=3)
{
printf("No ghost will come in this year\n\n");
continue;
}
if(len==4)
{
int num=0;
int j;
for(j=0; j<len; j++)
num=(num*10)+(year[j]-'0');
// printf("%d",num);
if(num<=2147)
{
printf("No ghost will come in this year\n\n");
continue;
}
}
int dv2=0,dv5=0,dv7=0,dv11=0,dv15=0,dv20=0,dv28=0,dv36=0,dv400=0,dv4=0,dv100=0;
for(i=0; i<len; i++)
{
dv2=((dv2*10)+(year-'0'))%2;
dv5=((dv5*10)+(year-'0'))%5;
dv7=((dv7*10)+(year-'0'))%7;
dv11=((dv11*10)+(year-'0'))%11;
dv15=((dv15*10)+(year-'0'))%15;
dv20=((dv20*10)+(year-'0'))%20;
dv28=((dv28*10)+(year-'0'))%28;
dv36=((dv36*10)+(year-'0'))%36;
dv4=((dv4*10)+(year-'0'))%4;
dv100=((dv100*10)+(year-'0'))%100;
dv400=((dv400*10)+(year[i]-'0'))%400;

}
if(dv2==0)
printf("Ghost of Tanveer Ahsan!!!\n");
if(dv5==3)
printf("Ghost of Shahriar Manzoor!!!\n");
if(dv7==6)
printf("Ghost of Adrian Kugel!!!\n");
if(dv11==3)
printf("Ghost of Anton Maydell!!!\n");
if(dv15==3)
printf("Ghost of Derek Kisman!!!\n");
if(dv20==8)
printf("Ghost of Rezaul Alam Chowdhury!!!\n");
if(dv28==20)
printf("Ghost of Jimmy Mardell!!!\n");
if(dv36==24)
printf("Ghost of Monirul Hasan!!!\n");
if((dv400==0)||(dv4==0&&dv100!=0))
printf("Ghost of K. M. Iftekhar!!!\n");
else if(dv2!=0&&dv5!=3&&dv7!=6&&dv11!=3&&dv15!=3&&dv20!=8&&dv28!=20&&dv36!=24)
printf("No ghost will come in this year\n");
printf("\n");
}
return 0;
}

brianfry713 · Post by **brianfry713** » Tue Jun 26, 2012 11:58 pm

Print a blank line between two consecutive output. You've got an extra blank line at the end of the output.

OJ Board

10992 - The Ghost of Programmers

must use BigInteger Class?

must use BigInteger Class?

Re: 10992 - The Ghost of Programmers

Re: 10992 - The Ghost of Programmers

Why WA?? Plz Helppppppppp....

Re: 10992 - The Ghost of Programmers

Re: 10992 - The Ghost of Programmers

Re: 10992 - The Ghost of Programmers