Archive

Archive for July, 2015

Calculate Sum Off All 8 Neighbors Of Each Element In An Integer Array (Tính tổng các giá trị lân cận trong mảng 2 chiều)

July 25th, 2015 No comments

http://i.imgur.com/Rr67DFK.gif

http://i.imgur.com/WUzKnmp.gif

You can use If-else statements to do this, very simple, but i use another way to calculate this, help you improving about FOR-LOOP 🙂

[code language=”cpp”]

#include <iostream>
using namespace std;
int main() {
int IntArray[5][5] = {
{1, 1, 1, 1, 1},
{2, 2, 2, 2, 2},
{3, 3, 3, 3, 3},
{4, 4, 4, 4, 4},
{5, 5, 5, 5, 5}
};

for(int i=0; i<5; i++){
for(int j=0; j<5; j++){
cout << IntArray[i][j] << " ";
}
cout << endl;
}
cout << endl;
int TempArray[7][7] = {0};
for(int i=1; i<6; i++){
for(int j=1; j<6; j++){
TempArray[i][j] = IntArray[i-1][j-1];
}
}

cout << "After add a \"zero-shape\"" << endl;
cout << endl;
for(int i=0; i<7; i++){
for(int j=0; j<7; j++){
cout << TempArray[i][j] << " ";
}
cout << endl;
}
int ResultArray[5][5] = {0};
for(int i=1; i<7; i++){
for(int j=1; j<7; j++){
ResultArray[i-1][j-1] =
TempArray[i-1][j-1] + TempArray[i-1][j] +
TempArray[i-1][j+1] + TempArray[i][j-1] +
TempArray[i][j+1] + TempArray[i+1][j-1] +
TempArray[i+1][j] + TempArray[i+1][j+1];
}
}
cout << "\nHere is result\n" << endl;
for(int i=0; i<5; i++){
for(int j=0; j<5; j++){
cout << ResultArray[i][j] << " ";
}
cout << endl;
}
return 0;
}

[/code]

Categories: Algorithms, C/C++ Tags:

[URI Online Judge] – 1237 – Compare Substring

July 25th, 2015 No comments

Find the longest common substring between the two informed Strings. The substring can be any part of the String, including the entire String. If there is no common substring, return 0. The search is case sensitive (‘x’ != ‘X’).

Input

The input contains several test cases. Each test case is composed by two lines that contains a string each. Both input Strings will contain between 1 and 50, inclusive, letters (a-z, A-Z), and/or spaces.

Output

The length of the longest common substring between the two Strings.

Sample InputSample Output
abcdef
cdofhij
TWO
FOUR
abracadabra
open
Hey This java is hot
Java is a new paradigm
2
1
0
7

my solution:

[code language=”cpp”]

#include <iostream>
#include <iomanip>
#include <cmath>
#include <cstring>

using namespace std;

int count_substrings (char *str1, char *str2) {
int n1 = strlen(str1), n2 = strlen(str2);
int max = 0;

for (int i = 0; i < n1; i++) {
for (int j = 0; j < n2; j++) {
if (str1[i] == str2[j]) {
int c = 0;
for (int k = 0; k+i<n1, k+j<n2; k++) {
if (str1[k+i] != str2[k+j])
break;
c++;
}
if (c > max)
max = c;
}
}
}
return max;
}

int main () {
char str1[100], str2[100];

cin.getline(str1, 100);
while (cin.getline(str2, 100)) {
cout << count_substrings(str1, str2) << endl;
cin.getline(str1, 100);
}

return 0;
}

[/code]

[URI Online Judge] – 1193 – Base Conversion

July 25th, 2015 No comments

The Julian math teacher has marked a test whose content will on to convert between decimal, hexadecimal and binary numbers. For Julian, this kind of convertion is one of the most complex things to be done. Regardless of the time spent for studying these contents, he simple don\’t understand. So, as you understand about computing and is a friend of Julian, he asked for your help to make a program that checks if the conversions made ​​by him are correct.

Input

The input contains many test cases. The first line of input contains an integer N indicating the number of test cases that follow, one by line. Each test case contains a number X (X > 0) followed by a Y text with three characters, indicating if the X number is in binary, decimal or hexadecimal. Regardless of the format, any of the numbers must fit into a 32-bit integer.

Output

For each test case, Julian wants that you print the number of the test case folloed by two lines, that contains the oiginal number converted for each one of the other two bases. The sequence of the bases of output is always: decimal, hexadecimal (lowercase) and binary, ie must respect this order obviously excluding the input format.
Note: should print a blank line after each test case, even after the last test case.

Sample InputSample Output
3
101 bin
101 dec
8f hex
Case 1:
5 dec
5 hex

Case 2:
65 hex
1100101 bin

Case 3:
143 dec
10001111 bin

My solution:

[code language=”cpp”]

#include <iostream>
#include <iomanip>
#include <cmath>
#include <cstdlib>
#include <string>

using namespace std;

char digit_hex (int x) {
if (x >= 0 && x < 10)
return x+’0′;
else if (x < 16)
return x-10+’a’;
else
return ‘!’;
}

string tobin (int x) {
string aux;
while (x > 0) {
char c = x%2+’0′;
aux = c + aux;
x /= 2;
}
return aux;
}

