Home

online judge

29. Hash it! - Solution

After going back and forth over this code for it seems like an eternity (about an hour) I finally got an accepted solution. The problem turned out to be a small typo.

Here it is, my solution to https://www.spoj.pl/problems/HASHIT/ in C#. 

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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107

using System;
using System.Text;
 
namespace HASHIT
{
        class MainClass
        {
                public static void Main (string[] args)
                {                       
                        int t = Convert.ToInt32 (System.Console.ReadLine ());
                        
                        for (int i = 0; i < t; i++) 
                        {
                                string[] table = new string[101];
                                int n = Convert.ToInt32 (System.Console.ReadLine ());
                                for (int i2 = 0; i2 < n; i2++) 
                                {
                                        string line = System.Console.ReadLine ();
                                        string op = line.Substring (0, 3);
                                        string key = line.Substring (4);
                                        int ix = FindKey (table, key);
                                        
                                        if (op == "ADD") 
                                        {
                                                if (ix == -1) 
                                                {
                                                        ix = FindNextOpenAddress (table, Hash (key));
                                                        if (ix >= 0) 
                                                        {
                                                                table[ix] = key;
                                                        }
                                                }
                                        } 
                                        else 
                                        {
                                                if (ix >= 0) 
                                                {
                                                        table[ix] = string.Empty;
                                                }
                                        }
                                }
 
                                StringBuilder sb = new StringBuilder ();
                                int count = 0;
                                for (int j = 0; j < 101; j++) 
                                {
                                        if (!string.IsNullOrEmpty (table[j])) 
                                        {
                                                count++;
                                                sb.AppendLine (j + ":" + table[j]);
                                        }
                                }
                                Console.WriteLine (count);
                                Console.Write (sb.ToString ());
                        }
                }
 
                public static int Hash (string key)
                {
                        int ret = 0;
                        ret = h (key) % 101;
                        return ret;
                }
 
                public static int h (string key)
                {
                        int ret = 0;
                        int cnt = key.Length;
                        for (int i = 0; i < cnt; i++) 
                        {
                                ret += (int)key[i] * (i + 1);
                        }
                        return ret * 19;
                }
 
                public static int FindKey (string[] table, string key)
                {
                        int ix = Hash (key);
                        if (table[ix] == key)
                                return ix;
                        for (int j = 1; j < 20; j++) 
                        {
                                int newix = (ix + j * j + 23 * j) % 101;
                                if (table[newix] == key) 
                                {
                                        return newix;
                                }
                        }
                        return -1;
                }
 
                public static int FindNextOpenAddress (string[] table, int ix)
                {
                        if (string.IsNullOrEmpty (table[ix]))
                                return ix;
                        for (int j = 1; j < 20; j++) 
                        {
                                int newix = (ix + j * j + 23 * j) % 101;
                                if (string.IsNullOrEmpty (table[newix])) 
                                {
                                        return newix;
                                }
                        }
                        return -1;
                }
        }
}

899. Ws Cipher

https://www.spoj.pl/problems/WSCIPHER/

 

Weird Wally's Wireless Widgets, Inc. manufactures an eclectic assortment of small, wireless, network capable devices, ranging from dog collars, to pencils, to fishing bobbers. All these devices have very small memories. Encryption algorithms like Rijndael, the candidate for the Advanced Encryption Standard (AES) are demonstrably secure but they don't fit in such a tiny memory. In order to provide some security for transmissions to and from the devices, WWWW uses the following algorithm, which you are to implement.

Encrypting a message requires three integer keys, k1, k2, and k3. The letters [a-i] form one group, [j-r] a second group, and everything else ([s-z] and underscore) the third group. Within each group the letters are rotated left by ki positions in the message. Each group is rotated independently of the other two. Decrypting the message means doing a right rotation by ki positions within each group.

Consider the message the_quick_brown_fox encrypted with ki values of 2, 3 and 1. The encrypted string is _icuo_bfnwhoq_kxert. The figure below shows the decrypting right rotations for one character in each of the three character groups.

Looking at all the letters in the group [a-i] we see {i,c,b,f,h,e} appear at positions {2,3,7,8,11,17} within the encrypted message. After a right rotation of k1=2, these positions contain the letters {h,e,i,c,b,f}. The table below shows the intermediate strings that come from doing all the rotations in the first group, then all rotations in the second group, then all the rotations in the third group. Rotating letters in one group will not change any letters in any of the other groups.

  [a-i], k1= 2 [j-r], k2= 3 [s-z] and _, k3= 1
Encrypted: _icuo_bfnwhoq_kxert _heuo_icnwboq_kxfrt _heuq_ickwbro_nxfot
Decrypted: _heuo_icnwboq_kxfrt _heuq_ickwbro_nxfot the_quick_brown_fox
Changes: 
 ^^   ^^  ^     ^  
    ^   ^  ^^ ^  ^  
