ACM (UVa) : 10070


Give a closer look at this line:
“All the years will not be less than 2000 (to avoid the earlier different rules for leap years). Please don’t assume anything else.”

The input number would be very big, like: 865756756227892375172800
so, Ur program must have the capability to manipulate such big integers

Analysis:
Take the inputs as a string.
The actual headache is how to divide a string by 4/100/400/55!!

Cautions: Have u already taken a medicine for this headache ??
if u’ve done so then .. aaaa .. (what should i say !!) .. good job !
anyway, It could be solved easily by a clever method, without getting TLE & as well as without having a headache tablet !

String A
Mod 4 = 0 (initially inserted 0 (zero))
Continue ( k = 1 to string_length ) : k++
Mod4 = Mod4 * 10 + ( A [k] – ‘0’ )  % 4;

After this loop,
Mod4 gives u the remainder. Means, String A % 4 = Mod4
so, if ( Mod4 is equals to zero (0) ) then String A is divisible by 4

Critical input: [taken from UVa Online Judge forum]
22000
22055
22220
330000
330015
330220
4248035245857302861304475122262852382232831183377907185400973044372526725256648804647567360

Critical output:
This is Leap year.
This is buluculu festival year.

This is ordinary year.

This is Leap year.
This is buluculu festival year.

This is Leap year.
This is huluculu festival year.
This is buluculu festival year.

This is huluculu festival year.

This is Leap year.
This is buluculu festival year.

This is leap year.
This is huluculu festival year.
This is bulukulu festival year.

Again, do not print an extra line after last test case. For example:

This is leap year.
:: Blank Line ::
This is leap year.
This is huluculu festival year.
:: Blank Line ::
This is huluculu festival year.
:: Blank Line ::
This is an ordinary year.


#include <stdio.h>
#include <math.h>
#include <string.h>
#include <iostream.h> 

int main ()
{
	long Flag, Mod4, Mod100, Mod400, Mod15, Mod55, I, Len, leap;
	char A[1000000];
	int print = 0;

	while (cin >> A){

		if ( print != 0 )
			printf("\n");
		print = 1;
		
		leap = Flag = Mod4 = Mod100 = Mod400 = Mod15 = Mod55 = 0;

		Len = strlen (A);

		for (I=0; I< Len; I++) {

			Mod4 = ((Mod4 * 10) + (A[I]-'0')) % 4;
			Mod100 = ((Mod100 * 10) + (A[I]-'0')) % 100;
			Mod400 = ((Mod400 * 10) + (A[I]-'0')) % 400;
			Mod15 = ((Mod15 * 10) + (A[I]-'0')) % 15;
			Mod55 = ((Mod55 * 10) + (A[I]-'0')) % 55;
		}

		if ((Mod4==0 && Mod100!=0) || Mod400==0){
			printf("This is leap year.\n");
			leap = 1;
			Flag = 1;
		}

		if (Mod15==0){
			printf("This is huluculu festival year.\n");
			Flag = 1;
		}

		if (leap==1 && Mod55==0)
			printf("This is bulukulu festival year.\n");

		if (Flag==0)
			printf("This is an ordinary year.\n");
	}
	return 0;
}
Advertisements

19 thoughts on “ACM (UVa) : 10070

  1. Hi,
    Need a help dude. Can you tell me how do I redirect input in a compiled java file. For eg. in C++, if I create a new file, compile it, FileName.exe will be created (in windows environment). And then, to redirect input and output to this exe, we use
    FileName output.
    What do we use to achieve the same in java?
    Thanks!
    Gagan.

  2. hi Gagan
    i can’t see any relation of your question and this post .. may be these two are disguisedly interrelated 😛
    mm so far i understand ur ques, u want a double click executable file which is written in java
    surely u can make a FileName.jar file from ur java source code
    There are many ways to make a .jar file
    Here u find a solution using NetBeans : make a jar

  3. hi taha,
    its an easy process
    by multiplying mod4 with 10, we will get the actual number
    for example,
    u r given a string str [] = “85632”
    using the process u can get it as integer

    #include <stdio.h>
    
    int main ()
    {
        char str [] = "85632";
        int mod = 0;
    
        for ( int i = 0; str [i]; i++ ) {
            mod = (mod * 10 + (str [i] - '0')) % divisor;
        }
    
        printf ("%d\n", mod);
    }
    

    hope, this code will help

  4. I think the way u calculate the modulo of a string doesn’t work I tried it but still not working
    Maybe you made a mistake of taping the code
    can u please give the code another time if its possible
    thx !

  5. @saad
    sorry, my mistake
    i’ve updated the code, now it should work
    in this code,
    “str” contains dividend
    “mod” is the remainder
    “divisor” is divisor! 😛
    thanks to you for your concern.

  6. your code helps me a lot to understand the critical inputs in UVa. but can u plz explain how this code works:
    for ( int i = 0; str [i]; i++ ) {
    mod = (mod * 10 + (str [i] – ‘0’)) % divisor;
    }

    thanx in advance.

  7. @Ratul
    for ( int i = 0; str [i]; i++ )
    loops through the entire string array str

    guess, str [] = “85632”
    divisor = 5

    finally mod should be = 2 (i.e, 85632 % 5 = 2)

    suppose, we are going to divide the number with divisor by simple paper-pencil division

    5 ) 85632 ( 17126
    	5
    	------
    	35
    	35
    	------
    	 06
    	  5
    	------
    	  13
    	  10	
    	------
    	   32
    	   30
    	------
    	    2
    

    now simulate the code with paper-pencil and i hope u will find the ans 🙂

  8. thanx for ur reply. I actually want to know why I multiply mod with 10 and deduct ‘0’ from i-th index ed character… how can I know which is to be multiplied, or deducted?

  9. @Ratul
    int x = ‘2’;

    printf (“%d\n”, x);

    do u know the output?
    50

    int x = ‘2’ – ‘0’;

    printf (“%d\n”, x);

    output: 2

    subtraction of ‘0’ makes an integer character to actual integer

    look at the example carefully
    5 ) 85632 (
    5
    ———
    35

    initially, mod = 0
    after 1st iteration, mod = 3
    3 is not divisible by divisor (5)
    so we take into account the 2nd digit of dividend (5)
    before that, we need to multiply 3 by 10
    3 * 10 + 5 = 35

  10. Yes … I m clear now … I didn’t know “subtraction of ’0′ makes an integer character to actual integer” . Thanx for giving me time.

  11. very well written indeed …
    but i have used a different strategy …
    1.determination of the divisibility by 400, 55, 4,100, 15 …. 😀
    in order to find the divisibility by 400 .. well needs to check the divisibility of 16 && 25 😀
    and there u go 😀 happy coding … 🙂

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s