string tohex (int x) {
string aux;
while (x > 0) {
aux = digit_hex(x%16) + aux;
x /= 16;
}
return aux;
}

int main () {
char str[50];
string type;
int x, n;

cin >> n;
for (int i = 0; i < n; i++) {
cin >> str >> type;

cout << "Case " << i+1 << ‘:’ << endl;
if (type == "bin") {
x = strtol(str, 0, 2);
cout << x << " dec" << endl;
cout << tohex(x) << " hex" << endl;
} else if (type == "dec") {
x = strtol(str, 0, 10);
cout << tohex(x) << " hex" << endl;
cout << tobin(x) << " bin" << endl;
} else {
x = strtol(str, 0, 16);
cout << x << " dec" << endl;
cout << tobin(x) << " bin" << endl;
}

cout << endl;
}

return 0;
}

[/code]

[URI Online Judge] – 1424 – Easy Problem from Rujia Liu?

July 25th, 2015 No comments

Though Rujia Liu usually sets hard problems for contests (for example, regional contests like Xi’an 2006, Beijing 2007 and Wuhan 2009, or UVa OJ contests like Rujia Liu’s Presents 1 and 2), he occasionally sets easy problem (for example, ‘the Coco-Cola Store’ in UVa OJ), to encourage more people to solve his problems 😀

Given an array, your task is to find the k-th occurrence (from left to right) of an integer v. To make the problem more difficult (and interesting!), you’ll have to answer m such queries.

Input

There are several test cases. The first line of each test case contains two integers n, m (1 ≤ n, m ≤ 100,000), the number of elements in the array, and the number of queries. The next line contains npositive integers not larger than 1,000,000. Each of the following m lines contains two integer k and v (1 ≤k n, 1 ≤ v ≤ 1,000,000).

The input is terminated by end-of-file (EOF). The size of input file does not exceed 5 MB.

Output

For each query, print the 1-based location of the occurrence. If there is no such element, output 0 instead.

Sample InputSample Output
8 4
1 3 2 2 4 3 2 1
1 3
2 4
3 2
4 2
2
0
7
0

my solution:

[code language=”cpp”]

#include <vector>
#include <cstring>
#include <iostream>
using namespace std;

vector<int> T[1000010];

int main() {
int n, m;
while(cin >> n >> m) {
memset(T, 0, sizeof T);
for(int i=1; i<=n; i++) {
int temp; cin >> temp;
T[temp].push_back(i);
}

while(m–) {
int k, v;
cin >> k >> v;
k–;
if (k<T[v].size())
cout << T[v][k] << endl;
else
cout << 0 << endl;
}
}
}

[/code]

[URI Online Judge] – 1023 – Drought

July 25th, 2015 No comments

Due to the continuous drought that happened recently in some regions of Brazil, the Federal Government created an agency to assess the consumption of these regions in order to verify the behavior of the population at the time of rationing. This agency will take some cities (for sampling) and it will verify the consumption of each of the townspeople and the average consumption per inhabitant of each town.

Input

The input contains a number of test cases. The first line of each test case contains an integer N (1 ≤ N ≤ 1 * 10 6), indicating the amount properties. The following N lines contains a pair of values X (1 ≤ X ≤ 10) and Y( 1 ≤ Y ≤ 200) indicating the number of residents of each property and its total consumption (m3). Surely, no residence consumes more than 200 m3 per month. The end of input is represented by zero.

Output

For each test case you must present the message “Cidade# n:”, where n is the number of the city in the sequence (1, 2, 3, …), and then you must list in ascending order of consumption, the amount people followed by a hyphen and the consumption of these people, rounding the value down. In the third line of output you should present the consumption per person in that town, with two decimal places without rounding, considering the total real consumption. Print a blank line between two consecutives test cases. There is no blank line at end of output.

Sample InputSample Output
3
3 22
2 11
3 39
5
1 25
2 20
3 31
2 40
6 70
0
Cidade# 1:
2-5 3-7 3-13
Consumo medio: 9.00 m3.

Cidade# 2:
5-10 6-11 2-20 1-25
Consumo medio: 13.28 m3.

My solution:

[code language=”cpp”]
<pre class="brush: cpp; , toolbar: false">#include <iostream>
#include <iomanip>
#include <map>
#include <cmath>

using namespace std;

map<int, int> r;

int main(){
int n, nn = 0, x, y, s, c;
double xs, ys;
bool first = true;

while (cin >> n && n != 0){
if (!first) {
cout << endl;
}
first = false;

xs = 0.0;
ys = 0.0;
nn++;

r.clear();

while (n–){
cin >> x >> y;
ys += y;
xs += x;

if (r[y / x] != 0) r[y / x] += x;
else r[y / x] = x;
}

s = r.size();
c = 0;

cout << "Cidade# " << nn << ":" << endl;
for(map<int, int>::iterator iter = r.begin(); iter != r.end(); iter++){
cout << iter->second << "-" << iter->first;
if (c < s – 1) cout << " ";
c++;
}

cout << endl;
cout << "Consumo medio: ";
cout << fixed << setprecision(2) << floor((ys / xs) * 100) / 100;
cout << " m3." << endl;
}
return 0;
}</pre>
[/code]