^  ^ ^   ^   ^ ^  ^

All input strings contain only lowercase letters and underscores(_). Each string will be at most 80 characters long. The ki are all positive integers in the range 1-100.

Input consists of information for one or more encrypted messages. Each problem begins with one line containing k1, k2, and k3 followed by a line containing the encrypted message. The end of the input is signalled by a line with all key values of 0.

For each encrypted message, the output is a single line containing the decrypted string.

Input:
2 3 1
_icuo_bfnwhoq_kxert
1 1 1
bcalmkyzx
3 7 4
wcb_mxfep_dorul_eov_qtkrhe_ozany_dgtoh_u_eji
2 4 3
cjvdksaltbmu
0 0 0

Output:
the_quick_brown_fox
abcklmxyz
the_quick_brown_fox_jumped_over_the_lazy_dog
ajsbktcludmv
Added by:Wanderley Guimarães
Date:2006-06-09
Time limit:1s
Source limit:50000B
Languages:All except: ERL TECS JS
Resource:ACM Mid Central Regionals 2001
 

My Solution

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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100

using System;
using System.Collections.Generic;
 
namespace www.spoj.pl._899_WSCIPHER
{
    class Program
    {
        static void Main(string[] args)
        {
            while (true)
            {
                string line = Console.In.ReadLine();
                string[] nums = line.Split(new char[] { ' ' });
                if (nums.Length == 3)
                {
                    int k1 = 0;
                    int.TryParse(nums[0], out k1);
                    int k2 = 0;
                    int.TryParse(nums[1], out k2);
                    int k3 = 0;
                    int.TryParse(nums[2], out k3);
 
                    if (k1 == 0 && k2 == 0 && k3 == 0)
                        break;
 
                    string ciphertext = Console.In.ReadLine();
 
                    CipherGroup Group1 = new CipherGroup(k1);
                    CipherGroup Group2 = new CipherGroup(k2);
                    CipherGroup Group3 = new CipherGroup(k3);
                    int len = ciphertext.Length;
                    for (int i = 0; i < len; i++)
                    {
                        char c = ciphertext[i];
                        if (c >= 'a' && c <= 'i')
                        {
                            Group1.Add(c, i);
                        }
                        else if (c >= 'j' && c <= 'r')
                        {
                            Group2.Add(c, i);
                        }
                        else
                        {
                            Group3.Add(c, i);
                        }
                    }
 
                    Group1.Rotate();
                    Group2.Rotate();
                    Group3.Rotate();
 
                    string[] letters = new string[len];
                    Group1.AddToArray(letters);
                    Group2.AddToArray(letters);
                    Group3.AddToArray(letters);
 
                    Console.WriteLine(string.Join("", letters));
                }
            }
        }
    }
 
    public class CipherGroup
    {
        public int k { get; set; }
        public List<char> Letters { get; set; }
        public List<int> Positions { get; set; }
        public CipherGroup(int k1)
        {
            k = k1;
            Letters = new List<char>();
            Positions = new List<int>();
        }
        public void Add(char c, int p)
        {
            Letters.Add(c);
            Positions.Add(p);
        }
        public void Rotate()
        {
            int len = Letters.Count;
            if (len == 0) return;
            for (int i = 0; i < k; i++)
            {
                Letters.Insert(0, Letters[len - 1]);
                Letters.RemoveAt(len);
            }
        }
 
        public void AddToArray(string[] letters)
        {
            int len = Letters.Count;
            for (int i = 0; i < len; i++)
            {
                letters[Positions[i]] = Letters[i].ToString();
            }
        }
    }
}

Prime Time - UVA Online Judge

http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=14&page=show_problem&problem=1141

 Problem G: Prime Time 

 

The Problem

Euler is a well-known matematician, and, among many other things, he discovered that the formula n^2 + n + 41 produces a prime for 0 <= n < 40. For n = 40, the formula produces 1681, which is 41 * 41. Even though this formula doesn't always produce a prime, it still produces a lot of primes. It's known that for n <= 10000000, there are 47,5% of primes produced by the formula!

So, you'll write a program that will output how many primes does the formula output for a certain interval.

The Input

Each line of input will be given two positive integer a and b such that 0 <= a <= b <= 10000. You must read until the end of the file.

The Output

For each pair a,b read, you must output the percentage of prime numbers produced by the formula in this interval (a <= n <= b) rounded to two decimal digits (with round half up rule).

Sample Input

0 39
0 40
39 40
1423 2222

Sample Output

100.00
97.56
50.00
44.13

My Solution

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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81

#include <stdio.h>
#include <math.h>
 
long isprime(long n);
long n2n41(long n);
int primepct[10001];
 
int main(int argc, char **argv)
{
        long a, b, i, ip;
        int notprime, prime;
        for(i = 0; i < 10001; i++)
        {
                        primepct[i] = 0;
        }
        while (scanf("%ld %ld", &a, &b) != EOF)
        {
                for(i = a; i <= b; i++)
                {
                        if(primepct[i-1]==0)
                        {                               
                                if(isprime(n2n41(i))==0)
                                {
                                        prime++;
                                        primepct[i-1] = 1;
                                }
                                else
                                {
                                        notprime++;
                                        primepct[i-1] = -1;
                                }
                        }
                        else
                        {
                                if(primepct[i-1]==1)
                                {
                                        prime++;
                                }
                                else
                                {
                                        notprime++;
                                }
                        }
                }
                printf("%.2f\n", floor(((double)prime/(prime+notprime))*10000+.5)/100);
                notprime = 0;
                prime=0;
        }
        return 0;
}
 
long n2n41(long n)
{
        return n*n+n+41;
}
 
long isprime(long n)
{
        long i = 3;
        long sqn = 0;
        
        while (n%2==0)
        {
                n /= 2;
                return 1;
        }
        sqn = (sqrt(n))+1;
        while (i <= sqn)
        {
                if ((n%i)==0)
                {
                        n /= i;
                        return 1;
                }
                else
                {
                        i += 2;                 
                }
        }
        return 0;
}

Problem 583: UVA Online Judge - Prime Factors

http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=7&page=show_problem&problem=524

  Prime Factors 

Webster defines prime as:


prime (prim) n.[ME, fr. MF, fem. of prin first, L primus; akin to L prior] 1 :first in time: original 2 a : having no factor except itself and one (3 is a prime number ) b : having no common factor except one ( 12 and 25 are relatively  ) 3 a : first in rank, authority or significance : principal b : having the highest quality or value (television time) [from Webster's New Collegiate Dictionary]

 


The most relevant definition for this problem is 2a: An integer g>1 is said to be prime if and only if its only positive divisors are itself and one (otherwise it is said to be composite). For example, the number 21 is composite; the number 23 is prime. Note that the decompositon of a positive number g into its prime factors, i.e.,

g = f1 x f2 x ... x fn

 

is unique if we assert that fi > 1 for all i and fi <fj for i<j.

One interesting class of prime numbers are the so-called Mersenne primes which are of the form 2p- 1. Euler proved that 231 - 1 is prime in 1772 -- all without the aid of a computer.

 

Input 

The input will consist of a sequence of numbers. Each line of input will contain one number g in the range -231 < g <231, but different of -1 and 1. The end of input will be indicated by an input line having a value of zero.

 

Output 

For each line of input, your program should print a line of output consisting of the input number and its prime factors. For an input number g > 0, g =  f1 x f2 x ... x fn, where each fi is a prime number greater than unity (with fi <fj for i<j), the format of the output line should be

 

g = f1 x f2 x ... x fn

 

When g < 0, if | g | =  f1 x f2 x ... x fn, the format of the output line should be

g = -1 x f1 x f2 x ... x fn

 

Sample Input 

-190
-191
-192
-193
-194
195
196
197
198
199
200
0

Sample Output 

-190 = -1 x 2 x 5 x 19
-191 = -1 x 191
-192 = -1 x 2 x 2 x 2 x 2 x 2 x 2 x 3
-193 = -1 x 193
-194 = -1 x 2 x 97
195 = 3 x 5 x 13
196 = 2 x 2 x 7 x 7
197 = 197
198 = 2 x 3 x 3 x 11
199 = 199
200 = 2 x 2 x 2 x 5 x 5

My Solution

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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77

#include <stdio.h>
#include <math.h>
 
void print_factors(long n);
 
int main(int argc, char **argv)
{
        long n;
        while (1)
        {
                scanf("%ld", &n);
                if (n==0)
                {
                        break;
                }
                printf("%ld = ", n);
                if (n<0)
                {
                        printf("-1 x ");
                        n = -n;
                }
                print_factors(n);
                printf("\n");
        }
        return 0;
}
 
void print_factors(long n)
{
        int first = 1;
        while (n%2==0)
        {
                if (first)
                {
                        printf("2");
                        first = 0;
                }
                else
                {
                        printf(" x 2");
                }
                n /= 2;
        }
        long i = 3;
        long sqn = (sqrt(n))+1;
        while (i <= sqn)
        {
                if ((n%i)==0)
                {
                        if (first)
                        {
                                printf("%ld", i);
                                first = 0;
                        }
                        else
                        {
                                printf(" x %ld", i);
                        }
                        n /= i;
                }
                else
                {
                        i += 2;                 
                }
        }
        if (n>1)
        {
                if(first)
                {
                        printf("%ld", n);
                }
                else
                {
                        printf(" x %ld", n);
                }
        }
}